CN115361103A - Buffer Management Mechanism for Select-Repeat Hybrid Automatic Repeat Request Protocol - Google Patents

Abstract

The invention discloses a buffer management mechanism for a selective-repeat hybrid automatic repeat request protocol, which comprises the following steps: 1) The specific implementation of the HARQ mechanism comprises a sending end and a receiving end, and the sending end and the receiving end are respectively provided with an independent data frame buffer area and an independent data reading and writing module; 2) The data frame buffer area adopts an annular structure and is mainly characterized in that the buffer areas are connected end to form a cycle; 3) Before the data frame is read/written into the buffer area, the existing data frame or vacant space must be found in the buffer area in advance; 4) The error correction algorithm used by the mechanism comprises a cyclic redundancy check and a Reed-Solomon code; 5) The received data frames can be divided into three types: ACK/NACK information, a common data frame with CRC check bits and RS code check bits; 6) Besides calculating error check bits, metadata indicating the attribute of the data frame is added on the basis of the original data frame to form a new HARQ data frame format.

Description

Buffer Management Mechanism for Select-Repeat Hybrid Automatic Repeat Request Protocol

technical field

The invention belongs to the technical field of data frame buffer management, and in particular relates to a buffer management mechanism for a select-repeat hybrid automatic repeat request protocol.

Background technique

There are non-ideal factors such as noise, attenuation, and interference in communication channels in reality, which can cause bit errors in the transmission process of data frames. Therefore, practical communication technology needs to implement error correction technology at different levels to ensure that the data frame can be correctly decoded by the receiving end. One of the widely used technologies is Hybrid Automatic Transfer Request (HARQ): At its core, it combines error-checking bits and data retransmission mechanisms. When the receiving end cannot correct the bit error in the data frame, it will notify the sending terminal to retransmit the data frame until it succeeds. In this way, data frames with errors during transmission can be finally received without errors, ensuring the reliability of the communication system.

In different implementations of HARQ, HARQ based on a selective retransmission (SR) mechanism retransmits data frames with errors in a non-blocking manner. This means that SR-HARQ can continue to send and receive data streams without waiting for the successful transmission of erroneous data frames before continuing, so the channel utilization rate is high. However, this will result in the situation that the subsequent new data frames may have been successfully received on the premise that some old data frames have not been successfully sent. This will inevitably disrupt the original sequence of data frames, making it impossible for the receiving end to restore the original data according to the normal timing. Therefore, establishing a complete set of data frame buffer management mechanism is the key to realize the out-of-order sending and receiving function normally.

Hybrid Automatic Repeat reQuest (Hybrid Automatic Repeat reQuest) is one of the commonly used protocols in communication systems, mainly used to ensure that the receiving end of the communication can finally receive the data accurately: if the receiving end detects that the data is If there is interference and an error occurs, a NACK message will be returned to the sender to notify it to resend the data; if there is no error, an ACK message will be returned to notify the sender that the data has been successfully received. This simple mechanism ensures that information is transmitted reliably over unreliable communication channels.

Among them, the mechanism based on Select-Repeat only requires the sender to resend the error data frame when receiving the report, and other data frames can still be sent and received normally. SR-HARQ breaks the limitation in the traditional HARQ implementation that the sending terminal needs to transmit data frames in sequence, and waits for the receiving end to successfully receive the current data frame before attempting to send the next data frame, which greatly improves the utilization of communication resources. However, this method will cause the original timing of sending and receiving data frames to be disrupted, so the sequence management of data frames plays a crucial role in the specific implementation of SR-HARQ.

The current SR-HARQ has the following steps for the write operation:

1. Try to write the externally stored HARQ data into the cache;

2. If the write hits, write the HARQ data; if the write is missing, reallocate the cache line;

3. For the case of missing write in step 2, if there is no data in the cache line, write HARQ data; if there is, decide whether to execute the write operation according to the error verification result and specific configuration;

The operation of reading data from the cache to the external storage is roughly the same as the writing process, and will not be repeated here.

Through the above steps of cache line allocation and polling of cache line data, storage space bubbles can be reduced, cache utilization can be improved, and HARQ operating resources can be saved. But there are following disadvantages in this technical scheme:

1. Only read and write data based on the occupancy of the cache, but fail to perform queue management on the data and retain the original order of the data;

2. Only use CRC as an error detection algorithm, without combining other algorithms to strengthen the error correction function.

Contents of the invention

In order to solve the above problems, the primary purpose of the present invention is to provide a buffer management mechanism for selection-repeat hybrid automatic repeat request protocol, the method can realize out-of-sequence sending and receiving functions through this mechanism, while retaining the sequence of data frames sex.

To achieve the above object, the technical solution of the present invention is as follows.

A buffer management mechanism for the Select-Repeat Hybrid Automatic Repeat Request protocol, the mechanism comprising the following:

1) The specific implementation of the HARQ mechanism includes two parts, the sending end and the receiving end, and each has an independent data frame buffer, data reading and writing module;

2) The data frame buffer adopts a ring structure. The main feature is that the buffer is connected head to tail, and the next element at the tail is the head, forming a loop; this feature is suitable for caching data streams, and is also the key to realizing out-of-order sending and receiving functions .

3) Before the data frame is read/written into the buffer, an existing data frame or vacancy must be found in the buffer before the corresponding operation can be continued.

4) The error correction algorithm used by this mechanism includes two types: cyclic redundancy check (CRC) and Reed-Solomon code (Reed-Solomon code); the specific algorithm is adopted based on the number of data frame transmissions and the complexity of the algorithm and error correction capability decisions.

5) The received data frame can be divided into three types: ACK/NACK information, ordinary data frame with CRC check digit and RS code check digit; the three are distinguished by the size of the received data frame.

6) In addition to calculating the error parity bit, add metadata indicating the attributes of the data frame on the basis of the original data frame to form a new HARQ data frame format.

Further, for point 1), the objects for reading and writing the buffer include the sending end and the receiving end; for the sending end, the data frame from the upper layer of the network will be written into the module temporarily after being encoded by the error correction algorithm. Stored in the sending buffer, and then the reading module reads the data frame from the buffer for subsequent sending actions; for the receiving end, the writing module temporarily stores the newly received data frame in the receiving buffer, At the same time, the readout module reads the data frame from the buffer, decodes and verifies it, and pushes the verified data frame to the upper layer of the network; at the same time, the sending and receiving ends, and the read and write operations of both are independent .

Further, for point 3), where to write the data frame to the buffer:

When a new data frame is about to be written into the buffer, the write module needs to use the Round-Robin method to poll the buffer before the new data frame is written to find a valid vacancy in the buffer; assuming the buffer can be To store up to N data frames, and BUF[i] represents the i-th position in the buffer, the specific steps are as follows:

S1. Start from the starting position i (default i=0), check whether BUF[i] is empty;

S2. If BUF[i] is empty, it means that the location is available for writing. The write module writes the new data frame into BUF[i] and updates the starting position i, and the next search will start from this position; otherwise, it means that there is an old data frame at this position, at this time execute i++ and repeat step 1;

S3. When i++ needs to be executed in step 2 and i=N-1, it means that the check has reached the end of the buffer. At this point, i should be reset to 0 and then step 1 should be repeated, so that the checking process can continue from the head;

S4. When the above steps have been executed N times and no vacancy is found after scanning the buffer, it means that the buffer is full, and a corresponding error message is returned.

Furthermore, for point 3), the position of reading the data frame from the buffer, the readout module also needs to scan the buffer in advance, and the scan for reading will check whether there is a data frame in BUF[i], so as to read from the The read action is performed at the position of the data frame to avoid reading the vacancy in the buffer by mistake.

Further, for point 4), the adoption of the error check bit algorithm.

Before a new data frame is sent for the first time, the sender will use CRC to add a check digit to the data frame; if the data frame fails to be sent for the first time, before it needs to be resent, the sender will clear the original CRC check digit of the data frame , and then use the RS code with higher complexity but stronger error correction capability to re-encode the data frame. Since the sizes of data frames generated by the two algorithms are different after encoding, the receiving end can use this to determine the decoding method that should be used after receiving the data frames.

Further, for point 6), the data frame structure, in addition to error correction coding, the HARQ implementation will also add a metadata tag on the basis of the original data frame, which is used to mark and track the transmission status of the data frame.

