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

[JP Vasseur <[e-mail]>]

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:

> 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: [phone]
>> *From:* Pascal Thubert (pthubert) [mailto:[e-mail]]
>> *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: [e-mail] [mailto:[e-mail]] 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: [phone]
>> [e-mail]
>> www.landisgyr.com
>> manage energy better
>> From: [e-mail] [mailto:[e-mail]] 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: [e-mail]
>> Date: June 29, 2009 1:15:01 AM CEDT
>> To: [e-mail]
>> Subject: I-D Action:draft-dt-roll-rpl-00.txt Reply-To: [e-mail]
>> 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
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/roll
>
>