Tackling group-to-tree matching in large scale group communications |
| |
| Affiliation: | 1. Computer Science Department, University of California, Los Angeles, United States;2. Computer Science and Engineering Department, University of Connecticut, Storrs, United States;1. COMSATS Institute of Information Technology, Islamabad, Pakistan;2. College of CIS, King Saud University, Almuzahmiah, Saudi Arabia;3. Department of ECE, University of Idaho, Moscow, USA;1. Faculty of Information Technology, Monash University, Australia;2. Faculty of Science and Technology, Federation University, Australia;1. School of Information Science and Engineering, Central South University, Changsha, 410083, China;2. School of Electronics and Information Engineering, Hunan University of Science and Engineering, Yongzhou, 425199, China;1. University Children''s Hospital (UKBB), University of Basel, Basel, Switzerland;2. Pediatric Respiratory Medicine, Inselspital and University of Bern, Bern, Switzerland;3. Institute of Social and Preventive Medicine (ISPM), University of Bern, Bern, Switzerland;4. Swiss Tropical and Public Health Institute, University of Basel, Basel, Switzerland;1. School of Engineering and IT, Faculty of Science, Federation University, Australia;2. Faculty of Information Technology, Monash University, Australia |
| |
| Abstract: | As a mechanism to efficiently support group communications, multicasting, faces a serious state scalability problem when there are large numbers of groups in the network. Recently, a novel solution called Aggregated Multicast has been proposed, in which multiple groups can share one delivery tree. A key problem in Aggregated Multicast is group-to-tree matching (i.e., assigning groups to proper trees). In this paper, we formally define this problem, and formulate two versions of the problem: static and dynamic. We analyze the static version and prove that it is NP-complete. To tackle this hard problem, we propose three algorithms: one optimal (using Linear Integer Programming, or ILP), one near-optimal (using Greedy method), and one Pseudo-Dynamic algorithm. For the dynamic version, we present a generic dynamic on-line algorithm. Simulation study has been conducted to evaluate the performance of the algorithms. Our results show that: (1) for the static problem, the Greedy algorithm is a feasible solution and its performance is very close to the optimal ILP solution, while the Pseudo-Dynamic algorithm is a good heuristic for many cases where Greedy does not work well; (2) for the dynamic problem, the generic dynamic on-line algorithm is a very practical solution with promising performance and reasonable computation requirement. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
