Computer networks must accommodate a wide variety of applications, ranging from simple file transfer programs to complex multimedia applications. Many of these applications require certain Quality of Service (QoS) guarantees for their proper operation. QoS guarantees include bounds on the packet delay, delay variation and loss rate. These guarantees can be provided through the allocation of network resources such as, processor time, buffer space and link bandwidth. Properly allocating network resources remains a challenging problem due to the number of users, diversity of network applications and the finite supply of resources. Furthermore, these resources are expected to have costs associated with their usage (amount and renegotiation). Given this environment, two important resource allocation issues are addressed in this thesis. First, methods are needed to reduce the amount of resources and renegotiations required to provide a desired QoS (thereby reducing the cost and increasing the utilization). Second, network administrators are interested in allocating and managing resources to all users in an efficient and fair manner.

Determining an efficient amount of network resources that will result in a desired QoS is difficult for certain sources, due to their unpredictable behavior and limited a priori source information. Such applications include the transmission of, MPEG-compressed video, live video and interactive multimedia. In this thesis, an allocation method called Dynamic Search Algorithm (DSA+) is introduced. DSA+ is an on-line algorithm that dynamically adjusts the resource allocation based upon the measured QoS. Advantages of DSA+ include efficient use of resources, few renegotiations, reasonable implementation cost, and stringent QoS control. The ability of DSA+ to allocate bandwidth to meet a desired cell loss probability is investigated and analyzed via simulation using generated (MMBP) and actual MPEG-compressed videos. Advantages of DSA+ over other allocation methods, the robustness to initial parameter selection and the ability to allocate for multiple hop connections are presented.

Network managers seek to allocate resources, to all users, in an efficient and fair manner. In this thesis, microeconomic-based allocation techniques are introduced that model the network as an economy, consisting of separate and independent competitive markets. In these markets, switches price their link bandwidth based on supply and demand, and users purchase bandwidth to maximize their individual QoS. Two different types of markets are used to allocate resources: the spot market and the reservation market. The reservation market provides users the advantage of bandwidth ownership over a period of time, while the bandwidth sold in the spot market has the advantage of immediate availability (no reservation overhead). These decentralized state-less allocation methods can provide efficient and fair allocations of bandwidth as well as guarantees of resource availability. Proofs of important microeconomic and standard computer network measures of fairness are presented, as well as price stability. The performance of these resource allocation methods are also investigated and analyzed using simulations with various network configurations and actual MPEG-compressed videos. Results indicate that these microeconomic-based resource allocation methods achieve high utilization, optimal allocations and provide better QoS than other allocation techniques.

Multimedia applications are expected to play a more prevalent role in integrated service networks. One method of efficiently transmitting such traffic uses the ABR service class. However, rate control for this class becomes more difficult due to the bursty and somewhat unpredictable behavior of multimedia traffic. This paper presents a microeconomic-based ABR rate control technique that models the network as competitive markets. Prices are affixed to ABR bandwidth based upon supply and demand, and users purchase bandwidth to maximize their individual QoS. This yields a \textit{state-less} rate control method that provides Pareto-optimal and QoS-fair bandwidth distributions, as well as high utilization. Simulation results using actual MPEG-compressed video traffic show utilization over 95\% and better QoS control than max-min or demand-based weighted max-min.

This paper presents a new variant of Slow-start, called Smooth-start, which improves the performance of TCP congestion control at the start of a TCP connection, or after a retransmission timeout. It is known that Slow-start causes multiple packet loss, and reduces effective throughput when the available bandwidth of a connection is overestimated. Smooth-start solves this problem by approaching flow equilibrium in a more conservative way. Simulation results show that Smooth-start can significantly reduce packet loss, and improve effective throughput during an overestimation period which usually hapens at the beginning of a TCP connection. Furthermore, the implementation of Smooth-start is very simple. All TCP modifications are at the sending side only.

