REGISTER  |  SIGN IN
United States Patent6643650
Slaughter , ; et al.November 4, 2003
Title
Mechanism and apparatus for using messages to look up documents stored in spaces in a distributed computing environment
Abstract
A system and method for searching for documents within spaces in a distributed computing environment are provided. A client sends a lookup message to a space which stores documents. The lookup message may specify desired characteristics, such as a name or partial XML schema, of the stored documents. The documents may include XML service advertisements and XML device advertisements as well as general-purpose XML documents. A set of zero or more documents which match the lookup message are discovered. In one embodiment, the lookup message may include a desired name. If the lookup message includes both a desired name and a desired schema, the set of discovered documents may include both discovered documents having a name that matches the desired name and discovered documents having a schema that matches the desired schema. If the lookup message includes neither a desired name nor a desired schema, the set of discovered documents may include substantially all the documents stored in the space. After the matching documents are found, the space may send a lookup response message to the client. For each discovered document, the lookup response message may include a name and an advertisement. Each advertisement may include information which is usable by the client to obtain the respective discovered document or access the resource (e.g., a service) that the document advertises. The advertisements and messages may be expressed in a data representation language such as XML.
Inventors:Slaughter; Gregory L. (Palo Alto, CA), Saulpaugh; Thomas E.  (San Jose, CA), Traversat; Bernard A.  (San Francisco, CA), Abdelaziz; Mohamed M.  (Santa Clara, CA), Duigou; Michael J.  (Fremont, CA)
Assignee:Sun Microsystems, Inc. (Palo Alto, CA)
Appl. No.:660548
Filed:September 12, 2000
Current U.S. Class:707/10 707/104.1 707/4 709/203 709/218 705/14 705/7 
Current International Class:G06F 9/46 (20060101)
Field of Search:705/14,7 707/3,4,10,104.1 709/203,218
U.S. Patent Documents
20020004733January 2002Addante
20020010757January 2002Granik et al.
20020032677March 2002Morgenthaler et al.
20020038344March 2002Ullman et al.
20020069105June 2002Do Rosario Botelho et al.
20020080927June 2002Uppaluru
4491946January 1985Kryshow, Jr. et al.
4713806December 1987Oberlander et al.
4809160February 1989Mahon et al.
4823122April 1989Mann et al.
4939638July 1990Stephenson et al.
4956773September 1990Saito et al.
5088036February 1992Ellis et al.
5109486April 1992Seymour
5187787February 1993Skeen et al.
5218699June 1993Brandle et al.
5257369October 1993Skeen et al.
5293614March 1994Ferguson et al.
5297283March 1994Kelly, Jr. et al.
5307490April 1994Davidson et al.
5311591May 1994Fischer
5339435August 1994Lubkin et al.
5386568January 1995Wold et al.
5390328February 1995Frey et al.
5423042June 1995Jalili et al.
5440744August 1995Jacobson et al.
5448740September 1995Kiri et al.
5452459September 1995Drury et al.
5455952October 1995Gjovaag
5471629November 1995Risch
5475792December 1995Stanford et al.
5475817December 1995Waldo et al.
5481721January 1996Serlet et al.
5504921April 1996Dev et al.
5511197April 1996Hill et al.
5524244June 1996Robinson et al.
5553282September 1996Parrish et al.
5555367September 1996Premerlani et al.
5555427September 1996Aoe et al.
5557798September 1996Skeen et al.
5560003September 1996Nilsen et al.
5561785October 1996Blandy et al.
5577231November 1996Scalzi et al.
5594921January 1997Pettus
5603031February 1997White et al.
5617537April 1997Yamada et al.
5628005May 1997Hurvig
5640564June 1997Hamilton et al.
5644768July 1997Periwal et al.
5649186July 1997Ferguson
5652888July 1997Burgess et al.
5655148August 1997Richman et al.
5659751August 1997Heninger
5671225September 1997Hooper et al.
5675796October 1997Hodges et al.
5680573October 1997Rubin et al.
5680617October 1997Gough et al.
5684955November 1997Meyer et al.
5689709November 1997Corbett et al.
5706435January 1998Barbara et al.
5706502January 1998Foley et al.
5724588March 1998Hill et al.
5727145March 1998Nessett et al.
5737607April 1998Hamilton et al.
5745678April 1998Herzberg et al.
5745695April 1998Gilchrist et al.
5745703April 1998Cejtin et al.
5745755April 1998Covey
5748897May 1998Katiyar
5754849May 1998Dyer et al.
5757925May 1998Faybishenko
5761656June 1998Ben-Shachar
5764897June 1998Khalidi
5768532June 1998Megerian
5774551June 1998Wu et al.
5778187July 1998Monteiro et al.
5778228July 1998Wei
5778368July 1998Hogan et al.
5787425July 1998Bigus
5787431July 1998Shaughnessy
5790548August 1998Sistanizadeh et al.
5802367September 1998Held et al.
5808911September 1998Tucker et al.
5809507September 1998Cavanaugh, III
5813013September 1998Shakib et al.
5815149September 1998Mutschler, III et al.
5815709September 1998Waldo et al.
5815711September 1998Sakamoto et al.
5818448October 1998Katiyar
5829022October 1998Watanabe et al.
5832219November 1998Pettus
5832529November 1998Wollrath et al.
5832593November 1998Wurst et al.
5835737November 1998Sand et al.
5842018November 1998Atkinson et al.
5844553December 1998Hao et al.
5845129December 1998Wendorf et al.
5860004January 1999Fowlow et al.
5860153January 1999Matena et al.
5864862January 1999Kriens et al.
5864866January 1999Henckel et al.
5872928February 1999Lewis et al.
5872973February 1999Mitchell et al.
5875335February 1999Beard
5878411March 1999Burroughs et al.
5884024March 1999Lin et al.
5884079March 1999Furusawa
5887134March 1999Ebrahim
5890158March 1999House et al.
5892904April 1999Atkinson et al.
5933497August 1999Beetcher et al.
5935249August 1999Stern et al.
5940827August 1999Hapner et al.
5944793August 1999Islam et al.
5946485August 1999Weeren et al.
5946694August 1999Copeland et al.
5966531October 1999Skeen et al.
5969967October 1999Aahlad et al.
5987506November 1999Carter et al.
5999179December 1999Kekic et al.
6003763December 1999Gallagher et al.
6009103December 1999Woundy
6016496January 2000Roberson
6016500January 2000Waldo et al.
6026414February 2000Anglin
6031977February 2000Pettus
6061699May 2000DiCecco et al.
6061713May 2000Bharadhwaj
6324566November 2001Himmel et al.
6332062December 2001Phillips et al.
6405175June 2002Ng
Foreign Patent Documents
11-45187Oct., 1997JP
2 253 079Aug., 1992GB
2 262 825Jun., 1993GB
2 305 087Mar., 1997GB
300 516Jan., 1989EP
351 536Jan., 1990EP
384 339Aug., 1990EP
472 874Mar., 1992EP
474 340Mar., 1992EP
497 022Aug., 1992EP
555 997Aug., 1993EP
565 849Oct., 1993EP
569 195Nov., 1993EP
625 750Nov., 1994EP
651 328May., 1995EP
660 231Jun., 1995EP
697 655Feb., 1996EP
718 761Jun., 1996EP
767 432Apr., 1997EP
778 520Jun., 1997EP
794 493Sep., 1997EP
803 810Oct., 1997EP
803 811Oct., 1997EP
805 393Nov., 1997EP
810 524Dec., 1997EP
817 020Jan., 1998EP
817 022Jan., 1998EP
817 025Jan., 1998EP
836 140Apr., 1998EP
892 530Jan., 1999EP
92/07335Apr., 1992WO
92/09948Jun., 1992WO
93/25962Dec., 1993WO
94/03855Feb., 1994WO
96/03692Feb., 1996WO
96/10787Apr., 1996WO
96/18947Jun., 1996WO
96/24099Aug., 1996WO
98/02814Jan., 1998WO
98/04971Feb., 1998WO
Other References
XP-002211482, "Federating and Administering Lookup Services", pp. 320-329, 405-419, 635-656, Jun. 1999. .
XP-002212130, "The Search API's", pp. 297-305, 320-329, 635-656, Jun. 1999. .
"Network Nirvana and the Intelligent Device", Spotlight, XP-002927392, pp. 16-19, Apr. 1999. .
"Behavioral Specification Using XML", Mckee and Marshall, IEEE, pp. 53-59, 1999. .
"JavaSpaces", Chapter 15, XP-002212109, pp. 636-657, Jun. 1999. .
"T Spaces", Wycoff, et al., 8M Systems Journal, pp. 454-474, 1998. .
"Management of Advanced Services in H.323 Internet Protocol Telephony", Pagurek, et al. IEEE pp. 91-100. Mar. 26, 2000. .
"Service Location Protocol: Automatic Discovery of IP Network Services", Erik Guttman of Sun Microsystems, IEEE Internet Computing, pp. 71-80, Jul. 1999. .
Jaworski, "Java 1.1 Developer's Guide, 2.sup.nd Edition," Sams.net, 1997. .
Coulouris, et al., "Distributed Systems Concepts and Designs," Second Edition, Addison-Wesley, 1994. .
Mullender, "Distributed Systems," Second Edition, Addison-Wesley, 1993. .
Lindholm, et al., "The Java .TM. Virtual Machine Specification," Addison Wesley, 1996. .
"SOAP: Simple Object Access Protocol," msdn online Web Workshop, Microsoft, Apr. 26, 2000, msdn.Microsoft.com/xml/general/soapspec.asp, 34 pages. .
Rob Guth, "Sun tries on JacaSpaces for Distributed OS," Aug. 1997, vol. 19, Issue 34, 2 pages. .
Microsoft, "Microsoft.NET: Realizing the Next Generation Internet," A Microsoft White Paper, Jun. 2000, 8 pages. .
K. F. Eustice, et al., "A Universal Information Appliance," IBM Systems Journal, vol. 38, No. 4, 1999, Pp. 575-601. .
Wycoff et al., "T Spaces," IBM Systems Journal, vol. 37, No. 3-Java Technology, Aug. 1998, 36 pages. .
"Java .TM. Remote Method Invocation Specification," Sun Microsystems, Inc., <java.sun.com/products/ dk1.2beta1>, 1997. .
Agha, et al., "Actorspaces: An Open Distributed Programming Paradigm," University of Illinois, Report No. UIUCDCS-R-92-1766, Open Systems Laboratory TR NO. 8, pp. 1-12, Nov. 1992. .
Ahmed, et al., "A Program Building Tool for Parallel Applications," Yale University, pp. 1-23, Dec. 1, 1993. .
Aldrich, et al., "Providing Easier Access to Remote Objects in Client-Server Systems," System Sciences, 1998, Proceedings of the 31.sup.st Hawaii Internat'l. Conference, Jan. 6-9, 1998, pp. 366-375. .
Aldrich, et al., "Providing Easier Access to Remote Objects in Distributed Systems," Calif. Institute of Technology, www.cs.Caltech.edu/%7Ejedi/paper.html, Nov. 21, 1997. .
Anderson, et al., "Persistent Linda: Linda + Transaction + Query Processing," Proceedings of the 13.sup.th Symposium on Fault Tolerant Systems, pp. 93-109, 1991. .
"Transparent Network Computing," Locus Computing Corporation, Jan. 5, 1995. .
Alexander, et al., "Active Bridging," Proceedings of the ACM/SIGCOMM'97 Conference, Cannes, France, Sep., 1997. .
Beech, et al., "Object Databases as Generalizations of Relational Databases," Computer Standards & Interfaces, vol. 13, Nos. 1/3 pp. 221-230, Amsterdam, NL, Jan. 1991. .
Bertino, et al., Object-Oriented Database Management Systems: Concepts and issues,: Computer, vol. 24, No. 4, pp. 33-47, Los Alamitos, CA, Apr. 1991. .
Betz, et al, "Interoperable Objects: Laying the Foundation for Distributed Object Computing," Dr. Dobb's Journal, vol. 19, NO. 11, p. 18(13), Oct. 1994. .
Bevan, et al., "An Efficient Reference Counting Solution To The Distributed Garbage Collection Problem," Parallel Computing, NL, Elsevier Science Publishers, Amsterdam, vol. 9, No. 2, pp. 179-192, Jan. 1989. .
Birrell, et al., "Distributed Garbage Collection for Network Objects," Digital Systems Research Center, NO. 116, pp. 1-18, Dec. 15, 1993. .
Birrell, et al., "Grapevine: An Exercise in Distributed Computing," Communications fo the ACM, vol. 25, No. 4, pp. 260-274, Apr. 1982. .
Birrell, et al., "Network Objects," DEC SRC Research Report 115, Feb. 28, 1995. .
Birrell, et al., "Implementing Remote Procedure Calls," ACM Transactions on Computer Systems, vol. 2, No. 1, pp. 39-59, Feb. 1994. .
Birrell, et al., "Network Objects," Operating Systems Review, 27(5), pp. 217-230, Dec. 1993. .
Cannon, et al., "Adding Fault-Tolerant Transaction Processing to LINDA," Software-Practice and Experience, vol. 24(5), pp. 449-466, May 1994. .
Cardelli, "Obliq, A Lightweight Language For Network Objects," Digital SRC, pp. 1-37, Nov. 5, 1993. .
Carriero, et al., "Distributed Data Structures in Linda," Principles of Programming Language, pp. 1-16, 1986. .
Carriero, et al., "Distributed Data Structures in Linda," Yale Research Report YALEU/DCS/RR-438, Nov. 1985. .
Chung, et al., "A Tiny' Pascal Compiler: Part 1: The P-Code Interpreter," BYTE Publications, Inc., Sep. 1978. .
Chung, et al., "A Tiny' Pascal Compiler: Part 2: The P-Compiler," BYTE Publications, Inc., Oct. 1978. .
Dave, et al., "Proxies, Application Interface, And Distributed Systems," Proceedings International Workshop On Object Orientation In Operating Systems, pp. 212-220, Sep. 24, 1992. .
Deux, et al., "The O2 System," Communications Of The Association For Computing Machinery, Col. 34, No. 10, pp. 34-48, Oct. 1, 1991. .
Dijkstra, "Self-stabilizing Systems in Spite of Distributed Control," Communications of the ACM, Vol 17, No. 11, pp. 643-644, Nov. 1974. .
Dolev, et al., "On the Minimal Synchronism Needed for Distributed Consensus," Journal of the ACM, vol. 34, NO. 1, pp. 77-97, Jan. 1987. .
Dollimore, et al., "The design of a System for Distributing Shared Objects," The Computer Journal, No. 6, Cambridge, GB, Dec. 1991. .
Dourish, "A Divergence-Based Model of Synchrony and Distributed in Collaborative Systems," Xerox Technical Report EPC-1194-102, pp. 1-10, 1994. .
Drexier, et al., "Incentive Engineering for Computational Resource Management," The Ecology of Computation, Elsevier Science Publishers B.V., pp. 231-266, 1988. .
Gelernter, et al., "Parallel Programming in Linda," Yale University, pp. 1-21, Jan. 1995. .
Droms, "RFC 1541 Dynamic Host Configuration Protocol," <http://www.cis.ohio-state.edu.htbin/rfc/rfc1541.html>, pp. 1-33, Oct. 1993. .
Emms, "A Definition Of AN Access Control Systems Language," Computer Standards And Interfaces, vol. 6, No. 4, pp. 443-454, Jan. 1, 1997. .
Fleisch, et al., "High Performance Distributed Objects Using Distributed Shared Memory & Remote Method Invocation," System Sciences, 1998, Proceedings of the 31.sup.st Hawaii Internat'l. Conference, Jan. 6-9, 1998, pp. 574-578. .
Gelernter, "Generative Communication in Linda," ACM Transactions on Programming Languages and Systems, vol. 7, No. 1, pp. 80-112, Jan. 1985. .
Gottlob, et al., "Extending Object-Oriented Systems with Roles," ACM Transactions On Information Systems, vol. 14, NO. 3, pp. 268-296, Jul. 1996. .
Gray, et al. "Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency," ACM, pp. 202-210, 1989. .
Guth, "JavaOne: Sun to Expand Java Distributed Computing Effor," <http://www.sunworld.com/swol-02-1998/swol-02-sunspots.html>, XP-002109935, p.1, Feb. 20, 1998. .
Guyennet, et al., "A New Consistency Protocol Implemented in the CaliF System," IEEE, 1094-7256/97, pp. 82-87, 1997. .
Guyennet, et al., "Distributed Shared Memory Layer for Cooperative Work Applications," IEEE, 0742-1303/97, pp. 72-78, 1997. .
Hamilton, et al., "Subcontract: A Flexible Base for Distributed Programming," Proceedings of 14.sup.th Symposium of Operating System Principles, Dec. 1993. .
Hamilton, "Java and the Shift to Net-Centric Computing," Computer, pp. 31-39, Aug. 1996. .
Harris, et al., "Proposal for a General Java Proxy Class for Distributed Systems and Other Uses," Netscape Communications Corp., Jun. 25, 1997. .
Hartman, et al., "Liquid Software: A New Paradigm For Networked Systems," Technical Report 96-11, Dept. of Comp. Sci., Univ. of Arizona, Jun. 1996. .
Howard, et al., "Scale and Performance in a Distributed File System," ACM Transactions on Computer Systems, vol. 6, No. 1, pp. 51-81, Feb. 1988. .
Pier, "A Retrospective on the Dorando, A High-Performance Personal Computer," Xerox Corporation, Aug. 1983. .
Pinakis, "Using Linda as the Basis of an Operating System Microkernel," University of Western Australia, Dept. of Computer Science, pp. 1-165, Aug. 1993. .
Riggs, et al., "Picking State in the Java .TM. System," USENIX, Association Conference on Object-Oriented Technologies and Systems, CP-002112719, pp. 241-250, Jun. 17-21, 1996. .
Rosenberry, et al., "Understanding DCE," Chapters 1-3, 6, 1992. .
Sharrott, et al., "ObjectMap: Integrated High Performance Resources into a Distributed Object-oriented Environment," ICODP, 1995. .
Stevenson, "Token-Based Consistency of Replicated Servers," IEEE, CH2686-4/89/0000/0179, pp. 179-183, 1989. .
Thompson, "Regular Expression Search Algorithm," Communications of the ACM, vol. II, No. 6, p. 149 et seq., Jun. 1968. .
Venners, "Jini Technology, Out of the Box," JAVAWORLD, Online!, pp. 1-4, Dec. 1998. .
Waldo, et al., "Events in An RPC Based Distributed System," Proceedings Of The 1995 USENIX Technical Conference, Proceedings USENIX Winter 1995 Technical Conference, New Orleans, LA, USA, 16-20, pp. 131-142, Jan. 1995. .
Wilson, et al., "Design of the Opportunistic Garbage Collector," Proceedings of the Object Oriented Programming Systems Languages And Applications Conference, New Orleans, vol. 24, No. 10, Oct. 1989. .
Wollrath, et al., "A Distributed Object Model for theJaca .TM. System," USENIX Association, Conference on Object-Oriented Technologies and Systems, Jun. 17-21, 1996. .
Wu, "A Type System For An Object-Oriented Database Systems," Proceedings of the International Computer Software and Applications Conference (COMPSAC), Tokyo, Japan, pp. 333-338, Sep. 11-13, 1991. .
Yemini, et al., "Towards Programmable Networks," IFIP/IEEE International Workshop on Distributed Systems: Operations and Management, L'Aquila, Italy, Oct. 1996. .
Yin, et al., "Using Leases to Support Server Driven Consistency in Large-Scale Systems," Computer Services Department, University of Texas at Austin, p. 285-294, May 26-28, 1998. .
Yin, et al., "Volume Leases for Consistency in Large-Scale Systems," IEEE Transactions on Knowledge & Data Engineering, vol. 11, No. 4, pp. 563-576, Jul./Aug. 1999. .
Mitchell, et al., "An Overview of the Spring System," Feb. 1994. .
Mitchell, et al., "Mesa Language Manual," Xerox Corporation, Palo Alto Research Center, 1978. .
McDaniel, "An Analysis of a Mesa Instruction Set," Xerox Corporation, May 1982. .
McGrath, "Discovery and its Discontents: Discovery Protocols for Ubiquitous Computing," Presented at Center for Excellence in Space Data and Information Science, NASA Goddard Space Flight Center, Apr. 5, 2000. .
Mummert, et al., "Long Term Distributed File Reference Tracing: Implementation and Experience," Carnegie Mellon University School of Computer Science, pp. 1-28, Nov. 1994. .
Orfali, et al., "The Essential Distributed Objects Survival Guide," Chapter 11: Corba Commercial ORBs, pp. 203-215, John Wiley & Sons, Inc., 1996. .
Ousterhout, et al., "The Sprite Network Operating System," Computer, IEEE, pp. 23-36, Feb. 1988. .
Pier, "A Retrospective on the Dorando, A High-Performance Personal Computer," IEEE Conference Proceedings, The 10.sup.th Annual International Symposium on Computer Architecture, 1993. .
Hunt, "IDF: A Graphical Data Flow Programming Language for Image Processing and Computer Vision," Proceedings of the International Conference on Systems, Man, and Cybernetics, pp. 351-360, Los Angeles, Nov. 4-7, 1990. .
IBM .TM. Technical Disclosure Bulletin, "Object Location Algorithm," vol. 36, No. 09B, pp. 257-258, Sep. 1993. .
IBM, "Chapter 6--Distributed SOM (DSOM)," SOMobjects Developer Toolkit Users Guide, Version 2.1, pp. 6-1-6-90, Oct. 1994. .
Anonymous, "Change-Notification Service for Shared Filed," IBM Technical Disclosure Bulletin, vol. 36, No. 8, pp. 77-82, XP002109435 New York, US, Nov. 1973. .
IBM .TM. Technical Disclosure Bulletin, "Retrieval of Qualified Variables Using Extendible Hashing," vol. 36, No. 12, pp. 301-303, Dec. 1993. .
Anonymous, "Resource Preemption for Priority Scheduling," IBM Technical Disclosure Bulletin, vol. 16, No. 6, p. 1931, XP002109435 New York, US, Nov. 1973. .
IBM .TM. Technical Disclosure Bulletin, "Local Network Monitoring to Populate Access Agent Directory," vol. 36, No. 09A, pp. 403
Primary Examiner: Coby; Frantz
Attorney, Agent or Firm:Kowert; Robert C. Meyertons, Hood, Kivlin, Kowert & Goetzel, P.C.
Parent Case Text


