Recovery of √n bytes of data using Backtracking Algorithm
Assume that a busy server is transferring files across the
network, and during the transfer certain data present in the file is
replaced with erroneous data. If the client node or receiver node does
not have any technique to detect errors, then it would process the
erroneous data got, and provide unexpected results. Now assume that
the client just has a error detecting technique, it would be able to
detect if errors were present in the received file or not, but will not be
able to correct it, and in case it wants the correct data it will have to
request the busy server to send the file again, this in turn leads to
wastage of precious server cycles and bandwidth.
Hence an efficient and effective error detection algorithm
is required to overcome the above mentioned problems. Proposed
algorithm can recover the erroneous data. It can be applied to all kind
of data files.
Here we divide the input data into a 2D square matrix,
calculate xor value of all rows, and columns present in the matrix.
This information is transferred along with the actual data, and at
receiver end we use backtracking algorithm to recover erroneous data
if any. It contains three stages, encoding of the data, testing for
errors, decoding the data.
Before sending any file across the network it is encoded by
adding header to the actual data, header contains the necessary
information required for backtracking algorithm. The output file
received is tested for errors and if errors are found it is corrected
using backtracking algorithm and the resultant data file is decoded to
obtain the original data. If the file size is of n bytes then the
backtracking algorithm can correct upto √n bytes of the data.
Keywords: Ex-OR, RAID(Redundant Array of Inexpensive Disks), BackTracking Algorithm, Error Detection, Error Recovery, Repetition schemes, Checksum, Cyclic redundancy checks, Hamming Code, Automatic Repeat-Request
Download Full-Text
