United States Patent (19)
`Van Hoff et al.
`
`54 METHOD FOR THE DISTRIBUTION OF
`CODE AND DATA UPDATES
`
`75 Inventors: Arthur Van Hoff, Mountain View;
`Jonathan Payne, Santa Clara; Sami
`Shaio, Menlo Park, all of Calif.
`73 Assignee: Marimba, Inc.
`
`21 Appl. No.: 08/690,257
`22 Filed:
`Jul. 24, 1996
`51 Int. CI.
`
`O
`
`-1 - O
`
`- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
`
`C06F 17/30
`
`USOO5919247A
`Patent Number:
`11
`(45) Date of Patent:
`
`5,919,247
`Jul. 6, 1999
`
`5,619,716 4/1997 Nonaka et al..
`5,628,005 5/1997 Hurvig.
`5,634,052 5/1997 Morris.
`5,713,017
`1/1998 Lin et al..
`OTHER PUBLICATIONS
`Baron, Robert J. and L.G. Shapiro, Data Structures and their
`Implementation, 1980, p. 150 and pp. 218-219, Van Nos
`trand Reinhold Company, New York, New York, USA.
`Bentley, Jon L Multidimensional Binary Search Trees in
`Datab
`Applicat
`IEEE T
`t
`Soft
`OSC
`Ical IOnS,
`SCIOS O SOLWC
`Engineering, Jul. 1979, pp. 333-340, vol. SE-5, Institute of
`Electrical and Electronics Engineers, Inc., New York, New
`
`York, USA.
`
`56)
`
`52) U.S. C. - - - - - - - - - - - - - - - - - - - - - - - - - - - 709/217; 707/201; 395/712
`
`58 Field of Search ......................... 395/200.31, 200.33,
`395/200.49,395,47,395.59,684, 20047,
`200.48, 712; 707/201, 203
`
`yp
`Gotlieb, C.C. and L.R. Gotlieb, Data Twpes and Structures,
`1978, pp. 169-185, Prentice Hall Inc., Englewood Cliffs,
`New Jersey, USA.
`(List continued on next page.)
`Primary Examiner Dung C. Dinh
`References Cited
`Attorney, Agent, or Firm-Charles E. Gotlieb
`U.S. PATENT DOCUMENTS
`57
`ABSTRACT
`4,432,057 2/1984 Daniell et al..
`-
`4,468,728 8/1984 Wang.
`A System and method for distributing Software applications
`4,558,413 12/1985 Schmidt et al. ........................ 7071203
`and data to many thousands of clients over a network. The
`4,611,272 9/1986 Lomet.
`applications are called “channels', the Server is called the
`4,658,093 4/1987 Hellman.
`“transmitter', and the client is called the “tuner'. The use of
`4,714,992 12/1987 Gladney et al..
`channels is based on Subscription. The end-user needs to
`4,714,996 12/1987 Gladney et al..
`4.866,611
`9/1989 Cree et al..
`Subscribe to channel before it can be executed. When the
`4,875,159 10/1989 Cary et al..
`end-user Subscribes to a channel the associated code and
`4,897,781
`1/1990 Chang et al. .
`data is downloaded to the local hard-disk, and once down
`5,113,519 5/1992 Johnson et al..
`loaded the channel can be executed many times without
`5,115,504 5/1992 Belove et al..
`requiring further network acceSS. Channels can be updated
`5,155,847 10/1992 Kirouac et al..
`automatically at regular intervals by the tuner, and as a result
`5,341,477 8/1994 Pitkin et al. ....................... 395/200.56
`the end-user is no longer required to manually install Soft
`5,377,329 12/1994 Seitz.
`5,388.255
`2/1995 Pytlik et al. ................................ 707/4 WC updates, instead these Software and data updates C
`5,408,619 4/1995 Oran.
`automatically downloaded and installed in the background.
`5,434,994 7/1995 Shaheen et al..
`This method of automatic downloading of updates achieves
`5,471,629 11/1995 Risch.
`for the client the same result as the broadcast distribution of
`5,473,772 12/1995 Halliwell et al. ....................... 395/712
`Software over a connection based network, but wherein the
`5,491,820 2/1996 Belove et al..
`5,574,906 11/1996 Morris.
`client initiates each update request without requiring any
`5,581,764 12/1996 Fitzgerald et al. ...................... 395/703
`Special broadcast networking infrastructure.
`5,586,322 12/1996 Beck et al. .............................. 707/200
`5,606,705 2/1997 Randall et al..
`61 Claims, 13 Drawing Sheets
`
`700-
`
`77
`
`-
`
`fa
`
`SERVERSYSE
`
`cent SYSEM
`
`Network
`
`SERWEr SYSTEM
`
`CENT SYSE
`
`77
`
`
`
`WENT
`SYSTEM
`
`at
`
`fe
`
`73
`
`Proxy systew
`
`Page 1
`
`Lenovo Exhibit 1004
`
`

`

`5,919,247
`Page 2
`
`OTHER PUBLICATIONS
`
`Gull, W.E. and M.A. Jenkins, Recursive Data Structures in
`APL, Communications of the ACM, Jan. 1979, pp. 79–96,
`Vol. 22, No. 1, ASSociation for Computing Machinery, Inc.,
`Baltimore, Maryland, USA.
`Lee, D.T. and C.K. Wong, Quintary Trees: A File Structure
`for Multidimensional Database Systems, Sep. 1980, pp.
`339-353, vol. 5, No. 3, Association for Computing Machin
`ery, Inc., Baltimore, Maryland, USA.
`Tremblay, Jean-Paul and Paul G. Sorenson, An Introduction
`to Data Structures with Applications, 1984, pp. 811-826,
`Second Edition, McGraw-Hill Book Company, New York,
`New York, USA.
`Brown, Bradley J., Checksum Methodology as a Configu
`ration Management Tool, The Journal of Systems and Soft
`ware, Jun. 1987, pp. 141-143, vol. 7, Elsevier Science
`Publishing Co., Inc., New York, New York, USA.
`Segal, Mark E., and O. Frieder, Dynamically Updating
`Distributed Software: Supporting Change in Uncertain and
`Mistrustful Environments, Conference on Software Mainte
`nance-1989, Oct. 16–19, 1989, pp. 254-261, IEEE Com
`puter Society Press, Piscataway, New Jersey, USA.
`Danzig, Peter B., R. S. Hall and M. F. Schwartz, A Case for
`Caching File Objects Inside Internetworks, Proceedings:
`SIGCOM 93-Ithaca N.Y., 1993, pp. 239-248, Association
`for Computing Machinery, Inc., Baltimore, Maryland, USA.
`Wedde, Horst F. et al., Distributed Management of Repli
`cated and Partitioned Files Under Dragon Slayer, Confer
`ence Publication: Compsac90, The Fourteenth Annual Inter
`national Computer Software and Applications Conference,
`Oct. 1990, pp. 436–441, Institute of Electrical and Electron
`ics Engineers, Inc., New York, New York, USA.
`Pilarski, Slawomir, and T. Kameda, A Novel Checkpointing
`Scheme for Distributed Database Systems, Proceedings of
`the Ninth ACM SIGACT-SIGMOD-SIGART Symposium
`on Principles of Database Systems, Apr. 2-4, 1990, pp.
`368-378, ACM Press, Baltimore, MD., USA.
`Teorey, Toby J. and J.P. Fry, Design of Database Structures,
`1982, pp. xiii-XV and 3-492, Prentice-Hall, Englewood
`Cliffs, New Jersey, USA.
`Bentley, Jon Louis, and J.H. Friedman, Data Structures for
`Range Searching, Computing Surveys: The Survey and
`Tutorial Journal of the ACM, Dec. 1979, pp. 397–409, vol.
`11, No. 4, ASSociation for Computing Machinery, Inc.,
`Baltimore, Maryland, USA.
`Bentley, Jon Louis, Multidimensional Binary Search Trees
`Used for ASSociative Searching, Communications of the
`ACM, Sep. 1975, pp. 509–517, vol. 18, No. 9, Association
`for Computing Machinery, Inc., Baltimore, Maryland, USA.
`Date, C.J., An Introduction to Database Systems, 1981, pp.
`1–61, 97-115, 159-181, 237-273, 279-337, and 386-387,
`Third Edition, Addison-Wesley, Reading, Massachusetts,
`USA.
`Korth, Henry F., and A. Silberschatz, Database System
`Concepts (1 ed.), 1986, pp. 265-272, McGraw-Hill Book
`Company, New York, New York, USA.
`Nievergelt, J., Hinterberger, H., and K.C. Sevcik, The Grid
`File: An Adaptable, Symmetric Multikey File Structure,
`ACM Transactions on Database Systems, Mar. 1984, pp.
`37-71, vol. 9, No. 1, Association for Computing Machinery,
`Inc., Baltimore, Maryland, USA.
`
`Dart, Susan A., “The Past, Present and Future of Configu
`ration Management, Technical Report, Software Engineer
`ing Institute, Jul. 1992, pp. 1-28, Carnegie Mellon Univer
`sity, Pittsburgh, PA USA.
`Dart, Susan, “Concepts in Configuration Management Sys
`tems.” Article, Software Engineering Institute, Jun. 12-14,
`1991, Carnegie Mellon University, Pittsburgh, PA, USA.
`Hiller, Thomas, “SUP-das Software Update Protocol der
`Carnegie-Mellon Universitat.” Feb. 2, 1997 World Wide
`Web Page. German Language Document: A concise expla
`nation is attached.
`Kumar, Puneet, “Coping with Conflicts in an Optimistically
`Replicated File System.” Article, Nov. 8–9, 1990, pp. 60–64,
`School of Computer Science, Carnegie Mellon University,
`Pittsburgh, PA, USA.
`Downing, Alan R., et. al., “OSCAR: A System for Weak
`Consistency Replication,” Article, Nov. 8–9, 1990, pp.
`26-30, Information and Telecommunications Sciences Cen
`ter, SRI International, Menlo Park, CA, USA.
`Faloutsos, Christos, “Multiattribute Hashing. Using Gray
`Codes,” Article, Department of Computer Science, 1986, pp.
`227–238, University of Maryland, College Park, MD, USA.
`Feiler, Peter, and Downey, Grace, “Transaction-Oriented
`Configuration Management: A Case Study, Technical
`Report, Software Engineering Institute, Nov. 1990, pp.
`9-23, Carnegie Mellon University, Pittsburgh, PA USA.
`Feiler, Peter, and Downey, Grace, “Tool Version Manage
`ment Technology: A Case Study, Technical Report, Soft
`ware Engineering Institute, Nov. 1990, pp. 1-30 Carnegie
`Mellon University, Pittsburgh, PA USA.
`Feiler, Peter, “Software Configuration Management:
`Advances in Software Development Environments.” Article,
`Software Engineering Institute, Mar. 9 1990, pp. 1-12,
`Carnegie Mellon University, Pittsburgh, PA, USA.
`Cooper, Michael A., “Overhauling Rdist for the 90’s.”
`Article, Proceedings of the Sixth Systems Administration
`Conference (LISA VI), USENIX Association, Oct., 1992,
`pp. 175-188, Long Beach, CA, USA.
`Brown, A., et al., “The State of Automated Configuration
`Management,” Annual Technical Review, Sep. 1991, pp.
`1-52, Software Engineering Institute, Carnegie Mellon Uni
`versity, Pittsburgh, PA, USA.
`Brown, Mark R. and Ellis, John R., “Bridges: Tools to
`Extend the Vesta Configuration Management System,”
`Article, System Research Center, Digital Equipment Cor
`poration, Jun. 14, 1993, pp. 1-42, Palo Alto, CA, USA.
`Bauer, Michael A., “Naming and Name Management Sys
`tems: A Survey of the State of the Art,” Technical Report
`241, Jun. 1989, pp. 1-83, Distributed Directories Labora
`tory, Department of Computer Science, The University of
`Western Ontario, Ontario, Canada.
`Bauer, Michael A., et al., “Replication Strategies for X.500:
`Experiments with a Prototype X.500 Directory,” Technical
`Report 279, Oct. 1990, pp. 1-36, Distributed Directories
`Laboratory, Department of Computer Science, The Univer
`sity of Western Ontario, Ontario, Canada.
`Bennett, J.M. and Bauer, Michael A., “An Analysis of
`Replication Strategies for X.500-like Distributed Directo
`ries,” Proceedings, Workshop On the Management of Rep
`licated Data, Nov. 8–9, 1990, pp. 137-142 IEEE Comput.
`Soc. Press Los Alamitos, CA.
`
`Page 2
`
`

