RE: [manet] DYMO and other routing protocols

["Joe Macker" <[e-mail]>]

Some 2 cents.

Link state variants can be made more reactive and may provide other
opportunities for robustness management.  Also, MANET multicast may be the
better way to go for some network traffic in extreme edge temporal
fragmentation cases or at least it should be considered.  I think it really
depends on not just the scenario but the applications and traffic patterns
desired.  A real user traffic model is needed to properly analyze and I
don’t buy general statements.  Fuzzy-sighted approaches (also having been
done within OLSR implementations) have exhibited good scaling properties and
can be made to converge in different ways depending on the scenario
requirements and assumptions.  Previous analyses showed that for dense
networks and networks with small relative diameters (8 hops or less) that
optimized flooding was a more important scaling feature than fuzzy sighted
methods but dynamic convergence properties needed more study.  Reactive
approaches can also be made more proactive (e.g., maintaining gateway
routes,etc even when not on demand). For large networks, I think there is
some interesting additional work for someone to do regarding the convergence
potential of fuzzy-sighted or fisheye methods.  This is outside the present
engineering WG charter but implementations already exist that work with core
WG designs. I believe spatial-temporal realtionship can be made more
reactive in nature (to improve delay), but as Phillipe says even without
that the route convergence can generally improve as one gets closer to the
destination.  Certainly there is no one size fits all.  Also rather than
generalizing comparative analysis, one needs to think about protocol control
requirements under peak conditions as well (e.g., what happens when everyone
needs routes at once). In other words, a peak analysis may be more important
than average routing overhead analysis for some deployments and the fact
that some MANET platforms have entire prefixes or sets of prefixes behind
them including possible heterogeneous interfaces (normal IP routing)...

Also John, since you mentioned the ACK control tradeoff issue, if you are
interested the IETF MANET-OSPF design team did some evaluation on examining
tradeoffs between ACK-based control and best effort control propagation.

