Subject: [Roll] load based parent selection and CAC

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 20 Oct 2009 18:26:23 +0200

Hi:

Here's what I gathered from the industrial space:

'Buffered' sensor data is captured at a certain frequency (typically
4Hz) and placed in a buffer.

The buffer is then transmitted at a same or different frequency than
that of capture. 

If the data capture frequency is higher than the transmit frequency then
the buffer is overwritten and some readings are just lost.

The buffered data might be lost on the way and that's usually OK, but
some applications react very badly to jitter.

This strikes me as resembling quite a bit to voice over radio. A
technique called Load-Based Call Admission Control is used in WCDMA and
WIFI to compute whether there's enough free space to take an additional
call that will fit the codec characteristics. Basically that's a set of
heuristics and a magical formula that uses the measure of the energy in
the channel and the transmit queue delays to compute whether there's
enough free space in the air. 

Obviously, using such load estimate to do routing would take us back to
Arpanet and is a proven bad idea. But I thought that it could be used:

-          By hosts to select a router

-          By routers to select a next_hop between its parents for a
given packet (IOW a packet forwarding time metric as opposed to a
routing time metric).

What do you think?

Pascal

---

From: Maxence Dalmais <[email-masked]>
Date: Tue, 20 Oct 2009 19:43:25 +0200

Hi Pascal,

On Tue, Oct 20, 2009 at 6:26 PM, Pascal Thubert (pthubert) <
[email-masked]> wrote:

>  Hi:
>
>
>
> Here’s what I gathered from the industrial space:
>
>
>
> ‘Buffered’ sensor data is captured at a certain frequency (typically 4Hz)
> and placed in a buffer.
>
> The buffer is then transmitted at a same or different frequency than that
> of capture.
>
> The buffered data might be lost on the way and that’s usually OK, but some
> applications react very badly to jitter.
>
>
>
> This strikes me as resembling quite a bit to voice over radio. A technique
> called Load-Based Call Admission Control is used in WCDMA and WIFI to
> compute whether there’s enough free space to take an additional call that
> will fit the codec characteristics. Basically that’s a set of heuristics and
> a magical formula that uses the measure of the energy in the channel and the
> transmit queue delays to compute whether there’s enough free space in the
> air.
>
>
>
> -          By routers to select a next_hop between its parents for a given
> packet (IOW a packet forwarding time metric as opposed to a routing time
> metric).
>
>

Yes but how would you expect "host" to use that information to select the
router ?
It may very well be that the router offering the lower forwarding time end
up following a high forwarding time path.  [adapt from JP Vasseur in RPL
Metric I-D ].

Maxence.

> What do you think?
Hi Pascal,

Yes but how would you expect "host" to use that information to select the
router ?
It may very well be that the router offering the lower energy cost end up
following a high energy path.

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

---

From: JP Vasseur <[email-masked]>
Date: Tue, 20 Oct 2009 22:45:43 -0700

On Oct 20, 2009, at 9:26 AM, Pascal Thubert (pthubert) wrote:

> ‘Buffered’ sensor data is captured at a certain frequency (typically  
> If the data capture frequency is higher than the transmit frequency  
> then the buffer is overwritten and some readings are just lost.
>
> The buffered data might be lost on the way and that’s usually OK,  
> but some applications react very badly to jitter.
>
> technique called Load-Based Call Admission Control is used in WCDMA  
> and WIFI to compute whether there’s enough free space to take an  
> additional call that will fit the codec characteristics. Basically  
> that’s a set of heuristics and a magical formula that uses the  
> measure of the energy in the channel and the transmit queue delays  
> to compute whether there’s enough free space in the air.
>
> Obviously, using such load estimate to do routing would take us back  
> to Arpanet and is a proven bad idea. But I thought that it could be  
> used:

CAC is fairly well-known but is typically end to end (e.g. RSVP). If  
what you want is another local decision criteria
then no need to make it a routing metric.

JP.

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 21 Oct 2009 16:29:40 +0200

Hi JP:

If the utilization metric is to be used at all then it must represent a
path not a hop. So it needs to be passed along by the routers.

Pascal

From: JP Vasseur (jvasseur) 
Sent: mercredi 21 octobre 2009 07:46
To: Pascal Thubert (pthubert)
Cc: roll ROLL
Subject: Re: [Roll] load based parent selection and CAC

Hi:

 

JP.

What do you think?

Pascal

---

From: Kris Pister <[email-masked]>
Date: Wed, 21 Oct 2009 11:17:38 -0700

Pascal - it would be unseemly for the two IA requirements document 
editors to argue about IA requirement in public :)
so I'll just present these comments as an alternative interpretation.

