Considers the support of hard real-time connections in ATM networks. In an ATM network, a set of hard real-time connections can be admitted only if the worst-case end-to-end delays of cells belonging to individual connections are less than their deadlines. There are several approaches to managing the network resources in order to meet the delay requirements of connections. This paper focuses on the use of traffic regulation to achieve this objective. Leaky buckets provide simple and user-programmable means of traffic regulation. An efficient optimal algorithm for selecting the burst parameters of leaky buckets to meet connections' deadlines is designed and analyzed. The algorithm is optimal in the sense that it always selects a set of burst parameters whose mean value is minimal and by which the delay requirements of hard real-time connections can be met. The exponential size of the search space makes this problem a challenging one. The algorithm is efficient through systematically pruning the search space. There is an observed dramatic improvement in the system performance in terms of the connection admission probability when traffic is regulated using this algorithm.

We study connection-oriented service in an FDDI-ATM-FDDI heterogeneous network for real-time applications. We design and analyze an algorithm for connection admission control (CAC) for such a network. Upon a request of connection establishment, the CAC determines if the worst case delays of the requesting and existing connections can be satisfied given the available network resources. If so, the CAC allocates appropriate network resources to the requesting connection. The process of allocating resources for homogeneous networks (e.g. FDDI-only or ATM-only) may not be applied directly to a heterogeneous network environment (e.g. FDDI-ATM-FDDI network) because heterogeneity adds more complexity to the process. Hence resource allocation in a heterogeneous network needs more careful analysis than its homogeneous counterpart. We propose a CAC algorithm that will, by proper parameter tuning, allocate sufficient but not excessive network resources to the requesting connection in an FDDI-ATM-FDDI network. We show that the system can achieve satisfactory performance with this CAC algorithm. Our approach is compatible with current network standards and hence can be readily used in practical systems.

We address the issues of stability in ATM networks. A network is stable if and only if all the packets have a bounded delay. We first consider ATM networks with an FCFS scheduling policy. We then study networks with a priority driven scheduling policy. For each network, we develop criteria for testing the stability of an ATM network and methods of deriving delay bounds in a stable network. In previous work, the Cruz-Gallager-Parekh (1991, 1992) ring has been a "benchmark" architecture to study the stability problem. For example, Gallager and Parerkh (1993) claimed that the ring with a size of no more than four switches is stable when the total utilization of the links is less than 100%. We validated this result. Furthermore, we find that a ring with large number of switches is stable if the utilization of each link is less than or equal to 73%.

A CAC algorithm must efficiently determine if a new connection can be admitted by verifying that its QoS requirements can be met without violating those of previously admitted connections. In hard real-time systems, the QoS requirements are specified in terms of end-to-end cell deadlines and no cell loss due to buffer overflow. A CAC algorithm must account for interdependencies among connections caused by statistical multiplexing of cells in ATM networks. Arbitrarity of network topology may lead to cyclic dependencies among various connections. We present an efficient CAC algorithm that addresses the above issues. The algorithm uses a traffic descriptor called the maximum traffic rate function to effectively compute bounds on end-to-end delays of connections and buffer requirements within the network. Our work differs from most previous work in that it does not require traffic restoration inside the network.

For any connection admission control (CAC) algorithm to work correctly and efficiently, accurate information of the traffic flow out of the host systems is required. We develop several approximation approaches for modeling the traffic flows of hard real-time connections. We show that without accurate traffic characterization, the CAC algorithm may do either of the following: (1) admit connections that may cause network congestions which results in violating connection deadline requirements; or (2) pessimistically reject many connections whose QoS can be guaranteed. We propose a traffic approximation model that can characterize the traffic correctly and efficiently, achieving a higher admission probability. From our experimental data we observe that the source traffic from a typical host is bursty. This burstiness may cause congestion within the network. To overcome this problem, we propose and analyze a simple traffic regulation mechanism at the application layer. The performance evaluation data shows that in the regulated system the traffic burstiness is lower and the probability of a connection being admitted is higher than the unregulated system.

We address the issue of guaranteeing the end-to-end deadlines of hard real-time connections in an ATM network. In an ATM network, a set of hard real-time connections can be admitted only if the end-to-end delays of cells belonging to individual connections are not more than their deadlines. We systematically decompose an ATM network into constant delay and variable delay servers to facilitate the delay analysis. Effective traffic description is the key part of such a process. We propose a comprehensive traffic description function that provides adequate information about the worst case traffic behavior of connections anywhere in the network. We also study some simple approximations of this function that perform reasonably well in practice. We analyze and compare the performance of ATM networks with FCFS and WRR link scheduling policies under different loading conditions.

In this paper, we address issues related to providing guaranteed real-time communication in ATM local area networks. We concentrate on output link scheduling because it plays a critical role in meeting message deadlines. We are particularly interested in the weighted round robin scheduling policy because of its simple design and implementation. To use weighted round robin scheduling for hard real-time applications, the weights must be properly allocated to each of the connections. We propose and analyze two weight allocation schemes. The first scheme is heuristic, and is easy to understand and implement. The second scheme is optimal. That is, it can always guarantee a set of hard real-time connections whenever it is possible to do so. We evaluate and compare the system performance in terms of its admission probability-the probability that deadlines of all connections in a randomly chosen connection set can be met. We find that the optimal weight allocation scheme indeed performs the best. However, the heuristic scheme performs closely to the optimal scheme over a wide range of loading conditions.

This paper considers the support of hard real-time connections in ATM networks. In an ATM network, a set of hard real-time connections can be admitted only if the worst case end-to-end delays of cells belonging to individual connections are less than their deadlines. Although there are several approaches to manage the network resources in order to meet the delay requirements of connections, we focus on the use of traffic regulation to achieve this objective. Leaky buckets provide simple and user-programmable means of traffic regulation. We design and analyse an efficient optimal algorithm for selecting the burst parameters of leaky buckets to meet connections' deadlines. Our algorithm is optimal in the sense that it always selects burst parameters to meet the delay requirements of hard real-time connections whenever some such assignment exists. The exponential size of the search space makes this problem a challenging one. Our algorithm is efficient and we observe a dramatic improvement in the system performance in terms of the connection admission probability when traffic is regulated using our algorithm.

We study the effect of the output link scheduling discipline of an ATM switch on the ability of an ATM LAN to admit real-time connections. Three output link scheduling policies are studied: first come first served (FCFS), round robin (RR), and packet-by-packet generalized processor sharing (PGPS). We derive connection admission criteria for the three scheduling policies. To evaluate the performance of the three scheduling policies, we introduce the metric of admission probability. The admission probability gives the probability that a randomly chosen set of real-time connections will be admitted into the network. The admission probability allows system designers to study the performance of different scheduling policies over a wide range of network loads. We observe that the performance of the three scheduling policies is sensitive to message deadlines. When the deadlines are small, PGPS outperforms both RR and FCFS, and RR outperforms FCFS. When the deadlines are large, all three scheduling policies perform the same. We also note that although PGPS is better than RR and FCFS most of the time, its improved performance is achieved at the cost of high implementation complexity and run time overheads.>