Distributed routing architecture

• US 9,282,032 B2
• Filed: 02/26/2015
• Issued: 03/08/2016
• Est. Priority Date: 12/17/2009
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Judge, Alan M., McGaugh, David J., Hamilton, James R., Pietsch, Justin O., O'Meara, David J.
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): KAVLESKI, RYAN C
• Application Number:
  US14/632,962
• Publication Number:
  US 20150172178A1
• Time in Patent Office: 376 Days
• Field of Search: 370/392, 370/400, 370/408
• US Class Current: 1/1
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04L 45/44 Distributed routing
• CPC Class Codes: H04L 45/58 Association of routers
• CPC Class Codes: H04L 45/741 Routing in networks with a plurality of addressing schemes, e.g. with both IPv4 and IPv6
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 47/33 using forward notification
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: H04L 69/323 in the physical layer [OSI layer 1]

Abstract

A routing management component is provided for distributing routing information among a hierarchical distributed routing architecture. The routing management component can function to associate levels of the routing architecture with subsets of a network address format. The routing management component can further assign routers of the routing architecture to portions of network addresses defined at least in part by the network address format. For example, a router may be assigned to route packets addressed to a network address with a first octet between a range of values. The router management component may further distribute, to the routers of the hierarchical distributed routing architecture, sections of routing information associated with their assigned portions of network addresses. Because routing information can be distributed between various routers, the memory requirements of individual routers can be reduced comparatively to systems in which a single router maintains an entire set of forwarding information.

Claims

1. A system for routing packets, the system comprising:

one or more routers associated with a first level of a hierarchy of physical routing components;

one or more routers associated with a second level of the hierarchy of physical routing components; and

a management component for distribution of forwarding information associated with the first and second levels of the hierarchy, the management component comprising one or more processors configured with specific computer-executable instructions to;

receive the forwarding information for routing data packets addressed to individual addresses within a set of network addresses, wherein the set of network addresses are expressed in a network address format;

select a first subset of the network address format to associate with the first level of the hierarchy, wherein the first subset of the network address format identifies a specific segment of the individual addresses of the set of network addresses;

assign to a router of the first level a first portion of the set of network addresses, wherein the first portion of the set of network addresses is defined at least in part by the first subset of the set of network address format;

distribute, to the determined router of the first level, a first section of the forwarding information, the first section including routing information for the first portion of the set of network addresses;

select a second subset of the network address format to associate with the second level of the hierarchy, wherein the second subset of the network address format identifies a second specific segment of the individual addresses of the set of network addresses;

assign to a router of the second level a second portion of the set of network addresses, wherein the second portion of the set of network addresses is defined at least in part by the second subset of the set of network address format; and

distribute, to the router of the second level, a second section of the forwarding information, the second section including routing information for the second portion of the set of network addresses.

2. The system of claim 1, wherein the network address format corresponds to at least one of an internet protocol version four (IPv4) address format or an internet protocol version six (IPv6) address format.

3. The system of claim 1, wherein the first subset of the network address format corresponds to a first eight or sixteen bits of a 32-bit address format.

4. The system of claim 1, wherein the second subset of the network address format corresponds to a first sixteen or twenty four bits of a 32-bit address format.

5. The system of claim 1, wherein the first portion of the set of network addresses is determined based at least in part on a traffic volume associated with the first portion of the set of network addresses.

6. The system of claim 1, wherein the router of the second level is configured to utilize the second section of the forwarding information to determine a destination component for one or more received packets.

7. The system of claim 6, wherein the destination component is at least one of a component included within a third level of the hierarchy of physical routing components or a component external to the hierarchy of physical routing components.

8. A computer-implemented method for managing packet routing within a hierarchy of physical routing components, the computer-implemented method comprising:

associating a first subset of a network address format with a first level of the hierarchy of physical routing components, wherein the network address format corresponds to a set of network addresses expressible within the network address format, and wherein the first subset of the network address format identifies a specific segment of individual addresses within the set of addresses;

