Protocol design for ATM networks: Theory and implementation

Asynchronous Transfer Mode (ATM) has generated new challenging problems for computer network designers. One of the challenges lies in the efficient management of ATM traffic so that the communication bandwidth of the network can be optimally utilized. This dissertation addresses both practical and theoretical issues in ATM. In particular, two aspects of ATM networks are discussed: the theoretical foundation on how to provide multicast services and "intelligent congestion control" for traffic management.; In many networking applications, it is essential for a process to disseminate the same piece of information to other processes. One of the main contributions in this dissertation is to establish new optimality results on the message complexity of fault-tolerant broadcast/multicast protocols, in which the processes are subject to crash, sending, and receiving omission failures. The new insights provided in the lower bound proofs further yield a graph-theoretic characterization of all message-optimal protocols in failure-free executions. These characterizations for reliable broadcast/multicast protocols in failure-free executions are also the first known in the literature.; Since data applications usually require a service that dynamically shares the available bandwidth among all active users, such a service is referred to as a best-effort or available bit rate (ABR) service. Despite considerable past research efforts in the area of congestion control in high speed networks, there were major limitations in the existing control schemes for ABR service. To address the problems, this dissertation proposed a novel traffic management technique, which is now referred to as "intelligent congestion control" by the ATM Forum, and has been adopted as the standard approach to congestion control of ABR service.; This dissertation also addresses the fundamental limitations of all end-to-end congestion control schemes for ABR service. These results will help us design schemes that are theoretically best possible and consider the trade-offs among various parameters such as transient period, maximum queue length, and link utilization. After considering the issues on providing unicast ABR service, we present the first unified approach to transform almost all existing congestion control algorithms for unicast ABR service into corresponding algorithms for multicast service.