Abstract
Original language  Undefined 

Supervisors/Advisors 

Award date  19 Oct 2000 
Place of Publication  Enschede 
Publisher  
Print ISBNs  903651505X 
Publication status  Published  19 Oct 2000 
Keywords
 METIS118434
 IR17915
 EWI7724
Cite this
}
Analysis and efficient simulation of queueing models of telecommunication systems. / de Boer, PieterTjerk.
Enschede : Universiteit Twente, 2000. 206 p.Research output: Thesis › PhD Thesis  Research UT, graduation UT › Academic
TY  THES
T1  Analysis and efficient simulation of queueing models of telecommunication systems
AU  de Boer, PieterTjerk
N1  Imported from research group DACS (ID number 285)
PY  2000/10/19
Y1  2000/10/19
N2  In modern packetswitched telecommunication systems, information (such as email, sound, pictures) is transported in the form of small packets (or cells) of data through a network of links and routers. The Quality of Service provided by such a network can suffer from phenomena such as loss of packets (due to buffer overflow) and excessive delays. These aspects of the system are adequately described by queueing models, so the study of such models is of great relevance for designing systems such that they provide the required QoS. This thesis contributes methods for the efficient estimation of several loss probabilities in various queueing models of communications systems. The focus is on rareevent simulation using importance sampling, but some analytical, asymptotic and numerical results are also provided. One part of this thesis is concerned with issues related to the estimation of the probability of consecutive (cell) loss: the loss of several consecutive arrivals to a queue. Analytical calculation of this is demonstrated for several simple queues (M/G/1/k and G/M/m/k), and an importance sampling simulation procedure is provided for M/G/1/k queues. Furthermore, an M/M/1/k queue with multiple sources is considered, in which the probability of consecutive (cell) loss incurred by one of these sources is calculated analytically. The other part of this thesis is concerned with the estimation of overflow probabilities in queueing networks. For estimating these probabilities, importance sampling simulation methods are considered, in which several adaptive techniques (mostly based on crossentropy) are applied to approximate the optimal change of measure. Two classes of change of measure are used: those which do not depend explicitly on the state of the model (e.g., a ``static'' change of the arrival and service rates), and those which do (e.g., changing the arrival and service rates separately for each state). The methods using a stateindependent change of measure turn out to be quite effective and to result in an asymptotically efficient simulation in most cases; however, some counterexamples are also observed. With a statedependent change of measure, an asymptotically efficient simulation is obtained in every example tried, including those for which no good stateindependent change of measure is known. The statedependent method has only been applied to Markovian networks, but possible ways to extend it to nonMarkovian networks are briefly discussed. Furthermore, a simple numerical method is proposed for the calculation of overflow probabilities in simple Jackson networks, which is used to verify the correctness of the results from the above simulation methods. In the course of the work on the above two main problems, some interesting subproblems and related issues were investigated. The obtained results are also useful in other contexts, and include the following: (1) asymptotic expressions for the past and remaining service time distributions upon reaching a high (overflow) level in MG1 queues; (2) asymptotically efficient importance sampling simulation schemes for the estimation of probabilities of events of the form ni 1 Xi ] Y, where Xi are positive i.i.d. random variables, and Y is also a positive random variable (useful in e.g. reliability models); (3) an extension of the central limit theorem to exponentially tilted random variables (useful for asymptotic efficiency proofs).
AB  In modern packetswitched telecommunication systems, information (such as email, sound, pictures) is transported in the form of small packets (or cells) of data through a network of links and routers. The Quality of Service provided by such a network can suffer from phenomena such as loss of packets (due to buffer overflow) and excessive delays. These aspects of the system are adequately described by queueing models, so the study of such models is of great relevance for designing systems such that they provide the required QoS. This thesis contributes methods for the efficient estimation of several loss probabilities in various queueing models of communications systems. The focus is on rareevent simulation using importance sampling, but some analytical, asymptotic and numerical results are also provided. One part of this thesis is concerned with issues related to the estimation of the probability of consecutive (cell) loss: the loss of several consecutive arrivals to a queue. Analytical calculation of this is demonstrated for several simple queues (M/G/1/k and G/M/m/k), and an importance sampling simulation procedure is provided for M/G/1/k queues. Furthermore, an M/M/1/k queue with multiple sources is considered, in which the probability of consecutive (cell) loss incurred by one of these sources is calculated analytically. The other part of this thesis is concerned with the estimation of overflow probabilities in queueing networks. For estimating these probabilities, importance sampling simulation methods are considered, in which several adaptive techniques (mostly based on crossentropy) are applied to approximate the optimal change of measure. Two classes of change of measure are used: those which do not depend explicitly on the state of the model (e.g., a ``static'' change of the arrival and service rates), and those which do (e.g., changing the arrival and service rates separately for each state). The methods using a stateindependent change of measure turn out to be quite effective and to result in an asymptotically efficient simulation in most cases; however, some counterexamples are also observed. With a statedependent change of measure, an asymptotically efficient simulation is obtained in every example tried, including those for which no good stateindependent change of measure is known. The statedependent method has only been applied to Markovian networks, but possible ways to extend it to nonMarkovian networks are briefly discussed. Furthermore, a simple numerical method is proposed for the calculation of overflow probabilities in simple Jackson networks, which is used to verify the correctness of the results from the above simulation methods. In the course of the work on the above two main problems, some interesting subproblems and related issues were investigated. The obtained results are also useful in other contexts, and include the following: (1) asymptotic expressions for the past and remaining service time distributions upon reaching a high (overflow) level in MG1 queues; (2) asymptotically efficient importance sampling simulation schemes for the estimation of probabilities of events of the form ni 1 Xi ] Y, where Xi are positive i.i.d. random variables, and Y is also a positive random variable (useful in e.g. reliability models); (3) an extension of the central limit theorem to exponentially tilted random variables (useful for asymptotic efficiency proofs).
KW  METIS118434
KW  IR17915
KW  EWI7724
M3  PhD Thesis  Research UT, graduation UT
SN  903651505X
PB  Universiteit Twente
CY  Enschede
ER 