We study a routing problem which occurs in high-speed (ATM) networks,
termed the ''rooted virtual path layout problem'' on chain networks. T
his problem is essentially a tree embedding problem on a chain host gr
aph. We present four performance measures for the quality of such an e
mbedding 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 I an
d number of hops h in a layout, we then present a family of ordered tr
ees T(l, h), within which an optimal solution can be found (if one exi
sts at all); this holds for either the worst-case or average-case meas
ures, and for a chain of length n, with n less than or equal to (l+h/l
). For the worst-case measures these trees are used in characterizing,
constructing, and proving the optimality of the solutions. For each a
verage-case measure, a recursive formulation of the optimal solution i
s presented, from which an optimal polynomial dynamic programming algo
rithm is derived. Furthermore, for the unweighted average measures, th
ese formulations are explicitly solved, and the optimal solutions are
mapped to T(l, h). (C) 1998 Elsevier Science B.V. All rights reserved.