llllllllllllllllllllllllllllllllllllllll122204
`
`O "
`
`o[L
`
`achD
`05
`g:
`V"
`
`g
`*>
`C
`
`IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`REQUEST FOR FILING NATIONAL PATENT APPLICATION
`Under 35 use 111(a) and Rule 53(b) with Signed Declaration
`
`20>
`1blon. Commissioner of Patents
`.0. Box 1450
`
`lexandria, VA 22313-1450
`
`Sir:
`
`Herewith is the PATENT APPLICATION of:
`
`NONPROVISIONAL
`
`NON REISSUE NON PCT NAT PHASE
`
`Atty. Dkt. No.: 2618-0011
`‘
`
`Date: December 22, 2004
`
`
`
` _nventor(s): FARBER,_avidA.-_CHMANRonald D
`
`
`Title'
`CONTENT DELIVERY NETWORK AND ASSOCIATED METHODS AND
`MECHANISMS
`
`Including:
`
`1. Specification: 7_7 pages (only spec. and claims)
`
`2. [:l Specification in non-English language
`
`3.
`
`4.
`
`5.
`
`IX Declaration: E] Original [2 Facsimile/Copy
`
`3b. [Z Abstractl page(s); Q claims
`
`[XI Drawings: §_1_ sheet(s) ofl] informal;
`
`[Z formal size:
`
`[:1 A4
`
`IE 11”
`
`[:1 Attached an Assignment document and Recordation cover sheets. Please return the recorded
`assignment to the undersigned.
`
`
`6. X Prior application is assigned to SAVVISI Inc. by Assignment recorded on December 3 2004' Reel Unknown
`Frame Unknown, and KINETECHI Inc. by Assignment recorded on November 15, 2001; Reel 012313/Frame
`04___4_6.
`
`
`
`7 FOREIGN_priority is claimed under 35 USC 119(aa-(d)/365(b) based on the following applications:
`
`
`
`
`
`
`
`
`
`8.
`
`(No.) Certified copy/copies: |:| attached;l:] previously filed on
`
`in US Application No.
`
`9. Small Entity Status: E is NOT claimed I:I i_s claimed.
`
`provisional, nonprovisional and/or PCT international application)
`
`Application/Patent No.
`
`Filing Date
`
`Application/Patent No.
`
`Filing Date
`
`
`
`
`
`
`
`
`
`10. E] See NONPUBLICATION REQUEST under Rule 213(a) attached.
`11. DOMESTIC/INTERNATIONAL priority is claimed under 35 USC 1.19(e)/120/365(c) based on the following
`
`
`
`
`
`
`(1) 09/987 723
`
`(2) 6415 280
`
`11/15/2001
`
`(3) 5, 978 791
`
`04/01/1999
`
`(4) 08/425 160
`
`10/24/1997
`
`04/11/1995
`
`12. E] This application is being filed under Rule 53(b)(2) since an inventor is named in the enclosed Declaration who
`was not named in the prior application.
`
`13.
`
`IX] Attached: Information Disclosure Statement and eighteen (18) USPTO Form 1449’s.
`
`14. I] Preliminary Amendment Attached.
`
`GOOG-1020-Page 1 of 114
`
`GOOG-1020-Page 1 of 114
`
`

