Subject: [manet] DYMO and other routing protocols

From: David Murray <[email-masked]>
Date: Wed, 06 Jun 2007 16:26:20 +0800

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

---

From: "Ian Chakeres" <[email-masked]>
Date: Wed, 6 Jun 2007 14:13:54 +0530

There is no winner takes all in the contest of routing protocols for
MANET. I think each protocol and its supporters can easily make a case
where it will beat other protocols. Simply look at conference
publications for good examples.

That said, we have chosen to standardize DYMO and OLSRv2 - one
reactive and one reactive protocol in the MANET WG. For more
information regarding when one might deploy one or the other, please
see the applicability statements in the drafts.

DYMO is a successor to AODV (and other reactive protocols). The
specification is chartered to become a proposed standard. AODV is not
being actively discussed or standardized in the WG.

Ian

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 06 Jun 2007 11:40:05 -0700

Hello folks,

I am quite hopeful that we can get to a converged
routing protocol that will subsume the best aspects
of DYMO and OLSR.  We have many recent
results pointing the way forward, some of which
I presented at the last IETF.  I am hoping to have
a much more complete presentation ready for the
next meeting.

I think it is clear by now that proactive protocol
operation is better when either there is a strong
requirement for minimizing latency in an uncongested
network, or when the traffic patterns are not very
sparse.  So, for instance, if most nodes in an ad
hoc network have open communications with most
other nodes in the same network, the communication
pattern is not at all sparse.  The tricky point is to find
out how dense the traffic pattern needs to be in order
to favor proactive operation (or, alternatively, how
sparse the traffic has to be in order to favor
reactive operation).

Furthermore, it is quite likely that some routes
should be proactively maintained even if route
table entries are generally acquired on demand.
The canonical example is that nodes need a
route to a gateway [if one exists] (or default router)
often enough that the route should always be there.
Whether this is done by periodic advertisement or
by triggered route repairs is a matter for further
study.  One could imagine similar requirements
might be imposed for important servers in the
network (e.g., certificate authority, data sink, ...).

I do _not_ think that proactive protocols should
automatically be the choice for mesh backbone routers.
Certainly not for all mesh clients...!  I would really
question whether it is needed for all other mesh
points anyway.  Plus, the whole concept gets quite
fuzzy if there are intermittent long-range connections
to neighboring meshes (as an example).

Regarding the naming of AODV vs. DYMO: this is
a long story with as much political as technical content,
and for my own part the former was by far the more
persuasive factor to persuade me to agree to a new
name for the standards-track reactive protocol.
Now the downside is that we have exactly the confusion
in evidence currently for newly interested parties.  Perhaps
we should rename DYMO to be AODVv2 :-)

Finally, regarding:
>   I think each protocol and its supporters can easily make a case
Simply stated: caveat emptor.

Stated more verbosely and redundantly using more words
and so on...
---> it is very important to fully understand the range
         of applicability for each research result.  These are
         sometimes not stated very clearly.  It is also very
         helpful, when possible, to understand the motivations
         of the authors.

Regards,
Charlie P.

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 08 Jun 2007 12:36:29 +0200

Charles E. Perkins wrote:
> 
> Hello folks,
> 
> I am quite hopeful that we can get to a converged routing protocol 
> that will subsume the best aspects of DYMO and OLSR.

I'm in the process of reading OLSRv2 spec for seeing it fitting MANEMO
topologies.

As an external, I must say that I would very much favor only one MANET
routing protocol and not two.  It simply takes too much effort to just
read two documents (30+70 pages), not even mention the time it takes to
implement both protocols.

If possible, the length of a common protocol document should be upper
bounded, something like half the sum of parts.

Covergence is the only option now, IMHO, after all this time.

Alex

> We have many recent results pointing the way forward, some of which I
>  presented at the last IETF.  I am hoping to have a much more
> complete presentation ready for the next meeting.
> 
> I think it is clear by now that proactive protocol operation is 
> better when either there is a strong requirement for minimizing 
> latency in an uncongested network, or when the traffic patterns are 
> not very sparse.  So, for instance, if most nodes in an ad hoc 
> network have open communications with most other nodes in the same 
> network, the communication pattern is not at all sparse.  The tricky
>  point is to find out how dense the traffic pattern needs to be in 
> order to favor proactive operation (or, alternatively, how sparse the
>  traffic has to be in order to favor reactive operation).
> 
> Furthermore, it is quite likely that some routes should be 
> proactively maintained even if route table entries are generally 
> acquired on demand. The canonical example is that nodes need a route
>  to a gateway [if one exists] (or default router) often enough that 
> the route should always be there. Whether this is done by periodic 
> advertisement or by triggered route repairs is a matter for further 
> study.  One could imagine similar requirements might be imposed for 
> important servers in the network (e.g., certificate authority, data 
> sink, ...).
> 
> I do _not_ think that proactive protocols should automatically be the
>  choice for mesh backbone routers. Certainly not for all mesh 
> clients...!  I would really question whether it is needed for all 
> other mesh points anyway.  Plus, the whole concept gets quite fuzzy 
> if there are intermittent long-range connections to neighboring 
> meshes (as an example).
> 
> Regarding the naming of AODV vs. DYMO: this is a long story with as 
> much political as technical content, and for my own part the former 
> was by far the more persuasive factor to persuade me to agree to a 
> new name for the standards-track reactive protocol. Now the downside
>  is that we have exactly the confusion in evidence currently for
> newly interested parties.  Perhaps we should rename DYMO to be AODVv2
> :-)
> 
> Finally, regarding:
> Stated more verbosely and redundantly using more words and so on... 
> ---> it is very important to fully understand the range of 
> applicability for each research result.  These are sometimes not 
> stated very clearly.  It is also very helpful, when possible, to 
> understand the motivations of the authors.
> 
> Regards, Charlie P.
> 
> 
> ext Ian Chakeres wrote:
>> There is no winner takes all in the contest of routing protocols 
>> for MANET. I think each protocol and its supporters can easily make
>>  a case where it will beat other protocols. Simply look at 
>> conference publications for good examples.
>> 
>> information regarding when one might deploy one or the other, 
>> please see the applicability statements in the drafts.
>> 
>> specification is chartered to become a proposed standard. AODV is 
>> not being actively discussed or standardized in the WG.
>> 
>> Ian
>> 
>>> 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 mailing list 
> [email-masked] https://www1.ietf.org/mailman/listinfo/manet
> 

