Multipoint routing and traffic management in high-speed networks
Anoop Ghanwani, Erol Gelenbe · 1998
High speed networking has brought with it a number of challenges due mainly to the need for supporting applications having diverse quality of service (QoS) requirements. QoS is typically characterized by parameters such as loss and end-to-end latency. The asynchronous transfer mode (ATM) technology, designed to be scalable in speed and geographical distance, has the ability to seamlessly integrate data from various applications for transport over a single network. As such, it is widely considered to be the transport technology of choice for emerging and future high speed networks such as the broadband integrated services digital network (B-ISDN). In this work, we are concerned with the key areas of multiparty communications and traffic control mechanisms for high speed networks with an emphasis on ATM. Multicast communication involves the transport of data to multiple receivers. In order to enable multicast data transfer in an ATM network, a tree must be constructed which spans the source and all the destinations. For the purpose of routing, the network is usually modeled as a weighted, undirected graph. The edge weights represent the cost to be optimized while constructing the tree. The problem is to find a minimum Steiner tree for the graph given a set of destinations. This dissertation reviews available heuristics for solving this problem which run in polynomial time. We then use the random neural network (RNN) to improve on the solutions delivered by these heuristics. Next, we consider a different flavor of the problem for delay sensitive applications. Here, the goal is to minimize tree cost while ensuring a bounded end-to-end delay between the source and each of the destinations and requires the construction of a constrained minimum Steiner tree. We review existing heuristics for this problem, and then develop a new one. For both of the above problems, exhaustive simulation shows that the new heuristics are able to find trees that are significantly closer to optimal than those found by the existing ones in many instances. Our next concern is a method to provide efficient multicast support for large multicast connections in an ATM network. In order to support multicast, ATM switches at the branch-point of a multicast tree must be capable of replicating cells from an input port and routing them to multiple output ports. We develop a queueing model to study this behavior in a single node. Finally, we explore issues concerning traffic management in ATM networks. We review existing work on scheduling disciplines ranging from simple priority schemes to weighted fair queueing. We then focus on a dynamic priority queueing method for multiple classes of traffic in an ATM network. This scheduling discipline has a very desirable property of providing minimum bandwidth guarantees for each class of traffic. We use an approximation to perform a simple queueing analysis for this system. We find that the approximation yields very accurate results for a variety of traffic conditions and operating parameters. (Abstract shortened by UMI.)