Electrical computers and digital processing systems: multicomput – Remote data accessing
Reexamination Certificate
2004-04-15
2009-06-30
Follansbee, John (Department: 2451)
Electrical computers and digital processing systems: multicomput
Remote data accessing
C707S793000, C713S186000
Reexamination Certificate
active
07555531
ABSTRACT:
A method and system are related to updating objects over limited bandwidth networks. Objects are updated between two or more computing devices using remote differential compression (RDC) techniques such that required data transfers are minimized. In one aspect, efficient large object transfers are achieved by recursively applying the RDC algorithm to its own metadata; a single or multiple recursion step(s) may be used in this case to reduce the amount of metadata sent over the network by the RDC algorithm. Objects and/or signature and chunk length lists can be chunked by locating boundaries at dynamically determined locations. A mathematical function evaluates hash values associated within a horizon window relative to potential chunk boundary. The described method and system is useful in a variety of networked applications, such as peer-to-peer replicators, email clients and servers, client-side caching systems, general-purpose copy utilities, database replicators, portals, software update services, file/data synchronization, and others.
REFERENCES:
patent: 5446888 (1995-08-01), Pyne
patent: 5486826 (1996-01-01), Remillard
patent: 5488364 (1996-01-01), Cole
patent: 5721907 (1998-02-01), Pyne
patent: 5933104 (1999-08-01), Kimura
patent: 5987022 (1999-11-01), Geiger et al.
patent: 5990810 (1999-11-01), Williams
patent: 6049874 (2000-04-01), McClain et al.
patent: 6101507 (2000-08-01), Cane et al.
patent: 6226629 (2001-05-01), Cossock
patent: 6317754 (2001-11-01), Peng
patent: 6374250 (2002-04-01), Ajtai et al.
patent: 6449612 (2002-09-01), Bradley et al.
patent: 6574657 (2003-06-01), Dickinson
patent: 6728711 (2004-04-01), Richard
patent: 6771826 (2004-08-01), Boon
patent: 6791982 (2004-09-01), Westberg
patent: 6819271 (2004-11-01), Geiger et al.
patent: 7054912 (2006-05-01), Kanai et al.
patent: 7058941 (2006-06-01), Venkatesan et al.
patent: 7099884 (2006-08-01), Gu
patent: 2002/0010702 (2002-01-01), Ajtai et al.
patent: 2002/0152219 (2002-10-01), Garcia-Osuna et al.
patent: 2003/0028867 (2003-02-01), Kryloff et al.
patent: 2003/0061287 (2003-03-01), Yu et al.
patent: 2003/0110296 (2003-06-01), Kirsch et al.
patent: 2003/0133616 (2003-07-01), Lippincott
patent: 2003/0177485 (2003-09-01), Waldin et al.
patent: 2003/0187960 (2003-10-01), Koba et al.
patent: 2004/0015697 (2004-01-01), de Queiroz
patent: 2004/0039716 (2004-02-01), Thompson
patent: 2004/0054700 (2004-03-01), Okada
patent: 2005/0235043 (2005-10-01), Teodosiu et al.
patent: 2005/0256974 (2005-11-01), Teodosiu et al.
patent: 2005/0262167 (2005-11-01), Teodosiu et al.
patent: 2006/0047855 (2006-03-01), Gurevich et al.
patent: 2006/0085561 (2006-04-01), Manasse et al.
patent: 2006/0112113 (2006-05-01), Gu et al.
patent: 2006/0184652 (2006-08-01), Teodosiu et al.
patent: 01587007 (1995-10-01), None
patent: 01587007 (2005-10-01), None
patent: 01641219 (2006-03-01), None
patent: WO 98/27483 (1998-06-01), None
patent: WO 98/35306 (1998-08-01), None
patent: WO 02/41147 (2002-05-01), None
Tridgell, Andrew,Rsync algorithm, http://www.infoscience.co.jp/technical/rsync/tech—report/index.html.
Tridgell, Andrew,Rsync algorithm, http://olstrans.sourceforge.net/release/OLS2000-rsync/OLS2000-rsync.html.
Samba documentation http://rsync.samba.org/documentation.html.
Muthitacharoen, et. al.,Low-Bandwidth File System(LBFS), http://pdos.csail.mit.edu/papers/lbfs:sosp01/1bfs.pdf.
Muthitacharoen, Athicha; Chen, Benjie; Mazières, David. “A Low-bandwidth network file system,” Proceedings of the eighteenth ACM symposium on Operating systems principles, 2001, pp. 174-187.
Burns, Randal C.; Long, Darrell D.E. “Efficient Distributed Backup with Delta Compression,” Proceedings of the fifth workshop on L/O in parallel and distributed, 1997, pp. 27-36.
Spring, Neil T.; Wetherall, David. “A protocol-independent technique for eliminating redundant network traffic,” Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication; 2000, pp. 87-95.
Douglis, Fred; Iyengar, Arun. “Application-speicific Delta-encoding via Resemblance Detection,” USENIX Annual Technical Conference, 2003, [14 pages].
Randal C. Burns; “Differential Compression: A Generalized Solution for Binary Files”; Dec. 1996; pp. 1-61.
Randal C. Burns et al.; “A Linear Time, Constant Space Differencing Algorithm”; 8 pgs.
Miklos Ajtai et al.; “Compactly Encoding: Unstructured Inputs with Differential Compression”; Journal of ACM, vol. 49, No. 3, May 2002; pp. 318-367.
John Langford, “Multiround Rsync,” Jan. 31, 2001, p. 1-11.
Torsten Suel et al., “Algorithms for Delta Compression and Remote File Synchronization,” {suel,memon}@poly.eduAcademic Press, Aug. 2002, 24 pgs.
Andrei Z. Broder, On the resemblance and containment of documents,IEEE, 1997 Proceedings on Compression and Complexity of Sequences Conference Jun. 11-13, 1997 (11 pgs.).
Kave Eshghi, “Intrinsic References In Distributed Systems,”Hewlett-Packard Company, 2002, pp. 1-8.
Raffaele Giancarlo, et al., Combinatorial Pattern Matching, 11th Annual Symposium, CPM 2000,Springer(13 pgs.).
Kotz, et al., “I/O in Parallel and Distributed Systems,” Mar. 1, 1998, (last viewed Mar. 14, 2007) pp. 1-29, http://72.14.253.104/search?q=cache:OZiK—nQxc2sJ:www/cs/dart,pitj/edi/˜dfk/papers.
Dr. Jim Hamilton et al, “Design and Implementation of a Storage Repository Using Commonality Factoring,”IEEE2003 (6 pgs).
Chang, et al., Mimic: Raw Activity Shipping for File Synchronization in Mobile File Systems, 2004ACM, pp. 165-176.
Purushottam Kulkarni, et al., “Redundancy Elimination Within Large Collection of Files,”USENIX Association, 2004, pp. 59-72.
Andrei Z. Border, Identifying and Filtering Near-Duplicate Documents,Combinatorial Pattern Matching, 11th Annual Symposium, CPM 2000, Montreal, Canada, Jun. 21-23, 2000 Proceedings,Springer, (13 pgs).
Randal C. Burns; “Differential Compression: A Generalized Solution for Binary Files,”University of California, Santa Cruz, Dec. 1996; (69 pgs.).
Randal C. Burns et al.; “A Linear Time, Constant Space Differencing Algorithm,”Performance, Computing and Communications Conference, IEEE International, Feb. 5-7, 1997, (8 pgs.).
Tridgell, The rsync algorithm,The Australian National University, Jun. 1996 (8 pgs.).
Tridgell,, “rsync algorithm,” Nov. 9, 1998 (last viewed Oct. 11, 2006) http://www.infoscience.co.jp/technical/rsync/tech—report/index.html (10 pgs.).
Tridgell,, “The Rsync Algorithm,” Jul. 21, 2000 (last viewed Oct. 11, 2006) http://olstrans.sourceforge.net/release/OLS2000-rsync/OLS2000-rsync.html (27 pgs.).
Tridgell, “Efficient Algorithms for Sorting and Synchronization,” Thesis—The Australian National University, Apr. 2000, (115 pgs.).
Samba documentation http://rsync.samba.org/documentation.html (last viewed Oct. 11, 2006) (1 pg.).
European Search Report EP05108288.1.
Examination Report for Europe Application No. EP05108288.1.
Response to Examination Report for Europe Application No. EP05108288.1.
Trigell, Andrew, “Efficient Algorithms for Sorting and Synchronization,” Feb. 1999, 115 pp.
Broder, Andrei Z., “Identifying and Filtering Near-Duplicate Documents,” (Sequence 1997), 10 pp.
Kotz, David, “I/O in parallel and Distributed Systems,” Department of Computer Science, Dartmouth College, pp. 1-10.
Non Final Office Action in U.S. Appl. No. 10/948,980 dated Sep. 3, 2008.
Non Final Office Action in U.S. Appl. No. 10/844,907 dated Nov. 14, 2006.
Final Office Action in U.S. Appl. No. 10/844,907 dated May 18, 2007.
First Office Action in Chinese Application No. 200510108958.3 dated Aug. 1, 2008.
Torsten Suel et al.; “Improved File Synchronization Techniques for Maintaining Large Replicated Collections over Slow Networks,”In Proceedings: IEEE 20 International Conference on Data Engineering, Mar. 30, 2004 to Apr. 2, 2004,
Bjørner Nikolaj S.
Bozeman Patrick E.
Gurevich Yuri
Teodosiu Dan
Daftuar Saket K
Follansbee John
Merchant & Gould P.C.
Microsoft Corporation
LandOfFree
Efficient algorithm and protocol for remote differential... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient algorithm and protocol for remote differential..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient algorithm and protocol for remote differential... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4120081