UDP Vs TCP/IP

Networking & Multiplayer
#101

I said not counting that! I’m thinking broadband at the moment.

[quote]Not True. The sender doesn’t wait for ACKs. Its a NAK based protocol (at least in all modern implementations.) The sender just keeps pumping packets but keeps a “sliding window” of history of past packets. When it gets a NAK on an old packet, it retransmits from that history.
[/quote]
I admit that I haven’t done the math, but I have read the papers of those that did. I believe my statement is true.
It CAN’T be NAK based with a sliding window. It is IMPOSSIBLE to be reliable that way. Think about it. No NAK is received to request re-transmission of the oldest packet in the window. A new packet is transmitted and so the window advances overwriting that old packet in the sliding window buffer. NOW a NAK is received for that old packet… oops too late, it is out of the buffer and not available to retransmit.
I believe it is ACK based with a sliding window… and that is where the round trip time comes in to play… transmission MUST either be suspended if the oldest packet is not yet ACKed, or that old packet must be re-transmitted automatically. Either way no new data is sent in that situation until the ACK is received. The time for the ACKs to get back and the size of the sliding window establish an upper limit on the transmission rate regardless of the speed of the channel.

#102

[quote]I believe it is ACK based with a sliding window… and that is where the round trip time comes in to play… transmission MUST either be suspended if the oldest packet is not yet ACKed, or that old packet must be re-transmitted automatically. Either way no new data is sent in that situation until the ACK is received. The time for the ACKs to get back and the size of the sliding window establish an upper limit on the transmission rate regardless of the speed of the channel.
[/quote]
But this all depends on the size on your window. As you have to block when the oldest packet isn’t acknowledged, you can just make your buffer bigger and increase your retry rate.

E.g., just to give an example, have a sliding window of x seconds, retransmit anything requested immediately, or anythinng not acknowledged every x/y seconds. This gives y chances for each packet to get through, and you’ll only block if none of them get through.

#103

[quote]It CAN’T be NAK based with a sliding window. It is IMPOSSIBLE to be reliable that way. Think about it. No NAK is received to request re-transmission of the oldest packet in the window. A new packet is transmitted and so the window advances overwriting that old packet in the sliding window buffer. NOW a NAK is received for that old packet… oops too late,
[/quote]
This is assuming you want to reliably COMPLETE transmission under all cases. Clearly there are already cases on the internet where that isn’t true (ie a main router goes down in the middle of the transmission.)

In practice all you need is a window large enough to cover some “maximum wait time” beyond which you would simply abort the transmission as “failed.” As long as this maximum is larger then 99.99% of the internet lags experienced, you have “4-nines” of reliability, which is damn good.

Absolute anythings aren’t usually efficient. Cut off the one ina million end cases and things improve a lot :slight_smile: I’m not saying this IS how its done, but it is certainly POSSIBLE to do it this way.

The way to find out for sure what’s going on is to go to the MAGIC archive and search the RFEs. If i had time, Id do that, but I don’t right now.

#104

Your NAK method depends on reliable delivery of NAKs… and it would be sensitive to lags in the response time… a fast sender could overrun the sliding window before the first NAK came back.

I have been reading a very good TCP/IP book, I don’t have it with me now… But I’m pretty sure TCP is ACK based with the sliding window.

I know you can simply unplug the network cable and it wouldn’t matter how “reliable” TCP is - your data isn’t going to get through. I was refering to the effect on throughput, not reliability. I think timeouts are set such that you will see a significant slowdown well before you see failures.

Yes the size of the window can improve performance and it can grow dynamically etc… But my point was that RTT (Round Trip Time) combined with the (max or current) size of the sliding window determines a maximum throughput that is independent of the transport speed. I am pretty sure that is true.

That’s why using Forward Error Correction and UDP you can eliminate the need for a sliding window and dramatically improve throughput IF you have high RTT (ping) or a lossy connection. I’m not suggesting this is particularly useful information for games though… perhaps it would be useful for server downloads like models, levels, updates, etc.

My main point was that reliability can in many cases not matter, so doing without it might give you a measurable gain. Specially if clients can connect to a multicast group to get the game state. Though I don’t know enough about multicast yet to know how practical that is. It seems to make sense.

Take the networked Power Pong game mentioned in another forum. The state of the game is so tiny, and the ball is basically always moving… so there needs to be relatively constant network traffic anyway… so just have the server constantly, at some fixed rate, tuned for the speed of the channel, send the current state of the game with a timestamp. The client could send the paddle moves with TCP only when the paddle position changes, or it can do something like the server and simply send the current paddle position constantly (with timestamps) at a fixed rate.

