11 ms·

The point of this article seems to be that high latency and packet loss combined with extremely high available bandwidth is not a scenario that TCP is optimised

The point of this article seems to be that high latency and packet loss combined with extremely high available bandwidth is not a scenario that TCP is optimised to handle. This would be interesting if I could think of a common scenario on the internet where you get that combination of features.

anon4 12y ago
100ms is not that high, that's less than what you get when you're in Europe and want to play with your American friends. And the issue is with delayed retransmission when you can actually afford to send the packets again preemptively. I would still agree that you should have a bit in the TCP stack that says "use preemptive retransmission instead of waiting so damn long". Can you actually tune the wait time for the ACKs?
- asuffield 12y ago
  Yeah, but the 100ms/1% version is more or less acceptable - some client-side smoothing would completely conceal those artifacts. It was at 250ms/5% that things really started to fall apart. I'd say that 1% packet loss is high, and the most likely reason why you'd have packet loss rates that high is because your network link is congested - in which case, sending more packets is the exact opposite of what you want to do. High latency, high packet loss, spare available bandwidth. I can think of lots of scenarios where you have two out of three of those things. I can't think of any where you get all three, and this idea only seems useful when you have all of them.
  - falcolas 12y ago
    Satellite or radio based ISPs, mobile networking, and if we get exotic, interplanetary communications all come to mind as environments which fit all three criteria.
    - asuffield 12y ago
      Interesting - I'm not sure that mobile networking really has massively overprovisioned bandwidth, but satellite and radio links might. Can you think of a way to identify these links so that similar techniques can be deployed when they are found?
      - falcolas 12y ago
        No, cellular data is not massively over provisioned; but in the era of LTE, I frequently have more bandwidth than stability. Also, this scheme is not really asking for massively over provisioned lines; we're looking at fairly small data sets with infrequent bursts to larger sets, and an ack from the receiver knocks the size back down again. That said, if I were implementing this, I would probably implement a sliding window for messages I send (waterfall encoding would work great here, though it is patent encumbered), and add the ability for the client to request a set of messages it missed. This would make the traffic a bit more predictable and offer the server & client the ability to make up for traffic which was lost during its send window.
  - comex 12y ago
    You're not sending more packets, but slightly larger packets - as the article says, even 120 frames of data takes up 90 bytes. When, even with extreme repetition, you're sending single digit kilobytes per second over the Internet, it's unlikely that your stream itself is substantially contributing to congestion, unless you have some completely broken/saturated link that nobody wants to play on anyway. (One might want to send enough bytes per frame that such a buffer would start to bump up against packet size limits, but 120 frames is ridiculous. I'm not even sure where he got it from, since 60 * 5 seconds timeout = 300, not 120 - and you don't really want to time out after 5 seconds, since transient total outages happen when accidentally going out of range of a Wi-Fi network or whatever. Layer the opportunistic resending on top of a TCP-like slow resend mechanism for the worst case, and then there's no point sending each packet more than a handful of times.) I implemented opportunistic resending last year for netplay in a branch of the Dolphin emulator. The target audience was a group of people playing a fighting game (Super Smash Bros.) at a semi-high level, so it was essential to keep latency to an absolute minimum. Even a few frames of lag is enough to substantially impede high level play (might be mitigated by prediction/rewinding if I ever implement that, but since fighting games are based on very quickly responding to others' actions, there's only so good it can get); the 100ms from the article, for example, would be totally unacceptable for anything serious. Even if it were feasible to implement client-side smoothing in an emulator, it would still be much superior to actually get the real data in time. The question is then whether packet loss is common/significant enough in practice that opportunistic resending's effects are visible in any significant way. For Dolphin, the main advantage of using UDP over TCP is actually NAT traversal, so there is no reason not to do it, but it would be nice to know whether it helped. Unfortunately, I don't have data here: I didn't include code to explicitly record packet loss statistics or anything, and I haven't had the time to actually clean up the code enough to promote it to master, so there aren't many people using it anymore. Anecdotally I implemented opportunistic resending, there was feedback that it was a noticeable improvement; there would certainly be some confirmation bias in there, but the feedback was positive enough to convince me it was likely a real effect. They didn't necessarily have to be losing a lot of packets; as the article mentions, with TCP a single packet lost makes you wait something like 2*RTT, which is certainly noticeable if your input buffer is set to the lowest possible value that produces smooth play under normal conditions.
  - gafferongames 12y ago
    I don't want to play a multiplayer game with hitches every few seconds. You can't fix this with "smoothing" with deterministic lockstep model but you could fix it by increasing the playout delay buffer from 100ms to 250ms, but that's adding another 150ms of latency to the player experience which is less than ideal. It's a much better option to use UDP in this case to get the best experience for most players.