`

`5,919,247
`Page 3
`
`Broder, Andrei Z., “Some applications of Rabin's finger
`printing method,'Article, presented at workshop-Sequences
`II Methods in Communication, Security, and Computer
`Science, Jun. 17-21, 1991, pp. 143-152, Springer-Verlag,
`New York, USA, Published 1993.
`Broder, Andrei Z., et al., “Trading Space for Time in Undi
`rected s-t Connectivity,” Article, May 7, 1991. pp. 1-14,
`Digital Equipment Corporation, Systems Research Center,
`Palo Alto, CA, USA.
`Barbara, Daniel and Lipton, Richard J., “A Class of Ran
`domized Strategies for Low-Cost Comparison of File Cop
`ies,” Article, Apr. 1991, pp. 160-179, vol. 2, No. 2, IEEE
`Transactions On Parallel And Distributed Systems, Princ
`eton, NJ, USA.
`IBM, “Administrator's Guide” IBM Distributed Change
`Management Facility /MVS, Version 1, Release 1, 1 edi
`tion, Aug. 1990, pp. 1-64, Cary, NC, USA.
`Metzner, John A., “A Parity Structure for Large Remotely
`Located Replicated Data Files”, Article, IEEE Transactions
`on Computers vol. C 32, No. 8, Aug. 1983, pp. 727-730,
`IEEE Computer Society Press, Washington, D.C., USA.
`Schwarz, Thomas, et al., “Low Cost Comparisons of File
`Copies.” Technical Report, UCSD, Proc. Of the 10' inter
`national Conference on Distributed Computing Systems,
`May/Jun., 1990, pp. 196-202, IEEE Computer Society
`Press, Washington, D.C., USA.
`Sarin, Sunil, Floyd, Richard, and Phadnis, Nilkanth, “A
`Flexible Algorithm for Replicated Directory Management,”
`Article, Proc. Of the 9" International Conference on Dis
`tributed Computing Systems, 1989, pp. 456-464, IEEE,
`Cambridge, MA, USA.
`Rangajaran, Sampath and Fussell, Donald, "Rectifying Cor
`rupted Files in Distributed File Systems”, Article, 11"
`International Conference on Distributed Computing Sys
`tems, May, 1991, pp. 446-453, University of Maryland,
`College Park, MD, USA.
`Madej, Tom, “An Application of Group Testing to the File
`Comparison Problem.” Article, Proc. Of the 9" International
`Conference on Distributed Computing Systems, Jun., 1989,
`pp. 237-243, University of Illinois, Urbana, IL, USA.
`Barbara, Daniel, et al., “Exploiting Symmetries for
`Low-Cost Comparison of File Copies.” Article, 8" Inter
`national Conference on Distributed Computing Systems,
`Jun. 1988, pp. 471-479, IEEE Computer Society Press,
`Princeton University, Princeton, NJ.
`Fuchs, W.K., Wu, K. and Abraham, J., “Low-Cost Com
`parison and Diagnosis of Large Remotely Located Files,”
`Article, Proc. 5" Symposium on Reliability in Dist. Soft
`ware and Database Systems, Jan., 1986, pp. 67-73, IEEE,
`Computer Society Press, IL, USA.
`Pu, Calton, Noe, Jerre, and Proudfoot, Andrew, “Regenera
`tion of Replicated Objects: A Technique and its Eden
`Implementation.” IEEE Transactions on Software Engineer
`ing, vol. 4, No. 7, Jul. 1988, pp. 936–945, University of
`Wash., Seattle, WA, USA.
`Acharya, Arup, and Badrinath, B.R., “Delivering Multicast
`Messages in Networks with Mobile Hosts,” Article, Proc.
`13" International Conference on Distributed Computing
`Systems, May. 1993, pp. 292–299, IEEE Computer Society
`Press, Los Alamitos, CA, USA.
`Jia, Xiaohua, et al., "Highly Concurrent Directory Manage
`ment in the Galaxy Distributed System.” Article, Proc. 10"
`International Conference on Distributed Computing Sys
`tems, May-Jun., 1990, pp. 416–423, IEEE Computer Soci
`ety Press, Los Alamitos, CA, USA.
`
`Tugender, Ronald, “Maintaining Order and Consistency in
`Multi-Access Data.” Article, AFIPS Conference Proceed
`ings, 1979 National Computer Conference, Jun. 1979, pp.
`869-874, USC Information Science Institute, Marina Del
`Ray, CA, USA.
`Gopal, Inder and Segall, Adrian, “Directories for Networks
`with Casually Connected Users,” 1990, pp. 255-262,
`Elsevier Science Publishers B.V. (North-Holland.).
`Cheng, Hsiao-Chung and Sheu, Jang-Ping, “Design and
`Implementation of a Distributed File System.” Article, Soft
`ware-Practice and Experience, vol. 21(7), Jul., 1991, pp.
`657-675, John Wiley and Sons, Ltd.
`Grosse, Eric, “Repository Mirroring.” Article, ACM Trans
`actions on Mathematical Software, vol. 21, No. 1, Mar.
`1995, pp. 89–97, Murray Hill, NJ, USA.
`Howard, John H., “Using Reconciliation to Share Files
`between Occasionally Connected Computers,” Article, Proc.
`4" Workshop on Workstation Operating Systems, Oct.,
`1993, pp. 56–60, IEEE Computer Society Press, Cambridge,
`MA, USA.
`Courington, William, “The Network Software Environ
`ment,” Tech. Sun Microsystems Tech Report, 1989, pp.
`1-104, Sun Microsystems Mt. View, CA, USA.
`Nachbar, Daniel, “When Network File Systems Aren't
`Enough: Automatic Software Distribution Revisited.”
`Article, USENIX ASSociation, Summer Conference Pro
`ceedings, Jun., 1986, pp. 159-171, Bell Communications
`Research, Morristown, NJ, USA.
`Satdeva, Bjorn and Moriarty, Paul M., “Fdist: A Domain
`Based File Distribution System for a Heterogeneous Envi
`ronment,” USENIX Association, Proc. Of the 5' Large
`Installation Systems Administration Conference,(LISA V)
`Sep./Oct. 1991, pp. 109–125.
`Symborski, Carl, “Updating Software and Configuration
`Data in a Distributed Communications Network, Article,
`Hughes Network Systems, IEEE, 1988, pp. 331-8, German
`town, MD, USA.
`Shafer, Stephen and Thompson, Mary, “The SUP Software
`Upgrade Protocol, Sep. 1989, pp. 1-13, Carnegie Mellon
`University School of Computer Science, Pittsburgh, PA,
`USA.
`Prusker, Francis J. and Wobber, Edward P., “The Siphon:
`Managing Distant Replicated Repositories,” Article, Digital
`Equipment Corporation, Nov. 8-9, 1990, pp. 44-47, IEEE,
`Palo Alto, CA, USA.
`Cooper, Michael A., “Rdist Version 6.1, May 2, 1994, pp.
`1-4, University of Southern California Computing Services,
`Los Angeles, CA, USA.
`Paciorek, Noemi and Teller, Mark, “An Object Oriented,
`File System Independent, Distributed File Server,” Article,
`File Systems Workshop, USENIX Association, May 21,
`1992, pp. 45-62, Marlborough, MA, USA.
`Shasa, Dennis and Zhang, Kaizhong, “Fast Algorithms for
`the Unit Cost Editing Distance Between Trees.” Article,
`Journal of Algorithms II, 1990, 581-62, Academic Press,
`Inc, New York, NY, USA.
`Tai, Kuo-Chung, “The Tree to Tree Correction Problem,”
`Article, Journal of the ASSociation for Computing Machin
`ery, vol. 26, No. 3, Jul. 1979, pp. 422-433, Raleigh, NC,
`USA.
`Digital Equipment Corporation, “fingerprint/Src/finger
`print.i3.” SRC Modula-3, 1994, Digital Equipment Corpo
`ration, pp. 1-5, Maynard, MA, USA.
`
`Page 3
`
`

`