`

`-.
`
`‘
`
`New US. Continuation Application
`|nventor(s): FARBER, David A. et al.
`Title:
`ENFORCEMENT AND POLICIKNG OF LICENSED
`CONTENT USING CONTENT-BASED IDENTIFIERS
`Date: December 22, 2004
`
`.
`
`.
`
`Docket No.: 2618-0003
`
`THE FOLLOWING FILING FEE IS BASED ON CLAIMS AS FILED LESS ANY ABOVE CANCELLED
`
`_
`
`Large [Small
`
`18. Basic Filing Fee ................................... Regular Utility Application
`Design Application
`
`
`
`
`
`$790 / $395
`$350 / $175
`
`$ 790
`
`
`
`
`
`
`19 TotaICIaIms
`”la/$9
`20- Ind-Claims --—- X$88I$44 _
`21. Ifaany proper multiple dependent claim (ignore improper) is present, add -—
`
`
`(Leave this line b|_aflk if thisIs a r_eissue application)
`
`
`
`
`
`|f"non-Eng|ish" box 2Is X’d add Rule 17k() processing fee ——
`23.
`24 If"assignment" box 8 isX’d add recording fee —-
`
`
`25 [:I Attached Is a PetItIon/Fee under Rule No —_
`
`
`26. Total Fee Enclosed:
`$2,086
`
`27. C] Please charge the total fee to our deposit account below under the stated order no.:
`Our Deposit Account No.: 501860.
`
`CHARGE STATEMENT: 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 (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 not authorize charge of the issue fee until/unless an issue fee transmittal form is filed.
`
`CUSTOMER NUMBER
`
`042624* Registration No.: 37,497
`
`Iii
`
`ilil
`
`ill ill
`
`Ill Ill
`
`Davidson Berquist Jackson & Gowdey, LLP
`4501 N. Fairfax Drive; Suite 920
`Arlington, VA 22203
`Main:
`(703) 248-0333
`FAX:
`(703) 248-9558
`
`GOOG-1020-Page 2 of 114
`
`GOOG-1020-Page 2 of 114
`
`

`

`llllllllllllllllllllllllllllllllllllllll122204
`
`O "
`
`o[L
`
`achD
`05
`g:
`V"
`
`g
`*>
`C
`
`IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`REQUEST FOR FILING NATIONAL PATENT APPLICATION
`Under 35 use 111(a) and Rule 53(b) with Signed Declaration
`
`20>
`1blon. Commissioner of Patents
`.0. Box 1450
`
`lexandria, VA 22313-1450
`
`Sir:
`
`Herewith is the PATENT APPLICATION of:
`
`NONPROVISIONAL
`
`NON REISSUE NON PCT NAT PHASE
`
`Atty. Dkt. No.: 2618-0011
`‘
`
`Date: December 22, 2004
`
`
`
` _nventor(s): FARBER,_avidA.-_CHMANRonald D
`
`
`Title'
`CONTENT DELIVERY NETWORK AND ASSOCIATED METHODS AND
`MECHANISMS
`
`Including:
`
`1. Specification: 7_7 pages (only spec. and claims)
`
`2. [:l Specification in non-English language
`
`3.
`
`4.
`
`5.
`
`IX Declaration: E] Original [2 Facsimile/Copy
`
`3b. [Z Abstractl page(s); Q claims
`
`[XI Drawings: §_1_ sheet(s) ofl] informal;
`
`[Z formal size:
`
`[:1 A4
`
`IE 11”
`
`[:1 Attached an Assignment document and Recordation cover sheets. Please return the recorded
`assignment to the undersigned.
`
`
`6. X Prior application is assigned to SAVVISI Inc. by Assignment recorded on December 3 2004' Reel Unknown
`Frame Unknown, and KINETECHI Inc. by Assignment recorded on November 15, 2001; Reel 012313/Frame
`04___4_6.
`
`
`
`7 FOREIGN_priority is claimed under 35 USC 119(aa-(d)/365(b) based on the following applications:
`
`
`
`
`
`
`
`
`
`8.
`
`(No.) Certified copy/copies: |:| attached;l:] previously filed on
`
`in US Application No.
`
`9. Small Entity Status: E is NOT claimed I:I i_s claimed.
`
`provisional, nonprovisional and/or PCT international application)
`
`Application/Patent No.
`
`Filing Date
`
`Application/Patent No.
`
`Filing Date
`
`
`
`
`
`
`
`
`
`10. E] See NONPUBLICATION REQUEST under Rule 213(a) attached.
`11. DOMESTIC/INTERNATIONAL priority is claimed under 35 USC 1.19(e)/120/365(c) based on the following
`
`
`
`
`
`
`(1) 09/987 723
`
`(2) 6415 280
`
`11/15/2001
`
`(3) 5, 978 791
`
`04/01/1999
`
`(4) 08/425 160
`
`10/24/1997
`
`04/11/1995
`
`12. E] This application is being filed under Rule 53(b)(2) since an inventor is named in the enclosed Declaration who
`was not named in the prior application.
`
`13.
`
`IX] Attached: Information Disclosure Statement and eighteen (18) USPTO Form 1449’s.
`
`14. I] Preliminary Amendment Attached.
`
`GOOG-1020-Page 3 of 114
`
`GOOG-1020-Page 3 of 114
`
`

