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

From: Alexandru Petrescu <[email-masked]>
Date: Wed, 13 May 2009 14:51:43 +0200

REviving older discussions...
Miguel Sanchez a écrit Octobre 2009:
> Hi Mijeom,
> 
> 2008/10/31 김미점[USN연구담당] <[email-masked]>:
>> 
>> Hi, Miguel,
>> 
>> As I pointed out in my early posting, "Propagation delay" is just
>> time a packet to traverse a link. So it doesn't include
>> transmission time. On the
> 
> Ok, I see, from the current wording I was not sure whether 
> transmission time was included or not.
> 
>> other hand, node latency comprises transmission time, packet
>> processing time and queuing delay in section 4.4. In section 5.3,
>> path latency = propagation delay of all links + node latency of all
>> nodes along the path. Since propagation delay is negligible as
>> Philip wrote and it's hard to get its value, we might exclude the
>> propagation delay from routing metrics. Need more opinions.
>> 
>> Regarding the energy metric, I believe that there is a trade-off
>> between multi-threshold approaches and using numerical values. But,
>> for practical solutions, we might need to compromise precision by
>> choosing multi-threshold mechanisms.
> 
> The number of bits used for encoding energy information seems like an
>  implementation issue to me.

YEs, and here we talk implementation.

I propose to use 32bit single-precision floating point numbers, in
network-byte order, as Joules.  This number is the Energy needed to send
a packet.

What do you think?

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: Wed, 13 May 2009 14:50:04 +0200