`5,919,247
`Page 4
`
`Loverso, Susan, et al., “The OSF/1 Unix Filesystem (UFS).”
`Article, USENIX, Winter, 1991, pp. 207-218, Dallas, Texas,
`USA.
`Lu, Shin-Yee, “A Tree to Tree Distance and It's Application
`to Cluster Analysis,” IEEE Transactions on Pattern Analysis
`and Machine Intelligence, vol. PAMI-1, No. 2, Apr., 1979,
`pp. 219–224, Syracuse University, Syracuse, NY, USA.
`Katz, Randy H., et al., “Version Modeling Concepts for
`Computer-Aided Design Databases,” Article, ASSociation
`for Computing Machinery, 1986, pp. 379–386, Berkeley,
`CA, USA.
`Kistler, James Jay, “Increasing File System Availability
`through Second Class Replication.” IEEE, Nov. 8-9, 1990,
`p. 69, Carnegie Mellon University, Pittsburgh, PA, USA.
`Kistler, James J. and Satyanarayanan, M., “Disconnected
`Operation in the Coda File System.” Article, ACM Trans
`actions on Computer Systems, vol. 10, No. 1, Feb. 1992, pp.
`3-25, ACM, Carnegie Mellon University, Pittsburgh, PA,
`USA.
`Harrison, Helen E., "So Many Workstations, So Little
`Time,” USENIX Association, Proc. Of the 6' Systems
`Administration Conference (LISA VI), Oct., 1992, pp.
`79-87, SAS Institute, Cary, NC, USA.
`Pukatzki, Dieter and Schumann, Johann, “Autoload; The
`Network Management System,” USENIX ASSociation,
`Proc. Of the 6' Systems Administration Conference (LISA
`VI), Oct., 1992, pp. 97-104, Germany.
`Rosenstein, Mark and Peisach, Ezra, “MkServ-Workstation
`Customization and Privatization,” USENIX ASSociation,
`Article, Proc. Of the 6" Systems Administration Conference
`(LISA VI), Oct., 1992, pp. 89–95, MIT Information Sys
`tems, Boston, MA, USA.
`Vangala, Ram R., et al., “Software Distribution and Man
`agement in a Networked Environment,” Article, USENIX
`Association, Proc. Of the 6" Systems Administration Con
`ference (LISA VI), Oct., 1992, pp. 163–170, NJ, USA.
`Zwicky, Elizabeth D., “Typecast: Beyond Cloned Hosts,”
`Article, USENIX Association, Proc. Of the 6' Systems
`Administration Conference (LISA VI), Oct., 1992, pp.
`73–78, SRI International, Menlo Park, CA, USA.
`Fletcher, Mark, “doit: A Network Software Management
`Tool.” Article, USENIX Association, Proc. Of the 6' Sys
`tems Administration Conference (LISA VI), Oct., 1992, pp.
`189-196, Cary, NC, USA.
`Tichy, Walter F., “An Introduction to the Revision Control
`System,” UNIX Programmer's Supplementary Documents
`vol. 1:13-1, Apr., 1986, pp. 13-1-13-21, Purdue University,
`West Lafayette, IN, USA.
`Eirich, Thomas, “Beam: A Tool for Flexible Software
`Update,” Article, 1994 LISA, Sep., 1994, pp. 75–82, Uni
`versity of Erlangen-Numberg, Germany.
`Rouillard, John P. and Martin, Richard B., “Depot-Lite: A
`Mechanism for Managing Software.” Article, 1994 LISA,
`Sep., 1994, pp. 83-91, Boston, Massachusetts, USA.
`Allman, Eric., “An Introduction to the Source Code Control
`System,” UNIX Programmer's Supplementary Documents
`vol. 1:14-1, Apr., 1986, pp. 14-1-14-15, Berkeley, CA,
`USA.
`Walpole, J. et al., “Maintaining Consistency in Distributed
`Software Engineering Environments.” Article, IEEE, Proc.
`Of the 8” International Conference on Distributed Comput
`ing Systems, Jun., 1988, (no page ifs), Bailrigg, United
`Kingdom.
`
`Osel, Peter, W. and Gansheimer, Wilfried, “OpenDist
`Incremental Software Distribution,” Article, USENIX ASSo
`ciation, Proc. Of the 9"Systems Administration Conference
`(LISA IX), Sep., 1995, pp. 181-193, Siemens AG,
`Munchen, Germany.
`Chiu, Sheng-Yang and Levin, Roy, “The Vesta Repository:
`A File System Extension for Software Development,”
`Article, Systems Research Center of Digital Equipment
`Corporation, Jun., 1993, pp. 1-32, Palo Alto, CA, USA.
`Manheimer, Kenneth, et al., “The Depot: A Framework for
`Sharing Software Installation AcroSS Organizational and
`UNIX Platform Boundaries.” Article, LISA IV, Oct., 1990,
`pp. 37-45.
`Jones, George M. and Romig, Steven M., “Cloning Cus
`tomized Hosts (or Customizing Cloned Hosts).” Article,
`LISAV, Sep./Oct., 1991, pp. 233–241, Ohio State Univer
`sity, Columbus, OH, USA.
`Rich, Kenneth and Leadley, Scott, “hobgoblin: A File and
`Directory Auditor,” Article, LISA V, Sep./Oct., 1991, pp.
`199-206, University of Rochester, Rochester, NY, USA.
`Wuu, Gene T.J. and Bernstein, Arthur, J., “Efficient Solu
`tions to the Replicated Log and Dictionary Problems.” Proc.
`Of the 3' PODC Conference Proceedings, ACM, 1984, pp.
`57-66, ACM Press, Department of Computer Science, Suny
`Stony Brook, Long Island, NY, USA.
`Daniels, Dean and Spector, Alfred Z., “An Algorithm for
`Replicated Directories.” Proc. Of the 2" PODC Conference
`Proceedings, 1983, pp. 24–43, ACM Press, Department of
`Computer Science, Carnegie Mellon University, Pittsburgh,
`PA, USA.
`Gladney, H.M., “Data Replicas in Distributed Information
`Services,” Article, ACM Transactions on Database Systems,
`vol. 14, No. 1, Mar. 1989, pp. 75–97, San Jose, CA, USA.
`Colton, Malcom, “Replicated Data in a Distributed Envi
`ronment,” Proc. Of the 1993 ACM SIGMOD International
`Conference on Management of Data, Vol. 22, ISSue 2, May,
`1993, pp. 464–6, ACM Press, Washington, D.C., USA.
`Alonso, Rafael and Korth, Henry F., “Database System
`Issues in Nomadic Computing.” Proc. Of the 1993 ACM
`SIGMOD International Conference on Management of
`Data, vol. 22, Issue 2, May, 1993, pp. 388-392, Princeton,
`NJ, USA.
`Lindsay, et al., “A Snapshot Differential Refresh Algorithm,”
`Proc. Of the 1986 ACM SIGMOD International Conference
`on Management of Data, ACM, 1986, pp. 53–60, ACM
`Press, San Jose, CA, USA.
`Wolfson, Ouri and Jajodia, Sushil., “Distributed Algorithms
`for Dynamic Replication of Data.” Proc. Of the 11". ACM
`SIGACT SIGMOD SIGART Symposium on Principles of
`Database Systems, ACM, Jul., 1992, pp. 149-156, ACM
`Press, San Diego, CA, USA.
`Liskov, Barbara, et al., “Replication in the Harp File Sys
`tem.” Proc. Of the 13" ACM Symposium on Operating
`Systems Principles, ACM, Oct., 1991, pp. 226-238, MIT,
`Cambridge, MA, USA.
`Liskov, Barbara, et al., “A Replicated UNIX File System,”
`ACM Operating Systems Review, vol. 25, No. 1, Jan., 1991,
`pp. 60–64, ACM Press, MIT, Cambridge, MA, USA.
`Ladin, Rivka, et al., "Lazy Replication: Exploiting the
`Semantics of Distributed Services,” ACM Operating Sys
`tems Review, vol. 25, No. 1, Jan., 1991, pp. 49-55, ACM
`Press, Cambridge, MA, USA.
`Tivoli Systems, Inc., “Tivoli/Courier User's Guide,” Tivoli
`Systems, Inc., 1991-5, pp. 1-1-8-27, Austin, TX, USA.
`
`Page 4
`
`

`

