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

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

JP Vasseur a écrit :
> Hi,
> 
> 
> On 10/30/08 1:31 PM, "Miguel Sanchez" <[email-masked]> wrote:
> 
>> Hi JP,
>> 
>> On Thu, Oct 30, 2008 at 12:30 PM, JP Vasseur <[email-masked]>
>> wrote:
>>> Hi Miguel,
>>> 
>>> 
>>> On 10/30/08 11:56 AM, "Miguel Sanchez" <[email-masked]>
>>> wrote:
>>> 
>>>> 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).
>>> Ah I see what you mean, it is w/o transmission delay (just
>>> propagation delay). We'll clarify.
>> Ok.
>> 
>>>>> 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 that may be "good" enough ... The issue with a numeric value
>>> is that it will be really hard to define a consistent way to
>>> compute the value *and* will be hard to use by the computation
>>> engine.
>>> 
>>> Agree ?
>> Not really. As I see it local computation at a node is used to 
>> determine the residual energy. Based on that (and may be other 
>> constraints) node is tagged as high/medium/low. That energy tag is 
>> used later for routing decisions. Nodes could advertise the source 
>> data instead, residual energy. Doing that might make routing 
>> calculations more complex, but not doing it restricts the freedom
>> of routing algorithm.
>> 
>> Certainly the numeric value could end up having a few bits and 
>> effectively becoming 2 or four discrete values (similar to what you
>>  suggest).
> 
> Looks like you are agreeing with the suggested use of a few discrete
> values (flags) used for constrained based routing ?

I disagree to use a such a discrete metric, allowing only a few values.

The existing metric (IP number of hops) has a much higher resolution, 
going from 15 vlaues for RIP to OSPF's huge 65535.

Alex

> 
>>>>> 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?
>>> Heu ... You may want to try ... But certainly not trivial.
>> We've agreed on energy reporting. How this is done effectively does
>>  not seem trivial but it has to be done for protocols to be able to
>> use that.
>> 
>> My suggestion here is to report two energy related values: residual
>>  energy in Joules and the same as a percentage.
> 
> OK let's wait to see what others say. I claim that a few flags are 
> sufficient you would prefer to define a way to express energy. Let's
> try to converge on the list.
> 
>>>>> 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.
>>>> 
>>> One problem though: the PER of a function of packet size and can
>>> be computed knowing the BER anyway.
>>> 
>>> Agree ?
>> Yes but non trivial (coding, iid errors). PER can be measured
>> easily on the nodes (if link layer ACKs are used). That's why I was
>>  suggesting it.
> 
> Yes.
> 
> Thanks.
> 
> JP.
> 
>> Kind regards,
>> 
>> Miguel
> 
> _______________________________________________ Roll mailing list 
> [email-masked] https://www.ietf.org/mailman/listinfo/roll
>

---

From: JP Vasseur <[email-masked]>
Date: Thu, 14 May 2009 11:32:59 +0200

On May 13, 2009, at 2:49 PM, Alexandru Petrescu wrote:

> The existing metric (IP number of hops) has a much higher  
> resolution, going from 15 vlaues for RIP to OSPF's huge 65535.

It all depends on how we want to represent energy *and* for what  
purpose. I never look only at what I want to model but what could be  
done with it. WE has for example in depth discussion on metrics,  
objective functions, ... in other WGs and many times people wanted to  
standardize metrics and could be practically used by the routing  
protocol, we know ho easy it is to come up with an NP complete  
problem. This is why we would like to advance the document in parallel  
with the routing protocol !

JP.

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

---

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