PRIORITY INFORMATION

This application claims benefit of priority to the following provisional applications, each of which is hereby incorporated by reference in its entirety: Serial No. 60/202,975 filed May 9, 2000 titled Distributed Computing Environment; Serial No. 60/208,011 filed May 26, 2000 titled Distributed Computing Environment; Serial No. 60/209,430 filed June 2, 2000 titled Distributed Computing Environment; Serial No. 60/209,140 filed June 2, 2000 titled Distributed Computing Environment; and Serial No. 60/209,525 filed June 5, 2000 titled Distributed Computing Environment.
Claims

What is claimed is:
1. A method, comprising: a client sending a lookup message to a network-addressable location of a space, wherein the space is operable to store one or more advertisements expressed in a data representation language, wherein each advertisement comprises information which is usable by the client to access a particular content or service over a network, and wherein the lookup message specifies desired advertisement characteristics; finding a set of discovered advertisements, wherein the discovered advertisements comprise zero or more of the stored advertisements which meet the desired characteristics; and the space sending a lookup response message to the client, wherein the lookup response message comprises the set of discovered advertisements.

2. The method of claim 1, wherein each advertisement comprises a Uniform Resource Identifier (URI) at which the respective content or service is accessible.

3. The method of claim 1, wherein at least one of the discovered advertisements comprises an advertisement for a service.

