Technical Report CS0831

Authors: I. Cidon, O. Gerstel and S. Zaks
Abstract: We study the problem of designing a layout of virtual paths on a given ATM network. We first define a mathematical model that captures the characteristics of virtual paths. In this model we define the general virtual path layout problem, and a more restricted case; While the general case layout should cater connections between any pair of nodes in the network, the restricted case layout should only cater connections between a specific node to the other nodes. For the latter case we present an algorithm that finds a layout by decomposing the network into sub-networks and operating on each sub-network recursively; This algorithm enables the formulation of a quantitative upper bound for the problem. We then present a greedy approach for the same problem, and prove the correctness and optimality of the resulting layout. Finally, we demonstrate how the algorithm for the restricted case is used as a building block in a solution to the general problem, and prove the asymptotic optimality of our result. The results exhibit a tradeoff between the efficiency of the call setup and both the utilization of the VP routing tables, and the overhead during recovery from link disconnections.
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 (, 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 1994
To the main CS technical reports page

Computer science department, Technion