Method and apparatus for accelerating border gateway protocol convergence

• US 20060233181A1
• Filed: 04/13/2005
• Published: 10/19/2006
• Est. Priority Date: 04/13/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Raszuk, Robert, Shah, Himanshu, Patel, Keyur, Fernando, Rex E.
• Granted Patent: US 7,532,631 B2
• Time in Patent Office: Days
• US Class Current: 370/401
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/54 Organization of routing tables

Abstract

A method and apparatus are disclosed for accelerating Border Gateway Protocol (BGP) route convergence in an autonomous system. A virtual link identifier is assigned to each link of a set of communication links that are established between a BGP host and one or more network elements in one or more networks. For a particular link of the set of communication links, one or more routes that are reachable on the link are determined. The BGP host stores an association of the one or more routes with a BGP identifier of the BGP host and the virtual link identifier that is assigned to the particular link. The BGP host advertises the one or more routes to a BGP peer in a message, where the message includes the BGP identifier and the virtual link identifier.

Claims

1. A method of identifying routes in a Border Gateway Protocol (BGP) host, the method comprising the computer-implemented steps of:

assigning a virtual link identifier to each link of a set of digital communication links established between the BGP host and one or more BGP peers;

determining one or more routes that are reachable on a particular link of the set of digital communication links; and

creating and storing, in electronic digital memory, an association of the one or more routes with a BGP identifier of the BGP host and a particular virtual link identifier that is assigned to the particular link.

2. A method as recited in claim 1, further comprising advertising, in a first BGP message, the one or more routes to a particular BGP peer of the one or more BGP peers, wherein the first BGP message includes the BGP identifier and the particular virtual link identifier.

3. A method as recited in claim 2, further comprising sending a second BGP message to the particular BGP peer, wherein the message indicates that the one or more routes are withdrawn and includes the BGP identifier and the particular virtual link identifier.

4. A method as recited in claim 1, wherein the particular link is any one of a logical transport connection and a physical medium transport connection.

5. A method of accelerating route convergence in autonomous systems using Border Gateway Protocol (BGP), the method comprising the computer-implemented steps of:

at a BGP host, performing the steps of;

assigning separate virtual link identifiers to each link of a set of communication links established between the BGP host and one or more network elements in one or more networks;

determining one or more routes that are reachable on a particular link of the set of communication links; and

associating the one or more routes with a BGP identifier and a virtual link identifier assigned to the particular link, wherein the BGP identifier identifies the BGP host;

advertising, in a first message, the one or more routes to a BGP peer, wherein the first message includes the BGP identifier and the virtual link identifier;

determining whether the particular link has become unavailable;

if the particular link has become unavailable, then sending to the BGP peer a second message that includes the BGP identifier and the virtual link identifier, wherein the second message indicates that the one or more routes are withdrawn.

6. A method as recited in claim 5, wherein:

the one or more routes are each associated with separate address prefixes; and

the second message does not include any address prefix associated with the one or more routes.

7. A method as recited in claim 5, further comprising:

at the BGP peer, receiving the second message; and

based on the BGP identifier and the virtual link identifier, withdrawing the one or more routes.

8. A method as recited in claim 5, wherein:

each route of the one or more routes is associated with an address prefix;

advertising the one or more routes further comprises including in the first message the address prefix associated with each route;

in response to receiving the first message at the BGP peer, storing the one or more routes in a routing table, wherein storing includes recording the address prefix, the BGP identifier, and the virtual link identifier associated with each route of the one or more routes; and

in response to receiving the second message at the BGP peer, performing the steps of

identifying the one or more routes based only on the BGP identifier and the virtual link identifier; and

withdrawing the one or more routes, wherein withdrawing comprises at least one of deleting the one or more routes from the routing table and setting a status code, for each route of the one or more routes, which indicates that each route is withdrawn.

9. A method as recited in claim 8, wherein:

