网络自相似性及其在测试中的应用

理论计算机科学电子笔记164（2006）67-82www.elsevier.com/locate/entcs测试自相似网络Constantinos Djouvas康斯坦丁诺斯·朱瓦斯1，2计算机科学美国纽约市立大学研究生中心南希·D Gri Bleeth3纽约市立大学莱曼学院关闭NY，USA南希·A 林奇4麻省理工关闭MA，USA摘要网络测试中的一个难题是验证一类网络以及被测实际网络的正确性。在实践中，实际上最多测试几个网络（有时只有一个）因此，一个重要的问题是如何选择一个或多个网络是充分代表性的应用结果的一类网络。我们提出了一个基于模型的技术，选择一个代表性的网络。中心定理确定代表网络显示存在于该类的任何网络中的任何故障本文介绍了用于网络选择的自相似性概念，并给出了对一类网络进行关键词：测试，验证，模型检查，I/O自动机，参数化过程。1引言当供应商测试自己的网络设备时，目标是验证设备是否适用于一系列网络拓扑和配置。网络1这项工作得到了DARPA/AFOSR MURI Award F49620-02-1-0325、MURI AFOSR Award SA 2796 PO 1-0000243658、NSF Award CCR-0121277、NSF Award NetTS-0435130、USAF、AFRL Award FA 9550 -04-1-012、DARPA Air Force（STTR）contract FA 9550 -04-C-0084和Cisco URP Award的部分支持。2电子邮件：cdjouvas@gc.cuny.edu3电子邮件：ndgriffeth@lehman.cuny.edu4电子邮件：lynch@csail.mit.edu1571-0661 © 2006由Elsevier B. V.出版，CC BY-NC-ND许可下开放获取。doi：10.1016/j.entcs.2006.09.00768C. Djouvas等人/理论计算机科学电子笔记164（2006）67用户还可能需要验证一类网络的正确性。例如，ISP网络不断变化。即使是小型组织也会定期添加新主机。随着新技术或更高带宽的出现，任何人都可以添加或更换新的网络设备。其余设备必须继续按预期工作。这种观察激发了如何选择网络进行测试的问题，而真正的目标是验证一类网络是否有效。 这项工作的中心目标是找到一类网络的单一代表，其正确性意味着该类的正确性。本文研究了一个子网络的使用，这个子网络对该类中的所有网络都是公共的，并且其行为看起来像任何网络的行为。当一个子网络具有这种性质时，该类被称为“自相似”。测试人员也可以使用一个较弱的条件，相对于一个属性的自相似性，来建立网络符合施加该属性的单一要求。在后一种情况下，只需要说明该属性，并证明如果一个网络符合该属性，则由该网络的多个副本组成的任何组合也符合该属性。互联网协议的设计使得互联网协议的许多属性是自相似的。代理是自相似性的一个众所周知的例子。代理后面的Web服务器对于客户端来说就像是Web服务器;同样，代理和客户端一起对于Web服务器来说就像是客户端交换和路由算法的设计目的是隐藏它们所支持的网络结构，以便单个交换机或路由器的行为看起来像一个更大的网络的行为。DHCP故障转移服务器的设计看起来像一个单一的，高度可靠的服务器。在本文中，我们将讨论如何在不降低测试覆盖率的情况下，降低被测网络的规模和复杂性。本文的核心贡献是通过找到所有网络的共同子结构来选择要测试的网络的方法，该子结构的行为类似于每个网络。定义和基本定理在第3节和第4节中给出。在第5节和第6节中，我们描述了一个案例研究，其中我们建模了学习桥的转发功能，并证明了自相似性。在第7节中，我们描述了一个关于网络测试的实验，其中运行了三个测试，每个测试由不同的学习桥配置组成2相关工作一般的问题是如何确定一个小的测试，将验证正确性的整个类的网络。协议一致性测试通过验证单个网络设备的实现是否符合所需的协议标准来解决问题。然后，假设协议标准保证网络具有所需的属性，协议一致性测试表明，由任何数量的互连设备组成的网络具有所需的属性。协议一致性测试的优秀综述见[10]。然而，一致性测试的先决条件是每个协议都有一个经过验证的正式模型，并证明这些模型具有所需的属性。在实践中，互联网标准很少被正式化，制定正式标准C. Djouvas等人/理论计算机科学电子笔记164（2006）6769证明才刚刚开始。一些标准，如BGP，已经被证明有严重的问题[6]。其他的，如DHCP，正常工作的概率很高，但在极少数情况下会出现错误[3]。尽管如此，这些协议具有理想的属性，并且能够验证特定实现的所需属性非常重要。一种不同的网络测试方法是将协议一致性测试扩展为这种方法将网络视为一个黑盒子，其外部行为是已知的，但其内部行为无法观察到。 测试方法需要开发网络外部行为的正式模型，以生成覆盖所有可能序列的测试 可见的行动。如上所述，网络和协议的模型很少可用，开发起来也很耗时基于实际实践的工业网络测试描述见[1，5]。Buchanan[1]提出了测试网络的特设和常识方法。虽然这些技术很有价值，但很难分析和优化它们。Gri Betheth [5]介绍了一个工业实验室中互操作性测试的案例研究。对朗讯下一代网络互操作性实验室（NGN）的四个测试项目（一个IP语音、两个数据中心和一个网络管理）的每个测试阶段所需时间的研究表明，绝大多数时间都花在了测试网络设置上[5]。图1总结了本研究的结果以及当前实验的结果。本文的假设是，只测试一种配置将大大节省时间，因为只需要设置一个网络一个类似的问题，即验证一个参数化的进程集合，已经在模型检查中得到了解决。Wolper和Lovinfesse[12]以及Kurshan和McMillan[9]已经展示了如何应用归纳法来验证参数化的过程集合。他们的结果适用于相同过程的集合，这在本文中并不严格要求。 此外，它们需要过程的互模拟;目前的结果只需要遏制。它们还要求测试者设计一个不变量。 这对这项工作来说是不必要的。 在最简单的情况下，测试人员必须只识别需求强加了自相似属性。 其他工作降低模型检测的复杂性3I/O自动机模型为了分析网络属性，我们使用I/O自动机建模框架[11]，它将网络组件建模为自动机，并将它们的交互建模为自动机的共享动作。该模型为一个网络的行为与另一个网络的行为相似提供了形式化的基础：如果自动机A的所有外部可见行为也是B的外部可见行为，则自动机A被称为实现了自动机B。证明一个自动机实现另一个自动机的一个重要技术是模拟。自动机A被称为模拟B，如果存在一个模拟关系（在第6节中定义）将A的状态与B的状态联系起来。自相似自动机70C. Djouvas等人/理论计算机科学电子笔记164（2006）67××≥Fig. 1.网络测试各阶段所需的时间。阴影条显示NGN研究的结果。 测试实验室设置没有花费大部分时间的唯一测试是网络配置测试工具，即，网络设置。交叉阴影线表示本文所报道的实验结果A是一个可以被复制并通过通道连接到自身以形成实现原始自动机A的新自动机。另一个重要的概念是自相似属性，这是自动机的一个属性，是由这样的组合物保存的我们简要回顾了I/O自动机的定义;有关详细信息，请参见[11]。定义3.1I/O自动机由以下组件组成：• sig（A），签名，由三个不相交的动作集合组成：输入动作in（A）、输出动作out（A）和内部动作int（A）。输出和内部操作是本地控制的;输入操作是由环境控制的。签名中的所有动作的集合被表示为动作（A）。• 状态（A），一个非空的，可能是有限的状态集合。• start（A），状态（A）的非空子集，称为起始状态。• 反式（A）， 一 状态转移 关系， （A）行为（sig（A））国家（A）。我们要求对于每个状态s和输入动作π，存在一个transi- tion（s，π，SJ）。• 任务（A），任务划分，其是关于具有至多可数个等价类的局部控制动作的等价关系。I/O自动机A的执行是序列s0，π1，s1，.， s n−1，π n，s n，其中s0是起始状态，（s i−1，π i，s i）是每个i的跃迁1. 执行可以是有限的，也可以是无限的。A的执行集表示为execs（A）。我们将迹（A）定义为所有序列π1，π2，.的集合，πn，. 通过从execs（A）中的序列中删除状态和内部操作获得。跟踪捕获外部可见行为的概念。自动机A的迹性质是对A的所有迹都成立的性质。C. Djouvas等人/理论计算机科学电子笔记164（2006）6771（A）-（A）。i{Si}i∈i，j∈I，i/jI⊆组合操作允许通过组合原始I/O自动机来构造复杂的I/O自动机。 为了组成自动机，我们将不同自动机中具有相同签名的动作视为相同动作，并且当任何组件执行动作π时，它迫使具有相同动作的所有组件执行该动作。为了组成自动机，它们必须兼容：定义3.2可数集合是相容的，如果对于所有=，以下所有成立：（1）int（Si）acts（Sj）=φ，（2）out（Si）out（Sj）=φ，并且(3)没有行动包含在无限多个集合行动（Si）中。定义3.3给定自动机的相容集合{Ai}i∈IA=i∈IAi由以下规则形成• sig（A）定义为：out（A）=i∈Iout（Ai），int（A）=i∈Iint（Ai），且in（A）=• states（A）=i∈Istates（Ai）.• start（A）=i∈Istart（Ai）.• transs（A）是三元组（s，π，sJ）的集合，使得对于所有i ∈ I，如果π ∈acts（A i），则（s i，π，sJi）∈ transs（A i）;否则，s i= sJi。• tasks（A）=i∈I（A i）.我们表示自动机A1，...，A n由A1... A.在组成I/O Automata之后，我们可能希望隐藏用于组件之间通信的操作，使它们成为组合的内部操作。因此，ActHideΦ（A），对于Φout（A），定义为从A获得的自动机将Φ中的每个动作重新分类为内部动作。4自相似激发这篇论文的问题是找到一个有代表性的网络测试而不是测试类的所有成员。如果有一个小网络N“看起来像”类中所有较大的网络，那么最小的网络是一个明显的候选者。 这是因为我们可以测试N本身来确定属性 全班最好的学生定义自相似性。因为我们对网络感兴趣，所以我们只考虑具有发送输出动作和接收输入动作的自动机。 这些自动机由它们到网络的端口（接口）的数量参数化。每个发送动作都与一个端口相关联，并使用该端口发送消息。每个接收动作也与端口相关联，并接收到达端口的消息消息是通过端口的可能消息的集合。具有n个端口的自动机具有至少包含以下动作的签名send（m：Message，i：Int），其中1≤i≤n，receive（m：Message，i：Int），其中1≤i≤n。72C. Djouvas等人/理论计算机科学电子笔记164（2006）67−--ǁǁǁ ǁ ⊆−为了组合自动机，我们使用通道自动机Channel（A，B）i，j，如[11]中所述。它将自动机A的端口i连接到自动机B的端口j。(When 只有两个自动机正在组成，我们只写通道i，j。该自动机具有输入动作send（m，i）A和send（m，j）B以及输出动作receive（m，i）A和receive（m，j）B。 我们假设消息被可靠地、有序地、无重复地传递。假设一个自动机N由端口数n参数化。然后我们说N（n）是自相似的，如果迹（ActHideΦ（N（n））通道i，j（n））迹（N（2 n2）），其中Φ=send（m，i）a，send（m，j）b，receive（m，i）a，receive（m，j）b.换句话说，使用连接端口i和j的通道，N（n）与自身的组合的外部可见动作看起来像单个自动机N（2n 2），忽略连接自动机的端口上的动作我们还定义了网络属性的自相似性，因为建立感兴趣属性的自相似性可能比建立整个自动机的自相似性更容易我们说迹性质T是自相似的，如果网络N（n）信道i，jN（n）具有性质T，只要网络N（n）具有性质T。因此，关于网络N（n）的自相似性质的测试结果可以推广到更大的网络。在测试中使用自相似性。根据自相似性的定义，自相似网络N的正确行为意味着由N的多个实例组成的更大网络的正确行为。也许更重要的是，如果在更大的网络中有bug，它们也会在N中被发现。有两种方法可以让我们利用自相似性来减小测试网络的大小。 首先，我们可以定义一个网络的自相似模型，该模型具有测试样本中感兴趣的属性。 其次，我们可以直接测试感兴趣的属性是否自相似。 案例研究 第6节中的学习桥梁遵循第一种方法。一组公理学习桥梁和证明，一个组合的两个自动机遵守公理在本文的一个较长的版本中提出[2]。自相似模型这种方法需要自相似的网络的广义模型M如果该规范对M成立，并且如果我们通过测试确定N实现了M，那么我们可以使用测试结果，就好像N本身是自相似的。下面的定理是这个主张的基础定理4.1若M（n）是自相似的，且迹（N（n））≠迹（M（n））<$traces（S），则ActHideΦ（traces（N（n）<$Channel i，j<$traces（N（n））<$traces（S）。这个定理说，给定一个网络N（n）和一个自相似模型M（n），其中M（n）实现S，N（n）实现M（n），我们可以得出两个C. Djouvas等人/理论计算机科学电子笔记164（2006）6773∧ ∧∧∧网络N（n）的组合实例实现S。通过归纳，我们可以组合任意数量的N（n）的实例，并且仍然符合S。证据 从定义中直接得出。Q自相似性质。如果自相似迹性质S和T对网络N都成立，那么迹性质ST显然也成立。这个事实可以用来证明一个复杂网络满足性质T1T2... T n：在证明这一点时，可以证明每个单独的属性T i都是自相似的，而不是一起考虑属性。并不是我们感兴趣的测试的每个属性都是自相似的。然而，我们相信许多人会这样做;对于这些人，可以使用小型网络进行测试。5学习桥接器一个学习桥将独立的IEEE 802 LAN段互连成一个桥接LAN。它在独立的LAN网段之间“智能地”中继和过滤帧学习网桥包含转发算法和生成树算法。转发算法最初转发到达的每个帧，每隔一个端口输出一个端口。 此外，当帧到达端口时，转发算法会“学习”源地址和端口之间的关系。它将这种关系记录在一个过滤数据库中。一旦转发算法了解了地址与端口的关系，它就会在相应的端口上转发发送到该地址的任何帧。生成树算法将任意拓扑转换为树。这消除了网络中的循环，因此帧不会永远转发。我们假设生成树算法强制执行以下重要属性，如标准所要求的：“生成树算法为任何桥接LAN拓扑创建单个生成树。”因此，在任何两个主机之间存在唯一路径，并且消除了循环6学习桥本节将展示我们证明学习桥是自相似的。证明是基于一个广义模型的学习桥梁。自相似性属性允许测试者使用定理5.1来证明仅测试单个学习桥以验证整个网络5是合理的。学习网桥操作可以简单地描述为5请注意，我们在本文中只讨论了消息的转发，而没有讨论生成树的构造。74C. Djouvas等人/理论计算机科学电子笔记164（2006）67完全符合这一要求的网桥网络不是自相似的。请考虑以下示例：示例6.1学习桥。网桥A和B相互连接，在从S（源）到D（目的地）的路径中，A在B之前。假设A中的过滤数据库不包含D的条目，而B中的过滤数据库包含D的条目。然后，如果发起的消息是从S到D，则A将该消息转发到每个活动端口，但B仅将其转发到正确的端口。将A和B组成一个桥AB。上面的要求意味着外部观察者会期望AB的跟踪只有一个目的地为D的传出消息。 但这并没有发生。 相反，从A继承的所有端口和从B继承的单个端口- 也就是B转发消息的那个人。因此，我们定义了一个通用模型，它只需要网桥将每个消息复制到“正确的端口”，也许还需要复制到其他端口。通过学习桥通过使用过滤数据库来记录每个到达消息的源地址以及它到达的端口来发送到该地址的所有后续消息将被复制到相应的端口（可能还有其他端口）。如果没有收到来自目的地址的报文，则过滤数据库没有该地址的条目，网桥将报文转发到所有端口。广义模型。每个桥有五个动作：输入动作接收，输出动作发送，以及内部动作copyIn，copyOut和delete。它有一个过滤数据库，每个端口的输入和输出缓冲器，以及对应于每个（输入端口，输出端口）对的队列数组。 数组入口队列[i，j]是一个消息队列，这些消息已经到达端口i，并将被发送到端口j。接收操作将接收到的消息添加到到达端口的输入缓冲器中，并更新过滤数据库。send动作将端口输出缓冲器中的第一条消息发送到连接到该端口的通道。 copyIn操作复制 从输入缓冲器到输入端口所有内部队列末尾的消息;copyOut将消息从一个内部队列复制到输出缓冲器。最后，如果在删除时正确的端口是已知的并且队列不对应于消息6的正确端口，则删除动作可以从内部队列中删除任意消息m。我们假设在任何网桥中有有限数量的活动端口，并且生成树算法确定哪些端口是活动的。automatonbridge（n：Int）i签名6.删除操作是对允许将消息从正确端口以外的端口转发出去的网桥进行建模的多种方法之一。它不确定地从队列中删除未指向正确端口的消息C. Djouvas等人/理论计算机科学电子笔记164（2006）6775----联系我们联系我们∧输入receive（m，inPort）输出send（m，outP ort）i内部copyIn（m，inPort）copyOut（m，inPort，outPort）idelete（m，inPort，outPort）i国inbuf，输入缓冲器数组，索引为1、......、n，每个端口outbuf，一个输出缓冲器（FIFO队列）数组，索引为1，.，n，每个端口一个，最初都是空的。队列，一个FIFO队列数组，索引为1、......、n 1，...，n每对端口一个，最初都是空的。filterDB，消息目的地到网桥端口的映射i索引通过{1，...，n}，最初都是nil。receive（m，inPort）检查将m添加到inbuf（inPort）setfilterDB（m.src）：=inPort send（m，outPort）i前提outbuf上的第一个元素检查从outbuf中删除第一个元素copyIn（m，inPort）前提条件m是inbuf[inPort]事件上的第一个元素将m添加到queue[inPort，i]中，用于所有i从inbuf[inPort]中删除mcopyOut（m，inPort，outPort）i前提输入端口队列中的第一个元素检查将m添加到outbuf[outPort]removem fromqueue [inPort，outPort]delete（m，inPort，outPort）i前提m在队列queue[inPort，outPort]filteringdb[dest（m）]中=nil filteringdb[dest（m）]检查从队列[inPort，outPort]中删除m输出端口桥梁组成现在，我们描述两个学习桥梁的组成。我们假设生成树算法已经被网络中的所有网桥运行完成，并且没有失败。因此，任何两个网桥之间只有一条活动路径。让桥1和桥2是两个学习桥，运行上面给出的IOA代码。 我们使用约定，端口i是桥1的端口，j是端口2号桥。不失一般性，我们假设桥1的端口i0通过通道i0、j0与桥2的端口j0连接。由于采用了生成树算法，这些端口是连接网桥1和网桥2的唯一活动端口。假设网桥c是将网桥2的端口重命名为n+1，...，2n（避免与网桥1的端口号冲突），然后将网桥1和网桥2组成一个连接通道，最后隐藏它们之间通道上的发送和接收桥c=ActHideΦ（桥1|信道i0，j0|桥2），以及Φ ={发送（m，i0）1，接收（m，i0）1，发送（m，j0）2，接收（m，j0）2}。76C. Djouvas等人/理论计算机科学电子笔记164（2006）67≤≤≤≤−≤≤≤ ≤我们的目标是证明桥c本质上与单个桥相同，我们将其称为桥p，运行学习桥IOA。桥接器P必须具有与桥接器1和桥接器2一起相同的端口数，减去两个连接的端口。因此，如果网桥1和网桥2每个都有n个活动端口，则网桥p有2n 2个活动端口。网桥p的端口i，带1我n连接到与桥1的相应端口i相同的信道。类似地，网桥p的端口j，其中n+1连接到与桥2的相应端口j相同的信道。最后，网桥p的输入和输出动作被重命名，使得端口i上的动作1 i n是receive（m，i）1和send（m，i）1（而不是receive（m，i） p和send（m，i） p）;类似地，端口j上的动作n+ 1j2 n是receive（m，j）2和send（m，j）2。模拟一座由多座桥梁组成的桥梁我们使用一个关于IOA的重要定理来证明桥c的等价性到布里奇角。该定理表明，如果IOAA到IOAB之间存在模拟关系（定义如下），则迹线（A）等于迹线（B）。定义6.2从IOAA到IOAB的模拟关系是一个关系R=states（A）×states（B）。定义f：状态（A）→ P（状态（B）），由f（s）={t|（s，t）∈ R}. 为了成为模拟关系，R必须满足：(i) （起始条件：）若s∈start（A），则f（s）<$start（B）φ（起始条件）。(ii) (Step条件：）如果s是A的可达状态，u∈f（s）是B的可达状态，并且（s，π，SJ）∈transs（A），则存在B的执行片段α，该执行片段从状态u开始，到某个状态UJ∈f（SJ）结束，使得trace（α）=trace（π）。下面，我们定义一个从桥c到桥p的关系R，并证明R是一个模拟关系。这给了我们想要的结果：定理6.3学习桥自动机bridge（n）是自相似的。证据 假设s是桥c的状态，t是桥p的状态。 我们用点表示法 表示桥中的状态变量，例如，s.filterDB1是网桥c的状态s中网桥1的过滤数据库的值。对（s，t）属于关系R，如果：(i) t.filterDB= s.filterDB1= s.filterDB2− {端口地址，端口号|port ∈ {i0，j0}}(ii) t.outbuf[i]=s.outbuf[i]m，对于i∈ports1ports2− {i0，j0}，m∈ {1，2}依赖于i的值。(iii) t.inbuf[i]=s.inbuf[i]m，对于i∈ports1ports2− {i0，j0}，m∈ {1， 2}依赖于i的值。(iv) 消息队列的内部数组t.queue对应于组合数组s.queue1和s.queue2，如下所示：• t.queue[i，iJ]=s.queue[i，iJ]1 ifi，iJ ∈ports1，i，iJ/=i0• t.queue[j，jJ]=s.queue[j，jJ]2如果j，jJ∈端口2，j，jJj0• t.queue[i，j]是以下队列的级联，i∈端口1，j ∈端口2，其中ii =i0，j i =j0：C. Djouvas等人/理论计算机科学电子笔记164（2006）6777S. queue [j0，j] 2，s.outbuf[j0] 2，s. queuej0，i0，s.inbuf[i0] 1，s. queue [i，i0] 1• t.queue[j，i]对于i∈端口1，j ∈端口2对称定义，其中i i0，ji =j0：这些条件意味着：(i) 网桥p的过滤数据库包含与网桥c的两个组件网桥的过滤数据库的并集相同的条目，不包括内部端口的条目。(ii) 网桥p的每个端口的输出缓冲器包含与网桥c的相应端口的输出缓冲器相同的消息。在桥p中没有对应于i0和j0的缓冲器。桥c中的这些缓冲器可以包含与其它条件一致的(iii) 网桥p的每个端口的输入缓冲器包含与网桥c的相应端口的输入缓冲器相同的消息。(iv) 队列的内部阵列中的队列在网桥P中与网桥C中相同，如果该条目将输入端口连接到同一组件网桥的输出端口;否则，它们是涉及信道队列和端口i0和j0的缓冲器的级联。为了证明R是一个模拟关系，我们必须证明起始条件和步长条件。前者是微不足道的，因为两个桥的所有状态最初都是空的。后者要求证明桥p和桥c的状态在每个动作之后对应。首先，我们证明过滤数据库的状态对应：定义6.4状态不变量：在组合IOA的所有可达状态中，网桥c的过滤数据库对应于网桥p的过滤数据库，如模拟关系所定义的证据是通过归纳执行的长度。 结果很明显，如果消息仅在其到达的网桥的端口上被转发。当帧到达一个网桥并从第二个网桥转发出去时，这种情况就不那么明显了。在这种情况下，网桥1和网桥p的过滤数据库在接收到具有到达端口和源地址之间的关系的消息时被更新。之后，网桥2的过滤数据库被更新，以显示通过网桥1到达源的路径。 由于模拟关系仅引用条目 在桥1中，忽略桥2中的条目，在这种情况下，它被保留（以及 所有其他）。为了证明输入缓冲器、输出缓冲器和内部队列在每个动作之后都是对应的，我们考虑所有的动作π。 表1总结了所有可能的操作 桥C的相应执行片段、桥P的相应执行片段以及对于两个桥都相同的78C. Djouvas等人/理论计算机科学电子笔记164（2006）67桥C的作用的执行片段桥P微量1234567891011121314151617181920接收（m，i）1，i/= i0接收（m，j）2，j/=j0接收（m，i0）1接收（m，j0）2发送（m，i）1，i/= i0发送（m，j）2，j/= j0发送（m，i0）1send（m，j0）2发送（m，i，iJ）1，iJ=/i0delete（ m，j，jJ）2，jJ/=j0delete（ m，i，i0）1delete（ m，j，j0）2copyIn（m，i）1，ij = i 0 copyIn（m，i0）1 copyIn（m，j0）2 copyOut（m，i，i j）1，i j = i 0copyIn（m，i 0）1copyIn（m，j 0）2copyOut（m，i，ij）1，i j = i 0copyIn（m，i 0）2copyOut（m，i，ireceive（ m ， i ） 1receive（ m，j）2λsend（ m，i）1send（ m，j）2λλ删除（m，i，iJ ）p 删 除（m，j，jJ）p序列删除（m，i，j）p，j∈por ts2， j=/j0序列删除（m，j，i）p，i∈ ports1，i/=i0copyIn（ m，i）p copyIn（ m，j）pλλcopyOut（ m，i，iJ）pcopyOut（ m，j，jJ）pλλreceive（ m ， i ） 1receive（ m，j）2λsend（ m，i）1send（ m，j）2λλλλλλλλλλλλλλC. Djouvas等人/理论计算机科学电子笔记164（2006）6779j）1，i j = i 0copyIn（m，i 0）1copyIn（m，j 0）2copyOut（m，i，ij）1，i j = i 0copyIn（m，i 0）1copyIn（m，j 0）2copyOut（m，i，ij）1，i j = i 0copyIn（m，i 0）2copyOut（m，i，j0）2 copyOut（m，i，i j）1，i j = i 0copyIn（m，i 0）2copyOut（m我0copyOut（ m，j，jJ）2，jJ/=j0copyOut（ m，i，i0）1 copyOut（ m，j，j0）2表1：网桥c和网桥p的动作之间的对应关系一个简单的案例分析证实了这一结果。Q7实验我们进行了三个测试学习桥梁的目标是量化的影响，减少测试时间的自相似性第一次测试使用了一座桥，第二次测试80C. Djouvas等人/理论计算机科学电子笔记164（2006）67两个连接的桥，第三个使用三个连接的桥。我们的假设是，只做第一次测试将减少测试时间至少一个因素，2、测试三个连接的网桥，因为只需要测试一个配置而不是三个。这种情况下的测试设置比大多数网络测试设置简单得多，因此节省的时间应该被低估。在我们的测试中，我们使用了三台Cisco Catalyst 2950交换机，每台交换机都连接了四台主机，所有主机都位于一个VLAN（vlan1）上。 我们使用300秒（默认值）作为mac-addr-table中条目的过期时间，mac-addr-table是Cisco交换机上包含学习的MAC地址的内部表。因此，5分钟内未使用的条目将从表中删除这些主机与192.168.0.0/24网络中的网络地址进行了确认每个交换机连接四台主机。网络未连接到路由器，因此只能看到来自LAN的流量。在每个测试中，其中一台主机执行脚本，对彼此连接的主机执行ping操作5次。此外，ping器尝试ping各种不存在的主机各5次。在尝试ping列表中的所有主机后，pinger休眠了600秒，使mac-addr-table条目过期，然后重复ping。对于ping，ping器使用参数-f-c5 -p< pattern>.• -f：Flood ping with 0 interval：以主机提供的速度发送数据包。• -c 5：数据包计数为5。• -p：用给定的十六进制模式假设交换机处于压力状态时更可能出现错误，则可以使用“最佳状态”选项来尽可能地对交换机施加压力。每次ping的模式都不同，以发现网络上潜在的数据相关问题使用tcpdump-s 0命令捕获网络跟踪，以捕获整个帧。为了进行分析，我们使用tcpdump和选项-exxtts 0，意思是：• -e：打印每个帧的链路级标题。这是评估交换机行为所必需的，因为它是链路层设备。• - s 0：捕获帧中的所有八位字节，用于评估意外行为。• -tt为每帧打印一个无格式的时间戳，以消除消息匹配的歧义。• -xx：以十六进制打印每个帧，包括其链接级标题正确的网桥行为要求主机捕获以下消息：• 广播：任何主机广播的所有ARP请求消息必须出现在所有主机的跟踪中。换句话说，如果ARP请求消息出现在源主机的跟踪中，它也必须出现在其他主机的跟踪对于连接的主机，ARP请求的数量为1或2，尽管正确的数字可能更高（在其他测试中，我们在较大的LAN上看到多达对于不可用的主机，广播了六条消息• 单播：对于源主机的跟踪中出现的每个单播消息，目的主机上的跟踪必须包含相同的消息（ARP应答消息，C. Djouvas等人/理论计算机科学电子笔记164（2006）6781回送请求消息或回送应答消息）。• 收到的消息：收到的每个消息必须与发送的消息相匹配。对tcpdump生成的网络跟踪的后续分析发现了所有需要的消息。这些测试是由项目研究团队的一名成员设置和运行的，他是雷曼学院计算机科学项目的应届毕业生由于第一个测试运行是单开关测试，其次是两个开关测试，最后是三个开关测试，因此从早期测试中学习可能会减少设置后期测试所需的由于时间限制，我们实际上只使用了一台主机作为pinger，而不是在主机之间轮换;这减少了总的执行时间，因为我们使用了脚本，所以这是可以预测的 它将乘以每个测试中的主机数量（对于一个交换机的情况为4，对于两个交换机的情况为8，对于三个交换机的情况为12）。我们假设对设置时间的影响很小，将脚本复制到其他主机大约需要几分钟表2显示了运行测试所观察到的时间分布。 测试计划所需的时间短可以归因于测试的简单性。我们观察到，在为第一个测试套件设置后，在单一学习桥配置上，为后续测试套件设置实验室所需的时间大大减少了。一桥两座桥三座桥梁测试计划1小时--测试实验室设置12.5小时1.08小时0.92小时测试执行2.33小时（9.3小时）2.33小时（18.6小时）2.33小时（27.9小时）测试文件3小时2小时2小时总18.83小时5.41小时5.25小时表2.1、2和3座桥梁测试阶段所需的时间括号中显示了使用每台主机（而不是仅使用一台主机）作为pinger的假定测试执行时间运行三个测试所需的时间大约是运行第一个测试所需时间的1.6倍，而不是2倍。 其中一个原因是，由于网络是自相似的，测试设置也几乎相同;因此设置一个配置所获得的经验减少了设置下一个配置所需的时间。另一个原因是配置任务本身并不困难。创建测试执行脚本并验证网络配置是否正确是设置中最困难的部分82C. Djouvas等人/理论计算机科学电子笔记164（2006）67我们注意到，在实践中，测试人员实际上不是测试直到达到期望的置信水平，而是测试直到他们耗尽时间。这一现象也影响了本试验。因此，在测试中使用自相似性的主要贡献可能是帮助测试人员选择更好的测试并改进测试结果。测试结果的置信水平这个实验的第二个目标是确定有用的工具，可以使用测试模型，特别是自相似模型，以支持更多的成本效益测试。测试中观察到的困难问题是评估测试结果（即，正确与否），并验证测试实验室设置的正确性。支持确定网络跟踪是否有效的模型将有助于评估测试结果。更好的网络管理工具将有助于验证测试实验室设置的正确性。8结论在本文中，我们已经表明，自相似的网络设备和它们的属性提供了一个强大的工具，以减少规模的网络测试实验室。通过测试最小的自相似子网络，可以测试一类自相似网络中的所有网络。这将待测试的网络数量减少到一个，同时最小化网络的大小学习桥的自相似性的案例研究说明了一种方法，使用自相似性在网络测试。这种方法使用自相似网络模型来捕获网络必须实现的行为。本文[2]的较长版本展示了如何定义学习桥的必要属性并证明自相似性。 当一个模型的 网络协议不可用。需要更多的工作来识别其他自相似网络和网络的重要自相似属性。此外，它将是有用的，以研究使用模型来评估网络测试的结果。 另一条调查线索是确定如何评估网络的一组测试的覆盖范围，开发方法来衡量我们对网络工作的信心水平，给出网络的测试套件确认我们感谢Pearl Abotsi在运行测试方面所做的出色工作引用[1] Robert W.布坎南 测试网络系统的艺术。 Wiley，1996年。[2] 康斯坦丁诺·朱瓦斯南希·格里·里维斯和南希·林奇使用自相似性进行高效网络测试。http://comet.lehman.cuny.edu/griffeth/Papers/selfsimlong.pdf，2005年9月[3] 拉尔夫·德罗姆斯RFC 2131：动态主机配置协议，1997年3月C. Djouvas等人/理论计算机科学电子笔记164（2006）6783[4] Nancy Gri Bleeth，Ruibing Hao，David Lee，and Rakesh Sinha.集成的系统互操作性测试与应用程序，以满足客户的需求。2000年FORTE/PSTV会议记录，意大利比萨，2000年10月[5] 南希·格里高利和弗雷德里克·史蒂文森。一流的互操作性测试方法。Journal of the International Testand Evaluation Association，23（3）：68[6] 蒂莫西·GGri Bern和Gordon T.威尔丰BGP收敛特性分析在SIGCOMM的Proceedings，第277[7] 放大图片作者：David Lee，Rakesh K. Sinha，and Nancy Nancy Gri Gradereth.集成的系统互操作性测试与应用程序，以满足客户的需求。I E E E /ACM Trans. 网络，12（5）：823[8] IEEE局域网和城域网标准：媒体访问控制（MAC）网桥，2004年6月。[9] R. Kurshan和K.麦克米兰过程的结构归纳定理。在PODCPress.[10] D. Lee和M.扬纳卡基斯有限状态机测试原理与方法综述。在IEEE会议录，第84卷，第1090-1126页[11] 南希·林奇。分布式算法摩根·考夫曼出版公司，1996年3[12] P. Wolper和V. Lovinfosse。具有网络不变量的大型过程集的可拓性质。在有限状态系统的自动验证方法中，计算机科学讲义第407卷，第68-80页。Springer-Verlag，1989.