rfc2791.txt

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

   The keys to reducing routing complexity are systematic as well as
   consistent routing scheme and a routing policy that is simple but
   meets the requirement of administrative polices.

   Another factor contributing to the complexity of routing management
   is prefix-based route filtering. As is well known, prefix-based
   filtering is necessary in order to protect the integrity of the
   routing system. This becomes a challenge when the number of routes
   known to the Internet is as large as it is today.

5. Routing Protocol Scalability

   Today's commonly deployed routing protocols are IS-IS or OSPF for
   Interior routing (aka IGP) and BGP for exterior routing (aka EGP). In
   terms of scaling and other aspects, these protocols are already an
   improvement over the previous generation of protocols, such as RIP
   and EGP. However, scalability is still a major issue when a network
   is large, when a routing design is insensitive to scaling issues, or
   the protocol implementation is inefficient.

5.1. IS-IS and OSPF

   As described earlier in the document, IS-IS and OSPF are Link State
   routing protocols. The basic components of a link state routing
   protocol are i) generation and maintenance of a Link-State-DataBase
   (LSDB) that describes the routing topology of a given routing area;
   and ii) route calculation based on the topology information in the
   database. Each node in a routing area is responsible for describing
   its local routing topology in a Link State Advertisement or LSA (LSP
   in the case of IS-IS.) Each individually generated LSA will be
   distributed or flooded to all the routers in the area. Each router
   receives LSAs from all the other routers, forming a link-state-
   database that reflects the routing topology of the entire routing
   area.

   The main associated scaling issues are the complexity of the link
   state flooding and routing calculation, plus the size of the LSDB
   which contributes to the cost of routing calculation and router
   memory consumption.






Yu                           Informational                      [Page 6]

RFC 2791           Scalable Routing Design Principles          July 2000


   Flooding is the process by which a router distributes its self-
   originated LSA to the rest of the routers in the area in case of any
   link state change. A router will send the LSA via all its interfaces.
   When receiving an LSA update, a router validates the information and
   updates its local LSDB before sending it out via all its own
   interfaces, except the one from which it received the original LSA
   update. Given the nature of IS-IS or OSPF flooding, a full-mesh
   network with N routers would have O(N^2) of LSAs flooded in the
   network when a single link failure occurs. A single router outage
   would cause LSA in the order of O(N^3) to be flooded in the system.

   In the case of OSPF, the protocol will refresh or flood every 30
   minutes even under stable network conditions, which could increase
   the problem for an already highly loaded router.

   From the above discussion, one can easily observe that the more
   routers and adjacencies in a Link State IGP routing area, the more
   CPU burden there are for each router to bear. When a network is
   unstable, the load will be amplified.

   A link-state protocol typically uses Dijkstra's Shortest Path First
   (SPF) algorithm for route calculation. The Dijkstra algorithm scales
   to the order of O(N^2), where N is the number of nodes. The algorithm
   could be improved to the order of O(l*logN) where l is the number of
   links in the network and N is the number of destinations or routers
   [6].

   Consequently, link state routing protocols do not scale to a network
   topology with many routers and excessive adjacencies in an area. When
   the network topology is unstable, the computation, processing and
   bandwidth costs are magnified, which causes excessive consumption of
   router resources. When the instability prevents IS-IS or OSPF from
   maintaining adjacencies, a network routing meltdown occurs.

   Node adjacencies are discovered and maintained through the exchange
   of HELLO messages sent periodically from each node. When a node fails
   to receive HELLO messages from its neighbor within a certain period
   of time (40 seconds for OSPF and less for IS-IS), it considers the
   neighbor down. When heavy flooding, re-calculation and other
   activities happen that make router CPU a scarce resource, a router
   may not be able to allocate CPU time to send or process HELLO
   packets. Routers in the network then lose adjacency, which magnifies
   the instability. As a result, an isolated instability can escalate to
   a routing failure across the entire network.

   Link-state IGPs also do not scale well to carry a large number of
   routes such as the 70,000 routes known to the Internet today. Since
   external routes are included in the link-state-database and in LSA



Yu                           Informational                      [Page 7]

RFC 2791           Scalable Routing Design Principles          July 2000


   (LSP for IS-IS) updates, the link bandwidth and router memory
   consumption will be tremendous. Moreover, due to the large size of
   LSA updates, it would aggravate router resource consumption in the
   process of LSA flooding, especially under unstable network condition.

   To summarize, a scalable design should avoid inclusion of too many
   routers in an IGP routing area, a large external routes carried by
   IGP and, more important, excessive adjacencies in the area.

5.2. BGP

   BGP is an inter-domain routing protocol allowing the exchange of
   routing or reachability information between different Autonomous-
   System networks. Functionally, BGP is composed of External BGP(E-BGP)
   and Internal BGP(I-BGP). E-BGP is used for exchanging external routes
   while I-BGP is typically used for distributing externally learned
   routes within an AS.

   The general costs of BGP are as follows:

      o CPU consumption in BGP session establishment, route selection,
        routing information processing, and handling of routing updates

      o Router memory to install routes and multiple paths associated
        with the routes.

   The major scaling issue associated with BGP lie in the full mesh I-
   BGP connections. Since it does not scale for an IGP to carry
   externally learned prefixes, as mentioned in the previous section,
   I-BGP assumes this duty. In order to prevent routing loops, prefixes
   learned via I-BGP are prohibited from being advertised to another I-
   BGP speaker. As a result, a full mesh of I-BGP sessions among the
   routers within an AS is required. In an AS with N routers, each
   router will have to establish I-BGP sessions with N-1 routers, and
   the system complexity is in the order of O(N^2). Therefore, BGP
   scales poorly when the number of routers involved in I-BGP mesh is
   large.

   A large network normally learns all the routes known to the Internet,
   which is approximately 70,000. I-BGP will need to carry all these
   routes.

   The large number of I-BGP sessions and routes consumes tremendous
   resources from each router, especially during BGP session
   establishment and during periods of heavy route flapping.






