Subject: [Roll] RPL Metric ID

From: JP Vasseur <[email-masked]>
Date: Wed, 7 Oct 2009 20:07:52 +0200

Dear all,

We would appreciate your feed-back on RPL routing metrics.

Now that RPL is stabilizing it is time to move forward with the METRIC  
I-D. The next revision will be a major one, with packet encoding,  
processing rules, etc.

We discussed and agreed some time ago on several links and nodes  
metrics (also required according to our requirement IDs).

Still, there are a few metrics for which we would like to know whether  
you think that they should be specified.

4.2.  Latency

    As with throughput, the latency of many LLN MAC sub-layers can be
    varied over many orders of magnitude, again with a corresponding
    change in current consumption.  Some LLN MACs will allow the latency
    to be adjusted globally on the subnet, or on a link-by-link basis,  
or
    not at all.  Some will insist that it be fixed for a given link, but
    allow it to be variable from link to link.  For efficient operation,
    nodes must be able to report the range of latency that their links
    can handle, and the currently available latency.

4.3.  Link reliability

    In LLNs, link reliability is degraded by external interference and
    multi-path interference.  Multipath typically affects both  
directions
    on the link equally, whereas external interference is sometimes uni-
    directional.  Time scales vary from milliseconds to days, and are
    often periodic and linked to human activity.  Packet error rate can
    generally be measured directly, and other metrics (e.g. bit error
    rate, mean time between failures) are typically derived from that.

In addition:

Node Memory resources:

Memory is a critical node resources in presence of constrained nodes.  
Is there a need to report node memory resources as a routing metric/ 
constraint ?

Node CPU resources:
CPU duty cycle for virtually all LLN applications to date is well  
below 10%, and the trend in low power embedded systems is to more  
capable processors rather than less. Computational speed is not  
expected to be a limiting factor in routing in LLNs. Is there a need  
to report node CPU resources as a routing metric/constraint ?

Link Security metrics

Thanks for your feed-back.

JP, Mijeon, Kris.

---

From: Michael Richardson <[email-masked]>
Date: Wed, 07 Oct 2009 15:30:31 -0400

>>>>> "JP" == JP Vasseur <[email-masked]> writes:
    JP> We discussed and agreed some time ago on several links and nodes
    JP> metrics (also required according to our requirement IDs).

    JP> Still, there are a few metrics for which we would like to know
    JP> whether you think that they should be specified.

  If I understand your question, you are asking if the protocol should
carry these fields in the DIOs, and transmitted through the DAG?
  Or are you asking if these things should be configured into the node
(somehow? operator?) and taken into account.
  Or are you asking if RPL has to somehow measure these things for each
on-link peer ("cousin"?), such that it can be taken into account?

    JP> Node CPU resources: CPU duty cycle for virtually all LLN
    JP> applications to date is well below 10%, and the trend in low
    JP> power embedded systems is to more capable processors rather than
    JP> less. Computational speed is not expected to be a limiting
    JP> factor in routing in LLNs. Is there a need to report node CPU
    JP> resources as a routing metric/constraint ?

  I.e. it's better to be a sleepy hare, than a slow-plodding-tortoise.

-- 
]       He who is tired of Weird Al is tired of life!           |  firewalls  [
]   Michael Richardson, Sandelman Software Works, Ottawa, ON    |net architect[
] [email-masked] http://www.sandelman.ottawa.on.ca/ |device driver[
   Kyoto Plus: watch the video <http://www.youtube.com/watch?v=kzx1ycLXQSE>
	               then sign the petition.

---

From: Mukul Goyal <[email-masked]>
Date: Wed, 7 Oct 2009 14:40:44 -0500 (CDT)

I think both latency and reliability are important metrics. 

I am sort of negative on using memory/CPU availability as metric or constraint. They seem like local factors to me. If a node is running low on memory/CPU, it can simply not participate in routing.

Thanks
Mukul
 
----- Original Message -----
From: "JP Vasseur" <[email-masked]>
To: "IETF ROLL" <[email-masked]>
Cc: "Kris Pister" <[email-masked]>
Sent: Wednesday, October 7, 2009 1:07:52 PM GMT -06:00 US/Canada Central
Subject: [Roll] RPL Metric ID

Dear all, 

Now that RPL is stabilizing it is time to move forward with the METRIC I-D. The next revision will be a major one, with packet encoding, processing rules, etc. 

We discussed and agreed some time ago on several links and nodes metrics (also required according to our requirement IDs). 

Still, there are a few metrics for which we would like to know whether you think that they should be specified. 

4.2.  Latency 

   to be adjusted globally on the subnet, or on a link-by-link basis, or 

4.3.  Link reliability 

   multi-path interference.  Multipath typically affects both directions 

In addition: 

Node Memory resources: 

Memory is a critical node resources in presence of constrained nodes. Is there a need to report node memory resources as a routing metric/constraint ? 

Node CPU resources: 
CPU duty cycle for virtually all LLN applications to date is well below 10%, and the trend in low power embedded systems is to more capable processors rather than less. Computational speed is not expected to be a limiting factor in routing in LLNs. Is there a need to report node CPU resources as a routing metric/constraint ? 

Link Security metrics 

JP, Mijeon, Kris. 
_______________________________________________
Roll mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/roll

---

From: [email-masked]
Date: Wed, 7 Oct 2009 14:51:08 -0500

JP,

I am not sure what you're asking, but I 'll hazard a guess.  Let me know 
if my comments make sense.

I believe you are saying that the Metrics ID specifies some minimization 
strategies and are asking if we should add additional strategies for 1) 
latency and 2) link reliability.

As for latency, I am presuming this would be analogous to a QoS strategy. 
That is move packets from point 'a'  to point 'b' in the minimal amount of 
time.  The Building Requirements called out a QoS requirement to assure 
high priority packets (e.g. Fire Alarms) could traverse the LLN faster 
than other messages.

As for Link Reliability, I also vote 'yes'.  I am presume that Link 
Reliability is akin to ETX.  That is moving packets from point 'a' to 
point 'b' with the best possible change of success of arrival with no 
errors.

So I think I have answered your questions.  If not, please let me know.

Jerry

JP Vasseur <[email-masked]> 
Sent by: [email-masked]
10/07/2009 01:08 PM

To
IETF ROLL <[email-masked]>
cc
Kris Pister <[email-masked]>
Subject
[Roll] RPL Metric ID

Dear all,

We discussed and agreed some time ago on several links and nodes metrics 
(also required according to our requirement IDs).

Still, there are a few metrics for which we would like to know whether you 
think that they should be specified.

4.2.  Latency

4.3.  Link reliability

In addition:

Node Memory resources:

Memory is a critical node resources in presence of constrained nodes. Is 
there a need to report node memory resources as a routing 
metric/constraint ?

Node CPU resources:
CPU duty cycle for virtually all LLN applications to date is well below 
10%, and the trend in low power embedded systems is to more capable 
processors rather than less. Computational speed is not expected to be a 
limiting factor in routing in LLNs. Is there a need to report node CPU 
resources as a routing metric/constraint ?

Link Security metrics

JP, Mijeon, Kris._______________________________________________
Roll mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/roll

---

From: JP Vasseur <[email-masked]>
Date: Thu, 8 Oct 2009 07:50:52 +0200

Hi Jerry,

On Oct 7, 2009, at 9:51 PM, [email-masked] wrote:

>
> JP,
>
> I am not sure what you're asking, but I 'll hazard a guess.  Let me  
> know if my comments make sense.
>
> I believe you are saying that the Metrics ID specifies some  
> minimization strategies and are asking if we should add additional  
> strategies for 1) latency and 2) link reliability.
>

That's right. This document specifies the list of metric used by RPL  
to build the DAG (parent selection).

> As for latency, I am presuming this would be analogous to a QoS  
> strategy.  That is move packets from point 'a'  to point 'b' in the  
> minimal amount of time.  The Building Requirements called out a QoS  
> requirement to assure high priority packets (e.g. Fire Alarms) could  
> traverse the LLN faster than other messages.
>

Yes, I would just like to clarify something here. We are not  
discussing QoS, which strictly speaking refers to the set of  
mechanisms used along the forwarding path (scheduling, congestion  
management such as RED, ...) once the path is computed. For example,  
you could compute the DAG based on a reliability metrics and provide  
differentiated QoS to traffic forwarded along this path.

The question here is whether we should use a QoS metric to build the  
DAG and if yes what should be the metric. Several IETF ago, we agreed  
that queueing delays were not a good idea due to their high  
fluctuation. Furthermore, it does not make much sense when nodes have  
1 packet buffer ...

This is why the proposal was here to use latency in order to reflect  
the MAC latency, which may indeed vary by an order of magnitude.

> Reliability is akin to ETX.  That is moving packets from point 'a'  
> to point 'b' with the best possible change of success of arrival  
> with no errors.

Right.

In the implementations that you deployed, did you use such "QoS" and  
reliability metric ? In which units ?

Thanks.

JP.

> Now that RPL is stabilizing it is time to move forward with the  
> METRIC I-D. The next revision will be a major one, with packet  
> encoding, processing rules, etc.
>
> Still, there are a few metrics for which we would like to know  
> whether you think that they should be specified.
>
> 4.2.  Latency
>
> Memory is a critical node resources in presence of constrained  
> nodes. Is there a need to report node memory resources as a routing  
> metric/constraint ?
>
> Node CPU resources:

---

From: JP Vasseur <[email-masked]>
Date: Thu, 8 Oct 2009 07:52:27 +0200

Hi Mukul,

> I think both latency and reliability are important metrics.

OK thanks for the feed-backs.
The most obvious and common reliability is ETX.
Any preference for the latency?

> I am sort of negative on using memory/CPU availability as metric or  
> constraint. They seem like local factors to me. If a node is running  
> low on memory/CPU, it can simply not participate in routing.

And we already have an "overload" bit.

Thanks.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Thu, 8 Oct 2009 07:52:55 +0200

Hi Jerry,

Right.

Thanks.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Thu, 8 Oct 2009 07:57:44 +0200

Hi Michael,

> (somehow? operator?) and taken into account.

This is already specified in RPL: metrics are carried in the DAG  
Metric Container
and used during parent selection process according to the OF.

So the question is whether we should have metrics reflecting link  
latency, reliability, ...

> on-link peer ("cousin"?), such that it can be taken into account?

The local per-link metric is also taken into account. Upon receiving a  
RA-DIO,
a node will take into account the advertised metric, OF, rank and also  
local
link characteristics.

Thanks.

JP.

>   Kyoto Plus: watch the video <http://www.youtube.com/watch?v=kzx1ycLXQSE 
> >
> 	               then sign the petition.

---

From: [email-masked]
Date: Thu, 8 Oct 2009 08:19:33 -0500

JP,

Thanks for the response.

Per your question, our current implementation uses standard ZigBee 
algorithms.  ZigBee bases path costs on RSSI only.  While nice and simple; 
unfortunately we feel this approach doesn't necessarily pick the best 
communication paths, only the ones that have a strong signal.  Mukul did a 
lot of simulation work for us on this and helped drive us to this 
conclusion.

Our product was developed and deployed in 2006.  We used what is termed 
the 'ZigBee 2006 Stack'.  Since that time, ZigBee has developed the 
'ZigBee PRO' stack which will in time subsume the ZigBee Stack.  ZigBee 
PRO selects paths based on the best symmetric path found.  I believe 
asymmetric paths are discarded or only used as a last resort. 
Unfortunately, I have no empirical or simulation data on this metric. 
Maybe Richard can provide some insight on this approach since I believe it 
was championed by Ember.

Jerry

10/08/2009 12:53 AM

To
[email-masked]
cc
IETF ROLL <[email-masked]>, Kris Pister <[email-masked]>, 
"???[??????]" <[email-masked]>
Subject
Re: [Roll] RPL Metric ID

Hi Jerry,

JP, 

That's right. This document specifies the list of metric used by RPL to 
build the DAG (parent selection).

Yes, I would just like to clarify something here. We are not discussing 
QoS, which strictly speaking refers to the set of mechanisms used along 
the forwarding path (scheduling, congestion management such as RED, ...) 
once the path is computed. For example, you could compute the DAG based on 
a reliability metrics and provide differentiated QoS to traffic forwarded 
along this path.

The question here is whether we should use a QoS metric to build the DAG 
and if yes what should be the metric. Several IETF ago, we agreed that 
queueing delays were not a good idea due to their high fluctuation. 
Furthermore, it does not make much sense when nodes have 1 packet buffer 
... 

This is why the proposal was here to use latency in order to reflect the 
MAC latency, which may indeed vary by an order of magnitude. 

Right. 

Thanks.

JP.

Jerry 

To

Dear all, 

4.2.  Latency 

4.3.  Link reliability 

In addition: 

Node Memory resources: 

Node CPU resources: 

Link Security metrics

---

From: JP Vasseur <[email-masked]>
Date: Thu, 8 Oct 2009 16:10:42 +0200

Hi Jerry,

On Oct 8, 2009, at 3:19 PM, [email-masked] wrote:

> algorithms.  ZigBee bases path costs on RSSI only.  While nice and  
> simple; unfortunately we feel this approach doesn't necessarily pick  
> the best communication paths, only the ones that have a strong  
> signal.  Mukul did a lot of simulation work for us on this and  
> helped drive us to this conclusion.

I see, thanks. At least you will get a reliability metric.

>
> Our product was developed and deployed in 2006.  We used what is  
> termed the 'ZigBee 2006 Stack'.  Since that time, ZigBee has  
> developed the 'ZigBee PRO' stack which will in time subsume the  
> ZigBee Stack.  ZigBee PRO selects paths based on the best symmetric  
> path found.  I believe asymmetric paths are discarded or only used  
> as a last resort.  Unfortunately, I have no empirical or simulation  
> data on this metric.  Maybe Richard can provide some insight on this  
> approach since I believe it was championed by Ember.

