Colloquia

The Border Gateway Protocol (BGP) and Generalizations

Gordon Wilfong
Bell Labs

Thursday, November 15, 4:00 p.m.
Amos Eaton 214 - 4:00 p.m. to 5:00 p.m.
Refreshments at 3:30 p.m.

Abstract:

The Border Gateway Protocol (BGP) is the interdomain routing protocol used by routers to exchange routing information in the Internet. While intradomain protocols such as RIP can be viewed as distributed algorithms for computing shortest paths, BGP is actually trying to solve a problem we call the Stable Paths Problem (SPP). Most of the talk will be in terms of SPP to allow us to mask the complex details of how BGP operates. We will discuss a number of decision questions concerning BGP convergence and show that they are NP-hard. Then we'll consider modifications to the protocol and configuration constraints that guarantee convergence. A fractional multi-path version of SPP is discussed and we show that this problem always has a stable solution. This leads to open problems such as how to design a protocol (i.e., a distributed algorithm) to achieve such a fractional stable solution. Some optimization questions arising from multi-path routing will also be discussed.

Bio:

Gordon Wilfong is a Distinguished Member of Technical Staff in the Algorithms Research Department of the Mathematical and Algorithmic Sciences Center at Bell Labs in Alcatel-Lucent. His major research interests are in algorithm design and analysis. Dr. Wilfong 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.

Hosted by: Elliot Anshelevich (x6491)
Administrative support: Chris Coonrad (x8412)

For more information:

Gordon Wilfong's Home Page at Bell Labs

Last updated: September 7, 2005