（通信与信息系统专业论文）字符串匹配算法在p2p流量检测中的研究与实现.pdf

独创性( 或创新性) 声明 本人声明所呈交的论文是本人在 t ) i l i 指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处， 本人签名： 镌眈韵 本人承担一切相关责任。 日期：幽：三：星 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以 公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇 编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论文注 释：本学位论文不属于保密范围，适用本授权书。 本人签名：塑堕刍日期：2 竺翌：至：2 导师签名：董丘! 兰 e l i o t ： 1 2 ：三：! ； 北京邮电大学硕士研究生擘位论文 字符串匹配算法在p 2 p 流量检测中的研究与实现 摘要 对等网络( p e e r - t o p e e rn e t w o r k , p 2 p ) 的出现是对传统c s 网络架构 的一次进化，其特点是每个网络节点地位相等，既充当客户机从其他节 点处索取服务，同时也充当服务器为其他节点提供服务。对等网络不仅 使深度挖掘网络资源成为了可能，而且还为计算机网络的发展提供了广 阔的思路，是当前计算机网络领域内最重要的研究课题之一。 目前，p 2 p 的应用非常广泛，统计表明，p 2 p 应用已占i s p 业务总量 的4 0 7 0 ，成为网络带宽的最大杀手。随着i n t e m c t 的日益普及和网 络结构的日益复杂，网络的安全性、可管理性及其传统应用的可用性受 到了挑战，所以对p 2 p 流量和网络行为进行深入地了解、分析，进一步 管理p 2 p 流量，并及时调整经营策略以适应p 2 p 流量的特点，已成为每 个网络服务提供者的紧迫课题，而其中首要的任务就是对p 2 p 流量进行 有效的识别与管理。本文基于项目“p 2 p 应用流量管理的研究”，深入研 究了对等网络的行为特性、影响字符串匹配算法性能的因素以及p 2 p 流 量检测的相关内容，并对一些典型p 2 p 应用的流量检测采用具体的字符 串匹配算法进行了性能仿真研究和比较，取得了一些研究结果。本文是 项目部分研究结果的总结，全文的主要内容分为以下五个部分： 第一章主要介绍了课题的技术背景和研究的重要意义，并指出本人 所做的研究工作；第二章阐述了p 2 p 网络的研究现状及发展趋势；第三 章论述了基于p 2 p 网络进行的行为特征分析，给出了对一些典型p 2 p 应 用进行行为特征分析的结果；第四章介绍了字符串匹配算法的相关理论， 第l 页 并对一些典型的算法性能进行了分析和实验研究，针对算法和典型的p 2 p 应用，做了仿真实现，得出了性能比较的结果。第五章集中介绍了基于 硬件的p 2 p 流量检测的研究；最后对所做研究工作进行了总结，同时对 下一步研究工作做了展望。 关键词：对等网络字符串匹配算法流量检测模式漏判 第2 页 北京邮电大学硕士研究生学位论文 r e s e a r c ha n dn 仰l e m 匣n r i o no fs 耶r i n g 脚c h ga l g o r i 耶h mi np e e r t o - p e e r t ra f f i cd e t e c t i o n a b s t r a c t t h ea p p e a r a n c eo fp e e r - t o - p e e rn e t w o r ke v o l v e st h en e t w o r ka r c h i t e c t u r e o ft r a d i t i o n a lc sm o d e e v e r yn e t w o r kn o d ep l a y st h es a m er o l ei np 2 p n e t w o r k , t h e yn o to n l yo b t a i ns e r v i c ef r o mo t h e rn o d e sa sc l i e n t s ，b u ta l s o p r o v i d es e r v i c ef o ro t h e rn o d e sa ss e r v e r s p 2 pn e t w o r km a k e si tp o s s i b l et o e x c a v a t en e t w o r kr e s o u r c e sd e e p l y , a n da l s op r e s e n t sap r o s p e c t i v ef u t u r eo f c o m p u t e rn e t w o r k s op e e r - t o - p e e rn e t w o r ki sah o tp o i n ti nt h er e s e a r c hf i e l d o fi n t e m e tc u r r e n t l y p 2 pi ss o ww i d e l yu s e da sa ni m p o r t a n ta p p l i c a t i o no fi n t e m e t s t a t i s t i c s s h o wt h a tp e e r - t o p e e rn e t w o r kt r a f f i cc o n s u m e st h ef o r t yp e r c e n to rs e v e n t y p e r c e n to ft h et o t a ln e t w o r kt r a f f i c o fi s p s ，a n di tb e c o m e st h em o s t d a n g e r o u sk i l l e ro fn e t w o r kb a n d w i d t h n o ww i t ht h ei n c r e a s i n gp r e v a l e n c e o fi n t e m e ta n di n c r e a s i n gc o m p l e x i t yo fn e t w o r ka r c h i t e c t u r e ，n e t w o r k s e c u r i t y , m a n a g e m e n ta n dt h eu s eo ft h et r a d i t i o n a ls e r v i c eh a se n c o u n t e r e da c h a l l e n g e ，t h e r e f o r er e s e a r c h , d e t e c t i o n ，a n a l y s i s a n dm a n a g e m e n ta b o u t p e e r - t o p e e r t r a f f i ci s v e r yn e c e s s a r y , s i n c e i s p s w o u l d 甜j u s t t h e 第3 页 摘要 m a n a g e m e n ts t r a t e g yi nt i m ei no r d e rt oa c c o m m o d a t et h ec h a r a c t e r i s t i co f p e e r - t o 。p e e rn e t w o r k ，w h i c hi so n eo f t h ep r e s s i n gt a s k so f i s p s a m o n gt h o s e t a s k s ，t h em o s tu r g e n tt a s ki st h ee f f e c t i v ei d e n t i f i c a t i o na n dm a n a g e m e n to f p e e r - t o p e e rt r a f f i c t h i sp a p e ri sb a s e do nt h ep r o j e c t r e s e a r c ho nt r a f f i c d e t e c t i o na n dm a n a g e m e n to fp 2 p a p p l i c a t i o n ；i ti st h es u m m a r i z a t i o na b o u t s o m ep r o j e c tr e s u l t s t h ep a p e rp r e s e n t sr e s e a r c ho nf e a t u r e so fp e e r - t o - p e e r n e t w o r k , f a c t o r st h a ta f f e c tt h ep e r f o r m a n c eo fs t r i n gm a t c h i n ga l g o r i t h ma n d p e r f o r m a n c ee m u l a t i o nr e s u l t sa n dc o m p a r i s o no fs o m es t r i n gm a t c h i n g a l g o r i t h m s t h ep a p e rc o n s i s t so ff i v e c h a p t e r s c h a p t e ro n ep r o v i d e sab r i e f i n t r o d u c t i o na b o u tp 2 pt e c h n o l o g ya n dt h er e s e a r c hw o r ko fa u t h o rc o m p l e t e d i nt h e p r o j e c t ；c h a p t e rt w om a i n l yc o v e r st h er e s e a r c hs t a t u sa b o u t p e e r - t o 。p e e rn e t w o r ka n di t sd e v e l o p m e n tt r e n d ；c h a p t e rt h r e ea n a l y s e s f e a t u r e so fs o m et y p i c a lp e e r - t o - p e e rn e t w o r kt h o r o u 曲l y , a n dp r e s e n t ss o m e r e s u l t so ft h e s ep 2 pa p p l i c a t i o no nf e a t u r ea n a l y s i s ；c h a p t e rf o u rd e s c r i b e s r e l a t e dt h e o r ya b o u ts t r i n gm a t c h i n gf l g o r i t h m ，a n a l y s i sa n de x p e r i m e n t r e s e a r c ho fs o m ec l a s s i c a la n dm o d i f i e d s t r i n gm a t c h i n ga l g o r i t h m s e m u l a t i o no np e r f o r m a n c ec o m p a r i s o no fs o m es t r i n gm a t c h i n ga l g o r i t h m s a n d t y p i c a l p 2 p a p p l i c a t i o n 钔g i v e n c h a p t e r f i v e g e n e r a l i z e s h a r d w a r e - b a s e d p e e r - t o - p e e rt r a f f i c i d e n t i f i c a t i o n t e c h n i q u e ，a n df i n a l l y s u m m a r i z e st h er e s e a r c hw o r ki nt h ep a p e ra n dap r o s p e c to fp 2 pr e s e a r c hi n 第4 页 北京邮电大学硕士研究生学位论文 t h ef u t u r e k e yw o r d s ：p e e r - t o p e e rn e t w o r k s t r i n gm a t c h i n ga l g o r i t h m t r a f f i cd e t e c t i o n p a t t e m f a l s en e g a t i v e 第5 页 第一章绪论 1 1 研究背景 第一章绪论 对等网络( p e e r - t o - p e e r ，p 2 p ) 是目前流行于计算机网络领域的一个研究热点， 它被广泛地应用于网络互联技术领域，极大地提高了因特网中信息、带宽和计算资源 的利用率，改变了现有网络的应用模式，也为未来网络的发展提供了种新的组网思 路，财富杂志将其列为影响因特网未来的四项科技之一i ij 。 对等网络p 2 p 并不是一个全新的概念，现代互联网整体架构的基础t c p 仰协议 中并没有客户机和服务器的概念，所有设备都是通讯中平等的一端。上世纪7 0 年代 末8 0 年代初出现的u s e n e t 8 l 和f i d o n “9 】系统都采用了p 2 p 的思想，u s e n e t 作为 一种分布式新闻组系统，通过u u c p ( u n i x - t o - u n i xc o p yp r o t o c 0 1 ) 协谢”l 在计算 机之间进行文件复制，该协议使得任意一台u n i x 计算机都可以拨号到另外一台 u n i x 计算机上，并在交换完文件后自动断线。f i d o n e t 和u s e n e t 类似，也是一个 分布式信息交换系统，目的是让不同的b b s 系统用户可以互相交换信息，这种符合 人们需要的技术迅速成长起来，并且今天还在使用着。u s e n e t 和f i d o n e t 都是值得 探究的系统，因为它们在多年前就遇到并解决了许多当今对等网络p 2 p 技术所面临 的问题。另外d n s ( d o m a i nn a m es y s t e m ) 也是一个仍在使用的经典p 2 p 例子，它 完成因特网域名和口地址之间的映射，d n s 之所以属于p 2 p ，是因为每个d n s 既可 以是服务器接受其他d n s 的请求，也可以是客户端向其他d n s 发出请求。 近年来随着因特网飞速发展、网络带宽成倍增加以及计算机计算能力大大提高， p 2 p 又以一种新的形式引起了人们的关注。这主要归功于音乐文件共享软件n a p s t e r t “】 的成功运行，它是由1 9 岁美国大学生绍恩法宁设计开发，与以往的f r p 服务器不同， n a p s t e r 所有共享的m p 3 文件都是用户提供，服务器只保留m p 3 文件目录及其所在 的地址，当用户需要下载某文件时，首先通过服务器查到此文件所在的计算机地址列 表，再与列表中任意一台计算机建立连接，进行文件传输，由于不经过服务器，因此 不存在带宽问题，并且共享资源可以是无穷无尽。2 0 0 0 年1 2 月，n a p s t e r 拥有的用 户已达5 千万，它使得p 2 p 模式风靡全球。虽然n a p s t e r 因涉嫌违反版权法于2 0 0 1 年3 月关闭，但是网络业界却普遍认为p 2 p 技术蕴涵着不可忽略的价值。 p 2 p 让成千上万台计算机能够自由地通过因特网之间传送资料，使个人计算机不 再是被动的客户机，而是具有服务器和客户机特征的设备，让人们通过互联网直接交 第8 页 北京邮电大学项士研究生擘位论文 互，使网上沟通变得更容易、更直接。p 2 p 带来的另一个变化就是改变了“内容”所 在的位置，内容正在从。中心”走向“边缘”，也就是说内容将不再主要存在几个服 务器上，而是存在所有用户的个人计算机上，将互联网的存储模式e h 现在的“内容位 于中心”模式转变为“内容位于边缘”模式，改变了因特网现在以门户网站为中心的 状态，重返“非中心化”，把控制权交还给用户。 人们通过p 2 p 可以共享硬盘上的文件、目录甚至整个硬盘，其信息量是非常令 人激动的，那些费心存储在自己硬盘上的东西肯定是我们认为最有价值的东西，所有 的人都共享了他们认为最有价值的东西，这将使互联网上信息的价值得到极大地提 升。对等网络如何提高互联网上的信息价值，d a v i dr e e d 做了如下分析【1 2 】【1 3 】，提出 了三个网络法则，其中n 表示网络中对等设备的总数。 s a m o f f 法则：网络的效益与n 成正比。该法则认为网络是广播媒介，有少数发 送者和很多接收者，这里网络给单个独立设备提供的服务带来线形效益； m c t c a i f e 法则：网络的效益与n 2 成正比。该法则认为网络是全互联的媒介，任 何一个设备可以与其他n 一1 个设备交互，允许同时有n ( n - 1 ) 个设备交互，允许同 时有n ( n 1 ) an 2 个事务同时执行； 夺 r e e d 法则：网络的效益与2 ”成正比。该法则认为网络是群组媒介，有 2 一n 一1z2 。个小组组成，它的效益是指数效益； 对等网络在各个方面都增加了网络效益：针对s a m o f f 法则，网络增加了发送者 和接收者的数目；针对m e t c a l f c 法则，增加了参加事务处理的个数；针对r e e d 法则， 增加了网络中小组的个数。 对等网络使网络上的计算机都变成了服务器，共享它们的计算能力、存储和信息 资源，极大地增加了网络效益。因为每个计算机都代表了其后的人，基于自发组织的 网上社区也正在显现，与门户站点从上而下建立社区的方式不同，人们将以自发的方 式形成社区。当人们加入p 2 p 网络的时候，所有人都拥有了极容易地在网络上创造 “内容”机会，p 2 p 使所有上网的人拥有了平等的机会。 1 2 对等网络的技术特点 p 2 p 网络的技术特点主要体现在以下几个方面： 非中心化( d e c e n t r a l i z a t i o n ) ：网络的资源和服务分散在所有节点上，信息的传 输和服务的实现都直接在节点之间进行，无需中间环节和服务器的介入，避免了可能 的瓶颈。p 2 p 的非中心化的基本特点，给网络带来了可扩展性、健壮性等方面的优势。 可扩展性：在p 2 p 网络中，随着用户的加入，不仅服务的需求增加了，系统整 第9 页 第一幸绪论 体的资源和服务能力也在同步扩充，始终能较容易地满足用户的需求。由于整个体系 是全分布式的，所以相应的可扩展性在理论上是无限的。 健壮性：p 2 p 架构具有耐攻击、高容错的优点。由于服务是分散在各个节点之 间进行，所以部分节点或者网络遭到破坏对其他的部分影响很小，而且一般情况下当 其他节点失效时网络能自动调节整体的拓扑，保持其他节点的连通性。p 2 p 网络通常 都是以自组织的方式建立起来的，并允许节点自由地加入和离开。此外，p 2 p 网络还 能够根据网络带宽、节点数、负载等变化不断地做自适应的调整。 高性价比：性能优势是p 2 p 被广泛关注的一个重要原因。随着硬件技术的发展， 个人计算机的计算能力和存储能力以及网络带宽性能依照摩尔定律高速增长。采用 p 2 p 架构可以有效地利用互联网中分散的大量普通节点，将计算任务或者存储资料分 布到所有节点上，利用闲置的计算能力或者存储空间，达到商性能计算和海量存储的 目的，这样可以用较低的成本提供更高的计算和存储能力。 隐私保护：在p 2 p 网络中，由于信息的传输分散在各节点之间进行而无需某个 集中环节，用户的隐私信息被窃听和泄漏的可能性大大缩小此外，目前解决i n t e r a c t 隐私问题主要采用中继转发的技术方法，从而将通信的参与者隐藏在众多的网络实体 之中。在传统的一些匿名通信网络中，实现这一机制依赖于某些中继服务器节点。而 在p 2 p 网络中，所有参与者都可以提供中继转发功能。因而大大提高了匿名通信的 灵活和可靠性，能够为用户提供更好的隐私保护。 负载均衡：在p 2 p 网络环境下，由于每个节点既是服务器又是客户机，减少了 对传统c s 结构服务器计算能力、存储能力的要求，同时因为资源分布在多个节点， 更好地实现了整个网络的负载均衡。 1 3 对等网络的研究现状 自从上世纪9 0 年代末对等网络p 2 p 的出现以来，其应用随着互联网的普及迅速 增加，对当前互联网流量特征产生了巨大的影响，因此对对等网络进行深入的研究有 着重要的意义。 p 2 p 是一把双刃剑，应用得好，将加速分发的渠道，并避免服务器瓶颈；应用得 不好，将成为盗版泛滥的平台。当前，p 2 p 的巨大流量给运营商造成很大压力，增加 了其运营成本，尤其是网际互联费用。但是封堵p 2 p 会造成客户流失更是运营商所 不愿意看到的。目前一种解决办法是运营商在其网络服务器中缓冲p 2 p 流，以便减 少外出流量和网际互联费用。另外对于混合式p 2 p 结构，一些超级结点分布在网络 关键的地方，存在流量分布不平衡的问题，所以要对其采用分布式管理。近几年来， 第l o 页 北京邮电大学硕士研究生学位论支 围绕p 2 p 开展的研究主要分为以下几方面： p 2 p 网络结构、路由算法和资源搜索机制的研究 在c s 应用模式中，网络搜索引擎起着信息导航作用，著名的搜索引擎如b a i d u 、 g o o g l e 等采用c s 服务模式响应资源查找请求，而p 2 p 模式中，资源存储在网络边缘 节点处，如何高效地进行资源搜索是p 2 p 的核心问题之一。目前对等网络所采用的 资源搜索机制有集中目录式、洪泛查找请求方式、分布式哈希表( d i s t r i b u t e dh a s h t a b l e ，d h t ) 方式等，集中目录式可以提供可靠的资源查找性能，但是随着用户的 增多，目录服务器将成为整个系统的瓶颈，因此这种资源搜索机制的可扩展性不好。 在洪泛查找请求方式中，资源和节点之间没有确定的对应关系，会产生大量的网络流 量，不过其优点是节点动态变化的处理比较简单。d h t 方式是在构建覆盖网络时严 格地控制着网络拓扑结构和资源信息的存储位置，从而可以进行高效的、可扩展的资 源搜索，是目前最具有发展前景的资源查找机制，然而d h t 中哈希函数的使用破坏 了网络节点的地理位置性，另外严格控制的覆盖网络拓扑与底层物理网络拓扑之间的 关系并未得到重视，d h t 方式仅支持单关键字的简单精确查询等等，总之，目前d h t 技术还不成熟，还有很多问题需要解决。 安全问题的研究 网络结构从集中式转变到分布式，面i 临的最大问题就是安全问题。在分布式环境 中，不仅存在目前网络环境中同样的安全威胁，也带来了动态环境中如何保障资源和 系统安全的新课题。由于没有集中控制，p 2 p 需要安全环境来保证无序行为的有序化。 与目前的c s 模型中面临的安全问题相似，p 2 p 技术中的主要安全问题包括：用户认 证问题、数据加密和解密问题、路由安全问题、存储与访问安全问题、恶意破坏问题、 故意欺骗问题、应用安全问题和个人隐私问题。 资源管理的研究 对等网络中资源的管理要比传统的c $ 模式困难，主要因为网络节点的自组织 性，需要合理的机制激励节点主动贡献资源，另外对等网络的规模巨大，网络节点频 繁地加入和离开网络，资源和资源的需求在不断变化，很难得到有效资源的完整分布 图。可以采用经济学上的概念来构建一个资源市场，节点对所需的资源进行买卖交易， 以增强节点共享资源的主动性，比如对等网络为了让网络中的资源有充足的备份、更 长的生存时间，会将资源复制到多个节点处，但有些节点并不乐意在没有回报的情况 下贡献出自己的存储空间，在交易机制下，每个节点都愿意贡献出自己的一部分存储 空问以获得其他节点的存储空间，这样节点都拥有自己资源的备份，一系列的交易建 立起来后就形成p 2 p 复制网络，从而提高资源的可获得性，同时也极大地丰富了网 第1 l 页 第一幸绪 论 络的资源 p 2 p 网络行为特征与系统测量的研究 目前，随着i n t e r a c t 日益普及和网络结构的日益复杂，网络的安全性、可管理性 及其传统应用的可用性收到了严重挑战虽然p 2 p 已经成为重要的网络应用，其流 量已占据互联网流量4 0 7 0 ，它不论在知识产权保护方面还是在防病毒抗攻击 等方面都存在很多问题，但是制约p 2 p 发展的关键是盗版问题和流量控制问题，此 外，如何测量和评估p 2 p 应用的性能以及如何使网络提供满意的p 2 p 服务，是一个 亟待解决的问题。p 2 p 系统测量是解决问题的基础，所以对的p 2 p 应用进行深入的研 究和分析，以便进一步管理p 2 p 流量，并及时调整经营策略以适应p 2 p 流量的特点， 已成为每个互联网服务提供者的紧迫课题。而其中最首要的任务就是对p 2 p 流量进 行有效的识别和管理。 1 4 论文结构与内容 本文基于实验室与华为技术有限公司合作的 p 2 p 应用流量管理的研究课题， 深入研究了p 2 p 流量的动态识别与管理。p 2 p 流量识别一般是通过报文中是否包含某 种p 2 p 业务肯定包含的特征字符串来识别的，但是随着p 2 p 应用的多样化，这种识 别方法也存在一定的局限性。由于p 2 p 网络中各个节点地位相等每个对等节点性 能，如节点连接在网络上的时间、加入和退出网络的频繁程度、提供共享空间的大小、 对等节点之间的连通性等，都会对整体性能产生影响，因此，建立一个合理的p 2 p 网络流量模型，综合研究其流量分布、性能指标及其相关的影响因素、探索相应的测 量方法对p 2 p 应用的发展有着重要的实用价值。 本课题主要采用传输层和应用层联动的方式来对p 2 p 流量进行动态地识别与管 理。在对p 2 p 应用识别的基础上，这种多层联动的系统可以选择支持两种p 2 p 应用处 理方式：封堵和标记，图1 1 是系统识别的流程。主要分为三个模块：数据预处理： 传输层过滤；应用层识别。对于数据预处理，其功能主要有：完成必要的数据格式转 换，过滤掉非i p 包，将标准i p 包送入传输层模块，经过传输层过滤后的数据再送往 应用层进行精确识别。本人的主要研究内容是课题中应用层识别模块部分，即完成应 用层对p 2 p 流量做准确而快速地识别。为此，本文首先深入分析了多种应用广泛的 p 2 p 网络行为特征、选取响应的特征模式，接着对几种经典的字符串匹配算法性能进 行分析研究，从而选出高效的字符串匹配算法在应用层做精确识别。全文的主要内容 如下： 第1 2 页 北京邮电大学顷士研究生学位论文 m a c层数据包 ， 三三 岳 是i p 赞 一一十 否 l 。彳：洙三兰竺 日 图i 1 系统识别流程 第一章：绪论。本章主要论述了论文的研究背景和选题意义，首先分析了对等网 络的技术特点，随后对对等网络的应用进行了探讨，根据制约对等网络发展的一个主 要问题，即网络流量的管理问题提出了本文的研究内容和研究意义。由于对等网络是 一个典型的由应用推动的研究领域，所以解决应用中存在的问题是本文的研究目的。 最后，总结了本文的主要研究工作。并给出论文的章节安捧。 第1 3 页 - 一一 传输层与应用层联动 第一幸绪论 第二章：对等网络的研究现状及发展趋势。本章首先分析了计算机网络应用模式 的演变过程，随后对对等网络的发展过程进行了分析。接着就本文的研究方向，简要 分析了前人工作的优点和不足，最后结合当前的应用情况提出了本文的研究内容和思 路。 第三章：对等网络行为特征分析要对p 2 p 网络流量做出准确的识别，首先必 须对相应的网络特征进行详尽的分析。目前对等网络的发展还没有一个统一的标准， 所以出现了多种有效的p 2 p 应用，本章就当前几种应用广泛的p 2 p 网络进行深入的 分析，并按照其特征进行了简单的归类，同时总结出了相应的应用层识别特征模式。 第四章：字符串匹配算法性能分析及实验研究。在应用层进行准确、快速地流量 识别的基础就是字符串匹配算法的有效利用，所以选用一个高效的算法对系统识别有 着重要意义。本章首先简单介绍了字符串匹配技术的应用与研究现状，然后就几种经 典字符串匹配算法的原理进行了分析，接着主要深入探讨了影响字符串匹配算法性能 的因素，最后从实验研究的角度对字符串匹配的算法进行了性能分析和仿真，从而针 对相应的算法总结出最有效的p 2 p 流量特征识别模式。 第六章：基于硬件的p 2 p 流量检测的研究。在通用的处理器上实现基于软件的 流量检测与管理时，其吞吐量通常只能达到百兆左右，虽然实现方式灵活，但其性能 速度已不能充分满足日益增长的应用需求，网络安全设备如入侵检测、内容过滤等功 能要求数据包达到吉比特的扫描速度，所以基于硬件的实现是高速并行处理系统的首 选。本章首先提出了基于硬件实现的必要性，然后研究分析了当前基于硬件的多种方 法及其优缺点，同时指出课题下一步工作研究和改进的重点。 第1 4 页 北京邮电大学硕士研究生擘位论文 第二章对等网络的研究现状与发展趋势 2 1 网络应用模式的演变 随着互联网规模的迅速发展，人们如何利用网络为其提供方便快捷地服务成为一 个热点问题。与此同时，计算机的计算能力按照摩尔定律在飞速地增长，网络带宽在 成倍地增加，利用快速发展的网络技术将各种计算资源整合到一起，从而实现资源的 高效利用，其可行性及迫切性已经被广泛认同，对等网络就是基于这种形势出现的。 在计算机网络四十多年的发展历程中，其应用模式首先从主从模式、经c s 模式 睇j 。随着技术的发展，现在充当客户机的计算机在性能上有的已经达到甚至超过了早 期的大型主机，它们不但可以请求服务，同时也可以提供服务，所以网络的应用模式 就从c s 模式逐步演变到p 2 p 模式1 w 】。在纯粹的对等模式中，参与网络的各个计算 机是完全对等的，没有严格地划分客户机和服务器，各个计算机因为互为服务而共存， 不依赖于特定的集中式机制，各个节点可以直接交互信息，同时可能随时离开网络。 2 2 对等网络的定义 目前，对等网络技术正在处于不断发展的阶段，因而尚未给出一个精确的定义， 当前给出的许多定义都是尽可能去反映对等网络发展过程中某阶段的新特征。以下是 一些著名研究机构给出的对等网络的定义： i b m ：p 2 p 系统由若干互联协作的计算机组成，并且至少具有如下特征之一：系 统依存于边缘化( 非中央式服务器) 设备的主动协作，每个成员直接从其他成员而不 是从服务器处受益；系统中的成员同时扮演服务器与客户机的角色；系统中的用户能 够意识到彼此的存在，构成一个虚拟或实际的群体。 i n t e i 的p 2 p 工作组：p 2 p 通过在系统之间直接交换来共享计算机资源和服务， 这些资源和服务包括信息交换、高速缓存、处理能力、存储空间。p 2 p 可以整合这些 p c 机上计算能力和网络连接，从而提供企业级的计算平刨。 c i a ys h j r k e y ：p 2 p 是一种利用因特网边缘各种可用资源( 如存储空间、计算能 力、媒体内容) 的应用。访问这些分散的资源，就意味着要在连接不稳定和口地址 不可预见的环境里工作，由于网络上大量的节点工作在d n s 系统之外，这些分散的 资源具有不稳定的连通性和未知的口地址。因此p 2 p 节点必须能够独立于d n s 系统 第1 5 页 第二幸p 2 p 同络的研究现状与发曩趋势 且高度自治【”】。 r m sl e eg r a h a m ：p 2 p 系统有三个关键特性具有服务器的操作能力；有独 立d n s 的寻址系统；能够处理变化的网络连接【l 们。 m i k em i l e r ：p 2 p 是一个网络体系，其中每个计算机具有相同的能力和责任。 m i l e r 定义了五个关键特性：网络提供节点问实时的数据传输和消息传递；节点 既是客户机又是服务器；网络的内容是由分散的节点提供；节点具有网络控制权 和自治权；网络允许不总是连接的节点和可能没有永久口地址的节点参与【l ”。 p 2 p 是一个用于资源共享的网络节点群体，其中每个节点向群体提供资源同时作 为回报从中获取所需资源，其基本思想是基于世界上的事物是广泛分布且相互联系 的，不可能通过一种集中化的方式管理如此庞大的结构，p 2 p 通过分布于世界各地的 个人计算机管理大量的计算能力、存储空间和网络连接。p 2 p 网络中每个节点自治又 彼此依赖，所谓自治是指每个节点独立决定自己的行为而不受其它例如集中式授权机 构的控制，同时每个节点又需要相互协作获得信息资源和计算资源。 2 3 对等网络的发展 为了发挥互联网无所不在的优势，不对互联网协议进行任何修改，解决的办法就 是在基础的互联网上架设一个p 2 p 重叠网。p 2 p 重叠网分为“无组织的p 2 p 重叠网” 和“有组织的p 2 p 重叠网”两大类。目前在互联网上广泛使用的大多是无组织的p 2 p 重叠网，而有组织的p 2 p 重叠网目前还处于学术界研究阶段，如t a p e s t r y 、c h o r d 、 p a s t r y 、和c a n 等。正在研究的新一代的p 2 p 应用包括多播、网络存储等都运行在 这种有组织p 2 p 重叠网之上。无组织的p 2 p 重叠网已经演进了四代。 第一代p 2 p 采用中央控制网络体系结构。该类网络中节点的地位和责任不完全 相等，存在有服务器的概念，但是这里的服务器与传统意义上的服务器不同，它只提 供资源信息，而不提供资源本身，典型的代表有n a p s t e r 、b i t t o r r e n t i ”】( 简称b t ) 、 e d o n k c y 【19 】等。n a p s t e r 中目录服务器保存节点共享资源的信息，当网络中某个节点需 要查找资源时，首先向目录服务器发送查询请求，根据响应消息得到存放该资源的目 的节点地址，然后直接从该节点下载资源，如图2 1 所示。虽然文件的传输发生在节 点之间，但资源查询是通过服务器来完成的，随着用户数量增加，目录服务器可能成 为整个系统的瓶颈，因此本类网络结构的可扩展性较差。 第1 6 页 北京邮电大学顷士研究生擘住论文 图2 1 中央控制式的p 2 p 网络 b i t t o r r e n t 协议和同名软件是由美国旧金山的软件工程师布莱姆科亨开发的。在 b t 中服务器称为t r a c k e r ，用来保存共享资源的信息。资源提供者称为种子，而资源 下载者称为用户。b t 中共享资源被分为n 块，文件和文件块用s h a i h a s h 2 0 】标识， h a s h 值既是文件的标志。也可用来验证文件的完整性，共享资源的信息保存在扩展 名为t o r r e n t 的文件中，具体包括t r a c k e r 服务器的地址、资源的描述信息、资源的校 验信息等，t o r r e n t 文件通常借助w e b 网站发布。如果用户甲在种子处随机下载了资源 的第1 个部分，而乙在种子处随机下载了第j 个部分，这样甲会根据情况从乙处下载 已经下载好的第j 部分，同理乙也会根据情况到甲处下载甲已经下载好的第1 个部分， b t 客户在下载的同时也上传，所以b t 的特点就是下载的人越多，下载速度就越快 通过b t 下载某文件时，首先在网上搜索对应的t o r r e n t 文件，根据其包含的信息，连 接t r a c k e r 服务器获知正在下载该文件的节点信息，并与之建立连接，下载文件。 e d o n k e y 是由j o dm c c a l e b 于2 0 0 0 年创立的，其资源定位由服务器来提供，文 件的传输在节点之间进行，e m u l e 是e d o n k e y 的升级版，原理和运作方式与e d o n k e y 相似不过它同时提供了一些新的功能，比如可以自动搜索网络中的服务器、保留搜 索结果、与连接用户交换服务器地址和文件、优先下载便于预览的文件头尾部分等， 第1 7 页 g _ - 章p 2 p 网络的研究现状与发展趋势 这些都使得e m u l e 使用起来更加便利。它和b t 类似，采用了多源文件传输协议，同 一个文件可以从多个节点处分别下载不同的文件块，节点越多，下载速度越快，从而 使得整个系统在资源传输方面具有极强的可扩展性，不过e d o n k e y 具有信用系统， 如果用户只下载不上传，那么积分会越来越少，下载速度也就越来越慢，以便鼓励用 户间多提供上传。本系统的缺点在于，一旦t r a c k e r 服务器连接不上，整个系统就无 法正常运行，因此最新版本的b t 和e m u l e 都采用纯对等网络中结构化对等网络的资 源搜索机制。 第二代p 2 p 采用分散分布网络体系结构。所以又称纯对等网络。该类网络中的 节点地位相等，每个节点和其他若干节点相连，目前纯对等网络相当于在现有物理网 络上虚拟了一层“叠加”拓扑，属于“叠加网络”。“叠加”的网络拓扑结构没有严格 限定且资源的存放同叠加拓扑没有任何联系，这种网络称为非结构化网络，典型代表 包括c m u t e l l a i 2 1 】【2 2 1 、f r e e n e d 2 3 1 等，如图2 2 所示。g n u t e l l a 是最早运行在因特网上的 大规模的纯对等网络，它采用洪泛的方式进行资源查找和搜索，当某节点需要查找资 源时，它就向其所有邻居节点广播查找请求消息，邻居节点也将中转广播消息，其广 播查找的范围用r r l 参数来控制。拥有该资源的节点则响应该资源查找请求。 f r e e n e t 的最大特点是匿名，文件的发布者、查询者包括文件的持有者都是匿名 的。为了实现匿名，f r e e n e t 在路由上降低了效率，路由中的每个节点不能判断前一 个节点是否是文件的请求者，也不能判断后一个节点是否是文件的持有者。为了获得 一个文件，用户必须首先获得文件描述符并计算二进制文件关键字，然后发送包括文 件关键字和t t l 值的请求，当节点收到请求后，首先对消息中的关键字进行本地匹 配，匹配成功则返回应答，如果匹配失败，则在其路由表中查找和请求关键字最相似 的关键字，并把请求递交到相应的节点。如果请求最终匹配成功且返回数据，数据将 在请求路径上逆向转发，沿途每个节点在本地缓存该资源，并在路由表里创建关联实 际数据源和该关键字的表项，以后对该文件的请求将从本地缓存中立刻得到满足。如 果由于目标节点失败或者查询循环路径出现导致某节点转发给下游节点的请求失败， 该节点则使用第二最近的关键字、第三最近关键字，依次类推。如果节点尝试了路由 表中的所有节点均失败，就给上游节点报告转发失败消息，上游节点同样对路由表中 各个节点进行尝试。如果到达兀l 极限，文件请求失败后，响应消息返回到文件请 求者并不再尝试，所有节点都可以削减t t l 值以减轻网络负载。f r e e n e t 中并没有明 确规定某个具体节点负责某部分文档，查找采用搜索文件副本的方式，因此可以提供 某种程度的匿名，但是不能保证一定能找到网络中存在的文档，并且降低了路由效率。 第1 8 页 北京邮电大学硕士研究生学位论文 图2 2 分散分布式的对等网络 结构化对等网络严格控制着“叠加”的网络拓扑和资源的存放，其主流技术是分 布式哈希表( d i s t r i b u t e h a s h t a b l e ，d h t ) ，其基本思想是为网络节点和网络资源赋 予唯一可识别的关键字，通过哈希函数将资源和节点映射到相同的值空间，根据某种 距离测度在资源和节点之间形成一定的对应关系，为了在有限逻辑跳内查找定位资 源，节点之间连接都是参考特定网络拓扑结构。典型结构化对等网络的代表有 c h o r d l 2 4 1 、p 笛h v 擒、t a p e s 蚋1 2 6 卅和c a n i 等。 第三代p 2 p 网络采用混合网络体系结构，又称超级对等网络该类网络特点是 包括了“超级节点”的概念，超级节点的结构借鉴了混合式对等网络和纯分布式网络 的优点，通过选择网络中具有较高带宽、较大内存和存储空间以及较强c p u 处理能 力的节点为超级节点，并通过超级节点存储其周围其他节点共享文档的索引来提高搜 索的性能，如图2 3 所示。超级节点除了继续扮演本身的普通节点角色之外，还担当 局部目录服务器的角色，与类似n a p s t e r 的混合对等网络中的中央目录服务器不同的 是，超级节点的选择是动态的，它们像普通节点一样，随时可能离开网络，一旦网络 发现某个超级节点不再工作，就采用某种选举机制通过比较某个区域内节点的c p u 处理能力、内存和存储空间的大小以及网络带宽的高低等资源信息重新选择一个资源 丰富的节点担任超级节点。网络中节点对于某个资源的查找将首先被发送给它所在区 第1 9 页 第二幸p 2 p 网络的研究现状与发展趋势 域的超级节点，如果这个超级节点没有存储关于该资源的任何信息，那么它继续将查 询请求转发给其他超级节点，这种转发方式就是泛洪方式，仅在超级节点之间通过泛 洪转