（计算机应用技术专业论文）支持qos的atm交换缓冲管理算法研究与实现.pdf

硕十学位论文 摘要 a t m 技术是i t u t 定义的作为b i s d n 的交换技术，具有快速分组交换和统 计复用技术的特点，可以有效地支持多种业务( 如语音、图像、数据等) 。a t m 网络优于其它通信网络的一个显著特征是能够同时确保不同类型用户业务的服务 质量( q o s ) 。a t m 交换机内的缓冲器管理机制、信元丢失策略以及信元调度问 题均属于q o s 的重要内容，因此它们一直是a t m 网络q o s 领域内的研究热点。 为了用更简洁、有效的机制支持对q o s 的确保，本文开展了对a t m 交换中能够 支持多类型业务、公平并且容易实现的缓冲管理算法和信元丢弃策略的研究。本 文主要内容包括： 研究了a t m 交换中缓冲管理机制和信元丢弃策略。通过对离散排队模型的 分析，研究了输入缓冲、输出缓冲和共享缓冲的性能，从信元丢失率、吞吐量、 时延和缓冲器利用率等方面进行了理论分析。 研究了几种不同的共享缓冲管理算法。针对几种支持多优先级信元的共享缓 冲管理算法，在均匀业务流和非均匀业务流下分别用计算机进行了算法仿真，从 信元丢失率、时延、缓冲器利用率、公平性等方面进行了比较。 提出了一种改进的共享缓冲管理算法。在继承部分共享和压出方案优点的基 础上提出一种改进的共享缓冲管理算法，分别在均匀业务流和非均匀业务流下， 对陔算法的性能进行了仿真分析，和部分共享方案、压出方案进行了性能比较。 最后用v h d l 语言在m a x + p l u si i 环境下仿真实现了提出的改进的共享缓 冲管理算法。 关键词：服务质量；异步转移模式；a t m 交换机；缓冲管理 童量g 箜笪笪咝攀鎏篁堡堡墼堡垒墼耋塑坠： a b s t r a c t a s y n c h r o n o u st r a n s f e rm o d e ( a t m ) i s d e f i n e db y1 t u ta ss w i t c ht e c h n o l o g y o fb i s d n a t mc a ns u p p o r tav a r i e t yo ft r a f f i c ( a u d i o ，i m a g e ，d a t ae t c ) e f f e c t i v e l y b e c a u s eo ff a s tp a c k e ts w i t c h i n ga n ds t a t i s t i cm u l t i p l e x i n g a t mn e t w o r k sa r ep r o v e d t ob ea d v a n t a g e o u so v e ro t h e rf o r m so fc o m m u n i c a t i o nn e t w o r k si np r o v i d i n gq u a l i t y o fs e r v i c e ( o o s ) g u a r a n t e ef o rav a r i e t yo ft r a f f i c t y p e s b u f f e rm a n a g e m e n t ，c e l l d i s c a r d i n g a n dc e l l s c h e d u l i n gp l a yk e y r o l e si nt h e d y n a m i cq o sc o n t r o l ，t h e y c o n t i n u o u s l y r e c e i v em u c ha t t e n t i o na n d i n v e s t i g a t i o n b e i n g i nt h ei n t e r e s to f e f f i c i e n c ya n ds i m p l e n e s s ，b u f f e rm a n a g e m e n tm e c h a n i s ma n dc e l ld i s c a r d i n gp o l i c y w h i c ha r ej u s t i c e ，e a s yt oc a r r yo u ta n d s u p p o r ts e v e r a lt y p eo ft r a f f i ci na t m s w i t c h a r es t u d i e di nd e p t h t h i st h e s i sc o n s i s t so ft h ef o l l o w i n g ： 1 r e s e a r c h e so nb u f f e rm a n a g e m e n ta n dc e l ld i s c a r d i n gi na t m s w i t c h b y a n a l y z i n gd i s c r e t eq u e u i n gm o d e l ，t h et h e s i sh a sar e s e a r c ha b o u tt h ep e r f o r m a n c eo f i n p u tb u f f e rm a n a g e m e n t ，o u t p u tb u f f e rm a n a g e m e n ta n ds h a r eb u f f e rm a n a g e m e n t c e l ll o s s p r o b a b i l i t y , t h r o u g h o u t ，c e l ld e l a ya n db u f f e ru t i l i z a t i o n a r ep r e s e n t e db y t h e o r e t i ca n a l y s i s 2 s t u d i e ss h a r e db u f f e rm a n a g e m e n ts c h e m e s s i m u l a t i o n so fs e v e r a lb u f f e r m a n a g e m e n ts c h e m e s a r ed o n eu n d e ru n i f o r ma n dn o n u n i f o r mt r a f f i cu s i n g c o m p u t e r t h et h e s i s a n a l y z e s t h e s es h a r e db u f f e r m a n a g e m e n ts c h e m e s i nc e l l d i s c a r d i n g p r o b a b i l i t y , c e l ld e l a y , j u s t n e s se t c 3 p r o p o s e sa ni m p r o v e ds h a r e db u f f e rm a n a g e m e n ts c h e m e b a s e do np a r t i a l s h a r e da n d p u s h o u ts c h e m e s ，t h e t h e s i s p r o p o s e s a n i m p r o v e d s h a r e db u f f e r m a n a g e m e n t b ys i m u l a t i n g u n d e ru n i f o r ma n dn o n u n i f o r m t r a f f i c ，t h e t h e s i s a n a l y z e s t h es c h e m e sp e r f o r m a n c ea n dc o m p a r e sw i t h p a r t i a l s h a r e da n dp u s h o u t s c h e m e s 4 s i m u l a t e st h ei m p r o v e ds h a r e db u f f e rm a n a g e m e n ts c h e m ei nm a x + p l u s i i u s i n gv h d l l a n g u a g e k e yw o r d s ：q u a l i t yo fs e r v i c e ( q o s ) ；a s y n c h r o n o u st r a n s f e rm o d e ( a t m ) a t m s w i t c h ；b u f f e rm a n a g e m e n t i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 日期： 侔3 月访日 学位论文版权使甩授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“j ”) 作者签名： 导师签名： 克卅 易阪 日期：矿牛年；月砖日 日期：细垆年7 月日 i 硕十学位论文 1 1 研究背景与意义 第1 章绪论 a t m 技术足i t u t 定义的作为b 一1 s d n 的交换技术| l 】，具有快速分组交换和 统计复用技术的特点，可以有效地支持多种业务( 如语音、图像、数据等) 。a t m 网络优于其它通信网络的一个显著特征是能够同时确保不同类型用户业务的服务 质量( q u a l i t yo f s e r v i c e ，o o s ) 1 2 , 3 】。 经过十几年的研究，学术界与工业界对a t m 网络的q o s 保证体系进行了大 量卓有成效的研究与实践。目前，国际电联电信部( i t u t ) 和a t m 论坛( a t m f o r u m ) 两大机构已制订出了系列规范与建议，形成了a t m 网络o o s 体系的 基本构架。为了保证a t m 网络满足多种类型业务的q o s 要求，需要进一步研究 a t m 网络的o o s 控制与管理问题。a t m 交换机内的缓冲器管理机制、信元丢弃 策略以及信元调度等控制问题通常被认为是与实现相关的方面，所以没有相应的 规范与建议。出于这几个问题均属于q o s 的重要内容，因此它们一直是a t m 网 络o o s 领域内的研究热点。 a t m 交换机是a t m 网络的重要组成部分，其性能是评价网络q o s 的重要方 面，也是网络研究的热点之一。a t m 交换中的缓冲管理机制、信元丢弃策略和信 元调度机制等控制机制直接决定每个连接在各个交换节点处的信元丢失与时延性 能，是决定整个连接端到端丢失、时延及时延抖动性能的主要方面，也是保汪整 个a t m 网络q o s 的前提条件。降低a t m 交换控制机制的复杂性，研究简洁、有 效、公平、易实现的控制机制是确保网络o o s 要求的重要方面。所以研究a t m 交换中缓冲管理机制和信元丢弃策略等与o o s 相关的控制机制对于网络q o s 的 研究有一定的理论价值和学术意义，特别是研究简洁、有效、公平、易实现的控 制机制有一定的实用价值，能为基于a t m 的多媒体传输提供借鉴经验，有很好 的市场应用前景。 为了用更简洁、有效的机制确保q o s ，本文开展了对a t m 交换中支持多类 型业务、有效、公平并且容易实现的缓冲管理算法和信元丢弃策略的研究。 1 2 a t m 技术的概念 随着互联刚的发展，人们通信的需要，要求在刚络卜传输的、j t 务种类不断增 多。人们要求建立一个能够支持现有的和未来的各种业务、高效利用网络资源、 统一的信息传输与交换网络，于是综合业务数字网i s d n 和宽带综合业务数字网 b 一1 s d n 的概念应运而生。 电路交换速率固定，接入不灵活；分组交换处理复杂，交换时延大，都不能 很好的应用于b i s d n 中。1 9 8 6 年美国贝尔实验室( b e l ll a b ) 和法国邮电科学 院分别同时提出a t m 技术的初框，a t m 的目标一开始即定位于在高速光纤网上 传送各类多媒体业务( 数据、声音、图像和视频等) 。 a t m 交换结合电路交换和分组交换的优点，是一种面向连接的统计复用技 术，能够灵活高效地保证b i s d n 业务的o o s 要求。a t m 将各种不同业务划分为 固定长度的信元进行交换，减小了时延抖动，降低了时延值。a t m 信元长度为 5 3 字节，其中信息域为4 8 字节，信头为5 字节。a t m 技术充分利用光纤技术， 简化差错控制，在中间节点不检查业务完整性，大大简化了执议，以虚通道v p 和虚信道v c 为基础进行信元交换。 为了完成正常的信元交换和其他一些必要的功能，得到网络利用率的提高和 q o s 的保证，a t m 交换必须具备相应的控制机制，这些控制机制包括缓冲策略、 信元调度、竞争消除、反压控制、选路方式和组播实现等。交换机对其缓冲器的 管理以及信元丢弃策略的确定，将直接影响交换机的性能从而也直接影响各业务 流q o s 水平的高低。 a t m 流量控制和信令用精确的控制获得网络利用率的提高和服务质量的保 证。a t m 在连接建立之前，通过信令协商能否保证用户的服务质量要求，只有当 网络确认之后才接受入网，保证为每一个虚电路提供不同的服务质量，能实现真 正意义上的q o s 。 1 3a t m 网络服务质量研究 在多媒体业务的传输中，q o s 的确保十分重要，迄今认为，a t m 网络是传输 多媒体业务的最理想的网络，以a t m 技术为核心的b i s d n 可以承载各种各样的 业务。 1 3 1 o o s 是宽带通信网络的设计目标 用户业务向网络提出的传送要求称为“服务质量要求”，而网络向用户业务实 际提供的传送效果则称为网络的“服务质量”。q o s 是指网络对用户业务所呈现 的综合服务效果，该效果决定了用户对其获得服务的满意程度。q o s 是可度量的， 取决于网络性能，是用户实际接受的网络服务效果。对q o s 的描述要使用能为用 2 户和网络提供者共同理解和认可的语言。 不同类型用户业务通常具有不同的q o s 要求f 引。比如，数据业务通常不能容 忍比特错误及数据完整性被破坏，但可容忍一定的时延；多媒体业务则要求其中 多个业务成分的信息流之间保持特定的“同步”关系( 比如，话音信元相应的视 频信元的滞后须在卜9 0 m s ，1 2 0 m s 的范围内) 。因此，b i s d n 对这些业务的支持， 就是要求能够同时确保对所有业务的服务质量。 影响q o s 的因素来自业务本身和网络两个方面。每种、世务在比特率、突发性、 随机特性等方面都具有其固有的特性，这些特征通常用业务量参数的形式予以描 述【“。一般说来，业务的比特率越高，向网络递交的业务量负荷越大，突发性和 随机性越强，其q o s 要求就越难以保证。另一方面，网络本身的工作机制( 如信 息传递模式) 、对进入其内的业务量的控制方式以及对其资源的分配、管理方式等 都将直接影响其q o s 。比如，是否为用户业务建立连接、是否为用户连接预留网 络资源、是否对各业务产生的业务量进行控制与管理、采用何种方式对网络资源 进行动态分配等等。 在客观属性上，q o s 应是网络基本传送能力的个组成部分，如果网络对信 息的传递未能达到用户业务所要求的q o s ，就等于没有真正实现信息传送这一最 基本的网络功能。另一方面，q o s 也有其主观性，即它是人们对网络所提供服务 的一种主观的度量与评价，而这种度量与评价的准则会因不同的人或不同的时间 而异。q o s 的主观性特征决定了人们对某些业务的q o s 要求可能会不断升级。由 此可见，无论从客观属性还是从主观属性看，稳定、可靠的q o s 都应始终是宽带 通信网络的首要设计目标。 1 3 2a t m 网络服务质量体系 a t m 的呼叫控制q o s 参数包括连接建立时延、连接撤除时延和连接被接受 概率。对于a t m 的传送控制，a t mf o r u m 定义了六个a t m 层的q o s 参数【。6 l 最大信元时延( c t d 。；) 、峰一峰信元时延抖动( p p c d v ) 、信元丢失率( c l r ) 、 误信元率( c e r ) 、严重错误信元块率( s e c b r ) 和信元误差率( c m r ) 。 为确保a t m 网络端到端的q o s ，网络必须建立相应的q o s 体系，其中包括 q o s 规范描述、q o s 控制与q o s 管理1 5 。”。 目前，a t m 网络已形成了一个完整的q o s 体系。a t m 根据不同的业务类型 定义了不同的q o s 参数，为每个不同的信息传送建立端到端的虚连接并分配必需 的网络资源( 包括带宽、缓冲器等) ，在a t m 的标准中具体地定义了实旌呼叫连 接控制的信令过程及相应的连接接纳控制( c a c ) 功能，确立了保证其所要求q o s 的前提。a r m 建立了一系列业务量控制与管理机制，提供对各业务流数据传送阶 段q o s 的动态控制，比如：业务量警管、业务量整形、优先级控制、捐j 塞控制等。 a t m 层的操作与维护( o a m ) 功能，为a t m 的网络管理及q o s 管理奠定了基础。 a t m 技术并不是完美无缺的，它依然需要继续完善与发展，比如，降低其复 杂性，用更为简洁、有效的机制支持对q o s 的确保等，而这正是本文研究的出发 点。 1 3 3a t m 网络q o s 控制和管理研究现状 o o s 的控制与管理是a t m 网络q o s 体系构架的重要组成部分。o o s 的控制 机制负责q o s 确保过程的具体实施，分为静态和动态控制。静态o o s 控制机制 用于在虚连接建立阶段为用户分配相应的网络资源，动态q o s 控制机制负责在用 户信息传送阶段完成确保相关q o s 要求为目标的业务量级网络资源动态控制，比 如，业务量警管( u p c n p c ) 、业务量平滑、拥塞控制、优先级控制、缓冲器管 理、信元调度等。 静念控制是通过信令来实现的，目前i t u t 与a t mf o r u m 均已分别在 q 2 9 3 1 、o 2 9 7 1 、u n l 3 1 、u n l 4 0 和u n l 4 1 建议中给出了较为详细的技术规范 h j 。对于动态控制，在1 3 7 1 、u n l 4 0 、u n l 4 1 和t r a f f i cm a n a g e m e n t 4 0 建议中给 出了网络资源管理、业务流量控制、业务量警管、业务量整形及基于信元丢弃优 先级( c l p ) 的信元选择性丢弃的功能描述p “，但并未给出诸如缓冲器管理、基 于虚连接的信元丢弃以及信元调度机制的功能描述，而恰恰是这几种机制直接决 定每个连接在各个交换结点处的信元丢失与时延性能，从而决定整个连接端到端 的丢失、时延及时延抖动性能的主要方面。为此，近十年来许多学者对这几个问 题分别进行了大量研究。 1 。4 缓冲器结构及其管理的研究现状 各业务流的随机性和相互独立性会导致同一瞬间( 或信元时隙) 有多个信元 同时到达同一结点交换机的某个端口，缓冲器的作用是临时存储这些同时到达但 不能得到立即服务的信元。因此，缓冲器的结构形式及管理策略是直接影响信元 丢失性能的根本因素。对缓冲器结构及其管理策略研究的一个焦点在于寻找缓存 空间的共享方式与确保各业务流的信元丢失率一服务质量( c e l ll o s sr a t i o q u a l i t v o f s e r v i c e ，c l r q o s ) 之间的关系以及二者的最佳结合方式。 目前有五种典型的缓冲器管理机制【7 _ 1 3 】：完全划分( c p ) 、完全共享( c s ) 、 部分共享( p s ) 、最小容量、最大队长。 “完全划分”方式为每一业务流均单独分配一个固定容量缓冲空间，虽具有 4 硕士学位论文 理想的公平性，但缓存空间的利用率很低，不能动态适应各业务流的随机波动性。 “完全共享”则恰恰相反，它具有最高的缓存空间利用率，但由j i 没有隔离 功能，会导致少数突发业务流对缓冲器空间的过多占用而直接影响多数i f 常用户 的c l r - o o s 。 “部分共享”是以上两种方式的一种折衷；但是，由于业务流特性的不确定 性，因而很难确定不同级别( 具有不同c l r q o s 要求) 业务流的信元队列门限， 而且该机制仍不能完全消除高优先级信元流的突发对低优先级信元流c l r 的直 接影响。 “最小容量”法由于在缓存空间中分别开辟各业务流的独占区与共享区两部 分，确保了每一业务流c l r 的最低水平( c l r 上界) ，但对共享区的使用完全取 决于各业务流的动态行为，导致了其公平性仍是有限的。 “最大队长”方式则与“最小容量”的做法相反，它为每个业务流规定一个 对缓冲器的最大占用量，其本质仅是为各业务流确定了其c u 的最高水平，但无 法保证c l r 的最低水平。 文献 1 3 指出，以上各种缓冲管理算法单独使用时，均不能达到满意的效果。 简单的将最小容量与最大队长方式相结合依然不是一种有效的解决方案。因为这 种静态确定最小容量和最大队长的本质无法适应各个业务流特性的随机波动，势 必导致要么公平性差，要么缓存空间利用率低。文献【8 9 】提出的几种缓冲管理算 法，可以兼顾公平性和提高总体吞吐量，但没考虑多个信元丢弃优先级。 为了考虑多优先级的影响，文献 1 4 一t s 提出了支持多优先级的部分共享和压 出方案。 部分共享方案很容易实现1 1 4 】，但只在某些特定条件下运行得很好，在不同的 业务流模型和负荷强度下，这种静态队列长度限制策略缺乏适应性，不可能找出 一种静态门限来适应各种业务流的变化。 文献 1 5 1 提出的压出方案( s p ) 在缓冲区满的情况下是很有效的，对于高优 先级信元可以达到非常低的信元丢失率，也是公平的。但s p 的实现很复杂，很 难选择出最长的输出队列，并且随着输出端口数目的增加而变得更复杂。而且因 为对到达非饱和输出端口的低优先级信元的过度挤压，会导致不公平和整体吞吐 量下降。 以上这几种静态缓冲管理机制，均不能充分利用缓冲器。文献【1 6 】提出了一 种根据整个剩余缓存空间容量大小动态调节各业务流信元队列门限的机制，但由 于仅根据剩余空间容量的大小动态分配而不是“按需分配”，故仍不能很好的适应 各业务流间随机出现的突发性，而且剩余缓存空间中总是存在不能分配的“浪费” 部分。文献 1 7 研究了一种根据业务类型及其动态特征动态调节队列门限的算法， 出于要同时动态地监视各业务流和缓存的状态，故引入了较多的工作参量来支持 动态门限的计算，开销较大，并且还要引入特殊处理，导致算法复杂，因而很难 用于高速场合。 以上这些缓冲管理算法中，性能好的算法往往难以实现，容易实现的算法性 能又不够好。总之，研究如何更简洁、有效地确保q o s 、支持多优先级信元、公 平、有效、并且容易实现的缓冲管理算法是很有必要的。 + 1 5 本文研究内容及工作成果 本文在前人工作的基础上，消化现有研究成果，结合校外协项目：“智能学习 系统”，以简洁、有效为目标，针对a t m 交换机共享缓冲管理算法和信元丢弃策 略两个方面进行了系统和深入的研究。全文结构如下： 第一章，绪论。介绍了本文的研究背景和意义，研究了目前国内外a t m 网 络q o s 体系、q o s 控制和管理的研究现状，重点研究了a t m 交换缓冲管理机制 和信元丢弃策略的现状。 第二章，a t m 交换缓冲管理机制和信元丢弃策略的研究。本章首先研究了 a t m 交换的基本原理和控制机制。通过离散排队模型，重点从理论上研究了a t m 交换的输入缓冲、输出缓冲和共享缓冲管理机制。最后研究了信元的丢弃策略， 针对几种典型的丢弃策略进行了性能分析。 第三章，共享缓冲管理算法研究及改进。首先研究了目前国内外共享缓冲管 理的研究现状。针对几种支持优先级信元的缓冲管理算法，分别在均匀业务流和 非均匀业务流下进行了仿真，进行了性能比较。最后提出了一种改进的共享缓冲 管理算法，对该算法进行了仿真分析，同时和部分共享方案、压出方案进行了比 较。 第四章，改进共享缓冲管理算法的v h d l 语言设计及实现。采用了第三章提 出的改进的共享缓冲管理算法，用v h d l 语言设计了8 8 的a t m 交换单元，在 m a x + p l u s i i 环境下仿真实现了该改进共享缓冲管理算法。 最后，结束语。总结全文研究内容，并对a t m 网络的o o s 研究做了迸一步 的展望。 本文的主要工作成果如下： 1 研究了a t m 交换缓冲管理机制。通过离散排队模型，从理论上研究了 a t m 交换的输入缓冲、输出缓冲和共享缓冲管理机制。分析了这几种缓冲管理机 制的性能，从信元丢失率、吞吐量、时延和缓冲器利用率等方面进行了比较。结 果表明共享缓冲器机制具有最优的性能，它的缓冲器利用率最高，在相同的缓冲 器大小的情况下，信元丢失率最低，而且还可以实现更复杂的缓冲区共享机制， 同时指出共享缓冲区设计的缺点是共享缓冲区存取的速率必须等于输入( 输出) 6 硕士学位论文 速率的总和，对存储器件要求较高，控制复杂。 2 研究了不同的共享缓冲管理算法，进行了几种共享缓冲管理算法的仿真 分析。针对几种支持多优先级信元的缓冲算法，分别在均匀业务流和非均匀业务 流r 进行了完全共享、完全划分、部分共享和压出方案的仿真，并从信元丢失率、 平均时延、缓冲器利用率、以及对高、低优先级信元的公平性等方面进行了性能 分析和比较。仿真结果表明，部分共享和压出方案具有较优的性能，缓冲器利用 率高，公平性好，有一定的自适应能力。但压出方案需要查找最长队列以及记录 各信元的优先级，实现较复杂，而部分共享对于突发业务流的自适应能力有限。 3 ，提出了一种改进的共享缓冲管理算法。在继承了部分共享方案和压出方 案优点的基础上提出了一种改进的共享缓冲管理算法，并在均匀业务流和非均匀 业务流下对该算法进行了仿真和性能分析，同时和部分共享方案、压出方案进行 了比较。仿真结果表明，该算法缓冲器利用率高，相同条件下可以达到比其它两 种算法更低的总信元丢失率，能够支持多类型业务，可以优先保证高优先级信元 的服务质量，同时又是公平的，并且容易实现。 4 仿真实现了改进的共享缓冲管理算法。在m a x + p l u s l i 环境下用v h d l 语言设计并仿真实现了改进的共享缓冲管理算法，并对8 8 的a t m 交换单元各 模块进行了仿真，仿真波形表明可以完成a t m 信元的交换。 7 支持o o s 的a t m 交换缓冲管理算法研究与实现 第2 章a t m 交换缓冲管理机制和信元丢弃策略研究 a t m 交换中为了完成正常的信元交换和其他一些必要的功能，得到网络利用 率的提高和q o s 的保证，必须具备相应的控制机制。这些控制机制包括缓冲策略、 信元调度、竞争消除、反压控制、选路方式和组播实现等。交换机对其缓冲器的 管理以及信元丢弃策略的确定，将直接影响交换机的性能从而也直接影响各业务 流q o s 水平的高低。 本章首先研究了a t m 交换的基本原理和控制机制。重点研究了a t m 交换机 的缓冲管理方式，从理论上采用离散排队模型分析了三种不同的缓冲方式的性能。 最后，研究了目前的几种信元丢弃策略，分析比较了其性能。 2 1a t m 交换的基本功能和控制机制 a t m 交换采用面向连接的异步时分交换方式，既能像电路交换那样保证高的 服务质量，又能像分组交换满足各种带宽的交换要求。a t m 交换结构是实现a t m 交换的关键技术之一，是a t m 交换系统中必不可少的重要组成部分。 a t m 交换主要有以下特点 1 8 _ 1 9 】： 1 统计复用 a t m 交换不像电路交换那样每个连接占用固定的链路带宽，而是根据服务要 求和优先级灵活分配带宽。传输速率高的连接占用较宽的带宽；优先级高的连接 得到优先服务，服务质量更高。a t m 交换利用统计复用的特点具有比电路交换更 高的带宽利用率。 2 固定长度的信元交换 与可变长度帧的帧中继比较，a t m 交换是固定长度的信元( c e l l ) 交换。信 元是大小为5 3 个字节的分组，分为5 个字节的信头和4 8 个字节的信息域。采用 很短的信元可以减少交换结点内部的缓冲器容量以及排队时延和时延抖动；信元 的长度固定，则有利于简化交换控制和缓冲器管理，保证服务质量。 3 信头简化 简化信头可以减少交换结点的处理开销。a t m 信元的信头功能有限，主要是 虚连接标识、优先级标志、信头差错校验等。虚连接标识仅仅是局部虚连接标识， 而不是全局标识。a t m 交换机根据信元的局部虚连接标识给信元换上新的标识， 并将信元传送到下一个交换结点，下一个交换结点再根据新的标识传送信元，最 终传送到目的地。 8 硕士学位论文 4 面向连接 a t m 交换采用面向连接的方式确保服务质量。用户信息传送前，建立连接； 信息传送后，拆除连接。为了便于应用和管理，a t m 的虚连接分为两个等级：虚 信道连接( v i r t u a lc h a n n e lc o n n e c t i o n v c ) 和虚通道连接( v i r t u a l p a t h c o n n e c t i o n v p ) 。传输通道可包含若干个v p ，每个v p 又可划分若干个v c 。 2 1 1 a t m 交换结构的基本功能 a t m 交换结构应能实现任一入线和出线之间的信元交换，任一入线上的任一 逻辑信道的信元能够被交换到任一出线上的任一逻辑信道中去。为此，a t m 交换 结构应具有信元标头变换、选路和排队三项基本功能【1 8 l 。 1 信元标头变换 信元标头变换主要是指虚通道标识符虚信道标识符( v p i v c i ) 的变换，即 入v p i v c i 变换为出v p i v c i ，v p i v c i 的变换体现了信元交换的重要概念，意 味着入线上某逻辑信道中的信息被交换到出线上的另一逻辑信道中去。为了实现 信元标头变换，应该建立翻译表。 2 选路 选路表示任一入线的信息可被交换到任一出线，具有空间交换的特征。信元 标头变换加上选路功能，才能实现a t m 交换结构的交换功能。在翻译表中由入 线v p i v c i 应能查到出线号以及新的v p i v c i 值，翻译表是建立连接时写入的。 3 排队 a t m 是统计复用的异步时分交换，在连接建立后的传送信息阶段，经常会发 生在同一个时刻有多个信元争抢公用资源的情况，例如争抢出线或交换结构中的 内部链路。因此，a t m 交换结构需要有缓冲排队的功能，以免在发生资源争抢时 丢失信元。缓冲策略是a t m 交换结构设计中的重要问题，在很大程度上影响交 换结构的性能和复杂性。 除去以上3 项基本功能外，a t m 交换结构通常还应具备组播( m u l t i c a s t ) 功 能和优先级( p r i o r i t y ) 控制功能，以适应宽带业务的多样性。前者是输入信元可 通过交换结构送到多个目的地，后者是可以按各类业务的优先级高低来控制服务 质量，例如当不同优先级的信元在争抢资源时，应该保证优先级高的信元得到服 务，优先级低的信元在缓冲器中等待。 a t m 交换结构应提供良好的性能，以保证所需的服务质量。与服务质量有关 的主要参数是信元丢失率、时延和时延抖动。各类业务的要求有所不同，有些业 务对信元的丢失率很敏感，另一些业务则对时延和时延抖动很敏感。 9 2 1 2a t m 交换结构的控制机制 为了完成正常的信元交换和其它一些必要的功能，以及能达到一定的服务性 能指标的要求，a t m 交换结构必须具备相应的控制机制，这些控制机制主要包括 缓冲策略、信元调度、竞争消除、反压控制、选路方式和组播实现等i i 。 1 缓冲策略 缓冲策略( b u f f e rs t r a t e g i e s ) 又称为排队策略( q u e u i n gs t r a t e g i e s ) ，足a t m 交换结构设计的重要内容，对a t m 交换结构的性能具有重要的影响。从广义来 说，缓冲策略包括缓冲器设置方式、缓冲器的数量、队列的存取控制、以及缓冲 器的管理等。 不同的缓冲方式具有不同的性能，共享缓冲和输出缓冲具有较好的性能，获 得了较多的应用。缓冲管理用来实现缓冲的分配策略和信元丢弃策略，与吞吐率、 时延和信元丢失率均有密切的关系，缓冲管理对缓冲方式的服务质量起重要作用。 对于同一种缓冲方式，采用不同的缓冲管理算法会获得不同的服务质量。缓 冲管理算法主要从缓冲器的利用率和公平性两方面进行考虑，同时还要兼顾实现 的复杂性。目前的缓冲管理算法有完全共享与完全划分、静态的队列长度限制策 略、公平共享和动态队列长度限制策略等。有关共享缓冲管理的研究，将在第三 节中详细介绍。 2 信元丢弃策略 由于每个网络结点内的缓冲器空问总是有限的，因而就可能造成流向某个 ( 些) 交换机的某些端口的信元数量超过它所能接受的程度，从而出现拥塞。因 此，必须有一种机制在拥塞期间确定允许哪些信元进入或继续留在缓冲器中，缓 解或避免拥寨的基本方法是对信元进行选择性丢弃。 从总体上看，信元丢弃策略也是缓冲器管理机制的一个组成部分。目前，国 内外学者己在信元丢弃策略方面做了大量研究，就共享缓冲器环境下的信元丢弃 策略而言1 1 1 , 1 6 , 2 0 - 2 5 】，它可分为先到先丢、后到先丢、推出式丢弃、门限法、门限+ 推出法等信元丢弃策略。有关各信元丢弃策略的研究，将在第四节中详细介绍。 3 信元调度 信元调度是一个复杂的问题，即基于时延或信元丢失优先级来安排信元的发 送，它与信元丢弃策略有关，也是保证q o s 的一个重要方面。简单的信元调度方 法有f i f o 规则、轮循规则、加权轮循规则等。其它较复杂的信元调度方法还有 如基于虚时钟的信元调度，基于e d d 的信元调度和基于自校准的压出策略等等。 4 反压控制 有些交换结构的缓冲器分设在各处，例如具有内部缓冲的多级网络的每一级 都有缓冲器，采用输入缓冲与输出缓冲的单级或多级网络的缓冲器分设在输入端 1 0 硕士学位论文 和输出端。对于这些缓冲方式的交换结构，信元丢失不仅可能由于竞争所致，还 可能由于后级缓冲器溢出而引起。当然，争抢缓冲器也可看成是一种竞争。如何 对待后级缓冲器的溢出，也是控制机制中必须考虑的问题。 所谓反压控制，就是后级应向前级发送表明后级缓冲器是否占满的反向信号， 使得前级在后级缓冲器占满时不向后级发送信元，信元仍保留在前级的缓冲器中。 反压控制也称为交换结构内部的流量控制。反压控制有几种不同的实现方式：证 实或许可、局部反压或整体反压。 当上级发来的信元所到达的交换单元的相应队列是空队列时，可以采取直通 策略，即不在该交换单元中排队而直接穿越到下级交换单元的缓冲器队列中。 5 选路方式 这里的所谓选路是指多级a t m 交换结构内部的选路，是在信元传送阶段的 选路。选路问题也是一个最优控制的问题，必须具有合适的选路控制机制，使得 每个用户信元到来时，可以引导信元通过交换结构正确地传送到所需的出端。选 路控制应该与流量控制一起进行考虑，孤立的研究会导致不合理的结论。 按照确定路由的时间不同，可以分为面向连接的选路和无连接的选路，按照 路由信息存放位置的不同，可以分为自选路由和表格控制。 6 组播实现 a t m 交换结构还应该能支持点到多点连接，即组播功能。组播是指某个入端 的输入信元可以传送到n ( 1 n o ，则1 ( z 0 ) = 1 ，否则为0 。 表达式( x ，一1 ) + 说明，如果爿，) o ，则一个信元将要从端口1 传送出去，留。f 队列的长度为( x ，一1 ) 。 如前假设，到达的4 个信元是独立同分布( i i d ) 的，并且已经到达一个稳定 的状态。令p ( x ) 表示x 。的稳定状态分布，则p ( a ) 表示4 的分布。式( 2 4 ) 两边 取期望值，可以得到： e ( x ) = e ( j ) + e ( a ) 一e ( x 0 ) ( 2 5 ) 于是可得到： p ( x ) o ) = e o ) 一p 将式( 2 4 ) 两边平方并取期望值，得到 e ( 爿2 ) + p + 2 卢匠( z ) 一2 e ( x ) 一2 2 2 = 0 ( 2 6 ) 假设爿。的方差为盯2 ，则e ( a 2 ) ；p 2 + 盯2 。因此，队列的平均长度是 掣) 5 钎 ( 2 7 ) 由于a 遵循泊松分布，所以仃2 = p ，代入式( 2 7 ) 中会得到下面的公式： 删；篙 s ， 假设在稳定状态下，缓冲区不阻塞的概率是巾，则一是服从均值p = 中 的泊松分布。从定义来看，阻塞缓冲区的期望值是n ( 1 一中1 。 令e ( ) = 掰a 卢，因为所有信元的目的端口均匀地分布到所有的n 个 输出端口，则阻塞缓冲区的期望值也是n e ( x ，一1 ) + = ( 芦一p ) a 所以可得到： 西：p ；1 卢+ p ( 2 9 ) 若 = 1 ，则1 3 = 1 ，由式( 2 8 ) 和( 2 9 ) 可得到p = 2 一2 = 0 5 8 。这里p 是 类型1 信元的吞吐量。由两式推导出输入负载 和吞吐量j d 的关系为： a 0 = 1 _ 焉呐如酏3 腑： 07 d 6 0 e _ 口4 翟 呻03 0 2 3 1 b 一一 7 输入负啦大小 图2 3 输入缓冲方式中输入负载与吞吐量的关系 分析表明，在假设到达信元是i i d 分布并且均匀的分布到各个目的端口的前 提下，即随机的均匀业务流模型，当入线数n 很大时，