Algorithms for network management
Jon M. Kleinberg, Amit Kumar · 2002
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. Many of these problems are computationally hard and so we look for polynomial time algorithms that give good approximations to the optimal solution. In this thesis, we have initiated such a study for several protocols, ranging from protocols which are used for routing between autonomous systems, the Border Gateway Protocol (BGP), to protocols which are more local in range, Multiprotocol Label Switching (MPLS), and the design and application of Virtual Private Networks (VPN). We also define new notions of fairness in bandwidth allocation to users in a network. In this thesis, we show that problems of direct relevance to network management require techniques that have their roots in the area of design and analysis of algorithms. Moreover, this results in new algorithmic problems, which not only require new techniques for solving them, but also have implications for seemingly unrelated problems. The problem of minimizing bandwidth allocation in VPNs and minimizing traffic in BGP gives rise to facility location problems. Understanding resource trade-offs in MPLS protocol gives rise to interesting issues in graph embeddings.