Subject: Re: [Roll] Fwd: I-D Action:draft-dt-roll-rpl-00.txt Q2..4

From: Alexandru Petrescu <[email-masked]>
Date: Wed, 01 Jul 2009 11:07:54 +0200

Pascal, as I wrote in private, I doubt the necessity of using the term
DAG and the associated DAG theory.  Picturing a DAG without arrows makes
doubtful sense (figure 1).  A link between siblings would use bidir
arrows, which would make for a 'loop', which we would try to avoid.

Besides, what would an arrow between two nodes mean actually: is it that
a node can send a packet to another node but not the other way around?
Makes little sense to have all edges so unidirectional.

Pascal Thubert (pthubert) a écrit :
[...]
> Q: Can siblings hear each other as it is not evident from Figure 2: 
> Example DAG?
> 
> R: Figure 1 represents connectivity and you can see siblings hearing
>  each other. Figure 2 represents the DAG so it does not include the 
> sibling links.

It should be clear whether or not the siblings can be linked together by
links and direct routes or not.  At some point  in the draft this is
explicitely forbidden (it says traffic from node a to node b deep in the
network must pass through the DAG root) - this is not good.

> Sibling links are bidirectional at the graph level though 
> unidirectional for a given packet.

I don't understand.  Do you mean that all links in the network (the DAG
is the network) are _uni_directional?

> We're missing the term to indicate the DAG+sibling_links.

We should call it a network.  A graph of paths hopefully loop-free, not
necessarily guaranteed.  But not a DAG.

> Gradient is fine when you talk about pointing to the preferred 
> parent, but this is also a term that was overloaded in the past. What
>  else?

A network.  A net.   A set of paths.  A topology and the associated 
paths.  A conceptual picture stemming from the set of routes present in 
each node's routing table.

I don't understand the word gradient in this context, throughout the
document.  Is it a derivative of something?  A differential of something?

Alex

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 1 Jul 2009 12:16:46 +0200

Hi Alex:

The links to parents form a DAG. If you include the sibling links it is no more a DAG.

Yet the resulting graph has some properties since there is no orientation that leads deeper; so it is not a general network. The difference between what we are doing and more classical routing is that we REALLY want multipath. So we are ready to forward not only along a classical DAG but also via siblings. 

The decision to pass a given packet to a given sibling is taken on a per packet basis when:
- the DAG does not help, none of the parents is usable at this time (e.g. retries failed)
- per packet loop avoidance allows that sibling for that packet

So the whole question is how do we perform per packet loop avoidance. In a very rich world we could actual use a source route header that traces all the hops along a sibling path and try all possibilities. I guess we cannot afford that. We could also build a DAG between siblings but again that would reduce our opportunities. With the current draft, we resolve the most probable loops and let TTL finish the job.

Basically if:
- nodes prefer parents over siblings, sibling path should be real short, and mostly 1 hop.
- nodes do not give a packet back to a sibling, or there's a tie break there, 1 hop loops would be avoided
- TTL is decremented aggressively along sibling path (Like minus N instead of minus 1), loops should not cost too much

The last option is not in the draft yet. It is on the table for discussion. It is a way to adapt the up*down* to IPv6 that has a single counter, hop limit. So we would allow an outward packet to make up to Hop Limit hops along the DAG, but only up to Hop Limit/N hops along siblings, and disallow going outward.

Makes sense?

Pascal

>-----Original Message-----
>From: Alexandru Petrescu [mailto:[email-masked]]
>Sent: mercredi 1 juillet 2009 11:08
>To: Pascal Thubert (pthubert)
>Cc: Goindi, Manhar; JP Vasseur (jvasseur); ROLL WG
>Subject: Re: [Roll] Fwd: I-D Action:draft-dt-roll-rpl-00.txt Q2..4
>

---

From: Alexandru Petrescu <[email-masked]>
Date: Wed, 01 Jul 2009 12:49:59 +0200

> The links to parents form a DAG. If you include the sibling links it 

So why talking DAG in the first place?  Do you assume there are no links
between siblings?

> Yet the resulting graph has some properties since there is no 
> orientation that leads deeper;

There should be an orientation that leads deeper too.

> so it is not a general network. The difference between what we are 
> doing and more classical routing is that we REALLY want multipath.

