（计算机系统结构专业论文）业务选择网关中ip分类算法研究与设计.pdf

摘要 摘要 随着i n t e m e t 在世界范围内的迅速发展和成熟，网络服务进一步细分并向个性 化服务的方向发展，在日趋多样的服务和对客户提供个性化服务的需求背景下， 业务选择网关应运而生。 本文的选题来自于业务选择网关研究项目，在业务选择网关的设计中，i p 分 类算法是影响整个业务选择网关系统性能的关键因素之一。本文对业务选择网关 的总体设计进行介绍，分析研究前人经典算法，针对业务选择网关对m 分类的具 体要求和业务选择网关的应用环境特点，在对其规则库进行分析和化筒以及对流 入业务选择网关的数据包特点进行分析的基础上，分别对入口分类模块和出口分 类模块设计了两种以哈希查找算法为核心的分阶段查找算法，对这两种算法分别 进行理论上的性能分析，并提出分类模块在l i n u x 系统下的实现方案，对实现时的 主要技术难点进行介绍，在l i n u x 环境下对两种分类算法进行仿真测试。 关键词：业务选择网关l p 分类哈希算法 a b s t r a e t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n ta n dr i p e n e s sw o r l d w i d eo fi n t e r a c t ，w e bs e r v i c ei s s u b d i v i d e df u r t h e ra n dd e v e l o p st o w a r dp e r s o n a l i z e ds e r v i c e o nt h ed e m a n dt h a t s e r v i c ei sb e c o m i n gm u l t i p l ei n c r e a s i n g l ya n dp e r s o n a l i z e ds e r v i c es h o u l db ep r o v i d e d t oc u s t o m e r s ，s e r v i c es e l e c t i o ng a t e w a y e m e r g e sa st h et i m e sr e q u i r e t h es u b j e c to ft h i sp a p e rc o n l e sf r o mt h es t u d yo fs e r v i c es e l e c t i o ng a t e w a y i n t h ed e s i g no f t h es e r v i c es e l e c t i o ng a t e w a y , i pp a c k e tc l a s s i f i c a t i o na l g o r i t h mi so n eo f t h ek e yf a c t o r sw h i c ha f f e c tt h ew h o l es y s t e mp e r f b 咖a n c eo fs e r v i c es e l e c t i o n g a t e w a y t h eg e n e r a ld e s i g no fi ti si n t r o d u c e da n dt h ef o r m e rc l a s s i ca l g o r i t h m sa r e a n a l y z e di nt h i sp a p e r a i m i n ga tt h ed e t a i lr e q u i r e m e n to fi pp a c k e tc l a s s i f i c a t i o n a l g o r i t h m i ns e r v i c es e l e c t i o n g a t e w a ya n d t h ec h a r a c t e r i s t i c so f a p p l i c a t i o n e n v i r o n m e n t , i t sr u l eb a s ei sa n a l y z e da n dp r e d i g e s t e d , a l s ot h ec h a r a c t e r i s t i c so fd a t a p a c k e ti ns e r v i c es e l e c t i o ng a t e w a ya r ea n a l y z e d o nt h eb a s i so fw h i c h ，t h ep a p e r d e s i g n st w ok i n d so fg r a d i n gl o o k u pa l g o r i t h m sr e s p e c t i v e l yf o re n u a n c ec l a s s i f i c a t i o n m o d u l ea n de x i tc l a s s i f i c a t i o nm o d u l e t h e o r e t i c a lp e r f o r m a n c ea n a l y s i si sm a d et ob o t h o ft h ea l g o r i t h m s t h ep a p e rp r e s e n t st h er e a l i z a t i o ns c h e m ef o rc l a s s i f i c a t i o nm o d u l e s i nl i n u xo p e r a t i o ns y s t e ma n dd i s c u s s e st h et e c h n o l o g yd i f f i c u l t i e s s i m u l a t i o ni sm a d e t ot h et w oc l a s s i f i c a t i o na l g o r i t h m su n d e rl i n u xe n v f f o n m e n t k e y w o r d s ：s e r v i c es e l e c t i o ng a t e w a y i pp a c k e tc l a s s i f i c a t i o n h a s ha l g o r i t h m 声明 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均己在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文( 保密的论文 在解密后遵守此规定) 。 本人签名：王盘遵 聊签名卜j 蝴 日期： 日期：丛生! ! ! 1 2 第一章绪论 第一章绪论 1 1 引言 随着i n t e r a c t 在世晃范围内的迅速发展和成熟，人们对电信服务商提供服务的 要求日趋多样性和个性化，这些服务包括：在线游戏、口电话、视频会议、视频点 播、w e b 浏览、电子商务和远程教育等等。这也使得传统i n t e r n e t 服务没有考虑用 户差异的服务模式的弊端日益暴露出来。正是在这些日趋多样的服务和对用户提 供个性化服务的需求背景下，业务选择网关( s e r v i c es e l e c t i o ng a t e w a y ，s s g ) 应 运而生。 业务选择网关作为网络内容服务提供商的控制网关，通过为客户提供个人服 务的门户w e b 页面的方式为客户提供个性化服务的菜单，从而拉近了网络内容提供 商和客户之间的距离。同时，业务选择网关可以通过个人门户w e b 页面对客户进行 认证，并且可以为客户对收费资源的访问提供按连接时长或者按流量等不同的计 费策略。对客户来讲，这样的计费方式更加灵活也更加合理，对内容提供商来讲， 费用的计算也更加方便，而且还可以通过提供增值服务来获取更多的经济收益。 业务选择网关工作在基于t c p i p 协议族的i n t e r n e t 网络环境中，流经网关的数 据包有很多种。从传输层协议来看可以分为t c p 和u d p 流等；从应用层协议来看可 以分为h 订p 流和f t p 流等；从数据包对应资源的类别来看，又可以分为访问收费 资源的数据包和访问免费资源的数据包等。业务选择网关需要对这些不同种类的 数据包进行不同的处理，而处理的基础是对这些数据包按照一定的规则进行分类， m 分类算法( 因为需要分类的数据包都是m 包而得名，也称报文分类算法，详细定 义见第三章3 1 节) 的作用就在于此。在业务选择网关的设计中，口分类算法是影 响整个业务选择网关系统性能的关键因素之一，稳定高效的分类算法是业务选择 网关正常工作的基础。而现有的经典i p 分类算法由于应用环境等原因并不适合在业 务选择网关中采用。 本文的选题正来自于业务选择网关的研究项目，在研究经典算法的基础上， 针对业务选择网关对数据包分类的具体需求和业务选择网关的应用环境特点，设 计了适合在业务选择网关中应用的口分类算法，并对设计的口分类算法做了性能分 析和仿真测试。 2 业务选择网芙中i p 分类算法研究与设计 1 2 国内外研究现状 采用业务选择网关目的是为客户提供个性化服务。在提供个性化网络服务和 发展增值业务j 方面，西方国家起步比较旱，已经出现一些提供个性化网络服务的 产品。这些产品中具有代表性的是c i s c o 公司的业务选择网关( s s g ) 。s s g 是c i s c o l o s 软件的一个模块化特性集，可以为针对不同i p 目的地址的客户交互策略提供 r a d i u s 身份认证和记账功能，包括同时登录多项服务的能力等。c i s c o 公司所采 用的业务选择网关技术就是通过提供个性化的服务菜单，为客户提供了丰富多彩 的服务，从而拉近了客户与电信运营商之间的距离f 2 1 。 在我国由于这方面的研究起步比较晚，所以现在还没有成熟的产品。一些较 大的i s p ( 如上海网通等) 都在使用c i s c o 和北电等国外较大设备提供商的产品， 此类网络产品主要工作于网络汇聚层。现在还没有为内容提供商设计的基于内容 定制的个性化网络服务产品。 对于i p 分类算法的研究，国外学者的研究起步稍微早一些，从上个世纪9 0 年代中后期开始，陆续有研究i p 路由查找的学者开始转而对分类问题进行研究。 这种现象产生的原因是分类问题与路由查找问题之间存在一股和特殊的关系，i p 分类问题需要匹配伊包头中的一个或多个字段( 如源目的i p 地址、传输层协议类 型、服务类型等) 来决定这个i p 报文属于哪个数据流，而i p 路由查找只需要根据 i p 包头中目的i p 地址去奁路由表即可。从这个角度来看，i p 路由查找问题町以看 作特殊的i p 分类问题。在i p 分类算法的研究领域，国外主要有两个流派p 】：圣路 易斯华盛顿大学( w a s h i n g t o nu n i v e r s i t yi ns t l o u i s ) 学派和斯坦福大学学派。前者以 g e o r g ev a r g h e s e 教授及其弟子s r i n i v a s a n 为首，其主要的合作伙伴是b e l l 实验室 和微软研究院，倾向于使用数据结构和h a s h 函数：后者以n i c km c k e o w n 教授及 其弟子p a n k a jg u p t a 为首，其主要合作伙伴是c i s c o 公司，重点研究基于t c a m ( t e r n a r yc o n t e n t a c c e s sm e m o r y ，一种专用存储器件) 的多维数据包分类算法。 近年来经典的报文分类算法基本都出自这两大学派。 国内i p 分类算法的研究比国外起步晚一些，但在近年来的研究工作中也取得 了一定的成果。这些成果中的一部分为： 徐恪等从路由器规则库中源端口、目的端口以及协议类型三个域内容相对单 的特点入手，提出了基于跳转表的分阶段查找算法1 4 】，将复杂的多维1 p 分类问 题转化为二维i p 分类问题，极大地提高了多维分类的效率。 喻中超等同样根据分类规则中端口和协议域的取值( 或取值范围) 组合数目 非常有限的特点，提出了无冲突哈希t r i e 树查找算法，该算法不仅克服了g r i do f 第一章绪论 t r i e s 经典算法在多维i p 分类方面的局限性，而且在时间和空间性能上比g r i do f t r i e s 算法都有所提升1 5 j 。 刘惠义等在基于无冲突哈希t i i e 树的基础上对哈希函数进行了研究，给出了 一组哈希函数，进一步增强了算法的灵活性嘲。 谭兴晔等对m 路由表中i p 地址前缀进行了研究，发现i p 地址前缀总是覆盖 地址的前8 比特，并在此基础上提出了r c f s t 算法，该算法支持分类规则数据库 大、可扩展性好、适于硬件流水线方式实现r ”。 综上所述，国内目前对i p 分类算法的研究已经取得了长足的进步，但是应该 看到国内的研究成果大部分都是针对国外经典理论的改进或实现，没有根本性的 突破，赶超国外领先水平还有很长的路要走。 1 3 论文研究的意义和所做的工作 在业务选择网关的设计中，m 分类模块对m 包的分类结果是后续模块工作的 基础，它是影响整个业务选择网关系统运行效率的关键因素之一。1 2 节简单介绍 了国内外对于m 分类算法的研究情况，目前已有的算法种类较多，但应用到业务 选择网关中存在如下问题： 1 绝大多数口分类算法都有其适用的特定环境，通用的优秀算法少之又少。 大部分i p 分类算法都只能用于分类维数( 具体概念见第三章3 1 节) 比较低的分 类问题，例如经典的g r i do f t r i e s 算法和交叉乘积算法只能用来解决2 维分类问题， 而本文讨论的业务选择网关中需要解决的是4 维分类问题，因此不适合。递归流 分类算法可以解决多维分类问题，但是需要硬件具有并行处理能力，本文中讨论 的网关设计方案是基于p c 机中运行的l i n u x 操作系统，同样不适合； 2 算法设计时要考虑线速处理、折中、满足实时需要、简单性等原则( 详见 第三章3 4 节) 。尤其是简单性原则，这是进行理论研究的人常常容易忽视的原则， 却也是非常莺要的原则，很多理论上性能优秀的算法未能得到实际应用，都是因 为实现机制太过复杂的缘故。 针对以上问题，本文从业务选择网关的实际需求出发，对业务选择网关中的 i p 分类算法进行了分析和设计。下面将本文所做主要工作概括如下： 1 对业务选择网关的总体需求和功能进行分析，对业务选择网关的工作流程 进行了详细设计，包括其系统结构和详细的模块设计( 这部分工作是与谭君、王 家胜、乔航等三位同学合作进行的) ； 2 对前人经典算法进行分析，并对各种算法的性能和适用环境进行了比较； 3 针对业务选择网关对i p 分类的具体要求和业务选择网关的应用环境特点， 本文在对其规则库进行分析和化简以及对流入业务选择网关的数据包特点进行分 4业务选择网关中i p 分类算法研究与设计 析的基础上，分别对入口分类模块和出口分类模块( 业务选择网关的i p 分类模块 分为这两个模块，它们分类的结果分别为会话管理和流量控制模块提供依据) 设 计了两种以哈希查找算法为核心的分阶段查找算法，并且对此两种算法分别进行 了理论上的性能分析，这也是本文的主要创新之处： 4 本文提出了业务选择网关中的m 分类模块在l i n u x 系统下的实现方案，对 实现时的主要技术要点进行介绍，并在l i n u x 环境下对两种分类算法进行仿真验 证。 1 4 论文结构 本文共分为五章： 第一章绪论。提出论文研究的对象以及国内外相关研究发展现状，介绍本文 所做工作及其意义。 第二章业务选择网关。对业务选择网关出现的时代背景、业务选择网关的功 能特性、应用环境以及工作原理等方面傲了介绍。并且对本文要进行研究的l p 分 类模块在业务选择网关中的作用和工作原理进行了简要叙述。 第三章i p 分类算法分析与设计。对于i p 分类问题进行描述，对已有的一些 经典算法进行介绍和分析，在对实际规则库进行化简以及对流入业务选择网关的 数据包特点进行分析的基础上，设计了两种以哈希查找算法为核心的分阶段查找 算法，并在理论上分析每种分类算法性能。 第四章分类算法实现方案。本蕈首先对业务选择网关进行总体设计，然后提 出i p 分类模块在l i n u x 系统下的实现方案，包括分类模块与其他模块间的关系以 及分类模块的数据处理流程以及编程实现时所用到的关键技术要点。最后对分类 算法进行了仿真测试。 第五章结论与展望。对全文所做工作进行总结，并提出需要改进之处和进一 步研究方向。 第二章业务选择网关 2 1 1 业务选择网关的由来 第二章业务选择网关 2 1 业务选择网关简介 提到业务选择网关( s e r v i c es e l e c t i o ng a t e w a y ，s s g ) ，就不能不先介绍一下 n o n 。n g n 的概念已经提出多年，不过在业界一直存在诸多不同的解释。在2 0 0 4 年年初国际电联n g n 会议上，经过激烈的辩论，n g n 的定义终于有了定论：n g n 是基于分组的网络，能够提供电信业务；利用多种宽带能力和q o s 保证的传送技术； 其业务相关功能与其传送技术相独立。n o n 使客户可以自由接入到不同的业务提 供商；支持通用移动性。n g n 是“下一代网络( n e x t g e n e r a t i o n n e t w o r k ) ”或“新 一代网络( n e wg e n e r a t i o nn e t w o r k ) ”的缩写l g j 。n g n 是以软交换为核心，能够 提供话音、视频、数据等多媒体综合业务，采用开放、标准体系结构，能够提供 丰富业务的下一代网络。 由于n g n 技术在世界范围内的迅速发展，电信市场的竞争愈演愈烈，也给中 国电信运营商在市场竞争中赶上甚至超越国际电信巨头提供了一个历史性的机 遇，特别是目前各个电信运营商都在面临着服务转型的形势，如何适应n g n 运行 的模式，已成为各个电信运营商所面临的一个重要课题。n g n 宽带网络技术的成 熟，使数据网将能统一承载语音、数据、视频等多种业务。因为n g n 是一个开放 的网络，在其架构内，各构件协议已趋于标准化，原来各大通信厂商对技术、业 务的垄断格局已不复存在，小型的设备供应商也存在着较大的发展空间。为此， 专注于增值业务的开展就成为电信运营商们谋求生存及发展的重要途径，以向客 户提供更高质量、更多元化和个性化服务的方式，将客户吸引住。人们日益要求 电信服务商们提供的服务包括：在线游戏、口电话、视频会议、视频点播、w 曲浏 览、电子商务和远程教育等等。这些宽带服务将更加体现“以人为本”的理念和 趋向于个性化，而且更加突出了人性化。例如c i s c o 公司所采用的业务选择网关技 术就是通过提供个性化的服务菜单，为客户提供了丰富多彩的服务，从而拉近了 客户与电信运营商之间的距离。而在服务过程中，电信运营商们可以根据客户的 连接时间和所使用的服务项目，制定灵活的价格计算策略，向客户收取相应的费 用【2 1 。 6 业务选择网关中】p 分类算法研究与设计 2 1 2 业务选择网关的功能特性 c i s c o 公司的业务选择网关工作在网络的汇聚层，作为一个动态的服务创造和 管理平台对传入的网络进行汇聚，并将来自a aa 、l d a p 或者o r a c l e 数据库中客 户简表中豹策略动态分配给网络上的客户( 这些客户都是指i p 域中的客户) ，客户 可以基于简表对不同服务进行访问，对于每种服务的访问都可以基于流量或者连 接时长进行计费。并且具备客户访问模式的切换、域名系统重定向、d n s 容错等 特性。 由于研究环境和时间等因素的限制，本文讨论的业务选择网关是一个基于 u r l 柱度的内容选择网关。与c i s c o 公司的产品相比，其功能更简单( 不具备d n s 容错等特性) ，应用环境也有所不同( 用于内容提供商，而不是电信运营商处) 。 此外，由于它是基于u r l 粒度进行控制，从控制粒度上看，它要比c i s c o 公司的 产品控制得更细一些。通过给客户提供个人服务门户的w e b 页面对客户进行认证， 业务选择网关既为客户提供了更灵活更合理的收费方式也为内容提供商的管理和 计费带来了方便，并便内容提供商通过增值服务，获得更高的经济收益。 业务选择网关( 如无特殊说明，本文中提到的“业务选择网关”均指本文研 究的业务选择网关，而不是c i s c o 公司的软件产品) 为客户提供个性化的服务定制， 不仅方便客户对网路服务的使用而且也为服务提供商创造新的利润增长机会，其 主要功能特性如下： 1 个性化的业务定制 业务选择网关为客户提供方便快捷的业务定制和取消界面。客户可以通过认 证登录进入个性化服务界面，方便地进行各种业务的访问。 2 业务数据存储 业务选择网关可以存储业务数据，包括免费业务、收费业务和阻止访问业务 的相关数据等。对于免费业务，业务选择网关不做任何控制，允许所有客户( 包 括登录客户和匿名客户) 随时访问；而对于收费业务和阻止访问业务则需要进行 控制。 3 基于u 也的内容控制 业务选择网关可以进行细粒度的内容控制，以u r l 作为内容控制的基本单元。 业务选择网关对客户发来的请求数据包进行分析，获取数据包请求资源的u r l ， 然后与客户已经定制收费资源的u r l 进行匹配，判断是否准许客户进行该业务的 访问。 4 虚拟会话管理 业务选择网关对服务内容进行控制的目的是为了提高效率，以及避免每次客 户访问相同服务都要进行控制。业务选择网关必须以虚拟会话的方式来管理客户 第二二章业务选择阿关7 访问。 5 优先级控制 业务选择网关应当能够对客户的请求进行优先级控制，使优先级高的请求首 先通过，从而保证高优先级请求服务的服务质量。业务选择网关至少应当实现以 下两种优先级控制方式： ( 1 ) 基于客户身份。业务选择网关处理客户请求时，可以根据发起请求的客 户身份区分不同优先级，对优先级级别较高的客户请求优先处理； ( 2 ) 基于目标口地址和端口号的组合。业务选择网关处理客户请求时，可以 根据请求的目标i p 地址和端口号( 请求服务的不同) 区分不同的优先级，对级别 较高的服务优先处理。 6 路由选择 业务选择网关可以根据规则区分不同的客户请求，并将客户请求转发到正确 的地址。转发规则可以根据多种参数确定，包括业务种类、服务提供商类型以及 其他参数。 7 地址转换 提供业务内容的服务器可能使用私网地址，客户的业务访问请求全部进入业 务选择网关，网关对访问请求进行判断转发到相应的内容服务器上，因此业务选 择网关应当具备网络地址转换的功能。 8 手工配置 、业务选择网关作为一个网络设备，必须提供相应的手工配置的功能。其具体 表现为：业务选择网关可根据业务的需要，利用软件提供的接口对业务选择网关 进行各种相关的配置。 9 话单提供 业务选择网关可以向业务支撑平台的计费系统提供原始话单，话单应当包含 足够的信息，以满足基于内容计费的要求。话单信息中必须包含对长和流量的信 息，同时话单中需要有目标地址、端口号、协议信息以及其他相关信息，从而才 能够满足“区分目标地址和业务”计费的要求。 2 1 3 业务选择网关的典型应用 业务选择网关的一个典型应用场景如图2 1 所示。 业务选择网关是一个第5 层或者说第7 层内容控制的一个解决方案。如图左 部所示，客户可以通过多种方式和渠道连接i n t e r n e t ，例如p c 机或者p d a ，甚至 手机等智能终端都可以。业务选择网关与w e b 服务器以及r a d i u s 服务器相连， w e b 服务器负责为客户提供认证、登录以及业务选择的门户页面，r a d i u s 服务 业务选择网关中i p 分类算法研究与设计 器负责客户合法性的验证，以及客户可以访问的资源列表的保管。内容提供商的 业务分为收费和免费两种，分别由不同的服务器所承载。业务选择网关只对收费 业务进行控制，而对于免费业务的数据包，直接允许通过网关。当然，对于免费 业务的数据包处理的优先级要低于收费业务的数据包。业务选择网关有两种工作 模式；普通工作模式和透明的n a t ( n e t w o r ka d d r e s st r a n s l a t o r ，网络地址转换) 工作模式。如果内容服务器采用的i p 地址是私有地址，则网关工作在透明的n a t 工作模式。 收莆睢备 免费服务 图2 1 业务选择网关典型应用场景 2 2 业务选择网关工作原理 c i s e o 公司的业务选择网关可以提供两种实现或业务模型：第二层业务选择或 者第三层业务选择模型【9 l 。第三层业务选择与第二层业务选择之间的主要区别是： 在第二层业务选择模型中，客户在发起一条p p p 会话之前就已经确定了他的最终 目标，并且在p p p 会话处于活跃的整个过程中，最终目标都始终保持相同。而在 第三层业务选择模型中，客户在进入了n a p 或n s p 的“带有围墙的花园( w a l l e d g a r d e n ) ”( 也就是本地网络) 后，客户可以有多种业务( 最终目标) 供其选择。然 后，用户可以选择他需要连接的具体业务，而不必断开p p p 会话( 而在第二层业 务选择模型中就需要断开原来的p p p 会话) 。可见，第三层业务选择模型与第二层 业务选择模型相比，具有更好的灵活性。 本文讨论的业务选择网是一个基于u r l 粒度的内容选择网关。从控制粒度上 看，它比c i s c o 公司的s s g 控制得更细一些。不过从工作原理上看，它与c i s c o 公司的s s g 是非常相似的，都是采用提供个人服务门户w e b 页面的方式为用户提 供业务选择的接口，因此也称为基于w e b 页面的业务选择( w e b b a s e ds e r v i c e 第二章业务选择网关 9 s e l e c t i o n ) 唧。与第二层业务选择模型不同，基于页面的业务选择可以与接入方式 无关，只要可以通过唯一的m 地址来确定主机或用户就可以。 基于页面的业务选择使用一个h t l p 服务器或w e b 服务器，被称为业务选择 控制板( s e r v i c es e l e c t i o nd a s h b o a r d ，s s d ) ，是一个w e b 服务器，可以在各种操 作系统上运行，并与业务选择网关进行通信。 采用基于页面业务选择方式的主要优点： ( 1 ) 关于业务的信息( 如相应的收费信息) 可以随时被通告； ( 2 ) w 曲浏览器随处可见，使用非常方便； ( 3 ) 用户可以同时选择多项业务； ( 4 ) 用户可以获得个性化的服务。 业务选择网关控制部分 图2 2 业务选择网关各组成部分交互关系图 如图2 2 所示，业务选择网关、业务选择w e b 服务器、外部r a d i u s 服务器 ( 图中aa 服务器) 之间的交互过程如下： 首先，客户主机使用浏览器软件访问预先定义好的业务选择w e b 服务器的 u r l 或者m 地址。这发生在用户被分配了某个口地址以后，此时用户只可以访 问默认网络( 包括w e b 服务器、a a a 服务器和免费资源) 。在客户访问到w e b 服 务器的第一个页面时，他被要求输入用户名和密码进行登录。输入这些信息以后， w 曲服务器会把通过h r r p 收到的用户名和密码翻译成r a d i u s 认证数据包，并 将这个包发送给业务选择网关控制部分。当控制部分收到这个请求以后，会将它 转发给a a a 服务器。a a a 服务器对用户进行认证，并向业务选择网关控制部分 发回一个应答包。包中可能含有两种信息：认证成功或者认证失败。如果用户被 成功认证，舢执服务器向控制部分发送一个认证成功的授权数据包，控制部分根 l o业务选择网关中i p 分类算法研究与设计 据授权数据包生成用户会话和资源权限包，并同时把授权数据包转发给业务选择 w e b 服务器，w e b 服务器生成用户的个性化选择页面；如果认证失败，a a a 服务 器则向控制部分发送认证失败数据包，控制部分转发给业务选择w e b 服务器，反 馈给用户登录失败信息。 2 3 业务选择网关中的i p 分类模块 业务选择网关的基本组成结构如图2 3 所示。 图2 3 业务选择网关基本组成结构 如图所示，业务选择网关由报文分类模块( 即i p 分类模块，关于这两个名词 在第三章3 1 节中有解释) 、访问控制模块、会话管理模块、计费模块、n a t 模块、 路由模块以及系统配置模块等7 个模块组成。 i p 分类模块位于业务选择网关数据处理流程的第一个环节，它的作用是根据 业务选择网关接收到的数据包包头中的信息，对数据包进行分类，把数据包划归 不同的队列，交给后续模块进行处理。对于i p 分类模块的具体工作原理和作用， 第三章3 1 节有具体的解释，此处不作详细说明。 2 4 本章小结 本章对业务选择网关出现的时代背景，以及业务选择网关的功能特性、应用 环境、工作原理等方面进行了介绍。并且对于本论文要研究的i p 分类模块在业务 选择网关中的作用和工作原理进行了简要阐述。 第三章i p 分类算法分析与设计 第三章i p 分类算法分析与设计 对口分类算法的研究起始于2 0 世纪9 0 年代中后期，当时主要是一些研究口 路由查找的学者转而研究这一领域。不过在短短的近1 0 年内，分类算法研究取得 了很大突破，目前基于不同思想和数据结构的算法及改进变形已经有十多种【3 】。 3 1i p 分类问题描述 任何科学和技术问题的研究都反映一个时代的特定需求，i p 分类问题也不例 外，对口分类问题的研究是在i n t e m e t 高速发展的背景下展开的。随着i n t e r a c t 的 高速发展，路由器正在成为网络数据传输的瓶颈。在路由器的转发过程中，主要 有三个瓶颈：查找、交换和输出调度【l o l 。当前路由器上的瓶颈主要表现在路由器 的查找效率上。近年来兴起的一些新型的网络应用要求路由器能够提供相应的功 能支持，如：防火墙l l l l ，基于策略的路由( p o l i c yb a s e dr o u t i n g l l 2 1 ) 、区分服务 ( d i f f e r e n t i a t e d q u a l i t i e s o f s e r v i c e l l 3 1 ) 、q o s 1 4 1 、负载均衡( 1 0 a d b a l a n c e ) 、基于流量 的计费 1 s l 等等。这些功能需要将经过路由器的数据包归类为不同的数据流，根据 不同的数据流来进行不同的操作，如决定诸如是否转发该数据包、如何转发数据 包、数据包应该得到什么样的服务或相应流量数据包该收取多少费用等。这些功 能都是以包分类( p a c k e tc l a s s i f i c a t i o n ) 技术( 或者说报文分类技术) 为基础的。 由于路由器处理的数据包绝大部分都是i p 包，因此相应的技术也称为i p 分类( i p c l a s s i f i c a t i o n ) 技术i 。在本文中，如果没有特殊声明，口分类技术、报文分类技 术这两个名词是通用的( 也简称为分类技术) 。 3 1 1 分类的定义 i p 分类的目的是根据预先定义好的标准把数据包分为若干个组，以便于网络 设备( 如防火墙、网关等) 对于不同的数据包可以分别进行处理。这里“预先定 义好的标准”就是指分类规则，它们是对报文进行分类的依据。这些分类规则的 集合叫规则库( 也称为策略库、或者流分类器) ，报文分类的工作就是围绕它来 展开的。 假定一个规则库c 含有n 个过滤规则玛，( 1 p d ( r j ) ，v j m ，i j n ，且满足p i 匹配刚，1 - 1 0 2 4 、p o r tc 【2 0 ，2 1 1 等等。当然，精确表示法也 第二章i p 分类算法分析与设计 会采用，如w w w 服务的专用端口8 0 、t e l n e t 服务的专用端口2 3 等。传输层协议 的端口实际上表示该报文的高层应用，如2 5 表示简单邮件传输协议( s m t p ) 访 问、5 3 表示d n s 访问、1 1 0 表示p o p 3 访问等等。对于协议字段，通常采用精确 描述，如协议类型号6 对应t c p 协议、1 7 对应u d p 协议、1 对应i c m p 协议、2 对应i g m p 协议等等。正是这些不同的描述方法使得匹配方式也各不相同。 下面给出几个匹配表3 1 对应规则库中规则的报文例子。 表3 2 匹配上述规则库规则的报文示例 、 报文 源i p 地址目的l p 地址目的端口协议字段匹配规则 p 12 0 2 1 1 7 1 2 1 2 3 06 1 1 3 6 韵9t2 1t c pr l p 22 舵1 1 2 5 1 2 5 1 5 1 6 7 3 0 6 7 舯 t c p船 p 32 0 2 1 1 5 6 1 2 42 0 2 1 1 7 ，1 1 2 2 0 41 0 6 1 8t c p r 5 p 42 0 2 11 7 1 2 1 7 91 5 1 9 5 ，4 5 9 l2 0 t c p r 2 如表3 1 和表3 2 可以看出，报文p 2 同时匹配了规则r 3 和r 6 ，即规则存在 冲突的现象，这种冲突可以表现为重叠关系或包含关系，如本例中的关系就是 r 3 c r 6 ( 包含关系) 。同时，这种现象也表示规则之间存在着优先级。对于包含关 系的这两个规则r 3 和r 6 ，若r 3 c r 6 ，则r 3 的优先级高于r 6 。而对于重叠规则 之间的优先级，则需要在规则库中来体现，不同的规则库的规定不同，这种体现 既可以是显式的也可以是隐式的1 3 1 。一般隐式的表示多表现为规则在规则库中的顺 序不同，优先级高的规则在规则库中的位置更靠前。显示的表示需要在每个规则 中添加一个优先级标识，若报文同时匹配了多个规则，则比较这几个规则的优先 级标识，从而找到优先级最高的规则作为匹配结果。具体采用哪种表示方法，取 决于规则库的规模、实际的应用以及更新的频繁度等因素。 规则库r 的规模随着具体应用的不同，差别很大。有一种说法 3 1 是：当规则 库的规模不大于1 6 k b 时则为小规则库，而当规则库的规模介于1 6 k b 和1 2 8 k b 之间为中等规模规则库，大于1 2 8 k b 小于i m b 的规则库为大规则库，而超过1 m b 的规则库为超大规模规则库。要注意规则库的规模是指规则库的物理存储区域大 小，并不是规则数，即规则库的规模= 规则数规则长度。 3 1 2 分类的基本原理 分类器一股处在通信子网的结点或路由器中，路由器分为识别流与非识别流 的路由器。识别流的路由器跟踪流的传输并对在同一个流的报文进行相似的处理。 非识别流的路由器( 也称报文- 报文路由器) ，单独处理每个进入路由器的报文。两 1 4 业务选择网戈中i p 分类算法研究与设计 者的效率差别很大，非识别流的路由器远远低于识别流的路由器，在实际中极少 采用，此处不作讨论。 每个报文在流识别路由器中的主要处理步骤有：路由表的查找、报文分类、 报文特殊处理( 例如丢弃未授权报文、重定向报文到代理服务器或特殊队列以便 后续模块调度等) 、交换调度( 将报文通过交换机构传到输出端1 2 1 ) l j 7 l 。其过程如 图3 1 所示，报文分类的基本原理图如图3 2 所示。 二二二工 进入的报文 阔3 i 流识别路由器的基本组成结构 分类模块 = 、 7 ： 规则库 艘鄹l各域细节 行为 r i a l r 2 a 2 r n a n 图3 2 报文分类的基本原理图 如图3 2 所示，报文分类模块根据进入的报文的头部( 里面含有源i p 地址、 目的m 地址、目的端口号等信息) 的各个参数域与规则库中的各条规则进行匹配， 一旦找到匹配的规则，则将该报文按照规则中定义的“行为”去做相应的处理。 在整个匹配的过程中，如何对各条规则进行组织、如何进行规则的存储、匹配的 先后顺序、怎样使得查找速度更快、占用存储空间更少等等问题，则属于分类算 法研究的范畴。可以说，报文分类问题的核心就是高效查找方法。 3 1 3 分类的应用 从前面3 1 1 小节可以看出，报文分类就是根据预先定义好的规则( 也称为策 第二章l p 分类算法分析与设计 略) ，参照报文头部的各个参数域对报文进行分类，再对同一类报文进行相应的 处理。也有说法称之为流分类、第4 层交换【1 8 1 等等。报文分类不像i p 路由查找只 需参照网络层的目的i p 地址，它可能参照链路层、网络层、传输层、应用层的多 个参数，具体可能参照的参数如下：链路层的源m a c 地址、目的m a c 地址；网 络层的源i p 地址、目的i p 地址、协议字段、t l l 和1 - o s ；传输层的源端口号、 目的端口号、s y n 、a c k 和f i n 标志；此外还有特定应用层的协议参数等。报文 分类的应用范围很广，具体可以应用于以下这些领域：服务质量( 区分服务、带 宽预留、分级调度) 、网络安全( 接入控制、v p n ，i p s e c ，s s u s e t ) 、路由( 基 于u r l 的路由、多播) 、基于使用的计费( u s a g e - b a s e d a c c o u n t i n g ) 等。 下面举例1 1 9 1 说明报文分类在现代网络中的应用。 图3 3 一个多i s p 网络简单示意图 如图3 1 3 所示，i s p l 分别通过路由器a 和b 连接两个企业网络e l 和e 2 ，同时 i s p 2 和i s p 3 作为另外两个i s p 通过网络接入点( n a p ) 与i s p l 进行连接。i s p l 为 其用户提供了如下服务： 表3 3i s p l 为其用户提供的服务 服务服务示例 包过滤 禁止所有从i s p 3 到e 2 的数据包 策略路由使所有从e 1 到e 2 的v o 口报文通过一个单独的a t m 网络 区分服务和记账对所有目的地为e 1 的视频流记账并给予最高优先级 流量控制使所有来自i s p 2 的邮件流量不超过1 0 m b p s 如表3 3 所示，为实现i s p l 对其用户提供上述各种服务，对应路由器需要对 经过自己的数据包进行分类，从而实现对不同数据包提供不同服务。现在以i s p l 和n a p 连接路由器c 为例进行分析。路由器c 需要将经过自己的数据包分成如下 几类： 1 6 业务选择网关中i p 分类算法研究勺设计 表3 4 路由器c 需要分类的数据流 类别判定流相应的报文域 从i s p 3 到e 2 的数据包 源i p 地址和目的i p 地址 目的为e - 的视频流目的i p 地址和应用层的参数 来自i s p 2 的邮件源i p 地址和目的端口 如表3 4 所示，若要实现“禁止所有从i s p 3 到e 2 的数据包”的服务，对于路 由器c 来讲，首先要能区分出哪些数据包是从i s p 3 到e 2 的数据包，而具体的区分 方法只能是通过数据包包头中源i p 地址和目的i p 地址与规则库规则中源i p 地址 与目的m 地址的对应域进行匹配，从而判断这个数据包是否是从i s p 3 到e 2 的数 据包。其他几个类别也是如此，此处不作详细说明。 3 2 已有分类算法分析 下面简单介绍一下目前国内外已有的一些分类算法。按照规则的存储方式， 报文分类算法可分为以下四判1 9 】： ( 1 ) 采用基本数据结构的算法； ( 2 ) 几何算法； ( 3 ) 启发式算法； ( 4 ) 基于硬件实现的算法。 下面具体对这几类算法进行介绍。先介绍经常用到的几个符号：n 表示规则 个数，d 表示分类的维数( 即查找时匹配的字段数，也叫域数) ，w 为分类域宽， l 为树的层数。 3 2 1 采用