Virtual Connection over UDP

Introduction

Hi, I’m Glenn Fiedler. Welcome to the third article in Networking for Game Programmers.

In the previous article, I showed you how to send and receive packets using UDP.

Since UDP is connectionless, one UDP socket can be used to exchange packets with any number of different computers. In multiplayer games however, we usually only want to exchange packets between a small set of connected computers.

As the first step towards a general connection system, we’ll start with the simplest case possible: creating a virtual connection between two computers on top of UDP.

But first, we’re going to dig in a bit deeper about how the Internet really works!

The Internet not a series of tubes

In 2006, Senator Ted Stevens made internet history with his famous speech on the net neutrality act:

“The internet is not something that you just dump something on. It’s not a big truck. It’s a series of tubes”

When I first started using the Internet, I was just like Ted. Sitting in the computer lab in University of Sydney in 1995, I was “surfing the web” with this new thing called Netscape Navigator, and I had absolutely no idea what was going on.

You see, I thought each time you connected to a website there was some actual connection going on, like a telephone line. I wondered, how much does it cost each time I connect to a new website? 30 cents? A dollar? Was somebody from the university going to tap me on the shoulder and ask me to pay the long distance charges? :)

Of course, this all seems silly now.

There is no switchboard somewhere that directly connects you via a physical phone line to the other computer you want to talk to, let alone a series of pneumatic tubes like Sen. Stevens would have you believe.

No direct connections

Instead your data is sent over Internet Protocol (IP) via packets that hop from computer to computer.

A packet may pass through several computers before it reaches its destination. You cannot know the exact set of computers in advance, as it changes dynamically depending on how the network decides to route packets. You could even send two packets A and B to the same address, and they may take different routes. This is the source of the non-guaranteed order of packet delivery in UDP by the way.

On unix-like systems can inspect the route that packets take by calling “traceroute” and passing in a destination hostname or IP address.

On windows, replace “traceroute” with “tracert” to get it to work.

Try it with a few websites like this:

    traceroute slashdot.org
    traceroute amazon.com
    traceroute google.com
    traceroute bbc.co.uk
    traceroute news.com.au

Take a look and you should be able to convince yourself pretty quickly that there is no direct connection.

How packets get delivered

In the first article, I presented a simple analogy for packet delivery, describing it as somewhat like a note being passed from person to person across a crowded room.

While this analogy gets the basic idea across, it is much too simple. The Internet is not a flat network of computers, it is a network of networks. And of course, we don’t just need to pass letters around a small room, we need to be able to send them anywhere in the world.

It should be pretty clear then that the best analogy is the postal service!

When you want to send a letter to somebody you put your letter in the mailbox and you trust that it will be delivered correctly. It’s not really relevant to you how it gets there, as long as it does. Somebody has to physically deliver your letter to its destination of course, so how is this done?

Well first off, the postman sure as hell doesn’t take your letter and deliver it personally! It seems that the postal service is not a series of tubes either. Instead, the postman takes your letter to the local post office for processing.

If the letter is addressed locally then the post office just sends it back out, and another postman delivers it directly. But, if the address is is non-local then it gets interesting! The local post office is not able to deliver the letter directly, so it passes it “up” to the next level of hierarchy, perhaps to a regional post office which services cities nearby, or maybe to a mail center at an airport, if the address is far away. Ideally, the actual transport of the letter would be done using a big truck.

Lets be complicated and assume the letter is sent from Los Angeles to Sydney, Australia. The local post office receives the letter and given that it is addressed internationally, sends it directly to a mail center at LAX. The letter is processed again according to address, and gets routed on the next flight to Sydney.

The plane lands at Sydney airport where an entirely different postal system takes over. Now the whole process starts operating in reverse. The letter travels “down” the hierarchy, from the general, to the specific. From the mail hub at Sydney Airport it gets sent out to a regional center, the regional center delivers it to the local post office, and eventually the letter is hand delivered by a mailman with a funny accent. Crikey! :)

Just like post offices determine how to deliver letters via their address, networks deliver packets according to their IP address. The low-level details of this delivery and the actual routing of packets from network to network is actually quite complex, but the basic idea is that each router is just another computer, with a routing table describing where packets matching sets of addresses should go, as well as a default gateway address describing where to pass packets for which there is no matching entry in the table. It is routing tables, and the physical connections they represent that define the network of networks that is the Internet.

The job of configuring these routing tables is up to network administrators, not programmers like us. But if you want to read more about it, then this article from ars technica provides some fascinating insight into how networks exchange packets between each other via peering and transit relationships. You can also read more details about routing tables in this linux faq, and about the border gateway protocol on wikipedia, which automatically discovers how to route packets between networks, making the internet a truly distributed system capable of dynamically routing around broken connectivity.

