Delay Differentiation By Balancing Weighted Queue Lengths
Abstract
Scheduling policies adopted for statistical multiplexing should provide delay differentiation between different traffic classes, where each class represents an aggregate traﬃc of individual applications having same targetqueueingdelay requirements. We propose scheduling to optimally balance weighted mean instanteneous queue lengths and later weighted mean cumulative queue lengths as an approach to delay differentiation, where the class weights are set inversely proportional to the respective products of target delays and packet arrival rates. In particular, we assume a discretetime, twoclass, singleserver queueing model with unit service time per packet and provide mathematical framework throughout our work.
For iid Bernoulli packet arrivals, using a stepwise costdominance analytical approach using instantaneous queue lengths alone, for a class of onestage cost functions not necessarily convex, we find the structure of the totalcost optimal policies for a part of the state space. We then consider two particular onestage cost functions for finding two scheduling policies that are totalcost optimal for the whole statespace. The policy for the absolute weighted difference cost function minimizes the stationary mean, and the policy for the weighted sumofsquare cost function minimizes the stationary secondorder moment, of the absolute value of the weighted difference of queue lengths. For the case of weighted sumofsquare cost function, the ‘iid Bernoulli arrivals’ assumption can be relaxed to either ‘iid arrivals with general batch sizes’ or to ‘Markovian zeroone arrivals’ for all of the state space, but for the linear switching curve. We then show that the average cost, starting from any initial state, exists, and is finite for every stationary workconserving policy for our choices of the onestage costfunction. This is shown for arbitrary number of class queues and for any i.i.d. batch arrival processes with finite appropriate moments.
We then use cumulative queue lengths information in the onestep cost function of the optimization formulation and obtain an optimal myopic policy with 3 stages to go for iid arrivals with general batch sizes. We show analytically that this policy achieves the given target delay ratio in the long run under finite buffer assumption, given that feasibility conditions are satisfied. We take recourse to numerical value iteration to show the existence of averagecost for this policy. Simulations with varied classweights for Bernoulli arrivals and batch arrivals with Poisson batch sizes show that this policy achieves mean queueing delays closer to the respective target delays than the policy obtained earlier. We also note that the coefficients of variation of the queueing delays of both the classes using cumulative queue lengths are of the same order as those using instantaneous queue lengths. Moreover, the shortterm behaviour of the optimal myopic policy using cumulative queue lengths is superior to the existing standard policy reported by Coffman and Mitrani by a factor in the range of 3 to 8. Though our policy performs marginally poorer compared to the valueiterated, sampled, and then stationarily employed policy, the later lacks any closedform structure.
We then modify the definition of the third state variable and look to directly balance weighted mean delays. We come up with another optimal myopic policy with 3 stages to go, following which the error in the ratio of mean delays decreases as the windowsize, as opposed to the policy mentioned in the last paragraph, wherein the error decreases as the squareroot of the windowsize. We perform numerical valueiteration to show the existence of averagecost and study the performance by simulation. Performance of our policy is comparable with the valueiterated, sampled, and then stationarily employed policy, reported by Mallesh. We have then studied general interarrival time processes and obtained the optimal myopic policy for the Pareto interarrival process, in particular. We have supported with simulation that our policy fares similarly to the PAD policy, reported by Dovrolis et. al., which is primarily heuristic in nature.
We then model the possible packet errors in the multiplexed channel by either a Bernoulli process, or a Markov modulated Bernoulli process with two possible channel states. We also consider two possible roundtriptime values for control information, namely zero and oneslot. The policies that are nextstage optimal (for zero roundtriptime), and twostage optimal (for oneslot roundtriptime) are obtained. Simulations with varied classweights for Bernoulli arrivals and batch arrivals with Poisson batch sizes show that these policies indeed achieve mean queueing delays very close to the respective target delays. We also obtain the structure for optimal policies with N = 2 + ⌈rtt⌉ stagestogo for generic values of rtt, and which need not be multiple of timeslots.
Collections
Related items
Showing items related by title, author, creator and subject.

On the Tradeoff Of Average Delay, Average Service Cost, and Average Utility for Single Server Queues with Monotone Policies
Sukumaran, Vineeth Bala (20180423)In this thesis, we study the tradeoff of average delay with average service cost and average utility for both continuous time and discrete time single server queueing models without and with admission control. The continuous ... 
Errors In Delay Differentiation In Statistical Multiplexing
Mallesh, K (20100303)Different applications of communication networks have different requirements that depend on the type of application. We consider the problem of differentiating between delaysensitive applications based on their average ... 
Modelling and Performance Analysis of New Coolstreaming for P2P IPTV
Raghvendra, Potnis Varada (20180223)Peer to peer networks are becoming increasingly popular among Internet users as the downloading peers share the storage and upload bandwidth load of the system. This makes it possible for a large number of users to share ...