Miguel Sanchez a écrit :
> Hi JP,
> 
> On Thu, Oct 30, 2008 at 10:02 AM, JP Vasseur <[email-masked]> wrote:
>> Hi Miguel,
>>
>>
>> On 10/30/08 9:29 AM, "Miguel Sanchez" <[email-masked]> wrote:
>>
>>> I've got a terminology problem with "propagation delay" (5.3), while
>>> defined in the draft (and later defined is path propagation) a new
>>> meaning is given to the term. (For short range communications
>>> transmission time could be used instead).
>> Let me make sure that I get your point here. The document says:
>> "Propagation delay is the time taken for the packet to traverse the
>> link from the source node to the target node."
> 
> Definition is clear enough but what bothers me is that "propagation
> delay" equals link length over propagation speed in my book.
> Apparently the meaning here is more like transmission time +
> propagation delay (the latter as I've defined here).
>> I think that the notion of source and target node is confusing and the text
>> should read:
>>
>> " Propagation delay is the time taken for the packet to traverse the
>> link. "
> 
> Do you mean including the transmission time?
> 
>> Does that clarify ?
>>
>>> Regarding the energy metric I can see a problem if only one value is
>>> given (ie: remaining enery). The value might be infinite to signal
>>> nodes without energy restrictions, but for the remaining nodes, a
>>> single value may not be enough. Let me elaborate on this with an
>>> example: A node may have an overall lower consumption than another
>>> one. If the former has slightly less energy than the second one, then
>>> choosing the later may not be the best choice for long term
>>> survivability of the network (this could be addressed by advertising
>>> expected node lifetime instead of node's remaining energy).
>>>
>> Absolutely. The remaining energy metric may be difficult to interpret and
>> the expected lifetime may be hard to compute.
>>
>>>  On the other hand, without knowing the initial energy, it's not
>>> possible to know what fraction of the original energy is the remaining
>>> one. This could be addressesed advertising remaining energy as a
>>> percentage (contrary to the above paragraph approach).
>> Yes or ... We may use a simple multi-threshold mechanisms: "Low, Medium,
>> High" where:
>> "LOW: avoid this node if possible"
>> "Medium: no particular constraint"
>> "HIGH: favor this node"
>>
>> Avoid/favor should of course be interpreted in the context of energy.
>>
>> What do you think ?
> I think the high/medium/low approach may hurt some implementations
> over a numerical value (i.e: choosing between two nodes with high
> value).
>> But ... In any case, we need to avoid the definition of metric that are
>> implementation/node dependent. The way you model energy cannot be
>> standardized.
> 
> We've to find a way to create an standard way for energy reporting. Haven't we?

YEs we have to.

Alex

> 
>> We also need to ensure that nodes use consistent metrics (a fairly common
>> problem).
>>
>>> And last, in certain network setups some nodes may be easy to replace
>>> while others are not. You may want batteries to die out more often on
>>> nodes that can have their batteries replaced easily even though other
>>> nearby nodes have more energy available.
>> Absolutely, as defined in the industrial routing requirement document. This
>> should be an administrative constraint.
>>
>> Energy metric need to be
>>> complemented with other metrics. (Network survivability is not the
>>> only factor we have to take into account).
>> Right. Did you have a look at the other ones ?
> I mostly agree with the rest, perhaps I'd chose PER (packet error
> rate) metric instead of BER.
> 
> Regards,
> 
> Miguel Sánchez
> 
>> Thanks.
>>
>> JP.
>>
>>> Regards,
>>>
>>> Miguel Sánchez
>>>
>>>
>>> On Thu, Oct 30, 2008 at 8:55 AM, JP Vasseur <[email-masked]> wrote:
>>>> Good, feel free to comment on other metrics, we need to make a careful
>>>> decision on which one we keep, remove, add, ...
>>>>
>>>> Thanks for the comments.
>>>>
>>>> JP.
>>>>
>>>>
>>>> On 10/30/08 8:43 AM, "Mischa Dohler" <[email-masked]> wrote:
>>>>
>>>>> Hola Miguel, JP, all,
>>>>>
>>>>> They are all already either implicitly or explicitly part of the specs. If
>>>>> we start thinking however which one to explicitly include and which to
>>>>> exclude, remaining energy is definitely a vital metric.
>>>>>
>>>>> Mischa.
>>>>>
>>>>>
>>>>>
>>>>> -----Original Message-----
>>>>> From: [email-masked] [mailto:[email-masked]] On Behalf Of JP
>>>>> Vasseur
>>>>> Sent: Thursday, October 30, 2008 8:30 AM
>>>>> To: Stan Ratliff (sratliff); Miguel Sanchez; ROLL WG
>>>>> Subject: Re: [Roll] ROLL Routing Metrics - WF feed-back needed
>>>>>
>>>>> Hi,
>>>>>
>>>>>
>>>>> On 10/29/08 2:54 PM, "Stan Ratliff (sratliff)" <[email-masked]> wrote:
>>>>>
>>>>>> I absolutely agree with using remaining-energy. Would also
>>>>>> suggest bandwidth on the link (current and maximum), BER,
>>>>>> and latency.
>>>>> All currently defined also.
>>>>>
>>>>> Still I think that we need to think a bit more about this. I personally
>>>>> question whether we need these metrics or not. Designing a routing protocols
>>>>> with so many dynamic metric is not trivial.
>>>>>
>>>>> For the sake of illustration propagation delay may greatly vary if queueing
>>>>> delays are taken into account. So does the bandwidth.
>>>>>
>>>>> Thus we do need to make sure that we do not end up with a wide set of
>>>>> dynamic metrics that will unavoidably lead to routing instabilities.
>>>>>
>>>>> Other comments from the WG ?
>>>>>
>>>>> Thanks.
>>>>>
>>>>> JP.
>>>>>
>>>>>> Regards,
>>>>>> Stan
>>>>>>
>>>>>> -----Original Message-----
>>>>>> From: [email-masked] [mailto:[email-masked]] On Behalf Of
>>>>> Miguel
>>>>>> Sanchez
>>>>>> Sent: Wednesday, October 29, 2008 6:59 AM
>>>>>> To: ROLL WG
>>>>>> Subject: Re: [Roll] ROLL Routing Metrics - WF feed-back needed
>>>>>>
>>>>>>> So we would need your feed-back, bearing in mind that we may want to only
>>>>>>> keep the metrics that are critical to LLNs.
>>>>>>>
>>>>>> Not sure what is the best way but being able to use remaining-energy
>>>>>> as a parameter for routing decisions maybe useful (if routing
>>>>>> contemplates that). Remaining node energy may be added to other
>>>>>> metrics (delay, traffic, PER, etc).
>>>>>>
>>>>>> Cheers,
>>>>>>
>>>>>> Miguel Sánchez
>>>>>> Universidad Politécnica de Valencia, Spain
>>>>>> _______________________________________________
>>>>>> Roll mailing list
>>>>>> [email-masked]
>>>>>> https://www.ietf.org/mailman/listinfo/roll
>>>>>> _______________________________________________
>>>>>> Roll mailing list
>>>>>> [email-masked]
>>>>>> https://www.ietf.org/mailman/listinfo/roll
>>>>> _______________________________________________
>>>>> Roll mailing list
>>>>> [email-masked]
>>>>> https://www.ietf.org/mailman/listinfo/roll
>>>>>
>>>> _______________________________________________
>>>> Roll mailing list
>>>> [email-masked]
>>>> https://www.ietf.org/mailman/listinfo/roll
>>>>
>> _______________________________________________
>> 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: Miguel Sanchez <[email-masked]>
Date: Wed, 13 May 2009 19:05:15 +0200

On Wed, May 13, 2009 at 2:51 PM, Alexandru Petrescu <
[email-masked]> wrote:

>> Ok, I see, from the current wording I was not sure whether transmission
>> time was included or not.
>>

I'm not entirely happy with floating point numbers if 8-bit micro
controllers  with not so much program memory (a few KBytes) are involved.
However I do like the idea of using Energy units to express Energy values
(whether it is Joules or mJ integers are easier).

OTOH, the estimate of the battery capacity may come from a combination of
usage recording and battery voltage (and maybe current) measurement (which
is performed at a limited resolution), so a floating-point energy
representation could be a bit overkill here.

Just my two cents,

Miguel Sánchez

---

From: Alexandru Petrescu <[email-masked]>
Date: Wed, 13 May 2009 20:15:18 +0200

Miguel Sanchez a écrit :
[and some people replied]
>> network-byte order, as Joules.  This number is the Energy needed to 
>> send a packet.
>> 
>> What do you think?
> 
> 
> controllers  with not so much program memory (a few KBytes) are 
> involved.  However I do like the idea of using Energy units to 
> express Energy values (whether it is Joules or mJ integers are 
> easier).
> 
> OTOH, the estimate of the battery capacity may come from a 
> combination of usage recording and battery voltage (and maybe 
> current) measurement (which is performed at a limited resolution), so
>  a floating-point energy representation could be a bit overkill here.

I agree the energy estimation may come from measurement happening
straight on the sensor node (in addition to offline measurement
performed potentially in the lab, with sophisticated equipment).  This
may involve measurement of the battery voltage while a packet is sent.
Chipsets of PMU (Power Management Unit) do offer this as integers, not
floats.  Sure some constrained devices don't have PMU but some do have.

At a limit, an 8bit controller could perform floating-point comparisons
even if it had only 8bit registers, depends how it's programmed.

The issue I have with an integer to represent energy is that it has a
limited range.  For example a 16bit integer may represent it as between
0 and 65535 mili-Volt.  And this may correspond linearly to an Energy
value between 0 and 65535 qualifier-Joule (qualifier may be micro, nano,
mili, etc.) - but it would not allow to represent both a Joule and a
micro-Joule.

Or, the lowpower wireless links and the e.g. GSM  can differ in orders
of magnitude.

This is of course subject to discussion.

Alex

> 
> Just my two cents,
> 
> Miguel Sánchez
> 
> 
> 
> 
> Alex
> 
> 
> 
> 
> _______________________________________________ Roll mailing list 
> [email-masked] <mailto:[email-masked]>

---

From: Michael Richardson <[email-masked]>
Date: Wed, 13 May 2009 14:22:59 -0400

>>>>> "Miguel" == Miguel Sanchez <[email-masked]> writes:
    Miguel> I'm not entirely happy with floating point numbers if 8-bit
    Miguel> micro controllers with not so much program memory (a few
    Miguel> KBytes) are involved.  However I do like the idea of using
    Miguel> Energy units to express Energy values (whether it is Joules
    Miguel> or mJ integers are easier).

  Floating point is expressed as mantissa * 2^(exponent).
  I wonder if the mantissa is even important.  

  Does it matter if it costs 10 Joules or 20 Joules to transmit: the
point is that it costs O(10^1)?

-- 
]     Y'avait une poule de jammé dans l'muffler!!!!!!!!!        |  firewalls  [
]   Michael Richardson, Sandelman Software Works, Ottawa, ON    |net architect[
] [email-masked] http://www.sandelman.ottawa.on.ca/ |device driver[
] panic("Just another Debian GNU/Linux using, kernel hacking, security guy"); [

---

From: Alexandru Petrescu <[email-masked]>
Date: Wed, 13 May 2009 21:32:23 +0200

Michael Richardson a écrit :
> Floating point is expressed as mantissa * 2^(exponent). I wonder if
> the mantissa is even important.

If mantissa not important then we should propose a value and agree with
it.  Because it could be 1, 0.1, 2, etc.

Mantissa could be important - it would allow finer representation (many
digits after comma) between e.g. exa-Joule and ato-Joule, i.e. both a
121987,349164 exa-Joules and 0,0972734902 ato-Joules could be represented.

I do understand an Energy value for a node of ROLL is very low (I expect
it in the range of micro-Joules for 1280 bytes on WiFi).  But a ROLL
connected to the Internet should take paths into consideration too,
maybe a sattelite link, which requires of course more than just
micro-Joules... I must say I don't know how much.

If I knew the maximum Energy value for sending an 1280 byte packet on
the most hungry satellite link were 1 Joule, then of course the metric
range representation should be adapted to that upper bound.  But even
then, people doing inter-galactic communications, or more Earthly
communications through thick concrete, may think otherwise.  Maybe even
ask for 128bit floating point (instead of just the proposed 32bit).

> point is that it costs O(10^1)?

On a link - yes, true, the question is perfectly legitimate.

On a path I expect one to prefer finer expression.  A routing protocol
would add and compare the Energy values of links on paths.

I would imagine an Energy metric for link in ROLL routing protocol could
be further exported in the routing protocols in the Internet, OSPF, BGP,
like the IP hopcount metric is.

I may be far off with this...

Thank you for the message,

Alex
(PS: Another argument in favor of the 32bit single precision format is
that is standardized - IEEE 754-2008.  As such many people understand
it.  Otherwise, if we eliminate mantissa, and decide only on some range
of representation, we should agree in ROLL about it.  We could agree
when we had many confirmed measurements of this value on many different
links...)

---

From: Kris Pister <[email-masked]>
Date: Wed, 13 May 2009 17:03:31 -0700

...and if you burn O(10^1) Joules per packet, should I route through 
you, or someone who burns O(10^-4) J/pkt?

I think that metrics related to total lifetime packets and max packets 
per second are closer to what we really care about than the absolute 
cost of the packets, and the absolute state of the node's internal power 
source.

ksjp

---

From: Michael Richardson <[email-masked]>
Date: Wed, 13 May 2009 14:22:30 -0400

---

From: Philip Levis <[email-masked]>
Date: Thu, 14 May 2009 11:46:24 -0400

> point is that it costs O(10^1)?

As an aside, floating point for routing metrics can cause problems.  
These problems are not insurmountable, but it's important to recognize  
them and design routing protocols appropriately. In particular, using  
floating point means that route costs will not necessarily be  
monotonically increasing: if a link cost is very small compared to the  
overall route cost, it can be lost in the exponent. The lack of  
monotonicity means that you cannot depend on the metric to detect  
loops, unless you add some special cases (e.g., always add).

I raised this issue in the MANET link metric discussions (August 15,  
2007).

Phil

---

From: [email-masked]
Date: Thu, 14 May 2009 12:11:15 -0500

You can't assume that an 8-bit processor has intrinsic floating point 
support.  If the sensor is measuring temperature, you might expect they 
would support floating point.  (Not all of our do).  However, a binary 
sensor (e.g. a window tamper switch) clearly won't have floating point 
support.

Jerry

Philip Levis <[email-masked]> 
Sent by: [email-masked]
05/14/2009 11:48 AM

To
Michael Richardson <[email-masked]>
cc
ROLL WG <[email-masked]>
Subject
Re: [Roll] ROLL Routing Metrics - WF feed-back needed

Phil

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 14 May 2009 22:12:12 +0200

Philip Levis a écrit :
>>  Miguel> Energy units to express Energy values (whether it is
>> Joules Miguel> or mJ integers are easier).
>> 
> These problems are not insurmountable, but it's important to 
> recognize them and design routing protocols appropriately. In 
> particular, using floating point means that route costs will not 
> necessarily be monotonically increasing: if a link cost is very small
>  compared to the overall route cost, it can be lost in the exponent.

I don't get it... lost in the exponent?

> The lack of monotonicity means that you cannot depend on the metric 
> to detect loops, unless you add some special cases (e.g., always 
> add).

I don't fully understand you.

Loop avoidance: IPv6 Hop Limit is 0 then discard.

Not creating the really shortest path because floats are used: I can
understand.  I don't assume perfect paths are created with integer
metrics either.

But the influence of the difference float-integer metric - I don't get.

> I raised this issue in the MANET link metric discussions (August 15, 

That's a long way back I don't have archive that far.  Could you please
post a pointer?

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 14 May 2009 22:13:28 +0200

> You can't assume that an 8-bit processor has intrinsic floating point 

Right, but one can expect a _program_ of the 8-bit processor to perform 
floating point operations.

Alex

   If the sensor is measuring temperature, you might expect they
> *Philip Levis <[email-masked]>*
> ------------------------------------------------------------------------
>

---

From: [email-masked]
Date: Thu, 14 May 2009 15:39:41 -0500

Alex,

I didn't say you shouldn't expect 'floating point hardware', I said you 
shouldn't expect 'floating point'.  That means neither hardware nor 
software floating point.  Many sensor implementations read the A/D 
convertor directly; perform syntactic and semantic checks on this value 
without converting it and then ship it upstream to its respective 
controller in ADC form.  The controller may convert this to floating point 
so it can do other operations (e.g. averaging across multiple sensors).

As we move toward energy harvested sensors (that is battery-less) the 
processor may only have a few hundred machine instructions it can run 
before it's out of energy.  It won't have the luxury to perform floating 
point operations.

We need to be really careful that the NWK layer doesn't assume processing 
and memory resources that aren't already available to the application 
layer

Jerry

Alexandru Petrescu <[email-masked]> 
05/14/2009 03:13 PM

To
[email-masked]
cc
Philip Levis <[email-masked]>, [email-masked], Michael 
Richardson <[email-masked]>, ROLL WG <[email-masked]>
Subject
Re: [Roll] ROLL Routing Metrics - WF feed-back needed

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 14 May 2009 23:39:42 +0200

Jerald,

[email-masked] a écrit :
> 
> 
> Alex,
> 
> I didn't say you shouldn't expect 'floating point hardware', I said
> you shouldn't expect 'floating point'.  That means neither hardware
> nor software floating point.  Many sensor implementations read the
> A/D convertor directly; perform syntactic and semantic checks on this
> value without converting it and then ship it upstream to its
> respective controller in ADC form.  The controller may convert this
> to floating point so it can do other operations (e.g. averaging
> across multiple sensors).
> 
>  processor may only have a few hundred machine instructions it can
> run before it's out of energy.  It won't have the luxury to perform

On an 8-bit micro-controller with 8bit registers and 8bit addressing, a
fundamental IP longest prefix match would average 8 CMP instructions
before the successful JMP, plus 16 fetches of the 2 parts of the
compared IP addresses.  Optimistically: 30 instructions required. Only
to route one packet!

Not many packets could be routed when only a few hundred instructions 
are available...

> We need to be really careful that the NWK layer doesn't assume 
> processing and memory resources that aren't already available to the
>  application layer

I agree these ressources wouldn't be available on the most constrained
chips, but IP couldn't run on them anyways, even the most stripped-out IP.

Alex

---

From: [email-masked]
Date: Thu, 14 May 2009 16:55:29 -0500

Yes.  Don't forget, the sensor also has to actually sense the air and 
complete sanity checks on the data prior packetizing and shipping the 
packet. 

As I mentioned in my last email, we might want to consider some 'reduced 
function' definition for these really low power devices.  Once we get past 
this sensor/actuator layer, the upstream devices have some addition 
horsepower (512Kbytes flash, 64Kbytes RAM, floating point) that can do 
more traditional IP type operations.

Jerry

05/14/2009 04:40 PM

To
[email-masked]
cc
Michael Richardson <[email-masked]>, Philip Levis 
<[email-masked]>, ROLL WG <[email-masked]>, [email-masked]
Subject
Re: [Roll] ROLL Routing Metrics - WG feed-back needed

Jerald,

Alex