（通信与信息系统专业论文）通信系统中重排序问题研究.pdf

摘要 们古jj 爱 随着网络技术在全球范围突飞猛进的发展，在给传统电信网络带来巨大冲击的 同时，也为网络技术的进一步发展和演进提供了新的机遇。从当前信息技术的发 展潮流来看，建设高速大容量的宽带综合业务网己成为现代信息技术发展的必然 趋势。为了适应这种需求，通信的两大组成部分一传输与交换，都在不断地发展 与变革。发展的触须接触到了两个方面，一者是电域的高速交换系统，一者是光 交换系统。 乱序重组的具体定义为将时间顺序被打乱的一系列信息通过缓存、比较和交 换的方式恢复其应有顺序。乱序重组是一个很宽泛的概念，交换系统中的乱序重 组问题伴随着分组交换的概念出现而受到重视，在分组交换系统中，分组乱序几 乎无处不在。研究者通过缓存，流控，确认和重传等等方法来解决乱序问题以及 由乱序带来的种种派生问题。 多平面交换和o b s 光突发交换，分别作为两个领域中具有代表性的技术，受 到广泛的关注。本文以作者在这两个领域的研究和工作为背景，阐述了乱序重组 问题在两个领域中的重要性，分析了各自的产生和特点，并针对这两个具体问题 提出了相应的解决方案：寄存器链表排序算法和预分配重组算法。前者通过实际 应用验证了其正确性和有效性，后者通过仿真证明了其优势。并且为两个领域中 的乱序重组问题提出了下一步的研究方向。 以文中所述简化板块为核心的o b s 实验系统已经通过国家8 6 3 项目验收，具 有相当的参考价值。 关键词：乱序重组，寄存器链表排序，预分配重组 a b s t r a c t a b s t r a c t t h ed e f i n i t i o no fr e o r d e ri st o r e g a i nt h e c o r r e c ts e q u e n c eo fas e r i e so f i n f o r m a t i o n ，w h i c hi ss h u f f l e do nt h ea s p e c to ft i m e ，b ym e a n so fb u f f e r i n g ，c o m p a r i n g ， e x c h a n g i n g ，e t c r e o r d e ri s aw i d ec o n c e p t a st h ep a c k e ts w i t c h i n gt e c h n o l o g y e m e r g e d ，r e o r d e r i n gi ns w i t c h i n gs y s t e mw a se v a l u a t e da sa ne s s e n c ei nc o m m u n i c a t i o n s y s t e m ，s i n c et h ed i s o r d e rp h e n o m e n o ni sa l m o s te v e r y w h e r e i np a c k e ts w i t c h i n g s y s t e m r e s e a r c h e r sp r o p o s e db u f f e r i n g ，f l o wc o n t r o l ，a c k n o w l e d g e m e n t a n d r e - t r a n s m i s s i o na sm e t h o d st os o n ed i s o r d e rp r o b l e ma n dp r o b l e m si n t r o d u c e db y d i s o r d e r a sc o m p u t e rn e t w o r ke x h i b i t st r e m e n d o u sp r o g r e s s e st h e s ey e a r s ，i tp l a c e sh u g e i m p a c to nt r a d i t i o n a lt e l e c o m m u n i c a t i o ni n d u s t r y ，b u ta l s ob r i n g sn e wo p p o r t u n i t yf o r e v o l u t i o no fn e t w o r kt e c h n o l o g y c o n s t r u c t i o no fh i g hs p e e d ，l a r g ev o l u m e ，a n d b r o a d b a n di n t e g r a t e db u s i n e s sn e t w o r ki sat r e n di nd e v e l o p i n gp r o c e s so fm o d e mi t t h ed e v e l o p m e n tr e a c h e st w of i e l d s ，o n ei sh i g hs p e e de l e c t r o n i cs w i t c h i n gs y s t e m ，o n e i so p t i c a ls w i t c h i n gt e c h n o l o g y p a r a l l e lp l a n es w i t c h i n ga n do p t i c a lb u r s ts w i t c h i n gr e c e i v e dw i d ec o n c e ma s l e a d i n gt e c h n o l o g i e si nt w or e s p e c t i v ef i e l d s t h i st h e s i si sb a s e do na u t h o r sr e s e a r c h a n dd e v e l o p m e n ti nt h e s et w of i e l d s t h ei m p o r t a n c eo fr e o r d e ri nt h e s et w of i e l d si s d e s c r i b e d c a u s e sa n da t t r i b u t e so ft w op r o b l e m sa r ea n a l y z e d s o l u t i o n s ，c a c h e dl i n k l i s ta n dp r e e m p t i v ea l l o c a t i o nr e o r d e r i n ga r ep r o p o s e dr e s p e c t i v e l y t h ef o r m e ro n ei s p r o v e df e a s i b l ea n de f f e c t i v eb yp r a c t i c a li m p l e m e n t a t i o n ，a n da d v a n t a g eo ft h el a t t e r o n ei sv e r i f i e db ys i m u l a t i o n a tl a s t ，f u t u r er e s e a r c ht o p i c so ft w op r o b l e m sa r ep r o b e d k e y w o r d s ：r e o r d e r , c a c h e dl i n kl i s ta l g o r i t h o m ，p r e e m p t i v ea l l o c a t i o na l g o r i t h o m i i 主要符号表 缩略语： d w d m o b s o c s o x c o a d m o p s f d l b h p g m p l s o e e o v h d l f p g a d s p l v d s s e r d e s f p s c p a r 主要符号表 d e n s i t yw a v e l e n g t hd i v i s i o nm u l t i p l e x i n g o p t i c a lb u r s ts w i t c h i n g o p t i c a lc i r c u i ts w i t c h i n g o p t i c a lc r o s sc o n n e c t i o n o p t i c a la d d d r o pm u l t i p l e x i n g ， o p t i c a lp a c k e ts w i t c h i n g f i b e rd e l a yl i n e b u r s th e a d e rp a c k e t g e n e r a l i z e d m u l t i p l ep r o t o c o l l a b e l s w i t c h i n g o p t i c a lt oe l e c t r o n i c e l e c t r o n i ct oo p t i c a l v e r y h i g hs p e e di n t e g r a t e d c i r c u i t s h a r d w a r ed e s c r i p t i o nl a n g u a g e f i e l dp r o g r a m m a b l eg a t ea r r a y d i g i t a ls i g n a lp r o c e s s i n g l o w v o l t a g ed i f f e r e n t i a ls i g n a l i n g s e r i a l i z e r d e s e r i a l i z e r f i e l dp r o g r a m m a b l es y s t e m - - o n - a - - c h i p p r e e m p t i v ea l l o c a t i o nr e o d e r v i 密集波分复用 光突发交换 光路交换 光交叉连接 光分插复用 光分组交换 光纤延迟线 突发控制分组 广义多协议标签交换 光电电光转换 高速集成电路硬件描述语 言 现场可编程门阵列 数字信号处理器 低电压差分信号 串行器解串器 现场可编程单芯片系统 预分配重组 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名：兰堕竺日期：切。1 f 年6 月步e t 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：塑垒 第一章绪论 1 1 引言 第一章绪论 路由器作为划分和连接子网的关键设备，近十年来随着n t e r n e t 规模和应用服 务的增长，发生了许多革命性的变化，影响到从组网结构到路由器体系结构本身 的方方面面。在8 0 年代中后期，为了减小同一物理网络内的竞争冲突提高网络容 量，开始使用“网桥”设备。但随着网络规模的扩展和广播流量的增加，以及网 桥对广播流量的控制能力有限，这种方式己不能满足网络的扩展需求。为了解决 扩展问题，一些公司开始开发“路由器”。不同于网桥( 第二层设备) 的是路由器在 第三层划分子网，最初的设计遵守“8 0 2 0 规则”一即8 0 的本地流量，2 0 的 网间流量，通常一个子网占用路由器的一个端口。但随着个人主机处理能力的提 高和应用需求的快速发展，如多媒体、分布式计算等，用户需求更高的带宽，”8 0 2 0 规则”变成了“5 0 5 0 规则”，本地流量和网间流量各占5 0 ，为了提高传输速率 又再次引入了第二层的交换技术，子网之间的连接方式发展成了“路由器+ 交换机” 的模式，以后本文中统称为交换机。 随着i p 业务在全球范围突飞猛进的发展，在给传统电信业务带来巨大冲击的 同时，也为电信网络的发展提供了新的机遇。从当前信息技术的发展潮流来看， 建设高速大容量的宽带综合业务网己成为现代信息技术发展的必然趋势。为了适 应这种需求，通信的两大组成部分一传输与交换，都在不断地发展与变革。 发展的触须接触到了两个方面，一者是电域的高速交换系统，一者是光交换系 统。 1 1 1 电域高速交换 网络传输速率和互连用户数的快速增长，作为基础网络互连设备的交换机在体 系结构上发生了巨大的变化。传统方法是在一个单总线的计算机系统上通过软件 方式实现，之后经历了单总线多处理器、单总线多机系统等体系结构，发展为目 前的基于背板互连的多机系统结构即交换式交换机。但该结构是一个由报文缓冲、 电子科技大学硕士学位论文 转发引擎、交换核心等主要单元组成的复杂系统，系统的总体性能并不是几个单 元理论性能的简单组合。并且每个单元的性能除受制于其内部结构外，还与其前 级单元的输出形式相关，而且其输出形式又将对后级单元造成影响。另外，同样 的结构在不同的业务流量下性能表现也不同。 交换系统线速和缓存速度的矛盾，引出了多平面交换技术。 1 1 2 光交换系统 早期的光通信系统主要是针对长距离、点对点之间的传输。随着w d m 技术的 出现，极大的利用了光纤的波长资源，扩大了点对点连接的传输容量，开创了光 层网络的新时代。在这些网络中，在光纤中传输的波长称为光通道，利用这些光 通道就能够建立起光传输网络。当然，这些网络功能的实现，需要性能优良的光 网络单元，也就是需要光器件的支持，包括光交换矩阵。光纤通信不仅在主干网 络( b a c k b o n en e t w o r k s ) 和城域网f m a m 中得到广泛的应用，而且慢慢渗透到接入网 络( a c c e s sn e t w o r k s ) 和企业局域网f l 气n s l 中。 密集波分复用( d w d m ) 的出现，使得“光纤耗尽”的问题得到了有效解决。 近年来，d w d m 技术已经从长途干线系统渗透到城域网。可以预见，建立一个光 因特网的目标并不遥远。由于复用的波长信道数急剧增加，光纤的传输容量以指 数形式增长。相应地，光传送网的路由和交换则成了整个网络的瓶颈。在过去的 2 0 多年中，每比特的传输成本下降了近一万倍，而交换成本仅下降了3 倍左右。 简言之，传输容量通过d w d m 技术相对容易扩展，而交换路由则仍多采用光一 电一光方式，两者之间的矛盾越来越突出。解决这个问题的途径是建立一个具有 强大功能的光层，具有全光交换功能如光交叉连接( o p t i c a lc r o s sc o n n e c t i o n ， o x c ) 和光分插复用( o p t i c a l a d d d r o pm u l t i p l e x i n g ，o a d m ) i 2 4 等，能进行透明 传输( 比如光突发交换o b s ) 并具有灵活的可扩展能力【1 4 】【1 5 】【16 1 。因此，全光交换 设备是光传送网络的核心设备。 1 1 3 乱序重组问题 乱序重组的具体定义为将时间顺序被打乱的一系列信息通过缓存、比较和交 换的方式恢复其应有顺序。乱序重组是一个很宽泛的概念，交换系统中的乱序重 组问题伴随着分组交换的概念出现而受到重视，因为在分组交换系统中，分组乱 2 第一章绪论 序几乎无处不在。研究者通过缓存，流控，确认和重传等等方法来解决乱序问题 以及由乱序带来的种种派生问题。 而在高速交换领域和光交换领域，乱序重组问题以不同的形式出现，但是都 对系统功能实现和系统性能优劣起着极大作用。本文根据作者在这两个领域的研 究经验，对乱序重组问题的产生，特性和解决方案进行了详尽的描述。 1 2 本文主要内容及安排 本文围绕通信系统中的乱序和重组问题，从o b s 实验系统中命令解析单元和 多平面交换系统的出端口适配器两个角度，研究了该问题的成因，特征和解决方 法，并提出了寄存器链表缓存结构这一创新结构和预分配重组算法这一创新算法。 本文的安排如下： 第一章绪论通过简洁的叙述，引出了本文的三个重要技术背景：多平面交换， o b s 交换和乱序重组问题。 第二章对o b s 技术背景和原理进行了简要的介绍，说明了实验系统的基本情 况，分析了乱序问题的成因、特点和解决方式，并着重描述了硬件实现过程。 第三章简介了多平面交换技术，对多平面交换中的乱序问题进行了深入的分 析，提出了预分配重组算法，并比较了该算法和其他两种重组算法的仿真结果。 第四章总结全文。 电子科技大学硕士学位论文 第二章o b s 实验系统中的重排序问题 2 1o b s 技术背景 2 1 1o b s 技术产生背景 随着网络技术的拓展深入，近年来网络中的业务数据量呈爆炸式增长，网络 带宽的需求越来越大，波分复用( w d m ，w a v e l e n g t hd i v i s i o nm u l t i p l e x i n g ) 被广 泛采用。密集波分复用( d w d m ) 技术更为通信网络提供了巨大的传输容量，逐步 成为主流传输技术。 但是当前w d m 仅仅是工作于骨干网的实现点到点连接的技术，i p 业务仍然 是采用i po v e ra t mo v e rs d ho v e rw d m 的多层网络结构方式进行。这种方式层 次功能重叠，带来的额外开销巨大，而且在网络中间节点的处理需要进行o e o 的 转换，由于电子瓶颈的存在，网络速度受限。因此有必要减少层次结构，而i po v e r w d m 技术有望满足这一需求。 i po v c rw d m 光网络有三种方案：光路交换o c s ( o p t i c a lc i r c u i ts w i t c h i n g ) ， 光分组交换o p s ( o p t i c a lp a c k e ts w i t c h i n g ) ，光突发交换o b s ( o p t i c a lb u r s t s w i t c h i n g ) 。其中光路交换也就是光的波长路由交换方案，本质上是一种光层的 电路交换，其处理颗粒和带宽分配策略并不适合承载突发性的i p 业务，不是理想 的承载方案。光分组交换直接在光域进行层间适配，丢弃了电适配层，简化了网 络的控制，提高了操作效率，真正实现了i p 层与光层的紧密耦合，是理想的承载 方案。但是由于缺乏高速光逻辑器件、光缓冲存储器件等，该方案还处于理论研 究阶段。 基于这种背景，作为一种折中方案的o b s 技术脱颖而出，o b s 技术在支持 分组业务的性能上高于o c s ，而实现难度( 尤其是对光器件技术的要求) 低于o p s 。 作为一种很有发展潜力的交换模式，o b s 得到了广泛的关注。 第二章o b s 交换系统中的重排序问题 2 1 2o b s 的基本原理 图2 10 b s 网络示意图 如图2 - 1 所示o b s 网络由三部分组成：处于网络边缘的边缘交换机、位于网 络中心的光核心交换机以及波分复用( w d m ) 的链路。分组在网络入口处被组装 成突发数据，经过光核心交换机的交换，在网络的出口处被分解成分组，并被转 发到下一跳( h o p ：即节点) 。边缘交换机提供突发分组的组装和拆分功能，并且 提供了各种网络接口( 如：g i g a b i t e t h e m e t ，p a c k e t o v e r s o n e t ( p o s ) ，i p a t m 等) p ，使之可以和其他协议类型的网络互联。光核心交换机主要由光交换矩阵 ( o p t i c a ls w i t c h i n gm a t r i x ) 和交换控制单元( s w i t c hc o n t r o lu n i t ) 组成。 o b s 网络中的基本交换单位是突发分组( b u r s t ) 。突发分组是由一些i p 包组成 的超长数据包，通常为1 0 k b 。组成突发的i p 分组具有相同的出口边缘交换机地 址，以及相同的服务质量( o o s ) 要求。每一个b u r s t 均有与其一一对应的b h p ，b h p 中包含所有必要的控制信息，如突发长度、偏移时间、波长信息和路由信息，b h p 的具体帧格式在实际应用中可以根据需要灵活变动。 b h p 在物理信道和时间上与b u r s t 分离，即在物理信道上一般为同一光纤中不 同波长，在时间上控制分组提前于突发数据分组一段时间，该时间即为偏移时间 ( o f f s e tt i m e ) 。通过核心节点时b l i p 被转换到电域上进行相应处理，o b s 主干 5 电子科技大学硕士学位论文 网的每一跳的交换控制单元根据b h p 携带的信息来配置光交换矩阵，以便b u r s t 直接通过光域已经配置好的路径。b u r s t 和b h p 独立传输和交换不仅有助于对 b h p 进行电处理，降低光核心交换机光电转换的需求，而且可以提供入口到出口 的透明光通路来传输b u r s t 。 2 1 3o b s 技术的优点 通过上一节对o b s 技术原理的分析可知，o b s 的主要优点为： 从不同源端到不同宿端的突发分组可以利用统计复用的方式，有效地利用 链路上相同波长的带宽，带宽使用效率较高。 b h p 和b d p ( 也就是b u r s t ) 的分离，有效降低了核心节点的复杂度和对 光器件的要求。 核心节点可以不需要缓存，降低了系统的同步要求。 单向资源预留机制缩短了等待时延 交换容量大，可以达到t b i t s 级的交换容量。 2 1 4o b s 研究动态 自1 9 9 7 年c q i a o 提出o b s 理论以来【，国外关于o b s 的研究方兴未艾。典 型的研究包括：美国纽约州立大学b u f f a l o 分校的q i a o 等对o b s 经过比较深入的 研究，提出了一种j e t ( j u s te n o u g ht i m e ) 信令协议【”】【”1 ，并研究了基于该协议 的核心节点的结构和性能。该协议能在w d m 层实现基本的区分服务，支持一 定的服务质量( 仅以突发丢包率为q o s 参数) 。该小组还开展了o b s 交换中的组 播和m p l s ( 多协议标签交换) 在o b s 交换中的运用研究，提出了m p l s 与o b s 相结合的方案标签光突发交换( l o b s ) 。为了降低复杂性，y w e i 等建议采用 j i t ( j u s ti nt i m e ) 2 1 信令协议，j i t 协议提供尽力而为的服务，不支持w d m 层的 q o s 。英国伦敦大学学院( u c l ) 的p b a y v e l 等人提出了一种波长路由光突发交 换( w r o b s ) 方案，并对其性能进行了研究，该方案以波长路由为基础，更接近 电路交换的概念，可以提供有服务质量( q o s ) 保证，但网络的灵活性和带宽利用 率低，而且虽然原理上可以以波长为标签实现m p l s ，但由于涉及到对波长的操作， 第二章o b s 交换系统中的重排序问题 一止匕n 厅p tq 操作难i jj 生扛硼【3 】r 酊象丰结棵睿由小、白钉y ；m 1 1 3 1 竺 研容了n 一。卜- j 俐u i i u b、-o o 络的控制结构和数据信道调度算法。从事这方面的研究还有美国德克萨斯大学、 伊利诺斯州技术学院、意大利的罗马大学等。国内一些大学和研究机构，如北京 邮电大学，上海交大近年来也开展了相关预研工作。目前的研究主要课题集中在： 资源预约方案，冲突处理，仅以突发丢包率为参数的o b s 层的o o s 支持【2 5 】，边缘 交换机的突发会聚机制及o f f s e t t i m e 管理、网络核心节点交换结构和控制管理、控 n 数据信道的调度算法等。 o b s 网络中，数据突发与信令( 控制分组) 是分离的。不仅采用不同的信道， 而且时间上也是分离的，源端先发送b h p ，然后间隔一段时间后，发送b u r s t ，这 段时间称为偏移时间( o f f s e tt i m e ) 。目前提出的各种预约方案最主要的区别在于 如何判断突发的结束，以及如何确定某个新突发占用相应资源( 通常情况下应包 括信道上的波长资源和交换结构中的缓存资源) 的持续期间【1 8 。 图2 2 给出了几种预约方梨。”，以及相应的信令流程示意图。图中示意了突发 经过o b s 交换机的情况。每个突发发送前，先在一个独立的信道中通过控制分组 发送一个s e t u p 消息；在某些方案中还需要在突发结束时发送一个r e l e a s e 消 息。下面分别描述这几种方案： 方案1 ：e x p l i c i ts e t u pa n de x p l i c i tr e l e a s e 。当s e t u p 消息到达时，立刻对交换 模块进行相应的配置，包括对交叉矩阵的设置以及对输出波长的预约。这一配置 直到收到r e l e a s e 消息时释放。 方案2 ：e x p l i c i ts e t u pa n de s t i m a t e dr e l e a s e 。s e t u p 消息中要携带突发的持续 时间信息。与方案1 不同的是，方案2 不需要r e l e a s e 消息来标志突发的结束。 突发的结束根据s e t u p 消息的到达时刻与突发的持续时间来估计。 7 电子科技大学硕士学位论文 方案3 ：e s t i m a t e ds e t u pa n de x p l i c i tr e l e a s e 。该方案与方案2 刚好相反。估计 的是突发的开始时刻，而突发的结束用r e l e a s e 消息来标志。 图2 2 几种信令方案的示意图 方案4 ：e s t i m a t e ds e t u pa n de s t i m a t e dr e l e a s e 。突发的开始和结束时刻都根据 s e t u p 消息中的信息来估计。 2 2 0 b s 实验系统 核心节点控制系统作为o b s 实验系统的重要组成部分，与整个系统关联密切 为此有必要在讨论核心节点命令解析器队列之前先对o b s 实验系统作出介绍在 本节中将分别介绍o b s 系统的结构和工作流程。【1 9 】 第二章o b s 交换系统中的重排序问题 2 _ 2 1o b s 实验系统框图与说明 一、d w 光纤信道 l v d s 控制电缆叶以太网线 十单波长数据苎遵蔓一二二二e 二二控制信道k - 困 核心节点 图2 30 b s 实验系统框图 如图2 - 3 所示，本o b s 实验系统由边缘节点和核心节点两部分以及连接两部 分的w d m 链路组成。以下分别简单阐述边缘节点、核心节点的结构与功能。 3 7 1 3 8 】 本系统中有四个边缘节点e 0 到e 3 ，边缘节点通过以太网口与担任数据源的台 式计算机相连接，通过9 波长的w d m 光纤与核心节点相连接。边缘节点主要功 能是：进行外部数据的汇聚、排队，b u r s t 、b h p 的产生、b h p 的接收解析、b u r s t 的还原。位于网络发送端的边缘节点将数据源产生的数据包汇聚成b u s r t ，并对每 一个b u r s t 生成b b p 。然后经过e o 转换通过w d m 链路发送到核心节点。 o b s 中的核心节点主要由光交换阵列和光交换结构模块两部分构成。核心节 点的主要功能为：根据b h p 携带的控制信息和节点保存的资源状态信息对b t i p 进 行调度，然后修改并转发b h p 到下一跳边缘节点；根据调度的结果控制光开关在精 确的时间合理地动作，达到b u r s t 的透明传输。 光交换结构由8 个4 4 的交换模块以及光缓存f d l 2 1 】【2 2 】( 图中未画出) 组成； 在交换控制模块提供的配置信息控制下，这些部件协调工作，共同为数据提供透 明的通道。 电子科技大学硕士学位论文 w d m 链路：输入和输出的w d m 光纤均有4 条，每条光纤上复用9 个波长： 包括个用于b h p 传输的控制波长沁和8 个用于突发数据包传送的数据波长h ， 到h 8 。 输入的w d m 光纤在进入核心节点时通过分波器将9 个波长分开，九c 连接到 核心节点的光控制模块，而数据波长连接到核心节点的光交换矩阵的入端口，来 自边缘节点e i 的数据波长h i 被连接到第j 个4 x 4 的交换模块的第i 个入端口。 输出的w d m 光纤由通过核心节点的9 个波长通过合波器耦合而成。 2 2 2o b s 实验系统工作流程 o b s 实验系统的工作流程如下： a ) b l i p 汇聚与排队：i p 包发送到边缘节点时，边缘节点需要将发往同一目的节 点( 如果支持q o s ，还需要是同一优先级) 的i p 包汇聚为b u r s t 。在指定时间 内发往同一目的节点的数据尚未达到b u r s t 的最小长度之前( 即数据不足以汇 聚成一个b u r s t ) ，先到达的数据将缓存在边缘节点的相应等待队列中。1 2 3 1 1 2 6 】【2 7 1 b ) b h p 与b u r s t 的产生：直到超过等待时间或者当汇聚起来的i p 包达到b u r s t 的 要求长度为止，此时产生b h p 。将汇聚成的b u r s t 信息( 含b u r s t 长度、o f f s e t t i m e 、目的端口号、波长等) 封装到对应b h p 中，然后将b h p 通过光电转换 模块由光纤控制信道沁发往与该边缘节点相连的核心节点。b l i p 发出o f f s e t t i m e 时间后，将汇聚的b u r s t 通过光电转换模块由光纤数据信道上的指定波长 发往核心节点。 c ) b h p 的调度：在核心节点转发数据分组前将收到先期到达的控制分组b h p ， 交换控制模块根据b h p 携带的信息( 到达时间、持续时间即突发长度、端口 和波长信息、优先级) ，查找资源表，按照某种调度算法进行b h p 调度，生 成配置命令，使与该b h p 对应的b u s r t 透明通过核心节点。 d ) b h p 的转发：调度完成后，核心节点还需要修改b h p 的o f f s e tt i m e 字段( 即 扣除掉b h p 在本系统的处理时间) ，然后通过控制信道沁转发到下一跳的核 心节点或者边缘节点。 e ) b h p 的接收解析和b u r s t 的还原：当边缘节点收到由核心节点发向自己的b h p 时，经过光电转换模块对b h p 进行解析，获取对应的o f f s e t t i m e 。等待o f f s e t t i m e 1 0 第二章o b s 交换系统中的重排序问题 时间后，由光电转换模块接收b u n t 数据校验正确，则对b u r s t 进行解包 重新恢复为有效的i p 报文分组分发到外部i p 网络。 2 2 3 光交换矩阵简介 在实验系统中使用的光交换矩阵是l y n xp h o t o n i cn e t w o r k s 公司设计的 p a c k e t 2 4 x 4 光通信交换系统。该系统提供两个独立的4 x 4 光交换端口，入端口 和出端口可以两两连接。实时应用时使用并行l v d s 电缆作为控制接口。该接口 包括如下三个入信号：命令字c w ( 1 6 b i t ) 、加载命令l o a d ( 1 b i t ) 、配置命令 c o n f i g ( 1 b i t ) ；同时还有三个出信号：加载确认l o a da c k ( 1 b i t ) 、配置确认 c o n f ! ga c k ( 1 b i t ) 、命令字错误p e ( 1 b i t ) 。 光交换矩阵接收的c w 格式如表2 - 1 所示，其中属于同一4 x 4 的4 组输入不 能重复。 m s b2 n 6 4 x 41 “4 x 4l s b 1 5 1 41 3 1 21 1 1 09 87 65 43 21 o s e l e c ts e l e c ts e l e c ts e l e c ts e l e c ts e l e c ts e l e c ts e l e c t i n p u tf o ri n p u tf o ri n p u tf o ri n p u tf o ri n p u tf o ri n p u tf o ri n p u tf o ri n p u tf o r o u t p u t 4o u t p u t3o u t p u t 2o u t p u t lo u t p u t 4o u t p u t3o u t p u t 2o u t p u t l 表2 一l 光交换矩阵c w 格式 光交换矩阵工作的简单流程如下： 1 复位p e 和c o n f i ga c k ，检测l o a d ，如果为1 转到步骤2 ； 2 检测c w 数据线上的命令字是否满足条件，如满足则复位p e ，置位 l o a da c k ，将c w 载入内部缓存并转到步骤3 ；否则置位p e ，并转 到步骤1 ； 3 清位l o a da c k ，检测c o n f i g ，如果为1 转到步骤4 ； 4 根据缓存中的c w 配置交换矩阵，置位c o n f i g _ a c k ，转到步骤1 。 介于光交换矩阵不是课题的主要部分，所以只对其接口和工作流程进行简单 的叙述。 2 2 4 命令解析器 命令解析器位于核心调度器和光交换矩阵之间，主要负责命令格式解析、命 1 1 电子科技大学硕士学位论文 令排队、配置光交换矩阵。 为了解决l v d s 电缆传输距离受限，满足不同机架结构产生的连接问题，命 令解析器提供了两种控制方式，一是本地解析，二是远端解析。本地解析使用本 地核心调度器f p g a 的剩余资源，直接在主板上提供与光交换矩阵的接口。远端 解析则是在主板和远端板上通过s e r d e s 芯片通过串行方式传递命令，在远端板上 完成命令解析器的全部功能。 图2 4 命令解析器核心框架 核心调度单元通过对b h p 的处理，产生了要求配置光交换矩阵的命令。其命 令格式如表2 - 2 所示。 2 3 2 2 2 01 9 1 8 1 7 1 6 1 5 0 0 ( 交换矩阵命令)4 x 4 的选择入端口号出端口号偏移时间 表2 2 核心调度单元命令格式 如图2 4 所示，命令解析器的核心框架围绕m a i np r o c e s s i n gp a r t 。该部分按功 能可以划分为一下几部分功能模块：1 ) 命令入缓存。2 ) 形成对光交换矩阵的命 1 2 第二章o b s 交换系统中的重排序问题 令字和对f d l 的命令，即将命令由表格2 的格式转化为表格l 的格式。3 ) 与光交 换矩阵和f d l 交互、配置。 2 3o b s 中乱序问题的成因，特点 在o b s 系统中，核心结点调度器作为b h p 处理、路由选择和光路配置的核 心器件，其性能直接影响到整个o b s 实验系统的表现。对核心结点控制系统预期 的设计指标为： 端口数：4 数据交换波长数：8控制信道波长数：1 控制通道数据到达输出速率：= 1 5 5 5 2 m b p s b l i p 平均处理时延： 1 0 u s 突发数据丢失率： 1 0 e 一5 2 3 1o b $ 核心结点中乱序问题的成因 在前文我们已经介绍过了核- 1 1 , 结点的结构，命令解析器在核心结点中担任3 项工作：命令格式解析、命令排队、配置光交换矩阵。由于b h p 产生、到达和调 度的时刻和b h p 中指定的光路配置时刻没有映射的关系，所以就可能产生乱序的 问题，即较后产生的光路配置命令可能需要较先进行配置。例如命令c 1 于t 1 时刻 到达，要求在时刻t 2 配置光路，而命令c 2 在t 2 时刻到达，要求在t l 时间配置光 路，t 1 2 的连接已经失效。 r 1 ：p o r to u q o o r ti n p o f to u t p o r t 图2 8 配置命令交换示意图 该条件的含义是光交换矩阵由于某种原因在预设时间内没有成功加载 该命令。这种情况下，当前的c w 只能舍弃，将队首替换为链表中处 于下一个位置的命令。需要注意的是，虽然该命令没有实际在光交换 矩阵中得到配置，但必须将其作为下次生成c w 的基础，因为核心调 度器是以该次命令正确配置为前提决定下一条命令的可配置性的，如 第二章o b s 交换系统中的重排序问题 果不将该次命令记入，由于命令的记忆性，本次配置失败将会导致其 后几次配置无效。 4 该条件含义是光交换矩阵由于某种原因在指定时刻没有成功配置该命 令。在出现这种情况时，没有任何明确的信息能够提供链路的状况， 所以只能认为本次调度失败。不过出于与3 同样的理由，该次c w 也 需要记录作为下次产生c w 的依据。 5 p e = 1 显示c w 出现问题，也就是前文提到的，没有达到出入端口一 一对应的条件。如果距离配置时刻还有时间，则需要核心处理单元重 新产生c w ；如果到达配置时刻，则重新产生c w ，但是不进行配置而 直接将该c w 保存，并转入对下一个命令的处理流程。 最后需要注意的一点是，虽然在状态转化图中，为了简化，将核心处理单元合 并为一个状态机，但实际上状态转化图的上下两部分分别是两个独立的状态机， 并行运行。 2 5 5 命令缓存空间 在硬件实现中，命令缓存空间通过使用f p g a 提供的b l o c kr a m 来实现。 v i r t e x l l 支持在一定大小空间范围之内，随意设置存储空间的深度和宽度。 2 5 6 其他部分 f d l 接口单元是为了配置结点可能配置的f d l ( f i b e r d e l a y l i n e ，光纤延迟线) 而预留的，在最后的实现中并没有使用f d l 。 c w 接口即命令解析器和光交换矩阵的接口，在前文已经描述过了。 2 6 仿真结果和在实验系统中的测试 为了测试寄存器链表算法以及使用该算法的命令解析器的有效性，首先在 m o d e l s i m 软件平台上进行了仿真。在仿真环境中，上游信号( 即由核心调度模块 电子科技大学硕士学位论文 提供的信号) 通过自定义激励来模拟，光交换矩阵反馈命令根据需要仿真的情况 不同而分别产生。以下是仿真结果。 2 6 2 新入命令进入空队列 图2 9 单一命令 空队列时，有新的命令进入队列，解析器将命令放入队列，并刷新链表队首 在寄存器的副本。在该命令到期前无新命令进入解析器，则配置该命令，其后链 表清空。图2 - 9 显示了单个命令进入队列的情况。 2 6 3 新入命令配置时间晚于链表表头项 如果队列非空，新入信号配置时间晚于链表表头项，则新入信号与链表中的 信号进行比较，确定位置后插入链表，如图2 1 0 所示。 图2 1 0 插入链表操作 第二章o b s 交换系统中的重排序问题 2 6 。4 新入命令配置时间早于链表表头项 新入命令配置时间较表头项为早 链表中第；艰，面新a 命令成为表头， 2 6 5 光交换矩阵配置 则寄存器和表头均需要改变，原表头成为 同时置入寄存器中。波形如图2 1 1 。 图2 1 1 新入命令替代表头 光交换矩阵配置的正确性和时间准确性需要命令解析器和光交换矩阵交互， 图2 1 2 是光交换矩阵配置的时序波形图。 2 6 6 在实际系统中的性能 图2 1 2 光交换矩阵配置 上面给出的是命令解析模块在m o d e l s i m 仿真软件中的几个重要的时序波形 图。在o b s 核一f l , 结点实验板上，命令解析模块时序正确，工作正常，完成了相应 的任务。在o b s 交换系统的联调中没有出现问题，收n t 预期效果。 皇王型堇奎兰堡圭堂垡笙苎 2 7 在硬件实现中遇到的问题和解决 2 7 1 状态机一数据稳定后操作 因为在v h d l 硬件描述语言中，同一信号量不能在两个进程中被赋值，为避免 出现此情况，同时使程序结构更清晰明了，决定采用状态机。最早使用状态机模 型一 状态机模型一： 【进程一】p r o c e s s ( c l k ) 一时钟沿触发将下一个状态值赋值给当前状态 i f ( c l k 0 e v e n ta n dc l k = 1 ) t h e n i fi e s e t ：1t h e nc s = i n i t _ s t ； 一】f e s e t 状态初始化 e l s ec s n s i f ( x x = 1 ) n s = o t h e