Subject: Re: [Roll] Polling WG for adoption of Metrics Draft

From: [email-masked]
Date: Thu, 2 Apr 2009 09:33:48 -0500

Good draft.  Comments below.  Mainly grammatical and typos.  I approve 
moving this document forward.

p5.  "It is also worth mentioning that it fairly common for link in LLNs 
to ..."   s/b  "It is also worth mentioning that it is fairly common for 
links in LLNs to ..."

p6/s3.  "In LLNs, it is not uncommon.."  might read better as "In LLNs, it 
is common"

p6/s 3.1 "Units to be determined" seems like an editors note that should 
be deleted.

p6/s 3.2 This is somewhat of an erroneous statement and merits more 
consideration.  While it might be true that the communication processing 
eats up 10% of the processing power, you fail to note that in LLNs the 
devices deployed have a primary application (e.g controlling HVAC) that 
will require most of the processor's bandwidth.  This is somewhat 
different than other communication networks where there are dedicated 
communication device deployed such as switches and routers.

I think the CPU resource metric is important, and would read better if it 
stated that the metric will limit the communication processing to less 
than or equal to 10% of the processor's bandwidth.  That saves the other 
90% for the application layer.

p6.s3.3  "scavening" s/b "scavenging"

p6.s3.3  Also in the same sentence, you are noting that the routing path 
may indeed be a longer (more hops) path to to steer around energy starved 
devices.  This is ok.  However, you then note that the devices that are 
not energy starved are "mains-powered nodes or nodes equiped with energy 
scavenging".  In my experience energy scavenged devices have even less 
available disposable energy than battery powered devices.  They should NOT 
be considered in the same light as mains-powered devices.

p8/s3.4 "Algorithms used to set the overload bit and to compute path to
   potentially avoid node..." s/b "Algorithms used to set the overload bit 
and to compute paths to
   potentially avoid nodes ... 

p8/s3.5 "Applications where high directional data flow is expected in a
   regular basis..." s/b "Applications where high directional data flow is 
expected on a
   regular basis..."

p8/s4. "Even in case ..." s/b "Even in the case ..."

p9/s6.  "shoudl" s/b "should"

"David E. Culler" <[email-masked]> 
Sent by: [email-masked]
03/24/2009 02:14 PM

To
[email-masked]
cc

Subject
[Roll] Polling WG for adoption of Metrics Draft

The ROLL charter includes the following work item:
* Specification of routing metrics used in path calculation. This 
includes static and dynamic link/node attributes required for routing in 
LLNs.

The following draft has been submitted and discussed at the ROLL WG 
meeting during IETF 74:
* http://tools.ietf.org/html/draft-mjkim-roll-routing-metrics-03

The consensus at the meeting was that it was ready to WG polling.  I 
would like to poll the WG for adoption of this draft as a WG draft. 
Please respond to the list to establish consensus. 

Also, please provide feedback to the authors on the draft through the 
list.

Thanks,

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

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 24 Apr 2009 12:21:24 +0200

Dear ROLLers, let me revive this thread...

I would like to propose a different perspective of an energy metric.
This perspective is different than in
draft-mjkim-roll-routing-metrics-03, which proposes to quantify the
Residual Energy in a node.

Here I need Energy for links, not for nodes.

This energy metric for a link says how much energy is needed to send (or
rcv) an IPv6 MTU packet on that particular link.  It assumes that 
regardless of the type of Node device, the same amount of energy is 
needed to send 1280bytes on a particular link-layer technology.

For example, my LiIon-powered PDA needs 500mW to send 1280bytes on WiFi,
and the mains-powered AP needs the same amount of energy to send 1280bytes.

This could be encoded as a min-max value: a device needs between min and
max Watts to send a packet on this link.

Any oppinion on this "link" energy metric kind?

Alex

Alexandru Petrescu a écrit :
> Kris Pister a écrit : [...]
>> Below are some candidate metrics with more detail.  I've made the 
>> assumption/recommendation that the node can summarize it's energy
>> in terms of packets that it can forward (short packets?  long
>> packets? Usually there's an affine relationship between packet
>> length and energy consumption), and it's power consumption in units
>> of packets per second.
> 
> Energy akin to MTU?
> 
> For a particular link, energy representation for a link as MTU.  This
>  computer's interface needs x Watts to send a typical 1280byte IPv6 
> packet and y Watts to receive such.
> 
> (Watt and not Joule for this case).
> 
> These x and y figures are usually the same for all interfaces
> attached to that link, independent of computer - a server would spend
> same amount of energy to send that packet on that link, as a
> micro-controller on a PDA.
> 
> Which would give to represent energy in the RA, as MTU is.
> 
> Alex
> 
> 
> _______________________________________________ Roll mailing list 
> [email-masked] https://www.ietf.org/mailman/listinfo/roll
>

