组播路由协议

组播路由协议（共8篇）

组播路由协议 篇1

随着网络技术的发展,网络传输和处理能力的大幅提高,网上应用业务越来越多,特别是多媒体压缩技术的发展和成熟,使得依靠网络进行视频会议、视频点播(VOD)、远程可视监控等视频信息传输业务成为网络上重要的业务之一。在网络上实现的视音频信息业务和一般业务相比,有着数据量大、时延敏感性强、持续时间长等特点。因此采用最少时间、最小空间来传输和解决视音频业务所要求的网络利用率高、传输速度快、实时性强的问题,就要采用不同于传统单播、广播机制的转发技术及Qo S服务保证机制来实现,而IP组播技术是解决这些问题的关键技术。

1 IP组播技术概述

1.1 IP组播技术的概念

IP组播(也称多址广播或多播)技术,是一种允许一台或多台主机(组播源)发送单一数据包到多台主机(一次的,同时的)的TCP/IP网络技术。组播是一种数据包传输方式,当有多台主机同时成为一个数据包的接受者时,出于对带宽和CPU负担的考虑,组播成为了一种最佳选择。在网络音频/视频广播的应用中,当需要将一个节点的信号传送到多个节点时,无论是采用重复点对点通信方式,还是采用广播方式,都会严重浪费网络带宽,只有组播才是最好的选择。组播能使一个或多个组播源只把数据包发送给特定的组播组,而只有加入该组播组的主机才能接收到数据包。

1.2 IP组播地址和组播组

IP组播通信必须依赖于IP组播地址,在IPv4中它是一个D类IP地址,范围从224.0.0.0到239.255.255.255,并被划分为本地组播地址、全局组播地址和管理组播地址三类。其中,本地组播地址范围在224.0.0.0~224.0.0.255,这是为路由协议和其它用途保留的地址,路由器并不转发属于此范围的IP包;全局组播地址为224.0.1.0~238.255.255.255,可用于全球范围(如Internet)或网络协议;管理组播地址为239.0.0.0~239.255.255.255,可供组织内部使用,类似于私有IP地址,不能用于公网,可限制组播范围。

使用同一个IP组播地址接收组播数据包的所有主机构成了一个主机组,也称为组播组。一个组播组的成员是随时变动的,一台主机可以随时加入或离开组播组,组播组成员的数目和所在的地理位置也不受限制,一台主机也可以属于几个组播组。此外,不属于某一个组播组的主机也可以向该组播组发送数据包。

2 组成员关系协议IGMP

IGMP协议运行于主机和与主机直接相连的组播路由器之间,IGMP实现的功能是双向的:一方面,通过IGMP协议,主机通知本地路由器希望加入并接收某个特定组播组的信息;另一方面,路由器通过IGMP协议周期性地查询局域网内某个已知组的成员是否处于活动状态(即该网段是否仍有属于某个组播组的成员),实现所连网络组成员关系的收集与维护。通过IGMP,在路由器中记录的信息是某个组播组是否在本地有组成员,而不是组播组与主机之间的对应关系。

到目前为止,IGMP有三个版本。IGMPv1(RFC1112)中定义了基本的组成员查询和报告过程;目前通用的是IGMPv2,由RFC2236定义,在IGMPv1的基础上添加了组成员快速离开的机制;IGMPv3中增加的主要功能是成员可以指定接收或指定不接收某些组播源的报文。以下着重介绍IGMPv2协议的原理。

当同一个网段内有多个组播路由器时,IGMPv2通过查询器选举机制从中选举出唯一的查询器。查询器周期性地发送通用组查询消息进行成员关系查询;主机发送报告消息来响应查询。主机发送报告消息的时间有随机性,当检测到同一网段内有其它成员发送同样的消息时,则抑制自己的响应报文。如果有新的主机要加入组播组,不必等待查询器的查询消息,而是主动发送报告消息。当要离开组播组时,主机发送离开组消息;收到离开组消息后,查询器发送特定组查询消息来确定是否所有组成员都已离开。对于作为组成员的路由器而言,其行为和普通的主机一样,响应其它路由器的查询。通过上述机制,在组播路由器里建立起一张表,其中记录了路由器的各个接口所对应的子网上都有哪些组的成员。当路由器接收到某个组G的数据报文后,只向那些有G的成员的接口上转发数据报文。至于数据报文在路由器之间如何转发则由路由协议决定,不是IGMP协议的功能。

3 组播路由协议

3.1 组播路由的分类

组播路由可以分为两类:源分发树(Source Tree)和共享分发树(Shared Tree)。源分发树是指以组播源作为树根,将组播源到每一个接收者的最短路径结合起来构成的转发树。由于信源树使用的是从组播源到接收者的最短路径,因此也称为最短路径树(Shortest Path Tree,SPT)。对于某个组,网络要为任何一个向该组发送报文的组播源建立一棵树。共享分发树以某个路由器作为路由树的树根,该路由器称为汇集点(RP),将RP到所有接收者的最短路结合起来构成转发树。使用共享分发树时,对应某个组,网络中只有一棵树。所有的组播源和接收者都使用这棵树来收发报文,组播源先向树根发送数据报文,之后报文又向下转发到达所有的接收者。

源分发树的优点是能构造组播源和接收者之间的最短路径,使端到端的延迟达到最小;但是付出的代价是,在路由器中必须为每个组播源保存路由信息,这样会占用大量的系统资源,路由表的规模也比较大。共享分发树的最大优点是路由器中保留的状态数可以很少,缺点是组播源发出的报文要先经过RP,再到达接收者,经由的路径通常并非最短,而且对RP的可靠性和处理能力要求很高。

3.2 组播路由协议

与单播路由一样,组播路由也分为域内和域间两大类。域内组播路由目前已经发展的相当成熟,域间组播目前仍然处于研究和试验阶段。在众多的域内路由协议中,PIM-DM(密集模式协议无关组播)和PIM-SM(稀疏模式协议无关组播)目前应用最多的协议。

3.2.1 PIM-DM(密集模式协议无关组播)

PIM-DM协议使用了反向路径组播机制来构建分布树。PIM不依赖于网络中的单播路由协议和所有的密集模式路由协议一样也是数据驱动的。在PIM-DM域中,运行PIM-DM协议的路由器周期性的发送Hello消息,发现邻接的PIM路由器,进行叶子网络、叶子路由器的判断,并且负责在多路访问网络中选举指定路由器(DR)。

PIM-DM协议使用下面的假设:当组播源开始发送组播数据时,域内所有的网络节点都需要接收数据,因此采用"扩散/剪枝"的方式进行组播数据包的转发。组播源开始发送数据时,沿途路由器向除组播源对应的RPF接口之外的所有接口转发组播数据包。这样,PIM-DM域中所有网络节点都会收到这些组播数据包。为了完成组播转发,沿途的路由器需要为组G和源S创建相应的组播路由项(S,G)。(S,G)路由项包括组播源地址、组播组地址、入接口、出接口列表、定时器和标志等。

3.2.2 PIM-SM(稀疏模式协议无关组播)

在PIM-SM域中,运行PIM-SM协议的路由器周期性的发送Hello消息,用以发现邻接的PIM路由器,并且负责在多路访问网络中进行DR的选举。这里,DR负责为与其直连的组成员向组播树根节点的方向发送“加入/剪枝”消息,或是将直连组播源的数据发向组播分发树。

PIM-SM通过建立组播分发树来进行组播数据包的转发。组播分发树分为两种:以组G的RP为根的共享树和以组播源为根的最短路径树。PIM-SM通过显式的加入/剪枝机制来完成组播分发树的建立与维护。

PIM-SM中还涉及到RP的选择机制。在PIM-SM域内配置了一个或多个候选自举路由器。使用一定的规则从中选出自举路由器。PIM-SM域中还配置有候选RP路由器,这些候选RP将包含了它们地址及可以服务的组播组等信息的报文单播发送给自举路由器,再由BSR定期生成包括一系列候选RP以及相应的组地址的“自举”消息。“自举”消息在整个域中逐跳发送。路由器接收并保存这些“自举”消息。若DR从直连主机收到了IGMP加入报文后,如果它没有这个组的路由项,将使用hash算法将组地址映射到一个候选RP。然后朝RP方向逐跳组播“加入/剪枝”消息。若DR从直连主机收到组播数据包,如果它没有这个组的路由项,也将使用hash算法将组地址映射到一个候选RP,然后将组播数据封装在注册消息中单播发送到RP。

