基于Overlay Network协同选播通信机制的研究

张园园

摘 要：应用层选播因不了解物理网络拓扑而缺乏高效性，网络层选播因不了解服务器本身的负载而缺乏灵活性。在充分发挥应用层的灵活性和网络层的高效性的基础上，提出了基于Overlay Network的协同选播网络体系结构，给出了覆盖层的构造方法，并从域内和域间两方面对协同选播机制进行了阐述，最后利用Petri网理论对相关机制进行了形式化描述，且对其正确性和完备性进行了验证。

关键词：Overlay Network；协同选播机制；负载均衡；Petri网

中图分类号：TP393.09 文献标识码：A DOI：10.15913/j.cnki.kjycx.2016.05.020

选播Anycast（one-to-one-of-many）是在面向下一代网络时，为了解决负载均衡和提升服务可用性而提出的。一个选播地址标识不同节点的多个网络接口，如果一个报文被传送到一个选播地址上，那么它最终被传送到具有该地址标识的、根据路由协议距离度量“最近”的一个接口上。

传统的选播服务是在应用层或网络层上实现的，在网络层上实现选播具有低时延和低开销的优势。但是，由于网络层不了解提供选播服务节点的信息和负载状况，可能会选择一个负载过重的节点来为用户提供服务，这样反而降低了选播通信的效率；应用层则通过外部实体来实现选播，很容易了解到服务节点当前的状态和负载信息，可以非常便捷地选择一个相对空闲的服务节点来提供服务。但是，由于应用层不了解底层网络拓扑信息，所选出的节点很可能距离用户很远，这样反而不利于其灵活性优势的发挥。现有的一些研究已经开始考虑在应用层实现选播时加入反映物理网络的因素或者在网络层加入反映服务节点信息的因素，继而出现了许多新型网络架构。尽管如此，应用层和网络层的关系仍没有达到合理的协调。为此，本文提出基于Overlay Network的协同选播网络体系结构，将应用层和网络层各自的优势很好地结合起来，以期提高选播服务的质量，达到大规模部署和应用的目的。

1 基于Overlay Network的协同选播网络体系结构

为了充分发挥应用层的灵活性和网络层的高效性优势，并且实现协同选播，本文提出了基于Overlay Network的协同选播网络体系结构。这一网络体系结构的建立，需要在应用层和网络层之间构造虚拟的协同选播覆盖层。考虑到实际可行性等因素，本文提出基于选播服务域层—汇聚层的分层协同选播覆盖层模型。图1所示为协同选播Overlay Network拓扑结构模型。

为了更好地实现协同选播，使用户节点都能与其距离最近、最优的选播服务节点通信，同时解决选播存在的交错服务问题，对网络中的节点重新进行了划分，提出了一种以选播服务器节点为中心的区域划分方法，并将划分后的区域称为“选播服务域（Anycast Service Domain，ASD）”，在每个域内可能存在一种或者多种类型的选播服务。

在每个选播服务域内，通过提取选播服务节点和选播路由器，并部署一定的选播代理节点来共同构成底层的覆盖层，即选播服务域层。选播代理节点负责管理应用层选播服务器节点的状态信息，选播路由器负责获取网络层的拓扑信息。在选播服务域内，将选播代理节点与能够获得网络层物理拓扑的选播路由器协同起来完成域内协同选播。

在每个选播服务域内选取一个域头节点（Domain Head，DH）来收集自身选播服务域内的信息，并对其进行管理。为了防止域头节点发生故障，在每个选播服务域内选取部分性能相对较高、运行稳定的选播服务代理节点，并随机选取两个节点分别作为域头节点和后备节点。将域头节点和选播服务域层的选播路由器提取出来，通过虚拟链路构成域间覆盖层，也就是汇聚层。在汇聚层，将域间获得的物理拓扑信息的选播路由器与应用层服务域状态信息的域头节点协同起来共同完成域间协同选播。

综上所述，基于Overlay Network的协同选播覆盖层的构造过程体现了分层的思想。覆盖层的底层是由选播服务器、选播路由器和选播代理节点共同构成的选播服务域层，顶层是由各个选播服务域的域头节点和选播服务器共同构成的汇聚层。

2 协同选播服路由机制

