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

[Philippe Jacquet <[e-mail]>]

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