Method and system for managing data records on a computer network

• US 7,096,228 B2
• Filed: 03/27/2002
• Issued: 08/22/2006
• Est. Priority Date: 03/27/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jones, Michael B., Theimer, Marvin M.
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): Rayyan, Susan
• Application Number:
  US10/107,287
• Publication Number:
  US 20030187812A1
• Time in Patent Office: 1,609 Days
• Field of Search: 707/10, 707/100, 707/101, 707/200, 707/201, 707/203, 707/1, 707/104.1, 707/204, 709/219
• 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. A method for administering a plurality of data records on a computer network, each data record of the plurality of data records comprising information associated with a name of a plurality of names, the computer network comprising a plurality of servers, the method comprising:

providing, to each of a subset of the plurality of servers, a copy of a data record of the plurality of data records;

organizing the servers of the subset into a tree for disseminating updates to the data record, wherein one of the servers of the subset maintains a master copy of the data record and acts as the root of the tree, wherein the tree comprises a plurality of edges, each edge defining an update path between a pair of servers of the subset, the update path being usable to transmit an update of the data record from one server of the pair of servers to the other server of the pair of servers;

determining whether a first server of the subset is receiving an excessive number of requests for information from the data record;

based on the determining step;

identifying a second server of the plurality of servers that does not belong to the subset;

transmitting a copy of the data record from the first server to the second server so as to add the second server to the subset; and

adding a new edge to the tree, the new edge defining an new update path between the second server and the first server, the new update path being usable to transmit updates of the data record from the first server to the second server.

2. A computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 1.

3. The method of claim 1, wherein the second server is the server from whom the most requests for information from the data record have been received.

4. The method of claim 1, further comprising disseminating the update to the data record to the subset of the plurality of servers along the plurality of edges.

5. The method of claim 1, wherein the data record has an associated key number, wherein each of the plurality of servers has a node ID, and wherein the node ID of the server having the master copy of the record is closer to the key number than the node ID of any of the other servers of the plurality of servers.

6. The method of claim 1, wherein the servers of the subset have a parent-child relationship to one another with regard to updating their respective copies of the data record, and wherein each server of the subset has a node ID that is closer to the key number than any of its children.

7. In a computer network, a method for managing a data record for the computer network, the method comprising:

organizing a plurality of servers of the computer network into a tree, wherein one of the plurality of servers maintains a master copy of the data record and represents the 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 an excessive number of requests of information contained in the data record, the first server being in the plurality of servers that comprise the tree;

based on the determining step, 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; and

at the second sever, servicing a request for a lookup of a network name using the received copy of the data record.

8. A computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 7.

9. The method of claim 7, 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.

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

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

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

13. The method of claim 7, 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.

14. The method of claim 12, 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.

15. The method of claim 7, 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.

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

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

18. The method of claim 13, wherein each of the plurality of servers only performs the forwarding step when the server cannot service a request itself.

19. The method of claim 7, further comprising:

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

transmitting a response to the request directly to the client computer.

20. The method of claim 7, further comprising:

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

transmitting a response to the request to the client computer via a local server of the network, wherein the client computer accesses the computer network through the local server.

21. A method for administering a name service on a computer network, the computer network having a plurality of name servers, each name server having a node ID number, the method comprising:

organizing network names of the computer network into a plurality of directories according to the subject matter to which the network names relate;

at a first name server of the plurality of name servers;

receiving a request for a network name to be translated into a network address, wherein the request includes a key number, the key number being derived from the name of a directory of the plurality of directories, the directory storing information regarding the network address, wherein the network address corresponds to a node of the computer network that maintains information concerning the subject matter of the directory;

comparing the key number to the node ID number of the first name server;

determining whether there is a second name server whose node ID number is closer to the key number than the node ID number of the first name server; and

based on the determining step, forwarding the request to the second name server.

22. A computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 21.

