I 11111 11111111 111 11111 11111 11111 11111 11111 11111 11111 lllll 111111 111 11111 1111
`US006151708A
`6,151,708
`[11]Patent Number:
`United States Patent
`[19J
`[45]Date of Patent:
`
`Pedrizetti et al.
`Nov. 21, 2000
`
`[54]DETERMINING PROGRAM UPDATE
`
`Alok Sinha, "Client Server Computing", Comm. of the
`
`
`
`AVAILABILITY VIA SET INTERSECTION
`ACM, vol. 35, No. 7, pp 77-98, Jul. 1992.
`
`OVER A SUB-OPTICAL PATHWAY
`
`Felton et al., "Early experience with message passing on the
`
`
`
`
`
`
`
`SHRIMP multicomputer", ISCA ACM, pp 296-307, Mar.
`Raymond D. Pedrizetti; Scott D.
`
`[75]Inventors:
`1996.
`
`
`Quinn, both of Issaquah; Timothy W.
`
`Bragg, Redmond, all of Wash.
`
`[73] Assignee: Microsoft Corporation, Redmond,
`
`
`
`
`Wash.
`
`
`
`(List continued on next page.)
`
`[21]Appl. No.: 08/994,594
`
`[22]Filed:Dec. 19, 1997
`
`Attorney, Agent, or Firm----Klarquist Sparkman Campbell
`
`[56]
`
`
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`OIBER PUBLICATIONS
`
`Primary Examiner-Paul R. Lintz
`
`
`Assistant Examiner-Anil Khatri
`
`
`
`
`
`Leigh & Whinston, LLP
`
`[51]Int. Cl.7 ........................................................ G06F 9/45
`ABSTRACT
`[57]
`717/10; 717/12 [52]U.S. Cl. .................................. 717/11;
`
`
`
`395/705, 706, [58]Field of Search .....................................
`
`
`
`
`
`
`A set of software programs on a client computer is compared
`
`
`
`
`395/707, 712, 709; 711/184; 382/166; 707/8;
`
`
`
`against a set of updates on a server computer to determine
`
`709/221, 217; 717/11
`
`
`
`which updates are applicable and should be transferred from
`
`
`
`
`the server to the client. If the link between the client and
`
`
`
`server is slow, the listing of available updates must be
`
`
`
`
`represented in compact form. A many-to-one mapping func­
`
`
`
`
`tion ( e.g. a hash function) is applied to update identifiers to
`
`
`
`
`4,999,806 3/1991 Chernow et al. ......................... 717/11
`
`
`
`
`generate a table of single bit entries indicating the presence
`
`
`
`5,339,430 8/1994 Lundin et al. .......................... 709/332
`
`
`
`of particular updates on the server. This table is transferred
`
`
`
`
`5,586,304 12/1996 Stupek, Jr. et al. .................... 395/712
`
`
`to the client over the slow link. At the client, the same
`
`
`5,701,463 12/1997 Malcolm ................................... 707/10
`
`
`
`
`mapping function is applied to program identifiers, and
`
`
`
`
`5,701,491 12/1997 Dunn et al. .... ... ... ... ... .... ... ... ... .. 717 /11
`
`
`
`
`5,742,829 4/1998 Davis et al. ............................ 395/712
`
`
`
`
`corresponding entries of the transferred table are checked to
`
`
`5,752,042 5/1998 Cole et al. .............................. 395/712
`
`
`
`
`
`determine whether the server has a potential update. If such
`
`
`
`5,832,275 11/1998 Olds ........................................ 395/712
`
`
`a potential update is noted, a second transmission is
`
`
`
`5,832,484 11/1998 Sankaran et al. . ... ... ... ... .... ... ... ... . 707 /8
`
`
`requested by the client from the server-this one conveying
`
`
`5,881,236 3/1999 Dickey .................................... 709/221
`
`
`
`additional data by which hash collisions can be identified by
`
`
`
`5,919,247 7/1999 Van Hoff et al. ....................... 709/217
`
`
`
`
`the client and disregarded. If availability of an actual update
`
`
`
`5,930,513 7/1999 Taylor ....................................... 717/11
`
`
`6,047,129 4/2000 Frye .......................................... 717 /11
`
`
`
`
`(versus a hash collision) is thereby confirmed, the client
`
`
`6,049,671 4/2000 Slivka et al. ... ... ... ... ... .... ... ... ... .. 717 /11
`
`
`requests a third transmission from the server-this one
`
`
`conveying the actual update data. By this arrangement,
`
`
`optimized use is made of the low bandwidth link, with
`
`
`
`successively more information transferred as the likelihood
`Karger et al., Consistent hashing and random trees: distrib­
`
`
`
`
`
`
`
`of an applicable update is successively increased. (The same
`
`
`
`uted caching protocols for relieving hot spots on WWW,
`
`
`
`arrangement can be employed in reverse, with the bit table
`
`ACM STOC, pp 654-663, 1997.
`
`
`
`
`generated at the client and identifying program files avail­
`
`
`Wuytack et al., Tranforming set data types to power optimal
`
`
`
`
`able for possible updating, transferred to the server, etc.).
`
`data structure, ACM pp 1-6, 1997.
`
`
`
`
`Wall, Matthew, "User services implications for client server
`
`
`transitions", ACM SIGUCCS XX, pp 231-238, Jan. 1992.
`
`
`
`22 Claims, 13 Drawing Sheets
`
`
`
`100
`
`102
`
`104
`
`Server
`
`122
`
`106 108
`
`120 118
`
`Page 1 of 25
`
`

`

`6,151,708
`Page 2
`
`OTHER PUBLICATIONS
`
`Naps et al., "Using the WWW as the delivery mechanism for
`interactive, visualization based
`instructional modules",
`ACM ITiCSE, pp 13-26, 1997.
`Franklin et al., "Tranactional client server cache consis(cid:173)
`tency: alternative and performance", ACM Trans, on Data(cid:173)
`base sys. vol. 22, No. 3, pp 315-363, Sep. 1997.
`
`Browne et al, "Location independent naming for virtual
`distributed software respositories", ACM SSR, pp 179-185,
`Jan. 1995.
`Dwarkadas et al, "Evaluation of release consistent software
`distributed shared memory on emerging network technol(cid:173)
`ogy", IEEE, pp 144-155, 1993.
`Iftode et al, "Share virtual memory with automatic update
`support", ICS ACM, pp 175-183, 1999.
`
`Page 2 of 25
`
`

`

`U.S. Patent
`
`Nov. 21,2000
`
`Sheet 1 of 13
`
`6,151,708
`
`FIG. 1
`
`100
`
`102
`
`122
`
`Module
`_ l n f o^
`
`Update
`Data
`
`Module
`Info
`
`Page 3 of 25
`
`

`

`U.S. Patent
`
`Nov. 21, 2000
`
`Sheet 2 of 13
`
`6,151,708
`
`FIG. 2
`
`200
`
`202
`
`204
`
`206
`
`208
`
`210
`
`212
`
`214
`
`Contact
`Server
`
`Receive
`Banner
`
`Load OCX /
`
`Auto-sense
`Peripherals
`
`Locate
`Registered
`Applications
`
`/
`
`Search for
`Non-
`registered
`Applications
`
`/
`
`Check for
`Updates
`
`List
`Available
`Updates
`
`Page 4 of 25
`
`

`

`U.S. Patent
`
`Nov. 21,2000
`
`Sheet 3 of 13
`
`6,151,708
`
`F I G. 3 -Step 212 of FIG. 2
`
`314
`
`Yes
`
`/ 320
`
`\_y 322
`
`Download
`and Execute
`DLL
`
`Download
`and Apply
`Patch
`
`300
`
`302
`
`304
`
`306
`
`308
`
`310
`
`312
`
`Encode
`Identifier
`
`Search
`Client Map
`
`Search
`Server Map
`
`Retrieve
`Index
`
`Page 5 of 25
`
`

`

`U.S. Patent
`
`Nov. 21, 2000
`
`Sheet 4 of 13
`
`6,151,708
`
`FIG. 4
`
`400
`
`/
`
`402
`
`i
`1
`
`r m-
`
`Decompressed Sparse
`Bitmap
`
`fi i i i i i i i
`f
`N
`|
`8443
`
`FIG. 7
`
`712
`
`A
`
`1 FT
`
`^
`
`- 4
`
`Complete
`Data-set
`
`702
`_£_
`
`710
`^
`
`Server
`
`/
`
`716
`
`704
`
`Unix Client
`
`706
`
`Macintosh Client • 708
`
`Windows Client
`
`Page 6 of 25
`
`

`

