Selective distribution of routing information

• US 9,473,386 B1
• Filed: 12/27/2013
• Issued: 10/18/2016
• 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): Ton, Dang
• Assistant Examiner(s): Davis, Ronald H
• Application Number:
  US14/142,538
• Time in Patent Office: 1,026 Days
• Field of Search: None
• US Class Current: 1/1
• 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 system comprising:

a physical data store maintaining routing information of a first computing device; and

a processor in communication with the physical data store, the processor configured to;

receive, from a second computing device, routing information of the second computing device;

process the received routing information to identify a distinction between the received routing information of the second computing device and the maintained routing information of the first computing device;

determine, based at least in part on the identified distinction, a third computing device to receive information corresponding to the identified distinction between the received routing information of the second computing device and the maintained routing information of the first computing device; and

transmit the information corresponding to the identified distinction between the received routing information of the second computing device and the maintained routing information of the first computing device to the determined third computing device.

2. The system of claim 1, wherein the first computing device is included within a point of presence.

3. The system of claim 1, wherein the routing information comprises at least a portion of a routing table.

4. The system of claim 1, wherein the processor is further configured to update the routing information of the first computing device based at least in part on the identified distinction.

5. The system of claim 4, wherein the processor is configured to update the routing information of the first computing device based at least in part on generation of a forwarding information base.

6. The system of claim 1, wherein transmission of the information corresponding to the identified distinction includes making the updated current version of the routing tables available via a communication network.

7. The system of claim 1, wherein the processor is further configured to:

receive routing information of an additional computing device; and

process the received routing information of the additional computing device to identify a distinction between the received routing information of the additional computing device and the maintained routing information of the first computing device; and

wherein the third computing device is further determined based at least in part on the distinction between the received routing information of the additional computing device and the maintained routing information of the first computing device.

8. A computer-implemented method comprising:

as implemented by a first computing device based at least in part on specific computer-executable instructions,

receiving, at the first computing device, routing information of a second computing device;

processing the received routing information to identify a distinction between the received routing information of the second computing device and routing information maintained by the first computing device;

determining, based at least in part on the identified distinction, a third computing device to which to transmit an indication of the identified distinction between the received routing information of the second computing device and the routing information maintained by the first computing device; and

transmitting the indication of the identified distinction between the received routing information of the second computing device and the routing information maintained by the first computing device to the determined third computing device.

9. The computer-implemented method of claim 8, wherein the received routing information comprises a hash tree.

10. The computer-implemented method of claim 9, wherein the hash tree is representative of a routing table of the second computing device.

11. The computer-implemented method of claim 9, wherein processing the received routing information comprises comparing the hash tree within the received routing information with a hash tree representative of the routing information maintained by the first computing device.

12. The computer-implemented method of claim 8, wherein the identified distinction represents a modification to a current version of the routing information maintained by the first computing device.

13. The computer-implemented method of claim 8 further comprising updating the routing information of the first computing device based at least in part on the identified distinction.

14. Non-transitory computer-readable storage media including computer-executable instructions that, when executed by a processor of a first routing device, cause the first routing device to:

receive routing information of a second routing device;

process the received routing information to identify a distinction between the received routing information of the second computing device and routing information maintained by the first routing device;

determine, based at least in part on the identified distinction, a third routing device to which to transmit an indication of the identified distinction between the received routing information of the second computing device and the routing information maintained by the first routing device; and

transmit the indication of the identified distinction between the received routing information of the second computing device and the routing information maintained by the first routing device to the determined third routing device.

15. The non-transitory computer-readable storage of claim 14, wherein the third computing device is further determined based at least in part on a trust level associated with receipt of the routing information of the second computing device.

16. The non-transitory computer-readable storage of claim 14, wherein the third computing device is further determined based at least in part on at least one of time-based or geographic-based criteria.

17. The non-transitory computer-readable storage of claim 14, wherein the first computer-executable instructions further cause the first routing device to update the routing information of the first routing device based at least in part on the identified distinction.

18. The non-transitory computer-readable storage of claim 14, wherein the received routing information further comprises routing information of an additional computing device.

19. The non-transitory computer-readable storage of claim 14, wherein the first computer-executable instructions cause the processor to process implementing conflict resolution between the routing information of the second computing device and the routing information of the additional computing device by associating a weight to the routing information of the second computing device and associating a weight to the routing information of the additional computing device.

20. The computer-implemented method of claim 19, wherein the assigned weights are based on at least one of a previous history of the individual computing devices, an amount of traffic processed by the individual computing devices, or an assigned priority of the individual computing devices.