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

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 7 Nov 2008 17:32:00 +0100

Hi Mijeom,

I suspect that in many radio systems with operations similar to IEEE 802, the propagation delay you are talking about is almost useless taken separately since the transaction is only complete when an ack is received back that enables a wireless router to free the resources allocated to the frame and go back to sleep. The time between acking a received frame and receiving the ack for that frame being forwarded is the real latency of a node. If we want to sustain a given rate R with a Latency L, we need R*L in buffer space. Considering that memory is often a constrained resource this is something that we need to account for.

Pascal

________________________________

From: [email-masked] [mailto:[email-masked]] On Behalf Of MiJeom Kim
Sent: vendredi 31 octobre 2008 05:56
To: Miguel Sanchez
Cc: ROLL WG
Subject: Re: [Roll] ROLL Routing Metrics - WF feed-back needed

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 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. 
 
Thanks,
Mijeom.

On Thu, Oct 30, 2008 at 7:56 PM, 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).

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

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

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

---

From: Philip Levis <[email-masked]>
Date: Fri, 7 Nov 2008 12:57:53 -0800

On Nov 7, 2008, at 8:32 AM, Pascal Thubert (pthubert) wrote:

> Hi Mijeom,
>
> I suspect that in many radio systems with operations similar to IEEE  
> 802, the propagation delay you are talking about is almost useless  
> taken separately since the transaction is only complete when an ack  
> is received back that enables a wireless router to free the  
> resources allocated to the frame and go back to sleep. The time  
> between acking a received frame and receiving the ack for that frame  
> being forwarded is the real latency of a node. If we want to sustain  
> a given rate R with a Latency L, we need R*L in buffer space.  
> Considering that memory is often a constrained resource this is  
> something that we need to account for.

Pascal,

I'm not sure this is really an issue. You're talking about layer 2  
acks? Generally those are always transmitted within a quite  
deterministic and tiny time interval; furthermore, media access is  
designed to prevent transmitting on top of them (e.g., through 15.4's  
double channel sense, or 802.11's NAV). The idea that a node has to  
hold onto a packet for a long time waiting for a layer 2 ack just  
isn't a problem, as they are generally synchronous rather than  
asynchronous (do not go through media access).

Phil

---

From: "MiJeom Kim" <[email-masked]>
Date: Mon, 10 Nov 2008 15:07:01 +0900

Hi,

We have had quite a few arguments regarding delay related metrics
through this mailing list. In traditional packet switched networks,
there are four kinds of delays, which are processing delay, queuing
delay, transmission delay and propagation delay. There is one more
delay we make an issue here is L2 delay caused by MAC protocols. The
document classifies the first three delays as node latency, one of
node metrics and propagation delay as a link metric.

Let's take into consideration one by one.
- Processing delay: it's time for a node to process a packet including
header analysis and error check. I personally prefer to exclude
processing delay from metrics since it is kind of negligible and is
depending on node's computing resource which is specified as a node
metric.
- Queuing delay: it is depending on time and current node workload
(the number of packets arrived earlier), thus I prefer to exclude it,
too.
- Transmission delay: it's time to push the packet to the link and
calculated as packet size/bit rate. It's a function of packet size,
which is hard to make it a metric. We can take bit rate as a factor to
affect link throughput, though.
- Propagation delay: as we already agreed, it's close to light speed
in radio systems and negligible. So I don't think we need this as a
metric.
- L2 delay: as I mentioned before, it's very fluctuating by time and
depending on MAC protocols. Due to the all dependency I don't think
it's a good idea to take L2 delay as a metric.

To summary, delay related attributes are mostly varying as time and
depending on variables such as packet size and workload. Therefore, I
don't think anything above can be a feasible routing metric.
Otherwise, we need really well designed schemes to take care of all
the variables affecting the delays and to avoid instability, which is
pretty skeptical.

Always welcome other opinions,

Thanks,
Mijeom.

On Sat, Nov 8, 2008 at 5:57 AM, Philip Levis <[email-masked]> wrote:
>> I suspect that in many radio systems with operations similar to IEEE 802,
>> the propagation delay you are talking about is almost useless taken
>> separately since the transaction is only complete when an ack is received
>> back that enables a wireless router to free the resources allocated to the
>> frame and go back to sleep. The time between acking a received frame and
>> receiving the ack for that frame being forwarded is the real latency of a
>> node. If we want to sustain a given rate R with a Latency L, we need R*L in
>> buffer space. Considering that memory is often a constrained resource this
>> is something that we need to account for.
>
> Pascal,
>
> I'm not sure this is really an issue. You're talking about layer 2 acks?
> Generally those are always transmitted within a quite deterministic and tiny
> time interval; furthermore, media access is designed to prevent transmitting
> on top of them (e.g., through 15.4's double channel sense, or 802.11's NAV).
> The idea that a node has to hold onto a packet for a long time waiting for a
> layer 2 ack just isn't a problem, as they are generally synchronous rather
> than asynchronous (do not go through media access).
>
> Phil
>

---

From: JP Vasseur <[email-masked]>
Date: Mon, 10 Nov 2008 09:56:30 +0100

Could you all have a look at all metrics and let us know which metrics you
think that useful ? Then we start discussing how often they should be update
for routing, packet format, ....

Thanks.

JP.

---

From: "Mischa Dohler" <[email-masked]>
Date: Mon, 10 Nov 2008 10:29:02 +0100

Hi Mijeom, all, the conclusion on the instability has - if I understood
correctly - always been drawn assuming a fairly heavily loaded network. With
some exceptions, however, our networks will be lightly loaded and
duty-cycled, which means that in most cases the processing + queuing +
transmission delay << L2 delay. Whilst this L2 delay heavily depends on the
MAC, it is not a value which fluctuates strongly (if at all) over time. The
end-to-end delay, will hence more or less be proportional to the number of
hops multiplied by the L2 delay. Therefore, although differently motivated,
I would agree that delay is not really needed. Having said this, in our
urban scenario, delay is not really a design issue - Jerry, Kris and Anders
may have a different opinion here. Regards, Mischa.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
MiJeom Kim
Sent: Monday, November 10, 2008 7:07 AM
To: Philip Levis
Cc: ROLL WG
Subject: Re: [Roll] ROLL Routing Metrics - WF feed-back needed

Hi,

Thanks,
Mijeom.

---

From: Philip Levis <[email-masked]>
Date: Mon, 10 Nov 2008 04:45:33 -0800

> may have a different opinion here. Regards, Mischa.

It is proportional, in that if you add a hop it will become longer,  
but that doesn't mean it's a linear function. Consider a standard TDMA  
MAC layer which uses communication slots; if slots are distributed in,  
say, a 250ms cycle, then the MAC latency at one hop can be 0-250ms. In  
such a network, minimizing latency might lead to different routes than  
minimizing cost (transmissions).

Phil

---

From: Kris Pister <[email-masked]>
Date: Mon, 10 Nov 2008 15:08:31 -0800

Mijeom -
  given that L2 performance can easily vary over three orders of 
magnitude even with the same radio, I don't understand how we can do a 
good job of routing without taking L2 delay into account.
Your concerns below seem to be that the delay is time varying, and 
depends on mac protocol.
For a given node, of course, the mac protocol is likely to be fixed.  
Certainly that will be true of a given link.  And the rate of change of 
a parameter like link latency is likely to be low - there will certainly 
be some "high frequency" (e.g. 1/s) variation, but that's not what a 
node would report in a routing algorithm.  Routing decisions can be made 
with a filtered version, say with a time constant of hours.

Can someone explain how we can do a good job of latency-sensitive 
routing (an industrial requirement) if we don't take the primary source 
of latency into account?  It seems to me that whether we think that it's 
hard or not, we have to do it.

ksjp

---

From: Kris Pister <[email-masked]>
Date: Mon, 10 Nov 2008 15:25:41 -0800

Mischa -
 I agree with everything except the second to last sentence. :)
