Introduction

Multiplayer games often need to deal with the complex nature of the networking technology. Most notably, multiplayer games on the Internet represent a greater challenge to the developers than those games written only to run on LAN environments. One of these challenges is the delay that exists from the time at which a process sends a message over the network to the moment at which the message is received by the other process. This delay is known as network latency, and it's both a consequence of our world's physical constraints and the design of the networking technology (protocols).

Network latency, informally known as LAG, represents a serious challenge to multiplayer game developers. LAG can have disastrous effects on the player's gaming experience, making the game unplayable.

The latency can change over the course of a game session; this dynamic behavior of the network requires a solution that can detect these changes and react to minimize their impact in the game.

Client clock synchronization is a simple technique that can be used to cope with network latency. It's not a perfect solution but in some specific cases can greatly improve the experience of the users, masking the effects of network latency and making the game look pleasant and fair.

The presented document describes how to synchronize client clocks over the network. The first part of the document describes how the messages are encoded before sending them over the network. The closing part of the document describes the messages that the clients and the server exchange in order to synchronize the clocks.

Game scenario

Remember, our goal is that the game can react to the network's dynamic behavior. For this purpose we are going to suppose that we are working on a simple arcade multiplayer game in which two players compete.

The programsAE clocks are the main and only synchronization mechanism in which we are going to be relying on to achieve our goal. A clock is just a simple counter ranging from 0 up to N, with the current value of a clock representing the number of milliseconds that have elapsed since the game began.

ItAEs essential that when a game session starts, that is when the game itself begins, all the three clocks (two clients and server) be synchronized and have their initial value set to zero. The algorithm described later on this article will let us do this.

Once the clocks are synchronized we can use them for at least three very important functions:
[nbsp]

• The server can report to the clients key state changes in the game environment.
  
• The server can use the clock along with the clients' message timestamps to arbitrate conflicts.
  
• Clients can use the clocks and incoming messages' timestamps to detect network latency changes. When the client notices a change in the latency, it will scale the speed of the local Avatar to minimize the effect of the latency.
  

[nbsp]
Here is a C++ class for the game's virtual clock:

class VClock {
DWORD mRealStart;
bool mStarted;
public:
VClock() : mRealStart(0) {} ;
bool Started() const { return mStarted ; }
void Start( DWORD time_delta )
{
mRealStart=GetTickCount()-time_delta;
mStarted=true;
}
DWORD getTime( ) const
{
assert(mStarted) ;
return GetTickCount() - mRealStart;
}
};

The function [font=courier new,courier,monospace]GetTickCount[/font] retrieves the number of milliseconds that have elapsed since the computer was turned on. The value returned is 8 bytes long and the biggest value can be [font=courier new,courier,monospace]49.7[/font] days, which is more than enough for a game session! Otherwise the player is in grave danger and needs to get help.

The real clock is the value returned from the [font=courier new,courier,monospace]GetTickCount[/font]. The virtual clock is the value of [font=courier new,courier,monospace]GetTickCount[/font] minus the instant in which the server signaled the start of a game session.

Application Messages

The game client communicates with the server by sending messages over the network, the transport protocol used by the game is TCP. A message is a piece of information that the client/server wants to communicate, e.g. one player has pressed the mouseAEs left button.

Game Message Layout

The field ID is two bytes long, it's an integer used to identify the different messages.

The values of this field are declared in the program as an enumerative type:

typedef enum commands
{
cmdLOGIN = 0x1U,
cmdERROR = 0x2U,
cmdLOGIN_OK = 0x3U,
cmdMOUSE_LEFT_BUTTON_DOWN = 0x5U,
cmdREADY = 0x9U,
cmdBEGIN_GAME = 0x10U,
cmdGAME_END = 0x11U,
cmdSYNCH_REQUEST = 0x12U,
cmdSYNCH_REPLY = 0x13U,
cmdPRIMARY_CLIENT = 0x14U,
cmdSECONDARY_CLIENT = 0x15U,
cmdSYNCH_DONE = 0x16U,
cmdSYNCH_WAIT = 0x17U
} protoCommands;

The field SIZE is two bytes and specifies the size of the message measured in bytes. The smallest message has a size of 4 bytes.

The field DATA has variable length. This field is used to communicate additional information, e.g. the field data of the message [font=courier new,courier,monospace]cmdMOUSE_LEFT_BUTTON_DOWN[/font] has the mouse position of the remote user.

The fields are encoded/decoded using the standard socket functions htons, ntohs, htonl and ntohl. These functions convert a 16-bit / 32-bit number from the host byte order (little-endian on Intel processors) to the network byte order (big endian) as well as the opposite.

The field TIMESTAMP is 4 bytes, please note that this field is only used once the clocks have been synchronized. When sending messages, the clients always store their virtual clock value here.

Clock Synchronization Algorithm

In order to synchronize the client clocks the programs need to estimate the network latency: the amount of time it takes a message to travel from one client program to the other one. Therefore the clock synchronization process has two steps: 1) compute network latency and 2) signal clock synchronization.

The diagram below shows the messages that are exchanged to accomplish the clock Synchronization:

[nbsp]

1. Client #1 establishes a TCP connection to the Game Server and sends the message [font=courier new,courier,monospace]cmdLOGIN[/font]. This message includes the ID of the game that the client wants to join to.
   
2. Upon receipt of the message [font=courier new,courier,monospace]cmdLOGIN[/font], the server checks if the requested game already has a primary client associated to it. If there is no primary player the server assigns this role to the client and sends the message [font=courier new,courier,monospace]cmdPRIMARY_CLIENT[/font].
   
3. Client #1 receives the [font=courier new,courier,monospace]cmdPRIMARY_CLIENT[/font] message. The client sends the [font=courier new,courier,monospace]cmdSYNCH_REQUEST[/font] message to the server and records the time at which the message was sent.
   
4. The Server receives the [font=courier new,courier,monospace]cmdSYNCH_REQUEST[/font] message, but as the other player has not joined to the game yet, the server sends back to Client #1 the message [font=courier new,courier,monospace]cmdSYNCH_WAIT[/font]. This message tells to the client that it should try again later.
   
5. Client #1 sends the [font=courier new,courier,monospace]cmdSYNCH_REQUEST[/font] message to the server and records the time at which the message was sent.
   
6. Item 4.
   
7. Client #2 establishes a TCP connection to the Game Server and sends the message [font=courier new,courier,monospace]cmdLOGIN[/font]. This message includes the ID of the game that the client wants to join to.
   
8. Upon receipt of the message [font=courier new,courier,monospace]cmdLOGIN[/font], the server checks if the requested game already has a primary client associated. The primary player already joined to the game, so the server assigns the secondary role to this new client and sends to it the message [font=courier new,courier,monospace]cmdSECONDARY_CLIENT[/font]
   
9. Client #1 sends the [font=courier new,courier,monospace]cmdSYNCH_REQUEST[/font] message to the server and records the time at which the message was sent.
   
10. The Server forwards to the Client #2 the message [font=courier new,courier,monospace]cmdSYNCH_REQUEST[/font]
    
11. Client #2 receives the message [font=courier new,courier,monospace]cmdSYNCH_REQUEST[/font] and sends the message [font=courier new,courier,monospace]cmdSYNCH_REPLY[/font] to the server.
    
12. Client #1 receives the message [font=courier new,courier,monospace]cmdSYNCH_REPLY[/font] and records the time at which it has been received.
    
    [The programs repeat the steps 9,10,11 and 12 several times. The [font=courier new,courier,monospace]cmdSYNCH_REQUEST[/font] messages are spaced by 20 milliseconds]
    [nbsp]
    
13. At this point the primary client has gathered the data needed to estimate the latency, so now the client computes the latency, sets its clock to 0 and sends the message [font=courier new,courier,monospace]cmdSYNCH_DONE[/font]. This message includes the estimate of the latency. The primary client uses the following statistics to estimate the latency:
    
    A(n) = time at which the Nth [font=courier new,courier,monospace]cmdSYNCH_REPLY[/font] was received
    B(n) = time at which the Nth [font=courier new,courier,monospace]cmdSYNCH_REQUEST[/font] was sent
    X(n) = A(n) - B(n) / 2
    
    a) Sort the X(n) from smallest latency to largest and choose the median value.
    
    b) Compute the standard-deviation s? = ( ?x? - (?x)?/ n ) / n - 1
    
    c) Discard the X(n) values that are not in the interval: I : [ mid-point - s, mid-point + s ]
    
    d) Compute the average ?x / n from the interval I, this value is going to be used as latency.
    
14. The Server forwards the message [font=courier new,courier,monospace]cmdSYNCH_DONE[/font] to the secondary client.
    
15. Client #2 receives the message [font=courier new,courier,monospace]cmdSYNCH_DONE[/font] and sets its clock to 0 + latency
    
16. The Server sends the [font=courier new,courier,monospace]cmdLOGIN_OK[/font] message to both clients.
    

[nbsp]

Epilogue

I want to thank Stuart Rosen, this article is mainly based on his ideas and the work we did together. I also want to thank Cristobal Zingarelli, a talented programmer and a friend who worked with us.

Please feel to contact me to share any insights, thoughts or suggestions about this article.

You can reach me at gulfas at gmail.com

Pablo aka Morgolock Marquez

References

Alex Spurling 2004 - QoS Issues for Multiplayer Gaming

Fritsch, Ritter and Schiller - The Effect of Latency and Network Limitations on MMORPGs