Subject: Re: [manet] Distance vector routing and adhoc

From: Joe Macker <[email-masked]>
Date: Fri, 27 Jun 2003 14:52:50 -0400

As far as WG documents AODV comes to mind..

At 09:29 AM 6/27/2003 +0200, Christophe Jelger wrote:
>Hi all,
>
>I am relatively unfamiliar with some aspects of adhoc routing and was
>wondering if people could point me to some key papers describing the
>performance (and potential problems) of distance vector routing in adhoc
>networks. I know it is probably not the best way for routing in such
>networks but I'd like to know what optimizations have been proposed in order
>to increase the efficiency of distance vector routing in adhoc networks. In
>particular, I'd like to know if there are some relatively well admitted
>methods for optimizations.
>
>Thanks in advance and apologies for the (quite) silly question. ;-)
>
>Regards,
>
>Christophe
>
>
>
>_______________________________________________
>manet mailing list
>[email-masked]
>https://www1.ietf.org/mailman/listinfo/manet

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: "Christophe Jelger" <[email-masked]>
Date: Mon, 30 Jun 2003 09:21:33 +0200

Hi,

I forgot to mention that I was rather interested by proactive protocols,
i.e. a distance vector algorithm that maintains routing tables in a
continuous way (like RIP for wired networks).

Cheers,

Christophe

---

From: "Christophe Jelger" <[email-masked]>
Date: Mon, 30 Jun 2003 15:32:41 +0200

Hi,

For people aware of the paper "Internet connectivity for mobile adhoc
networks" by Perkins et al that appears in "Wireless Communications and
Mobile Computing", 2, pp.465-482, 2002 (Wiley) (and also sorry for the
length of this email).

It is stated in this paper that an AODV node that has a default route to an
Internet Gateway, should make a route request before sending the packet if
shortest route is required. In clear and because AODV is a reactive
protocol, before sending the packet to the gateway, check if there a direct
route to the destination (i.e. to check if the destination is in the adhoc
network).

I personaly think that it is somehow strange to use a default route with a
reactive protocol, because it "stops" the protocol from being reactive
(there is a default route !). That is why the above paper specifies that is
"shortest route" is required an AODV node should first send a route request
to find a better route. In other words, if shortest route is required it is
the same to remove the default route, with the Internet Gateway responding
to route requests for destinations outside the adhoc network.

These thoughts are, however, personal opinions about the paper. My main
concerns about this proposal are such :

1. In usual operating systems (Linux, BSD, Windows), the routing daemon is
in charge for populating the routing table. The OS then uses the routing
table information to forward packets. In the paper referenced above, this
behaviour is "corrupted" : the OS, when about to forward a packet, must
initiate the discovery of a route (by sending a request to the routing
daemon). From an enginneering point of you (the E in IETF), I wonder if this
behaviour is acceptable (needs strong modifications in the OS kernel code).
I don't know if the authors are members of the list but I would appreciate
to have their opinion (keeping in mind that their paper is research) and
also, of course, the opinion of other members of the list.

2. It is mentioned in the paper that the gateway information should be kept
as such in the routing table : a default entry to the gateway, and a host
entry to the gateway. That means that the OS should perform a double lookup
operation : to send packet to X, check route to X (default and find next hop
is gateway), then check route to gateway (and find next hop direct
neighbor). To my personal knowledge (I did tests with FreeBSD), this cannot
be done in modern operating systems (although some people told me it is
possible but did not tell me how ...). Also, I think it would be better to
keep the "next hop" philosophy and install a default via the next hop
(direct neighbor)  to the gateway (default route is next hop to the
gateway). Could I please have other peoples' opinions on this subject ?

Thanks,

Christophe Jelger

---------------------------------------------------------------
Christophe Jelger - LSIIT           [email-masked]
Université Louis Pasteur
Strasbourg - France                   Tel: +33 (0)3 90 24 45 90

http://www-r2.u-strasbg.fr/~jelger
---------------------------------------------------------------

---

From: Ryuji Wakikawa<[email-masked]>
Date: Tue, 01 Jul 2003 01:03:39 +0900

Hi Christophe.

At Mon, 30 Jun 2003 15:32:41 +0200,
> Mobile Computing", 2, pp.465-482, 2002 (Wiley) (and also sorry for the

Yes, I am co-author of that paper.

> route to the destination (i.e. to check if the destination is in the adhoc

correct.

> to route requests for destinations outside the adhoc network.

see below comment

> also, of course, the opinion of other members of the list.

I think your comment here is not only for AODV global connectivity,
but is for all reactive protocols.

> The OS, when about to forward a packet, must
> daemon).

This is how I implemented AODV6:)

The operations of handling the default route is similar to normal AODV
operation.

When an aodv6 nodeA sends packets to another aodv6 nodeB, it issues
RREQ for the destination because there is no route.  The nodeA
queues the outgoing packets until the route of the nodeB is
discovered. If there is no route, it gives up sending the packets.

When an aodv6 nodeA sends packets to another aodv6 nodeB, it issues
RREQ for the destination, because there is no route. The nodeA queues
the outgoing packets until route is discovered. If the route is not
discovered, the nodeA uses the default route.

Can you see big differences?

One more note: 
We sometime assumed that each MANET clouds has manet specific prefix
for inner routing (inside manet).  
See draft-perkins-manet-autoconf-01.txt. The title is "IP Address
Autoconfiguration for Ad Hoc Networks"

All manet nodes have site-local address as a MANET specific address
and may also acquire a global address if it is needed. If a
destination is site-local address (i.e. the destination must be
located inside the manet cloud), the sender discovers a route by
RREQ. If a destination is global address, the sender just routes
packets to the default route.  This is simple.

> gateway). Could I please have other peoples' opinions on this subject ?

One of advantage of this configuration is that even if a neighbor
node towards a gateway is changed due to movements, the default route
is not expired. Only the host route is deleted from the routing table.
Manet node just requests the host route towards the gateway by RREQ.
The host route may be fixed by local-repair.

About the philosophy, you can configure two routes for a destination on BSD.
Check your routing table. sometime the default route is configured as
follows on BSD.
   default-route  -> gw global-addr
   gw global-addr -> gw MAC-addr

AFAIK, implementing "recursive routing table search" is easier than
you expect;-)

The latest document is draft-wakikawa-manet-globalv6-02.txt
You may be able to find more information.

regards,
ryuji