Network Working Group Abhay Roy (editor) Internet-Draft Cisco Systems Expires: January 10, 2006 July 10, 2005 Adjacency Reduction in OSPF using SPT Reachability draft-roy-ospf-smart-peering-00.txt Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of 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 December 25, 2005. Copyright Notice Copyright (C) The Internet Society (2005). Abstract There is a significant overhead in OSPF if a router has to establish adjacencies with every peer it can verify 2-way connectivity with. OSPF supports a broadcast network type for these scenarios, where you only have to peer with a designated router (DR). But a full mesh of connectivity is required for proper DR election, so this doesn't help in networks with overlapping partial meshes of connectivity. This draft proposes a technique to reduce the number of adjacencies based on the shortest path tree (SPT) reachability information. Roy (Editor), et al. [Page 1] Internet-Draft OSPF Adjacency Reduction Jul 2005 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1 Requirements notation . . . . . . . . . . . . . . . . . . 3 2. Previous Related Work . . . . . . . . . . . . . . . . . . . . 3 3. Proposed Solution . . . . . . . . . . . . . . . . . . . . . . 3 3.1 SPT Reachability Heuristics . . . . . . . . . . . . . . . 3 3.2 State Machine . . . . . . . . . . . . . . . . . . . . . . 5 3.3 Announce the 2-way link in Router-LSA . . . . . . . . . . 6 4. Security Considerations . . . . . . . . . . . . . . . . . . . 6 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 6 6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 6 6.1 Normative References . . . . . . . . . . . . . . . . . . . 6 6.2 Informative References . . . . . . . . . . . . . . . . . . 6 Contributers . . . . . . . . . . . . . . . . . . . . . . . . . 7 Author's Address . . . . . . . . . . . . . . . . . . . . . . 7 Intellectual Property and Copyright Statements . . . . . . . . 7 1. Introduction In OSPF [OSPFV2] [OSPFV3], nodes establish an adjacency by first verifying 2-way connectivity between them and then synchronizing their link state databases. Once the peering relationship is complete and the adjacency is established, the nodes will continue to advertise each other in their periodic Hellos and LSAs. As a result, the peers are maintained in the link state database and are included in all SPF calculations. During the reliable flooding process, a node must ensure that each peer has indeed received the flooded routing update via an acknowledgement and retransmission mechanism. Consequently, maintaining an adjacency for a particular peer is a tradeoff between the added redundancy in routing paths and network reachability versus the overhead (memory consumption, SPF computations, routing overhead, and network convergence). Consider the possibility of reducing the number of adjacencies that a node maintains without compromising reachability and redundancy. This will have direct implications on network scalability and is especially attractive in environments where the network topology is dynamic. For example, in a Mobile Ad-Hoc Network (MANET) where nodes are mobile and the topology is constantly changing, it seems highly desirable to 'intelligently' become adjacent with only selected peers and thus, not establish a peering session with every node that comes within transmission range. Selective peering can be particularly useful in avoiding the peering process for unstable nodes, i.e., nodes that come in and out of transmission range. Roy (Editor), et al. [Page 2] Internet-Draft OSPF Adjacency Reduction Jul 2005 1.1 Requirements notation 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 RFC2119 [RFC2119]. 2. Previous Related Work The formation of a FULL adjacency requires the discovery (2-way relationship) and the database synchronization. To prevent from achieving the FULL state, others have taken the approach of modifying link state protocols to use periodic advertisements (instead of a database exchange). The result is that neighbor discovery is still required, but the routing information is learned over time. An example of this approach is: - OSPFv2 Wireless Interface Type [WINTF] - where the use of periodic advertisements "eliminates the formation of full adjacencies on wireless interfaces; all neighbor states beyond 2-Way are not reached,and no database synchronization is performed". What we propose below, goes a step further by not requiring the formation and maintenance of neighbor state (2-way, or other) *and* without changing the route distribution mechanisms in the link state protocols. In other words, the mechanism described is completely backwards compatible. 3. Proposed Solution Two routers are called synchronized when they have identical link state database. To limit the number of neighbors that are formed, an algorithm is needed to select which neighbors to peer with. The algorithm MUST provide reachability to every possible destination in the network, just like when normal adjacency formation processes are used. We should always peer with a neighbor if it provides our only path to currently unreachable destinations. 3.1 SPT Reachability Heuristics The peering decision is really a local matter to a router. If a router can ensure that the reachability to other nodes is available without bringing up a new adjacency, it can choose to not bring up the new adjacency. Roy (Editor), et al. [Page 3] Internet-Draft OSPF Adjacency Reduction Jul 2005 We propose an algorithm which uses the already existing information about a new neighbor's reachability in the SPT. If the two routers can already reach each other in the SPT, it is not necessary to build up the adjacency between them. The decision to peer or not, is made when a hello is received. When a hello is received from a new neighbor or a neighbor in a state lower than Exchange: - A check is made in the link state database to see if the peer is already reachable in the SPT. - If the peer is either not known in the SPT or is not reachable, we start the Exchange process. - If the peer is reachable than bringing up adjacency with this neighbor does not provide reachability to any new destinations. Lets take an example of a single OSPF area. This check would look for the neighbor's Router LSA. If the LSA is present in the database and is reachable in the SPT, we have a chance to keep this adjacency from going to Exchange. It's worth noting that as the number of links and redundancy in the network is reduced, there may be an increase in suboptimal routing. Roy (Editor), et al. [Page 4] Internet-Draft OSPF Adjacency Reduction Jul 2005 3.2 State Machine The state machine of a basic implementation of this algorithm is provided below: An implementation MAY use some heuristics below (step (3)), beyond the SPT reachability to decide if it considers a new adjacacency to be of value or not. ...................... |Receive a hello | (1) |from a new potential| |neighbor | '`'''''''''''''''''''' | | | ,''''''''''''''''''''''| |Check to see if there | (2) |is a router LSA from |----no--(4)form a |the new potential | new |neighbor in the link | neighbor |state database, which | |is reachable in SPT | '`'''''''''''''''''''''' | |yes (3) | ,'''''''''''''''''''''''''''''''''''''''''''''''''''''''''| | (3b)........................ | |(3a),______________________ |Determine if the | | | |Determine if the new | |number of redundant | | | |link cost is better | |paths to the potential| | | |than the current path| |neighbor is < the | | | |cost by a configured | |maximum configured | | | |amount | |value | | | '`''''''''''''''''''''' '`'''''''''''''''''''''' | | \ / | | .....\.........../.... | | |User configurable | | | |selection algorithm | | | '`'''/'''''''\'''''''' | | / \ | '`'''''''''''''''''''''/'''''''''''\''''''''''''''''''''''' / \ requirements requirements met not met / \ / \ (4) form a new neighbor (5) do not become neighbors Roy (Editor), et al. [Page 5] Internet-Draft OSPF Adjacency Reduction Jul 2005 3.3 Announce the 2-way link in Router-LSA While the technique described above minimizes the number of adjacencies in highly meshed einvironments, it may lead to the undesirable result of limiting the number of transit links available on which to forward traffic. An implementation may choose to allow some (or even all) of these 2-way state neighbors to be announced in the Router-LSA. Since the state remains 2-way, we don't incur control plan (database sync and flooding) overhead. But at the same time, announcing the link in the Router-LSA makes the link available to the data plane. 4. Security Considerations The function described in this document does not create any new security issues for the OSPF protocol. Security considerations for the base OSPF protocol are covered in [OSPFV2], [OSPFV3] and [OSPFV3SEC]. 5. IANA Considerations This document has no actions for IANA. 6. References 6.1 Normative References [OSPFV2] Moy, J., "OSPF Version 2", RFC 2328, April 1998. [OSPFV3] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6", RFC 2740, December 1999. 6.2 Informative References [OSPFV3SEC] Gupta M., Melam N., "Authentication/Confidentiality for OSPFv3", draft-ietf-ospf-ospfv3-auth (work in progress) [WINTF] Ahrenholz J. et al, "OSPFv2 Wireless Interface Type", draft-spagnolo-manet-ospf-wireless-interface (work in progress) Roy (Editor), et al. [Page 6] Internet-Draft OSPF Adjacency Reduction Jul 2005 Contributors The following persons are contributing authors to the document: Dave Cook Russ White Cisco Systems Cisco Systems 7025-4 Kit Creek Road 7025-4 Kit Creek Road RTP, NC 27709 RTP, NC 27709 USA USA Email: dacook@cisco.com Email: riw@cisco.com Alvaro Retana Yi Yang Cisco Systems Cisco Systems 7025-4 Kit Creek Road 7025-4 Kit Creek Road RTP, NC 27709 RTP, NC 27709 USA USA Email: aretana@cisco.com Email: yiya@cisco.com Madhavi W. Chandra Cisco Systems 7025-4 Kit Creek Road RTP, NC 27709 USA Email: mchandra@cisco.com Author's Address Abhay Roy Cisco Systems 170 W. Tasman Drive San Jose, CA 95134 USA Email: akr@cisco.com Intellectual Property Statement The IETF 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 this 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. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Roy (Editor), et al. [Page 7] Internet-Draft OSPF Adjacency Reduction Jul 2005 Copies of IPR 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. 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 this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY 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 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Copyright Statement Copyright (C) The Internet Society (2005). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Roy (Editor), et al. [Page 8]