Hugo Daigmorte

Marc Boyer

Luxi Zhao

Modelling in network calculus a TSN architecture mixing Time-Triggered, Credit Based Shaper and Best-Effort queues

Time-Sensitive Networking (TSN) is a collection of standards that extend Ethernet to support safetycritical and real-time applications. TSN integrates multiple traffic types, i.e., Time-Triggered (TT) traffic scheduled based on Gate-Control-Lists (G-CLs), Credit-Based Schaper (CBS) traffic that requires bounded latencies, and Best-Effort (BE) traffic, for which no guarantees are provided. This paper considers multiple classes of AVB/CBS traffic in TSN networks, and models its into network calculus theory, in order to compute upper bounds on delays and memory use in such network.

This work can be seen as an extension of [9]: the global architecture is the same, but the number of CBS queue is arbitrary between 1 and 7, and a shaping curve is also provided.

TSN/TT-CBS-BE: adding Time Triggered flow to AVB

TSN is the name of a working group of IEEE, that produces addenda to Ethernet, and in particular Ethernet queuing (802.1Q), in order to allow it to support real-time data flows. The word "TSN" is also the name used for a network implementing these new functions.

While writing theses lines, the working group is still working, so we can not claim to model the full

In addition to the other checks carried out by the transmission selection algorithm, a frame on a traffic class queue is not available for transmission [as required for tests (a) and (b) in 8.6.8] if the transmission gate is in the closed state or if there is insufficient time available to transmit the entirety of that frame before the next gate-close event (3.1) associated with that queue. A per-traffic class counter, TransmissionOverrun (12.29.1.1.2), is incremented if the implementation detects that a frame from a given queue is still being transmitted by the MAC when the gate-close event for that queue occurs. TSN standard. Moreover, TSN architecture admits a lot of parameters, leading to different behaviours.

Figure 8-12-Transmission selection with gates

In the generic TSN architecture, an output port of a bridge has 8 queues, and arbitration between "ready" queues is done using a static priority policy. Each queue has a gate which is either open or closed. The system has a global period, and a global table, the Gate control list, which defines when is each gate closed or open. Each queue can also have an optional transmission selection algorithms, the main known being the credit based shaper. A queue is ready if and only it is not empty, and the gate is open, and the transmission selection algorithms allows transmission.

This paper only consider one specific class of TSN architecture, called TSN/TT-CBS-BE where: • the higher priority queue, is called the TT queue, it has no transmission selection algorithm;

• it exists n queues, called CBS (or AVB) queues, with a credit based shaper selection algorithm;

• the remaining queues, called best effort (BE) queues, have no transmission selection algorithm and lower priority than TT and CBS;

• the gate control list is such that when the gate of the TT flow is open, all others gates are closed; conversely, when the gate of the TT flow is closed, all others gates are open.

One problem with the closing of gates rises when a queue is ready to send a frame "just before" the closing of its gate. Several policies are defined in standard [START_REF]IEEE Standard for Local and metropolitan area networks -Bridges and Bridged Networks -Amendment 26: Frame Preemption[END_REF] and presented in section 4.

Shaping in bridges

Definition 1 (TSN/TT-CBS-BE). An TSN/TT-CBS-BE scheduler has a set of parameters:

1. a finite set of queues q 1 , . . . , q n (the lower the index, the higher the priority), 2. one or more (N T T ) of theses queues that are time-triggered, Q T T = {q 1 , . . . , q N T T } 3. one or more (N CBS ) of theses queues that are credit-shaped,

Q CBS = {q N T T +1 , . . . , q N T T +N CBS } 4. the remaining queues (N BE = n -N T T - N CBS ) are used for best effort, Q BE = {q N T T +N CBS +1 , . . . , q n } 5.
for each i ∈ Q CBS , two parameters, the send slope, sd i < 0 and the idle slope, id i > 0.

To schedule the incoming packets, a TSN scheduler associates to each i ∈ Q CBS a credit, c i , initialized to 0, and associates to each queues a gate with two states, open and closed, and apply the following set of rules: R1 when the server is idle, its selects to send the head of the non empty queue with the highest priority, with an open gate, and with a non-negative credit (c i ≥ 0) if the queue is credit-shaped;

R2 when a credit-shaped queue q i emits a packet (but not the overhead related to preemption) its credit is decreased with slope sd i , R3 when a credit-shaped queue q i is waiting for the output (it has some backlog, its gate is open, but is not sending packet), its credit is increased with slope id i , R4 when a credit-shaped queue q i is empty, and its gate is open, it is either set to 0 if it is positive, or increased with slope id i as long as it is negative (c i < 0), up to 0.

