[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
- [Manet-dt] Re: [manet] DYMO RREQ flooding and sup… Philippe Jacquet
- [Manet-dt] Re: [manet] DYMO RREQ flooding and sup… Philippe Jacquet
- [Manet-dt] Re: [manet] DYMO RREQ flooding and sup… Philippe Jacquet
- [Manet-dt] Re: [manet] DYMO RREQ flooding and sup… Philippe Jacquet
- Re: [Manet-dt] Re: [manet] DYMO RREQ flooding and… Charles E. Perkins
- Re: [Manet-dt] Re: [manet] DYMO RREQ flooding and… Philippe Jacquet
- Re: [Manet-dt] Re: [manet] DYMO RREQ flooding and… Charles E. Perkins
- Re: [Manet-dt] Re: [manet] DYMO RREQ flooding and… Philippe Jacquet