Method for providing loop free routing table in a router

• US 20060159034A1
• Filed: 12/23/2005
• Published: 07/20/2006
• 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
• Granted Patent: US 7,889,712 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• 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; and

a module to evaluate a route of the routing table and detect a loop path associated with the route.

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 maintains a list of remote next hops associated with paths of a route, and designates remote next hops resulting in a loop path as inactive.

4. The router of claim 3 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 3 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.

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 is a loop path is detected.

7. The router of claim 3 wherein the list of remote next hops is evaluated in response to deleting a first route from the routing table, wherein the first route is dependant 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; and

a module to evaluate a route using the routing table and detect a loop path associated with the route, the module maintains a list of remote next hops associated with paths of the route and designates remote next hops resulting in a loop path as 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, the first route is designated as an active route if no loop path is detected and designated as inactive is a 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, wherein the first route is dependant upon a parent route and the module evaluates the parent route.

12. A method comprising:

managing communication routes in a system wherein routes are added and deleted;

evaluating the communication routes to detect path loops in response to managing the communication routes; and

designating routes associated with a loop as inactive routes.

13. The method of claim 12 further comprising:

periodically evaluating the communication routes to determine if a previously detected loop has been eliminated; and

designating routes associated with an eliminated loop as active routes.

14. The method of claim 12 wherein evaluating the communication routes comprises maintaining a list of remote next hops associated with each route, and wherein designating the routes associated with a loop as inactive routes comprises designating remote next hops associated with the routes as inactive.

15. The method of claim 14 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, the first route is designated as an active route if no path loop is detected and designated as inactive is a path loop is detected.

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

17. A method comprising:

managing communication routes in a system;

evaluating the communication routes to detect path loops in response to managing the communication routes;

designating routes associated with a loop as inactive routes;

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

re-designating routes associated with an eliminated loop as active routes.

18. The method of claim 17 wherein evaluating the communication routes comprises maintaining a list of remote next hops associated with each route, and wherein designating the routes associated with a loop as inactive routes comprises designating remote next hops associated with the routes as inactive.

19. A router comprising:

means for managing communication routes in a system wherein routes are added and deleted;

means for evaluating the communication routes to detect path loops in response to managing the communication routes; and

means for designating routes associated with a loop as inactive routes.

20. The router of claim 19 further comprising:

means for periodically evaluating the communication routes to determine if a previously detected loop has been eliminated; and

means for designating routes associated with an eliminated loop as active routes.

21. The method of claim 19 wherein the means for evaluating the communication routes further maintains a list of remote next hops associated with each route, and wherein the means for designating the routes associated with a loop as inactive routes further designates remote next hops associated with the routes as inactive.