ad-hoc网络中路由协议的博弈论分析方法

理论计算机科学电子笔记119（2005）67-92www.elsevier.com/locate/entcsAd-Hoc路由的博弈论理解Irfan Zakiuddina，1 Tim Hawkinsb，2 尼克·莫在b，3a指挥和情报系统，QinetiQ，Malvern，英国b可信信息管理，QinetiQ，Malvern，英国摘要在本文中，我们提出了一个新的应用博弈论，其中博弈论的技术被用来提供一个严格的支撑ad-hoc路由协议的分析。 爆炸 在过去几年中对ad-hoc网络的关注已经导致提出了非常大量的路由协议。尽管如此，分析路由协议的科学仍然相对不成熟，仍然存在的问题是如何确定给定协议的“好坏”。 我们提出了一个博弈论的方法作为回答这个问题的一个潜在的有效手段。我们相信，将路由概念映射到游戏中是自然而简单的。此外，博弈论为分析关键属性提供了广泛的工具。本文介绍了如何路由技术可以建模为游戏，并提出了一些分析结果。保留字：博弈论，路由，ad-hoc网络，性能分析1介绍博弈论包括一套强大的技术来推理涉及冲突和竞争的情况。本文的主题是博弈论技术在ad-hoc路由协议分析中的应用。我们认为这是这种技术的一种新用途。我们将博弈论应用于这一问题的具体方法将在第3节中描述。1电子邮件：I. signal.QinetiQ.com2电子邮件：T. eris.QinetiQ.com3电子邮件：N. eris.QinetiQ.com1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2004.07.00968I. Zakiuddin等人理论计算机科学电子笔记119（2005）67然而，我们首先概述了目前的研究状态的发展和分析的ad-hoc路由协议。在过去的几年里，人们对ad-hoc网络研究的兴趣激增[1]。这项研究的一个很好的一部分，旨在开发ad-hoc网络的路由协议。结果是现在有非常多的ad-hoc路由协议。设计新协议的部分动机来自于希望满足自组织网络领域的挑战性要求;下面将讨论其中的一些挑战显然，新协议的设计者或ad-hoc网络的开发者需要分析协议，以确定满足需求的程度。主要分析技术基于仿真，使用了许多仿真工具，如OPNET Modeler[2]、NS-2 [3]和GloMoSim [4]。然而，这些工具似乎没有提供一致的结果[5]。Fur-2010，[6]和[7]发现模拟结果与部署实际ad-hoc网络的现场试验结果之间存在差异。人们可能会问：为什么模拟会给出不一致和不可靠的结果？我想到两个答案：• 模拟器试图表现现实，但它的预测失败了，因为它对现实的表现并不足够忠实。• 当模型的行为被模拟器采样和分析时，所选择的样本太小，不能充分代表协议的行为。在这方面，请注意，关于移动性模型的工作具有预先确定完整样本空间的子空间的效果[8]。当被引用的论文推测他们发现的各种糟糕的模拟结果的原因时显然，如果模型是完全忠实的，并且样本覆盖了模型行为的整个空间，那么分析的结果将是一致和正确的。当然，要求完美的保真度是不可能的，而完全覆盖的要求充其量也是非常困难的，即使对于非常抽象和网络模型大小受限的模型也是如此。然而，这两个原则，即保真度和覆盖提供了基础和灵感，我们的工作，试图采取一个新的角度来分析ad-hoc路由协议的问题。1.1我们的方法和本文在我们的方法中，我们的目标是从我们严格分析的抽象模型开始，然后使用这些分析的结果作为指导I. Zakiuddin等人理论计算机科学电子笔记119（2005）6769启发式搜索更精确的模型。因此，我们打算将高覆盖率（在低可靠性模型上）与高可靠性模型（在有限覆盖率下分析）的好处结合起来。本文涉及该计划的第一步：我们如何严格分析低fidelity模型。 第2节讨论了我们对路由协议建模的抽象层次。该部分还讨论了第一种方法，即模型检查，以及为什么我们选择不使用模型检查。 我们认为博弈论提供了一种既自然又强大的分析路由协议的方法。 在第3节中，我们给出了一个非常简短的描述博弈论，以及它如何可以用来分析路由协议。第4节重点介绍了将路由协议映射到游戏时出现的一些一般性问题。迄今为止，我们在博弈论方面取得的成果将在第5、6和7节中介绍。这仍然是我们提出的方案的早期阶段，我们目前的博弈论分析技术存在各种限制;我们在第8节结束时讨论这些限制是什么，如何解决它们以及前进的道路2严格分析路由技术2.1路由技术最近的研究不仅导致了许多路由协议，但许多路由技术。路由技术是指路由协议用来存储和传播路由信息的基本策略路由技术具有以下三个协议特征：• 路由信息是按需传播还是主动传播;• 路由信息是通过遍历还是通过在生成树上传播来传播的;以及• 本地存储和通信的路由信息的格式（无论是链路状态数据、距离矢量还是其他）。因此，路由技术的示例可以是：主动多播距离向量、主动多播链路状态路由、被动多播链路反转等。路由技术可以被视为特定路由协议的抽象此外，可以只对路由技术建模，而不是对技术的协议实例建模（我们将在第3节中讨论）。在我们看来，最抽象的层次上，一个路由协议可以有效地建模是路由技术，它的实例。70I. Zakiuddin等人理论计算机科学电子笔记119（2005）67在确定了路由技术作为我们想要开始研究的层次之后，显而易见的问题是：我们想从这些技术中了解什么？我们打算使用什么样的分析工具2.2我们想学什么我们可以将路由协议属性分为两类：(i) 健全。这意味着路由器会做出正确的路由决策，但此属性对做出决策所涉及的延迟或所消耗的资源不敏感。可靠性相当于说，协议保证最终终止，并且在未指定的通信量之后，路由器具有正确的网络拓扑视图。(ii) 性能这些也被称为效率要求。我们将集中注意以下方面：• 收敛性，它是路由协议响应网络拓扑变化的速度的度量• 网络开销，它是路由协议消耗的网络资源的度量，只是为了使它能够做出正确的路由决策。路由协议设计者对可靠性的主题很感兴趣（阿帕网的错误[9]使得可靠性无法忽视！），但是工程师和ad-hoc协议研究人员的大部分精力都投入到实现和改进性能上。因此，收敛和网络开销都是众所周知的，并且涵盖路由的标准文本（例如[9]）详细讨论了它们。然而，我们还没有发现在文献中的各种路由技术如何比较这两个性能特征的一个明确的分析。我们工作的一个关键目标是了解这个问题，本文报告了我们工作的第我们可以研究路由技术的可靠性和性能，我们相信这是一个很好的起点，为我们的事实上，我们希望对路由技术性能的严格分析将为理解重要问题提供坚实的基础，例如：(i) 在生成树上传播路由信息（而不是复制路由信息）对收敛有什么影响？(ii) 使用生成树方法可以减少多少网络开销(iii) 反应式路由方法消耗的网络资源是否比I. Zakiuddin等人理论计算机科学电子笔记119（2005）6771积极主动的？关于最后一点，公认的观点是，反应式方法确实可以减少管理费用，但我们听到了对这种信念的质疑，我们不知道这种信念的确切基础。在确定了我们想要学习的路由技术之后，接下来要做的决定是使用什么工具2.3我们可以使用哪些工具我们的目标是高覆盖率在我们的探索行为的一个模型的路由技术。在过去的十年中，模型检查的使用[10，11]已经大大增加，基本上作为形式化方法的一个分支，基于它已经能够从其详尽的分析中提供的结果的模型。模型检查的主要用途是通过创建该设计的模型来验证设计是否正确，然后根据指定的属性检查模型的完整行为。模型检查器主要验证安全性和活性属性[12]，其中路由的可靠性属性是一个例子。然而，有一些模型检查工具可以分析具有时序和概率行为的模型[13];这些工具可以用于研究路由技术的性能吗？我们认为，概率模型检查器不太可能为分析路由协议性能提供有效的技术;对模型检查工具必须检查的行为空间（通常称为状态空间）大小的粗略计算表明了在5个节点的模型中，每个节点都是路由器，在所有链路都是双向的简化假设下，有10条链路。为了对主动链路状态单播技术进行建模，每个路由器将需要为每个链路保留至少一条信息，即它是上行还是下行。这意味着每个路由器在模型中至少有210个状态（10个链路中的每个链路有两个状态），因此5节点模型至少有（210）5或250个状态。这个简单的计算假设路由器能够相互独立地了解网络拓扑，或者对网络拓扑感到困惑。4一个包含250个状态的模型对于典型的计算引擎来说已经很难分析了，但这还不是故事的结束。这样的模型只能研究可靠性，因为它只有关于链接是向上还是向下的二进制信息。为了研究性能，我们需要做两件事：(i) 添加有关时间、通信延迟、拓扑变化率、链路质量等的信息。4在现实中，不同路由器的状态之间可能存在一些相关性，但另一方面，5个节点并不多！72I. Zakiuddin等人理论计算机科学电子笔记119（2005）67(ii) 将工具从安全活性验证器更改为时间和概率模型检查器。这两种变化都可能极大地增加状态空间。对这类问题的典型反应，来自正式验证社区，需要使用抽象技术。使用抽象使棘手的安全性验证问题变得易于处理是有趣的，有用的和公认的。然而，在使用模型检查器进行性能分析的领域中，使用类似的技术包含许多更深层次和更困难的问题。由于上面给出的原因，我们怀疑模型检查是否有能力满足我们的需求。然而，它可能是4路由器的模型可以通过模型检查器的性能属性进行分析，并且这种分析可以用于验证我们选择的方法，我们将在下面介绍。3路由协议的博弈模型博弈论[14]的发明是为了给冲突和竞争提供一个数学基础。它已经发展成为一个丰富的理论，拥有强大的数学和计算工具。 它还有一个好处，保持其直观的吸引力，这是它最初吸引我们的地方。两个见解使我们能够将这一理论和工具池转化为分析路由的潜在强大分析能力：(i) 路由协议可以被建模为网络和路由器之间的极大极小博弈。(ii) 博弈的极大极小值可以量化性能属性。为了解释这两个见解是如何使用极大极小博弈论来分析路由的基础，我们首先需要对我们将使用3.1极大极小对策的基本形式在极大极小博弈中，每个参与者选择博弈策略以最大化他或她的保证最小收益（因此称为极大极小）;用简单的语言来说，参与者试图使底线尽可能高假设我们在考虑一个两人博弈，在这个博弈中，每一轮，一个参与者有三个合法的行动选择。图1可能代表了这种游戏的前两步的可能选择;它是一棵树，其中每个节点代表游戏的状态，每个分支代表合法的移动I. Zakiuddin等人理论计算机科学电子笔记119（2005）6773参与人I移动1参与人II第二参与人I第三Fig. 1. 一个博弈两个国家之间这种结构被称为博弈树。游戏的运行是从根节点（表示初始状态）开始到叶节点（游戏结束）结束的游戏树路径因此，游戏的每一轮都对应于由两个玩家轮流选择的特定移动序列。在博弈树的叶子上评估成本函数它将游戏的每个完整运行其结果是一个特定参与者的成本，称为最小化参与者。游戏必须是零和的，这意味着另一个玩家（最大化玩家）的成本减去最小化玩家的成本正如它们的名字所暗示的，最小化的参与者试图最小化成本函数，而最大化的参与者试图最大化成本函数。当博弈树可以被充分探索时，极大极小策略将找到一条路径，保证每个玩家在其他玩家尽可能好的情况下获得最佳结果。[5]例如，考虑一个游戏，每个玩家依次走一步，每个人从两种可能的走法中选择图2显示了这种博弈的极大极小搜索的三个阶段。 阶段1显示了每个叶节点的成本函数值。第二阶段表明，在博弈树的左边中间层状态，参与人II（最小化参与人）会选择使结果最小化的移动;博弈将以结果2结束。第三阶段表明参与人II3.2将路由建模为博弈将路由建模为游戏背后的直觉是注意路由问题可以理解为网络和路由器之间的竞争从某种意义上说，这些路由器是在与一个试图以智取胜的网络竞争5当探索整个博弈树不可行时，成本函数有时必须 适用于截断运行;在这种情况下，它有效地判断游戏的状态，使用启发式的我们将在4.5节讨论这一点。74I. Zakiuddin等人理论计算机科学电子笔记119（2005）67最大化水平2最小化水平187287218721221静态评价第一阶段第二阶段第三图二. 工作中的极大极小算法他们路由器在“墨菲网络”中的表现如何？因此，我们正在考虑一个两个玩家，零和游戏，如上所述。6.要将任何东西建模为这样的游戏，我们需要：• 确定两个参与者及其初始状态，说明哪个是最小化参与者，哪个是最大化参与者;• 为每个玩家定义游戏的移动• 指定一个成本函数来量化最小化玩家的结果;最小化玩家选择移动来最小化这个函数，最大化玩家选择移动来最大化它。在博弈论的所有应用中，两个参与者都是一样的。所有路由器一起形成一个播放器，此后称为路由器集播放器;另一个播放器是链路集，称为网络播放器。路由器集合参与者的游戏动作本质上是执行路由协议。而对于网络玩家来说，游戏的招式就是改变网络的拓扑结构。这是我们将路由协议映射为博弈模型的基本见解;下面的部分将对此进行扩展，以更详细地描述映射。 成本函数取决于所研究的属性， 下面分别讨论每个属性一旦游戏被定义，游戏树就可以被构建和探索。最小最大策略搜索博弈树以找到最小最大路径;最小最大值（或最小最大结果）是应用于此路径的成本函数。最小最大值的含义可以解释为：在提供给博弈的约束条件内，如果路由器的行为是最优的，那么无论网络发生什么变化，路由器的行为都保证不比最小最大值差有了这些基本的直觉，我们可以更详细地思考如何利用博弈论来研究我们感兴趣的性质[6]这种映射不是唯一的;例如，可以构造一个n人博弈。I. Zakiuddin等人理论计算机科学电子笔记119（2005）67753.3目标稳健性在分析路由协议的可靠性时，目的是了解路由协议是否能适应移动网络，无论它如何变化。要把这变成一个游戏，我们首先要注意的是，如果路由器无法获得网络的正确视图，则网络可以被理解为获胜。 在我们的博弈论模型中，当网络停止变化，两个玩家中的一个获胜时，游戏结束。如果所有路由器都成功地获得了网络的正确视图，则路由器组获胜，如果路由器错误地判断了网络的状态并且无法纠正该状态，则网络获胜。游戏的成本函数可以被认为是一个成本谓词-“路由器在游戏的最终状态下具有正确的拓扑视图”。 我们从这种分析中得到的结果具有以下形式：• 如果谓词最终为真，则协议处理;或者• 如果断言保持为假，则无论路由器被给予多少机会来重新获得正确的视图，该协议都不能处理。3.4瞄准网络开销研究路由协议消耗的网络开销的目的是了解路由协议需要多少网络流量来应对不断变化的网络。回想一下2.2节，我们主要对比较路由协议感兴趣，因此我们使用的确切方法不如具有一致的比较基础重要。当路由器获得正确的网络视图时，游戏结束。因此，路由协议必须是可靠的，即，路由器必须始终能够在网络发生变化后进行恢复，这在上一节中有所描述。博弈的成本函数是路由器获得正确网络视图所需的流量的度量与对可靠性的调查不同，必须跟踪游戏每次运行时的网络流量，因此路径的成本取决于最终状态的完整路径。然后，可以生成图表，显示获得正确视图所需的网络流量，以及网络波动程度。根据我们比较路由协议的目的，从这个分析的结果采取的形式比较不同的路由协议的网络流量图。76I. Zakiuddin等人理论计算机科学电子笔记119（2005）673.5目标趋同在研究路由协议的收敛性时，目标是了解路由器的信念收敛到正确（或基本正确）的网络视图的速度。在这种情况下，游戏可以无限地继续。在实践中，只要我们对协议的行为有一个满意的想法，博弈的成本函数由路由器对网络的看法的正确性决定;路由器的看法越正确，路由器做得越好。成本函数还包括网络流量的度量，其用于在导致具有路由器视图的相同正确度的状态的移动之间进行选择;网络流量越高，路由器做得代价函数的网络传输部分取决于到达最终状态的完整路径，而（主要）正确性部分仅取决于最终状态。我们需要某种方法来衡量路由器对网络的看法的正确性我们有一个正确性度量，用于评估收敛性。此正确性度量值作为所有路由器的平均值计算。 图可以产生的显示（平均）的正确程度，在每个国家沿极大极小路径，对时间。同样，我们的主要关注点是比较路由协议，因此此分析的结果是不同路由协议的收敛图的比较。4一般映射问题4.1映射概述上一节概述了如何构建博弈来分析路由协议的各种属性。在本节中，我们先来看看定义映射的一般问题，然后再详细讨论每个分析问题的映射细节。为了研究路由协议的可靠性和性能，我们将博弈定义如下：(i) 代表所有路由器集合的路由器集合参与者是最小化参与者;代表所有链路集合的网络参与者是最大化参与者;在游戏的初始状态下，所有链路都断开，并且每个路由器都有正确的网络视图(ii) 路由器的原子移动是按照协议的规定发送其所有路由消息（此外，所有路由器注意到本地链路改变并处理接收到的消息）。网络的原子移动改变了I. Zakiuddin等人理论计算机科学电子笔记119（2005）6777一个链路从上到下或从下到上的状态。对于任何一个玩家来说，一个游戏移动都是一个（小）数量的原子移动;(iii) 成本函数是两个度量的字典式排序，其顺序如下：(a) 在路径的最终状态，路由器(b) 路由器使用的网络流量因此，网络玩家的目标是最大化成本函数，该成本函数记录了路由器对网络状态的困惑程度，以及它们使用了多少流量;路由器集合玩家的目标是最小化这个相同的函数。这里描述的字典序成本函数给出了3.3、3.4和3.5节中描述的三种分析类型的成本函数;特别是，当在路由器具有正确网络视图的游戏状态下评估成本函数时，可以忽略不一致部分我们已经描述了我们正在使用的基本映射，但是关于这个映射的具体实现方式还有很多问题;这些问题将在下一节中讨论。4.2建模问题由于我们考虑的是路由技术而不是特定的路由协议，因此我们首先分析了真实协议的低保真模型。 因此，我们被迫作出一些建模决策的映射路由协议的极大极小博弈。我们在这里描述最重要的问题。 在某些情况下，我们在每一次分析中都做出了相同的决定，而在某些情况下，我们发现有必要根据所进行的分析类型下面我们详细讨论以下建模问题• 用于决定发送哪些更新的标准• 更新数据的表示形式。• 距离矢量路由模型的详细信息。• 如何处理最优调度假设。• 博弈成本函数的精确形式我们必须做出的最重要的决定之一涉及路由器用于选择何时发送更新的问题是，是否对路由器进行建模，使其仅在响应网络变化时才创建和发送更新，或者是否应在不考虑网络是否发生变化的情况下发送更新（我们称之为这两个选项78I. Zakiuddin等人理论计算机科学电子笔记119（2005）67分别为“改变时输出”和“总是输出”）。在实际的路由协议中，很可能是两者的结合，根据网络状态的变化创建和发送更新，以及定期广播更新。然而，在这个阶段，我们已经决定使用一种方法或另一种方法，以简化建模。在每个分析部分中解释了所做的特定决定。我们所做的另一个建模决策涉及更新中包含的数据的表示。我们必须在将最新数据准确地表示为链路状态分组（LSP）或距离向量7和表示它们作为单独的链路状态更新或距离不太准确。那里是使用各个链路状态更新或距离的计算效率的原因，但是显然优选使用更精确的表示。我们稍后会解释我们在每一个分析中选择了哪个选项。我们必须做出与我们的距离矢量路由模型相关的决定，即路由器传输的距离矢量是否应该包括到节点的整个路径或仅仅是该路由上的邻居。同样，在不同的分析中做出了不同的选择;这些选择在适当的章节中进行了解释。我们必须解决的另一个问题是如何建模路由器的调度。所有的路由器一起组成了路由器集的参与者，它决定哪个路由器应该在每个原子移动中发送路由更新。 因此，我们假设路由器在全局控制器的控制下，可以实现最优调度。我们使用公平性约束来处理这个不切实际的最优调度假设。公平性约束对允许哪些路由器在游戏中的任何给定点执行原子移动施加限制。当我们说我们使用n+k公平性约束时，这意味着n个路由器中的每一个必须在每n+k个路由器的集合原子移动中至少执行一次路由器的集合原子移动。 （我们也可以通过说每个路由器必须在每n+k个路由器集合的原子移动中被调度至少一次来我们在适当的章节中指出了使用公平约束的地方另一个问题是游戏的成本函数到底应该由什么构成。在我们的分析中，一直使用函数的网络传输部分来表示发送的路由信息的数量。然而，我们发现有必要根据我们进行的分析类型来改变成本函数的不一致部分。取决于我们想要让路由器简单地说，链路状态数据包记录了网络中所有其他节点的状态;距离向量记录了网络中所有其他节点的距离I. Zakiuddin等人理论计算机科学电子笔记119（2005）6779为了正确地看待网络，我们改变了函数的不一致部分的形式，使其介于单个链接或距离的知识和整个网络的知识之间;在每个分析部分中解释了所做的选择。4.3一组路由器原子移动的详细说明网络的原子移动和游戏移动是（我们希望）合理清晰的。路由器组的游戏移动相当复杂，因此我们在这里详细阐述它们。本节对于理解该方法并不重要，因此读者可以选择跳到4.4节。在每个原子移动中，选择一个路由器（该选择由最小化记录不一致性和网络传输的成本函数的需要来确定）。假设选择了路由器n，则原子移动包括以下活动顺序：8(i) 每个路由器检查其本地链路的状态，并相应地更新其自己的这些链路的状态记录。9(ii) 每台路由器执行一些处理，如下所示：(a) 在链路状态路由中，每个路由器创建自己的LSP并将其放在其传出队列中（如“始终输出”模型所要求的(b) 在距离矢量路由中，每个路由器丢弃它从链路刚刚断开的邻居接收的距离矢量，并相应地重新计算自己的距离矢量。(iii) 路由器n执行广播，包括以下内容：(a) 在链路状态路由中，路由器n处理其保持队列上的LSP对于每一个，如果路由器n现在链接到LSP然后路由器n处理其输出队列上的LSP（第一次调度路由器时，该队列仅包含路由器n输出队列中的每个LSP被克隆多次，每个克隆对应于特定的目的地路由器，而不是n本身和LSP的发送方（如果与n不同）。为每个8.为了简单起见，让我们假设我们选择将更新表示为链路状态数据包或距离向量，并且我们正在使用[9]请注意，在链路状态路由和距离矢量路由中，所有路由器都至少维护其本地链路的状态记录;在链路状态路由中，路由器还维护网络其余部分的视图，而在距离矢量路由中，路由器还维护自己的距离矢量。80I. Zakiuddin等人理论计算机科学电子笔记119（2005）67克隆LSP，如果n链接到该LSP的目的地，则将LSP添加到要广播的LSP列表中，排除已经存在的任何重复LSP。如果n没有链接到LSP的目的地，则LSP被添加到n然后，列表中要广播的每个LSP被传递到其目的地。(b) 在距离向量路由中，路由器n向所有与它链接的邻居广播它自己的距离(iv) 已发送更新的所有路由器都会接收更新，并执行以下操作：(a) 在链路状态路由中，当路由器接收到LSP时，它会相应地更新其网络视图。然后，它将LSP放在其传出队列中，但前提是它的时间戳比传出队列中已有的任何LSP的时间戳都要新，并且来自相同的源和具有相同的目的地。(In反向路径转发，除非路由器认为LSP的发送方位于其自身与LSP源之间的最短路径上，(b) 在距离矢量路由中，当路由器接收到距离矢量时，它将其添加到其存储的距离矢量列表中，替换先前从同一邻居接收到的任何距离矢量。然后，它重新计算自己的距离向量。也可能发生“空”路由器集合原子移动。在这种情况下，没有路由器被调度，并且仅执行上面列表中的活动1和2。4.4执行我们实现了一个简单的Java工具，它使用上述映射来建模，作为一个极大极小博弈，三种不同的路由技术，即链路状态路由[9]，链路状态路由的反向路径转发（RPF）算法[17]和距离矢量路由[9]。该工具允许用户指定组成每个游戏移动的原子移动的数量。然后，它为该博弈生成博弈树，并根据极大极小算法搜索结果。该工具模拟了一个7节点网络，可以在几分钟内构建并完全搜索由12个原子移动组成的游戏树。很难将这种类型的有界深度优先搜索与模型检查器的完全深度优先（或宽度优先）搜索进行比较。 然而，这里所描述的方法产生了对状态空间远远超出I. Zakiuddin等人理论计算机科学电子笔记119（2005）6781任何模型检查器的范围。 搜索的速度得益于使用α-β修剪[18]和一些简单的对称性约简，但我们没有在优化搜索工具方面投入太多精力;它是一个粗糙而简单的原型。4.5分析的可追溯性我们能够用这种技术分析的网络规模比使用传统的模型检查技术可能要大得多。然而，博弈树的指数增长是一个严重的限制因素，在树中有多深，它是可能在一个合理的时间段内搜索。我们通过在游戏搜索工具中实现一个额外的功能来解决这个问题。这个工具允许我们执行游戏的递归运行，其中任何运行的初始状态（除了第一次）都是最终状态上一次跑步。这并不等同于对博弈树的完整搜索;相反，它使用启发式算法提供了对博弈状态的估计。这种技术使我们能够在博弈树中任意深度搜索5分析可靠性我们分析的第一个路由协议特征是可靠性。如果路由器可以被网络“击败”，那么路由协议肯定是不健全的。然而，反过来并不成立。网络的失败并不构成协议的验证，即使仅仅是对所建模的网络的大小进行验证;这与模型检查相反。要看到这一点，请记住，路由器集参与者充当全局控制器，决定在每次原子移动中哪个路由器应该发送路由更新这是前面提到的最优调度假设。这个假设的一个重要结果是，我们的技术目前是一个反驳程序：如果路由器组可以强制获胜，则路由协议仍然可以被吓倒，因为非最优调度顺序可能导致路由器失败;另一方面，如果我们的技术发现路由器组必须失败（即使在最优调度假设下），则路由协议存在真正的问题。5.1我们如何使用该工具当我们考虑如何使用我们的工具来分析一个路由协议，必须问的问题是：什么将真正构成网络的胜利，或者换句话说，82I. Zakiuddin等人理论计算机科学电子笔记119（2005）67在工具的输出中表现出不合理性答案在于成本函数的不一致部分。非零不一致性值表示至少有一个路由器在游戏中的该点无法获得网络的正确视图。可以预料的是，路由器在游戏过程中有时会对网络状态感到困惑。然而，如果一个路由协议被认为是合理的，那么人们会期望，如果在任何时候，网络被固定在任何特定的状态，每个路由器最终都应该收敛到至少它所在的网络分区因此，我们观察到，如果路由器根据某些特定的路由协议进行行为，则可以找到游戏的状态，其中至少一个路由器无法在游戏结束时重新获得（不再改变的）网络的正确视图，那么该协议可以被认为是不健全的。我们认为这是网络的胜利10我们进行了一些实验，两个路由协议，即链路状态RPF和距离矢量路由。我们为该工具提供了不同数量和组合的网络和路由器组原子移动，试图为网络找到胜利，即路由器变得无法挽回的混乱的情况。我们的结果详述如下。5.2决定成本函数的不一致部分为：• 对于链路状态路由，节点0和节点1之间的链路的可信状态的正确性;• 对于距离向量路由，到节点0和到节点1的所相信的距离的正确性。消息采用单独的更新和距离的形式，而不是数据包和向量，我们使用“变化时输出”模型。我们不使用公平约束。表1总结了这一信息。5.3结果我们首先考虑链路状态RPF算法。然而，该工具无法在该算法中找到任何错误，因此为了验证我们的方法，我们调整了模型，以便：• 算法是错误的，或者[10]我们使用了有界深度搜索，这将在第8节中讨论。I. Zakiuddin等人理论计算机科学电子笔记119（2005）6783• 单个路由器可能会表现不正确。在这两种情况下，游戏搜索都找到了网络击败路由器组的方法。然后我们研究了距离矢量路由。众所周知，在路由社区中，距离矢量路由以其最简单的形式出现在计数到无限问题[9]中，路由器可以无限地转发数据包，这通常是因为对网络状态的错误局部信念。(For例如，路由器A可能认为到C的最短路由是通过下一跳B，而B认为到C的最佳路由是通过A。）在这种情况下，该工具报告说，网络可以强制获胜，因此我们能够得出结论，这种混乱最终可能会出现。对在通往极大极小解的路径上所达到的状态的检查显示，计数到无穷大是可能的，这是我们对特定初始状态和建模的操作假设所没有预期的同样，该工具发现了一个即使对于距离矢量路由的Split Horizon [9]变体也会发生这些实验验证了我们的方法;它们提供了证据，证明该工具能够发现令人惊讶的行为。6分析网络开销我们认为，游戏搜索的工作，研究健全本身是新颖和有趣的，但我们的兴趣极大极小搜索的基础上，了解路由大大增加时，我们意识到如何使用游戏搜索研究网络开销。6.1我们如何使用该工具简单的观察是，路由器和网络之间的博弈计算的极大极小值回想一下，我们使用的成本函数记录了路由器发送的路由更新数据包的数量。如果我们计算出路由器需要多少个更新数据包才能获得正确的网络视图，那么我们就有了一个性能度量。该成本函数将每个路由更新数据包视为具有相同的成本，并且它假设统一的链路质量。即便如此，它也提供了一个基本的衡量标准，衡量支持路由需要消耗多少网络资源。请注意，我们现在需要在整个路径上的博弈状态下评估成本函数，而不仅仅是在路径的最终状态这一点--84I. Zakiuddin等人理论计算机科学电子笔记119（2005）67从我们在将稳健性分析映射到博弈时使用的成本函数中猜测它。人们普遍认为，RPF消耗的网络开销比路由更低（实际上，对算法的检查表明，情况可能是这样）。然而，我们未能在文献中找到卢旺达爱国阵线节省经费的任何分析数字根据我们严格分析路由技术的目标，我们使用博弈论分析来量化RPF所实现的节省。我们还使用这些技术来调查距离矢量路由所需的网络开销。每个游戏都对特定的初始状态进行编码，并对每个玩家移动中允许的连续原子移动的数量进行约束。因此，对工具提出的所有问题都是关于特定的初始状态和特定的移动约束的。该工具用于确定需要多少个路由器集合的原子移动以在每个连接的节点处实现关于特定链路的状态的正确信念）。在整个游戏过程中，定期测量所需的路由传输6.2决定成本函数的不一致部分的选择受计算效率考虑的影响 如果期望所有路由器在每一组路由器移动之后获得整个网络的正确视图，那么将需要在树中非常深地搜索，这将在计算上变得因此，我们将成本函数的不一致部分设置为用于合理性分析的不太严格的选择;如下所示：• 对于链路状态路由，节点0和节点1之间的链路的可信状态的正确性;• 对于距离向量路由，到节点0和到节点1的所相信的距离的正确性。消息采用单独的更新和距离的形式，而不是数据包和向量，我们使用“变化时输出”模型。我们已经产生了结果，使用和不使用公平约束。11表1总结了这一信息。[11]我们还使用“始终输出”方法构建了一个模型I. Zakiuddin等人理论计算机科学电子笔记119（2005）67855个路由器，无限制1401201008060402000 5 10 15 20 25 30游戏移动图3.第三章。RPF法与反渗透法的对比6.3结果图3显示了为重新获得正确的网络视图而进行通信的总路由流量如何随着移动次数的增加而变化。在图3中，RPF消耗的网络开销比RPF消耗的网络开销明显减少，但我们对所显示的微小改进感到惊讶经考虑，我们认为小间隙可能是人为因素我们映射到一个博弈我们假设责任在于路由器集合玩家必须调度各个路由器的（不现实的）完全控制。直觉是，如果从路由器集玩家中移除一些不切实际的权力，则更有可能展示出现实的结果，在这种情况下，选择为每个原子移动调度哪个路由器的不受约束的权力（事实上，如果路由器拥有良好的消息，而不是使用RPF，则可以完全控制何时调度路由器的路由器集播放器可以更好地利用这种能力：路由器集播放器可以选择以与运行RPF时最佳调度相同的顺序来调度它们，从而最小化非RPF通信。当然，在现实中，路由器在类似的负载下并发地并且经常在类似的处理器上操作，因此它们可以被认为以类似的速率被调度。 这向我们表明， 如果路由器集合被约束为以公平的方式被调度。因此，如第4节所述，我们选择制定公平性约束，要求每个路由器在任何n+k个连续的路由器集合原子移动序列中至少被调度一次，其中n是路由器的数量，k是表征公平性程度的数字。溢流RPF网络流量86I. Zakiuddin等人理论计算机科学电子笔记119（2005）675台路由器，n+2限制5004504003503002502001501005000 5 10 15 20 25 30游戏移动图四、公平约束下RPF与随机编码的传输性能比较我们通过扩展工具来测试我们的假设，以允许执行这种公平约束。然后，我们生成新的图对，并强制执行不同程度的公平性。图4显示了5个路由器必须以7个路由器集合的原子移动的任意顺序被调度的情况的图形。正如假设的那样，结果表明，RPF消耗的网络开销比没有公平性约束时减少得更多。我们通过测量距离矢量路由消耗的开销来结束我们对网络开销的调查。这是困难的，直接com-court的距离矢量路由与我们以前的结果，链路状态路由，各自的成本函数的不一致的部分，由必要性，不同的结果。尽管如此，我们的距离矢量路由结果（有和没有公平性约束）显示在图5中。7分析收敛性在我们对可靠性和网络开销的分析取得了一些成功之后，我们的注意力转向了2.2节中提到的路由协议的一个剩余属性，即收敛性。7.1我们如何使用该工具人们普遍认为，链路状态路由比距离向量路由收敛得更快，并且链路状态路由比链路状态RPF收敛得更快[9]。然而，我们亦未能就此作出任何定量分析。我们认为博弈论可以有效地应用于溢流RPF网络流量