Subject: Forwarding table lookup / unicast, multicast

From: Chip Elliott <[email-masked]>
Date: Mon, 16 Oct 2000 09:49:22 -0400

At 10:33 PM 10/14/00 -0500, [email-masked] wrote:
>I was wondering, in an ad hoc network node, what would be the actual
>routing/state-table-lookup delay (time taken at the intermediate node to
>execute the instructions that look-up the routing/state table and
>determine the next-hop) ? What percentage of the the overall end-to-end
>packet transmission latency from source to destination would this lookup
>delay constitute? Is it negligible?
>

It is almost certainly negligible, assuming that you already have
the next-hop information in your routing table. If you use short, unique
node identifiers (eg 16 bits) it can be as quick as an indexed table
lookup in memory. And that memory is presumably already in your cache.
So on many machines, one cycle will do it.

Note that there are a few other parts to the packet forwarding
path (eg decrementing TTLs etc) but on the whole the forwarding
path is very quick - especially when compared to 802.11 channel access.

As an aside, the multicast forwarding operation is considerably
more complex than that for unicast. The main problem here is that
routing loops cause much worse behavior in multicast than they do
in unicast, since packets get replicated at each multicast forking
point. Hence routing loops can lead to "chain reactions" of more
and more forwarded copies of packets. As a result, multicast forwarding
in ad hoc networks really needs some more complicated checks to
prevent routing loops from wreaking such havoc.

Chip Elliott
BBN Technologies

PS. Note that getting the right information into the forwarding table
is the hard part - but I imagine that you know that.

---

From: [email-masked]
Date: Mon, 16 Oct 2000 17:41:59 -0500 (CDT)

Hi, 

Thank you for your reply.

Yes, I was assuming that the next-hop information has been previously
determined and is cached.

Is there a way I can determine average end-to-end propagation delay of a
flooded packet in an ad hoc network? Averaged over all senders and all
recipients. And also, the corresponding standard deviation.

Assuming duplicate packets are ignored and a 50-node network in a 500m x
500m area, using 2 Mbps links and given a maximum load of (say) 10 other
flows in the network. Also, maximum speed is 20 m/s.

Further, I am assuming that this average won't vary much with time.

Thanks and regards,
Samarth.

---

From: Chip Elliott <[email-masked]>
Date: Tue, 17 Oct 2000 09:33:54 -0400

>Further, I am assuming that this average won't vary much with time.

Hi Samarth,

Well, your previous question was very easy to answer, but this one
will require a PhD thesis in response. Maybe someone else on the
list is actually doing a thesis on this and cares to hold forth...?

If not, I suggest that you start rummaging about in the hundreds of
papers that people have writting on ad hoc networking, then get
yourself a good simulator, implement some algorithms, and start
measuring the results. (I suggest simulation because in general
such networking performance results are not easy to reduce to
closed-form math.)

Cheers and good luck,

Chip Elliott
BBN Technologies

---

From: Vijay Devarapalli <[email-masked]>
Date: Tue, 17 Oct 2000 10:10:36 -0700

Samarth,

if it is simulations you are doing, you have to assume something called a
'router processing delay' at each node between the RECEIVE event and a SEND
event for a packet. this is NOT negligible.

combine this with a 'link propagation delay' and you have your propagation
delay between two nodes in your ad hoc network. the link propagation delay
depends on the bandwidth you choose for the link and the size of the packet
you are sending.

for eg if your packet is going from node 1 to node 5 and there are nodes 2,
3 and 4 in between the
propagation delay would be

       = router processing delay * 3 + link propagation delay for each link

router processing delay could be an average value, the same for every node.
for link propagation delay, you can safely ignore the distance between two
nodes.

for the average router processing delay, read a few papers. a lot of
simulations ignore this and in my opinion those results are wrong.

regards
Vijay

---

From: [email-masked]
Date: Thu, 19 Oct 2000 15:45:25 -0500 (CDT)

> such networking performance results are not easy to reduce to

