Subject: [manet] DYMO RREQ flooding and super-flooding

From: Philippe Jacquet <[email-masked]>
Date: Tue, 15 May 2007 18:34:18 +0200

Hello, folks,

I see in DYMO spec (5.3.4) that a RREQ message can be retransmitted 
several times by a node if it receives copies on shorter routes.

This reminds me the paper we did about this kind of super-flooding.

Comparative Study of Routing Protocols for Mobile Ad Hoc Networks
T. Clausen, P. Jacquet et L. Viennot
Med-hoc-Net, 2002

http://gyroweb.inria.fr/~viennot/postscripts/medhocnet2002sim.ps.gz

It gives the shortest path to OrigNode in hop count, but the number of 
retransmissions may be important and exceed the network size (can be 
quadratic in the network size per RREQ).

I wonder if one could also add other metrics than simply hop count. For 
example RREQ could seek the path with average shortest delay by adding 
the last hop average link delay to the current weight carried by the 
RREQ. The RREQ would carry a bit indicating that average shortest delay 
is activated). Or the RREQ could look to the largest bandwidth route (in 
this case one take the minimum of the last hop bandwidth with the weight 
carried by the RREQ.

Other metrics are possible (variance, etc).

Best regards,
Philippe

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

---

From: "Ian Chakeres" <[email-masked]>
Date: Wed, 16 May 2007 09:57:28 +0530

I had done some work on using different metrics by introducing delay
during route discovery to influence route selection.

Here is the paper info:

Ian D. Chakeres and Elizabeth M. Belding-Royer. "Transparent Influence
of Path Selection in Heterogeneous Ad hoc Networks." Proceedings of
the 15th IEEE International Symposium on Personal, Indoor and Mobile
Radio Communications (PIMRC), Barcelona, Spain, September 2004.

For the base spec we are not including any complex metrics, but
instead rely on DV & hopcount (if included) or other techniques that
work under these assumptions (like the paper above).

I think some additional TLVs and new functionality to enable DYMO to
support more complex metrics would be interesting.

Ian

---

From: Philippe Jacquet <[email-masked]>
Date: Wed, 16 May 2007 13:47:31 +0200

Ian, I don't understand how the method you described in your paper for 
AODV can be applied for DYMO.

Assume you delay the RREQ retransmission on the two-hop route because 
the routers have low willingness, so that it is transmitted after the 
three hops route. Anyhow the two-hop RREQ will be relayed since it has a 
smaller hop-count and the shortest route will be in fact selected. Or am 
I wrong?

Philippe

---

From: "Ian Chakeres" <[email-masked]>
Date: Wed, 16 May 2007 17:31:38 +0530

If you don't include hop count information, it will not be used in the
decision making.

If you were interested in using "fasted RREQ" path, you would not
include the hop count information.

Ian

---

From: Philippe Jacquet <[email-masked]>
Date: Wed, 16 May 2007 15:03:54 +0200

I didn't know that you could disable hop counter, I thought 
MsgHdr.HopCnt was mandatory in RREQ message.

In case you use super-flooding, should you put a limit in the number of 
retransmissions per node in order to avoid a flooding explosion?

Philippe

---

From: "Ian Chakeres" <[email-masked]>
Date: Wed, 16 May 2007 19:06:15 +0530

The MsgHdr.HopCount is not used in reference to routing information in
DYMO. Node.HopCount (in an address block TLV) is optional.

I have not read about super-flooding, but DYMO's method for
determining the quality of routing information should be sufficient to
avoid excess flooding.

Ian

---

From: Philippe Jacquet <[email-masked]>
Date: Tue, 22 May 2007 21:24:17 +0200

I see, I confused with MsgHdr.Hopcount, sorry. Maybe this could be 
specifed as a remark in the draft.

I am not sure that the method specified in the draft will avoid a 
quadratic flooding. In particular when slow interfaces have longer hauls 
than fast interfaces.

Consider a chain of n nodes, each having two interfaces a fast one 
covering one hop, and a slow one covering two hops. The route with n-1 
hops will come first, then the n-2 hops, then the n-3, and finally n/2 
hops. This would give O(n) RREQ relayed per node.

In fact the quadratic bound could explode if the metric has no 
constraint on discrepancy. In this case it could become exponential or 
even factorial in worst case.

Why not an upper limit on the number of per RREQ per node relaying as a 
safeguard to flooding explosion? Even if it has the cost that optimal 
route may not be attainable that way.

Philippe

---

From: "Ian Chakeres" <[email-masked]>
Date: Wed, 23 May 2007 09:49:57 +0530

Sounds like a good idea, I will add a recommendation in the next DYMO
revision that devices SHOULD limit the number of RREQ forwarded.

Do you have a suggestion for the default limit that should be forwarded?

Ian

---

From: Philippe Jacquet <[email-masked]>
Date: Wed, 23 May 2007 18:13:24 +0200

Hard to see a default number value. To my opinion it should be included 
in RREQ message and hinted that it should depend on traffic conditions. 
A short relay number will imply a light flooding but sub-optimal routes. 
This would be better suited for short lived path or connection. For long 
lived connection where route sub-optimality may be more costly than a 
heavy super-flooding, a larger relay number may be more suitable.

In general I would be careful when introducing additional default 
parameters in DYMO since the latter is strongly based on network 
dynamic. A bad default protocol timing may have great negative impacts.

Philippe

Ian Chakeres a écrit :
>> >> >> >> I wonder if one could also add other metrics than simply hop 
>> count.
>> >> >> For
>> >> >> >> RREQ. The RREQ would carry a bit indicating that average 
>> shortest
>> >> >> delay
>> >> >> >> this case one take the minimum of the last hop bandwidth with 
>> the
>> >> >> weight
>> >> >> >> carried by the RREQ.
>> >> >> >>

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 23 May 2007 13:07:01 -0700

Hello Philippe,

I have been following along, and have a minor comment about
the proposal.

In general, I think it is appropriate to maintain default values
but to enable modifications based on measurements of current
relevant traffic and network conditions.  Having a default
value saves a great deal of repetition, and so saves a great
deal of wasted transmission capacity.  The lesson we have
been learning in our measurements is that more bytes over
the air equals more congestion and always there must be
justification for the potentially degraded performance.

What would you say about having a default value and
a newly defined extension to change it when needed?
What happens when variable congestion conditions in
different parts of the network suggest different values for
the number of RREQs that should be retransmitted?
I don't automatically see a problem there, but it could
be a tricky point.

Regards,
Charlie P.

ext Philippe Jacquet wrote:
> Hard to see a default number value. To my opinion it should be 
> included in RREQ message and hinted that it should depend on traffic 
> conditions. A short relay number will imply a light flooding but 
> sub-optimal routes. This would be better suited for short lived path 
> or connection. For long lived connection where route sub-optimality 
> may be more costly than a heavy super-flooding, a larger relay number 
> may be more suitable.
>
>>> >> >> three hops route. Anyhow the two-hop RREQ will be relayed 
>>> since it
>>> >> has a
>>> >> >> smaller hop-count and the shortest route will be in fact 
>>> selected.
>>> >> Or am
>>> >> >> I wrong?
>>> >> >>
>>> >> >> Philippe
>>> >> >>
>>> >> >> Ian Chakeres a écrit :
>>> >> >> >> I wonder if one could also add other metrics than simply 
>>> hop count.
>>> >> >> For
>>> >> >> >> example RREQ could seek the path with average shortest 
>>> delay by
>>> >> adding
>>> >> >> >> the last hop average link delay to the current weight 
>>> carried by
>>> >> the
>>> >> >> >> this case one take the minimum of the last hop bandwidth 
>>> with the
>>> >> >> weight
>>> >> >> >> carried by the RREQ.
>>> >> >> >>
> Manet-dt mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/manet-dt

---

From: Philippe Jacquet <[email-masked]>
Date: Thu, 24 May 2007 11:07:23 +0200

Hello, Charlie,

Not sure you will have real transmission saving here. Since the area 
with lowest RREQ retransmission number on the path will be a bottleneck, 
then areas with highest retransmission number will generates useless 
RREQ traffic that will actually not be forwarded. This would cost much 
more than adding few bits in a RREQ in order to equalize RREQ 
retransmissions, with exactly same effect but with much less waste of 
retransmissions.

Regarding default retransmission number, you already have two: one (no 
NodeHop counter) and infinity (with NodeHop counter). You can add a 
third one but I don't know if it will help. Maybe we can toss a coin 
between two and ten. Perhaps DYMO will have too many default numbers at 
the end in detriment of adaptibility to network condition.

Regards,
Philippe

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 24 May 2007 09:08:18 -0700

Hello Philippe,

Let's try it again from a somewhat different perspective.

Suppose the default is appropriate for "normal" network
conditions -- and, thus most packets do not need to have
any such extension. 

Now, your comment would apply to the less common
case.  When that happens, we would have more RREQ
retransmissions in uncongested parts of the network,
and RREQ retransmissions would be throttled in the
congestion regions, effectively producing fewer completed
route discoveries utilizing links in the congestion region.

Overall, this doesn't seem too bad to me...

We just have to pick the default wisely according to
whatever experience we can acquire.  What would you
say if the default number of retransmissions were, for
instance, 6 at every node?

If, on the other hand, there is no observable regularity
in the network congestion, and most packets end up
setting new retransmission parameter values, then I
can agree that setting aside some bits for this purpose
would be reasonable.  However, I do not recall any
studies that have indicated the need for this, or any
studies that have shown that having some adaptive
behavior would improve performance.  I didn't see
any algorithms for making the adaptation.  This
does not mean the danger is nonexistent.  But it
does suggest we shouldn't automatically enlarge all
packets to combat a potentially quite rare problem.

Regards,
Charlie P.

ext Philippe Jacquet wrote:
> with lowest RREQ retransmission number on the path will be a 
> bottleneck, then areas with highest retransmission number will 
> generates useless RREQ traffic that will actually not be forwarded. 
> This would cost much more than adding few bits in a RREQ in order to 
> equalize RREQ retransmissions, with exactly same effect but with much 
> less waste of retransmissions.
>
> between two and ten. Perhaps DYMO will have too many default numbers 
> at the end in detriment of adaptibility to network condition.
>
> Regards,
> Philippe
>
>>> may be more costly than a heavy super-flooding, a larger relay 
>>> number may be more suitable.
>>>
>>>>> >> >> >> is activated). Or the RREQ could look to the largest 
>>>>> bandwidth
>>>>> >> >> route (in

---

From: Philippe Jacquet <[email-masked]>
Date: Fri, 25 May 2007 15:25:10 +0200

Hello, Charlie,

Not sure it will likely work that way. It already fails in my simple 
example. If nodes in the middle of the chain are congested it won't 
prevent the path to go through even by locally adjusting RREQ 
retransmission number.

Super-flooding (limited or not) makes the path to evolve toward the 
shortest path, by smoothing out unnecessary random excursion from the 
optimal path that would incur in simple flooding. If the shortest path 
has to go through a congested area, super-flooding won't help to avoid 
it. I am afraid that the most likely outcome would be to create new 
congested areas due to useless RREQ retransmissions without avoiding 
existing congestion.

If one really wants to avoid congested area, then one can add an 
objective penalty to hop count when the link is in a congested area. For 
example instead of making hop_count<-hop_count+1, adding the average 
delay or, better, the average number of data packet retransmissions 
experienced on that link. In fact this is equivalent to consider another 
metric than simple hop count. But of course would imply a proactive 
monitoring of local conditions.

I am also not aware of an efficient congestion monitoring in reactive 
protocols, this is why I was merely suggesting to insert the non-default 
RREQ retransmission limit in the RREQ itself. A node can monitor the 
previous routes to a given destination and if they happened to be stable 
(no frequent RERR) and if the demanded connection is expected to last 
long, then it would be worthy to spend more flooding in order to catch a 
more optimal route and save in long term communication overhead.

Of course this is just a one penny contribution...

Best regards,
Philippe

---

From: "gabik" <[email-masked]>
Date: Fri, 25 May 2007 19:08:38 +0300

Hello

Is not the same trick of limiting the number of RREQ messages per node is
already used in AODV/DSR?

I know that studying from the simulators' code is not the best idea, but:
It seems that it is already implemented at least in glomosim in the context
of initiating RREQ messages in AODV (not forwarding)
(AODV_MAX_RERR_DESTINATIONS, glomosim-2.03\glomosim\network\aodv.pc 1997).

But I was under an impression that the same mechanism is used for forwarding
as well.

Gabi Kliot

-----Original Message-----
From: Ian Chakeres [mailto:[email-masked]] 
Sent: Wednesday, May 23, 2007 7:20 AM
To: Philippe Jacquet
Cc: manet
Subject: Re: [manet] DYMO RREQ flooding and super-flooding

Ian

On 5/23/07, Philippe Jacquet <[email-masked]> wrote:
> quadratic flooding. In particular when slow interfaces have longer 
> hauls than fast interfaces.
>
> Why not an upper limit on the number of per RREQ per node relaying as 
> a safeguard to flooding explosion? Even if it has the cost that 
> optimal route may not be attainable that way.
>
> Philippe
>
> Ian Chakeres a écrit :
> > The MsgHdr.HopCount is not used in reference to routing information 
> > in DYMO. Node.HopCount (in an address block TLV) is optional.
> >
> > determining the quality of routing information should be sufficient 
> > to avoid excess flooding.
> >
> > Ian
> >
> >> In case you use super-flooding, should you put a limit in the 
> >> number of retransmissions per node in order to avoid a flooding
explosion?
> >>
> >> Philippe
> >>
> >>
> >>
> >> Ian Chakeres a écrit :
> >> > If you don't include hop count information, it will not be used 
> >> > in the decision making.
> >> >
> >> >> Ian, I don't understand how the method you described in your 
> >> >> paper for AODV can be applied for DYMO.
> >> >>
> >> >> Assume you delay the RREQ retransmission on the two-hop route 
> >> >> because the routers have low willingness, so that it is 
> >> >> transmitted after the three hops route. Anyhow the two-hop RREQ 
> >> >> will be relayed since it
> >> has a
> >> >> > I had done some work on using different metrics by introducing 
> >> >> > delay during route discovery to influence route selection.
> >> >> >
> >> >> > Here is the paper info:
> >> >> >
> >> >> > of Path Selection in Heterogeneous Ad hoc Networks." 
> >> >> > Proceedings of the 15th IEEE International Symposium on 
> >> >> > Personal, Indoor and Mobile Radio Communications (PIMRC),
Barcelona, Spain, September 2004.
> >> >> >
> >> >> > For the base spec we are not including any complex metrics, 
> >> >> > but instead rely on DV & hopcount (if included) or other 
> >> >> > techniques that work under these assumptions (like the paper
above).
> >> >> >
> >> >> > I think some additional TLVs and new functionality to enable 
> >> >> > DYMO to support more complex metrics would be interesting.
> >> >> >
> >> >> > Ian
> >> >> >
> >> >> >> I see in DYMO spec (5.3.4) that a RREQ message can be 
> >> >> >> retransmitted several times by a node if it receives copies on
shorter routes.
> >> >> >> Comparative Study of Routing Protocols for Mobile Ad Hoc 
> >> >> >> Networks T. Clausen, P. Jacquet et L. Viennot Med-hoc-Net, 
> >> >> >> 2002
> >> >> >>
> >> >> >>
count.
> >> >> For
> >> >> >> example RREQ could seek the path with average shortest delay 
> >> >> >> by
> >> adding
> >> >> >> the last hop average link delay to the current weight carried 
> >> >> >> by
> >> the