`5,919,247
`Page 5
`
`Tivoli Systems, Inc., “Tivoli/Courier Reference Manual,”
`Reference Manual, Tivoli Systems, Inc., 1991-5, pp.
`1-1-6-4, Austin, TX, USA.
`Lan Supervision, Inc., “Change Management Facility
`(CMF).” Administrator's Guide, 1995, pp. 2–159, San
`Ramon, CA, USA.
`Lan Supervision, Inc., "Change Management Facility,' Gen
`eral Information Guide, 1995, pp. 1-51, San Ramon, CA,
`USA.
`IBM, “General Information Manual,” IBM Distributed
`Change Management Facility /MVS, Version 1, Release 1,
`1 edition, Aug. 1990, pp. 1-50, Cary, NC, USA.
`
`AnderSon, Paul, “Managing Program Binaries in a Hetero
`geneous UNIX Network,” Article, LISAV Sep./Oct., 1991,
`pp. 1-7, University of Edinburgh, Edinburgh, U.K.
`Cooper, Michael, RDist (Computer Program and Documen
`tation), Web Site: http://hpux.dutchworks.nl, Date of Publi
`cation Unknown, not later than Feb. 25, 1997, HP Dutch
`works, The Netherlands.
`Lemay, Laura, “Official Guide to Castanet', 1997, iv-353
`and Supplements, 1 ed. Sams.net, Indianapolis, IN.
`
`Page 5
`
`

`

`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 1 of 13
`
`5,919,247
`
`700-
`
`770
`
`707
`
`740
`
`74 f
`
`SERVER SYSTEM
`
`CLENT SYSTEM
`
`SERVER SYSTEM
`O
`
`77
`
`
`
`777
`
`DEVELOPMENT
`SYSTEM
`
`NETWORK
`
`CLENT SYSTEM
`
`O
`747
`
`790
`
`797
`
`PROXY SYSTEM
`
`A76, 74
`
`Page 6
`
`

`

`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 2 of 13
`
`5,919,247
`
`
`
`NETWORK
`INTERFACE
`
`CLENT SYSTEM
`747
`
`OPERATING SYSTEM
`WEB BROWSER
`
`CHANNEL APPL.
`
`STORAGE SYSTEM
`
`HOLDING LOG
`
`HOLDING INDEX
`
`HOLDING DATA
`
`CHANNEL INDEX
`
`CHANNEL DATA
`
`CHANNEL
`
`A76, 7A
`
`Page 7
`
`

`

`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 3 of 13
`
`5,919,247
`
`
`
`SERVER SYSTEM
`
`OPERATING SYSTEM
`TRANSMITTER
`
`777
`
`777
`
`NETWORK
`NERFACE
`
`STORAGE SYSTEM
`
`CHANNEL INDEX
`
`CHANNEL DATA
`
`CHANNEL
`
`A/6 7.O.
`
`Page 8
`
`

`

`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 4 of 13
`
`5,919,247
`
`
`
`DEVELOPMENT SYSTEM
`737
`
`OPERATING SYSTEM
`DEVELOPMENT TOOLS
`
`767
`
`ADMINISTRATION TOOL
`
`772
`
`777
`NETWORK
`INTERFACE
`
`STORAGE SYSTEM
`
`CHANNEL DATA
`
`A/G 7A
`
`Page 9
`
`

`

`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 5 of 13
`
`5,919,247
`
`
`
`790
`
`PROXY SYSTEM
`
`NETWORK
`INTERFACE
`
`OPERATING SYSTEM
`
`HTTP PROXY SERVER
`
`STORAGE SYSTEM
`
`HTTP CACHE
`
`A76, 7A
`
`Page 10
`
`

`

`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 6 of 13
`
`5,919,247
`
`2O7
`DIRECTORY INDEX NODE 222
`2O3
`
`
`
`- 200
`
`CHECKSUM
`
`NUMBER OF CHILDREN
`
`2O4.
`
`
`
`
`
`
`
`CHECKSUM
`
`FILE INDEX NODE
`
`CHECKSUM
`
`FILE POINTER
`
`223
`
`224
`
`237
`
`232
`
`233
`
`234
`
`A76, 2
`
`Page 11
`
`

`

`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 7 of 13
`
`5,919.247
`
`FOREACH UNOUE
`NODE IN THE CLENT
`AND SERVER INDEX
`
`3OO
`
`
`
`
`
`
`
`
`
`
`
`YES
`
`307
`
`YES
`
`DIRECTORY
`NODE2
`
`
`
`NO
`
`IN BOTH
`NDCES
`
`303
`
`YES
`
`NO
`
`NO
`
`307
`
`
`
`
`
`N
`SERVER
`INDEX?
`
`(A)
`
`3O4
`
`YES(B)
`
`303
`
`YES (c)
`
`NO
`
`NO
`
`ISSUE CREATE
`FILE
`
`ISSUE DELETE
`FILE
`
`ISSUE UPDATE
`FILE
`
`309
`
`370
`
`377
`
`A/G 34
`
`Page 12
`
`

`

`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 8 of 13
`
`5,919,247
`
`
`
`3O2
`
`
`
`
`
`
`
`IN BOTH
`NDCES2
`
`NO
`
`
`
`YES
`
`GB)
`
`NO ACTION
`RECURED
`
`N SERVER
`INDEX?
`
`
`
`NO
`
`2O6
`
`39
`
`YES
`
`
`
`
`
`ISSUEFLE OFF
`
`ISSUE DELETE
`DIRECTORY
`
`ISSUE CREATE
`DIRECTORY
`
`312
`
`373
`
`374
`
`A/G 3A
`
`Page 13
`
`

