picture

Papers

 
Hardness of Robust Network Design with C. Chekuri, G. Oriolo, M.G. Scutella, INOC 2005. Submitted to Networks.
We are given an uncapacitated undirected graph $G$ and a collection $P$ of matrices for pairwise traffic demands between nodes of $G$. What is the cheapest assignment of edge capacity needed so that any matrix $D$ in $P$ can be routed using this capacity? In the "oblivious routing" setting, for each pair $i,j$ there is a pre-specified unit flow ("template") and one may only scale this flow up or down according to the value of $D_{ij}$. In this version Applegate and Cohen showed that the optimal capacity is computable in polytime. If we may choose our flows dynamically for each different demand matrix, then obviously we may need less capacity. We show, by a reduction from graph expansion, that this problem is hard, even for a single-source hose problem (and even to get within a factor 2).
Multilateral Transport Games with G. Wilfong, INOC 2005. .
Content Distribution for Seamless Transmission, with E.G. Coffman, A. Constantinides, D. Rubenstein, D. Stavrou, Mathematical performance Modeling and Analysis, MAMA 2004 .
Lighting Fibers in a Dark Network, with Adrian Vetta, Journal on Selected Areas in Communication , Vol. 22, Number 9, 1583-1588, 2004.
Cluster and Server Selection Using Passive Monitoring with M. Andrews, A. Srinivasan, P. Winkler, F. Zane, Infocom 2002
A Fast and Scaleable Approximation Algorithm for Computing Shared Recovery Flows Minimizing Long-Term Expected Cost with L. Fleischer, A. Meyersen, I. Saniee, A. Srinivasan, CORC Report 2003-10
Route Oscillations in I-BGP with A. Basu, L. Ong, A. Rasala, G. Wilfong, SIGCOMM 2002; an article
The Stable Paths Problem and Interdomain Routing with T.G. Griffin, G.T. Wilfong. IEEE/ACM Transactions on Networking, vol. 10 (2), 2002, 232-243. Policy Disputes in Path-Vector Protocols, (Earlier version) International Conference on Network Protocols, ICNP '99.
Some strategies for reserving resilient capacity, with G. Brightwell, G. Oriolo. SIAM J. Discrete Math., , Vol. 14, No. 4, 524-539, 2001. A fuller, earlier version describes a number of alternative strategies for different types of restoration architectures.
Many coarse network designs are performed as follows. For each source-destination pair of nodes $s,t$ with say $D$ traffic demand between them, reserve $D$ units of capacity on each link of a shortest $s-t$ path in the network (topology). This reserved bandwidth is completely vulnerable, however, to any single link failure. This paper generalizes the shortest path problem to natural resilient path analogues. Several resilient (up to $k$ failures) versions are discussed including the case where we must route traffic on a collection of disjoint paths. Here a simple algorithm is described for the fractional version, and a $\frac{1}{14}$-approximation algorithm is described for the integer version. It is also shown that it is NP-hard to obtain a polytime $(\frac{1}{14}-\epsilon$)-approximation algorithm, for any $\epsilon > 0$. The longer version contains more discussion of alternative network resilience and restoration strategies.
Reserving Resilient Capacity for a Single Commodity with Upper Bound Constraints with G. Brightwell, G. Oriolo. Networks, vol 41. no.2 (2003), pp 87-96.
Routing and configuration of static path optical transport networks , with E.Lowe, N. Walker. IEE Electronic Letters, vol. 32, 1996, 1913-1914.