Monday April 18 4:00 - 4:50 PM Kelley 1001
Gordon Wilfong Algorithms Research Group Bell Labs Constrained Connectivity The Border Gateway Protocol (BGP) is the de facto interdomain routing protocol used by routers to exchange routing information in the Internet. Internal BGP (iBGP) is a version of BGP that exchanges external reachability information within an Autonomous System (AS). Our work is motivated by the problem of trying to minimize the size of an iBGP overlay in an Autonomous System (AS) subject to a natural notion of correctness derived from the standard "hot-potato" routing rules. In particular, we study a new connectivity-based network design problem that we call Constrained Connectivity. In this problem we are given a graph G=(V,E), and for every pair of vertices u,v in V we are given a subset S(u,v) of V called the safe set of the pair. The goal is to find the smallest subgraph H=(V,F) of G in which every pair of vertices u,v is connected by a path contained in S(u,v). We show that the problem of minimizing an iBGP overlay can be reduced to Constrained Connectivity. The talk wi! ll begin with a general overview of iBGP. An approximation algorithm as well as hardness of approximation results for Constrained Connectivity will then be described. This is joint work with Mike Dinitz (Weizmann Institute). Biography Gordon Wilfong is a Distinguished Member of Technical Staff in the Algorithms Research Group at Bell Labs in Alcatel-Lucent. His broad research interests are in algorithm design and analysis. His current areas of focus are protocol analysis, routing, and the development of game theoretic network models. He received his B.Sc., First Class Honours, in mathematics from Carleton University in 1980 and his M.S. and Ph.D. in computer science from Cornell University in 1983 and 1984 respectively. _______________________________________________ Colloquium mailing list [email protected] https://secure.engr.oregonstate.edu/mailman/listinfo/colloquium