R5 when the gate of a credit-shaped queue q i is closed, it cannot send message and its credit remains constant.

Note that several integration policy exist, they are describe section 4.

In the TSN standard, the idle slope is implicitly defined from the send slope and the link rate R,

id i = R + sd i , with the constraint that |sd i | < R.
The Figure 2 illustrates the case with 5 queues, where T T, M 1, M 2, M 3 and BE are respective shortcuts for q 1 , q 2 , q 3 , q 4 , q 5 .

The behaviour can be illustrated on some example. Considers the scenario of Figure 3. In this example, the send slope is simply the opposite of the idle slope for the class M2. This figure represents the arrival of packets (on top), the value of the credit of the M2 Figure 3: Illustration of credit evolution class, as a function of time (on the middle), the link output (on the middle), and the gate state (at the bottom).

Three effects are illustrated: basic credit behaviour, blocking due to non preemption of lower priorities flow, blocking due to gate closed and blocking due to higher priorities flow.

At origin, the credit valuer is null, up to the arrival of packet M2-1. From rule R1, M2-1 is the head of queue M2, is has non-negative credit, and the highest priority (others are empty). So, it is sent immediately, and its credit is decreased with slope sd M 2 (rule R2). At end of emission of M2-1, the queue is empty, and the credit is increased with slope id M 2 (rule R4). At arrival of M2-2, the queue M2 is no more empty, but the credit is still negative, so the queue M2 can not be selected. Then, the credit is still increased with slope id M 2 (rule R3), and the packet M2-2 has to wait until the credit value reaches null. Note that it means that it exist some time interval where there is some packet waiting and no output at the link. The TSN queuing is not a work conserving scheduling policy. Once the credit reaches 0, the packet M2-2 can be sent. This is the basic behaviour related to the credit. Now, consider the gate closed effect. After emission of M2-2, the gate become closed. From rule R5, its credit remains constant and no message is sent. Now, consider lower priority blocking. After emission of M2-2, a lower priority packet, M3-1, is received. Assume either that M3-1 is not a creditshaped queue, or that its credit is non negative. From rule R1, as the credit of M2 is negative, M3-1 is se-lected. Since the static priority between queues is not preemptive, M2-3 has to wait, and from, rule R3, its credit is increased whit slope id M 2 . Note that this blocking allows the credit to reach positive values.

Last, higher priority is illustrated: some packet with higher priority, M1-1, is received, and its queue is either no credit-shaped, or has positive credit. Then, is it sent, and the packets M2-3 can not be sent, even with its non-negative credit. Then M2-3 can be sent. At end of emission of M2-3, the queue M2 is empty, and is send to 0 (rule R4).

Remind of Talker traffic constraints

The AVB standard specifies some constraints that the Talkers, the entities sending data in the standard, must respect. [START_REF]Virtual Bridged Local Area Networks Amendment 12: Forwarding and Queuing Enhancements for Time-Sensitive Streams[END_REF] describes different specifications which determine the Talker transmission. Concretely, the Talker behaviour section specifies that the Talker transmits information by frames that are part of an individual data stream, that means, it transmits stream data frames from a Port. In addition, SRP [START_REF]Virtual Bridged Local Area Networks Amendment 14: Stream Reservation Protocol (SRP)[END_REF] defines that the Talker, during each class measurement interval (CMI), can place up to MaxIntervalFrame data frames, each no longer than M axF rameSize into the queue.

There are several interpretations of this specification:

Periodic: some consider that it implies a periodic behaviour, where at most MaxIntervalFrame frames are sent at start of CMI period, Fix windows: others consider that it exists fixed windows, and that at most MaxIntervalFrame frames are sent in each window of length CMI, Sliding windows: and others that on any sliding window of length CMI, there is no more than MaxIntervalFrame frames.

The interpretation generating the data flow with the bigger bursts is the one of the fixed window, and seems to be the one capturing the standard requirements, but since some equipment providers may have a different interpretation, all cases will be modelled in network calculus.

TSN integration modes

The static priority between queues is not preemptive, but some preemption-related mechanisms have been introduced to deal with closing of gates.

The problem is the following: is a queue allowed to start to send a frame "just before" the closing of a gate. If not, some bandwidth is lost. If yes, what append at the gate closing instant?

The addendum [START_REF]IEEE Standard for Local and metropolitan area networks -Bridges and Bridged Networks -Amendment 26: Frame Preemption[END_REF] addresses this problem, called integration mode, making reference to [START_REF]5: Specification and Management Parameters for Interspersing Express Traffic[END_REF] for the details on preemption.