the BGP peer is a BGP route reflector; and

the method further comprises sending, to a particular BGP peer of the BGP route reflector, a third message that indicates to the particular BGP peer that the one or more routes are withdrawn.

10. A method as recited in claim 9, wherein the third message includes the BGP identifier and the virtual link identifier.

11. A method as recited in claim 9, wherein the third message includes the address prefix associated with each route of the one or more routes.

12. A method as recited in claim 5, wherein:

the first message is a BGP UPDATE message; and

advertising the one or more routes to the BGP peer further comprises storing the BGP identifier and the virtual link identifier in a path attribute field of the first message.

13. A method as recited in claim 5, wherein:

in addition of being reachable on the particular link, the one or more routes are reachable on a specific link of the set of communication links that is different than the particular link;

the step of associating the one or more routes further comprises associating the one or more routes with the BGP identifier and a specific virtual link identifier assigned to the specific link; and

the step of advertising the one or more routes further comprises including the specific virtual identifier in the first message.

14. A method as recited in claim 5, further comprising:

as part of establishing a BGP session, negotiating an accelerated BGP convergence capability between the BGP host and the BGP peer, wherein the accelerated BGP convergence capability is defined by an Address Family Identifier (AFI) value and a Subsequent Address Family Identifier (SAFI) value; and

wherein the second message further includes the AFI value and the SAFI value.

15. A method as recited in claim 14, wherein the second message is a BGP UPDATE message.

16. A method as recited in claim 5, further comprising:

storing a message counter in a path attribute field of any message sent by the BGP host, wherein the value of the message counter is incremented every time the BGP host sends a new message;

in response to receiving a particular message at a BGP peer, determining whether the one or more routes advertised in the particular message are stored at the BGP peer, wherein the particular message is any one of the first message and the second message;

if it is determined that the one or more routes are not stored at the BGP peer, then storing the value of the message counter in a routing table, wherein the value of the message counter is associated with the one or more routes advertised in the particular message; and

if it is determined that the one or more are stored at the BGP peer, then dropping the particular message if the value of the message counter received in the particular message is lower than the value of the message counter that is stored in the routing table for the one or more routes advertised in the particular message.

17. A method as recited in claim 16, wherein the path attribute field is a BGP extended community attribute field.

18. A method as recited in claim 5, wherein the BGP peer is established in a different autonomous system than the BGP host and at least one of the steps of advertising the one or more routes to the BGP peer and sending the second message to the BGP peer is performed over an external Border Gateway Protocol (eBGP) transport connection.

19. A method as recited in claim 5, wherein:

the BGP peer is established in the same autonomous system as the BGP host; and

at least one of the steps of advertising the one or more routes to the BGP peer and sending the second message to the BGP peer is performed over an Internal Gateway Protocol (IGP) transport connection.

20. A method as recited in claim 5, wherein:

the BGP peer is established in the same autonomous system as the BGP host; and

at least one of the steps of advertising the one or more routes to the BGP peer and sending the second message to the BGP peer is performed over an internal Border Gateway Protocol (iBGP) transport connection.

21. A method as recited in claim 5, wherein each route of the one or more routes is at least one of an Internet Protocol version 4 (IPv4) route, an Internet Protocol version 6 (IPv6) route, and a Virtual Private Network (VPN) route.

22. A method as recited in claim 5, wherein:

the one or more routes include a first route to a particular address destination; and

the method further comprises the steps of;

at the BGP peer, receiving a third message that advertises a second route to the particular address destination, wherein the second route is different than the first route; and

re-advertising the first route and the second route to a BGP neighbor of the BGP peer.

23. A method as recited in claim 5, further comprising, in response to receiving the second message at the BGP peer, withdrawing the one or more routes, wherein the one or more routes are identified based only on the BGP identifier.

24. A method as recited in claim 5, wherein:

the BGP host runs a plurality of BGP instances; and

