US008001096B2
`
`a2) United States Patent
`US 8,001,096 B2
`(0) Patent No.:
`*Aug. 16, 2011
`(45) Date of Patent:
`Farberet al.
`
`(54) COMPUTER FILE SYSTEM USING
`CONTENT-DEPENDENTFILE IDENTIFIERS
`
`(75)
`
`Inventors: David A. Farber, Ojai, CA (US);
`Ronald D. Lachman, Northbrook, IL
`(US)
`
`(73) Assignees: Kinetech, Inc., Studio City, CA (US);
`Level 3 Communications, LLC,
`Broomfield, CO (US)
`
`(*) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 514 days.
`
`This patent is subject to a terminal dis-
`claimer.
`
`(21) Appl. No.: 11/980,677
`
`(22)
`
`Filed:
`
`Oct. 31, 2007
`
`(65)
`
`Prior Publication Data
`
`US 2008/0082551 Al
`
`Apr. 3, 2008
`
`Related U.S. Application Data
`
`(60) Continuation of application No. 11/724,232, filed on
`Mar. 15, 2007, which is a continuation of application
`No. 11/017,650, filed on Dec. 22, 2004, which is a
`continuation of application No. 10/742,972, filed on
`Dec. 23, 2003, which is a continuation of application
`No. 09/987,723, filed on Nov. 15, 2001, now Pat. No.
`6,928,442, which is a continuation of application No.
`09/283,160,
`filed on Apr. 1, 1999, now Pat. No.
`6,415,280, which is a division of application No.
`08/960,079, filed on Oct. 24, 1997, now Pat. No.
`5,978,791, which is a continuation of application No.
`08/425,160, filed on Apr. 11, 1995, now abandoned,
`application No. 11/980,677, which is a continuation of
`application No. 10/742,972, filed on Dec. 23, 2003,
`whichis a division ofapplication No. 09/987,723, filed
`on Nov. 15, 2001, now Pat. No. 6,928,442, which is a
`continuation of application No. 09/283,160, filed on
`Apr. 1, 1999, now Pat. No. 6,415,280, which is a
`
`continuation of application No. 08/960,079, filed on
`Oct. 24, 1997, now Pat. No. 5,978,791, which is a
`continuation of application No. 08/425,160, filed on
`Apr. 11, 1995, now abandoned.
`
`(51)
`
`Int. Cl.
`(2006.01)
`G06F 17/30
`(52) U.S.C occ 707/698; 707/690; 707/699
`(58) Field of Classification Search .................. 707/690,
`707/698, 699
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`3,668,647 A
`
`6/1972 Evangelisti et al.
`(Continued)
`
`EP
`
`FOREIGN PATENT DOCUMENTS
`0 268 069 A2
`5/1988
`
`(Continued)
`OTHER PUBLICATIONS
`
`Cheriton, David R. and Mann, Timothy P., “Decentralizing a global
`naming service for improved performanceandfault tolerance”, ACM
`Transactions on Computer Systems, vol. 7, No. 2, May 1989, pp.
`147-183.
`
`(Continued)
`
`Primary Examiner — Khanh B Pham
`(74) Attorney, Agent,
`or Firm —Davidson Berquist
`Jackson & Gowdey, LLP; Brian Siritzky
`
`ABSTRACT
`(57)
`A file system includes a plurality of servers to store file data
`as segments or chunks; andfirst data that includes file iden-
`tifiers for files for which the file data are stored as segments;
`and second data that mapsthefile identifiers to the segments
`to whichthefile identifiers correspond; and location data that
`identifies which of the plurality of servers stores which ofthe
`segments, the location data being keyed on segmentidentifi-
`ers, each segment identifier being based on the data in a
`corresponding segment.
`
`137 Claims, 31 Drawing Sheets
`
`cae
`
`DATA ITEM
`
`DATA ITEM
`
`DATA ITEM COMPUTE MD FUNCTION ON
`
`APPEND LENGTH MODULO 32 OF
`
`i
`i
`
`APPLE 1017
`
`APPLE 1017
`
`1
`
`

`

