Queueing theory is one of the most important branches of modern probability theory which has many applications in computer science and communication networks.
The main purposes of this dissertation are to analyze threshold-based queueing systems and to apply these models to traffic controls in ATM networks such as the cell discarding(CD) scheme, the dynamic rate leaky bucket scheme and the queue-length- threshold(QLT) scheduling policy.
In Chapter 2, we analyze a queueing system MMPP/$G_1$, $G_2$/1/B with queue length dependent service times where arrivals follow a Markov-modulated Poisson process(MMPP). The service time of customers depends upon the queue length at service initiation epoch: if the queue length at service initiation epoch is less than or equal to a threshold L, the service time distribution of customer is $G_1$ ; otherwise, the service time distribution of customer is $G_2$. By using the embedded Markov chain method, we obtain the queue length distribution at departure epochs. Then, by using the supplementary variable method and the basic property of semi-Markov process, we obtain the queue length distribution at an arbitrary time. By this result, we obtain the loss probability and the mean waiting time. Our model has application to the cell discarding(CD) scheme operating at the output of a buffer for voice traffics in ATM networks. From numerical examples, we see that the loss probability and the mean waiting time for the CD scheme are improved considerably compared with those of the uncontrolled system without CD scheme.
In Chapter 3, we propose the leaky bucket scheme with threshold-based token generation intervals. The leaky bucket scheme is a promising method that regulates input traffics for preventive congestion control in ATM networks. In order to meet the constraint of loss probability for more bursty input traffics, it is known that the leaky bucket scheme with static token generation interval requires a larger data buffer and token pool size. This causes an increase in the mean waiting time for input traffic to pass the leaky bucket scheme, which would be inappropriate for the real-time traffics such as voice and video. So we propose the leaky bucket scheme with threshold-based token generation intervals in which the token generation interval changes according to buffer occupancy. The proposed leaky bucket scheme is analyzed in the discrete-time case by assuming the arrival process to be a Markov-modulated Bernoulli process(MMBP). By using the supplementary variable method and the state splitting method, we obtain the cell loss probability, the mean waiting time and the interdeparture time distribution. Numerical examples show that the Quality of Service(QoS) of input traffics in the proposed leaky bucket scheme is satisfied with a smaller data buffer and token pool size compared with ordinary leaky bucket scheme with static token generation interval.
In Chapter 4, we analyze an MMPP,M/G/1 finite queue with queue-length-threshold(QLT) scheduling policy where the arrivals of type-1 customers follow a Poisson process and the arrivals of type-2 customers follow a Markov-modulated Poisson process(MMPP). There are two separate buffers to accommodate each type customer. We place a threshold L on the buffer of type-1 customers. The next customer to be served is determined by the queue length in the buffer of type-1 customers: if the queue length of type-1 customers is less than or equal to the threshold L at service initiation, the service is given to type-2 customers; otherwise, the service is given to type-1 customers with probability p and type-2 customers with probability q=(1-p). We obtain the joint queue length distribution for each type customer at departure epochs by using the embedded Markov chain method, and then obtain the queue length distribution at an arbitrary time by using the supplementary variable method. By this result, we obtain the loss probability and the mean waiting time for customers of each type. We may consider the type-1 customer as the nonreal-time traffic and the type-2 customer as the bursty real-time traffic in ATM networks. Numerical examples show that the QLT scheduling policy improves the performance of the nonreal-time traffic while still meeting the Quality of Service(QoS) requirement for the real-time traffic.