Virtual connections

Now back to connections.

If you have used TCP sockets then you know that they sure look like a connection, but since TCP is implemented on top of IP, and IP is just packets hopping from computer to computer, it follows that TCP’s concept of connection must be a virtual connection.

If TCP can create a virtual connection over IP, it follows that we can do the same over UDP.

Lets define our virtual connection as two computers exchanging UDP packets at some fixed rate like 10 packets per-second. As long as the packets are flowing, we consider the two computers to be virtually connected.

Our connection has two sides:

  • One computer sits there and listens for another computer to connect to it. We’ll call this computer the server.
  • Another computer connects to a server by specifying an IP address and port. We’ll call this computer the client.

In our case, we only allow one client to connect to the server at any time. We’ll generalize our connection system to support multiple simultaneous connections in a later article. Also, we assume that the IP address of the server is on a fixed IP address that the client may directly connect to. We’ll cover matchmaking and NAT punch-through in later articles.

Protocol id

Since UDP is connectionless our UDP socket can receive packets sent from any computer.

We’d like to narrow this down so that the server only receives packets sent from the client, and the client only receives packets sent from the server. We can’t just filter out packets by address, because the server doesn’t know the address of the client in advance. So instead, we prefix each UDP packet with small header containing a 32 bit protocol id as follows:

    [uint protocol id]
    (packet data...)

The protocol id is just some unique number representing our game protocol. Any packet that arrives from our UDP socket first has its first four bytes inspected. If they don’t match our protocol id, then the packet is ignored. If the protocol id does match, we strip out the first four bytes of the packet and deliver the rest as payload.

You just choose some number that is reasonably unique, perhaps a hash of the name of your game and the protocol version number. But really you can use anything. The whole point is that from the point of view of our connection based protocol, packets with different protocol ids are ignored.

Detecting connection

Now we need a way to detect connection.

Sure we could do some complex handshaking involving multiple UDP packets sent back and forth. Perhaps a client “request connection” packet is sent to the server, to which the server responds with a “connection accepted” sent back to the client, or maybe an “i’m busy” packet if a client tries to connect to server which already has a connected client.

Or… we could just setup our server to take the first packet it receives with the correct protocol id, and consider a connection to be established.

The client just starts sending packets to the server assuming connection, when the server receives the first packet from the client, it takes note of the IP address and port of the client, and starts sending packets back.

The client already knows the address and port of the server, since it was specified on connect. So when the client receives packets, it filters out any that don’t come from the server address. Similarly, once the server receives the first packet from the client, it gets the address and port of the client from “recvfrom”, so it is able to ignore any packets that don’t come from the client address.

We can get away with this shortcut because we only have two computers involved in the connection. In later articles, we’ll extend our connection system to support more than two computers in a client/server or peer-to-peer topology, and at this point we’ll upgrade our connection negotiation to something more robust.

But for now, why make things more complicated than they need to be?

Detecting disconnection

How do we detect disconnection?

Well if a connection is defined as receiving packets, we can define disconnection as not receiving packets.

To detect when we are not receiving packets, we keep track of the number of seconds since we last received a packet from the other side of the connection. We do this on both sides.

Each time we receive a packet from the other side, we reset our accumulator to 0.0, each update we increase the accumulator by the amount of time that has passed.

If this accumulator exceeds some value like 10 seconds, the connection “times out” and we disconnect.

This also gracefully handles the case of a second client trying to connect to a server that has already made a connection with another client. Since the server is already connected it ignores packets coming from any address other than the connected client, so the second client receives no packets in response to the packets it sends, so the second client times out and disconnects.

Conclusion

And that’s all it takes to setup a virtual connection: some way to establish connection, filtering for packets not involved in the connection, and timeouts to detect disconnection.

Our connection is as real as any TCP connection, and the steady stream of UDP packets it provides is a suitable starting point for a multiplayer action game.

We also have some insight into how the Internet routes packets. For example, we now know the reason UDP packets sometimes arrive out of order is because they took different routes over IP! Take a look at a map of the internet, isn’t it amazing that your packets arrive at all? If you would like to dig a bit deeper into all this, a great starting point is this article on wikipedia.

Now that you have your virtual connection over UDP, you can easily setup a client/server relationship for a two player multiplayer game without needing to use TCP.

You can see an implementation of this in the example source code for this article.

It’s a simple client/server program that exchanges 30 packets per-second. You can run the server on any machine you like, provided it has a public IP address, because we don’t support NAT punch-through at this point.

