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.