结束语

从目前的情况看,组成员管理普遍采用IGMPv2,PIM-SM因其良好的扩展性和从共享树向信源树转换的能力而成为域内组播路由的首选协议。组播技术为多媒体业务的开展提供了传送技术的基础,可以提供包括流媒体、视频会议在内的各种数据通信业务。组播技术涵盖了从地址方案、成员管理、路由和安全等各个方面,其中组播地址的分配方式、域间组播路由以及组播安全等仍是研究的热点和未来发展的方向。

主动可靠组播拥塞控制协议研究 篇2

关键词:主动网络;组播;拥塞控制

中图分类号:TN915.03文献标识码:A文章编号:1007-9599 (2010) 03-0041-02

Active Reliable Multicast Congestion Control Protocol

Li Juan,Zhang Xiuru

(Central South University of Information Science and Engineering,Changsha410083,China)

Abstract:Multicast Congestion Control in the general model, based on research on the ACC(Active Congestion Control)protocol of the main algorithm and implementation process.ACC selection strategy for the sender sending rate as the congestion control parameters.According to fairness criteria for the worst link in the active node and the multicast sender filter parameters at the same time congestion,and finally controlled by the sender's congestion parameters.

Keywords:Active networks;Multicast;Congestion control

一、引言

(一)概述

随着计算机网络尤其是Internet应用的不断多扩展,传统的单播(Unicast)技术无法解决像基于IP的音/视频会议(多点传输)之类的网络传输问题,而广播(broadcast)技术又会大量消耗网络资源,严重影响传输效率,组播技术正是基于此类问题而提出的全新网络传输方案。

(二)相关工作

组播是网络中多用户之间进行数据通信所采用的通信方式。随着组播应用的发展,对于数据可扩展性、传输延迟和可靠性等性能都提出了更高的要求,而不同类型的应用对于不同性能参数的要求也不尽相同。组播应用在传输层通常是采用UDP来实现的,而UDP协议是基于“尽力服务”,并不保证所有数据的正确传输和接受。为此,作者根据国内外的一些研究资料,对ACC协议的主要算法和实施过程进行了深度的研究。

二、组播拥塞控制协议体系结构

(一)丢包的检测及拥塞控制参数确定

ACC策略使用了可靠组播差错回复(armer)协议的丢包检测模块,且利用接受到的数据包序号“间隔”(Packet SN Gap)来进行丢包检测。利用马氏过程研究了链路丢包率较高时的TCP吞吐量,给出了一个适应性更好的TCP吞吐量模型:

T(RTT,p, ,b)=

其中,b为每一ACK确认的数据包个数; 为重传定时器的时间长度,以往返行程时间的倍数表示;P为链路上的丢包率;RTT为往返行程时间。

(二)丢包率p的计算。

设TCP中拥塞窗口大小为w,TCP协议允许w个已发送但未被确认的数据包(Outstanding Packet)。这些数据包在网络中可能由于拥塞而发生丢失,因而发送者可能会检测到多个数据包的丢失,但TCP协议在一个拥塞窗口内只响应检测到的第一个数据包的丢失,而忽略此窗口内的其他丢包,将这些丢包看作同一个“丢包事件(Loss Event)”。在基于数率的拥塞控制中,并不存在拥塞窗口的概念,但由于TCP的拥塞窗口对应于一个往返行程时间,因而可以讲在一个往返行程时间内的多个数据包的丢失看作属于同一个“丢包事件”。

如图一所示,丢包事件的检测是在数据包接受记录队列的基础上进行的,设前一次丢包事件结束在数据包记录i,目前收到的数据包最大序号为i+n,接收者在发送者发送的n个数据包中接收到的数据包个数为m个,此时在接收者共有n-m个数据包丢失。设j为满足以下条件的具有最小序号的数据包:

1.i

2.数据包j在接收者丢失。

图一丢包事件检测

(三)参数指示过滤

依据ACC协议,主动节点上的基本的过滤算法描述为:

If((Rate_New=0 and RTT_New=0)or Rate_Select≦Rate_New)then ADDR,RTT,Rate,Time_Select = ADDR,RTT,Rate,Tme_New else DROP_IT

(四)拥塞控制的实施

当经过组播树中主动节点及发送者层层筛选出拥塞控制参数后,发送者即开始进入拥塞控制的实施阶段。因而ACC策略拥塞控制对于处在不同阶段的组播通信分别设计了不同的实施策略。在组播通信建立时,发送者不希望盲目发送组播数据包,因而它通过发送带有指示的单个组播数据包主动地要求接收者立即发送反馈消息。

三、算法的优化

为增加算法的稳健性和适应性,对算法做如下完善:

(一)为增加算法的适应性,以满足不同网络条件的要求。ACC拥塞过滤算法加入了一个调节因子β,使得判断条件变为:

If Rate_New=0orRate_Select≦β*Rate_New

β参数通常取值范围为(0.8≦β≦1.2),当β取小于1的值时,节点对反馈消息的过滤比较严格,其对下游网络的恶化反应较慢,但不会出现较大的幅度变化。反之,当β取大于1的值时,节点更偏重于对目前下游网络中的恶化做出快速反应,此时节点中符合逻辑筛选条件的接收者会出现比较频繁的变化。

(二)对于主动节点来说,当它收到来自接收者的反馈消息并发现其符合拥塞控制参数筛选条件时,它将这一接收者视为当前其下游组播树中的“拥塞控制代表”,直到有新的符合拥塞控制参数筛选条件的反馈消息将其取代。因而此时应将此反馈消息向上游节点转发以反映这一情况。这一判断过程可以表示为:

If Rate_New>0 and ADDR_New=ADDR_Select

then ADDR,RTT,Rate,Time_Select=ADDR,RTT,Rate,Time_New;

(三)主动节点的下游子树中,如果某一接收者被上游主动节点选为“拥塞控制代表”当主动节点子树中的拥塞情况好转时,其他组播接收者发生的反馈消息均不满足筛选条件,而无法取代其“代表”地位,此种情况称之为接收参数“僵死”。此时,主动节点中需要采取相应措施,定期地对这些“拥塞控制代表”的状态信息进行刷新,直接取新来到的消息中的参数为选定参数。设主动节点中设置的状态刷新时间长度为Time_Update,则这一过程可以表示为:

If Rate_New>0 and ADDR_New ADDR_Select

then ADDR,RTT,Rate,Time_Select=ADDR,RTT,Rate,Time_New;

else DROP_IT;

组播发送者同样具备拥塞控制参数筛选模块,其功能和实施过程与主动节点中的一致。

(四)当组播通信进入正常工作阶段时,考虑到立即增大发送速率容易引发网络的拥塞,因而采用如下算法进行速率调整:

Rate_Delta=Rate_New-Rate_Current

Rate_Curren=Rate_Curren+ζ Rate_Delta(0<ζ<1)

这一算法可以提供平滑的最大发送速率,以避免造成或加重网络中的拥塞状况。

四、结论

ACC较全面的解决了基于主动网络的大规模可靠组播协议必须解决的主要问题,其算法的稳健性和适应性,满足了不同网络条件的要求。在今后的工作中,我还将对ACC协议进一步改进,包括过滤算法的完善,最大发送数率的提高。

参考文献:

[1]周贤伟,杨军,薛楠.IP组播与安全[M].北京:国防工业出版社,2005

组播路由协议 篇3

Ad Hoc网络终端具有路由功能, 是由一组带有无线收发装置的可移动节点组成的一个多跳的临时性自治系统。因其具有独立自组网能力以及无中心、动态性、易于铺设等特点被广泛应用于紧急救援、道路交通、军事战场、偏远野外和探险等临时信息系统建设, 成为当今的一个研究热点[1,2]。

