Dynamic magnetic information storage or retrieval – Automatic control of a recorder mechanism – Controlling the record
Reexamination Certificate
1999-03-12
2001-07-31
Peikari, B. James (Department: 2752)
Dynamic magnetic information storage or retrieval
Automatic control of a recorder mechanism
Controlling the record
C360S072100, C360S077070, C360S077060, C360S049000, C360S070000, C360S050000
Reexamination Certificate
active
06268975
ABSTRACT:
TECHNICAL FIELD
The present invention relates to data storage and in particular to methods and apparatus for locating target positions in stored data.
BACKGROUND ART
It is well known for data storage apparatus, such as a tape drive, to compress incoming data prior to storing the data to a backup medium, such as tape. An example of such a tape drive is one conforming to the DDS (Digital Date Storage) format, defined in ISO/IEC Standard 10777:1991 E. As described in detail in EP 0 464 190, a DDS tape drive encodes received data records, by compressing the data records using a codeword based algorithm, and stores the compressed data codewords into fixed length groups.
One characteristic of a codeword based compression algorithm is that data can only be decompressed if decompression begins from exactly the same position in an encoded data stream as where the compression began. The position in the data stream where both compression and decompression must begin is sometimes called an access point. Codeword algorithms of this type include the well-known LZ (Lempel-Ziv) algorithms, which will not be described in detail herein. Although not considered herein, an encoded data stream might comprise encrypted data rather than compressed data. However, the same requirements for an access point apply.
Prior to compressing the data, a DDS drive strips out all host data structure information, such as file mark and set mark information, received from the host computer system. The effect of this is that the compressed data stream in a group only contains host data.
Typically, hosts can issue commands to a tape drive to ‘space’ to, or ‘locate’, different positions in the encoded data stream. Such an operation is conveniently supported in a DDS drive by the provision of index information for each group, in the form of a block access table (BAT). The BAT of includes a series of entries, each one corresponding to a respective record, file mark or set mark in the group. Each entry corresponding to a record includes the length in bytes of the respective compressed record data in the group. In effect, the BAT contains a logical map of the data in the group, which provides a derivable byte position of any record boundary, file mark or set mark within the group. Therefore, a DDS tape drive can move to any valid logical target position within the encoded data stream simply by using the BAT to calculate the byte position of the target and decoding from the access point to that byte position.
In the co-pending, commonly assigned U.S. patent application Ser. No. 09/182,308 (filed on Oct. 30, 1998), entitled Data Encoding Method and Apparatus, the contents of which are hereby incorporated herein by reference, there is proposed a novel data encoding scheme suitable for tape drives. In the scheme, the requirement to have a BAT, or equivalent, is removed by embedding special codewords representative of host data structure information into the encoded data stream itself. In particular, special codewords are reserved to represent file marks and ends of records in an encoded data stream. The removal of the need for a BAT enables the encoding pipeline of a tape drive implementing the new scheme to operate at far higher data rates, since there is no requirement to generate and update a BAT.
The novel data encoding scheme, in common with DDS drives, implements a codeword-based compression algorithm, which allows data to be read only in the forward direction starting from an access point.
The lack of a BAT in the applicant's new scheme, however, presents a problem as far as moving to target positions is concerned. The lack of a BAT means it is not possible to predetermine the byte position of a target in a stream of encoded data. This is particularly problematic when a target position is specified as being upstream (or backwards) in the encoded data stream.
DISCLOSURE OF THE INVENTION
The present invention is aimed at providing a convenient solution to the problem of moving backwards, or in upstream direction, to a target position within encoded data, where the data can only be read in the forwards, or downstream, direction from an access point.
Accordingly, the present invention provides a method of controlling data storage apparatus to locate a target position upstream of a current position within an encoded data stream, the encoded data stream being readable only in the downstream direction from an access point and comprising a sequence of codewords including data codewords representing encoded blocks of user data and structure codewords representing the logical partitioning of the blocks of user data within the encoded data stream,
wherein the target position is a number of structure codewords upstream from the current position and at, or a number of structure codewords downstream from, the access point the method including the steps of:
from the current position, moving to the access point upstream of the target position;
from the access point, decoding the encoded data in the downstream direction until the structure codeword at the target position is encountered or until an unexpected structure codeword is encountered; and
arranging the apparatus to re-encounter said structure codeword first in any subsequent data read operation.
In accordance with a second aspect, the present invention provides tape drive apparatus comprising:
an interface arranged to receive a host command to locate a target position within an encoded data stream;
a data store arranged to store at least some of the encoded data stream, the encoded data stream being readable only in a downstream direction from an access point which is upstream of the target position and comprising a sequence of codewords including data codewords representing encoded blocks of user data and structure codewords representing the logical partitioning of the blocks of user data within the encoded data stream; and
a decoder arranged to locate the access point and decode the stored data in the main memory downstream from the access point until the target position is encountered or until an unexpected structure codeword is encountered, the decoder also being arranged to re-encounter said structure codeword first in any subsequent data read operation.
REFERENCES:
patent: 3852814 (1974-12-01), Johnson et al.
patent: 4691250 (1987-09-01), Ookawa
patent: 4947367 (1990-08-01), Chang et al.
patent: 5163136 (1992-11-01), Richmond
patent: 5319503 (1994-06-01), Hasegawa et al.
patent: 5335122 (1994-08-01), An
patent: 5394280 (1995-02-01), Chliwnyj et al.
patent: 5566032 (1996-10-01), Cleveland et al.
patent: 6118605 (2000-09-01), Call et al.
patent: 0482297 A2 (1992-04-01), None
patent: WO 93/0551 (1993-03-01), None
Hewlwtt-Packard Company
Lowe Hauptman & Gilman & Berner LLP
Peikari B. James
LandOfFree
Tape drive utilizing encoded file markers to locate target... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Tape drive utilizing encoded file markers to locate target..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tape drive utilizing encoded file markers to locate target... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2511943