Joint Scheduling of URLLC and eMBB Traffic in 5G Wireless Networks

I Introduction

An important requirement for 5G wireless systems is its ability to efficiently support both broadband and ultra reliable low-latency communications. On one hand enhanced Mobile Broadband (eMBB) might require gigabit per second data rates (based on a bandwidth of several 100 MHz) and a moderate latency (a few milliseconds). On the other hand, Ultra Reliable Low Latency Communication (URLLC) traffic requires extremely low delays (0.25-0.3 msec/packet) with very high reliability (99.999%) . To satisfy these heterogenous requirements, the 3GPP standards body has proposed an innovative superposition/puncturing framework for multiplexing URLLC and eMBB traffic in 5G cellular systemsAn earlier version of this work appears in the Proceedings of IEEE Infocom 2018, Honolulu, HI, ..

The proposed scheduling framework has the following structure . As with current cellular systems, time is divided into slots, with a proposed one millisecond (msec) slot duration. Within each slot, eMBB traffic can share the bandwidth over the time-frequency plane (see Figure 1). The sharing mechanism can be opportunistic (based on the channel states of various users); however, the eMBB shares are decided by the beginning, and fixed for the duration of a slotThe sharing granularity among various eMBB users is at the level of Resource Blocks (RB), which are small time-frequency rectangles within a slot. In LTE today, these are (1 msec $\times$ 180 KHz), and could be smaller for 5G systems.. Further the new framework also allows aggregation of eMBB slots where transmissions to an eMBB user over consecutive slots are coded together to achieve better coding gains resulting from long codewords while reducing overheads due to control signals. This results in better spectral efficiency as compared to the OFDMA frame structure of LTE .

URLLC downlink packets may arrive during an ongoing eMBB transmission; if tight latency constraints are to be satisfied, they cannot be queued until the next slot. Instead each eMBB slot is divided into minislots, each of which has a 0.125 msec durationIn 3GPP, the formal term for a ‘slot’ is eMBB TTI, and a ‘minislot’ is a URLLC TTI, where TTI expands to Transmit Time Interval.. Thus upon arrival URLLC packets can be immediately scheduled in the next minislot on top of the ongoing eMBB transmissions. If the Base Station (BS) chooses non-zero transmission powers for both eMBB and overlapping URLLC traffic, then this is referred to as superposition. If eMBB transmissions are allocated zero power when URLLC traffic is overlapped, then it is referred to as puncturing of eMBB transmissions. To achieve high reliability URLLC transmissions are by design protected through coding and HARQ if necessary. At the end of an eMBB slot, the BS can signal eMBB users the locations, if any, of URLLC superposition/puncturing. eMBB users can then use this information to decode transmissions, with some possible loss of rate depending on the amount of URLLC overlap. See for additional details.

A key problem in this setting is the joint scheduling of eMBB and URLLC traffic over two time-scales. At the slot boundary, resources are allocated to eMBB users (with possible aggregation of slots) based on their channel states and utilities, in effect, allocating long term rates to optimize high-level goals (e.g. utility optimization). Meanwhile, at each minislot boundary, the (stochastic) URLLC demands are placed onto previously scheduled and ongoing eMBB transmissions. Decisions on the placement of such overlaps across scheduled eMBB user(s) will impact the rates they will see on that slot. Thus we have a coupled problem of jointly optimizing the scheduling of eMBB users on slots with the placement of URLLC demands across minislots.

This paper is, to our knowledge, the first to formalize and solve the joint eMBB/URLLC scheduling problem described above. We consider various models for the eMBB rate loss associated with URLLC superposition/puncturing, for which we characterize the associated feasible throughput regions and propose online joint scheduling algorithms as detailed below.

Linear Model: When the rate loss to eMBB is directly proportional to the fraction of superposed/punctured minislots, we show that the joint optimal scheduler has a nice decomposition. Despite having non-linear utility functions and time-varying channel states, the stochastic URLLC traffic can be uniform-randomly placed in each minislot, while the eMBB scheduler can be scheduled via a greedy iterative gradient algorithm that only accounts for the expected rate loss due to the URLLC traffic.

Convex Model: For more general settings where the rate loss can be modeled by a convex function, the solution does not have the decomposition property as in the linear model and hence, the finding the optimal solution is challenging. Therefore, we restrict to a simpler class of joint scheduling policies called as minislot-homogeneous joint scheduling policies where the URLLC placement policy does not change across the minislots in an eMBB slot. In this setting, we characterize the capacity region and derive concavity conditions under which we can derive the effective rate seen by eMBB users (post-puncturing by URLLC traffic). We then develop a stochastic approximation algorithm which jointly schedules eMBB and URLLC traffic, and show that it asymptotically maximizes the utility for eMBB users while satisfying URLLC demands. We also show that for convex functions which are homogeneous, minislot-homogeneous joint scheduling policies are optimal within the larger class of causal and non-anticipative joint scheduling policies. Further for the convex loss model, we show that it is better to schedule eMBB users to share bandwidth (i.e. slice across frequency, see also Fig. 4), and let each user occupy the entire slot duration to mitigate rate loss due to URLLC puncturing.

Threshold Model: Finally we consider a loss model, where eMBB traffic is unaffected by puncturing until a threshold is reached; beyond this threshold it suffers complete throughput loss (a 0-1 rate loss model). We consider two broad classes of minislot homogeneous policies, where the URLLC traffic is placed in minislots in proportion to the eMBB resource allocations (Rate Proportional (RP)) or eMBB loss thresholds (Threshold Proportional (TP)). We motivate these policies (e.g. TP minimizes the probability of any eMBB loss in an eMBB slot) and derive the associated throughput regions. Finally, we utilize the additional structure underlying the RP and TP Placement policies along with the shape of the threshold loss function to derive fast gradient algorithms that converge and provably maximize utility.

I-B Related Work

Resource allocation, utility maximization and opportunistic scheduling for downlink wireless systems have been intensely studied in the last two decades, and have had a major impact on cellular standards. We refer to for a survey of the key results. In this paper, we focus on joint scheduling of URLLC and eMBB traffic. From an application point of view, there have been several studies arguing for the need to support URLLC services (e.g. for industrial automation) .

With demand of both broadband and low-latency services growing, there has been rapid developments in the 5G standardization efforts in 3GPP. Of key relevance to this paper, the 3GPP RAN WG1 has focused on standardizing slot structure for eMBB and URLLC, and have been evaluating signaling and control channels to support superposition and puncturing in recent meetings . We specifically refer the reader to Sections 8.1.1.3.4 – 8.1.1.3.6 in for current proposals.

Beyond standards, recent work has focused on system level design for such systems (overheads, packet sizes, control channel structure, etc.) . Of particular note, argues (based on system level simulation and queuing models) that statically partitioning bandwidth between eMBB and URLLC is very inefficient. There have also been several studies focusing on physical layer aspects of URLLC (coding and modulation, fading, link budget) .

Efficient sharing of radio resources between eMBB and URLLC traffic has been discussed in literature, see . In , the authors have considered joint optimization of resource allocation for eMBB and URLLC traffic. However, they do not use puncturing/superposition mechanisms to share resources. Some works () use information theoretic results to obtain expressions for the average eMBB rates under URLLC puncturing for various decoding schemes for uplink eMBB traffic punctured/superposed by URLLC users. However, they do not consider the design of joint scheduling algorithms for eMBB and URLLC traffic. To the best of our knowledge, our paper is the first to explore the resource allocation issues for joint scheduling of URLLC and eMBB traffic using puncturing/superposition based mechanisms.

II System Model

Traffic model: We consider a wireless system supporting a fixed set $\mathcal{U}$ of backlogged eMBB users and a stationary process of URLLC demands. eMBB scheduling decisions are made across slots while URLLC demands arrive and are immediately scheduled in the next minislot. In this section we shall consider the case where eMBB all users receive resources for slots without using slot aggregation even though more flexible resource allocations which can possibly include slot aggregation and splitting are proposed in 5G standards . We shall justify this choice in Sec. IV-E. Each eMBB slot has an associated set of minislots where the set ${\cal M}=\{1,\dots|{\cal M}|\}$ denotes their indices. URLLC demands across minislots are modeled as an independent and identically distributed (i.i.d.) random process. We let the random variables $(D(m),m\in{\cal M})$ denote the URLLC demands per minislot for a typical eMBB slot and let $D$ be a random variable whose distribution is that of the aggregate URLLC demand per eMBB slot, i.e., $D\sim\sum_{m\in{\cal M}}D(m)$ with, cumulative distribution function $F_{D}(\cdot)$ and mean $E[D]=\rho.$ We assume demands have been normalized so the maximum URLLC demand per minislot is $f$ and the maximum aggregate demands per eMBB slot is $f\times|{\cal M}|=1$ i.e., all the frequency-time resources are occupied. URLLC demands per minislot exceeding the system capacity are blocked by URLLC scheduler thus $D\leq 1$ almost surely. The system is engineered so that blocked URLLC traffic on a minislot is a rare event, i.e., satisfies the desired reliability on such traffic.

