Starcraft evolution: Why UDP?

Only few days left until the end of Starcraft 2 Beta testing Phase 1. With latest patch 13 Blizzard's developers enabled UDP in order to improve game performance over Bnet system. From outside it looks like it didn't go well. I may be completely wrong, but I have feeling that all lagging, dropping and other things are UDP issue. I guess that many players (whining players) would rather say "disable that UDP again, it was better before". Simplest thing to do. On a short run. But it is not what you think...
Even this may be unrelated, someone may be interested in what is this UDP and why we need it. On Bnet forum (NA) lagging and bad game performance discussions takes more space then recent Ultralisk balance changes. But enabling UDP is completely normal step in beta, and it is expected to look like step back. But it is not. We are in final stress testing. Once all problems are solved, game will be faster and snoother then ever. Since I have some average programing background here it is, UDP for beginners.

UDP stands for User Datagram Protocol, or Universal Datagram Protocol. It is one of the protocols that makes Internet communications available. Even there are many protocols that define different types and methods of communication (ie. sending data over the Internet), you may also hear about TCP/IP protocol. This one is quite enough for comparison with UDP.

Lets state some facts about TCP/IP without going to deep in technical aspects. It is heavy weight protocol, and its intention is to make data streaming reliable. The main characteristics TCP/IP are:
- reliable - it handles message acknowledgement, retransmissions and timeouts. TCP/IP wil rarely fail in delivering data packages. It tries multiple attempts in case of connection problems, it can detect missing parts and properly react if data is not get in after multiple attempts or timeout.
- ordered - multiple messages can be send in sequence. Sometimes, due to connection problems this data packages may arrive in different order. In this case TCP/IP buffers the out of order data, until all packages arives and then pass them to receiving application in proper order.
- heavyweight - it requires three packages to set up connection, it includes congestion control, and all this controlling principles makes him a bit slow for some purposes
- streaming - data is read as byte stream

Comparing to this, UDP is almost completely different:

- unreliable - when message is sent, it cannot be known if message is received at destination, data package may be lost, no resending, no timeouts, nothing to control
- not ordered - multiple messages send to receiver may arrive in different order, no predictions and order corrections are made
- lightweight - no data or connection controls exist so it is very lightweight and fast
- datagrams - data is sent as packets and are checked for integriti only if they arrived

Then why we need UDP for playing Starcraft

Only one main reason - SPEED. UDP is used for multiple clients, in Starcraft words - MASS clients. UDP is up to 3 times faster then TCP, it is connectionless, and it doesn't spend much time controlling if everything is wrong. Before start ranting on Blizzard why they enabled such funny protocol, read on.

In Starcraft 2 multiplayer mass data is send over Internet. The problem is how to control data streaming between clients. When you play multiplayer, both your and your opponents clients should be completely synchronized so you can see the same things and actions. Even in 1v1 lots of data is send from one client directly to another because of real-time requirement.
I will not try to guess actual Blizzard's programming logic, but here is primitive example. When you click on SCV and order your SCV to move, other client gets this like what unit(SCV)/what command(MOVE)/atributes(to what position). Then other client must replicate and animate your action based on this data. Note that other things may happen during this. Your SCV may be attacked. To avoid that your CSV runs one way, and the same one on clients map runs somewhere else, this attack action data is also send so they both synchronize.
So this is just one SCV moving somewhere in 1v1.
Now imagine mass battle where hundreds of units are involved. It is lots of data.
And now even imagine 4v4. Much more units, and 4 clients to synchronize in one match.
At the end, imagine at least 10.000 games played at the same time.

Now we are at the right point. TCP protocol will be perfect if there were no any connection problems and delays. But wrong data orders, resending packages, controlling if everything is ok takes three times more time and bandwidth. Match will easily be broken because one of the clients didn't receive right package and doesn't know where to send your SCV, and all your other actions will wait in queue because one missing package. It can't skip some data because TCP is made that way.

UDP on the other side send packages the fastest possible way. It just send the package to all clients in match and doesn't care about it. If one of the clients have problem it will never receive some data, but WILL receive next package and WILL catch up. If packages are received in different orders, it will not wait to sort them up but just pass them to application.

Now what Blizzard developers are working on (it is my guess) is to make proper programming logic which will allow game to work according to this. Lagging is result of not receiving data by your client, it doesn't know what to do at some point. If too many data packages are lost, one client is "blind" to other.

Client must ensure that it can work with data even if it receives them in different order then they are sent. Lack of robust TCP control mechanisms must be programmed in game logic.

Lets get back to our example. When SCV is moving to its position on both maps, client may send some controlling data just to check if SCV is on the same position on both clients while he travels to its destination. If not, one of the clients should correct that. Now programming should stand on logic that SCV should eventually reach its destination. Even if any data is lost in meantime, it will keep going there. So it is not so important that all packages are not received, if client can handle it. In TCP case, if one control point is missing while others are received, due To order control client should wait for missing package to be resend.

