Subject: [Roll] Moving forward with the protocol work

From: M Anand <[email-masked]>
Date: Thu, 30 Jul 2009 19:00:50 -0400

I would support adoption of draft-dt-roll-rpl-01  as a WG document based on
the reasoning below.

The one area of (I think quite valid) concern appears to be optimal P2P
routing or lack thereof. I would make the following points with regard to
this:

1. I think first there seems to be some misinterpretation because I see
references to nodes within direct physical range, light switch/light etc. in
the discussion.
RPL as it stands would let a node in direct contact with another route
directly to that node. No need to go up and down a DAG. I think this was in
one of the examples in the slide presentation in the mtg. and, if I recall
correctly, someone explcitly asked this question.

2. So, we are not talking about P2P route sub-optimality in RPL when there
is a one-hop route. And I sure would hope that a light switch would be in
direct physical range of its light. We can leave aside these cases when
debating the possible P2P demerits of the present RPL.

3. The issue arises when there is a 2 or more edge shortest path between
nodes in the base connectivity graph, but that path does not contain a
parent common to the nodes in the induced DAG rooted at some node (LBR or
other) that RPL would produce. *Significant* differences in the length of
the path in the two cases, would really only arise when the base graph is
very sparsely connected *and* of large diameter. I would suspect, certainly
in the home, and in most cases in commercial buildings that the graphs are
not like that. I am tempted to go out on a limb and leave out the "suspect"
- it might be interesting to analyze a decent dataset of random graphs or
actual connectivity graphs in the application scenarios if someone can
produce them (oops...did I just volunteer for something ?)

4. If an application is interested in mutliple P2MP/MP2P rather than total
P2P, RPL can take us there as well.

5. The DAG (or tree) formation out of the original graph is intended to
simplify the routing problem and minimize state information. I would submit
that the spectrum of things one can do, in order of increasing state and
complexity would be:
a. Induce a tree and route along it  ----- suited for P2MP/MP2P
b. Induce a DAG and route along it   ----- same with more redundancy
c. Induce multiple DAGs              ----- multi - P2MP/MP2P
d. Route along base graph            ----- complete P2P

RPL sits at b & c and occupies the solid middle ground.

5. If d is the desire, a couple of points to note (this one and #6 below).
First, I think in that case there is a not a whole lot to do other than make
every node maintain and disseminate routing state for every other node.
Sure, we can play some tricks and prune some nodes that don't participate in
the interesting paths, but all this will come with a price - and when it is
paid the price will be steep - because intelligent decisions here will
require global information and not local information. And it may change with
time. Next thing we know, that one node that pruned itself out of the
picture with regard to a certain flow, is the *the* guy for an optimal path
five years later for a newly installed node and the alternative is vastly
longer. Everyone can *see* there is a 2-hop path and wonder why it takes 5
hops. The point is, without knowledge of whole topology these local
decisions can cause major trouble and defeat the original intent, which was
optimal P2P. I would suggest that the best and only thing to do if we want
to do d) is to go all the way and make sure the network can deal with the
large state information.

6. I can fully understand Jerry's "diatribe", as he called it in a recent
post. Rest assured Jerry, I, and I am sure many of us, have had occasion to
say similar things. But I think it illustrates a point. If our radios were
to do the equivalent of what the wire did for us, i.e., make every node
reach every other node and create a complete graph, from a routing
perspective RPL would be absolutely no worse than any P2P. If the radio did
only somewhat worse in providing connectivity, RPL may correspondingly also
do slightly worse. But. It would do vastly better for a several thousand
node network spread over a city.

7. And that I think summarizes the argument for moving forward with RPL -
not for stopping where it stands, just moving forward with it is a basis. It
is not going to be everything for everyone, but I think it is going be a
very large something for almost everyone, including home/bldg. control.

Best regards,
Anand.

On Thu, Jul 30, 2009 at 5:48 PM, M. B. Anand <[email-masked]> wrote:

>
>
> -------- Original Message --------
> Subject:        [Roll] Moving forward with the protocol work
> Date:   Tue, 28 Jul 2009 18:34:24 +0200
> From:   JP Vasseur <[email-masked]>
> To:     ROLL WG <[email-masked]>
>
>
>
> Dear WG,
>
> First of all, thanks for all the time and energy you all have devoted
>  during the past few weeks on the protocol work. There was excellent
>  followup discussion at the physical WG meeting.
>
> To the question "Do you think that RPL provides an adequate foundation  for
> the ROLL routing protocol work", there was clearly a good  consensus in the
> WG meeting. It was also recognized there are still  several open issues for
> which we WILL need help from many WG  contributors, including the authors of
> other documents.
>
> Could you please confirm (or not) the adoption of draft-dt-roll-rpl-01  as
> a WG document ?
>
> Then we will of course move to the next step.
>
> Thanks,
>
> JP and David
>
>
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll
>
>
>

---

From: JP Vasseur <[email-masked]>
Date: Fri, 31 Jul 2009 18:36:23 +0200

