Method and apparatus for providing scalable resource discovery

• US 20030074402A1
• Filed: 09/12/2002
• Published: 04/17/2003
• Est. Priority Date: 10/23/2000
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Lincoln, Patrick D., Dawson, Steven M., Stringer-Calvert, David W. J.
• Granted Patent: US 7,177,867 B2
• Time in Patent Office: Days
• US Class Current: 709/203
• 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; and

b) assigning to each of the server nodes membership in at least one of a plurality of request sets, where each of the request sets intersects with at least one of the announce sets thereby forming a logical grid.

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, further comprising the steps of:

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.

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

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

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

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

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

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

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

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

11. 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.

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

13. 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.

14. 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.

15. 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.

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

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

c) splitting one of said plurality of announce sets.

18. 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.

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

20. 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.

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

22. 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.

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

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

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

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

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

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

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

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

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

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

c) providing resource announcement that comprises an equivalence function.

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

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

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

34. The method of claim of 32, wherein said requested resource comprises a web service.

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

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

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

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

38. 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.

39. 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.

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

means for assigning to each of the server nodes membership in at least one of a plurality of request sets, where each of the request sets intersects with at least one of the announce sets thereby forming a logical grid.

41. The apparatus of claim 40, 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.

42. The apparatus of claim 40, further comprising:

means for receiving a join request from a new server node for joining 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.

43. The apparatus of claim 42, 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.

44. The apparatus of claim 42, 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 split request sets.

45. The apparatus of claim 42, 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.

46. The apparatus of claim 42, further comprising:

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

47. The apparatus of claim 46, further comprising:

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

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

49. The apparatus of claim 47, 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.

50. The apparatus of claim 40, 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.

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

52. The apparatus of claim 40, 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.

53. The apparatus of claim 40, 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.

54. The apparatus of claim 40, further comprising:

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

55. The apparatus of claim 54, 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.

56. The apparatus of claim 40, further comprising:

means for splitting one of said plurality of announce sets.

57. The apparatus of claim 40, 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.

58. The apparatus of claim 57, 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.

59. The apparatus of claim 40, 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.

60. The apparatus of claim 59, 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.

61. The apparatus of claim 40, further comprising:

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

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

63. The apparatus of claim 62, wherein said target search time is a constant search time.

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

65. The apparatus of claim 61, 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.

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

67. The apparatus of claim 40, further comprising:

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

68. The apparatus of claim 40, further comprising:

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

69. The apparatus of claim 40, further comprising:

means for providing resource announcement that comprises an equivalence function.

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

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

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

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

74. The apparatus of claim 40, further comprising:

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

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

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

77. The apparatus of claim 40, 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.

78. The apparatus of claim 40, further comprising:

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

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

b) assigning to each of the server nodes membership in at least one of a plurality of request sets, where each of the request sets intersects with at least one of the announce sets thereby forming a logical grid.

80. The computer-readable medium of claim 79, 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.

81. The computer-readable medium of claim 79, further comprising the steps of:

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.

82. The computer-readable medium of claim 81, 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.

83. The computer-readable medium of claim 81, 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.

84. The computer-readable medium of claim 81, 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.

85. The computer-readable medium of claim 81, 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.

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

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

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

88. The computer-readable medium of claim 86, 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.

89. The computer-readable medium of claim 79, 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.

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

91. The computer-readable medium of claim 79, 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.

92. The computer-readable medium of claim 79, 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.

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

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

94. The computer-readable medium of claim 93, 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.

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

c) splitting one of said plurality of announce sets.

96. The computer-readable medium of claim 79, 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.

97. The computer-readable medium of claim 96, 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.

98. The computer-readable medium of claim 79, 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.

99. The computer-readable medium of claim 98, 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.

100. The computer-readable medium of claim 79, further comprising the step of:

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

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

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

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

104. The computer-readable medium of claim 100, 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.

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

106. The computer-readable medium of claim 79, further comprising the step of:

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

107. The computer-readable medium of claim 79, further comprising the step of:

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

108. The computer-readable medium of claim 79, further comprising the step of:

c) providing resource announcement that comprises an equivalence function.

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

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

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

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

113. The computer-readable medium of claim 79, further comprising the step of:

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

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

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

116. The computer-readable medium of claim 79, 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.

117. The computer-readable medium of claim 79, 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.