HOME    »    PROGRAMS/ACTIVITIES    »    Annual Thematic Program
April 7-11, 2003

2002-2003 Program: Optimization

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
  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