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 parti-tioning e.g. ATM (Asynchronous Transfer Mode), MPLS (Multi Protocol Label Switch-ing), or SDH/SONET (Synchronous Digital Hierarchy/Synchronous Optical Network-ing). 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 pro-tection 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 Dijkstra’s 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. KEY WORDS: Heuristic algorithms; Dijkstra’s algorithm; edge weight calculation; simulated allocation; network configuration