______________________________________________________________________
This email has been scanned by the MessageLabs Email Security System.
For more information please visit http://www.messagelabs.com/email 
______________________________________________________________________

---

From: Philippe Jacquet <[email-masked]>
Date: Fri, 08 Jun 2007 13:12:14 +0200

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.
> 
> 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)
> 
> 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

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 08 Jun 2007 13:57:51 +0200

Philippe Jacquet wrote:
> 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.

I mostly agree (although I don't see the spatio-temporal discrimination,
not even the frequency-temporal :-)

I think the classification on-demand vs proactive is conceptual only,
helping frame one's mind around two ways of obtaining routes.

That classification can't really be used to pit a protocol vs another.

OLSRv2 document says it's proactive but I think an OLSRv2 implementation
must be able to obtain a route if it receives a app packet whose dst it
doesn't know, and if it doesn't have a default route.  Making it on-demand.

Similary, DYMO says it's on-demand but it should advertise RREP (or
RREQs) periodically if it needs to maintain up to date information at
all times.  Making it reactive.

OLSRv2 says it's 'table-driven'.  But DYMO uses tables too.

Similar things apply to link-state vs distance-vector distinction.

I think I personally would like to escape this artificial classification.

In my humble oppinion.

Alex

>  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.
> 
>> 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 
>> 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
>> 
>>

---

From: "Dearlove, Christopher \(UK\)" <[email-masked]>
Date: Fri, 8 Jun 2007 13:47:23 +0100

> doesn't know, and if it doesn't have a default route.

Not in that way.

Using the protocol as to be standardised, if an OLSR (v1 or v2) node
receives a packet from destination it doesn't know, it does nothing
to find that route.

There is allowed to be responsiveness (a term we use as say
reactiveness would be confusing) in the protocol at the signalling
level. If an OLSR (v1 or v2) node receives a HELLO message containing
information about a neighbour it's never heard of, it doesn't
have to maintain its current fixed schedule to send a HELLO
message containing this extra information, but can do so early.
This will accelerate what you want here, and may even look reactive.
But it's more than just subtly different. A node that wants to
find node X can't make that happen, it has to wait for node X to
inform it (directly or, more usually, via other nodes).

> all times.

But maintaining up to date information about all destinations at all
times is not necessarily desirable. (Talk to 6LoWPAN people about this,
for example.)

********************************************************************
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: "Mullen, John" <[email-masked]>
Date: Fri, 8 Jun 2007 09:51:39 -0600

I've been lurking on current topics and agree with most comments.
Nevertheless, I decided to peep up.

I think, in the end, at the least there will be a common framework for a
MANET routing protocol which employs a mix of strategies. A proactive
protocol has its advantages, but is not practical for very large
networks, due to the fact that the status of a wireless link is often
not easily determined and that it takes time for updates to propagate.
At some point, few, if any, nodes in the network will have an accurate
set of tables and no node will be sure that the data it has is accurate.
On top of that, you have bandwidth being used to propagate routing
information that may never be used.

On the other hand, while on-demand protocols address these issues, there
is an initial latency for establishing a new route. In addition,
bandwidth is consumed in searches and nodes are not much more confident
in their data. 

In the "real" world, MANETS differ greatly in a number of features,
including node density, propagation characteristics, traffic patterns
and intensity, etc. In addition, one can expect MANETs to be
heterogeneous. There may be a few clusters of nodes in an otherwise
sparse network, much like the manner in which human population is
distributed. Propagation conditions may vary within the range of the
network. Traffic patterns and intensity may change drastically from time
to time.

While Hello messages can be useful, I think we have to be careful. For
several reasons, they can be reliably received over significantly
greater distances than data packets. I do think they should be used, but
not without some independent assessment of the ability of the connection
to transfer data.

I suspect that in the end, the design will be to have a table-driven
proactive mode for nearby nodes and an on-demand mode for the long haul.
It should be relatively easy for nodes to maintain tables of one-hop
neighbors and two-hop is not that much more difficult. Clustering is a
possible approach here, as well, though it does require a bit more
sophistication. If there are also shared records of current long-haul
routes, the combination can reduce the time and bandwidth needed to find
or repair a route. 

It took a long time for people to work out the nasty details for radio
communications and in the beginning, operators relied on a few basic
controls and their skill. Now, we know enough to reliably handle that
mess through hardware and software. A basic MANET protocol in which
different features can be "tweaked," either manually or through
algorithms, would provide a sound basis on which to study the messier
problems and, over time, find good solutions. That is, a common protocol
would provide a common framework in which to conduct experiments and
report results in a manner that all involved could understand and
evaluate. Establishing that common protocol would be a giant step in the
direction we all want to go.

Bye for now,

John P. Mullen, Ph.D.
(505) 646-2958
[email-masked]
 
-----Original Message-----
From: Dearlove, Christopher (UK) [mailto:[email-masked]] 
Sent: Friday, June 08, 2007 6:47 AM
To: Alexandru Petrescu; Philippe Jacquet
Cc: [email-masked]
Subject: RE: [manet] DYMO and other routing protocols

