面向时序图的季节突发性子图挖掘算法

时序图是一类边上带有时间戳信息的图.在时序图中,季节突发性子图是在多个时间周期内具有突发性特征的稠密子图,它可以用于社交网络中的活动发现和群体关系分析.然而以前大多数的研究主要集中在识别没有时间信息的网络中的稠密子图.为此,提出一种极大(ω,θ)-稠密子图模型对时序图中的季节突发性子图进行建模.所提模型表示时序图中在至少ω个长度不小于θ的时间段内快速累积密度的子图.为了挖掘出时序图中所有的极大(ω,θ)-稠密子图,将该类挖掘问题转化为一个混合的整数规划问题,包括挖掘最稠密子图和寻找突发值最大化时间段集合两个子问题,并给出有效的解决方案.进一步基于key-核模型和动态规划思想设计两种优化策略来提升算法的性能.实验表明所提模型能够真实地反映现实世界中具有季节突发性的行为模式.同时在5个真实时序网络中验证了所提算法的有效性、效率和可扩展性.

一种QoS有保障的Web服务分布式发现模型

如何动态地选择、绑定并调用最适合用户需求的Web服务备受研究领域的关注.提出了一种QoS有保障的Web服务分布式发现模型,具体研究基于QoS约束的服务发现问题,以及如何提高服务发现系统的可用性问题.研究Web服务的三维QoS模型并设计基于QoS约束的服务选择算法.提出集成服务选择算法的UDDI(universal description,discovery,andintegration)兼容扩展模型,并运用可扩展Kautz图和Bloom Filters理论,提出分布式UDDI的实现机制.该模型的原型系统在国家地质调查网格中得到应用,测试结果显示:扩展UDDI模型具有很高的查准率、响应率以及较好的负载均衡能力,而模型的分布式实现机制在保障查询性能的前提下,提高了发现系统的有效性和可用性.

一种基于QoS约束的Web服务选择和排序模型

提出了一种基于QoS约束的Web服务选择和排序模型,在研究Web服务的三维QoS模型的基础上设计基于QoS约束的服务选择模型,进一步研究服务效能的概念和量化方法并设计基于服务效能的排序模型.该模型的原型系统已经在国家地质调查网格中得到应用,结果表明模型能够有效保障用户对服务的需求,具有很高的查准率、响应率以及较好的负载均衡能力,提高了基于面向服务架构(SOA)的网络应用的可用性.

数据中心内Incast流量的网内聚合研究

MapReduce等分布式计算系统应用在数据中心内产生了严重的东西向流量,其中以incast和shuffle为代表的关联性流量占相当大的比重,进而严重影响到上层应用的性能.这促使研究者们考虑在这些关联性流量的网内传输阶段尽可能早而不是仅在流量的接收端进行流间数据聚合.首先以新型数据中心网络结构为背景讨论流间数据聚合的可行性和增益,为最大化该增益,为incast传输建立最小代价树模型.为解决该模型,提出了2种近似的incast树构造方法,其能够仅基于incast成员的位置和数据中心拓扑结构生成一个有效的incast树,进一步解决了incast树的动态和容错问题.最后,采用原型系统和大规模仿真的方法评估了incast流量的网内聚合方法,实验结果证明该方法能大幅降低incast流量造成的传输开销,能节约数据中心的网络资源.同时,提出的模型和解决方法也适用于其他类型的数据中心网络结构.

软件定义的云数据中心网络基础理论与关键技术

介绍了国家重点基础研究发展计划("973"计划)"软件定义的云数据中心网络基础理论与关键技术"项目的主要研究内容。指出了当前云数据中心网络所面临的挑战,并针对问题提出了利用软件定义网络的解决方案。对于软件定义的云数据中心网络未来发展需要研究的4个课题,即软件定义的云数据中心网络架构、云数据中心网络资源利用率优化、云数据中心网络多租户资源管理和云数据中心网络能耗协同控制,进行了论证和阐述。

面向云计算的数据中心网络拓扑研究