Multimedia applications are expected to play a more prevalent role in integrated service networks. One method of efficiently transmitting such traffic uses the ABR service class. However, rate control for this class becomes more difficult due to the bursty and somewhat unpredictable behavior of multimedia traffic. This paper presents a microeconomic-based ABR rate control technique that models the network as competitive markets. Prices are affixed to ABR bandwidth based upon supply and demand, and users purchase bandwidth to maximize their individual QoS. This yields a \textit{state-less} rate control method that provides a Pareto optimal and QoS-fair bandwidth distribution, high utilization (up to 95\% in simulation results), and better performance than max-min or demand-based weighted max-min. Proofs that this method achieves weighted max-min fairness, Pareto optimality, QoS-fairness and price stability are provided, as well as simulation using MPEG-compressed video traces.

Network applications require a certain level of network performance for their proper operation. These individual guarantees can be provided if sufficient amounts of network resources are available; however, contention for the limited network resources may occur. For this reason, networks use flow control to manage network resources fairly and efficiently. This paper presents a distributed microeconomic flow control technique, that models the network as competitive markets. In these markets switches price their link bandwidth based on supply and demand, and users purchase bandwidth so as to maximize their individual Quality of Service (QoS). This decentralized flow control method provides a Pareto optimal bandwidth distribution, individual QoS, and high utilization. Simulation results using actual MPEG-compressed video traffic show utilization over 95\% and better QoS control than max-min.

Network applications require certain performance guarantees that can be provided if enough network resources are available. Consequently, contention for the limited network resources may occur. For this reason, networks use flow control to manage network resources fairly and efficiently. This paper presents a distributed microeconomic flow control technique. This method models the network as competitive markets, where pricing of bandwidth based upon supply and demand. This yields a decentralized flow control method that provides a Pareto optimal bandwidth distribution, high utilization (up to 95% in simulation results) and better QoS than max-min. Proof of stability and a Pareto optimal distribution are provided as well as results from various simulations.

Network applications require certain individual performance guarantees that can be provided if enough network resources are available. Consequently, contention for the limited network resources may occur. For this reason, networks use flow control to manage network resources fairly and efficiently. This paper presents a distributed microeconomic flow control technique, that models the network as competitive markets. In these markets switches price their link bandwidth based on supply and demand, and users purchase bandwidth so as to maximize their individual Quality of Service (QoS). This yields a decentralized flow control method that provides a Pareto optimal bandwidth distribution and high utilization (over 90% in simulation results). Discussions about stability and Pareto optimal distribution are given as well as simulation results using actual MPEG-compressed video traffic.

In this paper, we study the NP-hard delay-constrained
least-cost path problem. A solution to this problem is
needed to provide real-time communication service
to connection-oriented applications, such as video and voice.
We propose a simple, distributed heuristic
solution, called the delay-constrained unicast routing (DCUR) algorithm. DCUR
requires limited network state information to be kept at each node: a cost
vector and a delay vector.
We prove DCUR's correctness by showing that it is always capable of
constructing a loop-free delay-constrained path within finite time, if such
a path exists. The worst case message complexity of DCUR is O(|V|^{2})
messages, where |V| is the number of nodes. However, simulation results
show that, on the average, DCUR requires much fewer messages. Therefore, DCUR
scales well to
large networks. We also use simulation to compare DCUR to the optimal
algorithm, and to the least-delay path algorithm. Our results show that DCUR's
path costs are within 10% from those of the optimal solution.

Network multimedia applications require certain performance guarantees that can be provided through proper resource allocation. Allocation techniques are needed to provide these guarantees as efficiently as possible since resources are limited. This paper presents an allocation method called Dynamic Search Algorithm (DSA+). DSA+ is an on-line algorithm that dynamically adjusts the resource allocation based upon the measured quality of service. Advantages of DSA+ include efficient use of resources, reasonable implementation cost and stringent quality of service control. In this paper we demonstrate how DSA+ dynamically allocates bandwidth to achieve a given loss rate for actual variable bit rate MPEG videos. Performance and cost advantages over other allocation methods are presented, as well as allocation for multiple hop connections.

