Subject: DSR - Problem with ARP

From: Aaditeshwar Seth <[email-masked]>
Date: Sat, 7 Jul 2001 16:53:01 +0800 (SGT)

Hello Sirs,

I am a final year CSE B-Tech student at IIT-Kanpur, India, and am doing
a bit of work on the MANET protocols when unidirectional links can also
exist. My query is about DSR's policies in the case of unidirectional
links. Consider a scenario, when a source needs a route to a
destination, and unidirectional links can exist along this route.
According to the RFC:

1. When a node receives a ROUTE REQUEST, it adds its IP-address to
the source route that the request has travelled so far, and  simply
rebroadcasts it. This broadcast may even travel over a unidirectional
link, where the receiving node will not be able to send packets back
along the same link.
2. When the REQUEST gets to the destination, it now has to send a ROUTE
REPLY back to the source. It will not reverse the route that the request
took, since the request might have travelled over a unidirectional link.
Therefore, it will generate a fresh route request for the source, and
piggy-back the route-reply on it. 
2. So-Far-So-Good. The source finally recieves the piggy-backed ROUTE
REPLY, and source-routes all data packets meant for the destination.
3. As the data packet travels over the source-route, the intermediate
nodes extract the next-hop IP address from the source-route and unicasts
the packet to the next-hop. This unicasting will however require the
MAC address of the next-hop (not only the IP address), and therefore will
issue an ARP request for the same.
4. Suppose that this link is unidirectional - in that case, the present
node will not receive the ARP reply at all, and will keep retransmitting
ARP requests, and finally drop packets or maybe send back a route-error,
etc, and not be able to take advantage of the unidirectional link.

What should be done in this case? One alternative is to MAC-broadcast but
IP-unicast the data-packet - any better method apart from this?

Please do revert back as soon as possible.

Thanking you,
Yours sincerely,
Aaditeshwar.

---

From: Yih-Chun Hu <[email-masked]>
Date: Sat, 7 Jul 2001 23:27:34 -0400 (EDT)

Hi Aaditeshwar,

Thanks for your interest in DSR and your comments.

The MAC broadcast and IP unicast approach may cause additional power
expenditure and additional interference in MACs providing power control,
so I agree that this isn't an optimal solution, since it would affect all
packets traversing a unidrectional link. 

There are two alternate solutions for this. One is to provide a
manet-level protocol for ARPing over multihop paths. The other is to
assume that any link layer providing a unidirectional link also provides
bidirectional IP-to-MAC address resolution, as is required for normal IP
to work.

Thanks,
Yih-Chun

---

From: [email-masked] (Amritansh Raghav)
Date: Mon, 9 Jul 2001 11:16:21 -0700

you cant MAC broadcast and IP Unicast data. A lot of TCP/IP stacks will
throw away such packets
(I think Host Requirements might say something about this, but I havent
checked)

-----Original Message-----
From: [email-masked]
[mailto:[email-masked]]On Behalf Of Aaditeshwar Seth
Sent: Saturday, July 07, 2001 1:53 AM
To: [email-masked]; [email-masked]; [email-masked];
[email-masked]
Cc: [email-masked]
Subject: DSR - Problem with ARP

Hello Sirs,

Thanking you,
Yours sincerely,
Aaditeshwar.

---

From: Kui Wu <[email-masked]>
Date: Mon, 9 Jul 2001 12:07:07 -0600 (MDT)

> bidirectional IP-to-MAC address resolution, as is required for normal IP
 
   I would like to know more details about method 1.
   It seems that method 2 is not a solution, since it is just an
assumption. The problem is what is the method to make the assumption
realistic.
   ARPing in unidirectional link is likely to be a problem not only in
DSR...
   My opinion is that MAC broadcast may be a good solution, considering
the additional cost for the "ARP" solution in the networks with  
unidirectional links.

Kui

---

From: Aaditeshwar Seth <[email-masked]>
Date: Tue, 10 Jul 2001 06:42:22 +0800 (SGT)

Hello everyone,

> the additional cost for the "ARP" solution in the networks with  

Even I think that this is not altogether a bad idea, because any kind
of higher level protocol that we might build up will have it's own
additional overheads. A bit of contemplation on an optimal structure
of this protocol will reveal that it will definitely involve a number of
broadcasts (which essentially implies MAC broadcasts) at various stages.
These broadcast packets might be smaller for this multihop ARP protocol
than the original data-packet requiring a broadcast, but even so, a
MAC-broadcast and IP-unicast for the data-packet can be assumed not to
hamper the network-loading around the nodes to a great extent.

Infact, in a related exercise, I have been experimenting on NS-2 with a
variation of the AODV and DSR protocols in the presense of unidirectional
links, and seeing whether special software ACKs (like the DSR-ACKs that
the DSR draft talks about) are required for reliable transmission over a
unidirectional link, or is a simple MAC-broadcast without any ACKs also
doable (I am assuming no higher level ARP protocol, and therefore using
the same solution of a MAC broadcast and IP unicast over a unidirectional
link). This hybrid-protocol that I am talking about, is more similar to
AODV than to DSR, and therfore software ACKs requiring a new
route-discovery from the next-hop to the previous-hop nodes turns out to
be very expensive. Such a scheme is easier with pure-DSR because of it's
high cache-hit ratio. My results came out that simple MAC-broadcasts were
OK enough and gave slightly better performance than when specific software
ACKs and additional route-discoveries are required. This becomes more
evident in cases of high mobility - as can also be logically expected.

