Internet Draft Z. Zhang
Expiration Date: May, 1998 Bay Networks
File name: draft-zhang-ospf-dvl-01.txt November, 1997
Fixing Backbone Partition with Dynamic Virtual Links
Zhaohui Zhang
Bay Networks, Inc.
Status of this Memo
This document is an Internet-Draft. 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.''
To learn the current status of any Internet-Draft, please check
the ``1id-abstracts.txt'' listing contained in the Internet-
Drafts Shadow Directories on ftp.is.co.za (Africa),
nic.nordu.net (Europe), munnari.oz.au (Pacific Rim),
ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast).
Abstract
This document proposes a Dynamic Virtual Link (DVL) algorithm to
dynamically detect and fix OSPF backbone area partition.
In the DVL algorithm, each ABR periodically checks if it can reach
via backbone area all other ABRs that it can reach via its transit
areas. If not, it knows that a backbone partition has occurred and
a spanning tree of Dynamic Virtual Links are created. When the
DVLs are not needed, they are automatically deleted.
Zhang Expires May, 1998 [page 1]
Internet Draft Dynamic Virtual Links November, 1995
1. Introduction
Open Shortest Path First (OSPF) protocol requires that all Area
Border Routers (ABRs) be connected to a backbone area and that
the backbone area be contiguous. However, the protocol does not
try to detect and fix partitioned areas.
Virtual links can be used to provide or enhance backbone
connectivity. However, a lot of redundant virtual links have to
be used to ENSURE backbone connectivity and they introduce a
lot of overhead both in traffic and to the routers.
The author proposes that virtual links be made dynamic: they are
created when they are needed and destroyed when they are not
needed.
Supporting Dynamic Virtual Links (DVL) is optional.
1.1 Differences from previous version
1. The "spanning tree center" is no longer "elected" and
"maintained". The "center" is now always the router with
the highest ID.
2. To detect redundant DVLs, routers now run a special Dijkstra
in the backbone area, using tie-breakers similar to those in
MOSPF, instead of depending upon random timers to avoid
thrashing.
3. A configurable area parameter is added to control whether
DVLs are allowed through a transit area.
2. Dynamic Virtual Links
2.1 Detect Backbone Partition
Since each router maintains a routing table in each area for all
ABRs in that area, the backbone partition can be easily detected:
if an ABR discovers that it can reach another ABR via a transit
area, but it can not reach the ABR via the backbone area, then it
knows that there is a backbone partition and DVLs need to be
created to fix the partition.
2.2 Spanning Tree of DVLs
It is not necessary that a DVL be created between each pair of
ABRs that can not reach each other via the backbone area.
In Figure 1, the ABRs in a transit area are divided into disjoint
groups (shown as blocks): ABRs (shown as "o" in the blocks) in a
group can reach each other via the backbone area, but they can not
reach ABRs outside the group via backbone. A star-shaped spanning
Zhang Expires May, 1998 [page 2]
Internet Draft Dynamic Virtual Links November, 1995
tree (see 5.2 of [2]) that connects the groups is enough: a chosen
ABR in a leaf group creates a DVL to a chosen ABR in the center
group B if it cannot reach the chosen ABR in the center via the
backbone, and deletes the DVL when it is not needed to reach the
ABR in the center. The chosen ABR in the center is passive and
dynamically creates a DVL when it receives the first Hello packet
from a new virtual neighbor with lower ID.
The chosen ABR in a center group is hereafter called a center.
Previously disjoint groups merge into one group after adjacencies
on their DVLs to the center have been established. However, this
does not change anything. A group can also split, and a chosen ABR
in each subgroup will have a DVL to the center.
+------+ +------+
++==+ o o +==============+ o +==+
// | o o | DVL | o o | \\
// | o o +--------------+ o o | \\
// +------+ /+----+-+ \\
++ A / B | ++
|| / | ||
|| transit area / DVL | ||
++ / DVL | ++
\\ C / D | //
\\ +------+ / +----+-+ //
\\ | o | | o o | //
++==+ +==============+ +==++
| o o | ^ | o o |
+------+ | +------+
|
transit area border
Figure 1. Disjoint groups of ABRs
The spanning tree needs not to be a Minimum Weight Spanning Tree
(MST) (see 5.2.2 of [2]):
1. A distributed MST algorithm requires exchange of cost
information among the ABRs, which can cause extra routing
traffic and longer convergence time.
2. A MST needs to be reformed whenever there is a topology
change in the transit area, which again leads to more
traffic and longer convergence time.
3. Even if a nonoptimal spanning tree of virtual links is used,
the route calculation will still result in shortest path
trees for the ABRs (see 16.3 of [1]).
The spanning tree is formed per transit area, but some tie-
breakers make sure that there will be no redundant DVLs formed
or kept in all areas (see 3.2.2 & 3.3).
Zhang Expires May, 1998 [page 3]
Internet Draft Dynamic Virtual Links November, 1997
The center could change when more ABRs join the transit area.
It is always the router with the highest ID in a transit area.
However, existing DVLs to old centers are not affected by a
new center.
Note that if a DVL is already established for a group, when
another ABR with higher Router ID joins the group, it does not
create another DVL because it can reach the center via the
existing DVL.
2.3 Detect/delete Redundant DVLs
Some DVLs become redundant when the original backbone connection
failures are fixed. Sometimes redundant DVLs could be created due
to the distributed nature of the algorithm. Redundant DVLs should
be deleted.
Note that the deleting of a redundant DVL is only initiated by the
router that initiated the DVL when the router was a leaf.
To find out if a DVL initiated by the router is redundant, the router
runs a Dijkstra in the backbone area, rooting the tree at the router
with the highest ID of those reachable in the backbone area.
Tie-breaks similar to those in MOSPF are used to ensure that all ABRs
get the same shortest path trees rooting at the highest ID router,
so that they agree which DVLs are redundant.
3. Implementation Details
3.1 A Functionality Bit -- D-bit
A new functionality bit, D-bit, is used in Router LSAs to indicate
that a router supports DVL in the area, as shown in Figure 2.
0 1 2 3
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ |
| Router LSA Header |
+ |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 0 |D|W|V|E|B| 0 | # links |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Data |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
Figure 2. Functionality bits
Zhang Expires May, 1998 [page 4]
Internet Draft Dynamic Virtual Links November, 1997
3.2 Detect and Fix Possible Backbone Partition
The following procedure is taken by an ABR for a transit area
whenever:
a. there is a topology change (indicated by new Router/Net LSAs)
in the backbone area.
b. there is a topology change in the transit area.
1. Find out current center C, which is the ABR with the highest ID
of those with the D-bit set in their Router LSAs and reachable in
the transit area.
Find out the ABR with the highest ID of those with the D-bit
set in their Router LSAs and reachable via the backbone area,
calling it L.
2. create a DVL to the center if all the following three conditions
are met:
a. this router is L but not the current center C
b. it can not reach the center C via the backbone
c. there is not another transit area with a higher area ID,
via which the center can be reached
3.3 Detect/Delete Redundant DVLs
If a router has active DVLs (with neighbors fully adjacent over the
DVLs) initiated by itself, the following procedure is taken in the
backbone area when there is a topology change in the backbone area
and there is no partition in the backbone area after the change.
1. Find out the router H with the highest ID of those reachable in the
backbone area, whether the D-bit is set in their Router LSAs or not.
2. With H's Router LSA as the root, do a Dijkstra in the backbone area
with the following special process:
a) Use tie-breakers similar to those in MOSPF (see step (2)(d) in
Section 16.1, RFC 2178).
b) When a vertex is moved from the candidate list to the SPF
tree, if the link between its parent and itself is a DVL
initiated by this router, mark it as "needed".
3. Delete those DVLs that are initiated by the router and not marked
as "needed".
Because of the tie-breakers all DVL routers will build the same
tree so they will agree on which DVLs are redundant. Note that
DVLs that are not absolutely needed but do lead to optimal paths
are not deleted.
Zhang Expires May, 1998 [page 5]
Internet Draft Dynamic Virtual Links November, 1997
Before a DVL is deleted, if the associateed neighbor is in state
N2WAY or higher, the router should send a Hello packet with no
listed neighbor over the DVL, so that the neighbor can immediately
drop its adjacency with this router and delete the DVL from its end.
4. Discussions
4.1 Performance
The backbone partition detecting/fixing procedure is taken for a
transit area only when there is a topology change in the backbone
area or in the transit area; the procedure for detecting/deleting
redundant DVLs is taken only for the backbone area when there are
DVLs initiated by this router and there is a topology change in
the backbone area and there is no backbone partition after the
change.
Therefore, the algorithm does not introduce much extra load.
4.2 Spanning tree center/leaf determination
The algorithm relies on the routers that have the highest IDs of
all ABRs in a transit area or of all ABRs reachable via backbone.
If each ABR, instead of only the one with the highest ID of all ABRs
reachable via backbone, creates a DVL to the center, there will be
some redundant DVLs being created and then deleted, causing extra
traffic and routing oscillation.
5. Configurable Area Parameters
DVLEnabled
Control whether DVLs are allowed through this transit area.
DVLRxmtInterval
DVLInfTransDelay
DVLHelloInterval
DVLRouterDeadInterval
DVLAuType
DVLAuthKey
Zhang Expires May, 1998 [page 6]
Internet Draft Dynamic Virtual Links November, 1997
6. Acknowledgement
Special thanks goes to John Moy. This document and related work
could not have been finished without help from him.
In fact, John had his DVL idea in
his mind too when the author's was brought up to him. He also
pointed out some holes and gave some suggestions, such as on
spanning tree, eliminating center election in version 0, and the
logic for deleting DVLs, which are very important in the DVL
algorithm.
A special thanks also goes to Rob Coltun, whose OSPF simulator
made it possible to implement and test the DVL algorithm in draft
version 0.
The initial work and versions of this document were finished
while the author was working in the IP/Routing Consortium,
InterOperability Laboratory (http://www.iol.unh.edu), University
of New Hampshire.
7. Author's Address
Zhaohui Zhang
Bay Networks, Inc.
600 Technology Park
Billerica, MA 01821
Email: zzhang@baynetworks.com
Phone: (978) 916-8225
Fax: (978) 670-8760
Reference
[1] John Moy, "OSPF Version 2", RFC2178, July 1997
[2] Dimitri Bertsekas and Robert Gallager, "Data Networks",
Prentice-Hall, Inc., 1992.
[3] John Moy, "Multicast Extension to OSPF", RFC 1584, March 1994.
This document expires in May, 1998.