RUDP(Reliable UDP) has been talked about recently in my communication with many friends in the field of real-time audio and video. It is actually a platitudine question. RUDP is used in many famous projects, such as Google’s QUIC and webRTC. On UDP to do a layer of reliability, many friends think this is a very unreliable thing, there are friends think this is a big kill, can solve most problems in the real-time field.

As an education company, high achiever students do use RUDP technology to solve our problems in many real-time scenarios, and we use RUDP differently in different scenarios. Let’s take a look at some of the situations where top students use RUDP:

  • RUDP + multi-point relay intelligent routing scheme is used for real-time 1V1 query with global 250 ms delay.
  • 500 ms 1080P video interactive system, using RUDP + PROXY scheduling transmission scheme.
  • A 6-way real-time synchronous writing system using RUDP+ Redo log reliable transfer technology.
  • The 720P same-screen transmission system of Pad under weak network Wi-Fi adopts RUDP +GCC real-time flow control technology.
  • Large live P2P distribution system saves more than 75% distribution bandwidth through RUDP + multi-point parallel relay technology.

When it comes to real-time transmission, we always consider RUDP first. RUDP is used in all aspects of the core transmission system for high-achieving students, but we have designed different RUDP approaches for different system scenarios, so based on those heated discussions and our experience in using RUDP, I will take a look at RUDP.

Triangle constraint

In fact, there is a triangular balance in the field of real-time communication: the constraint relation among cost, quality and delay:

Figure 1

That is to say, there is a triangular constraint (LEQ) relationship between the cost of investment, the quality obtained and the delay of communication, so the designer of real-time communication system will find a balance point under these three constraints. TCP belongs to the communication mode that guarantees the quality by increasing the delay and transmission cost. UDP is a communication method that sacrifices quality to ensure latency and cost, so RUDP is more likely to find such a balance in certain scenarios. How RUDP tries to find this balance point should be analyzed from RUDP’s reliable concepts and usage scenarios.

Concept of reliability

In the process of real-time communication, different demand scenarios have different requirements for reliability, which can be generally summarized into three definitions:

  • Try to be reliable: The receiver of the communication requires that the data of the sender arrive as intact as possible, but the data of the business itself may be allowed to be missing. For example: audio and video data, idempotent state data.
  • Unordered reliability: The receiver of a communication requires that the data from the sender must arrive intact, but in whatever order it arrives. For example, file transfer, whiteboard writing, real-time graph drawing data, log type additional data, etc.
  • Ordered reliability: the receiver of the communication requires that the data of the sender must arrive in order and complete.

RUDP determines its communication model and mechanism according to these three requirements and the triangular constraints in Figure 1, that is, to find the balance point of communication.

Why should UDP be reliable

Here may be a lot of people will say: why bother, just use TCP! TCP is a reliable communication protocol based on fairness, but in some harsh network conditions TCP either does not provide normal communication quality assurance or is too costly. The reason for making reliable guarantee over UDP is to reduce the cost as much as possible while ensuring the delay and quality of communication. RUDP mainly solves the following related problems:

  • End-to-end connectivity problem: generally, direct communication between terminals and terminals will involve NAT traversal. TCP is very difficult to achieve NAT traversal, while UDP traversal is much simpler. If end-to-end reliable communication is generally solved by RUDP, the scenarios are as follows: End-to-end file transfer, audio and video transmission, interactive instruction transmission and so on.
  • Transmission problem in weak network environment: In some Wi-Fi or 3G/4G mobile networks, reliable communication with low latency is required. If TCP communication is used, the delay may be very large, which will affect user experience. For example: real-time operational online game communication, voice dialogue, multi-party whiteboard writing, etc., these scenarios can adopt special RUDP method to solve these problems.
  • Bandwidth competition: Sometimes the client data upload needs to break through the limitations of TCP fairness to achieve high speed, low latency and stability, that is to say, special flow control algorithms are used to squeeze the client upload bandwidth, for example: RUDP can not only squeeze the bandwidth, but also improve the stability of communication and avoid frequent disconnection and reconnection like TCP.
  • Transmission path optimization problem: In some scenarios with high requirements on delay, the application layer relay is used to optimize the transmission route, namely, dynamic intelligent route selection. In this case, RUDP is used for transmission, and the intermediate delay is relay optimization delay. There is also a class of transmission throughput based scenarios, such as data distribution and data backup between services, which generally use multi-point parallel relay to improve transmission speed and are also based on RUDP (these two points will be described in detail later).
  • Resource optimization problem: In some scenarios, to avoid the TCP three-way handshake and four-way wave, RUDP is used to optimize resource utilization and response time and improve the concurrent capability of the system, such as QUIC.