Performance guarantees for multimedia services can be achieved through proper resource allocation. Resources should be reserved in a manner which provides these guarantees as efficiently as possible. This paper presents an allocation method called the Dynamic Search Algorithm (DSA+). DSA+ is an on-line algorithm that dynamically adjusts the resource allocation, based upon the measured quality of service (QoS). Advantages of DSA+ include efficient use of resources, reasonable implementation cost, and stringent QoS control. In this paper, we show how DSA+ dynamically allocates bandwidth to achieve a given loss rate for MMBP generated traffic and actual MPEG VBR videos. Performance and cost of other allocation methods are compared, as well as the lack of dependence of DSA+ on initial parameter settings. DSA+ allocation for multiplexed traffic and multiple hop connections is also examined.

We formulate the problem of constructing broadcast trees for real-time traffic with delay constraints in networks with asymmetric link loads as a delay-constrained minimum spanning tree (DCMST) problem in directed networks. Then we prove that this problem is NP-complete, and we propose an efficient heuristic to solve the problem based on Prim's algorithm for the unconstrained minimum spanning tree problem. Simulation results under realistic networking conditions show that our heuristic's performance is close to optimal when the link loads are symmetric as well as when asymmetric link loads are used. Delay-constrained minimum Steiner tree heuristics can also be used to solve the DCMST problem. Simulation results indicate that the fastest delay-constrained minimum Steiner tree heuristic, DMCT, is not as efficient as the heuristic we propose, while the most efficient delay-constrained minimum Steiner tree heuristic, BSMA, is much slower than our proposed heuristic and does not construct cheaper delay-constrained broadcast trees.

Real-time and other performance guarantees for multimedia can be achieved through proper resource allocation. This paper evaluates an allocation method called Resource Efficient Quality of Service (REQS). REQS is an on-line algorithm that dynamically adjusts the resource allocation, based upon the measured quality of service (QoS). Advantages of REQS include efficient use of resources, reasonable implementation cost, and stringent QoS control. In this paper, we show how REQS dynamically allocates bandwidth to achieve a given loss rate for actual MPEG VBR videos. We also develop an enhancement for REQS to better handle these sources. Comparisons of performance and cost with a peak-rate allocation method are also presented.

We study the problem of constructing delay-constrained shared multicast trees for real-time applications in connection-oriented high-speed networks. We formulate the problem as a diameter-constrained minimum Steiner tree problem, and prove that it is NP-complete. Then we propose distributed, dynamic heuristics for solving this problem. Most previous work on shared multicast trees starts by selecting a multicast center, and then constructs a shared tree around it. One of the heuristics we propose eliminates the need for a separate center selection phase. We use simulation to compare the performance of the heuristics, and of the optimal method. These experiments measure the probability of achieving delay bounds, the tree cost, and the load-balancing ability of the methods.

Real-time and other performance guarantees for multimedia can be achieved through proper resource allocation. This paper presents an allocation method called the Dynamic Search Algorithm (DSA+). DSA+ is an on-line algorithm that dynamically adjusts the resource allocation, based upon the measured quality of service (QoS). Advantages of DSA+ include efficient use of resources, reasonable implementation cost, and stringent QoS control. In this paper, we show how DSA+ dynamically allocates bandwidth to achieve a given loss rate for actual MPEG VBR videos. We compare its performance and cost with a peak-rate allocation method. The lack of dependence of the algorithm on initial parameter settings is also demonstrated.

Real-time network applications, e.g., multimedia applications and critical control applications, are evolving at a fast pace. These applications are resource-intensive, have stringent delay requirements, and in many cases involve more than two participants. Efficient multicast communication mechanisms are, therefore, necessary to support real-time applications. In this dissertation, we study five routing problems for real-time communication on high-speed connection-oriented wide-area networks. The objective of all problems we study is to optimize the utilization of the network resources without violating the delay requirements of real-time applications. We focus primarily on multicast routing problems, but we consider also the special cases of broadcast routing and unicast routing.