基于Ad Hoc的组播路由协议有多种分类方法, 一般把它们按组播传输结构可分为树状组播路由协议、栅格状组播路由协议、混合性组播路由协议和无状态组播路由协议。在小规模的Ad Hoc网络中, 无状态组播路由协议因其独特的性能和特点得到众多研究人员的关注和认可。

无状态组播路由协议是基于这样一种考虑:基于树和基于网格的组播路由协议都需要进行路由树或网格的创建和维护, Ad Hoc网络频繁的拓扑变化导致这种过程的开销非常大。为了减少这种开销, 无状态的组播路由采用组播发送者集中管理组播成员关系的方法, 在分组的报头中显式的列出组播的接收者, 中间节点不需要维护动态的组播路由信息。无状态的组播路由主要用于小规模的组播, 并由单播路由协议根据分组的报头转发到各个接收者。

1DDM协议

DDM[3] (Differentail Destination Multicast) 是一种典型的无状态组播路由协议, 它由组播发送者负责对成员的管理。当节点加入组播组时, 利用单播路由, 发送JOIN消息到组播发送者, JOIN消息包括组播的ID号, 加入节点的ID号, 发送者的ID号。组播发送者接收到JOIN后, 将加入节点的ID号加入成员列表中, 加入节点就成了一个组播发送者的接收成员。

成员列表的更新是发送节点主动完成的。发送成员在数据分组中周期地捎带一个查询标志, 接收成员通过单播一个JOIN信息来响应发送成员的“查询”。当一个成员需要退出组播分组时, 显式地发送一个LEAVE消息。

DDM议的关键技术是基于组播接收成员的转发报头计算与编码, DDM采用差分编码。它的控制包有四种类型, 即JOIN, ACK, LEAVE和RSYNC。前三种控制分组用于成员控制算法, RSYNC用于节点与其上游节点的组播成员列表同步。DDM的包格式如图1所示。其包格式分数据包和控制包, 数据包主要包括DDM报头和有效负荷。

每一个DDM块对应一个下游邻居。DDM块包括有期望的接收者、DDM块类型、DDM块序列号。有三种类型的DDM块:空 (Empty) 块、刷新 (Refresh) 块、差分 (Difference) 块, 简便记为E, R, D。在无线广播网络中, 到不同邻居节点的DDM块可能汇聚到一个分组中, 以减少传输次数。

DDM的包头中需要转发的信宿节点的集合称作FS。在组播的源节点, FS和成员列表是一致的。在其他节点, FS是所有上游邻居节点FS的并集。节点到达FS中的信宿节点的路径是不同的, 根据转发的下一跳, 可将FS中的信宿节点划分为不同的子集, 成为方向子集DS。每个DS对应一个下游邻居节点。每个DS还包括一个强制刷新标志, 用于转发组的同步。节点在接到数据包以后, 首先比较序列号, 如果已经处理过, 则丢弃该包, 并根据DDM快的期望接收节点, 定位自己的DDM块。如果是R块, 则创建新的FS, 如果是D块, 则更新FS, FS=∪FS。

当采用差分编码时, 在DDM块中仅包含节点的差分列表, 因此保持上游节点的FS表与下游节点的DS表的一致性是十分重要的, DDM用序列号来维护表的同步。每个DDM块都有一个序列号, 来标记上游节点FS表的序列号为, 每发一个分组序列号加1, 发E块时不变。当节点检测到序列号不连续时, 就发送一个RSYNC消息到相应的上游节点, 接收到RSYNC的节点根据发RSYNC消息的节点的ID定位将发送DDM相应的分组DSS, 并更新列表, 从而使列表同步。

2对DDM的分析和扩展

评价一个协议好坏的标准有很多, 其中数据传输效率是很重要的一条。在Ad Hoc环境中, 能量和带宽是有限的, 怎么样在一定的时间里用尽可能少的能量传输尽可能多的数据, 一直是人们努力实现的技术。DDM是一个适用于规模小、移动速度快的Ad Hoc环境, 但从DDM的包格式来看, 其控制部分在整个包中占了很大比例, 这将严重影响协议的传输效率。一般情况下, 按需路由协议的包头都带有大量控制信息;表驱动的路由协议则需要大量的控制信息。

表驱动路由协议又称为主动式的路由协议, 该路由协议试图维护网格中各个节点到其余所有节点的最新路由信息, 所有路由信息保持一致。每个节点都维护一张或几张到网络中其他节点的信息表, 当网络拓扑结构发生变化时, 节点通过交互信息来实时地维护网络路由表。在表驱动协议中, 由于每个节点需要实时地维护路由信息, 这样在网络规模较大、拓扑变化较快的环境中, 大量拓扑信息更新消息会占用过多的信道资源, 使得系统效率下降。按需路由协议是只有在节点有数据要发送时, 才激活路由发现机制寻找到达目的地的路由, 很多控制信息加在数据包上, 减轻了网络负担, 灵活性、健壮性较好, 但其包格式的控制部分占比例太大, 影响传输效率[4]。

为了保持协议的传输效率和健壮性, 可以取长补短, 使用表驱动和按需驱动两种方式相结合的协议。即组播路由的发现和维护使用按需驱动的方式, 而传输组播数据包则用表驱动的方式。这里提出一种同样适用于规模小, 移动速度快的Ad Hoc环境的新的组播路由协议EDDM。

3EDDM组播路由协议

EDDM (Efficient Differentail Destination Multicast) 是一种靠单播链路来进行分发的组播协议, 它是使用按表驱动和按需驱动混合的一种高传输效率的组播协议。它内嵌的单播协议也是DSR协议。

3.1 EDDM的包格式

EDDM主要有JOIN, REQ, ACK, DATA, LEAVE和RSYNC六种包格式, 其中, JOIN, REQ, ACK, LEAVE和RSYNC是控制包, 它们的包格式是DSR格式, 如JOIN的包格式, 如图2所示。JOIN, REQ, LEAVE是用来维护和发现路由的, RSYNC是用来同步数据包的。这些包中含有部分控制信息, 包头相对较长。

DATA包是数据包, 它的格式相对就简单多了。为了提高传输效率, EDDM的数据包不包含控制信息, 控制信息都写在节点内部的表中, 其格式如图3所示。

3.2 组播路由的发现和维护

EDDM的路由维护和管理是由组播的发送者来实施的。其过程如下:

(1) 想加入组播的节点通过向源节点单播一个JOIN消息来加入组播组, 源节点收到JOIN消息后, 把发送JOIN的节点加入组播组然后单播REQ消息给请求的节点。

(2) 中间节点在收到JOIN消息后, 就认为自己是组播的转发节点, 并记下JOIN消息的上一个节点、下一个节点以及JOIN消息的发送节点, 从而建立了一只组播链路。

(3) 组播源节点周期性的组播确认信息REQ, 当成员节点收到REQ后, 将回复JOIN消息。

(4) 如果组播成员节点在规定的时间内没有收到REQ消息, 那么它将继续周期性的发送JOIN消息, 直到得到源节点的回应。

(5) 如果某条链路在数据转发的过程中发生断链, 那么发现断链的节点将使用单播的形式发送RSYNC消息给与本链路相关的各个目的节点。目的节点收到RSYNC消息后将重启单播寻路机制, 然后向源节点发送JOIN消息, 从而达到维护路由的目的。

(6) 如果某个目的节点想退出组播组, 则发送LEAVE消息给源节点, 那么沿途所有收到LEAVE消息的中间节点都会取消针对退出的目的节点的数据转发。源节点如果在规定的时间内没有收到某个成员的JOIN消息, 也没收到LEAVE消息, 会将该节点从组播成员中删除。而中间节点如果在一定的时间内 (这个时间设定为刷新时间的2倍) 没有收到经过它的JOIN消息, 则认为自己不再是中间节点, 不再转发数据。

3.3 EDDM数据包的转发

当源节点广播数据包时, 源节点和目的节点之间已经通过发送JOIN消息和REQ消息建立起了组播路由。组播路由表是独立于单播路由表的, 它只是从靠JOIN消息中解读出有用的信息保存在JION所经过的节点的表中。

