1,720,988 research outputs found
Delay Differentiation By Balancing Weighted Queue Lengths
Get PDFScheduling policies adopted for statistical multiplexing should provide delay differentiation between different traffic classes, where each class represents an aggregate traffic of individual applications having same target-queueing-delay 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 discrete-time, two-class, single-server queueing model with unit service time per packet and provide mathematical frame-work throughout our work.
For iid Bernoulli packet arrivals, using a step-wise cost-dominance analytical approach using instantaneous queue lengths alone, for a class of one-stage cost functions not necessarily convex, we find the structure of the total-cost optimal policies for a part of the state space. We then consider two particular one-stage cost functions for finding two scheduling policies that are total-cost optimal for the whole state-space. The policy for the absolute weighted difference cost function minimizes the stationary mean, and the policy for the weighted sum-of-square cost function minimizes the stationary second-order moment, of the absolute value of the weighted difference of queue lengths. For the case of weighted sum-of-square cost function, the ‘iid Bernoulli arrivals’ assumption can be relaxed to either ‘iid arrivals with general batch sizes’ or to ‘Markovian zero-one 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 work-conserving policy for our choices of the one-stage cost-function. 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 one-step 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 average-cost for this policy. Simulations with varied class-weights 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 short-term 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 value-iterated, sampled, and then stationarily employed policy, the later lacks any closed-form 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 window-size, as opposed to the policy mentioned in the last paragraph, wherein the error decreases as the square-root of the window-size. We perform numerical value-iteration to show the existence of average-cost and study the performance by simulation. Performance of our policy is comparable with the value-iterated, sampled, and then stationarily employed policy, reported by Mallesh. We have then studied general inter-arrival time processes and obtained the optimal myopic policy for the Pareto inter-arrival 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 round-trip-time values for control information, namely zero and one-slot. The policies that are next-stage optimal (for zero round-trip-time), and two-stage optimal (for one-slot round-trip-time) are obtained. Simulations with varied class-weights 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⌉ stages-to-go for generic values of rtt, and which need not be multiple of time-slots
On the Tradeoff Of Average Delay, Average Service Cost, and Average Utility for Single Server Queues with Monotone Policies
Get PDFIn 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 time and discrete time queueing models that we consider are motivated by cross-layer models for point-to-point links with random packet arrivals and fading at slow and fast time scales. Our studies are motivated by the need to optimally tradeoff the average delay of the packets (a network layer performance measure) with the average service cost of transmitting the packets, e.g. the average power required for transmission (a physical layer performance measure) under a lower bound constraint on the average throughput, in various point-to-point communication scenarios.
The tradeoff problems are studied for a class of monotone and stationary scheduling policies and under the assumption that the service cost rate and utility rate are respectively convex and concave functions of the service rate and arrival rate. We also consider the problem of optimally trading off the average delay and average error rate of randomly arriving message symbols which are transmitted over a noisy point-to-point link, in which case the service cost function is non-convex.
The solutions to the tradeoff problems that we address in the thesis are asymptotic in nature, and are similar in spirit to the Berry-Gallager asymptotic bounds. It is intuitive that to keep a queue stable under a lower bound constraint on the average utility a minimum number of customers have to be served per unit time. This in turn implies that queue stability requires a minimum average service cost expenditure. In the thesis we obtain an asymptotic characterization of the minimum average delay for monotone stationary policies subject to an upper bound constraint on the average service cost and a lower bound constraint on the average utility, in the asymptotic regime where the average service cost constraint is made arbitrarily close to the above minimum average service cost.
In the thesis, we obtain asymptotic lower bounds on the minimum average delay for the cases for which lower bounds were previously not known. The asymptotic characterization of the minimum average delay for monotone stationary policies, for both continuous time and discrete time models, is obtained via geometric bounds on the stationary probability of the queue length, in the above asymptotic regime. The restriction to monotone stationary policies enables us to obtain an intuitive explanation for the behaviour of the asymptotic lower bounds using the above geometric bounds on the stationary probability distribution of the queue length. The geometric bounds on the stationary probability of the queue length also lead to a partial asymptotic characterization of the structure of any optimal monotone stationary policy, in the above asymptotic regime, which was not available in previous work. Furthermore, the geometric bounds on the stationary probability can be extended to analyse the tradeoff problem in other scenarios, such as for other continuous time queueing models, multiple user communication models, queueing models with service time control, and queueing models with general holding costs.
Usually, queueing models with integer valued queue evolution, are approximated by queueing models with real valued queue evolution and strictly convex service cost functions for analytical tractability. Using the asymptotic bounds, we show that for some cases the average delay does not grow to infinity in the asymptotic regime, although the approximate model suggests that the average delay does grow to infinity. In other cases where the average delay does grow to infinity in the asymptotic regime, our results illustrate that the tradeoff behaviour of the approximate model is different from that of the original integer valued queueing model unless the service cost function is modelled as the piecewise linear lower convex envelope of the service cost function for the original model
Scheduling For Stable And Reliable Communication Over Multiaccess Channels And Degraded Broadcast Channels
No full textInformation-theoretic arguments focus on modeling the reliability of information transmission, assuming availability of infinite data at sources, thus ignoring randomness in message generation times at the respective sources. However, in information transport networks, not only is reliable transmission important, but also stability, i.e., finiteness of mean delay in-
curred by messages from the time of generation to the time of successful reception. Usually, delay analysis is done separately using queueing-theoretic arguments, whereas reliable information transmission is studied using information theory. In this thesis, we investigate these
two important aspects of data communication jointly by suitably combining models from
these two fields. In particular, we model scheduled communication of messages , that arrive in a random process, (i) over multiaccess channels, with either independent decoding or joint decoding, and (ii) over degraded broadcast channels. The scheduling policies proposed permit up to a certain maximum number of messages for simultaneous transmission.
In the first part of the thesis, we develop a multi-class discrete-time processor-sharing
queueing model, and then investigate the stability of this queue. In particular, we model the queue by a discrete-time Markov chain defined on a countable state space, and then establish (i) a sufficient condition for c-regularity of the chain, and hence positive recurrence and finiteness of stationary mean of the function c of the state, and (ii) a sufficient condition
for transience of the chain. These stability results form the basis for the conclusions drawn in the thesis.
The second part of the thesis is on multiaccess communication with random message
arrivals. In the context of independent decoding, we assume that messages can be classified into a fixed number of classes, each of which specifies a combination of received signal power, message length, and target probability of decoding error. Each message is encoded independently and decoded independently. In the context of joint decoding, we assume that messages can be classified into a fixed number of classes, each of which specifies a message
length, and for each of which there is a message queue. From each queue, some number of messages are encoded jointly, and received at a signal power corresponding to the queue. The messages are decoded jointly across all queues with a target probability of joint decoding error.
For both independent decoding and joint decoding, we derive respective discrete-
time multiclass processor-sharing queueing models assuming the corresponding information-theoretic models for the underlying communication process. Then, for both the decoding schemes, we (i) derive respective outer bounds to the stability region of message arrival rate vectors achievable by the class of stationary scheduling policies, (ii) show for any mes-
sage arrival rate vector that satisfies the outer bound, that there exists a stationary “state-independent” policy that results in a stable system for the corresponding message arrival process, and (iii) show that the stability region of information arrival rate vectors, in the
limit of large message lengths, equals an appropriate information-theoretic capacity region for independent decoding, and equals the information-theoretic capacity region for joint de-coding. For independent decoding, we identify a class of stationary scheduling policies, for which we show that the stability region in the limit of large maximum number of simultane-ous transmissions is independent of the received signal powers, and each of which achieves a
spectral efficiency of 1 nat/s/Hz in the limit of large message lengths.
In the third and last part of the thesis, we show that the queueing model developed for
multiaccess channels with joint decoding can be used to model communication over degraded
broadcast channels, with superposition encoding and successive decoding across all queues. We then show respective results (i), (ii), and (iii), stated above
Performance Analysis Of A Variation Of The Distributed Queueing Access Protocol
No full text"A distributed queueing Medium Access Control (MAC) protocol is used in Distributed Queue Dual Bus (DQDB) networks. A modified version of the MAC protocol was proposed by R.R. Pillai and U. Mukherji in an attempt to overcome some of the shortcomings of the DQDB MAC protocol. They analyzed the performance of the system for Bernoulli arrivals and for large propagation delays between the nodes. We extend the performance analysis of the modified MAC protocol for a DQDB type of Network. The parameter of interest to us is the bus access delay. This has two components, viz., the request bus access delay and the data bu6 access delay. We use the model at the request point at node and present methods to evaluate the delay experienced in such a model. The model is an n-priority ./D/l queue with D vacations (non-preemptive priority) where n is the number of nodes sending requests on the request bus for transmission on the data bus. The methods presented help to evaluate the request bus access delay when the arrivals at each node are Markovian Arrival Processes (MAPs). The algorithms for evaluating the mean request bus access delay are based on matrix geometric techniques. Thus, one can use the algorithms developed in the literature to solve for the finite buffers case too. This model, for the request bus access delay, holds irrespective of the propagation delay between the nodes.
We also evaluate the inter-departure time of class 1 customers and virtual customers in a 2-priority M/G/l system with G vacations (non-preemptive priority). In the case of Poisson arrivals at all the nodes, we would have a 2-priority M/D/l system with D vacations (non-preemptive priority). We thus evaluate the inter-arrival time of the free slots on the data bus as seen by Node 2. Note that this is independent of the number of active nodes in the network
We then develop methods to evaluate the mean data bus access delay experienced by the customers at Node 2 in a three-node network with 2 nodes communicating with the third when the propagation delay between the nodes is large. We consider the case of finite Local Queue buffers at the two nodes. Using this assumption we arrive at process of arrivals to the Combined Queue and the process of free slots on the data bus to be Markov Modulated Bernoulli processes. The model at the combined queue at Node 2 then has a Quasi Birth-Death evolution. Thus, this system is solved by using the Ramaswami-Latouche algorithm. The stationary probabilities are then used to evaluate the mean data bus access delay experienced at Node 2. The finite buffer case of this system can be solved by G.Wi Stewart's algorithm. The method in modelling the system and the results are presented in detail for Poisson arrivals. The extension of this to more complex processes is also explained. We encounter in the analysis an explosion of the state-space of the system. We try to counter this by considering approximations to the process of free slots on the data bus. The approximations considered are on the basis of what are known as Idealized Aggregates. The performance of the approximation is also detailed. It works very well under low and moderate load but underestimates the mean delay under heavy load.
Thereafter, we discuss the performance of the system with reference to the mean of the access delay and the standard deviation of the access delay under varying traffic at the two nodes. For this part we use simulation results to discuss the performance. The comparison between the performance measures at both the nodes is also done.
Then we develop methods/techniques to understand the performance of the system when we have finite propagation delays between the nodes. We concentrate on the 3-node problem and calculate performance bounds based on linear programs. This is illustrated in detail for Bernoulli arrivals for the case of 1 slot propagation delay between the nodes as well as for the case of 2 slots propagation delay. The performance of the bounds obtained is also detailed. The presence of an idling system at the combined queue of Node 2 makes the bounds somewhat loose. Finally, we discuss the performance of the system with reference to the mean access delay and the standard deviation of the access delay under varying load on the system. Again, we rely on simulation studies.
Finally, we study the performance of the system as a multiplexer. For this, we restrict the traffic to Markov Modulated Processes (or those which would satisfy the Gartner-Ellis Theorem requirements). The traffic is characterized by what are known as Envelope Processes - Lower and Upper. The class of processes which satisfy the conditions of the
Gartner-Ellis theorem come under the category where both the Envelope Processes exist and the Minimum Envelope Rate and the Maximum Lower Envelope Rate are the same. We use the system evolution equations at the combined queue at any node to develop relations between the various input and output processes. First, this is done for a. system of this kind, in isolation. Then, we consider this system as a part of the modified protocol and present relations, among the various input and output processes, which are specific to the modified protocol. The possible use of all of the above to do Admission Control at the entry point to the Asynchronous Transfer Mode (ATM) network is also presented
Delay Minimization of an M/M/1 Point-to-Point Link Model Subject to Throughput and Power Constraints
Get PDFIn this thesis, we address the problem of minimizing the average delay of data pack-ets served by a transmitter on a static, point-to-point link. The transmitter dynamically chooses state-dependent admission and transmission rates, while adhering to average throughput and transmission power constraints. The transmitter is modelled as an infinite buffer Markov queue with adjustable arrival and service rates. Data packets arrive at the system according to a Poisson process with rate, Λ, and are admitted at a rate, λnwith 0≤ λn ≤ Λ, depending on the number, n, of data packets present in the system. The packet size is assumed to be exponentially distributed, and the controller chooses a transmission rate, µn, at most equal to a maximum value, M, depending on the current backlog, n, in the system. The objective is to minimize the average delay of data packets in the system subject to a throughput lower bound constraint, while satisfying an upper bound on the average transmission power. This constrained MDP problem is solved using a Lagrange relaxation approach and analysed for the cases with throughput and power constraints that are achievable with equality by appropri-ate values of the Lagrange multipliers. A procedure is developed, based on explicit formulae, using which optimal admission and service rates as a function of the packet queue length are obtained
Errors In Delay Differentiation In Statistical Multiplexing
No full textDifferent applications of communication networks have different requirements that depend on the type of application. We consider the problem of differentiating between delay-sensitive applications based on their average delay requirements, as may be of interest in signalling networks. We consider packets of different classes that are to be transmitted on the same link with different average delay requirements, to reside in separate queues with the arrival statistics for the queues being specified. This statistical multiplexer has to schedule packets from different queues in so that the average delays of the queues approach the specified target delays as quickly as possible.
For simplicity, we initially consider a discrete-time model with two queues and a single work-conserving server, with independent Bernoulli packet arrivals and unit packet service times. With arrival rates specified, achieving mean queue lengths in a ratio which corresponds to the ratio of target mean delays is a means of achieving individual target mean delays. We formulate the problem in the framework of Markov decision theory. We study two scheduling policies called Queue Length Balancing and Delay Balancing respectively, and show through numerical computation that the expectation of magnitude of relative error in θ (1/m) and θ (1/√m) respectively, and that the expectation of the magnitude of relative error in weighted average delays decays as θ (1/√m) and θ (1/m) respectively, where m is the averaging interval length.
We then consider the model for an arbitrary number of queues each with i.i.d. batch arrivals, and analyse the errors in the average delays of individual queues. We assume that the fifth moment of busy period is finite for this model. We show that the expectation of the absolute value of error in average queue length for at least one of the queues decays at least as slowly as θ (1/√m), and that the mean squared error in queue length for at least one of the queues decays at least as slowly as θ (1/m). We show that the expectation of the absolute value of error in approximating Little’s law for finite horizon is 0 (1/m). Hence, we show that the mean squared error in delay for at least one of the queues decays at least slowly as θ (1/m). We also show that if the variance of error in delay decays for each queue, then the expectation of the absolute value of error in delay for at least one of the queues decays at least as slowly as θ (1/√m)
Low delay file transmissions over power constrained quasi-static fading channels
No full textThe ubiquitous deployment of battery-operated wireless devices has resulted in the need
for efficient low latency power allocation schemes. A common phenomenon in wireless
transmission systems is congestion, where the transmitter backlog grows due to restrictions
in channel usage on a resource-constrained shared access medium. In this research
work, we aim to achieve low communication delay of wireless downlink file transmissions
operating on power-constrained quasi-static fading channels, using state-dependent transmission
rate control and admission of file transmission requests. We employ a Markov
queueing model to formulate the low delay objective for exponentially distributed file sizes
as a constrained average queue length minimization problem.
The corresponding primal problem is known to be expressible as a linear program
in occupation measures, and therefore strong duality holds. In our work, we show the
primal feasibility of the dual optimal policy w.r.t. the average throughput and power constraints,
which is proved under the assumption the optimal average power and throughput
are continuous with respect to the Lagrange dual variables at the optimal point. The dual
problem is simplified to an iterative optimization using Dinkelbach’s fractional programming
method and solved using gradient analysis techniques to analytically derive the
ON-OFF threshold characteristics of the admission policy and the recursive structure of
the transmission rate policy.
We first apply our solution method to a wireless transmission system using the M/M/1
queueing model. Our objective is to minimize the average queue length subject to an upper
bound on average transmission power and a lower bound on average admission rate.
This constrained average queue length minimization problem is solved using Lagrange dual method. We substitute the individual stationary probabilities in the Lagrange dual
function using the product form distribution expressed in terms of the stationary probability
of the maximum queue length. The resulting objective function then corresponds
to a fractional minimization problem which is solved using Dinkelbach’s method. We
analytically derive the ON-OFF threshold characteristic of the optimal admission rates
and the recursive structure of the optimal transmission rates. We illustrate the results of
our algorithm for different values of throughput and power requirements. We also demonstrate
the efficiency of optimal state-dependent rate control for exponentially distributed
file sizes compared to benchmark state-independent transmission schemes.
We next apply the solution techniques to an energy harvesting wireless transmission
system, extending the M/M/1 queueing model. The model uses energy stored in a battery
as well as energy packets available from an auxiliary power supply for file transmission. We
use the product-form stationary distribution to establish a correspondence between the
energy harvesting system and the M/M/1 queueing system. Using the solution approach
using Dinkelbach’s method, we derive similar characteristics for the optimal admission
and transmission rates.
We finally extend the analysis to model a cache-aided wireless transmission system
operating under the assumption the cache-hit probability is uniform for all files and queue
length states. The system is modeled as a quasi-one-dimensional Markov chain. The stationary
probabilities in the Lagrange dual function are expressed in terms of the stationary
probability of the empty buffer state using the product of matrices. The solution methods
and insights developed from the previous models simplify the analysis of this problem,
and we analytically characterize the structure of the optimal admission and transmission
rates. The applicability of our solution methodology to these three models of transmission
systems illustrates its simplicity and versatility
Distributed Algorithms for Power Allocation Games on Gaussian Interference Channels
Get PDFWe consider a wireless communication system in which there are N transmitter-receiver pairs and each transmitter wants to communicate with its corresponding receiver. This is modelled as an interference channel. We propose power allocation algorithms for increasing the sum rate of two and three user interference channels. The channels experience fast fading and there is an average power constraint on each transmitter. In this case receivers use successive decoding under strong interference, instead of treating interference as noise all the time. Next, we u se game theoretic approach for power allocation where each receiver treats interference as noise. Each transmitter-receiver pair aims to maximize its long-term average transmission rate subject to an average power constraint. We formulate a stochastic game for this system in three different scenarios. First, we assume that each user knows all direct and crosslink channel gains.
Next, we assume that each user knows channel gains of only the links that are incident on its receiver. Finally, we assume that each use r knows only its own direct link channel gain. In all cases, we formulate the problem of finding the Nash equilibrium(NE) as a variational in equality problem. For the game with complete channel knowledge, we present an algorithm to solve the VI and we provide weaker sufficient conditions for uniqueness of the NE than the sufficient conditions available in the literature. Later, we present a novel heuristic for solving the VI under general channel conditions. We also provide a distributed algorithm to compute Pare to optimal solutions for the proposed games. We use Bayesian learning that guarantees convergence to an Ɛ-Nash equilibrium for the incomplete information game with direct link channel gain knowledge only, that does not require knowledge of the power policies of other users but requires feedback of the interference power values from a receiver to its corresponding transmitter.
Later, we consider a more practical scenario in which each transmitter transmits data at a certain rate using a power that depends on the channel gain to its receiver. If a receiver can successfully receive the message, it sends an acknowledgement(ACK), else it sends a negative ACK(NACK). Each user aims to maximize its probability of successful transmission. We formulate this problem as a stochastic game and propose a fully distributed learning algorithm to find a correlated equilibrium(CE). In addition, we use a no regret algorithm to find a coarse correlated equilibrium(CCE) for our power allocation game. We also propose a fully distributed learning algorithm to find a Pareto optimal solution. In general Pareto points do not guarantee fairness among the users. Therefore we also propose an algorithm to compute a Nash bargaining solution which is Pareto optimal and provides fairness among the users. Finally, we extend these results when each transmitter sends data at multiple rates rather than at a fixed rate
- …