#105

Hmm.

I guess Ill go to MAGIC and look, but NAK based re-transmission dates all the way back to Zmodem. I’d be surpised if TCP sat and waited for individual ACKs. (In fact Im sure it doesn’t, though a large sliding buffer of packets awaiting ACKs I suppose is possible.)

On your PowerPong, unless im missing something in the game design I wouldnt flood the world with UDP packets. All the motion is predictable given the collision point of ball and paddle. I haven’t sat down and worked it out but I my instincts say one reliable packet per collision would work fine. You have all the time of the travel of the ball to synch up. (And if you are clever and slightly time delay one players’ view of the other players’ actions you can easily cover the critical timing at that point.)

#106

So i’ve started researching. The initial answer seems to be it isn’t simple ACK or NAK, but a pretty evolved and complex hybrid.

This is my first reference, it references others…

http://www.faqs.org/rfcs/rfc1106.html

#107

Yes, the pong example was over simplified. But it makes the point… assume the client can’t predict very far into the future and so client prediction is only useful for smoothing out the action.

The reference you linked to states:

[quote]This memo describes an Experimental Protocol, these extensions are not proposed as an Internet standard, but as a starting point for further research.
[/quote]
It is old (1989) - but is it in widespread use? My reference (TCP/IP Illustrated Vol.1-3) is newer.

The first paragraph of the introduction also backs up my point about RTT and loss limiting the throughput.

[quote]After the last batch of algorithm improvements to TCP, performance over high bandwidth*delay networks is still very poor.
[/quote]
For the record, my company has just licensed a UDP-based transporter that uses FEC and in real world tests we are seeing significant gains over TCP (50% + just from Texas to Toronto where there is almost 0 packet loss and ping <=100ms). We need to move large video files from one side of the world to another. The speed ups can be VERY substantial (500%) with even a little bit of packet loss.

edit I’m comparing to regular FTP - which is not the fastest TCP based transfer protocol.

Also note Figure 1 in the Appendix - see the massive drop in throughput caused by an error rate of 10e-7. It is better using this proposed protocol, but error rate of 10e-6 still severely cripples the throughput. Actual loss on the Internet from for example Singapore to L.A. can easily be 10e-6.

#108

I think your video protocol gets us back to initial contentions.

(A) if you don’t need reliable or in order devliery then by all means use UDP (unless you have serial PPP bandwidth issues.) Thats what its for!

(B) For very domain specific things, WHERE you are really willing to do the not unsubstantial work of developing a sophisticated protocol, I absolutely agree you can improve on TCP. As i mentioned we had a hybrid TCP/UDP protocol Bill developed at TEN for very specific types of games (Quake2 like) that was a big improvement over pure TCP or simple UDP.

But its a lot of work and requires a pretty deep understanding of how the net actually functions. People who just slap a simple reliability/ordering protocol on top of UDP are reinventing the wheel and end up only hurting their performance.

Unfortunately, that last is the most common occurance in games that decide to “use UDP 'cause its faster!”

© As you say, FTP isn’t TCP. Also when you start talking about file transfer, or anythign that can be buffered (like video streams) bandwidth is usually much more important then latency. People often confuse the two but they are very different quantities and have very different effects. Game packets on the other hand are usually more latency then bandwidth sensative.

(D) Foward Error Correction makes a lot of sense I think where the data stream is well known into thge future, but again game packets usually arent that way.

(E) Lastly video ofcourse can handle some loss and error so perfect error correction isnt necessary. A proper video protocol can make good use of that. Again this generally isnt true for your game data stream.

#109

But one has to keep in mind that bigger messages (-> bandwidth) esp. on very thin lines add their part to latency, bc. it just takes longer to transmit them! Another 100byte on an ancient 14k modem causes ~100ms on pure transmission time which adds to the other sources of latency. 100ms!

Addtionally, bandwidth gets more important when talking about MMP things.

#110

True they are related, particularly on thin analog lines.

But in fact the relationship is significantly more complex.

In order to get above 28.8K the modems do compression and decompression, so upping the bandwidth actually UPS the latency as that takes time.

Even worse, the faster you try to run the analog modem the more likely it is to fail due to noise and have to fall back and find a new speed to communicate at. These retrains can take 6 or 8 SECONDS.