(1) 当一个中间节点收到一个组播数据包, 先检查是不是收到过同样的包, 如果以前收到过则销毁。

(2) 如果第一次收到这个包, 则检查这个包经过的上一个节点号和它的组播号并将他们跟自己的组播路由表对比, 看其是否与自己相关如果不相关则销毁。

(3) 如果这个数据包与自己相关, 则立即给上游邻节点发送ACK消息并广播数据包, 然后等待下游邻节点的ACK消息。

(4) 如果在规定的时间内没有收到下游邻节点的ACK消息, 则认为该处断链。

4仿真与分析

为了评测EDDM协议的性能, 使用NS2仿真工具对其性能进行模拟研究, 并与经典组播协议ODMRP进行比较。网络中节点通信半径最大为250 m, 信道能力为2 Mb/s, 节点的无线传输模型选Two-Ray Ground传输模型, 仿真过程中每个组播组中仅有一个信号源发送数据;仿真时间为400 s, 节点移动速度为2～20 m/s。节点在1 000 m×1 000 m的矩形平面空间中进行随机运动移动。

本实验针对ODMRP和EDDM的数据包传输效率进行了仿真比较, 比较结果如图4所示。从图中可以看到, 组播成员节点相对较少的情况下, EDDM的数据包传输效率明显优于ODMRP。但随着成员节点个数的增多, 其性能逐渐下降, 说明EDDM的扩展性不强。在这里没有从仿真中严格比较DDM和EDDM在数据传输效率方面的优劣, 但给出了EDDM和ODMRP的比较。在成员节点数目较少的情况下, 他的数据传输效率都优于ODMRP, 但这种优势也都随着组播成员个数的增多而变小。

从传输单个数据包的角度来看, EDDM的效率与DDM的效率相比差别很大。现在设DDM的源节点周围有m个下游节点 (也就是说第一次转发的数据包中需要带m个DS块) , 设每个DS块中有n个目的节点, m和n的最小值为1, 每个段按最小8位, x为数据大小, 则DDM的数据部分占总大小比例为 x/[8 (4+m (5+n) ) +x];而EDDM的数据部分占的比例为x/ (3×8+x) 。

通过Matlab的计算比较可以得到如图5所示的结果。

图5分别对式x/[8 (4+m (5+n) ) +x]中的n=m=1和n=2, m=3及式x/ (3×8+x) 进行了计算比较, 数据部分x的大小范围为32～256 b。从图5中很容易发现, 在DDM协议的包格式中, 目的节点越多, 单个包的数据传输效率越低, 只有在带宽很大时, 其单包传输效率才很高, 而这在实际应用中是很难达到的。在EDDM中, 单个数据包的数据传输效率高于DDM很多, 在数据部分x比较小的时候, 这种优点尤为明显。

5结语

EDDM是一种使用于小规模的高效组播路由协议。它从无状态组播路由协议延伸而来, 是一种树状结构的协议, 但其状态结构的组织非常松散, 类似于无状态的组播结构。该协议充分考虑了表驱动与按需路由驱动的优缺点, 是从实际应用出发, 使用二者相结合的方式形成的一种高效数据传输协议。从各个方面的比较来看, EDDM确实有效地保证了在小规模、高速度Ad Hoc网络中的高效数据传输。

摘要：Ad Hoc网络中, 组播路由协议具有广泛的应用前景。但由于网络拓扑的变化和节点能量的限制, 设计具有高效传输能力的组播路由协议比较困难。通过综合比较表驱动路由协议与按需路由协议的优缺点, 并且考虑Ad Hoc网络中节点的移动性以及路由发现与路由维护的方法对传输效率的影响, 在无状态组播路由的基础上, 使用表驱动与按需路由驱动相结合的路由方法, 提出一种新的组播路由协议, 使传输效率有较高的提升。

关键词：自组网,组播路由协议,传输效率,按需驱动

参考文献

[1]郭永洪, 李光胜, 毛启容, 等.Ad Hoc网络组播路由协议研究现状、问题和方向[J].计算机应用及软件, 2006, 23 (4) :8-10, 65.

[2]孙宝林, 李腊元, 李相棚.移动Ad Hoc网络多播路由协议的研究进展[J].计算机工程与应用, 2004, 40 (32) :139-143.

[3]JI Lu-sheng, CORSON M Soctt.Explicit multicasting formobile Ad Hoc network[J].Mobile Networks and Appli-cations, 2003, 8 (1) :535-549.

[4]郑少仁, 王海涛.Ad Hoc网络技术[M].北京:人民邮电出版社, 2004.

[5]LEE S, SU W, GERLA M.On-demand multicast routingprotocol (ODMRP) [C]//Proceedings of IEEE WCNC′99.New Orleans, LA:IEEE, 1999:1298-1302.

[6]LUO Jun-hai, YE Dan-xia.A survey of multicast routingprotocol for mobile Ad Hoc networks[C]//IEEE Commu-nications Surveys&Tutorials.[S.l.]:IEEE, 2009, 11 (1) :78-91.

[7]KALIAPERUMAL B, EBENEZER A, Jeyakumar.Adap-tive core-based scalable multicasting networks[J].Proc.IEEE INDICON, 2005, 29 (3) :198-202.

[8]SOON Y O, PARK J S, GERLA M.E-ODMRP:enhancedODMRP with motion adaptive refresh[J].Proc.ISWCS, 2005, 49 (17) :211-217.

[9]YU Yao, ZHOU Yu.Impact of Interference on multicastthroughput over Ad Hoc Networks[R].Fifth InternationalJoint Conference on INC, IMS and IDC, 2009.

一种新的QoS组播路由算法 篇4

BP神经网络通过学习和推理这两个过程,能够修正各个连接途径的权值,无限地逼近样本值,不断修正结果,并且对相关信息实施处理[3 - 4]。BP神经网络在学习、分类和优化上有优势,有较强的局部搜索能力。蚁群算法( Ant Colony Algorithm,AC) 是蚁群能够找到一条从巢穴到食物的最短路径的方法[5],蚁群算法的优点是具有较强的鲁棒性、分布式计算、易于融合其他算法,同时具有较强的全局搜索能力,但是收敛速度慢、易陷入局部最小点。

本文结合BP神经网络和蚁群算法的优点,提出了一种新型的神经网络蚁群算法( Neural Network Ant Colony Algorithm,NNAC) 。结合BP神经网络局部搜索的优势和蚁群算法全局搜索的优势,同时BP神经网络还能弥补蚁群算法易陷入局部最小点的不足。

1 Qo S组播路由网络模型

在Qo S组播路由网络模型中,通常用加权图G = ( V,E) 表示通信网络,V表示节点集,E表示链路集,节点数和链路数分别由V和E表示[6 - 7]。同一对节点间的链路数≤1 的网络模型如图1 所示。

R+、R*分别表示正实数集和非负实数集。数据由源节点s ∈ V传送到目的节点集D  V - { s} ,组播组M = { s} ∪ D 。定义组播树T = ( VT,ET) ,组播树T由源节点传送到目的节点的路径为l( s,d) ,则对于任意链路e ∈E可定义以下Qo S参数:

时延函数

带宽函数

时延抖动函数

包丢失率函数

链路代价函数

求解多约束Qo S组播路由优化问题是指寻找从源节点到目的节点的组播树T ,并且满足Qo S参数的约束条件

式中: Dp,Bp,Jp,Lp分别为时延、带宽、时延抖动、包丢失率约束量。

2 NNAC算法

结合BP神经网络局部搜索的优势和蚁群算法全局搜索的优势,进行Qo S组播路由算法的设计,提出了一种新型的神经网络蚁群算法( NNAC)[8 - 10]。

2. 1 NNAC算法实现步骤

NNAC算法步骤为:

Step1: 确定BP神经网络结构,给定BP神经网络权值和阈值; 对蚁群算法初始化设置,包括多路径信息强度、蚂蚁数量。

Step2: 计算各个路径的适应度。

Step3: 从源节点出发,通过赌轮规则选择合适的路径,进行分泌物强度调整。

Step4: 将收集的参数作为BP神经网络初始权值和阈值,并对BP神经网络进行训练。