`

`-.
`
`‘
`
`New US. Continuation Application
`|nventor(s): FARBER, David A. et al.
`Title:
`ENFORCEMENT AND POLICIKNG OF LICENSED
`CONTENT USING CONTENT-BASED IDENTIFIERS
`Date: December 22, 2004
`
`.
`
`.
`
`Docket No.: 2618-0003
`
`THE FOLLOWING FILING FEE IS BASED ON CLAIMS AS FILED LESS ANY ABOVE CANCELLED
`
`_
`
`Large [Small
`
`18. Basic Filing Fee ................................... Regular Utility Application
`Design Application
`
`
`
`
`
`$790 / $395
`$350 / $175
`
`$ 790
`
`
`
`
`
`
`19 TotaICIaIms
`”la/$9
`20- Ind-Claims --—- X$88I$44 _
`21. Ifaany proper multiple dependent claim (ignore improper) is present, add -—
`
`
`(Leave this line b|_aflk if thisIs a r_eissue application)
`
`
`
`
`
`|f"non-Eng|ish" box 2Is X’d add Rule 17k() processing fee ——
`23.
`24 If"assignment" box 8 isX’d add recording fee —-
`
`
`25 [:I Attached Is a PetItIon/Fee under Rule No —_
`
`
`26. Total Fee Enclosed:
`$2,086
`
`27. C] Please charge the total fee to our deposit account below under the stated order no.:
`Our Deposit Account No.: 501860.
`
`CHARGE STATEMENT: 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 (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 not authorize charge of the issue fee until/unless an issue fee transmittal form is filed.
`
`CUSTOMER NUMBER
`
`042624* Registration No.: 37,497
`
`Iii
`
`ilil
`
`ill ill
`
`Ill Ill
`
`Davidson Berquist Jackson & Gowdey, LLP
`4501 N. Fairfax Drive; Suite 920
`Arlington, VA 22203
`Main:
`(703) 248-0333
`FAX:
`(703) 248-9558
`
`GOOG-1020-Page 4 of 114
`
`GOOG-1020-Page 4 of 114
`
`

`

`APPLICATION UNDER UNITED STATES PATENT LAWS
`
`Attorney Docket:
`
`2618-001 1
`
`Invention:
`
`CONTENT DELIVERY NETWORK AND ASSOCIATED METHODS AND
`MECHANISMS
`
`Inventor(s):
`
`FARBER, David A.
`
`LACHMAN, Ronald D.
`
`
`
`
`
`
`
`
`
`
`Davidson Berquist Jackson & Gowdey, LLP
`4501 North Fairfax Drive, Suite 920
`
`(703)248-9558 Fax
`
`Arlington, VA 22203
`(703) 248-0333 Phone
`
`This is a:
`
`E]
`
`Provisional Application
`
`El
`
`IX
`
`Regular Utility Application
`
`Continuing Application
`[Z] The contents of the parent are
`incorporated by reference
`
`D PCT National Phase Application
`
`[:I Design Application
`
`E]
`
`Reissue Application
`
`El
`
`Plant Application
`
`GOOG-1 020-Page 5 of 114
`
`GOOG-1020-Page 5 of 114
`
`

`

`CONTENT DELIVERY NETWORK AND ASSOCIATED METHODS
`
`AND MECHANISMS
`
`-
`
`RELATED APPLICATIONS
`
`[0001]
`
`This is a continuation of and claims priority to co-pending
`
`application no. 09/987,723, filed November 15, 2001 (allowed), (the contents of
`
`which are hereby incorporated herein by reference), which is a continuation of
`
`‘ application NO. 09/283,160, filed April 1, 1999, now US. Patent No. 6,415,280,
`
`which is a division of application Ser. No. 08/960,079, filed Oct. 24, 1997, now
`
`US. Pat. No. 5,978,791 filed Oct. 24, 2001 which is a continuation of Ser. NO.
`
`08/425,160, filed Apr. 11, 1995, now abandoned.
`
`BACKGROUND OF THE INVENTION
`
`1. FIELD OF THE INVENTION
`
`[0002] 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
`‘
`. 1"'.".;.— L.
`.
`
`the data‘items.‘
`
`2. BACKGROUND OF THE INVENTION
`
`[0003] 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.
`
`[0004] 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.
`
`'
`
`2618-0011
`
`_ 1 _
`
`GOOG-1020-Page 6 of 114
`
`GOOG-1020-Page 6 of 114
`
`

`