`US 8,001,096 B2
`
`Page 2
`
`10/1994 Talbott et al.
`5,359,523 A
`U.S. PATENT DOCUMENTS
`11/1994 Clark et al.
`5,361,356 A
`3,835,260 A
`9/1974 Prescher etal.
`12/1994 Brownetal.
`5,371,897 A
`4.096.568 A
`6/1978 Bennett et al
`iiloos cunteret al.
`oerees A
`4.215402 A
`7/1980. Mitchell etal.
`2/1995 Hunter et al
`5.304.555 A
`4,221,003 A
`9/1980 Changet al.
`ay
`4,290,105 A
`9/1981 Cichelli et al.
`4/1995 Belsan etal.
`5,403,639 A
`4376-299 A
`3/1983 Rivest
`4/1995 Konradetal.
`5,404,508 A
`4408899 A
`9/1983 Rivest et al
`SsTooe man
`easaay ‘
`4,412,285 A
`10/1983 Nechesetal.
`1
`:
`9/1995 Perel
`5 448668 A
`4,414,624 A
`11/1983 Summer,Jr. et al.
`9/1998 Conon
`S448718 A
`4,441,155 A
`4/1984 Fletcheretal.
`oan
`er
`al.
`oe
`4,464,713 A
`8/1984 Benhaseet al.
`9/1995 Nelson et al.
`5,452,447 A
`4.490.782 A
`12/1984 Dixon et al
`lope Corian thetal
`odeoso A
`4.558.413 A
`12/1985 Schmidt etal.
`10/1998 Burnet
`etal.
`5°450°860 A
`4,571,700 A
`2/1986 Emry,Jr. et al.
`une
`ee
`4,577,293 A
`3/1986 Matick et al.
`11/1995 Winterbottom
`5,465,365 A
`4.642.764 A
`2/1987 Ausland
`11/1995 Bader
`5,467,471 A
`4642.793 A
`9/1987 Meaden
`12/1995 Fischer
`5,475,826 A
`4658093 A
`4/1987 Hellman
`sateen Squibb
`5,479,054 A
`4.675.810 A
`6/1987 Gruner et al.
`Stoo popalefal.
`2400804 ‘
`4.691.299 A
`9/1987. Rivest etal.
`tal
`4/1996 Eisenb
`5.504.879 A
`4,725,945 A
`2/1988 Kronstadtet al.
`6/1996 Kraw. a a
`5'830.757 A
`4,773,039 A
`9/1988 Zamora
`7/1996 Blickenct fetal
`5.537585 A
`4,821,184 A
`4/1989 Clancyet al.
`7/1996 Neimatetal.
`5547087 A
`4,887,235 A
`12/1989 Hollowayet al.
`eumat
`et
`al.
`ne
`4,888,681 A
`12/1989 Barneset al.
`8/1996 Akizawaetal.
`5,548,724 A
`4914571 A
`4/1990 Baratzet al
`;
`loviooe Coss etal
`oesitt
`4.914.586 A
`4/1990. Swinehart etal.
`12/1996 Sten etal.
`Ss81615 A
`4,922,414 A
`5/1990 Hollowayetal.
`10/1996 Burnett
`5581758 A
`4,922,417 A
`5/1990 Churm etal.
`12/1906. Fi
`Idetal
`S381 764 A
`4,937,863 A
`6/1990 Robert et al.
`«15/1996 oa oe
`2283008 &
`4,949,302 A
`8/1990. Arnoldet al.
`arener era.
`200"
`4,953,209 A
`8/1990 Ryder,Sr. et al.
`12/1996 Neeman etal.
`5,588,147 A
`4.972.367 A
`11/1990 Burk
`1/1997 Daoet al.
`5,596,744 A
`S008401 A
`6/1991 Cho
`soo) Howard
`oooeat ‘
`5.014.192 A
`7/1991. Mansfield etal.
`2/1997 Nuttall et al
`5.604.892 A
`5,032,979 A
`7/1991 Hecht etal.
`.
`:
`ean’
`5,047,918 A
`9/1991 Schwartz etal.
`5/1997 Kindell et al.
`5,630,067 A
`5050074 A
`9/1991 M
`5/1997 Velissaropoulosetal.
`5,632,031 A
`5080212 A
`9/199] Dyson
`6/1997 Stefik et al.
`5,638,443 A
`5.057.837 A
`10/1991 Colwell et al.
`6/1997 Hamilton et al.
`5,640,564 A
`5.077658 A
`12/1991 Bendert
`7/1997 Woodhill etal.
`5,649,196 A
`S08481s A
`1/1992 Maz ert
`10/1997 Blakley, III et al.
`5,677,952 A
`S117351 A
`5/1992 Miller
`
`
`
`5,129,082 A
`7/1992 Tirfingetal.
`5694472 A
`12/1997.
`J in ° tal verter
`5,144,667 A
`9/1992 Pogue,Jr. et al.
`5604506 A
`10/1997 C.
`sbell
`5,163,147 A
`11/1992 Orita
`one
`ampre
`5179,680 A
`1/1993 Colwell et al
`5,701,316 A
`12/1997 Alfernessetal.
`5189799 A
`1/1903 ‘Tamara ct al
`5,710,922 A
`1/1998 Alley et al.
`5199073 A
`3/1993 Scott
`5,724,425 A
`3/1998 Changet al.
`5.202.982 A
`4/1993. Gramlich etal.
`os07 ‘
`Aloos nda
`5,204,897 A
`4/1993 Wyman
`5745870 A
`4/1998 Woma sr
`5,204,958 A
`4/1993 Chenget al.
`3787913 A
`5/1908. Bellareetal
`.
`5,204,966 A
`4/1993 Wittenberg etal.
`nen
`.
`5208 858 A
`5/1993 Vollert
`et al
`5,757,915 A
`5/1998 Aucsmithet al.
`3990134 A
`6/1993 a tal.
`5,781,629 A
`7/1998 Haberet al.
`5230081 A
`7/1993 Quan
`5,802,291 A
`9/1998 Balick et al.
`5930,648 A
`8/1993 Nukui
`5,809,494 A
`9/1998 Nguyen
`SAL eTl A
`8/1993 Reed etal
`5,826,049 A
`10/1998 Ogataet al.
`5.247.620 A
`9/1993. Fukuzawaet al.
`oNereny
`‘toes perca ;
`5,260,999 A
`11/1993 Wyman
`5007619 A
`5/1999 pee
`209,
`5907,
`avis
`oreo, ‘
`ti1904 Herrectal
`5.907.704 A
`3/1999 Gudmundsonetal.
`5987499 A
`1994 N
`eal
`5,940,504 A
`8/1999 Griswold
`587514 A
`9/1904 Gran
`5,978,791 A
`11/1999 Farberet al.
`5907979 A
`3/1994 Bannon etal
`5,991,414 A
`11/1999 Garayet al.
`5301086 A
`4/1904. Rajani
`6,006,018 A
`12/1999 Burnett et al.
`5.301.316 A
`4/1994. Hamilton etal.
`eee A
`Hooeeg jones et ar
`5,317,693 A
`5/1994 Cuenodetal.
`os
`5,321,841 A
`6/1994 Eastet al.
`6,415,280 Bl
`7/2002 Farberetal.
`5.339.403 A
`8/1994 Parker
`6,732,180 Bl
`5/2004 Hale et al.
`5,341,477 A
`8/1994 Pitkin etal.
`6,816,872 Bl
`11/2004 Squibb
`5,343,527 A
`8/1994 Moore veeccccccccscsesceeseees 713/179
`6,928,442 B2
`8/2005 Farberetal.
`5,347,653 A
`9/1994 Flynn etal.
`2002/0052884 Al
`5/2002. Farberetal.
`5,351,302 A
`9/1994 Leighton et al.
`2002/0082999 Al
`6/2002 Lee etal.
`5,357,440 A
`10/1994 Talbott et al.
`2003/0078888 Al
`4/2003 Lee etal.
`5,357,623 A
`10/1994 Megory-Cohen
`2003/0078889 Al
`4/2003 Lee etal.
`5,357,630 A
`10/1994 Oprescu et al.
`2003/0095660 Al
`5/2003 Lee etal.
`
`5,129,081 A Ser8046 A*101997 Cahilletal7/1992 Kobayashiet al. 707/829
`
`2
`
`

`