Not in that way.

---

From: "Charles E. Perkins" <[email-masked]>
Date: Fri, 08 Jun 2007 12:04:21 -0700

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:
> 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.
>
>> limited. Equally, in situations where movement is very low, and there 
>> are no power limitations, protocols like OLSR/TBRPF/STAR perform better.
>>
>> 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
>>
>>

---

From: "Charles E. Perkins" <[email-masked]>
Date: Fri, 08 Jun 2007 12:14:22 -0700

Hello Alexandru,

> helping frame one's mind around two ways of obtaining routes.
Well, leaving aside the notion that all work in the IETF is
conceptual only, I am not sure just what you mean.  In my
view, on-demand routing is one of the main contributions
of [manet] to routing technology.
> That classification can't really be used to pit a protocol vs another.
It has proved to be a very useful conceptual tool, helping
a lot of people organize their thoughts about the way
protocols work.
> all times.  Making it reactive.
I know you meant "proactive".  This is not in the protocol
specification, but for some particular cases I quite agree.
A better example would be "HELLO" messaging.

Generally speaking, just because two classifications are
not mathematically contradictory, does not make them
useless -- right??  We use blue and green to describe things
as needed, and no one complains based on the existence of
turquoise or aqua.  If you would rephrase your point to
instead say that we should avoid being constrained by
the way we have classified things in the past, I would very
much agree with you.

Regards,
Charlie P.

---

From: "Krishna Sankar \(ksankar\)" <[email-masked]>
Date: Fri, 8 Jun 2007 12:25:37 -0700

Philippe,

	Interesting discussions. Couple of questions:

> space. Personally I have preference to proactive approach 
> because it is richer and gives better internet legacy. 
<KS>
	I would argue exactly the opposite - reactive protocols are more "internet-native". Let me explain:

	a)	In internet you resolve end point locations thru DNS (and optimize it by caching and querying when a cache is invalid, one does not query every time nor one has all the resolution database locally)
	b)	Naturally internet is packet based not circuit based
	c)	The routes do change based on congestion, peering, even optimized edge routing and multi topology routing based on declarative policies and "coloring"
	<I am just naming a few instance I know of from my very limited knowledge>
</KS> 
> Some adaptability feature in DYMO would be welcome, not 
> necessarily proactive, but at least some memory based feature 
> could help.
<KS>
	Are you talking about spatial interpolation based on history ? Mobility algorithmics based on 1st and 2nd order derivatives of mobility vectors - For example if we know a node is moving, if we can infer the acceleration and also the spatial topology, we could possibly say where it could be and what the route could be knowing the nodes in that vicinity ...
</KS>

Cheers
<k/>
> From: Philippe Jacquet [mailto:[email-masked]] 
> Sent: Friday, June 08, 2007 4:12 AM
> To: David Murray
> Cc: [email-masked]
> Subject: Re: [manet] DYMO and other routing protocols
> 
> 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 
> 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,
> > 
> > DYMO. So, is DYMO likely to be a replacement for AODV or do 
> they have different uses/applications?
> > 
> > Thanks for your time
> > 
> > Dave
> > 
> >

---

From: "Charles E. Perkins" <[email-masked]>
Date: Fri, 08 Jun 2007 12:34:01 -0700

Hello John,

ext Mullen, John wrote:
> MANET routing protocol which employs a mix of strategies.
In the new millenium, "framework" is a derogatory term (isn't it?).
I reckon it would be better to position such an effort as a hybridized
or parameterized protocol, which activates perhaps somewhat
different "strategies" (i.e., protocol messages) depending on the
recent state of the network -- or alternatively based on application
requirements.
> ... no node will be sure that the data it has is accurate.
>   
Mobility ==> inaccuracy, to a very large extent.  Some approaches
use velocity information to place a bound on the inaccuracy, but
these have had variable success.  So I don't think we can achieve
the goal of enabling nodes to have complete "confidence".  But we
can devise strategies so that nodes can recover from error conditions.
>   ...  Establishing that common protocol would be a giant step in the
I think we know enough to start pursuing this goal, but on the
other hand such an effort should be managed very carefully
so that we do not impede progress towards achieving our
current charter items.

Regards,
Charlie P.

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 11 Jun 2007 11:52:25 +0200

Charles E. Perkins wrote:
>> I think the classification on-demand vs proactive is conceptual 
>> only, helping frame one's mind around two ways of obtaining routes.
>> 
>> 
> 
> conceptual only, I am not sure just what you mean.  In my view, 
> on-demand routing is one of the main contributions of [manet] to 
> routing technology.

Yes, that notion not purposefully stressed, I mean that it does not make
sense to push two different protocols just because the conceptual 
distinction makes sense.

On-demand routing (create routing data at most or all intermediary nodes
onyl when end nodes need to communicate) seems to me indeed to be a main
contribution of IETF manet to routing technology.  It is different than
other IETF routing in that it can accommodate potentially very variable
topologies.

> It has proved to be a very useful conceptual tool, helping a lot of 
> people organize their thoughts about the way protocols work.

I think yes.

>>  RREQs) periodically if it needs to maintain up to date information
>>  at all times.  Making it reactive.
> 
> specification, but for some particular cases I quite agree. A better 
> example would be "HELLO" messaging.

I think we talk here about a proactive need.  I take your mentioning of
HELLO just an example of semantics.  I see very well either OLSR's
HELLO, or periodic RREP, or ND's RAs used for proactive needs.

> Generally speaking, just because two classifications are not 
> mathematically contradictory, does not make them useless -- right??

Right.  They are useful so we can characterize behaviours.  But this
classification shouldn't entrench one into thinking a certain protocol
can't be both proactive and reactive (some times so other times so).

