Internet Draft OSPF Multi Links December 2005 Network Working Group Internet Draft Nitin Kakkar K.L Srini Document: draft-kakkar-srini-ospf-multi-link- Huawei 00.txt Technologies Bangalore Expires: June 2006 December 2005 OSPF Multiple Interface Optimizations Status of this Memo This document is a submission by the author to IETF Network Working Group of the Internet Engineering Task Force (IETF). Comments should be submitted to the nitink@huawei.com. 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. Abstract OSPF is a link state IGP routing protocol, but it does not utilizes multiple links between adjacent routers efficiently. This Memo tries to utilize multiple links between adjacent routers to make initial adjacency establishment & flooding more optimized, such that these procedures become faster and consumes lesser bandwidth. Conventions used in this document Expires - June 2006 [Page 1] Internet Draft OSPF Multi Links December 2005 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. Table of Contents 1. Introduction...................................................2 2. Adjacency formation Recommendation.............................2 3. Flooding Recommendations.......................................4 4. Adjacency Switching Recommendations............................6 5. Patents........................................................6 6. Formal Syntax..................................................6 Security Considerations...........................................6 References........................................................6 Acknowledgments...................................................7 Author's Addresses................................................7 Disclaimer of Validity............................................7 1. Introduction In this document ospf refers to both version 2 and version 3 of open shortest path first protocol. Any large network is likely to have multiple links between routes, if ospf is running in such environment it is likely to receive multiple requests to form adjacency with peer on . Under large databases adjacency formation put extreme strain on cpu and network resources. Similarly during flooding, LSA’s are flooded and retransmitted multiple times to the same neighbor because no special handling is provided for topologies involving multiple interfaces between peers. In order to improve cpu and network utilization during initial adjacency establishment and flooding we provide some recommendations in section 2,3 and 4. 2. Adjacency formation Recommendation If two adjacent routes have multiple links between them, whenever links/routers come up simultaneously, OSPF tries to form multiple adjacencies with the same neighbor almost simultaneously (Subjected to Maximum Concurrent Adjacencies Number described in [3]). This approach has following problems 1) LSDB’s are traversed multiple times. 2) Most of the LSA's are propagated Multiple times Expires - June 2006 [Page 2] Internet Draft OSPF Multi Links December 2005 AS Scope LSA’s will be propagated multiple times, Area scope LSA's May be propagated multiple times if adjacencies are in same area. 2) Subjected to Maximum Concurrent Adjacencies Number [3], some distinct router will have to wait to form adjacency. To avoid these problems we provide following recommendations Classify every adjacency as ‘‘Primary’’ or ‘‘Secondary’’. Always first adjacency with a peer is marked as Primary and subsequent adjacencies with the same peer are marked as ‘‘Secondary’’. Before entering 2way state with a peer, 1. If there is NO existing adjacency with the peer Prepare DB description packet as described in [1]. 2.If there is already a FULL adjacency with the same peer. A)If there is an existing adjacency in same area with the peer, Only describe Link Scope LSA’s in Db description packet B)If there is an existing adjacency in different, non stub area with the peer, Only describe Area scope and Link Scope LSA’s in Db description packet C) If all existing adjacencies with the peer are in stub area and new adjacency is in non-stub area, Prepare DB description packet as described in [1]. 3.If already an adjacency formation is in progress with the peer (i.e NFSM state 2 way or greater but less then full, irrespective of area and interface). A)Mark adjacency as Secondary B)Prepare DB Description packet as described in 2.A , 2.B and 2.C above. C)If secondary adjacency exhausts its request list first, borrow some external LSA headers(Or area scope LSA’s if both primary and secondary adjacencies are in same area) from Primary adjacencies request list, Mark secondary adjacency state as ‘‘Borrowed’’ and request LSA’s to peer on secondary adjacency , till primary adjacency’s request list also exhausts. D)If to some reason secondary adjacency is terminated abnormally and its state is borrowed, simply copy the retransmit list of Secondary neighbor to Primary adjacency’s neighbor. E)Do not make secondary adjacency FULL before primary adjacency. Expires - June 2006 [Page 3] Internet Draft OSPF Multi Links December 2005 F)If to some reason Primary adjacency is terminated abnormally, router must restart all secondary adjacencies by sending a deliberate sequence number mismatch,( This is faster method to reestablish adjacency then One way Hello). It is easier to see that in presence of multiple interfaces between peers adjacency establishment will be faster because of 1) Reduced request list size of secondary adjacencies. 2) Concurrent and disjoint usage of link bandwidth for multiple adjacencies. 3. Flooding Recommendations Whenever multiple adjacencies exists between same peers it is fruitless to flood LSA’s multiple times. In this section we will present an approach to optimize flooding by minimizing the duplication of LS updates. We introduce following new flags, In neighbor structure we introduce flag ‘‘ASMaster’’, used for AS scope LSA’s. Whenever multiple adjacencies exist between two peers, it will naturally have multiple neighbor entries. One of these neighbor entries from non stub area will be marked as ‘‘ASMaster’’ A) If the interface on which it is connected to neighbor is the fastest (highest bandwidth) among all interfaces connected to same neighbor, B) If multiple interfaces are of same bandwidth then interface with highest IP(ipv6 for ospfv3) MTU is preferred., C) If Mtu is also same, interface with highest IF Index is preferred. In Interface structure we introduce a new flag ‘‘FloodAS’’, Whenever an Interface contains at least one neighbor with ‘‘ASMaster’’ flag set, its ‘‘FloodAS’’ flag will be set. Similarly we introduce a flag ‘‘AreaMaster’’ in neighbor structure, used for AREA Scope LSA’s. This flag will be set on per area basis for the neighbor on fastest link. I.e Among adjacencies to same pear in same area, FloodArea will set for the neighbor stucture on fastest interface (Same criteria as described in A,B & C above). Similarly in Interface structure we introduce another new flag ‘‘FloodArea’’, will be set if there is a neighbor with ‘‘AreaMaster’’ flag set. Expires - June 2006 [Page 4] Internet Draft OSPF Multi Links December 2005 Example Lets say between two routers A & B there are 4 adjacencies number 1 -4, And assume link 1 & 2 are in Area 0, Link 3 & 4 are in Area 1. Further Link capacities are Link1-1Mbps, Link2-100Mbps, Link3- 64kbps, MTU1500, Link4-64Kbps MTU 1280. _____ _____ | |--------|1 | | A |--------|2 B | | |--------|3 | |_____|--------|4____| According to algorithm described Link 2 will be marked as ‘‘FloodAS’’ and also ‘‘FloodArea’’ for area 0. Link 3 will be marked as ‘‘FloodArea’’ for area 1. Flooding Algorithm Modification Basic flooding mechanisms remain the same as section 13 of [1] with the following additional checks 1) Flood an AS scope LSA on an interface only when it’s ‘‘FloodASE’’ flag is set 2) Add AS Scope LSA’s to the retransmit list of only neighbors with ‘‘ASEmaster’’ flag set, 3) Flood an Area scope LSA on an interface only when its ‘‘FloodArea’’ flag is set. 4) Add Area scope LSA’s to the retransmit list of only neighbors with ‘‘AREAMaster’’ flag set. 5) When Ifdown event occurs for interface marked as ‘‘FloodASE’’/’’FloodArea’’, or KillNbr event occur for neighbors marked as ‘‘ASMaster’’ or ‘‘AreaMaster’’, select a new ‘‘ASMaster’’ and ‘‘AreaMaster’’ neighbor and copy the retransmit list from neighbors to the new ‘‘master’’. If no new neighbor is found discard entries from retransmit list. It is easier to see that flooding will be lighter because only one interface is used for retransmission and only a few interfaces will be used for flooding. From our example only Link-2 will be used to flood AS Scope LSA’s. Further Link-2 will be used to flood Area scope LSA’s in Area 0 & Link 3 will be used to flood Area Scope LSA’s in Area 1. Expires - June 2006 [Page 5] Internet Draft OSPF Multi Links December 2005 4. Adjacency Switching Recommendations RFC 4222 explicitly defines max concurrent DD number and advises to throttle more adjacencies. Further RFC4222 prohibits terminating adjacencies in the middle. This approach has a problem that whenever slow interfaces come up first and makeup max dd count number faster interfaces have to wait unusually long time to form adjacencies. For this scenario we recommend 1) If a new adjacency request comes up from a neighbor which is already having an adjacency with us do not apply max concurrent DD criteria on it. 2) While building Database Description packet, keep a count of all LSA’s sizes, so that we know the total amount of bytes to be sent to peer. 3) Whenever receive an acknowledge packet during dd formation, keep a count of bytes already reached peers. These two count along with interface bandwidth will give us an estimate of remaining time for an adjacency. If Remaining time for forming adjacency >> Time for new adjacency, send sequence number mismatch to first adjacency and form adjacency on the faster interface. 5. Patents A Patent has been applied for this mechanism in Peoples Republic of China’s Beijing patent office. Approval is pending. 6. Formal Syntax The following syntax specification uses the augmented Backus-Naur Form (BNF) as described in RFC-2234. Security Considerations This document does not introduce any new security issues to OSPF. References [RFC2328] J Moy, ‘‘OSPF Version 2’’. [RFC2740] J Moy, R Coltun, D Ferguson, ‘‘OSPF for IPV6’’. Expires - June 2006 [Page 6] Internet Draft OSPF Multi Links December 2005 [RFC4222] G Chodhury, Ed. " Prioritized Treatment of Specific OSPF Version 2 Packets and Congestion Avoidance’’. Acknowledgments We would like to acknowledge the support and helpful comments of Mr Praveen GS, Mr Anup, Mr Raghu, Mr Zhangjinagping ,Mr Fucho.and Mr Prabhu G.Biradar. Author's Addresses Nitin Kakkar Huawei Technologies India Pvt Ltd, Level-3, Leela Galleria, The Leela Palace, #23 Airport Road, Bangalore 560008, India Phone: +91 80 5217192 Email: nitink@huawei.com KL Srini Huawei Technologies India Pvt Ltd, Level-3, Leela Galleria, The Leela Palace, #23 Airport Road, Bangalore 560008, India Phone: +91 80 5217192 Email: kls@huawei.com 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. Expires - June 2006 [Page 7]