the step of associating further comprises associating the one or more routes with a plurality of distinct BGP identifiers, wherein each distinct BGP identifier corresponds to a distinct BGP instance of the plurality of BGP instances, and wherein the BGP identifier is one of the plurality of distinct BGP identifiers.

25. A method as recited in claim 5, wherein:

the virtual link identifier comprises a first portion and a second portion;

the first portion uniquely identifies a network interface of the BGP host;

the second portion identifies a network element of the one or more network elements, wherein the network element is communicatively connected to the network interface over the particular link; and

the method further comprises, in response to receiving the second message at the BGP peer, withdrawing the one or more routes, wherein the one or more routes are identified based on any one of the first portion of the virtual link identifier and the second portion of the virtual link identifier.

26. A method as recited in claim 5, wherein determining whether the particular link has become unavailable comprises at least one of:

(a) detecting whether a BGP instance running on the BGP host has become unavailable;

(b) detecting whether a transport connection over which the particular link is established has failed, wherein the transport connection is established between the BGP host and a particular network element of the one or more network elements; and

(c) detecting whether the particular network element has failed.

27. A network element, comprising:

one or more processors;

one or more stored sequences of instructions which, when executed by the one or more processors, cause the one or more processors to perform the steps of;

executing a Border Gateway Protocol (BGP) instance;

assigning a virtual link identifier to each link of a set of digital communication links established between the BGP host and one or more BGP peers;

determining one or more routes that are reachable on a particular link of the set of digital communication links; and

creating and storing, in electronic digital memory, an association of the one or more routes with a BGP identifier of the BGP host and a particular virtual link identifier that is assigned to the particular link.

28. A network element for accelerating route convergence in autonomous systems using Border Gateway Protocol (BGP), wherein the network element executes a BGP instance, the network element comprising:

means for assigning separate virtual link identifiers to each link of a set of communication links established between the BGP instance and one or more network elements in one or more networks;

means for storing one or more routes that are reachable on a particular link of the set of communication links;

means for associating the one or more routes with a BGP identifier and a virtual link identifier assigned to the particular link, wherein the BGP identifier identifies the BGP instance;

means for advertising, in a first message, the one or more routes to a BGP peer, wherein the first message includes the BGP identifier and the virtual link identifier;

means for determining whether the particular link has become unavailable;

means for sending to the BGP peer a second message that includes the BGP identifier and the virtual link identifier, wherein the second message indicates that the one or more routes are withdrawn, and wherein the second message is sent if the particular link has become unavailable.

29. A computer-readable medium carrying one or more sequences of instructions for identifying routes in a Border Gateway Protocol (BGP) host, which instructions, when executed by one or more processors, cause the one or more processors to perform the steps of:

assigning a virtual link identifier to each link of a set of digital communication links established between the BGP host and one or more BGP peers;

determining one or more routes that are reachable on a particular link of the set of communication links; and

creating and storing, in electronic digital memory, an association of the one or more routes with a BGP identifier of the BGP host and a particular virtual link identifier that is assigned to the particular link.

30. A computer-readable medium carrying one or more sequences of instructions for accelerating route convergence in a Border Gateway Protocol (BGP) host, which instructions, when executed by one or more processors, cause the one or more processors to perform the steps of:

assigning separate virtual link identifiers to each link of a set of communication links established between the BGP host and one or more network elements in one or more networks;

storing one or more routes that are reachable on a particular link of the set of communication links;

associating the one or more routes with a BGP identifier and a virtual link identifier assigned to the particular link, wherein the BGP identifier identifies the BGP host;

advertising, in a first message, the one or more routes to a BGP peer, wherein the first message includes the BGP identifier and the virtual link identifier;

determining whether the particular link has become unavailable;

if the particular link has become unavailable, then sending to the BGP peer a second message that includes the BGP identifier and the virtual link identifier, wherein the second message indicates that the one or more routes are withdrawn.