Three integration modes are defined, non preemption, preemption no HOLD/RELEASE and preemption with HOLD/RELEASE. They are illustrated in Figure 5 in the context of our TSN/TT-CBS-BE architecture, i.e. we are only interested in the impact on AVB/CBS queue of it gate closing, corresponding by definition to the opening of the TT gate.

Warning

But before presenting the integration policies, we have to warn that this addendum is quite complex, and somehow misleading. We may have made mistake while reading it, even if our interpretation is for example the same as in [START_REF] Thiele | Formal Worst-Case Performance Analysis of Time-Sensitive Ethernet with Frame Preemption[END_REF]. Moreover, even if our model conforms to the standard, an implementation could also be broken... In particular, in case of preemption, we consider that the credit of a CBS queue is frozen when sending bits related to the preemption overhead. This could be hard to implement.

Preemption recall

The preemption defined in [START_REF]IEEE Standard for Local and metropolitan area networks -Bridges and Bridged Networks -Amendment 26: Frame Preemption[END_REF] Annex R allows to split a frame into several sub-frames, adding some overhead. Nevertheless, no sub-frame can be less than 64 bytes long. So, a frame smaller than 123 bytes can not be split.

The three integration policies

Non-preemption: the idea is to block any lower priority frame emission if its emission time can interfere with the next TT window. That's why a guard band is defined before each time window of a TT frames. The guard band has the length of the maximum-sized frame that may interfere with the TT window, witch in the worst case is 1530 bytes. During the guard band, after the last lower priority frame has completed its transmission, the gates associated to each CBS/AVB and BE queues are closed in advance, to make sure that the link is idle at the beginning of the TT window. The gates are reopened at the end of the TT window.

Preemption no HOLD/RELEASE: the idea is to activate preemption of a CBS frame at gate closing. Then, either it can be preempted of not. The first case can due to two sub-cases: either the left to transmit is less than min packet size (64 bytes) or the frame is to small to be preempted (less than 123 bytes). In both subcases, this frame will complete its transmission and the TT window will be delayed by at most 143 bytes (123 + IFG + preamble). In the second case, the CBS frame can be preempted, the overhead (header + trailer in Figure 5) per preemption is 24 bytes. The gates associated to each AVB/CBSand BE queues are closed during the overhead, and after the trailer only the lower priority frame can be sent.

Preemption with HOLD/RELEASE: the idea is to combine the guard band and the preemption: a reduced guard band (143 bytes) is introduced in order to protect the TT window. During the guard band either the frame can finish its transmission either it cannot and will be preempted. If the frame has to be preempted, the overhead to consider is 8 bytes long (trailer in Figure 5). The gates associated to each CBS and BE queues are closed during the guard band and the overhead, and after the trailer only the lower priority frame can be sent.

Note that from AVB point of view, the three integration policies can be generalised as a system with a (possibly empty) guard band before the gate closing, and some overhead (also possibly empty) after the gate re-opening. If the Talker sends its information with a sliding window semantics, it has the same arrival curves.

Modeling Talkers in network calculus

Proof. As [START_REF] Queck | Analysis of Ethernet AVB for automotive networks using network calculus[END_REF] expresses, in Periodic transmission the Talker sends information periodically every CM I. In this scenario, the worst-case transmission is when the Talker sends all the allowed information during a CM I (MFS • MIF • 8) at the beginning of the period. Figure 6 shows this critical scenario, S. This worst scenario is also an arrival curve, α periodic . This can be upper approximated by a function made of two slopes, α periodic .

The sliding window case is easier: by definition of this semantics, on any interval of width CM I, they are at most M IF frames, so A(t

+ CM I) -A(t) ≤ M IF • M F S.
α noper (t) = min{Ct, b + rt} (1)
α noper (t) = (m t + CMI CMI ) * Ct (2)
where b = 2b and m, r, b as in Thm. 1.

Proof. In this transmission the Talker sends information at any time during each CM I. In this scenario, the worst-case transmission is when the Talker sends all the allowed information in a CM I (MFS • MIF • 8) at the end of the first CM I and then at the beginning of the next one. In the following periods, the worst-case behaviour is the same than the periodic transmission. Figure 7 shows this critical scenario S, and α noper is just a left shift of S.

6 Service Curve for AVB/CBS traffic with non-preemption and preemption modes

In this section, we focus on the service curve analysis for AVB/CBS Class M i (i

∈ Q CBS = [2, N CBS + 1]
) available in an output port h by considering the presence of TT traffic with the non-preemption and the preemption modes, respectively.

Closing time arrival curve

Let us start by discussing the aggregate arrival curve considering the impact of TT traffic in the output

