Processing packet routing information

• US 8,619,780 B1
• Filed: 09/30/2010
• Issued: 12/31/2013
• Est. Priority Date: 09/30/2010
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Brandwine, Eric Jason, Sivasubramanian, Swaminathan, Marshall, Bradley E., Certain, Tate Andrew
• Primary Examiner(s): Wilson, Robert
• Assistant Examiner(s): Davis, Ronald H
• Application Number:
  US12/894,702
• Time in Patent Office: 1,188 Days
• Field of Search: None
• US Class Current: 370/392
• CPC Class Codes: H04L 12/44 Star or tree networks
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/025 Updating only a limited number of routers, e.g. fish-eye update
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/488 using root node determination
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7453 using hashing

Abstract

A distributed system for collecting and processing packet routing information is provided. A service provider, such as a content delivery network service provider, can maintain multiple Points of Presence (“POPs”). Routing computing devices associated with each POP can forward information about the packet routing information to a packet routing management component. The packet routing component can process the information provided by the various POPs. The packet routing component can then update, or otherwise modify, packet routing information used by one or more of the POPs. Accordingly, the packet routing management component can then selectively distribute the updated or modified packet routing information, including the distribution to all POPs, the targeted distribution to specific POPs and the creation of centrally accessible routing information.

Claims

1. A method for managing routing information comprising:

obtaining routing information from one or more points of presence, the routing information corresponding to routing tables maintained by the points of presence and a hash tree representative of the routing tables;

processing the hash tree representative of the routing tables provided by the one or more points of presence to identify modifications to a current version of routing tables maintained for each of the one or more points of presence;

updating the current version of the routing tables maintained for each of the points of presence based on the routing information provided by the one or more points of presence, the updated current version indicative of the identified modifications; and

in response to identification of the modifications to the current version of routing tables;

determining, based at least in part on the identified modifications, at least one additional point of presence to which to distribute the updated current version of the routing tables indicative of the identified modifications; and

selectively distributing the updated current version of the routing tables indicative of the identified modifications to the determined at least one additional point of presence.

2. The method as recited in claim 1, wherein processing the hash tree representative of the routing tables includes comparing the hash tree representative of the routing tables provided by the one or more points of presence with a hash tree representative of the current version of the routing tables maintained for each of the one or more points of presence.

3. The method as recited in claim 1 wherein obtaining routing information from one or more points of presence comprises obtaining the routing information from a plurality of points of presence.

4. The method as recited in claim 3 further comprising implementing conflict resolution by associating a weight to the routing information provided by each of the one or more points of presence.

5. The method as recited in claim 4, wherein the weight is based at least one of previous history, amount of traffic processed by the points of presence, and an assigned priority.

6. The method as recited in claim 1, wherein updating the current version of the routing tables includes the generation of a forwarding information base.

7. The method as recited in claim 1, further comprising distributing the updated current version of the routing tables to the one or more points of presence.

8. The method as recited in claim 1, further comprising distributing the updated current version of the routing tables to a subset of the one or more points of presence.

9. The method as recited in claim 1, wherein selectively distributing the updated current version of the routing tables includes making the updated current version of the routing tables available via a communication network.

10. The method as recited in claim 1, wherein selectively distributing the updated current version of the routing tables includes selectively distributing the updated current version of the routing tables based on weighing factors associated with a trust level associated with the receipt of the routing information from the one or more points of presence.

11. The method as recited in claim 1, wherein selectively distributing the updated current version of the routing tables includes selectively distributing the updated current version of the routing tables based on weighing factors associated with at least one of time-based or geographic-based criteria associated with the one or more points of presence.

12. A method for managing routing information comprising:

obtaining routing information from one or more computing devices, the routing information corresponding to routing tables maintained by the one or more computing devices;

processing the routing information provided by the one or more computing devices to identify modifications to a current version of routing tables;

updating the current version of the routing tables based on the routing information provided by the one or more computing devices, the updated current version indicative of the identified modifications; and

in response to identification of the modifications to the current version of routing tables;

identifying, based at least in part on the identified modifications, at least a one additional computing device that should receive the updated current version of the routing tables indicative of the identified modifications; and

