:51:= I—-
`i :E K;
`‘hsfi‘ “’
`‘\"~E 7:
`SE‘ 5”
`:3
`‘- 3
`I
`
`e:
`
`4'
`.
`
`I
`
`For Desi n or Utilit A Iications
`'
`
`Rule 53(b)(1) PATENT APPLICATION:
`[Z
`Continuation
`
`) )
`
`application under 37 CFR 1.53(b)(1)
`
`IN THE UNITED STATES PATENT AND TRADEMARK
`'
`OFFICE
`REQUEST FOR FILING
`(RULE 53(b)(1))
`
`a flat-4
`9‘... r:
`.. 2.35:"
`vino_ fig
`sci-E:
`«‘5:
`89%
`2%
`(DO NOT USE FOR ClPs)
`
`)
`Divisional
`El
`application under 37 CFR 1.53(b)(1)
`of pending prior application of
`
`‘
`Farber et al.
`inventor(s):
`Parent'AppIn. No.:
`
`09
`Series Code 0
`
`Group Art Unit:
`
`2771
`
`Examiner:
`
`Jean HOMERE
`
`283,160
`Serial No. 1.?
`
`Atty. Dkt.
`
`P 283002
`MW!
`
`TN-Cont—2
`Client Ref
`
`Parent Filed: April 1, 1999
`This Appln. Filed:
`November 15, 2001
`
`Title:
`
`ldentifiying Data in a Data Processing System
`
`November 15, 2001
`Date:
`(Parent Matter No.
`252465
`
`)
`
`
`= Hon. Commissioner of Patents
`
`.= Washington. DC 20231
`
`1;:
`;, =
`:5; 1.
`%A
`:24,-
`;._.2
`3.»;
`2;
`f: 1A.
`t“
`(1)
`(2)
`
`'
`
`Sir:
`
`‘
`
`To effect the above-requested filing today:
`
`:
`Attached is a copy (which must be filed) of the prior application, including:
`'
`
`IZ Abstract
`E Specification and claims (9_4 pages) (must be attached)
`:fl Drawings (must be attached if originally filed): fl sheet(s)/set: E] 1 set informal;
`'
`Formal of size
`IZ A4
`A_|v__vays X one box, only:
`IX] Copy of Signed declaration or oath as originally filed in prior application attached
`[3 fl declaration or fee is enclosed; therefore, this is a filing under Rule 53(f).
`
`El 11"
`
`2.
`
`E]
`
`This application is hereby filed by less than all of the inventors named in the prior application. Petition is
`hereby made requesting deletion as inventor(s) of the following who is/are n_c>t inventor(s) of the
`invention being claimed in this application (DELETE THE FOLLOWING |NVENTOR(S)):
`
`1
`3
`5
`7
`
`2-5
`
`THE INVENTOR(S) FOR THIS NEW APPLICATION IS(ARE):
`
`David A. FARBER
`
`1.
`3.
`5.
`7.
`
`2.
`4.
`6.
`8.
`
`2.
`4.
`6.
`8.
`
`Ronald D. LACHMAN
`
`
`
`3.
`
`The entire disclosure of the prior application is considered as being part of the disclosure of the accompanying
`application and is hereby incorporated therein by reference thereto.
`‘l
`\
`
`30238680_1.DOC ‘
`
`"
`
`_
`
`GOOG-1018-Page 1 of 143
`
`PAT-1 na 10/01
`
`GOOG-1018-Page 1 of 143
`
`

`

`.
`
`4.
`
`El
`
`Priority is claimed under 35 U.S.C. 119/365 based on filing in
`'
`'
`Application No.
`
`Filing Date
`
`(country)
`Application No.
`
`
`
`<2)
`(1)
`(3) _______ _____ (4)
`(5) ________ ____'_ (6)
`
`a. [:1 _____4_ (No.) Certified copy/copies attached.
`b. E]
`Certified copy/copies previously filed on
`US. Application No.
`/
`series code 1}
`
`1} serial no.
`
`, filed on
`
`in
`.
`
`4.
`
`Certified copy/copies filed during International stage of PCT/
`c. |:l
`
`/
`(a) |___]
`Domestic priority is claimed from
`,
`PCT/
`
`/
`
`filed
`
`(b) {:1
`
`Benefit is claimed of Provisional Application No.
`
`60/
`
`, filed
`
`5.
`
`IX
`
`Prior application is assigned to
`
`Kinetech, Inc. and Digital Island, Inc. respectively
`
`Page 2 of4
`
`of
`
`,
`
`Filing Date
`
`by assignment recorded
`
`April 1,1995/ October 5, 2000
`(Date)
`Attached is the following number of Assignments (including original and all later successive ones by
`
`different assignors):
`2
`and respective new Cover Sheets. (Do NOT file old cover sheets.)
`
`Reel
`
`9873/11273
`
`Frame
`
`0463/0164.
`
`6.
`
`IX
`
`
`
`(Assignments in parent must be refiled with new Cover Sheets in this continuing application if you
`want it/them recorded against the continuing application.)
`
`Please return the recorded Assignment to the undersigned.
`
`7.
`
`>14
`
`The power of attorney in the prior application is to Dale §, Lazar, Beg, N9, g§,§12
`
`
`
`9.
`
`9.
`
`(Name and Reg. No.)
`whose current address is as in item 8 below.
`
`Recognize as associate attorney Brian Siritzky, Reg. No. 37,497
`a.
`
`
`(Name, Reg. No. and Address)
`
`Address all future communications to Intellectual Property Group
`of Pillsbury Winthrop LLP, 1600 Tysons Boulevard, McLean, VA 22102
`
`Amend the specification by inserting before the first line the sentence:--This is a
`[XI continuation El division
`of Application No.
`09/283,160,
`filed
`series code 1}
`1} serial no.
`which is a continuation of 08/960,079, filed October 24, 1997, now abandoned, which is
`
`a continuation of 08/425,160, filed April 11, 1995, now abandoned.
`
`.--
`
`April 1, 1999
`
`(a) E] Amend the specification by inserting before the first line: --This application claims the benefit of
`Provisional Application No. 60/
`, filed
`.—-
`
`10.
`
`Small Entity Status
`
`is N_ot claimed
`
`E] is claimed
`
`(pre—filing confirmation reguired)
`
`(No.) Small Entity Statement(s) (n_ot essential since 9/8/00) were/are:
`U filed in above prior application
`El attached.
`
`11.
`(m DOX)
`(mu_st be)
`(X'd)
`
`Petition to extend the life of the above prior application flieisuh—egatehiegf
`CI is being concurrently filed in that prior application (Use Form PAT-111).
`C] was previously filed in that prior application (Check length of prior extension).
`(XI is not necessary for copendency (Double check before X'ing this box).
`
`30238680_1.DOC
`
`-
`
`GOOG-1018-Page 2 of 143
`
`DAT-1 “8 10/01
`
`GOOG-1018-Page 2 of 143
`
`

`

`Page 3 of 4
`
`12.
`
`[XI
`
`-
`
`'
`
`‘
`
`INFORMATION DISCLOSURE STATEMENT: Attached is Form PTO-1449 listing all of the documents
`cited by Applicant and the PTO in the parent application(s) relied upon under 35 USC 120 and
`referenced in item 9 above. Per Rule 98(d) copies of those documents are not reguired now. Please
`consider those documents and advise that they have been considered in this new application as by
`returning a copy of the enclosed Form PTO-1449 with the Examiner's initials in the left column per
`MPEP 609. .
`
`13.
`
`|:I
`
`Attached is a Rule 103(a) Petition to Suspend Action.
`
`14. E PRELIMINARY AMENDMENT to be entered before fee calculation: (Do n_ot make amendments here
`except for correction of improper multiple dependencies or cancellation of whole claims or multiple
`dependencies for purpose of reducing the filing fee per MPEP §§ 506 and 607; do n_o_t cancel all claims).
`
`Please cancel claims_1-45 and 50-53.
`
`FILING FEE
`THE FOLLOWING FILING FEE IS BASED ON
`->—>->->CLAIMS AS FILED AND CHANGED BY PRELIMINARY AMENDMENT IN ITEM 14<-<-<-<-
`
`
`NOTE:
`
`If box 1A2 is X’d, do not pay fees,
`but leave lines 15-22 and 27-32 blank.
`
`i
`n
`“I.
`
`"Ilifttill.
`
`
`
`m: PLEASE NOTE CLAIM CANCELLATIONS IF BOX 14 ABOVE IS X’D.
`
`Large/Small
`
`
`if;{til
`Enti
`
`
`
`
`
`
`
`15. Basic Filing Fee .............................. Design Application
`16. Basic Filin- Fee ..............................'Utilit A olication
`
`
`
`
`
`23.
`
`24.
`
`25.
`
`El ATTACHED:
`
`IZI Preliminary Amendment attached (to be entered after assigning Appln. No.)
`
`I: See NONPUBLICATION REQUEST under Rule 213(a) attached (Pat-258)
`
`(carry forward to Item 31)
`
`30238680_1 .DOC
`
`GOOG-1018—Page 3 of 143
`
`PAT-1 08 10/01
`
`GOOG-1018-Page 3 of 143
`
`

`

`26.
`
`-
`
`"
`
`‘
`
`27.
`
`28.
`
`29.
`
`30.
`
`31.
`
`E; 32.
`
`E 33.
`:: 34_
`:5: 35_
`i 1
`
`I
`
`,
`
`Page 4 of4
`
`,
`
`'
`
`ADDITIONAL FEE CALCULATION FOR
`PRELIMINARY AMENDMENT
`PER BOXES 24I25,
`
`_
`
`.
`
`r
`
`Claims
`remaining
`after
`amendment
`
`Highest
`number
`previously
`paid for
`
`Present
`Extra
`
`Additi nal
`Fee
`
`Total Effective Claims
`
`Independent Claims
`
`
`*16
`
`
`*14
`
`minus **
`
`
`20
`=
`0
`
`minus ***
`
`
`3
`=
`11
`
`x
`
`x
`
`$18l$9
`
`$84l$42
`
`=
`
`=
`
`Large/Small Entig
`
`File Code
`
`(103/203)
`
`$ 0
`
`+ 924
`
`(102/202)
`
`if amendment enters proper multiple dependent claim(s) into this application for the
`first time, add (per application) .................................. $280/$140
`
`+ 0
`
`(104/204)
`
`ADDITIONAL FEE
`
`$ 0
`
`pig FEE from item 22 on page 3
`
`TOTAL FEE ATTACHED
`
`+
`
`820
`
`$ 1744
`
`'If the entry in this space is less than a entry in the next space, the “Present Extra" result is ‘0'
`“Itthe “Highest number previously paid for” (see item 17 above) is less than 20, write “20' in this space
`Ifthe ”Highest number previously paid for“ (see item 18 above) is less than 3, write “3' in this space
`
`Our Deposit Account No. 03-3975
`Our Order No.
`007018
`
`C#
`
`0283002
`
`M#
`
` CHARGE STATEMENT: Upon the filing of a Declaration pursuant to Rule 60(b) or 60(d), the Commissioner is hereby
`
`7‘ authorized to charge any fee specifically authorized hereafter, or any missing or insufficient fee(s) filed. or asserted to
`%—= be filed. or which should have been filed herewith or concerning any paper filed hereafter, and which may be required
`under Rules 16—18
`(missing or insufficient fee only) now or hereafter relative to this application and the resulting
`Official document under Rule 20, or credit any overpayment,
`to our Account/Order Nos. shown above for which
`purpose a duplicate copy of this sheet is attached.
`This CHARGE STATEMENT does fl! authorize charge of the issue fit? until/unless an issue fee transmittal
`form is filed.
`
`Pillsbury Winthrop LLP
`Intellectual Prope ‘ Group
`
`1600 Tysons Boulevard
`
`McLean, VA 22102 Tel: (703) 905-2000
`
`BS/BS
`
`Reg. No.
`
`37497
`
`Fax:
`Tel:
`
`(703) 905-2500
`(703) 905-2135
`
`Atty/Sec.
`
`NOTE No. 1: File this Request in duplicate with 2 postcard receipts (PAT-103) & attachments
`NOTE No. 2: Is extension in parent necessary for copendency? DOUBLE CHECK Item 11 above.
`If yes, printout Pat-111 and head it in parent.
`
`30238680_1.DOC
`
`GOOG-1018-Page 4 of 143
`
`PAT-1 08 10/01
`
`GOOG-1018-Page 4 of 143
`
`

`

`APPLICATION UNDER UNITED STATES PATENT LAWS
`PW 283002
`
`Atty. Dkt. No.
`
`(M#)
`
`Invention:
`
`IDENTIFYING DATA IN A DATA PROCESSING SYSTEM
`
`Inventor (s):
`
`David A. FARBER
`Ronald D. LACHMAN
`
`I“I
`iiiIIEEIIII I
`
`
`
`III:III;iii"?III:«III:$7,,
`
`I:
`
`..I?"IIIl
`
`"u:I113;{lift
`
`Pillsbury Winthrop LLP
`Intellectual Property Group
`1600 Tysons Boulevard
`McLean, VA 22102
`
`Attorneys
`Telephone:
`
`(703) 905-2000
`
`This is a:
`
`Provisional Application
`
`Regular Utility Application
`
`Continuing Application
`IZI The contents of the parent are incorporated
`by reference
`
`PCT National Phase Application
`
`Design Application
`
`Reissue Application
`
`Plant Application
`
`Substitute Specification
`Sub. Spec Filed
`in App. No.
`
`/
`
`Marked up Specification re
`Sub. Spec. filed
`. In App. No
`
`/
`
`
`
`DEIDEIDIEDD
`
`El
`
`SPECIFICATION
`
`30238890_1 .DOC
`
`GOOG-1018-Page 5 of 143
`
`PAT~100 a/oo
`
`GOOG-1018-Page 5 of 143
`
`

`

`Sfiéfi
`
`..._
`_.
`L‘
`
`53'2.:w.L
`
`E§s#%%§§%
`
`mow
`
`Now
`
`momwmoomm
`
`Nov
`
`Nev
`
`mommmoomm
`
`mowwmoomm
`
`3:a:
`
`«or
`
`wea
`
`mowwmoomm
`
`mOwwmoomm
`
`vm0<m0hm
`
`woSmD
`
`..353
`
`$555
`
`GOOG-10'18-Page 6 of 143
`
`GOOG-1018-Page 6 of 143
`
`

`

`>mOs_ms_
`
`«2,
`
`m<
`
`g.Qmm“m"my.HawLu.a:a:mm,3Za.
`
`.memmmoomn.
`
`
`
`a....0:
`
`GOOG-1018—Pagé 7 of 143
`
`GOOG-1018-Page 7 of 143
`
`
`
`
`

`

`3.QE"mHmy,Nu.m,”ana,a:“a,mmZa.
`
`a:we".
`
`55%‘N07.
`
`m_._.
`
`.
`
`”Fr“Fr
`
`.
`
`
`
`>m,o._.omm_o.
`
`...5.28%5.98%.
`
`cwr
`
`m.=u_
`
`NNF
`
`
`
`thEOmw.
`
`...m.=n_me".
`
`i
`
`ourcar
`
`«NF.«Ne
`
`
`
`FZMEOmmhszOmw
`
`GOOG-1018—Pagé 8 of 143
`
`GOOG-1018-Page 8 of 143
`
`

`

`
`
`
`.38.
`'
`FIG 3
`—'
`
`
`
`
`
`
`
`
`
`
`
`' Size
`
`
`
`__
`
`
`
`
`
`
`
`
`
`
`FIG. 4
`
`'
`
`
`
`
`
`
`
`
`
`
`
`_
`
`
`
`
`
`‘
`
`.
`
`I42 ,
`
`
`
`
`
`
`
`FIG. 5
`
`
`
`
`
`
`
`
`
`
`GOOG-1018—Page 9 of 143
`
`1F“£13135H!l I
`
`.as:
`I"
`
`"E?"ii?"'3i:Eiii!412;
`“337flE331"ii.
`
`n.
`
`GOOG-1018-Page 9 of 143
`
`

`

`figflfififififla%fi%fifig
`
`o¢_
`
`VS,
`
`
`
`...mafia-flu—Oogom
`
`
`
`nodumooamousom
`
`
`
`‘mawzHmcw.auo
`
`m.0:
`
`l5co«uaum.o
`
`Na:
`
`mi
`
`
`
`mamamane
`
`mamzmane!Hugomomumv
`
`”.9...
`
`I3:
`,Om..
`
`GOOG-1018—Page 10 of 143
`
`GOOG-1018-Page 10 of 143
`
`
`
`
`
`

`

`FIG. now)
`
`simple
`
`DA TA ITEM
`
`""IN{11;:L
`
`‘{sail4:2:153:H2311{Eu[15
`
`
`
`
`
`
`will?it]!ifiii"i137‘IET"i137”’'
`
`-——_-—-—_-—_-__--..-_-__—-~
`
`COMPUTE MD FUNCTION ON
`
`DATA ITEM
`
`’p
`
`~-........-——--————_._.---—._—'
`
`8214
`
`APPEND LENGTH'MODULO 32 OF
`
`DATA ITEM
`
`TRUE NAME
`
`1
`
`GOOG-1018—Page 11 of 143
`
`GOOG-1018-Page 11 of 143
`
`

