ѧ
JOURNAL OF SOFTWARE
1999 1 No.1 1999



Ƶ㲥зԵо*
񡡳ӡ¸
ժҪͬʱΪ㲥ûתԺͱ,VOD(video-on-demand)ڲƻ·㲥ʵʱʵǰ,ӦЩԵķ.
ؼʡת,,Ƶ㲥,Ƶ,ݷֲ.
ͼšTP391
Study of Servicing Policies in Video-on-Demand Server 
LIU Heng-zhuCHEN Xu-canCHEN Fu-jie 
AbstractThe round robin servicing policies and the proportional servicing policies which can simultaneously serve for the multiple subscribers of a VOD (video-on-demand) server are studied in this paper. And how to use these policies without violating the real-time playback rates of the subscribers of a VOD server is also proposed.
Key wordsRound robin servicing policy, proportional servicing policy, video-on-demand, video stream, data placement.
ͼšTP391
ٷչļ缼ѾʹСģVOD(video-on-demand)ϵͳΪ.1,2ĿǰһЩϵͳ,ЩϵͳΪ˱֤һĿĲ㲥,Ԥ˴豸Դ,ԽϸߵϵͳɱΪ.Ϊ˽VODϵͳĳɱ,ʹʵ,Ƶ紫䡢еȼһЩ֧żно,ʹԤ豸ԴرӦ.Ҫ,ĶԷʱŻо,ڱ֤ÿ·ϸ䲥Ҫٶȡͬʱ,Ϊĵ㲥ûṩVOD.ڶVODϵͳƵƽĻ,ͬʱΪ㲥ûתԣһѭУ3,ÿ·ȡݿһࣩ,˱ԣһѭ,ƵݿƵĲ֡ʳȣ,ڱ֤Ƶʵǰ,֤˱һͬʱΪûṩĲ.
ĵ1˱֤·ʵʱŵԼ;2תԺͱ,֤˱һ֧ಢķ;3ʵ,תԺͱԵܽ˱Ƚ.
1֤㲥ŵԼ
ҪоʱŻ,ڱ֤ÿϸ䲥Ҫٶȡͬʱ,Ϊĵ㲥ûṩVOD.Ϊ˽ϾȷرʾЩҪ,ƵΪn㲥ûṩ,Ӧn·㲥ΪS1,S2,...,Sn.ڵλMPEG(moving picture experts group)Ƶڿ,ƽԶϱλƵҪ,VODϵͳĿõúܶ.ۺʵ,ҪԺλ,Ҽٶѹ,ÿһGoP(group of picture)ͬ֡,ڴ洢ֲѡһGoPΪһ,ڴϴ洢,ȻһCTL4ݣconstant time lengthݷֲıͣھͬ֡ʵƵǰCTL洢ģ.óĽԼ޸,ͬʺڱλ.ѹĵλƵ,λMPEG,Bframe(1),Bframe(2),...,Bframe(n)ֱΪ·ÿݶӦ֡,ǰļ,ǶӦͬ,ͼΪBframe,λΪ֡/飻Sframe(1),Sframe(2),...,Sframe(n)ֱΪ·ÿƽÿ֡ĴСΪԺλ,ͨλֽڿͬһ·ÿƽÿ֡ĴСͬ,λΪֽ/֡Rpl(1),Rpl(2),...,Rpl(n)ֱΪ·Ĳ֡,λΪ֡/.Щһ·ƵѹƵʽͼȵĲͬͬ.ӺϿ,ƵͬʱΪn·ṩ,ʵͨʱɵ,ΪSiKiݺ,лΪSi+1ṩKi+1ݴ.K1,K2,...,Knһѭ.ظѭ,ֱn·ȫΪֹ.
һ·лһ·,ѴͷǰݿƵһ·ݿĿʼ,һʱС̵Ѱַʱ䣫תһʱ.ڴ,ǲһŵٿɴ洢1ݿ,ʱ,϶Զ1.,ڷ,ȡSiKiʱ.
(1) ⿪ϴ1õʱT1(i)ΪѰַʱ,תһõʱ,T1(i);
(2) Ki1ʱT2(i).
 