There is more in logic optimization. If your opponent can't see your base (meaning you are covered under fog of war) your client should not synchronize your SCVs gathering minerals, as only you should see them. But if you have observer over your base, then your in-base actions must be sent to other client. I believe this may work this way to spare bandwidth.

You probably noticed during this beta, your CSVs gathering minerals, then they freezes, and in a moment they jumped to locations where they would be if not frozen.

Content of that datagrams are purely in the hands of programmers, as well as receiving data. They determine what should be send.

Current lagging, dropping, freezing problems may be addressed to handling data. If some of game engine functions get stucked because of lost package, we have problem. Programmers then detect this based on data and logs they received from beta testers and try to fix that. Lost data packages causes client to "not know" something. Approach to solution can be to "ignore it", "if-then" or different alternatives which will not ruin match synchronisation. Note that if client doesn't receive data package it also doesn't know that it was send at all. It has to be "smart" to override small glitches. If client "knows" (recieves) that you shoot at Collosus who has one HP left Colossus should die on both clients even one doesnt doesn't receive conformation for that. Kill him, start animation and remove him from match. It is pretty sensitive.

My professional experience in programming simple multiplayer games using UDP, ports, sockets etc. shows me the value of UDP protocol despite of its unreliability. UDP makes more pressure to client developer to compensate lack control mechanisms. At the beginning policy of every game was "send EVERYTHING" so both clients aware of each other. Once done, you try to tweak game so not all data is necessary, until you get to the point that you send minimal amount of data. Less you send, less can be lost, more clients can be handled.

UDP is just sending data, like when you watch streaming video. Source doesnt care if you see some glitches or not, and your client shows whatever it receives. Source sends nice and clear image. On your side it may look different because something is lost on the way. However you are still able to see video without delay, maybe some frame is jumped over, maybe some flickering is present due to wrong data order. But it is still watchable. Your video client is set to ignore missing data, and not to freeze if not received. In Starcraft, playing a match is almost like both you and your opponent create a video on-fly, real time, and stream to each other so you can see exactly the same final result. Since creation of this is interactive and dependable of each other, some missing data may cause problems. Programmers should fill the gaps. UDP is kind of "zerg" in data sending protocol. UDP is fast and send mass of data. Clients should handle what to do with data received and what to do in case of data absence. Missing data should not lag or stop the game.

However, no matter how bad and unreliable UDP is comparing to TCP, its speed is still great advantage for handling 24 hours a day of multiple units actions, guided by multiple users in multiple matches. Controlling game synchronization is moved to client itself.

Here is something for fun. Two clients communicating over TCP.

C1: Are you online?
C2: Yes
C1: Ok, I'll start to transmit some data, comply upon receiving
C2: OK
C1: Sending 1.
C2: Received 1. Complying instructions 1. OK
C1: Sending 2
C2: Error! Number 2 is of wrong size, doesn't match control code, application is on hold, please resend 2
C1: Are you online?
C2: Yes
C1: Ok, sending 3. Resending 2.
C2: Error! Number 2 is of wrong size, doesn't match control code, application is on hold, please resend 2. Received 3. Number 3 buffered as out of order.
C1: Are you online?
C2: Yes
C1: Sending 4. Resending 2.
C2: Received 2. Complying instructions 2. OK. Complying instructions 3 from buffer. Error! Instruction 3 requires instruction 4
C1: Are you online?
C2: Yes
C1: Ok, sending 5.
C2: Error! Number 4 is missing, application is on hold, please resend 4. Received 5. Number 5 buffered as out of order
C1: Are you online?
C2: Yes
C1: Ok, resending 4.
C2: Received 4. Complying instructions 4. Error! Wrong argument! Complying instructions 5 from buffer. Error! Application not respond!
(actually application freezes for not receiving 4 on time, client freezes)
C1: Are you online?
C2:....
C1: Guess not. However, all data was send correctly...

Now they are communicating over UDP

C1: Are you online?
C2: Yes
C1: Listen! 1,2,3,4,5!
C2: Complying 1,2,3,5: It seems that I am missing 4, but jumped right to 5
C1. No problem, I am on 5 too :) Now something different and urgent.  Listen! 6,7. I will wait for response for 1 second.
C2: ....
C1: Hmm, no response in 1 second. Listen! 6, 7. I will wait for response for 1 second.
C2: Hey, where have you been :) Complying 6 and 7. Actually 7 instructs me to send 8 right away. So here you go. Listen! 8!
C1: Complying 8 :) GG

I am sure that developers so far handle all received data between clients. IMHO, the current problem is few critical points or situations where missing datagrams affect the game. Starcraft is so massive that this possibility exists. When they improve critical points, and ensure all alternatives and what-ifs, we will have the best strategy game ever.

Disclaimer: This article is based on my average understanding of this matter and is written for fun. Evrything I said about Starcraft 2 programming logic and data flow is completely speculative.

You may want to read some other articles on other sites:
http://gafferongames.com/networking-for-game-programmers/udp-vs-tcp/ - better then I can explain
http://tunnel.mrq3.com/explain/node3.html - why games use UDP