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

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

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