Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
2001-05-18
2004-02-24
Ton, David (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
C714S808000
Reexamination Certificate
active
06697996
ABSTRACT:
BACKGROUND
The present invention relates generally to packet data transmission systems and method, and more particularly, to a multi-dimensional packet recovery system and method for restoring lost packets in a network environment.
U.S. Pat. No. 5,432,787 entitled “Packet data transmission system with adaptive data recovery method”, assigned to the assignee of the present invention discloses a packet communication system that uses a recovery method in which a “parity” packet is added to a transmitted packet string for each span (sequence) of K data packets. The parity packet's data field is comprised of the modulo-2 sum of the respective data bits of all of the K packets in the span.
More particularly, this packet communication system transmits a stream of L data packets with at least one parity packet transmitted as an L+1
th
packet. The parity packet comprises at least N data segments, each i
th
data segment being the modulo-2 sum of all identically positioned data segments in the stream of L packets. A node includes adaptive packet stream transmission apparatus which comprises a packet queue for holding a series of packets ready for transmission to a destination node. The adaptive packet stream transmission mechanism further includes modulo-2 sum circuitry for deriving a parity packet for each L transmitted data packets.
Transmission control circuitry selectively enables transmission of a parity packet after each L data packets have been transmitted. A processor in the node controls the transmission control circuitry to vary the value of L in accordance with a determined network metric. The network metric may indicate a level of network congestion, with the processor increasing the value of L if the network metric manifests a lessened network congestion, and vice versa. The processor may vary the value of L in accordance with a data error rate metric.
However, the system disclosed in U.S. Pat. No. 5,432,787 does not address recovery of a multi-dimensional array of packets. It is therefore an objective of the present invention to provide for multi-dimensional packet recovery systems and methods that recover lost transmitted packets and packets containing transmission errors.
SUMMARY OF THE INVENTION
To accomplish the above and other objectives, the present invention provides for multi-dimensional packet recovery systems and methods that permit recovery of lost transmitted packets and packets containing transmission errors. The packet recovery system and method transmits a multi-dimensional array comprising rows, columns and hyperdimensional volumes of data packets between a source node and one or more destination nodes. The present invention improves upon the teachings of U.S. Pat. No. 5,432,787.
A two-dimensional packet array is exemplary of the multi-dimensional array with no loss of generality. Parity packets are derived from source packets on a linear array of packets. A span of packets is defined as a packet block. Each of the first data bits of the packets in the packet block are modulo-2 added to form a parity bit. This is the first bit in the parity packet of the packet block. Similarly, all corresponding 2nd through k bits of the member packets are modulo-2 added to form the second through kth bits in the parity packet. In the two-dimensional packet array, a span of packets may comprise a row of length R packets. Many rows are assembled to form a rectangular block of C rows. Parity packets are computed on the columns of packets where each column is treated as a span of packets of length C. A final parity packet is computed on the parity packets and completes the rectangular array.
The blocks are transmitted over a traditional network with erasures and bit errors. The receiver establishes block synchronization and stores the array of packets constituting the received block. Where errors and lost packets are detected (through CRC and missing sequenced packets) the receiver inserts a place holder for each failed packet. For all rows of packets with a failed packet, a parity packet for each linear span is calculated and is used to replace the failed packet. The procedure is then repeated for each columnar span. This process is iterated among rows and columns until all possible failed packets are recovered and the block of packets are output. The present invention implements what may be referred to as product codes with “turbo” packet recovery.
Certain arrays of failed packets are unrecoverable using the above-described process. Various arrangements of packet interleaving may be applied in the transmission sequencing so that bursts of lost packets due to a network node failure may be spread over a large number of packet blocks. The lost packets are caused to be “randomized”, thus allowing the block packet recovery process to succeed.
The system and method provides for recovery of missed or failed packets of a multi-dimensional packet array in a data packet switching network. The system and method provide for recovery of failed packets resulting from transmission of packets over the data packet network without the use of retransmission (ARQ) protocols.
The present invention extends the recovery process disclosed in U.S. Pat. No. 5,432,787 to multi-dimensional arrays of packets. The present invention recovers multiple failed packets per “span”, and is useful at higher failure rates than the technique disclosed in U.S. Pat. No. 5,432,787. The present invention thus extends the basic principles of forward packet recovery to higher dimensional blocks of packets. A recursive recovery method is employed in the present invention to recover multiple lost packets of a group, where such multiple losses may be unrecoverable using the techniques disclosed in U.S. Pat. No. 5,432,787.
REFERENCES:
patent: 5630151 (1997-05-01), Muramatsu et al.
patent: 6289013 (2001-09-01), Lakshman et al.
patent: 6574213 (2003-06-01), Anandakumar et al.
patent: 6594268 (2003-07-01), Aukia et al.
Float Kenneth W.
Lockheed Martin Corp.
Ton David
LandOfFree
Multi-dimensional packet recovery system and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-dimensional packet recovery system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-dimensional packet recovery system and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3340151