distributing the updated current version of the routing tables to the identified at least one additional computing device.

13. The method as recited in claim 12 further comprising obtaining information representative of the routing information from the one or more computing devices.

14. The method as recited in claim 13 further comprising comparing the information representative of the routing information with information representative of the current version of the routing tables.

15. The method as recited in claim 12 wherein obtaining routing information from one or more computing devices comprises obtaining the routing information from a plurality of computing devices.

16. The method as recited in claim 15 further comprising providing conflict resolution for the routing information provided by the plurality of computing devices.

17. The method as recited in claim 16, wherein the conflict resolution includes associating a weight with each of the plurality of computing devices.

18. The method as recited in claim 17, wherein the weight is based at least one of previous history associated with reported changes by a specific computing device, an amount of traffic processed by a respective computing device, and an assigned priority.

19. The method as recited in claim 12, wherein updating the current version of the routing tables includes the generation of a forwarding information base.

20. The method as recited in claim 12 further comprising distributing the updated current version of the routing table to the one or more computing devices.

21. The method as recited in claim 12 further comprising distributing the updated current version of the routing tables to a subset of the one or more computing devices.

22. The method as recited in claim 12, wherein distributing the updated current version of the routing tables to the identified at least one additional computing device includes making the updated current version available via a communication network.

23. The method as recited in claim 12, wherein the one or more computing devices correspond to a point of presence.

24. The method as recited in claim 12, wherein identifying at least one additional computing device that should receive the updated current version of the routing tables includes identifying the at least one computing device that should receive the updated current version of the routing tables based on weighing factors associated with a trust level, time-based criteria and geographic-based criteria associated with the one or more computing devices.

25. A system for managing routing information comprising:

a first network point of presence, wherein the first network point of presence transmits first routing information corresponding to routing tables maintained by one or more computing devices associated with the first network point of presence;

a second network point of presence associated with a content delivery network service provider, wherein the second network point of presence transmits second routing information corresponding to routing tables maintained by one or more computing devices associated with the second network point of presence; and

one or more computing devices configured to implement a routing information management component for;

obtaining routing information from the first and second point of presence, the routing information corresponding to routing tables associated with the first and second points of presence;

processing the routing information provided by the first and second points of presence to identify modifications to a current version of routing tables;

updating the current version of the routing tables based on the routing information provided by the first and second points of presence, the updated current version indicative of the identified modifications; and

in response to identification of the modifications to the current version of routing tables;

determining, based at least in part on the identified modifications, at least one additional point of presence to which to distribute the updated current version of the routing tables indicative of the identified modifications; and

selectively distributing the updated current version of the routing tables indicative of the identified modifications to the at least one additional point of presence.

26. The system as recited in claim 25, wherein the first and second points of presence transmit information representative of the routing information.

27. The system as recited in claim 26, wherein the routing information management component compares information representative of the routing information for the first and second points of presence with information representative of the current version of the routing tables.

28. The system as recited in claim 25, wherein the routing information management component performs conflict resolution for the routing information provided by the first and second points of presence.

29. The system as recited in claim 28, wherein the conflict resolution includes associating a weight with each of the first and second points of presence.

30. The system as recited in claim 29, wherein the weight is based at least one of previous history associated with reported changes by a specific computing device, an amount of traffic processed by a respective computing device, and an assigned priority.

31. The system as recited in claim 25, wherein the routing information management component updates the current version of the routing tables by generating a forwarding information base.

32. The system as recited in claim 25, wherein the routing information management component distributes the updated current version of the routing table to the first and second points of presence.

33. The system as recited in claim 25, wherein the routing information management component distributes the updated current version of the routing table to a subset of the first and second points of presence.

34. The system as recited in claim 25, wherein the routing information management component distributes the updated current version available via a communication network.

35. The system as recited in claim 25, wherein the routing information management component selectively distributes the updated current version of the routing tables based on weighing factors associated with a trust level associated with the receipt of the routing information from the first and second points of presence.

36. The system as recited in claim 25, wherein the routing information management component selectively distributes the updated current version of the routing tables based on weighing factors associated with at least one of time-based or geographic-based criteria associated with the first and second points of presence.