结点笔记本变无线路由器
笔记本变无线路由器 时间:2021-05-23 阅读:()
ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,Vol.
19,No.
4,April2008,pp.
925945http://www.
jos.
org.
cnDOI:10.
3724/SP.
J.
1001.
2008.
00925Tel/Fax:+86-10-625625632008byJournalofSoftware.
Allrightsreserved.
基于双向令牌的可扩展及可靠的群组成员管理王国军+,吴敏,周薇,贺建飚,陈松乔(中南大学信息科学与工程学院,湖南长沙410083)ScalableandReliableGroupMembershipManagementwithBi-DirectionalTokensWANGGuo-Jun+,WUMin,ZHOUWei,HEJian-Biao,CHENSong-Qiao(SchoolofInformationScienceandEngineering,CentralSouthUniversity,Changsha410083,China)+Correspondingauthor:Phn:+86-731-8877711,Fax:+86-731-8877711,E-mail:csgjwang@mail.
csu.
edu.
cnWangGJ,WuM,ZhouW,HeJB,ChenSQ.
Scalableandreliablegroupmembershipmanagementwithbi-directionaltokens.
JournalofSoftware,2008,19(4):925945.
http://www.
jos.
org.
cn/1000-9825/19/925.
htmAbstract:GroupcommunicationshavebeenstudiedinthewiredInternetformanyyearsandremainaveryhotresearchtopic,especiallyonextendingtheexistingachievementsintomobileandwirelessnetworkenvironment.
Thispaperidentifiessomeinterestingproblemsinmobilegroupcommunicationsregardingdynamicgroupmembershipduetomemberjoiningandleaving,dynamiclocationsduetonodemobility,anddynamicnetworksduetonode/linkfailures.
Theseproblemsaresolvedbyproposingaring-basedhierarchyofproxieswithbi-directionaltokens.
Theproposedhierarchyisacombinationoflogicalringsandlogicaltrees,whichtakesadvantageofthesimplicityoflogicalringsandthescalabilityoflogicaltrees.
Moreimportantly,suchacombinationmakestheproposedprotocolbasedonthishierarchymorereliablethantheexistingtree-basedprotocols.
Theoreticalanalysisandsimulationstudiesoftheproposedprotocolshowthat:(1)Itscalesverywellwhenthesizeofagroupbecomeslarge;(2)Itisstronglyresilienttofailuresthatoccurinthenetwork.
Itisparticularlysuitableforthoseserviceprovidersandnetworkoperatorswhichhavedeployedtheirmachinesinahierarchicalsetting,whereeachmachinecanbelocallyconfiguredtoknowtheinformationaboutitssiblingandparentmachines.
Keywords:groupcommunications;groupmembershipmanagement;multicast;reliability;bi-directionaltokens摘要:面向有线因特网的群组通信已研究多年,目前仍是研究热点之一,尤其是将现有研究成果扩展到移动与无线网络环境方面.
研究了移动群组通信,该问题涉及群组成员关系动态性(成员加入及退出)、成员位置动态性(移动主机的移动性)和网络动态性(结点或链路出错).
提出了适合于移动群组通信的基于双向令牌的层次环模型(也称为层次环结构)以解决该问题.
该模型是逻辑环与逻辑树的结合模型,它利用了逻辑环的简单性和逻辑树的可扩展性.
更为重要的是,这样的结合使得基于层次环结构的群组通信协议比现有的基于树结构的协议更可靠.
理论分析和SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNos.
60503007,90718034(国家自然科学基金);theNationalScienceFundforDistinguishedYoungScholarsofChinaunderGrantNo.
60425310(国家杰出青年科学基金);theProgramforNewCenturyExcellentTalentsinUniversityofMinistryofEducationofChinaunderGrantNo.
NCET-06-0686(新世纪优秀人才支持计划);theProgramforChangjiangScholarsandInnovativeResearchTeaminUniversityofChinaunderGrantNo.
IRT-0661(国家教育部长江学者与创新团队发展计划)Received2006-08-03;Accepted2007-05-24926JournalofSoftware软件学报Vol.
19,No.
4,April2008模拟研究表明:(1)当群组规模增大时,该协议的可扩展性很好;(2)该协议具有很高的可靠性.
该协议特别适合于服务提供者和网络运营商将其计算设备分层次部署的情况,这时就要求每台计算设备都能局部化地维护其兄弟和父亲设备的信息.
关键词:群组通信;群组成员管理;组播;可靠性;双向令牌中图法分类号:TP393文献标识码:A近年来,随着移动计算与无线通信技术的飞速发展,由有线因特网和多种无线网络如无线局域网、蜂窝网络和卫星网络组成异构型的网络,即通常所说的移动因特网,成为了研究热点[1].
但是在这种网络环境中,许多具有挑战性的问题将比在有线网络中更难以解决,如可扩展性和可靠性.
其中一个典型应用是将数据从一个或多个发送者同时传送给多个接收者的群组通信应用,比如面向新闻信息、股市行情、天气预报、交通状况的数据广播应用和基于网络的多媒体流式应用.
但是研究表明,在移动因特网中实现高效的群组通信非常困难[24].
现有的群组通信系统(groupcommunicationsystem,简称GCS)[5,6]主要是为传统的广域网而设计的,没有考虑把移动主机(mobilehost,简称MH),如笔记本电脑、个人数字助理(personaldigitalassistant,简称PDA)、移动电话和移动可视电话当作群组成员的情况,因此无法保证在MH存在时也能高效工作.
实际上,广域网中固有的问题,如延迟大和不稳定性,仍然存在于移动因特网中.
而且,在引入MH以后可能出现频繁断开连接、频繁切换、频繁发生错误等更为困难的问题.
本文基于我们在文献[7]中的前期工作,提出了适合于移动群组通信的基于双向令牌的层次环模型(也称为层次环结构).
一方面,该模型是逻辑环与逻辑树的结合模型,它利用了逻辑环的简单性和逻辑树的可扩展性;更为重要的是,这样的结合使得基于层次环结构的群组成员管理协议比现有的基于树结构的协议更为可靠.
当树结构中某结点出错时,树结构会被打破成多棵子树,所有子树的根结点必须找到新的父结点重新附着到树结构上.
因此,树结构存在单点错误问题(singlepointoffailureproblem).
当在层次环结构中出现错误结点时,该结构也会被打破成为多个子结构.
但是,由于该结构中的每个代理维护两类候选邻居(候选的兄弟结点与候选的父结点),该结构能够尽快地维护它的完整性,从而可以解决树结构中的单点错误问题.
另一方面,该模型结合了应用层组播和网络层组播的解决方案,既利用了网络层组播的高效性,又利用了应用层组播的易于部署的特点.
从系统实现的观点看,现有两种基本的因特网组播通信技术:基于网络层的组播(以下简称IP组播[7])和基于应用层的组播(以下简称应用层组播[8]).
IP组播提出得早,组播效率高,但应用不广泛.
其主要原因是:(1)部署时需要升级所涉及的网络中所有的路由器,因而是对现有网络基础设施的一种"巨变";(2)只提供局部的群组成员管理[9],对某些需要全局成员信息的应用则不适合;(3)由于组播树的维护是基于一种平面的网络结构,因而难以扩展到大规模的组播通信中.
针对第3点,文献[10]提出了按需分支组播的方法.
该方法只要求处于组播树分枝处的路由器和本地链路上有组成员的路由器保存组播树的有关信息,将基于平面的组播树维护方式转变为层次型结构的维护方式,从而提高了可扩展性.
为了从IP组播的困境中走出来,近几年提出了大量的应用层组播方案.
由于应用层组播只要求网络提供单播服务,其他工作如组播树的维护、组播包的复制都在称为"叠加网"中的主机而不是在路由器中完成,因此部署比较容易,但是其效率可能不如IP组播高,且难以扩展到大规模网络环境中.
本文所提出的层次环模型中的结点根据实际需要可以是传统的IP组播中使用的路由器,也可以是新型的应用层组播中部署的主机.
本文第1节介绍相关工作.
第2节概述所提出的成员管理协议.
第3节和第4节分别描述所提出的成员管理协议中的两个子协议:成员信息传播子协议和拓扑结构维护子协议.
第5节分析层次环模型的可扩展性及可靠性.
第6节通过大量模拟实验给出协议的性能评价.
第7节总结全文.
1相关工作群组通信系统提供面向一组进程的通信服务.
群组是指该组进程,这些进程被称为该群组的成员.
进程可以自愿加入或退出某群组,或者因为出错而离开某群组.
群组的成员关系信息是指该群组中当前活跃的进程/成员王国军等:基于双向令牌的可扩展及可靠的群组成员管理927列表,该列表通常称为"视图".
GCS能够有效地简化容错分布式应用的编程难度.
GCS的一个重要任务是群组成员管理服务,即当成员加入、退出、切换或出错事件发生时维护成员关系信息;GCS的另一个重要任务是组播通信服务,即将信息从一个或多个源结点高效地传送到群组中的所有活跃进程.
群组成员管理算法主要分为3大类:(1)基于广播的算法[11];(2)基于协调者的算法[12];(3)基于令牌的算法[13].
基于令牌算法的基本思想是,把群组成员组织成一个逻辑环,然后让令牌环绕逻辑环以传播成员消息.
但是,基于逻辑环的算法无法很好地扩展到大规模群组通信环境中.
为了提高成员管理算法的可扩展性,研究者提出许多可扩展的成员管理模式.
成员角色模式[14]区分核心成员、客户成员和汇点成员.
Spread系统[15]集成了两个层次的协议:第1层是局域网中的Ring协议,第2层是广域网中的Hop协议.
一些基于多层的层次结构模式提供了更好的可扩展性方案.
Transis系统[11]把广域网看成组播簇结构,每个簇表示可以通过广播或组播硬件进行通信的计算机域.
通过将所有簇中挑选的代表结点形成层次结构来组织这些簇.
结构中的每一层可以看作是它以下各层的抽象,并维护它所在层的群组服务.
该系统使用抽象方法使得群组服务在广域网中具有好的可扩展性.
但是,由于高层域的代表结点实际上是最底层域中的服务器,这加重了服务器处理不同层次群组服务的负担.
特别地,如果代表结点出错,则会影响到该代表结点涉及的所有群组域.
CONGRESS系统[16]把广域网看作由域组成的层次结构.
每个域由一个CONGRESS服务器提供服务,包括局部成员服务器(localmembershipserver,简称LMS)和全局成员服务器(globalmembershipserver,简称GMS),以提供弱一致性的成员信息.
LMS设置在每个主机上为其客户提供服务.
GMS设置在树结构中,高层GMS实际上就是底层的LMS.
该结构被称为基于代表结点的树层次结构.
CONGRESS系统的新颖之处在于它的客户-服务器方法:群组成员服务由指定的成员服务器提供,但它们本身不是任何群组的成员.
作为成员参与某个或某些群组的进程成为成员服务器的客户.
客户发送请求给它的服务器以加入或退出特定的群组,而成员服务器发送成员视图给它的客户.
这种方式使得该协议在群组个数和每个群组中的成员个数上的可扩展性都非常好.
Moshe系统[17]扩展了CONGRESS系统,提供了强的成员信息语义和强的消息分发语义.
CONGRESS和Moshe系统的新意在于,它们以客户-服务器的方式建立:群组成员服务由指定的成员服务器提供,但服务器本身并不是任何群组的成员.
为了提高系统的可靠性,研究者提出许多错误检测方法.
考虑到许多应用有某种时间约束,文献[18]为错误检测器设计了一个新的规范:(1)及时性,即错误检测器需要多久才能察觉到出错;(2)准确性,即错误检测器检测结果正确的概率有多大.
文献[18]提出的Freshnesspoints方法同时满足这两个规范.
其基本思想是,如果进程q需要检测进程p是否出错,则需p每隔η个时间单位发送心跳(heartbeat)消息m1,m2,…给q.
为了决定是否怀疑p,q采用固定的时间点序列τ1,τ2,.
.
.
,这些点被称为Freshnesspoints,它们是由固定参数δ改变心跳消息的发送时间而获得的.
更具体地说,τi=σi+δ.
这里,σi是消息mi的发送时间.
对任意给定的时刻t,假设i使得t∈[τi,τi+1),则当且仅当q已经收到消息mi或更往后的消息时,q信任t时刻的p.
以上工作主要面向传统的有线广域网环境.
而在移动因特网中,群组成员关系不仅受到进程状态(活跃或出错)和链路状态(连接或断开)的影响,还受到MH的移动性的影响.
但是,针对这种网络环境的成员管理问题的研究还很少.
在移动因特网中,移动IP技术[1921]使得MH在改变网络接入点时不必改变IP地址而保持通信的连续性.
移动IP提供了面向组播移动性管理的两种基本方案:双向隧道和远程签署.
双向隧道方案向外界屏蔽了MH的移动性,MH移动时,无须重构组播树,但是组播路径不是优化的;远程签署方案具有优化的组播传输路径,但是可能引起组播树的频繁重构.
这两种基本方案代表了移动IP技术与IP组播技术结合时的两种极端情形,因而在一般情况下并不适用,其主要原因是没有充分考虑MH的移动性对组播通信性能的影响.
文献[22]提出两层的Host-View协议.
Host-View由一组移动支持站(mobilesupportstation,简称MSS)组成.
MSS代表群组中聚合的位置信息,即:只要该MSS范围内至少有一个MH仍是该群组中的成员,则该MSS代表这些成员加入该群组的Host-View;如果所有成员都退出了该MSS,则该MSS将退出Host-View.
该协议以MSS为基本的组播移动性管理单元,通过记录一组MSS而不是跟踪单个的MH,使成员管理和组播通信变得非常简单.
而且,为了把组播消息传送给由MH组成的群组,只需发送消息给该群组的Host-View中的MSS就可以928JournalofSoftware软件学报Vol.
19,No.
4,April2008满足要求.
由于大部分的任务将在MSS中完成,MH的任务将大为减少.
但是,Host-View协议不允许群组成员动态加入和退出,也没有指定一种方法用于创建和删除群组.
特别地,由于每次"显著性移动"必然导致全局更新,这不仅可能导致组播效率低,而且有可能引起长时间的服务中断.
文献[23]提出了一个3层的RelM协议以解决Host-View协议中的问题:最底层由MH组成,中间层由MSS组成,这些MSS组合成若干个MSS组,每个组由一个监督主机(supervisorhost,简称SH)控制,SH组成了第3层.
因为SH是有线网络的一部分,它可以处理大部分的协议细节,比如维持MH之间的连接以及为可靠组播通信收集确认消息.
文献[12]提出的RMP(areliablemulticastprotocolfordistributedmobilesystems)协议也是基于3层结构:一层是MH,中间层是MSS,第3层是协调者.
在RMP中,每个MSS维护一个称为local的数据结构,用来标识它所在局部范围中MH的集合.
RMP采用的系统模型相当通用,它没有限制群组成员的移动模式,并且可适用于具有不完全的空间覆盖区域的无线网络环境.
特别地,MH从一个MSS切换到另一个MSS不会导致有线网络中的任何消息交换.
在以上相关工作中,基于令牌环绕逻辑环的算法虽然简单但可扩展性不好;而基于树型层次结构的算法可扩展性好但可靠性存在问题.
本文的基本思路就是将两种结构结合起来,提出了层次环结构,使得基于该结构的成员管理算法既具有良好的可扩展性,又具有较高的可靠性.
2协议概述2.
1系统模型研究者现已提出许多面向移动因特网的网络体系结构以解决移动因特网中的异构性问题,即不同类型的MH通过不同类型的无线网络无缝地访问不同类型的应用.
典型的体系结构包括无线叠加网络体系结构[24]、全IP无线与移动网络体系结构[25]和总是最佳连接体系结构[26].
基于这些体系结构,本文提出了基于多层代理的移动因特网体系结构,如图1所示.
部署在有线因特网上的组播服务器称为全局发送者,而部署在无线网络中的组播服务器称为局部发送者.
全局发送者为整个网络中的移动用户提供组播服务,而局部服务器为有限区域的用户提供服务.
本文扩展了代理方法[24]和通信网关方法[27],在不同网络之间设置若干层次的代理,负责为服务提供商与移动用户隐藏异构性.
本文区分两种类型的代理:(1)直接代理(directproxy,简称DP),如无线局域网的接入点、蜂窝网络的基站和卫星网络的卫星,它们直接为附着的MH提供服务;(2)间接代理(intermediateproxy,简称IP),部署在组播发送者与DP之间,组播发送者与DP(及MH)之间的通信必须经由IP.
在图1中,不同的无线网络通过不同的方式连接到有线因特网上:无线接入网络(radioaccessnetwork,简称RAN)通过蜂窝网络的核心网络(corenetwork,简称CN)连接到有线因特网[28];无线局域网既能通过网关(gateway)直接连接到有线因特网,也能先通过网关再通过蜂窝网络的CN间接连接到有线因特网[29];而卫星网络可以通过固定地面站(fixedearthstation,简称FES)与有线因特网连接[25].
在图1中,代理可以是网络中独立的主机,也可以依附在一些网络实体上,例如无线局域网的网关、蜂窝网络的无线网络控制器(radionetworkcontroller,简称RNC)、GPRS服务支持结点(servingGPRSsupportnode,简称SGSN)、GPRS网关支持结点(gatewayGPRSsupportnode,简称GGSN)[28]、卫星网络的FES,甚至是有线因特网中的边界路由器.
基于该结构提出了基于代理结点的层次环模型.
图2是一个4层的例子,自顶向下分别是间接代理层2(intermediateproxytier2,简称IPT2)、间接代理层1(intermediateproxytier1,简称IPT1)、直接代理层(directproxytier,简称DPT)和移动主机层(mobilehosttier,简称MHT),上面3层根据位置相邻性(或其他特性)分别组织成一个或多个逻辑环,每个逻辑环中有且仅有一个领导结点.
领导结点除了起到普通代理的作用,还负责与层次结构中上一层的父结点通信(如果父结点存在).
领导结点是其父结点的孩子结点,父结点与该领导结点之间的关系称为父子关系.
另外,每个逻辑环中邻居的关系称为前后关系.
逻辑环中每个代理都存在该代理的前一个代理(简称前代理或前结点)以及该代理的后一个代理(简称后代理或后结点).
如果逻辑环只包含一个结点,则领导结点、前结点、后结点都是这个结点本身.
每个代理初始化时获取以下信息:(1)若干个候选的兄弟代理,该代理王国军等:基于双向令牌的可扩展及可靠的群组成员管理929通过它们与同一层逻辑环合并;(2)若干个候选的父代理,该代理通过它们附着到上一层逻辑环.
CNCNWLAN3GRANWLAN2.
5GRAN2.
5GRAN4GRANWLAN3GRANMHMHMHMHMHMHMHMHMHMHDPDPDPDPDPDPDPDPIPIPIPIPIPIPIPIPIPIPIPIPIPIPlatigidLocalserverlatigidLocalserverSatellitenetworkDPIP4GRANDPIPThewiredInternetIPIPIPIPlatigidGlobalserverAttachMovementMH:MobilehostRAN:RadioaccessnetworkWLAN:WirelessLANCN:CorenetworkDP:DirectproxyIP:IntermediateproxyFig.
1Multi-Tierproxy-basedmobileInternetarchitecture图1基于多层代理的移动因特网体系结构DPDPDPDPDPDPDPDPDPDPDPDPDPDPDPDPPDAPDAIPIPIPIPIPIPIPIPIPIPIPIPMHTDPTIPT1IPT2IPT2:Intermediateproxytier2DPT:DirectproxytierMHT:MobilehosttierIPT1:Intermediateproxytier1ProxyProxyLeaderNon-LeaderLogicallinkAttachMovementLaptopcomputersMobilephonesMobilephonesMobilevideophonesMobilevideophonesLaptopcomputersFig.
2Ring-Basedhierarchyofproxiesforgroupcommunications图2面向群组通信的基于代理结点的层次环模型最后,本节简要介绍移动性检测机制.
每一个DP周期性地在其覆盖区域中广播心跳消息.
作为群组成员的MH一旦收到心跳消息,就返回一条包含其主机标识符的招呼(greeting)消息,对DP宣告其存在.
DP一旦收到招呼消息,就把MH登记为群组成员,即MH通过DP加入层次环结构.
在此过程中,如果DP没有附着到该结构,则开始加入该结构.
MH加入该结构后,周期性地发送成员刷新(member-update)消息给DP,以刷新其存在信息.
如果在超时间隔过后DP仍没有收到刷新消息,则认为MH切换到另一个DP或者出错;如果MH从不同的DP收到若干个心跳消息,则简单地选择在它与DP之间距离最近的那个DP,然后返回一条招呼消息.
930JournalofSoftware软件学报Vol.
19,No.
4,April20082.
2局部群组的概念本文把每个DP逻辑环范围内的群组成员看作是一个基本的局部群组,把每个IP逻辑环范围中的群组成员看作是一个扩充的局部群组.
扩充的局部群组包含其子层次环结构中这些基本局部群组中存在的所有成员.
基于局部群组概念,这里以成员加入(member-join)消息为例说明成员改变消息是如何沿着层次环结构自底向上传送的.
如果MH希望加入群组,它首先发送Member-Join消息给其附着的DP,然后,该消息进入这个DP的消息队列中,接着同时执行以下两个操作:成员信息传播操作:该操作运行在DP位于的局部群组或逻辑环中,以传播Member-Join消息.
如果该消息到达局部群组或逻辑环的领导结点,则由领导结点发送到其父结点(如果父结点存在).
当领导结点的父结点收到该消息时,该消息就进入父结点的消息队列中,然后,继续在父结点所在的局部群组或逻辑环中传送.
该成员信息传播过程一直持续到Member-Join消息到达顶层的局部群组或逻辑环为止.
拓扑结构维护操作:如果DP已经在层次环结构中,则对于Member-Join消息不需要任何拓扑结构维护的操作;如果DP不在层次环结构中,则通过与其候选兄弟结点联系,尝试加入DP逻辑环.
如果至少有一个DP逻辑环满足条件,如邻接性条件,则DP加入该DP逻辑环.
如果联系过程失败,就建立一个DP逻辑环只包含这个DP本身,并设置自己为逻辑环的领导结点.
该逻辑环将与其邻接的一个DP逻辑环合并,或与上一层的候选IP联系,然后附着到其中一个IP.
该加入过程一直持续到消息到达层次环结构的顶层局部群组或顶层逻辑环为止.
对于层次环结构中的成员消息传播而言,当把每个局部群组看作是一个结点时只使用单向传播:MH请求DP更新成员信息;DP领导结点再请求其父结点更新成员信息,等等.
这样,MH和其附着的DP之间就形成客户-服务器关系;DP领导结点和其父结点也形成客户-服务器关系.
客户-服务器方法可以有效地降低协议设计的复杂性,并提高协议的可扩展性,这是因为每个成员改变消息只需传送给其父结点,而无须广播到整个网络中.
2.
3邻居检测的概念严格地说,只有已经加入群组的MH才是群组成员,层次环结构中所有代理都不是群组成员.
由于成员信息传播操作沿着层次环结构自底向上传送成员信息,则每个局部群组将包含其子层次环结构中所有群组成员的弱一致性的成员关系信息.
成员信息的准确性依赖于当层次环结构中出错时如何准确、及时地维护整个结构.
一方面,要求为系统中每个代理初始配置若干个候选邻居(候选父结点和候选兄弟结点),候选结点的配置可能随系统演化而发生变化.
本文假设在任意时刻为每个代理所配置的候选结点总数都维持在一个较小的值上,如最多为8.
另一方面,层次环结构中每个代理在任意时刻至多有4个当前邻居(前结点、后结点、父结点和孩子结点).
层次环结构中代理总数可能会很多,但是邻居个数(候选邻居和当前邻居)可以很少.
邻居检测的工作机理是:为每个代理配备一个邻居检测部件,负责监视代理的所有候选邻居和当前邻居的状态.
为了检测当前邻居是否出错,可以直接使用基于心跳消息的Freshnesspoints方法[18].
然而,为了检测候选结点是否可达,本文扩展该方法以处理探测(polling)消息.
如果进程q需要检测进程p是否可达,则q周期性地每隔η个时间单位发送探测消息m1,m2,.
.
.
到p.
当p收到探测消息后就把消息返回给q.
决定是否怀疑p的余下过程类似于基于心跳消息的Freshnesspoints方法.
错误检测时,代理发送的每个心跳消息包含该代理的前代理和后代理的结点标识符的信息(若前代理和后代理存在).
当目标代理收到该消息后就相应地更新信息.
无论每个运行拓扑结构维护操作的代理当前是否处在层次环中,都使用基于探测消息的Freshnesspoints方法以维护其候选邻居.
如果目标代理是候选父结点,则探测消息带回目标代理是否有孩子结点的信息;如果是候选兄弟结点,则带回目标代理是否在其子层次环中"顶层"逻辑环的信息,即目标代理的领导结点当前是否有父结点,以及目标代理的前代理、后代理和领导代理的结点标识符的信息(若前代理、后代理和领导代理存在).
本文假设崩溃类型的结点错误可能发生,并称这种错误为代理错误.
同时假设网络中链路错误只可能暂时地发生,而不会永久性地发生(除非链路对应的代理结点出错).
崩溃结点不能从系统接收任何消息,也无法发送任何消息给系统,而暂时出错的链路将在相当短的时间内丢弃沿该链路传送的消息.
本文基于邻居检测概念提王国军等:基于双向令牌的可扩展及可靠的群组成员管理931出了Neighbor-Repair算法(即基于当前邻居检测的层次环修复算法).
如果发生网络分区,成员管理协议在每个分区中独立运行.
当分区合并时,成员信息也合并在一起.
基于可达性检测,本文提出了Partition-Repair算法(即基于候选邻居检测的网络分区的合并算法).
本文将涉及网络分区与网络合并的错误称为网络错误.
虽然错误检测器很少出错,但它仍然有可能出错.
下面我们来说明一旦邻居检测器出错时是否会对协议造成影响.
首先,考虑进程q正在检测当前邻居p.
如果p确实出错,则无法发送和接收任何信息,因此,可以假设p总是被q正确地检测为出错.
但是,即使p没有出错,在某些情况下也可能被错误地检测为出错.
例如,从p发送到q的心跳所有消息全部丢失了.
在这种情况下,为了确保协议正确运行,需要q丢弃从p给q的所有消息,并且q停止发送任何消息给p.
这样,q认为p真的出错,p也认为q出错,因为之后p无法从q接收任何信息.
然后考虑进程q正在检测候选邻居p的情况.
如果p是真的不可达,则可假设q总能正确地检测到p是不可达的.
但是,q可能错误地检测p是不可达的,而实际上是可达的.
易知,这不会对本文的协议造成影响.
这是因为q不会把其所有可达的候选邻居检测为不可达,否则就违背了Freshnesspoints方法有相当高准确性的特征.
2.
4基本组播协议使用层次环模型的组播信息传送是由组播发送者发送组播信息给"顶层"逻辑环中的代理.
对于全局发送者,"顶层"逻辑环是整个结构的顶层逻辑环;而对于局部发送者,"顶层"逻辑环是其所位于的子结构的顶层逻辑环.
然后,组播信息沿每个逻辑环传送再转发给所有孩子结点.
最终,MH从其附着的DP接收组播信息.
这里先介绍针对组播通信的组播移动性管理概念.
对于组播通信中的位置管理,本文考虑把层次环结构视为整个组播群组的一个虚拟位置.
换言之,该层次环结构动态地变化以反映当前群组中所有群组成员的聚合位置信息.
对于组播通信中的切换管理,本文采用了预留机制.
它与成员管理的预留机制有关,但不同之处在于,当DP接收到预留消息时,如果DP已经建立了自己与其领导代理的父结点IP之间的组播路径,则丢弃这个消息;如果没有建立组播路径,则立即建立一条通向其领导代理的父结点IP的预留路径.
这样,如果MH切换到新的已经执行过预留操作的DP,则该MH能够立即接收组播消息.
由于MH的成员关系动态性与位置动态性,层次环结构中低层次比高层次变化得更快.
如果在DP逻辑环变化非常频繁时仍使用该结构,则组播传送就会变得很低效.
因此,在组播传送协议中,本文使用一个与层次环结构稍有不同的层次结构:(1)如果DP察觉到自己包含的成员个数从零变化到非零,则开始建立一条经由某些称为组播移动代理(multicastmobilityagent,简称MMA)的中间代理通向其领导代理的父结点IP的组播路径;(2)如果DP已经从邻接DP收到预留消息,且不包含任何活跃成员,则启动预留一条经由某些MMA通向其领导代理的父结点IP的组播路径;(3)如果DP退出该结构,则拆除通向其领导代理的父结点IP的组播路径.
3基于局部群组的成员信息传播子协议3.
1MH、代理、令牌的数据结构MH的数据结构.
作为群组成员的每个MH记录以下信息:GID:GroupID.
群组标识符,可以采用某种群组寻址模式,例如IP组播中的D类地址[7];DP:NodeID.
附着的DP的结点标识符;GUID:GloballyUniqueID.
MH的全局唯一标识符,例如移动IP网络的家乡地址[30];LUID:LocallyUniqueID.
MH的局部唯一标识符,例如移动IP的转交地址[30];Status:Integer.
为一整型值,典型状态如活跃、断开连接和出错.
代理的数据结构.
每个代理记录以下信息:GID:GroupID.
请见MH的数据结构;Current,Leader,Previous,Next,Parent,Child:NodeID.
分别表示层次环结构中的当前结点、领导结点、前结点、后结点、父结点和孩子结点的结点标识符;PreviousOK,NextOK,ParentOK,ChildOK:Boolean.
分别表示当前结点在层次环结构中的前结点、后结932JournalofSoftware软件学报Vol.
19,No.
4,April2008点、父结点、孩子结点的状态.
TRUE表示没有出错,FALSE表示出错或者不存在;CandidateSiblings[],CandidateParents[]:NodeID.
分别表示候选兄弟结点和候选父结点的结点标识符列表;CandidateSiblingsOK[],CandidateParentsOK[]:Boolean.
分别表示候选兄弟结点和候选父结点的状态列表.
TRUE表示可达,FALSE表示不可达或者不存在;ListOfMembers[]:MemberInfo.
以当前结点所属的逻辑环为根向下到其覆盖的所有DP及MH的子层次环中活跃成员的列表;MQ:MessageQueue.
缓存成员改变/成员关系更新消息的消息队列.
令牌的数据结构.
每个代理独立地收集、生成成员改变/成员关系更新消息,使用令牌沿着逻辑环以传送这些消息.
令牌记录以下信息:GID:GroupID.
请见MH的数据结构;Holder:NodeID.
令牌持有者的结点标识符;MQ:MessageQueue.
缓存成员改变/成员关系更新消息的消息队列.
3.
2成员信息传播算法在层次环结构中,每个代理维护当前存在于其子层次环中的所有活跃群组成员的"全局"成员信息.
群组成员管理包括两个主要任务:成员信息传播和拓扑结构维护.
这两个任务是紧密相联的,但是,这里用在这两个任务之间通信的事件把它们分开以简化处理.
本文为成员信息传播设计两种信号消息(signalingmessage):Membership-Change(简称MC)消息(即成员改变消息,该类消息与单个移动主机相关)和Membership-Update(简称MU)消息(即成员关系更新消息,该类消息包含了与多个移动主机相关的聚合成员信息).
每个逻辑环中的领导结点负责根据其ListOfMembers[]周期性地生成MU消息.
MC消息有以下几种:(1)Member-Join/Leave/Handoff消息(当MH加入、退出或切换时生成);(2)Member-Update消息(由每个作为成员的MH生成,周期性地向其附着的DP刷新其状态);(3)Member-Failure消息(当DP周期性地检查其ListOfMembers[]后发现某个MH已经闲置超过预定义的时间时发送该消息).
有3种情况可能导致错误状态:(1)作为群组成员的MH确实出错;(2)MH发送的所有Member-Update消息全部丢失;(3)MH从其附着的新DP发送给旧DP的Member-Handoff消息丢失.
在DP层中,MC消息由每个逻辑环中的令牌沿着逻辑环传播.
成员改变消息,例如Member-Join,Member-Leave,Member-Failure,Member-Handoff,由环绕在每个逻辑环中的令牌沿着层次环结构自底向上传播.
对于每个逻辑环,如果令牌成功环绕一轮后没有丢失,在使用某种重传机制的基础上,令牌的控制权可靠地转移到逻辑环中的下一个结点.
令牌的控制权成功转移后,逻辑环中所有代理都已获得了相同的成员关系.
算法1表示在每个DP逻辑环中运行的成员信息传播算法.
算法1.
One-Round令牌传递的成员信息传播算法.
输入:令牌(token)所处的当前结点CurNode和CurNode所属的逻辑环;输出:沿着逻辑环传播成员改变/成员关系更新消息.
1.
WhileTRUEDo{2.
OnReceivingaToken:3.
IfToken.
Holder==CurNode.
CurrentThen4.
LetToken.
MQbeempty;5.
ElseifToken.
MQisnotemptyThen6.
UpdateCurNode.
ListOfMembers[]withToken.
MQ;7.
ElseifCurNode.
MQisnotemptyThen{8.
LetToken.
HolderbeCurNode9.
LetToken.
MQbeCurNode.
MQ;王国军等:基于双向令牌的可扩展及可靠的群组成员管理93310.
}11.
TransfertheTokentothenextnodereliably;12.
}13.
//注释1.
当令牌环绕一轮后,其MQ被设为空;14.
//然后空令牌沿着下一条逻辑链路被可靠地转移到一个MQ不为空的结点.
15.
//注释2.
由于代理结点可能出错(见第4节),因此令牌可能会丢失.
16.
//本文假设,如果领导结点在超时间隔以后没有收到令牌,则领导结点将重新生成一个新的令牌.
从某一层的领导结点到其上一层的父结点(如果父结点存在)的MU消息的传播,本文采用超时机制:首先每个领导结点周期性地发送其成员信息给其父结点,成员信息保存在其父结点的MQ中;然后,父结点使用One-Round令牌传递算法沿着它所在IP层的逻辑环传播成员信息.
沿层次环结构传播成员改变/成员关系更新消息的成员信息传播算法见算法2.
算法2.
沿着层次环结构的成员信息传播算法.
输入:层次环结构中的每一个代理所维护的不同层次的成员信息;输出:沿着层次环结构自底向上传播成员改变/成员关系更新信息.
1.
ParForeachproxyrunningtheproposedprotocolDo{2.
OnTimeouteventforgeneratingMUmessagesataleaderproxy:3.
GenerateandSendMUmessagestotheleaderproxy'sparent(ifexists);4.
OnReceivinganMCmessageataproxy://该代理是DP;5.
KeeptheMCmessageintheproxy'sMQ;6.
//MQ中的消息按照One-Round令牌传递的成员信息传播算法传送;7.
OnReceivinganMUmessageataproxy://该代理是IP;8.
KeeptheMUmessageintheproxy'sMQ;9.
//MQ中的消息按照One-Round令牌传递的成员信息传播算法传送.
10.
}层次环中每个代理独立地收集、生成、发送MC/MU消息,成员信息传播算法以并行及分布式的方式运行.
为加快成员信息在逻辑环中的传播并提高其可靠性,可以在每个逻辑环中设置双向令牌以传送成员信息.
双向令牌实际上是在逻辑环的两个相反方向上运行且互相独立的两个令牌.
为简单起见,算法中没有表示出双向令牌.
需要指出的是,该算法也没有表示两个令牌之间的信息交换,这是因为只是使用两个令牌在同一个逻辑环中传播成员信息,这样可以比使用单个令牌时的可靠性高些;另外,本文提出的成员管理协议只需要提供弱一致性的成员关系信息,因此不需要两个令牌中传播严格一致的成员信息.
这里指出,在成员信息传播子协议中可以使用预留机制让DP的若干个邻接DP事先加入层次环.
如果DP察觉到其包含的活跃成员从零变到非零,则生成并发送预留消息给其所有邻接DP.
DP一旦收到该消息,若已包含活跃成员,则简单地丢弃该消息;否则,立即加入层次环.
这样,如果MH切换到已经执行过预留操作的DP中,则MH立即通过新的DP加入层次环.
这里还需指出,层次环结构在两种情况下会动态改变:一是结构中出现错误时(将在第4节讨论);另一种是MH动态加入、退出、切换以及因为群组成员出错而离开时.
对于后一种情况,存在两类拓扑结构改变事件:一类是Proxy-Join/Leave事件,引起单独的结点加入或退出结构中同一层上的某个逻辑环;另一类是Proxy-Attach/Detach事件,引起相邻两层上的结点之间的父子关系的建立或结束.
成员信息传播算法中的两种情况会导致拓扑结构改变事件:一种情况发生在DP收到成员信息传播算法生成的MC消息时:如果MH切换到另一个DP(或加入一个DP)并且它正好是附着到该DP上的第一个成员,则该DP开始加入该结构;若该MH是它所退出(或出错所在)的DP中的最后一个成员,则该DP可能开始从结构上退出.
DP层的Proxy-Attach/Detach事件可能进一步引发DP的934JournalofSoftware软件学报Vol.
19,No.
4,April2008父亲IP相应地加入、退出、附着或离开该结构.
第2种情况发生在IP收到成员信息传播算法生成的MU消息时:若收到MU消息的IP所维护的活跃成员数由零变为非零,并且该IP不在结构中,将会导致Proxy-Join或Proxy-Attach事件;同样地,若活跃成员数由非零变为零,并且该IP在该结构中,则会导致Proxy-Leave或Proxy-Detach事件的发生.
为了避免Proxy-Leave/Detach事件引起结构的频繁重构,本文采用Lazy-Leave/Detach机制.
只有当DP在整个超时间隔内都不包含活跃成员,并且它的所有邻居DP也不包含活跃成员时,它才离开该结构.
相应地,对于IP,只有当它在整个超时间隔内都不包含任何孩子结点时才离开该结构.
3.
3成员信息传播子协议的性能分析当成员加入、退出、切换、出错以及层次环结构中结点出错时,层次环结构会动态变化.
下面的分析中使用了以下性能度量:Join-Delay,定义为从MH发出加入该群组的意愿到它接收到第1个组播数据包的时间间隔;Handoff-Delay,定义为从MH检测出它已经进入一个新的DP到它从新DP接收到第一个组播数据包的时间间隔;Service-Speed,定义为从MH发出加入该群组的意愿到它的成员信息成功地在顶层逻辑环的领导结点登记的时间间隔;Signaling-Overhead,定义为成员信息传播与拓扑结构维护中所有代理接收到的信号数据包总数或总大小除以代理的总数,然后再除以总的执行时间,它代表协议的平均开销.
本文基于上述度量作最坏情况分析.
这里,使用Member-Join消息在层次环结构中传送的过程为例来说明.
假设3.
1.
如果MH通过其附着的DP请求加入群组,该DP总是成功地把MH登记为群组成员,而无论该DP目前是否处于层次环结构中.
假设该操作时间的界为TMH-Join-Registration.
假设3.
2.
如果代理通过候选兄弟结点或候选父结点请求加入层次环结构,则该代理总是成功地通过其中一个候选兄弟结点与同一层的兄弟逻辑环合并,或通过其中一个候选父结点附着到上一层逻辑环.
假设该操作时间的界为TProxy-Merge-Attach.
假设3.
3.
如果Member-Join消息已经进入代理的MQ中,该消息总是被成功地传送到该代理所在逻辑环的领导结点.
假设该操作时间的界为TProxy-MS-Leader.
假设3.
4.
如果Member-Join消息到达领导结点的ListOfMembers[],该消息总是成功地传送到该领导结点的父结点(如果父结点存在).
假设这个操作时间的界为TProxy-MS-Parent.
假设3.
5.
假设层次环结构中的任何MH总是成功地接收组播消息的时间的界为TMulticast-Transmission.
这里把上述假设作为一个整体称为Always-Successful-assumptions(简称AS-assumptions).
AS-assumptions是合理的:(1)为了提供给用户最佳的服务,服务提供商或网络运营商有责任在其服务范围内合理地部署所有的代理;(2)如果代理部署不合理,则处于相应区域的用户可能得不到好的服务.
在第1种情况下,AS-assumptions成立;而在第2种情况下,AS-assumptions有可能不成立.
有了AS-assumptions,本文首先证明Join-Delay与Service-Speed度量的界.
定理3.
1.
假设AS-assumptions在高度为h的层次环结构中成立,在最坏情况下,Join-Delay的界为TMH-Join-Registration+(h1)*(2*TProxy-Merge-Attach+TProxy-MS-Leader+TProxy-MS-Parent)TProxy-Merge-AttachTProxy-MS-Parent+TMulticast-Transmission(1)证明:假设逻辑环的领导结点只通过其候选父结点附着到层次环结构中,不会通过其候选兄弟结点与其他逻辑环合并.
在最坏情况下:(1)当MH发送Member-Join消息给其附着的DP以请求加入群组时,首先花费TMH-Join-Registration时间把它登记为其附着的DP中的群组成员;(2)如果该DP恰好不在层次环中,它就请求通过其候选兄弟结点之一与逻辑环合并,这将花费TProxy-Merge-Attach时间;(3)Member-Join消息沿逻辑环传送到领导结点,将花费TProxy-MS-Leader时间;(4)如果该领导结点恰好不在层次环中,则请求通过其候选父结点之一附着上一层逻辑环,这将花费TProxy-Merge-Attach时间;(5)Member-Join消息从领导结点传送到其父结点,这将花费TProxy-MS-Parent时王国军等:基于双向令牌的可扩展及可靠的群组成员管理935间;(6)对于上面h2层的IP层,重复以上步骤(2)~步骤(5);(7)至此,建立起沿层次环自底向上成员信息传播的一条完整"路径";(8)组播数据包沿反向"路径"自顶向下传播,最终被MH接收到,这将花费TMulticast-Transmission时间.
定理3.
2.
假设AS-assumptions在高度为h的层次环结构中成立,在最坏情况下,Service-Speed的界为TMH-Join-Registration+(h1)*(2*TProxy-Merge-Attach+TProxy-MS-Leader+TProxy-MS-Parent)TProxy-Merge-AttachTProxy-MS-Parent(2)证明:证明过程与定理3.
1的证明过程相似.
唯一的区别是这里去掉了传送组播数据包的时间.
从上述两个定理来看,Join-Delay的界还大于Service-Speed的界.
实际上,这只是最坏情况才可能如此.
在平均情况下,Join-Delay很小,因为MH附着的DP可能已经位于层次环中.
然后论证Signaling-Overhead度量.
每个代理的MQ中所有成员消息都会作为一个聚合消息沿每个逻辑环传送,这样信号开销会大为减少.
另外,成员信息传播从逻辑环的领导结点到领导结点的父结点基于超时机制,这也减少了信号开销.
因此,可以认为层次环结构中每个代理的信号开销的界为常数.
对Handoff-Delay度量可以作相似的分析,这里从略.
因为切换处理过程通常采用某种预留机制,当MH切换到一个新的DP中时,大部分时间都能立即接收到组播消息.
因此,在平均情况下,Handoff-Delay度量都比Join-Delay要小,有关这一点将在第6节的模拟分析中得以验证.
4基于邻居检测的拓扑结构维护子协议本节研究层次环中的两种错误对协议的影响:(1)代理错误,可导致层次环结构中父子关系、前后关系结束;(2)网络错误,可造成在网络分区期间系统中形成若干个互不相交的子层次环结构.
本节首先描述处理代理错误的Neighbor-Repair算法,然后描述处理网络错误的Partition-Repair算法.
4.
1Neighbor-Repair算法处理代理错误的Neighbor-Repair算法如下.
对于层次环结构中的每一个代理:情况1.
如果代理是领导结点,且其错误检测部件(failuredetectioncomponent,简称FDC)报告其父代理出错,则将该代理的ParentOK设置为FALSE,指示父子关系结束.
然后,它与其中一个可达候选父结点建立新的父子关系,称为ATTACH过程,或通过其中一个可达候选兄弟结点与逻辑环合并,称为MERGE过程;情况2.
如果代理的FDC报告其孩子代理出错,则将该代理的ChildOK设置为FALSE,指示父子关系结束;情况3.
如果代理的FDC报告其前代理出错,则将PreviousOK设置为FALSE.
为去掉逻辑环中的错误结点,代理将发送Previous-Repair消息给前代理的前代理,建立它们之间的兄弟关系.
如果代理错误不常发生,与Previous-Repair消息相关的Neighbor-Repair算法会很快终止,本文称这部分算法为Fast-Neighbor-Repair过程.
如果出错的代理恰好是领导结点,在Fast-Neighbor-Repair算法终止后,该逻辑环将没有领导结点.
为了解决该问题,发送Previous-Repair消息的代理将自己设为新的领导代理,然后发送Leader-Change消息通知逻辑环中所有代理更新其领导代理.
如果代理错误频繁发生,则如果前代理的前代理也出错,则Previous-Repair消息将永久丢失.
在这种情况下,在超时间隔过后,Slow-Neighbor-Repair过程就会启动.
为了从逻辑环中去掉两个以上连续出错的代理,则发送Dest-Find消息沿逻辑环中查找目标代理(称为DESTINATION),然后建立它们之间的兄弟关系.
DESTINATION是无法沿逻辑环可靠地转发Dest-Find消息的那个代理.
因为Dest-Find消息沿逻辑环传送给DESTINATION,与Fast-Neighbor-Repair过程相比较,这部分算法需要花更长的时间才能终止,本文称其为Slow-Neighbor-Repair过程.
如果领导结点恰好是出错的结点之一,则在Slow-Neighbor-Repair算法终止之后,该逻辑环将没有领导结点.
为了解决这个问题,需要Dest-Find消息收集它到DESTINATION的路径上的领导结点信息.
如果领导结点不在路径上,DESTINATION就被设为新的领导结点,再发送一条Leader-Change消息以通知新的领导结点信息.
情况4.
如果代理的FDC报告其后代理出错,则将该代理的NextOK设为FALSE.
首先执行Fast-Neighbor-Repair过程;如果在超时间隔过后它还没有终止,则执行类似的Slow-Neighbor-Repair过程.
以上是Neighbor-Repair算法的基本设计.
但在基本设计中,由于情况3和情况4的对称操作会导致以下问题:(1)重复操作.
因为出错代理的两个邻居可能同时检测到其错误状态,它们可能分别独立地启动执行936JournalofSoftware软件学报Vol.
19,No.
4,April2008Neighbor-Repair算法.
该算法仍然可以正常运行,但是同样的操作会执行两次;(2)领导信息不一致.
由于情况3和情况4的对称操作,在发送Leader-Change消息时,逻辑环中各个代理上的领导结点信息可能会不一致;(3)逻辑环不一致.
考虑代理实际上没有出错但被错误地怀疑为出错的情况,这里需要被错误怀疑的代理将正在检测的代理也看作出错.
但是,这样会导致逻辑环不一致.
例如,有5个代理的逻辑环具有前后关系:ABCDEA;然后假设C错误地怀疑D出错,之后D也会怀疑C出错;然后C发送Next-Repair消息给E,D也发送Previous-Repair消息给B;再假设C和E的兄弟关系在B和D的兄弟关系之前已建立,即去掉D首先形成了一致的逻辑环ABCEA,再去掉C将会形成不一致的逻辑环:包括后一条链路的逻辑环A→B→D→E→A和包括前一条链路的逻辑环A←B←C←E←A.
为避免出现这些问题,只需简单地去掉情况3或情况4即可.
4.
2Partition-Repair算法如果网络出错,层次环结构被划分成若干个子层次环结构(理想情况下,每个网络分区对应一个子层次环结构),当网络分区合并时,若干个子层次环结构又合并在一起.
在出现分区期间,层次环结构中的一个逻辑环可能破裂成两个或更多个部分.
逻辑环的每个部分通过运行Neighbor-Repair算法将修复成一个新的逻辑环.
本文在网络出现分区的情况下也使用第4.
1小节的ATTACH和MERGE过程.
只有处于"顶层"逻辑环的领导结点可以发送请求以启动这两个过程.
首先定义一个领导结点的可达候选邻居结点队列(aqueueofreachablecandidateneighbors,简称QRCN)作为可达候选邻居结点的集合.
QRCN是在使用检测可达性时保留在返回的探测消息中的信息而动态形成的.
若QRCN不为空,则领导结点从其中选择一个候选邻居,该候选邻居必须不在领导结点位于的子层次环结构中,领导结点再用该候选邻居启动ATTACH或MERGE过程来处理网络分区的合并.
处理ATTACH和MERGE过程的Partition-Repair算法如下.
对于网络分区子层次环结构中"顶层"逻辑环的领导结点来说:情况1.
ATTACH过程用来在两个代理之间建立新的父子关系.
为了确保层次环结构的一致性维护,本文采用了两阶段提交协议,把每次维护看作一个事务.
每次ATTACH事务只涉及两个代理:LEADER及其某个候选父结点代理(称为PARENT).
在第1阶段,LEADER发送Leader-Attach消息给PARENT,PARENT肯定地或否定地应答.
在第2阶段,LEADER确认或回滚,通知PARENT相应地做确认或回滚.
情况2.
MERGE过程用来把两个逻辑环合并成一个逻辑环.
每个MERGE事务涉及4个代理,即LEADER、LEADER的后结点(称为NEXT)、CANDIDATE和CANDIDATE的后结点(称为CANDIDATE-NEXT).
在第1阶段,LEADER发送一个Leader-Merge消息给其他3个代理,然后,这3个代理做出肯定或否定的回复.
在第2阶段,如果LEADER收到的3个回复都是肯定的,LEADER就确认并通知另外3个代理确认;否则,LEADER回滚并通知另外3个也回滚.
当这两个逻辑环成功地合并成一个时,则LEADER发出一个从探测消息得到的领导结点信息的Leader-Change消息,通知LEADER原来逻辑环中所有代理更改新的领导结点信息.
在MERGE过程中,如果正在合并的两个逻辑环恰好是它们各自子层次环结构中的"顶层"逻辑环,则两个LEADER中结点标识符较大的结点才允许启动其事务.
4.
3拓扑结构维护子协议的性能分析当考虑到网络出现分区时,下面所提到的特征和界将适用于每个分区.
特征4.
1.
及时性.
该特征度量拓扑结构维护子协议对错误事件响应的时间.
(1)拓扑结构维护子协议基于Freshnesspoints方法来检测错误并获得可达性信息,该方法满足及时性.
(2)所有拓扑结构维护过程都是基于局部信息的,因为它们只需要知道当前邻居和候选邻居的信息.
(3)所有拓扑结构维护过程以并行与分布式方式运行并将在确定时间内终止.
对于Fast-Neighbor-Repair和Slow-Neighbor-Repair过程,如果前者在超时间隔后没有终止时,后者就会启动然后在确定时间内终止.
尤其对于ATTACH和MERGE过程,当一个过程不能正常终止,它就从其可达候选邻居集合中选择另一个候选邻居启动另一个过程.
本文假设选择过程在所有可达候选邻居中运行过一轮后,至少有一个过程会正常终止.
特征4.
2.
准确性.
这个特征度量错误发生时拓扑结构维护子协议维护层次环结构的准确程度.
王国军等:基于双向令牌的可扩展及可靠的群组成员管理937(1)基于Freshnesspoints方法可以高准确性地检测出代理错误和网络分区与网络合并.
(2)如果Freshnesspoints方法错误地怀疑没有出错的代理,就从逻辑环中去掉正在检测的代理或被错误怀疑的代理.
这样,去掉的代理将变成一个独立的代理,然后自己单独加入层次环结构中.
基于及时性和准确性,可以认为执行每次拓扑结构维护过程的时间的界为某个常数,而且层次环结构的维护是非常准确的.
另外,可以认为成员信息传播子协议中类似的性能度量的界也存在.
5层次环结构的可扩展性和可靠性的分析5.
1可扩展性的比较分析在文献[16]中,成员服务器被组织成一个基于代表结点的树结构,称为CONGRESS层次结构,其中包含局部成员服务器和全局成员服务器.
本节针对层次环结构与CONGRESS层次结构作可扩展性比较.
树结构/层次环结构中的LMS/DP个数n作为等效的可扩展性参数.
为简单起见,下面分别计算沿CONGRESS层次结构和层次环结构将成员改变消息分别传送给所有LMS和所有DP时所经过的逻辑链路的总数HopCount,它近似于CONGRESS层次结构或层次环结构中边的总数.
首先考虑CONGRESS层次结构.
在高度为h≥4、每个GMS的分支数r≥2的层次结构中,LMS的个数为n=rh2,则HopCount为31-0(,,)hdefiTreebasediHopCountnhrr+==∑(3)然后计算高度为h≥3、每个逻辑环包含r≥2个结点的层次环结构中的HopCount.
底层逻辑环中的DP总数为n=rh1,逻辑环的总数为20hiitnr==∑,则HopCount为1)1)defRingbasedHopCountnhrrtn4)正规化HopCount,即把它除以n,它代表一条成员改变消息引起的成员信息传播的"平均"消息个数.
分别把CONGRESS层次结构和层次环结构的正规化HopCount记为和-NTreebasedHC-NRingbasedHC:310hidefdefNNiTreebasedTreebasedrHCHopCountnhrn+===∑(5)20--(1)1(1)1(,,)hidefdefNNiRingbasedRingbasedrrrtnHCHopCountnhrnn=+*+*===∑(6)根据式(5)和式(6),我们给出了表1的数值分析结果.
可见,在给定相同个数的LMS/DP的情况下,层次环结构的可扩展性与树结构的可扩展性一样好.
Table1Comparisononscalabilitybetweenthetree-basedandring-basedhierarchies表1树结构与层次环结构的可扩展性对比nhr-NTreebasedHCnhr-NRingbasedHC16441.
250016341.
500064541.
312564441.
6250256641.
3281256541.
656336461.
166836361.
3333216561.
1944216461.
38891296661.
19911296561.
398264481.
125064381.
2500512581.
1406512481.
28134096681.
14264096581.
28521004101.
10001003101.
200010005101.
110010004101.
2200100006101.
1110100005101.
2220938JournalofSoftware软件学报Vol.
19,No.
4,April20085.
2可靠性的比较分析首先说明:如果把层次环结构中每个逻辑环看作是一个结点,层次环结构与树结构是同构的,则层次环结构的可靠性比树结构更高.
这是因为,当只考虑出现一个结点出错的情形时,显然,由于树结构中一个错误会把树结构破裂成若干个部分,而层次环结构中一个错误会使得一个逻辑环破裂,该结构可能不会破裂成若干个部分(除非该错误结点具有孩子结点).
实际上,当考虑同时出现多个错误时,也会存在类似状况.
然后说明:如果两个结构是同构的,树结构比基于代表结点的树结构具有更高的可靠性.
这是因为,在基于代表结点的树结构中,一个代表结点出错实际上是若干个逻辑结点出错,而在树结构中一个结点出错只是它本身出错.
因此,树结构比基于代表结点的树结构更可靠.
下面只需说明层次环结构比树结构更可靠.
树结构中如果一个结点出错,则其孩子结点只有一种选择,即去寻找新的父结点并附着其上.
而层次环结构中如果一个代理出错,则其孩子结点有两种选择:通过候选兄弟结点之一与同一层逻辑环合并,或者通过候选父结点之一附着到上一层逻辑环.
与此同时,通过运行Neighbor-Repair算法把出错代理从逻辑环中去掉.
因此在出错的情况下,层次环结构比树结构可以更可靠地维护.
以上只是非形式的比较分析.
下面从数学上给出严格的比较分析.
首先定义Function-Well(运行良好)概念.
树结构中的一个出错结点会影响到其所有孩子结点,因此,这里定义树结构的Function-Well如下:如果允许在除最低两层以外的层次结构中至多有k个结点同时出错,则称该树结构是Function-Well的.
为了计算树结构的Function-Well(简称fw)概率,假设层次结构是满的:它包含最大层数(记为h),层次结构中每个代理有最多的孩子结点数(记为r).
直观来看,在同样的网络环境中,小层次结构比大层次结构更可能Function-Well.
因此,这里使用满层次结构作最坏情况分析.
该层次结构中倒数第2层包含n=rh2个结点,从第1层~倒数第3层包含30hiitnr==∑个结点,在该层次结构中至多k个结点无法Function-Well.
假设f是层次结构中具有均匀且独立分布的结点出错概率(nodefailureprobability),则树结构的Function-Well概率为()-01kdeftnifwiTreebaseditnProbnhrfkffi==*∑(7)再计算逻辑环的Function-Well概率.
如果在逻辑环中不能出现两个连续的代理同时出错,则只需要Fast-Neighbor-Repair过程修复逻辑环.
在这种情况下,称逻辑环Function-Well.
如果逻辑环无法Function-Well,即逻辑环中至少有两个连续的代理同时出错,则需要Slow-Neighbor-Repair过程修复逻辑环.
然后讨论计算整个层次环的Function-Well概率所使用的参数:n表示DP的个数,h表示层次环的高度,r表示逻辑环中的结点数,f表示层次环结构中具有均匀且独立分布的结点出错概率,k表示不能Function-Well的逻辑环的最大个数.
如果层次环结构中至多k个逻辑环不能Function-Well,则认为该层次环结构是Function-Well的.
定义每个逻辑环的Function-Well概率t为20=(,)(1)rdeffwriiringitProbBriff==∑*(8)在式(8)中,B(r,i)代表错误发生的个数,即在逻辑环的r个结点中恰好有i个结点出错,而且不会发生互为邻居的两个结点出错.
对于0≤i≤3与r≥5,很容易推断出B(r,i)如下:(,0)10rBr==(9)(,1)1rBrr==(10)(3)(,2)212rrrrBr==(11)王国军等:基于双向令牌的可扩展及可靠的群组成员管理93924(920)(,3)31116rrrrrrrBr==(12)而当i≥4时难以得到相应的公式,但可以由计算机程序计算在02ri≤≤时B(r,i)的值.
表2是其数值结果.
接着,在假设满层次环结构时作最坏情况分析.
该层次环包含最大层数,每个逻辑环具有最多结点个数.
这样,层次环中包含个逻辑环,至多k个逻辑环不能Function-Well.
层次环的Function-Well概率表示为20hiitnr==∑-01)kdeffwtniiRingbaseditnProbnhrfktti==∑(13)从式(7)和式(13)得出的数值分析结果见表3.
结论如下:(1)在网络规模和结点出错概率相同的情况下,层次环结构总比树结构更为可靠.
特别地,随着LMS/DP个数的增多和结点出错概率的增大,树结构的可靠性大为降低,而层次环的可靠性只会适度地降低.
例如,在最大层次环结构中,当结点出错概率从0.
1%增大到5.
0%时,树结构的Function-Well概率从99.
980%降到了7.
999%,层次环结构从100.
000%只降到51.
216%;(2)当结点出错概率设定为0.
1%,并且DP个数多达1000个时,层次环结构只需运行Fast-Neighbor-Repair过程修复该结构,此时,该结构的Function-Well概率高达99.
889%;如果允许Slow-Neighbor-Repair过程最多执行2次,则概率可高达100.
0%;(3)在允许Slow-Neighbor-Repair过程至多执行2次的Function-Well层次环的定义以及99.
980%的高概率的情况下,拥有DP个数多达1000个的群组可确保在结点出错概率设定为0.
1%时,该结构仍能Function-Well;(4)当结点出错概率增大到5.
0%时,小规模的层次环结构仍然能以高概率Function-Well.
例如,对于包含64个DP的小规模层次环而言,其Function-Well的概率是99.
900%,但是对于包含1000个DP的大规模层次环只有51.
216%的低概率Function-Well.
Table2B(r,i)valuesforcomputingthefunction-wellprobabilityofalogicalring表2计算逻辑环的Function-Well概率的B(r,i)值rIB(r,i)riB(r,i)401822041483164228426011001616101106291023563210350801104258181052Table3Comparisononreliabilitybetweenthetree-based(h=5)andring-based(h=4)hierarchies表3树结构(h=5)与层次环结构(h=4)的可靠性比较nrf(%)k-fwTreebasedProb(%)-fwRingbasedProb(%)nrf(%)k-fwTreebasedProb(%)-fwRingbasedProb(%)6440.
1097.
92199.
99251280.
1092.
95799.
9426440.
1199.
979100.
00051280.
1199.
749100.
0006440.
12100.
000100.
00051280.
1299.
994100.
0006441.
0080.
97399.
17251281.
0048.
01494.
3816441.
0198.
14999.
99751281.
0183.
41999.
8416441.
0299.
884100.
00051281.
0296.
29399.
9976445.
0034.
05681.
82551285.
002.
36524.
7766445.
0171.
69798.
31751285.
0111.
45159.
6786445.
0291.
50899.
90051285.
0228.
66883.
92521660.
1095.
78999.
9741000100.
1089.
48999.
88921660.
1199.
912100.
0001000100.
1199.
432100.
00021660.
1299.
999100.
0001000100.
1299.
980100.
00021661.
0064.
91097.
4781000101.
0032.
77289.
59121661.
0193.
10499.
9691000101.
0169.
51799.
44321661.
0299.
084100.
0001000101.
0289.
93199.
98021665.
0011.
01853.
9871000105.
000.
3377.
071921665.
0135.
95587.
5061000105.
012.
30426.
03121665.
0263.
51697.
6691000105.
027.
99951.
216940JournalofSoftware软件学报Vol.
19,No.
4,April20086性能评价6.
1模拟方案本文的模拟实验中使用NS-2模拟工具[31]模拟4层的层次环结构.
DP被配置成m*n的网格.
IPT1中有4mn*个IP,IPT2中有4mn*个IP和32mn*个其他代理,其中一个代理还作为组播源.
初始时,在稀疏模式(sparsemode,简称SM)模拟过程中,每个DP都有一个MH附着;在稠密模式(densemode,简称DM)模拟过程中,每个DP有4个MH附着.
在任何时候,SM模拟中由8个DP构成的集合中大约有1个群组成员,DM模拟的每个DP中大约有1个群组成员.
每个代理初始配置4个候选兄弟结点和4个候选父结点.
图3是一个4*4的DP配置的例子,每个DP逻辑环最初由4个DP构成.
本文模拟了8*8,12*12,16*16,20*20的DP配置,每个DP逻辑环最初由4个DP构成,每个IP逻辑环最初分别由4,6,8,10个IP构成.
SM模拟中的最小拓扑结构由64个MH、64个DP、IPT1中的16个IP、IPT2中的16个IP和96个其他代理构成,其结点总数是256个.
如果每个DP的覆盖区域为670m*670m,则其总覆盖区域为5360m*5360m.
DM模拟中的最大拓扑结构由1600个MH、400个DP、IPT1中的100个IP、IPT2中的100个IP和600个其他代理构成,其结点总数是2800个.
如果每个DP的覆盖区域为670m*670m,则其总覆盖区域为13400m*13400m.
DP2DP3DP4DP1DP2DP3DP4DP1DP2DP3DP4DP1DP4DP2DP3DP1Non-LeaderMHLeaderCoverageareaLogicalringPhysicallinkLogicallinkMHmovementFig.
3Example4*4DPconfiguration图34*4DP配置的例子在所有方案中,模拟总时间为600s.
有线链路带宽为10Mbps,链路延迟为10ms,消息丢失率为1.
0%;DP和MH之间的无线链路的等效带宽为2Mbps,链路延迟为20ms,消息丢失率为2.
0%.
信号消息重传的超时间隔设定为100ms,最大重传次数为3.
在作移动性检测时,每个DP的超时间隔为1s,MH向其附着的DP刷新其状态的超时间隔设为1s.
每个逻辑环中领导结点的成员更新间隔为1s.
采用最大速率为15m/s、暂停时间为5s的CMU移动性模型[31]和每个代理从层次结构真正退出、离开的Lazy-Leave/Detach超时间隔设为3s.
每个领导结点检测成员信息传播使用的令牌是否丢失的超时间隔设为3s.
假设每个MC消息大小为10字节,DP、IPT1层的IP和IPT2层的IP生成的MU消息大小分别为20,30,40字节.
DPT,IPT1和IPT2中传播成员信息的每个令牌大小分别为20,35,70字节.
采用消息大小为512字节以及包速率为每50ms发送一个数据包的定常比特率(constantbit-rate,简称CBR)的通信流进行通信.
为了模拟动态的网络环境,通过仿真每一个代理所有直接的链路同时断裂以模拟该代理出错,但不模拟任何MH成员出错.
本文使用NS-2中的确定性模型[31],有以下4个参数:Start-Time表示代理开始出错的时间,Up-Interval和Down-Interval表示代理在某段时间内是好的(即没有出错)和是坏的(即出错),Ratio是模拟中可能出错的代理数与代理总数的比例.
对于所有情况,Start-Time设为从0.
0s~100.
0s的一个随机值.
使用{Up-Time,Down-Time,Ratio}的三元组表示结点出错概率,在模拟中设定{95.
0s,5.
0s,0.
2},{95.
0s,5.
0s,1.
0},{90.
0s,10.
0s,1.
0}分别表示1.
0%,5.
0%和10.
0%的结点出错概率.
在代理检测其当前邻居是否出错的Freshnesspoints方法中,η和σ参数设为50ms和200ms,在检测候选邻居可达性时,η和σ参数设为50ms和250ms.
Fast-Neighbor-Repair过程启动Slow-Neighbor-Repair过程的超时间隔王国军等:基于双向令牌的可扩展及可靠的群组成员管理941设为1s.
在每个"顶层"逻辑环中,领导结点发送请求启动ATTACH或者MERGE过程的超时间隔设为100ms.
为了模拟成员关系动态性,本文设计了使用两个参数的Join/Leave模式:Minimal/MaximalInterval定义为同一个MH的任意两个连续的Member-Join/Member-Leave事件间的最小/最大时间间隔,分别设为50s及70s.
MH触发其Member-Join事件的开始时间定义为从1.
3s~20.
0s的一个随机变量.
为了动态地控制群组成员与所有MH的成员比例为某个预期值,每次触发Member-Join事件就采用一个随机变量以确定MH是否真的加入该群组.
例如,为把SM模拟中的成员比例控制为12.
5%,即大约8个DP的集合中只有1个成员的情况,如果与MH的Member-Join事件相关的随机变量小于12.
5%,那么MH加入该群组;否则就忽略Member-Join事件.
6.
2模拟结果本文根据不同的网络规模和不同结点出错概率进行了大量的针对SM和DM模式的模拟.
把10次独立的模拟程序得出的平均值作为模拟结果.
图4和图5分别表示可扩展性和可靠性.
2.
0(256,448)(576,1008)(1024,1792)(1600,2800)1.
51.
00.
50.
0SMDM160SMDM(256,448)(576,1008)(1024,1792)(1600,2800)1401201008060Norm.
Num.
EventsJoin-Delay(ms)NetworksizeNetworksize110NetworksizeSMDM(256,448)(576,1008)(1024,1792)(1600,2800)1009080706050404.
2Service-Speed(s)NetworksizeSMDM(256,448)(576,1008)(1024,1792)(1600,2800)4.
14.
03.
93.
83.
73.
6Norm.
Size.
Msgs(Bytes)SMDM(256,448)(576,1008)(1024,1792)(1600,2800)300250200150350SMDM(1600,2800))(256,448)(576,1008)(1024,179224222018161426Handoff-Delay(ms)Norm.
Num.
MsgsNetworksizeNetworksizeFig.
4Simulationresultsforscalabilityproperty图4可扩展性的模拟结果在图4中,X轴表示网络规模,Y轴表示所评估的性能度量.
网络规模以成对的数值出现,每对数值分别表示SM和DM中所模拟的结点总数.
每个子图中都有对应SM和DM的两条曲线.
这里没有给出移动性检测中的心942JournalofSoftware软件学报Vol.
19,No.
4,April2008跳/探测消息及错误检测中的心跳/探测消息的个数/大小.
由于所有拓扑结构中可靠性具有类似的趋势,这里只给出最大拓扑结构时的结果(如图5所示,X轴表示结点出错概率,Y轴表示所评估的性能度量).
图中还同时表示正规化的Member-Join/Leave/Handoff事件的个数(简称Norm.
Num.
Events).
该度量定义为,在模拟过程中,这些事件的总数除以DP总数,再除以总的模拟时间,最后乘以60.
因此,它表示每个DP在每分钟内处理这些事件的平均个数.
在两个图中,Norm.
Num.
Events度量在所有网络规模或者所有结点出错概率的情况下都基本不变.
例如,图4中SM的4种网络规模中该度量分别为0.
19,0.
20,0.
20和0.
21,而DM的4种网络规模中该度量分别为1.
47,1.
58,1.
59和1.
62.
0.
0%1.
0%5.
0%10.
0%1401201008060SMDM160SMDM2.
00.
0%1.
0%5.
0%10.
0%1.
51.
00.
50.
0Norm.
Num.
EventsJoin-Delay(ms)Nodefailureprobability(f)Nodefailureprobability(f)0.
0%1.
0%5.
0%10.
0%4.
14.
03.
93.
83.
73.
6SMDM4.
20.
0%1.
0%5.
0%10.
0%100908070605040SMDM110Handoff-Delay(ms)Service-Speed(s)Nodefailureprobability(f)Nodefailureprobability(f)SMDM3500.
0%1.
0%5.
0%10.
0%300250200150SMDM260.
0%1.
0%5.
0%10.
0%242220181614Norm.
Size.
Msgs(Bytes)Norm.
Num.
MsgsNodefailureprobability(f)Nodefailureprobability(f)Fig.
5Simulationresultsforreliabilityproperty图5可靠性的模拟结果从模拟结果可以看出:(1)图4表示群组成员管理协议的可扩展性非常好.
当网络规模增大且成员密度固定时,该协议的性能即Join-Delay,Handoff-Delay和Service-Speed,保持很高且在很小范围内发生变化,然而性能开销即Norm.
Num.
Msgs或Norm.
Size.
Msgs很小且总保持在同一水平.
例如,SM中4种网络规模的Join-Delay度量分别为99.
42ms,101.
39ms,101.
83ms,103.
18ms,最大变化量仅为103.
1899.
42=3.
76ms;DM中4种网络规模的Join-Delay度量分王国军等:基于双向令牌的可扩展及可靠的群组成员管理943别为67.
11ms,67.
90ms,70.
24ms,70.
70ms,最大变化量仅为70.
7067.
11=3.
59ms.
另外,SM中Norm.
Num.
Msgs和Norm.
Size.
Msgs的最大值分别为每个代理每秒22.
38个信号消息和每个代理每秒280.
43字节;相应地,DM中的最大值分别为24.
21个信号消息和303.
19字节.
Signaling-Overhead度量的两条曲线中,随着网络规模的扩大,Signaling-Overhead具有减小的趋势.
因为每个逻辑环中用于传播成员改变/成员关系更新消息的令牌消息是所有信号消息中最重要的组成部分之一,可以计算出不同网络拓扑结构中令牌总数与有线结点总数的比例.
由于逻辑环的总数也就是令牌的总数会随着层次环结构的变化而变化,可以利用模拟开始时的初始值来估计该值.
因此,4种模拟的网络拓扑结构中该比例分别为2*(1+4+4*4)/(3*8*8),2*(1+6+6*6)/(3*12*12),2*(1+8+8*8)/(3*16*16),即21.
88%,19.
90%,19.
02%和18.
50%.
可以看到,当网络规模增大时,比例变小.
(2)图5表示,当网络规模和成员密度都固定不变时,层次环中的结点出错概率对该协议的性能有一定的影响.
随着结点出错概率从0.
0%增大到10.
0%,性能会适度地降低.
例如,SM中4种结点出错概率的Handoff-Delay度量分别为55.
72ms,59.
38ms,100.
19ms,109.
50ms,最大错误情况和无错误情况之间的最大变化量仅为109.
5055.
72=53.
78ms;DM中4种结点出错概率的Handoff-Delay度量分别为56.
51ms,55.
66ms,85.
77ms,103.
41ms,最大错误情况和无错误情况之间的最大变化量仅为103.
4156.
51=46.
90ms.
(3)在图4和图5中,可以观察到每个性能度量的一些趋势.
Join-Delay度量受到群组成员密度的影响.
如果成员分布稠密,例如DM,则对于MH来说很可能它一加入DP就能立即收到消息;相反,如果成员分布稀疏,例如SM,则当MH加入DP时,由于该DP可能不得不开始加入层次环而使MH必须等待一段时间才能接收消息.
这就是Join-Delay子图中两条曲线之间有明显间隙的原因.
Handoff-Delay度量对群组成员密度则不敏感,主要是因为该协议使用一种预留机制,该机制弱化了SM和DM间的差异.
Service-Speed度量主要受到网络规模的影响,随着网络规模的增大它只是略微地增大.
然而,它对结点出错概率和成员密度不敏感.
这是因为模拟中把层次结构的高度固定为4层,生成Member-Update消息和Membership-Update消息的超时间隔固定为1s.
而在实际环境中,这些参数根据不同应用的需要可能发生变化.
因此,这里只是给出了用于评估该协议的一个相对的Service-Speed度量.
Signaling-Overhead度量主要受到成员密度的影响,而对网络规模和结点出错概率不敏感.
主要原因是SM中群组大小和代理个数比相同网络规模的DM中群组大小和代理个数都小得多.
因此,SM中的信号消息个数与大小自然比DM中的要少,从而可以看到,Signaling-Overhead子图中的两条曲线之间有很明显的间隙.
7结束语本文的主要贡献是:(1)提出了一个适合于移动群组通信的新颖的层次环结构,它是逻辑环和逻辑树的结合模型,利用了逻辑环的简单性与逻辑树的可扩展性;(2)基于该模型提出了一种基于局部群组的成员信息传播算法,对于移动因特网环境中提供可扩展的、可靠的群组通信服务非常重要;(3)提出了一种能够满足及时性和准确性、基于邻居检测的拓扑结构维护算法,它是成员信息传播算法高效、可靠、一致运行的基础.
本文还论证了该协议具有与基于树的协议一样高的效率,因为只有自底向上的逻辑环序列才需要参与成员信息传播,而不是层次环结构中所有逻辑环.
作为将来的工作,我们将扩展该协议,处理具有恶意入侵行为的Byzantine类型的错误.
与本文基于崩溃类型这种错误类型相比,基于Byzantine错误类型的研究将更具挑战性.
References:[1]FasbenderA,ReichertF,GeulenE,HjelmJ,WierlemannT.
Anynetwork,anyterminal,anywhere.
IEEEPersonalCommunications,1999,6(2):2230.
[2]VarshneyU.
Multicastsupportinmobilecommerceapplications.
IEEEComputer,2002,35(2):115117.
[3]DuttaA,ChennikaraJM,ChenW,AltintasO,SchulzrinneH.
Multicastingstreamingmediatomobileusers.
IEEECommunicationsMagazine,2003,41(10):8189.
[4]DuttaA,SchulzrinneH.
MarconiNet:Overlaymobilecontentdistributionnetwork.
IEEECommunicationsMagazine,2004,42(2):6475.
944JournalofSoftware软件学报Vol.
19,No.
4,April2008[5]ShiML,XiangY.
Groupcommunication.
JournalofChinaInstituteofCommunications,1998,19(1):4553(inChinesewithEnglishabstract).
[6]PanJP,GuGQ.
Modelofgroupcommunicationsandprojectionfortransportprotocols.
JournalofSoftware,1998,9(8):574579(inChinesewithEnglishabstract).
[7]WangG,CaoJ,ChanKCC.
Afaulttolerantgroupcommunicationprotocolinlargescaleandhighlydynamicmobilenext-generationnetworks.
IEEETrans.
onComputers,2007,56(1):8094.
[8]DeeringS,CheritonDR.
MulticastroutingindatagraminternetworksandextendedLANs.
ACMTrans.
onComputerSystems,1990,8(2):85110.
[9]CastroM,DruschelP,KermarrecAM,RowstronAIT.
Scribe:Alarge-scaleanddecentralizedapplication-levelmulticastinfrastructure.
IEEEJournalonSelectedAreasinCommunications,2002,20(8):14891499.
[10]JinZQ,XiangXJ,ChenPP.
On-Demandbranchingmulticast.
JournalofSoftware,2003,14(3):553561(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/14/553.
htm[11]DolevD,MalkiD.
Thetransisapproachtohighavailabilityclustercommunication.
CommunicationsoftheACM,1996,39(4):6470.
[12]AnastasiG,BartoliA,SpadoniF.
Areliablemulticastprotocolfordistributedmobilesystems:Designandevaluation.
IEEETrans.
onParallelandDistributedSystems,2001,12(10):10091022.
[13]RajagopalanB,McKinleyPK.
Atoken-basedprotocolforreliable,orderedmulticastcommunication.
In:Proc.
ofthe8thSymp.
onReliableDistributedSystems.
Seattle:IEEE,1989.
8493.
http://ieeexplore.
ieee.
org/[14]BabaogluO,SchiperA.
Ongroupcommunicationinlarge-scaledistributedsystems.
In:Proc.
ofthe6thWorkshoponACMSIGOPSEuropeanWorkshop:MatchingOperatingSystemstoApplicationNeeds.
NewYork:ACMPress,1994.
1722.
http://portal.
acm.
org/[15]AmirY,StantonJ.
Thespreadwideareagroupcommunicationsystem.
TechnicalReport,CNDS98-4,Baltimore:TheJohnsHopkinsUniversity,1998.
[16]AnkerT,ChocklerGV,DolevD,KeidarI.
Scalablegroupmembershipservicesfornovelapplications.
In:MavronicolasM,MerrittM,ShavitN,eds.
Proc.
oftheNetworksinDistributedComputing.
Providence:AmericanMathematicalSociety,1998.
2342.
[17]KeidarI,SussmanJ,MarzulloK,DolevD.
Moshe:AgroupmembershipserviceforWANs.
ACMTrans.
onComputerSystems,2002,20(3):191238.
[18]ChenW,TouegS,KawazoeAguileraM.
Onthequalityofserviceoffailuredetectors.
IEEETrans.
onComputers,2002,51(5):561580.
[19]SunLM,LiaoY,WuZM.
Ahierarchyreliablemobilemulticastalgorithmbasedonmixedacknowledgementmechanism.
JournalofSoftware,2002,15(6):908914(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/15/908.
pdf[20]WuQ,WuJP,XuK,LiuY.
AsurveyoftheresearchonIPmulticastinmobileInternet.
JournalofSoftware,2003,14(7):13241337(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/14/1324.
htm[21]WangSL,HouYB,HuangJH,HuangZQ.
Dynamicrange-basedmobilemulticastprotocol.
ChineseJournalofComputers,2005,28(12):20962102(inChinesewithEnglishabstract).
[22]AcharyaA,BadrinathBR.
Aframeworkfordeliveringmulticastmessagesinnetworkswithmobilehosts.
ACM/KluwerMobileNetworksandApplications,1996,1(2):199219.
[23]BrownK,SinghS.
RelM:Reliablemulticastformobilenetworks.
ComputerCommunications,1998,21(16):13791400.
[24]BrewerEA,KatzRH,ChawatheY,GribbleSD,HodesT,NguyenG,StemmM,HendersonT,AmirE,BalakrishnanH,FoxA,PadmanabhanVN,SeshanS.
Anetworkarchitectureforheterogeneousmobilecomputing.
IEEEPersonalCommunications,1998,5(5):824.
[25]ZahariadisTB,VaxevanakisKG,TsantilasCP,ZervosNA,NikolaouNA.
Globalroaminginnext-generationnetworks.
IEEECommunicationsMagazine,2002,40(2):145151.
[26]GustafssonE,JonssonA.
Alwaysbestconnected.
IEEEWirelessCommunications,2003,10(1):4955.
[27]KellererW,VogelHJ.
Acommunicationgatewayforinfrastructure-independent4Gwirelessaccess.
IEEECommunicationsMagazine,2002,40(3):126131.
王国军等:基于双向令牌的可扩展及可靠的群组成员管理945[28]TamuraT,TakahashiT,MoritaT,OhtakiK,TakedaH.
IMT-2000corenetworknodesystems.
IEEEWirelessCommunications,2003,10(1):1521.
[29]BuddhikotMM,ChandranmenonG,HanS,LeeYW,MillerS,SalgarelliL.
DesignandimplementationofaWLAN/CDMA2000interworkingarchitecture.
IEEECommunicationsMagazine,2003,41(11):90100.
[30]PerkinsC.
IPmobilitysupport.
IETFRFC2002,1996.
[31]NS-2.
http://www.
isi.
edu/nsnam/ns/附中文参考文献:[5]史美林,向勇.
群组通信研究.
通信学报,1998,19(1):4553.
[6]潘建平,顾冠群.
群组通信模型及运输协议映射.
软件学报,1998,9(8):574579.
[10]金志权,项晓晶,陈佩佩.
按需分枝组播.
软件学报,2003,14(3):553561.
http://www.
jos.
org.
cn/1000-9825/14/553.
htm[19]孙利民,廖勇,吴志美.
基于混合应答机制的层次型可靠移动组播算法.
软件学报,2002,15(6):908914.
http://www.
jos.
org.
cn/1000-9825/15/908.
pdf[20]吴茜,吴建平,徐恪,刘莹.
移动Internet中的IP组播研究综述.
软件学报,2003,14(7):13241337.
http://www.
jos.
org.
cn/1000-9825/14/1324.
htm[21]王胜灵,侯义斌,黄建辉,黄樟钦.
基于动态范围的移动组播协议.
计算机学报,2005,28(12):20962102.
王国军(1970-),男,湖南长沙人,博士,教授,博士生导师,CCF高级会员,主要研究领域为移动计算,可信计算,软件工程.
贺建飚(1964-),男,博士生,副教授,主要研究领域为计算机网络,智能识别与智能信息处理,嵌入式系统,移动机器人.
吴敏(1963-),男,博士,教授,博士生导师,主要研究领域为过程控制,鲁棒控制,智能系统.
陈松乔(1940-),男,教授,博士生导师,CCF高级会员,主要研究领域为软件工程及应用,算法及网络优化.
周薇(1980-),女,博士生,主要研究领域为网络与信息安全,群组通信.
ac.
cnJournalofSoftware,Vol.
19,No.
4,April2008,pp.
925945http://www.
jos.
org.
cnDOI:10.
3724/SP.
J.
1001.
2008.
00925Tel/Fax:+86-10-625625632008byJournalofSoftware.
Allrightsreserved.
基于双向令牌的可扩展及可靠的群组成员管理王国军+,吴敏,周薇,贺建飚,陈松乔(中南大学信息科学与工程学院,湖南长沙410083)ScalableandReliableGroupMembershipManagementwithBi-DirectionalTokensWANGGuo-Jun+,WUMin,ZHOUWei,HEJian-Biao,CHENSong-Qiao(SchoolofInformationScienceandEngineering,CentralSouthUniversity,Changsha410083,China)+Correspondingauthor:Phn:+86-731-8877711,Fax:+86-731-8877711,E-mail:csgjwang@mail.
csu.
edu.
cnWangGJ,WuM,ZhouW,HeJB,ChenSQ.
Scalableandreliablegroupmembershipmanagementwithbi-directionaltokens.
JournalofSoftware,2008,19(4):925945.
http://www.
jos.
org.
cn/1000-9825/19/925.
htmAbstract:GroupcommunicationshavebeenstudiedinthewiredInternetformanyyearsandremainaveryhotresearchtopic,especiallyonextendingtheexistingachievementsintomobileandwirelessnetworkenvironment.
Thispaperidentifiessomeinterestingproblemsinmobilegroupcommunicationsregardingdynamicgroupmembershipduetomemberjoiningandleaving,dynamiclocationsduetonodemobility,anddynamicnetworksduetonode/linkfailures.
Theseproblemsaresolvedbyproposingaring-basedhierarchyofproxieswithbi-directionaltokens.
Theproposedhierarchyisacombinationoflogicalringsandlogicaltrees,whichtakesadvantageofthesimplicityoflogicalringsandthescalabilityoflogicaltrees.
Moreimportantly,suchacombinationmakestheproposedprotocolbasedonthishierarchymorereliablethantheexistingtree-basedprotocols.
Theoreticalanalysisandsimulationstudiesoftheproposedprotocolshowthat:(1)Itscalesverywellwhenthesizeofagroupbecomeslarge;(2)Itisstronglyresilienttofailuresthatoccurinthenetwork.
Itisparticularlysuitableforthoseserviceprovidersandnetworkoperatorswhichhavedeployedtheirmachinesinahierarchicalsetting,whereeachmachinecanbelocallyconfiguredtoknowtheinformationaboutitssiblingandparentmachines.
Keywords:groupcommunications;groupmembershipmanagement;multicast;reliability;bi-directionaltokens摘要:面向有线因特网的群组通信已研究多年,目前仍是研究热点之一,尤其是将现有研究成果扩展到移动与无线网络环境方面.
研究了移动群组通信,该问题涉及群组成员关系动态性(成员加入及退出)、成员位置动态性(移动主机的移动性)和网络动态性(结点或链路出错).
提出了适合于移动群组通信的基于双向令牌的层次环模型(也称为层次环结构)以解决该问题.
该模型是逻辑环与逻辑树的结合模型,它利用了逻辑环的简单性和逻辑树的可扩展性.
更为重要的是,这样的结合使得基于层次环结构的群组通信协议比现有的基于树结构的协议更可靠.
理论分析和SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNos.
60503007,90718034(国家自然科学基金);theNationalScienceFundforDistinguishedYoungScholarsofChinaunderGrantNo.
60425310(国家杰出青年科学基金);theProgramforNewCenturyExcellentTalentsinUniversityofMinistryofEducationofChinaunderGrantNo.
NCET-06-0686(新世纪优秀人才支持计划);theProgramforChangjiangScholarsandInnovativeResearchTeaminUniversityofChinaunderGrantNo.
IRT-0661(国家教育部长江学者与创新团队发展计划)Received2006-08-03;Accepted2007-05-24926JournalofSoftware软件学报Vol.
19,No.
4,April2008模拟研究表明:(1)当群组规模增大时,该协议的可扩展性很好;(2)该协议具有很高的可靠性.
该协议特别适合于服务提供者和网络运营商将其计算设备分层次部署的情况,这时就要求每台计算设备都能局部化地维护其兄弟和父亲设备的信息.
关键词:群组通信;群组成员管理;组播;可靠性;双向令牌中图法分类号:TP393文献标识码:A近年来,随着移动计算与无线通信技术的飞速发展,由有线因特网和多种无线网络如无线局域网、蜂窝网络和卫星网络组成异构型的网络,即通常所说的移动因特网,成为了研究热点[1].
但是在这种网络环境中,许多具有挑战性的问题将比在有线网络中更难以解决,如可扩展性和可靠性.
其中一个典型应用是将数据从一个或多个发送者同时传送给多个接收者的群组通信应用,比如面向新闻信息、股市行情、天气预报、交通状况的数据广播应用和基于网络的多媒体流式应用.
但是研究表明,在移动因特网中实现高效的群组通信非常困难[24].
现有的群组通信系统(groupcommunicationsystem,简称GCS)[5,6]主要是为传统的广域网而设计的,没有考虑把移动主机(mobilehost,简称MH),如笔记本电脑、个人数字助理(personaldigitalassistant,简称PDA)、移动电话和移动可视电话当作群组成员的情况,因此无法保证在MH存在时也能高效工作.
实际上,广域网中固有的问题,如延迟大和不稳定性,仍然存在于移动因特网中.
而且,在引入MH以后可能出现频繁断开连接、频繁切换、频繁发生错误等更为困难的问题.
本文基于我们在文献[7]中的前期工作,提出了适合于移动群组通信的基于双向令牌的层次环模型(也称为层次环结构).
一方面,该模型是逻辑环与逻辑树的结合模型,它利用了逻辑环的简单性和逻辑树的可扩展性;更为重要的是,这样的结合使得基于层次环结构的群组成员管理协议比现有的基于树结构的协议更为可靠.
当树结构中某结点出错时,树结构会被打破成多棵子树,所有子树的根结点必须找到新的父结点重新附着到树结构上.
因此,树结构存在单点错误问题(singlepointoffailureproblem).
当在层次环结构中出现错误结点时,该结构也会被打破成为多个子结构.
但是,由于该结构中的每个代理维护两类候选邻居(候选的兄弟结点与候选的父结点),该结构能够尽快地维护它的完整性,从而可以解决树结构中的单点错误问题.
另一方面,该模型结合了应用层组播和网络层组播的解决方案,既利用了网络层组播的高效性,又利用了应用层组播的易于部署的特点.
从系统实现的观点看,现有两种基本的因特网组播通信技术:基于网络层的组播(以下简称IP组播[7])和基于应用层的组播(以下简称应用层组播[8]).
IP组播提出得早,组播效率高,但应用不广泛.
其主要原因是:(1)部署时需要升级所涉及的网络中所有的路由器,因而是对现有网络基础设施的一种"巨变";(2)只提供局部的群组成员管理[9],对某些需要全局成员信息的应用则不适合;(3)由于组播树的维护是基于一种平面的网络结构,因而难以扩展到大规模的组播通信中.
针对第3点,文献[10]提出了按需分支组播的方法.
该方法只要求处于组播树分枝处的路由器和本地链路上有组成员的路由器保存组播树的有关信息,将基于平面的组播树维护方式转变为层次型结构的维护方式,从而提高了可扩展性.
为了从IP组播的困境中走出来,近几年提出了大量的应用层组播方案.
由于应用层组播只要求网络提供单播服务,其他工作如组播树的维护、组播包的复制都在称为"叠加网"中的主机而不是在路由器中完成,因此部署比较容易,但是其效率可能不如IP组播高,且难以扩展到大规模网络环境中.
本文所提出的层次环模型中的结点根据实际需要可以是传统的IP组播中使用的路由器,也可以是新型的应用层组播中部署的主机.
本文第1节介绍相关工作.
第2节概述所提出的成员管理协议.
第3节和第4节分别描述所提出的成员管理协议中的两个子协议:成员信息传播子协议和拓扑结构维护子协议.
第5节分析层次环模型的可扩展性及可靠性.
第6节通过大量模拟实验给出协议的性能评价.
第7节总结全文.
1相关工作群组通信系统提供面向一组进程的通信服务.
群组是指该组进程,这些进程被称为该群组的成员.
进程可以自愿加入或退出某群组,或者因为出错而离开某群组.
群组的成员关系信息是指该群组中当前活跃的进程/成员王国军等:基于双向令牌的可扩展及可靠的群组成员管理927列表,该列表通常称为"视图".
GCS能够有效地简化容错分布式应用的编程难度.
GCS的一个重要任务是群组成员管理服务,即当成员加入、退出、切换或出错事件发生时维护成员关系信息;GCS的另一个重要任务是组播通信服务,即将信息从一个或多个源结点高效地传送到群组中的所有活跃进程.
群组成员管理算法主要分为3大类:(1)基于广播的算法[11];(2)基于协调者的算法[12];(3)基于令牌的算法[13].
基于令牌算法的基本思想是,把群组成员组织成一个逻辑环,然后让令牌环绕逻辑环以传播成员消息.
但是,基于逻辑环的算法无法很好地扩展到大规模群组通信环境中.
为了提高成员管理算法的可扩展性,研究者提出许多可扩展的成员管理模式.
成员角色模式[14]区分核心成员、客户成员和汇点成员.
Spread系统[15]集成了两个层次的协议:第1层是局域网中的Ring协议,第2层是广域网中的Hop协议.
一些基于多层的层次结构模式提供了更好的可扩展性方案.
Transis系统[11]把广域网看成组播簇结构,每个簇表示可以通过广播或组播硬件进行通信的计算机域.
通过将所有簇中挑选的代表结点形成层次结构来组织这些簇.
结构中的每一层可以看作是它以下各层的抽象,并维护它所在层的群组服务.
该系统使用抽象方法使得群组服务在广域网中具有好的可扩展性.
但是,由于高层域的代表结点实际上是最底层域中的服务器,这加重了服务器处理不同层次群组服务的负担.
特别地,如果代表结点出错,则会影响到该代表结点涉及的所有群组域.
CONGRESS系统[16]把广域网看作由域组成的层次结构.
每个域由一个CONGRESS服务器提供服务,包括局部成员服务器(localmembershipserver,简称LMS)和全局成员服务器(globalmembershipserver,简称GMS),以提供弱一致性的成员信息.
LMS设置在每个主机上为其客户提供服务.
GMS设置在树结构中,高层GMS实际上就是底层的LMS.
该结构被称为基于代表结点的树层次结构.
CONGRESS系统的新颖之处在于它的客户-服务器方法:群组成员服务由指定的成员服务器提供,但它们本身不是任何群组的成员.
作为成员参与某个或某些群组的进程成为成员服务器的客户.
客户发送请求给它的服务器以加入或退出特定的群组,而成员服务器发送成员视图给它的客户.
这种方式使得该协议在群组个数和每个群组中的成员个数上的可扩展性都非常好.
Moshe系统[17]扩展了CONGRESS系统,提供了强的成员信息语义和强的消息分发语义.
CONGRESS和Moshe系统的新意在于,它们以客户-服务器的方式建立:群组成员服务由指定的成员服务器提供,但服务器本身并不是任何群组的成员.
为了提高系统的可靠性,研究者提出许多错误检测方法.
考虑到许多应用有某种时间约束,文献[18]为错误检测器设计了一个新的规范:(1)及时性,即错误检测器需要多久才能察觉到出错;(2)准确性,即错误检测器检测结果正确的概率有多大.
文献[18]提出的Freshnesspoints方法同时满足这两个规范.
其基本思想是,如果进程q需要检测进程p是否出错,则需p每隔η个时间单位发送心跳(heartbeat)消息m1,m2,…给q.
为了决定是否怀疑p,q采用固定的时间点序列τ1,τ2,.
.
.
,这些点被称为Freshnesspoints,它们是由固定参数δ改变心跳消息的发送时间而获得的.
更具体地说,τi=σi+δ.
这里,σi是消息mi的发送时间.
对任意给定的时刻t,假设i使得t∈[τi,τi+1),则当且仅当q已经收到消息mi或更往后的消息时,q信任t时刻的p.
以上工作主要面向传统的有线广域网环境.
而在移动因特网中,群组成员关系不仅受到进程状态(活跃或出错)和链路状态(连接或断开)的影响,还受到MH的移动性的影响.
但是,针对这种网络环境的成员管理问题的研究还很少.
在移动因特网中,移动IP技术[1921]使得MH在改变网络接入点时不必改变IP地址而保持通信的连续性.
移动IP提供了面向组播移动性管理的两种基本方案:双向隧道和远程签署.
双向隧道方案向外界屏蔽了MH的移动性,MH移动时,无须重构组播树,但是组播路径不是优化的;远程签署方案具有优化的组播传输路径,但是可能引起组播树的频繁重构.
这两种基本方案代表了移动IP技术与IP组播技术结合时的两种极端情形,因而在一般情况下并不适用,其主要原因是没有充分考虑MH的移动性对组播通信性能的影响.
文献[22]提出两层的Host-View协议.
Host-View由一组移动支持站(mobilesupportstation,简称MSS)组成.
MSS代表群组中聚合的位置信息,即:只要该MSS范围内至少有一个MH仍是该群组中的成员,则该MSS代表这些成员加入该群组的Host-View;如果所有成员都退出了该MSS,则该MSS将退出Host-View.
该协议以MSS为基本的组播移动性管理单元,通过记录一组MSS而不是跟踪单个的MH,使成员管理和组播通信变得非常简单.
而且,为了把组播消息传送给由MH组成的群组,只需发送消息给该群组的Host-View中的MSS就可以928JournalofSoftware软件学报Vol.
19,No.
4,April2008满足要求.
由于大部分的任务将在MSS中完成,MH的任务将大为减少.
但是,Host-View协议不允许群组成员动态加入和退出,也没有指定一种方法用于创建和删除群组.
特别地,由于每次"显著性移动"必然导致全局更新,这不仅可能导致组播效率低,而且有可能引起长时间的服务中断.
文献[23]提出了一个3层的RelM协议以解决Host-View协议中的问题:最底层由MH组成,中间层由MSS组成,这些MSS组合成若干个MSS组,每个组由一个监督主机(supervisorhost,简称SH)控制,SH组成了第3层.
因为SH是有线网络的一部分,它可以处理大部分的协议细节,比如维持MH之间的连接以及为可靠组播通信收集确认消息.
文献[12]提出的RMP(areliablemulticastprotocolfordistributedmobilesystems)协议也是基于3层结构:一层是MH,中间层是MSS,第3层是协调者.
在RMP中,每个MSS维护一个称为local的数据结构,用来标识它所在局部范围中MH的集合.
RMP采用的系统模型相当通用,它没有限制群组成员的移动模式,并且可适用于具有不完全的空间覆盖区域的无线网络环境.
特别地,MH从一个MSS切换到另一个MSS不会导致有线网络中的任何消息交换.
在以上相关工作中,基于令牌环绕逻辑环的算法虽然简单但可扩展性不好;而基于树型层次结构的算法可扩展性好但可靠性存在问题.
本文的基本思路就是将两种结构结合起来,提出了层次环结构,使得基于该结构的成员管理算法既具有良好的可扩展性,又具有较高的可靠性.
2协议概述2.
1系统模型研究者现已提出许多面向移动因特网的网络体系结构以解决移动因特网中的异构性问题,即不同类型的MH通过不同类型的无线网络无缝地访问不同类型的应用.
典型的体系结构包括无线叠加网络体系结构[24]、全IP无线与移动网络体系结构[25]和总是最佳连接体系结构[26].
基于这些体系结构,本文提出了基于多层代理的移动因特网体系结构,如图1所示.
部署在有线因特网上的组播服务器称为全局发送者,而部署在无线网络中的组播服务器称为局部发送者.
全局发送者为整个网络中的移动用户提供组播服务,而局部服务器为有限区域的用户提供服务.
本文扩展了代理方法[24]和通信网关方法[27],在不同网络之间设置若干层次的代理,负责为服务提供商与移动用户隐藏异构性.
本文区分两种类型的代理:(1)直接代理(directproxy,简称DP),如无线局域网的接入点、蜂窝网络的基站和卫星网络的卫星,它们直接为附着的MH提供服务;(2)间接代理(intermediateproxy,简称IP),部署在组播发送者与DP之间,组播发送者与DP(及MH)之间的通信必须经由IP.
在图1中,不同的无线网络通过不同的方式连接到有线因特网上:无线接入网络(radioaccessnetwork,简称RAN)通过蜂窝网络的核心网络(corenetwork,简称CN)连接到有线因特网[28];无线局域网既能通过网关(gateway)直接连接到有线因特网,也能先通过网关再通过蜂窝网络的CN间接连接到有线因特网[29];而卫星网络可以通过固定地面站(fixedearthstation,简称FES)与有线因特网连接[25].
在图1中,代理可以是网络中独立的主机,也可以依附在一些网络实体上,例如无线局域网的网关、蜂窝网络的无线网络控制器(radionetworkcontroller,简称RNC)、GPRS服务支持结点(servingGPRSsupportnode,简称SGSN)、GPRS网关支持结点(gatewayGPRSsupportnode,简称GGSN)[28]、卫星网络的FES,甚至是有线因特网中的边界路由器.
基于该结构提出了基于代理结点的层次环模型.
图2是一个4层的例子,自顶向下分别是间接代理层2(intermediateproxytier2,简称IPT2)、间接代理层1(intermediateproxytier1,简称IPT1)、直接代理层(directproxytier,简称DPT)和移动主机层(mobilehosttier,简称MHT),上面3层根据位置相邻性(或其他特性)分别组织成一个或多个逻辑环,每个逻辑环中有且仅有一个领导结点.
领导结点除了起到普通代理的作用,还负责与层次结构中上一层的父结点通信(如果父结点存在).
领导结点是其父结点的孩子结点,父结点与该领导结点之间的关系称为父子关系.
另外,每个逻辑环中邻居的关系称为前后关系.
逻辑环中每个代理都存在该代理的前一个代理(简称前代理或前结点)以及该代理的后一个代理(简称后代理或后结点).
如果逻辑环只包含一个结点,则领导结点、前结点、后结点都是这个结点本身.
每个代理初始化时获取以下信息:(1)若干个候选的兄弟代理,该代理王国军等:基于双向令牌的可扩展及可靠的群组成员管理929通过它们与同一层逻辑环合并;(2)若干个候选的父代理,该代理通过它们附着到上一层逻辑环.
CNCNWLAN3GRANWLAN2.
5GRAN2.
5GRAN4GRANWLAN3GRANMHMHMHMHMHMHMHMHMHMHDPDPDPDPDPDPDPDPIPIPIPIPIPIPIPIPIPIPIPIPIPIPlatigidLocalserverlatigidLocalserverSatellitenetworkDPIP4GRANDPIPThewiredInternetIPIPIPIPlatigidGlobalserverAttachMovementMH:MobilehostRAN:RadioaccessnetworkWLAN:WirelessLANCN:CorenetworkDP:DirectproxyIP:IntermediateproxyFig.
1Multi-Tierproxy-basedmobileInternetarchitecture图1基于多层代理的移动因特网体系结构DPDPDPDPDPDPDPDPDPDPDPDPDPDPDPDPPDAPDAIPIPIPIPIPIPIPIPIPIPIPIPMHTDPTIPT1IPT2IPT2:Intermediateproxytier2DPT:DirectproxytierMHT:MobilehosttierIPT1:Intermediateproxytier1ProxyProxyLeaderNon-LeaderLogicallinkAttachMovementLaptopcomputersMobilephonesMobilephonesMobilevideophonesMobilevideophonesLaptopcomputersFig.
2Ring-Basedhierarchyofproxiesforgroupcommunications图2面向群组通信的基于代理结点的层次环模型最后,本节简要介绍移动性检测机制.
每一个DP周期性地在其覆盖区域中广播心跳消息.
作为群组成员的MH一旦收到心跳消息,就返回一条包含其主机标识符的招呼(greeting)消息,对DP宣告其存在.
DP一旦收到招呼消息,就把MH登记为群组成员,即MH通过DP加入层次环结构.
在此过程中,如果DP没有附着到该结构,则开始加入该结构.
MH加入该结构后,周期性地发送成员刷新(member-update)消息给DP,以刷新其存在信息.
如果在超时间隔过后DP仍没有收到刷新消息,则认为MH切换到另一个DP或者出错;如果MH从不同的DP收到若干个心跳消息,则简单地选择在它与DP之间距离最近的那个DP,然后返回一条招呼消息.
930JournalofSoftware软件学报Vol.
19,No.
4,April20082.
2局部群组的概念本文把每个DP逻辑环范围内的群组成员看作是一个基本的局部群组,把每个IP逻辑环范围中的群组成员看作是一个扩充的局部群组.
扩充的局部群组包含其子层次环结构中这些基本局部群组中存在的所有成员.
基于局部群组概念,这里以成员加入(member-join)消息为例说明成员改变消息是如何沿着层次环结构自底向上传送的.
如果MH希望加入群组,它首先发送Member-Join消息给其附着的DP,然后,该消息进入这个DP的消息队列中,接着同时执行以下两个操作:成员信息传播操作:该操作运行在DP位于的局部群组或逻辑环中,以传播Member-Join消息.
如果该消息到达局部群组或逻辑环的领导结点,则由领导结点发送到其父结点(如果父结点存在).
当领导结点的父结点收到该消息时,该消息就进入父结点的消息队列中,然后,继续在父结点所在的局部群组或逻辑环中传送.
该成员信息传播过程一直持续到Member-Join消息到达顶层的局部群组或逻辑环为止.
拓扑结构维护操作:如果DP已经在层次环结构中,则对于Member-Join消息不需要任何拓扑结构维护的操作;如果DP不在层次环结构中,则通过与其候选兄弟结点联系,尝试加入DP逻辑环.
如果至少有一个DP逻辑环满足条件,如邻接性条件,则DP加入该DP逻辑环.
如果联系过程失败,就建立一个DP逻辑环只包含这个DP本身,并设置自己为逻辑环的领导结点.
该逻辑环将与其邻接的一个DP逻辑环合并,或与上一层的候选IP联系,然后附着到其中一个IP.
该加入过程一直持续到消息到达层次环结构的顶层局部群组或顶层逻辑环为止.
对于层次环结构中的成员消息传播而言,当把每个局部群组看作是一个结点时只使用单向传播:MH请求DP更新成员信息;DP领导结点再请求其父结点更新成员信息,等等.
这样,MH和其附着的DP之间就形成客户-服务器关系;DP领导结点和其父结点也形成客户-服务器关系.
客户-服务器方法可以有效地降低协议设计的复杂性,并提高协议的可扩展性,这是因为每个成员改变消息只需传送给其父结点,而无须广播到整个网络中.
2.
3邻居检测的概念严格地说,只有已经加入群组的MH才是群组成员,层次环结构中所有代理都不是群组成员.
由于成员信息传播操作沿着层次环结构自底向上传送成员信息,则每个局部群组将包含其子层次环结构中所有群组成员的弱一致性的成员关系信息.
成员信息的准确性依赖于当层次环结构中出错时如何准确、及时地维护整个结构.
一方面,要求为系统中每个代理初始配置若干个候选邻居(候选父结点和候选兄弟结点),候选结点的配置可能随系统演化而发生变化.
本文假设在任意时刻为每个代理所配置的候选结点总数都维持在一个较小的值上,如最多为8.
另一方面,层次环结构中每个代理在任意时刻至多有4个当前邻居(前结点、后结点、父结点和孩子结点).
层次环结构中代理总数可能会很多,但是邻居个数(候选邻居和当前邻居)可以很少.
邻居检测的工作机理是:为每个代理配备一个邻居检测部件,负责监视代理的所有候选邻居和当前邻居的状态.
为了检测当前邻居是否出错,可以直接使用基于心跳消息的Freshnesspoints方法[18].
然而,为了检测候选结点是否可达,本文扩展该方法以处理探测(polling)消息.
如果进程q需要检测进程p是否可达,则q周期性地每隔η个时间单位发送探测消息m1,m2,.
.
.
到p.
当p收到探测消息后就把消息返回给q.
决定是否怀疑p的余下过程类似于基于心跳消息的Freshnesspoints方法.
错误检测时,代理发送的每个心跳消息包含该代理的前代理和后代理的结点标识符的信息(若前代理和后代理存在).
当目标代理收到该消息后就相应地更新信息.
无论每个运行拓扑结构维护操作的代理当前是否处在层次环中,都使用基于探测消息的Freshnesspoints方法以维护其候选邻居.
如果目标代理是候选父结点,则探测消息带回目标代理是否有孩子结点的信息;如果是候选兄弟结点,则带回目标代理是否在其子层次环中"顶层"逻辑环的信息,即目标代理的领导结点当前是否有父结点,以及目标代理的前代理、后代理和领导代理的结点标识符的信息(若前代理、后代理和领导代理存在).
本文假设崩溃类型的结点错误可能发生,并称这种错误为代理错误.
同时假设网络中链路错误只可能暂时地发生,而不会永久性地发生(除非链路对应的代理结点出错).
崩溃结点不能从系统接收任何消息,也无法发送任何消息给系统,而暂时出错的链路将在相当短的时间内丢弃沿该链路传送的消息.
本文基于邻居检测概念提王国军等:基于双向令牌的可扩展及可靠的群组成员管理931出了Neighbor-Repair算法(即基于当前邻居检测的层次环修复算法).
如果发生网络分区,成员管理协议在每个分区中独立运行.
当分区合并时,成员信息也合并在一起.
基于可达性检测,本文提出了Partition-Repair算法(即基于候选邻居检测的网络分区的合并算法).
本文将涉及网络分区与网络合并的错误称为网络错误.
虽然错误检测器很少出错,但它仍然有可能出错.
下面我们来说明一旦邻居检测器出错时是否会对协议造成影响.
首先,考虑进程q正在检测当前邻居p.
如果p确实出错,则无法发送和接收任何信息,因此,可以假设p总是被q正确地检测为出错.
但是,即使p没有出错,在某些情况下也可能被错误地检测为出错.
例如,从p发送到q的心跳所有消息全部丢失了.
在这种情况下,为了确保协议正确运行,需要q丢弃从p给q的所有消息,并且q停止发送任何消息给p.
这样,q认为p真的出错,p也认为q出错,因为之后p无法从q接收任何信息.
然后考虑进程q正在检测候选邻居p的情况.
如果p是真的不可达,则可假设q总能正确地检测到p是不可达的.
但是,q可能错误地检测p是不可达的,而实际上是可达的.
易知,这不会对本文的协议造成影响.
这是因为q不会把其所有可达的候选邻居检测为不可达,否则就违背了Freshnesspoints方法有相当高准确性的特征.
2.
4基本组播协议使用层次环模型的组播信息传送是由组播发送者发送组播信息给"顶层"逻辑环中的代理.
对于全局发送者,"顶层"逻辑环是整个结构的顶层逻辑环;而对于局部发送者,"顶层"逻辑环是其所位于的子结构的顶层逻辑环.
然后,组播信息沿每个逻辑环传送再转发给所有孩子结点.
最终,MH从其附着的DP接收组播信息.
这里先介绍针对组播通信的组播移动性管理概念.
对于组播通信中的位置管理,本文考虑把层次环结构视为整个组播群组的一个虚拟位置.
换言之,该层次环结构动态地变化以反映当前群组中所有群组成员的聚合位置信息.
对于组播通信中的切换管理,本文采用了预留机制.
它与成员管理的预留机制有关,但不同之处在于,当DP接收到预留消息时,如果DP已经建立了自己与其领导代理的父结点IP之间的组播路径,则丢弃这个消息;如果没有建立组播路径,则立即建立一条通向其领导代理的父结点IP的预留路径.
这样,如果MH切换到新的已经执行过预留操作的DP,则该MH能够立即接收组播消息.
由于MH的成员关系动态性与位置动态性,层次环结构中低层次比高层次变化得更快.
如果在DP逻辑环变化非常频繁时仍使用该结构,则组播传送就会变得很低效.
因此,在组播传送协议中,本文使用一个与层次环结构稍有不同的层次结构:(1)如果DP察觉到自己包含的成员个数从零变化到非零,则开始建立一条经由某些称为组播移动代理(multicastmobilityagent,简称MMA)的中间代理通向其领导代理的父结点IP的组播路径;(2)如果DP已经从邻接DP收到预留消息,且不包含任何活跃成员,则启动预留一条经由某些MMA通向其领导代理的父结点IP的组播路径;(3)如果DP退出该结构,则拆除通向其领导代理的父结点IP的组播路径.
3基于局部群组的成员信息传播子协议3.
1MH、代理、令牌的数据结构MH的数据结构.
作为群组成员的每个MH记录以下信息:GID:GroupID.
群组标识符,可以采用某种群组寻址模式,例如IP组播中的D类地址[7];DP:NodeID.
附着的DP的结点标识符;GUID:GloballyUniqueID.
MH的全局唯一标识符,例如移动IP网络的家乡地址[30];LUID:LocallyUniqueID.
MH的局部唯一标识符,例如移动IP的转交地址[30];Status:Integer.
为一整型值,典型状态如活跃、断开连接和出错.
代理的数据结构.
每个代理记录以下信息:GID:GroupID.
请见MH的数据结构;Current,Leader,Previous,Next,Parent,Child:NodeID.
分别表示层次环结构中的当前结点、领导结点、前结点、后结点、父结点和孩子结点的结点标识符;PreviousOK,NextOK,ParentOK,ChildOK:Boolean.
分别表示当前结点在层次环结构中的前结点、后结932JournalofSoftware软件学报Vol.
19,No.
4,April2008点、父结点、孩子结点的状态.
TRUE表示没有出错,FALSE表示出错或者不存在;CandidateSiblings[],CandidateParents[]:NodeID.
分别表示候选兄弟结点和候选父结点的结点标识符列表;CandidateSiblingsOK[],CandidateParentsOK[]:Boolean.
分别表示候选兄弟结点和候选父结点的状态列表.
TRUE表示可达,FALSE表示不可达或者不存在;ListOfMembers[]:MemberInfo.
以当前结点所属的逻辑环为根向下到其覆盖的所有DP及MH的子层次环中活跃成员的列表;MQ:MessageQueue.
缓存成员改变/成员关系更新消息的消息队列.
令牌的数据结构.
每个代理独立地收集、生成成员改变/成员关系更新消息,使用令牌沿着逻辑环以传送这些消息.
令牌记录以下信息:GID:GroupID.
请见MH的数据结构;Holder:NodeID.
令牌持有者的结点标识符;MQ:MessageQueue.
缓存成员改变/成员关系更新消息的消息队列.
3.
2成员信息传播算法在层次环结构中,每个代理维护当前存在于其子层次环中的所有活跃群组成员的"全局"成员信息.
群组成员管理包括两个主要任务:成员信息传播和拓扑结构维护.
这两个任务是紧密相联的,但是,这里用在这两个任务之间通信的事件把它们分开以简化处理.
本文为成员信息传播设计两种信号消息(signalingmessage):Membership-Change(简称MC)消息(即成员改变消息,该类消息与单个移动主机相关)和Membership-Update(简称MU)消息(即成员关系更新消息,该类消息包含了与多个移动主机相关的聚合成员信息).
每个逻辑环中的领导结点负责根据其ListOfMembers[]周期性地生成MU消息.
MC消息有以下几种:(1)Member-Join/Leave/Handoff消息(当MH加入、退出或切换时生成);(2)Member-Update消息(由每个作为成员的MH生成,周期性地向其附着的DP刷新其状态);(3)Member-Failure消息(当DP周期性地检查其ListOfMembers[]后发现某个MH已经闲置超过预定义的时间时发送该消息).
有3种情况可能导致错误状态:(1)作为群组成员的MH确实出错;(2)MH发送的所有Member-Update消息全部丢失;(3)MH从其附着的新DP发送给旧DP的Member-Handoff消息丢失.
在DP层中,MC消息由每个逻辑环中的令牌沿着逻辑环传播.
成员改变消息,例如Member-Join,Member-Leave,Member-Failure,Member-Handoff,由环绕在每个逻辑环中的令牌沿着层次环结构自底向上传播.
对于每个逻辑环,如果令牌成功环绕一轮后没有丢失,在使用某种重传机制的基础上,令牌的控制权可靠地转移到逻辑环中的下一个结点.
令牌的控制权成功转移后,逻辑环中所有代理都已获得了相同的成员关系.
算法1表示在每个DP逻辑环中运行的成员信息传播算法.
算法1.
One-Round令牌传递的成员信息传播算法.
输入:令牌(token)所处的当前结点CurNode和CurNode所属的逻辑环;输出:沿着逻辑环传播成员改变/成员关系更新消息.
1.
WhileTRUEDo{2.
OnReceivingaToken:3.
IfToken.
Holder==CurNode.
CurrentThen4.
LetToken.
MQbeempty;5.
ElseifToken.
MQisnotemptyThen6.
UpdateCurNode.
ListOfMembers[]withToken.
MQ;7.
ElseifCurNode.
MQisnotemptyThen{8.
LetToken.
HolderbeCurNode9.
LetToken.
MQbeCurNode.
MQ;王国军等:基于双向令牌的可扩展及可靠的群组成员管理93310.
}11.
TransfertheTokentothenextnodereliably;12.
}13.
//注释1.
当令牌环绕一轮后,其MQ被设为空;14.
//然后空令牌沿着下一条逻辑链路被可靠地转移到一个MQ不为空的结点.
15.
//注释2.
由于代理结点可能出错(见第4节),因此令牌可能会丢失.
16.
//本文假设,如果领导结点在超时间隔以后没有收到令牌,则领导结点将重新生成一个新的令牌.
从某一层的领导结点到其上一层的父结点(如果父结点存在)的MU消息的传播,本文采用超时机制:首先每个领导结点周期性地发送其成员信息给其父结点,成员信息保存在其父结点的MQ中;然后,父结点使用One-Round令牌传递算法沿着它所在IP层的逻辑环传播成员信息.
沿层次环结构传播成员改变/成员关系更新消息的成员信息传播算法见算法2.
算法2.
沿着层次环结构的成员信息传播算法.
输入:层次环结构中的每一个代理所维护的不同层次的成员信息;输出:沿着层次环结构自底向上传播成员改变/成员关系更新信息.
1.
ParForeachproxyrunningtheproposedprotocolDo{2.
OnTimeouteventforgeneratingMUmessagesataleaderproxy:3.
GenerateandSendMUmessagestotheleaderproxy'sparent(ifexists);4.
OnReceivinganMCmessageataproxy://该代理是DP;5.
KeeptheMCmessageintheproxy'sMQ;6.
//MQ中的消息按照One-Round令牌传递的成员信息传播算法传送;7.
OnReceivinganMUmessageataproxy://该代理是IP;8.
KeeptheMUmessageintheproxy'sMQ;9.
//MQ中的消息按照One-Round令牌传递的成员信息传播算法传送.
10.
}层次环中每个代理独立地收集、生成、发送MC/MU消息,成员信息传播算法以并行及分布式的方式运行.
为加快成员信息在逻辑环中的传播并提高其可靠性,可以在每个逻辑环中设置双向令牌以传送成员信息.
双向令牌实际上是在逻辑环的两个相反方向上运行且互相独立的两个令牌.
为简单起见,算法中没有表示出双向令牌.
需要指出的是,该算法也没有表示两个令牌之间的信息交换,这是因为只是使用两个令牌在同一个逻辑环中传播成员信息,这样可以比使用单个令牌时的可靠性高些;另外,本文提出的成员管理协议只需要提供弱一致性的成员关系信息,因此不需要两个令牌中传播严格一致的成员信息.
这里指出,在成员信息传播子协议中可以使用预留机制让DP的若干个邻接DP事先加入层次环.
如果DP察觉到其包含的活跃成员从零变到非零,则生成并发送预留消息给其所有邻接DP.
DP一旦收到该消息,若已包含活跃成员,则简单地丢弃该消息;否则,立即加入层次环.
这样,如果MH切换到已经执行过预留操作的DP中,则MH立即通过新的DP加入层次环.
这里还需指出,层次环结构在两种情况下会动态改变:一是结构中出现错误时(将在第4节讨论);另一种是MH动态加入、退出、切换以及因为群组成员出错而离开时.
对于后一种情况,存在两类拓扑结构改变事件:一类是Proxy-Join/Leave事件,引起单独的结点加入或退出结构中同一层上的某个逻辑环;另一类是Proxy-Attach/Detach事件,引起相邻两层上的结点之间的父子关系的建立或结束.
成员信息传播算法中的两种情况会导致拓扑结构改变事件:一种情况发生在DP收到成员信息传播算法生成的MC消息时:如果MH切换到另一个DP(或加入一个DP)并且它正好是附着到该DP上的第一个成员,则该DP开始加入该结构;若该MH是它所退出(或出错所在)的DP中的最后一个成员,则该DP可能开始从结构上退出.
DP层的Proxy-Attach/Detach事件可能进一步引发DP的934JournalofSoftware软件学报Vol.
19,No.
4,April2008父亲IP相应地加入、退出、附着或离开该结构.
第2种情况发生在IP收到成员信息传播算法生成的MU消息时:若收到MU消息的IP所维护的活跃成员数由零变为非零,并且该IP不在结构中,将会导致Proxy-Join或Proxy-Attach事件;同样地,若活跃成员数由非零变为零,并且该IP在该结构中,则会导致Proxy-Leave或Proxy-Detach事件的发生.
为了避免Proxy-Leave/Detach事件引起结构的频繁重构,本文采用Lazy-Leave/Detach机制.
只有当DP在整个超时间隔内都不包含活跃成员,并且它的所有邻居DP也不包含活跃成员时,它才离开该结构.
相应地,对于IP,只有当它在整个超时间隔内都不包含任何孩子结点时才离开该结构.
3.
3成员信息传播子协议的性能分析当成员加入、退出、切换、出错以及层次环结构中结点出错时,层次环结构会动态变化.
下面的分析中使用了以下性能度量:Join-Delay,定义为从MH发出加入该群组的意愿到它接收到第1个组播数据包的时间间隔;Handoff-Delay,定义为从MH检测出它已经进入一个新的DP到它从新DP接收到第一个组播数据包的时间间隔;Service-Speed,定义为从MH发出加入该群组的意愿到它的成员信息成功地在顶层逻辑环的领导结点登记的时间间隔;Signaling-Overhead,定义为成员信息传播与拓扑结构维护中所有代理接收到的信号数据包总数或总大小除以代理的总数,然后再除以总的执行时间,它代表协议的平均开销.
本文基于上述度量作最坏情况分析.
这里,使用Member-Join消息在层次环结构中传送的过程为例来说明.
假设3.
1.
如果MH通过其附着的DP请求加入群组,该DP总是成功地把MH登记为群组成员,而无论该DP目前是否处于层次环结构中.
假设该操作时间的界为TMH-Join-Registration.
假设3.
2.
如果代理通过候选兄弟结点或候选父结点请求加入层次环结构,则该代理总是成功地通过其中一个候选兄弟结点与同一层的兄弟逻辑环合并,或通过其中一个候选父结点附着到上一层逻辑环.
假设该操作时间的界为TProxy-Merge-Attach.
假设3.
3.
如果Member-Join消息已经进入代理的MQ中,该消息总是被成功地传送到该代理所在逻辑环的领导结点.
假设该操作时间的界为TProxy-MS-Leader.
假设3.
4.
如果Member-Join消息到达领导结点的ListOfMembers[],该消息总是成功地传送到该领导结点的父结点(如果父结点存在).
假设这个操作时间的界为TProxy-MS-Parent.
假设3.
5.
假设层次环结构中的任何MH总是成功地接收组播消息的时间的界为TMulticast-Transmission.
这里把上述假设作为一个整体称为Always-Successful-assumptions(简称AS-assumptions).
AS-assumptions是合理的:(1)为了提供给用户最佳的服务,服务提供商或网络运营商有责任在其服务范围内合理地部署所有的代理;(2)如果代理部署不合理,则处于相应区域的用户可能得不到好的服务.
在第1种情况下,AS-assumptions成立;而在第2种情况下,AS-assumptions有可能不成立.
有了AS-assumptions,本文首先证明Join-Delay与Service-Speed度量的界.
定理3.
1.
假设AS-assumptions在高度为h的层次环结构中成立,在最坏情况下,Join-Delay的界为TMH-Join-Registration+(h1)*(2*TProxy-Merge-Attach+TProxy-MS-Leader+TProxy-MS-Parent)TProxy-Merge-AttachTProxy-MS-Parent+TMulticast-Transmission(1)证明:假设逻辑环的领导结点只通过其候选父结点附着到层次环结构中,不会通过其候选兄弟结点与其他逻辑环合并.
在最坏情况下:(1)当MH发送Member-Join消息给其附着的DP以请求加入群组时,首先花费TMH-Join-Registration时间把它登记为其附着的DP中的群组成员;(2)如果该DP恰好不在层次环中,它就请求通过其候选兄弟结点之一与逻辑环合并,这将花费TProxy-Merge-Attach时间;(3)Member-Join消息沿逻辑环传送到领导结点,将花费TProxy-MS-Leader时间;(4)如果该领导结点恰好不在层次环中,则请求通过其候选父结点之一附着上一层逻辑环,这将花费TProxy-Merge-Attach时间;(5)Member-Join消息从领导结点传送到其父结点,这将花费TProxy-MS-Parent时王国军等:基于双向令牌的可扩展及可靠的群组成员管理935间;(6)对于上面h2层的IP层,重复以上步骤(2)~步骤(5);(7)至此,建立起沿层次环自底向上成员信息传播的一条完整"路径";(8)组播数据包沿反向"路径"自顶向下传播,最终被MH接收到,这将花费TMulticast-Transmission时间.
定理3.
2.
假设AS-assumptions在高度为h的层次环结构中成立,在最坏情况下,Service-Speed的界为TMH-Join-Registration+(h1)*(2*TProxy-Merge-Attach+TProxy-MS-Leader+TProxy-MS-Parent)TProxy-Merge-AttachTProxy-MS-Parent(2)证明:证明过程与定理3.
1的证明过程相似.
唯一的区别是这里去掉了传送组播数据包的时间.
从上述两个定理来看,Join-Delay的界还大于Service-Speed的界.
实际上,这只是最坏情况才可能如此.
在平均情况下,Join-Delay很小,因为MH附着的DP可能已经位于层次环中.
然后论证Signaling-Overhead度量.
每个代理的MQ中所有成员消息都会作为一个聚合消息沿每个逻辑环传送,这样信号开销会大为减少.
另外,成员信息传播从逻辑环的领导结点到领导结点的父结点基于超时机制,这也减少了信号开销.
因此,可以认为层次环结构中每个代理的信号开销的界为常数.
对Handoff-Delay度量可以作相似的分析,这里从略.
因为切换处理过程通常采用某种预留机制,当MH切换到一个新的DP中时,大部分时间都能立即接收到组播消息.
因此,在平均情况下,Handoff-Delay度量都比Join-Delay要小,有关这一点将在第6节的模拟分析中得以验证.
4基于邻居检测的拓扑结构维护子协议本节研究层次环中的两种错误对协议的影响:(1)代理错误,可导致层次环结构中父子关系、前后关系结束;(2)网络错误,可造成在网络分区期间系统中形成若干个互不相交的子层次环结构.
本节首先描述处理代理错误的Neighbor-Repair算法,然后描述处理网络错误的Partition-Repair算法.
4.
1Neighbor-Repair算法处理代理错误的Neighbor-Repair算法如下.
对于层次环结构中的每一个代理:情况1.
如果代理是领导结点,且其错误检测部件(failuredetectioncomponent,简称FDC)报告其父代理出错,则将该代理的ParentOK设置为FALSE,指示父子关系结束.
然后,它与其中一个可达候选父结点建立新的父子关系,称为ATTACH过程,或通过其中一个可达候选兄弟结点与逻辑环合并,称为MERGE过程;情况2.
如果代理的FDC报告其孩子代理出错,则将该代理的ChildOK设置为FALSE,指示父子关系结束;情况3.
如果代理的FDC报告其前代理出错,则将PreviousOK设置为FALSE.
为去掉逻辑环中的错误结点,代理将发送Previous-Repair消息给前代理的前代理,建立它们之间的兄弟关系.
如果代理错误不常发生,与Previous-Repair消息相关的Neighbor-Repair算法会很快终止,本文称这部分算法为Fast-Neighbor-Repair过程.
如果出错的代理恰好是领导结点,在Fast-Neighbor-Repair算法终止后,该逻辑环将没有领导结点.
为了解决该问题,发送Previous-Repair消息的代理将自己设为新的领导代理,然后发送Leader-Change消息通知逻辑环中所有代理更新其领导代理.
如果代理错误频繁发生,则如果前代理的前代理也出错,则Previous-Repair消息将永久丢失.
在这种情况下,在超时间隔过后,Slow-Neighbor-Repair过程就会启动.
为了从逻辑环中去掉两个以上连续出错的代理,则发送Dest-Find消息沿逻辑环中查找目标代理(称为DESTINATION),然后建立它们之间的兄弟关系.
DESTINATION是无法沿逻辑环可靠地转发Dest-Find消息的那个代理.
因为Dest-Find消息沿逻辑环传送给DESTINATION,与Fast-Neighbor-Repair过程相比较,这部分算法需要花更长的时间才能终止,本文称其为Slow-Neighbor-Repair过程.
如果领导结点恰好是出错的结点之一,则在Slow-Neighbor-Repair算法终止之后,该逻辑环将没有领导结点.
为了解决这个问题,需要Dest-Find消息收集它到DESTINATION的路径上的领导结点信息.
如果领导结点不在路径上,DESTINATION就被设为新的领导结点,再发送一条Leader-Change消息以通知新的领导结点信息.
情况4.
如果代理的FDC报告其后代理出错,则将该代理的NextOK设为FALSE.
首先执行Fast-Neighbor-Repair过程;如果在超时间隔过后它还没有终止,则执行类似的Slow-Neighbor-Repair过程.
以上是Neighbor-Repair算法的基本设计.
但在基本设计中,由于情况3和情况4的对称操作会导致以下问题:(1)重复操作.
因为出错代理的两个邻居可能同时检测到其错误状态,它们可能分别独立地启动执行936JournalofSoftware软件学报Vol.
19,No.
4,April2008Neighbor-Repair算法.
该算法仍然可以正常运行,但是同样的操作会执行两次;(2)领导信息不一致.
由于情况3和情况4的对称操作,在发送Leader-Change消息时,逻辑环中各个代理上的领导结点信息可能会不一致;(3)逻辑环不一致.
考虑代理实际上没有出错但被错误地怀疑为出错的情况,这里需要被错误怀疑的代理将正在检测的代理也看作出错.
但是,这样会导致逻辑环不一致.
例如,有5个代理的逻辑环具有前后关系:ABCDEA;然后假设C错误地怀疑D出错,之后D也会怀疑C出错;然后C发送Next-Repair消息给E,D也发送Previous-Repair消息给B;再假设C和E的兄弟关系在B和D的兄弟关系之前已建立,即去掉D首先形成了一致的逻辑环ABCEA,再去掉C将会形成不一致的逻辑环:包括后一条链路的逻辑环A→B→D→E→A和包括前一条链路的逻辑环A←B←C←E←A.
为避免出现这些问题,只需简单地去掉情况3或情况4即可.
4.
2Partition-Repair算法如果网络出错,层次环结构被划分成若干个子层次环结构(理想情况下,每个网络分区对应一个子层次环结构),当网络分区合并时,若干个子层次环结构又合并在一起.
在出现分区期间,层次环结构中的一个逻辑环可能破裂成两个或更多个部分.
逻辑环的每个部分通过运行Neighbor-Repair算法将修复成一个新的逻辑环.
本文在网络出现分区的情况下也使用第4.
1小节的ATTACH和MERGE过程.
只有处于"顶层"逻辑环的领导结点可以发送请求以启动这两个过程.
首先定义一个领导结点的可达候选邻居结点队列(aqueueofreachablecandidateneighbors,简称QRCN)作为可达候选邻居结点的集合.
QRCN是在使用检测可达性时保留在返回的探测消息中的信息而动态形成的.
若QRCN不为空,则领导结点从其中选择一个候选邻居,该候选邻居必须不在领导结点位于的子层次环结构中,领导结点再用该候选邻居启动ATTACH或MERGE过程来处理网络分区的合并.
处理ATTACH和MERGE过程的Partition-Repair算法如下.
对于网络分区子层次环结构中"顶层"逻辑环的领导结点来说:情况1.
ATTACH过程用来在两个代理之间建立新的父子关系.
为了确保层次环结构的一致性维护,本文采用了两阶段提交协议,把每次维护看作一个事务.
每次ATTACH事务只涉及两个代理:LEADER及其某个候选父结点代理(称为PARENT).
在第1阶段,LEADER发送Leader-Attach消息给PARENT,PARENT肯定地或否定地应答.
在第2阶段,LEADER确认或回滚,通知PARENT相应地做确认或回滚.
情况2.
MERGE过程用来把两个逻辑环合并成一个逻辑环.
每个MERGE事务涉及4个代理,即LEADER、LEADER的后结点(称为NEXT)、CANDIDATE和CANDIDATE的后结点(称为CANDIDATE-NEXT).
在第1阶段,LEADER发送一个Leader-Merge消息给其他3个代理,然后,这3个代理做出肯定或否定的回复.
在第2阶段,如果LEADER收到的3个回复都是肯定的,LEADER就确认并通知另外3个代理确认;否则,LEADER回滚并通知另外3个也回滚.
当这两个逻辑环成功地合并成一个时,则LEADER发出一个从探测消息得到的领导结点信息的Leader-Change消息,通知LEADER原来逻辑环中所有代理更改新的领导结点信息.
在MERGE过程中,如果正在合并的两个逻辑环恰好是它们各自子层次环结构中的"顶层"逻辑环,则两个LEADER中结点标识符较大的结点才允许启动其事务.
4.
3拓扑结构维护子协议的性能分析当考虑到网络出现分区时,下面所提到的特征和界将适用于每个分区.
特征4.
1.
及时性.
该特征度量拓扑结构维护子协议对错误事件响应的时间.
(1)拓扑结构维护子协议基于Freshnesspoints方法来检测错误并获得可达性信息,该方法满足及时性.
(2)所有拓扑结构维护过程都是基于局部信息的,因为它们只需要知道当前邻居和候选邻居的信息.
(3)所有拓扑结构维护过程以并行与分布式方式运行并将在确定时间内终止.
对于Fast-Neighbor-Repair和Slow-Neighbor-Repair过程,如果前者在超时间隔后没有终止时,后者就会启动然后在确定时间内终止.
尤其对于ATTACH和MERGE过程,当一个过程不能正常终止,它就从其可达候选邻居集合中选择另一个候选邻居启动另一个过程.
本文假设选择过程在所有可达候选邻居中运行过一轮后,至少有一个过程会正常终止.
特征4.
2.
准确性.
这个特征度量错误发生时拓扑结构维护子协议维护层次环结构的准确程度.
王国军等:基于双向令牌的可扩展及可靠的群组成员管理937(1)基于Freshnesspoints方法可以高准确性地检测出代理错误和网络分区与网络合并.
(2)如果Freshnesspoints方法错误地怀疑没有出错的代理,就从逻辑环中去掉正在检测的代理或被错误怀疑的代理.
这样,去掉的代理将变成一个独立的代理,然后自己单独加入层次环结构中.
基于及时性和准确性,可以认为执行每次拓扑结构维护过程的时间的界为某个常数,而且层次环结构的维护是非常准确的.
另外,可以认为成员信息传播子协议中类似的性能度量的界也存在.
5层次环结构的可扩展性和可靠性的分析5.
1可扩展性的比较分析在文献[16]中,成员服务器被组织成一个基于代表结点的树结构,称为CONGRESS层次结构,其中包含局部成员服务器和全局成员服务器.
本节针对层次环结构与CONGRESS层次结构作可扩展性比较.
树结构/层次环结构中的LMS/DP个数n作为等效的可扩展性参数.
为简单起见,下面分别计算沿CONGRESS层次结构和层次环结构将成员改变消息分别传送给所有LMS和所有DP时所经过的逻辑链路的总数HopCount,它近似于CONGRESS层次结构或层次环结构中边的总数.
首先考虑CONGRESS层次结构.
在高度为h≥4、每个GMS的分支数r≥2的层次结构中,LMS的个数为n=rh2,则HopCount为31-0(,,)hdefiTreebasediHopCountnhrr+==∑(3)然后计算高度为h≥3、每个逻辑环包含r≥2个结点的层次环结构中的HopCount.
底层逻辑环中的DP总数为n=rh1,逻辑环的总数为20hiitnr==∑,则HopCount为1)1)defRingbasedHopCountnhrrtn4)正规化HopCount,即把它除以n,它代表一条成员改变消息引起的成员信息传播的"平均"消息个数.
分别把CONGRESS层次结构和层次环结构的正规化HopCount记为和-NTreebasedHC-NRingbasedHC:310hidefdefNNiTreebasedTreebasedrHCHopCountnhrn+===∑(5)20--(1)1(1)1(,,)hidefdefNNiRingbasedRingbasedrrrtnHCHopCountnhrnn=+*+*===∑(6)根据式(5)和式(6),我们给出了表1的数值分析结果.
可见,在给定相同个数的LMS/DP的情况下,层次环结构的可扩展性与树结构的可扩展性一样好.
Table1Comparisononscalabilitybetweenthetree-basedandring-basedhierarchies表1树结构与层次环结构的可扩展性对比nhr-NTreebasedHCnhr-NRingbasedHC16441.
250016341.
500064541.
312564441.
6250256641.
3281256541.
656336461.
166836361.
3333216561.
1944216461.
38891296661.
19911296561.
398264481.
125064381.
2500512581.
1406512481.
28134096681.
14264096581.
28521004101.
10001003101.
200010005101.
110010004101.
2200100006101.
1110100005101.
2220938JournalofSoftware软件学报Vol.
19,No.
4,April20085.
2可靠性的比较分析首先说明:如果把层次环结构中每个逻辑环看作是一个结点,层次环结构与树结构是同构的,则层次环结构的可靠性比树结构更高.
这是因为,当只考虑出现一个结点出错的情形时,显然,由于树结构中一个错误会把树结构破裂成若干个部分,而层次环结构中一个错误会使得一个逻辑环破裂,该结构可能不会破裂成若干个部分(除非该错误结点具有孩子结点).
实际上,当考虑同时出现多个错误时,也会存在类似状况.
然后说明:如果两个结构是同构的,树结构比基于代表结点的树结构具有更高的可靠性.
这是因为,在基于代表结点的树结构中,一个代表结点出错实际上是若干个逻辑结点出错,而在树结构中一个结点出错只是它本身出错.
因此,树结构比基于代表结点的树结构更可靠.
下面只需说明层次环结构比树结构更可靠.
树结构中如果一个结点出错,则其孩子结点只有一种选择,即去寻找新的父结点并附着其上.
而层次环结构中如果一个代理出错,则其孩子结点有两种选择:通过候选兄弟结点之一与同一层逻辑环合并,或者通过候选父结点之一附着到上一层逻辑环.
与此同时,通过运行Neighbor-Repair算法把出错代理从逻辑环中去掉.
因此在出错的情况下,层次环结构比树结构可以更可靠地维护.
以上只是非形式的比较分析.
下面从数学上给出严格的比较分析.
首先定义Function-Well(运行良好)概念.
树结构中的一个出错结点会影响到其所有孩子结点,因此,这里定义树结构的Function-Well如下:如果允许在除最低两层以外的层次结构中至多有k个结点同时出错,则称该树结构是Function-Well的.
为了计算树结构的Function-Well(简称fw)概率,假设层次结构是满的:它包含最大层数(记为h),层次结构中每个代理有最多的孩子结点数(记为r).
直观来看,在同样的网络环境中,小层次结构比大层次结构更可能Function-Well.
因此,这里使用满层次结构作最坏情况分析.
该层次结构中倒数第2层包含n=rh2个结点,从第1层~倒数第3层包含30hiitnr==∑个结点,在该层次结构中至多k个结点无法Function-Well.
假设f是层次结构中具有均匀且独立分布的结点出错概率(nodefailureprobability),则树结构的Function-Well概率为()-01kdeftnifwiTreebaseditnProbnhrfkffi==*∑(7)再计算逻辑环的Function-Well概率.
如果在逻辑环中不能出现两个连续的代理同时出错,则只需要Fast-Neighbor-Repair过程修复逻辑环.
在这种情况下,称逻辑环Function-Well.
如果逻辑环无法Function-Well,即逻辑环中至少有两个连续的代理同时出错,则需要Slow-Neighbor-Repair过程修复逻辑环.
然后讨论计算整个层次环的Function-Well概率所使用的参数:n表示DP的个数,h表示层次环的高度,r表示逻辑环中的结点数,f表示层次环结构中具有均匀且独立分布的结点出错概率,k表示不能Function-Well的逻辑环的最大个数.
如果层次环结构中至多k个逻辑环不能Function-Well,则认为该层次环结构是Function-Well的.
定义每个逻辑环的Function-Well概率t为20=(,)(1)rdeffwriiringitProbBriff==∑*(8)在式(8)中,B(r,i)代表错误发生的个数,即在逻辑环的r个结点中恰好有i个结点出错,而且不会发生互为邻居的两个结点出错.
对于0≤i≤3与r≥5,很容易推断出B(r,i)如下:(,0)10rBr==(9)(,1)1rBrr==(10)(3)(,2)212rrrrBr==(11)王国军等:基于双向令牌的可扩展及可靠的群组成员管理93924(920)(,3)31116rrrrrrrBr==(12)而当i≥4时难以得到相应的公式,但可以由计算机程序计算在02ri≤≤时B(r,i)的值.
表2是其数值结果.
接着,在假设满层次环结构时作最坏情况分析.
该层次环包含最大层数,每个逻辑环具有最多结点个数.
这样,层次环中包含个逻辑环,至多k个逻辑环不能Function-Well.
层次环的Function-Well概率表示为20hiitnr==∑-01)kdeffwtniiRingbaseditnProbnhrfktti==∑(13)从式(7)和式(13)得出的数值分析结果见表3.
结论如下:(1)在网络规模和结点出错概率相同的情况下,层次环结构总比树结构更为可靠.
特别地,随着LMS/DP个数的增多和结点出错概率的增大,树结构的可靠性大为降低,而层次环的可靠性只会适度地降低.
例如,在最大层次环结构中,当结点出错概率从0.
1%增大到5.
0%时,树结构的Function-Well概率从99.
980%降到了7.
999%,层次环结构从100.
000%只降到51.
216%;(2)当结点出错概率设定为0.
1%,并且DP个数多达1000个时,层次环结构只需运行Fast-Neighbor-Repair过程修复该结构,此时,该结构的Function-Well概率高达99.
889%;如果允许Slow-Neighbor-Repair过程最多执行2次,则概率可高达100.
0%;(3)在允许Slow-Neighbor-Repair过程至多执行2次的Function-Well层次环的定义以及99.
980%的高概率的情况下,拥有DP个数多达1000个的群组可确保在结点出错概率设定为0.
1%时,该结构仍能Function-Well;(4)当结点出错概率增大到5.
0%时,小规模的层次环结构仍然能以高概率Function-Well.
例如,对于包含64个DP的小规模层次环而言,其Function-Well的概率是99.
900%,但是对于包含1000个DP的大规模层次环只有51.
216%的低概率Function-Well.
Table2B(r,i)valuesforcomputingthefunction-wellprobabilityofalogicalring表2计算逻辑环的Function-Well概率的B(r,i)值rIB(r,i)riB(r,i)401822041483164228426011001616101106291023563210350801104258181052Table3Comparisononreliabilitybetweenthetree-based(h=5)andring-based(h=4)hierarchies表3树结构(h=5)与层次环结构(h=4)的可靠性比较nrf(%)k-fwTreebasedProb(%)-fwRingbasedProb(%)nrf(%)k-fwTreebasedProb(%)-fwRingbasedProb(%)6440.
1097.
92199.
99251280.
1092.
95799.
9426440.
1199.
979100.
00051280.
1199.
749100.
0006440.
12100.
000100.
00051280.
1299.
994100.
0006441.
0080.
97399.
17251281.
0048.
01494.
3816441.
0198.
14999.
99751281.
0183.
41999.
8416441.
0299.
884100.
00051281.
0296.
29399.
9976445.
0034.
05681.
82551285.
002.
36524.
7766445.
0171.
69798.
31751285.
0111.
45159.
6786445.
0291.
50899.
90051285.
0228.
66883.
92521660.
1095.
78999.
9741000100.
1089.
48999.
88921660.
1199.
912100.
0001000100.
1199.
432100.
00021660.
1299.
999100.
0001000100.
1299.
980100.
00021661.
0064.
91097.
4781000101.
0032.
77289.
59121661.
0193.
10499.
9691000101.
0169.
51799.
44321661.
0299.
084100.
0001000101.
0289.
93199.
98021665.
0011.
01853.
9871000105.
000.
3377.
071921665.
0135.
95587.
5061000105.
012.
30426.
03121665.
0263.
51697.
6691000105.
027.
99951.
216940JournalofSoftware软件学报Vol.
19,No.
4,April20086性能评价6.
1模拟方案本文的模拟实验中使用NS-2模拟工具[31]模拟4层的层次环结构.
DP被配置成m*n的网格.
IPT1中有4mn*个IP,IPT2中有4mn*个IP和32mn*个其他代理,其中一个代理还作为组播源.
初始时,在稀疏模式(sparsemode,简称SM)模拟过程中,每个DP都有一个MH附着;在稠密模式(densemode,简称DM)模拟过程中,每个DP有4个MH附着.
在任何时候,SM模拟中由8个DP构成的集合中大约有1个群组成员,DM模拟的每个DP中大约有1个群组成员.
每个代理初始配置4个候选兄弟结点和4个候选父结点.
图3是一个4*4的DP配置的例子,每个DP逻辑环最初由4个DP构成.
本文模拟了8*8,12*12,16*16,20*20的DP配置,每个DP逻辑环最初由4个DP构成,每个IP逻辑环最初分别由4,6,8,10个IP构成.
SM模拟中的最小拓扑结构由64个MH、64个DP、IPT1中的16个IP、IPT2中的16个IP和96个其他代理构成,其结点总数是256个.
如果每个DP的覆盖区域为670m*670m,则其总覆盖区域为5360m*5360m.
DM模拟中的最大拓扑结构由1600个MH、400个DP、IPT1中的100个IP、IPT2中的100个IP和600个其他代理构成,其结点总数是2800个.
如果每个DP的覆盖区域为670m*670m,则其总覆盖区域为13400m*13400m.
DP2DP3DP4DP1DP2DP3DP4DP1DP2DP3DP4DP1DP4DP2DP3DP1Non-LeaderMHLeaderCoverageareaLogicalringPhysicallinkLogicallinkMHmovementFig.
3Example4*4DPconfiguration图34*4DP配置的例子在所有方案中,模拟总时间为600s.
有线链路带宽为10Mbps,链路延迟为10ms,消息丢失率为1.
0%;DP和MH之间的无线链路的等效带宽为2Mbps,链路延迟为20ms,消息丢失率为2.
0%.
信号消息重传的超时间隔设定为100ms,最大重传次数为3.
在作移动性检测时,每个DP的超时间隔为1s,MH向其附着的DP刷新其状态的超时间隔设为1s.
每个逻辑环中领导结点的成员更新间隔为1s.
采用最大速率为15m/s、暂停时间为5s的CMU移动性模型[31]和每个代理从层次结构真正退出、离开的Lazy-Leave/Detach超时间隔设为3s.
每个领导结点检测成员信息传播使用的令牌是否丢失的超时间隔设为3s.
假设每个MC消息大小为10字节,DP、IPT1层的IP和IPT2层的IP生成的MU消息大小分别为20,30,40字节.
DPT,IPT1和IPT2中传播成员信息的每个令牌大小分别为20,35,70字节.
采用消息大小为512字节以及包速率为每50ms发送一个数据包的定常比特率(constantbit-rate,简称CBR)的通信流进行通信.
为了模拟动态的网络环境,通过仿真每一个代理所有直接的链路同时断裂以模拟该代理出错,但不模拟任何MH成员出错.
本文使用NS-2中的确定性模型[31],有以下4个参数:Start-Time表示代理开始出错的时间,Up-Interval和Down-Interval表示代理在某段时间内是好的(即没有出错)和是坏的(即出错),Ratio是模拟中可能出错的代理数与代理总数的比例.
对于所有情况,Start-Time设为从0.
0s~100.
0s的一个随机值.
使用{Up-Time,Down-Time,Ratio}的三元组表示结点出错概率,在模拟中设定{95.
0s,5.
0s,0.
2},{95.
0s,5.
0s,1.
0},{90.
0s,10.
0s,1.
0}分别表示1.
0%,5.
0%和10.
0%的结点出错概率.
在代理检测其当前邻居是否出错的Freshnesspoints方法中,η和σ参数设为50ms和200ms,在检测候选邻居可达性时,η和σ参数设为50ms和250ms.
Fast-Neighbor-Repair过程启动Slow-Neighbor-Repair过程的超时间隔王国军等:基于双向令牌的可扩展及可靠的群组成员管理941设为1s.
在每个"顶层"逻辑环中,领导结点发送请求启动ATTACH或者MERGE过程的超时间隔设为100ms.
为了模拟成员关系动态性,本文设计了使用两个参数的Join/Leave模式:Minimal/MaximalInterval定义为同一个MH的任意两个连续的Member-Join/Member-Leave事件间的最小/最大时间间隔,分别设为50s及70s.
MH触发其Member-Join事件的开始时间定义为从1.
3s~20.
0s的一个随机变量.
为了动态地控制群组成员与所有MH的成员比例为某个预期值,每次触发Member-Join事件就采用一个随机变量以确定MH是否真的加入该群组.
例如,为把SM模拟中的成员比例控制为12.
5%,即大约8个DP的集合中只有1个成员的情况,如果与MH的Member-Join事件相关的随机变量小于12.
5%,那么MH加入该群组;否则就忽略Member-Join事件.
6.
2模拟结果本文根据不同的网络规模和不同结点出错概率进行了大量的针对SM和DM模式的模拟.
把10次独立的模拟程序得出的平均值作为模拟结果.
图4和图5分别表示可扩展性和可靠性.
2.
0(256,448)(576,1008)(1024,1792)(1600,2800)1.
51.
00.
50.
0SMDM160SMDM(256,448)(576,1008)(1024,1792)(1600,2800)1401201008060Norm.
Num.
EventsJoin-Delay(ms)NetworksizeNetworksize110NetworksizeSMDM(256,448)(576,1008)(1024,1792)(1600,2800)1009080706050404.
2Service-Speed(s)NetworksizeSMDM(256,448)(576,1008)(1024,1792)(1600,2800)4.
14.
03.
93.
83.
73.
6Norm.
Size.
Msgs(Bytes)SMDM(256,448)(576,1008)(1024,1792)(1600,2800)300250200150350SMDM(1600,2800))(256,448)(576,1008)(1024,179224222018161426Handoff-Delay(ms)Norm.
Num.
MsgsNetworksizeNetworksizeFig.
4Simulationresultsforscalabilityproperty图4可扩展性的模拟结果在图4中,X轴表示网络规模,Y轴表示所评估的性能度量.
网络规模以成对的数值出现,每对数值分别表示SM和DM中所模拟的结点总数.
每个子图中都有对应SM和DM的两条曲线.
这里没有给出移动性检测中的心942JournalofSoftware软件学报Vol.
19,No.
4,April2008跳/探测消息及错误检测中的心跳/探测消息的个数/大小.
由于所有拓扑结构中可靠性具有类似的趋势,这里只给出最大拓扑结构时的结果(如图5所示,X轴表示结点出错概率,Y轴表示所评估的性能度量).
图中还同时表示正规化的Member-Join/Leave/Handoff事件的个数(简称Norm.
Num.
Events).
该度量定义为,在模拟过程中,这些事件的总数除以DP总数,再除以总的模拟时间,最后乘以60.
因此,它表示每个DP在每分钟内处理这些事件的平均个数.
在两个图中,Norm.
Num.
Events度量在所有网络规模或者所有结点出错概率的情况下都基本不变.
例如,图4中SM的4种网络规模中该度量分别为0.
19,0.
20,0.
20和0.
21,而DM的4种网络规模中该度量分别为1.
47,1.
58,1.
59和1.
62.
0.
0%1.
0%5.
0%10.
0%1401201008060SMDM160SMDM2.
00.
0%1.
0%5.
0%10.
0%1.
51.
00.
50.
0Norm.
Num.
EventsJoin-Delay(ms)Nodefailureprobability(f)Nodefailureprobability(f)0.
0%1.
0%5.
0%10.
0%4.
14.
03.
93.
83.
73.
6SMDM4.
20.
0%1.
0%5.
0%10.
0%100908070605040SMDM110Handoff-Delay(ms)Service-Speed(s)Nodefailureprobability(f)Nodefailureprobability(f)SMDM3500.
0%1.
0%5.
0%10.
0%300250200150SMDM260.
0%1.
0%5.
0%10.
0%242220181614Norm.
Size.
Msgs(Bytes)Norm.
Num.
MsgsNodefailureprobability(f)Nodefailureprobability(f)Fig.
5Simulationresultsforreliabilityproperty图5可靠性的模拟结果从模拟结果可以看出:(1)图4表示群组成员管理协议的可扩展性非常好.
当网络规模增大且成员密度固定时,该协议的性能即Join-Delay,Handoff-Delay和Service-Speed,保持很高且在很小范围内发生变化,然而性能开销即Norm.
Num.
Msgs或Norm.
Size.
Msgs很小且总保持在同一水平.
例如,SM中4种网络规模的Join-Delay度量分别为99.
42ms,101.
39ms,101.
83ms,103.
18ms,最大变化量仅为103.
1899.
42=3.
76ms;DM中4种网络规模的Join-Delay度量分王国军等:基于双向令牌的可扩展及可靠的群组成员管理943别为67.
11ms,67.
90ms,70.
24ms,70.
70ms,最大变化量仅为70.
7067.
11=3.
59ms.
另外,SM中Norm.
Num.
Msgs和Norm.
Size.
Msgs的最大值分别为每个代理每秒22.
38个信号消息和每个代理每秒280.
43字节;相应地,DM中的最大值分别为24.
21个信号消息和303.
19字节.
Signaling-Overhead度量的两条曲线中,随着网络规模的扩大,Signaling-Overhead具有减小的趋势.
因为每个逻辑环中用于传播成员改变/成员关系更新消息的令牌消息是所有信号消息中最重要的组成部分之一,可以计算出不同网络拓扑结构中令牌总数与有线结点总数的比例.
由于逻辑环的总数也就是令牌的总数会随着层次环结构的变化而变化,可以利用模拟开始时的初始值来估计该值.
因此,4种模拟的网络拓扑结构中该比例分别为2*(1+4+4*4)/(3*8*8),2*(1+6+6*6)/(3*12*12),2*(1+8+8*8)/(3*16*16),即21.
88%,19.
90%,19.
02%和18.
50%.
可以看到,当网络规模增大时,比例变小.
(2)图5表示,当网络规模和成员密度都固定不变时,层次环中的结点出错概率对该协议的性能有一定的影响.
随着结点出错概率从0.
0%增大到10.
0%,性能会适度地降低.
例如,SM中4种结点出错概率的Handoff-Delay度量分别为55.
72ms,59.
38ms,100.
19ms,109.
50ms,最大错误情况和无错误情况之间的最大变化量仅为109.
5055.
72=53.
78ms;DM中4种结点出错概率的Handoff-Delay度量分别为56.
51ms,55.
66ms,85.
77ms,103.
41ms,最大错误情况和无错误情况之间的最大变化量仅为103.
4156.
51=46.
90ms.
(3)在图4和图5中,可以观察到每个性能度量的一些趋势.
Join-Delay度量受到群组成员密度的影响.
如果成员分布稠密,例如DM,则对于MH来说很可能它一加入DP就能立即收到消息;相反,如果成员分布稀疏,例如SM,则当MH加入DP时,由于该DP可能不得不开始加入层次环而使MH必须等待一段时间才能接收消息.
这就是Join-Delay子图中两条曲线之间有明显间隙的原因.
Handoff-Delay度量对群组成员密度则不敏感,主要是因为该协议使用一种预留机制,该机制弱化了SM和DM间的差异.
Service-Speed度量主要受到网络规模的影响,随着网络规模的增大它只是略微地增大.
然而,它对结点出错概率和成员密度不敏感.
这是因为模拟中把层次结构的高度固定为4层,生成Member-Update消息和Membership-Update消息的超时间隔固定为1s.
而在实际环境中,这些参数根据不同应用的需要可能发生变化.
因此,这里只是给出了用于评估该协议的一个相对的Service-Speed度量.
Signaling-Overhead度量主要受到成员密度的影响,而对网络规模和结点出错概率不敏感.
主要原因是SM中群组大小和代理个数比相同网络规模的DM中群组大小和代理个数都小得多.
因此,SM中的信号消息个数与大小自然比DM中的要少,从而可以看到,Signaling-Overhead子图中的两条曲线之间有很明显的间隙.
7结束语本文的主要贡献是:(1)提出了一个适合于移动群组通信的新颖的层次环结构,它是逻辑环和逻辑树的结合模型,利用了逻辑环的简单性与逻辑树的可扩展性;(2)基于该模型提出了一种基于局部群组的成员信息传播算法,对于移动因特网环境中提供可扩展的、可靠的群组通信服务非常重要;(3)提出了一种能够满足及时性和准确性、基于邻居检测的拓扑结构维护算法,它是成员信息传播算法高效、可靠、一致运行的基础.
本文还论证了该协议具有与基于树的协议一样高的效率,因为只有自底向上的逻辑环序列才需要参与成员信息传播,而不是层次环结构中所有逻辑环.
作为将来的工作,我们将扩展该协议,处理具有恶意入侵行为的Byzantine类型的错误.
与本文基于崩溃类型这种错误类型相比,基于Byzantine错误类型的研究将更具挑战性.
References:[1]FasbenderA,ReichertF,GeulenE,HjelmJ,WierlemannT.
Anynetwork,anyterminal,anywhere.
IEEEPersonalCommunications,1999,6(2):2230.
[2]VarshneyU.
Multicastsupportinmobilecommerceapplications.
IEEEComputer,2002,35(2):115117.
[3]DuttaA,ChennikaraJM,ChenW,AltintasO,SchulzrinneH.
Multicastingstreamingmediatomobileusers.
IEEECommunicationsMagazine,2003,41(10):8189.
[4]DuttaA,SchulzrinneH.
MarconiNet:Overlaymobilecontentdistributionnetwork.
IEEECommunicationsMagazine,2004,42(2):6475.
944JournalofSoftware软件学报Vol.
19,No.
4,April2008[5]ShiML,XiangY.
Groupcommunication.
JournalofChinaInstituteofCommunications,1998,19(1):4553(inChinesewithEnglishabstract).
[6]PanJP,GuGQ.
Modelofgroupcommunicationsandprojectionfortransportprotocols.
JournalofSoftware,1998,9(8):574579(inChinesewithEnglishabstract).
[7]WangG,CaoJ,ChanKCC.
Afaulttolerantgroupcommunicationprotocolinlargescaleandhighlydynamicmobilenext-generationnetworks.
IEEETrans.
onComputers,2007,56(1):8094.
[8]DeeringS,CheritonDR.
MulticastroutingindatagraminternetworksandextendedLANs.
ACMTrans.
onComputerSystems,1990,8(2):85110.
[9]CastroM,DruschelP,KermarrecAM,RowstronAIT.
Scribe:Alarge-scaleanddecentralizedapplication-levelmulticastinfrastructure.
IEEEJournalonSelectedAreasinCommunications,2002,20(8):14891499.
[10]JinZQ,XiangXJ,ChenPP.
On-Demandbranchingmulticast.
JournalofSoftware,2003,14(3):553561(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/14/553.
htm[11]DolevD,MalkiD.
Thetransisapproachtohighavailabilityclustercommunication.
CommunicationsoftheACM,1996,39(4):6470.
[12]AnastasiG,BartoliA,SpadoniF.
Areliablemulticastprotocolfordistributedmobilesystems:Designandevaluation.
IEEETrans.
onParallelandDistributedSystems,2001,12(10):10091022.
[13]RajagopalanB,McKinleyPK.
Atoken-basedprotocolforreliable,orderedmulticastcommunication.
In:Proc.
ofthe8thSymp.
onReliableDistributedSystems.
Seattle:IEEE,1989.
8493.
http://ieeexplore.
ieee.
org/[14]BabaogluO,SchiperA.
Ongroupcommunicationinlarge-scaledistributedsystems.
In:Proc.
ofthe6thWorkshoponACMSIGOPSEuropeanWorkshop:MatchingOperatingSystemstoApplicationNeeds.
NewYork:ACMPress,1994.
1722.
http://portal.
acm.
org/[15]AmirY,StantonJ.
Thespreadwideareagroupcommunicationsystem.
TechnicalReport,CNDS98-4,Baltimore:TheJohnsHopkinsUniversity,1998.
[16]AnkerT,ChocklerGV,DolevD,KeidarI.
Scalablegroupmembershipservicesfornovelapplications.
In:MavronicolasM,MerrittM,ShavitN,eds.
Proc.
oftheNetworksinDistributedComputing.
Providence:AmericanMathematicalSociety,1998.
2342.
[17]KeidarI,SussmanJ,MarzulloK,DolevD.
Moshe:AgroupmembershipserviceforWANs.
ACMTrans.
onComputerSystems,2002,20(3):191238.
[18]ChenW,TouegS,KawazoeAguileraM.
Onthequalityofserviceoffailuredetectors.
IEEETrans.
onComputers,2002,51(5):561580.
[19]SunLM,LiaoY,WuZM.
Ahierarchyreliablemobilemulticastalgorithmbasedonmixedacknowledgementmechanism.
JournalofSoftware,2002,15(6):908914(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/15/908.
pdf[20]WuQ,WuJP,XuK,LiuY.
AsurveyoftheresearchonIPmulticastinmobileInternet.
JournalofSoftware,2003,14(7):13241337(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/14/1324.
htm[21]WangSL,HouYB,HuangJH,HuangZQ.
Dynamicrange-basedmobilemulticastprotocol.
ChineseJournalofComputers,2005,28(12):20962102(inChinesewithEnglishabstract).
[22]AcharyaA,BadrinathBR.
Aframeworkfordeliveringmulticastmessagesinnetworkswithmobilehosts.
ACM/KluwerMobileNetworksandApplications,1996,1(2):199219.
[23]BrownK,SinghS.
RelM:Reliablemulticastformobilenetworks.
ComputerCommunications,1998,21(16):13791400.
[24]BrewerEA,KatzRH,ChawatheY,GribbleSD,HodesT,NguyenG,StemmM,HendersonT,AmirE,BalakrishnanH,FoxA,PadmanabhanVN,SeshanS.
Anetworkarchitectureforheterogeneousmobilecomputing.
IEEEPersonalCommunications,1998,5(5):824.
[25]ZahariadisTB,VaxevanakisKG,TsantilasCP,ZervosNA,NikolaouNA.
Globalroaminginnext-generationnetworks.
IEEECommunicationsMagazine,2002,40(2):145151.
[26]GustafssonE,JonssonA.
Alwaysbestconnected.
IEEEWirelessCommunications,2003,10(1):4955.
[27]KellererW,VogelHJ.
Acommunicationgatewayforinfrastructure-independent4Gwirelessaccess.
IEEECommunicationsMagazine,2002,40(3):126131.
王国军等:基于双向令牌的可扩展及可靠的群组成员管理945[28]TamuraT,TakahashiT,MoritaT,OhtakiK,TakedaH.
IMT-2000corenetworknodesystems.
IEEEWirelessCommunications,2003,10(1):1521.
[29]BuddhikotMM,ChandranmenonG,HanS,LeeYW,MillerS,SalgarelliL.
DesignandimplementationofaWLAN/CDMA2000interworkingarchitecture.
IEEECommunicationsMagazine,2003,41(11):90100.
[30]PerkinsC.
IPmobilitysupport.
IETFRFC2002,1996.
[31]NS-2.
http://www.
isi.
edu/nsnam/ns/附中文参考文献:[5]史美林,向勇.
群组通信研究.
通信学报,1998,19(1):4553.
[6]潘建平,顾冠群.
群组通信模型及运输协议映射.
软件学报,1998,9(8):574579.
[10]金志权,项晓晶,陈佩佩.
按需分枝组播.
软件学报,2003,14(3):553561.
http://www.
jos.
org.
cn/1000-9825/14/553.
htm[19]孙利民,廖勇,吴志美.
基于混合应答机制的层次型可靠移动组播算法.
软件学报,2002,15(6):908914.
http://www.
jos.
org.
cn/1000-9825/15/908.
pdf[20]吴茜,吴建平,徐恪,刘莹.
移动Internet中的IP组播研究综述.
软件学报,2003,14(7):13241337.
http://www.
jos.
org.
cn/1000-9825/14/1324.
htm[21]王胜灵,侯义斌,黄建辉,黄樟钦.
基于动态范围的移动组播协议.
计算机学报,2005,28(12):20962102.
王国军(1970-),男,湖南长沙人,博士,教授,博士生导师,CCF高级会员,主要研究领域为移动计算,可信计算,软件工程.
贺建飚(1964-),男,博士生,副教授,主要研究领域为计算机网络,智能识别与智能信息处理,嵌入式系统,移动机器人.
吴敏(1963-),男,博士,教授,博士生导师,主要研究领域为过程控制,鲁棒控制,智能系统.
陈松乔(1940-),男,教授,博士生导师,CCF高级会员,主要研究领域为软件工程及应用,算法及网络优化.
周薇(1980-),女,博士生,主要研究领域为网络与信息安全,群组通信.
- 结点笔记本变无线路由器相关文档
- 思科笔记本变无线路由器
- 无线网络笔记本作无线路由器,将win7电脑变身WiFi热点,让手机、笔记本共享上网
- 连接Win7系统让笔记本电脑变身无线路由器
- 虚拟不用无线路由器,让电脑变身WIFI热点,与手机、笔记本共享上网
- 猎豹笔记本电脑瞬间一秒变无线路由器免费wifi来啦
- 设置Win7预装笔记本变身无线路由器设置教程
香港云服务器 1核 256M 19.9元/月 Mineserver Ltd
Mineserver(ASN142586|UK CompanyNumber 1351696)，已经成立一年半。主营香港日本机房的VPS、物理服务器业务。Telegram群组: @mineserver1 | Discord群组: https://discord.gg/MTB8ww9GEA7折循环优惠：JP30（JPCN2宣布产品可以使用）8折循环优惠：CMI20（仅1024M以上套餐可以使用）9折循...
无忧云-河南洛阳BGP，CEPH集群分布式存储，数据安全可靠，活动期间月付大优惠！
无忧云怎么样？无忧云服务器好不好？无忧云值不值得购买？无忧云是一家成立于2017年的老牌商家旗下的服务器销售品牌，现由深圳市云上无忧网络科技有限公司运营，是正规持证IDC/ISP/IRCS商家，主要销售国内、中国香港、国外服务器产品，线路有腾讯云国外线路、自营香港CN2线路等，都是中国大陆直连线路，非常适合免备案建站业务需求和各种负载较高的项目，同时国内服务器也有多个BGP以及高防节点...
陆零（￥25）云端专用的高性能、安全隔离的物理集群六折起
陆零网络是正规的IDC公司，我们采用优质硬件和网络，为客户提供高速、稳定的云计算服务。公司拥有一流的技术团队，提供7*24小时1对1售后服务，让您无后顾之忧。我们目前提供高防空间、云服务器、物理服务器，高防IP等众多产品，为您提供轻松上云、安全防护 为核心数据库、关键应用系统、高性能计算业务提供云端专用的高性能、安全隔离的物理集群。分钟级交付周期助你的企业获得实时的业务响应能力，助力核心业务飞速成...
笔记本变无线路由器为你推荐
如何查询域名备案号 金万维动态域名 骨干网 2014年感恩节 表格样式 dd444 流量计费 银盘服务 重庆服务器 linux服务器系统 服务器机柜 cc加速器 服务器操作系统 国外bt下载网站 北京公租房申请网站 snis-789 永久免费网络电话 网络测速电信 电信带宽测试 睿云网快速查分 更多