基于缓存映射项重用距离的闪存地址映射方法

经典的闪存转换层(flash translation layer, FTL)地址映射方法DFTL(demand-based FTL)将全局映射信息放在闪存中,仅缓存最近最常使用的映射信息,解决了页级映射策略中映射信息较大和缓存容量有限的矛盾.但是,DFTL没有充分利用负载的空间局部性特点提高缓存命中率;在缓存失效时频繁的脏映射项换出也会导致大量的映射页写操作;此外,它未能优化垃圾回收过程中有效页迁移导致的写放大问题.针对上述不足,提出一种基于缓存映射项重用距离的地址映射方法IRR-FTL(inter-reference recency-based FTL),通过设置映射页缓存槽,充分挖掘负载空间局部性;基于缓存映射项重用距离实现负载自适应的写缓存映射表冷热分区,并分别采取不同的管理策略,减少映射页写操作;此外,实现基于重用距离的冷热数据分离存储,提高垃圾回收效率.通过采用多种负载对该方法进行验证实验,实验结果表明IRR-FTL相比DFTL缓存命中率提高29.1%,平均响应时间降低了27.3%,擦除次数降低了10.7%.     

基于HBase的多维索引查询机制的优化

键值存储旨在从非常大的数据量中提取值,同时具有高可用性、容错性和可伸缩性,因此提供了非常需要的基础设施来支持基于位置的服务（LBS）。然而,多维数据上的复杂查询不能有效地处理,因为键值存储不提供访问多个属性的方法。针对键值存储HBase不能有效处理多维数据的问题,提出了一个统一的索引框架——New-grid,使键值存储HBase支持多维查询。在改进的P-grid覆盖网络中,组织了一组节点,提供了高效的数据分布、容错和多维数据的查询处理。为了进行索引,使用基于Hilbert空间填充曲线来保存数据的局部性,从而有效地管理键值存储中的多维数据。同时使用HBase底层存储管理数据,并提出了一种范围查询和K最近邻查询的算法,以消除维护单独索引表的开销。在Amazon EC2上使用4、8和16个普通节点的集群进行了广泛的实验。实验结果表明,New-grid的性能相比MD-Hbase以及MapReduce更优。     

基于连续缓存和二级缓存的DFTL改进算法

DFTL(demand-based FTL)是一种根据负载访问特点动态加载映射项到缓存中的知名FTL(flash translation layer)算法,但是它没有考虑到请求的空间局部性,而且缓存中的一个映射项剔除就可能会导致翻译页的更新,缓存中映射项的频繁剔除又会导致额外的擦除操作.在DFTL的基础上,提出了SDFTL(sequential/second cache DFTL)算法.SDFTL新设置连续缓存和二级缓存,连续缓存通过预取映射信息,利用请求的空间局部性,提高了FTL对连续负载的处理性能;二级缓存通过暂存从一级缓存中剔除的、发生更新的映射项,并采取批量更新策略回写到闪存,减少了闪存的翻译页写回次数和擦除次数.利用实际负载做的实验结果显示,SDFTL相比DFTL缓存命中率平均提高41.57%,擦除次数平均减少23.08%,响应时间平均减少17.74%.     

一种高效的P2P环境中的窗口查询算法

随着多媒体以及P2P网络的发展,针对高维数据基于属性的窗口查询已经成为一个重要研究课题.提出了一种在超级节点P2P网络中有效解决高维数据的窗口查询算法,在每个单独的网络节点上,数据通过一种降维算法映射到一维空间,在超级节点上,构造数据的统计信息表以及构造网络查询树,算法在每次查询时,按照查询树的规则来访问整个网络,并利用统计信息剪枝网络中的节点查询,避免网络的泛洪.实验中使用了不同的数据集来评测算法的查询效率,结果表明该算法具有很高的查询效率.     

基于伸展树的文件数据缓存管理策略研究