---

From: Michele Rossi <[email-masked]>
Date: Fri, 24 Apr 2009 16:04:49 +0200

I all,

I'm new to the ROLL mailing list.

My personal opinion is that we need both energy metrics.
1. A metric is needed for sure in oder to characterize the residual
energy of the nodes (e.g., related to battery level). I'm thinking of
a sensor network, for instance, where you may want to perform routing
exploiting energy rich nodes in order to prolong the network lifetime.
As a further example, if there are two nodes that performs the same
service, you may want to use the one with higher residual energy in
order to balance energy consumption.
2. A metric for the energy expenditure in sending an IPv6 packet over
the links is however also useful. As Alex suggests this metric is
related to the type of PHY interface, e.g., energy consumption for
IEEE802.5.4 differs from that of IEEE802.11g. However, I also think
that in homogeneous wireless nets (where all or most of the nodes have
the same radio interface) it might be also useful to define a metric
weighing the expected amount of energy needed to transmit a packet
between any two given nodes A and B. This metric depends on the energy
consumed in sending the packet as well as on the status of the link,
i.e., on the overall packet error probability over the link and hence
on the total number of retransmissions to correctly deliver this
packet. Here you may consider the well known Expected Transmission
Count metric ETX [1] or its variants, see [2].

[1] D. De Couto, D. Aguayo, J. Bicket, and R. Morris, “A high
throughput path metric for multi-hop wireless routing,” in Proc.
MobiCom, 2003.

[2] Koksal, C.E.; Balakrishnan, H., "Quality-Aware Routing Metrics for
Time-Varying Wireless Mesh Networks," Selected Areas in
Communications, IEEE Journal on, Volume 24, Issue 11, Nov. 2006
Page(s):1984 - 1994.

I hope you'll find this useful.

Respectfully,

Michele.

On Fri, Apr 24, 2009 at 12:21 PM, Alexandru Petrescu
<[email-masked]> wrote:
> rcv) an IPv6 MTU packet on that particular link.  It assumes that regardless
> of the type of Node device, the same amount of energy is needed to send
> 1280bytes on a particular link-layer technology.
>
>>  computer's interface needs x Watts to send a typical 1280byte IPv6 packet
>> and y Watts to receive such.
>>

-- 
Michele Rossi - Assistant Professor, "SIGNET Group"
Dep. of Inf. Engineering, University of Padova, Italy
Office: +39 049 827 7915 - Fax: +39 049 827 7699
[email-masked] - http://www.dei.unipd.it/~rossi

---

From: Richard Kelsey <[email-masked]>
Date: Fri, 24 Apr 2009 11:52:06 -0400

Date: Fri, 24 Apr 2009 16:04:49 +0200
   From: Michele Rossi <[email-masked]>

It isn't clear to me what the goal is.  Prefering devices
with higher residual energies makes sense if the goal is to
have all devices run out of energy at about the same time.
This can make it hard to predict the lifetime of any one
device.  A new device added to an old network is likely to
have a much shorter lifetime than the original devices.

In my experience battery-powered devices are usually
designed and marketed with some particular minimum lifetime.

If device has sufficient energy to relay X messages and has
to last Y years, then on average it can relay X/Y messages
per year, or X/12Y messages per month, or X/365 messages per
day, and so on.  Relating the capacity to the battery level
is equivalent to averging over the lifetime of the device.

Desiging in a minimum lifetime would require rationing
energy in smaller allotments.  For example, a device that
was expected to last two years might be limited to using
only 1/24 of its energy each month.  Such a device would
report the percentage of the current month's energy
remaining, not the percentage of total energy.  In the limit
this makes battery powered device behave like energy
scavenging devices, with a bandwidth limit rather than an
energy limit.

Using a bandwidth metric instead of a residual energy metric
could lead to more stable routing.  Routes would need to
change only in response to the topology changes, and not in
response to the passage of time alone.

                                 -Richard Kelsey

---

From: Mukul Goyal <[email-masked]>
Date: Fri, 24 Apr 2009 11:50:05 -0500 (CDT)

I think that linking routes too tightly to node battery levels may prove to be counter-productive. I think a routing protocol should allow a node to decline being part of a route based on its local conditions (such as remaining battery levels) without requiring the node to send this information to other nodes. The criteria used by a node to determine if it wants to be part of a route or not should be local, i.e., the node should decide which metric would it consider. The routing protocol should not impose a particular metric on the nodes. 

Thanks
Mukul

----- Original Message -----
From: "Richard Kelsey" <[email-masked]>
To: [email-masked]
Cc: [email-masked]
Sent: Friday, April 24, 2009 10:52:06 AM GMT -06:00 US/Canada Central
Subject: Re: [Roll] Energy metric for link (was: Polling WG for adoption of	Metrics Draft)

                                 -Richard Kelsey

