Subject: IP forwarding enhancement for on-demand routing

From: Bruno Husson <[email-masked]>
Date: Wed, 29 Nov 2000 17:06:58 +0100

Hi,

IP forwarding is commonly implemented like this on a router
(for instance FreeBSD or Linux):

Extract destination IP address, D, from datagram,
If D is on a directly connected network,
   deliver datagram to destination over that network
else if there is an entry in the routing table that fits D (by use of
mask for instance)
   then route the datargam to the specified next hop address
else (no entry is found in the routing table)
   declare a routing error, and send an ICMP error message.

This is in keeping with most routing algorithms which are proactive
(RIP, OSPF, BGP...). This implementation is not satisfying for
on-demand routing algorithms.

When considering a reactive (on-demand) routing algorithm,
the end of the IP forwarding algorithm should be modified like this:

...
else (no entry is found in the routing table)
 ask the routing algorithm for a new route towards D,
 (possibly) keep the datagram until a new route is calculated or until a

tempo expires
 when the new route is available, forward the datagram
 otherwise, after the tempo, declare a routing error, and send an ICMP
error message.

This seems to indicate that the routing algorithm is not the only one
that needs to be adapted or replaced on ad-hoc networks : the IP
forwarding algorithm should also be adapted

Is this modification of the IP forwarding algorithm described somewhere
?
Has somebody already implemented this modification on an OS (UNIX, BSD,
LINUX, Windows...) ?

Regards.

--
Bruno HUSSON
e-mail:[email-masked]
-----------------
SYCOMORE AEROSPATIALE MATRA
http://www.sycomore.fr
------------------------------------------------------

---

From: Lawrence MacIntyre <[email-masked]>
Date: Wed, 29 Nov 2000 16:04:24 -0500

Bruno:

We've done something like this on Linux using the external resolver
mechanism in the kernel.

-- 
                                 Lawrence
                                    ~
------------------------------------------------------------------------
Lawrence MacIntyre      Center for Information Infrastructure Technology
[email-masked]   http://www.ciit.y12.doe.gov/~lpz     865.574.8696

---

From: Matthew Impett <[email-masked]>
Date: Wed, 29 Nov 2000 18:54:41 -0500 (EST)

Bruno,

We have done something very similar as well but we wrote a linux kernel
module which handles the ip forwarding and enhancements..

Matt

---

From: SSDP143 <[email-masked]>
Date: Thu, 30 Nov 2000 11:25:40 +0200 (EET)

Dear Bruno;

We are group of three members.

We have done something like this by writing a Linux kernel module 
Extract destination IP address, DestIP from datagram,
If DestIP is on a directly connected network,
 send datagram to destination over that network
else 
 if there is an entry in the routing table (System routing table) that fits DestIP
  then route the datargam to the specified next hop address
 else (no entry is found in the System routing table)
   1.Search in routing table of AODV (Ad-Hoc On demand Distance Vector
    routing)protocol
    If there is a nexthop available for this DestIP
     then route the datargam to the specified next hop address
    Else
     send RREQ to find a suitable path to this DestIP and waits for RREP
     If recieving RREP
      then route the datargam to the specified next hop address   
     Else
      declare a routing error, and send an ICMP error message.

So our kernel module handles the ip forwarding and enhancements..
And so, we decrease number of broadcasting (On Demand only)

For more details you can e-mail:
                                  Azza ([email-masked])
                                  Morcos ([email-masked])
                                  Hany ([email-masked])

---

From: Francis Dupont <[email-masked]>
Date: Thu, 30 Nov 2000 11:04:22 +0100

In your previous mail you wrote:

=> this is very common for multicast forwarding, for instance both in
the traditional BSD code (with VIFs) and the Tom Pusateri's one
(I used Tom's approach then you know where to find an example of this).

Regards

[email-masked]

---

From: Francis Dupont <[email-masked]>
Date: Thu, 30 Nov 2000 12:39:12 +0100

=> this is a bit different because the external resolution should add
a template route and the remaining processing is done in the interface
code (in place of in the forwarding code).

Regards

---

From: [email-masked]
Date: Thu, 30 Nov 2000 15:37:04 +0100 (CET)

Hi Bruno,

I agree with your concirns regarding routing in reactive
protocols, specifically that the issue of buffering is of
importance. The AODV-draft specifies in section  8.2 that:

"Data packets waiting for a route (i.e., waiting for a 
 RREP after RREQ has been sent) SHOULD be buffered.  The 
 buffering SHOULD be FIFO." 

I am curious how one would go about implementing that without 
rewriting (parts of) the IP-stack? Also, I am curious if doing
so would contradict the IP standard? Perhaps someone with 
implementation experience from reactive protocols would share their
experiences?

Implementing OLSR (a proactive MANET protocol) we haven't had to deal 
with these issues - our implementations are done entirely in
user-space.

Best regards

--thomas

---

From: Matthew Impett <[email-masked]>
Date: Thu, 30 Nov 2000 10:12:44 -0500 (EST)

> implementation experience from reactive protocols would share their

The way we have handled this is by writing a linux kernel module which
resides under the IP stack. This module was written as a dummy
device driver, so to IP this module (called the forwarding engine, or
FE) looks like a device.  In this way we could install one route in IP
through the FE, and then the internal routing tables of the FE are used to
route IP packets. Therefore, if a packet hits the FE for a destination for
which we have no route, we can store the packet in a buffer associated
with that destination. Then, if a route is added for that destination by
some routing protocol, we can empty the buffer.

In this way, we can avoid changing the IP-stack but still acheive the
desired affect.

matt