Mesh Topology Design in Overlay Virtual Private Networks

Ezhan Karasan (ezhanee.bilkent.edu.tr)
Oya Ekin-Karasan (karasanbilkent.edu.tr)
Nail Akar (akaree.bilkent.edu.tr)
Mustafa C. Pinar (mustafapbilkent.edu.tr)

Abstract: We study the mesh topology design problem in overlay virtual private networks. Given a set of customer nodes and associated traffic matrix, tunnels that are connecting node pairs through a public service provider network subject to degree constraints are determined so as to minimize total multihopped traffic. Valid inequalities strengthening the LP relaxation and a tabu search heuristic are proposed and validated on a set of large test cases, leading to small duality gaps.

Keywords: mesh topology design, virtual private networks, integer programming, network design

Category 1: Applications -- OR and Management Sciences (Telecommunications )

Category 2: Integer Programming (0-1 Programming )

Category 3: Network Optimization

Citation: Electronics Letters, Vol. 38, No. 16, August 2002, pp. 939-941.

Download:

Entry Submitted: 04/24/2002
Entry Accepted: 04/24/2002
Entry Last Modified: 09/17/2002

Modify/Update this entry