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]
