Technical Report CS0845

TR#:CS0845
Class:CS
Title: OPTIMAL VIRTUAL PATH LAYOUT IN ATM NETWORKS WITH SHARED ROUTING TABLE SWITCHES.
Authors: O. Gerstel, I. Cidon and S. Zaks
PDFCS0845.pdf
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 (termed {\em virtual path layout} in which, given a network of switches and links, one must find a set of paths in the network, termed the virtual path layout, so that each pair of switches may connect using a route which 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 switches. Our goal is to find a layout which minimizes this utilization, assuming that each such switch 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 switches 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 sub-optimal solution to the original problem. The results exhibit a tradeoff between the performance of a routing scheme and its resource utilization.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1995/CS/CS0845), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1995
To the main CS technical reports page

Computer science department, Technion
admin