一种 MCKite:-种面向命名数据网络的多生产者多播新机制

作者：张毅  

  本文提出一种面向NDN的多生产者多播支撑机制-MCKite。MCKite基于之前提出的一种面向NDN的移动支撑机制-Kite，利用Kite的interest追踪机制来实现生产者间成员的发现以及协作生产者之间、消费者与多生产者之间的mterest多播。MCKite的主要思想在于通过集会( rendezvous)机制利用PIT转发信息来追踪生产者，使得生产者的拓扑位置对其他生产协作者及消费者透明，进而无需事先建立或更新路由／转发表。对每个多播实例只需建立一个集会点或利用一组公共集会点基础设施，生产者通过发送注册mterest消息即可加入多播组并建立从集会点到生产者的反向路径，生产者之间通过以集会点为根的双向转发树建立多播信道。作为MCKite的一个概念证明和应用示例，在ndnSIM上实现了一个改进的Sync协议-MCKiteSync，该协议实现了分布式多生产者间数据同步以及数据多播分发。

    MSM-IP指出支持多播与支持移动是类似的，这也表明了MCKite与Kite的相似性，但与面向移动环境的Kite相比，MCKite的主要特点在于假定生产者拓扑位置相对稳定，进入了一种新的循迹前缀匹配方案，增加了多生产者间的双向转发树(bidirectional forwarding tree，BFT)建立和更新机制，通过硬状态转发来降低不必要的信令开销。参考文献均基于位置建立路径，前者根据interest中位置信息重定向，后者通过向原位置发出请求建立轨迹，而MCKite则是一种与位置无关的方案。MCKite的双向转发树机制与BIDIR_PIM和CBT类似，都独立于特定的底层单播路由，在多源情境下具有良好的可扩展性。但MCKite与它们分别面向不同的体系结构，得益于NDN自身具备的无环路转发特性，MCKite不需要像BIDRI-PIM那样来实现指定转发器的选举或者反向路径转发检查，这一特性极大降低了MCKite的复杂性。DCR提出一种支持任播的可扩展路由方案，或许可以与MCKite结合以支持多个集会点。

2  MCKite原理与方案

2.1  NDN转发与多播原理

    一次典型NDN通信过程如下：消费者发送一个包含数据名字的interest消息，路由节点以数据名字为目标，根据转发信息库(forwarding information base，FIB)向下一跳转发消息，同时在PIT中记录mterest消息及其人口，直到interest消息到达生产者。生产者应答一个包含相同数据名字前缀的data消息，路由节点根据之前PIT中记录反向转发data消息直到消费者，同时路由节点可以将data内容缓存在内容库(content store，CS)中。这种“撒面包屑”式的反向路径转发机制使得mterest和data消息中路由／转发信息只有数据名字本身，不包含消费者标识或位置，也不要求包含生产者拓扑位置，尽管通常数据名字前缀作为唯一寻址信息也意味着生产者位置。

    当多个消费者向单个生产者请求数据时，形成单生产者一多消费者多播。单生产者的可达性通过单播路由实现，即由单播路由协议以数据名字为目的计算路由并填写FIB。当消费者在较近时间间隔内发送多个相同interest消息，进入同一个路由节点时，只有第一个interest消息被转发，后续消息会被抑制，但仍会被记录在PIT中。PIT记录构成了以生产者为根，连接到消费者的一棵多播树，此后data消息将沿此棵树上反向路径返回。若data消息被中间节点缓存，则此后相应的interest消息在到达该中间节点时就将获得data消息，而无需从生产者处重新获取数据。可见,NDN转发机制直接支持单生产者一多消费者多播，无需像IP那样需要额外的多播协议来实现。

