Method and system for managing data records on a computer network

• US 7,640,253 B2
• Filed: 02/22/2005
• Issued: 12/29/2009
• Est. Priority Date: 03/27/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Marvin M. Theimer, Michael B. Jones
• Inventors: Jones, Michael B., Theimer, Marvin M.
• Primary Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US11/063,140
• Publication Number:
  US 20050154768A1
• Time in Patent Office: 1,771 Days
• Field of Search: 707/10, 707100-103, 707 2- 5, 707/201, 709/203
• US Class Current: 1/1
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 61/4552 Lookup mechanisms between a plurality of directories; Synchronisation of directories, e.g. metadirectories
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method and system for managing data records on a computer network is described, in which copies of data records are distributed among various servers in a hierarchical tree structure, and in which servers that experience an excessive number of requests for a particular data record transmit replicas of that data record to other servers to distribute the load.

Claims

1. In an overlay network, a method for managing a data record, the method comprising:

organizing a plurality of servers of the overlay network into a tree, wherein any one of the plurality of servers is capable of maintaining a master copy of the data record and representing a root of the tree, wherein each of the other servers of the plurality of servers maintains a copy of the data record, wherein the plurality of servers transmits updates to one another based on the tree, the tree comprising a plurality of edges, each edge defining a path for updates to the data record between a pair of the plurality of servers;

determining whether a first server is receiving requests for information contained in the data record at an excessive request rate, the first server being in the plurality of servers that comprise the tree; and

in response to determining that requests for information contained in the data record are being received at an excessive request rate, transmitting an additional copy of the data record to a second server that did not previously have a copy of the data record, thereby adding the second server to the tree.

2. A computer-readable storage medium having stored thereon computer-executable instructions that, when executed by a computing device, perform the method of claim 1.

3. The method of claim 1, further comprising:

at the first server;

receiving notification of a change in the record; and

transmitting information regarding the change from the first server to the second server.

4. The method of claim 3, further comprising, at the second server, updating the additional copy of the record to reflect the information received from the first server.

5. The method of claim 4, wherein the determining step comprises determining whether the first server has received an excessive number of requests over a defined period of time.

6. The method of claim 1, wherein the determining step comprises determining whether the first server has received an excessive number of requests over a defined period of time.

7. The method of claim 1, wherein the plurality of servers is a subset of all of the servers of the network, and wherein each server of the network has a node ID, the method further comprising:

at a server of the plurality of servers, receiving a request for information contained in the data record;

forwarding the request to another server of the network along with a key number, the key number being mathematically derived from the name of the record that is the subject of the request;

at each server of the network that receives a forwarded request, determining whether there is at least one other server whose node ID is closer in value to the key number than the node ID of the server that received the request; and

if it is determined that there is at least one other server whose node ID is closer in value to the key number than the node ID of the server that received the request, transmitting the request to the other server.

8. The method of claim 1, further comprising, at the second server, servicing a request for a lookup of a network name using the received copy of the data record.

9. The method of claim 1, wherein the data record is a directory that includes a plurality of network name records, each network name record comprising information associated with a name of a node on the network.

10. The method of claim 9, wherein the information associated with the name of the node on the network comprises the IP address of the node.

11. The method of claim 9, wherein the directory represents an informational topic, and wherein the node maintains information that relates to the informational topic.

12. The method of claim 1, further comprising:

at one of the plurality of servers, receiving, from a client computer of an underlying network independent of the overlay network, a request for information contained in the data record; and

transmitting a response to the request to the client computer through the underlying network.

13. A computerized system for managing a data record comprising an overlay network, the overlay network comprising a plurality of servers, the plurality of servers comprising:

a first server including a processing unit and a memory, the first server configured to, at least;

participate in a tree for propagating data records;

maintain a first copy of the data record;

receive requests for information contained in the data record;

determine that the requests are being received at an excessive request rate;

in response to determining that requests for information contained in the data record are being received at an excessive request rate, add a second server to the tree for propagating data records; and

transmit an additional copy of the data record to the second server; and

the second server including a processing unit and a memory, the second server configured to, at least;

participate in at least one tree for propagating data records;

receive at least one of a plurality of copies of the data record; and

maintain the at least one of the plurality of copies of the data record.

14. The system of claim 13, wherein:

the first server is further configured to, at least;

receive notification of a change to the data record; and

transmit information regarding the change to the second server; and

the second server is further configured to, at least;

receive information regarding the change to the data record; and

update the at least one of the plurality of copies of the data record.

15. The system of claim 13, wherein each of the plurality of servers in the overlay network is further configured to, at least:

maintain a node ID;

calculate a cryptographic hash of a name of the data record; and

determine a logical distance between the cryptographic hash and the node ID of at least one of the plurality of servers in the overlay network.

16. The system of claim 13, wherein the second server is further configured to, at least, service a request for a lookup of a network name using the at least one of the plurality of copies of the data record.

17. The system of claim 13, wherein the data record is a directory that includes a plurality of network name records, each network name record comprising information associated with a name of a node on the network.

18. A computerized system for managing a data record comprising a server including a processing unit and a memory, the server configured to, at least:

participate in an overlay network;

participate in a tree for propagating data records;

maintain a first copy of the data record;

receive requests for information contained in the data record;

determine that the requests are being received at an excessive request rate;

in response to determining that requests for information contained in the data record are being received at an excessive request rate, add a further server participating in the overlay network to the tree for propagating data records; and

transmit an additional copy of the data record to the further server.

19. The system of claim 18, wherein each server participating in the overlay network is further configured to, at least:

maintain a node ID;

calculate a cryptographic hash of a name of the data record; and

determine a logical distance between the cryptographic hash and the node ID of at least one server participating in the overlay network.

20. The system of claim 18, wherein the data record is a directory that includes a plurality of network name records, each network name record comprising information associated with a name of a node on the network.