ѧ
JOURNAL OF SOFTWARE
1999 2 No.2 1999



˵ʽԵо*
֮˶
ժҪӦķʽ˽ṹķ.ڸʽԵ,3Ԫ״̬,ͨԻԪ״̬״̬ɵķ,׼ȷнͨż洢״̬.ͬʱ,֤ô˷ĳ´ӳʼ㵽˽ԽΩһķ·,ܱͻ.˷Լ/ͻоһĲοֵ.
ؼʡʾ,ķ,Ԫ,.
ͼšTP301
Research of a Formal Language for Describingomputer Network Topology 
YU Zhi-shouYANG Jing
AbstractBeing different from the general method, a formal language and grammar, stochastic liner grammar and its representation are used to describe the topology logic of the computer network by analyzing the grammar of three elemental statuses. It can be seen that combining them may describe statuses of each node in communication and shared memory of the computer network. In this paper, it is proved that the grammar can establish only route between the start node and the terminal node in some conditions. Under conditions above if may avoid collision. The use and the limit of the grammar are presented at the end of the paper.
Key wordsProbability matrix, grammar, base element, network.
Լ˽ṹ,㷨ͨȡͼۼķ.Ϣͷ䷽ǻڸ.һԼķ,ͨϸĶķʽ,ʹΪһԱʽ,ӦǰƵʾȷؼȷֵ,ʹҪļ֮佨Ψһѵͨ·.ΪʹϱԷ,ؼ£
(1) ȫͼͼ11ʾ.ÿһ㶼ʾһд洢ļû.

ͼ1ȫͼ
(2) и3״̬ ĳԴ Դæڵȴ õԴǶд.
(3) m,K˵,ķʸPkӦ
Pk=Pki,(1) 
PkkʾԱĴ洢.Ϊ,ɰPkֳPk,Pk,
Pk=Pk+Pk.(2) 
PkΪһķʸʺ,
Pk=Pkii={1,2,...,q}.(3) 
PkΪһķʸʺ,
Pk=Pkii={q+1,q+2,...,n}.(4) 
(4) ÿһԴƷģʽ.
(5) Ӹȷ˵,״һ.״ĸʷ¾(ͼ1ȼ).

Ρμĸʷͼ2ʾ1.ͼ2ɼ,ھͬĿ,ĸʽΪ66,ͬĳЩΪ.Ҳʷ.


(a)ʾ󡡡(b)ʾ
ͼ2Ρʾ
1ʽģʽ
1.1ģʽ
һ˵,ķ4ͼ1,0͡ķ1͡йķ2͡޹ķ3͡״̬ķ͡ķ.
ķ¼,ԵĶ﷨ṹԶΪһԪʽ2,
Gs=(VN,VT,PS,S),(5) 
VNΪֹVTΪֹPSΪʽ޼ϣSΪʼ,SVN.
õķĽṹGSʽ(5)ͬ,VN={A1...AK},S=A1,VT={U,V,Ur},PSΪAiUAjV,AiUr,ҶÿAjVN.ȼCAiͨñʽΪ
CAi={PSΪAiĲʽ},

PS=CAi.(6) 
ԾPSĲʽΪAiUAjV,AiUr˵,AiUAjVĸΪPij,AiUrĸΪPir.ڵiĲʽΪ
PS=Pij+Pir.(7) 
1.2ķһ
ķһԵĶΪ
Px)=1,
(8) 
,ķһԵĶֿΪ
Pij+Pir=1.(9) 
ʽǲΪ(K+1)ӦVNU{T}״̬޸Ʒ̣2.GSһµ,״̬TӦһ״̬,״̬Ӧڹ״̬.ͬʱ,ڲʽAiUAjV,AiAj֮һ·,AiUr֮Ҳһ·.κνAi,ÿνʽ֮һ,ĳʱ̴Aiʼɵ״̬һ,ڵʽSx,ڳʼSյһ·.Ҫ,GSһµ,ӳʼ㵽յUrVTĸʱΪ13,4.Щʰĸ״̬ͲķһһӦ,GSһµ,ÿһ˲䱣֤һԴ,ͻֹͻ.
ף2ᵽжķGSһµ
lim m1,k+1(n)=1,(10) 
mij(n)=Mn=M1M2...Mn,ʽMΪʷ.,m1,k+1(n)ʾMNκľе1еһԪ,˺ϽǵԪ.lim m1,k+1(n)=13ݱʾʼ㵽˸ĸΪ1.
1.3һķ
һķGS=(VN,VT,PS,S),VN={S,A,B}ΪյVT={0,1}ΪյSΪʼ״̬PSΪʽ.
 
зֲM1Ϊ

P1=0.4,P2=0.5,P3=0.6ʱ,

nʱ,

lim m1,4(n)=1.,ķʽΪPS,ҷʾΪM1,ʷP1=0.4,P2=0.5P3=0.6ʱGSһµ.ķʾͬ,ͬ,nʱ,lim m1,4(n)1,˵ķҲڲһ.
2ķʾԪ״̬
ݱĸеļ,ϸɴڡԴæ͡д״̬֮һ,״̬3״̬϶.ѡһķ,һԴ,κνԴܿǶԴ,ʷPK=PK+PK.һԴķʾ״̬ΪԪ״̬,Ƴ3ֻԪ״̬ϸһ״̬5.
2.1Ԫķ1
״̬ķͲʽΪGSPS,ķʾ״̬ͼ3ʾ.ͼ3,SԶԴAB,ʷֱΪP11-P1,BԴ˵æ,SBȴ.ȴĸ1-P3,B׼,ɶBԴд,á00ʾ.AԴ˵,SԺ,ѡһͨAԴ루á1ʾ,ҲΪǡһͨAԴBԴ,ĸP2.

