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