（通信与信息系统专业论文）ipv6网络数据包分类的研究与实现.pdf

i 摘摘 要要 数据包分类在虚拟专用网络、基于策略的路由、区分服务、流量计费等领域得 到了广泛的应用。为了更大的地址空间和更好的服务质量，以 ipv4 为基础的网络向 ipv6 升级是因特网发展的趋势。新的网络环境下，数据包分类技术面临着新的压力 和挑战，主要表现在：(1)ipv6 更深的协议栈增加了协议解析的难度；(2)ipv6 网络设 备需要后向兼容 ipv4；(3)多维分类要求支持最佳规则匹配；(4)新的应用要求基于内 容分类。 针对上述问题，本文的研究工作从两个方面展开：(1)基于指令集的协议解析与 字段抽取技术；(2)利用三态内容寻址存储器实现最佳规则匹配和基于内容分类的技 术。本文取得的成果有： 1. 协议解析和字段抽取指令集。基于该指令集的硬件同时支持 ipv4 和 ipv6，与协 议栈深度无关。和软件/硬件协议栈相比，其所需资源更少，处理性能更高，并 可以动态支持新的协议类型。 2. 分布式规则管理算法。该算法支持最佳规则匹配，时间复杂度只与规则种类有 关，而与规则数量无关。与集中式规则管理算法相比，该算法将时间复杂度减 小了两个数量级。 3. 多字节移位多模式匹配算法。运用三态内容寻址存储器，该算法能够实现多模 式的并行匹配，适用于基于内容的分类。算法的时间复杂度是待检测文本长度 的线性函数，与模式的数量无关。该算法可以通过增大模式空间换取数倍的处 理带宽。 本文的研究成果在 fpga 上进行了实现，还可以很方便地集成到 asic 或 npu 中。参考设计能够处理 5g 输入带宽下从数据报链路层到运输层的多维分类，同时支 持 ipv4 和 ipv6，支持基于内容的分类。 关键词：关键词：数据包分类，协议解析，基于内容的分类，最佳规则匹配，内容寻址存储 器 ii abstract packet classification is widely used in fields of virtual private network, distributed firewall, policy-based routing, differentiated qualities of service and traffic billing etc. for more ip addresses and higher quality of service, ipv4-based network is tending to be upgraded to ipv6 network gradually. since this brings more pressures and new challenges to packet classification: 1) dealing with deeper protocol stack, 2) being compatible with ipv4, 3) best matching rule, 4) supporting content-based classification, this thesis mainly focuses on the research of: protocol analyzing, field extracting, rule managing and pattern matching. the attributions of the thesis include: 1. instructions for protocol analyzing and field extracting: an instruction-based hardware is independent on the depth of protocol stack. compared with tcp/ip-based software, it processes packets at higher performance with less memory and supports new protocols dynamically. 2. distributed rules managing algorithm: collisions often happen in multi-field classification. for packet to match the best rule, the thesis presents a distributed rules managing algorithm, which depends on the classes rather than the number of rules. 3. multi-byte shifting multi-pattern matching algorithm: it is proposed for content-based classification by using ternary content addressable memory. it can support new patterns dynamically and multiple the processing bandwidths by enlarging the pattern space. the thesis presents a reference design of packet classifier that is implemented with fpga and can be easily integrated to asic or npu. it supports multi-field classification through layer 2 to layer 7 at 5gbps wire speed. key words: packet classification, protocol analyzing, best matching rule, content-based classification, content addressable memory 独创性声明 本人声明所呈交的学位论文是我个人在导师的指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已标明引用的内容外，本论文不包含任何其他人或集 体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文 中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密，在_年解密后适用本授权书。 本论文属于 不保密。 （请在以上方框内打“” ） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 1 1 绪绪 论论 1.1 选题背景与课题意义选题背景与课题意义 经过 30 多年的发展，以 ipv4(internet protocol version 4)为基础的网络无论是地 址空间还是服务质量(qos，quality of service)都难以满足现状。ietf(internet engineering task force)成立了专门的工作小组，研究从现有 ipv4 网络向下一代网络 (ngn，next generation network)过渡的可行策略和必要技术。ipv6(internet protocol version 6)1作为下一代网际协议已经达成了共识。未来互联网的发展离不开对 ipv6 的支持和应用。ipv6 甚至被认为是后起发展网络的国家追赶发达国家的一个良好机 遇。2003 年底，以国家战略项目，中国下一代互联网示范工程(cngi，china next generation internet)启动为标志的中国 ipv6 商用化进程进入了实质性的发展阶段。 数据包分类是指基于协议首部的某些字段，对数据包进行分类处理。ipv4 网络 中，数据包分类技术在虚拟专用网络、基于策略的路由、区分服务、流量计费等领 域得到了广泛的应用。为了更大的地址空间和更好的服务质量，由 ipv4 网络向 ipv6 升级是因特网发展的趋势。新的网络环境下数据包分类技术面临着新的压力和挑战， 主要表现在： 1.1.1 更深的协议栈 为了保证服务质量，ietf 提出了集成服务模型(intserv)2和区分服务模型 (diffserv)3。无论是集成服务模型还是区分服务模型，路由器都要对用户数据包进 行分类(区分服务模型中，复杂的数据包分类工作仅由边缘路由器完成)。分类规则可 能依据网络层以上的协议字段，因此边缘路由器需要解析运输层甚至应用层的协议， 而不仅仅是网络层。 ipv6 是网络层的协议，相对于 ipv4 做了比较大的改动。它力图将协议首部开销 降到最低，具体做法是将协议首部分为基本首部和扩展首部，字段数减少到 9 个， 把一些非关键性字段和可选字段置于扩展首部中，而且还取消了首部的检验和字段。 由于主干路由器不需要对扩展首部进行处理(逐跳选项首部除外)，改进后的 ipv6 基 本首部大大提高了主干路由器的转发效率。 如图 1.1 所示，ipv6 的扩展首部最多可达 7 级。随着网络技术的不断发展，将 来可能出现更多新的扩展首部。层层级联的扩展首部大大加深了协议栈的深度，这 给边缘路由器解析数据包协议带来了严峻的压力。 2 ipv6基 本首部 基 本首部 链路层链路层 逐跳选 项首部 逐跳选 项首部 目的选 项首部 目的选 项首部 路由 首部 路由 首部 分片 首部 分片 首部 认证 首部 认证 首部 安全 首部 安全 首部 目的选 项首部 目的选 项首部 运输层运输层 应用层应用层 网络层网络层 ipv6扩展首部扩展首部 图图 1.1 ipv6 协议栈协议栈 1.1.2 对 ipv4 的兼容 现有网络中仅支持 ipv4 的网络设备数量庞大， “规定一个日期，从这一天起所 有的网络设备一律都改用 ipv6” ，显然是不行的。因此，由 ipv4 向 ipv6 过渡是一个 逐步演进的过程。 ipv6 网络设备需要向后兼容， 要求能够接收和转发 ipv4 数据包4。 ietf建议三种由ipv4向ipv6过渡的策略： 双协议栈(dual-stack)、 隧道技术(tunneling) 以及转换技术(translation)58。 数据包分类是一个功能相对单一但性能要求很高的工作。 例如同步光纤网oc-48 的收发两个线路在最极端情况下的数据包率高达 1000 万个每秒。网络设备的数据包 分类工作一般由专门的硬件单元来完成。用硬件实现双协议栈来同时支持 ipv4 和 ipv6，代价太高。而隧道技术和转换技术主要面向 ipv4 网络与 ipv6 网络之间的通信 传输。 设计一种简单、易于硬件实现且同时支持 ipv4 和 ipv6 的数据包分类器，是一个 极富挑战的工作。 1.1.3 最佳规则匹配 为了更加有效的利用 ipv4 的地址空间，ipv4 路由器普遍采用无分类域路由选择 (cidr，classless inter-domain routing)，将 ip 地址分为网络前缀和主机号两个部分， 路由表由网络前缀和下一跳地址组成。路由器在查找路由表时可能会得到不止一个 匹配结果。路由器采用最长前缀匹配(longest matching prefix)的策略4，即从匹配结 果中选择具有最长网络前缀的路由， 因为网络前缀越长路由就越具体。 ipv6 相对 ipv4 的一个重要变化就是单播地址采用多级结构，即把单播地址分为顶级、地点级、网 络接口级。ipv6 单播地址的多级地址结构使得路由器可以更快地查找路由。 最长前缀匹配的初衷是更加有效的利用 ipv4 的地址空间。对于 ipv6 来说，地址 空间在可以预见的未来也不会耗尽4。然而， 很多网络应用要求基于多个字段的组合 对数据包进行多维分类，这便引起了规则冲突的问题。 假设一个路由器设定了三条规则：(1) 将所有目的端口为 5004 并且目的 ip 地址 3 为 a 的数据包划分第一类，服务级别为 1；(2) 将所有目的端口为 5004 的数据包划 分为第二类，服务级别为 2；(3)将所有目的 ip 地址为 a 的数据包划分第三类，服务 级别为 3。当一个目的 ip 地址为 a，目的端口为 5004 的数据包进入路由器时，这个 数据包可能被划分到以上三类中的任何一类。显然，第一类是第二类和第三类的一 个交集，它对数据包的分类更加具体。 类比最长前缀匹配，第一条规则对于这个数据包来说是最佳规则，本文称数据 包匹配最具体或最高优先级规则的情形为“最佳规则匹配(best matching rule)” 。如 何实现最佳规则匹配以及如何管理规则，这是数据包分类必须解决的新问题。 1.1.4 基于内容分类 前文提到的虚拟专用网络、基于策略的路由、区分服务、流量计费等应用，都 是基于数据链路层到运输层的某个字段或字段的组合对数据包进行分类。随着网络 技术的发展，新的应用层出不穷。一些新的应用要求基于应用层的内容对数据包分 类。 基于 snort 规则的轻量级 ids(intrusion detection system，入侵监测系统)，除了 监测数据包协议首部的常用字段外，还需要用到应用层内容的模式匹配9。应用层交 换机要求能够解析 ftp(file transfer protocol，文件传输协议)、http(hypertext transfer protocol，超文本传输协议)等的 url(uniform resource locator，统一资源定 位符)，根据访问站点、目录结构或者文件类型做负载均衡10,11。网络监控系统要求 采集或者过滤访问某些非法站点以及包含某些敏感关键词的数据包。 诸如此类的新应用，要求网络设备能够基于应用层的位置和长度并不固定的内 容进行数据包分类。这是数据包分类面临的又一挑战。 针对以上几大问题，研究以 ipv6 为基础的下一代网络的数据包分类技术，可以 提高网络的处理性能，改善网络的服务质量，拓展网络新的应用，具有较高的理论 意义与经济效益。 1.2 研究内容与本文组织研究内容与本文组织 如何从 ipv6 数据包深层的协议栈中抽取所需的分类字段以及后向兼容 ipv4，如 何实现基于内容的分类，如何让数据包匹配最佳的规则，分别属于协议解析、分类 查找、规则管理的范畴。协议解析、分类查找、规则管理，是数据包分类的三个方 面。其中，协议解析是分类查找的必要前提，规则管理是分类查找的有效保障。 自上个世纪 90 年代以来，国内外对数据包分类技术进行了广泛而深入的研究， 4 提出了很多分类算法。已有的研究大多集中在分类查找，而对于协议解析、规则管 理的研究不多。此外，对于多维分类的最佳匹配、基于内容的分类等问题，已有研 究也没有提出很好的解决办法。 本文的研究将从两个方面展开：第一，研究基于指令集的协议解析与字段抽取 技术；第二，研究利用三态内容寻址存储器实现最佳规则匹配和基于内容分类的技 术。 本文的工作得到了与某企业合作的 “下一代网络应用层交换机(application switch for next generation network)”研究课题的资助。 本文后续部分的组织如下：首先第 2 章将对数据包分类技术进行概述，包括常 见的分类字段、分类算法的衡量标准、已有分类算法的评价、实现方式的比较以及 数据包分类的应用领域等。接着第 3 章将对基于指令集的数据包协议解析和分类字 段抽取技术进行探讨。之后第 4 章将研究如何运用三态内容寻址存储器支持最佳规 则匹配则和实现基于内容分类的技术。然后第 5 章将给出数据包分类器的一个参考 设计，包括逻辑设计、仿真测试以及实现结果。最后第 6 章将总结本文的工作，讨 论数据包分类技术今后的研究方向。 5 2 数据包分类技术概述数据包分类技术概述 本章主要介绍数据包分类技术的基本概念和国内外的相关研究成果，包括常见 的分类字段、分类算法的衡量标准、已有分类算法的评价、实现方式的比较以及数 据包分类的应用领域。 2.1 常用的分类字段常用的分类字段 数据包分类是指依据一定的规则，对数据包进行分类处理。这些规则通常是数 据包协议首部的某个字段或者一些字段的组合12。 数据链路层可按源 mac(media access control，媒体访问控制)地址、目的 mac 地址来确定数据包发送的源、目的主机。对于以太网还可以按协议类型来确定上层 传输所使用的协议， 如 ipv4、 ipv6、 arp(address resolution protocol， 地址解析协议)、 rarp(reverse address resolution protocol，逆地址解析协议)等。 网络层可按源 ip 地址、目的 ip 地址来确定主机，按协议类型来确定运输层所 使用的协议，如 tcp(transfer control protocol，传输控制协议)、udp(user datagram program，用户数据包协议)等。ipv4 的服务类型(tos，type of service)或 ipv6 的流 量类型(tc，traffic class)指示了服务质量或者优先级类别，也可用作分类的字段。 运输层可以用于分类的字段有源端口、目的端口，它包含了连接两端的应用程 序的端口号。 tcp 定义了 6 个比特的标识字段： urg (紧急比特)、ack (确认比 特)、psh (推送比特)、rst (复位比特)、syn (同步比特)和 fin (终止比特)。这 6 个 标识用来指示数据包的应用目的和内容，并给出对数据包头部中其他字段的解释。 tcp 的标识字段也可以用来对数据包进行分类。 应用层协议种类繁多，常见的作为分类依据的有 ftp、http 的 url，它包含 了服务站点、目录结构、文件类型等信息。数据内容也可以作为一些应用(如网络监 控)的分类依据。 目前两种比较常见的分类组合是： 源ip地址、 目的ip 地址的二维分类和源ip 地 址、目的 ip 地址、协议类型、源端口号、目的端口号的五维分类13。 数据包协议解析、分类字段抽取是分类查找的必要前提。很多应用要求基于字 段组合的多维分类。多维分类存在同时匹配多个规则的问题，分类器需要提供一种 机制保证数据包匹配最佳的规则。关键词长度的不一致以及出现位置的随意性是基 于内容分类的难点。 6 2.2 分类算法的衡量指标分类算法的衡量指标 数据包经过协议解析和字段抽取，接下来就是分类查找。分类查找的核心是分 类算法。在评价已有的分类算法之前，本文先介绍分类算法的几个衡量指标：时间 复杂度(time complexity)、空间复杂度(space complexity)、更新复杂度(update complexity)、可扩展性(extension)以及最坏情况下的性能12。 (1) 时间复杂度 时间复杂度定义为分类算法所需要的步骤或循环数目的最大边界 o(f)，f 是规 则个数 n、域宽 w 和维数 d 的函数。该指标用于确定找到匹配/不匹配规则所需要 的步骤。 (2) 空间复杂度 空间复杂度定义为保存分类规则及其相关数据结构所需要空间的最大边界 o(f)。和时间复杂度相同，f 也是规则个数 n、域宽 w 和维数 d 的函数。 (3) 更新复杂度 更新复杂度定义为插入、删除或更新一条规则所需要的步骤或循环数目的最大 边界 o(f)。一般有三种可能的更新： 1完全更新。完全更新指对全部数据结构进行 重建。 2增量更新。增量更新指在运行过程中向分类器中插入或删除一条分类规则。 3结构重组。结构重组指随着分类规则的不断插入和删除，可能会造成查找数据结 构效率变低，需要对数据结构进行适当的调整。 (4) 可扩展性 可扩展性包括三个方面的内容： 1分类规则的个数具有可扩展性。分类规则的 个数 n 可以很大，而不是限定在固定的数目。 2分类的维数具有可扩展性。规则可 以包含多个分类字段，而不是限定在固定的某几个字段。 3分类的层次具有可扩展 性。分类可包含多个层次，理想的算法应该是能够容许匹配任意层内的字段，包括 数据链路层、网络层、运输层，在一些特殊的情况下还可能包括应用层的内容。 (5) 最坏情况下的性能 一个分类算法的好坏，除了给出平均性能的分析外，还应该给出在最怀情况下 的性能分析。平均的性能分析有时不能完全真实反映分类的性能。研究表明 75%的 数据包比典型的 552 字节的 tcp 数据包要小，而且将近一半的数据包的长度为 40 到 44 字节，它们主要由 tcp 确认数据包和 tcp 控制数据包组成14。对于所有数据 包都是最短包的最坏情况，分类器无法用缓存来吸收包长变化从而获取较大的平均 包长，因此分类算法必须能够线速处理最坏情况下的分类查找15。 7 对于数据包分类算法而言，一般期望时间复杂度、空间复杂度和更新复杂度越 小越好，并具有良好的可扩展性，不仅平均性能好，而且在最坏情况下的性能也良 好。在许多情况下，数据包分类算法的全部指标无法同时达到最优，只能根据算法 的使用场合加以折衷。 2.3 已有分类算法的评价已有分类算法的评价 数据包分类的一个重要步骤就是分类查找，分类查找的核心就是分类算法。已 有的数据包分类算法可以大致分为五类12,1622：基本数据结构算法(basic data structure algorithms)、几何算法(geometric algorithms)、并行搜索算法、启发式算法 (heuristics algorithm)和基于硬件的算法(hardware-based algorithm)。本节将根据 2.2 节列举的衡量标准，对这五类分类算法加以评价。下文将要用到几个符号：w 表示 分类域宽，n 表示规则个数，d 表示分类维数，l 表示树的层数。 (1) 基本数据结构算法 表格算法23通过构造全部的可能情况表，利用可能情况直接作为寻址标示(数组 下标)，其时间复杂度为 1，空间复杂度为 o(2w)。 线性查找算法简单地线性地存储规则，并将分类字段与规则进行线性匹配。该 算法具有较好的存储效率(o(n)， 但是它的时间复杂度会随着规则数目的增加而线性 增加(o(n)。 分层查找树(hierarchical tries)算法24将 d 维规则按第一维分类排列为按比特的 树，然后递归地建立其它维域的树并将其连接到上一维的树。其时间复杂度为 o(wd)，空间复杂度为 o(ndw)，更新复杂度为 o(d2w)。这种算法一般用于规则数 目较少的场合。 集合归并查找树(set-pruning tries)算法12是对是分层查找树算法的改进， 通过复 制部分树，可以不回溯查找。此算法的时间复杂度为 o(dw)，空间复杂度为 o(nddw)，更新复杂度为 o(nd)，一般用于不经常更新的数据包分类器。 (2) 几何算法 栅格查找树(grid-of-tries)算法25该算法是集合归并查找树算法的改进，将复制 功能通过指针实现， 节约了空间。 其时间复杂度为 o(wd 1)， 空间复杂度为 o(ndw)， 更新复杂度较高。该算法常被用于二维分类。 基于空间划分的四叉树(aqt，area-based quadtree)算法2629通过将二维空间划 分为若干区域(一般是相等的四个区域)，每个四叉树的每个节点表示一个区域(每个 区域至少包含一个规则或其某部分)。时间复杂度为 o(w)，空间复杂度为 o(nw)。 8 该算法常用于二维空间分类。 fis-tree(fast inverted segmented tree)算法30利用规则之间的覆盖关系构造庞大 的逆向分段树，时间复杂度为 o(w( l + 1)，空间复杂度为 o(ln(1 + 1/ l) )。该算法允 许通过调整 l，牺牲空间来换取较快的匹配速度。 (3) 并行搜索算法 abv(aggregated bit vector)算法3133是并行搜索算法的一个代表算法，由于采 用并行查找集中地访问内存的方法，使得查询时间大大减少。其时间复杂度为 o(dn)，空间复杂度为 o(dn2)。此算法最坏情况下的空间复杂度非常高。 (4) 启发式算法 递归流分类(rfc， recursive flow classification)算法34分布并行运算， 逐步求精， 时间复杂度为 o(d)，空间复杂度为 o(nd)。此算法需要并行计算能力，速度快，存 储和维数相关。 智能查找树(hicuts，hierarchical intelligent cuttings)算法35，通过几何搜索获得 一个规则的子集，其中规则数目少于一常数，继续搜索获得最终规则。其时间复杂 度为 o(d)，空间复杂度 o(nd)。此算法空间需要量大，速度快，可多维分类，更新 复杂度低。 元组空间查找(tuple-space search)算法36,37，预先计算规则前缀元组(tuple)，进 行比较时采用 hash 算法。一般地，元组数比过滤规则数少很多，因此即使是在元组 空间中采用线性查找，其性能也有很大提高。该算法最坏时间复杂度为时间复杂度 为 o(d)，空间复杂度为 o(d)。在更新时，一般只需要一次 hash 操作，因此该算法 更新复杂度较低。总之，在元组数目较少的情形下，该算法对于多维空间的分类有 较小的时空复杂度。 (5) 基于硬件的算法 tcam(ternary content addressable memory, 三态内容寻址存储器)算法3840将 所有规则利用硬件存储，可以实现并行匹配，该算法时间复杂度为 1，空间复杂度为 o(n)，更新复杂度为 1，具有非常好的时间复杂度、空间复杂度和空间复杂度。其缺 点是硬件集成度小，实现成本较高。tcam 一般只用于规则数目较少的分类器。 位图交集算法(bitmap-intersection)41利用投影关系计算位表， 利用位表合成运算 结果， 其时间复杂度为 o(dw+n/memwidth)， 空间复杂度为 o(dn2)， 需要硬件实现， 存储空间大。该算法适用于规则较少的分类器。 从以上的分析比较可以看出，tcam 在时间复杂度、空间复杂度、更新复杂度、 9 最坏情况下的性能四个方面都具有独特的优势。在可扩展性方面，tcam 能够灵活 地扩展维数。 tcam 的缺点是集成度低， 成本较高。 目前的商用 tcam 可以存储 256k 条 72 位宽的规则，能够满足大多数网络设备数据包分类的要求。 2.4 实现方式的比较实现方式的比较 数据包分类属于网络处理的范畴。传统的网络设备采用通用处理器。随着网络 传输速率的迅猛增长，通用处理器难以满足高速网络的处理要求。目前的网路设备 一般采用 asic、npu 或 fpga。 (1) asic asic(application specific integrated circuit，专用集成电路)是当前网络设备的 核心处理技术。网络设备将路由查找、数据包处理等数据层面的操作固化在硬件芯 片中，可以获得更高的处理速度，因而能够很好地满足对性能的要求，以适应网络 带宽不断增长的发展趋势。对于大批量生产，asic 的成本较低。asic 最大的缺点 是缺乏灵活性。一旦逻辑固化到硬件中，就很难修改升级、增加新的功能，这使得 asic 的资源重用率很低。另外，asic 需要较高的设计成本和较长的设计周期，从 而使得产品上市时间很长。 在 asic 中简单地实现硬件 tcp/ip 协议栈的代价非常昂贵。如果用一块硬件逻 辑来解析一种协议首部。ipv6 现有的 6 种扩展首部就对应 6 块硬件逻辑。这种实现 方式导致 asic 的面积与所支持的协议种类成正比，成本很高。如要实现双协议栈， 芯片面积更大，成本更高。另外，随着网络的发展，ipv6 可能出现新的扩展首部。 而 asic 一旦设计完毕，硬件逻辑已经固化，很难扩展支持新的协议类型。文献42 提出了一种可配置的数据包分类器的 asic 实现方式。 该方式采用五级宏流水线的架 构， 根据应用场合更改配置， 支持最多五级的协议首部解析。 依照这种实现方式， ipv6 数据包需要十级以上的宏流水线才能解析运输层协议首部，其代价也太高。 (2) npu npu (network processing unit，网络处理器)是一种经过专门设计和高度优化来 完成各种网络功能的可编程设备43。它一般集成了精简指令集处理核、协处理器、 内部高速总线、大容量片上存储器(embedded memory)、高速 i/o 接口单元等。npu 具有很多优点： 1可编程性。npu 的本质在于可以编程，从而改变 asic 灵活性差 的缺点。这是通过提供界面友好、功能强大的编程、调试和性能评价等软件环境来 实现的。 2并行处理。npu 可实现不同级别的并行处理。流水线可以实现指令级的 并行，硬件线程可以实现线程级的并行，片内多处理器结构可以实现处理器级的并 10 行。 3可扩展性。npu 包括硬件层面和软件层面，力图在保持高性能的基础上获得 很好的可扩展性和灵活性。在原有软件结构的基础上做很小的改动，npu 就可以加 入新的服务和功能。npu 也有一些缺点，最显著的就是需要大容量存储带宽。另外， npu 价格昂贵，处理性能相对 asic 而言要差一些。 基于 npu 的网络设备，一般采用软件 tcp/ip 协议栈来完成协议解析和字段抽 取工作。npu 先将数据包暂存在缓存中，接着解析各层协议，并抽取分类字段(分类 查找由专门的硬件完成)。 当所有的协议首部解析完毕， npu 将数据包从缓存中取出， 连同分类结果一起发送给其他处理单元。由于长包的净荷不需要解析，这种“接收 存储处理发送”的模式，能够借助大缓存实现长短包平均包长意义上 的线速处理。然而，这种处理方式需要大量的片上存储器或者片外缓存，所要求的 缓存带宽是网络带宽的十几倍以上，成本代价太高。并且，对于高速网络环境下所 有输入数据包都为最短包的最坏情况，npu 必须解析所有数据(没有净荷)，即使增 大缓存也做不到线速处理，还有可能出现严重丢包的现象。npu 可以采用双协议栈 来同时支持 ipv4 和 ipv6。 (3) fpga fpga (field programmable gate array，现场可编程门阵列)是一种通用的可编程 逻辑器件。它由许多独立的可编程逻辑单元构成。各逻辑单元之间可以灵活地相互 连接。 fpga 具有密度高、 速度快、 编程灵活和可重新配置等诸多优点。 近年来， fpga 制造商推出了面向网络通信、信号处理、工业控制等不同应用领域的平台 fpga。网 络通信平台 pfga 通过集成网络处理 ip 核(intelligent property core)、嵌入式处理核 等，可以提供高性能的数据处理和网络控制功能，将灵活性与性能折衷控制权完全 交到用户手中。平台 fpga 具有设计周期短、灵活性好、扩展性强等优点。基于平 台 fpga 的二次开发需要详细划分软硬件功能，还需要运用硬件描述语言、软件设 计语言等进行协同设计。 平台 fpga 的可编程逻辑结构使得其处理性能无法和 asic 相媲美。另外，平台 fpga 的功耗较大，片上存储器有限，大批量的平均价格要高 于 asic。 在 fpga 中实现硬件 tcp/ip 协议栈或者多级宏流水线结构来解析 ipv4/ipv6 数 据包， 成本代价比 asic 更高。 但是， fpga 可以通过重新编程来支持新的协议类型。 数据包分类是一个速率要求较高而操作相对简单的工作。设计一种同时支持 ipv4 和 ipv6、方便扩展而且易于实现的数据包分类器，将它集成到 asic、npu 或 平台 fpga 中，既可以保证高速的处理性能，又不失灵活性。 11 2.5 分类的应用领域分类的应用领域 数据包分类在很多领域得到了应用，下文列举的网络关键技术都是以数据包分 类为基础的。数据包分类在未来网络中将会有更多新的应用。 (1) 虚拟专用网 虚拟专用网(vpn，virtual private network)是利用公用互联网建立虚拟的专用网 络。虚拟专用网的一种实现技术是路由过滤技术，也称为受控路由过滤(controlled router leaking)。网络服务提供商在路由器中根据数据包的源地址、目的地址将用户 划分为不同的通信域，每个通信域构成一个虚拟专用网。路由器控制不同通信域间 的信息传送，达到虚拟专用网的逻辑分割。 (2) 基于 acl 的防火墙 防范网络攻击最常用的方法是防火墙。随着网络安全技术的发展，防火墙已经 成为一种更为先进和复杂的应用层网关。防火墙可以根据 acl(access control list， 访问控制列表)对数据包进行过滤。过滤规则包括数据包的源地址、目的地址、源端 口号、目的端口号、运输层的协议，还包括特定的网络服务协议等。 (3) qos 路由 支持 qos 的路由器提供接入控制、基于流的排队和公平调度等机制，根据预先 定义的规则，用快速分类算法对每个数据包进行分类44，以标识和区分不同的流， 为不同的流提供不同的服务质量。 例如， 支持qos的路由器可以把voip(voice over ip) 数据包分配到一个具有较高优先权的队列中。qos 路由的规则可以根据数据包中的 源地址、目的地址、服务类型、端口号、协议类型等参数来制订，且具有优先级标 识。 (4) 拥塞控制 对于拥塞的数据包分类经常为选择的协议配置一系列的规则来定义队列的优先 级，以便网络设备管理数据包。规则一般基于运输层参数，如使用的协议、端口号、 连接状态，也可能用到用户配置的参数，以确保有较高优先级的数据包不被延迟或 丢弃。 (5) 传输测量与计费 网络计费是网络管理的重要组成部分。开发一套完善的网络计费系统是每个网 络运营部门的首要工作。网络计费的主要任务是对登录用户进行认证和传输测量(例 如测量两个子网间的传输量)。目前网络普遍采用的是以 ip 地址标识用户，采用路由 器管理信息数据库中数据，统计该 ip 地址的数据流通量的计费方法。为防止 ip 盗 12 用，也采用 ip 地址与 mac 地址绑定的办法来惟一确定一台计算机，从而为传输记 账打下基础。分类字段涉及到 ip 地址、mac 地址等信息。 (7) 资源预留 资源预留(rsvp，resource reservation protocol) 为预先指定的流做资源预留， 与包分类和流标识密切相关。资源预留还需要制定一些策略来限制单个独立流的要 求，或隔离包调度，以阻止超出限制的流。 除了以上介绍的应用外，数据包分类在负载平衡(例如将数据包路由到不同的服 务器上)、网络入侵检测、网络监控等领域都有广泛的应用。 2.6 本章小结本章小结 本章对数据包分类技术进行了概述，包括常见分类规则、分类算法的衡量标准、 已有分类算法的评价、分类实现方式的比较以及数据包分类的应用领域等。 很多应用要求基于字段组合的多维分类。多维分类存在同时匹配多个规则的问 题，分类器需要提供一种机制保证数据包匹配最佳的规则。关键词长度的不一致以 及出现位置的随意性是基于内容分类的难点。 在现有分类查找算法中， tcam 在时间复杂度、空间复杂度、更新复杂度、最 坏情况下的性能等方面具有独特的优势。 用 asic、npu、fpga 实现数据包分类各有优缺点。综合三者的特性，设计一 种同时支持 ipv4 和 ipv6、 方便扩展而且易于实现的数据包分类器， 将它集成到 asic、 npu 或平台 fpga 中，既可以保证高速的处理性能，又不失灵活性。 13 3 协议解析与分类字段抽取协议解析与分类字段抽取 很多应用要求网络设备能够根据网络层以上的协议字段对数据包分类。因此， 这些网络设备必须能够解析运输层甚至应用层的协议。 随着 ipv4 网络向 ipv6 网络的 升级，这些问题变得越来越显著。首先，ipv6 将协议首部分为基本首部和多级扩展 首部，每一级扩展首部都可以视作一个独立的协议首部，最多可以级联 7 个扩展首 部。 要解析运输层协议， 必须依次解析 ipv6 的每级扩展首部。 其次， ipv4 网络向 ipv6 升级是一个逐步演进的过程。ipv6 网络设备需要后向兼容 ipv4。网络设备的数据包 分类器要能够同时支持 ipv4 和 ipv6。 数据包分类包括协议解析、字段抽取、分类查找几个步骤。协议解析和分类字 段抽取是数据包分类查找的必要前提。 目前的网络设备一般基于npu、 asic或fpga 处理。npu 采用软件 tcp/ip 协议栈，性能有所不足，存储带宽要求很高。用 asic 或 fpga 实现硬件 tcp/ip 协议栈，代价太高，而且扩展性不好。 本章将从另外一个角度，探讨一种基于指令集的适合于协议解析与字段抽取的 硬件结构，要求该硬件结构能够解析 ipv6 深层的协议首部，后向兼容 ipv4，灵活性 好，扩展性强，且易于实现。 3.1 协议解析原理协议解析原理 在计算机网络中要做到有条不紊地交换数据，必须遵守一些事先约定的有关数 据格式和同步问题的规则。这些为进行网络数据交换而建立的规则、标准或约定即 称为网络协议(network protocol)。 计算机网络一般都分为若干层次， 每一层都包含一 些协议。计算机网络的各层以及协议的集合称为网络的体系结构。 为了使不同体系结构的计算机网络能够互连，国际标准化组织(iso，internet standard orgnization)提出了著名的开放系统互连基本参考模型(osi/rm，open systems interconnection reference model)，简称为 osi。osi 模型采用七个层次的体 系结构，自下而上依次为： 1物理层；2数据链路层；3网络层；4运输层；5会 话层； 6表示层；7应用层。 而实际网络中应用最为广泛的是 tcp/ip 模型。tcp/ip 一般指整个协议栈 (protocol stack)或协议族(protocol suite)。tcp/ip 模型采用四个层次： 1网络接口层； 2网络层；3运输层；4应用层。其中，网络接口层对应 osi 模型的物理层和数据 链路层，应用层对应 osi 模型的会话层、表示层和应用层。 一些文献中用第一层到第七层来表示网络协议层。实际上第二层(l2，layer 2) 14 指数据链路层，第三层(l3，layer 3)指网络层，第四层(l4，layer 4)指运输层，第七 层(l7，layer 7)指应用层。 组装数据包时，从上层到下层，应用数据经过各层协议的封装，被加上属于不 同层次的协议首部。解析数据包时，从下层到上层，数据包的各层协议首部被依次 剥离。图 3.1 说明了数据包组装与解析的过程： 物理传输媒体物理传输媒体 应用层应用层 运输层运输层 网络层网络层 链路层链路层 应用层应用层 运输层运输层 网络层网络层 链路层链路层 物理层物理层物理层物理层 应用数据应用数据链路层链路层 进程进程进程进程 网络层网络层运输层运输层应用层应用层 应用数据应用数据网络层网络层运输层运输层应用层应用层 应用数据应用数据运输层运输层应用层应用层 应用数据应用数据应用层应用层 应用数据应用数据 1 0 1 0 0 1 1 0 1 0 0 1 1 1 0 1 0 1 1 1 0 比特流比特流 校验校验 图图 3.1 数据包组装与解析数据包组装与解析 协议首部或者采用固定的长度， 或者包含一个协议长度字段(pl， protocol length) 来表示当前协议的长度。根据协议长度可以确定当前协议的结束位置和上层协议的 开始位置。协议首部通常还包含一个协议类型字段(pt，protocol type)来标识上层(逻 辑上的上层)使用的协议类型。通过当前首部长度和上层协议类型，可以从下层到上 层依次解析各层协议首部。 3.2 协议长度计算协议长度计算 数据包分类中，协议解析的主要目的是抽取分类的字段。如果知道一个协议首 部的起始位置，就可以根据协议定义中的一些字段的相对位置来确定这些字段的绝 对位置，抽取这些字段组成查找关键字进行分类查找。因此，对于数据包分类，协 议解析的首要任务就是计算协议首部的长度，确定协议首部的边界。 常见协议首部长度的计算可以分为以下四种情况： (1) 固定长度。很多协议首部采用固定的长度，如 cisco-hdlc(cisco high-level data link control)为 4 字节，以太网 mac 为 14 字节，vlan(virtual local area network，虚拟局域网)为 4 字节，udp 为 8 字节，ipv6 基本首部为 40 字节等。 (2) 可变长度。一些协议采用可变长度，由协议首部中的长度字段指示。如 ipv4 的长度为前 4 比特乘以 4。类似的还有 tcp。 (3) 固定长度加上可变长度。例如 ipv6 逐跳选项(hop-by-hop option)扩展首部， 15 其长度并不包括最前面的 8 个字节1，而是等于扩展首部长度(协议长度字段)的值乘 以 8 再加上基本长度 8，如图 3.2 所示。类似的还有 ipv6 的其他扩展首部。 下一个首部下一个首部 可变长度选项 扩展首部长度 可变长度选项 扩展首部长度 图图 3.2 ipv6 逐跳选项扩展首部逐跳选项扩展首部 (4) 特殊长度。mpls (multi-protocol label switching，多协议标记交换协议)的 长度需要用特殊的计算方法。 mpls 首部实际上是一个标记栈。 它可以包含多个标记 (每个标记的长度为 4 字节)，直到栈底标记(s)的值