Step5: 应用BP神经网络在当前路径中找到更优解,如果有更优解则替代原有路径。

Step6: 计算各组播树的代价,判断大部分路径是否收敛于同一组播树,收敛则为最优路径,退出程序; 否则,只保留最小代价的组播树,转到Step7。

Step7: 返回源节点,转到Step2。

2. 2 初始化

初始化中需要设定BP神经网络的权值和阈值para = { wi} ,wi为N个较小的随机值,N个随机值组成集合Iwi= { wijwij∈[- l,l]} ,i = 1,2,…,N; j = 1,2,…,N ,设wi对应的信息素为 τij,初始时刻、信息素相等,上限为 τ0= τmax。

2. 3 路径适应度

NNAC算法依据适应度函数选取路径[8],选用的适应度函数为

式中: phePj表示路径Pj的分泌物强度,phePj值越大,表明路径Pj被选择的概率越大。

2. 4 信息调整

分泌物强度调整函数为

式中: ω 为常量参数; l为链路代价。每当蚁群走完一条路径后,需要对所有路径的分泌物挥发性进行调整[9 - 10]

式中: η 为分泌物挥发度; α 为各个路径的初始信息强度。

2. 5 BP网络训练和调整

BP神经网络采用包括输入层、隐含层、输出层的网络结构[11 - 13]。在BP神经网络训练时,并不知道准确的输出结果,将Step3 中分泌物强度phePj最大的路径和其他路径进行比较,来指导BP神经网络。同时,BP神经网络采用附加动量法进行训练,当修正的权值对误差的影响较大时,应放弃新权值,并停止动量; 当新的误差变化率超过设定的最大误差变化率值后,应放弃对权值的变化。最大误差变化率一般设置为1. 04。附加动量法判断公式为

式中: mc为动量因子,取0. 95; k为训练次数。

设BP神经网络输入向量为X = [x1,x2,…,xn]T,输出向量为Y = [y1,y2,…,yl]T,期望输出为D = [d1,d2,…,dl]T。

BP神经网络的目的就是求误差能量E的最小值,应用BP神经网络在当前路径中找到更优解的方程为

式中: cij表示链路代价; dij表示时延; vij表示神经元的输出; λ → ∞ ; 能量函数u1项表示代价和时延的最小值; 能量函数u2项表示每个节点的出、入边数相等时的最小值,保证从源节点到目的节点为一完整路径。

3 算法仿真分析

首先对NNAC算法全局最小值的寻找进行仿真[14]。由于该算法采用附加动量的BP神经网络进行了训练,所以在附加动量的驱动下,可以避免局部极小值的干扰,从而最终寻找到全局最小值,结果如图2 所示。

对NNAC算法进行仿真分析的网络拓扑结构采用8节点网络结构,如图3 所示。拓扑结构图中的源节点为s,目的节点为a,c,e,f,图中各个边上的数值代表延时和代价,用( Dp,CP) 表示,( Dp,CP) 的数值是随机的,BP神经网络误差能量的公式中的u1= 1 000 ,u2= 200 。

利用MATLAB编写NNAC算法程序,得到最优组播树如图4 所示。通过图4 可知,总延时为35,总代价费用为21。

为了进一步分析NNAC算法的性能,引入AC算法,通过两种算法进行最优组播树的寻找成功率进行对比分析,通过实验可以得到如表1 所示结果。

%

通过表1 可以看出,两种算法在指定的网络环境下,完成150 个度约束组播路由路径时,NNAC算法在进行最优组播树的寻找成功率上高于AC算法。因为NNAC算法融合了BP神经网络局部搜索的优势,克服了易陷入局部最小点的不足。

4 结论

无线mesh网络组播路由研究 篇5

随着无线通信和移动计算技术的发展, 人们对无线宽带接入提出了更高的要求, 作为“最后一公里”宽带无线接入非常重要的技术之一, 无线mesh网络正倍受科学家和工程师的广泛关注。无线mesh技术的出现, 代表着无线网络技术的又一大跨越, 有着极为广阔的应用前景。无线Mesh网络[1] (Wireless Mesh Network) 简称WMN, 是一种通过无线链路连接路由器和终端设备的无线多跳网络, 具有自组织、自愈合, 高速率、易组网等特点。

组播是一种一点到多点或者多点到多点的通信方式, 即一个源节点同时发送相同的信息给多个目的节点。在一个组播会话中, 所有源节点和目的节点的集合构成了一个组播组, 组播源把数据包发送到特定的组播组, 而只有属于该组播组的地址才能接收到数据包。组播可以大大地节省网络带宽, 因为无论有多少个目的节点, 在整个网络的任何一条链路上只传送单一的数据包。组播通信具有网络利用率高、节约主机资源等优点, 在视频点播、远程教育、分布财务数据、电话会议、文件分发、实时信息发布以及交互式网络游戏等很多网络应用中发挥着巨大的作用, 因此组播技术一直是网络领域中的热门研究课题。虽然组播技术有着许多非常重要的应用, 但是关于无线mesh网络中组播技术的研究一直还处在初级阶段。组播与单播的区别如图1所示。

2 基于树的组播路由算法

这类组播算法的基本思想是将参与组播路由的所有节点在拓扑上组成一棵树。有两种基本的组播路由方法:最短路径树 (SPT) 和最小开销树 (MCT) 。

SPT算法的目的是以发送节点为根, 构造一棵从发送节点到所有接收节点的树, 使得发送节点与每个接收节点的路径最短。所以, SPT算法能够使端到端延迟最小化。

不同于SPT算法, MCT算法的目的是使组播树的所有开销最小化。MCT组播路由算法是基于最小Steiner树 (MST) 问题, 它是一个NP完全问题。

通过Steiner树的定义可以知道, 它的总开销要小于相应的SPT的总开销。然而, Steiner树中发送节点与接收节点之间的路径要比SPT中的更长。这就意味着, Steiner树的平均路径长度要比SPT的更大。

Ruiz和Gomez-Skarmeta[2]重新定义了MCT的开销问题:在一个广播媒介里面, 组播数据包从一个节点传送到与它相邻的节点可以被看作是单播数据包的传送。因此, 在一个无线多跳网络里面, 最小开销树也就是用最小的传输节点数连接发送节点和接收节点的组播树, 而不是传统的MST定义的拥有最小的边开销的组播树。换句话说, 最小开销树应该包含最少的组播转发节点数 (MNT) 。

实验[2]证明了在大多数情况下, 与MST和SPT相比, MNT有最少的转发节点数。另一方面, MST和MNT的平均路径长度要比SPT的更大。如图2和表1所示。

然而, 目前的实验结果都不能反映出包发送率、吞吐量以及延迟等组播性能的好坏, 这些性能参数对于一些实时的组播应用来说是非常重要的。

文献[3]的仿真实验中, 由Ruiz和Gomez-Skarmeta提出的组播路由算法并不能构建最优组播树。事实上, 这些结果与Ruiz和Gomez-Skarmeta的发现是一致的:因为MNT算法只有在高密度的网络 (40个节点/km2或者更多) 中才能有效运用。与其他类型的无线多跳网络 (例如移动Ad hoc网络和传感器网络) 相比, WMN属于一般的低密度网络 (小于40个节点/km2) , 因为mesh路由器的传输范围要大得多 (超过300m) 。

当组播组的大小介于小型网络和中型网络 (相当于100个节点的网络里n≤50或者300个节点的网络里n≤100) 之间时, SPT算法能够提供比MST算法和MNT算法更好的组播流性能。这是因为SPT算法有更短的平均路径长度, 它能够提供更高的组播发送率和吞吐量, 以及更低的端到端延迟。

在发送率比较低的大型组播组里面, SPT算法在某种程度上同样要优于MST算法和MNT算法, 并且三种算法会产生同样多的组播通信开销。

3 算法性能评估

当组播组规模较大、组播发送率较高时, 我们通过仿真实验来比较SPT、MST以及MNT算法在包发送率、吞吐量、端到端延迟等性能参数方面的差异, 选择适合于WMN的组播路由算法。

