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

From: Philippe Jacquet <[email-masked]>
Date: Tue, 12 Jun 2007 11:31:46 +0200

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

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

---

From: "Justin Dean" <[email-masked]>
Date: Tue, 12 Jun 2007 10:44:24 -0400

There has been some discussion among the authors of packetbb on the merits
of adding an optional extended TLV type field (as well as the comments
charlie has posted to the list.)  While attempting to write a metric TLV
document based on packetbb, for use with MANET protocols, the issue of how
to include/define multiple metric types without using up a lot of the TLV
type space came up.  By using an optional type sub field a generalized
metric TLV document can be written to allow for multiple metric types,
different sized value fields, differing value representations, and how the
metrics are to be used.  This can be done with the current TLV type field
but I can easily envision 10s if not 100s of metric types in the future.
With our current space there would be little room for official assignments.

The benefits are not limited to an unfinished not yet released TLV metric
document.  A TLV type field could be assigned to a commercial or research
entity which would then allow much more flexibility in defining TLVs by
using the subtype field, without having to resort to using the experimental
(and possibly conflicting) TLV type space in the current TLV type field.

On the negative side TLVs which used the extend type field would be 8 bits
longer per TLV.  TLVs which are concerned with 8 bits per TLV would not be
forced to use this subfield however and there would be no extra overhead
involved.  An extra semantics bit would be assigned as outlined below.  This
would make the specification slightly more complex and only 2 bits would be
left for future use in the semantics field.  (In my mind if we aren't using
them they are going to waste and if we have a good use for them we should be
using them)

The proposed changes would comprise mostly of the following. 

In Section 5.3 change to:

       <tlv> = <tlv-type>
               <tlv-semantics>
               <tlv-subtype>?               <-new optional field
               <index-start>?
               <index-stop>?
               <length>?
               <value>?

In Section 5.3 change to:

      bit 5 (hassubtype):  if cleared ('0'), then <tlv-subtype> is not
         included in <tlv>.  If set ('1'), then <tlv-subtype> is 
         included in <tlv>.

      bits 6-7:  are RESERVED and MUST each be cleared ('0') to be in
         accordance with this version of the specification.

In Section 5.3 add:

   <tlv-subtype>  is an 8 bit field, specifying the subtype of the TLV,
      specific to the TLV type and kind (i.e. packet, message, or address
      block TLV).

   tlv-subtype  is a variable, defined to equal <tlv-subtype> if
      present, or 0 otherwise.

   tlv-fulltype  is a variable, defined by:

      *  tlv-fulltype = 256 * <tlv-type> + tlv-subtype;

Section 5.3.2 change to:

   TLVs in the same TLV block MUST be sorted in ascending tlv-fulltype
   order.

   Two or more TLVs with the same tlv-fulltype associated with the same
   address block MUST NOT both cover any address.

   TLVs with the same tlv-fulltype associated with the same address block
   MUST be sorted in ascending index-start order.

In Section 6.1 Table 5 add column Subtype. In existing row set to 0.
Add new row for subtype 1-255 RESERVED.

In Section 7 change to

   A new registry for packet TLV types must be created, with no initial
   assignments.  Future values in the range 0-127 can be allocated using
   standards action [3].  Additionally, values in the range 128-255 are
   reserved for private/local use.  If a TLV type is allocated a new
   registry for subtypes of that type must be created.

   A new registry for message TLV types must be created with no initial
   assignments.  Future values in the range 0-127 can be allocated using
   standards action [3].  Additionally, values in the range 128-255 are
   reserved for private/local use.  If a TLV type is allocated a new
   registry for subtypes of that type must be created.

   A new registry for address block TLV types must be created with
   initial assignments as specified in Table 7.  Future values in the
   range 1-127 can be allocated using standards action [3].
   Additionally, values in the range 128-255 are reserved for private/
   local use.  If a TLV type is allocated a new registry for subtypes
   of that type must be created.

Justin Dean

---

