Virtual network embedding in the cycle

Abstract: We consider a problem motivated by the design of Asynchronous transfer mode (ATM) networks. Given a physical network and an all-to-all traffic, the problem consists in designing a virtual network with a given diameter, which can be embedded in the physical one with a minimum congestion (the congestion is the maximum load of a physical link). Here we solve the problem when the physical network is a ring. We give an almost optimal solution for diameter 2 and bounds for large diameters. [Copyright &y& Elsevier]