Scalable route resolution

• US 7,184,437 B1
• Filed: 07/17/2002
• Issued: 02/27/2007
• Est. Priority Date: 07/17/2002
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Murphy, James, Cole, Bruce A
• Primary Examiner(s): Nguyen; Chau
• Assistant Examiner(s): PARK, JUNG H
• Application Number:
  US10/197,922
• Time in Patent Office: 1,686 Days
• Field of Search: None
• US Class Current: 370/392
• 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:

maintaining indirect next hop data within a centralized routing engine, wherein the indirect next hop data associates protocol next hops with forwarding next hops;

communicating the indirect next hop data from the routing engine to one or more packet forwarding engines;

updating the indirect next hop data within the centralized routing engine in response to network events;

issuing one or more messages from the routing engine to at least one of the packet forwarding engines in response to the update, wherein the messages direct the packet forwarding engine to associate at least one of the protocol next hops with a different forwarding next hop; and

routing packets within a network using the indirect next hop data.

2. The method of claim 1, wherein routing packets comprises:

generating the indirect next hop data in response to protocol messages advertising routes within the network;

generating forwarding information in accordance with the indirect next hop data; and

forwarding the packets in accordance with the forwarding information.

3. The method of claim 1, wherein the indirect next hop data comprises addressable entries that store pairs of protocol next hops and forwarding next hops.

4. The method of claim 1, wherein updating the indirect next hop data comprises:

receiving a packet comprising network update information.

5. The method of claim 1, wherein routing packets comprises:

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.

6. The method of claim 5, 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.

8. 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.

9. 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.

10. The method of claim 9, wherein the forwarding labels comprise virtual private network labels.

11. The method of claim 9, wherein the forwarding labels comprise MPLS labels.

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

13. The method of claim 12, 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.

14. The method of claim 12, 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.

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

16. The method of claim 12, wherein the elements uniquely associate forwarding next hops with protocol next hops in combination with forwarding labels.

17. The method of claim 16, wherein the forwarding labels comprise virtual private network (VPN) labels.

18. The method of claim 16, wherein the forwarding labels comprise MPLS labels.

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

7. A method comprising:

maintaining a tree data structure having route resolution leaf nodes that resolve prefixes to unique identifiers for addressable entries within indirect next hops data that associates protocol next hops and forwarding next hops;

receiving a packet comprising network update information;

traversing dependent route resolution leaf nodes of the tree in response to the network event to identify unique identifiers for one or more affected indirect next hops;

modifying the addressable entries of the indirect next hop data addressed by the unique identifiers to associate at least one of the protocol next hops with a different forwarding next hop; and

routing packets within a network using the indirect next hop data.

20. A router comprising:

a computer-readable medium to store indirect next hop data having addressable elements, wherein the elements uniquely associate protocol next hops with forwarding next hops;

a routing engine to maintain routing information in accordance with a topology of a network; and

a packet forwarding engine to forward packets in accordance with forwarding information, wherein, in response to network events, the routing engine updates the indirect next hop data and issues messages directing the packet forwarding engine to update the forwarding information,

wherein the packet forwarding engine maintains a version of the indirect next hop data and updates the version of the indirect next hop data in response to the messages by modifying the indirect next hop data to associate at least one protocol next hop with a different forwarding next hop.

21. The router of claim 20, 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.

22. The router of claim 20, 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.

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

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

25. The router of claim 24, wherein the forwarding labels comprise virtual private network (VPN) labels.

26. The router of claim 24, wherein the forwarding labels comprise MPLS labels.

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

28. A router comprising:

a routing engine comprising;

(i) a route resolution module to maintain routing information in accordance with a topology of a network; and

(ii) an indirect next hop manager to maintain indirect next hop data that associate protocol next hops with forwarding next hops, wherein 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; and

a packet forwarding engine to forward packets in accordance with forwarding information, wherein, in response to network events, the routing engine updates the indirect next hop data and issues messages directing the packet forwarding engine to update the forwarding information,

wherein the packet forwarding engine maintains a version of the indirect next hop data and updates the version of the indirect next hop data in response to the messages by modifying the indirect next hop data to associate at least one protocol next hop with a different forwarding next hop.

29. The router of claim 28, wherein the route resolution module maintains a tree having route resolution leaf nodes that resolve prefixes to indirect next hops.

30. The router of claim 29, wherein the route resolution module traverses dependent route resolution leaf nodes of the tree in response to the network event and identifies one or more affected indirect next hops.

31. The router of claim 28, wherein the indirect next hop data comprises addressable elements, wherein each element stores a protocol next hop and a respective forwarding next hop.