`

`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 9 of 13
`
`5,919,247
`
`SELECT CHANNEL
`
`407
`
`4O2
`
`
`
`PREPARE SUBSCRIBE
`RECQUEST
`
`403
`
`
`
`
`
`GET CHANNEL INDEX
`
`
`
`
`
`
`OPTIMIZE
`UPDATE2
`
`PREPARE OPTIMIZEO
`UPDATE RECQUEST
`
`
`
`
`
`PREPARE UPDATE
`REGUEST
`
`409
`
`ADD CENT
`NFORMATION
`
`
`
`429
`
`ADD CHANNEL DATA
`
`A/G 4
`
`Page 14
`
`

`

`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 10 of 13
`
`5,919.247
`
`407
`
`O2
`
`PREPARE REGUEST
`
`CONNECT TO
`TRANSMITTER
`
`
`
`O3
`
`NO
`
`YES
`
`SEND REGUEST
`
`WAT FOR REPLY
`
`
`
`
`
`
`
`READ REPLY
`
`
`
`
`
`CONNECT TO
`REDIRECTED
`TRANSMITTER
`
`
`
`
`
`
`
`INDEX
`RECURED?
`
`PREPARE UPDATE
`RECQUEST
`
`GA)
`
`GB)
`A/G 34
`
`477
`
`Page 15
`
`

