CJTCS Volume 1996 Article 3

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
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.

[] Article 2 [] Article 4
[back] Volume 1996 [back] Published articles
[CJCTS home]

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