Distributed routing architecture

• US 8,331,370 B2
• Filed: 12/17/2009
• Issued: 12/11/2012
• 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): Phan, Man
• Assistant Examiner(s): Kavleski, Ryan
• Application Number:
  US12/641,255
• Publication Number:
  US 20110149963A1
• Time in Patent Office: 1,090 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 destination addresses to router components of the distributed routing environment may be managed by a router management component. In some embodiments, mapping of destination address to router components may be based, at least in part, on traffic volumes associated with the mapped destination addresses.

Claims

1. A system for routing packets comprising:

a router management device, executed on a computing device, for associating destination address information to a router hierarchy comprising a plurality of levels, wherein the router management device is configured to, for each level of the router hierarchy, dynamically assign one or more router devices to a portion of incoming packets based at least in part on traffic volume associated with one or more destination addresses of the incoming packets;

one or more router devices corresponding to a first level of the router hierarchy; and

one or more router devices corresponding to a second level of a router hierarchy, the second level of the router hierarchy for processing an incoming packet for routing received from at least one of the one or more router devices corresponding to the first level of a router hierarchy, wherein each router device corresponding to the second level is dynamically allocated a portion of destination addresses of incoming packets by the router management device, and wherein the portion of destination address is associated with a first subset of destination addresses of incoming packets;

wherein the one or more router devices corresponding to the first level of a router hierarchy receive, for routing, an incoming packet comprising a destination address, and identify at least one router device corresponding to the second level of a router hierarchy based on a first subset of a destination address of the incoming packet, and wherein the at least one router device corresponding to the second level of a router hierarchy identifies an outgoing transit path based on a second”

subset of the destination address of the incoming packet, and wherein the second subset of the destination address is greater than the first subset of the destination address.

2. The system as recited in claim 1, wherein the one or more router devices corresponding to a first level of a router hierarchy are selected in accordance with one of random selection, round robin selection, hashing and load balancing.

3. The system as recited in claim 1, wherein the destination address corresponds to an IP address.

4. The system as recited in claim 3, wherein the first subset of the IP address corresponds to the eight most significant bits of the IP address.

5. The system as recited in claim 3, wherein the first subset of the IP address corresponds to at least one of the sixteen or twenty four most significant bits of the IP address.

6. The system as recited in claim 1, wherein at least two of the one or more router devices corresponding to the first level of the router hierarchy are implemented in a common physical router device.

7. The system as recited in claim 1, wherein at least two of the one or more router devices corresponding to the second level of the router hierarchy are implemented in a common physical router device.

8. The system as recited in claim 1, wherein the destination address corresponds to an IP flow descriptor.

9. The system as recited in claim 1, wherein at least two of a router device of the first level of the router hierarchy and a router device of the second level of the router hierarchy are implemented in at least one physical router device.

10. The system as recited in claim 1, wherein at least one router device corresponds to the first and second levels of the router hierarchy.

11. A system for routing packets comprising:

a first set of router devices;

a second set of router devices for routing packet received from the first set of router devices, wherein each of the second set of router devices is dynamically correlated to a portion of destination addresses of incoming packets by a router management device based on a first subset of destination addresses of incoming packets, and wherein each portion of destination addresses is determined based on traffic volumes associated with each portion of the destination addresses; and

an external transit device for routing packets received from the second set of router devices via a plurality of routing paths, wherein each of the plurality of routing paths is dynamically correlated to a portion of destination addresses of incoming packets by the router management device based on a second subset of destination address of incoming packets, and wherein each portion of the destination addresses is determined based on traffic volumes associated with each portion of the destination addresses;

wherein the first set of router devices identify a router device from the second set of router devices correlated to the incoming packet based at least in part on a first subset of a destination address of the incoming packet; and

wherein the second set of router devices identify a routing path correlated to the incoming packet based at least in part on a second subset of a destination address of the incoming packet.

12. The system as recited in claim 11, wherein each router device of the second set of router devices is correlated to a portion of destination addresses of incoming packets based at least in part on a combination of an association of traffic volumes for destination addresses and an equal allocation of remaining destination addresses.

