Subject: [Roll] A couple of thoughts on draft-ietf-roll-protocols-survey-00

From: Thomas Heide Clausen <[email-masked]>
Date: Wed, 17 Sep 2008 16:40:29 +0200

Dear all,

I may be late to the party, but I have read draft-ietf-roll-protocols-
survey-00, and want to share my thoughts on that document (which,
credit to the authors, is a well written and easy to read document).

First, I am not quite sure that it is clearly justified from where
the different "suitability metrics", over which protocols are
evaluated, are presented. I am aware of the various requirements
documents, however the simplified and simplistic view of "suitability
metrics" as presented seem somewhat of a leap from those. This may be
due to the survey and the requirements documents being in an early
phase of development, and so I shall retain detailed comments on this
matter until a later point in time.

Second, with respect to the "Control Cost" suitability metric, I
would respectfully question their validity since they are observing
events at one given point in time, rather than over time - i.e. does
not take any requirements for recurring transmissions into account. A
"protocol operation"  on the network with a complexity of O(N^2)
might, on the face value, appear less preferential than one which has
a complexity of O(N). However (taking an extreme example) in the
event where the former O(N^2) operation occurs once every week and
the latter O(N) once every microsecond, the O(N^2) operation could be
largely preferential.

On a similar token and considering that the ROLL working group is
interested in complexity with respect to the number of destinations,
a protocol might (taking a sought example again) exhibit a
complexity of O(k*D) whereas another a complexity of O(i*N).  On the
face value, the O(k*D) option might appear preferential, however as D
approaches N the relative value of k and i of course become
important. This has long been a favorite subject of study in the
MANET community, where this presents one of the differences between
e.g. AODV and OLSR. Note that, however, there's also a difference
between considering "number of destinations" and "number of
communicating pairs", which is interesting to observe.

Third, the suitability metrics disregard, at least in part, both
temporary storage requirements necessary for the algorithms to
operate, as well as the penalty incurring from suboptimal routes
(e.g. the energy consumption penalty of transiting data over a longer-
than-shortest-path). Evaluating table-size alone is insufficient. (I  
may get
back to this specific point in a subsequent email later.)

I want to share a single observation regarding the evaluation
of OLSR, which is the protocol among those surveyed with which I am
most familiar. I will, for brevity, in this email address the
observation that OLSR is recorded as "fail" with respect to the
survey metric "Control"; I may in following emails address the remaining
suitability metrics, which I believe are similarly inappropriately  
applied.  I note
that the evaluation in the I-D is considering only the ROLL  
suitability metrics,
and that the evaluation is considering only the "stock" deployment, and
specifically not a deployment with additional "design consideration  
necessary".

Let me thus address the temporal aspect, i.e. that which has to do
with the "Control Cost" suitability metric when considering not only
the cost of one protocol operation, but the cost of protocol
operations over the lifetime of a network. In OLSR (RFC3626, OLSRv2
both), TC messages are diffused globally and periodically, using MPR
flooding. In both, however, there are provisioning for modulating the
period time - i.e. to increase or decrease the periodicity as
appropriate for the network in operation. A "design consideration
necessary" that would need to be specified for a given deployment
would thus when observing "local stability" (in OLSRv2-terms: when
the MPR selector set of a router is stable) increase the interval
between TC message emissions. In case of "local instability (in
OLSRv2 terms: when the MPR selector set of a router experiences
changes), a TC message MAY be generated and/or the interval between
TC messages modulated. While the exact heuristics by which this
modulation is performed is not specified, performing this modulation
requires no changes to the protocol, since the mechanism for
modulating these intervals exists.

Since I have started using extreme examples let me continue: in a
stable network, a reasonable heuristic would after an initialization
phase set a 45-day interval between successive TC message emissions.

Hence, my reflection on the simple O(...) notation as evaluation
metric for the "Control Cost"  as being insufficient or inappropriate.

I am not convinced that the conclusion drawn by the protocol survey
I-D -- which seems to be that all routing protocols in existence are
severely broken -- is justified.

Sincerely,

Thomas

_______________________________________________
Roll mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/roll

---

From: "Stephen Dawson-Haggerty" <[email-masked]>
Date: Wed, 17 Sep 2008 18:30:32 -0700

It seems in the current version, "control cost" is the setup cost and
assumed to be recurring.  There is also "loss response"; all of the
triggered temporal components of traffic would fit into that bin, provided
that you can, as you suggest, turn down the global flood frequency so as to
be basically negligible.  However, we don't have a way to pass something
that sends large updates extremely infrequently; I believe that that were a
protocol to emerge which had a setup phase followed only by triggered
updates, it __would__ have to pass the control traffic criteria (loss
response might be another story).

It's also true, we never say that protocols need to converge to optimal
routes; this seems unnecessary to me since people seem unlikely to develop
protocols that do not converge to good routes under some metric; as long as
that metric is clear it would be fine with me.

Also, I would disagree that we conclude that all protocols are "severely
broken"; I actually think that a number of them could be made to work
without all that much trouble...  apparently that doesn't come out in the
draft, though.  I think having a discussion about whether or not OLSR (or
any other protocol) will work in this space will be very interesting and
seems to be the point you are driving at; after all that is the question we
are trying to answer.  This draft is mostly a guide for this debate.

As always, we appreciate the comments.
Steve

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Thu, 18 Sep 2008 09:35:03 +0100

Stephen Dawson-Haggerty
> It's also true, we never say that protocols need to converge to
optimal routes; 
> this seems unnecessary to me since people seem unlikely to develop
protocols 
> that do not converge to good routes under some metric; as long as that
metric 
> is clear it would be fine with me.

That doesn't have to be the case. A protocol could
set up a route, even according to some good criterion,
but then, in order to minimise signalling, maintain
that route in the face of mobility by patching it
locally. That won't optimise any particular metric
of the route. Over time, the route could become quite
sub-optimal. (Separate route establishment and route
maintenance is done by more than one protocol. How
good routes they maintain, I don't know for certain.)

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