IP路由器

主要内容 IP路由器架构的演变 IP路由查找 数据包分类

IP路由器架构的演变

1.1 IP路由器的一般结构

IP路由器的基本功能 路由处理： 包转发： 特殊服务： 通过运行路由协议来学习网络的拓扑结构，建立并维护路由表。 IP包检验（如版本号、头长度、头校验等）、目的IP地址解析及查表、包头修改（如TTL域修改、头校验生成）、IP包分片等。 特殊服务： 不属于核心路由的其它功能，包括数据包转换、封装、流量管理、认证、包过滤等。

路由表查找 最早的路由表查找方法采用二元查找树+路由cache，路由cache存放最近使用过的<目的IP地址，下一跳>，通常组织成一个哈希表，使用简单的精确匹配查找方法。 使用路由cache的前提是网络流量具有足够的局部性，从而cache的命中率足够高。 实践发现，路由cache在因特网边缘比较有效，在因特网核心并不奏效： 核心路由器见到的目的地址数量巨大，可导致缓存溢出或查找速度变慢； 频繁的路由更新使得cache中的路由信息很快失效。

二元查找树 将路由表中的地址前缀组织在一棵二元查找树中； 查找时使用地址前缀的每一位决定树的分支； 与地址前缀对应的节点包含了转发信息； 查找算法的时间复杂度与地址长度成正比。

1.2 IP路由器架构的演变 第一代：基于总线和单处理器的架构（软件路由器） 中央处理器必须处理经过路由器的每个包，导致严重的处理瓶颈。 每个包需穿过总线两次，I/O总线成为限制路由器吞吐量的另一重要因素。 路由器的性能严重依赖于共享总线的吞吐量以及中央处理器的转发速度，不具有扩放性。

第二代：基于总线和多处理器的架构（1） 将包转发、路由cache和包缓存分布到各个NIC上： 缺点： 带路由cache的结构 减少总线拷贝次数 减轻CPU负担 减少查表时间 缺点： 吞吐量依赖于流量模式（路由cache命中率）。 高速情况下，主路由表很容易成为瓶颈。 共享总线仍是瓶颈。 带路由cache的结构

第二代：基于总线和多处理器的架构（2） 将转发功能从NIC中分离，由专门的转发引擎完成。 转发引擎包含自己的路由cache，只负责解析下一跳和处理包头。 包载荷总是直接在接口模块间传输，从不发送给转发引擎或主CPU（除非是以路由器为目的的包）。 多个转发引擎并行地处理不同的分组头。 优点：提高了路由器的端口密度。 缺点：共享总线仍然是瓶颈。 使用转发引擎的结构

第三代：基于交换的路由器架构 控制卡、多块线卡和转发引擎卡通过一个交换结构连接： 每个线卡包含一个或多个网络接口； 每个转发引擎卡包含一组转发表和路由cache，负责包头的处理与转发； 控制卡提供基本的管理功能，如路由表生成和链路管理。 使用交换结构代替共享总线

Crossbar交换结构 使用N×M 个交叉开关连接输入与输出端口； 控制器硬件处理端口竞争； 多个端口之间可以并行传输，集合吞吐率高。

使用转发数据库（FIB）代替路由cache 路由cache采用demand-caching模式： 当目的地址不在cache中时，包转发变为基于软件的路由查找； 当网络拓扑频繁变化（路由失效快）、流量模式高度随机（缓存的路由信息重用率低）时，网络流量主要通过主CPU而不是路由cache转发。 目前骨干路由器的一个接口上可能同时存在上千万条活跃的并发流，硬件cache很难实现，而软件哈希表的查找性能无法得到保证。 高度随机的流量模式和频繁的拓扑变化消除了从路由cache获得的任何好处，需要一种新的转发模式。 解决方案：在每个网络接口上用转发数据库（IP路由表的完整镜像）取代路由cache。

快路径和慢路径 分布式路由器的设计关键是快路径和慢路径的划分。 快路径（关键路径）： 慢路径（非关键路径）： 由时间关键的处理任务构成，与包转发直接相关的任务是时间关键任务，如IP包检查、目的地址解析和查表、TTL控制和头校验生成等。 快路径的速度直接影响IP路由器的性能，因此一般在网络接口上实现，大多数高速路由器用硬件实现快路径。 慢路径（非关键路径）： 由非时间关键的处理任务构成，与发送给路由器本身的包相关的处理任务是非时间关键任务，如ICMP包、路由协议包、网络管理消息等。 慢路径一般在CPU上实现。