目前对数据中心网络拓扑的研究主要集中在如何提高结构性能上,却忽略了数据中心网络拓扑是否与云计算机制相适应的问题。针对该问题,建立了一种面向云计算的数据中心网络拓扑结构。研究了在具有该拓扑结构的数据中心网络上执行主流云计算机制的方法。分析了该拓扑结构的网络规模、网络直径等性能。仿真结果表明在具有该拓扑结构的数据中心网络上进行云计算是可行的。

开销敏感的多处理器最优节能实时调度算法

嵌入式多处理器系统的能耗问题变得日益重要,如何减少能耗同时满足实时约束成为多处理器系统节能实时调度中的一个重要问题.目前绝大多数研究基于关键速度降低处理器的频率以减少动态能耗,采用关闭处理器的方法减少静态能耗.虽然这种方法可以实现节能,但是不能保证最小化能耗.而现有最优的节能实时调度未考虑处理器状态切换的时间和能量开销,因此在切换开销不可忽视的实际平台中不再是最优的.文中针对具有独立动态电压频率调节和动态功耗管理功能的多处理器系统,考虑处理器切换开销,提出一种基于帧任务模型的最优节能实时调度算法.该算法根据关键速度来判断系统负载情况,确定具有最低能耗值的活跃处理器个数,然后根据状态切换开销来确定最优调度序列.该算法允许实时任务在处理器之间任意迁移,计算复杂度小,易于实现.数学分析证明了该算法的最优性.

一种基于移动基站的无线传感器网络数据收集方法

针对传统的无线传感器网络数据收集协议大多受制于发生在基站周围的热点问题,提出了一种使用移动基站的数据收集方法。将数据收集问题转化为支配集构造和旅行商问题,并提出了一种分布式的支配集构建算法,结合旅行商问题的近似算法生成基站的移动路线。仿真结果表明,所提出的方法减少了通信消耗,且能使负载均衡地分布。

数据中心网络高效数据汇聚传输算法

在数据中心中,类MapReduce的分布式计算系统在数据的混洗阶段产生巨大流量,令数据中心的东西向网络资源成为瓶颈.将这些高度相关的数据流在接收端进行聚合是分布式计算的通用处理方式,为了降低网络通信量并有效利用带宽,文中采用网内关联性流量的汇聚传输策略,将混洗和汇聚并行化,达到进一步降低东西向网络资源消耗、缩短混洗阶段延迟的目的.目前提出的IRS-based算法在适用场景上有一定局限性,为了解决这一问题,文中首先在以服务器为中心的代表结构BCube上建立incast最小树模型,分别提出MIB-based算法和MC-based算法,仅根据已知拓扑结构和发送节点编号即可快速生成一棵近似的最小代价incast树.MIB-based算法针对发送节点强关联的情况,使高层发送节点尽可能汇聚到已有的低层发送节点构建incast树;MC-based算法针对发送节点松散关联的情况,将节点进行最大程度上的聚合,通过增加最少的汇聚点完成incast树的构建.随后将上述两种算法结合起来进一步提出适用于各种场景的M2-based算法,通过推算时间复杂度证明该算法能够满足在线构建incast树的需求.最后,详细分析了M2-based算法对其他数据中心网络结构的适应性以及网内汇聚传输能够减少作业完成时间的原理.小规模实验结果表明,在不同网络规模下,M2-based比IRS-based节省了网络中约3%的数据量,整个作业在混洗和Reduce阶段的等待时间比不采用网内汇聚缩短约2/3;在不同传输节点规模下,M2-based比IRS-based节省了网络中约19%的数据量,整个作业在混洗和Reduce阶段的等待时间比不采用网内汇聚缩短约3/4.

基于副本复制和Bloom Filter的P2P概率路由算法

非结构化P2P网络资源定位过程中的查询延迟、查准率和查询成本难以同时被优化,为此,提出一种基于副本复制和Bloom Filter技术的P2P概率路由算法DCBF(data copying and Bloom Filter).DCBF基于有向随机网络,对资源对象进行少量的复制,并将各个副本随机路由给网络中的节点;接收副本的节点,以分布式衰减Bloom Filter向邻近节点传递副本的成员资格信息.理论分析和实验结果均表明,DCBF仅需复制少量的副本,通过以分布式衰减Bloom Filter传递副本的成员资格信息,使得网络中的绝大多数节点能够感知到副本的成员资格信息,从而使得各个节点能够以极低的查询代价,在较低的路由延迟范围内,高概率地将查询路由到目标节点.

