Subject: [Roll] Fwd: P2P performance with current RPL proposal

From: Mukul Goyal <[email-masked]>
Date: Mon, 15 Mar 2010 20:56:20 -0500 (CDT)

Hi Pascal

I may not have been clear enough in expressing the scalability concern I have. I was saying that
we can not have "source-destination pair" specific route states in the intermediate nodes. It would simply be unscalable. The approach you described in your slides seemed to suggest that nodes maintain "source-destination pair" specific route states (nodes maintain state for DAG "R,i" with target "T"). Please let me know if this is not the case.

The simple/regular distance vector approach I was referring to means storing "destination(s)" specific routing states (i.e. the cost to reach a particular destination(or destinations)) in the nodes so that all the sources going to the same "destination" can benefit from this state in both routing as well as route discovery (so, no need to flood the RREQ/DIO further if I already know the cost to reach this destination). 

So, the scheme you proposed would work if we can have a source (or multiple sources) build a DAG towards the destination (or destinations) so that the DAG ranks/cost maintained by the nodes are with respect to the destination(s) rather than the root(s)/source(s). So, when another node needs to reach this destination, it can simply join this DAG.

I hope I am clear enough this time.

Thanks
Mukul
    
----- Original Message -----
From: "Pascal Thubert (pthubert)" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: "ROLL WG" <[email-masked]>, "robert cragie" <[email-masked]>, "Ted Humpal" <[email-masked]>
Sent: Monday, March 15, 2010 1:04:51 PM GMT -06:00 US/Canada Central
Subject: RE: [Roll] P2P performance with current RPL proposal

Hi Mukul

> 1. A node/router in the middle may need to maintain state for multiple DAGs
> that lead to the same destination. Consider the situation where 5 nearby
> nodes need to find route to the same destination D. As per your scheme,
> each node would form its own DAG towards the destination D and the nodes
> in the middle would need to maintain state about all 5 DAGs. This seems
> wasteful. You may argue that this is a fit case for these 5 nodes to belong to a
> single DAG rooted at D. But the problem is that D does not know that it is a
> destination for these 5 nodes. So, in general, I see a scalability problem
> associated with the use of DAGs for P2P routing. A simple DV approach,
> where the nodes maintain information about destinations (rather than
> DAGs), seems to avoid this scalability problem.

[Pascal] I do not know what you call regular :) 
RIP usually maintains trees but eigrp allows for non-equal cost feasible successors and thus builds DAGs.

AODV (Thomas, or Charlie if you're listening, correct me if I'm wrong) builds and maintains routes that are dotted lines between 2 points.

With RPL used reactively as proposed here, we can do either way. 

The OF can be designed to build a tree and if so, we end up with something quite similar to AODV/DYMO.
Or the OF wants a DAD for redundancy and we build a DAG.

One cool thing is that we can request more than one target, effectively building a DAG that looks like a flower.

It's not a matter of scalability, it's a matter of what you cant to achieve and the associated cost. DAG is more expensive than tree.

> 
> 2. So, in your scheme, the nodes timeout the state they have for a DAG. This
> means that a node that does not belong to the actual route taken by the
> packets would end up timing out its state for this DAG. This is ok unless this
> node is part of an obvious backup route and should have maintained
> information about this DAG. It would be good to use the "routing interest"
> concept in this situation. As per this concept, each node maintains a "routing
> interest" in a particular DAG (or destination). The routing interest is a metric
> between 0 and 1. If a node is actively sending packets along the DAG, its
> routing interest would be 1. Otherwise, the routing interest would be
> x*max(routing interest of its nbrs), where x is a fraction. A node may delete
> state about a DAG/destination if its routing interest in that dag/destination
> drops below a threshold. The routing interest concept would allow nodes
> "around' the actual path to maintain state about this dag while other nodes
> can delete this state after initial route discovery.
[Pascal] 

Cool : ) Now we're building a solution.

Pascal 

