（计算机系统结构专业论文）对等网络信息检索中若干关键问题研究.pdf

中请上海交通大学博士学位论文 摘要 对等网络信息检索中若干关键问题研究 摘要 近年来对等网络( p e e r t o p e e rn e t w o r k ，简称p 2 p ) 发展迅速，在文件共享、 普及计算、协同工作、搜索引擎以及广域网络存储等方面有了广泛的应用。但随 着对等网络规模的不断扩大，目前p 2 p 网络中文件级的资源共享因其资源划分粒 度太大而造成共享资源利用率较低，已经不能够满足人们的对资源利用的需求 了，因此如何高效率、深层次地利用对等网络中的资源已经成为急需解决的问题。 在分析了计算模式和资源利用发展趋势的基础上，本文提出了“对等网络挖 掘”( p 2 pm i n i n g ，简称p m i n i n g 或p 2 p 挖掘) 的概念，并对其主要内容“对等 刚络信息检索”( p 2 pi n f o r m a t i o nr e t r i e v a l ，简称p i r ) 作了进一步研究。 在深入研究信息检索和数据挖掘理论的基础上，结合对等计算的基本特点，提出 了对等网络计算的文件共享和信息检索的框架模型，并针对该模型中的各个层次 所涉及的关键问题进行了深入研究，具体有o v e r l a y 层路由优化，文档层中的文 档分类以及关键词发布，用户模式层中的用户查询等，我们分别提出了改进算法， 用以解决对等网络信息检索中存在的路由效率低，发布不合理，检索效果差等问 题。 本文的创新性主要体现在以下几个方面： 1 提出了“对等网络文件共享和信息检索系统框架模型( p f s i r f m ) ”，并对其 进行了数学分析，指出了对等网络研究中主要研究切入点的理论依据。该框 架模型将对等网络分为四个层次，分别为：物理网络层、对等网络o v e r l a y 层、文档层和用户模式层，这样将问题分解可以清楚地发现各自层内的不足 和层间的不协调，为对等网络的进一步研究指明方向。 2 在框架模型中的o v e r l a y 层，针对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 非 满环情况下，提出了对f i n g e r 表进行重新构造的方法，实验表明，该重构 有效地提高了o v e r l a y 层的路出效率。 3 在文档层，对文档分类后发布和用户模式确定所涉及到的分类问题进行了深 入研究：在已有文本分类理论和实践的基础上，为了进一步提高分类器精度， 首先提出r 基于结构损失最小化的支持矢量机模型( 简称为s l m b s v m 模型) ， 然后利用分类器融合的思想提出了一种多类别的m s i m b s v m k n n 文档分类算 法，该分类算法有效地提高了文本分类的精度， 4 在关键词间关系发现方面，提出了关键词阃关联性发现的概率算法和用关联 挖掘发现关键词频繁关联项的挖掘算法，并在此基础上提出了基于关键词 闻关系的关键词集查询系统( k r b k $ s ) ，该系统有效地克服了单关键词发布 算法查询开销过大和多关键同集合发布算法发布量太大的不足，从而有效地 改善了对等网络信息检索的发布效率和检索效率。 5 定义了反映用户偏好的用户模式树，根据用户模式树之间的近似性来判断用 户模式之间的近似陡，进而构造用户社区，并提出了基于社区的信息检索算 法( c b s a 算法) ，该算法有效地减少了检索时的网络带宽消耗，缩短了检索 的啊应时间，提高了检索效果。 关键词：对等网络，信息检索，o v e r l a y 拓扑，路由，文本分类，用户模式 i i 申请上) 每交通太学博士学值论文 r e s e a r c h o ns e v e r a lk e yp r o b l e m so f i n f o r m a t i o nr e t r i e v a li np e e r t o p e e r n e t w o r k 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 to ft h e p e e r t o - p e e r ( p 2 p ) t e c h n o l o g yi nr e c e n t y e a r s ，p 2 pn e t w o r ki sh a v i n gb e e nw i d e l ya p p l i e di ni n f o r m a t i o nr e s o u r c e s h a r i n g ， p e r v a s i v ec o m p u t i n g ，c o o r d i n a t e dw o r k ，s e a r c he n g i n e ，w i d e a r e an e t w o r ks t o r a g e r e s p e c t s h o w e v e r ，w i t hi n c r e a s i n ge n l a r g e m e n to fp 2 pn e t w o ni ns i z e ，f i l e - s h a r i n g l e v e la p p l i c a t i o n sd o n tm e e tf a rf r o mp e o p l e sd e m a n d so fu t i l i z a t i o no fr e s o u r c e sf o r t h er e l a t i v e l yl o wu t i l i z a t i o nr a t eo ff i l e l e v e li n f o r m a t i o ns h a r i n g t h e r e f o r e ，h o wt o m a k ef u r t h e ra n dm o r ee f f i c i e n tu s eo fr e s o u r c e si np 2 pn e t w o r kh a v ea l r e a d yb e c o m e t h eu r g e n tp r o b l e mt ob es o l v e d b a s e do na n a l y s e so nt h ed e v e l o p m e n to fc o m p u t i n gm o d ea n dr e s o l l r e es h a r i n g , t h ep a p e rp u t sf o r w a r dac o n c e p to fp 2 p m i n i n g ( p m i n i n g ) a n dh a saf u r t h e rs t u d yo n i t sm a i nc o n t e n t ，a l s on a m e da st h ep 2 pi n f o r m a t i o nr e t r i e v a l ( p i r 、o nt h eb a s i so f f u r t h e ri n v e s t i g a t i n gt h e o r yo fi n f o r m a t i o nr e t r i e v a la n dd a t am i n i n g ，w e ，c o m b i n i n g b a s i cc h a r a c t e r i s t i c so fp 2 pn e t w o r k ，p u tf o r w a r dt h ef r a m em o d e lo ff i l es h a r i n ga n d i n f o r m a t i o nr e t r i e v a l i np 2 pn e t w o r k ，g i v eaf u r t h e rr e s e a r c ho nk e yt e c h n o l o g i e s i n v o l v e di nt h et h r e el a y e r si nt h ef r a m em o d e ：t h er o u t e sl a y e ro fo v e r l a y ，t h e d o c u m e n tl a y e r , u s e rm o d el a y e r ，a n dp r o p o s e di m p r o v i n ga l g o r i t h m sr e s p e c t i v e l yt o i m p r o v et h er o u t ee f f i c i e n c yo ft h ep 2 pn e t w o r ki n f o r m a t i o nr e t r i e v a l ，t h ek e y w o r d s p u b l i c a t i o n ( i n d e x ) e f f i c i e n c y ，a n dq u a l i t yo f t h er e t r i e v e dr e s u l t s ， t h em a i ni n r t o v a t i o n so f t h i sd i s s e r t a t i o na r ea sf o l i o w s ： 1 p r o p o s e dt h es y s t e m a t i cf r a m em o d e lo ff i l es h a r i n ga n di n f o r m a t i o nr e t r i e v a lo f p 2 pn e t w o r k ，g a v ed e t a i l e dm a t h e m a t i c sa n a l y s e s ，a n dp o i n t e do u tp 2 pn e t w o r k r e s e a r c h st h e o r e t i c a lf o u n d a t i o n t h ep 2 pn e t w o r ki sd i v i d e di n t of o u r1 e v e l si u l i i 申请上海交通大学博士学位论丈 a b s l r a c t t h ef r a m em o d e l ，i n c l u d i n g ：p h y s i c a li n t e r n e tl a y e r ，o v e r l a yl a y e r ，d o c u m e n t l a y e ra n du s e rm o d el a y e rt h i sm o d e lm a yh e l pu sc l e a r l yd i s c o v e re x i s t i n g q u e s t i o n so fi n n e r - l a y e r sa n dm i s m a t c hb e t w e e nl a y e r s ，a n dl e a dt ow h e r et h e f u r t h e rr e s e a r c ho fp 2 pn e t w o r kw i l lg o 2 a st oo v e r l a yl a y e ri nt h ep 2 pf r a m em o d e l ，w eh a v ec a r r i e do n i n d e p t h a n a l y s e st oc h o r dp r o t o c o l ：a tf i r s tw cp r o p o s e dt h ef o r m a l i z a t i o no fc h o r di n c a s eo ff u l lr i n g ，w h i c hm a k e st h e r o u t i n gp r o c e d u r ei n t oal i m i t e dl i n e a r e x p r e s s i o nq u e s t i o no fo n ei n t e g e r t h e nw ea n a l y z e da n dp r o p o s e do p t i m u m s t r u c t u r eo fp e e r sf i n g e rt a b l ei nf u l lc h o r d ，a n dp r o v e dt h r e e - t i m e ss t r u c t u r ei s o p t i m u mf i n g e rt a b l ei nc a s eo ff u l lr i n g ；s e c o n d l y , i nt h ec a s eo fn o n f u l lr i n go f c h o r d ，w ea l s oh a v ep r o p o s e dt h es e v e r a lr e f o r m u l a t i o n so ft h ef i n g e rt a b l et o i m p r o v e r o u t ee f f i c i e n c yo fo v e r l a yl a y e r 3 i nd o c u m e n tl a y e ro ft h em o d e l ，t e x tc l a s s i f i c a t i o nq u e s t i o ni n v o l v e di np 2 p d o c u m e n tp u b l i c a t i o na n du s e rm o d eh a sb e e nf u r t h e rs t u d i e d b a s e do nt h e e x i s t i n gt h e o r y a n dp r a c t i c eo ft e x t c l a s s i f i c a t i o n ，w ep r o p o s e da t f i r s t s l m b s v mm o d e lt oi m p r o v et h ep r e c i s i o no ft h ec l a s s i f i c a t i o nf t l r t h e r ，a n d t h e no nt h eb a s e so ft h et h o u g h to fm e r g i n go ft h ed i f f e r e n tc l a s s i f i c a t i o n a l g o r i t h m s ，p r o p o s e d ak i n do fc l a s s i f i c a t i o n a l g o r i t h m s f o rm u l t i c l a s s ： m s l m b s v m - k n n ， w h i c h e f f e c t i v e l y i m p r o v e sp r e c i s i o n o f t e x t c l a s s i f i c a t i o n 4 p r o p o s e dt h ep r o b a b i l i t ya l g o r i t h ma n da s s o c i a t i n gm i n i n ga l g o r i t h m i n d i s c o v e r i n gr e l a t i o n s h i pa m o n gk e y w o r d s t o i m p r o v et h ee f f i c i e n c y o f p u b l i c a t i o n ，a n db a s e do nq u e r yk e y w o r d sr e l a t i o n s h i p ，w ea l s op r o p o s e d k e y w o r d s r e l a t i o n s h i p b a s e d k e y w o f d s s e t s y s t e m( k r b k s s ) ， w h i c h o v e r c o m e st h eq u e s t i o n so fh e a v yq u e r yo v e r l o a do fs i n g l ek e y w o r da l g o r i t h m a n dt h eh u g ep u b l i c a t i o nm e s s a g e so fm u l t i k e y w o r da l g o r i t h ma n de f f i c i e n t l y i m p r o v e st h ep u b l i c a t i o nc o s t sa n dq u e r y c o s t s ， 5 w eh a v ed e f i n e dt h eu s e rm o d et r e er e f l e c t i n gu s e r si n t e r e s t i n g ，j u d g e dt h e s i m i l a r i t yb e t w e e nu s e r sa c c o r d i n gt ot h es i m i l a r i t yo ft h eu s e rm o d eg e e 5 ，a n d v 申请上海交通大学博士学位论文 t h e np r o p o s e dt h ea l g o r i t h mo fi n f o r m a t i o nr e t r i e v a lb a s e do nc o m m u n i t y ， w h i c he f f e c t i v e l yr e d u c e sc o n s u m p t i o no fb a n d w i d t h ，s h o r t e n st h er e s p o n s et i m e a n di m p r o v e st h eq u a l i t yo fr e s u l t s k e yw o r d s ：p e e r t o p e e rn e t w o r k ，i n f o r m a t i o nr e t r i e v a l ，o v e r l a yt o p o l o g y r o u t i n g ，t e x tc l a s s i f i c a t i o n ，u s e rm o d e v 一 上海交通大学学位论文答辩决议书 所在学科 申请 者 张亮 ( 专业) 计算机系统结构 ! 论文题目 对等网络信息检索中若干关键问题研究 1 答辩日期 2 0 0 5 0 3 - 1 6 地点上海交通大学新建楼 答辩委员会成员 姓 名单位 职称签- 名 高传善复旦大学 教授 抛易 白英彩 上海交通大学教授 向剩 顾君忠 华东师范大学教授 泓融 陈家训j东华大学教授 博爹p 陈克非 上海交通大学教授 俐 j 许谙丰口袂议 该论文对对等网络信息检索作了深入研究，提出了对等网络计算的文件共享和信息检索 和分层改进算法，改善了对等网络信息检索中存在的路由效率低，发布不合理，检索效果差 l ：作具有重要的理论意义和应用价值。该论文的主要工作及创新性在于：提出了“对等网络 信息检索系统框架模型”，该框架模型表明了各自层内的不足和层间的不协调，为对等网络 切入点提供了依据：提出井证明了c h o r d 协议在满环情况下的最优路由表结构以及非满环情 的重构，有效地提高了o v e r l a y 层内的路由效率；提出了基于结构损失最小化的支持矢量机 合的分类模型，然后利用用户模式树构造用户社区，提出了基于杜区的信息检索算法( c b s j 算法有效地减少了检索时的网络带宽消耗，缩短了检索的响应时间，提高了检索效果；提出 关联性发现的概率算法和用关联挖掘发现关键词频繁关联项的挖掘算法，并在此基础上，提 键词闻芙系的关键词集查询系统，改善了对等网络信息检索的发布效率和检索效率。 论文叙述清楚，条理清晰，反映作者具有坚实宽广的理论基础，掌握了系统深入的专业 i 蚰蚶川驯1 心1 4 - j i 百z * 二苫二井；p t 坤月菪通过罾 主泡 年月日 申请上海交迫走学博士学位论五 中英支图表索 本文图索弓 图卜1 对等网络的分类， 图i - 2 计算模式数据存储形式一信息挖掘的瘸化图 图l - 3 论文的组织和结构， 图2 1 基于文件共享的p 2 p 框架模型，、 图2 2 基于全文信息检索的p 2 p 框架模型，一， 图3 1c h o r d 的逻辑环及其f i n g e r 表项 圉3 2 拥有三个节点0 、l 和3 的c h o r d 标识环， 图3 3 三倍数最优说明示意图， 图3 - 4 三倍数路由表满环c h o r d 路由过程 图3 5 标准c h o r d 和b i - o p t - c h o r d 的路由跳数比较图 圈3 - 6 不同重构方法下的平均路由跳数曲线 ， 图3 7 不同k 值下的路由平均跳数曲线， 图4 - 1 向量空间模型， 图4 2 自动丈本分类流程， 图4 3 支持矢量机产生的线形决蓑面， 图4 - 4 支持矢量机从原空间到特征空问的映射关系， 图4 5 泛化p o s e r r o r r a t e 结果， 图4 - 6 泛化n e g e r r o r r a t e 结果， 图4 - 7 随n 和c 的取值不同s l m b - s c m 的分类决策面变化图 图4 8 训练样本数量对k n n ，s v m 和m s l m b s v m k n n 的分类精度的影响 图5 1p 2 f 网络中的倒排索引， ， 图5 - 2 使用b l o o mf i l t e r 计算组合查询a nb ， 圈5 - 3 构建k r b k s s 的过程， 图5 4k r b k s s 系统架构， 图5 5 不同发布算法下发布量的变化关系图， 图5 5 不同发布算法下每文档索引量和索引百分率的变化关系匿 圈5 7 不同索引关键词个数下传输的字节量，。 图6 一1 分类层次树，- 图6 - 2 用户模式树， 图6 3 两用户拥有同类共享丈件时的用户模式树， 图6 - 4 查询带宽比较， 图6 - 5 查询时间比较，- 图6 - 5 累计收到的命中消息数 袅1 表 表 试) 表 试) 本文表格索弓 - l 各种p 2 p 路由算法的缝合性能比较， 4 - is l m b s 啪算法的泛化错误率和整体泛化损失 4 2 对于网页分类k nn ，s v m 和k s l m b sv ms 4 3 对于网页分类kn n ，sv m 和k s l m b sv ms 1 0 ，4 9 算法分类精度比较( 开放；刚 72 算法分类精度比较( 封闭测 ，3 o加儿扣”钾铊盯盯酏似趴跎的鹊蚴蛇 ! 童圭查墨翌查兰堡圭兰竺堡圭 墨墨璺叁查! ! i n d e xo ff i g u r e s f i g 1 - 1t h ec l a s s i f i c a t i o no fp e e r - t o - p e e rn e t w o r k s f i g i 一2e v o l u t i o no f c o m p u t i n gm o d e s d a t as t o r a g ef o r m sa n di n f o r m a t i o nm i n i n g ， f i g 1 - 3 t h eo r g a n i z a t i o na n ds t r u c t u r eo f t h ed i s s e r t a t i o n 。，。， f i g 2 1f i l e - s h a r i n g - b a s e dp 2 p a r c h i t e c t u r e m o d e l f i g 2 - 2l n f o n - a a t i o n - r e t r i e v a l - b a s e dp 2 pa r c h i t e c t u r em o d e l f i g 3 - 1t h el o g i c a lr i n ga n dt h ef i n g e rt a b l ei t e mo f t h ec h o r da l g o r i t h m f i g 3 - 2t h ei d e n t i t yc i r c l eo fc h o r dw i t ht h r e en o d e sw h o s ei d e n t i t yi s0 ，l ，3s e p a r a t e l y f i g 3 - 3 t h r e e t i m e so p t i m u mp r o v e f i g u r e ， f i g 3 - 4r o u t i n gp r o c e d u r e i n3 - t i m e s c h o r d ，。，、 f i g 3 - 5c o m p a r i s o no f h o p s 洒t r a d i t i o n a ic h o r da n db o p t - c h o r d ， f i g3 - 6 c u r v e so f a v g h o p sh u m i n t h e f i v er e f o r m u l a t i o no f c h o r d ， f i g 3 - 7 c u r v e o f a v g h o p s i n t h e d i f f e r e n t kv a l u e ， f i g4 - lv e c t o rs p a c e m o d e l ， f i g 4 - 2p r o c e s so f a u t o m a t i c t e x t c l a s s i f i c a t i o n ， f i g 4 - 3 d e c i s i o nh y p e r - p l a n eg e n e r a t e db ya l i n e a rs v i v i ，、 f i g4 - 4 m a p p i n g f r o m i n p u t s p a c e t o f e a t u r e s p a c e 、。、，、 f i g 4 - 5 r e s u l t o f g e n e r a l i z i n gp o se r r o rr a t e ， f i g 4 - 6r e s u l to f g e n e r a l i z i n g n e g _ e r r o r r a t e ， f i g 4 - 7s l m b s v mc l a s s i f i c a t i o nd e c i s i o nh y p e r - p l a n ec h a n g ew i t hd i f f e r e n tna n dc f i g 4 - 8 a ni l l u s t r a t i o no f t h ee f f e c t so f t r a i n i n gs a m p l en u m b e r ， f i g 5 - 1d i s t r i b u t i n ga ni n v e r t e di n d e xa c r o s sap e e r - t o p e e rn e t w o r k ， f i g 5 - 2 c o m p u t i n gc o m b i n a t i o nq u e r y a n bu s i n gb l o o m f i l t e r ，。， f i g5 - 3 t h ep r o c e s so f c o n s t r u c t i n g k r b k s s ， f i g5 - 4s y s t e m a r c h i t e c t u r e o f k r b k s s 、 f i g 5 - 5 n u m b e ro fi n d e xe n t i t i e sg e n e r a t e di nd i f f e r e n ti n d e x i n gs c h e m e s f i g 5 - 6c u m u l a t i v ed i s t r i b u t i o ni nd i f f e r e n ti n d e x i n gs c h e m e s ， ， f i g5 - 7m e a nk b 订a n s f e r r e di nd i f f e r e n ti n d e x i n gs c h e m e s f i g 6 - 1a t r e eo f c l a s s i f i c a t i o n ，。，。；，。，。 f i g 6 - 2u s e r m o d e t r e eo f au s e r f i g 6 - 3u s e rm o d et r e e so ft w ou s e r sj u s th a v i n gs a m e c l a s sf i l e s f i g 6 - 4c o m p a r i s o no f q u e r yb a n d w i d t hi nd i f f e r e n ta l g o r i t h m ， f i g6 5c o m p a r i s o no f q u e r yt i m ei nd i f f e r e n ta l g o r i t h m - f i g 6 6n u m b e ro f q u e r y h i tm e s s a g e sr e c e i v e dw i t ht i m ep a s s i n g ， 5 1 5 1 7 2 0 2 1 3 9 3 9 4 3 4 9 5 2 5 3 5 4 5 6 5 7 6 3 6 3 6 7 6 7 6 8 7 4 7 8 8 t 8 2 8 6 8 9 8 9 9 0 9 2 9 4 9 7 1 0 3 1 0 4 1 0 4 申请上海交通大学博士学位论丈中其丈圈表索 i n d e xo ft a b l e s t a b1 1p e r f o r m a n c ec o m p a r i s o no f d i f f e r e n tp 2 ps y s t e m s ，1 0 t a b4 - 1 ：g e n e r a l i z a t i o ne r r o rr a t e s t o t a lg e n e r a l i z a t i o nl o s sr e s u l t so fs l m b - s v m 6 9 t a b4 - 2c o m p a r i s o no f c l a s s i f i c a t i o np r e c i s i o nf o rk n n ，s v ma n dk s l m b s v m - k n n ( o p e n t e s t ) ，7 2 t a b 4 - 3 c o m p a r i s o no fc l a s s i f i c a t i o np r e c i s i o n f o rk n n ，s v ma n dk - s l m b s v mk n n ( c l o s e t e s t ) ，7 3 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： ；挈0 、 j 盘统 日期：厂年；月6 日 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上方框内打“4 ”) 、 学位论文作者签名：i 圳 日期：册3 月，6 日 辨挪豁骗 日期：年月日 由请上海交通犬学博士学位论文第一章绪论 1 1 对等网络的概述 第一章绪论 如今，i n t e r n e t 正面临着场革命。这场革命正在改变i n t e r n e t 的一个基 本特性，这就是网络的终端( 或者说客户端) 如桌面电脑，移动电话，p d a 等正 要求一个更优越的网络地位以结束服务器为主导的i n t e r n e t 。这就是 p e e r t o p e e r 计算( 简称为p 2 p 计算) 。 p 2 p 计算技术出现的目的就是希望充分利用互联网中所蕴含的潜在计算资 源。p 2 p 中文称为对等网络，是指分布式系统中的各个节点是逻辑对等的，与目 前互连网上比较流行的c s 计算模型不同的是：p 2 p 计算模型中不再区别服务器 以及客户端，系统中的各个节点之间可以直接进行数据通信而不需要通过中间的 服务器。和传统的c l i e n t s e r v e r 网络相比，对等网络具有扩展性好、容错性好、 负载均衡和整体性能高等优点。 对等网络的以下特征使之与传统系统相区别： ( 1 ) 节点之间通过直接交互共享资源； ( 2 ) 资源分布在各个节点中，而不是集中在一个服务器中进行管理； ( 3 ) 节点具有动态性和自治性： ( 4 ) 纯粹的p 2 p 系统没有集中控制机制。系统的各节点运行的p 2 p 系统软 件功能相同，各节点之间交互对称。 1 2p 2 p 的定义 i n t e l p 2 p w2 0 0 1 将p 2 p 计算定义为“通过系统间的直接交换所达成的计算 机资源与信息的共享”，这些资源与服务包括信息交换、处理器时钟、缓存和磁 盘空间等。p 2 p 计算利用了已有的桌面计算能力和网络连接，将这些资源和服务 有效组织，通过更强大的集合能力来完成任务。而i b m k a r l2 0 0 2 为p 2 p 下了 如下定义：p 2 p 系统由若干互联协作的计算器构成，且至少具有如下特征之一： 系统依存于边缘化( 非中央式服务器) 设备的主动协作每个成员直接从其它成 员而不是从服务器的参与中受益；系统中成员同时扮演服务器与客户机的角色： 申请上海交通大学博士学位论文第一章绪论 系统应用的用户能够意识到彼此的存在，构成一个虚拟或实际的群体。p 2 p 将网 络抽象成由主机和主机间的应用层链路组成，把网络计算模式从集中式引向分布 式，网络应用的核心从中央服务器向网络边缘的终端设备扩散。 为了方便叙述，我们称对等网络中的每个p e e r 为个节点，并把由p e e r 所组成的逻辑网络成为叠加网络( o v e r l a yn e t w o r k ) 。 1 3p 2 p 网络的应用领域 p 2 p 计算引导网络计算模式从集中式向分布式偏移，也就是说网络应用的核 心从中央服务器向网络边缘的终端设备扩散。这使人们在i n t e r n e t 上的共享行 为被提到了一个更高的层次，使人们以更主动的方式参与到网络中去，每个人都 能为网络的资源和功能扩展做出自己的贡献。 从目前的情况来看，p 2 p 计算主要应用在文件共享、普及计算、协同工作、 搜索引擎以及广域网络存储等方面。 1 3 i 文件共享 文件共享是p 2 p 最为流行的应用也是最为典型的应用之一，也是p 2 p 技术革 命的闪光点。n a p s t e r n a p s1 9 9 9 是提供给用户在互联网上共享m p 3 音乐文件的 p 2 p 应用，与传统的音乐共享技术不同的是n a p s t e r 把音乐文件存储在客户节点 上而不是存储在服务器节点上，中心服务器上存储的仅仅是文件的索引信息，用 户之间可以直接共享、传输音乐文件而不需要通过中心索引服务器。采用这种方 式来共享信息资源可以更加充分的利用网络中的带宽资源，从而提高了系统数据 通信的效率。n a p sc e r n a p s1 9 9 9 、o n u t e l l a g n u t2 0 0 0 和p r e e n e r c l a r2 0 0 0 等文件共享系统被认为是p 2 p 领域非常成功的范例。 i 3 2 普及计算 普及计算技术研究的是如何充分利用网络中各种各样的计算资源来共同完 成大规模的计算任务。此类应用属于计算型资源共享，g r i d g r i d2 0 0 2 和 s e t i h o m e 是该类型应用的典型代表。s e t l h o m e s e t l 2 0 0 2 是b e r k e l e y 大学 启动的普及计算的研究项目，该项目是利用该大学的空间科学实验室开发的屏幕 中请上海交通大学博士学位论文 第一章绪论 保护程序来使用计算机的空闲机时，该屏幕保护程序在运行时分析在外星系文明 研究项目中所获得的无线电信号，程序运行节点从中心服务器节点下载数据后进 行计算然后再将计算结果上载到该实验室的中心服务器上，因为不是完全的p 2 p 计算模式，所以节点之间不能直接利用彼此计算的数据。 1 3 3 协同工作 协同工作是指多个用户之间利用网络中的协同计算平台互相协同来共同完 成计算任务，共享信息资源等。g r o o v e g r 0 02 0 0 2 是基于i n t e r n e t 的p 2 p 协同 应用软件的典型代表，