Network-aware partial caching for Internet streaming media

The delivery of multimedia over the Internet is affected by adverse network conditions such as high packet loss rate and long delay. This paper aims at mitigating such effects by leveraging client-side caching proxies. We present a novel cache architecture and associated cache management algorithms that turn edge caches into accelerators of streaming media delivery. This architecture allows partial caching of media objects and joint delivery from caches and origin servers. Most importantly, the caching algorithms are both network-aware and stream-aware; they take into account the popularity of streaming media objects, their bit rate requirements, and the available bandwidth between clients and servers. Using Internet bandwidth models derived from proxy cache logs and measured over real Internet paths, we have conducted extensive simulations to evaluate the performance of various cache management algorithms. Our experiments demonstrate that network-aware caching algorithms can significantly reduce startup delay and improve stream quality. Our experiments also show that partial caching is particularly effective when bandwidth variability is not very high.Shudong Jin: Corespondence to This research was supported in part by NSF (awards ANI-9986397, ANI-0095988, ANI-0205294 and EJA-0202067) and by IBM. Part of this work was done while the first author was at IBM Research in 2001.     

基于动态内容流行度的NDN缓存决策和替换策略研究

命名数据网络(NDN)中的路由器节点具有缓存能力,这就极大地提高了网络中的数据发送与检索效率。然而,由于路由器的缓存能力是有限的,设计有效的缓存策略仍然是一项紧迫的任务。为了解决这个问题,提出了一种动态内容流行度缓存决策和替换策略(DPDR)。DPDR综合考虑内容流行度和缓存能力,利用一个和式增加、积式减少(AIMD)的算法动态调节流行度阈值,并将超过流行度阈值的内容存入缓存空间;同时提出了一个缓存替换算法,综合考虑了缓存空间中内容的流行度和内容最后被访问时间等因素,将替换值最小的内容移出内容缓存。大量仿真结果显示,与其他算法相比,本文所提的算法能够有效提高缓存命中率,缩短平均命中距离和网络吞吐量。     

一种新的基于代理缓存的流媒体分送策略

提出了一种新的带缓存的补丁调度策略,有效地将代理缓存与服务器调度技术结合起来,采用基于缓存窗口自适应伸缩的缓存分配方案,实现了流媒体对象在代理服务器中缓存的数据段数与其流行度成正比的原则。理论分析及实验结果表明,该策略有效地降低了服务器及骨干网络带宽资源的消耗,对于客户请求到达速率的变化具有非常好的适应性。     

自适应的分段代理缓存传输策略

结合现有的代理缓存策略和传输方案,针对现有的网络条件,提出了一种自适应的分段方法,解决了已有方法对于流媒体对象流行性的变化和用户访问模式的不确定缺乏自身调整能力的缺欠,和一种优化的传输方案,采用了单播和多播相结合, 主动预取和补丁传输相结合的方法,对于缩短启动延时、提高字节命中率以及节省骨干网带宽等方面取得了较明显的效果.     

基于补丁算法的流媒体代理缓存的研究与实现

对流媒体代理缓存和流调度技术进行了分析与研究，结合代理缓存和补丁算法的优点，设计与实现了一种基于补丁算法的流媒体代理缓存的高效方法。分析和实验研究表明，该方法能进一步减少对骨干网络带宽资源和原始服务器的磁盘I/O资源的占用，提高用户访问请求的响应速度。     

Frequency-based cache management policies for collaborative and non-collaborative topologies of segment based video caching proxies

This paper examines a novel cache management policy applied to non-collaborative and collaborative environments of more than one proxy server that serve homogeneous or even heterogeneous client requests for video streaming over the Internet. This cache management policy, which we call LRLFU because of a combination between an LRU and an LFU policy, is capable of capturing the changing popularities of the various videos by attaching a caching value to every video according to how recently and how frequently the video was requested, and decides to cache the most ‘valuable’ videos. Our event-driven simulations have shown that LRLFU when applied to a simple non-collaborative topology of proxies and compared with previous work in this area (1) improve the byte-hit ratio (BHR), (2) significantly reduce the fraction of user requests with delayed starts and (3) require less CPU overhead. Furthermore, our simulation results have shown that the collaborative hierarchical tree topology of proxies that we examine achieves a much higher BHR when using the same overall cache capacity with the simple topology and in general provides better performance characteristics.This work was conducted while A. Satsiou was a MSc student in the Department of Electronic and Computer Engineering Technical University of Crete.     

一种P2P流媒体系统中的缓存替换算法

针对视频节目受欢迎程度不同的特性,提出一种P2P流媒体系统中的缓存替换算法,通过将系统中的全部视频片段分类,为其赋予不同的优先级,并周期性地更新该值,同时考虑视频片段被访问次数和最近被访问的情况,使得被替换出存储空间的片段更加合理。实验表明,该算法能提高缓存命中率及系统的启动延时,性能较优。     

