draft-ietf-ospf-dbex-opt-00.txt   draft-ietf-ospf-dbex-opt-01.txt 
OSPF Working Group R. Ogier OSPF Working Group R. Ogier
Expires: July 2, 2007
Category: Informational Category: Informational
Expires: October 12, 2007
OSPF Database Exchange Summary List Optimization OSPF Database Exchange Summary List Optimization
draft-ietf-ospf-dbex-opt-00.txt draft-ietf-ospf-dbex-opt-01.txt
Status of this Memo Status of this Memo
By submitting this Internet-Draft, each author represents that any By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware 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 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. aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
skipping to change at page 1, line 33 skipping to change at page 1, line 33
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/1id-abstracts.html http://www.ietf.org/1id-abstracts.html
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html http://www.ietf.org/shadow.html
This Internet-Draft will expire on July 2, 2007. This Internet-Draft will expire on October 12, 2007.
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2007). Copyright (C) The IETF Trust (2007).
Abstract Abstract
This document describes a backward compatible optimization for the This document describes a backward compatible optimization for the
Database Exchange process in OSPFv2 and OSPFv3. In this Database Exchange process in OSPFv2 and OSPFv3. In this
optimization, a router does not list an LSA in Database Description 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 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 the LSA was listed in a Database Description packet already received
from the neighbor. This optimization reduces Database Description from the neighbor. This optimization reduces Database Description
overhead by about 50% in large networks. This optimization does not overhead by about 50% in large networks. This optimization does not
affect synchronization, since it only omits unnecessary information affect synchronization, since it only omits unnecessary information
from Database Description packets. from Database Description packets.
1. Introduction 1. Introduction
In OSPFv2 [RFC2328] and OSPFv3 [RFC2740], when two neighboring In OSPFv2 [RFC2328] and OSPFv3 [RFC2740], when two neighboring
routers become adjacent, they synchronize their link-state databases routers become adjacent, they synchronize their link-state databases
via the Database Exchange process. Each router sends the other via the Database Exchange process. Each router sends the other
router a set of Database Description (DD) packets that describes the router a set of Database Description (DD) packets that describes the
router's link-state database for the area. This is done by listing router's link-state database. This is done by listing each LSA
each LSA (i.e., including the header of each LSA) in one of the sent (i.e., including the header of each LSA) in one of the sent DD
DD packets. This procedure allows each router to determine whether packets. This procedure allows each router to determine whether the
the other router has newer LSA instances that should be requested via other router has newer LSA instances that should be requested via
Link State Request packets. Link State Request packets.
The optimization simply observes that it is not necessary for a The 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 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 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 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 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 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 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 recent than the one received, the LSA is removed from the summary
list. list.
The optimization, called the Database Exchange summary list The optimization, called the Database Exchange summary list
optimization, does not affect synchronization, since the LSAs that optimization, does not affect synchronization, since the LSAs that
are omitted from DD packets are unnecessary. The optimization is are omitted from DD packets are unnecessary. The optimization is
fully backward compatible with OSPF. The optimization reduces fully backward compatible with OSPF. The optimization reduces
Database Description overhead by about 50% in large networks in which Database Description overhead by about 50% in large networks in which
routers are usually already nearly synchronized when they become routers are usually already nearly synchronized when they become
adjacent, since it reduces the total number of LSA headers exchanged adjacent, since it reduces the total number of LSA headers exchanged
by about one-half in such networks. The optimization is especially by about one-half in such networks. The optimization is especially
beneficially in large networks with limited bandwidth, such as large beneficial in large networks with limited bandwidth, such as large
mobile ad hoc networks. mobile ad hoc networks.
2. Specification of Optimization 2. Specification of Optimization
The Database Exchange summary list optimization is defined by The Database Exchange summary list optimization is defined by
modifying Section 10.6 (Receiving Database Description Packets) of modifying Section 10.6 (Receiving Database Description Packets) of
RFC 2328 as follows. The second-to-last paragraph of Section 10.6 is RFC 2328 as follows. The second-to-last paragraph of Section 10.6 is
replaced with the following augmented paragraph: replaced with the following augmented paragraph:
When the router accepts a received Database Description Packet as the When the router accepts a received Database Description Packet as the
skipping to change at page 3, line 34 skipping to change at page 3, line 34
different implementations to use the same ordering, this document different implementations to use the same ordering, this document
recommends that LSAs be listed in lexicographically increasing order recommends that LSAs be listed in lexicographically increasing order
of (LS type, Link State ID, Advertising Router) for OSPFv2 and (LS of (LS type, Link State ID, Advertising Router) for OSPFv2 and (LS
type, Advertising Router, Link State ID) for OSPFv3. type, Advertising Router, Link State ID) for OSPFv3.
3. Example 3. Example
This section describes an example to illustrate the database exchange This section describes an example to illustrate the database exchange
summary list optimization. Assume that routers RT1 and RT2 already summary list optimization. Assume that routers RT1 and RT2 already
have identical databases when they start database exchange. Also have identical databases when they start database exchange. Also
assume that the list of LSA headers for the database fits into two assume that the list of LSA headers for the database fits into two DD
(but not one) DD packets. Then the standard database exchange is as packets. Then the standard database exchange is as follows when RT1
follows when RT1 is the first to change the neighbor state to is the first to change the neighbor state to ExStart. Note that each
ExStart. Note that each router sends two full DD packets. router sends two full DD packets.
RT1 (slave) RT2 (master) RT1 (slave) RT2 (master)
ExStart Empty DD (Seq=x,I,M,Master) ExStart Empty DD (Seq=x,I,M,Master)
------------------------------> ------------------------------>
Empty DD (Seq=y,I,M,Master) ExStart Empty DD (Seq=y,I,M,Master) ExStart
<------------------------------ <------------------------------
Exchange Full DD (Seq=y,M,Slave) Exchange Full DD (Seq=y,M,Slave)
------------------------------> ------------------------------>
Full DD (Seq=y+1,M,Master) Exchange Full DD (Seq=y+1,M,Master) Exchange
skipping to change at page 4, line 25 skipping to change at page 4, line 25
Full DD (Seq=y+1,Slave) Full DD (Seq=y+1,Slave)
------------------------------> ------------------------------>
Full DD (Seq=y+2, Master) Full DD (Seq=y+2, Master)
<------------------------------ <------------------------------
Full Empty DD (Seq=y+2, Slave) Full Empty DD (Seq=y+2, Slave)
------------------------------> ------------------------------>
Full Full
If the optimization is used, when RT2 receives the first full DD If the optimization is used, when RT2 receives the first full DD
packet from RT1, it removes from its summary list all LSAs that are 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 listed in the DD packet. Then RT2 sends a DD packet that lists the
remaining LSAs (since all LSA headers fit into two DD packets). When remaining LSAs (since all of the LSA headers fit into two DD
RT1 receives this DD packet, it removes these remaining LSAs from its packets). When RT1 receives this DD packet, it removes these
summary list (causing it to be empty) and sends an empty DD packet to remaining LSAs from its summary list (causing it to be empty) and
RT2. sends an empty DD packet to RT2.
With the optimization, each router sends only one full DD packet With the optimization, each router sends only one full DD packet
instead of two, as shown below. instead of two, as shown below.
RT1 (slave) RT2 (master) RT1 (slave) RT2 (master)
ExStart Empty DD (Seq=x,I,M,Master) ExStart Empty DD (Seq=x,I,M,Master)
------------------------------> ------------------------------>
Empty DD (Seq=y,I,M,Master) ExStart Empty DD (Seq=y,I,M,Master) ExStart
<------------------------------ <------------------------------
skipping to change at page 5, line 8 skipping to change at page 5, line 8
------------------------------> ------------------------------>
Full Full
4. Security Considerations 4. Security Considerations
This document does not raise any new security concerns. This document does not raise any new security concerns.
5. IANA Considerations 5. IANA Considerations
This document specifies a simple backward compatible optimization for This document specifies a simple backward compatible optimization for
OSPFv2 and OSPFv3, which does not require any new number assignment. OSPFv2 and OSPFv3 that does not require any new number assignment.
6. Normative References 6. Normative References
[RFC2328] J. Moy. "OSPF Version 2", RFC 2328, April 1998. [RFC2328] J. Moy. "OSPF Version 2", RFC 2328, April 1998.
[RFC2740] R. Coltun, D. Ferguson, and J. Moy. "OSPF for IPv6", RFC [RFC2740] R. Coltun, D. Ferguson, and J. Moy. "OSPF for IPv6", RFC
2740, December 1999. 2740, December 1999.
Appendix A. Acknowledgments
The recommendation to list LSAs in lexicographical order was
suggested by Acee Lindem.
Author's Address Author's Address
Richard G. Ogier Richard G. Ogier
Email: rich.ogier@earthlink.net Email: rich.ogier@earthlink.net
Intellectual Property Statement Intellectual Property Statement
The IETF takes no position regarding the validity or scope of any The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in pertain to the implementation or use of the technology described in
skipping to change at page 6, line 31 skipping to change at page 6, line 31
http://www.ietf.org/ipr. http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at this standard. Please address the information to the IETF at
ietf-ipr@ietf.org. ietf-ipr@ietf.org.
Disclaimer of Validity Disclaimer of Validity
This document and the information contained herein are provided on an This document and the information contained herein are provided
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY,
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, THE IETF TRUST AND
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES,
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 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 Statement
Copyright (C) The Internet Society (2007). This document is subject Copyright (C) The IETF Trust (2007). This document is subject
to the rights, licenses and restrictions contained in BCP 78, and to the rights, licenses and restrictions contained in BCP 78, and
except as set forth therein, the authors retain all their rights. except as set forth therein, the authors retain all their rights.
Acknowledgment
Funding for the RFC Editor function is provided by the IETF
Administrative Support Activity (IASA).
 End of changes. 14 change blocks. 
27 lines changed or deleted 34 lines changed or added

This html diff was produced by rfcdiff 1.33. The latest version is available from http://tools.ietf.org/tools/rfcdiff/