分类:
2009-07-19 21:26:43
摘要:对等网络(P2P)有3种主要的组织结构:分布式哈希表(DHT)结构、树形结构、网状结构。P2P已经延伸到几乎所有的网络应用领域,如分布式科学计算、文件共享、流媒体直播与点播、语音通信及在线游戏支撑平台等方面。现在人们已经开始将重心转入到覆盖层网络的节点延时聚集研究、覆盖网之间(Inter-Overlay)优化研究、P2P支撑平台研究以及P2P安全研究等方面。
关键词:对等网络;分布式哈希表;覆盖层网络
Abstract:ThePeer-to-peer(P2P)network has three main structures: Distributed Hash Table (DHT) structure, tree structure, and mesh structure. P2P technology has been extended to almost all areas of network applications, including distributed scientific computing, file sharing, streaming media on-demand and live broadcast, voice communications, and online gaming support platform. Now, study areas such as node latency aggregation for overlay network, Inter-Overlay optimization, P2P supporting platform, and P2P security are receiving more attention.
Keywords:P2P;distributedHash table; overlay network
什么是对等网络(P2P)技术?P2P技术属于覆盖层网络(Overlay Network)的范畴,是相对于客户机/(C/S)模式来说的一种网络信息方式。在C/S模式中,数据的分发采用专门的服务器,多个客户端都从此服务器获取数据。这种模式的优点是:数据的一致性容易控制,系统也容易管理。但是此种模式的缺点是:因为服务器的个数只有一个(即便有多个也非常有限),系统容易出现单一失效点;单一服务器面对众多的客户端,由于CPU能力、内存大小、网络带宽的限制,可同时服务的客户端非常有限,可扩展性差。P2P技术正是为了解决这些问题而提出来的一种对等网络结构。在P2P网络中,每个节点既可以从其他节点得到服务,也可以向其他节点提供服务。这样,庞大的终端资源被利用起来,一举解决了C/S模式中的两个弊端。
P2P网络有3种比较流行的组织结构,被应用在不同的P2P应用中。
(1)DHT结构
分布式哈希表(DHT)[1]是一种功能强大的工具,它的提出引起了学术界一股研究DHT的热潮。虽然DHT具有各种各样的实现方式,但是具有共同的特征,即都是一个环行拓扑结构,在这个结构里每个节点具有一个唯一的节点标识(ID),节点ID是一个128位的哈希值。每个节点都在路由表里保存了其他前驱、后继节点的ID。如图1(a)所示。通过这些路由信息,可以方便地找到其他节点。这种结构多用于文件共享和作为底层结构用于流媒体[2]。
(2)树形结构
P2P网络树形结构如图1(b)所示。在这种结构中,所有的节点都被组织在一棵树中,树根只有子节点,树叶只有父节点,其他节点既有子节点也有父节点。信息的流向沿着树枝流动。最初的树形结构多用于P2P流媒体直播[3-4]。
(3)网状结构
网状结构如图1(c)所示,又叫无结构。顾名思义,这种结构中,所有的节点无规则地连在一起,没有稳定的关系,没有父子关系。网状结构[5]为P2P提供了最大的容忍性、动态适应性,在流媒体直播和点播应用中取得了极大的成功。当网络变得很大时,常常会引入超级节点的概念,超级节点可以和任何一种以上结构结合起来组成新的结构,如KaZaA[6]。
2 P2P技术应用现状
由于能够极大缓解传统架构中服务器端的压力过大、单一失效点等问题,又能充分利用终端的丰富资源,所以P2P技术被广泛应用于计算机网络的各个应用领域,如分布式科学计算、文件共享、流媒体直播与点播、语音通信及在线游戏支撑平台等方面。
(1)分布式科学计算
我们知道,许多计算机的CPU资源并不是时刻保持峰值运转的,甚至很多时候计算机处于“空闲”状态,比如使用者暂时离开等情况。而P2P技术可以使得众多终端的CPU资源联合起来,服务于一个共同的计算。这种计算一般是计算量巨大、数据极多、耗时很长的科学计算。在每次计算过程中,任务(包括逻辑与数据等)被划分成多个片,被分配到参与科学计算的P2P节点机器上。在不影响原有计算机使用的前提下,人们利用分散的CPU资源完成计算任务,并将结果返回给一个或多个服务器,将众多结果进行整合,以得到最终结果。
世界最著名的P2P分布式科学计算系统非“SETI@home”项目莫属。SETI@home项目(简称为S@H或SETI),由美国加利福尼亚大学伯克利分校在1999年发起,是至今最成功的分布式计算项目。SETI@home通过分析从射电望远镜传来的数据来搜寻地外文明,这在不少科幻迷甚至是很多普通大众眼里都是一个“很酷”的应用。SETI的早期版本截至2005年已经吸引了543万用户,分析了大量积压数据。正如宇宙的浩瀚一般,需要计算的数据(即存在宇宙空间的无数无线号)也是海量的。可以说,这几百万台终端组成了一个目前最快的高性能计算机都望尘莫及的“超级计算机”。
(2)文件共享
要问一百个网友目前中国最流行的文件下载方式,恐怕99个都会回答是“BT”。“BT”是BitTorrent[7]的简称,是一种依赖P2P方式将文件在大量互联网用户之间进行共享与传输的协议,对应的客户端软件有BitTorrent、BitComet和BitSpirit等。由于其实现简单、使用方便,在中国用户之间被广泛使用。BitTorrent中的节点在共享一个文件时,首先将文件分片并将文件和分片信息保存在一个流(Torrent)类型文件中,这种节点被形象地称作“种子”节点。其他用户在下载该文件时根据Torrent文件的信息,将文件的部分分片下载下来,然后在其他下载该文件的节点之间共享自己已经下载的分片,互通有无,从而实现文件的快速分发。由于每个节点在下载文件的同时也在为其他用户上传该文件的分片,所以整体来看,不会随着用户数的增加而降低下载速度,反而下载的人越多,速度越快。
BitTorrent是一种无结构的网络协议。除了BitTorrent之外,还有不少著名的无结构化的P2P文件共享协议,典型的有Gnutella[8]和KaZaA[6]。
Gnutella协议是一种最典型的完全分布式、无等级结构的P2P网络模型。网络中的节点随机连接若干个其他节点,称之为“邻居”。这种结构能够很好地适应P2P网络中节点频繁加入与离开的动态特性,因为任意一个节点都可以被新加入的节点作为“邻居”而连接,任意一个“邻居”也可以随意地离开网络。同时,这种加入节点和离开节点的选择是节点间的独立行为,随机分布于网络之中。所以说Gnutella的网络具有健壮性、实时性、可靠性、负载平衡等优势。
在Gnutella网络中存在以下问题:
冗余消息多,对带宽的消耗存在一定的浪费。Gnutella网络协议采用泛洪式(Flooding)消息传播机制,这种消息传播机制产生了呈指数级增长的冗余消息。据统计,P2P软件白天占Internet上运行带宽的40%~70%,晚上有时能达到80%。
搜索效率低,可扩展性差。Gnutella网络的搜索协议将所有资源与节点统一对待,没有考虑节点的性能差异,也没有利用查询成功的历史经验,使得搜索效率低下。
KaZaA协议中节点大体上也是无结构连接的。但是在KaZaA协议中存在一种“超级节点”。这种“超级节点”其实是来源于各个普通的客户端节点,但它们一般具有计算能力强、带宽大、在线时间稳定等特点。在KaZaA协议中,超级节点承担着部分服务器的任务,如管理部分普通节点,负责搜索消息的转发等。每一个节点上线后会寻找一个超级节点挂靠,并和原先挂靠在该超级节点下的其他普通节点随机相连,组成一个小的无结构网络。普通节点的共享文件索引汇报给所挂靠的超级节点。因而,KaZaA网络大体上可以看作是两层的无结构网络,上层是超级节点组成的无结构网络;下层是普通节点组成的多个无结构网络,按所挂靠的超级节点分成多个簇。当普通节点发起文件搜索请求时,将请求消息发给所挂靠的超级节点,超级节点从自己存储的共享文件索引信息中查找区域内符合条件的文件,同时将搜索请求转发给若干个其他超级节点,由它们返回其区域内搜索结果。如果需要,这个转发过程可以执行多步以获得更大范围内的搜索结果。这样的混合式结构对异构的终端节点“分而治之”,可以充分利用一些能力较强的终端节点来担任“小”服务器的角色,可谓是“人尽其才,物尽其用”。
除了这些无结构的P2P文件共享协议之外,几乎所有的DHT网络都可以并已经用来实现文件共享的应用,如Chord、Pastry、KAD、CAN等应用。
(3)流媒体直播
曾经人们以为P2P做文件共享最合适,但现在大家发现P2P模式是如此适合于流媒体直播,以至于研究热点在很短的时间内迅速转移到P2P的流媒体上来。中国最早的P2P流媒体直播软件应该算香港科技大学计算机系研究的Coolstreaming[5]、华中科技大学与网格计算湖北省实验室研究的AnySee[9]以及清华大学的Gridmedia等系统。
Coolstreaming是一款基于网状无结构网络拓扑的流媒体直播软件,中文名叫做“酷流”。在Coolstreaming中,每个节点通过登录服务器(BS)进入网络,并得到一些邻居列表。每个节点和邻居之间共享媒体数据。Coolstreaming中节点共享媒体数据是基于一种称作“数据驱动”的机制。首先,对于节点缓冲区内所拥有的数据,使用一种“缓冲映射表”(Buffer Map)来进行标记:对于每一秒的媒体内容,如果节点已经从节目源或邻居处获取,则标记该秒数据为“1”,否则标记为“0”。这样,一个80秒长度的缓冲区就对应一个80位长度的缓冲映射表。其次,节点之间以“心跳”(Heartbeat)方式定期交换各自的缓冲映射表,通过比对得到自己没有而邻居拥有的数据位,然后根据数据调度算法,选择合适的邻居,请求得到相应的数据。Coolstreaming采取全网状结构组织网络中的节点,每个节点连接20个左右的邻居,在定期交换缓冲映射表的同时,还要交换自己的邻居列表。这样,在一个邻居离开时,可以从它最近提供的邻居列表中选择一个连接数没有达到上限的邻居作为“替补”邻居进行连接。最早期的Coolstreaming是采取随机选取邻居的策略,即从BS上随机返回一些当前在线的节点列表,然后随机从中选择一些节点进行连接,在选择“替补”邻居时也是随机的。这样做同时又可以达到一定程度的负载平衡效果,因为每个节点连接的邻居数基本是均匀的。但是这样做的缺点也是明显的,两个距离很远、连接很差的节点也可能被调度成为邻居,大大影响的系统的服务质量。
华中科技大学集群与网格计算湖北省重点实验室是中国最早研究P2P流媒体直播的小组之一,它所研发的AnySee软件期望能够使得用户在网上任何时候任何地点都能观看多媒体直播节目。
AnySee的第一个版本基于树状结构:节目源是一个多播树的根节点,之后的节点被调度为其“儿子”或子树。每个节点向其父节点索要数据,并将数据提供给多个子节点。这样的结构可以使得节点快速加入到网络中,并且可以根据IP邻近原则构建起一棵IP多播树,使得节点加入位置都是和自己IP邻近的节点,从而优化服务质量。之后AnySee推出第二个版本,结合了原有的树状结构和流行的网状结构,使得“控制数据走树,媒体数据走网”,既能帮助节点快速定位到加入点,又能实现一定程度的负载均衡,并缓解了原有纯树状结构中底层节点和顶层节点之间播放时差较大的问题。最近的AnySee版本已经取消了树的结构,演化成了优化的网状结构(如图2所示),即每个节点维护一定数量的邻居成员,并从中选出最合适的“伙伴”节点与之交换数据。伙伴的数量既有上限又有下限,在不满足下限时,节点会不断寻找新的合适节点加入伙伴列表;在达到下限时,节点停止主动寻找伙伴的过程,但可以接受其他节点将其加入伙伴列表的请求;在达到上限时,节点不再和新的节点建立伙伴关系。
除了学术界对P2P流媒体直播的研究外,中国还涌现了很多成功的P2P流媒体直播商业产品,如PPLive、PPStream、沸点和TVAnts等,其中以PPLive最为有名。PPLive目前拥有数百个频道,在2006年“超级女声”决赛期间,频道观看人数达到十万人,可以说是把P2P发挥到了极限。此外,国外也有不少对P2P流媒体直播的研究,如SplitStream[10]等。
(4)流媒体点播
由于观看直播节目时用户不能选择观看指定片段,所以在人们热烈研究P2P流媒体直播时,已有人开始将目光转向P2P流媒体点播服务。目前成功推出P2P流媒体点播的机构还不多,典型的有GridCast[11]系统、PPStream点播系统。GridCast也是一款由华中科技大学集群与网格计算湖北省重点实验室于2005年12月份成功研发并投入使用的对等视频点播系统,具有支持多人共享点播片段、跟踪(Tracker)服务器用户引导、环状结构内容组织等特点。由于一个点播频道的人数往往不会太多,所以在用户进行视频录放(VCR)操作时(即前后拖动播放点、暂停/继续播放等操作),能否快速将用户定位到观看该点节目的其他用户处就成了P2P点播技术的关键。为了实现快速定位,GridCast中采取了一种同心圆环的媒体内容组织结构。在每一个节目频道里,媒体内容按指数递增的区间进行划分,例如一个一个半小时的电影节目,可划分成[0, 5]、(5, 15]、(15, 35]、(35, 75]和(75, END=90]几段,其单位为分钟。每个节点记录几个正在观看各个段之间内容的节点。这样,在和AnySee类似的网状结构中,可以定期交换这种分段记录,从而,在某个用户拖动观看点时,可以快速定位到相应段的记录节点处,并从这些节点当时所观看的区间内得到大量备用记录以请求该区间媒体数据。此外,GridCast还根据用户习惯对数据调度策略进行优化。
(5)IP层语音通信
IP层语音通信()是一种全新的通信业务,它和传统的电话业务相比有着扩展性好、部署方便、价格低廉等明显的优点。在全球范围内的VoIP应用中,由于通信各方可能处于不同的网络状况下,所以采取少数几个服务器来进行话音包中转不仅存在压力过大的问题,还可能无法为指定通信双方提供满意的通话质量保证。所以采取P2P技术动态自适应地根据通信双方网络进行链路控制与消息转发是可行的。
目前风靡全球的Skype[12]即是一款典型的P2P VoIP软件。Skype由于能够提供清晰的语音质量和免费的服务,使用起来又方便快捷,所以吸引了全球数千万的用户,每天在线用户达500万人,并且注册用户数每天增加15万。基本上,Skype采取类似KaZaA的拓扑结构,在网络中选取一些超级节点。在通信双方直连效果不好时,一些合适的超级节点则担当起其中转节点的角色,为通信双方创建中转连接,并转发相应的语音通信包。
(6)网络游戏平台
大型网络在线游戏和网络对战游戏是不少“网虫”的至爱。但由于服务器能力有限,大型网络在线游戏往往需要限制场景人数或者不断增加服务器,而网络对战游戏也必须局限在内进行或者依赖独立的服务器端程序及机器实现Internet上的电子竞技。目前,已有研究人员将P2P技术引入网络游戏和网络游戏支撑平台中。
目前较为成功的P2P游戏平台是华中科技大学集群与网格计算湖北省重点实验室推出的PKTown[13]系统。PKTown系统是一个支持多种网络对战游戏的P2P平台。P2P网络对战游戏平台的难点在于将严格延时约束的节点聚集在一起,这由对战游戏本身要求所决定:延时是影响对战游戏用户体验的关键因素。在众多在线用户中,如何将新加入用户调度到周围都是延时邻近的环境中去呢?PKTown也是采取GridCast中出现过的指数增长的同心圆环方式,很好地解决了这个问题。
PKTown不需要改变游戏本身的代码,而是将用户和Internet邻居组建成一个虚拟局域网,将游戏发出的通信包截获后负载上虚拟局域网的地址,转发出去,游戏进程接收到之后认为是来自同一局域网的游戏包,则可以正常进行游戏。目前PKTown支持魔兽争霸、星际争霸和反恐精英几款游戏,已经在高校范围内进行公测,并成功举办华中科技大学第三届Race War游戏大赛,用户反应良好。
3 结束语
自P2P技术从1999年出现之后,现在已经发展繁荣起来。前文中提到的很多技术都已经趋近成熟,如拓扑构建和内容分发等相关技术。由于P2P架构灵活,适用面广阔,所以将P2P应用到新领域的现象层出不穷,P2P的软件产品也如雨后春笋一般爆炸性增长。
通过本文的描述可以看出,P2P蹬基本原理是容易实现的,人们的研究方向也由基础架构的构建和维护及优化算法等桎梏中摆脱出来,开始深入到P2P技术的根本性问题中去。最新的研究成果表明,不少研究人员已经开始将重心转入到覆盖层网络的节点延时聚集研究、覆盖网之间(Inter-Overlay)优化研究、P2P支撑平台研究以及P2P安全方面的研究等方面。相信随着对P2P技术研究的不断深入,人们能够对P2P计算有一个更深入的认识并解决目前P2P领域中大部分科学问题。可以预见,P2P所带来的技术创新和应用创新还将继续。
4 参考文献
[1]STOICAI,MORRIS R, KARGER D, et al. Chord: a scalable peer-to-peer lookup service for Internet applications [C]// Proceedings of the International Conference of the Special Interest Group on Data Communication (SIGCOMM'01), Aug 27-31,2001, San Diego, CA, USA. New York, NY, USA: ACM Press, 2001:149-160.
[2]HEFEEDAM,HAB A, BOTEV B, et al. PROMISE: Peer-to-peer media streaming using CollectCast [C]// Proceedings of the 11th ACM International Conference on Multimedia, Nov 2-8, Berkeley, CA, USA. New York, NY, USA:ACM Press, 2003:45-54.
[3]BANERJEES,BHATTACHARJEE B, KOMMAREDDY C. Scalable application layer multicast [C]// Proceedings of the International Conference of the Special Interest Group on Data Communication (SIGCOMM'02), Aug 19-23,2002, Pittsburgh, PA, USA. New York, NY,USA: ACM Press,2002, 205-217.
[4]TRANDA, HUA K A, DO T T. ZIGZAG: An efficient peer-to-peer scheme for media streaming [C]// Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '03): Vol 2, Mar 30-Apr 3,2003, San Francisco, CA, USA. New York, NY, USA:IEEE, 2003:1283-1292.
[5]ZHANGXinyan,LIU Jiangchuan, LI Bo, et al. CoolStreaming/DONet: a data-driven overlay network for peer-to-peer live media streaming [C]//Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies: Vol 3, Mar 13-17, Miami, FL, USA. Piscataway, NJ,USA:IEEE,2005: 2102-2111.
[6]LEIBOWITZN,RIPEANU M, WIERZBICKI A. Deconstructing the Kazaa network [C]// Proceedings of 3rd IEEE Workshop on Internet Applications (WIAPP’03), Jun 23-24, 2003, Santa Clara, CA,USA. Piscataway, NJ, USA:IEEE,2003:112-120.
[7]POUWELSEJA, GARBACKI P, EPEMA D H J, et al. The bit torrent P2P file-sharing system: measurements and analysis [C]//Proceedings of the 4th International Workshop on Peer-to-Peer Systems, Feb 24-25, 2005, Ithaca, NY, USA. Berlin, Germany: Springer-Verlag, 2005: 205-216.
[8]RIPEANUM.Peer-to-Peer architecture case study: Gnutella network [C]//Proceedings of Peer-to-Peer Computing, Aug 27-29,2001, Skyways, Sweden. Los Alamitos, CA, USA: IEEE Computer Society, 2001:99-101.
[9]LIAOXiaofei,JIN Hai, LIU Yunhao, et al. AnySee: peer-to-peer living streaming [C]//Proceedings of 25th IEEE International Conference on Computer Communications (Infocom’06), Apr 23-29, 2006, Barcelona, Spain. Piscataway, NJ, USA: IEEE, 2006: 1-10.
[10]CASTROM,DRUSCHEL P, Kermarrec a m, et al. SplitStream: High-bandwidth multicast in cooperative environments [C]// Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, Oct 19 - 22, 2003, Bolton Landing, NY, USA .New York, NY, USA:ACM Press,2003:298-313.
[11]CJENGB,LIU X, ZHANG Z, et al. A measurement study of a peer-to-peer video-on-demand system [C]//Proceedings of 6th International Workshop on Peer-to-Peer Systems (IPTPS'07), Feb 26-27,2007,Bellevue,WA, USA. 2007.
[12]BASETSA, Schulzrinne h G. An analysis of the Skype peer-to-peer Internet telephony Protocol [C]//Proceedings of 25th IEEE International Conference on Computer Communications, Apr 23-29, 2006,Barcelona, Spain. Piscataway, NJ,USA: IEEE ,2006:1-11.
[13]JINH,YAO H, LIAO X, et al. PKTown: A peer-to-peer middleware to support multiplayer online games [C]//Proceedings of International Conference on Multimedia and Ubiquitous Engineering, Apr 26-28, 2007,Seoul, Korea. 2007: 54-59.
作者简介:
金海,华中科技大学特聘教授、博士生导师,华中科技大学计算机学院院长。长期从事计算系统虚拟化、网格计算、对等计算、集群计算等相关领域的研究。获国家发明专利14项。已发表学术论文300余篇,被SCI、EI索引收录160余篇次。廖小飞,博士,华中科技大学副教授。从事对等计算、流媒体服务等领域的研究。已发表论文30余篇,其中被SCI、EI等索引引用10余篇次。