（计算机软件与理论专业论文）基于ixp网络处理器的分组调度机制实现及研究.pdf

摘要 摘要 基于多处理器体系结构的网络处理器( n p ) 通过利用网络中存在的三种并行 性：p l p 、i l p 、i p p ，可以提供高速的处理能力。同时网络处理器具有的对硬件 的完全可编程性，也使得用网络处理器实现路由器等网络设备在计算机网络与 通信领域具有重要的应用前景。目前越来越多的高端路由器等网络设备开始使 用网络处理器。 随着网络上各种不同应用的出现，我们需要在路由器中实现q o s 以提供对 不同业务的区分服务，路由器等网络设备提供q o s 的核心技术是分组调度机制。 完善的分组调度机制能提供诸如带宽、延迟、抖动和丢失率等的性能保证，适 应用户和应用的服务质量要求。同时分组调度机制也能改进拥塞控制，提供系 统服务公平性和服务类间保护。 本文研究了基于网络处理器i x p 2 4 0 0 的并行方式下i p 数据包的分类、队列 管理、d r r w r r p s 分组调度等功能实现技术。讨论了多微引擎通信，即如何定 义有效的接口以实现多微引擎协同工作的问题；临界区访问，即怎样设计算法 从而保持数据包的顺序性的问题；还包括如何有效利用网络处理器中通用寄存 器，传输寄存器和邻接寄存器来最大可能避免并行过程中带来的互斥等技术问 题；如何有效利用专用硬件加速程序执行速度等。模拟器分析结果表明，本文 实现的调度机制能够提供一定的q o s ，该结论对利用网络处理器( n p ) 设计其他 网络设备具有一定的借鉴意义。 关键词：网络处理器，微块，分类，队列管理，d m u w r r p s a b s t r a c t i nt h ec o m m u n i c a t i o n se n v i r o n m e n t ，t h e s y s t e m sd e s i g n e da r o u n dc m p a r c h i t e c t u r ea r ec a l l e dn e t w o r kp r o c e s s o r s0 岬s ) t h e yu s et h ep i j p ，i l p ，口pt o a c h i e v eh i g hs p e e d a tt h es a m et i m e ，n p sp r o v i d ef u l lp r o g r a m m i n go nh a r d w a r e s ot h en p - b a s e dr o u t e r sh a v ea b r i g h tf u t u r ei n t h ec o m p u t e rn e t w o r k sa n d c o m m u n i c a t i o n sf i e l d n o w a d a y s ，m o r ea n dm o r eh j i g h e n dt o u t e r st e n dt ob e n p b a s e d w i t hm o r ea n dm o r en e wa p p l i c a t i o n sa p p e a r i n go nt h ei n t e r n e t w es h o u l d p r o v i d eq o si nt o u t e r st om e e tt h ev a r i o u sn e e d so ft h e m q o si n c l u d e sal o to f a s p e c t s b u tt h ec o r eo ft h e mi sp a c k e ts c h e d u l i n g i d e a lp a c k e ts c h e d u l i n gc a n p r o v i d es e r v i c e sa c c o r d i n gt ot h ec l i e n t s d e m a n d s ，s u c ha sp a c k e tl o s s ，d e l a y ，a n d f l u c t u a t i o n si nn e t w o r kt h r o u g h p u t a tt h es a m et i m e ，t h ep a c k e ts c h e d u l i n gc a r l i m p r o v et h ep e r f o r m a n c eo ft h et r a d i t i o n a lb e s te f f o r ts e r v i c e s ot h i st h e s i si m p l e m e n t sap a c k e ts c h e d u l i n g s y s t e mo ni n t e li x p 2 4 0 0n e t w o r k p r o c e s s o r t h es y s t e mi n c l u d e sc l a s s i f i c a t i o n ，q u e u em a n a g e m e n ta n dw r r d r r p sp a c k e ts c h e d u l i n ga l g o r i t h m i ta l s od i s c u s s e st h et e c h n o l o g yo fc o m m u n i c a t i o n b e t w e e nm i c r o e n g i n e s ，t h ew a yt om a i n t a i np a c k e to r d e r ，t h eu s eo fs p e c i a lh a r d w a r e i na p p l i c a t i o nd e s i g na n dt h es k i l lo fu s i n gt h et r a n s f e rr e g i s t e r s ，t h en e x tn e i g h b o u r r e g i s t e r sa n dt h eg e n e r a lr e g i s t e r st op r e v e n tt h en e e dt oe x c l u s i v e l yu s i n gt h e r e s o u r c e t h eo u t c o m es h o w st h a t t h i ss c h e d u l i n gs y s t e mi s c a p a b l eo fp r o v i d i n g c e r t a i nq o s w eb e l i e v et h a to u rc o n s i d e r a t i o n sa r ca l s oh e l p f u lf u ro t h e rn e t w o r k p r o c e s s o r s k e yw o r d s ：n e t w o r kp r o c e s s o r , m i c r o b l o c k , c l a s s i f i c a t i o n ，q u e u em a n a g e m e n t ， d r r ，、) l ，l i r ，p s 第1 章绪论 第1 章绪论 1 1 网络处理器的诞生与发展 网络处理器的诞生是和互联网络的发展密不可分的。因此，本文先从网络的初期谈起 由路由器的发展过程，逐渐引出我要介绍的话题：网络处理器。 1 1 1 路由器发展 2 0 世纪6 0 年代后期，d e c 推出了个人计算机以取代大型机。由于当时网络速度很低， 个人计算机的能力已经足以完成分组交换的功能加上其比较小的物理空间，较低的f o 端口复杂度，便宜的价格，使得基于传统计算机硬件的体系结构在很长一段时间内主宰了 路由器的发展。现在一般将拥有这样体系结构的路由器( 图1 1 ) 称为第一代路由器或软件路 由器【1 】( s o f t w a r er o u t e r ) 。 s t a n d a r d c p u f r a u l n g s 阻d d r e s s f r a i l r 幽d d r e s s r e c o g n i t i o n l lo t h e rp r o c e s s i n g r e c o g n n l o r t 图1 1 第一代路由器体系结构 困1 2c p u 速度对比网络速度 从图1 2 可以看出，从1 9 9 0 年开始，1 在过去的1 0 年中，网络的速度提高了2 4 0 倍， 而处理器的速度只提高了1 2 倍。因此，第一代以c p u 为核心的路由器很快不能满足需要， 第1 章绪论 人们自然而然的想到将原先c p u 的一些工作( 一般是第二层和第三层的任务) 放到网络接 口卡( n i c ) 中，这样减轻了c p u 的负担，使得系统总的处理能力得到提高。这样改进后 的路由器的体系结构如图1 3 所示： s t a n d a r d c p u s m a r tn i c s m a r t n i c s o m el a y 3p r o c e s s i n g a l lo t h e rp r o c e s s i n g s o m el a y 3p r o c e s s i n g m o s tl a y l & l a y 2p r o c e s s i n gm o s tl a y l & l a y 2p r o c e s s i n g 田1 3 第一代路由器体系结构改进 进一步发现，由于网络上所有的数据包都要经过c p u ，影响了c p u 的工作，在部分 第三层的功能移到网络接口卡中后，n i c 有能力独立进行路由。因此，在这个基础上形成 了不经过c p u 的数据包的快速通道( f a s tp a t h ) ，将c p u 解放了出来，用于处理少量的 控制和例外情况。这样就形成了第二代路由器，如图1 4 ： s t a n d a r d c p u s m a r tn i c s m a r tn i c c o n t r o la n de x c e p t i o n l a y 3f o r w a r d i n gl a y 3f o r w a r d i n g l a y h d a 业p r o c e s s i n gl a y l & l a y 2p r o c e s s i n g f a s tp a t h 田1 4 第二代路由器体系结构 网络速度继续以惊人的速度提高，不仅如此，新涌现的各种应用如q o s 负载平衡等， 需要对数据包进行深度处理，这种情况下，c p u 依然成为瓶颈。为了进一步减轻c p u 的 负担，人们设计出了第三代路由器，如图1 5 所示。这种系统中，针对各种具体协议处理 任务优化的硬件被设计出来，然后在每个网络接口上进行复制，这样就将这些协议的处理 任务从c p u 中移走，大大减轻了c p u 的负担，而且使得网络接口能够处理异常和高层协 议。同时用交换结构组建快速通道，替代以前的总线方式，这样可以使快速通道上的数据 流速度最大 2 第1 章绪论 s t a n d a r d c p u o t h e rp r o c e s s i n g t r a f f i cm a n a g e m e n t 一 l a y l kl a y l a y 2 l a y 3 t c h s s i l a y f i c a t i o n s w i t h c h i n gf a b r i c 田1 5 第三代路由器体系结构 然而把第二层和第三层的处理交由硬件处理的方法，随着底层协议的迅速变化( 如 m p l s ，d i f f s e r v 等) 而遇到了巨大的困难，硬件a s i c 的设计成本高，设计周期长，通常要 1 2 到1 8 个月，一旦需要作修改，则不得不重新设计，浪费大量的时间和金钱，因此迫切 需要在底层硬件中引入某种类似于处理器的可编程能力。 同时，随着高层应用的不断涌现，如网络交换，u r l 访问负载平衡等。这些应用，不 仅需要高层处理有很大的灵活性，还需要很高的速度。而且，最近的趋势表明高层应用对 速度的需求会越来越大。同时快速通道有上移的趋势。研究表明，当嵌入式处理器处在 快速通道中时，已经越来越成为系统的瓶颈。本文迫切要在这里引入a s i c 的高速度。 既然a s i c 和嵌入式处理器各有优缺点，而且都是构建路由器不可或缺的，人们自然 想到了，能不能将他们的优点整合到一起呢? 在这种需要的推动下，人们开始了寻求能集 两者优点于一身的网络设备，这种设备各人们称为网络处理器( n e t w o r kp r o c e s s o r ) 。由此 开始了网络处理器漫长的发展过程。 1 1 2 网络处理器发展 下面，我就网络处理器的发展过程中世界上开展的与之有关的研究作以下总结： 1 网络处理器体系结构评估研究 自从业界出现网络处理器的需求后，很多厂商如i n t e l 、i b m 等就开始着手其体系结构 的研究，企图使自己的体系结构成为业界标准。这些厂商提出的体系结构千差万别，但都 有一个共同点，那就是尽量使得网络的负载本身固有的并行性能得到充分发挥。 然而，什么样的负载才是网络处理器应该针对的，即网络处理器的应用范围应该是什么， 仍然没有明朗，这和当前新的应用层出不穷不无关系。其实这是一个两难问题：一方面，网 络处理器是用来解决当前应用变化过快导致的基于a s j c 的网络设备灵活性不足的问题，这 就表明网络处理器必须能够适应这种变化，并且当新的应用出来时，其依然可以在保持优于 a s i c 灵活性的同时又有相当高的速度；另一方面，网络处理器的设计，是依靠当前的网络 负载来评估其性能的，怎样能找到这样的负载，使得它代表了当前应用的特点的同时，又具 有很好的前瞻性，也是网络处理器研究过程中不得不考虑的一个很重要的问题。不然，若针 对一个负载设计出的处理器在应用发生变化时性能变化很大，则网络处理器就失去了存在的 意义了。因此，负载和网络处理器的体系结构可以说是相互影响，互为鸡和蛋的关系。 p a t r i c kc r o w l e y 等人“1 假设网络处理器体系基于超标量处理器、 细粒度多线程处理器、 单芯片多处理器( c m p ) ”。、 同时多线程处理器( s m t ) “1 ，然后利用了几种负载“1 来对这些 3 第1 章绪论 体系结构进行评估。用模拟器进行模拟得出的结论是：在相同的处理器资源的条件下，s m t 架构的网络处理器对这些负载的表现要好于其他架构。 t i l m a n w o l f 等人讨论了在单个芯片上集成多个处理核时的体系结构的配置问题”“，利 用c o m m o n b e n c h s l 技术，得出网络处理应用在多处理器平台上的特性，一般用s i m p l e s c a l a r 模 拟，包括执行的指令，内存访问等，然后利用这些参数作为该论文中提出的晟优化模型的输 入，得到针对这些参数的处理器最优设计，使得单位片上处理能力最大。本文的贡献在于用 提出的模型，可以给出对网络处理器最优化配置的建议和系统参数的变化对整体性能的影 响。 r r a m a s w a m y 等人提出y p a c k e t b e n c h 的方法，也是用s i m p l e s e a l a r i 具来模拟网络处 理器的内核部分，主要特点是提出了p a c k e t b e n c h 的框架结构，在框架中，对内存管理也有相 应的模拟。 随着研究工作的进展，业界各大公司也相继推出了自己设计的网络处理器的第一代产 品，$ ! j 2 0 0 2 年为止，已经有3 0 多家生产商提供网络处理器产品。如a l c h e m y ，a g e r e 的f p p ， i n t e l 的i x p l 2 0 0 等。其中i n t e l 的i x p l 2 0 0 ，比较有代表性，可以说是在这之前研究界所做研究 的一个总结性产品。i x p l 2 0 0 主要由6 个可编程微引擎和一个工作在2 0 0 m h z 的 s t r o n g a r m 处理器组成。6 个微引擎在快速通道中并行工作。有了成型的网络处理器，人们 也把以前用s i m p l e s c a l a r 来模拟体系结构进行基准测试的方法转换成了在这些产品上来做。 m e m i k ，ga n dm a n g i o n e - s m i t h 等人“1 ，将所有应用分为了3 个层次：微观级，路由级和 应用级。比较m e d i a b e n c h 和n e t b e n c h ，m e d i a b e n c h 是运用于通信和多媒体领域的基准，这些领 域的系统结构接近于n p ，比较结果显示两种基准所表现出来的差别很大，n e t b e n c h 表现出的 是数据密集，有着大量的内存访问。而m e d i a b e n c h 确有着大量的跳转指令，表示它代表的应 用有着很低的指令并行度。在将n e t b e n c h 在1 g h z 的i n t e lp e n t i u m 上运行的结果和在i x p l 2 0 0 上作了比较，结果i x p l 2 0 0 全面胜出。 m e lt s a i l ，c h l d a m b e rk u l k a m i l 等人“，在考虑了当前商用网络处理器体系结构的差别 ( 如c - p o r t - 5 和i x p l 2 0 0 在很多方面存在很大的差别) ，并将它融入到基准测试中。文中简要 概括t c o m m e n b e n c h ，e e m b c ，n e t b e n c h ，n p fb e n c h m a r k i n gw o r k i n gg r o u p 的局限性。 2 网络处理器应用研究 1 ) q o s 相关研究 q o s 一直是一个趋势，如何能够对用户提供高效的q o s 服务一直是研究的热点。网络处 理器概念的出现，也使很多人将目光转向怎样利用网络处理器来提供q o s 服务的研究中来。 y i n g - d a r l i na n d y i - n e n g l i n 等人用i x p l 2 0 0 实现了一个支持区分服务的边界路由器 1 ，并分析得出，i x p l 2 0 0 路由器在实现区分服务时，吞吐率会下降很多，瓶颈在于静态内 存和微引擎。 h i d e y u k is h i m o n i s h i ，t u t o m um u r a s e 等人设计了一个基于网络处理器的高速灵活的q o s 控制器“：这个基本体系包括几个级别：( 1 ) 寄存器内采取共享的方式，( 2 ) 一个局部互连， ( 3 ) 全局互连，( 4 ) 芯片间的互连。在速度的优化上采用的是多条数据腔制线的方式，使 得存取寄存器更快，在多处理器调度的策略上采用的是静态的调度方式，避免了动态调度的 缺点，并且每个处理器得到的是固定的时钟周期t ，由于可以把旧调整为最小包的处理时间 或其整数倍，因而能得到很好的性能。对于该体系架构的评估采取的是用如下三个应用的实 现来测量其性能表现。( 1 ) i p 数据包转发，( 2 ) i p a t m 多层交换，( 3 ) 基于流的区分服务 调度器。 2 )可扩展路由器相关研究 主动网的出现，打破了传统网络中信息只是被动的从一个结点流动到另一个结点的模 式，使得可以根据需要在信息经过结点时对其进行一些处理，从而可以提高更好和更灵活的 4 第1 章绪论 服务，如拥塞通知，包过滤等i l “。 用来计算的代码可以放在两个地方： ( 1 ) 信息包的内部【l6 j 【l ”，( 2 ) 信息包里是代码 的引用，真正的代码放在路由器中1 18 j _ l “。 如果用方法1 来实现，那么代码的平台无关性就显得非常重要，通常用虚拟机代码可以 实现平台无关性。但是，虚拟机代码需要解释执行，一般说来有本地机器码1 0 倍的执行时间 p l l 。 j r r ( 即时翻译) 的出现，使得传统的基于软件的路由器的低性能实现臌得不可能，而 j 丌技术是提高虚拟机代码的执行速度，进而促进代码平台无关性的重要一步。而网络处理 器的出现，使得j 的实现有了好的平台。 a n d r e a sk i n d 口日等人针对i b m 的p o w e r n p4 g s 3 网络处理器实现了s n a p 的j r r ，并且针对 t r a c e r o u t e 和c o n g e s t e dh o pc o u n t e r 两个例子分析了j r r 和解释的性能，从文中本文可以得出： ( 1 ) 对于这两个例子的每一条语句进行比较时发现，平均情况下，编译一条语句要5 7 4 个 时钟周期，而解释一条语句要4 7 7 个周期，本地代码的执行要4 4 个周期，这样看来j i t 的性 能要稍差于解释。( 2 ) 对于整个例子而言，t r a c e r o u t e 上j r r 没有表现出优于解释的地方( 见 图5 ) ，而c o n g e s t e d h o p c o u n t e r 上j 1 t 却表现出来惊人的速度，j r r 执行只需要大约1 8 0 0 个周 期，而解释却要接近7 8 0 0 个周期。分析后发现，后一个例子存在大量的循环，这种情况下， 指令映射和基于内存的栈操作带来的是解释开销的急剧上升，而此时，j r r 就显得优势非常 明显了。 由于主动网的出现，可扩展路由器的研究受到了广泛的关注。 3 1基于i x p l 2 0 0 的i p v 4 i p v 6 转换 由于i p v 4 地址空间很快就要用完，下一代互联网协议i p v 6 于1 9 9 5 年正式成为i e t f 的标 准，但是由于现在很多应用都是基于i p v 4 的。不可能很快被i p v 6 取代，因此， p v 4 和i p v 6 共存的情况必定要延续很长时间，i p v 4 和i p v 6 之间转换的研究已经展开l m l ，如目前用 的比较多的要数n a p t - p t 。由于网络处理器的出现，已经有人开始利用它来实现n a p t - p t , e r i cg r o s s e 等人利用i x p l 2 0 0 ，实现了n a p t - p t ，并讨论了相关的问题。 3 其他研究问题 1 )处理引擎并行性研究进展 为了达到很高的速度，对于网络处理器内部的处理引擎必然要求其能并行工作。 在 2 6 1 d p ，l i u h u a n 研究了在数据包流中存在的3 种并行可能：p l p , i p p , i l p ，对于现在一些厂 商盲目地添加更多的处理引擎来提高对于p i n 的利用率，指出：由于同一个数据流内的数 据包，存在包与包的依赖关系，导致本文不能随意靠增加p e 的数目来达到这个目的。 l i u h u a n 针对实际的网络数据分析后得出，为了能提高数据的处理速度，本文更应该在i p p 的提高上下功夫。 l i u h u a n 提出的网络处理器架构是一个3 级的体系结构，由处理引擎实现p l p ，在每个处 理引擎内，由任务引擎实现i p p ，每个任务引擎内又可以实现l i p 。 l i u h u a n 的试验得出的结论是p i p 的利用率随着处理引擎的增加而迅速下降，即使在只有 8 u 1 2 个处理引擎的情况下。p l p 的利用率已经很低了。 另外，l i u h u a n 验证了，在输入端增加输入重排序缓存可以显著提高p l p 的利用率。 p a p a e f s t a t h i o u ，k v l a c h o s , n n i k o l a o u 等人对球p 进行了深入的研究，并提出了一个3 层 的管道模型口”。这3 个部分单元，其实就是前面所说的任务引擎，分别是域提取单元( f e x ) ， 普通r i s c 核和一个域修改单元( f m o ) 。这3 个单元，把一个数据包分成3 阶段处理，阶段 间可并行执行。通过这种精巧的设计，使得i p p 利用率提高，从而达到对整个数据流处理速 度的提高。通过试验表明，该模型能比现有的商业网络处理器有更好的性能。 2 )表查找算法和体系结构研究进展 5 第1 章绪论 网络上的应用大量的要对不同的表进行查找( 如路由表，访问控制链表，会话表等) ， 因此网络处理器一般集成有专用的搜索引擎，用来将网络处理器从繁重的搜索处理中解 脱出来。 目前的做法般有3 种，( 1 ) 一些商用的网络处理器已经集成了搜索幽】【2 9 j ；( 2 ) 提高 主处理器核的m i p s ，依靠软件实现各种搜索算法刖j ；( 3 ) 将某些处理引擎用来专门做搜索， 即将这些处理引擎等同于某些特定的搜索算法的硬件实现j 。 m o h a m m a dp e y r a v i a n ，g o r d o nd a v i s 等人对于这三种做法，结合几种搜索算法的分析， 给出了它们对网络处理器性能的影响。 3 )分类算法及相关研究 网络处理器一个很重要的功能就是包的分类，而其中最重要的要数在多域上的分类， g u p t ae t e 3 3 | 给出了各种传统分类算法和相关的分析，这里就不一一列举。这种分类进展不大 如果用软件来实现，在最坏情况下，算法的复杂度会很高，对包分类这类问题，可扩展性 一直都是没有解决的问题，因此，分类功能能否在网络处理器上高效的实现，将是网络处 理器能否成功的一个关键性因素。 y i e - t a m gc h e r t ”“给出了一个基于硬件的分类算法，用于构建网络处理器中的包分类 引擎。首先，一个大的规则集被分为了几个小的集合，这些集合可以被同时并行的搜索， 然后，每个规则被编码为了一个较小的位字符串，并且用一个一位的二进制检索树实现位 选择；最后，所有被编码的规则被压缩在了一个两级的索引表中。通过进行模拟测试表明， 包分类可以在一个很小的内存中，只用两个内存周期就可以完成对索引表的查找和一次规 则比较。在最坏情况下，仍然获得了8 ，0 0 0 ，0 0 0 p s 的速度。 1 2 基于网络处理器分组调度机制研究的意义 在1 1 2 节本文已经详细描述了网络处理器领域中的各个研究方向和发展状况。可以看 出目前网络领域几个重要的趋势：( 1 ) 基于网络处理器架构的路由器已经受到越来越多的 关注；( 2 ) 传输管理( t r a f f i cm a n a g e m e n t ) 是网络中一个重要的部分。传输管理包括不 同的机制和策略，但其核心技术是分组调度机制。完善的分组调度机制能提供诸如带宽、延 迟、抖动和丢失率等的性能保证，适应用户和应用的服务质量要求；同时分组调度机制也能 改进尽力发送服务以避免拥塞和提供系统公平性和服务类间保护。在网络中关键的设备一 路由器中实现o o s 已经受到广泛的关注。 国际上关于分组调度机制的相关研究较多，如s o n y 公司开发的基于f r e e b s d 内核实 现的有c b o ( c l a s sb a s e dq u e u i n g ) ”和d r r 模块的a l t q 1 ：普林斯顿大学的可扩展路 由器项目利用基于路径( p a t h ) 的s c o u t ”操作系统实现了可扩展的路由器体系结构1 ，它 实现了d r r 1 ，v i r t u a l c l o c k ”1 和w f q “等算法：华盛顿大学的研究小组提出了路由器插 入程序“体系结构用于对集成服务路由器进行功能扩展；m 1 t 的计算机科学实验室实现 了一种称为c l i c k 的模块化的路由器软件体系结构“。以前的这些研究提出过许多分组调 度策略，也作了一些分析和模拟，但这些策略的一个关键问题是没有或难于在实际的网络互 连设备( 如路由器) 中实现。另外，在c i s c o 和j u n i p e r 开发完成的高档路由器中实现了 可酉己置的分组调度机制，c i s c o 实现了包括优先级捧队、分类排队( c b 0 ) 、随机丢弃 ( r e d ) 、标签交换( m p l s ) 等在内的多种算法和机制，而j u n i p e r 也实现了r e d 、m p l s 等调度策略。但由于分组调度机制是路由器的核心技术，所以其实现细节是非公开的。 因此，有必要研究基于网络处理器q o s 机制的实现，即分组调度机制和网络处理器结 合性研究。 6 第1 章绪论 1 3 本文的贡献 本文详细讨论了几种基于i x p 2 4 0 0 网络处理器的具有q o s 能力的分组调度算法的实现 过程和方法。并对算法的性能给出了仿真和评测。具体贡献如下： 1 研究了基于网络处理器的分组调度机制的几个模块的具体实现步骤和方法。 2 研究了如何利用网络处理器上多微引擎( p e ) 进行并行处理，提高算法效能的方 式。 3 利用数据包模拟器进行各种数据流的模拟，观察在几种并行方式的框架下系统的 性能，并对结果进行分析。 4 对基于网络处理器的分组调度机制实现的优化给出了建议。 7 第2 章i x p 2 4 0 0 网络处理器 第2 章i x p 2 4 0 0 网络处理器 2 1i x p 2 4 0 0 硬件体系结构 i n t e l 的p 2 4 0 0 网络处理器为第二代高性能网络处理器，为互联、通信和数据集中应 用提供o c - 4 8 ( 2 5 g b s ) 的能力。 它有着一个i n t e l x s c a l e 核以及8 个硬件多线程，3 2 位的r i s c 数据引擎。可以提供高 达5 4 g i p s 。 图2 1 显示了i x p 2 4 0 0 的整体结构图。 2 1 1 可编程处理器 圈2 1i x p 2 4 0 0 整体结构图 1 i n t e l x s c a l e 核 通用3 2 位r i s c 处理器，兼容a r m 版本的i n t e l x s c a l e 主要用来初始化和管理网络 处理器芯片，可以处理高层网络应用。 2 微引擎 3 2 位针对网络应用优化了的可编程引擎，主要用来执行快速通道中的处理任务。微引 擎的关键组成部分如图2 2 ： ( 1 ) 多硬件线程：每个微引擎支持8 个硬件线程。每个线程拥有自己独立的程序计数 器。 ( 2 ) 通用寄存器：每个微引擎有2 5 6 个通用寄存器，作为算术计算。可分为两组，用 绝对和相对编址模式。 0 ) 邻接寄存器：每个微引擎有1 2 8 个邻接寄存器，用于在流水线方式下的前后微引 擎间提供直接的通道，比如，微引擎0 ：0 将数据写道邻接寄存器中，只有微引擎0 ：1 可 以从中读取数据。通过配置两个控制与状态寄存器( n n _ g e t , n n _ p u t ) ，可以作为1 2 8 个邻 接寄存器组成的队列的生产者和消费者的地址。 8 第2 章i x p 2 4 0 0 网络处理器 图2 2 微引擎内部结构图 f 4 1 静态存储器传输寄存器：每个微引擎有2 5 6 个3 2 位的静态存储器传输寄存器。静 态存储器传输寄存器用来在l x p 2 4 0 0 上读和写所有的功能单元( 除了动态内存单元) 如便 笺式暂存，啥希控制和状态寄存器访河代理，媒体交换结构，p a 接口等。当数据从这些单 元中读出时，首先被放置在静态存储器传输寄存器中，而如果要写到这些单元中，则必须 首先放到静态存储器传输寄存器中。静态存储器传输寄存器一半是只读，一半是只写。 ( 5 ) 动态存储器传输寄存器：每个微引擎有2 5 6 个，3 2 位的动态存储器传送寄存器， 被等分成相同大小的只读和只写寄存器。可以用于微引擎和动态存储器单元通信。也可以 以只读的方式和其他单元通信。就是说，动态存储器读寄存器可以取代静态存储器读寄存 器。 f 6 ) 控制与状态寄存器：微引擎必须和许多硬件设备大交互，这是通过控制与状态寄 存器实现的，控制与状态寄存器用来控制i x p 2 4 0 0 而不是和外部设备通信，每个微引擎可 以访问自己的本地控制与状态寄存器，但是不能访问其他朱引擎的控制与状态寄存器，控 制与状态寄存器提供了控制i x p 2 4 0 0 的机制。 2 1 2 功能接口 1 动态存储器控制器 一个动态存储器控制器。动态存储器容量大，访问时间长，通常动态存储器用来存储 数据包。 2 静态存储器控制器 两个独立的用于静态存储器的控制器。静态存储器容量较小，访问时间快，通常静态 存储器用来存储控制信息。 3 便笺式暂存 9 第2 章i x p 2 4 0 0 网络处理器 1 6 k 用于通用任务的存储器。组织成4 k 3 2 位的字，每次只能一次性读或写，只能以4 个字节为单位，一条微引擎指令可以读取1 到1 6 个字。 4 媒体和交换结构接口( 媒体交换结构) 用于网络数据包和，或者交换结构的接口。包含了用于接收和传送的缓冲区。 5 哈希单元 多项式哈希加速器。i n t e lx s c a l e 核和微引擎可以用它来进行哈希计算。 6 p c i 控制器 6 4 位的p c ir e v 2 2 兼容i o 总线。p c i 既可以用来连接宿主处理器，又可以连接p c i 兼容的外部设备。 7 控制和状态寄存器访问代理 全局控制和状态寄存器。这些用来提供微引擎间或者微引擎和x s c a l e 核的通讯。 8 i n t e lx s c a l e 外围设备接口 中断控制器，计数器和连接外部低速设备的接口。 2 1 3i x p 2 4 0 0 和i x p 2 0 0 的区别 本文是用1 x p 2 4 0 0 实现算法的，由于在此之前在l x p l 2 0 0 上做了一些工作，在这里 我将i x p 2 4 0 0 不同于i x p l 2 0 0 的地方做一些说明。 更多的通用寄存器和传输寄存器 拥有1 2 8 个邻接寄存器v sn o n ef o ri x p l 2 0 0 拥有6 4 0 个3 2 位字长的本地寄存器v sn o n ef o ri x p l 2 0 0 i x p 2 4 0 0 有8 个可用的线程，而i x p l 2 0 0 只有4 个 拥有4 k 的指令存储空间v s2 kf o ri x p l 2 0 0 拥有c a m 单元v s n o n c f o r i x p l 2 0 0 1 x p 2 4 0 0 没有i x p l 2 0 0 的总线。代之以媒体交换结构接口 2 2i x p 2 4 0 0 软件体系结构 本文在前言中就网络处理器的各种软件结构的发展作了一个总结，从中可以看到，一 个好的软件体系结构是网络处理器能否成功的关键。换句话说，成功的网络处理器要在提 供给程序开发者一个既能让他们操纵硬件以得到性能上优化的同时屏蔽掉大部分硬件细 节，使得开发人员的开发工作能简单和轻松。 有了上文所插述的体系结构，接下来就介绍在该体系结构上开发网络应用程序的简单 步骤： 2 2 1 软件开发平台 i x p 2 4 0 0 软件体系结构在i n t e l x s c a l e 上给开发人员提供了类似于l i n u x 的编译和执行 环境，而微引擎上的开发则提供了基于w i n d o w s 的可视化编程界面开发环境。 微引擎上主要开发语言有两种： 微引擎c ：一种类似于c 语言的语言，在某些方面有区别和联系 微码：基本格式为：o p c o d e p a r m l ，p a r m 2 ，】，o p t l ，o p t 2 1 0 第2 章i x p 2 4 0 0 网络处理器 另外，它还提供了一个框架，叫做主动编程框架( a c e ) 。开发人员利用这个框架可以 开发出在不同应用程序和不同版本的网络处理器上可复用的代码。 2 2 2i x a 可移植编程框架 网络应用程序通常分为3 个层次：数据层( 数据p l a n e ) 、控制层( c o n t z o lp l a n e ) 、管 理层( m a n a g e m e n tp l a n e ) 。快速通道位于数据层，处理大部分的数据包。控制层和管理层 属于慢速通道( s l o w p a t h ) 。其中，控制层用于处理异常情况，用来维护数据层用到的数据 如路由表等管理层用来负责配置系统，收集统计数据，提供用户界面等。微引擎位于快 速通道，而i n t e l x s c a l e 位于慢速通道中。 为了减轻程序员的负担，i n t e l 提出了i x a 可移植框架。在该框架中，网络应用被看 成在一个连续的数据包流上进行的一系列处理。由于1 x p 2 4 0 0 的多线程多微引擎的硬件体 系结构，这些处理分布在所有这些微引擎上。 i x a 可移植框架是一个层次化的框架。如图： 图2 3i n t e il x a 框架总体结构圈 通过给各个层次提供需要的程序库，以及定以备个层次间的标准化接口，例如微引擎 和x s c a l e 核通讯的接口，使得本文可以将精力放在自己的那部分，也可使程序每个部分的 开发人员能够顺利的沟通和交流。 由于本文都是关于快速通道层次的，即在微引擎上的编程，因此，在这里，我主要介 绍i x a 框架在这个层次提供给本文的东西。、 1 m i c r o b l o c k 在微引擎上进行的快速通道的处理被i x a 框架从逻辑上分为一些独立的部分，每个部 分叫做一个微块。每个微块都是一个用微码写成的宏或是微引擎c 语言写成的函数。 每个微块执行一个独立的功能，和其他微块都必须有着清晰的接口。这样本文就可以将 许多微块按照不同的方式连接起来，组成一个大的应用程序。 第2 章i x p 2 4 0 0 网络处理器 每个微块在i n t e l x s c a l e 核上都有一个对应的管理组件，叫核组件，一般在一个完整的席 用程序中，本文将每个微块产生的异常发送给他 | 、】进行处理，在这里，我对核组件不做近一 步的介绍，有兴趣的可以参考相关手册。 2 调度循环 由于在一个微引擎上运行的线程可能有几个微块，因此本文通过调度循环将他们组织起 来。 调度循环提供了微块有效存取在数据包描述符和元数据中数据的机制，也提供了接收和 发送给其他调度循环数据包的方法。本文一般用微块库来实现它。 该库提供了用于和x s c a l e 核通讯的例程，同时还提供了几种把微块组织成处理组的机 制。特别的是，该设施支持顺序处理和并行处理细分为两种模式：有序线程执行模式和乱 序线程执行模式。 3 优化数据层库 这是一些对性能和指令条数进行优化了的可复用的软件功能模块。分为两部分： 1 ) 硬件抽象 指令简化，提供了用于微引擎汇编指令的简化接口。微引擎c 不需要这个库。 操作系统仿真，提供了诸如油箱，i 临界区，简化的内存访问，缓冲区操作等。 工具设施，提供了对专用硬件的访问，如哈希表，循环冗余校验，线程等。 2 ) 协议库 提供了有助于标准网络协议处理的功能，如以太网字段抽取，i p 包处理等。 2 2 3i 】( 重要数据结构 i x a 框架用到了一些类型的数据结构，这些数据结构对每个数据包是唯一的，这些数 据结构是： 1 数据包原子数据 描述数据包的一些特性，比如缓冲区描述符，数据包长度，头部类型。数据包的状态 是通过数据包原子数据从一个微块传到另外一个微块中的。共享内存，邻接寄存器，或者 是反射操作，可以在微引擎间传送原子数据。当多个微块运行在同一个微引擎上时，原子 数据是在局部存储器中。如：本地寄存器，通用寄存器，传输寄存器等。在调度循环的开始， 原子数据被存放在这些地方，在调度循环的结束处，原子数据写回到静态存储器中。微块 通过访问函数访问原子数据，这样本文可以屏蔽掉底层原子数据的实现细节。缺省情况下， 原子数据有8 个长字，存放在静态存储器中。 主要内容如图2 4 包括： 缓冲区中数据包数据的大小 动态存储器中数据包开始的偏移量。每个缓冲区在动态存储器中都是2 k 大小，数 据包在1 2 8 偏移量处。这样本文可以在数据包前面加上包头而不需要移动数据包 数据包长度，如果数据包长度大于2 k ，微引擎就知道数据包跨越了许多缓冲区 长度类型，判断是否是i p v 4 或者i p v 6 2 数据包缓冲区 数据包被媒体交换结构单元以m p a c k e t 的形式接收后，存放在动态存储器中，在动态 存储器中，数据包以缓冲区的形式存放。通常缓冲区的大小设置为2 k ，也可以配制成其他 大小，只要大小是2 的幂就行。如果数据包小于2 k ，则被放在一个缓冲区中。如果人于2 k 第2 章l x i ： 2 4 0 0 网络处理器 l wb i 协s i z ef i e l dd e s cr i f ) t i o n o3 1 ：o3 2 b u f f e r _ n e m b u f f e rh a n d l eo fn e x tb u f f e rht h ec h a i n 3 ：1 61 6 t l e r _ $ 1 z e b u f f e r s i z ei nb y t e s 1 1 5 ：o1 6o f f s e to f f s e to f t h es t a r t o fd a t e i n t h eb u f f e r i nb 、舳e 3 ：2 日1 6 p a c k o t _ 鲥z e t o t a lp a c k e t s i z e , a o m sh t j f f e r 自, 1 5 ：1 24 f r e e l i s l i d