（物理电子学专业论文）高性能交换技术的研究.pdf

主里型兰垫查查兰壁主兰垡堡壅 壹丝壁銮堡垫查盟里堑 摘要 信息技术是2 0 世纪最重要的科技进展之一。几十年来，互联网的迅速发展，其规模迅 速扩天，互联网用户的数目呈指数上升。互联网的迅速发展使得对互联网的研究变得越来越 热门并且取得了许多引人注目的成果，本文就其中的高性能交换技术作了详细的介绍。 互联网的发展导致互联网通讯量变得越来越复杂，同时使得对网路设备的研究越来越离 不开对通信量的分析夯文在第一章中详细介绍了要壁旦望笪量。妊这一章里我们先介绍了 互联网通信量的测量，然后就互联网通信量的特性和建模展开讨论，最后讨论了互联网通信 量管理中的一些问题。自相似性是互联网通信量最重要的特性，我们在这一章日擗细介绍了 自相似性的概念，给出了互联网通信量自相似性的证据以及些自相似通信量模型。 在本文的第二章，我们系统地介绍了高速交换系统，给出了排队结构加交换结构的高速 交换系统结构，并对输入排队、输出排队、虚拟输入排队和结合的输入输出排队进行了详细 的讨论。( 由于并行多模块交换是目前交换技术发展的趋势，因此在第二章的后半部分，我们 讨论了并行高速交换系统，重点讨论了并行交换系统的加速比问题，介绍了并行交换系统的 稳定性分析方法。七 ，、 本文第三章的主要内容是交叉开关交换。在这一章里，我们介绍了交叉开关及交叉开关 调度算法。俾s l i p 算法是第三章的重点，文中对e 乳堡算法给出了详细的性能分析和仿真 结果。在第兰章的最后，我们介绍了c o n e x a n t 公司的c x 2 7 3 0 0 芯片组，这是一种使用 交叉开关交换的交换芯片组。、 在本文的第四章，我们详细讨论了共享存储交换。首先我们介绍了共享存储交换中的两 个关键问题：存储器分配和高带宽存储器设计。艋存储器分配技术上，我们重点讨论了动态 门限方法；在高带宽存储器设计方面，我们介绍了流水线存储器设计和宽字长存储器设计。 在第四章中，我们还介绍了i b m 公司使用共享存储交换的交换芯片q 6 4 g 。我们设计的f e l s w i t c h 交换芯片是采用共享存储交换技术的，在第四章中也对此作了详细的介绍并给出了仿 真结果4 主里型兰垫查查兰堡主兰垡堡苎 壹丝堕窒垫垫查塑婴塞 a b s t r a c t i n f o r m a t i o nt e c h n o l o g y ( i t i so n eo ft h em o s ti m p o r t a n ta d v a n c e so fs c i e n c ea n d t e c h n o l o g yi nt h e2 0 “c e n t u r y i nr e c e n ty e a r s ，i n t e m e ti n c r e a s e sv e r yf a s t ，t h es c a l eo f i n t e m e t i n c r e a s e s r a p i d l y , a n d u s e r so fi n t e r a c ti n c r e a s ee x p o n e n t i a l l yt h er a p i d l y p r o g r e s s m a k e s r e s e a r c h e so ni n t e r n e tb e c o m i n gm o r ea n dm o r ep o p u l a ra n dt h e r ea r em a n y g o o d r e s u l t st h a th a v e b e e n g a i n e d v i at h e s er e s e a r c h e st h i sd i s s e r t a t i o ng i v e sad e t a i l e dd e s c r i p t i o no nh i 曲 p e r f o r m a n c es w i t c h i n gt e c h n o l o g i e s t h e p r o g r e s so f i n t e r n e tm a k e s i n t e m e tt r a f f i cb e c o m i n gm o r ea n dm o r e c o m p l e x ，a n dm a k e s r e s e a r c ho fi n t e m e td e v i c e sm o r ea n dm o r ed e p e n d e n tt oi n t e r a c tt r a f f i ca n a l y z i n g i nc h a p t e ro n e ， w ei n t r o d u c ei n t e m e tt r a f f i ci nd e t a i l f i r s t ，w ei n t r o d u c et h em e a s u r e m e n to fi n t e m e tt r a f f i c ，t h e n w ed i s c u s si n t e m e tt r a f f i cc h a r a c t e r i s t i ca n d m o d e l i n g a tt h ee n do f c h a p t e ro n e ，w ed i s c u s ss o m e i s s u e sa b o u ti n t e m e tt r a f f i cm a n a g e m e n ts e l f - s i m i l a r i t yi st h em o s ts i g n i f i c a n tc h a r a c t e r i s t i co f i n t e r a c tt r a f f i c ，w ei n t r o d u c et h ec o n c e p to f s e l f - s i m i l a r i t yi nt h i sc h a p t e r , g i v es o m ee v i d e n c e sf o r s e l f - s i m i l a r i t yo fi n t e m e tt r a f f i ca n ds o m es e l f - s i m i l a rt r a f f i cm o d e l s i nc h a p t e rt w o ，w es u m m a r i z et h eh i g hs p e e ds w i t c h e s ，p o i n to u tt h a th i g hs p e e ds w i t c h i n g a r c h i t e c t u r ei n c l u d e sq u e u i n ga r c h i t e c t u r ea n ds w i t c hf a b r i c ，a n dd i s c u s si n p u tq u e u i n g ，o u t p u t q u e u i n g ，v i r t u a lo u t p u tq u e u i n ga n dc o m b i n e di n p u ta n do u t p u tq u e u i n gi nd e t a i l f o rp a r a l l e l s w i t c h i n gi st h et r e n do f c u r r e n ts w i t c h i n gt e c h n o l o g y , w ed i s c u s sh i g hs p e e dp a r a l l e ls w i t c h i n gi n t h i sc h a p t e r , m a i n l ya b o u ti s s u e so ns p e e d u pa n d s t a b i l i t ya n a l y z i n gf o rp a r a l l e ls w i t c h e s i nc h a p t e rt h r e e ，w em a i n l yi n t r o d u c ec r o s s b a rs w i t c h i n g w eg i v ead e s c r i p t i o no nc r o s s b a r a n ds c h e d u l i n ga l g o r i t h m sf o re r o s s b a ne s l i pi sw h a tw ef o c u so n ，d e t a i l e dp e r f o r m a n c e a n a l y s e s a n ds i m u l a t i o nr e s u l t so fe s l i pa r eg i v e ni nt h i sc h a p t e r a tt h ee n do ft h i sc h a p t e r , w ei n t r o d u c e c x 2 7 3 0 0 ，w h i c hi sak i n do f c r o s s b a rs w i t c h i n gc h i ps e t sd e v e l o p e db yc o n e x a n t i nc h a p t e rf o u r ，w ed i s c u s ss h a r e dm e m o r ys w i t c h i n gi nd e t a i l a tf i r s t ，w ed e s c r i b et w o c r i t i c a li s s u e si ns h a r e dm e m o r ys w i t c h i n g ：m e m o r ya l l o c a t i o na n dh i g hb a n dm e m o r y d e s i g n d y n a m i ct h r e s h o l da l l o c a t i o n ，p i p e l i n em e m o r ya n dw i d ew o r dm e m o r ya r ed e s c r i b e d i nt h i s c h a p t e r , w ei n t r o d u c eq 6 4 g , w h i c hi sak i n do fs h a r e dm e m o r ys w i t c h i n gc h i pd e v e l o p e db yi b m f e ls w i t c hi sa l s oas h a r e dm e m o r ys w i t c h i n g c h i p ，w ei n t r o d u c et h i sc h i pa n dg i v es o m e s i m u l a t i o nr e s u l t s 致谢 首先我要感谢我的导师王砚方教授，本论文是在他的悉心指导下完成的，他 严谨的治学作风和不断开拓创新的态度令我深受启发和鼓励。王教授领导的快电 子学实验室是一个充满活力和友爱的集体，我在此度过了五年的美好时光，这里 活跃的学术气氛非常有利于我的学习生活，这段时光我将永铭于心。 我还要感谢北京畅讯科技有限公司的徐茂先生和宋美娜小姐、数学系的陈卿 教授和杨周旺老师、统计与金融系的吴耀华教授、胡太忠教授和吴成庆博士，他 们给予了我许多的帮助和指导。 本论文涉及的工作凝结了课题组所有成员的心血，在此向与我一同工作的王 永纲副教授、宋克柱博士、石江涛博士、杨小军博士、束礼宝博士、冯海涛博士 和何浩硕士表示感谢。与邢涛副教授、张万生博士、刘树彬博士、陈曦博士、陈 家琴博士、吴义宝博士、倪奇志博士、武杰博士、张俊杰硕士和乔崇硕士的许多 讨论对我的工作大有裨益，在此表示感谢，同时要感谢在日常工作和生活中给予 我诸多帮助的程伊敏女士。 我要特别感谢我的父母和家人，感谢他们的养育之恩和在学业上对我长期以 来的支持。在论文完成的过程中，陈瑶小姐的关心和鼓励也令我深深感动。 向所有给予我关心和帮助的人致以真诚的谢意 ! 里型兰垫查盔堂堕主堂竺堡茎 蔓堡堂奎垫垫查堕盟 引口 互联网是2 0 世纪9 0 年代快速发展起来的一项重要的信息产业技术。随着互联网规模的 迅速扩大，互联网的通讯量也日益增长。十几年来，互联网用户的数目成指数增长，用户对 网络带宽的要求不断上升，带宽的需求远远超出了互联网现有的连接和交换容量。网络带宽 的快速增长，使网络系统设计者必须紧跟看起来无体止的带宽的需求。为了满足这些要求， 网络设备商和服务商已经开发和配置了越来越快的交换器和路由器。目前，w d m ( 波分复用) 和d w d m ( 密集波分复用) 技术已达到在一根光纤上有8 0 到1 6 0 个波长每一个波长带宽 1 0 g b p s ，已能满足最近几年内互联网对传输介质带宽的要求。但是光交换和光存储技术现 在还远不到应用阶段，因此路由器已成为提高网络速度的瓶颈。 路由器是典型的交换系统，它是构成i p 网的核心产品。路由器通常用于节点众多的大 型网络环境，处于i s o o s i 模型的网络层。路由器的一个作用是连通不同的网络，另一个作 用是选择信息传送的线路。高速路由器通常用于骨干网之间的互联以及骨干网与互联网的连 接。特别是对于骨干网的互联和骨干网与互联网的互联互通，不但技术复杂，涉及通信协议、 路由协议和众多接口，信息传输速度要求高，而且对网络安全性的要求也比其他场合高得多 由于电子商务、网络存储和宽带( 影像、游戏等) 用户的大量增加，路由器面临新的挑战： l ， 核心路由器的线速要适应w d m 和d w d m 技术的发展，现正由o c t 9 2 ( 1 0 g b p s l 过渡到o c 7 6 8 ( 4 0 g b p s ) 。这是指全国范围内的骨干网，我国目前的结构是所谓“八 横八纵”。从端口速率上说，这是顶级技术的路由器，处于金字塔的最高层。 2 城域网面临大量的用户，他们通过网络中心站接入城域网骨干，设置在中心站的路 由器称为边沿路由器，处于用户f 如企业网、校园网和居民小区) 同骨干网的交接处。 为了减低网络服务提供商( i s f ) 的成本，边沿路由器需要将数以干计的端口集中在 一个标准机柜中。在电信网同数据交换网合一的趋势下，端口要能够适应 o c 3 f 1 5 5 m b p s ) 甚至t 3 ( 4 5 m b p s ) 的速率。 路由器的研究和制造商的应付办法是将同用户终端相连的部分从交换系统中分离出来， 形成独立的线卡和交换卡。线卡除了由物理层接口的功能外，还负担网络管理和主要的信息 包处理。交换系统则测重于包转发功能，也称为转发引擎。线卡同交换卡通过高速背板插在 机柜中，背板之间、机柜之间通过高速串行线相连，形成由数千个端口，总交换容量达几十 t b p s 的高性能路由器。 我国是世界上通信和网络发展最快的国家之一，近十年来在国内已形成可观的电信产 业。但在路由器方面，特别是高端路由器方面，只占有很小的市场份额，研发的力量较小， 投入不足，现在又面临开放的电信市场的激烈竞争。发展有自主产权的高端网络产品已是当 务之急。在这一方面，国外的大学同工业界的合作有许多成功的例子。 在技术发展的前景下，在中国科技大学快电子学实验室几年来同电信业公司和研究所合 作的基础上，论文作者选择了高端路由器交换系统的研究，主要的目标是： 1 研究种交换结构( s w i t c hf a b r i c ) ，单片容量达到3 2 g b p s ： 2 在现有的f p g a ( 现场可编程门阵列) 实现单片。并进行仿真验证，以后还要考虑过 渡到a s t c ( 特定用途集成电路) 的可能性； 3 ，单片的交换结构必须便于在端口速率和端口数两个维度上扩展。 垦型兰垫苎茎兰堡主兰垡丝壅 蔓壁! ! 奎墼垫查塑婴墨 本文是作者在这方面研究的总结，共分为四部分： 交换结构设计的主要依据之一是互联网的通信量( i n t e m e tt r a f f i c ) 模型，设计的验证也要 用这种模型仿真。对互联网通信量的理论研究一直在i n # b n - - p 0 , 0 5 l ，( 1 1 ) d 其中= 表示同分布。 自相似参数也称为赫斯特( f m m o 参数，它表征了过程自相似的程度。h 越大，过程 的自相似程度越高，其长程相关性越高；当h = 05 时，过程退化为短程相关过程，不再有自 相似性了。 6 中国科学技术大学博士学位论文 高性能交换技术的研究 由于稳定过程要求y ( f ) 兰】，( 讲) ，所以连续时间自相似过程不是稳定过程，可以证明， 连续时间自相似过程是稳定增长过程。对于连续时间自相似过程，以下结果： 始e 防( f ) = 掣 ：， 方差：砌，防( f ) 】_ 丁v r x ( a o ( 1 3 ) 自相关函数：尺( f ，f ) = r i ( a 矿t , a r ) ( 14 ) 有 对于一个平稳的序列x = ( f ) ，i 1 ) ，令 蹦胪证1 ，熬( f ) ，2 ( 15 ) 如果z 是自相似过程y 的增长过程，即x ( i ) = y ( i + 1 ) 一y ( f ) ，并且对于任何整数m x ：m ih x t ” ( 16 ) 则称平稳序列= x ( o ，i 1 ) 为绝对自相似掣j ( e x a c t l ys e l f - s i m i l a r ) 。与连续时间的自 相似过程比较，可以看出两种定义非常接近， m x “( ) 对应于y ( a _ ) 。 称平稳序列x = x ( f ) ，i 1 为渐进自相似( a s y m p t o t i c a l l ys e l f - s i m i l a r ) ，如果当 m o o 时( 16 ) 式成立。 对于绝对自相似过程，有以下结果： 碰= 踟r = 矧 ， 自相关函数：月( 女，x ”) = | r ( 女，) 对于渐进白相似过程，有以下结果： 方差：砌r i x ( m - 弘f a r 而 x 白相关函数：l i m r ( k ，x “) = r ( k ，) ( 1 8 ) ( 1 9 ) ( 1 1 0 ) 图1 1 a 是一个自相似随机过程例子。注意其中的时间函数在不同的时间尺度上并不是 精确重复的，但是在不同时间尺度上的波形彼此是类似的。将这个过程与图1 1 b 中显示的 一个典型平稳随机过程的实例进行对比，我们可以看到在较高的放大率下，图1 1 b 中的函 数具有不同的特征，它变得更起伏更不规则。反过来就是说如果我们在较长的时间尺度上看， 这个信号表现得起伏较小，波形更规则。 7 中国科学技术大学博士学位论文 高性能交换技术的研究 ( a ) 自相似过程 ( b ) 非自相似过程 图1l 白相似过程和非自相似过程的比较 1 3 2 自相似性的表现 自相似性的表现有： 1 长程相关。性( l o n g r a n g e d e p e n d e n c e , 兄们 如果一个过程z 的自相关系数不可求和，即 则称并为长程相关过程。反之z 为短程相关( 肋d r t r a n g e d e p e n d e n c e j 酣) 过程。 长程相关过程的自相关函数按双曲线规律衰减： ! i m c o v ( x o ，x 。) = c i k l - p , 0 l ，c 为常数 短程相关过程的自相关函数按指数规律衰减： i m c o v ( x 。，x 。) = c l a l - k ，0 a 0 5 ，所以方差的衰减速度小于m 。 3 1 f 噪声性质 这是l r d 过程在频域上所表现出来的性质，特别地，l r d 过程的功率谱密度函数 ( p s d ) 在低频时发散，这正好与s r d 过程的功率谱函数在低频时仍然波动不大相反。换 句话说，l r d 过程的功率谱函数在0 附近表现为如下的一个功率定律：当iwi _ 0 时， 跏) 击 其中0 o ，k o ，x k ， f 1 2 2 ) 其概率分布函数为 f c z ，= p c x x ，= 一( 妻 。 c t z ， 均值为 研彳 _ 三k ，口 1 ( 1 埘) 口一l k 是p a r e t o 分布的位置参数，口是p a r e t o 分布的形状参数。 当 口2 时，p a r e t o 分布没有方差( 二阶矩) ；当口1 时，p a r e t o 分布没有均值r 一 中国科学技术大学博士学位论文 高性能交换技术的研究 阶矩) 。 图1 2p a r e t o 分布和指数分布的概率密度函数在对数一线性坐标尺度上进行了比 较。注意在这一尺度上指数分布的概率密度函数是一条直线，反映了这一分布的指数衰减 特性。p a r e t o 分布的尾部则比指数分布的尾部衰减得慢得多，反映出了p a r e t o 分布的重 尾性质。 图1 2p a r e t o 与指数概率密度函数 1 3 5 互联网通信量自相似性的几个例子 1 以太网通信量 l e l a n d 等人通过大量的数据和仔细的统计分析，指出了以太网通信量存在着自相似 性“。他们研究了从1 9 8 9 到1 9 9 2 年间所做的详细的高分辨率( 2 0 微秒的时间精度) 以 太网通信量测量所得的结果。数据中包括四组通信量测量值，每组都代表了连续的2 0 到4 0 小时的以太网通信量并包括总共1 0 0 多万个分组。数据是从b e l l c o r e 公司的各个 以太局域网上收集的。 图13 中左边一栏表示的是1 9 8 9 年一组测量值中的单位时间分组数的变化曲线， 这组测量值包括了连续2 7 小时对以太网通信量的检测结果，第一条曲线表示整个2 7 小时的情况，用的时间单位是1 0 0 秒，曲线中包括1 0 0 0 个数据点。每个接下来的曲线 都是通过将时间分辨率提高l o 倍从前一个得来得，图中示出的是一个随机抽取的小段 时间( 由较暗的阴影表示) 。因而第二条曲线包括了大约2 7 小时的段时间，第三条o 2 7 小时，如此等等。反方向来看即当我们从第一列的曲线从底下往上面移动的时候，一 条曲线图中的一个数据点是通过将它下边一条曲线的1 0 个相应数据点进行平均得到 的。 - 1 2 ! 县型兰垫查盔堂竖主兰竺堡兰苎羔堕望坠墼堑型塑! ! 翌 图1 3 实际的与合成的以太网通信量比较1 观察这批数据我们可以注意到几个有趣之处。除了第一条曲线可能是个例外( 第一 条曲线特征中的不同之处可能是由于天中不同时段的区别所致) ，所有曲线在分布意 义上是彼此相似的。这就是说所有曲线都包含有一定量的突发度。因此以太网通信量趋 向于在大时间尺度( 小时，分钟) 和小时间尺度( 秒，毫秒) 看起来都是相同的。另外，注 意突发没有自然的长度。在每一个时间尺度上，突发都是由突发较大的小区间和突发较 小的小区间交替组成的。这种自相似特性与语音通信量中以及通常用于数据网络分析和 设计中观察到的特性截然不同。 要看到两者的不同，可以看图1 3 中间一列曲线。这组曲线是用于以太网相同的方 中国科学技术大学博士学位论文 高性能交换技术的研究 式产生的，但用的是合成的通信量数据。这组数据是使用一个在平均分组大小和到达速 率方面类似于实际数据集的一个泊松模型产生的。在高分辨率情况( 时间单位为0 1 秒) 下其通信量相当有突发性，这一点正如我们预料到的。随着数据在越来越长的时间尺度 上被聚集起来，通信量模式变得平坦起来。对于诸如泊松模型所定义的平稳遍历随机过 程而言，这个结果不出所料。每一级的聚集都代表了取一系列的不重叠的采样大小为 1 0 的采样平均的操作。因此，我们可以预料每一级聚集数据的方差都减小到原有的1 1 0 。 左边和中间两列曲线看起来对比很强烈。 w i l l i n g e r 等采用并进行了细致分析的方法是将以太网通信量描述为许多p a r e t o 分 布的o n o f f 信源叠加产生的【7 “。每个这样的信源都在o n 阶段和o f f ( a p 空闲) 阶段之 间交替，在o n 时段信源就发送一串分组。如果我们假设各个时段都是由独立同分布的 随机变量描述并且每个信源都服从同一种分布，那么就可能f 但很困难) 确定多个这种信 源的叠加后的行为。实际上，这种方法可以用来产生对应于传统通信量模型的通信量。 关键的因素是要使用一个有限方差的分布，譬如指数或几何分布来描述o n 和o f f 时 段的长度。我们可以看到这些模型并不反映真实的以太网通信量。 b e l l c o r e 的儿位研究人员所采取的方法是用具有无穷大方差的分布，特别是采用参 数口在1 和2 之间的p a r e t o 分布作为o n o f f 时段的模型。在这个范围，p a r e t o 分布 随机变量具有有限均值和无穷大的方差。w i l l i n g e r 等人证明，许多p a r e t o 分布随机变 量的叠加结果就是自相似参数= ( 3 1 2 ) 2 的自相似过程。注意对于l 口 2 ，就 有o 5 h l ，即处于自相似范围之内。对于以太网通信量，他们发现单独的信源 的a 取值通常是1 2 ，这对应于日= 0 9 的自相似过程。 w i l l i n g e r 等人证明，类似p a r e t o 这样的重尾分布反映了单个以太网信源的实际情 况1 7 “。直观来看，重尾分布的较高或无限大的方差表现出极大的变化性，因此也就表 现出在所有时间尺度上都具有可变化性。一个应用或一台工作站通常以突发的方式产生 通信量，突发之间是空闲时段。对于高方差分布而言，则有关时间间隔的范围就可能非 常宽，很短的突发由许多，还有一些很长的突发。分形的创始人m a n d e l b r o t 将这种特 性称为n o a h 效应，这个名字用的是圣经上的一个典故：“在n o a h 一生的第6 个 1 0 0 年中，天堂的窗户打开了，大雨倾盆而下落到地球上，一直持续了4 0 天4 0 夜。” 2 w w w 通信量 对包含有5 0 多万条w w w 网页请求的w w w 通信量的研究结果显示w w w 通信 量也具有自相似性【6 j 。将每个w w w 浏览器描述为o n o f f 信源，研究人员发现数据 刚好符合一个p a r e t o 分布，并且l 0 ，= 1 其中x 。是一族随机变量，口，和屏是实数，占。是零均值的独立同分布随机变量。典型的线 性随机模型有a r ( p ) ，m a ( q ) ，a r m a ( p ，g ) ，a r i m a ( p ，吐q ) 等。 1 4 5 自相似通信量模型( s e l f - s i m i l a rt r a f f i cm o d e l s ) 自相似模型是最接近实际互联网情况的模型，也是目前应用最广泛的互联网通信量模 型。 1 分形布朗运动( f r a c t i o n a l b r o w n i a nm o t i o n ) 对于一个自相似参数为h 的分形布朗运动过程田1 b 日( t ) ，有： e b 。( f ) = 0 b 。( 0 ) = 0 b n ( f + j ) 一b 。( f ) 为高斯分布| v ( o ，- 1 8 1 ”) b h 的增长过程是独立过程 占。( f ) 占。( s ) = 仃2 2 0 f 1 2 “+ b 1 2 h i f s 2 “) 可以用分形布朗运动来刻画时间段( o ，f ) 之间的到达数： n r = m t + 、a m z f ， 其中m 代表过程的均值，口是方差因子v a r t e t ，z ，为自相似参数为h 的分形 布朗运动。 分形布朗运动模型的建立可以使用随机中点置换法r 月如mm i d p o i n td i s p l a c e m e n t ) 或小波( w a v e l e t s ) 法。 2 分形高斯噪声( m c f f d h d ，g a u s s i a n n o i s e ) 分形布朗运动的增长过程为分形高斯噪声。对于分形高斯噪声2 ”( ( f ) ，有： g 。( f ) = p 。( f + 万) 一口。( f ) ) o g 。( f ) 为高斯分布( o ，盯例“1 ) e g 。o + f ) g 。( r ) 】= o - 2 h ( 2 h 1 ) h 2 “2 ，f 远远大于占 对于离散的分形高斯噪声序列，其自相关函数为： - 1 7 ! 璺型兰垫查查兰堕主堂焦笙壅 堕堡堕銮塑苎查堕! ! 墨 p 。( ) ：妻+ 1 2 h 一2j 七f 2 + j k - lj 2 ”k l 3 分形a r i m a 过程叮m c t i o n n ta u t o m g m s s i v ei n t e g r a t e d m o v i n g a v e r a g e p r o c e s s e s ) 分形a r i m a 模型是建立在经典a r i m a 模型基础上的。如果存在非整数 d 0 使得 以 二为一个a r m a 过程，则称 以) 二为一个分形a r l m a 过程。其 由 = ( 1 一b ) 。= 死b ” b ( x 。) = 以一 铲揣= 密半舻啦，以2 币i 丽丽2 - l t 。1 # 分形a r i m a 过程的自相似参数为h = d + 0 5 。 4 小波方法( w a v e l e t ) 小波变换可以使变换后过程的自相似性比变换前减弱。这就为自相似性通信量建模 提供了一种新的方式。我们可以在小波空间使用诸如高斯模型的简单随机模型产生通信 量，再通过反小波变换就可以得到所需要的时域中的通信量i 。 5 o n o f f 模型 将网络通信量分为o n 和o f f 阶段，o n 阶段网络传输数据，o f f 阶段网络空闲。 大量重尾分布的过程按照o n o f f 模型( 即一个过程或者在o n 阶段中，或者在o f f 阶段中) 叠加，形成的新的过程表现出自相似性p 。例如我们分别使用参数为q 和口， 的p a r e t o 分布作为o n 阶段和o f f 阶段的过程，叠加的结果为自相似参数为 h = ( 3 一m i n ( a i ，口2 ) ) 的分形高斯噪声过程。 6p o i s s o n - z e t a 过程 p o i s s o n z e t a 过程可以用来模拟a t m 交换机的输入通信量2 ”。在p o i s s o n - z e t a 过程 p z c t ，p 中，在每个时间点n 突发的数目由均值为口的泊松分布确定。每个突发在它 的突发期的每一个信元时间产生一个a t m 信元。突发期长度由重尾分布的z e t a 分布确 定，z e t a 分布的参数取值为1 p 2 。p o i s s o n z e t a 过程是渐进自相似的过程。 7 确定性的混沌映射模型( d e t e r m i n i s t i cc h a o t i cm a p s ) 如果o n o f f 模型中的激励过程是从混沌过程中派出来生具有s i c ( s e n s i t i v e d e p e n d e n c e o ni n i t i a lc o n d i d o n s ) 性质的，这种模型就是确定性的混沌映射模型。这种过 程的轨迹明显她依赖于起始点。对起始点的修改将对轨迹形成巨大的影响。通信量的产 、 中国科学技术大学博士学位论文 高性能交换技术的研究 生由随机过程工。确定 x 。+ i = z ( x n ) ，0 z 。d x 。+ l = ( x 。) ，d 石。 1 x + l 2 x n 0 1 ，( 1 x 一- 五) o - x x 。) i 3 6 m ”。尽管这些方案可以提高吞吐量，但他们对通讯到达模式很敏感，当通讯突发 时，性能不比通常的f i f o 排队好。 ” ! 璺坠兰垫查查兰堡主兰垡笙壅 塞壁壁垡垫查盟! ! 墨 图2 3 通过使用虚拟输出排队来消除队列头阻塞 c 对于这个问题有一个叫做“虚拟输出排队”( v i r t u a l o u t p u t q u e u i n g ) 的解决方法可以完 全消除队列头阻塞，并且信息包的传输利用了1 0 0 的有效交换带宽。后面我们将对虚拟输 出排队做一个详细的介绍。输入阻塞和输出阻塞是由于争用访问交换结构而引起：交换结构 对于每个输入端口和每个输出端口一次只能传送一个信元。如果同时有多个信元希望访问一 条线路，只有一个可以访问，其他的将排队等待。我们后面会看到，输入阻塞和输出阻塞不 会降低开关交换器的吞吐量。而是增加了单个信息包通过系统的延迟，更重要的是延迟可能 随机不确定。幸运的是，我们可以使用两种技术来减少这个问题：第一是在使用优先级机制， 第二是使用加速技术。优先级机制使得高服务质量要求信元的时延得到保证；而加速技术让 交换结构的交换速率是端口速率的两倍或更高，有效地降低了输入阻塞带来的时延。 在非常简单的开关交换器中，等在每个输入的所有信元存在单一f i f o 队列中。当一个 信元到达了f i f o 队列头时，它被中央调度器考虑。信元和送往同一个输出但是目前在其他 输入队列头的信元争用它们共同的输出端口。决定下面哪个信元通过是中央调度器的任务。 最后每个信元将被选择并且通过开关交换器被送往它的输出。尽管f i f o 排队广泛使用，它 有一个问题：信元可能被一个送往不同输出但是却在它前面的信元所滞留。这个现象被称为 队列头阻塞。中央调度器仅仅看到f i f o 队列头的信元，所以队列头信元阻塞了在它后面需 要送往不同输出的信息包。一个很好的类比是一个交通灯，即使是红灯向右转的交通也是允 许的。如果只有一个单车道，你想向右转，但是你前面的车想直走，你就被阻塞了：在单车 道上，你不能通过你前面的车到达你的空闲输出。即使对于良好的通讯量模式，队列头阻塞 对于定长p “或者不定长信息包将吞吐量限制到只有总带宽的6 0 。当通讯量是突发的，或 者是偏向一些输出端口，吞吐量可能更差。 虚拟输出排队是对这问题的简单的解决方法，它首先在【3 8 中被提出。在每个输入， 对每个输出保留一个单独的f i f o ，如图2 3 所示。做出转发判决之后，一个到达信元被置 于相应于它的输出端口的队列中。在每个时隙的开始，一个中央调度算法检查所有输入队列 的内容，在输入和输出间发现一个不冲突的匹配。理论上，一个调度算法可以使开关交换器 的吞吐量从f i f o 排队的6 0 增加到使用虚拟输出排队的1 0 0 【3 。这是因为队列头阻塞已 经完全被消除：没有信元被它前面通向一个不同输出的信元所阻塞。在我们的交通灯例子中。 这等效于有一个专用的向右转车道：在你前面的汽车不会再阻塞你，你可以随便通向你的空 闲输出。 2 8 。巍 、一 ! 里型兰垫查盔兰堡生兰垡堡兰 蔓丝壁銮垫垦查堕! ! 翌 2 2 4结合的输入和输出排队( c o m b i n e di n p u t a n d o u t p u tq u e u i n g ) 输出排队在保证通信量的服务质量方面比输入排队和虚拟输出排队要强。在输出排队交 换系统中，到达的信元被立刻转发到相应的输出端口，从而消除了输入阻塞，这样做有两个 好处：( 1 】只要存在目的地为某输出端口的信元，该端口就不会空闲：( 2 ) 可以对信元的离开 时间调度从而满足不同服务质量要求信元对时延的限制。然后很不幸，输出排队对硬件的速 度要求很高，在交换带宽很高( 几十g b p s 甚至几百g b p s ) f l 根难实现。在输出队列的性能优 越性和输入队列的易实现性之间做个折衷，就有了结合的输入和输出排队c i o q 。 v o q i n p u t l i n p u t n v o q ，v 竹口 1 o qk v 图2 4c 1 0 0 排队结杩示意图 如图2 4 ，c i o q 在输入端设计有虚拟输出队列，在输出端设计有输出队列。由于有输 入缓存，对于端口数为n 的交换系统，c i o q 不要求输出队列和内部交换互联的速度达到端 口速率的n 倍，从而火火降低了设计的难度。 在交换系统中，如果一个时隙中( 或称为信元时间，是输入端产生一个信元的时间) 系统 能将每个输入端口的s 个信元读入并传输s 个信元到每个输出，则称该系统的加速比为s 。 加速比为s 要求系统交换结构、输入队列的读取速度和输出队列的写入速度均为端口线速 率的s 倍。对于n x n 的交换系统，不同的排队结构要求的加速比如表2 1 。 表2 1 不同排队结构的加速比 排队结构加速比( s ) i n p u tq u e u i n g ，v o q s ；l o u t p u tq u e u i n g s = n c i o q l s n 使_ l jc i o q 排队结构，我们需要找到一个合适的加速比数值，使得交换系统在输入任意 通信量时其性能都类似或接近输出排队，同时系统设计的复杂度在可以接受的范围。 我们可以证明，当交叉开关调度算法使用紧急优先算法m u c f a ( m o s tu r g e n tc e l lf i r s t a l g o r i t h m ) ，c i o q 结构的交换系统加速比大于等于4 时，该交换系统将与加速比为n 为 交换系统端口数) 的输出排队的交换系统具有相同的行为，也就是说，任意输入流分别通过 两个交换系统将得到完全相同的输出流。 在证明之前，我们先简单介绍一下紧急优先算法。 紧急优先算法至关重要的特征是信元的紧迫l 生( u r g e n