Distributed routing architecture

• US 8,971,328 B2
• Filed: 09/14/2012
• Issued: 03/03/2015
• 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): Ton, Dang
• Assistant Examiner(s): KAVLESKI, RYAN C
• Application Number:
  US13/620,363
• Publication Number:
  US 20130010796A1
• Time in Patent Office: 900 Days
• Field of Search: 370/392, 370/400, 370/408
• US Class Current: 370/392
• 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, the system comprising:

a first level of a hierarchy of physical routing components comprising one or more first level physical routing components, wherein each of the one or more first level physical routing components is configured to;

receive a packet for routing, wherein the packet comprises at least a destination address, and wherein the destination address comprises a first subset of the destination address and a second subset of the destination address;

identify a second level physical routing component based at least in part on an association of the first subset of the destination address with the identified second level physical routing component, wherein the identified second level physical routing component is associated with the first subset of the destination address based at least in part on a dynamic allocation of individual portions of a set of destination addresses to individual second level physical routing components of the second level of the physical routing component hierarchy; and

transmit the packet to the identified second level routing component;

a second level of the hierarchy of physical routing components comprising one or more second level physical routing components, wherein each of the one or more second level physical routing components is configured to;

receive the packet from a first level physical routing component;

identify a third level physical routing component based at least in part on an association of the second subset of the destination address with the identified third level physical routing component, wherein the identified third level physical routing component is associated with the second subset of the destination address based at least in part on a dynamic allocation of individual portions of the set of destination addresses to individual third level physical routing components of the third level of the physical routing component hierarchy; and

transmit the packet to the identified third level physical routing component; and

a third level of the hierarchy of physical routing components comprising one or more third level physical routing components, wherein each of the one or more third level physical routing components is configured to;

receive the packet from a second level physical routing component;

identify an additional component to which to transmit the packet; and

transmit the packet to the identified additional component.

2. The system of claim 1, wherein the destination address corresponds to an IP address.

3. The system of claim 2, wherein the first subset of the destination address corresponds to the eight most significant bits of the IP address.

4. The system of claim 1, wherein at least two physical routing components corresponding to at least one of the first level, the second level, or the third level of the hierarchy of physical routing components are implemented in a common physical router device.

5. The system of claim 1, wherein each physical routing component corresponding to at least one of the first level, the second level, or the third level is allocated a portion of destination addresses of packets based at least in part on traffic volume associated with one or more destination addresses of the packets.

6. The system of claim 1 further comprising a router management device configured to dynamically allocate the individual portions of the set of destination addresses to the individual second level routing components of the second level of the routing component hierarchy.

7. A computer-implemented method for routing packets, the method comprising:

receiving, at a router component of a first level of a routing component hierarchy, a packet comprising a first subset of a destination address and a second subset of the destination address;

identifying a second level routing component of a second level of the routing component hierarchy based at least in part on an association of the first subset of the destination address with the identified second level physical routing component, wherein the identified second level physical routing component is associated with the first subset of the destination address based at least in part on a dynamic allocation of individual portions of a set of destination addresses to individual second level physical routing components of the second level of the physical routing component hierarchy;

transmitting the packet to the second level routing component;

identifying, at the second level router component, a third level routing component of a third level of the routing component hierarchy based at least in part on an association of the second subset of the destination address with the identified third level physical routing component, wherein the identified third level physical routing component is associated with the second subset of the destination address based at least in part on a dynamic allocation of individual portions of the set of destination addresses to individual third level physical routing components of the third level of the physical routing component hierarchy;

transmitting the packet to the third level routing component;

identifying, at the third level router component, an additional component to which to transmit the packet; and

transmitting the packet to the additional component.

8. The computer-implemented method of claim 7, wherein the destination address corresponds to an IP address.

9. The computer-implemented method of claim 8, wherein the second subset of the destination address corresponds to at least one of the sixteen or twenty four most significant bits of the IP address.

