SWIFT: Predictive Fast Reroute
Background
BGP is a well-known routing protocol used for inter-AS. Internet is composed of more than 20000 nodes. The network structure changes at any time, which brings great challenges to BGP convergence.
Problem
BGP converges slowly upon remote outages. This can result in long data-plane downtime for many destinations, including popular ones.
- Slow outage detection: In BGP, propagation of outage is done hop by hop.
- Slow routing table updating: There are huge amount of prefixes. BGP router need to update each infected entry when outrage occurs.
So in this paper, author present SWIFT, a fast reroute algorithm.
SWIFT Overview
Before the outage. The SWIFTED router continuously pre-computes backup next-hops (consistently with BGP routes) to use upon remote outages. This computation is done for each prefix and considering any link on the corresponding AS path.
Upon the outage. After receiving a few BGP withdrawals caused by the failure, the SWIFTED router runs an inference algorithm that quickly identifies a set of possibly disrupted AS links and affected prefixes. The router then redirects the traffic for all the affected prefixes to the pre-computed backup next-hops.
Main design of SWIFT
- An inference algorithm which can detect the failed link.
SWIFT monitors the received input stream of BGP messages, looking for significant increases in the frequency of withdrawals.
When detecting a burst, SWIFT infers the corresponding failed link as the one maximizing a metric called Fit Score (FS).
- A encoding algorithm which can tag each session to facilitate the forwarding.
- The first part of the tag encodes the AS path along which each packet will flow.
- The second part of the tag identifies the primary next-hop as well as backup next-hops for each encoded AS link.
According to this, router can forward the request according to the tag rather than prefix.
Inspiration from this paper
- This paper only explain the result that current BGP converges slowly when remote outage occurs in several aspects, but they doesn’t explain why current BGP performance bad and why SWIFT can solve the problem.
- ICN is a potential method to solve the problem of slowly converge in BGP because name-based routing can eliminate the number of long-distance sessions, so it is likely that we can use ICN to solve this problem.