Subject: [Roll] I-D Action:draft-ietf-roll-routing-metrics-01.txt

From: [email-masked]
Date: Sat, 24 Oct 2009 03:30:01 -0700 (PDT)

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the Routing Over Low power and Lossy networks Working Group of the IETF.

	Title           : Routing Metrics used for Path Calculation in Low Power and Lossy Networks
	Author(s)       : J. Vasseur, D. Networks
	Filename        : draft-ietf-roll-routing-metrics-01.txt
	Pages           : 28
	Date            : 2009-10-24

Low power and Lossy Networks (LLNs) have unique characteristics
compared with traditional wired and ad-hoc networks that require the
specification of new routing metrics and constraints.  By contrast
with typical Interior Gateway Protocol (IGP) routing metrics using
hop counts or link metrics, this document specifies a set of link and
node routing metrics and constraints suitable to LLNs.

A URL for this Internet-Draft is:
http://www.ietf.org/internet-drafts/draft-ietf-roll-routing-metrics-01.txt

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

Below is the data which will enable a MIME compliant mail reader
implementation to automatically retrieve the ASCII version of the
Internet-Draft.

---

From: Alexandru Petrescu <[email-masked]>
Date: Sat, 24 Oct 2009 12:42:31 +0200

>   The Expected Transmission Count (ETX) metric is defined as 1 / (Df *
>    Dr) where Df is the measured probability that a packet is received

How do you measure that probability ^ ?

>   ETX: 8 bits.  The Latency is encoded in 32 bits in IEEE floating
>    point format (see [IEEE.754.1985]).  Refer to Section 3.1.2 of
>    [RFC3741] for a table of commonly used values.

Er?  That RFC "Exclusive XML Canonicalization" does not have any section 
3.1.2.  Are you sure you refer to the right document? (it too sounds 
strange to use XML carried in RPL).

BTW, do you use XML to edit the metrics draft?

Alex

[email-masked] a écrit :
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: JP Vasseur <[email-masked]>
Date: Sat, 24 Oct 2009 14:31:42 +0200

Dear all,

Please find below the new revision of the METRIC ID. As you know we  
had to wait until RPL was stable enough to update this document. This  
revision is thus a major update compared to the previous one.

Few important comments
1) This revision of course takes into account the discussion that we  
had on the mailing list,
2) No metric is mandated. RPL implementation may use one or several of  
these metrics and we made them generic enough to be extensible. The  
use of the metrics will be dictated by the OF.
3) IMPORTANT: there are many ways to use metrics. It could be as  
simple as a cumulative hop counts or as complex as a hierarchical  
constraint based approach with multi-metric heuristics, both for nodes  
and links. We made the design quite generic to support all cases. A  
RPL implementation may be EXTREMELY simple and compliant to the  
document or more complex to handle specific situations with less  
constrained nodes.

Waiting for your comments.

Thanks.

JP, Mijeom and Kris.

Begin forwarded message:

> From: [email-masked]
> Date: October 24, 2009 12:30:01 PM CEDT
> To: [email-masked]
> Cc: [email-masked]
> Subject: [Roll] I-D Action:draft-ietf-roll-routing-metrics-01.txt
>

---

From: Philip Levis <[email-masked]>
Date: Sat, 24 Oct 2009 18:20:47 -0700

On Oct 24, 2009, at 5:31 AM, JP Vasseur wrote:

> had to wait until RPL was stable enough to update this document.  
> This revision is thus a major update compared to the previous one.
>
> Few important comments
> 2) No metric is mandated. RPL implementation may use one or several  
> of these metrics and we made them generic enough to be extensible.  
> The use of the metrics will be dictated by the OF.
> constraint based approach with multi-metric heuristics, both for  
> nodes and links. We made the design quite generic to support all  
> cases. A RPL implementation may be EXTREMELY simple and compliant to  
> the document or more complex to handle specific situations with less  
> constrained nodes.

4.3.2.  The Expected Transmission Count (ETX) Reliability Object

    The Expected Transmission Count (ETX) metric is defined as 1 / (Df *
    Dr) where Df is the measured probability that a packet is received  
by
    the neighbor and Dr is the measured probability that the
    acknowledgment packet is successfully received.

I would change this to say

    The Expected Transmission Count (ETX) metric is the number of  
transmissions
    a node expects to make to a destination in order to successfully  
deliver a
    packet.

The approach of 1 / (Df * Dr) is the approach used by Srcr, but there  
are other algorithms for measuring it, such as 4B and EAR.

Phil

---

From: Alexandru Petrescu <[email-masked]>
Date: Sun, 25 Oct 2009 15:26:46 +0100

Philip Levis a écrit :
>    Dr) where Df is the measured probability that a packet is received by

Ok... suppose I want to implement this.  Is this number a constant 
somewhere in a sheet?  Where am I supposed to get this number in order 
to put it in a message?

Alex

---

From: JP Vasseur <[email-masked]>
Date: Mon, 26 Oct 2009 09:25:03 +0100

On Oct 25, 2009, at 2:20 AM, Philip Levis wrote:

>> 1) This revision of course takes into account the discussion that  
>> we had on the mailing list,
>> cases. A RPL implementation may be EXTREMELY simple and compliant  
>> to the document or more complex to handle specific situations with  
>> less constrained nodes.
>
>
> The approach of 1 / (Df * Dr) is the approach used by Srcr, but  
> there are other algorithms for measuring it, such as 4B and EAR.
>

Absolutely. Makes sense. I added this one as an example (I'll be more  
explicit about the fact that this *one* example). We want to make it  
implementation specific since there are many ways to compute it  
depending on the link layer and other parameters.

Cheers.

JP.

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 26 Oct 2009 09:54:49 +0100

> depending on the link layer and other parameters.

In defining ETX one would like to make sure that two different 
implementers implement the same way an ETX.

Alex

---

From: Thomas Heide Clausen <[email-masked]>
Date: Mon, 26 Oct 2009 09:59:48 +0100

On Oct 26, 2009, at 9:54 AM, Alexandru Petrescu wrote:
>>>
>> Absolutely. Makes sense. I added this one as an example (I'll be  
>> more explicit about the fact that this *one* example). We want to  
>> make it implementation specific since there are many ways to  
>> compute it depending on the link layer and other parameters.
>

In the case where two different implementations would cause  
interoperability difficulties, yes.

Otherwise, no.

Do you think that, as long as the ETX value is unambiguous to whoever  
calculates it and is consistently communicated, there are  
interoperability difficulties?

Thomas

---

From: JP Vasseur <[email-masked]>
Date: Mon, 26 Oct 2009 10:11:52 +0100

On Oct 26, 2009, at 9:54 AM, Alexandru Petrescu wrote:

>>>> Please find below the new revision of the METRIC ID. As you know  
>>>> we had to wait until RPL was stable enough to update this  
>>>> document. This revision is thus a major update compared to the  
>>>> previous one.
>>>>
>>>> Few important comments
>>>> 2) No metric is mandated. RPL implementation may use one or  
>>>> several of these metrics and we made them generic enough to be  
>>>> extensible. The use of the metrics will be dictated by the OF.
>>>> to the document or more complex to handle specific situations  
>>>> with less constrained nodes.
>>>
>>>

This is more of a deployment issue though. Look at OSPF/ISIS/..., we  
do not mandate the use of a specific formula. But you're right that  
the use of consistent metric is key (this is mentioned in Section 8).

Thanks.

JP.

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 26 Oct 2009 10:12:57 +0100

Thomas, where do I get this number:
> The Expected Transmission Count (ETX) metric is the number of transmissions
>   a node expects to make to a destination in order to successfully deliver a
>   packet.

Where can I get this number of transmission my node expects to make to a 
destination in order to successfully deliver a packet?

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 26 Oct 2009 10:14:46 +0100

JP Vasseur a écrit :
> This is more of a deployment issue though. Look at OSPF/ISIS/..., we do 
> not mandate the use of a specific formula.

However, the hopcount metric in OSPF is univerally understood: the 
number of IP hops in between, and this number is well understood.

