Subject: [Roll] Comments on draft-levis-roll-protocols-survey-02

From: Tim Winter <[email-masked]>
Date: Mon, 11 Aug 2008 14:14:35 -0400

WG,

In reviewing the document I have come up with the following comments:

Overall I find that the approach taken is useful and constructive.  It 
certainly provides a solid starting point from which to debate the 
merits and drawbacks of various prtocols and their suitability to ROLL.

DSDV does not appear to be covered by any RFC or active draft.  I 
suggest that it should be removed from ths survey.

With regard to the Table Scalability criterion I think it should be more 
stringent.  The use case of LLNs behaving as data collection networks, 
with the bulk of traffic flow through routers to data collection points, 
is certainly a dominant one.  But there are other use cases, e.g. access 
points -> sensor/actuator, which may let the number of possible 
destinations D begin to approach N.  Should it be necessary to maintain 
such state at individual nodes, for large networks, it would be better 
for a protocol to provide routing table scaling with O(log(D)).  Such 
may be found, for example, in protocols which employ clustering or 
hierarchical strategies.

The Control Cost criterion makes a lot of sense when considering the 
energy constraints of nodes who are only battery powered and must 
conserve energy at all times.  However I think we should also consider 
that a (proactive) routing protocol may be able to take advantage of 
powered (i.e. not energy constrained) nodes that may be available in the 
network.  For example, a set of powered nodes who are able to 
communicate without regard to limited energy may be able to maintain a 
proactive routing state in order to service transient battery powered 
nodes, who may come and go and would not be expected to maintain any 
unused state.  None of the protocols under consideration appear to have 
such capabilities.

Some small items:
  
111     Energy is a fundamental challenge in these devices.  Convenience and
 >>>>>                                        ^^^^^ in many of these devices

112     ease of use requires they be wireless and therefore battery powered.
 >>>>>                                             ^^^^^^^^^ and in many 
cases

266     properties abd attributes such as power, memory, and battery life
 >>>>>              ^^^ and

274  4.  Routing Protocol Taxonomy

 >>>>>  Suggest to add heading `4.1.  Protocol Classes'

275     Routing protocols broadly fall into two classes: link-state and
276     distance-vector.
    
330     Protocols Today
 >>>>>   ^^^  Suggest to add heading `4.2. ...'

362     protocols.  Later sections consider the properties of these protocol
^s

586     messages, but TC messages spread topology information throughout the
587     network (using MPRs).  As such, control traffic is proportional to
588     O(N^2).  As L is bounded by N, this means control traffic is
 >>>>>            ^XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

589     proportional to O(N).  MPRs reduce this load to O(N^2 / L).  As the
 >>>>>   ^XXXXXXXXXXXXXXXXXXXX
 >>>>>   This sentence seems like it should be removed, the explanation 
is more
 >>>>>   clearly laid out below

590     number of MPRs is inversely proportional to the density of the
591     network and L is bounded by N, this means control traffic is at best
592     proportional to O(N), and fails the control cost metric.

Regards,

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

---

From: Philip Levis <[email-masked]>
Date: Mon, 11 Aug 2008 22:20:40 -0700

On Aug 11, 2008, at 11:14 AM, Tim Winter wrote:

> Overall I find that the approach taken is useful and constructive.   
> It certainly provides a solid starting point from which to debate  
> the merits and drawbacks of various prtocols and their suitability  
> to ROLL.
>

It is unique in this regard. We mostly put it in there because it is  
very much a key part of the MANET canon. If we didn't have it in, I'm  
sure someone would have said that we should. That being said, I'm not  
against holding hard and fast to the draft/RFC requirement. Does  
anyone else feel strongly about this?

>
>
> With regard to the Table Scalability criterion I think it should be  
> more stringent.  The use case of LLNs behaving as data collection  
> networks, with the bulk of traffic flow through routers to data  
> collection points, is certainly a dominant one.  But there are other  
> use cases, e.g. access points -> sensor/actuator, which may let the  
> number of possible destinations D begin to approach N.  Should it be  
> necessary to maintain such state at individual nodes, for large  
> networks, it would be better for a protocol to provide routing table  
> scaling with O(log(D)).  Such may be found, for example, in  
> protocols which employ clustering or hierarchical strategies.

Well, as soon as we go to sub-linear factors on D, then we're talking  
about routing stretch. Remember, the purpose here isn't to state the  
requirements of ROLL protocols -- the application drafts do that --  
but rather to lay out a set of minimal (perhaps even insufficient)  
requirements by which we can judge existing protocols. I'm a bit wary  
saying that any protocol which does not use hierarchical routing  
cannot satisfy ROLL needs.

> conserve energy at all times.  However I think we should also  
> consider that a (proactive) routing protocol may be able to take  
> advantage of powered (i.e. not energy constrained) nodes that may be  
> available in the network.  For example, a set of powered nodes who  
> are able to communicate without regard to limited energy may be able  
> to maintain a proactive routing state in order to service transient  
> battery powered nodes, who may come and go and would not be expected  
> to maintain any unused state.  None of the protocols under  
> consideration appear to have such capabilities.

Agreed. The point here, though, isn't that some nodes could maintain  
more than O(D) state, or have a higher control cost, rather that some  
node's can't. If a protocol requires them to have > O(D) RT state, or  
a higher control cost, than it cannot be used on these weaker nodes.  
To some degree, I think node cost encompasses much of what you're  
talking about, though.

Again, to reiterate, the criteria in this draft are *not* intended to  
be the principal ways in which we will evaluate ROLL protocols: those  
are the application requirements documents. This is just asking the  
question of whether existing protocols can meet our needs.

Phil