Richard ?

Thanks Jerry.

JP.

> DAG and if yes what should be the metric. Several IETF ago, we  
> agreed that queueing delays were not a good idea due to their high  
> fluctuation. Furthermore, it does not make much sense when nodes  
> have 1 packet buffer ...
>

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 08 Oct 2009 16:18:46 +0200

Hi JP,

I am attracted by the subject of the mail, it is about Metric I-D 
(Internet Draft).  However, I am not sure what are you asking for? 
Please see below feedback I'm interested in.

> (also required according to our requirement IDs).

I really am not sure there was agreement on the link metrics.  I 
suggested several times a way to encode the link metrics and there 
didn't seem to be universal agreement, only some.

I still suggest to have link metrics taken into account by ICMP, routing 
protocols _and_ RPL.  These link metrics would express the energy needed 
to send a certain amount of bytes on a certain interface, or on a 
certain path.  The exression would be made in Joules, as 
single-precision 32bit floats, with two values: min and max.  Like this:

>     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                      |
>     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> 
> 
>    Type:
> 
>            TBA (see [ICMPv6parms])
> 
>            Energy Metric Option for IPv6 Link.
> 
>    Length:
> 
>            Decimal 10.
> 
> 
>    Reserved:
> 
>            Set to zero by sender and ignored by receiver.
> 
> 
>    Max Link Energy
> 
>            Single-precision 32bit floating point number in binary
>            interchange format (see [IEEE754-2008] and [IEC60559-2.0]), a
>            C 'float' type (see [ISOIEC-C99]), and in network byte order.
>            The value represents the maximum energy, expressed in Joules,
>            necessary to send a packet of size 1280 bytes on this link.
> 
>    Min Link Energy
> 
>            Single-precision floating point number representing the
>            minimum energy, expressed in Joules, necessary to send 1280
>            bytes on this link.

Alex

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 08 Oct 2009 11:03:22 -0400

Jerry,

   From: [email-masked]
   Date: Thu, 8 Oct 2009 08:19:33 -0500

   Per your question, our current implementation uses standard ZigBee
   algorithms.  ZigBee bases path costs on RSSI only.

No, ZigBee's path costs are based on the probability of
packet reception over the link.  See Section 3.6.3.1 of the
ZigBee spec.  RSSI above the noise floor could be used to
estimate that probability, of course.  Raw RSSI doesn't tell
you very much.

Not quite.  ZigBee PRO only requires that the cost assigned
to an asymmetric link be the worse of the two unidirectional
costs.

   Unfortunately, I have no empirical or simulation data on this
   metric.  Maybe Richard can provide some insight on this approach
   since I believe it was championed by Ember.

Ember and Mitsubishi proposed the solution that was adopted
(exchanging link costs with neighbors).  The actual problem
that it solved was first raised by Ghulam Bhatti of
Mitsubishi, if I remember correctly.  Under certain
circumstances having the two ends of a link use different
costs could cause ZigBee's P2P routing to consistently fail
to discover a route.  The problem was fairly fundamental to
ZigBee's P2P mechanism, and given the other advantages of
identifying asymmetries and knowing more about your local
neighborhood, ZigBee added a feature where nodes inform
their neighbors of their link costs.  This seems like
something that could be done at the link layer.

                                    -Richard Kelsey

---

From: Philip Levis <[email-masked]>
Date: Thu, 8 Oct 2009 09:08:40 -0700

> helped drive us to this conclusion.

Path selection based purely on RSSI (or any other PHY parameter) also  
suffers from biased sampling. It could be that all received packets  
have a high RSSI, but only half the packets are received. Interference  
(high I, leading to low SINR on some packets) or highly variable  
channels (high variance in S, leading to low SINR on some packets) can  
cause this. The result is a protocol uses poor paths because it  
doesn't know better[1]. Note that this kind of behavior typically  
doesn't show up in simulation, as most simulators limit themselves to  
gaussian-based analytical models of the channel and don't consider  
external interference.

The standard solution is to use link-layer delivery rates to  
supplement the physical layer parameters. E.g., one can try another  
path after a few failures[2] or use link layer delivery rates to  
dynamically calculate costs[3].

> approach since I believe it was championed by Ember.

For a path to be asymmetric, it must have at least one asymmetric  
link. My experience is that asymmetric links are of limited use for  
LLNs. Because LLNs are lossy, they tend to have single-hop  
acknowledgment schemes, either at the link layer or at the network  
layer. Single-hop acknowledgments don't work well in asymmetric links.  
Yes, the acknowledgments are shorter and so the ARR (acknowledgment  
reception rate) can be higher than the PRR (packet reception rate),  
but this window is so narrow and the complexity needed to use it is  
significant enough that asymmetric links are more an intellectual  
curiosity rather than something of significant value to exploit.

Phil

[1] R. Fonseca, O. Gnawali, K. Jamieson, and P. Levis. "Four Bit  
Wireless Link Estimation." In the Proceedings of the 6th Workshop on  
Hot Topics in Networking (HotNets-VI), 2007.

[2] J. Hui and D. Culler. "IP is dead, long live IP for wireless  
sensor networks." In the 6th ACM Conference on Embedded Networked  
Sensor Systems (SenSys), 2008.

[3] O. Gnawali, R. Fonseca, K. Jamieson, D. Moss and P. Levis.  
"Collection Tree Protocol." To appear in the
7th ACM Conference on Embedded Networked Sensor Systems (SenSys), 2009.

---

From: JP Vasseur <[email-masked]>
Date: Fri, 9 Oct 2009 11:35:58 +0200

Hi Alex,

> (Internet Draft).  However, I am not sure what are you asking for?

Which metric should be defined for RPL (link and node). Note that we  
have several metrics already defined, but still a few TBD.

> I still suggest to have link metrics taken into account by ICMP,  
> routing protocols _and_ RPL.

Not sure why you refer to ICMP here but back to RPL ...

> These link metrics would express the energy needed to send a certain  
> amount of bytes on a certain interface, or on a certain path.  The  
> exression would be made in Joules, as single-precision 32bit floats,  
> with two values: min and max.  Like this:
>

Yes I do remember the discussion ... but I cannot see how this would  
be helpful. Indeed, even if a node receives two RA-DIO messages from  
parents that reports path-1 with energy G1 and path-2 with energy G2  
(we can discuss the packet format later on), in which way would that  
help in the path selection process? It might very well be that the  
past that consumes the most energy is to the one that is preferable ?

Thanks.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Fri, 9 Oct 2009 11:42:26 +0200

Hi Richard,

> estimate that probability, of course.  Raw RSSI doesn't tell

Right. What we need to define is metric that describes the probability  
of packet delivery
ratio along the path. Since RPL is a distance vector, we would use a  
cumulative metric.
Of course, each node should filter out the transient error rate and  
periodicity of the metric
update should be limited to avoid routing metric but this not specific  
to the reliability metric.
It is true for all dynamic metrics.

The objective is thus to define a cumulative reliability metric  
reflecting the probability of success
path delivery, in units independent of the Link layer. Local  
mechanisms to filter out local transient
phenomena are left to implementation specific decisions.

Make sense ?

> termed

Makes sense. We had a discussion on this too, and it was decided not  
to take it into account
for the time being.

> something that could be done at the link layer.

Yes.

JP.

---

From: Tim Winter <[email-masked]>
Date: Fri, 09 Oct 2009 10:08:12 -0400

> I think both latency and reliability are important metrics. 
+1

> I am sort of negative on using memory/CPU availability as metric or constraint. They seem like local factors to me. If a node is running low on memory/CPU, it can simply not participate in routing.
Exposing an exaggerated rank might also be an option.

-Tim

---

From: Richard Kelsey <[email-masked]>
Date: Fri, 09 Oct 2009 10:28:08 -0400

From: Philip Levis <[email-masked]>
   Date: Thu, 8 Oct 2009 09:08:40 -0700

   My experience is that asymmetric links are of limited use for  

I completely agree.  In addition, if the routing layer
assumes that links are bidirectional, it is important that
the any link quality measurement not make the same assumption.
In other words, either the link layer or routing layer has
to take asymmetries into account.

                                 -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Fri, 9 Oct 2009 08:05:07 -0700

In general, I agree with both Phil and Richard, but asymmetric links  
are a bit ill-defined in this discussion.  The implicit meaning in  
seems to have been that communication is "good" in one direction while  
"bad" in the reverse.  Instead, I'd prefer to make a stronger  
statement and say that the routing metrics should project symmetric  
information about the links - meaning that the computed cost of using  
the link in one direction is the same as in the reverse direction.   
Obviously, this is more natural in some metrics (reliability, signal  
strength) than others (latency, energy).  But, in my experience,  
relying on symmetric information when it is natural to do so does  
simplify the routing problem.

--
Jonathan Hui

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 09 Oct 2009 19:39:24 +0200

JP Vasseur a écrit :
>> From: [email-masked] Date: Thu, 8 Oct 2009 08:19:33
>> -0500
>> 
>> No, ZigBee's path costs are based on the probability of packet
>> reception over the link.  See Section 3.6.3.1 of the ZigBee spec.
>> RSSI above the noise floor could be used to estimate that
>> probability, of course.  Raw RSSI doesn't tell you very much.
>> 
> 
> Right. What we need to define is metric that describes the
> probability of packet delivery ratio along the path.

JP, that is your definition of what's needed and I respectfully disagree.

PAcket delivery ratio is something which equals "best effort" i.e. it 
has no number quantifying it.

Energy?  Energy is something different, and doesn't relate to "best 
effort" - it can be quantified.

Alex

  Since RPL is a
> distance vector, we would use a cumulative metric. Of course, each
> node should filter out the transient error rate and periodicity of
> the metric update should be limited to avoid routing metric but this
> not specific to the reliability metric. It is true for all dynamic
> metrics.
> 
> reflecting the probability of success path delivery, in units
> independent of the Link layer. Local mechanisms to filter out local
> transient phenomena are left to implementation specific decisions.
> 
> Make sense ?
> 
> 
>> as a last resort.
>> Not quite.  ZigBee PRO only requires that the cost assigned to an
>> asymmetric link be the worse of the two unidirectional costs.
> 
> to take it into account for the time being.
> 
>> 
>> (exchanging link costs with neighbors).  The actual problem that it
>> solved was first raised by Ghulam Bhatti of Mitsubishi, if I
>> remember correctly.  Under certain circumstances having the two
>> ends of a link use different costs could cause ZigBee's P2P routing
>> to consistently fail to discover a route.  The problem was fairly
>> fundamental to ZigBee's P2P mechanism, and given the other
>> advantages of identifying asymmetries and knowing more about your
>> local neighborhood, ZigBee added a feature where nodes inform their
>> neighbors of their link costs.  This seems like something that
>> could be done at the link layer.
>> 
> 
> Yes.
> 
> JP.
> 
>> -Richard Kelsey
>> 
>> _______________________________________________ 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: Alexandru Petrescu <[email-masked]>
Date: Fri, 09 Oct 2009 19:53:45 +0200

Hi JP,

> have several metrics already defined, but still a few TBD.

Do you have a metric which says "energy needed to send a packet on an
interface"? I don't think you do. I think your draft briefly alludes
to energy cost of sending and receiving packets (presumably on a link),
but falls short in defining one as such.

To cite your draft:
> Raw power and energy values are meaningless without knowledge of the
>  energy cost of sending and receiving packets

Yet the table of contents says:
>    4.  Link Metrics and Attributes  . . . . . . . . . . . . . . . . .  8
>      4.1.  Throughput . . . . . . . . . . . . . . . . . . . . . . . .  8
>      4.2.  Latency  . . . . . . . . . . . . . . . . . . . . . . . . .  8
>      4.3.  Link reliability . . . . . . . . . . . . . . . . . . . . .  9
>      4.4.  Link Coloring  . . . . . . . . . . . . . . . . . . . . . .  9

Where is the link energy metric I am proposing and of which your draft
seems to be hinting at?

> Not sure why you refer to ICMP here but back to RPL ...

BEcause I think it would be good if a metric invented for one protocol
could be reused by another protocol.

>> These link metrics would express the energy needed to send a 
>> certain amount of bytes on a certain interface, or on a certain 
>> path.  The exression would be made in Joules, as single-precision 
>> 32bit floats, with two values: min and max.  Like this:
>> 
> 
> path that consumes the most energy is to the one that is preferable ?
> 
That's indeed tricky. I would let the definition of what is more
preferable to some intelligent logic depending on the programmer of the
context.

We could struggle to compare a path with high energy cost yet low
hopcount cost to a path with low energy cost yet high hopcount cost. Is
P1 preferable over P2 or vice-versa?

I think this is a question to which one can't answer without knowing the
deployment context.

It is exactly like the node's decision upon reception of a default route
RA from two different routers - this decision is not imposed by the
specifier, but by the specific context where this happens.

Yours,

Alex

> 
> 
> Thanks.
> 
> JP.
> 
>>> 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: TBA (see [ICMPv6parms]) Energy Metric Option for IPv6 
>>> Link. Length: Decimal 10. Reserved: Set to zero by sender and 
>>> ignored by receiver. Max Link Energy Single-precision 32bit 
>>> floating point number in binary interchange format (see 
>>> [IEEE754-2008] and [IEC60559-2.0]), a C 'float' type (see 
>>> [ISOIEC-C99]), and in network byte order. The value represents 
>>> the maximum energy, expressed in Joules, necessary to send a 
>>> packet of size 1280 bytes on this link. Min Link Energy 
>>> Single-precision floating point number representing the minimum 
>>> energy, expressed in Joules, necessary to send 1280 bytes on this
>>>  link.
>> 
>> Alex
>> 
>> 
> 
>

