See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/221164236

Open Shortest Path First (OSPF) Routing Protocol Simulation.

Conference Paper in ACM SIGCOMM Computer Communication Review · October 1993

DOI: 10.1145/167954.166243 · Source: DBLP

CITATIONS READS

30 9,688

5 authors, including:

Deepinder Sidhu Raj Nair

University of Maryland, Baltimore County Avesha
99 PUBLICATIONS 1,518 CITATIONS 30 PUBLICATIONS 1,418 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Raj Nair on 28 May 2014.

The user has requested enhancement of the downloaded file.

 Open Shortest Path First (OSPF)
Routing Protocol Simulation*

Deepinder Sidhu, Tayang Fu, Shukri Abdallah and Raj Nairt

Maryland Center for Telecommunications Research &
Department of Computer Science
University of Maryland — BC
Baltimore, MD 21228
and
Institute for Advanced Computer Studies
University of Maryland — CP
College Park, MD 20742

Rob Coltun
Consultant

Abstract At each router, the Router-ID of the DR con-

tinuously changes causing instability. (3) In the
Open Shortest Path First (OSPF) is a dynamic, worst case, when the DR and the BI)R fail at
hierarchical routing protocol designed to support the same time, the DR-agreement-time is bounded
routing in TCP/IP networks. A simulation of the above by twice the HelloInterval. A simulation of
OSPF Election Protocol shows three results: (1) the OSPF Flooding Protocol, using 20, 50 and 80
The Designated Router(DR) can be elected in con- router point-to-point networks, shows three results:
stant time, (2) If a router has a limited number of (1) For the 50 router network, as link speed exceeds
input buffers, a competition for buffers between the 4000 Kbps, the probability of overflowing the in-
Election and the Flooding Protocols increases the put buffers increases causing ret ransmissions. The
election time and causes an oscillatory behavior. increase in bootup-convergence-time from retrans-
*This research was supported in part by the Department of mission is bounded by two and three times the
Defense at the University of Maryland Baltimore County. The RxmtInterval for link speeds of 4000 to 6000 Kbps
vie ws and conclusions contained in this document are those of and above 50 Mbps respectively. The increase in
the authors and should not be interpreted as representing the of- the bootup-convergence-time is due to large nunl-
ficial policies, either expressed or implied, of the Department of ber of unacknowledged flooding packets received
Defense or the U.S. Govermnent. within RxmtInterval. (2) For 20 and 50 router net-
t present address: Netrix Corporation, 13595 Dnlles Technol- works, the input buffer size has little impact on the
ogy Dr., Herndon, VA 22071 bootup-convergence-time. For the 80 router net-
Permission to copy without fee all or part of this material is work, a small change in the input buffer size clras-
granted provided that the copiee ara not made or distributed for
tically changes the bootup-convergence-time. (3)
direct commercial advantage, the ACM copyright notice and the
title of the publication and its date appear, and notice is given Reducing the value of the RxmtInterval lowers the
that copying is by permission of the Association for Computing bootup-convergence-time at high link speeds.
Machinery. To copy otherwise, or to republish, requires a fee
and/or specific permission.
SIGCOMM’93 - Ithaca, N. Y., USA 19193
~ 1993 ACM 0-89791-61 9-01931000910053 . ..S 1.50

