Random vs. Combinatorial Methods for Discrete Event Simulation of a Grid Computer Network
Random vs. Combinatorial Methods for Discrete Event Simulation of a Grid Computer Network
复制标题
DOI：
--
复制
发表时间：
2009-10
期刊：
影响因子：
--
通讯作者：
中科院分区：
文献类型：
--
作者：
本研究比较了随机和t路组合输入的网络模拟器，以确定这两种方法是否产生显着不同的死锁检测不同的网络配置。建模死锁检测对于分析可能无意中降低网络操作的配置更改或确定攻击者可能故意引起死锁的修改非常重要。可以使用输入的随机生成来进行网络的离散事件仿真。在本研究中，我们比较了随机生成的输入和组合生成的输入。组合（或t路）测试要求任何t参数值的每个组合都至少被一个测试覆盖。组合方法可以是非常有效的，因为经验数据表明，几乎所有的故障都涉及少量参数（1到6）的相互作用。因此，例如，如果所有死锁都涉及n个参数之间的最多5路交互，则对所有n路交互的穷举测试不会添加通过测试所有5路交互无法获得的额外信息。虽然死锁中涉及的参数之间的最大交互程度显然无法预先知道，但覆盖所有t路交互可能比使用随机生成的输入更有效。在这项研究中，我们测试了t = 2，3和4的网络模拟中的死锁检测的假设。要达到与4路测试相同的覆盖度，需要大约3.2倍的随机测试;因此组合方法对于检测涉及更高交互程度的死锁更有效。本文回顾了这些结果的解释和影响建模和仿真。
This study compared random and t-way combinatorial inputs of a network simulator, to determine if these two approaches produce significantly different deadlock detection for varying network configurations. Modeling deadlock detection is important for analyzing configuration changes that could inadvertently degrade network operations, or to determine modifications that could be made by attackers to deliberately induce deadlock. Discrete event simulation of a network may be conducted using random generation, of inputs. In this study, we compare random with combinatorial generation of inputs. Combinatorial (or t-way) testing requires every combination of any t parameter values to be covered by at least one test. Combinatorial methods can be highly effective because empirical data suggest that nearly all failures involve the interaction of a small number of parameters (1 to 6). Thus, for example, if all deadlocks involve at most 5-way interactions between n parameters, then exhaustive testing of all n-way interactions adds no additional information that would not be obtained by testing all 5-way interactions. While the maximum degree of interaction between parameters involved in the deadlocks clearly cannot be known in advance, covering all t-way interactions may be more efficient than using random generation of inputs. In this study we tested this hypothesis for t = 2, 3, and 4 for deadlock detection in a network simulation. Achieving the same degree of coverage provided by 4-way tests would have required approximately 3.2 times as many random tests; thus combinatorial methods were more efficient for detecting deadlocks involving a higher degree of interactions. The paper reviews explanations for these results and implications for modeling and simulation.