`

`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 11 of 13
`
`5,919,247
`
`CB)
`
`572
`(A)
`
`NO
`
`APPEND
`YES COMMANDS TO
`HOLDING
`SPACE
`
`573
`
`REPORTERROR
`
`afe5
`
`476
`
`
`
`
`
`
`
`AP
`PLICATIONNYES
`RUNNING
`
`NOTIFY
`APPLICATION
`
`674
`
`
`
`UPDATE
`CHANNEL DATA
`
`677
`
`A76, 6A
`
`Page 16
`
`

`

`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 12 of 13
`
`5,919,247
`
`READ REGUEST
`
`300
`
`a07
`
`REEE,
`
`YES
`
`NO
`
`DETERMINE
`CORRECT HOST
`AND PORT
`
`602
`(A)
`
`aO4
`ys GET INDEX FROM
`CLIENT INDEX
`CACHE
`
`EAEP
`
`625
`CB)
`
`
`
`
`
`
`
`
`
`
`
`NO
`
`603
`
`YES
`
`SUBSCRIBE
`
`NO
`
`a 72
`
`YES
`
`NO
`
`SEND ERROR
`REPLY
`
`676
`
`USE EMPTY
`CLIENT INDEX
`
`609
`
`(C)
`
`USE CLIENT
`INDEX FROM
`REGUEST
`
`67.3
`(D)
`
`GE)
`
`A/G. 64
`
`Page 17
`
`

