Internet Engineering Task Force M. Goyal
Internet-Draft University of Wisconsin Milwaukee
Intended status: Informational G. Choudhury
Expires: April 30, 2009 AT&T
A. Shaikh
AT&T - Research
K. Trivedi
Duke University
H. Hosseini
University of Wisconsin Milwaukee
October 27, 2008
LSA Correlation to Schedule Routing Table Calculations
draft-goyal-ospf-lsacorr-00
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/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on April 30, 2009.
Abstract
OSPF requires a router to recalculate its routing table whenever it
receives a new router or network LSA. However, a topology change,
such as a router down event, may cause a number of new LSAs to be
generated. These LSAs may arrive at a router at different times. In
order to avoid several routing table calculations in quick succession
Goyal, et al. Expires April 30, 2009 [Page 1]
Internet-Draft LSA Correlation October 2008
in such cases, commercial routers enforce a hold time between
successive routing table calculations. The hold time based schemes,
while limiting the number of routing table calculations, may also
cause undesirable delays in convergence to the topology change. This
ID describes an alternate approach to schedule routing table
calculations, called LSA Correlation. Rather than using individual
LSAs as triggers for routing table calculations, LSA Correlation
scheme correlates the information in the LSAs to identify the
topology change. A routing table calculation can be performed when
the topology change has been identified, which could span multiple
LSAs.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Requirements Language . . . . . . . . . . . . . . . . . . . . 3
3. LSA Correlation . . . . . . . . . . . . . . . . . . . . . . . 3
3.1. How to identify a topology change? . . . . . . . . . . . . 4
3.1.1. Identifying link/node down events . . . . . . . . . . 5
3.1.2. Identifying link/node up events . . . . . . . . . . . 6
3.2. Avoiding multiple routing table calculations for
multiple concurrent topology changes . . . . . . . . . . . 7
4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8
5. Security Considerations . . . . . . . . . . . . . . . . . . . 8
6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.1. Normative References . . . . . . . . . . . . . . . . . . . 8
6.2. Informative References . . . . . . . . . . . . . . . . . . 9
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 9
Intellectual Property and Copyright Statements . . . . . . . . . . 11
Goyal, et al. Expires April 30, 2009 [Page 2]
Internet-Draft LSA Correlation October 2008
1. Introduction
OSPF requires a router to recalculate its routing table whenever it
receives a new router or network LSA. However, a topology change,
such as a router down event, may cause a number of new LSAs to be
generated. These LSAs may arrive at a router at different times. In
order to avoid several routing table calculations in quick succession
in such cases, commercial routers enforce a hold time between
successive routing table calculations. The hold time based schemes,
while limiting the number of routing table calculations, may also
cause undesirable delays in convergence to the topology change. This
ID describes an alternate approach to schedule routing table
calculations, called LSA Correlation. Rather than using individual
LSAs as triggers for routing table calculations, LSA Correlation
scheme correlates the information in the LSAs to identify the
topology change. A routing table calculation can be performed when
the topology change has been identified, which could span multiple
LSAs.
The proposed LSA correlation scheme is based on the fact that a new
LSA is just a symptom of a topology change and hence should not be
used as the trigger for a routing table calculation. Rather, a
router should correlate the information in individual new LSAs to
identify the topology change itself and then perform a routing table
calculation.
2. Requirements Language
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 [RFC2119].
3. LSA Correlation
In the following, we discuss how to correlate the individual router
and network LSAs to identify the topology change(s). In this
discussion, we have used the term 'node' to refer to both a 'router'
and a 'transit network'. Also, any reference to scheduling an
'immediate' routing table calculation means that a routing table
calculation is performed after completing the processing of the
current 'Link State Update' packet.
The LSA correlation process consists of the following steps.
o Step 1: Identify an 'up', 'down' or 'cost change' subevent by
iterating through the contents of the new LSA and its old version.
Goyal, et al. Expires April 30, 2009 [Page 3]
Internet-Draft LSA Correlation October 2008
This step has O(k) running time complexity, where 'k' is the
number of link states contained in the LSA.
o Step 2: Correlate the subevents to identify a topology change.
This step has O(1) running time complexity for each subevent.
Every new router and network LSA needs to undergo this correlation
task with an overall running time complexity O(k). Here, 'k'
corresponds to the number of neighbors (routers and networks) of the
node originating the LSA, which is typically a small number. As
discussed later, the identification of a "node down" event requires
some additional processing with running time complexity O(k). Note
that the OSPFv2 specification [RFC2328] requires the new instance of
an LSA to be compared to the old instance to determine if a routing
table calculation is required. Hence, many OSPF implementations may
already be doing most of the processing required for LSA correlation.
Thus, the additional processing overhead of LSA Correlation procedure
should be insignificant.
+--------------------------+----------------------------------------+
| Link Type | Link States (LS) in an LSA |
+--------------------------+----------------------------------------+
| Point-to-point link | one type 3 LS |
| | one type 1 LS (after adj |
| | establishment) |
| Broadcast/NBMA link | one type 3 LS (before adj est.) |
| | one type 2 LS (after adj est.) |
| Point-to-multipoint link | one type 3 LS |
| | multiple type 1 LS (after adj est.) |
| Virtual link | one type 4 link state |
+--------------------------+----------------------------------------+
Table 1: Different Link Types in OSPF and the Corresponding Link
States in an LSA
3.1. How to identify a topology change?
In the following, we list typical topology changes and the criteria
for their identification.
o Link Down: A link can be declared \emph{down} if either end breaks
adjacency with the other.
o Link Up: A link can be declared \emph{up} if both ends establish
adjacency with each other.
o Node Down: A node can be declared \emph{down} if no node is
currently adjacent to it.
Goyal, et al. Expires April 30, 2009 [Page 4]
Internet-Draft LSA Correlation October 2008
o Node Up: A node can be declared \emph{up} if it has established
adjacency with all its known neighbors and all the neighbors have
also established adjacency with this node.
3.1.1. Identifying link/node down events
A "link down" event could be a part of a "node down" event. In case
of a "link down" event, both ends of the link will break adjacency
with each other and hence both ends will generate new LSAs. But for
a "node down" event, the down node will not generate a new LSA.
Hence, one way to distinguish a "link down" event from a "node down"
event is to wait for new LSAs from both ends of the link announcing
the breakdown of adjacency with each other. However, such a wait
will delay the convergence to the "link down" events, which
constitute the most common case of network failures.
We distinguish between "link down" and "node down" events as follows.
Consider two nodes 'A' and 'B' that are currently adjacent to each
other. Suppose no node has recently broken adjacency with node 'B'.
Further, suppose that node 'A' generates a new LSA that no longer
indicates an adjacency with node 'B'. Now, the topology change that
led to the generation of this LSA could be the failure of link 'A:B'
or the failure of node 'B' itself. In any case, we schedule an
immediate routing table calculation, thereby ensuring quick
convergence to a possible "link 'A:B' down" event. To prepare for
the possibility that node 'B' is down, we mark node 'B' as in the
process of "going down" and also decrement the number of
bidirectional adjacencies of both nodes 'A' and 'B'.
If node 'B' indeed went down, its other neighbors would also soon
generate LSAs indicating break down of their adjacency with node 'B'.
Suppose, we receive one such LSA from node 'C' showing that it is no
longer adjacent with node 'B'. This time, since node 'B' is marked
as "going down", a routing table calculation is not performed.
Rather, we decrement the count of the bidirectional adjacencies
associated with nodes 'B' and 'C' and wait for other nodes currently
adjacent to node 'B' to break their adjacency too. We also (re)start
a timer, called "doSPF". The purpose of the "doSPF" timer is to
assimilate all the pending LSAs into the routing table if the
topology change(s) can not be identified before the timer's firing.
The firing of this timer results in a routing table calculation. The
timer is stopped if a routing table calculation is performed while
the timer is running. Once no node is adjacent to node 'B' any more,
we schedule an immediate routing table calculation.
On the other hand, if node 'B' is not down, it will soon generate a
new LSA announcing the break down of its adjacency with node 'A'.
This LSA will cause node B's "going down" marking to be undone. This
Goyal, et al. Expires April 30, 2009 [Page 5]
Internet-Draft LSA Correlation October 2008
solution ensures that convergence to "link/node down" events is
quick. A "link down" event requires one routing table update while a
"node down" event requires two. In case node 'B' is down but it is
not possible to receive adjacency breakdown indications from all its
currently adjacent neighbors (because they are down too or they can
no longer be reached), a routing table calculation will be performed
when the "doSPF" timer fires.
On the identification of a "node down" event, all the adjacencies and
stub networks associated with the node are marked as down, which
requires iterating through the last LSA received from the down node
and has a time complexity of O(k), where 'k' is the number of link
states in the LSA. This is the additional processing required,
alluded to earlier, following the identification of a "node down"
event.
3.1.2. Identifying link/node up events
A "link up" event could be distinguished from a "node up" event by
checking whether both ends of the link are already "up" or not. Both
ends of the link would be "up" only in case of a pure "link up"
event. If either end of the link is not currently "up", the "link
up" event must be a part of a "node up" event. A node can be
declared to be "up" when it has established adjacency with all its
known neighbors, i.e., when the number of bidirectional adjacencies
for the node is same as the number of its neighboring nodes.
Suppose node 'A' generates an LSA that indicates a new adjacency with
node 'B'. If the last LSA from node 'B' did not indicate node 'A' as
adjacent, there is nothing to be done. Otherwise, we increment the
number of bidirectional adjacencies for nodes 'A' and 'B'. If both
nodes 'A' and 'B' are currently considered "up", we declare link
'A:B' as "up". Otherwise, we consider this adjacency establishment
as part of a node "up" event. If either node 'A' or node 'B' is
currently considered to be down, we check if its bidirectional
adjacency count is equal to the number of its known neighbors and if
so, we declare the node to be "up".
The number of neighbors for a node can be determined by examining the
node's LSA. Table Table 1 shows different types of OSPF links and
the information contained in an LSA for each link type in OSPF
version 2. Clearly, "max(type 3 link states, type 1/2/4 link
states)" gives the number of neighbors for the node originating the
LSA. We count only bidirectional adjacencies in the test for "node
up" event since, in OSPF, the routing table calculation uses only
those links where bidirectional adjacency exists between the two
ends.
Goyal, et al. Expires April 30, 2009 [Page 6]
Internet-Draft LSA Correlation October 2008
To deal with the possibility that a newly up node may not establish
adjacency with all its neighbors, we (re)start the "doSPF" timer when
a new bidirectional adjacency is identified. The expiry of the
"doSPF" timer will cause a routing table calculation, thereby
assimilating all the new LSAs received so far into the routing table.
The scheme, described above, can be referred to as "simple" LSA
correlation.
3.2. Avoiding multiple routing table calculations for multiple
concurrent topology changes
There are several scenarios where multiple topology changes take
place concurrently or in quick succession. For example, a cut in an
optical fiber would cause failure of all the IP links it carries. An
optical fiber is an example of a "shared risk link group" (SRLG),
which is defined as a group of links that share a common risk of
failure, i.e., all the links in the SRLG will fail if the risk
materializes. Another example is a "point of presence" (PoP), which
refers to a physical location where an Internet Service Provider
(ISP) locates the networking hardware such as routers. All the
routers in a PoP may fail together if a power failure affects the
entire PoP. If multiple topology changes occur in quick succession,
doing a new routing table calculation immediately on identifying a
topology change could lead to several back-to-back calculations in
the routers.
In order to avoid multiple routing table calculations in case of
multiple concurrent "node up/down" events, we propose the following
modification in the LSA correlation process: do not perform a routing
table calculation as long as some nodes are in the process of "going
down" or "coming up". As discussed earlier, a node is marked as
"going down" if atleast one neighbor has recently broken adjacency
with it. We need to additionally keep track of the nodes that are in
the process of "coming up". We can infer that a node is in the
processing of "coming up" if it originates a new LSA but has not
established adjacency with all its neighbors. When a node has
established adjacency with all its neighbors (i.e. is declared up),
its "coming up" marking is undone. Whenever a link/node "up" or
"down" event is identified, we schedule an immediate routing table
calculation only if no node is currently marked as "coming up" or
"going down".
To protect against pathological situations such as "link flaps" that
may keep one or more nodes in "coming up" or "going down" states
forever, a "pending" timer is (re)started every time a routing table
calculation is postponed in this manner. If some nodes are still in
the process of "coming up" or "going down" when this timer fires, a
Goyal, et al. Expires April 30, 2009 [Page 7]
Internet-Draft LSA Correlation October 2008
routing table calculation is performed to assimilate all recent
topology changes into the routing table. Note that this optimization
does not impact fast convergance to "isolated" link/node up/down
events. This scheme is referred to as "conservative" LSA
correlation.
Another optimization is to avoid routing table calculations while a
router is establishing adjacency with a neighbor. The correlation of
the LSAs received during the link state database exchange may cause
identification of several "topology changes". Thus, without this
optimization, a router may end up doing several routing table
calculations while establishing adjacency with a neighbor. Once the
adjacency establishment process is over, the two newly adjacent
routers will generate new LSAs, which when correlated will cause a
routing table calculation to take place.
Note that multiple routing table calculations in case of multiple
concurrent topology changes can also be avoided using a fixed/
exponential hold time based scheme. In such a scheme, individual
topology changes, identified via LSA correlation, could serve as the
triggers for driving the scheme's state machine. Further, it is
possible to identify and handle pathological conditions such as link
flaps using the "up/down" subevents generated during the LSA
correlation process. An implementation of the LSA correlation
process in a modified "ospfd" simulator is publically available
[newospfd].
4. IANA Considerations
This memo includes no request to IANA.
5. Security Considerations
TBD
6. References
6.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
Goyal, et al. Expires April 30, 2009 [Page 8]
Internet-Draft LSA Correlation October 2008
6.2. Informative References
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[newospfd]
Goyal, M., "A distributed OSPFD simulator", 2006,
<http://www.cs.uwm.edu/~mukul/newospfd.html>.
Authors' Addresses
Mukul Goyal
University of Wisconsin Milwaukee
3200 N Cramer St
Milwaukee, WI 53201
USA
Phone: +1 414 229 5001
Email: mukul@uwm.edu
Gagan Choudhury
AT&T
200 Laurel Avenue
Middletown, NJ 07748
USA
Phone: +1 732 420 3721
Email: gchoudhury@att.com
Aman Shaikh
AT&T - Research
180 Park Avenue
Florham Park, NJ 07932
USA
Phone: +1 973 360 7288
Email: ashaikh@research.att.com
Goyal, et al. Expires April 30, 2009 [Page 9]
Internet-Draft LSA Correlation October 2008
Kishor Trivedi
Duke University
Durham, NC 27708
USA
Phone: +1 919 660 5269
Email: kst@ee.duke.edu
Hossein Hosseini
University of Wisconsin Milwaukee
3200 N Cramer St
Milwaukee, WI 53201
USA
Phone: +1 414 229 5184
Email: hosseini@uwm.edu
Goyal, et al. Expires April 30, 2009 [Page 10]
Internet-Draft LSA Correlation October 2008
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.
Goyal, et al. Expires April 30, 2009 [Page 11]