4. The method of claim 3, wherein the advertisement for the service comprises a schema, wherein the schema specifies one or more messages usable to invoke one or more functions of the service.

5. The method of claim 1, wherein the lookup message comprises a desired name, wherein each of the discovered advertisements comprises a name that matches the desired name, and wherein each name identifies the respective discovered advertisement within space.

6. The method of claim 5, wherein the desired name comprises a wildcard.

7. The method of claim 1, wherein the lookup message comprises a desired schema which is expressed in the data representation language, and wherein each of the discovered advertisements comprises a schema that matches the desired schema.

8. The method of claim 1, wherein the lookup message comprises a desired name and a desired schema, wherein the set of discovered advertisements comprises discovered advertisements having a name that matches the desired name and discovered advertisements having a schema that matches the desired schema.

9. The method of claim 1, wherein the lookup message comprises a request for all advertisements in the space, and wherein the set of discovered advertisements includes substantially all the stored advertisements.

10. The method of claim 1, wherein the data representation language comprises eXtensible Markup Language (XML).

11. The method of claim 1, wherein the lookup message and the lookup response message are expressed in the data representation language.

12. A system, comprising: a client; and a space which is communicatively coupled to the client, wherein the space is operable to store one or more advertisements expressed in a data representation language, wherein each advertisement comprises information which is usable by the client to access a particular content or service over a network; wherein the client is operable to send a lookup message to the space, and wherein the lookup message specifies desired advertisement characteristics; and wherein the space is operable to: find a set of discovered advertisements, wherein the discovered advertisements comprise zero or more of the stored advertisements which meet the desired characteristics; and send a lookup response message to the client, wherein the lookup response message comprises the set of discovered advertisements.

13. The system of claim 12, wherein each advertisement comprises a Uniform Resource Identifier (URI) at which the respective content or service is accessible.

14. The system of claim 12, further comprising: a service which is communicatively coupled to the client, wherein at least one of the discovered advertisements comprises an advertisement for the service.

15. The system of claim 14, wherein the advertisement for the service comprises a schema, wherein the schema specifies one or more messages usable to invoke one or more functions of the service.

16. The system of claim 12, wherein the lookup message comprises a desired name, wherein each of the discovered advertisements comprises a name that matches the desired name, and wherein each name identifies the respective discovered advertisements within the space.

17. The system of claim 16, wherein the desired name comprises a wildcard.

18. The system of claim 12, wherein the lookup message comprises a desired schema which is expressed in the data representation language, and wherein each of the discovered advertisements comprises a schema that matches the desired schema.

19. The system of claim 12, wherein the lookup message comprises a desired name and a desired schema, wherein the set of discovered advertisements comprises discovered advertisements having a name that matches the desired name and discovered advertisements having a schema that matches the desired schema.

20. The system of claim 12, wherein the lookup message comprises a request for all advertisements in the space, and wherein the set of discovered advertisements includes substantially all the stored advertisements.

21. The system of claim 12, wherein the data representation language comprises eXtensible Markup Language (XML).

22. The system of claim 12, wherein the lookup message and the lookup response message are expressed in the data representation language.

23. A carrier medium comprising program instructions, wherein the program instructions are computer-executable to implement: a client sending a lookup message to a network-addressable location of a space, wherein the space is operable to store one or more advertisements expressed in a data representation language, wherein each advertisement comprises information which is usable by the client to access a particular content or service over a network, and wherein the lookup message specifies desired advertisement characteristics; finding a set of discovered advertisements, wherein the discovered advertisements comprise zero or more of the stored advertisements which meet the desired characteristics; and the space sending a lookup response message to the client, wherein the lookup response message comprises the set of discovered advertisements.

24. The carrier medium of claim 23, wherein each advertisement comprises a Uniform Resource Identifier (URI) at which the respective content or service is accessible.

25. The carrier medium of claim 23, wherein at least one of the discovered advertisements comprises an advertisement for a service.

26. The carrier medium of claim 25, wherein the advertisement for the service comprises a schema, wherein the schema specifies one or more messages usable to invoke one or more functions of the service.