Sorry, I don't understand.  IF we wanted multipath then we preferred
links between siblings and also paths down the DAG, not only up to DAG root.

> So we are ready to forward not only along a classical DAG but also 
> via siblings.

Ok this.

> The decision to pass a given packet to a given sibling is taken on a 
> per packet basis when: - the DAG does not help, none of the parents 
> is usable at this time (e.g. retries failed) - per packet loop 
> avoidance allows that sibling for that packet

Sorry, I don't understand you when you say routing on a per packet 
basis.  All routing is on a per packet basis - it looks at dst, consults 
routing table and then puts the packet on the right interface with the 
right dst MAC address.

> So the whole question is how do we perform per packet loop avoidance.
>  In a very rich world we could actual use a source route header that 
> traces all the hops along a sibling path and try all possibilities. I
> guess we cannot afford that. We could also build a DAG between 
> siblings but again that would reduce our opportunities.

I disagree.  To build a loop-free network there are much more options
than just source route headers and DAGs.  I don't understand the choice
of DAG.

> With the current draft, we resolve the most probable loops and let
> TTL finish the job.

Inefficient DAG.  Unnatural DAG.

> Basically if: - nodes prefer parents over siblings, sibling path 
> should be real short, and mostly 1 hop. - nodes do not give a packet 
> back to a sibling, or there's a tie break there, 1 hop loops would be
> avoided - TTL is decremented aggressively along sibling path (Like 
> minus N instead of minus 1), loops should not cost too much
> 
> The last option is not in the draft yet. It is on the table for 
> discussion. It is a way to adapt the up*down* to IPv6 that has a 
> single counter, hop limit. So we would allow an outward packet to 
> make up to Hop Limit hops along the DAG, but only up to Hop Limit/N 
> hops along siblings, and disallow going outward.

If by this table you mean the table of negotiation of DT I think the 
table should be open to much more options of building routing for 
networks than just DAG and src routing.

Alex

---

From: "Goindi, Manhar" <[email-masked]>
Date: Thu, 2 Jul 2009 14:46:35 +1000

Hi Pascal,

Thanks for your clarification!

I shall await the use case drafts and the enhanced metrics draft to get more clarity on the manner to short-list preferred parents & siblings.  For instance, there could be a metric for choosing parents and another metric to choose siblings.

I agree that Case 1 & Case 2 are loops and are not desirable.  Case 4 is superior to Case 3 by offering an alternate path for forwarding by way of siblings.  Thanks for the illustration.

Thanks & Best Regards,

Manhar Goindi

From: Pascal Thubert (pthubert) [mailto:[email-masked]] 
Sent: Tuesday, June 30, 2009 7:20 PM
To: Goindi, Manhar; JP Vasseur (jvasseur); ROLL WG
Subject: RE: [Roll] Fwd: I-D Action:draft-dt-roll-rpl-00.txt Q1

1. How does a node know that DIO it has received from a node should be taken as a Parent or a Sibling with reference to Example in section 3.3.1.4.1?  I mean how would it decide its own depth.

Hi Manhar:

The component that makes that resolution is out of scope. That component, that I call plugin for the lack of a better term,  depends on the metrics which in turn depend on the link type (like RSSI) and the use case (like battery). Because the plugin depends on the metrics, it makes more sense to specify reference examples using those metrics in the current metrics drafts. Other drafts might follow for more specific use cases, and you might even find RA extensions and plugins that are completely proprietary. 

The plugin component is very loosely constrained. It selects an ordered set of preferred parents and from then generic RPL takes over. RPL will use for this node a depth that is incremented from the depth of the deepest parent. The resulting depth enables an abstraction of feasible successors in the same DAG, some parents (least depth) some siblings (same depth). Loop avoidance is guaranteed by construction when packets are passed to parents. It is attempted on a per packet basis when forwarding via siblings.

Note that the plugin might not be use the depth as primary selector for the choice of the preferred parent. For instance that a node sees 2 routers, one at depth 1 with a poor signal indicator and one at depth 2 with a very good signal. The plugin should prefer the second router. 

