상세정보
학술지
Content Distribution by Multiple Multicast Trees and Intersession Cooperation: Optimal Algorithms and Approximations
- 저자
- Xiaoying Zheng, 조충래, Ye Xia
- 발행일
- 201506
- 출처
- Computer Networks : The International Journal of Telecommunications Networking, v.83, pp.100-117
- ISSN
- 1389-1286
- 출판사
- Elsevier
- 협약과제
- 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.
- KSP 제안 키워드
- Approximation ratio, Content Distribution Network, Distribution network(DN), Long-lasting, Multicast tree, NP-hard, Optimal Solution, Optimal algorithms, Optimal resource allocation, Resource-poor, Steiner trees