Wireless channel variations: The wireless system experiences channel variations each eMBB slot which are modeled as an i.i.d. random process over a set of channel states ${\cal S}=\{1,\ldots,|{\cal S}|\}.$ Let $S$ be a random variable modeling the distribution over the states in a typical eMBB slot with probability mass function $p_{S}(s)=P(S=s)$ for $s\in{\cal S}.$ For each channel state $s$ eMBB user $u$ has a known peak rate $\hat{r}_{u}^{s}.$ The wireless system can choose what proportions of the frequency-time resources to allocate to each eMBB user on each minislot for each channel state. This is modeled by a matrix ${\bm{\phi}}\in\Sigma$ where

and where the element $\phi_{u,m}^{s}$ represents the fraction of resources allocated to user $u$ in mini slot $m$ in channel state $s$. We also let $\phi_{u}^{s}=\sum_{m\in{\cal M}}\phi_{u,m}^{s}$, i.e., the total resources allocated to user $u$ in an eMBB slot in channel state $s$. Now assuming no superposition/puncturing if the system is in channel state $s$ and the eMBB scheduler chooses an allocation ${\bm{\phi}}$ the rate $r_{u}$ allocated to user $u$ would be given by $r_{u}=\phi_{u}^{s}\hat{r}_{u}^{s}.$ The scheduler is assumed to know the channel state and can thus opportunistically exploit such variations in allocating resources to eMBB users. Note that for simplicity, we adopt a flat-fading model, namely, the rate achieved by an user is directly proportional to the fraction of bandwidth allocated to it (the scaling factor is the peak rate of the user for the current channel state).

Class of joint eMBB/URLLC schedulers: We consider a class of stationary joint eMBB/URLLC schedulers denoted by $\Pi$ satisfying the following properties. A scheduling policy combines a possibly state dependent eMBB resource allocation matrix $\bm{\phi}$ per slot with a URLLC demand placement strategy across minislots. The placement strategy may impact the eMBB users’ rates since it affects the URLLC superposition/puncturing loads they will experience. As mentioned earlier in discussing the traffic model, in order to meet low latency requirements URLLC traffic demands are scheduled immediately upon arrival or blocked. The scheduler is assumed to be causal so it only knows the current (and past) channel states and peak rates $\hat{r}_{u}^{s}$ for all $u\in{\cal U}$ and $s\in{\cal S}$ but does not know the realization of future channels or URLLC traffic demands. In making superposition/puncturing decisions across minislots, the scheduler can use knowledge of the previous placement decisions that were made. In addition the scheduler is assumed to know (or able measure over time) the channel state distribution across eMBB slots and URLLC demand distributions per minislot i.e., that of $D(m)$, and per eMBB slot, i.e., $D$, and thus in particular knows $\rho=E[D]$.

In summary a joint scheduling policy $\pi\in\Pi$ is thus characterized by the following:

an eMBB resource allocation ${\bm{\phi}}^{\pi}\in\Sigma$ where ${\phi}^{\pi,s}_{u,m}$ denotes the fraction of frequency-time slot resources allocated to eMBB user $u$ on minislot $m$ when the system is in state $s$.

the distributions of URLLC loads across eMBB resources induced by its URLLC placement strategy, denoted by random variables ${\bf L}^{\pi}=(L^{\pi,s}_{u,m}|u\in{\cal U},m\in{\cal M},s\in{\cal S})$ where $L^{\pi,s}_{u,m}$ denotes the URLLC load superposed/puncturing the resource allocation of user $u$ on minislot $m$ when the channel is in state $s$.

The distributions of $L^{\pi,s}_{u,m}$ and their associated means $\overline{l}_{u,m}^{\pi,s}$ depend on the joint scheduling policy $\pi$, but for all states, users and minislots satisfy

In the sequel we let $L^{\pi,s}_{u}=\sum_{m\in{\cal M}}L^{\pi,s}_{u,m}$, i.e., the aggregate URLLC traffic superposed/puncturing user $u$ in channel state $s$, and denote its mean by $\overline{l}_{u}^{\pi,s}$ and note that

We also let $L^{\pi,s}:=\sum_{u\in{\cal U}}L^{\pi,s}_{u}$ denote the aggregate induced load and note that any policy $\pi$ and for any state $s$ we have that

Modeling superposition/puncturing and eMBB capacity regions: Under a joint scheduling policy $\pi$ we model the rate achieved by an eMBB user $u$ in channel state $s$ by a random variable

where the rate allocation function $f_{u}^{s}(\cdot,\cdot)$ models the impact of URLLC superposition/puncturing – one would expect it to be increasing in the first argument (the allocated resources) and decreasing in the second argument (the amount superposition/puncturing by URLLC traffic). Under our system model we have that

with equality if there is no superposition/puncturing, i.e., when $l_{u}^{s}=0.$ Let $\overline{r}^{\pi,s}_{u}=E[R^{\pi,s}_{u}]$ denote the mean rates achieved by user $u$ in state $s$ under the URLLC superposition/puncturing distribution induced by scheduling policy $\pi$.

Models for Throughput Loss: In the sequel we shall consider specific forms of superposition/puncturing loss models: (i) linear, (ii) convex, and (iii) threshold models.

We rewrite the rate allocation function in (2) as the difference between the peak throughput and the loss due to URLLC traffic, and consider functions that can be decomposed as:

where $h^{s}_{u}:\rightarrow$ is the rate loss function and captures the relative rate loss due to URLLC overlap on eMBB allocations. The puncturing models we study now map directly to structural assumptions on the rate loss function $h^{s}_{u}(\cdot);$ namely it is a non-decreasing function, and is one of linear, convex, or threshold as shown in Figure 2.

Linear Model: Under the linear model, the expected rate for user $u$ in channel state $s$ for policy $\pi$ is given by

i.e., $h^{s}_{u}(x)=x,$ and the resulting rate to eMBB users is a linear function of both the allocated resources and mean induced URLLC loads. This model is motivated by basic results for the channel capacity of AWGN channel with erasures, see for more details. Our system in a given network state can be approximated as an AWGN channel with erasures, when the slot sizes are long enough so that the physical layer error control coding of eMBB users use long code-words. Further, there is a dedicated control channel through which the scheduler can signal to the eMBB receiver indicating the positions of URLLC overlap. Indeed such a control channel has been proposed in the 3GPP standards . Note that under this model the rate achieved by a given user depends on the aggregate superposition/puncturing it experiences, i.e., does not depend on which minislots and frequency bands it occurs. We discuss scheduling policies for linear loss models in Section III.

Convex Model: In the convex model, the rate loss function $h^{s}_{u}(\cdot)$ is convex (see Figure 2), and the resulting rate for eMBB user $u$ in channel state $s$ under policy $\pi$ is given by

This covers a broad class of models, and is discussed in Section IV.

Threshold Model: Finally the threshold model is designed to capture a simplified packet transmission and decoding process in an eMBB receiver. The data is either received perfectly or it is lost depending on the amount of superposition/puncturing. With slight abuse of notation we shall let $h^{s}_{u}$ also depend on both the relative URLLC load and the eMBB user allocation, i.e., $h^{s}_{u}(x)={\bf 1}(x\geq t_{u}^{s}(\phi^{s}_{u}))$ where the threshold in turn is an increasing function $t_{u}^{s}(\cdot)$ satisfying $x\geq t_{u}^{s}(x)\geq 0.$ Such thresholds might reflect various engineering choices where codes are adapted when users are allocated more resources, so as to be more robust to interference/URLLC superposition/puncturing. The resulting rate for eMBB user $u$ in channel state $s$ and policy $\pi$ is then given by

While such a sharp falloff is somewhat extreme, it is nevertheless useful for modeling short codes that are designed to tolerate a limited amount of interference. In practice one might expect a smoother fall off, perhaps more akin to the convex model, e.g., when hybrid ARQ (HARQ) is used. We discuss polices under the threshold based model in Section V.

Note that this capacity region depends on the scheduling policies under consideration as well as the distributions of the channel states and URLLC demands.

Scheduling objective: URLLC priority and eMBB utility maximization: As mentioned earlier, URLLC traffic is immediately scheduled upon arrival, in the next minislot, i.e, no queuing is allowed. Thus if demands exceed the system capacity on a given minislot traffic would be lost. However, we assume that the system has been engineered so that such URLLC overloads are extremely rare, and thus URLLC traffic can meet extremely low latency requirements with high reliabilityNote that since we allow URLLC traffic in the entire system bandwidth, such overload events are very rare. . For eMBB traffic we adopt a utility maximization framework wherein each eMBB user $u$ has an associated utility function $U_{u}(\cdot)$ which is a strictly concave, continuous and differentiable of the average rate $c_{u}^{\pi}$ experienced by the user. Our aim is to characterize optimal rate allocations associated with the utility maximization problem:

and determine a scheduling policy $\pi$ that will realize such allocations.

III Linear Model for Superposition/Puncturing

In any state $s$, the optimal joint eMBB/URLLC scheduler may either 1) protect the user with the lower channel rate by placing less URLLC traffic into its frequency resources to ensure fairness or 2) opportunistically place URLLC traffic so that the user with a better channel gets a higher rate to improve the overall system throughput. The solution for any state is complex function of network states and their distribution and user utility functions and in general, eMBB scheduling and URLLC puncturing may be dependent. In this section, we show a surprising result – despite having non-linear utility functions, if the loss functions are linear and the eMBB scheduler is intelligent (i.e., takes into the degradation of rates due to puncturing), then the URLLC scheduler can be oblivious to the channel states, utility functions and the actual rate allocations of the eMBB scheduler.

Let us consider the capacity region for a wireless system based on linear superposition/puncturing model under a restricted class of policies $\Pi^{LR}$ that combine feasible eMBB allocations ${\bm{\phi}}\in\Sigma$ with random placement of URLLC demands uniformly over the bandwidth across minislots. Note that the notation $LR$ stands for linear loss model (L) with random (R) placement of URLLC traffic. For any $\pi\in\Pi^{LR}$ with eMBB allocation $\bm{\phi}^{\pi}$ the mean induced loads under such randomization for each state $s\in{\cal S}$ and minislot $m\in{\cal M}$ will satisfy $\overline{l}^{\pi,s}_{u,m}=\rho\phi^{\pi,s}_{u,m}.$ Indeed randomization clearly leads to an induced loads that are proportional to the eMBB allocations on a per mini-slot basis, but also per eMBB slot, i.e., $\overline{l}^{\pi,s}_{u}=\rho\phi^{\pi,s}_{u}.$ Thus for our linear loss model we have that

Hence the overall user rates achieved under such a policy are given by ${\bf c}^{\pi}=(c_{u}^{\pi}|u\in{\cal U})$ where

The capacity region associated with policies that use URLLC uniformly randomized placement is thus given by

where we have abused notation by using ${\bf c}^{\bm{\phi}}$ to represent the throughput achieved under policy $\pi$ that uses eMBB resource allocation ${\bm{\phi}}$ and uniformly randomized URLLC demand placement. Finally note that for any fixed $\rho\in(0,1),$ ${\cal C}^{LR}$ is a closed and bounded convex region. This is because an affine map of a convex region remains convex; hence multiplying the constraints on the capacity region defined by ${\bm{\phi}}$ by a constant $(1-\rho)$ preserves convexity of the rate region.

For a wireless system under the linear superposition/puncturing loss model we have that ${\cal C}={\cal C}^{LR}.$

The proof is deferred to the Appendix A. In other words the throughput ${\bf c}^{\pi}\in{\cal C}$ achieved by any feasible policy $\pi\in\Pi$ can also be achieved by policy $\pi^{\prime}$, with a possibly different eMBB resource allocation policy than $\pi$ but utilizing uniform random placement of URLLC demands across mini-slots.

III-B Utility maximizing joint scheduling

Given the result in Theorem 1 we now restate the utility maximization problem as optimizing solely over joint scheduling policies that use URLLC random placement policies, as follows:

The above optimization problem has a strictly concave cost function and convex constraints. Thus, at face-value, it appears that we can apply the gradient scheduler introduced in , which is an online algorithm designed to converge to the solution of similar optimization problem. This observation is approximately correct, but subject to two modifications.

First, the setting in has deterministic rates in each channel state. However, in our case, in each channel state, the rates are stochastic due to puncturing by URLLC traffic (this results in the $(1-\rho)$ correction). This can be easily addressed by modifying the setting in ; the finite state and i.i.d. nature of puncturing implies that the proofs in hold with minor modifications; we skip the details.

The second issue is somewhat more nuanced. In current wireless systems (e.g. LTE) and proposals for 5G systems, a slot is partitioned into a collection of Resource Blocks (RB), where each RB is a time-frequency rectangle (1 msec $\times$ 180 KHz in LTE). Importantly, these RBs can be individually allocated to different eMBB users. If we now apply the gradient scheduler in to our setting, the result will be that all RBs in a slot will be allocated to the same user. While this is no-doubt asymptotically optimal, it seems intuitive that sharing RBs across users even within a slot will lead to better short-term performance. Indeed this intuition has been explored in the context of iterative MaxWeight algorithms to provide formal guarantees, see . The high level idea is that even within a slot, RB allocations are done iteratively, where future RB allocations need to account for prior rate allocations even within the same slot. This is formalized below, where we describe our proposed joint eMBB-URLLC scheduler.

The URLLC scheduler: As explained in the previous section, the URLLC scheduler places the URLLC traffic uniformly at random in each minislot.

The eMBB scheduler: Let there be $B$ resource blocks available for allocation every eMBB slot, indexed by $1,2,\ldots,B$. Let $\overline{R}_{u}(t-1)$ be the random variable denoting the average rate received by eMBB user up to eMBB slot $t-1$. Let $\overline{r}_{u}(t-1)$ be a realization of $\overline{R}_{u}(t-1)$. In any eMBB slot $t$ we schedule an user $u(b)$ in RB $b$ such that

where $\overline{r}_{u}^{\epsilon}\left(b-1,t\right)$ is an estimate of the average rate received by eMBB user $u$ till slot $t$ which is iteratively updated as follows:

In the above equation, $\epsilon$ is a small positive value. At the end of eMBB slot $t$, the eMBB scheduler receives feedback from the eMBB receivers indicating the actual rates received by the eMBB users due to allocations. We denote the rate received eMBB user $u$ in slot by the random variable $R_{u}(t)$ and its realization by $r_{u}(t)$. We finally update $\overline{r}_{u}(t)$ as follows:

This scheduler and update equations are analogous to the gradient algorithm (see also iterative algorithms in ). The optimality proof of this algorithm follows (with minor modifications) from the analysis in ; we skip the details.

Remarks: (i) A natural decomposition of the joint eMBB+URLLC scheduling is now apparent. On one hand, the eMBB scheduler maximizes utilities based on the expected channel rates stemming from uniform random puncturing of minislots (accounted for through the $(1-\rho)$ multiplicative factor), and does so using the iterative gradient scheduler. The URLLC scheduler, on the other-hand, is completely agnostic to either the channel state or the actual eMBB allocations and simply punctures minislots based on the current instantaneous demand.

(ii) The fact that the URLLC traffic placement is completely agnostic to the channel state and eMBB utilities/allocation is surprising. Intuitively it seems plausible that one could puncture an eMBB user with a lower marginal utility with more URLLC traffic, while protecting an eMBB user with a higher marginal utility and achieve a better sum utility. Further, it seems reasonable that eMBB users with a worse channel state (and thus lower rate) could be loaded with additional URLLC traffic. However, Theorem. 1 implies that there exists an optimal solution that is achieved by channel and utility oblivious and uniform random URLLC placement, thus providing a very simple algorithm for URLLC scheduling.

(iii) We remark that the optimality of random puncturing for linear loss models depends critically on the use of an opportunistic scheduler for eMBB traffic.To see this, consider a simple system with two symmetric eMBB users each with two possible channel states. The associated channel rates are either $\{2,4\}$ packets/slot with equal probability, and independent across users and time slots. Suppose that we use a static (non-opportunistic) scheduler, which equally splits channel access between the users. It is easy to calculate that the rate to each user is then 1.5 packets/slot. Next suppose that the URLLC load is 50%, and that this traffic randomly punctures eMBB users. Then from symmetry, it follows that the rate per eMBB user is $0.75$ packets/slot. In contrast, suppose that puncturing is opportunistic, where the user with the currently lower rate is punctured whenever possible (opportunistic puncturing of the currently worse eMBB user), a straightforward calculation shows that the rate to each eMBB user is $0.875$ packets/slot, which is a strict improvement over random puncturing. At a high-level, this follows because opportunistic eMBB scheduling operates on the Pareto frontier of two-user capacity region, and consequently there is no residual opportunistic to be obtained by puncturing. However, with non-opportunistic scheduling, the system is not pushed to the boundary; thus, opportunistic puncturing can extract additional throughput for eMBB users.

IV Convex Model – Minislot-Homogenous Policies

In this section we shall consider joint scheduling for wireless systems for convex superposition/puncturing loss models. This is a somewhat complex problem, whence we will focus our attention on a restricted, but still rich, class of scheduling policies which we refer to as minislot-homogeneous eMBB/URLLC schedulers. We identify a key concavity requirement in Assumption 2 (that is satisfied by convex loss functions) that enables a stochastic approximation approach for utility maximizing scheduling.