No matter which kind of scenario, is to ensure reliability, that is, quality, so how to achieve reliability over UDP? The answer is retransmission.

The retransmission model

IP protocol is not designed for the reliable arrival of data, so UDP relies on retransmission to ensure reliability, which is also RUDP behavior in our common sense. Before describing RUDP retransmission, let’s first understand the basic framework of RUDP, as shown in the figure:

Figure 2

RUDP is divided into sender side and receiver side. Each RUDP will make different choices and simplification in the design, which is summarized as the unit in the figure. In RUDP retransmission, the sender retransmits data through the feedback of ACK packet loss information from the receiver. The sender designs its own retransmission mode according to the scenario. The retransmission mode can be divided into three types: timing retransmission, request retransmission and FEC selective retransmission.

Timing the retransmission

Timed retransmission is well understood. If the sender has not received an ACK message for the packet after sending it (T1), the sender will retransmit the packet. This mode relies on the ACK and RTO of the receiving end and is prone to misjudgment. There are two main cases:

  • The peer party received the packet, but the ACK was lost on the way.
  • The ACK is en route, but the sending time has exceeded one RTO.

Therefore, timeout retransmission mainly focuses on the CALCULATION of RTO. If your scenario is delay-sensitive but does not require high traffic cost, you can design the CALCULATION of RTO to be small, so as to ensure that your delay is small enough.

For example, real-time online games and writing synchronization in education are typical scenarios where expense swaps latency and quality. They are suitable for low-bandwidth and low-latency transmission. In real-time transmission with large bandwidth, scheduled retransmission consumes a lot of bandwidth. In extreme cases, the retransmission rate may be 20%. Therefore, the request retransmission mode is generally adopted in high-bandwidth mode.

Request retransmission

When receiving ACK information, the sender retransmits the ACK information based on the ACK feedback. The diagram below:

Figure 3

In this feedback process, the most critical step is the information about lost packets that should be carried when sending back ACK packets. Because UDP packets are out of order and jitter during network transmission, the receiver needs to evaluate the network Jitter time, that is, rTT_var (RTT variance). A time t1 is recorded when packet loss is detected. When T1 + rTT_var < curr_t(the current time), we consider it lost.

In this case, subsequent acks need to carry the packet loss information and update the packet loss time T2. Subsequently, the packet loss queue is continuously scanned. If T2 + RTO < CURr_T, the ACK carries the packet loss information again, and so on until the packet is received.

This method is retransmission caused by packet loss request. If the network is very bad, the receiver will continuously initiate retransmission request, causing the sender to continuously retransmit, causing network storm, and the communication quality will decline. Therefore, we design a congestion control module at the sender to limit traffic, which will be analyzed in the future.

The entire request retransmission mechanism depends on jitter Time and RTO. Evaluation and adjustment of these two parameters are closely related to the corresponding transmission scenario. Request retransmission has a longer delay than scheduled retransmission, and is suitable for transmission scenarios with high bandwidth, such as video, file transfer, and data synchronization.

FEC selects retransmission

In addition to timed retransmission and request retransmission modes, there is another way to select retransmission in FEC grouping mode. FEC (Forward Error Correction) is a kind of Forward Error Correction technology, which is generally realized by XOR algorithms. There are also multiple layers of EC algorithm and Raptor yongquan code technology, which is actually a process of solving equations. Application to RUDP is shown as follows:

Figure 4.

When the sender sends a packet, it groups several packets according to FEC mode, obtains several redundant packets through XOR mode, and then sends them to the receiver together. If the receiver finds that the packet is lost but can be restored through FEC grouping algorithm, it does not request retransmission to the sender. If the packet cannot be FEC recovered, the original packet is requested from the sender.

FEC is suitable for transmission scenarios that require time-sensitive and random packet loss. In a transmission with insufficient bandwidth, FEC will add redundant packets, which may worsen the network. The FEC mode can work with both the request retransmission mode and the scheduled retransmission mode.

