Distributed routing architecture

• US 10,063,459 B2
• Filed: 03/07/2016
• Issued: 08/28/2018
• Est. Priority Date: 12/17/2009
• Status: Expired due to Fees

• 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): Jiang, Charles C
• Assistant Examiner(s): Kavleski, Ryan
• Application Number:
  US15/063,368
• Publication Number:
  US 20160254985A1
• Time in Patent Office: 904 Days
• 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 hierarchical distributed routing architecture including at least three levels, or layers, for receiving, processing and forwarding data packets between network components is provided. The core level router components receive an incoming packet from a network component and identify a distribution level router component based on processing a subset of the destination address associated with the received packet. The distribution level router components that receiving a forwarded packet and identify a transit level router component based a second processing of at least a subset of the destination address associated with the received packet. The transit level router components receive the forwarded packet and forward the packet to a respective network. The mapping, or other assignment, of portions of the FIB associated with the distributed routing environment is managed by a router management component.

Claims

1. A system for routing packets in hierarchy of physical routing components having a first and second level of physical routing components, the system comprising:

a physical data store for maintaining forwarding information for routing data packets addressed to destination addresses within a set of network addresses, wherein the set of network addresses are expressed in a network address format;

one or more physical processors configured with specific computer-executable instructions to;

assign physical routing components of the second level to subsets of the set of network addresses, wherein the subsets of the set of network addresses are defined according to a first part of the network address format, and wherein assignment of the physical routing components within the second level to the subsets of the set of network addresses allocates responsibility to the physical routing components within the second level for routing respective subsets of the data packets that are addressed to their assigned subsets of the set of network addresses;

transmit to physical routing components of the first level information identifying assignment of the physical routing components within the second level to the subsets of the set of network addresses, wherein the physical routing components within the first level are configured to route the data packets to the physical routing components of the second level based on inspecting a section of the destination addresses corresponding to the first part of the network address format;

partition the forwarding information into sections according to the assignment of the physical routing components within the second level to the subsets of the set of network addresses; and

distribute to the physical routing components of the second level the respective sections of the forwarding information that pertain to their assigned subsets of the set of network addresses.

2. The system of claim 1, wherein the assignment of physical routing components within the second level to the subsets of the set of network addresses is based on a traffic volume associated with a subset of the assigned subsets.

3. The system of claim 1, wherein the respective section of the forwarding information distributed to a physical routing component of the second level requires more memory to store than is available within a primary memory of the physical routing component.

4. The system of claim 1, wherein the hierarchy of physical routing components includes an initial level of physical routing components prior to the first level, and wherein the one or more physical processors are further configured with specific computer-executable instructions to:

assign the physical routing components of the first level to subsets of the set of network addresses that are defined according to a second part of the network address format, wherein assignment of the physical routing components of the first level to the subsets of the set of network addresses that are defined according to a second part of the network address format allocates responsibility to the physical routing components of the first level for routing respective subsets of the data packets that are addressed to their assigned subsets of the set of network addresses; and

transmit to the physical routing components of the initial level information identifying assignment of the physical routing components of the first level to the subsets of the set of network addresses that are defined according to a second part of the network address format, wherein physical routing components within the initial level are configured to route the data packets to the physical routing components of the first level based on inspecting a section of the destination addresses corresponding to the second part of the network address format.

5. The system of claim 4, wherein the second part of the network address format is a smaller part of the network address format than the first part.

6. The system of claim 1, wherein a physical routing component of the second level of the hierarchy is configured to store a received section of the forwarding information in a combination of a first memory component and a second memory component, and wherein the physical routing component is configured to determine a portion of the received section of forwarding information that is stored in the first memory component based on a number of data packets obtained by the physical routing component that pertain to the portion.

7. The system of claim 1, wherein the one or more physical processors are further configured with the specific computer-executable instructions to alter the assignment of physical routing components of the second level to the subsets of the set of network addresses based on traffic volumes associated with the subsets of the set of network addresses.

8. In a hierarchy of physical routing components having a first and second level of physical routing components, a computer-implemented method for managing routing of data packets comprising:

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

assigning physical routing components of the second level to subsets of the set of network addresses, wherein the subsets of the set of network addresses are defined according to a first part of the network address format, and wherein assignment of the physical routing components within the second level to the subsets of the set of network addresses allocates responsibility to the physical routing components within the second level for routing respective subsets of the data packets that are addressed to their assigned subsets of the set of network addresses;

transmitting to the physical routing components of the first level information identifying assignment of the physical routing components within the second level to the subsets of the set of network addresses, wherein the physical routing components within the first level are configured to route the data packets to the physical routing components of the second level based on inspecting a section of the destination addresses corresponding to the first part of the network address format; and

distributing to physical routing components of the second level sections of the forwarding information that pertain to their assigned subsets of the set of network addresses.

