IISc Logo    Title

etd AT Indian Institute of Science >
Division of Electrical Sciences >
Electrical Communication Engineering (ece) >

Please use this identifier to cite or link to this item: http://hdl.handle.net/2005/647

Title: Errors In Delay Differentiation In Statistical Multiplexing
Authors: Mallesh, K
Advisors: Mukherji, Utpal
Keywords: Multiplexing
Computer Networks
Queues
Scheduling
Proportional Average Delay Scheduling
Waiting Time Priority Scheduling
Proportional Delay Differentiation (PDD)
Queue Length Balancing
Delay Balancing
Statistical Multiplexing
Submitted Date: May-2007
Series/Report no.: G21675
Abstract: Different 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).
URI: http://hdl.handle.net/2005/647
Appears in Collections:Electrical Communication Engineering (ece)

Files in This Item:

File Description SizeFormat
G21675.pdf457.16 kBAdobe PDFView/Open

Items in etd@IISc are protected by copyright, with all rights reserved, unless otherwise indicated.

 

etd@IISc is a joint service of SERC & IISc Library ||
Feedback
|| Powered by DSpace || Compliant to OAI-PMH V 2.0 and ETD-MS V 1.01