OSPF Working Group R. Ogier Internet-Draft August 10, 2006 Expires: February 10, 2007 Category: Informational OSPF Database Exchange Summary List Optimization draft-ogier-ospf-dbex-opt-01.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/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html This Internet-Draft will expire on December 19, 2006. Copyright Notice Copyright (C) The Internet Society (2006). Abstract This document describes a backward compatible optimization for the Database Exchange process in OSPFv2 and OSPFv3. In this optimization, a router does not list an LSA in Database Description packets sent to a neighbor, if the same or a more recent instance of the LSA was listed in a Database Description packet already received from the neighbor. This optimization reduces Database Description overhead by about 50% in large networks. This optimization does not affect synchronization, since it only omits unnecessary information from Database Description packets. Ogier Expires February 10, 2007 [Page 1] Internet-Draft MANET Extension of OSPF August 2006 1. Introduction In OSPFv2 [RFC2328] and OSPFv3 [RFC2740], when two neighboring routers become adjacent, they synchronize their link-state databases via the Database Exchange process. Each router sends the other router a set of Database Description (DD) packets that describes the router's link-state database for the area. This is done by listing each LSA (i.e., including the header of each LSA) in one of the sent DD packets. This procedure allows each router to determine whether the other router has newer LSA instances that should be requested via Link State Request packets. The proposed optimization simply observes that it is not necessary for a router (master or slave) to list an LSA in a DD packet if it knows the neighbor already has an instance of the LSA that is the same or more recent (and therefore will not request the LSA). To avoid listing such LSAs in DD packets, when an LSA is listed in a DD packet received from the neighbor, and the Database summary list for the neighbor has an instance of the LSA that is the same as or less recent than the one received, the LSA is removed from the summary list. The proposed optimization, called the Database Exchange summary list optimization, does not affect synchronization, since the LSAs that are omitted from DD packets are unnecessary. The optimization is fully backward compatible with OSPF. The optimization reduces Database Description overhead by about 50% in large networks in which routers are usually already nearly synchronized when they become adjacent, since it reduces the total number of LSA headers exchanged by about one-half in such networks. The optimization is especially beneficially in large networks with limited bandwidth, such as large mobile ad hoc networks. Three versions of the optimization are described, which differ in whether a router must fully process a received DD packet before sending its next DD packet, and whether the LSAs must be listed in (forward or reverse) lexicographical order. Depending on the network scenario, these versions may perform differently in terms of the amount of overhead saved and the time required to become fully adjacent. 2. Specification of Proposed Optimization The Database Exchange summary list optimization is defined by modifying Section 10.6 (Receiving Database Description Packets) of RFC 2328 as follows. The second-to-last paragraph of Section 10.6 is replaced with the following augmented paragraph: Ogier Expires February 10, 2007 [Page 2] Internet-Draft MANET Extension of OSPF August 2006 When the router accepts a received Database Description Packet as the next in sequence the packet contents are processed as follows. For each LSA listed, the LSA's LS type is checked for validity. If the LS type is unknown (e.g., not one of the LS types 1-5 defined by this specification), or if this is an AS- external-LSA (LS type = 5) and the neighbor is associated with a stub area, generate the neighbor event SeqNumberMismatch and stop processing the packet. Otherwise, the router looks up the LSA in its database to see whether it also has an instance of the LSA. If it does not, or if the database copy is less recent (see Section 13.1), the LSA is put on the Link state request list so that it can be requested (immediately or at some later time) in Link State Request Packets. Additionally, if it does and the database copy is the same as or less recent than the received copy, the LSA is also removed from the Database summary list, if a copy still exists on the list. To provide the maximum benefit, the router should perform one of the following three options, which differ in whether a router must fully process a received DD packet before sending its next DD packet, and whether the LSAs must be listed in (forward or reverse) lexicographical order. Option C was suggested by Mitchell Erblich. A discussion of the advantages of each option is given in Section 3. 2.1. Option A If this option is selected, the router must process all LSA headers (for the purpose of updating the summary list) in a received DD packet before sending its next DD packet in reply. In this way, the router avoids listing an LSA in a DD packet if the same or more recent instance of the LSA was already listed by the neighbor in a received DD packet. This option is recommended for limited bandwidth networks such as mobile ad hoc networks. 2.2. Option B To describe this option, we define the DR level of a router (for a given interface) to be 2 for a DR, 1 for a Backup DR, and 0 otherwise. In this option, the router with the larger DR level performs database exchange as in RFC 2328 with no changes. The procedure for the router with the smaller DR level is as follows. The router updates the summary list for the neighbor as described above when it accepts a received DD packet as the next in sequence. However, the procedure for replying to the received DD packet depends on the value of the M bit in the received DD packet. If the M bit is 1, then the router replies with an empty DD packet (with no LSA headers) with the M bit set to 1. If the M bit is 0 (all LSAs have been listed), then the router first processes all LSA headers in the Ogier Expires February 10, 2007 [Page 3] Internet-Draft MANET Extension of OSPF August 2006 received DD packet (as in Option A) and then proceeds to send one or more DD packets as in RFC 2328, to list any LSAs that remain in the summary list. Note that the router with the smaller DR level will only list LSAs for which it has a more recent instance than its neighbor with larger DR level. Therefore, assuming DRs and Backup DRs are more likely to have updated information than DR Others, the number of LSAs that must be listed by a DR Other is likely to be small. 2.3. Option C In this option, the master is required to list its LSAs (in DD packets) in lexicographically increasing order of (LS type, Link State ID, Advertising Router), and the slave is required to list its LSAs in the reverse (decreasing) order. The router (master or slave) is not required to process all LSA headers in the received DD packet before sending its next DD packet in reply. However, it is assumed that a router will process all LSA headers in the received DD packet with sequence number n before it replies to the next received DD packet with sequence number n+1. This allows the summary list to be updated in parallel with sending a DD packet in reply and receiving the next DD packet. Unlike Options A and B, Option C does not guarantee a 50% reduction in the number of LSA headers exchanged even if both routers already had identical databases. For example, if all LSA headers fit into a single DD packet, then both routers will still list all LSAs. This drawback can be lessened (but not completely fixed) by applying the procedure of Option A only to the final nonempty DD packet received from the neighbor. That is, if the M bit is 0 in the received DD packet, then the router processes all LSAs headers in the received DD packet before sending its next DD packet in reply. We note that if Option A or B is used, then there is no benefit to listing the LSAs in lexicographical order as in Option C. 3. Comparison of Options A, B, and C There may be a partial reduction in the number of LSA headers sent if the master selects one of the three options while the slave selects another of the three options. However, for the full benefit, all routers should select the same option. As mentioned above, Options A and B guarantee a 50% reduction in the number of LSA headers sent assuming that both routers already have identical databases, but Option C does not. However, the reduction Ogier Expires February 10, 2007 [Page 4] Internet-Draft MANET Extension of OSPF August 2006 for Option C approaches 50% if the number of DD packets required to list all LSAs is large. Although Option A requires each router to process all LSA headers in a received DD packet before sending its next DD packet in reply, in networks with limited bandwidth (where the optimization will provide the most benefit) the additional delay incurred by this requirement is expected to be much smaller than the time required to transmit the DD packet. Moreover, in such networks, the reduction in the number of LSA headers exchanged will more than compensate for any increased delay caused by this requirement. Option B avoids the requirement to fully process the received DD packet before sending the next DD packet in reply, except that the router with the smaller DR level must fully process the final nonempty DD packet received from its neighbor, before sending its next DD packet in reply. Option B has the disadvantage that the router with the smaller DR level will not list any LSAs until it receives the final nonempty DD packet from its neighbor. However, this will not increase the delay to reach the Full state unless the router with the smaller DR level has a large number of LSAs that the neighbor (with larger DR level) does not have, which is unlikely. Option C avoids the requirement to fully process the received DD packet before sending the next DD packet in reply, thus potentially reducing the delay to reach the Full state. This delay reduction could be significant in some networks, depending on the size of the database, the data transmission rate, and the router's processing speed. However, this delay will not likely be significant in limited bandwidth networks (such as mobile ad hoc networks), since the time required to process the list of LSA headers in a received DD packet will typically be much less than the time required to transmit the DD packet. Mobile ad hoc networks will likely be configured as a stub area to limit the number of summary-LSAs that are flooded into the area. As a result, the time required to process all received LSA headers is not likely to be significant in such networks. 4. Example This section describes an example to illustrate the database exchange summary list optimization. Assume that routers RT1 and RT2 already have identical databases when they start database exchange. Also assume that the list of LSA headers for the database fits into two (but not one) DD packets. Then the standard database exchange is as follows when RT1 is the first to change the neighbor state to ExStart. Note that each router sends two full DD packets. Ogier Expires February 10, 2007 [Page 5] Internet-Draft MANET Extension of OSPF August 2006 RT1 (slave) RT2 (master) ExStart Empty DD (Seq=x,I,M,Master) ------------------------------> Empty DD (Seq=y,I,M,Master) ExStart <------------------------------ Exchange Full DD (Seq=y,M,Slave) ------------------------------> Full DD (Seq=y+1,M,Master) Exchange <------------------------------ Full DD (Seq=y+1,Slave) ------------------------------> Full DD (Seq=y+2, Master) <------------------------------ Full Empty DD (Seq=y+2, Slave) ------------------------------> Full If the optimization is used with Option A, when RT2 receives the first full DD packet from RT1, it removes from its summary list all LSAs that are listed in the DD packet, and sends a DD packet that lists the remaining LSAs (since all LSA headers fit into two DD packets). When RT1 receives this DD packet, it removes these remaining LSAs from its summary list (causing it to be empty) and sends an empty DD packet to RT2. With the optimization, each router sends only one full DD packet instead of two, as shown below. RT1 (slave) RT2 (master) ExStart Empty DD (Seq=x,I,M,Master) ------------------------------> Empty DD (Seq=y,I,M,Master) ExStart <------------------------------ Exchange Full DD (Seq=y,M,Slave) ------------------------------> Full DD (Seq=y+1,Master) Exchange <------------------------------ Full Empty DD (Seq=y+1, Slave) ------------------------------> Full 5. Security Considerations This document does not raise any new security concerns. Ogier Expires February 10, 2007 [Page 6] Internet-Draft MANET Extension of OSPF August 2006 4. IANA Considerations This document proposes a simple backward compatible optimization for OSPFv2 and OSPFv3, which does not require any new number assignment. 5. Acknowledgments The idea of listing LSAs in lexicographical order was first suggested by Acee Lindem. Mitchell Erblich suggested more specifically that the slave should list LSAs in the reverse order as the master, which is Option C. Paul Jakma suggested the change in which the router compares the received LSA to the database copy (instead of to the copy on the Database summary list) in deciding whether to remove the LSA from the Database summary list. 6. Draft Modifications The main changes from version 00 to version 01 are as follows: o Two options (B and C) have been added, which differ in whether the LSAs must be listed in lexicographical order and whether a router must fully process a received DD packet before sending its next DD packet. (The previous version used option A.) o An example is presented to illustrate the optimization. o The router compares the received LSA to the database copy (instead of to the copy on the Database summary list) in deciding whether to remove the LSA from the Database summary list. 6. Normative References [RFC2328] J. Moy. "OSPF Version 2", RFC 2328, April 1998. [RFC2740] R. Coltun, D. Ferguson, and J. Moy. "OSPF for IPv6", RFC 2740, December 1999. Author's Address Richard G. Ogier Email: rich.ogier@earthlink.net Ogier Expires February 10, 2007 [Page 7] Internet-Draft MANET Extension of OSPF August 2006 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. 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 (2006). 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. Ogier Expires February 10, 2007 [Page 8]