分组化对 Network Calculus 分析的影响

Network calculus (NC) is a theory for performance guarantee analysis of communication networks [ 1 ] [ 2 ] [ 3 ] [ 4 ]. A key idea of network calculus is to model traffic and service processes using some bounding functions and base the analysis on them. Among the various network calculus models, service curve models play a central role, based on which various performance bounds can be derived [ 1 ] [ 2 ] [ 3 ] [ 4 ]. Since its introduction in the early 1990s [ 5 ] [ 6 ], the network calculus has been extended and applied to various types of communication networks that are packet-switched. In particular, for IEEE 802.1 Time-Sensitive Networking (TSN) networks [ 7 ] and for IETF Deterministic Networking (DetNet) networks [ 8 ], the theory has been extensively utilized to construct service models and compute performance bounds. Representative results include [ 9 ], [ 10 ], [ 11 ] and [ 12 ]. A comprehensive review can be found in [ 13 ], and more recent results include [ 14 ] [ 15 ]. All these results are based on the service curve models of the transmission selection schemes studied, among which the constant bit rate link and strict priority scheduling are the most fundamental or default settings [ 7 ] [ 8 ].

However, the investigation in this paper reveals that the widely adopted service curve characterization results, e.g. [ 9 ], [ 10 ], [ 11 ], [ 12 ], [ 14 ], and [ 15 ], for the two fundamental settings are faulty. In particular, counterexamples can be constructed, which disapproves the results of the adopted service curves. A closer look shows that the packetization effect is overlooked in them. The investigation is extended to examine the validity of the performance bounds derived from the faulty service curves. Counterexamples can also be constructed for output and backlog bounds as well as for the characterisation of the service curve of a concatenation system. This indicates that there is a need to update the service curve models and consequently also the performance bounds. To meet this need, corrected service curves and performance bounds for the two fundamental settings are derived, based on the idea of factoring the packetization effect directly into the service model. These results remind the necessity of taking the packetization effect into account when applying network calculus analysis.

The rest is organized as follows. In the next section, the system model and network calculus basics are introduced. In Section 3, it is shown with counterexamples that the widely adopted service curves for the two fundamental settings are faulty due to ignoring the packetization effect. Then, a study on the impact of using such faulty service curves on performance bounds is conducted. At the end of Section 3, discussion on related results from the network calculus theory is provided, which reveals that adjustments suggested by the theory for packetization have been overlooked by the faulty service curve results. In Section 4, corrected service curves and performance bounds are proved. Finally, conclusions are drawn in Section 5.

We consider systems in a packet-switched network. In particular, we focus on data traffic transmission over a constant bit rate link and through a priority queue that competes transmission over such a link with other priority queues. By convention, in such a system, a packet is said to have arrived (respectively, been served) when and only when its last bit has arrived (respectively, departed) [ 7 ]. When a packet arrives, the packet may be queued and the buffer size for the queue is assumed to be large enough, ensuring no packet loss. The queue is FIFO and initially empty.

The system is modeled by an input traffic process A ​ (t) A(t), a service process S S, and an output traffic process A ∗ ​ (t) A^{*}(t) as illustrated in Figure 1. Specifically, A ​ (t) A(t) denotes the cumulative amount of traffic from the input flow entering the system and A ∗ ​ (t) A^{*}(t) the cumulative amount of traffic from the flow leaving the system, up to time t t (excluded). By convention, we adopt A ​ (0) = A ∗ ​ (0) = 0 A(0)=A^{*}(0)=0. In addition, we define A ​ (s, t) ≡ A ​ (t) − A ​ (s) A(s,t)\equiv A(t)-A(s) and A ∗ ​ (s, t) ≡ A ∗ ​ (t) − A ∗ ​ (s) A^{*}(s,t)\equiv A^{*}(t)-A^{*}(s), which respectively denote the amount of input traffic and the amount of output traffic in period [ s, t) [s,t). Since traffic at t t is excluded, A ​ (t, t) = 0 A(t,t)=0 by convention and so is A ∗ ​ (t, t) = 0 A^{*}(t,t)=0.

In addition, we can also model the input and output processes of the flow using marked-point processes, where packetization of traffic is explicitly taken into account [ 1 ]. Specifically, for the input, the marked point process (a →, l →) (\overrightarrow{a},\overrightarrow{l}) consists of two sequences of variables a → = { a (n), n = 0, 1, 2, … } \overrightarrow{a}=\{a(n),n=0,1,2,...\} and l → = { l (n), n = 0, 1, 2, … } \overrightarrow{l}=\{l(n),n=0,1,2,...\}, where a ​ (n) a(n) denotes the arrival time of packet n n and l ​ (n) l(n) its length. For the output, a similar marked point process is defined which is (d →, l →) (\overrightarrow{d},\overrightarrow{l}) with d → = { d (n), n = 0, 1, 2, … } \overrightarrow{d}=\{d(n),n=0,1,2,...\}, where d ​ (n) d(n) denotes the departure time of the n n -th packet from the system. Here, the packet 0 is a virtual packet, and by convention a ​ (0) = 0 a(0)=0, l ​ (0) = 0 l(0)=0 and d ​ (0) = 0 d(0)=0.

