软件学报
JOURNAL OF SOFTWARE
1999年 第2期 No.2 1999



用于描述网络拓扑的形式语言的研究*
于之硕　杨　静
　　摘要　论述了应用随机线性文法及产生式描述计算机网络拓扑结构的方法.在该形式语言的描述中,设置了3个基元状态,通过对基元状态及各种状态规律的分析,准确地描述了网络中结点间通信及共享存储器的状态.同时,证明了用此方法在某种条件下从初始结点到终了结点间可以建立惟一的访问路径,并能避免冲突.此方法对计算机网络结点访问/冲突避免的研究具有一定的参考价值.
　　关键词　概率矩阵,文法,基元,网络.
　　中图法分类号　TP301
Research of a Formal Language for Describingomputer Network Topology 
YU Zhi-shou　YANG Jing
　　Abstract　　Being 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 words　Probability matrix, grammar, base element, network.
　　对计算机网络拓扑结构的设计,容量分配算法通常都采取基于图论及割集的方法.本文所提出的网络信息流量计算和分配方法是基于概率量度.即一种语言及其文法,通过严格的定义和文法产生式,使网络抽象为一种语言表达式,再应用前人所推导出来的语言性质精确地计算出概率量度分配值,可使所要求的计算机网络中两个结点机之间建立唯一最佳的通信路径.为使计算机网络符合本文描述的语言方法,特假设如下：
　　(1) 计算机网络的完全图如图1［1］所示.其中每一结点都表示一个带有存储器的计算机用户.

图1　计算机网络完全图
　　(2) 计算机网络中各结点上有3种状态：① 处理机申请某结点资源；② 因资源“忙”而处于等待；③ 得到资源后或是读或是写.
　　(3) 设网上有m个结点,对K点来说,它对网上其他结点的访问概率Pk应是
Pk=Pki,　　　　　　　　　　　　　　　　　　(1) 
其中Pkk表示对本结点机的存储器访问.为分析方便,可把Pk分成P′k,P″k,即
Pk=P′k+P″k.　　　　　　　　　　　　　　　　　(2) 
其中P′k为一类的访问概率和,且
P′k=Pki　　　i={1,2,...,q}.　　　　　　　　　　　(3) 
P″k为另一类的访问概率和,且
P″k=Pki　　　i={q+1,q+2,...,n}.　　　　　　　　　　(4) 
　　(4) 网上每一结点随机请求资源符合马尔科夫模式.
　　(5) 从概率量度分配来说,对于星形网、环形网及总线网仅是网状网的一种特殊情况.设网状网的概率分配如以下矩阵(与图1等价).

　　而星形、环形及总线形网的概率分配矩阵如图2所示［1］.由图2可见,在具有相同结点数目的情况下,矩阵的格式都为6×6,所不同的是某些概率为零.总线网也可求出概率分配矩阵.

　　　　　　　　　　
(a)星形网及概率矩阵　　　　　　　　(b)星形网及概率矩阵
图2　星形、环形网及概率矩阵
1　描述网络的形式语言模式
1.1　随机语言模式分类
　　一般来说,随机描述文法有4种类型及1个派生型,即：0型——无限制文法；1型——上下文有关文法；2型——上下文无关文法；3型——有限状态文法；派生型——随机线性文法.
　　各种文法可以描述各种随机事件,其随机描述语言的短语语法结构可以定义为一个四元式［2］,即
Gs=(VN,VT,PS,S),　　　　　　　　　　　　　　　(5) 
其中VN为非终止符；VT为终止符；PS为随机产生式有限集合；S为起始符,S∈VN.
　　本文所引用的随机线性文法的结构GS与式(5)相同,但VN={A1...AK},S=A1,VT={U,V,Ur},而PS为Ai→UAjV,Ai→Ur,且对于每个Aj∈VN.定义等价类CAi的通用表达式为
CAi={PS的所有左端为Ai的产生式},
即
PS=CAi.　　　　　　　　　　　　　　　　(6) 
　　若对具体PS的产生式为Ai→UAjV,Ai→Ur来说,设Ai→UAjV的概率为Pij,设Ai→Ur的概率为Pir.对于第i点的产生式概率为
PS=Pij+Pir.　　　　　　　　　　　　　　(7) 
1.2　线性随机文法的一致性
　　由于随机文法一致性的定义为
P（x)=1,
(8) 
所以,线性随机文法一致性的定义又可为
Pij+Pir=1.　　　　　　　　　　　　　　　(9) 
　　上式的物理意义是产生过程为具有(K+1)个对应于VNU{T}状态的有限个马尔科夫过程［2］.若GS是一致的,则状态T将对应于一个吸收状态,而所有其他状态将都对应于过渡状态.同时,对于产生式Ai→UAjV,则在Ai和Aj之间产生一条路径,在Ai和Ur之间也产生一条路径.对任何结点Ai,每次仅能用上述两个产生式之一,即某时刻从Ai开始生成的状态仅有一个,若对于导出式S→x,相对于初始结点S到终点有一条路径.其更重要的意义在于,若GS是一致的,则从初始结点到各终点Ur∈VT的概率必须为1［3,4］.本文利用这些性质把网络上所经过的各点的状态和产生的文法一一对应起来,如果GS是一致的,则每一瞬间保证有一对处理机建立了联接,这样就会防止冲突.
　　在文献［2］中提到了判定随机线性文法GS一致的条件是
lim m1,k+1(n)=1,　　　　　　　　　　　　　　(10) 
而［mij(n)］=Mn=M1×M2×...×Mn,式中M为网络概率分配矩阵.所以,m1,k+1(n)表示M连乘N次后的矩阵中第1行的最后一个元素,即连乘后矩阵中最左上角的元素.lim m1,k+1(n)=1［3］表示起始结点到终了各结点的概率为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.5及P3=0.6时GS是一致的.如果随机线性文法概率矩阵同上,但其他条件不同,当n→∞时,有lim m1,4(n)≠1,则说明随机线性文法也存在不一致.
2　随机线性文法表示的三基元网络状态
　　根据本文概述中的假设,网络上各结点可处于“申请资源”、“忙”和“读或写”三种状态之一,而其他状态都可由这3种状态组合而成.本文选一种文法,描述一结点对两个资源的请求,而任何结点对两个以上资源的请求总看作是对两类资源的请求,则概率分配符合PK=P′K+P″K.本文描述一个结点对两种资源的请求文法及表示的状态为基元状态,将推出的3种基元状态用以描述及组合网上各结点的一切状态［5］.
2.1　基元文法1
　　本状态的文法和产生式为上例中GS和PS,该文法表示的状态如图3所示.图3表明,结点机S可以对资源A或B申请,其概率分别为P1或1-P1,对B资源来说如果忙,由S在B等待.等待的概率是1-P3,若B早已准备好,由对B资源输出（或“写”,用“00”表示）.对A资源来说,从S对它请求以后,可有两种选择：一是通过A资源输入（用“1”表示,也可认为是“读”）；另一个是通过A资源对B资源请求,它的概率是P2.

