[Manet-dt] Re: [manet] DYMO and other routing protocols

Philippe Jacquet <philippe.jacquet@inria.fr> Tue, 12 June 2007 16:00 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 1Hy8nJ-0003cF-I5; Tue, 12 Jun 2007 12:00:33 -0400
Received: from manet-dt by megatron.ietf.org with local (Exim 4.43) id 1Hy8n0-0002ze-Fy for manet-dt-confirm+ok@megatron.ietf.org; Tue, 12 Jun 2007 12:00:14 -0400
Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1Hy8mx-0002tW-K1; Tue, 12 Jun 2007 12:00:11 -0400
Received: from discorde.inria.fr ([192.93.2.38]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1Hy8mw-0007Jg-R3; Tue, 12 Jun 2007 12:00:11 -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 l5CG09ta024698 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Tue, 12 Jun 2007 18:00:10 +0200
Message-ID: <466EC30B.7080802@inria.fr>
Date: Tue, 12 Jun 2007 18:00:11 +0200
From: Philippe Jacquet <philippe.jacquet@inria.fr>
User-Agent: Thunderbird 1.5.0.12 (Macintosh/20070509)
MIME-Version: 1.0
To: hrubens@persistentsystems.com
References: <20070606162620.iq4c8ltur1ck4k80@wwwstudent.murdoch.edu.au><4669398E.1030304@inria.fr> <4669A835.7090004@nokia.com> <466E6802.4020906@inria.fr> <00db01c7acf0$c108dae0$6a01a8c0@HerbRubens>
In-Reply-To: <00db01c7acf0$c108dae0$6a01a8c0@HerbRubens>
Content-Type: text/plain; charset="ISO-8859-1"; format="flowed"
X-Miltered: at discorde with ID 466EC309.001 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 l5CG09ta024698
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 681e62a2ce9b0804b459fe780d892beb
Cc: manet@ietf.org, manet-dt@ietf.org
Subject: [Manet-dt] Re: [manet] DYMO and other routing protocols
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

Herb,

In OLSR when a link fails, then the link change is immediately 
advertized. The route change is therefore computed from the new 
database: before the link advertizement packets are lost on the failing 
link, and after they are routed on the new route. There is no loop.

You may argue that some nodes may not receive the link change and send 
the packet to an old relay and if the latter considers the former as 
next hop in the new database in some pathological case, you may have a 
temporary root. In practice it never happens (at least to my knowledge).

On the other hand resolving routes with time interval as it is done with 
on-demand protocols will actually avoid loop but with disconnection time 
that can be long in practice. To my opinion this is something that would 
need to be improved regarding practical implementation.

Philippe

Herbert Rubens a écrit :
> Philippe,
> 
> 	Correct me if I am wrong, but Link-State protocols (e.g. OLSR) are
> generally not 'instantaneously loop free'. Meaning if a link metric changes
> or a link goes from working to not working, the link-state database is not
> loop free until an update is received by all of the nodes in the network.
> Consider a simple example: if data is flowing along a path and a node along
> the path decides that the next-hop link is no longer working. If it removes
> the link from the data-base and re-computes the	path, the route might be
> back to the node that sent it the packet. Until that node receives an update
> you will have a loop in the network. 
> 
> 	It appears that when a link fails on an active link-state path, you
> technically can't be routing reliably without a flood propagating the entire
> network. In an on-demand (dymo, aodv, dsr) protocol, when a link fails on an
> active path you also need to propagate a flood to the entire network before
> the routing can continue. So while link-state protocols actively track every
> imaginable path, it's not clear that they actually perform differently in
> the link-failure case that you suggested. 
> 
> -Herb
> 
> -----Original Message-----
> From: Philippe Jacquet [mailto:philippe.jacquet@inria.fr] 
> Sent: Tuesday, June 12, 2007 5:32 AM
> To: Charles E. Perkins
> Cc: manet@ietf.org; manet-dt@ietf.org
> Subject: Re: [manet] DYMO and other routing protocols
> 
> Dear Charlie,
> 
> Sorry to have been kind of elliptic in my previous post. I didn't want 
> to mystify you;-)
> 
> In proactive protocols, when a link fails the alternative route is 
> immediately available, because it is already stored in the database. 
> This what I call space diversity or space discrimination. The quantity 
> of information needed to this space diversity is controled by several 
> algorithms, the MPRs in OLSR is one example. This what I tried to name 
> space adaptability.
> 
> In DYMO when a route fails, a new route is created with a new sequence 
> number. The two routes don't exist simultaneously and it takes time to 
> recover. This is what I tried to name time discremination.
> 
> But I don't see time adaptability in DYMO. For example if a route 
> discovery fails it takes time to initiate a new route discovery. This 
> time should be controlled. Longer routes will have larger route 
> discovery delays, therefore need larger waiting time. However longer 
> route may have larger RREQ/RREP failure, therefore experience multiple 
> discovery route. In this case the waiting time should also be smaller in 
> order to minimize the delay to support multiple route discoveries. 
> Shorter waiting time may create broacast congestion and failure on other 
> routes which is a killing situation. Here, serious time adaptability is 
> missing. The exponential backoff won't help.
> 
> The case with unidirectional links is a straightforward example. Assume 
> a node C with a strong transmission power and all other nodes with lower 
> power. Node C is on the path between a node A and a node B. Assume that 
> node C has, say, 10 unidirectional neighbors on that path toward B. The 
> first RREQ from A to B will go through C and via these neighbors and in 
> return the RREP will fail on one of these neighbors. The later will list 
> node C in its blacklist. After an initial waiting time, node A will 
> issue a new RREQ and the RREP will in return go via another 
> unidirectional neighor (since the first blacklisted link is denied): 
> therefore a second blacklisted link. And so forth until all 
> unidirectional links have been blacklisted one by one: 10 route 
> discoveries attempt. Applying binary exponential backoff, you will 
> experience a delay larger than 1,000 times the initial route discovery 
> interval time.
> 
> If meanwhile one of the unidirectional neighbor un-blacklist its links 
> (this the only way to check if the link is now symmetric), then the 
> route discovery process may never end nor succeed. The blacklist period 
> (not specified in the draft) should be longer than the route discovery 
> delay.
> 
> It seems that DYMO shows some fragility with respect to timers. I think 
> it would be good to specify at least some strong adaptability algorithms 
> to correct this. I don't think you need to pickup from proactive 
> protocols for this end.
> 
> Below some links to real experiments where problems with recovery time 
> occurred.
> 
> 
> http://www.reseaucitoyen.be/wiki/index.php/ExperiencesAODV
> http://www.seattlewireless.net/OpenWrt
> 
> 
> 
> Charles E. Perkins a écrit :
>> Hello Philippe,
>>
>> I really want to understand your point, but I confess
>> that I am somewhat mystified and not yet getting it.
>>
>> How does OLSR adapt to "space"?  Do you mean
>> Euclidean space with constant radio range?  I can just
>> see the point about topology (because of MPRs),
>> but I think we should insist that both DYMO and
>> OLSR be equally able to utilize some SMF (or, lately for
>> us, SMURF) ways of flooding over reduced relay sets.
>>
>> As I understand this, the common dependence on a
>> reduced relay set will give both proactive and reactive
>> approaches equal adaptability to topology.  But this
>> still doesn't enlighten me about adaptability in space.
>>
>> Regarding the adaptability in time...
>>
>> DYMO has the following time-based dependencies
>> - route timeouts
>> - shifting route discovery anywhere up to and
>>     including application launch
>> - some second order effects about sequence
>>    numbers.
>> I can definitely see a role for a new extension which
>> enables nodes in a path to specify a non-default
>> value for the route timeout.  But it is not clear to me
>> that this is what you are referring to.  Could you be
>> a bit more explicit?
>>
>> Anyway, this note is a long way of asking for more
>> details, and I hope you won't mind having a longer
>> discussion about it.
>>
>> Finally, if you would care to point out cases where
>> DYMO performs poorly, but which are not able
>> to be explained by reliance on brute-force flooding,
>> it would be appreciated.  I know about the case of
>> fully-connected traffic patterns, and a few other
>> corner cases, but somehow I feel you may have
>> something else in mind.
>>
>> Regards,
>> Charlie P.
>>
>>
>> ext Philippe Jacquet wrote:
>>> I would say that from a very broad perspective, on-demand protocols 
>>> discriminate routes with respect to time and proactive protocols 
>>> discriminate routes with respect to space. Personnally I have 
>>> preference to proactive approach because it is richer and gives better 
>>> internet legacy. Objectively the two approaches have their advantages 
>>> and drawbacks and the two should be considered.
>>>
>>> This said, I don't think that on-demand and proactive approaches are 
>>> represented at the same level in MANET. OLSRv2 has "space" 
>>> adaptability: i.e algorithms which automatically adapt to space and 
>>> topology variety, including for instance the MPR mechanism. In DYMO I 
>>> don't see an equivalent "time" adaptibility that goes beyond the 
>>> default values in timers. I think this may explain why the protocol 
>>> performs great in some scenario and very poorly in other.
>>>
>>> Some adaptability feature in DYMO would be welcome, not necessarily 
>>> proactive, but at least some memory based feature could help.
>>>
>>> Philippe
>>>
>>> David Murray a écrit :
>>>> Hi,
>>>>
>>>> I am wondering how DYMO fits in with the other routing protocols. I 
>>>> have read a number of papers that discuss how on-demand routing 
>>>> protocols like DSR/AODV work better in highly mobile environments 
>>>> where movement is fast, CPU and memory are low and batteries are 
>>>> limited. Equally, in situations where movement is very low, and there 
>>>> are no power limitations, protocols like OLSR/TBRPF/STAR perform better.
>>>>
>>>> So, I have a mental picture of OLSR/TBRPF being predominantly used in 
>>>> stationary 802.11 mesh devices and AODV/DYMO being used to connect 
>>>> users mobile devices ush as phones and PDAs. Is this correct or are 
>>>> things not quite as simple as this? (I know RFC 2501 discusses MANET 
>>>> applications and characteristics but the discussion is quite general)
>>>>
>>>> If this is correct, it seems to me that DYMO and AODV are used in 
>>>> very similar situations (the ad hoc interconnect between users 
>>>> devices). I am aware that DYMO is a simplified version of AODV both 
>>>> in code and network operation. It seems like the major difference is 
>>>> the path accumulation feature in DYMO which allows nodes to append 
>>>> their information to a RREP to give other nodes better knowledge of 
>>>> the topology. It also seems that the hello feature has been removed 
>>>> in DYMO. So, is DYMO likely to be a replacement for AODV or do they 
>>>> have different uses/applications?
>>>>
>>>> Thanks for your time
>>>>
>>>> Dave
>>>>
>>>>
>>>> _______________________________________________
>>>> 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