TL;DR
This paper introduces Extrapolated Parity Packets (EPPs) to improve the accuracy of dead reckoning in online games, especially over lossy networks. By intelligently sending parity packets that can also act as predictions, EPPs significantly reduce avatar prediction errors compared to traditional methods.
What Problem Does This Paper Address?
Online multiplayer games, particularly fast-paced ones like First-Person Shooters (FPS), rely on players' computers predicting the positions of other players' avatars to create a smooth experience. This prediction technique, called "dead reckoning" (DR), uses past position updates. However, real-world networks are imperfect, introducing packet loss and delays. These network issues can cause DR predictions to diverge from actual avatar positions, leading to jarring visual glitches like "ghosting" or avatars appearing in incorrect locations. Existing solutions like retransmitting lost packets (ARQ) are too slow for the real-time demands of games, and while Forward Error Correction (FEC) can help, it's not specifically tailored for the unique characteristics of game updates. This paper aims to bridge this gap by proposing a novel packet type and scheduling strategy to enhance DR accuracy in the face of network impairments.
Methods
The core innovation is the Extrapolated Parity Packet (EPP). EPPs are designed to be application-aware, meaning they understand the nature of game updates. They are constructed using a DR mechanism at the sender. The key idea is that an EPP, generated from a window of past updates, can serve two purposes:
- Parity Recovery: If a single past update is lost, the EPP can be used to perfectly reconstruct that lost update.
- Prediction: If multiple updates are lost, the EPP acts as a direct prediction of the avatar's future position, mitigating the impact of those losses.
The paper details three specific EPP construction methods, each tailored to a different avatar motion model:
- Extrapolated Displacement (xd): For simple random displacement, the EPP is just the latest known position.
- Extrapolated Velocity (xv): For models with velocity, the EPP is calculated using a formula that predicts the position based on current and past velocities.
- Extrapolated Acceleration (xa): For more complex acceleration models, the EPP uses a more sophisticated prediction formula involving multiple past states.
The paper also addresses the scheduling and packetization of EPPs. EPPs are sent using any available extra bandwidth (beyond that used by regular game updates). Two packetization strategies are discussed:
- Piggyback Packetization: The EPP is sent within the same packet as a regular game update. This saves on header overhead but means losing the packet loses both the update and the EPP.
- Independent Packetization: The EPP is sent as its own packet. This incurs an extra header cost but provides resilience against losing the primary update packet.
The authors propose a token bucket mechanism to manage the transmission of EPPs, ensuring they are sent efficiently to maximize bandwidth utilization while minimizing prediction error.
Datasets
The paper uses two types of data for evaluation:
- Theoretical Models: The authors define and use three avatar motion models (random displacement, random velocity, and random acceleration) to derive theoretical predictions and errors.
- Real Game Traces: They collected 10 minutes of game update data from two popular FPS games: bzflag and sauerbraten. This data was captured from a low-delay, low-loss LAN environment.
Key Insights and Ideas
- EPPs are more than just parity: The dual role of EPPs as both error correction and direct prediction is a crucial insight. This allows them to handle scenarios beyond single packet loss, which is a significant advantage over traditional FEC.
- Motion model matters: The accuracy of DR and the effectiveness of EPPs are highly dependent on the underlying avatar motion model. More complex models (like acceleration) benefit more from sophisticated EPPs, but also have higher baseline errors.
- Trade-off in packetization: There's a clear trade-off between piggyback and independent packetization. Piggybacking is more bandwidth-efficient but riskier if the packet is lost. Independent packetization is more robust but uses more bandwidth due to extra headers. The optimal choice depends on network conditions and the specific motion model.
- Bandwidth is key: Increasing available bandwidth significantly reduces prediction error, especially for more complex motion models. However, the gains tend to plateau, suggesting diminishing returns beyond a certain point.
Key Results
- Significant error reduction: EPPs consistently outperform non-EPP schemes. Theoretical results show error reductions of up to 8.2% for rd, 24.5% for rv, and 54.6% for xa.
- Independent packetization often better: For the parameters tested, independent packetization generally yielded lower prediction errors than piggyback packetization.
- Motion model rv performs best: In real game traces, the Extrapolated Velocity (xv) EPP scheme showed the most substantial improvements, reducing prediction error by up to 47.0% for bzflag and 57.6% for sauerbraten compared to the raw (no-EPP) method. This is attributed to the rv motion model best matching the game movements.
- Update rate impact: Increasing the update rate (and thus increasing D, the prediction horizon) reduces the performance gains of EPPs, as predicting further into the future becomes inherently harder.
Limitations and Future Work
- Motion model dependency: The effectiveness of EPPs is tied to the accuracy of the chosen motion model. If the actual avatar movement deviates significantly from the assumed model, EPP performance might degrade.
- Parameter tuning: The paper mentions that the optimal packetization method depends on parameters like packet header size (H) and EP payload size (L), as well as available bandwidth. Finding the ideal balance might require dynamic tuning.
- Future work: The authors suggest exploring differential coding within piggybacked EPPs to further reduce packet size. They also imply that further research into more adaptive scheduling and packetization strategies could yield even better results.
Summary updated