> then the buffer is overwritten and some readings are just lost.
I've never seen an application like this.  The vast majority of 
applications sample (capture) and send immediately.  A small minority 
sample repeatedly before sending, but none of them would just overwrite 
the existing data.  That would show up as lost data in the network 
stats, and people would get mad.
> some applications react very badly to jitter.
I've never seen an application where lost data was ok, but jitter caused 
bad reactions.  Lost data is indistinguishable from long-jitter, yes?.  
Again, latency above some specified max counts as lost.
> and WIFI to compute whether there's enough free space to take an 
> that's a set of heuristics and a magical formula that uses the measure 
> of the energy in the channel and the transmit queue delays to compute 
> whether there's enough free space in the air.
>
Can you elaborate on the heuristics and the magical formula?
> to Arpanet and is a proven bad idea. But I thought that it could be used:
>
If I have several 1-hop nodes (with links to an LBR), and a whole bunch 
of other nodes further away routing through them, I'd really like to 
load balance among the 1-hop nodes.  So I'd like to be able to make a 
decision on which 5-hop parent to join based on the 1-hop 
energy/lifetime metrics.  Is that what you're talking about too?

ksjp
>
>  
>
> What do you think?
>
>  
>
> Pascal
>
>  
>
> ------------------------------------------------------------------------
>

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 22 Oct 2009 08:17:12 +0200

Hi Kris:

Since I'm only second hand on the buffered explanation I'll defer to my
sources J 

Alex, I'd really appreciate if you could give use more insight on the
buffered data, in particular WRT sensitivity to loss and jitter?

There's not so much data on the formulae that we use for Load-Based Call
Admission Control but for the patent we filed. You'll find all that info
by googling "load-based CAC" but I cannot promise that what Cisco
patented is exactly what made it in the final product. I'm not sure that
we published that level of information. There is similar work on WCDMA.

The patented formulas can be found at:

http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u
=%2Fnetahtml%2FPTO%2Fsearch-bool.html&r=1&f=G&l=50&co1=AND&d=PG01&s1=200
80186846.PGNR.&OS=DN/20070198578&RS=DN/20080186846 

I was involved in LB-CAC when I implemented the CAC over our mesh
product, in a recent life. The difference is that the metrics must be
aggregated over the mesh path, so it gets a bit more complex and harder
to prove. Until something changed in the mesh product since we completed
that project, Cisco does not to offer the option to do load based CAC
over multihop. Which is what I'm talking about here. 

Pascal

From: Kris Pister [mailto:[email-masked]] 
Sent: mercredi 21 octobre 2009 20:18
To: Pascal Thubert (pthubert)
Cc: roll ROLL
Subject: Re: [Roll] load based parent selection and CAC

Hi:

 

 

 

By hosts to select a router

By routers to select a next_hop between its parents for a given packet
(IOW a packet forwarding time metric as opposed to a routing time
metric).

ksjp

What do you think?

Pascal

________________________________

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 22 Oct 2009 12:11:27 +0200

Hi Maxence,

Basically we can see 2 sorts of information. Information that is
(statistically?) aggregated over time and is stable enough to be used in
the graph computation, and information that is volatile and depends on
the dynamics of the network thus formed and can only be used at packet
forwarding time. Those 2 sorts of information operate at different time
scales.

It appears that is the energy cost for a rather stable topology could be
used for routing, in the OCP logic. So if the OCP cares for energy, I
expect that the path this formed will all be with acceptable boundaries.
Like EIGRP selecting feasible successors for which the cost is less than
a ratio over the most favorable path.

But if we leave it at that, it's very possible that all the sensor data
will converge over a preferred path that will saturate and drop packets.
What I'm talking about here is to influence the forwarding decision over
the parents that are selected by the routing in order to distribute over
paths of lesser use, but that are still acceptable.

IOW for your question, the routing selects a DAG that is acceptable
energy-wise. And then the forwarding distributes the traffic over the
multiple parents to control the congestion. You'll note that congestion
is typically the type of information that you DO NOT want to use for
routing. ARPANET proved that this creates a causality loop and from
there instability.

If we care for only one hop, then as JP said, this has more to do with
the L2 triggers than with the metrics carried in our messages. But that
simplistic process will fail if the next hop is congested to death. This
is why I introduced this discussion.

Pascal

From: Maxence Dalmais [mailto:[email-masked]] 
Sent: mardi 20 octobre 2009 19:43
To: Pascal Thubert (pthubert)
Cc: roll ROLL
Subject: Re: [Roll] load based parent selection and CAC

Hi Pascal,

On Tue, Oct 20, 2009 at 6:26 PM, Pascal Thubert (pthubert)
<[email-masked]> wrote:

Hi:

Yes but how would you expect "host" to use that information to select
the router ?
It may very well be that the router offering the lower forwarding time
end up following a high forwarding time path.  [adapt from JP Vasseur in
RPL Metric I-D ].

Maxence.

	What do you think?

Hi Pascal,

