Title

Designing Communication Networks with Fixed or Nonblocking Traffic Requirements

Authors

J. Andrew Fingerhut, Washington University in St Louis

Document Type

Technical Report

Publication Date

1992-01-10

Filename

WUCS-91-55.pdf

DOI:

10.7936/K7B56H2F

Technical Report Number

WUCS-91-55

Abstract

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.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7B56H2F

Recommended Citation

Fingerhut, J. Andrew, "Designing Communication Networks with Fixed or Nonblocking Traffic Requirements" Report Number: WUCS-91-55 (1992). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/673