快路径 or 慢路径？

分布式路由器结构中的功能划分

1.3 Case study Cisco 7500 RSP执行以下任务 数据包交换，使用FIB而不是路由缓存，称为CEF（Cisco Express Forwarding）交换模式。 提供基本包转发之外的服务，如加密、压缩、访问控制、QoS、流量统计等。 运行路由协议。 其它维护功能，如网络管理。 Cisco 7500 Route Switch Processor

Cisco 7500（续） 每个VIP有自己的处理器，执行IP数据包交换和基本包转发之外的服务。 RSP处理其它重要任务，如路由协议、非IP流量、网络管理等。 Cisco Versatile Interface Processor

Cisco 10000 ESR（边缘服务路由器） 线卡（8块）：管理自己的接口类型，通过背板向PRE发送和接收数据包。 PRE（主、备各一块）：包括路由处理器RP和转发路径FP两个主要部分： RP：运行路由协议，更新路由表，其它控制面功能。 FP：转发路径。 使用点对点链路连接每一个PRE和每一块线卡，带宽高，故障隔离。

转发路径 转发路径使用PXF（Parallel Express Forwarding）网络处理器获得高吞吐量。 每个PXF网络处理器由16个微码编程的处理器（eXpress Micro Controller，XMC）组成，每个处理器是一个专为包处理而定制的独立的高性能处理器。 16个XMC链接成4条并行流水线，用于提高吞吐量。 每一个处理器及每一列处理器均分配独立的存储空间，用于优化存储访问。 一个路由器使用两个PXF，形成4条并行流水线（8级）。

Cisco ASR1000

1.4 基于通用多核处理器的路由器 通用多核处理器的出现为构建高速路由器提供了一种新的可选方案： 通用多核处理器为线程级并行而优化，特别适合具有天然线程级并行特性的网络处理任务。 处理器的计算核越来越多，cache容量越来越大，能够承担越来越复杂的包处理任务。 设计中已经考虑了适合网络处理的有用特性。

（1）RouteBricks [3] 随着网络处理功能越来越复杂及各主要ISP竞相提供新的服务，可编程、可扩展的网络设备受到人们的关注。 功能扩展的困难在于要修改路由器数据面上的包处理过程，而目前高性能和可编程性常常不可兼得： 高端路由器依靠专用、封闭的硬件和软件来获得高速度，很难扩展、编程和实验。 软件路由器利用运行在通用平台上的软件来执行包处理任务，易于编程，但目前只适用于低速环境。

构建可扩展高速路由器的两种方法 从已有的高端专用设备入手，增强其可编程性： 专用设备开放有限的API，允许第三方修改/扩展设备中的软件部分，但这些修改通常不涉及核心包处理。 利用网络处理器加速时间关键的任务，具有较高程度的可编程性，但编程困难。 从软件路由器着手，提高其包处理速度： 开发容易：可使用熟悉的通用计算机硬件平台、操作系统和开发工具来开发网络设备。 扩展性好：数据面和控制面功能可以通过软件升级来修改，免去了开发者设计硬件的负担。 [4]采用商用的PC机硬件和操作系统来构建路由器，且要求性能与具有几十至几百个1Gbps或10Gbps端口的高端路由器相当。

RouteBricks的设计目标和挑战 设计目标： 路由器的功能分为包处理和包交换两个主要的任务，在当前的硬件路由器上， 一个N端口路由器，每个端口的线速为R bps。 路由器的功能分为包处理和包交换两个主要的任务，在当前的硬件路由器上， 包处理：典型地发生在线卡上，每块线卡处理一个或几个端口，线卡的处理速度为kR（k为端口数）。 包交换：通过一个交换结构和集中的包调度器实现，交换结构/包调度器必须以NR的速度交换包。 N和R可能很大，如最高端的核心路由器需支持最多4608个10Gbps端口，单台服务器不可能达到NR的处理和交换速度。

设计原则（1） 设计原则一： 这种架构的优点是扩放性非常好： 将路由器的功能并行化到多个服务器上，降低对单个服务器的性能要求，即设计一个集群路由器架构。 每个服务器承担传统路由器中线卡的功能，负责一个或几个端口的包处理，处理速度为kR。 采用分散式的包交换机制，路由器中不使用任何集中式组件，任一组件的运行速率不高于cR（c为2或3）。 这种架构的优点是扩放性非常好： 只需往集群中加入更多的服务器，就可以很容易地提高路由器的容量； 由于采用软件路由器，功能扩展也非常方便。

