Re: [Manet-dt] Re: [manet] DYMO RREQ flooding and super-flooding

[Philippe Jacquet <[e-mail]>]

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




Charles E. Perkins a écrit :
> 
> 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:
>> 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
>>
>> Charles E. Perkins a écrit :
>>>
>>> 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.
>>>>
>>>> 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 :
>>>>> 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
>>>>>
>>>>> On 5/23/07, Philippe Jacquet <[e-mail]> wrote:
>>>>>> 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
>>>>>>
>>>>>> 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.
>>>>>> >
>>>>>> > 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
>>>>>> >
>>>>>> > On 5/16/07, Philippe Jacquet <[e-mail]> wrote:
>>>>>> >> 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
>>>>>> >>
>>>>>> >>
>>>>>> >>
>>>>>> >> Ian Chakeres a écrit :
>>>>>> >> > 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
>>>>>> >> >
>>>>>> >> > On 5/16/07, Philippe Jacquet <[e-mail]> wrote:
>>>>>> >> >> 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
>>>>>> >> >>
>>>>>> >> >> Ian Chakeres a écrit :
>>>>>> >> >> > 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
>>>>>> >> >> >
>>>>>> >> >> > On 5/15/07, Philippe Jacquet <[e-mail]> 
>>>>>> wrote:
>>>>>> >> >> >> 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
>>>>>> >> >> >> [e-mail]
>>>>>> >> >> >> https://www1.ietf.org/mailman/listinfo/manet
>>>>>> >> >> >>
>>>>>> >> >> >
>>>>>> >> >> >
>>>>>> >> >> > _______________________________________________
>>>>>> >> >> > manet mailing list
>>>>>> >> >> > [e-mail]
>>>>>> >> >> > https://www1.ietf.org/mailman/listinfo/manet
>>>>>> >> >> >
>>>>>> >> >> >
>>>>>> >> >>
>>>>>> >> >
>>>>>> >> >
>>>>>> >>
>>>>>> >
>>>>>> >
>>>>>> > _______________________________________________
>>>>>> > manet mailing list
>>>>>> > [e-mail]
>>>>>> > https://www1.ietf.org/mailman/listinfo/manet
>>>>>> >
>>>>>> >
>>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> Manet-dt mailing list
>>>> [e-mail]
>>>> https://www1.ietf.org/mailman/listinfo/manet-dt
>>>
>>>
>>>
>>> _______________________________________________
>>> manet mailing list
>>> [e-mail]
>>> https://www1.ietf.org/mailman/listinfo/manet
>>>
>>>
> 
> 
> 
> _______________________________________________
> manet mailing list
> [e-mail]
> https://www1.ietf.org/mailman/listinfo/manet
> 
> 


_______________________________________________
Manet-dt mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/manet-dt