Optimization and Systems Theory Seminar
Friday, March 23, 2001, 11.00-12.00, Room 3721, Lindstedtsvägen 25


Di Yuan
Division of Optimization
Department of Mathematics
Linköping University
E-mail: diyua@mai.liu.se

Optimization of internet protocol network design and routing

We study the optimization problem of network design and routing for IP (Internet Protocol) traffic. The design problem concerns capacity dimensioning of communication links in IP networks, where the design cost consists of fixed charges and linear capacity expansion costs. Given a set of traffic demand pairs, and a piecewise linear convex cost associated with unsatisfied demand, another part of the optimization problem is to determine the amount of demand that is to be carried by the network. We further consider IP routing that is usually operated by a routing protocol which does not support free flow distribution. IP routing optimization concerns setting the metric parameters in the routing protocol to determine the flow distribution. We propose a new linear mixed-integer mathematical formulation for the joint design and routing problem, where the IP routing characteristics are explicitly modeled. We present some theoretical results of the model and describe two heuristic solution procedures. The first heuristic uses mixed-integer programming to make sequential decisions with respect to the demand pairs. We further describe and evaluate a simulated annealing meta heuristic for the problem. Computational experiments show that high quality solutions are obtained by both approaches.
Calendar of seminars
Last update: Februari 21, 2001 by Anders Forsgren, anders.forsgren@math.kth.se.