---

From: JP Vasseur <[email-masked]>
Date: Sat, 10 Oct 2009 08:23:27 +0200

Hi Alex,

> JP, that is your definition of what's needed and I respectfully  

How can you disagree without knowing what is needed ;-) (smiley).
There is a consensus that a reliability metric is needed (note that we  
are not limited to radio links).
Several metrics have been used for years such as ETX.

> PAcket delivery ratio is something which equals "best effort" i.e.  
> it has no number quantifying it.
>
>>> _______________________________________________ Roll mailing list [email-masked] 
>> _______________________________________________ Roll mailing list [email-masked]

---

From: JP Vasseur <[email-masked]>
Date: Sat, 10 Oct 2009 08:26:56 +0200

Hi Alex,

On Oct 9, 2009, at 7:53 PM, Alexandru Petrescu wrote:

>> Which metric should be defined for RPL (link and node). Note that  
>> we have several metrics already defined, but still a few TBD.
>

The draft has not been updated for quite some time, since we were  
waiting to progress first on RPL of course.
The next revision will be significantly fleshed out.

>>   4.  Link Metrics and  
>> Attributes  . . . . . . . . . . . . . . . . .  8
>>     4.1.   
>> Throughput . . . . . . . . . . . . . . . . . . . . . . . .  8
>>     4.2.   
>> Latency  . . . . . . . . . . . . . . . . . . . . . . . . .  8
>>     4.3.  Link  
>> reliability . . . . . . . . . . . . . . . . . . . . .  9
>>     4.4.  Link  
>> Coloring  . . . . . . . . . . . . . . . . . . . . . .  9
>

Ah ... why not, but this is not an objective.

>> Yes I do remember the discussion ... but I cannot see how this  
>> would be helpful. Indeed, even if a node receives two RA-DIO  
>> messages from parents that reports path-1 with energy G1 and path-2  
>> with energy G2 (we can discuss the packet format later on), in  
>> which way would that help in the path selection process? It might  
>> very well be that the path that consumes the most energy is to the  
>> one that is preferable ?

Well at least we need one example where it could be useful. I can't  
find of any personally.
What matters is how much of energy left you have, not how much of  
energy you may consume, no ?

Thanks.

JP.

>>>> 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 | +-+-+-+-+-+-+-+-+-+- 
>>>> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>>>> Type: TBA (see [ICMPv6parms]) Energy Metric Option for IPv6 Link.  
>>>> Length: Decimal 10. Reserved: Set to zero by sender and ignored  
>>>> by receiver. Max Link Energy Single-precision 32bit floating  
>>>> point number in binary interchange format (see [IEEE754-2008] and  
>>>> [IEC60559-2.0]), a C 'float' type (see [ISOIEC-C99]), and in  
>>>> network byte order. The value represents the maximum energy,  
>>>> expressed in Joules, necessary to send a packet of size 1280  
>>>> bytes on this link. Min Link Energy Single-precision floating  
>>>> point number representing the minimum energy, expressed in  
>>>> Joules, necessary to send 1280 bytes on this
>>>> link.
>>> Alex
>
>

---

From: JP Vasseur <[email-masked]>
Date: Sat, 10 Oct 2009 08:29:01 +0200

Hi Alex,

Thanks.

JP.

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 12 Oct 2009 12:39:02 +0200

Hi JP,

> The next revision will be significantly fleshed out.

I hope the results of this will be to continue to mention energy cost of 
at least sending packets.  And not to remove this text.

> Well at least we need one example where it could be useful. I can't find 
> of any personally.

Here is one:
                       --        --
                      |R1|      |R2|
                       --        --
                        |        |
                        |        |
                        |        |
                        |        |
                         \ ---- /
                          |Host|
                           ----

R1 and R2 send two different RAs.  Each pretends to be a default router 
(non-zero Router Lifetime) and send different "link energy metrics" to 
Host.  Host  has thus a choice between R1 and R2 based on that link 
energy metric.

What do you think about this use case?

> What matters is how much of energy left you have, not how much of energy 
> you may consume, no ?

In a sense yes, makes think of "node" energy metrics.

I think it is also importnat for the nodes to know in advance how much 
energy they need in order to send a packet on a certain link.

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 12 Oct 2009 12:56:43 +0200

JP Vasseur a écrit :
[...]
> There is a consensus that a reliability metric is needed (note that 
> we are not limited to radio links). Several metrics have been used 
> for years such as ETX.

I strongly disagree on using ETX.

ETX relies on probabilities ("a Bernoulli trial"), i.e. it is not as
hard data as hopcount is.

ETX does not relate directly to the energy consumed per packet.  It may
have a positive influence on it, but it does not depend on it.

ETX is unnecessarily complex due to taking into account the
re-transmissions, i.e. noisy environments.

ETX claims to be additive ("ETX of a route is the sum of ETX of each
link") but probabilities are not as additive (20% success rate on a link
and 30% success rate on another link don't make for 50% path success
rate, but for 30% success rate - the least common denominator).

I suggest using a link metric which is simply the energy quantity needed
to send an IP packet of size 1280 bytes, on a particular link, full
success rate.

Alex

Argumentation based on paper:
De Couto, Aguayo, Bicket and Morris, "A HighThroughput Path Metric for
MultiHop Wireless Routing", MIT CSAIL, ACM MobiCom '03, 2003.

>>> distance vector, we would use a cumulative metric. Of course, 
>>> each node should filter out the transient error rate and 
>>> periodicity of the metric update should be limited to avoid 
>>> routing metric but this not specific to the reliability metric. 
>>> It is true for all dynamic metrics. The objective is thus to 
>>> define a cumulative reliability metric reflecting the probability
>>>  of success path delivery, in units independent of the Link
>>> layer. Local mechanisms to filter out local transient phenomena
>>> are left to implementation specific decisions. Make sense ?
>>>> Our product was developed and deployed in 2006.  We used what 
>>>> is termed the 'ZigBee 2006 Stack'.  Since that time, ZigBee has
>>>>  developed the 'ZigBee PRO' stack which will in time subsume 
>>>> the ZigBee Stack.  ZigBee PRO selects paths based on the best 
>>>> symmetric path found.  I believe asymmetric paths are discarded
>>>>  or only used as a last resort. Not quite.  ZigBee PRO only 
>>>> requires that the cost assigned to an asymmetric link be the 
>>>> worse of the two unidirectional costs.
>>> Makes sense. We had a discussion on this too, and it was decided 
>>> not to take it into account for the time being.
>>>> metric.  Maybe Richard can provide some insight on this 
>>>> approach since I believe it was championed by Ember. Ember and 
>>>> Mitsubishi proposed the solution that was adopted (exchanging 
>>>> link costs with neighbors).  The actual problem that it solved 
>>>> was first raised by Ghulam Bhatti of Mitsubishi, if I remember 
>>>> correctly.  Under certain circumstances having the two ends of 
>>>> a link use different costs could cause ZigBee's P2P routing to 
>>>> consistently fail to discover a route.  The problem was fairly
>>>> advantages of identifying asymmetries and knowing more about 
>>>> your local neighborhood, ZigBee added a feature where nodes 
>>>> inform their neighbors of their link costs.  This seems like 
>>> Yes. JP.
>>>> -Richard Kelsey _______________________________________________
>>>>  Roll mailing list [email-masked]

---

From: JP Vasseur <[email-masked]>
Date: Mon, 12 Oct 2009 13:06:05 +0200

> rate, but for 30% success rate - the least common denominator).

Thanks for your input. Let's see what other say.
I personally like the ETX.

> to send an IP packet of size 1280 bytes, on a particular link, full

But not only the use of energy is very much arguable but it does not  
reflect the link
quality, a must in LLN. What would you prefer then for the quality  
metric ?

Thanks.

JP.

>>>>> ZigBee Stack.  ZigBee PRO selects paths based on the best  
>>>>> since I believe it was championed by Ember. Ember and Mitsubishi  
>>>>> proposed the solution that was adopted (exchanging link costs  
>>>>> with neighbors).  The actual problem that it solved was first  
>>>>> raised by Ghulam Bhatti of Mitsubishi, if I remember correctly.   
>>>>> Under certain circumstances having the two ends of a link use  
>>>>> different costs could cause ZigBee's P2P routing to consistently  
>>>>> fail to discover a route.  The problem was fairly
>>>>> Roll mailing list [email-masked] https://www.ietf.org/mailman/listinfo/roll

---

From: JP Vasseur <[email-masked]>
Date: Mon, 12 Oct 2009 13:45:44 +0200

>> I think both latency and reliability are important metrics.

We have a good consensus to have both latency and reliability. We now  
need to agree on the units.

Unit for latency ?

Unit for ETX (I propose to use the ETX): thoughts ?

>> constraint. They seem like local factors to me. If a node is  
>> running low on memory/CPU, it can simply not participate in routing.
>>
>>

Indeed, although we have planned to use an Overload bit since we may  
not want all nodes to trigger a DAG recomputation but only to not send  
traffic until the bit is cleared.

Cheers.

JP.

>>   As with throughput, the latency of many LLN MAC sub-layers can  
>> be    varied over many orders of magnitude, again with a  
>> corresponding    change in current consumption.  Some LLN MACs will  
>> allow the latency    to be adjusted globally on the subnet, or on a  
>> link-by-link basis, or    not at all.  Some will insist that it be  
>> fixed for a given link, but    allow it to be variable from link to  
>> link.  For efficient operation,    nodes must be able to report the  
>> range of latency that their links    can handle, and the currently  
>> available latency.
>>
>> 4.3.  Link reliability
>>
>>   In LLNs, link reliability is degraded by external interference  
>> and    multi-path interference.  Multipath typically affects both  
>> directions    on the link equally, whereas external interference is  
>> sometimes uni-    directional.  Time scales vary from milliseconds  
>> to days, and are    often periodic and linked to human activity.   
>> Packet error rate can    generally be measured directly, and other  
>> metrics (e.g. bit error    rate, mean time between failures) are  
>> typically derived from that.
>>
>> In addition:
>>
>> Node Memory resources:
>>
>> Node CPU resources: CPU duty cycle for virtually all LLN  
>> applications to date is well below 10%, and the trend in low power  
>> embedded systems is to more capable processors rather than less.  
>> Computational speed is not expected to be a limiting factor in  
>> routing in LLNs. Is there a need to report node CPU resources as a  
>> routing metric/constraint ?
>>
>> Link Security metrics
>>
>> JP, Mijeon, Kris. _______________________________________________
>> Roll mailing list
>> [email-masked]

---

From: JP Vasseur <[email-masked]>
Date: Mon, 12 Oct 2009 14:50:02 +0200

On Oct 9, 2009, at 5:05 PM, Jonathan Hui wrote:

> seems to have been that communication is "good" in one direction  
> while "bad" in the reverse.  Instead, I'd prefer to make a stronger  
> information about the links - meaning that the computed cost of  
> using the link in one direction is the same as in the reverse  
> direction.  Obviously, this is more natural in some metrics  
> (reliability, signal strength) than others (latency, energy).  But,  
> in my experience, relying on symmetric information when it is  
> natural to do so does simplify the routing problem.

on the other hand, if a link is indeed highly asymmetrical in term of  
reliability for example, wouldn't we want to look at the reliability  
metric in the direction of interest ?

By the way, what is your preference in term of units ?

Thanks.

JP.

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 12 Oct 2009 15:21:51 +0200

JP Vasseur a écrit :
>> JP Vasseur a écrit : [...]
>>> There is a consensus that a reliability metric is needed (note 
>>> that we are not limited to radio links). Several metrics have 
>>> been used for years such as ETX.
>> 
>> ETX relies on probabilities ("a Bernoulli trial"), i.e. it is not 
>> as hard data as hopcount is.
>> 
>> ETX does not relate directly to the energy consumed per packet.  It
>>  may have a positive influence on it, but it does not depend on it.
>> 
>> 
>> ETX claims to be additive ("ETX of a route is the sum of ETX of 
>> each link") but probabilities are not as additive (20% success rate
>>  on a link and 30% success rate on another link don't make for 50% 
>> path success rate, but for 30% success rate - the least common 
>> denominator).
>> 
> 
> Thanks for your input. Let's see what other say. I personally like 
> the ETX.
> 
>> I suggest using a link metric which is simply the energy quantity 
>> needed to send an IP packet of size 1280 bytes, on a particular 
>> link, full success rate.
> 
> But not only the use of energy is very much arguable

Arguable?

"Low power networks" in ROLL title is not about link energy?

> but it does not reflect the link quality, a must in LLN. What would
> you prefer then for the quality metric ?

I think a common link quality metric is impossible to define 
consensually, especially in case of heterogeneous links.

On the other hand, the energy Joules needed to send a fixed-size packet 
seems easier to grasp as a common metric.

Alex

---

From: JP Vasseur <[email-masked]>
Date: Mon, 12 Oct 2009 15:27:39 +0200

Hi Alex,

> [snip]

> R1 and R2 send two different RAs.  Each pretends to be a default  
> router (non-zero Router Lifetime) and send different "link energy  
> metrics" to Host.

Link energy relates to which link ?

> Host  has thus a choice between R1 and R2 based on that link energy  
> metric.
>
> I think it is also importnat for the nodes to know in advance how  
> much energy they need in order to send a packet on a certain link.
>
> Alex
>
>

---

From: JP Vasseur <[email-masked]>
Date: Mon, 12 Oct 2009 15:29:56 +0200

On Oct 12, 2009, at 3:21 PM, Alexandru Petrescu wrote:

>>> ETX is unnecessarily complex due to taking into account the re- 
>>> transmissions, i.e. noisy environments.

But the objective of the RPL is to provide you the best path according  
to some metrics.
I may have a path requiring more energy than another one but if it  
goes across main powered nodes, this may be the preferable path.
Node energy is different and covered in the ID.

> On the other hand, the energy Joules needed to send a fixed-size  
> packet seems easier to grasp as a common metric.

But they are completely different metrics !

JP.

---

From: JP Vasseur <[email-masked]>
Date: Mon, 12 Oct 2009 15:31:56 +0200

Hi Alex,

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 12 Oct 2009 16:00:19 +0200

> Link energy relates to which link ?

Link energy metric in RA relates to the link on which that RA is sent. 
One RA is typically sent on a single link.

In the above figure there are two links.

Is this ok?

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 12 Oct 2009 16:04:13 +0200

JP Vasseur a écrit :
>>>> link") but probabilities are not as additive (20% success rate

Yes.

> I may have a path requiring more energy than another one but if it goes 
> across main powered nodes, this may be the preferable path.

I agree.  The same argument applies to a potentially  newly defined 
"link quality" metric and wired links substituting for the mains-powered 
node.

I.e.: I may have a path requiring less quality than another one but if 
it goes across wired links, this may be the preferable path.

> But they are completely different metrics !

I agree: link-energy metrics and link-quality metrics are different.

Would it hurt if both were discussed and included in the draft?

Alex

---

From: JP Vasseur <[email-masked]>
Date: Mon, 12 Oct 2009 16:05:45 +0200

On Oct 12, 2009, at 4:04 PM, Alexandru Petrescu wrote:

>>>>> ETX relies on probabilities ("a Bernoulli trial"), i.e. it is  
>>>>> not as hard data as hopcount is.
>>>>> on a link and 30% success rate on another link don't make for  
>>>>> 50% path success rate, but for 30% success rate - the least  
>>>>> common denominator).
>>>> Thanks for your input. Let's see what other say. I personally  
>>>> like the ETX.
>>>>> I suggest using a link metric which is simply the energy  
>>>>> quantity needed to send an IP packet of size 1280 bytes, on a  
>>>>> particular link, full success rate.
>> But the objective of the RPL is to provide you the best path  
>> according to some metrics.
>
> Yes.
>
> "link quality" metric and wired links substituting for the mains- 
> powered node.
>
> I.e.: I may have a path requiring less quality than another one but  
> if it goes across wired links, this may be the preferable path.
>

Not at all. As a matter of fact we will have more than one. The  
question is whether one can make use of the link energy metric.

Thanks.

JP.

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 12 Oct 2009 16:08:03 +0200

JP Vasseur a écrit :
>> "link quality" metric and wired links substituting for the 
>> mains-powered node.
>>
> Not at all. As a matter of fact we will have more than one. The question 
> is whether one can make use of the link energy metric.

That is a good question deserving discussion: how to make use of a 
link-energy metric.

Alex

---

From: Maxence Dalmais <[email-masked]>
Date: Mon, 12 Oct 2009 15:57:20 +0200

Hi JP,

>>
>>
> But the objective of the RPL is to provide you the best path according to
> some metrics.

I agree with you, but maybe something is missing:
Title is too about lossy network. Loss in wireless network is due to noise.
Sure one could argue that noise is a layer 2 (not 3) problem but that
argumentation won't make RPL better.
The fact is that sending a high energy cost packet won't be a problem for a
mains powered node, but it will induce noise and impact the links of the
entire network.

Maxence.

---

From: JP Vasseur <[email-masked]>
Date: Mon, 12 Oct 2009 16:12:18 +0200

Hi Maxence,

On Oct 12, 2009, at 3:57 PM, Maxence Dalmais wrote:

> Title is too about lossy network. Loss in wireless network is due to  
> noise. Sure one could argue that noise is a layer 2 (not 3) problem  
> but that argumentation won't make RPL better.

Indeed. Note that "lossy" also applies to PLC links but we're in sync.

> The fact is that sending a high energy cost packet won't be a  
> problem for a mains powered node, but it will induce noise and  
> impact the links of the entire network.

That is a second order effect though and not true for PLC link. It is  
bit of a stretch to choose a low energy path, because of a high energy  
path may cause increase noise along that path thus leading to more  
errors ... don't you think ?

Thanks.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Mon, 12 Oct 2009 16:18:18 +0200

Hi Maxence,

Thanks.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Mon, 12 Oct 2009 16:20:18 +0200

Hi Maxence,

Thanks.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Mon, 12 Oct 2009 16:14:24 +0200

On Oct 12, 2009, at 4:00 PM, Alexandru Petrescu wrote:

>>>> Well at least we need one example where it could be useful. I  
>>>> can't find of any personally.
>>>
>>> Here is one:
>>>                    --        --
>>>                   |R1|      |R2|
>>>                    --        --
>>>                     |        |
>>>                     |        |
>>>                     |        |
>>>                     |        |
>>>                      \ ---- /
>>>                       |Host|
>>>                        ----
>>>
> Link energy metric in RA relates to the link on which that RA is  
> sent. One RA is typically sent on a single link.
>

Yes but how would you expect "host" to use that information to select  
the router ?
It may very well be that the router offering the lower energy cost end  
up following a high energy path.

---

From: JP Vasseur <[email-masked]>
Date: Mon, 12 Oct 2009 16:16:25 +0200

---

From: Maxence Dalmais <[email-masked]>
Date: Tue, 13 Oct 2009 00:09:15 +0200

Hi JP,

>>
>> The fact is that sending a high energy cost packet won't be a problem for
>> a mains powered node, but it will induce noise and impact the links of the
>> entire network.
>>
>> That is a second order effect though and not true for PLC link. It is bit
>> of a stretch to choose a low energy path, because of a high energy path may
>> cause increase noise along that path thus leading to more errors ... don't
>> you think ?
>>
>>
>> Personnaly I don't think.
>>
>> Using high energy path will include more errors to others transmissions,
>> ie increase retransmissions, ie increase the ETX metric. This may involve
>> modifications in the chosen path.
>>
>
> you are basically saying that we should not use high energy links ....
>
>
I am saying that when using wireless links, a node should be aware that his
communication could interfere with other communication.
Less powered is the transmission signal, less noise is seen by neighbours.
A low powered node will also need less energy to communicate in a less noisy
environnement.

So, it appears to me logical that when others metrics are egals to choose
the less power needed links.

As said somewhere else, the final metric should be a computation of
different metrics.
I think that including the energy cost in the computation could be a little
great idea.

 Yes but how would you expect "host" to use that information to select the
> router ?
> It may very well be that the router offering the lower energy cost end up
> following a high energy path.
>
[In [Roll] RPL Metric I-D from JP Vasseur to Alexandru Petrescu about link
energy information in RA ]

That means that we need end-to-end energy-cost metric to balance the route.
Maybe we need 2. The first being a sum of product of the power consumption
to send the packet with the needs to save energy (ie the mains powered nodes
won't be include having a nul needs to save energy).
End-2-End Energy Cost Metric = sum for i in 0 to path_length :
powerConsumption (i,i+1) * savingEnergyNeeds(i)

The second one is more subject to discussion. Experimentation results of
such an idea could help to make a choice.
The idea is to get a representation for the inconvenience to other nodes to
transmit a packet on the specific link.
This is very different from the classical best effort, but maybe one of the
first think to do to improve quality in Lossy wireless Network is to reduce
the perceived noise.

Here is my point of view,

Maxence.

HI Maxence,
>
>
> On Oct 12, 2009, at 5:00 PM, Maxence Dalmais wrote:
>
>  Hi JP,
>>
>>
>> The fact is that sending a high energy cost packet won't be a problem for
>> a mains powered node, but it will induce noise and impact the links of the
>> entire network.
>>
>> That is a second order effect though and not true for PLC link. It is bit
>> of a stretch to choose a low energy path, because of a high energy path may
>> cause increase noise along that path thus leading to more errors ... don't
>> you think ?
>>
>>
>> Personnaly I don't think.
>>
>> Using high energy path will include more errors to others transmissions,
>> ie increase retransmissions, ie increase the ETX metric. This may involve
>> modifications in the chosen path.
>>
>
> you are basically saying that we should not use high energy links ....
>
>
>  Maybe we could think that we don't need to take energy path into account
>> the  because ETX will automatically adapt to this.
>>
>
> that is the aim of using ETX
>
>
>  But having a highly dynamic ETX may cause others trouble, don't you think
>>  ?
>>
>
> of course, this is true for ALL dynamic metrics.
>
>
>  Maybe, energy path has to be taken in count in RPL to avoid the need of a
>> very dynamic ETX and retransmissions.
>>
>> I think that when designing a new specialized protocol, we shouldn't be
>> affraid of developing new idea.
>>
>>
> we're not afraid ;-) but we learned from experience (look at the dynamic
> metric of ARPANET 2).
> - Hide quoted text -
>
>
> Does anyone have experience with such an altruistic routing protocol ?
>
> Cheers,
>
> Maxence.
>

---

From: Alexandru Petrescu <[email-masked]>
Date: Tue, 13 Oct 2009 00:57:07 +0200

> Yes but how would you expect "host" to use that information to select 

By using some local intelligence knobs.  If the knobs are up saying "use 
the default router on the link involving the least energy consumption" 
then do so.

Yes.

But in very many cases the end node can't choose paths based on any 
parameter, not only energy (well, except RSVP).

The notion of 'default' router itself is such.  When the host receives 
an RA from a router pretending to be a default router there is no 
guarantee for the host that that router offers a shortest path to a 
certain destination (IP hopcount metric).

My PDA with a 3G and a WiFi interface: I have no idea which offers the 
shortest path to gmail.com.  I just pick the interface which is sure to 
lead to the Internet.  If I need an interface to a link which consumes 
less then I pick the interface which has just received an RA telling it 
how little it is supposed to consume.

Same with MTU: when host reads an RA telling it the MTU is 1280 it has 
no guarantee that the entire path is 1280 - often the intermediary links 
to the final destination offer larger-than-1280 MTU, typically the 
backhaul links.

Thus I propose to have the same kind of behaviour for the energy metric 
for link in RA, as we have for default routers and with MTU.

Later we can see about link energy metric for routing protocols. (as 
Path MTU Discovery is for MTU of paths).

Alex

---

From: JP Vasseur <[email-masked]>
Date: Tue, 13 Oct 2009 04:48:34 +0200

Hi Maxence,

On Oct 13, 2009, at 12:09 AM, Maxence Dalmais wrote:

> That is a second order effect though and not true for PLC link. It  
> is bit of a stretch to choose a low energy path, because of a high  
> energy path may cause increase noise along that path thus leading to  
> more errors ... don't you think ?
>
>
> Using high energy path will include more errors to others  
> transmissions, ie increase retransmissions, ie increase the ETX  
> metric. This may involve modifications in the chosen path.
>
> I am saying that when using wireless links, a node should be aware  
> that his communication could interfere with other communication.
> A low powered node will also need less energy to communicate in a  
> less noisy environnement.
>

Bear in mind, that you do not know this environment so this may lead  
you to an incorrect conclusion.
The real metric is the link reliability, which reflect the properties  
of the environment.

Furthermore, this does not apply to PLC links.

> So, it appears to me logical that when others metrics are egals to  
> choose the less power needed links.
>

This is the objective function.

JP.

> I think that including the energy cost in the computation could be a  
> little great idea.
>
>
> Yes but how would you expect "host" to use that information to  
> select the router ?
> It may very well be that the router offering the lower energy cost  
> end up following a high energy path.
> [In [Roll] RPL Metric I-D from JP Vasseur to Alexandru Petrescu  
> about link energy information in RA ]
>
> Maybe we need 2. The first being a sum of product of the power  
> consumption to send the packet with the needs to save energy (ie the  
> mains powered nodes won't be include having a nul needs to save  
> energy).
> The second one is more subject to discussion. Experimentation  
> results of such an idea could help to make a choice.
> The idea is to get a representation for the inconvenience to other  
> nodes to transmit a packet on the specific link.
> This is very different from the classical best effort, but maybe one  
> of the first think to do to improve quality in Lossy wireless  
> Network is to reduce the perceived noise.
>
> That is a second order effect though and not true for PLC link. It  
> is bit of a stretch to choose a low energy path, because of a high  
> energy path may cause increase noise along that path thus leading to  
> more errors ... don't you think ?
>
>
> Using high energy path will include more errors to others  
> transmissions, ie increase retransmissions, ie increase the ETX  
> metric. This may involve modifications in the chosen path.
>
> Maybe we could think that we don't need to take energy path into  
> account the  because ETX will automatically adapt to this.
>
> But having a highly dynamic ETX may cause others trouble, don't you  
> think  ?
>
> Maybe, energy path has to be taken in count in RPL to avoid the need  
> of a very dynamic ETX and retransmissions.
>
> I think that when designing a new specialized protocol, we shouldn't  
> be affraid of developing new idea.
>
>
> we're not afraid ;-) but we learned from experience (look at the  
> dynamic metric of ARPANET 2).
> - Hide quoted text -
>
>

---

From: Henning Rogge <[email-masked]>
Date: Tue, 13 Oct 2009 10:11:05 +0200

> The real metric is the link reliability, which reflect the properties
We have a similar discussion about metrics in the Manet-WG. Different kind of 
metrics seem to be useful in different enviroments. Signal strength seem to be 
a good indicator for a "bad" link, but in praxis (especially with incorrect 
signal strengt estimation of consumer hardware) sometimes links with low 
signal strength are better than others with higher signal strength. On the 
other side ETX might be easy to implement on any kind of layer-2 hardware, but 
is only a rough estimation of the "link quality" which does not consider long 
time link statistics (stability, variance, ...) or transmission speed.