ͼ3ķGSʽPS״̬ͼ
2.2Ԫķ2
״̬ķGS2=(VN,VT,PS2,S.PS2Ϊʽ,:

ӦGS2PS2״̬ͼͼ4ʾ.ͼ4,SɶAB,ÿһԴɵ.

ͼ4ӦGS2ʽPS2״̬ͼ
2.3Ԫķ3
״̬ķGS3,GS3=(VN,VT,PS3,s).PS3ʽΪ:

ͼ5ʾ,״̬൱ABǡ,ǵĸʷֱP2P3SABʱ,ABæ,Ƿֱȴ,Ϊ1-P21-P3.GS4=(VN,VT,PS4,SǻԪķ4,Ӧ뵽Ԫķ3.ΪGS4˽SABʱ,ABڡд״̬.

ͼ5ӦGS3ʽPS3״̬ͼ
2.4Ԫķ״̬ĺϳ
ͼ6ʾ,AԴȴ⻹һP2,ҪAԴҪ(1-P4),Ҫд(P4).͵ǰķ3ķ2޸ĺϳ.ķΪGS5=(VN,VT,PS5,S),ʽΪGS5


ͼ6ϳ״̬ģʽ
3Ӧ3ֻԪķ
µĿʼ,ͼ1A,B,C,Dǽ,EFǴ洢,E,ͼ7ʾ.

(a)A״̬ͼ(b)ֻ洢E״̬ͼ
ͼ7ͼ1ӽṹ
3.1Խ
(1) ԽAͼ7a)ʾ,ķͬǰ״̬,ʽPSAΪ:

(2) A״̬ͼԿ3״̬ͼ:
 Է,SA1SA0,൱ڶ˽д洢,ΪPAA֦൱ڶ,ŶPAA=PAB+PAC+PAE+PAF,ϼ,൱ڻԪķ2.
 ڷ,൱ڶԴBCķ,ʸPCH=PAB+PAC,൱ڻԪķ2.
 ڷ,൱ڶԽDͶԴ洢Eķ,ҽǡ״̬6.
3.2ֻ洢
(1) ֻ洢Eͼ7(b)ʾ,ķԪʽ,ʽPSEΪ

(2) ɽM״̬ͼ3״̬,൱ڻԪķ2,,൱ڻԪķ3.
3.3Ωһ;
ҽΪ״̬ͼGSһʱ,ڳʼ㵽ս佨һΩһ·.ڻԪķ״̬ͼGSһԵжϼ֤ǰ,ﲻ׸.
4ķӦ
ǰԻԪķ3ʽ(4״̬),ϸ״̬͹洢״̬.ŵ,ҽķGSһʱ,ֻһ·,Աͻ.,ķأ
(1) ԴķʵĸʷҪ
ýĳԴͳָһʱ,ôýԴΨһͨ·,Դڹ״̬.AϸΪPAB,PAC,...,PAM,AԼ˽д洢ĸΪPAA,PAA+PAB+...PAM=PAj=1.Ը״̬ķֵĸҲΪPAA,PAB,...,PAM,,A˽д洢ͳķĸΪ1-PAA,ABֵĸΪ1-PAB,...,AMĸΪ1-PAM,,AԸԴƽͻĸΪ
(11) 
PAĸʵǽAÿһƽӳʱ,Խÿһ󼰷ʱTΪ
T=n.Ti+Ti+,(12) 
ʽTiΪʽÿ״̬Ĳʱ;Ϊʱ;TiΪƽӳʱ,ζÿһ
ϸԴĸķֵΪ
mʱ,
=Ti(n+1)+.(13) 
(2) ԴŶӼʱ
һ,ϸԴ,æ,Ŷ.ÿһԴ˵,ŶӺͷʱΪ
C=,(14) 
ʽЦΪϸĳԴƽʱ;MΪ϶ԸԴĽ.
(3) ķ
Ϊʹķõͨ״̬,нϿٶ,Ҫ
ԣ,(15) 

Ti(n+1)-.(16) 
ʽ(16)ɼ,ķܹõԭķĲʱԶԶСʵӷʱ,Ҳ˵,ķʶʱԺԲ,ͬʱܱʳͻ.
5
3Ԫķʽ˽ṹи״̬.״̬õķһʱ,Խһ·,·Ψһ·.ΪñͨŶģʽиٶ,ϵͳѭTi(n+1)-Ĺ.
ʽԷ˼·ѡ㷨.߽ͨƼӦͨʽ,ԱΪ÷ʵӦṩɿ.
оõʡȻѧ.
߽ܣ֮˶,1942,,ҪоΪרϵͳ,,֧ϵͳ.
,Ů,1962,,ҪоΪ˹,о.
ͨѶϵˣ֮˶, 150008,ѧӦϵ
ߵλ֮˶ѧӦϵ150008
ο
1ݴʲķ..:ѧ,1984(TANenbaum A S. Computer Network. Xi'an: Shanxi Science and Technology Publishing House, 1984)
2ݸ.ģʽʶӦ.:ѧ,1983(Fu Jing-sun. Pattern Recognize and Application. Beijing: Science Press, 1983)
3Feler W. An introduction to probability theory and its application. Computer Network, 1989,14(4):5267
4MarSan M A. MARKOV models for multiple bus multiprocessor system. IEEE Transactions on Computers, 1982,C.31(3):2527
5ݹ˹Ⱥ.(3).Ͼ:տѧ,1987(Gu Guan-qun. Computer Network(3rd ed). Nanjing: Jiangsu Science and Technology Publishing House, 1987)
6Ҹ.ϵͳNDPIS.о뷢չ,1988,25(3):35(Xu Jia-fu. NDPIS design of parallel inference system. Computer Research and Development, 1988,25(3):35)
1997-11-11յԭ,1998-02-11յ޸ĸ 