`

`
`
`$216
`
`YES
`DATA ITEM
`
`SIMPLE?
`
`
`$220
`
`PARTITION DATA ITEM INTO
`
`SEGMENTS
`
`FIG. IOI'b)‘
`
`EMEEMMMMI.I
`
`13[CH{EMIIT‘IIT“IE?I
`
`."l
`
`' ' ' ' 's'21’8"""
`
`COMPUTE TRUE :
`; NAME OF SIMPLE :
`'
`I
`|
`DATA ITEM
`.
`————————————— I
`
`$222 ASSIMILATE EACH SEGMENT
`
`(COMPUTING ITS TRUE NAME)
`
`
`
`3224
`
`CREATE INDIRECT BLOCK OF
`
`SEGMENT TRUE NAMES
`
`8226
`ASSIMILATE INDIRECT BLOCK
`
`(COMPUTING ITS‘TRUE NAME)
`
`8228
`
`ITEM
`
`REPLACE FINAL 32 BITS OF TRUE
`
`NAME WITH LENGHT MOD 32 OF DATA
`
`GOOG-1018—Page '12 of 143
`
`GOOG-1018-Page 12 of 143
`
`

`

`no.we“.w><I
`
`>m._.zwwmoomm>
`
`33.
`
`
`
`n:m..=n_map—b
`
`wmwm
`
`n:MAEmhmfio
`
`Q.5flufifiufiwwaa:aa:Einmm:
`
`ommm
`
`mz__2mm._.mo
`
`mE<zmay:
`
`__.9“.
`
`
`
`
`
`ms_<zmam...wmoo
`
`w.=n_may:2—hum—xm
`
`«him—0mm
`
`mmuw
`
`
`
`
`
`>m._.zm>>mzm._.<mmo.
`
`
`
`
`
`#2300mm:hmw. mangmmzko._.mw..n:mau—mmOHw..—.O...
`
`
`
`
`
`
`
`GOOG-1018—Page 13 of 143
`
`GOOG-1018-Page 13 of 143
`
`
`
`
`
`

`

`
`
`
`
`"113'{[1133131113”ii?313'iii:III}!III:A:Eli3&1£3{E}
`
`
`
`
`
`
`
`FIG. I2
`
`
`
`
`
`
`
`3240
`8238 '
`
`
`UPDATE
`
`
`FILE
`
`
`LOCKED?
`
`DEPENDENCY
`UST
`
` $242
`
`
`
`SEND MESSAGE TO
`CACHE SERVER TO
`
`8244
`UPDATE CACHE
`
`
`COMPRESS
`
` (IF DESIRED)
`
`
`
`
`
`" MIRROR
`
` $246
`(IF DESIRED)
`
`GOOG-1018—Page 14 of 143
`
`GOOG-1018-Page 14 of 143
`
`

`

`
`
`Iii:E21!It:tut”;fl(Ein-lExiL'li!
`
`J37“1i?"’III]
`
`"i“5
`$131.
`
`"I?11:11
`
`8250
`
`
`
`SEARCH FOR
`THE
`
`PATHNAME
`
`FOUND
`
`
`
`FAIL
`
`LDE INCLUDES
`
`
`
`
`TRUE NAME?
`
`
`
`
`
`
`
`
`
`
`ASSIMILATE
`LDE IDENTIFIES
`FILE ID
`DIRECTORY?
`
`
`
`
`
`$258
`
`YS
`
`$256
`
`FREEZE
`
`DIRECTORY
`
`GOOG-1018—Page 15 of 143
`
`GOOG-1018-Page 15 of 143
`
`

`

`CONFIRM THAT
`
`TRUE NAME
`
`EXISTS LOCALLY
`
`
`
`
` $260
`
`
`
`
`
`FIG.I4
`
`
`
`
`3262
`SEARCH FOR
`
`
`PATHNAME IN
`
`LDE TABLE
`
`
`
`:531E}.xii;«a:33’[IE{finIII}!
`"III?HE!Ex"It?If:'15
`
`
`
`
`CONFIRM THAT
`
`DIRECTORY '
`
`
`
`EXISTS
`
` $264
`
`
`
`
` $266
` 8268 '
`
`NAMED FILE
`DELETE
`
`EXISTS?
`TRUE FILE
`
`
`
`
`
`
`$270
`
`
`
`CREATE
`
`
`
`ENTRY IN LDE
`
`
`
`& UPDATE
`
`GOOG-1018—Page 16 of 143
`
`GOOG-1018-Page 16 of 143
`
`

`

`mmZOnwmm
`
`m>Ewom
`
`:Nw
`
`FE02mm
`
`mmZOmmmm
`
`m>_._.<wmz
`
`wm>
`
`
`
` «mammmoom.<22.200.—9.aSQ.me“mm2,,“mymmL.hma;g.Erma.
`
`ommm
`
`PZDOEam0<mwm2hmmzcmm
`mo...—.:<>>
`
` mmzommmmEm
`
`onmw
`
`
`
`MAEmam...awhzm
`
`mnz.
`
`
`
`o._.z_amzmzhmm
`
`~me
`
`
`
`may...tam;
`
`."awe".
`
`69.5%
`
`
`
`w.=u_oz."—
`
`2.10:
`
`GOOG-1018—Page 17 of 143
`
`GOOG-1018-Page 17 of 143
`
`
`
`
`
`
`
`

`

`Sgflfifififiwgfi%%fifig
`
`
`
`£<umemwmoomm
`
`mm>
`
`QMHOMJM
`
`.hzmfio35.0....§
`
`
`
`whm<on<0mmm>tzwm2
`
`vaw
`
`hzmfio
`
`953$
`
`anwmmooE
`
`mmwm
`
`>z<
`
`wwwm
`
`hzmfio
`
`mhzés
`
`.....HJWJ.TII-
`mmzommum
`
`
`
`ms.Rom
`
`mmzomwmm
`
`to.
`
`ks”M§=h
`
`GOOG-1018—Page is of 143
`
`GOOG-1018-Page 18 of 143
`
`
`
`
`
`
`
`

`

`.E\/Ew>m
`
`.5...ch22oz<mowmmoomm
`
`momaowzo
`
`
`
`QQ:23“a3mm:m“wig:a,Ewan”:.
`
`
`
`
`
`max..."—0mom—30m
`
`
`
`20m".mmmuu—EmE<z
`
`m20F<szmo
`
`momwm
`
`mo".mm...n5x00.—
`
`
`
`oo<ams_<zmam...
`
`
`
`n:zo_._.<oo._MOM—Dom
`
`«anwemoxzowO,._.
`
`
`
`w_2<zmam...
`
`omwm
`
`E05
`
`a.«8809:.
`
`
`
`36..o:
`
`0Sum
`
`
`Sam08%
`
`-2.$5meozmw
`
`
`
`mfifluflwfififi«91Awfiflwflm3:may:m>mmmmm
`
`GOOG-1018—Page 19 of 143
`
`GOOG-1018-Page 19 of 143
`
`
`
`
`
`
`

`

`
`
`mamamm>mama
`
`mmmmmsoomo
`
`ommmmmmioo
`
`no.m.=n_
`
`mm>
`
`4mo”.9we".
`
`95%25
`
`oz
`
`
`
`3a“Q“flux”Himmmwaa:gr.$me3Q,
`
`.__<.._
`
`,oz
`
`«mum
`
`>mhzmm.=u_m:.
`
`mam...mo“.mu...2.
`
`$522
`
`E:.9“.
`
`GOOG-1018—Page 20 of 143
`
`GOOG-1018-Page 20 of 143
`
`
`
`
`
`

`

`BE.9“.
`
`O
`
`comm
`
`o_mmOkw
`
`Nomw
`
`>Ehoz
`
`mum:
`
`
`
`‘.howdmm
`
`mo_mom30m
`
`vomm
`
`comm
`
`
`
`ms”:mugfim
`
`20Em.__u_
`
`Emomaow
`
`33§§%%%§5%%%§§%
`
`womw
`
`wh<004
`
`mammkosmm
`
`GOOG-1018—Page 21 of 143
`
`GOOG-1018-Page 21 of 143
`
`
`
`
`
`

`

`
`
`3a.QwmyEE.wa...hm,hm“.M“:Za;
`
`mm:
`
`mo".0.m.=u_
`
`3...".max...
`
`mmmm
`
`
`
`mDE.$.32
`
`
`
`.260...m..."—
`
`$47.
`
`was.no>moomm
`
`3mm
`
`mam-En
`
`
`
`wan.mam...
`
`
`
`mmr—Fzmo.mo.—
`
`
`
`mam...ozFflxm
`
`«mg—n.
`
`oumw
`
`
`
`Emzmhfimo
`
`
`
`w.=n_:o._.<mom
`
`GOOG-1018—Page 22 of 143
`
`GOOG-1018-Page 22 of 143
`
`
`
`
`
`

`

`QQE””.3"my.my.mm.mmaup.9..g:E5up.
`
`
`Mmhm>02mm
`
`.m4m<hmogz_an:m.=n_m><wa.MAEmmOhm£4."—
`
`
`
`>mhzmmmnhzwfimmomo
`
`
`
`mmmw>>m2o._.MAE>moo
`
`88
`
`b.2300
`
`mm;0
`
`BE.0:
`
`GOOG-1018—Page 23 of 143
`
`GOOG-1018-Page 23 of 143
`
`
`
`

`

`
`
`E5552memwizamomsm
`835%mo".
`we".a:2_5.98%
`
`
`
`8535522:fiwwflfi.oz<5.".‘
`
`ESQfinafifiuflaaawfmwfig:
`
`..l5:::-
`
`32a:
`
`«mmw
`
`hszmmoE
`
`
`
`x00...MNmmmn—
`
`
`
`>mo._.omm_ozw>_0
`
`Nmmw
`
`
`
`gmzwhfimo
`
`
`
`Emt<._.<o
`
`GOOG-1018—Page 24 of 143
`
`GOOG-1018-Page 24 of 143
`
`
`
`

`

`ovmm
`
`zo_._.<_2mou_z_
`
`._<zoE8<2EtaRE28%..
`
`omEmmo.<._.<o262
`
`2:2.9“.
`
`wmmw
`
`2m:
`
`3“”QQ”m..__J.3.5...._....:5:
`
`....fl...a:m......
`53wx...”r:
`
`:o<mmo".
`
`m._.<z_omom:w
`
`nz<m.=u_
`
`ME.2.>mo._.om~=o
`
`
`
`5.55.0mezw>_0
`
`Nvmw
`
`m5E5552
`
`smE<5652
`
`vvmm
`
`hzmfimmowo
`
`mmmEmE
`
`xoOA.
`
`GOOG-1018—Page 25 of 143
`
`GOOG-1018-Page 25 of 143
`
`
`
`
`
`
`

`

`
`
`
`
`0...I._.<n_v.2...
`
`ms_<zmay;
`
`38
`
`9mm
`
`>m0hom~=o
`
`ommw
`
`
`
`4.5".m._.<mmo
`
`ms_<z:._.<n_
`
`Nmmm
`
`”Q5m“.fl:"EMmm...“aEw“3..g.hm:5E“s,
`
`9.8
`
`mamhmx<z
`
`4<ooJm43
`
`38
`
`:05mo".
`
`>mo._.omm_n
`
`>m._.zm
`
`mac—zOz
`
`mm_m._.zm
`
`cm.oE
`
`GOOG-1018—Page 26 of 143
`
`GOOG-1018-Page 26 of 143
`
`
`
`
`
`
`

`

`
`
`If:3:8Eiii"i13"1131E"133}:RE?£1?«£1EB{£3334ffiiuI’ll
`
`
` S354
`
`WAIT FOR
`
`
`
`FREEZE LOCK
`
`TO TURN OFF
`
`
`ENTRY
`
` S356
`
`FIND TFR
`
`FIG.2|
`
`$358
`DECREMENT
`
`REFERENCE
`
`
`
`
`
`
`
`
`COUNT
`
`
`
`
`
` v 8362
`
`REFERENCE COUNT IS
`
`
`DELETE
`ZERO & NO DEPENDENT
`
`
`TRUE FILE
`
`
`
`SYSTEMS IN TFR?
`
`
`
`
`
`S364
`
`
`
`
`
`AND COMPRESSED
`
`FILE ID
`
`
`
`REMOVE FILE ID .
`
`
`
`-‘..____...____._____—_.—-——«--
`
`GOOG-1018—Page 27 of 143
`
`GOOG-1018-Page 27 of 143
`
`

`

`
`
`
`GET
`
`:
`
`S365
`
`
`
`OPERATION
`
`
`S366
`
`
`
`CREATEOR
`
`mommn
`
`COMPOUND?
`
`YES
`
`
`YES
`
`
` COPY OR DELETE
`
`
`“fiflflmfl
`
`IF'
`IE“:4‘“
`,m
`
`gEME
`
`"1123'“If
`[in
`
`WW
`
`FIG. 22
`
`$368
`
`ASSIMILATE
`
`FmE
`
`S369 --
`
`NENTRUE
`
`S378
`
`MODIFY USE "
`
`COUNT OF EACH
`
`COMPONENT
`
`
`
`S370
`
`RECORD TRUE
`
`NAME IN AUDIT
`
`FILE '
`
`I
`
`8379
`
`FOR EACH PARENT
`
`DIRECTORY OR FILE,
`UPDATE USE COUNT,
`LAST ACCESS AND
`
`MODIFY TIMES
`
`GOOG-1018—Page 28 of 143
`
`GOOG-1018-Page 28 of 143
`
`

`

`is
`l
`r‘‘
`
`m“
`
`:21gr"{m
`
`
`eel:5:255333!IE1!Iw
`
`
`5133'8:31155"Ill?“HI”???"51335.1;
`
`
` $382
`
`VERIFY
`
`
`
`GROOMING
`
`LOCK OFF
`
`
`
`
`
`S384
`SET
`
`GROOMING
`
`
`
`
`LOCK
`
`
`8386
`SET GROOM
`
`
`
`COUNTS
`
`GOOG-1018—Page 29 of 143
`
`GOOG-1018-Page 29 of 143
`
`

`

`
`FIND LDE
`
`RECORD
`
`
`
`
`FIG. 24
`
` S388
`
`RECORD
`
`1.it“E
`
`13%a:£3;1133511333111351:{EH
`
`
`
`wwfifirwm
`
` S390
`
`
`FIND TFR
`
` S392
`
`
`
`INCREMENT
`
`GROOMING
`
`DELETE COUNT
`
`
`
`
`$394
`
`
`
`ADJUST FILE
`
`SIZES
`
`
`
`GOOG-1018—Page 30 of 143
`
`GOOG-1018-Page 30 of 143
`
`

`

`afiwwmm
`
`«4
`“I".
`
`'32“''31
`iinu1"Wu“
`1K”UE
`“‘1«a:|w
`
`$1
`
`*=
`
`FIG. 25
`
`
`
`GROOMING
`
`$398
`
`UNLOCK
`
`LOCK
`
`GOOG-1018—Page 31 of 143
`
`GOOG-1018-Page 31 of 143
`
`

`

`mum.Q5W".mmmMmH4WW5Bum
`
`%%%fi§%
`
`«>420o...
`
`9553m..."—
`
`movm
`
`szEmEo
`
`20—03.
`
`vovw
`
`._._m_:omm
`
`zmmo
`
`Nova
`
`”oz—mm
`
`«omhkmmo
`
`2:5
`
`Io._.<mow
`
`«MAE.
`
`mwvw
`
`tmfomm
`
`zmmo
`
`mm>
`
`>._zo.o<mm
`
`GOOG-1018—Page 32 of 143
`
`GOOG-1018-Page 32 of 143
`
`
`
`
`
`
`
`
`
`

`

`
`
`._<oo.._mv._<_2
`
`
`.a":
`
` so”:9m4:zmamma206mm;
`
`owvm.
`
`5...,1:-_
`
`23§§%%E¥E%%%fi§%
`
`mwvw
`
`.Fozn:v.00.—
`
`05.00..—
`
`m._.<mmoN2%
`
`Ioonm
`
`>moo
`
`2:0de
`
`w..=..._
`
`«Our—9‘0
`
`mwwm
`
`02mm
`
`>._m._.m._n=zoo
`
`zm._.._._m>>m.
`
`vmvw
`
`zmahmm
`
`n:
`
`
`
`m.=n_:o._.<m0w
`
`
`
`w..=n_mmém
`
`85.
`
`m._.<mm0
`
`
`
`m.=u_:o._.<mom
`
`GOOG-1018—Page 33 of 143 ,
`
`GOOG-1018-Page 33 of 143
`
`
`
`
`
`
`
`
`
`

`

`3figQ"mm
`
`it“.5.2.".aid:
`_~...ra.a.mu...
`
`wa%%%§§%
`
`._._m=._omm
`
`zoFmfio
`
`ER.0:
`
`vaw
`
`
`
` >m._.zmkmama...wEEmWfio
`
`_mou—mom—00mm
`
`.m.=m
`
`.Oomoommmo.—0..
`
`
`
`2.mo$550...w..."—
`
`Ezoéfim
`
`«55.5%.;—
`
`vmvw
`
`
`
`mnE.>n=hzm2
`
`
`
`
`
`mam...20m”.m..."—
`
`mE<z
`
`GOOG-1018—Page 34 of 143
`
`GOOG-1018-Page 34 of 143
`
`
`
`
`

`

`
`
`
`
`E=meQME“”Nu.Hmm”m“wa.Erma“mu.,9:
`
`nwvm
`
`ukwgmo
`
`m..=u_mo
`
`
`
`>moo10.530”
`
`wmvm
`
`
`
`O._.>m._.zmno<
`
`
`
`w.=u_:92
`
`omvw
`
`mhwjmo
`
`MAEmam...
`
`rmvw
`
`
`
`mm:museum
`
`ES35:8
`
`mm;
`
`w.m..__n_may:
`
`
`
`m.#2300mm:
`
`$522may:
`
`
`
`02oz91..m3."—
`
`.m;
`
`GOOG-1018—Page 35 of 143
`
`GOOG-1018-Page 35 of 143
`
`
`
`
`
`
`

`

`|\
`
`mm.9“.
`
`35
`
`".363
`
`_
`
`msizmat
`
`ozwm>
`
`vmvw
`
`«0230....
`
`:2.E,
`
`1:::JJ,_..::..¢..E;.5,.nz=asE....
`
`
`
`.~....;”:swig......a»J5.1w:5::L“.mu.i.5.=5.
`
`vaw
`
`
`
`
`
`mewMMms—OoMOmmo._.hwm30mm0535.0".a.MAEmun—3.52
`
`
`
`~bmnx<>>m0uhwmsamm,
`
`
`mmvw
`
`m>_._.<0mz
`
`waOmmmm
`
`vvvw
`
`mmZOmwmm
`
`
`
`HEP—won..
`
`GOOG-1018—Page 36 of 143
`
`
`
`«a.m..."—
`
`GOOG-1018-Page 36 of 143
`
`
`
`

`

`7018/213987
`
` \
`
`535-“
`
`BACKGROUND OF THE INVENTION
`
`1.
`
`Field of the invention
`
`This invention relates to data processing
`
`systems and, more particularly,
`
`to data processing.
`
`systems wherein data items are identified by
`
`substantially unique identifiers which depend on all of
`
`the data in the data items and only on the data in the
`
`data items.
`
`10
`
`2.
`
`Background of the Invention
`
`15
`
`20
`
`25
`
`30
`
`Data processing (DP) systems, computers,
`
`networks of computers, or the like,
`
`typically offer users
`
`and programs various ways to identify the data in the
`
`systems.
`
`‘
`
`Users typically identify data in the data
`
`processing.system by giving the data some form of name.
`
`For example, a typical operating system (OS) on a
`
`computer provides a file system in which data items are
`
`named by alphanumeric identifiers.
`
`Programs typically
`
`identify data in the data processing system using a
`location or address.
`For example, a program may identify
`
`a record in a file or database by using a record number
`
`which serves to locate that record.
`
`In all but the most primitive operating
`
`systems, users and programs are able to create and use
`
`collections of named data items,
`
`themselves being named by identifiers.
`
`these collections
`These named
`
`collections can then,
`
`themselves,
`
`be made part of other
`
`named collections.
`
`For example, an_OS may provide
`
`mechanisms to group files (data items)
`
`into directories
`
`themselves be
`(collections). These directories can then,
`made part of other directories.
`A data item may thus be
`
`identified relative to these nested directories using a
`
`GOOG-1018—Page 37 of 143
`
`
`
`
`
`"332‘13:313333."Hi7"33:"33'“‘3333333'31'3133:Eli33in£13.51:ij
`
`
`
`
`
`
`
`GOOG-1018-Page 37 of 143
`
`

`

`‘
`
`w
`
`ufimfl
`'fiflfiim
`
`*r.
`:5.
`as;
`
`wwmwrwwafi
`
`sequence of names, or a so-called pathname, which defines
`
`a path through the directories to a particular data item
`
`(file or directory).
`
`As another example, a database management
`
`system may group data records (data items)
`
`into tables
`
`and then group these tables into database files
`
`(collections).
`
`The complete address of any data record
`
`the
`can then be specified using the database file name,
`table name, and the record number of that data record.
`
`other examples of identifying data items
`
`include:
`
`identifying files in a network file system,
`
`identifying objects in an object-oriented database,
`
`identifying images in an image database, and identifying
`
`articles in a text database.
`
`In general,
`
`the terms "data" and "data item" as
`
`used herein refer to sequences of bits.
`
`Thus a data item
`
`may be the contents of a file, a portion of a file, a
`
`page in memory, an object in an object-oriented program,
`
`10
`
`15
`
`20
`
`a digital message, a digital scanned image, a part of a
`video or audio signal, or any other entity which can be
`
`represented by a sequence of bits.
`
`The term "data
`
`processing" herein refers to the processing of data
`
`items, and is sometimes dependent on the type of data
`
`item being processed.
`
`For example, a data processor for
`
`a digital image may differ from a data processor for an
`
`audio signal.
`
`In all of the prior data processing systems the
`
`names or identifiers provided to identify data items (the
`
`data items being files, directories, records in the
`
`database, objects in object-oriented programming,
`locations in memory or on a physical device, or the like)
`are always defined relative to a specific context.
`For
`
`instance,
`
`the file identified by a particular file name
`
`can only be determined when the directory containing the
`
`file (the context)
`
`is known.
`
`The file identified by a
`
`pathname can be determined only when the file system
`
`(context)
`
`is known. Similarly,
`
`the addresses in a
`
`25
`
`30
`
`35
`
`GOOG-1018—Page 38 of 143
`
`GOOG-1018-Page 38 of 143
`
`

`

`r‘\
`
`
`
`
`
`process address space,
`
`the keys in a database table, or
`
`domain names on a global computer network such as the
`
`Internet are meaningful only because they are specified
`
`relative to a context.
`
`In prior art systems for identifying data items
`there is no direct relationship between the data names
`
`and the data item.
`The same data name in two different
`I
`contexts may refer to different data items, and two
`different data names in the same context may refer to the
`same data item.
`
`In addition, because there is no correlation
`
`between a data name and the data it refers to,
`
`there is
`
`no a priori way to confirm that a given data item is in
`
`fact the one named by a data name.. For instance,
`
`in a DP
`
`system, if one processor requests that another processor
`deliver a data item with a given data name,
`the}
`
`requesting processor cannot,
`
`in general, verify that the
`
`data delivered is the correct data (given only the name).
`
`10
`
`15
`
`Therefore it may require further processing,
`
`typically on
`
`20‘
`
`the part of the requestor,
`
`to verify that the data item
`
`it has obtained is,
`
`in fact,
`
`the item it requested.
`
`25
`
`30
`
`35
`
`A common operation in a DP system is adding a
`
`new data item to the system. When a new data item is
`added to the system, a name can be assigned to it only by
`updating the context in which names are defined. Thus
`such systems require a centralized mechanism for the
`
`management of names.
`
`Such a mechanism is required even
`
`in a multi-processing system when data items are created
`and identified at separate processors in distinct
`locations, and in which there is no other need for
`
`communication when data items are added.
`
`In many data processing systems or
`environments, data items are transferred between
`
`different locations in the system. These locations may
`be processors in the data processing system, storage
`
`devices, memory, or the like.
`
`For example, one processor
`
`may obtain a data item from another processor or from an
`
`GOOG-1018—Page 39 of 143
`
`GOOG-1018-Page 39 of 143
`
`

`

`external storage device, such as a floppy disk, and may
`
`incorporate that data item into its system (using the
`
`name provided with that data item).
`
`However, when a processor (or some location)
`
`obtains a data item from another location in the DP
`
`system, it is possible that this obtained data item is
`
`already present in the system (either at the location of
`
`the processor or at some other location accessible by the
`processor) and therefore a duplicate of the data item is
`created. This situation is common in a network data
`
`processing environment where proprietary software
`
`products are installed from floppy disks onto several
`
`processors sharing a common file server.
`
`In these
`
`systems, it is often the case that the same product will
`
`be installed on several systems, so that several copies
`
`of each file will reside on the common file server.
`
`In some data processing systems in which
`several processors are connected in‘a network, one system
`is designated as a cache server to maintain master copies
`
`of data items, and other systems are designated as cache
`clients to copy local copies of the master data items
`
`into a local cache on an as-needed basis. Before using a
`
`cached item, a cache client must either reload the cached
`
`item, be informed of changes to the cached item, or
`
`confirm that the master item corresponding to the cached
`
`item has not changed.
`
`In other words, a cache client
`
`must synchronize its data items with those on the_cache
`server. This synchronization may involve reloading data
`
`items onto the cache client. The need to keep the cache
`
`synchronized or reload it adds significant overhead to
`
`existing caching mechanisms.
`
`’
`
`In view of the above and other problems with
`
`prior art systems, it is therefore desirable to have a
`
`mechanism which allows each processor in a multiprocessor
`
`system to determine a cemmon and substantially unique
`
`identifier for a data item, using only the data in the
`
`data item and not_relying on any sort of context.
`
`4
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`GOOG-1018—Page 40 of 143
`
`amwu
`
`ii
`a:u
`...
`,rII1"dim.d!“
`m.,3! w.
`ll...“k.
`II“n.
`nau-m ‘u
`
`nW
`
`MHW.
`
`“2‘...
`
`GOOG-1018-Page 40 of 143
`
`

`

`It is further desirable to have a mechanism for
`
`reducing multiple copies of data items in a data
`
`processing system and to have a mechanism which enables
`
`the identification of identical data items so as to
`
`It is further desirable to
`reduce multiple copies.
`determine whether two instances of a data item are in
`
`fact the same data item, and to perform various other
`systems’ functions and applications on data items without
`
`relying on any context information‘or properties of the
`
`10
`
`data item.
`
`It is also desirable to provide such a
`
`mechanism in such a way as to make it transparent to
`
`users of the data processing system, and it is desirable
`
`that a single mechanism be used to address each of the
`
`15
`
`problems described above.
`
`SUMMAR! Of IEE INVENEION
`This invention provides,
`in a data processing
`
`system, a method and apparatus for identifying a data
`item in the system, where the identity of the data item
`depends on all of the data in the data item and only on
`
`the data in the data item.
`Thus the identity of a data
`item is independent of its name, origin,
`location,
`address, or other information not derivable directly from
`
`the data, and depends only on the data itself.
`
`This invention further provides an apparatus
`
`and a method for determining whether a particular data
`
`item is present in the system or at a location in the
`
`system, by examining only the data identities of a
`
`plurality of data items.
`
`invention,
`
`Using the method or apparatus of_the present
`the efficiency and integrity of a data
`
`processing system can be improved.
`
`The present invention
`
`improves the design and operation of a data storage
`
`system, file system, relational database, object-oriented
`
`database, or the like that stores a plurality of data
`items, by making possible or improving the design and
`
`20
`
`25
`
`30
`
`35
`
`y
`
`kaEMfl
`
`A"‘
`\“u«am
`1",?
`
`m":31\1
`m.
`
`Wflflwwwmt
`
`GOOG-1018—Page 41 of 143
`
`GOOG-1018-Page 41 of 143
`
`

`

`operation of at least some or all of the following
`
`features:
`
`the system stores at most one copy of any data
`
`item at a given location, even when multiple data names
`
`in the system refer to the same contents;
`
`the system avoids copying data from source to
`
`destination locations when the destination locations
`
`already have the data;
`
`the system provides transparent access to any
`
`10
`
`data item by reference only to its identity and
`independent of its present location, whether it be local,
`
`remote, or offline;
`the system caches data items from a server, so
`
`that only the most recently accessed data items need be
`
`15
`
`retained;
`
`when the system is being used to cache data
`
`items, problems of maintaining cache consistency are
`
`avoided;
`
`the system maintains a desired level of
`redundancy of data items in a network of servers,
`
`to
`
`protect against failure by ensuring that multiple copies
`
`of the data items are present at different locations in
`
`the system;
`
`the system automatically archives data items as
`
`they are created or modified;
`
`the system provides the size, age, and location
`
`of groups of data items in order to decide whether they
`
`can be safely removed from a local file system;
`
`the system can efficiently record and preserve
`any collection of data items;
`
`the system,can efficiently make a copy of any
`
`collection of data items,
`
`to support a version control
`
`mechanism for groups of the data items;
`
`the system can publish data items, allowing
`
`other, possibly anonymous, systems in a network to gain
`
`access to the data items and to rely on the availability
`
`of the data items;
`
`20
`
`25
`
`30
`
`35
`
`H(x
`KI1
`3I(
`
`HEM
`'H’51
`mUna“4%
`
`“mmnmm..m“.wa,“I“Hm“
`WMHEW
`
`GOOG-1018—Page 42 of 143
`
`GOOG-1018-Page 42 of 143
`
`

`

`the system can maintain a local inventory of
`
`all th data items located on a given removable medium,
`
`such as a diskette or CD—ROM,
`
`the inventory is
`
`independent of other properties of the data items such as
`
`their name,
`
`location, and date of creation;
`
`the system allows closely related sets of data
`
`items, such as matching or corresponding directories on
`
`disconnected computers,
`
`to be periodically resynchronized
`
`with one another;
`
`V
`
`the system can verify that data retrieved from
`
`another location is the desired or requested data, using
`
`only the data identifier used to retrieve the data;
`
`the system can prove poSsession of specific
`
`data items by content without disclosing the content of
`
`the data items, for purposes of later legal verification
`
`and to provide anonymity;
`
`the system tracks possession of specific data
`
`items according to content by owner,
`
`independent of the
`
`name, date, or other properties of the data item, and
`
`tracks the uses of specific data items and files by
`
`content for accounting purposes.
`
`other objects, features, and characteristics of
`
`the present invention as well as the methods of operation
`
`and functions of the related elements of structure, and
`
`the combination of parts and economies of manufacture,
`
`will become more apparent upon consideration of the
`following description and the appended claims with
`
`reference to the accompanying drawings, all of which form
`
`a part of this specification.
`
`E C
`
`ON 0
`;
`
`THE DRAWINGS
`
`FIGURE 1 depicts a typical data processing
`
`system in which a preferred embodiment of the present
`
`invention operates;
`
`FIGURE 2 depicts a hierarchy of data items
`
`stored at any lo