53
1 Introduction in the list of Router-Ids in the hello packet sent by
router Y.
Open Shortest Path First ‘( OSPF) is a dynamic, A router is said to declare itself a DR(BDR) if
hierarchical routing protocol designed to support it elects itself DR(BDR) and inserts its Router-Id
routing in TCP/IP networks [1]. The OSPF rout- in the DR(BDR) field of the hello packet. A null
ing protocol is a collection of interrelated algo- value in these two fields indicates the absence of
rithms: the Hello, Election, Flooding and Shortest- DR and the BDR. We refer to the router that wins
Path-First (SPF). The Hello, Election, and Flood- the election as the “winning-DR’).
ing Protocols distribute and synchronize rout-
ing information within an autonomous system.
Initial Election Time
The Shortest-Path-First algorithm computes the
shortest-path tree. Let tl be the time at which the first router is booted
In this paper, we present a simulation study of and t2 be the time at which the winning-DR elects
the Election and Flooding Protocols of OSPF. Sec- itself. The objective of this experiment is to deter-
tion 2 presents simulation results of the Election mine the DR-election-time, t2 – tl,on a broadcast
and the Flooding Protocols. Section 3 contains net work,
summary and conclusions. The network sizes vary from 10 to 100 routers
all of which have unlimited amount of input and
output buffers. The Wait Timer, RouterDeadIn-
2 OSPF Simulation
terval and the Hello Timer of each router are set
to 40, 40 and 10 seconds respectively. We assume
In this section, we present the results of the discrete
zero propagation and processing delays. We also
event simulation of the Election and Flooding Pro-
assume that the Election Protocol runs in zero sec-
t Ocols.
onds. Initially, all routers are eligible routers in the
DOWN state. If router R. was booted at time t.
2.1 Election Protocol
and the next router Rv was booted at time tg such
The Election Protocol elects a Designated Router that tu z tz, then tv – t$ is the inter-boot-time,
(DR) and a Backup Designated Router (BDR) to At. The first router is booted at time At seconds,
distribute and synchronize topology information and the remaining routers are booted in increasing
among routers on a broadcast network. Within order of Router-Id. The experiment is repeated for
the network, the DR reduces the number of mes- At of 7, 10, 22, 30 and 40 seconds.
sages needed to broadcast topology information Figure la shows the result for At = 7 seconds,
and hides topology information from other routers and Fig. lb shows the result for At = 30 and 40
within the autonomous system. seconds. In Fig. la, the DR-election-time increases
A router is eligible to participate in the Elec- linearly with the number of routers. In Fig. lb,
tion Protocol if its Router-Priority is positive. A the DR-election-time is constant. To explain the
router nominates a DR and a BDR using the DR linear increase of the DR-election-time in Fig. la,
and BDR fields of the hello packet. Every Hel- we trace the sequence of events executed at routers
loInterval, each router X transmits a hello packet R1 and Rz attached to a broadcast network. Then,
containing among other information its Router-Id, we generalize this explanation to a network of n
its Router-Priority and a list of Router-Ids from routers.
whom X has received a hello packet, Router X dis- At time 7 seconds, when router RI is booted up,
covers router Y when X receives for the first time it broadcasts a hello packet containing its Router-
a hello packet from router Y. Router X detects Id and enters the WAIT state for a period of 40
the absence of router Y when X does not receive seconds. Similarly, when router R2 is booted at
a hello packet from router Y for a period of Rou- time 14 seconds, it broadcasts a hello packet and
terDeadInterval. Router X considers router Y as enters the WAIT state. Router RI upon receiving
a bidirectional neighbor when X sees its Router-Id the hello packet from R2 at time 14 seconds estab-

