The Routing Continuum from Shortest-Path to All-Path: A Unifying Theory
Citations Over TimeTop 10% of 2011 papers
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 all-path 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.
Related Papers
- → Oblivious Routing Scheme Using Load Balancing Over Shortest Paths(2008)38 cited
- → The Routing Continuum from Shortest-Path to All-Path: A Unifying Theory(2011)18 cited
- A Multi-path Hybrid Routing Algorithm in Network Routing(2015)
- Comparison of the Q-routing and shortest path routing algorithm(2004)
- → Analysis of Shortest Path Routing for Large Multi-Hop Wireless Networks(2018)2 cited