WRP An Efficient Routing Protocol For Wireless Networks
WRP An Efficient Routing Protocol For Wireless Networks
WRP An Efficient Routing Protocol For Wireless Networks
183
Abstract. We present the Wireless Routing Protocol (WRP). In WRP, routing nodes communicatethe distance and secondto-last hop for each destination. WRP reduces the number of cases in which a temporary routing loop can occur, which accounts
for its fast convergenceproperties. A detailed proof of correctnessis presented and its performance is compared by simulation
with the performance of the distributed Bellman-FordAlgorithm (DBF), DUAL (a loop-free distance-vectoralgorithm) and an
Ideal Link-state Algorithm (ILS), which represent the state of the art of internet routing. The simulation results indicate that
WRP is the most efficientof the alternatives analyzed.
1. I n t r o d u c t i o n
The routing protocols used in multihop packet-radio
networks implemented in the past [2,3,11] were based on
shortest-path routing algorithms that have been typically based on the distributed Bellman-Ford Algorithm
(DBF) [4]. According to DBF, a routing node knows the
length of the shortest path from each neighbor to every
network destination and this information is used to compute the shortest path and successor in the path to each
destination. An update message contains a vector of one
or more entries, each of which specifies as a minimum,
the distance to a given destination. A major performance
problem with DBF is that it takes a very long time to
update the routing tables of network nodes after network partitions, node failures, or increase in network
congestion. This performance problem of DBF stems
from the fact that it has no inherent mechanism to determine when a network node should stop incrementing its
distance to a given destination. This problem is usually
called the counting-to-infinity problem.
The counting-to-infinity problem is overcome in one
of three ways in existing internet routing protocols.
OSPF [12] relies on broadcasting complete topology
information among routers, and organizes an internet
hierarchically to cope with the overhead incurred with
topology broadcast. BGP [16] exchanges distance vectors that specify complete paths to destinations. E I G R P
[1] uses a loop-free routing algorithm called D U A L [8],
which is based on internodal coordination that can span
multiple hops; D U A L also eliminates temporary routing
loops.
However, there are significant differences between
wireless networks and wired internets in which internet
routing protocols are used. A wired internet has relatively high bandwidth and topology that changes infre* This work was supported in part by the AdvancedResearchProjects
Agency (ARPA) under contract F19628-93-C-0175 and by the
Officeof Naval Research under Contract No. N-00014-92-J-1807.
9 J.C. Baltzer AG, Science Publishers
184
paths to the destination, because of the query-based synchronization approach to achieve loop-free paths, the
communication complexity could be high.
Recently, a number of distributed shortest-path algorithms have been proposed [5,7,9,10,15] that utilize
information regarding the length and the second-to-last
hop (predecessor) of the shortest path to each destination to eliminate the counting-to-infinity problem of
DBF. We call this type of algorithms as path-finding
algorithms. According to these algorithms, each node
maintains the shortest-path spanning tree reported by its
neighbors. A node uses this information along with the
cost of adjacent links to generate its own shortest-path
spanning tree. An update message exchanged among
neighbors consists of a vector of entries that report
updates to the sender's spanning tree; each update entry
contains a destination identifier, the distance to the destination, and the second-to-last hop of the shortest path
to the destination.
Path-finding algorithms are an attractive approach
for wireless networks, because they eliminate countingto-infinity problem. However, these algorithms can still
incur temporary loops in the paths specified by the predecessor before they converge; without proper precautions, this can lead to slow convergence, or incur
substantial processing if a node is required to update its
entire routing table for each input event. To address
these problems, we have proposed a path-finding algorithm, PFA, which substantially reduces temporary
looping situations [13], and which limits routing table
updates to include only those entries that are affected by
a network change.
The rest of this paper describes a Wireless Routing
Protocol (WRP) for a packet radio network based on
PFA, illustrating the key aspects of the protocol's operation. The following sections show that the protocol is
correct (i.e., that it produces correct routing tables
within a finite time after topology changes) and compares its performance with that of DBF, DUAL and an
Ideal Link-state Algorithm (ILS) which uses Dijkstra's
shortest path algorithm.
ILS consists of ideal flooding of link-state updates in
order to replicate the topology of the network at each
router; ideal flooding means that infinite sequence
numbers can be used to validate link-state updates, and
that all such updates are successfully delivered at every
router.
To describe WRP, we model a network as an undirected graph represented as G(V, E), where V is the set
of nodes and E is the set of links (or edges) connecting
the nodes. Each node represents a router and is a computing unit involving a processor, local memory and
input and output queues with unlimited capacity. In a
wireless network, a node has radio connectivity with
multiple nodes and a single physical radio link connects
a node with many other nodes. However, for the purposes of routing-table updating, a node A can consider
another node B to be adjacent (we call such a node a
"neighbor") if there is radio connectivity between A
and B and A receives update messages from B. Accordingly, we map a physical broadcast link connecting multiple nodes into multiple point-to-point functional
links defined for these node paths that consider to be
neighbors of each other.
Then, a functional bidirectional link connecting the
nodes is assigned a positive weight in each direction. All
messages received (transmitted) by a node are put in an
input (output) queue and are processed in FIFO order.
The communication links in the network are such that all
update messages transmitted over an operational link
are received in the order in which they were transmitted
within a finite time.
A link is assumed to exist between two nodes only if
there is radio connectivity between the two nodes and
they can exchange update messages reliably with a certain probability of success. When a link fails, the corresponding distance entries in a node's distance and
routing tables are marked as infinity. A node failure is
modeled as all links incident on that node failing at the
same time.
WRP is designed to run on top of the medium-access
control protocol of a wireless network. Update messages
may be lost or corrupted due to changes in radio connectivity or jamming. Reliable transmission of update messages is implemented by means of retransmissions.
After receiving an update message free of errors, a node
is required to send a positive acknowledgment (ACK)
indicating that it has a good radio connectivity and has
processed the update message. Because of the broadcast
nature of the radio channel, a node can send a single
update message to inform all its neighbors about
changes in its routing table; however, each such neighbor
sends an ACK to the originator node.
In addition to ACKs, the connectivity can also be
ascertained with the receipt of any message from a neighbor (which need not be an update message). To ensure
that connectivity with a neighbor still exists when there
are no recent transmissions of routing table updates or
ACKs, periodic update messages without any routing
table changes (null update messages) are sent to the
neighbors. The time interval between two such null
update messages is the HelloInterval.
If a node fails to receive any type of message from a
neighbor for a specified amount of time (e.g., three or
four times the HelloInterval known as the RouterDeadInterval), the node must assume that connectivity with
that neighbor has been lost.
A marker (tagj) used to update routing table; it specifies whether the entry corresponds to a simple path
(tag} = correct), a loop (tag} = error) or a destination
that has not been marked (tagj = null).
185
S. Murthy, or.s Garcia-Luna-A ceves / An efficient routing protoco[ for wireless networks
186
Procedure Initl
w h e n r o u t e r i initializes itself
do begin
set a link s t a t e t a b l e with costs of a d j a c e n t links;
N +.- i; N i e - x
f o r e a c h (x q N i )
do begin
N i 4- N U x; .tag~ e- null;
Sxt e- null; Px: ~- null; D xi 4- co
end
D~t 4 - 0; s t/ +- n u l l ; P ii 4- n u l l ; tag~ 4- c o r r e c t
f o r e a c h 3 q N call I n i t 2 ( x , 3 )
Init2(x, j)
D 3x
i. 4- oo; P3x
i 4- null; ~i.
3 x 4- null; ~eqnOtjx e- 0
end
Procedure Send
begin
for each (n q N i )
do begin
i f ( L I S T i ( n ) is not e m p t y )
t h e n send messages with L I S T i ( n ) to n
empty LISTi(n )
end
end
Procedure Message
w h e n r o u t e r i receives a message on link (i, k)
begin
i f (k ~ N i ) d o
begin
Ni 4- Ni
k;
s e n d update(O, k, D k , P ki
end
reset HelloTimer;
f o r e a c h entry ( u k j R D k r p k ) I i r j
3' '
3'
$
do begin
i f (~ ~ N)
then begin
i f (RD k = ,3o) t h e n delete entry
else begin
P r o c e d u r e Create_RList(seqno)
begin
s e q n o 4- s e q n o + 1; N e i g h b o r S e t <-- N i
b i t m a p ~ 4- 0; R e t r a n s m i s s i o n T i m e r
4- x
add u p d a t e s to R L i s t
end
Procedure Delete..RList(seqno)
begin
set b i t m a p [ s e q n o ] 4- 1; d e l e t e +- 1
for all n q N i begin
i f {bitraap[seqno] = O) d e l e t e 4- 0;
end
i f (delete = 1) delete l:l.List[seqno] e n d
P r o c e d u r e Update_RList(seqno)
begin
reset RetransmissionTimer
send u p d a t e R L i s t [ s e q n o ] ;
end
P r o c e d u r e Clean_RList (~eqno)
begin
f o r a l l entries in R L i s t
delete R L i s t [ s e q n o ] ;
end
P r o c e d u r e Connectivity
w h e n HelloTimer expires
begin
H e t l o C o u n t [ k ] 4- H e l l o C o u n t [ k ] + 1;
i f ( H e l l o C o u n t [ k ] < y) t h e n
reset HelloTimer;
else begin
N i ~- N i -- k
call D e l e t e _ R L i s t (k)
i
lk 4~
taglk 4- null
delete c o l u m n for k in d i s t a n c e t a b l e
update routing table
end
end
P r o c e d u r e T i m e O u t ( i , k)
w h e n R e t r e n s m i s s i o n T i m e r expires
begin
Retr~nsmissionCounter 4- RetransmissionCounter- 1;
if (RetransmissionCounter < z)
cMl U p d a t e - R L i s t (k)
else begin
N i 4- N i -- k
call D e l e t e _ R L i s t (k)
i
lk r co
tagtk 4- null
N 4- N U 2 ;
f o r e a c h entry q N i call I n i t 2 ( x , j )
tag~ 4- null; call D T
end
end
else begin
delete c o l u m n for k in d i s t a n c e t a b l e
update routing table
end
end
Procedure DT
w h e n distance table update has to be done
begin
D j k e - l i k + D 3k . ' P ij k e - p ; ;
tag~ 4- null;
end
end
fo . . . . h entry ( u k i , j , R D k i , rp k ) left l i r 3
d o case of u~
0: call Update(j,k)
I: call A C K ( j , k )
end
call S e n d
(2) f o r a l l neighbors b
do begin
i f k is in t h e p a t h from i to j in
t h e d i s t a n c e t a b l e t h r o u g h neighbor b
9 + D jk.
t h e n D}b 4- D~kb
, P ij b 4 - p k
end
end
end
Fig. 1. Protocolspecification.
ciated with the input event. This unique feature of WRP
accounts for its fast convergence after a single resource
failure or recovery as it eliminates more temporary looping situations than previous path-finding algorithms.
Processing an Update." To process an update from
neighbor k regarding destination j, the distance and the
predecessor entries in the distance table are updated. A
flag (tag) is set to specify that this entry in the table has
been changed. A unique feature of WRP is that node i
also determines if the path to destination j through any
of its other neighbors {b E Nilb r k} includes node k. If
the path implied by the predecessor information
reported by node b includes node k, then the distance
entry of that path is also updated as Djb = Dikb + D k and
the predecessor is updated asp}b = p~. Thus, a node can
! 87
Procedure
RT_Update
w h e n r o u t i n g t a b l e has to be u p d a t e d
begin
find m i n i m u m of t h e d i s t a n c e e n t r i e s D T m i n
begin
cM1 D e l e t e _ R L i s t (n) ;
R e t r a n s m i s s i o n C o u n t e r +- z;
i f ( D ~ si ' = D T m i n )
end
then
n s +-- s i3
3
Procedure
U p d a t e ( i , k)
w h e n r o u t e r i receives an u p d a t e on link (i, k)
begin
s e n d A C K to n e i g h b o r k
R e t r a n s m i s s i o n C o u n t e r t - z;
Retre, n s m i s s i o n T i m e r t - x;
(0)
begin
update=0;
R T E M P i +- 4;
D T E M P i,b +- r for atl n e i g h b o r s b
(1)
For e a c h t r i p l e t (3, D jk, p jk) in v k , i , 3
e l s e n s +- b I {b q N i a n d D i
while
V bSNi}
d o x +- p lx u s ,
r i do
s e q n o +-- s e q n e +
1;
then call R T _ U p d a t e
end
begin if (RTEMP i ~ r then
for each neighbor b do begin
f o r e a c h t r i p l e t t = ( j ., D ji , p 3i) in R T E M P
(4)
(D~ n ~ = Min{Dizb
a n d . D x~n s
call p r o c e d u r e D T
begin
i f t h e r e a r e b a n d j such t h a t
(3)
jb = DTmin};
x~j;
end
else begin
if(D~ < co) then begin
a e q n o +- s e q n o + 1;
a d d (0, 3, oo, null, s e q n o ) t o L I S T i ( x ) Vx q Ni;
cMl C l e a n . . R L i s t ( seqno)
callCreate.RList (seqno)
end
D :i. ~ oo; PJi ~- null; s .7
i +- n u l l
do begin
i f b is n o t in t h e p a t h f r o m i to 3
t h e n D T E M P i,b +- D T B M P i,b ~J t;
end
s e n d D T E M P i,b to n e i g h b o r b;
end
end
end
end
end
The path f r o m p t o j (which is implied by the predecessor information reported by p) does not include node
i.
| D~p < D}x for any other neighbor x, and Diyp < Dy x
for any other neighbor x and for every node y in the
path from i toj.
The above means that node i chooses n o d e p as its successor to a destinationj if that neighbor appears to offer
a smallest-cost loop-free path t o j and all the intermediate nodes in the path toj.
When node i sends an update message, it updates its
message retransmission list. For each destination j for
w h o m an update is being reported, node i sets the ackrequired flag for all its neighbors. It also adds an entry in
the message-retransmission list containing the sequence
number given to the update message, and starts the
retransmission timer for that entry.
Decrement the retransmission counter of all the existing entries in the MRL.
Processing an A CK." An A C K entry in an update message refers to another entire update message, i.e., it
acknowledges all the updates included in the update message bearing the referenced sequence number. There-
188
(0,J)
(0,J)
(1,K)
(infinity,-)
(a)
(o,J)
(infinity,-)
(b)
(o,J)
(c)
(11,B)
(d)
All links and nodes are assumed to have the same propagation delays. Link-costs are as indicated in the figure.
Node i is the source node, j is the destination node and
nodes k and b are the neighbors of node i. The arrows
next to links indicate the direction of updates messages
and the label in parentheses gives the distance and the
predecessor to destination j. Each update will be
acknowledged by an A C K message from the neighbor.
ACKs are not shown in the figure. The figure focuses on
update messages to destinationj only.
When link (]', k) fails, n o d e s j and k send update messages to their neighboring nodes as shown in Fig. 3(b). In
this example, node k is forced to report an infinite distance t o j as nodes b and i have reported node k as part of
their path to destination j. Node b processes node k's
update and selects link (b,j) to destination j. This is
because of step 2 of W R P which forces node b to purge
any path to node j involving node k. Also, when i gets
node k's update message, i updates its distance table
entry through neighbor k and checks for the possible
paths to destination j through any other neighboring
nodes. Thus, a node examines the available paths
through its other neighboring nodes and updates the distance and the routing table entries accordingly. This
results in the selection of the link (i,j) to the destinationj
(Fig. 3(c)). When node i receives neighbor b's update
reporting an infinite distance, node i does not have to
update its routing table as it already has correct path
information (Fig. 3(d)). Similarly, updates sent by node
k reporting a distance of 11 to destinationj will not affect
the path information of nodes i and b. This illustrates
how the method used in W R P to update a node's distance table (step 2 in Procedure DT) helps in the reduction of the formation of temporary loops in the explicit
paths.
2.5. Example
3. C o r r e c t n e s s o f W R P
In this section, we show that the basic routing algorithm used in W R P is correct. The following assump-
I89
L e m m a 2. When a node comes up and initializes its distance table, the link weight that can be extracted from
any of its distance table entries is the weight of the link.
Proof. The change in the link cost can be due to the link
coming up, the link going down, or the cost of the link
changing.
When a link comes up, a new column entry will be
added to the distance table and the new link cost will be
assigned to the corresponding entry in the distance table.
Procedure RT_Update will be called, which eventually
updates the routing table entry.
When a link goes down, the column entry will be
deleted and the distance entries in the distance table will
be set to ec. The procedure RT_Update again updates
the routing table entries accordingly.
When the link cost changes, the distance entry in the
distance table is updated to reflect the new link cost
(step 1 and step 2). These changes will be updated in the
routing table again by the procedure RT_Update.
F r o m assumption (7) we have that any change that
occurs in the time interval (0, T) will be updated by time
T. This implies that the link cost changes will be reflected
in the distance and routing tables of nodes adjacent to
the links within a finite time T.
D
P r o p e r t y 1. After a finite time interval T, the routing
table structures at all routers will form the final shortest
path.
190
Proof. Let T(K = 0) be the initial time when the algorithm begins execution. The theorem is true for K = 0
since no link exists between routers at time t = 0.
Assume that the property is true for T(M),
0 ~ M ~<K - 1. By time T(K), all the routing changes at
time T ( K - 1) would have been communicated to all
routers (assumption). N o router wilt be marked as undetermined as all the distance entries are finite.
When a router recovers, within a time T(K - 1), the
information about the change in the link cost will be
communicated within a finite time (by Lemma 3). As all
the entries in the table are finite, a path can be extracted
from any router i to any other router j by traversing
through the distance and the routing tables.
When a particular link is selected as a path from i to
j, the loop freeness of the path is checked in step 2 and
RT_Update. An update message about the link cost
change will be sent to the neighbor. The loop-freeness of
the update messages can be verified by traversing from
destination router to the source router using predecessor
information present in each entry of the distance and
routing tables.
Therefore, the paths in the final graph are loopfree.
[]
The following theorems prove that PFA terminates
in such a way that the distance to any other router maintained in the routing table in each router is the shortest
distance of the final graph and the distance to any
unreachable router is marked as undetermined.
P r o p e r t y 2. If r o u t e r j is not connected to router i in the
final topology, then the distance between the two routers
is equal to infinity for all time after T(H(i, oc) + 1).
Proof.
191
The RT_Update procedure is called in the update routine after updating all the distance table entries of that
router. This routine picks up a minimum entry through
one of its neighbors and will have a successful trace for
the destination router j and thus will have
D~ ---- D~. = D f dii, = D} a n d s } = b.
[]
4. C o m p l e x i t y analysis
WRP's time complexity is O(h) in the worst-case,
where h is the height of the routing tree. Theorem 4 below
proves this result. Time complexity is defined as the largest time that can elapse between the moment T when
the last topology change occurs and the moment at
which all the routers have final shortest path and distances to all other routers. Communication complexity is
defined as the maximum number of node identities
Proof.
j~
f-JJl
j.
2 . ~:J-
Fig. 4. Complexity.
~f-
192
5. S i m u l a t i o n results
193
60
PFA
DBF
DUAL
ILS
10000
t +,
9
+
o
,~
--
7 - - - ' - -
PFA
DBF
DUAL
50
-4,
!-
9
+
ILS
40
O3
Lu
1000
ii
<
co
co
,
~, oe:=
;,
ii
i
II+,L~T+TI!+=.-:jl
30
i i~i~iii.
20
100
10
10
~;II;;~;TIII?;;~=;;II;
;:%o;;~I=i=
'~oloi??i~
:i=: =, i i==,==i I,=~..III~H ii==i.i~ ~ i ! ~i~ii!~?i .~ii~!?i ~!II.~I!~Y
'i *iii ' hi :~' HII=!II IIeI:J'HIIH
lli[tlH!i!l!HIIIII]t lTtlll,th,lll,,tllll,
11111111111
..........................
....... '] I]11/
................
11111'1[I]]
IIIIH]lllllJiliiii'Itlt!1!1!
0
10
20
30
40
LINK FAILURES
50
10
70
60
Fig. 5, A R P A N E T
20
30
40
LINK FAILURES
50
60
70
l i n k failure.
20
350
PFA *
DBF ,DUAL ,:,
ILS x
300
PFA ,,
DBF +
DUAL o
ILS ,,
250
O3
LU
(5
<
co
O3
w
200
:
150
x x
,x,
:T ; X
l.x i
~ x
~ IX :
i,
~
xx
' 'xx' 'u
xx
X
i iu
X ~ : I I ~~ I
~} iill~
9 x~
'~u
,i ] :T
i
~ xx
:~ xu +., x
~X : I X : :
x
, xx,~
,XX:x,
,::
iiiixi!ii~i~ixilEiFtlil
: ~X~:
co
n
ILl
l.-O3
x
x.u
: :x
~ ~i[i~i
10
li~,4i==;i~i=='H
, ilTfi~fiiii~ii:,Ttii4il;i~i~il;illJ;Tfi~tilLiiJlt;
50
ii
.... HI
li
tl
i I ~llii~i
I !!
'
9,T TiTI
J+',iTTI
i!I it iI,Tf+ITII
I*l(lllllltlllllll~lll[llll:tlllllllllll~l
III1~1~11
il
tIHIIII
[1[1[1+[i
10
20
30
40
LINK RECOVERIES
50
80
/!Lr
!1 iI
LIIIIIlllLIIIIIllll
II I
]lll
II//
I[l~ltl[l[llllll
11+1
Fig, 6. A R P A N E T
10
link recovery.
20
30
40
LINK RECOVERIES
50
60
70
S. Murthy, J.J. Gar cia-Luna-Aceves / An efficient routing pro toeol for wireless networks
194
PFA 9
DBF +
DUAL
ILS x
50
10000
TttttT~t~t1~ttttT~T;ttTTtt~ttt!tt~ttTt~ttTtTt
ttttttttttttttt+ttttttttttttttt*ttttttttttttttt
!!iiiiiiiiii!iiiiiiiiiiiiii!!!!!iiiiiiii!!i!!
(,9
ILl
(5
<
U)
U.I
PFA .
DBF *
DUAL
ILS
60
!iiiii!iiiiiiii!ililiiii!!iii!!iiiiii!iiiiii!i
ilili~,~,,,,,,,,,~,,~,li!iiiii!*!iiiiiiiiiiiil
4O
iiiii!iiiiiiiiiii!iiiiiiii!!i!iiiiiiiiiiiiiii
o'3
ri
moo
~(,9
ii[!;iiiiiiiii!i!iiiiiiii!iiii;!il;iiiiiiii[!
30
iiii!iiii+iiii+iiiiiiiiiiiiiiii!iiiiiiiiiiiiii
iiiiliiiliiiiiiiiiiii'"'i;iiiiiilili!,,,,
iii,iiiiiiiiiiiiiii!!iiiiiii!i!iiiiiii!iiii
,,,,,,~,~,"'"
~ii~iiiiiiiiiiiii;i!!;!iiiiiii;;;i;iii!i;iii
L~t
*o o. . . . .
,~
,,,~
....
20
=~,,t,=,~,
i i i i i i , i i l l i i i l l , l l l l l l l l , l l l l i l t l l l l t l i l l l
::::::::::::::::::::::::::::::::::::::::::::::
;iliiiliiiiiiiiiilliiil;;;i;;;ili~;i;;;;i~;~;;
LLI
~ITIIITIIIiTTT+?*TiTi;;I***;IT+*I*IIT+r
10
iT
IIIII~jTflI~IIT~I
'00IIIIIIII[[IIIflIliTIIIIT
.............
IIIIIIIIII[TtlTII[Ilill
0
10
15
20
25
30
NODE FAILURES
35
40
45
~IT11rIIIIT11
lIJ
III
ti!lll]t[llillll/llllllllllllllllttllllltlllll
0
50
10
15
20
25
30
NODE FAILURES
35
40
45
50
400
+
PFA
DBF
DUAL
ILS
,
i+
,,
i
1?,~
"ii'ii
~|
ii:
ele l++I~,
i+IIii
lliiii ,
,;~ ~ Itl
10
i/iTll JTI?i,,"'I+THli
ItTTTTI,T@,/WT@T,tTTI
*T
iliil!l//II/li!/ITl*tIIliT/l|
/
I
I
50
9
+
o
x
15
t
x
:
250
The graphs in Figs. 5 and 6 depict the number of messages exchanged and the number of steps required before
PFA, DBF, D U A L , and ILS converge for every link failing and recovering in the A R P A N E T topology. We
focus more on the results for the A R P A N E T topology,
PFA *
DBF +
DUAL o
ILS
450
300
20
500
350
to itself. Data are collected for a large number of topology changes to determine statistical distribution. The
statistics has been collected after each failure and recovery of a link. To obtain the average figures, we make
each link (or node) in the network fail and count the
number of steps and messages required for each algorithm to converge. Then the same link (node) is made to
recover and the process is repeated. The average is taken
over all failures and recoveries. Again, this message
count is not exact, but the relative difference from one
protocol to another is accurate.
iiiiJllllll
E I/I{I/|IIIIIITIIIjI~I
I
II
II
IIIlillllllll]llllllll
I
I
IIIII
10
15
20
25
30
35
40
45
lIIil
Illl
Illll
' t TT'
lllI
llil
[ liJIi
{Iii
frill
IIII
IIII
50
NODERECOVERIES
Fig. 8. A R P A N E T node recovery.
10
15
20
25
30
35
NODE RECOVERIES
40
45
50
100.0
.,
. . ,
. . ,
. . ,
.,
o9
W
,<
o~
o9
LU
10.00
PFA
DBF
DUAL
ILS
195
-"--.....
.-~ ....
......
PFA
DBF
DUAL
ILS
"1"
--*--~--.~
....
....
t.,.9
Z
LU
(.9
,,=,
e~
09
o9
10.0
. . . . . . . . . . . . -;......T.. _ : .-'.'._.-cz--n~.=~ ~-
1.00
LIJ
3E
LU
z
la.i
1.0
1.0
10.0
.i
100.0
INTERARRIVAL
. . ,
1000.0
TIME
.,
0.10
10000.0
1.0
10.0
100.0
INTERARRIVAL
1000.0
TIME
10000.0
Fig. 9. Los-Nettos.
100.0
-.,
.,
. . ,
. . ,
.,
PFA
DBF
DUAL
ILS
-*---~--"-~ ....
~--
I 0 . 0 0 ,
PFA
DBF
.....
D U A L --~.....
I L S - * .....
-rl-Z
w
"-5
,<
o9
co
rr'
w
>
10.0
.
1.0
. .
10.0
. . . . . . . . . .
100.0
1000.0
INTERARR1VAL
T~ME
0.10
.
10000.0
1.0
10.0
. . . .
100.0
~NTERARRIVAL
. . . .
1000.0
TIME
,
10000.0
196
100.0
..
..,
..
PFA
-'.--
DBF
.....
DUAL
.,
,,
. . ,
. . ,
.,
PFA
-.--
DBF -+---
DUAL -.D....
. . e ....
~C
.~ .............. ~,,,
er
...---~"-~
UJ
m
1,00
W
C~
<
etLU
>
'"'"~'
9 1
1,0
,,
10.0
'...%
,i
100.0
..o .
,1
1000.0
/"
,i
,i
10000.0
1.0
,i
10.0
,i
100.0
,i
1000.0
,i
10000.0
INTERARRIVAL TIME
INTERARRIVAL TIME
zation mechanism spans the entire diameter of the network. ILS sends maximum number of messages since the
complete topology information has to be exchanged
between neighbors every time the topology changes.
The average length of each message is the highest in
D U A L as compared to all other algorithms. The average
message length in case of ILS is almost constant since it
always sends the complete topology information. Even
though we do not have simulation results for ILS in case
of A R P A N E T , topology, we can extrapolate the results
from the other two network topologies and can expect
similar behavior for A R P A N E T topology also.
6. C o n c l u s i o n
A new routing protocol, WRP, for a wireless network
has been presented. This protocol is based on a pathfinding algorithm which substantially reduces the number of cases in which routing loops can occur. A mechanism has been proposed for the reliable exchange of
update messages as part of WRP. The basic algorithm
used in W R P has been proved to be correct and WRP's
complexity has been analyzed. The performance of the
routing algorithm in W R P has been compared with that
of an ideal topology broadcast algorithm (ILS), D U A L
and DBF for highly dynamic environment through
simulations. The simulation results show that W R P
provides about 50% improvement in the convergence
time as compared to D U A L . The results indicate that
W R P is an excellent alternative for routing in wireless
networks.
References
[1] R. Albrightson, LJ. Garcia-Luna-Acevesand J. Boyle,EIGRPA fast routing protocol based on distance vectors, Proc.
Networld/Interop 94, Las Vegas,Nevada (May 1994).
[2] D. Beyeret al., Packet radio network research, developmentand
application, Proc. SHAPE Conf. on Packet Radio, Amsterdam
(1989).
197