Technical Report Number
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.
Fingerhut, J. Andrew, "Approximation Algorithms for Configuring Hierarchical Nonblocking Communication Networks" Report Number: WUCS-93-19 (1993). All Computer Science and Engineering Research.