10. The computer-implemented method of claim 7, wherein at least one routing component of the first level of the routing component hierarchy, the second level of the routing component hierarchy, and the third level of the routing component hierarchy are dynamically allocated individual portions of the set of destination addresses of packets based at least in part on traffic volume associated with the allocated portions of the set of destination addresses of the packets.

11. The computer-implemented method of claim 10, wherein remaining routing components of the first level of the routing component hierarchy, the second level of the routing component hierarchy, and the third level of the routing component hierarchy are allocated approximately equal portions of the set of destination addresses of the packets.

12. The computer-implemented method of claim 10, wherein remaining routing components of the first level of the routing component hierarchy, the second level of the routing component hierarchy, and the third level of the routing component hierarchy are allocated portions of the set of destination addresses of packets based on at least one of random selection, round robin selection, hashing and load balancing.

13. The computer-implemented method of claim 7, wherein identifying a second level routing component of a second level of the routing component hierarchy comprises:

attempting to identify the second level routing component from address information persisted in a first memory, and

if the address information is not available in the first memory component, attempting to identify the second level routing component from address information persisted in a second memory;

wherein the first memory is associated with a faster access time than the second memory.

14. A system for routing packets, the system comprising one or more physical routing devices configured with specific computer-executable instructions that, when executed by the physical routing devices, cause the physical routing devices to implement at least:

a first level of a routing component hierarchy comprising one or more first level routing components, wherein the first level of the routing component hierarchy is configured to;

in response to reception of a packet comprising a destination address, identify a second level routing component based at least in part on an association of a first subset of the destination address with the identified second level physical routing component, wherein the identified second level physical routing component is associated with the first subset of the destination address based at least in part on a dynamic allocation of individual portions of a set of destination addresses to individual second level physical routing components of the second level of the physical routing component hierarchy; and

transmit the packet to the identified second level routing component;

a second level of the routing component hierarchy comprising one or more second level routing components, wherein the second level of the routing component hierarchy is configured to;

in response to reception of the packet from the first level of the routing component hierarchy, identify a third level routing component based at least in part on an association of a second subset of the destination address with the identified third level physical routing component, wherein the identified third level physical routing component is associated with the second subset of the destination address based at least in part on a dynamic allocation of individual portions of the set of destination addresses to individual third level physical routing components of the third level of the physical routing component hierarchy; and

transmit the packet to the identified third level routing component;

a third level of the routing component hierarchy comprising one or more third level routing components, wherein the third level of the routing component hierarchy is configured to;

in response to reception of the packet from the second level of the routing component hierarchy, identify an additional component to which to transmit the packet; and

transmit the packet to the identified additional component.

15. The system of claim 14, wherein the destination address corresponds to an IP address.

16. The system of claim 15, wherein the first subset of the destination address corresponds to at least one of the eight, the sixteen, or the twenty four most significant bits of the IP address.

17. The system of claim 14, wherein each of the second level routing components comprises a first memory and a second memory for storing destination address information, and wherein the first memory is associated with a faster access time than the second memory.

18. The system of claim 17, wherein each of the second level routing components are further configured to:

attempt to identify the third level routing component from address information persisted in the first memory, and

if the address information is not available in the first memory, attempt to identify the third level routing component from address information persisted in the second memory component.

19. The system of claim 14, wherein at least one routing component of the first level, the second level, and the third level are dynamically allocated individual portions of the set of destination addresses of packets based at least in part on traffic volume associated with the allocated portions of the set of destination addresses of the packets.

20. The system of claim 19, wherein remaining routing component of the first level, the second level, and the third level are allocated portions of the set of destination addresses of packets based on at least one of random selection, round robin selection, hashing and load balancing.

21. The system of claim 19, wherein remaining routing component of the first level, the second level, and the third level are allocated approximately equal portions of the set of destination addresses of the packets.

22. The system of claim 14 further comprising a router management device configured to dynamically allocate the individual portions of the set of destination addresses to the individual second level routing components of the second level of the routing component hierarchy.