1 Delay Estimation and Fast Iterative Scheduling Policies for LTE Uplink Akash Baid(Rutgers), Ritesh Madan(Qualcomm), and Ashwin Sampath(Qualcomm) Abstract—We consider the allocation of spectral and power contiguousbandwidthallocationisconsidered,theproblemof 2 resourcestothemobiles(i.e.,userequipment(UE))inacellevery maximizingtheweightedsumrateineachsubframeontheUL 1 subframe(1 ms) for theLong Term Evolution (LTE)orthogonal can be posed as a constrained convex optimization problem. 0 frequency division multiple access (OFDMA) cellular network. For N users and M sub-bands general purpose methods 2 To enable scheduling based on packet delays, we design a novel mechanism for inferring the packet delays approximately from can solve the problem in O((NM)3). With peak UE power n the buffer status reports (BSR) transmitted by the UEs; the constraints,aO(NM)periterationsubgradientalgorithmwas a J BSR reports only contain queue length information. We then obtainedin[9];heuristicstocomputeallocationswithintegral 6 consider a constrained optimization problem with a concave number of resource blocks (RBs) were considered as well. objective function – schedulers such as those based on utility 1 Interior point methods (which have faster convergence) with maximization,maximumweightscheduling,andrecentresultson iterativeschedulingforsmallqueue/delayfollowasspecialcases. an O(NM2) (if N >> M) Newton iteration were obtained ] C Inparticular,theconstructionofthenon-differentiableobjective in[10]foruplinkresourceallocationwithadditionalfractional function based on packet delays is novel. We model constraints power control constraints. However non-differentiable objec- O on bandwidth,peak transmitpower attheUE,andthetransmit tivefunctionsarenotconsideredundertheframeworkin[10]. . power spectral density (PSD) at the UE due to fractional power h Also relevant to our paper are recent results on low com- control.Whenfrequencydiversitydoesn’texistorisnotexploited at at a fast time-scale, we use subgradient analysis to construct plexity iterative scheduling algorithms. Many papers prior to m an O(NlogL) (per iteration with small number of iterations) these results had considered scheduling to maximize the sum algorithmtocomputetheoptimalresourceallocationforN users ofweightedratesinsubframen,wheretheweightswerebased [ andLpointsofnon-differentiabilityintheobjectivefunction.For on the arrivals and departures in the queue of a user until 1 a frequency diversity scheduler with M sub-bands, the corre- v spondingcomplexityperiterationisessentiallyO(N(M2+L2)). subframe n−1. The iterative policies in [11], [12] take into 5 Unlike previous iterative policies based on delay/queue, in our account how the weights change in subframe n to determine 1 approach the complexity of scheduling can be reduced when the resource allocation in that subframe. In particular, the 2 the coherence bandwidth is larger. Through detailed system queue based server side greedy (SSG) rule is proposed for 3 simulations(basedonNGMNand3GPPevaluationmethodology) multi-ratechannelsin[12]andadelaybasedrulewithiterative 1. wdehpilcohymmeondt,elreaHli-sAtiRcQtr,affifinci,tepowreesroulirmceitagtiroannst,sinpteerrfesruebn-cfer,aamned, matchingineachsubframeforON-OFFchannelsisconsidered 0 channel fading,we demonstratetheeffectiveness of our schemes in [11]. The results in these papers shed a remarkable insight 2 for LTE. that when the rate grows linearly with bandwidth (no peak 1 power constraints at the transmitter), as the number of users : v in the system grow, these rules lead to much smaller per- i I. INTRODUCTION user queues and delays, respectively, compared with previous X Wideband cellular systems such as LTE allow for resource approaches.However,thecomplexityofthesealgorithmsgrow r a allocation with high granularity of a resource block (RB) with the resourcegranularityevenif the coherencebandwidth of 1 ms by 180 KHz [1]. While control signalling and the does not grow. In this paper, we construct a continuous but generalframeworkforthephysicalandmediumaccesscontrol non-differentiable concave reward function based on packet (MAC) layers is specified to enable efficient use of spectral delays. We argue that the matching algorithm in [11] is an resources, the exact resource allocation algorithms for power approximate algorithm to maximize this reward function in and frequencyallocation can be designed by an implementor. every subframe. Moreover,eachcellcanserveontheorderofathousandactive Motivated by the above observation, we consider re- connections over a bandwidth of 20 MHz. Hence, in order to source allocation to maximize a continuous (possibly non- takeadvantageoftheflexibilityallowedinresourceallocation, differentiable) concave reward function. We first consider a the resource allocation algorithmshave to be computationally channelmodelwherethechannelgaininthefrequencydomain simple. Many schedulers in the literature entail maximizing is flat and formulate the resource allocation problem as a the weighted sum of rates in each subframe. For example, non-differentiable convex optimization problem. Note that in the weights could be based on utility functions of average typical cellular environments, the channel gains can be fairly rate [2], [3], the queue length [4], [5], or head-of-line de- correlated even for frequencies 2 to 5 MHz apart [13] – lay[6],[7].Intheuplink,theresourceallocationproblemmust hence,the assumptionof frequencyflat fadingis a reasonable considerthemaximumtransmissionpowerofamobileandthe one when the total bandwidth is up to 5 MHz (28 RBs) constraints on the transmission power imposed by fractional or lower, or if the UEs are allocated to sub-bands (< 5 power control to limit inter-cell interference [1], [8]. When MHz) over a slower time-scale based on interference and 2 channel statistics. The above assumption allows us to use sub-bands satisfy [10]: M subgradient analysis to design algorithms with O(NlogL) p ≤γ b ,∀i,j, p ≤P, costperiteration(withsmallnumberofiterations)forN users ij ij ij ij and L pointsof non-differentiabilityin the objectivefunction. where b is the bandwidth allocateXj=d1to UE i on sub-band j ij We discuss implementation issues for the resulting algorithm and γ is a sub-band specific constant. ij inapracticalLTEsystemwithH-ARQre-transmissions,finite The interference PSD at the serving base-station on sub- numberofresourcegrantspersubframe,andtheconstraintthat band j (denoted as I ) can be measured by the base-station j all uplink transmissions have to be over a contiguous set of periodically over unassigned frequency resources. The value RBs. Notably, we also design a novel mechanism to estimate dependson the interferencecoordinationalgorithmused [24]. head-of-linedelaysof queuesatUEswith low complexityvia When a UE transmits with power p over bandwidth b on ij ij only queue length information contained in the buffer status sub-band j, it achieves a rate given by (treating interference reports (BSR). We note our techniques are equally applicable as noise) G p for enabling delay based scheduling in the PCF and HCF b ψ ij ij ij b I modes in WiFi [14]. We demonstrate the improvement in (cid:18) ij j (cid:19) where ψ : R 7→ R is an increasing concave and differen- performance due to our techniques through numerical results + + tiable function which maps the SINR to spectral efficiency. obtained via comprehensive numerical simulations based on 3GPP evaluation methodology [15]. Finally, when frequency selective fading is considered, we show how interior point B. Control Signaling methods with complexity of O(NM2 + NL2) per Newton Single carrier frequency division multiple access (SC- iteration can be obtained; note that in practice N >> L,M. FDMA) is used in the LTE uplink [1] and so a UE can be Since, we consider non-differentiable cost functions, this re- granteda numberof 180kHz resourceblocksin a contiguous quiresadditionalanalysiscomparedtothatin[10]whereonly manner in frequency. The resource allocation to the UEs is differentiable cost/utility functions were considered. computed by the base-station every subframe (1 ms) and Priorworkindevisingpracticalresourceallocationschemes signalled to the UEs via resource grants which include the fortheLTEuplinkincludes:[16]considersallocationoffixed contiguoussetofRBs allocatedtotheUE andthemodulation sizeresourcechunkstoUEs,[17]extendsthisapproachwhere and coding scheme (MCS). The timeline is as follows: a each (RB,UE)-tupleis associated with a metric (whichcannot resource grant is made to the UE at time t for an uplink capture power constraint at power limited UE), a similar transmission at time (t+4). At time (t+8) the base-station (RB,UE) metric is considered in [18]. These methods do not transmits an ACK/NACK to indicate if it could decode the extend to solving a general resource allocation problem con- packet; if a NACK is received by the UE, it re-transmits at sideredinthispaper.Semi-persistentschedulingforvoiceover the same poweranduses the same RBs at time (t+12)(asat IP (VoIP) has been considered in, for example, [19]. In [20] time (t + 4)). We assume a constant number of maximum heuristics for maximizing utilities of UEs in each subframe allowable re-transmissions for all UEs and do not adapt in the presenceof frequencyselective fadingbutno fractional the re-transmission power and resource assignment through power controlwere considered.Similarly, heuristics to satisfy additional control signalling available in LTE. minimum rate constraints of most users and maximize the Buffer status report(BSR) and scheduling request (SR) are sum rate were consideredin [21], heuristicsto maximize sum transmitted by the UEs to inform the base-station about new weighted rate were designed in [22], and algorithms for long packet arrivals at the UE. We describe the mechanism for the term proportional fairness were considered in [23]. special case of single logical channel (LC), or connection, at each UE. SR is one bit of information used to indicate the arrival of packets in an empty buffer at the UE. Each II. SYSTEMMODEL UE periodically gets an opportunity to send SR, and the A. Channel Model, Power, Rate time interval between two successive opportunities for SR is denoted by TSR, and is assumed to be fixed in a cell. BSRs We focus on the uplink of a single cell in LTE with N contain a quantized value of the number of bytes pending UEs and the total bandwidth divided into M sub-bands of transmission at the UE1, and are generated in two different equalbandwidthB,withB lessthanthecoherencebandwidth ways: Regular BSR: If the queue is empty in subframe t, of each user. The maximum transmit power of each UE is and new packets arrive in subframe t+1, a regular BSR is P. The channel gain for UE i on sub-band j is Gij; we generated at time t+1. When a regular BSR is generated, a focus on the scheduler computation in a subframe, and don’t SR is transmitted at the next available SR opportunity unless explicitly show the dependence of quantities on time t. The resources are granted to the UE between the BSR generation base-station can measure the G s via decoding the sounding ij and the opportunityto transmit SR. Periodic BSR: A periodic reference signal (SRS) [1]. Fractional power control in LTE BSRisgeneratedeveryTBSR subframes.AperiodicBSRthus limits the amountof interferencea UE causesat base-stations generated is transmitted by the UE to the base-station at the in neighboring cells. A UE which is closer to the cell edge earliest subframe after generation when resources are granted inverts a smaller fraction of the path loss to the serving to it by the base-station. base-station than a UE which is closer to the serving base- 1WeignoretheeffectofquantizationinBSR,butthemethodsinthispaper station [8]. Thus the transmit powers of a UE on different extendeasilytoquantized BSR. 3 analysis offers a computationally efficient method to imple- ment the scheduling policy in [3] for the LTE uplink with fractional power control; also note that it is easy to show that the rate vectorsin the uplinkresource allocation problem satisfy the conditions required for the results in [3]. B. Delay QoS Traffic Fig.1.Uplinktimeline Here the user experienceis a functionof the packetdelays. Userexperienceisacceptablewhenthepacketdelaysarelower than a certain tolerable value. The packet arrival process is A typical sequence of transmissions is shown in Fig. 1. assumed to be independent of the times at which the packets The buffer at a UE is empty in subframe (t−1) and a 1000 areserved.Trafficforapplicationssuchasvoicecallsandlive byte packet arrives in subframe t. The next SR opportunity video chatting fall in this category. is subframe (t+2) – the SR transmission by the UE signals At time t, let π (t) be the number of packets in the queue i to the base-station that the buffer at the UE is non-empty. ofUEi.Denotethesizesandthedelaysoftheseπ (t)packets i In response, the base-station allocates resource to the UE on by{s (1),...,s (π (t))}and{d (1),...,d (π (t))}.Thenfor i i i i i i the uplink via a grant at time (t + 5) – the actual uplink a UE i with delay QoS traffic, we define the reward function transmissionoccurs4subframeslater,i.e.,insubframe(t+9). as: This transmission includes the BSR report. Assume that the nsierv(ri) UE is allocated enough resources to also transmit 200 bytes f (r )= s (j)d (j) i i i i of the data packet – then the BSR report will contain a j=1 value of 800 bytes for the left-over data at the UE. The first X (3) transmission is unsuccessful – this is indicated by a NACK nsierv(ri) + r ∆− s (j) d (nserv(r )+1) transmitted by the base-station at time (t + 13). The UE  i i  i i i j=1 re-transmits the packet at time (t +17) – this transmission X   is decoded successfully by the base-station, and hence it where∆isthelengthofasubframe(1ms)andnserv(r )isthe i i is known at the base-station that 800 bytes were pending numberofpacketsfromUEiservedfullyifUEiisscheduled transmissionat the UE at time (t+9)whichis the time when at rate r , i.e., i the BSR report was created. nserv(r )=max k : k s (j)≤r ∆ . i i j=1 i i Lemma 3.1: fni(ri)Pis a continuous cooncave function. III. REWARD FUNCTIONS Proof: Concavity follows from the observation that In this section, we define the reward functions that we use di(1) > ... > di(πi(t)) and continuity is immediate from for the optimization problem and relate it to the schemes definition. used in earlier works. We assume each UE to have one active 2500 LC which supports either best effort or delay QoS traffic. 2000 slope = 0.03 A.ABeflsotwE,fifo,rwthich is best-effortis associated with an average reward (msKb)11050000 slope =s l0o.p7e6 = 0.27 rate x (t)∈R in subframe t which is updated as follows: i + 500 slope = 0.12 x (t+1)=(1−α )x (t)+α r , ∀t≥0, (1) i i i i i 0 0 1 2 3 4 5 6 where r is the rate at which UE i is served in the current rate (Kbps) x 104 i subframe, and 0 < α < 1 is a user specific constant. i Fig.2.Examplerewardfunction fordelayQoSflow. The user experience in subframe t is modeled as a strictly concave increasing function Ui :R+ 7→R of the average rate Example: Consider a UE with delay QoS traffic and four xi(t). Traffic for applications such as file transfer and web packets in the queue with delays (in ms) at time t given by browsingcanbemodeledbybesteffortflows,andistypically d = 120,d = 76,d = 27,d = 3, and packet sizes (in 1 2 3 4 transferredovera TCP connectionwhich hasclosed loop rate KB) are s = 1.5,s = 0.7,s = 2.1,s = 3. Then the 1 2 3 4 control. We greedily maximize the total utility at each time- corresponding reward function f is shown in Fig. 2. i step, i.e., the reward function for UE i with best efforttraffic, at time t is [25] C. Iterative Queue and Delay Based Policies 1 f (r )= U ((1−α )x (t)+α r ). (2) If we restrict the model in [11] to frequency flat fading, i i i i i i i α i i.e., a user is either connected to no server or all servers at Ifwesetf (r )=U′(x (t))r ,andletα →0inequation(1), any time, the algorithm in that paper can be interpreted as i i i i i the resulting scheduler is identical to that in [3]. Thus, our one which approximately maximizes the reward function in 4 equation (3). Specifically, the matching algorithm reduces to is the time at which the first BSR was generated, and so on. onewhereineachiterationa serverisallocatedtoa userwith C (t) denotesthe numberof bytesscheduledfor transmission i the highest head-of-line delay times spectral efficiency – this fromUEi,Cˆ (t)thenumberofbyteswhichweresuccessfully i approximately equalizes the head-of-line delay times spectral receivedfromUE i, and F (t) the numberof bytesthat failed i efficiency for all users after the allocation, which (as we will the final re-transmission for UE i, at time t. show) is the optimality condition to maximize the reward We maintainthe history of estimated queuelength for each function in (3) when divisible servers are considered. Larger UE i for duration Tretx, denoted by Q (t−Tretx : t). Then, i the number of servers the same bandwidth B is divided into, we update the Q matrix and the arrival vector A, at each t as theclosertheapproximation.Notethatpeakpowerconstraints follows: are not modeled in [11]. When frequency selective fading is For every t, i considered,i.e.,ausermaybeconnectedtoasubsetofservers 1) Scheduled Bytes: Q (t)=Q (t−1)−C (t). i i i in the model in [11], there is a sequence of maximum weight 2) Failed Bytes: Q (t)=Q (t)+F (t). i i i matchingswhichwillapproximatelycomputeasolutionwhich 3) BSR report: If a BSR report is received at time t, i.e., maximizes the reward function in (3). Motivated by this there is n such that τ (n) = t, then update queue state i interpretation, we consider the maximization of the reward asfollows:Ifthe base-stationhasnotreceivedanyBSR function in (3) for a much more general model with multiple report created after time t−δ (n), then i rate options, peak power constraints, and different transmit PSD constraints on different sub-bands. We also note that Qi(t−δi(n):t)=Qi(t−δi(n):t)+Ai(t−δi(n)) the complexity of the algorithm in [11] is O(NR2) for N where arrival A (t −δ (n)) = B (t) −Q (t − δ (n)) i i i i i users and R RBs – when there are multiple RBs in each sub- otherwise for band of bandwidth B, the complexity of our algorithms is lower. Finally, similar connections can be drawn between the argmin [τ (m)−δ (m)−(τ (n)−δ (n))] i i i i schemein[12]forfrequencyflatfadingandusinganobjective {m: τi(m)<t} function based on sums of squares of queues as in [26]; the update connections for the frequency selective fading case seem to A (t−δ (n))=B (t)−Q (t−δ (n)) exist but are harder to analyze. i i i i i A (τ (m)−δ (m))=A (t−δ (m))−A (t−δ (n)) i i i i i i i IV. ESTIMATION OFPACKET DELAYS Q (t−δ (n):τ (m)−δ (m)−1) i i i i We now describe a method to infer approximate packet =Q (t−δ (n):τ (m)−δ (m)−1)+A (t−δ (n)) i i i i i i delays at the eNB via the mechanisms available in LTE. We Note that Q can have negative entries. i use the SR and BSR report generated at the start of the burst of packets, and periodic BSR reports which are generated V. FREQUENCY FLATFADING regularly but transmitted only when resources are allocated to theUE (see Sec. II-B), alongwith theschedulingdecisions Here, we consider the resource allocation to N UEs over a made by the base-station to estimate packet delays. The main single sub-band with bandwidth B and frequency flat fading. intuition is as follows: if the base-station estimates the queue We dropthedependenceofquantitiesinthegeneralmodelon lengthattimettobesay,1000bytes,butlaterdecodesaBSR the sub-band j – for example, we denote channel gain from which was created at time t and has value 1300 bytes, the UE i to the eNB as Gi. We allow for contiguous allocation base-station can deduce that 300 bytes arrived between time – this is a reasonable approximation when B is larger than t and the time at which the previous BSR was created. This a few RBs. Rounding techniques in, for example, [9] can be informationaboutthetimeintervalduringwhichthe300bytes used to obtainintegralsolutions.The optimizationproblemto arrivedcanbeusedformakingresourceallocationdecisions– maximize the sum of rewards for all UEs over the bandwidth specifically,schedulingpoliciesbasedonpacketdelayscanbe allocation vector b∈RN in a subframe is: + implemented.The main complexityis due to re-transmissions N which can lead to the BSR report arriving out of order at the max. f b ψ Gimin(γibi,P) i i basLee-tstTatrieotxn.be the maximumamountof time betweenthe first Xi=1 (cid:18) (cid:18) INbi (cid:19)(cid:19) (4) transmissionof a MACpacketand thelatest time whenit can s.t. 0≤b ≤bmax, ∀i, b ≤B i i i be re-transmitted for H-ARQ (for example, if we configure i=1 X 6 as the maximum number of re-transmissions, Tretx = 48 wherebmaxisthemaximumbandwidththatUEicanusebased subframes). We estimate the number of bytes that arrived, i on the estimated queue length, Q (t), for UE i, and satisfies: i A (t)ineachsubframet.Thebufferstatusreportsaredenoted i by a sequence of random three tuples: bmaxψ Gimin(γibmiax,P) =Q (t)/∆ i Ibmax i {B (1),τ (1),δ (1)},{B (2),τ (2),δ (2)},... (cid:18) i (cid:19) i i i i i i where we recall that ∆ is the length of a subframe (1 ms). where B (1) is the buffer size reported in first BSR, τ (1) is Since, the function on the left is an increasing function of i i the time at which first BSR was received, and (τ (1)−δ (1)) bmax, we can compute bmax efficiently via a bisection search. i i i i 5 Problem (4) is a convex optimization problem (with non- Proof: The lemma follows from standard arguments in, differentiable objective function) due to the lemma which for example [27], the definitions of f ’s, and that the subdif- i follows. ferential of f for delay QoS user i is given by i Lemma 5.1: The objective function in optimization prob- d (nserv+1), nsierv(ri⋆)s (j)<r⋆∆ lem (P4r)oiosf:coCnocnasviedeinr tthheefbuisncftoiornbig≥:0R,+fo7→r alRl i+. defined by ∂fi(ri)=( [dii(nisierv),di(nsierv+1)], Pjnj==ser11v(ri⋆)sii(j)=rii⋆∆ g(x) = xψ(c/x), ∀x > 0,c ∈ R is constant. Since, ψ is + P assumed to be concave, it is easy to verify (via showing that Wenowevaluatethesub-differentialofh forx≥0,which i the second derivative is always negative) that g is concave as is bounded because γ is assumed to be bounded. i well. Since, (i) the sum of concave functions is concave, and (ii) the composition of one concave function with another is ψ Gi(It)γi , if x<P/γi concave, to show that the objective function is concave, it is  n (cid:16) (cid:17)o shu(fxfi)c=ienxtψto smhoiwn(ctxh1axt,tch2e)fo,llo∀wxi≥ng0f,ucn1c,tcio2n∈isRc+onacreavceonstant ∂hi(x)= nψψ(cid:16)GGii(I(txt))γPi(cid:17)−−GGii((xtt))PPψψ′′(cid:16)GGiiI((txt))γPi(cid:17)o, ,if x>P/γi (cid:18) (cid:19) I x I SNmionintcee{,xthψψa(tci1sth),eaxnψabi(noccv2r/eexaf)su}inn,gcwtifohunincchitsiioswnt,helewlmediencfiaimnneudwmrfiooterf txhw(ox≥)con=0-.  h (cid:16) ψ(cid:17)(cid:16)Gi(It)γi(cid:17)i, (cid:16)if x=P(cid:17)/γi cave functions, and hence, concave. 103 user 1 pkt 1 user 2 e A. Characterization of Optimal Solution ectiv λ pkt 4 bj biWtoeadchefiienveabalefurnactetiofonrwuhseicrhi:maps the bandwidth allocation ent of o102 pkt 1 pkt 2 pkt 3 di power hi(bi)=biψ(cid:18)GiminI(bγiibi,P)(cid:19) subgra limited pkt 5 Wedenotethesub-differentialofafunctiong :R7→Ratxby pkt 2 power ∂g(x). Forcontinuousconcavefunctionsoverthe setof reals, 101 limited 0 2 4 6 8 10 the subdifferentialat x is the set of slopes of lines tangent to number of RBs f at x. Let b⋆ ∈R denote the solution to the resource allocation Fig.3.Optimality condition + problem (4). The following lemma shows that an optimal We illustrate the optimality condition via a two user exam- allocation in a given subframe is one for which the following ple.Thetotalbandwidthtobesharedis10RBs,or1800KHz. quantities are equal for all users with non-zero bandwidth All packets are of size 500 bits. The packet delays of the two allocation: for best effort user, the marginal utility times the users in the given subframe are incremental rate when more bandwidth is allocated to it, and User 1: [450,330,135,80,20] for delay QoS user, the delay of the oldest packet which is not served completely times the incremental rate when more User 2: [170,150,140,110,80,20] bandwidth is allocated to it. The rate at which the users can be served as a functionof the Lemma 5.2: There exists a λ⋆ > 0 such that if i is best RBs are given by: effort, then b log 1+100.05 b ≤5∗180khz 1 2 1 λ⋆ ∈U′((1−α)xi(t)+αiri⋆)∂hi(b⋆i), if b⋆i >0 h1(b1)= b log 1+100.055∗180 b >5∗180khz λ⋆ <U′((1−α)x (t))min∂h (0), if b⋆ =0 ( 1 2(cid:0) (cid:1) b1 1 i i i b log (cid:16)1+100.4 (cid:17) b ≤8∗180khz 2 2 2 els•e,iiff i ijns=siedr1ve(rlai⋆y)sQi(ojS)<andri⋆b∆⋆i,>λ⋆0,∈di(nsierv(ri⋆)+1)∂hi(b⋆i) whhe2r(eb2t)he=5(anbd2l8ogR2B(cid:0)(cid:16)1th+re1s0h0o.l4d(cid:1)8s∗b1(28a0n(cid:17)d cobr2re>sp8on∗d1in8g0kShIzNRs • elsPe if jn=ser1v(ri⋆)si(j)=ri⋆∆ of0.5dBand4dB)arederivedfromfractionalpowercontrol constraints in Section II-A. The subgradient of the rewards λ⋆ ∈[Pd (nserv)min∂h (b⋆),d (nserv+1)max∂h (b⋆)] i i i i i i i i for both the users as a function of bandwidth allocation, and the optimal bandwidth allocation are shown in Fig 3 – the else, if i is delay QoS and b⋆ =0, i optimal resource allocation is 5 RBs to each user, and the λ⋆ <d (1)min∂h (0) optimaldualvariableλ⋆ isshownin thefigure.Foreachuser, i i the figure also shows the number of RBs required to fully where r⋆ =h (b⋆). serve a given number of packets and the number of RBs at i i i 6 whichtheuserbecomespowerlimited,i.e.,themaximumpeak λ≤λ⋆ ≤λ where powerconstraintlimits the transmission powerratherthan the G (t)γ i i fractional power control which limits the transmit PSD. λ= max ψ max∂f (0) i i=1,...,N I (cid:20) (cid:18) (cid:19) (cid:21) B. Computation of Optimal Solution G (t)P G (t)P G (t)P λ= ψ i − i ψ′ i The optimization problem (4) entails the maximization of IB B IB (cid:20) (cid:18) (cid:19) (cid:18) (cid:19)(cid:21) the sum of concave functions subject to a linear inequality Gi(t)P ×max∂f Bψ , for some i constraint.While, in principle,the optimalresourceallocation i IB (cid:18) (cid:18) (cid:19)(cid:19) scheme can be computed via a bisection search on the dual The main computational step in each iteration of Algo- variable λ, two difficulties arise: (i) There may be multiple rithm1entailssolving(5)N times–wenowshowthiscanbe values of b for which the subgradient of f ◦h is equal to i i i done in O(logL) time when the reward function f for user λ. See, for example,the first packet for user 1 in Fig. 3. As a i i is non-differentiable at at most L points. The composition result the dual functionis non-differentiableand the bisection of function f with h is a concave function as shown in search may not converge [28]. (ii) If λ belongs to the sub- i i Lemma(5.1).Hence,tocomputethebandwidthallocationfor differential at a point b of non-differentiability of either f i i UE i as given in equation (5), we can use a bisection on or h , the values of the gradient of f ◦h may be arbitrarily i i i b . First we obtain how many packets should be served fully differentat(b +ǫ)and(b −ǫ)foranarbitrarilysmallǫ. This i i i such that the corresponding bandwidth required, b , satisfies canalsobeseen inFig3.We useAlgorithm1tocomputethe i equation (5) in O(logL) time. Then, we compute b . optimal solution of problem (4). The convergence analysis is i We compute the range of subgradients for packet η as almostidenticalto thatin Sec. 6 in [28]. An accuratesolution can typically be computed in about 10 iterations. η−1s η s b=h−1 k=1 i , b=h−1 k=1 i i P∆ ! i (cid:18)P∆ (cid:19) (6) Algorithm 1: Bisection search for optimal λ SG(η)=d (η)[min∂h (b),min∂h (b)] i i i Given starting value of λ, λ, b, b and tolerance ǫ. wherewe recalld (η)ands (η) arethedelayandsize forηth repeat i i packet queued at UE i. Note that the inverse of h is simple Bisect: λ=(λ+λ)/2. i when b <P/γ ; otherwise it can be computed via bisection. Allocate bandwidth for all i: i i if λ>max∂f (0)max∂h (0) then i i set b =0. Algorithm 2: Bisection for Number of Packets i else Initialize: η =0 η =πi, where we recall πi is the b is such that number of packets queued at UE i. i repeat λ∈[min∂fi(ri)×min∂hi(bi), 1. Bisect: η = (η+η)/2 . (5) max∂f (r )×max∂h (b )] 2. Compute subgradient range SG(η) i i i i (cid:4) (cid:5) where 3. Update: If minSG(η)>λ, then η :=η, else if G (t)min(γ b ,P) maxSG(η)<λ, then η :=η, else η,η :=η. i i i r = b ψ i i Ib until η =η end (cid:18) (cid:18) i (cid:19)(cid:19) Update: if N b −B >0, λ=λ, b=b, else i=1 i λ=λ, b=b. Thenumberofpacketstobeservedcompletelyisη =η−1. P Now we show how to compute the bandwidth allocation b . i until |λ−λ|<ǫ Note that h has at most one point of discontinuity, say ˆb . If i i Feasible Solution: if ibi− ibi >0 then b ≤ ˆbi ≤ b for η = η −1 in (6), then bi = ˆb if λ/di(η) ∈ set α= B−Pibi . ∂hi(bˆi); else update b or b appropriately. Pibi−PibPi P else set α=0. Algorithm 3: Computation of RB assignment end Given tolerance µ, b, b. b=αb+(1−α)b repeat 1. Bisect: b=(b+b)/2. 2. Update: If h′(b)>λ/d (η), then b:=b, else if The starting values of λ and λ can be generated using i i h′(b)<λ/d (η), then b:=b. the following simple lemma (proof is straightforward and i i until |b−b|<η omitted); the values of b and b are obtained by repeating the Allocate Bandwidth step in Algorithm 1 for dual variables λ and λ, respectively. A similar methodcan be used for best efforttraffic and the Lemma 5.3: The optimal dual variable λ⋆ satisfies analysis is omitted here due to lack of space. 7 Parameter Value of 0.7 for the packet size distribution with varying values for ChannelProfile ITU-TPedA the truncation limits, so as to control the mean data rate. For MobileSpeed 3km/hr Log-NormalShadowing σ=8.9dBm example, to get a mean rate of 500 kbps, we fix the limits to Intra-site ShadowingCorrelation 1.0 [215 bytes - 1500 bytes]. Inter-siteShadowing Correlation 0.5 In order to map the optimal resource allocation computed CellRadius 1km No.ofUEs/cell 20 usingAlgorithm1toactualRBgrantsweuseaheuristicwhich No.ofRBs 110 ranks the users in decreasing order of marginal reward times MaxUETxPower 23dBm spectral efficiency when very small amount of bandwidth is No.ofTx&RxAntenna 1 given to the user. The RB allocation is then done in the order eNB&UEAntenna Gains 0dBi ThermalNoiseDensity -174dBm/Hz oftherank,witheachbandwidthamount(asperAlgorithm1) BSRperiodicity 5ms mapped to an available segment of closest size. max.numberofretransmission 6 TABLEI SIMULATIONPARAMETERS B. Results We consider two topologies for simulation: a macro-cell withthepathlossbetweenthebasestationandUEsrandomly selected between 100 dB and 135 dB [29], micro-cell with VI. SIMULATION RESULTS path loss in the range 107 dB to 115 dB. We simulate three A. Simulation Framework scheduling algorithms: (i) Iterative Delay which maximizes Thealgorithmsintheprevioussectionweresimulatedusing the reward function in Sec. III-B, (ii) Iterative Queue which a detailed system simulator where the MAC layer signalling minimizes sum-of-squares of queue lengths as in [26] and was modeled faithfully, and the PHY layer performance similar to [12], (iii) non-iterative maximum weight where a was abstracted via modeling of fading channels, transmission UE with thehighestqueuelengthtimesspectralefficiencyfor power,andcapacitycomputationsasin[29],[15].Ahexagonal first RB is allocated bandwidth until the queue is drained or regular cell layout with three sectors per site was simulated the UE becomes power limited before allocation to the next with the parameters as noted in Table I. For fractional power UE. We note that the computational algorithms in this paper controlparametervalues(P =−60dBm,α=0.6)similarto areapplicabletocomputingresourceallocationforscheduling 0 thosein[8],a19cell(57sector)simulationwithwraparound policies (i) and (ii), and that policies similar to (iii) do not wasfirstperformedtodeterminetheinterferenceoverthermal consider the change in reward function of the UE in a given (IoT) at the base-station of a cell to be 6 dB on an average. subframe. In subsequent simulations, only one cell was simulated with 1) Macro cell Topology: We consider 20 UEs with a mix the IoT assumed to be constant in time and frequency. This of live video and streaming video traffic. Since live video has drastically reduces the simulation time while still accounting a tighter requirementfor packetdelays, we bias the scheduler for the inter-cell interference. to assign live video users 5x priority compared to streaming The time varying channel gains, G ’s, were assumed to videousersforsamepacketdelay.Simulationswereperformed i be measured perfectly at the base-station in each subframe. for low load and high load cases: The MCS was picked on the basis of the channel gain from (1)HighLoad:5UEshavelivevideotraffic,eachwithamean the UE and a rate adaptation algorithm to target an average rate of 300 kbps. For the other 15 UEs with streaming video of two H-ARQ transmissions for successful decoding was traffic, we mimic an adaptive-rate streaming mechanism in used. We use the mutual information effective SINR metric whichthe datarate foreachuser dependsonthe qualityofits (MIESM) [30]; we first obtain the effective SINR according channeltothebase-station,i.e.auserclosetothebase-station to the modulation alphabet size and then use that value to transmits a better quality video compared to a cell-edge user. simulate an event of packet loss according to the packet Forsimulatinghigh-load,thetruncationparametersmentioned error rate for the effective SINR. We model the timelines inSectionVI-AarevariedforeachUEsuchthattheygenerate for Scheduling Request (SR), resource grants, Hybrid-ARQ, traffic at 80% of the average data rate they received with full ACK/NACKs, and BSR as described in Sec. II. We assume buffer traffic. errorfreetransmissionofcontrolmessagesinoursimulations. (2) Low Load: 5 UEs have live video traffic with a mean rate We focus on delay QoS traffic and consider two different of 200 kbps. The UEs with streaming video traffic are now models [31]. Live Video: This is an ON-OFF Markov process set to operate at 40% of their full buffer average data rate. with fixed packet size is used for the live video traffic model. We first study the performance of the delay estimation The Markov process dwells in either state for 2 seconds mechanism described in Section IV. Figure 4 shows the and when in the ON state, generates a packet every 20 ms. estimated head of line (HoL) delay and the actual HoL delay Streaming Video: Here, both the packet interarrival times and at a UE over a period of 1 second. The estimated values can thepacketsizesareindependentlydrawnfromtruncatedPareto be seen to follow the actualdelaysbutthe accuracyis limited distributions. The numberof arrivalsin a frame length of 100 by the granularityof BSR messages, i.e., if there are multiple millisecond is fixed at 8, while their interarrival times are arriving packets between two successive BSR messages, the drawn from a truncated Pareto distribution with exponent 1.2 packets are bundled as one in our mechanism resulting in and truncation to [2.5 ms - 12.5 ms]. We use an exponent relatively small errors in HoL estimation. 8 250 103 s) Actual Head Non−Iterative Scheduling d n of Line Delay Queue Based Scheduling eco200 Estimated Head HoL Delay Based Scheduling y (millis150 of Line Delay nds) 9D5e l%ayilse 9D5e l%ayilse a o ne Del100 millisec102 MDeeldaiyasn MDeeldaiyasn d of Li 50 Delay ( a e H 0 0 200 400 600 800 1000 Time (milliseconds) 101 Low Load Simulation High Load Simulation Fig.4.HoLdelay estimation performance Fig.5.Livevideousers:delayperformance Next we show the performance of the head of line delay based scheduling scheme computed as the solution to the optimization problem in (4) with the reward function in (3). 104 Non−Iterative Scheduling Figure 5 shows the median and 95th percentile delays of the Queue Based Scheduling live video UEs for the two baseline and the head of line HoL Delay Based Scheduling delay based schedulers for low and high loads. The delays 95 %ile 95 %ile experiencedbythelivevideousersareconsistentlylessinthe nds)103 Delays Delays o case of HoL delay based scheduling with the non-iterative ec scheme resulting in an average 95th percentile delay 1.6x millis MDeeldaiyasn MDeeldaiyasn higher than with the HoL delay scheduling. The queue based elay (102 scheme also results in slightly higher delays, on an average D 1.1xcomparedto95thpercentiledelaysforHoLscheduling.A more pronounced improvement is observed for the streaming video users, as shown in the delay plots in Figure 6. In this 101 case,the non-iterativeandqueuebasedschemesresultin 6.2x Low Load Simulation High Load Simulation and 5x more delays compared to HoL delay scheduling in terms of 95th percentile latencies. Finally, Figure 7 shows the Fig.6.Streaming videousers:delayperformance combined delay numbers for uplink packets from all the UEs inthehighloadsimulation.Ascanbeseenfromthefigure,the iterativequeuebasedanddelaybasedschemesresultinsimilar Live Video UEs Streaming Video UEs 150 4000 delays for live video users due to preferential assignment. 3750 However this results in large delays for the streaming video 3500 users for both non-iterative and queue based schemes: close 125 3250 to 11x and 8x respectively compared to HoL delay based 3000 schedulingintermsof95thpercentiledelays.Thus,leveraging 2750 100 the approximate packet delays obtained via our method leads ds) 2500 n to significant performance improvement over queue based co 2250 e scheduling.Moreover,evenforthequeuebasedscheduler,the millis 75 2000 computational methods in this paper are very useful. y ( 1750 a 2) Micro cell Topology: In order to compare these el 1500 D 50 scheduling schemes in a smaller cell topology, we ran a 1250 second simulation with 20 UEs located within a region with 1000 750 path loss 107-115 dB from the base station. Each UE, in 25 500 this simulation, carries streaming video traffic with the mean 250 data rate randomly selected between 300-2000 Kbits/sec. 0 0 Decoupling the mean traffic rate with the path loss highlights Median 95th %ile Median 95th %ile Non−Iterative Queue Based HoL Delay Based the relative performance of the scheduling algorithms in real deploymentswhere prior knowledge of user demand is rarely known. Individual and cell wide delay numbers are shown in Fig.7.Cell-wide delay performanceofallpackets inmacrocellsimulation Figure 8, which shows that 95th percentile delays for non- iterative and queue based schemes are 1.8x and 1.4x more than those for the HoL delay based scheduling. 9 Delays per UE Cell wide Delays The first constraint implies that the total rate for a user is 450 300 the sum of rates over sub-bands, the second constraint is on totalbandwidthallocationinasub-band,thirdconstraintison 400 250 peakpowerattheUE in a subframe,andthe fourthconstraint 350 modelsfractionalpowercontrol.Thefollowinglemmafollows easily from the construction of the f s: ds)300 200 Lemma 7.1: If (r⋆,b⋆) is a soluitlion to the optimization n ij ij o ec250 problem (7), then f r⋆ is the maximum sum re- ay (millis200 150 waGrdenfoerraalnpyurfpeoasseibPilnetiereriisoo(cid:16)ruPprcojeinaitjlsl(cid:17)omcaettihoond.s to solve the above el D150 100 optimization problem have a complexity of O(NM +NL)3 per iteration – we exploit the structure to reduce it to 100 50 O(N(L2 +M2)). Note that in practice L and M are much 50 smaller than N. In order to constructa solution for which the bandwidthallocation is contiguousin frequencyto satisfy the 0 0 Median 95th %ile Median 95th %ile SC-FDMArequirements,wecanusetheheuristicin[10].The Non−Iterative Queue Based HoL Delay Based maincomputationtosolve(7)istodeterminetheNewtonstep ateachiterationwhichentailssolvingasetoflinearequations Fig.8.IndividualandCell-wideDelayperformanceformicrocellsimulation oftheform(weomitthedetailsduetolackofspace,theexact expressions can be obtained following the steps in [32]): H AT VWIeI. eFxRteEnQdUEthNeCYanSaElyLsEisCTinIVE[1R0]ESfOoUrRfCreEqAueLnLcOyCsAeTleIOctNive  1 ...  x...1 = a rfaewdianrgd ftouncctoinocna)vwehficuhncatiroentshrficie(csouncthinuaosusthlyeddifeflearyenbtiaasbelde  HN  xN  (cid:20) b (cid:21)   y  everywhereexceptatLpointswheretheyareonlycontinuous.  A 0      We can re-write such a function as whereH ∈ R(L+M)×(L+M), A∈ RM×N(L+M), x ∈ L i i f (r )= f min ρ −ρ ,[r −ρ ] RL+M, a ∈ RN(L+M), y,b ∈ RM. We first eliminate the i i il l l−1 i l−1 + x ’s as l=1 i where 0 ≤ ρX< (cid:0)... <(cid:0) ρ are the points(cid:1)o(cid:1)f non- 1 L differentiability and fil : R+ 7→ R are thrice continuously xi =Hi−1 a−AT(L+M)(i−1)+1:(L+M)(i)y differentiable concave functions defined as (cid:16) (cid:17) where AT is the submatrix of AT given by rows k to m. k:m fil(x)=fi(ρl−1+x)−fi(ρl−1), x∈[0,ρl−ρl−1],l≥1,ρ0 =W0e, invert Hi−1 in O(L2+M2) time, solve for y in O(M3) time(M linearequationsinM variables),andback-substitute and satisfy y to obtain x. To invert H , we note that it decomposes as i f′(x)<f′ (y), l>1,x∈[0,ρ −ρ ], y ∈[0,ρ −ρ ]. il i,l−1 l l−1 l−1 l−2 We also assumexψ−1(y/x)is concaveforall(x,y)>0;this K1 is true for example,when ψ is the Shannoncapacity formula,  ...  and for practical M-QAM schemes. K Consider the following convex optimization problem over Hi = M g1 +gigiT rf˜oilr’su,sreirj’iso(rnatseufbo-rbaunsedrji)o:nsub-bandj),andbij’s(bandwidth  ...     g  N L  L  max. fil(r˜il), + hihTi 0 + 0 0  0 0 0 c cT Xi=1Xl=1 (cid:20) (cid:21) (cid:20) i i (cid:21) L M where g ∈ RL+M, h ∈ RL, c ∈ RM. Using the matrix s.t. r˜ ≤ r , ∀i, r˜ ≤ρ −ρ , ∀i,l i i i il ij il l l−1 inversion lemma we can invert H in O(L2+M2) time. i l=1 j=1 X X N b =B, ∀j, (7) VIII. CONCLUSIONS ij i=1 We designed a general computational framework in this X M papertoenableawidearrayofonlineschedulingpoliciesina b (N +I ) ij 0 j ψ−1(rij/bij −1)≤P, ∀i, computationallyefficient manner. We modeled the constraints G j=1 ij due to fractional power control, and formulated an optimiza- X G γ tion problem with non-differentiable objective function. We ij ij r ≤b ψ , r ,b ≥0, ∀i,j. ij ij N +I ij ij showed how to estimate the packet delays on the uplink via (cid:18) 0 j(cid:19) 10 theBSRreports,andproposedanovelschedulingpolicybased [23] Y.Ma,A.Leith,M.-S.Alouini,andX.Shen,“Weighted-SNR-basedfair on packet delays. Numerical results demonstrated that using scheduling foruplinkOFDMA,”Globecom, 2009. [24] G. Fodor, C. Koutsimanis, A. Rcz, N. Reider, A. Simonsson, and packet delay estimates for the uplink can lead to significant W.Mller,“IntercellinterferencecoordinationinOFDMAnetworksand reduction in packet delays as compared with a queue length inthe3GPPLongTermEvolutionsystem,”JournalofCommun.,2009. based scheduler. There are many interesting directions for [25] R. Madan, S. P. Boyd, and S. Lall, “Fast algorithms for resource allocationinwirelesscellularnetworks,”IEEE/ACMTrans.Netw.,2010. futurework.Forexample,wecanfurtherstudytheconnections [26] B. Sadiq, R. Madan, and A. Sampath, “Downlink scheduling for with the work in [11], [12]. In terms of implementation, an multiclasstrafficinlte,”EURASIPJournalonWirelessCommunications interesting question is whether we can design approximation andNetworking Special Issueon3GPP-LTE,2009. [27] N.Shor,K.Kiwiel,andA.Ruszcaynski,Minimizationmethodsfornon- algorithms for the uplink bandwidth packing problem which differentiable functions. Springer-Verlag, 1985. are optimal according to some metric. [28] V.FariasandR.Madan,“Theirrevocable multiarmedbanditproblem,” Operations Research,vol.59,no.2,2011. REFERENCES [29] G. C.-. V. 1.0, “CDMA2000 evaluation methodology,” http://www.3gpp2.org/. [1] E.Dahlman,S.Parkvall,J.Skold,andP.Beming,3GEvolution,Second [30] K.Brueninghaus,D.Astely,T.Salzer,S.Visuri,A.Alexiou,S.Karger, Edition:HSPAandLTEforMobileBroadband. AcademicPress,2008. andG.-A.Seraji,“Linkperformancemodelsforsystemlevelsimulations [2] H.J.KushnerandP.Whiting,“Convergenceofproportional-fairsharing ofbroadbandradioaccess systems,”PIMRC,2005. algorithms under general conditions,” IEEE Trans. Wireless Commun., [31] Next Generation Mobile Networks (NGMN) Alliance, “NGMN Radio 2004. Access Performance Evaluation Methodology,” NGMN White Paper, [3] A. Stolyar, “On the asymptotic optimality of the gradient scheduling January2008. algorithm formulti-user throughputallocation,” Oper.Res.,2005. [32] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge [4] M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, R. Vijayakumar, University Press,2004. andP.Whiting,“Schedulinginaqueueingsystemwithasynchronously varyingservicerates,”Prob.Engg.&Inform.Sci.,vol.18,pp.191–217, 2004. [5] L. Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihopradionetworks,” CDC,1990. [6] S. Shakkottai and A. Stolyar, “Scheduling for multiple flows sharing atime-varying channel: Theexponential rule,”AmericanMathematical Society Translations, Series 2,A volume in memory of F. Karpelevich, vol.207,2002. [7] B.SadiqandG.deVeciana,“Largedeviationssum-queueoptimalityof aradialsum-ratemonotoneopportunistic scheduler,” IEEETrans.Info. Th.,2010. [8] C. Castellanos, D. Villa, C. Rosa, K. Pedersen, F. Calabrese, P.-H. Michaelsen, and J. Michel, “Performance of uplink fractional power control inUTRANLTE,”VTCSpring,2008. [9] J.Huang,V.Subramanian,R.Agrawal,andR.Berry,“Jointscheduling andresourceallocationinuplinkOFDMsystemsforbroadbandwireless access networks,” IEEEJSAC,2009. [10] R.MadanandS.Ray,“Uplinkresourceallocationforfrequencyselective channels andfractional powercontrol,” Toappear inICC,2011. [11] M. Sharma and X. Lin, “OFDM downlink scheduling for delay- optimality:Many-channelmany-sourceasymptoticswithgeneralarrival processes,”ITA,2011. [12] S.Bodas,S.Shakkottai,L.Ying,andR.Srikant,“Schedulingforsmall delay in multi-rate multi-channel wireless networks,” in INFOCOM, 2011. [13] Q.ZhangandS.Song,“Exactexpression forthecoherence bandwidth ofrayleighfadingchannels,”IEEETrans.Commun.,vol.55,no.7,pp. 1296–1299,2007. [14] IEEE, “IEEE 802.11: Wireless LAN Medium Access Control (MAC) andPhysicalLayer(PHY)Specifications.” [15] G. T. 36.814, “Further advancements for E-UTRA Physical layer as- pects,”http://www.3gpp.org/. [16] F. Calabrese, M. Anas, C. Rosa, P. Mogensen, and K. Pedersen, “PerformanceofaradioresourceallocationalgorithmforUTRANLTE uplink,” VTC-Spring,2007. [17] F. Calabrese, C. Rosa, M. Anas, P. Michaelsen, K. I. Pedersen, and P.Mogensen,“AdaptiveTransmissionBandwidthBasedPacketSchedul- ingforLTEUplink,”VTCFall,2008. [18] S.-B. Lee, I. Pefkianakis, A. Meyerson, X. Shugong, and L. Songwu, “ProportionalFairFrequency-DomainPacketSchedulingfor3GPPLTE Uplink,”INFOCOM,2009. [19] D. Jiang, H. Wang, E. Malkamaki, and E. Tuomaala, “Principle and Performance of Semi-Persistent Scheduling for VoIP in LTE System,” WiCom, 2007. [20] E. Yaacoub, H. Al-Asadi, and Z. Dawy, “Low complexity scheduling algorithms fortheLTEuplink,”ISCC,2009. [21] L. Gao and S. Cui, “Efficient subcarrier, power, and rate allocation with fairness consideration forOFDMAuplink,” IEEETrans. Wireless Commun.,2008. [22] K.Kim,Y.Han,andS.-L.Kim,“Jointsubcarrierandpowerallocation inuplinkofdmasystems,”IEEECommun.Lett.,2005.