I haven't read the urban draft recently, but I tried to convince Thomas 
to put in the parking monitoring and traffic light applications, since 
both of those are actually in production already using LLNs (e.g. 
StreetlineNetworks.com, SensysNetworks.com).  In both cases, latency is 
a real issue.
In any case, even meter and meteorological data has latency 
constraints.  There are those who believe that the best way to get below 
a 0.1% radio duty cycle is to turn all of the radios on for 60 seconds 
once a day. There was a product on the market for a while that did this 
with a 15 minute cycle. I disagree with that approach, but it's 
certainly a LLN MAC that we might see some day, and hopping across 
networks like that is going to be painful for most applications.

ksjp

Mischa Dohler wrote:
>>> back that enables a wireless router to free the resources allocated to
>>>       
> the
>   
>>> node. If we want to sustain a given rate R with a Latency L, we need R*L
>>>       
> in
>   
>>> buffer space. Considering that memory is often a constrained resource
>>>       
> this
>   
>> Generally those are always transmitted within a quite deterministic and
>>     
> tiny
>   
>> time interval; furthermore, media access is designed to prevent
>>     
> transmitting
>   
>> on top of them (e.g., through 15.4's double channel sense, or 802.11's
>>     
> NAV).
>   
>> The idea that a node has to hold onto a packet for a long time waiting for
>>     
> a
>

---

From: "Mischa Dohler" <[email-masked]>
Date: Tue, 11 Nov 2008 11:07:07 +0100

Kris, I actually did not mean to remove latency from the protocol design but
rather proposed to omit it from the list of routing metrics since it can
more or less be inferred from the number of hops or, more precisely, the
number of duty-cycles needed to get the data through - all this, of course,
assuming WSN-tailored duty-cycled MACs and not traditional MACs. I have
however no strong opinion about this since loads of scenarios immediately
pop into my mind where the exact delay matters, such as a combination of
what Phil referred to and your TSMP for industrial monitoring. Mischa. PS:
Tim (Winter), what do you think about that issue in the context of meter
reading?

-----Original Message-----
From: Kris Pister [mailto:[email-masked]] 
Sent: Tuesday, November 11, 2008 12:26 AM
To: [email-masked]
Cc: 'ROLL WG'; Tod Dykstra; [email-masked]
Subject: Re: [Roll] ROLL Routing Metrics - WF feed-back needed