---

From: Michele Rossi <[email-masked]>
Date: Fri, 24 Apr 2009 23:31:09 +0200

Hi all,

thanks a lot for your comments.

I understand the arguments from Richard and I also think that defining
a routing protocol that *always* makes routing decisions based on
residual energy of the nodes is not the way to go. I also agree with
the fact that linking routes to tightly to battery levels may be
counter-productive (see email by Mukul).

My point is just that residual energies should not be completely neglected.

In some cases, we may want to extend the lifetime of some specific
nodes due to their location in the network or to their specific
function, and residual energies can be used as a metric to implement
this.
Thus, I agree with Mukul in that a node could locally decide whether
to participate or not in the routing based on local metrics, such as
its residual battery level (among others). As an example, nodes in a
sensor network that are sensing an important event and that are also
running out of battery could decide to use their energy to send their
measurements to a gathering point rather than relaying messages from
other nodes.

I think a good protocol should also allow this type of optimization, if needed.

Finally, I agree with Richard in that using a link metric would lead
to more stable routing.

So my view is that the routing protocol should be flexible enough to
allow routing using local and/or link metrics. The implementer could
then decide which option best suites its specific application.

Overall, local metrics may be used to decide whether a node
participates in the routing process and link metrics could be used for
path selection (considering the nodes that decide to participate).

Best,

Michele.

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 27 Apr 2009 11:04:27 -0400

Date: Fri, 24 Apr 2009 23:31:09 +0200
   From: Michele Rossi <[email-masked]>

This requires a mechanism to determine which nodes should
use their residual energy to originate messages and which
nodes should use their residual energy to forward messages.

   Thus, I agree with Mukul in that a node could locally
   decide whether to participate or not in the routing based
   on local metrics, such as its residual battery level
   (among others). As an example, nodes in a sensor network
   that are sensing an important event and that are also
   running out of battery could decide to use their energy
   to send their measurements to a gathering point rather
   than relaying messages from other nodes.

How does a node determine whether its measurements are more
or less important than some other device's measurements?
Not participating in routing makes sense only if the
device's local measurements have a higher priority than
other devices'.  This doesn't seem like a decision that can
be made locally.

If every node decides to reserve the last X% of its battery
for its own measurements, then a network is likely to
shut down as soon as a significant number of nodes is down to
X% battery.  This make sense only if X is zero.  Why shut
down when there is still energy available?

   Finally, I agree with Richard in that using a link metric
   would lead to more stable routing.

That wasn't the point I was trying to make.  My point was
that it makes more sense to treat a battery powered device
as being bandwith limited, with the limit determined by its
initial energy and its design lifetime, than as a device
that has one behavior for the first part of its lifetime and
then switches to some other behavior when its battery gets
low.  How this is reflected in a metric is a separate issue.

For example, a battery-powered node could dynamically adjust
its cost(s) to be as low as possible within its bandwidth
limit.  If it forwards too many messages it pushes the cost
up; too few and it reduces its cost, down to some floor
determined by its non-energy-related costs.  This would
maximize the utility of the network while ensuring that
the device lasts as long as it is meant to.

                                 -Richard Kelsey

---

From: Alexandru Petrescu <[email-masked]>
Date: Tue, 28 Apr 2009 15:35:50 +0200

Richard Kelsey a écrit :
> initial energy and its design lifetime,

This - relating bandwidth uniquely to battery-level - seems a stretch to 
me.  Supposedly, the way batteries deplete (the time it takes to send a 
1280bytes at a high bandwidth) vary largely with other factors such as 
battery age and number of recycle duties.

However, I do find it meaningful to relate the energy for transmission 
uniquely to the link type and to the number of bytes to be transmitted.

Something like:

Sending 1280bytes on this link (802.15.4-XY-enhancement-bandwidthZ) 
takes between 20mW and 200mW, no more no less, independent of the 
battery level, independendent of the memory size, independent of 
collisions, independent of daytime.

-sending
-1280bytes
-802.15.4-variantX-enhancementY-bandwidthZ
-min 20mW
-max 200mW

The values of min and max could be found by measurement.

Alex

  than as a device

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 28 Apr 2009 14:15:31 -0400

Date: Tue, 28 Apr 2009 15:35:50 +0200
   From: Alexandru Petrescu <[email-masked]>

Battery level need be only one input into the bandwidth
calculation.  Basically, each node would make its own
determination as to the bandwidth it could support, taking
into account whatever local state that it deemed relevent.
That limit could then be both reported to other devices and
enforced by the node itself.