From: "Dearlove, Christopher \(UK\)" <[email-masked]>
Date: Tue, 12 Jun 2007 16:02:57 +0100

> of adding an optional extended TLV type field

I judge modifications to packetbb (and other protocols here)on four main
axes:

- Extensibility
- Simplicity
- Efficiency
- Timeliness

On these four axes, this proposal is aimed at increasing extensibility,
and Justin has a reasoned argument for it. I'm not completely sold on
that we will need more TLVs than we can afford out of the general space
(proprietary extensions can use the 128+ space) but neither can I be
sure
they won't be needed. This is a cost on the simplicity axis; not a lot
in the ID (I wrote the changes Justin quotes - he's omitted a couple of
details I found as not essential to this discussion) but some in code.
This is a potential issue for those who are considering formal testing.
On efficiency it's neutral, or actually arguably a gain as some possible
alternatives if you do run out of TLV types are inefficient. But the
key one to my mind is timeliness. packetbb is on the critical path of
all the WG protocols, and it is not just due, but overdue, to get it to
the IESG. If the consensus is "do this, just this, get it out" that's
tolerable. If it opens the gates to people wanting all sorts of other
things added/changed (apart, of course, from editorial matters - and
we've also taken on board splitting message header options) then we
as a WG (and the active packetbb authors in particular) really can't
afford this. I'd rather go without this than introduce further such
delay.

(I - not uniquely, but unlike most people here - would also have to
change my packetbb software. I haven't made this an issue above, but
it is an issue for me, mostly about testing, even though mine isn't
formal.)

********************************************************************
This email and any attachments are confidential to the intended
recipient and may also be privileged. If you are not the intended
recipient please delete it from your system and notify the sender.
You should not copy it or use it for any purpose nor disclose or
distribute its contents to any other person.
********************************************************************

---

From: Philippe Jacquet <[email-masked]>
Date: Tue, 12 Jun 2007 18:00:11 +0200

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:[email-masked]] 
> Sent: Tuesday, June 12, 2007 5:32 AM
> To: Charles E. Perkins
> Cc: [email-masked]; [email-masked]
> Subject: Re: [manet] DYMO and other routing protocols
> 
> Dear Charlie,
>

---

From: "Joe Macker" <[email-masked]>
Date: Tue, 12 Jun 2007 16:16:27 -0400

Right, an early paper 2001 Mobihoc by the same authors introduced a general
class term called fuzzy sighted link state(FSLS). For experimentation we
built a version of this into an early OLSR implementation at NRL.

http://cs.itd.nrl.navy.mil/pubs/docs/ls_scaling_milcom03.pdf

In the previous paper, we were able to use an OLSR implementation to compare
fuzzy-sighted link state (FSLS), FSLS+MPR, MPR, and classical flooding for
LS flooding. This analysis only did overhead scaling comparison, but it
demonstrated some of the tradeoffs with density and diameter taken into
account the design from the initial paper in combination with a working
MANET protocol.  As Phillile mentions others have done fisheye work as well.

You do require longer term global state flooding so for long period
fragmentations/changes there are some resynch/delay issues since less
localized entries state will time out eventually.  However such changes may
trigger more reactive route learning as a possible solution. 

-Joe

>From: David Young [mailto:[email-masked]] 
>Sent: Tuesday, June 12, 2007 12:55 PM
>To: [email-masked]; [email-masked]
>On Tue, Jun 12, 2007 at 08:54:00AM -0400, Herbert Rubens wrote:
>> technically can't be routing reliably without a flood 
>propagating the 
>> entire network.
>
>As a practical matter, you do not ordinarily need to flood the 
>entire network following a change of linkstate.  You do need 
>to flood the region a few hops in diameter where most loops 
>occur.  See 
><http://www.ir.bbn.com/documents/techmemos/TM1301.pdf> for a 
>discussion.
>
>Dave
>
>-- 
>David Young             OJC Technologies
>[email-masked]      Urbana, IL * (217) 278-3933 ext 24
>
>