*For the most recent entries see the
Petri Nets Newsletter.*

## ATM Layouts with Bounded Hop Count and Congestion.

Flammini, M.;
Nardelli, E.;
Proietti, G.
In:
Mavronicolas, M.; Tsigas, Ph.: *Lecture Notes in Computer Science, Vol. 1320: Distributed Algorithms, Proc. of 11th International Workshop, WDAG'97, Saarbrücken, Germany*, pages 52-66.
Springer,
September 1997.

Abstract:
In this paper we consider two new cost measures related to the
communication overhead and the space requirements associated to virtual
path layouts in ATM networks, that is the edge congestion and the node
congestion. Informally, the edge congestion of a given edge e at an
incident node u is defined as the number of VPs terminating of starting
from e at u, while the node congestion of a node v is defined as the
number of the VPs having v as an endpoint. We investigate the problem of
constructing virtual path layouts allowing to connect a specified root
node to all the others at most h hops and with maximum edge or node
congestion c, for two given integers h and c.e first give tight results
concerning the time complexity of the construction of such layouts for
both the two congestion measures, that is we exactly determine all the
tractable and intractable cases. Then, we provide some combinatorial
bounds for arbitrary networks, together with optimal layouts for specific
topologies such as chains, rings, grids and tori. Extensions to
d-dimensional grids and tori with d>2 are also discussed.

*Do you need a refined search? Try our search engine
which allows complex field-based queries.*
*Back to the Petri Nets Bibliography*