论文部分内容阅读
P2P网络的逻辑结构和物理结构匹配,主要是指对节点的物理网络位置的知晓(比如距离的远近),以及逻辑层与物理层之间的拓扑网络结构的匹配。资源搜索是P2P网络中非常重要的构成部分,但是同时也带来了很大的网络开销,此外,资源搜索过程中查询消息需要在逻辑层的网络拓扑网络中传输,这就引出了逻辑层与物理网络层之间的匹配问题。
一、P2P网络的逻辑结构与物理结构不匹配。
由于逻辑层和物理网络的不匹配的原因,很容易出现同一消息重复穿越相同的物理链接的现象,带来大量多余流量。
根据文献的叙述,Gnutella网络是应用最广的典型的分布式P2P系统。而只有50000个节点的Gnutella网络,就会产生了330TB/月的流量。文献[2]指出:Gnutella网络中只有2%—5%的节点位于同一自治系统(AS)中,而超过40%的节点都位于前10大AS。这表明大部分的P2P网络流量都要跨越AS边界,增加了网间流量。
二、改进逻辑结构和物理结构不匹配的现有的办法。
现有,对P2P系统搜索效率的改进方法可以分为4类:基于转发机制、基于集群化、基于逻辑层拓扑优化及基于缓存。这四种方法可以一起使用,相互补充。目前已有的研究的相关工作,如下所述。
1.基于转发机制
基于转发机制的改进方法原理,对于分布式P2P网络系统来说就是,节点根据物理网络信息选择一部分邻居节点而不是所有的逻辑邻居节点来转发查询消息。文献[4]提出的有向BFS方法中,每个节点维护一个基于一些量化值的信息,比如从邻居节点获得的查询结果walker数量、与该邻居节点的链接时延。节点选择返回最多查询结果的邻居节点或者最近的邻居节点来转发查询消息。文献[5]提出的K-walker查询方法,源节点会发送若干个不同的行走者(转发邻居节点)。行走者到达的节点,随机只选择一个邻居节点来转发该查询。而对于每个行走者来说,查询过程是顺序处理的。
2.基于集群化
限制节点的交互信息的往来是严格控制资源搜索流量的关键问题。而将节点集群分组是一个很有效的方法。首先,先对集群化进行理论描述文献[6]。通过估算互联网上任意两台主机间的近似距离(采用IP网络的时延来代表距离),生成加权图,加权值就是主机间的距离。这样,网络的集群化问题就被定义为图的最优化划分。用图论公式描述为:给定加权图、直径,将整个图划分为最少的N个集群,集群的总和覆盖全图。任意一个集群中,两个节点的间距小于K。这样形成的理想逻辑网络和物理网络结构的关系是,大部分逻辑层逻辑连接位于同一集群的各主机之间,而集群之间只通过少数逻辑连接来连通。
3.基于逻辑层拓扑优化的方法
目前,有很多工作都是通过使用小范围的测量消息,来获知该范围内的拓扑信息,然后进行逻辑层的拓扑优化的。文献提出了LMT算法,是在Gnetella0.6P2P网络协议基础上,设计了叫做TTL2的探测消息类型。
4.基于缓存的方法
基于缓存的,包括数据索引缓存和内容缓存。集中式P2P系统提供集中索引服务器,保存所有节点的共享文件索引。KaZaA使用合作式的超级节点,每个超级节点保存一部分节点的文件索引。有些系统将保存索引这一功能分发到所有的节点。
三、基于聚类思想解决P2P网络的逻辑结构与物理结构匹配性的新方法。
正如前文所说,P2P网络的位置知晓性的问题,研究者提出了很多的解决方法,这些方法也确实都在一定程度上解决了P2P网络的位置知晓性的问题,但是这些方法也存在这样或者那样的问题,比如基于缓存的方法必然对设备的性能有更高的要求,要有更大的存储空间才有可能保持的性能;基于转发机制的方法也存在着在某些情况下容易引发消息洪泛的可能。所以,基于这些情况,本文提出了基于聚类思想的P2P网络的位置知晓性的问题的解决方案。
聚类方法是数据挖掘技术中的一种重要的方法。我们可以将解决P2P网络的位置知晓性的问题的方法中的基于集群化思想的地标方法与数据挖掘中的聚类思想相结合,从而得到新的解决P2P网络的位置知晓性的问题的方法。
本文讨论P2P网络的逻辑结构和物理结构匹配问题,分析造成底层网络重复消息的理论原因,研究对等网络(P2P)的逻辑结构和物理结构匹配问题。虽然对于P2P网络的逻辑结构和物理结构匹配问题很多研究者提出了很多的研究方法,但是总有这样那样的缺陷,本文根据网络环境的实际情况,提出了基于聚类的P2P网络知晓性的新算法。
参考文献:
[1]K.Sripanidkulchai.The Popularity of Gnutella Queries and Its Implications on Scalability.http://www2.cs.cmu.edu/ kunwadee/research/p2p/gnutella.html,2001.
[2]M.Ripeanu,A.Iamnitchi,and I.Foster.Mapping the Gnutella Network.IEEE Internet Computing,2002.
[3]Yunhao Liu,Li Xiao,Xiaomei Liu,Lionel M. Ni,Xiaodong Zhang.Location Awareness in unstructured Peer-to-Peer systems.IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,VOL.16,NO.2,FEBRUARY 2005
[4]B.Yang and H.Garcia-Molina.Efficient Search in Peer-to-Peer Networks.Proc.22nd Int’l Conf.Distributed Computing Systems(ICDCS),2002.
[5]Q.Lv,P.Cao,E.Cohen,K.Li,and S.Shenker.Search and Replication in Unstructured Peer-to-Peer Networks.Proc.16th ACM Int’l Conf.Supercomputing,2002.
[6]NG,T.E.,AND ZHANG,H.Predicting Internet Network Distance with Coordinates-based Approaches.In Proceedings of IEEE INFOCOM’02,New York,June 2002.
[7]Yunhao Liu,Li Xiao,Xiaomei Liu,Lionel M.Ni,Xiaodong Zhang.Location-Aware Topology Matching in P2P Systems.IEEE INFOCOM 2004,Hong Kong,China,March 2004.
一、P2P网络的逻辑结构与物理结构不匹配。
由于逻辑层和物理网络的不匹配的原因,很容易出现同一消息重复穿越相同的物理链接的现象,带来大量多余流量。
根据文献的叙述,Gnutella网络是应用最广的典型的分布式P2P系统。而只有50000个节点的Gnutella网络,就会产生了330TB/月的流量。文献[2]指出:Gnutella网络中只有2%—5%的节点位于同一自治系统(AS)中,而超过40%的节点都位于前10大AS。这表明大部分的P2P网络流量都要跨越AS边界,增加了网间流量。
二、改进逻辑结构和物理结构不匹配的现有的办法。
现有,对P2P系统搜索效率的改进方法可以分为4类:基于转发机制、基于集群化、基于逻辑层拓扑优化及基于缓存。这四种方法可以一起使用,相互补充。目前已有的研究的相关工作,如下所述。
1.基于转发机制
基于转发机制的改进方法原理,对于分布式P2P网络系统来说就是,节点根据物理网络信息选择一部分邻居节点而不是所有的逻辑邻居节点来转发查询消息。文献[4]提出的有向BFS方法中,每个节点维护一个基于一些量化值的信息,比如从邻居节点获得的查询结果walker数量、与该邻居节点的链接时延。节点选择返回最多查询结果的邻居节点或者最近的邻居节点来转发查询消息。文献[5]提出的K-walker查询方法,源节点会发送若干个不同的行走者(转发邻居节点)。行走者到达的节点,随机只选择一个邻居节点来转发该查询。而对于每个行走者来说,查询过程是顺序处理的。
2.基于集群化
限制节点的交互信息的往来是严格控制资源搜索流量的关键问题。而将节点集群分组是一个很有效的方法。首先,先对集群化进行理论描述文献[6]。通过估算互联网上任意两台主机间的近似距离(采用IP网络的时延来代表距离),生成加权图,加权值就是主机间的距离。这样,网络的集群化问题就被定义为图的最优化划分。用图论公式描述为:给定加权图、直径,将整个图划分为最少的N个集群,集群的总和覆盖全图。任意一个集群中,两个节点的间距小于K。这样形成的理想逻辑网络和物理网络结构的关系是,大部分逻辑层逻辑连接位于同一集群的各主机之间,而集群之间只通过少数逻辑连接来连通。
3.基于逻辑层拓扑优化的方法
目前,有很多工作都是通过使用小范围的测量消息,来获知该范围内的拓扑信息,然后进行逻辑层的拓扑优化的。文献提出了LMT算法,是在Gnetella0.6P2P网络协议基础上,设计了叫做TTL2的探测消息类型。
4.基于缓存的方法
基于缓存的,包括数据索引缓存和内容缓存。集中式P2P系统提供集中索引服务器,保存所有节点的共享文件索引。KaZaA使用合作式的超级节点,每个超级节点保存一部分节点的文件索引。有些系统将保存索引这一功能分发到所有的节点。
三、基于聚类思想解决P2P网络的逻辑结构与物理结构匹配性的新方法。
正如前文所说,P2P网络的位置知晓性的问题,研究者提出了很多的解决方法,这些方法也确实都在一定程度上解决了P2P网络的位置知晓性的问题,但是这些方法也存在这样或者那样的问题,比如基于缓存的方法必然对设备的性能有更高的要求,要有更大的存储空间才有可能保持的性能;基于转发机制的方法也存在着在某些情况下容易引发消息洪泛的可能。所以,基于这些情况,本文提出了基于聚类思想的P2P网络的位置知晓性的问题的解决方案。
聚类方法是数据挖掘技术中的一种重要的方法。我们可以将解决P2P网络的位置知晓性的问题的方法中的基于集群化思想的地标方法与数据挖掘中的聚类思想相结合,从而得到新的解决P2P网络的位置知晓性的问题的方法。
本文讨论P2P网络的逻辑结构和物理结构匹配问题,分析造成底层网络重复消息的理论原因,研究对等网络(P2P)的逻辑结构和物理结构匹配问题。虽然对于P2P网络的逻辑结构和物理结构匹配问题很多研究者提出了很多的研究方法,但是总有这样那样的缺陷,本文根据网络环境的实际情况,提出了基于聚类的P2P网络知晓性的新算法。
参考文献:
[1]K.Sripanidkulchai.The Popularity of Gnutella Queries and Its Implications on Scalability.http://www2.cs.cmu.edu/ kunwadee/research/p2p/gnutella.html,2001.
[2]M.Ripeanu,A.Iamnitchi,and I.Foster.Mapping the Gnutella Network.IEEE Internet Computing,2002.
[3]Yunhao Liu,Li Xiao,Xiaomei Liu,Lionel M. Ni,Xiaodong Zhang.Location Awareness in unstructured Peer-to-Peer systems.IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,VOL.16,NO.2,FEBRUARY 2005
[4]B.Yang and H.Garcia-Molina.Efficient Search in Peer-to-Peer Networks.Proc.22nd Int’l Conf.Distributed Computing Systems(ICDCS),2002.
[5]Q.Lv,P.Cao,E.Cohen,K.Li,and S.Shenker.Search and Replication in Unstructured Peer-to-Peer Networks.Proc.16th ACM Int’l Conf.Supercomputing,2002.
[6]NG,T.E.,AND ZHANG,H.Predicting Internet Network Distance with Coordinates-based Approaches.In Proceedings of IEEE INFOCOM’02,New York,June 2002.
[7]Yunhao Liu,Li Xiao,Xiaomei Liu,Lionel M.Ni,Xiaodong Zhang.Location-Aware Topology Matching in P2P Systems.IEEE INFOCOM 2004,Hong Kong,China,March 2004.