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

[Philippe Jacquet <[e-mail]>]

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
>>> [e-mail]
>>> https://www1.ietf.org/mailman/listinfo/manet
>>>
>>>
>>
>>
>> _______________________________________________
>> manet mailing list
>> [e-mail]
>> https://www1.ietf.org/mailman/listinfo/manet
> 
> 


_______________________________________________
Manet-dt mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/manet-dt