Subject: [Detnet] End-to-end latency versus per-hop latency bounds

From: Le Boudec Jean-Yves <[email-masked]>
Date: Mon, 8 Jan 2018 12:00:15 +0100

There are cases in detnet where the end-to-end latency is less than the 
sum of the latencies at every hop:

- If the detnet nodes uses per-flow scheduling, the worst case 
end-to-end queuing delay is less than the sum of the worst case queuing 
delays at every hop because all worst cases cannot happen at the same 
time (“pay burst only once” [3]).

- A similar case arises if the detnet nodes use the Urgency Based 
Scheduler defined by IEEE 802.1 TSN for asynchronous traffic shaping 
[4]. Here, a packet may be delayed (1) at a switch output port due to 
output port queuing and class-based scheduling and (2) at the next 
downstream node due to the urgency based scheduler, which reshapes 
individual flows in order to avoid cascades of burstiness increase. The 
worst case of the sum of the delays at (1) and (2) is strictly less than 
the sum of the worst cases of (1) and (2) – this is an instance of 
“reshaping is for free” [3].

Now in the drafts [1] and [2] the queuing delays are expressed and 
gathered per node, which is sufficient in these cases to find the worst 
case end-to-end delay. If the only information available to a path 
computation application is the per-hop latency, then the computed 
end-to-end latency bound will be the sum of the per-hop bounds, which 
may be much more than the end-to-end latency that would be computed by a 
path computation application that would be aware of the presence of 
per-flow scheduling or of urgency based schedulers. Therefore, it seems 
that these drafts should be adapted to allow for an accurate computation 
of the end-to-end latency.

[1] draft-finn-bounded-latency
[2] draft-geng-detnet-conf-yang-00
[3] slides-100-detnet-applicability-of-network-calculus-to-detnet-02
[4] 
http://www.ieee802.org/1/files/public/docs2015/new-tsn-specht-ubs-queues-0521-v0.pdf

Best, JY

---

From: Le Boudec Jean-Yves <[email-masked]>
Date: Mon, 8 Jan 2018 13:05:11 +0100

typo correction, sorry -- JY

Now in the drafts [1] and [2] the queuing delays are expressed and 
gathered per node, which is NOT sufficient in these cases to find the 
worst case end-to-end delay.

On 08.01.2018 12:00, Le Boudec Jean-Yves wrote:
> There are cases in detnet where the end-to-end latency is less than 
> the sum of the latencies at every hop:
>
> end-to-end queuing delay is less than the sum of the worst case 
> queuing delays at every hop because all worst cases cannot happen at 
> the same time (“pay burst only once” [3]).
>
> individual flows in order to avoid cascades of burstiness increase. 
> The worst case of the sum of the delays at (1) and (2) is strictly 
> less than the sum of the worst cases of (1) and (2) – this is an 
> instance of “reshaping is for free” [3].
>
> gathered per node, which is sufficient in these cases to find the 
> worst case end-to-end delay. If the only information available to a 
> path computation application is the per-hop latency, then the computed 
> may be much more than the end-to-end latency that would be computed by 
> a path computation application that would be aware of the presence of 
> per-flow scheduling or of urgency based schedulers. Therefore, it 
> seems that these drafts should be adapted to allow for an accurate 
> computation of the end-to-end latency.
>

---

From: Lou Berger <[email-masked]>
Date: Mon, 08 Jan 2018 07:21:21 -0500

JY,

Thank you for the input. Do you have any specific changes or new text you 
can propose?

Lou

On January 8, 2018 7:05:49 AM Le Boudec Jean-Yves 
<[email-masked]> wrote:

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

---

From: Le Boudec Jean-Yves <[email-masked]>
Date: Mon, 8 Jan 2018 17:14:40 +0100

Lou,

it is probably more than just a few text edits. We would need

a) to explain the method by which end-to-end latency bounds are derived 
when there are elements that do per-flow scheduling or that contain 
shapers such as the urgency based shaper. This could be in the bounded 
latency draft or in the architecture.

b) to have all elements required by a) formally defined and made 
available in the yang configuration files (hence in 
draft-geng-detnet-conf-yang). This would contain for example: the rate 
and latency parameters of a per-flow scheduler; the parameters of the 
shaping algorithm used by an urgency based shaper.

