Approximation Algorithms for Configuring Hierarchical Nonblocking Communication Networks

A framework is given for specifying nonblocking traffic limits in a connection-oriented communications network. In this framework, connections may be point-to-point or mutlipoint, and the data rates may vary from one connection to another. The traffic limits may be flat , or they may also be hierarchical, representing communities of interest within the network that have higher traffic among themselves than with the rest of the network. The communication networks are constructed from switches (or nodes) and trunks, which connect pairs of switches. This framework is intended to model Asynchronous Transfer Mode (ATM) networks and traffic. We present a way of computing a lower bound on the cost of any nonblocking network that can satisfy the limits, and show that this lower bound is good analytically and through experiments on randomly generated instances