The resulting graph might depend a lot on how greedy the plugins are.  If you consider that a node is richer when it has a higher number of feasible successors, what society are we trying to build? Let me give you an example. We have a triangle, A, B, C. A is  a root and B and C dynamically appear. Once things settle, you could end up with a situation like:  

 +--->A<---+        +--->A<---+        +--->A<---+        +--->A<---+

 |         |        |         |        |         |        |         |

 |         |        |+--->---+|        |         |        |         |

 B

Manhar Goindi
Technical Expert
Phone: +91 120 3352149

-------->C        B|       |C        B         C        B<------->C

                     +---<---+

   Case 1             Case 2             Case 3             Case 4

Case 1: B is a scrooge. If it comes up after C it sees A  and C and tries to optimize locally its number of parents. If C comes later, B detaches from A and reattaches to again get 2 parents. The resulting depths are A:0, C:1 and B:2 . Drawback: C is always deprived from an alternate forwarding solution. Greediness is discouraged unless the node has a very good reason like critical + low battery but draft 00 lacks any clear cut constraint about that.

Case 2:  C is also greedy. So when B attaches to C as before, C will detach from A to reattach to B and C, and we are in a loop till maximum depth. At which point the looser will attach to A only and we start over the count to infinity. This is definitively broken. A simple tie break is to ignore RAs from deeper, and this is MUSTed in section 5.4 at the end of item 5. So, case 2 is actually impossible with the current spec.

Case 3. B & C are both genuinely altruistic, so anxious of the benefit of others that they wouldn't dare get deeper than they could. So they end up at depth 1 with only one feasible successor, A. The result is in fact even worse than case 1 because neither B nor C can benefit from the other.

Case 4. Same as case 3 with a new rule of allowing sibling forwarding. In that case, B and C are still both depth 1, but they can use one another as alternate (backup) feasible successors. Because the sibling hops do not belong to the DAG, they are not loopless by construction and additional measures must be taken like always prefer a real parent, do not give a packet back to a sibling, decrement hop limit faster, that sort of thing.

The spec is very open but case 4 might be often desirable but for specific nodes that really need to be greedier than average. One way of doing this is to select only ONE preferred parent (then again not necessarily the shallowest one) and orient its vector in the gradient towards that guy. If we do that, the depth will really represent the hops over the preferred and most probable path as opposed to the worst path within selected parents.

My take is that we should SHOULD that behavior. What do you think?

Pascal

From: [email-masked] [mailto:[email-masked]] On Behalf Of Goindi, Manhar

Sent: mardi 30 juin 2009 11:15

To: JP Vasseur (jvasseur); ROLL WG

Subject: Re: [Roll] Fwd: I-D Action:draft-dt-roll-rpl-00.txt

Hi JP,

Thanks a lot for sharing this draft as it proved very informative & I thoroughly enjoyed reading it.

I have the following queries:

2. How does a node know that DIO it has received from a node should be taken as a Parent or a Sibling with reference to Example in section 3.3.1.4.1?  I mean how would it decide its own depth.

3. In Section 3.3.4.4 – why doesn’t node 51 reattach itself as a child to node 53 instead of making node 52 as its parent?  Is it that node 51 cannot hear node 53 directly so it has to go through node 52?

4. Can siblings hear each other as it is not evident from Figure 2:  Example DAG?

5. In section 3.3.4.1:  Moving Down a DAG – it is mentioned that there is little change for a loop and node 56 may reattach to DAG with parents 43 & 55.  How is the formation or non-formation of this loop detected?  What is the mechanism for that?

Would someone like to see if there is an answer to them?

Thanks & Best Regards,

Manhar Goindi

Manhar Goindi

Technical Expert

Landis+Gyr        

Phone: +91 120 3352149

[email-masked]

www.landisgyr.com

manage energy better

From: [email-masked] [mailto:[email-masked]] On Behalf Of JP Vasseur

Sent: Monday, June 29, 2009 10:19 AM

To: ROLL WG

Subject: [Roll] Fwd: I-D Action:draft-dt-roll-rpl-00.txt

Here you are.

Thanks.

JP.

Begin forwarded message:

From: [email-masked]

Date: June 29, 2009 1:15:01 AM CEDT

To: [email-masked]

Subject: I-D Action:draft-dt-roll-rpl-00.txt 

Reply-To: [email-masked]