2.2  多生产者多播方案MCKite原理

    当多个生产者分布式协作生产数据时，消费者需要获得来自全部生产者的数据，形成多生产者多播。一个典型多生产者应用情景是Sync协议，即多生产者间数据同步。由于当前NDN体系结构中，interest转发依赖于路由层构造的FIB,不同于单生产者多播中利用单播路由协议构造FIB．多生产者多播路由面临两个问题：可扩展性，即随着生产者规模扩大，由生产者加入和退出所带来的组结构扰动加剧，基于单播路由的机制将增加路由层负担；组成员发现，即生产者之间如何彼此发现，或者说如何避免泛洪实现彼此间消息定向发送。

    针对多生产者多播应用中存在的问题，MCKite提出基于集会与interest循迹转发的支撑方案。该方案可以看作之前提出的NDN移动支撑方案_Kite的多播版本。与Kite相似,MCKite中每个多播组需要一个集会点，集会点发出相关数据名字前缀路由声明，通过单播路由实现全网到集会点自身或数据名字前缀的可达性。MCKite通过集会点使来自不同生产者和消费者的interest可到达同一网络位置，这些interest消息在PIT中留下的踪迹构成了从集会点到多播成员的单向路径树。

    interest循迹转发是Kite引入NDN转发面的一种转发机制，该机制受data消息转发机制启发，使得一个interest消息可沿PIT中另一个interest消息反向路径转发，其中前一个interest消息称作“循迹interest”，后一个interest消息称作“被循迹interest”。一个生产者发送的被循迹interest消息经过中间路由节点转发在PIT中形成反向路径，其他生产者或消费者发送的循迹interest消息利用interest循迹转发机制沿该路径到达该生产者。一个interest消息可以既是一个循迹interest．也是一个被循迹interest。两个相互循迹的interest消息在相遇后将沿着彼此的反向路径转发。通过与集会模式的结合，从集会点到多播成员的单向路径树就转变为组成员之间的双向路径树，组成员间的interest消息会相互循迹，从而实现生产者间多播。

    为实现interest循迹转发，MCKite继承了Kite在interest消息中引入的两个新字段：TraceName域，即循迹interest消息中所包含的被循迹interest消息的数据名字；Traceable标记，即该interest消息是否可以被其他interest追踪，若置1．则可被追踪，否则禁止追踪。MCKite舍弃了Kite引入的TraceOnly标记。MCKite也继承了Kite在PIT中加入的两个新表：循迹转发表(trace forwarding table，TFT)．包含所有Traceable标记置1的被循迹interest}肖息；循迹名字表(trace name table，TNT)，包含所有带有TraceName域的循迹interest消息。

    MCKite引入一种新的interest循迹前缀匹配方案，在可区分来自不同生产者的interest消息的同时，令循迹interest消息可以被多播到所有生产者。该方案把循迹interest消息的TraceName蜮T作为被匹配前缀，以被循迹interest消息的名字N来前缀匹配TraceName域，即若T为N的前缀，则匹配。这样，一个循迹interest可以匹配多个名字不同的被循迹interest。

2.3 MCKite转发方案

    以上述新添加的interest消息字段、改造的PIT数据结构和新循迹前缀匹配方案为基础，MCKite转发算法如下所示：输入一个来自接口I的interest I；输出一个interest/data转发操作列表Oplist，push A、B操作表示将消息A通过接口B转发。第(1)~(5)步为标准的interest转发流程，即从cs中取得data，否则将I加入PIT；第(6)~(10)步，若Traceable置1，则I被循迹，将TFT中记录的每个追踪I的interest J通过F转发；第(11)~(16)步，若Tracename不为空，则I循迹，根据TNT将I转发向所有被循迹interest的人口；(17)~(20)步，根据FIB转发I，算法结束。

    算法1：MCKite  interest转发算法

    输入：I通过接口I进入路由器

输出：一个转发操作列表oplist

2.4 MCKite双向转发树方案

    下面描述基于算法1的MCKite BFT建立、维护和更新机制。设一次多播会话存在一个单播路由可达的集会点R，R声明一个可路由名字前缀，例如/SyncGroupl。为易于算法描述，下面给出任意两个组成员N和M间以R为根节点的双向路径，超过两个成员的双向转发树的建立原理相同。其中，假设N先发送一个用于加入组的interest消息，  例如interest名字为/SyncGroupl/Join/Memberl，TraceName为/SyncCroupl/Join，Traceable标记置1。算法如下所示：输入集会点R，组成员N和M;输出N和M间在PIT中的双向转发路径，该路径建立通过insert INTO PIT操作实现。第(1)~(6)步，生产者N发送interest I，根据单播路由从N到达R，并在中间路由器上的PIT表中留下踪迹，建立了从N到R的路径；第(7)~(15)步，生产者M发送interest J，根据单播路由从M到达R，若在R或中间路由器上I和J相遇，则根据lnterest循迹转发机制，I和J互为被循迹mterest，分别通过对方的入口转发，并最终到达生产者，形成了从R到M的路径以及从M到N的路径。此时，加上之前从N到R的路径，形成了从M到N的双向路径。类似的，当生产者规模超过2个时，新生产者发送的注册interest将多播转发到集会点和已有成员，由此形成了以集会点为根的BFT。不同于Kite中interest在PIT中以软状态保存，MCKite中注册的interest在PIT中为硬状态，无需周期发送新注册消息。

    算法2:MCKite双向转发树建立算法

    输入：集会点R，组成员N和M输出：隐含在PIT中形成的M和N间双向转发路径

    当一名生产者成员欲退出时，该成员先发送退出interest消息，例如/SyncGroupl/Leave/Memberl。集合点在收到退出消息后，通过发送一个退出data消息/SyncGroupl/Join/Memeberl/Leave．  将之前的注册interest消息／SyncGroupl/Join/Memeberl沿着从集合点到该生产者路径上的PIT中清除，同时发送一个退出应答data消息／SyncGroupl/Leave/Memberl通知该生产者已收到退出请求。此后，由于从集会点到该生产者的转发路径已经被清除，即BFT上通往该生产者的分支被剪掉，其他循迹interest消息将不再被转发到该生产者，实现了成员退出和BFT更新机制。

