`
`#7
`
`
`
`FILED WITH: |j ISK (CRF) DFICHE
`(Attached in pocket on nght inside flap)
`
`
`
`PREPARED AND APPROVED FOR ISSUE
`
`ISSUING CLASSIFICATIO
`cnoss REFERENCE(S) ‘
`
`Illleeeelnllulli
`
`SU BCLASS
`
`m 11
`
`TERI
`DISCLAIMER
`
`§
`
`_
`
`;
`[I a) The term of this patent
`subsequent to
`__ (date) ;
`has been disclaimed.
`
`W b) The term of this patent shall
`01 extend beyond the gxplratiorg dat
`fU.SP
`.m.§J_,
`.
`°
`°
`
`a‘°'“
`
`(Assistant Examiner)
`
`PRIMARY EXAMINER
`
`Jam
`
`I E] c) The tenninal _____months of
`this patent have been disclaimed.
`
`T '-~.j\'3
`
`Q?
`nls Examiroerf
`
`j WARNING:
`=' Tint: xninrmatlon dlsnlased herein may be restricted. Unauthorized disclosure may be prohlbtted by the United States Code Title 35. Sections 122, 181 and 368.
`'-, Possession outsnde the U.S. Patent & Trademark Office is restricted to authorized employees and contractors only.
`Form PTO-438A
`(Rev 8/98)
`
`A
`
`‘
`
`"‘
`
`(LABELAREA)
`
`3
`
`I \
`
`(F
`
`X
`
`.6 so;
`
`RACK-1002<\‘\
`H
`t‘:*Bage_1-of 351
`
`P1,.‘
`
`:53
`, ’
`
`3
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`z9+
`
`-<9‘
`
`E(I)
`
`
`
` S.bc:la’ss'I
`
`
`
`E’0
`u3
`(D
`Q
`
`' SECTOR
`
`PATENT NUMBER
`
`641 5280
`
`6415280
`
`'k
`xii’.
`is:
`PATENT DATE
`LITY PATENT APDIT I’
`.u ION
`
`lllllllwl|\|l\ll|||lN|ll||l}|\\|||H\||\
`
`
`
`
`
`‘V59’/gtéfi-60915 4‘
`J
`L:cim_oN"‘. (/4
`\ .WW%WW@mwm
`I
`I
`|\ll\\\\i\\\\\\\
`
`:1\1\x\\\g\g\gu
`
`APP
`
`NT
`‘E
`PA}
`|\\\\ll\\|\|\‘.l
`H
`D928
`
`‘CCNTENTS
`Date received
`(Incl. 0. of M.)
`0|‘
`Date Mailed
`
`Date received
`(Incl. C. at M.)
`or
`Date Malled
`
`
`
`'1
`
`1. Appliearion
`.2. * ?3w;
`:
`V
`.
`)
`,
`.3.
`,«~’4.
`g'27_L_t5\‘sv\ J3
`
`.
`
`I5
`
`papers.
`
`40! 39
`
`_
`ll 0| _
`.2 4 3—u;«J\
`aL—(‘*?>‘“M
`
`42.
`
`43.
`
`44.
`
`45.
`
`46.
`
`47.
`
` 48.
`
`49.
`
`50.
`
`51.
`
`52.
`
`5
`
`.
`
`.
`
`,;;9-
`
`_
`
`A11
`12
`
`'77
`
`4
`
`
`
`ri”"Io.“%"gA/~«_mz.gm§4‘ 6.3;Kg-‘wuvx
`AM?
`U
`'
`'
`ifim
`r€.(‘:€lo'n5__
`/A/m~-_—=‘tm'c,
`1 H. A.ommunwam
`1/
`. 4/
`.
`r‘0v)/WM‘
`.D/Hwt/ry
`b15_
`-F606 Afificn
`<’\
`,4 VW
`We.
`
`
`53.
`
`54.
`
`55.
`
`56.
`
`57.
`
`58.
`
`59.
`so.
`
`51.
`52.
`
`63.
`
`e4.
`
`65.
`
`66.
`
`57.
`
`ea.
`
`69.
`
`70.
`
`71 .
`
`72.
`
`73.
`
`74.
`
`75.
`
`76. _
`
`77.
`
`78.
`
`79.
`
`80.
`
`81.
`
`82.
`
`(LEFT OUTSIDE)
`
`
`
`
`
`
`
`'
`
`‘”
`
`'
`
`3
`
`*._x~.1.
`
`
`
`Page 2 of 351
`
`RACK-1002
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ISSUE SLIP STAPLE A1’
`
`(fart rd-‘litional cross references)
`
`POSITION
`
`,I=:_is betsnmlnnnou
`
`»
`
`I
`
`‘A
`
`.
`
`,,
`
`A="'E§Eflw%i'I/
`
`mN.IInun:InnIIIII,InHWV___._.mIIIsMm.IIIIIIIIIIII2n.33....“n..nc.u.—InW.
`IIIIIIIIIIIMJ.a=...IunI...m,.a..am__£. .mF...x...
`
`
`
`GEIIIIIIIIIIIIIIHIIIII
`
`
`
` 0ranamDmmmm«..IN.H»W1|V§R.A.c.n.
`
`uH.HE.."GEatOla;1.Wxx.mIIIIIIIII1IIla"nn._.._.....=..I_.
`.m_Em.,_rawmmmmmmuwmmumum
`
`Non-elected
`Interference
`Appeal
`objected
`
`F.
`
`M..
`
`
`
`UNIA0oCmI4
`
`
`
`If more than 150 claims or 10 actions
`staple additional sheet here
`
`(LEFT INSIDE)
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 3 of 351
`
`RACK—1002
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SEARCH NOTES
`
`(INCLUDING SEARCH STRATEGY)
`
` RAQK—1002)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ge"4 bf 351
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`COMMISSIONER FOR PATIENT:
`UNITED Sr/was PATENT AND TRADEMARK Omca
`INASHINGTON. D.C. 2O23I
`w-Ivv/uspiagcw
`
`CONFIRMATION NO. 9574
`IIIIIIIIIII IIIIIIIIIIIIIIIIII IIIIIIIII IIII III III IIIIIIIII
`Bib Data Sheet
`
`FILING DATE
`ATTORN EY
`DOCKET NO.
`SERIAL NUMBER
`04/01/1999
`GROUP ART UN” '
` PM252465
`09/283,160
`RULE
`2177
`
`
`* PPLICANTS
`
`DAVID A. FARBER, OJAI, CA;
`RONALD D. LACHMAN, NORTHBROOK, IL;
`
` irk*****
`
`
`
`
`
`
`* CONTINUING DATA
`
`* FOREIGN APPLICATIONS ********************
`
`
`
`
`
`
`
`IF REQUIRED, FOREIGN FILING LICENSE
`RANTED ** 0421/1999
`
`Foreign Priority claimed
`El yeyfi no
`lNI}‘EF’ENDENT
`STATE OR
`SHEETS
`
`35 use 119 (a-d) condltlons
`l:| yes Em D Met am
`
`CLAIMS
`me,
`Allowance
`COUNTRY DRAWING
`
`3
`Verified and
`V\.
`I
`CA
`24
`
`Acknowladed
`Examiners Slnature
`ials
`_
`‘
`‘
`_
`_
`n__'_'__
`ADDRESS
`
`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 DATA
`D II Fees L I
`L‘
`“ j
`
`
`D1.16Ff.e_es(FiIing)
`
`D 1.17 Fees ( Processing EXI. on‘
`FILING FEE FEES: Authority has been given in Paper
`
`RECEIVED No.
`to charge/credit DEPOSIT ACCOUNT
`time) _
`Mi
`for following:
`D1318 |;es(Issue)
`H
`‘H
`
`
`** SMALL ENTITY **
`
`
`
`‘
`
`
`
`
`
`
`
`
`
`
`
`RACK—1002
`Page 5 of 351
`
`(
`'
`'
`&
`%
`$
`#
`"
`!
`+*) & ,-./0-
`
`
`
`
`
`
`
`
`
`
`
`
`PATENT APPLICATION SERIAL NO.
`
`U.S. DEPARTMENT OF COMMERCE
`PATENT AND TRADEMARK OFFICE
`FEE RECORD SHEET
`
`:» W \
`/W/L,,£;.
` ’ \//{r_'_,,'
`
`.
`
`’
`
`}
`r
`
`14/12/1999 kl-ll-WES
`
`00000010 09283160
`
`11 FC:20I
`
`360.00 00
`
`PTO- 1556
`
`(5/87)
`'U.S. GPO: 199B-433-214/BO404
`
`!
`
`*
`
`+
`
`"
`
`,
`
`$
`
`#
`
`1
`
`)
`
`RACK-1002
`:
`Page 6 of 351
`
`%
`
`.
`
`&
`
`/
`
`'
`0
`
`'
`-
`
`(
`
`&
`
`
`
`Page 1 of 4
`
`FOR clPs)
`
`o E.
`E
`E”:
`S E‘;
`(DO:
`52?, fie
`332%
`ma %
`El %
`
`
`
`Group Art Unit:
`
`2776
`
`Examiner:
`
`Homere, J.
`
`FARBER et al.
`Inventor(s):
`Parent Appln. No.:
`
`PM 252465
`08
`bfl, M1:
`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# / New M#
`
`960.079
`1} Serial No.
`
`Atty. Dkt.
`
`cnent Ref
`
`Asst. Commissioner of Patents
`
`Washington, DC 20231
`Sir:
`
`Date:
`
`April 1, 1999
`
`:
`'
`
`(Parent Matter No.
`
`243063
`
`)
`
`To effect the above-requested filing today:
`
`1. egg is a copy ( hl
`
`be fi d) of this application, including:
`
`X Abstract
`El
`Specification and claims ($1 pages) (mgsj be attached)
`X Drawings (must be attached If orlglnally flled): 2_4 sheet(s)/set: XI 1 set informal;
`[] Formal of size
`[3 A4
`
`Always X one box, only:
`1A.
`(1) E §_[gn_e_d declaration or oath as originally filed in pn'or application attached
`(2) El N9 declaration or fee is enclosed; therefore, this is a filing under Rule 53(f).
`
`I] 11"
`
`2.
`
`[I
`
`This application is hereby filed by less than a I of the im_/entgrs named in the prior application. Petition is
`hereby made requesting deletion as inventor(s) of the following who is/are n_oj inventor(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/9!!
`
`RACK—1002
`Page 7 of 351 "
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`RE U ST F
`FILING
`(RULE 53(b)(1))
`
`Fgr Design Q]: utility Agpngggions
`
`I
`
`El
`
`X]
`
`I(1
`Continuation
`
`I
`
`T O :
`
`T A
`)
`) application under 37 CFR 1.53(b)(1)
`)
`Divisional
`of pending prior application of
`
`
`
`
`
`Priority is claimed under 35 U.S.C. 119/365 based on filing in
`‘
`1
`H
`&
`fllLn9_Qate
`
`of
`
`Fl’
`
`D e
`
`(country)
`Amletmdo.
`
`
`(4)
`(5)
`(6)
`
`
`
`4.
`
`E]
`
`(1)
`(2)
`(3)
`
`(No.) Certified copy/copies attached.
`a. [:1
`
`b. E Certified copy/copies previously filed on
`U.S. Application No.
`/
`I
`‘
`it
`swam fr
`c. E Certified copy/copies filed during International stage of PCTI
`(a) [:1
`Domestic priority is claimed from PCT/ ___l____ ,
`(b) E Benefit is claimed of Provisional Application No.
`60/
`
`, filed on
`
`filed
`
`, filed
`
`I
`
`in
`
`.
`
`
`
`F14
`
`Prior application is assigned to Kiuglggh lng.
`
`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 {mg Cover Sheets. (Do Q file old cover sheets.)
`
`Reel
`
`7593
`
`Frame
`
`0036.
`
`(Assignments in parent fl with new Cover Sheets in this continuing application if you
`want it/them recorded against the-continuing application.)
`
`re o
`
`si
`
`h
`
`rs‘
`
`E
`
`Pl
`
`The power of attorney in the prior application is to Qale §. Lazar ggg N9. 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 8. Sutro LLP, Nlnth 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
`. it
`it seLial_no_.
`which is a continuation of 08/425.160, filed April 11, 1995, now abandoned.
`
`b
`
`.--
`
`199
`
`(a)
`
`[:1 Amend the specification by inserting before the first line: -This application claims the benefit of
`Provisional Application No. 60/
`, filed
`.--
`
`10. E 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)
`E attached.
`
`11.
`(gl_e box)
`(mu_st be)
`(x'd)
`
`Petition to extend the life of the above prior application ;<m
`[:| is being concurrently filed in that prior application (Use Form PAT-111).
`|'_‘) was previously filed in that prior application (Check length of prior extension).
`E is not necessary fgLcg);e_n_d_e_r)_cy (Double check before X’ing this box).
`
`PAT-103 12/98
`
`RACK-1002
`
`Page 8 of 351
`
`3
`
`<
`
`;
`
`=
`
`4
`
`>
`
`6
`
`5
`
`?
`
`7
`
`@
`
`8
`A
`
`9
`B
`
`9
`C
`
`:
`8
`
`Lg»;
`
`4.
`
`5.
`
`6.
`
`7.
`
`8.
`
`9.
`
`9.
`
`
`
`
`
`Page 3 of 4
`
`12.
`
`IE
`
`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 net required now. Please
`consider those documents and fiyiee 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
`
`IE
`
`Attached is a Rule 103(a) Petition to Suspend Action.
`
`PBELIMJNABX AMENQMENI 19 be entered gefore fee eelgglejiong (Do n_Qt 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 mg cancel all claims).
`
`Please cancel claims 1-45 and 50-53 without prejudice. The remaining claims correspond to non-elected
`Groups Ill & IV from the Examiner's Restriction Requirement of June 4, 1996.
`
`F E
`L
`THE FOLLOWING FILING FEE IS BASED ON
`->->.>—>QLAlM§ As FILEQ AND Cl-_lANGED_B_Y_PBELlMflARY_AMENDM_ENJ' IN ITEM 14<-<-<-<-
`
`NOTE:
`
`If box 1A2 is X’d, do not pay fees,
`but leave lines 15-22 and 27-32 blame
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`15. Basic Filing Fee .
`.
`. .Design Application
`+380
`$760/$380
`N_o_t Design Application
`16. Basic Filing Fee
`17. Total Effective Claims MM +0
`1B. Independent Claims Ej +0
`19. If eny Lroper multiple deendent claim (ignore improper) is present,
`$260/$130
`+0
`20.
`Subtotal =
`$380
`
`Enti
`
`22.
`
`Code
`
`106/26
`101/201
`103003
`102/202
`104/204
`
`23.
`
`24.
`
`25.
`
`[:1 ATTACHED:
`
`1] Preliminary Amendment etteehed (to be entered etter assigning Appln. No.)
`
`[:1 The following PRELIMINARY AMENDMENT is to be entered _aj_e_[ assigning Appln. No.:
`
`(carry forward to Item 31)
`
`PAT-1O8 12/95
`
`‘
`
`
`
`RACK—1002
`Page 9 of 351
`,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`D
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ADDITIONAL FEE CALCULATION FOR
`PRELIMINARY AMENDMENT
`aeseoxesms
`
`Claims
`remaining
`after
`amendment
`
`Highest
`number
`previously
`paid for
`
`Present
`Extra
`
`Additional
`Fee
`
`Large/Small Entitv
`
`Total Effective Claims
`
`Independent Claims
`
`*
`
`*
`
`minus **
`
`20
`
`minus ***
`
`3
`
`=
`
`=
`
`o
`
`O
`
`x
`
`x
`
`$18/$9
`
`$78/$39
`
`=
`
`=
`
`5 0
`
`+
`
`0
`
`Page 4 of 4
`
`File code
`
`(103/203)
`
`(102/202)
`
`If amendment enters proper multiple dependent claim(s) into this application for the
` , add (per application)
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`. .$260/$130
`
`+ 0
`
`004/204)
`
`ADDITIONAL FEE
`
`$ 0
`
`plus FEE from item 22 on page 3
`
`mmeeeunacuec
`
`+ 420
`
`$ 420
`
`‘It the entry In this space is lessthan the entry In the next space, the ‘Present Extra’ result is '0“
`
`“Ifthe ‘Highest number previously paid for" (see item 17 above) is less than 20, write "20" in this space
`
`lfthe “Highest number previously paid for’ (sea Item 18 above) is less than 3. write ‘*3’ in this space
`
`25.
`
`27.
`
`28.
`
`29.
`
`30.
`
`31.
`
`32-
`
`33,
`
`34,
`
`35_
`
`Cl-_IABGE §TAI§MENI: 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 applicafion 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 gi_up_|jg_aj;§ copy of this sheet is attached.
`This CHARGE STATEMENT _d_o_e§ not autmrige charge of the i_s;u_e Lee untlllunless an issue fee transmittal form
`is filed.
`2
`
`
`Pillsbury Madison & Sutr /LLP
`Intellectual Property G up
`
` /
`
`
`1100 New York Avenue, N.W.
`Ninth Floor, East Tower
`Washington, Dc. 20005-3918
`Tel: (202) 861-3000
`DSL/BS:kim
`Atty./Sec.
`
`By Atty:
`Sig:
`
`
`
`ale 8.
`
`'
`
`’
`
`,. / ‘
`
`”
`
`/2 Reg. No.
`Fax:
`Tel:
`
`
`
`28872
`.
`(202)822-0944
`(202) 861-3527
`
`NOTE No.1: File this Request in ggglicate with 2 postcard receipts (PAT—103) & attachments
`NOTE No. 2: Is extension In parent necessary for copendency?
`
`PAT~108 12/95
`
`RACK-1002
`Page 10 of 351 ,
`
`F
`
`E
`
`O
`
`P
`
`H
`
`G
`
`J
`
`K
`
`I
`
`Q
`
`J
`R
`
`N
`
`K
`S
`
`K
`T
`
`L
`J
`
`M
`
`
`
`
`
`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:
`
`[
`
`] Provisional Application
`
`[ X] Regular Utility Application
`
`[
`
`[
`
`[
`
`[
`
`] Continuing Application
`
`] PCT National Phase Application
`
`] Design Application
`
`] Reissue Application
`
`] Plant Application
`
`SPECIFICATION
`
`CDC-IEO
`
`J/95
`
`‘
`RACK-1002
`Page11 of351 ‘
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`7018/213987
`
`
`BACKGROUND OF THE INVENTIQN
`
`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
`
`15
`
`20
`
`25
`
`30
`
`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 08 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
`
`Page12of351
`
`F
`
`E
`
`O
`
`M
`
`N
`
`P
`
`H
`
`G
`
`J
`
`L
`
`I
`
`Q
`
`J
`R
`
`RACK-1002
`
`K
`S
`
`K
`T
`
`L
`J
`
`
`
`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
`
`RACK-1002
`Page13of351
`
`V
`
`U
`
`_
`
``
`
`X
`
`W
`
`Z
`
`a
`
`Y
`
`b
`
`Z
`c
`
`^
`
`]
`
`[
`a
`
`[
`d
`
`\
`Z
`
`
`
`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
`
`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
`‘
`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
`
`e
`
`o
`
`p
`
`f
`
`h
`
`g
`
`j
`
`q
`
`i
`
`r
`
`j
`s
`
`Page14of351
`
`RACK-1002
`
`k
`t
`
`k
`u
`
`l
`j
`
`
`
`
`
`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
`
`
`
`Page 15 of 351
`
`V
`
`U
`
`_
`
`]
`
`^
`
``
`
`X
`
`W
`
`Z
`
`d
`
`Y
`
`b
`
`Z
`c
`
`RACK-1002
`
`[
`a
`
`[
`d
`
`\
`Z
`
`
`
`
`
`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.
`-
`
`NT 0
`I
`S
`in a data processing
`This invention provides,
`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.
`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
`
`RACK-1002
`Page 16 of 351
`IIIIIIIII.IIIII---____________________-_______—__—___—___———_—~\*‘*<‘¥
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`v
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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;
`T
`
`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 systemfican efficiently make a copy of any
`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;
`
`RACK—1002
`Page 17 of 351
` "*“a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`‘
`
`
`
`
`
`
`
`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
`
`5
`
`their name,
`
`location, and date of creation;
`
`10
`
`15
`
`20
`
`25
`
`30
`
`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;
`
`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.
`
`D WI GS
`T
`IO 0
`
`GURE 1 depicts a typical data processing
`ij2£>>
`h a preferred embodiment of the present
`system in wh
`invention oper tes;
`
`FIGURE 2 depicts a hierarchy of data items
`
`35
`
`stored at any location in such a data processing system;
`
`
`
`RACK—1002
`Page 18 of 351
`
`x
`
`w
`
`
`
`
`
`
`
`
`
`z
`
`y
`
`|
`
`
`
`{
`
`
`
`|
`
`
`
`}
`
`
`}
`
`
`~
`
`|
`
`
`
`gfi
`
`
`
`5
`
`10
`
`15
`
`20
`
`25
`
`3O
`
`35
`
`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.
`
`PRES NTLY REF RR D
`F T
`E AIL D D S RIPTIO
`EXEMPLARY EMBODIMENTS
`CDi>>
`embodiment of the present invention is now
`described w th reference to a typical data processing
`system 100, w ich, with reference to FIGURE 1,
`includes
`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.
`
`the processors 102
`In a multiprocessor system,
`‘
`may be homogeneous or heterogeneous. Further,
`in a
`8
`
`!\
`
`RACK—1002
`_,
`Page19of351
`
`z
`
`y
`
`|
`
`
`
`{
`
`
`
`|
`
`
`
`}
`
`
`}
`
`
`~
`
`|
`
`x
`
`w
`
`
`
`
`
`
`
`
`
`
`
`
`
`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
`
`implementation specific naming conventions,
`
`the name (or
`
`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
`
`pi
`f
`
`RACK4002
`Page20of351
`
`4
`
`3
`
`=
`
`>
`
`6
`
`5
`
`:
`
`9
`
`7
`
`@
`
`8
`A
`
`<
`
`;
`
`9
`B
`
`9
`C
`
`:
`8
`
`
`
`segment 122 is a fixed sequence of bytes.
`
`An important
`
`property of any data segment is its size,
`bytes in the sequence.
`A single processor 102 may access one or more
`
`the number of
`
`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", with
`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.
`
`30
`
`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