Routing cache for distributed hash tables

• US 20070002869A1
• Filed: 07/01/2005
• Published: 01/04/2007
• Est. Priority Date: 07/01/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Miller, John
• Granted Patent: US 7,808,971 B2
• Time in Patent Office: Days
• US Class Current: 370/395.320
• 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 61/4547 for personal communications, i.e. using a personal identifier
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053

Abstract

In a distributed hash table (DHT), a participating node has a routing cache associating nodes in the DHT with their respective network addresses. Messages can be routed with the routing table using prefix-matching or numerical-closeness without requiring rigid structuring of the node'"'"'s cache. Entries in the cache may be replaced using routing information obtained from en route messages. Entries in the routing cache may be replaced without regard for the nodeIDs in or entering the routing cache, and/or without structuring the routing cache according to the nodeIDs placed therein. Cache entries may be replaced randomly.

Claims

1. A method of managing a routing table that a node uses to route query messages in a distributed hash table (DHT) that is distributed among nodes on a data network, where each node has an assigned node identifier (nodeID) and an address on the data network, where the routing table comprises entries, and where an entry comprises a node'"'"'s nodeID and network address (define network address broadly in spec), the method comprising:

receiving DHT query messages from nodes, where a DHT query message comprises a target key and one or more nodeID-network address pairings of one or more nodes that previously sent the DHT query message via the data network;

selecting entries in the routing table based on numerical closeness of the entries'"'"' nodeIDs to the target key and using the network addresses of the selected entries to route the DHT query messages to the nodes corresponding to the selected entries; and

maintaining the routing table by placing nodeID-address pairings therein without structuring the routing table according to the nodeID placed therein, where the nodeID-address pairings are from the received DHT query messages.

2. A method according to claim 1, wherein the placing comprises replacing entries in the routing table, where the entries to be replaced are determined without regard for their nodeIDs.

3. A method according to claim 1, wherein the nodeID-address pairings placed in the routing table are randomly placed within the routing table.

4. A method according to claim 1, wherein the placing comprising replacing entries in the routing table, where the entries to be replaced are determined without regard for numerical closeness of their nodeIDs to the nodeID of the node maintaining the routing table.

5. A method according to claim 1, wherein the nodeID-address pairings placed in the routing table are placed in the routing table without regard for their nodeIDs.

6. A method according to claim 1, wherein the selecting entries in the routing table based on numerical closeness of the entries'"'"' nodeIDs to the target key comprises comparing prefixes of the target key with prefixes of entry nodeIDs.

7. A computer-readable medium storing information for enabling a computing device to perform a method according to claim 1.

8. A method of managing a routing cache for routing messages in a distributed hash table that is distributed across a network, the method comprising:

replacing cache entries in the routing cache with nodeIDs and corresponding network addresses obtained from communications being routed within the distributed hash table, where the cache entries are replaced such that the cache has a substantially random distribution of nodeIDs.

9. A method according to claim 8, wherein the replaced cache entries are replaced without regard for the nodeIDs therein.

10. A method according to claim 8, wherein the cache entries are replaced without regard for the nodeIDs with which they are replaced.

11. A method according to claim 8, wherein routing cache is not structured according to the nodeIDs therein.

12. A method according to claim 8, further comprising routing the communications within the distributed hash table by comparing prefixes of destination keys in the communications with prefixes of nodeIDs in the routing cache.

13. A volatile or non-volatile computer-readable medium storing information for enabling a computing device to perform a method according to claim 8.

14. A method according to claim 8, wherein cache entries are randomly selected for replacement.

15. A computing device comprising:

a portion of a distributed hash table;

a routing table for routing queries in the distributed hash table, where the routing table links the computing device to an overlay network of nodes participating in the distributed hash table via a data network, where the overlay network is layered above the data network; and

a routing unit routing the distributed hash table queries by selecting nodeIDs in the routing table based on their numerical closeness to nodeIDs in the routing queries; and

a routing table management unit managing the routing table by replacing table entries without structuring the routing table based on nodeIDs placed therein.

16. A computing device according to claim 15, wherein substantially of the replaced table entries are randomly selected for replacement.

17. A computing device according to claim 15, wherein the routing table is maintained with a substantially random distribution of nodeIDs.

18. A computing device according to claim 15, wherein the table entries are replaced without regard for numerical closeness of a nodeID of the computing device to nodeIDs being placed or replaced in the routing table.

19. A computing device according to claim 18, wherein nodeIDs and correspond network addresses placed in the routing table are obtained from the queries.

20. A computing device according to claim 15, where the routing unit routes the queries to nodes with entries in the routing table whose nodeIDs are numerically closest to keys to which the queries are directed.