Algorithms for Network Management

Amit Kumar, Cornell University

Communication networks have witnessed phenomenal growth in recent years. The issues raised by the introduction of new technology and protocols have led to problems which are both theoretically fundamental and relevant to current applications. In this talk, I shall focus on two key themes, namely, virtual private networks (VPN) and the Border Gateway Protocol (BGP).

VPNs provide customers with predictable and secure network connections over a shared network. Provisioning a VPN over a set of terminals gives rise to the following general network design problem: we have bounds on the cumulative amount of traffic each terminal can send and receive; we must reserve enough bandwidth on the network so that any pair-wise traffic matrix consistent with these bounds can be routed.

BGP is the standard protocol for exchanging information between border routers of autonomous systems(AS) in the Internet. Within an AS, border routers exchange externally learned route information. Naive solutions for this peering between the border routers simply cannot scale to the sizes of modern AS networks. Carefully designed route reflector configurations can drastically reduce the communication costs needed by such peering sessions. We give the first algorithmic approach towards designing such configurations.

We show connections of these problems with facility location problems and give efficient algorithms with provable performance guarantees.