针对企业内部网络存储,研究并提出了一种基于伸展树的缓存管理策略,以对网络缓存空间进行组织和管理。在内部网络存储缓存链的基础上,引入并改进了伸展树结构和操作,将改进后的伸展树作为缓存节点数据组织和管理的索引结构,分析并设计了基于伸展树的文件数据缓存管理策略。实验结果表明,基于伸展树算法的缓存管理策略提高了缓存空间利用率和用户访问数据的效率,有较好的实时性。     

信息中心网络中协作的内容缓存和请求路由算法

信息中心网络与传统IP网络区别的重要特点是在路由器节点配备缓存设施,将热门内容推送到更靠近用户的网络边缘,从而降低用户获取内容的时延。为了提高缓存空间的利用率,避免内容在相邻节点的冗余放置,本文提出了一种分层协作的内容放置和请求路由算法,在层次结构的接入网络中,依据内容的访问热度仅在层次结构的其中一层放置内容副本以减少内容的冗余备份;此外,通过建立二元标签组记录内容的放置信息,用于动态引导请求的转发;仿真结果表明,与现有的缓存放置算法相比,分层协作的内容缓存和请求路由机制,提高了网络存储内容的多样性,并降低了用户访问内容的时延。     

命名数据网络中一种基于节点分类的数据存储策略

缓存是命名数据网络(named data networking, NDN)有别于传统网络最突出的特性之一,NDN中默认所有节点都具有缓存所有经过数据的功能.这种“处处缓存”策略导致网内大量冗余数据的产生,使网内缓存被严重浪费.针对上述问题,首次提出了一种基于节点分类(based on node classification, BNC)的数据存储策略.基于节点位置的不同,将数据返回客户端所经过的节点分为“边缘”类节点与“核心”类节点.当数据经过“核心”类节点时,通过权衡该类节点的位置与数据在不同节点的流行度分布,将数据存储在对其他节点最有利的节点中;当数据经过“边缘”类节点时,通过该数据流行度来选择最有利于客户端的位置.仿真结果表明,提出的策略将有效提高数据命中率,减少数据请求时延和距离.     

基于贪心优化策略的网格排布算法

针对由存储带宽和数据访问速度导致的复杂数据集绘制性能低下等问题,提出了一种基于贪心优化策略的三角形排布算法,通过对绘制数据集进行重排以改善数据的空间局部性和时间局部性。该算法首先将顶点分为三类,根据改进的代价函数选择代价度量最小的顶点作为活动顶点;然后绘制（即输出）其所有未绘制的邻接三角形,并将相邻顶点压入缓存,算法迭代执行直到所有顶点的邻接三角形都绘制完成,得到重新排列后的三角形序列。实验结果表明,该算法不仅具备较高的顶点缓存命中率,还提高了渲染速度,减少了排序的时间,有效地解决了图形处理器的处理速度不断提升而数据访问速度严重滞后的问题。     

一种基于四叉树的空间数据缓存策略

提出了以四叉树作为缓存数据结构,结合广泛应用的LRU和LFU算法,给出了一种高效的缓存策略—基于四叉树的空间数据缓存策略,并详细描述了缓存框架和缓存策略。提出的缓存策略充分考虑了空间数据访问所具有的时间局部性和空间局部性,兼有LRU和LFU算法的优点。最后设计了空间数据请求模型,通过实验对算法的有效性进行了验证。     

基于概念漂移学习的ICN自适应缓存策略

针对如何提高信息中心网络的网内缓存性能,提出了一种基于概念漂移学习（concept drift learning,简称CDL）的自适应缓存策略.考虑到节点数据和内容数据的相互感知对缓存性能的影响,将节点和内容的状态数据流作为网络资源,对提取的多维状态属性数据和缓存匹配数据进行分析挖掘,利用学习到的状态属性与缓存匹配之间的函数映射关系,即概念,对未来时期内的节点与内容间的匹配关系进行预测.为提高匹配算法的准确度,在学习过程中,提出了一种基于信息熵的概念漂移识别算法,当根据状态属性的信息熵变识别出漂移后,利用提出的基于概念重现的缓存算法,重新定义函数映射关系.仿真实验结果表明,该策略与CEE,LCD,prob和OPP策略相比,降低了网络运行成本,提高了用户体验质量.     

