（通信与信息系统专业论文）两级负载平衡交换机关键技术研究.pdf

电子科技大学硕士论文 摘要 随着i n t e r n e t 业务的持续高速增长，t 比特级路由器技术成为业界研发 的重点之一。为了满足t 比特级路由器大容量、易扩张、高度可靠的性能要 求，需要在其核心关键技术一一交换结构上有所突破。最近，提出了一种负 载平衡交换机，该交换机易于扩展同时也能满足时延、吞吐量保证。负载平 衡交换机包括两级交换结构，第一级交换结构起着平衡负载的作用，连接输 入和中间输入，将到来的分组均匀散布到各个中间输入中；第二级交换结构 具有交换的功能，它连接中间输入和输出，将分组发送到输出端口。负载平 衡交换机不需要使用集中式的调度器，因此在保证具有良好的交换性能的同 时十分便于扩展，为网络工程师所推崇。 在本文中，作者首先介绍了负载平衡交换机的基本结构，并详细分析了 它的交换性能。由于当前的路由器要求交换结构具有快速的重构时间，因此 这罩介绍了可以将负载平衡交换机的两级结构应用于没有重构的单级光交换 机中。同时还简述了目前负载平筏交换机实现的各项关键技术。 另外，针对网络内不同业务的服务质量要求，在负载平衡交换机中应采 用优先级排队的机制。当前对于负载平衡交换机的研究大都处于无优先级的 业务模型下，本文将优先级机制引入负载平衡交换机中，分析了采用抢占策 略时的各优先级的吞吐量和平均时延，仿真结果证明了理论分析的正确性。 同时，负载平衡交换机的一个关键问题在于同一流的分组由于在负载平衡交 换机内部路径不同，可能会发生乱序的情况。本文提出了一种在两级负载平 衡交换机中保证分组顺序到达的满帧填充算法，该算法具有良好的交换特性， 同时也是一种分布式算法，各个端口可以独立地进行操作。接着我们提出了 仿真试验方案，并具体描述了在o p n e t 平台上所搭建的仿真模型。最后总 结了作者对于负载平衡交换机的研究工作，并讨论了今后的研究方向。 关键词：负载平衡交换机交换结构调度仿真 电子科技大学硕士论文 a b s t r a c t w i t hc o n t i n u o u s l yr a p i dd e v e l o p m e n to fi n t e r n e ts e r v i c e s ，t h et e c h n o l o g yo f t e r a b i tr o u t e rh a sb e c o m et h e h i g h l i g h t o fr e s e a r c h e r so fi ti n d u s t r i e sa n d a c a d e m i e s a sac o r et e c h n o l o g yo ft e r a b i tr o u t e r ，an e 、, vs w i t c hf a b r i ci sn e e d e d t om e e tt h e r e q u i r e m e n t o f c a p a c i t y , s a l a b i l i t y a n d r e l i a b i l i t y r e c e n t l y t h e l o a d - b a l a n c e ds w i t c hi si n t r o d u c e d 。t h es w i t c hi ss c a l a b l ea n dc a ng u a r a n t e ea f u l l c a p a c i t ya n dd e l a y t h el o a d b a l a n c e ds w i t c hi n c l u d e st w o s t a g e t h ef i r s t l o a d b a l a n c i n gs t a g ec o n n e c t si n p u t sa n di n t e r m e d i a t ei n p u t s ，s p r e a d sa r r i v i n g p a c k e t se q u a l l ya m o n gi n t e r m e d i a t ei n p u t s t h es e c o n ds w i t c h i n gs t a g ec o n n e c t s i n t e r m e d i a t e i n p u t s a n d o u t p u t s ，t r a n s f e r sp a c k e t s t ot h e o u t p u t s t h e l o a d b a l a n c e ds w i t c hd o e sn o tu s ea n yc e n t r a l i z e ds c h e d u l e r t h e r e f o r e ，i tc a n s c a l ew h i l ep r o v i d i n gt h es w i t c h i n g p e r f o r m a n c en e e d e db yn e t w o r ko p e r a t e r s i nt h et h e s i s ，if i r s ti n t r o d u c et h eb a s i ca r c h i t e c t u r eo fl o a d b a l a n c e ds w i t c h a n d a n a l y z e t h es w i t c h i n gp e r f o r m a n c eo ft h es w i t c h w h i l ec u r r e n t r o u t e r s c o m m o n l yn e e ds w i t c hf a b r i c sw i t hf a s tr e c o n f i g u r a t i o nt i m e s ，1s h o wh o wt o i m p l e m e n tt h el o a d - b a l a n c i n ga n df o r w a r d i n gs t a g e so ft h el o a d - b a l a n c e ds w i t c h u s i n gas i n g l ep a s s i v eo p t i c a ls w i t c hf a b r i cw i t hu oc o n f i g u r a t i o n s a n did i s c u s s t h ek e yt e c h n o l o g i e sa b o u tt h ei m p l e m e n t a t i o no ft h el o a d b a l a n c e ds w i t c h i na d d i t i o n ，w i t ht h er e q u i r e m e n t so fo o si nd i f f e r e n to p e r a t i o n si nn e t w o r k ， m u l t i p l ep r i o r i t yq u e u e sm u s tb ea d o p t e di nt h el o a d b a l a n c e ds w i t c h c u r r e n t l y t h er e s e a r c ha b o u tt h el o a d - b a l a n c e ds w i t c hi sf o c u s e do nn o p r i o r i t yt r a f f i c t h e t h e s i s a n a l y s e st h r o u g h p u ta n dm e a nd e l a yo ft h el o a d b a l a n c e ds w i t c hw i t h m u l t i p l ep r i o r i t i e si np r e e m p t i v ep r i o r i t yq u e u e i n gs t r a t e g y t h ep e r f o r m a n c eo f c o n s i d e r e d a p p r o a c h e s i sd e r i v e d b y t h e o r e t i c a l a n a l y s i s a n d c o m p u t e r s i m u l a t i o n s m e a n w h i l e ，ap r o b l e mw i t ht h el o a d b a l a n c e ds w i t c hi st h a td i f f e r e n t p a c k e t so ft h es a m ef l o wc a nt a k ed i f f e r e n tp a t h s ，p o s s i b l yl e a d i n gt o p a c k e t s r e o r d e r i n g i nt h et h e s i s ，1p r o p o s ea na l g o r i t h mc a l l e df f s ( f u l lf r a m es t u f f ) ， w h i c hm a i n t a i n sp a c k e to r d e ri nt h e t w o - s t a g el o a d b a l a n c e ds w i t c ha n dh a s e x c e l l e n ts w i t c h i n gp e r f o r m a n c e ( i nt e r m so fm e a nd e l a ya n dt h r o u g h p u t ) t h i s a l g o r i t h mi sd i s t r i b u t e da n de a c hp o r tc a no p e r a t ei n d e p e n d e n t l y i nt h ef o l l o w i n g ， t h es c h e m eo ft h es i m u l a t i o n e x p e r i m e n ti sp r e s e n t e d ，a n dt h eo p n e t - b a s e d s i m u l a t i o nm o d e li s d e s c r i b e d f i n a l l y , ic o n c l u d em yr e s e a r c hw o r ko ni h e 1 l 电子科技大学硕士论文 l o a d b a l a n c e ds w i t c ha n dd i s c u s st h ef u t u r ew o r k k e y w o r d s ：l o a d b a l a n c e ds w i t c h ，s w i t c hf a b r i c ，s c h e d u l e ，s i m u l a t i o n i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：童尘j日期：i 。j 年岁月i 文日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：导师签名： 日期：枷s 电子科技人学硕士论文 1 1 前言 第一章绪论 以i n t e r n e t 为代表的信息网络同益成为国家信息基础设旎的基本重要组 成部分，它已经渗透到社会的各个领域，成为国家进步和社会发展的基本需 求，是未来知识经济的基础载体和支撑环境。高性能信息网络的研究、建设 和应用水平已经成为衡量一个国家基本国力和经济竞争力的重要标志，在经 济可持续发展中发挥重要的作用。 基于i p 的网络在今后网络发展中将占主导地位已成为业界不争的事实 1 1 1 2 1 。从网络传输角度来看，国外一些大的网络运营商为解决带宽问题已经 纷纷大量铺设o c 一1 9 2 ( 1 0 g b p s ) 接口的光缆，如美国的a t & t 在c a m b r i d g e 和m a s s 到n e wy o r k 之间、c a b l e w i r e l e s s 公司在n e wy o r k 到 w a s h i n g t o n 之间、g l o b a lc r o s s i n g 公司在c l e v e l a n d 到c h i c a g o 之间等均采 用o c 一1 9 2 接口的光纤传输，此外其他公司如q w e s t ，s p r i n t 等也由o c 一4 8 升级到o c 一1 9 2 。a t & t 和q w e s t 还进行了o c 一7 6 8 ( 4 0 g b p s ) 接口的光传输 试验。在国内省级网络干线也将相继采用1 0 g b p s 传输技术，最终完全过度 到l o g b p s ，4 0 g b p s 或更高速率。 路由器是i p 网的支撑设备，完成l p 分组的寻路和转发功能。光传输网 容量的提升，决定了路由器容量也要相应提升。一台具有5 0 个o c 一1 9 2 接口 的路由器交换容量将达到t 比特级，而对连接核心网的骨干路出器来说5 0 个端口并不算多。因此，国外已有t 比特路由器在网上试运行。根据d e l l 、o r o 的市场分析报告，2 0 0 1 年的第一和第二季度o c 一1 9 2 接口的超高端路由器销 售已达2 8 6 亿美元，增长为1 6 ，这从市场角度印证了t 比特路由器已渐渐 发撵重要作用。而根掘r h k 公司分机，2 0 0 1 年国际高端路由器市场已达4 5 亿美元，而2 0 0 4 年已经增加到1 8 0 亿美元。 同时在技术方面，无论是高速线卡、大容量交换单元、交换结构，还是 调度算法理论研究、并行或分布业务调度处理等，随着半导体技术、光电子 技术等的发展，目前均能支持o c 1 9 2 的接口速率和几百g b p s 的交换容量， 币向o c 7 6 8 的接口速率和t 比特级交换容量迈进。 】 电子科技大学硕士论文 光传输、光网络和t 比特路由器将是构成下一代网络核心的三个基本要 素，只有同步发展，才能满足对网络带宽同益增长的需求。而现在的路由器 出于处理能力不够还不能全面支持这些标准接口和新的应用，致使这一巨大 的带宽资源未得到充分利用，发展下一代网络中的t 比特路由器势在必行。 1 2 下一代路由器研发的意义 在对网络业务的增长势头做出乐观的预测的同时，另一方面，一个不容 忽视的事实是当酶i p 骨干网的容量依然能够满足需求。伴随着近两年c o m 经济泡沫的破灭，人们对l t 业的前景不再像以前那样乐观，至少是更为审慎。 现实的情况是：电子商务与电子政务并没有发展到如业界当初预计的那种规 模，网上视频、音频服务等由于种种原因也未能在整个因特网范围内大行其 道，i p 电话、电视会议等通信业务也远不及传统的电话、会议业务普及，人 们使用因特网得到的服务中的绝大多数还只限于早已出现的w e b 浏览、电子 邮件、f t d 文件传输、b b s 等。总之，除了用户数量还会进一步增加之外，i p 网络业务量的其他的显著增长点到底在哪里，目前并不明朗。在这种情况下， 是否应陔对未来网络业务的增长势头进行新的估计呢? 现在研究超过现有需 求的下一代t 比特级路出器是否合适呢? 这个问题的答案可以到i t 业的发展历史中去寻求：在持续发展方面， i n t e l 公司与m i c r o s o f t 公司堪称业界典范，他们的成功经验可以给我们一些 启示。i n t e l 公司与m i c r o s o f t 公司的业务范围相差很远，但在经营之道上却 有相似之处：前者占据了硬件方面的龙头一一芯片，后者则占据了软件方面 的龙头一一操作系统：两者的产品都以持续的，定期不定期的升级换代而著 称，而i n t e l 更是将这种升级换代上升到了理论高度一一这就是著名的“摩尔 定律”。从经济学的角度讲，这种升级换代的做法是值得质疑的：i n t e l 与 m i c r o s o f t 是怎样处理他们产品的升级换代与市场需求之帕j 的关系的呢? n t e l 公司产品的升级总是走在市场需求的前面。当初，每当i n t e l 发布他 们的新一代c p u 时，总会有这样的疑问：用户有必要购买这么强大的c p u 吗? 什么样的软件才需要这么强大的c p u 昵? 然而当业界逐渐习惯了i n t e l 的这种 看似不讲道理的做法之后，人们爿恍然大悟：i n t e l 的新c p u 不是在适应市场， 而是在丌拓市场。新的c p u 推出之时，尽管与当前的软件相比显得超前，但 2 电子科技大学硕士论文 软件商必然会很快丌发出能够充分利用这一c p u 的处理能力的软件来。新的 c p u ( 或者更广泛一点，新代硬件) 使得更耗硬件资源的新软件成为可能， 而新软件使得新c p u 不乏市场。于是c p u 与软件形成了相互推动的发展模式， 讵是这一模式成全了i n t e l 的持续繁荣。丽这一模式能得以形成的先决条件 是：c p u 是软件运行的平台。 类似的情况也出现在m i c r o s o f t 公司的产品身上。当m i c r o s o f t - - 次次的把 它们操作系统进行升级时，他们不是以软件市场需求的适应者的身份而是以 市场需求的缔造者、市场潮流的引导者的身份进入市场的。首先有了一代的 w i n d o w s 操作系统，然后才出现各种以该操作系统为平台的应用软件。如果 这些应用软件是“雨后春笋”，那么w i n d o w s 就是“雨”。当这一轮的“笋” 长得差不多了，下一场“雨”也就到来了，于是又开始了下一轮的生长。很 明显，操作系统是应用软件的平台。事实上m i c r o s o f t 紧紧抓在手的并不是狭 义的“操作系统”，而是广义的“应用软件平台”。在网络时代，m i c r o s o f t 牢牢抓住浏览器市场不放，近来又推出n e t 的概念，这些正是网络时代的“应 软件平台”。 可见，平台的发展与基于该平台的应用的发展是相互推动的，而前者可 以居于主导地位。一旦这种相互推动的模式存在，那么平台的发展就可能保 持下去，于是具有平台地位的技术也就具有强大的生命力，抓住平台技术就 成为保持持续发展的途径之一。路由器技术f 是这种平台技术之一，路由器 与网络服务的关系，可以类i ：l c p u 与软件的关系。如本节一开始所述，目| i f 路由器的发展并没能马上带动网络业务的迅猛增长，这罩有技术上的原因， 也有很大一部分原因在于法律法规和其他行业的传统方面。如果这些障碍能 被消除，路由器技术的平台地位就能得到体现，因此很有可能得到一段时期 的持续发展。正是基于这种考虑，尽管t i ：l 特路由器的容量超过了目前网络 业务量的需求，但由于其具有的平台地位，进行t 比特路由器技术研究是很 有必要的。就算我们进入t 比特网络时代的时刻可能被推迟，现在发展tl l 特 路由器技术也可以作为一种非常有用的技术储备。 1 3 当前核心路由器存在的问题和发展方向 近年来，1 s p 、i c p 或其它网络运营商正同益面临着来自维护和升级其核 心网络的巨大压力，迫使他们寻求更先进的交换路由设备来满足用户需求并 降低总体费用。概括而苦，当前核心网络设备的问题在于： 系统升级代价高。带宽需求的增长使得服务供应商不断地对路山器 电子科技大学硕士论文 厂商的新一代产品进行评估、测试、安装等，以提高其核心路由的 容量或链路速率。往往是新的设备更薪完成，马上又计划另一次升 级方案的开始。这种系统升级是跳跃式的，并带来一系列问题，如 设备更新时引起网络服务的中断，系统操作维护人员要兼顾新设备 的评估和测试，同时要针对新的网络平台进行大量培训。 系统可靠性下降。由于目前的路由器尚无法提供很高的可靠性保证， 网络运营商不得不在网络层进行复杂的设计以提高核心系统的可靠 性，如大量网络设备的冗余配嚣；同时当单个路由器无法满足交换 容量要求时，要采用多个路由器的互联以构成更大的交换网络，每 个路由器必需分别进行设置、维护，并对可能的关键路由进行保护， 从而使得网络拓扑复杂化。当系统升级时，任何设计上的疏忽都将 导致整个交换系统的不稳定。 维护过于复杂。为提高核心路由系统的容量，目前的选择是采用多 个独立的路由器构成交换网。这些路由器必需单独进行配置、维护， 从而增加了人为因素导致网络瘫痪的概率，据统计这种影响已高达 7 0 ，并由此而增加了网络维护工作量、提高了网络复杂度、还需 要针对网络中新设备进行大量的培训等。 所有这些最终导致核心路出系统的总体费用增加，使网络运蕾商不仅要 面对设备维护、容量扩展等问题，而且要面对成本控制的问题。一般而言， 设备投资中核心路由器所占费用是最高的，但背板、线卡等每次系统升级剐 无法重用，当核心系统由多台路由器构成时，还必需占有宝贵的用户端口来 实现系统间的互联，进一步提高了设备投资。但这些还仅占总体费用的1 4 ， 更大的压力来自系统的运行，例如不断地“评估一测试一安装”过程、对f i 益复杂网络系统的配置、维护等。而这些问题是目莳路出器技术所无法解决 的，必需采用新的设计思想和结构。这种结构必需在以下方面有本质的前提： 灵活的扩展性 下一代核心路由器的规模必需是可扩展的，体现在其端口数和吞吐量方 面，可扩展系统应能够同时支持数千个用户端口，单机框内部的交换单元应 能根据要求进行升级，同时交换网络的吞吐量不仅要支持所有用户业务的交 换，而且要满足多机框问业务的交换( 该多机框问转移的业务带宽亦称为 b i s e c t i o n 带宽) 。端口速率方面，不仅要支持o c 4 8 、o c 一1 9 2 等，而且可 通过端口汇聚技术向用户提供o c 7 6 8 连接。系统的可扩展性不仅要体现在 交换规模上，还要体现在维护、升级、可靠性等方面，如多机框路出系统在 电子科技大学硕士论文 操作上对单个路由器的等效、系统在线软硬件升级、关键路由的保护等。 增强的可靠性 为尽可能降低系统异常当机的时间，下一代核心路由器必需增强可靠 性，并支持在线升级。在高可靠的系统中无单一故障点，任何部件均做冗余 备份，包括背板、控制卡、交换卡、电源、冷却等；不仅单机框系统内的模 块要备份，线卡与交换模块、交换模块之f 刚、机框之间等的高速链路也需要 备份；同时不仅标准网络协议处理要备份，如i p 、m p l s 等，而且交换系统 内部互联协议处理也要备份。 通过硬件级对失效单元的迂回来保持业务流的连续性，通过分布式软件 处理来提高性能和运行的鲁棒性，核心路由系统可在网络协议模型的更底层 实现容错，从而保证上层协议运行的可靠性。这样不仅提供了更快的恢复时 间，而且无需服务提供商在网络设计或升级时过多地作系统级的冗余备份， 降低总体费用。 优异的交换性能 核心路由系统所能提供的不仅是巨大的交换带宽，而且要根据用户要求 提供不同类型的服务。目前的路由器已能够部分满足优先级的要求，但所支 持的种类还很有限，特别当大量端口同时使用时，其包转发速率将很快下降。 下一代核心路由系统则必需满足所有端口线速分组处理，并同时提供功 能强大的q o s 功能【3 1 1 钔，如流分类、警管、调度、成型等。这要求不仅线卡 能够以线速对输入输出分组进行处理，而且要求交换网内部带宽、仲裁等满 足所有端口业务的快速、公平的交换。 1 4 路由器交换结构概述 路由器作为i n t e r n e t 网中负责业务转发的核心设备，主要包括两个功能 模块1 5 1 ：数据传送面( d a t ap a t hf u n c t i o n ) 和控制面( c o n t r o lf u n c t i o n ) 。前 者对每个到达路由器输入端口的分组进行处理、转发；而后者主要负责路由 表的更瓤和维护。由于数据传送面属于实时处理范畴，因此在设计高速路由 器时主要瓶颈在于数据传送面的处理速度。数据传送面主要有以下几个功能： ( 1 ) 转发判决：负责路由表查找，从而决定分组的输出端口；( 2 ) 交换背板 ( b a c k p l a n e ) 传送：交换背板也就是路由器的内部互连网络( i n ， i n t e r c o n n e c t i o nn e t w o r k ) ，它是连接输入输出端口的物理通道；( 3 ) 输出端 口判决：分组在到达输出端口后，同样是先进行缓存，由输出链路调度器决 电子科技大学硕士论文 定分组的发送时问。一般输出缓存采用f i f o 队列，但有的路由器也为不同 的业务流提供独立的排队缓存，山调度器束实现区分业务服务，提供q o s ( q u a l i t yo f s e r v i c e ) 保证。图1 - 1 是一个路出器基本参考模型的示意图l 6 1 。 交换甜；构 一一一 输入端内娜_ j ：_ 连结构输m 端 x 图1 - 1 路由器基本参考模型 在核心路由器设计中，交换结构( s w i t c hf a b r i c ) 对系统性能具有决定 性影响，如交换容量、交换时延、扩展性等。在目前已经成熟的g 比特级交 换机路由器( g s r ，g i g a b i ts w i t c ha n dr o u t e r ) 中，以单级c r o s s b a r 结构可 提供最佳的性能，如无阻塞交换、低的交换时延等，但其扩展性较差；相对 灵活的结构则采用时分空分相结合的方式，例如m s m ( m e m o r y s p a c e m e m o r y ) i7 1 可提供无阻塞或近似无阻塞交换性能的三级 c i o s 网络1 8 】，交换容量可接近t b p s 。这两种交换结构及其相关的交换调度算 法、流量控制算法等，都有大量的研究，并在实际产品设计中得到应用，如 p m c s i e r r a 公司的e t t l 芯片组、a g e r e 公司的p 1 4 0 芯片组等。但在系统的 扩展性、可靠性等方面，这些交换结构是有缺陷的，如系统交换容量无法平 滑扩展、系统中存在单点失效问题等。同时，由于必须采用集中式调度器， 当用于实现t 比特级路由器时，其处理速度极大地限制了系统容量的提升。 a v i c is y s t e m i9 j 的t 比特级交换机路由器( t s r ，t e r a b i ts w i t c ha n dr o u t e r ) 采用了三维t o u r s 结构，其交换结构如图1 - 2 所示，采用了在大型多处理机 系统( m u l t i p r o c e s s o r s ) 上常见的虫孔交换技术( w o r m h o l e ) l i e l 。它的交换 结构不同于传统意义上的分布式交换结构，它可以实现真正的线性升级，系 统的交换容量可达5 6 t b p s 。s t a n f o r d 大学的n i c km e o k o w n i “j 领导的研究小 组构建了一种光电结合的交换结构，采用m e m s 技术 ( m i c r o e l e c t r o m e c h a n i cs y s t e m ) 的光交叉互连设备作为核心互连背板，前 端多个小的电交换单元来连接输入输出端口，利用光互连来互连多个交换单 泖叫划纠多卜 = 一 i i 一 二一 二一 = 一 二一洲卜旷鼍一 电子科技大学硕十论文 元，从而实现交换容量可达l o o t b p s 的路由器，其交换结构如图1 3 所示。 这种基于m e m s 技术的交换结构基于台湾清华大学张尚正教授提出的负载 平衡的b i r k h o f f - m o r tn e u m a n n 交换机( l o a d b a l a n c e db i r k h o f f - v o nn e u m a n n s w i t c h ) 1 2 m 】，下文简称为负载平衡交换机。负载平衡交换机具有良好的可 扩展性，同时也可以提供1 0 0 的吞吐量保证；同时作为一种新的交换结构， 负载平衡交换机还有着一些亟需改进的地方。本文将着重分析负载平衡交换 机的各项关键技术，提出了解决的方案，并给出了仿真的结果。 幽1 2a v i c i 公司4 3 x 2 t o u r s 结构酗i - 3s t a n f o r d 交换结构示意酗 1 5 本文课题的来源和研究的内容 本文涉及的课题来源于国家自然科学基金，项目名称为“k 元n 方网络 构建可扩展交换结构的关键技术研究”，基会号为6 0 3 7 2 0 1 1 。 第二章介绍了负载平衡交换机的基本结构并分析其交换性能，并简要描 述了负载平衡交换机的关键技术问题和实现方案。 第三章从理论上分析了负载平衡交换机在多优先级负载输入下的，采用 抢占( p r e e m p t i v e ) 方式的优先级策略时的吞吐量和平均时延，计算机仿真 结果检验了分析的f 确性。 第四章介绍了当i i f 保证分组顺序通过负载平衡交换机的一些算法，并提 出了一种全新的满帧填充算法( f f s ，f u l lf l a m es t u f f ) ，该算法易于实现同 时也具有良好的交换性能。 第五章介绍了o p n e t 软件仿真模块的设计方案，给出了程序的流程图。 第六章总结全文并晚明负载平衡交换机以后的研究方向。 最后是致谢和参考文献。 7 电子科技大学硕士论文 第二章负载平衡交换机综述 2 1 负载平衡交换机的基本结构 2 1 1 假定说明 在详细介绍负载平衡交换机的基本结构之前，首先作如下说明：1 所有 到来的变长分组在穿过交换机前被截取为定长分组，在输出端口重新进行组 合离开交换机；2 所有的链路通过线卡连接到交换机，一个线卡集合了一个 输入端1 3 和输出端口以及中间输入，本文所讨论的负载平衡交换机的端口数 目设定为，即交换机由个线卡组成；3 连接每个线卡的链路线速相同， 并且按固定时隙工作，因此每个时隙每个输入端口最多只能到来一个分组， 每个输出端口最多只能有一个分组离丌交换机；4 最后，我们假定初始时刻 交换机内部不存在任何分组。 2 1 2 虚通道流控制技术 在负载平衡交换机中，交换机内部缓存采用了虚输出队列( v o q ，v i r t u a l o u t p u tq u e u e ) ，这种虚通道技术在交换结构中有着非常广泛的应用，下而将 对虚通道( v c ，v i r t u a lc h a n n e l ) 技术进行深入的分析说明。 2 1 2 1 虚通道问题的提出 传统交换结构中每个通道对应了一个缓存，一旦分组a 分配了缓存缸， 别的分组就不能使用缓存岛对应的通道c 。，直到分组a 释放包。在使用分组 级流控制的网络中，分组a 在持有缸的时候因为网络中别的地方发生 井j 塞而 被阻塞。在这种情况下，即使网络中有别的分组想使用，通道c 也会被闲 置。这种情况可以如图2 一l 所示，在2 ，1 中圆形框代表一个节点，实箭头代 表两个节点间的通道，长方形框代表分组缓存，虚箭头代表前进的路由方向。 分组a 在持有缓存3 e ( 节点3 的东部) 和4 s 的时候被阻塞，因为分组a 占 用了缓存3 e ，即使分组b 可以获得所需要的所有物理通道( 1 e 到2 w ，4 e 到5 w ) 也不能转发。这个通道空闲问题主要是因为交换网络实现的是唯一 资源对结合的原因，即分组只有同时拥有通道和对应的缓存才有可能被转发。 8 电子科技大学硕士论文 n o d ein o d e2n o d e3 n o d e4n o d e5 一p a c k e tap a c k e tb d e s t i n a t i o n o fb 图2 - 1 物理通道空闲时分组a 后面的分绸b 仍被阻塞 另外，一些自适应路出算法要求在相邻节点对间有多对通道，用物理线 路来布置这样的网络是相当昂贵的，而且在大多数的情况下这些通道的使用 率不高。解决这些问题的一个办法就是使用多个虚通道来复用一个物理通道， 每个虚通道有自己的缓存。通过虚通道的使用，一个物理网络可以划分成多 个互不相连的逻辑网络，方便了自适应路由算法的设计| 1 “。 虚通道在两个方面非常有用。一方面，通过提高网络的连接度可以绕过 网络中的拥塞热点和失效的节点。另一方面，虚通道可以为某些类的分组提 供保证通信带宽的能力，例如，为支持一些系统相关的功能( 如调试，监视， 渗断等) 保留一些带宽是非常有意义的。 虚通道包括一个可以容纳某个分组的一。个或多个分组的缓存以及相应 的状态信息。几个虚通道可以共事同一个物理通道的带宽。通过为网络中的 通道提供多个缓存，虚通道减弱了缓存分配和通道分配间的耦合关系。如果 阻塞的分组a 持有一个与通道c 相关的缓存包，另外一个缓存包，仍然允许 别的分组超过分组a 。相对图2 一i 中的网络，图2 2 给出了实现虚通道后的 情形。分组a 在持有缓存3 e 1 和缓存4 s 1 被阻塞，因为3 e 2 可用，允许分 组b 使用3 e 到4 w 的通道，从而分组b 可以超过分组a 继续前进。 w o d r 】n o d e2n o d e3n o d e4n o d e5 d e s t i n a t i o n o fb p a c k e t a 目p a c k e t b 斟2 - 2虚通道提供了额外的缓存以允许分组b 超越被阻塞的分组a 2 1 2 2 虚通道的构造 交换结构中的每个节点都包括一系列缓存和一个交换单元。节点缓存的 组织方式有如f 两种：传统网络通道对应的缓存是按先进先出队列的方式来 组织的，如图2 - 3 ( a ) 所示，这种结构严格限制了个缓存只能包括个分 。 形 一 刨 电子科技火学硕+ 论文 组，如果这个分组被阻塞，这条物理通道就闲置了，因为别的分组不能得到 需要的缓存资源以利用这条物理通道。使用虚通道的交换结构把每个通道对 应的缓存按虚通道数分成了多组，即每组输入缓存对应一个虚通道，如图2 - 3 ( b ) 所示。每组缓存的分配独立于其他组缓存的分配。这种分配的灵活性提 高了通道的使用率，相应地也提高了系统的吞吐量。一个被阻塞的分组，只 会在路由经过的节点上占用一个虚通道，不会影响其他虚通道对物理通道的 使用。 幽2 3( a ) 传统讧点的缓存组织形式( b ) 采 ! j 虚通道流控制的缓存形式 2 1 3 负载平衡交换机模型 负载平衡交换机的基本结构如图2 - 4 所示，负载平衡交换机具有个缓 存的中问输入级，位于两个相同的交换级中问。输入级与中间输入级相连， 中间输入级与输出级相连，因此负载平衡交换机也是两级交换机。中间输入 级的每个缓存被分为个独立的f i f o ( f i r s ti nf i r s to u t ) 队列，每个队列对 应着一个输出端口，我们称其为虚输出队列( v o q ，v i r t u a l o u t p u tq u e u e ) 。 每个交换级都按照预先设定的时序构造连接方式。两个交换级的连接时序可 以相同也可以不同，本文中所讨论的两级负载平衡交换机的连接时序为：在 时隙t 时，第一级输入i 与输出m + o m o d u l om 相连，第二级输入f 与输出 ( ( t - j ) m o d u l o m 相连，下文如不特别说明都将按照这种方式连接。负载平衡交 换机的两个交换级都按照固定的时隙周期性连接，两个交换级的每个输入和 输出在一个周期内只能连接一个时隙，而与当前到来的分组无关。 电子科技大学硕士论文 输入输出 蚓2 - 4负载平衡交换机的基本结构示意图 负载平衡交换机的两级交换结构虽然都按固定的时隙构造连接方式，但 是具有不同的功能，第一级具有平衡负载的作用，把业务量均匀散御到中问 输入的v o q 中；第二级具有交换的功能，与输入队列交换机一样，把中间 输入中v o q 的分组送到输出端口。当分组到达输入端口时，根据第一级交 换结构的连接方式送到中l 瑚输入；当分组到达中问输入时，按照分组的输出 端口存放到中间输入对应的v o q 队列中；过一段时间，当中间输入与某一 输出相连时，如果中间输入中对应v o q 中存在分组，则把分组通过第二级 交换结构送到输出。 2 2 负载平衡交换机交换性能分析 2 2 1 负载平衡交换机吞吐量分析 2 2 1 1 负载平衡交换机提供1 0 0 吞吐量条件 我们将对负载平衡交换机的吞吐量进行分析，在2 1 中我们已经知道负 载平衡交换机的第一级交换结构在适当的技术条件下可以将非均匀分和的业 务模型转化为均匀分布的业务模型，从而使得负载平衡交换机可以想输出队 列交换机一样达到1 0 0 吞吐量的保证。 为了我们分析的方便，我们假设两级交换结构的置换矩阵丌始于独立均 匀分粕的相位。近一步分析可知，作为周期性的置换矩阵，p ( o = p “l j ，t = n r o o dn ) ，p 为一个具有周期性的置换矩阵。我们假设“和u 为集合 0 ，1 ，2 ， l 1 ) 中独立同分柿的随机变量。这旱我们令p j 似和p 2 似为第一级交 换结构和第二级交换结构在时隙t 时的置换矩阵，则有： l l = l 子科技大学硕士论文 只( f ) = p ( f + 己，。)( 2 - 1 ) 只( f ) = e ( t + u ：)( 2 - 2 ) 我们作如下假设说明： r ：n x n 阶矩阵r = ( 7 ，) 表示输入负载的平均速率矩阵，r i , ，j 表示输入端口 i 前往输出端口j 的平均速率( 1 j 忉。 n ( f ) ：n x n 阶矩阵口( f ) = ( 口u ( f ) ) 表示时隙t 时的输入端口的负载矩阵，其 中口i 如) 表示时隙t 时在输入端口i 前往输出端口j 的分组数( 1 t j 奶。出 于负载平衡交换机输出端口排头每个时隙只能到来一个分组，因此a i m ( r ) = ( 0 o r1 ) ，a i , , j i ( f ) 的均值为7 t j 。 6 ( f ) ：n x n 阶矩阵6 0 ) = ( 6 u ( f ) ) 表示时隙t 时通过第一级交换结构到达中 间输入的负载矩阵，其中b i , o ( t ) 表示时隙t 时到达中闯输入i 中前往输出端口 j 的分组数( 1 j 奶。负载平衡交换机每个时隙只能发送一个分组，则有 b i , , j ( f ) = ( oo r1 ) ，则有： 6 ( f ) = p l ( t ) a ( t )( 2 - 3 ) 这里我们先回顾以下几个随机过程中常见的概念：各态历经 ( e r g o d i c i t y ) ，弱混合( w e a km i x i n g ) 以及强混合( s t r o n gm i x i n g ) 。它们 都反映了随机序列丢失记忆的程度1 1 5 1 1 托】。对于一个随机序列口( f ) = ( 口f j ( f ) ) ， 它的时移序列d o + 5 ) = 0 j ( f + s ) ) 。如果随机序列口( r ) 和它的时移序列d o + 5 ) 具 有相同的概率密度分布，随机序列口( f ) 是一个平稳过程，对a x n ) ，则有： p 0 ( f ) 爿) = p ( a ( t + s ) e a )( 2 - 4 ) 平稳随机序列口( f ) 满足各念历经的条件，对a ，b 俾，则有： l i m l f 箭亏4 p ( 拉( f + s ) 爿，( f ) 丑) 互p ( 8 9 + s ) 爿) p q ( f ) b ) ( 2 - 5 ) 平稳随机序列口( f ) 满足弱混合的条件，对a ，b 一，则有： l i m l f 箭警t p ( 4 ( f + s ) 爿，( f ) 曰) 一p ( d o + s ) 爿) p ( o ) 啡o ( 2 - 6 ) 平稳随机序列n ( f ) 满足强混合的条件，对a ，b 。1 ，则有： l i m p ( a ( t + s ) 爿，口o ) b ) = p ( a ( t + 5 ) 一) p o o ) b )( 2 7 ) 很明显，强混合意味着弱混合，他们都意味着各态历经。平稳、各态历 经的随机序列口( f ) 最重要的特性为时间平均等1 二统计平均，则有： 电子科技大学硕士论文 l i r a - ty 口( s ) = k ( 1 ) ( 2 - 8 ) t 盏 相应地，v o nn e u m a n n 和b i r k h o f f 都得出了一个重要的结论，即可以把 矩阵的转黄和周期性的重复看成是各态历经的过程。因此，p j ( 式2 - 1 ) 和p 2 ( 式2 2 ) 都可以看成平稳的各态历经的序列，它们的平均速率为 e ( 1 n ) ，其中e 为n x n 阶单位元素全为1 的矩阵。由( 2 - 8 ) 有( 其中f = 1 ，