非结构的_P_2P_网络拓扑模型

计算机工程与应用2 0 0 6 . 0 5 非结构的 P 2 P网络拓扑模型 曹佳张国清鲁士文 ( 中国科学院计算技术研究所, 北京1 0 0 0 8 0) E - m a i l:j i a c a o i c t . a c . c n 摘要在P 2 P系统中, 物理主机的组网比较灵活。由于网络拓扑直接影响了网络的性能, 所以构建什么样的对等网络 拓扑一直备受关注。论文讨论几种常用的非结构对等网络拓扑模型。非结构型的对等网络适合信息发布类型的应用, 其 组网和维护相对简单。研究发现, 虽然目前有很多构建非结构型的对等网络的方案, 但是这些方案最终构建的对等网络 基本可以归为三种类型的拓扑模型, 随机图论模型(E r d 5s - R n y i) ,k规则随机图和随机有向图。论文分别描述了这三种 拓扑模型的度分布、 连通性和直径, 以及一些相关的典型应用。 关键词对等网络随机图直径 文章编号1 0 0 2 - 8 3 3 1 -(2 0 0 6)0 5 - 0 0 2 3 - 0 3文献标识码A中图分类号T P 3 9 3 U n s t r u c t u r eP 2 PN e t w o r kT o p o l o g yMo d e l s C a oJ i a Z h a n gG u o q i n g L uS h i w e n (I n s t i t u t eo f C o m p u t i n gT e c h n o l o g y,C h i n e s eA c a d e m yo f S c i e n c e s,B e i j i n g1 0 0 0 8 0) A b s t r a c t:P 2 Pn e t w o r ki saf l e x i b l en e t w o r k . A sw ek n o w,t h en e t w o r kt o p o l o g yi n f l u e n c e st h ep e r f o r m a n c eo ft h en e t - w o r kd i r e c t l y,s ot h eP 2 Pn e t w o r kt o p o l o g yi sv e r yi m p o r t a n tf o rt h eq u a l i t yo ft h en e t w o r k . I nt h i sa r t i c l ew ed e s c r i b e u n s t r u c t u r e dm o d e l s . Wef i n dt h a tt h o u g ht h e r ea r ev a r i o u sk i n d so fp o l i c i e st ob u i l du n s t r u c t u r e dP 2 Pn e t w o r k s,t h e s e n e t w o r k sc a nb ec l a s s i f yi n t ot h r e em o d e l sw h i c ha r eE r d 5s - R n y im o d e l,k - r e g u l a rr a n d o m g r a p ha n dr a n d o m d i r e c t e d g r a p h . T h ed i s t r i b u t i o no ft h en o d a ld e g r e e,c o n n e c t i v i t ya n dd i a m e t e ri so u rm a i nc o n c e r n . A n ds o m et y p i c a la p p l i c a t i o n s a r em e n t i o n e dw i t hr e s p e c t t oe a c hm o d e l . K e y w o r d s:P 2 Pn e t w o r k,r a n d o m g r a p h,d i a m e t e r 基金项目: 下一代互联网中日I P v 6合作项目:I P v 6主机和智能终端等接入系统关键技术开发 作者简介: 曹佳(1 9 7 8 -) , 女, 博士研究生, 主要研究领域为组播路由算法及安全技术。张国清(1 9 6 5 -) , 男, 副研, 硕导, 主要研究领域为计算机网络 与通讯。鲁士文(1 9 4 4 -) , 男, 博导, 主要研究领域为计算机网络协议。 1引言 在P 2 P系统中,设计者可以根据不同的应用需求组建不 同拓扑的对等网络(P 2 P网络) 。 一个 “合适” 的网络拓扑可以为 应用提供更好的支持, 例如规则的拓扑结构有利于根据主机在 拓扑网络中的位置进行基于内容的索引; 而非结构的随机网络 的构建比较简单随意, 所以适合于信息发布、 即时通讯等主机 随时加入退出的情况。因此理解对等网络的拓扑对P 2 P系统 的研究有重要的意义。 参与P 2 P通讯的主机通常不太稳定,研究人员发现在 G n u t e l l a和N a p s t e r中,大约一半的参与者会在一个小时内随 时可能加入或者退出通讯 7 。 为此, 人们通常采用简单的组网策 略来适应动态情况, 那么这是否意味着形成的网络拓扑也不稳 定?我们发现无论采用何种策略, 最终都会保证网络的一些静 态几何特征相对稳定, 例如, 结点度浮动在某个小范围内, 网络 的连通性不变, 网络直径被约束在一定的范围内。这些方案最 终构建的对等网络基本可以归为三种类型的拓扑模型: 随机图 论模型(E r d5s - R n y i) 、k规则随机图和随机有向图。本文主要 讨论这三类模型。 我们通过简单的映射将对等网络抽象成一个图论模型G (V,E) , 结点表示主机, 边表示主机之间的路径。| V | = N表示结 点个数;k i表示结点i 的度; 如果图中所有结点的度相同, 则用 k来表示;D表示图的直径。本文主要关注度分布、 连通性和直 径三个几何特征。(1) 度分布: 每个结点都有一些邻接边, 邻接 边个数等于这个结点的度。 度分布用来描述具有相同度的结点 的数目的分布。 结点的度与结点的传输负载和存储负载等工作 负荷成正比; (2) 连通性: 如果一个对等网络连通, 那么说明网 络中的任意两个结点可以相互通讯。 (3) 直径: 表示图中任意两 个结点之间距离的最大值, 描述网络的传输时间, 这对即时通 讯和信息的快速发布具有很重要的意义, 对网络的吞吐量也有 大的影响。 2 E r d 5s - R n y i模型 几乎没有任何P 2 P系统可以直接采用E r d5sR n y i模型, 但是E r d 5sR n y i模型是最基础的随机图模型, 因此我们还是 对其进行一些阐述。在E r d5sR n y i模型中, 主要有两种生成 方案G n,p和GM. Gn,p表示把n个孤立的结点组成n(n - 1)/ 2对 结点对, 以概率p来随机选择每对结点, 选中的结点对需要互 连;GM表示随机地从这些结点对中选 M对结点进行互连。在 P 2 P应用中通常希望每个结点可以尽可能独立地选取其他结 点, 因此下面主要阐述G n,p的特性。 (1)Gn,p的结点度的分布符合 = n p的泊松分布 在G n,p中结点i的度ki满足参数为n - 1和p的二项式分 2 3 2 0 0 6 . 0 5计算机工程与应用 布, 即P(K i= k )= C k n - 1p k( 1 - p) n - 1 - k 。设 k表示度为k的结点的个 数的数学期望值, 则 k= n C k n - 1p k( 1 - p) n - 1 - k ; 设 Xk表示度为k的 结点的个数, 那么P(X k= r )= e - k r k r! 。具体证明请参考 1 。假设 p 2 ,Gn,p的直径: D l o g( 2(1 + ) 1 - 2 c“ - n l o g n) l o g(n p) + 关于G n,p的直径问题在文献 3 中有详细的研究, 这里仅仅 列举了对于大规模的P 2 P应用比较适用的一个结论。 值得一提的是幂律(p o w e r - l a w) 现象。G n u t e l l a网络是一个 呈幂律特征的随机网络 1 2 。之所以产生幂律现象的原因是结点 在互连时出现了某种偏好, 即互连概率的取值不均, 例如新加 入的结点偏向于和度大的结点连接, 导致某些结点的度越来越 大“r i c h - g e t - r i c h e r” , 需要承载的P 2 P流也越大。如果这个 结点的能力足以负载这些P 2 P流并且不出故障, 那么对整个系 统的性能很好。 但是在对等网络中, 考虑到结点的稳定性, 通常 需要某种机制来避免幂律情况。 文章 2 指出在构建对等网络的 时候, 根据结点的能力来限制结点的度, 从而使得在这个对等 网络上进行某种路由时, 即使出现偏好选择, 也不会导致一些 结点的负载过高。 3 k规则随机图 k规则随机图Gk - r e g的主要特点就是每个结点的度固定 为k。 (1 ) 当 3 k 3 l o g n时,Gk - r e g是k连通的。 换句话说, 至少需要从图中删除k条边, 或者k个结点才 能使得这个图分离。 (2 ) 当 k 3, 0时, 有一个整数D满足(k - 1) D( 2 + ) k n l o g n, 此时具有N个结点的Gk - r e g的直径最多为D 1 。 上面的结论等价于D = m i n D | D l o g k - 1( (2 + )k n l o g n) , 其 中 0,k 3。 显然, 当k一定,越接近0, 直径越小。 总之,k的 取值直接影响G k - r e g的连通性和直径。 Gk - r e g在P 2 P系统中得到了广泛的应用。在实际中, 由于大 量结点频繁动态加入退出, 一般不可能严格遵守结点度等于k 的约束.连通性和直径都是单调增的属性 1 , 即随着边数增加, 图的连通概率会增大, 直径有缩小的趋势。 因此, 只要保证结点 的度不小于k, 不会影响上述结论。 (1) 变形一 A r a n e o l a 3 采用了这样一个动态策略的构建对等网络的机 制: 每个新加入的结点至少和k个结点连接, 然后定时按照下 面的方案来修订每个结点的度:如果两个相邻的结点的度都 大于k, 那么把其中一个结点i的k i- k条邻接边删除;如果 一个结点i的两个邻居的度相差至少为2,那么把度较大的结 点的一个邻居点转交给度小的结点。一段时间后,最终大约 9 0 %结点的度为k, 大约1 0 %结点的度为k + 1, 两个相邻结点的 度不同时为k + 1。 (2) 变形二 文献 7 提出了另一种基于G k - r e g的变形机制, 主要用来适 应频繁加入退出的主机结点, 同时保证网络的O(l o g n) 直径。 系 统中有一个中心结点, 中心结点的缓冲区保存部分活跃在图中 的结点。每个新加入的结点和需要新连接的结点, 都会从中心 结点获得适当数目的其它结点, 新加入的结点需要D个, 度小 于D的结点需要补足到D个邻居结点,所以每个结点至少有 D个邻居。当缓冲区的结点被选中足够多的次数后, 当它的度 等于C(C D) 时, 它就退出缓冲区, 成为一个c -结点, 同时至少 要维持一个与缓冲区结点的连接, 使得每个结点都与缓冲区的 结点相连, 从而保证对等网络连通。可以看出每个结点至少有 D,C 个邻居。文献 1 0 指出了D、C等数据的参考值, 分别是中 心结点的缓冲区中保存N/ 4个结点,D = l o g n,C = 3 l o g n + 3。这个 机制虽然保证了连通性和较小的直径, 但是整个系统依赖一个 关键点。 4随机有向图 随机有向图G o u t - k每个结点的出度为k, 入度不限制。 (1) 结点入度独立于结点出度, 且结点入度服从 = k的泊 松分布 4 。 Go u t - k实现简单, 每个结点只需随机选取k个结点, 并且建 立连接。Go u t - k面临着类似于Gn,p同样的幂律问题, 每个新加入 的结点都倾向于选择相对 “好” 的结点, 于是 “好” 结点的入度呈 现出幂律特征。有些结点的入度很大, 那么这些结点被路由到 的可能性就很大, 使得这些结点需要负担繁重的P 2 P数据转发 任务, 性能下降。所以在构建基于G o u t - k的对等网络时需要限制 结点的入度, 控制结点转发P 2 P流的可能性。同样限制入度的 Go u t - k是Go u t - k的特殊情况,Go u t - k的性质没有丢失。 (2 ) 设 $(k,n) 表示从某结点到任意其他结点都有一条 路径的概率, 如果k = l o g n + c, 其中c是一个常数, 那么有l i m n $(k,n)= e - e - c 8 。 这也就说明,k满足(l o g n) 就可以保证Go u t - k的非强连通 性。 虽然无法证明强连通性, 但是本结论表明如果条件满足, 那 么某个结点的信息可以通过对等网络发布给所有的其他结点, 这对P 2 P实际应用很有指导意义。 (3) 假设L(k,n) 表示从某一点到任意结点的最大距离, 当 N = 2 0 1 0 0 0 0 0,k 2 . 4 3 n 0 . 5 6 时,L(k,n)= 2。 关于G o u t - k的直径问题一直没有相应的数学理论。但是我 们推导了从一个节点到任意节点的距离L“当L(k,n)= 2时,k 和n的关系” ,用来说明k和n满足什么样的关系才能使得从 一个节点最多经过2跳就可以连通其它任意节点。 我们采用广度遍历生成树方式来求解L(k,n) 。假设根结 点表示第0层, 根结点的孩子表示第1层, 以此类推; 分别用S i 来替代相应层次的结点集合; 树深度用d e p t h表示;T表示已经 访问过的点集合。具体遍历步骤如下: 随机挑选一个结点i 0,S0= i0 , 此时d e p t h = 0,T = i 0 ; 随机选择i 0的k个邻居结点,S1= i0的k个邻居结点 , 此时d e p t h = 1,T = T + S 1; S 1的结点分别随机选择k个邻居结点,此时d e p t h = 2 , 表 示L已经达到了2,T = T + S 1的结点的k个不属于T的邻居结 点。 如果| T | = n,那么就表示所有的结点都被选到,G o u t - k的 d e p t h = 2, 等价于L(k,n)= 2。于是得到了L(k = 2) 时,k与n的一 2 4 计算机工程与应用2 0 0 6 . 0 5 图1雨滴落地的随机过程 图2 k和N的关系图(d(k,n)= 2) 个关系, 这个关系是通过上述三个步骤描述的, 但是这三个步 骤很难直接用数学模型来求解, 因此我们对问题进行变换。做 法如下: 观察到, 遍历G o u t - k的过程是逐一处理每个结点的过程。如 果把n个结点看作是一个由n个等面积的小方块构成的区域; 把每次随机选择k个结点的过程看作在区域中随机挑选k个 小块的过程, 那么遍历过程十分类似于雨滴落地的过程。给定 一个区域,每一时刻都有一滴雨下落到这个区域的一个小块 中, 表示选中这个小块。 在现实中, 我们知道只要有足够的随机 落下的雨滴, 总可以把地面湿遍, 所以只要选择足够大的k值, 总可以遍历所有的结点。 将一个区域分成等大小的n块, 随机独立地访问m次, 每 访问到一个块就在相应的块上画一个点, 如图1。灰色的部分 表示没有雨滴落下,那么相应的结点在G o u t - k中就是一个只有 出度没有入度的孤立点。 因此问题演变成 “m为多大时, 才能够 以较大概率访问到所有的块” 。 1块无点的概率为p 1=( (n - 1)/ n) m 2块无点的概率为p 2=( (n - 2)/ n) m n - 1块无点的概率为p n - 1=(1 / n) m 全部块都被访问到的概率为P = 1 -(p 1+ p2+ pn - 1) , 只需保 证(p 1+ p2+ pn - 1)0, 就可以保证P 1。由于p1 p2 pn - 1 , 所 以保证(n - 1) p 10就必定有P 1。因此得到: (n - 1)(n - 1 n ) m 0 A r a n e o l a和 7 Go u t - k k 2 . 9 9 7 n 0 . 5 3 1 2% 2 0 n 1 0 0 0 0 0 2B i t T o r r e n t,Y o i d 表1几种常用的非结构对等网络模型 平等的机会和相同的工作负载。文献 2 主张充分利用资源, 能 力越强的结点负担越多的工作。我们认为, 如果一个结点负担 了较多的P 2 P任务, 那么除了它本身的工作负载外, 还消耗了 较大的网络带宽, 这就涉及到计费问题。如果参与P 2 P通讯的 参与者们在现实中是一个利益团体, 例如一个公司的P 2 P视频 会议, 那么采用偏好策略十分有好处, 毕竟可以获得更好的传 输性能; 如果不是, 例如很多彼此未知的网络用户同时收看一 个节目, 那么采用完全公平的策略比较合适。 综上所述, 本文主要针对目前出现的各种构建非结构对等 网络的方案, 从最基本的图论的角度把这些对等网络拓扑归类 成为数不多的几种基本模型, 并对它们进行了一定的描述。 ( 收稿日期:2 0 0 5年9月) 参考文献 1 . BB o l l o b a s,W F u l t o n,AK a t o ke t a l . R a n d o mG r a p h . S e c o n dE d i t i o n M . C a m b r i d g eu n i v e r s i t yp r e s s,2 0 0 1 2 . V V i s h n u m u r t h y,PF r a n c i s . O nR a n d o m N o d eS e l e c t i o ni nP 2 Pa n d O v e r l a yN e t w o r k . M a n u s c r i p t,h t t p:/ / w w w . c s . c o r n e l l . e d u / P e o p l e / f r a n c i s / R a n d S e l e c t i o n 1 9 . p d f . 2 0 0 4 3 . M e l a m e d,RK e i d a r,IA r a n e o l a . AS c a l a b l eR e l i a b l eM u l t i c a s t S y s t e m f o rD y n a m i cE n v i r o n m e n t s C . I n:P r o c e e d i n g so f3 r dI E E E I n t e r n a - t i o n a l S y m p o s i u m o nN e t w o r kC o m p u t i n ga n dA p p l i c a t i o n s,2 0 0 4 4 . C h a oG u i,R o n a l dD D u t t o n . I n - d e g r e eD i s t r i b u t i o ni nR a n d o m D i - g r a p h s C . I n:P r o c e e d i n g so f 3 2 n dI n t e r n a - t i o n a l C o n f e r e n c eo nC o m - b i n a t o r i c sG r a p hT h e o r ya n dC o m p u t i n g,2 0 0 1 - 0 3 5 . C e s u rB a r a n s e l,Wl o d e kD o b o s i e w i c z,P a w e lG b u r z y n - s k i . R o u t i n gi n M u l t i _ h o pP a c k e t S w i t c h i n gN e t w o r k s _G b p sC h a l l e n g e J . I E E EJ o u r - n a l o nN e t w o r k,1 9 9 5;9(3) :3 8 6 1 6 . S y l v i aR a t n a s a m y,P a u l F r a n c i s,M a r kH a n d l e ye t a l . As c a l a b l ec o n - t e n t - a d d r e s s a b l en e t w o r k C . I n:P r o cA C M S I G C O M M 2 0 0 1,2 0 0 1: 1 6 1 1 7 2 7 . G o p a l P a n d u r a n g a n,P r a b h a k a rR a g h a v a n,E l i U p f a l . B u i l d i n gL o w - D i - a m e t e rP e e r - t o - P e e rN e t w o r k J . I E E EJ o u r n a lo nS e l e c t e dA r e a si n C o m m u n i c a t i o n s(J S A C) ,2 0 0 3;2 1(6) :9 9 5 1 0 0 2 8 . M r kJ e l a s i t y,M i k eP r e u “. M a i n t a i n i n gC o n n e c t i v i t yi naS c a l a b l e a n dR o b u s tD i s t r i b u t e dE n v i r o n m e n t C . I n:2 n dI E E E /A C M I n t e r n a - t i o n a lS y m p o s i u m o nC l u s t e rC o m p u t i n ga n dt h eG r i d(C C G R I D 0 2) B e r l i n,G e r m a n y,2 0 0 2 9 . A n t o n yR o w s t r o n,P e t e rD u s c h e lP a s t r y . S c a l a b l e,d e c e n t r a l i z e do b j e c t l o c a t i o na n dr o u t i n gf o rl a r g e - s c a l ep e e r - t o - p e e rs y s t e m s C . I n:M i d - d l e w a r e 2 0 0 1,G e r m a n y,2 0 0 1 1 0 . h t t p:/ / i v . s l i s . i n d i a n a . e d u / s w / i n d e x . h t m l 1 1 . B r a mC o h e n . I n c e n t i v e sB u i l dR o b u s t n e s si nB i t - T o r r e n t . h t t p:/ / w w w . b i t t o r r e n t . c o m 1 2 . M a t e iR,I a m n i t c h iA,F o s t e rP . M a p p i n gt h eG n u t e l l an e t w o r k J . I E E EJ o u r n a l o nI n t e r n e t C o m p u t i n g,2 0 0 2;6(1) :5 0 5 9 1 3 . J o h nWa t r o u s . Q u a n t u m s i m u l a t i o n so fc l a s s i c a lr a n - d o m w a l k sa n d u n d i r e c t e dg r a p hc o n n e c t i v i t y J . J o u r n a l o f C o m p u t e ra n dS y s t e m S c i - e n c e s,2 0 0 1;6 2(2) :3 7 6 3 9 1 1 4 . P a u l F r a n c i sY o i d . E x t e n d i n gt h eI n t e r n e t M u l t i - c a s t A r c h i t e c t u r e R . U n r e f e r e e dr e p o r t,2 0 0 0 - 0 4 ( 上接2 5 页) 5结论与展望 移动A g e n t学习是一种无监督学习方法, 具有其它监督学 习方法所不具有的优点。但是, 在多移动系统中, 移动A g e n t学 习仍然具有局限性, 主要体现在组合爆炸, 隐含全局状态和信 度指派 1 4 等方面, 这些因素都会影响移动A g e n t学习算法的收 敛性。本文提出的移动A g e n t学习算法M M A L, 结合强化学习 技术更适合于非静态的数据分布, 使移动A g e n t能在随机动态 的环境中进行自主、 协作的学习。目前对移动A g e n t学习的研 究才刚刚起步,各种学习规则都是基于移动A g e n t理性假设。 所以,深入研究多移动A g e n t协作系统的工作机理和多移动 A g e n t学习算法复杂度,以及利用概率聚类方法降低移动 A g e n t学习算法对系统资源的要求将是我们下一步的研究方 向。( 收稿日期:2 0 0 5年7月) 参考文献 1 . S u t t o nR,B a r t oA G . R e i n f o r c e m e n tL e a r n i n g:A nI n t r o d u c t i o n M . M I T P r e s s,1 9 9 8 2 . T a nM . M u l t i - a g e n t r e i n f o r c e m e n t l e a r n i n g:I n d e p e n d e n t v s . C o o p e r a t i v e a g e n t s C . I n:p r o co ft h et e n t hi n t lC o n fo nm a c h i n el e a r n i n g,1 9 9 3: 3 3 0 3 3 7 3 . We i s sG . L e a r n i n gt oc o o r d i n a t ea c t i o n si nm u l t i - a g e n t s y s t e m s . I nI J - C A L,1 9 9 3:3 1 1 3 1 6 4 . S e nS,S e k a r a nM,H a l eJ . L e a r n i n gt oc o o r d i n a t ew i t h o u ts h a r i n gi n - f o r m a t i o n . I nA A A L,1 9 9 4:4 2 6 4 3 1 5 . S a n d h o l m T,C r i t e sR . L e a r n i n gi nt h ei t e r a t e dp r i s o n e rsd i l e m m a . B i o s y s t e m s,1 9 9 5;3 7:1 4 7 1 6 6 6 . Wa t k i n sCJCH,D a y a nP . Q - l e a r n i n g . M a c h i n el e a r n i n g M . 1 9 9 2:2 7 2 2 9 2 7 . L i t t m a nM L . M a r k o vg a m e sa saf r a m e w o r kf o rm u l t i - a g e n tr e i n - f o r c e m e n t l e a r n i n g C . I n:1 1 t hI C M L ,N e wB r u n s w i c k,1 9 9 4:1 5 7 1 6 3 8 . H u j u n l i n g,We l l m a n M P . N a s h Q- l e a r n i n g f o rG e n e r a l - S u m S t o c h a s t i cG a m e s J . J o u r n a lo fM a c h i n el e a r n i n gr e s e a r c h,2 0 0 3; (1) : 1 3 0 9 . C r a i gB o u t i l i e r . S e q u e n t i a lo p t i m a l i t ya n dc o o r d i n a t i o ni nm u l t i - a g e n t s y s t e m