Mischa -

ksjp

>>> I suspect that in many radio systems with operations similar to IEEE
802,

---

From: Tim Winter <[email-masked]>
Date: Tue, 11 Nov 2008 18:33:27 -0500

In the context of meter reading, periodic reporting of meter data from
the meter to the LBR will not generally have tight latency
requirements.  `Live' meter readings, where, e.g., a specific request is
made from a customer support to read a meter while a customer is waiting
on the phone will need to be more responsive.   In these case the
routing protocol should generally support selection of a route based on
priority, and it would be useful to be able to make some correlation
between priority and latency.  But I would agree that this does not
necessarily require latency to be a metric on its own- number of hops
or  some other metric could be used in this application.

-Tim

---

From: Kris Pister <[email-masked]>
Date: Wed, 19 Nov 2008 15:47:10 -0800

Mischa - we had some discussion of this at the IETF meeting, and it's 
clear that I'm not doing a good job of explaining my view on the 
interface to layer 2, and the power/latency tradeoff available there.  
So let me know which part of this makes sense and which doesn't.

There are many L2 protocols that allow me to specify a "listen duty 
cycle".  In several different incarnations of preamble sampling, and in 
TSMP, this calls for a receiver to wake up periodically to listen to the 
channel.  With todays radios, the cost of this operation is very very 
roughly (vvr) 1ms worth of radio RX time.  So whether this is a 
scheduled slot in a TDMA network (like TSMP) or an unsynchronized 
periodic listen, somehow the node must decide how often to wake up and 
listen.  That range can be vvr 10ms to 10s, giving me vvr 10% to 0.01% 
duty cycle on the receiver, and a corresponding mean link delay of vvr 
10ms to 10s (lots and lots of improvements can be made here).
In both the synchronized and unsynchronized approaches, the delay is a 
link property, not a network-wide property.  So I might have a 5 hop 
path with 0.1s total delay, and a 2 hop path with a 10s delay.  My 
routing algorithm needs to be smart enough to:
1) be aware of the existing delay
2) be able to ask L2 if it can afford to decrease it's delay
3) make rational decisions based on the answers to 1 and 2, and then 
command L2 to make the appropriate change in it's power/latency tradeoff 
(what I have been calling L3 provisioning of L2 to satisfy L4 QoS).

I don't think that this is a layer violation, and I'm not even sure if 
it's that new of a concept.  When JP gets going about MPLS, traffic 
engineering, and virtual circuits and things like that he says a lot of 
things that sound familiar to me, but I don't have the networking 
background to know how close that stuff is to what I'm describing.

ksjp

Mischa Dohler wrote:
>> correctly - always been drawn assuming a fairly heavily loaded network.
>>     
> With
>   
>> transmission delay << L2 delay. Whilst this L2 delay heavily depends on
>>     
> the
>   
>> MAC, it is not a value which fluctuates strongly (if at all) over time.
>>     
> The
>   
>> hops multiplied by the L2 delay. Therefore, although differently
>>     
> motivated,
>   
>> urban scenario, delay is not really a design issue - Jerry, Kris and
>>     
> Anders
>   
>>>> separately since the transaction is only complete when an ack is
>>>>         
> received
>   
>>>> receiving the ack for that frame being forwarded is the real latency of
>>>>         
> a
>   
>>> The idea that a node has to hold onto a packet for a long time waiting
>>>       
> for
>   
>>>     
>>>       
>> a
>>   
>>     
>>> layer 2 ack just isn't a problem, as they are generally synchronous
>>>       
> rather
>

---

From: "Mischa Dohler" <[email-masked]>
Date: Thu, 20 Nov 2008 16:44:56 +0100

Kris, 

I am not quite sure why you address this email to me as I fully see your
point and, as per below email exchanges, pretty much agree with you. My last
emails were just to highlight that you can do many hops in a single MAC
cycle and - if you use the same MACs under the same conditions - you can
calculate the e2e simply and vvr by having the numbers of hops. However, if
you start relying on MACs where you can change the cycle in each radio in
dependency of some metrics (and I don't think that traffic congestions will
have a major impact here), then this simple heuristics of course breaks
down. Including link delay into the specs may hence reflect better your
needs.

A general remark to the group, I am not sure why we are generally spending
so much time discussing this in such great details? I understand that some
good design specs help the protocol development but if we cannot agree why
not simply cater for the most demanding parameter(s) and then hope to be
able to relax this? Engineering work is iterative in nature, so let's talk
again when we will have some protocols on the table.

Mischa.

PS: I think what will give us more headache on the long run, however, is
what Phil alluded at, i.e. the problem with aggregation and e2e breakdown.
Did you discuss this at the meeting?

-----Original Message-----
From: Kris Pister [mailto:[email-masked]] 
Sent: Thursday, November 20, 2008 12:47 AM
To: [email-masked]
Cc: 'ROLL WG'
Subject: Re: [Roll] ROLL Routing Metrics - WF feed-back needed

ksjp