`[0005] In all but the most primitive operating systems, users and programs are able
`to create and use collections ofnamed 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 sequenceof names, or
`
`a so-called pathname, which defines a path through the directories to a particular
`
`data item (file or directory).
`
`I
`
`[0006] 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.
`
`[0007] 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.
`
`[0008] 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'pr—ocess'ing" 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.
`.
`[0009] 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 specificcontext.‘For
`' instance, the file identified by a particular file name can only be determined when
`
`26l8-0011
`
`- 2 ._
`
`GOOG-1020-Page 7 of 114
`
`GOOG-1020-Page 7 of 114
`
`

`

`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 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.
`
`[0010] 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.
`
`[0011] 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.
`
`[0012] 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.
`
`[0013] 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
`
`2618-001]
`
`GOOG-1020-Page 8 of 114
`
`GOOG-1020-Page 8 of 114
`
`

`

`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).
`
`c
`
`'
`
`[0014] 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.
`
`[0015] In some data processing systems in which several processors areconnected
`
`.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
`
`1 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. Theneed to keep- the cache
`
`synchronized or reload it adds significant overhead to, existing caching .
`
`mechanisms.
`
`[0016] In View of the above andother 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 onany sort of .
`
`' context.
`
`’
`
`[0017] It is further desirable to have a mechanism forredubing multiple copies of
`
`data items in a data processing system and to have a mechanism which enables the
`
`2618-0011
`
`- 4 _
`
`.
`
`_
`
`GOOG-1020-Page 9 of 114
`
`GOOG-1020-Page 9 of 114
`
`

`

`‘ identification of identical data items so as to reduce multiple copies. It. is further
`
`desirable to determine whether two instances of a data item arein fact the same
`
`, data item, and to perform various other systems' fimctions and applications on data
`
`items without relying on any context information or properties of the data item.
`
`[0018] It is also desirable to provide such a mechanism in such a way asto 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.
`
`SUMMARY OF THE INVENTION
`
`[0019] 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 datain the data item and only on the data1n 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.
`A
`[0020] 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.
`.
`_[0021] Using the method or apparatus ofthe present invention, 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 operation ofat least some or all
`of the following features:
`I
`I
`I.
`i
`I
`.[0022] the system stores at most one copy of any data item at a given location, i
`“even when multiple data names in the system refer to the same contents;
`[0023] thesystem avoids copying data from source to destination locations when
`
`I
`
`the, destination locations already have the data;
`
`2618-0011
`
`GOOG-1020-Page 10 of 114
`
`GOOG-1020-Page 10 of 114
`
`

`

`[0024] 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;
`
`[0025] the system caches data items from a server, so that only the most recently
`
`accessed data items need be retained;
`
`[0026] when the system is being used to cache data items, problems of maintaining
`
`cache consistency are avoided;
`
`[0027] 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;
`i
`
`[0028] the system automatically archives data items as they are created or
`
`modified;
`
`1
`
`[0029] 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;
`
`[0030] the system can efficiently record and preserve any collection of data items;
`
`[0031] the system can efficiently make a copy of any collection bf data items, to
`support a version control mechanism for groups of the data items;
`
`[0032] 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;
`
`[0033] 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
`I
`
`independent of other properties of the data items such as their'name, location, and
`
`date of creation;
`
`[0034] the system allows closely related sets of data items, such as matching or
`' corresponding directories on disconneéted computers, to be periodically
`i
`resynchronized with one another;
`‘
`i
`I
`1
`
`I
`
`[0035] 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;
`
`2618-0011
`
`- 6 _
`
`GOOG-1020-Page 11 of 114
`
`GOOG-1020-Page 11 of 114
`
`

