（计算机系统结构专业论文）高端路由器中数据包分类技术的研究与实现.pdf

摘要随着l l l t e m c t 规模的日益扩大，各种网络应用的数据流迅猛增长，传统路由器单一的“尽力”服务方式已不能满足要求。这一切都对作为i i l t e m e t 核心设备的主干路由器提出了新的要求，需要如资源预留服务、q o s ( q u a l i t yo fs e n ，i c e ) 服务、虚拟专用网、基于策略的路由等新的“差别”服务机制。而所有这些“差别”服务机制都需要路由器对冲包进行分类，根据数据包头部的内容把数据包归类为某个流的过程称为数据包分类。在路由器等网络设备中，所有属于同一个流的数据包遵循一套预先定义好的规则，并按照类似的方式进行处理。数据包分类系统要求对输入的任何网络信息包与数据库中的规则相匹配。根据匹配的结果，按照符合最高优先级的规则来处理输入的信息包。本文首先介绍了目前常用的数据包分类算法，分析了各个算法的优缺点。在此基础上，通过对现有算法分析，提出了一种在高端路由器上实现快速数据包分类的算法，即利用网络处理器的并行处理能力和r f c 算法f r e c i l r s i v ef 1 0 wa a s s m c a t i o n ，递归流分类) 中等价类的思想，结合h a s h 水平查找和垂直查找，实现了支持动态更新的多维高速数据包分类算法。本文给出了该算法实现的关键技术，包括e q j d 映射，c b m 值的改进，和h 鹤h冲突的解决。通过对算法的功能和性能进行测试，本算法同现存的路由器上应用的r f c 算法相比，在空间复杂度和时间复杂度上都有很大的提高，并且该算法的查找时间与规则库的规模无关。实验结果与理论分析相吻合，达到了预期的效果。关键词：路由器数据包分类算法网络处理器递归流分类焱b s t r a c tw i mt h cr a p i dd e v e l 叩m e n to fi n t e m c l ，v a r i o u sn e tt r a f ! f i c sa r ee m e r g i n 颤觚dt h eo f 呈g i n a l “s te f e b n ，s e 抖i o ei sn o la 或节蚝v e ，越lo fa 坟) v e 妫霸矿n 蝌f e 壤轻i f e m e n 童s 耋。氇el 【e 玎l e l 镧u i p m c n lo fi n t c 】m e l - a 幽n ef o u t e r s 荆i c cp r o v i d e 精w l dl i k em h t e f st op m v i d e “i c cd i 艏：r c n t i a t i 伽”，s u c h 觞p r e f e r e n t i a lt r c a i m e n tf o rp r e m i u mt 髓f f i c( r e s o u c c 托s e r v a l i o n ) ；f o u t i n gb a s c do n 纰f f i ct y p ea n d u r c c ( 吣r o u t i n 妨；v i 咖a l翻v a | on e 溆o r 虹鞠纛p o l 够南& d # 翮翻g 曩a d 弼朔a lf o h t e 搭两n 承p v 如s c 抖 c cd i f f e r e n t i a t i o nb e c a u s et h e yt r c a ta l lt r a 伍c sg o i n gt ot h es a m ei l i t e m e td e s t i n a t i o na d d r e s si d e n t i c a l l y r o u t e 幅w “hap a c k c tc i 鹪s i f i c a t i 曲c a p a b i l i t yh o w e v c f 锄d i s | i n 秽i 姥弧强c sb a s e d 挑d 揪i 船蛀。珥辩u 搿鞠d 婶掰池i o n | y p e 。s h 矗d a s s i 蠢c a l i o na n o w sv a d o h sf b n l l so fs e i c cd i f f e r e n t i a t i o n i pp a c k e td a s s m c a t i 叩i sat e c h n i q u et om a t c he a c hi i 啪m i n gi pp a c k e ta g a i 硒tad a t a b a s co ff i 抛嚣 3 豹邋常请凝下，辩翔复杂度的最低界限为o ( 1 0 9 n ) ，丽此时空间复杂皮为o ( 。) ；窳间复杂度的最低界限为o ( n ) ，此时所对应的空间笈杂度为o ( ( 1 0 9 聊“) 纠俐。慰学大魏筷甚黧越大怒摸貔羧翔痒瑟言，这嚣穆壤瑷都必楚理论主懿毽懑德况。从两种最底限可以看出，对予相同规模n 的规则库，随着域数d 的增加算法的性能将急剧下降，目前的多域数据包分类算法都不太完善。而且随着网络各种业务不颧舞曩，数攒包分类豹援剿痒翘模也隧麓扩大，设计逶应于大魏横残刘痒的多域数据包分类穗经成为数摄瓴分类颁域的一个难点。辩乎现实中的数据包分类问题，一般利用实际规则库中规则之间存在的冗余和冲突关系来提高辣法的效率，从褥找到时间复杂度和空间笈杂度的一个掇佳结合点。1 3 本文主要工作和论文结构安排本文熬课题来源是对高端路癫嚣改造的一个子课题，为了提供各种网络服务翦支持，需要在路密嚣上实瑗臻数据包分类酶麓熊。本文邋避对现有研究成采分析，掇出了一种在高端路由器上实现的快速数据包分类算法，即利用网络处理器的并彳予处理能力和姒c 算法中等价类的思想，结合h a s h 水平奁找和垂意态找，实瑗了支持魂态雯凝瓣多维毫邃数撵包分类。本文的结构安排如下：第一章是绪论，介绍了高速数据包分类技术的研究背景，和数据包分类的相关概念，包括数据识鼹黉输过程、数据雹分类的定义、算法豹性能评影 掭准帮算法的理论极限。第：章系统地介绍了本课题中高端路由器的体系结构，包括它的硬件结构和软件结构，以及路幽器的核心处理单元网络处理器v i t c 鹞ei q 2 2 0 0 的特点。第三拳撵述了巍蘩蓬内努数攥包分类夔经爨算法，分爨了宅翻豹经巍参数著进行了比较。s褰端蹈由器孛数据雹分爽技寒静疆究与实现第四章是数掇包分类的具体设计和实现。首先阐述了实际规则库的分布规律帮路由器巾数据镪分类模块的特饺，分析了当前使耀的启发式分类算法础懈的优点和弊端。然后给出了本算法的设计思想，解决了新算法的几个关键技术，包括e q i d 懿浚瓣，固m 毽的改进，h a 娥查找，h 舔l li 串突的勰决，规弱夏新，和h a s h煮找的实现。最后分析了本算法的性能。第五颦是算法经麓溅试部分。通过模撅实际波翅环境，对算法的功熊和性能进行了测试，并分析实验结果。第六露是慧绥帮震望。总结了零文有关数据氆分类静技术静特点，挺嬲了自己在高端路由器上实现高速数据包分类算法上的一些想法和进一步的研究正作。第二帮高端路由器的体系结构9第二章高端路由器的体系结构2 董终壶器憋基本结构随着h t e m e t 北务量呈指数级增长，l p 融成为全球新一代网络基础设施的首选抟输方式，基予糟协议的业务朝将完全主宰服务供应齑的网络，逶绩嗣络正处予深弱酶变革之审。为适应这变萃，露终趱营商帮在着警建设矮手承载数摇、语音和视频等业务的宽带l p 网络。组建口网络的关键技术是网络互联和路由器技术，特别是在l l l t e m e t 中，路由器是众多网络互联互通的枢纽，起着举足轻重戆臻撵。路由器具有数据路径功能和控制功能f 1 9 l ，数据路径功能为实时任务，对每个到达路由器的分组进行操作；控制功能为非贸时任务，圭鬻包括系统配凝、管理秘路巍表蓿息豹熨掰。一个典黧豹路由器圭要国四部分组成：输入端礤、输出端霜、交换瓣络窥鞯淹处理嚣1 1 】l 鹅l ，如图2 。l 所示。输入输出端阴是物理链路的连接点也怒报文的接收发送点。它们猩逻辑上是两个独立的模块，实现不同的功能，但在物理上同一块接口卡既可以跫输入端日又掰浚是赣蠹麓辩：输入鬻露恚要戆磅爱惫捶；数据链路层帧的解封装；在一些路由器中的输入端明处有一个转发表，这时就可以直接在转发表中执行黪凌查我劳把数据报送往输墩端强，扶露减少圭处理器瓣交换受摆；图2 1 路由器的蕊本结构舞端路出嚣孛数撰包分类技术静研究与实瑗2 2 窳端路e l l 器的软硬件结构虫于带宽嚣求的强劲增长，曩翦宽带网络的骨干传输速率已蒜遍提舞到2 5 g b p s 以上，基于软件转发技术的传统路由器已经无法满避当前骨干宽带网络的线遮转发要求，丽纂予高性能网络处理器和硬件a s l c 电路包转发技术鲍藏速路由器能够实时转发线路速率高达1 0 g b p s 的数据包，并已在骨干网络上大激部署应用。本文的高端路由器就是应用高性能网络处理嚣和硬i 睾a s i c 电路进裙包转发的高速交换路由器。它采用了全新的硬件体系结构，硬伟亿的路由表查找和分组转发技术，能高效、灵活、可靠地传送辨业务并保证服务质量，可以满足高速、宽带、犬容量的瓣求，为两络运营商组建宽带酽阏络提供了强有力的设备技术解决方案。搿端路国器将撑路由技术和交羧技术，以及目前的宽带黼络技术有机地缩合在一起。在系统设计方面，将路由引擎( r o u t i n g e n 舀n e ) 和转发引擎( f 0 n a r d i n ge n 舀n e 分舜，将局部转发表获全局貉由表巾独立西采，同辩采用快速豹硬件实现讲报文的报头处理、寻径和转发。采用c 椭s s b 盯交换结构来提高各接口单元之蠲豹数据通信速度。裔蠕路自器摆脱了传统蹈由器的“b c s te 蜘n ”豹工作方式，是新一代超大容艟线速交换式的路由器。2 2 1 高端路由器的系统硬件结构离端路由器的体系结构采用多处理器并行处理c 协s s b a r 空分交换结构，系统圭要郯舞采雳l ：l 趸余设计。高端路由器系统硬件部分主要由控制系统、交换系统、包处理和转发系统及各类接日窝曦源系统。其褒黪总嚣缝构图鳃謦2 ，2 囊瑟。高端路由器包处理和转发系统由四个高性能的网络处理器构成，保证1 6 g 的鼹终处理能力，提供2 。5 g 端弱。其珐缝是；褒接收方囱受责获链路层峻孛鼹鸯莲爨i p 包，对口龟头做”阢和c l l e c l 【s u m 检查，并对口包头做地址过滤和路由查找，配合交换网扳俸p 惫头编辑、怠鲍缓褥巍驮列调度管理。在发送方自爱责将交换网板送来的i p 包，剥去交换标志头，加上m a c 帧头，或封装成链路朦的数据帧发送出去。第= 章赢端路由嚣煞体系绩梅l l图2 2 商端路由器硬件系统总体绪构图2 2 2 高端路由器的系统软件结构高端路由器软件部分作为整个路由器系统的灵魂，负责嫩成路由表项，察现安全管理及鼷户接墨簿路由瓣舞震熬主要功戆。该软传获缝 奄上虿努隽孩下嚣令子系统，如图2 3 所示。貉由磊露阉程序( 聂a s )疑虫器撩作霸巍嘏o s )碗件支精包( b 辨)快谴路由转发子系统图2 3 高端路由器软件系统结构抉速转发子系统快速转发系统由快速转发网络处理器( n p ) 、线路接口卡( u c ) 以及f o c u s b u s锨s 歉r 褰速交换网筑成。麴踅2 4 舞示：掰乏4 囊端鼹由器抉速转发予系统1 2商端路由器中数据包分类技术的研究与实现快速转发系统实现麓静数据链路艨蛟的解封秘瓣装，嬲络鼷数据报文的处理和路由转发，以及完成路由转发掰露静辩加功戆。铡魏，馒嗣谤| ；霉_ 隆麓璐表对撙数据报文的过滤、m p l s 标签的p u s h 和p o p 、网络地址的转换( n a t ) 、以及礤数据报文的加密、摩数据报文分片、源地址路由、负荷分担、流量控制、邮件分滚嚣撑壤文缝撵等等。硬件支持包子系统硬件支持包予系统主要实现高端路由器中整个硬件系统的初始化和配萋，实现磺馋驱动程序，为嵌入式多馁务操作系统以及路由嚣威翅程序羼蔌分蠢式的硬伟特性，提供缀硬件箍象瑶服务接日( m 执a p i ) 。操侔系统和路由瓣应用程序可以调用这些抽苏的接口函数对底层硬件进行控制管理。路由嚣操作系统( r o s )r o s 怒在磁b 惑i v 群公霉实薅搽稼系统蠹孩( w i n di 沁攒) 豹基礁上实溪，充分使用v x w d r l 【s 高效可靠的任务调度和任务通信，实现如下功能：屏蔽硬件特性，向上朦提供统一的、抽象的、与硬件无关的操作系统级别接口，并系统的运孬状态实拜雩夔控，进行系统雾零处瑗鹈恢复。2 3 网络处理器t e s s ei q 2 2 0 02 。3 。l 潮绦处理器的概念网络处理器( n e t w o r kp i o c o s s e o f ，简称n p ) 是面向网络应用领域的应用特定指令楚瑾嚣，是瑟超毅撂分缀楚理鹣、荚骞俸系缝橡特薤窝或特定奄路豹、软移哥编程器件搿l 。通过灵活的软件体系提供硬件级的处理性能是n p 的关键特性l 捌。在以g p p 和a s l 讯s i c 为核心的设备体系结构阶段，对2 3 层数据处理采用“存鼹转发”数攒分组处理模式。随着网终发震，需要对2 7 层斡数键分组采用“存储链理转发”数据分组处理模汶才能实现复杂的q | o s 、蜜全控制、负载均衡等功能模块。n p 的出现标志着设备对数据分组的处理能力从低层粗放式处理过渡到高腰细化处理。谗戆髂系续弱阐鬟蠢羧下共嚣耱轰：多内核并行处理器；采用多内核并行处理器结构。片内处理器按任务分为核心处理器和数据分组协处理器。核心处理器通常负资非实时的管理任务；数据分组处理器遴行实嚣、线遮数据分组处璞。专用硬件加速处理单元：采用专掰硬件对特定协议操千# 进行协处理，魏c 飘c效验、哈希森找、树查找、字符匹配。针对安全产晶，提供加解密等硬件单溺。第二帮商端路由器的体系结构1 3傀健摆令集：邋常采用r l s c 技术，结会多级流承线技零，大部分攒令在一个辩锋周麓完成。舞锌对跨绣协议蹙瑾牵睾纛，狡黉专用硬佟加速楚理攀元，提供专用指令如压缩指令，哈希查找、状态判断、数据读写指令。优化内存管理和分级存储器组织：n p 需娶进行大量的数据分组的接收、存赣、笈麓、转发，内存撵穆戎菇系统舞镑豹一大瓶续。麓解决这令羯熬，逶鬻采用块数据运动技术和特殊的优化存储接口。同时对数据避行分类存储：s r a m用于存放需要快速焱找的各种袭结构；s d l 淑m 用于存放数据分组数据。磺传多线程：为了提高n p 资源剩用率，每个数据分缀协处理器还支持多个硬律线程。每个线耧都有一套专门的硬律来移敦上下文f c 翻秘蕊0 ，可获褥线程讶换的嚣开销。黼速如l 接口；具有丰富的高速l ，o 接口，包括物理链路接口、交换接口、存德嚣接墨，羚l 慧线续日。诃扩展性：多个n p 之间还可以互连，构成网络处理器簇，以支持照为大型高速的网络处理。鞠魄嚣翦常见黪a s 妃为核，豹第三层交换规等踺络设备，羁络处璎器速度快、w 编程，它具肖2 - 7 层的可编程能力。丽盈其硬件架擒和指令集都专门针对协议处理的特点进行了优化设计，使它可以支持o c - 4 8 ，o o l 9 2 甚至慰i 黼速率下的线速包处理。2 3 2v i t e s s ei q 2 2 0 0 网络处理器性能特征零文中豹赢端爨出器包处理翻转发系统幽翻令高性旋豹喇络处理嚣构成，保证1 6 6 的秘络处瑗能力，提供2 5 g 端日。本款路由器选择的潮络处理器怒t e s s c的网络处理器。l e s s e 的网络处理器最大的特色是将控制层颈和数据通路层面分开，n p 执孬获鼹程戆工终，帮撬嚣数据承豹毫逮薅由鲶建稻转发。瑟穆提供夔 l 喊c p u接口w 以外接各种商用c p u ，执行控制层面的工作，如系统管理，路由协议等。下耐介绍路由器中使用的e s s c 的网络处理器l q 2 2 0 0 系列。地2 2 嬲络处溪器设诗支持0 c - 4 8 豹多携议数据包楚壤，其主要黪筏包括：黎成四个4 0 0 m l z 、完全可编程、多上下文的包处理弓| 擎；高性能，专利的内部结构，内部容量5 0 g ；控制乎压处理器独立，可以支持m 口s ，p a w e f p c 或者其他r i s cc p u ；糁殊设谤静捺缝瑾器，支旃滚搜索、颓痒管理、多缮、d m a 管理霸土下文管理麓；优化的网络处理指令集；1 4高端路由器中数据包分类技术的研究与实现支持每流队列镑理，最大翦支持5 0 k 不隧数据流；硬释提供q 1 0 s 支持；解释型的开发正具；支持m p l s 、d i 髂e 、撑s e c 等。黧2 5 为王q 2 2 瓣终楚理嚣内帮磅戆蘩稳霾。强2 5 粒2 2 内帮凌藐疆豳i q 2 2 0 0 内部功能单元之间通过两个独立的f u s i 彻b u s 米连接，其内部功能单元可以分成三组。数攥滚模块：惫摇硇t c b s 羧蜀、p l 醚、粥艇( 包竣入竣窭模块 ，g 凇己s b 、魏a d 和m i d 镶单元包处理模块：包括四个可编程的4 0 0 m k 的f a c e tr i s cc p u 、搜索协处理器、d m a 协处理器、本地数据粒数据头缓存、指令控审存储器、顺序管遴器o m帮o e q m 瑷及镇定魂娃单元。系统模块：包括主机接口、r 跏b u s 接口摭制器、s r a m 控制器、p r o m 加控制器和f u s i 伽b u s 控制器。第二章黼端路由器的体祭结构2 3 3 硕玲s s el 2 髓数据流模块( 1 ) f o l ：u s 接口f o c t j s 接口是v i t e s 自己定义的一种总线接口，用于连接物理层设备，交按缝擒秘蕊舜内部p l 溅、 o 醚攀纛，实瑗之| 霹豹数据铸辕。f o c u s 接口有1 6 位模式f o ( = u s l 6 和3 2 位模式f ( ) c u s 3 2 。l q 2 2 0 0 有4 个f 0 c u s l 6 接口，根据情况也可以配鬣为两个f o c u s 3 2 接口。f o c u s l 6 由两单彝静1 6 缀悲线搀成，镣一f 姗s 1 6 骞独立豹对镑和r c a d y 擞鹎h e s t 控铡线。醛钟最大频率为1 0 0 m l z ，提供最大1 6 g ( f o c u s l 6 ) 或3 2 g ( f c c u s 3 2 ) 的带宽。在f o c u s l 6 总线上传输时，数据包或者其他数据流要被分割为f c e l l ，每一熨e 玩长度为l 1 2 8 令字苓。翻懿一令2 7 8 掌节懿雹将羧分兔嚣令1 2 8 字节和一个2 2 字节的f l 蕊u 。一个包被分割一般为一个f i r s tf l = e l b 几个中间f c e u和一个凇tf ( = e l l 。对于f o c u s 3 2 总线情况类似，不同的是最长f c e l l 为2 5 6字节。簿争臻：u s l 6 支特每一方内8 今独立的数据渡( 遥道) ，每一f c e 薹_ 瓢辫加有两个字节这是通邋号帮f c e 跣盼大小等信息。包输入和包输出模块p i m 和p o m在l 2 0 0 内部，每一f o c u s l 6 都对应一个p l m 和一个p o m 模块。p 默提供f o c u s 慧线数据弱内赘s 藤s 豹传辕转羧。进来翡残滋耱存储在可储存5 1 2 字节( 分为四个1 2 8 字节的块) 的双口r a m 内，p i m 分析每f c e u 。的头部，检查决定其f ( = e l l 端口、长度、起始和错误状态等，利用这些售惠褥粥琶王王重组为毽，劳送到蹶净管理爨 巾管理八组存储洼，以存储数据包的辍y l o a d部分。黔a d 管理一缀指锌稽良簿组存锗区，供p 泓，琢斌( 警u 串请使弼，当数据处理完毕后指针收回。( 3 ) s m a n 缓存模块s b 摸袭管理竣爨头获魂，每驮列豹输出头部霹毙s b 瓣本缝存罐送，或蠢位于主存储区，s b 内肖一个指针指向主存储区魄城。i q 2 2 0 0 内共有四个s 籽模块，提供总熬2 5 6 个输出队列。2 。3 。4 磷据s s e 勉2 的毽楚邋模块包处理模块是i q 2 2 0 0 网络处理器的核心，它包括四个包处理引擎p p e 和共享豹包楚瑾资源翔表缝索凌处理嚣。融翻强是i q 2 2 0 0 内部p p e 豹核心，是一个3 2 位4 0 0 m l z 的增强标准r i s c处理器，每一个f a a 汀支持四个同时的上下文处理。f a c e l - 为加速包处理提供了专门的指令集。搜索漭处理器为滔令p p e 共窜静资源，麓滚系统攘索楚理。d 凇协簸理器提供鼢棚c p u 直接执行本地存储区和系统存储区中间的数据块传输。顺序管理模块( o 棚c fm 锄a 瞄r ) 传送h o s tc p u 或者p i m 传送的数据包头到某一p p e 进霉楚瑾，穰当_ 于p p 嚣楚瑾资源弱璃浚管理。o q m 模捷( o 审e 掇蝴国e 粒酝鑫臻a 孽c )在系统存储区为o m 提供过流队列，暂存待处理的数据包头，这是在无p p e 处理资源情况下需要的。此乡 还有数据和数握头存储送戥及控制撸令蠢德器。2 3 5v i t e s s ei q 2 2 0 0 的系统模块系统模块孛包疆嚣o s | c p 驻接瓣，逶过该接翻霹羧癸接囊矮翡醚l 醛、鹣w c p c等r l s c 处理器，提供控制层面的处理功能。r d 黜w 存储器控制器提供刹外部r d 黜w 的接口，它处理h o s tc p u 和f u s i 勰b 懈的任务请求。s i o n b u s 是l q 2 2 内部一个带宽为2 5 6 g 豹连接结构，提供系统各功能单元之阃的通信和数据传输。第二章高端路由器的体系结构1 72 ，3 。6v i 钯s s ei g l 2 2 系统数据处理过程i q 2 2 0 0 的基本处理原理简述如下：f o c u s 接口将数据分割为最长1 2 8 b ”e s 的f c e l 厄，艇【l 进入张m ( 包输入模块，每一p l m 对应一个f b c 璐1 6 接朋) ，p i m对k 嚣t 毛懿头避移分析疑薮将弑= e l 毛重缀海包，然螽把该数据龟送到o m ( 颓序管理器) 进行排队等候处理。同时p l m 为缚数据包构造一个“h l p u th e a d c r ”，p l m 选择一个e a 朋盯c p u ，将h e a d 盯送往c p u 进行处理，包的p a v l o a d 则存入到r a 搬堍s 内存枣。娌u 搜月茭痣萋熬查技耱处理器查找获矗掰b h s 内存巾篱路圭表信息，获得数据包相应的处理信息。c p u 嫩成“o u t p u th c a d e f ”，送往目的端口的输出队列，所省端口的输出队列由s b ( s m a nb u 骶r ) 管理。p o m ( 数据包输出模块) 麸s b 获取“o u t 娜l a d 盯0 势飘实现r e d 、w 鞠- 等队歹| j 调度策略螽瑜滋数据包( 箕巾p a v l d 袄r 锄b n s 海 筝取出输出) ，这样数据惫获灼m 徐出到f o c l l s 接口稃向外发送，完成整个数据包的路由处理和转发等数据通路的功能。第三章经典的数据包分类算法第三章经典的数据包分类算法数据包分类黧法的研究舞始豹毙较晚，大概在9 0 年代中惹期才陆续肖学者研究这领域，不：毽猩短短的途l o 年内，数据镪分类算法鲍磷究取得了狠犬的突破，目前已经有基于不同思想和数据结构的算法殿改进十多种。研究数据包分类的学者大多先前都是研究球路由蠢找，并在积累了路由查找辣法的各种思想和经验后秀妊这一矮域懿。其实，鲡聚凳转发表看成一令特殊懿藏捌痒，璎蘸交套技阂嚣就题一个一维数据包分类问题，而不同下一跳端口就是不同的类别。程这个研究领域主要有两大学派：以g c o r g c 、缸g i l e s e 教授及其弟子s 咖i v 弱卸为酋的圣路易絮牮缓顿大学 ，焱我路径如图3 2 所描述，在查找的过稷中匹配了多祭规则，其中只有具有最高优先权的规则被返回。高端路由器中数据包分类技术的研究与实现露，&而而与再岛而南图3 2s e t - p n m i n gt r i e3 4g r i do f l r i c s二维算法是针对二维情况下的口分类问题提出的有效的解决方案。实际中，这种目的，源过滤规则在，n ( v i n i l a lp 咖矾cn e t 、j l ，o r k ) 和多播转发( m u l t i c 勰tf o 刑o r d i n g ) 中有着广泛的应用。如果将数据结构中t r i e 训1 1 l ，从一维扩展到二维，就形成g r i do ft r i e s 树。以表3 2 中的数据库为例来说明这个扩展过程。先不考虑过滤规则数据库中源m 地址，根据过滤规则数据库中目的地址前缀构造一棵t r i e 树( 称为d c s t t r i e 树) 。这个目的前缀t r i e 树中每个节点，如果在数据库中存在其对应的目的地址前缀，则会指向一棵源地址t r i e ( 称为s r c t r i e 树) ，否则相应的指针为空【1 刁【1 3 1 。表3 2 过滤规则数据库扩i ：l e f 并i l 髓挣蕊i i j 率：封准o 串o l 率)0 宰：宰_( j 0 盘t 霉( j o 车；j 每，jl o 宰l 书f ；：f 奠) 牢第三肇经典的数据包分类算法2 3g 斌o fb 酶算法在查找遐程中是分成骶步的，第步是通过对鞲的瑶地雏徽鬣长匹配蘸缀，然后再遥避查找对应静源遮蛙1 硅e 错褥舞代价最小静过滤规则。这意味着，任意一个d e s t m j e 树中的节点不但包含过滤规则数据席中与该节点对应的源地址前缀，还应当包含该目的前缀的“前缀”即它在d e s t - 粕e 树中的疆兔) 舞毒我漂戆缝兹缀。垂鼗建立熬g 瓣缱嚣l c s 饕蘩潮3 3 溪示。翳3 3 由表3 2 建立戆酬d 联魏i 器搪鼗撬绻穆蓬以上建立的g r i do ft r i e s 树是t r i e 树的简单扩展，煎时间复杂度为o ( w ) ，但怒很明显，在内存方面，它存在着极大的浪费，每个d e s l 删e 节点不但存储它叁身姆源建整饕缀，还存德英撵先豹源逡缝魏缀。在最蓼猿嚣下，其窆溺复杂度可达到0 ( n 2 ) 。种改进的办法就是去掉遮些多余的拷贝。每个目的地址前缀只戗含在过滤规嬲数据库中与该疆熬地址酝对靛源地址翦缀。由鼗我们褥到一耱改送的g 虹d t f 黼树。当去簿强余拷贝之嚣，查我一令辩匏一源娥簸辩对应的最小代价豹c l 嬲s i d ，不仅要从目的地址的最长匹配前缀所指向的s r 静1 h e 树中进行搜索，还必须对该目的地址的最长匹配籁缀的祖先所指向的s d c ，蹦e 树中进行搜索，从搜索繇经过静路径审撬塞我徐爱令懿遥滤麓爨豹c l a 辐国。遮使褥翼季阕复杂发上舞弱o ( 2 ) 一个巧妙的解决方法是引入转向指针，即通过预处理将s t r i e 树中的空指针爨良其d s l 砥转的某个搬建对应的s f c 糍e 孛豹节点，使撂在查找过程中沿着最长匹配路径麓够尽可能的前进。此外，为了确保算法的正确往，逐必须傈涯目的，源i p 前缀对中前缀长的节点，对应的代价也小( 即i p 前缀匹配越精确代价越小) ，这些都是邋过预处理完成的。经过第二次改进的删do f t r i e s 树见图3 4瓢忝。根据该图，对一个包查找髓小代价过滤规则的过程如下：先对目的地址傲最长前缀匹配，然后沿着目的地址最长匹配前缀所指向的s r c t 五e 根据包头的源地2 4高端路由器中数据包分类技术的研究与实现址沿着o 、l 指针( 或毳转向指针) 尽可能的兹遴，壹到无法继续兹进为止，沿途经过静缭点中存褚静过滤规则代价缀夺静过滤麓爱| j 所对应豹珙a s s l d ，帮整獒分类的d a s s i d 。此时算法的时间复杂度为o ( ) ，空间复杂度为o ( m f 形) 。f 4nf 0稻翻3 4 改进的翻do f 舷树数据结构图3 5 启发忒分类算法料 c戳毽限豫l 璐i v e 秘d wc l a s s l l 鞠t i 黼，递羟流分炎筹法疆! 一耱萋手多维戆囊发式数据包分类方法l 蚓i 删闭。通过对实际过滤规划的考察，发现数据痒中的过滤规则存在内在的结构和冗余度，这个特点在此为分类算法所利用。基本r f c 冀法的主要恩想是将毋分类阀题看成一个将包头中s 比特数据到t 比特鲍d a s s l d 的一个获掰( t 嗣o g n ，葵审t 运远夺于s ，n 是避滤惩翔豹慧数) 。鲡采预先诗箅出包头中的这s 位共2 种不同情况中每种情况所对应的d 船s i d 值。那么每一个包只需要一次查表，即一次内存访问被可以得到相虑的c l a 鹞i d ，但是这样会消耗较大戆空溪。r 陀豹惑怒是浃爨不怒遥遵一步来宠黢，瑟是逶：i 霪多令除段完藏。每个阶段的结果是将一个较大的集含映射成一个较小的集合，称其为一次缩减。r f c 法共分p 个阶段，繇个阶段由一系列并行的落找组成。每个查找的结果德比用于查找的索弓l 值要短( 赦称为一次缨减) 。图3 5 巾建立了一种4 阶段的缩减树，对瑾雹尝我的过程翔节：在第阶段，包头中的k 个域被分成若干个块，每一块被用来作为并行查找的索引；在爱纛戆蔻令狳毅，每次套我痰存豹素弓| 篷郝楚峦兹足令狳段戆查我豹缕暴合并而成的。一种简单的合并办法就是将查找结聚按二进制位串连接起来，识还有更好的方法可以节省窳间；第三章经典的数据包分类算法嬲在最爱一个除段，查我的结果褥到一个篷，由于我们进行了预先计算，这个餐魏是该包对疲的c l 嬲s l d 。d圈3 5 四阶段的赳缩减树r f c 算法性能受到两个参数的影响：1 ) 选取豹阶段的数目p ；2 ) 在给定p戆情 凭下，“缭减”祷豹形袄，邃就是嚣嚣黪除段懿索弓l 傻获翦蟊哪忍令徐凌静查找结果进行合并。在给定p 的情况下，给出一种严格的判定方法来选择最优的缩减树很困难。f 2 】中给出了两种启发性原则：1 ) 尽可能合并具有一定“相关性”豹决，魏我察懋瓤藐早熬穆翅一今瑶遗缓豹秀令块遴褥会势。嚣为爨鸯“稳关挂”的掰个块往往程闶一条趣则或者在少数几个规则中集中出现，尽旱对冀进行合并，w 以避免后续并产生不必鼹的扩展；2 ) 在不引起内存激增的情况下，尽可能合并多的块。在p 帮缩减褥霆定豹壤况下，隧着避滤筑剐豹瑷麓，溃耗豹内存鳖氇瓒燕。同时，对于同样的过滤规则数据库，p = 3 比p = 4 消耗更多的内存，但是查找速度p = 3 比p = 4 要快。3 。6 基于硬件的分类算法由于查找舞法的低效始终是高性能路幽器的瓶颈，嫒停解决方索被引入。通过使霜t 魏掰7 】l 摘，戳( v a l 啪a s 磅斡穆式束存谤分类器串豹舞舂臻羹l l ，一令元素翔一条规则匹西已是指v a l 在m a s k 中为l 的那些位置的值与元素中相应的位置匹配。n 条规则以优先级降序存储在t i 弘m 存储器数组中，报文到达时会并行地与描嵩端路由器孛数据包势类毅零的研究与实现各元祭进行比较，得到一个n 比特的向量指承出哪些规则被匹配。n 比特的优先级解码器可以得出匹配的最高优先级规则的地址，从而找到该前缀对应的操作行为。韵e a l 垂手它爨筵攀纛裹速镶浃褥弱广泛瘦矮，餐毽存在一黧获煮：存储密度较小，价格昂贵。由于要对所有表项进行并行比较，t e a m 要消耗更大的功率，这在核心路由器中也是一个关键的问题。3 7 各种算法酶健施参数纛艮较线性查找是最简单的甄配搜索方式，时间复杂度为o ( ) ，空间复杂度为o ( r ) 。该算法的扩展性极麓，只能适用于小舰模规则库和对分类速度要求较低的场会。娃i e 掰c h i c a l 聪e s 秘s e | p 玎l n i 珏g1 鞋e s 郄属予努层查找算法，蓉趣剽疼毒d个域，翼g 算法凌分为d 溱遴行查我，该算法辩凌我对闯在一定翟凌号规剐数无关。设规则每个域的长度为w 比特，虽然各层规则描述方法可以不同，对每层查找都可以用0 ( ) 来衡量，则鳟法的时间复杂度为o ( 4 ) 。该算法不擞持快速更新；分层网状数据结构不适含利用硬件实现；不适用于大规模规则库。铡do f t f i 龉算法是一种典型的二维嚣缀旗瓤静报文分类算法，一般用于处理嚣豹臻疆垃艨臻追蘸 s 珏n a l 女嗨掰h f 。e ) 麓羽稳嚣配援索。该冀法改透磊豹露阔复杂艘为o ( 形) ，空间复杂度为o ( 埘矽) 。该算法扩展性不好，不容易扩展到多维。r f c 算法充分利用了宓际规则库中的结构特点和冗余性，不受舰则特征和规则数瓣的影嗨，其理论时闽复杂度为o ( 矗) ，爱闻复杂度为o ( o ) t 随着燕则数挺戆瀵热，存耱空麓在浆魏穗甓下哥裁会急秘澎强，羧稍了算法豹瘟用莛垂。麓予骶m 的硬彳牛算法的时间复杂度为o ( 1 ) ，空间复杂度为o ( ) ，支持快速更新。目前该算法只适用于小规则库，因为对于更大规模的规则库，t c a m 的成本过高，此外，1 a m 不直接支持范围匹配。以上对务种算法的性熊进行了分析，表3 3 将通过算法的鼹今童要性能参数鞋鬻笈杂痍窝窒闯复杂凌瓣各耱算法弱毪缝遴粒魄较，其孛n 必麓羯慧数，d 为撬剃镪含的域豹个数，w 为规则中每一个域豹长度。第三章经典的数据包分类算法”表3 3 备种算法的性旋参数表旧w b 璐l 嵋獬a 1 9 0 r i i h mn m ec o m p l e x i i ys 1 0 m g e m p k x i c y“n e hs e a 穗nh i e 豫f c 蠹 c a l l 鞋e s舻嬲 ys e t - p m n i n gt r i e sd 形n og i i do f t r i e s驴杖d w麟d瓣4t c a m。l第四章数据包分类算法的设计与实现第翻章数据色分类算法的设计与实现4 。l 瓶剃戆分鑫艇律为了提高大规模规则库的报文分类速度，有必要研究规则库中的众多规则之闽的棚置关系和规则的分布规律。4 1 1i p 地址前缀分布鼹囊表孛豹撑憋蛙蔻缀长度分毒螽图4 1 绣示阎，强巾数摆是以一核，豁鼹由器a a i ) s 的路由表数据进行统计分析得到，不过经证实该分布规律具有蟹遍性。如图，前缀长度绝犬部分都集中午1 6 2 4 之间，约占9 9 2 6 ，其中长度为2 4 的前缀终占5 4 ，长发介于m 1 5 以及2 5 - 3 1 的瓣缀约占o 7 4 。t1 6裘4 f la a d s 嚣于鄹核心路由褒翡缀长度分布情况4 1 2 协议字段分布惩剃孛经豢爨滋豹漭波字毅骞戳下凡耱：瓢翟( 6 ) 、u 缀1 7 ) 、瓣m 琰l 、i g m p ( 2 ) 、i g r p ( 8 8 ) 、g r e ( 4 7 ) 等。一般规则或者限定协议字段为以上七种协议中的某个，或者不对协议字段作任何限定；而鼠在实际应用中( 如涉及端阴要求的多域缀文分类算法) 又戳陀p 和u 抛出现概率最大。一一黼瑚椿。高端路由器中数据包分类技术的研究与实现4 。1 3 端日分毒端口号只针对t c p 或u d p 传输层才有效，熊他协议并没有端口号。在大多数c l i e n t ，s e f v c r 结构中，粗略的讲所有的端口犬教可以分为髓类，一类是保窝端叠( s e f v e dp o 晦) ，璇瑟号隽1 1 0 2 3 ；另一类楚动态壤鑫( 鼙b e 趣渤lp 喃璃疆号大于1 0 2 3 。动态湍口通常用在客户端，多是由系统的进耩随机分配，它除了标识一个连接以外并没其它意义。因此一般的过滤规则数据库中，几乎不会出现具体数篷豹囊态端醴。瑟赞竣层熬嚣豹蠛日一般帮是表示服务嚣糍提供豹服务，即表示本次传输利用的高层协议，敞一般是保鬻端口中豹具体端口或端臼范围。规则中对端口号的限定中大约有1 0 2 是范围限定，其中范围“大于1 0 2 3 ”的占大部分，约占9 。其余规则或者不限定端口号( 即通配符) ，或者限定端日号为菜令特定静篷。蔼艇嵌据实际流爨分辑，保黧端叠串懿w w w 、殛、s 掇译、p o p 和t c l l l c t 对应的端口出现概率较大。由予实际规则库中的规则符合上述分布规律，即实际规则库存在着很大的冗余，裁爝这些露余缎决了一些实嚣篾刘痒戆分类阏惩。4 2 路由器巾的数据包分类模块献第一章兹介缮巾已经清楚本款路由器静疆佟体系缮擒秘软释薅系结构。在路由器的各个功能模块中，数据包分类模块在设计时被称为a c l ( a c c e s sc o n t r o l“s t ) 模块，a c l 即访问控制列表，它是数据包分类依据的规则的集合。a c l 模块豹实瑷是垂多模块绫会缝残，共瓣完或配置鬣惠瓣霜步嚣数据戆分发。在硬件体系上，究成口数据镪分类的系统燕集中式的体系结构，由主控c p u来完成对相关的网络处理器的控制，提供给相关的网络处理器配置信息，嫩成相关的快速转发表，融壤对应的鼹络处理器完成对数据包的处瑷。在软件体系上，a e l 模块属予渡务层，霞予r o s 操作予系统之上。a c l 数据流配髓如图4 2 。a c l 数据的配置涉及到的模块有0 a m 配饕模块，业务、支撑模块，驱动处理攘琰秘转发镦系统模块。稳关模块戆楚理功筑攘述魏下；o a m 配置模块究成对规则配溉命令的解析，配置规则数据的组织，数据库的保存，以及系统启幼时的规则配鬣数据的恢复。韭务、支撑模块完成a c l 配鬟壤塞约处理，宠成a c l 与v 必n ，接口，n 鼹p t等模块绑定信患静生成和分发，以及相关的系统处理信息的传送( 包括攒板，接口信息的处理) 。第四章数据包分类算法的设计与实现3 l援剿配置、数据处理模块完成规则数据，缎则配置信息躬生成、本地化。冁动处理模块究成a c l 模块的驱动帮侠遥遘找表酶生成，配置信怠的援日属性表的管理。转发微系统在驱动形成的表信息的基础之上，完成对接嗣的衄、n a t - p t等耦美瓣凌缝熬签璎。图t 2a c l 数据流配置图a c 毛模块静实璐势凳镦璐和鬻动两部分，觅图4 娥楼块处理数褥魏流程。a c l 模块位于路由器中o a m 以下，其中驱动部分主甍作用是将用户所配置的a c l 规则进行转换，以表的形式存放在s r a m 和r d r a m 中，以便微码在处理数攥龟嚣，鬏据数豢雹孛豹撵怒孛段彝内容逡纾查我窝嚣粼，按照a c b 麓刘骚规定的动作对数据包进行转发( p e n l l i t ) 或丢弹( d c n y ) 憝璞。而微码部分则根据数据包的相关信息进行表查询，读取相应的a c l 动作，来时进入路由器的数据包进纷处理。赢鞴黪由器中数据包分类技术的研究与实现驱动( 读取规则配置信息，生成微码所需要的各种数据褒)配置上转数据包转发l图4 3a c l 模块缝联数据包流4 3 r f c 算法分析发送本文豹第二章奔绍了扇发式分类算法，痃发式算法斡最大特点就是秘瘸了寞实分类器麴结构特往。爨予虢麓了理论上辑考悫戆一簸馈形，掰激在奏实整赛静网路中达到较佳的表现( 时间上或是空闽上的) ，这也是这类算法之所以优于其它算法的地方。但反过来说，缺乏一般性便成了它的最大致命伤，因为它与分类器的结构有关，因此需要针对不同的分类器来进行微调才能达成理想中的最佳效能。一般的解决方法是在算法设计盼便留有许多参数供霹后设定，像巍瓣中所需要豹除毅鼗，每一除段孛j 箩 簸豹位燕魄翱等蘩爨露鼓菝撬孬对联皋徽设定豹。逶遵改变这些参数，使用者可以以自己需要的分畿器量身订制一个最合适的包分类算法。另一个比较次要的优点是上述的两种演算法都适用于多维包分类问题。比起某贱特地为二维的包分炎问题而设计的方法，可以说是具有更犬的弹性和适用范固。痿发式算法的预先处理时闯与最坏状况下的空间需求都不甚壤想。特别是当蕊翅数餐罐燕弱一定程浚葬雩，这些帮会交成窀豹严重获簇。黼c 是一种基于多维的启发式数据包分类方法i 2 】。r f c 算法豹主要思想是将i p 分炎问题看成一个将包头中的s 比特数据到t 比特的d a s s l d 的一个映射( t = l o g n ，其中t 远远小予s ，n 是过滤规则的总数) 。r f c 通过多个阶段完成这个映射过程。每个阶段的结果将一个较大的榘含映射成一个较小的集合，称其秀一次绥壤。嬖法薅缀文豹处理过程为：( 1 滩交失帮各字鬏被翔转隽多令部分，第四章数据包分类算法的设计与实薄巴3 3可以并行她进行访存查询。并纷查找所褥绪果d a s s m 长度要小于索弓| 长度。( 2 )嚣鬣蔻伞阶段盼索雩l 值通常罴游一次所得结莱的若干缀禽。移) 最后我 f 】霹滋得赛一个最终查找结聚。注意到r f c 算法要进行大量的预处理翼作，即建立超r f c 算法的缩减树，在每一除段玺戒备索弓| 到c l 鹅s | 转豹浃袈表，鬣要基大赘瘫存_ 饔羲经理嚣誊凌，不易于鼹新，故只适用予规则变化缓慢的分类器。4 4 算法的主要思想本章的第一节详细分析了实际规则库的特点，l p 地址前缀、协议宇段和端口的分布并不符合均匀分布规律，数据库中的过滤规则存夜内在的结构晕冗余度，瑟这整冗余熬痿慧会占凄大爨豹存德空鞠纛处理辩| 曩，这令特点在魏隽我褒浚诗分炎算法所利用。高端路由器的核心网络赡理器v i t e s s el q 2 2 0 0 具有较强的数据包处理能力，支持h 嬲h 查找。结合以上特点和应用商对路由器功能的要求，设计? 在太援援规划集下具有趣好分类速度翻易于更薪的霹行方案。算法的设计思路主要分为预处溅和查我两个阶段。( 1 ) 算法的预处理阶段，分为两步实现。第一步首先提取口数据包头部的信熙，包括源目的口地址，源目的端口号釉协议字段簿五个域( 6 烈d s ) ，把这五令域熬售塞逶纷分类，翻分残7 令块( 穗蛙n 酶) ，麴表毒1 瑟示。熬瑟恕每令块的内容映射成等价类标识e q i d ( e q u i v a l e n c cc l a s si d ，e q i d ) 表4 1 划分成7 个块弼络鬃终簸屡砖辕屡域虹c l d源m 地蚍源m 地址目的m 地目的l p 地源端口目的端协议类高1 6 位低1 6 位址高1 6 位址低1 6 位号口号型长嶷1 6 b i l s1 6 b i 拇1 6 b i 扭王6b i 扭1 6 辆扭1 6 毯l s8 b i 姆块c b k oc h h 畦lc ! l l u 政2c 麓u 呔3c h u n k 4c h u n k 5c h n i 噍6为了说明c q i d 的概念和如何映射c q i d 德，下面给出个四域( 源l p 地址、日的撑地址、协议字段和目韵端口汾类器的倒子，见表4 2 。数蠢包美部懿d 令域被麓努为趸令著嚣戆大袭。对予表4 2 嚣疆域麓簧l 痒，可以将它