July 8, 2013

GSoC project: The network for you to play online !

Hello world ! my name is Robin Nicollet, alias hilnius, and I'm a GSoC student working on your favorite open-source game ;) I'm going to present you why I'm here and what I'll try to add to SuperTuxKart.

Abstract

First of all, I'd like to thank STK's mentors for choosing me, it's a great honor to work on that project, and I'll do everything possible to make this game as good as possible. I'd also like to say that the community that I found here is amazing, I feel that everybody is welcome here and that's great to have such a good atmosphere.

Presentation

Me

I'm a french student from Télécom-Bretagne, I just finished my first year in this school (2 more and i'll have a master). I've been programming in C then C++ for about 5 years. I know more programming languages but that's not really relevant for this project.

My project

My project is to bring to this game the main features that allow people to play together online. To be quick, that means:
  • Connecting people in LAN (Local Area Networks) or WAN (Wide Area Networks : all over the world).
  • Starting games and playing together.
One of the main features to play on WAN is the lag compensation, which I won't tackle here for timing reasons :) .

If you just wanted to know what i'll do, you're down at this stage.
In the next sections, I'll detail how the connection between people will work and explain some things about network that are necessary to understand my solution. I will talk about playing together later in the summer when that will be implemented and working ;)

Connecting people

Situation

You may or may not know, but SuperTuxKart do not own a private server and cannot deploy a proper and classic client-server architecture. That's why we will ask SuperTuxKart's player to host their own games. As a result, we will provide inside the game an accessible interface that will allow you to start a server on your own computer to host races.

NAT issues

In this part i'll explain details about how NAT (Network Address Translation) works so that you will have a better understanding of IP networks and how connection will work.
I will use NAT to name the devices that does the Network Address Translation.

Your local configuration

Your local configuration at home probably looks like this:

You are in the Local Network. You are behind a first NAT (it is probably a box that you either borrowed or bought to your ISP (Internet Service Provider). Then, your ISP has his own network, with a lot of devices. Then he has his own NAT.

You may wonder: what is Network Address Translation ?

Network Address Translation

(If you want a fully detailed answer, you can read the wikipedia article)
Network Address Translation is a process used first to extend the number of available IPv4 addresses. Your three computers probably have IPv4 addresses matching the formats 10.xxx.xxx.xxx, 172.16-31.xxx.xxx or 192.168.xxx.xxx.
This does not identify you uniquely over the internet, thousands of people have the same address. It identifies you uniquely only in the Local Network. You should also know that each interface of a connected device has its own IP. For example, your NAT has at least two interfaces : one in the LAN network, and one in the ISP network. Each one of them has its own IP address.
What your NAT does, is that each time you send a message on internet (get a web page, connect to a server, anything...), it changes the IPv4 address in that message to its own. A quick drawing will help me explain that :

Request

Your computer sends a message (get the google.fr webpage) and puts his own local address. Then all NAT that stands on the way of the message will "translate" this address. That means they will memorize the IP of the sender, and replace it by their own.
So for example, when the message is in the ISP network, the IP address of the sender written inside the message is the one of your Router/NAT. And when the message travels in the public internet, the IP address of the sender written in the message is the one of the ISP NAT.

Response

When the google server receives that request, it answers to the IP written in the request (the one of your ISP NAT).
But the ISP NAT knows who sent that message in the first place (10.2.3.4). So the ISP NAT will send the response to 10.2.3.4. Same for your NAT/Router, which knows that it's you who made the request (and then doesn't send the response to your computers 1 and 3).

Conclusion ?

You can now understand that if google sends a message to your public address (that is the one of your ISP NAT), that ISP NAT won't know that you're the one who should receive the message, and then cannot route the message.
As a result, if you try to send a message to anybody who is not directly in the "public internet", he won't receive your message.
The solution to that is the STUN protocol and will be detailed in the next section

The STUN Protocol

This protocol carries well its name, because STUN means Simple Traversal of UDP through NATs. Our goal is indeed to establish a connection between two users, let's say Alice and Bob, each of who are behind their local NAT and their ISP NAT. You can find a complete RFC of the protocol here.

How stun works

STUN is very simple : there are STUN servers in the public internet. You send a STUN request to one of those servers, and it will send you a STUN response telling you your public address. If you understood well how address translation works, you'll notice that when the STUN server receives your request, the sender's IP address is your ISP NAT's one. In the response, that server will tell you : "you have a public IP address that is A and a public port which is P.".

