Multiplayer Game Synchronization
Lecturer: Dr.
Queen Mary University of London
Copyright By PowCoder代写 加微信 powcoder
Introduction
• Massive Mulitplayer Online Games (MMOGs) produce billions of pounds of revenue and have several interesting design challenges
• Can be considered a distributed system
– The state of the game should be consistent to all users
– Updates to the state need to be communicated to all users in a robust fashion
www.qmul.ac.uk
/QMUL @QMUL
MMOG Design Principles
• There are several concepts specifically related to MMOGs namely:
– Object Types
– Player Interactions
– Object Replication
– Latency Tolerance
– Bucket Synchronization and Frame Rate
– Bandwidth Requirements
– Interest Management
– Consistency Control
www.qmul.ac.uk
/QMUL @QMUL
Object Types
– Landscape or terrain usually designed offline and never changed during the game
• Immutable Objects
• Characters or Avatars
– Controlled by the player using an input device and can interact with some other object types • Mutable Objects
– Examples include food and tools. Players can interact with these objects • Non player characters (NPCs)
– Similar to player characters but controlled by an AI
• Each of these objects need to be handled differently
• For example information on Immutable objects does not need to be sent as it never changes
www.qmul.ac.uk
/QMUL @QMUL
Player Interactions
• Player updates
– Updates that only affect the player such as position updates
• Player object interactions
– A player interacting with a mutable object such as food is an example of this
• Player player interactions
– A player interacting with another player such as waving to them (and the
various less friendly alternatives)
• Again these need to be handled differently
• Do we need to send information on a player update if it is outside the Area of Interest (AOI) (more on this later) of another player?
www.qmul.ac.uk
/QMUL @QMUL
Object Replication
• When a player joins an MMOG they receive an instance of a game world
• This instance is usually a secondary copy of the game world which contains objects relevant to the player
• The primary copy is a definitive version of the game world which is sometimes held on a special game server
• When players update objects the update must be sent to the primary copy which will authorise the update (it may not do this if it believes the update is related to a cheat for example)
• This update is then sent to all secondary copies of the game world
• Similar to publish-subscribe systems (RSS, MQTT(IoT), JMS etc)
www.qmul.ac.uk
/QMUL @QMUL
Latency Tolerances
• There is a point where network delays or latency make the game frustrating or impossible to play but this varies significantly depending on the game type
• This can dramatically affect the architecture
https://web.cs.wpi.edu/~claypool/papers/ precision-deadline/final.pdf
www.qmul.ac.uk
/QMUL @QMUL
Bucket Synchronization and Frame Rate
• Bucket Synchronization is a techniques for handling latency in MMOGs
• Each client will have a different latency and the primary copy of a game state will receive multiple updates concurrently from different clients
• Many games deliberately lag behind the execution of events to improve the fairness despite latency issues
• This is similar to Nagle’s algorithm in IP networking
www.qmul.ac.uk
/QMUL @QMUL
Bucket Synchronization and Frame Rate (cont)
• Games implement a discrete event loop (also known as a frame) in which all action which have occurred since the last loop are received buffered and executed
• Updates are sent at the end of the loop
• NPCs also execute a think function which determines their actions during
• This loop is executed 10 to 20 times a second which is known as the frame rate
• Note that this is different to the display frame rate
www.qmul.ac.uk
/QMUL @QMUL
Bucket Synchronization and Frame Rate
https://www.researchgate.net/figure/The-Locked-Bucket-Synchronization-algorithm_fig1_29461970
www.qmul.ac.uk
/QMUL @QMUL
Bandwidth Requirements
• Bandwidth requirements are based upon the number of active users, message size and update rate
• Games must also accommodate bursts in traffic due to changes in environments or activity
• This is typically dealt with via over provision
www.qmul.ac.uk
/QMUL @QMUL
Bandwidth Requirements
www.qmul.ac.uk
/QMUL @QMUL
Interest Management
• Important mechanism used in games for scalability reasons
• Limits the players movement and vision capabilities
• Thus, players can only move a small distance in the game in a given time interval
• This allows data access which shows spatial and temporal locality (This is very useful when it comes to caching data)
• Players only receive the game state that is relevant to them based upon their position and vision which improve scalability
www.qmul.ac.uk
/QMUL @QMUL
Interest Management (cont)
• The area around a player in which they can perceive game objects is known as the Area of Interest (AoI)
• One common mechanism for managing AoI is zoning where the game world is divided into smaller sections or zones
• In the most simple version of this the player can interact with all game objects in the zone
• In more complicated version players can interact with multiple zones to allow a continuous game world
www.qmul.ac.uk
/QMUL @QMUL
Interest Management (cont)
https://dl.acm.org/doi/10.1145/2522968.2522977
www.qmul.ac.uk
/QMUL @QMUL
Interest Management (cont)
• Also possible to use the concept of mini-world which are zones which have a free format and portals connecting them
• This does not offer the illusion of a continuous world
• Determiningtherightsizeofazoneischallenging
• Trade-off between network workload and performance
www.qmul.ac.uk
/QMUL @QMUL
Interest Management (cont)
• There are some limitations to interest management as flocking in MMoGs is common
• Flocking is movement of players to one specific area in the game world
• Possible to reduce the problems associated with flocking via dynamic
• Limitations to this as two many dynamic zones can reduce performance and there is also the possibility of inter zone communication becoming a bottleneck
www.qmul.ac.uk
/QMUL @QMUL
Consistency Control
• Like other distributed systems concurrent and possibly conflicting updates are possible
• Inconsistency can be caused by latency or loss of updates
• Games tend to use UDP for performance reasons which can
exacerbate this
• TCP or commit protocols can be used to try and improve consistency
www.qmul.ac.uk
/QMUL @QMUL
Consistency Definitions
• Several types of consistency for games have been defined
– Very strong consistency is defined as every interaction with a game object being treated as a transaction
– Eventual consistency is defined as a game in which all copies of game objects would reach the same value if updates stopped
• Brewer’s CAP theorem suggest that only two out of three properties of consistency, availability, and handling network partitions can be achieved in a distributed system.
www.qmul.ac.uk
/QMUL @QMUL
Consistency Control
• MMoGs are slightly different as they tend to aim for inconsistency resolution rather than inconsistency prevention as interactivity is a key component
• Different levels of consistency, however, can be performed on different mechanisms
• For example, strong consistency may be used in transactions involving virtual currency as this frequently has real world value
www.qmul.ac.uk
/QMUL @QMUL
Stale Views
• When a secondary copy of a game state has sent an update to the primary copy but has not yet received an update from the primary the view can be defined as stale
• Invalid update requests are therefore possible
• In 50% of cases this inconsistency lasts less than a second
• There are several techniques which games use to hide inconsistency and message loss
www.qmul.ac.uk
/QMUL @QMUL
Consistency Techniques
• Consistency Techniques broadly fall into two categories namely:
– Predictive Contract Mechanism (PCMs) • Dead Reckoning
• Smooth Corrections
– Multiresolution Simulation
www.qmul.ac.uk
/QMUL @QMUL
Dead Reckoning
• Dead reckoning is based upon the assumption that game objects rarely change speed or direction
• The previous movement is therefore an accurate predictor of the current movement
• An extrapolation algorithm can be used to estimate the position of a game object and reduce the number of updates to the game object
• Updates are only transmitted when a error threshold is reached
• It is possible to implement dead reckoning with lag awareness
www.qmul.ac.uk
/QMUL @QMUL
Smooth Corrections
• When a dead reckoning update arrives which is significantly different from the current predicted location the simplest solution is move the play to the new location
• This result in jerky animation and can be visually jarring for the player
• Convergence techniques can be used to correct these errors in a smooth
less surprising manner
• By estimating where the player will be in the future it can be moved progressively to that location
www.qmul.ac.uk
/QMUL @QMUL
Smooth Corrections
https://link.springer.com/article/10.1007/s00530-012-0271-3
www.qmul.ac.uk
/QMUL @QMUL
Measuring Consistency
• Can be simply calculated as the difference between the state at each client and the virtual perfect site that receives and executes all interactions with no delay and in the right order
• Also possible to evaluate consistency based upon three metrics namely
– Responsiveness: The time the system takes to respond to an event
– Precision: The degree of accuracy required to complete an action successfully
– Fairness: The degree of difference among all players’ gaming environments
• Could also consider inconsistency, interactivity, and discovery latency
www.qmul.ac.uk
/QMUL @QMUL
MMOG Architecture
• There are a number of different architectures which can be used to implement MMOG namely
– Client Server
– Multi Server (MS) – Peer-to-peer (P2P)
www.qmul.ac.uk
/QMUL @QMUL
MMOG Architecture
https://dl.acm.org/doi/10.1145/2522968.2522977
www.qmul.ac.uk
/QMUL @QMUL
Client Server Architecture
• In this architecture the server holds the master copies of all mutable objects and avatars and maintains global knowledge of the game world
• Clients connect to the server and receive necessary information about the game world
• Updates and interactions are sent to the server for execution and conflict resolution
• Once the updates have been executed the server forwards the updates to players who are affected
www.qmul.ac.uk
/QMUL @QMUL
Client Server Architecture Advantages/Disadvantages
• This system tends to get the best performance for low numbers of players as no inter server communication is required
• Performance tends to decrease as the number of players increases as even the best provisioned server can only support a limited number of players
• It is also a single point of failure and fault tolerance can be an issue
• Multiple servers can be added to improve performance
www.qmul.ac.uk
/QMUL @QMUL
Multi Server Architecture
• This is the approach normally taken by large game companies
• Server farms are maintained to provide services to clients
• There are two main categories of this architecture namely: – Shards
www.qmul.ac.uk
/QMUL @QMUL
Multi Server Architecture Shards
• A shard is defined as a complete instances of the game world and several of these exist at the same time
• Each shard is maintained by a separate server
• Each server is responsible for a different set of clients and follow a traditional
client server architecture
• As each server contains a complete copy of the game world there is no need for communication between the servers
• Games are usually designed to make it difficult to move between shards (E.g. £17 to transfer character between zones in WoW). Why?
• Users are typically assigned to servers based on their geographical location. Why?
www.qmul.ac.uk
/QMUL @QMUL
Multi Server Architecture Regions
• With this architecture only a single game world exists but the game world is divided into several regions
• Each region is maintained by a server
• Players can only interact with players who are in the same region
• Players can move between regions but this requires some mechanism to move the character between servers in a transparent fashion
• For example as a player nears a border necessary information can be sent to the server handling that region so that the player can easily cross the border
• It is also possible to use portals or gateways so that transparent movement between regions does not need to be implemented
• This approach is useful when implementing interest management
www.qmul.ac.uk
/QMUL @QMUL
Multi Server Architecture Shards vs Regions
• Shards allow players to communicate with any player in the world without additional network traffic (Regions would require the message to be forwarded to another server if the player was in a different region)
• Regions allow a greater density of players in a particular region
• Both approaches can be used in tandem. E.g. It is possible to have shards of regions but this is only necessary in very large games
www.qmul.ac.uk
/QMUL @QMUL
Multi Server Architecture Advantages/Disadvantages
• Allows a greater number of players to play the game without performance problems
• Increased complexity. If regions are used the game needs to handle functionality associated with global player interactions (Assuming this is a function of the game) as well as the transition of players between regions
• Using regions allows for a greater number of players to participate in the same game world assuming additional functionality can be implemented
• Fault tolerance is also improved as the loss of a shard will only affect some of the players
• Very expensive. Acquiring servers for 30,000 simultaneous players can cost approximately $800,000 and the bandwidth costs can reach hundreds of thousands of dollars
www.qmul.ac.uk
/QMUL @QMUL
Peer to Peer (P2P) Architecture
• In this architecture each client also acts as a server
• Each node can become responsible for maintaining a master copy of some game objects and disseminating updates to other players
• Asmorenodesjointhegamemoreresources become available for use by the distributed game system
www.qmul.ac.uk
/QMUL @QMUL
Peer to Peer (P2P) Architecture Advantages
• Improved scalability. Each player who joins the game adds more resources to the game
• Reduced cost. As the clients are maintaining the game world there is no increased costs relative to the scale of the game
• Improved failure tolerance. The failure of an individual node should not greatly affect other nodes assuming mechanisms for handling the failure exist
• Low latencies can be achieved by making direct connections between peers properly as updates can be sent to interested peers directly rather than being relayed through a server
www.qmul.ac.uk
/QMUL @QMUL
Peer to Peer (P2P) Architecture Disadvantages
• Security. Cheating is much easier in a P2P architecture
• The systems are much more difficult to manage as the game state is distributed among the peers
• Consistency is a problem as conflicting updates which are executed at different sites may result in an inconsistency
• The complexity and coordination overhead will tend to increase as more clients join the game
www.qmul.ac.uk
/QMUL @QMUL
Architecture comparison
Architecture
Advantages
Disadvantages
Client-Server
+ Simplicity
+ Easy Management + Consistency Control
— Scalability
— Fault tolerance – Cost
Multi-Server
+ Scalability
+ Fault Tolerance
– Isolation of players – Complexity
Peer-to-Peer
++ Scalability
+ Fault Tolerance
— Complexity
– Consistency Control – Cheating
www.qmul.ac.uk
/QMUL @QMUL
Hybrid Architecture Techniques
• There are a number of hybrid architectures which can utilise components of the different architectures discussed namely
– Cooperative Message Dissemination – State Distribution
– Basic Server Control
www.qmul.ac.uk
/QMUL @QMUL
Cooperative Message Dissemination
• In this technique the game state is maintained by one or multiple servers and updates are disseminated using a P2P approach
• Players send their updates directly to the server
• A P2P multicast mechanism is used to update the players
• This reduces the bandwidth requirements of the game
www.qmul.ac.uk
/QMUL @QMUL
State Distribution
• In this technique the game state is distributed among the peers
• Clients hold the primary copies of objects
• All communication between peers is managed by servers
• Servers are also responsible for authenticating players and determining which players are logged in
• Scalability is achieved by distributing the cost of state execution among the clients
www.qmul.ac.uk
/QMUL @QMUL
Basic Server Control
• Message dissemination and state distribution are handled in a P2P manner
• Servers perform additional functionality such as maintaining sensitive data such as client logins, payment information, and players’ progress and state.
• Servers also perform functions such as authentication and admissions control
• Servers can also coordinate some types of interactions between the peers such as those that require the highest consistency.
• P2P can also be used to distribute updates to game clients
www.qmul.ac.uk
/QMUL @QMUL
MMOG Communication
• Maintaining a consistent game state with a reasonable Quality of Experience (QoE) for all users requires significant communication between all the nodes in the distributed system
• There are a number of mechanism which can be used to manage this communication namely:
– Direct Communication
– Delta Coding
– Selective Dissemination
– Multicast Trees
– Message Aggregation
– NAT and Firewall
www.qmul.ac.uk
/QMUL @QMUL
Direct Communication
• The primary copy sends all object updates to the nodes that have subscribed to the associated object (Similar to RSS feed)
• Low latency and quite simple to implement
• Can result in high bandwidth requirements
• In P2P upload capacity can become a bottleneck due to the asymmetry of most broadband connections
www.qmul.ac.uk
/QMUL @QMUL
Delta Coding
• The message size is reduced by only sending the difference (delta) in update messages
• For instance by only sending attributes of objects which have changed since the last update the message size can be reduced
• Games frequently use UDP for performance reasons which can result in lost packets
• Complete updates can be sent periodically to correct errors in the game state
www.qmul.ac.uk
/QMUL @QMUL
Selective Dissemination
• Thistechniquesdropssomeupdateswhenthegame is overloaded to maintain interactivity
• Essentially clients attempt to avoid sending events which have already become obsolete
• Forexample,apositionupdatebecomesobsolete once a new move command has been issued
www.qmul.ac.uk
/QMUL @QMUL
Multicast Trees
• Frequently used in P2P architectures to reduce communication overhead
• Most commonly, a logical multicast tree is maintained and a single message is sent to the root of the tree which will forward it on to its children
• This lowers the bandwidth requirements but increases latency as the number of hops required to reach the final destination increases
• This, however, can be minimised by attempting to maintain geographical locality when constructing logical multicast trees
www.qmul.ac.uk
/QMUL @QMUL
Message Aggregation
• Multiple messages can be merged together to form a single message to reduce bandwidth requirements
• This can be particularly useful at the roots of logical multicast trees
• Artificial delay can be added before sending messages in order to allow for more messages to arrive and be aggregated together
www.qmul.ac.uk
/QMUL @QMUL
NAT and Firewall
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com