More Web Proxy on the site http://driver.im/

article

Multipath routing algorithms for congestion minimization

Authors:

Ariel OrdaAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 15, Issue 2

Pages 413 - 424

https://doi.org/10.1109/TNET.2007.892850

Published: 01 April 2007 Publication History

Abstract

Unlike traditional routing schemes that route all traffic along a single path, multipath routing strategies split the traffic among several paths in order to ease congestion. It has been widely recognized that multipath routing can be fundamentally more efficient than the traditional approach of routing along single paths. Yet, in contrast to the single-path routing approach, most studies in the context of multipath routing focused on heuristic methods. We demonstrate the significant advantage of optimal (or near optimal) solutions. Hence, we investigate multipath routing adopting a rigorous (theoretical) approach. We formalize problems that incorporate two major requirements of multipath routing. Then, we establish the intractability of these problems in terms of computational complexity. Finally, we establish efficient solutions with proven performance guarantees.

References

[1]

{1} R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithm, and Applications. Englewood Cliffs, NJ: Prentice-Hall, 1993.

[2]

{2} D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, and J. McManus, "Requirements for traffic engineering over MPLS," IETF RFC 2702, Sep. 1999.

[3]

{3} B. Awerbuch, "Reducing complexities in the distributed max-flow and breadth-first-search algorithms by means of network synchronization," Network, vol. 15, pp. 425-437, 1985.

[4]

{4} R. Banner and A. Orda, "Multipath routing algorithms for congestion minimization," Dept. Electr. Eng., Technion, Haifa, Israel, CCIT Rep. 429, (2005). {Online}. Available: http://www.ee.technion.ac.il/people/ ron/Congestion.pdf

[5]

{5} R. Banner and A. Orda, "The power of tuning: A novel approach for the efficient design of survivable networks," in Proc. IEEE ICNP, 2004, pp. 2-11.

[6]

{6} D. Bertsekas and R. Gallager, Data Networks. Englewood Cliffs, NJ: Prentice-Hall, 1992.

[7]

{7} A. Borodin and R. El Yaniv, Online Computation and Competitive Analysis. Cambridge, U.K.: Cambridge Univ. Press, 1998.

[8]

{8} I. Cidon, R. Rom, and Y. Shavitt, "Analysis of multi-path routing," IEEE Trans. Netw., vol. 7, no. 6, pp. 885-896, Dec. 1999.

[9]

{9} S. Chen and K. Nahrstedt, "An overview of quality-of-service routing for the next generation high-speed networks: Problems and solutions," IEEE Trans. Netw., vol. 12, no. 6, pp. 64-79, Dec. 1998.

[10]

{10} T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms. Cambridge, MA: MIT Press, 2001.

[11]

{11} M. Faloutsos, P. Faloutsos, and C. Faloutsos, "On power-law relationships of the Internet topology," in Proc. ACM SIGCOMM, 1999, pp. 251-262.

[12]

{12} M. R. Garey and D. S. Johnson, Computers and Intractability. San Francisco, CA: Freeman, 1979.

[13]

{13} A. V. Goldberg and R. E. Tarjan, "A new approach to the maximum flow problem," J. ACM, vol. 35, no. 4, pp. 921-940, 1988.

[14]

{14} H. Han, S. Shakkottai, C. V. Hollot, R. Srikant, and D. Towsley, "Multi-path TCP: A joint congestion control and routing scheme to exploit path diversity in the Internet," IEEE/ACM Trans. Netw., vol. 14, no. 6, pp. 1260-1271, Dec. 2006.

[15]

{15} C. Huitema, Routing in the Internet. Englewood Cliffs, NJ: Prentice-Hall, 1995.

[16]

{16} S. Iyer, S. Bhattacharyya, N. Taft, N. McKeoen, and C. Diot, "A measurement based study of load balancing in an IP backbone," Sprint ATL, Tech. Rep. TR02-ATL-051027, May 2002.

[17]

{17} Y. Jia, I. Nikolaidis, and P. Gburzynski, "Multiple path QoS routing," in Proc. ICC, 2001, pp. 2583-2587.

[18]

{18} N. Karmarkar, "A new polynomial-time algorithm for linear programming," Combinatorica, vol. 4, pp. 373-395, 1984.

[19]

{19} F. P. Kelly, A. K. Maulloo, and D. K. H. Tan, "Rate control in communication networks: Shadow prices, proportional fairness and stability," J. Oper. Res. Soc., vol. 49, pp. 237-252, 1998.

[20]

{20} F. P. Kelly and T. Voice, "Stability of end-to-end algorithms for joint routing and rate control," Comput. Commun. Rev., vol. 35, no. 2, pp. 5-12, 2005.

[21]

{21} J. Kleinberg, "Single-source unsplittable flow," in Proc. 37th IEEE FOCS, 1996, pp. 68-77.

[22]

{22} J. Moy, "OSPF Version 2," IETF RFC 2328, Apr. 1998.

[23]

{23} S. Nelakuditi and Z.-L. Zhang, "On selection of paths for multipath routing," in Proc. IWQoS, 2001, pp. 170-186.

[24]

{24} V. Paxson, "End-to-end routing behavior in the Internet," in Proc. ACM SIGCOMM, 1996, pp. 25-38.

[25]

{25} P. Papadimitratos and Z. J. Haas, "Secure routing for mobile Ad hoc networks," in Proc. CNDS, 2002, pp. 70-82.

[26]

{26} E. Rosen, A. Viswanathan, and R. Callon, "Multiprotocol label switching architecture," IETF RFC 3031, 2001.

[27]

{27} D. Thaler and C. Hopps, "Multipath issues in unicast and multicast next-hop selection," IETF RFC 2991, 2000.

[28]

