CN110943803B - A Data Transmission Control Method Based on Erasure Erasure Coding - Google Patents

Abstract

The invention discloses a data transmission control method based on erasure coding, which specifically comprises the following steps: 1. the Chunk is cut and coded with erasure correction, and put into sending buffer; 2. selecting the untransmitted data segments from the sending buffer for transmission according to a given sending rate; 3. placing the received data segment into a receiving cache; 4. performing Chunk recombination and decoding; 5. sending a confirmation message to each received data segment and feeding back the confirmation message; 6. estimating available bandwidth of the network according to the receiving condition of the feedback message of the receiving end so as to update the sending rate of the data segment; the invention ensures the transmission quality of the current network and the effective utilization of the network bandwidth, improves the stability and reduces the time delay.

Description

Data transmission control method based on erasure coding

Technical Field

The invention belongs to the field of data transmission, and particularly relates to a data transmission control method based on erasure coding.

Background

In wireless as well as wired networks, packet loss may occur in data being transmitted due to variations in channel quality or congestion. The underlying transport capabilities provided by the network tend to be unreliable. To achieve reliable data transmission in unreliable network environments, the most widely used design at present is to use the TCP protocol, and use the acknowledgement and retransmission mechanisms used therein to ensure effective delivery of data. The existing reliable data transmission protocols such as TCP are very sensitive to packet loss, which results in low utilization rate of bandwidth in an unreliable network.

Erasure coding techniques enable reliable data transmission in unreliable networks. For original data cut into X segments with the same size, erasure coding technology can code the original data into Y segments and ensure that the original data can be decoded as long as any X + Z segment is obtained. In practice, the value of Z is related to a specific encoding technique, and may be 0, or 1, 2, etc. After erasure coding is adopted, the transmitting and receiving parties do not need to accurately retransmit the lost data segment, and only need to ensure that the receiving end receives enough data. Erasure coding techniques can help the transceiving end not perform complex retransmission control on the lost packet, but face the problem of how to avoid transmission of redundant data and how to reduce transmission delay of data.

Disclosure of Invention

In view of the above problems, the present invention provides a data transmission control method based on erasure coding.

The invention relates to a data transmission control method based on erasure coding, which comprises the following steps:

step 1: chunk segmentation and encoding: inputting a file to be transmitted or streaming data, segmenting the file or the streaming data into a plurality of chunks, encoding each chunk into a plurality of data segments with equal size by using erasure correction codes, and putting the data segments into a sending cache;

step 2: data segment selection and transmission: selecting the untransmitted data segments from the sending buffer for transmission according to a given sending rate;

and step 3: and (3) receiving a data segment: placing the received data segment into a receiving cache;

and 4, step 4: chunk reorganization and decoding: attempting to decode the corresponding chunk after receiving the new data segment, and if the decoding is successful, performing streaming output on the chunk or reconstructing and restoring the chunk into a source data file;

and 5: confirmation and feedback: sending a confirmation message to each received data segment, and feeding back the number of data segments which need to be transmitted for completing decoding and corresponding to chunk;

step 6: bandwidth estimation and transmission control: estimating available bandwidth of the network according to the receiving condition of the feedback message of the receiving end so as to update the sending rate of the data segment; controlling the sending of the chunk residual data according to the number of the data segments required by the chunk fed back by the receiving end, so as to avoid redundant transmission of the data; and removing the data segment left by the transmitted chunk from the sending buffer.

Further, the sending rate of the data segment instep 2 is R, and the value of R is equal to the estimated available bandwidth Bw of the current path; the time interval for sending the data segments is v/R, wherein v is the length of the data segments; when a data segment is transmitted, selecting the chunk with the minimum number value which is not transmitted from the transmission buffer for checking to see whether the data segment needs to be selected for transmission.

The chunk check is as follows:

for chunk i, i represents a chunk number; setting the maximum number of the data segment sent by the current sending end as S_iThe maximum data segment number that has received an acknowledgement is A_i(ii) a Then the chunk has already been sentBut the total amount of data segments that have not yet been acknowledged is S_i-A_i(ii) a The ratio of successful transmission of the transmission path is estimated as gamma_iThen there is γ in these data_i(S_i-A_i) Can be received by the receiving end.

If chunk still requires O_iThe decoding can be completed for each data segment, then at gamma_i(S_i-A_i)<O_iThen, selecting the data segment with the minimum number which is not transmitted from chunk i and sending the data segment to the receiving end, and updating S_i(ii) a Otherwise, the same data segment selection and control is continued at the next chunk which has not been transmitted.

Further, the control method of the sending rate R is as follows:

(1) the sending rate R defaults to the maximum available bandwidth Bw supported by the network.

(2) The sending end continuously sends M data segments and then pauses; after the sending end receives N confirmation messages (the values of the data M and N are different according to different networks, and M is greater than N), the estimation of the available bandwidth Bw is immediately carried out: setting the duration between the first arrival and the last arrival acknowledgement message to T1; the minimum sending sequence number confirmed by the confirmation messages is A1, and the maximum sequence number is A2; then the available bandwidth of the current path is estimated to be N × v/T1, and the packet loss rate is estimated to be 1-N/(a2-a1+ 1).

(3) If the packet loss rate threshold caused by the non-congestion of the network path is set to be less, if 1-N/(A2-A1+1) > less, the sending end takes N x v/T1 as a new available bandwidth Bw value; otherwise, indicating that the bandwidth is not full, the sending rate may be increased, with N v/T1 θ as the new value of the available bandwidth Bw, where θ >1, representing the increased proportion of the sending rate, is a configurable parameter.

(4) If the N acknowledgement messages are not collected within the maximum acceptance time T, then (2) is returned.

(5) After the Bw finishes the first estimation, the sending end immediately adopts a new sending rate R to send the data segment; thereafter, each time an acknowledgment message is received, the sender performs the same calculations as described above based on the most recently received N acknowledgment messages.

Further, rateless coding or the like may be used as the erasure coding.

Compared with the prior art, the invention has the beneficial technical effects that:

1. the erasure correction coding is utilized to ensure that the system realizes reliable data transmission in an unreliable environment, and the transmission stability is ensured by automatically detecting and adjusting the transmission rate in a network environment with fluctuating bandwidth, so that the occurrence of congestion is avoided, and the transmission quality of the current network is ensured.

2. The available bandwidth in the network can be fully utilized while data transmission is avoided, and effective utilization of the network bandwidth is guaranteed.

3. The sending selection strategy of the data segments among different chunks ensures that the earlier chunk is transmitted with higher priority, reduces the time required for completing transmission of one chunk, and reduces the delay caused by introducing erasure coding technology.

Drawings

Fig. 1 is a schematic diagram of the transmission control operation of the present invention.

Detailed Description

The invention is described in further detail below with reference to the figures and the detailed description.

The design idea of the invention is as follows:

1. for a large file to be transmitted or continuously generated data to be transmitted, a data transmitting end divides the large file to be transmitted into a plurality of chunks, and each chunk is encoded into a plurality of data segments with the same size by adopting an erasure correcting encoding technology; each data segment obtained by coding can be just put into a UDP message for transmission; (by splitting a large file into multiple chunks, on one hand, the time required for erasure coding and decoding can be reduced, and on the other hand, the transmission delay of each data segment can be reduced, which is beneficial to reliable transmission of streaming data, and by splitting one large transmission task into multiple chunks for processing, which can help the sending and receiving ends to utilize the multi-core processing capability of computer hardware, and perform concurrent processing to reduce the required time).

2. The transmitting end and the receiving end adopt UDP to complete the transmission of the coded data, and by utilizing the characteristics of erasure correction coding, the transmitting and receiving parties only need to ensure that a receiver receives enough decoded data quantity, and do not care whether the received data is continuous or not.

3. The receiving end sends a confirmation message to the received data segment and feeds back the number of data segments needed to finish the decoding of the chunk; the transmitting end estimates the available bandwidth in the network according to the arrival rule of the confirmation message, and estimates and adjusts the transmitting rate of the data segment; and the sending end controls the sending of the chunk data segment according to the data volume required by chunk decoding fed back by the receiving end, so that the transmission of excessive redundant data segments is avoided.

4. Before the data segment generated by coding in each chunk is sent, the sending end does not need to retransmit the unacknowledged data segment; after all the data segments are sent, the sending end sends the unacknowledged data segments in sequence, and the receiving end is ensured to receive enough data.

5. In order to fully utilize the available bandwidth in the network, the transmitting end may transmit multiple chunk data segments simultaneously.

To achieve the above design, the present invention provides a data transmission control method based on erasure coding, as shown in fig. 1, specifically:

a: chunk segmentation and encoding: inputting a file to be transmitted or streaming data, segmenting the file or the streaming data into a plurality of chunks, encoding each chunk into a plurality of data segments with equal size by using erasure correction codes, and putting the data segments into a sending cache;

b: data segment selection and transmission: selecting the untransmitted data segments from the sending buffer for transmission according to a given sending rate;

c: and (3) receiving a data segment: placing the received data segment into a receiving cache;

d: chunk reorganization and decoding: attempting to decode the corresponding chunk after receiving the new data segment, and if the decoding is successful, performing streaming output on the chunk or reconstructing and restoring the chunk into a source data file;

e: confirmation and feedback: sending a confirmation message to each received data segment, and feeding back the number of data segments which are not decoded and correspond to chunk and need to be transmitted;

f: bandwidth estimation and transmission control: estimating available bandwidth of the network according to the receiving condition of the feedback message of the receiving end so as to update the sending rate of the data segment; controlling the sending of the chunk residual data according to the number of the data segments required by the chunk fed back by the receiving end, so as to avoid redundant transmission of the data; and removing the data segment left by the transmitted chunk from the sending buffer.

The selection and sending method of the data segment in B comprises the following steps:

in the invention, the data of each chunk generates a plurality of data segments with the same size through erasure coding, and the data segments are assumed to be v; if the available bandwidth of the current path estimated by the F module is Bw, the sending rate is R, and the value of R is equal to the estimated available bandwidth of the current path Bw; and simultaneously, the module B continuously selects data segments from the sending buffer to send to the data receiving end according to the time interval of v/R. In order to fully utilize the remaining bandwidth and avoid excessive redundant transmission, the present invention adopts a novel data segment selection method, and the working principle thereof is as follows.

When a data segment can be sent, the module B selects the chunk with the smallest number value that has not been transmitted from the sending buffer to check, and it is necessary to select the data segment for sending.

The examination contents are as follows:

for chunk i, assume that the maximum number of the data segment that has been sent by the current sender is S_iThe maximum data segment number that has received an acknowledgement is A_i(ii) a Then the total amount of data segments that have been sent by the chunk but have not yet been acknowledged is S_i-A_i. It is contemplated that these data segments in the transmission may not all be received because of packet loss. If the estimated value of the proportion of successful transmission of the transmission path is gamma_iThen there is about γ in these data_i(S_i-A_i) Can be received by the receiving end.

Further, if the latest feedback message at the receiving end indicates that the chunk still needs to be sent by O_iDecoding can be completed by each data segment; then, if γ_i(S_i-A_i)<O_iThe B module is the slave chSelecting the data segment with the minimum number which is not transmitted from the unk i to send to the receiving end, and updating the S_i(ii) a Otherwise, the module B continues to perform similar data segment selection and control on the next chunk that has not been transmitted.

The method for estimating the bandwidth (i.e., controlling the transmission rate) in F is designed as follows:

in a dynamic network, the available bandwidth between the sending and receiving ends may change over time. Therefore, the invention estimates the available bandwidth on the transmission path by using the sending and confirming conditions of the data segment, and dynamically adjusts the sending rate R used by the B module.

In the initial state, the transmission rate R defaults to the maximum transmission rate supported by the network.

In order to start the whole process, at the beginning, a sending end continuously sends M data segments, and then pauses;

after the sending end receives N confirmation messages, the estimation of R is immediately carried out: assume that the duration between the first arrival and the last arrival acknowledgement message is T1; the minimum sending sequence number confirmed by the confirmation messages is A1, and the maximum sequence number is A2; then, the available bandwidth of the current path is estimated to be N × v/T1, and the packet loss rate is estimated to be 1-N/(a2-a1+ 1).