I figured that this average flood-packet delay is not dissimilar to the
average delay experienced by a flooded link state packet (LSP) in a link
state protocol for an ad hoc network.

Perhaps there exists some such protocol and such data for it exists in
literature.

I was just wondering if my analogy was right and if you might know of any
such link-state protocol or study of average delays for LSPs. If my
analogy is right, perhaps I should study OLSR in a little more detail?

Many thanks and regards,
Samarth.

---

From: Chip Elliott <[email-masked]>
Date: Fri, 20 Oct 2000 10:00:27 -0400

Hi Samarth,

That seems like a good approach, if by "flooding" you mean "flooding".
(That is, in classic link-state every update crosses every simplex link
in the network, and an acknowledgement crosses the reverse path of
each of these links. There are "smarter" though sometimes less robust
flooding techniques in which packets only transit a subset of the network
graph, eg, a multicast tree.) The delay time can then be estimated by graph
theory, eg, the network topology's diameter is the maximal delay, etc.

Real life link-state protocols are more complex than you might guess,
however. In particular they generally apply some form of rate control
to (a) the initial injection of routing updates into the network,
and (b) the forwarding onward of these messages across network links.
There are a number of different reasons for this. First, it can help
avoid flooding the network with control traffic for marginal links,
ie, those that keep coming up and going down. (This is often also
tackled by a "hello" protocol with hysteresis.) Second, when a new
router appears, delaying its initial update will allow batching of
updates from all the links that it is bringing up. Third, in some
situations - especially ad hoc networks - it can be desirable to
provide some cap on the rate at which control traffic can be injected
into a channel. Rate-limiting the updates in such cases has the further
desirable property that multiple updates can be batched into a single
message for transmission, thus amortizing the rather heavy channel
access penalty across a number of routing updates. All these techniques
have the downside, though, that they add delay to the flooding
propagation time. Calculating the delays analytically can be tricky
because a per-hop delay can depend on things link the average degree of
the network ie, the number of neighbors for each node.

You should also be extremely wary of the channel access delay in
flooding cases. People often assume that these delays are statistically
independent, ie, uncorrelated. This is very false in many flooding
techniques, since a number of nodes (in the same channel) will have
received a flooded message at about the same time, and will all be
contending for the channel in order to flood it onwards to their
neighbors. Hence my recommendation would that IF you are going to
perform analytic computations of the delay, you should be sure that
you're taking into account the correlated channel access problem.

Cheers and all the best,

Chip Elliott
BBN Technologies

---

From: "wooighee" <[email-masked]>
Date: Mon, 23 Oct 2000 12:38:23 +0900

Hai All
     I am reading the AODV draft and I am not quite sure about 
when the Hello packet of AODV is exchanged during
its oparation.

I wonder that the Hello packet is exchanged within neighboring nodes

(a) only within nodes along which  the RREP packet path is taken.

(b) within nodes after receiving RREQ packet.

(a) actively all of time

If anyone has any idea with this, please kindly inform me.
I really appreciate this.

Thank you
ghee

---

From: "wooighee" <[email-masked]>
Date: Sun, 22 Oct 2000 23:40:38 +0900

Hai All
     I am wondering when the Hello packet of AODV is exchanged during
its oparation.

(a) actively all of time

Thank you
ghee

---

From: Wong Hau Shian <[email-masked]>
Date: Mon, 23 Oct 2000 15:37:01 +0800

Hello packets are for neighbour discovery. So packets are exchanged
periodically.

Regards
HS

---

From: WANG Wooi Ghee <[email-masked]>
Date: Mon, 23 Oct 2000 17:35:17 +0900 (JST)

Hai Wong 
    
   Thank you for replying to my question. 
If the Hello packet is exchanged periodically over ALL
of the nodes, won't the hello packet waste the bandwidth
and power supply of nodes that are not actively involved
in forwarding of real data packet ?
Besides, we might piggyback the routing table over the
hello packet and spread the routing table over the 
whole network. 
But this sounds controversial to the idea of basic
on-demand routing protocol where route searching is
initiated  ONLY WHEN a sending node originates a data
packet addressed to that node.

   If I am wrong please kindly correct me and 
