Network programming for game developers. Part 4: Reliability, Streamlining, and Avoiding Overloads Over UDP
From the translator: I needed to deal with the work of UDP sockets in non-blocking mode in java and create my own class to work with network connections based on them. Unfortunately, I did not find sensible Russian-language documentation on this topic. But I came across several attempts at Habré to highlight the topic of creating a reliable connection over UDP. Including translation of several articles by Glenn Fiedler, made by the user bvasilyev . And although the articles consider the creation of such a connection to use it in games (not exactly what I need), and the language of the implementation is not java, but c ++, they became for me a starting point. Unfortunately , about a year ago, bvasilyev interrupted the translation of this cycle, and the most interesting remained in the original language. So I decided to translate the fourth article of the cycle and rewrite the implementation of the virtual connection from the third article of the cycle to java (I will post it later). Well, in order for this article to be used by anyone other than me, I post it here. Unfortunately, I never did professional translation, I always studied English documentation. But in this case, due to the numerous use of some words in completely different meanings, and also in the role of naming various definitions, repeatedly - within the same sentence, found it more expedient to make a translation, and after that work with the text in a familiar language. Amendments and reasoned suggestions are welcome.
First article
Second article
Third article
( remember : translated bvasilyev )
')
Hi, my name is Glenn Fiedler and I greet you in my fourth article in the series “Network Programming for Game Developers”.
In the previous article , we created our own concept of a virtual connection based on UDP.
Now we will add reliability, orderliness and prevention of overloads to our virtual UDP connection.
This is by far the hardest part of low-level networking in games, so this article will be very rich, so we buckled up and drove off!
Those of you who are familiar with TCP know that it already has its own internal concept of connections, with a reliable and streamlined packet transmission system and overload prevention, so why do we write our own mini TCP version based on UDP?
The problem is that action-type multiplayer games rely on a constant stream of packets sent from 10 to 30 packets per second, and for the most part, the data contained in these packets is so time sensitive that only the most recent data is useful. . This includes data from player input devices, the orientation position and speed of each character, and the state of physics of the objects in the game world.
The problem with TCP is its abstract data delivery to a reliable orderly flow. Because of this, if a packet is lost, TCP must stop and wait for the second packet to be forwarded. This interrupts the constant packet flow, which is why later packets have to wait in the queue until a re-sent packet is received, which makes it possible to line up the packets in the correct order.
What we need is a different type of reliability. Instead of seeing all the data as a well-ordered stream, we want to send packets at a constant speed and receive notifications about their reception by another computer. This allows you to deliver time-sensitive data without waiting for re-sent packets, while still allowing us to make decisions about how to handle packet loss at the application level.
It is not possible to create a reliable system with specified properties using TCP, so we have no choice but to create our own over UDP.
Unfortunately, reliability is not the only thing we need to rewrite. This is because TCP also provides congestion avoidance, so that it can dynamically change the speed of the transmitted data, in accordance with the properties of the connection. For example, TCP sends less data using a 28.8k modem than it would be on the T1 line, and he is able to do it without knowing in advance the type of connection!
Now back to reliability!
The goal of our reliability system is simple: we want to know which packets reach the other side of the connection.
First, we need a way to identify the packets.
What if we add the notion of “package identifier”? Let it be an integer. We could start it from scratch, and with each packet we send, increase that number by one. The first packet we would send would be “package 0”, and the 100th package sent is “package 99”.
In fact, this is a fairly common method. It is even used in TCP! These packet identifiers are called sequence numbers. And although we are not going to implement reliability exactly as TCP does, it makes sense to use the same terminology, therefore, from now on, we will call them serial numbers.
Since UDP does not guarantee the order of packets, 100 received packets does not necessarily mean that 100 packets have been sent. It follows that we need to insert a sequence number somewhere in the package, so that the computer at the other end of the connection knows exactly which package it is.
We already have a simple package header for the virtual connection from the previous article , so we just add the sequence number in the header. It will look like this:
Now, when the computer on the other side of the connection receives the packet, it knows its sequence number assigned by the sending computer.
Now that we can identify packets using sequence numbers, our next step is for the other side of the connection to know which packets we receive.
Logically, this is quite simple, you just need to take note of the sequence number of each packet received, and send these sequence numbers back to the computer that sent them.
Since we are constantly exchanging packets between two machines, we can simply add ack to the packet header, as we did with the sequence number:
Our overall approach is as follows:
This simple ack system works, provided that for every incoming packet there is a sent packet.
But what if the packages go so that the two packages arrive before we send the package? We only have room for one ack per package, so what do we do?
Now consider the case where one side of the connection sends packets at a faster rate. If the client sends 30 packets per second, and the server sends only 10 packets per second, we must put at least 3 ack in each packet sent from the server.
Let's complicate things even more! What if the package containing ack is lost? The computer that sent the original packet will think that it was lost, whereas in fact it was received!
Looks like we should make our reliable system ... more reliable!
Here we move away from the TCP protocol.
What TCP does is hold a sliding window for ack sent with a packet with the next sequence number — it expects to receive it in the specified order. If TCP does not receive ack acknowledgment for this packet, it stops and sends the packet with this sequence number again. This is exactly the behavior we want to avoid!
Thus, in our reliable system, we will never re-send a packet with a given sequence number. We send the packet with the number n exactly once, then we send n + 1, n + 2 and so on. If packet n has been lost, we will never stop to resend it, we will leave this to the application so that it forms a new packet containing data that was lost, if necessary, and this packet is sent with a new sequence number.
Since we are doing something different from TCP, it is now possible to have gaps (holes) in the set of packets for which we send ack, so now it’s not enough just to transmit the sequence number of the last packet we received.
We have to put several ack in one package.
How much ack do we need?
As mentioned earlier, we have a case where one side of a connection sends packets faster than the other. Let's assume that in the worst case one side sends at least 10 packets per second, while the other does not exceed 30. In this case, the average ack that we need in each packet is 3, but if the packets come in small heaps, then we may need more. Let's say 6-10 at worst.
How to deal with those ack that were not received due to the fact that the package containing them was lost?
To solve this problem, we are going to use the classic network redundancy strategy to defeat packet loss!
Let each package contain 33 ack, and it will not be possible to contain up to 33, but always 33. Thus, for any particular ack, we will send it up to 32 additional times with redundancy, in the event that one package with ack could not pass !
But how can we send 33 confirmations in the package? After all, 4 bytes for each ack is 132 bytes!
The trick is to represent up to “ack” 32 other ack using a bitfield:
We define the “ack bit field” so that each of its bits corresponds to the ack of those 32 sequence numbers that come before our “ack”. Let our “ack” 100. If the first bit of the “ack bit field” is set, then the packet also includes the ack for packet 99. If the second bit is set, then packet 98 will be confirmed. This goes all the way from 32 bits to packet 68 .
Our adjusted algorithm will look like this:
With this improved version of the algorithm, you will have to lose 100% of the packets for more than a second in order to start losing ack.
Now that we know that packets are received by the other side of the connection, how do we detect packet loss?
The trick here is that ack comes back to us, and we say: if we have not received confirmation within a certain time, then the package is considered lost.
Given that we send no more than 30 packets per second, and we redundantly send confirmation about 30 times, if you do not receive ack for a packet within one second, then it is very likely that the packet was lost.
So, with such a bit trick, we can be 100% sure which packages have reached and with a fair degree of confidence to assume that set of packages that was not received.
The consequence of this is that all the data that you re-send using this reliability technique must have your own message ID, so if you receive it several times, you can discard it. This can be done at the application level.
Discussion of sequence numbers and confirmations will not be complete without highlighting the issue of resetting the sequence numbers!
The sequence numbers and ack are 32-bit unsigned integers, so they are in the range [0.4294967295]. This is a very large number! So much so that if you send 30 packets per second, you will need more than four and a half years to exhaust this range and need to reset the sequence numbers.
But perhaps you want to save bandwidth, and reduce your sequence numbers and ack to 16-bit integers. You save 4 bytes in each packet, but now the range will be exhausted in just half an hour!
So how do we handle this?
The trick is to understand that if the current sequence number is already very large, and the next sequence number that has entered is very small, then you should start the counting of the sequence numbers again. So, although the new sequence number is numerically smaller than the current value of the sequence number, in fact it represents a later packet.
For example, suppose we encode sequence numbers in one byte (not recommended by the way :)), then they would be reset to zero after 255:
To cope in this case, we need a new function that knows that the sequence numbers will be reset to 255, so that 0, 1, 2, 3 are considered later than 255. Otherwise, our reliability system stops working after receiving package 255.
Here is the function:
This function works by comparing two numbers and their differences. If their difference is less than half the maximum value of the sequence number, then they should be close to each other - so we simply check if one number is more than another, as usual. However, if they are far from each other, their difference will be more than half the maximum value of the sequence number, then, paradoxically, we will consider a smaller sequence number than the current sequence number to be later.
This allows for the processing of zeroing sequence numbers in a transparent manner, so 0,1,2 are considered to be later than 255.
So simple and elegant!
Be sure to include this in any processing of sequence numbers you do.
While we have solved issues with reliability, there is still the issue of preventing overload. TCP provides overload prevention as part of the TCP reliability packet, but UDP has no means of overload prevention!
If we simply send packets without any control of the flow, we risk flooding the connection and cause a strong delay (more than two seconds!), Since the buffers of the routers between us and the other computer will be overloaded. This will happen because the routers will try very hard to deliver all the packets that we send, and therefore will put them in the buffer queue until they find it time to drop the packets.
Although it would be nice if we could tell the routers that our packets are very sensitive to time delays and should be dropped instead of buffering if the router is overloaded, we cannot do this without rewriting the software for all routers in the world!
So instead, we need to focus on what we can really do to avoid overflowing the communication channel in the first place.
The way to do this is to implement our own basic overload prevention algorithm. And I emphasize - the main! Just like with reliability, we have no hope on the first attempt to come up with something more suitable than in TCP, so let's make it as simple as possible.
Since all congestion avoidance comes down to avoiding connection overload and increasing the transit time (RTT), it turns out that the most important indicator of whether we are overloading the channel or not is RTT itself.
We need a way to measure our connection's RTT.
Here is the basic technique:
We now have an RTT and we can use it as a metric to guide our congestion avoidance. If RTT becomes too large, we send data less often, if it is within acceptable limits, we can try to send data more often.
As mentioned earlier, let's not be insatiable, we implement a very simple prevention of overload. This overload prevention has two modes. Good and bad. I call this simple binary overload prevention.
Let's assume that you are sending packets of a certain size, say 256 bytes. You would like to send these packets 30 times a second, but if conditions are bad, you can reduce the sending rate to 10 times a second.
So packets of 256 bytes 30 times per second will give a speed of about 64 kbps, and 10 times per second at about 20 kbps. There is no network connection in the world of broadband that cannot cope with at least 20kbit / s, so we will move forward with this assumption. Unlike TCP, which is generally adapted for any device with any receive / transmit bandwidth, we are going to make a minimum bandwidth allowance for devices participating in our connection.
Thus, the basic idea is as follows. When the network conditions are “good” we send 30 packets per second, and when the network conditions are “bad” we drop to 10 packets per second.
Of course, you can define “good” and “bad” the way you like it, but I got good results, considering only RTT. For example, if RTT exceeds a certain threshold (say, 250ms), then you know that you are probably overloading the connection. Of course, this assumes that no one will exceed 250 ms, under normal conditions, without connection overload, which are reasonable, given our broadband requirements.
How to switch between good and bad? The algorithm I like to use works as follows:
With this algorithm, you will quickly react to bad conditions and reduce the frequency of sending packets to 10 per second, avoiding channel overload. You will also conservatively try to switch to a good mode, and keep a higher frequency of sending packets - 30 per second, while the network conditions are good.
Of course, you can implement much more complex algorithms. So% packet loss can be taken into account, like the metric and even the value of network jitter (time of dispersion in packet acknowledgments), and not just RTT.
You can also show more greed with overload prevention, and try to find out when you can send data at a much higher bandwidth (for example, LAN), but you have to be very careful! With increasing greed there is a greater risk of overloading the connection!
Our new reliability system allows us to send a steady stream of packets and notifies us which packets were received. From this we can draw conclusions about the lost packets and resubmit data that was not received, if necessary.
On top of this, we have a simple overload prevention system that switches between sending packets 10 and 30 times per second, depending on network conditions, so we do not overload the connection.
There are many implementations of too specific details to mention in this article, so make sure you review the source code of the example to see how all this is implemented.
Reliability, ordering, and overload prevention are perhaps the most difficult aspect of low-level networks.
First article
Second article
Third article
( remember : translated bvasilyev )
')
Reliability, ordering and avoidance of overloading over UDP
Introduction
Hi, my name is Glenn Fiedler and I greet you in my fourth article in the series “Network Programming for Game Developers”.
In the previous article , we created our own concept of a virtual connection based on UDP.
Now we will add reliability, orderliness and prevention of overloads to our virtual UDP connection.
This is by far the hardest part of low-level networking in games, so this article will be very rich, so we buckled up and drove off!
TCP problems
Those of you who are familiar with TCP know that it already has its own internal concept of connections, with a reliable and streamlined packet transmission system and overload prevention, so why do we write our own mini TCP version based on UDP?
The problem is that action-type multiplayer games rely on a constant stream of packets sent from 10 to 30 packets per second, and for the most part, the data contained in these packets is so time sensitive that only the most recent data is useful. . This includes data from player input devices, the orientation position and speed of each character, and the state of physics of the objects in the game world.
The problem with TCP is its abstract data delivery to a reliable orderly flow. Because of this, if a packet is lost, TCP must stop and wait for the second packet to be forwarded. This interrupts the constant packet flow, which is why later packets have to wait in the queue until a re-sent packet is received, which makes it possible to line up the packets in the correct order.
What we need is a different type of reliability. Instead of seeing all the data as a well-ordered stream, we want to send packets at a constant speed and receive notifications about their reception by another computer. This allows you to deliver time-sensitive data without waiting for re-sent packets, while still allowing us to make decisions about how to handle packet loss at the application level.
It is not possible to create a reliable system with specified properties using TCP, so we have no choice but to create our own over UDP.
Unfortunately, reliability is not the only thing we need to rewrite. This is because TCP also provides congestion avoidance, so that it can dynamically change the speed of the transmitted data, in accordance with the properties of the connection. For example, TCP sends less data using a 28.8k modem than it would be on the T1 line, and he is able to do it without knowing in advance the type of connection!
Sequence numbers
Now back to reliability!
The goal of our reliability system is simple: we want to know which packets reach the other side of the connection.
First, we need a way to identify the packets.
What if we add the notion of “package identifier”? Let it be an integer. We could start it from scratch, and with each packet we send, increase that number by one. The first packet we would send would be “package 0”, and the 100th package sent is “package 99”.
In fact, this is a fairly common method. It is even used in TCP! These packet identifiers are called sequence numbers. And although we are not going to implement reliability exactly as TCP does, it makes sense to use the same terminology, therefore, from now on, we will call them serial numbers.
Since UDP does not guarantee the order of packets, 100 received packets does not necessarily mean that 100 packets have been sent. It follows that we need to insert a sequence number somewhere in the package, so that the computer at the other end of the connection knows exactly which package it is.
We already have a simple package header for the virtual connection from the previous article , so we just add the sequence number in the header. It will look like this:
[uint protocol id] [uint sequence] (packet data…) Now, when the computer on the other side of the connection receives the packet, it knows its sequence number assigned by the sending computer.
Acks
Now that we can identify packets using sequence numbers, our next step is for the other side of the connection to know which packets we receive.
Logically, this is quite simple, you just need to take note of the sequence number of each packet received, and send these sequence numbers back to the computer that sent them.
Since we are constantly exchanging packets between two machines, we can simply add ack to the packet header, as we did with the sequence number:
[uint protocol id] [uint sequence] [uint ack] (packet data...) Our overall approach is as follows:
- Every time we send a packet, we increase the local sequence number.
- When we receive a packet, we compare the sequence number of the packet with the sequence number of the recently received packet, called the remote sequence number. If the received packet number is larger, we update the deleted sequence number and set it to the received packet sequence number.
- When we compose the packet headers, the local sequence number becomes the sequence number of the packet, and the deleted sequence number becomes ack.
This simple ack system works, provided that for every incoming packet there is a sent packet.
But what if the packages go so that the two packages arrive before we send the package? We only have room for one ack per package, so what do we do?
Now consider the case where one side of the connection sends packets at a faster rate. If the client sends 30 packets per second, and the server sends only 10 packets per second, we must put at least 3 ack in each packet sent from the server.
Let's complicate things even more! What if the package containing ack is lost? The computer that sent the original packet will think that it was lost, whereas in fact it was received!
Looks like we should make our reliable system ... more reliable!
Reliable Acks
Here we move away from the TCP protocol.
What TCP does is hold a sliding window for ack sent with a packet with the next sequence number — it expects to receive it in the specified order. If TCP does not receive ack acknowledgment for this packet, it stops and sends the packet with this sequence number again. This is exactly the behavior we want to avoid!
Thus, in our reliable system, we will never re-send a packet with a given sequence number. We send the packet with the number n exactly once, then we send n + 1, n + 2 and so on. If packet n has been lost, we will never stop to resend it, we will leave this to the application so that it forms a new packet containing data that was lost, if necessary, and this packet is sent with a new sequence number.
Since we are doing something different from TCP, it is now possible to have gaps (holes) in the set of packets for which we send ack, so now it’s not enough just to transmit the sequence number of the last packet we received.
We have to put several ack in one package.
How much ack do we need?
As mentioned earlier, we have a case where one side of a connection sends packets faster than the other. Let's assume that in the worst case one side sends at least 10 packets per second, while the other does not exceed 30. In this case, the average ack that we need in each packet is 3, but if the packets come in small heaps, then we may need more. Let's say 6-10 at worst.
How to deal with those ack that were not received due to the fact that the package containing them was lost?
To solve this problem, we are going to use the classic network redundancy strategy to defeat packet loss!
Let each package contain 33 ack, and it will not be possible to contain up to 33, but always 33. Thus, for any particular ack, we will send it up to 32 additional times with redundancy, in the event that one package with ack could not pass !
But how can we send 33 confirmations in the package? After all, 4 bytes for each ack is 132 bytes!
The trick is to represent up to “ack” 32 other ack using a bitfield:
[uint protocol id] [uint sequence] [uint ack] [uint ack bitfield] (packet data...) We define the “ack bit field” so that each of its bits corresponds to the ack of those 32 sequence numbers that come before our “ack”. Let our “ack” 100. If the first bit of the “ack bit field” is set, then the packet also includes the ack for packet 99. If the second bit is set, then packet 98 will be confirmed. This goes all the way from 32 bits to packet 68 .
Our adjusted algorithm will look like this:
- Every time we send a packet, we increase the local sequence number.
- When we receive a package, we compare the sequence number of the package with the remote sequence number. If the received packet number is larger, we update the deleted sequence number and set it to the received packet sequence number.
- When we compose the packet headers, the local sequence number becomes the sequence number of the packet, and the deleted sequence number becomes ack. The ack bit field is calculated by viewing a queue of 33 packets containing sequence numbers in the range [remote sequence number — 32, remote sequence number]. We set the n bit in the bit field ([1.32]) to “1” if the sequence number of the packet is “remote sequence number –n” is in the received queue.
- In addition, when a packet is received, the ack bit field is scanned, and if bit n is set, then we confirm packet sequence number n if it has not been confirmed before.
With this improved version of the algorithm, you will have to lose 100% of the packets for more than a second in order to start losing ack.
Lost Packet Detection
Now that we know that packets are received by the other side of the connection, how do we detect packet loss?
The trick here is that ack comes back to us, and we say: if we have not received confirmation within a certain time, then the package is considered lost.
Given that we send no more than 30 packets per second, and we redundantly send confirmation about 30 times, if you do not receive ack for a packet within one second, then it is very likely that the packet was lost.
So, with such a bit trick, we can be 100% sure which packages have reached and with a fair degree of confidence to assume that set of packages that was not received.
The consequence of this is that all the data that you re-send using this reliability technique must have your own message ID, so if you receive it several times, you can discard it. This can be done at the application level.
Handling null sequence numbers
Discussion of sequence numbers and confirmations will not be complete without highlighting the issue of resetting the sequence numbers!
The sequence numbers and ack are 32-bit unsigned integers, so they are in the range [0.4294967295]. This is a very large number! So much so that if you send 30 packets per second, you will need more than four and a half years to exhaust this range and need to reset the sequence numbers.
But perhaps you want to save bandwidth, and reduce your sequence numbers and ack to 16-bit integers. You save 4 bytes in each packet, but now the range will be exhausted in just half an hour!
So how do we handle this?
The trick is to understand that if the current sequence number is already very large, and the next sequence number that has entered is very small, then you should start the counting of the sequence numbers again. So, although the new sequence number is numerically smaller than the current value of the sequence number, in fact it represents a later packet.
For example, suppose we encode sequence numbers in one byte (not recommended by the way :)), then they would be reset to zero after 255:
... 252, 253, 254, 255, 0, 1, 2, 3, ... To cope in this case, we need a new function that knows that the sequence numbers will be reset to 255, so that 0, 1, 2, 3 are considered later than 255. Otherwise, our reliability system stops working after receiving package 255.
Here is the function:
bool sequence_more_recent( unsigned int s1, unsigned int s2, unsigned int max) { return ( s1 > s2 ) && ( s1 - s2 <= max/2 ) || ( s2 > s1 ) && ( s2 - s1 > max/2 ); } This function works by comparing two numbers and their differences. If their difference is less than half the maximum value of the sequence number, then they should be close to each other - so we simply check if one number is more than another, as usual. However, if they are far from each other, their difference will be more than half the maximum value of the sequence number, then, paradoxically, we will consider a smaller sequence number than the current sequence number to be later.
This allows for the processing of zeroing sequence numbers in a transparent manner, so 0,1,2 are considered to be later than 255.
So simple and elegant!
Be sure to include this in any processing of sequence numbers you do.
Overload prevention
While we have solved issues with reliability, there is still the issue of preventing overload. TCP provides overload prevention as part of the TCP reliability packet, but UDP has no means of overload prevention!
If we simply send packets without any control of the flow, we risk flooding the connection and cause a strong delay (more than two seconds!), Since the buffers of the routers between us and the other computer will be overloaded. This will happen because the routers will try very hard to deliver all the packets that we send, and therefore will put them in the buffer queue until they find it time to drop the packets.
Although it would be nice if we could tell the routers that our packets are very sensitive to time delays and should be dropped instead of buffering if the router is overloaded, we cannot do this without rewriting the software for all routers in the world!
So instead, we need to focus on what we can really do to avoid overflowing the communication channel in the first place.
The way to do this is to implement our own basic overload prevention algorithm. And I emphasize - the main! Just like with reliability, we have no hope on the first attempt to come up with something more suitable than in TCP, so let's make it as simple as possible.
Transit Time Measurement (Round Trip Time - RTT)
Since all congestion avoidance comes down to avoiding connection overload and increasing the transit time (RTT), it turns out that the most important indicator of whether we are overloading the channel or not is RTT itself.
We need a way to measure our connection's RTT.
Here is the basic technique:
- For each package that is sent, we add an entry containing, in addition to the sequence number of the package, the time of its departure.
- Every time we get ack, we look at this record and find the difference in local time between the time it takes to receive ack and the time it takes to send a packet. This is RTT time for this package.
- Since The arrival of packets varies with jitter (jitter - phase jitter of the digital data signal - unwanted phase and / or frequency random deviations of the transmitted signal) of the network; RTT we calculate as a percentage the difference between our current RTT and RTT packet. 10%, in my opinion, seems good in practice. This is called the exponentially smoothed moving average, and it has the effect of smoothing deviations in RTT.
- To ensure that the queue of sent packets does not grow all the time, we will cancel sending packets when they exceed some maximum expected RTT. As mentioned in the previous section about reliability, it is quite likely that any package that ack did not arrive for a second was lost, so one second is a good value for the maximum RTT.
We now have an RTT and we can use it as a metric to guide our congestion avoidance. If RTT becomes too large, we send data less often, if it is within acceptable limits, we can try to send data more often.
Simple binary overload prevention
As mentioned earlier, let's not be insatiable, we implement a very simple prevention of overload. This overload prevention has two modes. Good and bad. I call this simple binary overload prevention.
Let's assume that you are sending packets of a certain size, say 256 bytes. You would like to send these packets 30 times a second, but if conditions are bad, you can reduce the sending rate to 10 times a second.
So packets of 256 bytes 30 times per second will give a speed of about 64 kbps, and 10 times per second at about 20 kbps. There is no network connection in the world of broadband that cannot cope with at least 20kbit / s, so we will move forward with this assumption. Unlike TCP, which is generally adapted for any device with any receive / transmit bandwidth, we are going to make a minimum bandwidth allowance for devices participating in our connection.
Thus, the basic idea is as follows. When the network conditions are “good” we send 30 packets per second, and when the network conditions are “bad” we drop to 10 packets per second.
Of course, you can define “good” and “bad” the way you like it, but I got good results, considering only RTT. For example, if RTT exceeds a certain threshold (say, 250ms), then you know that you are probably overloading the connection. Of course, this assumes that no one will exceed 250 ms, under normal conditions, without connection overload, which are reasonable, given our broadband requirements.
How to switch between good and bad? The algorithm I like to use works as follows:
- If you are currently in good mode, and conditions are deteriorating, immediately go into bad mode.
- If you are in a bad mode and the conditions were good for a certain period of 't', then return to a good mode.
- To avoid fast switching between good and bad modes, if you switch from good mode to bad mode in 10 seconds, double the time 't', through which bad mode can return to good mode. Limit the maximum time value 't' to some maximum, say, 60 seconds.
- To avoid a break in a good communication mode, when it has short periods of bad connection, for every 10 seconds that the connection is in good mode, shorten the time 't' by half. Limit the minimum time value 't' to some minimum, say, 1 second.
With this algorithm, you will quickly react to bad conditions and reduce the frequency of sending packets to 10 per second, avoiding channel overload. You will also conservatively try to switch to a good mode, and keep a higher frequency of sending packets - 30 per second, while the network conditions are good.
Of course, you can implement much more complex algorithms. So% packet loss can be taken into account, like the metric and even the value of network jitter (time of dispersion in packet acknowledgments), and not just RTT.
You can also show more greed with overload prevention, and try to find out when you can send data at a much higher bandwidth (for example, LAN), but you have to be very careful! With increasing greed there is a greater risk of overloading the connection!
Conclusion
Our new reliability system allows us to send a steady stream of packets and notifies us which packets were received. From this we can draw conclusions about the lost packets and resubmit data that was not received, if necessary.
On top of this, we have a simple overload prevention system that switches between sending packets 10 and 30 times per second, depending on network conditions, so we do not overload the connection.
There are many implementations of too specific details to mention in this article, so make sure you review the source code of the example to see how all this is implemented.
Reliability, ordering, and overload prevention are perhaps the most difficult aspect of low-level networks.
Source: https://habr.com/ru/post/276067/
All Articles