Method and apparatus for accelerating border gateway protocol convergence

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.

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.

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.

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.

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.