article

BGP route prediction within ISPs

Authors:

Jeremy McMahon,

Matthew Roughan,

Nigel BeanAuthors Info & Claims

Computer Communications, Volume 33, Issue 10

Pages 1180 - 1190

https://doi.org/10.1016/j.comcom.2010.01.011

Published: 01 June 2010 Publication History

Abstract

Internet Service Providers (ISPs) often collect routing data to troubleshoot, analyze and predict the behavior of their network. However, data collected from multiple interacting routing protocols is often incomplete and difficult to manually analyze. In this paper we present a systematic approach to combine the pieces of measured routing data to obtain a more complete picture of a network's routing state. Our technique is efficient, has no assumptions about router configuration and is accurate. We present a case-study of a large Tier-2 ISP, finding that for those routers with adequate measurement infrastructure, we consistently find the egress location for 99.9999% of (router,prefix) pairs. Further, for the 85% of routers without measurement infrastructure we predict their decisions. This technique has been successfully applied in a 'what-if' scenario and has future applications in the real-time analysis of routing decisions.

References

[1]

A. Feldmann, A. Greenberg, C. Lund, N. Reingold, J. Rexford, F. True, Deriving traffic demands for operational ip networks: methodology and experience, IEEE/ACM Transactions on Networking, 2001.

Digital Library

[2]

Zhang, Y., Roughan, M., Lund, C. and Donoho, D., Estimating point-to-point and point-to-multipoint traffic matrices: an information-theoretic approach. IEEE/ACM Transactions on Networking. v13 i5. 947-960.

[3]

R. Teixeira, A. Shaikh, T.G. Griffin, G.M. Voelker, Network sensitivity to hot-potato disruptions, in: ACM SIGCOMM, 2004.

[4]

A. Flavel, M. Roughan, N. Bean, A. Shaikh, Where's Waldo? practical searches for stability in iBGP, in: IEEE International Conference on Network Protocols, 2008.

[5]

M. Buob, M. Meulle, S. Uhlig, checking for optimal egress points in iBGP routing, in: International Workshop on the Design of Reliable Communications Networks, 2007.

[6]

T. Bates, R. Chandra, E. Chen, BGP route reflection - an alternative to full mesh IBGP, RFC 2796, 2000.

[7]

A. Flavel, J. McMahon, A. Shaikh, M. Roughan, N. Bean, Humpty dumpty: putting iBGP back together again, in: IFIP Networking, 2009.

[8]

Feamster, N. and Rexford, J., Network-wide prediction of BGP routes. IEEE/ACM Transactions on Networking. v15 i2. 253-266.

[9]

T. Griffin, G. Wilfong, On the correctness of IBGP configuration, in: ACM SIGCOMM, 2002.

[10]

Y. Rekhter, T. Li, S. Hares, A Border Gateway Protocol 4, RFC 4271, January 2006.

[11]

N. Feamster, H. Balakrishnan, Correctness properties for Internet routing, in: Forty-third Allerton Conference on Communication, Control, and Computing, 2005.

[12]

M. Vutukuru, P. Valiant, S. Kopparty, H. Balakrishnan, How to construct a correct and scalable iBGP configuration, in: IEEE INFOCOM, Barcelona, Spain, 2006.

[13]

M. Buob, S. Uhlig, M. Meulle, Designing optimal iBGP route-reflection topologies, in: IFIP Networking, 2008.

[14]

O. Bonaventure, S. Uhlig, B. Quoitin, The Case for More Versatile BGP Route Reflectors, Work in Progress, draft-bonaventure-bgp-route-reflectors-00.txt (2004).

[15]

K. Poduri, C. Alaettinoglu, V. Jacobson, BST-BGP scalable transport, in: NANOG 27, 2003.

[16]

N. Feamster, H. Balakrishnan, J. Rexford, A. Shaikh, J. van der Merwe, The case for separating routing from routers, in: ACM SIGCOMM Workshop on Future Directions in Network Architecture, 2004.

Digital Library

[17]

M. Caesar, D. Caldwell, N. Feamster, J. Rexford, A. Shaikh, J. van der Merwe, Design and implementation of a routing control platform, in: Symposium on Networked Systems Design and Implementation, 2005.

[18]

Govindan, R., Alaettinog-lu, C., Varadhan, K. and Estrin, D., Route servers for inter-domain routing. Computer Networks and ISDN Systems. v30 i12. 1157-1174.

[19]

B. Quoitin, S. Uhlig, Modeling the routing of an autonomous system with CBGP, IEEE Network Magazine, Special Issue on Interdomain Routing.