I'll be happy to help with that !

JY

On 08.01.2018 13:21, Lou Berger wrote:
>
> JY,
>
> Thank you for the input. Do you have any specific changes or new text 
> you can propose?
>
> Lou
>
>>> [4]. Here, a packet may be delayed (1) at a switch output port due 
>>> to output port queuing and class-based scheduling and (2) at the 
>>> next downstream node due to the urgency based scheduler, which 
>>> reshapes individual flows in order to avoid cascades of burstiness 
>>> increase. The worst case of the sum of the delays at (1) and (2) is 
>>> strictly less than the sum of the worst cases of (1) and (2) – this 
>>> is an instance of “reshaping is for free” [3].
>>>
>>> path computation application is the per-hop latency, then the 
>>> computed end-to-end latency bound will be the sum of the per-hop 
>>> bounds, which may be much more than the end-to-end latency that 
>>> would be computed by a path computation application that would be 
>>> aware of the presence of per-flow scheduling or of urgency based 
>>> schedulers. Therefore, it seems that these drafts should be adapted 
>>> to allow for an accurate computation of the end-to-end latency.
>>>
>> [email-masked] <mailto:detnet%40ietf.org>

---

From: Lou Berger <[email-masked]>
Date: Mon, 8 Jan 2018 16:28:33 -0500

On 1/8/2018 11:14 AM, Le Boudec Jean-Yves wrote:
> a) to explain the method by which end-to-end latency bounds are 
> derived when there are elements that do per-flow scheduling or that 
> contain shapers such as the urgency based shaper. This could be in the 
> bounded latency draft or in the architecture.
>
Great!  Please work with the authors directly or feel free to submit a 
draft (or even just proposed text in  e-mail) on the topic!

Lou
>>> gathered per node, which is NOT sufficient in these cases to find 
>>> the worst case end-to-end delay.
>>>
>>>> queuing delays at every hop because all worst cases cannot happen 
>>>> at the same time (“pay burst only once” [3]).
>>>>
>>>> Scheduler defined by IEEE 802.1 TSN for asynchronous traffic 
>>>> shaping [4]. Here, a packet may be delayed (1) at a switch output 
>>>> port due to output port queuing and class-based scheduling and (2) 
>>>> at the next downstream node due to the urgency based scheduler, 
>>>> which reshapes individual flows in order to avoid cascades of 
>>>> burstiness increase. The worst case of the sum of the delays at (1) 
>>>> and (2) is strictly less than the sum of the worst cases of (1) and 
>>>> (2) – this is an instance of “reshaping is for free” [3].
>>>>

---

From: "Gengxuesong (Geng Xuesong)" <[email-masked]>
Date: Wed, 10 Jan 2018 02:27:57 +0000

Hi JY,

I have read more material about Networking Calculus, and I think it is very useful to describe the network unit behavior accurately and make the worst case end-to-end latency smaller than the sum of worst case latency of every hop.
It will be very charming if we can prove the end-to-end latency will be shorter significantly. And as the author of DetNet YANG module, I am also very interested in specifying 'the rate and latency parameters of a per-flow scheduler; the parameters of the shaping algorithm' based on the method offered by Networking Calculus, as you have mentioned in the email (In my understanding, most of the parameters of different queuing management algorithm have been defined in IEEE, maybe we can make use of them and redefine them in a rigorous mathematical model ).
They are all very interesting. If you have further plans about these topics, please let me in.

Best Regards,

Xuesong

From: detnet [mailto:[email-masked]] On Behalf Of Le Boudec Jean-Yves
Sent: Monday, January 08, 2018 8:05 PM
To: [email-masked]
Subject: Re: [Detnet] End-to-end latency versus per-hop latency bounds

Now in the drafts [1] and [2] the queuing delays are expressed and gathered per node, which is NOT sufficient in these cases to find the worst case end-to-end delay.
On 08.01.2018 12:00, Le Boudec Jean-Yves wrote:
There are cases in detnet where the end-to-end latency is less than the sum of the latencies at every hop:

- If the detnet nodes uses per-flow scheduling, the worst case end-to-end queuing delay is less than the sum of the worst case queuing delays at every hop because all worst cases cannot happen at the same time ("pay burst only once" [3]).

