在防火墙上钻孔:穿透防火墙建立UDP连接

在防火墙上钻孔:穿透防火墙建立UDP连接 在防火墙上钻孔:穿透防火墙建立UDP连接 作者: 时间:2006-02-07 出处:黑客基地 人气: 313 在防火墙上钻孔【UDP Hole Puching】:穿透防火墙建立UDP连接 知道现在流行的P2P软件和IM软件是如何让两台分处在不同防火墙后面的电脑直接对话的吗,SIP当然是一种，还有一种被广泛应用的就是本文介绍的UDP Hole Puching技术。 为了便于讲述，我们假设有这样一个网络拓扑结构: IP=A.A.A.A IP=1.1.1.1 HostA----------FirewallA---------| | Server IP=S.S.S.S | HostB----------FirewallB---------| IP=B.B.B.B IP=2.2.2.2 运用这个技术，必须满足下面的条件: 1) HostA和HostB分别通过FirewallA和FirewallB经过NAT用UDP连接到了Server 2) FirewallA和FirewallB都满足这样的特性，即来自相同IP相同Port的数据包，不管目的地IP是多少， 都会NAT成相同的IP+Port，举个例子吧: HostA通过UDP Port 1234访问主机S1时，防火墙会把数据包NAT成1.1.1.1:5668(举例),那么HostA通过UDP Port 1234访问主机S2时，防火墙仍然会把数据包NAT成1.1.1.1:5668。好在现在的NAT基本上都具备这个特性。 现在，HostA用UDP端口1111连接到Server的5555端口，HostB用端口2222连接到Server的5555端口,在Server看来，HostA来自1.1.1.1:9676(FirewallA NAT过了嘛)，HostB则来自2.2.2.2:6573。当HostA想直接连接HostB时，它这样做: 1)用UDP端口1111发一个数据包给2.2.2.2:6573，注意一定要用端口1111哦，这个数据包一定会被FirewallA NAT成 1.1.1.1:9676 -> 2.2.2.2:5668(不要问为什么，看看前面对防火墙的要求先); 千万别期望HostB会收到这个数据包，因为当包到达FirewallB时，FirewallB被弄糊涂了，它根本不知道 1.1.1.1:9676 -> 2.2.2.2:6573的数据包应该转给谁，当然这个包就会被丢弃并回一个ICMP包说Port不存在。但是，我们还是得到了我们想要的一些东西，那就是我们成功地告诉了FirewallA "如果有2.2.2.2:6573 -> 1.1.1.1:9676的数据包，请转发到A.A.A.A:1111"，这就是一个洞洞!! 2)接下来，和你想象的一样，HostA通过Server中转，告诉HostB，用端口2222发一个数据包到1.1.1.1:9676，HostB照办了，而且这个包一定会被FirewallB NAT成 2.2.2.2:6573 -> 1.1.1.1:9676。这个回复的数据包同样在FirewallB上钻了个孔，凡是1.1.1.1:9676 -> 2.2.2.2:6573的包都会被转发到B.B.B.B:2222，当数据包到达FirewallA时，FirewallA很高兴地把2.2.2.2:6573 -> 1.1.1.1:9676的数据包转发给A.A.A.A:1111。 3)大功告成了，HostA和HostB开始愉快的交谈起来。 很简单吧?不过实施起来还要注意几点，否则你都不知道为什么总连不上: 1) 步骤1中那个Port不存在的ICMP是个杀手，至少对Linux上用iptables做的NAT来讲是这样，因为FirewallA收到这个ICMP会关闭刚钻上的洞洞，想办法不让FirewallB发这个ICMP或者让FirewallA丢掉这个ICMP吧; 2) 时间问，步骤1在FirewallA上开的洞洞是有时间限制的，通常为30,60秒吧，如果超时了都没 收到2.2.2.2:6573 -> 1.1.1.1:9676的包，洞洞会自动关闭，同样步骤2以后，HostA也应该及时在发个数据包给B，以保证FirewallB上的洞洞不会因为超时而关闭。值得提一下的是多数NAT防火墙会在看见进出双向的数据包后延长关闭洞洞的时间，Linux默认设置时会延长到3分钟。 3) HostA不能连到HostB，并不表示HostB一定连不到HostA，反一下方向试试也许会有意外惊喜。 好了，就写这些吧，祝大家钻孔愉快 P2P技术对网络与业务的影响分析 作者:徐亦基、刘云 时间:2006-02-24 出处:中国多媒体视讯 人气: 173 P2P(Peer To Peer)以字意理解就是“伙伴对伙伴”，是目前日益广泛使用的网络应用技术，或者说是一种日益流行的应用层组网技术。由于它在强化交流、文件传播、分布计算等方面所表现出的巨大优势，是目前公认具有广泛应用前途的未来“杀手级”应用。 众所周知，传统的网络应用模式基本是“服务器,客户端”方式一统天下。服务的提供者(发布者)通过网络服务器向大众提供(发布)资源，用户通过客户端(硬件或软件)按照规定的协议向服务器索取所需的内容。在这一方式下，一切服务都是以服务器为核心，以它的正常运转为前提。 P2P技术从根本上颠覆了这一传统模式。新的模式模糊了服务提供者与使用者的界限，甚至不再有传统意义上的服务器，服务提供者的作用大为减弱。每一个参与的使用者同时也成为了提供者。在一个P2P的应用网络中，发布者的作用有些类似于启动的“按钮”和极端情况下的应急备份，先加入的使用者很快就会成为服务的提供者，为后来的使用者提供服务。BT就是一种成功的P2P应用，它能够以超乎想象的速度传播文件，对于文件的发布者和使用者都是便利的工具。但是，也许设计者过于专注技术的完美，以至于几乎没有为其作为“业务”的发展留下任何空间。 为了更好的P2P技术对未来网络与应用的影响，下面我们以另一种也是具有代表性的P2P应用——Skype进行说明。 二、Skype分析 Skype是一种P2P方式的VoIP和IM应用软件，用户可以使用它在数分钟之内与世界上各个角落拨打免费电话。虽然在此之前，类似的软件已经有很多，但是没有一种能够象Skype这样灵活、便捷、可靠而且质量出色。后面我们将仅就其具有典型性的几个方面进行说明。 (1)集中式认证和分散式使用者目录 用户身份认证是Skype网络中惟一集中操作的地方，在应用享有高度灵活性的同时，也为未来向业务的转化做了必要的准备。但是，与众不同的是，用于记录使用者状态(在线)和IP地址的使用者目录却没有集中设置，而是充分信任“伙伴”们的工作，通过大家的协作完成用户搜索等功能。这就减少了在此方面的资源投入，而能够使运营者更加专注于核心的功能。 (2)防火墙和NAT穿越 防火墙在保护网络的同时，也为网络应用人为设置了障碍，NAT也是如此。这两项技术并不是与TCP/IP同时诞生的，从某种意义上说它们是为了使TCP/IP在基础网络方面更加实用而做的“补丁”。其产生的副作用就是对网络应用而言，网络不再像原本那么“通畅”。虽然各种应用都已经发展出一套“完善”的解决， 比如同样用于VoIP的H.323，但是解决方案的成本又注定它不适于一项需要向大众普及的应用。Skype的解决方式既吸取了成功的经验——利用网络中具有穿越防火墙(NAT)能力的主机作为代理，又合理的利用了现有防火墙(NAT)技术的“漏洞”——开放知名应用端口(HTTP)。即使是毫无经验与知识的用户，也能够在不了解自己可能所处的复杂网络环境的条件下轻松使用，并且几乎感觉不到质量的差异。 (3)应用层组网和智能路由 应用层网络的概念在Skype中的作用显得尤为突出。将参与通信的用户分为超级节点(SN)和普通客户端(SC)，通过对用户(主机)的组织，构造起层次清晰、结构合理的应用层网络。同时将必要的功能有的分解到网络中的各个部分，既充分利用的网络中的资源，也减轻了业务运营者的负担。这种应用层网络从结构、逻辑和功能等各个方面都独立于承载网络，并且能够根据用户的数量与状态的变化自行进行调整。智能路由更是其中重要的闪光点，Skype出色的语音质量很大程度得益于智能路由技术。超级节点同时参与了流量分配、路由选择等多项关键工作，从而使延时、抖动等传统VoIP技术中的难点在此变得不再那么重要。 当然，Skype中具有的先进技术特征还不止于此，比如加密技术、跨平台特性、简捷的界面等。 从设计思想上分析，传统的VOIP技术，如H.323还带有更多的PSTN网络的特点，或者说是将PSTN的思路与观点，“移植”到互联网上，使一种成熟的业务能够适应一个新的承载平台。Skype则是完全针对互联网的环境与特点“量身定做”，从设计之初就明确了适用环境、可资利用的资源和要达到的目标。因此，如果以旧的观念来认识Skype，也许将变得难以理解。 三、对网络的影响 在传统应用模式下的网络，应用服务的聚集点(IDC)同样是流量的汇聚点;大量用户仅仅被定位于服务的使用者，因而ADSL等非对称的接入技术大行其道;甚至网络之间的流量特点也带有明显的非对称性——拥有大量信息源的网络，出流量显著高于入流量。同时，这种应用模式和产生的流量特性长期以来指导着网络的设计与升级。 P2P技术将为我们带来一个业务“全分布”式的网络，而且这不再是以往所谈论的服务点有限的分布，而是一种可能无法估计的任意分布。因为运营者希望有更多的用户使用自己的服务，同时也无法预估哪里的用户会使用自己的服务。互联网对地域概念的模糊，将把全世界的用户带到你的面前。流量将呈现出更大的任意性，用户之间直接的数据交换将更加频繁，也不会是谁的IDC更多，谁就一定会有更多的输出流量。面对这一新的形势，网络准备好了吗, P2P技术在应用层的组网，也为网络应用的运营者带来更大的灵活性。无需依靠、关心业务的基础承载网络，就可以对用户进行管理、对业务进行规划、对业务进行控制，有更大的空间拓展业务的商业模式、实施业务策略、进行业务管理。与之相伴的是网络运营商对网络应用的掌控能力进一步下降，整个互联网将呈现出更强的灵活性与开放性。因为诸如Skype这种为互联网设计的业务的广泛应用，必将使互联网的一些固有特性得到进一步强化。 四、对应用、业务的影响 还是以Skype为例，虽然VoIP并不是什么新鲜事务，但是长期以来它对传统固话业务的分流仍然远远不及移动电话的冲击。这种现象很值得思考，人们是否忽略了技术(应用)与业务的差距，忽略了在这段距 离之间所隐藏的一些要素。提起“IP电话”，用户更多的想到的是五花八门的“IP电话卡”，而不是一种真正的网络电话。虽然这里面存在着政策与普及的因素，但是市场的需求永远是具有决定性的力量。如果我们从业务角度重新审视以往的“网络电话”，就会发现它们与Skype之间的差距不是一星半点。 设想一下，如果不存在政策等的限制要素，Skype作为一种真正的业务开始运营，首先收到冲击的就是传统的固定电话业务，更值得担忧的是，还有可能在一夜之间“克隆”出若干个Skype，在另一个层次上展开竞争。相对于传统的固定电话业务，Skype在建设和运营方面都有着无法比拟的成本优势。竞争的结果可想而知。 P2P技术已经不仅仅应用于BT、Skype，已经出现了P2P方式的软件更新、电子杂志分发、视频点播(VOD)，甚至预热阶段的IP-TV都在看好P2P。P2P技术对运营条件的低需求，大大降低了业务启动的成本门槛。也许，在一段时间内，会有人创造性的不断将这一新的技术用于各种既有应用，从而为这些应用带来全新的面孔和使用体验，也可能会带来全新的业务拓展模式。 虽然我们现在的网络和市场条件还不能完全接纳P2P这一新兴事务，甚至会对它的到来有些恐惧，但是这个“杀手”的出现也不会一夕而就。毕竟，还没有哪个P2P类型的业务能够靠从用户手中的收益而成就自身。虽然P2P在技术上已经取得了意想不到的成功，但它作为业务的完善还远未成熟。 “量子流媒体技术”，P2P的下一代, 作者:王科力、吴铭 时间:2006-02-28 出处:流媒体世界 人气: 193 技术的发展从来都是超越人们的想象。正在国内电信运营商纷纷被BT、电驴等P2P传输技术逼得无计可施，正准备祭起“流量计费”大旗时， 远在太平洋彼岸的美国却出现了“量子流媒体技术(Quantum Streaming)”，而这一技术的出现，似乎使得P2P与ISP之间得到了有机结合的机会。 原来，在互联网技术最为发达的美国， BT下载、P2P流媒体等应用早已司空见惯，从而给ISP带来的流量阻塞问题也是日盛一日。因此，美国ISP们纷纷酝酿按照服务类型对服务提供商，比如Google, Yahoo等收费，作为对于ISP们该项垄断措施的反应，美国国会开始制定”网络中立”法律，规定不准对网络数据类型“歧视“，这里的歧视指的是对于一些数据比如视频征收高费用，对于网页等数据则收低费用。 按照内容不同实行歧视性收费是解决流量拥塞的一种方法，但这势必遭到提供大量数据的内容供应商的不满。国会“网络中立”法案通过与否似乎变成了P2P与ISP们的搏弈。然而“量子流媒体技术“的出现，却为双方找了另一条双赢的道路。 量子流媒体技术是由一家惠普前数字媒体战略计划总监 Michel Billard创办的小公司 , Itiva公司 (www.itiva.com) 发明，这项技术的目的总结起来就是用类似HTTP Cache的思路来解决视频文件导致的ISP网络拥塞问题。 内容发行商首先将巨大的视频文件分解成很多小于普通网页的小文件 (量子)，然后发布出去，当某个ISP的用户观看该文件时，视频没有被全部下载，而是一点一点的到达ISP的接入路由器或者DSLAM，ISP在接入层放置Itiva的量子缓存服务器后，所有这些流过的文件片段都被部分缓存了下来，但其他用户想看时，就可以直接从本地ISP的缓存服务器下载，而不用再次启动从内容供应商的发布服务器到本地ISP的传输过程，从而提高响应速度，减少Backbone或城际网的拥塞。目前该技术还处于非常不成熟的阶段，没有正式推出。 从理论上说，该技术是ISP的P2P，能够为用户提供一种同样快速看到视频内容，同时为ISP解决网络拥塞的方案，从而代替目前的用户级P2P。但也存在几个问题，这项技术解决的是Backbone或城际网的拥塞，但在接入层或最后一公里上同样作用不大，而且这项技术给了ISP或内容发行商更大的控制权，用户是否会真的抛弃P2P而选择他也是个问题。而且从技术上说，量子流媒体很像UTStartcom的基于MEPG2TS流的IPTV CDN方案，这两者有什么关系尚不得而知(Itiva公司网站上说明该技术已经获得专利)。 P2P让广大网民廉价的进入了网络视频时代，但毕竟破坏了很多产业规则，导致ISP和内容发行商的利益受损，受到各方阻碍，很难持续发展。有鉴于此，笔者认为在不久的将来，类似量子流媒体这样既能降低网民收看影视内容费用，又能维护ISP利益的技术会不断出现。据闻，在国内也早有电信运营商在研究基于P2P技术的CDN方案。“魔鬼已经从盒子里出来了”，人们担心的并不是魔鬼的力量，而是它那不可控制的混乱。 对等网络中主流分布式哈希算法比较分析 作者:陈岭 时间:2006-03-07 出处:电子工程专辑 人气: 170 本文首先从P2P的定义出发，介绍了结构化P2P与非结构化P2P的区别以及结构化P2P的核心技术DHT。 DHT算法与协议并对每种协议进行了讨论。文章的最后展望了DHT在而后，本文深入介绍了几种主流的 未来的发展趋势。 对等网络(Peer-to-Peer，简称P2P)是目前非常热门的应用，自1999年以来，P2P的研究一直是国外知名学府(如美国麻省理工学院，加州大学伯克利分校和莱斯大学等)以及知名企业的研发机构(如微软，诺基亚的研究院)关注的重点。它甚至被美国《财富》杂志称为改变因特网发展的四大新技术之一，被认为是代表无线宽带互联网未来的关键技术。 作为一项新兴的技术，目前学术界对P2P在技术层面上的定义尚未统一。Keith W. Ross (Polytechnic University)和Dan Rubenstein(Columbia University)在[9]中提到了对P2P系统的3个基本定义: 相比中央服务器而言有明显的自治性(Autonomy)。 利用网络边缘的资源，如存储/计算能力和信息资源。 网络边缘的资源处在动态的变化中(新的资源加入，已有的资源消失)。 自治性的要求使得P2P系统不再需要特定的中央管理机制，所有节点之间拥有对等的关系。这一方面为系统带来了自组织、容错性好、可扩展性强等优点;另一方面也提出了新的问题:如何在没有集中管理机制的情况下实现系统的自组织和自管理, 定义2，3中分布性和动态性的特点使得上述问题的实现具有更大的难度。在分布式系统中，过多过快的信息交互可能消耗大量的网络资源;而为了实时反映系统的变化，又要求节点及时获得更新信息，这就需要在节点之间进行通信。 为了解决这一对矛盾，已经有许多P2P的框架和协议被提出来并得到了很好的应用。 结构化与非结构化P2P 依照节点信息存储与搜索方式的不同，诸多P2P协议可以分为2大类:结构化(Structured)的与非结构化(Unstructured)的系统。 非结构化P2P系统 在非结构化的系统中，每个节点存储自身的信息或信息的索引(如指针和IP地址)。当用户需要在P2P系统中获取信息时，他们预先并不知道这些信息(如某个文件)会在那个节点上存储。因此，在非结构化P2P系统中，信息搜索的算法难免带有一定的盲目性，例如最简单的泛洪式查找(类似于广播)和扩展环查找(从最近的n个节点开始，层层转发直到找到目标或超出了跳数的上限为止)。 一些典型的应用采用了一些优化的办法。如在Gnutella中，采用了等级制的组成结构:节点被分成超级节点(Super Node)和普通节点。普通节点必须依附于超级节点，每个超级节点作为一个独立的域管理者，负责处理域内的查询操作。在查找的过程中，查询首先在域内进行，失败后才会扩展到超级节点之间。 非结构化系统的优点在于实现结构简单:无须中央服务器，节点之间完全平等，网络的层次是单一的，而且节点之间无需维护拓扑信息。 结构化P2P系统 在结构化P2P系统中，每个节点只存储特定的信息或特定信息的索引。当用户需要在P2P系统中获取信息时，他们必须知道这些信息(或索引)可能存在于那些节点中。由于用户预先知道应该搜索哪些节点，避免了非结构化P2P系统中使用的泛洪式查找，因此提高了信息搜索的效率。 但是，结构化P2P也引入了新的问题: 首先，既然信息是分布存储的，那么如何将信息分布存储在重叠网中的节点上, 其次，由于节点动态的加入和离开重叠网，如何将拓扑的变更信息通知其它节点, DHT的引入基本解决了上述问题，因此自从DHT协议出现以后，结构化P2P的应用得到了快速的发展。目前已经有很多较为成熟的DHT协议被提出并且得到了应用。其中比较有代表性的有:缓冲阵列路由协议(CARP);一致性哈希;Chord;内容寻址网络;Pastry。 DHT简介 DHT使用分布式哈希算法来解决结构化的分布式存储问题。分布式哈希算法的核心思想是通过将存储对象的特征(关键字)经过哈希运算，得到键值(Hash Key)，对象的分布存储依据键值来进行。具体来讲，大致有以下步骤: 对存储对象的关键字进行哈希运算，得到键值。这样就将所有的对象映射到了一个具体的数值范围中。 重叠网中的每个节点负责数值范围中的特定段落。例如，节点A负责存储键值从8000到8999的对象;而节点B负责7000~7999的对象。这样就将对象集合分布地存储在所有的节点中。 节点可以直接存储对象本身，如文件中的一个片段;也可以存储对象的索引，如该对象所在节点的IP地 址。 结构化的分布式存储问题解决后，剩下的问题就是用户如何才能找到存储着目标信息的节点。在有着大量节点(如100万个)的P2P系统中，任何节点都不可能拥有全部的节点?键值?内容的对应关系;因此用户获得了键值之后，如何找到该键值对应的节点就被称为DHT的路由问题。DHT协议必须定义优化的查找(路由)算法来完成这一搜寻的工作。不同的DHT协议之间区别很大程度上就在于定义了不同的路由算法。 对等网络中主流分布式哈希算法比较分析(2) 作者:陈岭 时间:2006-03-07 出处:电子工程专辑 人气: 171 DHT的应用非常简洁----API简单到只有一项输入和一项输出: 应用层将数据对象(文件、数据块或索引)通过哈希算法获得键值，将该键值提交给DHT后，返回结果就是键值所在节点的IP地址。图1(来自[9])显示了这种应用结构: 图 1 DHT的应用结构 在这样的支持下，可以开发多种P2P的应用程序，如网络存储与文件共享、即时消息、音频/视频等。图2(来自[9])显示了这种应用结构: 图 2 DHT应用的层次 主流DHT协议 缓冲阵列路由协议(CARP，Cache Array Routing Protocol) 协议简介 CARP是由微软公司的Vinod Valloppillil和宾西法尼亚大学的Keith W. Ross在1997年提出的。该协议可以将URL空间映射到一个仅有松散关联关系的Web cache 服务器(在协议中称为“代理”，Proxy)阵列中。支持该协议的HTTP客户端可以根据要访问的URL智能选择目标代理。该协议解决了在代理阵列内分布存储内容的问题，避免了内容的重复存储，提高了客户端访问时Web Cache命中的概率。 哈希算法 哈希使用的关键字有2个，一个是代理的符(每个代理均有唯一的标识)，另一个是URL本身。存储内容时，每个代理负责缓冲哈希键值最大的URL。这样，当缓冲代理阵列发生少量变化时(新的代理加入或旧的代理退出)，原有的URL还有可能仍然被映射到原来的代理上，仍可以按照原有的方式访问。 路由算法 客户端(HTTP浏览器)首先加载一个代理配置文件，该文件中存储了代理的标识符和IP地址等用于哈希的关键参数。浏览器在访问网页时，可以根据URL和代理标识获得代理的位置信息(IP地址)，从而可以直接访问缓冲代理中的页面。 讨论 CARP的哈希过程比较简单，路由查找更是简单到至多只有一跳(O(1))。但是CARP在P2P的应用环境中 有一些致命的缺陷: 每个节点必须知道其它所有节点的信息。在大规模的重叠网环境中，由于可能存在大量的(数百万)节点，加之节点都是动态加入和退出网络，因此这一条件几乎不可能满足。 在缓冲阵列发生较大变化时(这在P2P网络中非常常见)，原有的URL和代理之间的对应关系可能发生改变，从而使得原有的配置文件失效。 一致性哈希(Consistent Hash) 协议简介 一致性哈希算法在1997年由麻省理工学院提出(参见0)，设计目标是为了解决因特网中的热点(Hot pot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得DHT可以在P2P环境中真正得到应用。 哈希算法 一致性哈希提出了在动态变化的Cache环境中，哈希算法应该满足的4个适应条件: 平衡性(Balance) 平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。 单调性(Monotonicity) 单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。 简单的哈希算法往往不能满足单调性的要求，如最简单的线性哈希: x ? ax + b mod (P) 在上式中，P表示全部缓冲的大小。不难看出，当缓冲大小发生变化时(从P1到P2)，原来所有的哈希结果均会发生变化，从而不满足单调性的要求。 哈希结果的变化意味着当缓冲空间发生变化时，所有的映射关系需要在系统内全部更新。而在P2P系统内，缓冲的变化等价于Peer加入或退出系统，这一情况在P2P系统中会频繁发生，因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够避免这一情况的发生。 分散性(Spread) 在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的 结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。 负载(Load) 负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。 从表面上看，一致性哈希针对的是分布式缓冲的问题，但是如果将缓冲看作P2P系统中的Peer，将映射的内容看作各种共享的资源(数据，文件，媒体流等)，就会发现两者实际上是在描述同一问题。 路由算法 在一致性哈希算法中，每个节点(对应P2P系统中的Peer)都有随机分配的ID。在将内容映射到节点时，使用内容的关键字和节点的ID进行一致性哈希运算并获得键值。一致性哈希要求键值和节点ID处于同一值域。最简单的键值和ID可以是一维的，比如从0000到9999的整数集合。 根据键值存储内容时，内容将被存储到具有与其键值最接近的ID的节点上。例如键值为1001的内容，系统中有ID为1000，1010，1100的节点，该内容将被映射到1000节点。 为了构建查询所需的路由，一致性哈希要求每个节点存储其上行节点(ID值大于自身的节点中最小的)和下行节点(ID值小于自身的节点中最大的)的位置信息(IP地址)。当节点需要查找内容时，就可以根据内容的键值决定向上行或下行节点发起查询请求。收到查询请求的节点如果发现自己拥有被请求的目标，可以直接向发起查询请求的节点返回确认;如果发现不属于自身的范围，可以转发请求到自己的上行/下行节点。 为了维护上述路由信息，在节点加入/退出系统时，相邻的节点必须及时更新路由信息。这就要求节点不仅存储直接相连的下行节点位置信息，还要知道一定深度(n跳)的间接下行节点信息，并且动态地维护节点列表。当节点退出系统时，它的上行节点将尝试直接连接到最近的下行节点，连接成功后，从新的下行节点获得下行节点列表并更新自身的节点列表。同样的，当新的节点加入到系统中时，首先根据自身的ID找到下行节点并获得下行节点列表，然后要求上行节点修改其下行节点列表，这样就恢复了路由关系。 讨论 一致性哈希基本解决了在P2P环境中最为关键的问题——如何在动态的网络拓扑中分布存储和路由。每个节点仅需维护少量相邻节点的信息，并且在节点加入/退出系统时，仅有相关的少量节点参与到拓扑的维护中。所有这一切使得一致性哈希成为第一个实用的DHT算法。 但是一致性哈希的路由算法尚有不足之处。在查询过程中，查询消息要经过O(N)步(O(N)表示与N成正比关系，N代表系统内的节点总数)才能到达被查询的节点。不难想象，当系统规模非常大时，节点数量可能超过百万，这样的查询效率显然难以满足使用的需要。换个角度来看，即使用户能够忍受漫长的时延，查询过程中产生的大量消息也会给网络带来不必要的负荷。 对等网络中主流分布式哈希算法比较分析(3) 作者:陈岭 时间:2006-03-07 出处:电子工程专辑 人气: 172 下文中讨论的几种DHT协议都对路由做出了优化，提出了各自的算法。 Chord协议 Chord在2001年由麻省理工学院提出(参见0)，其核心思想就是要解决在P2P应用中遇到的基本问题:如何在P2P网络中找到存有特定数据的节点。与前两种协议不同，Chord专门为P2P应用设计，因此考虑了在P2P应用中可能遇到的特殊问题，这些内容将在路由的部分进行讨论。 哈希算法 Chord使用一致性哈希作为哈希算法。在一致性哈希协议中并没有定义具体的算法，在Chord协议中将其规定为SHA-1。 路由算法 Chord在一致性哈希的基础上提供了优化的路由算法: 在Chord中，每个节点同样需要存储m个其他节点的信息，这些信息的集合被称为查询表(Finger Table)。一致性哈希中的节点同样具有这样的表格，但在Chord中，表格中的节点不再是直接相邻的节点，它们的间距(ID间隔)将成2i 的关系排列(i 表示表中的数组下标)。这样形成的节点之间路由关系实际上就是折半查找算法需要的排列关系。 在查询的过程中，查询节点将请求发送到与键值最接近的节点上。收到查询请求的节点如果发现自身存储了被查询的信息，可以直接回应查询节点(这与一致性哈希完全相同);如果被查询的信息不在本地，就根据查询表将请求转发到与键值最接近的节点上。这样的过程一直持续到找到相应的节点为止。不难看出，查询过程实际上就是折半查找的过程。 经过Chord的优化后，查询需要的跳数由O ( N)减少到O(log(N))。这样即使在大规模的P2P网络中(例如N,100,000,000)，查询的跳数也仅为O(8)，每个节点仅需存储27个(log2100000000)其他节点的信息。 Chord还考虑到多个节点同时加入系统的情况并对节点加入/退出算法作了优化。 讨论 Chord算法本身具有如下优点: 负载平衡 这一优点来自于一致性哈希，也就是一致性哈希中提到的平衡性。所有的节点以同等的概率分担系统负荷，从而可以避免某些节点负载过大的情况。 分布性 Chord是纯分布式系统，节点之间完全平等并完成同样的工作。这使得Chord具有很高的鲁棒性，可以抵 御DoS攻击。 可扩展性 Chord协议的开销随着系统规模(结点总数N)的增加而按照O(logN)的比例增加。因此Chord可以用于大规模的系统。 可用性 Chord协议要求节点根据网络的变化动态的更新查询表，因此能够及时恢复路由关系，使得查询可以可靠地进行。 命名的灵活性 Chord并未限制查询内容的结构，因此应用层可以灵活的将内容映射到键值空间而不受协议的限制。 Chord在CFS系统中得到了应用，具体的介绍可参见[8] 内容寻址网络(Content-Addressable Network，CAN) CAN在2001年由加州大学伯克利分校提出(参见[3])。与Chord一样，CAN也是DHT的一个变种。 哈希算法 CAN的哈希算法与一致性哈希有所不同。Chord中，哈希得到的键值总是一维的，而在CAN中，哈希的结果由d维的笛卡尔空间来表示。d是一个由系统规模决定的常量。 路由算法 CAN的路由查询将在d维笛卡尔空间中进行。 在CAN中，每个节点自身的ID经由哈希后得到的d维向量。经过这样的映射后，整个P2P系统将被映射到一个d维笛卡尔空间中，每个节点的位置由其自身ID决定。CAN对邻居节点的定义并不要求成2i的关系排列，而是改为用在笛卡尔空间上相邻来表示:在d维笛卡尔空间中，2个节点的d维坐标中有d-1维是相等的，剩余的一维是相邻的节点称之为相邻节点。 CAN中的节点仅存储相邻节点表。由于在d维的空间中最多有2d个相邻的节点，因此节点的相邻节点表最多有2d个表项。 在查询的过程中，查询节点首先计算被查询内容的键值(d维向量)，然后在节点列表中查找在笛卡尔空间中与该键值最为接近的相邻节点，找到后向该节点发送查询请求(这一策略被称为贪婪策略)。查询请求中将携带被查询内容的键值。收到查询请求的节点如果发现自身存储了被查询的信息，可以直接回应查询节点(这与一致性哈希完全相同);如果被查询的信息不在本地，就根据相邻节点表将请求转发到与键值最接近的节点上。这样的过程一直持续到找到相应的节点为止。在查询过程中，被查询节点到目标节点的笛卡尔空间距离单调地减少。 如果查询节点或转发节点发现邻居节点表中无法找到可用的下一跳节点，则采用非结构化P2P常用的扩展环搜索(Expanding Ring Search，使用无状态，受控的泛洪算法在重叠网中搜索)以找到合适的(符合贪婪策略)下一节点。 经过CAN的优化后，查询需要的跳数由O ( N)减少到均值为(d/4)(n1/d)的随机制，考虑到d为常数，这一值可以表示为O(n1/d)或O(dn1/d)。 讨论 CAN和Chord的主要区别在于路由算法不同。相比之下，在节点数量非常大时，CAN的平均查询跳数要比Chord增加得更快。而且CAN查询过程中需要的运算量也要高于Chord。但CAN使用的d为预先设置的常量，因此并不假设系统节点数量。在节点总数动态变化范围很大的系统中，CAN的相邻节点表结构保持稳定，这在P2P的应用中也是很重要的优点。 对等网络中主流分布式哈希算法比较分析(4) 作者:陈岭 时间:2006-03-07 出处:电子工程专辑 人气: 173 Pastry Pastry在2001年由位于英国剑桥的微软研究院和莱斯(Rice)大学提出(参见[4])。Pastry也是DHT的一个变种。 哈希算法 Pastry使用一致性哈希作为哈希算法。哈希所得的键值为一维(实际上使用的是128bit的整数空间)。Pastry也没有规定具体应该采用何种哈希算法。 路由算法 在Pastry协议中，每个节点都拥有一个128bit的标识(Node Id)。为了保证Node ID的唯一性，一般由节点的网络标识(如IP地址)经过哈希得到。 Pastry中的每个节点拥有一个路由表R(Routing table)，一个邻居节点集M(Neighborhood Set)和一个叶子节点集合L(Leaf set)，它们一起构成了节点的状态表。 路由表R共有logBN(B = 2b为系统参数，典型值为16，N表示系统的节点总数)行，每行包括B-1个表项，每个表项记录了一个邻居节点的信息(节点标识、IP地址、 当前状态等)。这样就形成了拥有(B-1)logBN个条目的二维表格。路由表第n行的表项所记录的邻居节点的Node ID前n个数位和当前节点的前n个数位相同，而第n，1个数位则分别取从0到B-1的值(除了与当前节点第n，1数位的值)。这样形成的路由表很类似IP路由中最长掩码匹配的算法。参数b(或B)大小非常关键:B过大则节点需要维护很大的路由表，可能超出节点的负载能力，但路由表大些可以存储更多的邻居节点，在转发时更为精确。平均每次路由查找需要的跳数在Pastry中计算的结果是logBN，因此B的选择反映了路由表大小和路由效率之间的折衷。 叶子节点集合L中存放的是在键值空间中与当前节点距离最近的|L|个节点的信息，其中一半节点标识大于 当前节点，另一半节点标识小于当前节点。|L|的典型值为2b或者2*2b。 邻居节点集合M中存放的是在真实网络中与当前节点“距离”最近的|M|个节点的信息。“距离”的定义在Pastry中非常类似IP路由协议中对距离的定义，也就是考虑到转发跳数、传输路径带宽、QoS等综合因素后所得的转发开销(可以参见OSPF等路由协议)。Pastry并未提供距离信息的获取方法，而是假设应用层可以通过某种手段(人工配制或自动协商)得到信息并配置邻居节点集合。|M|的典型值为2b或者2*2b。 图 3给出了一个Pastry节点状态表的例子，该图来源于[4]。 在节点状态表中，节点本身的ID为10233102。叶子集合中有8项，每一项都代表一个当前节点已知的其他节点的信息。路由表共有4*8项，可以看出由上至下节点ID重合的位数(前缀)不断增加。邻居集合中的节点ID由于来源于应用层，一般没有规律性可循。 Pastry的路由过程如下: 首先，路由查询消息中将携带被查询对象ID(Object Id)，又称消息键值。当收到路由消息时，节点首先检查消息键值是否落在叶子节点集合的范围内。如果是，则直接把消息转发给叶子节点集合中节点标识和消息键值最接近的节点;否则就从路由表中根据最长前缀优先的原则选择一个节点作为路由目标，转发路由消息。如果不存在这样的节点，当前节点将会从其维护的所有邻居节点集合(包括路由表叶子集合及邻居集合中的节点)中选择一个距离消息键值最近的节点作为转发目标。 从上述过程中可以看出，每一步路由和上一步相比都更靠近目标节点，因此这个过程是收敛的。如果路由表不为空，每步路由至少能够增加一个前缀匹配数位，因此在路由表始终有效时，路由的步数至多为logBN。 讨论 Pastry的路由利用了成熟的最大掩码匹配算法，因此实现时可以利用很多现成的软件算法和硬件框架，可以获得很好的效率。 与Chord和CAN相比，Pastry引入了叶子节点和邻居节点集合的概念。在应用层能够及时准确地获得这两个集合的节点信息时，可以大大加快路由查找的速度，同时降低因路由引起的网络传输开销;不过在动态变化的P2P网络中如何理想地做到这一点的确有很大的难度。 Pastry的典型应用包括PAST(参见[5][6])和SCRIBE(参见[7])。 趋势分析 目前DHT算法的发展方向非常多，不断有新的改进算法被提出来。就笔者目前了解到的信息而言，至少有以下一些方向: 接近性(Proximity) 文中提到的DHT算法中，除了Pasrty以外，均未考虑重叠网络拓扑结构与真实的IP网络之间的重合关系。节点之间进行对等通信时，不会考虑优先选取距离自己最近的节点。这样就使得最终形成的重叠网结构混 乱，效率低下。因此如何让节点获得并利用接近性信息就非常重要。 结构化 目前基于DHT的应用尚未大规模展开，很多工程上的细节问题尚待解决。例如:目前有很多种类的P2P 应用，如文件存储和共享、电子邮件、流媒体等。这些应用在处理P2P路由算法、拓扑维护和信息检索上 使用的方法均有很大差别，导致即使是同类的应用也无法实现互通。如何为各种P2P的应用抽象出一个通 用的层次，也是目前研究的热点问题之一。 信息查询 基于分布式哈希表的查询是一种单关键字的精确匹配，尽管相对于非结构化系统它使得系统资源可被确定 性地查询到，但它也极大地限制了查询的应用范围。目前有许多改进的结构化查询算法已经被提出来。 参考文献 David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, Rina Panigrahy "Consistent Hashing and Random Trees:Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web". In Proceedings of the 29th Annual ACM Sym-posium on Theory of Computing (El Paso, TX, May 1997), pp. 654-663. Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan_ "Chord: A Scalable Peertopeer Lookup Service for Internet Applications" SIGCOMM'01, August 2731, 2001, San Diego, California, USA. Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker "A Scalable Content-Addressable Network" SIGCOMM'01, August 27-31, 2001, San Diego, California, USA.. Antony Rowstron1 and Peter Druschel "Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems" Appears in Proc. of the 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001). Heidelberg, Germany, November 2001. P. Druschel and A. Rowstron. PAST: A large-scale, persistent peer-to-peer storage utility. In Proc. HotOS VIII, Schloss Elmau, Germany, May 2001. A. Rowstron and P. Druschel. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. In Proc. ACM SOSP'01, Banff, Canada, Oct. 2001. A. Rowstron, A.-M. Kermarrec, P. Druschel, and M. Castro. Scribe: The design of a large-scale event notification infrastructure. Submitted for publication. June 2001. F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica. Wide-area cooperative storage with CFS. In Proc. ACM SOSP'01, Banff, Canada, Oct. 2001. Keith W. Ross, Dan Rubenstein, "P2P Systems" 宁宁，“对等网络组通信机制的位置感知技术研究Research on Location-Aware Tech-nology in Peer-to-Peer Group Com-munication Mechanism”，申请清华大学工学硕士学位论文，May.2005. 李祖鹏，黄建华，唐辉，“基于P2P计算模式的自组织网络路由模型”，软件学报， 1000-9825/2005/16(05)0916 胡进锋，郑纬民(清华大学计算机系高性能计算研究所，北京，100084)，“p2p系统结点信息收集算法 Node Collection Protocol in P2P Systems” 邹福泰，马范援(上海交通大学计算机科学与工程系)，“基于分布式哈希表的对等系统关键技术研究RESEARCH ON THE KEY TECHNIQUE OF PEER-TO-PEER SYSTEMS BASED ON DISTRIBUTED HASH TABLE”，申请上海交通大学博士学位论文，二零零四年十一月