article

Impact of hot-potato routing changes in IP networks

Authors:

Renata Teixeira,

Timothy G. Griffin,

Jennifer RexfordAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 16, Issue 6

Pages 1295 - 1307

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

Published: 01 December 2008 Publication History

Abstract

Despite the architectural separation between intradomain and interdomain routing in the Internet, intradomain protocols do influence the path-selection process in the Border Gateway Protocol (BGP). When choosing between multiple equally-good BGP routes, a router selects the one with the closest egress point, based on the intradomain path cost. Under such hot-potato routing, an intradomain event can trigger BGP routing changes. To characterize the influence of hot-potato routing, we propose a technique for associating BGP routing changes with events visible in the intradomain protocol, and apply our algorithm to a tier-1 ISP backbone network. We show that (i) BGP updates can lag 60 seconds or more behind the intradomain event; (ii) the number of BGP path changes triggered by hot-potato routing has a nearly uniform distribution across destination prefixes; and (iii) the fraction of BGP messages triggered by intradomain changes varies significantly across time and router locations. We show that hot-potato routing changes lead to longer delays in forwarding-plane convergence, shifts in the flow of traffic to neighboring domains, extra externally-visible BGP update messages, and inaccuracies in Internet performance measurements.

References

[1]

Y. Rekhter, T. Li, and S. Hares, "A border gateway protocol 4 (BGP-4)," RFC 4271, Jan. 2006.

[2]

J. Moy, "OSPF version 2," RFC 2328, Apr. 1998.

[3]

R. Callon, "Use of OSI IS-IS for routing in TCP/IP and dual environments," RFC 1195, Dec. 1990.

[4]

D. Watson, C. Labovitz, and F. Jahanian, "Experiences with monitoring OSPF on a regional service provider network," in Proc. Int. Conf. Distributed Computing Systems, May 2003, pp. 204-213.

Digital Library

[5]

A. Shaikh, C. Isett, A. Greenberg, M. Roughan, and J. Gottlieb, "A case study of OSPF behavior in a large enterprise network," in Proc. Internet Measurement Workshop, Nov. 2002.

Digital Library

[6]

G. Iannaccone, C.-N. Chuah, R. Mortier, S. Bhattacharyya, and C. Diot, "Analysis of link failures in an IP backbone," in Proc. Internet Measurement Workshop, Nov. 2002.

Digital Library

[7]

C. Labovitz, A. Ahuja, and F. Jahanian, "Experimental study of internet stability and wide-area network failures," in Proc. Int. Symp. Fault-Tolerant Computing, Jun. 1999.

Digital Library

[8]

J. Rexford, J. Wang, Z. Xiao, and Y. Zhang, "BGP routing stability of popular destinations," in Proc. Internet Measurement Workshop, Nov. 2002.

Digital Library

[9]

S. Agarwal, C.-N. Chuah, S. Bhattacharyya, and C. Diot, "Impact of BGP dynamics on intra-domain traffic," in Proc. ACM SIGMETRICS, Jun. 2004.

Digital Library

[10]

C. Labovitz, R. Malan, and F. Jahanian, "Internet routing instability," IEEE/ACM Trans. Networking, vol. 6, pp. 515-558, Oct. 1998.

Digital Library

[11]

J. Scudder, "BGP Monitoring Protocol," Expired Internet Draft, draft-scudder-bmp00.txt, 2005.

[12]

C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian, "Delayed internet routing convergence," IEEE/ACM Trans. Networking, vol. 9, no. 3, pp. 293-306, Jun. 2001.

Digital Library

[13]

T. Griffin and G. Wilfong, "An analysis of the MED oscillation problem in BGP," in Proc. Int. Conf. Network Protocols, 2002.

Digital Library

[14]

S. Halabi and D. McPherson, Internet Routing Architectures, 2nd ed. Indianapolis, IN: Cisco Press, 2001.

Digital Library

[15]

A. Shaikh and A. Greenberg, "OSPF monitoring: Architecture, design and deployment experience," in Proc. USENIX Symp. Networked Systems Design and Implementation, Mar. 2004.

Digital Library

[16]

R. Teixeira, A. Shaikh, T. Griffin, and J. Rexford, "Dynamics of hot-potato routing in IP networks," in Proc. ACM SIGMETRICS, Jun. 2004.