`

`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 13 of 13
`
`5,919,247
`
`(A)
`
`SEND REDIRECT
`REPLY
`
`a23
`
`GB)
`
`(C)
`
`GD)
`
`606
`
`
`
`6O7
`
`SEND INDEX
`RECURED REPLY
`
`YES
`
`
`
`
`
`OBTAIN SERVER
`INDEX FROM
`PLUG-N
`
`
`
`COMPARE CLENT
`NDEX AND
`SERVER INDEX
`
`STORE INDEX IN
`CLENT INDEX
`CACHE
`
`674
`
`DETERMINE
`DELAY UNTL
`NEXT UPDATE
`
`
`
`SEND UPDATE
`REPLY
`
`WRITE LOG
`ENTRY
`
`6.79
`
`A/G 6A9
`
`Page 18
`
`

`

`1
`METHOD FOR THE DISTRIBUTION OF
`CODE AND DATA UPDATES
`
`5,919.247
`
`15
`
`BACKGROUND OF THE INVENTION
`This invention relates to the distribution of Software over
`a network. More particularly, this invention relates to the
`broadcasting of code and data, and updates thereto, to a
`plurality of subscribers.
`In large Scale networkS Such as the Internet, or Intranets
`within businesses, the distribution of Software applications
`is often a manual and laborious process which requires the
`correct use of Such program tools Such as ftp, tar, compress,
`uudecode, and Zip. The variety of platforms and tools, and
`the complexity of the installation procedures make this
`manner of distribution a complex and costly operation.
`Software installation is therefore frequently performed by
`Specially trained System administrators rather than end
`USCS.
`The Internet has significantly accelerated the release
`Schedule of applications significantly. Software is released
`more frequently and in Smaller increments, and as a result
`many more installations have to be performed, resulting in
`more work for the system administrator. This multitude of
`releases can cause versioning problems when a new piece of
`installed Software becomes incompatible with Some previ
`ously installed Software. AS these updates occur more often,
`it is desirable to automate this update process.
`A browser is a computer program for accessing the
`Internet via the World Wide Web, using the HTTP protocol.
`Browser plug-ins allow the user to extend the browser So
`that it can incorporate new functionality. Plug-ins are often
`very hard to install because they are platform dependent, and
`not Secure because they are implemented in low level
`languages Such as C or C++. To make plug-ins Secure the
`browser needs to implement Some form of authentication
`algorithm Such as those based on the RSA algorithm.
`The Java programming language and the introduction of
`Java applets has made it possible to run the Same Software
`program in a Secure manner on many different platforms,
`thus enabling the wide distribution of Such programs over a
`heterogeneous network such as the Internet. With Java
`applets it has also become possible to automatically launch
`small Java programs from a WorldWide Web browser which
`eliminates a lot of the installation headache.
`When Java applets are used as applications, the user is
`required to use a browser to navigate to the HTML page
`containing the desired applet. Once the applet is running it
`is usually constrained to the HTML page in which it is
`embedded, and the applet may be terminated prematurely
`when the user visits a new HTML page.
`Further, Java applets have Several restrictions which pre
`vent them from Scaling to larger applications. One problem
`is that the download times are too long because each Java
`class is loaded using a separate HTTP connection, and
`making each new connection often takes more time than the
`actual data transfer. Also, Java applets have to be reloaded
`from their Source each time they are used, there is no
`mechanism for persistence other than HTTP caching. HTTP
`caching has the drawback that it is too low level, which
`60
`causes versioning problems because it may mix old Java
`classes with newer Java classes. It is usually impossible to
`flush an applet from an HTTP cache, because it is not
`possible to know which files in the cache belong to the
`applet that needs to be flushed.
`Because Java applets are reloaded for each use, and
`because they usually consist of many parts, they can Sig
`
`2
`nificantly increase the number of Server accesses and thus
`Significantly increase the Server load. As a result most high
`Volume web-sites cannot afford to put Java applets on their
`HTML pages.
`A Java applet generally cannot be used when the client
`computer is disconnected from the network. If the user
`wants to use an applet after disconnecting the network, it is
`first necessary to use all the features of the applet to populate
`the HTTP cache. However, if the user ventures into a
`previously unexplored part of the applet once disconnected,
`the applet will be unable to proceed and a fatal error will
`result. This is a major drawback of caching Strategies
`because disconnected use is important for the next genera
`tion of portable Internet devices.
`Another drawback of HTTP is that ongoing transactions
`can often be corrupted when new code and data is installed
`on the Server. This is not a fatal problem when it happens to
`