I am not sure what in OSPF/ISIS/... makes you think I should look at, to 
make me think it's like ETX - deployment issue?

Alex

  But you're right that the use
> of consistent metric is key (this is mentioned in Section 8).
> 
> Thanks.
> 
> JP.
> 
>> Alex
>>
>>> Cheers.
>>> JP.
>>>> Phil

---

From: JP Vasseur <[email-masked]>
Date: Mon, 26 Oct 2009 10:15:52 +0100

On Oct 26, 2009, at 10:14 AM, Alexandru Petrescu wrote:

>>>>>> Please find below the new revision of the METRIC ID. As you  
>>>>>> know we had to wait until RPL was stable enough to update this  
>>>>>> 1) This revision of course takes into account the discussion  
>>>>>> that we had on the mailing list,
>>>>>> 3) IMPORTANT: there are many ways to use metrics. It could be  
>>>>>> as simple as a cumulative hop counts or as complex as a  
>>>>>> hierarchical constraint based approach with multi-metric  
>>>>>> heuristics, both for nodes and links. We made the design quite  
>>>>>> generic to support all cases. A RPL implementation may be  
>>>>>> EXTREMELY simple and compliant to the document or more complex  
>>>>>> to handle specific situations with less constrained nodes.
>>>>>
>>>>>
>> This is more of a deployment issue though. Look at OSPF/ISIS/...,  
>> we do not mandate the use of a specific formula.
>
> I am not sure what in OSPF/ISIS/... makes you think I should look  
> at, to make me think it's like ETX - deployment issue?
>

OSPF and ISIS do not use hop count but a static undefined link metric.

JP.

---

From: Thomas Heide Clausen <[email-masked]>
Date: Mon, 26 Oct 2009 10:15:52 +0100

On Oct 26, 2009, at 10:12 AM, Alexandru Petrescu wrote:

>> interoperability difficulties, yes. Otherwise, no.
>> Do you think that, as long as the ETX value is unambiguous to  
>> whoever calculates it and is consistently communicated, there are  
> Where can I get this number of transmission my node expects to make  
> to a destination in order to successfully deliver a packet?
>

I don't know, I would guess that it depends on your platform (OS,  
hardware, applications) allowing you to make more or less accurate  
estimates of this value.

It doesn't matter, however, as long as that value is established in  
one place (check) and so there are no ambiguities as to what that  
value is, for a given <source, destination>

Thomas

---

From: Thomas Heide Clausen <[email-masked]>
Date: Mon, 26 Oct 2009 10:20:02 +0100

> at, to make me think it's like ETX - deployment issue?

It's not really the point, Alex. Think of a graph with weights (cost)  
on the edges.

It doesn't matter if the weight is 1 or "something else", as long as  
the weights are unambiguous. If the weight for a given edge is  
established in *one* place only, everything works fine ;)

Thomas

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 26 Oct 2009 10:29:47 +0100

JP Vasseur a écrit :
>>>>>>> Please find below the new revision of the METRIC ID. As
>>>>>>> you know we had to wait until RPL was stable enough to
>>>>>>> update this document. This revision is thus a major
>>>>>>> update compared to the previous one.
>>>>>>> 
>>>>>>> Few important comments 1) This revision of course takes
>>>>>>> into account the discussion that we had on the mailing
>>>>>>> list, 2) No metric is mandated. RPL implementation may
>>>>>>> use one or several of these metrics and we made them
>>>>>>> generic enough to be extensible. The use of the metrics
>>>>>>> will be dictated by the OF. 3) IMPORTANT: there are many
>>>>>>> ways to use metrics. It could be as simple as a
>>>>>>> cumulative hop counts or as complex as a hierarchical 
>>>>>>> constraint based approach with multi-metric heuristics,
>>>>>>> both for nodes and links. We made the design quite
>>>>>>> EXTREMELY simple and compliant to the document or more
>>>>>>> complex to handle specific situations with less
>>>>>>> constrained nodes.
>>>>>> 
>>>>>> 
>>>>>> The Expected Transmission Count (ETX) metric is defined as
>>>>>> 1 / (Df * Dr) where Df is the measured probability that a
>>>>>> packet is received by the neighbor and Dr is the measured
>>>>>> probability that the acknowledgment packet is successfully
>>>>>> received.
>>>>>> 
>>>>>> The Expected Transmission Count (ETX) metric is the number
>>>>>> of transmissions a node expects to make to a destination in
>>>>>> order to successfully deliver a packet.
>>>>>> 
>>>>>> The approach of 1 / (Df * Dr) is the approach used by Srcr,
>>>>>> but there are other algorithms for measuring it, such as 4B
>>>>>> and EAR.
>>>>>> 
>>>>> Absolutely. Makes sense. I added this one as an example (I'll
>>>>> be more explicit about the fact that this *one* example). We
>>>>> want to make it implementation specific since there are many
>>>>> ways to compute it depending on the link layer and other
>>>>> parameters.
>>>> 

Ah!  There may be a misunderstanding.

I counted on this OSPF text: "The next hop calculation is invoked each
	    time a shorter path	to the destination is discovered."

"Shorter" is in terms of IP hop count.

Let me see later, thanks.

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 26 Oct 2009 10:32:38 +0100

Thomas Heide Clausen a écrit :
>>> do not mandate the use of a specific formula.
>>
>> I am not sure what in OSPF/ISIS/... makes you think I should look at, 
>> to make me think it's like ETX - deployment issue?
> 
> It's not really the point, Alex. Think of a graph with weights (cost) on 
> the edges.

YEs, yes.

> It doesn't matter if the weight is 1 or "something else", as long as the 
> weights are unambiguous. If the weight for a given edge is established 
> in *one* place only, everything works fine ;)

That's a problem IMHO - the expected in ETX.

Alex

---

From: Thomas Heide Clausen <[email-masked]>
Date: Mon, 26 Oct 2009 10:41:19 +0100

On Oct 26, 2009, at 10:32 AM, Alexandru Petrescu wrote:

>>>>>>>> know we had to wait until RPL was stable enough to update  
>>>>>>>> this document. This revision is thus a major update compared  
>>>>>>>> to the previous one.
>>>>>>>>
>>>>>>>> Few important comments
>>>>>>>> several of these metrics and we made them generic enough to  
>>>>>>>> be extensible. The use of the metrics will be dictated by the  
>>>>>>>> OF.
>>>>>>>> heuristics, both for nodes and links. We made the design  
>>>>>>>> quite generic to support all cases. A RPL implementation may  
>>>>>>>> be EXTREMELY simple and compliant to the document or more  
>>>>>>>> complex to handle specific situations with less constrained  
>>>>>>>> nodes.
>>>>>>>
>>>>>>>
>> It's not really the point, Alex. Think of a graph with weights  
>> (cost) on the edges.
>
> YEs, yes.
>
>> It doesn't matter if the weight is 1 or "something else", as long  
>> as the weights are unambiguous. If the weight for a given edge is  

As long as there's only one entity making the "expectation",  
everything is fine.

Thomas

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 26 Oct 2009 10:41:22 +0100

Thomas Heide Clausen a écrit :
> As long as there's only one entity making the "expectation", everything 
> is fine.

WEll - there may be a risk that if my node expects 2 retransmissions and 
the receiving node expects me to try 3 times - we may have a problem in 
building a coherent ETX-aware path.

Alex

---

From: Thomas Heide Clausen <[email-masked]>
Date: Mon, 26 Oct 2009 10:42:06 +0100

On Oct 26, 2009, at 10:41 AM, Alexandru Petrescu wrote:

>>>>>>>>>> this document. This revision is thus a major update  
>>>>>>>>>> compared to the previous one.
>>>>>>>>>>
>>>>>>>>>> Few important comments
>>>>>>>>>> 1) This revision of course takes into account the  
>>>>>>>>>> discussion that we had on the mailing list,
>>>>>>>>>> be extensible. The use of the metrics will be dictated by  
>>>>>>>>>> the OF.
>>>>>>>>>> 3) IMPORTANT: there are many ways to use metrics. It could  
>>>>>>>>>> be as simple as a cumulative hop counts or as complex as a  
>>>>>>>>>> quite generic to support all cases. A RPL implementation  
>>>>>>>>>> may be EXTREMELY simple and compliant to the document or  
>>>>>>>>>> more complex to handle specific situations with less  
>>>>>>>>>> constrained nodes.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> 1 / (Df *
>>>>>>>>> of transmissions
>>>>>> This is more of a deployment issue though. Look at OSPF/ 
>>>>>> ISIS/..., we do not mandate the use of a specific formula.
>>>>>
>>>>> However, the hopcount metric in OSPF is univerally understood:  
>>>>> the number of IP hops in between, and this number is well  
>>>>> understood.
>>>>>
>>>>> I am not sure what in OSPF/ISIS/... makes you think I should  
>>>>> look at, to make me think it's like ETX - deployment issue?
> WEll - there may be a risk that if my node expects 2 retransmissions  
> and the receiving node expects me to try 3 times - we may have a  
> problem in building a coherent ETX-aware path.

Why?

Thomas

---

From: JP Vasseur <[email-masked]>
Date: Mon, 26 Oct 2009 10:45:08 +0100

> "Shorter" is in terms of IP hop count.

Just to close on this ... No, OSPF does not use IP Hop Count but a  
link metric ...
Same for ISIS and many others.

> Let me see later, thanks.

Sure.

JP.

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 26 Oct 2009 10:51:45 +0100

JP Vasseur a écrit :
> Just to close on this ... No, OSPF does not use IP Hop Count but a link 
> metric ...

JP - before closing it too quickly, for my clarification - what does 
that "shorter path" mean in your interpretation?

Does that "shorter path" in OSPF mean it has some smaller link qualities 
(like smaller latencies)?

Thanks,

Alex

---

From: JP Vasseur <[email-masked]>
Date: Mon, 26 Oct 2009 10:54:59 +0100

>>> [snip]

> that "shorter path" mean in your interpretation?

This is not my interpretation ;-) but how OSPF/ISIS/... work. The  
shortest path is the one with the lowest path
cost (computed using SPF) where the cost = sum of link metric, the  
link metric being defined by the network
administrator. It may reflect the bw, latency or whatever you want.  
Some SP use a polynomial function of
bw, latency, ...

> Does that "shorter path" in OSPF mean it has some smaller link  
> qualities (like smaller latencies)?
>
> Thanks,
>
> Alex
>
>>>

---

From: Thomas Heide Clausen <[email-masked]>
Date: Mon, 26 Oct 2009 10:55:44 +0100

> qualities (like smaller latencies)?

Would it be clearer to you if we say "least cost paths" instead?

Thomas

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 26 Oct 2009 11:22:54 +0100

JP Vasseur a écrit :
> cost (computed using SPF) where the cost = sum of link metric, the link 
> metric being defined by the network
> administrator. It may reflect the bw, latency or whatever you want. Some 
> SP use a polynomial function of
> bw, latency, ...

JP - I begin to understand what you mean.

I however am interested in the parts of OSPF (and RPL) which try to 
avoid loops and offer shortest paths in terms of IP number of hops.

For ETX - I will come to it later.

(thanks for the cost explanation)

Alex

---

From: Thomas Heide Clausen <[email-masked]>
Date: Mon, 26 Oct 2009 11:24:50 +0100

On Oct 26, 2009, at 11:22 AM, Alexandru Petrescu wrote:

>>>> Just to close on this ... No, OSPF does not use IP Hop Count but  
>>>> a link metric ...
>>> JP - before closing it too quickly, for my clarification - what  
>>> does that "shorter path" mean in your interpretation?
>>>

As a complement to the discussion on the list, may I recommend:

	http://openlibrary.org/b/OL20956283M/Applied_and_algorithmic_graph_theory

Thomas

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 26 Oct 2009 11:27:15 +0100

> Would it be clearer to you if we say "least cost paths" instead?

Well yes.  In OSPF we can't say so anylonger.

"Least cost paths" used throughout is clearer from what you say.

One should be sure when using them coherently.  There are risks.  Check 
this in the metrics draft:

"the path quality, also referred to as the path cost"

I prefer high quality and low cost - as such the path quality and the 
path cost are contradictory; so one can't refer to the path quality as 
the path cost - they're completely inverse.

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 26 Oct 2009 11:28:53 +0100

>     http://openlibrary.org/b/OL20956283M/Applied_and_algorithmic_graph_theory 

SOrry the book is not clickable.

ARe you kind of like trying to tell me to go back read some basics?

Alex

---

From: JP Vasseur <[email-masked]>
Date: Mon, 26 Oct 2009 13:58:56 +0100

Hi,

> How do you measure that probability ^ ?

This is one example (I'll make it explicit). Depending on the link  
layer, you may use some link layer specific mechanism, use a probe, ...

> Er?  That RFC "Exclusive XML Canonicalization" does not have any  
> section 3.1.2.  Are you sure you refer to the right document? (it  
> too sounds strange to use XML carried in RPL).

Type, sorry, it should ready RFC3471.

---

From: Michael Richardson <[email-masked]>
Date: Mon, 26 Oct 2009 10:37:52 -0400

Alexandru asked where/how he can calculate the ETX.
Thomas suggests that it is a deployment issue, and then suggests looking at
OSPF.
JP points out that OSPF and ISIS use a static undefined link metric.

I want to point out that OSPF and ISIS are used in situations where
there is no (or little significant) movement, and in general the link
metric is configured by an operator.

I do not want to have to configure all the light switches in my house.
I also do not expect the builder to configure ETX metrics in them
either.

My impression is that RPL has to use metrics that can generally be
calculated by nodes themselves.  I also have no idea how I would
calculate ETX, except by observing what happened before. 

-- 
]       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: Thomas Heide Clausen <[email-masked]>
Date: Mon, 26 Oct 2009 15:50:21 +0100

> calculate ETX, except by observing what happened before.

....which is perfectly OK and, as far as I am concerned, in line with  
what I mentioned before: as long as the cost/weight of a link is  
calculated in an unambiguous manner, all is well.

Thomas

---

From: JP Vasseur <[email-masked]>
Date: Mon, 26 Oct 2009 15:51:10 +0100

Hi Michael,

> metric is configured by an operator.

The comment about OSPF/ISIS was in reply to the specification on how  
the ETX
had to be computed (deployment issue).

> I also do not expect the builder to configure ETX metrics in them

Sure. The proposal was not to manually configure these metrics but  
rather that
different nodes may used different techniques to compute the ETX.

> calculate ETX, except by observing what happened before.

This is one approach. Your node could also rely on PHY/MAC mechanisms  
when
available or use probes.

Thanks.

JP.

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

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 26 Oct 2009 16:15:52 +0100

> calculated in an unambiguous manner, all is well.

Well yes, but we still have to see that unambiguous manner.  MAybe it 
will come in later.

Alex

---

From: Thomas Heide Clausen <[email-masked]>
Date: Mon, 26 Oct 2009 16:18:15 +0100

On Oct 26, 2009, at 4:15 PM, Alexandru Petrescu wrote:

>> ....which is perfectly OK and, as far as I am concerned, in line  
>> with what I mentioned before: as long as the cost/weight of a link  
>> is calculated in an unambiguous manner, all is well.
>
> Well yes, but we still have to see that unambiguous manner.  MAybe  
> it will come in later.

Not really necessary. Unambiguous meaning "that link is associated  
with one and only one cost" -> no problems. If the cost two disjoint  
links are calculated using two different formula, still no problem.

---

From: Omprakash Gnawali <[email-masked]>
Date: Sat, 24 Oct 2009 23:18:35 -0700

On Sat, Oct 24, 2009 at 6:20 PM, Philip Levis <[email-masked]> wrote:
>> Please find below the new revision of the METRIC ID. As you know we had to
>> wait until RPL was stable enough to update this document. This revision is
>> thus a major update compared to the previous one.
>>
>> Few important comments
>> 1) This revision of course takes into account the discussion that we had
>> on the mailing list,
>> these metrics and we made them generic enough to be extensible. The use of
>> the metrics will be dictated by the OF.
>> 3) IMPORTANT: there are many ways to use metrics. It could be as simple as
>> a cumulative hop counts or as complex as a hierarchical constraint based
>> approach with multi-metric heuristics, both for nodes and links. We made the
>> design quite generic to support all cases. A RPL implementation may be
>> EXTREMELY simple and compliant to the document or more complex to handle
>> specific situations with less constrained nodes.
>
>
> The approach of 1 / (Df * Dr) is the approach used by Srcr, but there are
> other algorithms for measuring it, such as 4B and EAR.

I agree - we should not imply a particular method of estimating ETX,
unless it is being presented as an example. However, 4B/EAR's approach
also assume successful acknowledgment.

- om_p

---

From: JP Vasseur <[email-masked]>
Date: Mon, 26 Oct 2009 18:41:34 +0100

On Oct 25, 2009, at 7:18 AM, Omprakash Gnawali wrote:

>>> we had to
>>> several of
>>> simple as
>> there are
> unless it is being presented as an example.

now explicitly stated in the rev-02.

Thanks.

JP

> However, 4B/EAR's approach

---

From: Philip Levis <[email-masked]>
Date: Mon, 26 Oct 2009 11:25:49 -0700

> calculate ETX, except by observing what happened before.

There are three major algorithms out there: Srcr, 4B, and EAR. All  
have openly available source code.

Srcr is the algorithm that was in the older text. Using periodic  
broadcasts with sequence numbers, nodes measure incoming packet  
delivery ratios using a sliding window. These broadcasts contain those  
incoming delivery ratios. A node therefore calculates its own incoming  
ratios and stores (heard from others) its outgoing ratios. It uses  
these ratios to estimate the probability of both a data packet and its  
link layer ack arriving successfully. There are follow-on  
modifications to Srcr, such as including variance in the cost. The  
Srcr algorithm is described in John Bicket's Mobicom 2003 paper  
entitled "A High Throughput Path Metric for Multi-Hop Wireless  
Routing." The Srcr implementation is described in his 2005 paper  
entitled "Architecture and Evaluation of an Unplanned 802.11b Mesh  
Network." The software can be downloaded from the MIT Roofnet site.

4B (the 4-bit link estimator) uses a hybrid approach. It uses  
broadcasts similarly to Srcr, and to seed its link table. These  
broadcast-based estimates, however, are supplemented by direct  
measurement of the delivery rate of data frames. Every time a node  
sends a packet, 4B keeps track of whether the packet was acknowledged.  
It uses this binary string to estimate the number of transmissions for  
a packet. The 4B estimator and its implementation are described in  
Rodrigo Fonseca's HotNets paper entitled "Four-Bit Wireless Link  
Estimation." The software can be downloaded as part of recent TinyOS  
distributions.

EAR is another hybrid approach. Kyu-Han Kim's Mobicom 2006 paper "On  
Accurate Measurement of Link Quality In Multi-hop Wireless Mesh  
Networks" describes it, and his old web page has a source download for  
the Linux kernel.

Hope this helps,

Phil

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 26 Oct 2009 19:35:29 +0100

Philip Levis a écrit :
> There are three major algorithms out there: Srcr, 4B, and EAR. All have 
> openly available source code.
> 
> broadcasts with sequence numbers, nodes measure incoming packet delivery 
> ratios using a sliding window. These broadcasts contain those incoming 
> delivery ratios. A node therefore calculates its own incoming ratios and 
> stores (heard from others) its outgoing ratios. It uses these ratios to 
> estimate the probability of both a data packet and its link layer ack 
> arriving successfully. There are follow-on modifications to Srcr, such 
> as including variance in the cost. The Srcr algorithm is described in 
> John Bicket's Mobicom 2003 paper entitled "A High Throughput Path Metric 
> for Multi-Hop Wireless Routing." The Srcr implementation is described in 
> his 2005 paper entitled "Architecture and Evaluation of an Unplanned 
> 802.11b Mesh Network." The software can be downloaded from the MIT 
> Roofnet site.
> 
> 4B (the 4-bit link estimator) uses a hybrid approach. It uses broadcasts 
> similarly to Srcr, and to seed its link table. These broadcast-based 
> estimates, however, are supplemented by direct measurement of the 
> delivery rate of data frames. Every time a node sends a packet, 4B keeps 
> track of whether the packet was acknowledged. It uses this binary string 
> to estimate the number of transmissions for a packet. The 4B estimator 
> and its implementation are described in Rodrigo Fonseca's HotNets paper 
> entitled "Four-Bit Wireless Link Estimation." The software can be 
> downloaded as part of recent TinyOS distributions.
> 

Phil - thanks, I set this review aside.

It involves some link-layer information (a "reply" was received) and 
probabilities (Bernoulli?  Gauss?).  Putting them in IP format may not 
be straightforward (is a "reply" an ICMP Echo Reply? a TCP ACK?).

It looks to me as if I wanted to implement a new TCP or NUD or so, not 
easy :-)

Alex

---

From: Philip Levis <[email-masked]>
Date: Mon, 26 Oct 2009 16:41:40 -0700

On Oct 26, 2009, at 11:35 AM, Alexandru Petrescu wrote:

>> delivery ratios using a sliding window. These broadcasts contain  
>> those incoming delivery ratios. A node therefore calculates its own  
>> incoming ratios and stores (heard from others) its outgoing ratios.  
>> It uses these ratios to estimate the probability of both a data  
>> packet and its link layer ack arriving successfully. There are  
>> follow-on modifications to Srcr, such as including variance in the  
>> cost. The Srcr algorithm is described in John Bicket's Mobicom 2003  
>> paper entitled "A High Throughput Path Metric for Multi-Hop  
>> Wireless Routing." The Srcr implementation is described in his 2005  
>> paper entitled "Architecture and Evaluation of an Unplanned 802.11b  
>> Mesh Network." The software can be downloaded from the MIT Roofnet  
>> site.
>> sends a packet, 4B keeps track of whether the packet was  
>> acknowledged. It uses this binary string to estimate the number of  
>> transmissions for a packet. The 4B estimator and its implementation  
>> are described in Rodrigo Fonseca's HotNets paper entitled "Four-Bit  
>> Wireless Link Estimation." The software can be downloaded as part  
>> of recent TinyOS distributions.
>> EAR is another hybrid approach. Kyu-Han Kim's Mobicom 2006 paper  
>> "On Accurate Measurement of Link Quality In Multi-hop Wireless Mesh  
>> Networks" describes it, and his old web page has a source download  
>> for the Linux kernel.
>
> probabilities (Bernoulli?  Gauss?).  Putting them in IP format may  
> not be straightforward (is a "reply" an ICMP Echo Reply? a TCP ACK?).

The papers are pretty clear: as you're measuring a link's quality, you  
measure link behavior. Measuring TCP acks doesn't help if you're only  
sending UDP traffic. But measuring link layer frames does help.

But the basic point here is that ETX, as a metric, has a clear  
meaning. There's a variety of ways to calculate it, with differing  
degrees of accuracy in different situations, but the desired value is  
clear.

Phil

---

From: Alexandru Petrescu <[email-masked]>
Date: Tue, 27 Oct 2009 09:53:49 +0100

Philip Levis a écrit :
>>> paper entitled "A High Throughput Path Metric for Multi-Hop Wireless 
>>> Wireless Link Estimation." The software can be downloaded as part of 
>>> recent TinyOS distributions.

Ah, I suppose they use something like wifi's "ASSOCIATION RESPONSE" or 
"PROBE RESPONSE" when they say a "reply".

Do they take into account the length of this reply? (as various reply 
messages in WiFi have various lenghts) and probing with short messages 
may prove a higher success rate than long messages.

> But the basic point here is that ETX, as a metric, has a clear meaning. 
> There's a variety of ways to calculate it, with differing degrees of 
> accuracy in different situations, but the desired value is clear.

Ok.  I have to read their articles and code before agreeing they're clear.

Currently I think the desire is clear, not the desired value.

Alex