The components of the HARQ data frame in this implementation are as follows in sequence:

1) Sequence number: Record the specific position of the data frame in the sending buffer, which is used to quickly index the corresponding data frame in the ACK/NACK information returned from the receiving end.

2) Flag bit: It is mainly used to track the number of times the data frame has been sent. The receiving end will use this flag bit to carry ACK/NACK information: if the receiving end wants to return ACK information, set all flag bits to 0; otherwise set to 1. For the sending end, the information from the receiving end with all flag bits set to 0 is regarded as ACK; if the flag bits are all 1, it is regarded as NACK. When the sending end receives NACK and decides to resend the data frame, it will add 1 to the flag bit of the sending frame, and then perform the corresponding operation.

3) Timestamp: use the UNIX microsecond timestamp format to record the time point when the data frame arrives at the HARQ sender from the upper layer of the network. This method can record the time sequence of the original data stream, so that the receiving end can restore the time sequence of the original data frame according to the timestamp.

4) Size: used to indicate the size of the original data frame.

5) Data: the original data frame including error parity bits, and trailing zero padding (if any).

The invention forms a loop by connecting the buffers end to end, and is suitable for caching data streams; before a data frame is read/written into the buffer, an existing data frame or vacancy must be found in the buffer before proceeding The corresponding operation improves the accuracy of reading and writing of data, further ensures the reliability of the data frame through the error correction algorithm used, and ensures the sequence of the data frame by forming a new HARQ data frame format. Therefore, the present invention can realize out-of-order transmission and reception function while preserving the seriality of the dataframe.

Description of drawings

Fig. 1 is a flow chart of buffer reading and writing steps realized by the present invention.

Fig. 2 is a schematic diagram of the buffer polling process realized by the present invention.

Detailed ways

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention.

The implementation of the buffer management mechanism for the selective-repeat hybrid automatic repeat request protocol implemented by the present invention is shown in FIG. 1 .

1) The specific implementation of the HARQ mechanism includes two parts, the sending end and the receiving end, and each has an independent data frame buffer, data reading and writing module.

2) The data frame buffer adopts a ring structure. The main feature is that the buffer is connected head to tail, and the next element at the tail is the head, forming a cycle. This feature is suitable for buffering data streams and is also the key to realizing out-of-order sending and receiving functions.

3) Before the data frame is read/written into the buffer, an existing data frame or vacancy must be found in the buffer before the corresponding operation can be continued.

4) The error correction algorithm used by this mechanism includes two types: cyclic redundancy check (CRC) and Reed-Solomon code (Reed-Solomon code). The adoption of the specific algorithm is determined based on the number of data frame transmissions, the complexity of the algorithm, and the ability to correct errors.

5) Received data frames can be divided into three types: ACK/NACK information, ordinary data frames with CRC check digit and RS code check digit. The three are distinguished by the size of the received data frame.

6) In addition to calculating the error parity bit, add metadata indicating the attributes of the data frame on the basis of the original data frame to form a new HARQ data frame format.

For point 1), read and write buffer objects.

For the sending end, after the data frame from the upper layer of the network is encoded by the error correction algorithm, it will be temporarily stored in the sending buffer by the writing module, and then the reading module will read the data frame from the buffer for subsequent sending action. For the receiving end, the writing module will temporarily store the newly received data frame in the receiving buffer, and at the same time, the reading module will decode and verify the data frame after reading the data frame from the buffer, and push the data frame with successful verification to the upper layer of the network. In addition, the sending and receiving ends, as well as the read and write operations of the two are independent, so asynchronous operation can be adopted to realize full-duplex data transmission and reception.

For point 3), write the location of the data frame to the buffer.

When a new data frame is about to be written into the buffer, there may be existing old data frames in the buffer, which are distributed in different positions in the buffer. For example, after the data frame in the sending buffer is unsuccessfully sent, it will still occupy the same position until it is successfully resent or cleared. Therefore, before the new data frame is written, the writing module needs to use the Round-Robin method to poll the buffer to find a valid vacancy in the buffer. Here, assuming that the buffer can store up to N data frames, and BUF[i] represents the i-th position in the buffer, the specific steps are as follows:

S1. Start from the starting position i (default i=0), check whether BUF[i] is empty;

S2. If BUF[i] is empty, it means that the location is available for writing. The write module writes the new data frame into BUF[i] and updates the starting position i, and the next search will start from this position; otherwise, it means that there is an old data frame at this position, at this time execute i++ and repeat step 1;

S3. When i++ needs to be executed in step 2 and i=N-1, it means that the check has reached the end of the buffer. At this point, i should be reset to 0 and then step 1 should be repeated, so that the checking process can continue from the head. This step is a concrete implementation of the buffer ring structure.

S4. When the above steps have been executed N times and no vacancy is found after scanning the buffer, it means that the buffer is full, and a corresponding error message is returned.

In general, the above steps adopt the method of sequential search and write, which can ensure that new data frames can be written into the buffer in sequence to the greatest extent, and can also skip existing old data frames to avoid overwriting data by mistake. This mechanism can achieve a good balance in terms of sequence and efficiency.

For the location of reading data frames from the buffer, similar to the process of writing data frames to the buffer, the readout module also needs to scan the buffer in advance. The difference is that the scan for reading will check whether there is a data frame in BUF[i], so as to read from the position of the existing data frame, and avoid reading the vacancy in the buffer by mistake. The rest of the details are roughly the same as the writing process, as shown in Figure 2, and will not be repeated here.

For point 4), the adoption of the error check bit algorithm.

Before a new data frame is sent for the first time, the sender will use CRC to add a check digit to the data frame. The algorithm complexity of CRC is low, so using this algorithm for new data frames can reduce the impact of error correction steps on HARQ operation efficiency, and avoid performance bottlenecks causing congestion. If the data frame fails to be sent for the first time, before resending, the sender will clear the original CRC check digit of the data frame, and then re-encode the data frame using RS code with higher complexity but stronger error correction capability. Since the sizes of data frames generated by the two algorithms are different after encoding, the receiving end can use this to determine the decoding method that should be used after receiving the data frames. This mechanism can achieve a good balance in terms of efficiency and error correction.

For point 6), the data frame structure, in addition to error correction coding, the HARQ implementation will also add metadata tags on the basis of the original data frame for marking and tracking the transmission status of the data frame. The components of the HARQ data frame in this implementation are as follows in sequence:

1) Sequence number: Record the specific position of the data frame in the sending buffer, which is used to quickly index the corresponding data frame in the ACK/NACK information returned from the receiving end.

2) Flag bit: mainly used to track the number of times a data frame has been sent (the default is 1, because each data frame will be sent at least once). In addition, the receiving end will use this flag bit to carry ACK/NACK information: if the receiving end wants to return ACK information, set all flag bits to 0; otherwise, set them to 1. For the sending end, the information from the receiving end with all flag bits set to 0 is regarded as ACK; if the flag bits are all 1, it is regarded as NACK. When the sending end receives NACK and decides to resend the data frame, it will add 1 to the flag bit of the sending frame, and then perform the corresponding operation.

3) Timestamp: use the UNIX microsecond timestamp format to record the time point when the data frame arrives at the HARQ sender from the upper layer of the network. This method can record the time sequence of the original data stream, so that the receiving end can restore the time sequence of the original data frame according to the timestamp.

4) Size: used to indicate the size of the original data frame.

5) Data: the original data frame including error parity bits, and trailing zero padding (if any).

It should be noted that the ACK/NACK returned from the receiving end to the sending end only includes two parts, the sequence number and the flag bit. The reason is that the sequence number can locate its corresponding feedback data frame, and the flag bit is used to identify the ACK/NACK itself. From the two, the sending end can obtain all the necessary information fed back by the receiving end.

The above are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention should be included in the protection scope of the present invention. Inside.

Claims (6)

1. A buffer management mechanism for a select-repeat hybrid automatic repeat request protocol, the mechanism comprising:

1) The specific implementation of the HARQ mechanism comprises a sending end and a receiving end, and the sending end and the receiving end are respectively provided with an independent data frame buffer area and an independent data reading and writing module;