Yes but how would you expect "host" to use that information to select
the router ?
It may very well be that the router offering the lower energy cost end
up following a high energy path. 

	Pascal

---

From: Kris Pister <[email-masked]>
Date: Thu, 22 Oct 2009 08:33:02 -0700

Alex - well stated, thanks. The bottom line is that periodic 
measurements need to be carried with high reliability and low jitter. 
Anything other than that is a network failure, and some control systems 
have smart ways of dealing with that, and some don't.

ksjp

Chernoguzov, Alexander (PA35) wrote:
> Pascal,
> Your explanation of how buffered data transfer works is very good. I 
> particularly like the analogy to voice over radio (or over wired IP 
> for that matter).
> Most process control systems are built around periodic sampling. 
> Control algorithms (e.g. PID) execute periodically on a fixed schedule 
> (e.g. once a second). They assume that fresh input data is available 
> right before control algorithm execution.
> In a networked environment, control algorithm may run on a different 
> node than the one providing the input data. In that case, it is 
> assumed that inputs are published synchronously to the control 
> algorithm execution and phased in such a way that input value is 
> delivered to the control algorithm immediately before it executes.
> It is evident from the above that high jitter is in fact very similar 
> to packet loss. If the input is delivered to the controller node after 
> it did the control algorithm execution, it is not going to be used 
> until next execution cycle, by which time a new input value is 
> normally available. It also explains the over-write policy. There is 
> no point trying to deliver old value when new one is available few 
> moments later. In this discrete sampling system, only the last value 
> matters.
> Most control algorithms know how to deal with lost data. They either 
> use the last received value or approximate lost value based on recent 
> history of the measurement. In voice analogy this is equivalent to a 
> short blip in conversation.
> Variable jitter is a significant adversary of good control. If phasing 
> of input publication is variable relative to the control execution, 
> you get the effect of executing control some times on old input value 
> and some times on new input value. This results in erratic control 
> behavior if control algorithm was tuned to the ideal input delivery. 
> It also explains why high jitter is different from complete packet 
> loss. Variable jitter in voice analogy results in distorted sound.
> Alex
>
> *From:* Pascal Thubert (pthubert) [mailto:[email-masked]]
> *Sent:* Thursday, October 22, 2009 2:17 AM
> *To:* Kris Pister; Chernoguzov, Alexander (PA35); Brett, Patricia (PA62)
> *Cc:* roll ROLL
> *Subject:* RE: [Roll] load based parent selection and CAC
>
> Hi Kris:
>
> Since I’m only second hand on the buffered explanation I’ll defer to 
> my sources J
>
> Alex, I’d really appreciate if you could give use more insight on the 
> There’s not so much data on the formulae that we use for Load-Based 
> Call Admission Control but for the patent we filed. You’ll find all 
> that info by googling “load-based CAC” but I cannot promise that what 
> Cisco patented is exactly what made it in the final product. I’m not 
> sure that we published that level of information. There is similar 
> work on WCDMA.
>
> http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=%2Fnetahtml%2FPTO%2Fsearch-bool.html&r=1&f=G&l=50&co1=AND&d=PG01&s1=20080186846.PGNR.&OS=DN/20070198578&RS=DN/20080186846 
> <http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=%2Fnetahtml%2FPTO%2Fsearch-bool.html&r=1&f=G&l=50&co1=AND&d=PG01&s1=20080186846.PGNR.&OS=DN/20070198578&RS=DN/20080186846> 
>
>
> aggregated over the mesh path, so it gets a bit more complex and 
> harder to prove. Until something changed in the mesh product since we 
> completed that project, Cisco does not to offer the option to do load 
> based CAC over multihop. Which is what I’m talking about here.
>
> Pascal
>
> *From:* Kris Pister [mailto:[email-masked]]
> *Sent:* mercredi 21 octobre 2009 20:18
> *To:* Pascal Thubert (pthubert)
> *Cc:* roll ROLL
> *Subject:* Re: [Roll] load based parent selection and CAC
>
> sample repeatedly before sending, but none of them would just 
> overwrite the existing data. That would show up as lost data in the 
> network stats, and people would get mad.
>
> The buffered data might be lost on the way and that’s usually OK, but 
> I've never seen an application where lost data was ok, but jitter 
> caused bad reactions. Lost data is indistinguishable from long-jitter, 
> yes?. Again, latency above some specified max counts as lost.
>
> that’s a set of heuristics and a magical formula that uses the measure 
> whether there’s enough free space in the air.
>
> (IOW a packet forwarding time metric as opposed to a routing time metric).
>
> If I have several 1-hop nodes (with links to an LBR), and a whole 
> bunch of other nodes further away routing through them, I'd really 
> like to load balance among the 1-hop nodes. So I'd like to be able to 
> make a decision on which 5-hop parent to join based on the 1-hop 
> [email-masked] <mailto:[email-masked]>