> We use blue and green to describe things as needed, and no one 
> complains based on the existence of turquoise or aqua.  If you would 
> rephrase your point to instead say that we should avoid being 
> constrained by the way we have classified things in the past, I would
>  very much agree with you.

I agree, I will rephrase my point to say a protocol can be acqua some
times blue other times green.

Alex

---

From: "Dearlove, Christopher \(UK\)" <[email-masked]>
Date: Mon, 11 Jun 2007 11:07:37 +0100

> so that we do not impede progress towards achieving our

Definitely agree with both parts of this.

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 11 Jun 2007 12:13:21 +0200

Krishna Sankar (ksankar) wrote:
> <KS> Are you talking about spatial interpolation based on history ? 
> Mobility algorithmics based on 1st and 2nd order derivatives of 
> mobility vectors - For example if we know a node is moving, if we can
>  infer the acceleration and also the spatial topology, we could 
> possibly say where it could be and what the route could be knowing 
> the nodes in that vicinity ... </KS>

It sounds logic to use the expected future physical position as an
indicator of where the node is.

However, this line of thought is very daring and prone to deep
disappointments when tried in IP practice.  Because it misses the
all-important point that 'mobility' as when an object moves, or as when
we draw Brownian dots on paper, is very much different than 'mobility' 
as implemented in C on some computers.  This difference is easily 
illustrated by the speed paradox of a vehicle moving very fast (130kmph) 
but whose IP address changes very slow (5 changes per hour).

Thus, if we define 'mobility' as the speed at which a node changes its
address then (1) we're out of MANET scope because in MANET nodes don't
dynamically change their addresses and (2) one realizes physical
location ("space") has no relationship whatsoever with an IP address,
and interpolating a set of physical coordinates can't result into an IP
address whatever trick one applies.

I think in order to be able to use the interpolation mathematical tool
in the MANET context one has to agree on how routes are represented at
intermediary nodes, and how they vary.  That agreement is difficult to
obtain, to start with.  Then I am almost sure route variation (routing
table changes) can not be expressed mathematically as function of
'space' co-ordinates.  Or if it were then it couldn't easily be grasped 
by a programmer's mind.

That's why I think space can not fit here.  But then people are of
course free to understand whatever they want by 'space' as people
understand whatever they want by 'color'.

Alex

> 
> Cheers <k/>
>> -----Original Message----- From: Philippe Jacquet 
>> [mailto:[email-masked]] Sent: Friday, June 08, 2007 4:12
>>  AM To: David Murray Cc: [email-masked] Subject: Re: [manet] DYMO 
>> and other routing protocols
>> 
>> This said, I don't think that on-demand and proactive approaches 
>> are represented at the same level in MANET. OLSRv2 has "space" 
>>  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.
>> 
>>> very low,
>> and there
>>> stationary 802.11 mesh devices and AODV/DYMO being used to 
>>> 2501
>> discusses MANET
>>> 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

---

From: "Dearlove, Christopher \(UK\)" <[email-masked]>
Date: Mon, 11 Jun 2007 11:27:24 +0100

> In MANET nodes don't dynamically change their addresses

Actually, in anticipation of possible needs for this in
some MANETs (using some possible autoconf mechanisms for
example) some support is included in NHDP - not mechanisms
for deciding on address changes, but "if you change your
address(es) for reasons outside the scope of NHDP then do
this" and some parts of HELLO processing that may look like
"why check that?" but are there to avoid badly behaving
neighbours creating inconsistencies in your information
repository. Of course in the former case if you don't ever
change your addresses, you don't need to ever do anything
about it.

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 11 Jun 2007 12:38:18 +0200

Dearlove, Christopher (UK) wrote:
> this"

Hi Christophe, I'm wondering whether NHDP should recommend the use 
Mobile IP when MANET nodes change their addresses (in addition to 
recommending sending new HELLO messages).

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 11 Jun 2007 12:46:19 +0200

Dearlove, Christopher (UK) wrote:
>> OLSRv2 document says it's proactive but I think an OLSRv2 
>> implementation must be able to obtain a route if it receives a app
>>  packet whose dst it doesn't know, and if it doesn't have a default
>>  route.
> 
> Not in that way.
> 

Maybe we have a misunderstanding.

I meant that an OLSR router, when it receives a packet from a host
permanently attached to that router, a packet that that OLSR router
should forward, packet whose dst address that OLSR router doesn't know -
the OLSR router should try to discover the route.

It's not a packet that the app on that OLSR router receives, and whose
dst that router doesn't know.

>  information about a neighbour it's never heard of, it doesn't have 
> to maintain its current fixed schedule to send a HELLO message 
> containing this extra information, but can do so early. This will 
> accelerate what you want here, and may even look reactive. But it's 
> more than just subtly different. A node that wants to find node X 
> can't make that happen, it has to wait for node X to inform it 
> (directly or, more usually, via other nodes).

I think I understand that in the MANET network the route propagation can
happen only with HELLOs advertised on link scope.

I also understand that very frequent HELLOs may in the end look as
routes are created immediately prior to an e2e application needing it.

However, as the efficiency of MANET networks should be taken into
account one deployer has to have the option of either rely on periodic
advertisements or immediate requested responses.  This is exactly as
periodic RAs and RS/RA, or as periodic RIP advertisements and Triggered RIP.

>>  at all times.
> times is not necessarily desirable. (Talk to 6LoWPAN people about 
> this, for example.)

I agree not desirable.

I wanted to mean that both tools should be in one spec (both the
periodic advertisements _and_ the immediately-answered directed
requests) and that deployers should be able to use whichever mechanism
independently or tuned for ege 6LowPAN.

Alex

---