JP Vasseur a écrit :
>>> Hi, On 10/30/08 1:31 PM, "Miguel Sanchez" <[email-masked]>
>>> wrote:
>>>> Hi JP, On Thu, Oct 30, 2008 at 12:30 PM, JP Vasseur
>>>>> Hi Miguel, On 10/30/08 11:56 AM, "Miguel Sanchez"
>>>>> <[email-masked]> wrote:
>>>>>> Hi JP, On Thu, Oct 30, 2008 at 10:02 AM, JP Vasseur 
>>>>>>> Hi Miguel, On 10/30/08 9:29 AM, "Miguel Sanchez"
>>>>>>> <[email-masked]> wrote:
>>>>>>>>  (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).
>>>>>>>  says: "Propagation delay is the time taken for the
>>>>>>> packet to traverse the link from the source node to the
>>>>>>> target node."
>>>>>> "propagation delay" equals link length over propagation
>>>>>> speed in my book. Apparently the meaning here is more like 
>>>>>>> confusing and the text should read: " Propagation delay
>>>>>>> is the time taken for the packet to traverse the link. "
>>>>>>>> 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 ?
>>>>>>> 
>>>>>> implementations over a numerical value (i.e: choosing
>>>>>> between two nodes with high value).
>>>>> But that may be "good" enough ... The issue with a numeric
>>>>> value is that it will be really hard to define a consistent
>>>>> way to compute the value *and* will be hard to use by the
>>>>> computation engine. Agree ?
>>>>  constraints) node is tagged as high/medium/low. That energy
>>>> tag is used later for routing decisions. Nodes could advertise
>>>> the source data instead, residual energy. Doing that might make
>>>> routing calculations more complex, but not doing it restricts
>>>> the freedom of routing algorithm. Certainly the numeric value
>>>> could end up having a few bits and effectively becoming 2 or
>>>> four discrete values (similar to what you suggest).
>>> Looks like you are agreeing with the suggested use of a few
>>> discrete values (flags) used for constrained based routing ?
>> 
> purpose.
> I never look only at what I want to model but what could be done with
> it. WE has for example in depth discussion on metrics, objective
> functions, ... in other WGs and many times people wanted to 
> problem.

JP,

I'm intrigued...

What does NP-completeness have to do with a metric here?

When you say "we all know" - is this as a Chair of this WG?  Or as a
co-author of the metrics WG item?

Alex

> This is why we would like to advance the document in parallel with
> the routing protocol !
> 
> JP.
> 
>> 
>> Alex
>> 
>>>>>>> metric that are implementation/node dependent. The way
>>>>>>> you model energy cannot be standardized.
>>>> We've agreed on energy reporting. How this is done effectively
>>>> does not seem trivial but it has to be done for protocols to be
>>>> able to use that. My suggestion here is to report two energy
>>>> related values: residual energy in Joules and the same as a
>>>> percentage.
>>> OK let's wait to see what others say. I claim that a few flags
>>> are sufficient you would prefer to define a way to express
>>> energy. Let's try to converge on the list.
>>>>>>> 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).
>>>>> One problem though: the PER of a function of packet size and
>>>>> can be computed knowing the BER anyway. Agree ?
>>>> easily on the nodes (if link layer ACKs are used). That's why I
>>>> was suggesting it.
>>> Yes. Thanks. JP.
>>>> Kind regards, Miguel

---

From: JP Vasseur <[email-masked]>
Date: Thu, 14 May 2009 16:38:51 +0200

On May 14, 2009, at 11:48 AM, Alexandru Petrescu wrote:

>>>>>>> Hi JP, On Thu, Oct 30, 2008 at 10:02 AM, JP Vasseur <[email-masked] 
>>>>>>> > wrote:

As a protocol designer ;-) (individual contributor)

Cheers.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Thu, 14 May 2009 16:42:42 +0200

> What does NP-completeness have to do with a metric here?

Defining metric is fairly easy ... the issue is what you with it. In  
other words, take two metrics M1 and M2. Try to compute the "best"  
path according to M1 and M2 and you have an NP complete problem. I am  
of course not saying that we will ned up with only one of course and  
one can use one at a time, many of them using a hierarchical approach,  
as tie breaker, ... but it is necessary to move the metric document in  
parallel with the protocol spec.

Thanks.

JP.

---

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

JP Vasseur a écrit :
[...]
>>> I never look only at what I want to model but what could be done 
>>> with it. WE has for example in depth discussion on metrics, 
>>> objective functions, ... in other WGs and many times people 
>>> wanted to standardize metrics and could be practically used by 
>>> the routing protocol, we know ho easy it is to come up with an NP
>>>  complete problem.
>> 
>> JP,
>> 
>> I'm intrigued...
>> 
> path according to M1 *and* M2 and you have an NP complete problem.

You seem to assume that trying to compute the best path only according
to M1 is not an NP complete problem.

Well, if instead of "M1 _and_ M2"  we say "M1+M2", then this
would be a not NP complete problem.

I.e., if 1hopcount+1joule makes for metric 2hopcountjoule then this is
not an NP complete problem, which is good, right?

However, if we say 1hopcount can't be added to a selected value from
(unlimited, scavenging, ok, low), because they're different types, then
we may have an NP complete problem, right?

Alex