Routing cache for distributed hash tables
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
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. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
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. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification