Method and apparatus for providing scalable resource discovery

• US 7,177,867 B2
• Filed: 09/12/2002
• Issued: 02/13/2007
• Est. Priority Date: 10/23/2000
• Status: Expired due to Fees

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Dawson, Steven M., Stringer-Calvert, David W. J., Lincoln, Patrick D.
• Primary Examiner(s): Ali, Mohammad
• Application Number:
  US10/242,285
• Publication Number:
  US 20030074402A1
• Time in Patent Office: 1,615 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-205, 709220-224, 709/203, 709/226
• US Class Current: 1/1
• CPC Class Codes: G06F 2209/505 Clust
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

A scalable method and architecture for efficiently locating desired resources within a network containing a plurality of server nodes, each of which hosts or otherwise provides access to a subset of a global resource set. In one aspect of the invention, each of the server nodes are assigned membership in at least two sets, an “announce” set and a “request” set.

Claims

1. A method for facilitating access to a plurality of resources distributed across an electronic network comprising a plurality of interconnected server nodes, each of the resources being associated with at least one corresponding server node, said method comprising the steps of:

a) assigning to each of the server nodes membership in at least one of a plurality of announce sets, each of said plurality of announce sets comprising two or more of said server nodes who advertise an availablity of associated resources to each other;

b) assigning to each of the server nodes membership in at least one of a plurality of request sets, each of said plurality of request sets comprising two or more of said server nodes who query each other for an availability of one or more associated resources, where each of the request sets intersects with at least one of the announce sets thereby forming a logical grid;

c) receiving a join request from a new server node for joining the network by a member server node of the network; and

d) applying information stored within said member server node to determine how said new server node will be assigned membership to said network.

2. The method of claim 1, further comprising the step of:

c) publishing a resource of a server node that has not been assigned membership in one of said plurality of announce sets or one of said plurality of request sets.

3. The method of claim 1 wherein said applying step d) applies information relating to sizes of said plurality of announce sets and request sets within the network to determine a proper set for said new server node to join.

4. The method of claim 1 further comprising the step of:

e) splitting one of said plurality of request sets into two request sets; and

f) assigning said new server node with membership to one of said newly split request sets.

5. The method of claim 1 further comprising the step of:

e) splitting one of said plurality of announce sets into two announce sets; and

f) assigning said new server node with membership to one of said newly split announce sets.

6. The method of claim 1 further comprising the step of:

f) forwarding said join request to a server node that serves as a publish peer of said member server node.

7. The method of claim 6, further comprising the step of:

g) forwarding request set information or announce set information to said new server node.

8. The method of claim 7, wherein said set information comprises identification of other server nodes within the set and identification of the set'"'"'s publish peers.

9. The method of claim 7, further comprising the step of:

h) receiving a request from said new server node directed to each node in the set to provide a random node in that node'"'"'s set for allowing said new server node to form its own set of publish peers.

10. The method of claim 1, wherein said assigning steps a) and b) assign server nodes such that a ratio of the number announce sets and the number of request sets is held within a target ratio.

11. The method of claim 10, wherein said target ratio varies dynamically depending on a ratio of announce to request actions.

12. The method of claim 1, further comprising the steps of:

c) detecting loss of membership of a server node within a first request set of said plurality of request sets; and

d) forwarding a lookup request that is unanswerable by said first request set to at least a second request set of said plurality of request sets, where an answer provided by said second request set is appended to said first request set.

13. The method of claim 1, further comprising the steps of:

c) detecting loss of membership of a leaving server node within an announce set of said plurality of announce sets by detecting a failure to respond to a publish request; and

d) determining a replacement publish peer server node for said leaving server node'"'"'s set by querying members of its own request set.

14. The method of claim 1, further comprising the step of:

c) splitting one of said plurality of request sets into a first request set and a second request set.

15. The method of claim 14, further comprising the step of:

d) forwarding a lookup request that is unanswerable by said first request set to at least said second request set, where an answer provided by said second request set is added to said first request set.

16. The method of claim 1, further comprising the step of:

c) splitting one of said plurality of announce sets.

17. The method of claim 1, further comprising the step of:

c) merging a first request set of said plurality of request sets into another request set of said plurality of request sets.

18. The method of claim 1, wherein said merging step c) treats each of a plurality of server nodes belonging to said first request set as a new server node joining the network.

19. The method of claim 1, further comprising the step of:

c) merging a first announce set of said plurality of announce sets into another announce set of said plurality of announce sets.

20. The method of claim 19, wherein said merging step c) treats each of a plurality of server nodes belong to said first announce set as a new server node joining the network.

21. The method of claim 1, further comprising the step of:

c) assigning a searching order to said server nodes of one of said request sets.

22. The method of claim 21, wherein said searching order is assigned to achieve a target search time.

23. The method of claim 22, wherein said target search time is a constant search time.

24. The method of claim 22, wherein said target search time is represented approximately by log(n), where n represents a number of server nodes in the network.

25. The method of claim 21, wherein said searching order is defined into a plurality of subsets of an ordering range, where each server node within a set is responsible for one of said subsets of the ordering range.

26. The method of claim 25, wherein said subsets of an ordering range are of equal size or of differing sizes.

27. The method of claim 1, further comprising the step of:

c) providing resource announcements to more than one announce set.

28. The method of claim 1, further comprising the step of:

c) providing resource requests to more than one request set.

29. The method of claim 1, further comprising the step of:

c) providing resource announcement that comprises an equivalence function.

30. The method of claim 29, wherein said equivalence function is representative of a description of a software agent'"'"'s capabilities.

31. The method of claim 30, wherein a requested resource is satisfied by delegation-based computing where a collection of agents are invoked to satisfy said request.

32. The method of claim 31, wherein said requested resource does not exist within the network but a composite response by said collection of agents satisfy the requested resource.

33. The method of claim of 3, wherein said requested resource comprises a web service.

34. The method of claim 1, further comprising the step of:

c) providing resource announcement that comprises a declarative functional language.

35. The method of claim 1, wherein said assigning steps account for physical geographic location of said server nodes.

36. The method of claim 35, wherein said physical geographic location of said server nodes is used to organize server nodes into a plurality of grids.

37. The method of claim 1, further comprising the steps of:

c) repeating steps a) and b) to produce two separate peer-grid networks; and

d) applying a meta-process for directing queries between said peer-grid networks.

38. The method of claim 1, further comprising the steps of:

c) distributing publishing content of a server node to more than one other server node within each of said announce sets.

55. The apparatus of claim 3, further comprising:

means for merging a first request set of said plurality of request sets into another request set of said plurality of request sets.

56. The apparatus of claim 55, wherein said merging means treats each of a plurality of server nodes belonging to said first request set as a new server node joining the network.

39. An apparatus for facilitating access to a plurality of resources distributed across an electronic network comprising a plurality of interconnected server nodes, each of the resources being associated with at least one corresponding server node, said system comprising:

means for assigning to each of the server nodes membership in at least one of a plurality of announce sets, each of stud plurality of announce sets comprising two or more of said server nodes who advertise an availability of associated resources to each other;

means for assigning to each of the server nodes membership in at least one of a plurality of request sets, each of said plurality of request sets comprising two or more of said server nodes who query each other for an availability of one or more associated resources, where each of the request sets intersects with at least one of the announce sets thereby forming a logical grid;

means for receiving a join request from a new server node for ioining the network by a member server node of the network; and

means for applying information stored within said member server node to determine how said new server node will be assigned membership to said network.

40. The apparatus of claim 39, further comprising:

means for publishing a resource of a server node that has not been assigned membership in one of said plurality of announce sets or one of said plurality of request sets.

41. The apparatus of claim 39, wherein said applying means applies information relating to sizes of said plurality of announce sets and request sets within the network to determine a proper set for said new server node to join.

42. The apparatus of claim 39, further comprising:

means for splitting one of said plurality of request sets into two request sets; and

means for assigning said new server node with membership to one of said newly spilt request sets.

43. The apparatus of claim 39, further comprising:

means for splitting one of said plurality of announce sets into two announce sets; and

means for assigning said new server node with membership to one of said newly split announce sets.

44. The apparatus of claim 39, further comprising:

means for forwarding said join request to a server node that serves as a publish peer of said member server node.

45. The apparatus of claim 44, further comprising:

means for forwarding request set information or announce set information to said new server node.

46. The apparatus of claim 45, wherein said set information comprises identification of other server nodes within the set and identification of the set'"'"'s publish peers.

47. The apparatus of claim 45, further comprising:

means for receiving a request from said new server node directed to each node in the set to provide a random node in that node'"'"'s set for allowing said new server node to form its own set of publish peers.

48. The apparatus of claim 39, wherein said assigning means assign server nodes such that a ratio of the number announce sets and the number of request sets is held within a target ratio.

49. The apparatus of claim 48, wherein said target ratio varies dynamically depending on a ratio of announce to request actions.

50. The apparatus of claim 39, further comprising:

means for detecting loss of membership of a server node within a first request set of said plurality of request sets; and

means for forwarding a lookup request that is unanswerable by said first request set to at least a second request set of said plurality of request sets, where an answer provided by said second request set is appended to said first request set.

