Bloom Filter技术在弹性重叠网络中的应用研究

来源 :北京大学 | 被引量 : 0次 | 上传用户:yaohaochang
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
如今,随着计算机和互联网的蓬勃发展,给人类的生活带来了革命性的变化。而不论是计算机基础应用还是互联网,表示和查找已经成为大多数计算机应用的核心。BloomFilter是一种空间效率和时间效率均很高的随机数据结构,它可以简洁地表示一个数据集合,并能有效的支持集合元素的哈希查找操作。自1970年提出以来,被广泛应用到各种计算机系统之中,以表示庞大数据集及提高查找效率。 但是随着网络和计算机的发展,现有的各种BloomFilter都存在着这样或那样的不足。因此,本文的研究目标为设计一种高性能的BlomFilter算法,它应该满足如下三个要求:1)适应P2P等动态应用场景;2)支持大规模数据集合;3)常数查找时间。 本文首先对现有的一个动态应用场景适应性较好的BloomFilter:DynamicBloomFilter(DBF)算法进行了改进,分析了改进之后的性能,在确定其依然无法满足我们的需求之后,重新设计了一种新颖的BloomFilter算法。彻底利用矩阵技术对BloomFilter进行了重新的设计,即矩阵型BloomFilter:MBF。并对其算法的性能,包括误称率和平均时间复杂度进行了分析,证明其具有算法实现简单,时间复杂度低等优点。 接下来,本文详细描述了在CNG12005--RON弹性重叠网络上的管理系统的技术细节及实现方案。着重从智能节点概况、配置管理、节点性能监测、支撑管理、记账管理、链路监测这几个方面对系统进行了详细的描述和介绍,分析了在设计一个能够完成对RON弹性重叠网络实现“可管、可控、可运营”的目标,这样一个管控系统所需要考虑的各种因素。 最后,对所设计的新型BloomFilter算法:MBF,其实际应用情况进行了分析,阐述了其应用在RON弹性重叠网络管理系统上的可行性,并对相关部分进行了具体的设计及实现。
其他文献
近年来,大数据以数据量大、数据类型多样、产生与处理速度要求快、价值高的4V特性成为工业界和学术界的研究热点。由于传统软件系统难以在可接受的时间范围内处理大数据,工业界
在网络中存在两类信息资源。一类是利用传统的搜索引擎,可通过爬行超链接获取并索引的信息资源,将其称为可见网或表层网。与此对应,网络中还存在另一类信息资源,这类资源对基于链
在工业化社会向信息化社会前进过程中,复杂系统建模与仿真技术与高性能计算技术相结合,成为继理论研究和实验研究后的第三种重要方法。复杂系统研究的主流之一是多领域统一建模
获取操作系统运行时的实时信息,监测并记录系统运行时的状态是十分重要的。一方面,这些信息是系统性能监测和调优(tuning)、内核剖面(profiling)、应用程序执行追踪(tracing)以
在开发大规模分布式应用的过程中,如何有效地集成和共享已有的软件和本地计算,提高系统的开发效率,降低系统的开发成本一直是分布式系统研究和关注的重点问题。为了解决这一问题
我国税务机关的个体税收征管,传统上是由税务人员主观评定纳税额。存在人为参与因素多、规范不细,不利于具体问题具体分析,规范的变化缓慢,不能适应市场经济发展的需要,严重制约着
Internet高速发展使人们越来越依赖于通过互联网获取各种信息,CNNIC的最新报告显示互联网第一入口是即时通信的比例是39.7%,看新闻则以20%居第二。新闻信息本身具有数量大、增长
随着经济活动的不断发展,人们对道路交通系统的依赖越来越强,交通拥堵(trafficcongestion)成为世界各大城市面临的严峻问题。近年来智能交通系统(IntelligentTrafficSystem,ITS)
细分曲面作为一种几何外形表示方法,具有交互直观、整体光滑、任意拓扑等优势,在影视特效、三维游戏和数字媒体内容创作等行业中得到了广泛的应用。细分曲面是递归定义的,这与当
如今,软件系统的复杂度越来越大,而对软件系统的可靠性、时效性的要求也越来越高。如何在保证软件产品质量的前提下有效控制产品的开发和维护成本,是企业提升市场竞争力的关键。