DISTRIBUTED ROUTING ARCHITECTURE

• US 20110149963A1
• Filed: 12/17/2009
• Published: 06/23/2011
• 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: Hamilton, James R., Judge, Alan M., O'Meara, David J., McGaugh, David J., Pietsch, Justin O.
• Granted Patent: US 8,331,370 B2
• Time in Patent Office: Days
• 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 comprising:

a router management component, executed on a computing device, for associating destination address information to a router hierarchy;

one or more router components corresponding to a first level of the router hierarchy, the first level of the router hierarchy for receiving an incoming packet for routing;

one or more router components 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 components corresponding to the first level of a router hierarchy;

wherein the one or more router components corresponding to the first level of a router hierarchy identifies one or more router components from the one or more router components corresponding to the second level of a router hierarchy based on a first subset of a destination address associated with the incoming packet, wherein the first subset is assigned by the router management component;

wherein each of the one or more router components corresponding to the second level of a router hierarchy correspond to portions of the first subset of the destination address associated with the incoming packet; and

wherein the one or more router components corresponding to the second level of a router hierarchy identifies an outgoing transit path based on a second subset of a destination address associated with the incoming packet, wherein the second subset is assigned by the router management component 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 components corresponding to the second level of a router hierarchy is allocated to correspond to approximately equal portions of the first subset of the destination addresses associated with the incoming packet.

3. The system as recited in claim 1, wherein the one or more router components corresponding to the second level of a router hierarchy is allocated to correspond to portions of the first subset of the destination address associated with the incoming packet based on traffic volumes attributed to the destination address.

4. The system as recited in claim 1, wherein the one or more router components 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.

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

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

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

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

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

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

11. The system as recited in claim 1, wherein at least a physical router component implements at least two of a first level router and a second level router.

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

13. A system for routing packets comprising:

a first set of logical router components for receiving an incoming packet for routing;

a second set of logical router components for routing packet received from the first set of router components;

an external transit component for routing packets received from the second set of router components

wherein the first set of logical router components identify a router from the second set of logical router components based on a correlation by a router management component of a subset of the destination address associated with the incoming packet to the selected router;

wherein each of the one or more router components corresponding to the second set of logical router components is allocated by the router management component to correspond to portions of the first subset of the destination address associated with the incoming packet; and

wherein the second set of logical router components identify a routing path identified by the external transit component based on a correlation by the router management component of a second subset of a destination address associated with the incoming packet to the second selected router.

14. The system as recited in claim 13, wherein the correlation of routers from the second set of router components is based on a substantially equal allocation of possible destination addresses.

15. The system as recited in claim 13, wherein the correlation of routers from the second set of logical router components is based on an association of traffic volumes for destination addresses.

16. The system as recited in claim 13, wherein the correlation of routers from the second set of logical router components is based on a combination of an association of traffic volumes for destination addresses and an equal allocation of remaining destination addresses.

17. The system as recited in claim 13, wherein each of the routers from the second set of logical router components are associated with a threshold number of destination addresses and wherein the correlation of routers from the second set of logical router components is based on allocation of a number greater than the threshold number of destination addresses associated with the second set of logical router components.

18. The system as recited in claim 13, wherein the correlation of routers from the second set of logical router components is based on an association of low traffic volumes for destination addresses.

19. The system as recited in claim 13, wherein the correlation of routers from the second set of logical router components includes an allocation of a plurality of routers for the same subset of destination addresses.

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

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

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

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

24. The system as recited in claim 13, wherein each of the first set of logical router components corresponds to a physical router component.

25. The system as recited in claim 13, wherein two or more of the first set of logical router components correspond to a single physical router component.

26. The system as recited in claim 13, wherein each of the second set of logical router components corresponds to a physical router component.

27. The system as recited in claim 13, wherein two or more of the second set of logical router components correspond to a single physical router component.

28. The system as recited in claim 13, wherein at least one of the set of first logical components and at least one of the second set of logical components correspond to a single physical router component.

29. The system as recited in claim 13, wherein at least one logical routing component corresponds to at least one of the first and second set of logical components.

30. 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 corresponding to a first level of a router hierarchy, the first level of the router hierarchy corresponding to one or more router components;

forwarding the received data packet to the identified first router;

identifying a second router corresponding to a second level of the router hierarchy, the second level of the router hierarchy corresponding to one or more router components;

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

identifying a transit path corresponding to a communication network;

wherein identifying the second router corresponding to a second level of the router hierarchy is based on a correlation of a subset of the destination address associated with the received data packet to the selected router; and

wherein identifying the transit path is based on a correlation of a second subset of a destination address associated with the incoming packet to the second selected router.

31. The method as recited in claim 30, wherein each of the one or more router components corresponding to the second level of the router hierarchy is allocated to correspond to portions of the first subset of the destination address associated with the incoming packet.

32. The method as recited in claim 31, wherein the correlation of routers from the second level of the router hierarchy is based on at least a substantially equal allocation of possible destination addresses.

33. The method as recited in claim 31, wherein the correlation of routers from the second level of the router hierarchy is based on an association of traffic volumes for destination addresses.

34. The method as recited in claim 31, wherein the correlation of routers from the second level of the router hierarchy is based on a combination of an association of traffic volumes for destination addresses and an equal allocation of remaining destination addresses.

35. The method as recited in claim 31, wherein each of the routers from the second level of the router hierarchy are associated with a threshold number of destination addresses and wherein the correlation of routers from the second level of the router hierarchy is based on allocation of a number greater than the threshold number of destination addresses associated with the second level of the router hierarchy.

36. The method as recited in claim 31, wherein the correlation of routers from the second level of the router hierarchy is based on an association of low traffic volumes for destination addresses.

37. The method as recited in claim 31, wherein the correlation of routers from the second set of router components includes an allocation of a plurality of routers for the same subset of destination addresses.

38. The method as recited in claim 30, wherein first set of router components are selected in accordance with one of random selection, round robin selection, hash selection and load balancing.

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

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

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