Journal article
Cost of not splitting in routing: characterization and estimation
IEEE/ACM Transactions on Networking (TON), Vol.19(6), pp.1849-1859
12/01/2011
DOI: 10.1109/TNET.2011.2150761
Abstract
This paper studies the performance difference of joint routing and congestion control when either single-path routes or multipath routes are used. Our performance metric is the total utility achieved by jointly optimizing transmission rates using congestion control and paths using source routing. In general, this performance difference is strictly positive and hard to determine--in fact an NP-hard problem. To better estimate this performance gap, we develop analytical bounds to this "cost of not splitting" in routing. We prove that the number of paths needed for optimal multipath routing differs from that of optimal single-path routing by no more than the number of links in the network. We provide a general bound on the performance loss, which is independent of the number of source-destination pairs when the latter is larger than the number of links in a network. We also propose a vertex projection method and combine it with a greedy branch-and-bound algorithm to provide progressively tighter bounds on the performance loss. Numerical examples are used to show the effectiveness of our approximation technique and estimation algorithms.
Details
- Title: Subtitle
- Cost of not splitting in routing: characterization and estimation
- Creators
- Meng WangChee TanWeiyu XuAo Tang
- Resource Type
- Journal article
- Publication Details
- IEEE/ACM Transactions on Networking (TON), Vol.19(6), pp.1849-1859
- Publisher
- IEEE Press
- DOI
- 10.1109/TNET.2011.2150761
- ISSN
- 1063-6692
- eISSN
- 1558-2566
- Language
- English
- Date published
- 12/01/2011
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984083818502771
Metrics
25 Record Views