The routing continuum from shortest-path to all-path: A unifying theory

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 31st International Conference on Distributed Computing Systems, ICDCS 2011
Pages847-856
Number of pages10
DOIs
StatePublished - 2011
Event31st International Conference on Distributed Computing Systems, ICDCS 2011 - Minneapolis, MN, United States
Duration: Jun 20 2011Jul 24 2011

Publication series

NameProceedings - International Conference on Distributed Computing Systems

Other

Other31st International Conference on Distributed Computing Systems, ICDCS 2011
CountryUnited States
CityMinneapolis, MN
Period6/20/117/24/11

Fingerprint Dive into the research topics of 'The routing continuum from shortest-path to all-path: A unifying theory'. Together they form a unique fingerprint.

Cite this