In making routing decisions, what matters in the end is the
bandwidth and latency through each possible relay.  I think
it would be both simpler and more effective to have each
node be responsible for determining its own bandwidth and
latency constraints rather than have each node report its
internal condition (link and battery parameters, for
example) and have some other device translate those into
bandwidth and latency constaints.

                              -Richard Kelsey

---

From: Alexandru Petrescu <[email-masked]>
Date: Wed, 29 Apr 2009 16:18:51 +0200

Richard Kelsey a écrit :
> Date: Tue, 28 Apr 2009 15:35:50 +0200 From: Alexandru Petrescu
> <[email-masked]>
> 
> Richard Kelsey a écrit :
>> 
>> That wasn't the point I was trying to make.  My point was that it
>> makes more sense to treat a battery powered device as being
>> bandwith limited, with the limit determined by its initial energy
>> and its design lifetime,
> 
> This - relating bandwidth uniquely to battery-level - seems a stretch
> to me.  Supposedly, the way batteries deplete (the time it takes to
> send a 1280bytes at a high bandwidth) vary largely with other factors
> such as battery age and number of recycle duties.
> 
> Battery level need be only one input into the bandwidth calculation.
> Basically, each node would make its own determination as to the
> bandwidth it could support, taking into account whatever local state
> that it deemed relevent. That limit could then be both reported to
> other devices and enforced by the node itself.

Richard, I can understand a node would need more battery to transmit at
higher speed (higher bandwidth).

I can also see a node settling for less transmission speed if it had
less battery available.

You seem to say nodes would exchange each other's such limits and maybe 
elect the lowest common denominator for that limit, and all conclude to
transmit at that bandwidth limit.

Sounds as an idea which should be listed too.

It's different than the energy metric for the link idea I suggested earlier.

May I then ask: what should be encoded in the metric?  Bandwidth? 
expressed how on bits/secods?  Millseconds?

Alex

> In making routing decisions, what matters in the end is the bandwidth
> and latency through each possible relay.  I think it would be both
> simpler and more effective to have each node be responsible for
> determining its own bandwidth and latency constraints rather than
> have each node report its internal condition (link and battery
> parameters, for example) and have some other device translate those
> into bandwidth and latency constaints.
> 
> -Richard Kelsey
>

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 29 Apr 2009 11:45:26 -0400

Date: Wed, 29 Apr 2009 16:18:51 +0200
   From: Alexandru Petrescu <[email-masked]>

That is not what I am suggesting.

Given its current battery level, design lifetime, internal
requirements, and so forth, a battery-powered device has
some amount of energy that it is willing to expend in
forwarding messages for other devices.  Combining this with
the energy efficiency of the link you get the bandwidth that
the device is willing to make available for forwarding
messages.  For example, a device might be willing to forward
ten 1280-byte messages every hour.

Regardless of what information is exchanged between devices,
in the end the decision comes down whether to forward a
particular packet via a particular neighbor.  Rather than
get all of the details of the neighbor's state and making
some judgement call, it seems much simpler just to find out
the rate at which the neighbor is willing to forward
packets.

   May I then ask: what should be encoded in the metric?
   Bandwidth?  expressed how on bits/secods?  Millseconds?

Byte/second would be fine, plus a per-packet overhead in
bytes.  For example, 1k bytes/second plus a 100 byte
per-packet overhead would mean that the device was willing
to forward one 900-byte packet or two 400-byte packets every
second.  The overhead is not the actual size of any link
headers, but reflects the additional per-packet cost
incurred by the device.  This might include the expected
cost of PHY backoffs, for example.

                                      -Richard Kelsey

---

From: Alexandru Petrescu <[email-masked]>
Date: Wed, 29 Apr 2009 18:49:31 +0200

> cost of PHY backoffs, for example.

Richard,

Is there any other place RFC/draft which specifies such a bandwidth 
metric encoding that we could reuse in ROLL?  (I've looked quickly at 
RIP and OSPF and couldn't find).

Alex

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 29 Apr 2009 13:53:36 -0400

Date: Wed, 29 Apr 2009 18:49:31 +0200
   From: Alexandru Petrescu <[email-masked]>

Alex,

Not that I am aware of.  The closest that I know of is the
OLSRv2 'willingness' metric, for which no units are
specified.  One difficulty is that it is really a node cost,
not a link cost, and most IETF protocols do not have metrics
for node costs.

An alternative would be for a node to adjust its advertised
link costs in order to limit the number of messages that
it was asked to forward.  Rather than advertising a maximum
acceptable bandwidth, the node would increase its advertised
link costs until the actual bandwidth dropped to an
acceptable level.  If the actual bandwidth was low enough,
1/2 the acceptable maximum, say, the node could reduce its
advertised costs.
                              -Richard Kelsey