Abstracts
Friday, November 4, 2005    Saturday, November 5, 2005
8:30 am	Continental Breakfast
9:15 am	Jennifer Rexford, Princeton University A Routing Control Platform for IP Networks Despite the early design goal of minimizing the complexity of network elements, tremendous amounts of state and logic are distributed across routers and management platforms in today's IP networks. The many, loosely-coordinated actors that create and manipulate the distributed state make it extremely difficult for network operators to manage their networks. Instead, we advocate moving the decision logic for running the network from the individual routers into a separate management platform, leaving routers simply to disseminate timely information about the network and forward data packets based on explicit instructions from the management system. In this talk, we argue that this approach would simplify network management and enable new services. Then, we describe a way to migrate to the new network-management architecture while remaining backwards compatible with the installed base of IP routers. Experiments with our prototype implementation show that a Routing Control Platform built from commodity components is fast and reliable enough to select routes for hundreds of routers in a large ISP network. We believe that this new approach will enable much-needed innovation in network management and, ultimately, in the design of routers and switches as well. This talk will draw on the papers listed at http://www.cs.princeton.edu/~jrex/net-wide.html.
9:45 am	Harald Räcke, Toyota Technological Institute at Chicago Oblivious Network Design Consider the following network design problem: given a network $G = (V,E)$, source-sink pairs $\{s_i, t_i\}$ arrive and desire to send a unit of flow between themselves. The cost of the routing is this: ifedge $e$ carries a total of $f_e$ flow (from all the terminal pairs), the cost is given by $\sum_e \load(f_e)$, where $\load$ is some concave cost function; the goal is to minimize the total cost incurred. However, we want the routing to be oblivious: when terminal pair $(s_i, t_i)$ makes its routing decisions, it does not know the current flow on the edges of the network, nor the identity of the other pairs in the system. Moreover, it does not even know the identity of the function $\load$, merely knowing that $\load$ is a concave function of the total flow on the edge. How should it (obliviously) route its one unit of flow? Can we get competitive algorithms for this problem? We develop a framework to model oblivious network design problems (of which the above problem is a special case), and give algorithms with poly-logarithmic competitive ratio for problems in this framework (and hence for this problem). This is joint work with Anupam Gupta and MohammadTaghi Hajiaghayi.
10:15 am	Break
10:40 am	Anant Balakrishnan, University of Texas at Austin Cutting Plane Approach for Service Network Design Many applications in transportation, telecommunications, and supply chain contexts require designing networks that are both cost-effective and responsive. To model these situations, we consider the multi-commodity network design problem of selecting the least cost set of edges containing origin-destination routes that satisfy end-to-end service requirements such as limits on total traversal time or reliability. This service network design problem generalizes previous models such as the budget-constrained shortest path, light t-spanner, and hop-constrained network design problems. We focus on developing effective optimization-based solution methods that rely on strengthening the LP-relaxation of the model formulation. We describe several classes of valid inequalities for the problem, discuss separation routines, and report preliminary computational results using a cutting plane procedure incorporating these inequalities.
11:10 am	Dan Bienstock, Columbia University Title TBD
11:40 am	Lisa Fleischer, IBM T J Watson Research Center Title TBD
12:10 pm	Lunch
1:00 pm	Open Problems
1:30 pm	Adrian Vetta, McGill University Metric Design with Network Costs We study undirected networks with edge costs that satisfy the triangle inequality. We present an O(1)-approximation algorithm for a generalization of the metric-cost subset k-node-connectivity problem. Our approximation guarantee is proved via lower bounds that apply to the simple edge-connectivity version of the problem, where the requirements are for edge-disjoint paths rather than for openly node-disjoint paths. A corollary is that, for metric costs and for each k=1,2,...,n-1, there exists a k-node connected graph whose cost is within a factor of 24 of the cost of any simple k-edge connected graph. Based on our O(1)-approximation algorithm, we present an O(log rmax)-approximation algorithm for the node-connectivity survivable network design problem where rmax denotes the maximum requirement over all pairs of nodes.
2:00 pm	Lisa Zhang, Lucent Technologies Bell Labs Design for Optical Transparency Optical transparency allows signal to travel within an optical network without electronic processing. In this talk we describe new models for designing transparent optical networks. We present recent theoretical advances as well as practical issues arising from design tools that we are developing at Bell Labs. This work is joint with many colleagues from Bell Labs.
2:30 pm	Nick Harvey, MIT Network Coding: A New Direction in Combinatorial Optimization Network coding is a new research area that centers on a fundamental and practical question: How much data can be transmitted through a communication network? Computer scientists have traditionally addressed such questions using network flow theory or other combinatorial models. Network coding enhances these traditional approaches by allowing network nodes to encode and intermingle the data as it flows through the network. The resulting model is quite powerful and leads to many surprising results. There are many intriguing open questions in network coding, suggesting an interesting new direction for work in combinatorial optimization. We survey some of the initial work in this area and present some recent results. First we will discuss network codes for multicasting data and algorithms for constructing such codes. Next we will consider scenarios where each data source transmits to a single sink node (as in multicommodity flows). For some directed graphs, we show that the use of network coding can allow data transmission at a much higher bandwidth. For undirected graphs, it is conjectured that network coding provides no bandwidth improvement at all. This conjecture turns out to have interesting connections to open problems in complexity theory. Using a blend of information theoretic and graph theoretic arguments, we give the first proof of this conjecture for a non-trivial class of graphs. This is joint work with Micah Adler, Kamal Jain, David Karger, Robert Kleinberg, April Rasala Lehman, and Kazuo Murota.
3:00 pm	Break
3:30 pm	Iraj Saniee, Bell Labs Research Load Balancing in CDMA Networks: A Distributed Dual Optimization Approach We consider a linear programming (LP) model for balancing loads in a system of base stations in power-controlled CDMA networks. This LP characterizes the (theoretical) minimum achievable base station load for a given configuration of mobiles at a given time interval. We next consider the dual formulation of this optimization problem, which turns out to incorporates the well-known fixed-point problem encountered in uplink power control in CDMA networks (and whose iterative solution is embedded in CDMA handsets). While the solution of the LP offers valuable insight to the qualitative properties of the optimal power allocation, the dual model furnishes the critical notion that optimal power allocation need not only be based on signal strengths but also on the "shadow price" imputed from each base station. The dual model also provides the necessary mechanism for an iterative ascent scheme for solving the load balancing problem in a (mostly) distributed fashion with low communication overhead leveraging the fixed-point scheme as a sub-step. Extensive numerical experiments demonstrate substantial scope for capacity gains from balancing base station loads even in conservative scenarios. This is joint work with Sem Borst, Georg Hampel, and Phil Whiting.
4:00 pm	Guido Schäfer, Technische Universität Berlin A Tight 4.66-Approximation for Multicommodity Rent-or-Buy In the multicommodity rent-or-buy network design problem (MRoB) we are given a network together with k terminal pairs (s_i, t_i). The goal is to install capacities on the edges of the network so that a prescribed amount of flow f_i can be routed between all terminal pairs s_i and t_i simultaneously. We can either rent capacity on an edge at some cost per unit flow or buy infinite capacity on an edge at some larger fixed cost. The overall objective is to install capacities at a minimum total cost. Gupta et al. (FOCS '03) gave a randomized scheme for the MRoB problem that has been used subsequently to improve the approximation ratio for this problem. The currently best known 6.82-approximation algorithm is due to Becchetti et al. (SODA '05). We present a surprisingly simple primal-dual 4.66-approximation algorithm and show that this result is tight; that is, no better approximation ratio can be achieved using the above mentioned randomized scheme in combination with the currently best known approximation algorithms. This is joint work with Lisa Fleischer, Jochen Könemann, and Stefano Leonardi.
4:30 pm - 5:00 pm	Chaitanya Swamy, Caltech Approximation Algorithms for Stochastic Optimization Stochastic optimization provides a means to handle uncertainty where (part of) the input is specified in terms of a probability distribution over possible realizations of the data, instead of deterministic data given in advance. We consider the widely-used paradigm of stochastic recourse models where the uncertainty evolves through a series of stages and one can take decisions in each stage in response to the new information learned. Planning under uncertainty introduces several algorithmic challenges with even simple polynomial-time solvable deterministic problems becoming computationally intractable in the stochastic setting. I will give an overview of some recent work on the design of approximation algorithms for these problems, most of which has focused on 2-stage recourse problems: one makes some initial decisions given only distributional information about the data, then the actual data is realized and further recourse actions may be taken. If time permits, I will briefly talk about very recent work on multi-stage problems where the random data is sequentially instantiated in multiple stages and one can take recourse actions in each stage. Some of the results I will talk about were obtained in joint work with David Shmoys.
Saturday, November 5, 2005   Friday, November 4, 2005
8:30 am	Continental Breakfast
9:30 am	Mohammad Mahdian, Microsoft Research Title TBD
10:00 am	Joseph Cheriyan, University of Waterloo On packing Steiner trees and related problems A set of nodes of an undirected graph G is called k-edge connected if there exist k edge-disjoint paths between every pair of nodes in the set. A conjecture of Kriesell states that if T is a 2k-edge connected node set, then there exist k edge-disjoint Steiner trees with terminal set T. The talk will survey some recent progress on this conjecture and related topics, using methods from the design and analysis of approximation algorithms. This is joint work with Mohammad Salavatipour.
10:30 am	Break
10:50 am	Thierry Klein, Lucent Technologies Bell Labs Dynamic optimizations for next-generation wireless networks We discuss the role of network performance optimization, which is required when deploying real-world wireless networks to adjust to complex channel propagation effects, network layout irregularities and inhomogeneous traffic distributions. Traditional and automated optimization procedures are presented, along with a cellular optimization tool to enhance the coverage and capacity of CDMA networks. The emerging trends in wireless data networks naturally lead to dynamic network optimizations. To highlight these trends, the specific problem of autonomous base station deployment is presented in greater detail. The objective of the optimization is to adjust the base station locations and the transmit powers to dynamic user distributions and changing network topologies.
11:20 am	Sanjeev Khanna, University of Pennsylvania Edge Disjoint Paths: On the Integrality Gap of the Multicommodity Flow Relaxation Edge-disjoint paths (EDP) is a fundamental problem in combinatorial optimization. We are given a network and a collection of source-destination pairs in the network. The goal is to route as many pairs as possible such that the paths assigned to the routed pairs do not share any network links. A well-studied approach for designing approximation algorithms for EDP is to use the multicommodity flow relaxation. It is known that the integrality gap of this relaxation is $\Omega(\sqrt{n})$ even in undirected planar graphs. It is also known that the gap is no worse than $O(n^{2/3})$ even in general graphs. In the first part of this talk, we will show that the integrality gap in general undirected graphs is $O(\sqrt{n})$, matching the known lower bound. In the second part, we will present some results on how the integrality gap changes when we allow congestion. This is joint work with Chandra Chekuri (Bell Labs), Julia Chuzhoy (MIT and UPenn), and Bruce Shepherd (Bell Labs).
11:50 am	Christian Scheideler, Johns Hopkins University Towards a paradigm for robust distributed algorithms and data structures There is a wealth of literature on distributed algorithms and data structures. Standard models used in the research community are synchronous or asynchronous shared memory or network models. The shared memory model is basically a generalization of the von Neumann model from one processing unit to multiple processing units or processes acting on a single, linear addressable memory. In the network model, there is no shared memory. Every processing unit has its own, private memory, and the processing units are interconnected by a network of (usually) bidirectional communication links that allow the processing units to exchange messages. The set of processing units is usually considered to be fixed though processing units may fail and recover according to some stochastic or adversarial model. With the rise of very large distributed systems such as peer-to-peer systems, these models are not appropriate any more. For example, the set of processing units can be highly dynamic and there may not be any mutual trust relationships between the units. This creates fundamental problems, such as keeping the (honest) units in a single connected component, that the previous models cannot address in their basic form. We show how to extend the network model so that we have a model that is powerful enough to design algorithms and data structures that are provably robust even against massive adversarial attacks. This model even allows to design strategies capable of addressing modern threats such as denial-of-service attacks that appear to lie outside of the algorithms realm. Our hope is that this model will open up many interesting research problems in the areas of network theory and distributed algorithms and data structures in the future.
12:20 pm	Lunch
1:10 pm	Kamal Jain, Microsoft Research Title TBD
1:40 pm	Tim Roughgarden, Stanford University Title TBD
2:10 pm - 2:40 pm	MohammadTaghi Hajiaghayi, MIT Graph Algorithms for Wireless Networks In this talk, we present real-world applications with deep theoretical underpinnings and consequences and show how wireless multi-hop Networks, algorithmic graph theory, and computational complexity have a nice intersection in this area. We present logarithmic approximability and almost-logarithmic inapproximability for a maximization problem called "unique coverage": given a collection of sets, find a subcollection that maximizes the number of elements covered exactly once. The unique coverage problem defined above is a natural maximization version of set cover which was brought to our attention from its applications in wireless networks. In one (simplified) application, we have a certain budget to build/place some transmitters at a subset of a specified set of possible locations. Our goal is to maximize the clients that are "covered" by (i.e., are within the range of) exactly one transmitter; these are the clients that receive signal without interference. Specifically, we prove O(1/log^{sigma(epsilon)} n) inapproximability assuming that NP is not subseteq BPTIME(2^{n^epsilon}) for some epsilon > 0. We also prove O(1/log^{1/3-\epsilon} n) inapproximability, for any epsilon > 0, assuming that refuting random instances of 3SAT is hard on average. We establish matching upper bounds up to exponents, even for a more general (budgeted) setting, giving an Omega(1/log n)-approximation algorithm as well as an Omega(1/log B)-approximation algorithm when every set has at most B elements. We also show that our inapproximability results extend to envy-free pricing, an important problem in computational economics. We believe that unique coverage has the potential to be a central inapproximable maximization problem in the same way that set cover is for minimization problems. We mainly focus on the above practical problem in the talk, however if there is any remaining time we also consider the concept of power optimization in fault-tolerant topology control algorithms for wireless multi-hop sensor networks and also define a nice set of theoretical problems on this subject.

Back to Workshop on Flexible Network Design main page

 

This material is based upon work supported by National Science Foundation under Grant No. 0122581.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the
National Science Foundation