DISTRIBUTED ROUTING ARCHITECTURE

• US 20110149965A1
• 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,325,730 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

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 distribution level router components maintain address routing information a first and second memory. 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 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 second level of the router hierarchy are associated with a first memory and a second memory for storing destination address information, the first memory associated with a faster access time than the second memory;

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

wherein the one or more router components corresponding to the second level of a router hierarchy identifies one or more router components from the one or more router components corresponding to third level of a router hierarchy based on a second subset of a destination address associated with the incoming packet, wherein the second subset of the destination address is greater than the first subset of the destination address; and

wherein the one or more router components attempt to identify the one or more router components from address information persisted in the first memory associated with the wherein the one or more router components and if the address information is not available in the first memory component, the one or more router components attempt to identify the one or more router components from address information persisted in the second memory component.

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 2, wherein the approximately equal portions of the first subset of destination addresses correspond to more address information than can be persisted in the first memory of the one or more router components corresponding to a second level of a router hierarchy.

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

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

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

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

8. The system as recited in claim 6, 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.

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

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

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

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

13. The system as recited in claim 1, the one or more router components corresponding to the first level of the router hierarchy are associated with a first memory and a second memory for storing destination address information, the first memory associated with a faster access time than the second memory and wherein the one or more router components corresponding to the first level of the router hierarchy attempt to identify the one or more router components from address information persisted in the first memory associated with the wherein the one or more router components and if the address information is not available in the first memory component, the one or more router components attempt to identify the one or more router components from address information persisted in the second memory component.

14. 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, the second set of logical router component associated with a physical router having a first memory and a second memory;

a third set of router logical components 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 such that address information provided by the router management component cannot be persisted entirely in the first memory component; and

wherein the second set of logical router components identify a router from the third set of logical router components 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 by examining address information in the first memory and if the address information is not persisted in the first memory component, by examining address information persisted in the second memory.

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

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

17. The system as recited in claim 14, 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.

18. The system as recited in claim 14, 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.

19. The system as recited in claim 14, 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.

20. The system as recited in claim 14, 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.

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

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

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

24. The system as recited in claim 23, 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.

25. The system as recited in claim 14, wherein each of the first set of logical router components correspond to a physical router component.

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

27. The system as recited in claim 14, wherein each of the second set of logical router components correspond to a physical router component.

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

29. The system as recited in claim 14, wherein each of the third set of logical router components correspond to a physical router component.

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

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

32. The system as recited in claim 14, wherein the router management component dynamically modifies the address information in the first memory component.

33. The system as recited in claim 14, wherein the first set of logical router component associated with a physical router having a first memory and a second memory.

34. The system as recited in claim 33, wherein the first set of logical router components identify a router from the second set of logical router components 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 by examining address information in the first memory and if the address information is not persisted in the first memory component, by examining address information persisted in the second memory.

35. A method for routing packets comprising of the one or more router components corresponding to the second set of logical router components.

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 third router corresponding to a third level of the router hierarchy, the third level of the router hierarchy corresponding to one or more router components, wherein identifying a third router corresponding to a third level of the router hierarchy corresponds to examining address information persisted in a first memory component associated with the identified second router and if the address information is not available, examining address information persisted in a second memory associated with the identified second router component;

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;

wherein address information provided by the router management component cannot be persisted entirely in the first memory component; and

wherein identifying a third router corresponding to a third level of the router hierarchy is based on a correlation of a second subset of a destination address associated with the incoming packet to the second selected router.

36. The method as recited in claim 35, 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.

37. The method as recited in claim 36, 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.

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

39. The method as recited in claim 36, 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.

40. The method as recited in claim 36, 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.

41. The method as recited in claim 36, 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.

42. The method as recited in claim 36, 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.

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

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

45. The method as recited in claim 35 further comprising dynamically modifying the address information provided by the router management component and persisted in the first memory component, wherein all the address information provided by the router management component cannot be persisted entirely in the first memory component.