基于Overlay Network的协同选播体系结构从域内和域间两方面提出了协同选播机制。在对协同选播服路由机制进行阐述之前，需引入以下几个概念：①选播服务节点。它是指能够提供选播服务的节点。将提供同一类服务的节点构成一个选播组，其中的节点称为选播组成员，这些节点共享一个Anycast地址。②服务节点利用率。它是指节点负载与承载能力的比值。节点的承载能力是指其综合处理能力，可以根据这个指标有效均衡服务器的负载。③协同服务域。它是指提供同一种选播服务的节点所在的选播服务域的集合。④服务域利用率。它是指选播服务域内所有提供同类选播服务的节点的总负载与总承载能力的比值。根据服务域利用率，可以在选播服务域之间进行负载的均衡调整。

对于一个选播服务节点而言，可能提供的服务类型是多种类的，对应多个Anycast地址，且分属于不同的协同服务域。将基于Overlay Network的协同选播覆盖网中所有的选播服务域根据服务类型划分成不同的协同服务域来提供选播服务。这样，既充分发挥了网络层的高效性和应用层的灵活性，又节约了在每个选播服务域内的查找时间，提高了选播服务的效率。

图2所示为基于Overlay Network的协同选播机制模型，其中，图（a）所示为协同选播机制的模型（从域内角度和域间角度来看），图2（b）所示为协同选播机制服务过程。假设整个网络有7个选播服务域，即Domain1～Domain7，共存的三类选播服务分别为A，B和C.其中，能提供同一类服务的构成一个协同服务域，而Domain6可以同时提供A和B两类服务，因此它分属于两个协同服务域。如果Domain1、Domain3、Domain6和Domain7内都存在能提供A类选播服务的节点，当一个用户发送选播请求要获得A类服务时，基于Overlay Network的协同选播机制就要在所有能提供此类服务的域内。也就是说，可以在由A类服务构成的协同服务域内找到相对于此用户最优的选播服务节点和到这个节点的最优路径来提供选播服务。同理，Domain4、Domain5和Domain6构成B类选播的协同服务域，Domain2和Domain3构成C类选播的协同服务域。

（a）协同选播服务机制的模型图

（b）协同选播机制服务过程示意图

3 基于Petri网的协同选播路由机制验证

Petri网是一种数学和图形化工具，具有准确的语义定义，并且直观、易用。Petri网的概念是于1962年德国科学家Carl Adam Petri提出的，主要用于对异步并发机制的描述。从形式上看，Petri网的结构就是一个没有孤立节点的有向二分图，它为描述异步并发关系提供了丰富多样的分析手段。鉴于此，本文采用Petri网的形式化描述语言来描述基于Overlay Netwrok的协同选播机制，并对其正确性和完备性进行验证。

3.1 描述

根据基于Overlay Network的协同选播服务机制，得到图3所示的Petri网模型。这里只分析服务请求节点和代理节点、选播路由器和域头节点的交互情况。由于对于任意一个用户或者机制中任意一个节点而言，工作过程是完全相同且相互独立的，因此，对于整个系统而言，只要一个用户节点在本系统中的运行是正确的，那么该机制就是正确的。在存在多个服务请求节点的情况下，库所P0的初始标记个数和容量为用户节点的总量，但整个Petri网的性质无任何变化。另外，域头节点与其他代理节点的细节行为对本地用户发送服务请求、协同选播路由和应答请求的整个机制没有影响，因而，为了简化Petri网，没有描述这些实体的细节行为。

务，T6 和T7的触发取决于该类型的选播协同服务域能否提供此类选播服务，T10、T11 和T12的触发取决于选播运行过程中是否会出现服务器故障或者链路断开的情况，T13和T14、T15和T16、T17和T18的触发取决于选播服务节点或者选播服务域是否发生过载。表1所示为Petri网库所和变迁的定义。

3.2 验证

虽然库所变迁图能够直观地显示基于Overlay Network的协同选播机制中实体间的交互，但是，多个实体间复杂的异步交互过程可能会产生无法预料的后果。因此，本文进一步采用Petri网分析方法对此机制的正确性和完备性进行验证。

本文对Petri网系统的正确性和完备性的验证采用可达图法。基于可达图的列举法是通过构建系统可达图，展现每个网和它们之间的单个变迁的发生过程。如果Petri网系统是有界的，则对应的可达图就是有限的，并且其各种性质极易被证明。我们采用可达图法构建图3所示的Petri网系统的可达图，得出如图4所示的基于Overlay Network协同选播过程的Petri网可达图。借助可达图，可以从理论上验证系统的正确性和完备性。该可达图包含了系统在初始条件下所能达到的所有系统标识和系统变迁序列。