2) The data frame buffer area adopts a ring structure and is mainly characterized in that the buffer areas are connected end to end, and the next element at the tail is the head, so that a cycle is formed;

3) Before the data frame is read out/written into the buffer area, the existing data frame or vacant position must be found in the buffer area in advance, and then the corresponding operation can be continued;

4) The error correction algorithm used by the mechanism comprises a cyclic redundancy check and a Reed-Solomon code;

5) The received data frames can be divided into three types: ACK/NACK information, a common data frame with CRC check bits and RS code check bits;

6) Besides calculating error check bits, metadata indicating the attribute of the data frame is added on the basis of the original data frame to form a new HARQ data frame format.

2. The buffer management mechanism for a select-repeat hybrid automatic repeat request protocol according to claim 1, wherein for point 1), objects read from and written to the buffer comprise a sender and a receiver; for a sending end, after a data frame from an upper layer of a network is coded by an error correction algorithm, the data frame is temporarily stored in a sending buffer area by a writing module, and then the data frame is read out from the buffer area by a reading module so as to carry out subsequent sending action; for a receiving end, the writing module can temporarily store a newly received data frame in a receiving buffer area, and the reading module reads the data frame from the buffer area and then decodes and verifies the data frame, and pushes the data frame which is verified successfully to an upper layer of a network; meanwhile, the sending and receiving ends and the read-write operations of the sending and receiving ends are independent respectively.

3. The buffer management mechanism for a select-repeat hybrid automatic repeat request protocol according to claim 1, wherein for point 3), the location of the data frame is written to the buffer:

when a new data frame is to be written into the buffer area, the writing module needs to poll the buffer area by using a Round-Robin mode before the new data frame is written into the buffer area so as to find an effective vacant position in the buffer area; assuming that the buffer can store a maximum of N data frames and BUF [ i ] represents the ith position in the buffer, the specific steps are as follows:

s1, starting from a starting position i (default i = 0), checking whether BUF [ i ] is empty;

s2, if the BUF [ i ] is empty, representing that the position can be written in; the writing module writes the new data frame into the BUF [ i ] and updates the initial position i, and the next search starts from the position; otherwise, representing that the position has an old data frame, executing i + + at the moment and repeating the step 1;

s3, when i + + needs to be executed in the step 2 and i = N-1, checking the tail of the buffer area; at this point, step 1 should be repeated after i is reset to 0 to continue the inspection process from the head;

s4, when the steps are executed for N times and no vacant position is found after the buffer zone is scanned, representing that the buffer zone is full, and returning corresponding error information.

4. The buffer management mechanism of claim 3, wherein for point 3), the location of the data frame is read from the buffer, and the read module also needs to scan the buffer in advance, and the scanning for reading will check if the data frame exists in the BUF [ i ] to perform the reading operation from the location of the existing data frame, so as to avoid the erroneous reading to the empty location in the buffer.

5. The buffer management mechanism for a select-repeat hybrid automatic repeat request protocol according to claim 1, wherein for point 4), the use of the error check bit algorithm: before a new data frame is sent for the first time, a sending end adds check bits to the data frame by using CRC; if the first transmission of the data frame fails, before retransmission is needed, the transmitting end will clear the original CRC check bit of the data frame, and then use the RS code with higher complexity and stronger error correction capability to re-encode the data frame.

6. The buffer management mechanism of claim 1, wherein for point 6), the data frame structure, in addition to error correction coding, the HARQ implementation adds metadata tags on the original data frame, and the HARQ data frame components in the implementation are sequentially as follows:

1) Sequence number: recording the specific position of the data frame in the sending buffer area, and quickly indexing the corresponding data frame from the ACK/NACK information returned by the receiving end;

2) A flag bit: the receiving end uses the flag bit to carry ACK/NACK information, which is mainly used to track the number of times the data frame has been sent: if the receiving end needs to return the ACK information, all the flag bits are set to be 0; otherwise, setting the value to 1;

3) Time stamping: recording the time point of a data frame from the upper layer of the network to the HARQ sending end by adopting a UNIX microsecond timestamp format;

4) Size: for indicating the size of the original data frame;

5) Data: the original data frame containing the error check bits, and the tail zero padding (if any).

Images