Run the client like this:

    ./Client 205.10.40.50

And it will attempt to connect to the address you specify on the command line. By default it attempts to connect to 127.0.0.1 if you don’t specify the address.

While one client is connected you can try to connect another, and you’ll notice that it fails to connect. This is intentional. For the moment, only one client may be connected at a time.

You could also try stopping the client or server while they are connected and you should notice that after 10 seconds the other side will timeout and disconnect. When the client times out it exits to the shell, but the server returns to a listening state ready for another client to connect.


Next: Reliability And Flow Control




If you enjoyed this article please donate.

Donations offset hosting costs and encourage me to write more articles!

31 thoughts on “Virtual Connection over UDP”

  1. Fantastic series and I await the next! Apart from a slight disagreeance with how you structured the Socket class it’s a great set of articles.

    The best thing about your writing is how the topics are introduced effortlessly with just the right amount of information. Perhaps when people donate you could provide a PDF version of the articles that’d be a lovely incentive.
    Regards,
    Nick

    1. I think eventually I’ll leave these original articles online but sell an ebook for the rest of the articles that I’ll write over the next ten years (hopefully a full books’ worth…) with updated example source code under BSD licence.

  2. I’m confused about why we need to filter out packets. Can’t we assume that if a packet is addressed to a port that the server/client is using then we can accept it?

  3. You are right you could just do this, but it is risky – what if somebody wished to fake a packet so it looked like it came from the correct address, but it was setup such that it would confuse or crash your server?

    This sort of packet injection attack is actually quite common, so for now we just add our protocol id as some sort of “place holder” for real security

    In reality it is best to use an encrypted connection such that the packet is encoded by some public key so that nobody may insert packets, you’ll find this is done on serious network platforms like Xbox-Live and PSN, and if you are planning on implementing your own game protocol you should at least have some sort of security to avoid packet tampering or injection

    I’ll be covering this in a later article! For now please note that this simple connection is really only suitable for playing over a LAN, it is not hardened such that it would be shippable for a modern multiplayer game. You should use some comms library like Raknet or OpenTNL instead!

    cheers

  4. Hi Glenn, these articles are the best that I have found on game networking and the samples are excellent. Would you consider selling the rest of the articles for a bundle price?

    1. thanks!

      well the current plan is keep plugging away on the articles over the next few years, then when they are all done in a first pass, turn it into a book, with diagrams, code samples and all that – and sell that as an ebook, or printed on dead trees (maybe)

      does this sound like a good idea to you?

      did you have something else in mind?

      cheers

      1. I would eventually like to write a book on networking, once work calms down a bit (if it ever does), I’d like to take all my GDC talks and articles and combine it into a e-book. I think I’ll maybe kickstarter it.

  5. yeah, I would have paid for your knowledge right now. I have tried to avoid network programming as much as I can but now its essential that I start to use it. Your articles have really brought me up to speed, thanks for sharing

  6. Excellent articles.
    I highly support this endeavor, so I donated 10 of our Canadian dollars for you to continue.

    If I decide to incorporate networking into my game prototype, then your articles are definitely the resource I will be using.

  7. I know you published this quite a while ago but dude, each one of your articles is more useful then 5x2hour lessons on our uni…thx a lot and pls keep publishing them ;]

  8. When using Visual Studio Express 2010 Beta 2 to compile your example Client/Server code, there is an issue with the dynamic packet array in the Net.h header file.

    unsigned char packet[size+4];

    needs to be changed to:

    unsigned char **packet;
    packet = new unsigned char*[size+4];

    and in the if statement below the cast of (unsigned char) needs to be changed to (unsigned char*)

    These changes need to be applied to both ReceivePacket and SendPacket functions.

    1. You don’t need a pointer-to-pointer since:

      unsigned char *packet;
      packet = new unsigned char[size+4];

      should be enough… the rest of code is pretty much the same.

  9. Well… this isn’t a connection over udp…
    This won’t work unless the client is directly connected to the Internet… right ?

    I mean, if all you have is an IP and a port, the server will send answers to the device who sent the packages… which is your client ONLY when you’re not using a router (and almost everybody use routers nowadays).

    When using a TCP connection, you don’t have such problems (you still can’t connect to a device which is not directly connected to the Internet, unless the router makes a redirection)… using UDP is a whole other matter.
    I am actually wondering how games such as Warcraft III deal with that stuff : why is the server the ONLY ONE who has to be directly connected to Internet (or have his router re-route packages from one port to him) ?

    1. actually it will work provided the server (the one being connected to) is not behind NAT. if you need to establish P2P connections then you’ll need to use NAT-punchthrough. cheers

  10. Hey Glen, Great job on the tutorials, I love them!

    I am however having a problems connecting from one computer to another. Say if I have one computer running as the server, i.e. it is just listening for a client, and I then get its IP address by looking up “what is my ip” on google. Can I then just go onto another computer which is connected to the internet and connect as a client by setting the connection address to the IP (eg set “connection.Connect( Address(XXX,XXX,XXX,XXX,ServerPort ) );” where X is the other computers IP)?

    1. You need to ensure that the server only sends packets to the client IP/port after the client has already sent packets to the server IP. otherwise, your firewall will freak out and think the server is initiating the connection with the client and block it.

      also, if you are establishing a P2P mesh (not client/server) then you will need to do NAT punchthrough.

      cheers

  11. There appears to be an error in InitializeSockets this time round.

    return WSAStartup( MAKEWORD(2,2), &WsaData ) != NO_ERROR;
    doesn’t work for me, while

    return WSAStartup( MAKEWORD(2,2), &WsaData ) == NO_ERROR;
    is sound.

    Visual Studio 2010. Windows 7. Enjoying this series by the way, thanks.

  12. Dear Glenn,
    First of all I would like to thank you for all these amazing articles about networking.
    I basically went “from zero to hero” learning as a network programmer from your articles.

    I started making the first multiplayer-oriented game with my team in the start of this year and everything went well until we encountered an issue simply called “routers”, or the thing they do: NAT. I have a basic understanding of the stuff behind it and our multiplayer game hardly has a problem when it comes to opening a port using UPNP. But when we are facing multiple routers doing multiple NAT and manual forwarding is not an option (say, your ISP doesn’t provide you a public IP address and you will be sitting under their private subnet) our easy one-click-join solutions fail. The basic udpclient/socket.Send(address:port, data) methods our app is based on becomes useless since the target is unreachable by a single address:port combination over the internet.

    If you could help a fellow networker out, my question would be: Are the only two solutions here:
    – Hosting a master server application on a site with public address, and relaying every client-to-client messaging (clients can host game servers, as in usual games) over the master server?
    – The clients using some sort of VPN (like Hamachi) which supplies them another address by which they are directly referrable for everyone in the same VPN? (We tested this, we know this works, but we can’t just make all our “players” get a VPN software and be in the same VPN room just for that..)

    .. Or is there some magical method of dealing with these Port Restricted Cone routers while maintaining our networking code we already have? I really hope there is… but I feel my hopes are in vain.

    1. There is a solution, google for “STUN server”

      The limitation is that full restricted NATs can only connect to non crappy routers, eg. You make sure the bad NAT type does not become the server in your game, and if P2P, you implement packet forwarding as you are not guaranteed to have a fully connected mesh.

  13. Hi Glenn,
    thanks for the great articles and sample code. This is one of the best articles I’ve read on Network Porgramming.
    I do have a question though. If I were to ask my server to “send” me the information on where another player is and show him on the client at that given location how could I “ask” this?
    So how can I say to the server to return the position to the client?

    I know this might be a nooby question but I am one and I can’t figure this out.

    Thanks in advance

    1. Typically the server doesn’t wait for the client to ask for such things, but sends them continually to the client at some rate, eg. 30 times per-second. cheers

        1. Yes you structure the data such that the client knows how to read it, knows that there are n objects, then for each object knows how to read that object, eg. which fields are encoded and in which order.

          Generally I do this by assigning objects the same Ids on each machine, so the packet sent probably looks a bit like:

          [int numObjects]
          [id][object 1 data]
          [id][object 2 data]

          [id][object n data]

          inside each object, I would probably have a “type” per-object because different object types (eg. a car vs. an AI) have different network data. As an optimization, if the objects were placed in the level in the editor, the type would be known as a function of the id that is the same on both machines, so it would not need to be sent. For spawned objects, the id is usually assigned dynamically, and thus the type must be included.

          For the rest of the object data, you write a serialize function, which is the same on the read and write sides. It knows to serialize first an integer of n bits, then a float then an integer of y bits and so on. You rely on the fact that the write and read code match, and in fact they way I write it is an a single unified “serialize” function which performs both read and write in different contexts so i don’t have to maintain two separate functions.

          I also do this with a bitpacker, so if I send a bool, it takes up one bit, not 8. I can then look at the range of an integer value, say [0,n] and know that i need X bits to serialize that. Since the min/max of each integer is in the serialize function, and is same on both machines, the read and write match.

          that’s how I do it anyway.

          cheers

Leave a Reply

Glenn Fiedler's Game Development Articles and Tutorials