27. The carrier medium of claim 23, wherein the lookup message comprises a desired name, wherein each of the discovered advertisements comprises a name that matches the desired name, and wherein each name identifies the respective discovered advertisements within the space.

28. The carrier medium of claim 27, wherein the desired name comprises a wildcard.

29. The carrier medium of claim 23, wherein the lookup message comprises a desired schema which is expressed in the data representation language, and wherein each of the discovered advertisements comprises a schema that matches the desired schema.

30. The carrier medium of claim 23, wherein the lookup message comprises a desired name and a desired schema, wherein the set of discovered advertisements comprises discovered advertisements having a name that matches the desired name and discovered advertisements having a schema that matches the desired schema.

31. The carrier medium of claim 23, wherein the lookup message comprises a request for all advertisements in the space, and wherein the set of discovered advertisements includes substantially all the stored advertisements.

32. The carrier medium of claim 23, wherein the data representation language comprises eXtensible Markup Language (XML).

33. The carrier medium of claim 23, wherein the lookup message and the lookup response message are expressed in the data representation language.

34. A method, comprising: a client sending a lookup message to a space, wherein the lookup message is expressed in a data representation language, wherein the space is operable to store one or more documents expressed in the data representation language, and wherein the lookup message specifies desired characteristics of the stored documents; finding a set of discovered documents, wherein the discovered documents comprise zero or more of the stored documents which meet the desired characteristics; and the space sending a lookup response message to the client, wherein the lookup response message is expressed in the data representation language and comprises the set of discovered documents.

35. The method of claim 34, wherein each of the discovered documents comprises information usable by the client to access a respective content or service.

36. The method of claim 35, wherein the information usable by the client to access a respective content or service comprises a Uniform Resource Identifier (URI) at which the respective content or service is accessible.

37. The method of claim 35, wherein at least one of the discovered documents comprises information for accessing a service.

38. The method of claim 37, wherein the information for accessing a service comprises a schema, wherein the schema specifies one or more messages usable to invoke one or more functions of the service.

39. The method of claim 34, wherein the lookup message comprises a desired name, wherein each of the discovered documents comprises a name that matches the desired name, and wherein each name identifies the respective discovered document within the space.

40. The method of claim 39, wherein the desired name comprises a wildcard.

41. The method of claim 34, wherein the lookup message comprises a desired schema which is expressed in the data representation language, and wherein each of the discovered documents comprises a schema that matches the desired schema.

42. The method of claim 34, wherein the lookup message comprises a desired name and a desired schema, wherein the set of discovered documents comprises discovered documents having a name that matches the desired name and discovered documents having a schema that matches the desired schema.

43. The method of claim 34, wherein the lookup message comprises a request for all documents in the space, and wherein the set of discovered documents includes substantially all the stored documents.

44. The method of claim 34, wherein the data representation language comprises eXtensible Markup Language (XML).

45. The method of claim 34, further comprising: the client sending an event subscription message to the space, wherein the event subscription message indicates a desired document for which the client is requesting to receive notification if the desired document is added to or removed from the space; and the space sending an event notification message to the client when a document matching the desired document is added to or removed from the space.

46. The method of claim 45, wherein the event subscription message and the event notification message are expressed in the data representation language.
Description
BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to distributed computing environments including Web-centric and Internet-centric distributed computing environments, and more particularly to a heterogeneous distributed computing environment based upon a message passing model for connecting network clients and services.

2. Description of the Related Art

Intelligent devices are becoming more and more common. Such devices range from smart appliances, personal digital assistants (PDAs), cell phones, lap top computers, desktop computers, workstations, mainframes; even, super computers. Networks are also becoming an increasingly common way to interconnect intelligent devices so that they may communicate with one another. However, there may be large differences in the computing power and storage capabilities of various intelligent devices. Devices with more limited capabilities may be referred to as small footprint devices or "thin" devices. Thin devices may not be able to participate in networks interconnecting more capable devices. However, it may still be desirable to interconnect a wide variety of different types of intelligent devices.

The desire to improve networking capabilities is ever increasing. Business networks are expanding to include direct interaction with suppliers and customers. Cellular phones, personal digital assistants and Internet-enabled computers arc commonplace in both business and the home. Home networks are available for interconnecting audio/visual equipment such as televisions and stereo equipment to home computers, and other devices to control intelligent systems such as security systems and temperature control thermostats. High bandwidth mediums such as cable and ASDL enable improved services such as Internet access video on demand, e-commerce, etc. Network systems are becoming pervasive. Even without a formal network, it is still desirable for intelligent devices to be able to communicate with each other and share resources.

Currently, traditional networks are complex to set up, expand and manage. For example, adding hardware or software to a network often requires a network administrator to load drivers and configure systems. Making small changes to a network configuration may require that the entire network be brought down for a period of time. Also, certain intelligent devices may not support the necessary interfaces to communicate on a given network.

What is needed is a simple way to connect various types of intelligent devices to allow for communication and sharing of resources while avoiding the interoperability and complex configuration problems existing in conventional networks. Various technologies exist for improving the addition of devices to a network. For example, many modern I/O buses, such as the Universal Serial Bus, 1394 and PCI, support plug and play or dynamic discovery protocols to simplify the addition of a new device on the bus. However, these solutions are limited to specific peripheral buses and are not suitable for general networks.

A more recent technology, Jini from Sun Microsystems, Inc., seeks to simplify the connection and sharing of devices such as printers and disk drives on a network. A device that incorporates Jini may announce itself to the network, may provide some details about its capabilities, and may immediately become accessible to other devices on the network. Jini allows for distributed computing where the capabilities of the various devices are shared on a network. The Jini technology seeks to enable users to share services and resources over a network. Another goal of the Jini technology is to provide users with easy access to resources anywhere on the network while allowing the network location of the user to change. Jini also seeks to simplify the task of building, maintaining and altering a network of devices, software and users.

Jini requires that each Jini enabled device has a certain amount of memory and processing power. Typically, a Jini enabled device is equipped with a Java Virtual Machine (JVM). Thus, Jini systems are Java technology centered. Java is a high level object oriented programming language developed by Sun Microsystems, Inc. Java source code may be compiled into a format called bytecode, which may then be executed by a Java Virtual Machine. Since Java Virtual Machines may be provided for most computing platforms, Java and thus Jini provide for a certain amount of platform independence. The Jini architecture leverages off the assumption that the Java programming language is the implementation language for the components of the Jini system. The ability to dynamically download and run Java code is central to many features of the Jini architecture.

The purpose of the Jini architecture is to federate groups of devices and software components into a single dynamic distributed system. A key concept within the Jini architecture is that of a service. A service is an entity that can be used by a person, a program, or another service. Two examples of services are printing a document and translating from one word processor format to another. Jini allows the members of a Jini system to share access to services. Services in a Jini system communicate with each other by using a service protocol, which is a set of interfaces written in the Java programming language. Services are found and resolved in a Jini system by a look-up service. A look-up service maps interfaces indicating the functionality provided by a service to sets of objects that implement the service.

Descriptive entries may also be associated with a service. Devices and applications use a process known as discovery to register with the Jini network. Once registered, the device or application places itself in the look-up service. The look-up service may store not only pointers to these services on the network, but also may store the code for accessing these services. For example, when a printer registers with the look-up service, it loads its printer driver and/or an interface to the driver into the look-up service. When a client wants to use the printer, the driver and driver interface get downloaded from the look-up service to the client. This code mobility means that clients can take advantage of services from the network without pre-installing or loading drivers or other software.

Communication between services in a Jini system is accomplished using the Java Remote Method Invocation (RMI). RMI is a Java programming language enabled extension to traditional remote procedure call mechanisms. RMI allows not only data to be passed from object to object around the Jini network, but full objects including code as well. Jini systems depend upon this ability to move code around the network in a form that is encapsulated as a Java object.

Access to services in a Jini system is lease based. A lease is a grant of guaranteed access over a time. Each lease is negotiated between the user of the service and the provider of the service as part of the service protocol. A service may be requested for some period and access may be granted for some period presumably considering the request period. Leases must be renewed for a service to remain part of the Jini system.

FIG. 1 illustrates the basic Jini technology stack. The Jini technology defines a distributed programming model 12 (supported by JavaSpaces, leases, and objectm templates). Object communication in Jini is based on an RMI layer 14 over a TCP/IP capable networking layer 16.

Jini is a promising technology for simplifying distributed computing. However, for certain types of devices, Jini may not be appropriate. The computing landscape is moving toward a distributed, Web-centric service and content model where the composition of client services and content changes rapidly. The client of the future may be a companion type device that users take with them wherever they go. Such a device may be a combination of a cell phone and a PDA for example. It would be desirable for such devices to be able to communicate and share resources with more powerful devices as well as thinner or less powerful devices.

Also, with the advent of the Internet and resulting explosion of devices connected to the net, a distributed programming model designed to leverage this phenomenon is needed. An enabling technology is needed that facilitates clients connecting to services in a reliable and secure fashion. Various clients from thick to thin and services need to be connected over the Internet, corporate Intemets, or even within single computers. It is desirable to abstract the distance, latency and implementation from both clients and services.