`U.S. Patent
`
`Nov. 21, 2000
`
`Sheet 5 of 13
`
`6,151,708
`
`FIG. 5
`
`500
`
`\
`
`Download and
`Decompress
`Bitmap
`
`504
`
`\
`
`Compile
`PnP List
`(hwinfo.dat)
`
`508
`
`\ Hash PnP ID
`(8443)
`
`510
`
`512
`
`\
`
`Read
`INDEX.8443
`from Server
`
`<
`
`524
`
`\| Get .DATA File
`(foo.vxd.data)
`
`526
`
`\
`
`Execute HTML
`Install-File
`in DATA File
`
`i i i i i i i i n-rn-rrrrm i
`1
`|
`|
`8443
`
`Decompressed Sparse
`Bitmap
`
`N
`
`502
`
`506
`
`v e nl 002&dev_4158&subsys_0000000&rev_02
`
`Region 3
`
`Region 2
`
`Region 1
`
`516
`
`5 1 8 / 5 20
`
`Keyfile name:
`Version information:
`HTML reference:
`Datafile:
`
`Keyfile name:
`Version information:
`HTML reference:
`Datafile:
`
`7
`Welcome.txt
`9/1/95
`Welcome95.html
`
`Welcome.txt
`9/15/97
`Welcome97.html
`
`514
`
`Keyfile name:
`
`Version information:
`HTML reference:
`Datafile:
`
`ven_1002&dev_4158&
`subsys_0000000&rev_02
`9/22/97
`Foo.html
`Foo.vxd'
`
`525
`
`Page 7 of 25
`
`

`

`U.S. Patent
`
`Nov. 21, 2000
`
`Sheet 6 of 13
`
`6,151,708
`
`FIG. 6A
`
`• ^ M ^ f f i S ^ S l ^ l l i ^^
`
`BC-J
`
`L'\
`
`^•«gsfe»**
`
`602
`
`600
`
`Page 8 of 25
`
`

`

`U.S. Patent
`
`Nov. 21,2000
`
`Sheet 7 of 13
`
`6,151,708
`
`FIG. 6B
`
`mmmmmmmmMm^wmmmmmMmmmmMim
`
`Li
`
`Page 9 of 25
`
`

`

`U.S. Patent
`
`Nov. 21, 2000
`
`Sheet 8 of 13
`
`6,151,708
`
`FIG. 6C
`
`$»S«W!^$H:MSi^i^
`
`612
`
`Page 10 of 25
`
`

`

`U.S. Patent
`U.S. Patent
`
`Nov.21, 2000
`Nov. 21, 2000
`
`Sheet 9 of 13
`Sheet 9 of 13
`
`6,151,708
`6,151,708
`
`FIG, 6.D
`FIG. 6D
`
`Tre following updates are racemmendad
`To install sn update, click
`it, and then
`
`for your Computer.
`Install. After you
`venta fgeyFSUETSY,
`
`aE
`
`-
`«* Reames
`
`>} Inaiiatt
`
`Dassrotion
`Welcame bo the Windaveg Wadate ”
`Manager
`
`alist of currant drivers, and a
`
`WELCOME TO WINDOWS UPDATE
`MANAGES Tis wil
`dowrninar 3
`textile tm your desktop Filename -
`Waelrome.tet This tle contain a
`simple welcome message, a ist of
`currant drivers, and the currant
`Peace for Wirciows Update
`Manager.
`
`Ceacriotion:
`This wih instal 4 welcome message,
`
`•812
`
`•808
`
`810
`
`Page 11 of 25
`
`Page 11 of 25
`
`

`

`U.S. Patent
`
`Nov. 21, 2000
`
`Sheet 10 of 13
`
`6,151,708
`
`FIG. 6E
`
`SSaJJSSi&^SiS!^^
`
`, 820
`
`,<ir ' i ^ - U
`
`V L 2 *C PD —
`
`i ,. n, -i
`11-
`;^ r j n ' ' > ''<
`r
`if P ~n*r i r n ~2q_
`
`"r i* ' i ll
`iGvScq> .
`"
`»-! •* v<-i
`•i i f* n* -tjigrv' a i srr a-t! =)
`
`Page 12 of 25
`
`