3  实验结果

    从两方面对MCKite性能进行评价：一方面，从路径延展度进行度量，与经典的PIM对比：另一方面，从流量消耗进行度量，实现MCKite。本实验采用Rocketfuel测量的不同ISP的路由器级网络拓扑。

3.1  延展度

    延展度指真实路由路径长度和最短路径长度的比值，其反映了路径被拉伸程度，延展度越低说明路径长度越接近最短路径。下面分别讨论3种不同情况下多播成员间通信路径延展度。

    (1)不同网络拓扑

    采用9个ISP网络拓扑进行实验。每次实验随机选择一个节点作为多播集会点，并选择30%节点作为多播成员，成员之间相互通信并统计实际路径，同时计算成员间的最短路径。图1为不同拓扑下平均路径延展度。虽然各网络拓扑路径延展度略有差异，但整体上MCKite路径延展度比PIM低近20.6%，其中MCKite的平均路径延展度为1.46～1.82．而PIM平均延展度为1.76～2.37。其主要原因在于MCKite采用循迹转发机制，多播成员间可能无需到达集会点就可通过循迹找到更短的捷径。

    此外，MCKite循迹转发机制还可尽可能降低由于距离很近的两个多播成员通过集会点通信产生的高时延。在AS1221中，PIM通过集会点通信造成约7.99%的路径延展度大于3，而通过MCKite循迹转发捷径，延展度大于3的比例下降到0.85%。同时MCKite最短路径比例比PIM高10010左右。

    (2)不同多播规模

    选定AS1221作为网络拓扑，随机选择一个节点作为固定集会点，依次随机选择loo/o～500/o的节点作为多播成员。图2显示．MCKite平均路径延展度依然优于PIM。同时，对于两种多播方案，随着多播成员增加，平均路径延展度略有增长。其主要原因可能在于集会点未处于网络中心，当多播成员增加时，离集会点较远，节点增加较多。其中．PIM增长幅度为7%．大于MCKite的5%，可见多播规模对MCKite的影响小于对PIM的影响。

    (3)集会点选择

    以AS1221作为网络拓扑，随机选择30%节点作为多播成员，根据节点度大小将节点划分为多个区间，每次从不同区间中随机选择一个节点作为集会点。图3为不同集会点平均路径延展度，MCKite和PIM平均路径延展度整体上都随节点度增大而下降。主要原因在于节点度越小，节点可能越接近网络边缘，使得多播成员到集会点距离大大增加，而节点度越大则越靠近网络拓扑中心，缩短了多播成员到集会点的距离。其中，PIM平均路径延展度下降幅度为36.40/0，而MCKite则能维持一个较低延展度，下降幅度仅为20%，可见集会点的选择对MCKite延展度的影响较小。

3.2流量消耗

    在rldriSIM上实现了MCKite并将其应用于一个多生产者间数据同步的应用情景，在AS1221拓扑下考察不同多播规模下流量消耗，平均每4s产生一个新数据，相同规模下模拟50次，每次模拟运行时间20 s，实验结果如图4所示。随着多播规模增长，流量消耗呈线性增长，远远低于泛洪的代价。

4结束语

针对未来网络体系结构NDN中多生产者多播问题，本文提出了一种基于集会模式和寻踪转发的多播方案MCKite。该方案利用集会点作为双向转发树根，利用PIT中interest踪迹实现通往生产者树枝，并提出一种新的interest循迹前缀匹配方案实现树的剪枝。MCKite方案不仅复杂性低，而且实验表明，MCKite在路径延展度上优于以往方案，且随多播规模增长，路径延展度和流量消耗的可扩展性都较好。

5摘  要：命名数据网络(named data networking,NDN)作为一种未来网体系结构，以命名数据代替主机作为网络层的核心对象，直接支持单生产者一多消费者多播应用模式。然而，NDN对于多生产者应用支持仍然是一个开放问题，为此提出一种多生产者多播支撑机制-MCKiteo MCKite通过集会机制利用挂起兴趣表(pendinginterest table，PIT)中状态来建立通往生产者的路径，使得生产者拓扑位置对其他生产协作者及消费者透明，进而无需事先建立或更新路由表，降低了协议复杂性。将MCKite应用于多生产者数据同步协议并在ndnSIM上实现。实验表明，与以往方案相比，延展度更低，流量消耗更少。