The backlog at time t t, denoted as B ​ (t) B(t), is: B ​ (t) = A ​ (t) − A ∗ ​ (t). B(t)=A(t)-A^{*}(t). (1) The delay of packet n (≥ 1) n(\geq 1), denoted by D ​ (n) D(n), is: D ​ (n) = d ​ (n) − a ​ (n). D(n)=d(n)-a(n). (2) In network calculus, a related delay concept, called virtual delay, has been adopted. Specifically, the virtual delay at time t (> 0) t(>0), denoted as D ​ (t) D(t), is defined as [ 1 ] [ 2 ] [ 3 ] [ 4 ]: D ​ (t) = inf { τ ≥ 0: A ​ (t) ≤ A ∗ ​ (t + τ) }. D(t)=\inf\{\tau\geq 0:A(t)\leq A^{*}(t+\tau)\}. (3)

Let ℱ \mathbf{\mathcal{F}} denote the set of nonnegative nondecreasing functions, and ℱ 0 \mathbf{\mathcal{F}}_{0} its subset with f ​ (0) = 0 f(0)=0. By their definitions, A ​ (⋅) A(\cdot) and A ∗ ​ (⋅) A^{*}(\cdot) are both in ℱ 0 \mathbf{\mathcal{F}}_{0}.

A flow A A is said to have an arrival curve α ∈ ℱ \alpha\in\mathbf{\mathcal{F}}, if for all 0 ≤ s ≤ t 0\leq s\leq t, the traffic A ​ (s, t) A(s,t) is upper-constrained by [ 2 ]: A ​ (s, t) ≤ α ​ (t − s). A(s,t)\leq\alpha(t-s). (4)

A system is said to provide a service curve β ∈ ℱ 0 \beta\in\mathbf{\mathcal{F}}_{0}, if for any time t ≥ 0 t\geq 0, there exists some time s ∈ [ 0, t ] s\in[0,t] such that A ∗ ​ (t) ≥ A ​ (s) + β ​ (t − s) A^{*}(t)\geq A(s)+\beta(t-s) or equivalently, there holds for all t ≥ 0 t\geq 0 [ 2 ], A ∗ ​ (t) ≥ A ⊗ β ​ (t) ≡ inf 0 ≤ s ≤ t { A ​ (s) + β ​ (t − s) }. A^{*}(t)\geq A\otimes\beta(t)\equiv\inf_{0\leq s\leq t}\{A(s)+\beta(t-s)\}.

If the input flow has an arrival curve α \alpha and the system provides to the input flow a service curve β \beta, there hold [ 2 ]: (i) the output has an arrival curve α ∗ ​ (t) ≡ sup u ≥ 0 { α ​ (u + t) − β ​ (u) } \alpha^{*}(t)\equiv\sup_{u\geq 0}\{\alpha(u+t)-\beta(u)\}, i.e. ∀ s, t ≥ 0 \forall s,t\geq 0, A ∗ ​ (s, s + t) ≤ α ∗ ​ (t); A^{*}(s,s+t)\leq\alpha^{*}(t); (5) (ii) the backlog B ​ (t) B(t) is upper-bounded by, ∀ t ≥ 0 \forall t\geq 0, B ​ (t) ≤ sup t ≥ 0 { α ​ (t) − β ​ (t) }; B(t)\leq\sup_{t\geq 0}\{\alpha(t)-\beta(t)\}; (6) (iii) the virtual delay D ​ (t) D(t) is upper-bounded by, ∀ t ≥ 0 \forall t\geq 0: D ​ (t) ≤ sup t ≥ 0 inf { τ ≥ 0: α ​ (t) ≤ β ​ (t + τ) }. D(t)\leq\sup_{t\geq 0}\inf\{\tau\geq 0:\alpha(t)\leq\beta(t+\tau)\}. (7)

As an example, suppose that the input flow is constrained by a token bucket with token generating rate ρ \rho and bucket size σ \sigma [ 5 ] or has an arrival curve α ​ (t) = ρ ​ t + σ \alpha(t)=\rho t+\sigma. In addition, the system provides to the input a latency-rate service curve β ​ (t) = R ​ (t − T) + \beta(t)=R(t-T)^{+}, where R R is called the rate term and T T the latency term. If ρ ≤ R \rho\leq R, the bounds from Theorem 2.1 can be written as α ∗ ​ (t) \displaystyle\alpha^{*}(t) = \displaystyle= ρ ​ t + (σ + ρ ​ T) \displaystyle\rho t+(\sigma+\rho T) (8) B ​ (t) \displaystyle B(t) ≤ \displaystyle\leq σ + ρ ​ T \displaystyle\sigma+\rho T (9) D ​ (t) \displaystyle D(t) ≤ \displaystyle\leq σ R + T \displaystyle\frac{\sigma}{R}+T (10)