Yu                           Informational                      [Page 8]

RFC 2791           Scalable Routing Design Principles          July 2000


   Frequent routing updates are another potential scaling problem in
   large networks. BGP uses incremental updates and sends out routing
   information about unreachable routes quickly for fast convergence.
   This is a great improvement from EGP, in which the whole routing
   table is updated at a fixed time interval. However, when a network is
   unstable the updates, especially those containing route withdrawals,
   are sent immediately, causing global BGP updates. As a result,
   network instability initiated anywhere in a network triggers updates
   all over the Internet. This effect is magnified when large amounts of
   routes are visible to the Internet, putting a heavy load on routers
   that participate in BGP.

   The introduction of a routing hierarchy in BGP, through I-BGP Route
   Reflectors [7] and BGP Confederations [8], for example, will help
   alleviate the scaling problem caused by the requirement of full mesh
   I-BGP establishment.

   Another potential solution is to avoid the requirement of full mesh
   pairwise I-BGP connections. This will change the way that BGP
   distributes routing information among the I-BGP peers. Mechanisms
   worth considering are using multicast to distribute information or
   adopting flooding mechanisms similar to those used in IS-IS or OSPF.
   Further investigation of the implication of using such mechanism for
   BGP route distribution is needed.

   Route dampening [9] is one way to reduce excessive updates triggered
   by route flapping. The trade-off between fast convergence and
   stability of the network should be considered, as discussed in
   section 6.3.

6. Scalable Routing Design Principles

   The routing design for a large-scale network should achieve the basic
   goals of accuracy, stability, redundancy and convergence as described
   in Section 2 and moreover should achieve it in a scalable fashion.

   How routing scales is influenced by protocol design decisions,
   protocol implementation decisions, and network design decisions. A
   network engineer has direct control over network design decisions and
   can have substantial influence over protocol design and
   implementation. The focus of this document is network design
   decisions.









Yu                           Informational                      [Page 9]

RFC 2791           Scalable Routing Design Principles          July 2000


   Following is a set of design principles for making a large network
   routing system more scalable:

      o Building hierarchy
      o Compartmentalization
      o Making proper trade-offs
      o Reducing route processing burdens
      o Defining scalable routing policies and implementation
      o Utilizing out-of-band routing assistance

6.1. Building Hierarchy

   As discussed in Section 5.1, OSPF and IS-IS scale poorly when a
   network has a large number of routers and in particular, a large
   quantity of adjacencies. This has unfortunately been proven by
   networks that deploy IP over ATM with full mesh adjacencies among the
   routers. The full mesh overlay design combined with the inefficient
   protocol implementation led to disastrous network outages. A lesson
   learned from this is to avoid full mesh overlay topology in a large
   network with a large, flat network routing structure.

   Building hierarchical routing structures in the network is the key to
   achieving routing scalability in a large network. As discussed
   earlier in this document, large networks are usually composed of many
   routers with a complex topology, which results in a large number of
   adjacencies. As also discussed earlier, currently available routing
   protocols scale poorly for handling a large number of routers in a
   routing domain or many adjacencies among the routers. Therefore, it
   is sensible to build a routing hierarchy to reduce the number of
   routers as well as the number of adjacencies in a routing domain.

   The current common practice is to build a two-tiered hierarchy in a
   network with a center component (or transit core network) to which a
   number of outskirt components (or access networks) attach. The
   transit core network covers the entire geographical area the network
   serves; each access network (aka regional network) covers one region.
   There are usually no direct link connections among the regional
   components. Traffic from one regional network to another traverses
   the transit core. Customer networks connect only to access or
   regional networks. There are a number of ways to build a routing
   hierarchy in the above described hierarchical network topology.

      1) Completely Separate Routing Domains

      This design treats the transit core network and each regional
      network as completely independent ASs with respect to routing, and
      each AS runs an independent IGP. Each regional network E-BGP with
      the transit core for exchanging routing knowledge. Full I-BGP



Yu                           Informational                     [Page 10]

RFC 2791           Scalable Routing Design Principles          July 2000


      connections need to be established only within each component
      network. With this design, the maximum number of routers in an IGP
      domain is the total number of routers in each component. As a
      result, the IGP processing load is reduced, and the number of
      routers in an I-BGP mesh in the network routing system is
      decreased dramatically.

      Another advantage of this design is that it compartmentalizes the
      routing system so that instability in one such component has less
      impact on the entire system. See the discussion in section 6.2.

      The main disadvantage of this scheme is that it inserts one extra
      AS in the routing path when routes are advertised to the Internet
      via BGP. This extra AS in the path may cause route selection
      difficulties for other providers.

      2) One Domain with IGP and BGP Hierarchy