Calculation of RTT and RTO

RTT, RTO and other Time measures are mentioned in the introduction of the retransmission mode. Round Trip Time (RTT) refers to the network loop delay, which is calculated by the sent packets and received ACK packets, as shown in the following diagram:

Figure 5

RTT = T2 – T1

This calculation method only calculates THE RTT of a certain message time, but the network will fluctuate, which will inevitably have noise phenomenon, so the method of weighted average convergence is introduced in the calculation process (refer to RFC793 for details).

SRTT = (α * SRTT) + (1-α)RTT

So that we can obtain approximate SRTT, general alpha = 0.8 in the formula, determine the SRTT, the next step is to calculate RTT_VAR (variance), we set RTT_VAR = | SRTT – RTT |. SRTT_VAR =(α * SRTT_VAR) + (1-α) RTT_VAR.

However, finally we need RTO, because it involves retransmission of packets. RTO is the retransmission period of a packet. It is easy to know from the network communication process that after retransmission of a packet, if the time after RTT+RTT_VAR has not been determined, then we can retransmit again. RTO = SRTT + SRTT_VAR.

However, the general network in the case of serious jitter will still have a large repetition rate problem, so: RTO = β*(SRTT + RTT_VAR), 1.2 <β<2.0, according to different transmission scenarios to select the value of β.

Windows and congestion control

RUDP guarantees reliability through retransmission. Retransmission in the triangle balance relationship is actually a behavior that uses expense and latency to exchange quality. Therefore, retransmission will cause two problems, one is delay and the other is retransmission bandwidth. Therefore, a window congestion mechanism is designed at the sending end to avoid excessive concurrent bandwidth usage.

window

RUDP requires a sliding window system for sending and receiving to coordinate with the corresponding congestion algorithm for flow control. Some RudPs require strict correspondence between the sending and receiving Windows, while others do not require strict correspondence between the sending and receiving Windows. If reliably ordered RUDP is involved, the receiver will do window sorting and buffering. If the scene is unordered and reliable, the receiver will generally do no window buffering and only position sliding. First, take a look at the relation diagram of the sending and receiving window:

Figure 6.

The figure above describes that the sender sends six data packets to the receiver from the sending window. When receiving 101,102,103,106, the receiver will first judge the continuity of the packets and slide the starting position of the window to 103. Then each packet responds with an ACK. And slide the window to 103, the sender will judge the window empty, and then fill in the new sent data, this is the whole window sliding process.

The value here refers to the processing when 106 is received by the receiving end. If it is orderly and reliable, 106 will not notify the upper-layer business for processing, but wait for 104 and 105. In the best-effort and out-of-order reliability scenarios, 106 is notified to upper-layer services for processing first. After receiving an ACK, how much the window of the sender will slide is determined by its own congestion mechanism, that is to say, the sliding speed of the window is controlled by the congestion mechanism. The congestion control is realized either based on the packet loss rate or the communication delay of both sides. The following are several typical congestion controls.

Classical congestion algorithm

Classic TCP congestion algorithm is divided into four parts: slow start, congestion avoidance, congestion control and fast recovery, this four parts are designed to decided to send window and sending speed, is actually to under the condition of the current network packet loss through the network to determine network congestion status, so as to determine the suit to send the transfer window.

The classical algorithm is based on timed retransmission. If RUDP adopts this algorithm to do congestion control, the general scenario is to ensure orderly and reliable transmission and take into account the fairness principle of network transmission. Let’s explain each of these parts one by one.

Slow start

When the link is just established, it is impossible to set the CWND too large at the beginning, which is easy to cause a lot of retransmission. In classical congestion, THE CWND will be set to 1 at the beginning, and then gradually expand the CWND according to the packet loss in the communication process to adapt to the current network state. Until the slow start threshold threshold (SSTHRESH) is reached, the steps are as follows:

  1. Initialize CWND = 1 and start transferring data.
  2. The CWND is added to the ACK after receiving the feedback.
  3. CWND = CWND * 2 when the sender has an RTT and there is no retransmission of lost packets.
  4. When CWND >= SSTHRESH or packet loss retransmission occurs, the slow start ends and the state of congestion avoidance enters.

Congestion avoidance

