计算机科学数学基础

0323233大规模连续媒体服务的缓存替换算法设计与实现[刊]/张潇//电子学报.—2003,31(5).—783～785(L)连续媒体的缓存设计是非常关键的问题,本文针对大规模连续媒体服务系统的特点,提出了 EA 缓存替换算法。该算法充分考虑了现有用户的请求接入用户的服务需求,提高了内存使用效率。我们的理论分析和实验模拟证明了它在性能上大大优于传统的缓存替换算法。参7     

一种基于自回归预测的缓存替换算法

由于目前的web缓存替换算法多侧重于对用户的历史访问进行参考,缺乏对用户请求的预测.主要利用自回归模型可用于预测的特性,在基于访问时间间隔(LRU)替换算法的基础之上提出了一种基于自回归模型预测的web缓存替换算法,并进一步的在opnet网络仿真中进行了仿真验证.仿真结果表明:基于自回归预测的缓存替换算法相对于传统的缓存替换算法更能提高代理缓存的对象命中率和字节命中率.     

变码率视频服务器间隔缓存的接纳策略和替换算法

本文提出了ROC(Resist-Overload Capability)缓存接纳策略和替换算法,解决了使用间隔缓存变码率视频服务器的缓存管理问题.确定性缓存接纳策略能提供确定的服务质量,却存在不适应交互应用和缓存利用率低的缺点;统计复用缓存接纳策略需要海量卷积运算,因此缺乏实用性;ROC缓存接纳策略通过简单运算,提供概率的缓存服务质量保证和较高的缓存利用率.仿真结果表明,在典型系统配置下,ROC缓存接纳策略和替换算法可以提高约25%的系统吞吐量;相对确定性缓存接纳策略和STP-L缓存替换算法,可以多服务约17%的视频流,平均缓存利用率也要高出约38%.     

基于异构网络的交互式流媒体缓存替换算法

针对交互式流媒体应用及异构网络对媒体类型要求多样性的特点,在代理服务器中引入转码技术,构建一种符合转码技术特点的新的缓存价值判断方法;通过新的缓存替换模型实现缓存替换。仿真结果表明,转码缓存算法能解决媒体类型多样性的要求,较之传统的缓存替换算法具有更高的缓存命中率和更低的启动延时率。     

基于多Markov链预测模型的Web缓存替换算法

为了提高web缓存的性能,提出了一种基于多Markov链预测模型的Web缓存替换算法PGDSF-AI.首先将Web中具有不同浏览特征的用户分为多类,为每一类用户建立类Markov链,进一步建立多Markov链预测模型.然后利用该模型对当前的用户请求预测,进而组成预测对象集.当缓存空间不足时,选取键值最小且不在预测对象集中的对象替换.通过估算对象的平均间隔时间,避免缓存大量保留长时间没有访问的对象.实验结果表明,提出的算法有较好的性能.     

并行计算框架Spark的自适应缓存管理策略

并行计算框架Spark缺乏有效缓存选择机制,不能自动识别并缓存高重用度数据;缓存替换算法采用LRU,度量方法不够细致,影响任务的执行效率.本文提出一种Spark框架自适应缓存管理策略（Self-Adaptive Cache Management,SACM）,包括缓存自动选择算法（Selection）、并行缓存清理算法（Parallel Cache Cleanup,PCC）和权重缓存替换算法（Lowest Weight Replacement,LWR）.其中,缓存自动选择算法通过分析任务的DAG（Directed Acyclic Graph）结构,识别重用的RDD并自动缓存.并行缓存清理算法异步清理无价值的RDD,提高集群内存利用率.权重替换算法通过权重值判定替换目标,避免重新计算复杂RDD产生的任务延时,保障资源瓶颈下的计算效率.实验表明：我们的策略提高了Spark的任务执行效率,并使内存资源得到有效利用.     

一种针对websearch应用的缓存替换算法

本文通过对websearch负载的分析,总结出负载访问模式的特点,在此基础上提出了一种新的缓存替换算法--ERDP-LRU.与传统的LRU算法的区别是它采用基于重用距离的放置策略.通过模拟实验和实际系统验证,在各种不同的典型负载和缓存大小下,ERDP-LRU的效果均好于其它替换算法.     

一种有资源适应性的transcoding代理缓存机制

