Internet DRAFT - draft-choudhury-manral-flooding-simulation
draft-choudhury-manral-flooding-simulation
Internet Engineering Task Force Gagan L. Choudhury
Internet Draft AT&T
Expires in May, 2003
draft-choudhury-manral-flooding-simulation-00.txt
Vishwas Manral
Netplane Systems
November, 2002
LSA Flooding Optimization Algorithms and Their Simulation Study
Status of this Memo
This document is an Internet-Draft and is in full conformance
with all provisions of Section 10 of RFC2026.
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.
Distribution of this memo is unlimited.
Abstract
The full flooding of LSAs in OSPF may cause large CPU and memory
consumption at node processors of a network with large number of nodes,
links, adjacencies per node and LSDB size. An LSA storm, defined as
the near-simultaneous update of a large number of LSAs, in such
networks may cause network instability and outage.
We do a simulation study of four alternative algorithms to full
flooding to determine their ability to handle large LSA storms.
Algorithm 2 does full flooding but in case two neighbors are connected
by multiple interfaces, flooding is done over only one such interface.
The other algorithms are based on Algorithm 2 and employ
further flooding restrictions. In Algorithm 3 each node asks only
a subset of its one-hop neighbors, known as multipoint relays, to
flood further. In Algorithm 4 flooding is done only over a
Choudhury et. al. [Page 1]
Internet Draft Flooding Simulation May, 2003
minimum spanning tree. Algorithm 5 uses full flooding (as in Algorithm
2) for LSAs carrying intra-area topology information and restricted
flooding over a minimum spanning tree (as in Algorithm 4) for other
LSAs.
In terms of handling large LSA storms and in terms of robustness under
link failures, it appears that Algorithms 2 and 5 are the most
desirable ones and it is proposed that they be pursued further.
1. Introduction
In OSPF, LSAs (Link-State-Advertisements) received at a node
(router) are flooded over all interfaces except the one it came over.
This full flooding adds a lot of redundancy and ensures that LSAs do
reach all intended destinations reliably and quickly. However, this
may also consume a large amount of CPU and memory resources at the
node processors of a large network (largeness in terms of number of
nodes, number of links, adjacencies per node, and LSA Database size).
This is particularly true in the case of a LSA storm, which we define
as the simultaneous or near-simultaneous update of a large number of
LSAs. An LSA storm may be caused by (a) one or more link failures due
to fiber cuts, (b) one or more node failures for some reason, e.g.,
software crash or some type of disaster in an office complex hosting
many nodes, (c) requirement of taking down and later bringing back
many nodes during a software/hardware upgrade, (d) near-
synchronization of the once-in-30-minutes refresh instants of a subset
of the LSAs, (e) refresh of all LSAs in the system during a change in
software version.
If the CPU utilization at a node stays high for a
long time then that may result in many retransmissions (retransmission
timer is typically 5 seconds) and may also result in links being
declared down due to missed Hello packets (Router-Dead interval is
typically 40 seconds). The above events would be reinforced in the
case of heavy memory utilization and dropped packets. If a link is
declared down then that would generate additional LSAs to carry the
link-down information and if it results in rerouting of MPLS LSPs then
that may generate further LSAs carrying traffic-engineering information.
Eventually when the link comes back up, further LSAs would be generated
again to carry the link-up information and potentially LSAs carrying
traffic-engineering information due to a possible reroute of MPLS LSPs.
The retransmissions and additional LSA generations result in further
CPU and memory usage, essentially causing a positive feedback loop.
We define the LSA storm size as the number of LSAs in the original
storm and not counting any additional LSAs resulting from the feedback
loop described above. If the LSA storm is too large then the positive
Choudhury et. al. [Page 2]
Internet Draft Flooding Simulation May, 2003
feedback loop mentioned above may be large enough to indefinitely
sustain a large CPU and memory utilization at many network nodes,
thereby driving the network to an unstable state.
In the past, network
outage events have been reported in IP and ATM networks using
link-state protocols such as OSPF, IS-IS, PNNI or some proprietary
variants. See, for example [Ref1-Ref4]. In many of these examples,
large scale flooding of LSAs or other similar control messages (either
naturally or triggered by some bug or inappropriate procedure) have
been partly or fully responsible for network instability and outage.
In this contribution we consider several alternatives to the basic full
flooding algorithm in order to significantly increase the LSA storm
threshold that can cause network instability. Ideally, the LSA storm
threshold should be the same as the full LSDB (LSA Database) size since
normally this is the upper limit of the number of LSAs that can be
present in a LSA storm.
One of the algorithms we consider is similar in spirit to flooding
optimization mechanisms proposed in the past [Ref5,Ref6]. Also, our
work is synergistic with a broader set of scalability and stability
improvement proposals. [Ref7] proposes a mechanism for greatly
reducing LSA refreshes in stable topologies. [Ref8] proposes
prioritization of certain critical OSPF packets (e.g., Hellos and
LSA Acknowledgements) in order to ensure that links are not declared
down due to missed hellos and retransmission traffic is reduced
during periods of congestion. [Ref9] proposes a wide range of
congestion control and failure recovery mechanisms.
2. The Flooding Algorithms
All algorithms we describe in this Section are applicable to a single
OSPF Area. If there are multiple areas then the same flooding
algorithm may be run independently and in parallel within each area.
Algorithm 1 (Full Flooding): LSAs are flooded over all interfaces just
as in RFC 2328.
Algorithm 2 (Flooding over one of many parallel links between
neighbors): If two routers are connected by multiple parallel point-
to-point links then flooding is done over only one such link. If the
link designated for flooding goes down and at least one other parallel
link is still up then a different parallel link is designated for
flooding. Mechanisms similar in spirit to this were proposed in
[Ref5,Ref6]. PNNI, a Link-state protocol
Choudhury et. al. [Page 3]
Internet Draft Flooding Simulation May, 2003
used in ATM networks also uses a similar mechanism [Ref10].
(It is also to be
noted that other variants are possible. For example, LSAs may be
scheduled for transmission over all interfaces to a neighbor but with
random delays and as soon as an acknowledgement is received, the
remaining transmissions are disabled. For the purpose of simulation
we stick to the basic mechanism described by the first two
sentences of the algorithm description)
Algorithm 3 (Flooding over one of many parallel links between
neighbors plus Multipoint Relays): In addition to the flooding
restrictions in Algorithm 2 (i.e., if there are multiple parallel
links to an immediate neighbor then only one is used for flooding),
we also introduce a further restriction by using the distributed
multipoint relay mechanism. For a given node x, we define N1(x) as
the set of its immediate or one-hop neighbors. We also define N2(x),
the set of two-hop neighbors of x, as the set of nodes that are not
a one-hop neighbor of x but are a one-hop neighbor of at least one
member of N1(x). A subset of N1(x) whose one-hop neighbors include
all two-hop neighbors of x, i.e., all members of N2(x), is defined
as M(x), the "Multipoint Relay Set" of node x.
As node x floods an
LSA to its one-hop neighbors, it asks only the multipoint relays to
flood further. A one-hop neighbor of x that is not one of its
multipoint relays, i.e., does not belong to M(x), would receive the
LSA and acknowledge it but would not retransmit it any further. A
one-hop neighbor of x that is one of its multipoint relays, i.e.,
belongs to M(x), would flood further using the same algorithm, i.e.,
it will flood to all its one-hop neighbors (except Node N1) and ask
only its multipoint relays to flood further. This is a distributed
algorithm in the sense that each node determines the set of its
multipoint relays independent of the selection process at any other
node.
If for all node x, the set of multipoint relays is the same
as the set of all one-hop neighbors then Algorithm 3 would be
identical to Algorithm 2. In general, however, it would be possible
to choose a multipoint relay set that is smaller than the set of all
one-hop neighbors. Finding an optimal multipoint relay set has large
computational complexity and so we choose the following near-optimal
heuristic algorithm.
Step 1: Include a one-hop neighbor (say y) of x as part of M(x) if
there exists at least one member of N2(x) who has y as its only one-hop
neighbor in the set N1(x). Keep repeating this process until no more
one-hop neighbor y with above-mentioned property exists.
Choudhury et. al. [Page 4]
Internet Draft Flooding Simulation May, 2003
Step 2: If all nodes in N2(x) are covered as one-hop neighbors of
members of M(x) then stop. Otherwise, choose a member of N1(x) - M(x)
as a new member of M(x) which covers as one-hop neighbors the maximum
number of previously uncovered members of N2(x). Keep repeating this
step until all members of N2(x) are covered at which point the
selection of the multipoint relay set M(x) is complete.
For every node x in the network, perform the multipoint relay set
selection process in parallel and independently.
The multipoint relay
mechanism has been proposed for use in Mobile Wireless networks
[Ref11].
Algorithm 4 (Flooding over one of many parallel links between neighbors
plus flooding over a minimum spanning tree): In addition to the
flooding restrictions in Algorithm 2 (i.e., if there are multiple
parallel links to an immediate neighbor then only one is used for
flooding), we also introduce a further restriction by developing a
minimum spanning tree that connects all nodes and flooding only over
the minimum spanning tree. It is possible to create a tree spanning
all network nodes in a given area in many ways.
We create a spanning
tree with the objectives of minimizing the maximum delay between any
two network nodes in a given area and restricting the adjacency at a
node in the spanning tree to no more than a certain maximum value
adjmax. The first objective is to minimize the LSA convergence time
and the second objective is to reduce the impact of LSA storm on nodes
since the node with the highest adjacency is impacted the most. For
delay between two nodes we use just the sum of the propagation and
processing delays along the spanning tree between the source and the
destination. Other delay components such as queueing delays and
scheduling delays are not considered since they are dependent on the
traffic load, exact LSA generation time, etc. and difficult to
estimate for the purpose of optimization (these quantities are
nevertheless computed exactly as part of the simulation model to be
described later). Note that only a subset of the adjacencies are on
the spanning tree (also no more than one between immediate neighbors)
and only the sum of those is not to exceed adjmax.
We develop the following heuristic algorithm. Build the spanning tree
sequentially starting from a single node that is nearest to the
geographic center of the network area. In each stage add that link
and associated node to the tree that would minimize the maximum delay
(along the spanning tree) from the new node to any other node in the
existing spanning tree but with the restriction that the adjacency of
any node cannot exceed adjmax. (We have seen that a spanning tree
generated using this algorithm can have significantly lower maximum
Choudhury et. al. [Page 5]
Internet Draft Flooding Simulation May, 2003
end-to-end delay between nodes compared to a randomly generated
spanning tree with the same adjmax value).
After the formation of a spanning tree if a link on the spanning tree
goes down then it is replaced with a parallel link between the same
set of nodes, if any such exists. If no such parallel link exists then
the spanning tree is to be recomputed. The spanning tree
re-computation is also needed in the case of failure of a node on the
spanning tree. The spanning tree computation/re-computation may be
done independently at each node in a distributed fashion but using the
same algorithm, or it may be computed at one node and flooded to the
whole network periodically using Algorithm 2.
Algorithm 5 (Flooding over one of many parallel links between neighbors
for all LSAs plus flooding over a minimum spanning tree for LSAs that
do not carry intra-area topology information): This algorithm is a
hybrid between Algorithms 2 and 4. For LSAs that carry intra-area
topology information (e.g., Router and Network LSAs), flooding is done
as in Algorithm 2. We call these Type A LSAs. For LSAs that do not
carry area topology information, flooding is done as in Algorithm 4
and we call them Type B LSAs. It is to be noted that since Type A and
Type B LSAs are flooded differently, they should not be packed as part
Of the same LSU. Examples of Type B LSAs include ASE LSA,
summary LSA and ASBR-summary LSA. Another example may be Opaque LSAs
used to carry link bandwidth information as used in the Traffic
Engineering extension of OSPFV2 [Ref12].
The reason for introducing Algorithm 5 is that
in order to compute the minimum spanning tree (and re-compute it
under link/node failure) we need the intra-area topology information.
If we also rely on the minimum spanning tree to get the topology
information, as in Algorithm 4, then it may be difficult to get an
accurate picture of the topology under the failure of the minimum
spanning tree. In Algorithm 5, however, the topology information that
is needed to compute/re-compute the minimum spanning tree is
distributed using the more robust Algorithm 2 and so even if some
links/nodes of the minimum spanning tree fails but the rest of the
network remains connected then the topology information would be
accurately carried to all network nodes in the area and it would be
possible to re-compute the minimum spanning tree.
On the other hand,
Algorithm 4 is less message intensive compared to Algorithm 2 and Type
B LSAs can benefit from this reduced amount of messaging. In many
situations Type B LSAs may be many more in number compared to Type A
LSAs. In one example there may be many more ASE, Summary and
ASBR-Summary LSAs compared to Router and Network LSAs. In another
example, if a traffic-engineering-related Opaque LSA is used for each
Choudhury et. al. [Page 6]
Internet Draft Flooding Simulation May, 2003
direction of each link of the network then there would typically be
many more LSAs of this type compared to Router and Network LSAs.
Algorithm 5 has the same amount of robustness as Algorithm 2 for
Carrying topology-related information but it can be far less
message-intensive if majority of the LSAs are of Type B.
3. The Network under Simulation
We generate a random network over a rectangular grid using a modified
version of Waxman's algorithm [Ref13] that ensures that the network is
connected and has a pre-specified number of nodes, links, maximum
number of neighbors per node,
and maximum number of adjacencies per node. The rectangular grid
resembles the continental U.S.A. with maximum propagation delay of
30 ms in the East-West direction and maximum propagation delay of
15 ms in the North-South direction. We consider two different
network sizes as explained in Section 4.
The network has a flat, single-area topology.
Each node is a Router and each link is a point-to-point link
connecting two routers.
We assume that node CPU and memory (not the link bandwidth) is the main
bottleneck in the LSA flooding process. This will typically be true
for high speed links (e.g., OC3 or above) and/or links where OSPF
traffic gets an adequate Quality of Service (QoS) compared to other
traffic.
Different Timers (usually default values): LSA refresh interval =
1800 seconds, Hello refresh interval = 10 Seconds, Router-Dead
interval = 40 seconds, LSA retransmission interval = 5 Seconds (note
that a retransmission is disabled on the receipt of either an
explicit acknowledgment or a duplicate LSA over the same interface
that acts as an implicit acknowledgment),
Minimum Time Between generation of the same LSA = 5 Seconds, Minimum
time between successive Dijkstra SPF calculations is 1 second.
Packing of LSAs: It is assumed that for any given node, the LSAs
generated over a 1-second period are packed together to form an LSU
but no more than 3 LSAs are packed in one LSU.
LSU/Ack/Hello Processing Times: All processing times are expressed in
terms of the parameter T. Different values of T in the range of 0.5 ms
to 2 ms are considered.
In the case of a dedicated processor for processing OSPF packets the
Choudhury et. al. [Page 7]
Internet Draft Flooding Simulation May, 2003
processing time reported represents the true processing time. If the
processor does other work and only a fraction of its capacity can be
dedicated to OSPF processing then we have to inflate the processing
time appropriately to get the effective processing time and in that
case it is assumed that the inflation factor is already taken into
account as part of the reported processing time.
The fixed time to send or receive any LSU, Ack or Hello packet is T.
In addition, a variable processing time is used for LSU and Ack
depending on the number and types of LSAs packed. No variable
processing time is used for Hello.
Variable processing time per Router LSA is (0.5 + 0.17L)T where L is
the number of adjacencies advertised by the Router LSA. For other
LSA types (e.g., ASE LSA or a "Link" LSA carrying traffic engineering
information about a link), the variable processing time per LSA is
0.5T.
Variable processing time for an Ack is 25% that of the corresponding
LSA.
It is to be noted that if multiple LSAs are packed in a single LSU
packet then the fixed processing time is needed only once but the
variable processing time is needed for every component of the packet.
LSU/Ack/Hello Priority: All LSUs/Acks/Hellos received at a node are
queued at the same priority and processed in a FIFO manner. Any
packets generated internally to a node and usually based on a timer
are processed at a higher priority. This includes the initial LSA
storm, LSA refresh, Hello refresh, LSA retransmission and new LSA
generation after detection of a failure or recovery.
Buffer Size for Incoming LSUs/Acks/Hellos: Buffer size is assumed
to be 2000 packets where a packet is either an incoming LSU, Ack or
Hello. The buffer is managed in a FIFO manner and when the buffer is
full, new packet arrivals are dropped.
Processing Time for MPR/MST computation at a node (Algorithms
3, 4 and 5): 10 ms. This is needed once in the beginning and
otherwise only when the last live link between a pair of nodes in the
network goes down.
LSA Refresh: Each LSA is refreshed once in 1800 seconds and the
refresh instants of various LSAs in the LSDB are assumed to be
uniformly distributed over the 1800 seconds period, i.e., they are
completely unsynchronized. If however, an LSA is generated as part
of the initial LSA storm then it goes on a new refresh schedule of
once in 1800 seconds starting from its generation time.
LSA Storm Generation: As defined earlier, "LSA storm" is the
Choudhury et. al. [Page 8]
Internet Draft Flooding Simulation May, 2003
simultaneous or near simultaneous generation of a large number of LSAs.
In the case of only Router and ASE LSAs we normally assume that the
number of ASE LSAs in the storm is about 4 times that of the Router
LSAs, but the ratio is allowed to change if either the Router or the
ASE LSAs have reached their maximum possible value. In the case of
only Router and Link LSAs (carrying traffic engineering information)
we normally assume that the number of Link LSAs in the storm is about
4 times that of the Router LSAs, but the ratio is allowed to change
if either the Router or the Link LSAs have reached their maximum
possible value. For any given LSA storm we keep generating LSAs
starting from Node index 1 and moving upwards and stop until the
correct number of LSAs of each type have been generated. The LSAs
generated at any given node is assumed to start at an instant
uniformly distributed between 20 and 30 seconds from the start of the
simulation. Successive LSA generations at a node are assumed to be
spaced apart by 400 ms. It is to be noted that during the period of
observation there are other LSAs generated besides the ones in the
storm. These include refresh of LSAs that are not part of the storm
and LSAs generated due to possible link failures and subsequent
possible link recoveries.
Failure/Recovery of Links: If no Hello is received over a link (due to
CPU/memory congestion) for longer than Router-Dead Interval then
the link is declared down. At a later time, if Hellos are received
then the link would be declared up. Whenever a link is declared
up or down, one Router LSA is generated by each Router on the
two sides of the point-to-point link. If "Link LSAs" carrying
traffic engineering information is used then it is assumed that each
Router would also generate a Link LSA. In this case it is also assumed
that due to rerouting of LSPs, one other link in the network
(selected randomly in the simulation) would have significant change
in reserved bandwidth which would result in one Link LSA being
generated by the routers on the two ends of the link.
4. Simulation Results
In this section we study the relative performance of the five
algorithms with a range of Network sizes, LSA types, and processing
time values as explained below:
Network size: Two networks are considered. Network 1 has 100 nodes,
1200 links, maximum number of neighbors per node is 30 and maximum
number of adjacencies per node is 50 (same neighbor may have more
than one adjacencies). Network 2 has 50 nodes, 600 links, maximum
number of neighbors per node is 25 and maximum number of adjacencies
per node is 48. Dijkstra SPF calculation time for Network 1 is assumed
to be 100 ms and that for Network 2 is assumed to be 70 ms.
Choudhury et. al. [Page 9]
Internet Draft Flooding Simulation May, 2003
LSA Type: Each node has 1 Router LSA (Total of 100 for Network 1 and
50 for Network 2). There are no Network LSAs since all links are point-
to-point links and no Summary LSAs since the network has only one area.
Regarding other LSA types we consider two scenarios. In Scenario 1 we
assume that there are no ASE LSAs and each link has one "Link" LSA
carrying traffic engineering information (Total of 2400 for Network 1
and 1200 for Network 2). In Scenario 2 we assume that there are no
"Link" LSAs and half of the nodes are ASA-Border nodes and each border
node has 10 ASE LSAs (Total of 500 for Network 1 and 250 for
Network 2). We identify Scenario 1 as "Link LSAs" and Scenario 2 as
"ASE LSAs".
Processing time values: Processing times for LSUs, Acks and Hello
packets have been previously expressed in terms of a common parameter
T. Three values are considered for T, which are 1 ms, 0.5 ms and 2 ms
respectively.
Based on Network size, LSA type and Processing time values we develop
5 Test cases as follows:
Case 1: Network 1, Link LSAs and T = 1 ms.
Case 2: Network 1, ASE LSAs and T = 1 ms.
Case 3: Network 1, Link LSAs and T = 0.5 ms.
Case 4: Network 1, Link LSAs and T = 2 ms.
Case 5: Network 2, Link LSAs and T = 1 ms.
For each case and for each algorithm we study the network stability as
=========|==========================================================
| Number of Non-Converged LSUs in the Network at Time(in sec)
LSA |
STORM |==========================================================
SIZE |10s 20s 30s 35s 40s 50s 60s 80s 100s
=========|==========================================================
50 | 0 0 9 10 0 0 0 0 1
(Stable)|
---------|----------------------------------------------------------
100 | 0 0 24 29 26 21 8 1 1
(Stable)|
---------|----------------------------------------------------------
130 | 0 0 31 45 42 41 38 127 237
(Unstable)
=========|==========================================================
Table 1: Network Stability Vs. LSA Storm (Case 1, Algorithm 1)
Choudhury et. al. [Page 10]
Internet Draft Flooding Simulation May, 2003
a function of the size of the LSA storm. The stability is determined
by looking at the number of non-converged LSUs as a function of time.
An example is shown in Table 1 for Case 1 and Algorithm 1.
The LSA storm starts a little after 20 seconds and so for some period
of time after that the
number of non-converged LSUs should stay high and then come down for a
stable network. This happens for LSA storms of sizes 50 and 100. With
an LSA storm of size 130, the number of non-converged LSAs stay high
indefinitely due to repeated retransmissions, link failures due to
missed Hellos for more than the Router-Dead interval which generates
additional LSAs and also due to subsequent link recoveries which again
generate additional LSAs. It turns out that for this example the
maximum LSA storm size that still keeps the network stable is 115.
|===========|========================================================|
| | Maximum Allowable LSA Storm Size For |
|Algorithm |==========|==========|===========|==========|===========|
| Type | Case 1 | Case 2 | Case 3 | Case 4 | Case 5 |
| |(Net. 1, | (Net. 1, | (Net. 1, | (Net. 1, | (Net. 2, |
| |Link LSAs,| ASE LSAs,| Link LSAs,|Link LSAs,| Link LSAs,|
| | T = 1 ms)| T = 1 ms)|T = 0.5 ms)| T = 2 ms)| T = 1 ms) |
|===========|==========|==========|===========|==========|===========|
|Algorithm 1| 115 | 130 | 275 | 25 | 138 |
|(Full Fld.)| | | | | |
|___________|__________|__________|___________|__________|___________|
|Algorithm 2| | | | | |
|(Fld. Over | 238 | 243 | 610 | 85 | 450 |
|One Parall.| | | | | |
| Link) | | | | | |
|___________|__________|__________|___________|__________|___________|
|Algorithm 3| | | | | |
|(Alg. 2 + | 248 | 249 | 645 | 90 | 450 |
|Multipoint | | | | | |
|Relay) | | | | | |
|___________|__________|__________|___________|__________|___________|
|Algorithm 4| | | | | |
| (Alg. 2 + | Full LSDB| Full LSDB| Full LSDB | 1825 | Full LSDB |
|Fld. Over | (2500) | (600) | (2500) | | (1250) |
|Span. Tree)| | | | | |
|___________|__________|__________|___________|__________|___________|
|Algorithm 5| | | | | |
|(Alg. 2 For| Full LSDB| Full LSDB| Full LSDB | 625 | Full LSDB |
|Type A, Alg| (2500) | (600) | (2500) | | (1250) |
|4 For Type | | | | | |
|B LSAs | | | | | |
|___________|__________|__________|___________|__________|___________|
Table 2: Maximum Allowable LSA Storm for a Stable Network
Choudhury et. al. [Page 11]
Internet Draft Flooding Simulation May, 2003
This stability threshold depends on the Case and the Algorithm under
consideration. A better algorithm should allow a higher stability
threshold.
In Table 2 we show the maximum allowable LSA storm size that would
still keep the network stable for the five different cases and for
the five different algorithms.
5. Summary of Observations
Comparison of Algorithm 2 and Algorithm 1: We observe that in all
cases in Table 2, Algorithm 2 substantially increases (usually by a
factor of two or more) the maximum LSA storm threshold of the network
compared to Algorithm 2. This implies that flooding over only one of
many parallel links between nodes has clear beneficial impact in terms
of improving network scalability and stability and ought to be pursued.
Comparison of Algorithm 3 and Algorithm 2: The Multipoint relay
mechanism used in Algorithm 3 increases the LSA storm threshold
(compared to Algorithm 2)
but by a moderate amount. One reason for this moderate improvement
is that even though the multipoint relay mechanism can significantly
reduce the overall amount of flooding in the network, it appears that
the nodes with highest number of neighbors tend to be more likely
to be chosen as multipoint relays by their neighbors. As an example,
in Network 1 (Cases 1-4 in Table 2) on the average a node chooses
70% of its neighbors as multipoint relays. However, the node with
highest number of neighbors (30), is chosen as a multipoint relay
by 27 out of the 30 (i.e., 90%) of its neighbors. This node, due
to its large number of neighbors, also happens to be the bottleneck
in terms of determining LSA storm threshold and since its effective
number of neighbors (the ones that ask it to flood further) goes
down only slightly, the overall improvement in LSA storm threshold
is moderate. In Network 2 (Case 5 in Table 2) all neighbors of the
highest adjacency node elect this node as multipoint relays and
therefore there is no improvement in LSA storm threshold.
Comparison of Algorithm 4 and Algorithm 2: Compared to Algorithm 2,
Algorithm 4 always raises the LSA storm threshold substantially and
in four out of the five cases the LSA storm threshold is raised to
its maximum value, i.e., it is OK to flood all LSAs in the LSDB over
a short period of time. However, one issue with Algorithm 4 is that
if a link on the minimum spanning tree fails, many nodes may not get
the required LSAs carrying the topology information and it would be
difficult for them to recompute the new minimum spanning tree. In the
simulation we re-computed the minimum spanning tree based on global
knowledge under failure conditions.
Comparison of Algorithm 5 and Algorithm 2: Compared to Algorithm 2,
Algorithm 5 always raises the LSA storm threshold substantially and
Choudhury et. al. [Page 12]
Internet Draft Flooding Simulation May, 2003
in four out of the five cases the LSA storm threshold is raised to
its maximum value, i.e., the full LSDB size. This Algorithm is
worse than Algorithm 4 in terms of maximum LSA storm threshold (as
shown in Case 4) but much better than Algorithms 1, 2 and 3. It is
also more robust than Algorithm 4 under link failure conditions. Even
if a link on the minimum spanning tree fails, those carrying intra-
area topology information (defined earlier as Type A LSAs) would
continue to get to all destinations since they are flooded as in
Algorithm 2 (full flooding but over only one interface between
neighbors). Once all the nodes know about the link failure condition,
they would be able to re-compute the new minimum spanning tree.
Overall Observation: It appears that Algorithm 2 (full flooding but
only over one of many parallel interfaces between neighbors) and
Algorithm 5 (flooding as in Algorithm 2 for LSAs carrying intra-area
topology information and flooding over a minimum spanning tree for
other LSAs) are the best ones and should be pursued further for
detailed specification.
6. Acknowledgements
We would like to acknowledge Jerry Ash, Margaret Chiosi, Elie Francis,
Anurag Maunder, Beth Munson, Moshe Segal, Vera Sapozhnikova, and Pat
Wirth for collaboration and encouragement in our scalability
improvement efforts for Link-State-Protocol based networks. We also
thank Aman Shaikh and Moshe Segal for comments on this draft.
7. References
[Ref1] Pappalardo, D.,"AT&T, customers grapple with ATM net outage,"
Network World, February 26, 2001.
[Ref2] "AT&T announces cause of frame-relay network outage," AT&T
Press Release, April 22, 1998.
[Ref3] Cholewka, K., "MCI Outage Has Domino Effect," Inter@ctive
Week, August 20, 1999.
[Ref4] Jander, M., "In Qwest Outage, ATM Takes Some Heat," Light
Reading, April 6, 2001.
[Ref5] A. Zinin and M. Shand, "Flooding Optimizations in Link-State
Routing Protocols," Work in Progress.
[Ref6] J. Moy, "Flooding over Parallel Point-to-Point Links," Work in
progress.
[Ref7] P. Pillay-Esnault, "OSPF Refresh and flooding reduction in
Choudhury et. al. [Page 13]
Internet Draft Flooding Simulation May, 2003
stable topologies," Work in progress.
[Ref8] G. Choudhury, V. Sapozhnikova, A. Maunder and V. Manral,
"Explicit Marking and Prioritized Treatment of Specific IGP
Packets for Faster IGP Convergence and Improved Network Scalability
and Stability," Work in Progress.
[Ref9] J. Ash, G. Choudhury, V. Sapozhnikova, M. Sherif, A. Maunder,
V. Manral, "Congestion Avoidance & Control for OSPF Networks",
Work in Progress.
[Ref10] "Private Network-to-Network Interface", ATM Forum
Specification af-pnni-0055.000, March, 1996.
[REF11] A. Qayyum, L. Viennot, A. Laouiti, "Multipoint Relaying for
Flooding Broadcast Messages in Mobile Wireless Networks," Project
Hipercom, INRIA Rocquencourt, France.
[Ref12] D. Katz, D. Yeung, K. Kompella, "Traffic Engineering
Extensions to OSPF Version 2," Work in progress.
[Ref13] B. M. Waxman, "Routing of Multipoint Connections," IEEE
Journal on Selected Areas in Communications, 6(9):1617-1622, 1988.
8. Authors' Addresses
Gagan L. Choudhury
AT&T
Room D5-3C21
200 Laurel Avenue
Middletown, NJ, 07748
USA
Phone: (732)420-3721
email: gchoudhury@att.com
Vishwas Manral
Netplane
189, Prashasan Nagar,
Road Number 72
Jubilee Hills, Hyderabad
India
email: Vishwasm@netplane.com
Choudhury et. al. [Page 14]
