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

["Charles E. Perkins" <[e-mail]>]

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-dt mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/manet-dt