Therefore, even in the case of ARP, I think that the MAC-broadcast
solution should be doable enough - assuming ofcourse that such a thing
will work with all actual stack-implementations - making it work with NS-2
was quite easy!!

Regards,
Aaditeshwar.

---

From: daniel russo <[email-masked]>
Date: Wed, 11 Jul 2001 01:53:05 -0400

Hi Aaditeshwar,

We came accross the same issues when working on network layer protocols
that work correctly using undirectional links. Using ns-2 with 802.11
and ARP stopped us from unicasting a packet accross a unidirectional
link. We came up with 2 solutions for getting the MAC layer to use
unidirectional links in a *reliable* manner. Simple MAC-broadcasts
accross unidirectional links do not provide a reliable service to the
layers above.

First and for-"least", we modified ns-2 802.11 implementaion to use a
flag in the header of the IP packet which the network layer set to tell
the MAC layer that this packet is being sent accross a undirectional
link. This node's network layer sends the packet and awaits a
network-layer-ACK. When this nodes MAC layer receives it, because the
the unidirectional flag was set it broadcasts the packet. The destined
receiving node at the network layer sends a network-layer-ACK packet
back to the node along some other multihop path (since it was
unidrectional link), preventing the sending node from retransmitting the
packet. Keep in mind I modified ns-2 in this manner just to make use of
unidirectional links painlessly and quickly, and no real metrics were
taken regarding this. This idea does make the network layer provide the
reliability for packets sent accross unidirectional links, and somewhat
merges the services provided between layers.

The second solution is documented and is a much more polished solution,
it is presented in a paper done by Sanket Nesargi and Ravi Prakash
entiled "A Tunneling Approach to Routing with Undirectional Links in
Mobile Ad-Hoc Networks". But I beleive they keep a bigger distinction
between the network layer and the MAC sublayer. You can contact myself,
Sanket Nesargi or Ravi Prakash for the paper. Any feed back would be
appreciated by those authors and myself as you seem to have thought
about this issue in detail coming from a similar starting point.

thanks,
daniel

---

From: Aaditeshwar Seth <[email-masked]>
Date: Wed, 11 Jul 2001 20:16:00 +0800 (SGT)

Hi Daniel,

Thanks a lot for the feedback.

Getting network-layer ACKs is definitely a solution for ensuring reliable
delivery, but as I wrote earlier - this requires a route-discovery from
the next-hop node to the previous-hop node. The route-discoveries do not
affect performance much in the case of DSR, because there's a good chance
that the node might have promiscously overheard a route. In the case of
AODV however, these route-discoveries hamper performance, and infact -
for high mobility the delays and route-loads go up by more than what
the delivery fraction is able to improve itself when these ACKs are used.
Ofcourse, I was using simple CBR packets here - had I used TCP, then I
know that the results would have been miserable without ACKs!! :-)

And please do send over the paper to me - I'm quite interested in this
problem!

Thanks a lot,
Aaditeshwar.

---

From: "Philippe Jacquet" <[email-masked]>
Date: Thu, 12 Jul 2001 01:10:10 +0200

The MAC broadcast of IP unicast is dangerous because it will be received by
other nodes that may reforward the packet and cause permanent loops. I have
no idea about multihop ARP, I guess it would be difficult to implement.
Maybe a *standard* solution could be to tunnel IP packets over
unidirectional links and to use MAC broadcast over tunnelled IP packets. But
this is not very reliable and there should be a way to make packets going
through bidirectional links in priority.

In the extension of OLSR about unidirectional links we assume that the nodes
handling unidirectional links have specific capabilities (UD-nodes) and that
the unidirectional links are detected.  I am not sure whether DSR has some
way to detect unidirectional links (like the black-list in AODV). I never
received clear answers about this topic.

Philippe

----- Original Message -----
From: Yih-Chun Hu <[email-masked]>
To: Aaditeshwar Seth <[email-masked]>
Cc: Dave Johnson <[email-masked]>; Jorjeta Jetcheva <[email-masked]>;
<[email-masked]>
Sent: Sunday, July 08, 2001 5:27 AM
Subject: Re: DSR - Problem with ARP

---

From: [email-masked] (Amritansh Raghav)
Date: Mon, 9 Jul 2001 11:16:21 -0700

-----Original Message-----

Hello Sirs,

Thanking you,
Yours sincerely,
Aaditeshwar.

---

From: daniel russo <[email-masked]>
Date: Wed, 11 Jul 2001 21:41:30 -0400

Philippe Jacquet wrote:
> other nodes that may reforward the packet and cause permanent loops. 

Hi Philippe,

yes this is one issue i forgot to mention when outlining the method i
used to be able to use undirectional links:

To prevent acknowledgement explosions when the return route (in which
the acknowledgement is traveling back to the source node) has a
unidirectional link, the MAC sublayer in the nodes along the return path
will not have to acknowledge the packet (so the bit in the IP header
will signify this), also the network layer at the receiving end of the
ack-unidirectional link will *not* be require to send an acknowledge for
the acknowledgment. Thus the network layer can provide the extra
reliability that the MAC sublayer has lost due to the added
functionality. The application cannot tell the difference, apart from a
slightly larger delay for packets sent across a unidirectional link.
This does add extra functionality to the network layer to take on the
task of reliability for this special case, as it is the network layer
that will do retransmissions.

thanks,
daniel

---

From: daniel russo <[email-masked]>
Date: Wed, 11 Jul 2001 21:41:48 -0400

Hi Aaditeshwar,

At what path lengths to these route-discoveries hamper performance? 
I'd like to know more about your results, things such as the the average
path lengh using the unidirectional link vs not using the link. I would
think what needs to be seen is the benifit of using unidirectional
links, and if the paths are not significantly made shorter by the use of
the unidirectional link and the route-discoveries hamper performance
then these results are not as significant. If the paths *are*  made
significantly shorter by the use of the unidirectional link and the
route-discoveries *still* hamper performance then this is means that we
would not need to go into the extra complexity of using the
unidirectional link, which is quite a significant result. At what path
length is the line drawn? 
Possibly, the most important question here might be found in discovering
the real occurence of unidirectional links in manets; exactly how often
they occur and how much shorter are paths made by using the links. Using
ns-2 we create unidirectional links through disparity in signal strengh
between nodes using power depeltion algorithms and also currently we are
working on a simple random distribution of unidirectional links, but how
do these models reflect actual RF propagation with both transitive and
static undirectional links?

thanks,
daniel

---

From: Aaditeshwar Seth <[email-masked]>
Date: Thu, 12 Jul 2001 13:41:38 +0800 (SGT)

Hi,

> length is the line drawn? 

I don't have the original results with me anymore, but as far as I can
recall the graphs, the protocol that we are developing here was able to
improve its delivery-fractions by about 2% in low-mobility, but the
delays went up by much more.
Also, I feel that the path-length would not have been making much of a
difference here, but the number of unidirectional links that the routes
would be consisting. Not too sure on this though...

Actually, I extended the AODV and DSR implementations in ns-2.1b7a, and
included the `black-list' in AODV, and unidirectionality in DSR - in
compliance with their respective drafts. I am attaching a few .ps graphs
that I got when I ran AODV and DSR in the presense of unidirectional
links. Referring to [Dr. Das, et al] on the comparison of DSR and AODV,
it is clear that unidirectional links can make a lot of difference.

However, please excuse my being so naive on this, but whatever I've done
on MANETs has been mostly self-study, and therefore I'm not too certain
on the correct way to model unidirectional links. My modelling of
unidirectional links will definitely appear to be repulsive to a lot of
people!! :-) Actually, I just randomly increased the carrier-sense and the
receive thresholds of a few nodes, and this led to the formation of a
number of unidirectional links. Please do send in more ideas on how this
can be done - I really don't know much about it myself.

The details of the parametres:
- 512 byte packets
- 4 packets/sec
- Pause time from 0 to 900 sec
- Simulation time = 900 sec
- Graphs are of Delivery fraction for 20, 30, 40 sources

The parametres are very identical to those used in the Infocom paper on
the comparison of AODV and DSR by Dr. Das, et al.

Apparently, AODV was choosing bidirectional paths longer than DSR by about
25% on an average, but most of the plummetting fractions were caused
because AODV was not able to find a bidirectional route at all sometimes
inbetween. Furthermore, fresh route-discoveries in AODV were slower than
DSR, because AODV was using an expanding-ring mechanism, while DSR was
using a TTL 0 RREQ, followed by a maximal TTL RREQ. Since, most of these
routes were more than 3 hops, therefore it took AODV's expanding-ring much
longer to get the RREQ to the destination.
Infact, this is an improvement that can be made in AODV as such: Not to
start the expanding-ring from a MIN_TTL itself when a route-discovery
is being done for a second time, but from a TTL of the number of hops
that the destination was away when the older route was being used.

> static undirectional links?

Please do send in further details on the models that you are using to
create unidirectional links.

Thanks,
Aaditeshwar.

---

From: "Philippe Jacquet" <[email-masked]>
Date: Thu, 12 Jul 2001 22:31:57 +0200

Hi Daniel,

Consider a route A--B--C->D--E-- with CD unidirectional. If C retransmit
data packets to D on MAC broadcast mode, then B will also receive the data
packets and reforward them to C, creating a permanent loop. A tunnel on C->D
would be safer to avoid this.

By the way I remember heavy discussions during Hiperlan and IEEE 802.11
standard elaboration, about an option we presented in order to skip ACK for
some unicast packets. The option was rejected because it was considered too
hereteric. Of course it would be now of no help when ARP does not work.

Philippe