I really appreciate this.

Thank you

ghee

---

From: "Samir R. Das" <[email-masked]>
Date: Mon, 23 Oct 2000 11:17:33 -0400

The intent of the hello packets in AODV is not for doing the actual routing
per se, but to maintain "local" connectivity information (i.e., to maintain
a list of current neighbors). It is important to know the local connectivity
so that link breaks on active routes are detected and routes are erased. If
other mechanisms exist to detect link breaks on active routes (such as a
layer-2 feedback) then hello packets are not needed.

It would be certainly interesting to exchange full or partial routing tables
with hello packets to add some proactive flavor to AODV. In fact, we have
simulated something similar. Early results seem to indicate that this can
improve performance in some situations for dense networks.

Samir

>-----Original Message-----
>From: [email-masked]
>[mailto:[email-masked]]On Behalf Of WANG Wooi Ghee
>Sent: Monday, October 23, 2000 4:35 AM
>To: [email-masked]
>Cc: [email-masked]; [email-masked]
>Subject: Re: When the AODV Hello Packet is exchanged ?
>
>
>Hai Wong
>

---

From: Mahesh Marina <[email-masked]>
Date: Mon, 23 Oct 2000 11:13:29 -0400 (EDT)

> in forwarding of real data packet ?

If the data communication is only among nodes in small section of the
network, then answer to your question is certainly yes.

> hello packet and spread the routing table over the 

Again, the benefit of such an approach depends on the kind of data
traffic.

Regards,
Mahesh

---

From: Mahesh Marina <[email-masked]>
Date: Mon, 23 Oct 2000 11:06:04 -0400 (EDT)

Hi,
Hello messages are intended for neighbor discovery. When hello messages
are used, they are exchanged between neighbors periodically regardless of
RREQ and RREP packets.
An alternative is to use link-level feedback to detect the loss of
neighbors.
Regards,
Mahesh

-- 
Regards,
Mahesh

---

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 23 Oct 2000 07:25:57 -0700

Hello,

It is true that Hello packets consume bandwidth,
and that we'd like to get rid of them.

According to the specification, Hello packets would
be transmitted periodically by all nodes if no
other means of neighbor detection were available.

> (a) only within nodes along which the RREP packet path is taken.

is intriguing, and I don't recall that we ever thought of
that idea before.  What _could_ happen is the following:

1) Broadcast RREQ
2) Unicast RREP
3) Hello never transmitted unless precursor list nonempty.

I don't see anything wrong with this scenario.

Regards,
Charlie P.

---

From: "Miguel Sanchez" <[email-masked]>
Date: Mon, 23 Oct 2000 19:57:27 +0200

Hi all,

I guess that Hello transmission can be skipped when nodes are actively
forwarding data packets because these transmissions are making them visible
to their neighbors.

Regards,

Miguel Sanchez

---

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 23 Oct 2000 13:08:57 -0700

Hello Miguel,

Yes, I think I agree about when Hello messages can be skipped.

So, if hello messages are NOT transmitted from inactive
nodes, and if they are NOT transmitted from nodes that
have forwarded a packet, then the only time they would
have to be transmitted is for the time interval
	ALLOWED_HELLO_LOSS * HELLO_INTERVAL
after the last time an active forwarder sent a packet.

We might have to make some relationship between
	ACTIVE_ROUTE_TIMEOUT (default: 3,000 Milliseconds)
and
	ALLOWED_HELLO_LOSS * HELLO_INTERVAL
so that a node deprecates a route only after some time
that is related to how many Hello messages its active
neighbors expect to hear.

We might also have to specify that nodes interested
in getting neighbor information about an active route
are mandated to operate in promiscuous mode if at
all possible for the abovementioned period of time.

Is this something that should be fixed before AODV
goes to Last Call?

Regards,
Charlie P.

PS. Please check your CC: list to make sure that my
    e-mail address at Sun is removed.  Thanks!

---

