о뷢չ
JOURNAL OF COMPUTER RESEARCH
AND DEVELOPMENT
1999 36 12 Vol.36 No.12 1999



ֲʽýϵͳеͬо

ժҪȸڽ̴LOTOSʽ淶ԵĻͨԴͳLOTOSлʱ䣬ʱӣӦ﷨ʽ.ͨԷֲʽµĶýͬϵͳķûʱLOTOS˻ͬϸĶý崽ͬ㷨.ͬʱһʵϵͳһ˻ʱLOTOSԷֲ¶ýϢͬʵеӦã봫ͳ˱Ƚ.
ؼʡֲʽýϵͳͬLOTOS
ͼšTP37
RESEARCH ON THE SYNCHRONIZATION PROBLEM IN
DISTRIBUTED MULTIMEDIA SYSTEMS
JIN Tao 
(College of Computer Science and Technology, Wuhan University, Wuhan 430072)
(College of Computer Science and Technology, National Engineering Research Center for Multimedia Software,
The Open Research Laboratory for Multimedia Software under the Department of Education, Wuhan University, Wuhan 430072)
AbstractLOTOS is a formal specification language ,designed for the precise description of the open distributed system. LOTOS is based on process algebra model. Firstly, this paper gives some basic concepts of LOTOS. By introducing two time operators, the traditional LOTOS is extended and time-based LOTOS's syntax and formal semantics are described. Then, it performs a systematic analysis of the synchronization problem in the distributed multimedia system. Applying the time-based LOTOS, the specification of the basic synchronization algorithm and the lip-synchronization algorithm is proposed. Also, an example of the lip-synchronization system is illustrated and compared with the traditional synchronization design methods.
Key wordsdistributed multimedia system, synchronization, LOTOS
1ǰ
봫ͳֲʽϵͳȣֲʽýϵͳ3Ҫص㣺ԡṩϸķƺʵʱͬ.ָڷֲʽýϵͳҪһֳýstreamĽƣ봫ͳķֲʽͨŽֵ֧һRPCʽȫͬڷֲʽý廷£ýϢֵϸͬҪڶԶýĴбýͬṩ˵˷ʱ漰ӳ٣delayjitterȷ⣬ԱԷֲʽýϵͳṩϸķƣʵʱͬԱڷֲʽýϵͳУϢϸ񱣳ʵʱͬҪ󱣳ִýɼýֶϸӳٺͶΧýͬintra-synchronizationҪڼýбʱ໥ʱϵýͬinter-synchronization.ý崽ͬlip-synchronization⣬ϸ񱣳ƵƵͬ.
ڴͳĶýͬҪAllenͳһʱģͣ1ݣequalmeetbeforeduringstartfinishoverlap13ֻʱ̬ϵͬĶýͬģ.T.D.C.LittleAllenʱϵOCPNģͣ2ݣPetriýʱϳɻ˳ͲʱϵͳһʱOCPNģ.Peter King3ΪֲAllenʱϵȷԣITLinterval temporal logicýĵеͬ.֮෴WahlRothermel4ݸ29ֶýͬʱϵͬϵ֮⣬˴ĲȷԵķǾȷʱϵ.ȻЩģֻý֮ͬϳɣڷֲʽµĶýͬ.ڷֲʽµĶýͬ⣬HutchinsonBlair5ݸʵʱ¶ýͬԼϵReganҲԷֲʽýϵͳͬ.
ȸڽ̴LOTOSʽ淶ԣ6ݵĻȻͨԴͳLOTOSлʱ䣬ʱӣӦ﷨.ͨԷֲʽµĶýͬϵͳķûʱLOTOSϸĶý崽ͬ㷨.󣬱ľһʵϵͳ˽һ˵.
2LOTOSĻ
LOTOSISO֯Ϊʽֲϵͳƶһֹ淶.LOTOSǻڽ̴ģͣоȷ﷨ʽ壬Э֤һֳ󼶱ϸߵʽ.ڣһϵͳͨⲿпɹ۲쵽Ľʱϵ壬ɷڷֲʽϵͳ.
LOTOSϵͳ໥ͨŵḶ̌process.ִ̿ڲΪҲͨžgateⲿ̽.žΪ̵ͬͨŵ㣬žϵΪžʹ͵ݹ.LOTOSݽṹֵʽûڳ͵ACT-ONE.ǸLOTOS﷨