`US 8,001,096 B2
`
`Page 3
`
`2004/0139097 Al
`2005/0010792 Al
`2005/0114296 Al
`2007/0185848 Al
`2008/0065635 Al
`2008/0066191 Al
`2008/0071855 Al
`2008/0082551 Al
`
`7/2004 Farberet al.
`1/2005 Carpentier et al.
`5/2005 Farberet al.
`8/2007 Farberetal.
`3/2008 Farberet al.
`3/2008 Farberet al.
`3/2008 Farberet al.
`4/2008 Farber etal.
`
`Bowman, C.M., et al., “Scalable Internet Resource Discovery:
`Research Problems and Approaches,” University of Colorado, Dept.
`of Comp. Sci. Technical Report# CU-CS-679-93 (Oct. 1993).
`Bowman, C.M., et al., “Research Problems for Scalable Internet
`Resource Discovery,” CU-CS-643-93, Mar. 1993, University of
`Colorado at Boulder, Dept. of Comp.Sci.
`Cate, V., “Alex—aGlobalFilesystem,” Proceedings of the USENIX
`File Systems Workshop,pp. 1-11, May 1992.
`FOREIGN PATENT DOCUMENTS
`Dewitt, et al. (Jun. 1984). “Implementation techniques for main
`0315 425
`5/1989
`EP
`memory database systems”. Proc. ACM SIGMODConf14 (4): 1-8.
`0 558945 A2
`9/1993
`EP
`Fagin, R., et al. Extendible hashing—a fast access method for
`
`EP 0 566 967 A2=10/1993
`dynamicfiles. ACM Trans. Database Syst. 4,3 (Sep. 1979), 315-344.
`EP
`0592045
`4/1994
`Griswold, William G.; Townsend, Gregg M. (Apr. 1993), “The
`
`EP 0631226 Al=12/1994
`EP
`0 654920 A2
`5/1995
`Design and Implementation of Dynamic Hashing for Sets and Tables
`EP
`0 658 022 A2
`6/1995
`in Icon”, Software—Practice and Experience 23 (4): 351-367 (Apr.
`GB
`2294132 A
`4/1996
`1993).
`JP
`59058564
`4/1984
`Hardy D. R., et al., “Essence: A resource discovery system based on
`JP
`63-106048
`5/1988
`semantic file indexing,” USENIX Winter 1993 Technical Conf., San
`JP
`63-273961
`11/1988
`Diego, CA (Jan. 1993), pp. 361-374.
`JP
`2-127755
`5/1990
`Kahn, R.E., “Deposit, Registration and Recordation in an Electronic
`JP
`05162529
`6/1993
`JP
`06187384 A2
`TN994
`Copyright Management System,” Tech. Report, Corporation for
`JP
`06348558 A
`12/1994
`National Research Initiatives, Reston, Virginia, Aug. 1992 (down-
`WO
`WO 92/20021
`11/1992
`loaded from _http://archive.ifla.org/documents/infopol/copyright/
`WO
`WO 94/06087
`3/1994
`kahn.txt on Nov. 10, 2010).
`WO
`WO 94/209 13
`9/1994
`Kitsuregawa, M.; Tanaka, H.; Moto-Oka, T. (Mar. 1983). “Applica-
`WO
`WO 95/01599
`1/1995
`tion of Hash to Data Base Machine andIts Architecture”. New Gen-
`WO
`WO 97/43717
`11/1997
`eration Computing | (1): 63-74, OHMSHA, LID. and Springer-
`Verlag.
`Litwin, W., “Linear Hashing: a New Toolfor File and Table Address-
`ing,” Proc. 6th Int. Conf. on Very Large Databases, IEEE 1980,
`212-223.
`Manber, U., Finding similar files in a large file system, Dept. of
`Computer Science TR 93-33, Oct. 1993., U. ofArizona, Tucson, AZ.
`Manber, U., Finding similar files in a large file system, USENIX,pp.
`1-10, San Francisco, CA, Jan. 1994. (WTEC’94, Proc. USENIX
`Winter 1994 Technical Conf.)
`USPTO,Non-Final Office Action mailed Jul. 2, 2010 in U.S. Appl.
`No. 11/980,688.
`USPTO,Notice ofAllowance mailed Apr. 30, 2010 in U.S. Appl. No.
`11/980,687.
`USPTO,Notice ofAllowance mailed Jun. 24, 2010 in U.S. Appl. No.
`11/980,687.
`USPTO,Supplemental Notice of Allowability mailed May 27, 2010
`in U.S. Appl. No. 11/980,687.
`[Proposed] Order Regarding Construction of Terms, filed Mar. 29,
`2007 in C.D. Cal. case No. CV 06-5086 SJO (Ex) [9 pgs.]
`Analysis of Plaintiffs’ Claim Chart for the ’280 Patent As Against
`Defendant Media Sentry, Inc. 11 pages filed May 21, 2007.
`Analysis of Plaintiffs’ Claim Chart for the ’791 Patent As Against
`Defendant Media Sentry, Inc. (11916.001.0150.a) pp. 1-48, filed
`Aug. 14, 2006.
`Analysis of Plaintiffs’ Claim Chart for the ’791 Patent As Against
`Defendant Overpeer pp. 1-40,filed Aug. 14, 2006.
`Barbara,D., et al., “Exploiting symmetries for low-cost comparison
`of file copies,” 8th Int’! Conf. on Distributed Computing Systems;
`Jun. 1988, pp. 471-479, San Jose, CA.
`Campbell, M., “The Design of Text Signatures for Text Retrieval
`Systems,” Tech. Report, Sep. 5, 1994, Deakin University, School of
`Computing & Math. Geelong, Australia.
`Chang, W. W.et al., “A signature access method for the Starburst
`database system,” in Proc. 15th Int’l Conf. on Very Large Data Bases
`(Amsterdam, The Netherlands), pp. 145-153, 1989.
`Changesto Mar. 23, 2007 Deposition of Robert B. K. Dewar, in C.D.
`Cal. case No. CV 06-5086 SJO (Ex) [3 pgs + coverletter.].
`Communication from EPO in European Application No. 96 910
`762.2—1225 dated May 8, 2009 [4 pgs.].
`Communication pursuant to Article 96(2) EPC from EPO (Examina-
`tion Report), Jan. 17, 2007, in Application No. EP 96 910 762.2-225
`[1 pg. with 5 pg. annex].
`Complaint for Patent Infringement, Permanent Injunction and Dam-
`ages, Aug. 8, 2006, in C.D. Cal. case No. CV 06-5086 SJO (Ex) [11
`pgs.].
`
`Request for Reexamination of U.S. Patent No. 6,928,442: Reexam
`Control No. 90/010,260, filed on Aug. 29, 2008.
`USPTO,U.S. Reexam Control No. 90/010,260, Notice of Intent to
`Issue Ex Parte Reexamination Certificate, Apr. 8, 2010.
`WIPO,International Preliminary Examination Report (IPER), Jul.
`1997, PCT/US96/04733 [5 pgs.].
`Fowler, et al. “A User-Level Replicated File System,” AT&T Bell
`Laboratories Technical Memorandum 0112670-930414-05, Apr.
`1993, and USENIX 1993 Summer Conference Proceedings, Cincin-
`nati, OH, Jun. 1993.
`Greene, D., et al., “Multi-Index Hashing for Information Retrieval’,
`Nov. 20-22, 1994, Proceedings, 3 5th Annual Symp on Foundations of
`Computer Science, IEEE, pp. 722-731.
`Hirano, et al, “Extendible hashing for concurrent insertions and
`retrievals,” in Proc 4th Euromicro WorkshoponParallel and Distrib-
`uted Processing, 1996 (PDP ’96), Jan. 24, 1996 to Jan. 26, 1996, pp.
`235-242, Braga , Portugal.
`Preneelet al., “The Cryptographic Hash Function RIPEMD-160”,
`appeared in CryptoBytes RSA Laboratories, vol. 3, No. 2, pp. 9-14,
`Fall, 1997 (also Bosselaersetal., “The RIPEMD-160 Cryptographic
`Hash Function”, Jan. 1997, Dr. Dobb’s Journal, pp. 24-28).
`Pruskeret al., “The Siphon: Managing Distant Replicated Reposito-
`ties” Nov. 8-9, 1990, Proc. Managementof Replicated Data IEEE.
`Reply to Examination Report, Munich, Nov. 18, 2009, in Application
`No. EP 96 910 762.2 [19 pgs.].
`Rich, K. et al, “Hobgoblin: A File and Directory Auditor’, Sep.
`30-Oct. 3, 1991, Lisa V., San Diego, CA.
`USPTOFinal Office Action in U.S. Appl. No. 10/742,972, Dec. 22,
`2009.
`USPTO, Advisory Action, Mar. 23, 2010,
`11/980,679.
`USPTO, Final Office Action in U.S. Reexam Control No.
`90/010,260, Jan. 29, 2010.
`USPTO,Final Office Action mailed Jan. 12, 2010 in U.S. Appl. No.
`11/980,679.
`USPTO,Final Office Action mailed Aug. 18, 2009 in U.S. Appl. No.
`11/017,650.
`USPTO,Final Office Action mailed Sep. 30, 2009 in U.S. Appl. No.
`11/724,232.
`USPTO, Final Office Action, Mar. 5, 2010 in U.S. Appl. No.
`11/980,687.
`
`OTHER PUBLICATIONS
`
`in U.S. Appl. No.
`
`3
`
`

`

`US 8,001,096 B2
`Page 4
`
`Complaint for Patent Infringement, Permanent Injunction and Dam-
`ages, filed Sep. 21, 2007 in C.D. Cal. Case No. CV 07-06161 VBF
`(PLAx) [10 pgs.].
`Declaration ofCharles S. Baker in Support ofDefendant Lime Wire’s
`Motion to Stay Pending Reexamination of Patent and Request for
`Extension of Deadlines, Aug. 29, 2008, in C.D. Cal. Case No. CV
`07-06161 VBF (PLAx)[2 pgs.].
`Defendant Lime Wire, LLC’s First Amended Answer, Affirmative
`Defenses and Counterclaims, Oct. 2, 2008, C.D. Cal. case No.
`07-06161 VBF (PLAx)[13 pgs.].
`Defendant Lime Wire, LLC’ s Second Amended Answer, Affirmative
`Defenses and Counterclaims, Oct. 27, 2008, from C.D. Cal. case No.
`07-06161 VBF (PLAx)[13 pgs.].
`Defendant Michael Weiss’s Answer to Plaintiff's Complaint for
`Patent Infringement, Permanent Injunction and Damages; Demand
`for Jury Trial, Sep. 15, 2006, case No. CV 06-5086 SJO (Ex) [10
`pgs.].
`Defendant Recording Industry Association of America’s Amended
`Notice of Motion and Motion for Partial Summary Judgment on
`Plaintiffs’ Claims for Patent Infringement and Inducing Patent
`Infringement; Memorandum of Points and Authorities, May 22,
`2006, redacted, original confidential, filed under seal, in C.D. Cal.
`case No. CV 04-7456 JFW (CTx)[19 pgs.].
`Defendant Recording Industry Association of America’s and
`Mediasentry, Inc.’s Notice of Motion and Motion for Partial Sum-
`mary Judgment Based on Implied License or, In the Alternative,
`Based on Patent Misuse and Unclean Hands, May 22, 2006,
`Redacted, in C.D. Cal. case No. CV 04-7456 JFW (CTx) [21 pgs.].
`Defendant Recording Industry Association of America’s and
`Mediasentry, Inc’s Notice of Motion and Motion for Partial Sum-
`mary Judgment Based on Implied License or, in the Alternative,
`Based on Patent Misuse and Unclean Hands, May 8, 2006, in C.D.
`Cal. case No. CV 04-7456 JFW (CTx)[20 pgs.].
`Defendant StreamCast Networks Inc.’s Answerto Plaintiff's Com-
`plaint for Patent Infringement, Permanent Injunction and Damages;
`Demandfor Jury Trial, Sep. 5, 2006, C.D. Cal. case No. CV 06-5086
`SJO (Ex) [10 pgs.].
`Defendants’ Amended. Preliminary Claim Constructions [Patent
`Rule 4-2], filed Feb. 7, 2007 in C.D. Cal. case No. CV 06-5086 SJO
`(Ex) [10 pgs.].
`Defendant’s Second Amended Preliminary Claim Constructions
`[Patent Rule 4-2], filed Feb. 9, 2007 in C.D. Cal. case No. CV
`06-5086 SJO (Ex) [10 pgs.].
`Dewar, Rebuttal Expert Report of Robert B.K. Dewar, in C.D. Cal.
`case No. CV 04-7456 JFW (CTx), Apr. 10, 2006 [87 pgs].
`Faloutsos, C. “Access methods for text;’ ACM Comput. Surv. 17, 1
`(Mar. 1985), 49-74.
`Faloutsos, C. et al., “Description and performance analysis of signa-
`ture file methods foroffice filing”’ ACM Trans. Inf. Syst. 5, 3 Jul.
`1987), 237-257.
`Faloutsos,C. et al., “Signaturefiles: an access method for documents
`and its analytical performance evaluation,” ACM Trans. Inf. Syst. 2,
`4 (Oct. 1984), 267-288.
`Federal Information Processing Standards (FIPS) Publication 180-1;
`Secure Hash Standard, Apr. 17, 1995 [17 pgs.]
`Feigenbaum,J. et al., “Cryptographic protection of databases and
`software,’
`in Distributed Computing and Cryptography: Proc.
`DIMACS Workshop,Apr. 1991, pp. 161-172, American Mathemati-
`cal Society, Boston, Mass.
`First Amended Answer of Defendant Mediasentry to Second
`Amended Complaint and Counterclaim, Apr. 24, 2006, in C.D. Cal.
`case No. CV 04-7456 JFW(CTx)[29 pgs.].
`First Amended Answer of Defendant RIAA to Second Amended.
`Complaint and Counterclaim, Apr. 24, 2006, in C.D. Cal. Case No.
`CV 04-7456 JFW (CTX)[27 pgs.].
`First Amended Complaint
`for Patent Infringement, Permanent
`Injunction and Damages,filed Sep. 8, 2008 in C.D. Cal. Case No. CV
`07-06161 VBF (PLAx)[10 pgs.].
`Harrison, M. C., “Implementation of the substring test by hashing,”
`Commun. ACM 14, 12 (Dec. 1971), 777-779.
`IEEE, The Authoritative Dictionary of IEEE Standards Terms, 7th
`ed., Copyright 2000, pp. 107, 176, 209, 240, 241, 432, 468, 505, 506,
`682, 1016, 1113, 1266, and 1267.
`
`Ishikawa,Y., et al., “Evaluation of signature files as set access facili-
`ties in OODBs,”In Proc. of the 1993 ACM SIGMODInter. Conf. on
`Management of Data (Washington, D.C., U.S., May, 1993). P. Bune-
`man & S. Jajodia, Eds. SIGMOD ’93. ACM,NY, NY, 247-256.
`Joint Claim Construction and Prehearing Statement, N. D. Cal. Rule
`4-3, Feb. 12, 2007, in C.D. Cal. case No. CV 06-5086 SJO (Ex) [20
`pgs.].
`Karp, R. M. and Rabin, M. O., “Efficient randomized pattern-match-
`ing algorithms,” IBM J. Res. Dev. 31, 2 (Mar. 1987), 249-260.
`List of Asserted Claims and Infringement Chart for Each Asserted.
`Claim, Jul. 28, 2008, in C.D. Cal. Case No. CV 07-06161 VBF
`(PLAX) [31 pgs.].
`McGregor D. R. and Mariani,J. A. “Fingerprinting—Atechnique for
`file identification and maintenance,” Software: Practice and Experi-
`ence, vol. 12, No. 12, Dec. 1982, pp. 1165-1166.
`Notice of Interested Parties,filed Sep. 21, 2007 in C.D. Cal. Case No.
`CV 07-06161 VBF (PLAX)[2 pgs.].
`Notice of Motion and Motion of Defendant Lime Wireto Stay Liti-
`gation Pending Reexamination of Patent and Request for Extension
`of Deadlines, Sep. 22, 2008, C.D. Cal. Case No. CV 07-06161 VBF
`(PLAX)[11 pgs.].
`Notice ofRelated Cases,filed Sep. 21,2007 in C.D. Cal. Case No. CV
`07-06161 VBF (PLAx)[2 pgs.].
`Panagopoulos,G., et al., “Bit-sliced signature files for very large text
`databases on a parallel machine architecture,” in Proc. ofthe 4th Inter.
`Conf. on Extending Database Technology (EDBT), Cambridge,
`U.K., Mar. 1994, pp. 379-392 (Proc. LNCS 779 Springer 1994, ISBN
`3-540-578 18-8) [14 pgs.].
`Patent Abstract, “Management System for Plural Versions,” Pub. No.
`63273961 A, published Nov. 11, 1988, NEC Corp.
`Patent Abstracts of Japan, “Data Processor,” Appln. No. 05135620,
`filed Jun. 7, 1993, Toshiba Corp.
`Plaintiff Kinetech, Inc.’s Responses to Defendant Mediasentry’s
`First set of Interrogatories, May 1, 2006, in C.D. Cal. Case No. CV
`04-7456 JFW (CTx) [14 pgs.].
`Inc.’s Supplemental
`Plaintiff-Counterclaim Defendant Altnet,
`Responses to Defendant-Counterclaim Plaintiff Overpeer Inc.’s First
`Set of Interrogatories, Mar. 8, 2006, redacted, in C.D. Cal. case No.
`CV 04-7456 JEW (CTx) [24 pgs.].
`Plaintiff-Counterclaim Defendant Brilliant Digital Entertainment,
`Inc.’s Supplemental Responses to Defendant-Counterclaim Plaintiff
`OverpeerInc.’s First Set ofInterrogatories, Mar. 8, 2006, redacted, in
`C.D. Cal. case No. CV 04-7456 JFW (CTx) [24 pgs.].
`Plaintiff-Counterclaim Defendant Kinetech, Inc.’s Supplemental
`Responses to Defendant-Counterclaim Plaintiff Overpeer Inc.’s First
`Set of Interrogatories Mar. 8, 2006, redacted, in C.D. Cal. case No.
`CV 04-7456 JEW (CTx) [24 pgs.].
`Plaintiffs Altnet, Inc., Brilliant Digital, Inc., and Kinetech, Inc.’s
`Responses to Defendant Recording Industry Association of Ameri-
`ca’s First Set of Requests for Admissions, Jan. 6, 2006, in C.D. Cal.
`case No. CV 04-7456 JFW (CTx)[26 pgs.].
`Plaintiffs’ Claim Construction Opening Briefand Exhibits A-D,F, G;
`May7, 2007, in C.D. Cal. case No. CV 06-5086 SJO (Ex) [112 pgs.].
`Plaintiffs’ Preliminary Claim Constructions and Extrinsic Evidence,
`Feb. 6, 2006, in case CV 06-5086 SJO (Ex) [20 pgs.].
`Plaintiff's Reply to Defendant Mediasentry’s Counterclaimsin its
`Answer to the Second Amended Complaint, May 1, 2006, in C.D.
`Cal. Case No. CV 04-7456 JFW (CTx)[11 pgs.].
`Plaintiff's Reply to Defendant RIAA’s Counterclaimsin its Answer
`to the Second Amended Complaint, May 1, 2006, in C.D. Cal. case
`No. CV 04-7456 JFW (CTx) [11 pgs.].
`Plaintiffs’ Reply to Defendants’ Claim Construction Brief,filed Apr.
`23, 2007 in C.D. Cal. case No. CV 06-5086 ODW (Ex) [15 pgs.].
`Reply to Examination Report, Jul. 19, 2007, in Application No. EP 96
`910 762.2-1225 [7 pgs.].
`Response to Non-Final Office Action filed May 19, 2009 in U.S.
`Appl. No. 11/017,650 [19 pgs.].
`Rivest, R., RFC 1320, “The MD4 Message-Digest Algorithm,” The
`Internet Engineering Task Force ETF), Apr. 1992.
`Sacks-Davis,R., et al., “Multikey access methods based on superim-
`posed coding techniques,” ACM Trans. Database Syst. 12, 4 (Nov.
`1987), 655-696.
`
`4
`
`

`

`US 8,001,096 B2
`Page 5
`
`Siegel, A., et al., “Deceit: a Flexible Distributed File System,” Proc.
`Workshop on the Managementof Replicated Data, Houston, TX,pp.
`15-17, Nov. 8-9, 1990.
`Siegel, A., et al., “Deceit: a Flexible Distributed File System,” Tech-
`nical Report, TR89-1042, Cornell University, Nov. 1989.
`Stipulation and Proposed. order to (1) Amend. the Complaint, (2)
`Amendpretrial Schedule, and (3) Withdraw Motionto Stay,filed Sep.
`8, 2008 in C.D. Cal. Case No. CV 07-06161 VBF (PLAx) [6 pgs.].
`Streamcast Networks Inc.’s Supplemental Responses to Certain of
`Plaintiffs’ First Set of Interrogatories, Apr. 16, 2007, in C.D. Cal. case
`No. CV 06-5086 SJO (Ex) [61 pgs.].
`StreamCast’s Brief Re Claim Construction, Apr. 12, 2007, in C.D.
`Cal. case No. CV 06-5086 SJO (Ex) [11 pgs.].
`Transcript of Deposition of David Farber, Feb. 16, 2006, in C.D. Cal.
`case No. CV 04-7456 JFW (CTx)[94 pgs. ].
`Transcript of Deposition of Robert B. K. Dewar, Mar. 23, 2007, in
`C.D. Cal. case No. CV 06-5086 SJO (Ex) [61 pgs.].
`Transcript of Deposition of Ronald Lachman,Feb. 1, 2006, C.D. Cal.
`case No. CV 04-7456 JFW(CTx) [96 pgs.].
`USPTO,Non-Final Office Action mailed May6, 2009 in U.S. Appl.
`No. 11/980,679.
`USPTO,Non-Final Office action mailed Jun. 15, 2009 in U.S. Appl.
`No. 11/980,687.
`USPTO, Non-Final Office action mailed Jun. 18, 2009 in Reexam
`No. 90/010,260.
`the
`Advances
`in Cryptology-AUSCRYPT ’92—Workshop on_
`Theory and Application of Cryptographic Techniques Gold Coast,
`Queensland, Australia Dec. 13-16, 1992 Proceedings.
`Advances in Cryptology-EUROCRYPT ’93, Workshop on the
`Theory and Application of Cryptographic Techniques Lofthus, Nor-
`way, May 23-27, 1993 Proceedings.
`Affidavit of Timothy P. Walker in Support of CWIS’ Opening Mark-
`man Brief Construing the Terms at Issue in U.S. Patent No.
`6,415,280, dated Jul. 25, 2003, from Civil Action No. 02-11430
`RWZ.
`Akamai and MIT’s Memorandum in Support of Their Claim Con-
`struction of USPAT 5,978,791, dated Aug. 31, 2001, from Civil
`Action No. 00-cv-11851RWZ.
`Akamai’s Answer, Affirmative Defenses and Counterclaims to
`Amended Complaint, filed Dec. 6, 2002, in Civil Action No. 02-CV-
`11430RWZ.
`Akamai’s Brief on Claim Construction, dated Aug. 8, 2003, from
`Civil Action No. 02-11430 RWZ.
`Albert Langer
`(cmf851@anu.oz.au), http://groups.google.com/
`groups?selm=199 1 Aug7.225159.786%40newshost.anu.
`edu.au&
`oe=UTF-8&output=gplain, Aug. 7, 1991.
`Alexander Dupuy (dupuy@smarts.com), “MD5 and LIFNs (was:
`Misc Comments)”, www.acl.lanl.gov/URI/archive/uri-94q2.mes-
`sages/0081.html, Apr. 17, 1994.
`Alexander Dupuy (dupuy@smarts.com), “Re: MD5 and LIFNs(was:
`Misc Comments)”, www.acl.lanl.gov/URI/archive/uri-94q2.mes-
`sages/0113 html, Apr. 26, 1994.
`Answer of Defendant RIAAto First Amended Complaint and Coun-
`terclaim, dated Feb. 8, 2005, from Civil Action No. CV04-7456 JEW
`(CTX).
`Berners-Lee, T. et al., “Hypertext Transfer Protocol—HTTP/1.0,”
`May 1996, pp. 1-54.
`Berners-Lee,T.et al., “Uniform Resource Locators (URL),”pp. 1-25,
`Dec. 1994.
`Berners-Lee, T., “Universal Resource Identifiers in WWW,” Jun.
`1994, pp. 1-25.
`Bert dem Boer, et al., Collisions for the compression function of
`MD.sub.5 pp. 292-304, 1994.
`Birgit Pfitzman, Sorting Out Signature Schemes, Nov. 1993, |.sup.st
`Conf. Computer & Comm.Security ’93, p. 74-85.
`Birgit Pfitzmann, Sorting Out Signature Schemes, Nov. 1993, Ist
`Conf. Computer & Comm.Security ’93 pp. 74-85.
`Bowman,C. Mic, et al., “Harvest: A Scalable, Customizable Discov-
`ery and Access System,” Aug. 4, 1994, pp. 1-27.
`Bowman,C. Mic, et al., “Harvest: A Scalable, Customizable Discov-
`ery and Access System,” Mar. 12, 1995, pp. 1-29.
`Brisco, T., “DNS Support for Load Balancing,” Apr. 1995, pp. 1-7.
`Browne,Shirley et al., “Location-Independent Naming for Virtual
`Distributed Software Repositories,” 1995, 7 pages.
`Browne,Shirley et al., “Location-Independent Naming for Virtual
`Distributed Software Repositories,” 1995, printed from http:/www.
`netlib.org/utk/papers/lifn/main.html on Mar. 22, 2006, 18 pages.
`
`Carter, J. Lawrence, et al. “Universal Classes of Hash Functions.”
`Journal of Computer and System Sciences, vol. 18, No. 2, Apr. 1979,
`pp. 143-154.
`Chris Charnes and. Josef Pieprzky, Linear Nonequivalence versus
`Nonlinearity, Pieprzky, pp. 156-164, 1993.
`Civil Minutes General dated Jan. 25, 2005, from Civil Action No. CV
`04-7456-JFW (CTx).
`Clifford Lynch (Calur@ucemvsa.bitnet), “ietf url/uri overview draft
`paper
`(long)”, www.acl.lanl.gov/URIJ/archive/uri-93q1.messages/
`0015.html, Mar. 25, 1993.
`Complaintfor Patent Infringement, Permanent Injunction, and Dam-
`ages, dated Sep. 8, 2004, from Civil Action No. CV 04-7456 JFW
`(AJWx).
`Cormen, Thomas H., et al. Introduction to Algorithms, The MIT
`Press, Cambridge, Massachusetts, 1994, pp. 219-243, 991-993.
`CWIS’ Opening Markman Brief Construing the Terms at Issue in
`USS. Patent No. 6,415,280, dated Jul. 25, 2003, from Civil Action No.
`02-11430 RWZ.
`CWIS’ Reply Markman Brief Construing the Termsat Issue in U.S.
`Patent No. 6,415,280, dated Aug. 15, 2003, from Civil Action No.
`02-11430 RWZ.
`Danzig, P.B., et al., “Distributed Indexing: A Scalable Mechanism
`for Distributed Information Retrieval,’ Proceedings of the 14th
`Annual International ACM SIGIR Conference on Research and.
`Development in Information Retrieval, pp. 220-229, Oct. 13-16,
`1991.
`Davis, JamesR., “A Server for a Distributed Digital Technical Report
`Library,” Jan. 15, 1994, pp. 1-8.
`Declaration of Robert B.K. Dewar in Support of CWIS’ Construction
`of the Terms at Issue in U.S. Patent No. 6,415,280, dated Jul. 25,
`2003, from Civil Action No. 02-cv-11430RWZ.
`Deering, Stephen,
`et
`al,
`“Multicast Routing in Datagram
`Internetworks and Extended LANs.” ACM Transactions on Com-
`puter Systems, vol. 8, No. 2, May 1990, pp. 85-110.
`Defendant Digital Island’s Opening Brief on Claim Construction
`Issues dated Aug. 17, 2001, from Civil Action No. 00-cv-11851-
`RWZ.
`Defendant Lime Wire, LLC’s Answer, Affirmative Defenses and
`Counterclaims dated Nov. 15, 2007, from Civil Action No. 07-06161
`VBF (PLAX).
`Defendant Media Sentry, Inc.’s Reply Memorandum ofPoints and.
`Authorities in Further Support of Its Motion to Dismiss, dated Nov.
`15, 2004, from Civil Action No. CV04-7456 JFW (CTx).
`Defendant MediaSentry Inc.’s Notice of Motion and Motion to Dis-
`miss First Amended Complaint; Memorandum of Points and
`Authorities in Support Thereof, dated Dec. 13, 2004, from Civil
`Action No. CV04-7456 JFW (.
`Defendant MediaSentry, Inc.’s Answerto Plaintiffs’ First Amended
`Complaint and Counterclaims, dated Feb. 8, 2005, from Civil Action
`No. CV04-7456 JFW (CTx).
`Defendant RIAA’s Notice of Motion and Motion to Dismiss First
`Amended Complaint; Memorandum of Points and Authorities in
`Support Thereof, dated Dec. 13, 2004, from Civil Action No. CV04-
`7456 JFW (CTx).
`Defendants Loudeye Corp.’s and Overpeer, Inc.’s Answerto Plain-
`tiffs’ First Amended Complaint and Counterclaim, dated Feb. 8,
`2005, from Civil Action No. 04-7456 JFW (AJWx).
`Defendants’ Preliminary Invalidity Contentions dated Dec. 14, 2006,
`from Civil Action No. CV 06-5086 SJO (Ex).
`Devine, Robert. “Design and Implementation of DDH: A Distributed.
`Dynamic Hashing Algorithm.” In Proc. of 4th International Confer-
`ence on Foundations of Data Organizations and Algorithms, 1993,
`pp. 101-114.
`European Search Report issued Dec. 23, 2004 in correpsonding
`European Application No. 96910762.2-2201.
`Expert Report of Professor Ellis Horowitz, dated Mar. 6, 2006, from
`Civil Action No. 04-7456 JFW (CTx).
`Expert Report of the Honorable Gerald J. Mossinghoff, dated Mar.
`13, 2006, from Civil Action No. 04-7456 JFW (CTx).
`Faltstrom, P. et al., “How to Interact with a Whois++ Mesh,” Feb.
`1996, pp. 1-9.
`Feeley, Michael, et al. “Implementing Global Memory Management
`in a Workstation Cluster.” In Proc. of the 15th ACM Symp. on Oper-
`ating SystemsPrinciples, 1995, pp. 201-212.
`Fielding, R. et al., “Hypertext Transfer Protocol—HTTP/1.1,” Jan.
`1997, pp. 1-163.
`
`5
`
`5
`
`

`

`US 8,001,096 B2
`Page 6
`
`Fielding, R. et al., “Hypertext Transfer Protocol—HTTP/1.1,” Jun.
`1999, pp. 1-157.
`for Patent Infringement, Permanent
`First Amended Complaint
`Injunction and Damages, dated Nov. 24, 2004, from Civil Action No.
`CV 04-7456 JFW (CTx).
`Floyd, Sally,et al. “A reliable Multicast Frameworkfor Light-Weight
`Sessions and Application Level Framing.” In Proceeding of ACM
`SIGCOMM 795, pp. 342-356.
`Fredman, Michael, et al. “Storing a Sparse Table with 0(1) Worst
`Case Access Time.” Journal of the Association for Computing
`Machinery, vol. 31, No. 3, Jul. 1984, pp. 538-544.
`G.L. Friedman, Digital Camera With Apparatus For Authentication
`of Images Produced From an Image File, NASA Case No. NPO-
`19108-1-CU, U.S. Appl. No. 08/159,980, filed Nov. 24, 1993.
`Grigni, Michelangelo, etal. “Tight Bounds on Minimum Broadcasts
`Networks.” SIAM Journal of Discrete Mathematics, vol. 4, No. 2,
`May 1991, pp. 207-222.
`Gwertzman, James,et al. “The Case for Geographical Push-Cach-
`ing.” Technical Report HU TR 34-94 (excerpt), Harvard University,
`DAS, Cambridge, MA 02138, 1994, 2 pgs.
`H. Goodman,Ada, Object-Oriented Techniques, and Concurrency in
`Teaching Data Structures and File Management Report Documenta-
`tion p. AD-A275 385—94-04277.
`H. Goodman,Ada, Object-Oriented Techniques, and Concurrency in
`Teaching Data Sructures and File Management Report Documenta-
`tion p. AD-A275 385—94-04277.
`Hauzeur, B. M., “A Model for Naming, Addressing, And Routing,”
`ACMTrans. Inf. Syst. 4, Oct. 4, 1986), 293-311.
`International Search Report dated Jun. 24, 1996 in corresponding
`international application PCT/US1996/004733.
`K. Sollins and L. Masinter, “Functional Requirements for Uniform
`Resource Names”, www.w3.org/Addressing/rfc 1737 txt, Dec. 1994,
`pp. 1-7.
`Khare, R. and Lawrence,S., “Upgrading to TLS Within HTTP/1.1,”
`May 2000, pp. 1-12.
`Khoshafian, S. N. et al. 1986. Object identity. In Conf. Proc. on
`Object-Oriented Programming Systems, Languages and Applica-
`tions (Portland, Oregon, United States, Sep. 29-Oct. 2, 1986). N.
`Meyrowitz, Ed. OOPLSA ’86. ACM Press, New York, NY, 406-416.
`Kim et al., “Experiences with Tripwire: Using Integrity Checkers for
`Intrusion Detection”, COAST Labs. Dept.