ANTSANTS 12y ago
Games and streaming audio/video aren't common scenarios on the internet? Don't be distracted by latency/packet loss/bandwidth configurations, the main problem here is that TCP was never intended to serve the needs of soft-realtime communication. It's not relevant to deterministic lockstep, but for most realtime problems (I'm thinking of multiplayer FPS, but you can think of Skype if that's not "serious" enough for you), if you miss a packet of data, it might as well have never existed. Better to hear blips and glitches on a phone call over a shitty connection than to start adding seconds of latency. You missed the point about deterministic lockstep as well, which is intended for scenarios where trying to transmit i.e. the entire state of a virtual army per tick is prohibitive. Designing the program to behave deterministically so that you can send only the player inputs per tick is the exact opposite of an "extremely high available bandwidth" solution.
- asuffield 12y ago
  Audio/video streams are a completely different problem - lost data is just lost. This article is discussing a very specific problem where no data loss can be tolerated. The solution described only works when very high bandwidth is available, because it aggressively sends duplicate copies of data until acked, using on average 2-15x more bandwidth and 120x more bandwidth in the worst case (numbers taken directly from the article). If you happened to have that kind of spare bandwidth available then yes, this is an excellent solution. When do you have high latency, packet loss, and bandwidth overprovisioned by a factor of 15?
  - ANTSANTS 12y ago
    Deterministic lockstep is primarily used in RTS games, where the only data that is transmitted per tick are tiny commands like "player 1 is constructing a war factory at this location" or "player 1 told unit 6 to move to this tile." If we're ridiculously generous and say that a kilobyte of commands are sent per tick, then 120x bandwidth would be 120 kb/tick. 10 ticks/s is a common RTS tickrate, so that's about a megabyte per second. In practice, far, far less bandwidth would be used than this, given that this architecture scales down to 90's dialup connections (https://www.codeofhonor.com/blog/the-making-of-warcraft-part-3 https://www.codeofhonor.com/blog/the-making-of-warcraft-part...), but even a megabyte/s is not a completely ridiculous amount of upload bandwidth for much of the first world (but sadly not the USA). > Audio/video streams are a completely different problem - lost data is just lost. This article is discussing a very specific problem where no data loss can be tolerated. I know that, which is why I separated deterministic lockstep from other solutions in my comment. You're missing my point, which is that soft-realtime problems aren't suited for TCP, and cannot be addressed by any single protocol because constraints differ.
felixgallo 12y ago
The author is a very experienced games network programmer whose recent credits include the multiplatform fps Titanfall.
- asuffield 12y ago
  Then I will make my plea a lot more urgent: Please do not implement protocols on the internet which respond to congestion by increasing the amount of traffic they send, if there is any chance that they might be used by a large number of people. This is poor internet citizenship and causes real problems. It means your code is a DoS attack against the internet transit links, which can be triggered by anybody capable of inducing low levels of packet loss, and the only effective mechanism to stop it is for ISPs to block the traffic entirely. Packet loss is how the internet signals that you're sending more bandwidth than it has capacity to forward. Internet protocols need to respond politely to this signal.
  - Timmmmmm 12y ago
    Not in this case - packets can be dropped by the route and the game player doesn't care as long as his connection is good enough to play. When it gets really bad the player will likely quit and the packets will stop. If it is really desired you could implement throttling according to packet loss, but not in the way that TCP does it - by buffering and waiting - instead you'd just send packets every N frames. You can't do that if you're just using TCP since you don't know when packets are dropped.
    - asuffield 12y ago
      > If it is really desired you could implement throttling according to packet loss, but not in the way that TCP does it - by buffering and waiting - instead you'd just send packets every N frames. You can't do that if you're just using TCP since you don't know when packets are dropped. It is really desired (and there are a bunch of ways to do it, and plenty of libraries that already implement them). Please, please implement protocols in this way, and not in the way described in the article.
