1992年，g43g，第1期 重庆邮电学院学报 1992，Vol·4，No—l
Jourr~l of C]1ongqing Institute of Posts and Telccommunications
线路交换的RI=T互连网络的性能分析
(计算机系)
【囊薹】 本文讨论 了两种不同的冲突解决方法一一 回退 法 和 保 持击。性
能分析的模型是基于一种更实际的假设，定量分析的参数是平均请求服务
时i爵I，分析的结论得到了模拟结果的验证，即回退法比保持法好。保特法
在高请求率的情况下，要多占册结点周期。
关■词 阻塞，连通，转移概率，状态
。 弓I 言
网络 互芝国络 ，J学
本文研究e1)中提出的RFT互连网络在线路变换时的性能，至于在报文变换时的性能将
另文讨论。
以前的性能评估模型通常是基于这种不实际的假设； 当一个请求被阻塞时，便完全放弃
而由发送者产生一个独立的请求代替之。虽然这种假设有助于简化理论模型，但这种简化结
果是与预浏的网络性能往往不一致的。另外，在两种可供选择的方法中，如何去选一种能较
好处理阻塞的方法，也没有定量的比较参数。
本文试图解决上述问题。我们选用的两种方法是保持法和 回退法。在保持法中，一个被
阻塞请求总是保留巳建立的部分路径，并且等待被占通路的释放。在回退法中，一个被艇拳
请求是释放巳建立的部分路径并回退到网络的入 口处重新开始建立路径。
1 RFT互连网络的操作
一 个有8个发送者和8个接收者的lu'T互连网络如图1所示，在发送者和 接收者之间的一
条线路连接称为是一条路径，3×3开关如图2所示。如果一个开关的某一输 出 端还没有被其
它请求占用，则一个请求可以从开关的一输入端与该输出端相连。当开关连接一输入端到一
输出端时，则称该请求通过了。在开关中，一 输 入 端和一输出嫱的一条路径就称为开关连
通。当一个请求到达网络的第i级的开关输入端，但没有通过该开关睡垂，其IJ弥这个芾乖是在
日期 1 9"一tl一1々
t ●
P■■■IF琶 5 ：
维普资讯 d
1 哥哥2卒，直~4卷，第1期 重庆部电学院学报 1992, ,
Jo出血I of Chongqing Instilut舍。f Posts and Telecommunications
.,.
7ii
嗡1马g』萄萨
E‘
•••••
'E
线路交换的RFT互连同缝的幢能分析
/;3'" 7乒 卢亚平 』ff21多
{计算机系〉
5
Z费量.1 本文讨论了两种不同的冲突解决方法一一在幸运法和保持法。拉
能分析约模型是基于一种史实际传假设，定量分析约参数是平均请求量在务
砖间，分荷枪结论得到了模拟结果约栓证， !lP!晋退法院保持海好。保持法
在高请求...豹情况下，要声占到结点周巍。
美幢稠
it华υi穹绿 豆芝!写给 4、主F言t
o 弓|
占百
事
1
本文研究(1)中提出的 RFT 互连网络在线路交换峙的性能，至于在报文交换财的性能将
另文讨论a
VJ前的性能评估模型通常是基于这种不实际灼假设事当一个请求被应塞时，便完全放弃
而出发送者产生 个独立约请求代替之.虽然这种假设有助于简化理论模型，但这种痛化结
果是与预测的网络性能往往不一致约.另外，在两种可供选择的方法中，如何去造一种能较
好处理阻塞的方法，也没有定量的比较参数.
本文试图解决上述问题。我们选用的两种方法是保持法和国退法.在保持法牢，→个被
阻塞请求总是保留巳建立灼部分路径，并且等待被占通路豹荐主主.在国逗诠中，一个被m塞
请求是释放巳建立剖部分~径并应退到网络的入口处重新开始建立路径。
1 RFT互连网络的操作
一个有8个发送者和8个接收者的RFT互连网络如图1所示，在发送者布接收者之阔的一
条线路连接称为是一条路经 J 3X3开关如图2所示.如果一个开关部某一输出端还没有被其
它请求占瘤， Ji!IJ-个需求百五以从开关前一输入端与该输出端怨连。当开关连接一输入端到一
输出端时， jJlJ称该请求通过了。在开关中，一输入端和一事量也端份一条路径就称为开关连
遥.当一个请求到这网络的第1级的开关输入畴，但没有通过该开关碌，则称这个号摩尔建在
本文收要llß期 1 罪'1-l1-1 号
、
64 重庆邮 电学院学报 1 992丰
第i级之中。
通常，到达开关的一个请求存在以下五种可能的状态，如图2．
在圈 2的 (d)和 (e)状态中，分别有两个和三个请求在同一周期到达。
两个请求在同一周期到达，每个请求要占用某一输出端的概率是1／3，两个请求占用同一
输出端的概率z／9，删 ，
Pf通过}；1一P{两／卜请求 占用同一输出端) ：
= 一
8
9
3个请求在同 一 周期到达，
一 输出端 的 概率t／3，3个
请求占用同一输出端的概率
1／2 7，3个请求中有两个 请
求要求同一输出端的概率是
c 1
r = {．
Pf通 过)=l—P{3个
请求中有两个请求占用同一
输 出 端)--P{3个请 求占用
同一输出端
； 1 —
1
一 ． ．
1
3 27
： 1 一 旦一 l
27 27
l7
、
一 日．多个请求申请 占用
同一输出端时，总让一个请
求通过，而其余的请求均被
阻塞。
这类冲突中究竟应让谁
通过是由已设置的开关优先
权 (顺序是上、中，下)确
定的，而不是随机选择 。
、
， 当发送者产生；个数据
传送的请求时， 由于直接与
两个开关相连，规定发送者
每个请求要是用某一输}fj端的概 率是1／3，两个请求占用同
发送 者
接 袁
罔l 8×8RFT~毒网许
●■■■■：
维普资讯
64 重庆部电学院学报 1992年
第i级之中 b
运常，到这开关的-个请求存在以下五种可能的状态，主E屈2.
在图 2 的〈郎和 (e) 状态中，分军事有两个和三个请求在同一周其是到达。
两个请求在同一海期到达，每个请求要占用幸在一能出端的街率是1/3，两个请求占用同一
输出端的概率1舟. !I!II
P{逐过}=-l-P{两个请求占用罔-输出端}
E1-i
s
s
31、请求在民二月期到达，
一输出端的概率1/3， 3-1、
请求占用罚一输出端灼蠕J号1
1/27. 3个请求中有两个请
求要求同-输出榻的概率是
C巳 χJ__ 1
;\^ 9 -3-
P{透过) =1-P{3 个
请求平有两个请求占用同
fJltlU 端}-P{3个请求占苟
同一输出端上
1 1
=一晶 3 27
-‘雪 1---'.---二
17
27
67 27
-E!_多个清求串清占用
同一输出端碍，总让一个请
求透过，而其余的请求均被
阻塞。
这类冲突中究竟应让谁
通过是由已设置的开关优先
权〈顺序是上，中、下〉购
定的. jJjj不是隧抗选择 a
当发送者产生品个数据
传送的请求时，白于直接与
两个开关祁连p 规定发送者
每个清求要是用某一输出端的夜率是1/3. 两个请求占用同
在送在
8
G
2
勺
盆，
生
挂在在
.
,
同 3X&RFT1J:连网络
民 b
，、
第 1期 邓亚平 线路 费_揍的RFr至连 同络的·I生能分析 65
(a)无其它请求到达输A端
Pf通过}一1 ．
(b)另有一请求巳建立连通 P{通过 号 (c)已有两个请求建立连通
P{通过 }=
(d)两个请求在同一周期到达 (e)三十请求在同一周期到达
P{通过} 言 P{通过}=
图2 在一个开关中建立一种连通的概率
随机地选择仅向一个开关传送该请求。由于文章篇幅受限，不讨论同时向两个开关传送请求
的情况。每个请求以图 2中所表示的五种概率之一通过网络的各级。本文用N表 示 发 送者
(接收者)的数量，当一个请 求 通过n级 (n=logiN)，则在发送者和接收者之间就 建立 了一
条路径。
在 回退法中，对一个请求产生阻塞的开关沿着已建立的部分路径回送给发送者一个释放
信号。这条部分路径在本周期结束时就不再存在。这个被阻塞请求退回到网络的 0级重新开
始传送，直到一条路径建立为止。在保持法中，被阻塞请求保留已建立的部分路径并继续尝
试在同级的连通。回退法的特点是尽量减少网络中请求的拥挤程度，可以增加连通接收者时
通过的概率。但是若一请求已建立部分路径又被迫释放而退回去，这又是一种极大的浪费。
而保持法的特点是可以节省这种浪费，却又往往使得请求被阻塞的概率会增大。
2 基本的假设和一般模型
2．1 分析■量的蠢设
网络分析模型是基于下列基本的假设
曩设‘1) 当在发送者和接收者之间建立一条路径后，该路径作为一次数据传送的固定
周期数。这种数据传送时间记为 d 。另一方面，在一个请求完成和一个 新 的请求产生之间
的时间是变量。请求的产生率用“r 表示。 请求产生率定义为当处理机为 空 闲时，发送者在
每个周期产生一个新的请求的概率。
曩设(2) 一个请求要到达的目的处理机是以等概率分布在N仝接收者之中的。
德设(3) 如有多个请求在同一周期到达同一开关且又要事同一输出端时，刚随机选择
维普资讯
第 1 期 1]1亚平 线路交换的RFr至连网络的性能分析 65
、\飞.\\气\
\\、、、飞、
。---
飞飞
、飞
气飞 ---」-一.
。---
。---
但〉无其它请求到达输入端 。〉另有一请求已建立遥远 (c) 已有两个请求建立连通
P{通过 1-1 P{通过}=3 P{通过}=t
D
。-
(d) 两个请求在黑-jì号黯重IJ达
Pl 透过?国:一
(e) 三个请求在同一周理到达
P{通过}=去
医2 在一小开关中建立一种这通曲概率
随机地选择仅向一个开关传送该请求e 由于文章篇幅受限，不讨论同时向两个开关传送需求
的情况。每个请求以图 2 中所表示的五种概率之一通过网络的各级e 本文用N表示衷送者
〈接收看〉的数量，当一个请求遥过在级机=log.到)，则在发送者和接收者之间就建立了一
条路径.
在回退法布，对一个请求产生阻塞的开关沿着已建立的部分路径理送给发送者一个释放
信号。这条部分路径在本建颊结束时就不再存在.这个被瞿塞请求退IElJlJ网络的 G 级重新开
始传送，直到-条路经建立为止。在保持给中，被阻塞请求保留已建立的部分路径并继续尝
试在同级灼连通.因遥法的特点是尽量减少网络申请求的损挤程度，可以增加连通接收看时
通过灼概率。但是若一请求已建立部分路径又被迫释放而适应去，这又是一种极大的浪费。
而保持法的特点是可以节省这种浪费，却又往往使得请求被阻塞灼概率会增大。
2 基本的假设和一般模型
分精篝擅疆军假载
网络分析模型是基于下列基本的假设E
辍银(1) 当在发送者和接放者之间建立一条路径后，该路径作为一次数据传送的固定
周颊数。这种数据传送对民记为 "d"。另一方国，在一个请求完成和一个新的请求产生之间
的时间是变量。请求的产生率用吁'表示。请求产生率定义为当处理机为空闲时，发送者在
每个周期产生一个新的请求的概率。
.键(.2) 一个请求要到达的汩的处理机z是以等概率分布袤Nl'接收者之中的e
.设{。 如有多个请求在同-周期到达同一开关且又要求同一输出端时，剧痛机选择
。
， 重虎邮电学院学报 ’ l992年
一 请求通过，其余请求被阻塞。
在分析模型中发送者的状态以及发送者产生的请求在网络中各级所处的状态，均用下列
符号表示t
A。0=o，1，I．·，n)l在i级的请求 ，它还没有被阻塞，Bl(i=O，1，I．·，n)I在i级 的请求，
它已经被阻塞j c| 已经建立一条路径并且这条路径正在传送数据。I：发 送 者 产 生的请求
已完成且无新的请求产生。
以上只是基本的状态定义，当需要表示被阻塞请求和阻塞请求(阻塞过一个请求的请求)
之间的关系时，再将Bi状态细分。
从sI状态改变到s』状态的转移概率记为P(S，l sI}。一个处于s·状态的 请 求的绝对概率
记为P‘s．)。为使状态转移图清晰起见，在表示分析模型的状态转移 中，从一个状态转到它
自身的状态转移就没有在图上标出a
2．2一般■垂
由于分析问题的一般原则是先简单后复杂，所以在前面的假设中 再 补 充 一 个假 设 条
件。
操设( 如果一请求在建立路径的过程中被阻塞，则就完全放弃此请求，而产生一个
独立的请求来代替它。
在一般模型的状态转移图中不存在Bi状态，如图3．
图3 一般模型的状态转移图
显然有； P I Iq = (1一r)／d
P{Aol C}--r／d
P{A口II} (1)
下面求一个请求在第i级的转移概率。一个请求要通过网络的第i级 共有五种不同的方
式，它的通过取决于网络中其它请求的状态和请求在特定状态下的概率。而要出现五种不同
状态的概率分别由下列各式给出：
P(图2的 (d)状态)=1一P(c)一∑P(A，) ． 。
P{图2的( 状态)：}【善． P(A )+P(c)J
Pt图2的(c)状态}={【墨+。P(At)+P(c)] L -，+1 J
P(图2的 (d)状鸯)一号P(^}) 。 ’
’
}
维普资讯
<
66 F 重庆邮电学院学在 1992'"
一请求通过，其余请求被墨塞.
在分拆模型中发送者的状态以及发送者产生的请求在网络中各级所处的状态，均照下911
符号表示z
A ，(i=司t 1 "... ，n)，在i级的需求，它还没有被医塞 J B. (i=哥. 1 ,… .n) ，在f级的请求，
它已经被阻塞，c，已经建立一条路径并且这条路径正在传送数据o 1: 发送者产生的请求
已完成立无新约请求产生a
以上只是基本精状态定义，当需要表示被应塞请求和应塞请求〈瘟塞过一个请求约素求〉
之汩的关系时，再将Bi状态细分，
从S，状态改变到S;状态的转移概率记为P(S;/ S，}.一个处于玩状态灼请求的绝对提率
-记为P(S，).为使状态转移黯清渐起觅，在表示分析模型的状态转移中，从一个状态转到忘
自身的状态转移就没有在窗上标出。
-戴羹量
由于分析问题的→盖章原则是先商单后复杂，所以在前窑的假设中再补充一个假设条
吾噩匾'幸宙
t枣王
件。
假设(4) 如果一请求在建立路径的过程中被阻塞，刻就完全放弃此请求，而产生一个
独立的请求来代替它.
在一般模型的状态转移圈中不存在四状态，主E图 3.
空闲 。级 2 级 2 革E
11
R
连遭
墨写2 一毅模型的状态转移图
显然有 P(IIC}= (l -r}/d
P{A,j C}=r/d
P( I}居r {1}
下室主求一个请求在第1级的转移概率a 一个请求要通过网络的第 1级共有五种不同的方
式，它的通过取决于网络中其它请求的状态和请求在特定状态下的绿率.而要出现五种不再
状态的概率分别应下列~式绘出g
P{医2的〈吟状态}=l-P (C}-Ep 件j)
P{图础。〉状态}=号I.~"P(Al)+P向
P{理2的。〉状态}=tiEY向+P叫
P{医2的 (á) 状态}=号F叫〉
.:川
比
再
口
第1期 郭亚平 线路交换的RpT互连同络的性能分析 67
P{图2的 (e)状态}= p(A．) (2)
一 个通过所在级失败的请求会从原来的状态转移到 An状态。一个请求 只要转移到A”
状态就是转移到c状态，如图3．因此可以由下式计算从A 状态到A 状态的转移概率。
^ ^
P{A lA1)盅【1州c1--⋯Y~．P(A，)]+；×乳 。P(A )】+
{×÷[ 量。P(A )+P(c)】十百8×导P(A )+ ×÷P(AJ)
=l一 (Aj)一告，-∑i+ P(Aj)---~P(c) 1)
P(ADf Ai)=1-P(Ai+ll AI』
一 16p"Aj)+詈，车 P(A c) (3．2)
用适当的数值计算方法，整个分析模型的所有转移概率均可从方程式 (1)到 (3)中求
得。
3 保持模型
在这种模型中，一个被阻塞请求保留已建立的部分路径。本 模 型 只 采 用 假设 (1)蜘
(3)。这种模型的状态转移图如图4．
图4 保持模型的状态转移图
如果一个请求被另一个请求阻塞时，这个在i级的请求就进入B；状态。称前者为被阻裹
请求，后者为阻塞请求。由于从Bj状态转移到An 状态与阻塞请求的级数有关，故将Bj状态
细分为B 状 态，意思 是一十在i级的请求 已被阻塞，而阻塞请求当前在J级，这里j>i 与前
面的一般模型一样，显然方程式 (1)在此模型中亦成立。
从A 状态到A +t状态的转移概率与前面的一般模型娄似，只要用 A‘和B 代替原来的A
就可以了。转移不成功时，被阻塞请求会从A 改变成Bi状态，这 里用J表示阻塞请求所在的
级数。
P(A⋯l A )=1一面16[P(A．)+P( ) --詈昌+。[P A^?+P<B^ 卜詈P(c)
●— 沼 螂 ；
维普资讯
,
i·=i
吨'在军
L、
agi
à
a
L
第 1 点 ~亚乎 线路交换的RFr互迄网络的位能分析 &1
P{图 Z的创状态}=;P内} (2)
-个通过所在级失败的请求会从原来的状态转移到 A. 状态。一个请求只要转移到A.=+J
状态就是转移到C状态，主B因3. 因此可以出下式计算从人状态到AS+l状态部转移概率。
P{A' +J I A ,} =1" r-P(C) - Ep(A ,) 1+: x 主 r E P(A, )+P(C) 1+ ι ，=， ...--" J I 3'~ 3l J =:-: , F' - "I -'J
1 1 r '<"""' _. • _ 8 2 _ . . 17 1 3 X 丁i-L主户A， )+P(C) 1+百X言P(A，) +庐丁于P( A， )
主6_ .. 4
'"
_ 4
= 1 -;;P(A，) 一百 γP(A， )一二叭。81 , 27+ 主 (3. 1)
P{ A ,}= l-P{A, ..I A ,}
16_. • .. 4 ~丐
=;:;-P(A, )+主?二 P(A，)+ ~p(C) 81'--."-'91-' 争豆
'
(3. z)
用适当她数值计算方法，整个分析模型的所有转移概与均司从方程式。〉到〈份中求
得e
3 保持模型
在这种模型中个被温室请求保留已建立的部分路径。本模型只采用假设。〉剑
。}。这种模型的状态转移留如国4.
004 保持模型德状态转移医
如果一个请求被另一个请求阻塞时，这个在i级的请求就进入B，状态。我:前者为被罐塞
请求，后者为阻塞请求。由于从Bi伏态转移到Ai+J.状态与阻塞请求的级数有关，故将Bj状态
细分为8:状态，意思是-个在1级的请求已被阻塞，雨思塞造求当前在i级，这里i>丸与前
面的一般模型一样，昼牵挂方程式(1)在此模型中亦或立。
从A，状态31I}A，..状态的转移概率与前面豹一般模型类叙，只要沼 A，和B，代替原来鹤A，
就丐I!J.了。转移不成功时，被阻塞请求会从人改变成BI状态，这里用j 表示阻塞请求所在的
级数。
16r_.... 4" r_..... P{ A， }=l 一辰lp山川P(B，) 1-豆豆+， t P从二十P(8ρ1- ;P(C)
68
～
童庆邮电学院学粗 1992~-
I [P(^．)--~P(B )]
-
q A,ffi Ir i4[P(^j)+ )]
(c) ‘
，= l
i<j≤n
=“+1 (4)
当一个请求处于B 状态时，在相应的阻塞请求完成数据传送之前，它 不 可能通过i级。
由于阻塞请求总是越来越接近目的地，被阻塞请求 (B；)的状态随j的 改变而发生相应的改
变。又 由 阻塞请求以后也会处于Ai状态或Bj状态，为了计算该阻塞请求的通过概率，定义
处于翰}的一个请求能通过此级到j+l级的概率，由下式表示：
m，一P{在j级的请求在同一周期内通过此级)
一 ! 生!! —— P(A~)q-P(Bi) O≤，≤
(5)
至此，可以用通过概率nl，米表示B{状态的转移概率；
当阻塞请求处于连通状态时，它将以I／d的概率完成这次数据传输，而被 阻塞请求则以
此概率通过该级。如果此阻塞请求还没有建立一条路径，则被阻塞请求不会通过此级。
当一个请求处于B{(j>i)状态时，阻塞请求以 的概率通过所在级，而被阻塞请求的
状态也发生相应的改变。
当一个请求处于B 状态时，若阻塞请求已在前一个周期通过了i级，则可以在 当前周期
通过下一级。因此，状态转移概率接下式计算；
r1／d j=n+1
P{A．+tI墨}) { (6．1)
o ，≤
， f j f<，≤”
P{B：”I卫})；{‘ (6．2)
、 、 l1·m =f
f0 <j≤n
P{B； 。l B；)={ (6．3)
【／Y~i+i j=
肌方程式 (4)到 (6)，再加上 (1)式，便给出了计算所有状态转移时的概率公式。对 {二
此模型只要给出一组合理的每种状态的初值，整个分析模型便可求解。
4 回退模塑
，
在这种模型中，被阻塞请求释放它已建立的部分路径，并且回退到网络的 0级，从头开
始·回退模型与保持模型一样，也是建立在假设 (1)到 (3)的基础上，同时迹满足下面的假
设。 ，
曩设(5)数据传送时间总是比在发送者和接收者之间建立一条路径的最短时间要长。
回退模型的状态转移图如图5．
一 旦一个请求在j缎被阻塞，它将改变到B。．，状态。B¨ 状态中的第一个下标i表示请求
维普资讯
在S 重庆部也学反学.f1
ZiF向M向)]
P{B.'I A ,= f : [P(AjHP向]
itpfC>
i=i
i<i<n
Î="+l
11192年
(4)
当一个请求处于B，状态慰，在相应的思塞请求完成数据传送之前，它不可能通过i级e
由于阻塞请求总是越来越接近吕的地，被阻塞请求恼。的状态黯jB甘改变而发生相应的改
变。又溢于短塞请求以后也会处于Ai状态或Bi状态，为了计算该阻塞请求吉它远过概率，定义
处于j绥的一个请求能运过此级主主Jj十 l绥的概率，温下式表示E
隅i=P{在1级梢请求在同一周织内通过此级}
P(Aj..)
P(互万平P(Bj} #运主 f每三n (5 )
至此.可以用通过概率血，米表示Bi状态的转移概率军
当阻塞请求处于连远状态时，它将以l/d的概率完成这次数据传输，而被阻塞请求到'J 以
JH;概率逐过该缀。如果JH;阻塞请求还没有建立一条路径. P\IJ 被阻塞请求不会速过JH;级，
当二个请求处子B! O>i) 状态时，阻塞请求以m;盘古概率通过所在级，而被应塞请求的
状态也发生相应的改变e
当一个请求处于Bj状态对，若阻塞请求已在前一个周颜通过了 i级，到IJ 可以在当前周期
透过下一级e 因此，状态转移概率接下式计算2
1fd ;="+1
P{A...I aH= { (6. 1)
e 1ζn
i<fζn
()
、 Î=i
i<iζn
(岳 .3)
Mj+t ;=i
从1方程式 (4)歪ø (的，再加上(1)式，使绘出了计算所有状态转移财的概率公式。对于
此模型只要给出一组合理的每种状态的初筐，整个分析模型便可求撞事e
4 远远模整
在这种模型中，被阻塞请求荐放它已建立的部分路径，并且因逼到网络的 8 缀，从头开
始. n主运模型与保持模型一样，也是建立在假设(1)重IJ (的的基础上，同时还满足下面的假
设。
量'能(s)数据传送时阁总是比在发送者和接收者之间建立→条路径的最短时饲要长e
离退模型均状态转移圈如图5.
→旦→个请求在i续被阻塞，它将改变型IJB' ， j状惑o ß.. i状态中的第→个下标i表示请求
.~
马
装
觚
毡
马
第1期 邓亚平 线路吏族的R T互连同络的性能分析 60
图5 回避模型的状态转移图
所在的当前级数，而第二个下标j表示该请求最近的一终被阻塞所在的级数。 请求从。级通过
到
．
1级，依次下去，直到它到达j级，当然必须在此期间没有被其它请求阻塞。如果 阻塞请求在
网络中一直未被其它请求阻塞，而对应的被阻塞请求在j级又被同一阻塞请求 再 次 阻塞，则
将BI-J状态细分为B；． 状态。它的意思是该请求当前在j级，而它最近一次被 阻塞是在j级，
此时阻塞请求是在k级。
为简l化回退模型的数学表达式，引八下列符号t
sf=P(一个请求在f级，这里O≤ ≤ )
： P(Af)+ 哪 I，】) (7)
～ 与_般攀掣和保持模型一样，等式 (1)所表示的转移概率对于回退模型依然成立。下面
分别不同情况求剩下的转移概率。
(1)当前状态是A
一 个处于A 状态的请求可能以 2中5种不同的方式通过该级。每种状态的概率如下：
P{图2的(口)状态)=1一P(c)一 ∑ s，
P{图2的(b)状态)= 2 ∑ s +P(c)1
L i- J+1 J
。的(c)状态)=；[，暑I s，+P(c)] ’ · L⋯l J
维普资讯 -
6G
dva-z'
飞
Hd/
E-n-rAh 句，‘、
、
2'
飞
tp
叫"以们
jidu'2
飞
MJ
气，啡
Jat/\J
产
1时
~FKVz{h~ιι)
，r
阻飞
/fl\/'Ai\
，f
飞入
jia-al
线路支换的Rl'IT王主主同格的性能分析邓亚平第 u朗
马芸制盼毡亘
一--~
E退摸壁的状态转移图图5
所在§甘当前级数，丽第二个下标3表示该洁求最近的-!.t被阻塞所在炮级数g 请求从8级通过
3楚 1级，依次下去，直到官到达i袋，当然必须在此期部没有被莫言请求阻塞。如果应塞请求在
网络中一直未被其它请求盟主塞，而对应的被阻塞请求在j级又被民一温塞请求再次应塞，则
将B"i状态细分为BLj状态。宫的意思是该请求当前在i缀，而它最近一次被阻塞是在j缀，
此砖阻塞请求是在k级，
为简.化回返模型的数字表达式，引人下3月j待号z
S， =P{一个请求在t级，这里。ζi三三对
=P(A,) + Ep(B.. ,)
事
旦「，旧恨
与一毅模型和保持模型一样，等式(1)所表示的特移概率对于回返模型依然成立。下面
分别不同祷况求莉下的转移慨率e
(1)当前状态是A j
-个处于A，状态的请求可能以图 2 中 5 利z不同的右式通过该级.每种状态å9禄率如于"
Es,
(7)
P{ 图2的 (a)状态}=l-P(C)-
P{邵阳b)状态} =丑，旦户+P(C) ]
•
P{酷的川状态HiLEF+PfC}]
圭庆邮电孛院学}正 i992直
P(图2的(d)状态)=告 0
P{图2的(e)状态)=i1 (8)
从Al到A'+l的平均通过概率是方程式 (8)中各个概率的加权和。不能通过i级的请求，
它的状态就变成B5，I．I这里k表示阻塞请求的级 数。特 别 地， 当k n+l时就表示阻塞请求
处 于 连 通 状 悉 a
一 般 转移概率可按下式 算1
．
P{^ 。+ r 一)；1一豇16s
·一 詈 +Si--音P(c)
8
1
1
6S
。
k= i
o
P(丑{，ll^ l}= 4 s }< ≤n
(9．1)
(9．2)
’
- P(C) k=n+ 1
(2)当前状态是B⋯，且i年j
此种状态表示当前在i级的请求最近一次在j级被阻塞。由于请求的当前级数不同于当时
被阻塞时的级数，此请求在谖级是独立于其它请求的。它的转移概率应如下式：
P ⋯ ，}=卜 816
l
Si一 4
i军。sr号P(c) (10．D
s
(3)当前状态是BI．J，且i年0 ’
由于此时阻塞请求 自身不会被其它的请求阻塞，故引入下面的概率来说明阻塞请求状态的
变化：
= P 在k级的请求在一个周期内通 过 该级)
M ，f=P(请求‘RI 再一次阻塞请求 R： ，
这里“Rz 是前次在i级被 R ”阻塞，当时“R ”在k级)
由定义l
P(A⋯)+∑ P(B⋯， )
m ^ — — — — —
P(^ )+∑ P(B )
- ●
≤ ≤ n (11)
如果没有假设 (5)，M ，^I计算起来会变得非常复杂。而由假设(5)正好省掉一个新连通
幻
仉
+
<
C
．
B
B
P
维普资讯
70
P{困2的(4)状态}=454
F锢2的例状态} =护，
重庆部电学院学报 1992年
(8)
从A，主~A川的平均通过模率是方程式 (8)中各个概率的加权租·不能运过i级的清求，
它的状态就变成况.. ,. ，这里k表示阻塞请求的级数.待到j 边，当k. n+1墨守就表示阻塞请求
处于连追状态。
一毅池，转移概率哼按下式计算z
-16_ 4 ", 4
p{A,+.IA ,}=l -gïS，-百户，非卢-9烈的
16~
8C'
P{BJJ|AJ=;马
fF(C>
(9. 1)
k=i
i<kζn ()
k=n+ 工
(2) 当前状态是B':J J' 且i午 3
此种状态表示当前在i级的请求最近一次在i级被阻塞，油子请求的当前级数不饲示当时
被阻塞峙的级数， 1地请求在该级是狼立于其它请求的e 它的转移概率应如下式E
P{B，川IB
-16_. 4 ，，~ 4
l 14312 , 36=1
8r'
p{章，，} ", ~ S. i<k<n
!jP{C}hn+工
(3)当前状态是B，叶，且i斗#
，、
(10. 1)
()
由于此对应塞请求自身不会被其它灼请求应塞，故引人下西部榄率来说确恩塞请求状态的
变化z
1I1， =P{在k毅的请求在一个周期内通过该级}
亘在'...=P{请求‘丸'再一次阻塞请求aR~" ,
这里"R2."是曹营次在i级被"Rl"也塞，当时‘Rz"在k级}
吕定义事
•
P(A.+ ,) + Ep(Bk+"')
mll:=~一一.一-一 i ζk运ζn
P(Aρ 十 Ep(B" ，)
(1 I)
如果没有假设 (5)，吼"诗算起来会变得非常复杂.而也假设(5) 正好省掉一个童音连通
,
第 l期 邓亚平 线路交筷的RFT五连同络的性能分析 7l
的请求完成一 、走数据传送的概率。Mk． 可以写成 的乘积形式：
lnm。 ≤n
M =1 (12)
【1一 ／矗 k= +1
倘若在 i级 的 请求被在k级的请求阻塞，k>i．此被阻塞请求要再返 回到i级要占用i个
周期，而在k级的阻塞请求要再次阻塞先前被阻塞请求的概率是M-一 当使 甩 回退或救传操
作完成时，阻塞请求便从所占用的开关撤走，被阻塞请求是独立于其 它请求的，也按BⅢ状
态 (i j)进行处理。注意到同时到达一开关的多个 请求中，阻塞请求是随机选取的，又由
于阻塞请求是以1的概率通过i级，它在i级占有开关的概率是以M ^ l_】来代替h m 因此，
转移概率应为：
(1--M )[ 一 ．一}暑+ ，一 cc)]
。 J 1 一M + 一， [。一 s。一{毒+ s 一鲁 ] ： (13)
在i级有两种不同的阻塞情况，
])被同一阻塞请求再次阻塞，此时
fM ]=min(k+1， +1)且
P{B5．。【日}． )={ (14) 【
M川 小 I f=rain(k+}， +1)且 士
2)被其它独立请求阻塞，此时
(1一M )si j=f且 k f
1 舌 (1一M )sJ {< ≤ 且k≮f
舌 (1一MhDP(c) ，= +1且k
t{ ． ) 16 (15)
(1-- ^+I．I-I)s。 = 且 =
(1一 ⋯ -1)s i<f≤哦 =
(1一M +^l，i—1)P( ) j= +1N． =f
d
(4)当前状态是B
此种是B 状态 的特殊情况。先考虑阻塞请求处于连通状态 一旦阻塞请求完成本次数
传，财被阻塞请求通常会通过 0级，否则它是被再次阻塞，才无法通过 0级。这个条件通过
的概率可按下式计算：
P(丑f：：I丑：：{)=1一m +l (16)
如果阻塞请求是处于1到n级之问，则会出现三种不同的情况t其一是阻塞请求通过一级}其
二是阻塞请求被回退，但被阻塞请求来能通过 0级，其三是阻塞请求被回退，使被阻骞请求
通过 级。备种慵况的概率分别如下， 、 ⋯
维普资讯
第 1 ~辆 1~ 豆子 钱Z喜交换骨告RFT互连网络约性能分析
的请求完成一次数据传送的概率o M，!n l可以写成mi前乘积形式z
("11-，.(_+垒 • 1;+ I -1}
JTIm, k"';;n
M. 事=γ- ，
l1 -i (d k=n+ 1
71
(2)
倘若在 i 级的请求被在k级约请求阻塞， k>i. 此被阻塞请求要再返归到1级要占用i个
周期，而在k级的担宴请求要再次组塞先前被温塞请求的模率是M，t， I. 当使愿回退或数传操
作完成时，理塞请求便lÁ所占用的开关搬走，被砸塞请求是独立于其它请求的，也按Bhj状
态 (i"r j) 进行处理.注意到商量才到达一开关的多个请求申，阻塞需求是随机选l\'it驹，又由
于阻塞请求是以1约概率通过i级，它在i缀占有开关的概率是以 MHhl- 1来代替画龟• ，.因此，
转移概率应为z
r 16_ 4 " 4 _ ~ _~ 1
(1 -M...) L 1 -âÏS.一百虫+25，一百P (C) J
PfB.+ , ..j B).,} =, 111§4hl (1 -M刊 01_') I 1 -~;S，- ~.L S,- ~ P (C) I L 1 -81....'- 9 ~令 1 &.I j- 9'" \...., J
在i级有两章中不同的阻塞情况z
])被同一阻塞请求再次军主塞，此时
t
P{BL , j B上 d =~
i晶'k+lti-l
i=min(k+l. n+I)且 k"r i
Î=由协作+i ，n+ I)旦k=i
2) 被其它独立请求阻塞，此对
P{B. , H B, .;} =
16 (I -M..1)S 81....... ---ft
f ←M削烬
!t ←M..，)川P(C白>
1在8Ï (1-M.. ,.'_I)S,
;c-M轩 I ， '_')S
7• Mk+t , j • )P(C)
〈。当前状态是B" ，
;=iJlk守 t
i<j<，n且k斗t
i=n+l旦k "r i
;=i且k=i
i<Îζ"Iik=i
;=n+1且k=i
主手t
(1 3)
k=i
(1()
(15)
此种是B..，状态的持殊情况e 先考虑应塞需求处于连通状态e 一旦阻塞请求完成本次数
传，直1/被阻塞浦求通常会通过 e 级，否则它是被再次阻塞，才无法通过 a 缀。这个条件通过
的概率可接下式计算z
P{B:':~I B::!}=1-m'+1 (1 6)
如果缸塞请求是处于13量IJn级之间. j]1/会出现三种不同的情况z 其一是阻塞请求通过一级s 其
二是应塞请求被四退，但被阻塞请求未能通过 e 级，其三是阻塞请求被罔逞，使被阻塞请求
通过 E 级.各静情况的概率分别郊下，
72 量度邮电学院学报 1992年
— — — 一 一 一 — — — — — — — — — — — — — — — — — —
一 — — — — — — — — — — — — — — — — — — — 一 一
P(B ： IB ．。)=m ’
1 ^
P{ag。 I B；．。，= (1--m ) ’
， (17)
P{B⋯l B：．。)一÷ (1一m )
如果在 0级的阻塞请求是在同一周期内两个到达的请求中l殖机选择， 由手阻塞请求不会
在前一个周期被回退，被阻塞请求不会在下一个周期通过 0级。这种情况的转移概率：
P{丑 ．。{矗3． )；1 (18)
董此，回退模型的所有转移概率都在方程式 (1)和 (7)一 (18)中求出
5 模拟和结论
我们用平均请求服务时间作为评价网络性能的主要参数，可按下式计算
平均请求服务时间=d一 (19)
通过模拟评估网络的性能，模拟的结果用来验证从理论分析中得到 的数值解。每一次模
拟运行 4万个结点周期。由于模拟相当费资和费时，模拟时的参数值仅限于下列范围
发送者数l 8，16，32，64
请求率1 0．I，0．2，0．5，1～
寰1 回 退 涪 的 请 求 服 务 时 问
N r d-5 l lO d=20
f I ：
J模 拟『分 析{误差(嘶 1模 拟 分 析J误差(嘶) 模 拟 分 析 误差(嘶)
8
0．1
0．2
0．5
1．O
9．38
10．89
1I．75
12．82
I l
一 3·3 i 18·44：19·27 4·5 33-34
0．6 l 19
．gR l 20．64 j 3．3 35．01
2．4 21．32 21．77 2．I 36．96
0 22．18 22．3 5 0．7 3$．75『
4．0
4．5
2．7
3．I
0．1 12．6I 12．23 —3．0 1 2I．45 22．37 4．2 39．63 41．41 4．5
16 0．2 I4．02 I3．78 一I．7 『 22．64 23．52 3．0 41．78 43．03 3．0
0．5 I5．23 I5．05 一 I．2 23．78 24．21 I．8 44．I2 45．18 2
．4
I．0 16．39 I6．26 — 0．0 J 25．98 25．80 — 0．7 46．9B I 47．7I I．6
O．1 16．01 15．72 — 1．8 25．63 26．45 3．2 蚰 ．住 48．94 1
． 7
32 0．2 17．89 l7．53 — 2．1 26．94 27．32 1．4 50．24 5 0．64 0．8
0．5 I9．32 18．55 — 4．0 l 28．01 27．95 — 0．2 53．0B 52．79 —0．5
_ I．0 20．59 19．46 — 5．5 『 30．12 29．31 —2．7 55．37 54．87 —0．9
0．1 2口．12 l9．64 — 2．4 f 29．34 29．57 O．8 56．89 ‘6．O4 -一 1
． 5
64 0．2 2I．9I 21．23 — 3．I 3I．28 3I．I9 — 0．6 58．14 57．62 — 0
．
0
_
O．5 22．62 2I．65 — 4．3 32．77 3I．8 — 2．7 60．42 5g．97 — 2
． 4
I．0 24．10 22．66 一 6．0 34．32 33．2 9 —3．O 62．23 GO．05 —3．5
盯 蛄
盯 抽
盯 ∞
9 O 2 3
维普资讯
72 重庆部电学院学报 1曹92年
PfE;7JjELe)=mh
P{B~. ， \B:' ，} = 专 α-m，，)
P{B矶"川，刊，，\ B乓;ιL，Je归t ←悯ρ (17)
如果在 o 级的阻塞请求是在民-~期内两个jlJ达的请求中撞机选择，由于阻塞请求不会
在前一个男期被囚退，被阻塞请求不会在下一个离期透过 c 援。这种情况的转移穰率军
P{B!'.I B:. ,}=1 (8)
至此，回返模型的所有转移溉率都在方程式(1)和(7)- (1 8) 中求出。
5 模拟和结论
,
我们用平均请求服务时间作为评价网络性能的主要参数，可按下式计算z
d (I -P(l)) 平均请求服务时间=一 P(C)→(19)
透过模拟评估网络的位能，模拟的结果用来验证从理论分析中得到的数值解@每一次模
拟运行 4 万个结点周恕。由于模拟相当费资和费时，模拟2寸的参数值仅限于下列范围z
发送者数. 8, 16, 32. 64 李
请求率， , , ,
司I1 每遇法鹤请求.务 E吉闰
d=5 d=IO d=2 t1
- 主些1芝二号 I户主~~~I 在芝 53' :j)f; ì牛~) j 丰拟!二芝:j)汗 1 号差得〉
I I ì ': '
。.2 I I 阳岛 I " 凡nl 36 4 59
I 12. 1)3 1 ~." :H.辑
12·回 1, 2川 Ð.7 叩!
到 r
8
i
lι 39 1
16
&
-Ð5~ .0
\
., 78
4".12
I
,‘
9081
4017
.....
1$57 A-za'aaT
后
-2..7
-3..1
:、
3:
主明哥 I
! -3.。
-4..3
-8..0
目.G4
i
I
肘.
第 1期 邓亚平 线路交换的RFT互连同络的性能分析 73
裹2 保 持 {圭 的 请 求 晨 务 时 闻
d= 5 d 10 d=20
N r
模 拟 分 析 误差(和) 模 拟 分 析 误差(和) 模 拟 分 析 误差(和)
0．1 9．24 9．69 4．9 18．34 19．3 3 f 5．4 34．68 36．69 5．8
8 0．2 l0．36 1O．51 I．4 20．12 20．72 3．O 3B．97 38．08 3．O
0．5 l1．12 11．01 — 1．0 21．78 22．17 1．8 38．46 39．34 2．3
1．0 12．33 l1．89 — 3．4 22．96 22．85 — 0．5 41．12 41．90 1．9
●
0．1 12．0l 12．25 2．O 21．86 22．93 4．0 43．0l 43．6l 1．4
16 O．2 13．让 13．43 一 2．1 23．Ol 23．30 0~9 44．77 45．67 2．O
O．5 14．88 14．39 — 3．3 25．12 24．92 — 0．8 46．12 47．27 2．5
1．0 l5．96 15．42 — 3．4 26．34 25．92 一 1．6 拈 ．34 49．79 3．0
0．1 i5．11 15．53 2．8 26．13 26．81 2．6 50．24 52．75 5．O
32 O．2 l7．O2 l 6．68 — 2．0 27．54 27．76 O．8 53．33 55．14 3．4
0．5 18．68 l7．90 — 4．2 29．12 28．78 一 1．2 55．76 56．93 2．1
1．O l0．98 18．68 — 6．5 31．43 3O．27 — 3．7 68．12 58．88 1．3
0．1 1口．1 18．53 I一3．0 31．02 30．25 —口．8 砒．t3 59．7l —2．8
64 0．2 21．24 20．23 — 4．8 32．24 31．43 — 2．5 62．78 81．65 — 1．8
O．5 22．78 22．23 — 2．4 3‘．B3 33．90 — 2．1 65．12 63．82 — 2．0
1．0 24．86 23．09 — 7．1 36．78 36．4l — 1．0 B8．眦 66．82 一 1．8
数传时间I 5，10，20
采用 回遇法和保持法的结果，分别如表1和表2所示。在所 比较的48种情况中，相对误差
超过 5 的分别仅有2种和4种。
通过比较，不论是分析值或是模拟值，都可以得到这样的结论 除非是非常短的数传时
间，回遇法比保持要好，保持法在高请求率时要多 占用结点周期。
维普资讯
'
,
、-
囊z;r:
邓亚平 线路交换崎RFT至连网络的性能分析 73
主f 分
银籍法fIIJ请求攘务时揭
d=5
析误差{警}!摸 拟 iJia同可模 d=20 拟分新 i 误差陪
" 队24 I ι9 -4 1 四.33 t I 34.盹也踊
8 I I I I i I I I
I I 一 I 38
I I 11.制 ; 22..辅 I I ;
I ;;.251 ~ 2山 川1
16 I 比43 I 矶时;比坷 ι77 I Iι
64
0..5 14..回 -LZ i25·12;24·回事 -OJ 47·27;2·5
i u jue 15J2 -3..4| 且由-1，.6 i 且.341 LO
I I I I ; I 2
国 ..63 ，口.90
10. 四 13 ， 68
.12
18.岱
Iι8 I
22..23 1 34..63
比09 I
数传11tf;司. 5 , 10. 却
8也
30 ", 27
~2 ‘g
-2..5
-1..0
-
I
I
61 嘈 65 I
I
1_ 1• 8
采用回逗主要草鞋保持法部结果，分别如表1和表21i吁示e 在所比较的4草种情况中，相对误差
超过 5 铀的分别仅有2种和基释，
透过比较，不论是分拆值或是模拟值，都可以得到这样的结论z 徐非是非常短的数传对
间，自退法比保持要好，保持法在高请求率时要多占用结点周颊。
74 重庆邮电学院学报 1992卓
[1]
[2]
[3]
[4]
参 考 文 献
Deng Yaping and Chen Tinhuai． A Reliable and Fault-Tolerant Intere onne—
orion Network． Journal of Computer Sclcnce and Technology, Vo1．5， 2，
1990， p】’．117--I26
L．N．Bhuyan and C． W ． Lee．An Interfrerence Aealysis of nterconnec—
tion Networks．Proc．of Inte1．Conf． on Parallel Processing， 1983， PP．2
— 9
A ． Varma and C． S． Raghavavendra． Performance ．~／nalysis of a Redunda-
nt—l th Intefc0nnectj0n Network． Proc． 12th Inte1． Symp． on Computer
Architecture， 1985，pp．474．一479．
S．Abraham an d K．Padmanbhan．Performance of the Direct Binary n—Cube
Netwerk for M ultipreocessors． IEEE． Trans． Computer Vo1． C一 38， July
1989，pp·1OOp一1011
Performance Analysis of Circuit SWitching RFT
Intereonnection Network
Deng Yaping
(Department of Computer)
Abstract
In 出is Paper， two difference Conflict resolution methods, backtrace and hold，
arc discns~d．0ur ana]ytica1 models of performance based on a／norc realistie a
sumption． The quantitative analytiea1 parameter is average request service time．
The outcomes of an alyses are given—and are verified by simulation results． n is
shown 'hat the Dacktraee method is be tter than the hold method． In th hold
method． the data transfer time has taken more node—cycles． ．
Keywords block'conuect)transition probability)state
维普资讯
74 重庆部电学院学报 1992年
参考文醺
(1) Deng Y"ping and Chen Tínhuai. A ReUable and Fault-Tolera时 Interconne
ction Net胃。雪k. J ournal 01 Computer ScÌεnce and Technology, . :NI>2,
1吉90. -126
(2) L. N. Bhuyan and C. W. Lee. An Interfreren臼 Ana1 ysis of Interconnec-
tIon Net曹orks. Proc. of Intel. Conf. on Parallel P四cessing， 1983, 霎
-9
(8) A. Varma and C. S. Raghavavendra. Per10nnance Analysis 01 a Red回到da
nt-P望在也 1时erconnectio觅到etwork. Proc. 12th Intel. SymP. on Computer
Archite由ne， 1985, -479.
(4) S. Abraha皿 and K. Pad血anbhan. Performance 01 宿舍 Direct Bìnary n-Cube
Network 10r Multiprcocessors. IEEE. Trans. Computer Vol. C-38, July
198章， -1011
Performance Analy翠is of Circuit Switching RFT
Interconnection Network
Deng Yaping
(Dcpartmcnt 01 Computer)
Abstract
In thìs Paper, two dìfference Confllct resolutìon n理thods， backtra臼 and hold,
are dìsculII担哇. Our ana1ytical models of performance based on a more realistic a&-
四mption.τ'he 哇，uantí坦tive 副主alytí阻I parameter ìs average rεquest servi时 ììme.
The outcomes 01 国alyses are gi ven二and are verified by símulation results鑫It is
shown th副也.e Dacl<1race mcthod ì8 bette宣言han tbe hold 血的hod. In 1h.. hold
method, the data transler tíme bas taken more node-cycles.
Keywords block, connec飞 transítíon probabil it民 stat♂
,
飞