We shall define minislot-homogeneous eMBB/URLLC schedulers as follows. First, feasible eMBB allocations ${\bm{\phi}}\in\Sigma$ will be restricted such that for any eMBB slot in channel state $s\in{\cal S}$ allocations are minislot-homogeneous across minislots in an eMBB slot, i.e., $\phi_{u,1}^{s}=\phi_{u,m}^{s},\forall m\in{\cal M}$ and its overall allocation for the slot is given by $\phi_{u}^{s}=|{\cal M}|\phi_{u,1}^{s}.$ The set of minislot-homogeneous eMBB allocations is thus given by

Second, URLLC demand placements per minislot are done proportionally based on pre-specified weights, and these weights are assumed to be time-homogeneous across minislots. In particular such policies are parametrized by a weight matrix $\bm{\gamma}\in\Sigma^{H}$, where the induced load on user $u$ under channel state $s$ and slot $m$ is given by

We shall call $\gamma_{u,1}^{s}$ the URLLC placement factor for eMBB user $u$ in state $s$. The eMBB and URLLC allocations are coupled together since it must be the case that for all $u\in{\cal U}$ $L_{u,m}^{s}\leq\phi_{u,m}^{s}=\phi_{u,1}^{s}$ almost surely, i.e., one can not induce more superposition/puncturing load on a user than the resources it has been allocated on that slot. So the following condition must be satisfied. For all $m\in{\cal M}$ we have that

Recall that $f$ denotes the maximum URLLC load per minislot so $D(m)\leq f$ almost surely, thus if $\frac{\phi_{u,1}^{s}}{\gamma_{u,1}^{s}}\geq 1$ the above condition will always hold. Yet if $\phi_{u,1}^{s}\geq\gamma_{u,1}^{s}$ for all $u$, then we have that $\phi_{u,1}^{s}=\gamma_{u,1}^{s}$, i.e., there is not flexibility to exploit careful placement of URLLC demands. Hence, we introduce the following assumption:

We say the system has a $(1-\delta)$ URLLC sharing factor per minislot if $D(m)\leq f(1-\delta)$ almost surely for all $m\in{\cal M}$, where $\delta\in\left(0,1\right)$.

For any $\delta$ the above assumption implies that the peak URLLC demand in an eMBB slot can be at most $1-\delta$ which is lower than maximum possible value of one. Such an assumption is reasonable as we consider shared resources which are engineered to meet the peak URLLC loads while also serving eMBB traffic. Under a $(1-\delta)$ URLLC sharing factor a minislot-homogeneous eMBB resource allocation ${\bm{\phi}}$ and URLLC allocation ${\bm{\gamma}}$ is will be feasible if for all $s\in{\cal S}$ we have

which is satisfied as long as $(1-\delta)\gamma_{u,1}^{s}\leq\phi_{u,1}^{s}$ for all $u\in{\cal U}$. This motivates the following definition:

For a system with a $(1-\delta)$ sharing factor, the feasible minislot-homogeneous eMBB/URLLC scheduling policies are parameterized by ${\bm{\phi}},{\bm{\gamma}}\in\Sigma^{H}$ such that $(1-\delta)\bm{\gamma}\leq{\bm{\phi}}$. We shall denote the set of such policies as follows:

IV-B Characterization of the throughput region

In this section we characterize the throughput regions achievable under time-homogeneous scheduling.

For a system with a $(1-\delta)$ sharing factor and minislot-homogeneous scheduler ${\bm{\pi}}=({\bm{\phi}}^{\bm{\pi}},{\bm{\gamma}}^{\bm{\pi}})\in\Pi^{H,\delta}$ the average induced throughput for user $u\in{\cal U}$ in channel state $s\in{\cal S}$ is given by

and the overall average user throughputs are given by ${\bf c}^{{\bm{\pi}}}=(c^{{\bm{\pi}}}_{u}\mid u\in{\cal U})$ where $c^{{\bm{\pi}}}_{u}=\sum_{s\in{\cal S}}r^{{\bm{\pi}},s}_{u}p_{S}(s).$

The proof is included in Appendix B. Based on the above we can define feasible throughput region constrained to the time-homogeneous policies in $\Pi^{H,\delta}.$ First let us define

and let $\hat{\cal C}^{H,\delta}$ denote the convex hull of ${\cal C}^{H,\delta}.$ Note that rates in the convex hull are achievable through policies that do time sharing/randomization amongst minislot-homogeneous scheduling policies in $\Pi^{H,\delta}.$

For all $s\in{\cal S}$ and $u\in{\cal U}$ the functions $g^{s}_{u}(,)$ given by

Assumption 2 is satisfied for systems where superposition/puncturing of each user is modelled via either a

Threshold loss function with fixed relative thresholds, i.e., $t^{s}_{u}(\phi^{s}_{u})=\alpha^{s}_{u}$ for $\phi\in$ and the URLLC demand distribution $F_{D}(\cdot)$ is such that $F_{D}(\frac{1}{x})$ is concave in $x$ (satisfied by the truncated Pareto distribution).

The proof is included in Appendix C. With this condition in place, we now describe the throughput region.

Under Assumption 2 we have that ${\cal C}^{H,\delta}=\hat{\cal{C}}^{H,\delta}$.

The proof is available in the Appendix D. The above theorem implies that we do not have to consider time-sharing/randomization amongst minislot-homogeneous joint scheduling policies. Thus, with minislot-homogeneous policies and under the concavity of $g_{u}^{\pi,s}\left(\cdot,\cdot\right)$ from Assumption 2, the above result sets up a convex optimization problem in $(\bm{\phi},\bm{\gamma)},$ i..e, we have a concave cost function with convex constraints. Thus, by iteratively updating $(\bm{\phi},\bm{\gamma)},$ we can develop an online scheduling algorithm that asymptotically maximizes eMBB users’ utility. This is descried next.

IV-C Stochastic approximation based online algorithm

We first restate the utility maximization problem for minislot-homogeneous URLLC/eMBB scheduling policies:

Observe that the objective function is concave because it consists of a sum of compositions of non-decreasing concave functions ($U_{u}(\cdot)$), and concave functions ($g^{s}_{u}\left(\cdot,\cdot\right)$) in $\bm{\phi}$ and $\bm{\gamma}$ (if Assumption 2 holds). Further, the constraint set is convex. Therefore, the above problem fits in the framework of standard convex optimization problems. However, solving the above problem requires knowledge of all possible network states and their probability distribution, resulting in an offline optimization problem. In this section, we develop a stochastic approximation based online algorithm to solve the above problem.

At the end of eMBB slot $t$, the eMBB scheduler receives feedback from the eMBB receivers indicating the rates received by the eMBB users. Let us denote the rate received eMBB user $u$ in the slot by the random variable $R_{u}(t)$. We update $\overline{R}_{u}(t)$ as follows:

where $\left\{\epsilon_{t}\mid t=1,2,3,\ldots\right\}$ is a sequence of positive numbers which satisfy the following (standard) assumption:

The averaging sequence $\{\epsilon_{t}\}$ satisfies:

Finally, we state the main result of this section, which is the optimality of the stochastic approximation based online algorithm.

Let $\bm{r}^{*}$ be the optimal average rate vector received by eMBB users under the solution to the offline optimization problem. Suppose that Assumptions 3 and 2 hold, then we have that:

The proof is available in the Appendix E.

IV-D Optimality of Minislot-Homogeneous Policies

In the previous section we restricted ourselves to minislot-homogeneous policies. In this section will justify this choice. Let us consider a generalization of minislot-homogeneous policies where the URLLC placement in each minislot can depend on the history of URLLC arrivals prior to that minislot. Such a policy will obviously perform better than minislot-homogeneous URLLC placement policies since in a minislot-homogeneous policy we decide the URLLC placement at the beginning of an eMBB slot based on the expected loss due to puncturing/superposition and do not adapt it based on the realization of URLLC demands per minislot. However, finding an optimal scheduling policy under this generalization can be computationally expensive as compared to minislot-homogeneous policies which are attractive due to their simplicity. In this section we identify conditions under which minislot-homogeneous URLLC placement polices perform as well as the general class of causal and minislot-dependent policies. These terms are defined below.

A scheduler is said to be causal if at the beginning of a mini-slot $m$ the scheduler knows the realizations of $D(1)$, $D(2),\ldots,D(m-1)$ and is unaware of the realizations of $D(m),D(m+1),\ldots,D(\left|\mathcal{M}\right|)$.

A scheduling policy is said to be minislot-dependent if the URLLC placement policy can vary with the minislot index $m$ and previous URLLC demands in the eMBB slot.

The decision variables in a causal and minislot-dependent joint scheduling policy $\pi$ can be described as follows:

At the beginning of an eMBB slot, the scheduler chooses $\phi_{u}^{\pi,s},u\in\mathcal{U}$ such that

