（计算机系统结构专业论文）传统网络协议软件的并行优化.pdf

摘要 网络处理器是当前为加速主干网络节点处理速度而提出的并行体系结构。不 同于传统的通用处理器，网络处理器充分的利用线程级的并行提升性能。网络处 理器复杂的体系结构和编程模型给开发高性能的网络应用程序造成困难，然而目 前有大量的网络协议软件作为操作系统的一部分运行在通用处理器上，通过修改 这些现有的软件使之可以运行在网络处理器上，并且分析性能瓶颈，充分开发程 序的并行性，可以极大的提高网络处理器的开发效率。 传统的网络协议软件是基于通用处理器体系结构的，本质上是事件驱动的 而网络处理器的编程模型是数据包驱动的，从而可以利用流一级和报文一级的 并行性分析和比较两种编程模型是首先要解决的问题本文在阅读l i n u x 的内 核协议栈代码和u i pt c p 协议栈代码的基础上，将它们手动修改和调试，改写成 适合i x p2 8 0 0 8 0 网络处理器的代码并且对性能作出分析和优化。提出对传统 网络协议软件优化的基本思路。最后把所有的修改方案统一整理，开发出合适的 算法，并且在我所研制的a g a s s i z 源程序自动变换系统上实现了部分算法 关键字 ：网络处理器网络协议软件并行优化 中图分类号 ：t p 3 计算机技术 a bs t r a c t u s i n g n e t w o r kp r o c e s s o ri st h en e wt r e n df o r d e v e l o p i n gh i g h p e r f o r m a n c ep a c k e tp r o c e s s i n ga p p l i c a t i o n s t h em u l t i c o r e a n d m u l t i t h r e a d i n ga r c h i t e c t u r eo fn e t w o r kp r o c e s s o rh e l p si m p r o v ep a c k e t p r o c e s s i n gp e r f o r m a n c es u c ha si pr o u t i n g ，t c ps t a c ke t c h o w e v e r ，t h e h i g hp r o g r a m m a b ili t yo fn e t w o r kp r o c e s s o rc o m p li c a t e sr a p i dd e v e l o p i n g a p p l i c a t i o n s a st h e r ee x i s t sm a n yn e t w o r kp r o t o c o ls o f t w a r e ，r e s e a r c h i n g t h ed i f f e r e n c eb e t w e e nt h e s et r a d i t i o n a lp r o t o c o ls o f t w a r ea n dn e t w o r k p r o c e s s o rs o f t w a r em o d e la n dt r yt op o r tt h e mt on e t w o r kp r o c e s s o rw i t h s o m eo p t i m i z a t i o n sc a nb ean e ww a yt oa c c e l e r a t ed e v e l o p i n gf o rn e t w o r k p r o c e s s o r s t r a d i t i o n a lp r o t o c o ls o f t w a r eo b e y se v e n t d r i v e n ( s u c ha si n t e r r u p t s ) p r o g r a m m i n gm o d e l ，w h i l en e t w o r kp r o c e s s o rp r o g r a m m i n gm o d e lf a v o r s p a c k e t d r i v e nm o d e l ，w h i c hc a nh i g h l ye x p l o i tp a c k e t l e v e la n df l o w l e v e l p a r a l l e l i s mo fp a c k e tp r o c e s s i n ga p p l i c a t i o n s t og a pt h ed i f f e r e n c e ，t h e i ps t a c ko fl i n u xk e r n e la n du l pt c ps t a c ki sa n a l y z e da n dp o r t e dt oi x p 2 8 0 0 b 0n e t w o r kp r o c e s s o rs y s t e m t h e i rp e r f o r m a n c e sa r ea l s oi m p r o v e db y s u g g e s t e do p t i m i z i n gm e t h o d s a tl a s t ，a l lt h ep o r t i n ga n do p t i m i z i n g m e t h o d sa r e p a c k e du p a n d p a r t i a l l yi m p l e m e n t e di n o u r a g a s s i z s o u r c e - t o - s o u k l r c et c o 】 k e yw o r d s ： n e t w o r kp r o c e s s o rp r o t o c o ls o f t w a r e p a r a l l e l 一4 1 1 课题背景 1 绪论 传统的网络协议处理系统建立在通用处理器上，协议处理软件也被编写成用 户级应用程序或者成为操作系统内核的一部分因此传统网络协议处理本质上 由软件来完成的比较典型的协议处理主要是i p 转发和路由但是由于通用处 理器体系结构的限制，软件路由器难以应付高速网络的处理速度要求目前出 现了很多新的技术和体系结构比如使用a s i c 制造高性能的协议处理器缺点 是设计和制造费用昂贵另一种代表性的技术则是设计专门针对网络协议处理 的网络处理器它是一种专用的，可编程的硬件设备，结合了r i s c 处理器的低成 本，灵活性和a s i c 的速度和可扩展性同时网络处理器拥有简单的硬件接口，降低 了定制网络系统的设计实现的时间和成本目前较成功的网络处理器产品是 i n t e l 公司的i x p 2 x x x 系列 网络处理器复杂的体系结构和编程模型给开发高性能的网络应用程序造成困 难对于如何设计编程模型，学术界倾向于研究自动机语言的高性能编译技术以 及p e r f o r m a n c ed o m a i ns p e c i f i cl a n g u a g e 等伴随着网络处理器以及其他多线 程多处理系统结构而新产生的编程语言和技术。本文试图从另一个方面探讨高性 能的网络协议软件的开发技术。目前存在大量的为通用处理器编写的网络协议处 理软件通过分析和比较传统的网络协议软件和专为网络处理器开发的协议处 理软件，在编程模型，优化技术等方面的区别和联系，进而总结出一些行之有效 的并行优化方法，充分利用网络处理器的并行性，无疑是很有启发意义的。如果 有一个工具可以自动把这些成熟的传统网络协议软件变换成可以运行在网络处 理器上的软件，通过研究必要的优化技术，更可以推动网络处理器的研究和开发 加速现有网络的协议处理速度同时，所得的成果也可能对一大类的应用程序的 并行化方法给出一定的指导意义 1 2 论文内容安排 本文内容安排如下：第二章给出传统网络协议软件的背景介绍；第三掌回顾 了在网络处理器架构提出之前，网络协议软件优化的途径和基本方法：第四章对 网络处理器的产生，发展和目前的软件开发模型进行了详尽的描述。第五章提出 了传统网络协议软件的抽象模型，以及使之能运行在网络处理器平台上必须解决 的问题。并且对网络协议软件报文处理模型的优化作了深入的探讨和实践。第6 章在前述章节的基础上，进一步分析开发自动化转化工具的面临的挑战，以及目 前的解决方案。 2 1 网络软件介绍 2 传统网络协议软件介绍 网络软件是在计算机网络环境下，用于支持数据通信和各种网络活动的软件。 连入计算机网络的系统，通常根据系统本身的特点、能力和服务对象，配簧不同 的网络应用系统。其目的是为了本机用户共享网中其他系统的资源，或是为了把 本机系统的功能和资源提供给网中其他用户使用。为此，每个计算机网络都制订 一套全网共同遵守的网络协议，并要求网中每个主机系统配置相应的协议软件， 以确保网中不同系统之间能够可靠、有效地相互通信和合作。 计算机网络分为用户实体和资源实体两种基本形式。用户实体( 如用户程序和 终端等) 以直接或间接方式与用户相联系，反映用户所要完成的任务和服务请求。 资源实体( 如设备、文卷和软件系统等) 与特定的资源相联系，为用户实体访问相 应的资源提供服务。网络中各类实体通常按照共同遵守的规则和约定彼此通信、 相互合作，完成共同关心的任务。这些规则和约定称为计算机网络协议( 简称网 络协议) 。网络协议通常是由语义、语法和变换规则3 部分组成。语义规定了通 信双方彼此之间准备”讲什么”，即确定协议元素的类型；语法规定通信双方彼此 之间”如何讲”，即确定协议元素的格式；变换规则用以规定通信双方彼此之间的 ”应答关系”，即确定通信过程中的状态变化，通常可用状态变化图来描述。 网络软件包括通信支撑平台软件、网络服务支撑平台软件、网络应用支撑平 台软件、网络应用系统、网络管理系统以及用于特殊网络站点的软件等。从网络 体系结构模型不难看出，通信软件和各层网络协议软件是这些网络软件的基础和 主体。 通信软件是用以监督和控制通信工作的软件。它除了作为计算机网络软件的 基础组成部分外，还可用作计算机与自带终端或附属计算机之间实现通信的软 件。通信软件通常由线路缓冲区管理程序、线路控制程序以及报文管理程序组成。 报文管理程序通常由接收、发送、收发记录、差错控制、开始和终了5 个部分组 成。 网络协议软件是网络软件的重要组成部分。按网络所采用的协议层次模型( 如 i s o 建议的开放系统互连基本参考模型) 组织而成。除物理层外，其余各层协议 大都由软件实现。每层协议软件通常由一个或多个进程组成，其主要任务是完成 相应层协议所规定的功能，以及与上、下层的接口功能。 网络应用系统则是根据网络的组建目的和业务的发展情况，构建在上述通信 软件和网络协议软件之上的。其任务是实现网络总体规划所规定的各项业务，提 供网络服务和资源共享。 2 2 传统网络协议软件的实现 2 2 1 协议和分层 自从计算机网络面世以来，它不断地促进着社会的发展，而且人类对计算机 网络的依赖与需求都愈演愈烈，所以许许多多的计算机厂商都建立了自己一套与 众不同的网络协议体系，然后配套一系列相对应的计算机网络硬件设各来完成计 算机的连网需求，而且它们之间并不能通用。这样造成了如果你选择了一个厂商 的网络产品，就被捆绑在这个厂商上，不得不“从而终”，这显然降低了整个 网络系统的可扩展性，甚至妨碍了计算机网络的更一步发展。 为此，国际标准化组织( i s o 、i n t e r n a t i o n a ls t a n d a r do r g a n i z a t i o n ) 在 1 9 7 9 年建立了一个专门的分委员会来研究和制定一种开放的、公开的、标准化了 的网络结构模型，以期用它来实现计算机网络之间相互联接与沟通。”开放系统 互连( o s i ) ”基本参考模型就是由此建立的。它由物理层、数据链路层、网络层、 运输层、会话层、表示层和应用层等7 层组成。就其整体功能来说，可以把o s i 网络体系模型划分为通信支撑平台和网络服务支撑平台两部分。通信支撑平台由 o s i 底4 层( 即物理层、数据链路层、网络层和运输层) 组成，其主要功能是向 高层提供与通信子网特性无关的、可靠的、端到端的数据通信功能，用于实现开 放系统之间的互连与互通。网络服务支撑平台由o s i 高3 层( 即会话层、表示层 和应用层) 组成，其主要功能是向应用进程提供访问o s i 环境的服务，用于实现 开放系统之间的互操作。应用层又进一步分成公共应用服务元素和特定应用服务 元素两个子层。前者提供与应用性质无关的通用服务，包括联系控制服务元素、 托付与恢复、可靠传送服务元素、远地操作服务元素等；后者提供满足特定应用 要求的各种能力，包括报文处理系统、文卷传送、存取与操作、虚拟终端、作业 传送与操作、远地数据库访问等。 当实现层次化的协议系统时，通常称这些协议软件的集合为“协议栈” 1 。 一种最直接的实现方式为：应用程序和物理网络之间的输出报文数据必须经过协 议栈的每一层，与此类似，输入数据同样如此。协议栈中的某一层可能支持不止 一种协议，比如o s i 的第四层至少包含两种传输层协议：t c p 和u d p 。 2 2 2 报文处理过程 两络协议软件的核心工作是对从网络上收到的报文进行系列的计算和处 理，然后根据一定的规则向协议栈的上层投递或者向下层进行转发。网络协议软 件涉及到的报文处理过程可以归纳为如下几类 1 ： 网络地址查询和报文转发 错误检测和恢复 报文分片( 段) 和重组 协议多路分解 报文分类 报文队列缓冲和丢弃 报文调度 报文认证和私密性 网络流量测量和整流 以上除了最后两类涉及到安全和具体网络业务的报文处理，其他都是 i n t e r n e t 上主要的报文处理操作。网络地址查询和报文转发是路由器最重要的报 文处理任务，可以说查询和转发的直接影响到i n t e r n e t 的运行和整体性能。 2 2 3 作为系统内核的网络协议软件 传统的网络协议软件通常作为操作系统内核的一部分实现。这样做有以下好 处 1 ： 操作系统通过对系统硬件和体系结构的抽象，屏蔽了底层细节，使得开发和 调试网络协议软件的效率较高。 设计者可以根据需求将网络协议软件分成两部分：要求较高报文处理速率的 可以作为内核的一部分实现，而对性能要求不高的那一部分可以作为应用程 序实现。 网络协议软件成为操作系统的一部分后即可通过导出编程接口被上层应用程 序重用。 网络协议软件通常依赖软件中断进行运作。软件中断一般是c p u 的一个特殊 指令，它的优先级比应用程序高，但同时又比硬件中断低，也就是说，只有当前 没有发生硬件中断的情况下才有可能执行软件中断服务例程。报文处理过程由软 件中断触发。通用处理器架构上的传统网络协议软件通常还必须通过网卡( n i c ) 硬件获取网络上的报文，操作系统使用硬件中断和网卡通信，网卡驱动程序( 也 是操作系统的一部分) 将接收到的报文写入主存。由于报文处理延迟的存在，内 核会维护一个报文队列，未来得及处理的报文会暂时存放在队列中等待软件中断 的到来。 2 3 传统网络协议软件实例分析 2 3 1 l i n u x 的i p 协议栈 l i n u x 作为开放源代码的操作系统内核被广泛应用在通用处理器，嵌入式 处理器和网络路由器系统上。l i n u x 的网络协议栈 2 借鉴了u n i x ，是目前典型 网络协议软件。它的i p 协议栈实现了i p 报文的路由查找和存储转发。 l i n u x 内核的网络协议栈基于层次化设计，共分为三层：最底层的驱动程序构成 数据链路层软件；往上是网络层，负责数据包的转发以及向上一层即传输层进行 投递；传输层支持t c p 协议和u d p 协议，分别用于有连接和无连接的应用程序。 对于i p v 4 协议栈来说，需要从驱动程序获得分组，进行i p v 4 有效性检查，查询 路由表，根据查询结果向下一跳( n e x th o p ) 转发或者向传输层投递，i p v 4 协议栈 的调用关系如图2 1 所示： li p l o c a l d e l i v e r y 传输层 it 意e 孟x i ti 。 网络层 i j pr o u t e i n p t j t s l n l i p _ o u t p u t ，7 7 if i p _ r _ o u t e _ i a p u t巾。皂砌l ? f i。f 瞧衙w 4 o ：一。f tl 上 i n e t f x a c t 湎l i h a r ds t a r t _ 一l 数据链路层( 驱动程序) r 、n 图2 一l l i n u x p v 4 协议栈调用关系 如上图所示，驱动程序接收到分组后，调用k m a l l o c 生成一个s k b u f f 实例， 作为分组句柄保存相关信息以及指向实际分组数据的指针，并将其置入队列。为 了快速响应中断，这部分代码会尽量快执行，而网络层的处理则由软件中断 ( n e t r x a c t i o n ) 触发。i p _ r c v 为网络层的入口，其后所有的分组信息都可从 s kb u f f 指针得到。i p r o u t e i n p u t 是路由查询入口，如果路由缓存查询失败， 则会调用i p _ r o u t e i n p u t s l o w 完成路由信息的慢速查找。根据i p r o u t e i n p u t 对s k b u f f 一 d s t 一 i n p u t 函数指针的修改，控制会转到i p l o c a l d e l i v e r 或者 i p f o r w a r d 。如果转到i p l o c a l d e l i v e r ，则最终交给传输层处理；如果是转到 i p f o r w a r d ，那么分组会通过i p o u t p u t 发送出去，最终由d e v q u e u e x m i t 调用 q d i s c r u n 进行分组调度，其中会在设备可传送数据时调用链路层发送函数 h a r d _ s t a r t x m i t 完成分组发送任务。s k b u f f 分组旬柄则在发送成功后内核处 理中断时删除。 综上所述，l i n u x 的i p v 4 协议栈主要由四部分组成：分组接收，查询路由， 分组调度，分组发送。虽然它们通过函数指针动态调用，但对于特定的i p v 4 分 组，有确定的函数调用关系，模块之间的通信通过指向分组旬柄的指针实现。 2 3 2 u i p 协议栈 u i p 协议栈 3 是轻量级的t c p 实现，它被广泛地应用在嵌入式处理器和单片 机系统上，这些处理器一般主频较低，而且通常不支持虚拟内存和保护，所以u ip 协议栈的实现特别简单以便于优化。 正如其他t c p i p 协议的实现，u i p 也遵循分层的原则。每一个协议都作为一 个模块来实现，提供一些与其他协议的接口函数。尽管各层分开实现，但为了同 时提高处理速度和内存利用两方面的性能，一些层在设计时违背这一原则。例如： 当检验一接收到的t c p 段( s e g m e n t ) 的校验和( c h e c k s u m ) 和分解t c p 段时， 源和目的i p 地址必须被告知t c p 模块。u i p 实现时不是通过函数调用把i p 地址 传递给t c p ，而是t c p 模块通过获取i p 报头的结构进而自己提取这一信息。 u i p 协议栈通过把系统划分成为不同的过程的方法进行描述。用于实现通讯 协议的过程模型使每个协议作为孤立的过程运行。 u i p 所使用的过程模型是：把所有协议封装到一个单一的过程中，从而与操 作系统内核分开，甚至可以在没有操作系统的环境中运行。应用程序也驻留在u i p 处理过程中，或者在单独的过程中。t c p i p 栈和应用程序之间的通信可以通过 函数调用实现。 u i p 仅实现了i p 协议的基本功能，由于它运行在慢速处理器上，因此不支持 i p 报文的转发。在接收到i p 报文后，通过检查类型字段，直接递交给u d p 或者 t c p 协议代码处理。u i p 也提供应用程序编程接口，但和一般的b s ds o c k e t 接口 不同，为了实现的简单和高效，u l p 直接在传输层代码中调用应用程序的回调函 数。而应用程序则以事件驱动的方式编写代码响应当前的连接状态。之所以这样 做，是因为u i p 面向的系统一般不存在m m u 部件，同时上层应用程序通常会固化 在r o m 中，因此应用程序的安全和隔离不再是问题。 u i p 的t c p 协议处理完全按照t c p 的状态机进行。当系统接收到报文后， u i p _ p r o c e s s 函数作为整个t c p 协议的入口被调用。全局变量u i pb u f 保存了当 前处理的报文数据，u i p l e n 为报文长度。在t c p 状态机处理过程中，需要发送 的报文数据赢接覆盖u i p b u f ，当u i p - p r o c e s s 调用结束时，系统检查u i p是_len 否为0 ，如果不是，则直接将u i p _ b u f 通过网卡驱动程序发送出去。 传统网络协议软件的优化 3 2 网络应用的发展趋势 当i n t e r n e t 还处于比较小和原始的阶段时，主要使用者是研究人员。当时 网络提供的主要“服务”是在两个特定的主机间点到点连接。当i n t e r n e t 从一 个开放的研究网络转到商业、银行业、电信业和个人通信的基础设施后，并且随 着其规模的急剧扩大，需要开发和部署更多新的服务，并且也需要路由器用新的 方式来转发和处理报文。这些服务包括： 防火墙：防火墙服务用来阻止网络间报文流。阻止的方式从最简单的，比如 丢弃所有某一主机的报文流，到比较复杂的，比如对电子邮件进行病毒扫描 等。路由器能快速过滤出不需要的报文的一个好处是可以防止“拒绝服务攻 击”( d o s ) 。在防火墙应用中，路由器需要对报文进行模式扫描。 入侵检测：入侵检测服务通过监视和分析报文流量中的模式和特点来判断系 统是否正遭受攻击。路由器可以提供报文流监视和分析等功能。 网络地址翻译( n a t ) ：因为i p 可用地址的限制，n a t 被用来使多个内部网 络中的设备共用一个i n t e r n e t 地址。提供n a t 服务的路由器需要对从内网 外出的报文修改源地址，对进入内网的报文修改目的地址。 商用服务器：为了支持并发访问和容错，i n t e r n e t 上的商用站点通常使用一 个具有负载均衡功能的前端路由器来动态的将访问分布到一组服务器上。 覆盖网络、隧道：v p n 是覆盖网络( o v e r l a yn e t w o r k ) 的一个例子。当低价 格的i n t e r n e t 服务普及以后，公司开始用加密的隧道建立虚拟专用网络 ( v p n ) ，将其各个i n t e r n e t 上的主机连接在一起。在实现v p n 时，路由器 将整个i p 报文视为数据，先加密数据，然后将加密后的数据封装在一个新 的报文中。这个“外部”报文通过i n t e r n e t 到达这个v p n 另一台路由器， 它将报文解开取出数据并解密，然后再传送到处于本地子网的真正目的主机。 转换编码的媒体网关：如今连接到i n t e r n e t 的设备包括移动电话、个人数 字助理( p d a ) 等设备，市场需要能有效为这些设备提供基于w e b 的内容服 务。转换编码媒体网关将高带宽、高分辨率的数据流转换成低带宽、低分辨 率的数据流，从而使数据流调整到适应终端设备的速率，这样能有效的减少 延迟和增加传输带宽的有效性。 服务质量( o o s ) ：服务质量为报文引入了优先级。在传统路由器中报文独立 的以基于接口的先入先出( f i f o ) 和尽力而为( b e s te f f o r t ) 的方式处理。 但实际应用中，有些报文的重要性比另一些报文要高，这就需要将报文得到 的服务区分开来。将服务区分开来还有利于提高i n t e r n e t 服务提供商的收 入。 这些服务的需求造成的结果是路由器： 1 ) 需要做出更复杂的转发决定，而不仅仅是根据报文的目的地址来转发报文： 2 ) 需要对报文做更复杂的处理，而不仅仅是i p ； 3 ) 需要对服务做出区分，而不仅仅是做尽力而为的转发。 路由器上的网络协议软件作为i n t e r n e t 的数据转发引擎，必须在完成以上服 务的同时尽量提高性能和效率。本章讨论在现有的通用处理器架构上如何对网络 协议软件进行优化。 3 3 基于编程语言的优化 在较长一段时间里，学术界比较关注哪种编程语言更适合网络协议软件的开 发，以及编译器的优化。由于网络协议可以很自然得使用状态变换图来表示，因 此，有些学者提出基于自动机语言的网络协议软件优化技术。 3 3 1 传统网络协议软件的性能瓶颈 评价网络协议软件的性能主要有两个指标：报文处理延迟和网络吞吐率。一 般来说，通用处理器的存储体系层次主要是影响了网络吞吐率，因为报文的接收 和发送都必须借助主存。但l a r r yl p e t e r s o n 发现存储系统同样也是限制报文 处理延迟的一个重要因素 4 。通过对r i s c 处理器上的t c p 和r p c 协议的研究发 现，提高指令c a c h e 的有效性能够显著减少报文处理开销。同时，更少的访存等 待时间也有助与提高处理速度。 协议层集成技术( i n t e g r a t i n gp r o t o c o ll a y e r s ) 则对提高网络吞吐率更为 有效 5 。通过将协议分层调用转变为流水线方式，可以更有效地访问报文数据。 该技术不仅能够提高传统网络协议软件的性能，而且能较大程度的保留协议栈分 层本身的模块特性。 需要指出的是，基于编程语言的优化很大程度上都利用了以上提到的两项优 化技术。 3 3 2 m o r p h e u s 协议开发框架 m a r kb e r ta b b o t t 提出的m o r p h e u s 协议开发框架从编程语言的角度定义了 协议的抽象语义 6 。m o r p h e u s 在以下方面帮助协议开发： 提供高层的抽象，使得开发者摆脱低级的设计工作，而专注与协议的内容。 统一的协议接口使得模块化成为可能，从而可以进行功能分解和组合重用。 m o r p h e u s 的c 风格的语言具有面向对象的特征，协议模型划分成状态( s t a t e ) 和动作( a c t i o n ) 。每一个动作只操作在某中状态上。面向对象语言的特征使协 议开发的模块性更强。 3 3 3 h i p p c o 协议编译器 c l a u d ec a s t e l l u c c i a 提出基于e s t e l l e 语言的自动协议栈优化编译器 h i p p c o 7 。h i p p c o 接受使用e s t e l l e 语言编写的网络协议抽象表述，并且生成 c 语言的实现。它使用以下技术使得协议栈编译器能够产生高效而简介的代码： 1 ) 使用修改的e s t e l l e 编译器产生一个完整的协议自动机，而不是几个独立的 自动机模块，这类似与传统编译中的i n l i n i n g 技术。 2 ) 协议优化在自动机层面上进行，比如状态分支的修改等。 h i p p c o 的协议开发流程如下： c o m m m r s l c a t t o n s t a c k s p “礴n o n 图3 - 1 h i p p c o 的协议开发流程 传统的e s t e r e l 语言 8 编写的协议规格和设计模块通过抽象的异步通信管 道连接，并且实现为独立的进程，通过模拟运行。但h i p p c 0 利用语义，控制和 数据相关性将其这些异步模块编译成一个完整的自动机。这使得自动机可以作为 个进程运行在通用处理器上，从而使得上下文切换的开销最小。 在获得协议栈的自动机后，h i p p c o 通过用户指定的各个状态的运行时执行概 率通过数学方法获得一条关键路径( c o m m o np a t h ) ，其后的优化则完全针对这条 关键路径进行。除了和自动机有关的状态最小化操作，h i p p c o 还利用执行概率信 息将状态检测的i f 语句进行重组，使得最有可能被执行到的分支被提前检测， 从而提高整体运行性能。 3 3 4 协议的指令级调度优化 这种优化技术由s t e f a nl e u e 提出 9 。通过给出一个协议的抽象实现( 也是 通过自动机描述的语言) ，利用和h i p p c o 类似的关键路径提取方法，构造出关键 路径无环图( 假定自动机描述不产生环) ，以后所有的优化都针对该关键路径进 行。 使用基本的编译技术，对该关键路径图进行数据相关性分析，将有相关性的 节点连接，从而得到一个标注过的图。此时，所有的可并行操作都已经产生。 编译器构造处理器可用功能单元表，使用处理器中的动态调度类似的算法， 从而将协议栈的操作指令并行化。 该方法显然并不适合复杂的通用处理器，因此更多可能应用在嵌入式处理器 h 。 3 4 c i i c k 路由器软件模型 为方便构造可灵活配置的路由器系统，m i t 的计算机实验室提出了c 1 i c k 路 由器软件模型 1 0 。 c l i c k 路由器软件是由多个报文处理模块( c l i c k 中定义为e l e m e n t ) 组成的。 单个的模块实现简单的路由功能，比如报文分类，队列缓存，调度，以及和网络 接口设备通信。另外有一个c 1 i c k 路由软件配置指导各个e l e m e n t 的交互机制。 该配置是一个由e l e m e n t 作为顶点，报文流动路径为边的图。c l i c k 定义了两种 e l e m e n t 之间通信的操作原语：p u s h 和p u l1 。使用p u s h 连接的两个e l e m e n t 使 得报文从起始e l e m e n t 传递到终结e l e m e n t ，而p u l l 则正好相反。p u s h 和p u i i 原语使得报文处理模块问的通信变得简洁，可以让开发者专注于协议的细节。 c 1 i c k 路由软件的e l e m e n t 使用c + + 语言开发，p u s h 和p u l l 原语被转换成 一个虚函数调用，报文的转移通过指针的传递完成。 c l i c k 更多的关注于路由器软件的可扩展性和可配置性上，以e l e m e n t 为模 块进行组装说明可以通过实现较小的报文处理单元构造可用的路由器软件是完 全可行的。 3 5 小结 本章介绍了传统网络协议软件在通用处理器架构下的优化技术。需要指出的 是，网络系统的整体性能不仅和主机间通信有关，更和网络上的路由器有关。 随着网络传输技术的发展，特别是光纤传输技术的成熟，网络传输速度已经 从1 5 5 m b i t s ，6 2 2 1 b i t s 等中低端速率迅速攀升到2 5 g b i t s ，l o g b i t s 甚至 4 0 g b i t s 等的中高端速率。目前网络传输技术不再是主干网上的网络通信瓶颈， 而网络通信节点的报文处理能力已经成为影响整体网络性能的主要因素。 传统的网络协议软件经过优化可以运行在基于通用处理器的路由器系统上， 但是由于通用处理器的体系结构限制，无法充分利用计算隐藏访存延迟，为了更 好地适应高速网络，人们设计了网络处理器，但是传统网络协议软件的有限并行 性又制约了在网络处理器上的运用。 4 网络处理器的体系结构和软件 4 2 网络系统体系结构的发展 随着i n t e r n e t 带宽的不断增加和提供的服务越来越丰富，作为在网络中为 主机提供服务的节点网络系统的体系结构也在不断的发展。在 1 中， 作者总结了网络系统体系结构发展的历程： 第一代网络系统： 1 9 6 0 到1 9 7 0 年间i n t e r n e t 刚刚出现，同时代还出现了小型计算机系统。由于 小型计算机具有价格便宜、体积小和i 0 接口简单的特点，i n t e r n e t 的开发者 决定用小型计算机来开发路由器。当时的网络速度相对于c p u 速度来说低得多， 路由器也只需要做路由表的查找，而且当时的网络规模也比较小，所以用传统计 算机硬件开发的路由器足以胜任在i n t e r n e t 中转发报文的任务。在这样的硬件 上一般运行报文转发软件，这可以是一个具备报文转发功能的通用操作系统，所 有的协议处理任务都在主机c p u 上运行。如今，一些低端的路由器仍然采用这样 的结构。一般将这样的硬件体系结构称为通用处理器( g e n e r a lp u r p o s e p r o c e s s o r ，g p p ) ，并且将在通用硬件上运行专用的报文交换软件构成的网络系 统称为软件路由器( s o f tr o u t e r ) 。 第一代网络系统的特点是价格低，而且功能易于扩展，但主要的缺点就是处 理速度慢。因为网络系统通常有几个网络接口，随着网络带宽的显著提高，聚合 带宽的速度超过了c p u 的处理能力。网络系统的设计者意识到用传统体系结构来 处理报文有两个缺点：( 1 ) 网络接口和网络接口间的报文交换要通过c p u 控制在 总线上传递；( 2 ) 报文的处理都交给了c p u 。所以c p u 和总线构成了瓶颈，于是 提出第二代网络系统的体系结构。 第二代网络系统： 第二代网络系统的体系结构有两个重要的特点：( 1 ) 使用分散式的设计，在 网络接口上具有报文分类和转发的能力；( 2 ) 利用高速的互连机制，提供在网络 接口间的快速通道( f a s tp a t h ) 。它比第一代网络系统的体系结构具有更好的可 扩展性。因为每个网络接口都具有报文分类和转发的能力，每个网络接口可以并 行的处理，而且网络接口之间可以通过快速通道进行报文的快速转发，所以第二 代网络系统可以支持更多的网络接口。 在第二代网络系统中，通用c p u 用来管理和控制系统，提供网络系统的管理 界面。它运行路由软件进行路由选择和路由通告，它还要处理无法进行分类的异 常报文以及各种错误。网络接口中的分类和转发功能可以用应用专用电路( a s i c ) 实现，也可以采用嵌入式的r i s c 处理器来实现。快速通道一般指交换结构 ( s w i t c hf a b r i c s ) ，可以是交叉开关( c r o s sb a r ) 、多级交换网络或多端1 2 1 内 存。 第三代网络系统： 在第二代嘎络系统中，虽然通用c p u 只处理报文流量中的一部分报文，但随着聚 合带宽的增加，通用c p u 仍然构成瓶颈，所以设计者们又设计了第三代网络系统。 第三代网络系统继续将报文处理工作从通用c p u 上分担到网络接口上，在网络接 口上设计不同的硬件来处理协议的各个层次。 在第三代网络系统中，网络1 、2 层用标准的商用芯片来处理，a s i c 用来进 行基本的三层报文分类、处理以及在快速通道中转发报文，a s i c 还用来在交换 结构中进行流量控制和管理。嵌入式的处理器被用来进行第四层或者更高层的协 议处理，用嵌入式处理器可以使高层协议处理用软件来实现，获得一定的灵活性。 由于在每个网络接口中都设置了嵌入式处理器，况且需要高层处理的报文并不是 很多，所以速度是可以接受的。但随着网络带宽的进一步提高，嵌入式的处理器 又构成了瓶颈。到了9 0 年代中期，网络系统的设计者认为只有专用的集成电路 ( a s i c ) 才可以处理i n t e r n e t 骨干网的流量，所以工业界生产的高速路由器都 用a s i c 来构建。a s i c 提供了最高的速度，但是它也有很大的局限性，具体有以 下几点：开发费用高、开发周期长、很难模拟、修改起来昂贵和耗时、可重用性 差、没有致的开发框架、需要硬件专家开发。 这样，网络系统的设计者面临着一个两难的境地，嵌入式处理器无法处理高 速网络的报文，而a s i c 开发起来又是如此的困难。因此，网络处理器应运而生。 4 3 网络处理器的体系结构 在 1 中，作者对网络处理器下的定义是：网络处理器是一种专用的、可编程的 设备，它具有嵌入式r i s c 处理器的灵活性和低价格，同时具有a s i c 的速度， 网络处理器是设计网络系统的基本构造模块。 4 3 1 网络处理器体系结构特点 网络处理器是一个复杂的系统，每个网络处理器都是由传统处理器、专用硬 件和多个部件的组合。在 1 中，作者就总结出网络处理器的以下基本特征： 处理器层次：处理器层次指执行报文各个层次处理的各种硬件。它们包括不 可编程的硬件和可编程的处理器。在网络系统中的处理器层次从最底层到最 高层有专用硬件到通用的处理器，它们需要协同工作。在网络处理器中一般 具有：一个或多个嵌入式的r i s c 处理器用来进行高层的协议处理以及对系 统作整体的控制；一个或多个协处理器，它们被优化用于特殊的报文处理工 作：一个或多个i o 处理器，它们以线速对报文作输入输出处理。为了隐藏 访存延迟，i o 处理器往往支持多个线程。在后文中，i o 处理器、报文处 理器、报文引擎和微引擎都具有相同意思。 存储器层次：存储器层次允许网络处理器以合理的价格达到较高的存取速度。 虽然网络处理器支持多个层次的存储器，但如何使用它们由程序员来决定。 内部传输机制：因为网络处理器往往由多个独立的处理单元构成，所以它们 之间必须具有高速的传输机制。一般内部传输机制有：内部总线、硬件f i f o 、 传输寄存器和片上共享内存。 外部界面和通信机制：虽然网络处理器中包含了很多处理资源，但是它仍然 需要和网络系统中的其他部件进行连接。网络处理器的外部连接包括：标准 总线、存储器接口、直接i o 界面和交换结构接口。其中光互连论坛( o i f ) 制定了直接i o 接口的标准，称为s p i 一3 4 ，网络处理器论坛( n p f ) 制定了 交换结构的接口，称为c s i x 。 专用硬件：网络处理器中至少有两种专用硬件。第一种是用来提供多个处理 单元问控制、同步和协调功能的硬件。第二种是被用来执行某种报文处理任 务的硬件，它们通常是可配置的，执行诸如c r c 检验计算，h a s h 计算等任 务。 查询和通知机制：网络处理器必须支持对异步事件的处理，比如报文的到来， 定时器通知等。一般有两种机制。查询是处理器自己去检查状态位，然后决 定异步事件有没有发生；通知机制相当于中断，可以有硬件中断和软件中断。 并发执行的支持：网络处理器一个重要的特点就是可以支持多个层次上的并 发执行。所谓并发执行是指一个处理器上有多个执行线程，如果一个因为等 待外部事件而阻塞，可以切换到另一个线程去执行。在网络处理器中，嵌入 式处理器中的并发执行由操作系统支持，i o 处理器中的并发执行由硬件支 持。 硬件对编程的支持：网络处理器的硬件往往对编程都有一定的支持，虽然各 个厂家的网络处理器的实现不太相同，但基本分为两类：异步事件服务程序； 可相互通信的线程。 硬件和软件的分派机制：所谓分派机制是指怎样将工作分配到各个并行的硬 件上去执行。软件分派用于嵌入式的处理器中，硬件分派用于低层的i o 处 理器。 隐式或显示并行：网络处理器中的并行大致分为两类：隐式并仃。- 捌显不- - 升 z - 。 隐式并行将程序的并行执行交给硬件去决定，显示并行将并行问题交给程序 员决定，程序员必须在程序中明确的使用并行构造。 4 3 2 网络处理器的并行特性 网络处理器对报文处理的优化体现在开发报文处理的并行性上。在 11 中， 作者指出报文处理存在着三个层次的并行性： 分组级并行( p a c k e tl e v e lp a r a l l e l i s m ，简称p l p ) ：大部分网络应用都是 基于分组级( p a c k e tl e v e l ) 的，不同的分组一般经过类似的处理，分组间 般是独立的，这样分组可以由不同的服务员并行服务。然而这种处理也存在 一定的局限性，即当属于同一个流( f l o w ) 的分组经过不同服务员并行处理 后必须有一个分组的重组保序过程。虽然上层的t c p 等协议允许分组乱序， 但是为了减小在终端分组重组的时间一般还要保证分组的顺序。 分组内并行( i n t r ap a c k e tp a r a l l e l i s m ，简称i p p ) ：在对分组内部处理的 过程中，有些任务也是彼此独立的。这种思路类似于微处理器设计中的线程 级并行( t h r e a dl e v e lp a r a l l e l i s m ) 。例如，一个二层交换程序，源m a c 地 址的处理和目的b i a c 地址的查找是完全独立的，可以并行处理。同时还可引 入一些专用的硬件协处理器，以增加i p p 的并行效果。另外，增加一些专用 的处理指令也是提高i p p 效果的有效手段。 指令级并行( i n s t r u c t i o nl e v e lp a r a l l e l i s m ，简称i l p ) ：在网络处理 器内部通过特殊的硬件结构完成处理器指令的并行执行，比如v l i w 和超标 量技术。此外，有些处理器还使用了线程级并行( t h r e a dl e v e lp a r a l l e l i s m ) 技术。然而，经模拟研究表明，在一般非特定的整数科学计算应用中，i l p 是 非常有限的，因此现