图4中，带有下划线的状态表示与初始状态重合形成圈，为了清楚起见，没有直接用弧连接。基于Overlay Network的协同选播机制的正确运行包括以下几种情况：①选播请求用户在本地选播代理节点找到了选播服务成员，然后将选播服务节点的信息返回给用户，两者开始通信，在Petri网中的变迁实施序列为（T0，T2，T13，T8，T10）。如果当前选播服务节点发生故障，则可通过域内路径进行动态调整，将选播服务重新定位到新的服务节点。此时的变迁实施序列为（T0，T2，T14，T8，T10）。②用户在本地选播代理节点未找到此类选播服务，则本地代理节点将请求发送给其他代理节点，域头节点在本选播服务域内进行服务查找，在Petri网中的变迁实施序列为（T0，T1，T3，T15，T5）。如果当前服务节点发生故障，则域头节点在该选播服务域内进行动态调整，为用户重新选择节点，在Petri网中的变迁实施序列为（T0，T1，T3，T16，T5）。③域头节点在本选播服务域内未找到合适的选播服务节点，则它将消息发送到协同选播服务域的其他域头节点，根据域间最优路径，选出

一个服务节点返回给用户。此时的变迁实施序列为（T0，T1，T4，T6，T17，T9，T12）。如果通过协同服务域间所选的服务节点或者链路发生故障，则通过路径动态调整将选播服务请求重新定位到新的服务节点，在Petri网中的变迁实施序列为（T0，T1，T4，T6，T18，T9，T12）。

由此可见，上述变迁序列均在图4所示的可达图中出现，且分别位于初始状态节点下的不同基本圈中，说明这些变迁序列是可反复无限次实施的。同时，从图4中还可以发现，所有可能状态从初始状态开始都是可达的，且都处于不同的基本圈中，因此，不可能出现死锁，也不会出现死循环，进而得出系统的各种行为逻辑都是正确的。各库所的Token 数量均不超过1，因此Petri网是有界的，从而保证了系统资源的有限性。在多个用户请求资源的情况下，由于用户每次只能提交一个资源请求，即库所P0 的初始Token 数量及其容量均限定为1.由于各弧的权重均为1，只要用户数量有限，各库所Token 的最大数量也不会超过用户数量，因此，系统是有界的。由以上分析可知，所有变迁序列一定会发生变化，且由Petri 网的有界性保证了资源消耗的有限性，因此，系统模型是正确的。另外，从可达图还可以看出，系统不论处于何种状态，都能返回到初始状态，而其所有变迁均可无限次触发，因此，系统不会无限制地陷入某种局部循环状态，也无“饥饿”现象出现，更不会发生死锁或活锁。同时，Petri网系统的可达状态均是合理、有效的，因此系统模型是完备的。

4 结论与展望

本文在充分发挥应用层选播的灵活性和网络层选播的高效性的前提下，提出了基于Overlay Network的协同选播覆盖网络体系结构，在此基础上，提出了基于Overlay Network的协同选播服务机制，并对协同选播的过程进行了详细描述，最后利用Petri网理论对协同选播机制进行了形式化描述，通过Petri网可达图对系统模型的正确性和完备性进行了验证。

参考文献

[1]Jun zhi，Jianyong Liu，Kai chen.Coures Optimization on Based on Improved Immune Genetic Algorithm[J].Computational Sciences and Optimization，2009（2）.

[2]尹海卫，王庆生.利用anycast技术实现MANET与IPv6网络互联[J].计算机应用与软件，2013，30（3）.

[3]张燕梅.基于覆盖网络的服务组合关键技术研究[D].北京：中国矿业大学，2009.

[4]F.Y.Wang，YGao，M.C.Zhou.A modified reachability tree approach to analysis of unbounded Petrinets[J].IEEE transactions on systems，man and cybermetric-Part B：metrics，2004，34（1）.

[5]鲁法明.Petri网的可达性分析的代数方法[D].泰安：山东科技大学，2007.

[6]曹阳，张维明，沙基昌，等.Petri网在通信网络仿真建模中的应用[J].计算机仿真，2001（5）.

[7]Angela Adamyan，David He.Sequential Failure Analysis Using Counters of Petri Net modes[J].IEEE Transaction on Systems，Man and Cybernettics-Part：Systems and Humans，2003，33（1）.

[8]P.Ramachandran.A sufficient condition of reachablitiy in a general Petrinet[J].Discrete event dynamic： theory and applications，2004（14）.

[9]王德志，余镇危.基于Petri网的PIM-SM协议建模与分析[J].计算机工程与应用，2007，43（3）.

〔编辑：刘晓芳〕