### Path Layout in ATM Networks

### Shmuel Zaks, The Technion

Recent results in the area of virtual path layout in ATM networks
are discussed. We focus on the one-to-all (or broadcast) and the
all-to-all problems. We present a model for theoretical studies of
these layouts, which amounts to covering the network with simple
paths, under various constraints. The constraints are the hop count
(the number of paths traversed between the vertices that have to
communicate), the load (the number of paths that share an edge),
and the stretch factor (the total length traversed between pairs
of vertices, compared with the distance between them).
For the first problem a complete characterization of the path layout
construction problem for networks with hop count bounded by $h$
and load bounded by $l$ is presented.
We prove that the problem of determining the existence of such layouts
is NP-complete for every given values of $h$ and $l$ (any given stretch
factor), except for the cases $h=2, l=1$ and $h=1$, any $l$, for
which we give polynomial-time layout constructions (for the case of
an unbounded stretch factor).

For both problems a geometric approach is presented, that enables a
simple argumentation about optimality of layout constructions, for
chain, augmented path and ring networks.
Stated in graph-theoretic terms, the problem amounts to the
embedding of the vertices of a graph with $N$ nodes onto the points
$1,2,\cdots,N$ of the $x$-axis. We look for a graph with minimum
diameter $D_c(N)$, for which such an embedding is possible, given
a bound $c$ on the cutwidth of the embedding.
We develop a technique to embed the nodes of such graphs into the
integral lattice points in the $c$-dimensional $l_1$-sphere.
Using geometric arguments, we derive analytical bounds for $D_c(N)$,
which result in substantial improvements on some known lower and upper
bounds.
This geometric approach helps also in understanding the duality between
the parameters of hop count and load in certain layout constructions.