So trying to push the bandwidth to high on a thin analog line actually makes your latency problems much worse.

(I’m about to write a chapter about all of this it looks like for Shawn’s book…)

As for MM, that totally depends on your communication architecture. You can do a lot to limit that by NOT sending players info they aren’t in a position to use. The cost ofcourse is more complex processing on the server.

#111

[quote]I think your video protocol gets us back to initial contentions.

(A) if you don’t need reliable or in order devliery then by all means use UDP (unless you have serial PPP bandwidth issues.) Thats what its for!
[/quote]
I think you may have read more into what I said. The sending of these large video files must be reliable and bit for bit accurate… this is not for broadcasting, it is for arbitrary file copying… video files are just what we happen to be transferring.

quote For very domain specific things… you can improve on TCP…

But its a lot of work and requires a pretty deep understanding of how the net actually functions. People who just slap a simple reliability/ordering protocol on top of UDP are reinventing the wheel and end up only hurting their performance.
[/quote]
I agree 100%

[quote]Unfortunately, that last is the most common occurance in games that decide to “use UDP 'cause its faster!”

quote As you say, FTP isn’t TCP. Also when you start talking about file transfer, or anythign that can be buffered (like video streams) bandwidth is usually much more important then latency. People often confuse the two but they are very different quantities and have very different effects. Game packets on the other hand are usually more latency then bandwidth sensative.
[/quote]
Right, My point on game packets is that in the event of an error along the data path, TCP will correct that at the expense of both bandwidth and latency. If your packet has to get through though TCP will probably do the best job and so you just have to live with what you get. However, depending on the size of the game state, it may make sense to send enough of it such that it does not matter if previous packets made it through, or the error that results would not be objectionable to matter and will correct itself when another few packets make it through.

With a little thinking ahead you may come to the conclusion that order of delivery and guaranteed delivery don’t actually help you. The state of the client won’t be ‘wrong’ long enough to matter, or the packets that TCP will send to correct the ‘problem’ are just getting inserted in the stream and delivered to the client when the next packet that supersedes that state is already waiting in the clients network buffer anyway. It’s just something to think about… you could probably calculate how useful it is to consider these things when you work out the ping vs. bandwidth and try to determine the time it takes to correct for a lost packet vs. the time it takes to get the next newer packet of game data.

quote Foward Error Correction makes a lot of sense I think where the data stream is well known into thge future, but again game packets usually arent that way.
[/quote]
I agree… I initally stated as much, saying that this UDP+FEC idea might be useful for downloading models, patches, level etc. but not dynamic game state.

quote Lastly video ofcourse can handle some loss and error so perfect error correction isnt necessary.
[/quote]
I should have just said “big files” there was no data loss allowed.

[quote]In order to get above 28.8K the modems do compression and decompression, so upping the bandwidth actually UPS the latency as that takes time.
[/quote]
But compression happens almost instantly relative to the slow speed of the transmission. Recall that the link between modem and CPU is MUCH faster than the phone line… the data would be sitting in the modems buffer waiting to get out anyway - so compression happens for free - when it is done by the modem hardware, and not some crappy winmodem with all the work done by the CPU… so does this not ultimately save latency via the methods Herkules mentioned by delivering a shorter packet?

[quote]Even worse, the faster you try to run the analog modem the more likely it is to fail due to noise and have to fall back and find a new speed to communicate at. These retrains can take 6 or 8 SECONDS.
[/quote]
Ah but your game, these days, has no control over the speed that the modem attempts to connect at. So re-trains do to line noise etc are just going to happen… the only thing that your program can control that I could thnk might effect it is that it might not know that it has to retrain until you actually send data for it to barf on… so by that account the more data you send the more opportunity it would have to realize the connection is crap. But as for speed that the data travels - that is usually beyond the control of applications. The dial-up networking layer will deal with it.

#112

Lots of agreement here, a few minor points.

If this is true today then modems have GREATLY improved their processing power in the last few years.

Remember in return that embedded hardware is HIGHLY cost sensitive. The cheapest parts that will do the job are always used because a $1.00 part cost difference easily becomes a $10.00 shelf cost difference, which will lose you sales v. a competitor who is that much cheaper. (My days at Philips are showing here :wink: )

When I was at TEN, which was 5 years ago, asking the modem to go over 28.8 definitely added signficant latency which is why we never did it.

At TEN we set it via Win32 APIs.

