Methods and apparatus for providing loop free routing tables

• US 7,889,712 B2
• Filed: 12/23/2005
• Issued: 02/15/2011
• Est. Priority Date: 12/23/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Talur, Dheerendra, Fernando, Rex, Sachdev, Avneesh, Yeung, Derek Man-Kit
• Primary Examiner(s): Shah; Chirag G
• Assistant Examiner(s): Zhou; Yong
• Application Number:
  US11/318,217
• Publication Number:
  US 20060159034A1
• Time in Patent Office: 1,880 Days
• Field of Search: 370/238, 370/254, 370/255, 370/256, 370/351, 370/356, 370/389, 370/395.52
• US Class Current: 370/351
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/54 Organization of routing tables

Abstract

A router is described that includes a routing table containing route information and a module to evaluate a route and detect a loop path associated with the route using the routing table. A process is described to detect and eliminate routing loops associated with recursive routes in a routing table, so as to provide a routing table that will be loop free.

Claims

1. A router comprising:

a routing module configured to maintain a routing table containing route information to determine data traffic routes;

a module to evaluate remote next hops in response to path changes in a route of the routing table and to detect a loop path associated with the route, the module to add the loop path to a hidden list, the module further to maintain a list of remote next hops associated with paths of the route that are not hidden; and

a hidden timer to periodically trigger a timer thread and to reevaluate the route associated with the loop path added to the hidden list.

2. The router of claim 1 wherein the module is implemented by a unicast routing information base (URIB) of the router.

3. The router of claim 1 wherein the module designates remote next hops resulting in the loop path as inactive.

4. The router of claim 1 wherein the list of remote next hops is evaluated in response to adding, modifying, or deleting a route from the router.

5. The router of claim 1 wherein the list of remote next hops is evaluated in response to adding a first route to the routing table, and wherein the first route added is a branch route that is used by a second route and is also dependent on a third route.

6. The router of claim 5 wherein the first route is designated as an active route if no loop path is detected and designated as inactive if a loop path is detected.

7. The router of claim 1 wherein the list of remote next hops is evaluated in response to deleting a first route from the routing table, and wherein the first route is dependent upon a parent route and the module evaluates the parent route.

8. A router comprising:

a routing module configured to maintain a routing table containing route information;

a module to evaluate remote next hops in response to path changes in a route using the routing table and detect a loop path associated with the route, the module to maintain a list of remote next hops associated with paths of the route and to designate remote next hops resulting in a loop path as inactive; and

a hidden timer to periodically trigger a timer thread and to reevaluate the paths of the route resulting in the loop path to determine whether the remote next hops should remain inactive.

9. The router of claim 8 wherein the module periodically evaluates the route to determine if a previously detected loop has been eliminated.

10. The router of claim 8 wherein the list of remote next hops is evaluated in response to adding a first route to the routing table, wherein the first route added is a branch route that is used by a second route and is also dependent on a third route, and wherein the first route is designated as an active route if no loop path is detected and designated as inactive if the loop path is detected.

11. The router of claim 8 wherein the list of remote next hops is evaluated in response to deleting a first route from the routing table, and wherein the first route is dependent upon a parent route and the module evaluates the parent route.

12. A method comprising:

evaluating remote next hops in communication routes in a system to detect path loops in response to changes in the communication routes;

maintaining a list of remote next hops associated with each route;

designating routes associated with a loop as inactive routes; and

periodically reevaluating the inactive routes associated with the loop and, based on a determination that the inactive routes are no longer associated with the loop, removing the designation of the inactive route and redesignating the inactive routes as active.

13. The method of claim 12 wherein designating the routes associated with the loop as inactive routes comprises designating remote next hops associated with the routes as inactive.

14. The method of claim 13 wherein the list of remote next hops is evaluated in response to adding a first route, wherein the first route is a branch route that is used by a second route and is also dependent on a third route, and wherein the first route is designated as an active route if no path loop is detected and designated as inactive if the path loop is detected.

15. The method of claim 13 wherein the list of remote next hops is evaluated in response to deleting a first route, wherein the first route is dependent upon a parent route, and wherein evaluating the communication routes to detect path loops comprises evaluating the parent route.

16. A method comprising:

evaluating remote next hops in communication routes in a system to detect path loops in response to changes in the communication routes;

designating routes associated with a loop as inactive routes;

maintaining a list of remote next hops associated with each route;

periodically re-evaluating the inactive routes to determine whether a previously detected loop has been eliminated; and

based on a determination that the previously detected loop has been eliminated, re-designating routes associated with an eliminated loop as active routes.

17. The method of claim 16 wherein designating the routes associated with the loop as inactive routes comprises designating remote next hops associated with the routes as inactive.

18. A router comprising:

means for evaluating remote next hops in communication routes in a system to detect path loops in response to changes in the communication routes;

means for maintaining a list of remote next hops associated with each route;

means for designating routes associated with a loop as inactive routes; and

means for periodically reevaluating the inactive routes and making a determination whether the inactive routes remain associated with a loop.

19. The router of claim 18 further comprising means for designating routes associated with an eliminated loop as active routes.

20. The method of claim 18 wherein the means for designating the routes associated with the loop as inactive routes further designates remote next hops associated with the routes as inactive.