Variable bit rate (VBR) traffic continues to have a more prevalent role in integrated networks. However it is difficult to efficiently manage resources and to provide a desired Quality of Service (QoS) for these sources due to their complex behavior. Dynamic resource allocation is a method of providing a desired QoS with a conservative amount of resources assigned. The idea is to adjust a resource based on QoS observations made at certain time intervals. This method benefits from not requiring static characterization of the source. Dynamic Search Algorithm (DSA) is a new allocation method introduced in this paper. This simple algorithm combines a dynamic algorithm with interrupts to quickly and efficiently adapt the bandwidth of a source to meet a desired cell loss probability. Experiments with MMBP traffic and actual MPEG traces show excellent performance, quickly allocating lower resources than current methods and requiring fewer allocation changes.

We present an MPEG slice layer model for VBR encoded video using Linear Predictive Coding (LPC) and Generalized Periodic Markov Chains. Each slice position within an MPEG frame is modeled using an LPC autoregressive function. The selection of the particular LPC function is governed by a Generalized Periodic Markov Chain; one chain is defined for each I, P, and B frame type. The model is sufficiently modular in that sequences which exclude B frames can eliminate the corresponding Markov Chain. We show that the model matches the pseudo-periodic autocorrelation function quite well. We present simulation results of an Asynchronous Transfer Mode (ATM) video transmitter using a FIFO queue and measure the average cell delay. Simulation results showed good agreement with results obtained using actual traces as sources.

It is predicted that in the near future, the transport of compressed video
will pervade computer networks. Variable Bit Rate (VBR) encoded video will
become a significant source of network traffic, due to its advantages in
statistical multiplexing gain and consistent video quality. Both systems
analysts and developers need to assess and study the impact these sources will
have on their networks and networking products. In order to do this, suitable
statistical source models are required to analyze performance metrics such as
packet loss, delay and jitter.

This paper provides a survey of VBR source
models which can be used to drive network simulations. The models are
categorized into four groups: Markov Chain and Autoregressive, TES,
Self-Similar, and i.i.d/Analytical. We present models which have been used for VBR sources containing
VBR sources containing moderate to significant scene changes and moderate to full
motion. A description of each model is given
along with corresponding advantages and shortcomings. Comparisons are made
based on the complexity of each model.

In this paper, we study the NP-hard delay-constrained least-cost path problem, and propose a simple, distributed heuristic solution: the delay-constrained unicast routing (DCUR) algorithm. DCUR requires limited network state information to be kept at each node: a cost vector and a delay vector. We prove DCUR's correctness by showing that it is always capable of constructing a loop-free delay-constrained path within finite time, if such a path exists. The worst case message complexity of DCUR is $O(|V|^3)$ messages, where $|V|$ is the number of nodes. However, simulation results show that, on the average, DCUR requires much fewer messages. Therefore, DCUR scales well to large networks. We also use simulation to compare DCUR to the optimal algorithm, and to the least-delay path algorithm. Our results show that DCUR's path costs are within 10% from those of the optimal solution.

MC routing protocols currently being standardized, PIM and CBT, propose the use of shared center-based trees, but they do not specify how to select the centers of these trees. We survey previous work on the center selection problems in the fields of operations research and communication networks.

We address the problem of determining the minimal resources necessary to satisfy a specified Quality of Service (QoS) measure using dynamic techniques. A key advantage of these techniques is that very little traffic characterization information is needed from the user. Specifically, we study the performance of a dynamic control algorithm which determines the minimum bandwidth needed to satisfy a specified average cell loss probability requirement for a given source. The emphasis of this study is to examine practical implementation issues for such techniques including transient behavior, dependence on system parameters such as buffer sizes and source burstiness, as well as algorithm paramaters such as measurment intervals.