- A similar case arises if the detnet nodes use the Urgency Based Scheduler defined by IEEE 802.1 TSN for asynchronous traffic shaping [4]. Here, a packet may be delayed (1) at a switch output port due to output port queuing and class-based scheduling and (2) at the next downstream node due to the urgency based scheduler, which reshapes individual flows in order to avoid cascades of burstiness increase. The worst case of the sum of the delays at (1) and (2) is strictly less than the sum of the worst cases of (1) and (2) - this is an instance of "reshaping is for free" [3].

Now in the drafts [1] and [2] the queuing delays are expressed and gathered per node, which is sufficient in these cases to find the worst case end-to-end delay. If the only information available to a path computation application is the per-hop latency, then the computed end-to-end latency bound will be the sum of the per-hop bounds, which may be much more than the end-to-end latency that would be computed by a path computation application that would be aware of the presence of per-flow scheduling or of urgency based schedulers. Therefore, it seems that these drafts should be adapted to allow for an accurate computation of the end-to-end latency.

[1] draft-finn-bounded-latency
[2] draft-geng-detnet-conf-yang-00
[3] slides-100-detnet-applicability-of-network-calculus-to-detnet-02
[4] http://www.ieee802.org/1/files/public/docs2015/new-tsn-specht-ubs-queues-0521-v0.pdf

Best, JY

---

From: Le Boudec Jean-Yves <[email-masked]>
Date: Tue, 16 Jan 2018 17:49:40 +0100

Dear Geng Xuesong

consider a path made of two hops. The end-to-end delay bound with 
per-flow scheduler and leaky bucket constraint at the source is

     b/R + 2T

where b is the burstiness of the flow, R the rate guaranteed to the 
flow, and T the latency parameter of the rate-latency service curve at 
each hop (here I assume the two hops offer the same service curve to 
this flow).

the worst case delay bound at the first hop is b/R+T and at the second 
hop b/R+  (1+r/R) T.

the sum of the hop by hop delays is

   2b/R +(2+r/R)T

the difference is b/R +r/R T

b is typically the max number of bits in one interval as given by the 
detnet T-spec. R is the rate guaranteed to this flow at each hop. 
Already for 2 hops the difference is significant, the main difference 
being that the sum of hop by hop delays contains a term 2b/R instead of 
b/r in the end-to-end bound. If there are k hops, the difference is at 
least at large as (k-1) b/R.

Please don't hesitate to contact me if you'd like us to work on more 
details of this.

JY

On 10.01.2018 03:27, Gengxuesong (Geng Xuesong) wrote:
>
> Hi JY,
>
> I have read more material about Networking Calculus, and I think it is 
> very useful to describe the network unit behavior accurately and make 
> the worst case end-to-end latency smaller than the sum of worst case 
> latency of every hop.
>
> It will be very charming if we can prove the end-to-end latency will 
> be shorter significantly. And as the author of DetNet YANG module, I 
> am also very interested in specifying ‘the rate and latency parameters 
> of a per-flow scheduler; the parameters of the shaping algorithm’ 
> based on the method offered by Networking Calculus, as you have 
> mentioned in the email (In my understanding, most of the parameters of 
> different queuing management algorithm have been defined in IEEE, 
> maybe we can make use of them and redefine them in a rigorous 
> mathematical model ).
>
> *From:*detnet [mailto:[email-masked]] *On Behalf Of *Le 
> Boudec Jean-Yves
> *Sent:* Monday, January 08, 2018 8:05 PM
> *To:* [email-masked]
> *Subject:* Re: [Detnet] End-to-end latency versus per-hop latency bounds
>
>     There are cases in detnet where the end-to-end latency is less
>     than the sum of the latencies at every hop:
>
>     burstiness increase. The worst case of the sum of the delays at
>     (1) and (2) is strictly less than the sum of the worst cases of
>     (1) and (2) – this is an instance of “reshaping is for free” [3].
>
>     worst case end-to-end delay. If the only information available to
>     a path computation application is the per-hop latency, then the
>     schedulers. Therefore, it seems that these drafts should be
>     adapted to allow for an accurate computation of the end-to-end
>     latency.
>