1、IP路由器架构 主要参考文献1 James Aweya.IP Router Architectures:An Overview.Nortel Networks,1999.2 Kiran Nukesh Misra,et al.Study of Internet Router Architectures.May 2001.3 Yuji Kawamura,et al.Network Processing on an SPE Core in Cell Broadband Engine.2008.4 Badrinath Dorairajan,et al.TCP/IP Acceleration in Ce
2、ll-BE based platforms.July 2007.5 Junchang Wang,et al.Practice of Parallelizing Network Applications on Multi-core Architecture.June 2009.6 John Giacomoni,etc.FastForward for Efficient Pipeline Parallelism:A Cache-Optimized Concurrent Lock-Free Queue.In proceedings of PPoPP08.1.IP路由器的一般结构IP路由器的基本功能p
3、路由处理：n通过运行路由协议来学习网络的拓扑结构，建立并维护路由表。p包转发：nIP包检验（如版本号、头长度、头校验等）、目的IP地址解析及查表、包头修改（如TTL域修改、头校验生成）、IP包分片等。p特殊服务：n不属于核心路由的其它功能，包括数据包转换、封装、流量管理、认证、包过滤等。路由表查找p路由表查找一直以来是IP路由器的一个主要性能瓶颈。p最早的路由表查找方法是Radix树（改进的Patricia树）+路由cache。路由cache通常组织为一个哈希表，使用简单的精确匹配查找方法。p路由cache适用于网络边缘或企业网内部，但在核心路由器中效果不明显：n核心路由器见到的目的地址数量巨
4、大，可导致缓存溢出，或查找速度变慢。n频繁的路由更新使得cache中的路由信息很快失效。p基于软件的查找方法灵活性强，基于硬件的查找方法一般能以较低的代价获得较高的性能，但是缺乏灵活性。2.IP路由器架构的演变p第一代：基于总线和单处理器的架构p第二代：基于总线和多处理器的架构p第三代：基于交换结构和多处理器的架构p第四代：基于网络处理器的全分布处理架构第一代：基于总线和单处理器的架构n中央处理器必须处理流经路由器的所有包，导致严重的处理瓶颈。n数据包需要穿过总线两次，I/O总线成为限制路由器吞吐量的重要因素。第二代：基于总线和多处理器的架构（1）p将包转发功能、路由cache和包缓冲器分布到
5、各个NIC上：n减少总线拷贝次数n减轻CPU负担n减少查表时间p缺点：n吞吐量依赖于流量模式（路由cache命中率）。n高速情况下，主路由表很容易成为瓶颈。n共享总线仍是瓶颈。带路由cache的结构第二代：基于总线和多处理器的架构（2）使用多个并行的转发引擎n将转发功能从NIC中分离，由专门的转发引擎完成。n转发引擎包含自己的路由cache，只负责解析下一跳和处理包头。n包载荷总是直接在接口模块间传输，从不发送给转发引擎或路由处理器。n转发引擎并行地处理不同的分组头。第三代：基于交换结构和多处理器的架构p每个线卡包含一个或多个网络接口。p每个转发引擎包含一组转发表和路由cache，负责包头的处
6、理与转发。p线卡、转发引擎卡、控制卡通过交换结构连接。使用交换结构代替共享总线转发引擎的处理过程p第一阶段并行执行以下操作n基本的差错检查，确认包头来自一个IPv4数据报n确认包长和包头长度是合理的n确认IPv4头没有选项n计算路由cache的哈希索引值，获取路由信息n读下一个头p第二阶段n若cache不命中，搜索路由表，生成适合路由cache的路由形式；n检查TTL，更新TTL及头校验，确认包是否发给自己。p第三阶段n将TTL及头校验放入IP头，将更新后的IP头及从转发表中获得的链路层信息发送给输入线卡。使用转发数据库（FIB）代替路由cachep路由cache采用demand-cachin
7、g模式：n当目的地址不在cache中时，包转发变为基于软件的路由查找（慢路径）。n当网络拓扑频繁变化、流量模式高度随机时，网络流量主要通过主CPU转发（慢路径），而不是通过路由cache转发（快路径）。p若网络接口上存在大量并发的流，则硬件cache很难实现，只能用哈希表实现，而哈希查找的性能无法得到保证。p解决方案：在每个网络接口上用转发数据库（IP路由表的完整镜像）取代路由cache，彻底消除慢路径。基于交换的分布式路由处理架构p结合以上所有技术的一种分布式路由处理架构：n使用一个交换结构，连接所有的网络接口及主CPU。n每个网络接口提供包处理所需的处理能力和缓存空间，包含自己的FIB，各
8、处理部件可并行操作。n路由器的各种功能被划分成慢路径和快路径，慢路径在主CPU上完成，快路径在网络接口上完成。关键路径和非关键路径p关键路径（快路径）：n由时间关键的处理任务构成，与包转发直接相关的任务是时间关键任务。n关键路径的速度直接影响IP路由器的性能，大多数高速路由器用硬件实现快路径。n一般在网络接口中实现。p非关键路径（慢路径）：n由非时间关键的处理任务构成，与发送给路由器本身的包相关的处理任务是非时间关键任务，如ICMP协议、路由协议、网络管理协议等。n一般在CPU中实现。IP路由器慢路径上的功能分布式路由器结构中的功能划分分布式路由器结构的功能框图转发数据库共享存储路由器结构中的
9、IP包处理3.Case studypCisco 7500pCisco 10000 ESRpCisco ASR 10003.1 Cisco 7500pRSP执行以下任务n数据分组交换（使用Cisco Express Forwarding模式及标签交换获得高性能）n提供基本包转发之外的服务，如加密、压缩、访问控制、QoS、流量统计等n运行路由协议n其它维护功能，如网络管理。Cisco 7500 Route Switch ProcessorCisco 7500p每个VIP有自己的处理器，执行IP数据包交换和基本包转发之外的服务。pRSP处理其它重要任务，如路由协议、非IP流量、网络管理等。Cisco
10、 Versatile Interface Processor3.2 Cisco 10000 ESRp线卡：管理自己的接口类型，通过背板向PRE发送和接收数据包。pPRE：包括路由处理器RP和转发路径FP两个主要部分：nRP：运行路由协议，更新路由表，其它控制面功能。nFP：转发数据包。p使用点对点链路连接每一个PRE和每一块线卡，带宽高，故障隔离。转发路径处理器阵列p转发路径使用PXF（Parallel Express Forwarding）网络处理器获得高吞吐量。p每个PXF网络处理器由16个微码编程的处理器（eXpress Micro Controller，XMC）组成，每个处理器是一个专
11、为包处理而定制的独立的高性能处理器。p16个XMC链接成4条并行流水线，用于提高吞吐量。p每一个处理器及每一列处理器均分配独立的存储空间，用于优化存储访问。p一个路由器使用两个PXF，形成4条并行流水线（8级）。3.3 Cisco ASR10004.通用多核处理器与网络设备p通用多核处理器的出现为构建高性能的网络设备提供了一种新的可选方案：n通用多核处理器为线程级并行而优化，适合具有天然线程级并行特性的网络应用。n拥有越来越多的计算核和越来越大的cache空量，能够承担越来越复杂的包处理任务。n设计中已经考虑了适合网络处理的有用特性。4.1 IBM Cell BE p1个PPE：n作为通用微处
12、理器使用，双发射有序核心。p8个SPE：nSIMD指令集处理器，双发射，无缓存，有256KB本地存储器，通过DMA引擎在本地存储与主存之间传递数据与代码。n主要计算任务由SPE承担p内置存储控制器与总线接口控制器p高速EIB总线连接各主要部件指定一个SPE进行网络处理软件系统编程模型-同构模型编程模型-异构模型Cell加速方案p卸载计算密集的操作:n卸载主机操作系统网络协议栈中的计算密集操作n卸载用户空间协议栈中的计算密集操作。p加速特定的数据路径。卸载主机栈的计算密集操作加速特定的数据路径p只加速某些延迟敏感的、或对网络利用率贡献较大的应用。p主机栈（PPE）负责控制面处理以及其它应用的数据
13、路径。pPPE上的网卡驱动程序将收到的包发送给“RX-Classifier”，确定由PPE还是SPE路径处理。pRX-Classifier可以由PPE承担，也可以指定一个SPE负责。p一种启发式的SPE分配方案：n1个SPE处理TCP，另1个专门的SPE为TCP处理IP流量n1个SPE处理UDP及其相关的IP流量n可以使用SPE组，以处理更多的连接或UDP端口。一种可能的数据路径加速方案多处理器配置4.2 基于Intel多核架构的网络处理平台p利用Intel的通用多核处理器建立高速网络处理平台，实现L2-L7层处理。p通过在多核平台上并行化已有的串行网络程序来达到利用多核结构的目的，而不是完全
14、从头开始编写一个并行的网络程序。p实验平台为使用2片Intel Xeon 5410（四核处理器）的Dell PowerEdge 2900服务器，目前实际上只使用了4个核。Intel Nehalem 8核处理器内部结构p8个计算核p每个核自带256KB L2 cache，8个核共享一个L3 cachep内置内存控制器p微内核与内存控制器之间使用crossbar交叉互联p内置QPI接口，允许与其它处理器进行高速点对点连接多个处理器互联pNehalem-EX 的最高配置是 4 芯 32 核。p每一颗 Nehalem-EX 芯片都与其他 3 颗芯由QuickPath 点对点相联。实验平台p每个Xeon
15、 5410有4个核p每个核自带32KB L1数据缓存p每2个核共享一个6MB L2数据缓存Dell PowerEdge 2900服务器内部结构三种基本的并行结构p任务并行n在相对较长的时间段内并行地执行多个独立的任务（如应用、TCP连接等），这是最基本的并行形式。n取决于是否存在独立的任务。p数据并行n通过并行地处理多个独立的数据单元来并行化一个任务。n取决于是否存在独立的数据单元。p流水线并行n通过将一个任务划分成一系列串行的子任务来并行化一个任务，每个子任务运行在一个核上。n许多应用有顺序处理的要求，从而无法使用任务并行或数据并行，但许多这样的应用都可以用流水线并行来并行化。n要求子任务之
16、间相对独立。流水线并行的例子：网络帧处理p网络帧处理提供了流水线并行的一个很好的应用示例。p10Gb/s以太网要求支持1,488,095fps的处理速度，这意味着每672ns必须处理完一个帧。p可将每个应用划分成三个处理阶段：输入处理、应用处理和输出处理。每个阶段分配给一个处理核，形成一个三级流水线，每个阶段的处理时间最多为672ns。p在流水线结构中，核与核之间的通信开销是制约流水线性能的主要因素：n在一个基于2.0GHz AMD Opteron的系统上，基于锁机制实现的队列，每次入队或出队操作至少要消耗200ns时间。设计要点pIP核运用connection-affinity原则将数据包分
17、发给某个APP核去处理。Connection-affinity是指将属于同一个TCP连接的包指派给同一个核，以确保数据的局部性。p4个核组织成一个2级功能流水线，第一级（IP）负责获取包，第二级（APP）负责其余的处理，使用一个先入先出队列（FIFO）连接相邻两个级。设计要点（续）p设计了一种并发无锁的FIFO队列，以cache line为单位汇聚读/写操作，实现相邻核之间的高效通信。p基于对每阶段处理时间的精确统计，将包处理任务均衡地映射到各个流水线级上。p尽可能消除数据路径上的锁操作。比如，采用预分配缓冲区的方法去除malloc()操作（从而内含的锁操作）。p一个将串行网络程序转换成并行程
18、序的并行编译器。任务映射 (a)(b)下一步的工作p在并行网络平台上添加更多的L7应用。p研究处理器之间的高效通信机制。4.3 Cache优化的并发无锁队列p基于锁的队列存在两个主要的开销：n在算法层面上，锁操作将生产者和消费者耦合在一起。n与cache一致多处理器结构的相互作用。Lamport CLF队列的实现pLamport已经证明，在顺序一致性模型下，单生产者-单消费者队列的锁可以去掉，从而形成一个并发无锁（CLF）队列。p在算法层面上消除了生产者和消费者之间的耦合，不要求有显式的同步操作，也消除了在锁的实现过程中的隐式同步。p比基于锁的队列提高了33%的性能。p控制数据（head和ta
19、il）仍然共享，在目前的cache一致性系统中仍会导致cache颠簸。FastForward CLF Queuep解除head和tail之间的耦合：n使用NULL表示空单元，通过检查head或tail指向的单元是否为空来判断队列状态，避免直接比较head和tail。nhead和tail分别是生产者和消费者的私有变量，一直保存在各自的cache中。Temporal Slippingp延迟启动消费者直至生产者已将足够多的数据存入队列，以使生产者和消费者操作在不同的cache行上，避免cache颠簸。Slip maintenancep以上算法在初始化时运行。p如果阶段的处理时间呈现非零均值的波动，或
20、者具有非均衡的阶段，则需要周期性地运行该算法进行调整。性能提高p在一个使用两片AMD Opteron 2218（2.66GHz，双核）的系统上，队列操作的开销为28.531ns，可获得3.75倍的性能提高。p 经常不断地学习,你就什么都知道。你知道得越多,你就越有力量p Study Constantly,And You Will Know Everything.The More You Know,The More Powerful You Will Be写在最后谢谢大家荣幸这一路，与你同行ItS An Honor To Walk With You All The Way演讲人：XXXXXX 时 间：XX年XX月XX日