gafferongames 12y ago
No the point of this article is to describe how deterministic lockstep works in the context of networking a physics simulation and how UDP is provably more efficient for sending time critical data over the internet in the presence of latency and packet loss.

anon4 12y ago

100ms is not that high, that's less than what you get when you're in Europe and want to play with your American friends. And the issue is with delayed retransmission when you can actually afford to send the packets again preemptively. I would still agree that you should have a bit in the TCP stack that says "use preemptive retransmission instead of waiting so damn long". Can you actually tune the wait time for the ACKs?

asuffield 12y ago
Yeah, but the 100ms/1% version is more or less acceptable - some client-side smoothing would completely conceal those artifacts. It was at 250ms/5% that things really started to fall apart. I'd say that 1% packet loss is high, and the most likely reason why you'd have packet loss rates that high is because your network link is congested - in which case, sending more packets is the exact opposite of what you want to do. High latency, high packet loss, spare available bandwidth. I can think of lots of scenarios where you have two out of three of those things. I can't think of any where you get all three, and this idea only seems useful when you have all of them.
- falcolas 12y ago
  Satellite or radio based ISPs, mobile networking, and if we get exotic, interplanetary communications all come to mind as environments which fit all three criteria.
  - asuffield 12y ago
    Interesting - I'm not sure that mobile networking really has massively overprovisioned bandwidth, but satellite and radio links might. Can you think of a way to identify these links so that similar techniques can be deployed when they are found?
    - falcolas 12y ago
      No, cellular data is not massively over provisioned; but in the era of LTE, I frequently have more bandwidth than stability. Also, this scheme is not really asking for massively over provisioned lines; we're looking at fairly small data sets with infrequent bursts to larger sets, and an ack from the receiver knocks the size back down again. That said, if I were implementing this, I would probably implement a sliding window for messages I send (waterfall encoding would work great here, though it is patent encumbered), and add the ability for the client to request a set of messages it missed. This would make the traffic a bit more predictable and offer the server & client the ability to make up for traffic which was lost during its send window.
- comex 12y ago
  You're not sending more packets, but slightly larger packets - as the article says, even 120 frames of data takes up 90 bytes. When, even with extreme repetition, you're sending single digit kilobytes per second over the Internet, it's unlikely that your stream itself is substantially contributing to congestion, unless you have some completely broken/saturated link that nobody wants to play on anyway. (One might want to send enough bytes per frame that such a buffer would start to bump up against packet size limits, but 120 frames is ridiculous. I'm not even sure where he got it from, since 60 * 5 seconds timeout = 300, not 120 - and you don't really want to time out after 5 seconds, since transient total outages happen when accidentally going out of range of a Wi-Fi network or whatever. Layer the opportunistic resending on top of a TCP-like slow resend mechanism for the worst case, and then there's no point sending each packet more than a handful of times.) I implemented opportunistic resending last year for netplay in a branch of the Dolphin emulator. The target audience was a group of people playing a fighting game (Super Smash Bros.) at a semi-high level, so it was essential to keep latency to an absolute minimum. Even a few frames of lag is enough to substantially impede high level play (might be mitigated by prediction/rewinding if I ever implement that, but since fighting games are based on very quickly responding to others' actions, there's only so good it can get); the 100ms from the article, for example, would be totally unacceptable for anything serious. Even if it were feasible to implement client-side smoothing in an emulator, it would still be much superior to actually get the real data in time. The question is then whether packet loss is common/significant enough in practice that opportunistic resending's effects are visible in any significant way. For Dolphin, the main advantage of using UDP over TCP is actually NAT traversal, so there is no reason not to do it, but it would be nice to know whether it helped. Unfortunately, I don't have data here: I didn't include code to explicitly record packet loss statistics or anything, and I haven't had the time to actually clean up the code enough to promote it to master, so there aren't many people using it anymore. Anecdotally I implemented opportunistic resending, there was feedback that it was a noticeable improvement; there would certainly be some confirmation bias in there, but the feedback was positive enough to convince me it was likely a real effect. They didn't necessarily have to be losing a lot of packets; as the article mentions, with TCP a single packet lost makes you wait something like 2*RTT, which is certainly noticeable if your input buffer is set to the lowest possible value that produces smooth play under normal conditions.