Hi Anand,

On Jul 31, 2009, at 1:00 AM, M Anand wrote:

> I would support adoption of draft-dt-roll-rpl-01  as a WG document  
> based on the reasoning below.
>
> The one area of (I think quite valid) concern appears to be optimal  
> P2P routing or lack thereof. I would make the following points with  
> regard to this:
>
> 1. I think first there seems to be some misinterpretation because I  
> see references to nodes within direct physical range, light switch/ 
> light etc. in the discussion.
> RPL as it stands would let a node in direct contact with another  
> route directly to that node. No need to go up and down a DAG. I  
> think this was in one of the examples in the slide presentation in  
> the mtg. and, if I recall correctly, someone explcitly asked this  
> question.
>

This is perfectly correct,

> 2. So, we are not talking about P2P route sub-optimality in RPL when  
> there is a one-hop route. And I sure would hope that a light switch  
> would be in direct physical range of its light. We can leave aside  
> these cases when debating the possible P2P demerits of the present  
> RPL.
>
> 3. The issue arises when there is a 2 or more edge shortest path  
> between nodes in the base connectivity graph, but that path does not  
> contain a parent common to the nodes in the induced DAG rooted at  
> some node (LBR or other) that RPL would produce. *Significant*  
> differences in the length of the path in the two cases, would really  
> only arise when the base graph is very sparsely connected *and* of  
> large diameter. I would suspect, certainly in the home, and in most  
> cases in commercial buildings that the graphs are not like that. I  
> am tempted to go out on a limb and leave out the "suspect" - it  
> might be interesting to analyze a decent dataset of random graphs or  
> actual connectivity graphs in the application scenarios if someone  
> can produce them (oops...did I just volunteer for something ?)
>

I think so .... and thanks ;-) You are perfectly correct in your  
analysis and we will need to do this analysis indeed to find out how  
much must be added/changed to address these cases. I also think that  
clarifications must be provided to make sure that there is no  
understanding. The DT did an outstanding job but I also understand  
that some part of the ID may lead to confusion, that must be clarified.

> 4. If an application is interested in mutliple P2MP/MP2P rather than  
> total P2P, RPL can take us there as well.
>

Correct.

> 5. The DAG (or tree) formation out of the original graph is intended  
> to simplify the routing problem and minimize state information. I  
> would submit that the spectrum of things one can do, in order of  
> increasing state and complexity would be:
> 5. If d is the desire, a couple of points to note (this one and #6  
> below). First, I think in that case there is a not a whole lot to do  
> other than make every node maintain and disseminate routing state  
> for every other node.

Yes, this is no "free lunch".

> Sure, we can play some tricks and prune some nodes that don't  
> participate in the interesting paths, but all this will come with a  
> price - and when it is paid the price will be steep - because  
> intelligent decisions here will require global information and not  
> local information. And it may change with time. Next thing we know,  
> that one node that pruned itself out of the picture with regard to a  
> certain flow, is the *the* guy for an optimal path five years later  
> for a newly installed node and the alternative is vastly longer.  
> Everyone can *see* there is a 2-hop path and wonder why it takes 5  
> decisions can cause major trouble and defeat the original intent,  
> which was optimal P2P. I would suggest that the best and only thing  
> to do if we want to do d) is to go all the way and make sure the  
> network can deal with the large state information.
>

Right, furthermore, there might be ways to optimize some flows between  
specific pairs of nodes, with specific constraints, for example using  
different DAGs. To be discussed ...

> 6. I can fully understand Jerry's "diatribe", as he called it in a  
> recent post. Rest assured Jerry, I, and I am sure many of us, have  
> had occasion to say similar things. But I think it illustrates a  
> point. If our radios were to do the equivalent of what the wire did  
> for us, i.e., make every node reach every other node and create a  
> complete graph, from a routing perspective RPL would be absolutely  
> no worse than any P2P. If the radio did only somewhat worse in  
> providing connectivity, RPL may correspondingly also do slightly  
> worse. But. It would do vastly better for a several thousand node  
> network spread over a city.
>
> 7. And that I think summarizes the argument for moving forward with  
> RPL - not for stopping where it stands, just moving forward with it  
> is a basis. It is not going to be everything for everyone, but I  
> think it is going be a very large something for almost everyone,  
> including home/bldg. control.
>

Thanks for the detailed feed-back.

JP.

> First of all, thanks for all the time and energy you all have  
> devoted  during the past few weeks on the protocol work. There was  
> excellent  followup discussion at the physical WG meeting.
>
> To the question "Do you think that RPL provides an adequate  
> foundation  for the ROLL routing protocol work", there was clearly a  
> good  consensus in the WG meeting. It was also recognized there are  
> still  several open issues for which we WILL need help from many WG   
> contributors, including the authors of other documents.
>
> Could you please confirm (or not) the adoption of draft-dt-roll- 
> rpl-01  as a WG document ?
>