基于覆盖网的分布式交互应用及其关键技术研究

发布时间：2018-03-06 02:21

本文选题：分布式交互应用　切入点：覆盖网　出处：《中国矿业大学(北京)》2016年博士论文　论文类型：学位论文

【摘要】：人类社会是群居社会,交流和协作是人类社会活动的基础。网络和计算机等相关技术的持续高速发展把人类带入了信息化时代。信息化时代的计算机应用从单用户模式向多用户协作模式发展,不再局限于单机独立的系统,而是以分布式的形式开展。当把Internet看成一个整体,人们与眼前计算机的交互应用就变成基于Internet的人与人交互应用,即分布式交互应用(Distributed Interactive Applications,DIA)。信息化时代基于交流和协作的DIA能够提高工作效率,促进生产力的发展,改善人们的工作和生活方式。覆盖网络(Overlay Network)由于具有可扩展性、灵活性、健壮性和易于部署等特点而备受关注并取得了广泛的发展。Overlay Network技术是一种与特定网络层次、特定技术无关的网络构造的方法,通过在原有物理网络的基础上,根据实际的需求来构造一个虚拟的逻辑网络,在保证与原有网络最大限度地兼容的情况下,支持原网络很难或者不可能提供的功能和服务。因此,可以较为灵活地解决现有网络体系结构中存在的问题。本文基于DIA的研究现状和特点,从网络体系结构入手,研究可扩展的分布式交互应用,将Overlay Network的思想融入到DIA的研究中,利用Overlay Network的可扩展性和适应性等特性,将DIA基于Overlay Network之上进行研究,有利于克服DIA在体系结构和机制方面的不足,从而实现DIA的大规模部署和应用。因此,本文针对DIA的可扩展性、低延时、高带宽、动态性、多对多、交互性等需求,提出了基于Overlay Network的DIA的概念及网络体系结构(Overlay-Network based Distributed Interactive Applications,ODIA),并对其关键技术进行了研究。第一,对基于覆盖网的DIA的网络体系结构进行了深入研究。在分析传统的DIA网络体系结构的基础上,提出了基于覆盖网的DIA的概念以及网络体系结构模型ODIA。从功能上将ODIA划分为用户DIA应用层、ODIA覆盖层和物理网络层三个层次,并定义了各层的功能及相互关系。详细描述了基于覆盖网的DIA覆盖层的构造,提出了DIA服务域层——DIA核心层的分层覆盖网结构模型。该模型的构造结合DIA的特点和现有物理网络的特点,以现有物理网络的自治域为单位综合考虑自治域间的延时和领域相关性,将网络聚类划分成K个DIA服务域,每个DIA服务域都包含一个或多个自治域,并在服务域内征用和部署一定的代理节点,由代理节点构造生成服务域层网络,为服务域内的DIA提供支撑。同时在每个DIA服务域内都选取出一个或多个核心代理节点,由核心代理构造生成DIA核心层网络,为服务域间的DIA提供支持。然后,在构造出的ODIA分层模型下确定了需要解决的关键问题。第二,研究了基于覆盖网的DIA网络体系结构模型ODIA的覆盖层构造问题。ODIA覆盖层的主要任务是生成并维护支撑分布式交互应用的Overlay Network拓扑结构,同时为其上层DIA应用层提供实现分布式交互应用所需的功能,如路由和交互性控制等,是整个DIA网络体系结构模型的核心。ODIA覆盖层的构造包括五个子问题,即DIA服务域的划分问题DSDD,DIA代理节点的征用和部署问题DPRP,DIA服务域层的构造问题DSCP,DIA核心代理节点选取问题DKPS,以及DIA核心层的构造问题。首先,针对DIA服务域的划分问题DSDD,以现有物理网络的自治域为单位综合考虑自治域间的延时和领域相关性,把自治域间地理位置邻近和领域相关性大的划分到一个DIA服务域中,对DSDD问题进行形式化描述和建模,并研究了求解DSDD问题的改进遗传算法DSDD_IGA。其次,可扩展的DIA应首先能够实现自治域内的分布式交互应用,由于在自治域内的DIA网络中,存在许多类型的服务器,因此以自治域为单位将这些服务器有选择的征用起来作为DIA代理节点,征用节点作为DIA代理的费用远远小于部署DIA代理的代价,只有当征用的代理节点无法支撑自治域内的DIA时,才部署一定的DIA代理节点,即DIA代理节点的征用和部署问题DPRP。然后,对DPRP问题进行了形式化描述和建模,研究了求解DPRP问题的改进粒子群算法DPRP_IPSO,该算法能够在满足网络性能约束的条件下,使得部署代价尽量小。再次,为了支撑服务域内的DIA应用,针对DIA服务域层的构造问题进行研究;为了构造拓扑匹配的DIA服务域层网络,采用了GNP网络坐标系统、Hilbert空间填充曲线、Skip Lists等技术,并对DIA服务域层的构造问题进行建模,研究了求解DIA服务域层的构造问题的差分进化算法DE_DSCP。第四,针对DIA核心代理节点选取问题DKPS进行建模,提出求解DKPS问题的免疫算法DKPS_IA,使得核心代理节点的选取满足最大网络带宽、最小网络延时。最后,为了高效地支撑服务域间的DIA应用,针对DIA核心层的构造问题,提出基于改进超立方体Hypercube对DIA核心层进行构造,并对该问题进行建模,达到DIA核心层网络的总时延最小、物理链路重用度最小、链路最小带宽的最大和总链路带宽最大的优化目标。第三,研究了基于覆盖网的DIA路由问题。基于本文提出的DIA网络体系结构模型ODIA,结合DIA路由问题的特点和性质,对DIA的路由问题分别从域内路由和域间路由两个方面进行了研究。首先,针对DIA服务域内的路由问题,由于DIA路由的多对多、实时性等特点,为每一个需要发送数据的DIA节点都以它为根构造一棵数据分发树,费用开销太大,而所有需要发送数据的DIA节点都基于单棵共享树进行数据分发树,又会造成流量集中,DIA延时无法保障。因此,这里采用多棵共享树来分发DIA数据。基于多共享树研究了DIA服务域内静态路由问题SMSTR和动态路由问题DMSTR,提出了求解SMSTR问题的禁忌遗传算法SMSTR_TSGA,研究了动态路由问题DMSTR的节点加入和退出算法。其次,针对可扩展的DIA应用,为了高效地支撑DIA服务域间的分布式交互应用,必须研究DIA的域间路由问题。域间路由是基于DIA核心层之上的,而DIA核心层是由所有DIA服务域内选出核心代理节点基于Hypercube构造出的一个覆盖层,因此需要结合Hypercube研究DIA的域间路由问题。对于DIA服务域间的静态路由问题SHMR,提出了基于局部簇的超立方体组播路由算法HMR_LC;对于DIA服务域间的动态路由问题DHMR,研究了DHMR的节点加入和退出算法。第四,研究了基于覆盖网的DIA交互性问题。在DIA中,发生在两个不同节点上的事件如何排序,如何判断某个事件当前是否可以提交处理是非常关键的。由于网络传输时延的异构,不同DIA节点接收到事件的顺序是不一样的,一个DIA节点显然不能把事件的接收顺序作为处理顺序,也不能将已接收到的最小时间戳的事件作为当前需处理的事件,因为它无法判断是否有更小时间戳事件仍在网上传输,还未接收到。本文根据DIA交互性问题的特点和性质,在基于Overlay Network的DIA网络体系结构模型的基础上,分层次地解决DIA交互性问题。对于DIA服务域内的交互性问题,在时钟同步的前提下,为了能够确定事件的可处理时刻,有效的解决了DIA服务域内不同节点上事件处理顺序不一致造成的交互性问题,提出了基于周期采样和事件序列号的DIA服务域内交互性控制方法ICM_SE。对于DIA服务域间的交互性问题,由于节点地理上分布的广泛性,节点间时钟无法精确同步。即时钟同步不能很好地适用于大规模广域网环境,但DIA服务域间的各节点的时钟步进速率几乎没有差异。因此,针对DIA服务域间的交互性问题,为了能够把发生在其他DIA服务域内的事件时间戳转化为对应的本地DIA服务域内的时间,本文提出了基于时钟关系矩阵的时间转化方法,进而提出DIA服务域间的交互性控制方法ICM_CRM。模拟仿真表明,本文提出的交互性控制方法具有开销低,可扩展性好,能有效减少DIA中不一致现象的发生。最后,针对在网环境下DIA网络的拥塞和数据包的丢失无法完全避免,会造成事件消息不一定都能在用户可接受的响应时间内到达接收节点的问题,研究了DIA交互性控制的修复机制。第五,研究了基于覆盖网的DIA机制。在基于覆盖网的DIA网络体系结构的基础上,研究了基于覆盖网的DIA机制,主要包括DIA会话和节点管理机制中的DIA会话的注册机制、DIA节点的加入机制、DIA节点的退出机制,以及基于周期采样和事件序列号的DIA服务域内交互性机制和基于时钟关系矩阵的DIA服务域间交互性机制。同时,利用形式化工具Petri网对基于覆盖网的DIA机制进行了形式化描述,基于Petri网可达图对DIA机制的模型进行了正确性和完备性验证。最后,分析了论文中存在的不足。基于现有的工作,针对需要进一步研究的问题提出了一些设想,并对基于覆盖网的DIA的发展前景做出了展望。
[Abstract]:......
【学位授予单位】：中国矿业大学(北京)
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP393.02

【参考文献】