- gafferongames 12y ago
  I don't want to play a multiplayer game with hitches every few seconds. You can't fix this with "smoothing" with deterministic lockstep model but you could fix it by increasing the playout delay buffer from 100ms to 250ms, but that's adding another 150ms of latency to the player experience which is less than ideal. It's a much better option to use UDP in this case to get the best experience for most players.

ANTSANTS 12y ago

Games and streaming audio/video aren't common scenarios on the internet? Don't be distracted by latency/packet loss/bandwidth configurations, the main problem here is that TCP was never intended to serve the needs of soft-realtime communication. It's not relevant to deterministic lockstep, but for most realtime problems (I'm thinking of multiplayer FPS, but you can think of Skype if that's not "serious" enough for you), if you miss a packet of data, it might as well have never existed. Better to hear blips and glitches on a phone call over a shitty connection than to start adding seconds of latency. You missed the point about deterministic lockstep as well, which is intended for scenarios where trying to transmit i.e. the entire state of a virtual army per tick is prohibitive. Designing the program to behave deterministically so that you can send only the player inputs per tick is the exact opposite of an "extremely high available bandwidth" solution.

asuffield 12y ago
Audio/video streams are a completely different problem - lost data is just lost. This article is discussing a very specific problem where no data loss can be tolerated. The solution described only works when very high bandwidth is available, because it aggressively sends duplicate copies of data until acked, using on average 2-15x more bandwidth and 120x more bandwidth in the worst case (numbers taken directly from the article). If you happened to have that kind of spare bandwidth available then yes, this is an excellent solution. When do you have high latency, packet loss, and bandwidth overprovisioned by a factor of 15?
- ANTSANTS 12y ago
  Deterministic lockstep is primarily used in RTS games, where the only data that is transmitted per tick are tiny commands like "player 1 is constructing a war factory at this location" or "player 1 told unit 6 to move to this tile." If we're ridiculously generous and say that a kilobyte of commands are sent per tick, then 120x bandwidth would be 120 kb/tick. 10 ticks/s is a common RTS tickrate, so that's about a megabyte per second. In practice, far, far less bandwidth would be used than this, given that this architecture scales down to 90's dialup connections (https://www.codeofhonor.com/blog/the-making-of-warcraft-part-3 https://www.codeofhonor.com/blog/the-making-of-warcraft-part...), but even a megabyte/s is not a completely ridiculous amount of upload bandwidth for much of the first world (but sadly not the USA). > Audio/video streams are a completely different problem - lost data is just lost. This article is discussing a very specific problem where no data loss can be tolerated. I know that, which is why I separated deterministic lockstep from other solutions in my comment. You're missing my point, which is that soft-realtime problems aren't suited for TCP, and cannot be addressed by any single protocol because constraints differ.

felixgallo 12y ago

The author is a very experienced games network programmer whose recent credits include the multiplatform fps Titanfall.

asuffield 12y ago
Then I will make my plea a lot more urgent: Please do not implement protocols on the internet which respond to congestion by increasing the amount of traffic they send, if there is any chance that they might be used by a large number of people. This is poor internet citizenship and causes real problems. It means your code is a DoS attack against the internet transit links, which can be triggered by anybody capable of inducing low levels of packet loss, and the only effective mechanism to stop it is for ISPs to block the traffic entirely. Packet loss is how the internet signals that you're sending more bandwidth than it has capacity to forward. Internet protocols need to respond politely to this signal.
- Timmmmmm 12y ago
  Not in this case - packets can be dropped by the route and the game player doesn't care as long as his connection is good enough to play. When it gets really bad the player will likely quit and the packets will stop. If it is really desired you could implement throttling according to packet loss, but not in the way that TCP does it - by buffering and waiting - instead you'd just send packets every N frames. You can't do that if you're just using TCP since you don't know when packets are dropped.
  - asuffield 12y ago
    > If it is really desired you could implement throttling according to packet loss, but not in the way that TCP does it - by buffering and waiting - instead you'd just send packets every N frames. You can't do that if you're just using TCP since you don't know when packets are dropped. It is really desired (and there are a bunch of ways to do it, and plenty of libraries that already implement them). Please, please implement protocols in this way, and not in the way described in the article.

gafferongames 12y ago

No the point of this article is to describe how deterministic lockstep works in the context of networking a physics simulation and how UDP is provably more efficient for sending time critical data over the internet in the presence of latency and packet loss.