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.