Metrics for wireless networks are still being researched without "final 
perfect metric" in sight, so ROLL should keep metric IDs for futher metric 
types. But you should put at least ONE easy to implement metric into the basic 
WG document. The problem of OLSRv1 (as an example) was that it did NOT include 
any metric except hopcount in it's basic document, so most people using OLSR 
for their projects (who do NOT research metrics for mesh networks) just use 
hopcount metrics and think that OLSR does not work.

So the question about a metric for ROLL should not only be "what's the best 
metric for our networks" but "what metric is simple enough that everyone can 
implement it on any kind of hardware".

> This is the objective function.
Yes, a good metric "post processing" (including long term statistical analysis 
of a links different metrics) can be a good thing to enhance the quality of 
the "link cost" estimation.

Henning Rogge

---

From: "Anders Brandt" <[email-masked]>
Date: Tue, 13 Oct 2009 11:12:09 +0200

>> I think both latency and reliability are important metrics.

Same for me.

One word of warning on the energy discussion:
It seems like the assumption is that the routing protocol should manage
the number of transmitted packets in order to ensure that the energy
consumption is distributed among more nodes.

There is however a caveat here:
>From our experience, a radio uses energy. Period.
Receiving uses the same as transmitting - the difference is just which
amplifiers use the energy.
Thus, the way to use less energy is to use the radio less - i.e. sleep
some of the time. Which again translates into higher latency to reach
such nodes. Obviously, there is something to save, since a radio may
quickly determine if it is the intended recipient of a packet and return
to sleep again OR receive the entire packet and stay awake to forward
the packet on to another node in the network.

Thus, what I am trying to say is:
Unless the lower layers have a smart way of quickly returning to sleep
(which some technologies have) the routing protocol will keep all nodes
awake within direct range - and they will all use power for listening =>
nothing gained from distributing the traffic.
Can battery-powered 802.15.4. nodes quickly return to sleep if they are
not the intended recipient?
If not, the energy metric may be rather useless (?)

Cheers,
  Anders

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
JP Vasseur
Sent: 12. oktober 2009 13:46
To: Tim Winter
Cc: [email-masked]
Subject: Re: [Roll] RPL Metric ID

Unit for latency ?

> Exposing an exaggerated rank might also be an option.

Indeed, although we have planned to use an Overload bit since we may not
want all nodes to trigger a DAG recomputation but only to not send
traffic until the bit is cleared.

Cheers.

JP.

>> Is there a need to report node memory resources as a routing 
>> metric/constraint ?
>>
>> Node CPU resources: CPU duty cycle for virtually all LLN applications

>> to date is well below 10%, and the trend in low power embedded 
>> systems is to more capable processors rather than less.

---

From: "Anders Brandt" <[email-masked]>
Date: Tue, 13 Oct 2009 12:22:09 +0200

Henning Rogge wrote:

>... So the question about a metric for ROLL should not only be "what's
the best metric for our networks" but
>"what metric is simple enough that everyone can implement it on any
kind of hardware". 

Good pragmatic approach to reality.

>... On the other side ETX might be easy to implement on any kind of
layer-2 hardware, but is only a rough
>estimation of the "link quality" which does not consider long time link
statistics (stability, variance, ...)
>or transmission speed.

I have seen other people on this thread indicating that RSSI
measurements tell a rather polluted truth.
This is also our experience.
Translated to the real world, ETX information based on the number of
received Acks from lower layers is a cheap and often sufficient metric.

ETX actually could be a good candidate for a default metric working
_FAIRLY_GOOD_ in most environments on most hardware platforms.

- Anders

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Henning Rogge
Sent: 13. oktober 2009 10:11
To: [email-masked]
Subject: Re: [Roll] ETX metric

> The real metric is the link reliability, which reflect the properties 
We have a similar discussion about metrics in the Manet-WG. Different
kind of metrics seem to be useful in different enviroments. Signal
strength seem to be a good indicator for a "bad" link, but in praxis
(especially with incorrect signal strengt estimation of consumer
hardware) sometimes links with low signal strength are better than
others with higher signal strength. On the other side ETX might be easy
to implement on any kind of layer-2 hardware, but is only a rough
estimation of the "link quality" which does not consider long time link
statistics (stability, variance, ...) or transmission speed.

Metrics for wireless networks are still being researched without "final
perfect metric" in sight, so ROLL should keep metric IDs for futher
metric types. But you should put at least ONE easy to implement metric
into the basic WG document. The problem of OLSRv1 (as an example) was
that it did NOT include any metric except hopcount in it's basic
document, so most people using OLSR for their projects (who do NOT
research metrics for mesh networks) just use hopcount metrics and think
that OLSR does not work.

So the question about a metric for ROLL should not only be "what's the
best metric for our networks" but "what metric is simple enough that
everyone can implement it on any kind of hardware".

> This is the objective function.
Yes, a good metric "post processing" (including long term statistical
analysis of a links different metrics) can be a good thing to enhance
the quality of the "link cost" estimation.

Henning Rogge

---

From: Adam Dunkels <[email-masked]>
Date: Tue, 13 Oct 2009 12:39:43 +0200

> not the intended recipient?

Some can, but the biggest energy savings is in mechanisms that keep the 
radio off for most of the time, and switch it on to listen for traffic 
from neighbors. These mechanisms are typically layered on top of 
802.15.4, although I believe there is ongoing work in the 802.15.4 wg to 
put such mechanisms into the standard. There are several techniques to 
do this, and the most common is called low-power listening (LPL) in 
which nodes turn on their radio at regular intervals to listen for a 
packet in the air. If there is a packet in the air (and it is addressed 
to the node), it switches on the radio for a longer time to receive the 
packet. Before sending a packet, a sender sends a preamble (typically a 
string of packets) to wake up the receiver.

Thus with such mechanisms there is an energy penalty for packet 
transmissions, but the energy is spent both by the sender and the receiver.

/adamn
-- 
Adam Dunkels <[email-masked]>, +46707731614
http://twitter.com/adunk | http://www.sics.se/~adam/

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 13 Oct 2009 08:23:17 -0400

Date: Tue, 13 Oct 2009 12:22:09 +0200
   From: "Anders Brandt" <[email-masked]>

   Henning Rogge wrote:

   > ... On the other side ETX might be easy to implement on any kind
   > of layer-2 hardware, but is only a rough estimation of the "link
   > quality" which does not consider long time link statistics
   > (stability, variance, ...)  or transmission speed.

   I have seen other people on this thread indicating that RSSI
   measurements tell a rather polluted truth.  This is also our
   experience.

I agree with you about raw RSSI.  On the other hand,
combining raw RSSI with sampled noise measurement to get a
measured SNR (or SINR) does much better.  It gives some idea
of the margin available on the link.
   
   Translated to the real world, ETX information based on
   the number of received Acks from lower layers is a cheap
   and often sufficient metric.

I and at least some others have not found this to work well
for 802.15.4, in that ETX isn't stable enough to be a good
predictor except in the very short term.  I am aware that
there disagreement on this :-).

                        -Richard Kelsey

---

From: Henning Rogge <[email-masked]>
Date: Tue, 13 Oct 2009 14:44:55 +0200

> there disagreement on this :-).
My experience comes from 802.11, so we have more range compared to 802.15.4.
If all 802.15.4 implementations have a good RSSI and noise/interference level 
measurement, this might be the better default metric for ROLL.

802.11 implementations sometimes have a poor, ugly or non-existant RSSI 
measurement, and noise/interference level measurement is worse. That's why I 
would not suggest signal-strength/SNIR based metrics for WLAN. I'm not sure 
how well 802.15.4 do the necessary measurements.

Henning

---

From: JP Vasseur <[email-masked]>
Date: Tue, 13 Oct 2009 15:33:35 +0200

Hi Henning,

On Oct 13, 2009, at 10:11 AM, Henning Rogge wrote:

> metric
> types.

Adding metric will not be an issue, just a new codepoint. What you  
said, what we need is
a "good" enough mono-dimensional reliability metric to start with.

> But you should put at least ONE easy to implement metric into the  
> basic
> WG document.
> The problem of OLSRv1 (as an example) was that it did NOT include

I fully agree with your approach.

Yes, what we have done so far (in the new revision to be posted) is to  
define one mandatory
metric (hop count) and have all other ones optional. May be "hop  
count" is one the one that
we will keep as mandatory but the spirit is to have a set of metrics  
people can decide to use
based on the OF.

We still need to define the one reliability metric that we will be  
using.

> the "link cost" estimation.

Thanks for the useful feed-back.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Tue, 13 Oct 2009 15:34:26 +0200

> _FAIRLY_GOOD_ in most environments on most hardware platforms.

Thanks for the feed-back. That is also my feeling.

---

From: JP Vasseur <[email-masked]>
Date: Tue, 13 Oct 2009 15:35:40 +0200

Hi Henning,

JP.

---

From: Henning Rogge <[email-masked]>
Date: Tue, 13 Oct 2009 15:53:43 +0200

Am Dienstag 13 Oktober 2009 15:35:40 schrieb JP Vasseur:
> > So the question about a metric for ROLL should not only be "what's
> > the best metric for our networks" but "what metric is simple enough that
> define one mandatory metric (hop count) and have all other ones optional.
> May be "hop count" is one the one that we will keep as mandatory but the
> spirit is to have a set of metrics people can decide to use based on the OF.

OLSRv1 did the same way and it shaped the conclusion "OLSR is crap" or "OLSR 
does not work" in huge parts of the industry. Hop count metrics can be called 
"use worst link" metrics for wireless networks, because it tries to optimize 
for the LONGEST links possible, which will be (most likely) worst links your 
network knows.

With OLSR and 802.11 you can summarize it "Hopcount does not work in real 
networks outside the lab". There are some special cases how you can improve 
hopcount, but most times you will still get a poor performance and your 
protocol will be blamed.

Unless 802.15.4 is totally different (I don't think so) I would strongly 
suggest thinking about something better than hopcount for your mandatory 
metric. At least that's the message I can tell from OLSR.

Henning Rogge

-- Those who cannot learn from history are doomed to repeat it.

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 13 Oct 2009 18:01:41 +0200

Hi Henning.

Good to hear from you :)

We also called that syndrome the 'Worst Path First'. I think the name
was introduced by Teco quite a long time ago.

The trick to make it work outside the Lab is to filter out any packet
that does not have metrics like RSSI above a quality threshold and
blacklist peers that show a poor history. Like a WIFI AP that does not
associate or drops association with nodes under a certain signal
strength.

RPL requires an abstract peer link evaluation though it does not say how
that is done and it has the hold down feature.

I got good results with an emulation of LMI's N392/N393 that computes a
loss ratio. But there must be a great many other strategies so that
least each hop is rated 'good enough' and the network is not stretched
too far. I'm unsure whether we should specify how that's done, since it
might be L2 dependent. And even if one can alleviate the WPF syndrome,
the end result is that paths cannot be compared for their end to end
metric thus are not optimized.
 
RPL is a bit more subtle than meet the eye from JP's summarized
description. It provides a default increment per hop (4), but the node
can play around that increment to reflect the quality of the link
(1..16). So we can advertise something that's a lot closer to the link's
quality and thus optimize something that's dependent on the objective.

OCP0 (the arch default) increments by 4 so it really relies on the link
evaluation. Maybe we could allow to play around the 4 value within the
1..16 range but then we cannot really specify how that is done since
that sort of thing is left to the metrics draft.

Cheers,

Pascal

Henning Rogge
>Sent: mardi 13 octobre 2009 15:54
>To: JP Vasseur (jvasseur)
>Cc: [email-masked]
>> > the best metric for our networks" but "what metric is simple enough
>> > that everyone can implement it on any kind of hardware".
>>
>> May be "hop count" is one the one that we will keep as mandatory but
>> the spirit is to have a set of metrics people can decide to use based
on the OF.
>
>OLSRv1 did the same way and it shaped the conclusion "OLSR is crap" or
"OLSR does not work" in huge parts of
>the industry. Hop count metrics can be called "use worst link" metrics
for wireless networks, because it tries
>to optimize for the LONGEST links possible, which will be (most likely)
worst links your network knows.
>
>With OLSR and 802.11 you can summarize it "Hopcount does not work in
real networks outside the lab". There are
>some special cases how you can improve hopcount, but most times you
will still get a poor performance and your
>protocol will be blamed.
>
>Unless 802.15.4 is totally different (I don't think so) I would
strongly suggest thinking about something
>better than hopcount for your mandatory metric. At least that's the
message I can tell from OLSR.

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 13 Oct 2009 12:02:35 -0400

From: Henning Rogge <[email-masked]>
   Date: Tue, 13 Oct 2009 15:53:43 +0200

   > spirit is to have a set of metrics people can decide to use based on the OF.

   OLSRv1 did the same way and it shaped the conclusion "OLSR is crap"
   or "OLSR does not work" in huge parts of the industry. Hop count
   metrics can be called "use worst link" metrics for wireless
   networks, because it tries to optimize for the LONGEST links
   possible, which will be (most likely) worst links your network
   knows.

   With OLSR and 802.11 you can summarize it "Hopcount does not work
   in real networks outside the lab". There are some special cases how
   you can improve hopcount, but most times you will still get a poor
   performance and your protocol will be blamed.

   Unless 802.15.4 is totally different (I don't think so) I would
   strongly suggest thinking about something better than hopcount for
   your mandatory metric. At least that's the message I can tell from
   OLSR.

   Those who cannot learn from history are doomed to repeat it.

We have to be careful not to learn the wrong lesson.
Hopcount without careful link assessment definitely doesn't
work.  Hopcount limited to stable, symmetric links is a
different beast entirely.  For example, consider the Cost/PL
column in table 1 of [1], which gives the average
transmissions per link.  For most of the networks it is very
close to 1 and it never goes above 2.  That's puts ETX
pretty close to hopcount for those networks, if routing is
limited to links with good ETX.

So let me propose a reliability metric with two hopcounts,
one for 'good' links and the other for 'okay' ones.  To make
it more concrete:

  'Good' links have a current ETX < 1.5 and are expected to
  stay working throughout a maximum RA-DIO interval (which I
  think is given by 2^(DIOIntervalMin +  DIOIntervalDoublings))
  99% of the time.

  'Okay' links have an ETX < 3.0 and are expected to be
  working throughout a maximum RA-DIO interval 80% of the time.

When comparing, five 'good' hops would be equivalent of one
'okay' one.

I pulled the numbers (1.5, 99%, 3.0, 80% and five) out of
thin air.  Real values would have to be chosen with care.

                               -Richard Kelsey

[1] Omprakash Gnawali, Rodrigo Fonseca, Kyle Jamieson, David
Moss, and Philip Levis "Collection Tree Protocol." Technical
Report SING-09-01

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 13 Oct 2009 09:09:58 -0700

> the packet on to another node in the network.

You're right.  There is a fundamental tradeoff between energy  
consumption vs. expected communication latency and/or throughput when  
using a particular radio technology.

> If not, the energy metric may be rather useless (?)

Specific to 802.15.4, it is possible to enable/disable the receiver  
with a period on the order of a couple hundred milliseconds and  
achieve an effective duty-cycle of far less than 1%.  The link simply  
appears as if it has lower throughput.  Expected latency will increase  
proportionally, but the particular factors depends on whether or not  
you can coordinate the duty-cycle schedules to match the routes (or  
vice versa).

In any case, 802.15.4e is working on incorporating at least two duty- 
cycling techniques.  The first is a channel-sampling approach that  
utilizes short chirp packets in the general case but incorporates  
scheduling to reduce transmission overhead.  You can find details of  
the approach being used in Chapter 4 of [1].  The second is a time- 
slotted approach where nodes have to synchronize schedules with their  
neighbors before they can communicate with them.  In both cases, the  
net effect is that they make the link appear as if it is up all the  
time, just with lower throughput and higher latency.  The challenge  
with respect to energy is that they shift energy costs in different  
ways.

[1] http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-116.pdf

--
Jonathan Hui

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 13 Oct 2009 09:45:56 -0700

> limited to links with good ETX.

I agree.  The challenge is that we really do want to minimize the  
number of transmissions to reach the destination, modulo details that  
are specific to the link protocol.  Simple hop count didn't work  
because of the tension between wanting to only use only 'good' links,  
but also utilizing 'okay' links, or even 'bad' links when necessary to  
keep the network connected an functioning.

>  working throughout a maximum RA-DIO interval 80% of the time.

As I mentioned before, I do think the distinction of 'good' and 'okay'  
links is a useful one, and I like that it distills information into  
simple concepts.  In general, a number of parameters (ETX, RSSI, SNR,  
SINR, chip correlation) will be used to discern between 'good',  
'okay', and 'bad' links.  What parameters may be used depends on the  
particular hardware/software capabilities of each node.  How those  
parameters are computed depends on the particular implementation as  
well (sampling methods, time scales, etc).  I'm not convinced that ETX  
as defined should be THE reliability metric simply because it's not  
good at discerning between 'good' and 'okay' links, but I am convinced  
that it is a useful input.

> thin air.  Real values would have to be chosen with care.

And these numbers will be, like it or not, dependent on the properties  
of the particular radio hardware, link protocols, software  
implementation, etc.  Better to give some general guidelines of what a  
'good' vs. 'okay' vs. 'bad' link is and guide implementations best we  
can.

--
Jonathan Hui

---

From: JP Vasseur <[email-masked]>
Date: Wed, 14 Oct 2009 12:53:01 -0700

Hi,

> consumption is distributed among more nodes.

that would be the objective by using node energy level, which may be  
useful
for SOME networks (not all for sure).

> If not, the energy metric may be rather useless (?)

I saw Adam answered already.

JP.

> not
>>> nodes.
>>> applications

---

From: Philip Levis <[email-masked]>
Date: Wed, 14 Oct 2009 21:30:02 -0700

> Less powered is the transmission signal, less noise is seen by  

It also means that it's more greatly affected by interference from  
neighbors: there is no free lunch.

> less noisy environnement.

In low-power wireless chipsets, CMOS dominates power costs. E.g., a  
chip that draws 60mW transmits at 1mW. Reducing transmit power  
typically does not conserve much energy.

> choose the less power needed links.

I don't know of any strong experimental evidence supporting this  
conclusion. Can you point me at some?

Phil

---

From: Philip Levis <[email-masked]>
Date: Wed, 14 Oct 2009 21:31:34 -0700

On Oct 13, 2009, at 1:11 AM, Henning Rogge wrote:

> the best

I agree. Well put! :)

Phil

---

From: Philip Levis <[email-masked]>
Date: Wed, 14 Oct 2009 21:33:41 -0700

On Oct 13, 2009, at 6:53 AM, Henning Rogge wrote:

> strongly

I agree -- hopcount is a non-starter. It is only useful if you can  
filter links based on a more expressive quality metric (ETX, etc.);  
but since you require such a metric, it's better to use it than a  
filtered proxy.

Phil

---

From: Philip Levis <[email-masked]>
Date: Wed, 14 Oct 2009 21:49:10 -0700

I think we should keep in mind that RPL must work across multiple link  
layers. E.g.:

A -- 900MHz --> B -- 2.4GHz --> C

ETX is a commonly used metric, but typically under two simplifying  
assumptions:

1) Routes are composed of a single link layer
2) The link layer has a static bitrate

If you break either assumption, it doesn't work well. ETT (expected  
time of transmission) can address 2), but not 1).

I'm wary of encoding a metric as a hard quantity. For example,  
quantifying the metric as uJ breaks when nodes have differential  
energy capacities. What we really want is a more abstract notion of  
cost, which a particular device can use to, in a very simple way,  
express its own tradeoffs. It is critical that exactly how devices  
calculate this value remain unspecified.

My first thought would be a quantification of how much of a node's  
"lifetime" a packet would cost. Such a cost can consider both the  
receiver and transmitter. E.g., given its particular low power  
algorithms and expected lifetime, how much would sending to this  
destination consume? (I try to avoid using the word "link.")

I don't think that a single metric will be sufficient; besides some  
notion of cost (hopcount, ETX, ETT, etc.), the other metric that is  
critical in many applications is latency. These two -- cost and  
latency -- can cover a large portion of the application design space,  
and provide a sound basis for the basic specification.

Thoughts?

Phil

---

From: Maxence Dalmais <[email-masked]>
Date: Thu, 15 Oct 2009 10:53:56 +0200

Hi Phil ,

> neighbors: there is no free lunch.

Could you please be more clear?
I'm not sure I understand quite well.

>
>  A low powered node will also need less energy to communicate in a less
>> noisy environnement.
>>
>
> In low-power wireless chipsets, CMOS dominates power costs. E.g., a chip
> that draws 60mW transmits at 1mW. Reducing transmit power typically does not
> conserve much energy.
>

Thank you for this information.
But keep this assumption as it assumes that hardware will not evolve in
coming years.

I totally aggre with you to say that we need an abstract notion of cost.
But I think that we can not consider only the receiver and transmitter but
that we have to consider all the nodes on which the transmission has an
(good or bad) effect. Sure, there will be a huge difference between wireless
and wired links.

A good effect of a high powered transmission from a main node to another
node could be seen if some nodes are using ambient radio radiation to stay
up.
For each nodes, the cost will be different depending if the node is involved
in the transmission in receiving, routing, or not directly involved but in
being affected by it.

Maxence.

---

From: JP Vasseur <[email-masked]>
Date: Thu, 15 Oct 2009 06:22:10 -0700

On Oct 14, 2009, at 9:49 PM, Philip Levis wrote:

> I think we should keep in mind that RPL must work across multiple  
> link layers. E.g.:
>

Not sure I would agree on this statement though. Being based on  
probing it's not link layer dependent.

> destination consume? (I try to avoid using the word "link.")

Ah you're moving to a different subject (still important) energy, that  
will be addressed in the draft.

> latency -- can cover a large portion of the application design  
> space, and provide a sound basis for the basic specification.

Also covered. Stay tuned.

---

From: JP Vasseur <[email-masked]>
Date: Thu, 15 Oct 2009 06:23:10 -0700

> typically does not conserve much energy.

I have the same data.

> conclusion. Can you point me at some?

And same conclusion.

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 15 Oct 2009 10:26:50 -0400

From: Philip Levis <[email-masked]>
   Date: Wed, 14 Oct 2009 21:49:10 -0700

Or maybe a PLC link or two.

I would agree that this is true as far as ROLL and the IETF
is concerned.  More concrete and layer-specific
specifications can, and probably will, be produced by
other organzations.

An 'available bandwidth' metric works for this.  For a
battery powered device you know the desired lifetime, the
amount of energy in the battery, and how much of this will
be consumed by the device itself.  The leftover energy,
divided by the desired lifetime and the cost of sending and
receiving, gives the bandwidth the device can donate to the
network.  This works for energy scavenging devices as well,
assuming that the scavenging rate is predictable.

I think three metrics are needed:
  - latency
  - bandwidth (which subsumes energy limits, as above)
  - reliability
The units for the first two are straightforward.  The third
is a puzzler.
                              -Richard Kelsey

---

From: Philip Levis <[email-masked]>
Date: Thu, 15 Oct 2009 09:02:34 -0700

> probing it's not link layer dependent.

You can of course use ETX in a link-independent way. It just leads to  
possibly very bizarre route choices. E.g., choose a very slow, high  
power link that requires one transmission over a very fast, low-power  
link that requires 2 transmissions. ETT breaks when you have a fast  
very high power link and a slower low power link. Nominally, one goal  
of ETT and ETX is to minimize the space-time that packets occupy a  
wireless channel. When different link layers have very different  
transmit ranges (space), they stop being accurate units for this  
purpose.

Did I understand you correctly?

Phil

---

From: Philip Levis <[email-masked]>
Date: Thu, 15 Oct 2009 09:09:12 -0700

> limited to links with good ETX.

Richard,

I fear this assertion might misrepresent the data. An average cost of  
<2 does not by any means suggest that there are no links with cost >2.  
It could be that 80% of links have a cost of 1 and 20% have a cost of 4.

Phil

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 15 Oct 2009 13:43:17 -0400

From: Philip Levis <[email-masked]>
   Date: Thu, 15 Oct 2009 09:09:12 -0700

Right.  I wasn't as clear as I should have been.  For
the networks with lowest Cost/PL, such as 1.04 or 1.09,
hopcount would have been nearly identical to ETX as a
metric, if routing were limited to links with good ETX.

As you point out, for the higher values the Cost/PL
doesn't tell as much about what was happening.  The fact
that the highest Cost/PL are less than 2 does indicate
that most of the links used had an ETX less than 1.5.

                             -Richard Kelsey

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 15 Oct 2009 21:24:40 +0200

Philip Levis a écrit :
> that draws 60mW transmits at 1mW. Reducing transmit power typically does 
> not conserve much energy.

Well but who cares how much energy does the CMOS consume, when what we 
need is link energy.

> conclusion. Can you point me at some?

Err... just a side note to say there's a long list of papers talking 
metrics which have implications on power consumptions for emitting on a 
link.  Do you really want me to post?

I'm wary to more and more negative about citing papers on this WG.

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 15 Oct 2009 21:27:09 +0200

Philip Levis a écrit :
> ETX is a commonly used metric,

Philip, what do you mean by "ETX commonly used metric"?

Could you please explain, in implementation terms.

Could you list some widely available software in solid software 
distributions, widely deployed, and using this ETX metric?

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 15 Oct 2009 21:32:16 +0200

>> typically does not conserve much energy.

What is the device you commonly talk about?

This 1/6 computing/transmitting fraction seems illogical to me, when 
considering other similar chipsets.

Alex

---

From: Philip Levis <[email-masked]>
Date: Thu, 15 Oct 2009 12:33:25 -0700

> distributions, widely deployed, and using this ETX metric?

MIT Roofnet/srcr: http://pdos.csail.mit.edu/roofnet/software.php
CTP: http://tinyos.cvs.sourceforge.net/viewvc/tinyos/tinyos-2.x/tos/lib/net/ctp/
OLSR: http://www.olsr.org/docs/README-Link-Quality.html

Phil

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 15 Oct 2009 21:34:10 +0200

>   - bandwidth (which subsumes energy limits, as above)

Please add to what's needed an "energy metric for link" expressed in 
Joules needed to send 1280bytes on that particular link.

Alex

---

From: Philip Levis <[email-masked]>
Date: Thu, 15 Oct 2009 12:41:33 -0700

On Oct 15, 2009, at 12:32 PM, Alexandru Petrescu wrote:

>>>> I am saying that when using wireless links, a node should be  
>>>> aware that his communication could interfere with other  
>>>> communication.
>>> In low-power wireless chipsets, CMOS dominates power costs. E.g.,  
>>> a chip that draws 60mW transmits at 1mW. Reducing transmit power  

 From just one (leading) manufacturer:

CC1000 (868MHz): @5mW, draws 75mW; @ 0.01mW draws 25mW
CC1100 (868MHz): @10mW, draws 90mW; @0.1mW draws 42mW
CC2420 (2.4GHz): @1mW, draws 50mW: @0.003mW draws 25mW
CC2520 (2.4GHz): @3mW, draws 75mW: @1mW draws 60mW