空间信息网格的资源共享框架研究

为了支持用户在空间信息网格内对空间资源进行半自动化的定位、选择、使用以及集成操作,并促使形成空间资源的规模应用,提出了SIG资源共享框架的思想。首先论述了SIG资源共享策略及框架的关键组成部分,并介绍了空间信息网格UDD I中心的顶层设计。最后结合国家地质调查局的应用需求,验证了SIG资源共享框架在解决多源异构分布式数据动态集成和系统集成问题方面所起的关键作用。

基于教育云平台的数据科学导论翻转课堂设计

分析数据科学导论课堂教学中存在的学情复杂、知识结构繁杂以及传统教学手段成效不显著等问题,提出当前云教育平台的特点和优势以及翻转课堂在数据科学导论课程中的适用性,给出基于教育云平台的数据科学导论翻转课堂设计方案,阐述该课程设计方案的具体实施细节。

基于对等网络的全球信息网格服务发现机制研究

全球信息网格采用面向服务的架构提高系统的可重用性、柔性设计能力以及按需快速构建能力。这些优势的充分发挥需要快速及时发现各类可用的数据和服务。该文提出了两种扩展性很好的分布式服务发现机制:面向完全自治UDDI注册中心的非结构化UDDI对等网络和面向协同UDDI注册中心的结构化UDDI对等网络。

多核系统中基于动态松弛时间回收的节能实时调度算法

许多嵌入式实时任务的实际执行时间往往小于最坏情况执行时间,因此可以产生大量的动态松弛时间。针对时限等于周期的偶发任务集,提出一种基于动态松弛时间回收的多核系统节能实时调度算法DSREM。该算法基于最优在线调度算法LRE-TL,利用TL面内节能实时调度思想,在每个TL面的提前完成时刻实现动态松弛时间回收,降低后续偶发任务的执行频率,实现更多的节能。同时该算法还在每个TL面的初始时刻、偶发任务的释放时刻实现动态电压和频率调节,保证了偶发任务集最优可调度性。经过系统的数学分析和仿真,结果表明,DSREM算法不仅保证了偶发任务集的最优可调度性,而且当任务集总负载超过某一个值后,其节能效果始终优于现有方法,尤其随着总负载的增加,节能效果会更好。

ODBF:基于操作型衰落Bloom Filter的P2P网络弱状态路由算法

在P2P网络中,基于衰落Bloom Filter的弱状态路由算法试图将每条查询消息沿着成员资格信息量最强的方向传递,并最终以较低的传输代价和传输时延确保较高的查准率.研究发现衰落Bloom Filter在传递过程中存在严重的多径叠加和噪音问题,这直接导致查询消息以很高的概率沿着错误的方向传播,甚至会退化为泛洪路由算法.为解决这一挑战性难题,文中提出了基于操作型衰落Bloom Filter的弱状态路由算法ODBF(Operative Deca-ying Bloom Filter).ODBF通过分别保存对象的衰落Bloom Filter及源节点等信息,使得ODBF能够有效解决基于衰落Bloom Filter的路由信息在P2P网络中的多径叠加和信息回流问题,有效抑制噪音的影响,进而使得基于弱状态的路由能够以很高的概率沿着正确方向进行.

QoS可信的服务组合技术研究

现有基于QoS的服务组合方法通常假定QoS数据可信,然而这种假设很难保证,虚假的服务对于服务组合实现的影响常常是致命的。针对该问题,提出一种考虑QoS可信的服务组合方法。分析了QoS来源,建立了相应的系统结构,划分了信任级别,根据社会交往方式量化了直接经验和间接经验在可信判断中的作用,并以此构建QoS的计算模型,设计了相应的算法。最后,通过仿真实验,将考虑可信的服务组合方法与未考虑可信的传统组合方法进行了比较,前者体现出明显的优越性,从而表明提出的方法在性能和执行效率上是可行的。