集群路由器架构图示

设计原则（2） 仅当单个服务器的性能能够提高到cR，集群路由器架构方案才是可行的，但目前的服务器远不能达到这个速度。 设计原则二： 在每个服务器内部，将路由器的功能分布到多条处理路径上来提高单台服务器的处理能力。

服务器架构 硬件：使用一个早期的Intel Nehalem服务器。 [4]使用一个早期的Intel Nehalem服务器，服务器使用了2个Nehalem处理器，每个处理器中包含4个2.8GHz的核和一个8MB的L3 cache，这个L3 cache被4个核共享。 每个处理器内部集成了一个内存控制器，通过存储总线连接到整个内存空间的一部分，因此这是一个NUMA结构。 2个处理器通过专门的点到点链路相互连接并连接到I/O Hub，I/O hub通过2个PCIe 1.1 x8插槽连接2块网卡，每块网卡包含2个10Gbps端口。 未来的服务器配置会包含更多的处理器、每个处理器中更多的核，以及4-8个 PCIe 2.0插槽。

服务器架构（续） 软件： 流量： 轮询模式下的Click/Linux 2.6.19，CPU轮询是否有包到达，而不是在包到来后被中断。 扩展了Linux 10Gbps以太网驱动程序。 流量： 服务器上安装了两块双端口10Gbps网卡，每块网卡可获得12.3Gbps的输入速率。 服务器最高数据输入速率为24.6Gbps。

充分利用服务器的并行性 用基于点到点连接的Nehalem 服务器代替基于共享总线结构的Xeon服务器，性能提高了2-3倍。

使用多队列网卡 在多核系统上，包输入/输出产生两个性能问题： 使用多队列网卡： 如何在核之间均衡负载？ 如何使系统I/O性能随核的数量线性增长？ 使用多队列网卡： 每个端口支持多个发送和接收队列，网卡对包的五元组进行哈希，根据哈希结果将包分到不同的队列，每个队列映射到一个CPU核。 扩展了支持多队列网卡的驱动程序。

批处理 在目前的操作系统中， [4]通过处理来减少开销： 数据包的元数据存放在skb buffer中，其中有一个指针指向数据包实际存放的位置。 CPU预先在内存中分配好以上数据结构，并将一个skb buffer的地址（包描述符）通知给网卡。 当有数据包到达网卡时，网卡将数据包及元数据通过DMA存放到指定位置，然后向CPU发送中断，返回包描述符。 [4]通过处理来减少开销： 网卡驱动的批处理：驱动程序每次传输kn个包描述符，减少在PCIe及I/O总线上产生的事务。 轮询驱动的批处理：Click每次轮询可最多接收kp个包。

性能改进

（2）PacketShader[4] 硬件配置 2片Intel Nehalem 四核CPU 2块NVIDIA GTX480显卡 4块双端口10GbE网卡（共8个10G端口）

软件配置 64-bit Ubuntu Linux 9.04 with kernel 2.6.28.10 优化的10GbE驱动程序（I/O engine） CUDA SDK 3.0

Linux网络栈的开销

I/O Engine的优化措施（1） 用静态预分配代替动态缓冲区分配，有效减小了： 包缓冲区的分配和释放开销 DMA映射开销 精简了skb数据结构，skb的大小从208字节减为8字节。 将包缓冲区的大小设置为2KB，且起始地址2KB边界对齐。

I/O engine的驱动结构

I/O Engine的优化措施（2） 批处理： 预取： 使用轮询代替传统中断模式或NAPI模式。 硬件批处理：网卡使用一个PCI事务传输多个包描述符，充分利用PCI总线带宽。 驱动层批处理：驱动程序接收或发送了多个包之后再写网卡寄存器，以平摊访问网卡寄存器的高额开销。 应用层批处理：应用程序每次系统调用接收多个数据包，以平摊系统调用的开销。 预取： 驱动程序预取下一个包的描述符和包数据到CPU cache，消除由DMA引起的强制缓存缺失。 采用预取隐藏数据包拷贝延迟。 使用轮询代替传统中断模式或NAPI模式。