From: [email-masked]
Date: Tue, 24 Oct 2000 11:02:52 +0200

Hello,

One non solved problem may be with long term unidirectional links.

A---->B

1) Broadcast RREQ from A received by B;
2) Unicast RREP from B not received by A;
3) route discovery failure.

One possible way to cope with this scenario would be that B be aware that
A->B is unidirectional before 1) happens, so that A is not registered in
precursor list of B and 2) does not happen. In this case pro-active hellos
may help to maintain this information.

Regards,
Philippe

---

From: "Charles E. Perkins" <[email-masked]>
Date: Tue, 24 Oct 2000 08:07:25 -0700

Hello,

We didn't solve the unidirectional routing problem for AODV,
but at least we can get rid of long-term route discovery failures.
This is the purpose of the 'A' bit for RREP, and the RREP-ACK
message.

Solving the general unidirectional routing problem requires
broadcast RREPs, a compatible link-layer, and perhaps another
unicast acknowledgement after the discoverer gets a RREP.  Plus,
source routes in the control messages would be handy.  We have
often thought about adding them to AODV's RREQ and RREP, abstaining
mainly because of political considerations.  They aren't needed
nearly as much unless one wishes to allow unidirectional routes.

There are probably simple solutions for special cases that
would then need some intuitive characterization.

Regards,
Charlie P.

---

From: [email-masked]
Date: Wed, 25 Oct 2000 14:46:53 +0200

Hello,

You mean the problem of routing packets on unidirectional links? Yes I
agree this is a difficult problem calling for appropriate data link layer. 

But my problem is much simpler: 

In presence of permanent unidirectional links in the network, the route
discovery process may permanently fail, even if there exists bidirectional
routes. One solution to this problem may be that no node should forward
RREQ packets received from unidirectional links. But this may need the use
of proactive hello exchanges. 

Example of architecture which leads to route discovery failure from A to G

A----B----C----D----E----F----G---H--- 
 \............>

Links between A and B, B-C, C-D, etc, are symmetric links. But nodes A has
unidirectional links to C and D (C and D hear A but are not heared by A). 

Regards,
Philippe

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 25 Oct 2000 08:11:16 -0700

Hello Philippe,

>>This is the purpose of the 'A' bit for RREP, and the RREP-ACK

Do you think that our solution of allowing a node to require
ACKs for RREPs fails to solve the problem?

If so, can you suggest any straightforward solution to this
problem?

Regards,
Charlie P.

---

From: "Samir R. Das" <[email-masked]>
Date: Wed, 25 Oct 2000 11:04:23 -0400

Yes. This problem was discussed in the MANET list a few months back and some
solutions were proposed.  Of course, proactive hellos will also work.

Samir

>From: [email-masked] [mailto:[email-masked]]
>Sent: Wednesday, October 25, 2000 8:47 AM
>To: Charles E. Perkins
>Cc: [email-masked]; Elizabeth Royer; Samir R. Das
>Subject: Re: When the AODV Hello Packet is exchanged withunidirectional
>links?
>
>
>Hello,
>

---

From: [email-masked]
Date: Wed, 25 Oct 2000 18:51:18 +0200

Hello Charlie,

I am not sure the RREP-ACK would suffice, because the problem comes because
the node has forwarded the RREQ before. 

One solution could be the "black list", described few months ago. Every
node manages a local black list listing known unidirectional links. Nodes
don't process nor forward RREQ packets received from a node listed in black
list. A node can be recorded in black list after one RREP-ACK failed (this
may imply at least one route failure). 

Maybe nodes in black lists should be time-out in some way, because I don't
see how to refresh such information without route failure or pro-active
hellos. 

Maybe there are simpler way to handle this problem,

Regards,
Philippe

---

From: Ravi Prakash <[email-masked]>
Date: Wed, 25 Oct 2000 13:06:14 -0500 (CDT)

Hello Philippe,

First, I apologize for this long message. Please be patient as there are
several issues that I have tried to address in the context of
unidirectional links.