`

`U.S. Patent
`U . S. P a t e nt
`
`Nov.21, 2000
`Nov. 21,2000
`
`Sheet 11 of 13
`Sheet 11 of 13
`
`6,151,708
`6,151,708
`
`FIG. 6F
`FIG. 6F
`
`onkn your deskion
`
`Description:
`This adiinetall a weloome rmesaaee,
`alist of murrent drivers, anda
`tgadine from the Update Manager
`
`. 622
`
`Page 13 of 25
`
`Page 13 of 25
`
`

`

`U.S. Patent
`
`Nov. 21, 2000
`
`Sheet 12 of 13
`
`6,151,708
`
`FIG, 6G
`
`^ : ^ ^ i : i S : : t ^ : S i S r i * b H:^ ^ i ! ( i i i i i s ' ; U | i i a i i t j i; Wiisiid; v MH2*<ji«>H' iHt*s«*wa Eii^iiSfto
`
`T Of Blf
`J" I*
`* A U C'H
`y3^ *an* iv v u ca 11
`
`•*=!
`t_!i
`
`Page 14 of 25
`
`

`

`U.S. Patent
`
`Nov. 21,2000
`
`Sheet 13 of 13
`
`6,151,708
`
`FIG. 8
`
`800
`
`812
`
`unsigned long Rand(unsigned long seed)
`<
`^ -— 814
`unsigned long r = 2836L; , 816
`unsigned long a = 16807L,^
`818
`unsigned long n = 127773L;
`^ 820
`unsigned long d = 2147483647;
`unsigned long val;x^_ o79
`
`^— 824
`val = ((seed%n)*a)-(seed/n)*r;
`if(((long)val) <= 0)
`val = val + d;
`return (val);
`
`802
`
`\
`
`}
`
`804
`/" 806
`unsigned long Hash( const char *IDstring,
`/^
`unsigned long tablesize)
`
`{
`810 ^ unsigned long hash = 1;
`x while(*IDstring)
`v\ __ 8 08
`
`hash = hash + Rand(hash+toupper(*IDstring));
`++IDstring;
`
`}
`hash = hash%tablesize;
`return(hash);
`
`Page 15 of 25
`
`

`

`1
`DETERMINING PROGRAM UPDATE
`AVAILABILITY VIA SET INTERSECTION
`OVER A SUB-OPTICAL PATHWAY
`
`FIELD OF THE INVENTION
`
`6,151,708
`
`2
`description, which proceeds with reference to the accompa-
`nying drawings.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The present invention relates to identifying a file or set of
`files sharing a particular characteristic and in particular,
`identilying such files while minimizing data transfer over a
`low-bandwidth communications pathway.
`
`10
`
`FIG. 1 shows a client and server configured according to
`a preferred embodiment of the invention.
`flow.chart
`a c l i e nt c h e c k i ng for an
`F IG 2 is a
`s h o wi
`undate
`
`,.
`,
`.
`,
`„ .
`FIG. 3 is a detailed view of a step of FIG. 2.
`FIG. 4 shows one preferred embodiment for a hash table
`entry.
`FIG. 5 is a flow-chart showing, in detail, a portion of FIG.
`
`2.
`
`FIGS. 6A-6G show a preferred implementation of the
`user interface for the upgrade procedure of FIG. 5.
`F IG 7 is a flow-chart showing a push-type implementa-
`tjon 0f ^e
`invention
`,
`,,
`,
`c
`„,
`rj„
`, c
`. c
`c
`FIG. o shows code fragments lor a preferred method of
`,
`,
`,.,.
`,.
`.,
`hash encoding identifiers.
`
`20
`
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`
`BACKGROUND AND SUMMARY OF THE
`INVENTION
`The prior art is replete with various schemes for providing
`data-file updates over a network connection. Ever since the
`days of large centralized corporate mainframes, maintaining
`software has been a pressing concern. With the proliferation
`of fast and powerful workstations, maintaining current soft-
`ware has become even more complex. Recently, software
`maintenance has been somewhat automated by the creation
`.
`r
`,
`,
`r
`of automatic computer software updates programs such as
`«^., ^,
`„, >, ,
`-.. ,•
`Oil Change by CyberMedia.
`There is a fundamental problem, however, with present-
`day automatic update schemes. With the explosion in pro-
`gram size, where a single complex application may have
`Preferred embodiments use computer systems to imple-
`hundreds or thousands of program modules, one ends up
`ment a method and apparatus embodying the invention,
`with a prohibitively large data-file listing all files and
`S u ch computer systems includes as their basic elements a
`associated version tracking information for all application
`computer, an input device, and output device. The computer
`program modules being tracked by a server. (For the pur-
`generally includes a central processing unit (CPU), and a
`poses of this application, the term "server" refers to the
`memory system communicating through a bus structure. The
`entity or entities providing the updating service, and the term
`CPU includes an arithmetic logic unit (ALU) for performing
`"client" refers to the computer or organization receiving
`computations, registers for temporary storage of data and
`updated files.) In order for a client to determine whether
`instructions, and a control unit for controlling the operation
`there are program updates available, a potentially huge
`of computer system in response to instructions from a
`volume of data has to be transferred between client and
`computer program such as an application or an operating
`server. If the client only has a low-bandwidth connection to
`system.
`the server, such coordination can be very time consuming.
`The memory system generally includes high-speed main
`In accordance with a preferred embodiment of the
`memory in the form of random access memory (RAM) and
`invention, the foregoing and other disadvantages of the prior
`4n read only memory (ROM) semiconductor devices, and see-
`art are overcome.
`o n d a ry s t o r age in t he f o rm of floPPy disks> h a rd disks> taPe>
`In the preferred embodiment, a set of software programs
`CD-ROM, etc. and other devices that use optical or mag-
`on the client computer is compared against a set of updates
`n e t lc recording material. Main memory stores programs,
`on the server computer to determine which updates are
`s u ch as a computer's operating system and currently running
`applicable and should be transferred from the server to the
`client. A many-to-one mapping function (e.g. a hash 45 aPP1ic a tion programs, and also includes video display
`function) is applied to update identifiers to generate a table
`memory. The input and output devices are typically periph-
`of single bit entries indicating the presence of particular
`e r al d e v l c es connected by the bus structure to the computer,
`^
`mPut d e v l ce m ay be a keyboard, modem, pointing
`updates on the server. This table is transferred to the client
`over the slow link. At the client, the same mapping function
`d e v l c e> Pen> or o t h er d e v l ce f or providing input data to the
`is applied to program identifiers, and corresponding entries 50 c o mPu t e r- An output device may be a display device, printer,
`of the transferred table are checked to determine whether the
`s o u nd d e v l ce or o t h er d e v l ce f or providing output data from
`server has a potential update. If such a potential update is
`t he computer. It should be understood that these are illus-
`noted, a second transmission is requested by the client from
`t r a t l ve elements of a basic computer system, and are not
`the server—this one conveying additional data by which
`intended to a specific architecture for a computer system,
`hash collisions can be identified by the client and disre- 55
`FIG. 1 shows the basic configuration of a client and server
`garded. If availability of an actual update (versus a hash
`employed in an illustrative embodiment of the present
`invention. A server computer 100 is in communication with
`collision) is thereby confirmed, the client requests a third
`a client computer 102 over a communications pathway 104.
`transmission from the server—this one conveying the actual
`It is expected that pathway 104 is a low bandwidth connec-
`update data. By this arrangement, optimized use is made of
`(e-g- 56 Kbit/sec) provided by a device such as a
`the low bandwidth link, with successively more information go ^on
`transferred as the likelihood of an applicable update is
`computer modem or the like. In addition, communications
`successively increased. (The same arrangement can be
`between the client and server may be through an Internet
`employed in reverse, with the bit table generated at the client
`connection via a Web Browser, and as such, available
`bandwidth of pathway 104 is further reduced by inherent
`and identifying program files available for possible
`updating, transferred to the server, etc.)
`gs Internet-related overhead.
`
`The foregoing and other features and advantages will be
`more readily apparent from
`the following detailed
`
`Associated with both the server 100 and client 102 are
`databases 106, 108, containing information regarding pro-
`
`Page 16 of 25
`
`

`

`6,151,708
`
`5
`
`gram modules that may be updated. Client computer 102
`may initially have the database installed during production
`of the computer, and then later updated as needed, or the
`client computer may dynamically download its initial copy
`of its database 108.
`On the server 100 side, database 106 contains entries 110
`regarding each updateable program module, where each
`entry contains data 112 including the module name and
`related tracking information. Associated with each entry 110
`is update data 114 corresponding to the data required to ...
`bring the particular entry up to date with respect to the latest
`version of that module. In a preferred embodiment, each
`older module version (e.g. a first, second, and third version
`of a module) has its own database entry and associated
`update data to bring such module up to date. It is understood,
`however, that such multiple older modules may be grouped
`under a single entry, and the update data appropriately
`segmented for access by client 102.
`On the client 102 side, database 108 corresponds to the
`server database 106 in that it also contains entries 116 20
`regarding each updateable program module, where each
`entry contains data 118 including the module name and
`related tracking information. However, unlike its server
`counterpart, the client preferably does not maintain update
`data for each module entry 116. In addition, the client 25
`computer database 108 might only track entries for program
`modules corresponding to programs 122 already installed on
`client computer 102.
`Consequently, in a preferred embodiment, the server
`database 106 may contain entries 120 not found in the 30
`client's copy 108 of the database. As noted above, since the
`client may or may not have had an initial database installed
`when the computer was manufactured, a preferred embodi(cid:173)
`ment obtains or updates a client database copy. In one
`embodiment, the client seeks to have an identical copy of the 35
`server database; in an alternate embodiment, the client only
`maintains a database corresponding to programs already
`installed in the client's computer. Both of these embodi(cid:173)
`ments are described further below. Preferably the database is
`designed so that the client version 106 can be incrementally 40
`revised.
`FIG. 2 is a flow-chart showing a client checking for the
`availability of module updates. (For the purposes of this
`application, it is assumed that a dedicated server is available
`to field such incoming client requests.) The first step 200 45
`taken by a requesting client is to contact a server. In
`response, at step 202 the server transmits a banner page to
`the client. This banner page may contain information to be
`displayed by a client, such as advertisements, or it may be
`data which is simply absorbed by the contacting client, 50
`where such data may include information regarding the
`latest version of the automatic upgrade system itself. A third
`alternative would be to combine these two possibilities, so
`as to provide visual feedback to a client user while also
`allowing the upgrade system to ensure that the contacting 55
`client's software and database are not too out of date.
`The next step 204 is to load the client's OLE (object
`linking and embedding) Custom Control (hereinafter OCX).
`As described more fully below, the function of the OCX is
`to contact the server computer and coordinate upgrading 60
`components installed in the client's computer. In another
`embodiment (e.g. push environments), the client OCX load(cid:173)
`ing may be controlled by commands received from the
`server. (Apush environment is considered to be one in which
`a source external to a client asynchronously sends informa- 65
`tion to the client, and the client is configured to automati(cid:173)
`cally receive (and perhaps process) the pushed data.)
`
`After the client OCX is loaded, the next task is to
`assemble a master list of identifiers, these identifiers being
`uniquely assigned for each hardware or software module
`that may be upgraded. At step 206, identifiers are collected
`for all auto-sense equipment installed in the client computer.
`In a preferred embodiment, auto-sense equipment includes
`all equipment conforming to the Plug-and-Play (hereinafter
`PnP) specification promulgated by Microsoft Corporation
`for its Microsoft Windows environments, as well as other
`architectures in which it is possible to query or read a
`device's unique identifier.
`Similarly, at step 208, identifiers for software installed in
`the client computer are collected. Preferably, such identifiers
`are ascertainable from a review of the installation of smart
`applications, where such smart applications register them(cid:173)
`selves into the Windows Registry file or create some other
`data file containing an installation log. The Registry or log
`contains the unique identifier for the installed program,
`which is then included into the master list.
`At step 210, the illustrated embodiment may also allow a
`search to be performed for other hardware or software not
`already found in the foregoing steps. For software, such
`further searching may be across all directories in the client
`computer, or only within predetermined designated directo(cid:173)
`ries (e.g. c:\windows and c:\windows\system). For the
`located files, in one embodiment a search is made through
`the client database (item 108 of FIG. 1), and if the file is
`located, then the identifier found in the database is used for
`the located file. In another embodiment, a pre-determined
`scheme is used to generate a corresponding file identifier
`(e.g. a hash function based on the file name, date, size and
`creator). Each such identifier is added to the client's master
`list.
`At step 212, after the master list of identifiers is built, a
`check is performed to determine whether corresponding
`program updates exist at the server. The details of step 212
`are shown as FIG. 3.
`At step 214, a list is presented to a user indicating what
`updates are available. At this point the user may select which
`updates to perform to the client computer. Alternatively,
`rules may be established for the automatic processing of
`available updates.
`FIG. 3 shows the steps taken by the client to evaluate
`whether there is an update available on the server for items
`in the client's master list.
`Since the client's update evaluation potentially requires
`checking a huge number of files for available updates, it
`would be prohibitive to have the client and server pass file
`name (or other program or hardware module references)
`back and forth to determine the availability of upgrades.
`Instead, as discussed below, the server maintains a large bit
`field having bit entries which indicate the potential avail(cid:173)
`ability of updates. This bit field is compressed and trans(cid:173)
`ferred to the client, allowing the client to locally determine
`a correspondence between the client's list and the server's
`bit field. The correspondence between modules and
`upgrades is by a hash function which maps unique module
`references to index positions within the field (a hash table).
`In a preferred embodiment, after transfer to the client, the
`bit field is decompressed, as needed, into a sparse hash table
`(bit field) by the client OCX. Various schemes may be
`employed regarding scheduling the transfer of the bit field,
`such as getting a new copy every time an Internet connection
`is made, but at a minimum a current copy is retrieved at the
`initiation of the upgrade procedure.
`Each sparse table's hash value has a corresponding entry
`in a large bitmap hash table stored on the server. (Note that
`
`Page 17 of 25
`
`

`

