Re: [Roll] energy metric for IPv6 links (was: Fwd: I-D Action:draft-dt-roll-rpl-00.txt Q1)

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 :
> 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
> 
> 
> 
> *Manhar Goindi*
> Technical Expert
> Phone: +91 120 3352149
> 
> *From:* Pascal Thubert (pthubert) [mailto:pthubert@cisco.com]
> *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-------->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: roll-bounces@ietf.org [mailto:roll-bounces@ietf.org] 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
> 
> manhar.goindi@landisgyr.com
> 
> www.landisgyr.com
> 
>  
> 
> manage energy better
> 
> From: roll-bounces@ietf.org [mailto:roll-bounces@ietf.org] 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: Internet-Drafts@ietf.org
> 
> Date: June 29, 2009 1:15:01 AM CEDT
> 
> To: i-d-announce@ietf.org
> 
> Subject: I-D Action:draft-dt-roll-rpl-00.txt 
> 
> Reply-To: internet-drafts@ietf.org
> 
>  
> 
> 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.
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Roll mailing list
> Roll@ietf.org
> https://www.ietf.org/mailman/listinfo/roll