RdrΪݴ,λΪֽ/.
ΪSiȡKiʱΪT(i)=T1(i)T2(i),һѭõʱΪ
 
Ҫn·ϸǸԲʵҪȡ,һѭҪn·вߵSiKiõʱС,
(1) 
Ϊʽ1nk1,k2,...,kn,Ҫȷki.
2
2.1ת
תԣһѭÿ·ȡͬ,k1=k2=...=kn=k.
ʱ,ʽ1Ϊ
 
пƵ
(2) 
κSiһ鶼ʱڶ,
ʡ
Ϊk0,
 
nrmaxΪתֵ֧㲥û,
(3) 
ʽ3Կ,תԷͬʱΪ㲥ûṩĸܲǸû,ʱóûnrmaxͨԼӸĽԾͿɵ.Ϊ,ûһѭùһѭʱ,ûݳһѭܲ,,ԼЩûݴ,Ϊûṩ.
,һһѭһ·ݿĲ֡ʳȵķ,Ϊ.Ȼ,֤һͬʱΪûṩĲ.
2.2
ԣÿѭ,Ϊÿ·ȡݿĲ֡ʳ,
iʣ1,nݡkiRpl(i). 
cΪ,
k1=c.Rpl(1),k2=c.Rpl(2),...,kn=c.Rpl(n). 
ʱ,ʽ1
4 
Ϊ۵Ǻλ,ȻRpl(i)ʱ,Sframe(i)С;Rpl(i)Сʱ,Sframe(i),,Եó
(5) 
С
ʽ45ɵó
(6)
(7) 
npmaxΪתֵ֧㲥û, 
(8) 
ͬʱṩ㲥ûnnpmax,ʽ(6)c,˾Ϳһѭÿ·ݿ,ki=c.Rpl(i),i=1,2,...,n.kiɽһԻռҪ,Ա֤.
ϵ,һֱݴ϶ԿΪλ,ÿ֡,ΪƵ֡ĴС֮֡֡䶼Ǳ仯,Ҫ϶ȡĿСǿɱ.ڴ϶ݵĵλСǹ̶,ʱһCDL洢ֲ4ݣconstant data length,ô,һ̿ݲһպð֡,,߽̿֡ı߽粻ϵ,,ͬʱΪn㲥ûṩ,Ըݲλʣʽ1ݲ֡ʣԼʽ.ɵó
(9) 
DΪһ̿С,RbriΪi㲥ûҪĴλʣΪMPEG,ָʾ.ʱҪͬʱΪٵ㲥ûṩ,ɰ·.
һѭÿ·贫ݿ벥ŸҪĴλʳ. iʣ1,n,kiRbr(i),cΪ,ki=c.Rbri,i=1,2,...,n,Ǵʽ9
(10)
(11) 
Ӧת,
(12)
(13) 
2.3һͬʱΪûṩĲԵ֤
һԿͬʱṩ㲥ĸתͬʱṩķҪ,ʽԿ.ͬʱṩķΪnpmax,תͬʱṩķΪnrmax,
 
·ݲ֡ʣλʣܴʱ,ֵҲͽϴ.ǿ֤һͬʱΪûṩĲ,֤̼.
1. ڱ֤·ܰǸԵĲ֡Ҫȡǰ,֧·ݲ,һͬʱΪûṩĲԣ.
֤ʧһ,Rpl(1)Rpl(2)...Rpl(i).Եó
Rpl(1)=a2.Rpl(2)=...=ai.Rpl(i),a1=1. 
һַ,ڱ֤·ܰǸԲ֡Ҫȡǰ,ͬʱṩ㲥,Ϊn,ĳѭ,i·ݿΪki,Ϊòܱ֤·ǸԲ֡Ҫȡ,k1,k2,...,knӦ㷽̣1.
ʱ,ֻҪܹҵֱ벥֡Rpl(i) ȵkii=1,2,...,n,ʹ
k1=a2.k2=a3.k3=...=an.kna1=1Ҳʽ1,ұ,֤ˣÿѭÿ·ֱȡk1,k2,...,knݵı,ڱ֤·㲥֡ʶȡǰ,ҲͬʱΪn㲥ûṩ.Ҳ˵ˣڱ֤·㲥֡ʶȡǰ,Բκṩķ..Ҫ,Ѱk1,k2,...,kn.
á
ȻС
km1km1,ʹam1.km1=am2.km2,ʱɵó 
 
