Scalable route resolution

• US 7,746,790 B1
• Filed: 02/01/2007
• Issued: 06/29/2010
• Est. Priority Date: 07/17/2002
• Status: Expired due to Fees

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Murphy, James, Cole, Bruce A.
• Primary Examiner(s): Patel; Jayanti K
• Assistant Examiner(s): PARK, JUNG H
• Application Number:
  US11/670,272
• Time in Patent Office: 1,244 Days
• Field of Search: 370/238, 370/356, 370/389, 370/392, 370/400, 370/401, 709/238, 709/239, 709/240, 709/241
• US Class Current: 370/238
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/60 Router architectures

Abstract

A router comprises a route resolution module to maintain routing information in accordance with a topology of a network, and an indirect next hop manager to maintain indirect next hop data that associates protocol next hops with forwarding next hops. The route resolution module invokes an application programming interface (API) of the indirect next hop manager for associating and disassociating protocol next hops and forwarding next hops. In response to a network event, the route resolution module can modify the indirect next hop data to reduce the time and resources necessary to perform route resolution.

Claims

1. A method comprising:

storing indirect next hop data within a packet forwarding engine of a router, wherein the indirect next hop data associates protocol next hops with forwarding next hops, wherein the protocol next hops identify peer routers that disseminated routes to the router in accordance with a routing protocol, and wherein the forwarding next hops identify neighboring routers physically coupled to the router;

maintaining a tree data structure external to the indirect next hop data, wherein the tree data structure includes route resolution nodes that resolve prefixes to entries within the indirect next hop data;

traversing the route resolution nodes of the tree data structure in response to a network event to identify one or more affected protocol next hops;

in response to a network event, modifying the indirect next hop data within the packet forwarding engine to associate the affected protocol next hops with a different forwarding next hop; and

forwarding packets within a network using the modified indirect next hop data.

2. The method of claim 1, further comprising receiving a packet comprising network update information.

3. The method of claim 1, further comprising:

receiving a network message advertising one or more routes associated with a first protocol next hop;

receiving a network message advertising one or more routes associated with a first forwarding next hop;

resolving the first protocol next hop to the first forwarding next hop; and

associating the first protocol next hop and the first forwarding next hop within the indirect next hop data.

4. The method of claim 3, wherein associating the first protocol next hop and the first forwarding next hop comprises:

allocating an indirect next hop index; and

storing the first protocol next hop and the first forwarding next hop within the indirect next hop data according to the indirect next hop index.

5. The method of claim 1, further comprising storing in the indirect next hop data forwarding next hops and associated protocol next hops in combination with identifiers for packet forwarding policies.

6. The method of claim 1, further comprising storing in the indirect next hop data forwarding next hops and associated protocol next hops in combination with forwarding labels.

7. The method of claim 6, wherein the forwarding labels comprise virtual private network labels.

8. The method of claim 7, wherein the forwarding labels comprise MPLS labels.

9. The method of claim 1, wherein the indirect next hop data includes addressable elements.

10. The method of claim 9, wherein each element represents a pair of a key and a value, and wherein the protocol next hops represent keys for the addressable elements and the forwarding next hops represent values for the elements.

11. The method of claim 10, wherein the indirect next hop data forms a two-dimensional array having rows and columns, and wherein each row is accessible by a respective indirect next hop index and uniquely associates a protocol next hop and a forwarding next hop.

12. The method of claim 9, wherein the elements uniquely associate forwarding next hops with protocol next hops in combination with identifiers for forwarding policies.

13. The method of claim 9, wherein the indirect next hop data comprises a numerical space in which the elements are addressable by an index.

14. A router comprising:

a packet forwarding engine to forward packets in accordance with forwarding information, wherein the packet forwarding engine stores indirect next hop data having entries that associates protocol next hops with forwarding next hops, wherein the protocol next hops identify peer routers that disseminated routes to the router in accordance with a routing protocol, and wherein the forwarding next hops identify neighboring routers physically coupled to the router;

a routing engine to maintain a tree data structure external to the indirect next hop data, wherein the tree data structures includes route resolution nodes that resolve network prefixes to the entries within the indirect next hop data; and

wherein, in response to a network event, the routing engine accesses the route resolution nodes of the tree data structure to identify one or more affected protocol next hops and modifies the entries of the indirect next hop data within the packet forwarding engine to associate the affected protocol next hops with a different one of the forwarding next hops.

15. The router of claim 14, wherein each of the elements represents a pair of a key and a value, and wherein the protocol next hops represent keys for the addressable elements and the forwarding next hops represent values for the elements.

16. The router of claim 14, wherein the indirect next hop data forms a two-dimensional array having rows and columns, and wherein each row is accessible by a respective indirect next hop index and uniquely associates a protocol next hop and a forwarding next hop.

17. The router of claim 14, wherein the elements uniquely associate forwarding next hops with protocol next hops in combination with identifiers for forwarding policies.

18. The router of claim 14, wherein the elements uniquely associate forwarding next hops with protocol next hops in combination with forwarding labels.

19. The router of claim 18, wherein the forwarding labels comprise virtual private network (VPN) labels or MPLS labels.

20. The router of claim 14, wherein the indirect next hop comprises a numerical space in which the elements are addressable by an index.