摘　要：提出一种适用于IP视频会议" title="视频会议">视频会议的组播" title="组播">组播——基于分层排列图的混合式组播。详细介绍了其拓扑结构" title="拓扑结构">拓扑结构,以及控制拓扑和数据拓扑的构建过程,并对该组播技术进行了性能分析。 

关键词：视频会议系统混合式组播 排列图 IP组播岛 

    IP视频会议是利用视频技术和IP数据通信技术通过IP网络在两点或多点之间建立可视通信,实现图像、语音及数据交流的一种会议形式。IP视频会议系统因其效率高、成本低、业务提供方式灵活等优势将代替传统的基于电路交换的视频会议系统。然而要解决视音频数据在IP网络上实时传输的问题,并为视频会议系统提供一定的QoS是一个技术难题,也是目前的研究热点。
　　本文把IP组播与应用层组播" title="应用层组播">应用层组播结合起来并采用分层排列图结构,提出了一种适用于IP视频会议的混合式组播方式——基于分层排列图的混合式组播。
1 混合式组播
1.1 问题的提出
　　IP视频会议属于传输数据量大、对带宽要求高的服务,为实现它的即时通信和互动沟通功能必须保证音视频等数据在IP网络上的实时传输。IP组播技术能够有效地解决多点对多点数据通信的网络带宽问题。相对于单播和广播方式来说,它能显著节省网络带宽,提高数据传输的效率,同时提高服务的质量,因而它较适合于IP视频会议系统。当前最流行的IP视频会议标准H.323就采用了IP组播技术。然而,由于技术、市场、需求等原因,IP组播并没有在Internet上得到广泛应用^[1],使得目前只有少数用户在局域范围(称为IP组播岛)内可以使用 IP 组播技术。因此基于IP组播技术的视频会议只能在这些相互孤立的组播岛上进行,与会成员受到很大的限制。
　　正是因为IP组播未能在Internet上广泛应用,近年来人们提出了十几种应用层组播方案,其中适用于IP视频会议的系统有NARADA^[2]和ALMI^[3]。NARADA只能应用于与会成员很少的情况。ALMI中,当有多人发言时易形成网络瓶颈,故在一定程度上限制了视频会议的规模。
　　相对于应用层组播来说,IP组播能更多地节约网络带宽^[4]、可靠性更好且数据转发速率更高。而相对于IP组播来说,应用层组播与现今网络结构相符合,使用时不需变动现有的网络协议与硬件,部署相对容易,同时具有较好的扩展性,可以适应网络条件的动态变化。它已成为目前最可能解决IP组播中的路由器瓶颈问题的方案。为了在IP视频会议中充分利用应用层组播和IP组播的优势,在此把二者结合起来,称为混合式组播。本文以后所提到的混合式组播均以IP视频会议这种特殊应用场合为例。
1.2 拓扑结构
　　在采用混合式组播的IP视频会议中,与会成员组成如图1所示的拓扑结构。在每个IP组播岛内,与会成员之间的数据传输使用IP组播,并选定一个与会成员作指定成员(Designate Member,DM),把岛内除DM外的与会成员称为其他成员(Pertinent Member,PM),DM是岛内成员与岛外成员之间通信的桥梁。岛外成员与DM参加应用层组播叠加网^[5](包括一个控制拓扑和一个数据拓扑)的构建,将其称为应用层组播成员(ALM Member,AM),AM之间的数据传输使用应用层组播。IP组播岛中PM通过DM与叠加网相连,DM与岛外成员之间的数据传输采用应用层组播方式,与岛内的成员之间的数据传输使用IP组播的方式。DM负责将来自叠加网的数据以IP组播方式传送给组播岛中PM,PM的数据也通过IP组播方式传送到DM,由DM以应用层组播的方式发送给叠加网上的其他与会成员。
　　DM的选取原则:岛中第一个参加会议的成员被设为DM,以后可以根据某种策略(如参加会议的时间最长者或物理位置“中心”点成员,或剩余带宽资源最多者等)选定某个成员作为DM。如果DM离开,则根据某种策略从岛内的PM中选择一个作DM。  

图1 混合式组播拓扑结构图  