When the communication connection ends and the network is slowly started, it is possible that the network transmission speed is not online. In this case, further adaptation is required through a slow adjustment process. CWND = CWND + 1 if no packet loss is found after an RTT. When packet loss or timeout retransmission is detected, the system enters the congestion processing state.

Congestion control

CWND / 2 = CWND / 2, and then enter the fast recovery state.

Fast recovery

Fast recovery is determined by confirming that packet loss occurs in only one position of the window. As shown in Figure 6, if only 104 is lost and 105 and 106 are received, ACK always sets ACK base = 103, If three consecutive ACKS with base 103 are received, a quick recovery is performed, that is, 104 is immediately retransmitted. Then, if a new ACK is received and base > 103 is received, CWND = CWND + 1 and congestion avoidance enters the state.

Classical congestion control is designed based on packet loss detection and timed retransmission mode. In triangular balance, it is a typical case of latency in exchange for quality. However, due to its fairness design, it avoids excessive expense, which makes it difficult for this transmission mode to squeeze network bandwidth. It is difficult to guarantee the high throughput and hour delay of the network.

BBR congestion algorithm

Google designs a BBR congestion control algorithm based on transmitting delay and bandwidth evaluation for the delay and bandwidth squeezing problems of classical congestion algorithms. This congestion algorithm aims to solve two problems:

  • Make full use of bandwidth in network transmission link with certain packet loss rate
  • Reduce buffer latency in network transmission

The primary strategy of BBR is to periodically evaluate the MIN_RTT and max_bandwidth of a link through ACK and NACK returns. The maximum throughput (CWND) size is: CWND = max_bandwidth/min_rtt.

The transmission model is as follows:

Figure 7.

BBR congestion control is a state of detecting bandwidth and Pacing rate, which has four states:

  • Startup: indicates the Startup state (equivalent to slow Startup). The gain parameter is max_gain = 2.85
  • DRAIN: transfer at full load
  • PROBE_BW: Bandwidth assessment status, increasing (1.25) or decreasing (0.75) by a small BBR gain parameter
  • PROBE_RTT: Delay evaluation status, RTT sampling by maintaining a minimum send window (4 MSS)

So how do these states go back and forth? The general steps of BBR in QUIC are as follows:

  1. When the connection is initialized, an initial CWND = 8 is set and the state is set to Startup.
  2. Send data under Startup. Check whether the bandwidth can be increased periodically based on ACK data sampling. If yes, set CWND = CWND *max_gain. If the number of cycles exceeds the preset start cycle time or packet loss occurs, enter the DRAIN state.
  3. In DRAIN state, continue DRAIN if flight_size(size of data sent but not confirmed) > CWND, and enter PROBE_BW if flight_size< CWD.
  4. In the PROBE_BW state, if no packet loss occurs and flight_size< CWND * 1.25, keep the original CWND and start StartUp. If packet loss occurs, CWND = CWND * 0.75.
  5. In the Startup/DRAIN/PROBE_BW three states, if no RTT <= MIN_RTT occurs for 10 seconds, the state goes into PROBE_RTT and CWND = 4 *MSS.
  6. In the PROBE_RTT state, flight_size >= CWND is continuously checked when ACK returns and no packet is lost. The smallest RTT is set as MIN_RTT and the system enters the Startup state.

BBR periodically calculates CWND, which is the maximum throughput and minimum delay of the network, through the above steps, and then determines the bit rate of the sender at this moment through pacing rate, finally achieving the purpose of congestion control.

BBR is suitable for congestion in the case of random packet loss and stable network. If the network signal is extremely unstable on Wi-Fi or 4G, network flooding and inaccurate prediction are easy to occur. In terms of multi-connection fairness, BBR connections with small RTT consume more bandwidth than those with large RTT. The connection speed of large RTT is slow. The BBR congestion algorithm is a case of expense for latency and quality in a triangular equilibrium.

webRTC GCC

Speaking of audio and video transmission will inevitably think of webRTC system, in webRTC for video transmission is also implemented a congestion control algorithm (GCC), webRTC GCC is a congestion control based on the packet loss rate of the sender and the statistical delay bandwidth of the receiver, and is a reliable transmission algorithm, In the process of transmission, if a message is retransmitted too many times, it will be directly discarded, which is in line with the scene of video transmission. Let’s borrow a picture from Weizhenwei to see what it is:

Figure 8, source www.jianshu.com/u/102fafe8c…

The sender of GCC will set pacing rate according to the packet loss rate and a comparison table. When loss < 2%, the transmission bandwidth will be increased; when Loss >= 2%&& Loss <10%, the current bit rate will be maintained; When loss>=10%, the transmission overload will be considered and the transmission bandwidth will be reduced.

The receiving end of GCC delay variance and the size is according to the data to arrive KalmanFilter bandwidth approximation convergence, the details is not introduced, see http://www.jianshu.com/p/bb34995c549a.

It is worth mentioning that GCC introduces the receiver to evaluate the bandwidth by KalmanFilter, which is a very novel congestion control idea. If a reliable RUDP transmission system is implemented, it can be regarded as a good reference.

However, this algorithm also has a defect, that is, in the case of intermittent packet loss on the network, GCC may converge slowly, which may make REMB difficult to feed back to the sender to a certain extent and prone to flow control failure on the sender. GCC is a case study of quality and expense for latency in triangle balancing.

Weak window congestion mechanism

There are many scenarios in which congestion control is not required or only weak, such as: Both teachers and students write synchronous and real-time games. Since the amount of data transmitted is not large, as long as the delay and reliability are small enough, a fixed window size is generally adopted for flow control. In our system, a window such as CWND =32 is generally adopted for flow control. ACK confirmation is also fed back to the sender through the data status of the whole receiving window, which is simple and direct and easy to adapt to the weak network environment.

Transmission path

RUDP in addition to optimizing connection, squeezing bandwidth and adapting to weak network environment, it also inherits the natural dynamic of UDP, and can do transmission optimization on intermediate application layer link, which is generally divided into multi-point series optimization and multi-point parallel optimization. Let’s be specific.

Multipoint series relay

In real-time communication, some service scenarios are very sensitive to delay, such as real-time voice, synchronous writing, real-time interaction, and live communication. Simple service transfer or P2P communication is difficult to meet their requirements, especially in the case of a large physical distance.

SKYPE took the lead in proposing global RTN (Real-time multi-point Transmission network) to solve this problem, which is to dynamically and intelligently select routes between communication parties through several relay nodes. This transmission mode is very suitable for RUDP. As long as we build a RUDP channel between communication parties, An intermediate link is a stateless relay cache set. Relay agents detect and select routes to achieve high availability and real-time performance. The diagram below:

Figure 9.

Multi-relay relay is used to ensure that RUDP transfers are optimized. This scenario is a typical case of sacrificing at least for latency in triangle balancing.

Multipoint parallel relay

In the process of media data transmission or distribution between services, it is necessary to ensure high availability of transmission path and concurrent bandwidth. In such scenarios, a RUDP channel will be constructed by both sides of the transmission and solved through the parallel connection of multiple relay nodes, as shown in the figure below:

Figure 10.

This model need to design a multicast routing table in the sending end detection mechanism, in order to determine the availability and the proportion of the various paths to send data at the same time, the model in addition to increased link backup and concurrent transmission bandwidth, and an auxiliary function, if it is a streaming media distribution system, we usually use BGP for transshipment, if nodes and between nodes can be direct, This also reduces the footprint of BGP bandwidth, thus reducing costs.

Remember after

This is the end of RUDP’s introduction, with some details and scenario-related stuff, and it’s kind of an introductory science article. The concept of RUDP has been put forward for almost 20 years. Many practitioners hope to design a universal RUDP through a set of perfect solutions. I personally think it is not possible, and even if it is designed, it is estimated to be similar to the current TCP.

The value of RUDP lies in the selection of different technologies according to different transmission scenarios, such as loose congestion mode or specific retransmission mode. However, the selection is based on the trade-off between expense, latency, and quality. RUDP may be able to help developers find a better solution by combining scenarios and balancing triangles.

The authors introduce

Yuan Rongxi with honors student jun, a senior architect, 16 years of C programmers, P2P communication network and TCP/IP communication protocol stack and authentication encryption technology, joined in 2015 students with excellent grades, responsible for building intelligent routing of the students with excellent grades king real-time audio and video transmission systems and network, solve the problem of real-time audio and video communications.

Thanks to Yuta Tian guang for correcting this article.