Method and apparatus for N+1 packet level mesh protection

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
0Forward
Citations 
0
Petitions 
6
Assignments
First Claim
1. An error correction encoder for encoding message symbols, m_{0 }through m_{N1}, to generate an error correction codeword that includes said message symbols, m_{0 }through m_{N1}, and one or more check symbols, comprising:
 a linear feedback shift register having one or more flipflops to generate said check symbols for said error correction codeword after shifting said message symbols, m_{0 }through m_{N1}, through said linear feedback shift register, wherein each error correction codeword includes said message symbols, m_{0 }through m_{N1}, and said corresponding generated check symbols.
6 Assignments
0 Petitions
Accused Products
Abstract
Methods and apparatus are provided for N+1 packet level mesh protection. An error correction encoder is provided for encoding message symbols, m_{0 }through m_{N1}, to generate a codeword that includes the message symbols, m_{0 }through m_{N1}, and one or more check symbols. The error correction encoder comprises a linear feedback shift register having one or more flipflops to generate the check symbols after shifting the message symbols, m_{0 }through m_{N1}, through the linear feedback shift register. An error correction decoder is also provided for decoding a codeword that includes message symbols, m_{0 }through m_{N1}, and one or more check symbols. The error correction decoder comprises a linear feedback shift register having one or more flipflops to generate an error symbol based on a remainder after shifting the message symbols, m_{0 }through m_{N1}, and the one or more check symbols through the linear feedback shift register.
29 Citations
No References
ENCODING AND DECODING METHOD, AND ENCODING AND DECODING DEVICES WITH A TWOSTAGE ERROR PROTECTION PROCESS  
Patent #
US 20110131474A1
Filed 02/07/2011

Current Assignee
Nokia Solutions and Networks GmbH Co. KG

Sponsoring Entity
Nokia Solutions and Networks GmbH Co. KG

Erasure forecasting and errorcorrection strategies  
Patent #
US 8,046,659 B1
Filed 04/13/2010

Current Assignee
Marvell International Limited

Sponsoring Entity
Marvell International Limited

FEC ARCHITECTURE FOR STREAMING SERVICES INCLUDING SYMBOL BASED OPERATIONS AND PACKET TAGGING  
Patent #
US 20100050057A1
Filed 10/27/2009

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

METHODS OF DATA HANDLING  
Patent #
US 20100306626A1
Filed 08/09/2010

Current Assignee
Ovonyx Memory Technology LLC

Sponsoring Entity
Ovonyx Memory Technology LLC

Symbol Error Correction by Error Detection and Logic Based Symbol Reconstruction  
Patent #
US 20080104479A1
Filed 01/04/2008

Current Assignee
Ternarylogic LLC

Sponsoring Entity


BCH forward error correction decoder  
Patent #
US 7,447,982 B1
Filed 03/30/2001

Current Assignee
ICONVERSE INC.

Sponsoring Entity
ICONVERSE INC.

Encoding and Decoding Method, and Encoding and Decoding Devices with a TwoStage Error Protection Process  
Patent #
US 20080320358A1
Filed 06/29/2005

Current Assignee
Nokia Siemens Networks GmbH Company KG

Sponsoring Entity
Nokia Siemens Networks GmbH Company KG

Physical layer repeater with selective use of higher layer functions based on network operating conditions  
Patent #
US 7,230,935 B2
Filed 01/26/2006

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Forward error correction system for packet based data and real time media, using crosswise parity calculation  
Patent #
US 6,243,846 B1
Filed 04/17/1998

Current Assignee
Hewlett Packard Enterprise Development LP

Sponsoring Entity
3Com Corporation

ATM communications system and ATM testing method  
Patent #
US 6,487,215 B1
Filed 03/11/1999

Current Assignee
OKI Electric Industry Company Limited

Sponsoring Entity
OKI Electric Industry Company Limited

Packet stream arrangement in multimedia transmission  
Patent #
US 20060109805A1
Filed 11/19/2004

Current Assignee
Nokia Corporation

Sponsoring Entity
Nokia Corporation

High performance CRC calculation method and system with a matrix transformation strategy  
Patent #
US 20050149818A1
Filed 12/17/2003

Current Assignee
Macronix International Co. Ltd.

Sponsoring Entity
Macronix International Co. Ltd.

Two stage detector having viterbi detector matched to a channel and post processor matched to a channel code  
Patent #
US 20040181732A1
Filed 03/04/2004

Current Assignee
Maxtor Corporation

Sponsoring Entity


Forward error correction (FEC) based on SONET/SDH framing  
Patent #
US 6,829,741 B1
Filed 10/23/2001

Current Assignee
Centillium Communications Incorporated

