Routing Protocol

Shiva Kintali Prasad (H. Venkateswaran) - The Border Gateway Protocol (BGP) is currently the only interdomain routing protocol deployed in the Internet. BGP can be viewed as a distributed algorithm for solving a fundamental problem known as Stable Paths Problem (SPP).

Unlike a shortest path tree, solution to an SPP does not represent a global optimum, but rather an equilibrium point in which each node is assigned its locally optimal path to the speci?ed destination. Currently there is no necessary and sufficient condition for the convergence of path vector protocols like BGP. In this project we would like to characterize this convergence. Also we would like to address the complexity of deciding safety and robustness for an SPP specification. Recently, Haxell and Wilfong? defined a fractional version of SPP and show that all instances of fractional SPP (FSPP) have solutions. We would like to develop a distributed algorithm that would solve FSPP.