CausalSim: A Causal Framework for Unbiased Trace-Driven Simulation
CausalSim: A Causal Framework for Unbiased Trace-Driven Simulation
复制标题
DOI：
--
复制
发表时间：
2022-01
期刊：
影响因子：
--
通讯作者：
Abdullah Alomar;Pouya Hamadanian;Arash Nasr-Esfahany;Anish Agarwal;MohammadIman Alizadeh;Devavrat Shah
中科院分区：
文献类型：
--
作者：
Abdullah Alomar;Pouya Hamadanian;Arash Nasr-Esfahany;Anish Agarwal;MohammadIman Alizadeh;Devavrat Shah
我们提出了CauseSim，无偏跟踪驱动模拟的因果框架。当前的轨迹驱动模拟器假设被模拟的干预（例如，新算法）不会影响轨迹的有效性。然而，真实世界的轨迹通常会受到算法在轨迹收集期间所做的选择的影响，因此在干预下重放轨迹可能会导致不正确的结果。CauseSim通过学习系统动态的因果模型和在跟踪收集期间捕获底层系统条件的潜在因素来解决这一挑战。它在一组固定的算法下使用初始随机对照试验（RCT）来学习这些模型，然后在模拟新算法时应用它们来消除跟踪数据中的偏差。CauseSim的关键是将无偏跟踪驱动的模拟映射到具有极稀疏观测的张量完成问题。通过利用RCT数据中存在的基本分布不变性，CauseSim实现了一种新的张量完成方法，尽管观测值稀疏。我们在真实的和合成数据集上对CauseSim进行了广泛的评估，包括来自Puffer视频流系统的十多个月的真实的数据，结果表明，与专家设计和监督学习基线相比，CauseSim提高了模拟准确性，平均减少了53%和61%的错误。此外，CauseSim提供了显着不同的见解ABR算法相比，有偏见的基线模拟器，我们验证了一个真实的部署。
We present CausalSim, a causal framework for unbiased trace-driven simulation. Current trace-driven simulators assume that the interventions being simulated (e.g., a new algorithm) would not affect the validity of the traces. However, real-world traces are often biased by the choices algorithms make during trace collection, and hence replaying traces under an intervention may lead to incorrect results. CausalSim addresses this challenge by learning a causal model of the system dynamics and latent factors capturing the underlying system conditions during trace collection. It learns these models using an initial randomized control trial (RCT) under a fixed set of algorithms, and then applies them to remove biases from trace data when simulating new algorithms. Key to CausalSim is mapping unbiased trace-driven simulation to a tensor completion problem with extremely sparse observations. By exploiting a basic distributional invariance property present in RCT data, CausalSim enables a novel tensor completion method despite the sparsity of observations. Our extensive evaluation of CausalSim on both real and synthetic datasets, including more than ten months of real data from the Puffer video streaming system shows it improves simulation accuracy, reducing errors by 53% and 61% on average compared to expert-designed and supervised learning baselines. Moreover, CausalSim provides markedly different insights about ABR algorithms compared to the biased baseline simulator, which we validate with a real deployment.