CCAMP Working Group D. Dovolsky (Movaz Networks) I. Bryskin (Movaz Networks) D. Awduche (Isocore) Internet Draft Expiration Date: May 2003 November 2002 Document: draft-dovolsky-ccamp-ospf-limited- flooding-00.txt Limited Flooding as a scalability improvement to OSPF draft-dovolsky-ccamp-ospf-limited-flooding-00.txt Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026 [1]. 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. Abstract This draft describes a limited flooding approach to address the problem of routing scalability in link state IGPs. The solution is based on decomposition of a routing area into ôzonesö and the restriction of the exchange of routing information between zones. This approach introduces an extra level in the isolation of knowledge within a routing domain. The advantage of this solution is that it considerably decreases the amount of information flooded in link state advertisements and reduces the size of the link-state database (and traffic engineering entries) on network elements utilizing link state protocols. The technique presented in this document has been particularized to OSPF in order to make the discussion practical and concrete. However, the underlying concepts are very general and similar modifications can be easily applied to other IGPs, such as ISIS. Table Of Contents Dovolsky, Bryskin, Awduche Expires May 2003 1 draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002 1. Summary for Sub-IP Area 1.1. Summary This document describes a generic mechanism to enhance the scalability of IGP routing protocols. More particularly, it specifies extensions to the OSPF routing protocol to make the protocol even more scalable in support of Generalized Multi-Protocol Label Switching (GMPLS). The method described is quite general and can be applied to other link state protocols, such as ISIS. 1.2. Where does it fit in the Picture of the Sub-IP Work This work fits squarely in either the CCAMP or OSPF box. 1.3. Why is it Targeted at this WG This draft is targeted at the CCAMP or the OSPF WG, because it specifies extensions to the OSPF routing protocols in support of GMPLS, because GMPLS is within the scope of the CCAMP WG, and because OSPF is within the scope of the OSPF WG. 1.4. Justification The WG should consider this document as it specifies the extensions to the OSPF routing protocols in support of GMPLS. 2. Overview This document proposes a method to enhance the scalability of link state interior gateway routing protocols (IGPs). The proposed solution is applicable to traditional link state routing protocols such as OSPF [1]. The proposed solution is even more pertinent in MPLS and GMPLS networks, where the IGP has been extended and equipped with traffic engineering and GMPLS extensions. The main idea behind the proposed approach is the reduction of a single routing area into multiple ôzonesö and the control of routing information between the zones. With this approach, it is no longer the case that network elements in the same routing area will necessarily have an identical copy of the area link state database. An important attribute of the zone concept is that it requires minimal modifications to the existing IGPs. Another important attribute is that it supports asymmetric exchange of routing information between network elements in different zones. The proposed approach also allows to: (1) decrease the size of the link state database on each node, (2) restrict the amount of routing information, (3) decrease the overhead associated with flooding, and (4) decrease the complexity of path selection. Dovolsky, Bryskin, Awduche Expires May 2003 2 draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002 To make the discussions in this document concrete and practical, we have used OSPF to illustrate the concepts. The solution is, however, quite general and applies to other link state routing protocols, such as ISIS, with very minor modifications. 2.1 Background: Scalability of Interior Gateway Routing Protocols Context Routing scalability is an important issue in operational networks. This issue becomes even more acute with the advent of GMPLS, which enables the use of IP routing protocols (after appropriate extensions) for different types of transport networks. The scalability of interior gateway routing protocols (IGPs) for IP networks and other types of transport networks is a particularly critical issue in operational networks, and is an important requirement for major service providers. Yet, many aspects of this issue have yet to be satisfactorily resolved. The most generic approach to addressing the routing scalability problem is the decomposition of a routing domain into multiple routing areas. This approach has become an integral part of existing IGP routing protocols such as OSPF [1]. Because the concept of routing areas by itself is not sufficient to address all nuances of the routing scalability problem, new improvements and workarounds have been proposed [4, 5, 6]. The intention of virtually all of the proposed solutions is to limit the amount of information advertised and to limit the amount of information maintained and managed by each routing engine on a network element. There are many dimensions that demand consideration in attempting to address the scalability of routing protocols. The main manifestations of lack of scalability in routing protocols is excessive consumption of CPU and memory resources on a network element, and undue transaction of state information between network elements to synchronize their routing databases. The transient behavior of the routing protocol is another aspect that could also have severe ramifications for scalability. In the worst case, the impact of lack of routing protocol scalability on the network itself can be devastating. In certain circumstances, lack of scalability can result in severe instability and a complete collapse of the network itself. Congestive collapse of the routing system can also occur because of the duplication of packet transmission inherent in the flooding mechanism [8]. In the best case, lack of routing scalability can result in inefficient network operation. Other manifestations of lack of routing scalability include: long convergence time, large path computation time, and slow forwarding time. Path computation time is a function of the number of routes, the size of the link-state database, the amount of traffic engineering parameters, and the types of user preference associated with a particular instance of the path computation process. All recently Dovolsky, Bryskin, Awduche Expires May 2003 3 draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002 proposed solutions attempt to improve the routing scalability by applying different algorithms to achieve one or more of the following objectives: increase the number of SPF calculations [5], avoid unnecessary flooding [6], restrict the database information exchange to only traffic-engineering link-state advertisements [4], etc. It is important to note that the most common operational network scenario for link state routing protocols is a single area, which encompasses the entire network. In many modern networks (especially those utilizing MPLS or GMPLS), the single routing area will implement the traffic engineering extensions (for example [2]). In such environments, the routing protocol disseminates the traditional link state information as well as traffic engineering data and other constraint information. Very large autonomous systems encompassing entire continents containing only one routing area are in operation today. It is also important to note that the issue of multi-area traffic engineering is an area in which the industry has not yet reached consensus on an effective solution. As an example, the classical approach suggested in [1] of breaking the network into multiple areas cannot be used to good effect. A typical service provider network is built of network elements with different capabilities, such as computational resources and memory. Some of them (for instance, routers installed on metro networks) may have more resources for keeping large databases and performing fast forwarding and path computation than the other (for instance, routers installed on access networks). The solution proposed in this draft is to break a single link state routing area into ôrouting zones.ö Routers and other network elements within the same zone maintain a synchronized topology state database among themselves. This means that network elements within the same zone receive full routing information (link-sate, traffic- engineering advertisements) from each other. 2.2 The Zone Concept The zone concept refers to a ôsoftö partitioning of a routing area into sub-domains, which allows to control the amount of routing information exchange between the sub-domains in the area. The zone concept also allows to decouple the advertisement of traditional LSAs defined in the original OSPF specification ([1]) from the advertisement of Traffic Engineering LSAs defined in the TE and GMPLS extensions. The zone concept allows grouping a collection of network elements into a ôzoneö which can be viewed as a single logical network entity. Each zone is associated with one or more zone border routers (ZBR). A ZBR exists at the boundary between a zone and the remainder of the routing area exterior to the zone. That is, a ZBR has routing IGP routing adjacencies with network elements within and outside the Dovolsky, Bryskin, Awduche Expires May 2003 4 draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002 zone. On the other hand, we say a network element is in the æinteriorÆ of a zone if it maintains IGP routing adjacencies with only network elements within its zone. We define three types of routing visibility to support the zone concept: (1) full visibility, (2) limited visibility, and (3) zero visibility. In the following discussion, when we say a ônetwork element,ö we mean a network element participating in the link state routing protocol. To fix these ideas, let us consider two zones, say zone æAÆ and zone æBÆ. We say that network elements within zone æAÆ have ôfull visibilityö of zone æBÆ if the network elements participating in the link state routing protocol in zone æAÆ receive routing information from all network elements in zone æBÆ. We say that network elements within zone æAÆ have ôlimited visibilityö of zone æBÆ if they receive zero routing information from network elements in the interior of zone æBÆ, with the exception of LSAs from one or more Zone Border Routers (ZBRs) at the boundary between the two zones. Lastly, we say that network elements within zone æAÆ have ôzero visibilityö of zone B if they receive zero routing information from any router that belongs to zone B. As a general concept, the notion of visibility defined above is not symmetric. Thus, it may be the case that zone æAÆ can have limited or zero visibility of zone æBÆ, while zone æBÆ may have full visibility of zone æAÆ. An immediate application of this concept in IP over circuit switch networks occurs within the context of the peer and augmented models. In such settings, some IP routers may have limited or full visibility into the circuit switch network, but it may not be beneficial for the circuit switch network elements to have full visibility into the IP network. Note, that routers within a given zone may have full visibility of some zones while having limited or zero visibility of other zones. For example, in an circuit switch network utilizing GMPLS, access network elements within an æaccess zoneÆ may have limited visibility of a metro-area network zone and zero visibility of a long-haul network zone, while metro-area network elements may have full visibility of some access network zones and limited visibility of a long-haul network zone. This draft allows decoupling the advertisement of æregular LSAsÆ from the advertisement of traffic engineering LSAsÆ. So that Dovolsky, Bryskin, Awduche Expires May 2003 5 draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002 different types of visibility can be applied with respect to advertisement of regular LSAs and traffic engineering LSAs. For example, routers within zone æAÆ may have full visibility of zone æBÆ with respect to regular LSA advertisements, but limited or zero visibility with respect to traffic engineering advertisements. The nature of routing visibility (full, limited or zero) between two zones can be asymmetrical, as noted earlier. This important characteristic of the zone concept is certainly worth emphasizing. For example, routers within zone æAÆ may have limited visibility of zone æBÆ, while routers with zone æBÆ may have full visibility of zone æAÆ. Routing visibility between two zones æAÆ and æBÆ is configured on ZBR(s) that belong(s) to both zones by limiting the flooding of the routing information of certain types (regular link-state advertisements, traffic-engineering advertisements, or both) through ZBR interfaces connecting zone æAÆ and zone æBÆ. ZBRs are responsible for advertising themselves as default routes for network elements within their zones, to support routing with zones that have limited or zero visibility with respect to the target zone. Transitive characteristics of zone visibility: If zone æAÆ is not adjacent to zone æBÆ (i.e. no ZBRs in common), then we say that network elements within zone æAÆ have full visibility of zone æBÆ if they have full visibility of zone æCÆ, which is adjacent to zone æAÆ and have full visibility of zone æBÆ. Otherwise, zone æAÆ has zero visibility of zone æBÆ. This is an expression of the transitive characteristics of zone visibility. [---] -------[ B ]---------- | [---] | | | [---]Limited Visibility [---] [ A ] Zone1 [ C ] [---] [---] | [---] | -------[ZBR]---------- -------[---]---------- | | [---] Full Visibility [---] [ D ] Zone [ E ] [---] [---] | | | [---] | -------[ZBR]---------- -------[---]---------- | | [---]Limited Visibility [---] [ E ] Zone2 [ F ] [---] [---] | | | [---] | Dovolsky, Bryskin, Awduche Expires May 2003 6 draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002 -------[ G ]---------- [---] In the example above routers A, B, C are within Limited Visibility Zone1. They contain full routing and traffic engineering information about each other. However, the only information they have about the rest of the network is the one that was generated by the upper ZBR. Likewise, routers E, F and G are within Limited Visibility Zone2. Routers D and E are within Full Visibility Zone. They contain full routing and traffic engineering information about all other routers in all zones. The approach described in this draft is advantageous because it allows controlling and decreasing the amount of routing information and associated processing overhead on network elements. In some types of network elements, it may also decrease convergence time and boost the routing/forwarding performance. The traffic engineering capabilities also become more scalable because constraint-based path selection, and tunnel setup and management can be distributed between access network elements and ZBR(s). This approach does not require changes to the routing protocol packet format. And it is enough to have only ZBR(s) routers supporting this feature. 3. Proposed solution A routing area may be divided into multiple zones by appropriately configuring the interfaces of zone boarder routers (ZBRs). Each pair of adjacent zones may be configured to have full or limited routing visibility with each other. Each pair of adjacent zones may have one or more ZBRs in common. Each ZBR in turn may have a number of interfaces configured with one or more zone identifiers (zone IDs) and flooding type. The flooding type indicates the type of routing information that may be flooded across the interface. It may have one of the following values: . link-state advertisements only; . traffic engineering advertisements only; . both The zone concept requires a slight modification to the OSPF Neighbor state machine and flooding procedures [1]. The OSPF Neighbor state machine defined in [1] should be amended as follows: ô10.3. The Neighbor state machine à State(s): ExStart Event: NegotiationDone New state: Exchange Action: The router must list the contents of its entire area link state database in the neighbor Database summary list. Dovolsky, Bryskin, Awduche Expires May 2003 7 draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002 If an interface associated with this neighbor is configured with limited flooding option and one or more zone IDs, each non self- originated link-state and/or traffic engineering database entry must be considered for inclusion into the Database Summary List according to the following rule: . non self-originated database entries must be included only if they are received from incoming interfaces that have non-zero overlapping list of zone IDs with the interface in question; . self-originated entries must be included regardless of the interface in question zone IDs; . both self-originated and non self-originated database entries that are disallowed to be distributed over the interface in question by its configured flooding type MUST NOT be included; ô13.3. Next step in the flooding procedure à Depending upon the LSA's LS type, the LSA can be flooded out only certain interfaces. These interfaces, defined by the following, are called the eligible interfaces: à When flooding an LSA, which has just been received, each outgoing interface must be considered on whether it is eligible outgoing candidate or not by comparing itÆs list of configured zone IDs with one configured for the interface the LSA has arrived on. The interface in question must be considered as eligible outgoing candidate if all following conditions are true: . it has a non-zero overlapping list of zone IDs with the incoming interface; . this LSA type is allowed to be flooded over the interface in question by its configured flooding type. In every place in the protocol implementation, where a locally originated Router LSA is needed to be flooded to a neighbor, the following procedure should be performed: For interfaces configured with one or more zone IDs and limited flooding option the Default Route stub network link (0.0.0.0/0) must be added to locally originated Router LSA. The Router LSA header link number, length and checksum should be updated appropriately. As a result of the described extensions routers within a particular zone will receive the routing information only from routers within the same zone and from other zones, which are fully visible from the router. They will also receive Router LSAs originated on ZBRs that belong to the zones, which the routers have limited visibility to (these LSAs contain Default Route stub network links identifying default routes that point to the ZBRs). They will receive no routing information from routers within zones with zero routing visibility. 4. Distributed Traffic Engineering across multiple zones Dovolsky, Bryskin, Awduche Expires May 2003 8 draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002 As a consequence of the flooding type definition (see 3.) the limited visibility of a router to a particular zone may apply to: a) link-state information; b) traffic engineering information; c) both. If the router is presented with a request to establish a traffic engineering tunnel that should go through one or more zones with the limited traffic engineering visibility, the path selection and tunnel setup is performed in the distributed way. Specifically, the originating router can define a path for the tunnel and signal the tunnel only up to one of ZBRs of a limited visibility zone towards the destination. Note, that routers learn about ZBRs via Default Route stub network links (0.0.0.0/0) found in received Router LSAs. When the setup message arrives on the ZBR, it repeats the process. Specifically, it defines the path and signal the tunnel either to the destination or to ZBR of next zone towards the destination depending on whether the destination is located in the zone fully visible from the computing ZBR or not. This process completes when the tunnel is established. If a router has full visibility towards the tunnel destination as far as link-state information is concerned, but has the limited traffic engineering visibility, it can use the full link-state visibility while deciding which ZBR to forward the tunnel setup message to in case he knows about more than one. 5. Topological Considerations Relating to Zones It may be necessary to impose some topological restrictions on the connectivity of zones within a routing area, especially for traditional hop by hop routing. Such restrictions are necessary to in order to avoid routing anomalies such as blackholes and routing loops. For getting end-to-end routing connectivity and avoiding black holes, some central (core) zone should be configured with full visibility. Hierarchical configured zones donÆt have to have direct connectivity to this core zone. 6. Example Network +--------------+ | Zone A | +--------------+ */LF-Z1 *\ LF-Z2 */ *\ */ *\ +---------+ +---------+ | Zone B | | Zone X | | | | | Dovolsky, Bryskin, Awduche Expires May 2003 9 draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002 +---------+ +---------+ LF-Z3 */ \ LF-Z4 LF-Z5 / *\ LF-Z6 */ \ / *\ +--------+ +--------+ +--------+ +--------+ | Zone C | | Zone D | | Zone Y | | Zone Z | | X | | | | | | | +--------+ +--------+ +--------+ +--------+ The above figure provides an example topology consisting of seven (7) zones. While not a requirement, a likely configuration of zones will be aligned with some topological or geographic regions. For example, zone A may map to a network backbone, zones B and X may map to local (interconnected) POPs, and zones C, D, Y and Z may map to separate access networks. In such a configuration, the zones could operate in the following fashion: . the zones C, D, Y and Z, have a limited visibility of directly attached zones, i.e., B and X respectively; . the zones B and X have full visibility of directly attached zones C, D, Y and Z, while having a limited visibility of zone A; . zone A has a full visibility of the directly connected zones B and X, and therefore also a full visibility of the subtending zones C, D Y and Z (and thus, becoming a backbone zone for the whole network) This example network can support both standard IP forwarding as well as MPLS Label Switch Paths (LSPs). To illustrate, consider an LSP terminating at endpoints at zone C (router C) and zone Y (router Y). Since, router C does not have information about router Y, it will route the LSP to ZBR of the directly attached zone (A, router LF- Z3). Since router LF-Z3 does not have information about router Y, it too will route the LSP to the ZBR of the directly zone (A, router LF-Z1). Lastly, since router LF-Z1 has full information about all routers on the network, it calculate a complete route for remaining portion of the LSP. 7. Compatibility Issues There should be no interoperability issues with routers and other network elements utilizing OSPF that do not implement this proposal. 8. Security Considerations This document does not raise new security issues beyond those that exist in OSPF with traffic engineering and GMPLS extensions. The method described in this document can actually enhance security because it can be used to block certain types of routing data from being advertised to a subset of network elements. 9. References Dovolsky, Bryskin, Awduche Expires May 200310 draft-dovolsky-ccamp-ospf-limited-flooding-01.txt November 2002 [1] Moy, J., "OSPF Version 2", RFC 2328, April 1998. [2] Katz, D., D. Yeung and K. Kompella, "Traffic Engineering Extensions to OSPF", work in progress. [3] Coltun, Rob, "The OSPF Opaque LSA Option", RFC 2370, FORE Systems, July 1998. [4] Venkata Naidu, "OSPF TE Only Option", draft-venkata-ospf-te- only-option-00.txt, April 2002. [5] A. S. Maunder, G. Choudhury, "Explicit Marking and Prioritized Treatment of Specific IGP Packets for Faster IGP Convergence and Improved Network Scalability and Stability", , March, 2001. [6] Alex Zinin, Mike Shand, "Flooding optimizations in link-state routing protocols", , March 2001. [7] Yong Xue at all, "Carrier Optical Services Requirements", , March, 2002. [8] Ash et al, ôCongestion Avoidance and Control for OSPF Networks,ÆÆ , April 2002. 10. Acknowledgements The authors of this document would like to acknowledge the valuable inputs from Lou Berger. 11. Author's Addresses Dan Dovolsky Movaz Networks 7926 Jones Branch Dr., Suite 615 McLean, VA 22102 Phone: (703)847-2438 Email: ddovolsky@movaz.com Igor Bryskin Movaz Networks 7926 Jones Branch Dr., Suite 615 McLean, VA 22102 Phone: (703)847-4208 Email: ibryskin@movaz.com Daniel Awduche Isocore Corporation 8201 Greensboro Drive, Suite 102 McLean, VA 22102 Phone: (703)298-5291 Email: awduche@awduche.com