rfc1774.txt

来自「RFC 的详细文档！」· 文本 代码 · 共 564 行 · 第 1/2 页


RFC 1774                BGP-4 Protocol Analysis               March 1995


Memory requirements

   To quantify the worst case memory requirements for BGP, denote the
   total number of networks in the Internet by N, the mean AS distance
   of the Internet by M (distance at the level of an autonomous system,
   expressed in terms of the number of autonomous systems), the total
   number of autonomous systems in the Internet by A, and the total
   number of BGP speakers that a system is peering with by K (note that
   K will usually be dominated by the total number of the BGP speakers
   within a single autonomous system). Then the worst case memory
   requirements (MR) can be expressed as

                    MR = O((N + M * A) * K)

   In the current NSFNET Backbone (N = 2110, A = 59, and M = 5) if each
   network is stored as 4 octets, and each autonomous system is stored
   as 2 octets then the overhead of storing the AS path information (in
   addition to the full complement of exterior routes) is less than 7
   percent of the total memory usage.

   It is interesting to point out, that prior to the introduction of BGP
   in the NSFNET Backbone, memory requirements on the NSFNET Backbone
   routers running EGP were on the order of O(N * K). Therefore, the
   extra overhead in memory incurred by the NSFNET routers after the
   introduction of BGP is less than 7 percent.

   Since a mean AS distance grows very slowly with the total number of
   networks (there are about 60 autonomous systems, well over 2,000
   networks known in the NSFNET backbone routers, and the mean AS
   distance of the current Internet is well below 5), for all practical
   purposes the worst case router memory requirements are on the order
   of the total number of networks in the Internet times the number of
   peers the local system is peering with. We expect that the total
   number of networks in the Internet will grow much faster than the
   average number of peers per router. Therefore, scaling with respect
   to the memory requirements is going to be heavily dominated by the
   factor that is linearly proportional to the total number of networks
   in the Internet.

   The following table illustrates typical memory requirements of a
   router running BGP. It is assumed that each network is encoded as 4
   bytes, each AS is encoded as 2 bytes, and each networks is reachable
   via some fraction of all of the peers (# BGP peers/per net).








Traina                                                          [Page 6]

RFC 1774                BGP-4 Protocol Analysis               March 1995


   # Networks  Mean AS Distance # AS's # BGP peers/per net Memory Req
   ----------  ---------------- ------ ------------------- ----------
   2,100       5                59     3                   27,000
   4,000       10               100    6                   108,000
   10,000      15               300    10                  490,000
   100,000     20               3,000  20                  1,040,000

   To put memory requirements of BGP in a proper perspective, let's try
   to put aside for a moment the issue of what information is used to
   construct the forwarding tables in a router, and just focus on the
   forwarding tables themselves. In this case one might ask about the
   limits on these tables.  For instance, given that right now the
   forwarding tables in the NSFNET Backbone routers carry well over
   20,000 entries, one might ask whether it would be possible to have a
   functional router with a table that will have 200,000 entries.
   Clearly the answer to this question is completely independent of BGP.
   On the other hand the answer to the original questions (that was
   asked with respect to BGP) is directly related to the latter
   question. Very interesting comments were given by Paul Tsuchiya in
   his review of BGP in March of 1990 (as part of the BGP review
   committee appointed by Bob Hinden).  In the review he said that, "BGP
   does not scale well.  This is not really the fault of BGP. It is the
   fault of the flat IP address space.  Given the flat IP address space,
   any routing protocol must carry network numbers in its updates." With
   the introduction of CIDR [4] and BGP-4,  we have attempted to reduce
   this limitation.  Unfortunately,  we cannot erase history nor can
   BGP-4 solve the problems inherent with inefficient assignment of
   future address blocks.

   To reiterate, BGP limits with respect to the memory requirements are
   directly related to the underlying Internet Protocol (IP), and
   specifically the addressing scheme employed by IP. BGP would provide
   much better scaling in environments with more flexible addressing
   schemes.  It should be pointed out that with only very minor
   additions BGP was extended to support hierarchies of autonomous
   system [8]. Such hierarchies, combined with an addressing scheme that
   would allow more flexible address aggregation capabilities, can be
   utilized by BGP-like protocols, thus providing practically unlimited
   scaling capabilities.

Applicability of BGP

   In this section we'll try to answer the question of what environment
   is BGP well suited, and for what is it not suitable?  Partially this
   question is answered in the Section 2 of [1], where the document
   states the following:





Traina                                                          [Page 7]

RFC 1774                BGP-4 Protocol Analysis               March 1995


      "To characterize the set of policy decisions that can be enforced
      using BGP, one must focus on the rule that an AS advertises to its
      neighbor ASs only those routes that it itself uses.  This rule
      reflects the "hop-by-hop" routing paradigm generally used
      throughout the current Internet.  Note that some policies cannot
      be supported by the "hop-by-hop" routing paradigm and thus require
      techniques such as source routing to enforce.  For example, BGP
      does not enable one AS to send traffic to a neighbor AS intending
      that the traffic take a different route from that taken by traffic
      originating in the neighbor AS.  On the other hand, BGP can
      support any policy conforming to the "hop-by-hop" routing
      paradigm.  Since the current Internet uses only the "hop-by-hop"
      routing paradigm and since BGP can support any policy that
      conforms to that paradigm, BGP is highly applicable as an inter-AS
      routing protocol for the current Internet."

   While BGP is well suitable for the current Internet, it is also
   almost a necessity for the current Internet as well.  Operational
   experience with EGP showed that it is highly inadequate for the
   current Internet.  Topological restrictions imposed by EGP are
   unjustifiable from the technical point of view, and unenforceable
   from the practical point of view.  Inability of EGP to efficiently
   handle information exchange between peers is a cause of severe
   routing instabilities in the operational Internet. Finally,
   information provided by BGP is well suitable for enforcing a variety
   of routing policies.

   Rather than trying to predict the future, and overload BGP with a
   variety of functions that may (or may not) be needed, the designers
   of BGP took a different approach. The protocol contains only the
   functionality that is essential, while at the same time provides
   flexible mechanisms within the protocol itself that allow to expand
   its functionality.  Since BGP was designed with flexibility and
   expandability in mind, we think it should be able to address new or
   evolving requirements with relative ease. The existence proof of this
   statement may be found in the way how new features (like repairing a
   partitioned autonomous system with BGP) are already introduced in the
   protocol.

   To summarize, BGP is well suitable as an inter-autonomous system
   routing protocol for the current Internet that is based on IP (RFC
   791) as the Internet Protocol and "hop-by-hop" routing paradigm. It
   is hard to speculate whether BGP will be suitable for other
   environments where internetting is done by other than IP protocols,
   or where the routing paradigm will be different.






Traina                                                          [Page 8]

RFC 1774                BGP-4 Protocol Analysis               March 1995


Security Considerations

   Security issues are not discussed in this memo.

Acknowledgments

   The BGP-4 protocol has been developed by the IDR/BGP Working Group of
   the Internet Engineering Task Force.  I would like to express thanks
   to Yakov Rekhter for providing RFC 1265.  This document is only a
   minor update to the original text. I'd also like to explicitly thank
   Yakov Rekhter and Tony Li for their review of this document as well
   as their constructive and valuable comments.

Editor's Address

   Paul Traina
   cisco Systems, Inc.
   170 W. Tasman Dr.
   San Jose, CA 95134

   EMail: [e-mail]






























Traina                                                          [Page 9]

RFC 1774                BGP-4 Protocol Analysis               March 1995


References

   [1] Rekhter, Y., and T., Li, "A Border Gateway Protocol 4 (BGP-4)",
       RFC 1771, T.J. Watson Research Center, IBM Corp., cisco Systems,
       March 1995.

   [2] Rekhter, Y., and P. Gross, Editors, "Application of the Border
       Gateway Protocol in the Internet", RFC 1772, T.J. Watson Research
       Center, IBM Corp., MCI, March 1995.

   [3] Willis, S., Burruss, J., and J. Chu, "Definitions of Managed
       Objects for the Fourth Version of the Border Gateway Protocol
       (BGP-4) using SMIv2", RFC 1657, Wellfleet Communications Inc.,
       IBM Corp., July 1994.

   [4] Fuller V., Li. T., Yu J., and K. Varadhan, "Classless Inter-
       Domain Routing (CIDR): an Address Assignment and Aggregation
       Strategy", RFC 1519, BARRNet, cisco, MERIT, OARnet, September
       1993.

   [6] Moy J., "Open Shortest Path First Routing Protocol (Version 2)",
       RFC 1257, Proteon, August 1991.

   [7] Varadhan, K., Hares S., and Y. Rekhter, "BGP4/IDRP for IP---OSPF
       Interaction", Work in Progress.

   [8] ISO/IEC 10747, Kunzinger, C., Editor, "Inter-Domain Routing
       Protocol", October 1993.























Traina                                                         [Page 10]