I've wrote another part-of-the-chapter for my upcoming book: http://ithare.com/mmog-rtt-input-lag-and-how-to-mitigate-them/ , and given the expertise of the audience here, I think I should ask for comments here, at the very least to make sure that I'm not making some silly mistakes.

There is nothing really new in this part, but the way it is organized might be not that usual, so if the flow feels confusing - please let me know. Also of particular interest are your observations about real-world RTTs (which always have an element of subjective experience), and of course, any further means of dealing with the input lag (ideally - without opening a door for cheaters too wide). which I've forgot about or never knew in the first place.

In any case, all the comments will be appreciated :-) .

It is obvious that the delay between player pressing a button, and her seeing results of herself pressing the button (which is known as “input lag”), will be at least so-called round-trip-time (RTT) between client and server

You got it all wrong, like I told you yesterday.

There's no delay between a player pressing a button and her seeing results of herself pressing the button, since on the client you run a graphical simulation of the physical one you're running server side. Get any AAA game, disconnect your cable, and immediately press a button. The character will perform any action (move,shoot,jump,cast,dance) that was assigned to that key, and you will be able to see the effects of that action on the world.

but even in a very ideal case, there are hard limits on “how low you can go with regards to RTT”.

Not really. You can go as low as you want by having different servers for different countries, or even regions. Latency is constrained by the speed of light. Hence, 20ms RTT is equivalent to ~3000km, or a 1860 mile radius for light traveling in vacuum. Our data packets travel through fiber, which slows us down by a factor of ~1.52, which translates to 2027 km, or a 1260 mile radius. What is remarkable is that we are already within a small constant factor of the theoretical limit.

What if when we’re extrapolating NPC’s movement, he runs into the wall?

And again the character won't ever run through the wall if the client doesn't allow it.

The client is not a physical renderer, it's not what you think it is. Let's say a player throws a fireball at a target at client time 10.5. The firing information is packed into a user command and sent to the server. While the packet is on its way through the network, the server continues to simulate the world, and the target might have moved to a different position. The user command arrives at server time 10.6 and the server wouldn't detect the hit, even though the player has aimed exactly at the target. This error is corrected by the server-side lag compensation. The lag compensation system keeps a history of all recent player positions for one second. If a user command is executed, the server estimates at what time the command was created as follows: Command Execution Time = Current Server Time - Packet Latency - Client View Interpolation Then the server moves all other players - only players - back to where they were at the command execution time. The user command is executed and the hit is detected correctly. After the user command has been processed, the players revert to their original positions. This is esentially why the world is always rendered in the past. What you call "Client Side Prediction" is not a prediction, is the real deal. Ever wondered why you can't cast two spells at the same time in any MMORPG?

like I told you yesterday

Your post yesterday was reported to the moderation queue and it seems it was removed due to consisting of unprofessional personal attacks and adding no value to the discussion. Act professionally, please.

there is one big problem with the flow shown on this diagram ... It is obvious that the delay between player pressing a button, and her seeing results of herself pressing the button (which is known as “input lag”), will be at least so-called round-trip-time (RTT) between client and server
You got it all wrong, like I told you yesterday.

You left out the bolded and underlined section that gives context to the italic quote... After starting with that simplistic diagram, he goes on to introduce client-side prediction as a solution to this problem... which you know, as your next quote is lifted from the section on prediction. You're just being disingenuous here.

What if when we’re extrapolating NPC’s movement, he runs into the wall? ... we need to take it into account when extrapolating, and detect when our extrapolated NPC collides.
And again the character won't ever run through the wall if the client doesn't allow it.

Again, you're removing half the quote and then telling him that he hasn't said the thing that you've cut.