From: "Dearlove, Christopher \(UK\)" <[email-masked]>
Date: Mon, 11 Jun 2007 11:53:44 +0100

> I'm wondering whether NHDP should recommend the use 

I think that's out of the scope of NHDP, which is
purely concerned not even with all of intra-MANET
communications, but a subset of that. That sort
of recommendation belongs in a higher level document,
one which actually knows why addresses change and
what the consequences are. NHDP is just responding
to a change, it's not its job to suggest what else
should be done. And maybe Mobile IP is the right
answer, or maybe not in some circumstances, NHDP
has no idea and building in a recommendation in
NHDP would be inappropriate.

---

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

> the OLSR router should try to discover the route.

No. That's a reactive approach. OLSR's approach is that destinations
are established proactively. If you don't know the destination then
either it's recently joined, and will make itself known soon, or it
isn't available, there's no point trying to find it, it isn't there.
If you get a packet with no destination, you should discard it. (Well,
actually you could queue it, but that's outside OLSR and is an IP
issue.)

> happen only with HELLOs advertised on link scope.

No, you also need TC messages in OLSR.

> independently or tuned for ege 6LowPAN.

That's not going to happen for the current protocols. OLSRv2 and
DYMO should be completed this year. That's the WP chartered work.
Producing a hybrid protocol is going back a step to experimental
work. See for example Charlie Perkins recent post where he's
interested in going forward with ideas in this area, but not to
delay the current work.

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 11 Jun 2007 14:06:24 +0200

Dearlove, Christopher (UK) wrote:
>>  permanently attached to that router, a packet that that OLSR
>> router should forward, packet whose dst address that OLSR router
>> doesn't know
> -
>  If you get a packet with no destination, you should discard it. 
> (Well, actually you could queue it, but that's outside OLSR and is an
>  IP issue.)
> 
>> I think I understand that in the MANET network the route 
>> propagation
> can

YEs, right... Topology Control messages...

>> requests) and that deployers should be able to use whichever 
>> mechanism independently or tuned for ege 6LowPAN.
> 
> That's not going to happen for the current protocols. OLSRv2 and DYMO
>  should be completed this year. That's the WP chartered work. 
> work.

Please explain why do you think a joint protocol deserves it
experimental status? On the contrary I think it can reflect consensus
reaching and thus qualify for Standards Track, better than two separate
protocols. No?

> See for example Charlie Perkins recent post where he's interested in 
> going forward with ideas in this area, but not to delay the current 
> work.

Yes, I've read it with interest. I agree with the point of not delaying
agreed timelines. Remark though, as already posted on the list, the
Charter has open the possiblity to converge:

Charter:
> Using mature components from previous work on experimental reactive and
> proactive protocols, the WG will develop two Standards track routing
> protocol specifications:
> 
> - Reactive MANET Protocol (RMP)
> - Proactive MANET Protocol (PMP)
> 
> If significant commonality between RMRP and PMRP protocol modules is
> observed, the WG may decide to go with a converged approach.

I think that if we continue pushing two different protocols up to WG
Last Call we implicitly agree that we have not found significant
commonality between the two protocols. The Charter implies so.

I personally think that two protocols right now is no different than
three protocols a few years ago.  Thus, experimental.

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 11 Jun 2007 14:21:38 +0200

Dearlove, Christopher (UK) wrote:
>> I'm wondering whether NHDP should recommend the use Mobile IP when 
>> MANET nodes change their addresses (in addition to recommending 
>> sending new HELLO messages).
> 
> I think that's out of the scope of NHDP, which is purely concerned 
> not even with all of intra-MANET communications, but a subset of 
> that. That sort of recommendation belongs in a higher level document,
>  one which actually knows why addresses change and what the 
> consequences are.

The consequences of a node changing its addresses affect _any_ protocol
behaviour I believe...

NHDP ignoring these consequences isn't quite ok IMHO.

It is not sufficient for NHDP and OLSR to just state that when a node is
changing its addresses it should re-advertise HELLOs.  This will simply
not work at least because of multicast joining.

In MANET, route-advertised messages are multicasted to multicast groups.
  I believe this is the case for NHDP/OLSR's TC and HELLO.  A MANET node
wishing to receive these multicast messages should join the respective
group (although the current OLSR/NHDP specs aren't yet recommending the
join if I understand correctly).  When a node joins a multicast group it
offers its IP address.  When that IP address changes the node is no
longer receiving the multicast messages.

With this in mind, I was thinking a possible suggestion is that either
NHDP/OLSR specify that nodes don't change their addresses, or specify
that if address change occurs (with AUTOCONF mechanism) then the
multicast group effects and session interruption exist.  Or similar...

> NHDP is just responding to a change, it's not its job to suggest what
> else should be done. And maybe Mobile IP is the right answer, or
> maybe not in some circumstances, NHDP has no idea and building in a
> recommendation in NHDP would be inappropriate.

Ok...

I think one main MANEMO effort is to look at what happens to a MANET 
protocol when the node changes its address.  I think it won't work.

Alex

---

From: "Templin, Fred L" <[email-masked]>
Date: Mon, 11 Jun 2007 09:15:30 -0700

> The consequences of a node changing its addresses affect 

Which addresses are you talking about? The ones assigned to
MANET interfaces, or the ones assigned to other interfaces?
The former may change while the latter remain stable, and
applications would ordinarily use the latter.

Fred
[email-masked]

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 11 Jun 2007 22:23:21 +0200

Templin, Fred L wrote:
>> The consequences of a node changing its addresses affect _any_
>> protocol behaviour I believe...
> 
> Which addresses are you talking about? The ones assigned to MANET
> interfaces, or the ones assigned to other interfaces? The former may
> change while the latter remain stable, and applications would
> ordinarily use the latter.