批处理获得的性能提升

I/O engine的多核优化 使用多队列网卡 消除和网卡相关的全局统计变量 NUMA感知的数据分布与I/O： 将所有的数据结构分配在处理它们的节点上 消除由RSS引起的跨节点I/O

I/O engine性能

PacketShader软件架构

用户级程序 为什么PacketShader运行在用户模式？ 用户模式的性能问题及PacketShader的解决方案： 开发容易 可靠性好 可与第三方库无缝集成 用户模式的性能问题及PacketShader的解决方案： 系统调用开销：使用批处理分摊开销。 队列与核的映射：给每个队列指定一个虚拟接口，绑定到核上。 接收端活锁：用轮询加中断的方式消除接收端活锁。

用户级包I/O接口

PacketShader的工作流程 pre-shading： shading： Post-shading： 工作线程从RX队列中取出一个chunk，丢弃异常的包，过滤出需要GPU处理的包，建立数据结构，将数据放入主线程的输入队列。 shading： 主线程将输入数据从主机内存传输到GPU显存，启动GPU程序，将结果从GPU显存传回主机内存，将结果放到工作线程的输出队列。 Post-shading： 工作线程从其输出队列中取出结果，根据处理结果对chunk中的包进行处理，将处理过的包放入目标端口的发送队列。

PacketShader的工作流程

优化措施（1） Chunk pipelining：工作线程执行完一个chunk的pre-shading，将输入数据传给主线程后，立即取下一个chunk处理，直到主线程返回第一个chunk的处理结果。

优化措施（2） Gather/Scatter：主线程从输入队列中取出多个chunk，流水地执行数据拷贝（gather），启动GPU一次性处理这些数据，将结果分发到相应工作线程的输出队列（scatter）。

优化措施（3） Concurrent copy and execution：在执行一个GPU内核函数时在主存和显存之间拷贝数据。

IPv4转发性能

IPv4转发性能

IPSec网关性能

IP路由查找

地址前缀与地址聚合 IP编址方案最初使用一个简单的二层结构：上层为网络，下层为主机。 这个分层结构反映在IP地址上，就是IP地址由两个部分组成：网络地址部分（地址前缀）和主机地址部分。 地址前缀的两种表示方法： 不大于32比特的比特串跟上一个*，比如：1000001001010110* 带点十进制表示加上地址前缀长度，比如：130.86/16 地址聚合（address aggregation）：连接到同一个网络的所有主机在转发表中对应一个入口，即允许使用前缀来表示一组地址。

转发表举例

基于类的编址方案 地址空间利用率低，地址短缺问题日益突显。 核心路由器的转发表规模急剧扩大，导致查表时间及内存需求增加。

无类域间路由（CIDR）编址方案 摒弃传统的基于类的地址分配方式，允许使用任意长度的地址前缀，有效提高地址空间的利用率。 允许任意地、递归地进行地址聚合，减少转发表中的入口数目，有效解决路由表爆炸的问题。

地址聚合的例子（1）

地址聚合的例子（2） 路由器的地址查找问题就是要从转发表中查找匹配数据包目的地址的最长的地址前缀。

基于类的地址查找 转发表中的前缀被组织成三张表（分别对应A、B、C三类地址前缀），地址查找就是在对应的转发表中进行精确匹配查找。 查找过程如下： 根据IP地址的前几位得到该地址所属的地址类别 根据地址类别提取目的地址中的网络地址部分 查找相应的哈希表或进行二分查找

最长地址前缀匹配的困难 转发表中的目的前缀具有任意的长度，并且不再对应地址的网络部分，因而前缀长度无法从目的地址本身获得。 转发表查找要求采用最长前缀匹配查找而不是精确匹配查找。 地址查找在数值和长度两个维度上进行。

地址查找算法的评价指标 查找速度 存储空间 预处理和更新速度 算法实现的灵活性（同时具有硬件和软件实现方式） 算法的可扩展性（路由表规模，IPv6）

二进制Trie树 采用基于树的数据结构，通过前缀中每一位的值来决定树的分支。 处于第L层的节点代表了一个地址前L比特均相同的地址空间，这L个比特串就是由从根节点到这个节点路径上的L比特组成。 与地址前缀对应的节点包含了转发信息。

Trie树代表的地址空间结构