Many distributed real-time applications require broadcasting information to all participants. This information must be received within some delay bound, and at the lowest possible cost. We formulate the problem of constructing broadcast trees for real-time traffic with delay constraints in networks with asymmetric link loads as a delay-constrained minimum spanning tree (DCMST) problem in directed networks. Then we prove that this problem is NP-complete, and we propose an efficient heuristic to solve the problem based on Prim's algorithm for the unconstrained minimum spanning tree problem. This is the first heuristic designed specifically for solving the DCMST problem. Simulation results under realistic networking conditions show that our heuristic's performance is close to optimal when the link loads are symmetric as well as when asymmetric link loads are used. Delay-constrained minimum Steiner tree heuristics can also be used to solve the DCMST problem. Simulation results indicate that the fastest delay-constrained minimum Steiner tree heuristic, DMCT, is not as efficient as the heuristic we propose, while the most efficient delay-constrained minimum Steiner tree heuristic, BSMA, is much slower than our proposed heuristic and does not construct cheaper delay-constrained broadcast trees.

Most methods for guaranteeing quality of service (QoS) in packet-switched networks require a static characterization of the user's traffic, and allocate resources accordingly. This process is inconvenient for unsophisticated users, and can result in overallocation of resources. We address the problem of automatically determining the minimal resources necessary to satisfy a specified Quality of Service (QoS) measure using dynamic techniques. Specifically, we study a dynamic control algorithm which determines the minimum bandwidth needed to satisfy a specified average cell loss probability for a given source. This algorithm is called REQS, which stands for Resource Efficient Quality of Service. REQS measures the actual cell losses, and uses this information to dynamically vary the bandwidth allocation. Experimental results show the algorithm converges quickly to the desired solution. The effect of the measurement frequency, source burstiness, buffer size and loss specification on the convergence time of the algorithm are all investigated. The algorithm is robust, converging quickly and accurately under most conditions. We demonstrate the bandwidth savings attainable by this approach over other techniques, such as the equivalent capacity. The applicability of the method for other QoS measures (such as queuing delay percentiles) is also investigated. Some of the applications of this technique include control of rate-enforcing servers, traffic shapers, and call admission control in ATM networks.

The dramatically increased bandwidths and processing capabilities of future high-speed networks make possible many distributed real-time applications, such as sensor-based applications and multimedia services. Since these applications will have traffic characteristics and performance requirements that differ dramatically from those of current data-oriented applications, new communication network architectures and protocols will be required. In this paper we discuss the performance requirements and traffic characteristics of various real-time applications, survey recent developments in the areas of network architecture and protocols for supporting real-time services, and develop frameworks in which these, and future, research efforts can be considered.

Networks supporting real-time traffic employ controlled admission of calls to ensure an acceptable quality of service. In this work, we investigate how routing and admission control interact in determining overall performance. We propose and evaluate the use of routing algorithms which take into account the constraints imposed by the admission control algorithms. These algorithms are of the least loaded path type and are found to perform better than sequential routing type algorithms which have been suggested elsewhere. We show that the new algorithms decrease call blocking probability and increase network utilization. The amount of improvement depends on such factors as the admission control function, the traffic mix, and the QOS constraints.

Two deterministic methods of Call Admission Control: Earliest Due Date and Stop&Go are evaluated. The effect of lossy source traffic shaping on routing is studied. The interaction and relative importance of routing, admission control, and traffic shaping is examined.

Interactive voice and video applications (e.g. teleconferencing) over multi-hop packet-switched networks require bounds on delay, loss, and jitter. This paper compares routing algorithms and admission control methods which are intended to provide the quality of service required by such applications. The method of comparison is detailed simulation. As part of this work, we propose several novel real-time routing algorithms.

The best-performing routing algorithm is a new method which takes into account the constraints imposed by the admission control algorithm. A routing algorithm similar to those used in the phone system is the worst of the dynamic algorithms; static routing is far worse than any of these. The differences between the routing algorithms are greatest when the network is highly connected, and when admission control constraints are difficult to meet. The issue of {\em fairness} is also considered in the evaluation of the routing algorithms.