,ʱһѭ,m1m2ֱȡkm1km2,ʱʽ1ȻĻ,ô,·Ķȡͷһֱ,ܱ֤·㲥֡ʶȡ.֤,km1ߵkm1,ʹʽ1ܵƻ.
ʽ1ֶˣ
 
ǿԹº
 
Ϊ˱֤SiܰRpl(i),ҪȡһõʱСڻһܲŵʱ,
С
ԡ
f(k1,k2,...,kn)kiĵ,i=1,2,...,n.
Ϊk1,k2,...,knʽ1,,f(k1,k2,...,kn)0,
Ϊkm1km1,
f(k1,k2,...,km1,...,kn)f(k1,k2,...,km1,...,kn)0, 
k1,k2,...,km1,...,knʽ1.
,km1ӵkm1ʱ,ƻʽ1ĳ.
MpropʾЩһѭƵȡݿòŵ֡ʳɱЩƵļ.,Mprop={m1,m2}.ֻҪMpropn,˵һЩڼMprop.
á
MpropӦkm1,km2,...,ʹê,kmiͬʽ1,֤ϲͬ,Ȼ,Mprop=Mprop{m},һһֱȥ,ֱMprop=n.ʱ,k1=a2.k2=a3.k3=...=an.kn,k1,k2,...,knʽ1. 
3ʵ
۵ķ,ǹVODƽ̨,һЩʵ,ԷԽһЩģ,ܽ˳,ϵͳݴΪ100MB/s.ǶPALʽNTSCʽӰƬMPEG-1ѹ,ÿGoP10֡,I֡,P֡,B֡ݲΪIBBPBBPBBP,ÿGoPΪһ洢,õƲѹƵԷֱΪ
PALʽƵλΪ180000ֽ/s֡Ϊ25֡/s
I֡ƽÿ֡Ϊ21000ֽڡP֡ƽÿ֡Ϊ11000ֽ
B֡ƽÿ֡Ϊ3000֡ƽÿGoP72000ֽ
NTSCʽƵλΪ180000ֽ/s֡Ϊ30֡/s
I֡ƽÿ֡Ϊ18000ֽP֡ƽÿ֡Ϊ9500ֽ
B֡ƽÿ֡Ϊ2250ֽڡƽÿGoP60000ֽ
һѭ,㲥ʱ,תֶ֧485·Ĳ,֧582·Ĳ.ڲκӲԴǰ,ϵͳЧʴԼ20%,ʮֿɹ۵.
оõԤл
߽ܣ,1963,оԱ,ҪоΪֲʽý塣
,1966,Ů,ʦ,ҪоΪм.
¸,1935,,ʿʦ,ҪоΪģС洢,ֲʽý.
ͨѶϵˣ,ɳ 410073,ɳѧԺѧϵ617о
ߵλ񡡳ӡ¸ӡɳѧԺѧϵɳ410073
E-mail: hzhliu@nudt.edu.cn
ο
1Rangan P V, Vin H M, Ramanathan S. Designing a multiuser multimedia on-demand service. IEEE Communications, 1992,30(7):5665
2Sincoskie W D. System architecture for a large scale video on demand service. Computer Networks and ISDN System, 1991,22(2):155162
3Vin H M, Rngan P V. Designing a multi-user HDTV storage server. IEEE Journal on Selected Areas in Communi
cations, 1993,11(1):153164
4Edward Te Chang. Storage and retrieval of compressed video Dissertation]. Berkeley, California: University of California, 1996
1997-07-18յԭ,1998-01-23յ޸ĸ 