assigning to a router of the first level a first portion of the set of network addresses, wherein the first portion of the set of network addresses is defined at least in part by the first subset of the network address format;

distributing a first section of a set of forwarding information to the router of the first level, wherein the forwarding information includes information for routing data packets addressed to at least one of the set of network addresses, and wherein the first section includes routing information for the first portion of the set of network addresses;

associating a second subset of the network address format to a second level of the hierarchy of physical routing components, wherein the second subset of the network address format identifies a second specific segment of the individual addresses of the set of network addresses;

assigning to a router of the second level a second portion of the set of network addresses, wherein the second portion of the set of network addresses is defined at least in part by the second subset of the network address format; and

distributing a second section of the forwarding information to the router of the second level, the second section including routing information for the second portion of the set of network addresses.

9. The computer-implemented method of claim 8, wherein the second subset of the network address format is represented by a greater number of bits than the first subset of the network address format.

10. The computer-implemented method of claim 8, wherein the forwarding information forms a forwarding information base (FIB).

11. The computer-implemented method of claim 8 further comprising determining at least two additional portions of the set of network addresses to assign to individual routers of the first level, wherein the at least two portions of the set of network addresses include an equal number of network addresses.

12. The computer-implemented method of claim 8 further comprising assigning the first portion of the set of network addresses to an additional router of the first level, and distributing the first section of the forwarding information to the additional router of the first level.

13. The computer-implemented method of claim 8, wherein the router of the first level is configured to store the first section of the forwarding information in a first memory component, and wherein the computer-implemented method further comprises distributing an additional section of the forwarding information to the router of the first level for storage in a second memory component.

14. The computer-implemented method of claim 8, wherein the first portion of the set of network addresses is determined based at least in part on a traffic volume associated with the first portion of the set of network addresses.

15. The computer-implemented method of claim 14, wherein the first portion of the set of network addresses is determined based at least in part on a determination that the traffic volume associated with the first portion of the set of network addresses satisfies a threshold traffic volume.

17. The non-transitory computer-readable storage media of claim 14, wherein the computer-executable instructions further cause the processor to assign the first portion of the set of network addresses to an additional router of the first level, and to distribute the first section of the forwarding information to the additional router of the first level.

18. The non-transitory computer-readable storage media of claim 14, wherein the router of the first level includes a first memory component and a second memory component, the first memory component associated with a faster access time than the second memory component, and wherein the first section of the forwarding information contains more information than may be simultaneously stored in the first memory component.

19. The non-transitory computer-readable storage media of claim 14, wherein the first portion of the set of network addresses is determined based at least in part on a traffic volume associated with the first portion of the set of network addresses.

20. The non-transitory computer-readable storage media of claim 14, wherein at least two routers of the first level are implemented by a single physical router component.

16. Non-transitory computer-readable storage media including computer-executable instructions for managing packet routing within a hierarchy of physical routing components, wherein the computer-executable instructions, when executed by a processor, cause the processor to:

select a first subset of a network address format to associate with a first level of the hierarchy of physical routing components, wherein the network address format corresponds to a set of network addresses expressible within the network address format, and wherein the first subset of the network address format identifies a specific segment of individual addresses of the set of addresses;

determine a first portion of the set of network addresses to assign to a router of the first level, wherein the first portion of the set of network addresses is defined at least in part by the first subset of the network address format;

distribute a first section of a set of forwarding information to the router of the first level, wherein the set of forwarding information includes information for routing data packets addressed to one of the set of network addresses, and wherein the first section includes routing information for the first portion of the set of network addresses;

select a second subset of the network address format to associate with a second level of the hierarchy of physical routing components, wherein the second subset of the network address format identifies a second specific segment of the individual addresses of the set of network addresses;

determine a second portion of the set of network addresses to assign to a router of the second level, wherein the second portion of the set of network addresses is defined at least in part by the second subset of the network address format; and

distribute a second section of the forwarding information to the router of the second level, the second section including routing information for the second portion of the set of network addresses.