Determining update availability via set intersection over a sub-optimal pathway

• US 6,789,255 B1
• Filed: 09/26/2000
• Issued: 09/07/2004
• Est. Priority Date: 12/19/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Pedrizetti, Raymond D., Quinn, Scott D., Bragg, Timothy W.
• Primary Examiner(s): Dam, Tuan
• Assistant Examiner(s): Kiss, Eric B.
• Application Number:
  US09/670,116
• Time in Patent Office: 1,442 Days
• Field of Search: 717/161, 717/171, 717/172, 717/173, 717/168, 717/169, 717/170, 709/201, 709/217, 707/1, 707/10
• US Class Current: 717/169
• CPC Class Codes: G06F 8/65 Updates security arrangements therefor G06F21/57

Abstract

A low bandwidth link can be used optimally for software updates, by successively transferring more information about the updates only as the likelihood of an applicable update successively increases. A many-to-one mapping function (e.g. a hash function) is applied to update identifiers on a server to generate a table of single bit entries corresponding to the updates. At a client, the same mapping function is applied to program identifiers to determine whether the server has a potential update. If a potential update is noted, a second transmission is requested for conveying additional data from the server by which hash collisions can be identified. A third transmission from the server is received conveying the actual update only after the availability of an actual update (versus a hash collision) is confirmed. The same arrangement can be employed in reverse.

Claims

1. A computer-readable medium having computer-executable instructions for indicating resources for which at least one of a plurality of updates are available by performing the following:

with a hash function, generating a table having a plurality of single bit entries, wherein at least one of the plurality of the single bit entries is set to inconclusively indicate the availability of at least one of the plurality of the updates to the resources having unique identifiers, wherein a plurality of the unique identifiers are associated with a single bit entry via the hash function; and

transferring to a client computer the table inconclusively indicating the availability of the at least one of the plurality of the updates.

2. The computer-readable medium of claim 1 further comprising computer-readable instructions for performing the following:

consulting the table to inconclusively determine that the at least one of the plurality of the updates is available by detecting that the at least one of the plurality of the single bit entries is set; and

responsive to inconclusively determining that the at least one of the plurality of the updates is available, sending a list of resources associated with the single bit entry.

3. The computer-readable medium of claim 2 further comprising computer-readable instructions for performing the following:

consulting the list of resources associated with the single bit entry to conclusively determine that the at least one of the plurality of the updates is available; and

responsive to conclusively determining that the at least one of the plurality of the updates is available, transmitting the at least one of the plurality of the updates to the client computer.

4. The method of claim 1 wherein the table comprises a sparse table.

5. A method for determining an update is available for an item installed at a client computer, the method comprising:

determining a unique identifier for the item;

assembling a first data structure by applying a many-to-one mapping function to the unique identifier for the item, wherein the first data structure inconclusively indicates that the update is available for the item;

sending the first data structure in a first transmission;

from the first data structure, determining the update may be available for the item installed at the client computer;

responsive to determining the update may be available for the item installed at the client computer, in a second transmission, sending a second data structure comprising confirmation data for the item installed at the client computer, wherein the second data structure conclusively indicates that the update is available for the item; and

via the confirmation data for the item installed at the client computer, confirming the update is available for the item installed at the client computer.

6. The method of claim 5 wherein the item is a file.

7. The method of claim 5 wherein the item is a hardware device.

8. The method of claim 5 wherein the first data structure comprises a bitmap inconclusively indicating the presence of the update via a bit, wherein the bit is associated with the unique identifier and at least one other unique reference for another item, wherein location of the bit within the bitmap is determined by the one-to-many mapping function.

9. The method of claim 5 wherein the confirmation data comprises a list of files for which updates are available.

10. The method of claim 5 wherein the confirmation data comprises a list of files and devices for which updates are available.

11. The method of claim 5 wherein the confirmation data comprises a version number for the item.

12. The method of claim 5 further comprising:

responsive to confirming an update is available for the item installed at the client computer, transferring the update for the item to the client.

13. The method of claim 5 further comprising:

identifying plural items on the client computer for which a corresponding update is available;

transferring plural updates from the server to the client computer; and

installing said plural updates on the client computer.

14. The method of claim 5 wherein the assembling comprises generating a hash code for the item, wherein the same hash code may be generated for two different items.

15. The method of claim 14 further comprising:

responsive to confirming the update is available for the item installed at the client computer, transferring the update for the item to the client; and

determining whether a hash conflict has occurred before transferring the update.

16. The method of claim 5 further comprising:

transferring the confirmation data from a server computer to the client computer, wherein the confirmation data specifies the name of the item for which the server computer has the update.

17. The method of claim 16 wherein the confirmation data further specifies a file by which the automatic transfer and installation of the update on the client computer can be invoked.

18. The method of claim 16 wherein the administrative data further includes an override file, said override file operative to provide a reject indication for the update.

19. A method for determining software update availability for a client computer by sending software update availability information over a communications pathway, the method comprising:

with a hashing function, hashing unique identifiers of available software updates to non-unique identifiers to generate a data structure inconclusively indicating the availability of at least one software update;

sending the data structure over the communications pathway during a first transmission;

after the first transmission, comparing the data structure to a list of upgrade candidates for the client computer to determine an update may be available for an upgrade candidate in the list, wherein the update is identified by a non-unique identifier associated with the update via the hash function;

responsive to affirmatively determining an update may be available, during a second transmission over the communications pathway, sending a list of entries for a plurality of software updates associated with the non-unique identifier via the hash function; and

consulting the entries to conclusively determine if a software update is available for the upgrade candidate.

20. The method of claim 19 further comprising:

over the communications pathway, before sending the software update available for the upgrade candidate, sending an executable override file for the software update available for the upgrade candidate; and

before sending the software update available for the upgrade candidate, executing the override file to determine whether to reject the software update based on configuration of the client computer.

21. The method of claim 19 further comprising:

responsive to conclusively determining that the software update is available for the upgrade candidate, in a third transmission, sending the software update available for the upgrade candidate.