In this paper we deal with the problem of designing virtual path layouts in ATM networks when the hop-count is given and the load has to be minimized. We first prove a lower bound for networks with arbitrary topology and arbitrary set of connection requests. This result is then applied to derive lower bounds for the following settings: (i) one-to-all (one node has to be connected to all other nodes of the network) in arbitrary networks; (ii) all-to-all (each node has to be connected to all other nodes in the network) in several classes of networks, including planar and k-separable networks and networks of bounded genus. We finally study the all-to-all setting on two-dimensional meshes and we design a virtual path layout for this problem. When the hop-count and the network degree are bounded by constants, our results show that the upper bounds proposed in this paper for the one-to-all problem in arbitrary networks and for the all-to-all problem in two-dimensional mesh networks are asymptotically optimal. Moreover, the general lower bound shows that the algorithm proposed in Gerstel (Ph.D. Thesis, Technion-Haifa, Israel, 1995) for the all-to-all problem in k-separable networks is also asymptotically optimal. The upper bound for mesh networks also shows that the lower bound presented in this paper for the all-to-all problem in planar networks is asymptotically tight.
On the design of efficient ATM routing schemes / Becchetti, Luca; Bertolazzi, Paola; Gaibisso, Carlo; Gambosi, Giorgio. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 270:1-2(2002), pp. 341-359. [10.1016/S0304-3975(00)00396-0]
On the design of efficient ATM routing schemes
BECCHETTI, Luca;
2002
Abstract
In this paper we deal with the problem of designing virtual path layouts in ATM networks when the hop-count is given and the load has to be minimized. We first prove a lower bound for networks with arbitrary topology and arbitrary set of connection requests. This result is then applied to derive lower bounds for the following settings: (i) one-to-all (one node has to be connected to all other nodes of the network) in arbitrary networks; (ii) all-to-all (each node has to be connected to all other nodes in the network) in several classes of networks, including planar and k-separable networks and networks of bounded genus. We finally study the all-to-all setting on two-dimensional meshes and we design a virtual path layout for this problem. When the hop-count and the network degree are bounded by constants, our results show that the upper bounds proposed in this paper for the one-to-all problem in arbitrary networks and for the all-to-all problem in two-dimensional mesh networks are asymptotically optimal. Moreover, the general lower bound shows that the algorithm proposed in Gerstel (Ph.D. Thesis, Technion-Haifa, Israel, 1995) for the all-to-all problem in k-separable networks is also asymptotically optimal. The upper bound for mesh networks also shows that the lower bound presented in this paper for the all-to-all problem in planar networks is asymptotically tight.File | Dimensione | Formato | |
---|---|---|---|
VE_2002_11573-942372.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
214.34 kB
Formato
Adobe PDF
|
214.34 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.