无线Mesh网络中节点分级协作缓冲机制研究

在无线Mesh中,由于每个节点缓冲的数据量不同,可能会造成某些节点的缓冲区利用率低,某些节点因为缓冲任务繁重而进行频繁的数据置换操作,从而造成节点存储空间使用不均衡,降低数据缓冲的效率。提出了一种基于节点分级管理的协作缓冲算法,该算法为网络中的每个节点在网络中构造一个分布式缓冲区域,利用该缓冲区域来替代节点本身的缓冲区,通过合理地利用每个节点的存储空间,增加单个节点的数据缓冲能力。理论分析和实验结果表明,该算法可以有效提高数据访问命中率,减少缓冲区数据的置换操作,降低节点的能量消耗。     

基于存储优化的多模式串匹配算法

多模式串匹配算法是网络内容过滤系统的核心技术之一.自动机的存储空间大小和Cache性能是影响多模式串匹配算法速度的关键因素.随着模式串规模的扩大,自动机的巨大存储开销导致现有的串匹配算法性能大幅度下降.从压缩存储空间以提高Cache命中率的思想出发,提出了一种对经典SBOM算法的优化策略,它用Suffix Tree代替SBOM算法中的Factor Oracle结构,同时用剪枝的方法将Suffix Tree降低为近似线性的空间复杂度,然后用双数组Trie表示之,以压缩存储空间.与SBOM算法相比,改进算法不仅能够有效地节省存储空间,而且显著地提高了串匹配的速度,非常适合于在线高速匹配的应用环境.     

基于用户偏好的协作内容缓存策略

随着无线网络不断增长的业务需求,蜂窝架构频谱资源受限,回程容量将成为系统瓶颈。为了缓解这种瓶颈,考虑一种特殊的异构蜂窝网络,结合缓存节点的部署、用户位置分布、用户对请求内容的偏好以及缓存节点有限的存储空间,对内容存储及用户关联联合优化问题进行建模分析。将目标函数建模为请求时延的最小化,简单证明该问题是NP-hard的,并设计了基于改进KM(Kuhn-Munkres)的内容放置策略。最后,通过实验比较了该算法与其他基准方案的性能。     

一种节约内存的中文多模式匹配算法

AC及其改进算法基于有限状态自动机,随着中文模式串数目增加,完全Hash表和状态表矩阵存储方式会导致存储空间快速膨胀,状态转移函数计算量大,Cache命中率下降,算法的时空性能急剧下降。提出以邻接链表方式存储有限状态自动机,并将状态"0"的链表转化为线性表,以提高算法的时空效率。在此基础上,设计了一种适合中文的多模式匹配算法,该算法所需存储空间仅为完全Hash表方式的10%,约为状态表矩阵方式的20%。     

移动机会网络中接触时间感知的协作缓存策略

数据访问效率一直都是移动机会网络研究中的一个备受关注的问题.协作缓存技术经常被用来提高网络数据访问效率,但是该类网络中节点的强自主移动性和有限的接触时间使得传统的缓存技术无法得到有效应用.首先提出一个新的度量节点在协作缓存中重要程度的指标,即节点重要度.基于此指标,利用贪心算法选择初始缓存节点;利用缓存节点相遇的机会,进行缓存数据的主动再分配.为了适应节点间有限的接触时间,提出了数据分片策略,并使用随机线性网络编码方法对分片进行编码,以解决数据恢复时的赠券收集问题.此外为每个节点确定了缓存边界来限制缓存数据量,从而合理利用缓存空间.最后,通过实验验证了提出的缓存协议能够有效地提高数据访问效率.     

BW-VSDS:大容量、可扩展、高性能和高可靠性的网络虚拟存储系统

