Name
Abstract | ||
|---|---|---|
We consider the multicast routing problem under operational communication constraints, such as in practical deployment scenarios, e. g., multi-domain ad hoc networks where two or more teams form a coalition, or in tactical networks where information flows need to adhere to specified policies regardless of the physical connectivity of nodes. First, we consider the problem of minimum-cost multicast routing on a multi-domain network by constructing a node-weighted Steiner tree (for mesh networks) and a Steiner connected dominating set (for wireless broadcast networks) that is subject to a non-additive cost constraint. This is because the multi-domain multicast cost is not just the sum of node costs of a Steiner tree, but it instead depends on the domains of the connected neighbors. We give an efficient algorithm that provides an O(log k) approximation guarantee, where k is the number of terminal (or sink) nodes in the network. Taking multidomain cost constraints into account can help reduce the cost of a multicast tree by up to 40%. We also consider a constraint imposed due to hierarchy compliance. We show that the overall multicast can be decomposed into several smaller multicasts, each of which might be efficiently solvable. We find that necessary hierarchical constraints could cause a significant increase in the total cost of multicast - up to 25%, as per our simulations based on a realistic deployment scenario. |
Year | Venue | Keywords |
|---|---|---|
2013 | 2013 11TH INTERNATIONAL SYMPOSIUM ON MODELING & OPTIMIZATION IN MOBILE, AD HOC & WIRELESS NETWORKS (WIOPT) | mesh networks,steiner trees,ad hoc networks,approximation algorithms,wireless networks,steiner tree,optimization |
Field | DocType | Citations |
Protocol Independent Multicast,Source-specific multicast,Multicast address,Steiner tree problem,Computer science,Xcast,Computer network,Pragmatic General Multicast,Distance Vector Multicast Routing Protocol,Multicast,Distributed computing | Conference | 2 |
PageRank | References | Authors |
0.40 | 4 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Prithwish Basu | 1 | 703 | 52.93 |
| Chi Kin Chau | 2 | 390 | 37.20 |
| Richard J. Gibbens | 3 | 393 | 29.96 |
| Saikat Guha | 4 | 1546 | 116.91 |
| Ryan E. Irwin | 5 | 12 | 2.39 |