In each mini-slot $m$, the total puncturing placed on eMBB user $u$ is given by $\gamma_{u,m}^{\pi,s}\left(\bm{d}^{\left(1:m-1\right)}\right)D_{m}$, where $\gamma_{u,m}^{\pi,s}\left(\cdot\right)$ characterizes the URLLC placement in minislot $m$ as function of the previously seen URLLC demands $\bm{D}^{\left(1:m-1\right)}:=\left(D(1),D(2),\ldots,D(m-1)\right)$. Let $\bm{d}^{\left(1:m-1\right)}$ is a realization of $\bm{D}^{\left(1:m-1\right)}$. For any $m$ and $\bm{d}^{\left(1:m-1\right)}$, $\gamma_{u,m}^{\pi,s}\left(\bm{d}^{\left(1:m-1\right)}\right)$ has to satisfy the following constraints.

Observe that the URLLC placement factor for causal and minislot-dependent scheduling policy is not just dependent on the user and network state but it also depends on the mini-slot index and past URLLC demands.

where $s$ is the current network state, $\bm{\gamma}_{u}^{\pi,s}:=\left({\gamma}_{u,1}^{\pi,s}\left(\cdot\right),{\gamma}_{u,2}^{\pi,s}\left(\cdot\right),\ldots,{\gamma}_{u,\left|\mathcal{M}\right|}^{\pi,s}\left(\cdot\right)\right)$ is the vector of URLLC placement factors of all minislots (with slight abuse of notation) and $g_{u}^{\pi,s}\left(\cdot,\cdot\right)$ is the average rate experienced by eMBB user $u$ under policy $\pi$. $g_{u}^{\pi,s}\left(\cdot,\cdot\right)$ is given by the following expression:

A loss function $h_{u}^{s}(\cdot)$ is said to be homogeneous if there exists a real number $p$ such that $\forall$ $x\in\left[0,1\right]$ and $\kappa\geq 0$ we have that

Even with this restriction we can model useful loss functions which could possibly be user and network state dependent. Some examples are given below.

Linear: $h_{u}^{s}(x)=k_{u}^{s}\left(x\right)$, where $k_{u}^{s}\geq 0$.

Monomial: $h_{u}^{s}(x)=k_{u}^{s}\left(x\right)^{q}$ where $k_{u}^{s}\geq 0$ and $q\geq 1$.

Our main result on the optimality of minislot-homogeneous policies is proved in Appendix F and stated next.

If the support of URLLC demands $D$ is a finite discrete set and eMBB loss functions are homogeneous and convex, then there exists an optimal solution $\left(\bm{\phi}^{s,*},\bm{\gamma}^{s,*}\left(\cdot\right)\right)$ for $\mathcal{OP}_{1}$ with a minislot-homogeneous URLLC placement policy $\bm{\gamma}^{s,*}$.

IV-E Optimal eMBB Slot Slicing

In Section II we have used uniform slot sizes for eMBB users, i.e. the allocated minislots to all users span the entire width of the slot (see Figure 4; henceforth referred to as frequency slices). However, new proposals allow greater flexibility in slot allocation, e.g., the capability to choose different slices over both time and frequency for different eMBB users . In this section we will show that while it is possible to slice eMBB users’ resources flexibly, it is preferable to slice frequency (see 4) than time from the point of view of puncturing losses for convex loss functions.

The essence of the discussion can be captured by comparing the two resource allocation configurations shown in Figures 3 and 4. In Configuration 1 (time slices), eMBB user 1 is allocated the entire frequency band for a subset of $m_{1}$ minislots. Similarly eMBB user 2 is allocated the entire frequency band for its subset of $m_{2}$ minislots. The network state $s$ is assumed to be the same for the entire $m_{1}+m_{2}$ minislots. This implies that the loss functions of eMBB users $(h_{u}^{s}\left(\cdot\right))$ do not change throughout the $m_{1}+m_{2}$ minislots. In Configuration 2 (frequency slices) we allocate an eMBB user $1$ a fraction $\phi_{1}$ of the bandwidth for a duration of $m_{1}+m_{2}$ minislots, where $\phi_{1}:=\frac{m_{1}}{m_{1}+m_{2}}$ and similarly for eMBB user $2$. Note that the total resources allocated to eMBB users, which is represented by the area allocated in the time-frequency plane is same in both configurations.

In Configuration 1, the total puncturing observed by eMBB user $1$ is given by $\sum_{m=1}^{m_{1}}D(m)$ and similarly for eMBB user $2$. Whereas in Configuration 2, under uniform URLLC placement, the total puncturing observed by eMBB user $1$ is given by $\sum_{m=1}^{m_{1}+m_{2}}\phi_{1}D(m)$. Note that the mean total puncturing is same in both the configurations.

The main result of this section is given below:

Under the assumption of i.i.d. URLLC demandsThis result can be extended to exchangeable URLLC demands. We use i.i.d. assumption to maintain consistency with other sections. ($D(m),\,m=1,2,\ldots,m_{1}+m_{2}$) and convex loss functions $(h_{u}^{s}\left(\cdot\right))$, for any eMBB user, e.g., eMBB user $1$, we have that

Proof of this result is given in Appendix G.

Remarks: The above theorem shows that the expected loss suffered by an eMBB user due to URLLC puncturing in Configuration 1 (time slicing) is higher than in Configuration 2 (frequency slicing). This implies that it is preferable for eMBB users to spread their resource allocation over time from the perspective of reducing their loss due to puncturing. The underlying reason is that Configuration 2 results in smaller variability in the total puncturing even though both the configurations have the same mean total puncturing. Since the loss functions are convex, a lower variability leads to a lower expected loss. Finally, for more complex (rectangular) slices, we can now apply Thm. 6 iteratively and show that using frequency slices with appropriate scaling of the bandwidth allocation results in a higher average rate for eMBB users.

V Threshold Model and Placement Policies

In the previous section, we developed a stochastic approximation based algorithm for minislot-homogeneous policies. This algorithm iteratively solves the optimization problem given in (10). This optimization problem jointly optimizes over a pair of row vectors $(\bm{\phi}^{s},\bm{\gamma}^{s}).$ While this convex optimization problem can be solved using standard methods, it could become computationally challenging as the number of users increases.

In this section, we shall restrict our attention to a threshold model for superposition/puncturing, and look at policies that impose structural conditions on the puncturing matrix $\bm{\gamma}.$ We will show that the resulting class of policies have nice theoretical properties that lead to simpler online algorithms (solving (4), which is an one-dimensional search).

We consider two types of structural conditions on $\bm{\gamma}$:

(i) Resource Proportional (RP) Placement: The first is based on allocating URLLC demands in proportion to eMBB user slot allocations, i.e., $\gamma^{s}_{u}=\phi^{s}_{u}.$ We refer to this as Resource Proportional (RP) Placement and denote such policies by

and define the associated achievable throughput region

The motivation for RP Placement comes from the optimality of random placement for the linear model in Section III. Observe that if puncturing occurs uniformly randomly, then the expected number of punctures is directly proportional to the fraction of bandwidth allocated to an eMBB user. Thus, RP Placement can be viewed as a determinized version of the random placement strategy which ensures that the proportions of puncturing satisfy resource proportional ratios.

(ii) Threshold Proportional (TP) Placement: The second policy allocates URLLC demands in proportion to the eMBB users associated loss thresholds so as to avoid losses,

We refer to this as Threshold Proportional (TP) Placement and denote such policies by

The associated achievable throughput region is denoted

First we state a corollary to Theorem 2 which characterizes the rates under different URLLC placement policies for systems having threshold loss model for superposition/puncturing.

Under a $(1-\delta)$ sharing factor and time-homogeneous scheduler ${\bm{\pi}}=({\bm{\phi}}^{\bm{\pi}},{\bm{\gamma}}^{\bm{\pi}})\in\Pi^{H,\delta}$ the probability of induced eMBB loss for user $u\in{\cal U}$ in channel state $s\in{\cal S}$ is given by

where $F_{D}$ denotes the cumulative distribution function of the URLLC demands on a typical eMBB slot. Then the associated user throughput is given by

and the overall user throughputs are given by ${\bf c}^{{\bm{\pi}}}=(c^{{\bm{\pi}}}_{u}:u\in{\cal U})$ where

The following two corollaries are direct consequences of Corollary 1 and Theorem 3 restricted to RP and TP Placement strategies, and characterize the capacity regions under the two policies.

Consider a wireless system with full sharing factor and time-homogeneous scheduler based on the RP URLLC Placement policy ${\bm{\pi}}=({\bm{\phi}}^{\bm{\pi}},{\bm{\gamma}}^{\bm{\pi}})\in\Pi^{RP,\delta}.$ Then any eMBB resource allocation $\bm{\phi}$ combined with a RP URLLC demand placement policy, $\bm{\gamma}=\bm{\phi}$ is feasible. The probability of loss for user $u\in{\cal U}$ in channel state $s\in{\cal S}$ is given by

Further if for all $s\in{\cal S}$ and $u\in{\cal U}$ the functions $g^{s}_{u}(,)$ given by

are concave then ${\cal C}^{RP,\delta}=\hat{\cal C}^{RP,\delta}.$