{28} C. Villamizar, "OSPF optimised multipath (OSPF-OMP)," Internet Draft, 1998.

[29]

{29} Y. Wang and Z. Wang, "Explicit routing algorithms for Internet traffic engineering," in Proc. ICCN'99, 1999, pp. 582-588.

[30]

{30} B. M. Waxman, "Routing of multipoint connections," IEEE J. Sel. Areas Commun., vol. 6, no. 9, pp. 1617-1622, Dec. 1988.

[31]

{31} A. E. I. Widjaja, "Mate: MPLS adaptive traffic engineering," Internet Draft, Aug. 1998.

Cited By

Tao BXiao MZhao J(2023)Minimum-Weight Link-Disjoint Paths With a Bounded Number of Shared NodesIEEE Transactions on Network and Service Management10.1109/TNSM.2023.323783220:3(2598-2610)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1109/TNSM.2023.3237832
Komarnicki MPrzewozniczek MKwasnicka HWalkowiak K(2023)Incremental Recursive Ranking Grouping for Large-Scale Global OptimizationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.321696827:5(1498-1513)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1109/TEVC.2022.3216968
Segal RAvin CScalosub G(2022)Constrained In-network Computing with Low Congestion in Datacenter NetworksIEEE INFOCOM 2022 - IEEE Conference on Computer Communications10.1109/INFOCOM48880.2022.9796980(1639-1648)Online publication date: 2-May-2022
https://dl.acm.org/doi/10.1109/INFOCOM48880.2022.9796980
Show More Cited By

Index Terms

Multipath routing algorithms for congestion minimization

Recommendations

Multipath routing algorithms for congestion minimization
NETWORKING'05: Proceedings of the 4th IFIP-TC6 international conference on Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communication Systems

Unlike traditional routing schemes that route all traffic along a single path, multipath routing strategies split the traffic among several paths in order to ease congestion. It has been widely recognized that multipath routing can be fundamentally more ...
Congestion Control in High Speed Networks via Alternate Path Routing

This paper presents a congestion control scheme based on alternate path routing. In the scheme, if a node encounters congestion or loses its preferred neighbor on its primary path to a destination, it sends data packets to that destination over ...
Mitigating path diminution in disjoint multipath routing for mobile ad hoc networks

Design of a disjoint multipath routing protocol in an ad hoc environment is a challenging task. In this paper, we propose a protocol named Vertex Disjoint Multipath Routing (VDMR) to discover multiple node disjoint paths between a given pair of nodes. A ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 15, Issue 2

April 2007

232 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 April 2007

Published in TON Volume 15, Issue 2

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
1,411
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tao BXiao MZhao J(2023)Minimum-Weight Link-Disjoint Paths With a Bounded Number of Shared NodesIEEE Transactions on Network and Service Management10.1109/TNSM.2023.323783220:3(2598-2610)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1109/TNSM.2023.3237832
Komarnicki MPrzewozniczek MKwasnicka HWalkowiak K(2023)Incremental Recursive Ranking Grouping for Large-Scale Global OptimizationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.321696827:5(1498-1513)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1109/TEVC.2022.3216968
Segal RAvin CScalosub G(2022)Constrained In-network Computing with Low Congestion in Datacenter NetworksIEEE INFOCOM 2022 - IEEE Conference on Computer Communications10.1109/INFOCOM48880.2022.9796980(1639-1648)Online publication date: 2-May-2022
https://dl.acm.org/doi/10.1109/INFOCOM48880.2022.9796980
Pingale RShinde S. N. (496f9936-0f8f-4b2e-a10c-8b656de7a925 (2021)Adaptive-Sunflower-Based Grey Wolf Algorithm for Multipath Routing in IoT NetworksInternational Journal of Business Data Communications and Networking10.4018/IJBDCN.28669917:2(1-28)Online publication date: 16-Dec-2021
https://dl.acm.org/doi/10.4018/IJBDCN.286699
Nguyen TPham TBinh HHung NThang HDe Raedt LDeville YBui MLinh TSang DPhuong NOanh N(2016)Adaptive multipath routing for network functions virtualizationProceedings of the 7th Symposium on Information and Communication Technology10.1145/3011077.3011123(222-228)Online publication date: 8-Dec-2016
https://dl.acm.org/doi/10.1145/3011077.3011123
Xiong YGan JAn BMiao CBazzan A(2015)Optimal electric vehicle charging station placementProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832581.2832621(2662-2668)Online publication date: 25-Jul-2015
https://dl.acm.org/doi/10.5555/2832581.2832621
Wu WDu WRuan G(2015)Network congestion control methods and theoryInternational Journal of Grid and Utility Computing10.1504/IJGUC.2015.0706826:3/4(200-206)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1504/IJGUC.2015.070682
Singh SDas TJukan A(2015)A Survey on Internet Multipath Routing and ProvisioningIEEE Communications Surveys & Tutorials10.1109/COMST.2015.246022217:4(2157-2175)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1109/COMST.2015.2460222
Qadir JAli AYau KSathiaseelan ACrowcroft J(2015)Exploiting the Power of Multiplicity: A Holistic Survey of Network-Layer MultipathIEEE Communications Surveys & Tutorials10.1109/COMST.2015.245394117:4(2176-2213)Online publication date: 18-Nov-2015
https://dl.acm.org/doi/10.1109/COMST.2015.2453941
Jung EVishwanath VKettimuthu RKimpe DChen YRoth PYu W(2014)Distributed multipath routing algorithm for data center networksProceedings of the 2014 International Workshop on Data Intensive Scalable Computing Systems10.1109/DISCS.2014.14(49-56)Online publication date: 16-Nov-2014
https://dl.acm.org/doi/10.1109/DISCS.2014.14
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents