Subject: Re: [Roll] ETX metric

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 19 Oct 2009 22:47:50 +0200

P. Levis wrote recently:

> On Oct 15, 2009, at 2:16 PM, Alexandru Petrescu wrote:
>
>> Philip Levis a écrit :
>>> On Oct 15, 2009, at 12:49 PM, Alexandru Petrescu wrote:
>>>> Philip Levis a écrit :
>>>>> On Oct 15, 2009, at 12:27 PM, Alexandru Petrescu wrote:
>>>>>> Philip Levis a écrit :
>>>>>>> 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,
>>>>>>
>>>>>> 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?
>>>>> 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
>>>>
>>>> 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.
>>> 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.
>>
>> 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).
>
> 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.

That's what you believe, right?  You could state it's not your 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.

Which bill?

> Furthermore, the cost of sending a frame can be highly variable.

That's why I propose a range of min-max.

> 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.

I agree, but we could define the distinction to be accounted for, i.e.
the values recorded consider only the cases when ends are in sync.

If you talk about dormant modes - I think it's a huge topic touching on
about everything ROLL does.  Does RPL take this into account with its
timers?

> 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.

I think we can fix that.  Precision is large enough.  Range could be
limited enough.  This is something we could look at closer.

> Does that make sense?

YEs it does in a way, except you still don't propose an energy metric
that you feel like you'd implement.  YOu keep raising objections about
my proposal.  I could raise objections about your proposal once you make it.

Alex

> Phil

---

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

>> doesn't quite fit the bill.

I'm sorry -- it's a colloquialism. I meant "For this reason, I think  
that your proposal on a 1280-byte packet isn't well suited to  
maximizing network lifetime." That doesn't mean it's not useful, or  
well suited to other administrative concerns. It's just that "low  
power" is generally -- but not always -- about maximizing network  
lifetime.

> about everything ROLL does.  Does RPL take this into account with its

I think this has come up on the list maybe a half-dozen times or so  
(or more): this is a link layer operation. The time scales involved  
are not in the same order of magnitude as ROLL timers.

> my proposal.  I could raise objections about your proposal once you  

I know that the IETF is political at times, but I'd hope objections  
would be raised on technical concerns, rather than authorship. I don't  
care whose proposal we adopt: I just care that it works well, can be  
implemented easily, and meets application/administrative requirements.

Phil

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 22 Oct 2009 18:04:38 +0200

Philip Levis a écrit :
> that your proposal on a 1280-byte packet isn't well suited to maximizing 
> network lifetime."

Right... so the "bill" was to maximize the network lifetime.

However, I do think the 1280byte energy expenditure metrics _is_ suited 
to maximize network lifetime.

I think network lifetime is improved by whatever can reduce the energy 
spent to reach a destination, and energy metrics for links are for that.

I am not sure whether I have already posted this example:

                        -------
                       |Router2|
                       /-------\
             IPv6 Link1         \IPv6 Link3
    -----     -------/           \-------     -----
   |Host1|---|Router1|-----------|Router3|---|Host2|
    -----     ------- IPv6 Link2  -------     -----

If the energy metrics of IPv6 Link1 and 3 indicate that path to consume 
less energy - then taking it into account rather than the hopcount 
metric (IPv6 Link2) surely contributes to extending the network lifetime.

This is what happens when Link1 and 3 are bluetooth and Link2 is wifi.

Even if one worries of sync'ed/notsync, or dormant/awake - the inherent 
energy consumption of these two techs is so different that decisions are 
easily made.

I am not sure what you understand by network lifetime - is it more like 
node lifetime?

> That doesn't mean it's not useful, or well suited to 
> other administrative concerns. It's just that "low power" is generally 
> -- but not always -- about maximizing network lifetime.

What is a network to you?

To me is a set of links (more than the set of nodes).

E.g. I don't worry about how much energy a node spends to access its 
memory but I do worry how much a node spends to send a packet.

Put another way: I don't worry if the set of nodes in a network consume 
all their batteries simply counting to infinity, but I do care if the 
network nodes run out of their batteries because they send out packets 
through energy-hungry paths.

> I think this has come up on the list maybe a half-dozen times or so (or 
> more): this is a link layer operation. The time scales involved are not 
> in the same order of magnitude as ROLL timers.

(Well of course depends how they are encoded.  I know for timers in ND 
have been tweaked for Mobile IP to deal with orders of magnitude of 
link-layers.)

My point was to say the "dormant/paging" aspects are often mentioned 
against about anything.  No reason to take it into account here.

> implemented easily, and meets application/administrative requirements.

YEs, right...

Let's see later...

Alex

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 22 Oct 2009 13:20:25 -0400

Date: Thu, 22 Oct 2009 18:04:38 +0200
   From: Alexandru Petrescu <[email-masked]>

Maximizing the lifetime of a network has at least as much to
do with energy supply as with energy use.

Suppose there are two routes, one of which makes use of a
battery-powered relay and the other of a line-powered relay,
but are otherwise identical.  It is quite likely that the
battery-powered device, whose designer had minimal energy
consumption as a high priority, uses less energy to send a
message than the line-powered device.  On the other hand,
relaying via the battery-powered device shortens the life of
the network, while using the line-powered device does not.

                           -Richard Kelsey

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 22 Oct 2009 20:16:38 +0200

> the network, while using the line-powered device does not.

Sounds logical.

Sounds as a potential contradiction between the paths computed according 
to link energy metrics vs node energy metrics.  I.e. the case you 
describe may shorten the network lifetime if link energy metrics were 
used and, on the contrary, extend the network lifetime if _node_ energy 
metrics were used.

You sure realize I could describe the reverse case where link-energy 
metrics were more advantageous for network lifetime.

Maybe a good routing protocol may be able to make proper use of both.

I personally tend to consider link energy metrics more, because there 
exist many other link-specific metrics (qos, latency) whereas there 
exist no CPU-specific metric for IP networking. (or am I missing something).

Alex