Subject: Re: uni-directional links discussions in DSR draft

From: daniel russo <[email-masked]>
Date: Thu, 28 Dec 2000 15:21:11 -0500

Hi Li,

Routing protocols such as DSDV, AODV and TORA don't work correctly with
unidirectional links because they assume all links are bidirectional,
while routing protocols such as DSR state they can work with
unidirectional links (or so the internet draft states, but in DSR's case
the ns-2 implementation actually has similar problems as AODV, DSDV and
TORA, because it Caches the reverse route when doing "route discovery"). 

In the following network we have paths to and from each node, but there
are unidirectional links from B to C and from E to D. The rest of the
links are bi-directional.

        A ----- B ----> C
        |               |
        |               |
        D <---- E ----- F

Protocols which make the explicit assumption that ALL links are
bidirectional will cause problems with routing. "Cache the reverse
route" like AODV, TORA, DSR (ns-2 implementation) do will never find a
route in the above network diagram, and cause nodes along the path to
hold incorrect routes to the source. 
i.e. Node A initiates a ROUTE REQUEST to find a route to node E. As the
ROUTE REQUEST propagates towards E it crosses a unidirectional link from
B to C. When node E receives the ROUTE REQUEST it flips the route and
sends the ROUTE REPLY back to A along the path E F C B A, but it cannot
cross the unidirectional link C to B, thus the ROUTE REPLY is dropped.
After the timeout period node S tries again, and again it fails.

DSR warns dosent warns against using the reverse route (but then uses in
in the ns-2 implementation), AODV go one step further than DSR and
explicitly build the process of caching the "reverse routes" into the
protocol, and TORA is based on the reversal of routes along the downward
flow of routes in the network, and it does such things as caluculate the
hights of such flows (i.e. routes) and reverses them.

Also DSDV has different flaw:
When a node S receives a route table update from a neighbor D, node S
automatically assumes that it can be heard by D, and reflects this in
its own routing table as a one hop bidirectional link. If there exists a
unidirectional link from S to D, then when the time comes to send a
packet from S to D the packet transmission will fail and node S will
have to buffer this packet until another route is found via the periodic
update algorithm. If another route exists it will take quite a time
before another route table propagates around to S, but since node S will
keep hearing updates from D it will keep thinking there is a one hop
link, thus never correcting this problem, which results in S never being
able to reach node D.

This has been the subject of our work for the last couple of years, any
input would be appreciated on the above discussion. A paper will be
avilable shortly on this topic with results comparing and contrasting
the above protcols preformance with ns-2 with undirectional links. 
Also I shouldn note  solutions to the unidirectional link problem have
already been presented at the network layer level by Carlos A.
Pomalaza-Raez, Lichun Bao and J.J. Garcia-Luna-Aceves (ULP) and Ravi
Prakash. Also Ravi Prakash and Sanket Negasari have presented a solution
at the MAC layer to allow these network layer protocols to function
correcly.

thanks,
daniel

Li Li wrote:
> 
> In the DSR draft, it says "Although many routing protocols operate correctly
> only over bi-directional links, DSR can successfully discover and forward
> packets over paths that contain uni-directional links."
> 
> I am interested to know which routing protocols do not work correctly over
> uni-directional links.
> 
> For DSR to take advantage of uni-directional links (assume a compatible
> MAC), DSR requires the route request destination do a seperate route
> discovery. Route caching has to be careful to distinguish uni-directional
> and bidirectional links. Are these the complete picture for DSR to factor in
> uni-directional links?
> 
> Thanks,
> 
> Li