On the Benefits of Traffic “Reprofiling” The Multiple Hops Case–Part II
arXiv:2604.24930v1 [cs.NI] 27 Apr 2026
Jiaming Qiu, Member, IEEE and Roch Guérin, Fellow, ACM, IEEE
With such schedulers, reprofiling is realized through nonwork-conserving traffic regulators, i.e., shapers2 , that are used to reduce flows’ burstiness. Reprofiling, therefore, introduces a fundamental trade-off: it consumes part of the end-to-end delay budget upfront, leaving tighter delay constraints for in-network scheduling, while the smoother traffic it produces can reduce resource requirements at every hop. How to best leverage this trade-off is scheduler dependent. An adaptive scheduler such as SCED was found [20] to benefit most from “middleground” solutions, i.e., using some of the delay budget to make flows smoother through reprofiling, while preserving enough of it for the scheduler to work with. Unlike SCED, FIFO and static-priority schedulers are static in their classification of packets. How this affects their reprofiling solutions is unclear. Addressing this question is the focus of this paper. The paper follows a similar methodology as [20]. It develops a unified framework to study bandwidth minimization under reprofiling for FIFO and static-priority schedulers, formulates a joint optimization for shaping, scheduling, and bandwidth provisioning, and designs efficient algorithms to solve it. The investigation offers insights into how schedulers’ “expressiveness” influences how reprofiling realizes bandwidth savings. For simple schedulers such as FIFO and static priority, the best or close to best reprofiling option is often “full shaping,” i.e., allocating a flow’s entire delay budget to making it smoother. In contrast [20], SCED prefers less aggressive solutions because its greater scheduling flexibility is capable of exploiting some residual delay budget. The remainder of the paper is structured as follows. Section II offers relevant background on network calculus and traffic shaping. Our problem formulation is introduced in Section III, with Section IV presenting our bandwidth minimization algorithms for FIFO and static-priority schedulers. Section V evaluates their performance across a range of scenarios. Section VI discusses related work, while Section VII concludes the paper. Proofs and supplementary material are relegated to appendices. For reproducibility, our solutions and the settings in which they are evaluated are available at https://github.com/qiujiaming315/traffic-reprofiling.
Abstract—Delivering hard delay guarantees over packet networks is increasingly important to applications ranging from automotive systems, avionics, industrial control, etc. Traffic control and schedulers play an essential role in enforcing such guarantees. In this paper, we focus on “simple” static priority and FIFO schedulers, and explore how reprofiling flows entering the network, i.e., proactively shaping them to a different traffic profile, can deliver delay guarantees with less bandwidth. To that end, we formulate a joint optimization framework and develop efficient algorithms to solve it. Extensive evaluations across both realistic and synthetic topologies demonstrate that, as with more sophisticated schedulers, reprofiling flows is beneficial. They also highlight an intuitive coupling between a scheduler’s capability and its ability to leverage more complex reprofiling solutions. Index Terms—latency, bandwidth, optimization, shaping, network calculus.
I. I NTRODUCTION Applications from domains as varied as automotive systems, avionics, industrial control, smart grids, etc., are increasingly deployed over packet networks where they demand predictable communication with bounded latency [1]–[9]. This is reflected in recent standardization efforts such as TimeSensitive Networking (TSN) and Deterministic Networking (DetNet) [10]–[16], which both focus on enabling deterministic delay guarantees for regulated traffic under a range of scheduling mechanisms. This is the setting this paper targets. Regulated flows indicate desired end-to-end delay bounds, with the token bucket [17] often used as their traffic regulator, one that specifies both sustained transmission rates and burstiness constraints. The network task is then to provision sufficient resources (bandwidth) to guarantee those bounds. Of interest in such a setting is to minimize the required provisioning, i.e., the amount of network bandwidth needed1 . This paper studies the role of reprofiling, i.e., proactively modifying flows’ profiles as they enter the network (and subsequently at each network hop), in reducing the bandwidth required to meet delay guarantees. The benefits of reprofiling with FIFO and static priority schedulers were demonstrated in [18] in a single-hop setting. The extension to multi-hop networks was presented for service curve schedulers (SCED [19]) in a precursor (Part I) to this paper [20]. This paper extends the results to FIFO and static priority schedulers.
II. BACKGROUND A. Network Calculus
J. Qiu and R. Guérin are with the Computer Science and Engineering department at Washington University in St. Louis, Saint Louis, MO 63130, USA, e-mail: {qiujiaming,guerin}@wustl.edu. This work was supported by NSF grant CNS 2006530. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation 1 A dual perspective maximizes the number of flows that can be accommodated for a given amount of bandwidth.
Network calculus [21] provides a framework for computing worst-case delay and buffer bounds in packet networks under deterministic traffic models. In this section, we briefly review key concepts and results on which this paper relies. To the 2 Hence, the paper uses the terms shaping and reprofiling interchangeably.
1
by σ. The 2SRC profile introduces a peak-rate constraint to regulate the transmission of the burst of a flow with tokenbucket arrival curve α = (r, b). This can be realized by concatenating4 two greedy shapers, each implemented as a two-parameter token bucket. Specifically, a 2SRC is realized by combining an (r, B) token bucket with an (R, 0) token bucket, where B = b − rb/R and R ≥ r. The parameter R represents the flow’s peak rate, yielding the arrival curve σ(t) = min(Rt, B + rt) of Fig. 1. As shown in [21, Section 1.4] and illustrated in Fig. 1, using σ to reprofile a flow with arrival curve α introduces a shaping delay D of the form: b (2) D= . R Varying the peak rate R yields a family of shaping profiles b parameterized by their shaping delay D, where D ∈ [0, d], b and d = min(d, b/r) with d the flow’s delay bound. Hence, db is the maximum shaping delay a flow can afford5 . As per [20, Lemma 2], given any shaping delay D, the 2SRC profile is the “smallest” (minimizes the flow’s bandwidth requirements) among all concatenations of token buckets with that shaping delay. In the remainder of the paper, we use the shaping delay D as the parameter that uniquely identifies a 2SRC profile.
extent possible, we follow the notation of [20], and, as in [20], we adopt a fluid model to simplify the exposition. 1) Arrival Curves: Arrival curves constrain the amount of traffic a flow can generate over time [21, Definition 1.2.1]. Formally, given a wide-sense increasing function α(t) for t ≥ 0, a flow with cumulative arrival function A(t) is said to conform to the arrival curve α if ∀s ∈ [0, t],
A(t) − A(s) ≤ α(t − s).
In other words, α(t − s) upper-bounds the amount of traffic that may arrive in any interval of duration t − s. A commonly used arrival curve is the two-parameter token (or leaky) bucket [22], denoted (r, b). It corresponds to the affine arrival curve α(t) = rt+b for t > 0, where r represents the sustained rate of the flow and b its maximum burst size. In this paper, we assume that flows entering the network are regulated by token buckets, which define their traffic profiles. 2) Service Curves: Service curves characterize the minimum service guaranteed to flows. If a flow with cumulative arrival function A(t) is guaranteed a service curve β, then the cumulative service S(t) it has received by time t satisfies the condition: ∃ s ∈ [0, t] such that [21, Section 1.3] S(t) ≥ A(s) + β(t − s). 3) Delay Bounds: Given a flow with arrival curve α and service curve β, its worst-case delay is upper-bounded by the maximum horizontal distance between α and β [21, Section 1.4]. This bound is expressed as ∆(α, β) = sup {inf{s ≥ 0 : α(t) ≤ β(t + s)}} .
C. Shaping Enforcement As discussed earlier, traffic shaping plays an important role in the derivation of delay bounds. Achieving these bounds, however, requires in-network shaping that reapplies a flow’s traffic profile at every hop along its path. This can be realized through Per-Flow shaping, which reshapes individual flows at every hop. This is, however, complex and, therefore, at odds with the simplicity of static-priority and FIFO schedulers. Interleaved Shapers [17], [24] (ILS) offer an alternative. They enforce shaping per switch port rather than per flow. Specifically, an interleaved shaper processes packets from multiple flows in a single FIFO queue and only checks the packet at the head of the queue against its shaping profile. This greatly reduces implementation overhead while preserving the same6 worst-case delay guarantees as per-flow shaping [17]. We, therefore, assume that in-network reprofiling is realized using per input port and per priority class interleaved shapers placed at each switch output port.
(1)
t≥0
In the following sections, we use Eq. (1) to derive the bandwidth required to guarantee per-hop scheduling delays. B. Traffic Shaping Shapers regulate traffic to ensure compliance with a specified arrival curve. Following its arrival, a packet’s eligibility time is the earliest time at which it can depart the shaper without violating the arrival-curve constraint. Greedy shapers [21, Section 1.5.3] release packets as soon as they become eligible. Traffic shaping plays an important role in multi-hop networks. Shapers can be placed before schedulers to (re)shape flows to their original traffic profiles without affecting worstcase delays3 . This prevents burst accumulation across hops, which can significantly tighten end-to-end delay bounds [23].
III. P ROBLEM F ORMULATION A. Problem Setting
bits 𝑏 𝐵 = 𝑏 − 𝑟𝐷
𝛼
𝑟
𝜎
We consider a network with fixed routing on a topology consisting of n links. The network carries m token-bucket regulated flows (ri , bi ) with end-to-end delay bounds di , 1 ≤ i ≤ m. P = {P1 , P2 , . . . , Pm } denotes the set of flow paths, with Pi specifying the sequence of links traversed by flow i. Given link j, 1 ≤ j ≤ n, Fj denotes the set of flows whose path includes link j. Our objective is to satisfy the flows’
𝑟
𝐷 𝑅 = 𝑏/𝐷
time
Fig. 1: Two-Slope Reprofiling Curve (2SRC).
4 Concatenation maps to the min-plus convolution operator of [21, Section 3.1.6]. 5 Our fluid-flow framework also assumes zero propagation delays. 6 As noted in [17], in packetized settings, a small discrepancy may arise from heterogeneous packet sizes or processing delays.
In this paper, we consider the shaping strategy of [20] based on a Two-Slope Reprofiling Curve (2SRC), denoted 3 Based on the Pay Bursts Only Once (PBOO) property [21, Section 1.4.3].
2
To this end, we introduce the minimal service function Shj for priority class h at link j. We note that Shj is mainly used as an intermediate construct to facilitate the computation of Cj . The formal relationship between Cj and Thj comes from Network Calculus via Eq. (1). Formally, Shj is defined as ( 0, t ≤ Thj , (5) Shj (t) = P ′ H (t) + H (t − T ), t > Thj , ′ hj hj 1≤h <h h j
delayP bounds while minimizing the total network bandwidth, n C = j=1 Cj , where Cj is the bandwidth of link j. To achieve this goal, we seek to proactively modify the traffic profiles of individual flows through traffic shaping. As mentioned in Section II-B, we focus on 2SRC shaping profiles that for a token-bucket controlled (ri , bi ), 1 ≤ i ≤ m, flow adds a peak-rate constraint Ri , and, as per Eq. (2), a shaping delay Di = Rbii . The remaining delay budget, di − Di , then becomes the flow’s new allowable end-to-end network delay. Each network hop employs a static-priority scheduler with k priority classes (for FIFO, k = 1). At hop j, every flow i ∈ Fj is assigned a priority tag pij indicating its priority class, where smaller values of pij correspond to higher priorities. Flows within the same priority class h are scheduled in FIFO order and share the same worst-case local scheduling deadline Thj . The priorities assigned to flows in Fj collectively define the priority assignment Γj . Let Gh (Γj ) denote the subset of flows mapped to priority class h under Γj . The assignment satisfies [ Gh (Γj ) = Fj ,
where Hhj (t) =
denotes the aggregate arrival curve of flows assigned to class h, assuming that each flow i is shaped according to its 2SRC arrival curve σi prior to multiplexing by the scheduler. Intuitively, the minimal service function specifies the minimum cumulative service that priority class h must receive from the scheduler in order to meet its worst-case delay bound Thj . The expression captures two competing sources7 for bandwidth: (i) traffic from higher-priority classes, i.e., the aggregate traffic from classes h′ < h, and (ii) traffic from flows within class h, which must be served within Thj after arrival. The minimal service function ensures that traffic from class h arriving at time t is guaranteed to depart by time t + Thj . Next, we provide an expression for the minimum bandwidth required to meet the deadlines of all priority classes at hop j. Proposition 1: Consider a hop j equipped with a staticpriority scheduler with k priority classes indexed in decreasing order of priority from 1 to k (priority 1 being the highest), serving the set of flows Fj . Given a priority assignment Γj and the corresponding minimal service function Shj for each priority class, the hop must provision a bandwidth of at least Cj∗ in order to satisfy the deadlines of all classes, where X ∗ Cj∗ = max ri , Chj , (6)
∀ 1 ≤ h < h′ ≤ k.
This ensures that each flow is assigned to exactly one priority class and that the sets {Gh (Γj )}kh=1 form a partition. The inputs to our problem consist of the flows’ parameter vectors (r, b, d), representing the flows’ rates, burst sizes, and delay bounds, and the flows’ path set P . The optimization variables are the vector of shaping delays D, the global priority assignment Γ, and the matrix T (per flow and link) of local scheduling deadlines. OurPobjective is to minimize the total n network bandwidth C = j=1 Cj . The problem can then be formulated as a constrained optimization as follows: MINSP :
min
D,Γ,T
n X
Cj ,
(3)
j=1
s.t. Di +
X
Tpij j ≤ di ,
1≤h≤k
1 ≤ i ≤ m.
j∈Pi
MINF IF O :
min D,T
∗ Chj = sup
Cj ,
t>Thj
X
(4) Tj ≤ di ,
Shj (t) , t
(7)
is the bandwidth needed to serve priority h traffic by Thj . The proof is in Appendix B-A. Fig. 2 illustrates the minimal service function of priority class 2 and the corresponding bandwidth required to transmit its traffic within deadline T2j in an example with three flows and two priority classes. Flow 1 belongs to the highest priority class 1, and flows 2 and 3 to class 2. Consistent with Eq. (5), traffic from higher-priority classes (flow 1) arrives greedily according to its 2SRC starting at time 0. Traffic from class 2 (flows 2 and 3) also arrives greedily according to their 2SRCs starting at time 0, but their contributions to the minimal service function of priority class 2 are shifted by its local deadline T2j . The intuition behind Fig. 2 is that we need to ensure that the service S2j (t) (blue line) that traffic from class 2 receives never “falls behind” by more than T2j , where falling behind is captured by crossing the (red) line Cj∗ ·t. The initial shift of T2j
j=1
s.t. Di +
i∈Fj
where
In the special FIFO case k = 1, the priority assignment becomes irrelevant and all flows traversing link j share the same deadline Tj . The optimization then simplifies to n X
σi (t),
i∈Gh (Γj )
1≤h≤k
Gh (Γj ) ∩ Gh′ (Γj ) = ∅,
X
1 ≤ i ≤ m.
j∈Pi
IV. S OLUTION With the optimization problem(s) defined, we now present the methods used to solve MIN. A. Link Bandwidth Provisioning Recall that in our formulation the required bandwidth Cj of link j depends on the local priority assignment Γj , the shaping delays Di of flows i ∈ Fj , and the worst-case local scheduling deadlines Thj of each priority class h. We first show how to compute Cj given these variables.
7 Under a fluid model, lower priority classes are transparent.
3
Although the number of possible orderings grows combinatorially with the number of flows, the search space can be explored using standard randomized search heuristics. For each ordering encountered during the search, the corresponding NLP is solved and the resulting bandwidth requirement recorded. The best solution among the explored orderings is then retained. In principle, this procedure can recover the exact optimal solution of MINF IF O if all orderings are examined. In practice, however, computational complexity necessitates limiting the number of orderings explored. This complexity motivates a simple heuristic introduced as Full Shaping (FS) in [20]. Under FS, each flow i is assigned the maximum feasible shaping delay, bi b . (8) Di = di = min di , ri
bits 𝑆"# 𝑡
𝐶# ∗
𝜎! 𝑡 𝜎% 𝑡 − 𝑇"# 𝜎" 𝑡 − 𝑇"#
time
𝑇"#
Fig. 2: Minimal service function and required link bandwidth.
The intuition for considering FS is that a FIFO scheduler treats all flows equally irrespective of their delay requirements. By allocating the maximum possible delay budget to shaping, FS pushes flows toward a common minimal in-network delay8 , which reduces delay heterogeneity in addition to making flows smoother. Also of note is that the required bandwidth Cj∗ on FIFO link j under FS, is readily seen to be simply of the form X Cj∗ = Ri , (9)
in S2j (t) acknowledges that class 2 can tolerate a delay of T2j , while the discontinuity it experiences at that point accounts for the amount of service that has been provided to class 1 by that time. After t = T2j , S2j (t) tracks the aggregate arrival curve of class 2 traffic σ2 (t−T2j )+σ3 (t−T2j ) with the added contribution of residual arrivals from class 1 (r1 t in this case). Repeating a similar reasoning across priority classes enables us to determine the minimum link bandwidth needed to ensure that the delay bounds of all priority classes are met. We also note that determining the minimum link bandwidth for the highest priority class or under FIFO scheduling is considerably simpler. In such a setting, there is no higherpriority to account for, and the minimal service function depends solely on the aggregate traffic of the class itself.
i∈Fj
Fj is the set of link j flows and Ri the shaping rate of flow i. 2) The Static Priority Case: As indicated by Eq. (3), solving MINSP requires jointly determining the priority assignment Γ and allocating the delay budget di of each flow i between its shaping delay Di and per-hop scheduling delays Thj . The inclusion of Γ significantly enlarges the combinatorial search space, rendering exact approaches based on solving Nonlinear Programs (NLPs) impractical. Although an exact NLP-based solution is no longer feasible, [20, Section V] suggested a progressive refinement heuristic that, in most cases, closely approximated the results of the NLP-based solution. Motivated by this observation, we adopt a similar heuristic, which we refer to as Greedy Reprofiling. As in [20], Greedy Reprofiling operates in two phases. For each flow i, the exploration phase generates candidate allocations of its delay budget di across reprofiling delay and local link deadlines. The adjustment phase iteratively refines these allocations by updating local scheduling deadlines across links, and consequently the flow’s reprofiling delay, towards reducing the total bandwidth. To facilitate this process, we allow independent initial per-flow local deadlines Teij (the delay permissible for flow i at link j). The corresponding priority assignment Γj and class-level deadlines Thj are then finalized in the adjustment phase. The general structure of Greedy Reprofiling and in particular its exploration phase mimics [20]. As [20], exploration is based on a global reprofiling ratio γ ∈ [0, 1], with the shaping delay of flow i, 1 ≤ i ≤ m set to Di = γ dbi , for all i, where dbi is defined in Eq. (8). The remaining delay budget, di − Di , is then evenly distributed across hops on the flow’s path Pi
B. Bandwidth Minimization Algorithm With link bandwidths computable once given flows shaping delays (and, therefore, 2SRCs), local deadlines for priority classes on each link, and how flows map to priority classes, the remaining challenge to solve MIN is to determine those quantities in a manner that minimizes the total network bandwidth. We next introduce the algorithms we developed for that purpose, beginning with the simpler FIFO case. 1) The FIFO Case: As in [20, Section IV.B], solving MINF IF O can be formulated as a collection of Non-Linear Programs (NLPs). This is achieved by expressing the worstcase link scheduling delay Tj in terms of the flows’ peak-rate shapers (determined by the shaping delays Di ) and the link bandwidth Cj through Eq. (6). Doing so requires a closedform characterization of Eq. (6), which can be obtained once the ordering (not the values) of the shaping delays Di is fixed. Following the approach of [20], we exploit the fact that the aggregate arrival curve Hj is piecewise-linear, concave, with segments of decreasing slopes, where segment boundaries are determined by the shaping delays Di . We can enumerate all possible orderings of the Di ’s, and for each derive a closedform expression of Eq. (6). The expressions can then be used to formulate a corresponding set of NLPs. As the derivation closely parallels that of [20], we relegate technical details to Appendix C-A.
8 Under a fluid model, FS commonly results in an in-network delay T
4
j = 0.
to form an initial allocation that is subsequently refined in the adjustment phase. Similarly, Greedy Reprofiling’s exploration proceeds by searching over γ ∈ [0, 1] (with progressive refinement) and invokes the adjustment phase (see next) for each value of γ. The process end with the γ value that yields the minimum total bandwidth after adjustment. We refer interested readers to [20, Section V.B] for details.
bits
bits
𝑆"# 𝑡
𝑆"# 𝑡 𝑠̃ %"# 𝐶# ∗
𝑠̃ &"#
𝐶# ∗
𝜎! 𝑡
𝚫 𝟐𝒋
𝜎% 𝑡 − 𝑇"#
𝜎" 𝑡 − 𝑇"#
𝜎" 𝑡 − 𝑇"#
time
time
𝑇"#
' 𝑇"#
Algorithm 1 Adjustment
(a) flow slack at inflection points
Input: flow profiles r = (r1 , r2 , . . . , rm ), b = (b1 , b2 , . . . , bm ), d = (d1 , d2 , . . . , dm ) path matrix P = (P1 , P2 , . . . , Pm ) initial reprofiling delays D = (D1 , D2 , . . . , Dm ) e = {Teij : ∀1 ≤ i ≤ m, j ∈ Pi } initial local deadlines T improvement threshold ϵ Output: total bandwidth C∗ after adjustment 1: initialize C = ∞, C′ = ∞, C∗ = ∞ S 2: sort links in decreasing order of | i∈Fj Pi | 3: while (C′ − C)/C′ > ϵ do 4: for j = 1 to n do 5: perform 1-d k-means clustering on Teij , ∀j ∈ Fj to determine the local P priority assignment Γj 6: initialize Cj∗ = i∈Fj ri 7: for h = 1 to k do 8: Thj = mini∈Gh (Γj ) (Teij ) 9: Di = min(Teij + Di − Thj , bi /ri ), ∀i ∈ Gh (Γj ) ∗ 10: compute Chj according to Eq. (7) ∗ ∗ 11: Cj = max(Cj∗ , Chj ) ∗ 12: reduce Thj to Thj ∗ 13: Di = min(Teij + Di − Thj , bi /ri ), ∀i ∈ Gh (Γj ) ∗ 14: Teij = Thj , ∀i ∈ Gh (Γj ) 15: end for 16: end for 17: update Cj∗ , ∀1 ≤ j ≤ n according to Eq. (6) P e 18: Teij = Teij + (dP i − Di − j∈Pi Tij )/ |Pi | ′ ∗ 19: C = C, C = 1≤j≤n Cj 20: C∗ = min(C, C∗ ) 21: end while 22: return C∗
𝜎! 𝑡
𝜎% 𝑡 − 𝑇"#
( 𝑇"#
𝑇"#
(b) decrease T2j by ∆2j
Fig. 3: Greedy Reprofiling adjustment. local deadlines Teij , i.e., Teij ≤ Tei′ j for i ≤ i′ . Then there exists a priority assignment Γ∗j that minimizes the required link bandwidth Cj while satisfying all local deadlines, such that a flow i is assigned a strictly higher priority than flow i′ only if Teij < Tei′ j . In other words, a flow with a larger deadline should never be assigned to a strictly higher priority class than a flow with a smaller deadline. The result parallels [18, Proposition 4], extending it from token-bucket arrival curves to 2SRCs. The proof is in Appendix B-B, with the next lemma a direct consequence of the proposition. Lemma 3: There exists an optimal priority assignment Γ∗j and a sequence of k + 1 non-decreasing local boundaries ′ ′ {Ťhj }k+1 h=1 , with Ťhj ≤ Ťh j for all 1 ≤ h < h ≤ k + 1 such that
Ťhj ≤ Teij ≤ Ťh+1,j ,
∀ i ∈ Gh (Γ∗j ).
(10)
The lemma implies that determining an optimal priority assignment Γ∗j is equivalent to selecting the k + 1 boundary values {Ťhj } (the first and last boundaries can be readily dropped). In step 1 of the adjustment phase, we perform such a selection using a one-dimensional k-means clustering9 over the initial local deadlines at hop j, i.e., {Teij : i ∈ Fj } (line 5 of Algorithm 1). The resulting cluster boundaries are used as the Ťhj ’s to define an assignment Γ∗j , where the set of flows assigned to priority class h are selected based on Eq. (10). Intuitively, the approach seeks to group flows with similar local deadlines into the same priority class. As shown in line 8 of Algorithm 1, the deadline Thj assigned to priority class h on link j is then initially set to the smallest local deadline of the flows assigned to that class10 . The next step proceeds to adjust (reduce) Thj without increasing the required link bandwidth. The motivation is that reducing Thj frees-up delay that can then be allocated to shaping, i.e., to make the flows smoother, which can benefit other links. b) Adjusting the local deadline allocation: The first step in determining if and by how much it is possible to reduce Thj ∗ involves computing the bandwidth11 Chj required by class h using Eq. (7) (line 10), and updating the overall link bandwidth Cj∗ accordingly (line 11). As shown in [20] and formalized in ∗ Proposition 1 of [18], Chj is attained at one of the inflection ′ points {Teihj }, where the slope of the minimal service function
The adjustment phase involves key aspects specific to static-priority scheduling and is detailed next. Starting from the initial deadline allocations produced by the exploration phase, the algorithm iteratively processes each link j in two steps as described in Algorithm 1: (1) determining the local priority assignment Γj , and (2) adjusting local deadlines by increasing shaping delays. We detail these two steps next. As the description is notation intensive, readers may wish to refer to Appendix A for a glossary of notation. a) Determining the local priority assignment: We start by establishing a key structural property satisfied by an optimal solution for Γj , the assignment of flows to priority classes. Proposition 2: Consider a hop j serving a set of flows Fj and employing a static-priority scheduler with k priority classes indexed in decreasing order of priority from 1 to k (with priority 1 being the highest). Suppose the flows are 2SRC-shaped and indexed in non-decreasing order of their
9 We validate this choice in Appendix D-A. 10 Note that by construction, i.e., Eq. (10), we must have T hj ≥ Ťhj . 11 Recall the discussion of Fig. 2 regarding this computation.
5
of lower-priority classes h′ > h at link j, and the required bandwidth at other links traversed by the class h flows. Since the minimal service function Shj depends on the 2SRC shaping profiles of higher-priority flows, the adjustment is performed in decreasing order of priority (starting from class 1, line 7). This ordering ensures that, when processing class h, the impact of higher-priority traffic has already been accounted for. However, it also implies that the link bandwidth Cj available to class h reflects only the updates from higherpriority classes processed thus far (line 11). Consistent with [20], links are processed in decreasing order S of | i∈Fj Pi | (line 2), prioritizing those whose flows traverse the largest number of links and thus have the greatest impact on the network-wide bandwidth. After all links have been traversed, flows’ shaping profiles may have changed (made smoother). Some flows may, therefore, now be fully shaped to their token rates ri , possibly leaving a portion of their endto-end delay budgets unused at some hops (cf. line 9 and 13). This creates opportunities for additional bandwidth reduction. To exploit this, the unused delay budget is redistributed by evenly splitting it across the hops of each flow (line 18), and the adjustment phase is repeated. Since this redistribution modifies the local deadlines Teij , the priority assignments must be recomputed (line 5), and the total bandwidth C is not guaranteed to decrease monotonically across iterations. We therefore track the minimum bandwidth C∗ observed so far (line 20), and terminate the algorithm when the improvement between successive iterations falls below a threshold ϵ (line 3), which is set to 0.1% in all experiments.
Shj decreases. Recalling that Gh (Γj ) denotes the subset of flows mapped to priority class h under priority assignment Γj on link j, these inflection points arise from three sources: ′ (a) The first inflection point Te0hj = Thj that coincides with the deadline Thj for class h, and that accounts for the aggregate service that higher-priority flows must have received by time Thj when priority class h starts receiving service. (b) A rate change for a flow i in class h (i ∈ Gh (Γj )), yielding ′ = Thj + Di . Teihj (c) A rate change from a flow i in a higher-priority class h′ < h with shaping delay Di exceeding Thj (i ∈ Gh′ (Γj ), Di > ′ Thj ), yielding Teihj = Di . ′ Following [20], the slack at an inflection point Teihj is the excess service provided under the provisioned bandwidth Cj∗ : ′ ′ seihj = Cj∗ Teihj − Shj (Teihj ).
(11)
The slack quantifies how much the current bandwidth exceeds the minimum service function at that point. Note that the use ∗ of Cj∗ instead of Chj allows accounting for the bandwidth provisioned across all priority classes, and not just class h. Leveraging the possible presence of slack to better utilize Cj∗ , the bandwidth provisioned at link j, is the focus of the second step of the adjustment phase illustrated in Fig. 3. Specifically, the second step of the adjustment phase decreases the local scheduling deadline Thj without increasing Cj∗ . The resulting increase in the available delay budget is then redistributed for use in shaping, i.e., by increasing the shaping delays of all flows in Gh (Γj ) without changing their inflection ′ points Teihj This in turn is used to produce “smoother” 2SRCs, thereby reducing bandwidth requirements on other links. The adjustment process is illustrated in Fig. 3b for priority class 2 that includes flows 2 and 3, with Fig. 3a showing nonzero slacks at the first inflection point (s2j ) and at the second inflection point (e s32j contributed by flow 3 from priority class 2). The presence of slack means that the minimal service curve Shj can be increased without increasing Cj∗ . The increases in Shj come from seeking to decrease Thj and come from two effects: (i) the 2SRC shaping profiles of flows in Gh (Γj ) increase with their shaping delays as transmissions start earlier, and (ii) more higher-priority traffic is accounted for within the service window. Since Shj increases monotonically as Thj decreases, this process continues until ∗ Thj reaches a critical value Thj beyond which the provisioned ∗ bandwidth Cj is no longer sufficient to support Shj (line 12). At this point, one of the following conditions must occur: ′ (a) The slack seihj at the inflection point Teihj of some flow i 12 is depleted . ′ (b) The slack se0hj at Te0hj (i.e., at Thj ) is depleted. In case (a), the limiting condition can be identified by examin′ ing the slacks at the stationary inflection points Teihj (marked by •). In case (b), Thj reaches the intersection point between the service curve Cj∗ t and the aggregate higher-priority traffic, + denoted by Thj (marked by •). This adjustment smooths the 2SRC arrival curves of flows in class h. This can reduce both the bandwidth requirement Ch∗′ j
V. E VALUATION A. Evaluation Setup Following the methodology of [20], we evaluate the performance of our proposed algorithms for solving MIN across three network topologies. First, Orion CEV [25] represents an in-vehicle network typical of automotive applications. Second, US-Topo (Fig. 18 of [20]) models a wide-area network interconnecting geographically distributed sites. Third, the parking lot topology (shown in Fig. 4) is a feed-forward synthetic network consisting of both main-path and cross traffic. The Orion CEV topology captures a canonical TimeSensitive Networking (TSN) scenario, while US-Topo represents Deterministic Networking use cases in cloud infrastructures. These two topologies capture expected deployment settings where the work may be applicable. In contrast, the parking lot topology provides a controlled environment for systematic exploration by varying key structural parameters such as the number of flows and path lengths. Link 1
Link n m main flows
m/2 cross flows enter at every hop
Fig. 4: Parking lot topology.
12 This corresponds to flow 3 in Fig. 3b.
6
1) Traffic Models: In Orion CEV, we adopt flow profiles corresponding to standard TSN traffic classes [26]: ControlData Traffic (CDT), class A, and class B, with delay bounds of 0.1, 2, and 50 ms, respectively. US-Topo uses inter-datacenter traffic characteristics from [27] to model three application classes: Web, Cache read/replacement, and Hadoop, with delay bounds of 10, 50, and 200 ms, respectively. The parking lot topology relies on synthetic traffic to facilitate exploring a broad parameter space. Flow rates and burst sizes are independently sampled from uniform distributions over [1, 100] Mb/s and [1, 100] Mb, respectively, with flows randomly assigned to one of four delay classes: 10, 25, 50, 100 ms. 2) Baselines: We compare our algorithm against two baseline strategies: No Shaping (NS) and Full Shaping (FS). Both assume that interleaved shaping is enforced at every hop, and differ only in the shaping profiles used. Under NS, each flow retains its original token-bucket profile (ri , bi ), and, therefore, experiences zero shaping delay. In contrast, FS maximizes shaping by setting Di to the maximum feasible value dbi , which maximizes shaping delay and minimizes the remaining in-network delay budget. Realizing each baseline differs across schedulers. Static-priority differentiates among flows based on their local deadline. Under both NS and FS, any remaining (after shaping) delay budget is evenly distributed across the hops a flow traverses13 . Priority assignments are then determined via k-means clustering at each hop with flows with tighter local deadlines assigned to higher priority classes. FIFO does not differentiate between flows that are all assigned to the same queue. Under FS, as all flows are fully shaped, there is little to no remaining (network) delay heterogeneity across flows, with most sharing a deadline of 0 (recall our fluid model assumption). As per Eq. (9), the required link bandwidth is set to the sum of the flows’ shaping rates. Under NS, we instead apply an NLP-based approach to optimally distribute the flows’ full delay budget across hops towards minimizing the required bandwidth14 . 3) Evaluation Scope: It proceeds along three dimensions:
of the benefits of more sophisticated schedulers, and the extent to which shaping can mitigate them. It also provides insight into how these benefits are affected by network topology and, for static priority, the number of priority classes. B. Bandwidth Minimization under FIFO We begin by evaluating the effectiveness of shaping for bandwidth minimization in FIFO networks. As mentioned earlier, we anticipate that FIFO’s inability to differentiate between flows will result in Full Shaping (FS) being close to the optimal solution of MINF IF O . To validate this observation, we compare the bandwidth achieved by FS with that obtained with an exact NLP-based solution. The combinatorial nature of the NLP-based solution results in a high computational cost. We, therefore, restrict our comparison to instances with 50 flows on the Orion CEV and US-Topo networks. For each, we randomly sample flow profiles and source–destination pairs, and repeat the experiment 1000 times for statistical significance. Given the expected “optimality” of the NLP-based approach, we use it as a baseline and report the bandwidth of FS relative to it. TABLE I: Network bandwidth requirement of FS relative to the NLP-based solution Average Bandwidth
95% Confidence Interval
Orion CEV
99.97%
[99.93%, 100.02%]
US-Topo
100.03%
[100.02%, 100.04%]
The results are in Table I, It reports average bandwidth and 95% confidence intervals. FS closely matches the NLP-based solution for both topologies, and even slightly outperforms it in Orion CEV15 . This is in contrast with observations from [20] for SCED, where optimal reprofiling often differed significantly from FS. This is because SCED can better leverage the residual scheduling flexibility these solutions preserve. In contrast, FIFO has no such ability. Allocating as much as possible of the delay budget to making flows more homogeneous (and smoother), as FS does, is then advantageous. Since FS provides a near-optimal solution for MINF IF O , we use it in the remainder of FIFO’s evaluation. Next we compare FS against No Shaping (NS). Fig. 5 reports the relative bandwidth reduction of FS over NS for both Orion CEV and US-Topo as a function of the number of flows. In both networks, the benefits of FS are substantial (over 90% in both) and eventually stabilize as the number of flows increase. This is because more flows means more homogeneous traffic mixes, which diminishes the relative impact of individual flow shaping decisions. FS’ improvements stem from the fact that it spreads bursts in time, reducing the amount of traffic simultaneously competing for bandwidth. In contrast, NS allows large bursts that may combine at any hop, therefore, requiring considerably more bandwidth on every link in spite of larger local deadlines.
(a) Bandwidth Minimization under FIFO. We begin with FIFO networks, and first validate the statement that, because of FIFO’s lack of flow differentiation, FS closely approximates the exact solution of MINF IF O . We then quantify the bandwidth reduction enabled by shaping relative to the NS baseline. (b) Bandwidth Minimization under Static Priority. Next, we investigate static-priority networks with shaping realized through Greedy Reprofiling. We first confirm the effectiveness of k-means clustering for priority assignment, before evaluating the bandwidth reduction achieved by Greedy Reprofiling over NS and FS. Finally, we explore when Greedy Reprofiling outperforms FS and analyze the structural characteristics of its shaping decisions across priority classes. (c) Scheduler Comparison. Finally, leveraging results from [20], we compare FIFO, static priority, and SCED schedulers. The comparison offers a quantitative assessment 13 Even under FS, flows with large delay bounds can only be shaped down to their token rates ri , leaving a residual in-network delay budget. 14 The NLPs are solely for deadline allocation absent any shaping.
15 This is due to the use of randomized heuristics for exploring flow orderings and the possibility of the NLP solver converging to local optima.
7
Relative Improvement (FS over NS)
97.0% 96.0% 95.0% 94.0% 93.0% 92.0%
to priority classes; a step specific to static priority schedulers. Appendix D-A compares k-means to several alternative assignment strategies for different numbers of priority classes, with k-means consistently performing the best. Having established the soundness of the priority assignment step used in Greedy Reprofiling, we evaluate next its bandwidth reduction capability relative to the two baselines, FS and NS. We begin with the Orion CEV topology, with a number of priority classes k = 8 commonly available in practice17 . Fig. 7 shows bandwidth reductions from Greedy Reprofiling compared to FS and NS as a function of the number of flows. As with FIFO, FS closely approximates the solution found by Greedy Reprofiling, with less than a 0.2% difference across all configurations, and diminishing with the number of flows. This gap is significantly smaller than the ∼ 16% improvements observed under SCED (Fig. 12a of [20]). Similarly, Greedy Reprofiling (and FS) achieves substantial gains over NS, reducing bandwidth by up to 84%. This exceeds the ∼ 73% gain observed under SCED (Fig. 12b of [20]), but remains below the ∼ 98% improvement under FIFO (cf. Fig. 5a). This parallels the schedulers’ progressively increasing flow differentiation capabilities. More powerful schedulers are less dependent on the proactive actions of shaping.
90.0% 88.0% 86.0% 84.0% 82.0% 0
400 800 1200 1600 2000 2400 2800 3200
Expected Number of Flows
400
(a) Orion CEV
800 1200 1600 2000 2400 2800
Expected Number of Flows
(b) US-Topo
Fig. 5: Bandwidth improvement of FS over NS under FIFO.
Finally, we evaluate the impact of network scale using the parking lot topology, varying the number of links n and mainpath flows m. For each (m, n) configuration, we generate 1000 random instances. The results are in Fig. 6 in the form of a heatmap that reports both average bandwidth reductions and 95% confidence intervals (as vertically aligned markers within each cell16 ). FS again consistently outperforms NS across all configurations. Moreover, bandwidth reduction increases with path length, as the benefits of smoother traffic accrue over more hops. This aligns with similar observations in [20]. 95.0% 90.0%
8
85.0%
6
Relative Improvement (Greedy over FS)
Number of Links n
10
80.0%
4
75.0%
2
70.0%
1
2
3
4
5
6
Log2 Flow Parameter m
7
Fig. 6: Bandwidth improvement of FS over NS under FIFO schedulers on the parking lot topology.
4.00% 3.50% 3.00% 2.50% 2.00% 1.50% 1.00% 0.50% 0.00%
45.50%
Relative Improvement (Greedy over NS)
Relative Improvement (FS over NS)
98.0%
0
800 1600 2400 3200 4000 4800 5600 6400 7200
Expected Number of Flows
(a) over FS
45.00% 44.50% 44.00% 43.50% 43.00% 0 800 1600 2400 3200 4000 4800 5600 6400 7200
Expected Number of Flows
(b) over NS
Fig. 8: Greedy Reprofiling’s bandwidth improvement on USTopo (with 8 priority classes). C. Bandwidth Minimization under Static Priority 84.0%
Relative Improvement (Greedy over NS)
Relative Improvement (Greedy over FS)
0.25%
We next evaluate Greedy Reprofiling on US-Topo, with results in Fig. 8 that are largely consistent with those of Orion CEV. Greedy Reprofiling achieves an improvement of about 2% over FS, again smaller than the ∼ 8% gain under SCED (Fig. 20a of [20]), and an improvement of ∼ 46% over NS, similar to that of SCED (also ∼ 46% from Fig. 20b of [20]), but much less than the ∼ 90% under FIFO (cf. Fig. 5b). While the delay targets of flows used with Orion CEV and US-Topo are derived from realistic application traces, it is instructive to examine how the benefit of shaping scales with delay requirements. To this end, we introduce a scaling factor ω and uniformly scale the delay bounds of all flows. Fig. 9 reports the bandwidth improvement of Greedy Reprofiling over FS as a function of ω for both topologies. We observe that the improvement peaks at around 4% for both Orion CEV and US-Topo, although for different values of ω. Consistent with intuition, all improvements disappear for sufficiently large or small deadlines. When deadlines are large, all flows can be fully shaped to their token rates, making FS optimal. Conversely, when deadlines are very tight, per-hop
0.20% 0.15% 0.10% 0.05% 0.00% 400 800 1200 1600 2000 2400 2800 3200
Expected Number of Flows
(a) over FS
82.0% 80.0% 78.0% 76.0% 74.0% 400 800 1200 1600 2000 2400 2800 3200
Expected Number of Flows
(b) over NS
Fig. 7: Greedy Reprofiling’s bandwidth improvement on Orion CEV (with 8 priority classes). We first evaluate the performance of Greedy Reprofiling (rather than FS) for static-priority scheduling. Recall that Greedy Reprofiling parallels the structure of a similar solution from [20]. In particular, it shares its exploration phase and deadline adjustment mechanism, whose effectiveness were already established in [20, Appendix B.G]. As a result, we begin our evaluation by assessing the efficacy of our proposed k-means clustering algorithm for mapping flows (deadlines)
17 IEEE 802.1Q and TSN standards [28] define a 3-bit Priority Code Point (PCP) field, supporting 23 = 8 priority classes.
16 The confidence intervals are small and the markers hardly visible.
8
2.0% 1.0% 0.0%
5
4
3
2
1
Log10
0
1
2
3
(b) US-Topo (3000 flows)
Number of Links n
20.0%
6
15.0%
4
10.0% 5.0%
2 1
2
3
4
5
6
Log2 Flow Parameter m
7
(a) over FS
0.0%
Number of Links n
30.0%
10
70.0%
8
60.0%
6
50.0%
4
40.0%
1
2
3
4
5
6
Log2 Flow Parameter m
4
6
8
10
12
14
16
Number of Priority Classes
18
80% 60% 40% 20% 0%
20
(a) Orion CEV (3100 flows)
SCED static-priority 2
4
6
8
10
12
14
16
Number of Priority Classes
18
20
(b) US-Topo (3000 flows)
Fig. 11: SCED and static priority schedulers’ bandwidth improvement (with NS) compared to FIFO (with NS) as a function of the number of priority classes.
SCED and static priority both significantly outperform FIFO, by up to 90% or 80% depending on the topology. Of interest is the fact that, as the number of priority classes increases, the performance of static priority becomes indistinguishable from that of SCED. This is an artifact of SCED being limited to use the flows’ original token bucket profiles as their service curves. This results in SCED behaving like EDF, which, at least for the worst-case scenarios we consider, can be well approximated using a (sufficient) number of fixed priority classes.
30.0%
2
SCED static-priority
50% 2
deadlines all approach 0, leaving no room for differentiation, with Greedy Reprofiling again converging to FS.
8
60%
3.0 2.5 2.0 1.5 1.0 0.5 0.0 0.5 1.0 1.5 2.0
Fig. 9: Bandwidth improvement of Greedy Reprofiling over FS as a function of deadline scaling ω (with 8 priority classes).
25.0%
70%
Log10
(a) Orion CEV (3100 flows)
10
80%
Relative Improvement (over FIFO)
3.0%
90%
7
(b) over NS
Relative Improvement (over FIFO)
Fig. 10: Greedy Reprofiling’s bandwidth improvement on parking-lot topology (with 8 priority classes). Finally, we examine how the bandwidth improvement of Greedy Reprofiling scales with network size by evaluating it against FS and NS on the parking lot topology over a range of (m, n) configurations (Fig. 10). As expected (Fig. 10a), as path length (n) increases, Greedy Reprofiling converges to FS. This partially explains why, in multi-hop topologies such as Orion CEV and US-Topo, Greedy Reprofiling yields only marginal gains over FS. When flow paths are short (e.g., n = 2), the improvement over FS can, however, reach up to 30% when the number of flows is large (the greater diversity in flows’ deadlines enables a more effective use of staticpriority’s scheduling flexibility). Appendix D-B explores this aspect in greater details. The comparison to NS (Fig. 10b) is also intuitive, the benefits of Greedy Reprofiling, as those of FS, increase with path length.
1.55% 1.50% 1.45% 1.40% 1.35%
SCED static-priority
1.30% 2
4
6
8
10
12
14
16
Number of Priority Classes
18
Relative Improvement (over FIFO)
4.0%
4.00% 3.50% 3.00% 2.50% 2.00% 1.50% 1.00% 0.50% 0.00%
Relative Improvement (over FIFO)
Relative Improvement (Greedy over FS)
Relative Improvement (Greedy over FS)
5.0%
15.90% 15.88% 15.86% 15.84% 15.82% 15.80% 15.78% 15.76% 15.74%
20
(a) Orion CEV (3100 flows)
SCED static-priority 2
4
6
8
10 12 14 16 18 20
Number of Priority Classes
(b) US-Topo (3000 flows)
Fig. 12: SCED and static priority schedulers’ bandwidth improvement (with FS) compared to FIFO (with FS) as a function of the number of priority classes. Fig. 12 reports a similar comparison as Fig. 11, but now under FS. By construction, FS devotes as much of a flow’s delay budget to making it smoother, and while this often results in flows with no residual network deadline18 , flows with large initial deadlines may retain an unused delay budget (they cannot be reshaped below their token rate). This offers schedulers such as SCED and static priority some, albeit limited opportunities to leverage those residual delays to further reduce bandwidth. The limited scope of those opportunities is also why SCED and static priority behave similarly. As we shall see next, this does not necessarily hold when reprofiling decisions yield a richer set of service curves for SCED to leverage, i.e., as is the case when Greedy Reprofiling is used.
D. Scheduler Comparison Since the role of shaping (reprofiling) has been explored for SCED [20], static-priority, and FIFO schedulers, it is natural to examine how that role varies across schedulers. We begin by comparing the three schedulers under NS and FS, with FIFO serving as the baseline. The comparison under NS (flow profiles remain unchanged) helps gauge the benefits afforded by schedulers of increasing complexity. For static priority, results are reported while varying the number of priority classes (from 2 to 20). Conversely, the comparison under FS offers insight into how a common shaping strategy can narrow the performance gap between the three schedulers. The comparisons are carried out on Orion CEV and US-Topo and, for each, involve a combination of 3000 flows. Results of the comparison under NS are in Fig. 11 that illustrates the advantages of greater scheduling flexibility.
This is explored in Fig. 13 that compares the three schedulers, but now using Greedy Reprofiling for SCED and static-priority, and FS for FIFO (FS is “optimal” for FIFO). Comparing Figs. 13 and 12 illustrates the benefits of Greedy Reprofiling over FS, primarily for SCED, as known from [20], and to a lesser extent for static priority, consistent with Fig. 9. 18 Recall our assumption of a fluid model.
9
SCED static-priority
2
4
6
8
10
12
14
16
Number of Priority Classes
18
20
(a) Orion CEV (3100 flows)
Relative Improvement (over FIFO)
Relative Improvement (over FIFO)
16.0% 14.0% 12.0% 10.0% 8.0% 6.0% 4.0% 2.0%
shaping (CBS) and asynchronous traffic shaping (ATS) using analytical models or simulation-based approaches [39], [40]. These works typically focus on computing feasible or efficient configurations under a fixed scheduling model. In contrast, we consider multiple schedulers and investigate the role of proactively adjusting flow shaping profiles to minimize the bandwidth required to meet delay bounds. Our analysis also highlights how scheduler’s flexibility influences the effectiveness of shaping in reducing bandwidth.
22.0% 21.0% 20.0%
SCED static-priority
19.0% 18.0% 17.0% 2
4
6
8
10
12
14
16
Number of Priority Classes
18
20
(b) US-Topo (3000 flows)
Fig. 13: SCED and static priority schedulers’ bandwidth improvement (with Greedy Reprofiling) compared to FIFO (with FS) as a function of the number of priority classes.
C. Bandwidth Optimization under QoS Constraints Bandwidth optimization under QoS constraints has been studied in several contexts beyond TSN/DetNet. In deterministic settings, network calculus and effective bandwidth theory have been used to derive the minimum service rates required to meet delay guarantees for regulated traffic. Related formulations arise in admission control and resource allocation, where the goal is to determine whether a set of flows can be supported under given bandwidth constraints [41], or to allocate resources efficiently while satisfying QoS requirements [42], [43]. In parallel, traffic engineering and network utility optimization frameworks address bandwidth allocation across paths and flows, often optimizing utilization, congestion, or throughput under capacity constraints [44]–[46]. While these works provide important insights into resourceefficient network design, they typically assume fixed traffic profiles and scheduling models, and focus on determining the minimum resources needed to ensure feasibility. In contrast, our work treats traffic profiles as decision variables and jointly considers how to adjust them under different scheduling disciplines. This allows us to study the trade-off between reducing traffic burstiness while tightening network delays across schedulers with varying levels of flexibility and, therefore, ability to leverage differences in-network delays.
Fig. 13 reveals another interesting aspect, namely, under Greedy Reprofiling, unlike FS, a performance gap persists19 between SCED and static priority, irrespective of how many priority classes the latter is allowed. This is in part because Greedy Reprofiling allows richer flow profiles than FS (distinct peak and long-term rates). Under SCED, the joint optimization of making flows smoother while preserving some scheduling flexibility can leverage those richer profiles. Finally, Fig. 13b also illustrates that increasing the number of priority classes does not always benefit the performance of static-priority scheduling. The figure shows a drop in performance as more priority classes are introduced. This is counterintuitive and an artifact of the k-means algorithm on which we rely. It seeks to utilize all classes without considering whether merging classes might yield better performance. As a result, flows with similar local deadlines may be unnecessarily separated, leading to poorer performance20 . VI. R ELATED W ORK A. Recent Advances in TSN/DetNet Systems Recent work on TSN/DetNet has targeted enabling deterministic communication over common network technologies through advances in system design and standardization [10], [13], [29]–[31]. Examples include architectures to integrate TSN with software-defined control and cross-domain networking [32]–[34], as well as prototype implementations that expose practical constraints such as synchronization inaccuracies and hardware-induced delays [31], [35]. The focus is on system-level realizations and the challenges of preserving theoretical guarantees in deployed solutions. In contrast, we explore the fundamental relationship between shaping and scheduling, providing insights that can guide system designs.
D. Priority Assignment and Queue Management Priority assignment has been extensively studied in realtime systems as a means to ensure schedulability under fixedpriority scheduling. Classical approaches include rule-based schemes such as rate-monotonic and deadline-monotonic policies, which assign priorities according to task periods or deadlines and are optimal under specific assumptions [47]. For instance, works targeting hard delay bounds often apply a deadline-monotonic policy and assign a flow with a tighter deadline to a higher priority class [18], [48]. More general settings are addressed by optimal priority assignment algorithms, such as Audsley’s algorithm [49], which iteratively constructs a feasible priority ordering using schedulability tests. When analytical methods become intractable, heuristic and optimization-based approaches, including genetic algorithms and other search techniques, have been proposed to explore the large space of possible priority assignments [50], [51]. Other works perform admission control by assigning incoming flows to pre-configured priority queues with specified service guarantees, with the objective of maximizing link utilization or admission rate [52], [53].
B. Traffic Shaping and Scheduling Optimization A large body of work studies network-wide scheduling and shaping configuration in TSN. Scheduling is often formulated as a global optimization problem, particularly for time-aware shaping (TAS), and solved using ILP, constraint programming, or heuristics [33], [36]–[38]. Complementary efforts focus on configuring traffic shaping mechanisms such as credit-based 19 Additional comparisons investigating the impact of network scale using the parking lot topology are available in Appendix D-C. 20 A simple albeit expensive solution involves running k versions of the clustering algorithm, one for each number of priorities, and try all solutions.
10
These works focus on identifying priority assignments that ensure feasibility or improve schedulability under a fixed system model. In contrast, we consider priority assignment as part of a broader optimization problem, where priorities are determined jointly with traffic shaping to minimize bandwidth. Rather than relying on feasibility-driven or rule-based policies, our approach, while similar to deadline-monotonic policies, adjusts local deadlines and priority assignments towards reducing resource requirements.
[4] Y. Xu and J. Huang, “A survey on time-sensitive networking standards and applications for intelligent driving,” Processes, vol. 11, no. 7, p. 2211, 2023. [5] Z. Satka, M. Ashjaei, H. Fotouhi, M. Daneshtalab, M. Sjödin, and S. Mubeen, “A comprehensive systematic review of integration of time sensitive networking and 5g communication,” Journal of systems architecture, vol. 138, p. 102852, 2023. [6] T. Docquier, Y.-Q. Song, V. Chevrier, L. Pontnau, and A. AhmedNacer, “Performance evaluation methodologies for smart grid substation communication networks: A survey,” Computer Communications, vol. 198, pp. 228–246, 2023. [Online]. Available: https://www.sciencedirect. com/science/article/pii/S0140366422004285 [7] (2026) AWS global network. [Online]. Available: https://aws.amazon. com/about-aws/global-infrastructure/ [8] (2026) Google cloud networking overview. [Online]. Available: https://cloud.google.com/blog/topics/developers-practitioners/ google-cloud-networking-overview [9] (2026, April) Microsoft global network. [Online]. Available: https: //learn.microsoft.com/en-us/azure/networking/microsoft-global-network [10] J. Farkas, L. L. Bello, and C. Gunther, “Time-sensitive networking standards,” IEEE Communications Standards Magazine, vol. 2, no. 2, 2018. [11] G. Parsons, “The rise of time-sensitive networking (TSN) in automobiles, industrial automation, and aviation,” In Compliance - Electronic Design, Testing & Standards, January 2022, https://incompliancemag.com/article/the-rise-of-time-sensitivenetworking-tsn-in-automobiles-industrial-automation-and-aviation/. [12] Y. Seol, D. Hyeon, J. Min, M. Kim, and J. Paek, “Timely survey of timesensitive networking: Past and future directions,” IEEE Access, vol. 9, pp. 142 506–142 527, 2021. [13] T. Zhang, G. Wang, C. Xue, J. Wang, M. Nixon, and S. Han, “Timesensitive networking (tsn) for industrial automation: Current advances and future directions,” ACM Computing Surveys, vol. 57, no. 2, pp. 1–38, 2024. [14] K. Zanbouri, M. Noor-A-Rahim, J. John, C. J. Sreenan, H. V. Poor, and D. Pesch, “A comprehensive survey of wireless time-sensitive networking (tsn): Architecture, technologies, applications, and open issues,” IEEE Communications Surveys & Tutorials, vol. 27, no. 4, pp. 2129–2155, 2024. [15] N. Finn, P. Thubert, B. Varga, and J. Farkas, “Deterministic Networking Architecture,” RFC 8655, October 2019. [Online]. Available: https://www.rfc-editor.org/info/rfc8655 [16] B. Varga, J. Farkas, A. G. Malis, and S. Bryant, “Deterministic Networking (DetNet) Data Plane: IP over IEEE 802.1 Time-Sensitive Networking (TSN),” RFC 9023, Jun. 2021. [Online]. Available: https://www.rfc-editor.org/info/rfc9023 [17] J.-Y. Le Boudec, “A theory of traffic regulators for deterministic networks with application to interleaved regulators,” IEEE/ACM Trans. Netw., vol. 26, no. 6, pp. 2721–2733, 2018. [Online]. Available: https://doi.org/10.1109/TNET.2018.2875191 [18] J. Song, J. Qiu, R. Guerin, and H. Sariowan, “On the benefits of traffic “reprofiling” the single hop case,” IEEE/ACM Transactions on Networking, vol. 32, no. 3, pp. 2511–2524, 2024. [19] H. Sariowan, R. L. Cruz, and G. C. Polyzos, “Sced: A generalized scheduling policy for guaranteeing quality-of-service,” IEEE/ACM transactions on networking, vol. 7, no. 5, pp. 669–684, 2002. [20] J. Qiu, J. Song, R. Guérin, and H. Sariowan, “On the benefits of traffic “reprofiling” the multiple hops case—part i,” IEEE/ACM Transactions on Networking, vol. 32, no. 4, pp. 3421–3436, 2024. [21] J.-Y. Le Boudec and P. Thiran, Network calculus: a theory of deterministic queuing systems for the internet. Springer, 2001. [Online]. Available: https://leboudec.github.io/netcal/ [22] J. Turner, “New directions in communications (or which way to the information age?),” IEEE Communications Magazine, vol. 24, no. 10, pp. 8–15, 1986. [Online]. Available: https://doi.org/10.1109/MCOM. 1986.1092946 [23] L. Georgiadis, R. Guérin, V. Peris, and K. N. Sivarajan, “Efficient network QoS provisioning based on per node traffic shaping,” IEEE/ACM Transactions on Networking, vol. 4, no. 4, 1996. [24] J. Specht and S. Samii, “Urgency-based scheduler for time-sensitive switched Ethernet networks,” in Proc. 28th Euromicro Conf. Real-Time Syst. (ECRTS), July 2016. [25] M. Paulitsch, E. Schmidt, C. Scherrer, and H. Kantz, “Industrial applications,” in Time-Triggered Communication. CRC Press, 2018, pp. 331–388. [26] S. Thangamuthu, N. Concer, P. J. Cuijpers, and J. J. Lukkien, “Analysis of ethernet-switch traffic shapers for in-vehicle networking applications,”
E. End-to-end Deadline Allocations Prior work on delay-constrained networking typically decomposes end-to-end delay into per-hop contributions using analytical models [54], [55], or implicitly determines delay allocation through resource optimization [56], [57]. While some studies reveal structural properties such as delay balancing across hops [58], they do not explicitly treat deadline allocation as a decision variable. In contrast, we seek to optimize the allocation of delay budgets across hops and study its interaction with traffic profiles and scheduling. VII. C ONCLUSION This paper investigates bandwidth minimization in networks with hard end-to-end delay guarantees, focusing on the role of traffic profiles under FIFO and static priority schedulers. The benefits of reprofiling, i.e., adjusting a flow’s traffic profile before it enters the network, had been previously established [20] for service curve schedulers (SCED). This work extends the results to two FIFO and static priority schedulers. As with SCED, we formulate a joint optimization accounting for reprofiling, scheduling, and bandwidth provisioning, and develop efficient solutions for both schedulers. The results offer insights beyond confirming the benefits of reprofiling. Under FIFO, full shaping, i.e., allocating as much of a flow’s delay budget to making it smoother, realizes a near-optimal. This is intuitive as full shaping equalizes residual flows’ delays, minimizing delay differences that FIFO cannot exploit. Full shaping is also effective under static priority, though an efficient greedy heuristic can outperform it, especially in networks with short path lengths. Finally, although reprofiling helps FIFO and static priority narrow their performance gap with SCED, SCED’s greater scheduling flexibility can leverage more sophisticated reprofiling solutions that allow it to continue outperforming the two simpler schedulers. R EFERENCES [1] M. Ashjaei, L. L. Bello, M. Daneshtalab, G. Patti, S. Saponara, and S. Mubeen, “Time-sensitive networking in automotive embedded systems: State of the art and research opportunities,” Journal of Systems Architecture, vol. 117, p. 102137, 2021. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1383762121001028 [2] Avionics Full Duplex Switched Ethernet (AFDX) Network, Airlines Electronic Engineering Committee, Aircraft Data Network Part 7, ARINC Specification 664, Aeronautical Radio, Annapolis, MD, USA, 2002. [3] C. Zunino, A. Valenzano, R. Obermaisser, and S. Petersen, “Factory communications at the dawn of the fourth industrial revolution,” Computer Standards & Interfaces, vol. 71, p. 103433, 2020. [Online]. Available: https://www.sciencedirect.com/science/article/pii/ S0920548919300868
11
in 2015 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 2015, pp. 55–60. [27] A. Roy, H. Zeng, J. Bagga, G. Porter, and A. C. Snoeren, “Inside the social network’s (datacenter) network,” in Proc. ACM SIGCOMM Conference, 2015, pp. 123–137. [Online]. Available: https://doi.org/10.1145/2785956.2787472 [28] C. Xue, T. Zhang, Y. Zhou, M. Nixon, A. Loveless, and S. Han, “Realtime scheduling for 802.1 qbv time-sensitive networking (tsn): A systematic review and experimental study,” arXiv preprint arXiv:2305.16772, 2023. [29] T. Stüber, L. Osswald, S. Lindner, and M. Menth, “A survey of scheduling in time-sensitive networking (TSN),” 2022. [Online]. Available: https://arxiv.org/abs/2211.10954 [30] J. Walrand, “A concise tutorial on traffic shaping and scheduling in time-sensitive networks,” IEEE Communications Surveys & Tutorials, pp. 1–1, May 2023. [31] S. Egger, F. Dürr, B. Varga, M. De Andrade, G. P. Sharma, J. Sachs, J. Harmatos, and J. Gross, “Wireless-aware tsn engineering: Implications for 5g and upcoming 6g networks,” IEEE Network, 2025. [32] M. Guo, G. Shou, Y. Liu, and Y. Hu, “Software-defined time-sensitive networking for cross-domain deterministic transmission,” Electronics, vol. 13, no. 7, p. 1246, 2024. [33] B. Li, Y. Zhu, Q. Liu, and X. Yao, “Development of deterministic communication for in-vehicle networks based on software-defined timesensitive networking,” Machines, vol. 12, no. 11, p. 816, 2024. [34] F. Ihle, M. Flüchter, and M. Menth, “P4-tas: P4-based time-aware shaper for time-sensitive networking,” arXiv preprint arXiv:2511.10249, 2025. [35] M. Eppler, S. Lindner, L. Osswald, T. Stüber, and M. Menth, “Impact of packet loss and timing errors on scheduled periodic traffic with timeaware shaping (tas) in time-sensitive networking (tsn),” arXiv preprint arXiv:2510.05290, 2025. [36] T. Stüber, L. Osswald, S. Lindner, and M. Menth, “A survey of scheduling algorithms for the time-aware shaper in time-sensitive networking (tsn),” Ieee Access, vol. 11, pp. 61 192–61 233, 2023. [37] H. Chahed and A. Kassler, “Tsn network scheduling—challenges and approaches,” Network, vol. 3, no. 4, pp. 585–624, 2023. [38] C. Xue, T. Zhang, Y. Zhou, M. Nixon, A. Loveless, and S. Han, “A survey and experimental study of real-time scheduling methods for 802.1 qbv tsn networks,” ACM Computing Surveys, vol. 58, no. 2, pp. 1–37, 2025. [39] R. Yan, Q. Li, and H. Xiong, “Optimizing traffic management in airborne power line communication networks: A credit-based shaping approach using network calculus,” IEEE Transactions on Network and Service Management, vol. 22, no. 2, pp. 1437–1449, 2025. [40] T. Hirofuchi, A. B. Ahmed, and T. Fukai, “Implementation and evaluation of a time-sensitive networking endpoint for asynchronous traffic shaping,” IEEE Access, 2026. [41] C. Wang, H. Xue, and Z. Huan, “Bpnn-based flow classification and admission control for software defined iiot,” IET Communications, vol. 18, no. 15, pp. 882–896, 2024. [42] E. Hernández and J. Vila, “A new approach to optimize bandwidth reservation for real-time video transmission with deterministic guarantees,” Real-Time Imaging, vol. 9, no. 1, pp. 11–26, 2003. [43] X. Gong, S. A. Vorobyov, and C. Tellambura, “Joint bandwidth and power allocation with admission control in wireless multi-user networks with and without relaying,” IEEE Transactions on Signal Processing, vol. 59, no. 4, pp. 1801–1813, 2011. [44] S. Sahni, N. Rao, S. Ranka, Y. Li, E.-S. Jung, and N. Kamath, “Bandwidth scheduling and path computation algorithms for connectionoriented networks,” in Sixth international conference on networking (ICN’07). IEEE, 2007, pp. 47–47. [45] M. Noormohammadpour and C. S. Raghavendra, “Minimizing flow completion times using adaptive routing over inter-datacenter wide area networks,” in IEEE INFOCOM 2018-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). IEEE, 2018, pp. 1–2. [46] D. Bethanabhotla, G. Caire, and M. J. Neely, “Utility optimal scheduling and admission control for adaptive video streaming in small cell networks,” in 2013 IEEE International Symposium on Information Theory. IEEE, 2013, pp. 1944–1948. [47] R. I. Davis, L. Cucu-Grosjean, M. Bertogna, and A. Burns, “A review of priority assignment in real-time systems,” Journal of systems architecture, vol. 65, pp. 64–82, 2016. [48] T. Zhu, M. A. Kozuch, and M. Harchol-Balter, “Workloadcompactor: Reducing datacenter cost while providing tail latency slo guarantees,” in Proceedings of the 2017 Symposium on Cloud Computing, 2017, pp. 598–610.
[49] N. C. Audsley, “On priority assignment in fixed priority scheduling,” Information Processing Letters, vol. 79, no. 1, pp. 39–44, 2001. [50] J. Lee, S. Y. Shin, S. Nejati, and L. C. Briand, “Optimal priority assignment for real-time systems: a coevolution-based approach,” Empirical Software Engineering, vol. 27, no. 6, p. 142, 2022. [51] N. Kumar, C. Gao, and A. Easwaran, “Optimal fixed priority scheduling in multi-stage multi-resource distributed real-time systems,” in 2024 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 2024, pp. 1–6. [52] M. P. Grosvenor, M. Schwarzkopf, I. Gog, R. N. Watson, A. W. Moore, S. Hand, and J. Crowcroft, “Queues {don’t} matter when you can {JUMP} them!” in 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI 15), 2015, pp. 1–14. [53] A. Van Bemten, N. Ðerić, A. Varasteh, S. Schmid, C. Mas-Machuca, A. Blenk, and W. Kellerer, “Chameleon: predictable latency and high utilization with queue-aware and adaptive source routing,” in Proceedings of the 16th International Conference on emerging Networking EXperiments and Technologies, 2020, pp. 451–465. [54] J. W. Guck, M. Reisslein, and W. Kellerer, “Function split between delay-constrained routing and resource allocation for centrally managed qos in industrial networks,” IEEE Transactions on Industrial Informatics, vol. 12, no. 6, pp. 2050–2061, 2016. [55] R. N. Gore, E. Lisova, J. Åkerberg, and M. Björkman, “Network calculus approach for packet delay variation analysis of multi-hop wired networks,” Applied Sciences, vol. 12, no. 21, p. 11207, 2022. [56] S. Kumar and V. Sharma, “Joint routing, scheduling and power control providing hard deadline in wireless multihop networks,” in 2017 Information Theory and Applications Workshop (ITA). IEEE, 2017, pp. 1–9. [57] N. Petreska, H. Al-Zubaidy, R. Knorr, and J. Gross, “Bound-based power optimization for multi-hop heterogeneous wireless industrial networks under statistical delay constraints,” Computer networks, vol. 148, pp. 262–279, 2019. [58] Q. Du, Y. Huang, P. Ren, and C. Zhang, “Statistical delay control and qos-driven power allocation over two-hop wireless relay links,” in 2011 IEEE Global Telecommunications Conference-GLOBECOM 2011. IEEE, 2011, pp. 1–5.
12
A PPENDIX A S UMMARY OF N OTATION AND ACRONYMS Acronyms Definition 2SRC Two-Slope Reprofiling Curve PBOO Pay Burst Only Once FIFO First In First Out SP Static Priority SCED Service Curve Earliest Deadline first Notation Definition α (token bucket) arrival curve β service curve σ two-slope reprofiling curve (2SRC) delay upper bound for ∆(α, β) arrival curve α under service curve β σi 2SRC of flow i S minimal service function m number of flows in the network n number of links in the network k number of priority classes in the network i flow index j link (hop) index h priority class index r flow long-term rate b flow burst size d flow end-to-end latency target flow maximum reprofiling delay db min(d, b/r) Pi set of links on flow i’s path (route) P flow path matrix Fj set of flows on link j (ri , bi , di ) profile of flow i (r, b, d) vector of flow profiles Γj priority assignment at link j Γ priority assignment for the network t time Ri 2SRC short-term rate of flow i Bi 2SRC burst size of flow i Di shaping delay (same with b/R) of flow i Thj scheduling deadline of priority h at hop j e Tij local deadline of flow i at hop j Thj when i = 0 ′ Thj + Di when i ∈ Gh (Γj ) Teihj Di when i ∈ Gh′ (Γj ), h′ < h ∗ Thj critical value of Thj for adjustment intersection between Cj t and + Thj the aggregate higher-priority traffic deadline boundary for priority assignment Ťhj Cj transmission link bandwidth capacity Cj∗ minimum required bandwidth capacity C total network bandwidth capacity seihj flow i slack for priority h
the propositions and present the proofs with the link-wise subscript j removed. A. Proof of Proposition 1 Proposition 1: Consider a hop equipped with a staticpriority scheduler with k priority classes indexed in decreasing order of priority from 1 to k (priority 1 being the highest), serving the set of flows F . Given a priority assignment Γ and the corresponding minimal service function Sh for each priority class, the hop must provision a bandwidth of at least C ∗ in order to satisfy the deadlines of all classes, where ! X ∗ ∗ C = max ri , Ch , (12) 1≤h≤k
where
i∈F
Sh (t) , t t>Th
Ch∗ = sup
denotes the bandwidth required to serve traffic from priority class h by its deadline Th . To ensure finite worst-case delay for all packets, the available bandwidth C ∗ must be no P smaller than the aggregate long-term token rates, i.e., C ∗ ≥ i∈F ri , which establishes the first part of Eq. (12). We start from the canonical delay bound guarantee from Network Calculus that relates worst-case delay to the link bandwidth at one hop, and then establish its equivalence to Eq. (12). According to Network Calculus [21, Theorem 1.4.2], satisfying the deadline Th of priority class h requires that sup inf {αh (t) ≤ βh (t + τ )} ≤ Th (13) t≥0 τ ≥0 ⇐⇒ sup inf {αh (t − Th ) ≤ βh (t + τ )} ≤ 0 (14) t≥0
τ ≥0
⇐⇒ βh (t) ≥ αh (t − Th ), ∀t ≥ 0.
(15)
where αh and βh denote the arrival and service curves of priority class h, respectively. For 2SRC-shaped flows, we have X αh (t) = Hh (t) = σi (t) (16) i∈Gh (Γ)
where σi (t) is the 2SRC of flow i. Following Network Calculus [21, Proposition 1.3.4], the service curve of a non-preemptive static-priority scheduler is given by X βh (t) = [Ct − Hh′ (t)]+ , (17) 1≤h′ <h
representing the residual bandwidth after serving all higherpriority traffic. We next show that Inequality (15) is equivalent to Ct ≥ Sh (t), ∀t > Th ,
A PPENDIX B P ROOFS
(18)
with Sh (t) being the minimal service function of priority class h, implying that C ≥ supt>Th {Sh (t)/t} is sufficient to meet the deadline of class h, thereby proving Eq. (12).
The propositions introduced to the paper focus on a single hop inside the network. To simplify the notations, we revise 13
bandwidth C while satisfying all local deadlines, such that a flow i is assigned a strictly higher priority than flow i′ only if Tei < Tei′ . We next prove the proposition based on a more generalized packet model that accounts for the packet size of each flow instead of a fluid model. Under a packet model, the minimal service function becomes:
Towards proving βh (t) ≥ αh (t − Th ), ∀t ≥ 0 ⇐⇒ Ct ≥ Sh (t), ∀t > Th , we start with βh (t) ≥ αh (t − Th ), ∀t ≥ 0 ⇒Ct ≥ Sh (t), ∀t > Th ,
Sh (t) = ( 0, t ≤ Th , P max lh (Γ) + 1≤h′ <h HGh′ (Γ) (t) + HGh (Γ) (t − Th ), t > Th ,
Substituting αh and βh from Eq. (16) and (17) into βh (t) ≥ αh (t − Th ), ∀t ≥ 0, we obtain X X [Ct − Hh′ (t)]+ ≥ σi (t − Th ) = Hh (t − Th ). 1≤h′ <h
i∈Gh (Γ) (max)
(19) Let βh′ (t) = Ct −
P
where lh (Γ) represents the maximum packet size among all flows belonging to priority classes strictly lower than h due to non-preemptive scheduling, and
′ 1≤h′ <h Hh (t). We first note that
βh (t) ≥ αh (t − Th ), ∀t ≥ 0 ⇒βh′ (t) ≥ αh (t − Th ), ∀t ≥ Th
HGh (Γ) (t) =
since αh (t) ≥ 0, ∀t ≥ 0. According to the definition of 2SRC, Hh (t − Th ) > 0 for t > Th . Because Inequality (19) holds from our assumption that βh (t) ≥ αh (t − Th ), ∀t ≥ 0, this implies that βh′ (t) > 0 for t > Th . Hence, Inequality (19) directly implies X Ct − Hh′ (t) ≥ Hh (t − Th ), ∀t > Th (20)
σi (t).
i∈Gh (Γ)
denotes the aggregate arrival curves from all the higher priority flows, with Gh (Γ) denoting the subset of flows assigned priority level h under Γ. (max) For a given priority assignment Γ, we denote Teh (Γ) = (min) maxi∈Gh (Γ) Tei and Teh (Γ) = mini∈Gh (Γ) Tei . To meet the deadline of all flows in priority class h, we need the scheduling (min) deadline Th = Teh (Γ). We prove the proposition by induction on the number k of priority classes. Let the induction hypothesis I(k) be formulated as follows:
1≤h′ <h
⇐⇒ Ct ≥ Sh (t), ∀t > Th
X
(21)
according to the definition of Sh (t) given in Eq. (5). Next, we show that Ct ≥ Sh (t), ∀t > Th
I(k): For any set of flows sharing a link, there exists an optimal k-priority assignment Γk such that for all (max) (min) 1 ≤ h < h′ ≤ k, Teh (Γk ) < Teh′ (Γk ).
⇒βh (t) ≥ αh (t − Th ), ∀t ≥ 0, In other words, we assume that Inequality 18 (and therefore Inequality 20) holds, which implies X βh′ (t) = Ct − Hh′ (t) ≥ Hh (t − Th ), ∀t > Th
Base case (k = 2): For k = 2, we show that for any (max) (min) assignment Γ2 , if Te1 (Γ2 ) ≥ Te2 (Γ2 ), then there exists (max) (min) ′ e another assignment Γ2 satisfying T1 (Γ′2 ) < Te2 (Γ′2 ) ∗ ′ ∗ and C (Γ2 ) ≤ C (Γ2 ). According to Proposition 1, the minimum bandwidth required for assignment Γ2 is •
1≤h′ <h
Since Hh (t − Th ) = 0 when t ≤ Th , and [βh′ (t)]+ ≥ 0 for all t 21 , this implies X [Ct − Hh′ (t)]+ ≥ Hh (t − Th ),
C ∗ (Γ2 ) = Pn i=1 ri , (min) l1max (Γ2 )+HG1 (Γ2 ) (t−Te1 (Γ2 )) , sup (min) t t>Te1 (Γ2 ) max (min) HG1 (Γ2 ) (t)+HG2 (Γ2 ) (t−Te2 (Γ2 )) supt>Te(min) (Γ ) t 2
1≤h′ <h
or Ct ≥ Sh (t), ∀t > Th ⇒ βh (t) ≥ αh (t − Th ), ∀t ≥ 0. This establishes the equivalence between Inequalities 15 and 18, and therefore proves Proposition 1.
2
B. Proof of Proposition 2 Proposition 2: Consider a hop employing a static-priority scheduler with k priority classes indexed in decreasing order of priority from 1 to k (with priority 1 being the highest), serving a set of m flows F. Suppose the flows are 2SRCshaped and indexed in non-decreasing order of their local deadlines Tei , i.e., Tei ≤ Tei′ for i ≤ i′ . Then there exists a priority assignment Γ∗ that minimizes the required link
(min) Define G′2 (Γ2 ) = {i ∈ G1 (Γ2 ) | Tei ≥ Te2 (Γ2 )} (the set of flows in G1 (Γ2 ) with deadlines larger than or equal to the smallest deadline of flows in G2 (Γ2 )), and G′1 (Γ2 ) = G1 (Γ2 )\G′2 (Γ2 ) (the set G1 (Γ2 ) from which flows with deadlines larger than or equal to the smallest deadline of flows in G2 (Γ2 ) have been removed). Next, construct Γ′2 by setting G1 (Γ′2 ) = G′1 (Γ2 ) and G2 (Γ′2 ) = G2 (Γ2 ) ∪ G′2 (Γ2 ). (max) (min) (min) This then yields Te1 (Γ′2 ) < Te2 (Γ′2 ) and Tei (Γ′2 ) =
21 By definition, [β ′ (t)]+ = max(0, β ′ (t)), ∀t. h h
14
.
(min) Tei (Γ2 ) for i = 1, 2, so that the required bandwidth under Γ′2 is given by
(max) – Condition 2: C ∗ (Γ′k+1 ) ≤ C ∗ (Γk+1 ) and Teh (Γ′k+1 ) < (min) ′ ′ e Th′ (Γk+1 ), ∀1 ≤ h < h ≤ k + 1.
C ∗ (Γ′2 ) = Pn i=1 ri , max ′ (min) (Γ2 )) l1 (Γ2 )+HG (Γ′ ) (t−Te1 1 2 , sup (min) t t>Te1 (Γ2 ) max (min) (Γ2 )) HG (Γ′ ) (t)+HG (Γ′ ) (t−Te2 1 2 2 2 sup e(min) t t>T (Γ2 )
Once established, combining these two conditions completes the induction and proves I(k + 1). 1) We first show the existence of an assignment Γ′k+1 satis. fying Condition 1. If Γk+1 satisfies Condition 1, then Γk+1 = Γ′k+1 . Otherwise, for all 1 ≤ m̂ ≤ m, G1 (Γk+1 ) ̸= {i | Te1 ≤ Tei < Tem̂ }. Define î = min{1 ≤ i ≤ n | i ∈ / G1 (Γk+1 )} 2 and suppose î ∈ Gĥ (Γk+1 ). Further define G′ĥ (Γk+1 ) = {i ∈ We next show C ∗ (Γ′2 ) ≤ C ∗ (Γ2 ). Because G2 (Γ2 ) ⊂ G2 (Γ′2 ), (min) G1 (Γk+1 ) | Tei ≥ Teĥ (Γk+1 ) = Teî } and G′1 (Γk+1 ) = we have l1max (Γ′2 ) ≥ l1max (Γ2 ). Two cases arise: ′ G1 (Γk+1 ) − Gĥ (Γk+1 ). – If l1max (Γ′2 ) = l1max (Γ2 ), then since G1 (Γ′2 ) ⊂ G1 (Γ2 ), we Consider the assignment Γ′k+1 such that 1) G1 (Γ′k+1 ) = have ′ ′ G1 (Γk+1 ), 2) Gĥ (Γk+1 ) = G′ĥ (Γk+1 ) ∪ Gĥ (Γk+1 ), and 3) (min) Gi (Γ′k+1 ) = Gi (Γk+1 ), when 2 ≤ i ≤ k + 1 and i ̸= ĥ. Note l1max (Γ2 ) + HG1 (Γ2 ) (t − Te1 (Γ2 )) that (min) ≥l1max (Γ′2 ) + HG1 (Γ′2 ) (t − Te1 (Γ2 )). –Pwhen h > ĥ, neither the higher-priority traffic – If l1max (Γ′2 ) > l1max (Γ2 ), there exists î ∈ G′2 (Γ2 ) such 1≤h′ <h HGh′ (Γk+1 ) (t), nor the lower-priority maximum that lî > l1max (Γ2 ). Because σî (t) ≥ lî for all t > 0 and packet size l(max) (Γk+1 ), nor the traffic from priority class h (min) G1 (Γ′2 ) ⊆ G1 (Γ2 ) − î, h itself HGh (Γk+1 ) (t − Teh (Γk+1 )) change. The minimal (min) service function of priority class h is, therefore, unchanged or max l1 (Γ2 ) + HG1 (Γ2 ) (t − Te1 (Γ2 )) ′ S (Γ ) = S (Γ ); h k+1 h k+1 (min) =l1max (Γ2 ) + HG1 (Γ2 )−î (t − Te1 (Γ2 )) – when h = ĥ, the lower-priority maximum packet size (max) (min) (Γk+1 ) remains unchanged. For the higher priority lĥ + σî (t − Te1 (Γ2 )) traffic, we have (min) max ≥l1 (Γ2 ) + HG1 (Γ′2 ) (t − Te1 (Γ2 )) + lî X X (min) H (t) − HGh′ (Γ′k+1 ) (t) max ′ G (Γ ) e ′ k+1 h ≥l1 (Γ2 ) + HG1 (Γ′2 ) (t − T1 (Γ2 )). 1≤h′ <ĥ
(min)
Finally, since HG′2 (Γ2 (t) ≥ HG′2 (Γ2 ) (t − Te2 follows that
(Γ2 )), it
=HG1 (Γk+1 ) (t) − H ĥ
and for traffic from priority class ĥ
(min) =HG1 (Γ′2 ) (t) + HG′2 (Γ2 ) (t) + HG2 (Γ2 ) (t − Te2 (Γ2 )) (min) ≥HG (Γ′ ) (t) + HG′ (Γ ) (t − Te (Γ2 )) 2
2
(min)
HGĥ (Γk+1 ) (t − Teĥ
2
2
2
2
(min) = − HG′ (Γk+1 ) (t − Teĥ (Γk+1 )).
2
2
∗
(Γk+1 ))
(min) − HGĥ (Γ′k+1 ) (t − Teĥ (Γk+1 ))
(min) + HG2 (Γ2 ) (t − Te2 (Γ2 )) (min) =HG (Γ′ ) (t) + HG (Γ′ ) (t − Te (Γ2 )). 1
(t)
=HG′ (Γk+1 ) (t),
(min) HG1 (Γ2 ) (t) + HG2 (Γ2 ) (t − Te2 (Γ2 ))
1
1≤h′ <ĥ
G′1 (Γk+1 )
ĥ
(Γ′2 ) ≤ C ∗ (Γ2 ).
Combining the two ensures C • Induction Step: Assume I(k) holds for k ≥ 2. We show that it also holds for k + 1. For any (k + 1)-priority assignment Γk+1 , the required bandwidth is (Pn i=1 ri , ∗ C (Γk+1 ) = max , (22) 1≤h≤k sup {Sh (t)/t} (min) t>Teh (Γk+1 ) P max where Sh (t) = (Γk+1 ) + 1≤h′ <h HGh′ (Γk+1 ) (t) + lh (min) HGh (Γk+1 ) (t − Teh (Γk+1 )). We first show that there exists a (k + 1)-priority assignment Γ′k+1 satisfying
(min) (Γk+1 )), we have Since HG′ (Γk+1 ) (t) ≥ HG′ (Γk+1 ) (t−Teĥ ĥ
ĥ
Sĥ (Γk+1 ) − Sĥ (Γ′k+1 ) (min)
=HG′ (Γk+1 ) (t) − HG′ (Γk+1 ) (t − Teĥ ĥ
ĥ
(Γk+1 ))
≥0. ĥ,o (max) max lh (Γk+1 ), maxi∈G′ li . – when n
h
<
(max)
lh
(Γ′k+1 )
=
ĥ
∗ when h > 1, the traffic from class h itself does not change. Let X X ∆Sh = HGh′ (Γk+1 ) (t) − HGh′ (Γ′k+1 ) (t)
– Condition 1: C ∗ (Γ′k+1 ) ≤ C ∗ (Γk+1 ) ∀ Γk+1 , and ∃ m̂ such that G1 (Γ′k+1 ) = {i | Te1 ≤ Tei < Tem̂ }.
1≤h′ <h
1≤h′ <h
= HG1 (Γk+1 ) (t) − HG′1 (Γk+1 ) (t) = HG′ (Γk+1 ) (t)
Under a slight abuse of notation, Condition 2 then states that for any assignment Γk+1 satisfying Condition 1, there exists a (k + 1)-priority assignment Γ′k+1 satisfying
ĥ
denote the reduction on higher-priority traffic by replacing Γk+1 with Γ′k+1 . 15
∗ when h = 1, class h is the highest priority class. Let
which further gives n o (min) (min) max sup Sh (t|Γk ) + HG1 (Γk+1 ) (t) /t =HG1 (Γk+1 ) (t − Te1 (Γk+1 )) − HG1 (Γk+1 ) (t − Te1 (Γ′k+1 )) 1≤h≤k t>Te(min) (Γ ) k h (min) =HG′ (Γk+1 ) (t − Te1 (Γ′k+1 )) ĥ n o denote the traffic reduction from class 1 itself by replacing Sh (t|Γ′k ) + HG1 (Γk+1 ) (t) /t . ≥ max sup 1≤h≤k (min) Γk+1 with Γ′k+1 . (Γ′k ) t>Teh (max) (max) (23) In both cases, when lh (Γ′k+1 ) = lh (Γk+1 ), we ′ Now consider the (k + 1)-priority assignment Γ , where ′ k+1 have Sh (Γk+1 ) ≤ Sh (Γk+1 ) since ∆Sh ≥ 0. When there Gh+1 (Γ′k+1 ) = Gh (Γ′k ) for all 1 ≤ h ≤ k, and G1 (Γ′k+1 ) = (max) ′ ′ exists a flow ĩ ∈ Gĥ (Γk+1 ) such that lh (Γk+1 ) = G1 (Γk+1 ). By the definition of G1 (Γk+1 ) and Γ′k , we know (max) lĩ > lh (Γk+1 ). Since both σĩ (t) ≥ lĩ and σĩ (t − that Te(max) (Γ′ ) < Te(min) (Γ′k+1 ), ∀1 ≤ h < h′ ≤ k + 1. k+1 h h′ (min) (min) ′ e Th (Γk+1 )) ≥ lĩ when t > Teh (Γ′k+1 ), we have Next we show that C ∗ (Γ′ ) ≤ C ∗ (Γk+1 ). k+1 ∆Sh ≥ lĩ , and therefore Since Sh+1 (Γ′k+1 ) = Sh (Γ′k ) + HG1 (Γk+1 ) (t), ∀1 ≤ h ≤ k, combined with Inequality 23, we have Sh (Γk+1 ) − Sh (Γ′k+1 ) ∆Sh
(max)
=lhmax (Γk+1 ) − lh
C ∗ (Γ′k+1 ) n X = max ri , sup {Sh (t|Γ′k+1 )/t} 1≤h≤k+1 (min) t>Teh (Γ′k+1 ) i=1 Pn r, n i=1 i o supt>Te(min) (Γ′ ) Sh (t|Γ′k ) + HG1 (Γk+1 ) (t) /t = max h k 2≤h≤k+1 sup e(min) ′ {S1 (t|Γ′ )/t} k+1 t>T (Γk+1 ) Pn 1 r, n i=1 i o supt>Te(min) (Γ ) Sh (t|Γk ) + HG1 (Γk+1 ) (t) /t , ≤ max k h 2≤h≤k+1 sup {S1 (t|Γk+1 )/t} (min) e t>T1 (Γk+1 ) n X = max ri , sup {Sh (t|Γk+1 )/t} 1≤h≤k+1 (min) t>Te (Γ )
(Γ′k+1 ) + ∆Sh
=lhmax (Γk+1 ) + ∆Sh − lĩ ≥0, which also implies Sh (Γ′k+1 ) ≤ Sh (Γk+1 ). We have, therefore, shown that for all priority classes Sh (Γ′k+1 ) ≤ Sh (Γk+1 ), which establishes that C ∗ (Γ′k+1 ) ≤ C ∗ (Γk+1 ) and proves the existence of an assignment Γ′k+1 satisfying Condition 1. 2) Next we show that for any (k + 1)-priority assignment Γk+1 satisfying Condition 1, there exists a (k + 1)-priority assignment Γ′k+1 satisfying Condition 2. For Γk+1 , there exists 1 ≤ m̂ ≤ m such that G1 (Γk+1 ) = {i | Te1 ≤ Tei < Tem̂ }. If G1 (Γk+1 ) = ∅, by induction of hypothesis I(k) we have I(k + 1). Hence, we focus on the case where G1 (Γk+1 ) ̸= ∅. Consider the subset of flows F̃ = {i|m̂ ≤ i ≤ m}, i.e., F̃ = F − G1 (Γk+1 ). According to I(k), there exists a kpriority assignment Γ′k for F̃ such that ∀1 ≤ h < h′ ≤ k, (max) (min) Teh (Γ′k ) < Teh′ (Γ′k ). Γ′k gives a minimum required bandwidth of k+1 X C ∗ (Γ′k ) = max ri , sup {Sh (t|Γ′k )/t} . 1≤h≤k (min) t>Te (Γ′ ) i=m̂
h
i=1
k+1
=C (Γk+1 ). Hence we show the existence of a assignment Γ′k+1 satisfying Condition 2. A PPENDIX C T ECHNICAL D ETAILS A. NLP Formulation for the FIFO Case
k
The formulation of Non-Linear Programs (NLPs) for solving MINF IF O closely follows the methodology in Section IV.B and Appendix B.E of [20]. We first note that, according to Eq. (6), the link bandwidths Cj (1 ≤ j ≤ n) can be derived from the scheduling delay bounds Tj and the flow shaping delays Di (1 ≤ i ≤ m). According to Eq. (6) and Lemma 7 of [20], the required bandwidth Cj∗ is given by P X σ (D ) i i∈Fj î , (24) Cj∗ = max ri , î∈Fj Te′
Consider the k-priority assignment Γk , where Gh (Γk ) = Gh+1 (Γk+1 ) for all 1 ≤ h ≤ k. Applying Γk to F̃ and using the fact that C ∗ (Γk ) ≥ C ∗ (Γ′k ), we then have C ∗ (Γk ) k+1 X = max ri , sup {Sh (t|Γk )/t} 1≤h≤k (min) t>Teh (Γk ) i=m̂ k+1 X {Sh (t|Γ′k )/t} ≥ max ri , sup 1≤h≤k (min) (Γ′k ) t>Teh i=m̂ ⇐⇒ max sup {Sh (t|Γk )/t} 1≤h≤k (min) t>Teh (Γk ) ≥ max sup {Sh (t|Γ′k )/t} , 1≤h≤k (min) t>Te (Γ′ ) h
h
∗
i∈Fj
îj
where Teij′ = Tj + Di is the inflection point of the minimal service function Sj . Pn Solving MINF IF O entails minimizing j=1 Cj using Eq. (24), by exploring all feasible Tj and Di combinations that satisfy Eq. (4). To formulate MINF IF O as an NLP, we first require a closed-form expression for Eq. (24). This is
k
16
application distributions. For each of these 10 configurations, we generate 10 random initial deadline allocations22 , resulting in a total of 100 instances. For each instance, we apply the three candidate strategies (k-means, same-size, and uniform) to determine priority assignments, and compare them against 100 randomly generated assignments. The required bandwidth at each link is computed using Eq. (6). For each strategy, we record the percentage of random assignments it outperforms at each link, and aggregate this metric across all links. The resulting cumulative distribution functions (CDFs) are plotted in Fig. 14 for k = 2, 4, and 8 priority classes. A lower CDF indicates a higher likelihood of outperforming random assignments, and thus better bandwidth minimization performance. Across all values of k, k-means consistently outperforms the other strategies, with its advantage increasing with the number of priority classes. For example, k-means outperforms 90% of random assignments with probabilities approximately 50%, 60%, and 85% for k = 2, 4, and 8, respectively. This suggests that, as the number of priority classes grows and the boundary selection problem becomes more complex, simple rule-based or random strategies become less effective, while k-means better captures the impact of the underlying distribution of local deadlines. Intuitively, k-means groups flows with similar local deadlines into the same priority class, creating a clearer separation of scheduling requirements across classes. This structure allows the scheduler to more effectively absorb burstiness from higher-priority traffic before serving lower-priority classes, thereby reducing the overall bandwidth requirement.
achievable when the relative order of the inflection points Teij′ is fixed—denoted as condition ORD in Section IV.B of [20]—which depends solely on Di because Tj is identical for all flows sharing link j under FIFO scheduling. Consequently, once an ordering of Di (1 ≤ i ≤ m) is specified, the ordering of all inflection points across all links is determined, enabling a closed-form NLP formulation for MINF IF O . We now consider a concrete example of a link j with two flows. Suppose the shaping delays satisfy: D1 ≤ D2 . The required bandwidth Cj fig:dd can be represented as a set of nonlinear constraints, beginning with the stability constraint: X ri = r1 + r2 , Cj ≥ i∈Fj
Additional constraints arise from the inflection points on Sj : Cj ≥
b1 + R2 D1 Te′ 1j
b1 D2 + b2 D1 = (Tj + D1 )D2 b1 + r1 (D2 − D1 ) + b2 Cj ≥ Te′ 2j
b1 + r1 (D2 − D1 ) + b2 = . Tj + D2 Applying the same procedure to all network links yields the complete set of nonlinear constraints. Together with the global shaping delay ordering constraint, these form an NLP instance for solving the problem. Finalizing a solution to MINF IF O entails enumerating all permutations of Di and solving the corresponding NLPs, a process that is inherently combinatorial. To balance solution quality with computational efficiency, we adopt the randomized combinatorial search strategy proposed in [20], which evaluates only a logarithmic subset of feasible orderings.
B. Shaping Ratio across Priority Classes Focusing on the case n = 2 from Fig. 10a, when flows traverse short paths, we analyze the shaping ratio Di /dbi of flows within each priority class. Since priority assignment is performed independently at each hop, a flow may belong to different priority classes along its path. We therefore compute the average shaping ratio for each class as a weighted average over flows, where the weight corresponds to the fraction of hops at which a flow is assigned to that class. The results are shown in Fig. 15. Some higher-index (lowerpriority) classes, such as classes 6–8, may not appear for small numbers of flows, as they are only populated when sufficient flow diversity exists. We observe that flows in the highest priority class (class 1) are almost always fully shaped. This is intuitive: highest-priority flows experience no interference from lower-priority traffic and effectively see FIFO-like service23 . As a result, their optimal solution aligns closely with FS, consistent with the observations in Section V-B. For lower-priority classes, the shaping ratio generally decreases as the number of flows increases. This trend mirrors the bandwidth improvements observed in Fig. 10a: with more flows, greater heterogeneity in deadline requirements allows
A PPENDIX D S UPPLEMENTARY R ESULTS A. Performance of k-means Clustering on Priority Assignment Recall from Lemma 3 that assigning flows to priority classes at each hop amounts to selecting k + 1 boundary values {Ťhj }k+1 h=1 to partition flows’ deadlines. To assess the performance of k-means in selecting these boundaries, we compare it against three alternative strategies: same-size that selects boundaries to ensure that each priority class is assigned the same number of flows; uniform that selects equidistant boundaries in the range of local deadlines, and random that randomly places boundaries in the range of local deadlines. We use the random strategy as a baseline and report the performance of the other three strategies relative to it. Specifically, we report the percentage of random assignments they outperform (i.e., assignments requiring as much or more bandwidth). We fix the number of flows to 3000, and sample 10 random source–destination pairs (s-d pairs) from the US-Topo topology, each with flow profiles drawn from the corresponding
22 As described in Section IV-B2, initial allocations are obtained by randomly selecting shaping delays and evenly distributing the remaining delay budget across hops. 23 Under the fluid model, lower-priority traffic does not affect higher-priority classes.
17
0.8 0.6 0.4 0.2
1.0
same-size uniform k-means
0.8
CDF
CDF
1.0
same-size uniform k-means
0.6 0.4 0.2
0.0 0%
20%
40%
60%
80%
100%
Percentage of random assignments outperformed
0.6 0.4 0.2
0.0 0%
20%
40%
60%
80%
100%
Percentage of random assignments outperformed
(a) 2 priority classes
same-size uniform k-means
0.8
CDF
1.0
(b) 4 priority classes
0.0 0%
20%
40%
60%
80%
100%
Percentage of random assignments outperformed
(c) 8 priority classes
Fig. 14: Distributions on the percentage of random assignments outperformed across different priority assignment strategies. vary, relative to the improvement SCED yields over FIFO24 . In other words, a gap of 100% means that static priority performs no better than FIFO, while a gap of 0% means that static priority achieves the same improvement over FIFO as SCED. The results are reported in Fig. 16, which, consistent with earlier observations, shows that increasing the number of flows introduces greater heterogeneity in delay requirements, which SCED is better able to leverage. Additionally, as the number of hops increases, static-priority solutions tend to converge towards FS, while SCED remains able to exploit scheduling flexibility at individual hops, thereby, increasing its ability to outperform static priority.
Shaping Ratio
100%
class 1 class 2 class 3 class 4 class 5 class 6 class 7 class 8
80% 60% 40% 20% 1
2
3
4
5
Log2 Flow Parameter m
6
7
Fig. 15: Shaping ratio for each priority class from Greedy Reprofiling’s solution on parking lot topology (with the number of links n = 2).
the scheduler to exploit in-network delay allocation more effectively, reducing reliance on shaping. Interestingly, higher-priority classes do not always exhibit higher shaping ratios. In fact, for classes 3 through 8, lowerpriority classes often have higher shaping ratios. This is due to the discrete deadline classes used in the parking lot setup (10, 25, 50, and 100 ms). Flows with larger deadlines can afford more shaping while still retaining relatively large local deadlines, which results in their assignment to lower-priority classes despite having higher shaping ratios.
Number of Links n
C. Performance Gap between Static Priority and SCED
10
100%
8
80% 60%
6
40%
4
20%
2 1
2
3
4
5
6
Log2 Flow Parameter m
7
0%
Fig. 16: Performance gap between static priority and SCED (with regard to relative bandwidth improvement over FIFO) on the parking lot topology. As Fig. 6 and Fig. 10, we seek to more systematically explore the impact of scale, both hop count (n) and number of flows (m) on the performance among schedulers. As before, we rely on the parking lot topology of Fig. 4, and report on the performance gap between SCED and static priority as m and n
24 Let the required bandwidths under FIFO, static-priority, and SCED be x, y, and z, respectively. The performance gap between SCED and static priority y−z relative to SCED’s improvement over FIFO is, therefore, of the form x−z .
18