Method and apparatus for achieving Border Gateway Protocol convergence using alternate route information

1. A method, comprising computer-implemented steps of:

at a first router in a packet-switched network:

receiving an advertisement of a first route and a notification indicating that an alternate route is available at a second router;

storing the notification in association with the first route;

detecting a change in network reachability of the first route, and in response thereto, determining if the notification is stored for the first route, and if so:

awaiting, for a particular time, an advertisement comprising the alternate route from the second router without sending a BGP withdrawal message;

storing and using the alternate route in place of the first route;

otherwise, initiating by the first router, a request for an alternate route by sending a BGP withdraw message.

2. A method as recited in claim 1 , wherein an unreachability advertisement relating to the first route is sent only when no alternate route information is stored for the first route.

3. A method as recited in claim 1 , wherein a route withdrawal message is sent in response to determining that the alternate route information is stored for the first route.

4. A method as recited in claim 1 , wherein the first route is received in a Border Gateway Protocol (BGP) UPDATE message.

5. A method as recited in claim 1 , wherein a route withdrawal message is sent for the first route if no alternate route is received within the particular time.

6. A method as recited in claim 1 , wherein the first route is received from a BGP route reflector that identifies the first route as a best path for a destination, determines whether an alternate path exists for the first route, and if so, creates and sends a route advertisement message that includes the first route and the alternate route information.

7. A method as recited in claim 1 , wherein a BGP route reflector determines a need to re-advertise the first route, determines that the first route was previously received from a particular BGP peer, and re-advertises the first route in association with second information instructing the particular BGP peer to ignore alternates available.

8. A method, comprising computer-implemented steps of:

at a Border Gateway Protocol (BGP) route reflector in a packet-switched network, identifying a first route as a best path for a destination, determining whether an alternate path exists for the first route, and if so, creating and sending a route advertisement message that includes the first route and a notification indicating that an alternate route is available at a second router;

at a BGP router that is communicatively coupled to the packet-switched network, receiving the route advertisement message, storing the first route and the notification in a route information base that the BGP router manages, detecting a change in reachability for the first route, and in response thereto, determining if the notification is stored for the first route, and if so: awaiting, for a particular time, an advertisement comprising the alternate route from the second router without sending a BGP withdrawal message;

storing and using the alternate route in place of the first route; otherwise, initiating by the BGP router, a request for an alternate route by sending a BGP withdraw message;

at the BGP route reflector, determining a need to re-advertise the first route, determining that the first route was previously received from a particular BGP peer, and re-advertising the first route in association with second information instructing the particular BGP peer to ignore alternates available.

9. An apparatus, comprising:

a Border Gateway Protocol (BGP) route reflector comprising read-write storage configured to store a plurality of route values and a plurality of alternate available route indicators, indicating that an alternate route is available at a second router, in association with corresponding routes;

one or more packet data routers configured as BGP peers of the BGP route reflector and communicatively coupled to the BGP route reflector in one or more BGP peering sessions;

in at least one of the routers, one or more stored sequences of instructions for improving BGP convergence in a packet-switched data network, which instructions, when executed by one or more processors, cause the one or more processors to carry out the steps of:

receiving an advertisement of a first route and a notification-indicating that an alternate route is available at the second router;

storing the notification in association with the first route;

detecting a change in network reachability of the first route, and in response thereto, determining if the notification is stored for the first route, and if so: awaiting, for a particular time, an advertisement comprising the alternate route from the second router without sending a BGP withdrawal message; storing and using the alternate route in place of the first route; otherwise, initiating by the

at least one router, a request for an alternate route by sending a BGP withdraw message.

10. An apparatus as recited in claim 9 , wherein an unreachability advertisement relating to the first route is sent only when no alternate route information is stored for the first route.

11. An apparatus as recited in claim 9 , wherein a route withdrawal message is sent in response to determining that the alternate route information is stored for the first route.

12. An apparatus as recited in claim 9 , wherein the first route is received in a Border Gateway Protocol (BGP) UPDATE message.

13. An apparatus as recited in claim 9 , wherein a route withdrawal message is sent for the first route if no alternate route is received within the particular time.

14. An apparatus as recited in claim 9 , wherein the first route is received from a BGP route reflector that identifies the first route as a best path for a destination, determines whether an alternate path exists for the first route, and if so, creates and sends a route advertisement message that includes the first route and the alternate route information.

15. An apparatus as recited in claim 9 , wherein a BGP route reflector determines a need to re-advertise the first route, determines that the first route was previously received from a particular BGP peer, and re-advertises the first route in association with second information instructing the particular BGP peer to ignore alternates available.

16. An apparatus, comprising:

means for receiving, at a first router in a packet-switched network, an advertisement of a first route and a notification indicating that an alternate route is available at a second router;

means for storing, at the first router, the notification in association with the first route;

means for detecting, at the first router, a change in network reachability of the first route, and in response thereto, determining if the notification is stored for the first route, and if so: for awaiting, for a particular time, an advertisement comprising the alternate route from the second router without sending a BGP withdrawal message; for storing and using the alternate route in place of the first route; otherwise, initiating by the first router, a request for an alternate route by sending a BGP withdraw message.

17. An apparatus as recited in claim 16 , wherein an unreachability advertisement relating to the first route is sent only when no alternate route information is stored for the first route.

18. An apparatus as recited in claim 16 , wherein a route withdrawal message is sent in response to determining that the alternate route information is stored for the first route.

19. An apparatus as recited in claim 16 , wherein the first route is received in a Border Gateway Protocol (BGP) UPDATE message.

20. An apparatus as recited in claim 16 , wherein a route withdrawal message is sent for the first route if no alternate route is received within the particular time.

21. An apparatus as recited in claim 16 , wherein the first route is received from a BGP route reflector that identifies the first route as a best path for a destination, determines whether an alternate path exists for the first route, and if so, creates and sends a route advertisement message that includes the first route and the alternate route information.

22. An apparatus as recited in claim 16 , wherein a BGP route reflector determines a need to re-advertise the first route, determines that the first route was previously received from a particular BGP peer, and re-advertises the first route in association with second information instructing the particular BGP peer to ignore alternates available.

23. An apparatus, comprising:

means, at a Border Gateway Protocol (BGP) route reflector in a packet-switched network, for identifying a first route as a best path for a destination, determining whether an alternate path exists for the first route, and if so, creating and sending a route advertisement message that includes the first route and a notification indicating that an alternate route is available at a second router;

means, at a BGP router that is communicatively coupled to the packet-switched network, for receiving the route advertisement message, storing the first route and the notification indicating that the alternate route is available at the second router in a route information base that the BGP router manages, detecting a change in reachability for the first route, and in response thereto, determining if the notification is stored for the first route, and if so: awaiting, for a particular time, an advertisement comprising the alternate route from the second router without sending a BGP withdrawal message; storing and using the alternate route in place of the first route; otherwise, initiating by the BGP router, a request for an alternate route by sending a BGP withdraw message;

means, at the BGP route reflector, for determining a need to re-advertise the first route, determining that the first route was previously received from a particular BGP peer, and re-advertising the first route in association with second information instructing the particular BGP peer to ignore alternates available.