（计算机软件与理论专业论文）轮询方式综合业务总线lan的优先级控制探讨.pdf

摘要 现代计算机通信网j 下进入宽带综合业务数字网( b i s d n ) ，其服务业务包括话音、 数据、传真和视频等。每种业务都有不同的统计特性并需要不同的服务质量( q o s ) 。 为了充分利用网络资源并满足每种业务的q o s ，需要进行优先级控制。而且，为了 传输综合业务，还需要对原有网络协议进行改进。 轮询方式是一种比较成熟的局域网介质访问方式，从它诞生以来一直受到广泛 关注。本文为了探索轮询访问方式在综合业务总线l a n 中的应用，对原有的轮询方 式进行了改进，提出了“改进型轮询方式”，不仅大幅度缩短了高优先级业务滞留系 统的时间，而且适当兼顾了低优先级业务的服务质量，使得整个网络传输综合业务 的性得以较大改善。 在对“改进型轮询方式”的优先级策略深入研究的基础上，经过仔细分析，本 文对基于轮询方式综合业务总线l a n 的系统提出了扩展排队模型( 即肯达尔 k e n d a l l 模型) l d l k i p r ，然后对该模型进行了数学解析。仿真实验表明，“改 进型轮询方式”显著改善了系统性能。该研究进展不仅具有理论创新，而且扩展了 轮询控制方式在综合业务总线l a n 中的应用。 关键词：轮询；优先级：建模研究：综合业务 a b s t r a c t m o d e mc o m p u t e rc o m m u n i c a t i o nn e t w o r ki sh e a d i n gf o rb i s d n ，w h i c hi n t e g r a t e d v a r i o u st r a f f i c ss u c ha sv o i c e ，d a t a ，f a xa n dv i d e o e a c ht y p eo ft r a f f i ch a sd i f f e r e n tt r a f f i c c h a r a c t e r i s t i ca n dr e q u i r e sd i f f e r e n tq u a l i t yo fs e r v i c e ( q o s ) t h u s ，ap r o p e rp r i o r i t y c o n t r o lm e c h a n i s mi sn e e d e di no r d e rt ou t i l i z et h en e t w o r kr e s o u r c e se f f i c i e n t l ya n d s a t i s f yt h eq o so fe a c ht r a f f i c w h a t sm o r e ，i no r d e rt ot r a n s m i tt h ei n t e g r a t e ds e r v i c e ， w en e e dt oi m p r o v et h eo r i g i n a lp r o t o c 0 1 p o t t i n gs t r a t e g yi saf u l l y f t e d g e dm a cp r o t o c o l ，i th a sa t t r a c t e dt h ew i d e l ya t t e n t i o no f p e o p l e i no r d e rt od i s c o v e rt h ea p p l i c a t i o no fp o l l i n gm a cp r o t o c o 【i nt h ei n t e g r a t e ds e r v i c eb u s l a n ，w ei m p r o v e dt h ef o r m e rp r o t o c o l ，a n dt h e “i m p r o v e dp o t t i n gp r o t o c o l ”w a si n t r o d u c e d i t n o to n t yd e c r e a s e st h ed e t e n t i o nt i m eo ft h eh i g hp r i o r i t yt r a f f i c ，b u ta l s oe n s u r e st h eq o so f l o w e rp r i o r i t yt r a f f i c t h u s ，t h ep e r f o r m a n c ei sg r e a t l yi m p r o v e d b a s e do nt h ed e e pr e s e a r c ho nt h ep r i o r i t ys t r a t e g yo ft h e “i m p r o v e dp o t t i n gp r o t o c o l ”， t h r o u g hs e r i o u sa n a l y s i s ，i nt h et h e s i s ，w ep r o p o s ea ne x t e n d e dk e n d a t tm o d e lf o rt h ei n t e g r a t e d s e r v i c eb u s ta ns y s t e mb a s e do nt h e p o t t i n gm a cp r o t o c o l ( s o - c a t t e d k e n d a t tm o d e l ) l d l k 1 p r ，a n dt h e n ，w ea n a l y s et h em o d e la b o v e s i m u l a t i o nr e s u l t ss h o wt h a tt h e “i m p r o v e dp o l l i n gp r o t o c o l ”i m p r o v e st h ep e r f o r m a n c er e m a r k a b l y t h er e s e a r c hi sn o t o n l yw i t ht h ei n n o v a t i o ni nt h e o r y , b u ta l s oe x p a n d st h eu s eo ft h ep o l l i n gm a cp r o t o c o li n t h ei n t e g r a t e ds e r v i c eb u sl a n k e yw o r d s ：p r i o r i t y ；p o l l i n g ；m o d e l i n gr e s e a r c h ；i n t e g r a t e ds e r v i c e 学位论义独创性声f 、学位论文知识产权权属声f u j 学位论文独创性声名 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名：王埏 日期：沁，年y 月日 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密瓯 ( 请在以上方框内打“”) 同期：哼年，月ii - f i f t 期：p 姑年y - 月，1p l ( 本声明的版权归青岛大学所有，未经许可，任何单位及任何个人不得擅自使用) 3 9 第一章0 i 击 1 1 综述 第一章引言 计算机通信网络发展的早期，数据传输的优先级控制策略就得到重要应用。而 现代计算机通信网正进入宽带综合业务数字网( b i s d n ) ，其服务业务包括话音、视 频、数据、传真等。每种业务都有不同的统计特性并需要不同的服务质量( q o s ) 。为 了充分利用网络资源并满足各种业务的q o s ，更需要进行优先级控制，即根据不同 业务传输时延的要求，将各类业务标以不同的优先级。 在综合业务l a n 中，优先级问题是一个热门的研究课题。常见的有基于访问控 制方式c s m a c d 总线的，有基于令牌总线的，有基于令牌环的。本文探讨基于轮 询方式总线型l a n 的综合业务优先级控制问题。在综合业务网中，不同的业务对实 时性的要求有所不同，要求网络提供不同质量的服务，对于那些对实时性要求比较 高的业务，需要网络优先为其提供服务。本文首次提出的“改进型轮询方式”，较好 的改善了网络性能，扩展了轮询介质访问方式在综合业务总线l a n 中的应用。 1 2 局域网介质访问方式 所谓访问方式就是指网络各结点如何管理、控制介质，即如何拥有介质的使用 权。 在计算机网络中，若干用户共享信道是常见现象。通常有两种方法：多路复用 信道，多点访问信道。最典型的多路复用信道是将若干用户用集中器或复用器连接 起来与主机通信。在集中器( 或复用器) 与主机之间用高速线路连通，高速线路由若 干用户共享，共享高速线路时采用时分复用技术或频分复用技术。目前，多路复用 信道的方法已经很成熟。多点访问信道是通过一个公用信道将所有用户都连接起来。 其连接形式有多种，但存在一个共同的问题是要设法避免不同用户同时使用公共通 道，否则就会发生冲突。在计算机局域网中的信道共享主要用多点访问信道方法。 为此，局域网在m a c 层使用了介质存取控制的方法。下面对常见介质存取方式进 行简要阐述，各种介质存取方式详细的物婵运行机理可参见相关文献【，限于篇幅， 不再赘述。 轮询轮询是网上主机按一定顺序逐个询问各用户有无信息发送，如有信息发送， 则被询问的用户立即将信息发给主机：如无，则接着洵问下一用户站。轮询分为轮 叫轮询和传递轮询。 。 预约先安排各站点利用信道的顺序，然后按安排顺序发送数据的访问方法，称为 青岛人学倾i j 学位论义 预约。着一点与同常生活中的预约完全一致。为此，网上各站点按两个阶段工作； 预约阶段与数据传送阶段。预约分为集中预约与分布式预约。 令牌控制在此只概述单报文分组令牌方式，其它令牌控制方式可参见相关文献l i j 。 典型的应用是i b mt o k e nr i n gl a n ，该访问方式的特点是：获得令牌的站点每次 只能发送一个信息帧( 为非穷举式) ，若有多帧信息要发送，必须依次排队等待下一 次令牌的到来。源结点发送的帧在目的站点被复制接受后，返回源结点被回收滤 除。原发送结点回收忙令牌及其后的信息帧之后，才放出一个闲令牌，因此该方 式的环状l a n 最多只有一帧数据，故称单报文分组令牌方式。该方式j 下是i e e e 8 0 2 5 的介质访问方式。 冲突限制方式冲突限制方式往往是将两种以上访问方式混合起来使用的访问方 式。当网络负载较重时，自动转向使用无冲突的访问方式，以防止因可能出现较多 冲突而使网络使用效率低。反过来，当网络负载较轻时，自动转向有冲突的访问方 式，这是因为当轻负载时，引起冲突的可能很小。再者，有冲突的访问方式往往有 较少的额外开销( 比如不出现预约中出现的预约时间片组开销等) ，很适于轻负载状 态下工作。由此可见，冲突限制方式是一种折中方案，在重负载时，使用无冲突的 访问方式，可得到高的利用率；在轻负载时，使用有冲突的访问方式，以便减小时 延。冲突限制访问方式主要有两种：自适应访问、缸( u r n ) 访问。 随机访问a l o h a2 0 世纪7 0 年代美国夏威夷大学研制的网络系统名为 a l o h a f a d d i t i v el i n ko n 1 i n eh a w a i is y s t e m 是夏威夷方言，译文为“您好”) ，该 系统使用无线电信道。它允许各用户工作站随机地向中心结点的计算机发送信息， 而由中心结点到各用户工作站采用广播式通信。像这样允许用户工作站随机访问中 心结点的方式就是最早的随机存取方式，起名为a l o h a 。 c s m ac s m a 为载波监听，多路访问。c s m a 访问方式是在a l o h a 基础上提出 的。与a l o h a 相比，c s m a 必须判断信道状念也就是监听信道上是否有其他站发 送数据的载波，当无载波时就认定信道空闲。只有信道空闲时才可能发送自己的数 据，从而减少了发生冲突的可能性。c s m a 分为非峰持型c s m a 和坚持型c s m a ， 其中略持型c s m a 又包括1 坚持型c s m a 和p 一坚持型c s m a 。 c s m a c d 和c s m a c ac s m a c d ( c a r r i e rs e n s em u i t i p l ea c c e s s c o l l i s i o nd e t e c t ) 即载波监听多路访问冲突检测方法，是一种争用型的介质访问控制协议。它起源于 美国夏威夷大学开发的a l o h a 网所采用的争用型协议，并进行了改进，使之具有比 a l o h a 协议更高的介质利用率。c s m a c d 控制方式的优点是：原理比较简单，技术 上易实现，网络中各工作站处于平等地位，不需集中控制，不提供优先级控制。但 在网络负载增大时，发送时间增长，发送效率急剧下降。c s m a c d 应用在i s 0 7 层早 的数据链路层，它的工作原理是：发送数据自订先监听信道是否空闲，若空闲则立即 2 第一章i j l 言 发送数据。在发送数据时，边发送边继续监听。若监听到冲突，则立即停止发送数据。 等待一段随即时间，再重新尝试。与c s m a c d 相比，c a 是冲突避免，c s m a c a 进行 两次检测判空，第一次判空与c s m a c d 一样，判空后随机延时6 。而第二次判空是 在6 后立即发生的，是用硬件高速判定，一旦信道空闲，立即发出数据。如果第二 次判明信道非空闲，则随机延时后重新开始第一次载波监听。 冲突淘汰访问方式与冲突限制方式和冲突后退方式相同的一点是冲突淘汰访问方 式也有冲突，但处理冲突的手段截然不同。冲突淘汰访问方式的要点是：发送到中 心结点( 对星状拓扑) 的数据单元，要通过中心结点时，虽然有空闲信道，但如果同 时要求通过中心结点的数据单元多于空闲通道数，就会发生冲突。此时中心结点从 发生冲突的多路数据单元中随机选择相当于空闲通道数的数据单元让其通过，剩余 的数据单元被淘汰，被淘汰的数据单元经超时处理后由源工作站重新发送。 1 3 局域网优先级控制策略 局域网一般是多个结点共享传输介质，在一个结点发送数据之前首先要解决由 哪个结点占用传输介质，妥善解决共享通道而有可能发生冲突的问题。局域网的主 要标准有：i e e e 8 0 2 3 、i e e e 8 0 2 4 、i e e e 8 0 2 5 、i e e e 8 0 2 6 、f d d i 。这些协议标准 有的原来并没有优先级控制，如1 9 8 0 年颁布的i e e e 8 0 2 3 标准主要针对数据交换， 而不提供服务质量和优先级控制。千兆以太网继承了这一协议，也就继承了它的缺 点。因此，千兆以太网虽然具有速度快且简单实用的优点，却不能提供真正意义上 的服务质量q o s ，从而不适用于对延时敏感的多媒体应用等实时业务。 时至今同，实现q o s 很重要的一个要求是能够进行优先级控制。因此，人们尝 试在原来没有优先级机制的协议中引入优先级，或对原来就有优先级机制的协议进 行改进，以期让它们能够提供更高质量的优先级服务，局域网中的优先级机制一般 属于时间优先级。 将预约机制引入以太网实现优先级控制 基本思想是：在每个以太网结点内部都维持一张预约表，表的长度足网内结点 的数目，每一个表项对应一个节点，表项内容包括逻辑结点号、是否预约和预约的 优先级。初始化预约表的过程如下：将冲突后的以太网传输时间划分为一个个时i 白j 片，在每个时间片里，节点根据自己的逻辑节点号顺序依次申明自己的预约和所要 求的优先级。网上的所有节点聆听这些申明，并据此更新自己的预约表。 由逻辑节点号和预约优先级共同决定发送次序，高优先级的预约先于低优先级 的预约得到满足，同级预约中逻辑节点号低的先于逻辑结点号高的得到满足，未进 行预约的帧必须等到高优先级或同级预约被满足后才有资格发送。每一个节点都必 须遵守这张预约表，但是未预约的高优先级帧可以中断低优先级帧，优先发送，而 青岛人学硕i ：学位论义 被干扰的低优先级帧必须多等待一个帧的时间彳能按预约表发送j 。 采用预约表可以有效降低网络的冲突率。与传统的c s m a c d 算法相比，它能 实现在保证低负荷情况下的低等待时间的同时，实现重负载情况下极低的冲突率。 该方法的另一个优点是采用分布式优先级控制，在每一个节点内维护一个预约表， 而不是采用一个中心控制节点来实施优先级控制。这虽然付出了一些内存上的代价， 却继承了以太网分布式控制的思想，增加了可靠性、健壮性和实现上的简单性。 轮询中的优先级机制 轮询系统是多个独立的信元共享一个设备的系统，此设备一般为传输信道。其 基本工作过程为：在网内有一个中央控制器及服务器担任对每一个站点的探询工作， 探询按顺序进行，两个队列之间的探询时间称为步行时间，接收探询的队列获得访 问信道的机会，如果该站有要发送的数据，它可以利用信道的全部数据速率将数据 送往目的地；否则，中央控制器继续对下一个队列探询i j j 。 在轮询系统中设立优先级机制的方法很多，比如在中央控制器中设霄优先级， 优先级的大小根据当前网络运行状态没定，当中央控制器对每一个站点探询时，在 接收探询的队列中只有优先级等于或高于中央控制器优先级的数据才能被送往目的 地，而低于中央控制器优先级的数据将得不到服务。 i e e e 8 0 2 3 中的分优先级控制机制 在i e e e 8 0 2 3 中用户共享传输介质，由于采用随机接入来存取介质，就可能出 现多个用户同时发送信息而冲突，这时冲突各站都要后退重发。有关文献提出了多 优先级随机接入算法( r a a u m p 算法) ，此算法可以在系统接近拥塞时，有效地拒绝 低优先级业务，保证高优先级业务的业务质量。又有人对其进行了改造，提出了一 种分优先级随机接入算法【4 】，大致思想是采用以太网的冲突后退方式，只是当冲突 发生时，让高优先级数据后退一段很短的时间重发，而低优先级数据后退一段较长 的时间重发，从而保证了高优先级数据的尽快发送。 i e e e 8 0 2 4 中的优先级控制 i e e e 8 0 2 4 令牌总线网协议也有相应的优先权机制，站内为各优先级设置独立 的缓冲区，当某工作站点接到令牌时，令牌在站点内部从最高优先级传往最低优先 级。当某一级别接到令牌后，在此级别缓冲区排队的信息将被传送，直到队长为0 或计时结束。有关文献导出了i e e e 8 0 2 4 令牌总线网在重负载条件下的循环时间和 吞吐量指标，在假设各级的信道并不总是满负荷的条件下，要导出平均循环时问和 平均信元服务时间的分析表达式是十分困难的。在很多文献中，对这类情况的处理 是对每级求出它的平均循环时问和平均信元服务时间的上下限，而非具体的提出表 达式。针对这点不足，有关文献【5 i 研究了i e e e 8 0 2 4 标准协议各项性能指标的一般 算法，算法中重点考虑了i e e e 8 0 2 4 标准协议用于实时通信的4 类通信优先级别，2 4 第一章引苦 中类型时间控制器：令牌保持时间和令牌循环时间。此外还考虑了网络中各站点具 有有限的缓冲区容量、不同的信元产生率和不同的网络服务时间等参数的限制。文 献1 6 j 对i e e e 8 0 2 4 标准协议优先级准公平性进行了研究，对原有的i e e e 8 0 2 4 协议做 了如下两点改进：为4 类、2 类、o 类优先级信息帧分别设立了目标令牌循环时间， 且满足m 死 t t r 磊 丁册乃。从而适当照顾了低优先级信息帧的发送：为4 类子 域设定了高优先级中断策略，防止了某站有4 类帧而不能发送，却有可能发2 类、0 类帧的优先级倒置局面出现。改进协议在确保高优先级信息优先得到服务的同时， 兼顾低优先级信息得到一定的服务。 i e e e 8 0 2 5 中的优先级控制 i e e e 8 0 2 5 令牌坏协议是一种常见的局域网协议，令牌环是依靠介质( 电缆) 连 接若干工作站的环状局域网络。源工作站产生的数据信元循环传送于介质环的其它 工作站，最终被目的工作站接收。令牌标志着发送权，不携带数据帧的令牌为闲令 牌，闲令牌到达某站，如该站无数据要发送，则迅速通过，如果有信息数据要发送， 则将闲令牌改为忙令牌，随后携带发送数据向下游传送。每个工作站的数据根据缓 急轻重分为若干个优先级，为了让优先级高的数据优先级得到发送，令牌具有优先 级和预约级，只有某站要发送数据的优先级不低于经过该站的闲令牌的优先级时， 才能发送。当经过该站的是忙令牌或是一个不能利用的闲令牌时，则可以通过预约 来竞争下一次的发送权，详细情况可参加文献盯1 。有关文献陋9 1 对 e e e 8 0 2 5 令牌环 协议优先级准公平性也进行了研究，在确保高优先级信息优先得到服务的同时，兼 顾低优先级信息得到一定的服务。 分布式队列双总线( d q d b ) 中的优先级控制 i e e e 8 0 2 6 城域网标准一d q d b 网包含两条数据流向相反的单向总线，是基于优 先级接入控制的分布式排队概念。d q d b 的主要特点是它的m a c 比较简单，在网络轻 载时可以充分利用网络的容量( 带宽) ，且不依赖于网络的大小和数据速率。但在重 载时，由于d q d b 结构本身不对称的特点，使得上游结点比下游结点有更多的机会利 用空时隙来发送信元，而下游结点则比上游结点有更多的机会利用时隙来发送信元， 而下游结点则比上游结点有更多的机会发送请求信息。另外，上游结点低优先级的 业务也会推迟到下游结点高优先级业务的发送。 针对上述不足，有关文献旧1 提出了扩展计数带宽平衡机制e c b w b ( e x t e n d e d c o u n t i n gb w b ) 。带宽平衡( b w b ) 机制的基本思想是：网上的结点并不全部使用提供 给它的带宽，而是放弃一部分带宽的使用权留给下游结点使用。它为每个结点设置 了一个带宽平衡模数( b w b m o d ) ，以便限制结点对带宽的使用权。扩展计数带宽平衡 机制e c b w b 使用多优先级管理机制和带宽平衡机制，实现具有优先级控制的带宽平 衡。在e c b w b 机制中，设置三个带宽平衡计数器，分别统计对应结点的三种优先级 青岛人学硕l j 学位论文 信息端发送成功的次数。计数器c d i 保存各结点相应的优先级信息，其增值是优先 级级别的函数：高优先级信息的计数器值小，低优先级的计数器信息值增大，这样， 在结点处于“递减计数”状态时，由于高优先级的c d 计数器值小，递减至o 快，低 优先级的c d 值大，递减至0 慢，从而保证优先级高的信息可以获得空槽发送信息， 因为只有c d = o 时才可以获得空槽。带宽平衡的门限值b w b - m o d 的大小可以根据网络 活动结点数动态调整，当活动结点较多而需占用较大的带宽时，降低门限值以便释 放更多的带宽；反之，如果当前网络活动结点较少，则将门限值凋高一些，以便提 高吞吐量改善网络性能。 上述针对d q d b 控制机制进行的探讨，目的在于实现具有优先级控制的带宽平 衡。有关d q d b 的性能分析也是近来学术界研究的一个热点。例如d q d b 城域网的稳 态和暂态公平性，信元的等待时间，实现局域网互连时的性能。 光纤分布式数据接口( f d d i ) 中的优先级控制 光纤分布式数据接口f d d i 是一个高性能的光纤令牌环l a n n 引，能提供l o o m b p s 的传输速率。典型的f d d i 网是由两条独立的传输方向相反的环组成，但进行数据传 输的始终是一个环形线路，与单坏令牌网类似，为了实现优先级控制，f d d 采用“时 控令牌协议”，提供同步数据服务和异步数据服务。网络初始化时，由各站点协商“目 标令牌循环时1 白j ”( 记为厂册力然后静态地为每个站点( 如观察站j ) 分配同步传输时 i 日j 蜊j ，“同步传输时间”是在每次令牌到达站点时，该站点可进行同步传输的最长 时间。此外，刀r 7 1 一y 刚，时间被动态的分配给网上的各站点用于异步服务。 ， f d d i 的运行机制是这样的：当令牌到达某站点，时，站点j 如有数据要发送， 则将令牌从环上取下，将待发的同步数据帧发到环上，最大可能是分配给此站的“同 步传输时暗j ”用完后停止同步数据帧发送。之后如果还有“异步传输时间”，则可继 续发异步数据帧，直到“异步传输时间”用完，或者在此之前该站的异步数据全部 发完。随即在数据帧之后挂一个令牌，供下游站使用。如果站点没有待发数据( 包括 同步数据和异步数据) ，则直接将令牌转发，每当运行的数据帧经过目的站点时，数 据立即被复制到该站的缓冲区中，并给原帧加上“已被复制”的记号。该帧继续运 行，绕环一周返回源站点被回收。 6 第_ 二章奉义前期研究进展 第二章本文前期研究进展 2 1 基于轮询方式综合业务总线l a n 的优先级控制 本毕业论文的前期研究工作，对基于轮询方式综合业务总线l a n 的优先级控制 进行了初步探讨，提出了“改进型轮询访问方式n 。 2 1 1 “改进型轮询访问方式的提出 传递轮询概述。轮询是人们比较熟知的访问方式，但为了探讨综合业务的优先级 机制，仍需对该访问方式略加阐述。轮询是网上主机按一定顺序逐个询问各工作站 有无信息发送，如有信息发送，则被询问的工作站立即将信息发给主机；如无，则 接着询问下一站。轮询分为轮叫轮询和传递轮询。轮叫轮询，是主机从站1 丌始逐 个轮询，站1 如有信息，立即发给主机，站l 如无信息，则向主机发送一种控制帧， 表明无信息可发。随后，主机询问站2 ，依次类推。从站1 到站循环访问，循环 发送信息；传递轮询，也称集中查询，主机先向站发出轮询帧，站在发送的信 息帧( 如果当时有信息的话) 或者控制帧( 如果当时无信息的话) 之后，将其相邻站n - 1 的地址附上，由此站- l 得到查询，依次类推，能实现一个循环周期的轮询。在下 一个循坏开始时，主机再向站发出轮询。传递轮询实为轮询信号传递。如果主机 在一次循环轮询完成，收回轮询信号后，无停留地把轮询帧发给站，传递轮询与 i e e e 8 0 2 5 的令牌环协议非常相似。 通过上述轮询协议的运行机理可以看出，基本的轮询访问方式对不同类型的业 务没有区分优先级别。当轮到某一工作站时，只要有帧即可发送。因此，不能为不 同类型的业务提供不同质量的服务，不适合综合业务的传输。显然，将轮询访问方 式应用在综合业务总线l a n 上，需要对原协议进行改进。 “改进型轮询访问方式 的提出。设网络中存在三种业务话音、视频、数据， 它们分别对应三种优先级0 勿1 锻、2 级，优先级依次降低。每个工作站有一个缓 冲区，设定缓冲区的容量为1 ，当到达缓冲区的一帧信息未被服务之前，本站不再 产生新帧，新产生帧的优先级由工作站自行确定。新协议采用传递轮询方式，按照 站号从高到低的顺序进行轮询。新协议将原来的“轮询”改称为“询问循环”。设定 一次“询问循环”包括两轮轮询。如果将一次“询问循环”称为“大轮询”，一轮轮 询称为“小轮询”，则“大轮询”包括两轮“小轮询”。小轮询时，对所有工作站只 服务同一种优先级别的帧。在一次大轮询中，第一轮小轮询只让有0 级帧的工作站 发送，那些有l 级、2 级帧的工作站在接到轮询帧后并不发送帧，而是立即把轮询 帧传递给下一相邻站；第二轮小轮询只让有l 级帧( 也可能是2 级帧) 的工作站发 青岛人学坝一【：学位论义 送，究竟是只让有l 级帧的站发送还是只让有2 级帧的站发送，第二轮小轮询开始 时由主机随机确定，按协议主机选取1 级的概率大于2 级。当然也可以在第一轮小 轮询中让有l 、2 优先级帧的工作站预约，在按概率确定第二轮小轮询中服务优先级 级别时，控制站将预约的信息作为一个因素予以考虑，这种情况将待研究取得进展 后另行报告。 2 1 2 协议运行过程及平均最大滞留时间分析 参数设定 本文通过平均最大滞留时间来对原协议和改进协议进行性能评价。为了计算平 均最大滞留时间，必须先求出最大滞留时间，考虑到每轮轮询从号站开始，因而 计算信息帧的最大滞留时间，只有设定1 号站为观察站，且每一轮轮询中l 号站均 有信息帧等待服务，而且要求该信息帧是在本站前一个信息帧发送结束后，立即产 生的。为分析协议性能，须首先对协议的运行过程进行阐述，并设定各类参数如下： m ：网络丌始运行时设定的最大轮询圈数，本论文中设定m = 1 0 0 0 0 m ：当前轮询圈数 ：第m 轮的轮询帧经过观察站时，观察站信息帧的滞留时间。按协议该信息 帧是上次发送后立即产生的。 r ：信息帧时宽 如：轮询帧在相邻工作站之间的步行时间，本论文中设定岛= l 疗：工作站总数 p ：第二轮小轮询主机选择只对1 级( 或2 级) 帧进行服务的概率，当选择1 级 时，p - p l ；当选择2 级时，p _ p 2 。p l = l p 2 p ：轮询帧到达某一工作站时，工作站有信息帧的概率，本论文中设定p = o 5 g ：在原协议中，观察站发送信息帧的总量 c j i ：在改进协议中，当观察站前一次发送l 级( 或2 级) 帧，当前产生的是级帧， 观察站发送，级帧的总量，o ，l ，2 铌：在改进协议中，当观察站前一次发送0 级帧，当前产生的是级帧，观察站 发送，级帧的总量，= 0 ，1 ，2 气：在原协议中，网络丌始运行后，观察站第“次产生的信息帧的最大滞留时间， u = l ，2 ，c ，w n ：在改进协议中，当观察站前一次发送1 级( 或2 级) 帧，当前产生的是级帧， 观察站第w 次产生的，级帧的最大滞留时i 白j ，w = l ，2 ，c j l k ：在改进协议中，当观察站自i 一次发送0 级帧，当前产生的是级帧，观察站 第1 ，次产生的，级帧的最大滞留时间，v = l ，2 ，c j 2 8 第一二章本文前期研究进展 l 垄每个工作整设军一个随机 l 数发生器随机产生信息帧 图2 1 原协议( 或改进协议0 级帧，前一次发送1 级或2 级帧) 流程图 t 原：在原协议中，信息帧的平均最大滞留时间 t j l ：在改进协议中，当观察站前一次发送1 级( 或2 级) 帧，当前产生的是，级帧， ，级帧的平均最大滞留时间，户0 ，l ，2 砀：在改进协议中，当观察站前一次发送o 级帧，当前产生的是，级帧，级帧 的平均最大滞留时间，户0 ，l ，2 乃：在改进协议中，级帧的平均最大滞留时间 原协议与改进协议0 级帧的发送过程及平均最大滞留时间分析 对于原协议，信息帧最大滞留时间为一轮轮询时间，平均最大滞留时间为多轮 轮询时i 日j 的平均值( 已设定进行朋次轮询) 。发送过程如图2 1 所示。由图2 1 很容 易看出，原协议的平均最大滞留时问丁原为： 乙 2 寺 关于改进坍议0 级帧的发送过程与原协议基本一致，只不过，由于改进协议将 “一次询问循环”设成“两轮小轮询”，0 级帧的最大滞留时间与观察站( 已没定为 l 号站) 前一次发送的信息帧类型有关。若自仃一次发送的为1 级或2 级帧，则当前 9 青岛人学帧l 学位论义 开始 为每个工作站设置个随机数发生器随机产生 0 、i 、2 级帧，再为t 机设置一个随机数发生器。 以便在第二轮小轮询中按不同概率确定1 类或2 类帧 主机站记数轮询圈数， 第一轮轮询开始m = l 甄诘丽丽函翦磊k 坠 y ，y l | 发送信息帧且传递轮 nf 询信q - 到 l ，- l 站后， l 轮询帧计时i r 埘+ r i 发送信息帧且传递轮 nl 询信号到 l ，_ l 站后， i 轮询帧计时“i r 埘+ r 发出传递轮询信号 到达j u f i 站，轮 询帧计时“= “托 件l 夏 讧n 1 发出传递轮询信号 到达v f 1 站，轮 询帧计时= f 。乜 ， 、f 一轮轮询结柬。f ，v 1 进入，肿i 轮轮询l 、 件l i 芦? 轮询l a n 上的j v - ，号站。i - = o 卜，当芦。v 时，v f 号站为 主机，一轮轮询开始时i = 0 且 轮询帧的计时器继续计时 n 有0 级 y l 发送信息帧且传递轮 nl 询信q - 到肛，_ i 站后， l 轮询帧计时“= + r + ，j 发出传递轮询信号 到述v - i - l 站轮 询帧计时，朋i k 址 f + i 又 净n t ! ：j 。一 一轮轮询结束输出o ，这 时的，j j l 称为f 2 ，f c 0 2 。轮询 帧计时器清零( r 胍= 0 ) 。o # i 帧 发送数量q 。+ i 第一轮开始 时c t r z = 0 进入下一轮轮询 图2 2 改进协议0 级帧流程图( 前一次发送0 级帧) 产生的0 级帧只要经过一轮小轮询( “第二轮小轮询”) 就能得到发送权，这种情况 下的平均最大滞留时间为乃l ，_ 0 ；若前一次发送的为o 级帧，则当前产生的o 级 帧需要经过两轮小轮询( 先经过“第二轮小轮询”，再经过“第一轮小轮询”) 才能得 到发送权，这种情况下的平均最大滞留时间为t j 2 ，产o ：因此，改进协议0 级帧有 两种最大滞留时间死l 和丁0 2 ，需要对二者再一次求平均值，才能得到平均最大滞留 时间t o 。这一点在稍后的模拟实验时，我们给予了充分关注。对于观察站前一次发 送1 级或2 级帧，当前帧是0 级帧的情况，发送过程与原协议基本一致，只需将图2 1 中的“当前站为空? ”和“为每个工作站设置一个随机数发生器，随机产生信息帧” 分别改为“当前站有o 级帧? ”和“为每个工作站设置一个随机数发生器，随机产 生0 、1 、2 级帧，再为主机设置一个随机数发生器，以便在第二轮小轮询中按不同 概率确定l 级或2 级帧”即可。对于观察站前一次发送0 级帧，当前帧也是0 级帧 第_ 二章奉义前期研究进展 回 0 、i 、2 级帧，再为主机设置一个随机数发生器， 以便在第二轮小轮询中按不同概率确定l 类或2 类帧 主机站记数轮询圈数， 第一轮轮询开始m = l n 轮询l a n 上的n - i 号站 i - - 0 。卜n 。当t = n 髓n - i 号站为e 机，一轮轸询开 始时i = 0 且轮询帧的计时器 继续计时。轮询帧每经过 观察站1 次，须累加计时 o 直至观察站信息帧成功 发送。第一轮开始时t i n = 0 l 繇有菇 发送信息帧且传递轮l 询信号剑 l ，一l 站后，ln 轮询帧计时o = o + r + ，l l 到达厶l 站，轮洵 帧卉碱t t t 。 y 一轮轮询结束 进入叶l 轮轮询 ，? 对o l i 进行求和，并除以c i i ( 2 级帧的i 流程图，对f h ：进行求和并除以卜必结束 晚i ) ，得出平均最大滞留时问且输出i 轮询l a n 上的n - ；号站女冒0 ，i n 当 扣，v 时，n - i 号站为e 机一轮轮询开始 时e = 0 且轮询帧计的时器继续计时 数量c i i + 1 第一轮开始时铆，= o ( 2 级帧的流! 程图，墒：为0 2 i ，f c 2 i 。发送数量晚i + 1 ，第1 一轮开始时d 2 l 卸) 。进入下一轮轮询 图2 3 改进协议1 级( 或2 级) 帧流程图( 前一次发送l 级或2 级帧) 的情况，其发送过程如图2 2 所示。参考图2 1 、2 2 可得改进协议0 级帧的平均最 大滞留时间t o 为： i f 删 l 一”v 1 t o l = 竺l c o l t o = + 瓦2 2 改进协议l 、2 级帧的发送过程及平均最大滞留时间分析 上述0 级帧经过一轮或两轮小轮询必定能够得到发送权，l 、2 级帧则不同。1 、 2 级帧由于受“一次大轮询”中“第二轮小轮询”选择概率p 的影响，最大滞留时 间具有不确定性，并且最大滞留时间也与观察站( 已设定为l 号站) 前一次发送的 信息帧类型有关。就l 级帧而言，若前一次发送的为l 级或2 级帧，则当前产生的 l 级帧需经过偶数轮( 至少两轮) 小轮询彳能得到发送权，这时的平均最大滞留时问为 弘i l | 2 瓦 为每个工作站 殳置一个随机散发生器，随机产生 0 、i 、2 级帧，再为主机嫂置一个随机数发生器 以便在第二轮小轮询中按不同概率确定1 类或2 类帧 主机站记数轮询圈数， 第一轮轮询肝始n f = l 轮询l a n 上的 l ，号站，l = o 1 n 当i = n 时，m f 号l、，l 对t “：进行求和并除以c i 续计时。轮询帧每经过观察站1 次须累加计时“直1 、二、：7 l 行求和并除以眈2 ) ，得出i l 二- 二 至观察站信息帧成功发送第一轮开始时k = ol 平均最大滞留时问且输出l 、j ， 。：轮询l a n 上的m f 号站。i = 0 ， i 主机启动随f唧：l n ，当扣。v 时，m ，号站为 l 机数发生器i 上 主机，一轮轮询开始时卢。且 l 级f 乇。：二涵 2 级 i 轮询帧的计堕器继续计时 、f 一 迤? 1 玻或2 翟哆p l ， “ 、 y 呜丽2 篙涂彳7 酉赢老泰， y 发送信息帧且传递轮询 n 发送信息帧且传递轮询 n 发送信息帧且传递轮询 n 信号到 l ，- l 站后轮信吁到肛，1 站后，轮 信号剑舻，_ i 站后，轮 询帧计时k = k + r + f f 询帧计时f 。；k + r + f j询帧计时。气k + r + ，l 发出传递轮询信号发出传递轮询信号 发出传递轮询信号 判达、l ，1 站，轮询到达_ n - i - i 站轮询到选u f - i 站，轮询 帧计时t m = t m + g 帧计时o = o 帧计时o = “ j ，、l j ， i 1 + 1_ 件i j 抖l n 当叁nn = 卜 n ：夕n 0 ： 一一 一一一一上y 一 一 y 、ly 一一轮轮询结柬输出，这时的称为，m ， d f 二轻轻葫话柬， 一轮轮蔷磊柬，进l 叫f c l 2 。轮询帧计时器清零( “= o ) 。i 级帧发送l 鼍进入矿i 轮轮询 入下一轮轮轮询l 蚺且删 。r r 山n n 臼z - ， 冶i 程图，“称为f m ，f 晚2 。发送数馈现z + l ，第! 一轮开始时助= o ) 进入叶l 轮轮询 图2 4 改进协议l 级( 或2 级) 帧流程图( 前一次发送0 级帧) 乃l ，1 ：若前一次发送的为o 级帧，则当前产生的1 级帧需经过奇数轮( 至少一轮) 小轮询才能得到发送权，这时的平均最大滞留时间为砀，产1 ；因此，改进协议l 级帧也有两种最大滞留时间五l 和n 2 ，需要对二者再一次求平均值，才能得到平均 最大滞留时间丁l ，这一点在稍后的模拟实验时，我们同样给予了关注。l 级帧的发 送过程分别如图2 3 、2 4 所示。参考图2 3 、2 4 可得改进协议l 级帧的平均最大滞 留时间t i 为： 。一 芝o 。 弋 _ 一”1 夏i = 竺l q i 戥。： 一 一一 石2 = l c 1 2 互= 半 2 级帧的发送过程与l 级帧基本一致，只是必须将图2 3 中的、号虚线框进 行位置上的交换。同样，要将图2 4 中、号虚线框以及两者之间的虚连线与 1 2 第- 二章奉义前期研究进展 号虚线框进行位置上的交换。参考图2 3 、2 4 很容易得出改进协议2 级帧的平均最 大滞留时间死为： 芝k ， 、1 _ 一1 互l = 竺l c 2 1 c 2 2 耻娶正：毕2 瓦2 = l 正= 丑丝 c ， 2 2 对重负载下竞争一冲突淘汰存取方式类系统模型建模的再研究 关于多星l a n 的运行机理和设计建造已有报告 1 2 , 1 3 。关于多星l a n 的“竞争 一冲突淘汰”存取方式的分类及对i 类、i i 类、i i i 类、类、v 类系统模型的数学 建模已经报告 1 4 - 1 8 3 。有关文献引中指出：如果将顾客请求服务权、请求失败后的 再一次请求服务权、得到服务权后接受服务的各种情况进行组合，其系统模型可分 为六类，已有详尽阐述。在本毕业论文的前期研究中，我们也对“竞争一冲突淘汰 存取方式的类模型给予了关注，不妨将结论简述如下。 类系统模型如图2 5 所示，该模型要求：顾客第1 次请求、再次请求服务都是 随机发生，获得服务权的一位顾客如果服务失败，不再保留服务权，重新请求服务。 建立排队模型时，将多星l a n 中心结点的交换通道当作服务员，且设定交换通道数 为l ；将用户终端产生的信息单元当作顾客，且设定信息单元长度为定长；将缓冲器 当作排队室。 在 、- 顾矿_