（模式识别与智能系统专业论文）基于面向对象方法的组态atm交换机仿真平台.pdf

摘要 异步传输模式( a t m ) 网络是一个网络传输的解决方案，在a t m 网络中，a t m 交换机是中间的核心部分，为了设计一个更有效率的a t m 网络，更有效的利用网 络资源，提高交换机的性能为关键。为了研究a t m 交换机中的各种资源控制和使 用的算法，比较各种算法的优劣，设计出一个a t m 交换机的仿真平台，可以加入 各种不同的网络流量控制算法，研究各种控制算法的效果。 本文利用面向对象的方法，设计出一个a t m 交换机仿真平台，实现了呼叫接 入控制、带宽分配、缓冲区管理的组态算法，并用实际数据进行了仿真实验，实 时的显示各种算法的效果。大大方便了研究a t m 流量控制算法，和评估算法的效 果和可行性。 随着互联网的高速发展，无线网络也成为一个重要的研究领域。而无线a t m 网络成为一个重要的研究方向，在无线a t m 中的带宽分配和呼叫接入控制等就成 为重要的方面。本文阐述了当前无线a t m 网络的发展现状，并借鉴有线的a t m 的带宽分配方法，设计出一个无线a t m 的带宽分配算法，并进行了仿真实验。 关键词：a t m ，呼叫接入，带宽分配，组态，仿真 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 ei s as t y l ew h i c hi su s et on e tt r a n s p o r t i naa t m n e t w o r k ，a t ms w i t c hi st h em o s ti m p o r t a n tp a r t i ti sv e r yi m p o r t a n tt oi m p r o v et h e c a p a b i l i t yo f t h ea t ms w i t c hf o rd e s i g nam o r ee f f i c i e n tn e t w o r k f o rr e s e a r c h i n gt h e m e t h o da n d c o m p a r i n g t h o s ea r i t h m e t i c so ft h ea t mn e t w o r k i ti sn e c e s s a r yt od e s i g n as i m u l a t o ro fa t ms w i t c hw h i c hc a nu s em a n yf l o wc o n t r o la r i t h m e t i c se a s i l ya n d e v a l u a t et h ee f f e c tt h o s ea r i t h r n e t i c s i nt h i sp a p e rw ed e s i g nas i m u l a t o ro fa t ms w i t c hb yu s i n go o pm e t h o d t h i s s i m u l a t o ra c h i e v ea r i t h m e t i c c o n f i g u r a t i o n o f c a c ( c a l l a d m i s s i o n c o n t r 0 1 ) ，b a n d w i d t ha l l o c a t i o na n db u f f e rm a n g i n g w eu s et h er e a l d a t at or u nt h e s i m u l a t o ra n dd i s p l a yt h ea f f e c to ft h o s ea r i t h m e t i c s i ti sm o r ec o n v e n i e n tt od e v e l o p t h en e wa r i t h m e t i ca n de v a l u a t et h ee f f e c to ft h o s ea r i t h m e t i c s w i r e l e s sn e t w o r ki s b e c o m i n gap o p u l a rf i e l dg o i n gw i t ht h ed e v e l o p m e n to f i n t e m e t w i r e l e s sa t mn e t w o r kb e c o m ea i n t e r e s t i n ga s p e c t o ft h e m a n y r e s e a r c h e s t h ec o n t r o lm e t h o do fw a t mi sa ni m p o r t a n tr e s e a r c hs u b j e c t ，w en a r r a t e t h e a c t u a l i t y o fw i r e l e s sa t ma n d i m p o s e t h ea r i t h m e t i co fa t mb a n d w i d t h a l l o c a t i o n ，d e s i g na na r i t h m e t i co f b a n d w i d t ha l l o c a t i o ni nw a t m ，t h e ns i m u l a t ei t k e y w o r d ：a t m ，c a l la d m i s s i o n c o n t r o l ( c a c ) ，b a n d w i d t h a l l o c a t i o r l ，c o n f i g u r a t i o n ，s i m u l a t e 致谢 奄s l s 2 3 7 在此论文成稿之际，谨向所有关心我的人士表示感谢! 特别要感谢我在研究生阶段的导师奚宏生教授，感谢他几年来对我的关心 和指导以及在学习生活方面给予我的关心和支持。奚老师以渊博的理论只是，严 谨务实的治学方法，展现了一个师长的可敬风范，为我以后的工作和学习树立了 榜样。在奚老师的悉心指导课题过程中，不仅学习了宝贵的理论知识，更重要的 学习了很多做人和做事的道理，使我受益终身。 衷心感谢我的父母! 作为他们的儿子，我是他们的希望所在，他们通情达 理。督学严明，他们对我的支持和鼓励，是我在人生中不断进取的动力。 感谢实验室的同学，刘建明，吴静诚，杨坚，赵宇，盛延敏在本论文和实 验中中给予有益的帮助、探讨和支持。 感谢我的同学和朋友黄云，尹大成，付厚超，感谢他们在我的大学生活中 给予我的关心和帮助，这份友情是我终身的财富。 此外，我还要感谢几年来一起生活过的朋友，是他们陪伴我走过美好的青 春时光。同时，还要向培养我的母校和老师们致以深深的谢意，并以此作别与我 朝夕相处了八年的科大。 感谢所有关心，爱护过我的人们。 里型堂垫查盔兰堡圭望塞一 第一章前言 由于异步传输模式( a t m ) 网络能灵活的支持不同统计特性，不同服务品质 要求( o o s ) 的多种类型的服务，国际电信联盟( i t u ) 已经建议把异步传输模 式( a t m ) 作为宽带综合业务数字网络( b - - i s d n ) 的传输方式。对a t m 的研 究已经成为网络研究领域热门的话题。a t m 网络中的通信业务量控制( t r a f f i c c o n t r 0 1 ) 因为能够有效的提高网络资源的利用率而吸引了众多的研究者 1 1 1 2 1 1 3 1 。 通信网络中的通信业务量控制的主要作用是保护网络和用户以实现预先规定的 网络性能，如信元丢失率或信元传输延迟等。概括的说，通信业务量控制是指网络 为了避免拥塞所采取的一系列操作。而拥塞是由不可预测的业务流量随机波动或 a t m 网络内的一些错误状态导致的。出现拥塞会使网络的服务质量严重下降。 通信业务量的另一个作用是优化网络资源的使用以取得较高的网络效率。因此需 要一个良好的通信业务量机制来控制网络资源的使用，以使网络高效，稳定的进 行传输。由于通信流量到达的随机性以及各通信源对交换资源的竞争，使得a t m 网络中的通信业务量控制变得异常困难。呼叫接入控制( c a l l a d m i s s i o n c o n t r 0 1 ) 与带宽分配在通信业务量控制中起着关键性的作用。而进行这些操作和缓冲器管 理有着密不可分的关系。 a t m 交换机是a t m 交换网的核心设备。因此，组建a t m 交换网的首要条件是 设计出结构扩展性好，能以极高的速率进行信元交换，支持各种不同服务品质要 求连接的交换机。一个成功的交换机设计除了要有合适的硬件结构，还要有高效 的资源控制算法，当前国外a t m 技术研究的一个热点 4 5 6 是对交换机资源 ( 链路带宽，缓冲区) 的优化使用，其目的是通过各种控制算法( 如：带宽分配策 略，缓冲管理机制和呼叫允许接入控制) 来调节交换机的工作状况，以提高其吞 吐量并且在满足用户服务品质( q o s ) 要求的条件下提高网络资源的利用率。在 a t m 交换网中，通信源的统计特性复杂多变，很难找到理想的数学模型来表征， 而且实际交换机的机构复杂，故很难从数学上准确分析各种控制算法的控制效 果。典型的数学分析方法是将通信源用简单的o n o f f 模型或i l m p p ( 马尔可夫调 制的泊松过程) 来表征，而交换机则用一个带缓冲的单服务台队列来模拟。显然， 在这种简化模型下研究交换机中控制算法的性能是无法得到全面而准确的结果 的。所以为了全面评估新的控制算法的效能，我们运用面向对象的分析方法，在 研究实际交换机结构 7 和借鉴实际交换机仿真设计 8 的基础上，开发了时间驱 动的信元级a t m 交换机仿真平台。在研究过程中，我们对交换机以资源( 带宽， 缓冲) 为中心进行结构分析和仿真框架的构建，以实现了在仿真平台中可嵌入各 种新的控制算法为目的，通过使用组态仿真的算法来模拟交换在这些控制算法作 主星型兰垫查丕兰堡主堡塞 一 用下资源的动态利用情况。为了实现这一目的，我们采用面向对象的设计方法来 设计仿真平台的结构，将各个模块定义为一个个的相对独立的对象，在每一个模 块中可使用不同的控制策略，来进行仿真，并用图形来实时直观显示各个性能指 标的变化情况。 本文中的仿真平台实现了c a c 算法、带宽分配算法、缓冲区管理以及信元丢 弃策略的组态算法，实现了模块化的中央共享型的a t m 交换机仿真。 由于计算机网络的飞速发展，网络正在迅速的向个人化和无线宽带化发展， 无线a t m 也受到更多的关注。在无线a t m 中同样存在着流量控制的问题，由于无 线网络本身存在的问题，如终端的移动、带宽资源有限等，使得在无线a t m 中控 制资源的算法显得更加重要，本文对一个典型的无线a t i v l 网络的v b r 信元的实时 传输中的带宽分配问题进行了研究，以传统的a t m 中的带宽分配算法为基础，给 除了一种带宽分配算法，并进行了仿真实验。 史里型兰塾查盔兰堡主笙塞一 第二章a t m 交换机仿真平台的主要结构及原理 2 1a t m 交换机的主要结构 a t m 暖 络的核心设备是a t m 交换机，它的作用主要是a t m 网络信元传输进行 交换。在a t m 交换机中进行信元交换和发送所需资源主要有输出链路带宽和暂 存信元的缓冲区。依据缓冲区位置及共享方式的不同，将交换机分为输入共享缓 冲型，输出共享缓冲型，中央共享缓冲型 1 1 。中央共享缓冲型交换结构由于自 身所具有的一些优点已经成为商用交换机制造商们普遍选择的设计方案。在nx n 的中央共享缓冲型交换机中n 个输入端口和n 个输出端口都可对中央缓冲进行 存取操作，在每个交换机时钟周期中，中央缓冲接受来自输入端口的n 个新的信 元同时向输出端口送出n 个信元。这样既不会出现输入缓冲型交换机缓冲区头阻 塞和输出缓冲型交换机输出端口竞争导致的交换机吞吐量和资源利用率下降的 情况，同时只需要较小的缓冲区就可以达到和其他缓冲型交换机同样的能力。 n 输入输出 输入控制 n 输出控制n 输出控制 图2 1 中央缓冲型交换机的典型结构示意 n 仿真中使用的中央缓冲型交换机的一种典型结构j z n l n 2 - 1 所示。 这种结构综合了输出缓冲和中央缓冲的优点。在信元中，占用存储资源的主 要是信元的负载( 4 8 字节) ，而完成交换所需的信息只在5 字节的信头中，于是就 将信头和信元的负载分开处理，即信元负载存放在共享的中央缓冲中，信头送入 选路机构中选路到相应的输出线上，并与信元净荷存放的地址一起放入输出队列 中进行排队，这样可以提高存储器的利用率，减少输出队列的长度要求。当然也 可以将信头也放入中央缓冲中，输出队列中只存放信元所在的地址。 2 2a t m 交换平台仿真结构 仿真方法主要有两种：基于时间驱动的和基于事件驱动的。仿真方法的选择 会对仿真平台的性能产生很大的影响并且取决于仿真事件的特性。如果事件发生 的密度比较小，一般选择事件驱动。如果事件同时发生的概率比较高，那么仿真 方法的选择取决于事件的特性。通信中信元数量非常大。因此，采用时间驱动技 术来仿真a t b t 交换机。 面向对象的仿真平台模块的的简要介绍 这个仿真平台是采用面向对象的方法设计而成，每一个模块都是一个相对独 立的对象。同时它又是一个开放性的开发平台，具有比较好的可扩展性，通过使 用加入不同的函数可以嵌入各种不同的控制算法，如在输入模块可以输入不同统 计类型和q o s 要求的不同信源，在输入控制中可以使用不同的c a c 算法等等。这样 逻辑队列1 图2 2 仿真平台结构图 w 大大增强了仿真的灵活性，有利于研究各种不同的控制算法。图2 2 给出仿真平 台的个结构示意图。 模型的各个模块的功能如下： 4 主里型兰蕉查查生堡主堡墨 一一 1 输入控制器：从空地址链表中读取一个空地址，将新到的信元存入对应 空地址的存储单元中，并根据信元的优先级将信元的地址传送给对应输出端口的 逻辑队列。 2 输出控制器：根据逻辑队列传送来的逻辑地址，将对应的信元发送到传 输链路上去，同时将该信元的逻辑地址编入到空地址链表中。3 空地址链表： 为了实现存储体的共享，必须设置空地址链表，当有新的信元到达时，输入控制 器就从链表读取空地址。当发送信元时，输出控制器将空地址编入链表中。 4 逻辑队列：每个逻辑队列对应一个输出端口，并且每个逻辑队列根据优 先级数目分成若干个子逻辑队列，各个逻辑队列的服务器根据各个子逻辑队列的 特性( 如队长，等待时间等) 决定先发送哪个信元，将逻辑地址传送给输出控制器。 根据信元的优先级，逻辑队列将控制器传送来的逻辑地址编入子逻辑队列中。 5 共享存储体：用来存储到达的信元。当输入控制器送来信元时，将信元存 入空地址单元。当输出控制器需要发送信元时，输出对应地址单元的信元。我们 采用4 * 4 端口的交换仿真，如果交换机的传输率为c 个信元秒，那么单位时间 片的大小为土，即发送一个信元所需要的时间。在每个单位信元时间片中，交换 c 机的输入端口最多接收一个信元。仿真平台在信元级上运行，即单位信元时间片 为一个仿真周期。在一个周期中，交换机完成一次交换过程，包括接收信元，发 送信元，信元的排队等等。以单位信元时间片作为一个仿真周期有利于提高统计 特性的准确性，而且接近交换机的真实运行过程，设计交换平台时，步骤相当清 晰。加大仿真步长，虽然有利于提高仿真平台的性能，但会降低统计特性的准确 性，而且增加仿真平台设计的复杂程度。从实际运行仿真平台来看，它的仿真时 间性能还是令人满意的。 这个仿真平台是一个开放性的开发平台，我们的是各个模块实现标准的接 口，以便在各个模块之中可以嵌入各种不同的算法，如在输入模块可以输入不同 服务类型及q o s 要求的不同信源、在输入控制中可以使用不同的c a c 算法、缓 冲区可以采用不同的管理方法等等。这样大大增强了仿真的灵活性，更加有利于 研究各种不同的控制算法。 2 3 仿真实现基本结构 一般，交换机有n 个输入端口和n 个输出端口，每个端口信元到达的时间 是同步的。发送一个信元所需要的时间称为单位信元时间片( c e l lt i m e ) 。在每 个单位信元时间片中，交换机的输入端口最多接收一个信元。如果交换机的传输 率为c 个信元秒，那么单位时间片的大小为圭。仿真平台在信元级上运行，即 l 单位信元时间片为一个仿真周期。在一个周期中，交换机完成一次交换过程，包 主旦型兰垫垄盔堂堡主堡塞 一 一一 括接收信元，发送信元，信元的排队等等。以单位信元时间片作为一4 f 疗n n n 有利于提高统计特性的准确性，而且接近交换机的真实运行过程，设计交换平台 时，步骤相当清晰。加大仿真步长，虽然有利于提高仿真平台的性能，但会降低 统计特性的准确性，而且增加仿真平台设计的复杂程度。从实际运行仿真平台来 看，它的仿真时间性能还是令人满意的。 仿真平台使用信元的数据结构 哑垂巫巫匦画亚画圃 图2 - 3 仿真信元的数据结构 在仿真中没有必要要求仿真信元与真实信元完全一样，因为这样会增加仿真 平台的计算量，而这种计算量是完全多余的，这样会降低方这平台的性能。同时， 很难获得真实的数据，给设计仿真平台带来很大的难度。用真实的数据，可以通 过转化格式后，转换具体方法后面给出，也能在仿真平台上使用。我们可以根据 要求来设计仿真信元数据结构，如图2 - 3 所示。 各参数的含义： 输出端口：是指信元应从交换机的哪个端口输出，在仿真中，该参数值指 定了它的逻辑地址应编入哪个逻辑队列。仿真中每一路低速信源的输入端口在仿 真一开始就初始化，而输出端口则随机产生。 优先级：优先级值表示信元的优先级，我们规定值越小，级别越高。它的值 是由信号源的类型决定的。 输入时间：信元进入交换杌的时间片序号。它和输出时间共同用于研究时延 性能。 输出时间：信元离开交换机的时间片序号。 仿真信元的产生： 这个部分的主要功能是把实际的信源变换成仿真平台可以使用的数据。仿真 平台所用采用仿真方法是以时间驱动的，即用每个时问片所产生的a t m 信元 数量表示带宽，由于实际仿真平台假设输入信号为1 5 5 m b p s 的信号流，所采用 的信源中有电影信号为1 2 4 秒为一帧，而每一个a t m 信元为4 8 个数据字节， 为方便我们的时间片为1 2 4 秒，可以得到一个1 5 5 m 信源在帧时间片内的信 元数量为1 5 5 m ( 2 4 8 4 8 ) 约为l ，6 8 0 个信元。 信源通常满足一定的统计特性，可以使用某种统计特性的数据来近似一个实 际信源，因此在仿真中我们采用符合泊松分布的数据来代替实际的信源。每一路 信源都用不同参数的符合泊松分布的数据来近似。 根据不同的q o s 要求，a t m 的服务类型分为c b r ( c o n s t a n tb i t r a t e ) ，r e a l t i m ev b r ( r e a l t i m e 丽a b l eb i t r a t e ) , n o n r e a l t i m e v b r ( n o i l 生璺型兰垫查莶堂堡主堡皇一 r e a l t i m ev i r i a b l eb i tr a t e ) ，a b r ( a v a i l a b l e b i tr a t e ) ，u b r ( u n s p e c i f i e db i tr a t e ) 。 在输入模块中也要对这些不同类型的信元分别进行处理。 f 1 1c b r 信源 处理比较简单，直接将c b r 所要求的带宽和1 5 5 m 的比值得到每一帧的信元 数量。 r 2 、r t - - v b r 和n r t - - v b r 信源 在仿真中对于v b r 信源采用实际电影星球大战【1 2 】信号经过处理后的数 据得来，它提供得是实时的每一帧的电影画面的带宽大小，把这每一帧的带宽大 小和1 5 5 m 的比值可得到所需的每一帧的信元数量。 ( 3 ) a b r 和u b r 信源 由于这两种信源对服务质量( q o s ：q u a n l i t yo fs e r v i c e ) 的要求比较低对于研 究a t m 交换机的带宽分配和呼叫接入控制算法的意义不大，在仿真中没有考虑 这两种信源。 产生了各种信元采用时分复用( t d m ) 的方法复合成仿真平台所用的1 5 5 m 信 源，输入到仿真平台中。 2 4 具体组态实现 在一个时间片内，完成如信元发送，信元接收，存入队列排队，存入缓冲等 待等功能，而这些相应的功能都有一个功能模块函数实现，调用不同的功能模块， 设定不同的功能参数，就可以实现a t m 交换机不同的组态策略。 图2 4 给出了仿真平台组态结构的搭建。控制策略组态由缓冲管理、带宽分 配、优先级管理和c a c 模块几个部分构成。这几个部分的详细算法将在第三章论 述；算法组态是通过填表完成的，分别通过缓冲管理和带宽分配对话框，只需要 选择某种算法，填入某些参数，而仿真平台主体的运行程序是不变的，只是将所 选择的算法连接而成仿真平台的算法库，形成交换机管理的具体运行模式。这样， 就可以完成一次具体的仿真过程。用表格形式的算法选择对话框，界面简单，清 晰，而且这里也没有必要构成图形算法库。 显示画面组态可以在实际仿真过程中动态的调节，我们提供的画面组态选择 有：1 ) 缓冲画面显示，可以按端口显示各个端口占有的缓冲情况，也可以按信 元级别显示各个级别信元占有缓冲情况。2 ) 各级信元丢失率和延时的趋势图显 示。3 ) 输出带宽利用率的趋势图。4 ) 各个级别信元显示的比较图以及仿真的进 度条等。各种算法和显示画面的选择，就可以形成交换平台多种的组态实现，尽 管不是严格意义上的组态软件，但是在我们的平台上可以运行不同的交换模式， 可以在各个级别信元之间来回切换，可以按端口或信元级别显示缓冲区情况，可 以说是组态思想的一种体现。后面，我们将用实际的信元和随机生成的的信元在 仿真平台上实现和比较多种缓冲管理的策略。 7 生旦型堂堡垄查兰堡主堡塞一 图2 4仿真平台组态结构图 图2 5显示画面组态结构构图 8 里型堂垫查盔堂堡主笙壅 一 第三章仿真平台各个模块使用算法 3 1 输入控制模块( 呼叫接入控制( ( c a c ) ) 模块) 输入控制模块的主要功能就是进行呼叫允许接入控制( c a l l a d m i s s i o n c o n t r 0 1 ，c a c ) 。a t m 是一种基于连接的快速信元交换网络，在进行连接请求时， 用户提交给网络两组不同的参数，通常称为使用参数控制( u s a g ep a r a m e t e r c o n t r 0 1 ) ，一组表明了q o s 要求，如信号丢失率和较大可接受延迟，另一组表明 了通信源的统计特性网络通过c a c 控制器利用用户所提供的描述自身统计特性 的参数，再结合目前网络中资源利用状况( 如带宽和缓冲区的使用情况等) 来决定 是否接纳个新的连接请求。目前仿真中采用的峰值法和基于测量的方法相结合 的算法进行仿真，即来一个新的信源，比较各个信源的峰值速率之和和交换机的 容量。如果速率和小，则接入这个新的信源：反之，则使用基于测量的c a c 算法 进行计算来确定是否可以接入这个信源。由于神经网络具有学习功能，有学者提 出采用神经网络预测带宽需求并实现c a c 决策，在此基础上有学者提出了结合模 糊控制器进行c a c 决策，取得了比较好的效果。然而由于信源的多类性，动态 性和强突发性，用完全相同的模糊规则进行在线c a c 决策，在一定程度上偏离 了通信源的瞬时动态性能，直接影响到网络资源的利用率。在此基础上，利用文 献 1 3 】中给出的框架，利用基于神经模糊算法的呼叫接入控nr 2 9 。神经模糊推 理系统是基于一种自适应网络的模糊推理系统，它可以自适应的建立、调节模糊 规则，与一般模糊控制相比较，对处理突发性、多变性很强的信源，比模糊控制 具有更好的效果，在仿真平台上应用这种基于神经一模糊的c a c 算法。它的具体 算法如下： ( i ) 设置初始值，包括q o s 要求、初始信元数目、预测步数等。设t = 0 。 ( ii ) 读取当前时段的各类信元的到达速率a i ( t ) 和丢失率l o i ( t ) 。 ( i i i ) 当t 5 时组成a i ( t ) = a i ( t ) ，a i ( t 一1 ) ，a i ( t 一5 ) ) ( i v ) 将a i ( t ) 送到相应的带宽预测器预测b w ，m a x ( t + 丁) ，并以 b w ，m a x ( t + t ) 的值作为t + t 时刻第i 类信元的分配带宽。 ( v ) 当t t + 5 时，训练带宽预测模块的神经网络。 输入：a i ( t t ) = a i ( t - t ) ，a i ( t - t 一1 ) ，a i ( t t 一5 ) ) 输出：b w , m a x ( t ) ( v i ) 训练丢失率预测模块的神经网络。 输入：a i ( t t ) = ( a i ( t - t ) ，a i ( t - t - 1 ) ，a i ( t - t 一5 ) 输出：l o i ( t ) ( v i i ) 当有第i 类信元的呼叫产生时，调用c a c 模块判断是否接入。 生里型兰垫查盔堂塑主鲨塞 一一 a 在流量控制模块，输入总带宽利用率，得到6 k 嘶， b 。在均衡模块，输入各类带宽利用率，得到g 向。 c 预测t 时刻后的带宽丢失率 d 在c a c 模块，当g _ 。枷，g 扣均大于0 5 ，而且丢失率预测值小于 所要求丢失率的时候，允许接入呼叫。否则拒绝。 ( v i i i ) 当最近1 0 0 个周期内的带宽利用率最大值小于l 的时候，我们将神 经一模糊网络向输出为1 的方向训练1 步。当系统丢失率大于q o s 要求的时候， 我们将网络输出向0 的方向训练1 0 0 步。 ( i x ) t = t + l 。返回( i i ) 3 2 缓存管理机制模块的实现 3 2 1 缓存管理概述 缓存管理是交换机的核心部分之一，交换机的性能之一信元丢失率主 要就是有这一部分引起的。由于a t m 网络要满足很多不同种服务的服务质量， 比如如视频信号和话音信号的丢失率要求分别为1 0 e 8 和1 o e 一5 。而丢失率的控 制是通过缓存管理来实现的，从某种程度上说，缓存管理就是如何进行信元丢弃 策略( d i s c a r dp r i o r i t yc o n t r 0 1 ) 的工作。 我们知道，缓存作为a t m 交换机的一种资源，是用来存储一些来不及立刻 转发的信元，这些信元存储在缓存内等待着被传输至它们各自要到的输出端口。 我门应该做到尽量利用而且避免完全利用那些有限的缓存，因为此时后来的信元 会因为缓冲资源的枯竭而不得不丢弃某些信元，如果网络流量足够的大，那么一 旦产生因为缓冲不足而造成的拥塞，其结果将是灾难性的。 现在的问题是，假设b * b 的交换机( 为了仿真的方便，假设交换机的输入 端口和输出端口大小相等，事实上，很多交换机产品确实是这样设计的) ，每个 端口有k 个缓冲，采用何种方法管理这整个的b k 缓冲空间，使得交换机的性能 如吞吐率( t h r o u g h p u t ) ，信元丢失率( c l r ：c e i il o s sr a t i o ) ，信元延时( c e l ld e l a y ) 等等尽可能的高。 很多文献1 1 4 1 5 1 6 1 讨论了这个问题，着眼点各有不同，基于不同的流量模 型，不同的数据业务类型，不同的交换机结构，得到了很多不同的结论。归纳起 来，可以分成两种考虑方向，一种是如何分配缓冲，这主要是考虑物理上交换机 的各个端口是如何占用缓冲的，各个物理端口在什么情况下开始丢弃信元。最简 单的方法就是每个端1 3 占用k 个，这种称作完全独占( c o m p l e t ep a r t i t i o n i n g ) l 拘方 法不利在于整个缓冲利用率的低下，因为某个端口可能已经满了开始丢弃信元， 而另外一个端口却还有空缓冲可用。 主旦型堂垫查盔堂堡主笙苎 一一 另外一个极端就是完全共享( c o m p i e 把s h a r i n g ) 的策略，在这种方法之下， 所有b k 的缓冲都被所有端口共享，如果缓存仍有可用的空间则接受新来的信元， 否则只有在缓冲完全被占用时才开始丢弃信元。这种有效利用缓冲的代价在于需 要更复杂的缓冲管理硬件。交换机必须支持b 个虚电路输出端口队列，通过存储 每个发往某个特定端口信元的缓冲地址，此外，交换机还必须将它们发往合适的 端口，尽管b 个物理队列已存在。这种所有输入与输出端1 ：1 共享一个共享缓冲的 方法被证明可以给a t m 交换机性能带来更多优点。其中之一就是提高了缓冲的 利用率，只需很小的缓冲大小就可以满足用户所要求的性能。然而，尽管这样的 利用率显而易见，还是避免不了信元丢失的发生。我们的兴趣在于如何降低这种 丢失。另外，共享同一个缓冲也带来了一些潜在的问题，一个独立的输入端口极 有可能影响到其它端口的效率。实际应用中这种缓冲管理的复杂性和a t m 网络 的高速度限制了完全共享结构的规模，但是对于端口不太多的交换机，仍不失为 一种好选择。 完全共享缓冲的最大缺点是不公平性。统计特性表明有这样一种可能，就 是某几个端口完全占用了整个缓冲，从而导致其它运行状况良好的端口不得不开 始变坏。这样我们需要强调对于各个端口的公平( f a i m e s s ) 有几种策略分别提供了不同的公平性，复杂度和运行效率。p s ( p a r t i a l s h a r i n g ) 将缓冲空问b k 分成d 组，每组端口共享这b k d 的缓冲空间。 s m x q ( s h 撕n g 、v i t hm a x i m u mq u e u el e n g t h ) ，每个输出端口所占缓冲不能超过某 个规定的限制。s m a ( s h a r i n gw i t hm i n i m u ma l l o c a t i o n ) ，一些最小量的缓冲被用 来仅服务于某个输出端口，而其余的则被完全共享。其它的，例如s m q m a 是 联合s m x q ，s m a 两种策略的结果。 当缓冲区满时，如果有新信元到达交换机，不得不丢弃某个信元( 在某些缓 冲分配策略下，也许未等到缓冲满就开始丢弃信元了，如上面所说的s m x q 策 略) 。丢弃的方式也将影响交换机的性能。这就是所要考虑的另一种方向，即选 择哪个端口哪个信元丢弃，是否容许新来的信元进入缓冲等。事实上由于a t m 交换机缓冲容量的有限，缓冲区满将是不可避免的一种情形。文献【1 7 】j 辱信元丢 弃级别可以定为信元层次( c e l ll e v e l ) ，端到端连接层次( c o n n e c t i o nl e v e l ) 及信元 级别层次( c l a s sl e v e l ) 。 在信元层次，每个信元头部的c l p ( c e l ll o s sp r i o r i t y ) 位用来区分出那些重要 的或对流量规划有重要影响的信元，不重要的或是破坏网络正常流量状况的信 元。一旦网络出现拥塞，c l p = 1 的那些信元被视为次要的信元将首先被丢弃用 来保证c l p = 0 的相对重要的信元。至于如何区分这两种信元，网络将会视用户 等级，流量状况给予不同的对待。 在信元级别层次，最早的方法是称作l i f o ( l a s ti nf i r s to u t 后来先丢) 的策 史旦型堂垫查盔堂堡圭丝壅一 略。当缓冲满时，不管新信元属于哪个服务级别，来自哪个端口，一律丢弃。显 然，这种方法对于满足不同的q o s 是非常不利的。所以后来推出机制( p u s h o u t1 就相运而生了，而l i f o 方法也由于它相对与p u s h o u t 机制的不同而被称为 n o n p u s h o u t 机制。 在推出机制中，只要中间交换缓冲区有空间可提供，低优先级信元和高优 先级信元就都被准许进入网络。如果一个低优先级信元在缓冲区满的时候到达， 那么它就会被丢弃。如果一个高优先级信元在缓冲区满的时候到达，那么仅在队 列没有低优先级信元在等待的情况下，它才会被丢弃。然而，如果缓冲区哪怕只 有一个低优先级信元，该高优先级信元也要替代低优先级信元进入队列。唯一的 例外是当低优先级信元正在被发送时不能被高优先级信元替代。这种机制的主要 缺点是它实现的复杂性。在优先级高信元替代低优先级信元的同时，仍然需要保 持信元的顺序，因此缓冲区不再是先进先出f i f o ) 。在管理缓冲区方面有相当大 的开销，也就是说，要保持跟踪低优先级信元存储的位置，也要同时跟踪高优先 级和低优先级信元的顺序以及信元的整体顺序。 考虑这样一种情况，设想某个端口在该时刻只有一个信元存储在缓冲中， 若刚好将该端口的那个信元丢弃，那么下个s l o t 时刻，该端口就可能处于“饥饿” 状态，即该端口将空闲，这对于提高带宽利用缓解缓冲紧张是不利的。l o c a l p u s h o u t 是这样一种方法，首先确定到底是哪个逻辑队列大量占用了缓冲，如果 当前到达信元要加入该逻辑队列，那么它将被丢弃；如果该信元是发往其它b - 1 的逻辑队列的，那么该队列将丢弃最后的一个信元以腾出空间接受该信元。这种 策略得到更大的效率和公平，不过增添了缓冲管理硬件的复杂度。 门槛机制 1 8 ( p a n i a ls h 撕n gi d e a ) 是另外种丢弃策略。在门槛机制中， 一个小缓冲区容量的门槛值被用来调节在高优先级信元和低优先级信元之间的 缓冲区的占用。只要在队列中等待的信元的总数小于或等于门槛值，两个类型的 信元都获准进入队列。一旦队列中的信元数超过门槛值，所有低优先级信元都被 丢弃，直到队列长度回落到低于门槛值为止。只要队列中的有空位，高优先级信 元就继续进入队列。这种方法中的主要问题是确定门槛值。如果它被设置成很低 的值，低优先级信元就可能在缓冲区中没有必要的被丢弃，因此限制了标记信元 的有效性。另一方面，如果把门槛值设置成一个很大的值，那么高优先级信元的 性能可能降低，因为可能没有足够的空间提供给它们。而且，虽然门槛值取决于 两种信元流的特征( 例如负载，突发行和相关性) ，但更重要的是高优先级信元的特 征，要首先保证它们的服务质量需求。因此，当缓冲区的交通特征改变时，可能 需要调节门槛值。然而，与推出机制不同，门槛机制可以实现为先进先出，复杂 性也不大。 仿真平台使用的是缓冲分配和信元丢弃策略两部分。下面就各种主要的分配 主旦型堂垫查盔堂堡主堡塞 一一 方案和丢弃策略作主要叙述并给出算法实现。 3 2 2 几种缓存分配方法 我们首先给出流量模型 1 9 ，假设一：信元到达各个输入端e l 的过程是各自 独立的典型伯努利( b e r n o u l l i ) 过程。也就是说，在任意给定的时间片，到达n 个端口中的任意一个的概率是p ，p 也是整个交换机的负载率。 假设二：每个信元发送到一个特定端口的概率是r n ，等价于发送到其余 n 一1 个端口的概率是( 卜r n ) ( n - 1 ) 。 假设三：连续信元是各自独立的。 参数r 是基本参数，用来衡量针对各个输出端口的不公平性( i m b a a n c e ) 。 如果r = l ，意味着是随机均匀流量，信元平均的发送到n 个输出端口。另一方 面，如果r l ，则意味着不公平流量，多个输入端口的信元集中发送到某一个输 出端口的可能性极大。 我们约定，一个信元发送到端口i ，则称其为端口i 信元。对于每个输出 端口，设弘( i n c o m i n g ) 为信元到达速率，7 ，( 1 0 s s ) 为信元丢弃速率，y ，( a d m i t t e d ) 为信元接受速率，y 。( d e p a r t u r e ) 为信元发送速率。 我们关心的是某个输出端口信元的概率r p l 的情况下，从而引发所谓的端 口不公平性的流量分析。我们做以下观察：对于每个输出端口在固定状态下，前 提一：信元丢失率相同：前提二：信元接受率等于信元发送率，即 y ( a d m i t t e d ) = y 。( d e p a r t u r e )对于i = 1 ，2 n 前提一是显然的，关于前提二，解释如下：考虑简单的2 x 2 的情况，假设二 不成立，则有y 。( a d m i t t e d ) y ( d e p a r t u r e ) ，既然是固定状态整个流量必须平 衡即有y i ( a d m i t t e d ) + y 2 ( a d m i t t e d ) = y ( d e p a r t u r e ) 1 2 ( d e p a r t u r e ) ，这样就 有yz ( a d m i t t e d ) 1 ，如果端口1 占用的缓冲可以无限那么端口1 空 闲的概率将会是0 ，在我们的分析中，缓冲是有限资源，而考虑到前提二有： r p - y 【( 1 0 s s ) = 1对于r p l( 3 1 ) 设p ，( 1 0 s s ) 是交换机在固定时刻的信元丢失率，考虑前提有： 主旦壁堂垫查盔堂塑主堡奎 一 p 。( 1 0 s s ) ：r l ( 1 0 s s ) ：r p - 1 r pr p 为了获得整个系统的带宽s ，注意到其它n - 1 端口所有接受率满足 兰 =(n-1而npyi(admission) 1 ( 1 _ 专) ( 1 一p r ( 1 0 s s ) ) 石( 1 。专) ( 1 - t = 2 。 1 1 同时通过前提二有： 芝y i ( d e p 州“r e ) 。 d m i s s i o n ) 所以对于c s ，带宽吞吐量为： s ：! 毯2 型! 塑! ! ! ! 生：!对于，n 并且，p 1 ( 3 - 2 ) ( 3 - 3 ) ( 3 - 3 ) ( 3 4 ) 注意到即使当流量不是很大时，对于r p 1 的完全共享式缓冲管理策略所得 到的效益也是很差的，这从吞吐量小就可以看出。这是因为在上述条件之下在一 个固定状态，缓冲区几乎被流量很大的端口所占用，导致其它端口的信元所占缓 冲很小，这必然导致其它端口在大多数时间内是空闲的，处于所谓“饥饿”状态。 我们很容易计算出某个端口i ( i 1 ) 的空闲概率从式( 3 一) 和( 3 一1 2 ) 得到： ( 蛔愀) 2 志( 1 一专) 其中i _ 2 ，n 定义h ( d e p a r t u r e ) = 、一p ( i d l e ) p i ( i d l e ) 是端 i i 空闲的概率 i = 2 ，n ，所以有： 1 p i e - 2 卜丽矗卜i r j 0-5n t ，f一1 1 例如，考虑两个不同的交换机设置，( n = 3 2 ，p = o 8 5 ，r = 1 2 ) 和 ( n = 3 2 ，p = o 7 ，r = 2 ) ，通过公式( 3 9 ) 可分别算得厅仃洲铂9 9 9 , 和 p i ( i d l e ) = o 9 8 ， 这里的丢弃策略有如下选择：1 ) 丢弃新来信元，称作n o n p u s h o u t 策略；2 ) 丢弃端口i 中最低优先级信元( 该优先级可考虑丢失率优先级或时延优先级或二 者综合) ，称作n o r m a l p u s h o u t ；3 ) 丢弃占用缓冲最大的端e l 中最低优先级信 元，称作l o c a l p u s h o u t 。c s + l o c a l p u s h o u t 机制就是d r o p o n - d e m a n d 缓冲管 理方案，一种很缓冲利用率很高的方案 ( 2 ) 完全独占式缓冲管理策略( c o m p l e t ep a r t i t i o n ) 1 4 生旦型堂垫垄丕堂堡主堡兰 一一 完全独占缓冲管理策略就是每个端口都有自己独立的缓冲空间，不平衡 流量对这种管理方式影响很大，流量很大的端口受到的影响尤其突出，与完全共 享缓冲策略相比起来，在不平衡( 或叫不对称网络) 情况下交换机的整体性能有 较大的下降。所谓不平衡( i m b a l a n c e d ) ，不对称( a s y m m e t r y ) 是指这样一种情 况，网络中大量的信元是同时发往同一个或者同几个端口，而其它端口得不到及 时的信元处于“空闲”状态。显然，这对于大量突发性的数据是有可能的，管理 这样的数据流量的花销是巨大的，还不能确定会得到怎样的性能结果。反之，如 果所有信元都是平等的发往各个端口，这样每个端口都能保证处于发送状态，那 么整个系统性能将得到极大的提升。 通过与上节同样的方法，可以得到平均丢失率和吞吐量如下： p r ( h s ) = 等 ( 3 - 6 ) 专) 对于r n 并且r p l ( 3 - 7 ) 如果n 1 ，公式( 3 7 ) 求极限为 s = p 完全独占缓冲策略( c o m p l e t ep a r t i t i o n i n g ) 也称为d e d i c a t e d a 1 l o c a t i o n ，其主要的思想是克服完全共享式的不公平性，即保证每个端口绝对 的公平性，这一点是通过给每个端口固定服务的缓冲大小来实现的。当一个端口 所分配的缓冲空时，那么新来的信元接受；而当缓冲满，不论这时候