实验采用QualNet仿真工具, 分别对文献[4]提出的SPT算法、文献[5]提出的MST算法以及文献[2]提出的MNT算法进行仿真实验。采用以下参数来衡量组播路由算法的性能:

(1) 平均组播包发送率:包发送率定义为接收节点收到数据包的实际数量与理论值的比值;平均PDR也就是所有接收节点的PDR的平均值。

(2) 平均吞吐量:吞吐量定义为接收节点实际收到的数据总量除以从接收节点收到第一个包开始到接收最后一个包所花费的时间。

(3) 平均端到端延迟:定义为目的节点的分组接收时间与源节点的相应分组发送时间的平均差值。

公共仿真参数及组播仿真参数见表2和表3。

4 仿真结果

从图3和图4可以看出, 在大多数情况下, SPT都能够提供比MST和MNT更高的PDR和吞吐量;从图5可以看出, 当通信负载比较大 (70或80packets/s) 的时候, SPT会产生比MST或MNT更高的端到端延迟, 这是由于SPT使用了更多的转发节点数, 更多的转发节点数造成了更多的网络拥塞和信道竞争。然而, 当通信负载增大的时候 (n=80) , MST和MNT的PDR降低到了72%以下, 这对于大多数实时应用来说是不能接受的。

5 结语

本文将无线mesh网络中SPT和MCT的不同性能进行量化, 对于MCT, 我们考虑了MST和MNT两种组播树。仿真结果显示, SPT在PDR、吞吐量以及端到端延迟等性能方面都要优于MCT。SPT的唯一不足就是, 当组播组规模较大以及组播发送率较高时, SPT会造成更多的包丢失。为了降低SPT组播通信给网络带来的影响, 可以通过用流量控制机制降低组播发送率, 并采用多信道、多无线电系统来解决。

另外, SPT比MCT更容易支持节点的动态加入或离开, 这是因为在SPT组播树里面, 每条发送节点到接收节点的路径之间都是相互独立的, 而在MCT组播树里面, 一个节点的加入或离开可能会要求整棵组播树进行重新计算, 以此来获得组播开销的最优化 (或者新的组播树不再是最优化的) 。因此, SPT组播路由算法在WMN中显得更为实用。

摘要：组播在无线mesh网络中有着重要的应用。介绍了两种基本的组播路由算法:最短路径树 (SPT) 和最小开销树 (MCT) , 通过仿真对组播发送率、吞吐量以及端到端延迟等性能进行比较, 找出适用于无线mesh网络的组播路由算法。

关键词：无线mesh网络,组播,SPT,MCT

参考文献

[1]Ian F.Akyildiz, Xudong Wang, Weilin Wang.Wireless mesh networks:a survey[J].Computer Networks and ISDN Systems.Vol.47, no.4, 2005page (s) :8-14.

[2]P.M.Ruiz, A.F.Gomez-Skarmeta, Approximating optimal multicast trees in wireless multihop networks, in:10th IEEE Symposium on Computers and Communications, June2005, pp.686–691.

[3]Uyen Trang Nguyen.On multicast routing in wireless mesh networks.Computer communications, Volume31, Issue7, 9May2008, pages1385-1399.

[4]Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, Clifford Stein, Introduction to Algorithms, The MIT Press, 2001.

广域网中组播路由安全策略设计 篇6

IP组播最早由Steve deering于1988年提出, 并在1989对标准IP网络层协议进行了扩展, 提出了IP组播规范。IETF RFC1112对IP组播的业务提供的方式和形式进行了描述和定义, 被看成是IP组播的标准业务模型的定义。[1]

1992年IP组播实验网MBone建立。MBone的建立大大促进了IP组播在Internet中的应用。MBone是在现有Internet之上构建的一个虚拟网络, 采用隧道方式连接各个组播节点。正在兴起的Internet2改变了MBone中采用隧道实现组播的方式, 全网所有路由器均支持组播, 这为未来组播业务的开展提供了良好的网络基础。下一代互联网协议IPv6规定所有的IPv6路由器必须支持组播路由功能。[2]

组播技术将在未来网络通信发挥重要作用, 有着广阔的应用前景。介绍了组播路由协议的基本原理, 针对组播路由可能受到的攻击, 设计了组播路由攻击安全防范策略。

2 组播路由基本原理与路由协议介绍

组播是一种允许一个或多个发送者发送单一的数据包到多个接收者的网络技术。组播源把数据包发送到特定组播组, 而只有属于该组播组的地址才能接收到数据包。组播可以大大的节省网络带宽, 因为无论有多少个目标地址, 在整个网络的任何一条链路上只传送单一的数据包。图1展示了单播与组播的区别。

组播路由选择协议是组播路由选择算法的扩充和标准化。它为组播信息找到从组播源到接收端的路由通道, 以保证组播信息能到达接收端网络。当前的组播协议细分为三类:密集模式协议、稀疏模式协议和链路状态协议[3]。

2.1 密集模式协议

密集模式协议适用于组成员比较多或分布比较稠密的情况。距离向量组播路由协议 (DVMRP) 和密集模式的协议无关协议 (PIM-DM) 都属于密集模式协议。它使用推的技术 (Push) 利用最短路径树来发送组播信息。这就如同无线电广播一样, 接收端只需简单的加入组播组就能够收到组播信息。

2.2 稀疏模式协议

稀疏模式协议适用于组成员比较少或分布比较稀疏的情况。有核树 (CBT) 和稀疏模式的协议无关协议 (PIM-SM) 都属于稀疏模式协议。它使用拉的技术 (Pull) 从组播组接收组播信息。因此, 它假定组播不被需要, 除非用一个显式的组播加入机制, 否则组播信息就不会被传送到接收站点。

2.3 链路状态协议

链路状态协议也适用于密集模式, 它是使用SPT的接收站点发布组播信息。但是, 链路状态协议不适用于DVMRP或PIM-DM的扩散和剪枝机制。相反, 它扩散特殊的组播, 即链路状态信息, 这些信息可随时随地的识别网络组成员。所有的网络路由器使用本组成员信息来建立从每一个源地址到所有接收站点的最短路径树。

3 组播路由安全策略设计

传统的任意源组播服务模型的一对多特性和多对多特性, 攻击的效果很容易被放大, 从而导致组播网络易受到攻击。因为组播网络和单播网络共享链路和设备, 所以对组播网络的攻击, 不仅影响到正常组播用户的服务质量, 还会间接地破坏单播服务的正常运行。

应对IP组播网络存在的这些安全威胁, 需要采取相应的安全策略。首先是增强协议的安全性, 在已有的协议基础之上添加新的安全机制, 确保组播协议能够稳定安全运行, 协议关键信息不被恶意攻击者利用。再者需要多种有效的安全措施保障组播网络运行, 如速率限制, 并加强对组播源和组成员接入的控制。[4]

3.1 增强组播协议

为了弥补组播协议存在的这些缺陷, 人们提出了一系列的改进措施。最简单的方案是在不修改组播协议的情况下, 仅依靠IP层提供的加密认证功能。通过签名处理, 伪造的消息将因为没有有效的签名而被丢弃。注意, 这里的签名对单播形式的报文和组播形式的报文同样有效。当非法签名组播报文到达邻居路由器时, 将被邻居丢弃。而对于非法签名的单播报文, 当其到达目的地之后也将被目的路由器丢弃。这样, 对register消息进行认证之后, 恶意攻击者伪装成第一跳路由器发送的register消息将不能通过认证而被丢弃。这可以有效防止攻击者“远程”实施针对RP的Register报文攻击。

3.2 报文速率限制

为了保证组播核心网络的安全性和稳定性, 必须确保核心路由器能够正常运转, 即在高负载情况下依然能够工作。常用的一个方法是进行速率限制, 即当某种类型的流量超过规定的闭值的时候, 路由器按照预定的规则丢弃部分报文, 以保证系统能够正常工作, 而不是因为过载而瘫痪。当遇到恶意攻击时, 特别是DDo S攻击, 就会出现大量的非正常流量, 这时候就会引起路由器过载。一般而言, 组播路由器都配备了相应的限速措施以应对这种强度比较大的攻击。

3.3 组播网络边缘控制