While the packet is on its way through the network, the server continues to simulate the world, and the target might have moved to a different position. The user command arrives at server time 10.6 and the server wouldn't detect the hit, even though the player has aimed exactly at the target. This error is corrected by the server-side lag compensation. The lag compensation system keeps a history of all recent player positions for one second. If a user command is executed, the server estimates at what time the command was created as follows: Command Execution Time = Current Server Time - Packet Latency - Client View Interpolation Then the server moves all other players - only players - back to where they were at the command execution time. The user command is executed and the hit is detected correctly. After the user command has been processed, the players revert to their original positions. This is esentially why the world is always rendered in the past. What you call "Client Side Prediction" is not a prediction, is the real deal.

Even in games that use that network model (often called the Counter-Strike network model ), yes, it's still client side prediction. A team-mate may have walked into you right before you fired that projectile, so the server might disagree with where you think you were standing. Or, the enemy might have killed you before you fired the shot, so the server might reject your command to fire your projectile altogether.

If the client code perfectly matches the server code, then the prediction will usually be 100% correct, but direct interactions between players can still cause prediction failures. In counter-strike, you usually only notice prediction errors when you're playing on a high-ping server and walk directly into other players, or get killed yourself at the same time that you think you've killed someone (except, they survive unscathed).

It's also not a universal networking model, and not used widely by MMO's. Different games do run different amounts of game logic on the client. Yes, some games do use dumb extrapolation without full client-side collision detection. Other games run all the collision detection on the client and none on the server. It all depends on the situation.

direct interactions between players can still cause prediction failures.

Exactly, and this is unavoidable at least for an authoritative server. In a general case (the one which allows inter-player interactions), client cannot be "the real deal" if we're using an authoritative server (and network models without an authoritative server were moved outside the scope of the book because of various issues, mostly cheating-related ones).

There are as many strategies for dealing with the various types of multiplayer latencies as there are successful multiplayer games. I found the article to be a decent treatment of a particularly popular group of strategies in use in MMOs and other similar systems, although it's by no means exhaustive (which I understand, and do not fault).

Casting multiple concurrent spells is actually trivial in most MMOs; it's often not done for design or balance reasons. I'd be shocked if any real MMO had a technical limitation on this. In fact I can state without hesitation that at least one MMO allows you to fire-and-forget a spell and then fire another one while the first is still active in the world ;-)

As for didntwant's criticisms, an advanced reader might get less frustrated it the wording is slightly edited to make it more clear that you're building up a picture by laying out broad strokes first, which contain issues, and then addressing those issues later. The bits that he's misquoted for example could be more clear that these problems lie with the simplistic algorithms introduced so far, and the solutions lie further ahead in the text.

There are as many strategies for dealing with the various types of multiplayer latencies as there are successful multiplayer games. I found the article to be a decent treatment of a particularly popular group of strategies in use in MMOs and other similar systems, although it's by no means exhaustive (which I understand, and do not fault).

Assuming we deal with authoritative servers, what other approaches could be (if any)?

You can combine building blocks (time frames, extrapolation, display, etc) in different ways.
For example, for There.com, designed to support up to 100 physical objects on a 56k modem, each object was deterministically simulated between client and server.
Checksums were exchanged for object state at particular simulation ticks. If the checksum mis-matched, the simulation state of the object was re-sent.
Input was time-stamped as well, and sent to the server (and forwarded to other viewing clients.)

The main trick with There (which I believe the founders filed for a patent on) was:
The client would simulate and display objects that are "far" from the viewing player "in the past" but would move up the time frame to that of the ocal player of objects that moved close to the player. Thus, a player would be likely to see "truth" of objects controlled by others in the distance, and have immediate control of objects nearby.
When two players are both attempting to control an object, one will actually "win" and the other will see a checksum mis-match and "correction" of that object.
Also, some interactions were put on the client. Two cars being piloted, and colliding, would both seem to be reacting correctly, but in different time frames on different player machines, and would, post-collision, end up in the same locations. This was because each player informed the server and other players of client-side detected collisions -- but those collisions would, on the other player's machines, only affect that player's object. Meanwhile, if the server detected a collision but the client hadn't requested it, the client got corrected, so you couldn't cheat (much) by disabling the "send a collision event" code.

