Routing cache for distributed hash tables

• US 7,808,971 B2
• Filed: 07/01/2005
• Issued: 10/05/2010
• Est. Priority Date: 07/01/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Miller, John L.
• Primary Examiner(s): Juntima; Nittaya
• Application Number:
  US11/172,686
• Publication Number:
  US 20070002869A1
• Time in Patent Office: 1,922 Days
• Field of Search: 370/351, 370/395.32, 370/400, 709/238, 709/243
• US Class Current: 370/351
• 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 distributed hash table (DHT) query messages in a DHT that is distributed among nodes, including the node, on a data network, where each of the nodes has an assigned node identifier (nodeID) and an address on the data network, wherein the routing table comprises entries, and wherein an entry comprises a node'"'"'s nodeID and network address, the method comprising:

receiving the DHT query messages from others of the nodes, wherein 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 nodeIDs placed therein, wherein the nodeID-address pairings are from the received DHT query messages, the method being performed by at least one of the nodes.

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 comprises 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 method of managing a routing cache utilized in routing distributed hash table (DHT) routing messages regarding a DHT that is distributed across a network, the method comprising:

replacing cache entries in the routing cache with node identifiers (nodeIDs) and corresponding network addresses obtained from the DHT routing messages being routed within the distributed hash table, wherein the cache entries are replaced such that the routing cache has a substantially random distribution of nodeIDs, and by placing the nodeIDs and corresponding network addresses as pairs in the routing cache without structuring the routing cache according to the nodeIDs placed therein, the method being performed by a node on the network.

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

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

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

11. A method according to claim 7, further comprising routing the DHT routing messages within the distributed hash table by comparing prefixes of destination keys in the DHT routing messages with prefixes of nodeIDs in the routing cache.

12. A volatile or non-volatile computer-readable medium storing computer executable instructions for enabling a computing device to perform a method according to claim 7.

13. A method according to claim 7, wherein cache entries are randomly selected for replacement.

14. A computing device comprising:

a portion of a distributed hash table (DHT);

a routing table utilized in routing DHT queries regarding the distributed hash table, wherein the routing table is utilized to link 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 operable to route the DHT queries by selecting node identifiers (nodeIDs) in the routing table based on their numerical closeness to nodeIDs in the routing queries; and

a routing table management unit operable to manage the routing table, the managing including replacing table entries without structuring the routing table based on nodeIDs placed therein, wherein the nodeIDs and corresponding network addresses placed in the routing table are obtained from the DHT queries.

15. A computing device according to claim 14, wherein a substantial portion of the replaced table entries are randomly selected for replacement.

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

17. A computing device according to claim 14, 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.

18. A computing device according to claim 14, wherein the routing unit routes the DHT queries to nodes with entries in the routing table whose nodeIDs are numerically closest to keys to which the DHT queries are directed.