The main objective of this thesis is the estimation of the bandwidth that should be allocated on each link along the path of a flow of IP packets, so that the end-to-end delay D is bounded statistically. That is, D is less than or equal to a given value T with a probability γ. The path through an IP network is depicted by a tandem queueing network of infinite capacity queues, where each queue represents the output port of a router.;We first obtain some results on adding percentiles, and then we propose two different algorithms for calculating end-to-end percentiles, which is then used in a simple search algorithm to obtain the required bandwidth. The first algorithm is based on probabilistic assumptions regarding the arrival process of the packet flow and service times at each node in the tandem queueing network. The second algorithm is based on traces, such as video traces, that consist of a sequence of tuplets, each describing the time of arrival of a packet and its packet length.;In the first algorithm, we assume that the arrival process to the first queue of the queueing network is bursty and correlated and the service times are exponentially distributed. Initially, we assumed an MMPP (Markov-modulated Poisson process) arrival process, and then we extended the algorithm to a MAP2 (two-stage Markov arrival process) arrival process. A MAP can represent a variety of processes that includes, as special cases, the Poisson process, the phase-type renewal processes, the MMPP and superposition of these. No background arrivals were considered at each node, the implication being that the output port scheduler is assumed to be per flow. The proposed algorithm is based on an interpolation between an upper and lower bound obtained by analyzing only the first queue. It is a relatively simple algorithm despite the complexity of the problem, and as shown through extensive comparisons with simulation data that it has a very low relative error. The average error is 1.25% for MMPP and 4.5% for MAP2.;Video traffic is widely expected to account for a large portion of the traffic in future wired and wireless networks. For interactive video the end-to-end delay has to be less than 150 to 200 msec in order to guarantee good QoE. Interestingly enough, little is known about how much bandwidth should be allocated to an interactive video so that a given percentile of the end-to-end delay is satisfied. Using the above algorithm, we obtained the end-to-end percentile for video traffic, by approximating a video trace with a MAP2. Subsequently, the required bandwidth so that a given end-to-end percentile is satisfied is obtained using a simple search algorithm. Three different types of video traces were used, namely, Cisco’s Telepresence, IPTV and WebEx. The approximation of video trace by a MAP2 coupled with the above algorithm gives results with a low relative error, the average relative error is around 6%.;The algorithm described above for calculating a percentile of the end-to-end delay of a video stream, cannot handle the presence of background traffic that competes with the video within the output port of a router. In view of this, we propose an exact and efficient algorithm for calculating any percentile of the end-to-end delay in the presence of background video traffic, assuming that all video flows are characterized by packet traces and an arriving packet keeps its packet length in the entire queueing network. These traces may be a single stream or multiple streams. Packets in each node are served in a FIFO, the implication being that the output port scheduler is assumed to be per class, which more general than the assumption made in the first algorithm. A class could be a DiffServ class where all video packets are queued. Based on this algorithm, the minimum amount of bandwidth required, so that a given percentile of the end-to-end delay is satisfied, is easily obtained using a simple search algorithm.
展开▼