A New Internet-Draft is available from the on-line Internet-Drafts directories.

            Title           : RPL: Routing Protocol for Low Power and Lossy Networks

            Author(s)       : T. Winter, R. Team

            Filename        : draft-dt-roll-rpl-00.txt

            Pages           : 60

            Date            : 2009-06-28

This document specifies the Routing Protocol for Low Power and Lossy

Networks (RPL), in accordance with the requirements described in

[I-D.ietf-roll-building-routing-reqs],

[I-D.ietf-roll-home-routing-reqs],

[I-D.ietf-roll-indus-routing-reqs], and [RFC5548].

A URL for this Internet-Draft is:

http://www.ietf.org/internet-drafts/draft-dt-roll-rpl-00.txt

Internet-Drafts are also available by anonymous FTP at:

ftp://ftp.ietf.org/internet-drafts/

Below is the data which will enable a MIME compliant mail reader

implementation to automatically retrieve the ASCII version of the

Internet-Draft.

 PLEASE CONSIDER OUR ENVIRONMENT BEFORE PRINTING THIS EMAIL.

This e-mail (including any attachments) is confidential and may be legally privileged. If you are not an intended recipient or an authorized representative of an intended recipient, you are prohibited from using, copying or distributing the information in this e-mail or its attachments. If you have received this e-mail in error, please notify the sender immediately by return e-mail and delete all copies of this message and any attachments. Thank you.

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 02 Jul 2009 11:13:15 +0200

About the metrics discussion.

As mentioned before, I think and believe an energy metric for IPv6 links 
can be useful.  It is related to energy needed to send an 1280byte IPv6 
packet on a certain link hop.

I propose 4 encodings: for RA, for RIPng and two for OSPF (one link 
metric and one multi-link cumulative metric).