图3　基于文法GS产生式PS的状态图
2.2　基元文法2
　　本状态的文法GS2=(VN,VT,PS2,S）.PS2为产生式,且有:

　　对应于GS2及PS2的状态图如图4所示.图4表明,结点机S可对A及B发生请求,而每一资源都可单独输入或输出.

图4　对应GS2及产生式PS2的状态图
2.3　基元文法3
　　本状态的文法是GS3,且GS3=(VN,VT,PS3,s).PS3产生式为:

　　如图5所示,本状态相当于A与B都是“读”,它们的概率分别是P2和P3；而在S对A或对B请求时,可能遇到A与B都“忙”,则它们分别等待,其概率为1-P2或1-P3.而GS4=(VN,VT,PS4,S）是基元文法4,但应归入到基元文法3中.因为GS4描述了结点机S对A与B发生请求时,置A与B处于“写”状态.

图5　对应GS3及产生式PS3的状态图
2.4　基元文法所描述状态的合成
　　如图6所示,对A资源除等待外还有一个分配概率P2,主要对A资源既要读(概率1-P4),又要写(概率P4).就等于是把文法3和文法2修改后合成.其文法为GS5=(VN,VT,PS5,S),其产生式为GS5：


图6　合成状态模式
3　应用3种基元文法描述整个网络
　　在文章的开始部分,假设图1中A,B,C,D是结点机,E和F是存储器,且设E仅允许读,如图7所示.

(a)结点机A状态图　　　　　　　　　　(b)只读存储器E状态图
图7　对图1的网络拓朴结构的描述
3.1　对结点机的描述
　　(1) 对结点机A的描述如图7（a)所示,其文法同以前各状态定义,但产生式PSA为:

　　(2) 对A的状态图可以看作3个子状态图:
　　① 对方框Ⅰ,其中S→A→1及S→A→0,相当于对私有存储器访问,其概率为PAA；右枝相当于对网上其他各点访问,其概度P′AA=PAB+PAC+PAE+PAF,符合假设,方框Ⅰ相当于基元文法2.
　　② 对于方框ⅠⅠ,相当于对处理机B和C的访问,访问概率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,结点机A碰不到B出现的概率为1-PAB,...,结点机A请求碰不到结点机M的概率为1-PAM,所以,结点机A对各资源请求平均不冲突的概率为
　(11) 
　　P′A碰不到的概率实际上是结点机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)
　［3］Feler W. An introduction to probability theory and its application. Computer Network, 1989,14(4):52～67
　［4］MarSan M A. MARKOV models for multiple bus multiprocessor system. IEEE Transactions on Computers, 1982,C.31(3):25～27
　［5］顾冠群.计算机网(第3版).南京:江苏科学技术出版社,1987(Gu Guan-qun. Computer Network(3rd ed). Nanjing: Jiangsu Science and Technology Publishing House, 1987)
　［6］徐家福.并行推理系统NDPIS的设计.计算机研究与发展,1988,25(3):3～5(Xu Jia-fu. NDPIS design of parallel inference system. Computer Research and Development, 1988,25(3):3～5)
本文1997-11-11收到原稿,1998-02-11收到修改稿 