为了限制恶意流量进入组播网络, 可以在组播路由器, 特:别是在第一跳路由器和最后一跳路由器上部署过滤器, 将非法的组播控制报文和数据报文拒绝在组播网络边缘, 这样就可以减轻组播核心网络的负担, 从而提高整个组播网络的安全性和稳定性。在组播网络边缘控制组播, 需要在组播源和组成员的加入两个方面进行控制。

4 结论

组播的特性使得它成为DDo S攻击的一种主要技术手段, 广域网由于其结构复杂多变和跨地区的特性, 使得它遭受组播协议攻击的机会比局域网要高很多。一旦利用组播技术进行DDo S攻击, 其破坏性特别大。针对广域网的特点, 以原有的组播路由协议为基础设计了三个安全策略。应用效果表明, 综合利用这三种安全策略能够有效地降低组播路由被攻击的可能性。

摘要：在广域网中使用组播传输一点对多点的数据能够减少对网络带宽的占用, 提供信道利用效率。介绍了组播路由基本原理与常用的组播路由协议, 针对广域网组播协议容易受到DdoS攻击的问题, 设计了广域网组播路由的安全策略。

关键词：组播路由,安全策略,DDOS

参考文献

[1]蒋东星, 郑少仁.IP网络组播技术的新发展[J].电信科学, 2003 (9) :9-13.

[2]郑健平.互联网的IP组播与泛播通信机制研究[J].中国科学院研究生院, 2004 (12) :1-2.

[3]李宏玉.组播拥塞控制技术研究[J].大庆石油学院, 2005 (3) :8-9.

组播路由协议 篇7

路由概念在计算机网络界出现较早, 但是由于早期阶段网络架构通常较为简单, 因此路由并没有得到很大的发展。直到20世纪80年代, 随着大型网络的出现和广泛应用, 路由才获得了巨大的发展机遇, 并很快在商业上取得了成功。路由就是将在网络环境中将信息从源传送到目的地的 行为, 在传送信息过程中至少会出现一个中间节点。路由一般情况下包括两个方面的内容, 一是选择出最有效的路径, 二是通过网络通道实现信息的传输。在整个过程中, 数据交换相对来说较为简单, 路径的选择是最为复杂的内容。而路由算法的提出为解决寻找最佳路由途径提供了支持。

网络环境中实现数据包的传输有三种方式: 单播式、广播式和组播式。组播传输方式介于单播和广播之间, 能够满足单一或者多个源点向多目的地同时发送同一数据包的要求, 这种传输方式对于网络宽带具有极强的优化作用, 同时能够最大可能地降低主机的数据处理压力以及控制网络流 量。组播的工作原理是将数据包传送到具有一定功能的组播组中, 在接受该数据包时, 通过网络地址协议限制数据流量, 达到了节省宽带的效果, 同时对于数据的传送效率有很显著的提高。

2 不同类型的组播路由算法

网络通信将会出现目标函数的优化问题, 具体包括树优化以及路由优化两个方面。一般解决这些问题的关键是通过运用组播路由算法对组播树 进行系统性的构建, 这就会涉及到NP-hard的相关问题, 所以在常规模式下会先行设计启发式组播路由算法。根据算法的目标函数以及其受到的约束条件可以将组播路由算法分成三种 类型, 这三种类型分别是最短路径和最小生成树算法、Steiner树算法和CBT算法以及QoS算法。

最短路径算法中最常见的两种是Bellman-Ford (距离矢量路由算法 ) 算法和Shortest-Path First (链路状态路由算法) 算法, 这两种算法的共同特点是信息从源节点送达目的节点的费用最小, 避免了环路造成的冗余;Steiner树算法的理论基础是建立费用最小化的生成树, 这种生成树的根为源点节, 该生成树能够将一切的目的节点纳入其运算范围之内。CBT算法与Steiner树算法结构类似, 这种算法根的选取为中心点, 相关成员依据最短路径与根进行连接, 从而实现源共享;QoS算法的最大特色是在保证数据包传输效率的同时, 尽可能地实现数据包不延时、不丢失、不乱序, 从而达到理想的数据传输效果。

3 计算机网 络组播路由算法的改 进策略

3.1 增强对 Internet 动态性的支持

网络通信中的重要内容和理论研究热点是关于网络拓扑变化以及状态信息变化的相关问题。对于这两种网 络变化因素应该使用动态算法进行处理, 此外还要改变传统的组播树设计理念, 不能仅仅根据频繁的重建组播树来实现对目的节点动态变化的处理。 在实际的操作中要研究Internet网络组播的通信量以及构成组播的动态特征, 从而可以进行有针对性地组播路由算法设计, 并且可以考虑将静态组播路由算法的技术优势经过处理用于网络的动态性分析。

3.2 提高分布式算法的应用性

传统的集中式算法复杂度高, 在网络环境中不具有大范围应用的价 值, 例如Bellman-Ford SPT虽然代码容易编写, 并且属于组播算法中复杂程度最低的算法, 通常只达到O (n2) 水平, 但是其工作效率极为低下, 不适于Internet状态的计算。除此之外, 多QoS约束的组播算法通常也具有较高的复杂程度, 一般在O (n2) 水平 , 很难将其与网络路由进行融合。相比而言, 分布式算法在简易程度上具有极大的优 势, 通过对中心点范围的计算量进行有效处理, 使其实现分散计算, 大大降低了复杂度。

3.3 提升组播树生成代价性能

开发Internet高性能的组播路由算法要面临的核心问题包括提升建构 组播树的代价性能以及与之紧密相关的计算复杂度问题。代价性能通常情况下表现为计算复杂度的矛盾体, 要想实现组播路由算法计算的简便性就会使生成组播树的代价性能大打折 扣。同样地增强组播树生成代价很大程度上会使计算更趋复杂。因此进行 计算机网络组播路由算法的改进必须处理好这两者之间的关系, 根据实际需求做出折中决定, 从而制衡两方面要素的优劣互斥。

3.4 加强网络 组播算法的创新力 度

网络技术的更新速度很快, 各种新技术新理念不断地涌现, 伴随而来的是更加多样化的业务需求以及相应的网络服务质量标准。可以确定的是 新一代的网络组播对于服务质量的要求将会更加严格, 因此, 需要不断地加强创新力度, 开发出适应新一带QoS要求的组播算法。

参考文献

[1]刘维群, 李元臣.时延约束的链路选择平衡优化组播路由算法[J].计算机应用, 2011, (04) .

组播路由协议 篇8

节点移动预测算法是通过对相邻节点的监控, 预测其下一时刻的行为, 如果相邻节点要离开节点间的有效通信范围, 那么节点预先启动新的路由发现过程。移动预测算法是基于无线传播数学模型的。通过合适的无线传播模型, 可以估计节点间的距离。通过估算距离和时间间隔这两个参数, 可以估计相邻节点的相对运动已经运动的速度等参数。

为了减少网络拓扑结构的变化带来的重路由操作, 寻找一条最为稳定的路径就成了关键, 因而首先要确定各个链路的稳定性。如何利用节点现有的运动信息预测节点在将来某个时刻的运动状况就成了预测链路稳定性的关键。链路预测包含两个阶段节点运动状态信息的获取和运用链路预测方法进行链路状态计算。

(二) 一种基于移动预测的分段Ad Hoc组播路由重建模型

根据当前网络节点分布情况, 将距离较远的通信节点之间的节点分成若干分段, 对每个分段进行分别管理, 当某分段路由失败时可以只针对这一分段进行路由重建, 而不需要整个网络都参与, 降低了路由维护的开销。每一个分段都用LET预测模型预测本分段中两个节点之间的连接保持时间, 以便在路由发现阶段寻找较为稳定的路由, 同时可以预测本段路由的失效时间, 在本分段路由接近失效的时候, 提前进行路由重建, 使上层应用尽量不受路由断裂的影响, 保持上层业务的持续性。

1. 分段模型

对于本文给出的分段模型, 根据当前Ad Hoc网络节点分布情况, 将距离较远的通信节点之间的节点分成若干分段, 组成员存在于分段内, 如图1中的Seg1, Seg2, …, Segi。这样, 对每个分段分别管理, 当某分段路由失效时可以只针对这一分段进行路由重建, 而不需要整个网络都参与重建, 从而降低了Ad Hoc网络组播路由维护的开销。

