Shulou(Shulou.com)06/03 Report--

Based on the introduction of FEC, this paper focuses on the concrete steps of using FEC to solve network packet loss, the steps are simple and easy to operate, and the content of the article is compact step by step. I hope you can get something according to this article.

FEC:Forward Error Correction, forward error correction

FEC is a method to directly recover the lost data packets by adding redundant information in the network transmission so that the receiver can use these redundant information to recover the lost packets directly after the network packet loss occurs.

The basic theory of FEC: XOR

The rule of XOR

If two values are not equal, it is 1, and if they are equal, it is 0.

0 ^ 0 = 01 ^ 1 = 00 ^ 1 = 11 ^ 0 = 1

Note: XOR ^ by bit converts two numbers into binary and performs XOR operation by bit.

The characteristic of XOR.

Law of identity: X ^ 0 = X return to zero law: X ^ X = 0 commutative law: a ^ B = B ^ An associative law: a ^ (B ^ C) = (A ^ B) ^ C

Note: it can be proved by mathematical method that we only need to remember these rules here, and there are a large number of applications.

Application case of XOR

With these basic theories of XOR, let's see how it is applied to "parity" and "error correction" in practice.

Parity check (Parity Check)

To determine whether the number of 1 in a binary number is odd or even (the law of identity and zeroing is applied):

/ / for example: whether the number of 1 in 10100001 is odd or even / / if the result is 1, it is odd, and the result is even 11 ^ 0 ^ 1 ^ 0 ^ 0 ^ 0 ^ 0 ^ 1 = 1.

This property can be used for parity (Parity Check). A parity bit is calculated for each byte of data, and the data is sent together with the parity bit, so that the receiver can roughly judge whether the received data is incorrect or not.

Disk array-RAID5

Three disks (A, B, C) are used to form a RAID5 array to store users' data. Each data is divided into An and B parts, and then the results of A xor B are written into A, B and C disks as C respectively. In the end, an error on either disk can be recovered from the data of the other two disks.

Realization principle: the law of identity and the law of association are applied.

C = a ^ ba = a ^ (b ^ b) = (a ^ b) ^ b = c ^ bb = (a ^ a) ^ b = a ^ c

FEC based on XOR

Assuming that the network communication has N packet to be sent, then, similar to the above RAID5 strategy, every 2 packet can generate a FEC packet, so that any one packet loss of three consecutive packet can be recovered by the other two.

But considering that one fec packet is generated for every 2 packet, and the redundancy may be a bit high (it is a waste of bandwidth), can we generate another fec packet for every 3 or every N packet? Of course, let's take one fec packet (D) for every three packet (A, B, C) as an example to deduce:

D = a ^ b ^ ca = a ^ (b ^ b) ^ (c ^ c) = (b ^ c) ^ (a ^ b ^ c) = b ^ c ^ db = (a ^ a) ^ b ^ (c) = (a ^ c) ^ (a ^ b ^ c) = a ^ c ^ dc = (a ^ a) ^ (b ^ b) ^ c = (a ^ b) ^ (a ^ b ^ c) = a ^ b ^ d

From the derivation of the above formula, we can know that these four packet, any loss of one packet, can be recovered from the other three packet.

Object Storage-EC erasure Code

The object storage services provided by some Internet cloud computing companies claim to have high data reliability, such as three-copy technology, EC erasure code technology, and so on. The latter solution is shown in the figure:

In the figure, the erasure code strategy of 8x4 is adopted (that is, the original data is cut into 8 copies and 4 redundant information is calculated). The 12 copies are stored on 12 different nodes in different cabinets. Even if multiple nodes (up to 4) are damaged or inaccessible at the same time, the data can be recovered as long as no less than 8 nodes are available.

I don't know if you can see anything? Compared with the above scheme of generating 1 FEC packet based on N packet, this K + M erasure code strategy has better ability to carry loss, which can be summarized as follows:

M FEC redundant packets are generated through K pieces of effective data. K + M pieces of data can be recovered if M pieces of data are lost arbitrarily.

In fact, this scheme was first applied in the field of network transmission, but it was borrowed to the storage field to improve the utilization of disks. In order to implement this K + M FEC strategy, it is difficult to use simple XOR XOR to deduce, with the help of matrix-related calculation, there are many implementation schemes, the following is a brief introduction to the most famous and commonly used Reed-solomon codes.

Reed-Solomon Codes

Reed-solomon codes (RS codes for short), the FEC strategy implemented by this principle, is usually called RS-FEC. There are many introductions about it on the Internet, so this article will not expand it in detail, but simply give a general principle in the form of a schematic diagram:

RS codes coding process

The general principle is as follows: suppose there are K valid data, and M FEC data are expected to be generated.

1. K valid data are formed into a unit vector D

two。 Generate a transformation matrix B: consisting of a K-order unit matrix and a K * M Vandermont matrix (Vandemode)

3. The matrix G obtained by multiplying two matrices contains M redundant FEC data.

RS codes decoding process

Assuming that the data D1 ~ D4 ~ C2 is lost, the original data matrix can be recovered by taking the inverse of the corresponding Vandermonde matrix * no missing data matrix.

The general principle is as follows: suppose the data D1, D4, C2 is missing.

1. For matrix B and D, the rows without loss are taken to form B 'and G', respectively.

two。 According to the following formula, the effective data vector D can be calculated.

Inverse x G' of B'x D = G'- > > D = B'

On the use of FEC to solve the problem of network packet loss is shared here, I hope the above content can be of some help to you, can learn more knowledge. If you like this article, you might as well share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.