I have been following this discussion on unidirectional links with great
interest because our group (including Sanket Nesargi and Daniel Russo) has
been working on the problem of unidirectional links for over a year now. 

If I understand your suggestion correctly, you are suggesting that the
routing protocol should ignore all unidirectional links and restrict
itself to bidirectional links only. 

While this will work in some situations it can lead to problems in other
situations. For example, let us assume that in the actual network there
exists a multi-hop path from A to B and a different multi-hop path from B
to A. Let both these
paths have at least one unidirectional link. If these unidirectional links
are ignored, the routing protocol will be unable to discover routes from A
to B and from B to A. Effectively, it will conclude that A and B belong to
different network partitions. So, A and B will be unable to communicate
with each other. In reality A and B are in the same
partition. 

Moreover, sometimes it may be possible to find a shorter route that uses a
combination of uni- and bi-directional links, compared to a route that
only uses bi-directional links. 

So, "black listing"  has its limitations.

In DIAL-M, 1999 (held in conjunction with MobiCom in August 99) I
presented a paper where in an N-node network nodes end up exchanging
their knowledge of the network topology by communicating N*N matrices with
their neighbors whenever permitted by the directionality of the
lins. Through a sequence of matrix exchanges between
neighbors the downstream node of a unidirectional link is able to
convey information about the existence of that link to the upsteam
node. Then, the upstream node can use this link to forward packets.
Of course, this requires that a path exist from the downstream node to the
upstream node of a unidirectional link.

Our initial goal was to see if some modifications could
be made to DSDV to handle unidirectional links and we ended up incurring
higher overheads. However, one has to make a choice between higher
overheads in route discovery vs. erroneous conclusions of partitioning or
sub-optimal paths with low overheads.  

In IC3N 1999, Lichun Bao and J.J. Garcia-Luna-Aceves presented a paper
which also
dealt with routing in wirless mobile ad hoc networks. They, too, observed
that the unidirectional link needs to be part of an inclusive cycle for it
to be usable for routing purposes, and presented a protocol. I will not go
into the details of their work because I do not wish to utter something
about their protocol that may be wrong.

In IC3N 2000, held last week, Sanket Nesargi and I presented a paper on
routing in ad hoc networks with unidirectional links using the tunneling
approach. This idea is to offer a frame-work for a variety of routing
protocols so that the unidirectionality of links can be hidden from the
routing modules by performing link-layer and network layer
operations. This is similar to the approach proposed by IETF's UDLR
working group.

Let us assume that in this framework a distance-vector based protocol is
operating. Then, the downstream node of the unidirectional link would
"tunnel" its route advertisement to the upstream node. Once the upstream
node receives this tunneled distance vector it can use the vector to
update its own distance vector as if the advertisement was received
directly from the downstream node. 

Also, at the link layer, acknowledgments for frames sent along
unidirectional links have to be handled. As the ACKs cannot be directly
sent from the downstream node to the upstream node of the unidirectional
link the ACKs, too, will need to be tunneled (routed at the network layer) 
to the upstream node. However, if care if not taken this can result in ACK
explosion if the tunnel also contains a unidirectional link. We
have proposed a simple fix to handle this problem. 

An important issue to note at this point is that RTS/CTS based link-layer
handshake, as done in IEEE 802.11, will work for bidirectional links
only. So, in order to be able to use unidirectional links we will need to
work on MAC layer protocols as well. 

Having said all this, one may wonder why go to such great lengths to use
unidirectional links when they create so many problems? Well, first
because it is an interesting problem! But, the more important reason is
that mobility, multi-path losses, interference, and uneven depletion of
battery can lead to several incidences of unidirectional links. So, we
cannot afford to ignore such links.

If anybody is interested in copies of our papers I will be happy to email
them.

With best regards,

----Ravi. 
========================================================================
Ravi Prakash ([email-masked])		www.utdallas.edu/~ravip
Department of Computer Science
The University of Texas at Dallas
Richardson, TX 75083-0688.  Phone: (972) 883-2289,   Fax: (972) 883-2349