TY - GEN
T1 - Multicasting under multi-domain and hierarchical constraints
AU - Basu, Prithwish
AU - Chau, Chi Kin
AU - Gibbens, Richard
AU - Guha, Saikat
AU - Irwin, Ryan
PY - 2013
Y1 - 2013
N2 - 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 multi-domain 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.
AB - 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 multi-domain 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.
UR - http://www.scopus.com/inward/record.url?scp=84883163707&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84883163707&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84883163707
SN - 9783901882548
T3 - 2013 11th International Symposium and Workshops on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, WiOpt 2013
SP - 524
EP - 531
BT - 2013 11th International Symposium and Workshops on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, WiOpt 2013
T2 - 2013 11th International Symposium and Workshops on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, WiOpt 2013
Y2 - 13 May 2013 through 17 May 2013
ER -