Diffusion approximation models for broadband integrated networks and their performance evaluation

Abstract

In this thesis, we first consider the VBR video traffic modelling, then the reactive congestion control of VBR and BET traffic, and finally the optimal scheduling scheme for CBR traffic over the broadband integrated services digital network with Quality of Service (QoS) constraints. Broadband networks are expected to serve a large variety of traffic sources with widely varying traffic characteristics and performance requirements. Broadly, the traffic sources can be classified into two categories: a) Real-time sources with specified performance criteria, like small end-to-end delay and loss probability, and b) Sources that do not have stringent performance criteria and do not demand performance guarantees from the network, i.e., the so-called Best Effort Type (BET) sources. Different models have been proposed in the literature to characterize the traffic. The traffic characterization is very important to engineer a good network as this characterization plays an important role in determining the performance of the BISDN. The performance model should incorporate the following: a) Modelling users with multiple classes. b) Characterizing network resources needed for processing those demands. c) Estimating the system performance based on the output in different channels along the network. Different types of services treated by the ATM are Constant Bit Rate (CBR) such as voice, Variable Bit Rate (VBR) such as compressed video and audio, Available Bit Rate (ABR) such as emails and normal data, and Unspecified Bit Rate (UBR) similar to ABR without any performance requirements. In our thesis, we consider VBR modelling using a diffusion process. Here, the video is coded by an encoder before being sent into the network. Each coded frame has a random number of bits and is delivered deterministically once in every 1/30 of a second. Also, these VBR classes exhibit burstiness. Here the arrival points {T?} appear to form visual clusters, i.e., A?, the arrival of the nth batch of cells has a large number of packets for a short interval of time. This happens when there are scene changes in the video. We consider a simple VBR video modelling as given by [56]. Here Maglaris et al. consider a video sequence as a combination of “on-off” sources. Such a system is defined as an M-state Continuous Time Markov Chain (CTMC). The transition parameters of the Markov chain are obtained after considering the parameters such as mean, variance, and auto-covariance of the original video signal v(t). We consider the same Markov chain as described in [56], but make the state space continuous instead of being discrete, i.e., we convert the Markov chain of [56] into a diffusion process with barriers. We then calculate the conditional probability density and distribution function of the above diffusion process. In both cases, we get closed-form expressions for both the probability density function and probability distribution function. We also calculate the cell loss probability of the process for the zero-buffer case. Then we consider the superposition of N such sources. We use the principles of large deviations theory to calculate the loss probability in the N-source case. But the model described in [56] does not include scene changes. Also, incorporating such a scene change in the basic diffusion process, which has been used to model a simple video sequence such as video telephony, and getting a closed-form expression is a difficult task. The scene change distributions are given in [33]. After extensive studies on a large number of test sequences, [33] say that the scene changes in a video can be broadly classified as Gamma, Weibull, or Pareto distributions. These are first-order distributions. In order to incorporate them in the diffusion equation, we consider the Pearson equation and use the method suggested by [88] to convert the first-order distributions into diffusion equations. We solve these equations to get closed-form expressions for the probability density functions. In the case of Video-on-Demand (VOD) and real-time video, the successive frames are highly correlated. Considering the “on-off” sources as done in [56], we consider the rate of transitions from one state to another state being dependent on the present state itself. This means that during the next transition epoch, the number of sources that are going to be in the “on” state is dependent on the number of sources that are “on” in the present state. We calculate the infinitesimal mean and variance of the above process. Simulation is carried out for the Wright-Fisher model of sources. Then we use the Fokker-Planck equations obtained to study the buffer behaviour of the system and calculate the loss probability. We compare with the leaky bucket scheme and show the improvement of our scheme. For the system modelled by diffusion sources, we then use a reactive congestion control mechanism to control the source rate based on the queue length at the output of the ATM switch. Consider a J × J ATM switch. The input side of the switch is called the source side and the output side is called the server side. Similar models were considered by [35] and [66]. All the above approaches consider fluid models for the sources. Since we have modelled the sources following a diffusion characteristic, we use Brownian control models for our flow control model. We employ a simple Bang-Bang control scheme with two thresholds instead of a single threshold as done in most of the literature. The model is shown in Fig. 4.1. Here the buffer size at the output port is of finite length B. The server at the output port has a constant service rate d. We consider two thresholds b? and b?, with b? closer to 0 and b? closer to B. The Buffer Access Controller (BAC) determines the rate at which the fluid is admitted into the system. The intuition in choosing two thresholds is as follows: When the fluid level drops below b?, we have a loss in throughput of the system. When the fluid level is greater than b?, we are entering the congestion phase and we might lose some fluid. So the aim is to have the fluid level between b? and b?. We formulate the problem in the following way. Let b? and b? represent two threshold levels such that 0 < b? < b? < B, where B is the buffer size. The output is represented by a constant draining rate d. Here b? and b? are the control variables. It is assumed that at any time the process BAC is free to change the rate at which the traffic is admitted into the buffer from A?(t) to A?(t) or vice versa. Such changes are made as follows: At time t = 0, the queue length process is assumed to be x, (b? < x < b?) and the rate at which the BAC allows the incoming traffic is A?(t). The first time the process hits b?, the rate at which the traffic is admitted into the buffer is changed into A?(t). The admission rate of the BAC is changed into A?(t) when the level b? is hit again, and so on. Under such a situation, the limiting distribution of the queue length process lies between the strip [b?, b?] is calculated. The optimum values of b? and b? are found using standard multivariable optimization techniques. The impulsive control of such a process is considered. Here, the delaying and stability effects of the controller are not analyzed. We consider two stopping times T? and T? as follows. Starting with the fluid level at b?, the source rate being A?(t) (> d), we calculate the first time the fluid level touches the upper threshold b?. Let this time be T?. Crossing the level b?, we enter the congestion region and immediately the BAC communicates to all the sources and asks them to immediately reduce the rate. So the net arrival rate that is allowed into the system is denoted by A?(t) (< d). Now the fluid level begins to drop. The first time it touches the lower threshold b?, starting from b?, is denoted by T?. If the level is allowed to go below b?, we enter into a region where the throughput is wasted. So the BAC restores the arrival rate to A?(t). The above analysis is valid only under the heavy traffic condition. So the cycle repeats itself. We use the martingale calculus as suggested by [30] and derive the expressions of T? and T? in terms of B, b?, and b?. Then we use the standard multivariable optimization technique to calculate the values of optimal b? and b? for a buffer of size B. Then we consider the instantaneous control for the above system. Here the instantaneous control is achieved by enforcing an upward jump to b? whenever the fluid content in the buffer hits 0 and a downward jump to b? is enforced whenever the fluid content touches B. The intuition behind the above control is to ensure that no throughput is wasted and the loss is minimized. We finally consider the scheduling of CBR traffic for service in a multiplexer, where the CBR traffic is mixed with traffic of another session (interfering traffic) that has throughput and burstiness constraints. The CBR traffic has a maximal delay T before which it has to be scheduled for service. Interfering traffic is described by the (?, ?)-constraint. This is the constraint of the traffic shaped by the leaky bucket regulation. [64] and [49] consider the worst-case performance of the traffic streams with (?, ?)-constraints. They also consider longest packet delay. [50] also uses the same model with the constant source rate and determines the fraction of the CBR traffic that fails to meet the deadline T. We solve the same problem using a dynamic programming approach and consider three varying cases of the source rate, viz., a) constant rate, b) Markov modulated, and c) diffusion rate. For all the three cases, we prove that there exists an optimal switching time t? (< T). We plot the switching times for all the three cases of the source rate and numerically compute the value of the switching time t? for source rate being constant and the interfering traffic being described by the (?, ?)-constraint.