Identifying and suppressing transient routing updates

• US 7,496,650 B1
• Filed: 03/29/2004
• Issued: 02/24/2009
• Est. Priority Date: 01/09/2003
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Filsfils, Clarence, Ward, David Delano, Scudder, John Galen, Previdi, Stefano Benedetto
• Primary Examiner(s): Dollinger; Tonia L
• Assistant Examiner(s): Sikri; Anish
• Application Number:
  US10/811,626
• Time in Patent Office: 1,793 Days
• Field of Search: 370/16
• US Class Current: 709/223
• CPC Class Codes: H04L 45/028 Dynamic adaptation of the update intervals, e.g. event-triggered updates
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

One or more sets of routing information are maintained. A network topology change indication of a progressive series of network changes is received, with at least one more associated network topology change indication of the progressive series of network changes expected to be received in the future. An updated set of routing information is computed based on the network topology change indication, and a determination is made as to whether or not the updated set of routing information changes nexthop information for one or more routes. In response to determining that the new set of routing information does not change nexthop information for said one or more routes and given the expectation of at least one more associated network topology change indication of the progressive series of network changes is expected to be received in the future, the routing information is not updated based on the updated set of routing information.

Claims

1. An apparatus comprising one or more processing elements and memory, wherein the memory stores one or more instructions that, when executed by said one or more processing elements, performs operations comprising:

maintaining one or more sets of routing information;

wherein said maintaining one or more sets of routing information includes;

computing an updated set of routing information based on a received network topology change indication and said one or more sets of routing information, the updated set of routing information including changes in one or more routes in said one or more sets of routing information, the network topology change indication being one of a progressive series of network changes related to a specific detected change in the network with at least one more associated network topology change indication of the progressive series of network changes expected to be received in the future;

wherein the network change indication includes a value identifying that said at least one more associated network topology change indication of the progressive series of network changes is expected to be received in the future; and

in response to determining that said updated routing information does not change nexthop information of said maintained one or more sets of routing information and said expectation, defined by the value, of said at least one more associated network topology change indication of the progressive series of network changes to be received in the future, determining not to update said one or more sets of routing information based on the updated set of routing information.

2. The apparatus of claim 1, wherein said maintaining one or more sets of routing information includes:

computing a second updated set of routing information based on a second received network topology change indication and said one or more sets of routing information, the second updated set of routing information including changes in one or more routes in said one or more sets of routing information, the second network topology change indication being one of the progressive series of network changes with at least one more associated network topology change indication of the progressive series of network changes expected to be received in the future; and

in response to determining that second updated set of routing information does change nexthop information of said maintained one or more sets of routing information, updating said one or more sets of routing information based on the second updated set of routing information.

3. The apparatus of claim 1, wherein the network topology change indication identifies one or more routing metric changes.

4. The apparatus of claim 1, wherein said maintaining one or more sets of routing information includes:

in response to identifying a timeout condition corresponding to the updated set of routing information subsequent to said determination of not to update said one or more sets of routing information based on the updated set of routing information, updating said one or more sets of routing information based on the updated set of routing information.

5. A method for updating routing information, the method comprising:

maintaining a routing information base;

wherein said maintaining one or more sets of routing information includes;

receiving a network topology change indication, the network topology change indication including a route update of a progressive series of route updates for switching routing to a computed backup path;

wherein the network topology change indication includes a value defining to expect one or more route updates of the progressive series of route updates;

performing a shortest path first determination based on the route update and the routing information base to identify an updated set of routing information, including updated one or more routes; and

in response to determining that the updated set of routing information does not change nexthop information for one or more routes included in the routing information base and the value to expect one or more route updates of the progressive series of route updates, determining not to update said one or more sets of routing information based on the updated set of routing information even though it includes said updated one or more routes.

6. The method of claim 5, wherein said maintaining one or more sets of routing information includes:

subsequent to said determination not to update said one or more sets of routing information, in response to identifying a timeout condition corresponding to the updated set of routing information, updating said one or more sets of routing information based on the updated set of routing information.

7. An apparatus for updating routing information, said apparatus comprising:

means for maintaining one or more sets of routing information;