IPSBSAR:一种基于熟人关系的增量式P2P搜索算法

P2P网络中参加资源共享的节点日益增多且呈海量趋势.如何在海量用户、海量资源的情况下,对所有满足查询语义的资源进行穷尽式搜索是一个颇具挑战性的问题.针对这一问题,提出了一种基于熟人关系的增量式P2P搜索算法IPSBSAR.算法基于人类社会的熟人关系,将人类社会关系中个体间交流与合作机制引入到P2P网络中,不但实现了P2P网络的增量式搜索,而且可以避免由非法拷贝而引起的版权问题.实验表明,IPSBSAR算法能够以较低的代价和较低的路由延迟,获得较高的增量式查询命中率;对同一语义进行穷尽式搜索时,能够搜索出满足查询语义的绝大多数资源,具有较高的效率.

一种构建超大规模数据中心的模块化网络结构

模块化数据中心网络的模块间互联结构和路由负责模块的有效组织以及不同模块服务器间的高效通信,使得如何设计具有高带宽、高容错和高可扩展能力的互联结构以支持大规模、超大规模数据中心的构建,成为模块化数据中心网络需要解决的首要问题.提出了一种构建超大规模模块化数据中心的模块间互联结构MDKautz.该结构通过模块内大量未被使用的交换机预留高速端口将模块以Kautz图互连,在无需额外增加任何高端交换设备的前提下,构造出具有高带宽、高容错和灵活可持续扩展性的超大规模数据中心网络.对MDKautz的构建方法、路由策略以及扩展方法进行了分析.数学分析和模拟实验结果证明了该新型网络结构具有良好的拓扑特性和通信性能,可有效支持数据中心高带宽、高容错的典型应用.

应用感知的数据中心网络多租户共享方法

在多租户数据中心,来自不同租户的应用程序共享并竞争使用网络资源.网络共享策略会对应用程序端到端的性能(如作业完成时间、吞吐量等)产生直接的影响.为了衡量租户应用程序的整体数据传输速率,本文引入进度(Progress)的指标.该指标被定义为租户应用程序在所有链路上经需求标准化后的最小带宽分配量,反映的是租户能够完成其数据传输的最慢速率.通过最大程度地提高租户进度,可以优化上层应用程序的执行时间等性能.先前的大多数工作都集中在实现网络共享的公平性、可预测性和效率之间的权衡,却忽略了提高租户的长期进度.本文观察发现应用程序放置于租户所租赁的不同虚拟机上会形成不同的带宽需求分布,进而影响后续带宽分配所能够获得的最优进度.通过理论分析我们证明了获得所有租户最优进度的关键在于最小化网络瓶颈链路上的带宽需求.基于此,本文提出应用感知的网络多租户共享方法,通过联合优化任务放置和带宽分配的过程,该方法最大化所有租户的进度,并在优势资源公平性限制下最大化网络利用率.实验结果证明,与目前的最新带宽分配方法相比,本文将租户整体进度提高了85.6%~107.7%,网络链路利用率提高了71.2%~112.4%.

MDCent:一种高可扩展、高吞吐量的模块间互连结构

近年来,提出的以服务器为中心的新型数据中心网络互连结构部分程度地解决了传统树型结构面临的性能瓶颈和可扩展性难题,同时出现了以集装箱为基本模块构建超大规模的数据中心.然而,如何设计模块之间的互连结构,确保数据中心网络具有高可扩展性、模块之间具有高带宽是一个非常具有挑战性的问题.以BCube为代表的新型数据中心网络,能够将数千台服务器互连在一个集装箱内,且对各种典型流量模式提供较高的带宽.提出了一种常量度数的模块之间的互连结构MDCent.MDCent基于BCube结构进行模块内服务器互连,利用模块内大量未被使用的上行端口,在各个模块保持常量度数的情况下,能够保证模块之间具有高可扩展性,同时模块之间具有较高的带宽.