΢ͻӦ
MICROCOMPUTER & ITS APPLICATIONS
2000 Vol.19 No.3 P.33-34,40



ֲʽݴʱͬϵͳ
ŷšά
ժҪֲʽݴʱͬϵͳΪ˽ֲʽеĸּͬһֹߡʱͬϴźܶ,ӰʱͬľȡĽΪϸطҪԭ,Ҹʵ˽Ľͷ
ؼʣֲʽ ݴ ʱͬϵͳ 
1 ֲʽݴʱͬԼ
Ŀǰ,ӦҪԵĸ߿ɿԺ͸ЧȷչؼԵĹ,纽ϵͳҽƼϵͳԼܷϵͳȵȡϵͳ޷κεĴͳҪ,ѲʺϸĻ,,ξȷմģʽӰ̶һ൱Ҫ⡣
ż缼ķչӽṹclient/serverᳫ,뼯Ȩʽcentralized processingеԡɱ͵ķֲʽṹdistributed processingΪֽڶϵͳáֲʽϵͳݴfault tolerance in distributed systems̽ݴڷֲʽϵͳеӦá缼ķչ,ϵͳ,ȡ֮Ƕ๤ķֲʽϵͳֲʽϵͳҪԪ:ͨ硢ʱϴװü,ЩǵһԪ,Щ͵Ԫͨῼݴʵ,ڷֲʽϵͳ,ЩԪ໥ķʽ,Ԫ,ЩԪݴ˷ֲʽϵͳݴ,ǷֲʽϵͳݴҪо롣ʱͬǷֲʽϵͳݴ൱ҪĿ⡣
Ŀǰķֲʽϵͳʱͬϴżϵ:1.޷ʱͬΪڷֲʽ,ÿڵ㶼Լļʱ,ÿʱĽʲȫһ,Ѵϵͳڵʱϵľͬ;2.ֲʽϵͳеʱͬҪοڵʱ,Ҫȡòοʱ,ҪͨͨĴݡʵͨϢһʱϵӳ٣propagation delay;3.οʱڷֲʽдȷҲӰϵͳʱͬ
ֲʽݴʱͬ㷨൱,ϿɷΪ͡
1.1 ʽʱʱͬ
ʽʱʱͬڷֲϵͳ,ֱӡҲ㷺ӦڷֲʽϵͳдﵽʱͬķԾϵͳн1ɸи߿ŶЧȵʱ,ϵͳĽڵ͸ֱͨӵߢȡȷʱԵʱ,ﵽϵͳиڵʱϵͬ
ʽʱͬҪӦNTPNetwork Time ProtocolصSNTPSimple NTPƶ,ҳΪʱͬƵı׼ʱʽʱͬԵĹؼNovell Netware 4.01ϵͳҲǲõʽṹNetware 4.01ϵͳΪڲʱͬinternal time synchronizationⲿʱͬexternal time synchronization,Ҫǽֲͬ͵ʱ,䲻ͬĹֲܶ,ͼ1ʾʽʱʽʱͬԵŵԭ豸ܼ,ȱݴ͡ʽƿЧӦbottle-neck effectӰȡ

ͼ1 Netware 4.01ʱ
1.2 ռͥЭʽʱͬ
ռͥЭ飨Byzantine Agreement/ConsensusڷֲʽϵͳݴһֻҪݴ,㷨һڵ䵱,һضϢн,ǴڵյϢһ,Ὣȷع㲥ʣڵ,ÿڵ͸˴ϢĽ,ͨmajorityʽ֪Щڵ㷢,֮ڵ,ϴݻؽϢ,ֱдҵΪֹ,ͼ2ʾ

ͼ2 ռͥЭʾͼ
ռͥЭ:1зֲʽϵͳеκδarbitrary fault,Ϣʧڵȵ;2ҪִmεݹԾm;3ݴԴܽڵ֮һĴ,ÿڵڴ2
ռͥЭҲʱͬĲ,ŵ:1ݴǿ;2κ̬ϵͳȱ:1Ҫ൱Ϣﵽ,縺;2ضϢĽ,ʱͬ轻ضĲοʱϢ,Ӧϵơ
1.3 ʽʱͬ
ʽʱͬǷֲʽݴʱͬ㷨ое3ֱ㷺ʹõһֲԡĿѼϵͳиڵĲοʱ,ͨ1ЧռĲοʱͬʱ,ٸԵʱ䡣:
1.Ľڵռοʱֵ;
2.Ӱؽʱֵ;
3.һЩʱֵ,һȷʱֵ;
4.ȷʱֵԵʱ䡣
2 ֲʽݴʱͬϵͳ
ǿС1ʱЭ顣,ЭҪﵽľ0.5s,Ƶϵͳ1̨1ͻ,ͻʱͬ,յʱϢ͸ͻ,ӶﵽʱͬʵʵĹ,ڸԭ,˺Ϳͻ˲ܴﵽȫͬ,Ϊʱ䴫дŸ
ݷֲʽݴʱͬϵͳľȹʽ:

ʽ:nΪڵ,kΪĽڵ
ϵͳвΪmaxͦmax,ЦmaxΪʱϢʱֵ,maxΪʱֵмֵ,ҲʱϵͳµĿͻ˼ʱ,ܻΪmaxֵӰ쾫ȷ,Ǿ2ʱͬں,Ϳһֵǵʵ,ͬ1,3ʱΪͬ,maxֵ28550ms,˦maxӰڹ̶,䶯Բ
1Ӱʱͬȷȵؾ紫ӳ٦maxеʱͬԶ,ӳٶǷǳҪıءΪֲʽϵͳݴʱͬҪΪ:ʱͬͼʱͬǶ֮ҪĲ紫ʱӳ٦;⾭ʵ֪,紫ʱӳԽС,õʱͬȷȾԽߡ,紫ʱӳʱͬоооص,ǲɺԵġ
ϵͳʵ,ҪԭΪ紫ʱӳ̫,Ӱͬľȷȡ紫ʱӳٹԭ,оʵ,óӰ紫ӳٲԭͽ취
1.TCP/IPͨЭ紫ӳӰ졣ǵSNTPϵͳǲTCP/IPͨЭΪͨŵĻ,ȻԱ֤ʱϢʧͣretransmission,紫ʱӳ,ɦmax,Ӱʱͬľȡ
ISOƶISOοģ߲ṹ,SNTPϵͳӦò㣨application layerͨ,TCP/IPڴ㣨transport layerͨЭ,Ϊ紫ʱӳٹҪԭTCP/IPͨЭͨЭӳ٣Protocol delay,ɦmaxֵ,ͬڴٶȺͨϽʱͬһ,ഫݽʱϢӳȻ,Ӱʱͬľȡ
2.ͨЭӳٵĴСʾʱû紫״̬,Ӱطǳ,縺أnetwork traffic loadûæµ״̬ȡ
2Ӱ紫ӳٵԭ,он취:
1ͨЭӳٵӰ,ʱͬϽ,СϢʱӳ,Խӽʵʱӳ,ﵽʱͬľȷ,ͼ3ʾ

ͼ3 ͨЭӳʾͼ
ȻͨЭӳٵӰ첢ô,TCP/IPڿɿԴͨЭ,Ĵʱ޷Ԥ,ͬͨЭӳҲ޷Ԥ,ʱ̵ͨЭӳ޷Ʋһʱ̵ͨЭӳ,˺ֱӲԡڽʱͬɼʱϢʱ,ͻ˸͸ϢLocal Host,㱻,˿Բʱͻ˵ͨЭӳܺ͡
2Ӱ,ȻͨԵʱͨЭӳٽв,޷ڽϢʱϢͨЭӳ,ΪСοֵ,ھӽʱͨЭӳ١ǵSNTPϵͳҪԾӦ,֮ǰгĽ,տɵþʱӳС10ms紫ʱӳֵΪa,iͻ˵ͨЭӳΪQci,ͨЭӳΪQs,Ϊ=Qs+Qci;ҲȡminQs+Qci֮ȡСߵͨЭӳٵСοֵ,ѡminQd,minQs+QciΪͨЭӳٵĲοֵ
ڸԭ,ǶĽʱͬӦòϽеķûеõʵ֤ʵ,ͨԤ֪,ԭϢݷʽ,˷Դظϵͳӳ
ŷ人ѧѧԺ430074
ţ人ѧѧԺ430074
άᣨ人ѧѧԺ430074
ο
1Mills D.L.Algorithms for synchronizing network clocks.DARPA Network Working Group Report RFC-956,M/A-COM Linkabit,1985;(9)
2Mills D.L.Network Time Protocol (version 2)-specifi-cation and implementation.DARPA Network Working Group Report RFC-1119.University of Delaware,
1989;(9)
3David L.Mills,Simple Network Time Protocol (SNTP),network working group report RFC-1361,1992;(8)
4Digital Time Service Functional Specification Ver-sion T.1.0.5.Digital Equipment Corporation,1989
5 Halpern J Y,Simons B,Strong R et al. FaultTolerant Clock Synchronization.Proc.Third Annual ACM Syn-posiumon Principles of Distributed computing.1984;(8)
6 ,.TCP/IPԭ뼼.:廪ѧ,1993
ոڣ1999-10-31
