A client-server (star) topology
This paper discusses the problems that programmers and game designers encounter and have to solve in order to implement multiplayer games for networks.
It's important to realise that making a game multiplayer and/or networked may impose rather strict limitations on how the game can be implemented and in the game rules themselves. For that reason, the game should be carefully designed from the start.
By far, the easiest category of games that can be made networkable are the turn based games, such as card and board games. The time between user actions is relatively long (from probably about a second up to minutes). Apart from the relative ease of managing the timing, all the other challenges of making a game networked exist. Remember, that to the user, a turn-based game could be just as much fun as any other game.
Strategy and role playing games usually have several human players acting simultaneously, but it's usually possible to design the game so that the player doesn't really mind if there's a slight delay before his/her orders are actually carried out.
Simulations, such as flight simulators, require more evolved algorithms in order to mask the problems that large scale networks cause, but fortunately there are solutions that work reasonably well and are not too difficult to understand and implement. The most important technique for large scale simulations is "dead reckoning", which is discussed later in this paper.
The worst category for the programmer is what are called action or 'twitch' games. Fast reaction time is usually the most important quality that the player can have and unfortunately network latency usually far exceeds the reaction times of even the best players, making it hard to make the game playable over longer distances or analog modems.
The problems that you have to deal with depend a lot on the type of network you are using. Whatever the platform is, you have to deal a multiprocessing situation.
LANs make a very easy platform for writing networked games, but unfortunately it means that the players have to have their computers networked in order to be able to play. This limits the number of customers that you will attract: mostly schools, universities and companies where games are allowed.
Modem to modem games make it slightly easier to find people to play with, but it means you'll be limited to just two players for each game and you start to encounter many of the same problems that larger networks have, so you might just as well design a little better and offer full networkability.
The Internet has one thing going for it: there are millions of potential game players (customers) on it at all times. Unfortunately that's where the good news ends: at this writing (December 1997) most parts of the net are highly congested and unreliable and most users are using old analog modem technology to connect to the network, which brings along even more problems.
From a financial point of view, it makes better sense to write for the Internet, since whatever works well there, will work well on a local area network too. It's usually pretty easy to implement modem to modem play, if your game is playable on the Internet. Remember to test on the worst case network (on the internet, over the longest possible distances.) On a LAN (local area network), you will usually be lucky and get away with things that will almost never work on the Internet. It's possible to write code that will simulate long distance internet connections, but nothing will beat a real game running between Finland and Australia.
It's not too hard to make a game work between two players, but as soon as you introduce a third player, all sorts of interesting things will start to happen. A good understanding of process synchronization primitives is required.
Once the game works well for three players, it will usually scale pretty well up to 6-8 well connected players. Going beyond that will require more careful design, because the communication bandwidth requirements will easily increase beyond anything that is available.
For medium sized games (8-100) players, a single server might be sufficient. The game still has to manage the connections to the clients (players) very carefully, or the server will quickly run out of steam.
Once you go beyond 30-40 players, you should seriously consider using a network of servers that somehow distribute their work. This will of course add complexity and again, something that works fine with just two servers can fail in amazing ways when you introduce a third server. Design and test carefully in demanding conditions.
Why do people bother with games anyway? For various reasons, games are fun to play. It's probably next to impossible to give a completely accurate description of what makes a game playable or fun, but I'll try to give a few pointers here.
People are usually most involved in games while they are still learning new things while they are playing. For that reason, the learning curve that the game presents to the user is an important part of how addictive the game is. Life is full of challenges, but unfortunately many of them are trivial and some of them are insurmountable. In an ideal game, all the challenges are interesting, but at the same time they are also possible to solve.
In a single player game, the game designer balances the game so that the player doesn't feel frustrated either because it's too easy (which becomes tedious really quickly) or too difficult.
Networked games are harder to balance, because of the human element. A beginner will easily become frustrated if confronted by a virtually unbeatable expert. If too much chance is involved in game play, the intermediate player will become frustrated, because there's nothing new to learn and there's no "expert level" to progress to.
To keep all levels of players interested, make sure that they all have something interesting to aim for. Beginners will like the instant gratification of being able to occasionally beat an expert player. Experts may have a long term involvement in a game, so they like being able to develop their character, equipment or game statistics. Once there's nothing new to expect from the game, the player starts to lose interest.
Consider a racing game where all cars are equal. A good driver will be able to outpace beginners, which tends to separate the players on the track and makes for a less interesting game for poorly matched players. Coin-op games solve this problem by adjusting the realism of the of the game to make it more "playable" (by their standards - you may of course disagree, if you believe in fair play). The leading player is not allowed to drive as fast as the one who is second. Similarly, the player who is third will be able to catch the first two, etc. For virtually equally skilled players, this means that the players will keep passing each other. It's not realistic, but it makes for a more exciting game especially when all players are not equal.
Skill still plays a large part in doing well, so the expert players are not totally frustrated by this lack of realism. For championships, the games have a setting where all the cars are equal regardless of race position, but at least by the time players reach the finals, they are likely to be relatively equal in skills, so the race will be interesting to them.
People are social: they like to chat and make friends while they are playing. For many, the chatting may become more interesting than the game itself. Intermediate and expert players also often make good tutors and they give technical support to new players who are having problems. It's absolutely required to give some kind of text chatting ability for the players, so that they can communicate easily. They should be able to communicate during all phases of their gaming experience:
Advanced voice compression technology now allows speech to be transmitted with a connection that uses only about 300 bytes per second. For many people, it's much easier to just speak their mind than to type, so consider allowing speech communication in addition to text-based messages.
Another idea that has been used quite widely is to allow the players to send pre-recorded voice messages with a press of a single key. They are usually taunts and greetings. Even better, you could allow your users to pre-record their own taunts and then let them play the sounds with a single keypress. The sound samples only need to be transmitted once to each player.
A victory become much more gratifying when your opponent has a face or some other identifying character. In addition to a nickname, my game Avara also allows players to design their own 64x64 pixel color icons. This feature has been very popular. Avara also shows the location of the player on a world map: on the Macintosh many users set this information when they adjust the time zone of their computer.
As has been noted above, there are several different kinds of players. In addition to differences in skill levels (novice-intermediate-advanced), there are also other kinds of players.
One unfortunate type is the player who is there to ruin the fun for others and try to cheat in as many ways as possible. If you think about it, it's just like a game within a game. You, as the game designer, should make sure the party-poopers can not ruin the fun for the others. They are a small minority and they're usually not the best paying customers around.
Some people just like to be spectators. If possible, the game should allow users to just watch a game and enjoy a good game and the company of their friends. Even an avid player will sometimes want to sit out a game and still observe what the others are doing. Remember that this player might also want to join in in the middle of the game, so if possible, allow for that. Good games also allow recordings to be made so that interesting games can be shared with people who didn't see the game happen firsthand.
Never let one group ruin the fun for others! Experts shouldn't be able to drive out beginners, nor should the game be so watered down that advanced players become bored quickly.
There are three primary connection properties that you should be aware of when designing a game:
|
|
LAN |
Modem |
Internet |
|
Latency time |
low |
OK |
bad |
|
Reliability |
high |
OK |
bad |
|
Bandwidth |
high |
low |
low |
Processing power can also play a significant part, especially if the game is computationally intensive or if the computer has to do a lot of network I/O using the CPU.
Whatever the true topology of the network you are using is, you are likely to have a virtual game topology overlaid on it.
The most common solution is to have one player start a server or require a dedicated server machine and then have all the other players connect to that server. All data from client machines pass to the server, so in order for client A to send a message to client B, the message has to pass through the server. This can mean an increase in latency, a decrease in reliability due to the longer route and the server has to have enough bandwidth available.
If the server is reasonably well connected, a client-server (star) topology tends to work very well. Players that have good connections to the server tend to have an advantage, so it may be necessary to try to equalize things somehow. (For instance to transmit fresh data first to those clients with the highest latency from the server.)
Another approach is to make all the involved computers equal. Pure peer to peer (fully connected) networking means that player A sends messages directly to player B without the involvement of a server. The number of connections to make increases quickly, so this solution often become unmanageable if the maximum number of players is very high. Low-bandwidth connections (such as modems) may also easily become congested and unlike with client-server solutions, it's very hard to accurately control congestion.
If players have variable connection parameters and peer to peer networking, it may be a good idea to use routing, so that data from A to B may actually pass through C. If A wants the data to go to B and C, then sending it through C will make a lot of sense, especially if the bandwidth from A to B is larger than in the same order as from A to C to B. The latency and bandwidth savings can be considerable, if routing is used wisely. From the programmers point of view, the nodes are still fully connected.
If the game is to be played on a local area network, where latency is not an issue, but bandwidth is scarce and packet collisions cause a significant decrease in performance (something like Apple's LocalTalk), it may be better to create a (token) ring topology. In this model, only one connection is active at a time and precautions have to be made for a situation where "the token" is lost. The problem is that latency is accumulated, so in our example, if A wants to send something to B, it will have to wait until it gets the token (receives data from B), then transmit to C, which will send to D, which will send to B. Latency is at least tripled. If connection latency is low, it's not a big problem, but on the Internet, a pure token ring approach can be a fatal mistake, if your game requires any kind of real time interaction.
Some companies are betting that players are willing to pay a premium price for a good quality Internet connection.Gaming-oriented ISPs and networks (such as MPlayer and TEN), have less congested net backbone connections and can thus offer reduced latency and latency variance and much improved reliability. Users may still be limited to the bandwidth that their net connection offers (usually modems), but they will on average have reasonably good connections to other players on the same gaming network.
Whatever their connections are like players just want to have fun. Make the game work as well as possible even in the worst conditions without help from the user. Players should not have to ping servers manually to find out which one suits them best, nor should they have to make special routing arrangements to be able to play.
When a packet data has to be transmitted from one point (A) on the network to another (B), the time that it takes from when the transmission starts from A to when it has been completely received at B is called the latency of the connection.
latency = time per bit * number of bits + travel time
The dependence on the amount of data that is sent in each packet means that the longer the packet is, the longer it takes to send it. If the connection is very fast all the way from end to end, packet length doesn't matter much, but if old modems are involved, the increase in latency can be significant. Also, each router on the way usually has to receive the whole packet before it can pass it along to the next destination, so packet size has an effect even when the local transmission and receptions speeds are quite high.
There also seems to be a large built-in latency in analog POTS (Plain Old Telephone System) modems. Two players with PPP modem connections through the same ISP may have the same latency as two other players who have Ethernet connections, but are thousands of kilometers apart (on different continents). All this because the focus on modems has been on bandwidth instead of latency.
Latency is often measured using the roundtrip time, meaning the time that it takes for a packet of data to travel back and forth. Note that one way latency usually isn't exactly half the roundtrip latency. The problem is that one way latency is difficult to measure, because it requires accurately synchronized clocks (even GPS satellite systems have been used to synchronize clocks to determine one way latency). Roundtrip latency (often also called ping time, because of the close analogy with how submarine sonar works) is easy to measure and is a pretty good metric.
|
Network |
|
|
|
Ethernet LAN |
|
|
|
Modem to modem |
|
|
|
PPP to PPP |
|
|
|
ISDN to ISDN |
|
|
|
Internet |
up to a few seconds |
|
*) An educated guess - I will correct this as soon as I will have access to an ISDN connection.
In conclusion, analog (POTS) modems are really bad for latency. ISDN is a lot better and from there on, usually the faster your connection to the net is, the less latency you will get from your local connection. Unfortunately the Internet is really unpredictable in terms of latency. Some users have ISPs with highly congested connections to the Internet backbone, so latency time can be up to a few seconds just because data is queued up at your ISP. Realistically, you can expect a large portion of your users to achieve a roundtrip latency of around 500 msec. Once your local connection (modem, for instance) becomes congested, this number may go up quickly, so good congestion control also results in optimal latency.
The concept of latency fits poorly into the paradigm of time that most people have. If at all possible, you shouldn't worry users with such things as latency: make your game work well at high latency and your users will enjoy playing it.
The number of possible solutions depends on what you are trying to achieve.
For games that do not need fast reaction times or where the players are known to be on the same local area network, a simple server controlled game can be implemented. The server does all the game computations and the clients are just relatively dumb input/output terminals. Most MUDs (Multi-User Dungeons) and many Unix-based games use this approach (xtank, the original xpilot).
The next step beyond the dumb terminal approach is to make the games run in parallel on each machine. Either input data or game object data can be transmitted over the network. The first approach has bandwidth advantages, but severe reliability problems and the second may be difficult to manage on low-bandwidth connections and it still suffers from unreliable networks.
Dead reckoning means that instead of presenting the exact same model of the world to all players, the view is extrapolated using the last known information about the true positions of each object in the game. It works very well for some types of simulations, but some other types of games translate poorly to this scheme.
Unfortunately an ideal solution that works for all games has yet to be discovered. In fact, it's very likely that one will be found, although hopefully improvements in technology will reduce latency, improve reliability and increase bandwidth so that global games can be run in conditions pretty close to what is experienced on the local area networks that are in use now.
Even with technological improvements, it's unlikely that solutions will be found for some types of games. For instance, a martial arts fighting game that requires lightning reflexes is unlikely to work well as a playable game over latencies of more than a few hundredths of a second.
Assuming that all players share identical object code, initial data and processing model, it can be seen that you can execute the game in parallel on all machines, as long as all the input data is also shared identically. For many games, the amount of input data generated by each user is very small (say, a key press here and there), so the bandwidth-requirements are relatively small as long as the number of players is small or the data can be broadcast over the network.
The "virtual joystick method" is very easy to implement on a LAN. It's just like writing a game that runs on a single computer with multiple input devices (joysticks or keyboards, for instance) connected.
Unfortunately each player node has to have access to the same input data as all the others, so this is where latency and poor reliability become a problem. The data from player A is of course available immediately, but it will take some amount of time for that information to reach all the other players. If the packet containing that data is lost or corrupted, it has to be sent again in order for the game to proceed. All the players have to stop and wait for the lost data to be transmitted.
Also, it is based on the assumption that all computers deterministically execute the same code with the same data. This goes against the general knowledge that all programs contain bugs that can make the program behavior non-deterministic. For example, even if your code is absolutely clean, it's possible that the player computers have different processors and one of them has a hardware bug that causes a 1 bit error in some floating point operations. That single bit error can introduce chaotic behavior in the program and pretty soon the simulated world on that computer bears relatively little resemblance to the one on the others. That's why I call this phenomenom "reality fragmentation".
Reality fragmentation is easy to detect by calculating a simple checksum on each machine, but difficult to recover from, because once it happens the only thing you can do is transmit the complete game state from the majority of machines that agree to those machines that disagree about the game state. Usually those data structures are so complicated that transmitting them over the network is totally impractical.
Bugs that cause "reality fragmentation" might be totally benign and go unnoticed otherwise. In that sense, being able to detect these bugs is an advantage, because it may give you a clue to solving a much more serious problem. Many of the bugs are very hard to understand and happen under very obscure circumstances, so it may be nearly impossible to debug the game so that it is 100% reliable even if the machines are identical.
As was noted, all players have to have the same input information at the same time. As connection latency increases, it becomes impossible to share this information within the time of a single game frame (or step).
One possible way to work around this is to increase the time margins by introducing an artificial delay on each local machine. For instance, the joystick information gathered on game frame 5 might only be used three frames later on frame 8. If the game runs at 20 frames per second, this buys us a latency tolerance of 150 milliseconds. Note that this is one way latency, so assuming symmetrical latency, it would equal 300 milliseconds of roundtrip latency, which is already pretty close to what is commonly encountered on the Internet.
Exact game clock synchronization is nearly impossible (due to unsymmetrical latency and latency variance) and it is also undesirable, because it would mean that that the maximum connection latency would govern the whole game. In fact, games can be allowed to "float" their timing so that latency appears symmetrical even when it isn't. This means that the latency experienced by the players is half the maximum roundtrip latency of any connection.
The reason the "virtual input method" was discussed in this depth was that it was used in Avara. My experience is that it's initially relatively easy to implement, but becomes quite cumbersome on the internet. Players with good connections can play OK, but if your connection is unreliable or has high latency, you can just as well forget about having a good game and your connection will also ruin it for the other players. The approach has been used rather widely, so it probably appeals to programmers. My advice is not to use it unless fast real time interaction isn't absolutely critical. It works pretty well for tactical and strategy games like Command & Conquer, Warcraft or Myth.
One way to reduce user latency would be to add some form of user action prediction with the possibility of back-off when the wrong prediction is made. If you were to write a PacMan style game, it might be a good assumption that the player always turns the same way at a given intersection. A player profile (say, a neural network) could be distributed to all the players and this profile would be used to predict player actions. If the wrong prediction is taken, the game backtracks to where it went wrong and re-predicts the current situation using the corrected action data. This brings us to our next topic:
Dead reckoning is based on the ability to predict (extrapolate) game positions from well known past information. For example, if you know that a ship is traveling North at 6 km/hour, it's a pretty good bet that it will have traveled 100 meters North in one minute.
The simplest method is to transmit object positions and use several past positions to estimate where the object will be next. Two positions are needed for a rough estimate of speed and a third one can be used to obtain acceleration.
It may actually make more sense to transmit data less frequently, but add other information too. Speed and acceleration are obvious candidates, but in addition to cartesian coordinates, the orientation and rotation speed and acceleration may also prove to be very useful.
Basic high-school physics are sufficient for determining the location of an object. Quaternions are almost ideally suited for extrapolation of object orientation in 3D. In 2D, object rotation is very easy to calculate, since it only involves one variable angle.
For many games, it will also be possible to improve the predictions using information on object behavior. For example, in addition to airplane speed and acceleration, the engine power and aileron positions could be used to predict its location. As was noted in the segment about the "virtual joystick method", user behavior can also be predicted, if a wrong prediction isn't fatal to the game.
The nice thing about dead reckoning is that lost data does not need to be retransmitted. It's in fact a bad idea to retransmit non-critical data that was lost, because the situation has probably already changed and fresh data has become available.
Some types of events need to be transmitted reliably, but they aren't nearly as common as simple changes in object movement and position. One such event could be the creation of a new object (say, a missile) or the destruction of an old one. For best results, creation and destruction of objects should be announced well before the information is needed (see: latency tolerance above).
Dead reckoning is well suited for large scale simulations with a lot of users, because the relevance of data depends on the player focus. Most of the time the player is only interested in the exact locations of players who are close enough to make a difference in game events. Information on a player that is very far away could be transmitted maybe once a minute or once every few seconds: the bandwidth requirements between two distant players are nearly zero.
Also, if an object is moving very predictably or slowly, it may not be necessary to transmit that information very often. Once the difference between reality and a calculated estimate becomes large enough, new data needs to be transmitted, but as long as it is below a certain treshold, it can be assumed that the estimate used on other machines is good enough. To compensate for possible data loss, the difference shouldn't be calculated between an estimate based on only the last sent information and the current information.
If a client-server model is used with dead reckoning, the server should be reasonably "well connected", considering the number of clients. All data passes through the server, so it can easily control connection congestion between itself and the clients. It will also always have the most up to date information on all player locations, so it is in a good position to decide what data to distribute among the players.
Note that players with good connections to the server may have an advantage in the game, because the information they use for their estimates is fresher.
A peer to peer solution can also be used with dead reckoning, but it becomes much harder to control the amount of connection congestion, because data is being sent through so many connections. The advantage is that there is no server to go through, so in ideal circumstances information latency is reduced (and thus prediction quality is improved). Also, a very large scale simulation is possible as long the players don't all bunch up in a small area (then again, you have the same problem with a client-server solution too).
If an error is made in a prediction (say, the player unexpectedly changes course) the game will have to adjust the player view from the incorrect prediction to the the actual position. If this transition is made without smoothing, the object will appear to teleport from one place to another without any apparent cause. It's often better to try to interpolate between the old prediction and the updated prediction so that the object moves smoothly from the incorrect position to one that matches the current prediction.
Dead reckoning is highly suitable for many types of games. It scales really well to large numbers of players as long as the players are not in close proximity in the simulation. The more advanced your prediction methods are, the better the game will work for the player.
This section gives a quick overview of various protocols that are commonly used to create networked games.
UDP is essentially a connectionless network layer protocol with "best effort" service. The programmer can implement other protocols on top of UDP, so it's very flexible. Pure UDP can be extremely unreliable, but it also gives you relatively low latency times for the data that does actually arrive at its destination.
Best effort protocols are ideally suited for situations where data loss is acceptable (dead reckoning) or when you need to do your own error recovery.
Unfortunately congestion control can be very tricky and you have to do it all on your own with UDP. Also, UDP packets are unaffected by PPP header compression, so they require more bandwidth from modem users.
UDP may be a problem for players who are behind firewalls, because firewalls are rarely allowed to pass UDP packets freely.
TCP is a full duplex connection-based reliable transport protocol. It offers reliability at the cost of increased latency variance. Network errors cause automatic retransmissions from the TCP protocol, so at times connection latency can be several times higher than optimal.
TCP is a good solution for PPP (modem) users, because header compression is used and so bandwidth is used efficiently. TCP also does automatic congestion control, although trying to send more data than can be handled by the available bandwidth will also increase the latency, because data is held in buffers until it can be sent.
A combination of TCP and UDP could be used to overcome the problems of both protocols. Modem and firewall users could use TCP to connect to a proxy. The proxy could translate the TCP stream into UDP packets and send them to their final destinations. Assuming reasonable bandwidth and good reliability between the proxy and the user, this results in the best possible use of bandwidth and relatively low latency.
The AppleTalk equivalent of UDP is called DDP. It can only handle small packets (it doesn't do fragmentation), but it's relatively easy to broadcast DDP packets to a LAN, although this may be safe, because there's no dynamic allocation of static DDP socket numbers. (Too technical? Just ignore me here in that case.)
ADSP (Apple Data Stream Protocol) is the rough AppleTalk equivalent of TCP. It's also used to implement PPCToolbox, which also provides a user interface for locating servers on locally available networks.
Apple NetSprocket can operate over various different kinds of networks. You can even mix TCP/IP connections with AppleTalk connections. It offers both reliable and best effort service. Unfortunately it's a Macintosh-only shared library and it has been put into "maintenance mode" by Apple, so no real work is being done on it anymore. The documentation may however be a good starting point for designing an API for your own game networking library.
Obviously, the attraction of networked games is that you get to play with new people and possibly even make new friends. To achieve this goal, the game should be as accessible as possible. In other words, the game has to work on the Internet.
The game should come with a built-in way to access a global server that allows players to meet and form teams or groups for games. It's probably a pretty good idea to make the "meeting rooms" work like IRC (Internet Relay Chat).
Players will also need to find game groups or servers based on several criteria:
It's probably a good idea to have a separate area for beginners, so that they can learn the basics in relative peace without losing their self-respect in the process. Virgin Entertainment's Subspace does this by forcing all players to register with a password. Once an account reaches a certain score, it is no longer allowed to play in the beginner zones. Since the system is still free at the moment, nothing stops players from registering over and over again with new names so that they can go kill the newcomers. If new accounts would cost something, the system would probably work a lot better.
Networked games often allow several different variations of a basic theme. It could be just a matter of changing the playfield or the rules of the game might be totally changed. Some players might only have 15 minutes to spare, so they might want to join games with strict time limits, while others just want to spend time.
Geographical location is also a useful parameter for game selection. Sometimes it's fun to try to play with really distant people while at other times, you may want to team up with (or against) other people from your own region.
Due to the current state of the Internet, users will also be interested in finding out some statistics about the other players: the average ping time and connection reliability from the other players to the server. If there's a choice of different servers, ping statistics to various servers can also be invaluable.
The global registration server should also keep track of ongoing games and provide statistics. That way people can keep an eye on the games in progress and drop in an spectate on a particularly interesting match.
The main server could also provide various game extensions and utilities, such as map files, FAQs and updates to the game software. You could also look into the possibility of selling advertising space on your server.
This section provides some examples of existing networked games. Some of the information here is based on known fact and some of it is speculation. The only case where I speak from direct experience is Avara, so don't take any of the other statements here as absolute truth. I err, therefore I am.
Bungie Software's Marathon uses a very pure form of sharing input data. It requires very short latency times in order to work. It also suffers from "reality fragmentation" due to network errors (it doesn't seem to do much about recovering from transmission errors), bugs in Bungie's code and from problems in the hardware that is used to run the game.
According to an article I saw on the internet Warcraft delays user input for Internet games so that it has time to reach all the involved players. Because user actions are relatively few and far apart in games such as Warcraft, this method works quite well. Based on what I have heard, Warcraft doesn't seem to suffer much from bugs and network errors.
Avara also uses a latency-delayed input. It runs at around 16 frames per second, so the amount of data that is sent is quite high. Once there's more than a few players, packet loss starts to have an effect on the smoothness of game play, because it becomes so much more likely that data is lost on some of the connections. 2-3 player modem/PPP games seem to work well enough, but good 4 player modem games are already rather common. This goes to show that this method of networking a game doesn't scale very well to larger games.
Subspace is a relative newcomer, but it's an interesting game, because it has clearly been designed to give the best possible game quality on the worst possible connections. It uses extrapolation to extremes and the game parameters are tuned so that fast changes in course are impossible. It seems to work very well, but it seemed to me that game play had suffered somewhat from all the concessions that had been made in the design.
Descent was probably the first 3D game to use dead reckoning. That's also why it works so much better than Doom over kludges such as Kali.
Quake is now becoming a classic example of a game that wasn't properly tested in its target environment. Wild rumours about networkability for up to 64 players were on the net before it was released, but once it was released, everyone soon found out that the networking code didn't work very well except on local area networks. Vast improvements have been made since then and it seems that Quake now behaves quite well on your average Internet connection. Even so, I have heard of players getting kicked out of games because of too high connection latency.
Air Warrior and Warbirds are classic examples of dead reckoning. Since they are both flight simulators, the movements of the planes are relatively easily predictable. Because Air Warrior uses TCP connections, connection problems can occasionally block the flow of data, which results in a backlog of unsent data buffered at each end. It takes a while for this backlog to clear up, so while that's happening, the extrapolations can differ a lot from reality and objects can appear to teleport all of a sudden.
I have only tried Big Red Racing on a LAN, but it appeared to be using a very simple form of dead reckoning without any smoothing between estimated and updated positions. If you want to see objects teleport all over the place, try this game.
Bolo is probably the most exotic in terms of the networking strategy used. It uses a ring topology, but has some tweaks built in to it so that the game is playable on the internet, if you have a good connection.