The key challenge for distributed computing technology is to be scalable from powerful thick clients down to very thin clients such as embedded mobile devices. Current distributed computing technologies, such as Jini, may not be scalable enough for the needs of all types of clients. Some devices, such as small footprint devices or embedded devices, may lack sufficient memory resources and/or lack sufficient networking bandwidth to participate satisfactorily in current distributed computing technologies. The low end of the client spectrum, including embedded mobile devices, often have limited or fixed code execution environments. These devices also may have minimal or no persistent storage capabilities. Most small, embedded mobile devices do not support a Java Virtual Machine. Most code-capable small clients run native code only. Also, most small devices have little more than flash memory or battery backed RAM as their sole persistent storage media. The size of the storage is often very small and sometimes read-only in nature. Furthermore, the access time of this type of storage media is often an order of magnitude greater than hard disk access time in more powerful clients.

Existing connection technologies, such as Jini, may not be as scalable as desired because they are too big. For example, Jini requires that all participants support Java; however, many small clients may not have the resources for a Java Virtual Machine. Furthermore, due to its use of RMI, Jini requires that clients be able to download code and content. Jini may augment the existing client platform by downloading new classes, which may pose security and size concerns for small devices such as embedded devices. Jini works by clients and resources communicating by passing code and data. When a client activates a Jini service, the service may return its results to the client, which may include a large amount of code or content. In Jini, a client may call a method and a large object may be returned, and thus downloaded. The client may not have the resource to accept the returned object. Also, RMI and Java itself require a lot of memory. Many small foot print devices may not have the resources to participate effectively or at all in current distributed computing technologies.

Another concern with existing distributed computing technologies is that they often require certain levels of connection capability and protocols. For example, Jini assumes the existence of a network of reasonable speed for connecting computers and devices. Jini also requires devices to support TCP/IP network transport protocol. However, many smaller devices may have limited connection capabilities. Small devices may have high latency or low speed network connections and may not support TCP/IP.

As mentioned above, Jini requires devices to support Java and thus include a Java Virtual Machine, which requires a certain amount of processing and storage capabilities that might not be present for many small devices. This also restricts the flexibility of Jini in that non-Java devices may not directly participate in a Jini system. Since Jini requires Java, it may be deemed a homogenous environment. However, it is desirable to have a distributed computing facility for heterogeneous distributed computing that scales from extremely small embedded devices through PDA's and cell phones to laptops and beyond even to the most powerful computers.

Other heterogeneous solutions exist, such as the Common Object Request Broker Architecture (CORBA). CORBA is an architecture that enables program objects to communicate with one another regardless of the programming language they were written in or what operating system they're running on. However, CORBA does not address all of the connection issues that are addressed by Jini. Also, CORBA suffers from similar scalability problems as Jini.

Technology such as Jini and CORBA use a code-centric programming model to define the interface between remote components. A code-centric programming model defines programmatic interfaces or API's for communication between remote clients or components. The API's may be defined in a particular programming language. The API's must be agreed to by all software components to ensure proper interoperability. Since all access to components is through the use of these standards API's, the code that implements these API's must be present in the client platform. The code may be statically linked into the platform or dynamically downloaded when needed. Many embedded or mobile devices simply cannot accept code dynamically from a network due to the quality control issues involved as well as the reliance on a single language and program execution environment. Data-centric models, such as networking protocols, may avoid the dependence on moving code; however, such protocols are not rich enough to easily provide for distributed computing and they also lack the ease of programming with code and other programming features, such as type safety.

Conventional distributed computing systems rely on the ability of a program executing on a first device to be able to remotely call a program on a second device and have the results returned to the first device. The Remote Procedure Call (RPC) is a basic mechanism for remotely calling a program or procedure. CORBA and Jini are both based on the ability to remotely invoke program methods. However, communicating by passing code or objects, such as in Jini or CORBA, may be somewhat complex. For example, as mentioned above, Jini uses the Java Remote Method Invocation (RMI) to communicate between services. In order for a client to move Java objects to and from remote locations, some means of serialization/deserialization is needed. Such current facilities in the Java Development Kit (JDK) rely upon the reflection API to determine the content of a Java object, and ultimately that code must consult the Virtual Machine. This code is quite large and inefficient.

The fundamental problems with the current method for doing serialization/deserialization include its size, speed, and object traversal model. Code outside the JVM does not know the structure or graph of a Java object and thus must traverse the object graph, pulling it apart, and ultimately must call upon the JVM. Traditional serialization and reflection mechanisms for storing and moving Java objects are just not practical for all types of devices, especially thinner devices. Some of the difficulties with Java reflection and serialization are that an object's graph (an object's transitive closure) reflection is difficult to do outside the JVM. Serialization is too large, requiring a large amount of code. Also, serialization is a Java specific object interchange format and thus may not be used with non-Java devices.

The Jini distributed computing model requires the movement of Java objects between Java devices. Thus, the serialization mechanism itself is not platform independent since it may not be used by non-Java platforms to send and receive objects. Serialization is a homogenous object format--it only works on Java platforms. Serialization uses the reflection API and may be limited by security concerns, which often must be addressed using native JVM dependent methods. The reflection API may provide a graph of objects, but is inefficient due to the number of calls between the JVM and the code calling the reflection methods.

The use of Java reflection to serialize an object requires an application to ping pong in and out of the JVM to pick apart an object one field at a time as the transitive closure of the object is dynamically analyzed. Deserializing an object using Java deserialization requires the application to work closely with the JVM to reconstitute the object one field at a time as the transitive closure of the object is dynamically analyzed. Thus, Java serialization/deserialization is slow and cumbersome while also requiring large amounts of application and JVM code as well as persistent storage space.

Even for thin clients that do support Java, the Jini RMI may not be practical for thin clients with minimal memory footprints and minimal bandwidth. The serialization associated with the Jini RMI is slow, big, requires the JVM reflection API, and is a Java specific object representation. Java deserialization is also slow, big and requires a serialized-object parser. Even Java based thin clients may not be able to accept huge Java objects (along with needed classes) being returned (necessarily) across the network to the client as required in Jini. A more scalable distributed computing mechanism is needed. It may be desirable for a more scalable distributed computing mechanism to address security concerns and be expandable to allow for the passing of objects, such as Java objects, and even to allow for process migration from one network mode to another.

Object based distributed computing systems need persistent storage. However, as discussed above, attempts at object storage are often language and operating system specific. In addition, these object storage systems are too complicated to be used with many small, embedded systems. For example, the Jini technology uses JavaSpaces as persistent object containers. However, a JavaSpace can only store Java objects and cannot be implemented in small devices. Each object in a JavaSpace is serialized and pays the above-described penalties associated with Java serialization. It may be desirable to have a heterogeneous object repository for distributed computing that may scale from small to large devices.

JavaSpaces from Sun Microsystems, Inc., draws from the parallel processing work of David Gelernter, a computer science professor at Yale University. Gelernter's set of functions named "Linda" create a shared memory space called a TupleSpace, in which results of a computer's processes or the processes themselves may be stored for access by multiple CPUs. Linda therefore provides a global shared memory for multiple processors.

Another technology which extends Linda is TSpaces from IBM Corporation. TSpaces extends the basic Linda TupleSpace framework with real data management and the ability to download new datatypes and new semantic functionality. TSpaces provides a set of network communication buffers and a set of APIs for accessing those buffers. Like many of the solutions discussed above, TSpaces therefore uses a code-centric programming model and shares the drawbacks of such a model. Additionally, TSpaces is implemented in the Java programming language and therefore requires a Java Virtual Machine, or other means of executing Java bytecode, such as a Java-capable microprocessor. Therefore, TSpaces may be inappropriate for small-footprint devices which cannot devote sufficient resources for executing Java bytecode.

It is desirable in object oriented distributed systems to be able to locate object repositories and find particular objects within those repositories. As mentioned above, the Jini look-up server may not be practical for small devices with small memory footprints. A more efficient mechanism for locating object stores may be desirable.

Distributed object access also desires a fair and efficient sharing mechanism. As described above Jini currently uses a leasing mechanism to share objects. However, Jini leases are time based which may result in a number of problems. For example, the current object holder might have no idea how long to lease an object and may hold it too long. Also, the use of time-based leases may require that time be synchronized between multiple machines. Moreover time based leasing may require operating system support. Also, Jini leases are established and released via RMI. Thus, the Jini leasing mechanism suffers from the above-noted problems with using RMI. Other leasing mechanisms may be desirable.

Generally speaking, it is desirable for small memory foot print mobile client devices to be able to run a variety of services, both legacy and new, in a distributed environment. The types of small clients may include cell phones and PDA's with a variety of different networking interfaces, typically low bandwidth. Often these devices have very small displays with limited graphics, but they could include laptops and notebook computers, which may have a larger display and more sophisticated graphics capabilities. The services may be a wide range of applications as well as control programs for devices such as printers. It is desirable for a mobile client to be able to use these services wherever they may be.

A mobile client will often be at a temporary dynamic network address, so networking messages it sends cannot be routed beyond that networking interface (otherwise there may be collisions when two different clients on different networks have the same dynamic address). Mobile clients often do not have the capability for a full function browser or other sophisticated software. The displays may limit the client from running certain applications. Traditional application models are based on predetermined user interface or data characteristics. Any change to the application requires recompilation of the application.