Digital Library

[17]

Configure Router Calculation Timers. Cisco {Online}. Available: http://www.cisco.com/univercd/cc/td/doc/product/software/ios120/12cgcr/np1_c/1cprt1/1cospf.html#xtocid2712621

[18]

Understanding BGP Processes on Cisco. Cisco {Online}. Available: http://www.cisco.com/warp/public/459/highcpu-bgp.html#topic1

[19]

C. Rossenhovel, "40-Gig Router Test Results," Light Reading, Nov. 2004 {Online}. Available: http://www.lightreading.com/document.asp?site=testing&doc_id=63606&page%_number=6

[20]

R. Teixeira, T. Griffin, A. Shaikh, and G. Voelker, "Network sensitivity to hot-potato disruptions," in ACM SIGCOMM, Portland, OR, Sep. 2004.

Digital Library

[21]

B. Quoitin and S. Uhlig, "Modeling the routing of an autonomous system with C-BGP," IEEE Network Mag., vol. 19, Nov. 2005.

Digital Library

[22]

G. Iannaccone, C.-N. Chuah, S. Bhattacharyya, and C. Diot, "Feasibility of IP restoration in a tier-1 backbone," IEEE Network Mag., Mar. 2004.

Digital Library

[23]

R. Teixeira and J. Rexford, "Managing routing disruptions in internet service provider networks," IEEE Commun. Mag., Mar. 2006.

Digital Library

[24]

Sampled Netflow. Cisco {Online}. Available: http://www.cisco.com/ univercd/cc/td/doc/product/software/ios120/120newft/120limit/120s/ 120s11/12s_sanf.htm

[25]

R. Teixeira, N. Duffield, J. Rexford, and M. Roughan, "Traffic matrix reloaded: Impact of routing changes," in Proc. Passive and Active Measurement Workshop, Boston, MA, Mar. 2005, Lecture Notes in Computer Science, vol. 3431, pp. 251-264.

Digital Library

[26]

U. Hengartner, S. B. Moon, R. Mortier, and C. Diot, "Detection and analysis of routing loops in packet traces," in Proc. Internet Measurement Workshop, Nov. 2002.

Digital Library

[27]

C. Alaettinoglu, V. Jacobson, and H. Yu, "Toward milli-second IGP convergence," Expired Internet Draft, draft-alaettinoglu-isis-convergence-00.txt, 2000.

[28]

P. Francois, C. Filsfils, J. Evans, and O. Bonaventure, "Achieving sub-second IGP convergence in large IP networks," ACM SIGCOMM Comput. Commun. Rev., vol. 35, Jul. 2005.

Digital Library

[29]

Route Views Project. {Online}. Available: http://www.routeviews.org

[30]

RIPE NCC RIS. {Online}. Available: http://www.ripe.net/ripencc/pub-services/np/ris-index.html

[31]

M. Caesar, L. Subramanian, and R. H. Katz, "Towards localizing root causes of BGP dynamics," UC, Berkeley, Tech. Rep. CSD-03-1292, 2003.

[32]

A. Feldmann, O. Maennel, Z. M. Mao, A. Berger, and B. Maggs, "Locating internet routing instabilities," in Proc. ACM SIGCOMM, Sep. 2004.

Digital Library

[33]

R. Teixeira and J. Rexford, "A measurement framework for pin-pointing routing changes," in Proc. ACM SIGCOMM Network Troubleshooting Workshop, Sep. 2004.

Digital Library

[34]

J. Wu, Z. M. Mao, J. Rexford, and J. Wang, "Finding a needle in a haystack: Pinpointing significant BGP routing changes in an IP network," in Proc. USENIX Symp. Networked Systems Design and Implementation , May 2005.

Digital Library

[35]

S. Agarwal, A. Nucci, and S. Bhattacharyya, "Measuring the shared fate of IGP engineering and interdomain traffic," in Proc. Int. Conf. Network Protocols, Nov. 2005.

Digital Library

[36]

R. Teixeira, T. Griffin, M. Resende, and J. Rexford, "TIE breaking: Tunable interdomain egress selection," IEEE/ACM Trans. Networking, vol. 15, Aug. 2007.

Digital Library

Cited By

Gong FRaghunathan DGupta AApostolaki MSekar VYu MSeneviratne AVeitch D(2024)Zoom2Net: Constrained Network Telemetry ImputationProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672225(764-777)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672225
Luttringer JBramas QPelsser CMérindol P(2021)A Fast-Convergence Routing of the Hot-PotatoIEEE INFOCOM 2021 - IEEE Conference on Computer Communications10.1109/INFOCOM42981.2021.9488880(1-10)Online publication date: 10-May-2021
https://dl.acm.org/doi/10.1109/INFOCOM42981.2021.9488880
Steinberger JKuhnert BDietz CBall LSperotto ABaier HPras ADreo G(2018)DDoS defense using MTD and SDNNOMS 2018 - 2018 IEEE/IFIP Network Operations and Management Symposium10.1109/NOMS.2018.8406221(1-9)Online publication date: 23-Apr-2018
https://dl.acm.org/doi/10.1109/NOMS.2018.8406221
Show More Cited By

Index Terms

Impact of hot-potato routing changes in IP networks

Recommendations

Dynamics of hot-potato routing in IP networks
SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systems

Despite the architectural separation between intradomain and interdomain routing in the Internet, intradomain protocols do influence the path-selection process in the Border Gateway Protocol (BGP). When choosing between multiple equally-good BGP routes, ...
Dynamics of hot-potato routing in IP networks

Despite the architectural separation between intradomain and interdomain routing in the Internet, intradomain protocols do influence the path-selection process in the Border Gateway Protocol (BGP). When choosing between multiple equally-good BGP routes, ...
Õ(Congestion + Dilation) Hot-Potato Routing on Leveled Networks

We study packet routing problems, in which we are given a set of N packets which will be sent on preselected paths with congestion C and dilation D. For store-and-forward routing, in which nodes have buffers for packets in transit, there are routing ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 16, Issue 6

December 2008

248 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 December 2008

Revised: 25 July 2006

Received: 31 December 2005

Published in TON Volume 16, Issue 6

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
268
Total Downloads

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

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gong FRaghunathan DGupta AApostolaki MSekar VYu MSeneviratne AVeitch D(2024)Zoom2Net: Constrained Network Telemetry ImputationProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672225(764-777)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672225
Luttringer JBramas QPelsser CMérindol P(2021)A Fast-Convergence Routing of the Hot-PotatoIEEE INFOCOM 2021 - IEEE Conference on Computer Communications10.1109/INFOCOM42981.2021.9488880(1-10)Online publication date: 10-May-2021
https://dl.acm.org/doi/10.1109/INFOCOM42981.2021.9488880
Steinberger JKuhnert BDietz CBall LSperotto ABaier HPras ADreo G(2018)DDoS defense using MTD and SDNNOMS 2018 - 2018 IEEE/IFIP Network Operations and Management Symposium10.1109/NOMS.2018.8406221(1-9)Online publication date: 23-Apr-2018
https://dl.acm.org/doi/10.1109/NOMS.2018.8406221
Secci SRougier JPattavina APatrone FMaier G(2018)Multi-exit discriminator game for BGP routing coordinationTelecommunications Systems10.1007/s11235-010-9335-x48:1-2(77-92)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1007/s11235-010-9335-x
Secci SRougier JPattavina APatrone FMaier G(2011)Peering equilibrium multipath routingIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2010.206253519:2(419-432)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1109/TNET.2010.2062535
Keller ERexford JVan Der Merwe J(2010)Seamless BGP migration with router graftingProceedings of the 7th USENIX conference on Networked systems design and implementation10.5555/1855711.1855727(16-16)Online publication date: 28-Apr-2010
https://dl.acm.org/doi/10.5555/1855711.1855727
Secci SRougier JPattavina APatrone FMaier G(2009)PEMPProceedings of the 28th IEEE conference on Global telecommunications10.5555/1811380.1811429(291-297)Online publication date: 30-Nov-2009
https://dl.acm.org/doi/10.5555/1811380.1811429
Secci SRougier JPattavina APatrone FMaier G(2009)ClubMEDProceedings of the 5th Euro-NGI conference on Next Generation Internet networks10.5555/1671421.1671448(196-203)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.5555/1671421.1671448

View Options

Get Access

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