Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-745bb68f8f-b95js Total loading time: 0 Render date: 2025-02-05T21:10:25.703Z Has data issue: false hasContentIssue false

12 - Multi-path BGP: motivations and solutions

from Part III - Protocols and practice

Published online by Cambridge University Press:  05 October 2012

By
Francisco Valera ,
Iljitsch van Beijnum ,
Alberto García-Martínez  and
Marcelo Bagnulo
Edited by
Byrav Ramamurthy ,
George N. Rouskas  and
Krishna Moorthy Sivalingam
Francisco Valera
Affiliation:
Universidad Carlos III de Madrid, Spain
Iljitsch van Beijnum
Affiliation:
IMDEA Networks, Spain
Alberto García-Martínez
Affiliation:
Universidad Carlos III de Madrid, Spain
Marcelo Bagnulo
Affiliation:
Universidad Carlos III de Madrid, Spain
Byrav Ramamurthy
Affiliation:
University of Nebraska, Lincoln
George N. Rouskas
Affiliation:
North Carolina State University
Krishna Moorthy Sivalingam
Affiliation:
Indian Institute of Technology, Madras
Get access

Summary

Although there are many reasons for the adoption of a multi-path routing paradigm in the Internet, nowadays the required multi-path support is far from universal. It is mostly limited to some domains that rely on IGP features to improve load distribution in their internal infrastructure or some multi-homed parties that base their load balance on traffic engineering. This chapter explains the motivations for a multi-path routing Internet scheme, commenting on the existing alternatives, and detailing two new proposals. Part of this work has been done within the framework of the Trilogy research and development project, whose main objectives are also commented on in the chapter.

Introduction

Multi-path routing techniques enable routers to be aware of the different possible paths towards a particular destination so that they can make use of them according to certain restrictions. Since several next hops for the same destination prefix will be installed in the forwarding table, all of them can be used at the same time. Although multi-path routing has a lot of interesting properties that will be reviewed in Section 12.3, it is important to remark that in the current Internet the required multi-path routing support is far from universal. It is mostly limited to some domains that deploy multi-path routing capabilities relying on Intra-domain Gateway Protocol (IGP) features to improve the load distribution in their internal infrastructure and normally only allowing the usage of multiple paths if they all have the same cost.

Type
Chapter
Information
Next-Generation Internet
Architectures and Protocols
 , pp. 238 - 256
Publisher: Cambridge University Press
Print publication year: 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

B., Albrightson, J. J., Garcia-Luna-Aceves, and J., Boyle. EIGRP – A fast routing protocol based on distance vectors. In Networld/Interop 94, Las Vegas. Proceedings, pages 136–147, 1994.Google Scholar
D., Andersen, H., Balakrishnan, F., Kaashoek, and R., Morris. Resilient overlay networks. In ACM SOSP Conference. Proceedings, 2001.Google Scholar
M., Bagnulo, L., Burness, P., Eardley, et al. Joint multi-path routing and accountable congestion control. In ICT Mobile Summit. Proceedings, 2009.Google Scholar
S. M., Bellovin. Security problems in the TCP/IP protocol suite. ACM SIGCOMM Computer Communication Review, 19(2):32–48, 1989.Google Scholar
T. W., Chim, K. L., Yeung, and K. S., Lui. Traffic distribution over equal-costmultipaths. Computer Networks, 49(4):465–475, 2005.Google Scholar
A. de la, Oliva, M., Bagnulo, A., García-Martínez, and I., Soto. Performance analysis of the reachability protocol for IPv6 multihoming. Lecture Notes in Computer Science, 4712:443–454, 2007.CrossRefGoogle Scholar
B., Fortz and M., Thorup. Internet traffic engineering by optimizing OSPF weights. In IEEE INFOCOM 2000. Proceedings, volume 2, pages 519–528, 2000.Google Scholar
L., Gao and J., Rexford. Stable Internet routing without global coordination. IEEE/ACM Transactions on Networking, 9(6):681–692, 2001.Google Scholar
T. G., Griffin and J. L., Sobrinho. Metarouting. ACM SIGCOMM Computer Communication Review, 35(4):1–12, 2005.Google Scholar
H., Han, S., Shakkottai, C. V., Hollot, R., Srikant, and D., Towsley. Overlay TCP for multi-path routing and congestion control. IEEE/ACM Transactions on Networking, 14(6):1260–1271, 2006.Google Scholar
C., Hopps. Analysis of an Equal-Cost Multi-Path Algorithm. RFC2992, 2000.
G., Huston. Potaroo.net. [Online]. Available: www.potaroo.net/, 2009.
H. T., Kaur, S., Kalyanaraman, A., Weiss, S., Kanwar, and A., Gandhi. BANANAS: An evolutionary framework for explicit and multipath routing in the Internet. ACM SIGCOMM Computer Communication Review, 33(4):277–288, 2003.Google Scholar
F., Kelly and T., Voice. Stability of end-to-end algorithms for joint routing and rate control. ACM SIGCOMM Computer Communication Review, 35(2):5–12, 2005.Google Scholar
F. P., Kelly. Loss networks. The Annals of Applied Probability, 1(3):319–378, 1991.Google Scholar
A., Khanna and J., Zinky. The revised ARPANET routing metric. ACM SIGCOMM Computer Communication Review, 19(4):45–56, 1989.Google Scholar
C. N., Laws. Resource pooling in queueing networks with dynamic routing. Advances in Applied Probability, 24(3):699–726, 1992.Google Scholar
X., Meng, B., Zhang, G., Huston, and S., Lu. IPv4 address allocation and the BGP routing table evolution. ACM SIGCOMM Computer Communication Review, 35(1):71–80, 2005.Google Scholar
T., Moncaster, B., Briscoe, and M., Menth. Baseline encoding and transport of pre-congestion information. IETF draft. draft-ietf-pcn-baseline-encoding-02, 2009.
R., Moskowitz, P., Nikander, P., Jokela, and T., Henderson. Host Identity Protocol. RFC5201, 2008.
M., Motiwala, N., Elmore, M., Feamster, and S., Vempala. Path splicing. In ACM INFOCOM. Proceedings, 2008.Google Scholar
J., Moy. OSPF Version 2. RFC2328, 1998.
P., Psenak, S., Mirtorabi, A., Roy, L., Nguyen, and P., Pillay-Esnault. Multitopology (MT) routing in OSPF. RFC4915, 2007.
Y., Rekhter, T., Li, and S., Hares. A Border Gateway Protocol 4 (BGP-4). RFC4271, 2006.
,Routeviews. University of Oregon Route Views Project. [Online] Available: http://routeviews.org/, 2009.
A., Sridharan, R., Guerin, and C., Diot. Achieving near-optimal traffic engineering solutions for current OSPF/IS-IS networks. IEEE/ACM Transactions on Networking, 13(2):234–247, 2005.Google Scholar
S., Vutukury and J. J., Garcia-Luna-Aceves. A simple approximation to minimum-delay routing. In ACM SIGCOMM. Proceedings, pages 227–238. ACM, 1999.Google Scholar
D., Wischik, M., Handley, and M., Bagnulo. The resource pooling principle. ACM SIGCOMM Computer Communication Review, 38(5):47–52, 2008.Google Scholar
W., Xu and J., Rexford. MIRO: Multi-path interdomain routing. In Proceedings of the 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, volume 36, pages 171–182. ACM, 2006.Google Scholar
D., Zhu, M., Gritter, and D. R., Cheriton. Feedback based routing. ACM SIGCOMM Computer Communication Review, 33(1):71–76, 2003.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×