Algorithms for Designing Nonblockings Communication Networks with General Topologies

J. Andrew Fingerhut, Washington University in St Louis


A framework is given for specifying nonblocking traffic requirements in a connection-oriented communications network. In this framework, connections may be form one point to one other point, or they may involve multiple points. Different connections may have different data rates. 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. Several computational problems are formulated, each intended to find a minimum cost configuration of switches and trunks which satisfy given traffic requirements. Efficient algorithms have been found for some problems, and computational hardness results for others.