Energy Metric Option in Router Advertisement:
     +-----------+    +-----------------+ +--+    +-------+
     |Base Header| ...|Extension Headers| |RA| ...|Options|
     +-----------+    +-----------------+ +--+    +-------+

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |      Type     |    Length     |            Reserved           |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                          Max Link Energy                      |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                          Min Link Energy                      |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Energy Metric Encoded in RIPng RTE:
     +-----------+    +-----------------+ +---+    +----+
     |Base Header| ...|Extension Headers| |UDP| ...|RTEs|
     +-----------+    +-----------------+ +---+    +----+
    +-----------+ +------------++-----------+ +------------++-----------+
    |NextHop1RTE| |Address1 RTE||Energy1 RTE| |Address2 RTE||Energy2 RTE|
    +-----------+ +------------++-----------+ +------------++-----------+

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                          Max Link Energy                      |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                          Min Link Energy                      |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |         route tag (2)         | prefix len (1)| Energy Metric |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Energy Metric Encoded in OSPF Opaque LSA

     +-----------+    +-----------------+ +----------+    +----+
     |Base Header| ...|Extension Headers| |OSPFheader| ...|LSAs|
     +-----------+    +-----------------+ +----------+    +----+

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |            LS age             |     Options   |  9, 10, or 11 |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |  Opaque Type  |               Opaque ID                       |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                      Advertising Router                       |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                      LS Sequence Number                       |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |         LS checksum           |           Length              |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                                                               |
     +-                                                             -+
     |                                                               |
     +-                Link-local Interface Address                 -+
     |                                                               |
     +-                                                             -+
     |                                                               |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                          Max Link Energy                      |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                          Min Link Energy                      |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    I also propose encoding the Energy metric for several IPv6 links by
    expressing the metric in terms of the cost to reach a prefix.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |            LS age             |     Options   |  9, 10, or 11 |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |  Opaque Type  |               Opaque ID                       |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                      Advertising Router                       |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                      LS Sequence Number                       |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |         LS checksum           |           Length              |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                         # prefixes                            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |  PrefixLength | PrefixOptions |             0                 |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                        Address Prefix                         |
    |                                                               |
    |                                                               |
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                          Max Link Energy                      |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                          Min Link Energy                      |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                             ...                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |  PrefixLength | PrefixOptions |             0                 |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                        Address Prefix                         |
    |                                                               |
    |                                                               |
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                          Max Link Energy                      |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                          Min Link Energy                      |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The related biblio follows:
    [callaway-lowpower]
               Callaway, E., "Secure Low-Power Operation of Wireless
               Sensor Networks", January 2004.

    [dsr-encoding-energy]
               Doshi, S., Bhandare, S., and T. Brown, "An On-demand
               Minimum Energy Routing Protocol for a Wireless Ad Hoc
               Network", Mobile Computing and Communications
               Review, Volume 6, pp. 50-66, 2002.

    [efficiency-centric-communication]
               Cao, Q., He, T., Fang, L., Abdelzaher, T., Stankovic, J.,
               and S. Son, "Efficiency Centric Communication Model for
               Wireless Sensor Networks", INFOCOM 2006. 25th IEEE
               International Conference on Computer Communications.
               Proceedings pp. 1-12, April 2006.

    [energy-aware-routing]
               Shah, R. and J. Rabaey, "Energy Aware Routing for Low
               Energy Ad Hoc Sensor Networks", Wireless Communications
               and Networking Conference, 2002. WCNC2002. 2002
               IEEE Volume 1, pp. 350-355, March 2002.

    [energy-conserving]
               Chang, J-H. and L. Tassiulas, "Energy Conserving Routing
               in Wireless Ad-hoc Networks", INFOCOM 2000. Nineteenth
               Annual Joint Conference of the IEEE Computer and
               Communications Societies. Proceedings. IEEE, Volume 1, pp
               22-31, 2000.

    [energy-efficient-aodv]
               Nie, N. and C. Comaniciu, "Energy Efficient AODV Routing
               in CDMA Ad Hoc Networks Using Beamforming", EURASIP
               Journal on Wireless Communications and Networking pp.
               14-14, 2006.

    [energy-efficient-communication]
               Heinzelman, W., Chandrakasan, A., and H. Balakrishnan,
               "Energy-Efficient Communication Protocol for Wireless
               Microsensor Networks", Proceedings of the 33rd Hawaii
               International Conference on System Sciences, HICSS Volume
               8, 2000.

    [energy-efficient-forwarding]
               Busse, M., Haenselmann, T., and W. Effelsberg, "Energy-
               Efficient Forwarding Schemes for Wireless Sensor
               Networks", Proceedings of the 2006 International Symposium
               on on World of Wireless, Mobile and Multimedia
               Networks pp. 125-133, 2006.

    [investigating-energy]
               Finnie, L. and M. Nilsson, "Investigating the Energy
               Consumption of a Wireless Network Interface in an Ad Hoc
               Networking Environment", INFOCOM 2001. Twentieth Annual
               Joint Conference of the IEEE Computer and Communications
               Societies. Proceedings. IEEE Volume 3, pp. 1548-1557,
               2001.

    [link-inef-metric]
               Dhananjay, L., Manjeshwar, A., Herrmann, F., Uysal-
               Biyikoglu, E., and A. Keshavarzian, "Measurement and
               Characterization of Link Quality Metrics in Energy
               Constrained Wireless Sensor Networks", IEEE Global
               Telecommunications Conference, Globecom 03 Volume 1, pp
               446-452, 2003.

    [minimum-energy-mobile]
               Rodoplu, V. and T. Meng, "Minimum Energy Mobile Wireless
               Networks", IEEE Journal on Selected Areas in
               Communications Volume 17, Number 8, August 1999.

    [minimum-energy-revisited]
               Li, L. and J. Halpern, "Minimum-Energy Mobile Wireless
               Networks Revisited", Communications, 2001. ICC 2001. IEEE
               International Conference on Volume 1, pp. 278-283,
               June 2001.

    [new-routing-metric]
               Boughanmi, N. and Y-Q. Song, "A New Routing Metric for
               Satisfying both Energy and Delay Constraints in Wireless
               Sensor Networks", Journal of Signal Processing
               Systems Volume 51, Issue 2, pp. 137-143, May 2008.

    [online-power-aware]
               Li, Q., Aslam, J., and D. Rus, "Online Power-aware Routing
               in Wireless Ad-hoc Networks", Proceedings of the 7th
               annual international conference on Mobile computing and
               networking pp. 97-107, 2001.

    [power-aware-routing]
               Singh, S., Woo, M., and C. Raghavendra, "Power-Aware
               Routing in Mobile Ad Hoc Networks", Proceedings of the 4th
               annual ACM/IEEE international conference on Mobile
               computing and networking pp. 181-190, 1998.

    [power-control-wireless]
               Goodman, D. and N. Mandayam, "Power Control for Wireless
               Data", IEEE Personal Communications , 2000.

    [routing-and-channel]
               Scott, K. and N. Bambos, "Routing and Channel Assignment
               for Low Power Transmission in PCS", Universal Personal
               Communications, 1996. Record., 1996 5th IEEE International
               Conference on Volume 2, pp. 498-502, 1996.

