Large-Scale Computer Network Experimentation Through Simulation

对计算机网络的研究虽然是一门相对年轻的科学，但与任何科学研究没有什么不同，因此需要建立在通过实验验证理论的基础上。在这个奖项中，我们专注于基于计算机的模拟的使用，它在创建一般实验环境方面提供了最大的灵活性。然而，模拟带来了几个重要的挑战。首先，互联网是一个不断变化的、高度异质的环境，通常很难建模。第二个问题是如何在基于计算机的模拟中真实地反映互联网的大规模。我们主要感兴趣的是在这项研究中解决后一种挑战。我们之所以对大规模网络模拟感兴趣，是因为我们将网络模拟视为了解新协议、机制、网络服务或应用在大型网络(如Internet)上广泛部署时的真实效果的重要工具。简单地扩展从小型模拟得出的结论，并在扩展到大规模时对效果和行为做出推断显然是有问题的。虽然今天在互联网规模上的网络模拟仍然不可行，但在过去的几年里，在提高网络模拟的规模能力方面已经取得了相当大的进展。我们的工作以这种改进的扩展能力为起点。这一奖项代表着一种努力，它超越了如何进行大规模模拟运行的问题，并解决了如何进行大规模模拟实验的问题。模拟实验通常由多个相关运行组成，并且还由特定的验证和/或评估目标(例如，如果在其所有路由器中启用某一队列管理算法将会发生什么)来定义。我们注意到，我们的工作主要集中在数据包级离散事件模拟，而不是允许通过聚合和近似进行扩展的其他方法。我们的目标是了解忠实的数据包级离散事件模拟作为实验和验证工具的局限性。我们的目标是研究如何进行大规模模拟实验的问题。我们专注于两个主要研究领域：1.我们将开发和分析允许高效执行多次网络模拟运行的技术。一个关键的观察是，组成一个实验的多次运行通常是相关的。利用这一事实，我们将开发技术，允许一个运行的计算在其他运行中重复使用，从而减少完成一组运行的时间。我们的初步工作证明了这种方法的可行性。我们注意到，虽然我们的许多基本思想一般都可以应用于模拟，但它们的有效实例化的细节在很大程度上取决于领域。本项目中的大部分研究将集中在针对特定、重要的网络协议和体系结构类的网络模拟的背景下利用这一想法。我们考虑了两种具体的方法，一种基于可更新模拟的使用，另一种基于模拟克隆。2.我们的第二个研究领域使用假设的执行大规模网络模拟实验的能力作为起点。我们问的主要问题是，为了得出正确的“互联网规模”结论，模拟实验的规模应该有多大？诚然，这是一个很难回答的问题。然而，我们认为，最近在大规模网络模拟方面的进展使最终开始解决这个问题成为可能。我们现在能够考虑网络模拟的非平凡尺度对由此得出的结果的影响。这项工作的目标是开发和分析一种系统的、动机良好的方法来回答“多大才是大--足够大？”问题。我们提出了一种稻草人的方法，这将是我们调查的起点。我们还提供了实验证据，展示了规模如何影响模拟结果。

The study of computer networks, while a relatively young science, is no different from any scientific inquiry and as such needs to be built on top of a theory-validated-by-experiment foundation. In this award we focus on the use of computer-based simulation which provides the greatest flexibility in creating a general experimentation environment. Simulation offers several important challenges, however. First is the fact that the Internet is an ever changing, highly heterogeneous environment that is typically very difficult to model. Second is the question of how to faithfully reflect the large scale of the Internet in a computer-based simulation. We are primarily interested in addressing this latter challenge in this research. Our interest in large-scale network simulation is motivated by the fact that we view network simulation as an important tool to understand the true effect of a new protocol, mechanism, network service, or application when widely deployed on a large network such as the Internet. It is clearly problematic to simply extend conclusions derived from small simulations and make inferences regarding effect and behavior when extended to a large scale.While simulation of networks at the scale of the Internet remains infeasible today, there has been considerable progress made in the last few years in increasing the scale capability of network simulations. Our work uses this improved scaling capability as a starting point. This award represents an effort to go beyond the question of how to perform a large scale simulation run and address the question of how to perform a large-scale simulation experiment. A simulation experiment typically consists of multiple related runs and is also defined by a specific validation and/or evaluation objective (e.g., what will happen if an ISP enables a certain queue management algorithm in all its routers). We note that our work focuses primarily on packet-level discrete-event simulation, as opposed to other approaches that allow scaling through aggregation and approximation. Our goal is to understand the limits of faithful packet-level discrete event simulation as a vehicle for experimentation and validation.With the goal of investigating the question of how to perform large-scale simulation experiments we focus on two principal areas of research: 1. We will develop and analyze techniques that allow for the efficient execution of multiple network simulation runs. A key observation is that the multiple runs that make up an experiment are often related. Exploiting this fact, we will develop techniques to allow computations from one run to be reused in other runs, thereby reducing the amount of time to complete a set of runs. Our preliminary work demonstrates the feasibility of this approach. We note that while many of our basic ideas can be applied to simulations in general, the specifics of their efficient instantiation is very much domain dependent. Much of the research in this project will focus on exploiting this idea in the context of network simulations for specific, important classes of network protocols and architectures. We consider two specific approaches, one based on the use of updateable simulations and the other based on simulation cloning. 2. Our second area of research uses as a starting point a presumed ability to perform large-scale network simulation experiments. The main question we ask is how large should a simulation experiment be in order for one to reach correct ``Internet-scale" conclusions? This is admittedly a very hard question to answer. We feel, however, that recent advances in large-scale network simulations have made it possible to finally begin to address this question. We are now capable of considering the effect of non-trivial scaling of a network simulation on the results derived from it. The goal of this work is to develop and analyze a systematic, well-motivated approach for answering the "how large is large-enough?" question. We present a strawman approach which will represent the starting point of our investigation. We also provide experimental evidence demonstrating how scale can affect simulation results.