Under a $(1-\delta)$ sharing factor and jointly uniform scheduler based on the TP URLLC Placement policy ${\bm{\pi}}=({\bm{\phi}}^{\bm{\pi}},{\bm{\gamma}}^{\bm{\pi}})\in\Pi^{TP,\delta},$ the probability of induced eMBB loss user $u\in{\cal U}$ in channel state $s\in{\cal S}$ is given by

Further if for all $s\in{\cal S}$ and $u\in{\cal U}$ the functions $g^{s}_{u}(,)$ given by

are jointly concave then ${\cal C}^{TP,\delta}=\hat{\cal C}^{TP,\delta}.$

The following theorem provides a formal motivation for TP Placement. The main takeaway here is that the probability of any loss in an eMBB slot under TP Placement policy is a lower bound for all other strategies. Note that minimizing the probability of any eMBB loss is not same as minimizing eMBB rate loss.

Consider a system with $(1-\delta)$ sharing factor. Consider a joint scheduling policy based on the TP URLLC placement i.e, ${\bm{\pi}}=({\bm{\phi}}^{\bm{\pi}},{\bm{\gamma}}^{\bm{\pi}})\in\Pi^{TP,\delta}.$ Then ${\bm{\pi}}$ achieves the minimum probability of any eMBB loss amongst all joint scheduling policies using the same eMBB resource allocation ${\bm{\phi}}^{\bm{\pi}}.$

Next we consider online algorithms that implement the RP and TP Placement policies. While the stochastic approximation algorithm developed in Section IV-C can clearly be used, the additional structure imposed by the RP and TP Placement policies, and the shape of the threshold loss function (discussed below) can result in much simpler algorithms (with optimality guarantees).

We consider the case where $t^{s}_{u}(\phi)$ is a (state dependent but $\phi$ independent) constant, i.e., $t^{s}_{u}(\phi)=\alpha^{s},$ where $\alpha^{s}\in(0,1).$ Intuitively, this means that eMBB traffic which has a higher share of the bandwidth is more resilient to losses (e.g. through coding over larger fraction of resources). Then, by substituting this loss function in (24) and (27) (where we also use the fact that $\sum_{u\in{\cal U}}\phi^{s}_{u}=1$), we have that

Comparing with the development in Section III-B, we observe that the cost and constraints are identical if $F_{D}(\alpha^{s})$ replaces $(1-\rho).$ Note that a small difference is that $F_{D}(\alpha^{s})$ is state dependent, whereas $(1-\rho)$ does not depend on the state; however, it is easy to see that the development in Section III-B immediately generalizes to this setting. Hence, we can interpret $F_{D}(\alpha^{s})$ as the state dependent average rate loss due to puncturing via the RP or TP Placement policies.

We can now employ the rate-based iterative gradient scheduler developed in Section III-B (by replacing $(1-\rho)$ in (5) by a user-dependent $F_{D}(\alpha^{s})$), and the theoretical guarantees directly carry over. As this algorithm only minimizes over users at each slot in (4), this is easier to implement when compared to the stochastic approximation algorithm developed in Section IV-C.

VI Simulations

We consider a system with a total of 100 RBs available per eMBB slot, and with 8 minislots per eMBB slot. In an eMBB slot, $\hat{r}_{u}^{s}$ for an eMBB user is drawn from the finite set $\left\{1,2,3,4,5,6,7,8,9,10\right\}$ Mbps according to a probability distribution and i.i.d. across users and slots. Our system consists of 20 users, and with 100 channel states (all equally likely). The ($20$ users $\times$ $100$ states) rate matrix is one-time synthesized by independently and uniformly sampling a rate from the finite rate set for each matrix element. For $10$ eMBB users, we have chosen the probability distribution such that the average rate is $7$ Mbps. For the rest, probability distribution is such that the average rate is $3$ Mbps. This models two classes of users, one class with higher link rates which can tolerate a higher amount of puncturing and the other with lower link rates which can tolerate lesser amount of puncturing. This is reasonable as a user with a higher channel rate can code more robustly and protect its transmissions from URLLC puncturing more than a user with a lower channel rate. In this spirit we shall call users with $7$ Mbps average rates as ‘robust’ users and users with $3$ Mbps average rates as ‘sensitive’ users. We use the utility function $U_{u}(r)=\log\left(r\right)$ for all users.

We first show that joint scheduling is necessary to preserve eMBB throughputs. To that end we benchmark our optimal online algorithm (stochastic approximation algorithm, see Section IV-C) for convex loss functions with a scheme which performs standard gradient based scheduling for eMBB users and Resource Proportional (RP) URLLC placement. Note that for convex loss functions, RP placement strategy does not take into account the eMBB user’s sensitivity to delays. For users with average rate $7$ Mbps, we use the loss function $h_{u}^{s}(x)=x^{2}$. For users with average rate $3$ Mpbs, we use the following loss function:

URLLC demands in a minislot is drawn from a binomial distribution which can take values with $p$ and $\frac{1-\delta}{8}$ with probability $1-p$. Note that this ensures that peak URLLC load in an eMBB slot is less than or equal to $1-\delta$.

In Fig. 5, we compare the average sum utility under our optimal joint scheduler and the RP based policy as a function of the URLLC load. As the load increases, RP performs poorly. To understand this phenomenon in detail, we have plotted the average rates of robust and sensitive users under the two policies in Fig. 6. As we increase the URLLC load, the average eMBB rates of both sensitive and robust users decrease rapidly. For example, when $\rho=0.4$, RP has $15$ % lower throughput for robust users and almost similar performance for sensitive users as compared to optimal algorithm. Further as we increase $\rho$ to $0.6$, the throughput of robust and sensitive users in RP decrease by $35$ % and $26$ %, respectively.

Sensitive users are the most affected by URLLC puncturing. When the RP URLLC placement policy is combined with the standard gradient based algorithm for eMBB users, it allocates more resources to sensitive users because they have higher marginal utility. Since sensitive users receive more bandwidth, under the RP URLLC placement strategy they receive more puncturing. This will lead to even more allocation of resources to sensitive users and this process continues until robust users have similar marginal utilities (due to reduced rates) as sensitive users. Hence, the robust users are resource starved. As we increase the URLLC load further, sensitive users receive even more URLLC puncturing and neither the robust nor sensitive users get good average rates when compared to the optimal joint scheduler. This shows that we require joint scheduling of eMBB and URLLC to exploit the heterogeneity in sensitivities to URLLC puncturing in maximizing eMBB utilities.

Next we consider a threshold based loss model with $\alpha^{s}=0.3$ for 50% of eMBB states and $\alpha^{s}=0.7$ for the rest. We use the utility function $U_{u}(r)=\log(r)+6.5$ for all eMBB users, where $r$ is measured in Mbps (constant added to ensure non-negativity of the sum utility). URLLC load in an eMBB slot ($D$) is generated based on the truncated Pareto distribution with tail exponent $\eta=2$. We compare the optimal policy (stochastic approximation algorithm, see Section IV-C) with that from the TP Placement policy (the simpler gradient algorithm in Section V). In this case, since the threshold functions are (state-dependent) constants, the RP and TP Placement policies are the same. As we can see in Figure 7, unlike the convex loss model the RP/TP Placement policy tracks the optimal policy very well.

In Figure 9, we study the trade-off between achieving a higher eMBB utility and lowering the mean delay of URLLC traffic for different values of the sharing factor $1-\delta$. Figure 9 plots the corresponding probability that the URLLC traffic delay exceeds two minislots ($0.125\times 2=0.25$ msec). To study this trade-off we generate URLLC arrivals in each minislot from an uniform distribution between $\left[0,1/8\right]$ (recall there are 8 minislots). In each minislot, we can serve at most $\frac{1-\delta}{8}$ units of URLLC traffic. If the URLLC load in a given minislot is more than $\frac{1-\delta}{8}$, the remaining URLLC traffic is queued and served in the next minislot on a FCFS basis. For the eMBB users we use a convex model with $h_{u}^{s}(x)=e^{{\kappa_{u}\left(x-1\right)}}$ where $\kappa_{u}$ determines the sensitivity of an eMBB user to an URLLC load. We have chosen $\kappa=0.2$ for 50 % of the users and $\kappa=0.7$ for the rest. We also set $\forall u$ $U_{u}(x)=\log(x)+4.2$ (constant added to ensure positive sum utility). In summary, a larger value of $\delta$ limits the amount of URLLC traffic than can be served in a minislot. However, a larger $\delta$ enlarges the constraint set $\Pi^{H,\delta}$ in the eMBB utility maximization problem, and hence we get higher eMBB utility.

VII Conclusion

In this paper, we have developed a framework and algorithms for joint scheduling of URLLC (low latency) and eMBB (broadband) traffic in emerging 5G systems. Our setting considers recent proposals where URLLC traffic is dynamically multiplexed through puncturing/superposition of eMBB traffic. Our results show that this joint problem has structural properties that enable clean decompositions, and corresponding algorithms with theoretical guarantees.

Acknowledgements