If you're asking yourself what is a port, you can see it as how the NATs identify you. If you send a message to the STUN server, the ISP NAT will give you a port number and put it in the message. Then the STUN server will respond to the couple (sender's ip, sender's port). The ISP NAT will know that the port has been allocated to you and will send the response to your local NAT.

As you see, NATs use "NAT tables" to have ip:port bindings and know where they have to forward packets.
You can see that the STUN response received by your computer contains the ISP NAT's IP address and port number.
A detail worth mentioning: some NAT, called symmetric NATs, allocate a specific port for each connection, and do not allow this protocol to work. It's basically a security feature. So I'm sad to tell that it's very likely that you won't be able to play SuperTuxKart online in a company environment (symmetric NATs are used usually by companies).

Imagine now, Alice and Bob want to communicate. Alice and Bob obtain their own public address (which is their ISP's NAT IP address). Now Alice calls bob with her phone and says "hi bob, my public address is A-A and the associated port is P-A". Bob answers and says "Hey Alice, my public address is A-B and the associated port is P-B". Then if Alice sends a message to the address A-B on the port P-B, Bob will receive the message, because his ISP NAT will know that this IP:port couple is bind to Bob's local NAT/Router. And Bob's local NAT/Router will know that the message he's receiving from the ISP NAT is meant to be delivered to Bob's computer.
So Bob and Alice can now talk :)

The only difference in the way STK will work is that instead of using phone calls to exchange public IP addresses / ports, we'll use a SQL database.

The connection protocol in SuperTuxKart

So when you'll want to play online, you'll query a STUN server, obtain your public IP address/port, then you will publish that in a SQL database. After that, you will put in that database which server you want to join. You also get the server's public IP address/port from the database and start sending messages to it.
This server will check regularly in the database who wants to join him. When he knows that you want to join him, he will get your public IP address/port, and send messages to it. After both you and the server have sent at least one message to each other, NATs will have the good entries in their NAT tables to allow a UDP exchange between you and the server.

After that setup, you will be connected to the server and you will be able to play races with other players that are connected to this server.

Conclusion

I hope it wasn't too long, and that you have now a good understanding of why this is necessary to work this way, and why people cannot connect directly to each other.
The networking part is designed to allow people to setup game servers on real servers, so I'm glad to announce you that at the end of summer you will probably be able to run your own SuperTuxKart server !!

Bye and see you online ;) !

13 comments:

  1. Very good work but ....

    End of Summer ? I think it was for STK 0.9 ?

    STK 0.8.1 is not puplish yet.

    ReplyDelete
  2. Indeed ;) But my GSoC project is the network. It's actually possible that some features of the 0.9 version will be available before features that should appear in earlier releases. By the way if nobody does the lag compensation code this feature won't be ready at the end of summer for WANs but only for LAN where lag compensation isn't really a matter.

    ReplyDelete
  3. Ok, thanks you for your answer. Bonne Chance à vous :)

    ReplyDelete
  4. Thanks!
    Where does the "STUN(156.42.32.67:15432)" come from or do you mean
    STUN(156.42.32.67:15423) ?

    "...called symmetric NATs, allocate a specific port for each connection, and do not allow this protocol to work..."
    Is there a way to overcome this?

    ReplyDelete
  5. Oh yes 15423 sorrry. The only way to overcome Symmetric NAT is the TURN protocol, which requires to own a server in the public domain. You then use that public server as an intermediate to forward packets.

    ReplyDelete
  6. This is awesome! I've always been waiting for network playing support.

    ReplyDelete
  7. Been waiting for this for years -- great work!

    ReplyDelete
  8. when you say that there is public stun srv on internet, do you mean STK will come with a static list of existing servers? Or download it from the project website? Is there a way to add our own in STK?

    what happen if bob just route a port on the nat to his laptop? Is there STUN trying?

    Why don't you consider to implement Pownat protocol to solve this problem ? It will make STK independant of any other people when bob & alice try to talk.

    ReplyDelete
  9. This comment has been removed by the author.

    ReplyDelete
  10. I'm looking forward to seeing these great new features!

    ReplyDelete
  11. I can not see any of the images in this post!

    ReplyDelete
  12. The only way to overcome Symmetric NAT is the TURN protocol, which requires to own a server in the public domain. You then use that public server as an intermediate to forward packets.Thanks.

    ReplyDelete