Not sure what you mean... you seem to say that some addresses may change 
without breaking anything in the MANET protocol, if I understand you 
correctly.

I mean when an address assigned to a MANET interface is changing - this 
will break the MANET protocol itself (not only the apps), would you agree?

Alex

---

From: "Ian Chakeres" <[email-masked]>
Date: Tue, 12 Jun 2007 09:20:47 +0530

Regarding the convergence within MANET, we have made significant
progress in a converged approach.

Here are some of the big examples of this fact - IANA, PacketBB, NHDP,
and common TLVs.

Regarding a merge between DYMO and OLSRv2, there is no straightforward
way to merge distance vector and link state routing information.

On a more positive note, I have indicated that I think it is possible
to make DYMO/OLSRv2 more proactive/reactive. I agree with John Mullen
that standardizing this advanced behavior should be done once we have
standard protocols complete.

Ian

<snip>
> reaching and thus qualify for Standards Track, better than two separate
<snip>

---

From: Alexandru Petrescu <[email-masked]>
Date: Tue, 12 Jun 2007 09:24:45 +0200

Ian Chakeres wrote:
> Here are some of the big examples of this fact - IANA, PacketBB,
> NHDP, and common TLVs.

Ok.

> Regarding a merge between DYMO and OLSRv2, there is no
> straightforward way to merge distance vector and link state routing
> information.

Indeed, sending routing information about immediate neighbors to all
network members (link-state) is different than sending routing
information to immediate neighbors about all network members (dv).

For my clarification, isn't the IANA-reserved LL multicast address a
link-local address?  If both protocols send messages to this address
then they both send to immediate neighbors then one can't be
link-state... right?

I'm afraid this ls-dv may be another entrenching classification.

>  to make DYMO/OLSRv2 more proactive/reactive. I agree with John
> Mullen that standardizing this advanced behavior should be done once
> we have standard protocols complete.

Ok.

Alex

---

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

---

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

> link-local address? 

Yes.

> If both protocols send messages to this address

No.

Take a simpler case, the most basic DV protocol. Each node
sends messages listing all the nodes it knows about and
the distance to each. It sends that to its immediate neighbours
whenever it changes. It updates its distances when it gets
such a message. Definitely distance vector, and definitely
using sending to immediate neighbours (which could use a
link local multicast address).

(Also definitely not good enough once things change. But
that's beside the current point.)

---

From: Alexandru Petrescu <[email-masked]>
Date: Tue, 12 Jun 2007 13:43:16 +0200

> link local multicast address).

Ok... but in this sense the LS protocol should send the info about its 
neighbors state to all routers in the MANET network (and not only to 
immediate neighbors) - right?

Alex

---

From: "Herbert Rubens" <[email-masked]>
Date: Tue, 12 Jun 2007 08:54:00 -0400

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: "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.)

---

From: "Mullen, John" <[email-masked]>
Date: Tue, 12 Jun 2007 09:37:53 -0600

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.
(505) 646-2958
[email-masked]
 
-----Original Message-----
From: Herbert Rubens [mailto:[email-masked]] 
Sent: Tuesday, June 12, 2007 6:54 AM
To: 'Philippe Jacquet'; 'Charles E. Perkins'
Cc: [email-masked]; [email-masked]
Subject: RE: [manet] DYMO and other routing protocols

Philippe,

-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: 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

---

From: David Young <[email-masked]>
Date: Tue, 12 Jun 2007 11:54:56 -0500

On Tue, Jun 12, 2007 at 08:54:00AM -0400, Herbert Rubens wrote:
> 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

---

From: Philippe Jacquet <[email-masked]>
Date: Tue, 12 Jun 2007 19:15:04 +0200

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

---

From: "Mullen, John" <[email-masked]>
Date: Tue, 12 Jun 2007 12:30:54 -0600

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.
(505) 646-2958
[email-masked]
 
-----Original Message-----
From: Philippe Jacquet [mailto:[email-masked]] 
Sent: Tuesday, June 12, 2007 11:15 AM
To: Mullen, John
Cc: [email-masked]
Subject: Re: [manet] DYMO and other routing protocols

Philippe

---

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]
>> technically can't be routing reliably without a flood 
>propagating the 
>> entire network.
>
>entire network following a change of linkstate.  You do need 
>to flood the region a few hops in diameter where most loops 
>occur.  See

---

From: "Joe Macker" <[email-masked]>
Date: Tue, 12 Jun 2007 15:53:48 -0400

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
>From: Mullen, John [mailto:[email-masked]] 
>Sent: Tuesday, June 12, 2007 2:31 PM
>To: [email-masked]
>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.
>(505) 646-2958
>[email-masked]
> 
>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,
>> 
>> 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.
>> (505) 646-2958
>> [email-masked]
>>  
>> 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
>> back to the node that sent it the packet. Until that node 
>receives an 
>> update you will have a loop in the network.
>> 
>> 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
>> 
>> 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):
>> 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.
>> 
>>> 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.
>>>
>>> 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.
>>>
>>>
>protocols 
>approaches are 
>>>> topology variety, including for instance the MPR 
>mechanism. In DYMO 
>>>> I don't see an equivalent "time" adaptibility that goes beyond the 
>necessarily 
>>>>> there are no power limitations, protocols like

---

From: "Mullen, John" <[email-masked]>
Date: Tue, 12 Jun 2007 14:46:54 -0600

Hi Joe,  

That's interesting. One approach I've seen is implicit ACKs. If A sends to B and then hears B retransmitting the update, A knows B got it. ACKs would only be needed in a few cases. For example, if B would not normally retransmit the update or if A specifically requested an ACK. 

Did the analysis consider that mechanism as well?

John P. Mullen, Ph.D.
(505) 646-2958
[email-masked]
 