It may be desirable for such clients to have a mechanism for finding and invoking distributed applications or services. The client may need to be able to run even large legacy applications which could not possibly fit in the client's memory footprint. As discussed above, current technology, such as Jini, may not be practical for small footprint devices. The pervasiveness of mobile thin clients may also raise additional needs. For example, it may be desirable to locate services based on the physical location of the user and his mobile client. For example, information about the services in a local vicinity may be very helpful, such as local restaurants, weather, traffic maps and movie info.

A distributed computing model should provide clients with a way to find transient documents and services. It may be desirable to have a mechanism for finding general-purpose documents (including services and/or service advertisements), where the documents are expressed in a platform-independent and language-independent typing such as that provided by eXtensible Markup Language (XML). Current approaches, including lookup mechanisms for Jini, Universal Plug and Play (UPnP), and the Service Location Protocol (SLP), do not support such a general-purpose document lookup mechanism. For example, the Jini lookup mechanism is limited to Java Language typing and is therefore not language-independent. UPnP and SLP support a discovery protocol only for services, not for general-purpose documents.

Similarly, information about computing resources, such as printers in a particular location, may be helpful. Current technologies do not provide an automatic mechanism for locating services based on physical location of the client. Another need raised by thin mobile clients is that of addressing the human factor. Thin mobile clients typically do not contain ergonomic keyboards and monitors. The provision of such human factor services and/or the ability to locate such services in a distributed computing environment may be desirable.

SUMMARY OF THE INVENTION

The problems outlined above are in large part solved by various embodiments of a system and method for searching for documents within spaces within a distributed computing environment. A distributed computing environment may rely on "spaces" or object repositories to provide a rendezvous mechanism or catalyst for the interaction between clients and services. Service providers may advertise services in a space. Clients may find the advertisements in a space and use the information from an advertisement to access a service using an XML (eXtensible Markup Language) messaging mechanism of the distributed computing environment. Many spaces may exist, each containing XML advertisements that describe services or content. Thus, a space may be a repository of XML advertisements of services and/or XML data, which may be raw data or advertisements for data, such as results.

In one embodiment, a space itself is a service. Like any service, a space has an advertisement, which a client of the space must first obtain in order to be able to run that space service. A space's own advertisement may include an XML schema, a credential or credentials, and a URI (Uniform Resource Identifier) which indicate how to access the space. A client may construct a gate from a space service's advertisement in order to access the space. A client of a space may itself be a service provider seeking to advertise in that space or modify an existing advertisement. Or a client of a space may be an application seeking to access a service or content listed by the space. Thus, spaces may provide catalysts for the interaction between clients and services in the distributed computing environment.

A space may include a collection of named advertisements. A space may be created with a single root advertisement that describes the space itself. Additional advertisements may be added to a space. An advertisement's name may locate the advertisement within the space, including specifying any necessary graphing information such as a hierarchy of names. In a preferred embodiment, the structure of a space is not dictated by the distributed computing environment. That is, spaces may be structured as, for example, a flat un-related set of advertisements or a graph of related advertisements (e.g. commercial database). Since, in a preferred embodiment, the distributed computing environment does not dictate how a space actually stores its content, spaces may be supported by small to large devices. For example, a simple space may be tailored to fit on small devices, such as PDAs. More advanced spaces may be implemented on large severs employing large commercial databases.

As mentioned above, a space may contain advertisements for services in the distributed computing environment. An advertisement may provide a mechanism for addressing and accessing services and/or content within the distributed computing environment. An advertisement may specify a URI for a service. In some embodiments, the URI may allow for the service to be accessible over the Internet. An advertisement may also include an XML schema for the service. The XML schema may specify a set of messages that clients of the service may send to the service to invoke functionality of the service. The XML schema may define the client-service interface. Together, the URI and the XML specified in an advertisement may indicate how to address and access the service. Both the URI and schema may be provided in XML as an advertisement in a space. Thus, a mechanism for addressing and accessing a service in a distributed computing environment may be published as an advertisement in a space. Clients may discover a space and then lookup individual advertisement for services or content. Spaces and all advertisements within a space may be addressed using URIs. In one embodiment, space and advertisement names may follow URL (Uniform Resource Locator) naming conventions. The use of URIs, e.g. URLs, for addressing spaces may allow spaces to be addressable throughout the Internet, in some embodiments.

Once a client of a space finds the advertisement of a space service, that client of the space may run the space service, as it would any other service. Note that the client of the space service may be another service (e.g. a service seeking to advertise in the space). In one embodiment, to run a space service, the client of the space may first run an authentication service for the space to obtain an authentication token. The authentication service may be specified in the service advertisement of the space service. The client of the space uses the authentication token, the XML schema of the space (from space's service advertisement), and the URI of the space (from space's service advertisement) to construct a gate for the space. The client of the space may then run the space service by using the gate to send messages to the space service.

For embodiments employing authentication, when the space service receives the first message from the client, with the authentication token embedded, the space service uses the same authentication service (specified in the service advertisement of the space service) to authenticate the client, thus establishing its identity. The space service may determine the client's capabilities and bind them to the authentication token.

A client of a space may run various space facilities by sending messages to the space service. In one embodiment, when a client of a space sends a request to the space service, it passes its authentication token in that request, so the space service can check the request against the client's specific capabilities.

Each space is typically a service and may have an XML schema defining the core functionality of the space service. The XML schema may specify the client interface to the space service. In one embodiment, all space services may provide a base-level of space-related messages. The base-level space functionality may be the basic space functionality that is capable of being used by most clients, including small devices such as PDAs. It may be desirable to provide for additional functionality, e.g. for more advanced clients. Extensions to the base-level space may be accomplished by adding more messages to the XML schema that advertises the space. For example, in one embodiment, the base-level messages do not impose any relationship graph upon the advertisements. Messages, for example, to traverse a hierarchy of advertisements may be a space extension. Providing such additional functionality may be done by providing one or more extended XML space schemas or schema extensions for a space. The extended schemas may include the base schema so that clients of an extended space may still access the space as a base space.

In one embodiment, a space may provide a facility for a client to instantiate a service advertised in the space. Service instantiation is the initialization done that allows a client to be able to run a service. To instantiate a service, a client may first select one of the service advertisements published in the space. The client may use the various facilities, such as the look up facility, provided by the space to look up the various advertisements in the space. Then the client may request the space to instantiate the service.

In one embodiment, service instantiation may include the following actions. After the client requests the space service to instantiate the selected service, the space service may then verify the client is allowed to instantiate the requested service. The space service may perform this verification by examining the an authentication token included in the clients message. The authentication token is the credential the client received when it established a session with the space service. The space service may verify if the client is allowed to instantiate the requested service according to the client's authentication token and capabilities indicated for that client.

Assuming the client is authorized, the space service may also obtain a lease on the service advertisement for the client with the lease request time specified by the client. The space service may then send a message to the client which includes the allocated lease and the service advertisement of the service. In one embodiment, the client may run an authentication service specified in the service advertisement and obtain an authentication token. Next, the client may construct a gate for the service (for example, using the authentication token and the XML schema and service URI from the advertisement). The above described communication between the client and space service is performed using the XML messaging of the distributed computing environment. The client may then run the service using the constructed gate and XML messaging. The service may similarly construct a service gate for XML message communication with the client.

In one embodiment, a client may interact with a space via lookup messages to find documents within the space. A client may send a lookup message to a space. The space may comprise a network-addressable storage location which is operable to store one or more documents. The stored documents may be expressed in a data representation language such as eXtensible Markup Language (XML). The lookup message may specify desired characteristics of the stored documents. In one embodiment, the documents may include XML service advertisements and XML device advertisements as well as general-purpose XML documents. For example, the XML documents in the space may include the results of a service as expressed in XML.

A set of documents which match the lookup message may be discovered. The discovered documents may include any stored documents which meet the desired characteristics specified in the lookup message. Zero or more stored documents may match the desired characteristics. In one embodiment, the lookup message may include a desired name. In one embodiment, the desired name specified in the lookup message may include one or more wildcards. Each of the discovered documents may then have a name that matches the desired name, and the names may identify the discovered documents within the space. In one embodiment, the lookup message may include a desired schema which is expressed in the data representation language. Each of the discovered documents may have a schema or part of a schema that matches the desired schema. In one embodiment, the lookup message may include both a desired name and a desired schema. In this case, the set of discovered documents may include both discovered documents having a name that matches the desired name and discovered documents having a schema that matches the desired schema. In one embodiment, the lookup message may include neither a desired name nor a desired schema. In this case, the lookup message is essentially a request for all documents in the space, and the set of discovered documents may include substantially all the documents that are stored in the space.

After the matching documents are found, the space may send a lookup response message to the client. In one embodiment, the lookup response message may include the names of the discovered documents. In one embodiment, the lookup response message may include an advertisement for each of the zero or more discovered documents. Each advertisement may include information which is usable by the client to obtain the respective discovered document or access the resource (e.g., a service) that the document advertises. In one embodiment, each advertisement may include a Uniform Resource Identifier (URI) at which the respective discovered document (or resource, such as a service, advertised by the document) is accessible. In one embodiment, at least one of the discovered documents may be an advertisement for a service. The advertisement for the service may include a schema, wherein the schema specifies one or more messages usable to invoke one or more functions of the service. The advertisements may be expressed in the data representation language, such as XML. In one embodiment, the lookup message and the lookup response message are expressed in a data representation language such as XML.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is an illustration of a conventional distributed computing technology stack;

FIG. 2 is an illustration of a distributed computing environment programming model according to one embodiment;

