Dev:Network Games Related Work

Terminology

• DIA = Distributed Interactive Applications
  • used by among others Delaney - Presence 2007
  • Includes any of the following:
    • DIS = Distributed Interactive Simulations
    • NVE = Networked Virtual Environment
    • DIM = Distributed Interactive Media
    • NIE = Networked Interactive Environment
    • DVE = Distributed Virtual Environment
    • CVE = Collaborative Virtual Environment
    • DSE = Distributed Synthetic Environment
    • SVE = Shared Virtual Environment
    • CSCW = Computer Supported Cooperative Work

Consistency is the degree to which users share the same view of the application state Delaney - Presence 2007. It includes:

• Synchronization: time of all events relative to other events are the same across the DIA
• Causality: cause/effect ordering is maintained
• Concurrency: simultaneous execution of events by different users on the same entity is managed correctly

Responsiveness is the time taken for the system to register and respond to a user event. Delaney - Presence 2007

Fidelity is the degree to which the virtual representations are similar to their real-world representations. Delaney - Presence 2007 & IEEE95

ISSUES IN SUPPORTING DIAs

Consistency vs Responsiveness

With 0 network latency and infinite bandwidth, a DIA could remain completely consistent and yet be highly responsive (i.e. change state rapidly). In the presence of network latency, however, the system will require time to reach a new consistent state. Thus when a state change is required, the system can either delay its response in order to first reach a consistent state or it can process the change without guaranteeing complete consistency across the DIA.
Fidelity is sacrificed in either case since fidelity represents how closely the simulation matches its real-world representation. Clearly inconsistencies harm fidelity as they lead to less accurate simulations. Decreased responsiveness also decreases fidelity since real events occur instantaneously. The importance of each aspect of fidelity is dependent upon the type of DIA. For instance, a fast-paced first-person shooter game must remain highly responsive but may tolerate certain types of inconsistencies. A shared whiteboard application, on the other hand, can tolerate some delay but should be consistent for all users.

It's important to notice that the fundamental problem to supporting DIAs is the presence of network latency. Certain sources have found that for many DIAs, the variation in latency or "jitter", has the greatest impact on performance Delaney - Presence 2007. In the face of latency, DIAs employ a wide range of Consistency Management Techniques (AKA Latency Hiding Techniques) in order to maintain fidelity by balancing consistency with responsiveness. How best to manage this tradeoff depends on the requirements of the DIA.

Scalability

Scaling a DIA to support a larger number of users increases the computation that must be done by the nodes and increases the network bandwidth needed to communicate the state between the nodes. While adding more nodes can usually alleviate the computational burden it increases the network bandwidth required as more endpoints in the network will need to share data. The exact architecture employed by each DIA will determine how the bandwidth requirements will increase with the number of users. To reduce the network bandwidth, DIAs employ a variety of Information Management Techniques.

RELATED WORK

Consistency Management Techniques

• Lockstep Synchronization
  • All nodes must acknowledged that they have completed their computation before they can advance their clocks.
  • Ensures consistency but is not real-time
• Imposed Global Consistency
  • Nodes must delay execution for a certain period to accommodate for network latency
  • Examples include Bucket Synchronization
• Delayed Global Consistency
  • Users will perceive the same consistent state but potentially at different times Delaney - Presence 2007
  • Useful in DIAs such as shared whiteboards.
• Time Warp
  • Execute messages as soon as they arrive but rollback when a message is received with an earlier time-stamp
• Predictive Time Management
  • Predict the occurrence of future events such as object collisions
  • Send out event and predicted time of occurrence before they occur
• Concurrency
  • A fast way of resolving conflict of ownership for entities
  • Rather than using a traditional lock, each entity has a key that provides write permission
  • The key remains with the node until another node requires it and a node can preemptively fetch a key when it predicts that it will need it

Information Management Techniques

• Dead Reckoning
  • A Prediction Technique allows a node to predict the state changes for an object in the absence of new state updates
  • When new state is received that contradicts the predicted state, a Convergence Technique can be used to smoothly converge to the correct state
  • Donnybrook's doppelganger approach is essentially a form of dead reckoning Bharambe - SIGCOMM 2008
  • Improves responsiveness at the cost of temporary inconsistencies
• Data Compression
  • Internal Compression: uses an encoding that compresses data within a single packet and is not dependent on information sent in previous packets
  • External Compression: uses an encoding across packets (e.g. delta encoding)
  • Techniques can be "lossy" or "lossless"
  • Can increase latency
• Packet Bundling/Aggregation
  • Aggregate as much data as possible into a packet to reduce overhead of packet headers
  • Can increase latency as the sending of data may be delayed so that it can be aggregated
• Relevance Filtering
  • Also called Interest Management Techniques, these techniques attempt to reduce bandwidth by exploiting the locality of interest of users
  • These techniques typically include a method for expressing interest and for performing filtering based on these interests
  • Area-of-interest filtering using the Aura-nimbus model:
    • Medium = communication type (e.g. audio, video, text)
    • Aura = object and subspace of medium that it can interact with
    • Focus = sphere of influence within aura
    • Nimbus = sphere of interest within aura
  • Extrinsic vs Intrinsic
    • Extrinsic: filters packets using properties of packet header (e.g. multicast address)
    • Intrinsic: filters using application data in packet payload

