Two-Hop Virtual Path Layout in Tori

We consider the problem of D-hop virtual path layout in ATM (Asynchronous Transfer Mode) networks. Given a physical network and an all-to-all traffic pattern, the problem consists of designing a virtual network with a given diameter D, which can be embedded in the physical one with a minimum congestion (the congestion is the maximum load of a physical link). Here we propose a method to solve this problem when the diameter is 2. We use this method to give an asymptotically optimal solution for the 2-hop virtual path layout problem for all-to-all traffic when the physical network is a mesh, a torus or a chordal ring.