Three admission control algorithms were compared, under varying traffic conditions and QoS requirements. The impact of traffic shaping on link utilizations was investigated. Overall, the choice of admission control method was more important than the choice of routing algorithm.

This work is the first detailed evaluation of routing algorithms for voice and video traffic in multi-hop networks that provide strong end-to-end guarantees.

Multicast (MC) routing algorithms capable of satisfying the quality of service (QoS) requirements of real-time applications will be essential for future high-speed networks. We compare the performance of all of the important MC routing algorithms when applied to networks with asymmetric link loads. Each algorithm is judged based on the quality of the MC trees it generates and its efficiency in managing the network resources. Simulation results over random networks show that unconstrained algorithms are not capable of fulfilling the QoS requirements of real-time applications in wide-area networks. Simulations also reveal that one of the unconstrained algorithms, reverse path multicasting (RPM), is quite inefficient when applied to asymmetric networks. We study how combining routing with resource reservation and admission control improves RPM's efficiency in managing the network resources. The performance of one semiconstrained heuristic, MSC, three constrained Steiner tree (CST) heuristics, KPP, CAO, and BSMA, and one constrained shortest path tree (CSPT) heuristic, CDKS are also studied. Simulations show that the semiconstrained and constrained heuristics are capable of successfully constructing MC trees which satisfy the QoS requirements of real-time traffic. However, the cost performance of the heuristics varies. BSMA's MC trees are lower in cost than all other constrained heuristics. Finally, we compare the execution times of all algorithms, unconstrained, semiconstrained, and constrained.

Distributed Real-time applications requiring quality of service (QoS) guarantees and involving groups of users will dominate future's high speed networks. Efficient multicast routing (MCR) algorithms are necessary for these applications. We survey the existing MCR algorithms and study their characteristics. These algorithms were not designed to provide QoS guarantees. We formulate the multicasting problem for applications with QoS requirements and define the criteria for evaluating the performance of the MCR algorithms when applied to this problem. We also describe the simulator we used for evaluating these algorithms.

Distributed multimedia applications requiring quality of service (QoS) guarantees and involving groups of users will dominate future's high-speed networks. Efficient multicast routing algorithms are necessary for these applications. This report compares the performance of multicast routing algorithms when applied to real-time networks. We briefly discuss previous work on multicast routing, then we formulate the multicasting problem for applications with QoS requirements and define the criteria for evaluating the performance of the MC routing algorithms. We study five MC routing algorithms, three unconstrained algorithms, and two heuristics designed specifically for ATM networks. A simulator is used to evaluate the performance of the algorithms. We present simulation results over random network graphs that show that unconstrained routing algorithms are capable of satisfying the delay requirements of real-time services when applied to networks spanning distances of up to a 1000 Km. We also use simulation to evaluate the ability of the algorithm to balance the network load.

Multicast (MC) routing algorithms capable of satisfying the QoS requirements of multimedia applications will be essential for future's high-speed networks. We compare the performance of selected MC routing algorithms when applied to networks with asymmetric link loads. Each algorithm is judged based on the quality of the MC tree it generates and its efficiency in managing the network resources. Simulation results over random networks show that unconstrained algorithms are not capable of fulfilling the QoS requirements of applications utilizing networks spanning large areas. One algorithm, reverse path multicasting, is not suitable for asymmetric networks irrespective of the requirements of the application. Three constrained Steiner tree (CST) heuristics are also studied. Simulations show that all three behave similarly and that they can manage the network efficiently and construct low cost MC trees that satisfy the QoS requirements of multimedia traffic. The execution times of the CST heuristics are larger than those of unconstrained algorithms.

