（计算机应用技术专业论文）基于bayesian网络的对等环境负载载均衡模型.pdf

浙江大学硕士学位论文摘要 摘要 近几年来p 2 p 技术飞速发展，吸引了越来越多的研究机构和团体加入到这个 研究领域。各式各样的p 2 p 的产品和服务更是层出不穷，p 2 p 的应用逐渐扩展到 文件共享、协同工作、对等计算、实时通信、信息检索、广域网存储、智能代理、 网络游戏等多个领域。 由于p 2 p 网络中节点间连接的随机性，随着p 2 p 网络的急剧膨胀，各节点的 连接数会出现很大的差距，导致整个网络的负载不均衡，因此负载均衡技术成为 当前p 2 p 网络的研究热点之一。 b a y e s i a n 网络是用来表示变量之间连接概率的图形模式，提供了一种自然的 表示因果关系的方法，能够根据事件发生的历史信息，对未来发生的可能性进行 预测。b a y e s i a n 网预测模型具备概率推理能力强、语义清晰、易于理解等特点， 是目前不确定知识表示和推理领域中最有效的理论模型之一，也是近年来各种领 域研究的热点之一。 本文在对p 2 p 的应用技术，b a y e s i a n 网络模型，以及负载均衡技术深入研究 的基础上，开展了p 2 p 环境下负载均衡的研究，论文的主要工作如下： 1 提出了基于b a y e s i a n 网络的p 2 p 环境下的负载均衡。该模型利用b a y e s i a n 网络推理，通过预测网络中节点的可能负载，调度服务节点的选择算法，平衡网 络节点中的连接，从而达到改善网络系统的负载使之达到均衡的目的，对保证整 个p 2 p 网络的稳定高效具有积极的意义。 2 构建了一个基于千兆以太网的p 2 p 负载均衡仿真实验环境，该环境包括5 个服务节点及1 0 0 个来自各客户节点的服务请求连接，每个连接各发起资源请求 2 0 0 次。 3 在构建的仿真环境下，对无负载指标的b a y e s i a n 信任网模型，负载指标 多层的b a y e s i a n 信任网模型，以及动态负载均衡模型进行了仿真实验。实验结果 表明，负载指标多层的b a y e s i a n 信任网模型和动态负载指标模型都能实现p 2 p 网 浙江大学硕士学位论文 摘要 络的负载均衡，但负载指标多层的b a y e s i a n 信任网模型较动态模型具有更强的适 用性。 关键词：p 2 p ，对等网络，b a y e s i a n 网络，负载均衡，信任模型 i i 浙江大学硕士学位论文 a b s t r a c t a b s t r a c t t h er a p i dd e v e l o p m e n to fp 2 p t e c h n o l o g yd u r i n gt h ep a s tf e wy e a r sh a si n v o l v e d m o r ea n dm o r ei n s t i t u t i o n sa n do r g a n i z a t i o n si n t ot h i sr e s e a r c ha r e a v a r i o u st y p e so f p 2 pp r o d u c t sa n ds e r v i c e se m e r g ei ne n d l e s s l y , a n dt h ea p p l i c a t i o no fp 2 ph a ss p r e a d o v e rt h ea l lt h o s e r e g i o n s ，i n c l u d i n g f i l e s h a r i n g ，c o l l a b o r a t i o n ，p e e r - t o - p e e r c o m p u t a t i o n ，r e a lt i m ec o m m u n i c a t i o n ，s e a r c h i n g ，n e t w o r ks t o r a g e ，i n t e l l i g e n ta g e n t ， a n dn e tg a m e s 。 d u et ot h er a n d o m i c i t yo ft h ec o n n e c t i o n ，a st h es h a r pg r o w t ho fp 2 p n e t w o r k ，t h e n u m b e ro ft h ec o n n e c t i o n sb e t w e e np e e r sd i f f e re a c ho t h e ral o tw h i c hl e a d st o i m b a l a n c eo fw h o l ep 2 pn e t w o r k t h e r e f o r e ，l o a db a l a n c eh a sb e c o m eo n eo ft h e h o t t e s ts u b j e c t si np 2 pn e t w o r kr e s e a r c h b a y e s i a nn e t w o r ki sag r a p hm o d e lw h i c hd e n o t e st h ep r o b a b i l i t ya m o n g v a r i a b l e s ，p r o v i d e san a t u r ew a yt or e p r e s e n tc a u s a l i t y , a n dp r e d i c t st h ef u t u r e p r o b a b i l i t ya c c o r d i n gt ot h eh i s t o r i ci n f o r m a t i o n t h eb a y e s i a nn e t w o r kh a st h e f e a t u r e so fs t r o n gp r o b a b i l i t yr a t i o c i n a t i o n ，c o n t e x tc l a r i t y , e a s yt ou n d e r s t a n di ti so n e o ft h em o s te f f e c t i v et h e o r ya n dr e s e a r c hh o t s p o ti nt h ea r e ao fi n d e t e r m i n a t e k n o w l e d g ep r e s e n t a t i o na n dr a t i o c i n a t i o n b a s e do nt h o r o u g h l y i n v e s t i g a t i o na n dd e e pr e s e a r c ho np 2 pt e c h n o l o g y , b a y e s i a nn e t w o r k ，a n dl o a db a l a n c e ，t h i st h e s i ss t a r t sr e s e a r c ho nl o a db a l a n c eu n d e r p 2 pn e t w o r k ，t h em a j o rw o r ki n c l u d e s ： 1 al o a db a l a n c em o d e lb a s e do nb a y e s i a n p r e d i c a t i o nm o d e lu n d e rp 2 p e n v i r o n m e n th a sb e e np r o p o s e di nt h i st h e s i s t h em o d e lu s e sp r o b a b i l i t ys y s t e ml o a d o fp e e r sp r e d i c t e db yb a y e s i a nr a t i o c i n a t i o nt os c h e d u l et h ep e e rc h o s e na l g o r i t h m ， w h i c hb a l a n c e st h ec o n n e c t i o nb e t w e e nt h ep e e r s ，a n da m e l i o r a t e st h en e t w o r k s y s t e m ， e x p r e s s e sp o s i t i v es i g n i f i c a n tt ot h ew h o l ep 2 pe n v i r o n m e n t s 2 as i m u l a t e dl a b o r a t o r ye n v i r o n m e n tf o rp 2 pl o a db a l a n c eb a s e do ng i g a b i t s w i t c h e rh a sb e e nc o n s t r u c t e d t h i se n v i r o n m e n ti n c l u d e san u m b e ro f5s e r v e rp e e r s a n d10 0c o n n e c t i o n sf r o mc l i e n tp e e r s ，a n de a c hc o n n e c t i o ni n i t i a t e2 0 0 r e q u e s t sf o r i i i 浙江大学硕士学位论文a b s t r a c t i c s u u i c e s 3 e x p e r i m e n t sf o rb a y e s i a nt r u s tn e t w o r km o d e lb a s e do nn o n el o a di n d i c a t o r , b a y e s i a nt r u s tn e t w o r km o d e lb a s e do nm u l t i - l a y e rl o a di n d i c a t o r , a n dd y n a m i cl o a d b a l a n c em o d e lh a db e e nt a k e n ，n l er e s u l t ss h o wt h a tb o t ht h el a t e rt w om o d e lc a n e n s u r et h el o a db a l a n c eo ft h ep 2 pn e t w o r k ，b u t ，c o m p a r et od y n a m i cl o a db a l a n c e m o d e l ，b a y e s i a nt r u s tn e t w o r km o d e lb a s e do nm u l t i - l a y e rl o a di n d i c a t o rh a ss t r o n g e r a d a p t a b i l i t y k e y w o r d s ：p 2 p , p e e r - t o p e e r ，b a y e s i a nn e t w o r k ，l o a db a l a n c e ，t r u s tm o d e l i v 浙江大学硕士学位论文 图目录 图目录 图1 1c s 模式和p 2 p 模式。2 图2 1 朴素b a y e s i a n 模型。l l 图2 2t a n 模型j 13 图3 1 负载指标单层的b a y e s i a n 网络模型一2 2 图3 2 负载指标多层的b a y e s i a n 网络模型2 4 图3 3 负载指标相关的b a y e s i a n 网络模型2 6 图4 1 基于b a y e s i a n 网的p 2 p 信任模型框架3 1 图4 2 服务节点h a s h 映射3 3 图4 3 动态负载指标均衡模型3 7 图5 1 实验环境网络拓扑3 8 图5 2 各服务节点系统总体负载随时间变化曲线4 0 图5 3 服务节点2 信任度和负载随请求数变化曲线4 0 图5 4 服务节点2 各负载指标随时间变化曲线4 1 图5 5 各服务节点系统总体负载随时间变化曲线4 2 图5 6 服务节点2 的系统总体负载和信任随请求数变化曲线4 2 图5 7 各服务节点系统总体负载随时间变化曲线j 4 3 图5 8 多层模型和动态模型分值分布4 5 图5 9 多层模型和动态模型的延迟时间随请求数变化曲线4 6 v i i 浙江大学硕士学位论文 表目录 表目录 表3 1f e d o r a8 平台下负载信息对应文件1 8 表3 2 p r o c s t a t 中c p u 信息1 9 表3 3 负载指标单层的b a y e s i a n 网络模型中c p u 利用率的c p t 表2 3 表3 4 负载指标多层的b a y e s i a n 网络模型中c p u 利用率的c p t 表2 5 表3 5 负载指标相关的b a y e s i a n 网络模型中c p u 利用率的c p t 表2 7 表4 1b a y e s i a n 网叶子节点的能力等级分类3 4 表4 2 系统总体负载分级3 4 表4 3c p u 利用率分级3 4 表4 4 内存利用率分级3 5 表4 5 磁盘i o 利用率分级3 5 表4 6 网络利用率分级3 5 表5 1 系统硬件配置3 8 v i i i 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得迸婆盘堂或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：影小云 签字日期：叫卯孑年1 7 ( ，月 学位论文版权使用授权书 口7 日 f 本学位论文作者完全了解澎婆盘堂有权保留并向国家有关部门或机构送交本 论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝江盘堂可以将学位论文的 全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：乱t l 云 签字日期：v 归2 年妙c 7 月。7 日 翩签名瑚 签字日期：矽g 年6 月 日 浙江大学硕士学位论文第l 章绪论 第1 章绪论 1 1p 2 p 网络的定义 p 2 p 1 1 ，2 ，3 1 是p e e r - t o p e e r 的缩写，p e e r 在英语里有“( 地位、能力等) 同等者”、 “同事”和“伙伴 等意义，p 2 p 也就可以理解为“伙伴对伙伴”的意思。这样 一来，p 2 p 网络可以称为对等网络。 p 2 p 并不是一种全新的技术，在计算机网络发展的初期，互联网中的基础协 议叫c p i p 协议并没有客户端和服务器的概念，只要遵守t c p i p 协议，计算 机之间就可以实现网络连接。然而随着一些大型门户网站和搜索引擎的出现，互 联网的拓扑结构很快演变成了典型的c s ( c l i e n ta n ds e r v e r ，简称c s ) 架构，目 前，这种结构还是非常流行，网络上的大型的服务架构基本都还是基于c s 的。 p 2 p 的兴起源于多年前美国的一场著名的官司，被告是n a p s t e r 4 】提供的一种免费 共享音乐的软件，p c 机安装联网后即变成一台m p 3 服务器，实现本地m p 3 资源 的全球共享，n a p s t e r 被告的理由是侵犯了美国唱片协会的权益，因而被告上了法 庭，最后由于败诉，n a p s t e r 被迫关闭。然而正是n a p s t e r 的出现开启了互联网络 的一个新的时代叫2 p 时代。 目前，在学术界、工业界有关p 2 p 的定义各式各样，描述的范围有大有小， 侧重的对象也各不相同，但是其主要内容可以定义如下： 定义：p 2 p 是一种分布式网络，网络的参与者共享他们所拥有的一部分硬件 资源( 处理能力、存储能力、网络连接能力、打印机等) ，这些共享资源需要由 网络提供服务和内容，能被其它对等节点( p e e r ) 直接访问而无需经过中间实体。 在此网络中的参与者既是资源( 服务和内容) 提供者( s e r v e r ) ，又是资源( 服务 和内容) 获取者( c l i e m ) 。 由上述p 2 p 的定义中，我们可以总结出p 2 p 网络具有的以下特征： ( 1 ) 平等性：节点之间地位平等，既提供资源访问，也获取其他节点资源； ( 2 ) 分布性：资源分布在各个节点中，网络中没有中心服务器； 浙江大学硕士学位论文第l 章绪论 ( 3 ) 可扩展性：在对等网络中，节点的加入和退出都非常容易实现； ( 4 ) 健壮性：p 2 p 网络一般具有较高的可靠性和鲁棒性，容错能力强； ( 5 ) 隐私性：p 2 p 网络的节点之间是匿名的，一个节点无法知道其他节点的资 源和行为。 目前，互联网服务的典型模式是c l i e n t s e r v e r 。这种模式要求有高性能的服 务器，配合各种软件来集中处理信息，同时还响应网络中其他客户端的请求，相 对于服务器来说，每个客户端的处理能力和性能要求比较低，客户端只需要处理 一些简单的事务，功能非常有限。这种结构导致了网络中的内容向少数服务器集 中，服务器成为了网络中的资源提供者，因此服务器的性能和稳定尤为重要。 p 2 p 打破了传统的c s 模式，p 2 p 网络的定义从网络节点来看将会更加清楚： 在p 2 p 网络中，节点被称为s e r v e n t ，这是一个由s e r v e r 和c l i e n t 合成起来的词， 说明了p 2 p 网络中的节点的地位都是对等的，既拥有服务器( s e r v e r ) 的行为为 其他节点提供服务，也包括客户端( c l i e n t ) 的行为能享用其他节点提供的服 务。在这种网络中，一般来说节点之间在权力和义务上是对等的，双方不需要依 赖中心节点或服务器，只通过直接的相互连接和访问，就可以完成多种资源的共 同使用。p 2 p 与c s 模式的典型拓扑如图1 1 所示： 典型的c s 模式 p 2 p 模式 图1 1c s 模式和p 2 p 模式 目前，p 2 p 技术发展迅速，在分布式科学计算、文件共享、协同工作、搜索 引擎、i p 层语音通信( v o i p ) 、电子商务等诸多方面都有了广泛的应用【5 1 。 2 浙江大学硕士学位论文第1 章绪论 1 2b a y e s i a n 网络 b a y e s i a n 网络1 6 】1 7 】亦称信任网络( b e l i e fn e t w o r k ) ，是19 8 5 年由j u d e ap e a r l 首 先提出的。它是一种模拟人类推理过程中因果关系的不确定性处理模型。b a y e s i a n 网络使用概率积分表示不确定性，称为条件概率，或b a y e s i a n 积分。条件概率描 述为，对于给定的事件b ，a 事件发生率的概率，用p ( aib ) 表示。这表明在b 事件发生的情况下，a 事件发生的概率只与b 事件有关，与其他事件无关。事件 a 和b 的联合概率为事件b 发生的概率乘以给定b 的情况下，事件a 的条件概 率，或者事件a 发生的概率乘以给定a 的情况下b 发生的概率，表述如下： p ( ai 曰) 尸( b ) = p ( a b ) = p ( bl 么) p ( 么)公式( 1 1 ) 转换上述公式，得出b a y e s i a n 公式： p ( ai 曰) ：p ( b ia ) p ( a ) p ( b ) 公式( 1 2 ) 公式1 2 是b a y e s i a n 概率推理计算中非常重要的一个法则。 概率推理就是用给定的变量信息来计算其它变量的概率信息过程。当有一个 很大的随机变量集合时，概率推理计算时非常难于处理的。所以，需要变量满足 一定的条件约束，这个约束称为条件独立。 定义：对于给定变量集合k ，一，如果v 满足尸( yi 杉，_ ) = p ( vl 巧) ，则称 变量矿条件独立子矿。 也就是说，对于变量矿，如果知道y ，可以忽略杉。因此如果给定一个集合 y 情况下，形和y i 相互独立，则有： e ( eiy ，v ) = 尸( i 矿) 由条件概率的定义，又有： 尸( 杉l 巧，矿) 尸( 一i 矿) = p ( 杉，巧iy ) 所以可以得出： 尸( 形，杉i 矿) = p ( 形iy ) p ( 矿，ly ) 浙江大学硕士学位论文第l 章绪论 不失一般性，对于给定变量集合矿，如果每个变量独立于所有其他变量，那 么k ，圪圪是相互条件独立的，则有： p ( k ，圪iv ) = n 尸( ki 矿) 公式( 1 3 ) i = 1 b a y e s i a n 网络的定义为：对于n 个随机变量构成集合y = k ，圪) ，建立 在该集合上的联合概率分布p k ，圪) 可以表示为一个b a y e s i a n 网络 b ，其由两部分构成： b 。为b a y e s i a n 网络结构，是一个有向无j 不图( d a g ) ，它是由节点和有向弧段 组成的。节点代表事件或变量，弧段代表节点之间的因果关系或概率关系，而弧 段是有向的，不构成回路。 b 口为b a y e s i a n 网络的条件概率集合，每个节点都对应一个条件概率表， 用来表示其和父节点p a r e n t ( v , ) 的相互关系。利用公式1 2 和条件独立性，可将 其联合概率表示为： p ( z l ，吒，圪) = f i 尸( kp a r e n t ( v 1 ) ) 公式( 1 4 ) j = l b a y e s i a n 网络是继模糊逻辑、可信度方法和神经网络等方法之后新提出的不 确定知识表示模型。它以其坚实的理论基础，知识结构的自然表达方式，灵活的 推理能力，方便的决策机制而成为数据联合分析与预测的有力工具。在医疗诊断 系统、软件测试、网站的智能导航、电力系统的故障诊断等方面都有着广泛的应 用。 1 3 负载均衡技术 随着i n t e r n e t 的迅猛发展，网络业务量和用户数的急剧增长，单个服务器的处 理能力己无法满足这种需求，单靠升级网络设备又面对价格昂贵和不断升级的困 境，因此负载均衡技术【8 】应运而生。负载均衡就是指把客户端的请求，按照一定 的分配策略平均分给集群内部的各个节点进行处理，当系统的负载出现不平衡 时，还能将重载节点上的任务转移到轻载节点上执行，使得整个集群中所有节点 4 浙江大学硕士学位论文 第l 章绪论 的负载都趋向平衡，从而缩短作业的平均响应时间和提高系统的资源利用率。负 载均衡技术基于现有的网络结构，提供了一种扩展服务器带宽和增加服务器吞吐 量的廉价有效的方法，加强了网络数据处理能力，提高了网络的灵活性和可用性。 负载均衡包括两方面的含义： ( 1 ) 大量的并发访问或数据流量分担到多台设备上分别处理，减少用户等待响应 时间； ( 2 ) 单个重负载的运算分担到多台节点设备上做并行处理，每个节点设备处理结 束后，将结果汇总，返回给用户，系统处理能力得到大幅提高。 由此可见，负载均衡就是通过重新分布系统负载，使各主机间负载达到相对 均衡，从而降低任务的响应时问，提高系统资源的利用率，使系统的性能得以提 高。因此负载均衡的目标可以表述为： ( 1 ) 解决网络拥塞问题； ( 2 ) 为用户提供更好的访问质量； ( 3 ) 提高服务器响应速度； ( 4 ) 提高服务器及其他资源的利用效率； ( 5 ) 避免了网络关键部位出现单点失效： 负载均衡是实现资源有效共享，提高系统资源有效使用率的必然要求，是影 响系统有效运行的重要因素之一。 1 4 本文研究的内容和意义 本文从p 2 p 环境，b a y e s i a n 网络，负载均衡三个方面进行了研究。在p 2 p 方 面，本文给出了p 2 p 的定义，典型应用，着重研究了p 2 p 网络结构的发展。在 b a y e s i a n 网络方面，本文从b a y e s i a n 理论产生，发展，应用多个角度进行了研究， 并着重把b a y e s i a n 和p 2 p 环境结合，研究了相关模型和应用。在负载方面，本文 从p 2 p 网络的负载出发，研究了p 2 p 网络的静态和动态负载均衡算法，重点分析 了几种p 2 p 环境下的负载均衡算法。本文最后分析给出了p 2 p 网络环境下的负载 指标，并提出了基于负载指标的b a y e s i a n 网的三种模型，作了相应的分析，对其 中负载指标多层模型进行了实现。在实现过程中，本文又采用了动态均衡算法作 5 浙江大学硕士学位论文第1 章绪论 为比较，最后进行实验，以及实验结果分析，总结，展望。 基于b a y e s i a n 网络的对等环境负载均衡模型采用b a y e s i a n 网络模型，在 b a y e s i a n 中引入负载指标节点，各种指标的灵活组合能满足资源请求节点各种需 求，适应多种p 2 p 网络环境，通过预测网络中服务节点的负载，平衡网络节点中 的连接，从而达到改善网络系统的负载使之达到均衡的目的，对保证整个p 2 p 网 络的稳定高效具有积极的意义。 1 5 本文的组织 第一章、绪论。介绍论文的研究背景。给出了p 2 p 网络的定义，以及其和传统 网络的比较；同时简单介绍了b a y e s i a n 网络和负载均衡的概念；最后提出 论文的研究方案，研究目标，和预期结果。 第二章、相关问题研究分析研究了p 2 p 网络结构的发展，并介绍了几种代表 性的p 2 p 软件；分析研究了b a y e s i a n 网络的发展和应用；分别介绍了动态 和静态负载均衡，以及p 2 p 环境下的负载均衡算法。 第三章、基于b a y e s i a n 网络的负载均衡模型设计。本章首先分析了p 2 p 网络 节点的系统负载指标，然后提出三种基于负载指标b a y e s i a n 网络模型，并 做了相应的分析计算，最后阐述了基于b a y e s i a n 网负载均衡的p 2 p 环境中 负载指标的更新维护。 第四章、基于b a y e s i a n 网络的负载均衡模型。主要提出了建立基于b a y e s i a n 网络的静态和动态的负载均衡模型，其中设计实现了系统负载模型。 第五章、仿真实验和结果分析。本章主要介绍基于b a y e s i a n 网络的静态和动态 负载均衡模型的实验，并对实验数据进行分析和比较。 第六章、总结和展望。对论文进行总结和概括，提出将来的工作。 6 浙江大学硕士学位论文第2 章相关问题研究 第2 章相关问题研究 2 1p 2 p 结构发展 第一代对等网络结构是一种集中式的模型。集中式p 2 p 模型由一个中心服务 器来负责记录共享信息以及反馈对这些信息的查询；每一个对等实体要对它所需 共享的信息以及进行的通信负责，根据需要下载它所需要的其他对等实体上的信 息。这种形式具有中心化的特点，所有网上提供的资料都存放在提供该资料的客 户机上，服务器上只保留索引信息。此外服务器与对等实体以及对等实体之间都 具有交互能力。经典案例就是著名的m p 3 共享软件n a p s t e r 。 n a p s t e r 是最早出现的p 2 p 系统之一，并在短期内迅速成长起来。n a p s t e r 实 质上并非是纯粹的p 2 p 系统，它的体系结构为服务器上保留文件的目录，但不保 存文件的数据，文件目录中写有相应文件数据所属节点的网络地址，用户之间既 通过服务器相连，也直接相连。用户通过查询服务器上的文件目录得到相应文件 数据的网络地址，再向这个网络中的节点发出获得所需文件的请求，获得确认后， 在两者间直接传递数据，不再需要服务器。 n a p s t e r 首先实现了文件查询与文件传输的分离，有效地节省了中央服务器的 带宽消耗，减少了系统的文件传输延时。这种方式最大的隐患在中央服务器上， 如果该服务器失效，整个系统都会瘫痪。研究者发现当用户数量增加到1 0 5 或者 更高时，n a p s t e r 的系统性能会大大下降。另一个问题在于安全性上，n a p s t e r 并 没有提供有效的安全机制。 集中式p 2 p 可提供中心服务器目录检索、管理服务和标准的点到点通信，具 有高效的检索和低效的交换服务的特点。集中式p 2 p 对小型网络而言在管理和控 制方面占有一定的优势，但是集中目录式p 2 p 模型还存在很多问题，主要表现在 以下方面： ( 1 ) 网络可靠性和安全性较低，因为中央服务器的瘫痪容易导致整个网络的崩溃； ( 2 ) 随着网络规模的扩大，中央目录服务器维护和更新的费用将急剧增加，所需 成本过高，因此对大型网络并不适合； 7 浙江大学硕士学位论文第2 章相关问题研究 ( 3 ) 中央服务器的存在引起共享资源在版权问题上的纠纷，这也是直接导致 n a p s t e r 破产的原因； ( 4 ) 缺乏有效的安全的共享机制，资源可用性差； 第二代对等网络分布式对等网络吸取了n a p s t e r 失败的教训，以g n u t e l l a 9 1 和e d o n k e y t l o j 为代表的后来者们将n a p s t e r 的理念推进一步，避免了中央服务器的 存在，这种p 2 p 网络模型称为分布式模型。当用户p c 安装这些软件后，就会立 即变成一台能够提供完整目录和文件服务的服务器，并会自动搜寻其他同类服务 器，从而联成一台由无数p c 组成的网络超级服务器。与n a p s t e r 网络不同，它 不存在中央目录服务器，或者说把所有机器都变成了服务器。以g n u t e l l a 网络为 例，一台新对等机首先通过访问某特殊站点提供的“主机缓存服务 机制来得到 一台活动对等机地址，通过与它建立一个连接将自己接入g n u t e l l a 网络；接着， 该新对等机主动探查网络中的其他对等机，找到与之相邻的对等机节点，在进行 文件查找时，该对等机首先向与之相邻的所有活动对等点发送一个查询描述符 q u e r y ，在其他对等机接收到该查询描述符后，检查本地是否有符合查询请求的 文件内容，如果有，则按查询描述符的发送路径返回一个查询响应描述符q u e r y h i t ，无论本地是否存在符合查询请求的文件内容，其他对等机都会将该查询包通 过扩散方式继续在网络中传递，直至查询包中t t l 属性值递减为o 时才停止继 续转发；一旦定位了响应查询文件的对等机之后，就与响应对等机建立t c p 连接， 通过h t t p 协议从响应对等机中下载自己查询的文件，文件传输不再经过 g n u t e l l a 网络进行。这种分布式的对等网络不再是简单的点到点通信，而是更加 高效、复杂的网络通信。类似的实现还有f r e e n e t t l l l 、f r e eh a v e n f l 2 1 、p u b l i u s 1 3 】 等。e d o n k e y 和e m u l e 1 4 】等软件引入了强制共享机制，在一定程度上避免了第一 代p 2 p 纯个人服务器管理带来的随意性和低效率，同时由于没有中心服务器的存 在，不会因为其中一个节点的故障而导致全部网络瘫痪。但是这种分布式对等网 络模型也存在很多弊端，主要表现在： ( 1 ) 搜索请求要经过整个网络或者至少是一个很大的范围才能得到结果，因此， 这种模式占用很多带宽，而且需要花费很长时间才能有返回结果； 8 浙江大学硕士学位论文第2 章相关问题研究 ( 2 ) 随着网络规模的扩大，通过扩散方式定位对等点及查询信息的方法将会造成 网络流量急剧增加，从而导致网络拥塞，最终使g n u t e l l a 网络被分片，使得查询 访问只能在网络很小的范围内进行。因此，网络的可扩展性不好，不适合大型网 络； ( 3 ) 纯分布式的p 2 p 模式很难被企业所利用，因为它缺少对网络上的用户节点数 以及对其提供的资源的一个总体把握； 在第三代p 2 p 的软件体系结构中，采用了混合式p 2 p 。混合式对等网络结合 了集中式和分布式对等网络的优点，在分布式模式的基础上，将用户节点按能力 进行分类，使某些节点担任特殊的任务。这些节点共分为三种： ( 1 ) 用户节点：普通节点，不具有任何特殊的功能； ( 2 ) 搜索节点：处理搜索请求，从它们的“孩子 节点中搜索文件列表，这些节 点必须有预先设定的网络连接速度； ( 3 ) 索引节点：用于保存可以利用的搜索节点信息，并收集状态信息，维护网络 结构信息。连接速度快、内存充足的节点可以作为索引节点； 一个节点可以既是搜索节点又是索引节点。用户节点可以选择3 个搜索节点 作为它的“父节点 ，如果“父节点”接受该用户节点作为它的“孩子”的话， 那么该用户节点就可以提交其所要共享的列表给它的“父节点 。在缺省的情况 下，搜索节点可以最多维护5 0 0 个“孩子”节点。 i c a z a a t l 5 】模型是p 2 p 混合模型的典型代表，它在纯p 2 p 分布式模型基础上引 入了超级节点的概念，综合了集中式p 2 p 快速查找和纯p 2 p 去中心化的优势。 k a z a a 模型将节点按能力不同( 计算能力、内存大小、连接带宽、网络滞留时间等) 区分为普通节点和搜索节点两类( 也有的进一步分为三类节点，其思想本质相同) 。 其中搜索节点与其临近的若干普通节点之间构成一个自治的簇，簇内采用基于集 中目录式的p 2 p 模式，而整个p 2 p 网络中各个不同的簇之间再通过纯p 2 p 的模式 将搜索节点相连起来，甚至也可以在各个搜索节点之间再次选取性能最优的节 点，或者另外引入一新的性能最优的节点作为索引节点来保存整个网络中可以利 用的搜索节点信息，并且负责维护整个网络的结构。由于普通节点的文件搜索先 9 浙江大学硕士学位论文第2 章相关问题研究 在本地所属的簇内进行，只有查询结果不充分的时候，再通过搜索节点之间进行 有限的泛洪。这样就极为有效地消除纯p 2 p 结构中使用泛洪算法带来的网络拥塞、 搜索迟缓等不利影响。同时，由于每个簇中的搜索节点监控着所有普通节点的行 为，这也能确保一些恶意的攻击行为能在网络局部得到控制，并且超级节点的存 在也能在一定程度上提高整个网络的负载均衡。 索引节点和搜索节点是第三代p 2 p 的软件体系结构中的两个关键之处。相对 于分布式结构而言，混合式结构的资源搜索事件更少，占用的网络带宽更小；相 对于集中式结构而言，混合式结构每个簇是一个自治块，不需要额外的中心服务 器管理，同时具有传统集中式结构易于管理的优点。但是，就一个簇来说，也可 能存在着单点故障和成为系统瓶颈的可能。 一般而言，混合p 2 p ，集中式p 2 p 形式有利于网络资源的快速检索，以及只 要服务器能力足够强大就可以无限扩展，但是其中心化的模式容易遭到直接的攻 击；分布式p 2 p 形式解决了抗攻击问题，但是又缺乏快速搜索的能力。混合p 2 p 形式结合了集中式和分布式p 2 p 形式的优点，在设计思想和处理能力上都得到近 一步优化。它在分布式模式基础上，将用户节点按能力进行分类，使某些节点担 任特殊的任务。 2 2b a y e s i a n 的发展 虽然b a y e s i a n 网络模型是2 0 世纪8 0 年代才提出的，但其产生的根源要追溯 到1 7 6 3 年由r e v e r e n dt h o m a sb a y e s 1 6 1 提出的b a y e s i a n 理论，b a y e s i a n 理论是 b a y e s i a n 网络的重要理论基础之一。由于当时b a y e s i a n 方法在理论和实际应用中 还存在很多不完善的地方，因而在1 9 世纪并未被普遍接受。2 0 世纪初，遗传学 家s e w a l lw r i g h t 提出了有向无环图( d i r e c t e d a c y c l i cg r a p h ，d a g ) ，并成为经济 学、社会学和心理学界广泛采用的因果表达模型。l j g o o d 和a l a nt u r i n g 合作发 展了概率的表示方法以及b a y e s i a n 推理方法，可以被认为是现代b a y e s i a n 网络的 先驱。与有向无环图相结合来表示决策问题的影响图( i n f l u e n c ed i a g r a m ) 在2 0 世纪7 0 年代末被用于决策分析中，但是它在求值运算中只用到了枚举方法。1 9 8 2 年，p e a r l 和k i m 发展了在具有树或者多树结构的网络上实现基于推理的消息传 1 0 浙江大学硕士学位论文第2 章相关问题研究 递方法，并阐述了构造因果概率模型的重要性。1 9 8 8 年，p e a r l 在总结并发展前 人上作的基础上，完整提出了b a y e s i a n 网络。2 0 世纪9 0 年代，有效的推理和学 习算法的出现，推动了b a y e s i a n 网络的发展和应用。 b a y e s i a n 定理给出了预测推理的方法，理论上它看起来很完美，但在实际中它 并不能被直接利用，因为它需要知道证据的确切分布概率，而实际上我们并不能 确切地给出证据的分布概率。为了使用b a y e s i a n 定理来分类，在很多预测方法中 都做出某种假设以逼近b a y e s i a n 定理的要求，朴素b a y e s i a n 分类方法就是其中的一 种。 朴素b a y e s i a l l 模型f 1 7 1 8 1 是b a y e s i a l l 模型中一种最简单、有效而且在实际使用中 很成功的模型，其性能可以与神经网络、决策树相媲美，甚至在某些场合优于其 它模型。朴素b a y e s i a n ( n b ：n a i v eb a y e s ) 模型描述如图2 1 所示，设有变量集合 u = a l ，a 2 ，a n ，c ，其中a l ，a 2 ，a n 是实例的属性变量，c 是取m 个值的 类变量。假设所有的属性都条件独立于类变量c ，即每一个属性变量都以类变量 作为唯一的父节点，就得到朴素b a y e s i a n 模型。 图2 1 朴素b a y e s i a n 模型 朴素b a y e s i a n 模型假定特征向量的各分量间相对于决策变量是相对独立的，也 就是说各个变量独立地作用于决策变量，尽管这一假定在一定程度上限制了朴素 b a y e s i a n 分类模型的适用范围，但在实际应用中，这种假设大大降低了b a y e s i a n 网络构建的复杂性，简化所需的计算，且具有较高的精确度。 s a s k a t c h e w a n 大学的y a o w a n g 等人利用朴素b a y e s i a n 网络来建立p 2 p 网络信任 模型【1 9 】【2 0 1 。每个p e e r 为所有与其交互过的p e e r 建立一个b a y e s i a n 网络。通过这个网 络，请求者可根据自己关心的内容，计算服务提供者的可信概率。每种概率表达 浙江大学硕士学位论文第2 章相关问题研究 t p e e r 在某一方面的可信度。该算法的特点在于以信任的概率值作为节点的属 性。该模型中信任被分为两类：一类是基于文件提供者自身宣告的文件信息内容 的质量和传送速度能力的可信度，另一类是进行评估推荐的其他节点可靠性的信 任。此外，信任值被划分为两种值：满意( + 1 ) 和不满意( 1 ) 。根据以上定义的 属性，使用b a y e s i a n 规划来表示评估节点和文件提供者间的信任值，并给出了一 个根据其他节点的推荐来计算某一节点信任值的迭代公式，如公式2 1 ： 一紫川学z g ，帅，川“踯， 其中r , j 为资源请求节点f 对服务节点的信任度，k 为曾经交互过并且可信的 节点数，t r , ，为第f 个节点对z 的信任度，为第，个节点对，的信任度，g 为未曾 交互过的节点个数，f 乞，为第z 个节点对歹的信任度，嵋，心为权重。由两部分 组成，前一部分是可信确定值，另一部分为未知值，具有不确定因素，即该值是 可变化的。该模型使用b a y e s i a n 公式的先验概率理论来预测一个节点将来行为的 信誉，而这一预测的前提是基于与该节点有过历史交互记录的其他节点进行评估 的概率值。 朴素b a y e s i a n 预测模型清晰直观，易于发现数据间的因果关系；综合了先验信 息和后验信息，能有效地避