Virtual Private/Overlay Network Design With Traffic Concentration and Shared Protection

In this paper different algorithms are presented and evaluated for designing Virtual Private/Overlay Network (VPNs/VONs) over any network that supports resource partitioning e.g. ATM (Asynchronous Transfer Mode), MPLS (Multi Protocol Label Switching), or SDH/SONET (Synchronous Digital Hierarchy/Synchronous Optical Networking). All algorithms incorporate protection as well. The VPNs/VONs are formed by full mesh demand sets between VPN/VON endpoints. The service demands of VPNs/VONs are characterized by the bandwidth requirements of node-pairs (pipe-model).We investigated four design modes with three pro-active path based shared protection path algorithms and four heuristics to calculate the pairs of paths. The design mode determines the means of traffic concentration. The protection path algorithms use Dijkstras shortest path calculation with different edge weights. The demands are routed one-by-one, therefore the order in which they are processed matters.To eliminate this factor we used three heuristics (simulated allocation, simulated annealing, threshold accepting). We present numerical results obtained by simulation regarding the required total amount of capacity, the number of reserved edges, and the average length of paths.Péter Hegyi received MSc (2004) degree from the Budapest University of Technology and Economics, Hungary, where he is currently a PhD student at the Department of Telecommunications and Media Informatics. His research interests focus on design of intra- and inter-domain multilayer grooming networks and routing with protection. He has been involved in a few related projects (IKTA, ETIK, NOBEL).Markosz Maliosz is a researcher in the High Speed Networks Laboratory, Department of Telecommunication and Media Informatics at the Budapest University of Technology and Economics, where he received his MSc degree in Computer Science (1998). He has participated in projects concerning telecommunication services, network device control, Voice and Video over IP. His current research areas are Virtual Private Networking and traffic engineering in optical networks.Ákos Ladányi is a student at the Department of Telecommunications and Media Informatics at the Budapest University of Technology and Economics. His research interests focus on routing, network resilience, and combinatorial optimization.Tibor Cinkler has received MSc(94) and PhD(99) degrees from the Budapest University of Technology and Economics, Hungary, where he is currently Associate Professor at the Department of Telecommunications and Media Informatics. His research interests focus on routing, design, configuration, dimensioning and resilience of IP,MPLS, ATM, ngSDH and particularly of WR-DWDMbased multilayer networks. He is the author of over 60 refereed scientific publications and of 3 patents.