Assuming that a packet loss rate threshold caused by non-congestion of a network path is less, if 1-N/(a2-a1+1) > less, a sending end takes N × v/T1 as a new R value; otherwise, indicating that the bandwidth is not full, the sending rate can be increased, taking N x v/T1 x θ as a new R value, where θ >1, representing the increasing proportion of the sending rate, is a configurable parameter;

if N confirmation messages are not collected within the time T2, repeating the process;

after R finishes the first estimation, the sending end immediately adopts the new sending rate to send the data segment; thereafter, each time an acknowledgment message is received, the sender performs a similar calculation as described above based on the most recently received N acknowledgment messages.

At this time, if no new acknowledgement message is received within the time T2, the sender returns to the start phase and starts over.

Claims (5)

Translated fromChinese

1.一种基于纠删编码的数据传输控制方法，其特征在于，步骤如下：1. a data transmission control method based on erasure correction coding, is characterized in that, step is as follows:步骤1：Chunk切分与编码：将待传输的文件或者流式数据输入，切分为多个chunk，并使用纠删编码将每个chunk编码为多个相等大小的数据段，放入发送缓存；Step 1: Chunk segmentation and encoding: Input the file or streaming data to be transmitted, divide it into multiple chunks, and use erasure coding to encode each chunk into multiple data segments of equal size, and put them into the sending buffer ;步骤2：数据段选择与发送：按照给定的发送速率从发送缓存中选择未传输的数据段进行传输；Step 2: data segment selection and transmission: select untransmitted data segments from the transmission buffer for transmission according to a given transmission rate;设数据段的发送速率为R，R的取值等于当前路径的估计可用带宽Bw；发送数据段的时间间隔为v/R，其中v为数据段长度；每当发送一个数据段时，从发送缓存中选择编号值最小尚未传完的chunk进行检查，看是否需要选择数据段进行发送；Let the sending rate of the data segment be R, and the value of R is equal to the estimated available bandwidth Bw of the current path; the time interval for sending data segments is v/R, where v is the length of the data segment; In the cache, select the chunk with the smallest number value that has not yet been transmitted to check to see if a data segment needs to be selected for transmission;步骤3：数据段接收：将收到的数据段放置到接收缓存中；Step 3: Data segment reception: place the received data segment into the receive buffer;步骤4：Chunk重组与解码：每当收到新数据段后，尝试对相应的chunk进行解码，如果解码成功，则将该chunk进行流式输出，或者重组还原为源数据文件；Step 4: Chunk reorganization and decoding: Whenever a new data segment is received, try to decode the corresponding chunk. If the decoding is successful, the chunk will be streamed output, or reorganized and restored to the source data file;步骤5：确认与反馈：对每个收到的数据段发送确认消息，并反馈为完成解码对应chunk还需传输的数据段数目；Step 5: Confirmation and feedback: send a confirmation message to each received data segment, and feed back the number of data segments that need to be transmitted to complete the decoding of the corresponding chunk;步骤6：带宽估计与发送控制：根据接收端反馈消息的接收情况估计网络的可用带宽，以更新数据段的发送速率；根据接收端所反馈chunk所需的数据段数目，控制该chunk剩余数据的发送，避免数据的多余传输；同时将已经传输完毕的chunk所剩余的数据段从发送缓存中移除。Step 6: Bandwidth estimation and transmission control: Estimate the available bandwidth of the network according to the reception of the feedback message from the receiver to update the transmission rate of the data segment; according to the number of data segments required by the chunk fed back by the receiver, control the remaining data of the chunk. Send to avoid redundant transmission of data; at the same time, remove the remaining data segments of the chunks that have been transmitted from the send buffer.2.根据权利要求1所述的一种基于纠删编码的数据传输控制方法，其特征在于，所述chunk检查内容如下：2. a kind of data transmission control method based on erasure correction coding according to claim 1, is characterized in that, described chunk checks content as follows:对于chunk i，i表示chunk序号；设当前发送端已经发送数据段的最大编号为S_i，已经收到确认的最大数据段编号为A_i；则该chunk已经发送但还未被确认的数据段总量为S_i-A_i；传输路径成功传输的比例的估计值为γ_i，则这些数据中有γ_i(S_i-A_i)的数据段能够被接收端收到；For chunk i, i represents the chunk sequence number; let the maximum number of the data segment that has been sent by the current sender be Si_{, and the maximum number of the data segment that has received confirmation is A i;} then the chunk has been sent but has not been confirmed The data segment The total amount is S_i -A_i ; the estimated value of the proportion of successful transmission of the transmission path is γ_i , then the data segments with γ_i (S_i -A_i ) in these data can be received by the receiver;若chunk还需O_i个数据段即可完成解码，则在γ_i(S_i-A_i)<O_i时，从chunk i中选择未被传输的编号最小的数据段发往接收端，并更新S_i；否则，继续在下一个尚未传输完成的chunk进行相同的数据段选择和控制。If the chunk still needs O_i data segments to complete the decoding, then when γ_i (S_i -A_i )<O_i , select the untransmitted data segment with the smallest number from the chunk i and send it to the receiver, and Update_Si ; otherwise, continue to perform the same data segment selection and control on the next chunk that has not yet been transmitted.3.根据权利要求1所述的一种基于纠删编码的数据传输控制方法，其特征在于，所述发送速率R的控制方法为：3. a kind of data transmission control method based on erasure correction coding according to claim 1, is characterized in that, the control method of described transmission rate R is:(1)发送速率R默认采用网络所支持的最大可用带宽Bw；(1) The sending rate R defaults to the maximum available bandwidth Bw supported by the network;(2)发送端连续的发送M个数据段，然后暂停；当发送端收到N个确认消息后，立即进行可用带宽Bw的估算：设第一个到达和最后一个达到确认消息之间的持续时间为T1；这些确认消息所确认的最小发送序号为A1，最大序号为A2；则当前路径的可用带宽估计值为N*v/T1，丢包率估计值为1-N/(A2-A1+1)；(2) The sender sends M data segments continuously, and then pauses; when the sender receives N acknowledgment messages, it immediately estimates the available bandwidth Bw: set the duration between the first arrival and the last acknowledgment message The time is T1; the minimum sending sequence number confirmed by these confirmation messages is A1, and the maximum sequence number is A2; then the estimated available bandwidth of the current path is N*v/T1, and the estimated packet loss rate is 1-N/(A2-A1 +1);(3)设网络路径非拥塞引发的丢包率阈值为loss，那么，如果1-N/(A2-A1+1)>loss，发送端将N*v/T1作为新的可用带宽Bw值；否则，表明带宽没被用满，可以增加发送速率，以N*v/T1*θ作为新的可用带宽Bw值，其中θ>1，代表发送速率的增大比例，是一个可配置的参数；(3) Set the packet loss rate threshold caused by non-congestion of the network path to loss, then, if 1-N/(A2-A1+1)>loss, the sender will use N*v/T1 as the new available bandwidth Bw value; Otherwise, it indicates that the bandwidth is not fully used, and the sending rate can be increased. N*v/T1*θ is used as the new available bandwidth Bw value, where θ>1, which represents the increase ratio of the sending rate, which is a configurable parameter;(4)如果最大接受时间T内没有收齐N个确认消息，则回到(2)；(4) If N confirmation messages are not received within the maximum acceptance time T, go back to (2);(5)当Bw完成首次估算后，发送端立即采用新的发送速率R进行数据段的发送；之后，每当收到一个确认消息时，发送端都基于最近收到的N个确认消息，进行同样的上述计算。(5) When Bw is estimated for the first time, the sender immediately uses the new sending rate R to send the data segment; after that, whenever an acknowledgment message is received, the sender will proceed based on the N recently received acknowledgment messages Same calculation above.4.根据权利要求3所述的一种基于纠删编码的数据传输控制方法，其特征在于，所述发送速率R的控制中，数据段数量M和确认信息数量N的取值根据采用不同网络而不同，且M>N。4. a kind of data transmission control method based on erasure correction coding according to claim 3, is characterized in that, in the control of described transmission rate R, the value of data segment quantity M and confirmation information quantity N according to adopt different network and different, and M>N.5.根据权利要求1所述的一种基于纠删编码的数据传输控制方法，其特征在于，所述纠删编码不限定具体编码方案。5 . The data transmission control method based on erasure correction coding according to claim 1 , wherein the erasure correction coding does not limit a specific coding scheme. 6 .

Images