9. The computer-implemented method of claim 8, wherein assigning the physical routing components of the second level to the subsets of the set of network addresses comprises determining a traffic volume attributed to network addresses within one of the subsets of the set of network addresses and selecting the subset based on the traffic volume.

10. The computer-implemented method of claim 8, wherein the subset assigned to a physical routing component of the first level is associated with a section of the forwarding information that requires more memory to store than is available within a primary memory of the physical routing component.

11. The computer-implemented method of claim 8 further comprising distributing additional sections of the forwarding information to an individual physical routing component of the second level, the additional sections including forwarding information relevant to subsets of the set of network addresses that are not assigned to the individual physical routing component of the second level.

12. The computer-implemented method of claim 8 further comprising altering the assignment of physical routing component within the second level to the subsets based on traffic volumes associated with the subsets.

13. The computer-implemented method of claim 8, wherein the hierarchy of physical routing components includes an initial level of physical routing components prior to the first level, and wherein the computer-implemented method further comprises:

assigning physical routing components within the first level to subsets of the set of network addresses that are defined according to a second part of the network address format, wherein assignment of the physical routing components of the first level to the subsets of the set of network addresses that are defined according to a second part of the network address format allocates responsibility to the physical routing components of the first level for routing respective subsets of the data packets that are addressed to their assigned subsets of the set of network addresses; and

transmitting, to the physical routing components of the initial level, information identifying assignment of the physical routing components of the first level to the subsets of the set of network addresses that are defined according to a second part of the network address format, wherein physical routing components within the initial level are configured to route the data packets to the physical routing components of the first level based on inspecting a section of the destination addresses corresponding to the second part of the network address format.

14. Non-transitory computer-readable storage media including computer-executable instructions for managing routing in hierarchy of physical routing components having a first and second level of physical routing components, wherein the computer-executable instructions, when executed by a processor, cause the processor to:

assign physical routing components within the second level to subsets of a set of network addresses expressible in a network address format, wherein the subsets are defined according to a first part of the network address format, and wherein assignment of the physical routing components within the second level to the subsets of the set of network addresses allocates responsibility to the physical routing components within the second level for routing respective subsets of the data packets that are addressed to their assigned subsets of the set of network addresses;

transmit, to the physical routing components of the first level, information identifying assignment of the physical routing components within the second level to the subsets of the set of network addresses, wherein physical routing components within the first level are configured to route the data packets to the physical routing components of the second level based on inspecting a section of the destination addresses corresponding to the first part of the network address format; and

distribute, to the physical routing components of the second level, respective sections of forwarding information for routing data packets addressed to destination addresses within a set of network addresses, the respective sections including forwarding information that pertains to the subsets of the set of network addresses assigned to the physical routing components.

15. The non-transitory computer-readable storage media of claim 14, wherein a physical routing component of the second 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 subset to the physical routing component is selected by the processor to correspond to a section of the forwarding information that includes more information than can be simultaneously stored in the first memory component.

16. The non-transitory computer-readable storage media of claim 14, wherein the assignment of physical routing components within the second level to the subsets of the set of network addresses is generated based on a traffic volume associated with a subset of the assigned subsets.

17. The non-transitory computer-readable storage media of claim 14, wherein the computer-executable instructions further cause the processor to distribute additional sections of the forwarding information to individual physical routing components of the second level, the additional sections including forwarding information relevant to subsets of the set of network addresses that are not assigned to the individual physical routing components of the first level.

18. The non-transitory computer-readable storage media of claim 14, wherein the computer-executable instructions further cause the processor to alter the assignment of physical routing components within the second level to the subsets of the set of network addresses based on traffic volumes associated with the subsets of the set of network addresses.

19. The non-transitory computer-readable storage media of claim 14, wherein the assignment of physical routing components of the second level of the hierarchy to the subsets of the set of network addresses is generated to assign two routers of the of the second level of physical routing components to respective subsets that overlap with respect to at least one network address that is included in both respective subsets.

20. The non-transitory computer-readable storage media of claim 14, wherein the hierarchy of physical routing components includes an initial level of physical routing components prior to the first level, and wherein the computer-executable instructions further cause the processor to:

assign physical routing components within the first level to subsets of the set of network addresses that are defined according to a second part of the network address format, wherein assignment of the physical routing components of the first level to the subsets of the set of network addresses that are defined according to a second part of the network address format allocates responsibility to the physical routing components of the first level for routing respective subsets of the data packets that are addressed to their assigned subsets of the set of network addresses; and

transmit, to the physical routing components of the initial level, information identifying assignment of the physical routing components of the first level to the subsets of the set of network addresses that are defined according to the second part of the network address format, wherein physical routing components within the initial level are configured to route the data packets to the physical routing components of the first level based on inspecting a section of the destination addresses corresponding to the second part of the network address format.