We investigate a method for supporting diverse quality-of-service requirements in broadband networks based on ATM technology. The method uses deterministic bandwidth reservation at the Virtual Path (VP) level and statistical multiplexing within each VP. A deterministic server such as a Weighted Round Robin (WRR) server is used to enforce bandwidth reservations among the VPs. We develop a connection admission algorithm which accounts for end-to-end delay and loss guarantees for Virtual Circuits which traverse a single VP. We show that under certain conditions the amount of network bandwidth required by a VP is minimized by incurring all the allowable loss at the first link of a VP. Achievable utilization is demonstrated using simulation. The effect of the parameters of the WRR server ({\em i.e.}, the vacation time) on the cell loss probability is also studied using simulation.

We address the problem of providing quality-of-service (QoS) guarantees in a multiple hop packet/cell switched environment while providing high link utilization in the presence of bursty traffic. A scheme based on bandwidth and buffer reservations at the Virtual Path level is proposed for ATM networks. This approach enables us to provide accurate end-to-end QoS guarantees while achieving high utilization by employing statistical multiplexing and traffic shaping of bursty traffic sources. A simple round robin scheduler is proposed for realizing this approach and is shown to be implementable using standard ATM hardware viz. cell spacers. The problem of distributing the bandwidth and buffer space assigned to a VP over its multiple hops is addressed. We prove the optimality of the approach of allowing all the end-to-end loss to occur at the first hop under some conditions and show that its performance can be bounded with respect to the optimal in other conditions. This results in an equal amount of bandwidth to a VP at each hop and essentially no queueing after the first hop. Using simulations, the average case performance of this approach is also found to be good. Additional simulation results are presented to evaluate the proposed approach.

This paper presents a slice based model for VBR-encoded MPEG videos. This model's random variable is independent and would fit clas- sical distributions. We analyzed four MPEG-1 VBR encoded high quality, color video sequences. None of the sequences contained audio. We present three types of slice based models and discuss the merits of each. We show the distributions given by each of the models and show their fit to the Gamma and Pareto distributions using the QQ plot.

In this paper, we statistically characterized four VBR encoded video sequences, containing I/B/P frames, at the Slice layer with the goal of developing an accurate source model to better under- stand the bit-rate behavior of these sources. We presented the cells/slice distributions and showed that it is ^Sheavy tailed^T and fits the Pareto distribution better than Gamma. We showed that an 8-state Markov Chain fits the cells/slice distribution well, reaching steady state after 37 to 80 transitions (2 to 5 frames). We also showed that the autocorrelation function is quasi-peri- odic which is mostly due to the frame sequence pattern rather than spatial content. We discussed the impact of I/B/P sequences on multiplexing and dynamic bandwidth allocation and proposed a multiplexing method called Time Shifted Multiplexing (TSM); whereby, the multiplexer attempts to overlap I and P frames of one video stream with B frames of an other. This tends to reduce both Peak-to-Mean-Ratio and Coefficient-of-Variation of the multiplexed output stream. We showed that coefficient-of-varia- tion reduced in half and bandwidth requirements reduced by 41% using TSM.

The increasing use of audio, video and other multimedia applications on computers mandates the use of real-time processor scheduling techniques. Real-time scheduling algorithms have mostly concentrated on meeting application deadlines (such as those required for video playback). An important requirement of such applications is a large buffer memory, due to the high rates of data generated. We investigate priority assignment algorithms for static-priority, preemptive real-time scheduling of periodic task sets. These algorithms are directed at applications in which worst case execution latency is not as important as buffer minimization. Examples of such applications include video and audio playout / recording, browsing through a database with audio / video data, and all types of non-interactive real-time applications. We refer to these as throughput-oriented real-time applications.

