Approximation algorithms for configuring nonblocking communication networks
J. Andrew Fingerhut · 1994
To support network applications that require guaranteed throughput, such as interactive audio and video communication, it is desirable to have a network architecture that allows users to reserve bandwidth on paths of links in the network. In such a network, attempts to reserve bandwidth may fail due to insufficient link capacities, i.e., the attempt blocks. In this dissertation, we examine networks with link bandwidths chosen so that the network is nonblocking, subject to some restrictions on the requests that can be made. Most previous work restricts the traffic in the network by specifying the maximum traffic between each pair of nodes. We restrict the traffic by specifying the maximum traffic that may leave or enter each node. With such restrictions, a star network topology often gives a nonblocking network with cost close to optimal, if not exactly optimal. We support this claim by analytical results, and experimental results on randomly generated instances. We also generalize this method of specifying the traffic for larger networks, in which groups of nodes can be organized into clusters with high traffic among nodes within the clusters, but less traffic between nodes in different clusters. This work is applicable to configuring Asynchronous Transfer Mode (ATM) networks, in which multicast connections are possible. We show that if the network nodes are capable of supporting multicast connections without blocking, then the entire network can also.