Lehigh University - CSE: Wilfong

Dr. Gordon Wilfong

"An Analysis of Route Oscillations in BGP"

Tuesday, October 5, 4:30 PM

Packard Lab, Room 466

Abstract: The Border Gateway Protocol (BGP) is the de facto interdomain routing protocol used in the Internet. BGP has two distinct modes of operation. External BGP (EBGP) exchanges reachability information between Autonomous Systems (ASes), whereas Internal BGP (IBGP) exchanges external reachability information within an AS. In either mode, there are situations in which BPG fails to converge. We show that many decision questions concerning BGP convergence are NP-hard. We then show that there are modifications to the protocol that guarantee convergence. Rather than changing the protocol, another approach is to find configuration constraints that guarantee that a network satisfying these constraints will have the property that BGP is provably guaranteed to converge. We discuss a number of such constraints.

This covers joint work with A. Basu (Morgan-Stanley), T. Griffin (Intel), L. Ong (Oxford), A. Rasala (MIT) and B. Shepherd (Bell Labs).

Bio: Gordon Wilfong received a B.Sc. in mathematics from Carleton University in 1980 and a Ph.D. in computer science from Cornell University in 1984. He joined Bell Laboratories in 1984 where he has been involved in the design of algorithms in areas such as scheduling, robotics, computational geometry, handwriting recognition and WDM routing. His most recent work has included generalized edge coloring problems, analyzing interdomain routing protocols and modeling routing in the Internet using a game theoretic approach.

		Dr. Gordon Wilfong "An Analysis of Route Oscillations in BGP" Tuesday, October 5, 4:30 PM Packard Lab, Room 466 Abstract: The Border Gateway Protocol (BGP) is the de facto interdomain routing protocol used in the Internet. BGP has two distinct modes of operation. External BGP (EBGP) exchanges reachability information between Autonomous Systems (ASes), whereas Internal BGP (IBGP) exchanges external reachability information within an AS. In either mode, there are situations in which BPG fails to converge. We show that many decision questions concerning BGP convergence are NP-hard. We then show that there are modifications to the protocol that guarantee convergence. Rather than changing the protocol, another approach is to find configuration constraints that guarantee that a network satisfying these constraints will have the property that BGP is provably guaranteed to converge. We discuss a number of such constraints. This covers joint work with A. Basu (Morgan-Stanley), T. Griffin (Intel), L. Ong (Oxford), A. Rasala (MIT) and B. Shepherd (Bell Labs). Bio: Gordon Wilfong received a B.Sc. in mathematics from Carleton University in 1980 and a Ph.D. in computer science from Cornell University in 1984. He joined Bell Laboratories in 1984 where he has been involved in the design of algorithms in areas such as scheduling, robotics, computational geometry, handwriting recognition and WDM routing. His most recent work has included generalized edge coloring problems, analyzing interdomain routing protocols and modeling routing in the Internet using a game theoretic approach.