Designing Communication Networks with Fixed or Nonblocking Traffic Requirements
J. Andrew Fingerhut · Open Scholarship Institutional Repository (Washington University in St. Louis) · 1992
A general framework for specifying communication network design problems is given. We analyze the computational complexity of several specific problems within this framework. For fixed multirate traffic requirements, we prove that a particular network analysis problem is np-complete, although several related network design problems are either efficiently solvable or have good approximation algorithms. For the case when we wish the network to operate without blocking any connection requests, we give efficient algorithms for dimensioning the link capacities of the network. This work is supported by the National Science Foundation, Bell Communications Research, Bell Northern Research, Digital Equipment Corporation, Italtel SIT, NEC, NTT, and SynOptics. 1. Introduction Much work has been done on the computational problem of designing low-cost communication networks (see [GN89, GTD + 89, GW90, GK90, KKG91, AKR91] and references therein). The general problem is: given a collection of no...