Alex

Goindi, Manhar a écrit :
> I shall await the use case drafts and the enhanced metrics draft to get 
> more clarity on the manner to short-list preferred parents & siblings.  
> For instance, there could be a metric for choosing parents and another 
> metric to choose siblings.
> 
>  
> 
> I agree that Case 1 & Case 2 are loops and are not desirable.  Case 4 is 
> superior to Case 3 by offering an alternate path for forwarding by way 
> of siblings.  Thanks for the illustration.
> 
>  
> 
>  
> 
> Thanks & Best Regards,
> 
> Manhar Goindi
> 
> 
> 
> *Manhar Goindi*
> Technical Expert
> Phone: +91 120 3352149
> 
> *From:* Pascal Thubert (pthubert) [mailto:[email-masked]]
> *Sent:* Tuesday, June 30, 2009 7:20 PM
> *To:* Goindi, Manhar; JP Vasseur (jvasseur); ROLL WG
> *Subject:* RE: [Roll] Fwd: I-D Action:draft-dt-roll-rpl-00.txt Q1
> 
>  
> 
> 1. How does a node know that DIO it has received from a node should be 
> taken as a Parent or a Sibling with reference to Example in section 
> 3.3.1.4.1?  I mean how would it decide its own depth.
> 
>  
> 
> Hi Manhar:
> 
>  
> 
> The component that makes that resolution is out of scope. That 
> component, that I call plugin for the lack of a better term,  depends on 
> the metrics which in turn depend on the link type (like RSSI) and the 
> use case (like battery). Because the plugin depends on the metrics, it 
> makes more sense to specify reference examples using those metrics in 
> the current metrics drafts. Other drafts might follow for more specific 
> use cases, and you might even find RA extensions and plugins that are 
> completely proprietary.
> 
>  
> 
> The plugin component is very loosely constrained. It selects an ordered 
> set of preferred parents and from then generic RPL takes over. RPL will 
> use for this node a depth that is incremented from the depth of the 
> deepest parent. The resulting depth enables an abstraction of feasible 
> successors in the same DAG, some parents (least depth) some siblings 
> (same depth). Loop avoidance is guaranteed by construction when packets 
> are passed to parents. It is attempted on a per packet basis when 
> forwarding via siblings.
> 
>  
> 
> Note that the plugin might not be use the depth as primary selector for 
> the choice of the preferred parent. For instance that a node sees 2 
> routers, one at depth 1 with a poor signal indicator and one at depth 2 
> with a very good signal. The plugin should prefer the second router.
> 
>  
> 
> The resulting graph might depend a lot on how greedy the plugins are.  
> If you consider that a node is richer when it has a higher number of 
> feasible successors, what society are we trying to build? Let me give 
> you an example. We have a triangle, A, B, C. A is  a root and B and C 
> dynamically appear. Once things settle, you could end up with a 
> situation like: 
> 
>         
> 
>  B-------->C        B|       |C        B         C        B<------->C
> 
>                      +---<---+
> 
> Case 1: B is a scrooge. If it comes up after C it sees A  and C and 
> tries to optimize locally its number of parents. If C comes later, B 
> detaches from A and reattaches to again get 2 parents. The resulting 
> depths are A:0, C:1 and B:2 . Drawback: C is always deprived from an 
> alternate forwarding solution. Greediness is discouraged unless the node 
> has a very good reason like critical + low battery but draft 00 lacks 
> any clear cut constraint about that.
> 
>  
> 
> Case 2:  C is also greedy. So when B attaches to C as before, C will 
> detach from A to reattach to B and C, and we are in a loop till maximum 
> depth. At which point the looser will attach to A only and we start over 
> the count to infinity. This is definitively broken. A simple tie break 
> is to ignore RAs from deeper, and this is MUSTed in section 5.4 at the 
> end of item 5. So, case 2 is actually impossible with the current spec.
> 
>  
> 
> Case 3. B & C are both genuinely altruistic, so anxious of the benefit 
> of others that they wouldn't dare get deeper than they could. So they 
> end up at depth 1 with only one feasible successor, A. The result is in 
> fact even worse than case 1 because neither B nor C can benefit from the 
> other.
> 
>  
> 
> Case 4. Same as case 3 with a new rule of allowing sibling forwarding. 
> In that case, B and C are still both depth 1, but they can use one 
> another as alternate (backup) feasible successors. Because the sibling 
> hops do not belong to the DAG, they are not loopless by construction and 
> additional measures must be taken like always prefer a real parent, do 
> not give a packet back to a sibling, decrement hop limit faster, that 
> sort of thing.
> 
>  
> 
> The spec is very open but case 4 might be often desirable but for 
> specific nodes that really need to be greedier than average. One way of 
> doing this is to select only ONE preferred parent (then again not 
> necessarily the shallowest one) and orient its vector in the gradient 
> towards that guy. If we do that, the depth will really represent the 
> hops over the preferred and most probable path as opposed to the worst 
> path within selected parents.
> 
>  
> 
> 2. How does a node know that DIO it has received from a node should be 
> taken as a Parent or a Sibling with reference to Example in section 
> 3.3.1.4.1?  I mean how would it decide its own depth.
> 
> 3. In Section 3.3.4.4 – why doesn’t node 51 reattach itself as a child 
> to node 53 instead of making node 52 as its parent?  Is it that node 51 
> cannot hear node 53 directly so it has to go through node 52?
> 
> 5. In section 3.3.4.1:  Moving Down a DAG – it is mentioned that there 
> is little change for a loop and node 56 may reattach to DAG with parents 
> 43 & 55.  How is the formation or non-formation of this loop detected?  
> What is the mechanism for that?
> 
>  
> 
> This e-mail (including any attachments) is confidential and may be 
> legally privileged. If you are not an intended recipient or an 
> authorized representative of an intended recipient, you are prohibited 
> from using, copying or distributing the information in this e-mail or 
> its attachments. If you have received this e-mail in error, please 
> notify the sender immediately by return e-mail and delete all copies of 
> this message and any attachments. Thank you.
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: JP Vasseur <[email-masked]>
Date: Thu, 2 Jul 2009 11:37:31 +0200

