# 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 PDF CS0845.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. Copyright The 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.