У
P̵Ϊʽ
stop̣ܽκλ¼
gd*;PgΪPžd*Ϊ.Ϊжǰ׺.Pͨ
g罻.aΪⲿ¼gd*ɱʾΪa
i;PPڲ¼i
bcݡPʽbcΪʱPΪstop̣
PۣPۣΪѡ
P|G|P|ۣ|ΪкϳɲͨžG̲еؽͬͨţ
ͨžGΪУɱʾΪP|ۣ|P
X(e*)X(e*)e*Ϊʽ.
LOTOSӦóACT-ONEͣݵĲ涨Ϊ
g!e;P:Pͨžgͱʽeֵ
g?(x:T)P:PͨžgֵֵTıx.
3ʱLOTOS
ֲʽýϵͳĺǿ佻ԣ绷Эͬ.ʵʱǷֲʽýϵͳеĹؼ.ԿͳLOTOSȱ֧ʵʱ淶.ԴͳLOTOS䣬ЧضԷֲʽýϵͳʽķоԱһо˴Ĺ.LOTOS-TTemporal LOTOSET-LOTOS.ʱLOTOSУܾȷͷʵʱĶýϵͳ.LOTOSʱ䣬¼ȼж.Reedͨڲ¼ȼ䣻BolognesiBrinksma6彻¼Ľ̶ȱʵʱϵͳ.ͨʱӣȷ¼ķԴﵽLOTOS֧ʵʱϵͳĿ.
3.1ɢʱ
ڶLOTOSʱʱȱ뿼ֵ֧ʱ.ɢʱ֧¼ʱȣֻԾȷ.ʱ֧¼ľȷʱнǿıʱԵ֤ڸӣӦָʽǶ.ڷֲʽýϵͳУͬҪý֮ʵʱͬʱԾȷԶýͬҪ󼰷Ҫ󣬹ʶLOTOSɢʱ.ӲʵʱϵͳУʱ֧Ǳزٵ.
ɢʱTʣ





t1t2,򼯺{t|t1tt2}Ϊt1,t2Ϊһʱ䣻
t2tt4,tʣt1,t4.
3.2ʱ
ӳӺͲӵʱӣLOTOS.ӳӵĿʱ䵥ԪĶ͹Ӧ̣ʹһʱ.ʽ£
1.ӳD(n)D(n)PʾΪnʱ䵥ԪP̣
2.M(t)cond.ݣM(t)cond.PʾΪtʱcond.ʱP.
LOTOS﷨Ϊ

3.3LOTOSĲ
(1)Ŷ
¼̣=LG{i}.LΪLOTOSеⲿ¼ƱǼGΪž.aLgG.ڲ¼Ϊi.PP估QQΪLOTOSĽΪʽ.
ǿԵõLOTOSĲ.
(2)Ƶ



4ֲʽ¶ýͬķ
ԷֲʽµĶýͬ뿼ӳ붶ȷȷصӰ죬ҪýڵͬͷQoSҪýýͬƺ͹涨һµķı֤.OCPNģΪһͨõĶýͬģͣҪý֮ͬϵýڵͬȱ֧֣һִȵͬģͣɴ˷չһXOCPNģһϸͬģͣýڷֲʽµĴƣһµQoSЭ̻ƣȱڲͬĶ̬.ʱ߼ITLýͬ⣬ŵڸý֮ϸȷʱϵڷֲʽµķȷԵĽƱ.
ͨԷֲʽµĶýͬķʱչLOTOSʽоǸһĶýͬ˵ýͬķı̶֤Ըӵϸͬ⡪ͬʽ˵ý֮ͬ.
4.1ͬ
ɶýڷֲʽ´ԣǽֽͬ3Դˣsourceý飨mediumˣsink.ͼ1ʾ.

