Network programming for game developers. Part 3: virtual connections over UDP
From the translator: This is a translation of the third article in the series "Networking for game programmers" . I really like the whole series of articles, plus I always wanted to try myself as a translator. Perhaps an experienced developers article seems too obvious, but, as it seems to me, the benefits of it in any case will be.
The first article is http://habrahabr.ru/post/209144/
The second article - http://habrahabr.ru/post/209524/
Hey. My name is Glenn Fiedler and I greet you in the third article in the series “Network Programming for Game Developers”.
In the previous article, we figured out how to send and receive packets using the UDP protocol.
Since UDP does not support connections, one UDP socket can be used to exchange packets with any number of remote computers. However, in multiplayer games, as a rule, we exchange information with only a few nodes.
')
As a first step towards the implementation of the connection system, we consider the simplest case: the creation of a virtual connection between two computers.
But first, we need to more tightly understand how the Internet works.
In 2006, Senator Ted Stevens entered the history of the Internet with his famous speech on the Network Neutrality Act:
When I first started using the Internet, I thought the same way as Ted. Sitting in the computer classroom at the University of Sydney in 1995, I “surfed the internet” with the help of a newfangled thing called Netscape Navigator, and had no idea what was really going on there.
Then I thought that every time I connected to a site, a real connection was created, like during a telephone conversation. And I thought - how much does it cost to connect to the site? Thirty cents? Dollar? Will anyone from the university demand money from me for long-distance connections? :)
Of course, now it all sounds ridiculous.
There is no remote, which is somewhere and directly connects you with a telephone wire to another computer to which you want to connect, no sets of pipes, which told us Senator Stevens.
Instead of all this, your data is sent over IP in packets that run from computer to computer.
A packet can go through several nodes until it reaches the destination. You cannot know in advance the number of these nodes, as it changes dynamically, depending on how the network decides to forward packets. Even if you send two packages A and B to the same address, they can go in different ways. This, by the way, is the reason for the lack of guaranteed delivery of packets in order in UDP.
In unix-like systems, you can examine the packet paths with the “traceroute” utility, passing it the host name or IP address.
In windows, tracert is used instead of traceroute.
Try to analyze routes to several sites, for example:
Look at the results of the utility, and you, I think, immediately make sure that there are no direct connections to the sites.
In the first article of the cycle, I gave a simple analogy of the package delivery process - like passing a note from one person to another in a room full of people.
Although this analogy reflects the general idea, it is too simplified. The Internet is not a simple peer-to-peer network, but a network of networks. And, of course, we need to send notes not within the room, but to anywhere in the world!
Obviously, a lot better analogy is ... postal service!
When you want to send someone a letter, you put it in the mailbox, and at the same time you are sure that it will come to the address. It does not matter for you exactly how it will be delivered, but the fact of delivery is important. Of course, someone must physically deliver the letter - but how?
Obviously, the postman will not deliver your letter himself - the postal service is also not a set of pipes :). Instead, he will take your letter to the post office for further processing.
If the addressee of the letter lives in the same area as you, then at the post office your letter will simply be given to another postman, and he will assign it. But if not, the more interesting process begins. Your local post office cannot deliver the letter on its own, and it passes it “higher” through the hierarchy - to the regional office or postal center at the airport if the addressee is far away. In the ideal case, your letter will be taken in a big truck (referring to the speech of that senator - approx. Transl.).
Let's take a hard case - let's say we send a letter from Los Angeles to Sydney in Australia. The local post office receives a letter, determines that it must be delivered abroad, and sends it to the postal center at Los Angeles airport. They process the address of the letter again, and send it by the nearest flight to Sydney.
The plane with a letter sits in Sydney, where a new postal service enters, and does all the same operations, but in reverse order. The letter goes "down" in the hierarchy, from the general to the particular. From the mail sorting point at the airport, it gets to the regional office, which, in turn, sends it to the local post office, and finally the postman (with a funny accent) hands the letter to the addressee. Wonderful! :)
Just as the post office determines how to deliver a letter, based on the analysis of the recipient's address, packets in the network are delivered based on the analysis of the IP address. The process of determining the route for transmitting a packet is rather complicated, but the basic idea is that each router is the same computer that has a routing table that determines where to send packets with specific destination addresses and the default gateway address to send packets for which there was no matching entry in the routing table. All this together makes up the very “network of networks” - the Internet.
Setting up routing tables is a task for network administrators, not developers (that is, us). But if you want to learn more about this, then this article from ars technica magazine has a lot of interesting information about how networks exchange packets using peering and peering agreements. You can also read about the routing tables in this linux faq, and the border gateway protocol (BGP) in wikipedia, which automatically determines how to forward packets between networks — which makes the Internet a truly distributed system with the ability to dynamically bypass corrupted communication channels.
Now back to the topic of connections.
If you have already worked with TCP sockets, then you know that working with them is similar to working with connections, however, since TCP runs on top of IP, and IP can only forward individual packets, TCP should have a virtual connection mechanism.
And if TCP implements a virtual connection mechanism, it means that we can implement it using UDP.
Also, let's define the term “virtual connection” as the exchange of UDP packets between two computers with a fixed frequency - say, ten packets per second. As long as the packet exchange continues, the virtual connection is considered established.
The connection has two ends:
In our case, only one client will be able to connect to the server at a time. In future articles, we will refine the code so that the server can support several connections at once. We also assume that the server will always have a public IP address, and the client can connect to it directly. We will also discuss the topic of work through NAT in the following articles.
Since UDP itself does not support connections, a UDP socket can receive packets from any computer.
We need to limit this behavior so that the server accepts packets only from its client, and the client only from the server. Nor can we simply filter packets at the sender’s address, since the server cannot know the addresses of the clients in advance. Therefore, at the beginning of each UDP packet, we will add a small header 32 bits long, in which the unique identifier of the protocol will be stored.
A protocol identifier is simply a unique number chosen for our protocol. As soon as the UDP socket accepts the packet, it should immediately analyze the first four bytes of the packet. If the data does not match our identifier, then the packet is discarded. If matched, then these four bytes are truncated, and the rest of the packet data is sent for processing.
You need to select a protocol identifier so that it is likely to be unique - for example, you can take a hash from the name of the game and the version number of the protocol. Although by the way, you can take any number you want. The point of the whole idea from the point of view of our protocol is to discard packets that do not have our chosen identifier.
Next, we need to come up with a method for determining the presence of a compound.
Of course, we could come up with some complicated scheme with “handshakes” and sending several UDP packets back and forth. For example, the following: the client sends the “Request Connection” packet to the server, and the server responds to it either with the “Connection established” packet or “Busy” if the client tries to connect to a server that already has a connection with another client.
... or we could simply program the server so that after receiving the first packet with the correct protocol identifier, it would immediately assume that the connection is established.
In this case, the client can simply start forwarding packets to the server (assuming that the connection is already established), and when the server accepts the first packet, it will save the client’s IP address and port, and also start sending packets.
In this case, the client, of course, knows in advance the IP address and port of the server, as it connects first. Therefore, when a client receives packets in response from the server, it can filter them by the address. Similarly, the server after receiving the first packet from the client can take the address and port of the client from the “recvfrom” function, and filter all other packets that will not come from the client.
We can use this scheme because we have only two computers to connect. In future articles, we will improve our connection implementation in such a way that it supports data exchange between more than two computers (like client-server or peer-to-peer), and improve the invented algorithm for filtering connections.
But for the time being we will not complicate more and more than necessary.
And how do we determine the shutdown?
Well, since we defined the connection as a packet transfer process, we can also define disconnection as the absence of packet transfer.
To determine, in turn, the absence of packet transmission, we must monitor the number of seconds since the last packet was received from the other side, on both computers.
Every time we receive a packet from another computer, we reset this counter, and in each new game cycle we increase its value by the number of seconds since the last cycle.
If the counter exceeds a certain threshold, for example, ten seconds, we consider this a “time-out” of the connection and close it.
This algorithm also takes into account the case when a client tries to connect to a server that already has a connection with another client. Since the server already has a connection, it drops all packets from addresses other than the address of the connected client, and therefore the second client (the one that tries to connect) does not receive response packets from the server, and its connection is disconnected due to a timeout.
So, here's what is required to create a virtual connection: the algorithm for establishing a connection, filtering non-participating packets, and a timeout mechanism for determining outages.
Our connection is as real as any TCP connection, and the UDP packet it provides is enough for use in our future multiplayer action.
In the article, we also discussed a bit how packet routing on the Internet works. For example, we have learned the reason why UDP packets sometimes do not come in the correct order - because they can go different routes at the IP level. Look at the map of the Internet - is it any wonder that the packages even go somewhere else? If you want a better understanding of all this, a good starting point can be this article on wikipedia .
Now that we have a virtual connection mechanism over UDP, we can easily implement the data exchange between the client and the server for our multiplayer game — and without using TCP.
You can see an example implementation in the source code for this article.
This is a simple client-server application that exchanges packets at a rate of 30 packets per second. You can run the server on any machine, but with a public IP address, since packet forwarding via NAT is not supported yet.
You can start the client as follows:
In this case, it will try to connect to the server at the address you provide on the command line. By default, if you do not specify anything, it will try to connect to 127.0.0.1.
If one client is connected to the server, you can try to launch another client, and then you will see that it will not be able to connect - this is how it was intended. In this implementation, only one client can be connected to the server.
You can also try to stop the client or server when a connection is established between them, and then you will notice that after ten seconds, the application on the other side disconnects due to a timeout. When the client is disconnected, control is returned to the shell, and when the server is disconnected, it returns to the pending state of connections from other clients.
The first article is http://habrahabr.ru/post/209144/
The second article - http://habrahabr.ru/post/209524/
Virtual connections over UDP
Introduction
Hey. My name is Glenn Fiedler and I greet you in the third article in the series “Network Programming for Game Developers”.
In the previous article, we figured out how to send and receive packets using the UDP protocol.
Since UDP does not support connections, one UDP socket can be used to exchange packets with any number of remote computers. However, in multiplayer games, as a rule, we exchange information with only a few nodes.
')
As a first step towards the implementation of the connection system, we consider the simplest case: the creation of a virtual connection between two computers.
But first, we need to more tightly understand how the Internet works.
The Internet is not a collection of pipes
In 2006, Senator Ted Stevens entered the history of the Internet with his famous speech on the Network Neutrality Act:
“The Internet is not a thing in which you can put something. Not a big truck. This is a set of pipes. ”
When I first started using the Internet, I thought the same way as Ted. Sitting in the computer classroom at the University of Sydney in 1995, I “surfed the internet” with the help of a newfangled thing called Netscape Navigator, and had no idea what was really going on there.
Then I thought that every time I connected to a site, a real connection was created, like during a telephone conversation. And I thought - how much does it cost to connect to the site? Thirty cents? Dollar? Will anyone from the university demand money from me for long-distance connections? :)
Of course, now it all sounds ridiculous.
There is no remote, which is somewhere and directly connects you with a telephone wire to another computer to which you want to connect, no sets of pipes, which told us Senator Stevens.
No direct connections
Instead of all this, your data is sent over IP in packets that run from computer to computer.
A packet can go through several nodes until it reaches the destination. You cannot know in advance the number of these nodes, as it changes dynamically, depending on how the network decides to forward packets. Even if you send two packages A and B to the same address, they can go in different ways. This, by the way, is the reason for the lack of guaranteed delivery of packets in order in UDP.
In unix-like systems, you can examine the packet paths with the “traceroute” utility, passing it the host name or IP address.
In windows, tracert is used instead of traceroute.
Try to analyze routes to several sites, for example:
traceroute slashdot.org traceroute amazon.com traceroute google.com traceroute bbc.co.uk traceroute news.com.au Look at the results of the utility, and you, I think, immediately make sure that there are no direct connections to the sites.
How are packages delivered?
In the first article of the cycle, I gave a simple analogy of the package delivery process - like passing a note from one person to another in a room full of people.
Although this analogy reflects the general idea, it is too simplified. The Internet is not a simple peer-to-peer network, but a network of networks. And, of course, we need to send notes not within the room, but to anywhere in the world!
Obviously, a lot better analogy is ... postal service!
When you want to send someone a letter, you put it in the mailbox, and at the same time you are sure that it will come to the address. It does not matter for you exactly how it will be delivered, but the fact of delivery is important. Of course, someone must physically deliver the letter - but how?
Obviously, the postman will not deliver your letter himself - the postal service is also not a set of pipes :). Instead, he will take your letter to the post office for further processing.
If the addressee of the letter lives in the same area as you, then at the post office your letter will simply be given to another postman, and he will assign it. But if not, the more interesting process begins. Your local post office cannot deliver the letter on its own, and it passes it “higher” through the hierarchy - to the regional office or postal center at the airport if the addressee is far away. In the ideal case, your letter will be taken in a big truck (referring to the speech of that senator - approx. Transl.).
Let's take a hard case - let's say we send a letter from Los Angeles to Sydney in Australia. The local post office receives a letter, determines that it must be delivered abroad, and sends it to the postal center at Los Angeles airport. They process the address of the letter again, and send it by the nearest flight to Sydney.
The plane with a letter sits in Sydney, where a new postal service enters, and does all the same operations, but in reverse order. The letter goes "down" in the hierarchy, from the general to the particular. From the mail sorting point at the airport, it gets to the regional office, which, in turn, sends it to the local post office, and finally the postman (with a funny accent) hands the letter to the addressee. Wonderful! :)
Just as the post office determines how to deliver a letter, based on the analysis of the recipient's address, packets in the network are delivered based on the analysis of the IP address. The process of determining the route for transmitting a packet is rather complicated, but the basic idea is that each router is the same computer that has a routing table that determines where to send packets with specific destination addresses and the default gateway address to send packets for which there was no matching entry in the routing table. All this together makes up the very “network of networks” - the Internet.
Setting up routing tables is a task for network administrators, not developers (that is, us). But if you want to learn more about this, then this article from ars technica magazine has a lot of interesting information about how networks exchange packets using peering and peering agreements. You can also read about the routing tables in this linux faq, and the border gateway protocol (BGP) in wikipedia, which automatically determines how to forward packets between networks — which makes the Internet a truly distributed system with the ability to dynamically bypass corrupted communication channels.
Virtual connections
Now back to the topic of connections.
If you have already worked with TCP sockets, then you know that working with them is similar to working with connections, however, since TCP runs on top of IP, and IP can only forward individual packets, TCP should have a virtual connection mechanism.
And if TCP implements a virtual connection mechanism, it means that we can implement it using UDP.
Also, let's define the term “virtual connection” as the exchange of UDP packets between two computers with a fixed frequency - say, ten packets per second. As long as the packet exchange continues, the virtual connection is considered established.
The connection has two ends:
- The first computer is waiting for a connection from another computer - this computer will be called a server.
- The second computer connects to the server with a specific IP address and port. This computer will be called a client.
In our case, only one client will be able to connect to the server at a time. In future articles, we will refine the code so that the server can support several connections at once. We also assume that the server will always have a public IP address, and the client can connect to it directly. We will also discuss the topic of work through NAT in the following articles.
Protocol ID
Since UDP itself does not support connections, a UDP socket can receive packets from any computer.
We need to limit this behavior so that the server accepts packets only from its client, and the client only from the server. Nor can we simply filter packets at the sender’s address, since the server cannot know the addresses of the clients in advance. Therefore, at the beginning of each UDP packet, we will add a small header 32 bits long, in which the unique identifier of the protocol will be stored.
[ID uint] ( ...) A protocol identifier is simply a unique number chosen for our protocol. As soon as the UDP socket accepts the packet, it should immediately analyze the first four bytes of the packet. If the data does not match our identifier, then the packet is discarded. If matched, then these four bytes are truncated, and the rest of the packet data is sent for processing.
You need to select a protocol identifier so that it is likely to be unique - for example, you can take a hash from the name of the game and the version number of the protocol. Although by the way, you can take any number you want. The point of the whole idea from the point of view of our protocol is to discard packets that do not have our chosen identifier.
Determining whether a compound is present
Next, we need to come up with a method for determining the presence of a compound.
Of course, we could come up with some complicated scheme with “handshakes” and sending several UDP packets back and forth. For example, the following: the client sends the “Request Connection” packet to the server, and the server responds to it either with the “Connection established” packet or “Busy” if the client tries to connect to a server that already has a connection with another client.
... or we could simply program the server so that after receiving the first packet with the correct protocol identifier, it would immediately assume that the connection is established.
In this case, the client can simply start forwarding packets to the server (assuming that the connection is already established), and when the server accepts the first packet, it will save the client’s IP address and port, and also start sending packets.
In this case, the client, of course, knows in advance the IP address and port of the server, as it connects first. Therefore, when a client receives packets in response from the server, it can filter them by the address. Similarly, the server after receiving the first packet from the client can take the address and port of the client from the “recvfrom” function, and filter all other packets that will not come from the client.
We can use this scheme because we have only two computers to connect. In future articles, we will improve our connection implementation in such a way that it supports data exchange between more than two computers (like client-server or peer-to-peer), and improve the invented algorithm for filtering connections.
But for the time being we will not complicate more and more than necessary.
Trip detection
And how do we determine the shutdown?
Well, since we defined the connection as a packet transfer process, we can also define disconnection as the absence of packet transfer.
To determine, in turn, the absence of packet transmission, we must monitor the number of seconds since the last packet was received from the other side, on both computers.
Every time we receive a packet from another computer, we reset this counter, and in each new game cycle we increase its value by the number of seconds since the last cycle.
If the counter exceeds a certain threshold, for example, ten seconds, we consider this a “time-out” of the connection and close it.
This algorithm also takes into account the case when a client tries to connect to a server that already has a connection with another client. Since the server already has a connection, it drops all packets from addresses other than the address of the connected client, and therefore the second client (the one that tries to connect) does not receive response packets from the server, and its connection is disconnected due to a timeout.
Conclusion
So, here's what is required to create a virtual connection: the algorithm for establishing a connection, filtering non-participating packets, and a timeout mechanism for determining outages.
Our connection is as real as any TCP connection, and the UDP packet it provides is enough for use in our future multiplayer action.
In the article, we also discussed a bit how packet routing on the Internet works. For example, we have learned the reason why UDP packets sometimes do not come in the correct order - because they can go different routes at the IP level. Look at the map of the Internet - is it any wonder that the packages even go somewhere else? If you want a better understanding of all this, a good starting point can be this article on wikipedia .
Now that we have a virtual connection mechanism over UDP, we can easily implement the data exchange between the client and the server for our multiplayer game — and without using TCP.
You can see an example implementation in the source code for this article.
This is a simple client-server application that exchanges packets at a rate of 30 packets per second. You can run the server on any machine, but with a public IP address, since packet forwarding via NAT is not supported yet.
You can start the client as follows:
./Client 205.10.40.50 In this case, it will try to connect to the server at the address you provide on the command line. By default, if you do not specify anything, it will try to connect to 127.0.0.1.
If one client is connected to the server, you can try to launch another client, and then you will see that it will not be able to connect - this is how it was intended. In this implementation, only one client can be connected to the server.
You can also try to stop the client or server when a connection is established between them, and then you will notice that after ten seconds, the application on the other side disconnects due to a timeout. When the client is disconnected, control is returned to the shell, and when the server is disconnected, it returns to the pending state of connections from other clients.
Source: https://habr.com/ru/post/213559/
All Articles