Communication Architectures

• Network services
  • Multicast
    • Core Based Multicast
      • DCM: Distributed Core Multicast
        • This paper assumes two level network hierarchy with a backbone connecting smaller areas. It focuses on supporting many (millions) of multicast groups where each group has only a few receivers. They cite distributed simulations as a motivating example. The way they accomplish this is that for each multicast group each area has a Distributed Core Router (DCR). The DCR for a multicast group is chosen with a hash function so all hosts in an area know which DCR to use for a given multicast group. All multicast traffic in an area goes through the DCR and the DCR sends traffic to the DCR in other areas if the other areas have receivers for the group.
      • Evaluation of Shared Multicast Trees with Multiple Active Cores
        • This paper explores two approaches to using multiple cores. In one approach, called "Senders-To-All", a sender sends a message to all cores for the multicast group and members only join nearest core. In the second approach, "Members-To-All", a sender only sends to one of the cores and the members must join all the cores. They evaluate the two approaches by varying the group size from and the number of cores and evaluating the delay, cost, and traffic concentration metrics. They also evaluate cost and delay with different core placement strategies. Their results show both approaches have slightly lower average delays between sender and group member due to the multiple cores. Some of the traffic concentration with single-core tree is alleviated and costs are comparable to shortest-path trees.
      • Border Gateway Multicast Protocol (BGMP)?
      • Protocol Independent Multicast - Spare Mode (PIM-SM)
      • Core Based Trees (CBT)?
      • Ordered-Core Based Trees (OCBT)?
    • Other multicast
      • ATM Kantawala 1996
  • QoS
    • Resource reservation
  • Active Services
    • Interest filtering
      • Zabele - DANCE 2002
• Protocols
  • Multicast
    • Lots of overlay multicast protocols... fill in later
  • QoS
    • RSVP
    • RTP/RTCP
  • Active Services

Software Architectures

Software architecture is driven by network services and the requirements of the DIA.
It includes:

• Client/Server, P2P, hybrid
• Information Management Techniques used
• Consistency Maintenance Techniques used

• Software Frameworks:
  • Atlas Lee - Presence 2007
  • Bamboo Watsen - Image 1998

Some Thoughts

Many of the issues that arise in supporting distributed virtual worlds are problems that apply to distributed systems generally. You can think of a virtual world as simply a distributed database with real-time requirements. The most fundamental issue here is that when data is distributed across a network, the presence of network latency makes total consistency impossible. As a result, there is a tradeoff between the level of consistency and the degree of responsiveness. Different applications have differing notions of fidelity and these determine what type of consistency the system should guarantee and how responsive it should be. Given this tradeoff, there are variety of consistency management techniques used to guarantee different levels of consistency. Clearly the most important thing the network can do is ensure minimal network latency. Beyond this, there are a number of network services that can make these varying techniques more efficient.

Ways in which the network can support DIAs

• Provide QoS
  • Consistent and low latency allows DIAs to improves fidelity by allowing them to by highly responsive but at the same time be tightly synchronous, thus offering higher consistency
  • Bandwidths must be provisioned to provide consistent performance/fidelity and to ensure low latency.
• Aid in Information Management
  • Network can perform both extrinsic filtering (using multicast) and use intrinsic filtering schemes such as those employed by SANDS Zabele - DANCE 2002
  • Allowing the network to play a more active role in interest management helps free up the resources of the nodes
• Aid in Consistency Management
  • Reliable multicast at the network layer also helps to reduce latency allowing DIAs to be more tightly synchronous
  • Network could help in establishing a global clock limiting the need for logical clock algorithms
  • Network could assist in synchronization
    • Ideas similar to Harry Thorvaldson's work
    • Again, the usefulness is that it could lower latency and potentially shift some of the burden of synchronization into the network

What have we done?

• Provided QoS
  • Our comtree scheme provisions links and isolates traffic
• Aid in information management
  • Extrinsic filtering in the network by supporting highly dynamic multicast groups

Colyseus used a single-copy consistency model where all writes are synchronized through a single copy. Replicas of the data allow low-latency reads but the data will be weakly consistent with the primary copy. Colyseus supported external compression using a delta-encoding scheme. They aggregated state updates into packets but did NOT use packet aggregation. Our modifications to Colyseus used a simple region-based Area-of-Interest management scheme where we were only concerned with the visual aura. Our filtering was done in the network extrinsically using multicast groups.

Classification

Related Work

Reference	Consistency Management	Information Management	Communication Architecture	Software Architecture
Assiotis - Netgames 2006	Cell 2	Cell 3
Donnybrook - Bharambe - SIGCOMM 2008	One copy consistency model	Per-object multicast, low fidelity dopplegangers	Overlay multicast	Decentralized