OSPF Working Group Dimitri Papadimitriou Internet Draft Alcatel-Lucent Intended status: Standard Track May 23, 2010 Expires: November 22, 2010 Phased OSPF Link-State Database Synchronization draft-dimitri-ospf-phased-db-sync-00.txt Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. This document may contain material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The person(s) controlling the copyright in some of this material may not have granted the IETF Trust the right to allow modifications of such material outside the IETF Standards Process. Without obtaining an adequate license from the person(s) controlling the copyright in such materials, this document may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process, except to format it for publication as an RFC or to translate it into languages other than English. 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 November 22, 2010. D.Papadimitriou Expires November 22, 2010 [Page 1] Internet-Draft Phased OSPF Database Synchronization May 23, 2010 Copyright Notice Copyright (c) 2010 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 the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Abstract Opaque Link-State Advertisements (LSA) extend the topological link state of Open Shortest Path First (OSPF). The information contained in Opaque LSA may be used directly by OSPF or indirectly by some application wishing to distribute information throughout the OSPF domain. However the Link-State Database (LSDB) synchronization process is kept unified, i.e., there is no messaging or processing allowing to order the exchanges in the link state database synchronization process. We call this ordering, phasing of logically segmented LSDB into Opaque and non-Opaque. The motivation is to prevent delaying reaching Full state whereas synchronizing over the entire LSDB would delay full adjacency establishment. Table of Contents 1. Introduction................................................3 2. Conventions used in this document...........................4 3. Link-State Database (LSDB) Synchronization..................4 3.1. LSDB Synchronization: General Description..............4 3.2. Application of LSDB Synchronization to Opaque LSA......5 4. Phased Link-State Database (LSDB) Synchronization...........6 4.1. Phased Link-State Database (LSDB) Synchronization Process................................................6 4.2. Transition from LSDB to Opaque LSDB Synchronization....8 4.3. Capability Negotiation.................................8 4.3.1. Option field in Hello Packets.....................9 4.3.2. Link Local Signaling (LLS)........................9 5. Backward Compatibility......................................9 6. Security Considerations....................................10 7. IANA Considerations........................................10 8. References.................................................10 D.Papadimitriou Expires November 23, 2010 [Page 2] Internet-Draft Phased OSPF Database Synchronization May 23, 2010 8.1. Normative References..................................10 8.2. Informative References................................10 9. Acknowledgments............................................10 1. Introduction Open Shortest Path First (OSPF) link-state routing protocol supports a class of Link-State Advertisements (LSA) called Opaque LSAs that provide a generalized mechanism to allow extensibility of OSPF [RFC2328]. The information field contained in Opaque LSAs is often indirectly used by some application wishing to distribute information throughout the OSPF domain. Standard OSPF Link-State Database (LSDB) flooding mechanisms are used to distribute Opaque LSAs to all or some limited portion of the OSPF topology [RFC2370]. Nevertheless, OSPF mandates full synchronization of the LSDB before a routing adjacency is declared in state Full (when LSDB synchronization is completed, the neighbor is in state Full and the two routers are fully adjacent). The reliable and effective LSDB synchronization but also link- state flooding mechanism provided by OSPF has thus been re-used by many distributed network applications that rely on OSPF to exchange non IP routing information. By non-IP routing information, we mean any information that is not directly or indirectly related to the forwarding of IP datagrams. Another case that often leads to a delayed synchronization process is when the number of entries is not bound by the number of links. This observation also leads us to think that AS-external LSAs in particular are good candidate for the approach proposed here and the mechanism can thus be seen as a complement to [RFC1765]. The proposed mechanism phases the LSDB synchronization process by first exchanging IP routing LSAs (Router, Network, Summary, AS- external, and Not-so-stubby area LSAs) and then, the Opaque LSAs as defined in [RFC2370]. The purpose is to prevent delaying the establishment of fully adjacent routers - at this point the adjacency is listed in LSAs - even if the "Opaque part" of the LSDB is not synchronized. We note here that in most cases the application itself makes use of the IP adjacencies for application specific message exchanges and thus the applications would not be slow down by this process. In this sense, the present document reverts back to [RFC2328] the LSDB synchronization process as extended by [RFC2370] (that covers LSDB including both non-Opaque and Opaque LSAs). Phasing is achieved by logically segmenting the LSDB synchronization process: add "on top of" the LSDB synchronization process D.Papadimitriou Expires November 23, 2010 [Page 3] Internet-Draft Phased OSPF Database Synchronization May 23, 2010 described in [RFC2328], a synchronization process dedicated to Opaque LSAs. This phasing prevents delaying establishment of full adjacency between two routers (Full state) resulting from the time needed to synchronize Opaque LSAs. This condition occurs in particular when the number of Opaque LSAs >> non-Opaque LSAs. The fundamental aspect of the proposed approach consists thus of considering the state Full as the invariant state for reaching full adjacency. The purpose of the proposed Opaque LSDB Synchronization process is to devise a less drastic alternative to the current approach developed at OSPF WG that mandates complete separation of OSPF instances when Opaque LSA are decoupled from IP Routing [OSPF- TP]. The latter does not actually solve the so-called "Opaque overload" problem because it separates IP-related from non-IP related routing information instead of Opaque from non-Opaque LSAs. The proposed approach here is to avoid duplicating OSPF instances while keeping Opaque LSA messaging and processing as part of a single OSPF instance. 2. Conventions used in this document In examples, "C:" and "S:" indicate lines sent by the client and server respectively. 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. 3. Link-State Database (LSDB) Synchronization 3.1. LSDB Synchronization: General Description In link-state routing, it is very important for all routers' Link-State Databases (LSDB) to stay synchronized. OSPF simplifies this by requiring only adjacent routers to remain synchronized. The synchronization process begins as soon as the routers attempt to bring up the routing adjacency. Each router describes its database by sending a sequence of Database Description (DD) packets to its neighbor. Each Database Description packet describes a set of LSAs belonging to the router's database. When the neighbor sees an LSA that is more recent than its own database copy, it makes a note that this newer LSA should be requested. This sending and receiving of Database Description packets is called the "Database Exchange D.Papadimitriou Expires November 23, 2010 [Page 4] Internet-Draft Phased OSPF Database Synchronization May 23, 2010 Process". During this process, the two routers form a master/slave relationship. Each Database Description packet has a sequence number. Database Description packets sent by the master (polls) are acknowledged by the slave through echoing of the sequence number. Both polls and their responses contain summaries of link state data. The master is the only one allowed to retransmit Database Description packets. It does so only at fixed intervals, the length of which is the configured per-interface constant RxmtInterval. 3.2. Application of LSDB Synchronization to Opaque LSA Per [RFC2370]: an opaque-capable router learns of its neighbor's opaque capability at the beginning of the "Database Exchange Process" (see Section 10.6 of [RFC2328], receiving Database Description packets from a neighbor in state ExStart). A neighbor is opaque-capable if and only if it sets the O-bit in the Options field of its Database Description packets; the O-bit is not set in packets other than Database Description packets. Then, in the next step of the Database Exchange process, Opaque LSAs are included in the Database summary list that is sent to the neighbor if and only if the neighbor is opaque capable. When flooding Opaque LSAs to adjacent neighbors, an opaque-capable router looks at the neighbor's opaque capability. Opaque LSAs are only flooded to opaque-capable neighbors, i.e., Opaque LSAs are only placed on the link-state retransmission lists of opaque- capable neighbors. In case non-opaque-capable neighbor inadvertently receives Opaque LSAs, the non-opaque- capable router will then simply discard the LSA receiving LSAs having unknown LS types). Hence, [RFC2370] does not modify the state machine as defined in Section 10.3 of [RFC2328] except for the action associated with State: ExStart, Event: NegotiationDone which is where the Database summary list is built in order to incorporate the Opaque LSA in OSPF (see Figure 1). 4. Phased Link-State Database (LSDB) Synchronization Compared to the [RFC2370] processing, the Phase Link-State Database (LSDB) synchronization modifies the LSDB exchange process as follows: Opaque LSAs are included in the LSDB summary list that is sent to the neighbor, if and only if i) The neighbor is Opaque capable (see Section 4 and Appendix A of [RFC2370]) D.Papadimitriou Expires November 23, 2010 [Page 5] Internet-Draft Phased OSPF Database Synchronization May 23, 2010 +-------+ |ExStart| +-------+ | NegotiationDone| | v +--------+ |Exchange| +--------+ | Exchange| Done | +----+ | +-------+ |Full|<---------+----->|Loading| +----+<- +-------+ | LoadingDone | ------------------ Fig.1 Neighbor state changes (Database Exchange) ii) The neighbor has fully exchanged the area LSDB that consists of the router-LSAs (Type 1), network-LSAs (Type 2), and summary- LSAs (Type 3, 4) contained in the area structure, along with the AS-external-LSAs (Type 5) contained in the global structure, and Not-So-Stubby Area (NSSA) LSAs (Type 7) [RFC3101], i.e., the "Full" state has been reached. iii) Both local and neighbor router supports the phased LSDB synchronization (see Section 4.3). 4.1. Phased Link-State Database (LSDB) Synchronization Process The process is depicted in Fig.2, the ExStart, Exchange, Loading and Full states are defined per [RFC2328]. Note that in Full State, the router can perform all subsequent operations per [RFC 2328] including, the computation of the shortest-path tree for an area, and the computation of the AS external routes, as described in Section 16 of [RFC2328]. Events NegotiationDone, ExchangeDone and LoadingDone are used as defined per [RFC2328]. D.Papadimitriou Expires November 23, 2010 [Page 6] Internet-Draft Phased OSPF Database Synchronization May 23, 2010 +---------+ | ExStart | +---------+ | |NegotiationDone | v +---------+ |Exchange | +---------+ | |Exchange |Done | +---------+ | +---------+ --------->| Full |<---------+--------->| Loading | | +---------+<- +---------+ | | | | | | | LoadingDone | | | ----------------------- | | | |Start_O | | RFC 2328 ------|---------------|------------------------------------------ | | | | New | v | +-----------+ | |NExchange_O| | +-----------+ | | | |NExchange | |Done_O | | +---------+ | +---------+ | Full_O |<---------+--------->|Loading_O| +---------+<- +---------+ | | | LoadingDone_O | ----------------------- Fig.2 Modified Neighbor state changes (Database Exchange) D.Papadimitriou Expires November 23, 2010 [Page 7] Internet-Draft Phased OSPF Database Synchronization May 23, 2010 4.2. Transition from LSDB to Opaque LSDB Synchronization In case Full state is not reached due to e.g. corruption or Fletcher checksum error, the exchange process restarts (go back to ExStart). In case Full state is reached, the process continues as follows (note that the master remains the master as negotiated during the ExStart step): - Start_O (Event): LSDB contain Opaque_LSA's AND capability as described in Section 4.3 successfully negotiated. This ensures backward compatibility with [RFC2370]. - NExchange_O (State): the router lists the contents of its Opaque area LSDB in the neighbor Database summary list. The Opaque area LSDB consists of Type 9 and Type 10 Opaque LSAs along with Type 11 Opaque LSAs contained in the global structure. The router sends the Database Description (DD) packets for these Opaque LSAs to the neighbor. Each DD Packet has a DD sequence number, and is explicitly acknowledged. Only one DD Packet is allowed outstanding at any one time. In this state, LS Request Packets may also be sent asking for the neighbor's more recent Opaque LSAs. - NExchangeDone_O (Event): both routers have successfully transmitted a full sequence of DD packets. Each router now knows what parts of its Opaque LSDB are out of date. - Loading_O (State): LS Request packets are sent to the neighbor asking for the more recent Opaque LSAs that have been discovered (but not yet received) in the NExchange_O state. - LoadingDone_O (Event): LS Updates have been received for all out-of-date portions of the Opaque LSDB. This is indicated by the Link state request list becoming empty after the Database Exchange process has completed. - Full_O (State): neighboring nodes have completed Opaque LSA exchange. 4.3. Capability Negotiation Negotiating Phased LSDB synchronization can be performed by inserting a Phased LSDB Flag in: D.Papadimitriou Expires November 23, 2010 [Page 8] Internet-Draft Phased OSPF Database Synchronization May 23, 2010 i) Option field of Hello Packets and DD Packets ii) Data block of Link Local Signaling (LLS) and DD Packets 4.3.1. Option field in Hello Packets The Options field (8-bits) enables OSPF routers to support (or not support) optional capabilities, and to communicate their capability level to other OSPF routers. Through this mechanism routers of differing capabilities can be mixed within an OSPF routing domain. When used in Hello packets, the Options field allows a router to accept a neighbor at the condition of adaptation to neighbors's capability (due to the initial mismatch): if either of the neighbors does not support or does not recognize the capability the synchronization is not phased. In this case, routers encountering the unrecognized Option bits in received Hello Packets ignore the capability and process the packet normally. Then, by exchanging this capability in Database Description (DD) packets a router can sequence its exchange of LSAs (starting by non-Opaque LSAs and then Opaque LSAs): if both neighbors are capable of phased synchronization, they may still decide to use or not. This alternative is perfectly valid but requires usage of one bit of the Option field that is a very sparse resource. 4.3.2. Link Local Signaling (LLS) To Link-local signaling (LLS), OSPF routers add a special data block to the end of OSPF packets (or right after the authentication data block when cryptographic authentication is used). The LLS block is attached to OSPF Hello packets. The drawback of this alternative is that the delivery of LLS data in Hello packets is not guaranteed. To circumvent this problem, the solution consists in piggy bagging the Phased DB Flag in the Database Description packets. 5. Backward Compatibility The proposed synchronization process is backward compatible since the mechanism extends the current process if and only if the mechanism is locally (see Section 4.2) and remotely supported (see Section 4.3). If either of these conditions is not met LSDB synchronization falls back to the linear process currently D.Papadimitriou Expires November 23, 2010 [Page 9] Internet-Draft Phased OSPF Database Synchronization May 23, 2010 specific per [RFC2370]. Note also that the proposed mechanism does not modify the LSDB process as specified in [RFC2328]. However, it does not prevent that routers may be required to support both methods. This could be the case typically for ABR's. 6. Security Considerations TBD 7. IANA Considerations TBD 8. References 8.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC2234] Crocker, D. and Overell, P.(Editors), "Augmented BNF for Syntax Specifications: ABNF", RFC 2234, Internet Mail Consortium and Demon Internet Ltd., November 1997. [RFC2328] J. Moy, "OSPF version 2", RFC 2328, Internet Engineering Task Force, April 1998. [RFC2370] R. Coltun, "The OSPF Opaque LSA Option", RFC 2370, July 1998. 8.2. Informative References [OSPF-TP] A.Lindem, et al. "OSPF Transport Instance Extensions", IETF Draft, Work in Progress, draft-ietf-ospf- transport-instance-04.txt, April 2010. [RFC3101] P. Murphy, "The OSPF Not-So-Stubby Area (NSSA) Option", RFC 3101, Internet Engineering Task Force, January 2003. 9. Acknowledgments Authors would like to thank Marc Lasserre, Devendra Raut, Andrew Lange, and Manav Bhatia for their comments. This document was prepared using 2-Word-v2.0.template.dot. D.Papadimitriou Expires November 23, 2010 [Page 10] Internet-Draft Phased OSPF Database Synchronization May 23, 2010 Authors' Addresses Dimitri Papadimitriou Alcatel-Lucent Bell Copernicuslaan 50 2018 Antwerpen Belgium Phone: +32 3 2408491 Email: dimitri.papadimitriou@alcatel-lucent.com D.Papadimitriou Expires November 23, 2010 [Page 11]