Chicago Journal of Theoretical Computer Science

Volume 1996

Article 3

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.

Optimal Virtual Path Layout in ATM Networks with Shared Routing Table Switches

Ornan Gerstel (IBM), Israel Cidon (Technion), and Shmuel Zaks (Technion)
31 October 1996
Selected Papers from PODC 1994, David Peleg editor

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.

DOI: 10.4086/cjtcs.1996.003
[] Article 2 [] Article 4
[back] Volume 1996 [back] Published articles
[CJCTS home]

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