Sponsoring Entity
Centillium Communications Incorporated

Error correction coding and decoding method, and circuit using said method  
Patent #
US 6,336,203 B1
Filed 03/26/1998

Current Assignee
Mitsubishi Electric Corporation

Sponsoring Entity
Mitsubishi Electric Corporation

Programmable, reconfigurable DSP implementation of a ReedSolomon encoder/decoder  
Patent #
US 6,385,751 B1
Filed 12/15/1999

Current Assignee
Texas Instruments Inc.

Sponsoring Entity
Texas Instruments Inc.

Demultiplexing and decoding apparatus for coded audio and video data  
Patent #
US 6,477,185 B1
Filed 09/28/1998

Current Assignee
Renesas Technology Corporation

Sponsoring Entity
Hitachi ULSI Systems Company Limited, Hitachi Ltd.

Forward error correction system for packet based real time media  
Patent #
US 5,870,412 A
Filed 12/12/1997

Current Assignee
Hewlett Packard Enterprise Development LP

Sponsoring Entity


Error correction coding and decoding method, and circuit using said method  
Patent #
US 5,951,708 A
Filed 03/26/1998

Current Assignee
Mitsubishi Electric Corporation

Sponsoring Entity
Mitsubishi Electric Corporation

Dedicated ALU architecture for 10bit ReedSolomon error correction module  
Patent #
US 5,778,009 A
Filed 06/14/1995

Current Assignee
Maxtor Corporation

Sponsoring Entity
Quantum Corporation

Global parity symbol for interleaved reedsolomon coded data  
Patent #
US 5,642,366 A
Filed 07/05/1994

Current Assignee
PMCSierra Incorporated

Sponsoring Entity
Adaptec Incorporated

Apparatus and method for error detection and correction in radio frequency identification device  
Patent #
US 5,479,416 A
Filed 09/30/1993

Current Assignee
Round Rock Research LLC

Sponsoring Entity
Micron Semiconductor Products Incorporated

Coding and decoding method  
Patent #
US 4,897,839 A
Filed 02/05/1988

Current Assignee
Mitsubishi Electric Corporation

Sponsoring Entity
Mitsubishi Electric Corporation

Multiple error trapping  
Patent #
US 4,843,607 A
Filed 12/17/1987

Current Assignee
Eastman Kodak Company

Sponsoring Entity
Eastman Kodak Company

Method and a system for multiple error detection and correction  
Patent #
US 4,782,490 A
Filed 03/16/1987

Current Assignee
GT Technologies

Sponsoring Entity
GT Technologies

Bit serial encoder  
Patent #
US 4,410,989 A
Filed 12/11/1980

Current Assignee
CYCLOTOMICS INC.

Sponsoring Entity
CYCLOTOMICS INC.

REVERSE CYCLIC CODE ERROR CORRECTION  
Patent #
US 3,811,108 A
Filed 05/29/1973

Current Assignee
Honeywell Information Systems Inc.

Sponsoring Entity
Honeywell Information Systems Inc.

MULTICHANNEL SHIFT REGISTER  
Patent #
US 3,703,705 A
Filed 12/31/1970

Current Assignee
International Business Machines Corporation

Sponsoring Entity
International Business Machines Corporation

BURST ERROR DETECTOR  
Patent #
US 3,465,287 A
Filed 05/28/1965

Current Assignee
Joseph C. Kennedy, John H. Sorg Jr

Sponsoring Entity
Joseph C. Kennedy, John H. Sorg Jr

4 Claims
 1. An error correction encoder for encoding message symbols, m_{0 }through m_{N1}, to generate an error correction codeword that includes said message symbols, m_{0 }through m_{N1}, and one or more check symbols, comprising:
a linear feedback shift register having one or more flipflops to generate said check symbols for said error correction codeword after shifting said message symbols, m_{0 }through m_{N1}, through said linear feedback shift register, wherein each error correction codeword includes said message symbols, m_{0 }through m_{N1}, and said corresponding generated check symbols.
 2. An error correction encoder for encoding message symbols, m_{0 }through m_{N1}, to generate an error correction codeword that includes said message symbols, m_{0 }through m_{N1}, and one or more check symbols, comprising:
a linear feedback shift register having one or more flipflops to generate said check symbols for said error correction codeword after shifting said message symbols, m_{0 }through m_{N1}, through said linear feedback shift register, wherein a payload containing said message symbols, m_{0 }through m_{N1}, comprises a symbolwise exclusive or (XOR) of said message symbols, m_{0 }through m_{N1}.
 3. An error correction decoder for decoding an error correction codeword that includes message symbols, m_{0 }through m_{N1}, and one or more corresponding check symbols, comprising:
