Publications at NRL

Search by Title


Search by Author


Conference Paper


A Study of Group-Tree Matching in Large Scale Group Communications


As a mechanism to support group communications, multi- casting faces a serious state scalability problem when there are large numbers of groups in the network: lots of resources (e.g., memory to maintain group state information) and con- trol overhead (e.g., multicast tree setup and maintenance) are required to manage the groups. Recently, an e±cient solution called aggregated multicast is proposed [8]. In this approach, groups are assigned to proper trees and mul- tiple groups can share one delivery tree. A key problem in aggregated multicast is group-tree matching (i.e., matching groups to trees). In this paper, we investigate this group- tree matching problem. We ¯rst formally de¯ne the prob- lem, and formulate two versions of the problem: static and dynamic. Since the static version is the fundamental part of the problem, in this paper, we focus our e®orts on this aspect. We analyze the static version problem and prove that it is NP-complete. To tackle this hard problem, we propose three algorithms: one optimal (using Integer Lin- ear Programming, or ILP), one near-optimal (using Greedy method), and one pseudo-dynamic algorithm. Simulation studies are conducted to compare these three algorithms. Our results show that Greedy algorithm is a feasible solu- tion and its performance is very close to the ILP optimal solution, while pseudo-dynamic algorithm is a good heuris- tic for many cases where Greedy does not work well. The study of group-tree matching in this paper not only provides solutions for the static version problem, but also paves the way for formally investigating the dynamic version problem.

Paper: PDF file of paper

Information & Date

International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS'05), Philadelphia, Pennsylvania, July. 2005


Jun-Hong Cui
Li Lao
Mario Gerla