Network Internet Draft Intended status: Information Track Expires: April 2012 October 24, 2011 Bibliography for the BGP Path Selection draft-hares-bgp-path-select-bib-00.txt Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html This Internet-Draft will expire on April 24, 2011. Copyright Notice Copyright (c) 2011 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of Hares Expires April 24, 2012 [Page 1] Internet-Draft BGP Path Selection Bibliography 2011-10-23 the Trust Legal Provisions and are provided without warranty as described in the BSD License. Abstract BGP-v4?s [RFC4271]path selection rule has been enforce since the 1990s. The Inter-Domain Working Group [IDR] will be considering additions to the path selection [add-path][add-path-guidelines][path- select-criteria] in 2011-2012. This document provides a bibliography of publications (research and public) regarding the bgp path selection. Conventions used in this document The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC-2119 0. Table of Contents 1. Introduction...................................................3 2. Terminology....................................................3 3. Review of Contributing Algorithms..............................4 4. Review of BGP algorithms.......................................6 4.1 BGP 2 and BGP-3 protocol specifications (IETF standards)......6 4.2 BGP-4 protocol specifications (IETF standards)................6 5. Requirements for IDR................Error! Bookmark not defined. 6. General Algorithm Papers............Error! Bookmark not defined. 7. Bibliography for Convergence/Stability........................11 8. BGP policy documents..........................................12 9. Conclusion and Recommendation.................................12 10. Manageability Considerations.................................12 11. Security Considerations......................................12 12. IANA Considerations..........................................12 13. Acknowledgments..............................................12 14. References...................................................12 Authors' Addresses...............................................13 Intellectual Property Statement..................................13 Disclaimer of Validity...........................................14 Hares Expires April 24, 2012 [Page 2] Internet-Draft BGP Path Selection Bibliography 2011-10-23 1. Introduction The IDR working group [IDR-WG] has several suggestion alternations to the BGP route selection process [add-paths][add-path-guidlines][best- path-select][aigp] BGP-4?s current path selection has been encoded in routers for 20+ years and incorporates bgp update reception, bgp policy, and convergence characteristics. Any BGP-4?s current path selection requires careful consideration of all the accumulated wisdom from academic research, industry research, deployment investigations, and algorithm examinations. This document seeks to provide a bibliography of this work that examines BGP basic functions, performance, and suggested solutions. Version-00 of this document is only a beginning of collecting these resources. 2. Terminology Atomized Routing ? modifying routing based on aggregate prefixes into equivalence classes (policy atoms) based on common AS path? from a topological perspectives [CAIDA-AR](section 3.8) BGP-v4 [RFC 4721] ? Border Gateway Protocol version 4. BGP Error reporting ? Errors reported within the BGP protocol. BGP Flap Damping ? Damping of BGP route oscillations BGP Monitoring messages ? Monitoring messages passed in the BGP protocol BGP Flap Damping ? Damping of BGP route oscillations L3VPN ?Layer 3 MPLS VPN [RF L2VPN ? Layer 2 MPLS VPN L2VPN BGP Auto-discovery ? BGP distribution of L2 VPN endpoints BGP Route Refresh ? Route Refresh Exchange in BGP to refresh the BGP routes received from Peer. Hares Expires April 24, 2012 [Page 3] Internet-Draft BGP Path Selection Bibliography 2011-10-23 Graceful Restart ? BGP Graceful Restart 3. Review of Contributing Algorithms This section describes research into contributing algorithms for BGP. 3.1 Distance Vector [MRR80] McQuillan, J.M., Richer, I., Rosen, E.C. (1980). The New Routing Algorithm for the ARPANET. IEEE Transactions on Communications, 28(5),711-719. May 1980. [BRE95] Breslau, L.M. (1995). Adaptive Source Routing of Real-Time Traffic in Integrated Services Networks. PhD Thesis, University of Southern California, Department of Computer Science, December 1995. Hop Count [Khanna88]Khanna, A. and Zinky, J. (1988). The Revised ARPANET Routing Metric. In Proceediongs of the ACM SIGCOMM ?88, 45-56. Palo Alto, CA, August 1988. [Rosen82] Rosen, E. (1982) Exterior Gateway Protocol (EGP), RFC827, [online: www.ietf.org/rfc/RFC827]. 3.2 Path Vector Algorithms [Jaggard-xxx] Jaggard, A. Jaggard (xxxx) ?Formal Models for Path- Vector Protocols,online: ?http://www.math.tulane.edu/~adj/Research/index.html#net 3.3 Link State (to be done) 3.4 Hybrid Link State (to be done) 3.5 Name versus Address [Chiappa-1999] Chiappa, N. (1999) Endpoints and Endpoint Names: A Proposed Enhancement to the Architecture. [Carpentar-2007] Carpenter, B. (2007) General Identifier-Locator Mapping Consideration, Work-in-Progress, draft-carpenter-idloc- Hares Expires April 24, 2012 [Page 4] Internet-Draft BGP Path Selection Bibliography 2011-10-23 map-cons-01.txt, online: [http:/tools/ietf.org/id/draft-carpenter- idloc-map-cons-01.txt] [Quoitin-2007] B. Quoitin, L. Iannone, C. de Launois and O. Bonaventure. Evaluating the Benefits of the Locator/Identifier Separation, Proceedings of MobiArch (ACM SIGCOMM Workshop), Kyoto, Japan, August 2007 3.6 TCP Congestion and traffic flow dynamics [Matthis97] Mathis, M., Semke, J., Mahdavi, J., (1997). The Macroscopic behavior of TCP Congestion Avoidance Algorithm. ACM Computer Communication, Review, 27(3): 67-82, July 1997. [PAXSON96] Paxson, V. (1996). End-to-End Routing Behavior in the Internet. In Proceedings of the ACM SIGCOMM ?96, 25-38, Stanford, Ca, August 1996. [PAXSON97a] Paxson, V. (1997a). End-to-end Internet Packet Dynamics. In Proceedings of the ACM SIGCOMM ?97, 139-152, Cannes, France, September 1997. [PAXSON97b] Paxson, V., (1997b). Measurements and Analysis of End-to- End Internet Dynamics. PhD Thesis, University of California at Berkley, Department of Electrical Engineering and Computer Science, April 1997. [Thompson97] Thompson, K., Miller, G.J., and Wilder, R. (1997). Wide- Area Internet Traffic Patterns and Characteristics. IEEE Network Managine, 11(6):10-23, November 1997. [Varadhan98] Varadhan, K., Estrin, D., Floyd, S. (1998). Impact of Network Dynamics on End-to-End Protocols: Case Studies in TCP and Reliable Multicast. Technical Report USC-CS-TR 98-672, University of Southern California, Information Sciences Institute, April 1998. 3.7 End-to-End effects of Internet Path Selection [Savage-1999] Savage, S., Collins, A., Hoffman, E., Snell, J., Anderson, T. (1999). The End-to-End Effects of Internet Path Selection [McManus] McManus, P.R. (1999). A Passive System for Server Selection within Mirrored Resource Environments Using AS Path Length Heuristics. Hares Expires April 24, 2012 [Page 5] Internet-Draft BGP Path Selection Bibliography 2011-10-23 (to be done) 3.8 Atomized Routing (to be done) 3.9 Compact Routing (to be done) 3.10 Fast Reroute (to be done) 3.11 Micro-Loop avoidance (to be done) 4. Review of BGP Papers This section considers the BGP specifications (sections 4.1-4.2), the extensions for IBGP scaling, the 4.1 BGP 2 and BGP-3 protocol specifications (IETF standards) Lougheed, K., and Rekhter, Y. (1989). A Border Gateway Protocol (BGP), RFC1105, online: www.ietf.org/RFC/RFC1105. [obsoleted by RFC1105]. Lougheed, K., and Rekhter, Y. (1990). A Border Gateway Protocol (BGP), RFC1163, online: www.ietf.org/RFC/RFC1163. [obsoleted by RFC1171]. Lougheed, K., and Rekhter, Y. (1991). A Border Gateway Protocol (BGP), RFC1267, online: www.ietf.org/RFC/RFC1267. [obsoleted by RFC1771] Haskins, D. (1993). Default Route Advertisement in BGP2 and BGP3 Versions of the Border Gateway Protocol, RFC1397, [online: www.ietf.org/RFC1397]. 4.2 BGP-4 protocol specifications (IETF standards) Rekhter, Y. and Li, T. (1994). A Border Gateway Protocol 4 (BGP-4), RFC1665, online: www.ietf.org/RFC/RFC1665. [obsoleted by RFC1771] Hares Expires April 24, 2012 [Page 6] Internet-Draft BGP Path Selection Bibliography 2011-10-23 Rekhter, Y. and Li, T. (1985). A Border Gateway Protocol 4 (BGP-4), RFC1771, [online: www.ietf.org/RFC/RFC1771. [obsoleted by RFC4771] Villiamizar, C., Chandra, R., Govindan, R. (1998) BGP Route Flap Damping. RFC2439, [online: www.ietf.org/RFC/RFC2439]. Rekhter, Y., Li, T., and Hares, S. (eds.) (2006). A Border Gateway Protocol 4 (BGP-4), RFC 4271. [online: www.ietf.org/RFC/RFC4771]. 4.3 BGP RFC Extensions for IBGP Scaling [RFC1965] Traina, P. (1996). Autonomous Systems Confederations for BGP. RFC1965, [online: www.ietf.org/RFC/RFC1965]. [RFC1966] Bates, T., Chandra, R., and Chen, E. (1996). BGP Route Reflections - An Alternative to Full Mesh IBGP, RFC1966, [online: www.ietf.org/rfc/rfc1966]. [RFC2796] Bates, T., Chandra, R., and Chen, E. (2000). BGP Route Reflections - An Alternative to Full Mesh IBGP, RFC2796, [online: www.ietf.org/rfc/rfc2796]. [RFC3065] Traina, P., McPherson, D., Scudder, J. (2001). Autonomous Confederations for BGP, RFC3065, [online: www.ietf.org/RFC/RFC3065]. [RFC4456] Bates, T., Chandra, R., and Chen, E. (2006). BGP Route Reflections - An Alternative to Full Mesh IBGP, RFC4456, [online: www.ietf.org/rfc/rfc4456]. [RFC5065] Traina, P., McPherson, D., Scudder, J. (2007). Autonomous Confederations for BGP, RFC5065, [online: www.ietf.org/RFC/RFC5065]. 4.4 BGP Protocol Analysis and Experiences with BGP 1990-1995 [Bolot-1993] Bolot, J-C, (1993). End-to-end Packet Delay and Loss Behavior in the Internet. In Proceedigns of ACM SIGCOMM ?94, 289-298, San Francisco, CA, Sept. 1993. [Chinoy 1994] Chinoy, B. (1994). Dynamics of Internet Routing Information. In Proceedigns of ACM SIGCOMM ?94, 45-52. San Francisco, CA, Sept. 1993. Hares Expires April 24, 2012 [Page 7] Internet-Draft BGP Path Selection Bibliography 2011-10-23 [Rekhter 1991a] Rekhter, Y., ed. (1991). BGP Protocol Analysis, RFC1265, [online: www.ietf.org/RFC1265] [Rekhter 1991b] Rekhter, Y., ed.(1991). Experience with BGP Protocol, RFC1266, [online: www.ietf.org/RFC1266] [Rekhter, 1991c] Rekhter, Y., eds (1991). Application of the Border Gateway Protocols, RFC1268, [online: www.ietf.org/RFC1268] [Varadhan, 1992] Varadhan, K. (1992). BGP OSPF Interactions, RFC1365, [online: www.ietf.org/RFC1365] [Varadhan, 1993] Varadhan, K. (1993). BGP OSPF Interactions, RFC1403, [online: www.ietf.org/RFC1403] [Varadhan, 1994] Varadhan, K., Hares, S., Rekhter, Y. (1994). BGP4/IDRP for IP --- OSPF interactions. RFC1745, [online: www.ietf.org/RFC1745] 1995-2000 [AGT-1998] Apostolopoulos, G., Guerin, R., and Tripathi, S.K.S (1998). Quality of Service Routing: A Performance Perspective. In Proceedings of ACM SIGCOMM ?98, pages 17-28, Vancouver, BC, September, 1998. [Breslau-1999] Breslau, L.M. (1995) Adaptive Source Routing of Real- Time Traffic in Integrated Service Networks. PhD thesis, University of Southern California, Department of Computer Science, December 1995. [BSSK-1997]Balakrishnan, H., Seshan, S., Stemm, M., and Katz, R.H. (1997). Analyzing Stability in Wide-Area Network Performance. In Proceedings of the 1997 ACM SIGMETRICS Conference, Seattle, WA, June 1997. [Dube-1999] Dube, R. (1999). A Comparison of scaling techniques for BGP. ACM Computer Communications Review 29, 3 (July 1999), 44-46. [DubeScudder-1998] Dube, R. and Scudder, J.G. (1998). Route Reflection Considered Harmful. Work-in-Progress, [online: http://tools.ietf.org/id/draft-dube-route-reflection-harmful- 00.txt]. [Francis-1999] Francis, P., Jamin, S., Paxon, V., Zhang, L., Gryniewicz, D., Jin, Y. (1999). An Architecture for a Global Hares Expires April 24, 2012 [Page 8] Internet-Draft BGP Path Selection Bibliography 2011-10-23 Internet Host Distance Estimation Service. In Proceedings of the IEEE INFOCOM ?99, New York, NY, March 1999. [Freedman-1998] Freedman, A. (1998). Optimal External Route Selection: Tips and Techniques for ISPs. Tutorial at North American Operators Group (NANOG), November 1998. [Labovitz97] Labovitz, C., Malan, G.R., Jahanian, F. (1997). In Proceedings of the ACM SIGCOMM ?97, 115-126, Cannes, France, September 1997. [Labovitz99] Labovitz, C., Malan, G.R., Jahanian, F., (1999). Origins of Internet Routing Instability. In Proceedings of the IEEE INFOCOM ?99, New York, NY, March 1999. 2000-2005 [Basu-2002] Basu, A., Ong, C.-H.L., RAsala, A., Shepherd, and Wilfong, G.(2002). Route Oscillations in IBGP with Route Reflections, Proceedings of ACM SIGCOMM, August 2002. [Ceasar-2003] Ceasar, M., Subramanian, L., and Katz, R.H. (2003). Toward localizing root causes of BGP Dynamics. Tech. Rep. CSD-03- 1202, UC Berkley, November, 2003. [Chandrashekar-2004] Chandrashekar, J., Duan, Z., Zhang, A.-l, and Krasky, J. (2004). Limiting Path Explaorationin Path Vector Protocols. Tech. rep. University of Minnesota, 2004. [Chang-2001] Chang, D-F, Govindan, R., Heidemann, J. (2001). An Empirical Router Response to Large Routing Tables, Technical Report No. 552, USC/Information Sciences Institute, CA, Nov. 2001. [online: http://www.isi.edu/~johnh/PAPERS/Chang02a.pdf] [Feamster-2003] Feamster, N. and Balakrishnan, H. (2003). Toward a logic for wide-area Internet routing. In ACM SIGCOMM Workshop on Future Directions in Network Architecture (August 2003). [Feamster-2004a] Feamster, N. and Balakrishnan, H. (2004). Verifying the correctness of wide-area Internet Routing. Tech. Rep. MIT-LCS- TR-948. Massachusetts Institute of Technology, May 2004. [Feamster-2004b] Feamster, N. Winick, J., and Rexford, J. (2004). A model of BGP routing for network engineering. In Proceedings of ACM SIGMETRICS (June 2004). Hares Expires April 24, 2012 [Page 9] Internet-Draft BGP Path Selection Bibliography 2011-10-23 [Feldman-2004] Feldmann, A., Mannel, O., Mao, Z.M., Berger, A., and Maggs, B. (2004). Locating Internet routing instabilities. In Proceedings of ACM SIGCOM (Portland, OR, September 2004). [Gao-2001a] Gao, L. (2001) On inferring autonomous systems relationships in the Internet, IEEE/ACM Transactions on Networking 9, 6 (December 2001). [Gao-2001b] Gao, L., Griffin, T.G., and Rexford, J. (2001), Inherently safe bckup routing with BGP. In Proc. IEEE INFOCOM (Anchorage, AK, April 2001). [Gao-2001c] Gao, L. and Rexford, J. (2001) Stable Internet routing without global coordination. IEEE/ACM Transaction Networking 9, 6 (December 2001), 681-692. Goodell, G., Aiello, W., Griffin, T., Ioannidis, J., McDaniel, P., and Rubin, A., (2003) Working around BGP: An incremental approach to improving security and accuracy of interdomain routing. In Proc. Networking and Distributed Systems, Internet Society (February 2003). [to be completed] 2006-2011 [to be completed] 3.5 Requirements for BGP Davies, E. and Doria, A. (2006), An Analysis of Inter-Domain Routing Requirements and History. RFC5773, [online: http://tools.ietf.org/pdf/rfc5773.pdf] Davies, E., Doria, A., and Kastenholz, F. (2006) A Set of Possible Requirements for a Future Routing Architecture. RFC5772. [online: http://tools.ietf.org/pdf/rfc4772.pdf] Feamster, N., Balakrishna, H., Rexford, J. (2005?) Feamster, N, Balakrishnan, H., Rexford, J., Shaikh, A., and Van Der Merwe, J. (2004). The case for separating routing from routers. In ACM SIGCOMM Workshop on Future Directions in Network Architecture (Portland, OR, August 2004). \ Hares Expires April 24, 2012 [Page 10] Internet-Draft BGP Path Selection Bibliography 2011-10-23 Li, T. (2011). Design Goals for Scalable Internet Routing. RFC6227, [online: www.ietf.org/rfc/RFC6227]. [Bonaventure-xxx] O. Bonaventure et al, Beyond Inter-domain Reachability?, [online: http://www.net.informatik.tu- muenchen.de/wired/position/bonaventure-wired.pdf] 4.6 Descriptions of BGP Routing protocols in implementations. [Cisco-1997] Halabi, B.(1997) Internet Routing, Cisco Press. 5. Impact of Reconfiguration on BGP 5.1 Problem of Network Configurations [to be done] 5.2 Route Refresh and OrfS [to be done] 5.3 Graceful Restart and ORFS [to be done] 6. Bibliography for Convergence/Stability 6.1 Benchmarking of BGP [to be completed] 6.2 Stability [Govindan-1999] Govindan,R., Alaettinoglu, Eddy, G., Kessens, D., Kumar, S., and Lee, W.S.. (1999) An Architecture for stable, analyzable internet routing. IEEE Network, 13(1):29-35, 1999. [Gao-2000], Gao, L., and Rexford, J. (2000). Stable Internet Routing without Global Coordination. Proc. Of ACM SIGMETRICS, June 2000. 6.3 Policy and Stability [to be done] Hares Expires April 24, 2012 [Page 11] Internet-Draft BGP Path Selection Bibliography 2011-10-23 7. BGP policy documents Alaettinoglu,A., Bates, T., Eric, E., Karenberg,D., Terpstra, M. and Villamizar, C. (1998) Routing Policy (RPSL). RFC 2280. [www.ietf.org/RFC2280] 8. Conclusion and Recommendation The literature on BGP points toward the complexity of many of these solutions, and the far ranging impact. The considerations of these new BGP algorithms 9. Manageability Considerations This document does not add additional manageability considerations. 10. Security Considerations This document as a document review has no security considerations. Perhaps because BGP algorithms have little security considerations. 11. IANA Considerations This document provides a bibliography of BGP documents and 12. Acknowledgments I want to acknowledge all the authors listed in the bibliography for their insight which has provided valuable inputs to the revision of Gated This document was prepared using 2-Word-v2.0.template.dot. 13. References [RFC4363] Rosen, E. and Rekhter, Y. ?BGP/MPLS IP Virtual Private Networks (VPNs)?, February 2006. [add-paths] Walton,D., Chen, E., Retana, A., Scudder, J. ?Advertisement of Multiple Paths in BGP?, draft-ietf-idr- add-patyhs-06.txt, September 15, 2011. Hares Expires April 24, 2012 [Page 12] Internet-Draft BGP Path Selection Bibliography 2011-10-23 [add-paths-guidelines] Uttarro, J., Van den Schrieck, V., Franciois, P., Fraggassi, R., Simpson, A., Mohaptra, P., ?Best Practices for Advertisement of Multiple Paths in BGP?, draft-ietf-idr-add-paths-guidelines-01.txt. [aigp] Mohapatra, P., Fernado, R., Rosen, E.C., Uttaro, J., ?Accumulated IGP Metric for BGP?, draft-ietf-idr-aigp- 06.txt. [dyn-caps] Chen, E. and Sangli, S. ?Dynamic Capability for BGP-4?, draft-ietf-idr-dynamic-cap-13.txt, June 2011. [frs-OPS] Freedman, D., Raszuk, R., Shakir, R. ?BGP OPERATIONAL Message?, draft-frs-bgp-opertoinal-message-00, June 2011. Authors' Addresses Susan Hares Huawei Technologies (USA) 2330 Central Expressway Santa Clara, CA 95050 Phone: +408-330-4581 Cell: +1-734-604-0332 Email shares@huawei.com Intellectual Property Statement The IETF Trust takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in any IETF Document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Copies of Intellectual Property disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr Hares Expires April 24, 2012 [Page 13] Internet-Draft BGP Path Selection Bibliography 2011-10-23 The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement any standard or specification contained in an IETF Document. Please address the information to the IETF at ietf-ipr@ietf.org. Disclaimer of Validity All IETF Documents and the information contained therein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION THEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Hares Expires April 24, 2012 [Page 14]