کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
451525 694315 2007 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Tackling group-to-tree matching in large scale group communications
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر شبکه های کامپیوتری و ارتباطات
پیش نمایش صفحه اول مقاله
Tackling group-to-tree matching in large scale group communications
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computer Networks - Volume 51, Issue 11, 8 August 2007, Pages 3069–3089
نویسندگان
, , ,