The work of Arjun Anand was partially supported by FutureWei Technologies and NSF grant CNS-1731658, Gustavo de Veciana was partially supported by NSF grants CNS-1343383 and CNS-1731658, and Sanjay Shakkottai was partially supported by NSF grants CNS-1343383 and CNS-1731658, and the US DoT D-STOP Tier 1 University Transportation Center.

References

-A Proof of Theorem 1

Clearly since $\Pi^{LR}\subset\Pi$ we have that ${\cal C}^{LR}\subset{\cal C}$

Now consider any policy $\pi\in\Pi$ with eMBB user allocations ${\bm{\phi}}^{\pi}$ and URLLC loads $\overline{{\bf l}}^{\pi}$ and associated long term throughput is $\mathbf{c}^{\pi}$ given by

Let us define a $\pi^{\prime}$ based on $\pi$ to have per minislot eMBB user allocations given by

for $s\in{\cal S},$ $u\in{\cal U}$ and $m\in{\cal M}.$ Since induced mean loads on an eMBB user can not exceed its allocation we have that ${\bm{\phi}}^{\pi}\geq\overline{{\bf l}}^{\pi}$ so the above allocations are positive. Note also that this allocation is not minislot dependent, but normalized so that per minislot they sum to $f$ and over the whole eMBB slot sum to $1$, i.e., ${\bm{\phi}}^{\pi^{\prime}}\in\Sigma$. Thus for such an allocation we have that

Also suppose that $\pi^{\prime}$ uses randomized URLLC placement across minislots which induces mean URLLC loads proportional to the allocations, i.e., $\overline{l}^{\pi^{\prime},s}_{u}=\rho\phi^{\pi^{\prime},s}_{u}$. It follows that

and so $c_{u}^{\pi,s}=c_{u}^{\pi^{\prime},s}$ for all $s\in{\cal S}$ and $u\in{\cal U}.$ Thus for any policy $\pi$ there is a policy $\pi^{\prime}$ which uses randomized URLLC placement and achieves the same long term throughputs. It follows that ${\cal C}\subset{\cal C}^{LR}$ and so ${\cal C}={\cal C}^{LR}.$

-B Proof of Theorem 2

Under a policy ${\bm{\pi}}=({\bm{\phi}}^{\bm{\pi}},{\bm{\gamma}}^{\bm{\pi}})\in\Pi^{H,\delta}$ we have that the induced loads are given by

where the last equality follows from the uniformity of URLLC splits and normalization it follows that

-C Proof of Lemma 1

Recall that convex loss functions are specified as follows

with $h^{s}_{u}:\rightarrow$ a convex increasing function. For time-homogenous policies we have defined

Recall that convex function $h(\cdot)$ one can define a function $l(\phi,\gamma)=\phi h(\frac{\gamma}{\phi})$ known as the perspective of $h(\cdot)$ which is known to be jointly convex in its arguments. It follows that $\phi-\phi h(\frac{\gamma}{\phi})$ is jointly concave, and so is $g^{s}_{u}(\cdot)$ since it is a weighted aggregation of jointly concave functions.

For threshold-based loss functions where $t^{s}_{u}(\phi^{s}_{u})=\alpha^{s}_{u}$ we have that

Now using the same result on the perspective functions of variables the result follows. The truncated Pareto case can be easily verified by taking derivatives.

-D Proof of Theorem 3

Clearly ${\cal C}^{H,\delta}\subset{\cal\hat{C}}^{H,\delta}.$ We will show that ${\bf c}\in{\cal\hat{C}}^{H,\delta}$ then their exists ${\bm{\pi}}=({\bm{\phi}}^{\bm{\pi}},{\bm{\gamma}}^{\bm{\pi}})\in\Pi^{H,\delta}$ such that ${\bf c}\leq{\bf c}^{{\bm{\pi}}}$ from which it follows that ${\cal C}^{H,\delta}\subset{\cal C}^{H,\delta}.$

Suppose ${\bf c}\in{\cal\hat{C}}^{H,\delta}$, then it can be represented as a convex combination of policies $\Pi^{H,\delta}$, in each channel state. For example suppose for simplicity that for that in channel state $s\in{\cal S}$ we have that $\lambda\in$ one time shares between two policies ${\bm{\pi}}_{1}$ and ${\bm{\pi}}_{2}$ to achieve throughputs for $u\in{\cal U}$ given by

where $\phi^{{\bm{\pi}},s}_{u}=\lambda\phi^{{\bm{\pi}}_{1},s}_{u}+(1-\lambda)\phi^{{\bm{\pi}}_{2},s}_{u}$ and $\gamma^{{\bm{\pi}},s}_{u}=\lambda\gamma^{{\bm{\pi}}_{1},s}_{u}+(1-\lambda)\gamma^{{\bm{\pi}}_{2},s}_{u}$. Clearly ${\bm{\phi}}^{\bm{\pi}},{\bm{\gamma}}^{\bm{\pi}}$ as given above correspond to a policy $\bm{\pi}$ such that $\bm{\pi}\in\Pi^{H,\delta}$ since the set is convex. It also follows that $r^{s}_{u}\leq r^{{\bm{\pi}},s}_{u}$, so ${c^{s}_{u}}\leq{c}^{{\bm{\pi}},s}_{u}$ and so ${\bf c}\leq{\bf c}^{{\bm{\pi}}}.$

-E Proof of Theorem 4

The proof requires intermediate lemmas, detailed below. For the ease of exposition, let us define $U(\bm{r}):=\sum_{u\in\mathcal{U}}U_{u}(r_{u})$ and \nabla U\left(\bm{r}\right):=\left(\frac{\partial U_{1}(x)}{\partial x}\Bigr{|}_{x_{1}=\begin{subarray}{c}r_{1}\end{subarray}},\frac{\partial U_{2}(x)}{\partial x}\Bigr{|}_{x_{2}=\begin{subarray}{c}r_{2}\end{subarray}},\ldots,\frac{\partial U_{1}(x)}{\partial x}\Bigr{|}_{\begin{subarray}{c}{x_{\left|\mathcal{U}\right|}=r_{\left|\mathcal{U}\right|}}\end{subarray}}\right)^{T}. First we have the following important lemma regarding the stochastic approximation algorithm.

$\bm{R}(t)=\left(R_{1}(t),R_{2}(t),\ldots,R_{\left|\mathcal{U}\right|}\right)^{T}$ is an unbiased estimator of $\underset{\bm{c}\in\mathcal{C}^{H,\delta}}{\text{argmax: }}\nabla U\left(\bm{\overline{R}(t)}\right)^{T}\bm{c}$, i.e.,

Based on the definition of $\mathcal{C}^{H,\delta}$ we can re-write $\underset{\bm{c}\in\mathcal{C}^{H,\delta}}{\text{max: }}\nabla U\left(\bm{\overline{R}(t)}\right)^{T}\bm{c}$ as follows:

The main intuition behind the proof of optimality is that for large $t$, the trajectories of $\overline{\bm{R}}(t)$ can be approximated by the solution to the following differential equation in $\bm{x}(t)$ with continuous time $t$:

Let us define $q(\bm{x}):=\underset{\bm{c}\in\mathcal{C}^{\mathcal{H},\delta}}{\text{argmax: }}\nabla U\left(\bm{x}\right)^{T}\bm{c}$. To show the optimality of our online algorithm, we shall also require the following result on the above differential equation.

The differential equation (35) is globally asymptotically stable. Furthermore, for any initial condition $\bm{x}(0)\in C^{\mathcal{H},\delta}$, we have that $\lim_{t\rightarrow\infty}\bm{x}(t)=\bm{r}^{*}$.

To prove this lemma it is enough to show that there exists a Lyapunov function $L(\bm{x}(t))$ such that it has a negative drift when $x(t)\neq\bm{r}^{*}$ and has zero drift when $x(t)=\bm{r}^{*}$. Define $L(\bm{x})=U(\bm{r}^{*})-U(\bm{x})$. Observe that under our assumption of strictly concave $U_{u}(\cdot)$, the offline optimization problem is guaranteed to have an unique optimal solution, which is $\bm{r}^{*}$. Therefore, $\forall\bm{x}\in C^{\mathcal{H},\delta}$ and $\bm{x}\neq\bm{r}^{*}$ $L(\bm{x})>0$. Next we will compute the drift of $L(\bm{x}(t))$ with respect to time.

To get inequality (38), first observe that from the definition of $q(\bm{x(t)})$ and (37), we get that $\frac{dL(\bm{x}(t))}{dt}\leq 0$. However, we have to show that this inequality is strict for $\bm{x}(t)\neq\bm{r}^{*}$. Observe that $q(\bm{x})=\bm{x}$ is a necessary and sufficient condition for optimality of the offline optimization problem, see for more details. From strict concavity of the utility functions, we have an unique optimal point $\bm{r}^{*}$. Therefore, $\frac{dL(\bm{x}(t))}{dt}<0$ for $\bm{x}(t)\neq\bm{r}^{*}$ and $\frac{dL(\bm{x}(t))}{dt}=0$ at $\bm{x}(t)=\bm{r}^{*}$. ∎