`6,151,708
`
`although this specification presumes that a master list is
`created before searching for any updates, in an alternate
`embodiment, testing for updates may be made sequentially
`as identifiers are located, or testing may be done via a
`parallel algorithm.) For simplicity and clarity, a preferred 5
`embodiment creates the master list first. The procedure for
`updating the files is as follows.
`In order to check the update status for a given file or
`hardware component, at step 300 the OCX encodes the file's
`or device's unique identifier according to the hash function
`so as to obtain its hash number (a non-unique identifier). At
`step 302, the local sparse table is indexed by this hash
`number to identify a single bit position. If the bit is set (step
`304), this indicates that an update may exist for the file or
`device on the server. The reason the result is inconclusive is
`due to possible hash table collisions. More than one unique
`identifier can encode into a single hash number, resulting in
`a one to many correspondence between hash values and
`unique identifiers. It is not certain that an update on the
`server, if present, corresponds to the present file or device for
`which an update is being checked.
`
`...
`
`Embodiments may be also configured to catch synchro(cid:173)
`nization errors between the client and server, where, after
`locating the set bit in the local table, at step 306, the
`corresponding bit is located 308 in the hash table on the 25
`server, and checked 310 to ensure it is also set.
`Digressing for a moment, FIG. 4 shows one possible
`embodiment for a table entry in the a hash table 400 stored
`on the client and the server. Recall that the client's local
`sparse hash table simply contains a list of " 1" (high) or " 0" 30
`(low) bits in certain table locations, and that the server
`contains a corresponding table of bit entries, some of which
`have associated update data. Each position in the table 400
`corresponds to a different hash value. For example, shown is
`a bit 402 set high (e.g. equal to 1) indicating an update is 35
`available for some component that hashes to value 8443.
`Thus the possible availability of an update for a software or
`hardware component is indicated by a single bit transmitted
`in the bitmap table sent to the client computer. When the flag
`is set high, there is an available update, and by convention 40
`a file
`is present on
`the server having
`the name of
`"index.<hash id>". (For example, if the hash id is 8443, then
`the index file would be "index.8443".) This file contains
`entries for all files or devices, having the present hash id 402,
`for which an update is available.
`
`45
`
`Returning now to FIG. 3, after addressing the table with
`the hash value, the bit at that entry (the "flag" bit) is
`examined to determine if it is set (step 310). If set, then at
`step 312 the associated index file corresponding to the hash
`number is retrieved from the server. This index file lists all 50
`files or devices having that particular hash number, as well
`as other information related to the file or device, such
`information including a PnP id, version number, file date,
`optional override DLL (Dynamic linked Library), and name
`of the update package. In a preferred embodiment, the index 55
`file information is used to determine if the server database
`(item 106 of FIG. 1) contains an update for the file or
`hardware component being checked, or whether a hash
`collision occurred (i.e. an update is available for a different
`program module that yields the same hash code). Note that so
`for the purposes of this specification and claims that follow,
`references to an update for a hardware component includes
`not only updated drivers for the device, but also any soft(cid:173)
`ware for re-programming programmable portions of the
`device (e.g. PRAM, PROM, E-PROM, etc.).
`At step 314, a comparison is made between the unique
`identifier of the client file or device in question and the
`
`gs
`
`entries in the index file obtained from the server. If a match
`is found, then at step 316, version information is compared
`to confirm that the server has new update for the file or
`device. If an update exists, at step 318 the local OCX checks
`whether an optional download DLL is defined in the index
`file. If defined, then at step 320 the download DLL is
`downloaded from the server and executed locally on the
`client. Using the optional download DLL allows for writing
`programs specifically
`tailored to a specific update. For
`example, a vendor may write a DLL that coordinates any
`updates to the vendor's files and devices. If a download DLL
`then at step 322, the update data
`was not defined,
`is
`downloaded from the server and applied to the file or device
`being updated. Note that in alternate embodiments, the
`update data may be located on a third-party server, where
`only the location of such information is stored on the server
`100 (FIG. 1).
`
`FIG. 5 is a flow-chart showing a preferred implementation
`of the FIG. 2 and FIG. 3 embodiments.
`In the exemplary embodiment shown in FIG. 5, the
`upgrade process begins at step 500 by copying a file named
`bitmap.bts from the server. This file is a compressed version
`of a sparse bitmap stored at the server. The bitmap is copied
`to the client machine and decompressed. Shown associated
`with step 500 is an N-bit decompressed sparse bitmap 502.
`Preferably a run length encoding scheme (e.g. RLL (Run
`Length Limited)) is utilized to compress this bitmap prior to
`transmission to the client, but other compression schemes
`may also be used. As discussed above, the N'* bit entry in the
`field 502 corresponds to the hash value N encoding of some
`arbitrary (preferably unique) string, PnP identifier, file name,
`or other reference.
`At the next step 504, a list is compiled of all PnP devices
`presently in the client system. Preferably a local OCX
`creates a list in a file named HwInfo.dat. In preferred
`embodiments, the OCX runs as part of a hardware download
`manager incorporated into the controlling operating system.
`In alternate embodiments where the OCX is not embedded
`into the operating system, the OCX may be executed via an
`ActiveX or equivalent control.
`A similar list is also compiled for software that is eligible
`to receive updates. For simplicity, updating software is not
`shown in FIG. 5, as once an identifier is located for eligible
`software, the upgrade procedure is the same as for hardware.
`The general idea is to generate a list (or lists) containing
`identifier strings for upgrade candidates. A plain text file is
`presumed, but as the length of the list gets long, the list may
`be encoded as records in a database or other data structure.
`Note that an alternate method is to check each eligible
`hardware or software component as identified, without com(cid:173)
`piling a local list.
`Shown associated with step 504 is an illustrative PnP
`identifier 506 corresponding to a PCI-bus expansion card. In
`the Microsoft Windows environment, the format for PnP
`identifiers is well known. These PnP identifiers have several
`regions. Shown as Region #1 is the most specific reference
`available, which corresponds to the entire identifier string
`for a given PnP device. This #1 reference indicates the
`manufacturer and model of the PnP device, as well as
`indicating that it is revision version 2 of the PnP model.
`Shown as Region #2 is a less specific reference, indicating
`the manufacturer and device type, but not the specific
`installed device. For example, Region #2 indicates some
`information regarding a core device as modified or altered
`by an original equipment manufacturer (OEM). Shown as
`Region #3 is the general manufacturer identifier. This is the
`
`Page 18 of 25
`
`

`

`6,151,708
`
`least amount of information that may be encoded into an
`identifier. For more information, see chapter 8 of Inside
`Windows 95, by Adrian King (Microsoft Press 1994), and
`references cited therein.
`The preferred embodiment takes advantage of this tiered
`structure to allow upgrades to be tailored to different levels.
`Pr