设计并实现了一个大容量、可扩展、高性能和高可靠性的网络虚拟存储系--BW-VSDS.和其他网络存储系统对比,它有如下的特点:1)采用带内元数据管理和带外数据访问的虚拟存储管理架构,存储管理更灵活,并且系统扩展性更好;2)在单个节点内部的多个虚拟卷、多个虚拟池和多个网络存储设备上利用存储虚拟化技术重构得到面向多种存储应用的网络虚拟存储设备,实现了3层的层次化存储虚拟化模型,对内共享存储设备的容量和带宽,对外提供不同属性的虚拟磁盘;3)采用写时按需分配策略提高了存储空间的利用率,使用数据块重组提高了I/O读写性能;4)使用设备链表和位图实现了层叠式虚拟快照,支持增量快照、写时拷贝和写时重定向机制,实现源卷和快照卷的数据共享;5)提出结合带外存储虚拟化管理的后端集中的带外冗余管理结构,数据读写直接访问存储节点,冗余管理节点在磁盘上以日志方式缓存从存储节点镜像写的数据,然后在后台进行RAID5冗余计算,提高了活跃数据的可靠性,减轻了冗余计算对写性能的影响.     

节点与链路协同映射的生存性虚拟光网络映射算法

针对弹性光网络中单链路故障问题,提出一种基于匈牙利算法求解链路映射方案的节点与链路协同映射保护算法CMST-HA。将虚拟网络请求的节点与链路分别划分为主动类型与被动类型,把主动类型节点映射至邻接链路频谱资源丰富且邻接节点计算资源充足的物理节点上,在主动链路时使用匈牙利算法求解出最小映射开销方案并完成映射,确定被动节点的映射位置,利用KSP算法为被动链路选择映射路径,在此基础上为虚拟网络请求的最小生成树链路提供备份路径。仿真结果表明,与RVNM、CMST算法相比,CMST-HA算法不仅能够降低虚拟网络请求阻塞率,而且可增加物理网络收益。     

基于随机游走的语义重叠社区发现算法

语义社会网络是由信息节点及社会关系构成的一类新型复杂网络,因此语义社会网络重叠社区发现是传统社区发现研究的新方向.针对这一问题,提出基于随机游走的语义社会网络重叠社区发现算法,该算法首先以LDA(latent Dirichlet allocation)算法为基础建立语义空间,实现节点语义信息到语义空间的量化映射;其次,以语义空间中节点信息熵作为节点语义信息比重,以节点的度分布比率作为节点关系比重,建立节点语义影响力模型及语义社会网络的加权邻接矩阵;再次,以语义影响力模型和加权邻接矩阵为参数,提出一种改进的语义社会网络重叠社区发现的随机游走策略,并提出可度量语义社区发现结果的语义模块度模型;最后,通过实验分析,验证了所提出的算法及语义模块度模型的有效性和可行性.     

eXist数据库结构连接算法的改进和实现

为了进一步提高eXist数据库的查询效率,针对数据库现有的数据存储特点和查询策略,提出一种快速定位的结构连接算法FL-Stack。算法采用栈缓存已遍历过的但仍可能与尚未遍历的后代结点匹配的祖先结点,并对能预先判断不可能满足结构连接匹配的祖先或后代结点,提出相应方法实现快速定位,以批量跳过这类结点。与现有算法必须逐个扫描祖先后代结点序列相比,这种快速定位的结构连接算法避免了逐个扫描带来的多次重复无意义的比较,可大大提高结构连接效率。     

Web合作缓存置换算法的改进与实现

在LRU算法的基础上,提出一种改进的Web合作缓存置换算法。该算法针对不同大小的文档采取不同的存储策略,如增加小文档在缓存组中的存储数量,以提高其本地缓存的命中率,减少大文档在缓存组中存储的数量,以节约整个缓存组的空间。仿真实验结果表明该算法能够获得较好的性能。