FIG. 3 is an illustration of messaging and networking layers for a distributed computing environment according to one embodiment;

FIG. 4 is an illustration of a discovery service for finding spaces advertising objects or services in a distributed computing environment according to one embodiment;

FIG. 5 illustrates client profiles supporting static and formatted messages for a distributed computing environment according to one embodiment;

FIG. 6 is an illustration of a distributed computing model employing XML messaging according to one embodiment;

FIG. 7 illustrates a platform independent distributing computing environment according to one embodiment;

FIG. 8 is an illustration of a distributed computing model in which services are advertised in spaces according to one embodiment;

FIG. 9 is an illustration of a distributed computing model in which results are stored in spaces according to one embodiment;

FIG. 10 is an illustration of client and service gates as messaging endpoints in a distributed computing model according to one embodiment;

FIG. 10b is an illustration a message endpoint generation according to a schema for accessing a service according to one embodiment.

FIG. 11a illustrates gate creation in a distributed computing environment according to one embodiment;

FIG. 11b illustrates gate creation and gate pairs in a distributed computing environment according to one embodiment;

FIG. 12 is an illustration of possible gate components in a distributed computing environment according to one embodiment;

FIG. 13 is an illustration of proxy client for a conventional browser to participate in the distributed computing environment according to one embodiment;

FIG. 14 illustrates the use of a method gate to provide a remote method invocation interface to a service in a distributed computing environment according to one embodiment;

FIG. 15 is an illustration of the use of a space in a distributed computing environment according to one embodiment;

FIG. 16 illustrates advertisement structure according to one embodiment;

FIG. 17 illustrates one example of advertisement state transitions that an advertisement may undergo during its lifetime according to one embodiment;

FIG. 18 is an illustration various space location mechanisms in a distributed computing environment according to one embodiment;

FIG. 19 is an illustration of space federations in a distributed computing environment according to one embodiment;

FIG. 20 is a flow diagram illustrating client formation of a session with a space service in a distributed computing environment according to one embodiment;

FIG. 21 is an illustration of a space event type hierarchy for one embodiment;

FIG. 22 is a flow diagram illustrating service instantiation in a distributed computing environment according to one embodiment;

FIG. 23 is an illustration of a default space in a distributed computing environment according to one embodiment;

FIG. 24 illustrates an example of a device bridging proximity-based devices onto another transport mechanism to allow the services provided by the proximity-based devices to be accessed by devices outside the proximity range of the devices, according to one embodiment;

FIG. 25 is an illustration of the use of lease renewal messages in a distributed computing environment according to one embodiment;

FIG. 26a is a flow diagram illustrating an authentication service providing an authentication credential to a client according to one embodiment;

FIG. 26b is a flow diagram expanding on step 1002 of FIG. 26a and illustrating an authentication service generating an authentication credential according to one embodiment;

FIG. 27 illustrates one embodiment of a bridging mechanism;

FIG. 28 illustrates an example of a space discovery protocol mapped to an external discovery service according to one embodiment;

FIG. 29 illustrates bridging a client external to the distributed computing environment to a space in the distributed computing environment according to one embodiment;

FIG. 30 is an illustration of a proxy mechanism according to one embodiment;

FIG. 31 illustrates one embodiment of a client with an associated display and display service according to one embodiment;

FIGS. 32A and 32B illustrate examples of using schemas of dynamic display objects according to one embodiment;

FIG. 33A illustrates a typical string representation in the C programming language;

FIG. 33B illustrates an example of a conventional string function;

FIG. 33C illustrates an efficient method for representing and managing strings in general, and in small footprint systems such as embedded systems in particular according to one embodiment;

FIG. 34 illustrates a process of moving objects between a client and a service according to one embodiment;

FIGS. 35a and 35b are data flow diagrams illustrating embodiments where a virtual machine (e.g. JVM) includes extensions for compiling objects (e.g. Java Objects) into XML representations of the objects, and for decompiling XML representations of (Java) objects into (Java) objects;

FIG. 36 illustrates a client and a service accessing store mechanisms in the distributed computing environment, according to one embodiment;

FIG. 37 illustrates process migration using an XML representation of the state of a process, according to one embodiment;

FIG. 38 illustrates a mobile client device accessing spaces in a local distributed computing network, according to one embodiment;

FIG. 39a illustrates a user of a mobile device discovering the location of docking stations, according to one embodiment;

FIG. 39b illustrates a mobile client device connecting to a docking station, according to one embodiment;

FIG. 40a illustrates an embodiment of embedded devices controlled by a control system and accessible within the distributed computing environment, according to one embodiment;

FIG. 40b illustrates a device control system connected via a network (e.g. the Internet) to embedded devices accessible within the distributed computing environment, according to one embodiment;

FIG. 41 is a flow diagram illustrating the spawning of a new space in a distributed computing environment according to one embodiment;

FIG. 42 is a flow diagram illustrating the secure spawning of a new space in a distributed computing environment according to one embodiment;

FIG. 43 is a flow diagram illustrating a search for spaces using a search service in a distributed computing environment according to one embodiment;

FIG. 44a is a flow diagram illustrating a method of storing results of a service in a space in a distributed computing environment according to one embodiment;

FIG. 44b is a flow diagram illustrating a method of storing results of a service in a space and notifying a client using an event in a distributed computing environment according to one embodiment;

FIG. 44c is a flow diagram illustrating a method of sending results of a service in a message to a client in a distributed computing environment according to one embodiment;

FIG. 44d is a flow diagram illustrating a method of returning results of a service using an advertisement in a distributed computing environment according to one embodiment;

FIG. 44e is a flow diagram illustrating a method of returning results of a service using an advertisement sent to a client in a message in a distributed computing environment according to one embodiment;

FIG. 44f is a flow diagram illustrating a method of returning results of a service using an advertisement stored in a space in a distributed computing environment according to one embodiment;

FIG. 44g is a flow diagram illustrating a method of returning results of a service using an advertisement stored in a space and notifying a client using an event in a distributed computing environment according to one embodiment;

FIG. 45 is a flow diagram illustrating a method of sending results of one service to another service in a distributed computing environment according to one embodiment;

FIGS. 46a and 46b are illustrations of a search service and its interaction with a client in a distributed computing environment according to one embodiment;

FIG. 47 is a flow diagram illustrating a search for documents within a space in a distributed computing environment according to one embodiment; and

FIG. 48 is a flow diagram illustrating the addressing of a service using an advertisement stored in within a space in a distributed computing environment according to one embodiment.

While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the drawings and detailed description thereto are not intended to limit the invention to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the present invention.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION

Overview of Embodiments for Distributed Computing

Turning now to FIG. 2, a distributed computing environment programming model is illustrated. The model includes API layer 102 for facilitating distributed computing. The API layer 102 provides an interface that facilitates clients connecting to services. The API layer 102 is concerned with the discovery of and the connecting of clients and services. The API layer 102 provides send message and receive message capabilities. This messaging API may provide an interface for simple messages in a representation data or meta-data format, such as in the eXtensible Mark-up Language (XML). Note that while embodiments are described herein employing XML, other meta-data type languages or formats may be used in alternate embodiments. In some embodiments, the API layer may also provide an interface for messages to communicate between objects or pass objects, such as Java objects. API's may be provided to discover an object repository or "space", find a particular object, claim and release an object, and write or take an object to or from the object repository. Objects accessible through API layer 102 may be represented by a representation data format, such as XML. Thus, an XML representation of an object may be manipulated, as opposed to the object itself.

API layer 102 sits on top of a messaging layer 104. The messaging layer 104 is based on a representation data format, such as XML. In one embodiment, XML messages are generated by messaging layer 104 according to calls to the API layer 102. The messaging layer 104 may provide defined static messages that may be sent between clients and services. Messaging layer 104 may also provide for dynamically generated messages. In one embodiment, an object, such as a Java object, may be dynamically converted into an XML representation. The messaging layer 104 may then send the XML object representation as a message. Conversely, the messaging layer 104 may receive an XML representation of an object. The object may then be reconstituted from that message.

In one embodiment, messages sent by messaging layer 104 may include several basic elements, such as an address, authentication credentials, security tokens, and a message body. The message system transmission and receive mechanisms may be completely stateless. Any notion of state may be embedded in the message stream between sender and receiver. Thus, message transmission may be done asynchronously. In a preferred embodiment, no connection model is imposed. Thus, transports such as TCP are not required. Also, error conditions may be limited to non-delivery or security exceptions.

Messaging layer 104 sits on top of a message capable networking layer 106. In a preferred embodiment, messaging layer 104 does not require that a particular networking protocol be used. TCP/IP and UDP/IP are examples of message capable protocols that may be used for message capable networking layer 106. However, other more specialized protocols such as the Wireless Application Protocol (WAP) may also be used. Other possible message protocols are IrDA and Bluetooth network drivers beneath the transport layer. Networking layer 106 is not limited to a single reliable connection protocol, such as TCP/IP. Therefore, connection to a larger variety of devices is possible.

In one embodiment, message capable network layer 106 may be implemented from the networking classes provided by the Java2 Micro Edition (J2ME) platform. The Java2 Micro Edition platform may be suitable for smaller footprint devices that do not have the resources for a full Java platform or in which it would not be efficient to run a full Java platform. Since J2ME already provides a message capable family of networking protocols (to support sockets), it follows that for the small footprint cost of adding messaging layer 104, distributing computing facilities may be provided for small devices that already include J2ME.