From Java yes you might have to write some native hooks OR simply run the RECIEVING modems at a limited speed, if you have control over that end (we didn’t.)

At worst case, you make it part of your “what tp do if the game dossn’t work well” instructions and tell the user how to set it in the target OS. (We did this too, advising uses to back off the speed further if they had very dirty lines.)

#113

A few more comments…

[quote]With a little thinking ahead you may come to the conclusion that order of delivery and guaranteed delivery don’t actually help you. The state of the client won’t be ‘wrong’ long enough to matter,
[/quote]
This MAY be true depending on the type of game. I could see it, for instance, in a racing game.

Many games however contain SOME packets that need to be delivered reliably in a timely manner. Shots for instance in any kind of shooter.

Once you have ANY packets that require this, it means you need to solve the speed problem for reliable packets, you don’t have a choice. And once you’ve solved that problem, doing a second unreliable channel is generally needlessly redundant and just doubling your effort for no end gain.

#114

Oh and just to further complicate things…

On those thin analog lines remember you are running serial PPP, which means that the overhead for a UDP packet (30 bytes) is 15 times larger then for a TCP packet (2 bytes.)

As I think I mentioned this was a large part of why we were TCP based at TEN.

#115

:-*

how I love to hear you saying that…

#116

[quote]If this is true today then modems have GREATLY improved their processing power in the last few years.
[/quote]
I could be completely wrong about the compression thing. I am making some assumptions about the speed of modems the implement the compression on-board and comparing what I’m guessing to be the speed of on-board compression to the relatively snail-like pace of the modem’s outgoing analog transmission.
[/quote]

[quote]At TEN we set it via Win32 APIs.
[/quote]
You modified the parameters of the users dial-up netowrk connection? Or was this in the days of modem to modem, i.e. non-internet, network gaming? As long as you set the network settings back the way they were I guess it isn’t a problem… still seems scary to me though - what if you crashed before you could restore the settings?

#117

[quote]On those thin analog lines remember you are running serial PPP, which means that the overhead for a UDP packet (30 bytes) is 15 times larger then for a TCP packet (2 bytes.)
[/quote]
Right, but much of what I’ve been saying (UDP+FEC, TCP throughput bounds due to ping time and ack windows), applies mainly to higher speed connections, not serial PPP (does PPPoE have the same advantage?). I’m basing my comments on broadband, which will be the majority of on-line users in North America soon enough. (well before I complete a project, that’s for sure :)!)

[quote]As I think I mentioned this was a large part of why we were TCP based at TEN.
[/quote]
Yeah you’ve said that a zillion times :slight_smile:

Like you said you uses a combo of TCP and UDP at TEN (too many TLAs there!). You have to think about what you are trying to accomplish and use each where appropriate… e.g. TCP for the client to tell the server that it shot, UDP for the server to tell all the clients where to draw your rocket.

#118

[quote]Like you said you uses a combo of TCP and UDP at TEN (too many TLAs there!).
[/quote]
Actually no, you misunderstood me.

We were TCP based. We eventually developed a special hybrid protocol that used UDP to help certain conditions that occur during TCP for some specific games like Quake2. It wasn’t on the game-logic level. It was much lower, and really a way of augamenting TCP at the protocol level.

And thus my point was that you need to really understand whats happening at that level to make such domain specific custom hybrid protocols really work.

#119

Out of interest, whose implementation(s) of TCP/IP stacks are you using? How good is the hardware and software? Also, just how much less than 100ms is your ping time :slight_smile: ? And what bandwidths are you getting a 50% increase on?

I only ask because IME TCP has been very good to me in very low packet-loss very high bandwidth situations, although 100 ms sounds very high (I would expect to get significantly less than that trans-atlantic, IIRC?). At the same time, bad implementations of TCP have been excrutiatingly painful; back in the days of MSIE4 I used to encourage people to compare large high-bandwidth downloads via HTTP and then again via FTP and THEN with a specialist download client just to convince them that there were some seriously rubbish systems and protocol implementations around…(although I never dug deep to find out the precise causes of the differences in particular cases).

#120

[quote]You modified the parameters of the users dial-up netowrk connection? Or was this in the days of modem to modem, i.e. non-internet, network gaming? As long as you set the network settings back the way they were I guess it isn’t a problem… still seems scary to me though - what if you crashed before you could restore the settings?
[/quote]
This was over the internet using standard analog POPs.

AIR we created a new connection called something like “TEN Connection” that we referenced from the terminal program when we opened the connection to the POP.