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.

Abstract

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

DOI: 10.4086/cjtcs.1996.003

---

Article 2 Article 4
Volume 1996 Published articles

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