Message capable networking layer 106 may also be provided by the Java Development Kit's (JDK) java.net networking classes. Alternatively, any message capable networking facilities may be used for message capable networking layer 106. In a preferred embodiment, a reliable transport is not required, thus embedded devices supporting an unreliable data gram transport such as UDP/IP may still support the messaging layer.

Thus, thin clients may participate in a distributed computing environment by simply adding a thin messaging layer 104 above a basic networking protocol stack. As shown in FIG. 3, a basic system includes messaging layer 104 on top of a networking layer 106. The networking layer may provide for reliable messages, e.g. TCP, or unreliable messages, e.g. UDP. The Internet Protocol (IP) is shown in FIG. 3 as an example of protocol that may be used in networking layer 106. However, the distributed computing environment does not require IP. Other protocols may be used in the distributed computing environment besides IP. A network driver such as for Ethernet, Token Ring, Bluetooth, etc. may also be part of the networking layer. Many small clients already provide a network driver and transport protocol such as UDP/IP. Thus, with the addition of the thin XML based messaging layer, the device may participate in the distributed computing environment.

Thus, the foundation for the distributed computing environment is a simple message passing layer implemented on top of reliable connection and/or unreliable data grams. The messaging technology is very different from communications technologies employed in other distribution computing systems, such as Jini which employs the Java remote method invocation (RMI). The message passing layer 104 supports an asynchronous, stateless style of distributed programming, instead of the synchronous, state-full style predicated by RMI. Moreover, message passing layer 104 is based on a data representation language such as XML and thus copies data, but not code, from source to destination, unlike RMI. By using a representation data language, such as XML, messaging layer 104 may interoperate with non-Java and non-Jini platforms in a seamless fashion because Java code is not assumed on the sending or receiving end of a message. Moreover, unlike RMI, messaging layer 104 does not require a reliable transport mechanism such as TCP/IP.

The message passing layer may provide simple send( ) and receive( ) methods to send a message specified as an array or string of bytes, for example. The send( ) method may return immediately, performing the data transfer asynchronously. For flow control purposes a callback method may be supplied which is invoked in the event that the send( ) method throws an exception indicating it cannot handle the send( ) request. The receive( ) method may be synchronous and may return the next available message.

The message passing layer may also provide methods for storing XML representations of objects, services and content in "spaces". A space is named and accessed on the network using an URI (Uniform Resource Identifier). The URI may be a URL (Uniform Resource Locator) or a simpler version of a URL. In some embodiments, the URL class may be too large. For such embodiments a simpler resource locator may be used that specifies the protocol for moving the messages between client and server, protocol dependent host ID, protocol dependent port ID, and a space name.

An XML representation of an object may be added to a space using a write( ) method provided by the messaging layer. In one embodiment, the object and the client-specified name may be supplied as parameters. In one embodiment, the write method may translate the object into its XML representation. A take( ) method may be provided to return the object and remove it from the space. A find( ) method may be provided to return a specified object from its XML representation in a space. The find( ) method may also be used to return an array of matching objects in a space given a class. Each of these space methods is implemented using the message-passing layer. A lease mechanism may also be provided, as described in more detail below.

A discovery service may be provided for clients as a general search facility that may be used by a client to locate a particular space. Rather than attempt to define a complicated search protocol which may not be feasible for a thin client to implement, the discovery service may offload the actual search to XML-based search facilities, leaving the discovery service simply to provide interface functionality to the client. The approach is illustrated in FIG. 4. In one embodiment, the discovery service receive( ) a string specifying something to locate, and it sends an XML message to a known discovery front-end (perhaps found in a default space), which then parses the string and makes a corresponding XML query to a search facility (which may be an internet search facility). The discovery front-end may parse what it obtains from the search facility and repackage it as an array of strings (each string may be a URI for each found space) which it may send in an XML message to the client. It should be noted that the discovery service does not require that the messaging be atop a connection-oriented transport. Thus, even very thin clients that do not have TCP could use such a discovery service. The discovery front-end makes it possible for the client to discover spaces without a browser or search facility on the client. The client only needs a simple facility that sends a string that specifies keywords to the front-end, which interfaces with a search facility.

A client may be any platform that can send a message using at least a subset of the API and messaging layers. In one embodiment the API layer may provide for both static (or raw) and formatted (or cooked) messages. A server may be any platform capable of receiving and fulfilling message requests. An explicit raw message send may be provided that moves a series of bytes from a client to a server or to another client. The message type may be specified as reliable (e.g. TCP) or unreliable (e.g. UDP). The smallest of devices may use raw unreliable message passing as their sole means of participation in the distributed computing environment. The device may use these messages to announce its presence and its status. Such small devices may also receive raw messages to implement certain functions, such as turning a feature on or off.

Message-based services such as spaces may send and receive reliable formatted messages. A space message may be formatted with a well-defined header and with XML. In one embodiment, a formatted message send may occur when a client uses a space method to claim, write, or take objects from a space. The message contents may be dynamically formatted in XML and contain well-defined headers. FIG. 5 illustrates client profiles supporting formatted and static messages. By using static messages, small devices may use a smaller profile of code to participate in the distributed computing environment. For example, a small device could just send basic pre-defined messages. Depending on the client, the static pre-defined messages may consume a small amount of memory (e.g. <200 bytes). Static messages may also be an option even for larger devices. On the other hand, the dynamic XML messages may be useful when object values are not known at compile time.

Turning now to FIG. 6, a distributed computing model is illustrated that combines a messaging system with XML messages and XML object representation. The platform independence of XML may be leveraged so that the system may provide for a heterogeneous distributed computing environment. Thus, client 110 may be implemented on almost any platform instead of a particular platform like Java. The messaging system may be implemented on any network capable messaging layer, such as Internet protocols (e.g. TCP/IP or UDP/IP). Thus, the computing environment may be distributed over the Internet. In one embodiment, the messaging system may also use shared memory as a quick interprocess message passing mechanism when the client and/or space server and/or service are on the same computer system. The distributed computing model of FIG. 6 may also be very scalable because almost any size client can be configured to send and/or receive XML messages.

As shown in FIG. 6, two kinds of software programs may run in the distributed computing model: services 112 and clients 110. Services 112 may advertise their capabilities to clients wishing to use the service. The services 112 may advertise their capabilities in spaces 114. As illustrated in FIG. 7, clients 110 and services 112 may or may not reside within the same network device. For example, devices 120 and 124 each support one client, whereas service 112a and client 110b are implemented in the same device 122. Also, as illustrated in FIG. 7, no particular platform is required for the devices to support the clients and services. For example, device 120 is Java based, whereas device 124 provides a native code runtime environment.

A device may be a networking transport addressable unit. Example devices include, but by no means are limited to: PDAs, cellular/mobile phones, notebook computers, laptops, desktop computers, more powerful computer systems, even supercomputers. Both clients and services may be URI-addressable instances of software (or firmware) that run on devices. Using the distributed computing environment architecture, a client may run a service. A space is a service that manages a repository of XML documents. Even though it is redundant, the term, space service, may be used herein for readability. A software component may be both a client and service at different times. For example, when a service uses a space (e.g. to advertise itself), that service is a client of the space.

FIG. 8 illustrates the basic model of the distributed computing environment in one embodiment. The distributed computing environment may connect clients 110 to services 112 throughout a network. The network may be a wide area network such as the Internet. The network may also be a combination of networks such as a local area network (LAN) connected to a wireless network over the Internet. As shown in FIG. 8, a service 112 publishes an advertisement 132 for itself (represented in XML) in a space 114. The advertisement 132 specifies the service's XML schema and URI address. Then, a client 110 may look up the advertisement 132. The client 110 may use the advertisement 132 to instantiate a gate 130. The gate 130 allows the client 110 to run the service 112, by sending (and receiving) XML messages to (and from) the service 112.

Some results of running a service may be returned to the client in an XML message. However, since other results may be too large for a small client to receive and consume at once, a service 112 may put those results or an XML representation of the results 134 in a space 114, as shown in FIG. 9, and return them by reference (in an XML message) to the client 110, rather than by value. Examples of methods of returning a reference to results include, but are not limited to: returning in the message a URI referencing the results in a space, and: returning in the message an XML document including the URI of the results. Later, the client 110 may access the results, or pass them by reference to another service. The space in which results may be stored may be different from the space in which the service is advertised.

In one embodiment, the distributed computing environment uses XML for content definition, advertisement and description. New content for the distributed computing environment (messages and advertisements for example) are defined in XML. Existing content types (e.g. developed for other environments) may also be described using XML as a level of indirection (meta-data). XML provides a powerful means of representing data throughout a distributed system because, similar to the way that Java provides universal code, XML provides universal data. XML is language agnostic and is self-describing. The XML content may be strongly typed and validated using schemas. Using a provided XML schema, the system may ensure that only valid XML content is passed in a message. XML content may also be translated, into other content types such as HTML and WML. Thus, clients that do not understand XML may still use the distributed computing environment services.

In one embodiment, the distributed computing environment messages may define the protocol used to connect clients with services, and to address content in spaces and stores. The use of messages to define a protocol allows many different kinds of devices to participate in the protocol. Each device may be free to implement the protocol in a manner best suited to its abilities and role. For example, not all devices are capable of supporting a Java runtime environment. The distributed computing environment protocol d