о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999Vol.36No.7P.819-823



һѯϵͳƽʱ
ǿסͨ
ժҪȽ˷Ȩ޷ѯϵͳĲԭڴ˻ϣͨϵͳǶɷĸLaplace-Stieltjes任ϵͳƽʱ䣬֤ͨ˹ʽȷ.
ؼʣȨѯϵͳ, ޷, ƽʱ, ATM, ĸ, Laplace-Stieltjes任
ţTP393
MEAN CYCLIC TIME OF A POLLING SYSTEM
LIU Qiang
(Communication Research Center, Harbin Institute of Technology, Harbin 150001)
ZHANG Zhong-Zhao
(Communication Research Center, Harbin Institute of Technology, Harbin 150001)
ZHANG Nai-Tong
(Communication Research Center, Harbin Institute of Technology, Harbin 150001)
AbstractThe principle of the no interrupted priority queue polling system with gated service is introduced in this paper. By using the imbedded Markov chain method and the generating function of queue length and Laplace-Stieltjes transform, the mean cyclic time in statistical equilibrium with symmetry distribution is obtained. The formula is tested and verified by simulation.
Key wordsno interrupted priority queue polling system, gated service, mean cyclic time, ATM, generating function, Laplace-Stieltjes transform
ѯϵͳǴ·Դϵ򵥷.üпʽͣǿÿозŵĻᣬɴﵽϸߵӳҪ󣬴ӶӦڸϵͳATM.ATM߿Ƹ/еѯнṹ򵥣չǿͻŵ㣬Ŀǰ㷺ӦATMУ13.ѯϵͳΪϵͳһζÿһе̽ѯ̽ѯ˳У֮̽ѯʱΪ߲ʱ䣬̽ѯĶл÷ŵĻᣬվҪ͵ݣŵȫʽĿĵأһ̽ѯ4. KumarԹ滮㷽Ŷģͣ˺иȨ˿ѯŶ缰ͬ˿ͲòͬʱѯŶۣóܵͼóܽƽ5.Yangþķȷ˴ȼTDMϵͳ½磬ַҲûеóȨϵͳܱʽ6.HashidaøĸķͨǶɷԻѯϵͳ꾡ľȷóϵͳܵʽ7.ѯϵͳУƽʱϵͳ۵Ҫָ꣬ĲHashidaõķǶɷķ˷Ȩ޷ѯϵͳԳƷֲƽʱ.
1Ȩ޷ѯϵͳԭ򼰱
ϵͳһĶкNһйɣѯʽв.ĶозȨĶϢҪʱʱԱһһеķĶнз񣻷򣬵ȴԱɵǰеķĶнз.ԱԶеķͣԱֻԷԱöʱڶڵϢз񣬷еϢһѯöʱз.ǷȨѯϵͳĲԭ.
Աһ㰴12Nнѯ1Nܷ֮.Ķй˿ͣڵǰз֮󣬲߲ʱȷĶУȻѯĿǰԱǡһеѯĶнзȻѯ.ÿеŶΪ޴󣬽еĹ˿Ͱȷԭз.һi (i=1,2,,N)Ϊɹ̣ΪiʱΪһֲֲΪHi(x)ֵΪhiҵǿΪii=ihi ĶΪɹ̣ΪCʱΪһֲֲΪHC(x)ֵΪhCҵǿΪCC=ChC.Ӷii+1߲ʱΪһֲֲΪi(x).Ƕ
CĶУ
iӶii+1߲ʱ䣬i=1,2,,N
vi()ʱڶiĹ˿i=1,2,,N,C
gi(j1,j2,,jN,jC)ƽ״̬£Աi(i=1,2,,N)ʱڶk(k=1,2,,N,Cjk˿͵ȴĸ.
ĸ
(1)
2гȵķֲ
һУԱĳеʱΪtntn+1,ﲻĶеʱ̣С<tn<tn+1<TΪ{tn}.
Ƕ 
n(i)Ϊʱtni(i=1,2,,N,C)еĹ˿
nΪʱtnԱڵĶкţn(1,2,,N).
ʱtn,ϵͳ״̬ı
n,n(1),n(2),,n(N),n(C)
ˣϵͳ״̬ռΪ
I={(i, k1 ,k2, , kN ,kC) i=1,2,,N kj =0,1,2, j=1,2,,N,C }(2)
״̬n,n(1),n(2),,n(N),n(C)תƸʹһԼڵɷм޸ʣ
(3)
еjk0 ( k=1,2,,N,C )
(1) gi(j1,j2,,jN,jC)>0ɷǸ̬ģϵͳﵽȶ״̬
(2) gi(j1,j2,,jN,jC)=0ɷ״̬ǻ̬㳣̬.
ȶ״̬ıҪǣ
(4)
Цi=ihi,C=ChC,i=1,2,,N. hiǶi(i=1,2,,N)ƽʱ䣬hCΪվƽʱ䣬ķʽ(4)Ļ.
ʱtn+1Աi+1tnǷԱһεiʱ̣tn,tn+1T.iΪڶi(i=1,2,,N)ܷʱ䣨tntn+1֮䣩iΪӶii+1߲ʱ䣬i-1ΪӶi-1i߲ʱ䣻FC(x)ΪĶڿʼܷʱĶx˿ͣĶзʱķʱ.
ˣУ

һ˵ʱtԦʵĲɹ̣˿͸ĸ
(6)
УF*(s)ΪtķֲLaplace-Stieltjes任.
ԱiʱiЦn(i)˿ͣ˦iֲLaplace-Stieltjes任Ϊʽ
H*i(s)n(i)(7)
*ʾLaplace-Stieltjes任8.
ǵvi(i=1,2,,N)ͦi(i=1,2,,N)໥ԣùʽ(5)(7)ǵõP(i+1,n+1(1),n+1(2),,n+1(N),n+1(C))ĸ

ʽ:

ʽ8Уnޣϵͳƽ״̬У
(9)
Gi(x1,x2,,xN,xC)ĺϵͨʽʾˣǻƵʾʽ.
gi(j)(j=1,2,,N,C)ΪԱiʱjƽȣgi(j)ͨʽм㣺
(10)
ʽ9i =1,2,,Nʱǵõ
Gi(1,1,,1,1)=k()i=1,2,,N
(11)
ʽ9Уxj΢֣ҽxl1 (l=1,2,,N,C), ǵõ

ʽ12i=j,j+1,i-1,iۼУ
(13)
еj>iʱУ
ʽ13Уi=j-1У
(14)
ϵͳǶԳƷֲʱЦi=,i(x)=(x),Hi(x)=H(x),ϵͳﵽȶ״̬ʱУgi+1(C)=gi(C) (i=1,2,,N).
gi(C)=g(C) (i=1,2,,N), gi(i)=g(i=1,2,,N)ʽ12ã
(15)
ʽ15ʽ14УУ
(16)
ʽ16ΪԱk (k=1,2,N)ʱһk (k=1,2,N)ƽ.
3ƽʱ
ÿηԱվƽʱΪhCg(C)+Chg.ˣϵͳƽʱΪ
TC=Nhg+N+NhCg(C)+Chg
ʽ1516ʽУϵͳƽʱΪ
(17)
ʽУNΪѯϵͳһվĸΪ߲ʱľֵCΪĶеҵǿȣΪһеҵǿ.
4ۼʵ
ϷĻϣCandence˾BONeSƽ̨ϵͳĲԭ򹹽ϵͳķģͣзʵ.ۼͷʵͬϵͳһΪԳƷֲΪɹ̣ʱ߲ʱΪһֲ=0.0006h=0.0001C /ѷֱȡֵ1234ϵͳҵǿȦ=C +NѣĶкһаҵǿȣһиֱΪN=10N=50ۼͷ棬1ͱ2ʾ.
1N=10ۼͷ

ֵ
C /=1C /=2C /=3C /=4
0.100006.6667E-36.6800E-36.6796E-36.6685E-36.6757E-3
0.200007.5000E-37.5121E-37.5119E-37.5122E-37.5155E-3
0.300008.5714E-38.5700E-38.5706E-38.5711E-38.5721E-3
0.400001.0000E-29.9937E-39.9898E-39.9878E-39.9867E-3
0.500001.2000E-21.1989E-21.1983E-21.1983E-21.1976E-2
0.600001.5000E-21.4978E-21.4934E-21.4978E-21.4985E-2
0.700002.0000E-21.9993E-21.9981E-21.9946E-21.9956E-2
0.800003.0000E-22.9978E-22.9983E-22.9948E-22.9952E-2
0.900006.0000E-25.9985E-25.9979E-25.9944E-26.0068E-2
0.950001.2000E-11.2011E-11.2029E-11.2013E-11.2023E-1


2N=50ۼͷ

ֵ
C /=1C /=2C /=3C /=4
0.100003.3333E-23.3325E-23.3326E-23.3323E-23.3313E-2
0.200003.7500E-23.7489E-23.7510E-23.7480E-23.7504E-2
0.300004.2857E-24.2832E-24.2796E-24.2866E-24.2789E-2
0.400005.0000E-24.9917E-25.0101E-24.9898E-24.9897E-2
0.500006.0000E-26.0053E-25.9919E-25.9902E-25.9900E-2
0.600007.5000E-27.4716E-27.4694E-27.5188E-27.4711E-2
0.700001.0000E-19.9639E-29.9880E-29.9978E-21.0021E-1
0.800001.5000E-11.4929E-11.4988E-11.5101E-11.4986E-1
0.900003.0000E-12.9885E-12.9790E-13.0165E-12.9893E-1
0.950006.0000E-16.0243E-15.9869E-15.9457E-16.0523E-1


ӷԿһиֱΪN=10N=50Ķкһоиֲͬҵǿʱϵͳķۼֵ. 
5ᡡ
ͨԷȨ޷ѯϵͳǶɷķĸϵͳƽʱ.Կƽʱվ߲ʱȵģ1ÿУһкĶУҵǿ֮͵Ĳɷȣʽ17ʾ.ʵ֤۷ȷ.
Ŀõҡ߼չƻ(Ŀ863-2-4-8-2).
߼飺ǿУ1971ʿоĿǰҪ¿ռվڲͨϵͳо.
ףУ1951ڣʿʦ.ҪоΪƶͨšC3IӦáATM硢ռͨ.
ͨУ1934ΪҵѧͨżоڣʿʦҪоΪATM硢ƶͨšͨ.
ߵλǿҵѧͨżо150001
ףҵѧͨżо150001
ͨҵѧͨżо150001
οף
1Kesidis G. ATM Networks Performance. Boston: Kluwer Academic Publishers, 1996. 647
2Goralski W J. Introduction to ATM Networking. New York: McGraw-Hill Inc, 1995. 128189
3Minzer S E. Broadband ISDN and asynchronous transfer mode. IEEE Communication Magazine 1989, 27(9): 1724
4Joseph L P O'Reilly J P. Performance Ananysis of Local Computer Networks. Reading: Addison-Wesley Publishing Company1986
5Kumar P R. A tutorial on some new methods for performance evaluation of queueing networks.IEEE Journal on Selected Areas in Communication, 199513(6): 970980
6Yang O W, Mark J W. Queueing analysis of an integrated services TDM system using a matrix-analytic method. IEEE Journal on Selected Areas in Communication, 1991, 9(1): 8894
7Hashida O. Analysis of multiqueue. The Electrical Communication Laboratories NTT, 197220(3-4): 189199
8Cooper R B Murray G. Queues served in cyclic order. The Bell System Technical Journal, 1969, 3: 675689
ոڣ1998-09-14
޸ڣ1998-12-24