a linear feedback shift register having one or more flipflops to generate an error symbol based on a remainder after shifting said message symbols, m_{0 }through m_{N1}, and said one or more check symbols of said error correction codeword through said linear feedback shift register, wherein each error correction codeword includes said message symbols, m_{0 }through m_{N1}, and said one or more corresponding check symbols.
 4. An error correction decoder for decoding an error correction codeword that includes message symbols, m_{0 }through m_{N1}, and one or more check symbols, comprising:
a linear feedback shift register having one or more flipflops to generate an error symbol based on a remainder after shifting said message symbols, m_{0 }through m_{N1}, and said one or more check symbols of said error correction codeword through said linear feedback shift register, wherein said error symbol is said remainder for T equal to one check symbol, where T is a number of protection packets.
1 Specification
This application is a divisional of U.S. patent application Ser. No. 12/565,453, filed Sep. 23, 2009, which is a divisional of U.S. Pat. No. 7,624,333, issued Nov. 24, 2009, each incorporated by reference herein.
The present invention relates generally to failure protection techniques (redundancy) for a packet network, and more particularly, to methods and apparatus for N+1 packet level failure protection techniques.
Failure and error protection techniques are used in a number of communication and storage systems. Failure protection is used to mask the failure of an individual component, by providing other means of regenerating the data stream that was handled by the failed component. Error protection, on the other hand, is typically used to mask bursts of errors caused by noise in the transmission system. For example, error correction codes add one or more redundant bits to a digital stream prior to transmission or storage, so that a decoder can detect and possibly correct errors caused by noise or other interference. In a communication network, for example, failure protection typically involves sending a duplicate copy of the data being protected to the receiver. The receiver then selects the “best” copy of the signal. Unfortunately, this level of redundancy results in 50% of the network bandwidth being wasted. As well, the system does not typically take advantage of the duplicate signal to correct individual errors in the active, or working signal.
Thus, a number of techniques have been proposed or suggested for reducing the bandwidth required for failure protection. One proposed technique employs sharing schemes, where a reserve channel is kept open for a number of working channels. When one of these working channels fails, the reserve channel is invoked and protection occurs. Bidirectional Line Switched Ring (BLSR), One for N (1:N) and Resilient Packet Ring (RPR) fall into this category
Unfortunately, the signaling and operational logistics required to implement shared protection across a real network are prohibitive, and again none of these techniques are able to offer realtime error correction on their own, which relegates these shared protection schemes to either degenerate cases, such as N+1 connections all going between two points with no intermediate nodes, individual rings, or to background optical restoration schemes in which the network is reconfigured in nonreal time to deal with network outages, and instead relies on a simple highlevel scheme like 1+1 protection to deal with realtime protection against failures.
A need therefore exists for methods and apparatus for improved failure correction schemes that are: bandwidth efficient, simple to implement, operational across any network, and utilize failure protection information to also correct transmission errors.
Generally, methods and apparatus are provided for N+1 packet level mesh protection. According to one embodiment of the invention, an error correction encoder is provided for encoding message symbols, m_{0 }through m_{N1}, to generate a codeword that includes the message symbols, m_{0 }through m_{N1}, and one or more check symbols. The error correction encoder comprises a linear feedback shift register having one or more flipflops to generate the check symbols after shifting the message symbols, m_{0 }through m_{N1}, through the linear feedback shift register.
According to one embodiment of the invention, an error correction decoder is provided for decoding a codeword that includes message symbols, m_{0 }through m_{N1}, and one or more check symbols. The error correction decoder comprises a linear feedback shift register having one or more flipflops to generate an error symbol based on a remainder after shifting the message symbols, m_{0 }through m_{N1}, and the one or more check symbols through the linear feedback shift register.
A more complete understanding of the present invention, as well as further features and advantages of the present invention, will be obtained by reference to the following detailed description and drawings.
The present invention provides methods and apparatus for N+1 packet level mesh protection. Generally, the disclosed failure protection techniques are based on error correction, where for every working signal transmitted, some amount of redundancy is employed.
Erasure coding is a form of block error correction that is similar to normal error correction, except in the case of erasure coding, the user knows the location of the errors. In normal block error coding, for a block of N bytes, 2T check symbols must be added for every T symbols that are desired to be “fixable” within the block. In erasure coding, because the location of the errors are known, only T check symbols need to be added for every T symbols to be corrected in the block. It is noted from an information theory perspective, that if the location of the error is not known, one symbol must be employed to indicate the location of the error, and another symbol must be employed to indicate the error value.
Thus, in an N+1 mesh, T equals one, and this check symbol would be calculated from N symbols of the working signals.
Encoder
Given a systematic code of length N, the final message c(x) can be expressed as:
c(x)=x^{T}m(x)−r(x)=q(x)g(x) (1)
where r(x) is the remainder after dividing the shifted message polynomial m(x) by the generator polynomial g(x), and q(x) is the quotient. Assuming a Galois Field, GF (256), i.e., byte based coding, and as per Reed and Solomon'"'"'s theory:
and α^{n }are consecutive elements of GF(256). Thus, when the offset equals 0 and T equals 1:
g(x)=x−α^{0} (3)
Thus, for GF(256) with a single byte check, the codeword 200 would consist of the original message bytes, m_{0 }through m_{N1}, followed by one check byte, r_{0}, as shown in
Decoder
Typically, in erasure decoding, the syndrome polynomial is calculated that can then be used to calculate the error values. Since there is a 1:1 relationship between errors and the remainder polynomial used as an input to syndrome calculations, it is often just implemented as a lookup table, and it is only for large syndrome polynomials that algebraic methods must be employed.
Consider that the first step in the erasure decoding process is to calculate the remainder polynomial. This is done in the same fashion as the generator block 300, except now the entire received codeword c_{R}(x) is divided by g(x). The remainder polynomial is thus:
r(x)=c_{R}(x)g(x) (4)
It is given that c_{R}(x)+c(x)=e(x), where e(x) is the error polynomial. Since this remainder is calculated by dividing the received codeword by the generator polynomial, the same circuit as shown in
During step 420, an Mth packet is created, with the same sequence number as the previous M−1 packets, and whose payload is the bytewise XOR of the associated bytes in the M−1 packets. The length of this Mth packet will be equal to the longest packet in the group, with shorter packets having implicit zeropadding on the end.
It is noted that while the present invention is illustrated in
Consider 4 bytes A, B, C, D that must be protected. The packet mesh encoding process 400 creates a 5th byte E equal to A+B+C+D, where the addition is GF(256) (i.e., bytewise XOR).
Assume that the receiver receives the five bytes plus an error, e, in byte B. The packet mesh decoding process 500 calculates the error as:
since E=A+B+C+D and E+E=0.
The present invention applies to arbitrary Galois fields and binary extension Galois fields. For T=N, in an arbitrary Galois Field, the N check packets are the check bytes from the corresponding block erasure code calculated on a symbolbysymbol basis over the associated symbols in the M−N user packets. For T=1, in an arbitrary Galois Field, the check packet is calculated as the sum (using the appropriate Galois Field addition) on a symbolbysymbol basis over the associated symbols in the M−1 user packets.
For T=1, in a binary extension Galois Field (i.e. GF(2^{n})), the check packet is calculated as the bytewise XOR (also called BIP8) on a bytebybyte basis over the associated bytes in the M−1 user packets. It is noted that addition in GF(2^{n}) is a symbolwise XOR. The symbolwise XOR can only be used to produce the check bytes and correction bytes for T=1. For T>1, it must be calculated using the appropriate LFSR (containing T flops) to divide the codeword by the generator polynomial.
System and Article of Manufacture Details
As is known in the art, the methods and apparatus discussed herein may be distributed as an article of manufacture that itself comprises a computer readable medium having computer readable code means embodied thereon. The computer readable program code means is operable, in conjunction with a computer system, to carry out all or some of the steps to perform the methods or create the apparatuses discussed herein. The computer readable medium may be a recordable medium (e.g., floppy, disks, hard drives, compact disks, or memory cards) or may be a transmission medium (e.g., a network comprising fiberoptics, the worldwide web, cables, or a wireless channel using timedivision multiple access, codedivision multiple access, or other radiofrequency channel). Any medium known or developed that can store information suitable for use with a computer system may be used. The computerreadable code means is any mechanism for allowing a computer to read instructions and data, such as magnetic variations on a magnetic media or height variations on the surface of a compact disk.
The computer systems and servers described herein each contain a memory that will configure associated processors to implement the methods, steps, and functions disclosed herein. The memories could be distributed or local and the processors could be distributed or singular. The memories could be implemented as an electrical, magnetic or optical memory, or any combination of these or other types of storage devices. Moreover, the term “memory” should be construed broadly enough to encompass any information able to be read from or written to an address in the addressable space accessed by an associated processor. With this definition, information on a network is still within a memory because the associated processor can retrieve the information from the network.
It is to be understood that the embodiments and variations shown and described herein are merely illustrative of the principles of this invention and that various modifications may be implemented by those skilled in the art without departing from the scope and spirit of the invention. For example, while the present invention has been primarily illustrated herein using a single protection packet, the present invention may be extended to include T=N codes, with N protection packets, as would be apparent to a person of ordinary skill in the art.