-----Original Message-----
From: Joe Macker [mailto:[email-masked]] 
Sent: Tuesday, June 12, 2007 1:54 PM
To: Mullen, John; [email-masked]
Subject: RE: [manet] DYMO and other routing protocols

Some 2 cents.

<snip>

-Joe

---

From: "Krishna Sankar \(ksankar\)" <[email-masked]>
Date: Wed, 13 Jun 2007 08:26:10 -0700

Yep, the fisheye mechanisms are well suited for this domain. I think this is the option in 802.11s as well. I haven't gone thru the latest draft in detail, but am pretty sure. BTW, has there been any studies on DYMO for 802.11s ? 

Cheers
<k/>  

> Sent: Tuesday, June 12, 2007 10:15 AM
> To: Mullen, John
> Cc: [email-masked]
> 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
> 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. 
> > 
> 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.
> > 
> 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 
> 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.
> > 
> 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.  
> > 
> 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. 
> > 
> 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 
> > database is not loop free until an update is received by 
> all of the nodes in the network.
> > with lower power. Node C is on the path between a node A 
> and a node B. 
> us, SMURF) 
> enables nodes

---

From: "Joe Macker" <[email-masked]>
Date: Thu, 14 Jun 2007 16:05:59 -0400

This was discussed so you could search the archive to see more.
I was going to raise the CDS issue but this was made in a previous 2003
thread.

----snippet-----------
RFC 2328 also allows implicit ACKs, so this also would not require an
extension. But there is still the question of whether implicit ACKs
should be used on manet interfaces. It probably wouldn't hurt,
but it wouldn't help much either, since only a small percentage of
nodes will forward LSAs (e.g., CDS nodes or MPRs).

>Sent: Tuesday, June 12, 2007 4:47 PM
>To: [email-masked]
>That's interesting. One approach I've seen is implicit ACKs. 
>If A sends to B and then hears B retransmitting the update, A 
>knows B got it. ACKs would only be needed in a few cases. For 
>example, if B would not normally retransmit the update or if A 
>specifically requested an ACK. 
>
>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
>>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.
>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.
>>(505) 646-2958
>>[email-masked]
>> 
>links are 
>Gerla of 
>>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.
>>> 
>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.
>>> 
>>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.
>>> 
>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.
>>> 
>>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.
>>> 
>>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.
>>> 
>>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.
>>> 
>>information may not be current and have mechanisms to deal with that 
>>possibility.
>>> 
>>> John P. Mullen, Ph.D.
>>> (505) 646-2958
>>> [email-masked]
>>>

---

From: "Ian Chakeres" <[email-masked]>
Date: Thu, 21 Jun 2007 17:02:40 +0530

Everyone, I would like to solicit your opinion, either for or against
including sub-type. Please respond to the list.
==============

Justin, I think your metric dilemma is common to many other future TLV types.

Here are just a few examples off the top of my head:
location/position, name, security.

Based on this fact - I think including the sub-type would be useful.

I also like the fact that inclusion of sub-type is very
straightforward, does not impact existing work, and expands the tlv
space for a large number of future tlvs.

I look forward to seeing the metric document.
Ian

On 6/12/07, Justin Dean <[email-masked]> wrote:
> Manet-dt mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/manet-dt
>

---

From: Jerome Haerri <[email-masked]>
Date: Thu, 21 Jun 2007 14:12:41 +0200

Ian,

I am glad to hear that the debate on different metrics is now open !

As you probably know, I am a supporter of the inclusion of a sub-type 
field, as we proposed some times ago a common geo-localization signaling 
format based on TLVs and packetBB.

Indeed, we think that in order to enhance the capabilities of ad hoc 
networking protocols, new TLV types might be needed. Even though no 
protocol using potential new fields have been standardized yet, leaving 
space for extensions would be a measure that would guarantee the success 
of packetBB in more generalized applications than or specific extensions 
to OLSR, DYMO or SMF.

And as Justin said, TLVs which are concerned with 8 bits per TLV would 
not be forced to use this subfield and there would be no extra overhead 
involved. So, I personally do not see good reasons for not including an 
expanded TLV type field for packetBB.

By the way, we are also looking to seeing the metric document and we are 
offering our help in the definition and writing process of the new TLV 
metric document if needed.
According to this new document, we will also update our geo-localization 
draft to make it compliant with the expanded  field.

Jerome,
Fethi,
Christian

-- 
Jerome Haerri
Ph.D

Eurecom Institute
Mobile Communications Department
2229, Route des Cretes
B.P. 193
06904 Sophia-Antipolis Cedex
France

Office : +33 (0)4 93 00 81 76
Mob    : +33 (0)6 10 79 72 83

E-mail : [email-masked]

Web    : http://www.eurecom.fr/people/haerri.en.htm

---

From: "Joe Macker" <[email-masked]>
Date: Fri, 22 Jun 2007 14:06:27 -0400

One fan of including sub-type. 

>From: Ian Chakeres [mailto:[email-masked]] 
>Sent: Thursday, June 21, 2007 7:33 AM
>To: [email-masked]; Justin Dean
>Subject: Re: [Manet] Expanded tlv type field for packetbb?
>
>Everyone, I would like to solicit your opinion, either for or 
>against including sub-type. Please respond to the list.
>==============

---

From: "Charles E. Perkins" <[email-masked]>
Date: Fri, 22 Jun 2007 13:26:17 -0700

Hello folks,

As I understand it, some types could have a subtype
field, and other types would not have to make any
definition for a subtype.  So for the types that do not
define a subtype field, there would only be the
canonical TLV overhead.

Wouldn't it be better to have the type be the only
determinant of whether or not a subtype field exists?
Then we would not have to allocate another semantic
bit for the purpose of telling whether or not the
subtype field is present.

