Approximation Algorithms for Configuring Hierarchical Nonblocking Communication Networks
J. Andrew Fingerhut · 1993
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 multi-point, 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 Aynchronous Transfer Mode (ATM) networks and traffic. We present away 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.