The virtual path layout problem in fast networks (extended abstract)
O. Gerstel, Shmuel Zaks · 1994
In th~paper we present a new model, within which we define a generrd routing problem (termed virtual path layout) that occurs in fast networks (ATM).In an effort to solve this general problem, we first define an intermediate problem, and prove it is NPcomplete.We then 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 solve the general problem using the polynomially solvable subproblem as a building block.The results exhibit a tradeoff between the performance of a routing scheme and its resource utilization.