51. The apparatus of claim 39, further comprising:

means for detecting loss of membership of a leaving server node within an announce set of said plurality of announce sets by detecting a failure to respond to a publish request; and

means for determining a replacement publish peer server node for said leaving server node'"'"'s set by querying members of its own request set.

52. The apparatus of claim 39, further comprising:

means for splitting one of said plurality of request sets into a first request set and a second request set.

53. The apparatus of claim 52, further comprising:

means for forwarding a lookup request that is unanswerable by said first request set to at least said second request set, where an answer provided by said second request set is added to said first request set.

54. The apparatus of claim 39, further comprising:

means for splitting one of said plurality of announce sets.

57. The apparatus of claim 39, further comprising:

means for merging a first announce set of said plurality of announce sets into another announce set of said plurality of announce sets.

58. The apparatus of claim 57, wherein said merging means treats each of a plurality of server nodes belong to said first announce set as a new server node joining the network.

59. The apparatus of claim 39, further comprising:

means for assigning a searching order to said server nodes of one of said request sets.

60. The apparatus of claim 59, wherein said searching order is assigned to achieve a target search time.

61. The apparatus of claim 60, wherein said target search time is a constant search time.

62. The apparatus of claim 60, wherein said target search time is represented approximately by log(n), where n represents a number of server nodes in the network.

63. The apparatus of claim 59, wherein said searching order is defined into a plurality of subsets of an ordering range, where each server node within a set is responsible for one of said subsets of the ordering range.

64. The apparatus of claim 63, wherein said subsets of an ordering range are of equal size or of differing sizes.

65. The apparatus of claim 39, further comprising:

means for providing resource announcements to more than one announce set.

66. The apparatus of claim 39, further comprising:

means for providing resource requests to more than one request set.

67. The apparatus of claim 39, further comprising:

means for providing resource announcement that comprises an equivalence function.

68. The apparatus of claim 67, wherein said equivalence function is representative of a description of a software agent'"'"'s capabilities.

69. The apparatus of claim 68, wherein a requested resource is satisfied by delegation-based computing where a collection of agents are invoked to satisfy said request.

70. The apparatus of claim 69, wherein said requested resource does not exist within the network but a composite response by said collection of agents satisfy the requested resource.

71. The apparatus of claim of 69, wherein said requested resource comprises a web service.

72. The apparatus of claim 39, further comprising:

means for providing resource announcement that comprises a declarative functional language.

73. The apparatus of claim 39, wherein said assigning means account for physical geographic location of said server nodes.

74. The apparatus of claim 73, wherein said physical geographic location of said server nodes is used to organize server nodes into a plurality of grids.

75. The apparatus of claim 39, wherein said assigning means produce two separate peer-grid networks and said apparatus further comprising means for applying a meta-process for directing queries between said peer-grid networks.

76. The apparatus of claim 39, further comprising:

means for distributing publishing content of a server node to more than one other server node within each of said announce sets.

77. A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions Including instructions which, when executed by a processor, cause the processor to perform a method for facilitating access to a plurality of resources distributed across an electronic network comprising a plurality of interconnected server nodes, each of the resources being associated with at least one corresponding server node, said method comprising the steps of:

a) assigning to each of the server nodes membership in at least one of a plurality of announce sets, each of said plurality of announce sets comprising or more of said server nodes who advertise an availability_ of associated resources to each other;

b) assigning to each of the sever nodes membership in at least one of a plurality of request sets, each of said plurality of request sets comprising two or more of said server nodes who query each other for an availability of one or more associated resource, where each of the request sets intersects with at least one of the announce sets thereby forming a logical grid;

c) receiving a join request from a new server node for joining the network by a member server node of the network; and

d) applying Information stored within said member server node to determine how said new server node will be assigned membership to said network.

78. The computer-readable medium of claim 77, further comprising the step of:

c) publishing a resource of a server node that has not been assigned membership in one of said plurality of announce sets or one of said plurality of request sets.

79. The computer-readable medium of claim 77, wherein said applying step d) applies information relating to sizes of said plurality of announce sets and request sets within the network to determine a proper set for said new server node to join.

80. The computer-readable medium of claim 77, further comprising the step of:

e) splitting one of said plurality of request sets into two request sets; and

f) assigning said new sewer node with membership to one of said newly split request sets.

81. The computer-readable medium of claim 77, further comprising the step of:

e) splitting one of said plurality of announce sets into two announce sets; and

f) assigning said new server node with membership to one of said newly split announce sets.

82. The computer-readable medium of claim 77, further comprising the step of:

f) forwarding said join request to a server node that serves as a publish peer of said member server node.

83. The computer-readable medium of claim 82, further comprising the step of:

g) forwarding request set information or announce set information to said new server node.

84. The computer-readable medium of claim 83, wherein said set information comprises identification of other server nodes within the set and identification of the set'"'"'s publish peers.

85. The computer-readable medium of claim 83, further comprising the step of:

h) receiving a request from said new server node directed to each node in the set to provide a random node in that node'"'"'s set for allowing said new server node to form its own set of publish peers.

86. The computer-readable medium of claim 77, wherein said assigning steps a) and b) assign server nodes such that a ratio of the number announce sets and the number of request sets is held within a target ratio.

87. The computer-readable medium of claim 86, wherein said target ratio varies dynamically depending on a ratio of announce to request actions.

88. The computer-readable medium of claim 77, further comprising the steps of:

c) detecting loss of membership of a server node within a first request set of said plurality of request sets; and

d) forwarding a lookup request that is unanswerable by said first request set to at least a second request set of said plurality of request sets, where an answer provided by said second request set is appended to said first request set.

89. The computer-readable medium of claim 77, further comprising the steps of:

c) detecting loss of membership of a leaving server node within an announce set of said plurality of announce sets by detecting a failure to respond to a publish request; and

d) determining a replacement publish peer server node for said leaving server node'"'"'s set by querying members of its own request set.

90. The computer-readable medium of claim 77, further comprising the step of:

c) splitting one of said plurality of request sets into a first request set and a second request set.

91. The computer-readable medium of claim 90, further comprising the step of:

d) forwarding a lookup request that is unanswerable by said first request set to at least said second request set, where an answer provided by said second request set is added to said first request set.

92. The computer-readable medium of claim 77, further comprising the step of:

c) splitting one of said plurality of announce sets.

93. The computer-readable medium of claim 77, further comprising the step of:

c) merging a first request set of said plurality of request sets into another request set of said plurality of request sets.

94. The computer-readable medium of claim 93, wherein said merging step c) treats each of a plurality of server nodes belonging to said first request set as a new server node joining the network.

95. The computer-readable medium of claim 77, further comprising the step of:

c) merging a first announce set of said plurality of announce sets into another announce set of said plurality of announce sets.

96. The computer-readable medium of claim 95, wherein said merging step c) treats each of a plurality of server nodes belong to said first announce set as a new server node joining the network.

97. The computer-readable medium of claim 77, further comprising the step of:

c) assigning a searching order to said server nodes of one of said request sets.

98. The computer-readable medium of claim 97, wherein said searching order is assigned to achieve a target search time.

99. The computer-readable medium of claim 98, wherein said target search time is a constant search time.

100. The computer-readable medium of claim 98, wherein said target search time is represented approximately by log(n), where n represents a number of server nodes in the network.

101. The computer-readable medium of claim 97, wherein said searching order is defined into a plurality of subsets of an ordering range, where each server node within a set is responsible for one of said subsets of the ordering range.

102. The computer-readable medium of claim 101, wherein said subsets of an ordering range are of equal size or of differing sizes.

103. The computer-readable medium of claim 77, further comprising the step of:

c) providing resource announcements to more than one announce set.

104. The computer-readable medium of claim 77, further comprising the step of:

c) providing resource requests to more than one request set.

105. The computer-readable medium of claim 77, further comprising the step of:

c) providing resource announcement that comprises an equivalence function.

106. The computer-readable medium of claim 105, wherein said equivalence function is representative of a description of a software agent'"'"'s capabilities.

107. The computer-readable medium of claim 106, wherein a requested resource is satisfied by delegation-based computing where a collection of agents are invoked to satisfy said request.

108. The computer-readable medium of claim 107, wherein said requested resource does not exist within the network but a composite response by said collection of agents satisfy the requested resource.

109. The computer-readable medium of claim of 107, wherein said requested resource comprises a web service.

110. The computer-readable medium of claim 77, further comprising the step of:

c) providing resource announcement that comprises a declarative functional language.

111. The computer-readable medium of claim 77, wherein said assigning steps account for physical geographic location of said server nodes.

112. The computer-readable medium of claim 111, wherein said physical geographic location of said server nodes is used to organize server nodes into a plurality of grids.

113. The computer-readable medium of claim 77, further comprising the steps of:

c) repeating steps a) and b) to produce two separate peer-grid networks; and

d) applying a meta-process for directing queries between said peer-grid networks.

114. The computer-readable medium of claim 77, further comprising the steps of:

c) distributing publishing content of a server node to more than one other server node within each of said announce sets.