23. The method of claim 21, wherein the determining step comprises whether there is a second name server whose node ID number is closer, either in terms of value or in terms of the number of shared digits, to the key number than the node ID number of the first name server.

24. In a computer network comprising a plurality of name servers that send and receive data to and from one another according to an overlay routing architecture that is superimposed on an IP routing architecture, a method of administering a name service in which network names of the computer network are organized into directories, a copy of each directory being stored on at least one of the plurality of name servers, a subset of the plurality of name servers being organized into a tree according to which ones maintain a copy of a particular directory, wherein one of the name servers of the tree maintains a master copy of the particular directory, the method comprising:

at a first name server of the name servers of the tree;

receiving a request for a lookup of a network name via the overlay routing architecture;

determining whether a copy of a directory that contains the network name is stored on the first name server;

if a copy of the directory is determined not to be stored on the first name server, forwarding the request to another name server via the overlay routing architecture, wherein the name server to which the request is sent may or may not be a part of the tree;

determining whether any of the directories maintained by the first name server contains a network name that is the subject of an excessive number of lookup requests; and

if it is determined that a directory maintained by the first name server contains a network name that is the subject of an excessive number of lookup requests, transmitting a copy of the directory to another name server in the tree according to the overlay routing architecture, wherein the name server to which the copy is sent was not previously a part of the tree but, upon receipt of the copy, becomes a part of the tree.

25. The method of claim 24, wherein, according to the overlay architecture;

each name server has a node ID, and each directory is stored on the name server whose node ID most closely matches a value derived from a hash of the name of the directory.

26. A system for administering a name service on a computer network, the system comprising:

a plurality of name servers, wherein a subset of the plurality of name servers is organized into a tree having a plurality of edges, wherein adjacent name servers of the tree share common edges, each name server having a copy of a data record stored thereon, wherein one of the name servers of the tree maintains a master copy of the data record and represents the root of the tree, the data record comprising information relating to a network name,

each name server of the tree executing one or more programs for receiving, from other name servers of the plurality of name servers, requests for information relating to network names,

each name server of the tree executing one or more programs for detecting whether requests for information relating to a particular network name and which is stored in the data record have exceeded a threshold rate,

each name server of the tree comprising;

means for determining the identity of a name server of the plurality of name servers that is to be added to the tree, and to which a copy of the particular directory will be sent based on results obtained by the one or more programs for detecting whether the requests for information have exceeded a threshold rate; and

means for obtaining the network address of a name server of the plurality of name servers to which a received request should be forwarded in the event that the name server that receives the request does not have a record containing the requested information, wherein the name server to which the received request should be forwarded may or may not be part of the tree.

27. The system of claim 26, wherein the determining means comprises a processor executing one or more programs for determining which of the other name servers of the plurality of name servers is forwarding the most requests for the information.

28. The system of claim 26, wherein the data record is topical directory having network addresses of nodes of the computer network, wherein the nodes maintain information related to a topic that is covered by the directory.

29. The system of claim 26, wherein each name server of the tree executes one or more programs for:

determining whether the rate of requests for information stored in the data record has fallen below a threshold rate; and

based on the determining step, deleting the copy of the data record maintained by the name server.

30. The system of claim 26, wherein the obtaining means comprises a leaf table having the IP addresses and node IDs of other name servers.

31. The system of claim 26, wherein the obtaining means comprises a routing table having the IP addresses and node IDs of other name servers that are close according to a proximity metric.

32. A method for administering a name service on a computer network, the computer network having a plurality of name servers, each name server having a node ID number, the method comprising:

organizing a plurality of network names of the name service into a plurality of directories, each network name corresponding to one or more computers on the network, each of the one or more computers maintaining information regarding a particular topic, wherein the network name corresponding to the one or more computers falls under a directory for the particular topic;

at a first name server of the plurality of name servers;

receiving, from a client computer, a request for a translation of a network name to a network address, wherein the request includes a key number that is derived from the name of a directory in which the network address is maintained by the name service;

