2002-2003 Program: Optimization
Talk
Abstracts:
April
7-11, 2003
Material
from Talks
Andreas
Bley
(Konrad-Zuse-Zentrum, für Informationstechnik Berlin) bley@zib.de
http://www.zib.de/bley
An
Integer Programming Approach to IP Network Optimization
Slides: pdf
The
standard routing protocol used in IP networks currently is OSPF.
Given some administrative routing weights on the links of the
network, data packages are sent along a shortest path with respect
to these weights from their source to their destination. In
this article, the case of non-bifurcated routing is considered,
i.e., % traffic splitting enabling extension to the OSPF protocol
are not allowed and all data packages between two nodes are
send along the same path.
We
study the network design and the traffic engineering problem
for IP networks, both arising naturally in planning and operating
such networks. Given the node locations, the forecasted traffic
demands, all possible links, the possible node and link hardware
configurations, and various other technical and administrational
constraints, the goal in the IP network design problem is to
(simultaneously) decide the network's topology, its hardware
configuration, and the routing weights such that the overall
network cost is minimized. In the traffic engineering problem
for IP networks, the goal is to adjust the networks routing
weights such that, for a given network and some forecasted traffic
demands, the maximum congestion of the links is minimized. In
both cases we not only consider the networks normal operating
state but also scenarios where single network components may
fail.
Mixed-integer
linear programming models and solution methods are presented
for both problems. Computational results obtained with these
methods for German research network and other real-world network
planning problems are reported.
Keywords:
Network design, Traffic engineering, Shortest path routing,
IP routing, Mixed-integer programming
Mathematical
Subject Classification (2000): 90B18,
90C11, 90C27, 90C90
Andreas
Eisenblaetter (ZIB, Germany) eisenblaetter@zib.de
UMTS
Radio Network Planning Slides:
html
pdf
ps
The
new Universal Mobile Telecommunications System (UMTS) is a 3rd
generation cellular system for mobile telecommunication. UMTS
supports all services of the worldwide predominant, 2nd generation
GSM and GPRS networks. It is more powerful, more flexible, and
more radio spectrum efficient than its predecessors. Unlike
with GSM and GPRS, radio transmissions are not separated in
time or frequency. Instead, they are superimposed in time and
frequency, separable only by means of their encoding (an example
of code devision multiple access or CDMA, in short). For this
to work, a minimum ratio between radio transmission signal strength
as perceived by the receiver and the interference must be achieved.
In consequence, UMTS radio cell capacity and coverage are strongly
inversely coupled through system self-interference.
In
this talk, we present the governing interference constraints
for UMTS radio network planning and introduce a mixed integer
programming model for UMTS radio network design. The scope of
this model is to select base station locations (from a list)
and to configure base stations, including antenna types, heights,
azimuths, and tilts as well as the cell's dominance areas. We
discuss how this model is used within an integrated planning
loop to minimize network costs while satisfying coverage and
capacity constraints, which are given in the form of statistical
distributions. Finally, we show how we exploit standard mixed
integer programming tools for (heuristically) solving realistic
planning problems.
This
joint work with Alexander Martin
(TU Darmstadt, Germany) and Thorsten Koch
(ZIB, Germany) is carried out within the EU-funded project MOMENTUM
(http://momentum.zib.de).
Martin
Farach-Colton
(Department of Computer Science, Rutgers University) martin@farach-colton.com
Adventures
at Google
Google
has changed the way search engines are built. I'll discuss some
of the changes, as well as some experiences from my two years
in the Google Research Department and the nature of research
at a startup.
Lisa
K. Fleischer (Graduate School of Industrial Administration,
Carnegie Mellon University, Operations Research) lkf@andrew.cmu.edu
Multicommodity
Flows With Holding Costs Paper:
pdf
ps
We
consider a broad class of separated continuous linear programs
(SCLP) that arise as fluid relaxations of multiclass queueing
networks, and are used to find approximate solutions to complex
job shop scheduling problems. One example of a problem we consider
is the multicommodity flow problem with holding costs: Given
a capacitated network with node queues, linear flow costs and
linear, per-unit-time holding costs, drain the queues to minimize
total holding costs. The complexity of this problem is not well
understood, but there is evidence to suggest that optimal solutions
may have exponential size. Existing algorithms for SCLP do not
have polynomial time or space guarantees.
For given constants a > 0 and b > 0, we present an algorithm
that finds a solution with value at most (1+a)OPT + b, where
OPT is the value of the optimal solution. The complexity of
our algorithm and the size of the solution we produce are polynomial
in the size of the input network, 1/a, and log(1/b). We introduce
a natural discretization of polynomial size and prove that this
discretization produces a solution with low cost. This is the
first polynomial time algorithm with a provable approximation
guarantee for solving fluid relaxations.
This
is joint work with Jay Sethuraman
of Columbia University.
Luis
Goddyn
(Department of Mathematics and Statistics, Simon Fraser University)
goddyn@math.lsu.edu
Some
Network-Flow-Like Optimization Problems Slides:
html
We
consider a load balancing problem for a network in which data
can flow in one of two directions on each edge, where the direction
of flow must be specified at the outset of its use. One desires
that the flow on each edge be as "close" to its capacity as
possible. If edge-capacities are constant, and flow is conserved
at each node, then we are in the realm of the graph invariant
"circular flow number."
This
notion is dual in the matroidal sense to "circular chromatic
number," an invariant which arises in certain scheduling problems
such as in traffic light sequencing. Variations of these problems
arise from variable edge capacities and traffic streams. The
two problems are closely because of matroidal duality.
In
each case, to find an good solution, a selection of edge directions
is followed by the solving of a certain linear program. It is
crucial that such LPs be quickly soluble to get a practical
circular flow (or chromatic) number estimator. We also present
several bounds and relationships for certain classes of graphs,
surface embedded graphs, and more general structures called
oriented matroids. Some of these bounds are obtained through
probabilistic methods.
Michel
X. Goemans
(Department of Mathematics, Massachusetts Institute of Technology)
goemans@math.mit.edu
http://www-math.mit.edu/~goemans
Load-Balancing
in Content Delivery Networks
Load
balancing is a crucial component of content delivery networks.
It is a highly complex task because of a number of reasons,
including the unpredictability and sudden surges in traffic,
random events and failures in the internet, scalability issues,
the highly distributed nature and constant evolution of these
networks, and the heterogeneity of the services provided and
their resource requirements. This talk discusses the challenges
of building an appropriate model for load balancing and the
design of efficient, reliable and scalable algorithms. The speaker
will draw upon his experience at Akamai Technologies.
Oktay
Gunluk (Math Sciences, IBM Research) oktay@watson.ibm.com
Network Design with Small Number
of Flow Paths
We describe a network design and
routing problem where each commodity has to be routed on a small
number of node-disjoint paths from its source to its sink. We
describe an integer programming formulation and several relaxations.
We also introduce a simple mixed-integer set related to this
formulation and study its polyhedral structure.
We present (preliminary) computational
results.
Joint work with F.
Barahona, IBM Research.
Anupam
Gupta (Department of Computer Science, Carnegie Mellon
University) anupamg@cs.cmu.edu
Designing
Networks Without Knowing the Traffic Matrix Slides:
pdf
In
a classical network design problem, we specify a matrix of pairwise
demands (and possibly some added restictions on the network
structure) and ask for the "best" network. However, giving one
demand matrix is often very restrictive (volatility in traffic
cannot be handled, etc); furthermore, estimating pairwise traffic
matrices is a bit of a bother at the best of times.
A
natural alternative is to use the following model: each user
v specifies an upper bound b(v) on the traffic that it takes
part in, and the objective is to find the cheapest network that
handles all traffic matrices that respect the upper bounds at
the individual nodes.
We
will talk about known exact and approximation algorithms, and
some (of the many) open directions for research.
Howard
Karloff (AT&T
Labs-Research) howard@research.att.com
On the Fractal Behavior of TCP
Slides: html
I will speak on a simple dynamical
system which models the Internet protocol TCP. The simple model
embodies TCP's "additive increase, multiplicative decrease"
rule. Two sources s1 and s2 send packets at varying rates r1
and r2 to a recipient; whenever packets are lost, the sender
halves its sending rate.
We prove that for infinitely many
choices of the parameters, the set of feasible rate pairs that
can occur in the limit is a fractal. (This does not mean, however,
that the traffic is statistically self-similar.)
No previous knowledge of TCP or
of fractals will be assumed.
This is joint work with Anna
Gilbert of AT&T Labs-Research.
Carsten
Lund
(AT&T Labs - Research) lund@research.att.com
Network
Measurements and Sampling Slides:
html
pdf
ps
ppt
One
important aspect of Network Management is Network Measurements.
In order to design and manage a network we need to know the
traffic on the network. For example, to design an efficient
network it is crucial to know the traffic matrix, e.g., the
edge router to edge router traffic load. A good traffic matrix
requires detailed measurements of traffic flows. The good news
is that most network elements are today capable of creating
traffic flow statistics, the bad new is that we need to deal
with a large amount of measurement traffic. This talk to describe
one sampling approach to this problem, what reduces the resources
needed in the measurement collection infrastructure, but still
obtain accurate traffic matrix estimates.
Bruce
Maggs
(Computer Science Department, Carnegie Mellon University) bmm@cs.cmu.edu
Designing
Overlay Multicast Networks for Commercial Streaming
Slides: html
pdf
ps
ppt
This
talk begins with an overview of the architecture that Akamai
uses to deliver video and audio streams to a world-wide audience.
It then tackles the problem of how to measure stream quality,
and once metrics are defined, it describes various mechanisms
that are used to improve quality. The talk then shifts to a
combinatorial problem that arises in optimizing the overlay
network that Akamai uses for delivering live streams. We describe
a polynomial time approximation algorithm for "designing" such
a network. The algorithm finds a solution that satisfies capacity
and reliability constraints to within a constant factor of optimal,
and cost to within a logarithmic factor.
Joint
work with Konstantin Andreev,
Adam
Meyerson,
and Ramesh Sitaraman.
S.
Muthu Muthukrishnan (AT&T Labs Research) muthu@research.att.com
Data
Stream Algorithms for Network Traffic Analysis
There
is an emerging theory of algorithms that work on data streams,
that is, data that arrives as a series of observations at high
speed. Such algorithms exist for finding heavy hitters and outliers,
estimating the number of rare or distinct items, summarizing
traffic trends, and clustering. I will review these algorithms
and explore their application for IP network traffic analysis.
Andrew
Odlyzko
(Digital Technology Center, University of Minnesota) odlyzko@dtc.umn.edu
http://www.dtc.umn.edu/~odlyzko
Different
Types of Efficiency in Data Networks Slides:
pdf
What should be optimized in network design and management? High
rates of growth in traffic volumes, lumpy nature of network
capacity, distribution of costs, and the utility users derived
from data networks (as shown by their usage patterns) argue
that traditional goals of high utilization and guaranteed quality
of service should not be the dominating ones. Instead, minimizing
the complexity of the network and providing redundancy are most
desirable.
James
B. Orlin
(Operations Research Center, MIT) jorlin@mit.edu http://web.mit.edu/jorlin/www/
Very
Large Scale Neighborhood Search Slides:
html
pdf
ps
ppt
Many
optimization problems of practical interest are computationally
intractable. Therefore, a practical approach for solving such
problems is to employ heuristic (approximation) algorithms that
can find nearly optimal solutions within a reasonable amount
of computation time. An improvement algorithm is a heuristic
algorithm that generally starts with a feasible solution and
iteratively tries to obtain a better solution. Neighborhood
search algorithms (alternatively called local search algorithms)
are a wide class of improvement algorithms where at each iteration
an improving solution is found by searching the "neighborhood"
of the current solution. This talk focuses on neighborhood search
algorithms where the size of the neighborhood is "very large"
with respect to the size of the input data and in which the
neighborhood is searched in an efficient manner. We survey several
broad classes of very large-scale neighborhood search (VLSN)
algorithms and give applications to partitioning and to fleet
assignment problems in airline scheduling.
Aravind
Srinivasan
(Computer Science Department, University of Maryland, College
Park) srin@cs.umd.edu
Fast
Distributed Algorithms for (Weakly) Connected Dominating Sets
and Linear-Size Skeletons Slides:
html
Motivated
by routing issues in ad hoc networks, we present polylogarithmic-time
distributed algorithms for two problems. Given a network, we
first show how to compute connected and weakly connected dominating
sets whose size is at most O(log 
)
times optimal,
being the maximum degree of the input network. This is best-possible
under standard complexity-theoretic assumptions, and if the
processors are limited to polynomial-time computation. We also
show how to construct dominating sets which satisfy the above
properties, as well as the "low stretch" property
that any two adjacent nodes in the network have their dominators
at a distance of at most O(log n) in the network. Our time bounds
are shown to be near-optimal.
This
is joint work with Devdatt Dubhashi,
Alessandro Mei, Alessandro
Panconesi and Jaikumar Radhakrishnan.
Éva
Tardos
(Department of Computer Science, Cornell University) eva@cs.cornell.edu
Network
Design Games Slides:
html
pdf
ps
ppt
In
this talk we will consider several network design games with
selfish agents. Maybe the simplest network design games are
facility location and spanning tree-games when goal of each
player is to connect a terminal to a facility or to a common
source in the graph. Facilities, and potential edges in the
network have costs and each agent's goal is to pay as little
as possible, while having his terminals connected. We will consider
these and related games mostly from the perspective of cost
sharing. The result on cost-sharing presented are joint work
with Martin Pal.
Mikkel
Thorup
(AT&T Labs-Research) mthorup@research.att.com
Internet
Traffic Engineering by Optimizing OSPF Weights Slides:
pdf
ps
Shortest
Path First protocols such as OSPF and IS-IS are the most commonly
used intra-domain internet routing protocol. Traffic flow is
routed along shortest paths, splitting flow at nodes where several
outgoing links are on shortest paths to the destination. The
weights of the links, and thereby the shortest path routes,
can be changed by the network operator. The weights could be
set proportional to their physical distances, but often the
main goal is to avoid congestion, i.e. overloading of links,
and the standard heuristic recommended by Cisco is to make the
weight of a link inversely proportional to its capacity.
Our
starting point was a proposed AT&T WorldNet backbone with demands
projected from previous measurements. The desire was to optimize
the weight setting based on the projected demands. We showed
that optimizing the weight settings for a given set of demands
is NP-hard, so we resorted to a local search heuristic. Surprisingly
it turned out that for the proposed AT&T WorldNet backbone,
we found weight settings that performed within a few percent
from that of the optimal general routing where the flow for
each demand is optimally distributed over all paths between
source and destination. This contrasts the common belief that
OSPF/IS-IS routing leads to congestion and it shows that for
the network and demand matrix studied we cannot get a substantially
better load balancing by switching to the proposed more flexible
Multi-protocol Label Switching (MPLS) technologies.
Our
techniques were also tested on synthetic internetworks, based
on a model of Zegura et al. (INFOCOM'96), for which we did not
always get quite as close to the optimal general routing. However,
we compared with standard heuristics, such as weights inversely
proportional to the capacity or proportional to the physical
distances, and found that, for the same network and capacities,
we could support a 50%-110% increase in the demands.
Our
assumed demand matrix can also be seen as modeling service level
agreements (SLAs) with customers, with demands representing
guarantees of throughput for virtual leased lines.
We
will also discuss how our techniques can be adapted for link-failures
and changes in the demand matrix.
Part
of the above work was presented at the IEEE INFOCOM 2000, and
other parts were published IEEE J. Selected Areas in Communications
(Special Issue on Fundamentals of Network Management) 40(10):118--124,
October 2002. Also, there are some recent developments to be
presented at SIGMETRICS 2003.
William
Yurcik (NCSA/University of Illinois at Urbana-Champaign)
byurcik@ncsa.uiuc.edu
Visual
Network Monitoring for Situational Awareness with Netflows
(poster session)
Netflow
data, once only available from routers and now available from
independent platforms, provides fundamental network management
information especially for the identification of known traffic
signatures and unknown but anomalous network traffic when compared
to a statistical profile. At NCSA, we have developed a flexible
tool that visualizes an entire IP address space on one screen
including drill-down capabilities for subnets and individual
machines.
Material
from Talks
2002-2003
Program: Optimization
