Published by MIT Press. Copyright 1996 Massachusetts Institute of Technology.

Your institution may already be a
subscriber to CJTCS. If not,
**please subscribe**
for legitimate access to all journal articles.

In this paper we present a new model for routing that occurs in high-speed ATM networks. Within this model we define a general routing problem, called a virtual path layout. Given a network of nodes (switches) and links, one must find a set of paths in the network, termed the virtual path layout, whereby each pair of nodes may connect using a route that is a concatenation of a small number of virtual paths and is also short in terms of the network links it traverses. Each such layout implies a utilization of the routing tables in the network's nodes. Our goal is to find a layout that minimizes this utilization, assuming that each such node has a central routing table. We prove that this problem is NP-complete, and consequently focus on a simpler problem, in which it is required to connect all nodes to a single switch. Next, we prove that even this problem is NP-complete, and restrict some of the assumptions to yield a practical subproblem, for which we present a polynomial-time greedy algorithm that produces an optimal solution. Finally, we use this restricted problem as a building block in finding a suboptimal solution to the original problem. The results exhibit a tradeoff between the performance of a routing scheme and its resource utilization.

- Preformatted versions of the article
- DVI (173,956 bytes)
**PostScript**(439777 bytes)- PDF (395,321 bytes)
- Audio by
**AsTeR**(to appear)

- Source materials for custom formatting
**LaTeX**(`cj96-03.tex`, 140,428 bytes)**BIBTeX**(`cj96-03.bib`, 7,105 bytes)- Parameter settings for custom
formatting (
`cjropts.tex`, 323 bytes) - Self citation in
**BIBTeX**(325 bytes)

- Online discussion
- Instructions for Readers

Article 2 Article 4

Volume 1996 Published articles

Last modified: Tue Nov 25 10:54:56 CST