-Joe
>-----Original Message-----
>From: Mullen, John [mailto:[e-mail]] 
>Sent: Tuesday, June 12, 2007 2:31 PM
>To: [e-mail]
>Subject: RE: [manet] DYMO and other routing protocols
>
>Agreed Philippe,
>
>My computations were greatly simplified. However, there is 
>always a finite probability of error and it sounds like 
>fisheye in OLSRD takes this into account. However, this is my concern.
>
>I work with MANETs that support critical operations, e.g., 
>military, disaster relief, fire fighting, etc. In these 
>applications, the node distribution can be very uneven and 
>quite dynamic, due to operational needs. For example, 
>firefighters will place themselves along the perimeter of a 
>forest fire and tend to work in uneven terrain. Hence, routes 
>are likely to have little redundancy and even a small amount 
>of movement could require a change, say if a node drops below 
>a ridge.  As a result, an error is more likely to manifest 
>itself. In addition, there are people at risk and a loss of 
>communications could have serious consequences. My feeling is 
>that an acceptable MANET routing protocol needs to be robust 
>enough that such errors do not cause an unnecessary failure. 
>In addition, it is possible that such nets will become 
>partitioned from time to time, so the protocol needs to be 
>able to rejoin partitioned nets quickly. I think this is 
>harder if a global link state approach is taken than if the 
>long haul is reactive. 
>
>Bye for now,
>
>John P. Mullen, Ph.D.
>[phone]
>[e-mail]
> 
>-----Original Message-----
>From: Philippe Jacquet [mailto:[e-mail]]
>Sent: Tuesday, June 12, 2007 11:15 AM
>To: Mullen, John
>Cc: [e-mail]
>Subject: Re: [manet] DYMO and other routing protocols
>
>You are right that the information about a local link will 
>have an increasing probability to be wrong when the distance 
>increases. Not as dramatic as you suggest (because the number 
>of path for the TC to reach a remote node also increases with 
>distance and may correct the one path failure probability). In 
>this case a node database will give you a "fisheye" view of 
>the network: locally precise, more fuzzy at long distance. The 
>impact is not dramatic because the route starting from far
>  takes the good direction and details about the local wrong 
>links are resolved at the end. The path is thus very close to optimal.
>
>For this, you must activate the fisheye option, introduced by 
>Gerla of UCLA and included in OLSR long time ago. This allows 
>to deal with large network (with lot of hops and lot of 
>nodes). The principle is that TCs with large TTL are 
>transmitted less frequently but with larger time to live 
>(otherwise remote nodes will timeout link set before a new TC 
>arrive). Other advantage: the control overhead is reduced and 
>scales better.
>
>This is included in the basic OLSRD codes and is used in 
>practical implementation.
>
>Philippe
>
>Mullen, John a écrit :
>> Good points!
>> 
>> If that were not enough, it is the nature of wireless 
>communications that any transmission attempt may fail on a 
>"working" link or be successful on a "non-working" one. 
>Because there is always a finite probability of success on all 
>links, one cannot be entirely sure which nodes actually get 
>each updates, assuming they are sent UDP. If you use ACKs, on 
>the other hand, there is the problem of deciding which node(s) 
>decide when each update is complete and how that knowledge is 
>made known to the network. 
>> 
>> I think this problem is manageable in a small, local net, 
>but I'm not aware of a solution that is scalable to a MANET 
>containing routes of four or more links. Between random 
>variations in received signal strength due to fading and 
>shadowing, local interference, overflowing buffers, and who 
>knows what, the chances of every update reaching all nodes in 
>a geographically large MANET are very small. Thus, it would be 
>unlikely that all nodes would have the same image of the 
>topology, meaning their tables would be inconsistent with each 
>other and at odds with the real link states. For that reason, 
>any proactive protocol needs to acknowledge that each node's 
>tables are estimates of the actual link states and must be 
>robust enough to deal with incomplete information.
>> 
>> This is one reason I think a hybrid approach would be 
>advisable. Nodes in a one-, or maybe two-hop neighborhood 
>could exchange link data frequently, e.g., by Hello messages, 
>and would have a good chance of having locally consistent link 
>state data. These tables could provide stable data as a basis 
>for long-haul routes, improving the chances of a good route, 
>and accomplish local repair. However, the overhead for 
>informing an entire large MANET would be considerable. Aside 
>from the larger number of links to update, because probability 
>of end-to-end success decreases with the number of hops, all 
>other things being equal, updates for distant nodes would have 
>to be either ACKed or transmitted multiple times in order to 
>have the same assurance that link data is correct globally as 
>it would be locally.
>> 
>> To illustrate.
>> 
>> Suppose the probability of successful reception on a single hop is 
>> 0.98 (Don't we wish!) and our standard is Pr(successful updates) >= 
>> 0.95. Then,
>> 
>> # hops    Pr(sucess in one try)     minimum # tries for 
>Pr(sucess) >= 0.95
>> 
>>    1             0.980                          0.77 -> 1
>>    2             0.960                          0.93 -> 1
>>    3             0.941                          1.06 -> 2
>>    4             0.922                          1.17 -> 2
>>    5             0.904                          1.28 -> 2   
>> 
>> The actual degradation will depend on the actual 
>probabilities, which can be expected to differ by link and 
>change over time, but the principal will remain the same. More 
>distant nodes will have a greater chance of not receiving 
>updates. To compensate, one would either have to send multiple 
>copies of the update or use ACKs.  
>> 
>> Node density also plays a role. If a node has four one-hop 
>neighbors and the probability of success on each link is 0.98, 
>the probability that all four of its neighbors receiving a 
>single UDP update is only 0.92. If we modify the standard to 
>require that the probability of all nodes receiving the update 
>be at least 0.95, now one needs two transmissions of each 
>update just to meet the standard in the one-hop neighborhood. 
>Going further not only increases the number of hops, but also 
>the number of nodes, so at some point, the overhead would 
>become impractically high. Additionally, sending multiple 
>copies of an update or using ACKs will increase the average 
>time to propagate the updates, which will increase the risk 
>that the update itself is actually no longer valid. And that 
>is just to be 95% sure that all nodes have current data. There 
>is still a 5% chance that any random node will have invalid data. 
>> 
>> The number of updates also affects the situation. Suppose 
>there are ten updates a minute, each containing only the 
>changed information, not the complete set of MANET link 
>states, and the probability that each update is successful is 
>0.95. The probability that all nodes will have correct data 
>from all ten of the changes that occurred in that one minute, 
>after enough time has passed to propagate the updates, is only 
>about 0.6.
>> 
>> Although the actual numbers may differ, there will always be 
>some probability of failure on an attempt on any link, so 
>there will always be a sizable chance that any random node 
>will have incorrect link state data. Reducing the maximum 
>probability of invalid data increases the difficulty of 
>meeting that standard exponentially. Reducing it to zero is impossible.
>> 
>> Bottom line: To be successful in a wireless MANET, the 
>routing protocol needs to live with the fact that any tabled 
>information may not be current and have mechanisms to deal 
>with that possibility.
>> 
>> John P. Mullen, Ph.D.
>> [phone]
>> [e-mail]
>>  
>> -----Original Message-----
>> From: Herbert Rubens [mailto:[e-mail]]
>> Sent: Tuesday, June 12, 2007 6:54 AM
>> To: 'Philippe Jacquet'; 'Charles E. Perkins'
>> Cc: [e-mail]; [e-mail]
>> Subject: RE: [manet] DYMO and other routing protocols
>> 
>> 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:[e-mail]]
>> Sent: Tuesday, June 12, 2007 5:32 AM
>> To: Charles E. Perkins
>> Cc: [e-mail]; [e-mail]
>> 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
>>>>> [e-mail]
>>>>> https://www1.ietf.org/mailman/listinfo/manet
>>>>>
>>>>>
>>>>
>>>> _______________________________________________
>>>> 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 mailing list
>> [e-mail]
>> https://www1.ietf.org/mailman/listinfo/manet
>> 
>> 
>> _______________________________________________
>> 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 mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/manet