ETRI-Knowledge Sharing Plaform



논문 검색
구분 SCI
연도 ~ 키워드


학술지 Content Distribution by Multiple Multicast Trees and Intersession Cooperation: Optimal Algorithms and Approximations
Cited 4 time in scopus Download 0 time Share share facebook twitter linkedin kakaostory
Xiaoying Zheng, 조충래, Ye Xia
Computer Networks : The International Journal of Telecommunications Networking, v.83, pp.100-117
15MI2200, (통합)스마트 네트워킹 핵심 기술 개발, 양선희
In traditional massive content distribution with multiple sessions, the sessions form separate overlay networks and operate independently, where some sessions may suffer from insufficient resources even though other sessions have excessive resources. To cope with this problem, we consider the universal swarming approach, which allows multiple sessions to cooperate with each other. We formulate the problem of finding the optimal resource allocation to maximize the sum of the session utilities and present a subgradient algorithm which converges to the optimal solution in the time-average sense. The solution involves an NP-hard subproblem of finding a minimum-cost Steiner tree. We cope with this difficulty by using a column generation method, which reduces the number of Steiner-tree computations. Furthermore, we allow the use of approximate solutions to the Steiner-tree subproblem. We show that the approximation ratio to the overall problem turns out to be no less than the reciprocal of the approximation ratio to the Steiner-tree subproblem. Simulation results demonstrate that universal swarming improves the performance of resource-poor sessions with negligible impact to resource-rich sessions. The proposed approach and algorithm are expected to be useful for infrastructure-based content distribution networks with long-lasting sessions and relatively stable network environment.
Column generation, Multi-tree multicast, Optimization, Subgradient algorithm, Tree packing, Universal swarming
KSP 제안 키워드
Approximation ratio, Content Distribution Network, Distribution network(DN), Long-lasting, Multi-tree, Multicast tree, NP-hard, Optimal Solution, Optimal algorithms, Optimal resource allocation, Resource-poor