In network calculus analysis, an important technique for finding the service curve characterization of a system makes use of the concept of strict service curve and its relation with the service curve model as summarized below.

A system is said to provide a strict service curve β ∈ ℱ 0 \beta\in\mathbf{\mathcal{F}}_{0}, if during any backlogged period of length t t, the output satisfies [ 2 ] A ∗ ​ (t) ≥ β ​ (t) A^{*}(t)\geq\beta(t).

If β (∈ ℱ 0 \beta(\in\mathbf{\mathcal{F}}_{0}) is a strict service curve of a system, it is also a service curve of the system [ 2 ].

For a concatenation system, the following result is important for finding its service curve characterization.

Consider a flow that traverses two systems S 1 S_{1} and S 2 S_{2} in sequence. If each system S i, (i = 1, 2) S_{i},(i=1,2) offers a service curve of β i \beta_{i} to its input, then the concatenated system offers a service curve of β 1 ⊗ β 2 \beta_{1}\otimes\beta_{2} to the flow [ 2 ].

In this paper, we focus on two fundamental transmission selection settings in a packet-switched network. One is a (work-conserving) constant bit rate link, and the other is a strict priority queue for packet transmission on such a link. The former is the foundation of any other transmission selection algorithm, while the latter is commonly implemented, e.g. as the default setting for time-sensitive networking [ 7 ]. For the two fundamental cases, the following service curve results have been widely applied, e.g. in [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] and [ 15 ]: • A (work-conserving) link with constant bit rate c c provides a (strict) service curve c ​ t ct. • When (non-preemptive) strict priority is applied on the link, the highest priority queue receives a (strict) service curve c ​ (t − l M l c) + c(t-\frac{l^{M_{l}}}{c})^{+}, where l M l l^{M_{l}} denotes the maximum packet length of all lower priority queues and (x) + ≡ max ⁡ { x, 0 } (x)^{+}\equiv\max\{x,0\}.

A (work-conserving) link with constant bit rate c c provides a (strict) service curve c ​ t ct.

When (non-preemptive) strict priority is applied on the link, the highest priority queue receives a (strict) service curve c ​ (t − l M l c) + c(t-\frac{l^{M_{l}}}{c})^{+}, where l M l l^{M_{l}} denotes the maximum packet length of all lower priority queues and (x) + ≡ max ⁡ { x, 0 } (x)^{+}\equiv\max\{x,0\}.

Unfortunately, as shown in the following Section 3.1, both are faulty.

The intuition behind using c ​ t ct as a (strict) service curve of the system is as follows. Since the link is work-conserving, during any backlogged period, the link outputs traffic (in bits) at a rate c c and hence has a strict service curve c ​ t ct, with which c ​ t ct as a service curve can also be concluded from Proposition 1. While this sounds straightforward, the following example and discussion highlight that special care is needed when packetization effect needs to be taken into account.

Consider the transmission of a packet n n on the link as illustrated in Figure 2. Without considering the packetization effect, we would have A ​ (s, t) = A ∗ ​ (s, t) = c ​ (t − a ​ (n)) A(s,t)=A^{*}(s,t)=c(t-a(n)) (in bits). However, under the packet model, taking packetization into account, we actually have A ​ (s, t) = l ​ (n) A(s,t)=l(n) while A ∗ ​ (s, t) = 0 A^{*}(s,t)=0. The former is because at time a ​ (n) a(n) which is within [ s, t) [s,t), the (last bit of the) packet has arrived so that transmission can start. In contrast, for A ∗ ​ (s, t) A^{*}(s,t), d ​ (n) d(n) is not within the period, which means that the last bit of the packet has not finished transmission, so the packet is not considered to have been transmitted or served in the period considered [ s, t) [s,t). Because 0 ≤ c ​ (t − a ​ (n)) ≤ l ​ (n) 0\leq c(t-a(n))\leq l(n), we have A ∗ ​ (s, t) ≤ c ​ (t − s) A^{*}(s,t)\leq c(t-s), which contracts the definition of strict service curve if c ​ t ct were used as a strict service curve.

The discussion above disapproves the validity of using c ​ t ct as a strict service curve. However, the question of whether c ​ t ct is a valid service curve remains. For this, we construct a case where A ∗ ​ (t) ≥ A ⊗ β ​ (t) A^{*}(t)\geq A\otimes\beta(t) does not hold for β ​ (t) = c ​ t \beta(t)=ct.

Consider the first packet. Let a ​ (1) a(1) be its arrival time and l ​ (1) (> 0) l(1)(>0) its length. Then, for any time t ∈ [ a ​ (1), a ​ (1) + l ​ (1) c) t\in[a(1),a(1)+\frac{l(1)}{c}), the period (a ​ (1), t) (a(1),t) is backlogged because the packet has arrived but has not left. In addition, we have: A ⊗ β ​ (t) \displaystyle A\otimes\beta(t) = \displaystyle= inf 0 ≤ s ≤ t { A ​ (s) + c ​ (t − s) } \displaystyle\inf_{0\leq s\leq t}\{A(s)+c(t-s)\} (11) = \displaystyle= min ⁡ { inf 0 ≤ s < a ​ (1) { A ​ (s) + c ​ (t − s) }, inf a ​ (1) ≤ s ≤ t { A ​ (s) + c ​ (t − s) } } \displaystyle\min\left\{\inf_{0\leq s<a(1)}\{A(s)+c(t-s)\},\inf_{a(1)\leq s\leq t}\{A(s)+c(t-s)\}\right\} = \displaystyle= min ⁡ { c ​ (t − a ​ (1)), l ​ (1) } \displaystyle\min\{c(t-a(1)),l(1)\} = \displaystyle= c ​ (t − a ​ (1)) > 0 \displaystyle c(t-a(1))>0 Note that A ∗ ​ (t) = 0 A^{*}(t)=0 because a packet is considered to have been served only when its last bit has left, the first packet has not left at t (< a ​ (1) + l ​ (1) c) t(<a(1)+\frac{l(1)}{c}) and therefore the packet cannot be counted in A ∗ ​ (t) A^{*}(t). In other words, for any t ∈ [ a ​ (1), a ​ (1) + l ​ (1) c) t\in[a(1),a(1)+\frac{l(1)}{c}), A ⊗ β ​ (t) > A ∗ ​ (t) A\otimes\beta(t)>A^{*}(t), which contradicts the requirement of A ∗ ​ (t) ≥ A ⊗ β ​ (t), ∀ t ≥ 0 A^{*}(t)\ \geq A\otimes\beta(t),\forall t\geq 0 for β \beta to be a service curve. Proposition 2 is now concluded.

For a system with constant bit rate c c (in bps), c ​ t ct is neither a strict service curve nor a service curve.

For the (non-preemptive) strict priority case, the intuition behind using c ​ (t − l M l c) + c(t-\frac{l^{M_{l}}}{c})^{+} as a (strict) service curve is as follows. In the formulation, l M l c \frac{l^{M_{l}}}{c} factors in the non-preemption effect, which is, upon arrival, a highest priority packet will have to wait for the packet under transmission to complete even though the packet under transmission is from a lower priority queue. However, as discussed for Proposition 2, when packetization is taken into account, c ​ t ct is not a (strict) service curve for the link. In particular, factoring the non-preemption effect and adding l M l c \frac{l^{M_{l}}}{c} at a ​ (n) a(n) in Figure 2, the same analysis taking packetization into account can be conducted for the highest priority queue, from which we can consequently conclude Proposition 3.

For the highest priority queue on a link with constant bit rate c c, c ​ (t − l M l c) + c(t-\frac{l^{M_{l}}}{c})^{+} is neither a strict service curve nor a service curve.

The impact of packetization on the service curve characterization results as investigated above and summarized in Propositions 2 and 3 has two immediate implications:

• The various performance bounds derived from the faulty service curves, such as output arrival curve, backlog and delay bounds, must be re-examined for their validity and possibly updated. • For any complex setting that builds on the two fundamental cases, if its service curve result implies a faulty service curve for either of the two fundamental cases as indicated in Propositions 2 and 3, the service curve result for the complex setting as well as the correspondingly derived performance bounds will need to be re-examined and possibly updated.

The various performance bounds derived from the faulty service curves, such as output arrival curve, backlog and delay bounds, must be re-examined for their validity and possibly updated.

For any complex setting that builds on the two fundamental cases, if its service curve result implies a faulty service curve for either of the two fundamental cases as indicated in Propositions 2 and 3, the service curve result for the complex setting as well as the correspondingly derived performance bounds will need to be re-examined and possibly updated.

For the latter, since a fundamental case is a special case of the complex setting, if the result for the special case is faulty, the result for the complex setting cannot hold either. For the former, it is worth highlighting that the constant bit rate case is implied in the strict priority case (SP). Specifically, it is a special case of SP with a single queue in the system.

In this subsection, we investigate the impact of a faulty service curve on the correspondingly obtained performance bound results. By constructing counterexamples, we show that the faulty service can lead to faulty output bound, faulty backlog bound and faulty concatenation service curve, while for delay bound the same conclusion cannot be made. We focus on the constant bit rate case. Because it is the most fundamental setting and is a special case of SP, the related conclusion on the invalidity of a bound is also applicable to the SP case.

To ease discussion, a simple input case is considered. Specifically, the input flow sends packets periodically to the system. Let τ \tau denote the interval between two adjacent packets. All, except packet 1, have the same length l l, while the length of packet 1 is σ (> l) \sigma(>l). For stability, assume l τ < c \frac{l}{\tau}<c. For this input case, it can be verified that it has an arrival curve α ​ (t) = l τ ​ t + σ \alpha(t)=\frac{l}{\tau}t+\sigma. An illustration of A ​ (t) A(t) and α ​ (t) \alpha(t) is presented in Fig. 3, where the output A ∗ ​ (t) A^{*}(t) and an output arrival curve α ∗ ​ (t) \alpha^{*}(t) that uses the same slope as α \alpha are also illustrated. (Remark: For α \alpha and α ∗ \alpha^{*}, they correspond to intervals starting from a ​ (1) a(1) and d ​ (1) d(1) respectively.) For the output, applying β ​ (t) = c ​ t \beta(t)=ct as a service curve to Theorem 2.1 would give A ∗ ​ (s, s + t) ≤ l τ ​ t + σ = α ​ (t) A^{*}(s,s+t)\leq\frac{l}{\tau}t+\sigma=\alpha(t), ∀ s, t ≥ 0 \forall s,t\geq 0, or in other words α ∗ = α \alpha^{*}=\alpha. However, as illustrated in Fig. 3, α ∗ ​ (t) \alpha^{*}(t) needs to have a higher σ ∗ \sigma^{*} than the initial σ \sigma. In other words, the output is not constrained by α ​ (t) \alpha(t) and therefore using α \alpha as an upper bound on the output, based on derivation from the faulty service curve, is wrong.

For backlog, applying β ​ (t) = c ​ t \beta(t)=ct as service curve to Theorem 2.1 gives B ​ (t) ≤ σ B(t)\leq\sigma, ∀ t ≥ 0 \forall t\geq 0. However, this backlog bound σ \sigma is incorrect. Consider the same case as illustrated in Fig. 3. In particular, before packet 1 finishes, packet 2 has arrived. Hence, B ​ (t) B(t) for t = d ​ (1) − t=d(1)_{-}, i.e. the time just before packet 1 has finished its transmission, the backlog in the system is σ + l \sigma+l where σ \sigma is the size of packet 1 and l l is that of packet 2. Since σ + l > σ \sigma+l>\sigma, the backlog bound σ \sigma from the faulty service curve is therefore incorrect.

For delay, applying β ​ (t) = c ​ t \beta(t)=ct as service curve to Theorem 2.1 gives D ​ (t) ≤ σ c D(t)\leq\frac{\sigma}{c}, ∀ t ≥ 0 \forall t\geq 0. Surprisingly, unlike that the output bound and backlog bound derived from the faulty service curve are also faulty, no similar conclusion can be made for the delay bound. This is because σ c \frac{\sigma}{c} is actually a valid delay bound, which has been proved but using another service-modeling technique [ 16 ]. More remarks related to this are provided in Section 3.3.

Assume a flow traverses two switches S 1 S_{1} and S 2 S_{2} in sequence where the corresponding output links have constant bit rate c 1 c_{1} and c 2 c_{2} respectively. Let β i ​ (t) = c i ​ t, (i = 1, 2) \beta_{i}(t)=c_{i}t,(i=1,2). If they were correct service curves for S 1 S_{1} and S 2 S_{2} respectively, we would have β 1 ⊗ β 2 ​ (t) = min ⁡ { c 1, c 2 } ​ t \beta_{1}\otimes\beta_{2}(t)=\min\{c_{1},c_{2}\}t to be a service curve for the concatenation system. Then, if the input has an arrival curve of ρ ​ t + σ \rho t+\sigma with ρ ≤ min ⁡ { c 1, c 2 } \rho\leq\min\{c_{1},c_{2}\}, the delay of any packet would be upper-bounded by σ min ⁡ { c 1, c 2 } \frac{\sigma}{\min\{c_{1},c_{2}\}}, for which, however, counter examples can be constructed. Specifically, for simplicity, consider the case where all packets have the same length l l, σ = l \sigma=l and c 1 = c 2 ≡ c c_{1}=c_{2}\equiv c. Then we have σ min ⁡ { c 1, c 2 } = l c \frac{\sigma}{\min\{c_{1},c_{2}\}}=\frac{l}{c}. Furthermore, it is easily verified that for any packet, its delay is at least 2 × l c 2\times\frac{l}{c} due to its transmission time of l c \frac{l}{c} on both systems, which is larger than l c \frac{l}{c}. This implies that concatenation of faulty service curves leads to a faulty concatenation service curve for the concatenated system.

It is worth highlighting that the service curves in the same forms for similar systems have been introduced in the network calculus theory but under different contexts. • In [ 1 ], discrete time is adopted and the service rate c c is in the number of packets per unit time. Under these assumptions, c ​ t ct is proved to be a service curve, called an f f -server in [ 1 ], for the constant rate server and for the highest priority queue. • In [ 2 ] and [ 4 ], the analysis and results do not depend on whether the time model is discrete or continuous, which is also the case in the present paper. In [ 2 ] and [ 4 ], by defining the amount of service counted at the bit level, c ​ t ct is shown to be a strict service curve for the constant bit rate case and so is c ​ (t − l M l c) + c(t-\frac{l^{M_{l}}}{c})^{+} for the highest priority queue on such a link (cf. Proposition 1.3.4 in [ 2 ] and Section 1.2 in [ 4 ]).

In [ 1 ], discrete time is adopted and the service rate c c is in the number of packets per unit time. Under these assumptions, c ​ t ct is proved to be a service curve, called an f f -server in [ 1 ], for the constant rate server and for the highest priority queue.

In [ 2 ] and [ 4 ], the analysis and results do not depend on whether the time model is discrete or continuous, which is also the case in the present paper. In [ 2 ] and [ 4 ], by defining the amount of service counted at the bit level, c ​ t ct is shown to be a strict service curve for the constant bit rate case and so is c ​ (t − l M l c) + c(t-\frac{l^{M_{l}}}{c})^{+} for the highest priority queue on such a link (cf. Proposition 1.3.4 in [ 2 ] and Section 1.2 in [ 4 ]).

To account for the effect of packetization, particularly that a flow is composed of a sequence of (variable-length) packets and that the scheduling algorithm is at the packet level while not at the bit level, a novel concept called packetizer is introduced in [ 1 ] and also adopted in [ 2 ] and [ 4 ]. Its idea is to treat the system as the concatenation of two conceptual subsystems, as shown in Fig. 4. One is the bit-by-bit system, which is the part of the system before packetization is taken effect, and the other is a packetizer that assembles output traffic from the previous subsystem into packets.

With the packetizer concept, it is highlighted in [ 1 ], [ 2 ] and [ 4 ] that additional terms may need to be added to the service curve and performance bound results. In particular, the service curve, the backlog bound, and the concatenation service curve must be adjusted, although the packetizer is shown to not increase the maximum packet delay [ 1 ], [ 2 ] [ 4 ]. Unfortunately, this seems to have been largely overlooked in the recent application of network calculus analysis, e.g., in [ 9 ], [ 10 ], [ 11 ], [ 12 ] [ 13 ], [ 14 ] and [ 15 ], where the faulty service curves are directly adopted without considering the packetization effect.

Unlike relying on the concept of packetizer to account for the packetization effect in [ 1 ], [ 2 ], and [ 4 ], we take packetization into direct consideration when modeling the arrival and service processes. More specifically, as introduced in Section 2, we adopt the convention that a packet is said to have arrived (respectively, been served) when and only when its last bit has arrived (respectively, departed) and hence model the arrival and departure processes as marked point processes. Based on this idea, we conduct network calculus analysis and present corrected service curves and performance bounds for the two fundamental cases in the next Section 4.

For the constant bit rate case, corrected service curves are presented in Proposition 4.

A system with constant bit rate c c offers a strict service curve and a service curve c ​ (t − l M c) + c(t-\frac{l^{M}}{c})^{+}, where l M l^{M} denotes the maximum packet length in the system.

Consider any backlogged period (s, t ] (s,t] as shown in Figure 5, and let n 0 n_{0} denote the packet whose arrival starts the backlogged period. Clearly, we have s ≥ a ​ (n 0) s\geq a(n_{0}). Without loss of generality, suppose that packet m m is the first packet that leaves after time s s, and n n the first packet that departs after time t t. By their definitions, we must have d ​ (m − 1) < s ≤ d ​ (m) d(m-1)<s\leq d(m) and d ​ (n − 1) ≤ t < d ​ (n) d(n-1)\leq t<d(n). Since the system is backlogged during (s, t ] (s,t], it must also be so during (i) (s, d ​ (m) ] (s,d(m)], (ii) (d ​ (m), d ​ (n − 1) ] (d(m),d(n-1)] and (iii) (d ​ (n − 1), t ] (d(n-1),t]. Because the system has a constant bit rate c c, during any backlogged period of duration τ \tau, the amount of traffic it serves / transmits is c ​ τ c\tau (in bits). We hence have c ​ (d ​ (m) − s) ≤ l ​ (m) c(d(m)-s)\leq l(m), c ​ [ d ​ (n − 1) − d ​ (m) ] = ∑ k = m + 1 n − 1 l ​ (k) c[d(n-1)-d(m)]=\sum_{k=m+1}^{n-1}l(k), and c ​ [ t − d ​ (n − 1) ] ≤ l ​ (n) ≤ l M c[t-d(n-1)]\leq l(n)\leq l^{M}. Since A ∗ ​ (s, t) = ∑ k = m n − 1 l ​ (k) A^{*}(s,t)=\sum_{k=m}^{n-1}l(k) as illustrated by Fig. 5, we have A ∗ ​ (s, t) \displaystyle A^{*}(s,t) = \displaystyle= l ​ (m) + c ​ [ d ​ (n − 1) − d ​ (m) ] \displaystyle l(m)+c[d(n-1)-d(m)] (12) ≥ \displaystyle\geq c ​ [ d ​ (n − 1) − s ] ≥ c ​ (t − s − l M c) \displaystyle c[d(n-1)-s]\geq c(t-s-\frac{l^{M}}{c}) which, together with the fact that A ∗ ​ (s, t) ≥ 0 A^{*}(s,t)\geq 0, ends the proof.

With Proposition 4, various performance bounds can immediately be derived from Theorem 2.1. As a specific example where the input is constrained by a token-bucket arrival curve, they are summarized in Corollary 1.

Consider a traffic flow transmitting over a link that has a constant bit rate c c. If the traffic has a token-bucket arrival curve α ​ (t) = ρ ​ t + σ \alpha(t)=\rho t+\sigma with ρ ≤ c \rho\leq c, there hold: (i) the output has an arrival curve ρ ​ t + σ + ρ ​ l M c \rho t+\sigma+\rho\frac{l^{M}}{c}, i.e. ∀ s, t ≥ 0 \forall s,t\geq 0, A ∗ ​ (s, s + t) ≤ ρ ​ t + σ + ρ c ​ l M; A^{*}(s,s+t)\leq\rho t+\sigma+\frac{\rho}{c}l^{M}; (13) (ii) the backlog B ​ (t) B(t) is upper-bounded by, ∀ t ≥ 0 \forall t\geq 0, B ​ (t) ≤ σ + ρ c ​ l M; B(t)\leq\sigma+\frac{\rho}{c}l^{M}; (14) (iii) the virtual delay D ​ (t) D(t) is upper-bounded by, ∀ t ≥ 0 \forall t\geq 0: D ​ (t) ≤ σ + l M c. D(t)\leq\frac{\sigma+l^{M}}{c}. (15)

In addition, with Proposition 4 and Theorem 2.2, a corrected concatenation service curve can be found for the counterexample case discussed in Section 3.2.

Consider a flow that traverses two switches in sequence. The corresponding output links have constant bit rate c i, (i = 1, 2) c_{i},(i=1,2) respectively. The concatenation system offers to the flow a service curve of min ⁡ { c 1, c 2 } ​ (t − l M c 1 − l M c 2) + \min\{c_{1},c_{2}\}(t-\frac{l^{M}}{c_{1}}-\frac{l^{M}}{c_{2}})^{+}.

For the strict priority case, a corrected strict service curve, which is also a service curve, is presented in Proposition 5. For the proof, it is similar to that of Proposition 4. The key difference is that s s may be within the transmission period of a lower priority packet that has started its transmission and cannot be preempted by the arrival of the highest priority packet n 0 n_{0}. In such a scenario, we have c ​ (s − d ​ (n 0)) ≤ l ​ (n 0) + l M l c(s-d(n_{0}))\leq l(n_{0})+l^{M_{l}}, c ​ (d ​ (n − 1) − d ​ (n 0)) = ∑ k = n 0 + 1 n − 1 l ​ (k) c(d(n-1)-d(n_{0}))=\sum_{k=n_{0}+1}^{n-1}l(k), and c ​ [ t − d ​ (n − 1) ] ≤ l ​ (n) ≤ l M c[t-d(n-1)]\leq l(n)\leq l^{M}. From these, we obtain A ∗ ​ (s, t) \displaystyle A^{*}(s,t) = \displaystyle= ∑ k = n 0 n − 1 l ​ (k) ≥ c ​ [ d ​ (n − 1) − s − l M l c ] ≥ c ​ (t − s − l M c − l M l c) \displaystyle\sum_{k=n_{0}}^{n-1}l(k)\geq c[d(n-1)-s-\frac{l^{M_{l}}}{c}]\geq c(t-s-\frac{l^{M}}{c}-\frac{l^{M_{l}}}{c}) (16) where l M l^{M} and l M l l^{M_{l}} respectively denote the maximum packet length of the considered highest priority queue and the maximum packet length of all lower priority queues. For other scenarios, where the arrival of the highest priority packet n 0 n_{0} does not see any ongoing transmission of a lower priority packet, they are the same as in the proof of Proposition 4 and hence A ∗ ​ (s, t) ≥ c ​ (t − s − l M c) A^{*}(s,t)\geq c(t-s-\frac{l^{M}}{c}). Combining all scenarios and the fact that A ∗ ​ (s, t) ≥ 0 A^{*}(s,t)\geq 0, Proposition 5 can be concluded.

For the highest priority queue in a system with constant service rate c c (in bps), c ​ (t − l M c − l M l c) + c(t-\frac{l^{M}}{c}-\frac{l^{M_{l}}}{c})^{+} is both a strict service curve and a service curve.

Similarly, with Proposition 5, various performance bounds can also be derived from Theorem 2.1. Specifically, if the input is constrained by a token-bucket arrival curve, the corresponding bounds are summarized in Corollary 3.

Consider a traffic flow competing with other flows to transmit on a link that has a constant bit rate c c, and the considered flow is given the highest priority. If the traffic of the highest priority flow has a token-bucket arrival curve α ​ (t) = ρ ​ t + σ \alpha(t)=\rho t+\sigma with ρ ≤ c \rho\leq c, there hold: (i) the output has an arrival curve ρ ​ t + σ + ρ ​ l M + l M l c \rho t+\sigma+\rho\frac{l^{M}+l^{M_{l}}}{c}, i.e. ∀ s, t ≥ 0 \forall s,t\geq 0, A ∗ ​ (s, s + t) ≤ ρ ​ t + σ + ρ c ​ (l M + l M l); A^{*}(s,s+t)\leq\rho t+\sigma+\frac{\rho}{c}(l^{M}+l^{M_{l}}); (17) (ii) the backlog B ​ (t) B(t) is upper-bounded by, ∀ t ≥ 0 \forall t\geq 0, B ​ (t) ≤ σ + ρ c ​ (l M + l M l); B(t)\leq\sigma+\frac{\rho}{c}(l^{M}+l^{M_{l}}); (18) (iii) the virtual delay D ​ (t) D(t) is upper-bounded by, ∀ t ≥ 0 \forall t\geq 0: D ​ (t) ≤ σ + l M + l M l c. D(t)\leq\frac{\sigma+l^{M}+l^{M_{l}}}{c}. (19)

Similarly, with Proposition 5 and Theorem 2.2, a service curve can be found for the concatenation of two priority systems.

Consider a flow that traverses two systems in sequence. Both systems adopt strict priority scheduling to share among flows the service rate (in bps) c i, (i = 1, 2) c_{i},(i=1,2), which is constant. The flow is given highest priority at both systems. Then, the concatenation system offers the flow a service curve of min ⁡ { c 1, c 2 } ​ (t − l M + l M l c 1 − l M + l M l c 2) + \min\{c_{1},c_{2}\}(t-\frac{l^{M}+l^{M_{l}}}{c_{1}}-\frac{l^{M}+l^{M_{l}}}{c_{2}})^{+}.

The discussion in Section 3.3 has indicated that the idea of packetizer has been adopted in [ 1 ] [ 2 ] [ 4 ] to account for the packetization effect. In particular, for the corresponding bounds as shown in Propositions 4 and 5, the suggested adjustments can be found in [ 1 ] [ 2 ] [ 4 ].

More specifically, for the constant bit case, the service curve is adjusted to be the same as shown in Proposition 4, and the service curve for the concatenation system, the adjustment is also the same. In addition, the output is upper-bounded by, ∀ s, t ≥ 0, A ∗ ​ (s, s + t) ≤ ρ ​ t + σ + l M \forall s,t\geq 0,A^{*}(s,s+t)\leq\rho t+\sigma+l^{M} and the backlog is upper-bounded by ∀ t ≥ 0, B ​ (t) ≤ σ + l M \forall t\geq 0,B(t)\leq\sigma+l^{M}, while for virtual delay, it is upper-bounded by ∀ t ≥ 0, D ​ (t) ≤ σ c \forall t\geq 0,D(t)\leq\frac{\sigma}{c}. Comparing with the bounds shown in Corollary 1, our output and backlog bounds are tighter. However, for virtual delay, the bound derived from ignoring the packetizer effect is better. For the strict priority case, similar comparison can be conducted, and it is also observed that the packetizer approach gives the same service curves, looser output and backlog bounds, but tighter delay bound.

A final remark is that the approach of taking the packetization effect directly into account in service-modeling has been exploited in the network calculus literature, e.g. in [ 1 ] [ 16 ] and [ 17 ]. Recent work [ 17 ] particularly indicates that the same delay bounds can also be derived for the two basic systems using this approach. For a more detailed discussion, which is beyond the scope of the present paper, interested readers are referred to [ 1 ] [ 16 ] and [ 17 ].

Network calculus analysis has been applied to two basic systems that are fundamental or default settings in time-sensitive networks. The focus has been on analyzing their service curve characterizations and performance bounds. It was shown through counterexamples that the service curve s, which have been widely adopted in some recent literature for the two fundamental settings, are actually faulty. Additionally, it was also shown that for the output bound, backlog bound and concatenation service curve results derived from the faulty service curves, counterexamples can also be constructed. This implies that both the service curve characterizations of the two fundamental settings and the correspondingly derived performance bounds need to be adjusted or re-investigated to account for the packetization effect. To this end, the service curves and performance bounds were corrected by exploring the idea of factoring packetization directly into service-modeling. The results exemplify not only that if the packetization effect is overlooked, network calculus analysis can produce faulty results, but also how the packetization effect can be factored in the analysis.