^ Top

NANOG Meeting Presentation Abstract

BGP Convergence in much less than a second
Meeting: NANOG40
Date / Time: 2007-06-06 10:00am - 10:20am
Room: Grand Ballroom
Presenters: Speakers:

Clarence Filsfils, Cisco Systems

Clarence Filsfils is a Cisco Distinguished Engineer. He has been playing a key role in engineering, marketing and deploying the Quality of Service and Fast Routing Convergence technology at Cisco Systems.
Abstract: It is common to characterize any BGP-related routing convergence as hopelessly slow due to the linear relationship between the number of impacted prefixes (in the 500k range in early 2007 counting internet and vpn routes) and the number of convergence operation (bestpath, RIB and FIB update, transmission or reception of withdraw/update).

The objective of this paper is to demonstrate that this belief is wrong for any failures occurring within the network of a service provider or on peering links with redundantly-connected peers. This covers the vast majority (if not all) of business models involving BGP convergence requirements.

Thanks to BGP Prefix Independent Convergence (BGP PIC), an alternative path to the existing BGP next-hop is enabled at IGP convergence time (modify) in the core scenario, while in the edge scenario, the deletion of the IGP path to a BGP next-hop triggers an immediate and prefix-independent rerouting of the dependent BGP destinations via an alternate BGP next-hop.

Aside the obvious convergence gains, BGP PIC and its underlying hierarchical FIB organization bring significant scaling and robustness gains to router architecture.

The first section defines the problem and introduces concepts such as RIB, FIB, recursion, dependency, flattened and hierarchical FIB organization. The second section explains why modern high-end router design invests in more complex and expensive packet lookup engine to support hierarchical FIB databases. This allows for significant gains in scaling, robustness and routing convergence (BGP PIC Core). The next section generalizes the hierarchical FIB structure and introduces the concepts of shared BGP path-lists and loadbalancing FIB entries. BGP PIC edge is then defined both for the multipath and unipath BGP policies. The next section describes the BGP control Plane reaction to the core and edge failures, how it is automatically serialized with IGP convergence and how the later BGP control-plane induced FIB modifications reconciliate with the BGP-PIC-modified FIB in a lossless manner. We then review the vast applicability for BGP PIC behavior and report detailed lab measurement based on a commercially-available product. We finish with a conclusion.
Files: youtubeBGP Convergence in much less than a second
pdfClarence Filsfils Presentation(PDF)
Sponsors: None.

Back to NANOG40 agenda.

NANOG40 Abstracts

  • Panel: Higher Speed Ethernet - 40G vs 100G
    Moderators:
    Richard A. Steenbergen, nLayer Communications; Panelists:
    Greg Hankins, Force10 Networks; Drew Perkins, Infinera; Igor Gashinsky, Yahoo!; Lane PattersonEquinix; .
  • Panel: Higher Speed Ethernet - 40G vs 100G
    Moderators:
    Richard A. Steenbergen, nLayer Communications; Panelists:
    Greg Hankins, Force10 Networks; Drew Perkins, Infinera; Igor Gashinsky, Yahoo!; Lane PattersonEquinix; .
  • Panel: Higher Speed Ethernet - 40G vs 100G
    Moderators:
    Richard A. Steenbergen, nLayer Communications; Panelists:
    Greg Hankins, Force10 Networks; Drew Perkins, Infinera; Igor Gashinsky, Yahoo!; Lane PattersonEquinix; .
  • Panel: Higher Speed Ethernet - 40G vs 100G
    Moderators:
    Richard A. Steenbergen, nLayer Communications; Panelists:
    Greg Hankins, Force10 Networks; Drew Perkins, Infinera; Igor Gashinsky, Yahoo!; Lane PattersonEquinix; .
  • Panel: Higher Speed Ethernet - 40G vs 100G
    Moderators:
    Richard A. Steenbergen, nLayer Communications; Panelists:
    Greg Hankins, Force10 Networks; Drew Perkins, Infinera; Igor Gashinsky, Yahoo!; Lane PattersonEquinix; .
  • ISP Security
    Moderators:
    Danny McPherson, Arbor Networks; Kevin Lanning, AT&T;
  • ISP Security
    Moderators:
    Danny McPherson, Arbor Networks; Kevin Lanning, AT&T;
  • BGP Tools
    Speakers:
    Daniel Massey, Colorado State University;
  • Community Meeting
    Speakers:
    Randy BushActing SC Chair; .
    Steve FeldmanPC Chair; .
    Aleksandr PilosovActing MLC Chair; .
    Betty BurkeNANOG Project Chair at MERIT; .
  • Community Meeting
    Speakers:
    Randy BushActing SC Chair; .
    Steve FeldmanPC Chair; .
    Aleksandr PilosovActing MLC Chair; .
    Betty BurkeNANOG Project Chair at MERIT; .
  • Community Meeting
    Speakers:
    Randy BushActing SC Chair; .
    Steve FeldmanPC Chair; .
    Aleksandr PilosovActing MLC Chair; .
    Betty BurkeNANOG Project Chair at MERIT; .
  • Community Meeting
    Speakers:
    Randy BushActing SC Chair; .
    Steve FeldmanPC Chair; .
    Aleksandr PilosovActing MLC Chair; .
    Betty BurkeNANOG Project Chair at MERIT; .
  • Real-time Blackhole Analysis with Hubble
    Speakers:
    Ethan Katz-Bassett, University of Washington; Harsha V. MadhyasthaUniversity of Washington; .
    John P. JohnsonUniversity of Washington; .
    Arvind KrishnamurthyUniversity of Washington; .
    Thomas AndersonUniversity of Washington; .
  • Real-time Blackhole Analysis with Hubble
    Speakers:
    Ethan Katz-Bassett, University of Washington; Harsha V. MadhyasthaUniversity of Washington; .
    John P. JohnsonUniversity of Washington; .
    Arvind KrishnamurthyUniversity of Washington; .
    Thomas AndersonUniversity of Washington; .
  • Real-time Blackhole Analysis with Hubble
    Speakers:
    Ethan Katz-Bassett, University of Washington; Harsha V. MadhyasthaUniversity of Washington; .
    John P. JohnsonUniversity of Washington; .
    Arvind KrishnamurthyUniversity of Washington; .
    Thomas AndersonUniversity of Washington; .
  • Real-time Blackhole Analysis with Hubble
    Speakers:
    Ethan Katz-Bassett, University of Washington; Harsha V. MadhyasthaUniversity of Washington; .
    John P. JohnsonUniversity of Washington; .
    Arvind KrishnamurthyUniversity of Washington; .
    Thomas AndersonUniversity of Washington; .
  • Real-time Blackhole Analysis with Hubble
    Speakers:
    Ethan Katz-Bassett, University of Washington; Harsha V. MadhyasthaUniversity of Washington; .
    John P. JohnsonUniversity of Washington; .
    Arvind KrishnamurthyUniversity of Washington; .
    Thomas AndersonUniversity of Washington; .

 

^ Back to Top