6 ms·

Thanks for the pointer to fountain codes. Though, since I'm working on a networked game that works over websockets, this is basically something I wouldn't bothe

by ehsanu1 15y ago

Thanks for the pointer to fountain codes. Though, since I'm working on a networked game that works over websockets, this is basically something I wouldn't bother with since websockets are TCP, not UDP, and as such they are guaranteed delivery and correct order of arrival. I realize TCP vs UDP is something of a debate in game networking, but it's a simple solution here. Let the protocol do the work and just send (compressed) deltas. I suppose this is equivalent to the Doom way.

eru 15y ago
Yes, it's for the protocol to worry about. imurray basically described a protocol to build on top of UDP that has slightly weaker guarantees than TCP. (Or does the construction that immurray described benefit from domain knowledge about the underlying data?)
- imurray 15y ago
  eru makes a really good point, and I suddenly feel much less confident. My intention was to sketch the idea for a protocol that was reliable (with very high probability, just like anything in the real world). So, to repeat the argument: if there's some information we need reliably, whatever cunning thing we layer on top of UDP, we're just reimplementing what TCP does. It seems unlikely we can do better than TCP unless we're doing something very problem specific. I guess the argument is that a scheme based on UDP can have very low latency a lot of the time, only occassionally stalling while waiting for more data. Whereas TCP, which needs acknowledgements and to keep packets in order, has a uniformly high latency. For this particular type of application, the tradeoffs are different from typical internet use?
  - krakensden 15y ago
    > For this particular type of application, the tradeoffs are different from typical internet use? Absolutely. The value of any one packet is fairly low, you can interpolate the player's path, hell, maybe no one else was looking at him at the time. But with TCP, you basically stop the world for a couple roundtrips to make sure you have that packet, so all the packets you received after the original drop and before the retransmission are no longer useful, and you have to drop them too. It's also worth noting that TCP does /not/ have a uniformly high latency, it does the sawtooth thing. In other words, if Level3 decides they're going to shovel a bunch of your ISP's traffic into the bitbucket for a second, your packets have been dropped, the server is going to wait until it has a complete set of packets, and your TCP implementation has decided to throttle the number of packets you can send to catch up.
  - eru 15y ago
    > So, to repeat the argument: if there's some information we need reliably, whatever cunning thing we layer on top of UDP, we're just reimplementing what TCP does. It seems unlikely we can do better than TCP unless we're doing something very problem specific. We can do much better than TCP. We just have to weaken the reliability requirement. And like you say, in the real world, that can go quite a long way, without actually being much weaker than TCP.
  - stonemetal 15y ago
    TCP is kind of the full feature kid on the block. You might do better making up a protocol that has what you want and skip on the rest. There are real latency costs for parts of TCP that a game will never use i.e. Nagle's algorithm(sure you can turn that one off but every thing has its cost and you can't turn off everything you don't need in TCP). I am surprised how infrequently RTP comes up in these conversations. Something close to RTP seems like it would be ideal for games.
- nitrogen 15y ago
  A comparison of transport protocols to consider if anyone reading this ever decides to try their hand at implementing such a quasi-reliable UDP-based protocol: https://secure.wikimedia.org/wikipedia/en/wiki/Transport_layer#Comparison_of_Transport_Layer_protocols https://secure.wikimedia.org/wikipedia/en/wiki/Transport_lay... In addition to that list, there are µTP and rpp, plus others no doubt.
iqster 15y ago
Apart from the timelines, my impression is that implementing fountain codes has some IP issues. Also, there is some code complexity in getting them implemented correctly (as hard to get right as paxos). Anyone know a game that used these? Any body have first hand experience?
- imurray 15y ago
  If considering using fountain codes, I would definitely want to check out the IP issues; there are certainly some patents in that space. For the application being discussed, fountain codes wouldn't be an exact fit anyway. I pointed to them because the ideas used in fountain codes are fantastic, and it might be possible to do something with that flavor. (I too would love to hear first-hand experience of anyone who's used this type of code.)
  - eru 15y ago
    Too bad I only ever proved theorems about codes, but didn't actually use them. But many of code are really beautiful.

by ehsanu1 15y ago

eru 15y ago

Yes, it's for the protocol to worry about. imurray basically described a protocol to build on top of UDP that has slightly weaker guarantees than TCP. (Or does the construction that immurray described benefit from domain knowledge about the underlying data?)

imurray 15y ago
eru makes a really good point, and I suddenly feel much less confident. My intention was to sketch the idea for a protocol that was reliable (with very high probability, just like anything in the real world). So, to repeat the argument: if there's some information we need reliably, whatever cunning thing we layer on top of UDP, we're just reimplementing what TCP does. It seems unlikely we can do better than TCP unless we're doing something very problem specific. I guess the argument is that a scheme based on UDP can have very low latency a lot of the time, only occassionally stalling while waiting for more data. Whereas TCP, which needs acknowledgements and to keep packets in order, has a uniformly high latency. For this particular type of application, the tradeoffs are different from typical internet use?
- krakensden 15y ago
  > For this particular type of application, the tradeoffs are different from typical internet use? Absolutely. The value of any one packet is fairly low, you can interpolate the player's path, hell, maybe no one else was looking at him at the time. But with TCP, you basically stop the world for a couple roundtrips to make sure you have that packet, so all the packets you received after the original drop and before the retransmission are no longer useful, and you have to drop them too. It's also worth noting that TCP does /not/ have a uniformly high latency, it does the sawtooth thing. In other words, if Level3 decides they're going to shovel a bunch of your ISP's traffic into the bitbucket for a second, your packets have been dropped, the server is going to wait until it has a complete set of packets, and your TCP implementation has decided to throttle the number of packets you can send to catch up.
- eru 15y ago
  > So, to repeat the argument: if there's some information we need reliably, whatever cunning thing we layer on top of UDP, we're just reimplementing what TCP does. It seems unlikely we can do better than TCP unless we're doing something very problem specific. We can do much better than TCP. We just have to weaken the reliability requirement. And like you say, in the real world, that can go quite a long way, without actually being much weaker than TCP.
- stonemetal 15y ago
  TCP is kind of the full feature kid on the block. You might do better making up a protocol that has what you want and skip on the rest. There are real latency costs for parts of TCP that a game will never use i.e. Nagle's algorithm(sure you can turn that one off but every thing has its cost and you can't turn off everything you don't need in TCP). I am surprised how infrequently RTP comes up in these conversations. Something close to RTP seems like it would be ideal for games.
nitrogen 15y ago
A comparison of transport protocols to consider if anyone reading this ever decides to try their hand at implementing such a quasi-reliable UDP-based protocol: https://secure.wikimedia.org/wikipedia/en/wiki/Transport_layer#Comparison_of_Transport_Layer_protocols https://secure.wikimedia.org/wikipedia/en/wiki/Transport_lay... In addition to that list, there are µTP and rpp, plus others no doubt.

iqster 15y ago

Apart from the timelines, my impression is that implementing fountain codes has some IP issues. Also, there is some code complexity in getting them implemented correctly (as hard to get right as paxos). Anyone know a game that used these? Any body have first hand experience?

imurray 15y ago
If considering using fountain codes, I would definitely want to check out the IP issues; there are certainly some patents in that space. For the application being discussed, fountain codes wouldn't be an exact fit anyway. I pointed to them because the ideas used in fountain codes are fantastic, and it might be possible to do something with that flavor. (I too would love to hear first-hand experience of anyone who's used this type of code.)
- eru 15y ago
  Too bad I only ever proved theorems about codes, but didn't actually use them. But many of code are really beautiful.