Hi Alex,

We can certainly continue the discussion on whether we need a link  
energy metric.
For the ID, it will be updated once a routing protocol will have been  
chosen by the WG.

Thanks.

JP.

On Jul 2, 2009, at 11:13 AM, Alexandru Petrescu wrote:

> As mentioned before, I think and believe an energy metric for IPv6  
> links can be useful.  It is related to energy needed to send an  
> 1280byte IPv6 packet on a certain link hop.
>
>> I shall await the use case drafts and the enhanced metrics draft to  
>> get more clarity on the manner to short-list preferred parents &  
>> siblings.  For instance, there could be a metric for choosing  
>> parents and another metric to choose siblings.
>> I agree that Case 1 & Case 2 are loops and are not desirable.  Case  
>> 4 is superior to Case 3 by offering an alternate path for  
>> forwarding by way of siblings.  Thanks for the illustration.
>>  Thanks & Best Regards,
>> Manhar Goindi
>> *Manhar Goindi*
>> Technical Expert
>> Phone: +91 120 3352149
>> 1. How does a node know that DIO it has received from a node should  
>> be taken as a Parent or a Sibling with reference to Example in  
>> section 3.3.1.4.1?  I mean how would it decide its own depth.
>> Hi Manhar:
>> component, that I call plugin for the lack of a better term,   
>> depends on the metrics which in turn depend on the link type (like  
>> RSSI) and the use case (like battery). Because the plugin depends  
>> on the metrics, it makes more sense to specify reference examples  
>> using those metrics in the current metrics drafts. Other drafts  
>> might follow for more specific use cases, and you might even find  
>> RA extensions and plugins that are completely proprietary.
>> The plugin component is very loosely constrained. It selects an  
>> ordered set of preferred parents and from then generic RPL takes  
>> over. RPL will use for this node a depth that is incremented from  
>> the depth of the deepest parent. The resulting depth enables an  
>> abstraction of feasible successors in the same DAG, some parents  
>> (least depth) some siblings (same depth). Loop avoidance is  
>> guaranteed by construction when packets are passed to parents. It  
>> is attempted on a per packet basis when forwarding via siblings.
>> Note that the plugin might not be use the depth as primary selector  
>> for the choice of the preferred parent. For instance that a node  
>> sees 2 routers, one at depth 1 with a poor signal indicator and one  
>> at depth 2 with a very good signal. The plugin should prefer the  
>> second router.
>> The resulting graph might depend a lot on how greedy the plugins  
>> are.  If you consider that a node is richer when it has a higher  
>> number of feasible successors, what society are we trying to build?  
>> Let me give you an example. We have a triangle, A, B, C. A is  a  
>> root and B and C dynamically appear. Once things settle, you could  
>> end up with a situation like:          +--->A<---+        +--->A<--- 
>> +        +--->A<---+        +--->A<---+
>> |         |        |         |        |         |        |         |
>> |         |        |+--->---+|        |         |        |         |
>> tries to optimize locally its number of parents. If C comes later,  
>> B detaches from A and reattaches to again get 2 parents. The  
>> resulting depths are A:0, C:1 and B:2 . Drawback: C is always  
>> deprived from an alternate forwarding solution. Greediness is  
>> discouraged unless the node has a very good reason like critical +  
>> low battery but draft 00 lacks any clear cut constraint about that.
>> Case 2:  C is also greedy. So when B attaches to C as before, C  
>> will detach from A to reattach to B and C, and we are in a loop  
>> till maximum depth. At which point the looser will attach to A only  
>> and we start over the count to infinity. This is definitively  
>> broken. A simple tie break is to ignore RAs from deeper, and this  
>> is MUSTed in section 5.4 at the end of item 5. So, case 2 is  
>> actually impossible with the current spec.
>> Case 3. B & C are both genuinely altruistic, so anxious of the  
>> benefit of others that they wouldn't dare get deeper than they  
>> could. So they end up at depth 1 with only one feasible successor,  
>> A. The result is in fact even worse than case 1 because neither B  
>> nor C can benefit from the other.
>> Case 4. Same as case 3 with a new rule of allowing sibling  
>> forwarding. In that case, B and C are still both depth 1, but they  
>> can use one another as alternate (backup) feasible successors.  
>> Because the sibling hops do not belong to the DAG, they are not  
>> loopless by construction and additional measures must be taken like  
>> always prefer a real parent, do not give a packet back to a  
>> sibling, decrement hop limit faster, that sort of thing.
>> specific nodes that really need to be greedier than average. One  
>> way of doing this is to select only ONE preferred parent (then  
>> again not necessarily the shallowest one) and orient its vector in  
>> the gradient towards that guy. If we do that, the depth will really  
>> represent the hops over the preferred and most probable path as  
>> opposed to the worst path within selected parents.
>> 2. How does a node know that DIO it has received from a node should  
>> be taken as a Parent or a Sibling with reference to Example in  
>> section 3.3.1.4.1?  I mean how would it decide its own depth.
>> 3. In Section 3.3.4.4 – why doesn’t node 51 reattach itself as a  
>> child to node 53 instead of making node 52 as its parent?  Is it  
>> that node 51 cannot hear node 53 directly so it has to go through  
>> node 52?
>> 5. In section 3.3.4.1:  Moving Down a DAG – it is mentioned that  
>> there is little change for a loop and node 56 may reattach to DAG  
>> with parents 43 & 55.  How is the formation or non-formation of  
>> this loop detected?  What is the mechanism for that?
>> Landis+Gyr        Phone: +91 120 3352149
>> Subject: I-D Action:draft-dt-roll-rpl-00.txt Reply-To: [email-masked]
>> authorized representative of an intended recipient, you are  
>> prohibited from using, copying or distributing the information in  
>> this e-mail or its attachments. If you have received this e-mail in  
>> error, please notify the sender immediately by return e-mail and  
>> delete all copies of this message and any attachments. Thank you.