Data processing: software development – installation – and managem – Software upgrading or updating – Including multiple files
Reexamination Certificate
2000-09-26
2004-09-07
Dam, Tuan (Department: 2122)
Data processing: software development, installation, and managem
Software upgrading or updating
Including multiple files
C717S170000, C717S171000
Reexamination Certificate
active
06789255
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to identifying a file or set of files sharing a particular characteristic, and in particular, identifying such files while minimizing data transfer over a low-bandwidth communications pathway.
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 software has become even more complex. Recently, software maintenance has been somewhat automated by the creation 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 program size, where a single complex application may have hundreds or thousands of program modules, one ends up with a prohibitively large data-file listing all files and associated version tracking information for all application program modules being tracked by a server. (For the purposes of this application, the term “server” refers to the entity or entities providing the updating service, and the term “client” refers to the computer or organization receiving updated files.) In order for a client to determine whether there are program updates available, a potentially huge volume of data has to be transferred between client and server. If the client only has a low-bandwidth connection to the server, such coordination can be very time consuming.
In accordance with a preferred embodiment of the invention, the foregoing and other disadvantages of the prior art are overcome.
In the preferred embodiment, a set of software programs on the client computer is compared against a set of updates on the server computer to determine which updates are applicable and should be transferred from the server to the client. A many-to-one mapping function (e.g. a hash function) is applied to update identifiers to generate a table of single bit entries indicating the presence of particular updates on the server. This table is transferred to the client over the slow link. At the client, the same mapping function is applied to program identifiers, and corresponding entries of the transferred table are checked to determine whether the server has a potential update. If such a potential update is noted, a second transmission is requested by the client from the server—this one conveying additional data by which hash collisions can be identified by the client and disregarded. If availability of an actual update (versus a hash collision) is thereby confirmed, the client 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 of an applicable update is successively increased. (The same arrangement can be employed in reverse, with the bit table generated at the client and identifying program files available for possible updating, transferred to the server, etc.)
The foregoing and other features and advantages will be more readily apparent from the following detailed description, which proceeds with reference to the accompanying drawings.
REFERENCES:
patent: 4999806 (1991-03-01), Chernow et al.
patent: 5339430 (1994-08-01), Lundin et al.
patent: 5586304 (1996-12-01), Stupek, Jr. et al.
patent: 5701463 (1997-12-01), Malcolm
patent: 5701491 (1997-12-01), Dunn et al.
patent: 5742829 (1998-04-01), Davis et al.
patent: 5752042 (1998-05-01), Cole et al.
patent: 5832275 (1998-11-01), Olds
patent: 5832484 (1998-11-01), Sankaran et al.
patent: 5881236 (1999-03-01), Dickey
patent: 5919247 (1999-07-01), Van Hoff et al.
patent: 5930513 (1999-07-01), Taylor
patent: 5974454 (1999-10-01), Apfel et al.
patent: 6047129 (2000-04-01), Frye
patent: 6049671 (2000-04-01), Slivka et al.
patent: 6151708 (2000-11-01), Pedrizetti et al.
Andrew Tridgell, “Efficient Algorithms for Sorting and Synchronization”, Feb. 1999, Samba.org (http://samba.org/~tridge/phd_thesis.pdf), p. 1-115.*
Karger et al., “Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on WWW,”ACM STOC,pp. 654-663, 1997.
Wuytack et al., “Transforming Set Data Types to Power Optimal Data Structure,”ACM,pp. 1-6, 1997.
Wall, “User Services Implications for Client Server Transitions,”ACM SIGUCCS XX,pp. 231-238, Jan. 1992.
Sinha, “Client Server Computing,”Comm. of the ACM35 (7):77-98, Jul. 1992.
Felton et al., “Early Experience with Message Passing on the Shrimp Multicomputer,”ISCA ACM,pp. 296-307, Mar. 1996.
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., “Transactional Client Server Cache Consistency: Alternative and Performance,”ACM Trans. on Database Sys.22 (3):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 Technology,”IEEE,pp. 144-155, 1993.
Iftode et al., “Shared Virtual Memory with Automatic Update Support,”ICS ACM,pp. 175-183, 1999.
Bragg Timothy W.
Pedrizetti Raymond D.
Quinn Scott D.
Dam Tuan
Kiss Eric B.
Klarquist & Sparkman, LLP
Microsoft Corporation
LandOfFree
Determining update availability via set intersection over a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Determining update availability via set intersection over a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Determining update availability via set intersection over a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3204951