> 
> Thanks
> Mukul
> ----- Original Message -----
> From: "Pascal Thubert (pthubert)" <[email-masked]>
> To: "robert cragie" <[email-masked]>, "Ted Humpal"
> <[email-masked]>
> Cc: "ROLL WG" <[email-masked]>
> Sent: Monday, March 15, 2010 11:24:01 AM GMT -06:00 US/Canada Central
> Subject: Re: [Roll] P2P performance with current RPL proposal
> 
> 
> 
> 
> 
> HI Robert :
> 
> 
> 
> I respectfully have to disagree.
> 
> 
> 
> My understanding is that we are considering a limited set of P2P pairs, for
> which the specific path that we need to create might have to obey specific
> constraints.
> 
> So it makes sense to use an on-demand technique, probably inspired by the
> MANET Reactive protocols.
> 
> 
> 
> As it goes, those protocols usually use flooding for a node to locate another.
> Forking a DAG is just another flooding. It does not take a lot of addition to the
> existing DIO for a root to use RPL to build a DAG that contains one or multiple
> Targets as leaves, under a set of constraints expressed as an objective
> function. Please find attached a slideware that illustrates that.
> 
> 
> 
> 
> Pascal
> 
> 
> 
> 
> 
> 
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Robert Cragie
> Sent: Thursday, March 11, 2010 2:43 PM
> To: [email-masked]
> Cc: ROLL WG
> Subject: Re: [Roll] P2P performance with current RPL proposal
> 
> 
> 
> I agree with Ted's comments below. Creating a DODAG for every reachable
> node as a root seems a very inefficient approach compared to alternative
> routing algorithms. I am concerned that RPL does not actually meet the
> original requirements in I-D.ietf-roll-building-routing-reqs, I-D.ietf-roll-home-
> routing-reqs, RFC5673 and RFC5548. The traffic pattern requirement for a
> sink node features prominently in only two of those documents. Even in this
> case, as Ted points out, communication is likely to be bidirectional (e.g. end-
> to-end acks.) therefore the DODAG approach is fundamentally asymmetric,
> especially if no intermediate storage is allowed for destination routes and
> source routing has to be used.
> 
> Also, RPL seems highly complex for what are constrained nodes in terms of
> memory as well as power and bandwidth. The RPL draft as it stands is 82
> pages long and that doesn't include text about the objective function.
> 
> Robert
> 
> 
> Robert Cragie (Pacific Gas & Electric)
> 
> Gridmerge Ltd.
> 89 Greenfield Crescent,
> Wakefield, WF4 4WA, UK
> +44 (0) 1924 910888
> http://www.gridmerge.com
> 
> 
> 
> [email-masked] wrote:
> 
> 
> A concern also will be how much overhead (memory space) will be required
> for a DODAG Root?
> 
> and based on the first question how many DODAG roots a lamp may need to
> be a member of?
> 
> For example in lighting  a single lamp may be a root for a single switch (1
> DODAG root),  this lamp / luminaire may also
> be a member of another group - -  which could be all lights on the floor (2nd
> DODAG root), and a third group
> of all the lights in the building.  There can be many more speciality groups
> associated based on the building configuration.
> Consider also during the installation time - how these DODAG roots will be
> configured?  Must I commission each device
> to tell it which DODAG it must use for its Object Function?  How easy will this
> be to change and add in a new DODAG root
> for the end user if the lighting group changes??
> 
> With respect to Jerry Martocci's - commercial building requirements - every
> device may need to communicate to any or
> all of the end devices.  If each device must establish a DODAG for the other
> 499 devices in a 500 node network - How much memory
> space will this require for each end device to maintain?
> 
> Keep in mind that the end devices are very limited processor and memory
> wise.
> 
> Not to mention all of the network maintenance messages that would need
> to be transmitted to maintain all of these DODAGs.
> 
> Consider the reconvergence time when one device is turned off and it was in
> the middle of the majority of the 100+ DODAGS?
> 
> In many lighting and building application an application acknowledgement -
> must be returned {Back down the DODAG} so . . . the
> requirement is not just getting to the Root - a return path must also be
> maintained and have a  low latency path.
> 
> Ted Humpal
> 
> 
> 
> 
> 
> From:
> 
> Kris Pister <[email-masked]>
> 
> 
> To:
> 
> Anders Brandt <[email-masked]>
> 
> 
> Cc:
> 
> ROLL WG <[email-masked]>
> 
> 
> Date:
> 
> 03/08/2010 01:45 PM
> 
> 
> Subject:
> 
> Re: [Roll] P2P performance with current RPL proposal
> 
> 
> 
> 
> 
> 
> 
> 
> Anders - if we take JP's suggestion to make The Lamp a DODAG root, and
> take Phoebus' recommendation that we use path diversity to improve end-
> to-end reliability, do you see a chance of success?
> In my experience, with diverse paths and order-minutes updates you get
> extremely high reliability.
> 
> I have no aversion to TTL-limited floods as a part of a solution either.  I'm
> open to ideas on how to bring those in as (presumably infrequently used)
> options.
> 
> ksjp
> 
> Anders Brandt wrote:
> Hello
> 
> I would like to probe the temperature of the WG on using DAOs to
> support P2P.
> 
> The building and home application spaces (and maybe others) have
> a few clearly defined requirements.
> It is not obvious to me how the current RPL proposal (cRPLp) can
> satisfy those requirements:
> 
> 
> In both cases it is the worst case scenario that hurts:
> 
> 
> P2P routing inside the PAN
> ==========================
> cRPLp has no way of routing inside the PAN if you need more than
> one repeater. cRPLp has to go all the way to the top (maybe 4 hops up)
> and down again (maybe 4 hops down) to get just 2 hops to the side.
> 
> The consequence is high latency and high levels of background noise
> for nodes just outside the direct radio range.
> At the same time the risk of meeting a failing link is 4 times higher =>
> latency may be much more than 4 times larger.
> 
> Latency may sound like a minor issue but it actually translates directly
> into lower battery lifetime. In the above (very realistic) example,
> the battery lifetime is reduced to 25% of what it should be.
> 
> We have lots of battery devices sending into the network:
> * PIR sensors turning on lights
> * Door locks sending alarms
> * Door/window sensors starting chimes
> * Smoke sensors triggering an alarm system
> 
> 
> 
> 
> Response time
> =============
> The latency issue is important.
> When a user (real human being) presses a light button the user expects
> the light to turn on.
> cRPLp proposes that nodes in the tree periodically advertises their
> presence using DAOs.
> The periodicity is a real beast:
> Thanks to Trickle, the rate of updates in a (apparently) stable network
> is low. This is good since it leaves bandwidth for data.
> But it is not good if existing routes to my lamp fail and I do not get
> new routes to my lamp until it decides to send out a new DAO.
> My user will (with a good reason) not tolerate waiting for minutes for
> the light to turn on.
> 
> I have met two arguments to counter this concern:
> 
> A1: Well, your lamp can always send a DAO when it detects a problem.
>   My answer:
>   True, except that my lamp does not intend to send anything
>   so it will never experience any problems from its side of the network.
> 
> A2: Well, you can increase the DAO rate to sub-second updates.
>   My answer:
>   Oh no. I get a very high degree of management traffic which
>   limits my available bandwidth, increases the risk of collisions and
>   even run the risk of violating EU legislation requiring me to only
>   transmit in less than 1% of the time:
>   http://focus.ti.com/lit/an/swra048/swra048.pdf
>  868 - 868.6 MHz: <1%
> 
>   Reactiveness is hard to achieve via polling.
> 
> 
> 
> If you agree that this seems to be critical issues please raise your
> voice on the list.
> 
> Going forward
> =============
> 
> We need some reactive mechanism to reach lamps before the user decides
> to sue our companies.
> So is this possible? I think so.
> 
> Existing commercial (non-IP) solutions are capable of re-routing quickly
> if they really have to.
> 
> Let me try scoping the requirements to a potential solution:
> (no different from the req. docs for home and building)
> 
> * P2P routing in any direction independent of the tree.
> 
> * On-demand P2P route discovery if requested by a real-time critical app.
>  Data collection apps may be able to just wait for the next DAO update.
> 
> * Limited range of discovery mechanism: max 4 repeaters.
>   A TTL field may limit the scope of the repeaters.
> 
> * Suboptimal routing and traffic bursts are accepted in exchange
>   for quick route repair. But only as an exception.
> 
> 
> Just as an example, one existing home control technology uses a
> (source routing) variant of AODV for quick route repair.
> Nothing comes for free. The price is flooding - but not just flooding:
> Managed flooding using a distributed algorithm running in all
> participating nodes.
> The algorithm dampens the flooding in a time, volume and range
> perspective.
> Some similar mechanism could be built into RPL for quick route repair.
> 
> 
> If anyone have alternative proposals, please bring it to the list.
> Now is the time.
> 
> 
> 
> Thanks,
>   Anders
> 
> 
> 
> 
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll
>   _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll
> 
> 
> 
> 
>   _______________________________________________ Roll mailing
> list [email-masked] https://www.ietf.org/mailman/listinfo/roll
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: "Anders Brandt" <[email-masked]>
Date: Wed, 17 Mar 2010 17:56:35 +0100

