• KSII Transactions on Internet and Information Systems
    Monthly Online Journal (eISSN: 1976-7277)

Load-Balanced One-hop Overlay Multipath Routing with Path Diversity


Abstract

Overlay routing has emerged as a promising approach to improve reliability and efficiency of the Internet. For one-hop overlay source routing, when a given primary path suffers from the link failure or performance degradation, the source can reroute the traffic to the destination via a strategically placed relay node. However, the over-heavy traffic passing through the same relay node may cause frequent package loss and delay jitter, which can degrade the throughput and utilization of the network. To overcome this problem, we propose a Load-Balanced One-hop Overlay Multipath Routing algorithm (LB-OOMR), in which the traffic is first split at the source edge nodes and then transmitted along multiple one-hop overlay paths. In order to determine an optimal split ratio for the traffic, we formulate the problem as a linear programming (LP) formulation, whose goal is to minimize the worse-case network congestion ratio. Since it is difficult to solve this LP problem in practical time, a heuristic algorithm is introduced to select the relay nodes for constructing the disjoint one-hop overlay paths, which greatly reduces the computational complexity of the LP algorithm. Simulations based on a real ISP network and a synthetic Internet topology show that our proposed algorithm can reduce the network congestion ratio dramatically, and achieve high-quality overlay routing service.


Statistics

Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2015)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article

[IEEE Style]
Jianxin Liao, Shengwen Tian, Jingyu Wang, Tonghong Li and Qi Qi, "Load-Balanced One-hop Overlay Multipath Routing with Path Diversity," KSII Transactions on Internet and Information Systems, vol. 8, no. 2, pp. 443-461, 2014. DOI: 10.3837/tiis.2014.02.007

[ACM Style]
Liao, J., Tian, S., Wang, J., Li, T., and Qi, Q. 2014. Load-Balanced One-hop Overlay Multipath Routing with Path Diversity. KSII Transactions on Internet and Information Systems, 8, 2, (2014), 443-461. DOI: 10.3837/tiis.2014.02.007