2 基于分层排列图的混合式组播 

2.1 控制拓扑构建
　　在数学上,(n,k)维排列图^[6](用An,k表示,其中n和k是自然数,1≤k≤n-1。令 表示集合{1,2,……n}中k个符号的排列,An,k定义为无向图(V,E),其中:

    一个排列图实例A_4,2的拓扑结构如图2所示。排列图A_n,2仅能容纳n(n-1)个主机。为使系统可容纳任意多主机,可将参与主机组合成多个An,2结构,这些An,2按照树形结构连接在一起,称为分层排列图结构^[6]。  

图2 排列图A4,2的拓扑结构图


图3 以与会主机为单位的拓扑结构图

图4 以排列图  

　　混合式组播的核心任务是为AM完成拓扑(包括数据拓扑和控制拓扑)的构建。由于网络状况的动态性,以及客户端数量与客户端加入系统时间的不确定性,当前的应用层组播方案一般需要每个结点定期与其他全部或一定比例的结点交换控制信息,以了解其他结点的状态,形成控制拓扑,保障数据拓扑的健壮性。在结点个数逐渐增加时,网络上的控制信息数量会占用大量的带宽资源。应用层组播的数据拓扑可分为二大类:信源树和共享树。信源树必须为每个组播源保存路由信息,这样会占用大量的系统资源。共享树传输延时较大。IP视频会议系统属于实时交互应用,视音频数据占据很大的带宽,并且对端到端传输延迟和网络抖动的要求很高,需要寻找一种既可以减少交换控制信息又可以保证视音频数据实时传输的拓扑构建方式。为利用排列图的优越特性(如结点和边的对称性、故障恢复能力和容错能力、可以嵌入独立的组播树等),这里采用分层排列图的结构来组织混合式组播中的AM。
　　本文先按照文献[6]中的协议设计方法把参与IP视频会议所有主机中的AM组织成分层排列图结构,作为混合式组播的控制拓扑,并在主机申请加入会议时根据其带宽处理能力和一定的算法规定它的入度最大" title="最大">最大值和出度最大值,它们分别也是剩余入度和剩余出度的初始值。每个分层排列图都对应一棵以排列图为结点单位的树。如图3所示的以与会主机为单位的拓扑结构是一个由3个A4,2结构(AG1、AG2和AG3)所组成的分层排列图。图3也可以看作如图4所示的以排列图为单位的树结构,即以排列图AG2为根、以AG1和AG3为叶子的一棵树状拓扑。设在分层排列图中,父排列图AGi中的结点i1和i2分别是子排列图AGj的数据源结点和备用数据源结点,AGj中的结点j1和j2分别是i1和i2对应的根结点,则在树拓扑中父排列图AGi与子排列图AGj的连线实际上包括2条:(1)i1与j1之间的连线;(2)i2与j2之间的连线。图4中父排列图AG2与其子排列图AG1之间的连线有2条:(1)图3中AG2的a14与AG1的a31之间的连线;(2)图3 中AG2的a24与AG1的a41之间的连线。各排列图之间的连线在混合式组播中并不一定作为数据传输路径。
2.2 数据拓扑构建
　　基于分层排列图的混合式组播的控制拓扑是分层排列图,其数据拓扑在此基础上构建,具体算法如下:
　　设某排列图中的与会成员主机ai,j发言,首先把分层排列图对应的树结构转换为以ai,j所在的排列图为根的树结构,然后执行步骤(1)～(2)。
　　把ai,j所处的排列图作为当前排列图,在当前排列图中用文献[6]中的算法生成以ai,j为根的组播树,并修改当前排列图中所有结点的剩余入度值和剩余出度值。 

(1)为当前排列图的所有子排列图选择数据源、备用数据源和根结点(为描述方便起见,这里分别把它们记为s1、s2和r)。为某个子排列图选择数据源s1、备用数据源s2和根结点r的算法如下:
　　①令与会成员主机结点子集A={am,n|am,n属于当前排列图,ai,j与am,n相邻接并且am,n的剩余出度值大于0}。
　　·若|A|>1,则在A中选择剩余出度值最大者作为数据源s1,次大者作为备用数据源s2,此时一定可以选取合适的根结点使得组播树独立。
　　·若|A|=0,则选择在当前排列图中选择最大剩余出度结点作为数据源s1,次大者作为备用数据源s2。
　　·若|A|=1,则选择A中的结点作为数据源s1,选择当前排列图中其他成员中最大剩余出度结点作为备用数据源s2。
　　②s1和s2的剩余出度值分别减1。
　　③在此子排列图中先后选取数据源s1对应的根结点r,并把选出的根结点的剩余入度值减1。当s1不能正常工作或失效时,s2作为r的数据源结点。选取根结点时既要考虑结点的剩余出度值和剩余入度值,又要注意尽量保证组播树的独立性。如果能保证组播树独立性的结点的剩余入度值全为零,则选取子排列图中的剩余入度值最大者。
　　④在此子排列图内根据文献[6]中的算法生成以r为根的组播树,并修改相应结点的剩余出度值和剩余入度值。
　　(2)如果还有再下一级的子排列图,则令ai,j=当前排列图的相应子排列图的根结点的r,转(1);否则,结束。
　　图3给出了AG1中的a31和AG2中的a41发言时根据以上算法为实现应用层组播建立的组播树,分别以虚线和实线表示。在AG1、AG2和AG3中分别由三个DM(a34、a42、a41)作为IP组播岛的数据源结点,组播岛内的IP组播树分别以它们为根建立,由它们传输到IP组播岛中的PM。IP组播岛中对应的IP组播树在图3中没有画出。
2.3 性能分析
　　与当前其他的应用层组播相比,在IP视频会议中采用基于分层排列图的混合式组播技术,有以下优点:
　　(1)增强了系统的可扩展性。系统只需维护树形式的分层排列图即可,它就是应用层组播的控制拓扑,由它生成数据拓扑。IP组播岛内的数据传输由IP组播技术实现,系统只需选定DM,由DM来作为岛内成员与岛外成员之间通信的桥梁。控制信息数量大大减少,节约了网络带宽,使更多的用户可以加入会议。
　　(2)提高了系统的容错能力,减少了网络抖动。由于在An,2中可以建立n-2个独立的组播树,在用户带宽资源足够丰富的情况下只要发言用户数≤n-2就可以保证组播树的独立,使得每个用户只在最多一棵组播树上作为中间结点。这样一个用户出现故障最多影响一个组播树中的数据传输。分层排列图的这一性质使基于分层排列图的混合式组播能提高视频会议系统的容错能力,减少数据传输过程中的网络抖动。
　　(3)缩短了用户加入会议的时间。由于AM组织为分层排列图结构,IP组播岛外的用户加入会议的复杂度为O(log(N)),其中N表示IP视频会议系统中AM数目。组播岛内的用户加入更简单,它不需要了解岛外AM的任何信息就可以加入它所属的IP组播岛,通过该岛上的DM与岛外与会成员传输数据,因而一个申请加入会议的主机可迅速地完成加入过程。
　　本文为IP视频会议系统提供了一种简单、可靠的混合式组播方案。一方面能充分利用参与会议的主机资源,使系统能支持更多的用户参加会议,另一方面也为视频会议系统中视音频数据在Internet上的实时传输提供较好服务质量保障。
参考文献
1 李 晟,余镇危,潘 耘.应用层组播综述.计算机应用研究,2004;(11):14～17
2 Chu Y H,Rao S,Zhang H.A case for end system multicast.　ACM SIGMETRIC,2000;(6):1～12
3 Pendakaris D,Shi S.ALMI:An application level multicast in-frastructure.In:The 3rd USENIX
  Symposium on Internet Tec-hnologies and Systems,San Francisco,CA,USA,2001:49-60
4 Banerjee S,Bhattacharjee B,Kommareddy C.Scalable appli-cation layer multicast.In:SIGCOMM′ 

 02,2002:205～217
5 Yeo C K,Lee B S,Er M H.A Survey of application level multicast techniques.Computer
  Communications,2004;(27):1547～1568
6 田瑞雄,向 哲,李 星.基于分层排列图结构的流媒体应用层组播系统.
  清华大学学报(自然科学版),2004;44(4):493～497