在基于transcoding代理的流媒体服务系统中,CPU和网络是两种潜在的瓶颈资源.本文提出了一种有资源适应性的transcoding代理缓存机制,统一考虑CPU和网络的资源需求,以提高系统的服务能力.首先推导了多版本缓存策略下网络收益和CPU收益的计算方法.通过引入一个时变的影响因子 α (t),给出了缓存系统聚合资源收益的表达.在此基础上给出了单个对象的缓存价值函数,并设计了RAC替换算法.实验表明RAC具有较好的资源适应性和系统吞吐率.     

一种基于LRU算法改进的缓存方案研究与实现

LRU（最近最少使用）替换算法在单处理器结构的许多应用中被广泛使用。然而在多处理器结构中,传统LRU算法对降低共享缓存的缺失率并不是最优的。文中研究了基本的缓存块替换算法,在分析LRU算法的基础上,提出基于LRU算法及访问概率改进的缓存方案,综合考虑最近使用次数和访问频率来决定候选的替换块,增强了替换算法对多处理器的适应性。     

分布式多媒体存储系统中的全局缓存管理

多媒体存储系统必须同时支持连续媒体和非连续媒体的访问.由于连续媒体的实时要求,系统必须为访问连续媒体保留大量的磁盘带宽,并且持续很长的时间,这使其他类型文件的访问性能严重下降.本文根据连续媒体的访问特性,提出了一个分布式多媒体存储系统的协同缓存策略GLNU,充分利用系统中其他结点上可用的内存资源,提高缓存的利用率,以减少连续媒体的磁盘I/O,从而提高其他媒体的访问性能.仿真试验表明GLNU在各种不同的参数下,均优于现有的缓存策略,是一种适合分布式多媒体存储系统的缓存策略.     

Dynamic Probabilistic Caching Algorithm with Content Priorities for Content‐Centric Networks

This paper presents a caching algorithm that offers better reconstructed data quality to the requesters than a probabilistic caching scheme while maintaining comparable network performance. It decides whether an incoming data packet must be cached based on the dynamic caching probability, which is adjusted according to the priorities of content carried by the data packet, the uncertainty of content popularities, and the records of cache events in the router. The adaptation of caching probability depends on the priorities of content, the multiplication factor adaptation, and the addition factor adaptation. The multiplication factor adaptation is computed from an instantaneous cache‐hit ratio, whereas the addition factor adaptation relies on a multiplication factor, popularities of requested contents, a cache‐hit ratio, and a cache‐miss ratio. We evaluate the performance of the caching algorithm by comparing it with previous caching schemes in network simulation. The simulation results indicate that our proposed caching algorithm surpasses previous schemes in terms of data quality and is comparable in terms of network performance.     

Design of in-network caching scheme in CCN based on grey relational analysis

In-network caching is one of the most important issues in content centric networking （CCN）, which may extremely influence the performance of the caching system. Although much work has been done for in-network caching scheme design in CCN, most of them have not addressed the multiple network attribute parameters jointly during caching algorithm design. Hence, to fill this gap, a new in-network caching based on grey relational analysis （GRA） is proposed. The authors firstly define two newly metric parameters named request influence degree （RID） and cache replacement rate, respectively. The RID indicates the importance of one node along the content delivery path from the view of the interest packets arriving The cache replacement rate is used to denote the caching load of the node. Then combining hops a request traveling from the users and the node traffic, four network attribute parameters are considered during the in-network caching algorithm design. Based on these four network parameters, a GRA based in-network caching algorithm is proposed, which can significantly improve the performance of CCN. Finally, extensive simulation based on ndnSIM is demonstrated that the GRA-based caching scheme can achieve the lower load in the source server and the less average hops than the existing the betweeness （Betw） scheme and the ALWAYS scheme.     

命名数据网络中基于内容请求相关性的协作缓存算法

针对命名数据网络(Named Data Networking, NDN)存储空间的有效利用和应答内容的高效缓存问题,该文采用差异化缓存的方式,提出一种依据内容请求序列相关性的协作缓存算法。在内容请求中,预先发送对于后续相关数据单元的并行预测请求,增大内容请求的就近响应概率;缓存决策时,提出联合空间存储位置与缓存驻留时间的2维差异化缓存策略。根据内容活跃度的变化趋势,空间维度上逐跳推进内容存储位置,时间维度上动态调整内容缓存时间,以渐进式的方式将真正流行的请求内容推送至网络边缘存储。该算法减小了内容请求时延和缓存冗余,提高了缓存命中率,仿真结果验证了其有效性。     

基于媒体用户访问行为偏好模型的代理缓存算法