ͼ1ֲʽµĶýĴ
ͬķʽýԴÿnmsһݰýӳڣl,l+lݵʱ䷶Χڣÿһݰpmsp+pms.
ӦûʱLOTOSʽԻͬʽڷֲ£ͬΪ3Դˡý顢.ͬžΪSourceOutSinkIn.򣬶ýĽΪ
Source|SourceOut|Medium|SinkIn|Sink;
ͬͬ㷨ʽ£
Source:
Source(fr:N)=D(n)SourceOut!fr;Source(fr+1);
Sink:
Sink=SinkIn?fr:N;Sink|ۣ|M(t)p,p+p(play!fr;Sink);
Medium:
Medium=SourceOut?fr;N;
((M(t)l,l+l
(D(t)(SinkIn!fr;stopۣi;stop)))
|ۣ|Medium).
4.2ͬ(lip synchronization)
ͬһϸĶýͬ⣬ĻҪϸ֤ýͬͬʱҪý֮ϸͬ.ҪӦ÷ֲʽµĿӵ绰ϵͳеƵƵ֮ͬ.ȶԴͬзӦ̶ͬӦûʱLOTOS㷨.
(1)ͬ
ƵýƵԴƽݴΪÿdsmsһݰκεӳ붶
ƵýƵԴƽݴΪÿdvmsһݰƵýԼΧڵĶ趶Ϊjms
ͬƵýֵʱΪtpsݴͬҪƵýıʱʱtps-vpretpsvpost֮ڣ򽫲ܱͬ.ЦvpreΪƵýֵǰvpostΪƵýֵͺ.
(2)ͬʽ
ֽͬΪ5.ýԴˣSoundSend̺VideoSenḍý飺MediuṃˣSinḳͬƣSync.ͬɱʾΪ
SoundSendVideoSend |S_Send,V_Send| Medium |S_SinkIn,V_SinkIn| Sink |S_gate,V_gate,Syn_gate|Sync.
һǸ̵LOTOSʽ壺
SoundSend:
SoundSend(fr:N)=D(ds) S_Send! fr; SoundSend (fr+1);
VideoSend:
VideoSend(fr:N)=D(dv) (M(dv)dv-j,dv +jV_Send! fr; VideoSend (fr+1));
Medium:
Medium= (S_Send? fr;N;
((M(t)l ,l+l
(D(t) (SinkIn! fr; stop  i; stop)))
|ۣ|Medium))
|ۣ|
(V_Send? fr;N;
((M(t)l,l+l
(D(t) (SinkIn! fr; stop  i; stop)))
|ۣ|Medium))
Sink:
Sink=((S_SinkIn ?fr:N;S_gate!s_avail,s_avail_time;Sink)
|ۣ|
(V_SinkIn? fr:N ;V_gate!v_avail,v_avail_time;Sink))
|ۣ|:BOOL;flag=TRUEݪM(t)p,p+p(play!fr;Sink)
Sync: 
Sync=S_gate!s_avail,s_avail_time;V_gate!v_avail,v_avail_time;
M(v_avail_time)s_avail_time-v_pre,s_avail_time+v_postSyn_gate?TRUE; Sync
5ʵ
ͳĴͬϵͳǽƵϢƵϢԴ˽ͬ룬ýϳΪһϢͨý飬ݱֶ˽ͬ룬Ӷýͬ.ַĿԶȷýݱֶ˵ͬͬĴǴӲ/ҪܸߣЧֱӰ쵽ͬЧ.
ͨʱչLOTOSԷֲʽýϵͳͬķһͬʵϵͳ.ƵϢƵϢֱ䣬ͨͬƻƣһͬı֤£ﵽͬҪ.ͼ2ʾ.

ͼ2ͬϵͳṹͼ
ͬΪƵýÿ30msһ֡ӳٶ.Ƶýÿ40msһ֡Ƶý֡ӳٷΧΪ35ms45ms.ƵýͬҪǰó15msӳó150ms.ϵͳͨͬƻƣƵ/Ƶͬƣźs_avail_play,v_avail,v_play,s_ready,s_ok,v_ready,v_okЧر֤˶ýϢڷֲµĴͬҪ.
봫ͳķȣʱLOTOS룬ܱ֤Բͬýϸͬṩȷʱ䶨.ͬʱͬӲҪһͬԼ£˴ͳͬϸҪ֮֡֡临ӵͬ޶.ʱʹýϢڷֲͬṩQoSΪ.
6
ͨʱӶԴͳLOTOSʽ淶Խ䣬ʹֲ֮LOTOSȱ֧ʵʱ淶ӦûʱչLOTOSֲʽýϵͳеͬ.ֲʽýϵͳеͬĺǣҪýڲͬϵҪֲ֧ͬý֮ͬҪ.ӦLOTOSʽ׼ȷؿ̻ڷֲʽĻ£ýĴ估̣ͬṩϸȷʱͬҪ󣬶ڷֲʽµķȷԸһʱ䣬ͬҪ.ڶͬиӳ١ȷĲṩһķı֤.Ϊ˸оֲʽýϵͳͬ⣬ͱṩƵķĻƣԱ֤ͬҪ⽫ǽоص.
õҡ߿ƼĿ(Ŀ863-306-04-01).
߼飺ΣУ19734ʿоҪоΪ֪ʶ̡ý.
ߵλ(人ѧѧ뼼ѧԺ人430072)
(Ҷý̼оģýоʵҡ人
430072)
ο
1Allen J F. Maintaining knowledge about temporal intervals. Communications of the ACM, 1983, 26(11): 832843
2Little T D C, Ghafoor A. Synchronization and storage models for multimedia objects. IEEE Journal on Selected Areas in Communications, 1990, 8(3): 413427
3King P R. A logic based formalism for temporal constraints in multimedia documents. In: PODP 96, 1996
4Wahl T, Rothermel. Representing time in multimedia systems. In: Proc IEEE Int'l Conference on Multimedia Computing and Systems, Boston ,MA, 1994. 538543
5Blair G S. A programming model and system infrastructure for real-time synchronization in distributed multimedia system. IEEE Journal on Selected Areas in Communications, 1996, 14(1): 249263
6Bolognesi T,Brinksma E.Introduction to ISO specification language LOTOS.Computer Networks and ISDN Systems,1988,14(1):2559
ԭյڣ1999-02-05޸ĸյڣ1999-05-09.
