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

Philippe Jacquet <philippe.jacquet@inria.fr> Wed, 23 May 2007 16:13 UTC

Return-path: <manet-dt-bounces@ietf.org>
Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1HqtSs-0005et-E9; Wed, 23 May 2007 12:13:30 -0400
Received: from manet-dt by megatron.ietf.org with local (Exim 4.43) id 1HqtSq-0005Zl-Eq for manet-dt-confirm+ok@megatron.ietf.org; Wed, 23 May 2007 12:13:28 -0400
Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1HqtSp-0005ZS-Kl; Wed, 23 May 2007 12:13:27 -0400
Received: from discorde.inria.fr ([192.93.2.38]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1HqtSo-0004k6-W5; Wed, 23 May 2007 12:13:27 -0400
Received: from [128.93.62.246] (dhcp-rocq-246.inria.fr [128.93.62.246]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l4NGDPsF008915 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Wed, 23 May 2007 18:13:25 +0200
Message-ID: <46546824.9040905@inria.fr>
Date: Wed, 23 May 2007 18:13:24 +0200
From: Philippe Jacquet <philippe.jacquet@inria.fr>
User-Agent: Thunderbird 1.5.0.10 (Macintosh/20070221)
MIME-Version: 1.0
To: Ian Chakeres <ian.chakeres@gmail.com>
References: <4649E10A.5040007@inria.fr> <374005f30705152127m6a8bdfe2n99715930e2bd9393@mail.gmail.com> <464AEF53.7020506@inria.fr> <374005f30705160501v42c53e61h3f0b71569df2541c@mail.gmail.com> <464B013A.6070601@inria.fr> <374005f30705160636p69ae55e8ya6ab9bbcf499c04a@mail.gmail.com> <46534361.4020703@inria.fr> <374005f30705222119q2508118ep7ef85cddf635e4f9@mail.gmail.com>
In-Reply-To: <374005f30705222119q2508118ep7ef85cddf635e4f9@mail.gmail.com>
Content-Type: text/plain; charset="ISO-8859-1"; format="flowed"
X-Miltered: at discorde with ID 46546825.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)!
Content-Transfer-Encoding: quoted-printable
X-MIME-Autoconverted: from 8bit to quoted-printable by discorde.inria.fr id l4NGDPsF008915
X-Spam-Score: 0.0 (/)
X-Scan-Signature: d008c19e97860b8641c1851f84665a75
Cc: manet <manet@ietf.org>, manet-dt@ietf.org
Subject: [Manet-dt] Re: [manet] DYMO RREQ flooding and super-flooding
X-BeenThere: manet-dt@ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: MANET Design Team <manet-dt.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/manet-dt>, <mailto:manet-dt-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www1.ietf.org/pipermail/manet-dt>
List-Post: <mailto:manet-dt@ietf.org>
List-Help: <mailto:manet-dt-request@ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/manet-dt>, <mailto:manet-dt-request@ietf.org?subject=subscribe>
Errors-To: manet-dt-bounces@ietf.org

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 <philippe.jacquet@inria.fr> 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 <philippe.jacquet@inria.fr> 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 <philippe.jacquet@inria.fr> 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 <philippe.jacquet@inria.fr> 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
>> >> >> >> manet@ietf.org
>> >> >> >> https://www1.ietf.org/mailman/listinfo/manet
>> >> >> >>
>> >> >> >
>> >> >> >
>> >> >> > _______________________________________________
>> >> >> > manet mailing list
>> >> >> > manet@ietf.org
>> >> >> > https://www1.ietf.org/mailman/listinfo/manet
>> >> >> >
>> >> >> >
>> >> >>
>> >> >
>> >> >
>> >>
>> >
>> >
>> > _______________________________________________
>> > manet mailing list
>> > manet@ietf.org
>> > https://www1.ietf.org/mailman/listinfo/manet
>> >
>> >
>>
> 
> 


_______________________________________________
Manet-dt mailing list
Manet-dt@ietf.org
https://www1.ietf.org/mailman/listinfo/manet-dt