Selective distribution of routing information

• US 9,912,593 B2
• Filed: 10/14/2016
• Issued: 03/06/2018
• 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): Moore, Ian N
• Assistant Examiner(s): Davis, Ronald h
• Application Number:
  US15/294,566
• Publication Number:
  US 20170230289A1
• Time in Patent Office: 508 Days
• 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 data store maintaining routing information of a first computing device, wherein the routing information is associated with a first hash tree, wherein the first hash tree includes a node structure comprising a plurality of leaf nodes and a plurality of parent nodes, wherein individual leaf nodes represent routing information values, and wherein individual parent nodes represent hash values generated according to content of the child nodes of the individual parent nodes;

a processor of the first computing device and in communication with the physical data store, the processor configured to;

receive a second hash tree, the second hash tree including a node structure matching the node structure of the first hash tree, wherein the second hash tree includes at least one parent node representing a hash value different from a hash value of a corresponding parent node of the first hash tree;

compare the first hash tree and the second hash tree to identify the at least one parent node of the second hash tree having the hash value different from the hash value of the corresponding parent node of the first hash tree;

identify a leaf node of the corresponding parent node of the first hash tree; and

replace the routing information value corresponding to the leaf node of the first hash tree with a routing information value represented by a leaf node of the at least one parent node of the second hash tree.

2. The system of claim 1, wherein the processor is further configured to receive a data packet and route the data packet based at least partly on the routing information value corresponding to the leaf node of the first hash tree.

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

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

subsequent to replacing the routing information value, select a third computing device to which to transmit the first hash tree; and

transmit the first hash tree to the third computing device.

5. The system of claim 4, wherein the third computing device is selected according to at least the replaced routing information value.

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

receive a third hash tree including a node structure matching the node structure of the first hash tree;

determine that a hash value represented by a root node of the third hash tree matches a hash value represented by a root node of the first hash tree; and

decline to further traverse the third hash tree.

7. The system of claim 1, wherein, to compare the first hash tree and the second hash tree to identify the at least one parent node of the second hash tree having the hash value different from the hash value of the corresponding parent node of the first hash tree, the processor is configured to:

determine that a hash value represented by a root node of the first hash tree does not match a hash value represented by a root node of the second hash tree;

traverse the first hash tree to identify a path including nodes whose hash values differ from corresponding nodes in the second hash tree; and

identify a final parent node of the path as the at least one parent node.

8. A computer-implemented method comprising:

obtaining a first hash tree representing routing information, wherein the first hash tree includes a node structure comprising a plurality of leaf nodes and a plurality of parent nodes, wherein individual leaf nodes represent routing information values, and wherein individual parent nodes represent hash values generated according to content of the child nodes of the individual parent nodes;

obtaining a second hash tree, the second hash tree including a node structure matching the node structure of the first hash tree, wherein the second hash tree includes at least one parent node representing a hash value different from a hash value of a corresponding parent node of the first hash tree;

identifying the at least one parent node of the second hash tree representing the hash value different from the hash value of the corresponding parent node of the first hash tree; and

replacing the routing information value corresponding to the leaf node of the first hash tree with routing information from the second hash tree.

9. The computer-implemented method of claim 8, wherein the routing information comprises at least a portion of a routing table.

10. The computer-implemented method of claim 8, wherein the first hash tree is a Merckle tree.

11. The computer-implemented method of claim 8 further comprising transmitting the first hash tree to another computing device.

12. The computer-implemented method of claim 8 further comprising:

receiving a third hash tree including a node structure matching the node structure of the first hash tree;

determining that a hash value represented by a root node of the third hash tree matches a hash value represented by a root node of the first hash tree; and

declining to traverse the third hash tree.

13. The computer-implemented method of claim 8, wherein comparing the first hash tree and the second hash tree to identify the at least one parent node of the second hash tree representing the hash value different from the hash value of the corresponding parent node of the first hash tree comprises:

determining that a hash value represented by a root node of the first hash tree does not match a hash value represented by a root node of the second hash tree;

traversing the first hash tree to identify a path including nodes whose hash values differ from corresponding nodes in the second hash tree; and

identifying a final parent node of the path as the at least one parent node.

14. The computer-implemented method of claim 8 further comprising determining that the second hash tree is authoritative over the first hash tree.

15. The computer-implemented method of claim 14 wherein determining that the second hash tree is authoritative over the first hash tree comprising associating a weight to the first hash tree and associating a weight to the second hash tree.

16. The computer-implemented method of claim 15, wherein the assigned weights are based on at least one of a previous history of computing devices associated with the respective hash trees, an amount of traffic processed by the computing devices, or an assigned priority of the computing devices.

17. The computer-implemented method of claim 8 further comprising receiving a data packet and routing the data packet based at least partly on the routing information value corresponding to the leaf node of the first hash tree.

18. Non-transitory computer-readable media including computer-executable instructions that, when executed by a computing system, cause the computing system to:

compare a first hash tree and a second hash tree, the first and second hash trees having a matching node structure that includes a plurality of leaf nodes and a plurality of parent nodes, the individual leaf nodes representing routing information values and the individual parent node representing hash values generated according to content of child nodes of the individual parent nodes, to identify at least one parent node of the second hash tree having a hash value different from a hash value of a corresponding parent node of the first hash tree; and

replace the routing information value corresponding to the leaf node of the first hash tree with a routing information value represented by a leaf node of the at least one parent node of the second hash tree.

19. The non-transitory computer-readable media of claim 18, wherein the computer-executable instructions further cause the computing system to transmit the first hash tree to another computing device.

20. The non-transitory computer-readable media of claim 18, wherein the computer-executable instructions further cause the computing system to:

receive a third hash tree including a node structure matching the node structure of the first hash tree;

determine that a hash value represented by a root node of the third hash tree matches a hash value represented by a root node of the first hash tree; and

decline to traverse the third hash tree.

21. The non-transitory computer-readable media of claim 18, wherein comparing the first hash tree and the second hash tree to identify the at least one parent node of the second hash tree representing the hash value different from the hash value of the corresponding parent node of the first hash tree comprises:

determining that a hash value represented by a root node of the first hash tree does not match a hash value represented by a root node of the second hash tree;

traversing the first hash tree to identify a path including nodes whose hash values differ from corresponding nodes in the second hash tree; and

identifying a final parent node of the path as the at least one parent node.

22. The non-transitory computer-readable media of claim 18, wherein the computer-executable instructions further cause the computing system to receive a data packet and route the data packet based at least partly on the routing information value corresponding to the leaf node of the first hash tree.