From shortest-path to all-path: The routing continuum theory and its applications

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

As a crucial operation, routing plays an important role in various communication 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. Existing results in the literature show that the shortest path and all-path routing can be obtained from L1 and L2 flow optimization, respectively. Based on this 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. We also develop an efficient iterative algorithm for computing the entire routing continuum. Several generalizations are also considered, with applications to traffic engineering, wireless sensor networks, and network robustness analysis.

Original languageEnglish (US)
Article number6579599
Pages (from-to)1745-1755
Number of pages11
JournalIEEE Transactions on Parallel and Distributed Systems
Volume25
Issue number7
DOIs
StatePublished - Jul 2014

Keywords

  • Routing continuum
  • betweenness centrality
  • network flow

Fingerprint Dive into the research topics of 'From shortest-path to all-path: The routing continuum theory and its applications'. Together they form a unique fingerprint.

Cite this