（计算机科学与技术专业论文）高速ip分组分类算法及其实现技术的研究.pdf

国防科学技术火学研究生院学位论文 摘要 当前，因特网f 呈现两方面的新变化，一方面，因特网f 同益变得拥挤： 另 方面，因特网上的用户正呈现许多不同的种类，它们从安全、性能、可靠性 方面对因特网的期望是不同的。 为适应这些新变化，i s p 一方面必须升级因特网骨干网络的速度，一方面必 须筹划新的有差别的网络服务，以满足不同用户的需要。由于光纤技术和d w d m 技术的发展使得链路的速率不再成为瓶颈，而路由器作为连接链路的节点一 一的性能会成为主要瓶颈。这主要由于路由器对于每个输入分组需要执行许多操 作，包括十分复杂的分类操作：它们需要对每个输入分组执行最长前缀匹配 ( 1 0 n g e s tp r e f i xm a t c h i n g ) 以发现其下- - 跳( n e x th o p ，n h ) 地址；需要对每个输入分 组执行多维分组分类以便在执行q o s 调度、多目转发( m u l t i c a s tf o r w a r d i n g ) 、虚 拟专用网( v i r t u a lp r i v a t en e t w o r k s ，v p n ) 、基于策略的路i 拍( p o l i c y - b a s e dr o u t i n 9 1 等任务时区别对待不同的分组。 分组分类是路由器根据p 分组的多个域，从分类器数据库中匹配每个输入 分组，确定分组转发规则的技术。分类器为实现因特网新业务提供了统一的方式， 分组分类是因特网提供一切有差别服务和其他新业务的基础，高速分组分类问题 是具有重要现实意义和理论价值的研究课题。，十4 单纯根据m 目的地址的口路由查找是因特网环境下一维分组分类的主要形 式：包含口源地址和i p 目的地址的二维分组分类，包含口源地址、口目的地 址、协议域、源端口号和目的端口号的五维分组分类是因特网环境下多维分组分 类的主要形式。 针对p 路由查找问题，本文提出基于l s o ( l e n g t hs e g m e n ta n do f f s e tt a b l e l 的高速d 路由查找算法：针对多维分组分类问题，本文提出基于s p l s ( s h o r t e r p e r f i xl e n g t hs p l i t t i n g ) 的高速分组分类算法。 f 基于l s o 的高速i p 路由查找算法属于一维分组分类算法，主要适用于核心 路卣器( i p v 4 ) 环境，同时也兼顾企业级路由器环境。其主要特点是使用可变大小 的段表和偏移量表，使得算法能适应s r a m 和f p g a 芯片内存储器容量的变化， 在不同的情况下可以进行不同的选择，当段表长度取较小值时，偏移量表占用存 储空日j 大，这时可以使用图论压缩技术对偏移量表进行压缩。l s o 算法不仅适 合于硬件实现，而且适合于软件实现，本文给出了该算法的具体实现方法，并对 算法的存储代价和查找性能进行了详细的分析和模拟。段表长度可以根据实际路 由表进行实时计算，使得存储代价达到最小，本文给出了计算段表长度的简单方 法和硬件实现时段表长度的协商机制。用硬件实现时，l s o 算法具有查找速率 快、更新速率快、所需存储空间少、硬件实现代价低、硬件实现简单等特点，是 一种理想的适合于1 0 g b p s 端口核心路由器环境的查找机制。 第v 页 国防科学技术人学研究生院学何论文 基于s p l s 的高速分组分类算法属于多维分组分类算法，s p l s 技术是一种 以较短前缀长度将大分类器集合分割成许多小分类器子集合，使得分割后的小分 类器子集合可以使用已有的快速口路由查找方法进行查找的技术。s p l s 以多位 键树( m u l t i b i tt r i e ) 作为实现时的基本数据结构。若以多重链表实现多位键树，通 过分析和模拟，度为4 的多位键树( 四叉键树) 其性能达到最优。为改善性能，可 以将节点的所有子节点用连续存储器存储，实验显示，它比使用多重链表实现时 性能大大提高，对于2 0 k n 4 0 k 的分类器数掘库，其平均分组查找速率达到 4 5 9 8 m p p s ，存储空间为3 m b 6 5 m b 。为进步改善性能，可以使用路径压缩 键树和级压缩键树减少节点数。将基于s p l s 的高速二维分组分类算法扩充至多 维时，需要根据具体维的特征进行特殊处理。 另外，本文还设计和实现了一种p n l 核心路出器网络层输出控制部件。p n l 核心路出器是一种用于高速因特网主干的口路出器，它采用高速分布式路出体 系结构和先进的高速交换阵列，线速转发d 分组。核心路由器网络层输出控制 部件负责从交换模块接收并处理分组。、 、 关键词：分组分类，i p 路由查找，l s o ( l e n g t h e ns e g m e n t f a b l e 赫do f f s e tj a b l e ) s p l s ( s h o g e r p r e f i x e 学、跚讯堡蓟 ， f 键树，多位键树，n 叉键树，核心路由器。 第v i 页 a b s t r a c t i nr e c e n t y e a r s t h ei n t e r n e th a st r a n s f o r m e df r o ma l l e a r l yd a yl o ws p e e d n e t w o r k c o n n e c t i n gp r e d o m i n a n t l ye d u c a t i o n a l i n s t i t u t i o n st oaf a s t g r o w i n g c o m m e r c i a li n f r a s t r u c t u r e t h ed i v e r s eu s e r so ft h ei n t e m e tn o w r a n g ef r o mo r d i n a r v h o m eu s e r st ol a r g ec o r p o r a t i o n sc o n d u c t i n gs e n s i t i v et r a n s a c t i o n s t h ee x p e c t a t i o n s i nt e r m so fs e c u r i t y , p r i v a c y , p e r f o r m a n c e ，a n dr e l i a b i l i t yo ft h e s ed i v e r s eu s e r s a r e d r a m a t i c a l l yd i f f e r e n t r e a l i z i n gt h i s ，i n t e m e ts e r v i c ep r o v i d e r s ( i s p ) n o to n l yi m p r o v et h es p e e do f t h eb a c k b o n en e t w o r k ，b u ta l s oe n v i s i o nn e wd i f f e r e n t i a t e dn e t w o r ks e r v i c e ss u c ha s v i r t u a lp r i v a t en e t w o r k s ( v p n ) t h a tc a nm e e td e m a n d s o f t h e f u l ls p e c t r u mo f c l i e n t s t h el i n ks p e e dh a s n tb e e np e r f o r m a n c eb o r l e n e c kb e c a u s eo fi m p r o v i n gi nf i b e r o p t i c sa n dd w d m ，b u t i pr o u t e r sc a nb em a i np e r f o r m a n c eb o t t l e n e c kb e c a u s eo f r e q u i r i n gm a n yc o m p l e xo p e r a t i o n ss u c h a sf a s tp a c k e tc l a s s i f i c a t i o n p a c k e tc l a s s i f i c a t i o ni sat e c h n i q u et om a t c he a c hi n c o m i n gp a c k e ta tar o u t e r a g a i n s t ad a t a b a s eo fc l a s s i f i e ra n ds p e c i f yf o r w a r d i n gr u l e sf o rt h e p a c k e t s t h e c l a s s i t i e r sa r eap o w e r f u la n du n i f o r mw a yt oi m p l e m e n tn e wn e t w o r ks e r v i c e st h e i pr o u t i n gl o o k u p s b e l o n g s t oo n e d i m e n s i o n p a c k e tc l a s s i f i c a t i o n ，a n dt w o d i m e n s i o n p a c k e tc l a s s i f i c a t i o ni se x e c u t e da c c o r d i n g t oo ni ps o u r c ea d d r e s sa n di pd e s t i n a t i o n a d d r e s s ，a n df i v e d i m e n s i o np a c k e tc l a s s i f i c a t i o ni se x e c u t e da c c o r d i n gt oo ni p s o u r c ea d d r e s s ，i pd e s t i n a t i o na d d r e s s ，s o u r c ep o r t ，d e n s t i n a t i o n p o r t a n dp r o t o c o l f i e l di pr o u t i n gl o o k u p si st i m e c o n s u m i n gb e c a u s et h ep a r to fa ni pa d d r e s su s e di n t h e l o o k u p ，i e t h e n e t w o r ka d d r e s s p o r t i o n ，i s v a r i a b l ei n l e n g t h ，a n dp a c k e t c l a s s i f i c a t i o n si sa l s ot i m e - c o n s u m i n gb e c a u s et h e k e y s u s e di nt h el o o k u pi sl o n g i nt h i st h e s i sa n a l g o r i t h mo fi pr o u t i n gl o o k u p sb a s e do nl s o ( l e n g t h e n s e g m e n tt a b l ea n dl e n g t h e no f f s e tt a b l e ) i sp r o p o s e d t h el s oa l g o r i t h mi saw a y s t ou s e2l e v e lt a b l e ，b u tt h el e n g t ho fe a c hl e v e li sv a r i a b l e ，t h el e n g t h e ns e g m e n tt a b l e c a na d a p tt ot h ec h a n g e si nc a p a c i t yo fs r a mo rm e m o r yi nf p g a t h el e n g t h e n o f f s e tt a b l ec a nr e d u c em e m o r y s p a c ea c c o r d i n gt ot h ep r e f i xl e n g t ho fr o u t i n gt a b l e w h e nt h es i z eo fs e g m e n tt a b l ei ss m a l la n dt h em e m o r yt h a to f f s e tt a b l eo c c u p i e di s l a r g e ，g r a p ht h e o r yc o m p r e s s i o nt e c h n i q u e sc a nb eu s e dt or e d u c et h em e m o r ys p a c e t h eb e s ts i z eo fs e g m e n tt a b l ec a nb ec o m p u t e da c c o r d i n gt oa c t u a lr o u t i n gt a b l el o m i n i m i z em e m o r ys p a c e a l s ot h es i z eo fs e g m e n tt a b l ec a nb en e g o t i a t e dw h e nt h e l s oa l g o r i t h mi si m p l e m e n t e db yh a r d w a r e t h el s oa l g o r i t h mh a sc h a r a c t e r i s t i c s s u c h a sf a s ts e a r c h t i m e ，f a s t u p d a t e t i m e , s m a l lm e m o r ys p a c e a n d e a s y i m p l e m e n t a t i o n s oi tc a n b eu s e di nc o r er o u t e r st h a th a v e1 0 g b p si n t e r f a c e s 国防科学技术人学研究生院学位论丈 i nt h i st h e s i sa na l g o r i t h mo fm u l t i d i m e n s i o np a c k e tc l a s s i f i c a t i o nb a s e do nt h e s p l s ( s h o r t e rp r e f i xl e n g t hs p l i t t i n 曲i sa l s op r o p o s e d t h es p l si sr e a l i z e db y s p l i t t i n g a l a r g e r d a t a b a s eo fc l a s s i f i e ri n t om a n ys m a l l e rd a t a b a s e so fc l a s s i f i e r a c c o r d i n gt ot h es h o r t e rp r e f i xl e n g t hb e t w e e n t h ei ps o u r c ea d d r e s sa n di pd e s t i n a t i o n a d d r e s s a f t e rs p l i t t i n gi t ，t h ei pr o u t i n gl o o k u pa l g o r i t h mc a nb eu s e dt ot h es m a l l e r d a t a b a s eo fc l a s s i f i e r m u l t i - b i tt r i e ( o rn a r yt r i e ) i st h eb a s i cd a t as t r u c t u r ef o rs p l s i nt h i st h e s i st h ep e r f o r m a n c ew h e n i m p l e m e n t i n gs p l s i n2 - a r y t r i e ，4 - a r yt r i e ，8 - a r y t r i ea n d16 - a r yt r i eh a sa l s ob e e ne x a m i n e d a n di sf o u n dt h a tt h e4 a r yt r i ei sb e s t t o i m p r o v et h ep e r f o r m a n c eo fs p l s ，a l lc h i l d r e nn o d eo fan o d ec a nb es t o r e du s i n g c o n t i n u o u s m e m o r y i n t h i sw a y , t h e p e r f o r m a n c ei sf o u n dt ob ei m p r o v e dr a p i d l y , a n d t h el o o k u ps p e e dc a nb eu pt o4 m p p sa n dt h es t o r a g ec a nb er e d u c e dt o3 m b - 6 5 m b t of u r t h e ri m p r o v et h ep e r f o r m a n c eo f s p l s ，p a t h - c o m p r e s sa n dl e v e l c o m p r e s s t e c h n i q u e sc a nb eu s e d t h ea l g o r i t h mh a sc h a r a c t e r i s t i c ss u c h a sf a s ta v e r a g es e a r c h t i m e ，f a s tu p d a t et i m e ，a l l o w i n gd y n a m i cu p d a t e ，s m a l lm e m o r ys p a c ea n ds u i t i n gf o r l a r g ec l a s s i f i e r s s oi ti sa b e t t e ra l g o r i t h mf o ri n t e r n e tr o u t e r s i nt h i st h e s i st h ed e s i g na n di m p l e m e n ta c t i o no fan e t w o r kl a y e ro u t p u tc o n t r o l c o m p o n e n t o fac o r er o u t e ri sa l s od e s c r i b e d k e y w o r d sp a c k e tc l a s s i f i c a t i o n ，i pr o u t i n gl o o k u p ，l s o ( l e n g t h e ns e g m e n tt a b l e a n do f f s e tt a b l e ) ，s p l s ( s h o r t e rp r e f i xl e n g t hs p l i t t i n g ) ，t r i e ，m u l t i b i tt r i e ，n a r y t i l e ，c o r er o u t e r 国防科学技术犬学研究生院学位论文 第一章绪论 目前，因特网路由器需要高速分组分类( p a c k e t c l a s s i f i c a t i o n ) 算法，它们需要 高速一维分组分类算法进行i p 路由查找( d r o u t i n gl 0 0 k u p ) 或建立虚链路，需要 高速多维分组分类算法对分组( p a c k e t ) 进行分类、对不同的分组进行不同的处理。 另外，其他应用领域如地理信息系统( g i s ) 也需要高速分组分类算法。研究高速 分组分类算法具有十分重要的意义。 本文中我们描述了基于l s o ( l e n g t hs e g m e n ta n do f f s e tt a b l e ) 的高速i p 路由 查找算法，p 路由查找是因特网环境下一维分组分类的主要形式；同时也描述 了基于s p l s ( s h o r t e r p e r f i xl e n g t hs p l i t t i n g ) 的高速分组分类算法。对这些算法我 们不仅描述了硬件或软件上的实现，也给出了性能评价，其性能可以满足特定的 环境。另外，本文还给出了p n l 核心路由器网络层输出控制部件的设计与实现。 1 1 研究背景 近年来，因特网已经从主要连接教育机构的低速网络迅速成为重要的商业基 础设施。现在，因特网_ i _ f 呈现两方面的新变化，一方面，因特网上的用户币在呈 现爆炸性增长，w e b 站点f 在迅速增加，对网络带宽占用多的多媒体应用正在闩 益普及，因特网上的通信量也正在呈现爆炸性增长，因特网f r 益变得 爿j 挤：另 一方面，因特网上的用户正呈现许多不同的种类，从以浏览和下载资料为主的普 通家庭用户，到从事电子商务的大型企业等等，这些用户从安全、性能、可靠性 方面对因特网的期望是不同的。例如：一家大型公司在不同的地理位置有多个分 公司，它们需要通过因特网连接每个分厂的内部网络，并且需要有严格的带宽和 延迟保证，所有的p 分组在通过因特网时要加密，为提供这种新的网络服务( 也 称虚拟私用网或v p n ) ，路由器必须能识别源于或去往各分厂的分组，将它们与 其他的分组进行不同的处理。 为适应这些新变化，因特网服务提供者( i n t e m e ts e r v i c ep r o v i d e r , i s p ) 必须做 到如下两点：一方面，它们必须升级因特网骨干网络的速度，另一方面，它们必 须筹划新的有差别的网络服务，以满足不同用户的需要。由于光纤技术和d w d m 技术的发展使得链路的速率不再成为瓶颈，i s p 在做到这两点时必须面对另一个 主要困难：路由器作为连接链路的节点的性能是主要瓶颈。这主要出于 路由器对于每个输入分组需要执行许多操作，包括十分复杂的分类操作，它们需 要对每个输入分组执行最长前缀匹配( l o n g e s tp r e f i xm a t c h i n g ) 以发现其下一跳 第1 页 国防科学技术人学研究生院学位论文 ( n e x th o p ，n h ) 地址；需要对每个输入分组执行多维分组分类以便在执行缓冲器 管理( b u f f e rm a n a g e m e n t ) 、q o s 调度、防火墙( f i r e w a l l ) 、网络地址翻译( n e t w o r k a d d r e s st r a n s l a t i o n ，n a t ) 、多目转发( m u l t i c a s tf o r w a r d i n g ) 、虚拟专用网( v i r t u a i p r i v a t en e t w o r k s ，v p n ) 、基于策略的路由( p o l i c y b a s e dr o u t i n g ) 、虚拟带宽分配 ( v i r t u a lb a n d w i d t ha l l o c a t i o n ) 、速率限匍 ( r a t el i m i t i n g ) 、负载均衡( l o a db a l a n c i n g ) 、 流量整形( t r a f f i cs h a p i n g ) 、流量记帐( t r a f f i c b i l l i n g ) 等任务时区别对待不同的分组。 1 2 1 路由器的功能 1 2 因特网路由器结构 路由器的功能可以分成两类删“”】： 1 数据路径功能：为实时任务，对每个到达路由器的分组进行操作。主要 包括转发决定、通过背板转发和输出链路调度。 2 控制功能：为非实时任务，主要包括系统配置、管理和路由表信息的更 新。不对每个到达路由器的分组进行操作，因此与数据路径功能相比其执行 是相当不频繁的。 设计高速路由器的目标是增加分组被路由的速率，因此急待改进数据路径功 能以提高性能。在此我们简单讨论主要的数据路径功能。 转发决定：根据分组的目的地址查找路由表，确定每分组的输出端口 和下- - n g ( n e x t h o p ，n h ) 地址( 一维分组分类操作) 。同时对于每分组， 在其前面添加下一跳的m a c 地址、t t l 域减l 、验证头效验和、重新计 算头效验和以及对大于m t u 的分组进行分片处理等。如果要支持分组过 滤、v p n 、q o s 调度等其它功能，路由器还需执行多维分组分类操作。 通过背板转发：背板系指输入端口和输出端口之间的物理路径。分组一 旦完成转发决定，通过背板传送至输出端口，若不能立即传送，则进行 排队，如果队列没有足够的空间，分组将被丢弃。 输出链路调度。分组到达输出端口后，在发送之前再进行排队。在大多 数传统路由器中，仅有单独一个f i f o 队列。但是在大多数高性能路由器 中，不同的流或优先级有各自的队列，可以通过仔细调度每一分组的离 开时间来满足不同的延迟和吞吐率要求。 1 2 2 路由器结构的演化 最早的路由器结构是基于计算机的结构，见图1 1 。它由一条共享总线、中 第2 页 国防科学技术人学研究生院学能论文 心c p u 、存储器和线卡组成，输入输出端1 3 功能由线卡完成，线卡提供m a c 层功能并与外部链路相 连。每个输入分组均通过 共享总线送往c p u ，由 c p u 完成转发决定，然 后再次通过共享总线送 往输出端口。其性能受两 大因素限制：1 中心c p u 的处理能力，因为搜索路 由表非常耗时，2 共享总 线的性能，因为每个分组 均需两次通过共享总线。 为解决第1 个性能瓶 颈问题，一些路由器厂商 使用多c p u ，让多c p u 并 发，每个c p u 仅处理部分 输入流量，但是每个分组 依然需要通过共享总线 两次。不久路由器结构发 生了一次重要变化，出现 了带有智能线卡的路由 器结构，见图l - 2 。每个 接口提供路由c a c h e 和处 理能力，转发决定在接口 中完成，每个分组仅需在 从输入端口传送至输出 端口时通过共享总线一 次。路由c a c h e 是中心 c p u 路由表的高速缓存， 亦称转发表。但是，由于 c p u 性能不可能跟上物 理链路容量的增长速度， 不可能为来自每条输入 链路的每秒几百万个分 组完成转发决定，所以在 每个接口增加一个具有 特别用途的a s i c ( 专用 集成电路) ，它取代c p u 进行转发决定、管理队列和仲裁对共享总线的访问，但 国防科学技术人学研究生院学位论文 是共享总线一次只允许一个分组从输入端口传送至输出端口，共享总线的性能颁 颈依然存在，为消除第2 个性能瓶颈，将共享总线替换为交叉丌关( c r o s s b a r ) ，这 样多线卡之间可以同时通信，图1 3 显示了带有交叉丌关的路由器结构。带有交 换式背板的路由器结构是新一代路由器结构的典型代表。 在带有交换式背板的路由器中，智能线卡对于输入分组主要完成接收、i p 路出查找和分组分类操作，确定其输出端口、n h 地址和对分组欲进行的操作， 对于输出分组主要完成q o s 调度和发送：交叉开关的主要功能是将分组从一个 端口线速交换到另一个端口，并可同时对多个端口并发操作：路由c p u 主要完 成系统的控制，包括路由表的更新、m 库的管理和错误处理等。 1 2 3 新一代路由器的性能评价 评价新一代路由器结构的主要性能指标有【s i t l 2 ”0 1 ： 1 高分组转发率：日益增长的因特网流量使得每秒分组数的容量成为路由 器最重要的性能指标，另外由于因特网流量爆炸性增长，路出器的容量 必须是可伸缩的。 2 支持多服务：由于a t m 技术和p 技术各有优点，目前大多数网络主干都 同时支持a t m 和口流量，并且将来也会同时支持，因此路由器必须支持 a t m 信元、p 帧和其它网络流量类型，并能有效地传送各种网络流量类 型。 3 有保证的短的确定性延迟：实时音频和视频流量需要路由器有短的且可 预测的延迟，不可预测的延迟会导致不连续，这对于实时音频和视频应 用是不能接受的。 4 服务质量：路由器必须支持服务层合同( s e r v i c el e v e la g r e e m e n t s ) ，对于不 同的应用或流提供保证的线速率和不同的服务质量。 5 多目流量：因特网的流量正在从主要为点到点流量转变为多目流量，所 以路由器必须支持大量多目流量的同时传送。 6 高可用性：高速路由器位于骨干网络中处理大量的数据，不能关电进行 升级，因此需要有热交换能力。 第4 页 里堕型：兰鉴查尘兰塑壅尘堕：兰生笙茎 1 3 分组分类面临的挑战 1 3 1 分组分类问题概述 分组分类是因特网路由器 的重要功能。 分组分类技术是路由器根 掘口分组头的一个或多个域， 从分类器( c l a s s m e r ) 数据库中匹 配每个输入分组，确定分组转发 规则，确定分组操作的技术。分 组分类过程请参见图1 4 。 分类器数据库指定了分组 转发规则或对分组欲进行的操 作，它由n 条分类器( 或称规 吸q ( r u l e 、，或称过滤器( f i t t e r ) ，或 称过滤规则，也称分类规则，不同的文献有不同的称谓) 组成。 每条分类器由属性和行为( a c t i o n ) 组成，其中： 属性由k 个分量组成，第i 个分量( 用c i 】表示) 是分组头第i 个域的f 则表达式。正则表达式可以为： f j 缀，如2 0 2 1 9 7 0 + 2 5 5 2 5 5 2 5 5 0 算子，如= 8 0 ， 1 0 2 4 等 通配符，如- 一个分组p 匹配分类器c ，如果对于任意i ，分组头的第i 个域满足萨则表达 式c i ，其中1 i k 。根据分组头的k 个域可以决定匹配分组的过滤器，从而 确定相应的行为； 行为指定对该类分组欲进行的操作。根据因特网业务的不同，对分组所采 取的操作也不同，例如，对于多目转发，行为是多个输出端口号和n h 地址，对 于防火墙分组过滤，行为是允许和拒绝等等。行为可以有多个域，同时存储不同 因特网业务对该类分组欲进行的操作，因此分类器为实现因特网新业务提供了统 一的方式。 在本文中，如未加说明，w 、n 、l 和k 的意义如下：w 为口地址宽度，对 于i p v 4 ，w 为3 2 ，对于i p v 6 ，w 为1 2 8 ，n 为分类器的数目，l 为段表长度，k 为分组分类所涉及的维数( 即所涉及的分组头域的个数) 。 一般来说，k 域分组匹配分类器也称k 维分组分类问题。k 维分组分类问题即 第5 页 一 一 国防科学技术人学研究生院学位论文 为通用分组分类问题。例如：单目路由查找为l 维分组分类问题；多目路由查找 为2 维分组分类问题：防火墙分组过滤为k 维分组分类问题。 可以将分类器想象为匹配分类器的所有分组头的集合，因此两条分类器可能 不重叠、部分重叠或者一条分类器是另一条分类器的子集，当分组匹配多条分类 器时，需用优先级区分。 表1 1 示出了一个分类器数据库的例子 库，分组p ( 2 1 2 1 6 8 3 3 2 ，2 1 2 1 6 3 1 7 1 7 1 组p 欲进行的操作。 给定表1 1 大小为n 的分类器数掘 t c p ) 匹配分类器2 ，因此a 2 为对分 分类器1 2 1 2 1 6 3 1 9 0 6 9 2 1 1 i 甄动百矿订万r _ _ 可面r 丽一 分类器2 2 1 21 6 8 3 0 2 4 2 1 2 1 6 3 0 0 1 6t c p a 2 坌耋墨型 ! ! ! ：! 箜：! ：竺! ! ! ! ：! ：! ：! ! !_竺： 垒婴 表1 1 一个分组分类的例子 k 维分类器对应于k 维空间的对象，表1 2 示出了一个二维分类器( w = 8 ) 数 表1 2 ：一个二维分类器( w = 8 ) 集合的例子 据库的例子，图1 5 示出了对应表1 2 分 类器的几何解释，它 是将表1 2 的所有二 维分类器映射在平面 上得到的。每条分类 器在平面上占据的范 围由每一维的值决 定，因为维值是以前 塞髻銎霎喜譬要譬 图1 5 表1 2 所示分类器的几何解释 维值为范围值，设某 “”“”“” 第6 页 国防科学技术人学研究生院学位论文 维前缀长度为l l ，则其范围的起点和终点分别为前缀值后分别加上( w l l ) 个0 和1 形成，例如，f 1 第一维的前缀值为0 0 0 ，前缀长度为3 ，其范围的起点和 终点分别为0 0 0 0 0 0 0 0 和0 0 0 1 1 1 1 l ，第二维的前缀值+ ，f i 缀长度为0 ，其范田的 起点和终点分别为0 0 0 0 0 0 0 0 和1 1 1 1 1 1 1 1 。将分类器映射在平面上时，每维的 范围值分别对应于x 轴和y 轴的相应范围。因此，通用分组分类问题可视为多维 空间点的定位问题。点的定位问题是计算几何中的经典问题：给定k 维空间中的 一点p 和n 个k 维空间的对象，发现点所属的对象。其时间与空阳j 复杂度为： o ( l o g “1 n ) 对o ( n ) 或o ( l o g n ) 对o ( n 。) 。但是它仅处理非重叠对象，不适合于分组 分类问题。 分组头的k 个域可以为链路层的头、网络层的头、传输层的头或应用层的头。 典型的头域为口源地址( 3 2 位) 、d 目的地址( 3 2 位) 、i p 协议域( 8 位) 、t o s 域 ( 8 位) 、传输层源端1 2 1 号( 1 6 位) 、传输层目的端口号( 1 6 位) 、传输层标志( 8 位) 、 m a c 源地址( 4 8 位) 、m a c 源地址( 4 8 位) 。以及路由器的进入端口号、输出端口 号。 衡量分组分类算法的度量标准有：预处理时间、查找时间、更新时问和存储 代价。预处理时间是算法建立初始数据结构所用的时间；查找时问是指对于给定 i p 分组，算法查找匹配该分组的分类器所需的时阳j ；更新时间是指算法插入、 删除、修改一条分类器所需的时间，更新可分为静态更新、递增式更新和动态更 新，静态更新是指插入、删除、修改时需要重新建立逐个数据结构的方法，递增 式更新是指插入时不需重新建立逐个数据结构的方法，动态更新是指插入、删除、 修改时不必重新建立逐个数据结构的方法：存储代价是指算法所占用的存储空 间。特定环境的分组分类算法其查找时间、更新时间、预处理时间要足够快，且 存储代价要合理。 完美的分组分类算法应满足下列目标：适合于任意的域、任意的匹配模式； 任意数目的分类器；允许动态更新；查找速率高速；合理的存储代价。 要满足所有这些目标非常困难，因此一般仅考虑因特网环境的典型情况。在 因特网环境下，m 路由查找是常用的一维分组分类问题；使用口源地址和【p 目 的地址的二维分组分类以及使用疋源地址、i p 目的地址、协议域、源端口号和 目的端口号的五维分组分类是常用的多维分组分类问题。本文详细研究这两类问 题的解决方法，下面介绍这两类问题的来由和挑战。 1 3 2i p 路由查找 i p 路由查找属于一维分组分类问题，它是因特网一维分组分类最典型的形 式，与多维分组分类相比，m 路由查找的显著特点是它使用最长前缀i e 酉g ( l o n g e s t p r e f i xm a t c h i n g ) 进行查找。 第7 页 国防科学技术大学研究生院学位论文 1 3 2 1 最长前缀匹配 最简单的口路由查找方法是在每台路由器的路由表中为每个节点定义一条 记录。但是在节点数、链路速率、网络通信量、查找速率只益增加的情况下，需 要维持尽可能小的路由表，因此人们提出路由器不需跟踪网络中所有节点，而将 节点分成组形成不同大小的网络，路由器仅需跟踪网络的轨迹，在特定网络之外 的路由器仅需知道如何将分组转发至这些网络，位于特定网络中的路由器知道网 络内部的拓扑结构，从而确保分组到达它的最终目的地。为提供不同大小的网络， 以满足不同组织的需要，人们将口地址空间划分为a 类、b 类、c 类、d 类和 e 类，a 类、b 类、c 类分别允许8 位、1 6 位、2 4 位命名目的网络，它们分别 包括1 6 7 7 7 2 1 4 、6 5 5 3 4 、2 5 4 台主机。 表1 3 分类的因特网寻址 同时为了简化网络地址的抽取，人们用地址的前几位来指示网络地址的长 度，因此总共有1 2 6 个a 类网络、1 6 3 8 2 个b 类网络、2 0 9 7 1 5 0 个c 类网络( 见 表1 3 1 。d 类用于多目地址，e 类保留。 但是这种地址划分既不灵活又浪费地址空间，为有效利用口地址空间，特 别是为更有效利用b 类地址，分配口地址时，通常分配一组c 类地址，而不是 b 类地址，这样导致路由表项大量增加，因此，瑾t f 于1 9 9 3 年采用无类域问路 由( c i d r ) t ”c ”】【r ”】，这意味着：为减少路由表项，可以以2 的任意次方敛集 网络地址。使用这种敛集方法，不可能从地址本身抽出几位完成转发决定，而是 需要前缀匹配。 为最大限度地减少路由表项，可以对地址进行进一步敛集。假定一个大的网 络由许多子网组成，除了其中一个子网的路由信息不同以外，其它子网的路由信 息均相同，这时不需对大的网络的每一个子网均定义一条路由表项，而是仅需定 义两条路由表项：一条用于大的网络，另一条用于例外的子网。显然，对于欲去 往例外子网的分组，在查找路由表时出现两次匹配，而例外子网的表项优先，这 一点通过给最具体的表项分配高的优先级完成，从而导致出现最长前缀匹配问 题。总之，c i d r 是在更好地利用有限的印地址空间和减少路由信息之问寻求折 中，而减少路由信息则需要更复杂的查找机制。 对照1 3 1 节分组分类问题概述，在婵路由查找中，p 路由器的路由表对应 第8 页 国防科学技术人学研究生院学位论文 分类器数据库，路由表项对应分类器，路由表项的属性对应地址自u 缀，路由表项 的行动为输出端口号和n h 地址。 前缀是一种具体的范式，它是由两个域组成的位序列。第一个域从高位丌始， 左对齐，由精确定义值( 从0 或1 中选取) 的位序列构成；第二个域，从低位丌始， 右对齐，由所有不关心的位构成。两个域均可以为空，但两个域的长度之和必须 等于p 地址长度w 。前缀长度是精确定义值的位数目即第一个域的位长度。 当m 分组匹配多个路由表项时，优先级由路由表项的前缀长度决定，长度 越长，优先级越高。 当心路由器收到分组时，它用分组的p 目的地址查找路由表，计算哪一个 表项是最长前缀匹配，然后将分组转发至该表项指定的输出端口和下一跳路由器 或主机。一个最长前缀匹配的例子见表1 4 。例如，当目的口地址为1 01 21 时， 它与前缀1 0 8 和1 0 1 2 2 3 匹配，按最长前缀匹配原则，它的下跳地址应该是 h 4 而不是h 1 。 堑塑工二些些些鲤2 1 0 8 h 1 1 0 1 1 2 8 1 7 h 2 1 0 1 1 2 4h 3 1 0 1 2 2 3h 4 目的地址 下一跳地址( n h ) 1 0 1 2 1h 4 1 0 1 1 9 2 oh 2 表1 4 ：一个最长前缀匹配的例子 1 3 2 2i p 路由查找面临的挑战 f 如上节所述，当口路 由器收到分组时，它用驴 目的地址查找路由表，计算 哪一个表项是最长匹配，然 后将分组转发至该表项指 定的输出链路，传送至下一 台路由器或目的主机。在现 代路由器中，为加速转发决 定，在每块线卡上增加转发 引擎，转发引擎维持转发 表，转发表是路由表的c a c h e ，路由表由主控模块的路由软件维持，路出查找由 国防科学技术人学研究生院学位论文 转发引擎完成，图1 6 显示了出转发引擎完成的基于i p v 4 单目目的地址的路由 查找过程，它与图i 4 的分组分类过程相似。 因特网是由许多本地网和将本地网互连的主干网组成，因此因特网上的路出 器有企业级路由器和核心路由器两种，它们的性能需求是不同的。 企业级路由器使用缺省路由，其路由表较小，般小于1 0 0 0 个f 缀，且路 由稳定，一般几秒钟更新一次。 核心路由器不使用缺省路由，其路由表很大，根据【n 删，1 9 9 8 年因特网骨干 路由器的路由表的表 项数超过4 0 0 0 0 ，而 且这个数目还在不断 增加，请见图1