PATENT NUMBER
`
`641 5280
`
`z9 '
`
`5Et
`
`oto
`5U
`Lu
`Dto
`
`‘B O.|.P E.
`
`PATENT DATE
`,’
`
`
` }seamen __ \"
`u.A.'
`
`__
` EXAMINER
`
`' SECTOR
`
`SU BCLASS
`
`1 /i *
`
`‘ FiLED WITH:
`
`|:]isK(cRI=) DFICHE
`(Attached in pocket on right inside flap)
`
`
`
`PREPARED AND APPROVED FOR ISSUE
`
`‘J
`
`ISSUIG CLASSIFlCA11O
`
`TEI
`DISCLAIMER
`
`H
`
`CLAIMS ALOWD A
`Total laims
`
`J
`
`:
`U a) The term of this patent
`subsequent to
`__ (date) .
`has been disciaimed.
`~:
`
`.
`
`W b) The term of this patent shall
`ot extend beyond the gxpiratiorj dat
`of us Patent. rw.§)_._
`
`(Assistant Examiner)
`
`JEAN R. HOMERE
`PRIMARY EXAMINER
`
`Jam
`
`E] c) The tenninal ____months of
`this patent have been disclaimed.
`
`=' T;'.r.~ information disclosed herein may be restricted. Unauthorized disclosure may be prohibited by the United States Code Title 35. Sections 122, 181 and 368.
`-, Possession outside the U.S. Patent at Trademark Office is restricted to authorized employees and contractors only.
`Form PTO-436A
`(Rev. 6/98)
`
`‘
`
`i‘«se:1m“‘F%
`(LABEL AREA)
`
`keme:
`
`.
`
`N‘
`k
`
`/‘ x
`
`(F
`
`‘
`
`V‘
`
`I
`
`A J‘ am
`
`,F;,»{
`GOOG 1002 3‘; E
`’ : _1kof
`H;
`
`
`
`
`
`
`
`
`
`
`
`
`

`
`
`
`
`
`
`
`
`
`GOOG-1002
`
`

`
`
`
`
`
`‘
`
`“
`
`,
`J
`N
`K i \
`
`,;79,/2%.? 50
`_-
`,
`'
`PATENT APPLiCAT|_0N ‘EV,/*/fit/7[«)1.r,,iz2;;,*;:,,W,
`mmxuulxmmmm\\sm\\\mmum
`« 3.4/31/i“”””W
`0928316121
`.
`.
`-
`v
`CONTENTS
`3::?.'§f:1';i3
`'
`
`‘3
`
` Date received
`(Incl. C. of M.)
`or
`Date Mailed
`
`
`
`
`
`__
`
`GCOG-1002
`Page 2 of 351
`
`
`
`
`
`
`
`
`
`
`
`
`

`
`
`
`
`
`
`
`
`
`,.;f TWS‘
`.3.
`-
`.)7_\,2~__W 6
`.54. y‘.93 V
`
`’ ‘
`
`4 or 39
`L
`0| _
`3'U_«3~’i3\
`
`1:.
`44.
`45.
`
`'13s 50
`
`53o.“ _1D_~;7;"‘_(
`11.
`u42g;.AmcbE ID
`'
`L01
`lo!
`12. Cbmmmg Csiwcgtgszm
`LQIIQIQI
`‘
`/54510!
`Mgr
`H.
`..
`.
`cLx-._zmL’C.
`.
`3
`fin
`4
`H}? O!
`m
`Di. gommumu»
`K"
`r
`.
`H1? 0/
`rmrm,a,/ ‘
`\DVV~31,~JIrg)
`,1/[1Y~
`(‘.36 /Iféuri
`‘ 1'
`J.%[1.L[,Q\
`‘ MC'Z
`
`51.
`52.
`53.
`54.
`55.
`5s.
`57.
`5a.
`59.
`so.
`
`-
`
`' ‘ A
`
`1&5
`
`‘
`
`‘Ia’-{5_
`
`_
`
`’fi’f_
`
`20.
`
`21.
`
`22.
`
`23.
`
`24.
`
`25.
`
`26.
`
`27.
`
`23.
`
`29.
`
`30.
`
`31.
`
`32.
`
`33.
`
`_
`
`'
`
`61.
`
`52.
`
`63.
`
`54.
`
`65.
`
`as.
`
`67.
`
`ea.
`
`B9.
`
`7o.
`
`71.
`
`72.
`
`73.
`
`74.
`
`75.
`
`76..
`
`77.
`
`7a.
`79.
`so.
`
`51.
`82.
`
`__
`
`(LEFT OUTSIDE)
`
`34.’
`
`V 35.___
`
`3s._
`
`37.
`3a.
`39.
`
`.
`‘
`
`%~..“4o.____
`-
`
`H
`
`_
`
`’
`
`GOOG-1002
`
`

`
`ISSUE SLIP STAPLE A1‘ 3 (fcsr r-Mitional cross references)
`
`POSITION
`
`TmKE
`
`F‘...-
`
`
`
`N
`
`0Wmmm
`
`
`SMCFOXEDIN.
`Rejected
`= Allowed
`_ (Through numeral)... Canceled
`Restricted
`
`Non-elected
`Interference
`Appeal
`Objected
`
`33
`an:
`III
`!II
`
`III
`
`II
`
`
`r:>iflnflfiflfi
`YaEQEEFEQ
`IJIIIIII
`KIIIIIIIHIIIIII
`Em
`
`fififi
`
`‘
`
`nnmnn
`mmmmw
`nnnm
`wmnm
`@E%
`
`DHHBHHHH
`nanan
`..O.B.IRE
`
`3.38
`
`If more than 150 claims or 10 actions
`staple additional sheet here
`
`(LEFT INSIDE)
`
`GOOG-1002
`Page 3 of 351
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`GOOG-1002
`
`
`
`
`
`
`
`
`
`
`
`
`

`
`
`
`GQOGT1002 »
`‘Page"4bf351
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` SEARCH NOTES
`
`(INCLUDING SEARCH STRATEGY)
`
`
`
`
`
`
`
` %@
`
`
`
`I
`N
`
`"
`
`~
`
`
`_‘
`
`7
`~
`
`——
`
`T»
`
`(RIGHT OUTSIDE)
`—
`—
`
`GOOG-1002
`
`

`
`
`
`Page 1 of 1
`
` mm;M‘ -“
`
`UNITED STATES PATENT AND TRADEMARK Oman:
`
`_______*
`COMMISSIONER FOR :“um:r:
`UNITED STATES PATENT AND TRADEMARK OFFICE
`‘NASHINGTON. D.C. 2023|
`wwv/.uspIo.gov
`
`
`
`
`
`coNI=|RMA'rIoN N0. 9574
`IIIIIIIIIIIIIIIIIII|||I||lI||IIIIIIIIIIIIIIIIIIIIIIIIIIII
`Blb Data Sheet
`
`
`FILING DATE
`ATTORNEY
`GROUP ART UNIT .
`SERIAL NUMBER
`DOCKET NO.
`04/01/1999
`
`2177
`09/283,160
`PM252465
`RULE
`
`- PLICANTS
`DAVID A. FARBER, OJAI, CA;
`RONALD D. LACHMAN, NORTHBROOK, IL;
` Io-MA-<k*ir*
`
`* CONTINUING DATA
`
`* FOREIGN APPLICATIONS ********************
`
`
`
`IF REQUIRED, FOREIGN FILING LICENSE
`GRANTED ** 0421/1999
`
`** SMALL ENTWY **
`
`
`
`
`ma‘
`AIIo\ȴ::ce .
`
`‘
`A
`
`I
`Examiner's Sinaturs
`ials
`_
`.9
`‘
`_
`
`cugms
`__
`
`
`
`_V
`
`
`
`
`PILLSBURY MADISON & SUTRO
`INTELLECTUAL PROPERTY GROUP
`1100 NEW YOUK AVENUE NW
`NINTH FLOOR EAST TOWER
`NASHINGTON ,DC 200053918
`ITLE
`IDENTIFYING DATA REQUESTING DATA IN NETWORK USING IDENTIFIERS WHICH ARE BASED ON
`CONTENTS OF DTA
`“
`
`
`
`
`
`C1 All Fees __
`
`
`FILING FEE FEES: Authority has been given in Paper
`RECEIVED No.
`to charge/credit DEPOSIT ACCOUNT
`for followlng:
`
`ees (
`[D 1.18
`Issue)
`'>:her_:__:_;]
`El
`.
`
`
`
`
`_
`I:I1.16F5as(Finng)
`D 1.17 Fees ( Processing Ex: of—I_I
`
`I
`
`I
`
`GOOG-1002
`Page 5 of 351
`
`)
`
`*
`
`+
`
`,
`
`-
`
`.
`
`/
`
`0
`
`-
`
`&
`
`GOOG-1002
`
`

`
`PATENT APPLICATION SERIAL NO.
`
`U.S. DEPARTMENT OF COMMERCE
`PATENT AND TRADEMARK OFFICE
`FEE RECORD SHEET
`
`~\
`
`-V.”
`
`)4/12/1999 RHAYES
`>1 Fc:ao1
`
`00000010 09283160
`350.00 or
`
`M
`
`4’
`
`I
`
`» k
`
`«
`‘\3'3.‘ff
`
`PTO-1556
`
`(5/87)
`'U.S. GPO: 1993-433-214/B0404
`
`6
`
`GOOG-1002
`Page 6 of 351
`
`.
`
`/
`
`0
`
`-
`
`&
`
`)
`
`*
`
`+
`
`,
`
`1
`
`GOOG-1002
`
`

`
`Page 1 of 4
`
`FOR ClPs)
`
`
`
`Group Art Unit:
`
`2776
`
`Examiner:
`
`Homere, J.
`
`FARBER et al.
`inventor(s):
`Parent Appln. No.2
`
`PM 252465
`08
`_NL,M#
`series Code 1)
`(Our Deposit Account No. 03-3975
`October 24, 1997
`Parent Filed:
`(Our Order No.
`7018/252465
`April
`, 1999
`This Case Filed:
`Title:
`IDENTIFYING DATA IN A DATA PROCESSING SYSTEM
`C# I New M#
`
`960,079
`1) serial No.
`
`Atty. Dkt.
`
`cue": Ref
`
`Asst. Commissioner of Patents
`
`Washington, DC 20231
`Sir:
`
`Date:
`
`April 1, 1999
`
`1
`'
`
`(Parent Matter No.
`
`243063
`
`)
`
`To effect the above-requested filing today:
`
`1.
`
`Attached is a copy (which must be filed) of this application, including:
`
`X Abstract
`E Specification and claims (95 pages) (mfit be attached)
`E Drawings (must be attached If orlglnally flied): .2_4_ sheet(s)/set: El 1 set informal;
`[] Formal of size
`[:1 A4
`
`Always X one box, only:
`IX 5_ign_e_d declaration or oath as originally filed in prior application attached
`[:1 NQ declaration or fee is enclosed; therefore, this is a filing under Rule 53(f).
`
`1A.
`(1)
`(2)
`
`El 11'‘
`
`2.
`
`[I
`
`This application is hereby filed by named in the prior application. Petition is
`hereby made requesting deletion as inventor(s) of the following who islare 11_ojinventor(s) of the
`invention being claimed in this application:
`
`
`
`
`2.
`4.
`6.
`8.
`10.
`
`1.
`3.
`5.
`7.
`9.
`
`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.
`
`PAT-10812/95
`
`GOOG-1002
`Page 7 of 351
` *f
`
`
`
`
`
`
`
`
`
`2
`
`
`
`
`
`
`
`
`
`
`
`IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`REQUE§I E03 FILING
`(RULE 53(b)(1))
`
`For Design Q[ L_J1ility Appligtiong
`
`I
`
`I]
`>24
`
`P
`
`I AT 0 :
`
`I(1
`)
`Continuation
`) application under 37 CFR 1.53(b)(1)
`)
`Divisional
`of pending prior application of
`
`-E.
`9
`‘E. E
`£3 E:
`(DO:
`5?, ‘$3
`aj‘-,‘~%¢
`ms %°
`.3 %
`
`GOOG-1002
`
`

`
`
`
`of
`(country)
`
`Eiijng Date
`
`4.
`
`E]
`
`Priority is claimed under 35 U.S.C. 119/365 based on filing in
`
`fll‘Lng_Qate
`ii
`i
`
`(4)
`
`(5)
`(6)
`
`A.QD|_iQa_tJ'Qn_&
`
`
`
`(1)
`(2)
`(3)
`
`a. (:1
`b. [:1
`
`(No.) Certified copy/copies attached.
`
`Certified copy/copies previously filed on
`, filed on
`U.S. Application No.
`I
`1) serialgo.
`seLi_es_c9de fr
`Certified copy/copies filed during international stage of PCTI
`c. (:1
`(a) [:1
`Dorrestic priority is claimed from PCTI __l
`,
`(b) (:1
`Benefit is claimed of Provisional Application No.
`
`in
`.
`
`
`I
`.
`filed
`.
`
`60/
`
`, filed
`
`E
`
`Prior application is assigned to Kiugigch Inc.
`
`by assignment recorded
`
`June 23, 1995
`(Date)
`Attached is the following number of Assignments (including original and all later successive ones by
`different assignors):
`1
`and respective new Cover Sheets. (Do Q file old cover sheets.)
`
`Reel
`
`7593
`
`Frame
`
`0036.
`
`(Assignments in parent &d with new Cover Sheets in this continuing application if you
`want iilthem recorded against the-continuing application.)
`
`r
`
`s‘
`
`h
`
`rs‘ ne .
`
`E
`
`Pl
`
`The power of attorney in the prior application is to Qale §. Lazar, Beg ug. g§,a72
`E
`(Name and Reg. No.)
`whose current address is as in item 8 below.
`
`a. E Recognize as associate attorney Brian Siritzky. Reg. No. 37,497 __
`
`(Name, Reg. No. and Address)
`
`Address all future communications to intellectual Property Group
`of Pillsbury Madison & Sutro LLP, Ninth Floor, East Tower 1100 New York Avenue, N.W.,
`Washington, D.C. 20005-3918
`
`E Amend the specification by inserting before the first line the sentence:—This is a
`E continuation E division
`of Application No.
`08/960,079.
`filed Qctgber 24 1992
`goods 1}
`tr seLiaLno.
` j__j
`which is a continuation of 08/425.160, filed April 11, 1995, now abandoned.
`
`.--
`
`(a)
`
`(:1 Amend the specification by inserting before the first line: —This application claims the benefit of
`Provisional Application No. 60/
`, filed j .--
`
`514
`
`it has been recently determined that this new continuing application is entitled to small entity status.
`Hence:
`'
`
`(No.) Verified Statement(s) establishing “small entity" status under Rules 9 & 27 were/are:
`Efiled in above prior application (and hence applicable hereto)
`attached.
`
`4.
`
`5.
`
`6.
`
`7.
`
`8.
`
`9.
`
`9.
`
`10.
`
`11.
`(gig box)
`(mu_tsi be)
`(x'd)
`
`Petition to extend the life of the above prior application
`[:| is being concurrently filed in that prior application (Use Form PAT-111).
`[:1 was previously filed in that prior application (Check length of prior extension).
`E is not necessary fg_Lcgp_e_n_cl_e_r(_oy (Double check before X’ing this box).
`
`PAT-101! 12/98
`
`GOOG-1002
`Page 8 of 351
`
`;
`
`<
`
`=
`
`>
`
`?
`
`@
`
`A
`
`B
`
`C
`
`8
`
`GOOG-1002
`
`

`
`
`
`Page 3 of 4
`
`12.
`
`[2]
`
`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 n_o_t_Legm_d now. Please
`consider those documents and _ad1i_s_e 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.
`
`14.
`
`[:1
`
`Attached is a Rule 103(a) Petition to Suspend Action.
`
`IE I to beinjiered before fee c_gl_c_ula_tjgn_: (Do n_o_t 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 mt cancel all claims).
`
`Please cancel claims 1-45 and 50-53 without prejudice. The remaining claims correspond to non-elected
`Groups Ill & lV from the Examiner's Restriction Requirement of June 4, 1996.
`
`F E
`I
`THE FOLLOWING FILING FEE IS BASED ON
`->->->->QLAlM§ As FILE); Ago C|;lANGED_BY PRELIMINARY AMENMENT IN ITEM 1g<-<—<-<-
`
`NOTE:
`
`If box 1A2 is X’d, do not pay fees.
`but leave lines 15-22 and 27-32 mam;
`
`. .Design Application- 106/25
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`15. Basic Filing Fee .
`101/201
`+380
`$760/$380
`Not Design Application
`16. Basic Filing Fee
`17- Tolal Eiieclive Claims jflj 103003
`13. Independent Claims E_ W“?
`19. If any player multiple dependent claim (inore improper) is resent,
`$260/$130
`104/204
`20.
`Subtotal =
`
`$380
`
`Entity
`
`Code
`
`22.
`
`23.
`
`24.
`
`25.
`
`[:1 ATTACHED:
`
`[j Preliminary Amendment attached (to be entered afler assigning Appln. No.)
`
`[:1 The following PRELIMINARY AMENDMENT is to be entered _aj_e_r assigning Appln. No.:
`
`(carry forward to Item 31)
`
`PAT-108 12198
`
`‘
`
`GOOG-1002
`Page 9 of 351
`,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`D
`
`GOOG-1002
`
`

`
`ADDITIONAL FEE CALCULATION FOR
`PRELIMINARY AMENDMENT
`PER BQXES 24/25
`
`Claims
`remaining
`after
`amendment
`
`Highest
`number
`previously
`paid for
`
`Present
`Extra
`
`Additional
`Fee
`
`L r
`
`I mall En itv
`
`Total Effective Claims
`
`Independent Claims
`
`*
`
`*
`
`minus **
`
`20
`
`minus ***
`
`3
`
`=
`
`=
`
`O
`
`o
`
`x
`
`x
`
`$18/$9
`
`$78/$39
`
`=
`
`=
`
`$ 0
`
`+
`
`0
`
`Page 4 of 4
`
`File code
`
`(103/203)
`
`(1021202)
`
`If amendment enters proper multiple dependent claim(s) into this application for the
`fL§t_tjm§, add (per application)
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`. .$260/$130
`
`+ 0
`
`004/204)
`
`ADDITIONAL FEE
`
`$ 0
`
`mus FEE from item 22 on page 3
`
`IQIAL EEE ATTACHED
`
`+ 420
`
`$ 420
`
`‘lithe entry In this space is lessthan the entry in the next space, the ‘Present Extra” result is ‘O’
`
`“if the ‘Highest number previously paid for’ (see term 17 above) a less than 20, write “20" in this space
`
`lfths “Highest number previously paid for (see item 18 above) is less than 3. write “3' In this space
`
`25.
`
`27.
`
`28.
`
`29.
`
`30.
`
`31.
`
`32.
`
`33,
`
`34,
`
`35,
`
` : Upon the filing of a Declaration pursuant to Rule 60(b) or 60(d), the Commissioner is hereby
`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 ( ) 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 in the heading hereof for which
`purpose a g_up_|j§_aj;§ copy of this sheet is attached.
`This CHARGE STATEMENT does 1191 is charge of the i_s_s_u_e fig untlllunless an Issue fee transmittal form
`is filed.
`
`Pillsbury Madison & Sut -I l,;I.P
`Intellectual Property G up
`
`
`
`1100 New York Avenue, N.W.
`Ninth Floor, East Tower
`Washington, D.C. 20005-3910
`Tel: (202) 861-3000
`DSLlBS:kim
`Atty./Sec.
`
`By Atty:
`Sig:
`
`
`
`ale 5.
`
`'
`
`’
`
`. ,»'
`,. / "
`
`”
`
`/‘ Reg. No.
`Fax:
`Tel:
`
`
`
`28872
`.
`(202) 322-0944
`(202) 861-3527
`
`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?
`
`PAT-108 12/96
`
`GOOG-1002
`Page 10 of 351 ,
`
`M
`
`N
`
`O
`
`P
`
`J
`
`K
`
`Q
`
`R
`
`S
`
`T
`
`J
`
`GOOG-1002
`
`

`
`
`
`APPLICATION UNDER UNITED STATES PATENT LAWS
`
`Invention: David A.
`
`Farber and Ronald D. Lachman
`
`Inventor(s):
`
`IDENTIFYING DATA IN A DATA PROCESSING SYSTEM
`
`Cushman Darby & Cushman, LLJ.
`1100 New York Avenue, N.W.
`Ninth Floor, East Tower
`Washington, D.C. 20005-3918
`Attorneys
`-
`Telephone:
`(202) 861-3000
`
`This is Q:
`
`[
`
`1
`
`[X]
`
`E
`
`J
`
`E
`
`[
`
`]
`
`]
`
`Provisional Application
`
`Regular Utility Application
`
`Continuing Application
`
`PCT National Phase Application
`
`Design Application
`
`Reissue Application
`
`Plant Application
`
`SPECIFICATION
`
`CDC-HID
`
`J/E5
`
`GOOG-1002
`Page11 of351
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`GOOG-1002
`
`

`
`C \
`"
`7018/213987
`
`C#%
`BACKGROUND OF THE INVENTION
`
`1.
`
`Field of the invention
`
`5
`
`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
`
`Data processing (DP) systems, computers,f
`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,
`these collections
`themselves being named by identifiers. 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
`(collections). These directories can then,
`themselves be
`made part of other directories.
`A data item may thus be
`identified relative to these nested directories using a
`
`15
`
`20
`
`25
`
`30
`
`GOOG-1002
`Page12of351
`
`Q
`
`R
`
`S
`
`T
`
`J
`
`M
`
`N
`
`O
`
`P
`
`J
`
`L
`
`GOOG-1002
`
`

`
`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
`can then be specified using the database file name,
`the
`table,name, and the record number of that data record.
`other examples of identifying data items
`identifying files in a network file system,
`include:
`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,
`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
`
`10
`
`15
`
`
`
`20
`
`25
`
`30
`
`35
`
`GOOG-1002
`Page13of351
`
`b
`
`c
`
`a
`
`d
`
`Z
`
`]
`
`^
`
`_
`
``
`
`Z
`
`a
`
`GOOG-1002
`
`

`
`the keys in a database table, or
`process address space,
`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
`A
`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).
`Therefore it may require further processing, typically on
`the part of the requestor,
`to verify that the data item
`it has obtained is,
`in fact,
`the item it requested.
`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
`
`3
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`H
`
`
`
`m
`
`n
`
`o
`
`p
`
`GOOG-1002
`Page14of351
`
`j
`
`q
`
`r
`
`s
`
`t
`
`u
`
`j
`
`GOOG-1002
`
`

`
`
`
`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
`The need to keep the cache
`items onto the cache client.
`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 common and substantially unique
`identifier for a data item, using only the data in the
`data item and not relying on any sort of context.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`
`
`GOOG-1002
`Page 15 of 351
`
`b
`
`c
`
`a
`
`d
`
`Z
`
`]
`
`^
`
`_
`
``
`
`Z
`
`d
`
`GOOG-1002
`
`

`
`
`
`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
`reduce multiple copies.
`It is further desirable to
`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
`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
`)
`problems described above.
`
`IEZENTLON
`sgnggg Q: Eflfi
`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
`location,
`item is independent of its name, origin,
`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.
`Using the method or apparatus of_the present
`the efficiency and integrity of a data
`invention,
`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
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`GOOG-1002
`Page 16 of 351
`
`
`
`
`
`
`
`
`
`
`
`
`v
`
`
`
`
`
`
`
`
`
`
`
`GOOG-1002
`
`

`
`
`
`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
`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
`retained;
`I
`
`when the system is being used to cache data
`
`items, problems of maintaining cache consistency are
`avoided;
`
`the system maintains a desired level of
`
`to
`redundancy of data items in a network of servers,
`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;
`
`10
`
`15
`
`2d
`
`25
`
`30
`
`the system can efficiently record and preserve
`any collection of data items;
`
`the system,can efficiently make a copy of any I
`collection of data items, to support a version control
`mechanism for groups of the data items;
`
`35
`
`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;
`
`GOOG-1002
`Page 17 of 351
` ‘**a
`
`
`
`
`
`
`
`
`
`
`
`2
`
`‘
`
`
`
`
`
`
`
`
`
`
`
`GOOG-1002
`
`

`
`
`
`the system can maintain a local inventory of
`all the 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,
`with one another;
`
`to be periodically resynchronized
`
`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
`
`independent of the
`items according to content by owner,
`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.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`PTI N
`T
`D WI GS
`GURE 1 depicts a typical data processing
`.3xé>>
`h a preferred embodiment of the present
`system in wh
`invention oper tes;
`
`FIGURE 2 depicts a hierarchy of data items
`
`stored at any location in such a data processing system;
`
`GOOG-1002
`Page 18 of 351
`
`
`
`€
`
`
`
`‚
`
`|
`
`ƒ
`
`„
`
`…
`
`†
`
`‡
`
`|
`
`GOOG-1002
`
`

`
`FIGURES 3-9 depict data structures used to
`implement an embodiment of the present invention; and
`
`FIGURES 10(a)—28 are flow charts depicting
`operation of various aspects of the present invention.
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`
`
`TAI
`avé
`
`P ES NTL
`F T
`D D S RIPTIO
`EXEMPLARY EMBODIMENTS
`-
`
`PREF RR D
`
`
`includes
`system 100, w ich, with reference to FIGURE 1,
`one or more pr
`essors (or computers) 102 and various
`
`storage devices
`
`a bus 106.
`
`04 connected in some way, for example by
`
`Each processor 102 includes a CPU 108, a memory
`110 and one or more local storage devices 112.
`The CPU
`108, memory 110, and local storage device 112 may be
`internally connected, for example by a bus 114.
`Each
`
`processor 102 may also include other devices (not shown),
`such as a keyboard, a display, a printer, and the like.
`In a data processing system 100, wherein more
`than one processor 102 is used, that is,
`in a
`multiprocessor system,
`the processors may be in one of
`various relationships.
`For example,
`two processors 102
`may be in a client/server, client/client, or a
`server/server relationship. These inter-processor
`relationships may be dynamic, changing depending on
`particular situations and functions. Thus, a particular
`processor 102 may change its relationship to other
`
`processors as needed, essentially setting up a peer—to-
`peer relationship with other processors.
`In a peer—to-
`peer relationship, sometimes a particular processor 102
`acts as a client processor, whereas at other times the
`
`same processor acts as a server processor.
`In other
`words,
`there is no hierarchy imposed on or required of
`processors 102.
`
`35
`
`the processors 102
`In a multiprocessor system,
`’
`may be homogeneous or heterogeneous. Further,
`in a
`
`GOOG-1002
`N
`Page19of351
`
`
`
`€
`
`
`
`‚
`
`|
`
`ˆ
`
`„
`
`…
`
`†
`
`‡
`
`|
`
`GOOG-1002
`
`

`
`
`
`some or all of
`multiprocessor data processing system 100,
`the processors 102 may be disconnected from the network
`
`Such disconnection
`of processors for periods of time.
`may be part of the normal operation of the system 100 or
`
`it may be because a particular processor 102 is in need
`of repair.
`
`Within a data processing system 100,
`
`the data
`
`may be organized to form a hierarchy of data storage
`elements, wherein lower level data storage elements are
`combined to form higher level elements. This hierarchy
`can consist of, for example, processors, file systems,
`regions, directories, data files, segments, and the like.
`
`For example, with reference to FIGURE 2,
`
`the data items
`
`on a particular processor 102 may be organized or
`structured as a file system 116 which comprises regions
`117, each of which comprises directories 118, each of
`
`which can contain other directories 118 or files 120.
`Each file 120 being made up of one or more data segments
`122.
`
`In a typical data processing system,
`
`some or
`
`all of these elements can be named by users given certain
`
`the name (or
`implementation specific naming conventions,
`pathname) of an element being relative to a context.
`In
`
`the context of a data processing system 100, a pathname
`
`is fully specified by a processor name, a filesystem
`name, a sequence of zero or more directory names
`
`identifying nested directories, and a final file name.
`
`(Usually the lowest level elements,
`
`in this case segments
`
`122, cannot be named by users.)
`
`In other words, a file system 116 is a
`collection of directories 118.
`A directory 118 is a
`collection of named files 120 -- both data files 120 and
`
`A file 120 is a named data
`other directory files 118.
`item which is either a data file (which may be simple or
`
`compound) or a directory file 118.
`consists of a single data segment 122.
`
`A simple file 120
`A compound file
`
`120 consists of a sequence of data segments 122.
`
`A data
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`9
`
`/
`/LJ
`
`GOOG-1002
`Page20of351
`
`;
`
`<
`
`=
`
`>
`
`:
`
`9
`
`@
`
`A
`
`B
`
`C
`
`8
`
`GOOG-1002
`
`

`
`segment 122 is a fixed sequence of bytes.
`
`An important
`
`property of any data segment is its size,
`bytes in the sequence.
`
`the number of
`
`A single processor 102 may access one or more
`
`file systems 116, and a single storage device 104 may
`contain one or more file systems 116, or portions of a
`
`For instance, a file system 116 may
`file system 116.
`span several storage devices 104.
`
`In order to implement controls in a file
`system, file system 116 may be divided into distinct
`
`regions, where each region is a unit of management and
`control.
`A region consists of a given directory 118 and
`
`is identified by the pathname (user defined) of the
`directory.
`
`the term "location", wrth
`In the following,
`respect to a data processing system 100, refers to any of
`a particular processor 102 in the system, a memory of a
`particular processor, a storage device, a removable
`
`10
`
`15
`
`20
`
`storage medium (such as a floppy disk or compact disk),
`The term
`or any other physical location in the system.
`
`"local" with respect to a particular processor 102 refers
`
`to the memory and storage devices of that particular
`processor.
`
`25
`
`the terms "True Name", "data
`In the following,
`identity“ and "data identifier" refer to the
`
`substantially unique data identifier for a particular
`data item.
`The term "True File" refers to the actual
`
`file, segment, or data item identified by a True Name.
`
`A file system for a data processing system 100
`is now described which is intended to work with an
`existing operating system by augmenting some of the
`operating system's file management system codes.
`The
`embodiment provided relies on the standard file
`
`management primitives for actually storing to and
`retrieving data items from disk, but uses the mechanisms
`of.the present invention to reference and access those
`data items.
`
`30
`
`35
`
`10
`
`
`
`GOOG-1002
`Page 21 of 351
`
`m
`
`n
`
`o
`
`p
`
`l
`
`j
`
`r
`
`s
`
`t
`
`u
`
`j
`
`GOOG-1002
`
`

`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`The processes and mechanisms (services)
`provided in this embodiment are grouped into the
`following categories: primitive