If no bit is allocated from the vector of semantics bits,
then I'd be in favor.  In fact, I'd even be in favor of
having the presence of the semantics bits depend
on the type field, so that some types do not need
the extra eight bits of overhead.

If, instead, it is felt this is too hard to parse
for subtype presence, I would instead suggest
defining a subtype-able range of types.  So, for
instance, maybe types 64-127 have subtypes and
types 1-63 do not.

Regards,
Charlie P.

---

From: "Dearlove, Christopher \(UK\)" <[email-masked]>
Date: Mon, 25 Jun 2007 09:34:58 +0100

> define a subtype field, there would only be the

There would be no overhead if you don't have a subtype.

> subtype field is present.

This I don't agree with. If you allocate a range of
types with and without subtypes, then the only difference
is whether you check a bit in the type (or something more
complicated) or a semantics bit. And the latter has
advantages of orthogonality and consistency with the rest
of how a TLV is laid out. Any other way of making type
define subtype I can't see working (how can an already
fielded device learn that IANA have made a new allocation?).

> the extra eight bits of overhead.

Again, not in favour. What's the default semantics for
a type without semantics? The reason there are these
options is to be more efficient. Or in other words the
semantics octet costs you one octet, and often saves
more. The most obvious illustration of this is something
like NHDP's LINK_STATUS. If a node gets into a stable
state, with all good links, then all LINK_STATUS values
will be SYMMETRIC. And excellent opportunity for a
no index, single value TLV with total length four octets.
But if you are in a highly dynamic network, with a mix
of LINK_STATUS values, that's a good opportunity for a
no index (until you have multiple interfaces) multivalue
TLV, with total length 3+N octets, where N is the number
of (current and recent) neighbours. If you decide to
fix on the latter type of TLV only, the former case will
cost you N-1 octets. If you decide to fix on the former
type of TLV only, you can't do it unless you have a
separate address block per LINK_STATUS value. And there
are other possibilities.

> instance, maybe types 64-127 have subtypes and

Commented on above.

---

From: "Teco_Boot" <[email-masked]>
Date: Mon, 25 Jun 2007 13:13:38 +0200

I prefer a protocol that supports extensions.
I prefer routing on metrics and not on hop-count.

But:
I think the subtype implementation needs to be analyzed. I would opt for an
flat number space with an extended format (bit indicating small and long
number format) and not for hierarchical numbering, this introduces a waste
of the number space as most types need only a few subtypes. And subtypes
could have to do with multiple main types also.

I also opt for an in-depth analysis for the metric type. Flooding lots of
metric types doesn't always help. I am working (mostly thinking) on a
Uniform Link Metric (ULM) / Uniform Path Metric (UPM), where a single cost
value would indicate the level of preference for the link / path. Such a
metric is composed on whatever metric type and UPMs can always be compared,
to select the shortest path. I do not say I reject the idea flooding metric
types, but I have a bad feeling reading:
>>>> can easily envision 10s if not 100s of metric types in the future.
How can we ever define a standard routing protocol handling all these
special cases? I think a router that has this information should incorporate
it in the ULM and signal this with UPM.
Signaling position information to neighbors could be useful, but in some
cases it is available for the upper layer and signaling it twice looks not
efficient to me.

Teco.

> Sent: donderdag 21 juni 2007 13:33

---

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 25 Jun 2007 14:41:19 -0700

Hello Christopher,

> fielded device learn that IANA have made a new allocation?).

 Do you mean to suggest that legacy operations depend on the setting
of a bit in the semantic bit vector?

What if the subtype were to follow the length byte, and thus be
counted along with the other type fields?  (Now I realize I did not
go back to check the formulation in the original email, sigh...)
 
> a type without semantics?

 Whether or not the semantic bit vector is a good idea, depends on
how many types we have, and how many of those types use both
settings of various bits.  I have not been quibbling about this, but
anyway it is worth keeping in mind.
 
>  The reason there are these

 I'll try to read NHDP soon, but one could imagine various solutions here,
perhaps involving different types or prepended bit vectors.
 
>> instance, maybe types 64-127 have subtypes and

 Other protocols manage to do this without
significant discomfort, so I reckon we could also.

To be clear, though, I am just trying to look at
alternatives.  I do not have strong requirements one
way or another about the eventual solution.

Regards,
Charlie P.

---

From: "Dearlove, Christopher \(UK\)" <[email-masked]>
Date: Tue, 26 Jun 2007 09:30:59 +0100

> of a bit in the semantic bit vector?

I'm not clear what you're suggesting I'm suggesting - which
probably means I'm not suggesting it.

I'm saying if we have subtypes which may or may not be included
as an octet, then within the natural structure of TLVs as defined
in packetbb, a semantics bit is the natural way to signal it. In
fact if you look back at the origins of packetbb we started with
ranges of types with certain properties, but the number of
options (not all suggested by us) increased to where that wasn't
working, and hence the current semantics octet was born. I don't
see any good reason to go back. (I will agree that no solution
here is ideal.)

> counted along with the other type fields?

I don't see that as important. I agree that if subtype were
signalled by a type bit then I'd naturally put it straight
after the type, if it's signalled by a semantics bit it
goes after that. But I don't see that as significant.
 
> anyway it is worth keeping in mind.

I believe we are well past worth keeping in mind, with
the implication we may change it later, time. I, and
many other people, are not interested in a later, we
need to get this finished.

> perhaps involving different types or prepended bit vectors.

Of course there are other solutions. But this is one, and
absent a serious objection - which there has been over a
year to lodge - a redesign is not called for and we don't
have the time for.

> way or another about the eventual solution.

I'm not interested in an eventual solution, I'm interested
in a solution now - in fact now is already considerably
later than it should be.