在Ad Hoc组播路由分段模型中, 节点分为源节点、目的节点、中间节点和普通节点四种: (1) 源节点为某一路由的开始节点, 如图1中的节点S; (2) 目的节点为某一路由的目标节点, 如图1中的节点D1, D2, D3, …, Dj; (3) 中间节点为某一路由中相连两个分段的公共节点, 如图1中的节点M1, M2, …, Ml;4) 普通节点为某分段除了中间节点以外的节点, 如图1中的节点C1, C2, C3, …, Ck。

在某次路由中, 如果某分段内的普通节点是路由接收者时, 这些普通节点就变为目的节点。为了使Ad Hoc路由协议在有效性和效率之间取得平衡, 该模型每一分段中设两个主节点, 一般把每段的中间节点设置为主节点, 例如图1中的Seg2分段的两个主节点为M1和M2。分段中的主节点主要用于对组成员的管理与维护, 主节点的路由表上应维护该分段内的组成员节点的信息。分段内某一组成员脱离或者加入组, 都需要在主节点的路由表中得到体现。

2. 分段的确定

将网络划分成若干分段时, 协议需要以下主要信息。分段列表 (SList) , 中间节点列表 (MList) 。分段列表保存所有分段的信息, 中间节点列表保存所有中间节点的信息。分段Ad Hoc网络组播路由重建模型中分段列表和中间节点列表如图2所示。

3. 基于移动预测的分段Ad Hoc组播路由的建立过程

基于移动预测的分段Ad Hoc组播路由的建立过程和标准的组播路由协议一样, 主要分为路由请求, 路由转发和路由应答三个阶段, 但是在基于移动预测的分段Ad Hoc组播路由协议中, 采用了分段模型和LET预测模型, 需要对这三个阶段进行改进。

(1) 路由请求

路由的发起过程是由源节点发起Join-Query分组开始的。如果源节点一直有数据需要发送, 它将会周期性地发起Join-Query分组, 以更新网络路由。当源节点为中间节点时, 它首先检查中间节点路由表中是否有目的节点, 如果有, 就将Join-Query消息直接广播给该分段内的目的节点, 然后将Join-Query分组广播给该分段中另一个中间节点, 并由该中间节点向后面的分段转发Join-Query分组。当源节点为非中间节点时, 它会先把请求包传播给源节点所在分段的中间节点, 再由该中间节点来进行发送。

(2) 路由转发

当某一分组要从某一分段的一个中间节点转发到另一个中间节点的时候, 就可以通过SelRET=max (RET1, RET2⋅⋅⋅, RETi) 来发现更为稳定即RET值更高的路由。

基于移动预测的分段Ad Hoc网络组播路由的转发过程如图3所示。

(3) 路由应答

接收到Join-Query消息的组播组的成员节点, 它会将数据保存下Join-Query消息的反向路径记录, 选择一个前向路径, 创建Join-Reply分组, 如果该成员节点是中间节点, 它会直接将Join-Reply分组广播到同分段中的另一个中间节点, 否则, 它会先把Join-Reply分组广播给该分组的中间节点。收到Join-Reply分组的所有节点检查它是否是重复分组, 如果是则丢弃;否则, 当一个任何中间节点接收到一个非重复的Join-Reply, 它检查是否路由缓冲中下一个节点的ID是它自己的ID, 如果是, 则该节点处于通往源节点的路径上, 如果不是, 则转发, 直至到达源节点为止。

4. 性能分析

标准ODMRP协议为了建立转发组和维护转发组成员, 发送节点必须周期性发送路由请求包, 同时该路由请求包是以洪泛的形式发送, 这将对网络造成不小的负担。尤其是在网络规模扩大或网络的负载较大的时候, 协议的性能将由于频繁的洪泛包而急剧下降。而在基于移动预测的分段组播路由重建模型中, 将网络分成若干个分段, 只有中间节点才对接收到的洪泛包进行处理, 分段内其他普通节点对这些洪泛包并不做出反应, 从而有效地减少了分组的洪泛, 并有效减少了协议的控制开销。

下面以图4为例, 分析比较基于移动预测的分段组播路由重建模型与标准ODMRP协议路由重建模型的性能。

该路由链路如图4所示, 从源节点S出发, 经过C1, C2, M1, C3, M2, …, Mi到达目的节点D, 假设节点C2因故要离开该组播组, 那么从C1到C2的链路将出现断路, 此时就需要进行路由重建。

标准ODMRP组播路由协议进行路由重建过程如下:

(1) 源节点S在节点C2离开组播组以后才进行路由重建;

(2) 源节点S广播路由请求Join-Query, 每个节点都将收到路由请求, 并转发;

(3) 目的节点D收到路由请求后, 发送路由应答Join-Reply, 并按照向前路径中最短路由建立反向转发组; (4) 路由重建后的路径:C1, C4, M1, C3, M2, …, Mi。

基于移动预测的分段组播路由重建模型重建路由的过程是:

(1) 在节点C2所在的链路失效前, M1开始进行路由重建;

(2) 源节点S广播路由请求Join-Query, 在seg1段中的每个节点都将收到路由请求, 并转发;

(3) 公共节点M1收到路由请求后, 将不再转发, 而是发送路由应答Join-Reply, 并按照向前路径中最短路由建立反向转发组;

(4) 路由重建后的路径:C1, C4, M1, C3, M2, …, Mi。

通过分析上述两个重建路由的过程, 可以发现路由重建后的节点路径是一样的, 但是在效率方面: (1) 标准ODMDRP协议在路由失效后才进行路由重建, 而基于移动预测的分段组播路由重建模型在路由失效前已经开始进行重建了; (2) 源节点S发送路由请求Join-Query时, 标准ODMRP协议需要网络中的每个节点都转发该请求包, 而基于移动预测的分段组播路由重建模型只需要在失效的节点所在段的区域内转发请求包; (3) 标准ODMRP协议需要路由请求包到达目的节点后才进行路由应答, 而基于移动预测的分段组播路由重建模型只需要路由请求包到达了失效节点所在段的公共节点后就可以进行路由应答。由此, 我们发现对于基 (下转第57页) (上接第48页) 于移动预测的分段组播路由重建模型, 通过检查各条路由对应的保持时间RETi, 可以在路由失败之前进行路由重建, 使上层业务保持连续性;当某分段的链路断开时只需要针对这一分段进行链路重建, 而不需要整个网络都参与, 减少了路由的重建时间, 降低了包丢失率, 提高了整个网络的数据传输效率。

此外, 在标准ODMRP协议的路由算法中, 当某条链路断开需要重新建立路由时, 时间复杂度为O (2h) =O (h) , 其中h为该条路由的链路数量。而在基于分段和预测的Ad Hoc网络组播路由重建模型中, 由于采用了分段的思想, 当某条链路断开需要重新建立路由时, 时间复杂度为O (2l) =O (l) , l为路由中某一分段内的链路数量, 当网络分为m段时, l≈h/m, 故时间复杂度又可表示为O (2 h/m) =O (h/m) 。由于m大于1, 所以本模型建立转发组的时间比标准ODMRP协议时间要短。

(三) 小结

鉴于组播的路由建立需要大量的洪泛控制信息, 本文考虑Ad Hoc网络中节点的移动性因素, 提出了基于移动预测的分段路由重建模型, 利用链路连接保持时间模型在路由失效前, 分段进行路由重建, 以减少控制信息的数量, 降低节点能量的消耗, 提高了整个网络的数据传输效率;但是由于中间节点的出现, 所以使得本文提出的分段路由模型的管理成本有所增加。

参考文献

[1]吴东亚, 侯紫峰, 侯朝桢, 等.移动自组网按需机制路由协议路径失效预测和局部修复算法[J].计算机工程, 2004, 30 (3) :102-103.

[2]郑少仁, 王海涛, 赵志峰, 等.Ad Hoc网络技术[M].北京:人民邮电出版社, 2005.