o 0 o 0 o 1 o 1 o 2 o 2 t g(t) g(t)
G(0, t) In order to model the closing time we use two functions g and G:

g(t) = 0 if the gate is closed at t 1 if the gate is open at t (3)
G(t, t + t) = t+ t t g(x) dx (4)
G(0, t) is a cumulative arrival function so it is possible to define its maximal arrival curve and its minimal arrival curve.

Considering a generic periodic system with an hyperperiod P and N TT windows per hyperperiod, each window begin at o i and finish at o i (cf. Fig. 8). We suppose that i

≤ j ⇒ o i ≤ o i ≤ o j ≤ o j .
Lemma 1. The maximal arrival curve for gate closing time in an output port h is

α h T T,u (d) = max 0≤i≤N -1 {G(o i , o i + d)} , (5)
Warning One must warn the reader that, despite the name (and α notation), the "arrival curve for gate closing time" is not a flow arrival curve, but a time bound. It does not bound an amount of data, but an amount of time. Given any time interval [s, t], there will exists some d c , the total duration of closing time of gate on this interval (of course, d c ≤ t -s). Then,

d c ≤ α h T T,u (t -s).
Proof. For any t ≥ 0, g(t) = 0 or g(t) = 1

• Case g(t) = 0: Then it exists i ∈ [0, N -1] such that the next TT window after t is the ith TT window:

o i-1 ≤ t ≤ o i G(t, t + t) = t+ t t g(x) dx = oi t g(x) dx + t+ t oi g(x) dx = oi t 0 dx + t+ t oi g(x) dx ≤ oi+ t oi g(x) dx = G(o i , o i + t) • Case g(t) = 1: Then it exists i ∈ [0, N -1] such that t
≤ oi+ t t g(x) dx + t oi g(x) dx ≤ G(o i , o i + t) So for any t ≥ 0, it exists i ∈ [0, N -1] such that G(t, t+ t) ≤ G(o i , o i + t) ≤ max 0≤i≤N -1 {G(o i , o i + t)} . (6)
Lemma 2. The minimal arrival curve for gate closing time in an output port h is

α h T T,l (t) = min 0≤i≤N -1 {G(o i , o i + t)} , (7)
Proof. For any t ≥ 0, g(t) = 0 or g(t) = 1

• Case g(t) = 0: Then it exists i ∈ [0, N -1] such that the previous TT window before t is the ith TT window:

o i ≤ t ≤ o i+1 G(t, t + t) = t+ t t g(x) dx = t o i 0 dx + t+ t t g(x) dx = t o i g(x) dx + o i + t t g(x) dx + t+ t o i + t g(x) dx ≥ o i + t o i g(x) dx = G(o i , o i + t) • Case g(t) = 1: Then it exists i ∈ [0, N -1] such that t is in the the ith TT window: o i ≤ t ≤ o i G(t, t + t) = t+ t t g(x) dx = o i t g(x) dx + t+ t o i g(x) dx = o i t 1 dx + t+ t o i g(x) dx = o i + t t+ t 1 dx + t+ t o i g(x) dx ≥ o i + t t+ t g(x) dx + t+ t o i g(x) dx ≥ G(o i , o i + t) So for any t ≥ 0, it exists i ∈ [0, N -1] such that G(t, t+ t) ≥ G(o i , o i + t) ≥ min 0≤i≤N -1 {G(o i , o i + t)} . (8)
i ≤ o i ≤ o i and o i ≤ o i ≤ o i ) it is possible to define g min (t) ≤ g(t) ≤ g max (t) G min (t, t + t) = t+ t t g min (x) dx G max (t, t + t) = t+ t t g max (x) dx
Then it is possible to adapt the lemmas (1, 2): Lemma 3. The maximal arrival curve and the minimal arrival curve for closing time in an output port h are

α h T T,u (t) = max 0≤i≤N -1 G max (o i , o i + t) , (9)
α h T T,l (t) = min 0≤i≤N -1 G min (o i , o i + t) . (10)
Proof. • For any t ≥ 0 and any 0 ≤ i ≤ N -1:

G(o i , o i + t) = oi+t oi g(x) dx ≤ oi+t oi g max (x) dx ≤ oi+t oi g max (x) dx + oi+t oi+t g max (x) dx ≤ oi+t oi g max (x) dx + oi+t oi+t 1 dx ≤ oi+t oi g max (x) dx + oi oi 1 dx ≤ oi+t oi g max (x) dx + oi oi g max (x) dx ≤ G max (o i , o i + t)
And so we can deduce that:

max 0≤i≤N -1 {G(o i , o i + t)} ≤ max 0≤i≤N -1 G max (o i , o i + t)
• For any t ≥ 0 and any 0 ≤ i ≤ N -1:

G(o i , o i + t) = o i +t o i g(x) dx ≥ o i +t o i g min (x) dx ≥ o i +t o i g min (x) dx + o i +t o i +t g max (x) dx ≥ o i +t o i g min (x) dx + o i +t o i +t 0 dx ≥ o i +t o i g min (x) dx + o i o i 0 dx ≥ o i +t o i g min (x) dx + oi oi g min (x) dx ≥ G min (o i , o i + t)
And so we can deduce that:

min 0≤i≤N -1 {G(o i , o i + t)} ≥ min 0≤i≤N -1 G min (o i , o i + t)
In the case of TSN, the GCL for an output port h is repeated after the hyperperiod p h GCL . For a given GCL in an output port, we known the finite number of TT traffic windows in the hyperperiod p h GCL , and we denote it with N . The beginning and the end of each TT window are defined by the GCl (o i,GCl and o i,GCl ) but can then be modified by the integration policy and so this values have to be bounded.

For the non-preemption mode, the guard band is established before each time that the TT traffic transmission starts. In the worst-case, the length of the guard band is the maximum transmission time of AVB/BE frames competing on the output port h (L GB ). So the offset are:

o i = o i,GCl - L GB C o i = o i,GCl o i = o i,GCl o i = o i,GCl
For the preemption mode no HOLD/RELEASE, if an AVB/CBS frame can not be preempted (either the left to transmit is less than min packet size or the frame is to small to be preempted), the frame will complete its transmission and the TT window will be delayed by at most L N P (143 bytes, 123 + IFG + preamble). If an AVB/CBS frame is preempted, an overhead is added to the remaining AVB/CBS frame. The overhead will appear immediately before and after each TT traffic window (header + trailer). In the worst-case, the length of the overhead is L OH (24 bytes).

So the offset are:

o i = o i,GCl o i = o i,GCl o i = o i,GCl + L N P C o i = o i,GCl + L N P C
For the preemption mode with HOLD/RELEASE, a reduced guard band is established before each time that the TT traffic transmission starts (header). In the worst-case, the length of the reduced guard band L rGB is 143 bytes. If an AVB/CBS frame is preempted, an overhead is added to the remaining AVB/CBS frame. The overhead will appear during the guard band and immediately after each TT traffic window (trailer). In the worst-case, the length of the trailer is L T (8 bytes).

o i = o i,GCl - L rGB C o i = o i,GCl o i = o i,GCl o i = o i,GCl + L T C

Service curve

In the following, we focus on the analysis of service curve for AVB/CBS Class M i in the output port h. All these result are adapted from tem proposed in [START_REF] De | Complete modelling of AVB in Network Calculus Framework[END_REF], exept the maximal arrival curve which seems incorect and so has not been adapted for TSN. Regardless of modes, any time interval t can be decomposed by

t = t + + t -+ t 0 , ( 11
)
where t + = i t + i represents the rising time of credit M i , t -= j t - j represents the descent time of credit M i and t 0 = k t 0 k is the frozen time of credit M i .

Minimal service curve

Theorem 3. The minimal service curve for AVB/CBS Class M i (i ∈ [1, N CBS ]) in an output port h regardless of modes is given by

β CBS,min h,i (t) = C • idSl i idSl i -sdSl i t -α h T T,u (t) - c max Mi idSl i + ↑ . (12)
where α h T T,u (t) is given by Lemma 3, and c max Mi is the upper bound of credit of the i-th queue given by ( 22), which will be discussed in Sect. 7.

Proof. Assume that R h

Mi (t) and R h * Mi (t) are the arrival and departure processes of AVB/CBS flows of Class M i crossing through the output port h.

Let s be the beginning of the latest server busy period for queue i such that the credit of queue i is null, i.e. for all x in (s, t], either c Mi (x) < 0 or

R h * Mi (x) < R h Mi (x). At time s, R h * Mi (s) = R h
Mi (s) and c Mi (s) = 0. For some arbitrary time t ≥ s, the interval t = t -s can be decomposed by t = t + + t -+ t 0 . t 0 is caused by TT traffic windows, i.e., t 0 = t 0 T T , and t -represents the duration of frame transmission of AVB/CBS Class M i . Therefore we have t -= t - AV B Mi . Then, the variation of credit during the time interval t satisfies

c Mi (t) -c Mi (s) = c Mi (t) = t + idSl Mi + t -sdSl Mi = ( t -t 0 ) • idSl Mi -t -• (idSl Mi -sdSl Mi ).
Therefore, we obtain the relationship of service times for AVB/CBS Class M i and TT traffic in any interval t,