passing the request to a second name server whose node ID is closer to the key number than the first name server'"'"'s node ID;

determining the amount of time that elapses between the execution of the passing step and the first name server receiving a response to the request;

comparing the elapsed amount of time to a threshold level; and

if the elapsed amount of time exceeds the threshold level, requesting a copy of the directory from the name service.

33. A computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 32.

34. The method of claim 32, wherein the passing step comprises passing the request to a second name server whose node ID is closer to the key number than the first name server'"'"'s node ID in terms of how many prefix digits the key number shares with the second name server'"'"'s node ID as compared to how name prefix digits the key number shares with the first name server'"'"'s node ID.

35. A method for administering a name service on a computer network, the computer network having a plurality of name servers, each name server having a node ID number, the method comprising:

organizing network names of the computer network into plurality of data records according to the subject matter to which the network names relate;

at a first name server of the plurality of name servers;

receiving a request for a network name to be translated into a value, wherein the request includes a key number, the key number being derived from the name of data record of the plurality of data records, the value being storied in the data record, wherein the value represents a property of a node of the computer network, wherein the node maintains information regarding the subject matter to which the network names of the data record relate;

comparing the key number to the node ID number of the first name server;

determining whether there is a second name server whose node ID number is closer, either in terms of value or in terms of the number of shared digits, to the key number than the node ID number of the first name server; and

based on the determining step, forwarding the request to the second name server.

36. A computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 35.

37. The method of claim 35, wherein the value is the network address of the node.

38. In a computer network, a method for managing a data record for the computer network, the method comprising:

organizing a plurality of servers of the computer network into a tree, wherein one of the plurality of servers maintains a master copy of the data record and represents the 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 an 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 an excessive number of requests for information contained in the data record, the first server being in the plurality of servers that comprise the tree; and

based on the determining step, 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;

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.

39. A computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 38.

40. The method of claim 38, 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.

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

42. The method of claim 38, 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.

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

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

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

46. The method of claim 38, further comprising:

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

transmitting a response to the request directly to the client computer.

47. The method of claim 38, further comprising:

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

transmitting a response to the request to the client computer via a local server of the network, wherein the client computer accesses the computer network through the local server.

48. In a computer network, a method for managing a data record for the computer network, the method comprising:

organizing a plurality of servers of the computer network into a tree, wherein the plurality of servers is a subset of all of the servers of the network, wherein each server of the network has a node ID, wherein one of the plurality of servers maintains a master copy of the data record and represents the 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 an excessive number of requests for information contained in the data record, the first server being in the plurality of servers that comprise the tree;

based on the determining step, 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;

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.

49. A computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 48.

50. The method of claim 48, 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.

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

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

53. The method of claim 48, 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.

54. The method of claim 48, wherein each of the plurality of servers only performs the forwarding step when the server cannot service a request itself.

55. The method of claim 48, further comprising:

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

transmitting a response to the request directly to the client computer.

56. The method of claim 48, further comprising:

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

transmitting a response to the request to the client computer via a local server of the network, wherein the client computer accesses the computer network through the local server.

57. In a computer network, a method for managing a data record for the computer network, the method comprising:

organizing a plurality of servers of the computer network into a tree, wherein one of the plurality of servers maintains a master copy of the data record and represents the 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 an excessive number of requests for information contained in the data record, the first server being in the plurality of servers that comprise the tree;

based on the determining step, 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;

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; and

at the second server, updating the additional copy of the record to reflect the information received from the first server.

58. A computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 57.

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

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

61. The method of claim 57, 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.

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

63. The method of claim 57, 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.

64. The method of claim 57, further comprising:

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

transmitting a response to the request directly to the client computer.

65. The method of claim 57, further comprising:

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

transmitting a response to the request to the client computer via a local server of the network, wherein the client computer accesses the computer network through the local server.