wherein said means for maintaining one or more sets of routing information includes;

means for receiving a network topology change indication, the network topology change indication being one of a progressive series of network changes related to a specific detected change in the network with at least one more associated network topology change indication of the progressive series of network changes expected to be received in the future;

wherein the network change indication includes a value identifying that said at least one more associated network topology change indication of the progressive series of network changes is expected to be received in the future;

means for computing an updated set of routing information based on the network topology change indication and said one or more sets of routing information, the updated set of routing information including updated one or more routes;

means for determining not to update said one or more sets of routing information based on the updated set of routing information, even though it includes said updated one or more routes, in response to determining that said updated set of routing information does not change nexthop information in said maintained one or more sets of routing information and said expectation, defined by the value, of said at least one more associated network topology change indication of the progressive series of network changes to be received in the future.

8. The apparatus of claim 7, wherein said means for maintaining one or more sets of routing information includes:

means for updating said one or more sets of routing information based on the updated set of routing information in response to determining that the new set of routing information does change nexthop information in said maintained one or more sets of routing information.

9. The apparatus of claim 7, wherein the network topology change indication identifies one or more routing metric changes.

10. The apparatus of claim 7, wherein said means for maintaining one or more sets of routing information includes:

means for, subsequent to said determining not to update said one or more sets of routing information, updating said one or more sets of routing information based on the updated set of routing information in response to identifying a timeout condition corresponding to the updated set of routing information.

11. An apparatus for updating routing information, the apparatus comprising:

means for maintaining a routing information base;

wherein said means for maintaining a routing information base includes;

means for receiving a network topology change indication, the network topology change indication including a route update of a progressive series of route updates for switching routing to a computed backup path;

wherein the network topology change indication includes a value defining to expect one or more route updates of the progressive series of route updates;

means for performing a shortest path first determination based on the route update and the routing information base to identify an updated set of routing information, including updated one or more routes;

means for determining not to update said one or more sets of routing information based on the updated set of routing information even though it includes said one or more updated routes in response to determining that the updated set of routing information does not change nexthop information for one or more routes included in the routing information base and the value to expect one or more route updates of the progressive series of route updates.

12. The apparatus of claim 11, wherein said means for maintaining a routing information base includes:

means for updating said one or more sets of routing information based on the updated set of routing information subsequent to said determination not to previously update the routing information base in response to identifying a timeout condition corresponding to the updated set of routing information.

13. A method, comprising:

maintaining one or more sets of routing information in a router, for use by the router in routing of packets;

wherein said maintaining one or more sets of routing information includes;

computing an updated set of routing information based on a received network topology change indication and said one or more sets of routing information, the updated set of routing information including changes in one or more routes in said one or more sets of routing information, the network topology change indication being one of a progressive series of network changes related to a specific detected change in the network with at least one more associated network topology change indication of the progressive series of network changes expected to be received in the future;

wherein the network change indication includes a value identifying that said at least one more associated network topology change indication of the progressive series of network changes is expected to be received in the future; and

in response to determining that said updated routing information does not change nexthop information of said maintained one or more sets of routing information and said expectation, defined by the value, of said at least one more associated network topology change indication of the progressive series of network changes to be received in the future, determining not to update said one or more sets of routing information based on the updated set of routing information.

14. The method of claim 13, wherein said maintaining one or more sets of routing information includes:

computing a second updated set of routing information based on a second received network topology change indication, the second updated set of routing information including changes in one or more routes, the second network topology change indication being one of the progressive series of network changes with at least one more associated network topology change indication of the progressive series of network changes expected to be received in the future; and

in response to determining that second updated set of routing information does change nexthop information of said maintained one or more sets of routing information, updating said one or more sets of routing information based on the second updated set of routing information.

15. The method of claim 13, wherein the network topology change indication identifies one or more routing metric changes.

16. The method of claim 13, wherein said maintaining one or more sets of routing information includes:

in response to identifying a timeout condition corresponding to the updated set of routing information subsequent to said determination of not to update said one or more sets of routing information based on the updated set of routing information, updating said one or more sets of routing information based on the updated set of routing information.