目前,代理缓存技术广泛应用于改善流媒体传输的服务质量.文章从实际用户日志文件的分析出发,利用发现的用户浏览流媒体对象时的行为分布模型,提出了一种新的视频流媒体缓存算法.仿真结果证明,该算法可以通过记录很少的用户访问信息获取较高的性能表现.     

Neighbor caching in multi-hop wireless ad hoc networks

We propose a neighbor caching strategy to overcome the overhead of multi-hop wireless communications. Neighbor caching makes a node able to expand its caching storage instantaneously by storing its data in the storage of idle neighbors. We also present the ranking based prediction that selects the most appropriate neighbor which data can be stored in. The ranking based prediction is an adaptive algorithm that adjusts the frequency of neighbor caching and makes neighbor caching flexible according to the idleness of nodes.     

A Novel Dynamic and Scalable Caching Algorithm of Proxy Server for Multimedia Objects

This paper presents a novel dynamic and scalable caching algorithm of proxy server with a finite storage size for multimedia objects. Among the multimedia such as text, image, audio and video, video is a dominant component in terms of the performance of proxy server due to its traffic characteristics. For the fast caching process, caching sequences for videos are obtained to decrease both the buffer size and the required bandwidth and saved into metafiles in advance. Then, we present a novel caching and replacing algorithms for multimedia objects based on the metafiles. Finally, experimental results are provided to show the superior performance of the proposed algorithm.     

雾无线接入网中基于内容流行度和信息新鲜度的缓存更新策略

将边缘缓存技术引入雾无线接入网,可以有效减少内容传输的冗余。然而,现有缓存策略很少考虑已缓存内容的动态特性。该文提出一种基于内容流行度和信息新鲜度的缓存更新算法,该算法充分考虑用户的移动性以及内容流行度的时空动态性,并引入信息年龄(AoI)实现内容的动态更新。首先,所提出算法根据用户的历史位置信息,使用双向长短期记忆网络(Bi-LSTM)预测下一时间段用户位置;其次,根据预测得到的用户位置,结合用户的偏好模型得到各位置区的内容流行度,进而在雾接入点进行内容缓存。然后,针对已缓存内容的信息年龄要求,结合内容流行度分布,通过动态设置缓存更新窗口以实现高时效、低时延的内容缓存。仿真结果表明,所提算法可以有效地提高内容缓存命中率,在保障信息的时效性的同时最大限度地减小缓存内容的平均服务时延。     

Cooperative caching algorithm of UAV and user in UAV-assisted cellular network

Aiming at the problem of mass data content transmission and limited wireless backhaul resource of UAV in UAV-assisted cellular network,a cooperative caching algorithm for cache-enabled UAV and user was proposed.By deploying caches on UAV and user device,the popular content requested by user was cached and delivered,which alleviated the backhaul resource and energy consumption of UAV,reduced the traffic load and user delay.A joint optimization problem of UAV and user caching was established with the goal of minimizing user content acquisition delay,and decomposed into UAV caching sub-problem and user caching sub-problem,which were solved based on alternating direction method of multiplier and global greedy algorithm respectively.The iterative way was used to obtain convergent optimization result,and the cooperative caching of UAV and user was realized.Simulation results show that the proposed algorithm can effectively reduce user content acquisition delay and improve system performance.     

一种内容中心网络中的热区控制及内容调度缓存算法

针对内容中心网络中同质化缓存造成的节点负载不均和存储资源无法有效利用的问题,提出一种热区控制及内容调度缓存算法.在内容请求时,根据节点介数与节点访问度综合判断节点热度,筛选出负载过重节点;缓存决策时,以流行度为依据将内容调度至空闲邻居节点,并设置生命期控制机制,从而达到分散请求、消除热区的目的.仿真结果表明该算法减少了请求时延与路由跳数,在提高缓存命中率的同时,有效改善了负载在节点上分布的均衡性.     

Caching algorithms for broadcasting and multicasting in disruption tolerant networks

In delay and disruption tolerant networks, the contacts among nodes are intermittent. Because of the importance of data access, providing efficient data access is the ultimate aim of analyzing and exploiting disruption tolerant networks. Caching is widely proved to be able to improve data access performance. In this paper, we consider caching schemes for broadcasting and multicasting to improve the performance of data access. First, we propose a caching algorithm for broadcasting, which selects the community central nodes as relays from both network structure perspective and social network perspective. Then, we accommodate the caching algorithm for multicasting by considering the data query pattern. Extensive trace‐driven simulations are conducted to investigate the essential difference between the caching algorithms for broadcasting and multicasting and evaluate the performance of these algorithms. Copyright © 2016 John Wiley & Sons, Ltd.