t - AV B Mi = t -= ( t -t 0 ) • idSl Mi -c Mi (t) idSl Mi -sdSl Mi .
(13) Moreover, an upper bound of t 0 is given by Lemma 3.

t 0 ≤ α h T T,u ( t). (14)
Then, considering (13) and ( 14), the departure process AVB/CBS Class M i frames over the interval t is bounded by

R h * Mi (t) -R h * Mi (s) = C • t - AV B Mi ≥ C • ( t -α h T T,u ( t)) • idSl Mi -c max Mi idSl Mi -sdSl Mi .
Since the departure cumulative function R h * Mi (t) is a non-decreasing non-negative function, we have

R h * Mi (t) -R h Mi (s) ≥ C • idSl Mi idSl Mi -sdSl Mi • t -α h T T,u (t) - c max Mi idSl Mi + ↑ = β CBS,min h,i (t).
Then, for ∀0 ≤ s ≤ t,

R h * Mi (t) ≥ inf 0≤s≤t R h Mi (s) + β CBS,min h,i (t) = R h Mi ⊗ β CBS,min h,i (t).
Thus, β CBS,min h,i (t) is the service curve for AVB/CBS Class M i .

Strict minimal service curve

Theorem 4. The strict minimal service curve for AVB/CBS Class M i (i ∈ [1, N CBS ]) in an output port h regardless of modes is given by

β CBS,min h,i (t) = C • idSli idSli -sdSli t -α h T T,u (t) - c max M i -c min M i idSli + ↑ . ( 15
)
where α h T T,u (t) is given by Lemma 3, c max Mi is the upper bound of credit of the i-th queue given by ( 22), which will be discussed in Sect. 7 and c min Mi is the lower bound of credit of the i-th queue given by (21).

Proof. Assume that R h Mi (t) and R h * Mi (t) are the arrival and departure processes of AVB/CBS flows of Class M i crossing through the output port h.

For some arbitrary times t and s such that t ≥ s and (s, t] is a backlogged period. The interval t = t -s can be decomposed by t = t + + t -+ t 0 . t 0 is caused by TT traffic windows, i.e., t 0 = t 0 T T , and t -represents the duration of frame transmission of AVB/CBS Class M i . Therefore we have t -= t - AV B Mi . Then, the variation of credit during the time interval t satisfies

c Mi (t) -c Mi (s) = t + idSl Mi + t -sdSl Mi = ( t -t 0 ) • idSl Mi -t -• (idSl Mi -sdSl Mi ).
Therefore, we obtain the relationship of service times for AVB/CBS Class M i and TT traffic in any interval t,

t - AV B M i = t -= ( t -t 0 ) • idSlM i -cM i (t) + cM i (s) idSlM i -sdSlM i . (16)
Moreover, an upper bound of t 0 is given by Lemma 3.

t 0 ≤ α h T T,u ( t). (17)
Then, considering ( 16) and ( 17), the departure process AVB/CBS Class M i frames over the interval t is bounded by

R h * Mi (t) -R h * Mi (s) = C • t - AV B Mi ≥ C • ( t -α h T T,u ( t)) • idSl Mi -c max Mi + c min Mi idSl Mi -sdSl Mi .
Since the departure cumulative function R h * Mi (t) is a non-decreasing non-negative function, we have

R h * Mi (t) -R h Mi (s) ≥ C • idSl Mi idSl Mi -sdSl Mi • t -α h T T,u (t) - c max Mi -c min Mi idSl Mi + ↑ = β CBS,min h,i (t).
Thus, β CBS,min h,i (t) is the strict service curve for AVB/CBS Class M i .

CBS shaping curve

Theorem 5 (CBS shaping curve). The shaping curve for a CBS Class i (i ∈ [1, N CBS ]) in an output port h is given by

σ CBS h,i (t) = C.idSli sdSli -idSli ( t -α h T T,l ( t)) + c max M i -c min M i idSli + ↑ (18)
where α h T T,l (t) is given by Lemma 3, c max Mi is the upper bound of credit of the i-th queue given by ( 22), and c min Mi is the upper bound of credit of the i-th queue given by (21), which will be discussed in Sect. 7.

Proof. Assume that R h

Mi (t) and R h * Mi (t) are the arrival and departure processes of AVB/CBS flows of Class M i crossing through the output port h.