The techniques developed retain the simplicity of static priority scheduling, while improving the processor utilization which can be obtained. In addition, we are able to derive hard bounds on worst case execution time which are low enough for most practical deadline-based applications. We show that the standard rate-monotonic priority assignment algorithm is not optimal in terms of our goal of minimising input buffer size. Approximate algorithms are then found which perform better than the rate-monotonic algorithm, and bounds on their performance are derived. Average case performance is studied using simulation. The best algorithm combines rate-monotonic and shortest-job-first priority assignments. We show how to obtain deadline-based scheduling algorithms for task sets with arbitrary deadlines. The existence of an algorithm which minimizes buffer space is left as an open problem.

This thesis introduces an interprocessor communication network for mobile robot computer architectures and real-time communication networks. The objective of the research is to provide communication with very low delay.

The segmented bus is a reconfiguralbe interconnection network for intelligent mobile robot aplications. The segmented bus employs a preemptive circuit-switched message transfer technique for low delay. For mobile robot aplications, message delays are lower on the segmented bus than on alternatives such as multiple buses.

Interactive real-time aplications require low end-to-end delay bounds and zero losses. This thesis offers solutions to admission control and low latency message transfers for interactive real-time message flows. Our proposed adaptive slack allocation method will accept a larger number of flows than a static allocation. Preemptive cut-through multiplexing reduces the minimum achievable end-to-end delay bounds to values close to that of circuit-switching. We show how these techniques can be applied to ATM networks, and assess the hardware and processing costs associated with these techniques.

This paper addresses the problem of providing very low guaranteed end-to-end delay bounds in packet-switched wide area networks such as B-ISDN. Such quality of service is necessary for real-time flows requiring no losses, and low end-to-end delay. These flows are used in continuous media, distributed sensing and command/control applications. Our works offers solutions to two problems: (i) flow admission control, and (ii) low-latency message transfers. The off-line flow admission control procedure adaptively reallocates slack to heavily loaded links. We show it results in higher acceptance rates than non-adaptive methods. The multiplexing or service method we propose combines preemption and cut-through to reduce the minimum achievable end-to-end delay bound. Preemptive cut-through can be implemented in ATM networks to provide tight delay bounds. The implementation cost of this method is examined as well.

Packet / cell switched networks are increasingly being used to carry real-time multimedai traffic such as voice and video. This kind of traffic requires certain guarantees on the Quality of Service (QoS) it receives from the network. Typically, QoS measures include end-to-end latency, and loss probabilities. A key issue facing the network service provider is that of providing such QoS guarantees to users while utilizaing network resources as efficiently as possible. In this thesis, three problems are analyzed on increasing the efficiency of network resource usage while providing strong guarantees on the end-to-end QoS received by users of such networks.

The first problem is whether existing routing algorithms can be used for real-time traffic. New routing algorithms are developed which perform better than algorithms not designed specifically for real-time traffic. It is shown that routing algorithms designed to exploit the constraints of the admission control algorithm result in improved call acceptance. The interaction between the routing and admission control functions is studied. The relative performance of three standard admission control schemes is also studied.

The second problem is what combination of multiplexing policies to use for efficient transport for real-time traffic. This thesis suggests an architecture which results in improved bandwidth utilization over existing schemes which provide end-to-end QoS guarantees. The architecture is based on deterministic bandwidth reservation at the level of Virtual Paths (i.e., on groups of channels rather than individual channels). It is shown that significant utilization levels are achievable while retaining the abilitiy to provide end-to-end QoS guarantees. The problem of distributing given network resources over the different physical links traversed by a VP in the proposed architecture is addressed. The improved resource usage of an approach which lets all the loss occur at the first physical hop is proved. An implementation of the proposed architecture is suggested and examined.

The final problem addressed in this thesis is how to allocate resources with minimal user input and guidance. An algorithm is developed for determining on-line the minimum resources required to satisfy a specified QoS. The use of this technique is demonstrated for determining the minimum bandwidth allocation needed to meet a specified constraint on average loss probability. The algorithm is shown to be robust and accurate under different conditions while requiring very little knowledge of the traffic generation statistics of the source. The technique is shown to be applicable to different types of resources and different QoS definitions.

The Real-Time Communication Project last modified May 24, 1999