流媒体帧分类存储模式下区间缓存算法的竞争分析
|
摘要
流媒体服务的瓶颈是磁盘带宽,而不同用户请求的数据长相关,区间缓存策略可以减少磁盘I/O。用户的交互请求改变了服务器的状态,影响缓存算法。针对交互引入了惰性替换的优化,并用竞争分析从理论上讨论了帧分类存储模式对缓存算法的影响。在最坏情况下,分类存储模式和顺序存储模式下缓存算法的磁盘I/O竞争比是常数。
Disk bandwidth is the bottleneck of streaming media service.The data of the same media are long-range dependent between different requests.Interval caching algorithm can reduce disk requests.But interactive requests affect status of server and the performance of caching algorithm.Lazy replacing strategy is introduced for interactions.Competitive analysis is applied to analyze the impacts of classified-video-frame storage mode.In the worst case,the competitive ratio of disk requests for cache algorithm is a constant between classified and sequential mode.
Disk bandwidth is the bottleneck of streaming media service.The data of the same media are long-range dependent between different requests.Interval caching algorithm can reduce disk requests.But interactive requests affect status of server and the performance of caching algorithm.Lazy replacing strategy is introduced for interactions.Competitive analysis is applied to analyze the impacts of classified-video-frame storage mode.In the worst case,the competitive ratio of disk requests for cache algorithm is a constant between classified and sequential mode.
引文
[1]Dan A,Sitaram D.Generalized interval caching policy for mixed interactive and long video workloads[C]//Electronic Imaging:Science&Technology.International Society for Optics and Photonics.1996:344-351.
[2]Ozden B,Rastogi R,Silberschatz A.Buffer replacement algorithms for multimedia storage systems[C]//Multimedia Computing and Systems,Proceedings of the Third IEEE International Conference on.1996:172-180.
[3]Hofmann M,Ng T S E,Guo K,et al.Caching techniques for streaming multimedia over the internet[C]//Soccer 2000 Draft.1999:128-136.
[4]Golubchik L,Lui J,Muntz R.Reducing I/O demand in video-on-demand storage servers[C]//Proceedings of the 1995 ACM SIGMETRICS.1995:25-36.
[5]Dan A,Sitaram D.Buffer management policy for an on-demand video server[C]//IBM Research Report,RC 19347,Yorktown Heights.1993:7-13.
[6]Dan A,Dias D M,Mukherjee R,et al.Buffering and caching in large-scale video servers[C]//Proc.of Compcon.1995:217-224.
[7]Andrews M,Munagala K.Online algorithms for caching multimedia streams[C]//Algorithms-ESA 2000.2000:64-75.
[8]Kim S,Das C R.An analytical model for interval caching in interactive video servers[J].Journal of network and computer applications,2007,30(1):384-413.
[9]Belady L A.A study of replacement algorithms for a virtual-storage computer[J].IBM systems journal,1966,5(2):78-101.
[10]Fiat A,Karlin A R.Randomized and multipointer paging with locality of reference[C]//Proceedings of the twenty-seventh annual ACM symposium on Theory of computing.1995:626-634.
[11]Liberatore V.Uniform multipaging reduces to paging[J].Information processing letters,1998,67(1):9-12.
[12]Young N.Competitive paging and dual-guided on-line weighted caching and matching algorithms[D].Princeton University,1991.
[13]Albers S.The influence of lookahead in competitive paging algorithms[C]//Algorithms—ESA'93.1993:1-12.
[14]Breslauer D.On competitive on-line paging with lookahead[J].Theoretical Computer Science,1998,209(1):365-375.
[15]王国权,李弋,叶德建.针对IPTV快进快退优化的媒体封装格式[J].计算机工程,2010,36(06):218-220.
[2]Ozden B,Rastogi R,Silberschatz A.Buffer replacement algorithms for multimedia storage systems[C]//Multimedia Computing and Systems,Proceedings of the Third IEEE International Conference on.1996:172-180.
[3]Hofmann M,Ng T S E,Guo K,et al.Caching techniques for streaming multimedia over the internet[C]//Soccer 2000 Draft.1999:128-136.
[4]Golubchik L,Lui J,Muntz R.Reducing I/O demand in video-on-demand storage servers[C]//Proceedings of the 1995 ACM SIGMETRICS.1995:25-36.
[5]Dan A,Sitaram D.Buffer management policy for an on-demand video server[C]//IBM Research Report,RC 19347,Yorktown Heights.1993:7-13.
[6]Dan A,Dias D M,Mukherjee R,et al.Buffering and caching in large-scale video servers[C]//Proc.of Compcon.1995:217-224.
[7]Andrews M,Munagala K.Online algorithms for caching multimedia streams[C]//Algorithms-ESA 2000.2000:64-75.
[8]Kim S,Das C R.An analytical model for interval caching in interactive video servers[J].Journal of network and computer applications,2007,30(1):384-413.
[9]Belady L A.A study of replacement algorithms for a virtual-storage computer[J].IBM systems journal,1966,5(2):78-101.
[10]Fiat A,Karlin A R.Randomized and multipointer paging with locality of reference[C]//Proceedings of the twenty-seventh annual ACM symposium on Theory of computing.1995:626-634.
[11]Liberatore V.Uniform multipaging reduces to paging[J].Information processing letters,1998,67(1):9-12.
[12]Young N.Competitive paging and dual-guided on-line weighted caching and matching algorithms[D].Princeton University,1991.
[13]Albers S.The influence of lookahead in competitive paging algorithms[C]//Algorithms—ESA'93.1993:1-12.
[14]Breslauer D.On competitive on-line paging with lookahead[J].Theoretical Computer Science,1998,209(1):365-375.
[15]王国权,李弋,叶德建.针对IPTV快进快退优化的媒体封装格式[J].计算机工程,2010,36(06):218-220.