流媒体代理缓存技术研究

随着流媒体技术在互联网上的广泛应用,原有用于加速Web内容分发的代理缓存技术也被应用于流媒体内容分发领域。然而,由于流媒体对象的一些独特特点,需要在传统Web缓存技术的基础上提出适用于流媒体对象的缓存技术。本文分析了基于代理缓存的流媒体分发中的关键问题和技术挑战,对现有的各种流媒体缓存方案进行了综述、分类和比较,最后对流媒体代理缓存的未来发展方向进行了展望。     

A stepwise optimization algorithm of clustered streaming media servers

The optimization of Clustered Streaming Media Servers (CSMS), which aims at using as few hardware resources and as cost-effective as possible, while providing satisfactory performance and QoS, has a great impact on the practicability and efficiency of CSMS. Based on the analysis and formulization of critical performance factors of CSMS and the relationship among the performance, QoS, and the costs in CSMS, a stepwise optimization algorithm is developed to solve the optimization problem efficiently. The algorithm is based on an approach that models the optimization problem into a directed acyclic graph and then addresses the complex optimization problem step by step. The algorithm applies a divide and conquer model that not only reduces the complexity of the optimization problem, but also accelerates the optimization process. Progressive information is collected in the process and used in solving the problem. Furthermore, a simulation system of CSMS is necessary for the optimization algorithm to generate the accurate information produced in the entire streaming service process. Thus, we designed and implemented such a simulation system based on the theoretical performance model of CSMS and the parameters measured in practical CSMS testbed. Finally, a case study of the optimization problem is given to demonstrate the process of the algorithm, and an appropriate plan for designing practical CSMS system is illustrated.     

种基于Sever和Proxy流媒体流行性的Caching策略

It is expected that by 2003, continuous media will account for more than 50% of the data available on origin servers. This will provoke a significant change in Internet workload, due to the high bandwidth requirements and the long-lived nature of digital video, streaming server loads and network bandwidths are proving to be major limiting factors. Aiming at the characteristic of broadband network in a residential area, we propose a popularitybased on server-proxy caching strategy for streaming media. According to a streaming media popularity on streaming server and proxy, this strategy caches the content of this streaming media partially or completely, and plays an important role in decreasing server load, reducing the traffic from streaming server to proxy, and improving the startup latency of the client.     

一种基于Sever和Proxy流媒体流行性的Caching策略

1 概述经过了2000、2001两年的社区宽带网建设的高速发展后,摆在中国ISP们面前的任务是如何在已建成的宽带网上开展增值服务,许多ISP尝试在宽带网上开展流媒体(Streaming Media)服务,如视频点播VOD(Video On-Demand)系统。然而,流媒体对网络带宽和实时性的要求使得流服务器必须能够进行端对端(End-to-End)的拥塞控制和质量调整,由于     

命名数据网中基于流行度的网内缓存替换策略

针对命名数据网络中如何高效地对节点内的数据进行替换的问题,对节点内已经缓存的数据块,根据被请求的频率、请求时间间隔,准确判断数据块在当前时间的流行度,提出了一种基于流行度的替换策略Po-Rep。从命中节点返回的数据决定要存储在相应节点时,把节点内流行度低的数据进行剔除替换。该策略使节点的内容保持最大价值,满足后续的用户请求。仿真结果表明,该策略有效提高了网内节点存储的命中率,降低了服务器的负载,提高了网络的整体性能。     

基于时间间隔的P2P流媒体直播系统缓存算法

针对基于分片传输机制的P2P流媒体直播系统客户端缓存问题,为提高节点间请求数据分片的命中率和避免数据分片大量冗余,提出一种依赖邻居节点请求量的节点缓存替换算法.该算法将分片在节点的缓存时间进行等间隔划分,利用马尔可夫链转移概率矩阵计算理论,预测分片在下一时刻的缓存价值.并将该算法和传统算法FIFO及LRU算法进行了对比实验,实验结果表明,在同等条件下,该算法相较于传统算法能更好地提高数据的命中率.     

Parameters of cache systems based on a Zipf-like distribution

The object of this paper is to explain a system of Internet traffic caching. The task is to create an analytical model of a cache system linking its size with other parameters by boundary conditions. A definition of a dynamic cache model is introduced. The parameters of a cache system are calculated using the Zipf's first law and Zipf-like distribution. The correspondence between size of a cache system and aggregated bandwidth of external links is derived.     

一种基于质量命中率的流媒体代理缓存布局方法