> considering other similar chipsets.

Please read some data sheets.

Phil

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 15 Oct 2009 21:44:44 +0200

Philip Levis a écrit :
> CTP: 
> http://tinyos.cvs.sourceforge.net/viewvc/tinyos/tinyos-2.x/tos/lib/net/ctp/

How about software implementing IETF standards, geared towards advancing 
on the Standards Track?

What are we talking about here?  I more and more feel we live in very 
different worlds.

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 15 Oct 2009 21:46:26 +0200

> Please read some data sheets.

Please implement some RFCs.

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 15 Oct 2009 21:49:27 +0200

> OLSR: http://www.olsr.org/docs/README-Link-Quality.html

Ah the World Wide Web, h t t p something, wikipedia and google and we 
know everything...

The software being on a website doesn't tell anything about how much it 
is used.

How about software which is not on h t t p something yet it runs ok.

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 15 Oct 2009 21:52:13 +0200

>> that everyone can implement it on any kind of hardware".

I agree on the simplicity aspects.

And my answer to that question is a metric which expresses in Joules how 
much energy is needed to send an IPv6 1280bytes packet on that link.

Is this simple?  Difficult?  What do you think about simplicity
and this energy metric link.

Alex

---

From: Henning Rogge <[email-masked]>
Date: Thu, 15 Oct 2009 21:53:17 +0200

> How about software implementing IETF standards, geared towards advancing
The RFC conform implementation of OLSR does not work well. The 
Freifunk/Funkfeuer community networks (which are some of the largest deployed 
mesh networks) all use ETX because it does not work with hopcount.

> What are we talking about here?  I more and more feel we live in very
OLSRv2 WILL contain integrated metric support because everyone in the MANET-WG 
agrees that it's necessary. We are discussing about if we integrate ETX as the 
easiest (and layer 1/2 independant) metric as an appendix/example into the 
main draft or not at the moment.

Henning Rogge

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 15 Oct 2009 22:17:36 +0200

> mesh networks) all use ETX because it does not work with hopcount.

Well it seems like a large effort indeed (you claim it as some of the 
largest deployed mesh networks) - can I ping it?

> main draft or not at the moment.

Well that sounds as good news for ETX and OLSR.

Do you have some comment on link energy metrics?

Alex

---

From: Henning Rogge <[email-masked]>
Date: Thu, 15 Oct 2009 22:45:51 +0200

Am Donnerstag 15 Oktober 2009 22:17:36 schrieb Alexandru Petrescu:
> > Freifunk/Funkfeuer community networks (which are some of the largest
> > deployed mesh networks) all use ETX because it does not work with
> > hopcount.
> 
Most freifunk/funkfeuer networks are hidden between NAT routers that connect 
the networks to a DSL line.

I think Berlin was up to 700+ nodes some time ago, but it's a little bit 
shrinking because DSL is easier to get today.

Leipzig is and Vienna have hundreds of nodes too (Vienna 400-500 I think).

> > OLSRv2 WILL contain integrated metric support because everyone in the
> > MANET-WG agrees that it's necessary. We are discussing about if we
> > integrate ETX as the easiest (and layer 1/2 independant) metric as an
> > appendix/example into the main draft or not at the moment.
> 
I think both link energy metrics and ETT have the potential to be a much 
better metric than ETX. OLSR.org has ETX at the moment because it's the only 
metric we can support on different OS/hardware platforms. We hope to move to a 
generic "linklayer data framework" soon, so we can start to experiment with 
ETT or similar metrics.

Link energy metrics for WLAN are a little bit difficult because there are no 
exact tables how many energy each specific hardware consumes for a package.

Henning Rogge

---

From: Philip Levis <[email-masked]>
Date: Thu, 15 Oct 2009 13:59:30 -0700

On Oct 15, 2009, at 12:49 PM, Alexandru Petrescu wrote:

> Ah the World Wide Web, h t t p something, wikipedia and google and  
> we know everything...
>
> The software being on a website doesn't tell anything about how much  
> it is used.
>

Meraki's technology is based on srcr (the Roofnet students from MIT  
founded Meraki). Not an IETF standard, but a mesh protocol running on  
13,000+ networks, serving >4,000,000 clients. Srcr uses ETX/ETT. Sorry  
for the http, it's to their web page, not the source code:

http://meraki.com

Phil

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 15 Oct 2009 23:16:33 +0200

Philip Levis a écrit :
> 13,000+ networks, serving >4,000,000 clients. Srcr uses ETX/ETT.

Philip - how about some metric about which _you_ feel like you'd 
implement ok, and about which you feel like many people would agree 
with, and about which _you_ feel some people may need, and some usecases 
may need.

(sorry being too direct to 'you', but that's what I mean, and no
  offence).

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 15 Oct 2009 23:27:48 +0200

> Leipzig is and Vienna have hundreds of nodes too (Vienna 400-500 I think).

Sorry, I don't understand you.  What do you mean by e.g. Vienna has 
400-500 nodes?  What do these nodes do?

The DSL line I use does offer non-NAT and IPv6.  How about Viena, 
Leipzig and Berlin?

Also, you talk NAT: is ETX exclusively related to IPv4?  Does OLSRv2 
work with IPv6?

> better metric than ETX.

Ok, I don't know what ETT means.  Expanding the abbreviation would 
suffice, don't send me to  a paper.

> OLSR.org has ETX at the moment because it's the only 

Well there is some publicly available specification data about how much 
Watts are needed, and dBm levels, for WiFi.  When one says Watt one says 
Joule and time.

There exist also measurements for WiFi emissions, and unpublished 
reports.  Some relate to health studies.

The lack of precision could be compensated by expressing the values as a 
  range [min, max].

I am not sure that ETX and ETT(?) have been expressed and experimented 
for anything else than WiFi(?)

Alex

---

From: Henning Rogge <[email-masked]>
Date: Thu, 15 Oct 2009 23:41:23 +0200

Am Donnerstag 15 Oktober 2009 23:27:48 schrieb Alexandru Petrescu:
> Henning Rogge a écrit :
> > Most freifunk/funkfeuer networks are hidden between NAT routers that
> > connect the networks to a DSL line.
> >
Nodes as in OLSR instances running on a single embedded hardware with 1-3 
interfaces.
 
> The DSL line I use does offer non-NAT and IPv6.  How about Viena,
At the moment all FF networks except one in South Africa (I think) are IPv4. 
IPv6 takes lot's of flash storage for the kernel part, most of our routers 
only have 2-4 MB of flash.

> Also, you talk NAT: is ETX exclusively related to IPv4?  Does OLSRv2
OLSRv1 (and the olsr.org implementation of it) can run in IPv4 or IPv6 mode.

> suffice, don't send me to  a paper.
ETT = Estimated Travel Time

ETT = ETX / Transmission speed

> > Link energy metrics for WLAN are a little bit difficult because there are
> > no exact tables how many energy each specific hardware consumes for a
> > package.
> 
I think ETX is pretty easy to do on any kind of medium. ETT is a little bit 
more difficult because you have to know the transmission speed.

Henning Rogge

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 16 Oct 2009 00:03:11 +0200

> Nodes as in OLSR instances running on a single embedded hardware with 1-3 

Ok.

> only have 2-4 MB of flash.

Err... an IPv6 stack doesn't take much more than IPv4 stack.  If you can 
put an entire operating system (which seems to be a requirement of the 
OLSR daemon - linux/bsd/windows) then the stack is not much load.

> OLSRv1 (and the olsr.org implementation of it) can run in IPv4 or IPv6 mode.

So ETX is only for OLSRv2.

So ETX is not for IPv6.

Yet here we do IPv6.

> ETT = ETX / Transmission speed

Ok.

> more difficult because you have to know the transmission speed.

I find difficult to implement a Bernoulli series.  Me thinks there is 
not a single widely agreed rule of implementation of a Bernoulli series 
(Bernoulli is what ETX requires).

Do you think there's a StdsTrack RFC which specifies a form of 
probability implementation?  I don't think so.

I am aware of the lengthy discussions of the probability of address 
collision - never documented, not agreeable, not implementable IMHO.

Alex

---

From: Henning Rogge <[email-masked]>
Date: Fri, 16 Oct 2009 00:19:21 +0200

Am Freitag 16 Oktober 2009 00:03:11 schrieb Alexandru Petrescu:
> > At the moment all FF networks except one in South Africa (I think) are
> > IPv4. IPv6 takes lot's of flash storage for the kernel part, most of our
> > routers only have 2-4 MB of flash.
> 
it's hundreds of kilobytes. That's much if your whole operation system is 
stored in 2 megabytes of flash.
 
> So ETX is only for OLSRv2.
No 

> So ETX is not for IPv6.
No

> Yet here we do IPv6.
Yes

ETX is totally independant from IP version or mesh net protocol.

> (Bernoulli is what ETX requires).
ETX calculation based on received/lost hello messages is very easy.

Henning Rogge

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 16 Oct 2009 00:48:22 +0200

> stored in 2 megabytes of flash.

Well 200kbytes is 1/10 of your memory, dedicated to the stack.  I find 
it fair.

How big is your olsrd running?

>> So ETX is only for OLSRv2.

Does OLSRv2 run IPv6 and ETX?

> ETX calculation based on received/lost hello messages is very easy.

Hmm... not sure what you mean but I hear "received/lost" as some form of 
retransmission.

I'd say that a metric should be something intrinsic to the link, not 
something calculable by heartbeats/hellos.  E.g. a hopcount metric is 
intrinsic to the link (1 link is 1 hop, 2 links 2 hops), the 
qos/bandwidth are intrinsic to the link, the latency, etc.

But of course, it is ok to propose differently.

This makes me think that we may want to define what we mean by a 
"metric".  A "routing metric" - ok, but what else?

What are the requirements for defining a "routing metric"?

We should also mention it being different than a performance metric.

And needed by a routing protocol - and that routing protocol not 
necessarily RPL, but mostly RPL.

Alex

---

From: "M. B. Anand" <[email-masked]>
Date: Fri, 16 Oct 2009 01:38:21 -0400

I am not quite sure I understand the motivation for considering even less
hard "lifetime" (assuming this refers to life of some limited energy
source).

After all, at a system level, it has to be designed so the that the life is
enough for the application accounting for that subset of nodes that must try
their hardest all the time in terms of consuming energy - use their highest
available tx power, the slowest bitrate and the slowest code rate if those
is variable,.

You might argue it is a bonus if a node used less than the design and
therefore last longer, but then you might simply shift the problem to some
other node which has to reduce some of its lifetime forwarding. So, isn't it
the case the whole thing only shifts around the bonus lifetime beyond the
minimum design in varying ways among the nodes ?

Instead, I would think the link metric should only worry about capturing the
link's ability to get things across, no ? Lower tx power will be used if
possible on any link, but that is matter safely and correctly left to the
lower layer power control mechanisms.

Of course, I do operate in the 20 - 30 dBm world (where, on a completely
tangential note, in case anyone missed Phillip's careful wording of "In
low-power wireless chipsets..", it is not true that CMOS dominates), so feel
free to clobber me over the head if I am missing something.

Regards,
Anand.

On Thu, Oct 15, 2009 at 12:49 AM, Philip Levis <[email-masked]> wrote:

> If you break either assumption, it doesn't work well. ETT (expected time of
> transmission) can address 2), but not 1).
>
> I'm wary of encoding a metric as a hard quantity. For example, quantifying
> the metric as uJ breaks when nodes have differential energy capacities. What
> we really want is a more abstract notion of cost, which a particular device
> can use to, in a very simple way, express its own tradeoffs. It is critical
> that exactly how devices calculate this value remain unspecified.
>
> "lifetime" a packet would cost. Such a cost can consider both the receiver
> and transmitter. E.g., given its particular low power algorithms and
> expected lifetime, how much would sending to this destination consume? (I
> try to avoid using the word "link.")
>
>
>

---

From: Henning Rogge <[email-masked]>
Date: Fri, 16 Oct 2009 08:35:59 +0200

> Well 200kbytes is 1/10 of your memory, dedicated to the stack.  I find
It's 10% of our "hard disk". And that is without the necessary userspace 
programs. Most people running a Freifunk node would consider it a waste of 
space. Luckily linux got LZMA compression support for the kernel, so we have 
chances to get IPv6 support into the default firmwares.

> How big is your olsrd running?
100-200 kb I think. Depends on the amount of debug/logging code and the 
architecture. In addition to this you can add a number of plugins into our 
routing code.

> Does OLSRv2 run IPv6 and ETX?
OLSRv2 is a protocol (in draft status). It can easily be used with IPv6 and 
any kind of routing metric.

The Olsr.org implementation does run OLSRv1 (with or without ETX, with IPv4 or 
IPv6) at the moment, but I'm in the process implementing OLSRv2 (again, with 
any kind of routing metric and with IPv4/6).

> But of course, it is ok to propose differently.
The easiest way (not the best) to calculate ETX is to measure the amount of 
loss in both directions of the link with probing packets (hello messages for 
example). Then you just use exponential aging or a binary buffer to calculate 
the average loss rate LQ/NLQ and use them to define your ETX value 
(ETX=1/(LQ*NLQ)).

> What are the requirements for defining a "routing metric"?
Routing metrics can be anything.

- they can be a constant (hopcount)
- they can be based on money (how much does this link cost to send traffic 
over)
- they can be measured on the link (ETX, ETT, energy, SNR, ect.)
- they can be based on security considerations (only route traffic through 
nodes you trust enough)
- they can be some internal state of the router (hardware/battery resources of 
the router)

and of course multiple kind of metrics can be combined (that's whats called 
objective function in RPL).