54
lishes one-way communication with R2. At time 17 ma
1
seconds, the second HelloInterval, router RI broad-
700-
casts a hello packet with the Router-Ids of RI and
R2. Upon receiving this hello packet, R2 estab- [-
.0
lishes bidirectional communication with router RI. .! ‘w
.At time 24 seconds, when R2 broadcasts a hello 4al -
4
packet, both routers establish bidirectional com- g
3rm-
munication becoming candidates for election. A
’200-
router exits the WAIT state if its Wait Timer ex-
pires or a Backup-Seen event is triggered. 1
1020304Q50 607080901CCI
Newark S-
A Backup _Seen event is triggered at any router
Rx if R. receives a hello packet from another router
Rv such that
or (2) RV declares
that it has not elected
(1) Rv declares
itself
itself
to be the DR
a BDR.
to be the BDR,
and declares
Since R1 and .R2 are !
.a
“~-
in the WAIT state, they cannot declare themselves .g ~, ,

as DR or BDR. Is
At time 47 seconds, the Wait Timer at RI ex-
pires, and RI elects R2 as the DR because R2 has
a higher Router-Id. R1 broadcasts the result of the ~ Iriler-nca lTir@.e.3Q0r40Jcc Fi~ b
10203040 SO 60 70 60 90 1 K1
elect ion in its hello packet. A Backup _Seen event
NeNwuk Sue
at R2 is not triggered because RI is not declar-
ing itself to be DR or BDR. At time 54 seconds, Figure 1: Election Time for Broadcast Networks
when the Wait Timer at R2 expires, R2 elects it-
self as the DR and R1 as the BDR. At the same
time, the Hello Timer at R2 expires and R2 broad- Finally, router Rn is booted at time 7 x n sec-
casts the results of the election. When RI receives onds, All routers establish bidirectional communi-
the hello packet, a Neighbor_Change event is trig- cation with Rn before its Wait Timer expires. As

gered causing RI to run the election. R1 selects a result, all routers elect Rn as the DR.. At time,

R2 as the DR and itself as the BDR. At time 57 7wz+40 seconds, the Wait Timer of R. expires, and

seconds, RI declares itself as a BDR to the whole R. elects itself as the DR and R.-l as the BDR.

network by broadcasting a hello packet. Thus, the Thus, the DR – eiection – time = 7 x n + 40 – 7,

DR-election-time for a network of two routers is where At = 7. The election time increases lin-

54 – 7 = 47 seconds. early because a Backup_Seen event cannot be trig-

To generalize the explanation, consider a gered at any router. The same explanation holds
network with n routers with Router-Ids of for At = 10 and 22 seconds.

RI, R2,. ... Rn. The boot time of these routers are Each router excluding & and R.-l runs the
7,14,21,.. .,7 * n seconds respectively. The Wait Election Protocol two additional times. 11~ and
Timer at each router expires at 47,54,61,..., 7xn+ R.-l run the Election Protocol one additional
40 seconds respectively. Each router remains in the time. First, Rn broadcasts a hello packet declaring
WAIT state for the whole period of 40 seconds be- itself as the DR which causes a Neighbor.Change
cause the Backup _Seen event cannot be triggered event at all other routers. Second, R._l broad-
by any router. Before the Wait Timer of router i casts a hello packet declaring itself as the BDR
(1 < i < n – 1) expires, router i + 1 is booted, which causes a Neighbor-Change event at all other
and both routers establish bidirectional communi- routers.
cation. When the Wait Timer expires at router i, Figure lb shows a constant DR-election-time. In
it elects the router with the highest Router-Id with this scenario, At = 30 and router RI is booted at
whom it established bidirectional communication. time 30 seconds. Router Rz is booted at time 60

55
seconds and enters the WAIT state. RI establishes routers. This result can be generalized by assigning
bidirectional communication with R2 at time 80 different positive priorities to the routers.
seconds. When the Wait Timer of RI expires at
time 70 seconds, RI elects itself as the DR. Since
Election Time and Topological Change
RI has no bidirectional neighbors, it does not elect
a B D R. Therefore, the DR-election-time is 40 sec- Assume that all routers are booted in increasing or-
onds. At time 70 seconds, R1 broadcasts the results der of Router-Id and eventually reach a FULL state
of the election in a hello packet which triggers a with the DR and the BDR. let tdl (t~l) be the time
Backup .Seen event at R2. R2 exits the WAIT state at which the first router detects the absence of the
and elects RI as the DR. For each of the remaining DR(BDR), and t&(t~z) be the time at which the
routers, a Backup_Seen event is triggered upon re- last router enters the EXCHANGE-START state
ceiving a hello packet from the BDR. These routers with the newly elected DR(BDR). The objective
exit their WAIT state and accept the existing DR of this experiment is to determine the DR(BDR)-
and BDR. agreement-time, t& – tdl (t~z– tbl),for a broadcast
Figure lb also shows a constant DR-election- net work aft er a t orological change.
time under a different scenario, where At = 40 The time t~l is measured after RouterDeadIll-
seconds. The Wait timer of RI expires at time 80 terval seconds have elapsed, where RouterDeadIn-
seconds when router R2 is booted. Since Rl and terval is the minimum period before a router de-
R2 have not yet established bidirectional commu- tects the absence of another router. At time t~b,
nication and the Wait Timer of RI has expired, RI the DR and the BDR are brought down, and the
elects itself as the DR. R1 does not elect a BDR DR-agreement-time and BDR-agreement-time are
since it is has not established bidirectional com- measured. This experiment is run with At equal
munication with any other router. On receiving to 7, 10, 22, 30 and 40 seconds. Figures 2a-2c show
the hello packet from RI which establishes bidi- the results of this experiment.
rectional communication, a Backup.Seen event is Let td~(t~~) be the last time at which the
triggered at R2 forcing R2 to exit its WAIT state DR(BDR) broadcast a hello packet before go-
and elect RI as the DR. A Backup-Seen event is ing down (td~, tb~ < tdb). All routers should
triggered at the remaining routers causing them to detect the absence of the DR exactly at tdh +
elect RI and R2 as the DR and BDR respectively. RouterDeadInterval and the absence of the BDR
The order of handling the events impacts the exactly at tbh + RouterDeadInterval seconds.
performance of the Election Protocol. The Dead- However, a router R. checks if the RouterDeadIn-
RouterInterval-expiration, Wait -Timer-expiration, t erval has expired only when R.’s Hello Timer ex-
Backup_Seen and Neighbor.Change events deter- pires. The Hello Timer expiration depends on the
mine the content of a hello packet. An efficient boot time of each router. Depending on its boot
OSPF implementation handles these events before time, a router belongs to one of ten groups, G’,,
it handles the Hello-Timer-expiration event; ot h- where i = (Router – Id * At) mod HelloInterval.
erwise, the most recent information(results of elec- All routers in a group detect the RouterDeadInter-
t ion, new bidirectional neighbors) will be broadcast val expiration of another router at the same time.
after one HelloInterval resulting in a degradation in Let the DR and BDR belong to the groupti Gd and
performance. Gb respectively.
To achieve the constant DR-election-time as in To calculate the DR(BDR)-agreement times, we
Fig. lb, (1) choose two routers to be the intended partition the groups into three sets, S1, Sz and
DR and BDR, and assign them positive Router- S3 where S1 is the set of groups which detect the
Priority and the highest two Router-Ids, (2) boot absence of the DR and the BDR at the same time,
the intended DR first and wait for a period of at Sz is the set of groups which detect the absence of
least Wait Timer before booting the intended BDR, the DR before they detect the absence of the BDR
(3) boot the intended BDR and wait for a period and S3 is the set of groups which detect the absence
of at least Wait Timer, and (4) boot the remaining of the BDR before they detect the absence of the

56
 1 BDR C.m&kOll 2

1
25 BDR-.-3
--, -------- ----------- . . . . .. . . . .. . .. -------------- . .. . .. . .. . . . . . ----
i
2.0 -
BDR-.-3
. . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . .. . . . . . ..

15- DR CMAQMI 2

10
.. .. . . . . . . . . . . . . . . . . . . . . . ------------- ------------- ---------
DR CMMMWU 3
t 1 10 -
DR CXudtwn 3
... . .. . .. . . . .. . .. . . . . .. . .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . .
‘t i
I
InmPBmI1 Time F 7 aec F,,, . I ti-Bswt Tlmo,= 22 SCGS, F,,. b
1070304050 607080901W 1020304050 607080 90 ICKI

Nelwaz S12C. New-k S-

10

-2 ILI&,PBoot ‘lhnc , 10= w muludc i.. c

107D304O5O 6070 M901W

Nelwmk Sur,

Figure 2: Election Time after Topological Change

DR. t& < tbh < tdb, or (3) tbh < tdh < tdb and & is
To determine in which set a group Gk belongs, not a multiple of the HelloInterval. Each condition
consider a router Rj in the DR-OTHER state determines a sequence of events to elect a new DR
which belongs to group Gk. Let tjh be the first and a new BDR.

time the Hello Timer expires at router Rj after the If condition 1 holds, all routers belong to
DR and BDR are brought down(tjh ~ t~b). Let grOUp Go ~ S1 and tdl = tbl = tdh +
z = ijh – Qh and g = tj~ – t~~. If z and g are both RouterDeadIntemal. A Neighbor_Change event
less than the HelloInterval, or both are greater or simultaneously causes all routers to run the
equal to the HelloInterval, then Gk c S1; other- Election Protocol, elect a DR and enter the
wise, if z is greater or equal to the HelloInterval, EXCHANGE-START state with the new DR. In
then Gk E 5’2; otherwise, Gk <5’3. this case tdz = tdl and the DR-agreement-time is
Thus, we determine t~l and tbl as follows. t~l = zero as shown in Fig. 2c. After one HelloInter-
tdh+RouterDeadInte?’val+d if Gd # @; otherwise, val, the new DR broadcasts a hello packet which
td~ = tdh + RouterDeadInterval + f if Gd = @ causes all routers to run the Election Protocol,
and G~ is the first non-empty group that follows d elect a new BDR and simultaneously enter the
in the ring of integers modulo 10. Similarly, t~l = EXCHANGE-START state with the new BDR.
tbh + RouterDeadInterval + b if Gb # ~; otherwise, Hence, tbz = tbl + Hellolntewai and the BDR-
tb~ = tbh + RouterDeadInterval + f if Gb = ~ and agreement-time is 10 seconds as shown in Fig. 2c.
Gf is the first non-empty group that follows b in If condition 2 holds, all groups belong to the sets
the ring of integers modulo 10. S1 and Sz, and the set S3 is empty. Each router in
To determine tdz and tbz, we relate the times S1 elects a new DR and enters the EXCHANGE-
tdh, tbh and tdb according to one of three conditions: START state with the new DR. Each router in Sz
(1) At is a multiple of the HelloInterval, or (2) promotes the present BDR to become the new DR

57
and detects the absence of the BDR at the next ex- neighboring router when its Hello Timer expires. If
piration of its HelloTimer. Let T1 be the first time the granularity of checking the RouterDeadInterval
at which the new DR broadcasts a hello packet, and is finer than the HelloInterval, it is possible to ob-
T2 be the last time at which any group in S2 detects tain one group of routers which detect the absence
the absence of its promoted BDR. T’l and T2 must of the DR and BDR at the same time as in Fig. 2c.
occur within one HelloInterval from t~l. All routers
are guaranteed to have entered the EXCHANGE-
Interaction of Election and Flooding Pro-
START state with the new DR at time min(Tl, 7’2).
tocols
Then, tdz = min(Tl, T2). At time T1 all routers run
the Election Protocol and elect a new BDR. There- The objective of this experiment is to determine
fore, tbz = T1. Figures 2a-2b show the DR(BDR)- if the Flooding Protocol affects the DR-election-
agreement times for condition 2 when N = 7 and time and DR(BDR)-agreement-time. The exper-
22 seconds. imental settings are identical to the two previous
If condition 3 holds, then all the groups belong experiments except that & = 7 and the size of the
to the sets S1 and S3, and the set S2 is empty. input-control-packet queues of all interfaces is set
Routers in the set S1 elect a new DR and en- to 10 packets. Each interface has one input-control-
ter the EXCHANGE-START state with the new packet queue which contains both hello and flood-
DR. Each router in S3 elects a new BDR and en- ing packets. If the queue is full, incoming packets
ters the EXCHANGE-START state with the new are dropped.
BDR. After one HelloInterval, routers in S3 de- We conducted three different runs of the same
tects the absence of the DR, promote the new experiment. The results of the three runs are dif-
BDR to the new DR and continue the database ferent from each other and different from the re-
synchronization process with the promoted DR. sults in Figs. la and 2a. This behavior results from
If the newly elected DR is in S3, it declares it- the competition between the flooding packets and
self as a new BDR, promotes itself and elects a the hello packets for input buffer. The flooding
new BDR. Let T4 be the time at which the newly packets prevented the hello packets from arriving
elected DR declared itself as a new BDR. After at the routers every HelloInterval thus increasing
one more HelloInterval, it declares itself a new DR. the election and agreement times. As the size of
The first declaration does not change the iden- the queues decreases, the election and agreement
tities of the new DR and new BDR. On receiv- times increase. However, when we introduce sepa-
ing the second declaration, all router agree on the rate input queues for the hello and flooding pacli-
new DR and new BDR. On the other hand, if the ets keeping the tot al size of both queues to 10, we
newly elected DR is in S1, it elects a new BDR obtain the same results as in Figs. la and 2a. We
and declares itself new DR one HelloInterval after processed the hello packets before we processed the
~dl. Therefore, we expect that the DR-agreement flooding packets. We strongly recommend that an
time to be less than one HelloInterval as shown OSPF implementation should have a separate con-
in Figs. 2a-2b. Let T3 be the last time at which trol queue for hello packets and should process the
any group in S3 detects the absence of the BDR. hello packets at a higher priority than the other
Therefore, all routers are guaranteed to have en- cent rol packets.
tered the EXCHANGE-START state with the new If a router, R, has a limited amount of input
DR at time min(T1, T3). Then, tdz = min(T1, T3). buffer space, we observe an oscillatory behavior in
All routers know about the newly elected BDR at the identity of the DR at R. If R does not re-
tbz = max(T1, T4+HelloInter8al) +HelloInterval. ceive a hello packet from the DR within a Rou-
In the worst case, when the DR and the BDR terDeadInterval seconds, R assumes that the DR
fail at the same time, the DR-agreement-time is is down. The DR may not be down except that
bounded above by twice the HelloInterval, its hello packets are being dropped due to lack
In an OSPF implementation, a router may of buffer space. R runs the election and elects a
checks the expiration of RouterDeadInterval for a new DR and starts a new synchronization process

58
wit h the new DR. Upon receiving a hello packet Link Speed and Convergence Time
from the old DR, 1? assumes that the old DR is up
again(Neighbor.Change event ) and runs the elec- The objective of this experiment is to determine

tion. R elects the old DR and starts a new database the impact of link speed on the convergence-time

synchronization process. and the bootup-convergence-time. All routers have

unlimited amount of input and output buffers. The
In networks with a strict performance require-
Wait Timer, RouterDeadInterval and the Hello
ments, for example convergence to occur within
Timer of each router are set to 40, 40 and 10 sec-
twenty seconds, it is crucial to impIement a sep-
onds respectively.
arat e queue for hello packets.
Initially, all routers are in the DOWN state
and are booted simultaneously. Aft er the network
reaches routing- convergence-st ate, the boot up-
convergence-time is measured, and a t orological
2.2 Flooding Protocol
change is introduced at time to by bringing down
a link. The routers are allowed to respond to
The Flooding Protocol is a reliable information ex-
this topological change and reach the routing-
change mechanism which ensures that all routers
convergence-state. The last action of the Flooding
within an area have identical topology informa-
Protocol is the deletion of a link state request list
tion for that area. Every pair of neighboring
or the receipt of a database description packet. Let
rout ers exchange topology summaries to learn
the time of the last action be tl. The convergence-
about the most recent topology changes within the
time is measured as the time period tl – to.
autonomous system. A router obtains the new in-
Figures 3a-3c show the bootup-convergence-time
formation by synchronizing its topology database
and convergence-time over a range of link speeds
with a neighboring router using the Flooding Pro-
for the 50 router’ network. In Figs. 3a-3b, for
tocol.
link speeds less than 4000 Kbps, the bootup-
In this section, we describe three experiments
convergence-t ime for the Rxmt Int erval of 5 and
that measure the bootup-convergence-time and the
10 seconds are 20 and 30 seconds respectively.
convergence-time for point-to-point networks. The
Since all routers are booted at the same time,
bootup-convergence-time is the interval between the they establish bidirectional communication in 10
time all routers and links in a network are initially
seconds. If a link state advertisement is not ac-
brought up until the routing-convergence-st ate is
knowledged within RxmtInterval, a retransmis-
reached. The routing-convergence-state is the state
sion occurs. Consequently, we get the bootup-
in which all routers reach the FULL state and have convergence-time to be the sum of one HelloIn-
empty retransmission and request lists. Let t be In Fig. 3b,
terval and twice the RxmtInterval.
the time at which a topological change occurs in for link speeds from 4000 to 6000 Kbps, the in-
a network that has reached a routing-convergence-
crease in the bootup-convergence-time is bounded
state. The convergence-time is the time interval by twice the RxmtInterval. For example, the
from t until the next routing-convergence-st ate is bootup-convergence-time for the link speed of 6000
reached. Kbps and RxmtInterval of 10 seconds is 50 seconds,
We use three topologies: (20,4, 6), (50,6,4) and giving an increase of 20 (50-30) seconds. In Fig. 3c,
(80, 6, 5). In the notation (IV, d, e), IV is the number for link speeds above 50 Mbps, the increase in
of routers, d is the network diameter and e is the the bootup-convergence-time is bounded by three
maximum router degree. To minimize topology- times RxmtInterval. As the link speed increases,
induced bias, we generate a topology with random the probability of input-buffer-overflow increases
interconnections, To exercise the Flooding Proto- causing retransmissions because large numbers of
col, high values are chosen for d and e. All links flooding packets are received within an RxmtInter-
have the same speed chosen from a range of 56 val. When a router, l?=, receives a flooding packet
Kbps through 2 Gbps. from a router, Ry, router Rz checks if this packet

59
 Net<%, 6.6 I

1 + Bcwmpw_-w, Rmt = Nat<30,6, &

33 45 -
c! BLwulp-ckmver--m, Rxm, . 0 + Booim@unvcr3-~, Rxmt = s
x C4rwnr---rww, 1 mum “1 o B_Cam_-h , h, = 10
40 - . -—TI!W 1 fuhm

3s

30 -

25 -

1.s 20’ -

15 -
10

5
s
M a F,& b
Om i
600 8al Iwo 12CK3 1400 1600 1800 20c4 3500 4CJXI 4500 5CUI 5S00 ww
Link sped (Kbps) (LOW) Lmk speed (Kllp) (?ntcJ.mdu.)

Boomp&mwgum-nme, lhu,t = s

w
45 .+

o Bom.#2mvq-’lhre> F.xmt = 10
x ccuva--mnc, 1 fulme + <20.4.6 I
so -

45

40 -
E :~:
33 -

30 -

10 - 2.5
1
s m
WI=
0 0.s 1 1.5 2

Lmk sped (*) (H@ .10, Buffer Sue Q&)

+Rxmt.3-
.RxInt. s&x
40 -
XRXM, =1 OSC’-J

3s-

xl -

?5

m -

1s -

%.=
,0
as 1 1.5 2

Link sp2c.i (lap) Xlo$

Figure 3: Impact of Link Speed, Buffer Size and RxmtInterval on

60
acknowledges a packet on Rz’s retransmission list. RxmtInterval and Convergence Time
Therefore, as the size of the retransmission list at
The objective of this experiment is to demonstrate
Rz increases, the time to acknowledge a packet in-
the effect of a low setting of the RxmtInterval. The
creases.
experimental procedure is as described above. In
In Figs. 3a-3c, RxmtInterval does not affect the
this experiment, we used the 50 router network
convergence-time which is bounded by 10 seconds.
with link speeds from 25 to 200 Mbps. Output
A router in this OSPF implementation responds to
and input buffer size is unlimited.
a topological change when its Hello Timer expires.
The results of this experiment are shown in
To explain the bounding value, let t,2 < tl, be the
Fig. 3e. Reducing the value of the retransmission
time at which the Hello Timers at all routers expire.
timer lowers the bootup-convergence-time for all
The interval tz – tl is less than or equal to the
link speeds. However, the reduction is larger for
HelloInterval, 10 seconds.
higher link speeds. For example, at the link speed
of 100 Mbps, a speedup of 14 seconds is observed
Buffer Size and Convergence Time when the retransmission timer is reduced from 10
to 3. This result verifies the suggestion in [1] that
The objective of this experiment is to determine
the setting of the retransmission timer can be re-
the impact of input buffer size on the bootup-
duced for high speed networks.
convergence-time. In this experiment, for networks
Buffer management is vital to the performance
of 20, 50 and 80 routers, the link speed is fixed at
of the Flooding Protocol; otherwise, there is poten-
T1 (1.544 Mbps) and the input buffer size is varied
tial for performance degradation due to high con-
from 4 through 20. The experimental procedure is
tention for memory. The Flooding Protocol in an
as described above.
OSPF implementation may use inherent rate-based
The results of this experiment are shown in
control mechanisms such as: (1) limit the number
Fig. 3d. For any of the networks, convergence does
of simult aneous synchronizations, or (2) reduce t he
not occur if the buffer size is less than or equal to
value of the retransmission timer. It is also recom-
three. This result implies that the lower bound
mended that a linear search of the retransmission
of the input buffer size for the operation of an
list be avoided.
OSPF network of 20 or more routers is greater than
three. Consequently, a router requires an input
buffer memory size of at least 4 times the maxi- 3 Summary and Conclusions
mum size of a flooding packet.
For the 20 and 50 router networks, the buffer Open Shortest Path First (OSPF) is a dynamic, hi-
size has little impact on bootup-convergence-time. erarchical routing protocol to support the TC!P /IP
The bootup-convergence-time increases at a buffer networks. In this paper, a simulation of the OSPF
size of 6 in the 50 router network and at a buffer Election Protocol shows three results: (1) The Des-
size of 7 in the 20 router network, This increase ignated Router(DR) can be elected in constant
results from two retransmissions which occur after time. (2) If a router has a limited number of input
the loss of a packet and its acknowledgment. This buffers, a competition for buffers between the Elec-
retransmission occurs at a higher buffer size for the tion and the Flooding Protocols increases the elec-
20 router network than for the 50 router network tion time and causes an oscillatory behavior. At
because the 20 router network has a higher router each router, the Router-ID of the DR continuously
degree and must send out more link-state adver- changes causing instability. To solve these prob-
tisements per output buffer than the 50 router net- lems, Hello packets must be queued in a separate
work. The 80 router network demonstrates very control queue and processed at a higher priority,
noisy behavior because the number of link-state ad- (3) In the worst case, when the DR and the BDR
vertisements that must be flooded is large. Clearly, fail at the same time, the DR-agreement-time is
a buffer size of 20 or more is needed for networks bounded above by twice the HelloInterval.
with more than 80 routers. A simulation of the OSPF Flooding Protocol

61
 using 20, 50 and 80 router point-to-point net-
works shows three results: (1) For the 50 router
network, as link speed exceeds 4000 Kbps, the
probability y of overflowing the input buffers in-
creases causing retransmissions. The increase in
bootup-convergence-time from retransmissions is
bounded by two and three times the RxmtInter-
val for link speeds of 4000 to 6000 Kbps and above
50 Mbps respectively. The increase in the bootup-
convergence-time is due to large number of unac-
knowledged flooding packets received within Rxmt-
Interval. (2) For 20 and 50 router networks, the
input buffer size has little impact on the bootup-
convergence-time. For the 80 router network, a
small change in the input buffer size drastically
change the bootup-convergence-time. (3) Reducing
the value of the RxmtInterval lowers the bootup-
convergence-time at high link speeds.

References

[1] J. Moy. The open shortest path first (OSPF)

specification. Technical Report RFC- 1131, SRI
Network Information Center, October 1989.

[2] Deepinder Sidhu, Tayang Fu, Shukri Abdallah,

Raj Nair, and Rob Coltun. Open shortest path
first simulation. under preparation.

62

View publication stats