在网络边缘对流媒体的热点片段进行缓存,是流媒体分发研究领域的一个热点。异构环境下不同种类的接入用户对流媒体的播放质量具有不同的要求。为了使代理缓存最大限度地满足全体用户对收看质量的请求,本文首先提出了质量命中率的定义来衡量代理缓存对提高用户观看质量的贡献,然后提出了一种基于质量命中率的流媒体代理缓存布局方法。仿真结果表明,该布局方法不仅能使全体用户的平均质量命中率最大,而且有效地利用了代理缓存的磁盘空间,显著降低了片段的播放时延。     

Design and analysis of a variable bit rate caching algorithm for continuous media data

In this paper, the problem of caching continuous media data in a (main) memory and disk caching system is addressed. Caching schemes can significantly reduce the load on the network as well as on the servers, also the retrieval of documents from the cache requires short response time. In interval-level caching algorithms, an interval of data between two adjacent streams is the basic caching entity. In this paper, we design a novel algorithm, referred to as variable bit rate caching (VBRC) algorithm, which belongs to the interval-level caching algorithms. The proposed VBRC algorithm can be used in the system for memory caching or disk caching. VBRC can handle variable retrieval bandwidth as well as constant retrieval bandwidth . In designing the VBRC algorithm, we propose the strategies of reducing the number of switching operation, which will probably cause discontinuity of retrieving data. Also, we propose a just-in-time scheme for resource allocation in our VBRC algorithm and show that the caching performance in comparison with the reservation scheme adopted in the resource-based caching (RBC) algorithm is significantly improved. Our simulation study compares the recent and most popular generalized interval caching, RBC, and VBRC, on several influencing factors such as cache space size, cache I/O bandwidth, request arrival rate, and percentage of requests for large documents, with respect to the byte hit ratio and the number of switching operations. The simulation result confirms our analysis.

改进的最小效用流媒体代理缓存替换算法

在SCU-K算法的基础上,提出了基于流行度和将来访问次数的最小效用替换算法（SCU-PFUT）。此外算法还考虑了流媒体文件的字节有效性和文件块大小的因素,使得替换出内存的数据块更加合理。不但避免LRU和LFU算法中出现的媒体文件被连续替换的问题,相对于LRU、LFU和SCU-2,其在缓存命中率、字节命中率和空间利用率都得到了提升。     

基于项目流行度的协同过滤TopN推荐算法

为了提高推荐系统挖掘用户感兴趣的冷门项目的能力,提出一种改进的协同过滤推荐算法.在传统算法基础上考虑项目流行度的影响,将其作为权重因子引入到相似性计算和推荐过程中,以提高用户相似性计算的可靠性和冷门项目在最终的项目推荐过程中的影响力.典型数据集上的对比实验表明,该算法能够在保持甚至提高推荐准确度的前提下,有效挖掘到用户感兴趣的冷门项目.     

基于DASH的混合控制码率算法

针对平滑流（SF）算法在带宽预测时存在的"毛刺"现象以及仅依靠带宽预测而没有缓存区控制所导致的频繁播放停滞的问题,提出一种动态自适应混合控制码率算法。首先,通过使用标准差来代替原SF算法中波动参数的计算,消除了预测带宽存在的"毛刺"现象;其次,针对原SF算法存在没有考虑缓存区状态所带来的频繁播放停滞问题以及传统缓存区控制算法存在分级困难的问题,引入一种基于缓存区容量的新型缓存区控制策略;最后,将改进SF算法与新型缓存区控制策略相结合形成混合算法来选择视频码率。实验结果表明,混合算法不但消除了原SF算法在带宽预测中存在的毛刺现象,而且弥补了仅依靠单一算法选择码率的不足,使得所选码率视频既降低了播放停滞频率（恶劣网络环境下效果明显,降低43%左右）又符合实际网络情况,提高了用户的观看体验。     

基于频繁序列挖掘的文件系统缓存算法设计

传统缓存算法存在命中率低、交换率高等问题,且现有缓存算法在分布式大数据存储系统中并不适用,为此提出了一种基于频繁序列挖掘的自适应缓存策略。该方法使用数据挖掘算法挖掘历史访问窗口内的频繁序列,将频繁序列模糊合并后构建匹配模式集合以供查询。当新的访问来临时,将固定访问长度内的子序列与匹配模式集合进行匹配,然后根据匹配结果预取数据,同时结合修改后的S4LRU(4-segmented least recently used)数据结构进行缓存数据换出。在公开的大数据处理trace集上进行了仿真实验,实验结果表明,在不同的缓存大小下,提出算法与现有典型缓存算法相比,平均命中率提高了0.327倍,平均交换率降低了0.33倍,同时具有低开销和高时效的特点。此结果表明,该方法较传统替换算法而言是一个更为有效的缓存策略。