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.
Back to the Petri Nets Bibliography