TY - GEN
T1 - The routing continuum from shortest-path to all-path
T2 - 31st International Conference on Distributed Computing Systems, ICDCS 2011
AU - Li, Yanhua
AU - Zhang, Zhi Li
AU - Boley, Daniel
PY - 2011
Y1 - 2011
N2 - Routing is a critical operation in networks. In the context of data and sensor networks, routing strategies such as shortest-path, multi-path and potential-based ("all-path") routing have been developed. Based on the connection between routing and flow optimization in a network, in this paper we develop a unifying theoretical framework by considering flow optimization with mixed (weighted) L1/L2-norms. We obtain a surprising result: as we vary the trade-off parameter θ, the routing graphs induced by the optimal flow solutions span from shortest-path to multi-path to all-path routing - this entire sequence of routing graphs is referred to as the routing continuum. Our theory subsumes the earlier results showing the shortest path and allpath routing can be obtained from L1 and L2 flow optimization, respectively. We also develop an efficient iterative algorithm for computing the entire routing continuum. Several generalizations are also considered, with applications to traffic engineering and wireless sensor networks.
AB - Routing is a critical operation in networks. In the context of data and sensor networks, routing strategies such as shortest-path, multi-path and potential-based ("all-path") routing have been developed. Based on the connection between routing and flow optimization in a network, in this paper we develop a unifying theoretical framework by considering flow optimization with mixed (weighted) L1/L2-norms. We obtain a surprising result: as we vary the trade-off parameter θ, the routing graphs induced by the optimal flow solutions span from shortest-path to multi-path to all-path routing - this entire sequence of routing graphs is referred to as the routing continuum. Our theory subsumes the earlier results showing the shortest path and allpath routing can be obtained from L1 and L2 flow optimization, respectively. We also develop an efficient iterative algorithm for computing the entire routing continuum. Several generalizations are also considered, with applications to traffic engineering and wireless sensor networks.
UR - http://www.scopus.com/inward/record.url?scp=80051914608&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80051914608&partnerID=8YFLogxK
U2 - 10.1109/ICDCS.2011.57
DO - 10.1109/ICDCS.2011.57
M3 - Conference contribution
AN - SCOPUS:80051914608
SN - 9780769543642
T3 - Proceedings - International Conference on Distributed Computing Systems
SP - 847
EP - 856
BT - Proceedings - 31st International Conference on Distributed Computing Systems, ICDCS 2011
Y2 - 20 June 2011 through 24 July 2011
ER -