第 28卷 第 i期
2000年 1月
华 中 理 工 大 学 学 报
J．Huazhong Unix,．0f Sei．8 Tech
N0 1
2000
@
6一
基于令牌环网的动态实时带宽分配算法
骆 雁 李胜利 韩宗芬 魔丽萍
— — — ～
— — ～
(华中理工大学计算机科学与技术学院)
，＼}
cl}
摘要：提出了一种动态实时带宽分配算法，能够动态估算当前各个结点的实时通信负载，分布式地控制各个
结点的令牌持有时间．宴时消息 M 的负载指数和结点的宴时消息负载指数．可 有效地衡量结点的实时通信
的负载情况，为动态分配实时带竟提供依据．通过模拟实验的刹试、证明该算法优于固定带宽分配，同时也说
上 的： ：实 令牌环 耸汤，宏日抽信眄． 关譬词：动态带宽分配；实时；令牌环 ．群 幽 ／、Hq‘ f p I√．
中图分类号：TP393 文献标识码：A 文章嫡萼：i000—8616(2000)01—0056 03
通 协
在实时通信网络中．实时消息有确定的传送 如何衡量结点在某时刻的实时通信负载是一
期限，如果不能在时限 (deadline)之前完成发送
就被认为是丢失了．实时通信协议的 目的是减少
实时消息的丢失率 。]．通信网络中每个结点的令
牌持有时间应能够根据当前结点的实时消息的负
载 隋况来动态地分配网络带宽、否则，可能会造成
某轻载的结点 Ⅳ 和重载结点 Ⅳ‘占用相同的网络
带宽．Ⅳ 得不到足够的带宽，从而使得实时消息
丢失率增加．本研究提出一种动态实时带宽分配
算法，采用分布式控制方式，在令牌上携带网络各
个结点最新的实时负载信息，结点根据此信息来
决定 自己的令牌持有时间，以此实现实时带宽的
动态分配．
1 动态实时带宽分配及其算法
1．1 动态实时带宽分配的思想
对于实时带宽的静态分配存在浪费带宽的问
题．在某结点上实时消息到达较少的时期 ，其发送
实时消息后所剩的带宽不能被其他结点利用．带
宽浪费会不必要地增加消息丢失率．
动态带宽分配的 目的是充分利用带宽，减少
消息丢失率，为此它应能够根据系统运行时各个
结点的通信负载动态分配带宽．本研究提出的动
态实时带宽分配，使得宴时通信负载较大的结点
能够有较多的令牌持有时间，宴时通信负载较小
的结点的令牌持有时间相对较少．而令牌持有时
间的比例决定了结点占有实时带宽的比例．
个难点．一般可以得到消息到达时问的统计分布
规律 (一般视为参数为 ^的泊松流)，但是，因为
分布规律参数只具有静态特性 ，所以不能作为衡
量标准．实时消息的长度和数量也不适于作为衡
量标准，因为投有考虑实时消息的时闻特征 本研
究提出的实时消息负载，综合考虑了实时消息的
长度及其时间特征．模拟实验的结果表明以实时
消息负载作为衡量结点实时通信负载的参数是可
行的．
1．2 网络拓扑
对令牌环网络 ，假定网络提供一个共享信道．
网络上有 个结点．按照物理的或者逻辑的前后
次序，依次编号为 Ⅳ．．，Ⅳ ，⋯．Ⅳ 一 ，Ⅳ⋯．
定义 1 实时 消息 M 用 五元 组 (L ， ，
D ．T ，P ( ))描述，其 中．L 表示消息的长
度；A 表示消息的到达时间；D 表示消息的截止
期限；T 表示消息的最迟发送时间；P ( )表示
消息 在时 刻 的松 弛度 ，即有 T —D 一工 和
PⅥ(f)一Tm f．
定义 2 在时刻f结点 l^上未超时的实时消
息集合 一{M 7’： ”>f，M 是结点 Ⅳ 上的实时
消息 }．
定义 3 结点 -^上的实时消息队列 Q 是由
到达结点的实时消息 M 组成的有序队列 ，队列中
的元素按照 T’升序排列．
本算法为了度量各个结点的实时消息负载．
定义下砥几十指数 ：
收 藕 日期 ：1999 07 27．
作者筒介：骆 雁(1976一)．男，硕士研究生；武汉+华中理工大学计算机科学与技术学院 (430074)
基盒项目：国防预研基金资助项目．
维普资讯
革 ~B 卷第 1 期
:!O(IO 年 1 月
华中理王大学字报
J. Huazhang Cmv.η( Sci ， ~ _ Tec: b
Vù l. 2('.
Jan. 2(1(10
e
Sb- $8
基于令牌环阔的动态实时带宽分配算法赘
骆暖辛胜利马芬览黯 丁f3，3•
{华中理工大学计算机矜学与主主术学院〉 7的~).三
察要 I 提出了一种动态实附带宽Jt童艺算法，室主穆动态估算笃前各于结点约实时通信负载胃分布式地控巍各于
结点的争牌得有时间实时3需皇)，1i!吉负载指数和结茸的主:I>t消阜负载f室主主.可以有效边蜜量运点的实时通信
童电负载?曹况、为动态耸配实在苦号苦宽提供依据.通过镇拟实主主剖醒过‘证BJ!该算洼优于吕定带宽分配.病毒才也说
明上述喝两个指数是写行的 告 .L b l1牛，三位面
美锺词·动态带宽分配 s实时 z 争毒草环 鼻均 /飞 ~O -'.ul I ~ r:J
中圈分类号 τP393 文戴串串识碍 A 文章菊号.. InoO-S';16{2υO(J陆 1- (10;;6-03
1鱼1! t寄 îX
在实时通信何络中.实时消息有确定幸亏传送 如何衡量结点在某时刻的实时通信负载是一
期限，如果不能在时限 (deadline) 之前完成发送
就被认为是丢失了.实量才通信协议主号目的是减少
实时消息的丢失率[1.-，].通信飘荡中每个结点的令
将持有时何应能够根据当前结点的实时消怠的负
载情况来动态地分裂照络带宽‘否则毛可能会造成
某轻载的结点 N 和重载结点二V 占黯相同的网络
带宽. .íV' 1寻不到足够的带宽鲁从而使得实ll1消息
丢失率增主U. 本研究援tlJ一矜动态实时带宽分配
算法，采F军分布式控部方式，在令牌上携带网络各
个结点最新的实对负载信息.结点根据此信息来
决定自己的令牌持在时间.以此实现实时带宽幸亏
动态分配，
1 动态实时带宽分配及其算法
1. 1 动态实肘带宽分重的思想
材于实对带宽的静态分配存在浪费带宽的同
题.在某结点上实时消息到达较少的时期.其发送
实时消息后所乘j的带宽不能被其他结点利用带
宽浪费舍不必要地增怒消息丢失率，
动态专营宽分配的吕豹是充分利用带宽，减少
消怠丢失率噜为此它应能够根据系统运衍对各个
结点必通信负载动态分配带宽.本研究提出的动
态实ll1带宽分跤，使得实时通信负载较大的结点
能够有较多剖令军事持有对间，实ll1通信象载较小
的结点的令斜待有时向相对较少范令牌持高慰
问的比例决定了结点占有实传带宽的 t~伊.j.
i在辅臣翻 1999-07-27.
个难点，一般可以得到消息到达时间的统计分布
巍律 i一般视为参数为 λ 的泊松流入但是.因为
分布媲律参数只具有静态待性.所以不能作为衡
量标准.实时消息在专长度叙数量也不适于作为衡
量标准，因为没有考虑实时消息部时i哥特征、本研
究提边的实时消息负载.综合考虑了实时消息的
长度及其时间特征=模拟实验告号结果表明以实时
消息负载作为衡量结点实对通信负载的参数是可
行的.
钢结搭扑
对令脾环网络·假定网络渠供一个共享信道
F理络上有 n 个结点，按照物理弱或者逻辑的前后
次序‘依次编号为儿 t .. V" …‘ Nη:"" NM寸'
定义? 实时消息双用五元缰 t!...M' AM~
1)\{. ~í，{. 只是(t门描述，其中、 4，表示消忌约长
度 :AM表示消息的到达时间 ;DM表示消息的截止
期限 ，T.，表示消息始最远发送对间 ;PM (ρ 表示
消息在时刻 2 的松弛度，即有 TM=DM-LM 幸Z
P划 (t l=T.， -t.
定义 2 在时刻 f 结点 N.上未超射的实财消
息集会 φ=IMT，叼 > 是主主点1.'\1.，上始实时
消息i.
定义 3 结点 λ7、上的实时消息;M.列 Q，是由
到达结J点的实对消息 M 组成的有序M.列，队列中
幻元素按照 Z 升序排列，
本算法为了度量各个结点的实ll1消息负载、
定义下面几于指数 2
伴着冒01)'，骆 罹 11975-}~亮，硕士读究生 z武汉，华中理工大学计算机科学与技本学院 (430074 ),
基金理U!I，国防预研塞金资助硕吕号
第 1期 骆 雁等：基于令牌环网的动态实时带宽分配算法
定义 4 实时消息 M 的负载 r是为了满足
M 的截止期限 ，而在单位时间 内要发送 的实时消
息的长度 ，r—L ／P (r)．
定义 5 在时刻 t，结点 Ⅳ．的实时消息负载
皿(f)是该结点上 中所有实时消息的负载之
和．n，0)一 ∑ r，．
M ∈
结点的实时消息负载 D综合反映了该结点
要发送的实时消息的数量和紧迫度．实时消息长
度越大，松弛度越小，结点的实时消息负载 n就
越大．
定义 6 在时刻 t，网络上总的实时消息负载
尺是网络上所有结点的实时消息负载之和．
J— L
R一 ∑D，．
n
尺反映了网络上总的实时消息负载情况．R
越大，负载越重．应该指出的是 尺是一个近似值．
因为当令牌持有结点计算 尺时，其他结点的n可
能已经发生了变化，令牌上的信息已经过时．但是
由于结点的消息到达遵循一定的统计分布规律．
这种近似是可行的．模 拟实验结 果也表明 了这一
点．
定义 7 令牌 Token表示 为一个 ”+l元组
(H．n。，n ，⋯，n )．H 表示平均令牌持有时
间，令睥不仅是持有令牌的结点占有信道的标志．
它还要携带当前环网上的各个结点的最新的实时
消息负载信息．
1．3 算法描述
网络上的结点有两种状态：持有令牌和未持
有令牌．动态带宽分配算法处理结点的这两种状
态．当令牌到达结点 Ⅳ．时．根据本结点的实时负
载和令牌上携带的各个结点实时负载信息来决定
本结点的令牌持有时间，发送实时消息．当结点未
持有令牌时．将到达的实时消息按照消息的丁排
队．
HoldT0ken
输人：i(持有令牌结点的编号)，Token；
输 出：‰ (下一个持有令牌结点的编号)，
Token
a．计算结点 的n．( )．
b．计 算结 点 Ⅳ 的令牌持 有时 间 Tnt—
n．(f)／(RnH )．
c．计算令牌失效时间 7 一，+T“ ，t为当前
时刻．
d．如果队列 Q．不空，取队列 Q 的队首元素
M；否则，转 h．
e 如果 T w<f，则丢弃 M：否则 ．如果 丁 w
+L<了1 ．则发送 M；其他情况 ．不处理 M．
f．M—M一．，重复 e，直到 M 为空或者
>f或者 t一7 ．
g．重新计算结点 Ⅳ．的n，( )，并使 nTo一 一
n．(r)．
h．决定下一个持有令牌的结点：‰ 一( +
1)M 0D ．
j．结束．
NoToken
输人：结点的编号 i，实时消息 M；
输出：无；
a．将 M 插人队列 Q．；
b．结束．
2 模拟模型
在模拟模型中．结点数目是 个，单位时间内
到达结点的实时消息个数服从泊松分布，到达率
为 ．各个结点的 可能不同．每个实时消息的到
达是独立的．实时消息的长度服从参数为 的负
指数分布．实时消息的松弛度是一个在 [0，2PAL]
上的均匀分布，P 是平均松弛度．
实验目的是对比动态带宽分配算法和固定带
宽算法在实时消息流量重载和轻载时的性能．本
研究用消息丢失率 尺M一-来衡量性能：Rm一(1一成
功 发 送 的 消 息 数 目／到 达 系 统 的 消 息 数 目)
1[)() ．实验分成两组，一组研究各个结点的 ^相
同，即各结点的负载均衡的情况；另一组研究各个
结点的 不^相同．即各结点的负载不均衡的情况．
决定令牌的平均持有时间H 的取值的原则是使
R M--取得最小值．令牌携带负载信息．具有一定的
开销 (长度为 2(71+1)byte)，但是一般令牌网上
的令牌帧的大小在 100 byte节以上，所 以当 <
j0时，可以认为该令牌不会增加额外的开销．
3 性能模拟和评价
第一组模拟实验中， 一10． 取值 50．100，
200．300，400．500： 固定取值 100，P 1^分别取值
l∞，1 000．图 l(a)和 (b)是在各结点负载均衡
时的比较．从图中可以看出，不论在消息松弛度较
大还是较小的情况下．动态带宽分配的性能均优
于固定带宽分配．
第二组实验结果亦表明在各结点负载不均衡
时．动态带宽分配的性能也优于固定带宽分配 比
如 ，当”： 10，结 点 的 分^ 别 取 值 100，500．50．
维普资讯
第 1 期 4吕 覆等基于争毒草环同的动.~实对带宽分配寰法
"
定义 4 实町梢怠刻的负载 F是为了满足
M 的截止期限.丽在单位时间内要发送的实时消
息的长度 ，r~L，， /PM (fl.
定义 5 在自才费~ t.结点 A\ 的实 ~t消息负载
。，臼}是该结点上 φ，中所有实时消息的负载之
和 .a，(t l~ ~ r ,
.U<二，
结点的实时消息负载。综合反映了该结点
要发送的实时消息的数量和紧迫度.实E扫毒息长
度越大，松弛度越小.结点的实时消息负载。就
越大.
定义§ 在时费~ t ，网络上总的实耐消息负载
R 是网络上所有结点的实时消息负载之秘.
R~ 工n.
，且们
R 反串起了湾络上总的实~t消息负载翁况.R
越大，负辈辈越重.应该指出的是 R 是一个运似值.
因为当令牌持有结点it算 R B>t.其他结点的。可
能已经发生了变化.令牌上的信息、已经过对.但是
由于结点吉它消 j怠到达遵循一定的绞it分有规律毛
这矜近似是可行的.模拟实验结果也表Il)j了这一
点.
定义 7 令粹 Tokεn 表示为 争 n+1 元纽
(H , ao .βj' … . a.→ ， ).H 表示平主主令眸持有对
伺‘令牌不仅是持有令婷的结点占有信道的标志.
它还要携带当前环网上的各个结点约最新的实时
消怠负载信息.
1. 3 算法描述
网络上的结点有两种状态持有令弹和未持
有令草草.动态带宽分配算法处理结点的这两种状
态.当令聘到达主主点J..Vj R-才.根据本主主点的实时负
载和令膊上携带的各个结点实时负载信息来决定
本主吉点的令粹待有时沟，发送实时消息.当结点未
持有令牌碍，将到达的实时消息按照消息的 T 排
队.
Holdτoken
输入， (持有令牌结点前编号).Token ,
输出 nn~>.< (下一个持有令牌结点的编号λ
Tokεn
a. it算结点 N， á<J a, (t ).
b. 计算结点 l、rz 约令烧持有对 i胃 THT =
aJt) /(RnHl.
e. 计算争瞬失效对间 TE二t+THT~t 为主要毒草
时魁
d 如果队列 Q，不空‘取队到 Q 的队苔元素
M.否则，转 h
已如果 TLS\(<t~ 如j丢弃 M. 否则.如果 T，皿
十L<TE • 则发送豆，1.其他情况雹不处理 M
f. M~M叩噜重复 ι直到到为空或者 TLSM
>t 或者 t~T'l.
岳重新计算结点 l\lj 的 β'， (0 ‘并使 βTö;.盯
a,(t l.
b. 决定下一个持有令牌的结点 :nR~、~(ì+
UMODn.
i 结束.
NoToken
输入 z结点的结号 I •实 ~t消息 IH.
赣出?无 s
a. ~号 M 插入队列 QI*
起.结束.
2 模拟模型
在模拟模型中.结点数目是 n 个.单位时间内
主要j 达结点的实B>t消息争数服从泊松分布.到达率
为 À.各个结点的 λ 可能不同.每个实对消息的到
达是独立的，实时消息的长度疲从参数为 μ 的负
指数分布.实时消忌的怯弛度是→个在[白 ， 2P" ]
上的局匀分布 ~P.'d 是平均松弛度.
实验目的是对比动态带宽分自己算法秘密远带
宽算法在实时消忌流量重载和轻载时的性能-本
研究用消息丢失率 RM' 来衡量性能 .R盹=门 成
功发送的消息数目/王军这系统的消息数目}
1白o 1}1，.实验分成两组. 组研究各个结点始 λ 相
同.即各结点约负我均衡约情况:另→组研究各个
结点的 λ 不稳同. ~p各主主点的负载不均街的情况.
决运令牌的平均持有时阔 H 的取值约原践是使
RM1 取得最小值.令牌携带负载信息.具有→定的
开销〈长度为 2(n+11bytel ，但是一般令盖章网上
的令牌赖的大小在 100 七yte 节以上，所以当 n<
，0 时.1lJ以认为该令牌不会增泌额外的开镑，
3 性能模拟和评价
第一经模拟实验中 .n=10.À 取值 .
， 4∞ .0白 Ú: ，U 固定取值 ， 分别取值
100 ， 1 号自O. 图 1 (s 1 和{初是在各结点负载均在蕾
时的比较.从图中可以看出、不论在消息松弛度较
大还是较小约情况下，动态带宽分自己约性能均优
于固定带宽分配.
案二组实验结果亦表明在各结点负载不均衡
时·君主态带宽分配的性能也优子固定带宽分重已比
纽‘当 n = 10. 结点的 A 分JjJJ 取值 1号0 ， 5()白， 50 ，
58 华 中 理 工 大 学 学 报
蕞
＼
世
宴时清患到达率 ^ 宴时诮息到进辜 ^
(a)P 一 1 00 (b)P = 1 000
图 i 不同消息松弛度对应的消息丢失率
300，200，400，1 000，66．800，150，P 一1 000时，
动态带宽分配的R 一2．1 ．小于固定带宽分配
的 RML一27
通过模拟实验的测试，证明该算法优于固定
带宽分配，同时也说明上述的两个指数是可行的．
进一步的工作包括给出计算最优的令牌持有时间
的计算公式．以及采取不同的策略来决定下一个
持有令牌结点．
参 考 文 献
[1]李胜利，骆 雁，许青林等．一种有保证实时通信协议
的设计．华中理工大学学报．1999，27(4)：lj～17
[2]Chou C C Shin K G．StatlstieM Real Time Channels
OD．Multi-Access Bus Network． IEEE Trans． On
Parallel and Distributed Systems·1997-8(8)：769
～ 779
Dynamic Allocation Algorithm for Real—Time
Bandwidth in Token Ring Network
Luo Yah Li Shengli Han Zongfen Pang Liping
Abstract：Dynamic allocation algorithm for real—time bandwidth is proposed tO estimate the current re—
a1-time communication load of each node dynamically and control the token hold time of each node dis—
tributedly．The two metrics—load of rea[一time message and teal time communication load of node—pro—
posed can be used tO compute the real—time communication load of nodes efficiently and provide the
clues tO allocate network bandwidth．The simulation results show that this algorithm outperforms the
fixed bandwidth allocation．
Key words：dynamic band width allocation；real—time；token ring
Luo Yah Postgraducte；College of Computer Sci．＆Tech．-HUST-Wuhan 430074，China．
(上接 第 37 页)
Study of Generation of Mesh for Laminated Object Manufacturing
Zhou Aiain Xiao Yu ia H art M ing H uang Shuhuai
Abstract；A new method for automatic generation of mesh on LOM is proposed by means of modular—
ization method after the principle of detaching waste parts from model is analyzed，Different modules
can be combined complying with feature and requirement of model in this method，making detachment
easy and furthermore improving the efficiency of the process．
Key words：laminated object manufacturing；generation of mesh；detachment of waste parts；modu
larizaiton
Zhou Aixin Postgraduate：College of Materials Sci．8 Eng，，HUST．W uhan 430074，China．
维普资讯
5&
25
~ 20
、
225
呐~ 10.
a￥
~ 5
G
华中理工大学字报 如何年
100 2013 400. 500.
辑时清理、驾运率/.
2S
~ 2。
\
:- 15
Zm
号~ S
e 100 四o 4.忍 500
~'fi啻且到达草/.
~a)P..~=lúJ) (b)P、= 1 OOrì
00 1 不同黎息怯强凄苦才应给i自息丢失率
通过模拟实验的削球，证明该算法优于困定
辛苦宽分配.民对也说明上述约两个指数是可行的
进一步的工作包括给出计算最tt鹤令盖率持有财间
的计算公式，以及菜或不同的策略来决定下一个
持有令辈辈结点，
参 考 文 戴
[1] 李胜利.骆 糙，许青林等.一种有保证实沟通信给议
的设计，华中理工大学学经.1999. 27(4)~ -17
300 ， 告 .1 , 151) .PAL=1 ()O白时.
动态辛苦宽分配的 RM1_=2-1 吨，小于理定带宽分配
约 RML =27 %.
[:-:] C C. Sbm K 心. Statistlcal Real-TiτlW; Ch~mnels
(Jfi MUltl~A白白， B飞回 Ne-twork. IEEE Trans. 00
Parallε i and Di~tn缸tted System:h 1997. 8 <8>: T68
~719
Dynamic AlIocation Algoritbm for Real-Time
Bandwidtb in Token Ring Network
Luo YU 1I Li Shengli H .an Zongfen PanK I...í卢mg
Abstract: Dynamic allocation algorithm for real-tirτle bandwidth is propo旦岳 阳回tímate the curren主 re
al-tÎme communicatÎon load of 臼ch node dynamically and control the token hold time of each node dis-
tributedly. τhe 雹百o metrics-Ioad. f} f rea[-tÎ回em白sagεand teal-time communïcation load of node-pro
posed can be used to C'ompute the real-timεcommUß1C剖ion load of nodes effícíently and provìde the
dues. to alJocate n时work 坦andwìdtλThεsimulatlon 丘sults 田 that thls algoríthm outperforms 芝he
lixed 七andwidth allocation.
E豆ey words: dynamic band width aHocation; real-time; token ring
Luo 吉an Postgraducte ~ Colleg t:' of Compllter Sc i. ß.τ四h. • HUST. Wuhan 43白074 ‘ China.
…一一一』一←+一-+…+→一一-一…~-+-~-+十一一"一一一一一一一，
〈上接第 37 茧}
Study of Generation of Mesb for Laminated Object Manufacturing
ZIWll .. 4iJV/ .. Yiao Yue;i tI Han ;,\{in. g Huung Shuhuai
Abstract , A ne暂 method for autüm剖IC genεration of m臼h on L。如f i!'. proposed 垣y means of
ization method af时r the prin口ple 01 detaching 胃部te parts from mooel is analyzed. Ðìfferent modules
can 法 combined comp~ying wíth fεature and req出rement of model În thís 四ethod. making detachment
εasyand fllrthermore ì四proving the εHiciency of the proce臼.
区ey words: laminated 0七ject manufacturin草 generation of mesh;. dεtachment of waste-parts 1 modu
lariz鑫i芝on
Zhou Aixin Postgraduate , College 01 M挝erials Sc;. t.. Eng. . HUST. W uhan 430074. China