Pascal,
 
> Cool : ) Now we're building a solution.
 
Are we?
OK - I guess I need some readers guidance here...
 
In some previous mail I saw you mention that the DAG mechanisms could be made reactive.
Could you explain in a few words how this can be achieved?
 
Even if so, I fail to see how this meets the other goals pinpointed multiple times by Jerry, me and others:
 
Just re-iterating, my world (also) consists of 
 
* Battery powered
 
devices having to send
 
* P2P traffic to a subset of network nodes or all nodes
 
with
 
* close to optimal routing
 
to keep battery consumption low and a need for
 
* soft real-time route repair (less than 4 seconds with a limit of four repeaters)
 
to provide a reasonable user experience when turning on light.
 
Are we getting closer to these objectives?
 
Thanks,
  Anders

________________________________

Fra: [email-masked] på vegne af Mukul Goyal
Sendt: ti 16-03-2010 02:56
Til: roll
Emne: [Roll] Fwd: P2P performance with current RPL proposal

Hi Pascal

Thanks
Mukul
   
----- Original Message -----
From: "Pascal Thubert (pthubert)" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: "ROLL WG" <[email-masked]>, "robert cragie" <[email-masked]>, "Ted Humpal" <[email-masked]>
Sent: Monday, March 15, 2010 1:04:51 PM GMT -06:00 US/Canada Central
Subject: RE: [Roll] P2P performance with current RPL proposal

Hi Mukul

[Pascal]

Pascal

> http://www.gridmerge.com <http://www.gridmerge.com/> 
>
>
>