`

`[0036]‘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;
`
`[0037] 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.
`
`[0038] 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
`
`i 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.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`, [0039], Figures 1(a) and 1(b) depict a typical data processing system in which a
`
`preferred embodiment of the present invention operates;
`
`‘[0040] Figure 2 depicts a hierarchy of data items stored at any location in such a
`
`‘
`
`data processing system;
`V [0041] Figures 3-9 depict data structures used to implement anembodiment of the
`present invention; and
`i
`I
`
`'
`
`1 [0042] Figures 10(a)-28 areflow charts depicting operation of various aspects of
`
`the present invention.
`
`1
`
`I DETAILED DESCRIPTION OF THE PRESENTLY PREFERRED
`
`EXEMPLARY EMBODIMENTS
`
`,
`
`[0043] -An embodiment of the present invention is now. described with reference to
`
`a typical data'processing system 100, which, with reference to FIGS. 1(a) and 1(b),
`
`includes one or more processors (or computers) 102 and various storage devices
`
`104 connected in Some way, for example by a bus'106.‘
`
`2618-0011
`
`GOOG-1020-Page 12 of 114
`
`GOOG-1020-Page 12 of 114
`
`

`

`[0044] Each processor 102 includes a CPU 108, a memory. 110 and one or more
`
`local storage devices 112. The CPU.108, memory 1.10, 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.
`
`[0045] 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 otherproceSSOrs as i
`
`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 aets'as a server processor. In
`other words, there is no hierarchy imposed on or required ofprocessors 102.
`[0046] In a multiprocessor system, the processors 102 may be homogeneous or
`"heterogeneous. Further, in a multiprocessor data processing system 100, Some or
`
`all of the processors 102 may be disconnected from the network of processors for
`' periods Of time. ’Such disconnection may be partrof the norrrial operation of the
`
`system ‘100 or it may be because a particular processor 102 is in need of repair.
`[0047] 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,_‘segmer_1ts_,yjandv
`
`the like, For example, with reference to FIG, 2,,the data items on a particular ,
`
`:
`
`processor 102 may be organized or structured as a file system ,1 1,6 which. ~
`
`_
`
`comprises regions 11'?, each of which comprises directories 118, each of which
`
`~ can contain other directories 118 or files 120. Each file-1‘20 being made up of one
`
`or more data segments 122.
`
`.
`
`2618-0011
`
`- 8 —
`
`.
`
`, _-
`
`GOOG-1020-Page 13 of 114
`
`GOOG-1020-Page 13 of 114
`
`

`

`‘ [0048] .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 elementbeing 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.)
`
`[0049] ,In other words, a file system 116 is a collection of directories 118. A
`directory 118 is a collection of namedfiles 120--both data files 120 and other ‘
`
`directory files 118. A file 120 is a named data item which is either a data file
`
`(which may be simple or compound) or a directory file 118. A simple file 120
`
`consists of a single data segment 122. A compound file 120 consists of a sequence
`
`of data segments 122. A data segment 122 is a fixed sequence of bytes. An
`
`important property of any data segment is its size, the number of bytesvin the
`sequence.
`I
`
`‘
`
`[0050] 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 file system 116. For instance, a file system 116 may span several storage devices
`' 104.
`7
`
`[0051] 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.
`[0052} In the following, the term "location", with respect to a data processing
`
`'
`
`system 100, refersto any of a particular processor 102 in the system, a memory of
`
`a particular processor, a storage device, a removablestOrage medium (such as a.
`
`floppy disk or compact disk), or any other physical location in the system. The .
`
`term "local" with respect to a particular processor 102 refers to the memory and
`
`storage devices of that particular processor.
`
`26l8-OOll
`
`_ 9 -
`
`GOOG-1020-Page 14 of 114
`
`GOOG-1020-Page 14 of 114
`
`

