Re: [Manet-dt] Re: [manet] DYMO RREQ flooding and super-flooding
Philippe Jacquet <philippe.jacquet@inria.fr> Thu, 24 May 2007 09:07 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 1Hr9Ic-0004OC-Im; Thu, 24 May 2007 05:07:58 -0400
Received: from manet-dt by megatron.ietf.org with local (Exim 4.43) id 1Hr9Ia-0004Nw-D1 for manet-dt-confirm+ok@megatron.ietf.org; Thu, 24 May 2007 05:07:56 -0400
Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1Hr9IW-0004N3-8d; Thu, 24 May 2007 05:07:52 -0400
Received: from discorde.inria.fr ([192.93.2.38]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1Hr9IU-00089z-Gi; Thu, 24 May 2007 05:07:52 -0400
Received: from [192.168.112.191] (sphinx.lix.polytechnique.fr [129.104.11.1]) (authenticated bits=0) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l4O97NQg025438 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Thu, 24 May 2007 11:07:49 +0200
Message-ID: <465555CB.1040500@inria.fr>
Date: Thu, 24 May 2007 11:07:23 +0200
From: Philippe Jacquet <philippe.jacquet@inria.fr>
User-Agent: Thunderbird 1.5.0.10 (Macintosh/20070221)
MIME-Version: 1.0
To: "Charles E. Perkins" <charles.perkins@nokia.com>
Subject: Re: [Manet-dt] Re: [manet] DYMO RREQ flooding and super-flooding
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> <46546824.9040905@inria.fr> <46549EE5.7070509@nokia.com>
In-Reply-To: <46549EE5.7070509@nokia.com>
Content-Type: text/plain; charset="ISO-8859-1"; format="flowed"
X-Miltered: at discorde with ID 465555E5.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 l4O97NQg025438
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 93b4f10b2112e1468b61e19ea6180478
Cc: manet <manet@ietf.org>, manet-dt@ietf.org
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
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 <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 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