> We should also mention it being different than a performance metric.
Performance (transmission speed for example) can be a routing metric too.
That would be useful for QoS in mesh networks.

Henning Rogge

-- 
Diplom-Informatiker Henning Rogge , Fraunhofer-Institut für
Kommunikation, Informationsverarbeitung und Ergonomie FKIE
Kommunikationssysteme (KOM)
Neuenahrer Straße 20, 53343 Wachtberg, Germany
Telefon +49 228 9435-263,   Fax +49 228 9435 685
mailto:[email-masked] http://www.fkie.fraunhofer.de
GPG: E1C6 0914 490B 3909 D944 F80D 4487 C67C 55EC CFE0

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 16 Oct 2009 11:36:28 +0200

> chances to get IPv6 support into the default firmwares.

I think one could save space by also removing the IPv4 stack.

> architecture. In addition to this you can add a number of plugins into our 

I think olsrd would save some space if it did not use IPv4 at all.  Is 
this the case?

> - they can be based on money (how much does this link cost to send traffic 

I have never seen such a routing metric.

> - they can be measured on the link (ETX, ETT, energy, SNR, ect.)

Yes, but there is a difference between relying on live measurements and 
prior measurements used as constants.

> - they can be based on security considerations (only route traffic through 

I haven't seen such routing metrics either.

> - they can be some internal state of the router (hardware/battery resources of 

Never seen these.

Ok.

(when I say I never saw some metrics above it's about implementations of 
OSPF and such).

> That would be useful for QoS in mesh networks.

Hmm, I am afraid of making a confusion between metrics used for 
performance evaluation and transmission speed (performance) to be a 
routing metric.

E.g. a metric is the meter in Switzerland against which everyone 
compares their rules.  But  I don't think a routing metric is such a 
concept.  We could distinguish this case - saying the ROLL routing 
metrics are not performance evaluation metrics.

Alex

---

From: Henning Rogge <[email-masked]>
Date: Fri, 16 Oct 2009 12:16:05 +0200

> I think one could save space by also removing the IPv4 stack.
This would make it a little bit difficult for people to get their transparent 
connection to the internet. Many routers in the Freifunk/Funkfeuer networks 
are connected to local private networks, so all of them need to be dual stack 
machines (to establish the 4in6 tunnel).

> > architecture. In addition to this you can add a number of plugins into
> > our routing code.
>
I don't think so. The core of the routing daemon does not care about the IP 
version, just the network/os specific parts do. Not much space to save.

> > - they can be based on money (how much does this link cost to send
> > traffic over)
>
Think about internet and BGP... an important point of routing traffic is how 
much money do you have to pay for it.

Yes.

> > - they can be based on security considerations (only route traffic
> > through nodes you trust enough)
>
http://en.wikipedia.org/wiki/RED/BLACK_concept

Some routers might be allowed to handle "secret" traffic. Some do not.

> > - they can be some internal state of the router (hardware/battery
> > resources of the router)
>
> Never seen these.
You might not want to route all your traffic through a small smart phone which 
battery might be empty within a few minutes, so it make sense to include this 
into a routing metric.

> > and of course multiple kind of metrics can be combined (that's whats
> > called objective function in RPL).
>
> Ok.
>
Different routing metrics are used for different scenarios.

Henning Rogge

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 16 Oct 2009 13:56:40 +0200

> machines (to establish the 4in6 tunnel).

Well, I tend to agree, but I think in this WG the nodes are constrained 
and if one has to make choices then the IPv4 stack is a good candidate 
for deletion.

> version, just the network/os specific parts do. Not much space to save.

Hmm... if every socket() call has a form for each address family then we 
sure can save some space by removing the AF_INET4 socket calls.

The same with all mallocs which reserve space related to IPv4 addresses.

The same with all text-to-binary conversion functions.

I think there is much space to save in the olsrd memory footprint if it 
only did IPv6.

There is also much space to save in the kernel if the IPv4 stack is removed.

> much money do you have to pay for it.

Ok, yes, makes some sense in principle.

But have you ever seen any form of encoding money values in an IP message?

Is it expressed in dollars or euros?  How much precision?

> Some routers might be allowed to handle "secret" traffic. Some do not.

Sounds as a good principle but what does it mean in practice?

Is there a routing protocol which works like that?

> battery might be empty within a few minutes, so it make sense to include this 

It's an appealing principle but what does it mean in practice?  I have 
never seen a metric encoded in a message which quantifies how much 
battery is left.

Ok.

Alex

---

From: Henning Rogge <[email-masked]>
Date: Fri, 16 Oct 2009 14:14:17 +0200

Am Fri October 16 2009 13:56:40 schrieb Alexandru Petrescu:
> ... (saving space by dropping IPv4)
I think this discussion is going off topic. But we can agree that you can save 
storage space and maybe memory if you limit your OS/routing agent to IPv4 or 
IPv6.

> > Think about internet and BGP... an important point of routing traffic is
> > how much money do you have to pay for it.
>
No.

> Is there a routing protocol which works like that?
Some time ago someone posted a plugin for the olsr.org code that used GPG for 
some kind of "web of trust" and created different routing tables from it. It 
was a proof of concept, but "security aware routing" is definitely something 
to remember, especially if you have a mixture of authenticated and not 
authenticated nodes in your network. You might want NOT to route over the not 
authenticated nodes...

> > You might not want to route all your traffic through a small smart phone
> > which battery might be empty within a few minutes, so it make sense to
> > include this into a routing metric.
>
Olsr.org has some experimental code to set the willingness to forward routing 
protocol traffic on the fly by looking at the battery settings.

Henning Rogge

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 16 Oct 2009 17:02:51 +0200

Hi Phil:

Fully agreed. 

This is why we are NOT looking for one-fit-it-all metric. Too many
bright people already lost their hair on that problem. What we are
looking for is a number of metrics and some logic to tie them together
and that gives us an OCP/OF. 

And there can be a different OCP for a different problem. Thus we are
NOT looking for the perfect OCP/set of metrics that would please
everybody, else we'd probably end up looking like an Egyptian scribe
with no hair anywhere ;)

Note that the rank IS NOT used to select the position in the DAG, but a
consequence of that position as selected by the OCP, at least in normal
operations. As you said earlier, it is but a proxy. As long as the OCP
and the metrics are found in the DIO, the proxy is not used as an input
to the OCP but generated as an output for the loop avoidance and
detection processes that comes later.

So what we really want in this draft is a set of OCPs that make sense in
the domain where we have experience in this group. It seems that a
consistent network of 802.15.4 nodes is a good problem to start with. 

So what would be a good set of metrics and an OCP in that case?

Pascal
>From: [email-masked] [mailto:[email-masked]] On Behalf Of
Philip Levis
>Sent: jeudi 15 octobre 2009 06:49
>To: roll ROLL

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 16 Oct 2009 17:15:01 +0200

> consistent network of 802.15.4 nodes is a good problem to start with. 

I doubt that.  A set of 802.15.4 nodes would use 802.15.5 mesh 'routing' 
instead of RPL.

I'd rather start with a heterogeneous set of low-power nodes each having 
multiple interfaces.

Alex

---

From: Philip Levis <[email-masked]>
Date: Mon, 19 Oct 2009 09:08:11 -0700

On Oct 15, 2009, at 2:16 PM, Alexandru Petrescu wrote:

>>>>>> I think we should keep in mind that RPL must work across  
>>>>>> multiple link layers. E.g.:
>>> The software being on a website doesn't tell anything about how  
>>> much it is used.
>>>
>> founded Meraki). Not an IETF standard, but a mesh protocol running  
>> on 13,000+ networks, serving >4,000,000 clients. Srcr uses ETX/ETT.
>
> with, and about which _you_ feel some people may need, and some  
> usecases may need.
>

I think I touched on this in a prior mail; I'll reiterate.

It's clear from the requirements documents that LLN applications have  
multiple routing optimization criteria. The two which seem clearest  
(to me) are latency and energy. Neither exists in a vacuum, it's a  
tradeoff. E.g., one trivial way to have zero-energy routing is to  
never send any packets (unbounded latency).

I think latency is a pretty simple one to tackle, with respect to  
metrics and route selection. I haven't heard much disagreement on  
this: I'd love to hear what application developers on the list think.

Energy (or some notion of energy cost) is a little more challenging.  
In particular, minimizing the energy spent forwarding the packet isn't  
the goal. There could be higher-power nodes with unlimited energy, who  
are willing to forward. From a pure energy standpoint, they are  
unattractive, but from a notion of how much this energy "costs" the  
system they are attractive.

For this reason, I think that your proposal on a 1280-byte packet  
doesn't quite fit the bill. Furthermore, the cost of sending a frame  
can be highly variable. E.g., if I am synchronized with the next hop  
then it might be cheap. If I'm not, I'll need to do some kind of  
wakeup operation and it will be expensive.

The thing which worries me about some notion of "energy cost," and  
what makes me wary of suggesting anything just yet, is its range.  
Packet-BB ran into this a bit with metric specifications. In  
particular, if we decide that the range is great enough that it  
requires some kind of simple floating point (exponential notation),  
then one needs rules to make sure you round up when well below the  
range set by the exponent. Otherwise, you can get into a situation  
where adding a hop won't increase the cost, as it's outside the  
precision allowed.

Does that make sense?

Phil

---

From: Philip Levis <[email-masked]>
Date: Wed, 21 Oct 2009 11:06:54 -0700

On Oct 15, 2009, at 10:43 AM, Richard Kelsey wrote:

>   <2 does not by any means suggest that there are no links with cost  
> >2.

I agree. Steep SNR/PRR curves mean that narrowband wireless physical  
layers tend to have few intermediate links in the absence of external  
interference.

But my concern is that we need to design a protocol for the hard case,  
not the easy one. Administrators can't always control the wireless  
environment: it would be a problem if RPL didn't work in Tutornet,  
Motelab, or Wyman-park like environments. Furthermore, RPL needs to be  
able to run over wider-band physical layers, or those with much more  
gradual SNR/PRR curves.

I'm very uncomfortable with the thread of logic hat RPL's topology  
needs to be very stable. I think all other things being equal, a  
stable topology is better than a dynamic one, and it's reasonable for  
implementations to try to improve stability. My worry starts, however,  
when we start *assuming* it is stable, and relegating highly dynamic  
networks to an oddity only worth cursory consideration. Doing so will  
lead to many failed deployments and general skepticism on the  
engineering and utility of RPL.

Phil

---

From: Philip Levis <[email-masked]>
Date: Wed, 21 Oct 2009 18:41:47 -0700

Phil

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 22 Oct 2009 12:05:56 -0400

From: Philip Levis <[email-masked]>
   Date: Wed, 21 Oct 2009 18:41:47 -0700

   But my concern is that we need to design a protocol for
   the hard case, not the easy one. Administrators can't
   always control the wireless environment: it would be a
   problem if RPL didn't work in Tutornet, Motelab, or
   Wyman-park like environments.  Furthermore, RPL needs to
   be able to run over wider-band physical layers, or those
   with much more gradual SNR/PRR curves.

I am not sure I understand your point.  The question at hand
is the design of a link reliability metric.  Coping with,
and making intelligent use of, noisy or otherwise unreliable
links is what this is about.

Any protocol that stores routes for future use depends on
some amount of stability.  If the topology is sufficiently
unstable the bandwidth needed to maintain routes will
overwhelm the network.  Leaving the application with not
enough bandwidth is just as much a routing failure as not
having a working route.  With a very dynamic topology the
emphasis has to be on quickly and efficiently finding some
route, rather than spending resources on finding one of the
better routes.  I am skeptical that a single protocol will
work well at both ends of the spectrum.

In my experience a lack of bandwidth is a bigger problem for
application on ROLL-style networks than a lack of reliable
connectivity.  Connectivity problems can be almost always be
solved by installing more repeaters.  If you are out of
bandwidth, there is little you can do to fix that particular
installation.  Bounding the routing overhead at the cost of
depending on a more stable topology is the right way to go.

Using a purely reactive routing strategy has the effect of
shifting some of the routing design to the higher layers.
Given a fixed amount of total bandwidth, the amount
available to the application will depend on the stability of
the links.  This isn't something that application designers
should have to think about.  Again, the solution is to bound
the reactivity, which again requires depending on a some
network stability.
                              -Richard Kelsey

---

From: Maxence Dalmais <[email-masked]>
Date: Mon, 12 Oct 2009 17:00:14 +0200

Hi JP,

Using high energy path will include more errors to others transmissions, ie
increase retransmissions, ie increase the ETX metric. This may involve
modifications in the chosen path.
Maybe we could think that we don't need to take energy path into account
the  because ETX will automatically adapt to this.
But having a highly dynamic ETX may cause others trouble, don't you think  ?
Maybe, energy path has to be taken in count in RPL to avoid the need of a
very dynamic ETX and retransmissions.

Cheers,

Maxence.

---

From: Philip Levis <[email-masked]>
Date: Sat, 24 Oct 2009 05:15:15 -0400

> work well at both ends of the spectrum.

Some of the CTP results suggest it is possible: using datapath  
validation and adaptive beaconing, it's able to be much more reactive  
and dynamic while simultaneously sending fewer control packets. That  
being said, it's critical to have some kind of hysteresis. A student  
here at Stanford studied how hysteresis values (the threshold better a  
new route must be to choose it over the existing one) affects  
performance, and found that it's a reasonably robust value that  
doesn't need fine tuning.

> depending on a more stable topology is the right way to go.

I guess this is the part I don't understand: if capacity is the  
limiting factor, this suggests a high duty cycle. Where does the "low  
power" part come in?

Phil

---

From: Philip Levis <[email-masked]>
Date: Sat, 24 Oct 2009 21:02:16 -0400

Phil