`

`[0053] In the following, the terms "True Name", "dataidentity" 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.
`' [0054] _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.
`
`[0055] The processes and mechanisms (services) provided in this embodiment are
`
`grouped into the following categories: primitive mechanisms, operating system
`
`mechanisms, remote mechanisms, background mechanisms, and extended
`
`mechanisms.
`
`[0056]_Primitive mechanisms provide fimdamental capabilities used to support
`
`other mechanisms. The following primitive mechanisms are described: '
`
`I
`
`1. Calculate True Name;
`
`2. Assimilate Data Item;
`
`3. True File;
`
`4. Get True Name from Path;
`
`5. Link path to True Name;
`
`6. Realize True File from Location;
`
`7. Locate Remote File;
`
`8. Make True File Local;
`
`9. Create Scratch File;
`
`10. Freeze Directory;
`
`11. Expand Frozen Directory;
`
`12. Delete True File;
`
`13. Process Audit File Entry; '
`
`V
`
`'
`
`'
`
`2618-001]
`
`_ 10-
`
`GOOG-1020-Page 15 of 114
`
`GOOG-1020-Page 15 of 114
`
`

`

`14. Begin Grooming;
`
`15. Select For Removal; and '
`
`16. End Grooming.
`
`[0057] Operating system mechanisms provide typical familiar file system
`
`mechanisms, while maintaining the data structures required to offer the.
`
`'mechanisms of the, present invention. Operating system mechanisms arepdesigned
`
`to augment existing operating systems, and in this way tomake the present
`
`_
`
`invention compatible with, and generally transparent to, existing applications. The
`
`following operating system mechanisms are described:
`
`1. Open File;
`
`2. Close File;
`
`3. Read File;
`
`4. Write File;
`
`5.
`
`Delete File or Directory;
`
`. Copy File or DireCtory;
`
`. Move File or Directory;
`
`. Get File Status; and
`
`6 7 8
`
`9. Get Files in Directory.
`
`[0058] Remote mechanisms are used by the operating system in responding to
`
`requests from other processors. These mechanisms enable the capabilities of the
`
`present invention in a peer-to-peer network mode of operation. ‘The- following
`
`remote mechanisms are described:
`
`1.
`
`2.
`
`3.
`
`4.
`
`5.
`
`6.
`
`7.
`
`Locate True File;
`Reserve True File;
`
`Request True File;
`
`Retire True File;
`
`Cancel Reservation;
`
`Acquire'True File;
`
`Lock Cache;
`
`2618-0011
`
`-11_
`
`GOOG-1020-Page 16 of 114
`
`GOOG-1020-Page 16 of 114
`
`

`

`8. Update Cache; and
`
`9. Check Expiration Date.
`
`‘ [0059] Background mechanisms are intended to run occasionally and at a low
`
`priority; These provide automated management capabilities with respect to the
`
`present invention. The following background mechanisms are described:
`
`1. Mirror True File;
`
`2. Groom Region;
`
`3. Check for Expired Links; and
`
`4. Verify Region; and
`
`5. Groom Source List.
`
`'[0060]'Extended mechanisms run within application .programs over the operating
`
`system. These mechanisms provide solutions to specific problems and
`
`applications. The following extended mechanisms are described:
`
`1. Inventory Existing Directory;
`
`2. Inventory Removable, Read-only Files;
`
`3. Synchronize directories;
`
`4. Publish Region;
`
`5. Retire DirectOry;
`
`6. Realize Directory at location;
`
`7. Verify True File;
`
`8. Track for accounting purposes; and
`
`9. Track for licensing purposes.
`
`[0061], The file system herein described maintains sufficient information to ‘
`
`provide a variety of mechanisms not ordinarily offered by an operating system,
`
`some of which are listed and described here. Various processing performed by this ‘
`
`embodiment of the present invention will now be described in greater detail.
`
`.
`
`[0062] In some embodiments, some files 120. in a data processing system 100 do
`
`' not have True Names because they have been recently received or created or
`
`modified, .and thus their True Names have not yet beencomputed. A file that does.
`
`2618-0011
`
`_ 12 _
`
`GOOG-1020-Page 17 of 114
`
`GOOG-1020-Page 17 of 114
`
`

`

`not .yet'have a True Name is called a scratch file. The process of assigning a True
`
`. Name to a file is referred to as assimilation, and is described later. Note that a
`
`scratch file may have a user provided name.
`
`[0063] SOme of the processing performed by the pr