c min Mi -c max Mi ≤ c = c(t + t) -c(t) ≤ t + .idSl i + t -sdSl i + t 0 .0 ≤ ( t -t --t 0 )idSl i + t -.sdSl i ≤ ( t -t 0 ).idSl i + t -(sdSl i -idSl i ) ≤ ( t -α h T T,l ( t))idSl i -t -(sdSl i -idSl i ) ≤ ( t -α h T T,l ( t))idSl i -R h * Mi sdSl i -idSl i C
Since the departure cumulative function R h * Mi (t) is a non-decreasing non-negative function, we have

R h * M i ≤ C.idSli sdSli -idSli ( t -α h T T,l ( t)) + c max M i -c min M i idSli + ↑ (19)

Maximal service curve

The proposed result on Maximal service curve in [START_REF] De | Complete modelling of AVB in Network Calculus Framework[END_REF] (Theorems 6 and 10) seems incorrect. The proof of Theorem 6 is false. From A (t) ≤ A(s) + f (t -s), it can be deduced that A (t) ≤ sup s≥0 A(s) + f (t -s), that A (t) ≤ inf s≥0 A(s) + f (t -s). And we have doubts on the validity of the result (even if we have no counter example). Then, it has not been adapted to TSN.

Delay bound

According to Network Calculus, the upper bound latency of an Class M i flow τ AV B Mi[k] in the output port h is given by the maximum horizontal deviation between the arrival curve α h AV B Mi (t) of intersecting flows of AVB/CBS Class M i and the service curve

β CBS,min h,i (t) for AVB/CBS Class M i in h, D h AV B Mi[k] = h(α h AV B Mi (t), β CBS,min h,i (t)), (20)
where the service curve is from Theorem 3 and the arrival curve from chapter 5.

Bounding the credit for AVB/CBS traffic

In this section, we bound the traffic for AVB/CBS credit. Let us recall from Sect. 2 how AVB/CBS is transmitted. In TSN, the transmission of AVB/CBS traffic is not only related to the gate states, but also to CBS. Although TT transmission in both preemption and non-preemption modes delays AVB/CBS traffic, the credits for both classes are frozen during these periods. Therefore, we can say that AVB/CBS credits will not be affected by TT traffic. In fact, the credit value is related to the transmission and backlog of AVB/CBS frames during respective AVB/CBS gate open, and settings of idle slope idSl Mi and send slope sdSl Mi for each traffic class, which are configuration parameters given by designer.

Theorem 6. Let L max Mi be the maximal frame size of any flow crossing the queue Q Mi . Then the credit c Mi (t) of Class M i can be lower bounded by:

c min Mi = L max i C sdSl i ≤ c Mi (t) (21)
Proof : Since only sending a frame of Class M i the credit is decreased, the check of the lower bound must be done at the end of the emission of a frame of Class M i . Considering the evolution of the credit, the minimal value of the credit is reached only when the size of the transmitted frame is the maximal one. In this situation the transmission period is defined as t -max Mi = L max Mi /C. Therefore, the credit at the end of the transmission is c

Mi (t + t -max Mi ) = 0 + sdSl Mi • L max Mi /C.
In order to upper bound the credit of AVB/CBS Class M i , a pre-condition is to give the non-overflow condition for AVB/CBS credit. With no constraints on idSl Mi and sdSl Mi for AVB/CBS traffic, the overloaded AVB/CBS traffic may cause a credit overflow, which is a problem that may cause the failure of the anti-starvation function of CBS, hence leading to unbounded WCDs for the AVB/CBS traffic. Thus, we need to constrain idSl Mi and sdSl Mi to make sure the credit of Class M i is bounded in more general situation.

The standard 802.1Qbv gives the constraints between idSl Mi and sdSl Mi , i.e., sdSl Mi = idSl Mi -C. In this section, we are interested to give the constraints such that the credits M i does not overflow considering this condition. Proof : Let c H (t) = i j=1 c Mj (t) denotes the sum of credits of AVB/CBS traffic with the priority same to or higher than M i . Consider a point in time t.

If there is no backlog at all in any AVB/CBS queues Q ≤i AV B = 1≤j≤i {Q Mj } with the priority same to or higher than M i , we have c H (t) ≤ 0. So, consider the case when there is some backlog, and let q H ⊂ Q ≤i AV B be the set of AVB/CBS queues with some backlog at time t.

If no frame is being sent, it means that the credit of each backlogged AVB/CBS queues is negative, which also implies that c H (t) < 0. But if some frame is being sent, let s be the start of the emission of this frame.

