（计算机应用技术专业论文）基于chord的p2p网络的负载平衡的研究.pdf

摹于c h o r d 的p 2 p 网络的负载甲衡的研究 摘要 第三代p 2 p 系统大多数都提供了一种d h t 算法，它将网络中的资源随 机地分布在参与网络的各个节点上。在某种情况下，某些节点分配到的资 源是平均水平的o ( 1 0 9 n ) 倍。而且，在标识符空间内节点的不均匀分布， 加上每个节点的负载和处理能力不同所形成的异构性，都是网络的不平衡 度加剧。再者，节点的负载还会随着时间的变化而变化，因为p 2 p 系统中 各个节点是相互独立的，期间会有频繁的资源插入、删除、各种各样的资 源加入模式及随机的相关节点加入和离开。 本文提出了一种在异构的p 2 p 系统中负载平衡的新模型。这种模型是 基于现在最流行的c h o r d 协议。模型在底层使用c h o r d 的d h t 算法来分 配资源，并根据节点处理能力将系统进行层次化划分，使得能力较强的节 点承担更多的责任。 理论分析和实验仿真结果表明，我们的系统比较好的利用了网络的异 构性，从而在负载平衡方面达到了较理想的性能。另外，由于系统的分层 结构，带来另一个优势，本负载平衡的新模型使系统的查询时问复杂度在 原来的o ( 1 0 9 n ) 的水平上降到常数级的水平。 关键词：d h t ，异构性，标识符，负载 中图分类号： 基于c h o r d 的p 2 p 网络的负载p 衡的研究 a b s t r a c t m o s tp 2 ps y s t e m st h a tp r o v i d ead h ta b s t r a c t i o nd is t r i b u t eo b j e c t s r a n d o m l ya m o n g “p e e rn o d e s ”i naw a yt h a tr e s u l t si ns o m en o d e s h a v i n g0 ( 1 0 9 n ) t i m e sa sm a n yo b j e c t sa st h ea v e r a g en o d e f u r t h e r i m b a l a n t em a yr e s u l td u et on o n u n i f o r md i s t r i b u t i o no fo b j e c t si n t h ei d e n t i f i e rs p a c ea n dah i g hd e g r e eo fh e t e r o g e n e i t yi no b j e c t l o a d sa n dn o d ec a p a c i t i e s a d d i t i o n a l l y an o d e s1 0 a dm a y v a r y g r e a t l yo v e rt i m es i n c et h ep 2 ps y s t e mc a nb ee x p e c t e dt oe x p e r i e n c e c o n t i n u o u si n s e r t i o n sa n dd e l e t i o n so fo b j e c t s ，s k e w e do b j e c t a r r i v a lp a t t e r n s ，a n dc o n t i n u o u sa r r i v a la n dd e p a r t u r eo fn o d e s i nt h i sp a p e r ，w ep r o p o s ean e wm o d e lf o rl o a db a l a n c ei n h e t e r o g e n e o u sp 2 ps y s t e m t h i sm o d e li s b a s e do nt h em o s tp o p u l a r c h o r dp r o t o c 0 1 u n d e r l y i n gt h em o d e l ，w eu s et h ed h ta l g o r i t h mi n c h o r dt od i s t r i b u t er e s o u r c e s ，a n dc a t e g o r i z ea 1 1t h en o d e sint h e s y s t e ma c c o r d i n gt ot h ep r o c e s s i n gc a p a b i l i t y a sar e s u l t ，t h em o r e p o w e r f u ln o d et a k e sm o r er e s p o n s i b i l i t y t h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a ls i m u l a t i o nr e s u l ts h o w s t h a t d u et ot h eb e t t e ru t i l i z a t i o no ft h eh e t e r o g e n e i t yo ft h e n e t w o r k ，o u rs y s t e mp r o v e sav e r yg o o dp e r f o r m a n c ei nl o a db a la n c e b e s i d e s ，a sw ec a t e g o r i z e t h es y s t e m ，w eg e ta n o t h e ra d v a n t a g e ， w h ic hist h el o o k u pe f f i c i e n c yi sr a i s e df r o m0 ( 1 0 9 n ) i nf o r m e r s y s t e mt oac o n s t a n t1 e v e l k e y w o r d ：d h t ，h e t e r o g e n e i t y ，i d e n t i f i c a t i o n ，l o a d i l 基于c h o r d 的p 2 p 网络的负载平衡的研究 引言 信息时代，技术发展日新月异。计算机网络技术也取得了飞速的进步， 其中新兴的p 2 p ( 对等) 网络技术，便是技术创新的产物。p 2 p 网络的发 展，从最初的共享音乐信息的n a p s t e r ，到“被人称奇的软件产品” g n u t e i l a ，再到现在的基于d i s t r i b u t e dh a s ht a b l e ( d h t ) 的c h o r d ， p a s t r y ，c a n 等等，其可扩展性和稳定性不断地提高，同时网络的对等、 自治程度也越来越高。 在过去的几年中，d h t 发展成了一种灵活和普遍的体系结构( 以c h o r d ， p a s t r y 等网络为代表) 。这种体系结构可以支持许多的应用，包括文件共 享 1 ， 2 3 ，存储系统 3 ，查询处理 4 ，命名服务 5 ，和通讯服务 6 ， 7 3 ， 8 。在d h t 体系结构中，要查找个给定i d 所在的节点，通常所 需要的时间复杂度为0 ( 1 0 9 仃) ，即节点之间的通信量，空间复杂度也为 0 ( 1 0 9 n ) ，即每个节点需要维护的路由表的大小。 d h t 的设计带来了另一个问题，那就是如何平衡整个d h t 网络中节 点的负载。即使不考虑网络中各个节点的异构和多样性，假设网络中所有 的节点都具有相同的能力，d h t 网络还是会表现出以0 ( 1 0 9 而为系数的不 平衡性。 9 这种不平衡性会随着网络的异构性和节点数量的增加而明显 地增加。表现出来是网络中各个节点不能很好地参与网络各种活动，影响 了整个网络的性能。 到目前为止，解决d h t 网络节点负载不平衡的方法基本上都町以归 为两类：第一类为标识符空问平衡法；第二类为数据项空间平衡法。 标识符空间平衡的方法的基本思想是：对于网络中各个节点负责的 标识符进行调整，已达到平衡负载的效果。 基于c h o r d 网络的虚拟节点技术便是属于第一类方法，它能在一定 程度上使整个网络中各个节点的负载量达到平衡，代价是节点需要存储更 多的信息和网络通信量大大增加。 数据项空间平衡的方法的基本思想是可以在网络中的节点直接来移 动负载，即资源可以选择性地存储在某个节点上，其代价是移动资源带来 的开销，而且这种方法给网络安全带来了一定的隐患。 上述两类方法都没有考虑真实的网络系统中节点的异构性和能力的 苎q ! 璺竺丝! 堕竺塑垒垡! 塑竺竺壅 不同。对目前世界范围内部署的p 2 p 系统测量之后，发现系统成员之l 日j 能 力和参与活动的程度，有着非常明显的异构性。 1 0 ， 1 1 ， 1 2 ， 1 3 本文将利用网络节点的异构性，在c h o r d 的基础上，提出一个新的 网络模型，能有效地平衡p 2 p 系统中各个节点的负载。 2 基于c h o r d 的p 2 p 网络的负载甲衡的研究 第1 章p 2 p 概述 1 1p 2 p 网络的发展历史 p 2 p 是英文p e e r - t o - p e e r 的缩写，p e e r 在英语里有“同等者”、 “同事”和“伙伴”等意义。p 2 p 可以理解为“伙伴对伙伴”的意思， 或称为对等互联。国内的媒体一般将p 2 p 翻译成“端对端”或者“点 对点”。p 2 p 是一种技术，但更多的是一种思想，它有着改变整个互 联网基础的潜能。它的核心思想是：上网用户之间自由的、不受主服 务器控制的信息交流。 p 2 p 并不是什么新概念，p 2 p 是互联网整体架构的基础。互联网最 基本的协议t c p i p 并没有客户机和服务器的概念，所有的设备都是通 讯的平等的一端。在十年之前，所有的互联网上的系统都同时具有服 务器和客户机的功能。当然，后来发展的那些架构在t c p i p 之上的软 件的确采用了客户机月艮务器的结构：浏览器和w e b 服务器，邮件客户 端和邮件服务器。但是，对于服务器来 兑，它们之b j 仍然是对等联网 的。以e - m a i l 为例，互联网上并没有一个巨大的、唯一的邮件服务器 来处理所有的e - m a i l ，而是对等联网的邮件服务器相互协作把e - m a i l 传送到相应的服务器上去。另外，用户之间e - m a i l 则一直是对等的联 络渠道。 简而言之，p 2 p 技术就是在个人电脑之间直接进行资源和服务的共 享，而不像传统的b r o w s e r s e r v e r 或者c l i e n t s e r v e r 结构那样需要 经过服务器的介入4 * 1 8 e 务。在p 2 p 结构中，每台个人电脑同时充当服 务器和客户端的角色，当需要其他电脑的文件或者服务时，两台电脑 直接建立联系，本机是客户端，而当响应其他电脑的资源要求时，本 机又成为提供资源与服务的服务器。通常这些资源和服务包括：文件 的共享与交换，计算资源如c p u 的共享使用等。p 2 p 的实质就是把控 制权重新还到用户手中去。人们通过p 2 p 可以共享硬盘上的文件、目 录甚至整个硬盘。这种能量是非常令人激动的，那些费心存储在自己 的硬盘上的东西肯定是我们认为最有价值的东西，所有人都共享了他 们认为最有价值的东西，这将使互联网上信息的价值得到极大的提升。 p 2 p 技术第一次让个人计算机和高贵的服务器平起平坐，让p c 焕 基于c h o r d 的p 2 p 嘲络的负载，f 衡的研究 发了新的活力。当人们加入p 2 p 网络的时候，所有人都拥有了平等的 机会，所有人都拥有了极容易地在网络上创造“内容”的机会。有一 天，你忽然发现你不再需要到别人的网站申请免费主页空i 、日j 和e m a i l ， 你可以在自己的计算机上实现这些服务。无论走到哪里，你都可以使 用上网设备( 例如w a p 手机) 读取办公室或家里的计算机上的文件。 凡此种种，p 2 p 改变了互联网的游戏规则，也改变了我们的生活。 从2 0 0 0 年开始，真正的p 2 p 应用得到了飞速地发展，到目前为止 已经经历了三次更新换代。 1 1 1 第一代p 2 p 网络 第一代p 2 p 以n a p s t e r 为代表。它是一个能够在网上进行音乐 文件共享的p 2 p 程序。n a p s t e r 上所有的共享m p 3 文件都是由用户 提供的，种类繁多，而且所有的文件都保存在用户的计算机上。 n a p s t e r 提供了一个中央服务器，来保存所有用户提供的m p 3 文件 的目录以及其计算机的地址，当某个用户需要下载m p 3 文件时，他 通过服务器查询到所需要的m p 3 文件所在的计算机地址的列袁，然 后选择列表中任意一台计算机，直接与其建立连接，就可以下载 m p 3 文件了。 注册 圜 1 服务器 r | ( 用户、文件) “a 有x m p 3 ” 、。哪里有x m p 3 7 ” 下载x m p 3 图1 1 ：n a p s t e r 交互模式 r i 【，一 1 1 2 第二代p 2 p 网络 g n u t e l l a 可以说是第二代p 2 p 网络中最成功的一个应用。用户 4 幕于c h o r d 的p 2 p 瑚络的负载平衡的研究 通过客户端软件把自己的账号和计算机地址登记到服务器上，并通 过服务器查找其他在线的用户账号和地址，然后直接进行聊天，也 可以共享文件。 g n u t e l l a 是一个分布式的文件共享系统，其参与者都是通过 g n u t e l l a 协议 2 9 来形成一个可以互相通信的虚拟网络。 g n u t e l l a 协议其实是一个简单的分布式文件查询的协议。节点加 入网络i j i 需要先连接到一个已知的g n u t e l l a 主机上。协议包含了 5 种基本的消息类型。如表1 1 所示： 消息类型描述包含的信息 p i n g声明可用性以及探 无 测其他服务节点 p o n gp i n g 的回应回应节点的i p 地址 和端口号：共享文件 的数量和总的k b 数 q u e r y查询请求回应节点的最小网 络带宽；查询准则 q u e r y h it含有请求文件的服回应节点的i p 地址， 务节点的回应端口号和网络带宽； 查询结果的数量和 查询结果集 p u s h向处在防火墙后面 服务节点的标识；请 的服务节点发送的求文件的索引；发送 文件下载请求文件的i p 地址和端 口号 表1 1 ：g n u t e l l a 的消息类型 g n u t e i l a 协议中的消息路由都是基于一种受限的广播机制：广 播信息有超时设置。 一个简单的6 n u t e l l a 会话是这样工作的：主机a 连接到主机b ， 并向它发送一个p i n g 消息。b 回应一个p o n g 消息，并且向其他主 5 基于c h o r d 的p 2 p 刚络的负载平衡的研究 机转发。一段时间之后，a 知道了一些主机，反之亦然。其过程如 图1 2 所示： 图1 2 ：g n u t e l l a ：节点相识 然后节点可以按照表1 所示的格式发送查询请求。当接收到 q u e r y t t i t 的消息后，它就尝试连接回应消息的主机，并且通过简 单的h t t pg e t 来检索文件。如果主机在防火墙后面，它可以发送 一个p u s h 消息，这样主机就可以运行一个“被动式”的g e t 会话。 如图1 3 所示： 摹于c h o r d 的p 2 p 网络的负载平衡的研究 回 图1 3 ：g n u t e l l a 中的搜索 1 1 3 第三代p 2 p 网络 随着分布式散列表( i ) h t ) 技术的不断发展和完善，以此为基 础的第三代p 2 p 网络得到了广泛地发展和应用。其中以c h o r d 、 p a s t r y 、t a p e s t r y 和c a n 等网络为代表。使用d h t 技术，可以很 好地提高网络中的查询效率，进而增加了网络的可扩展性。 1 2p 2 p 网络的价值 p 2 p 在为个人产品、娱乐应用程序和公司级的商业应用程序提供了 新机会的同时，还解决了实际中的商业和个人问题。p 2 p 的价值体现 在以下方面： 1 2 1 提供重要的信息和服务 “信息”是一个普通词，在数字世界中它却包括许多内容，如 图片、音乐、录像、文档，等等。它还代表生日贺卡的交流、体育 节目的日程变化以及股票价格的通知。服务所提供的信息处理包括 显示图片、播放歌曲和发送电子邮件等等。信息除了代表商业数据 外，还代表其它东西。它引导、通知并促使人们做出决定。越来越 多的数字信息在代替传统的介质。绝大部分的数字信息都不在大型 7 基于c h o r d 的p 2 p 网络的负载甲衡的研究 公司级服务器上。 用户想要与之交流的人也不是坐在大型公司级服务器的后面。 信息和通信的大部分都存在于个人计算机上，也就是i n t e r n e t 对 等设各上。p 2 p 的目标就是使用户获得信息并联系到最关心的人。 该目标定义了p 2 p 的巨大潜质。 1 2 2 促使成本最小化 价值的另一个决定性的关键部分是成本。个人计算机的计算平 台包括大部分的已支付成本。p 2 p 的原材料，即处理能力、存储空 间等等己经购得。这样p 2 p 就可以在前人栽的树下乘凉了，而且网 络成本为零。但是这并不是成本计算的终点。下一步是信息和通信 工具。而这些工具已经存在于大多数计算机上了，或者能够以极少 的成来获得，通常只要简单地下载就可以了。因此，用于生产有用 信息、服务和通信的原材料的成本实际上己经支付了。 下面将p 2 p 成本与传统w e b 站点做一下比较。w e b 站点成本包 括连接成本、软件成本、操作系统维护和提供宿主服务的硬件。传 统的w e b 站点是一种新的资源，一种必须支付成本的资源。w e b 站 点还需要将信息转移到另一个平台上，并在该平台上重新创建服 务。这些服务既耗时又复杂。提供服务重建，而不止是提供静态信 息的站点，成本更高。提供i n t e r n e t 服务打包的站点如a m e r i c a o n l i t 3 e 不允许任何用户方安装的服务，而且只提供有限的存储空 间。 t 2 3 赋予用户控制权 控制有用信息也是一个重要因素。当用户的信息和服务能够被 其它用户使用时，用户要对这些信息和服务进行控制。用户不仅要 能够容易地更新和改变提供给别人的信息，还要及时地了解到更新 的版本何时可用。如果一种技术所提供的控制越少，那么它的价值 就越低。 p 2 p 为用户提供了完全的控制权。信息存在于用户的个人计算 机上，这要比将信任的信息放在w e b 站点的服务器上所获得的控制 基十c h o r d 的p 2 p 嗣络的负载甲衡的研究 权要大。一旦用户将信息移动到服务器上。这些信息就处在了他人 的控制之下。w e b 站点可以许诺并建立“隐私保护政策”，但是事 实是，仍有其他人控制着用户的信息以及关于这些信息所搜集的数 据。例如访问这些信息的其它用户和时间。 1 2 4 多样性的服务 多样性也是一个关键问题。在p 2 p 世界中，用户可以使任何信 息或服务可用。w e b 站点是非常有限的，除非用户进入w e b 站点的 内部工作组中。w e b 站点经常限制为只处理h t m l 格式的信息，并 且不允许提供完整的服务。p 2 p 则可以自由地使用任意类型的交互 格式和协议。这种自由可以迅速地产生创新浪潮。 1 2 5 虚拟的普适访问能力 访问能力也是价值的一个关键方面。i n t e r n e t 及其相关技术正 变得越来越容易访问。网络本身的价格也日趋台理，并且可以通过 多种代理进行访问，范围从卫星到简单的电话调制解调器。具备多 个访问点对于用户保持连接是十分关键的，因为当这些连接点中的 一个或多个无法工作时，还有其它访问点可供使用。w e b 站点的服 务器如果出了问题，整个网络就瘫痪了，而p 2 p 恰好提供了简单的 方法来解决这类问题。 1 3p 2 p 网络的应用 p 2 p 给互联网的分布、共享精神带来了无限的遐想，有观点认为至 少有1 0 0 种应用能被开发出来。但从目前的应用来看，p 2 p 的威力还 主要体现在大范围的共享、搜索的优势上。在这方面主要引发了，或 者说是更好地解决网络上四大类型的应用：文件共享与交换、协同工 作、搜索引攀、分布计算、智能代理。 1 3 1 文件共享与交换 可以说文件交换的需求直接引发了p 2 p 技术热潮。在传统的w e b 方式中，要实现文件交换需要服务器的大力参与，通过将文件上传 到某个特定的网站，用户再到某个网站搜索需要的文件，然后下载， 摹于c h o r d 的p 2 p 网络的负载平衡的研究 这种方式的不便之处不言而喻。电子邮件是方便了个人问文件传递 问题，却没法解决大范围的交换。这也是w e b 的重要缺陷，n a p s t e r 就是在情况下横空出世，抓住人们对m p 3 喜欢的需求，n a p s t e r 的 m p 3 交换直接引发了网络的p 2 p 技术革命。在国外类似n a p s t e r 的 产品很多，如c u t e m x 、f r e e n e t 、g n u t e l l a 、i m e s h 、t o a d n o d e 、 s c o u re x c h a n g e 等。 1 3 2 协同工作 公司机构的日益分散，给员工和客户提供轻松、方便的消息和 协作的工具，变得日益重要。网络的出现，使协同工作成为可能。 但传统的w e b 方式实现，给服务器带来了极大的负担，造成了昂贵 的成本支出。p 2 p 技术的出现，使得互联网上任意两台p c 都可建 立实时的联系，建立了这样一个安全、共享的虚拟空间，人们可以 进行各种各样的活动，这些活动可以是同时进行，也可以交互进行。 p 2 p 技术可以帮助企业和关键客户，以及合作伙伴之间建立起一种 安全的网上工作联系方式，因此基于p 2 p 技术的协同工作也受到了 极大的重视。 1 3 3 搜索引擎 p 2 p 技术的另一个优势是开发出强大的搜索工具。p 2 p 技术使 用户能够深度搜索文档，而且这种搜索无需通过w e b 服务器，也可 以不受信息文档格式和宿主设备的限制，可达到传统目录式搜索引 擎( 只能搜索到2 0 一3 0 的网络资源) 无可比拟的深度( 理论 上将包括网络上的所有丌放的信息资源) 。以p 2 p 技术发展的另一 先锋g n u t e l l a 进行的搜索为例：一台p c 上的g n u t e l l a 软件可将 用户的搜索请求同时发给网络上另外1 0 台p c ，如果搜索请求未得 到满足，这1 0 台p c 中的每一台都会把该搜索请求转发给另外1 0 台p c ，这样，搜索范围将在几秒钟内以几何级数增长，几分钟内 就可搜遍几百万台p c 上的信息资源。可以说，p 2 p 为互联网的信 息搜索提供了全新的解决之道。著名的搜索引擎公司g o o g l e 也宣 称要采用p 2 p 技术来改进其搜索引擎，一家名为i n f r a s e a r c h 的新 l o 基于c h o r d 的p 2 p 嘲络的负载平衡的研究 建公司也因为开发p 2 p 技术的搜索引擎而获得了一笔巨额风险投 资。 1 3 4 分布计算 p 2 p 技术可以为企业或者研究机构提供大规模的运算能力。它 可以利用整个网络上的电脑，运用其闲置的中央处理器，内存以及 磁盘空间，让企业或者研究机构将大型的运算工作分散到多部电脑 上。此外，其运算结果可以直接分享到对等网络中的其他机器上。 以往未曾运用的计算资源，如今可以不通过分布式架构就得到充分 运用的效果。其结果就是更快速的计算过程以及更低廉的成本。 1 3 5 智能代理 p 2 p 技术也可以让电脑网络通过智能代理程序，进行灵活的人 机互动。智能代理程序常驻在对等网络的电脑上，并互相传送信息 进行通信。智能代理还可以为其他对等共享系统进行初始化操作。 例如，智能代理可以用来根据网络进程的优先顺序进行排序，统计 流量，查找本地的共享文档或者检测异常行为并中止其运行，避免 病毒和黑客程序对网络的破坏。 当然以上五种类型应用决不是p 2 p 仅有的应用，被认为至少还有 1 0 0 种应用等着去开发。与b 2 c 、b 2 b 、c 2 c 、c 2 b 等一些概念不同，p 2 p 是技术，甚至技术思想的革命。更重要的是，p 2 p 技术将实现互联网 的大部分潜力，将互联网从一个基于文件的网页和电子邮件网络转变 成一个动态的、颗粒状网络，在网络中，特定的信息组件可被有效地 放置和分享。 1 4 影响p 2 p 技术应用的限制 1 4 1 可管理性方面的问题 在实际应用方面，p 2 p 的运算结构很容易引发错误和故障。例 如，在p 2 p 网络中，用户可能会突然关闭其它人正在访问的电脑设 备。还有目前越来越多的商业人士使用便携的笔记本电脑，很可能 摹于c h o r d 的p 2 p 网络的负载r 衡的研究 当带有非常重要数据的笔记本电脑离开公司的内部网络，就会出现 其他人无法访问的尴尬局面。p 2 p 网络的精髓在于其“乌托邦”式 的管理方式，这种方式给了用户更多的自由，但是这也陷入了“无 政府主义”的困境。可以想象，缺乏管理的p 2 p 网络将会成为病毒、 色情内容以及非法交易的温床。 1 4 2 安全问题 不少专家认为，不同的计算机平台、软件版本和大量存在的其 他因素成为分布式计算得以广泛应用的一个难以逾越的障碍。微软 的高级研究员g o r d o nb e l l 说：“要使p 2 p 的梦想成为现实，安全 和标准是最重要的。”物理和逻辑安全是p 2 p 模式所要关心的重点 问题。公司用户理所当然地将他们的服务器放置在安全地点，同时 使用安全软件进行保护。但是桌面电脑往往安全级别较低。如果将 办公场所内的所有桌面电脑通过内部p 2 p 网络进行互联，将大大增 加不安全隐患一黑客可以只要访问其中一台电脑，就可以在整个网 络中畅通无阻 著名的网络安全公司i s s ( i n t e r n e ts e c u r i t ys y s t e mi r c ) 的研究主任c h r i sr o u l a n d 先生曾针对n a p s t e r 这样的音乐交换服 务做出这样的评判：“我们将网上音乐下载称作危险的网络行为。” 这种安全上的隐患通常来自两个方面：病毒和黑客。谁也不知道， 自己下载的文件是否带有致命的病毒，而无孔不入的黑客能放过一 个呈开放状态的电脑系统吗? 在n a p s t e r 上，有一点是不容置疑 的，那就是：你正和自己不认识、不信任的人分享代码及i p 地址。 一旦i p 地址公开，用户便很可能引来入侵者或“拒绝服务”攻击。 与拨号上网的方式相比，任何以高速方式连接网络和维持开放状态 的电脑，其遭受攻击的风险更高。 1 4 3 成本仍然过高 商业应用的开发人员需要仔细的检测企业应用程序所需要的 服务器资源和带宽。p 2 p 模式则减少了这种仔细设计的可能性，而 增加了大量的不确定带宽、服务器资源和分饰式存储的需求。尽管 1 2 基于c h o r d 的p 2 p 嘲络的负载甲衡的研究 理想中的p 2 p 模式会将数据存储在消费者的客户端系统中，这样在 实际的应用中就需要客户端和服务器端一样，都拥有所需数据的备 份。此外，p 2 p 模式的应用越多，那么就必须拥有更快的硬件性能 和更大的存储容量。而上述问题可能造成的结果必然是抵消了原来 p 2 p 可以减少服务器端费用支出的优势。 能源的消耗也是个问题一在p 2 p 模式中，客户系统将需要2 4 小时的不关机运行一而这种情况的出现，将会导致p 2 p 解决方案的 总体成本增高。虽然p 2 p 系统所使用的硬件设备可能比服务器的价 格较低，但专家指出，p 2 p 模式的真正成本支出在于规划和管理。 1 4 4 仍没有非常吸引人的商业应用 p 2 p 模式目前所存在的最大问题就是缺少足够吸引人的企业应 用程序。而它最适应作相对简单、重复性的工作，可以把工作任务 分配给数量众多的电脑系统。s e t i h o m e 是一个非常理想的分布式 计算计划，由于运算结果不需要特定的排序，而任务是运行在大致 相同的电脑系统中，因此数据可以更简便的汇总，日程安排也相对 更加轻松。p 2 p 模式也具有成为工作组协作系统的有力助手的潜 力，但某些公司财政方面的操作，比如e r p ( 企业资源计划) 和 c r m ( 用户关系管理) 等应用并不适合分布式计算环境。 1 4 5 吞噬网络带宽 由于p 2 p 网络的用户众多，当某个用户进行搜索时，自然会得 到大量的搜索结果。而除了少数有用的信息以外，其他大多数的信 息可能都属于垃圾信息。用户将不可避免地陷入垃圾信息的汪洋大 海。在p 2 p 使网络变得空前活跃的同时，将大量吞噬网络带宽。特 别是在大多数用户更喜欢传送大体积的m p 3 文件、视频文件的时 候，这个问题更加不容忽视。在我国，网络带宽较窄成了p 2 p 应用 难以逾越的障碍。 尽管对p 2 p 存在着这样那样的疑虑，许多p c 业专家仍然相信 该技术将彻底推翻现在抑制分布式计算发展的藩篱。现在的桌面系 统的性能远远超过以前的许多服务器，这为p 2 p 的发展提供了巨大 基于c h o r d 的p 2 p 嘲络的负载r 衡的研究 的硬件基础。随着宽带、高速网络的发展，p c 将释放出前所未有 的潜能，而v p n ( 虚拟个人网络) 软件也将为p 2 p 的发展提供保障。 1 5 小结 p 2 p 网络从诞生到今天，已经经历了三次更新换代。从最初共享音 乐的n a p s t e r ，到风靡一时的g n u t e l l a ，再到现在以d h t 技术为主的 第三代研究型p 2 p 网络，如c h o r d ，p a s t r y 等。p 2 p 网络不仅在性能 上得到了很大的提升，其应用性也不断的被用户所接受。 p 2 p 网络可以应用在很多领域，诸如文件共享与交换，协同工作， 搜索引擎，分布计算和智能代理等等。它能提供重要的信息和服务， 促进成本的最小化，赋予了用户更多的自主权，在这之上出现了各种 各样的服务。 当然，p 2 p 网络的发展并不是一帆风顺，它受到了一些条件的制约， 网络的自治性带来了管理方面的问题，安全隐患也随时存在，成本过 高使得网络并不能广泛的应用，特别是在商业上，没有非常好的应用， 网络对带宽的吞噬也是一个影响到性能的重要问题。 1 4 基于c h o r d 的p 2 p 网络的负载平衡的研究 第2 章d h t 网络概述 2 1 前两代p 2 p 网络的缺陷 p 2 p 网络发展的前两代技术，分别以n a p s t e r 和c n u t e l l a 为代表 的应用，有着严重的局限性。 n a p s t e r 使用了中央服务器，由此带来了单点失效的问题，即如果 服务器崩溃，整个网络将瘫痪。而之前由于m p 3 版权的法律问题， n a p s t e r 中央服务器被迫停止运行，继而是整个n a p s t e r 网络在一夜 之间消失，就足以说明单点失效问题的严重性。因此可以说，n a p s t e r 并不是真正意义上的p 2 p 系统。 g n u t e l a 没有中央服务器，网络中的节点都是处于对等的地位。 但是它所使用的泛洪法查询方式，使得网络的可扩展性大大降低。因 为随着网络中节点数量的大幅度增加，泛洪法查询带来的网络通讯量 的增加将是无法想象，甚至可以导致网络的崩溃。 2 2d h t 网络的产生 前两代p 2 p 网络的缺陷，也促使着越来越多的人来对p 2 p 网络进行 研究和创新。在最近几年取得了突破，即基于d is t r i b u t e dh a s ht a b l e ( d h t ) 的结构化网络的广泛应用 1 4 3 ， 9 ， 1 5 ， 1 6 ， 1 7 。其 中比较典型的几个网络为t a p e s t r y 1 7 ，c h o r d 9 ，p a s t r y 1 8 ， c a n 1 5 3 和v ic e r o y 1 9 。在这些系统中，数据单元与一个关键字相结 合，每一个处理器负责存储某一个范围内的关键字。这些系统都支持 一种路由协议，它能使用户找到负责目标关键字的一台机器。评价这 些d h t 系统的参数包括下面这些： 拥塞：不能有任何主机成为整个服务性能的瓶颈。有查询带来 的路由开销应该均匀地分布在网络中的各个参与活动的主机 上。 加入离开的代价：服务应该能轻松地适应各种变化。当有主 机加入或者离开，只需要- - t j 、部分主机改变它们的状态。特别 是网络中的连接数，即代表网络的图的度数应该较小。 查询路径长度：查询的转发路径上应该涉及到尽可能少的机 基于c h o r d 的p 2 p 网络的负载甲衡的研究 器。我们的目标是使最长路径最小化。这叫做网络的膨胀。 容错：当某些主机连接失效之后，网络还能比较好的服务。 我们需要考虑下面一种情况，即网络中任意一个子集的主机失 效，或者是在最差的情况下，即可以选择网络中任何一台主机 失效。对于上面两种情况，我们都有两种模型可以考虑。第一 种是失败停止模型，在这个模型中，失效的主机连接一点都 不响应了。第二种是拜占庭模型，这种模型中，失效的主机 连接可能会表现一种不确定或者恶意的行为。 动态缓存：非常热点的数据可能会在它们所在位置或者附近造 成网络瓶颈。减轻热点附近的拥塞状况则需要服务能支持某种 动态缓存的机制，在这种机制中，数据可以复制到其他的主机 上。 表2 1 以上面的这些参数，总结了各种d h t 系统的性能。 查询方案膨胀拥塞连接 c h o r d l o gn( 1 0 9n ) nl o gn t a p e s t r yl o gn( 1 0 9n ) n1 0 9n c a n d n 7 。 d n ”d s m a l lw o r l d l 0 9 2n( 1 0 92 n ) n0 ( 1 ) v i c e r o yl o gn( 1 0 9n ) n 0 ( 1 ) 表2 1 ：集中d h t 查询方案的亟塑性能比较 2 3c h o r d 针对p 2 p 网络中如何有效地定位存储所需数据的节点的问题，i o n s t o ic a ，r o b e r tm o r r i s ，d a y i dk a r g e r 等人提出了c h o r d 9 。c h o r d 作为d h t 系统的一个应用，是一个分布式的查询协议。 c h o r d 协议只提供一种操作：给定一个关键字，它把这个关键字映 射到一个节点上。在c h o r d 的实际应用中，这个节点可能负责存储与这 个关键字相关的一个值。c h o r d 使用了一种一致散列方法 2 0 来给c h o r d 节点分配关键字。这种一致散列方法能起到一定的负载平衡的作用，因 为每一个节点接收到的关键字的数量大致相同，而且当节点加入离开 1 6 摹干c h o r d 的p 2 p 刚络的负载f 衡的研究 系统的时候，关键字的移动次数也较少。 2 3 1 系统模型 c h o r d 比较好的解决了下面的几个问题，从而简化了p 2 p 系统的 设计和基于c h o r d 的应用： 2 0 负载平衡：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 能忍受下层 网络的失效，因为负责给定关键字的节点总是能找到。在系 统处于连续的变化状态时，这也是能保证的。 灵活的命名：c h o r d 对于它所查询的关键字的结构没有限制： c h o r d 的关键字空问是扁平的。这就给c h o r d 应用如何在名字 和关键字之问建立映射，提供了很大的灵活性。 2 3 2c h o r d 基本协议 c h o r d 的一致散列函数使用一个基本的散列函数，如s h a l 2 1 ， 赋予每个节点和关键字一个m 位长的标识符。节点的标识符通过对 节点的i p 地址进行散列得到，而关键字的标识符则是对关键字进行 散列得到的。标识符的长度m 的值应该足够长，使得两个节点或者 关键字散列成同一个标识符几乎不可能。 一致散列函数按照下面的方法来把关键字赋予节点。标识符被 排成一个以2 。为模的环形。关键字k 被赋予在环形中，标识符等于或 紧跟着k ( 的标识符) 的那个节点。这个节点被称为关键字k 的 摹于c h o r d 的p 2 p 列络的负载平衡的研究 s u c c e s s o r 节点，记为s u c c e s s o r ( k ) 。如果用值从0 到2 。1 的一个环 形上的数字来表示标识符，那么s u c c e s s o r ( k ) 就是k 之后按顺时针 方向上的第一个节点。 图2 1 表示了一个标识符环，m = 3 。这个环上有3 个节点：0 ，l 和 3 。标识符1 的s u c c e s s o r 节点是l ，所以关键字1 的被定位在节点1 上。 类似的，关键字2 的被定位在节点3 上，关键字6 在节点0 上。 m k s n 6 ) ，3 图2 1 ：含有3 个节点0 ，1 和3 的标识符环 在分布式的环境中，只需要- - d , 部分的路由信息就能进行一致 散列。每个节点只要知道在环上，它的s u c c e s s o r 节点。对一个给 定的标识符的查询，可以在通过这些s u c c e s s o r 指针在环上传递， 直到遇到它们遇到第一个紧跟着标识符的节点，这个节点就是查询 的目标节点。c h o r d 协议的一部分维护着这些s u c c e s s o r 指针，这 样来保证所有的查询可以被j f 确地解析。但是，这种方法的效率不 高：查询到目标节点可能会访问到环上的所有n 个节点。为了加 速查询过程，c h o r d 还维护着额外的路由信息。 每个节点，n ，维护着一个有着m ( 至多) 个入口的路由表， 这个表叫做f i n g e r 表。节点n 的表中的第i 个入口，包括了在标识 符环上，n 的至少2 1 1 个位置之后的( 如s u c c e s s o r ( n + 2 。1 ) ，其中l i m ( 所有运算都是以2 为模的) 第一个节点，s ，的标识符。 我们把s 称为节点n 的第i 个f i n g e r ，记为n f i n g e r i 1 n o d e ( 见表 2 2 ) 。一个f i n g e r 表的入口包括了c h o r d 标识符和对应节点的i p 摹于c h o r d 的p 2 p 州络的负载平衡的研究 地址( 端口) 。注意到n 的第一个f i n g e r 就是环上的紧跟着的 s u c c e s s o r ；为了方便，我们把第一个f i n g e r 叫做s u c c e s s o r 。 符号定义 f i n g e r k s t a r t( n + 2 ”1 ) m o d2 ，1 k m i n t e r v a l f i n g e r k s t a r t ，f i n g e r k + 1 s t a r t ) n o d e第一个节点n f i n g e r k s t a r t s u c c e s s o r 在标识符环上的下一个节点；f i n g e r 1 n o d e p r e d e c e s s o r在标识符环上的前一个节点 表2 2 ：含有m 位标识符的节点n 的变量定义 在图2 3 的例子中，节点1 的f i n g e r 表指向了标识符分别为( 1 + 2 0 ) m o d2 3 = 2 ，( 1 + 2 1 ) m o d2 3 = 3 ，( 1 + 2 2 ) m o d2 3 = 5 的s u c c e s s o r 节点。因 为节点3 是节点2 之后的第一个节点，所以节点2 的s u c c e s s o r 就是 节点3 ，节点3 的s u c c e s s o r 当然也是节点3 ，节点5 的s u c c e s s o r 是 节点0 。 这种方法有两个重要的特点。首先，每个节点只是存储了一小部分 其他节点的信息，而且对于标识符环上在它之后的节点，距离越近， 它掌握的信息就越多。其次，一个节点的f i n g e r 表并不是包含了能查 询任意关键字k 的足够信息。比如，在图2 3 中，由于节点l 的 s u c c e s s o r 并没有出现在节点3 的f i n g e r 表中，所以节点3 并不知道 节点1 的s u c c e s s o r 。 如果节点n 不知道关键字k 的s u c c e s s o r 节点，那么它可以找到一 个比它自己离k 更近的节点，这个节点所了解的关于k 的信息会比节 点n 多。于是n