一种新的基于流合并的调度策略  

A Novel Scheduling Strategy Based on Stream-Merging

作　　者：王浩[1] 钟玉琢[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《计算机学报》2001年第3期225-230,共6页Chinese Journal of Computers

基　　金：国家自然科学基金! (69973 0 2 5 )

摘　　要：分析了 Patching调度策略的特点 ,指出 Patching流满足了 70 %左右的用户请求而只消耗 8%左右的系统资源 .以此为依据 ,提出了 Patching First连续媒体播放调度策略 ,并基于该策略设计了 MPQL 和 MFPQ通道分配算法 .试验结果表明 ,与 MQL算法比较 ,这两种算法可以明显地缩短用户等待时间、减少用户请求撤消率、降低调度的不公平性 .通过试验结果分析 ,证明了 Patching First策略增强了 Patching流合并调度算法的优势 。The number of audio and video (continuous media) objects stored on web servers is increasing rapidly these years. Popular continuous media objects create “hot spots” of server and network load, and thereby significantly increase latency for client access. Patching, a recent stream merging schedule using multicast or broadcast techniques, can provide immediate service to each client request yet achieve considerable client stream sharing. Recent researches on Patching focus on how to achieve optimal stream merging schedule or how to deal with various network situations in Patching systems, but seldom consider the channel allocation stage in Patching systems. In this paper, the characteristics of Patching are investigated, the results show that Patching streams can satisfy about 70% of client requests with only about 8% of the system resources (i.e., server and network bandwidth), thus play the role more important than regular streams in stream merging systems. According to the investigation, the authors propose a novel scheduling strategy based on stream merging——Patching First, which first allocate channels for pending requests that can be served with Patching streams when system resources are available. Two specific channel allocation algorithms, MPQL (Maximum Patching Queue Length) and MFPQ (Maximum Fixed Patching Queue length), are designed for Patching First strategy. The algorithms are verified by simulation with various client request rates and different access modes. Simulation results are compared with Patching systems using traditional channel allocation algorithm, MQL. The comparison shows that MPQL and MFPQ algorithms can markedly increase the number of client requests served with Patching streams and significantly reduce the average waiting time, request defection and unfairness in various situations. Apparently, the proposed Patching First strategy using MPQL or MFPQ as channel allocation algorithm can leverage the advantage of Patching, thus can serve as a highly effective stream merging st

关 键 词：连续媒体 INTERNET 网络通道 Patching算法 流合并调度算法 

分 类 号：TP393.4[自动化与计算机技术—计算机应用技术]