If this frame is from the lower priority AVB/CBS queue Q >i AV B = i<j≤N CBS {Q Mj } or the BE queue, it means that either c H (s) = 0 and there is no backlog at all in any AVB/CBS queues Q ≤i AV B = 1≤j≤i {Q Mj } with the priority same to or higher than M i or c H (s) < 0 (otherwise, at time s, an AVB/CBS frame from Q ≤i AV B would have been selected for emission), so in all cases c H (s) ≤ 0. Then, c H (t)-c H (s) ≤ Q M j ∈q H idSl Mj (t-s) ≤ Notice that the frame emission from lower priority AVB/CBS or BE queue is bounded, i.e., t -s ≤ max{L max >i , L max BE } C .

Thus,

c H (t) ≤ max{L max >i , L max BE } C i j=1 idSl Mj .
If this frame is from AVB/CBS queue of Class M k , Q M k ∈ Q ≤i CBS , then between s and t, the credit of the Class M k decreases with the send slope sdSl M k , whereas the credit of each other active Class M j increases with the idle slope idSl Mj . Therefore, we have c H (t) -c H (s)

≤ Q M j ∈q H idSlM j (t -s) + sdSlM k (t -s) ≤ i j=1,j =k idSlM j (t -s) + sdSlM k (t -s) = N CBS j=1 idSlM j -idSlM k + sdSlM k - Q M j ∈Q >i AV B idSlM j    (t -s).
Since sdSl Mi = idSl Mi -C and

N CBS i=1 idSl Mi ≤ C, then c H (t) -c H (s) ≤ - Q M j ∈Q >i AV B idSl Mj • (t -s) ≤ 0.
To sum up, given some t, either c H (t) ≤ 0 or c H (t) ≤ max{L max >i , L

Conclusion

This paper considers multiple classes of AVB/CBStraffic in TSN networks, and models its into network calculus theory, in order to compute upper bounds on delays and memory use in such network.

Figure 1 :

 1 Figure 1: TSN bridge architecture -from [4, Figure 8-12]

Figure 2 :

 2 Figure 2: Architecture of TSN shaper

Figure 4 :

 4 Figure 4: Periodic (top), per Fix Window (middle) and per Sliding Window (bottom) Transmissions

Figure 5 :

 5 Figure 5: AVB-TT integration policies.

Theorem 1 (Figure 6 :

 16 Figure 6: Arrival curves for Periodic or Sliding Window transmission

Theorem 2 (Figure 7 :

 27 Figure 7: Arrival curve for No-Periodic transmission (red) and critical scenario (black)

Figure 8 :

 8 Figure 8: Closing time functions

Theorem 7 .

 7 Let L max Mi be the maximal frame size of any flow crossing the AVB/CBS queue Q Mi and especially L max BE be the maximal frame size of a BE flow. If ∀i, sdSl Mi = idSl Mi -C andN CBS i=1idSl Mi ≤ C, then for any t ≥ 0, the credit value of each Class M i is upper bounded by, c Mi (t) >i = max j∈[i+1,N CBS ] L max Mj , and c min Mj is the lower bound of credit of Class M j from Theorem 6.

idSl

  Mj (t-s).

  Authorized licensed use limited to: ONERA. Downloaded on June 23,2017 at 09:00:06 UTC from IEEE Xplore. Restrictions apply.

	Queue for	Queue for	Queue for	Queue for	Queue for
	traffic class #7	traffic class #6	traffic class #5	traffic class #4	traffic class #0
						Gate control list
						T00: oCooCooo
						T01: CoCooCCo
						T02: oCooCooo
	Transmission Selection Algorithm (Table 8-5)	Transmission Selection Algorithm (Table 8-5)	Transmission Selection Algorithm (Table 8-5)	Transmission Selection Algorithm (Table 8-5)	Transmission Selection Algorithm (Table 8-5)	T03: ooCooCCo T04: oCooCooo T05: CoCCoCCC T06: oCooCooo T07: CoCooCCC
						T08: oCooCooo
						T09: CoCCoCCC
	Transmission Gate = C	Transmission Gate = o	Transmission Gate = C	Transmission Gate = C	Transmission Gate = C	.............
						T78: oCooCooo
						T79: CoCooCCC
			Transmission Selection		C= closed, o=open

  Mj or there exists s such that c H (t) ≤ c H (s). Since this s is also a time instant, either c H (s) ≤ 0, c H (s) ≤ max{L max >i , L max BE }/C • i j=1 idSl Mj or there exists s such that c H (s) ≤ c H (s ). Thus, we can deduce:

	c H (t) ≤	max{L max >i , L max BE } C	•	i j=1	idSl Mj
	Then, by using the Theorem 6, i.e., c Mj (t) ≥ c min Mj ,
	we have:
	c Mi (t) ≤	max{L max >i , L max BE } C	•	i j=1	idSl Mj -	i-1 j=1	c min Mj .

max BE }/C • i j=1 idSl