OSPF Database Exchange Summary List Optimization
A backward-compatible trick that roughly halves the LSA headers OSPF routers send when they synchronize.
Ogier, R., "OSPF Database Exchange Summary List Optimization", RFC 5243, DOI 10.17487/RFC5243, May 2008, <https://www.rfc-editor.org/info/rfc5243>.
@misc{rfc5243,
series = {Request for Comments},
number = 5243,
howpublished = {RFC 5243},
publisher = {RFC Editor},
doi = {10.17487/RFC5243},
url = {https://www.rfc-editor.org/info/rfc5243},
author = {R. Ogier},
title = {{OSPF Database Exchange Summary List Optimization}},
pagetotal = 5,
year = 2008,
month = may,
} RFC text
Contents
Network Working Group R. Ogier
Request for Comments: 5243 SRI International
Category: Informational May 2008
OSPF Database Exchange Summary List Optimization
Status of This Memo
This memo provides information for the Internet community. It does
not specify an Internet standard of any kind. Distribution of this
memo is unlimited.
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 a Link State Advertisement (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.
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. 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 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 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
beneficial in large networks with limited bandwidth, such as large
mobile ad hoc networks.
2. Specification of 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:
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, 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. In addition, if the Database summary list contains
an instance of the LSA that is the same as or less recent than the
listed LSA, the LSA is removed from the Database summary list.
The above additional step (which updates the Database summary list)
may be performed either before or after the router looks up the
listed LSA in its database and possibly adds the LSA to the Link
state request list. However, to implement the optimization, the
additional step must be performed for each LSA listed in the received
DD packet (to fully update the Database summary list) before the next
DD packet is sent in response.
Although the optimization does not require that LSAs be listed in DD
packets in any particular order, faster lookup of LSAs in the
Database summary list may be possible if LSAs are listed in the same
order by all routers. If such an ordering is used, then to encourage
different implementations to use the same ordering, this document
recommends that LSAs be listed in lexicographically increasing order
of (LS type, Link State ID, Advertising Router) for OSPFv2 and (LS
type, Advertising Router, Link State ID) for OSPFv3.
3. 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 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.
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, 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. Then RT2 sends a DD packet that lists the
remaining LSAs (since all of the 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
4. Security Considerations
This document does not raise any new security concerns.
5. IANA Considerations
This document specifies a simple backward-compatible optimization for
OSPFv2 and OSPFv3 that does not require any new number assignment.
6. Normative References
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[RFC2740] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6", RFC
2740, December 1999.
7. Acknowledgments
The recommendation to list LSAs in lexicographical order was
suggested by Acee Lindem.
Author's Address
Richard G. Ogier
EMail: rich.ogier@earthlink.net
Full Copyright Statement
Copyright (C) The IETF Trust (2008).
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.
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, THE IETF TRUST 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.
Intellectual Property
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.
AI ELI5
On this page
§1The Idea
In OSPFv2 (RFC 2328) and OSPFv3, two neighboring routers that become adjacent synchronize their link-state databases through the Database Exchange process. Each sends Database Description (DD) packets listing the header of every LSA in its database, so the other can tell whether it has newer instances to request with Link State Request packets.
The optimization observes that a router need not list an LSA if the neighbor already has the same or a more recent instance, since the neighbor will not request it. The neighbor's own DD packets reveal this, so the LSA is dropped from the Database summary list when the neighbor listed an instance that is the same or newer.
If your friend already told you about a sticker and it is the same as yours, there is no need to tell them about it again.
§2The Change to Section 10.6
The memo modifies Section 10.6, "Receiving Database Description Packets", of RFC 2328. After the usual checks, for each listed LSA the router looks it up and, if it has none or an older copy, puts it on the Link state request list. The addition is that if the Database summary list holds an instance of the LSA that is the same as or less recent than the listed one, it is removed from the summary list.
This step may happen before or after the lookup, but it must be done for every LSA in a received DD packet before the next DD packet is sent in response.
LSAs need not be listed in any order, but a shared order may speed lookups. The memo recommends increasing lexicographic order of (LS type, Link State ID, Advertising Router) for OSPFv2 and (LS type, Advertising Router, Link State ID) for OSPFv3.
Each time you hear your friend's list, cross off anything on your own list that they already have the same or newer.
§3Example and Properties
In the memo's example, routers RT1 and RT2 start with identical databases whose headers fit in two DD packets. In the standard exchange each router sends two full DD packets. With the optimization, RT2 removes everything RT1 listed in its first full packet, then lists only the remaining LSAs. RT1 removes those, finds its list empty and sends an empty DD packet. Each router sends only one full DD packet instead of two.
The optimization is fully backward compatible with OSPF and does not affect synchronization, because only unnecessary information is omitted. It cuts the LSA headers exchanged by about half in large networks where routers are usually nearly synchronized when they become adjacent, and is especially beneficial in large networks with limited bandwidth, such as large mobile ad hoc networks.
The memo raises no new security concerns and needs no new IANA number assignments.
With the shortcut, each friend reads out one page of stickers instead of two, and they finish sooner.
| Exchange | Full DD packets per router |
|---|---|
| Standard | 2 |
| With optimization THIS RFC | 1 |