（计算机软件与理论专业论文）基于高可靠性的重负载Ⅰ型双星lan性能评价.pdf

摘要 一般而言，星形计算机局域网( l a n ) 中心结点只有一条通道，形成单星l a n ， 为星型l a n 的最简单构成。而多星l a n 的中心结点由多条通道构成，具有更大的通 信容量。 为了改进星型网存取方式，人们在研究多星l a n 时提出了著名的介质访问控制 方式一竞争冲突淘汰( c o n t e n t i o n c o l l i s i o nc a n c e l l a t i o n ，c c c ) 访问方式，根据顾 客请求服务、再次请求服务、接受服务的各种情况进行组合，区分出六类系统模型。 目前，竞争一冲突淘汰存取方式单星l a n 的i 类类系统模型的数学建模与性能评 价已经完成。但是，由于在数学方面存在的困难，对多星l a n 数学建模的研究进展 缓慢，所以对于多星l a n 的建模解析，尚需深化研究。 目前，深化研究工作主要集中在双星l a n 。最近有学者在重负载条件下对i 类 双星l a n 进行了建模研究。但是该文在研究双星l a n 时，并未完全考虑到目前网络 技术的发展，建模时考虑了网络服务存在失败的情况。近年来，随着计算机网络硬 件和软件的进步，局域网服务的可靠性有了极大提高，因此本文忽略双星l a n 服务 存在失败的情况，在重负载下进行了数学建模，再次评价了网络性能，提出了顾客 转移概率只，、顾客继续滞留时间等的数学计算式，同时进行了模拟实验。本文的研 究进展简化了有关文献的结论，不仅对发展重负载下有线星形l a n 和无线星形l a n 有一定理论价值，而且具有性能评价的实用性。 硕士研究生刘飞( 计算机软件与理论) 指导教师逯昭义教授 关键词：双星l a n ；竞争一冲突淘汰访问方式；数学建模 a b s t r a c t g e n e r a l l vs p e a k i n g ，t h e r ei so n l yo n ec h a n n e li ns t a r - l a nn a m e ds i n g l e s t a rl a n ， t h em o s ts i m p l ef o r m m u l t i s t a rl a nh a sm o r et h a no n ec h a n n e l sw h i c hb r i n gg r e a t e r c o m m u n i c a t i o n sc a p a c i t y i no r d e rt oi m p r o v es a t e l l i t e b a s e dn e t w o r ka c c e s sm e t h o d ，an e wf a m o u sm e d i a a c c e s sm o d e 4 】n a m e dt h ec o n t e n t i o n c o l l i s i o nc a n c e l l a t i o na c c e s sm o d e ( a b b r e v i a t e da s c c c ) h a sb e e np r e s e n t e d a c c o r d i n gt ot h ed i f f e r e n ts i t u a t i o n so f c u s t o m e r sr e q u e s t i n g f o rs e r v i c e ，r e r e q u e s t i n gf o rs e r v i c e ，a n db e i n gs e r v e d ，t h es y s t e mm o d e lo fc c cc a nb e c l a s s i f i e da ss i xt y p e s a tp r e s e n t ，t h es t u d i e sa b o u tc c cs i n g l e s t a rl a no ft h ei s t 、 l i n d 、i i i r d 、i v t h 、v t h 、t ht y p e sh a v eb e e nf i n i s h e d h o w e v e r , b e c a u s eo fd i f f i c u l t i e s i nm a t h e m a t i c a la n a l y s i s ，n op a p e rh a sm a d ea n yr e p o r to fm u l t i s t a rl a n i no r d e rt o m a k ei n n o v a t i o nf o r t h ec c ca c c e s sm o d e w eh a v et os t u d ym u l t i s t a rl a nd e e p l y a tp r e s e n t t h ed e e pr e s e a r c hm a i n l yi sc o n c e n t r a t e do nd o u b l e - s t a rl a n r e c e n t l y f o rt h ef i r s tt i m et h em o d e l i n gr e s e a r c ho fi s tt y p ed o u b l e - s t a rl a ni nh e a v yl o a d c o n d i t i o n sh a sb e e nf i n i s hi nl i t e r a t u r e h o w e v e r ，t h et e x to f t h es t u d yo fd o u b l e - s t a rl a n h a sn o tf u l l y t a k e ni n t oa c c o u n tt h ed e v e l o p m e n to fc u r r e n tn e t w o r kt e c h n o l o g y a s r e s u l t ，i tc o n s i d e r e dt h ec a s eo fs e v e r i n gf a i l u r ew h e nm o d e l i n g i nf a c t ，i nt h ep a s ty e a r s w i t ht h ep r o g r e s so fc o m p u t e rh a r d w a r ea n ds o f t w a r e ，t h er e l i a b i l i t yo fl o c a la r e an e t w o r k s e r v i c e sh a sb e e ng r e a t l yi m p r o v e d s oi nt h i sp a p e rw en e g l e c t e dt h es i t u a t i o no ff a i l u r e i n d o u b l e s t a rl a ns e r v i c e sa n df i n i s ht h em a t h e m a t i c a lm o d e l i n ga n dp e r f o r m a n c e e v a l u a t i o ni nt h eh e a v y1 0 a d a tt h es a m et i m ew eg e te x p r e s s i o n sf o rt h et r a n s f e r p r o b a b i l i t yo ft h ec u s t o m e r s ，t h ec o n t i n u e dr e t e n t i o nt i m eo ft h ec u s t o m e r si nt h es y s t e m a n dc a r r yo nt h es i m u l a t i o nf o rt h e m 1 1 1 i sr e s e a r c hs i m p l i f i e st h ec o n c l u s i o no ft h e l i t e r a t u r e i tn o to n l yh a st h e o r e t i c a lv a l u ef o rd e v e l o p m e n to fw i r e ds t a r - l a na n d w i r e l e s ss t a r - l a ni nh e a v yl o a d b u ta l s oh a v ep r a c t i c a l i t yt op e r f o r m a n c ee v a l u a t i o n g r a d u a t es t u d e n t ：f e il i u ( c o m p u t e rs o f t w a r ea n dt h e o r y ) d i r e c t e db yp r o f z h a o y il u k e yw o r d s ：d o u b l e s t a rl a n ，c o n t e n t i o n c o l l i s i o n c a n c e l l a t i o na c c e s sm o d e ， m a t h e m a t i c a lm o d e l i n g 学位论文独创性声明、学位论文知识产权权属声明 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中依法引用他 人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上已属于他人的任何形式 的研究成果，也不包含本人已用于其他学位申请的论文或成果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名：塑l ! 睦 日期山拇年阴l 阳 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。学校享有以 任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校后发表或使用学位论文 或与该论文直接相关的学术论文或成果时，署名单位仍然为青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密瓯 ( 请在以上方框内打“”) 论文作者签名：壶l 整日期：) 胁& 年写f l l b 导师签名：延酿 日期：睥易月i 泪 ( 本声明的版权归青岛大学所有，未经许可，任何单位及任何个人不得擅自使用) 4 5 第一章引言 第一章引言 计算机是2 0 世纪最重要的发明之一。计算机的发明使得人们对信息的处理和加 工更加简便、直接，借助于计算机，人类具有了处理异常复杂系统的能力。但计算 机网络并不是随着计算机的出现而出现的，而是随着社会对资源共享和信息交换与 及时传递的迫切需要而发展起来的。它是现代计算机技术和通信技术密切结合的产 物。在现代社会中，信息已成为经济发展的重要源动力，人们对信息的需求量越来 越大，范围越来越广，对信息收集、传送、存储和处理的能力要求也越来越高。显 然，单枪匹马的计算机操作已不能满足人们的这些需求。计算机网络就这样应运而 生了，计算机网络的发展与完善，真正使得人类跨入了信息社会。目前，从政府、 企业、学校到生活小区，各行各业、社会的各个角落都感受到了计算机网络所带来 的新变化。2 l 世纪，我们面临的是一个网络化时代。 计算机网络是计算机技术与通信技术相结合的产物。利用通信线路和通信设备， 将地理位置不同的、功能独立的多台计算机相互连接起来，以功能完善的网络软件 来实现资源共享和信息传递就构成了计算机网络系统。 局域网主要有三种拓扑结构，即星型、总线型和环型，它们都是以单介质( 如单 星、单总线、单环) 为基础的。为了发展计算机局域网技术，在早年人们对单介质 存取方式进行了广泛而深入的研究，目前单介质总线形l a n 和环形l a n 的介质存取 方式已趋成熟，星形l a n 存取方式的研究也取得很大的进展。然而近年来由于综合 业务数字网和a t m 交换网的发展使网络的通信量不断向海量信息量增进，这一现实 严重地冲击了单介质存取方式局域网。为了在局域网中既实现综合业务( 语音、数 据、视频、传真) 传输，又提高局域网的吞吐量和可靠性，自然而然人们将研究的 重心转向了多介质( 包括双介质) 局域网存取方式的研究。众所周知，网络存取方 式主要由网管理方式和通信方式两部分组成。管理方式指l a n 的独占方式，即如何 拥有l a n 的使用权。通信方式指信息帧如何通过介质。存取方式研究的重点主要是 网络管理方式，其次是通信方式，多介质存取方式的研究也不例外。 在局部网的拓扑结构中，星型拓扑以扩展性好、容易实现高速传送而著称。但是， 由于它具有中心结点、且在中心结点设立的中央处理器如果出现故障会使全网瘫痪， 故可靠性较总线形和环形逊色，这在一个时期内限制了它的发展。近年来，伴随着 光纤通信的急速发展，人们注意到星形拓扑很适于连接光纤，对光l a n 的开发研究 能起促进作用。于是，星形l a n 和星形光l a n 的研究又积极开展起来。目前见到的 星型l a n 其存取方式大都采用总线型l a n 的c s m a c d 存取方式。因为这种存取方式 对冲突不可避免，它并不是星型l a n 的理想存取方式，因此对星型l a n 的存取方式 进行开创性的研究早就是国内外很多学者的共同看法。为此人们就星形拓扑结构提 青岛大学硕士学位论文 出了多星l a n n 3 1 ，并就多星l a n 的运行机理进行了报告。 上世纪八十年代以来，在计算机通信网络和计算机局部网络快速发展的同时， 人们把通信信息量理论扩展到计算机网络，使评价网络性能、设计建造性能价格比 优异的计算机网络的研究工作取得了很大进展。单星l a n 的情况已经取得了突破性 研究进展，人们提出了一种创新介质访问控制方式一竞争一冲突淘汰访问方式 ( c o n t e n t i o n - c o l l i s i o nc a n c e l l a t i o n ，c c c ) 4 1 ，该文将单星l a n 的c c c 方式分为6 大类型。目前c - c c 存取方式i 类、i i 类、i i i 类、类、v 类、类的数学建模已 经完成 5 - 1 0 】。在重负载下，双星l a n 的数学建模已取得了一定研究进展。 本毕业论文针对当前计算机网络硬件飞速发展、局域网服务可靠性有了极大提高 的情况下对双星l a n 建立数学模型，进行了数学解析和模拟实验，同时，与文献 1 1 情况进行了比较，比较结果在最后讨论。 2 第二章前期研究进展 第二章前期研究进展 一双令牌双环l a n 的一种性能解析评价 为了对多环( 双环以上) l a n 进行性能评价，比较简洁精确的评价双令牌双环 l a n 的性能，是个亟待解决的研究课题。本文将双环l a n 中两个物理性服务员( 双 令牌) 分别进行间歇式服务的非典型排队系统比较巧妙地等效为1 个“扩展服务员” 进行扩展服务( 将循环时间扩展为服务时间) 的典型排队模型，比较理想地解决了 待求问题。这一性能评价方法可以推广到多环l a n 。数值计算表明，本研究为建造 高性能的双令牌双环l a n 提供了理论依据。 2 1 双令牌双环l a n 运行原理简介 双令牌双环l a n ( 简称双环l a n ) 的运行机理已有报告【1 2 l ，本文为了建模研究 的需要，不妨略加说明。双令牌环l a n 由个工作站和两条传输方向相同的环路 构成，分别称之为外环和内环，两条环各有一个令牌，分别记为a 令牌和b 令牌。 a 、b 令牌在环网内按一定方向传递，获得令牌的站点即可发送数据。拓扑结构如图 2 1 所示。 图2 1 双令牌双环l a n 双环l a n 的两环独立工作，每一环的工作机理与 单环l a n 基本相同i l3 1 ，一旦环网上的某个结点要发送 信息，它必须获取在环上旋转的空令牌。一旦获得， 点 立即将空令牌改为忙令牌，并在其后附加上目的地址、 源地址、数据信息等组成一个信息帧，让其在环上传 递。这时环上的每一个结点都要检查该帧的目的地址， 若与自己的地址相一致，立即把信息复制到本结点的 适配器中，并给原帧加上已被复制的记号。原信息帧 绕环一周后，返回源结点被全部回收。待忙令牌及一 帧信息回收完毕，立即放出一个空令牌向下游结点传递。显然，在不考虑优先权等 问题的情况下，就双环中的任意一环而言，其运行特征是单令牌单帧环l a n 工作方 式。 在单环l a n 中，将令牌看作服务员，将数据帧看作顾客，就每一个结点而言， 服务员对顾客的服务通常是不连续的，即服务员对一个顾客结束服务后，不能立即 进入对下一个顾客的服务，这种服务称为间歇循环服务。一次服务开始至下一次开 始服务的时间间隔为循环时间。现以单环l a n 为例来说明这个概念i l4 | ，在每一个 结点中，一个服务员的循环周期( 也称为服务周期) 包括三部分：服务时间( 信息 青岛大学硕士学位论文 发送时间+ 信息帧头部或尾部绕环一周时间) 、信息帧的回收时间、服务间歇时间。 其中服务过程为：得到闲令牌改为忙令牌、发送信息帧一信息帧到达目的结点并被 复制一信息帧头部到达源结点。服务间歇时间则是指服务员结束对本结点顾客的服 务( 放出空令牌) 至空令牌下一次到达本结点的时间间隔，也称为单环l a n 回归 时间。单环l a n 回归时间又可看作两部分时间的和，即服务员步行环网一周的时 间加上对所有不空闲结点( 除去结点f ) 的顾客的服务时间的总和。通过上述分析可 见，单环l a n 中的循环时间最短为对f 结点的服务时间+ 信息帧的回收时间+ 服务员 步行环网一周的时间( 除f 结点外其他一1 个结点都无信息帧要发的情况) ，最长 为对f 结点的服务时间+ 信息帧的回收时间+ 服务员步行环网一周的时间+ 除f 结点外 其他一1 个结点都有信息帧要发送所需服务时间的总和。 2 2 双令牌双环l a n 排队模型的建立 2 2 i 符号设定 系统用户结点数 ， 令牌步行环网一周时间即信息帧绕环一周的时间 双令牌环中，令牌最大循环时间，即最长扩展服务时间 d 信息帧的回收时间 函令牌所占时宽 r 令牌回归时间 r 令牌最大回归时间，即除观察结点f 之外，一1 个结点都有信息要发送时， 令牌的回归时间 元重负载下，观察结点顾客的平均扩展服务时间 万 一般负载下，观察结点顾客的平均扩展服务时间 耽，重负载下，观察结点顾客的平均等待时间即扩展服务时顾客平均等待时间 既一般负载下，观察结点顾客的平均等待时间 胪顾客到达率为五时，非扩展服务员的服务率 终扩展服务员到达观察站时有顾客的概率 2 2 2 排队模型 在单环l a n 中，服务员本次到达f 结点至下次到达f 结点的时间间隔就是循环 时间，这个定义可进一步理解为当排队室顾客 1 ( 重负载条件下) 时，f 结点排在队 首及第二位的两个顾客先后开始服务的时间间隔。而在考虑双环l a n 时，如果两个 服务员的循环时间也像单环l a n 时一样独立考虑，显然是不对的。为此依据循环时 间的后一个定义：，结点排队室内连续两个顾客先后开始服务的时间间隔。对双环 4 第二章前期研究进展 l a n 做进一步分析。 岸+ 一一仁i 在前面的讨论中注意到：双环心中存 片在两个服务员a 、b 同时到达i t结点的情况，bb-征阴i 、服分贝a 、bl 口jh 习到还鲐息嗣情巩， ： ： 这里的“同时”是指到达间隔为a t ，且a t e 0 。 是2 圜。县桀循环时问诵明园嚣：这时两个服务员到达i 结点的时间间隔最 坫选 图2 2 最长循环时间说明图选芷 这时两个服务员到达结点的时j 司i 司隔最 短。显然t 应该是双环l a n 的最短循环时间。 考虑双环l a n 出现最长循环时间的情况，现以图2 2 为例予以说明。在某观察 时点t 。令牌a 第一次到达结点f 并开始为其提供服务，令牌a 开始它的循环周期。 设在a 第一次为f 的服务完成后，环网上其他结点( 即一1 个结点) 都有信息要发 送，则此时a 的间歇时间达到最长，为除f 结点外其他一1 个结点都有信息帧要发 送的时间总和。设令牌a 在到达f 后，经a t ( a t - 0 ) 令牌b 到达，设b 为f 服务完成后 进入间歇阶段时，环网上所有其他结点也都有信息要发送，显然此时一定是a 先于 b 回到结点f 开始第二次服务。根据前面分析，在这个过程中从b 第一次为f 服务到 a 第二次为f 服务的时间间隔为双环l a n 系统的最长循环时间瓦煅，于是 = 最长单环循环时间一a t = 信息帧头部绕环一周时间+ 回收时间+ 最长回归时间 一t = 什毋r 删+ a t 2 一( 1 ) 其中。显然r 一= 空令牌绕环一周的步行时间+ a 为( 一1 ) 个顾客服务的时间。 当环l a n 足够长且用户结点很多时，从理论上讲，死掰近似趋近于无穷。 在单环l a n 中，服务时间为l + d ，循环时间为z + d + r ，而在上述双环l a n 的等效 分析中，将两个物理服务员等效为1 个“扩展服务员”，将循环时间等效为“扩展服 务时间”，扩展服务时间由l x t ( a t - - 0 ) 乃瞰( 为卜丹尺+ t ) 而且由于r o c ，显 然当环l a n 足够长，用户结点很大时，x _ 0 0 ，从而使扩展服务的规律有可能 遵从一般分布。 于是，通过上述解析条件的设定和分析可以确定双令牌双环l a n 的等效排队 模型为： mg 1 ，f c f s 2 一( 2 ) 十千 + 泊这一哮- 1 展员 松般个服 到服扩务 2 _ ( ：z j 式是一个典型再达_ ；= j k e n d a l l ) 排队模型。由于我们将双环l a n 中两个 物理性服务员( 双令牌) 分别进行间歇式服务的非典型排队系统等效为1 个“扩展 服务员 进行扩展服务( 将循环时间扩展为服务时间) 的典型排队模型，使很难求 解的问题能够比较简洁精确的得到解析。 青岛大学硕士学位论文 2 3 服务时间与等待时间分析 2 3 1 服务时间分析 设观察站点顾客的平均服务时间为万，则 万= j c o f 卵( f ) = j c o 矿( f ) 出 其中，f ( t ) 为服务时间t 的概率分布，f ( t ) 为概率密度。现在的问题是必须知道 f ( t ) 的具体形式，比如服务时间满足负指数分布，则五：上，其中l a c 为服务率。由 雌 前面的分析可知，重负载下扩展服务时间应该满足均匀分布，则 7最短服务时间+ 最长服务时间，t l = = 2 f + ( 信息帧头部绕环一周时间+ 回收时间+ 令牌最大回归时间一& ) = = - - - - - - - - - - - - - - - - - - - - - - - - - - - - 。- 。- - - - 。- - 。一 2 ：! 垡! 型二! ! 型尘2 一( 3 ) = ：- - - - - - - - - - - - 一 _ 、o ， 2 将2 - ( 3 ) 式忽略的令牌所占时宽( 设为凶) 加入，得 再l-l+d+do+(n-1)x(1+d+do) 2 一( 4 ) ，2 上述h 。是在扩展服务员每次到达观察站点时，观察站点都有顾客的条件下得到 的，实际上扩展服务员到达时，观察站点可能无顾客，必须将这一因素考虑进去。 为此，设扩展服务员到达观察站点时，有顾客的概率为p g ，则平均扩展服务时间万为 万；旦：! 垡鱼! 型二1 2 兰垡垡鱼2 ：n ( t + d + d o ) 2 一( 5 ) p g2 p s 2 p 2 3 2 等待时间分析 在典型m g 1 , x , f c f s 模型中，顾客平均等待时间已经求解【1 4 1 5 1 为 形：笙垒：竺： 2 一( 6 ) 2 五( 卜“) 其中西：为方差，材为服务强度坳c 。 本文考虑扩展服务员后，服务规律满足均匀分布，因此方差最：和服务密度“为 磊：竖生皇幽丝堑二幽旦墼嬖塑! 塑兰垦莶堕塑堕塑垒巡 。 i z ：! ! 垡当坠! ：【丝垡垡鱼卫： 2 一( 7 ) 1 21 2 硝万 2 - ( 8 ) 于是，扩展服务的平均等待时间睨。为 6 第二章前期研究进展 五z n ( 14d + d o ) 2 + ( 兄瓦) ： 1 2 、 1 2 一( 9 ) ” 2 名( 1 一名是1 )2 4 2 ( 1 一兄岛) 考虑到观察结点排队室通常在非重负载条件下工作，因此 j y q = p g j y q l = p g 型掣 2 - ( 10 ) 至此，本文求得了平均扩展服务时间h 及平均等待时间睨的数学表达式。 2 4 数值计算 1 ) ，分别取3 k m ，1 0 k i n ，2 0 k s n 时求得石和随着变化的情况如图2 ( 3 ) 、图2 - ( 4 ) 所示。 2 ) 表1 与图3 表明了当环长固定时，环上的结点数增加，平均服务时间即循环 时间也随之呈线性增加，且速度较快；而当环长增加时，平均循环时间也随之增大， 但增大的幅度较小。这也说明了平均循环时间的大小主要取决于结点数的大小。 3 ) 由表2 2 及图2 。4 可见，随着环上结点数的增加，平均等待时间逐渐增长且速 度大大快于线性增长；而当环长增加时，平均等待时间也随之增大，且增大的幅度 随环长增加而迅速增大。 表2 1 元随n 和f 变化情况表 柏 5 0 1 0 02 0 0 冉 3 狮7 7 7 7 7 8 帕1 6 s 8 8 6 77 6 9 4 4 4 4 4 41 5 3 明8 8 8 93 0 7 7 7 7 7 7 8 l o3 4 6 6 8 8 8 6 76 2 0 0 ( x ) o 6 6 6 6 71 7 3 3 3 3 3 3 33 4 6 6 6 6 6 6 7 2 04 0 2 2 2 2 2 2 28 0 3 3 3 3 3 3 31 0 0 5 6 5 5 6 62 0 1 i i 1 1 1 l4 0 2 2 2 2 2 2 2 耋! ：! 坠堕生塑! 奎些堕 工 加如如l 2 0 0 屹 308 7 1 9 6 2 6 5i 3 0 3 9 1 354 5 9 1 3 6 9 1 l2 1i 朔3 5 聃1 0 3 6 2 4 4 l oi ，4 1 9 2 4 5 2 631 9 5 6 3 4 8 8i 8 8 9 7 5 3 1 53 5 6 8 9 5 7 7 0 3b 1 4 4 l 2 02 4 3 1 6 1 5 5 254 7 6 3 6 9 3 7i s 2 4 1 3 0 1 06 i2 ，0 柏2 4 1 1 3 4 2 n n 图2 3 厅随和l 变化情况 图2 4 呢随和l 变化情况 7 青岛大学硕士学位论文 第三章局域网存取方式及星型l a n 综述 对计算机网络进行系统地研究始于上个世纪八十年代，现在己经发展成了一个研 究热点。而对计算机网络的性能评价( p e r f o r m a n c ee v a l u a t i o n ) 是计算机网络和计 算机系统研究与应用的重要理论基础和支撑技术，是通信和计算机科学领域的重要 研究方向。本文正是对上述分类中星型网络进行研究，为其进行数学建模，并进行 了仿真实验。为了更好地理解后面的数学解析以及叙述的方便，下面对本文研究的 相关内容做一介绍。 3 1 局域网存取方式概述 不同用户结点如何合理存取通信介质、避免因同时存取通信介质而发生冲突是 局域网需要认真对待的最为重要的问题。为了发展计算机局域网技术，必须对介质 存取方式进行研究。网络存取方式由网管理方式和通信方式两部分组成。管理方式 指l a n 的独占方式，即如何拥有l a n 的使用权，分为集中管理、分布式管理、无 管理( 即通过自由竞争获得l a n 的使用权) 三种方式。通信方式指信息帧如何通过 介质，按照通信中源结点和目的结点的关系可分为集中通信和分散通信。本节分别 对总线形、星形和环形l a n 的介质存取方式进行了全面综述。 3 1 1 总线形l a n 存取方式 总线形是计算机局域网最常见的一种拓扑形式，如图3 1 所示。总线形l a n 的 工作站和通信介质之间的连接多数采用多点方式，即网络上所有工作站( 终端) 之 间都通过一通信介质进行报文分组交换。因此，就存在通信介质管理问题：如何不 干扰其它工作站正常工作，访问这一通信介质? 如何避免或处理由于有两个以上工 作站同时访问介质而产生的冲突7 图3 1 总线l a n i e e e8 0 2 标准规定的l a n 体系结构设立了独特的介质存取控制层( m a c ) 就 是要解决上述介质存取的问题。介质存取控制可区分为集中控制与分布控制两种方 式。集中控制要设立中心控制站，协调各站的介质存取。由于控制功能集中在中心 站，因此造成该站结构复杂，而且该站一旦失效或控制失灵将导致系统瘫痪，同时 它将成为系统信息流的瓶颈，如果处理不当，在重负荷时会降低系统的效率。集中 8 第三章局域网存取方式与星型l a n 综述 控制的优点是容易实现管理及优先服务，简化了其它站的控制功能。分布控制是将 控制功能分散给各个工作站，由工作站决定访问介质时机。该模式可有较高的可靠 性与灵活性，避免了集中控制的短处。 分布控制在各种网络拓扑中有不同的实现方法( 协议) ，就总线形而言，最为流 行的是带冲突检测的载波侦听多路访问协议( c s m a c d c a r t i e rs e n c em u l t i p l e a c c e s s c o l l i s i o nd e t e c t i o n ) ，其次是令牌传递协议( t o k e n - p a s s i n g ) 。c s m a c d 是广为应用的争用型随机访问方式。它不同于以往传统有序的控制，而是由各站以 随机的方式访问通信介质、发送信息，如发生冲突，则采取相应措施，在适当时机 重发。最早的争用型随机访问方式的实例是七十年代夏威夷大学建立的纯a l o h a 网，以后逐步演变为c s m a 总线网、c s m a c d 总线网等。 纯a l o h a 网采用两种高频无线信道，分别传送报文分组和应答信号，用作星 形结构网络的主站与多个分站的通信。分站可以不加限制随机发送报文分组至主站， 然后侦听主站的应答信号，如分站在规定时间内没有收到应答信号，则重发报文分 组，重发次数可以限定。分站在收到应答信号后，可发送下一报文分组。在分站站 数较多和通信负荷增加情况下，多个分站同时发信而产生冲突的机率加大，信道有 效利用率会急剧下降。， c s m a 是指载波监听、多路访问方式，在总线l a n 中各站采取“先听后说”， 以避免或减少冲突。由于在l a n 范围里，各站之间的传递时延大大小于报文分组时 宽，所以某站发送后，其它站随即侦听到此报文分组，此时即使有待发的报文分组， 也只能处于等待状态，直到侦听信道空闲为止。一般c s m a 方式不能完全消除冲突， 原因其一是信道忙时，如有若干站同时处于待发状态，一旦信道空闲，这些站就会 同时发送；二是在站间传播时延的短暂间隔，某个站或某些站由于未能及时侦听到 另一站开始发送，而决定发送本站的报文分组。这段时间间隔通称“碰撞窗口 。此 间隔相对报文分组的时宽不能太大，否则容易造成冲突。该原因限制了c s m a 方式 只能限于l a n 范围内应用。 先听后发的c s m a 方式虽然比前述的不听就发a l o h a 方式效率高，但还是潜 在一种影响效率提高的因素：多站发送报文分组产生冲突时，这些站仍然要坚持把 报文分组发送完毕，这对于报文分组较长的总线形l a n 来说，无疑造成较大的时间 浪费，因此，x e r o x 公司在1 9 7 5 年研制和生产以太网( e m e m e t ) 时，采用了带有冲 突检测的c s m a 协议，把“先听后说 加上“边说边听”，称之为c s m a c d 本站 在发送时，如发现自己“说”的与“听 的有异，则说明发生了冲突，此时立即中 断报文分组发送，而送出了一个较强的阻塞信号，告之各站出现了冲突，此后冲突 各方随机延迟一段时间，再按c s m a 方式处理。 除了c s m a c d 方式外，总线形l a n 还有一种称为令牌总线( t o k e nb u s ) 的 9 青岛大学硕士学位论文 令牌存取控制协议。总线形l a n 1 6 , 1 7 】在物理结构上不是环，不适于令牌旋转，但可 以人为规定循环顺序，构成逻辑上的环。如图3 2 所示的称为令牌的特殊脉冲序列， 沿着a 叶e _ c _ d _ b _ a 叶的逻辑环循环传递。令牌是发信权的凭证，在l a n 上只有一个，有报文分组待发的站获得令牌后方可发信。此后，再把令牌传送给逻 辑环下一个工作站。令牌到站时，如该站没有报文分组，则令牌随即送至下站。 图3 2 令牌总线l a n 令牌总线l a n 在上电后，逻辑顺序是确定的，增加或减少工作站时，需要更改 逻辑顺序，还需要有其它相应运行管理措施。令牌传送总线l a n 各站发信机会均等； 容易实现优先级方式通信；不存在冲突；负荷变化时，对系统延迟特性影响较小； 适合实时通信，如文件传送、传真电报等。但是，在负荷轻时，有报文分组待发的 站需等待令牌到来，时延稍长，这是它的缺点之一。c s m a c d 方式与令牌传递比 较，优缺点反之。虽说c s m a c d 各站发信机会平等，但总有可能在重负荷时，某 站的报文分组发送一再冲突，而较长时间成功不了，此时，不仅影响本站后续报文 分组的发送，还会导致延时的不确定性，从而限制了在实时系统的使用。但是，c s m a c d 非常适合发送信息具有突发性的计算机通信系统，而有这种特性的系统是广泛 存在的，因此，c s m a c d 存取控制方式已成为当今l a n 的主流之一。 3 1 2 环形l a n 存取方式 环形l a n 如图3 3 所示，由若干工作站( 结点) 和站间链路组合成闭合回路。 工作站通过站接口与环网相连，报文分组单方向从一个工作站传至相邻的另一工作 站。每个工作站的接口是有源的，报文分组通过时，经短暂延时后向前传送。因此， 工作站及其接口应具备以下几种功能：发送报文分组，接收报文分组，中继 报文分组，删除( 回收) 报文分组。环形l a n 是l a n 的主要类型之一。环形l a n 的结构特点在很大程度上决定了它特有的存取方式。 环形l a n 由于是多个工作站共用一个环路，所以必须对各工作站发送报文分组 进行控制。目前已研制了众多的存取控制方式不同的环形l a n ，其中主要有令牌环、 时槽环和寄存器插入环。最著名的环形l a n 是i b m 令牌环。下面将分别叙述其存 取方式。 1 0 第三章局域网存取方式与星型l a n 综述 干线耦合器 图3 3 环形l a n 令牌环形l a n 令牌环 1 8 - 2 1 】( t o k e nr i n g ) 是环形l a n 的主流，令牌控制技术 最早于1 9 6 9 年在贝尔实验室所研制的n e w h a l l 环上使用，以后i e e e 8 0 2 把令牌技术 作为局部网络介质存取访问方法的一个标准，即i e e e 8 0 2 5 t 2 2 ，2 3 1 ，该标准是在i b m 令牌环的基础上修订的。 令牌方式是在环网内按一定方向和顺序在各工作站传递令牌，获得令牌者有权 发送该站待发的报文分组，发送完毕后再把令牌传给下一站。工作站得到令牌而无 报文分组时，随即把令牌送往下游的邻站。各站获取发信权机会是相等的。令牌通 常是由特定模式的一个字节和多个字节的脉冲序列组成。例如单字节令牌，其中规 定8 位的某一位为0 时，该序列称空令牌，表示没有站发送；此位反转为1 时，称 忙令牌，表示有站正在发送。或者相反规定。有报文分组发送的站，必须等待空令 牌到来，一旦空令牌传至该站接口，便将指定位变为1 ，接着在忙令牌后发送报文 分组。此时在环网上无空令牌，所以其它工作站不能发送，只是起转发作用。目的 站在识别报文分组中的地址码后，在转发同时，还复制报文分组至本站的接收缓冲 器。 依照发送报文分组的工作站生成( 释放) 空令牌时机的不同，令牌环分作单令 牌单帧( 单报文分组) 协议，简称单报文分组令牌协议；单令牌非单帧协议，简称 单令牌协议；多令牌协议阱】。 ( 1 ) 单报文分组令牌协议。源站在完全回收忙令牌和报文分组后才放出空令牌， 因此环网上至多有一个报文分组，故称单报文分组令牌协议。 单报文分组令牌协议为该令牌环l a n 建立物理模型( 这里为排队模型) 提供了 物理基础。下边进一步分析该环l a n 所具有的特征。 该环l a n 由l ，2 ，n 号结点( 工作站) 和一条主环路构成。每个工作站 的信息帧随机产生( 也称到达，其到达时间间隔是随机变量) ，且在各个站形成排队 队列。如果将产生的信息帧看作顾客，则顾客到达哪一个队列排队是预先确定的。 在各个站排队的信息帧，如果已经排到队首并且该站已经获得了空令牌，则立 即发送队首的信息帧，受到l a n 的服务。因此可将环l a n 看作排队系统中的服务 员，故服务员为1 人。 1 1 青岛大学硕士学位论文 信息帧的长度是一个随机变量且遵从某一分布。在环形l a n 中，数据帧的服务 时间通常并不仅仅取决于数据帧的长度，还可能取决于信息帧的传送距离和l a n 的 长度。但在令牌环形l a n 中，由于数据帧都要绕环一周，故可认为信息帧传送距离 造成的延迟时间相同。那么，环网对每个信息帧的服务时间分布仅依赖于数据信息 长度的分布。 某一结点排队于队首的第一个信息帧被环网服务结束后，空令牌就要传递到下 一站点。只有当下一站点得到空令牌，环网才能开始对该站点的信息帧进行服务( 即 传送) ，故可将令牌的传递看作服务员由一个队列步行到另一队列去进行服务。通常 令牌的移动时间是随机的，故服务员步行时间可看作具有某种分布的随机变量。 环l a n 中各个站点发送信息帧的情况，相当于服务员服务结束一个顾客，步行 到下一站点继续服务，依次将服务进行下去( 如果某一站点无排队顾客，则经过该 站点对再下一个站点继续服务) 的移动式服务系统。从多队列的整个系统看，服务 员移动进行循环服务，但从某一个队列看，服务员进行间歇式服务。这种服务对每 一个队列的顾客来说是先来先服务，而且每个顾客都不能改换队列，也不能中途退 出，但对整个系统来说，顾客的服务并不是先来先服务。 通过上述分析可见，单报文分组令牌协议的排队模型是不能用典型肯达尔排队 模型来描述的。由于服务员巡回在个窗口进行服务，因此它只能是以移动服务来 实现的多重排队模型。 注意：上面将环l a n 的物理介质设成服务员，在单报文分组令牌协议中，这种 设定与将令牌设定为服务员是一致的。 ( 2 ) 单令牌协议。源站发送报文分组后，只要完整回收忙令牌，即可放出空令 牌，因此环网上只有一个令牌( 忙令牌或空令牌) ，故称单令牌协议。由于某一个工 作站送出空令牌，且正在回收本站报文分组时，其它下游站获取空令牌之后即可发 送报文分组，所以环网上可能同时有一个以上报文分组的信息在运行。 单令牌协议和单报文分组令牌协议虽然都具有一个令牌，但依据空令牌生成时 间的不同而将它们区分开来。信息帧循环一周返回源站时，如果前方的忙令牌一删 除即放出空令牌，则为单令牌协议；如果返回的忙令牌和信息帧全部删除后才放出 空令牌，则为单报文分组令牌协议。两种协议性能解析的区别由此而来，下边予以 分析。 单令牌环l a n 也由一条主环路构成，如果象单报文分组令牌协议一样，也将信 息帧在主环路上的传递看作服务员对顾客的服务，即将主环路看作服务员，则给排 队模型的建立带来困难。这是因为单令牌环l a n 往往会出现两帧的信息同时运行于 环网上，不能在时间上将服务员对不同顾客的服务截然分开。为此。只能将令牌当 作服务员，设定一帧信息的服务时间为忙令牌绕环一周的时间。 1 2 第三章局域网存取方式与星型l a n 综述 然而，设定令牌为服务员后，当服务员为另一队列顾客服务时，还未完全返回 的信息帧必然没有服务员服务在“顾客身旁”。但仔细分析可见，这种情况不会影响 环l a n 的性能分析。设定令牌为服务员后，服务为定常分布服务。 顺便指出：在单令牌协议中，一般要求信息帧的长度不大于环路的长度，即信 息帧的时宽不大于环路的时延。 由上可见，单令牌协议和单报文分组协议性能分析的主要区别在于：单报文分 组令牌协议的服务为一般分布，单令牌协议的服务为定常分布。如果将单报文分组 令牌协议的报文分组设定为定常，则它的服务也为定常分布。这时两种协议的解析 过程是完全一致的。 ( 3 ) 多令牌协议。源站在发送出忙令牌和报文分组之后，立即生成一个空令牌 挂于报文分组之后，下游站收到空令牌后，也同样将空令牌改为忙令牌、后面紧跟 发送的报文分组，接着再生成一个空令牌。当然，环网长度与报文分组时宽要配合 好，使该网能同时容纳多个包含忙令牌的报文分组及一个空令牌，以免源站还未生 成空令牌而本站开始发送的忙令牌返回后要求自己回收。 与其他令牌环协议相比，多令牌协议的主要特征如下。 a ：获得空令牌的站，将排在队首的一个信息帧发出，受到l a n 的服务，由于 该环再物理结构上也只有一条主环，因此该系统看做存在一个物理性服务员。然而， 站点f 排在队首的一个信息帧正处在服务状态时，f + 1 、f + 2 等站的信息帧也先后被 环l a n 服务。于是，就出现多个信息帧先后由一个物理性服务员开始服务、并且同 时持续服务的局面。这种服务既不同于单一服