[20]

A. Flavel, M. Roughan, Stable and flexible iBGP, in: ACM SIGCOMM, 2009.

Digital Library

[21]

<http://www.perl.org>, Perl Programming Language.

[22]

A. Shaikh, A. Greenberg, OSPF monitoring: architecture, design and deployment experience, in: Symposium on Networked Systems Design and Implementation, 2004.

[23]

T. Griffin, G. Wilfong, Analysis of the MED oscillation problem in BGP, in: IEEE International Conference on Network Protocols, 2002.

Digital Library

[24]

W. Mühlbauer, O. Maennel, S. Uhlig, A. Feldmann, M. Roughan, Building an AS-topology model that captures route diversity, in: ACM SIGCOMM, 2006.

[25]

A. Flavel, BGP, Not As Easy As 1-2-3, Ph.D. thesis, University of Adelaide, 2009.

Cited By

Steffen SGehr TTsankov PVanbever LVechev M(2020)Probabilistic Verification of Network ConfigurationsProceedings of the Annual conference of the ACM Special Interest Group on Data Communication on the applications, technologies, architectures, and protocols for computer communication10.1145/3387514.3405900(750-764)Online publication date: 30-Jul-2020
https://dl.acm.org/doi/10.1145/3387514.3405900
Cardona JVissicchio SLucente PFrancois P(2016)“I Can’t Get No Satisfaction”: Helping Autonomous Systems Identify Their Unsatisfied Interdomain InterestsIEEE Transactions on Network and Service Management10.1109/TNSM.2016.252500313:1(43-57)Online publication date: 9-Mar-2016
https://dl.acm.org/doi/10.1109/TNSM.2016.2525003
(2016)Building Nemo, a system to monitor IP routing and traffic paths in real timeComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.12.01197:C(1-30)Online publication date: 14-Mar-2016
https://dl.acm.org/doi/10.1016/j.comnet.2015.12.011
Show More Cited By

Index Terms

BGP route prediction within ISPs
1. Networks
  1. Network protocols
    1. Network layer protocols
      1. Routing protocols

Index terms have been assigned to the content through auto-classification.

Recommendations

Quantifying the BGP routes diversity inside a tier-1 network
NETWORKING'06: Proceedings of the 5th international IFIP-TC6 conference on Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communications Systems

Many large ISP networks today rely on route-reflection [1] to allow their iBGP to scale. Route-reflection was officially introduced to limit the number of iBGP sessions, compared to the $\frac{n\times(n-1)}{2}$ sessions required by an iBGP full-mesh. ...
Multiple route selector BGP (MRS-BGP)
ICWET '10: Proceedings of the International Conference and Workshop on Emerging Trends in Technology

To maximize the utilization of network resources it is necessary to have good approach for Routing Policy. The protocol currently used for Interdomain Routing is Border Gateway Protocol (BGP). BGP permits each router to use single best route for each ...
From destination prediction to route prediction

A prediction of a vehicle's route would be useful for giving the driver advance warnings and alerts about upcoming situations and opportunities. This paper presents a new algorithm for predicting a driver's route based on a probabilistic prediction of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Copyright © Elsevier B.V. © 2010.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 June 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Steffen SGehr TTsankov PVanbever LVechev M(2020)Probabilistic Verification of Network ConfigurationsProceedings of the Annual conference of the ACM Special Interest Group on Data Communication on the applications, technologies, architectures, and protocols for computer communication10.1145/3387514.3405900(750-764)Online publication date: 30-Jul-2020
https://dl.acm.org/doi/10.1145/3387514.3405900
Cardona JVissicchio SLucente PFrancois P(2016)“I Can’t Get No Satisfaction”: Helping Autonomous Systems Identify Their Unsatisfied Interdomain InterestsIEEE Transactions on Network and Service Management10.1109/TNSM.2016.252500313:1(43-57)Online publication date: 9-Mar-2016
https://dl.acm.org/doi/10.1109/TNSM.2016.2525003
(2016)Building Nemo, a system to monitor IP routing and traffic paths in real timeComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.12.01197:C(1-30)Online publication date: 14-Mar-2016
https://dl.acm.org/doi/10.1016/j.comnet.2015.12.011
Vissicchio SCittadini LDi Battista G(2015)On iBGP routing policiesIEEE/ACM Transactions on Networking10.1109/TNET.2013.229633023:1(227-240)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1109/TNET.2013.2296330

View Options

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 Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents