Technical Report CS0852

 TR#: CS0852 Class: CS Title: OPTIMAL LAYOUTS ON A CHAIN ATM NETWORK. Authors: O. Gerstel, A. Wool and S. Zaks PDF CS0852.pdf Abstract: We study a routing problem which occurs in high-speed (ATM) networks, termed the one-to-many virtual path layout problem'' on chain networks. This problem is essentially a tree embedding problem on a chain host graph. We present four performance measures to the quality of such an embedding which have practical implications, and find optimal solutions for each of them. We first show that the search can be restricted to the class of layouts with no crossovers. Given bounds on the load ${\cal l}$ and number of hops ${\cal h}$ in a layout, we then present a family of ordered trees ${\cal T(l,h)}$, within which an optimal solution can be found (if one exists at all); this holds for either the worst-case or average-case measures, and for a chain of length $n$, with $n \leq \left( \begin{array}{c} l+h\\[-0.2cm] l \end{array} \right )$. For the worst-case measures these trees are used in characterizing, constructing and proving the optimality of the solutions. For the average-case measures polynomial dynamic programming algorithms are presented which find optimal solutions for all cases. 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/CS0852), rather than to the URL of the PDF files directly. The latter URLs may change without notice.