Subject: Re: [Roll] ROLL Routing Metrics - WF feed-back needed

From: Philip Levis <[email-masked]>
Date: Thu, 30 Oct 2008 10:35:56 -0700

This document is coming together really well. Generally, I think the  
metrics presented cover almost all of the cases and issues that have  
emerged in the application documents. In that way, structurally, the  
document is very sound. My comments mostly have to do with some  
assumptions on how protocols behave and a lack of specificity in a few  
cases.

Details:

Section 4 says that "An implementation MUST make use of multi- 
threshold scheme rather than fine granular metric update so as to  
avoid constant routing changes." This seems rather problematic for a  
MUST. First, it assumes that quickly adapting routes are in and of  
themselves problematic. Second, it assumes how routing protocols  
operate, that is, it assumes they don't use hysteresis to prevent  
constant changes. Based on these assumptions, it then specifies a MUST  
that limits how nodes can represent information. Finally, without a  
precise specification of what "fine granular" or "multi-threshold"  
are, it's hard to say whether something satisfies the MUST. The last  
sentence is particularly confusing: "sets a few levels to categorize  
metric values and uses the levels as discrete values instead of actual  
values." Assuming that we're talking about a finite set of bits, the  
values are discrete.

Operating from some perhaps invalid assumptions, this MUST very  
strongly limits how information can be encoded without a strong  
justification for the need of such a restriction. This seems  
problematic. It might make more sense for this to simply be an  
advisory paragraph about how values can be multi-threshold.

4.3 suggests that node workload can be 1 bit. This is a level of  
detail absent in most of the other metrics.

4.6: Is the intention that a node calculates its degree? This is very  
difficult (some might say impossible under any realistic network  
scenario). First, it requires O(n^2) communication. The observation  
that routing protocols might want to change decisions based on density  
makes sense, but by stating it is a metric that implies nodes  
calculate it.

4.7: Dynamicity of what? I think it makes sense to talk about how  
dynamic a metric is (e.g., just as TCP RTT estimation measures  
variation). Is the assumption that this is how dynamic its degree is?  
Or the temporal variation of its individual links?

The second paragraph of 4.8 seems out of place. It seems to be stating  
routing policy decisions, and has an assumption of what "sleeping"  
means (radio off an unable to receive a packet). But if that's the  
definition, this seems self-evident; your next hop shouldn't be a node  
that can't receive the packet.

5.2: This section doesn't address the issue of variable bit rates.  
E.g., if a next-generation low-power link layer supports multiple bit  
rates, possibly with different encodings, then a single node pair  
might have multiple values.

5.3: Propagation delay traditionally refers to the time it takes the  
RF wave to reach a destination. For low-power wireless, is not very  
important (1000ft is a microsecond). Perhaps this should be "Air  
time?" In that way, it would consider the bitrate and packet length.  
Combined with 5.2, you can use air time to compute expected time of  
transmission (the expected time to successfully deliver a packet),  
which studies have shown to be a very good metric.

6. I think it is outside the scope of this document to state how  
metrics should be calculated. On one hand, the advice in this section  
is well warranted; it is a bad idea to report values whose values  
change much faster than the reporting interval. But maybe this is what  
it wants to say? Of course, this is problematic when you want event- 
driven reporting. E.g., I only tell you my load when it is high.

Phil
_______________________________________________
Roll mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/roll

---

From: "MiJeom Kim" <[email-masked]>
Date: Fri, 31 Oct 2008 17:20:14 +0900

Hi, Phil, Thank you for your detail comments. Please see below in lines.

On Fri, Oct 31, 2008 at 2:35 AM, Philip Levis <[email-masked]> wrote:

> metrics presented cover almost all of the cases and issues that have emerged
> in the application documents. In that way, structurally, the document is
> very sound. My comments mostly have to do with some assumptions on how
> protocols behave and a lack of specificity in a few cases.
>
> Details:
>
> Section 4 says that "An implementation MUST make use of multi-threshold
> scheme rather than fine granular metric update so as to avoid constant
> routing changes." This seems rather problematic for a MUST. First, it
> assumes that quickly adapting routes are in and of themselves problematic.
> Second, it assumes how routing protocols operate, that is, it assumes they
> don't use hysteresis to prevent constant changes. Based on these
> assumptions, it then specifies a MUST that limits how nodes can represent
> information. Finally, without a precise specification of what "fine
> granular" or "multi-threshold" are, it's hard to say whether something
> satisfies the MUST. The last sentence is particularly confusing: "sets a few
> levels to categorize metric values and uses the levels as discrete values
> instead of actual values." Assuming that we're talking about a finite set of
> bits, the values are discrete.
>
> Operating from some perhaps invalid assumptions, this MUST very strongly
> limits how information can be encoded without a strong justification for the
> need of such a restriction. This seems problematic. It might make more sense
> for this to simply be an advisory paragraph about how values can be
> multi-threshold.
> ===> I absolutely agree with you. We need to change "MUST" to "MAY" or a
> similar word and need to rewrite to some sentences to avoid confusion. I
> would do that.

> 4.3 suggests that node workload can be 1 bit. This is a level of detail
> absent in most of the other metrics.
> ===> So do you suggest removing the part? It just tries to give a simple
> example for better understanding.

> difficult (some might say impossible under any realistic network scenario).
> First, it requires O(n^2) communication. The observation that routing
> protocols might want to change decisions based on density makes sense, but
> by stating it is a metric that implies nodes calculate it.
> ===>
>
> I think a node can figure out its degree by overhearing. So as time goes,
> it can get the number of neighbors more precisely.
>
> 4.7: Dynamicity of what? I think it makes sense to talk about how dynamic a
> metric is (e.g., just as TCP RTT estimation measures variation). Is the
> assumption that this is how dynamic its degree is? Or the temporal variation
> of its individual links?
>
> routing policy decisions, and has an assumption of what "sleeping" means
> (radio off an unable to receive a packet). But if that's the definition,
> this seems self-evident; your next hop shouldn't be a node that can't
> receive the packet.
>
> 5.2: This section doesn't address the issue of variable bit rates. E.g., if
> a next-generation low-power link layer supports multiple bit rates, possibly
> with different encodings, then a single node pair might have multiple
> values.
>
> 5.3: Propagation delay traditionally refers to the time it takes the RF
> wave to reach a destination. For low-power wireless, is not very important
> (1000ft is a microsecond). Perhaps this should be "Air time?" In that way,
> it would consider the bitrate and packet length. Combined with 5.2, you can
> use air time to compute expected time of transmission (the expected time to
> successfully deliver a packet), which studies have shown to be a very good
> metric.
>
> 6. I think it is outside the scope of this document to state how metrics
> should be calculated. On one hand, the advice in this section is well
> warranted; it is a bad idea to report values whose values change much faster
> than the reporting interval. But maybe this is what it wants to say? Of
> course, this is problematic when you want event-driven reporting. E.g., I
> only tell you my load when it is high.
>
> Phil
>
>

---

From: "MiJeom Kim" <[email-masked]>
Date: Fri, 31 Oct 2008 17:29:43 +0900

Hi, Phil, This is the rest. The gmail system has some problems. Please see
below again.

> ==> in 4.7, node dynamicity refers to node mobility, duty cycle, etc. I
> also think this is kind of ambiguous and confusing with node reliability
> (4.8). Dynamic node is not reliable and static node is more reliable
> relatively. In that sense, we might consider node dynamicity is a factor to
> affect node reliability. Combining the two metrics as one could be a
> possible solution.

> ==> Sometimes, when constructing a path, the node is awake, but in the
> middle of packet delivery, the node can fall a sleep. That's why the status
> of nodes should be monitored or predictable.

> ==> I believe the bit rates are more related to bandwidth (5.1).

> ==> I agree. Initially, I mentioned transmission delay as one affects node
> latency in 4.4. But transmission delay is a function of data rate, so it can
> be considered as a link attribute.

> ==> I couldn't get what you try to say here. So could you let me know your
> point?

---

From: Philip Levis <[email-masked]>
Date: Fri, 31 Oct 2008 09:13:30 -0700

On Oct 31, 2008, at 1:20 AM, MiJeom Kim wrote:

>
> 4.6: Is the intention that a node calculates its degree? This is  
> very difficult (some might say impossible under any realistic  
> network scenario). First, it requires O(n^2) communication. The  
> observation that routing protocols might want to change decisions  
> based on density makes sense, but by stating it is a metric that  
> implies nodes calculate it.
> ===>
> I think a node can figure out its degree by overhearing. So as time  
> goes, it can get the number of neighbors more precisely.

That would be true if degree were defined as the number of neighbors a  
node can hear. However, it's defined as

    Node degree is the number of neighbors that can receive a message
    from the node directly.

Unless you assume asymmetric links do not exist, this requires each  
node to report the set of nodes from which it hears messages, so those  
nodes can calculate their degree. It also requires a node to maintain  
state linear in the number of its neighbors, which is problematic.

Phil