Assuming we deal with authoritative servers, what other approaches could be (if any)?

Many of the more common features are based on public post-mortems or public writeups of how the networking was accomplished.

The one described in no-bug's article is typically called the counterstrike / valve model, since that's where it was widely published. The thing that was innovative at the time was that effectively the server would rewind time, validate that they could be properly inserted at that time, then re-simulate from that point. Most of the rest of the model was based on existing networking models.

The Doom model was only used for a short time, but it was widely published at the time in the PCGPE. (PC Game Programmer's Encyclopedia). There wasn't anything fancy going on, and relative to what you see today the network code was laggy and terrible at anything except local network play. It was enough to get the job done.

The Quake model, common in the late 1990s on action games, was to basically simulate what you've got and then correct the positions when new data came. It still did the dead reckoning and prediction that nothing would change. (Note that they did not rewind time like the counterstrike model would eventually introduce, only run the simulation and snap/slide people to correct locations on update.) These models also tended to use a data compression model of sending large block deltas that had sequencing difficulties. On highly reliable networks they worked well enough, but on unreliable networks performance became terrible.

The Quake3 model was picked up by a lot of other networking systems of the era, and it improved on the Quake model. Instead of larger deltas and assuming reliable packets, a sequence of deltas were combined and compressed together. Every time a sequence number is passed it includes the sequence number of the last packet they handled. So instead of sliding windows preserved for retransmission, they retransmitted all the windows every time until acknowledged, then dropped the tail of the window. This used more bandwidth but with widespread adoption of faster internet access it wasn't a problem. Again, clients used dead reckoning and estimation, but they did not rewind time to insert data as the counterstrike method since that wasn't out yet.

Another historic model was used in RTS genre and bears mentioning here. It was used by Westwood in Dune games and Command and Conquer, and by Blizzard in Warcraft and Warcraft 2, and by the Age of Empires folks. It was best known from the 1500 Archers paper. Some systems went full lockstep, others partial lockstep and partial independent simulations. Even though what you saw on screen was fluid animation, the simulation operated on 4 or 5 updates per second. All the events of a simulation step were forwarded for execution two simulation steps in the future. So if you sent a command at simulation step 2000 by clicking a command, it would be queued for execution on simulation step 2002, and optionally show a pre-animation on simulation step 2001. That would give plenty of time for all clients to receive and process the command before executing it. You would hear a response immediately on your side so you know the command was issued, e.g. "Yes Sir!", followed by a pre-execution animation of turning or dust or whatever, followed by motion a half second later. Combined this meant the simulation could be slow, just four updates per second, but the feedback could be instant to the player and animation variations could give visually pleasing experiences.

Some of the effects of the 1500 Archers model are still useful and common in today's shooters. Many games that employ the counterstrike model for lag compensation also use the archers model to help mask communication times. They can enqueue and broadcast the command while showing a 45+ms trigger pulling animation. They can communicate to the player that bullets take time to fly through the air by showing a tracer line for another 3 or more frames and a small puff of smoke, buying another 45ms-60ms. The local animations give the player a feeling of immediate responsiveness but also allow some time for machines to communicate

Every game tends to incorporate different techniques, those are just a few of them. Generally they are not publicly discussed, but you will see a few conference papers or public post-mortems about features a game added to their networking toolkit. Most are fairly standard techniques that are commonplace, but occasionally someone will document a groundbreaking technique.

Assuming we deal with authoritative servers, what other approaches could be (if any)?

I'd advise against the (naive) assumption that server authority is a binary switch. It's thoroughly possible to have a continuum of levels of authority and for various operations within the game world to fall in different places on that spectrum. (This is actually common practice with things like particle effects and debris, where the simulation of, say, a shower of sparks is local to a given player since it has no "game changer" effects on the world.)

As soon as you have this flexibility, the models of authority and security are as varied as the rules of the game itself.