《武汉工程大学学报》 2010年09期
90-93
出版日期：2010-09-30
ISSN:1674-2869
CN:42-1779/TQ
一种应用层组播拓扑的设计
0引言近年来,由于IPTV直播、视频监控等应用的需求,支持实时多媒体传输的组播通信技术的研究和方案日益增多.IP层组播能够在通信时保证在每一条网络链路中只存在一份数据报文,能够极大地节省网络带宽,但由于组播需要底层路由器进行全面的升级支持如DVMRP［1］和IGMP［2］等路由协议,在部署方面存在较大的困难［3］,同时由于组播路由器要为每一个组播组维护路由状态信息,扩展性不好;另外,组播的可靠性、QOS、拥塞控制等方面目前仍处于研究阶段,因此IP组播并没有得到广泛应用.于是,出现了一些对IP层组播的替代方案［45］.有研究者提出将对组播通信功能的支持从IP层的路由器转移到终端系统中,由应用层的终端系统来负责组成员管理、报文的复制和分发,并称之为应用层组播［6］:Application Level Multicast或者Overlay Multicast.应用层组播利用现有的网络传输协议,并不需要网络的底层路由和传输结构作调整,不存在部署困难的问题.同时应用层组播的路由路径可以随着网络状况的变化动态地调整,应用程序也可以参与路由策略的制定,能实现IP组播所没有的灵活性和扩展性.1应用层组播ALMIP应用层组播通常有两种实现方式:一种是将路由和传输功能放在参加组播通信的各个主机中,组成P2P的overlay网络;另一种则是由分布在网络中的多个组播节点完成组播功能,每个节点可以为多个客户端同时服务.第一种方法可以做到完全分布,第二种方法则可以提高组的规模.在应用层组播组的管理方面,根据建立应用层组播拓扑结构时采用的方案,可采用两种管理方式:网状优先(mesh first)和树状优先(tree first)［6］.网状优先的系统会首先在节点上建立一个网状的拓扑结构,节点间按照某种路由协议来生成路由树.网状优先的模式下,系统的拓扑结构是确定的,但是路由树结构是不确定的.树状优先系统中,节点直接通过某种算法在树形关系中选择其各自的父节点,并检测和避免环路的产生.网状优先的系统能通过重新选择邻居、更改拓扑关系的方式,在很大的范围内更新路由树的结构.因此,在多源的系统中,网状优先系统相对更加稳固,能更加灵活的对不同源建立不同的组播树.树状优先的方案有ALMI［7］等,大规模的网状优先应用层组播方案的代表有NICE［8］和Zigzag［9］,它们对单个数据源组播的问题,都使用了“分层”(Hierarchical)和“分群”(Cluster)的思路.大部分组成员位于分层结构的底层,并只和少量固定数目的节点存在联系,这样就大大降低了大部分组播成员的处理开销.2MCR组播拓扑本文提出的组播环拓扑MCR(Multicast Cross Rings)将应用层组播节点以集群的方式管理起来,建成以“环”为基本集群单元的层次化管理拓扑结构,并且在此拓扑结构基础上建立组播路由树.2.1树状层次拓扑MCR采用的层次化树形结构的管理拓扑,分两个级别管理所有节点间的逻辑关系.第一级别是树形拓扑,第二级别是环形拓扑(集群子系统).如图1所示,每个树形节点均为一个集群子系统,每个集群子系统保持环状拓扑的多个节点.图1树状的层次拓扑
Fig.1Hierarchy topology treeMCR将节点组织为多个cluster,再以多叉树的方式来组织多个cluster形成层次化结构,其中每个cluster均为采用环状结构组织的多个节点集合,如图1(b)所示.第9期王立,等:一种应用层组播拓扑的设计
武汉工程大学学报第32卷
若用k表示每个cluster的最大下级cluster数,则MCR是一个由多个cluster组成的k叉树.MCR的层次拓扑随着节点的加入而逐渐扩展,节点首先尝试加入顶层cluster,如果失败则逐级向下寻找一个有空闲的cluster加入.组建层次拓扑的组织基本准则包括:(1)MCR是由多个cluster组成的k叉树(k＞=3),每个cluster最多有k个下级分支cluster;(2)最先加入的2k个节点组成的cluster为MCR的顶点L0,后续加入的节点寻找L0的一个分支加入;(3)每个cluster环最多可包含2k个节点,其中两个节点为RP节点(互为备份的集中点),其他节点为普通节点(L0环没有RP节点);(4)任何一个节点最多可以同时属于2个cluster环,即两个关联(相交)的cluster最多有2个公共节点;如图2所示,新节点在L0下属子环中寻找一个未满的环如图2(c)所示,或新建一个环如图2(b)所法加入,形成共2层的拓扑.图2拓扑组织过程示例(k=3)
Fig.2Contraction example(k=3)Li表示某环在分层拓扑中的层编号,L0是最顶层的环,也是一级树形拓扑的根.如果要保证一级拓扑树的平衡性,L0的位置可能被拓扑管理算法更新.定义:RS表示一个环,Ai为该环上所有节点,W(Ai)为节点的重量,普通节点的重量为2,RP节点X的重量计算方式为:W(X)=∑Ai∈RS,AiRPW(Ai)/（2+2）如图3(b)所示,通过计算可知Li+2上RP节点的W为6,Li+1上RP节点的W为14,Li上RP节点的W为30.事实上W值也代表了该环及下属环链所包含的总的节点数.定理:某环的RP节点的W即为该RS环及其下属子环所含总的节点的数量.图3节点与环的关系
Fig.3Relationship between nodes and clusters2.2层数与节点数的关系若用N表示拓扑中总的节点数,H表示层次拓扑的层数.如图3(a)所示,满环情况下,将每个环的RP节点仅在主环上统计一次,某顶层环节点数为2k,其下属各个环的节点数均为2k-2,第i层的总环数为(k-1)i.则满环情况下,H层拓扑容纳的最大节点数为:Nmax=∑H-1i=0(∑(k-1)ij=0Ri,j)=2k+
(k-1)(2k-2)+…+(k-1)H-1(2k-2)=
2∑Hi=1(k-1)i+2=
2(k-1)(k-1)H-1k-2+2令j=k-1,k＞=3,即j＞=2,则:(1)层数确定时的最大节点数为Nmax=2jH+1-1j-1;(2)节点数确定时的最小层数为Hmin=logjj-12N+1-1.完整的MCR拓扑在L0层实际可以由k个图3(a)所示的H层子环拓扑组成,因此,MCR的总层数为HO=H+1,全网最大节点数为NOmax=kNmax,即:NOmax=2jH+1-1j-1k=2j+1j-1(jHO-1)于是,节点数确定时的MCR最小层数为:HOmin=logjj-12(j+1)N+13MCR拓扑维护根据前面描述的拓扑组建原则,新节点加入时,首先找到L0环,请求加入该环,当L0环上的节点数已达到2k时,如果L0没有子环则新建一个,否则通过子环选择算法在其k个下属子环中选择一个加入.3.1子环选择节点加入时,应保证拓扑树的总层数最小、枝的数量最少,即树最矮,从而使组播路由的跳数最小.此算法的节点加入拓扑的顺序图4所示,层次结构中将依次填满L0、所有L1、所有L2…….拓扑包含的所有环仅有一个环的节点数小于2k,每次节点加入的算法就是找到层次拓扑中节点数小于2k的这个环,并加入该环.图4拓扑扩展方式
Fig.4Topology growing path子环选举算法如下:(1)遍历L0环的节点重量集合W0,计算系统总节点数N=∑wi∈W0wi/2;(2)计算新增一个节点后的总层数最小值HOmax=logjj-12(j+1)(N+1)+1;(3)计算子环所内包含的最大节点数Nmax=2jH+1-1j-1,其中H为子环层数,所以H=HO-1;(4)找到L0环上w最大且小于Nmax的节点Xm,新节点向该节点(即以其为RP的环)发起加入子环的流程.(注:若所有w均为2将建立新环.)3.2组播路由应用层组播分发的关键问题是节点度与路由深度的平衡.节点度的表示节点分发数据流时的输出端连接数,路由深度表示数据流从源端到达接收端经过的转发次数.组播路由要保证数据报文通过组播数据源到达加入该组播组的各个节点,同时要保证达到不同的节点时的转发的跳数受控,从而提高转发效率.假设环中的各个节点之间通过直接或间接的网络层路由互相可达,因此环内的节点通信距离为1.若规定环间节点的通信通过RP节点分发,则环间节点的通信距离与通信通过的环的数量相同.根据MCR的组网算法,在节点加入流程中,采用最短树算法保持网络的总环数最少时,MCR的拓扑树高度被算法控制为HOmin=logjj-12(j+1)N+1,因此在此拓扑基础上建立的路由转发数可以保证最差情况下的路由跳数能够受到限制.如图5(b)所示,一个组播源source节点发送组播数据,有两个destination节点希望接收该组播数据,即加入该组播组.其中一个destination节点与source处于同一子环内,另一个destination节点位于另一个子环.此时组播分发路径为:source节点将数据流发送给其所在RM环的RP1节点,该RP1节点将流转发给同一RS环内的destination1节点,同时将流分发给上级RM环的RP2节点.RP2将数据流转发给RP3,RP3将数据转发给RP4,RP4将数据转发给最终目的destination2.分发采用的路由树如图中箭头所示,对于图5中所示的3层拓扑,路由树的最大深度为5.图5组播分发路径
Fig.5Multicast tree4MCR的性能分析MCR的复杂度分析如下:(1)每个节点可能存在于两个环中,每个环有2k-1个邻接点,所以节点的度最大值为2(2k-1)-1=4k-3平均度为2k+1而在满环配置情况下,中间节点的度均为4k-3最外环节点的度均为2k-1因此总度和平均度分别为:总度:
［2k+(k-1)(2k-2)+…+
(k-1)H-2(2k-2)］(4k-3)+
(k-1)H-1(2k-2)(2k-1)=
2jH+1-1j-1(4k-3)-2jH(2k-2)平均度:
2jH+1-1j-1(4k-3)-2jH(2k-2)2jH+1-1j-1=
4k-3-2jH+1(j-1)jH+1-1
4k-3-2(j-1)=2k+1(2)路由的跳数即转发次数受控,因此组播分发的端到端延时受控为O(logN)级别.因为总层数为logjj-12(j+1)N+1因此最坏情况的组播转发跳数为2logjj-12(j+1)N+1(3)加入和离开拓扑的控制开销为拓扑的层数,即O(logN)5结语MCR采用网状优先的拓扑组织形式,将节点组成局部cluster后,再将cluster建为一个层次化树形拓扑结构,并在此层次化树形集群系统基础上建立组播树.这种拓扑结构适合稳定节点的组网,大量组播源数据源在共享拓扑上建立起不同的源组播最短路径树.拓扑管理中节点的离开和加入仅仅影响局部cluster内的节点和少量上级节点,对网络全局拓扑不产生影响.并且通过设置两个RP节点的方式保证节点失效时的业务连续和快速恢复.MCR采用与NICE和Zigzag类似的层次化拓扑,将节点组成多个小集群系统,将小集群系统构建成层次化拓扑,并在拓扑基础上建立组播路由树.与NICE和Zigzag不同的是,MCR中的节点自上而下加入层次化拓扑,而且节点最多同时出现在两个相邻的层中,因此最多需要维护的邻接关系为4k-3.NICE和Zigzag中,节点自下而上加入拓扑,并且节点可以同时出现在多个层中.MCR能提供基于应用层组播的S2S服务对等网络,网络的节点都是服务器.客户端可以通过任何一个节点接入,从而可以访问到整个网络的资源,即资源是由整个网络提供的.