（计算机应用技术专业论文）结构化对等网络覆盖网路由机制关键技术研究.pdf

结构化对等网络覆盖网路由机制关键技术研究 摘要 因特网( i n t e m e t ) 技术的发展日新月异，向全球用户展现出了一系列具有创造 性的分布式应用成果。作为计算机处理能力提高和网络技术发展的直接产物，对 等网络( p e e r - t o - p e e r ，p 2 p ) 系统已经成为占据i n t e m e t 网络流量最多的新型网络应 用。p 2 p 覆盖网路由机制设计是构建p 2 p 系统的核心问题，本文就结构化p 2 p 覆盖网 路由机制的路由本地性问题、抗扰动问题和p 2 p 应用系统任务分配问题等三个重要方 向展开了研究，提出了新颖有效的路由机制构建方案；并且结合路由机制研究的成 果，构建了p 2 p 应用系统原型一一基于p 2 p 技术的w e b 搜索联盟。本文的主要贡献和 创新点为： ( 1 ) 提出了组合逻辑空间临近路由选择算法和物理网络临近路由选择算法的路 由机制，在保持c h o r d 覆盖网低开销特点的同时，解决了c h o r d 覆盖网的路由本地性 问题。 c h o r d 作为典型的结构化p 2 p 覆盖网，采用了逻辑空间上的临近路由选择算 法，实现了覆盖网路由的正确性和可扩展性，并且具有覆盖网维护开销低的特 点。然而，由于c h o r d 的设计中完全没有考虑参与结点在物理网络上的拓扑关系， 使c h o r d 在路由本地性方面的性能很差。并且，由于c h o r d 独特的路由机制。使得 现有的路由本地性研究成果，如临近邻居选择方案和网络拓扑标识指定方案等， 不能被借鉴n c h o r d 覆盖网中来。本文将物理网络的临近路由选择算法有机地组 合至u c h o r d 的路由算法中，围绕此组合临近路由选择策略构建了新的p 2 p 覆盖网 一- - p c h o r d ( p r o x i m i t yc h o r d ) p c h o r d 在解决路由本地性问题的同时，依然保持 了c h o r d 覆盖网开销低的优秀特点。 ( 2 ) 提出了能够利用p 2 p 结点会话时间的差异性，从而优化解决p 2 p 覆盖网扰动 问题的路由机制，在较好地控制结构化p 2 p 覆盖网维护开销的基础上，提高了p 2 p 覆 盖网的抗扰动能力。 p 2 p 结点频繁地加入和退出覆盖网，称为对等网络的“扰动”问题。扰动问题 是p 2 p 系统区别于传统分布式系统的独特问题。本文在综合p 2 p 应用系统跟踪实验结 果的基础上，分析了结点会话时间的概率分布规律，提出了新型的覆盖网路由机制 一- - s c h o r d ( s e s s i o nc h o r d ) 。s c h o r d 的特点是，在依概率估计的基础上，充分发 1 上海交通大学博士学位论文 挥了会话时间长的结点在覆盖网抗扰动过程中的作用。本文从理论分析和仿真实验 两个层面上，确定了s c h o r d 路由机制的具体参数和优化性能，证明了s c h o r d 能够在 较好地控制覆盖网维护开销的基础上，提高p 2 p 覆盖网的抗扰动能力。 ( 3 ) 提出了能够适应p 2 p 应用系统任务差异性，从而实施- p 2 p 应用系统任务分配 优化策略的路由机制，提高了p 2 p 应用系统的任务响应时间、吞吐率和公平性等性能 指标。 任务响应时间、吞吐率和公平性等性能指标，是分布式系统设计的重要问 题。p 2 p 系统作为分布式系统的新发展，也必须优化这些分布式应用系统的重要性 能指标。本文在分析了实际应用系统任务分布规律的基础上，提出了对覆盖网参与 结点进行分组整合的组织方式，并构造了相应的覆盖网路由机制。从而，通过实施 适应p 2 p 应用系统任务差异性的任务分配策略，提高了p 2 p 应用系统的性能指标。 本文在c h o r d 的基础上实现了此路由机制一- - v c h o r d ( v i r t u a lc h o r d ) 。仿真实验证 明，v c h o r d 在闭环网络环境下实现了吞吐率的提高和任务响应时间的缩短：在开环 网络环境下实现了平均等待时间和平均降速的降低，以及更好的系统公平性。 关键词：对等网络、覆盖网、路由机制、分布式哈希表、临近路由选择、扰动、任 务分配 一一 r e s e a r c ho nk e yt e c h n i q u eo fr o u t i n gm e c h a n i s mo f s t r u c t u r e dp e e r - t o - p e e ro v e r l a y a b s t r a c t r e c e n t l y 。t h e r eh a v eb e e nl o t so fn e wn e t w o r ka p p l i c a t i o ns y s t e m sa p p e a r i n go nt h e i n t e r n e t t h ep e e r - t o - p e e r ( p 2 p ) a p p l i c a t i o ns y s t e mi st h em o s tt y p i c a lo n eo ft h e m , w h i c h h a so c c u p i e dt h em a j o r i t yo fi n t e r n e tt r a f f i c r o u t i n gm e c h a n i s mi st h ec r i t i c a li s s u ew h e n c o n s t r u c t i n gp 2 po v e r l a y t h e r e f o r e ，t h i sd i s s e r t a t i o nf o c u s e so nt h er e s e a r c ho f k e y t e c h - n i q u eo fr o u t i n gm e c h a n i s mo fs 仃u c m r e dp 2 po v e r l a y , i n c l u d i n gr o u t i n gl o c a l i t yp r o b l e m , c h u mh a n d l i n gp r o b l e ma n dt a s ka s s i g n m e n tp r o b l e mo fp 2 ps y s t e m t h r e en e wr o u t i n g m e c h a n i s m so fp 2 po v e r l a ya r ep r o p o s e di nt h i sd i s s e r t a t i o na st h eo u t p u to fr e s e a r c ho n t h el i s t e dt h r e ek e yp r o b l e m so fr o u t i n gm e c h a n i s m b a s e do nt h e s er e s e a r c h , an e w p 2 p a p p l i c a t i o ns y s t e m - t h ew e bs e a r c hu n i o no ns t r u c t u r e dp 2 po v e r l a y - w i l lb ei l l u s t r a t e di n t h i sd i s s e r t a t i o n , t o o m a i nc o n t r i b u t i o ne n dt h ec r e a t i v ep o i n t so ft h i sd i s s e r t a t i o na r ea s f o l l o w i n g ： ( 1 ) an e wr o u t i n gm e c h a n i s m n a m e dp c h o r d ( p m x i m i t yc h o r d ) ，i sp r o p o s e di nt h i sd i s - s e r t a t i o n p c h o r da i m st oa c h i e v eb e t t e rr o u t i n ge f f i c i e n c yt h a nc h o r d , a n dk e e p st h el o w c o s tm e r i to f c h o r do v e r l a y c h o r di so n eo f t h et y p i c a ls t r u c t u r e dp 2 po v e r l a y , w h i c ha c h i e v e sl o wc o s ti no v e r l a y m a i n t e n a n c ep r o c e d u r e ，b u td o e sn o tt a k er o u t i n gl o c a l i t yp r o b l e mi n t oa c c o u n t p l u s ，f i x - i s t i n gi m p r o v e m e n tt e c h n i q u et oa c h i e v em u t i n gl o c a l i t yc a n n o tb ei n t r o d u c e di n t oc h o r d , b e c a u s ec h o r d 璐铭i t ss p e c i a lr o u t i n ga l g o r i t h m p c h o r di st h er o u 吐n ge n h a n c e m e n tp 2 p o v e r l a yc o n s t r u c t e do nc h o r d ，w h i c hc o m b i n e st h ep r o x i m i t yr o u t i n gs e l e c t i o na l g o r i t l m a i n t oc h o r d sr o u t i n ga l g o r i t h mt os o l v er o u t i n gl o c a l i t yp r o b l e m p c h o r dh a sa c h i e v e db e t t e r r o u t i n ge f f i c i e n c yt h a nc h o r da n dk e e p st h el o w c o s tm e r i to f o v e r l a ym a i n t e n a n c ep r o c e d u r e a sc h o r d ( 2 ) an o vr o u t i n gm e c h a n i s mn a m e ds c h o r d ( s e s s i o nc h o r d ) ，i sp r o p o s e di nt h i sd i s - s e r t a t i o n s c h o r da i m st oh a n d l ec h u mp r o b l e mo f t h es t r u c t u r e dp 2 po v e r l a yb ye x p l o i t i n g t h en o d e so f l o n gs e s s i o nt i m e 1 上海交通大学博士学位论文 p 2 ps y s t e m sa r ed i s t i n g u i s h e df o r mt r a d i t i o n a ld i s t r i b u t e ds y s t e m si nt h a tn o d e sj o i n a n dl e a v ep 2 ps y s t e m sa th i g hm t e c a l l e dc h u r np r o b l e m a f t e rs u m m a r i z i n gt h er e s u l to f t r a c ee x p e r i m e n t so ne x i s t i n gp 2 ps y s t e m s ，s o m ei m p o r t a n ts t a t i s t i cc o n c l u s i o n sh a v eb e a n d r a w no nt h eb a s i so ft h e o r e t i c a la n a l y s i so nt h ep r o b a b i l i t yd i s t r i b u t i o no fn o d e s s e s s i o n t i m e s c h o r di sc o n s t r u c t e d0 1 1c h o r do v e r l a y , w h i c he x p l o i t ss u c hs t a t i s t i cc o n c l u s i o n st o m a k em o r eu o f t h en o d e so f l o n gs e s s i o nt i m ei ni t so v e r l a ym a i n t e n a n c ep r o c e d u r e f r o m t h ed e d u c t i o np r o c e s so fs c h o r d st h e o r e t i cp e r f o r m a n c ea n dt h es i m u l a t i o ne x p e r i m e n to f s c h o r d , i tc a l lb ec o n c l u d e dt h a ts c h o r dc a na c h i e v eb e t t e rp e r f o r m a n c eo nc h u r nh a n d l i n g t h a nc h o r d ，o nt h eb a s i so f c o s tc o n t r o l l i n g ( 3 ) an e wm u t i n gm e c h a n i s mn a m e dv c h o r d ( v i r t u a lc h o r d ) ，i sp r o p o s e di nt h i sd i s - s e r t a t i o n v c h o r da i m st oa c h i e v es h o r t e rt a s kr e s p o n s et i m e b e t t e rt h r o u g h p u t , b e t t e rl o a d b a l a n c i n ga n db e t t e rf a i r n e s so f p 2 pa p p l i c a t i o n s t a s kr e s p o n s et i m e t h r o u g h p u t , l o a db a l a n c ea n df a i r n e s sa 咒i m p o r t a n tf o rd i s t r i b u t e d s y s t e md e s i g n i n g p 2 ps y s t e m ss h o u l dp e r f o r mw e l lr e g a r d i n gt ot h e s ea s p e c t st o o a r e r s u m m a r i z i n gt h er e s u l to f t r a c ee x p e r i m e n t so ne x i s t i n gc o m p u t e ra p p l i c a t i o n s ，v c h o r di s c o n s t r u c t e dt oe x p l o i tt h ed i f f e r e n c eo fs i z ea m o n gt a s k s v c h o r dd i s t r i b u t e si t so v e r l a y n o d e si n ms e v e r a lg r o u p sa n de a c hg r o u pf o r m so n ec h o r do v e r l a y v c h o r di st h ec o m = p o s i t i o no v e r l a yo fa l lt h e s ec h o r do v e r l a y sw i t hi t ss p e c i a lr o u t i n ga l g o r i t h m a no p t i m a l t a s ka s s i g n m e n ta l g o r i t h mi sr e a l i z e db a s e d0 1 1v c h o r dt oh e i pt h ea p p l i c a t i o n so nv c h o r d t oa c h i e v eb e t t e rp e r f o r m a n c e t h es i m u l a t i o ne x p e r i m e n tp r o v e st h a tt h ea p p l i c a t i o n so n v c h o r dc a na c h i e v eb e t t e rt h r o u g h p u ta n ds h o r t e rt a s kr e s p o n s et i m ei nc l o s e dn e t w o r ks y s - t c mt e s t , a sw e l la ss h o r t e rm & a nw a i t i n gt i m e ，l o w e rs l o w d o w na n db e t t e rf a i r n c s si no p e n n e t w o r ks y s t e mt e s l k e yw o r d s ：p e e r - t o - p e e r , o v e r l a y , m u t i n g ，d h t , p r o x i m i t yr o u t i n g ，c h u m , t a s ka s s i g n m e n t i v 第一章序论 1 1 对等网络概述 近年来因特网( i n t e m e t ) 技术的发展日新月异，向全球用户展现出了一系列具 有创造性的分布式应用。其中，最流行的应用无疑是对等网络( p e e r - t o p e e r , p 2 p ) 应用系统；因为p 2 p 应用系统不仅在因特网内有广大的用户群，而且也在因特网外引 起了方方面面的关注。首先，p 2 p 系统由于方便、快捷和开销少受到了数以千万网络 用户的欢迎。其次，p 2 p 应用已经成为占据因特网整个流量的5 0 强的应用，使得网 络营运商不得不调整对网络应用的监管策略。再次，p 2 p 应用提供的及时通讯技术 正在日益取代传统电信服务商提供的通讯服务，引发了电信服务商、电信设备商和 网络营运商的新一轮设备竞争和业务整合。最后，p 2 p 应用提供的文件下载，引起 了司法界的关注；第一个广泛应用的基于p 2 p 技术的音乐共享系统n a p s t e r 【l 】，就曾 于2 0 0 1 年被美国司法部以违反版权法为理由关闭。 p 2 p 系统在产业界迅速发展的同时，学术界也对p 2 p 技术迅速展开了研究工作。 自2 0 0 0 年起，在s i g c o m m 、i n f o c o m 、o s d i 、s o s p 、u s e n i x 和h o t o s 等系统 结构方向的国际顶级学术会议上不断出现关于p 2 p 技术的重要研究成果。f 1 2 0 0 1 年 起，学术界又召开了新的专门针对p 2 p 系统的学术会议i 盯p s ，由于该会议受到各著 名院校和研究机构的广泛关注，很快成为p 2 p 技术研究领域的高峰会议，已经成为影 响p 2 p 技术研究方向的风向标。从2 0 0 2 年开始，b e r k e l e y 、s t a n f o r d 、c m u 等著名大 学相继开设了与p 2 p 技术相关的研究生课程，进一步推广了这一新兴的研究方向。 p 2 p 技术揭开了i n t e r a c t 发展的新时代的序幕，是通过全世界i n t e m e t 参与者协作 构建智能化、个性化的i n t e m e t 的开端。所以，研究p 2 p 技术、构造p 2 p 应用、以及提 升p 2 p 系统的性能，已经成为网络技术研究的一个重要课题。 1 1 1 对等网络技术起源 近年来，p 2 p 应用作为新型的大规模分布式应用迅速发展起来，并很快取代w e b 成为i n t e m e t 上占用带宽最多的应用系统。p 2 p 技术的诞生与发展来源于两个重要因 素：计算机处理能力提高导致了计算模式的演变；网络技术发展引发了新的网络应 用。 ( 1 ) 计算机处理能力提高导致计算模式的演变，是p 2 p 技术诞生的根本原因。 1 上海交通大学博士学位论文 电子技术的发展带来了计算机处理能力的长足进步。m o o r e 定律指出：微处理器 计算能力每1 2 一1 8 个月提高l 倍，标示着计算机处理能力提高的规律。计算机处理能 力提高带来了计算机计算模式的演变。计算模式的演变经历了三个阶段： 1 主从模式 主从计算模式的特点为计算能力全部集中在主机，数据的处理完全由主机进 行，主机的计算能力由多客户分时复用；客户端仅用于输入和显示，完全没有计算 能力。主从计算模式反映了上世纪5 0 7 0 年代的计算机发展的客观特点：计算机价 格昂贵，计算能力是稀缺资源。 2 服务器，客户机模式 服务器，客户机( s e r v e r c l i e n t ，c s ) 计算模式的基本工作方式是客户机发出服 务请求，服务器接收到请求后进行分析处理，然后将处理结果返回给客户机。在该 模式中客户机具备一定的计算能力，可以进行数据处理的预加工以及处理结果的后 处理，但主要的数据处理工作由服务器来完成。服务器客户机计算模式发展于上世 纪7 0 一8 0 年代，并于上世纪9 0 年代开始流行。目前，这种计算模式已成为主流计算 模式，并演变成为客户机文件服务器、两层c s 、多层c s 及浏览器服务器( b s ) 等多种类别。该计算模式反映了随着微型计算机计算能力的提高，用户的数据处理 任务开始在不同的计算机上分布进行 3 对等计算模式 随着个人电脑的计算能力越来越强，如何更好地利用所有结点的计算能力搭建 分布式系统，自然而然地成为研究者们关注的问题。对等计算的核心思想是，所有 参与系统的结点( 指互联网上的某个计算机) 处于完全对等的地位，没有客户机和 服务器之分，也可以说每个结点既是客户机，也是服务器；既向别人提供服务，也 享受来自别人的服务。对等计算模式正成为业界持续关注与探讨的话题。 ( 2 ) 计算机网络带宽和速度的提高，是对等网络技术发展的直接原因。 通信技术的发展带来了计算机网络带宽和速度的提高。g i l d e r 定律指出：网络的 带宽每1 2 个月提高i 倍；网络带宽的提高使得构建跨i n t e r a c t 的分布式系统成为了可 能。同时，m e t c a l f e 定律指出：网络价值的增长是网络用户数增长的二次函数。随 着更多的用户参与至l j i n t e m e t 中，原先单源的数据和服务在整个i n t e m e t 上呈现了多副 本、多提供点的趋势。如何更好地利用现代网络条件，发挥网络用户的潜在价值， 一2 一 第一章序论 寻找目的数据或服务的最佳副本，就自然而然地成为现阶段学术界和企业界关注的 热点问题。这正是对等网络技术发展的直接原因。 事实上，p 2 p 技术作为新的计算模式和新的网络应用，反映着人类社会的组织形 式：人人贡献出自己的资源、人人享受他人提供的资源；是人类集体行为在现阶段 技术条件下，在信息技术领域的自然折射，必将长期存在，并随着计算机处理能力 和网络能力的进一步提高而演化、发展。 1 1 2 对等网络定义及特点 到目前为止，业界对于“p 2 p 技术”还未形成统一的权威定义，但近年来已有很 多研究者对p 2 p 技术的基本内涵进行了概括： ( 1 ) 一类利用位于i n t e r n 鲥直缘的资源( 包括存储、计算周期、内容、人) 的应用 【2 】。该定义是在2 0 0 0 年的o p p 2 p 组织年会上提出的，是p 2 p 系统最早的定义。该定 义指出了p 2 p 技术的目的是利用位于网络边缘的用户端资源。 ( 2 ) 在分布式方式下，利用分散资源开展重要任务的应用或系统【3 】。该定义 是由l i p 研究院提出的，说明了工业界对p 2 p 系统功能的设想。 ( 3 ) 分散的、自组织的分式布系统，系统中的主要通信是对称的【4 】该定义 是由有“网格之父”之称的美国a l g o n e 国家实验室的l a n f o s t e r 教授提出的。该定义 从体系结构的角度概括了对等网络的特征，反映了对等网络作为一种新的分布式应 用的主要特点。 ( 4 ) 所有参与系统的结点( 指i n t e m e t 上的计算机) 处于完全对等的地位，没 有客户机和服务器之分，也可以说每个结点既是客户机，也是服务器；既向别人提 供服务，也享受来自别人的服务 5 】。该定义是由清华大学郑纬民教授的研究组提 出的，描述了p 2 p 系统基本构成单元一一结点的特性，也是对p 2 p 基本组织形式的概 括。 虽然，上述p 2 p 技术的定义表述各异，但是从中可以总结出p 2 p 技术的主要特 点，也是p 2 p 系统区别于传统分布式系统的重要特点和问题： ( 1 ) 结点数量大。由于很多p 2 p 系统已经达到上百万结点同时在线的规模，因 此全连接的拓扑结构( 就是让每个结点记录当前所有其它结点) 是完全不可行的。如何 构造p 2 p 覆盖网，并实现相应的覆盖网路由机制是p 2 p 技术研究的关键问题。 ( 2 ) 结点位于网络边缘。该特点要求作为p 2 p 系统组成单元的结点之间通信 时，其通信消息的传递依赖于i n t e m e t 的通信子网0 p 网络) 。但是，结点之间的逻辑 一1 一 上海交通大学博士学位论文 关系由应用层覆盖网维护。于是，p 2 p 覆盖网上的路由机制，必然需要有不同于网络 路由机制的组织形式 ( 3 ) 结点动态性强。参与结点完全由用户控制，可以自由地加入和退出对等网 络，即对等网络完全由动态的结点构成，这样p 2 p 覆盖网存在着大量的扰动现象。覆 盖网的扰动性一方面带来了p 2 p 系统中数据可用性比较低：另一方面使得p 2 p 覆盖网 抗扰动设计成为路由机制研究的重要问题。 ( 4 ) 结点异构性强。i n t e r a c t 中结点在硬件能力和接入方式等方面通常具有不同 性能。同样，参与对等网络的结点在存储能力、计算能力和带宽能力上存在着巨大 差异，如何将p 2 p 系统中异构结点的所有可用资源都利用起来以提高对等网络的性 能，是p 2 p 技术研究的重要问题。 ( 5 ) p 2 p 覆盖网的组织协议是分布式的，自组织的。首先，对等网络的大规模 性使得集中控制方案实现开销大同时，结点的动态性、异构性使得集中控制方案 实现难度高。并且，结点分布广泛且位于i n t e r n c t 边缘，决定了结点之问只能采用异 步通信。因此，只有分布式、自组织的覆盖网协议才能适用于对等网络。 ( 6 ) 结点之间的信任度低。p 2 p 结点来自于不同的组织和用户，使得结点的隐 私保密工作和p 2 p 覆盖网组织的安全策略成为重要问题。如何在与别的结点交换数据 时保护好自己的隐私，以及如何构建安全的p 2 p 覆盖网，就成为p 2 p 技术研究的重要 方向。 ( 7 ) 结点具有自私性。对等网络用户总是倾向于试图多使用别人的资源，少贡 献自己的资源。p 2 p 系统跟踪实验结果显示，在g - n u t c l l a 系统中有2 5 的结点从不共 享数据给别人，只从别人那里下载数据【6 】。如何激励用户多贡献自己的资源，并 且保证交换中的公平性也是受到很多研究者关注的热点方向之一同时，结合特点 ( 6 ) 和特点( 7 ) ，如何评定和传播对等网络参与者的信用等级也成为对等网络目 前研究的热点问题。 总结上述对等网络的7 个特点，可以看出特点( 1 ) 和特点( 5 ) 描述了对等网络 结点之间的组成关系或体系结构的特性；特点( 2 ) 一( 4 ) 反映了对等网络基本组 成单元一一结点本身的特性；特点( 6 ) 和( 7 ) 说明了在部署对等网络时，涉及到 的安全策略问题。p 2 p 技术的这些新特点使得p 2 系统自出现起就表现出与传统的分布 式系统的巨大差别。这也是p 2 p 技术能够迅速成为学术界和工业界的研究热点问题的 重要原因。 一4 一 第一章序论 1 1 3 对等网络技术与网格技术的比较 网格计算( g r i dc o m p u t i n g ) 是近年来分布式计算的另一个重要方向，并且网格 技术的主要目的和对等计算具有很大的相似性，都是利用地理上分布的动态的资源 完成一定的任务。但对照对等网络的定义和7 个主要特点可以发现，网格技术与对等 技术具有不同的内涵和特点。 关于网格计算至今也还没有公认定义网格刨始人l a nf o s t e r , j 网格进行了这样 的定义【7 】：网格是一个集成的计算资源环境，也被称为计算资源池。网格能够充 分吸纳各种资源，并将它们转化成一种随处可得的、可靠的、标准的、经济的计算 能力除了各种类型的计算机，这里的计算资源还包括网络通信能力、数据资料、 仪器设备等资源。随后，i a nf o s t e r 进- - 步指出，网格计算关心的是：在动态的、多 机构的虚拟组织中的资源共享和协同解决问题【8 1 。i a nr o s t e r 提；r l 了判断网格三条标 准：非集中式协同控制资源；使用标准、开放、通用的接口和协议；提供非平凡的 服务质量。【9 】 ( 1 ) 将网格技术和对等技术进行对比，可以看出二者的相同点在于： 二者的目的都是，利用具有通信能力的计算机及其他设备，进行跨网络的资源 整合。 二者的参与结点都具有地理上的分布性、控制上的自治性、行为上的动态性和 结点的自私性等特点。 ( 2 ) 二者的不同在于： 组织结构网格计算要组建的虚拟组织，其参与结点的组织关系是相对固定的；而对 等网络结点的组织关系是不固定的。所以，网格计算通常通过目录服务器来组 织结点；而对等网络通过分布式方式组织结点。进而，网格计算在任务分配、 作业调度和资源监测，分配等关键支撑技术上仍采取较多的集中控制：对等技术 则基本不使用集中控制。 服务提供者网格技术比对等网络技术更注重开放标准特性，说明了网格服务的构建 者主要为业界的服务商，不同服务商之间的交互和协同是提供网格服务的关 键；而对等网络的主要构建者和消费者部是i n t e m e t 上使用同一种p 2 p 软件的用 户群，目前尚不存在不同用户群之间的交互和协同问题。 一s 一 上海交通大学博士学位论文 服务质量和安全性网格技术比对等网络技术更注重服务质量和安全性的特点，说明 网格服务的应用面侧重于解决某些专业领域诸如大规模计算、存储等的关键问 题：而p 2 p 应用通常是为i n t e r n e l e 的普通用户群提供便利的网络工具。 通过比较可以看出，网格技术和对等网络技术虽然存在一些相同的特性，但其 面向的领域却是不同的。网格是由业界服务商和研究院所的高性能资源构成的虚拟 组织。其目的是，通过资源协同解决专业领域的关键问题。业界服务商可以通过网 格收取服务费，科研院所可以通过网格交互高性能资源。对等网络是由因特网上的 一般用户群通过使用同样的p 2 p 软件构建的网络平台。其目的是，为一般用户提供特 定服务中国教育科研网内的两个新的分布式应用正说明了这一点：“中国教育科 研网格( c h i n a g r i d ) ”项目是通过连通中国各高校的高性能资源，为全国科学研究 提供计算、存储等高性能服务 1 0 。而北京大学开发的基于p 2 p 技术的文件共享系统 “m a z e ”，虽然同时在线用户已经有数万，但是其目的是方便一般网络用户进行文 件的共享和获取【1 1 】。又如，“上海网格( s h a n g h a i g - r i d ) ”项目协同了上海市的主 要高性能计算资源，以实现智能交通信息服务为目的 1 2 】。 近年来，网格技术和对等网络技术也表现出了相互借鉴的趋势，比如网格计算 在服务发现方面也可以采用p 2 p 覆盖网进行分布式组织，又如在进行流媒体广播的 时候，流媒体源结点及广播覆盖网中的某些关键服务结点也可能先构成网格，再参 与p 2 p 覆盖网。 1 1 4 对等网络应用简介 近年来，随着p 2 p 技术研究的深入和业界的实践，越来越多的f 2 p 应用系统正在 走向成熟。与此同时，对等网络的研究者也正在努力构造新型的p 2 p 应用，以体现和 发挥p 2 p 架构的优越性。目前，对等网络主要应用领域包括： ( 1 ) 信息资源共享 信息资源共享一直是网络技术发展的重要推动力，也是目前p 2 p 技术最典型的应 用。在p 2 p 技术之前，信息共享及文件交换主要通过w e b 技术实现，属于c s 计算模 式。但是网络服务器( w e bs e r v e r ) 由于直接面向大量用户的访问请求，经常成为此类 共享系统的性能瓶颈，甚至引发单点故障。这正是c s 计算模式的主要缺点。为了提 高网络服务器向用户客户端提供服务的性能，分布式网络服务器应运而生。分布式 网络服务器采取了在服务器端使用多台网络服务器提供服务的构架，通过服务器端 ，6 第一章序论 内部的路由机制和请求分发算法来为远端用户提供服务【1 3 。但是该方案对服务器 端要求的成本高，并且仍不能完全解决单点故障问题。 1 9 9 9 年诞生的文件共享系辅a p s t e r ，通过p 2 p 技术成功解决了w e bs e r v e r 的瓶 颈问题【1 4 n a p s t e r 是最早的p 2 p 实用系统，系统参与者是大量个人计算机用户， 每个用户将自己愿意共享的文件提供出来，同时可以下载其他用户共享的文 件n a p s t e r 虽然仍采用目录服务器提供文件索引服务，但文件存储和下载服务 在n a p s t e r 用户之间进行，因此它支持上万结点同时在线。n a p s t e r 在发布后迅速流 行起来，很快成为增长最快的网络应用系统【l s 。c , n u t e l l a 进- - 步将n a p s t e r h 录服 务器提供的文件索引功能分布到所有参与结点中【1 6 】。通过由所有参与结点构造 的g n u t e l l a 覆盖网来进行文件检索，从而进一步提高了系统鲁棒性和可扩展性。 k a z a a 采取了层次结构【1 7 。k a z a a 将系统中的结点分成两种：强结点和弱 结点会话时间长的结点为强结点；反之，为弱结点。强结点之间构造类似 于c m u t e l l a 的覆盖网，而弱结点只连接到一个或几个强结点，并把自己的元数据( 即 共享文件的列表) 发送给强结点，文件搜索只在强结点上进行。这样，k a z a a 获得 了比g n u t e l l a 更高的稳定性和搜索效率。当前，k a z a a 的同时在线用户稳定在三百 万以上，已成为全球最大的分布式文件共享系统。 b i t t o r r e n t 试图充分利用下载用户之间的带宽进行数据传输，从而减轻服务器负 担，提高下载速度和系统的可扩展性( 指同时下载人数) 。b i t t o r r e n t 的基本策略 是：每个用户只从服务器下载一部分数据，各个用户下载的部分不尽相同。同时， 用户之间互相交换对方没有的数据，最终使所有用户都获得全部数据。b i t t o r r e n t 在推出之后迅速流行，由于越来越多的人使用b i t t o r r e n t 进行数据下载，很快使 得b i t t o r r e n t 系统成为占据5 0 以上网络流量的i n t e m e t 首要应用【1 8 ，1 9 。e m u l e 的 文件传输策略与b i t t o r r e n t 大致相同，但e m u l e 进一步将b i t t o r r e n t 中集中控制的文件 索引信息分布到地域分散的e m u l e j 艮务器组，并且e m u l e 服务器还协助用户结点进 行n a = r 穿越和防火墙穿越等工作【2 0 。 北京大学开发的m a z e 文件共享系统在结构上类似于n a p s t e r 【1l 】，搜索策略类 似于c m u t e l l a 【2 1 。目前，m a z e 系统的同时在线用户已经达到了三万以上。基于对 等网络的分布式文件共享系统还有f r e e n e t 2 2 、z o o k o 2 3 1 、f r e eh a v e n 2 4 】、o h a h a 2 5 】等。这些研究项目均从不同的角度尝试解决如何充分利用网络中的带宽资源，提 高p 2 p 系统的文件检索及数据传输的效率的问题。 一，一 上海交通大学博士学位论文 ( 2 ) 实时通信技术 实时通信技术是网络中重要的通信技术，成功的实时通信技术吸引了数 以万计的在线用户。目前的实时通信技术一般采用一个中心服务器控制用 户的基本信息，如用户的认证和好友列表等信息；结点之间直接进行数据通 信。i c q 、o l c q 、a i m 及m s n 等正是典型的实时通信系统。j a b b e r 2 6 】是一个开放 源码的实时通信平台，j a b b e r 提出了一个采用x m l 表示的，可以在不兼容的各种 实时通信平台之间进行消息交换的协议。s k y p e 是目前最流行的语音实时通信系 统【2 7 。s l o y p e 的系统结构基本上类似于k a z a a ，当用户之问需要进行语音通信 时，s k y p e 在覆盖网中找寻出一条当前带宽最大的覆盖网通路，通过多跳转发的 方式进行数据传送。由于s k y p e 的出现和高速发展，越来越多的用户转向网络电 话，已经对传统的电信业构成了一定的威胁。截至2 0 0 5 年2 月，s k y p e 的注册用户已 趔2 1 0 0 万，同时在线用户数超过2 0 0 万。 ( 3 ) 应用层组播系统 虽然i p 层组播技术提出已经有十年之久，但由于它需要改变路由器算法，且需 要记录组状态( 组内成员地址) ，因此难以在现有网络上被广泛部署。鉴于这一 点，研究者们提出不需要i p 层支持的应用层组播，也就是在需要收到消息的结点之 间不断转发消息，保证消息最终能够被该组的所有成员收到 2 8 】。应用层组播的主 要研究内容为：在结点之间通过构造树状或网状p 2 p 覆盖网进行组播，并且覆盖网必 须能够处理由于结点加入，退出带来的扰动问题；优化覆盖网结构，与下层i n t e m e t 物 理网络结构相匹配，以提高组播效率，降低组播通信对i n t e r n e t 链路产生的压力 2 ”4 】。l o n g 3 5 】量化评估了网络拥塞对p 2 p 应用层组播性能的影响，其研究成果 进而可以指导设计应用层组播的拥塞控制协议。 视频组播系统可以视为应用层组播的特例，基于p 2 p 覆盖网的视频组播主要是 解决组播服务器的带宽问题。视频组播的带宽要求很高，因此传统基于c s 结构 的视频组播系统往往由于服务器出口带宽的限制而导致系统的可扩展性差。在基 于p 2 p 技术的视频组播系统中，只有少数结点从服务器直接获取数据，更多的结点 一方面从其它结点处获得数据，一方面也向其它结点提供数据。整个系统的体系 结构为树状结构或者网状结构。这种以p 2 p 方式构建的视频组播系统充分利用了结 点之间的可用带宽，使得系统的可扩展性大为提高 3 6 - 3 8 1 。华中科技大学开发的 视频直播系统a n y s e e 采用了p 2 p 技术【3 9 - 4 1 。在2 0 0 4 年奥运会期间向教育网进行 一8 一 第一章序论 了2 0 2 4 j , 时的直播服务，共有l o 万人次使用。2 0 0 4 年1 1 月11 日，武汉市电子政务 网络试用a n y s e e 系统，分布于武汉三镇的8 9 6 个社区使用a n y s e e 收看政务节目，试 用效果良好。基于p 2 p 技术的视频组播系统还有c o o l s t r e a m 【4 3 】和p p l i v e 【4 4 】等。 ( 4 ) 广域网分布式存储系统 分布式存储系统一直是分布式系统的一个重要应用领域，传统的局域网范围 内的分布式文件系统、分布式对象存储系统、分布式数据库系统都有着良好的研 究基础。p 2 p 技术出现后，研究者们开始尝试把这些分布式存储系统向更大范围 拓展，提出了在广域网中构建基于p 2 p 技术的分布式文件系统 4 5 ，4 6 ，对象存储 系统 4 7 ，4 8 和数据库系统 4 9 ，5 0 l 。清华大学开发了基于p 2 p 技术的分布式存储系 统g r a