Distributed routing architecture

• US 8,902,897 B2
• Filed: 09/14/2012
• Issued: 12/02/2014
• 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: Hamilton, James R., Judge, Alan M., McGaugh, David J., Pietsch, Justin O., O'Meara, David J.
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): KAVLESKI, RYAN C
• Application Number:
  US13/620,281
• Publication Number:
  US 20130010788A1
• Time in Patent Office: 809 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/58 Association of routers
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

A hierarchical distributed routing architecture including at least two 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 receive a 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 at least one second level physical routing component based at least in part on the first subset of the destination address, wherein the identified at least one 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 potential destination addresses to individual second level physical routing components of the second level; and

transmit the packet to the identified at least one second level physical routing component; and

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 an outgoing transit path based at least in part on the second subset of the destination address, wherein the identified outgoing transit path is associated with the second subset of the destination address based at least in part on a dynamic allocation of individual portions of a set of potential destination addresses to individual outgoing transit paths; and

transmit the packet to the identified outgoing transit path.

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 routing physical components corresponding to at least one of the first level or the second level of the hierarchy of physical routing components are implemented in a physical router device.

5. The system of claim 1, wherein each physical routing component corresponding to at least one of the first level or the second level of the hierarchy of physical routing components 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 potential destination addresses to the individual second level physical routing components.

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 the first subset of the destination address, wherein the identified second level 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 potential destination addresses to individual second level routing components of the second level of the routing component hierarchy;

causing the packet to be routed to the second level routing component;

identifying, at the second level router component, an outgoing transit path based at least in part on the second subset of the destination address, wherein the identified outgoing transit path is associated with the second subset of the destination address based at least in part on a dynamic allocation of individual portions of a set of potential destination addresses to individual outdoing transit paths; and

causing the packet to be routed to the outgoing transit path.

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 the dynamic allocation of individual portions of a set of potential destination addresses to individual second level routing components of the second level of the routing component hierarchy is based at least in part on traffic volume associated with the set of potential destination addresses.

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

12. 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 a first subset of the destination address, wherein the identified second level 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 potential destination addresses to individual second level routing components; 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 an external routing path based at least in part on a second subset of the destination address, wherein the identified external routing path is associated with the second subset of the destination address based at least in part on a dynamic allocation of individual portions of a set of potential destination addresses to individual outgoing transit paths; and

transmit the packet to the identified external routing path.

13. The system of claim 12, wherein the destination address corresponds to an IP address.

14. The system of claim 13, 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.

15. The system of claim 12, 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.

16. The system of claim 15, 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.

17. The system of claim 12, wherein the dynamic allocation of individual portions of the set of potential destination addresses to individual second level routing components is based at least in part on traffic volume associated with the set of potential destination addresses.

18. The system of claim 12 further comprising a router management device configured to dynamically allocate the individual portions of the set of potential destination addresses to individual second level routing components.

19. The system of claim 12, wherein the dynamic allocation of the individual portions of the set of potential destination addresses to individual second level routing components of the second level of the routing component hierarchy is based at least in part on an available memory capacity of the individual second level routing components.