To conclude the proof, Lemmas 2 and 3 along with the condition 3 satisfy all the conditions necessary to apply Theorem 2.1 in Chapter 5, which states that $\bm{\overline{R}}(t)$ converges to $\bm{r}^{*}$ almost surely.

-F Proof of Theorem 5

We shall first consider a hypothetical non-casual scenario and show that there exists an optimal joint scheduling policy with minislot-homogeneous URLLC placement policy which in general is a function of the aggregate URLLC load in an eMBB slot. We then upper bound the optimal value of $\mathcal{OP}_{1}$ by the solution to a hypothetical non-causal scenario described in the sequel.

Secondly, under Assumption 4 on the loss functions, we show that there exists an URLLC placement policy policy which is minislot-homogeneous but independent of the aggregate URLLC load for the hypothetical non-causal scenario. We then conclude that there exists an optimal minislot-homogeneous joint sceduling policy for $\mathcal{OP}_{1}$ as an upper bound for its value is attained by a minislot-homogeneous joint scheduling policy.

First let us describe the non-causal scenario. At the beginning of each eMBB slot, first the scheduler chooses $\phi^{\pi,s}$. Next the total URLLC demand in each minislot is revealed, i.e., the realizations of $D(1),D(2),\ldots,D({\left|\mathcal{M}\right|})$ are revealed. Therefore, this setting is not causal as it assumes knowledge about future URLLC demand realizations. In general the URLLC placement under the non-causal setting is dependent on the minislot index $m$ and $\bm{D}^{\left(1:\left|\mathcal{M}\right|\right)}$. With slight abuse of notation, we shall denote it by $\gamma_{u,m}^{s}\left(\bm{D}^{\left(1:\left|\mathcal{M}\right|\right)}\right)$. The joint scheduling policy has to satisfy the constraints (16), (17), and (18). We have the following lemma on the non-causal setting.

There exists an optimal minislot-homogeneous policy for the non-casual setting such that the URLLC placement depends only on the total URLLC demand in an eMBB slot, i.e., $\sum_{m=1}^{\left|\mathcal{M}\right|}D_{m}$.

Note that with the definition of $\nu_{u}^{s}$, the total puncturing experienced by an eMBB user $u$ in an eMBB slot is $\nu_{u}^{s}d$. From this one can construct an equivalent minislot-homogeneous URLLC placement policy. For all minislots, use $\nu^{s}$ as the URLLC placement factor. This satisfies the constraints (16), (17), and (18). In general $\nu^{s}$ could depend on $d(1),\,d(2),\,\ldots,d({\left|\mathcal{M}\right|})$. However, we will show that the optimal solution depends only on the sum $\sum_{m=1}^{\left|\mathcal{M}\right|}d_{m}$.

Let $d^{\prime}(1),\,d^{\prime}(2),\ldots,\,d^{\prime}({\left|\mathcal{M}\right|})$ be such that $\sum_{m=1}^{\left|\mathcal{M}\right|}d_{m}^{\prime}=d$ and there exists an $m$ such that $d^{\prime}(m)\neq d(m)$. Define the following:

Therefore, the total puncturing observed by $\nu_{u}^{\prime s}d$. Observe that $\nu^{\prime s}$ is also a feasible URLLC policy for the case when the URLLC demand realizations are $d(1)$, $d(2),\,\ldots,\,d({\left|\mathcal{M}\right|})$. Similarly $\nu^{s}$ is also a feasible URLLC placement policy for the case with $d^{\prime}(1)$, $d^{\prime}(2),\,\ldots,\,d^{\prime}({\left|\mathcal{M}\right|})$. Therefore, the optimal solution has to be independent of the realizations of $D(1),\,D(2),\ldots,D({\left|\mathcal{M}\right|})$ and depends only on the sum $\sum_{m=1}^{\left|\mathcal{M}\right|}D_{m}$. ∎

Therefore, we shall restrict ourselves to minislot-homogeneous policies in the non-causal setting with the URLLC placement as a function of the total URLLC demand for that eMBB slot. With slight abuse of notation we shall denote a URLLC placement policy in this setting by $\gamma_{u}^{s}\left(\cdot\right)$ with the only argument as the total URLLC demand in that eMBB slot. This procedure is formally described next.

At the beginning of an eMBB slot, the joint scheduler chooses $\phi_{u}^{\pi,s},u\in\mathcal{U}$ such that

The total URLLC demand $D=\sum_{m=1}^{\left|\mathcal{M}\right|}D(m)$ in that eMBB slot is revealed.

For an URLLC demand of $D$, $\gamma_{u}^{\pi,s}(D)$ is chosen such that

Let us denote the feasible policies for this hypothetical non-causal scenario by $\Pi^{\dagger}$. $\left(\bm{\phi^{\pi,s}},\bm{\gamma^{\pi,s}}\right)$ is chosen as the solution to the following optimization problem.

This directly follows from the proof of Lemma 4 where we have shown that any URLLC placement factor $\bm{\gamma}_{u}^{\pi,s}$ can be transformed into a minislot-homogeneous policy which depend only on the total URLLC demand in an eMBB slot, and hence, any feasible solution for $\mathcal{OP}_{1}$ is a feasible solution for $\mathcal{OP}_{2}$. ∎

-F2 Existence of an optimal solution independent of the value of D𝐷D

In general the optimal URLLC placement policy under $\mathcal{OP}_{2}$ may depend on the total URLLC demand in an eMBB slot. However, under the Assumption 4 it is independent of the total URLLC demand. This is stated formally in the following lemma.

Under Assumption 4, there exists an optimal solution $\left(\bm{\phi}^{*,s},\bm{\gamma}^{*,s}\left(\cdot\right)\right)$ for $\mathcal{OP}_{2}$ with URLLC placement policy ($\bm{\gamma}^{*,s}\left(\cdot\right)$) independent of $D$.

If $\left(\bm{\phi}^{*,s},\bm{\gamma}^{*,s}\left(\cdot\right)\right)$ is an optimal solution to $\mathcal{OP}_{2}$, then $\bm{\gamma}^{*,s}\left(\cdot\right)$ must also be an optimal solution to the following optimization problem in $\bm{\gamma}^{s}:=\left(\gamma_{1}^{s}(\cdot),\gamma_{2}^{s}(\cdot),\ldots,\gamma_{\left|\mathcal{U}\right|}^{s}(\cdot)\right)$.

For any $d$ and $u$, from the K.K.T. conditions for the above optimization problem, we have that

where h_{u}^{s^{\prime}}(x)=\frac{dh_{u}^{s}(y)}{dy}\Bigr{|}_{\begin{subarray}{c}y=x\end{subarray}},$\beta(d)$ is an arbitrary constant (function of $d$) and $\eta_{u}(d)$, $\nu_{u}(d)$ and $\lambda_{u}(d)$ are constants such that

We have shown in Lemma 6 that there exists an optimal policy $\left(\bm{\phi^{*,s}},\bm{\gamma^{*,s}}\right)$ which is a minislot-homogeneous policy and independent of the realization of $D$. In Lemma 5, we have also shown that the optimal value of $\mathcal{OP}_{2}$ is an upper bound for $\mathcal{OP}_{1}$. Hence, there exists a minislot-homogeneous policy which achieves an upper bound for $\mathcal{OP}_{1}$. Therefore, there exists a minislot-homogeneous policy which is optimal for $\mathcal{OP}_{1}$.

-G Proof of Theorem 6

Let $\mathcal{S}_{k}$ be the set of all subsets with $k$ elements chosen from the set $\left\{1,2,\ldots,m_{1}+m_{2}\right\}$. For example, if $m_{1}+m_{2}=3$ and $k=2$, then $\mathcal{S}_{k}=\left\{\left\{1,2\right\},\left\{2,3\right\},\left\{1,3\right\}\right\}$. Note that $\left|\mathcal{S}_{k}\right|=\binom{\left|\mathcal{M}\right|}{k}$. Using the above definitions, we can re-write the R.H.S. of (23) as follows:

Using the above expression one can apply Jensen’s inequality on the R.H.S. of (23), we have that

Since $D_{m}$’s are i.i.d. the R.H.S. of the above expression is same as the L.H.S. of (23). Hence, proved.

-H Proof of Theorem 7

Clearly the probability of loss depends on the minislot demands and the users thresholds. If one relaxes the sequential constraint on URLLC allocations, one can consider aggregating the the minislot demands and pooling together the users superposition/puncturing thresholds. The probability of loss for this relaxed system is simply the probability the demand exceeds the size of the superposition/puncturing pool, i.e., The probability of loss under the pooled resources is given by

This is clearly a lower bound for any placement policy. Note however that the threshold proportional strategy meets this bound from Corollary 3 (see Equation (26)) so it indeed minimizes the probability of loss on a given eMBB slot.