13. The system as recited in claim 11, wherein each router device of the second set of router devices is associated with a threshold number of destination addresses maintainable in a first memory of the router device, and wherein at least one router device of the second set of router devices is correlated with a portion of destination addresses containing more than the threshold number of destination addresses maintainable in the first memory of the at least one router device.

14. The system as recited in claim 11, wherein each router device of the second set of router devices is correlated to a portion of destination addresses of incoming packets based at least in part on an association of low traffic volumes for destination addresses.

15. The system as recited in claim 11, wherein a plurality of router devices of the second set of router devices are correlated to the same set portion of destination addresses.

16. The system as recited in claim 11, wherein first set of router devices are selected in accordance with one of random selection, round robin selection, hash selection and load balancing.

17. The system as recited in claim 11, wherein the destination address corresponds to an IP address.

18. The system as recited in claim 17, wherein the first subset of the IP address corresponds to the eight most significant bits of the IP address.

19. The system as recited in claim 18, wherein the first subset of the IP address corresponds to at least one of the sixteen or twenty four most significant bits of the IP address.

20. The system as recited in claim 11, wherein two or more of the first set of router devices correspond to a single physical router device.

21. The system as recited in claim 11, wherein two or more of the second set of router devices correspond to a single physical router device.

22. The system as recited in claim 11, wherein at least one of the set of first router devices and at least one of the second set of router devices correspond to a single physical router device.

23. The system as recited in claim 11, wherein at least one router device corresponds to at least one of the first and second set of router devices.

24. A method for routing packets comprising:

obtaining a routing request corresponding to a data packet received from a first communication network;

identifying a first router component of a first level of a router hierarchy, the first level of the router hierarchy comprising one or more router components;

forwarding the received data packet to the identified first router;

identifying a second router component of a second level of the router hierarchy, wherein the second level of the router hierarchy comprises one or more router components, wherein each of the one or more router components of the second level is dynamically associated with a portion of destination addresses of incoming data packets, and wherein each portion of destination addresses is determined based at least in part on traffic volumes associated with the portion of destination addresses and on a first subset of destination addresses;

forwarding the received data packet to the identified second router; and

identifying a transit path of a plurality of transit paths corresponding to a communication network, wherein each of the plurality of transit paths is dynamically associated with a portion of destination addresses of incoming data packets, and wherein each portion of destination addresses is determined based at least in part on traffic volumes associated with the portion of destination addresses and on a second subset of destination addresses;

wherein identifying the second router of the a second level of the router hierarchy is based at least in part on a first subset of a destination address of the received data packet; and

wherein identifying the transit path of the plurality of transit paths is based at least in part on of a second subset of a destination address of the incoming packet.

25. The method as recited in claim 24, wherein each router component of the second level of the router hierarchy is associated with a portion of destination addresses of incoming data packets based at least in part on a combination of an association of traffic volumes for destination addresses and an equal allocation of remaining destination addresses.

26. The method as recited in claim 24, wherein each router component of the second level of the router hierarchy is associated with a threshold number of destination addresses maintainable in a first memory of the router component, and wherein at least one router component from the second level of the router hierarchy is associated with a portion of destination addresses containing more than the threshold number of destination addresses maintainable in the first memory of the at least one router component.

27. The method as recited in claim 24, wherein each router component of the second level of the router hierarchy associated with a portion of destination addresses of incoming data packets is based at least in part on an association of low traffic volumes for destination addresses.

28. The method as recited in claim 24, a plurality of router component of the second level of the router hierarchy are associated with the same portion of destination addresses.

29. The method as recited in claim 24, wherein the one or more router components of the first level of the router hierarchy are selected in accordance with one of random selection, round robin selection, hash selection and load balancing.

30. The method as recited in claim 24, wherein the destination address corresponds to an IP address.

31. The method as recited in claim 24, wherein the transit path corresponds to an external transit component.

32. The method as recited in claim 24, wherein the transit path corresponds to a communication network.