（通信与信息系统专业论文）obs边缘节点数据包突发汇聚的研究与实现.pdf

摘要 因特网的爆炸性发展和各种新业务的出现，促使研究者们加快对波分复用 ( w d m ) 传输和全光交换技术深入研究，以便适应这些变化。在新业务大多是 坤业务的情况下，出现了先进的i po v e rw d m 网络分层结构。由于这种结构省 去了传统的a t m 和s d h 两个中间层，使传输效率有很大提高。目前由于密集 波分复用( d w d m ) 技术的进步使得一根光纤上能够承载上百个波长信道，光 纤传输网络面临的问题是交换速率的瓶颈。光突发交换是下一代i p o v e rw d m 光因特网的一种有效的光交换方案。缓解了由于现在的电子瓶颈而导致的带宽 扩展困难。本课题一一光突发交换关键技术与实验系统就是在此背景下产生的， 这是我国8 6 3 计划重点资助项目。 本文是关于光突发交换输入边缘节点实现的应用性文章。在说明了光突发 交换的优越性后，文章紧接着对光突发交换体系中核心节点，边缘节点的功能 进行阐述。对输入边缘节点的关键实现方案进行了讨论。接着讲解了在实现输 入边缘节点时功能模块的划分。此后，文章详细说明了输入边缘节点中数据排 队模块的实现过程，数据排队模块采用的是本文提出的v i s p 算法实现其调度功 能。最后，讲解了输入边缘节点的硬件设计，包括原理图设计，器件选型和高 速p c b 的布线。 本文的创新点在于：1 、将通用多协议标签交换( g m p l s ) 用于光突发交 换输入边缘节点设计中。2 、根据输入边缘节点口数据包变长调度的特点，吸 收了常用于路由器中的i s p 调度算法的思想，提出了v i s p 调度算法。3 、将v i s p 算法用硬件描述语言描述了出来，并且在f p g a 上实现。比较了v i s p 和i s p 实现的性能和资源占用情况。4 、在输入边缘节点p c b 设计中，在理论和实际 结合的情况下对高速信号布线进行了分析。 在课题中的成果：1 、提出v i s p 调度算法并在f p g a 上实现其功能。2 、 设计输入边缘节点主要原理图。3 、实现输入边缘节点高速p c b 板的设计。 关键词：波分复用，i po v e r w d m ，光突发交换，输入边缘节点，突发汇 聚，流分类，分组排队，高速p c b a b s t r a c t n o w a d a y s ，a s t h er a p i de x p a n d i n go ft h ei n t e r a c ta n dt h ee m e r g e n c eo fn e w n e t w o r ks e r v i c e s ，r e s e a r c h e r sc o n c e n t r a t eo nt h ed e n s ew a v e l e n g t hd i v i s i o n m u l t i p l e x i n g ( d w d m ) t e c h n o l o g y a n d s w i t c h i n g i n - o p t i c a ln e t w o r k a i m i n gt o s o l v et h ep r o b l e mm e n t i o n e da b o v e ，m o s to f t h en e ws e r v i c e sa r eb a s e do ni n t e m e t p r o t o c o l ( m ) ，s oa p p e a r st h ei po v e rw d m n e t w o r ka r c h i t e c t u r e i tc a n g r e a t l y i m p r o v e t h et r a n s m i t t i n ge f f i c i e n c y b yl e a v i n g o u tt h ea t ma n ds d h l a y e r so f t h e n e t w o r ka r c h i t e c t u r e t h ed e v e l o p m e n t so f d e n s e w a v e l e n g t h d i v i s i o nm u l t i p l e x i n g ( d w d m ) t e c h n o l o g y h a v em a d ei tp o s s i b l et os e r v em o r et h a no n eh u n d r e d c h a n n e l si na s i n g l eo p t i c a lf i b e r b u t a tt h es a m et i m et h ep e r f o r m a n c eo ft h eo p t i c a l n e t w o r ki sl i m i t e db yt h es w i t c h i n gt e c h n o l o g y o b s ( o p t i c a lb u r s ts w i t c h ) i sa g o o dw a y t or e a l i z et h ei po v e rw d m o p t i c a ln e t w o r k o u rr e s e a r c h ，w h i c hi s s u p p o s e t or e s e a r c ho b sn e t w o r k k e yt e c h n o l o g y ，i ss u p p o r t e db y t h e n a t i o n a l8 6 3 p l a n ” t h i sp a p e ri sm a i n l ya b o u tt h ea p p l i c a t i o no fo b s e d g en o d e f i r s t l y ，i t i n t r o d u c e st h es u p e r i o r i t yo fo b sa n da c c o u n t sf o rt h ef i m c t i o no f t h ec o r en o d ea n d t h ee d g en o d eo f o b s s e c o n d l y ，t h ek e yi m p l e m e n t a lm e t h o d s o f i n g r e s se d g en o d e a n dt h ed i v i s i o no ff i m c t i o nm o d u l ea r ed i s c u s s e d t h i r d l y , i ti l l u s t r a t e st h e i m p l e m e n t a t i o n o f t h es c h e d u l i n gm o d u l ei ne d g en o d ew i t ht h ev a r i a b l ei n g r e s s s e r i a lp o l l i n g ( v i s p ) a l g o r i t h m f i n a l l y , t h ed e s i g np r o c e d u r eo fo b s e d g en o d e i n t h es c h e m a t i ca n d p r i n tc i r c u i tb o a r d 口c b ) w i l l b e p r e s e n t e d t h ei n n o v a t i o n so f t h i sp a p e ra r ep r e s e n t e da sf o l l o w ： 1 g e n e r a lm u l t i p r o t o c o ll a b e ls w i t c h i n g ( g m p l s ) i sa d o p t e di n i m p l e m e n t i n g o b s i n g r e s se d g en o d es y s t e m 2 a na l g o r i t h m ，b yt h en a m eo fv i s pw h i c hi sb a s e du p o ni s p ，i sd e s i g n e dt o a c h i e v ev a r i a b l ed a t as c h e d u l i n g 3 s u c c e s s f u ld e s c r i p t i o no f v i s pa l g o r i t h mb yv e r y h i g h s p e e di n t e g r a t e d c i r c u i th a r d w a r ed e s c r i p t i o nl a n g u a g e ( v h d l ) a n da c c o m p l i s h m e n t i nf p g a 4 t h e o r e t i ca n d p r a t i c a la n a l y z i n g o f t h ep c b d e s i g ni nh i g hs p e e dl a y o u t i i k e yw o r d s ：w d m ，i p o v e rw d m ，o b s ，e d g e n o d e ，a s s e m b l e ，c l a s s i f y ，q u e u e h i g hs p e e d p c b 1 i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：垄：垫日期：一f 年- 月砖日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：查垄导师签名：煎! 日期：口 a ) 之后将相应的数据发送出去( 在图2 3 中，假定源宿端 之间只有3 跳，即h = 3 ；同时假定控制分组在每一跳的传输和处理时间之和为6 ， 从而= 36 ) 。由于突发包是在源节点处缓存，所以在中间节点处就不需要缓存a j e t 的另外一大特征延迟预留( d e l a y e d r e s e r v a t i o n ) 的思想如图2 - 3 ( 2 ) 所 示。在节点i 的出口端，资源是从时刻t 开始预留( 这里，时刻t 就是突发包到达 节点i 的时刻) 而不是从时刻t 开始预留( 而时刻t 是节点i 处理完毕其相应的控 制分组的时刻) 。而且，带宽的预留持续时间只限于突发包的传输时间段( 在图 2 - 3 中，这一时间段是1 ) 。 通过充分利用每一个突发包的持续时间等有用信息，延迟预留d r 可以提高 利用f d l 的有效性，正如它可以通过合适的调度来提高带宽利用率一样a 1 3 电子科技大学硕士学位论文：o b s 边缘节点数据包突发汇聚的研究与实现 2 _ 3 边缘节点设计的功能模块划分 由于边缘节点的功能就是围绕突发包的组装和调度来的，所以本节先说明突 发包及控制分组的格式，然后介绍我们设计的输入边缘节点总功能框图，接下来 对各个功能模块进行详细说明。 2 3 1 突发包及控制分组( b h p ) 的格式 1 、突发包封装后的格式 图2 4 设计中使用的突发包格式 第二层突发包 第一层 关于d b 和b h p 的格式，目前并无统一的标准，图中突发包格式是我在o b s 输 入边缘节点设计中使用的的d b 格式。其中p t ( p a y l o a d t y p e ) 、n o p ( n u m b e r o f p a c k e t s ) 、p l ( p a y l o a dl e n g t h ) 为净荷所对应的头标。图中各部分具体含义如下： 表2 1 突发包说明 中文对照 g u a r d - b s v n c p t n o p p l 保护带 同步码，来同步输入端边缘节点与输出端边缘节点 净荷类型，根据其中净荷中分组的q o s 等级和目的地址分类 净荷中所含的口分组数 净荷长度 p a y l o a d 净荷 由于o b s 网络中各个节点的时钟不可能完全同步，可能再节点出现时钟漂移 ( 也就是说各个节点的时钟之间有偏差) ，不同波长之间的延迟差异从而突发包 1 4 电子科技大学硕士学位论文：o b s 边缘节点数据包突发汇聚的研究与实现 的到达时刻以及突发包的持续时间就具有一定的不确定性。设置g u a r d b 的目的 就是为了克服这种不确定性。 2 、控制分组( b h p ) 的格式 控制分组( b h p ) 的格式如图2 - 5 所示，其内部数据信息如表2 - 2 所示 图2 - 5 本设计中b h p 的格式 表2 2b l i p 的内部信息说明 作用 优先级指明了该b h p 对应的突发包的服务等级 偏置时间指明b l i p 和突发包到达本节点的偏移时间 选用信道占用的波长信息 包长度 包括了整个d b ( 净荷和头标) 偏置时间指明b h p 和突发包到达本节点的偏移时间。为了减轻网络处理b h p 的压力和减少b h p 对网络资源的竞争以及降低网络中各种调度算法的复杂性，可 以将偏移时间量化成一些离散值。这样，b h p 就不必携带具体的偏移时间而是携 带一个整数，该整数表示b h p 与其相应的突发包的偏移时间是某个晟小值的多少 倍。 2 3 2 输入边缘节点功能框图 我们设计o b s 输入边缘节点实现从以太网接收口包，然后对它进行流分类和 数据排队，之后数据包进入缓存，突发包组装器根据一定的组装算法将它们组装 成为突发包。突发包经过波长调度模块之后，输入光电转换模块，转变成光信号， 然后通过d w d m 进入光纤，传往下一个节点。同时波长调度模块也将产生相应的 电子科技大学硕士学位论文：o b s 边缘节点数据包突发汇聚的研究与实现 b h p 信号送往光纤。 输入边缘节点的功能框图如图2 6 ； 2 3 3 路由信息处理 本模块实现如下功能 图2 - 6 输入边缘节点功能框图 1 、千兆以太网m a c 帧头的拆包 由于边缘节点发送部分的输入连接的是以太网。需要在发送部分拆除m a c 帧头，还原出口数据包，送交到网络层处理( 如果i p 数据包来自于短帧子网时 ( m a c 帧长度小于包长) ，还需对d 数据包进行分段与重组) 。 2 、路由选择和g m p l s 标记功能 即依照本地路由表和g m p l s 标记表，确定单个口数据包下一跳的i p 地址， 若下一跳是本接点的另一业务端口，则只需直接交换，若为远端其他边缘节点， 则需安在光标记交换控制器下，把e p 数据包按目的端1 3 、服务属性( q o s ) 分为 不同的转发等效类( f e c ) ，并且在转发数据包之前发送其标签。以便后面突发汇 1 6 电子科技大学硕士学位论文：o b s 边缘节点数据包突发汇聚的研究与实现 聚和d w d m 光虚通路的建立。 2 3 4 流分类和数据排队 1 、职包流分类：根据收到的g m p l s 标签信息对网络层口数据包进行分类， 按照g m p i 点标签中的目的边缘节点信息和优先级信息把p 包分类缓存，并且把 g m p l s 标签加在i p 包包头上。g m p l s 标签包含目的边缘节点、优先级和长度 信息。功能如图2 7 所示： 图2 7p 包流分类框图 组队列1 组队列n i p 包流分类的功能：根据g m p l s 标签把d 包分类放在不同队列，并将 g m p l s 标签加在p 包头。 2 、数据排队：按照口包包头的g m p l s 标签信息对输入缓存的包分组进 行交换。功能如图2 8 所示： 口分组队列 i p 分组队列 图2 - 8 数据排队功能模块框图 1 7 电子科技大学硕士学位论文：o b s 边缘节点数据包突发汇聚的研究与实现 交换阵在调度器的控制之下，对加了g m p l s 标签后的口包进行调度。使其 分类排队，以等待后续突发包组装。调度的关键是避免阻塞，加快交换速率，提 高带宽利用率。 2 3 5 突发包组装 突发包的组装是o b s 的一项关键技术，直接影响到o b s 的性能。它的核心 是组装算法的选择和实现。参考文献 3 2 中提出了几种算法，并比较了它们各自 的优缺点，其中算法c 最小突发长度最大汇聚时间( m i nb u r s tm a xa s s e m b l y p e r i o d ，m b m a p ) 兼顾了包长和组装时间两个参数，既能有效地利用网络带 宽，又避免了大的网络延迟，是一种较为优越的算法。 m b m a p 算法的基本思想是：当累积p 分组的长度超过设定的最小突发长度 m b l 或者汇聚时间超过时，发出一个控制分组，经偏景时间( o f f s e tt i m e ) 后， 发送突发包。 该模块主要是按照算法把口分组组装成b u r s t 。b u r s t 组装好后如图2 - 9 ： 第二层突发包 图2 - 9b u r s t 的格式 第一层 图q b p t 为突发包类型，n o p 为突发包中包含的i p 分组数，p a y l o a d 为净荷，p l 为净荷长度。突发包类型按照其中口分组的q o s 等级和目的边缘节点的地址分类。 设有m 种优先级，n 个边缘节点，那么对任意一个边缘节点中形成的突发包，其目 的边缘节点地址都有n 1 种可能，于是在每个边缘节点中组装的突发包共有q = m ( n 一1 ) 种。 2 3 6 波长调度及b h p 的发送控制 o b s 边缘节点中非常重要的一个环节就是波长调度。模块的功能如下 电子科技大学硕士学位论文：o b s 边缘节点数据包突发汇聚的研究与实现 1 、采用r o u n d - r o b i n ( 时间片轮转) 算法按照优先级的分类来对输入b u r s t 包排队及请求信息进行轮询，选出当前时刻最需响应请求队列。 2 、读取数据包后对波长状态表进行分析，把突芨包分配到合适的波长上，并 且完成对相应数据包的b h p 数据的组装，同时把突发包缓存起来等待发送。该部 分的运行效率和资源占用情况赢接影响到整个调度模块的工作效率。 波长调度模块的结构如图2 1 0 所示。由于组装的突发包种类可能有q 种，输 入一共有q 列： 图2 1 0 波长调度功能框图 整个设计中最重要的内容就是波长调度模块对各个光波长发送缓存的存储状 态的判别。存储状态包括当前包的长度信息，发送等待时间，发送状态等一系列 重要数据。通常定义第i 个波长的状态表的数据存储格式如图2 - 1 1 所示。 图2 1 l 第i 个波长的状态表的数据存储格式 从图中看出，状态字说明该波长发送缓存是否为禁用；发送缓存长度为整个 1 9 电子科技大学硕士学位论文：o b s 边缘节点数据包突发汇聚的研究与实现 发送缓存当前的存储数据量；第i 个突发包的长度( i _ 1 n ，n 的取值取决于发 送缓存可以容纳的最大突发包数目) 。 为了体现输入突发包的优先级，并且防止发送缓存的“溢出”，调度模块在全 局时钟的控制下实时对状态表的“发送缓存长度”信息进行侦测，筛选出最短发 送缓存，将当前最高优先级突发包交换入该发送缓存并及时将这一操作记录入该 波长状态表。 2 0 电子科技大学硕士学位论文：o b s 边缘节点数据包突发汇聚的研究与实现 第三章输入边缘节点中突发汇聚的研究与实现 光突发交换系统的输入边缘节点对数据进行处理的一个重要环节就是突发汇 聚。所以需要选择一种快速有效的汇聚方案，以保证后续突发包的组装。本人在 设计中负责突发汇聚中的球包流分类和数据排队部分设计。本章主要讨论数据排 队方案的实现。首先介绍一种常见的调度算法i s p ( 3 1 节) ，然后提出一种基于 i s p 的针对变长数据包的调度方案v i s p ( 3 2 节) 。接着详细说明了根据此方案的 硬件实现细节( 3 3 节) ，研究比较了两种算法在现场可编程门阵列上实现的资源 占用与工作频率( 3 4 节) 。 3 1i s p 调度方案 3 1 1c r o s s b a r 与调度 路由器通常由3 个部分组成：输入模块、交换模块、输出模块。其中交换模 块是高性能路由器的核心。影响路由器的吞吐量、时延、硬件实现的复杂度以及 路由器的生产成本。c r o s s b a r 作为一种交换结构具有单级无阻塞的良好特性，可 同时进行多路传输，适用于并行处理，因而在目前的路由器产品中被广泛采用， 如c i s c o 的1 2 0 0 0 系列路由器。 对于c r o s s b a r 结构而言，调度算法的目的实际上是快速寻找一个合理的配置矩 阵，去控$ 0 c r o s s b a r 节点的开或关，使得能够完成数据传输的输入输出端口之间无 冲突。即每一个时隙，每个端口只向一个端发送或接收分组。 3 1 2 调度的两种排队模型 在路由器中，交长的分组到达输入端口时，被拆成固定长度的数据单元，称 为c e l l 或m i n i p a c k e t ，为简单起见，我们称为分组。分组在输入端口排队等候被 交换到目的输出端。不可避免会出现多个输入端竞争同一输出端的情况，对于这 种情况，不同的排队模型有着不同处理方法2 5 1 。 对于基于输出排队模型来说，由于分组仅在输出端缓存，因此所有输入端的 分组都被交换到目的输出端，在那儿排队等待被发送到输出链路上。在这种模型 2 1 电子科技大学硕士学位论文：o b s 边缘节点数据包突发汇聚的研究与实现 下，并不需要调度算法。但该模型对于高速或多端口的路由器来说是很不实际的， 由于它要求开关内部交换速率为端1 3 速率的n 倍( n 为输入端口数) ，随着端口速 率的增加，实现困难增大，因此目前高性能路由器一般采用基于输入队列的交换 开关。 基于输入队列的交换模型由输入队列、交换阵列和仲裁器三部分组成，见图 3 1 。到达交换开关的报文首先在输入队列中排队，然后通过交换阵列的交换到达 输出端口。由于c r o s s b a r 无内部阻塞，因此路由器常选用c r o s s b a r 作为交换阵列。 基于输入队列的交换开关中c r o s s b a r 部交换速率等于交换开关端口速率。仲裁器 的作用是根据输入队列的状态，决定在某段时间内输入和输出端口间的匹配关系， 即c r o s s b a r 的内部拓扑结构。为提高c r o s s b a r 带宽利用率，交换模型一般采用定长 交换。数据在进入交换模型前被分解成定长的分组。c r o s s b a r 交换一个分组的时间 称为一个时间槽。 同闩同同! 。誊 同闩闩同l二 r 交换阵列 ： c ： 同闩同闩 r 图3 1 基于输入队列的交换开关结构 若输入端口只采用简单的f i f o ( f i r s t i n f i r s t o u t ) 队列机制，那么h o l ( h e a d o f l i n e ) 阻塞会降低c r o s s b a r 内部交换带宽的利用率。例如当分组到达服从独立同 分布的贝努里过程，n 趋近于无穷时，c r o s s b a r 的带宽利用率只有5 8 6 ，对于b u r s t 分组到达，利用率更低。采用v o q ( v i r t u a lo u t p u tq u e u e ) 技术可以使基于输入队 列的交换开关获得1 0 0 的利用率 2 6 1 。但下面两种阻塞会影响分组通过交换开关 的延时： 1 、输入端口阻塞。同一输入端口不同v o q 中的分组因竞争输入端e l 而产生的 阻塞。 2 2 电子科技大学硕士学位论文：o b s 边缘节点数据包突发汇聚的研究与实现 2 、输出端口阻塞。不同输入端1 3 的分组竞争同一输出端口而产生的阻塞。 为v o q 设置优先级和提高c r o s s b a r 的加速比( s p e e d u p ) 可以控制或减小上 述两种阻塞对分组延时的影响。然t j 面v o q 、优先级和加速比等策略的采用必须依 赖于具体的c r o s s b a r 仲裁算法。 3 1 3i s p 算法介绍 般来说，高效、公平的仲裁算法具有如下性质 1 、平均每次仲裁匹配的输入输出端口数目多 2 、分组通过交换开关的平均延时短 3 、v o q 头部分组等待时间有确定上限，分组通过交换开关延时的均方差小 4 、硬件实现简单，工作频率高 目前常见的仲裁算法主要有p i m ( p a r a l l e l i t e r a t i o nm a t c h i n g ) 、二维r r ( r o u n d r o b i n l 和i s l i p 等【2 8 】。其中i s l i p 算法已在c i s e og s r1 2 0 0 0 路由器中使用。这 些算法的特点是采用多次迭代方式增加输入输出端口的匹配数目，采用r o u n d r o b i n 方式保证公平性。上述算法也有明显不足。p i m 和i s l 口的每次迭代包括 r e q u e s t 、g r a n t 和a c c e p t 三个过程，二维r r 算法需要产生复杂的请求矩阵，因 此这些算法实现复杂。且在重负载情况下，算法的性能较差。 串行输入轮循算法 串行输入轮循算法( i n p u t s e r i a lp o l l i n g ，i s p ) 是一种采用定长交换和v o q 2 9 】 技术雕j c r o s s b a r 仲裁算法。i s p 算法以轮询的方式检查各输入端口的请求，并按 r o u n d r o b i n 的策略为其选择一个输出端口。由于各端口的轮询是串行的，因此i s p 算法不存在i s l i p 等算法中i n r o u n dr o b i n 指针同步而带来的性能下降问题。 i s p 主要针对定长的分组交换3 0 1 。设有n 个输入端口和m 个输出端口( 很多 情况下n = m ) ，每个输入端口的请求都有可能有m 种情况。把输入端口i 的请求 j 记做v o q ( i ，j ) 。其中i 属于n ，j 属于m 。交换的过程以时间槽为单位a 每 2 3 电子科技大学硕士学位论文：o b s 边缘节点数据包突发汇聚的研究与实现 个时间槽内需同时完成： 1 、调度器检查各输入端口v o q 的状态，每个输入端口根据轮循顺序选出 个请求。 2 、根据仲裁算法产生下一个时间槽对c r o s s b a r 的配置信息，并将该信息写 入c r o s s b a r ，完成对下一个时间槽的仲裁。 3 、输入端口通过c r o s s b a r 交换一个信元到输出端口。 i s p 算法采用了串行方式消解输入输出端口阻塞 1 、算法依次轮询各输入端口( 解决了输出端口竞争) 。 2 、按圆桶( r o u n dr o b i n ) 原则为输入端口匹配一个输出端口( 解决了输入 端口竞争) 。 端口阻塞的串行消解实现简单，又不存在r o u n dr o b i n 指针同步而带来的性 能下降问题，因此重负载时性能高。当n 较小时( 端口数目一般不大于3 2 ) ，i s p 算法不会成为交换开关的瓶颈。 3 2 变长串行输入轮循算法v i s p 3 2 1 边缘节点中数据排队的特点 输入边缘节点需要在组装突发包前对长度不等的数据包( 即加了g m p l s 标 签的i p 包) 进行数据排队。在本边缘节点设计中路由信息处理后有r a m 提供缓 存，对于突发汇聚来说输入队列有缓存提供排队，可采用基于输入队列的排队， 可以借鉴i s p 算法。 但是由于后续组装突发包的过程中需要把变长的数据包一次性写入，以方便 突发包的组装和长度计算。不能象i s p 算法一样分割数据包为定长分组，所以对 i s p 要进行一些改动。 2 4 一堑型垫奎堂堡主堂垡丝茎! 竺呈! 望丝蔓皇墼堡垒壅鏊鎏塞塑堡塞量壅翌 3 2 2v i s p 的提出 针对突发变长数据包调度的要求，本人提出了一种基于i s p - - - - 变长串行输入轮循算法( v a r i a b l ei n p u ts e r i a lp o l l i n g ，v i s p ) 。它是根据i s p 的 基本思想结合变长分类的要求修改而来的，可以满足变长数据包的交换。与i s p 的具体差异如下： l 、在调度器内部的输出控制器里增加针对每个输入端口的变模计数器，以便 根据数据包长准确控制c r o s s b a r 的开关时间。 2 、反馈的输出端口占用信息在i s p 中由微仲裁器输出，而在v i s p 中则由输 出控制器输出。v i s p 中输出控制器完全控制c r o s s b a r 的工作状态，能准确地说明 c r o s s b a r 的占用情况。 3 、把轮循顺序产生器输出的顺序信息的周期变为4 个c l k 周期长度。因为 v i s p 中端口占用信息的反馈要在输出控制器中产生，延时比i s p 大。把时序发生 器的周期改为4 个c l k 周期长度，可以保证时序正确。时序发生器的4 个c l k 周期 长度比变长数据包的长度小很多，对突发数据包的及时响应没有影响。 3 3 用v h d l 设计v i s p 3 3 1 基于v i s p 的数据排队框图 由于设计中需要完成流分类和基于v i s p 的数据排队。即根据g m p l s 标签对 突发包进行流分类。然后由v i s p 调度器进行数据排队。现将其框图示于图3 2 。 图中“虚1 到2 ”代表输入端口1 到输出端口2 的加上g m p l s 标签后的口队列。 在设计光突发交换边缘节点的时候，本地接入部分( 以太网) 设置了6 路输 入。所以在包流分类之前收到路由信息处理后的口包为6 路，经过碑包流分 类和数据排队后输出到突发包组装模块的数据共有4 路。设计中输入数据包速率 为6 2 5m h z ，输出速率为1 2 5m h z 。内部交换速率要快于输入端口的数据速率才 能保证不出现拥塞的情况。事实上，此输入端口最大流量为1 6b i t ) 6 路6 25 m m z = 6g b i t s ，输出端口最大流量为1 6b i t 4 路1 2 5m h z = 8g b i t s 。即输出 端口最大流量有剩余，出现拥塞几率较小。 2 5 电子科技大学硕士学位论文：o b s 边缘节点数据包突发汇聚的研究与实现 图3 - 2i p 包流分类和基于v i s p 的数据排队框图 3 3 2v i s p 调度器( 仲裁器) 内部框图 v i s p 调度器，是为了满足变长数据包的交换，由i s p 基本思想结合变长分类 的要求修改而来的。所以内部结构和i s p 基本一致。如图3 - 3 所示。 图3 - 3v i s p 调度器( 仲裁器) 内部框图 电子科技大学硕士学位论文：o b s 边缘节点数据包突发汇聚的研究与实现 v i s p 调度器主要由时序发生器( 状态机) 、当前请求产生器、r r 指针产生器、 微仲裁嚣和输出控制器组成。框图中一些关键信息如下： 古虚队列请求 即v o q ( v i r t u a lo u t p u tq u e u e ) ，表示虚队列排好队之后提出的请求。请 求是根据收到的p 包相应的g m p l s 标签中目的节点、长度和优先级信息而来的。 在设计中有6 个输入端口和4 个输出端口，每个输入端口的请求都有可能有4 种 情况。输入端口i 到输出端口j 的请求记做v o q ( i ，j ) 。其中1 i 6 ，1 j 4 4 。虚队列i 请求包含输入端口i 到4 个输出端口的所有请求。 - k 时序信息 由时序产生器产生的，以4 c l k 为周期的时序信息。包含当前应轮循的输入 端口号信息，即此刻应该处理那个虚队列请求。 这样做的理论依据和i s p 算法类似：通过轮循各输入端口的请求，解决了输 入端口的竞争。 - k 端口占用信息 由输出控制器反馈的端口占用信息包含了此刻4 个输出端口的使用情况。由 于此信息完全反映输出端口的使用情况，所以由输出控制器内部状态机控制。当 前请求产生器结合端口占用信息可以准确的选择出此刻应该处理的虚队列请求。 - k 选中的请求 是当前请求产生器根据时序信息、端口占用信息以及输入端口的虚队列请求 信号产生的信号。它按照时序信息中该轮循端口的信息选择虚队列请求，公平地 相应虚队列请求。然后把请求中对正在使用的端曰的请求过滤掉，输出的就是对 目前未使用的端口的请求。 优先级信息 根据时序信息，由r o u n dr o b i n 指针产生器产生的，反映当前虚队列请求中 2 7 电子科技大学硕士学位论文：o b s 边缘节点数据包突发汇聚的研究与实现 输出端口占用优先级的信息。目的是在几个v o q 竞争同一个输出端口的情况下， 根据当前输出端口优先级，作出仲裁，以避免不必要的竞争阻塞。优先级是要随 读取次数改变的，以保证轮循的公平性。 理论依据和i s p 类似：按圆桶( r o u n dr o b i n ) 原则为输入端口匹配一个输出 端口，这样就解决了输入端口竞争。 例如：时序信息是5 ，表示当前应该轮循虚队列请求5 。r r 指针产生器根据 信息5 查找虚队列请求5 所对应的4 个输出端口的优先级信息，并输出这个信息。 仲裁结果 仲裁结果是微仲裁器根据当前选中的请求和优先级信息，经过一些编码运算 产生的队输出控制器的配置信息。即作出裁定：当前应该打通具体输入端口i 到 输出端口j 的通道。并告知输出控制器，以作出相应的操作。 女对c r o s s b a r 配置信息 此信息是输出控制器根据仲裁结果及输出端口的打通情况信息作出的最后判 定。信息包含输入端口信息和输出端口信息。如果输入端口信息为3 ，输出端口4 的电平为高，就表示此刻c r o s s b a r 的输入端口3 和输出端口4 需要连通。以保证 数据通过。 3 3 3 用v h d l 为v i s p 调度器中的模块建模 突发汇聚要在硬件上实现，我们选择了使用f p g a 。那么在v i s p 调度器模块 框图( 图3 ，3 ) 中所示各个模块要用硬件描述语言建模。要使其符合硬件实现的 特征。我们使用v h d l 语言实现v i s p 调度器。 v h d l 的英文全名是v e r y - h i g h s p e e di n t e g r a t e dc i r c u i th a r d w a r ed e s c r i p t i o n l a n g u a g e 。1 9 8 7 年底，v h d l 被i e e e 和美国国防部确认为标准硬件描述语言。 v h d l 主要用于描述数字系统的结构，行为，功能和接口。含有许多具有硬件特 征的语句。v h d l 的语言形式和描述风格与句法是十分类似于一般的计算机高级 语言。 2 8 电子科技大学硕士学位论文：o b s 边缘节点数据包突发汇聚的研究与实现 v h d l 具有很强的行为描述能力，从而决定了他成为系统设计领域最佳 的硬件描述语言。强大的行为描述能力是避开具体的器件结构，从逻辑行为上描 述和设计大规模电子系统的重要保证。v h d l 语句的行为描述能力和程序结构决 定了他具有支持大规模设计的分解和已有设计的再利用功能。 七v h d l 丰富的仿真语句和库函数，使得在任何大系统的设计早期就能查 验设计系统的功能可行性，随时可对设计进行仿真模拟。对于用v h d l 完成的一 个确定的设计，可以利用e d a 工具进行逻辑综合和优化，并自动的把v h d l 描 述设计转变成门级网表。 v h d l 对设计的描述具有相对独立性，设计者可以不懂硬件的结构，也 不必管理最终设计实现的目标器件是什么，而进行独立的设计。 3 3 3 i 时序发生器 以4 倍全局时钟g c l k 为周期产生当前应轮循的端口号。内部使用3 个计数器， 一个计数器产生周期为4 个g c l k 的节拍。还有2 个模n ( n 为输入端口数) 计数 器t i m e r l 和t i m e r 2 ( 初始值均为o ) 主要生成轮循端口号，t i m e r 2 表示每 次调度中迭代的次数，每拍加1 ，t i m e r l 表示当前迭代应首先轮询的端口。当 t i m e r 2 等于n 一1 时，t i m e r l 加1 。t i m e r ! + t i m e r 2 值为当前应轮询的端口 号，n 为输入端口数目( 本设计中n 为6 ) 。 v h d l 建模：主要用3 个计数器级联实现此功能模块，输出时序信息。波形 如图3 - 4 ：其中g c l k 表示全局时钟，p o r t 是当前应轮询的端口号。 3 3 3 2r r 指针产生器 图3 _ 4r r 时序发生器时序仿真波形图 r r 指针产生器包括n 个l 0 9 2m ( m 为输出端口数) 位的r r 指针寄存器及 一个n 选1 开关。 电子科技大学硕士学位论文：o b s 边缘节点数据包突发汇聚的研究与实现 r r 寄存器存储输出端1 3 的优先级信息。存储的优先级在每一次读取后要 改变，以保证轮循的公平性。 n 选1 开关根据当前轮循端口信息读出相应的r r 指针寄存器，将其送往 微仲裁器。 v h d l 建模：用c a s e 语句来实现多路选择输出，用寄存器存储优先级信息。 时序仿真波形如图3 5 ：o r d e r 表示输入的时序信息，表示当前该轮循的端口号。 c l k 为内部计数信号，以4 x 全局时钟为周期，上升沿采样o r d e r 信号，输出对应 的优先级信息p r i o r ( 2 b i t 宽，可以表示4 个端1 3 ) ，如为3 就是输出端口3 优先。 3 3 3 3 当前请求产生器 图3 5r r 指针产生器时序仿真波形图 当前请求产生器是根据时序信息、端口占用信息以及输入端口的虚队列请求 信号产生当前的请求信号。当前请求产生器主要由输出端口状态寄存器，n 选l 开关组成。如图3 - 6 所示： 图3 - 6 当前请求产生器内部结构 3 0 口占用信息 电子科技大学硕士学位论文：o b s 边缘节点数据包突发汇聚的研究与实现 v h d l 建模：n 选一选择器用i f 语句实现。输出端口状态寄存器用内部寄存 器实现。输出的与门可由赋值语句实现。如下： 选择请求 - n 选一后的请求a n d ( n o t 输出端口状态寄存器输出) ； 3 3 3 4 微仲裁器 微仲裁器根据当前请求产生器选中的请求和r r 指针产生器输出的优先级信 息产生仲裁结果。 器件规模复杂度和关键路径是硬件电路设计的两个关键参数。器件规模复杂 度用面积耗费，即用等效的或非门和与非门的数目来衡量，关键路径时延是指从 输入到输出的最大电路时延。微仲裁器是调度器中的关键路径，决定调度器的工作 频率。所以需要选择一个合适的可编程优先级编码器。温度计编码型p p e 方案是 一个很好的选择。 选择用温度计编码型p p e 来实现微仲裁器。因为它对最高优先级做特殊的编 码，并用此预处理输入请求，巧妙地消除了p p e 的优先级可编程性，不影响输出， 并且硬件实现简单。当n 较大时，温度计编码型p p e 在时延和面积耗费上都不大 3 3 1 。 温度计编码型p p e 在实现时要采用“温度计编码”的编码方案对最高优先级 p 编码。其真值表如表3 - 1 ： 表3 1n = 4 ( w = 2 ) 的温度计编码真值表 输入x输出y 0 0 0 l 1 0 1 l 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 l 微仲裁器由温度计编码型p p e 实现，内部框图如图3 - 7 所示。 3 1 电子科技大学硕士学位论文：o b s 边缘节点数据包突发汇聚的研究与实现 注：空心箭头的数据宽度为l o g ：( 曲b i t ，虚线箭头数据宽度为1b i t 宽，实线箭头的数据 宽度为1 7b i t 。设计中月= 4 图3 7 温度计编码型p p e ( 微仲裁器) 内部框图 v h d l 建模：优先级编码器和温度计编码器可以用c a s e 语句实现。最后映射 到器件上是查找表的形式实现。 3 , 3 3 5 输出控制器 输出控制器根据仲裁结果控制c r o s s b a r 的打通和关闭。内部有计数器，对打 通的时间进行控制。输出控制器还锁存当前匹配端口号和匹配结果，并产生对 c r o s s b a r 的配置信号。通知c r o s s b a r 进行内部拓扑的切换。同时反馈端口占用信 息给当前请求产生器，显示现在端口占用的情况。 v h d l 建模：使用同步状态机配合计数器计时，用寄存器寄存当前c r o s s b a r 的 配置信息。 对于v i s p 的v h d l 代码在仿真软件m o d e l s i m 5 7 中仿真结果如下： 3 2 电子科技大学硕士学位论文：o b s 边缘节点数据包突发汇聚的研究与实现 图3 - 8 温度计编码型p p e ( 微仲裁器) 内部框图 图3 - 8 示出了两个2 个虚队列在v