Scheduling in Multi-Hop Wireless Networks With Deadlines
arXiv:2604.17493v1 [cs.NI] 19 Apr 2026
Nicholas Jones and Eytan Modiano Abstract—We analyze the problem of scheduling in wireless networks to meet end-to-end service guarantees, defined by instantaneous throughput and hard packet deadlines. Using a network slicing model to decouple the queueing dynamics between flows, we show that the network’s ability to meet hard deadline guarantees under interference is largely influenced by the link scheduling policy. We characterize throughput- and deadline-optimal policies for a solitary flow operating in isolation, which provide bounds on feasibility in the general case with multiple flows. We prove that packet delays can grow arbitrarily large in the multi-flow setting under a worst-case stabilizing policy, showing that queue stability is not sufficient to guarantee tight deadlines. We derive conditions on end-to-end packet delays in terms of link inter-scheduling times, and show that it is possible to make hard guarantees under any interference model by solving a generalized version of the pinwheel scheduling problem. Finally, we introduce a decentralized polynomial-time algorithm which can meet tight end-to-end packet deadlines while achieving nearoptimal throughput.
I. I NTRODUCTION Next-generation wireless networks require strict throughput and delay guarantees for technologies such as real-time control and inference taking place over the network. Due to the need for high reliability, best-effort service is insufficient to meet these needs. The 5G standard supports Quality of Service (QoS) guarantees at the flow level using network slicing [1], [2], and the level of network traffic with QoS requirements is only expected to grow with 6G and beyond. A largely open question, however, is how to efficiently schedule resourcelimited wireless networks to guarantee these QoS requirements are met. Much of the wireless scheduling literature focuses on online scheduling policies and stochastic arrivals, most notably the well-known Max-Weight policy [3] and its variants. Recently, work has been done on online scheduling to meet hard packet deadlines, with policies that guarantee performance within a constant factor of an optimal offline policy under the same traffic arrivals [4], [5]. Unfortunately, without putting constraints on network traffic, these optimality factors can become large, and it is difficult to make guarantees on the service that any single packet will experience. Motivated by this, we consider traffic flows with deterministic arrivals, and This material is based upon work supported by the Department of the Air Force under Air Force Contract No. FA8702-15-D-0001. Any opinions, findings, conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the Department of the Air Force. The authors are with the Laboratory for Information and Decision Systems (LIDS), Massachusetts Institute of Technology, Cambridge, MA 02139, USA (email: [email protected], [email protected])
a class of policies which may be computed online but are able to make guarantees on both throughput and end-to-end delay a priori. We consider wireless networks with general topologies, and develop efficient scheduling policies to meet a given set of QoS requirements. In particular, we study the impact that wireless interference plays on end-to-end packet delay and optimize our scheduling policies to account for this. We use a network slicing model akin to virtual circuits to decouple the queueing dynamics between traffic flows. This model is not only practical for making service guarantees, but useful for highlighting the impact of interference. In the offline wireless scheduling literature, there is a large body of work on scheduling for throughput maximization [6]– [8]. Most notably, Hajek and Sasaki designed an algorithm to find a minimum schedule length which meets a set of link demands in polynomial time [7], and Kodialam et al. used Shannon’s algorithm for coloring a multigraph to efficiently schedule links while achieving at least 2/3 of maximum capacity [8]. There has also been considerable work on QoS guarantees in networks. One of the first approaches was Cruz’s network calculus [9], [10], which bounds the delay that each packet experiences over multiple hops in a wired network, when arrivals are constrained by a traffic-shaping envelope. Several works have extended this framework to the wireless setting using a variant called stochastic network calculus [11]–[14], which bounds the tails of arrival and service processes to obtain a high-probability bound on end-to-end delay. While network calculus is perhaps the most comprehensive analytical QoS framework in the literature, it fails to capture the interference present in wireless networks. It is certainly possible to fix a scheduling policy respecting interference constraints and use calculus to find delay bounds, but optimizing this schedule quickly becomes intractable. A novel QoS framework for single-hop wireless networks was developed by Hou and Kumar [15]. It assumes a set of sources, each with a single packet that must be delivered by the end of a frame with some probability, thereby meeting a deadline equal to the frame length. They design a policy to ensure the “delivery ratio,” or time average fraction of packets which are delivered within each frame, meets a reliability requirement. They extend this framework in [16] to solve utility maximization and in [17] to support Markov arrival processes. Several works have extended a version of this framework to multi-hop. In [18], the authors analyze a multi-hop network
with end-to-end deadline constraints and develop policies to meet delivery ratio requirements over wired links. In [19], the authors design a spatio-temporal architecture with virtual links to solve a similar problem. In [20] and [21], the authors analyze a multi-hop wireless network with unreliable links. By considering each packet individually, they develop both centralized and decentralized policies for maximizing throughput with hard deadlines, using relaxed link capacity constraints and assuming no interference. The works closest to ours are [22] and [23], which consider a multi-hop wireless network and find a transmission schedule to meet deadline guarantees under constant traffic arrivals. Similar to the works above, they split time into frames and develop a mixed-integer program to find an optimal ordering of link activations within each frame, bounding packet delay as a linear function of the frame length. They show that the optimal ordering can be found in polynomial time under tree topologies. The authors of [24] and [25] generalize the arrival processes to calculus-style envelopes and consider the case of sink-tree networks, while routing is incorporated into [26]. The authors of [27] show that shortening frame lengths and optimizing slot re-use for non-interfering links can improve efficiency. In this paper we adopt a novel approach to meeting QoS guarantees under wireless interference by removing the dependency between packet deadlines and the traditional notion of frame length. We show that deadline guarantees can be made by bounding link inter-scheduling times, effectively creating unique frames for each link with endpoints at scheduling opportunities, and interleaved in time with the frames of other links. This greatly enhances the flexibility of the schedule, allowing us to simultaneously achieve tighter deadlines and higher throughput, while ensuring that interference constraints are met. Our main contributions can be summarized as follows. • In Section III, we develop conditions on throughput and deadline feasibility for a solitary flow. We introduce an Ordered Round-Robin scheduling policy in this setting, provide tight delay bounds, and show that it is deadlineoptimal when throughput is below a certain threshold. Above this threshold, we show that a greedy policy is deadline-optimal under a total interference model, when only one link can be scheduled at a time, and is a good heuristic in the general case. • In Section IV, we prove a tight upper bound on endto-end packet delays under the worst-case stabilizing policy, and show that delay can grow arbitrarily large even though queues are stable. We then show that under some mild assumptions, end-to-end delay can be bounded as a function of link inter-scheduling times. Using these conditions, we examine the general problem of multiple flows in an arbitrary topology, and we formulate a feasibility problem to jointly satisfy deadline, rate, and interference constraints. We show that under total interference, the problem reduces to an NP-complete problem known as pinwheel scheduling [28], and we introduce a generalized version of this problem which we call pinwheel coloring
for an arbitrary interference model. In Section V, we design a polynomial-time algorithm called Weighted Greedy Coloring (W GC), which approximately solves the pinwheel coloring problem when coupled with existing pinwheel schedulers. This algorithm can be run in a decentralized fashion at each node, requiring no control overhead. When it returns a feasible solution, it is guaranteed to be a coordinated, conflict-free schedule that meets rate and deadline constraints for all flows. • Finally, in Section VI, we demonstrate the performance of our algorithms through extensive simulations, verifying that greedy is a good heuristic for solitary flows and that the W GC algorithm can simultaneously achieve tight deadlines and near-optimal throughput for a variety of network topologies and traffic arrivals. An earlier version of this work appeared in the conference proceedings of ACM MobiHoc 2024 [29]. •
II. P RELIMINARIES A. System Model We consider a wireless network with fixed topology modeled as a directed graph G = (V, E). Time is slotted, with the duration of a slot dictated by the physical and link layers of the network. Each link e ∈ E has a fixed capacity ce and can transmit up to this number of packets in each time slot it is activated. Because links share a wireless channel, they are subject to interference, which restricts the links that can be scheduled at the same time. We assume a centralized controller that computes a pre-determined offline schedule of noninterfering links to activate in each slot, and communicates this schedule to each node ahead of time. We consider general interference models, which can be described using a conflict graph. Define the conflict graph of the network graph G as Gc = (Vc , Ec ), and let each vertex v ∈ Vc correspond to a link in the network graph G. An edge exists between two conflict nodes v and v ′ if and only if their corresponding links interfere in the network graph. We assume that interference is mutual between links, so Gc is an undirected graph. Any clique in the conflict graph represents a set of mutually interfering links, and any independent set in the conflict graph is a set of links that can be activated simultaneously. We denote the set of all feasible activation sets as M. In some cases it is useful to consider a subset of interference models Φ, which take the form of ϕ-hop interference constraints. Specifically, for any ϕ, no two links can be activated at the same time if they are separated by fewer than ϕ hops. We will also refer to the interference model itself as ϕ ∈ Φ. In the special cases of no interference and total interference, where only one link can be activated at a time, we define ϕ to be 0 and |E| − 1 respectively. We denote Mϕ as the set of feasible activation sets under the model ϕ. Traffic arrives at the network in the form of flows, which request a level of service from the network. Each flow fi ∈ F
is assigned a fixed pre-determined route T (i) from source to (i) destination, and we denote Tj as the j-th hop in the route. Arrivals are deterministic, with λi packets belonging to flow fi arriving at its source node in each slot1 . We assume a fluid traffic model, so λi need not be integer, and we colloquially use the terms packet and traffic interchangeably throughout the paper. Flows are further characterized by a deadline τi for each fi , and we say that a packet meets its deadline if it is delivered to its destination (over possibly many hops) within τi slots of when it arrives, otherwise the packet expires. Assume that packet arrivals stop at time T , but packets remaining in the network are given time to be served by their respective deadlines. Each link e ∈ T (i) reserves capacity for flow fi in the form of a network slice, akin to a virtual circuit, with slice width (i.e., capacity) equal to wi,e . We will also refer to the slice itself as wi,e when there is no risk of confusion. Because link capacities are fixed, the sum of all slice widths allocated on link e must be bounded by ce . Each slice has its own first-come-first-served queue, which decouples the queueing dynamics between flows. Let Qi,e (t) be the size of the queue belonging to slice wi,e at the beginning of time slot t. We assume the network is empty before t = 0, so Qi,e (t) = 0 for all i and e, and all t < 0.
B. Policy Structure Define Π as the set of admissible scheduling policies, which are work-conserving and satisfy interference constraints. Let µπ (t) ∈ M be the set of links activated at time t under π, and let µπe (t) = 1 if e ∈ µπ (t) and 0 otherwise. The workconserving property ensures that each scheduled link serves the smaller of its queue size and its slice capacity each time it is activated. We are interested in policies which meet the following performance objective. Definition 1. A policy π ∈ Π supports the set of flows F if and only if all packets in F reach their destination without expiring, over any finite time horizon T .
Fig. 1: Illustrative Two-Hop Example
Theorem 1. If there exists a policy in Π that supports F, then there must exist at least one such cyclic policy π ∈ Πc , and some t0 > 0, such that Qπi,e (t) = Qπi,e (t + K π ), ∀ fi ∈ F, e ∈ E, t0 ≤ t ≤ T. (1)
Proof. See Appendix A. Here t0 represents the time required for the network to “ramp up” from its initial state. The theorem shows that after this ramp-up period, the network will reach a steady state under any cyclic policy π, and that we can restrict ourselves to such cyclic policies without loss of optimality. For ease of analysis, we assume t0 +K π ≤ T , so that the network operates in steady-state for at least one full scheduling period. Under a cyclic policy π, define the time average activation rate of link e as π
µ̄πe ≜
K −1 1 X π µ (t), K π t=0 e
(2)
and the number of activations per scheduling period as ηeπ ≜ µ̄πe K π . Clearly for packets to meet any finite deadline, queues must be bounded by a finite constant. We refer to any queue which remains bounded as T → ∞ as stable, which leads to the following condition on activation rates. Corollary 1. Queues are stable under a policy π ∈ Πc if and only if µ̄πe ≥
λi , ∀ e ∈ T (i) , fi ∈ F. wi,e
(3)
Proof. See Appendix B. We first show that to meet this objective we need only consider cyclic scheduling policies. Define a scheduling policy π as cyclic if µπ (t) = µπ (t + K π ), for all t ≥ 0 and some positive integer K π , which we refer to as the scheduling period. Denote the set of all admissible cyclic scheduling policies as Πc ⊆ Π.
1 This can be generalized to a network calculus-style envelope, and for simplicity of exposition we assume traffic shaping occurs before packets arrive at the source.
While stability is necessary for deadlines to be met, it is not sufficient, because queues may still grow too large to satisfy deadlines. Consider the two-hop example in Figure 1, with flow f1 traveling from node 1 to node 3, and f2 traveling in the opposite direction. Both flows have a deadline of 10 slots, with λ1 = 9 and λ2 = 1. Assume only one link can be active at a time due to interference, and let the capacity of each link be 27. Note that while links are drawn as bi-directional, this represents two separate directional links in our model. Because only one flow traverses each link, we can set slice widths equal to link capacity in all cases.
From (3), we observe that a necessary condition for supporting F is that links (1, 2) and (2, 3) are activated at least λ1 1 27 = 3 of the time, and links (3, 2) and (2, 1) are activated 1 at least λ272 = 27 of the time. Consider the cyclic policy π1 = {(1, 2), (2, 3), (3, 2), (1, 2), (2, 3), (2, 1)},
(4)
which repeats itself every 6 slots, and where µ̄(1,2) = µ̄(2,3) = 1 1 3 and µ̄(2,1) = µ̄(3,2) = 6 . This satisfies the necessary activation rates, so all queues are stable under π1 . In fact, a close examination shows that no more than 27 packets can arrive at any link in between slots when that link is scheduled, so queues are not only stable but are emptied each time they are served. This means that packets see no queueing delay, and experience only scheduling delay, i.e., waiting for a link to be scheduled. Given this, one can verify that packets arriving at t = 1, 4, 7, . . . experience the largest delay of any f1 packets. These packets must wait 3 slots before reaching node 2 and 4 slots before reaching their destination. Similarly, packets arriving at t = 3, 9, 15, . . . experience the largest delay of any f2 packets. These packets must wait 6 slots before reaching node 2, and then another 3 slots before reaching their destination, resulting in a total delay of 9 slots. The worst-case delay for both flows satisfies deadline constraints, so π1 is a supporting policy. Note that if deadlines were tightened to τ1 = τ2 = 8, the above policy would not satisfy deadlines, but would still remain stable. Furthermore, there exist many alternative schedules where queues are stable but the original deadlines τ1 = τ2 = 10 are not satisfied. Consider the schedule π2 = {(2, 3), (2, 3), (1, 2), (1, 2), (2, 1), (3, 2)},
(5)
which again repeats itself every 6 slots, and note that this is simply a re-ordering of π1 . Because activation rates are unchanged, the queues are guaranteed to be stable as under π1 , but the re-ordering of the schedule drastically increases the scheduling delay. Consider an f1 packet that arrives at t = 4. It must wait 5 slots before it reaches node 2, followed by another 4 slots before it reaches node 3. Similarly, consider an f2 packet that arrives at t = 0. It must wait 6 slots before it reaches node 2, and then another 5 slots before it reaches node 1. The worst-case delays increase from 4 and 9 slots respectively under π1 to 9 and 11 slots respectively under π2 . Simply shuffling the order of the schedule more than doubles packet delays for f1 and causes f2 packets to miss their deadlines. This leads to the following critical observation.
necessary and sufficient condition for meeting deadlines from Theorem 1. Corollary 2. All flow fi packets meet their deadlines under a scheduling policy π ∈ Πc if and only if X max Qπi,e (t) ≤ λi τi , (6) 0≤t≤T
e∈T (i)
for any finite T .
Proof. Follows from the proof of Theorem 1. Before analyzing the general case, it is instructive to characterize the feasible guarantees that can be made to a solitary flow fi under a policy π ∈ Πc , which is the focus of the next section. III. S OLITARY F LOW F EASIBILITY In this section we consider a solitary flow that operates in isolation, so the policy can be optimized independently of other traffic. We can then view a flow fi ’s route T (i) as a line network with the source at one end and the destination at the other. In addition, we assume this line network follows a ϕ-hop interference model for ease of analysis. Denote the set of jointly achievable rate and deadline guarantees for fi under an interference model ϕ and fixed set of slices w as Λϕi (w). In the general setting, with flows on separate routes coupled through the scheduling policy, the jointly achievable region over all flows is a subset of what can be achieved by each flow in isolation. Analyzing Λϕi (w) allows us to define not only optimal policies for a single flow, but also bounds on feasibility in the general case. Because we are focused on a single flow in the remainder of this section, we drop the subscript i for ease of notation and note the results hold for all flows without loss of generality. We begin by characterizing throughput optimality. A. Throughput Optimality Define λ∗ (π, w) as the maximum rate a flow can take as τ → ∞, under fixed slice widths w and while supported by a policy π. We omit the dependency on ϕ for ease of notation. From Corollary 1, it immediately follows that λ∗ (π, w) = min µ̄πe we , e∈T
Observation 1. In addition to queue stability, conditions on schedule order are necessary to satisfy deadline guarantees. A large focus of this work is defining these conditions in a meaningful way so that we can design policies which satisfy them in polynomial time. To begin, we extract the following
(7)
and we define a throughput-optimal policy as follows. Definition 2. A policy π ∈ Πc is throughput-optimal for a set of slice widths w if λ∗ (π, w) ≥ λ∗ (π ′ , w) for all π ′ ∈ Πc .
In particular, any throughput-optimal policy is a solution to max min µ̄πe we
π∈Πc e∈T π
s.t. µ (t) ∈ Mϕ , ∀ 0 ≤ t ≤ K π ,
(8)
and we denote the solution as λ∗ (w). This has a closed-form solution given by the following. Theorem 2. For any set of slices w and interference model ϕ ∈ Φ, 1 λ (w) = min H(wj , . . . , wj+ϕ ) ϕ + 1 1≤j≤|T |−ϕ ∗
Definition 3. A policy π ∈ Πc is deadline-minimizing for rate λ and slice widths w if τ ∗ (π, w, λ) ≤ τ ∗ (π ′ , w, λ) for all π ′ ∈ Πc . There is clearly a relationship between τ ∗ and λ, because as rates increase, it becomes harder for every packet to meet its deadline. To capture the inherent scheduling delay caused by interference, we define the rate-independent quantity τ ∗ (π) ≜ lim τ ∗ (π, w, λ),
(13)
λ→0
(9)
and note that this is the smallest deadline that π can guarantee for any λ > 0 and any set of slices. This allows us to define a deadline-optimal policy, independent of arrival rate and slices.
where H(·) represents the harmonic mean.
Proof. The throughput-optimal formulation (8) can be reformulated as
Definition 4. A policy π ∈ Πc is deadline-optimal if τ ∗ (π) ≤ τ ∗ (π ′ ) for all π ′ ∈ Πc .
max λ(w) s.t. λ(w) ≤ µ̄e we , ∀ e ∈ T , j+ϕ X
(10) µ̄l ≤ 1, ∀ 1 ≤ j ≤ |T | − ϕ,
l=j
where link j is understood to mean the j-th hop on the route Tj . The second constraint is equivalent to the interference constraint in (8) because only one of each set of ϕ+1 adjacent links can be activated at once. Combining the two constraints yields j+ϕ X 1 ≤ 1, ∀ 1 ≤ j ≤ |T | − ϕ, (11) λ(w) wl l=j
and rearranging the equation yields λ(w) ≤
1 H(wj , . . . , wj+ϕ ), ∀ 1 ≤ j ≤ |T | − ϕ. (12) ϕ+1
The maximum λ∗ (w) is then equal to the minimum over j, which completes the proof. This result shows that, for a fixed set of slices, the maximum supported rate scales as 1/ϕ, which approximates the average activation rate of each link. The harmonic mean of a set is dominated by the minimum, so this result also shows that the smallest slice (i.e., the bottleneck) has the largest impact on achievable rates, which matches our intuition. B. Deadline Optimality We next turn to characterizing feasible deadline guarantees. Define τ ∗ (π, w, λ) as the minimum deadline a flow can meet, with rate λ and slice widths w, and under a policy π. Equivalently, this quantity is the largest delay seen by any packet in the flow, so we will sometimes refer to τ ∗ as maximum delay when appropriate. We define a deadlineminimizing policy for these parameters as follows.
To avoid confusion, we note the distinction between the terms deadline-minimizing when speaking in terms of a specific arrival rate, and deadline-optimal when speaking independently of arrival rates. In the example in the previous section, we saw that schedule order plays an important role in making deadline guarantees, and we begin to formalize this here with the concept of interscheduling times. Denote the set of time slots where link e is scheduled under a policy π as π(e) ≜ {0 ≤ t ≤ K π | µπe (t) = 1}. Then define the minimum inter-scheduling time of links e and e′ to be the smallest time interval between consecutive scheduling events of links e and e′ . Formally, we define this as k πe,e′ ≜ min min ′ (t2 − t1 ) mod K π , (14) t1 ∈π(e) t2 ∈π(e )
and similarly define the maximum inter-scheduling time as π
k e,e′ ≜ max
min (t2 − t1 ) mod K π .
t1 ∈π(e) t2 ∈π(e′ )
(15)
For ease of notation, we denote the min and max interπ scheduling times of a link e with itself as k πe and k e respectively. Using these quantities, we can bound τi∗ (π) as follows. Lemma 1. For any admissible policy π ∈ Πc , X k πj,j+1 ≤ τi∗ (π) k π1 + 1≤j<|T | π
≤ k1 +
X
π
k j,j+1 ,
(16)
1≤j<|T |
where we slightly abuse notation to denote Tj as link j.
Proof. We first show the lower bound. Any packet delivered to its destination must traverse all links on its route in order, and
under a policy π, every packet served by link e that arrives at link e + 1 must wait at least k πe,e+1 slots before being served. Therefore, the smallest amount of time between being served at P the sourceπ link and being served at the πdestination link is 1≤j<|T | k j,j+1 , and packets must wait k 1 slots from when they arrive at the source link until they are served. Similarly, because λ → 0, all queued packets are served each time a link is scheduled, so a packet must P wait at πmost π k 1 slots to be served at the source link and 1≤j<|T | k j,j+1 slots from when it is served at the source link to when it is served at the destination link. The result follows. These bounds show that in order to keep packet delays small, we should minimize inter-scheduling times between consecutive links on a route. We will show that deadline optimality is in fact achieved by a specific Ordered RoundRobin (ORR) policy, under which the upper and lower bounds in Lemma 1 are tight and minimized over all admissible policies. Recall that under an interference model ϕ, links separated by fewer than ϕ hops cannot be scheduled in the same slot. Then define the ORR policy as follows. At each time t, we activate link Tj , where j = t mod ϕ, along with every ϕ + 1 subsequent links. Then at each slot, links at equally spaced intervals of ϕ + 1 hops are activated, beginning with links {0, ϕ+1, 2(ϕ+1), . . . } at time t = 0, links {1, 1+(ϕ+1), 1+ 2(ϕ + 1), . . . } at t = 1, and so on, where again link j refers to Tj . Note that this schedule has a period K ORR = ϕ + 1.
where we again slightly abuse notation to denote Tj as link j. We can immediately observe that when all slice widths are equal, this quantity becomes zero. Corollary 3. When slice widths are equal across a flow’s route, the ORR policy is both throughput-optimal and deadline-optimal.
Under general slice widths, however, (20) exhibits a tradeoff between supported rates and deadlines. We can achieve deadline optimality with the ORR policy at a cost of sacrificing throughput, and similarly, we can choose an alternative policy to ORR and achieve higher throughput at a cost of sacrificing deadlines. From Corollary 2, a policy under the throughputoptimal rate λ∗ (w) meets deadline τ if and only if X 1 max Qπe (t) ≤ τi . (21) ∗ λ (w) 0≤t≤T e∈T
Then the smallest achievable deadline under a throughputoptimal policy is the solution to min τ ∗ π, w, λ∗ (w) π X 1 Qπe (t) max = min ∗ π λ (w) 0≤t≤T e∈T X ϕ+1 Qπe (t) (22) = min max π minj H(wj , . . . , wj+ϕ ) 0≤t≤T e∈T
Theorem 3. The ORR policy is deadline-optimal under any interference model ϕ ∈ Φ, with a maximum packet delay τ ∗ (ORR) = |T | + ϕ, (17) and activation rates µ̄ORR = e
1 , ∀ e∈T. ϕ+1
(18)
Proof. See Appendix C. Note that under the ORR policy, the bounds in (16) are tight because inter-scheduling times are equal for all individual links and link pairs, with k 1 = k 1 = ϕ and k j,j+1 = k j,j+1 = 1 for all j. From (7), the maximum rate the ORR policy can support for a set of slices w is 1 λ∗ (ORR, w) = min we , (19) ϕ + 1 e∈T which is not throughput-optimal in general. From Theorem 2, the difference between this and the throughput-optimal rate is λ∗ (w) − λ∗ (ORR, w) 1 = min H(wj , . . . , wj+ϕ ) − min we , e∈T ϕ + 1 1≤j≤|T |−ϕ
(20)
= min Γ(π, w) · (ϕ + 1) · |T |, π
within a value of 1 because τ ∗ must be an integer, and where we define P max0≤t≤T |T1 | e∈T Qπe (t) Γ(π, w) ≜ . (23) minj H(wj , . . . , wj+ϕ ) The min is taken over all throughput-optimal π which support rate λ∗ (w). Note that this is less than a factor of Γ(π, w)(ϕ + 1) from τ ∗ (ORR). Minimizing Γ(π, w) over π, however, involves optimizing over all feasible schedule orders which support a rate λ∗ (w). This is a combinatorial optimization problem with a state space that grows exponentially in |T |. In fact, this characterization shows that solving minπ τ ∗ (π, w, λ) for any rate λ > λ∗ (ORR, w) has worst-case exponential complexity. This illustrates the difficulty of minimizing delay even in a line network with a single flow. C. Bottleneck Slice Widths One factor that adds to the complexity of (22) is that a link can serve a variable number of packets each time it is activated, depending on the current queue size. We can simplify analysis by considering a special case where every link is a bottleneck. For a given λ and set of slices w, we know that µ̄e ≥ wλe for Pϕ queues to be stable, and that j=0 µ̄e+j ≤ 1 for all 0 ≤ e < |T | − ϕ due to interference. Combining these conditions, the
minimum slice widths w′ ≤ w that support λ are the solution to the convex program X min we′ ′ w
s.t.
e∈T ϕ X
1 1 ≤ , ∀ 0 ≤ e < |T | − ϕ, ′ w λ j=0 e+j
(24)
′ 0 ≤ wi,e ≤ we , ∀ e ∈ T .
Consider an augmented network with slice widths equal to w′ . We refer to these as bottleneck slice widths because no slice can be reduced while still supporting the rate λ. Because each slice we′ ≤ we , the minimum achievable deadline τ ∗ (π, w′ , λ) is an upper bound on the original τ ∗ (π, w, λ) under any policy π, because no more packets can ever be served with slices w′ . Thus the number of packets in the network at a given time can only be larger, and because this holds for any π, it must hold for the deadline-minimizing policy. Define a greedy scheduling policy under bottleneck slices as follows. At each time t, schedule a link e if Qe (t) ≥ we′ , and if more than one such queue exists, schedule the one closest to the destination. If no such queues exist, schedule the source link. This policy is optimal under total interference.
the more disparate the slice widths are, the more burstiness and delay packets will see, as evidenced by the bound in (25). A particularly large slice width will lead to a small activation rate and therefore a large backlog under greedy, causing the total delay to increase. IV. G ENERAL F EASIBILITY We now turn to understanding general feasibility for simultaneous flows with unique source/destination pairs. We again attempt to characterize the feasible guarantees that can be made under any policy in Πc , this time applying guarantees to all flows jointly. While slicing decouples the queueing dynamics between flows, we have seen that meeting tight deadlines is dependent on schedule order, which couples flows together through the scheduling policy. We assume that multiple flows can be routed over the same link, and our policy is able to choose the slice width allocated to each flow, subject to capacity constraints. In particular, we must jointly optimize slice widths and scheduling to satisfy deadline constraints following the condition in Corollary 2 and capacity constraints following X wi,e ≤ ce , ∀ e ∈ E. (26) fi :e∈T (i)
Combining this with the stability condition in (3) yields Corollary 4. Under total interference and bottleneck slice widths w′ , greedy is deadline-minimizing for any supported rate λ, with X 1 1X ′ . (25) we = τ ∗ (greedy, w′ , λ) ≲ greedy λ e∈T e∈T µ̄e
Proof. See Appendix D. Greedy can be extended to any value of ϕ by again starting at the destination link and moving toward the source, scheduling the first link observed with a full queue. When a link is scheduled, the subsequent ϕ links are skipped, and the next link with a full queue is scheduled. This is repeated until the source link is reached. Unfortunately, this is not guaranteed to be optimal because more than one link can be scheduled per slot. Scheduling the greedy links may preclude another link or set of links from being scheduled which would improve future performance. For this reason, it is unlikely that any myopic policy is optimal outside of the total interference model. Nevertheless, greedy still prevents queues from growing too large and prioritizes packets closer to the destination, enabling them to be delivered quickly. As a result, we conjecture that greedy is near-optimal for any ϕ, and a good heuristic for minimizing τ ∗ under bottleneck slice widths. When slice widths are equal, the greedy policy reduces to ORR as we expect. This follows because if link Tj is scheduled at time t under greedy, then link Tj+1 will be scheduled at t+1 because slice widths are equal, so Qj+1 must be full. By induction, this policy becomes ORR. Intuitively,
X fi :e∈T
λi ≤ ce , ∀ e ∈ E, π µ̄ e (i)
(27)
which is a necessary and sufficient condition for stability under π ∈ Πc , by implicitly setting slice widths equal to wi,e = λi µ̄πe . Recall that slices of this size are by definition bottleneck slice widths. Extending notation from the previous section, we denote τi∗ (π, λi ) as the minimum achievable deadline, or equivalently the maximum packet delay, for a flow fi with rate λi under a policy π which chooses both the schedule and slice widths. In the previous section, we saw that finding a deadlineminimizing policy for a solitary flow has complexity that grows exponentially in the number of queues |T |. This remains true P in the(i) general case, where the number of queues is |, and the worst-case complexity grows exponenfi ∈F |T tially in this quantity. This problem is intractable for all but the smallest problem sizes. Furthermore, because the direction of traffic is no longer the same for all flows, and interference is no longer limited to a line network, the ORR and greedy policies developed in the previous section are clearly no longer applicable. There has been considerable work on scheduling policies that ensure queue stability under interference constraints. Before attempting to optimize for deadlines directly, it is instructive to understand how large packet delays can become under a policy which guarantees that queues remain stable and thus bounded. Because queues are bounded, the maximum packet delay is also bounded, and we can derive an exact expression.
Theorem 4. The worst-case packet delay under any stabilizing policy in Πc is given by X max τi∗ (π, λi ) = max K π (1 − µ̄πe ). (28) π∈Πc
π∈Πc
e∈T (i)
Moreover, there exist many such policies where τi∗ grows linearly with K π .
where T̃ (l) denotes all links on packet l’s route where it has already been served. Delay deficit evolves in the following way. When packet l arrives at the source, δ l (tl0 ) = 0. Then it is incremented by one in each subsequent slot until it reaches its destination, and it is decremented by keπ whenever it is served at link e. A negative delay deficit signifies that a packet has seen less delay than its quota on its route thus far, making it ahead of schedule. A delay deficit larger than the delay quota at a packet’s current link signifies that the packet is behind schedule.
Proof. See Appendix E. Recall that µ̄πe = λi /wi,e = ηeπ /K π , and after rearranging, wi,e K π = ηeπ , ∀ i, e. (29) λi In order to be integer, K π must be an integer multiple of the denominator of wi,e /λi , for all i and e. This is a rational quantity by assumption, but the denominator can grow aribtrarily large under our fluid traffic model. Even when λi is constrained to be integer and represent a discrete number Q of packets, K π can be as large as i λi . This shows that many policies in Πc are insufficient to meet tight deadline guarantees. In fact, it shows that there exists at least one policy where packets experience delays within a constant factor of K π |T (i) |, and many policies where packet delays grow with K π . These are not pathological examples, but rather any policy with inter-scheduling times that are a function of the scheduling period. This includes frame-based policies, like much of the existing QoS scheduling literature, or simply random orderings of activations which happen to have large inter-scheduling times. To avoid delays that grow with K π , and motivated by the complexity of searching over all schedule orders, we derive alternative deadline conditions which drastically reduce the state space of the problem. Using a similar argument to that in Lemma 1, which gives a bound on packet delays in the solitary flow setting, we will show an upper bound on packet delays in our general case subject to conditions on slice widths and maximum inter-scheduling times. A. Delay Deficit First we introduce a quantity called delay deficit. This quantity tracks how long a packet has been in the network relative to a pre-defined quota, which dictates the delay a packet should “expect” to see at each link. Consider a packet l belonging to flow fi , and denote the time that it arrived at its source node as tl0 and the age of this packet at time t as al (t) ≜ t−tl0 . We will show that by setting the delay quota for link e under policy π ∈ Πc to the maximum inter-scheduling π time k e , the delay deficit of any packet will never grow too large. For ease of notation, we will drop the overline in the π quantity k e for the remainder of the paper and refer to this simply as keπ . Define the delay deficit of packet l at time t as X δ l (t) ≜ al (t) − keπ , (30) e∈T̃ (l)
Lemma 2. Under any policy π ∈ Πc , with maximum inter-scheduling times keπ and slice widths wi,e ≥ λi keπ , for all e ∈ T (i) , the delay deficit of a packet belonging to flow fi will never be larger than zero when it arrives at a new link. Proof. See Appendix F. It is important to note that this result and the subsequent theorem hold even though a packet is not necessarily served at link e within keπ slots of arrival. This would require larger slice widths to guarantee that queues are emptied each time a link is scheduled. Rather, our choice of slice widths ensures that a packet is scheduled within keπ slots of when its delay deficit becomes positive. This is demonstrated by the example in Figure 2, which shows the first two queues of a flow fi ’s route and the delay deficit of one packet. For simplicity we let λi = 1 and assume that k0 = 3 and k1 = 4, noting that the schedule shown in the figure satisfies these maximum inter-scheduling times. Let slice widths wi,0 = 3 and wi,1 = 4, which satisfy the condition in Lemma 2. The figure shows the queue position and delay deficit of the packet marked with an X. Note that the packet remains in Qi,1 for longer than k1 slots, but that its delay deficit is still negative when it arrives at the next link. This is possible because the packet only spends one slot in Qi,0 , so it arrives at the second link “early” with a negative delay deficit. An immediate consequence of Lemma 2 is the following end-to-end delay bound, which will form the basis for our scheduling policies in the next section. Theorem 5. Under any policy π ∈ Πc , with maximum inter-scheduling times keπ and slice widths wi,e ≥ λi keπ , for all e ∈ T (i) , X |T (i) | ≤ τi∗ (π, λi ) ≤ keπ . (31) e∈T (i)
Proof. The lower bound is simply the length of the route, so it holds trivially. Now we will show the upper bound. Imagine a ficticious exit link leaving the destination node of fi . From
Corollary 5. A policy π ∈ Πc with maximum interscheduling times kπ supports a set of flows F if it is a solution to (P 1) : find π X
s.t.
keπ ≤ τi , ∀ fi ∈ F,
e∈T (i)
X
wi,e ≤ ce , ∀ e ∈ E,
(33)
fi :e∈T (i)
wi,e = λi keπ , ∀ fi ∈ F, e ∈ T (i) , µπ (t) ∈ M, ∀ 0 ≤ t < K π . Furthermore, if π is a regular schedule, then all slices are equal to their bottleneck values. Fig. 2: Queue Size and Delay Deficit Evolution Lemma 2, the delay deficit of a packet which reaches this link zero, so from (30) the packet’s age is at most P is at most π e∈T (i) ke . This completes the proof. We note several things about this result. First, it subsumes the worst-case delay bound in Theorem 4. In particular, in the proof of Theorem 4, the worst-case scenario is shown to have a maximum inter-scheduling time keπ = K π (1 − µ̄πe ) for all links e, which makes the bounds identical under this policy. Second, when links are scheduled more regularly and keπ is independent of the schedule length, this bound can be significantly tighter than that in Theorem 4 and is within a factor of the average keπ from the lower bound. Intuitively, bounding the inter-scheduling times for each link bounds how far a policy can deviate from the ORR policy for each flow. The ORR policy ensures that once packets are served at a link, they are immediately served at the subsequent link in the next slot. While this is no longer feasible in the general case, the delay deficit conditions show that no packet can wait too long to be served when inter-scheduling times are small, bounding the deviation from the ORR policy. A final thing to note is that, while the necessary conditions on slice widths are larger than their bottleneck values, the amount of additional slice capacity required is generally small. Define this additional capacity for slice wi,e as 1 ∆wi,e (π) ≜ λi keπ − π ≥ 0. µ̄e
(32)
Because the average inter-scheduling time is 1/µ̄πe , ∆wi,e (π) is small when inter-scheduling times are somewhat regular and the maximum is not much larger than the average. If interscheduling times are always equal, then keπ = 1/µ̄πe for all e ∈ E, and ∆wi,e (π) = 0. When this holds we say that π is a regular schedule.
Proof. The sufficient conditions come from the deadline bound in Theorem 5 and link capacity constraints. If both of these are satisfied for all flows and links, then π is guaranteed to support F by Theorem 5. The conditions in Corollary 5 are sufficient but not necessary for a policy to support F . It is interesting to note, however, that after combining constraints, the deadline bound becomes X 1 X ke = wi,e ≤ τi , (34) λi (i) (i) e∈T
e∈T
which is equal to the approximate bound on τ ∗ under the greedy policy for a solitary flow in (25). Recall that greedy is optimal under total interference, and we conjecture that it is near-optimal under more relaxed interference constraints. This leads us to conclude that the conditions in Corollary 5 are close to necessary and further motivates our approach. B. Pinwheel Scheduling The conditions in Corollary 5 present a massive reduction in complexity from tracking the age of each individual packet to ensure its deadline is met. Nevertheless, finding a schedule which satisfies these conditions is still a non-trivial task. In addition to finding a vector of integers kπ which satisfies constraints, we must also construct a feasible schedule that satisfies these maximum inter-scheduling times. In particular, there must exist a schedule of links such that no two consecutive appearances of link e in the schedule are farther than keπ slots apart. This type of scheduling has been studied under the name pinwheel scheduling [28], [30] and periodic maintenance scheduling [31] with somewhat limited success. Under a total interference model where only one link can be scheduled at a time, determining whether a schedule exists for a given vector kπ is known to be NP-hard [32], [33]. To illustrate the complexity of the problem, we assume a total interference model and a fixed vector k that satisfies (33)
(for ease of notation, we drop the superscript π). Following the nomenclature in the literature, define X 1 ρ(k) ≜ (35) ke e∈E
as the density of a scheduling vector k. Because ke represents the maximum inter-scheduling time, it is larger thanP the average inter-scheduling time 1/µ̄πe . Therefore, ρ(k) ≤ e∈E µ̄e , and a necessary condition for feasibility is that ρ(k) ≤ 1. This is trivially satisfied in some cases like round-robin. The vector k = (3, 3, 3) for example has density 1 and is satisfied by the schedule {0, 1, 2}, where recall that all schedules are by definition cyclic and repeating. The vector k = (2, 4, 4) likewise has density 1 and is schedulable with {0, 1, 0, 2}. The density condition is far from sufficient, however. Consider a vector k = (2, 3, x). It is easy to verify that no matter how large a value we assign to x, no satisfying schedule exists for this vector. Because this vector has a density of 5/6 + 1/x, there is no guarantee that a schedule exists for any vector with density larger than 5/6. It has long been conjectured that all vectors with density up to 5/6 are schedulable, and this was recently proven to be true [34], though scheduling all such vectors in polynomial time remains elusive. Furthermore, density is not the only factor that affects schedulability. Consider the vector k = (3, 4, 8, 8, 8) with density 0.96. This is satisfied by the schedule {0, 1, 2, 0, 3, 1, 0, 4}. Now consider the vector k = (3, 5, 7, 8, 8), with density 0.93. While this vector appears similar and in fact has a lower density, there is no way to construct a satisfying schedule, and enumerating over all possible schedules in an effort to do so is intractable for all but the shortest schedule lengths. There are certain properties which make vectors easy to schedule, however, and algorithms exist to schedule these vectors in polynomial time. These include all vectors with density up to 1 that contain at most two distinct values [30], such as k = (4, 4, 6, 6, 6), and all vectors with density up to 1 where each value in the sorted vector is a multiple of the previous [28], [35], such as k = (2, 6, 6, 12, 12). We refer to the second class of vectors as step-down vectors following [36]. There are also a number of algorithms which apply rounding techniques to force a vector to satisfy one of the above conditions. Because values can always be rounded down without violating the inter-scheduling times in the original vector, rounding values down until the resulting vector is step-down, for example, is a valid technique. The most comprehensive of these algorithms is known as Scheduler xy, or Sxy , and can schedule all vectors with density up to 0.7 [37], plus a subset of vectors with densities larger than this value (including the three cases above). This is the closest density guarantee to the 5/6 bound of any known algorithm. To further complicate things, the discussion thus far only applies to the total interference model, where every link is mutually interfering. Under more relaxed interference models, multiple links can be scheduled per slot, which creates a more general version of the problem. In this generalized
version, a schedule must simultaneously satisfy both interscheduling times and interference constraints. We refer to the joint problem of forming independent sets and scheduling them under pinwheel constraints as the pinwheel coloring problem.
Theorem 6. (P 1) generalizes the pinwheel coloring problem, which is NP-hard.
Proof. We will show that (P 1) generalizes both pinwheel scheduling and graph coloring. Assume that each route has a length of one link so deadline constraints reduce to an upper bound on each ke , and that capacities are infinite. Then, under a total interference model, the problem reduces to finding a schedule such that the inter-scheduling time of each task is bounded by some quantity, which is precisely the pinwheel scheduling problem. Now assume that all values of τi are equal, but the conflict graph allows more than one link to be scheduled at once. Then deciding whether every link can meet its inter-scheduling time is equivalent to deciding whether the conflict graph can be colored with τi colors, which is the vertex coloring problem. Both pinwheel scheduling and vertex coloring are NP-complete, so (P 1) is NP-hard. To generate schedules efficiently in light of this result, we develop an algorithm in the next section which leverages the sets of vectors k that can be scheduled in polynomial time, while efficiently handling interference constraints. We demonstrate the algorithm’s performance through extensive simulations in Section VI. V. A LGORITHM D ESIGN In this section we design a polynomial-time algorithm which is able to solve many instances of (P 1) and the Pinwheel Coloring problem. Because the problem is NP-hard, it cannot find a supporting policy in all cases where one exists, but simulation results in the next section show that it can simultaneously achieve near-optimal throughput and tight deadlines in a variety of network scenarios. Our algorithm consists of two stages, and for ease of exposition we present them using the conflict graph representation of the network, where each node v ∈ Vc corresponds to a link in the network graph, and edges between nodes represent interference constraints. In the first stage, we construct activation sets which form a coloring of the conflict graph, so each node v ∈ Vc belongs to exactly one set. At each time step, we will activate one of these sets. Denote the set of activation sets after coloring as S, and the maximum inter-scheduling time of set s ∈ S as ks . Then the maximum inter-scheduling time of a node v in the conflict graph is equal to ks when v ∈ s. After forming S, we set ks such that it satisfies the conditions in (33) for all v ∈ s, and denote the vector of interscheduling times ks as kS . Because vectors with lower density are generally easier to schedule, our objective in the first stage
of the algorithm is to find a coloring S and corresponding kS that minimizes ρ(kS ). Explicitly, this is a solution to X 1 (P 2) : min S,kS ks s∈S
s.t. kv = ks , ∀ v ∈ s, s ∈ S, X kv ≤ τi , ∀ fi ∈ Fd ,
(36)
v∈T (i)
cv , ∀ v ∈ Vc , λv kv ∈ Z+ , ∀ v ∈ Vc , kv ≤
where we minimize P S over the set of all valid colorings of Vc , and where λv ≜ fi :v∈T (i) λi is the total traffic routed over v. After solving (P 2), the second stage of the algorithm attempts to form a satisfying schedule using the Sxy pinwheel scheduling algorithm. If the algorithm finds a satisfying schedule then it is guaranteed to support all flows in F from Corollary 5. A. Weighted Greedy Coloring We begin by addressing how to solve (P 2). This problem is NP-hard because if all values in kS are equal, it reduces to finding a minimum vertex coloring, which is a well known NPcomplete problem. To solve it efficiently, we devise a heuristic based on a greedy coloring algorithm. Let the vertices Vc be ordered in some manner which we will fix later, and assume we have a set of colors {0, 1, . . . }. For each vertex, the algorithm assigns it the smallest feasible color, i.e., the first color which does not already contain a conflicting vertex. It proceeds in order until each vertex is assigned a color. The motivation for this approach is twofold. First, it runs in O(|Vc |)2 time and so satisfies our polynomialtime objective. And second, while greedy coloring can be far from optimal in general, it tends to perform well in our setting of a conflict graph based on local interference constraints. Greedy coloring has been studied specifically under ϕ-hop interference to solve the maximum weighted independent set problem. When the connectivity graph is geometric, i.e., nodes are fixed on a plane and share a link if they are within some distance of each other, it has been shown to be a constant factor from optimal in the worst case [38]. By iteratively solving this problem with equal weights, it is easy to see that greedy is a constant factor from optimal for the unweighted coloring problem. Similarly, on random geometric graphs with chromatic number χ, it has been shown that greedy colors the graph with at most χ + 1 colors with high probability as the size of the network goes to infinity [39]. In developing our greedy algorithm, we are motivated by connectivity graphs that can be represented as geometric graphs, or behave similarly. Simulation results in the next section verify the effectiveness of this choice on a variety of graph topologies. An optimal coloring of any graph can be found by greedy when vertices are ordered correctly, simply by taking the optimal solution, ordering vertices by color, and running greedy on
that order. On the other hand, there are pathological examples where greedy uses |Vc |/2 colors to color a 2-colorable graph by using a bad ordering. Saying that greedy performs well on a graph effectively means that order does not matter, and that any arbitrary ordering yields approximately the same result for the unweighted coloring problem. However, recall that (P 2) is a weighted coloring problem, where the weight of each color s is 1/ks = maxv∈s 1/kv , which is tightly coupled to the coloring itself. Then even if the number of colors returned by greedy is largely independent of order, the weighted solution and density of the resulting vector kS may not be. Clearly if we knew the coloring and the value of the optimal kv∗ a priori for each v, then ordering vertices by k∗ would be sufficient for greedy to recover the optimal solution. To approximate this, we solve a relaxation of (P 2) for an estimate k̂, and order vertices by these values in our greedy algorithm to form activation sets S. Then with the coloring fixed, we solve the unrelaxed problem (P 2) for kS . Denote node v’s activation set after coloring as s(v), and the size of s(v) as ωv . Then the objective of (P 2) is equivalent to X 1 X 1 X 1 X 1 = = , (37) ks |s| v∈s kv ωv kv s∈S
s∈S
v∈Vc
where the first equality follows from the (P 2) constraint kv = ks , for all v ∈ s. This shows that the optimization only depends on the size of the activation sets ωv , and not on the coloring itself. To approximate the optimal ordering for greedy, we replace the objective with this representation and begin by relaxing the kv = ks constraint and the integrality condition on the vector kS . This yields the program X 1 min S,k ωv k v v∈Vc X s.t. kv ≤ τi , ∀ fi ∈ Fd , (38) v∈T (i) cv kv ≤ , ∀ v ∈ Vc , λv kv ≥ 1, ∀ v ∈ Vc . Because the solution depends only on the size of the activation sets and the vector k, we approximate the solution to (38) in the following way. We start by assuming each node is assigned its own color, and fix each ωv to an estimate ω̂v = 1, for all v ∈ Vc . When these values are fixed, the program is completely independent of S and becomes a convex program in k. We solve this program and greedily color the graph with vertices ordered by weights kv from the solution. Then, using this new coloring, we update the estimates ω̂v with the size of node v’s activation set. We repeat this process iteratively until reaching a vector of estimates ω̂ that no longer improves the solution to (38). Let SW GC denote the set of all colorings found while iterating in this way. Then we fix activation sets to those found in the previous iteration, which minimize the solution to (38) over all S ∈ SW GC .
Finally, we re-solve (P 2) for kS under this fixed S. Note that this once again enforces integrality of kS , so any solution satisfies the conditions in (33). Furthermore, note that all vertices that belong to a set s share the same inter-scheduling time ks , so the number of integer variables is reduced from |Vc | in the original problem (P 2) to |S|. This can be written as the following mixed-integer convex program, X 1 min kS ks s∈S X s.t. ni,s ks ≤ τi , ∀ fi ∈ Fd , (39) s∈S cv , ∀ v ∈ s, s ∈ S, ks ≤ λv ks ∈ Z, ∀ s ∈ S,
Algorithm 1: Weighted Greedy Coloring (WGC) Input: Conflict graph Vc , rates λ, deadlines τ , routes T , capacities c Output: Activation sets S and maximum inter-scheduling times kS 1 Set ω̂v = 1, for all v ∈ Vc ∗ 2 Set ρ = ∞, S = [] 3 Solve (38) with fixed ω = ω̂. Denote the solution as k∗ ∗ ∗ 4 while ρ(k ) < ρ do ∗ 5 Set ρ = ρ(k∗ ), S ∗ = S 6 Initialize activation set s1 = ∅, conflict set ξ1 = ∅ 7 Set S = [(s1 , ξ1 )] 8 Sort Vc by value of k∗ , from smallest to largest 9 for each v ∈ Vc do 10 Set s(v) = 0 (i) where ni,s = |s ∩ T | is the number of links in fi ’s route 11 for each i ∈ len(S) do that belong to set s. 12 if v ∈ / ξi then Greedy never uses more than ∆(Gc ) + 1 colors, so there Q∆(Gc ) 13 Add v to si are at most s=0 ks,max combinations of integer solutions. 14 Set s(v) =i Here ks,max is the largest value ks can take from slice 15 break capacity constraints, and is trivially less than the smallest if s(v) == 0 then deadline of any flow which traverses it. Therefore, when the 16 17 Initialize activation set si+1 = {v}, conflict degree of the conflict graph is bounded, this can be upper set ξi+1 = ∅ bounded by a constant, and (39) can be solved with polynomial 18 Set s(v) = i + 1 complexity. In theory, this constant upper bound can be large, 19 Append (si+1 , ξi+1 ) to S but in practice branch-and-bound and cutting plane techniques ′ 20 for v ∈ V \ v do c make modern mixed-integer solvers incredibly efficient at ′ 21 if (v, v ) ∈ Ec then solving integer programs with relatively few variables. The ′ 22 Add v to ξs(v) full Weighted Greedy Coloring (WGC) algorithm is shown in 23 for each s ∈ S do Algorithm 1. 24 for each v ∈ s do B. Schedule Construction 25 Set ω̂v = |s| Solve (38) with fixed ω = ω̂. Denote the solution Given the coloring S and scheduling vector kS returned by 26 as k∗∗ W GC, all that remains is to construct a satisfying schedule 27 Set S = S and solve (39) for kS using the state-of-the-art pinwheel scheduler Sxy . Known as a fast online scheduler, Sxy takes the vector kS as input and 28 Return S and kS either produces a schedule with a single activation set s ∈ S to be activated in each time slot, or returns false if it cannot Together, W GC and Sxy form a polynomial-time algorithm find a satisfying schedule. It determines success or failure in that takes as input a conflict graph Vc with fixed interference O(|S|2 ) time, but returns the schedule on a slot-by-slot basis constraints and link capacities c, fixed rates and deadlines because the length of the schedule can grow exponentially λ and τ , and fixed routes T for all flows. If it is able to large, and computing the entire schedule offline may not be find a feasible solution, it returns a deterministic coloring S possible in polynomial time. of the conflict graph, and a deterministic decision of which The algorithm searches for two values x and y, and aug- activation set to schedule in each time slot. Therefore, running mented values ks′ ≤ ks , for each ks in kS , such that each ks′ this algorithm in a decentralized fashion at each node generates is a power of 2 multiple of either x or y. This results in a a coordinated, conflict-free schedule that is guaranteed to partitioning X and Y , where we denote the set of values that support the set of flows F and requires no control overhead. are multiples of x as X, the vector of their inter-scheduling VI. N UMERICAL R ESULTS times as kX , and likewise for Y and kY . By construction, both of these vectors are step-down, and if In this section we evaluate the performance of our policies in a variety of scenarios, beginning with the solitary flow greedy ⌈xρ(kX )⌉ ⌈yρ(kY )⌉ + ≤ 1, (40) policy. x y then the algorithm returns a satisfying schedule. We omit A. Solitary Flow Greedy Policy the full details of the algorithm and encourage readers to Recall that for a solitary flow under total interference and reference [37] for complete details. bottleneck slice widths, the greedy policy in Corollary 4 was
Fig. 3: Histogram of solitary flow greedy delay ratios ζ shown to be optimal, and we conjectured that it is nearoptimal for any value of ϕ. Furthermore, we showed an approximate bound for the maximum delay seen under a greedy policy based on the idea that the policy will never let a queue grow too much larger than its slice width. Denote the actual maximum packet delay observed after running greedy as τ̂ (greedy), and define the greedy delay ratio λτ̂ (greedy) ζ≜ P ′ e∈T we
(41)
as the ratio of this value to the approximate bound on τ ∗ (greedy, w′ , λ) in (25). In Figure 3, we show a histogram of ζ seen after running greedy under a variety of different slice widths and interference models. Using a route with a length of 6 hops, we varied the value of ϕ from 1 (primary interference) to 5 (total interference). For each value of ϕ, we generated 30, 000 random sets of slice widths. For the first third of the sets, we drew values of w from a normal distribution with a mean of 55 and standard deviation of 15. For the second third, we drew from a uniform distribution on the interval [10, 100], and for the final third we drew from a bimodal distribution, with values normally distributed around 20 with probability 0.5 and normally distributed around 100 otherwise. For each set of slice widths, we computed the maximum rate λ∗ (w) and the bottleneck slice widths w′ ≤ w. Figure 3 shows a histogram of the greedy delay ratio for the combined data with rate λ∗ (w) under these bottleneck slices. In the total interference case, nearly all of the histogram mass is below 1, indicating that the bound is close to being exact when greedy is optimal. As the value of ϕ decreases, we expect more instances to arise where greedy is not optimal as discussed in Section III, and we see a corresponding increase in both mean and variance of ζ. Nevertheless, even under primary interference the ratio remains close to 1. This reinforces greedy as a good heuristic for minimizing deadlines under any value of ϕ. B. Weighted Greedy Coloring Next we turn to simulating the W GC + Sxy algorithm. In an effort to demonstrate the versatility and performance of the algorithm, we show results for a variety of network topologies and traffic patterns. We will also show results comparing it to
Fig. 4: Average feasibility regions for a sink tree topology with depth 3 and degree 4 (top), a 4x4 mesh grid (middle), and random topologies generated by randomly failing links in a 4x4 mesh grid with probability p = 0.25 (bottom). the Credit-Based Heuristic (CBH) algorithm from [27], which is the best known algorithm for meeting deadlines in multihop wireless networks with interference and fixed arrivals. Our results show that we are able to significantly improve on the CBH algorithm and meet deadlines on the order of milliseconds over multiple hops, while remaining close to throughput optimality. For ease of exposition, in each experiment we set rates and deadlines equal to the same λ and τ respectively across all flows, and we generate 32 flows with random source/destination pairs unless otherwise specified. We set the duration of each time slot to be 125µs, which is the smallest time slot typically used by data in the 5G standard [40]. The CBH algorithm assumes that all rates are integer-valued, so for the most accurate comparison we round each rate to the nearest integer when comparing our results to CBH. In each
plot, we show the average of 200 random instances, where the randomness is over the flow generation and topology (when random). This is a sufficiently large sample so that the values shown are within 5% of the true value with 95% confidence. Under primary interference (ϕ = 1), we are able to compute the throughput-optimal λ∗ independent of deadlines in polynomial time, using the well-known algorithm from Hajek and Sasaki [7]. In many of our experiments, we normalize the achievable rates under each algorithm by λ∗ , so that if an algorithm achieves a normalized rate of 1 for a given deadline τ , it means that this deadline can be achieved without any loss in throughput. The (λ, τ ) feasibility curve shows the loss in throughput as deadlines become more strict. Note that even as deadlines become large, our algorithm may not be able to achieve throughput optimality because the W GC algorithm forces each link to belong to a single activation set. Recall that our algorithm takes as input a set of flows with known rates and deadlines, and attempts to find a feasible schedule to simultaneously satisfy all service guarantees. If an algorithm is able to find such a schedule for a given (λ, τ ) pair, then that pair lies within the feasibility region for that algorithm. In Figure 4, we show the (λ, τ ) feasibility region under each algorithm and for several different topologies and traffic patterns with ϕ = 1. The top of the figure shows results for a sink-tree topology with depth 3, degree 4, and a single flow arriving at each leaf. This makes the traffic highly symmetric and amenable to the CBH algorithm, which performs best under tree topologies. As a result, CBH is able to achieve throughput optimality for all deadlines above ≈ 10ms. W GC + Sxy is able to do the same, however, for deadlines above ≈ 2.5ms. This shows that our algorithm is able to take similar advantage of the symmetry and guarantee throughput optimality with less than 1ms of latency per hop. W GC combined with a simple roundrobin schedule is able to achieve the same deadlines but only about 75% of the optimal throughput. In the middle figure, we show results for a 4x4 mesh grid topology and 32 flows with random source/destination pairs. W GC + Sxy can achieve significantly tighter deadlines and higher throughput in this setting compared to CBH. The bottom figure shows similar results for a random topology, where we start with a 4x4 mesh grid and allow links to fail independently with probability p = 0.25 (repeating this process if the resulting graph is not connected). As topologies and traffic flow become less symmetric, W GC + Sxy is able to handle this gracefully and the performance gap increases significantly between W GC + Sxy and the other policies. We next examine how the interference model affects performance. In Figure 5, we show the feasibility regions for a 4x4 mesh grid under ϕ-hop interference for varying values of ϕ. All rates are normalized with respect to the value of λ∗ under ϕ = 1, so the comparison shown in each plot is the relative achievable rate across values of ϕ. Naturally, as ϕ increases, both achievable rates and deadlines suffer as fewer links are able to be activated in each slot. Once again, the performance of W GC + Sxy shows significant improvement over CBH
Fig. 5: Average feasibility regions for a 4x4 mesh grid topology and varying values of ϕ, showing the performance of W GC + Sxy (top) and CBH (bottom). All rates are normalized with respect to the optimal λ∗ when ϕ = 1.
Fig. 6: Average feasible normalized rate for a 4x4 mesh grid with ϕ = 1, where each link is on iid with probability p, and with varying deadlines. The solid curves show the performance of W GC + Sxy and the dashed curves show the performance of CBH. under any value of ϕ. We observed in Figure 4 that when links randomly fail in a 4x4 mesh grid, the performance of each algorithm suffers. Figure 6 shows the change in performance as topologies become less structured and more random, with solid curves representing W GC + Sxy and dashed curves representing CBH. We start with a 4x4 mesh grid, and determine whether each link is active iid with some probability p. We again
Fig. 7: Average feasible normalized rate for a 4x4 mesh grid with ϕ = 1, and with varying number of flows and deadlines. The rates are normalized separately for each set of flows, so the performance dropoff is not due to network saturation but rather scheduling limitations. The solid curves show the performance of W GC + Sxy and the dashed curves show the performance of CBH. plot the normalized rate for each algorithm and three different deadline values as we sweep p from 0.5 to 1. When p = 1, we recover the 4x4 mesh grid, and as p becomes smaller, the topology becomes less structured. In any instance, if the resulting topology is not connected, we regenerate the topology. The figure shows that each algorithm improves with more structure in the topology, but for deadlines above 10ms, the change in performance for W GC + Sxy is negligible, showing its versatility under any network topology. Finally, we examine how the number of flows and different service guarantees that must be met simultaneously affect performance. In Figure 7, we plot the normalized rate as a function of the number of flows, again denoting W GC + Sxy with solid curves and CBH with dashed curves. We show results for a 4x4 mesh grid topology and normalize rates separately for each instance, so that any performance dropoff as the number of flows increases is not due to network saturation, but rather the ability to schedule more flows simultaneously. The performance of each algorithm drops off as the number of flows increases, as it becomes harder to satisfy deadlines for more unique source/destination pairs, but once again the dropoff is small under W GC +Sxy for deadlines above 10ms. Each of these results shows the ability of W GC + Sxy to meet tight deadlines on the order of milliseconds across multiple hops in wireless networks with general topology, interference, and traffic patterns. Moreover, our algorithm is able to meet these deadlines while achieving near-optimal throughput in many cases. It accomplishes this in polynomial time and determines offline whether a network can support a given set of flows, making it a significant step forward in scheduling to meet tight deadlines in wireless networks with interference.
VII. C ONCLUSION In this paper, we analyzed the impact of wireless interference on scheduling for service guarantees. We defined throughput- and deadline-optimal policies for a solitary flow, and showed that even when queues are stable, packets can experience large delay. To alleviate this problem, we derived conditions on end-to-end delays in terms of inter-scheduling times, and showed that we can meet tight deadline guarantees under any interference model by solving a generalized version of pinwheel scheduling. Finally, we developed a heuristic algorithm to solve this problem in polynomial time, which can achieve deadlines on the order of milliseconds and nearoptimal throughput under arbitrary network topologies and traffic patterns. Future work includes optimizing routing as well as scheduling, and expanding our policy to support unreliable links, changing wireless topologies, and stochastic traffic. A PPENDIX A. Proof of Theorem 1 We start by showing that a policy π ′ supports F if and only if at most λi τi packets from fi are present in the system at the end of each slot. To show the forward direction, recall that arrival rates are fixed on the interval 0 ≤ t ≤ T , so exactly λi packets of fi arrive in each slot. Packets are served in a FCFS manner, so all packets must have arrived in the last τi slots. Similarly, if there were more than λi τi packets, then at least one must have arrived prior to the last τi slots, so the condition is both necessary and sufficient. Define the state of the system at time t under a supporting ′ policy π ′ as the length of each queue and denote it by Qπ (t). Queue lengths are bounded by the argument above, and there exists a finite number of states which can be visited over any time horizon T . In particular, for sufficiently large T , there ′ must exist a state Qπ (t0 ) which occurs at time t0 and then ′ occurs again at time t0 + K for some K > 0. Let Qπ (t0 ) be the first state where this event occurs, and let the set of actions taken in the time interval [t0 , t0 + K) be the policy ′ π with K π = K and µπ (t) = µπ (t − t0 ) mod K π + t0 for all t ≥ 0. Then for all t0 ≤ t ≤ T , we have Qπ (t) = ′ Qπ (t − t0 ) mod K π + t0 , so (6) holds and π supports F for all t0 ≤ t ≤ T . Note that t0 > 0 because queues are empty at t = 0 and the system requires time to “ramp up”. However, we next show that π supports F on the interval 0 ≤ t < t0 using induction on the queue sizes. The queue evolution equations are given by Qπi,e (t + 1) = min{Qπi,e (t) + λ̃i,e (t) − µπe (t)wi,e , 0}, (42) for all 0 ≤ t ≤ T , where ( λi , λ̃i,e (t) = µπe−1 (t) · min{wi,e−1 , Qπi,e−1 (t)},
(i)
e = T0 , (i) e ̸= T0 , (43) and with a slight abuse of notation we denote the link preceding e in T (i) as e−1 , where it is understood we are
referring to fi . Now assume that Qπi,e (t) ≤ Qπi,e (t + K π ) for all i and e. Then, from the queue evolution equations and given that µπ (t) = µπ (t + K π ), this implies that Qπi,e (t + 1) ≤ Qπi,e (t + K π + 1) for all i and e as well. By definition, Qπi,e (0) ≤ Qπi,e (K π ) for all i and e, which completes the induction step. Therefore, X X Qπi,e (t) ≤ Qπi,e (t + nK π ) ≤ λi τi (44) e∈T (i)
e∈T (i)
for all fi and 0 ≤ t < t0 , and some n > 0 such that t0 ≤ t + nK π < t0 + K π , which shows that π supports F on the interval 0 ≤ t < t0 . It can easily be shown that π also supports F on the interval t > T . Assume for all t > T , dummy packets arrive with the same rate λi for each flow, until all real packets have been delivered. Then, because π supports every flow under regular arrivals, it must also support every flow under the dummy arrivals. This completes the proof. B. Proof of Corollary 1 We show this by contradiction. Assume µ̄πe < λi wi,e for some fi and e ∈ T (i) , so equivalently µ̄πe K π wi,e = ηeπ wi,e < λi K π .
(45)
Recall that ηeπ is the number of times a link is scheduled in a scheduling period, and each time it serves min{wi,e , Qi,e (t)} packets. Then the total number of packets served by link e in any period is at most the left-hand side of (45), while the right-hand side is the total number of packets that arrive to the network in that period. Therefore, after one period, the total number of fi packets in flight from the source to link e is at least the difference in these quantities. Because the inequality is strict, this must be at least as large as some ϵ > 0. This holds for each scheduling period, so after Ω scheduling periods, the total number of fi packets in flight is at least ϵΩ. Now let Ω → ∞, so this quantity also goes to infinity because ϵ is strictly positive. In order for a policy to support F, all queue sizes must be bounded by a finite constant, else the policy cannot meet any finite deadline. There are a finite number of queues along T (i) , so at least one of them must also grow without bound, which is a contradiction. C. Proof of Theorem 3 The ORR policy schedules links in order from source to destination in subsequent time slots according to the definition above. The activation rate follows because each link is only activated once per scheduling period. Now assume a packet arrives at the source at some time t, and that slice widths are large enough to serve all enqueued packets when a link is scheduled. This is non-restrictive because τi∗ is defined as the smallest feasible deadline for an arbitrarily small throughput. (i) At time t mod (ϕ + 1), the packet is served at link T0 , and following the ORR schedule, it is served at each subsequent link in the next |T (i) | − 1 slots. In the worst case, the packet must wait ϕ slots at the source before being served, so it spends
a maximum of |T (i) | + ϕ slots in the network, which verifies τi∗ for the ORR policy. It remains to show that no other policy can achieve a smaller deadline for all packets. Recall that only one of (i) (i) {T0 , . . . , Tϕ } can be scheduled in the same slot. We claim that it must take at least some packets 2ϕ + 1 slots to reach (i) link Tϕ+1 . The fewest slots a packet can take is ϕ + 1, so we define ∆(t) as the number of additional slots it takes beyond this minimum for packets which arrive at the source at time t. Then if ∆(t) ≥ ϕ for any t, our claim must hold. Note that ∆(t) = 0 at time t when packets arrive, and it is incremented by one each time a scheduling decision is made that does not schedule those packets. Assume our claim does not hold, i.e., that ∆(t) < ϕ for all t. First note that packets which arrive at t can allow at most ∆(t) slots of arrivals behind them to “catch up”. We say a slot of arrivals t + j is caught up to t if it is enqueued at the same link as the slot of arrivals t. Each slot of arrivals which catches up to t increments ∆(t), so arrivals from slot t + ϕ cannot be caught up to t under our assumption on ∆(t). Let t + j ∗ ≤ t + ϕ be the first slot which is not caught up to t (i) when packets from slot t reach Tϕ+1 . Because the previous slot of arrivals is caught up to t, it must have been scheduled ϕ times independently of the arrivals from slot t+j ∗ . Therefore, ∆(t+j ∗ ) ≥ ϕ, which is a contradiction. This proves the result. D. Proof of Corollary 4 In any policy with bottleneck slice widths, a link e must serve a full slice width of packets each time it is scheduled (after the ramp-up period). If not, it would serve fewer than ηe we = λK π packets per scheduling period, and the queue would become unstable. Therefore the first condition of greedy must always hold for at least one link e after the ramp-up period. Now assume there are two queues which are “full,” i.e., contain at least a slice width of packets at time t, and denote them as links e and e′ respectively. Without loss of generality let link e′ be the closest full queue to the destination, and assume that link e is scheduled at t. We will show that this cannot be optimal by contradiction. When link e is served, we packets are served to the next queue in the route, but remain behind the packets already queued at link e′ . Future actions are taken, and at some point t′ > t, link e′ is scheduled. No queues could have changed between link e′ and the destination on the interval [t, t′ ), because only full queues can be served. Furthermore, because Qe′ was already full at time t and queues are FCFS, only the packets which would have been served at t are now served at t′ . If link e′ is not the destination link, then the state of the system after t′ is exactly the same as if link e′ had been scheduled at time t, and the actions in the interval [t, t′ ) were all delayed by one slot. If link e′ is the destination link, then the we′ packets served by link e′ could have arrived at their destination sooner had link e′ been scheduled at t. Therefore, it could not have been optimal to serve link e, which is a contradiction.
Bounding the exact value of τ ∗ (greedy, w′ , λ) is challenging because the scheduling decisions at each step of greedy depend on the state of the queues, which creates a recursive relationship. We can approximate τ ∗ by observing that Qe is never allowed to grow much larger than we′ before being served, and that if link e is scheduled, the subse′ quent queue Qe+1 smaller than we+1 . Therefore P P is strictly ′ Q (t) ≲ w at any time t, and the result follows e e e∈T e∈T from Corollary 2. E. Proof of Theorem 4 Assume without loss of generality that slices have bottleneck slice widths. Allowing slice widths to be larger than this can only decrease packet delay, so this assumption is not only non-restrictive but necessary. Under bottleneck slice widths, µ̄πi,e wi,e = λi for all fi ∈ F and e ∈ T (i) by definition, so the total number of fi packets served in each period in steady state is ηeπ wi,e = µ̄πi,e wi,e K π = λi K π . Because this many packets are served at each link, this is the number of arrivals each subsequent link sees per scheduling period, as well as the number of arrivals at the source link. Assume that Qi,e (t) = 0 at some time t. Then because it serves the same number of packets as arrivals within each scheduling period, the queue must be emptied again at some time ti,e (t) ≤ t+K π . By induction, the queue must be emptied at least once per scheduling period if it is ever empty. Assume that before the network reaches steady-state, dummy packets are added to each queue so that links still serve a full slice width. Because queues are initialized to zero, this completes the induction step. Let ti,e be any time slot when Qi,e (ti,e ) = 0. Because link e is scheduled ηe times per scheduling period and serves a full wi,e packets each time, the maximum delay that packets can experience at link e occurs when link e is scheduled the ηe time slots leading up to time ti,e , regardless of when packets arrived. Now consider the next link e + 1 in the route, and let ti,e+1 be the first time slot after ti,e where Qi,e+1 (ti,e+1 ) = 0. Just like link e, the maximum delay packets can experience occurs when e + 1 is scheduled in ηe+1 consecutive slots leading up to time ti,e+1 , and where the λi K π packets from link e arrive in the interval ti,e+1 − K π < t ≤ ti,e+1 . In particular, the worst-case delay occurs when link e + 1 begins receiving packets from link e at time ti,e+1 − K π + 1, immediately after Qi,e+1 becomes empty. The same holds for each link in T (i) , and so the worst-case delay occurs when links are scheduled in blocks such that each link e begins scheduling its block immediately after link e + 1 finishes scheduling. This is a valid schedule with bottleneck links under any ϕ. To see this, consider any set of ϕ + 1 consecutive links Pϕ {e, . . . , e+ϕ}. From interference constraints, j=0 µ̄e+j ≤ 1, and each link e′ is part of at least one set of ϕ + 1 consecutive links where this bound is tight. If not, µ̄e′ could be increased and wi,e′ could be decreased, which contradicts our bottleneck slice assumption. Then for each set of ϕ + 1 links, scheduling blocks in reverse order of packet flow fills the entire scheduling
period and satisfies activation rates. When two such sets of links overlap or adjoin, the schedule for each block is shifted so the pattern holds for all sets of ϕ + 1 links. Because packets are scheduled in blocks, we consider the first and last packet in each block. Denote the time the first packet arrives at the source as t(s0 ) and the time the last packet in the block arrives at the source as t(s−1 ) = t(s0 ) + K π − 1. Similarly, denote the time the first packet is delivered to its destination as t(d0 ) and the time the last packet is delivered as t(d−1 ) = t(d0 ) + η−1 − 1 < t(d0 ) + K π − 1, where link −1 is the destination link. The total delay seen by the first packet is therefore larger than the last packet, and because all intermediate packets see a gradient of delay between these two values, the first packet sees the largest delay. This packet is the first served in each block, so at each link e it sees a delay of K π − ηeπ = K π (1 − µ̄πe ) before being served. Summing over the route yields the result. This bound is tight for at least one policy by construction of the policy just described. We say that there are many policies where τi∗ grows linearly with K π , because any policy which schedules links in blocks incurs a delay at each link that is linear in K π . In fact, from Lemma 1, any policy with interscheduling times that depend on the schedule length incurs such a delay. F. Proof of Lemma 2 We will show this by induction, by first showing that if packets arrive at link e with delay deficit less than or equal to zero, then whenever they arrive at the next link in the route, their delay deficit will also be at most zero. Let Qi,e have a counter which tracks the number of packets with strictly positive delay deficit. Because δ l (t) ≤ 0 for all packets l by assumption, no packets are added to the counter on arrival. Of the packets already in the queue, (30) shows that a strictlyPpositive delay deficit implies that a packet’s age al (t) > T̃ (l) keπ at time t. Because λi packets arrive at the source in each time slot, at most λi new packets can exceed this bound in each slot, so at most λi packets are added to the counter in each slot. Next we claim that when link e is scheduled, it serves all packets with positive delay deficits. Assume this is true at some slot t when link e is scheduled. Then due to the maximum inter-scheduling time, it must be scheduled again within the next keπ slots. We just saw that at most λi packets can be added to the counter in each slot, so at most λi keπ packets can have positive delay deficit the next time link e is scheduled. This is a lower bound on the allowable slice width, so all these packets are again served. The first time that link e is scheduled, there can be no more than λi keπ packets in the network, so it necessarily serves all packets with positive delay deficits, and this completes the induction step. Therefore, every packet enqueued at link e is served no later than the first time that link e is scheduled after its delay deficit becomes positive. Because the link is scheduled at least every keπ slots, the delay deficit of any packet is at most keπ when it is served. This is exactly the delay quota of link e, so no
packet can have a delay deficit larger than zero when it arrives at the next link in its route. By definition, packets arrive at the source link with a delay deficit of zero, which completes the induction step and the proof. R EFERENCES [1] T-mobile launches first-ever 5g network slicing beta for developers. Accessed: 03-21-2024. [Online]. Available: https://www.t-mobile.com/news/network/ t-mobile-launches-first-ever-5g-network-slicing-beta-for-developers [2] Quality of service (qos) in 5g networks. Accessed: 03-21-2024. [Online]. Available: https://5ghub.us/quality-of-service-qos-in-5g-networks/ [3] L. Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks,” in 29th IEEE Conference on Decision and Control. IEEE, 1990, pp. 2130–2132. [4] Y. Gu, B. Liu, and X. Shen, “Asymptotically optimal online scheduling with arbitrary hard deadlines in multi-hop communication networks,” IEEE/ACM Transactions on Networking, vol. 29, no. 4, pp. 1452–1466, 2021. [5] C. Tsanikidis and J. Ghaderi, “Scheduling Stochastic Traffic With End-to-End Deadlines in Multi-hop Wireless Networks,” in IEEE INFOCOM 2024 - IEEE Conference on Computer Communications. Vancouver, BC, Canada: IEEE, May 2024, pp. 651–660. [Online]. Available: https://ieeexplore.ieee.org/document/10621239/ [6] K. Jain, J. Padhye, V. N. Padmanabhan, and L. Qiu, “Impact of interference on multi-hop wireless network performance,” in Proceedings of the 9th annual international conference on Mobile computing and networking, 2003, pp. 66–80. [7] B. Hajek and G. Sasaki, “Link scheduling in polynomial time,” IEEE Transactions on Information Theory, vol. 34, no. 5, pp. 910–917, Sep. 1988. [8] M. Kodialam and T. Nandagopal, “Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem,” in Proceedings of the 9th annual international conference on Mobile computing and networking, 2003, pp. 42–54. [9] R. L. Cruz, “A calculus for network delay. i. network elements in isolation,” IEEE Transactions on information theory, vol. 37, no. 1, pp. 114–131, 1991. [10] ——, “A calculus for network delay. ii. network analysis,” IEEE Transactions on information theory, vol. 37, no. 1, pp. 132–141, 1991. [11] M. Fidler, “An end-to-end probabilistic network calculus with moment generating functions,” in 200614th IEEE International Workshop on Quality of Service. IEEE, 2006, pp. 261–270. [12] A. Burchard, J. Liebeherr, and S. D. Patek, “A min-plus calculus for endto-end statistical service guarantees,” IEEE Transactions on Information Theory, vol. 52, no. 9, pp. 4105–4114, 2006. [13] C. Li, A. Burchard, and J. Liebeherr, “A network calculus with effective bandwidth,” IEEE/ACM Transactions on Networking, vol. 15, no. 6, pp. 1442–1453, 2007. [14] H. Al-Zubaidy, J. Liebeherr, and A. Burchard, “A (min,×) network calculus for multi-hop fading channels,” in 2013 Proceedings IEEE INFOCOM. IEEE, 2013, pp. 1833–1841. [15] I.-H. Hou, V. Borkar, and P. Kumar, A theory of QoS for wireless. IEEE, 2009. [16] I.-H. Hou and P. Kumar, “Utility-optimal scheduling in time-varying wireless networks with delay constraints,” in Proceedings of the eleventh ACM international symposium on Mobile ad hoc networking and computing, 2010, pp. 31–40. [17] I.-H. Hou, “Scheduling heterogeneous real-time traffic over fading wireless channels,” IEEE/ACM Transactions on Networking, vol. 22, no. 5, pp. 1631–1644, 2013. [18] R. Li and A. Eryilmaz, “Scheduling for end-to-end deadline-constrained traffic with reliability requirements in multihop networks,” IEEE/ACM Transactions on Networking, vol. 20, no. 5, pp. 1649–1662, 2012. [19] X. Liu, W. Wang, and L. Ying, “Spatial–temporal routing for supporting end-to-end hard deadlines in multi-hop networks,” Performance Evaluation, vol. 135, p. 102007, 2019. [20] R. Singh and P. Kumar, “Throughput optimal decentralized scheduling of multihop networks with end-to-end deadline constraints: Unreliable links,” IEEE Transactions on Automatic Control, vol. 64, no. 1, pp. 127–142, 2018.
[21] ——, “Adaptive csma for decentralized scheduling of multi-hop networks with end-to-end deadline constraints,” IEEE/ACM Transactions on Networking, vol. 29, no. 3, pp. 1224–1237, 2021. [22] P. Djukic and S. Valaee, “Quality-of-service provisioning for multiservice tdma mesh networks,” in Managing Traffic Performance in Converged Networks: 20th International Teletraffic Congress, ITC20 2007, Ottawa, Canada, June 17-21, 2007. Proceedings. Springer, 2007, pp. 841–852. [23] ——, “Delay Aware Link Scheduling for Multi-Hop TDMA Wireless Networks,” IEEE/ACM Transactions on Networking, vol. 17, no. 3, pp. 870–883, Jun. 2009. [24] P. Cappanera, L. Lenzini, A. Lori, G. Stea, and G. Vaglini, “Link scheduling with end-to-end delay constraints in Wireless Mesh Networks,” in 2009 IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks & Workshops. Kos, Greece: IEEE, Jun. 2009, pp. 1–9. [25] ——, “Efficient link scheduling for online admission control of real-time traffic in wireless mesh networks,” Computer Communications, vol. 34, no. 8, pp. 922–934, Jun. 2011. [26] ——, “Optimal joint routing and link scheduling for real-time traffic in TDMA Wireless Mesh Networks,” Computer Networks, vol. 57, no. 11, pp. 2301–2312, Aug. 2013. [27] S. Chilukuri and A. Sahoo, “Delay-aware TDMA Scheduling for MultiHop Wireless Networks,” in Proceedings of the 16th International Conference on Distributed Computing and Networking. Goa India: ACM, Jan. 2015, pp. 1–10. [28] R. Holte, A. Mok, L. Rosier, I. Tulchinsky, and D. Varvel, “The pinwheel: A real-time scheduling problem,” in Proceedings of the 22nd Hawaii International Conference of System Science, 1989, pp. 693–702. [29] N. Jones and E. Modiano, “Optimal Slicing and Scheduling with Service Guarantees in Multi-Hop Wireless Networks,” in Proceedings of the Twenty-fifth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing. Athens Greece: ACM, Oct. 2024, pp. 181–190. [Online]. Available: https://dl.acm.org/doi/10.1145/3641512.3686385 [30] R. Holte, L. Rosier, I. Tulchinsky, and D. Varvel, “Pinwheel scheduling with two distinct numbers,” Theoretical Computer Science, vol. 100, no. 1, pp. 105–135, 1992. [31] W. D. Wei and C. L. Liu, “ON A PERIODIC MAINTENANCE PROBLEM,” vol. 2, no. 2, 1983. [32] A. Mok, L. Rosier, I. Tulchinsky, and D. Varvel, “Algorithms and complexity of the periodic maintenance problem,” Microprocessing and Microprogramming, vol. 27, no. 1-5, pp. 657–664, Aug. 1989. [33] A. Bar-Noy, R. Bhatia, J. S. Naor, and B. Schieber, “Minimizing Service and Operation Costs of Periodic Scheduling,” Mathematics of Operations Research, vol. 27, no. 3, pp. 518–544, Aug. 2002. [34] A. Kawamura, “Proof of the Density Threshold Conjecture for Pinwheel Scheduling,” in Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Vancouver BC Canada: ACM, Jun. 2024, pp. 1816–1819. [35] M. Y. Chan and F. Chin, “Schedulers for larger classes of pinwheel instances,” Algorithmica, vol. 9, no. 5, pp. 425–462, May 1993. [Online]. Available: http://link.springer.com/10.1007/BF01187034 [36] C. Li, Q. Liu, S. Li, Y. Chen, Y. T. Hou, and W. Lou, “On Scheduling with AoI Violation Tolerance,” in IEEE INFOCOM 2021 - IEEE Conference on Computer Communications. Vancouver, BC, Canada: IEEE, May 2021, pp. 1–9. [37] M. Chan and F. Chin, “General schedulers for the pinwheel problem based on double-integer reduction,” IEEE Transactions on Computers, vol. 41, no. 6, pp. 755–768, Jun. 1992. [38] G. Sharma, R. R. Mazumdar, and N. B. Shroff, “On the complexity of scheduling in wireless networks,” in Proceedings of the 12th annual international conference on Mobile computing and networking, 2006, pp. 227–238. [39] C. Mcdiarmid and T. Müller, “On the chromatic number of random geometric graphs,” Combinatorica (Budapest. 1981), vol. 31, no. 4, pp. 423–488, 2011. [40] 3rd Generation Partnership Project (3GPP), “NR; Physical channels and modulation,” ETSI, Tech. Rep. TS 138 211 V17.5.0, Dec. 2023, release 17. [Online]. Available: https://www.etsi.org/deliver/etsi ts/138200 138299/138211/