Trie树的查找 从根节点开始每次一位地查找： 以上查找方法为基于长度的顺序前缀查找，每搜索一步，搜索空间就缩减一半。 当地址中的相应位为0时选择左分支，为1时选择右分支。 当遇到那些对应地址前缀的中间节点时，将此地址前缀记录为目前为止找到的最长地址前缀。 当不再有分支可以选择时搜索过程结束，此时被记录的最长地址前缀就是查找结果。 以上查找方法为基于长度的顺序前缀查找，每搜索一步，搜索空间就缩减一半。

Trie树的更新 插入一个地址前缀 删除一个地址前缀 以该前缀为关键字在Trie树中进行查找； 若查找过程在一个中间节点终止，将此节点标记为前缀节点，并在此中间节点中加入前缀转发信息； 若不再有分支可选取，需要插入必要的分支节点。 删除一个地址前缀 若查找过程在一个中间节点终止，将此节点标记为非前缀节点，删除此节点的转发信息； 若查找过程终止于叶子节点，除了删除该节点之外，还需要根据情况删除其它一些内部节点 。

路径压缩Trie树 路径压缩Trie树压缩单孩子分支 每个节点需要维护一个变量，指示下一个需要检查的比特位 前缀节点需要保存地址前缀的比特串

路径压缩Trie树（续） 当二进制Trie树中的前缀分布较稀疏时，路径压缩算法能够获得良好的压缩效果。 研究表明，对于一个具有47113个前缀表项的典型骨干网路由器，使用BSD Trie会创建93304个节点，树的最大高度为26，平均高度为20。而对于同样的前缀表，二进制Trie树的最大高度为30，平均高度为22。

多分支Trie树的基本算法 查找的每一步检查地址的多个比特，每次检查的比特数称为查找步宽。 同一层中不同子树的步宽可以相同（固定步宽多分支Trie），也可以不同（可变步宽多分支Trie）。 前缀表中的地址前缀必须转换成多分支Trie查找能够允许的地址前缀，称前缀扩展。 多分支Trie树的深度有很大缩减，因而提高了查找效率。 多分支Trie的查找过程类似于二进制Trie。 多分支Trie的更新过程比二进制Trie复杂： 插入一个前缀时，需要找到相应的subtrie，对前缀进行扩展，然后插入。 删除一个前缀时，需要删除所有扩展的前缀。 需要额外的数据结构保存原始前缀。

可变步宽与固定步宽的多分支Trie树

多分支Trie例1

多分支Trie例2 在地址扩展过程中，如果扩展的地址前缀与原来的地址前缀冲突，应保留原来的地址前缀。

多分支Trie的优化 步宽的选择 步宽的选择是在算法查找速度、存储空间和更新复杂度之间的折衷。 一种较自然的做法是根据实际地址前缀的分布来选择合适的步宽。 使用某种优化策略，使在搜索深度固定的情况下整个树的存储空间最小。

Stanford算法 24-8多分支trie快速查找算法的硬件实现 查找最多只需要两次访存；采用硬件流水线技术，实际上只需要一次访存的时间。 TBL24 TBLlong 24-8多分支trie快速查找算法的硬件实现 查找最多只需要两次访存；采用硬件流水线技术，实际上只需要一次访存的时间。 算法要求的内存空间比较大。

基于TCAM的硬件查找 TCAM中每一个表项以<地址，掩码>序偶的形式保存。 查找速度快，实现简单。完成一次查找只需三步操作，采用流水线技术可以进一步提高查找速度。 容量小，代价高，功耗大，更新复杂（关键字需要排序）。

内容可寻址寄存器（CAM） CAM是一种支持快速搜索和数据存储的存储机制，主要用于改善查表操作的性能。 CAM提供的查找操作是并行匹配，处理器提供一个查找关键定，CAM返回匹配该关键字的一组槽，响应时间一般不超过100ns。 CAM的组织

TCAM（三态CAM） 硬件在每个入口存储一个二进制数和一个掩码。 掩码的长度等于槽长度，用于说明槽中哪些比特要和查找关键字中的相应比特进行比较。 TCAM适合于查找带通配符的关键字。

主要参考文献 [1] IP Router Architectures: An Overview. [2] Study of Internet Router Architectures. [3]RouteBricks: Exploiting Parallelism to Scale Software Routers. [4]PacketShader: A GPU-Accelerated Software Router. [5] Survey and Taxonomy of IP Address Lookup Algorithms.