Path Layout in ATM Networks

摘要

This paper surveys recent results in the area of virtual path layout in ATM networks. 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 or a vertex), and the stretch fac-tor (the total length traversed between pairs of vertices, comparing with the distance between them). The results include recursive constructions, greedy and dynamic programming algorithms, lower bounds proofs, and NP-complete results.