通过DHTS（分布式散列表系统）引导P2P控制传输

通过DHTS（分布式散列表系统）引导P2P控制传输

Jaroslaw Adam Gralak, Adam Wierzbicki

摘要----近年来，P2P覆盖层拓扑优化已经成为日益重要的焦点。现在P2P系统已经拥有相当数量的合法应用，但是这些系统仍然不能满足对于许多应用和网络提供商至关重要的两个要求：有效利用广域网资源和通过减少路由伸长对查询提供快速的响应。

这篇文章展现的DHTS系统利用IP层引导现有结构化P2P系统。DHTS旨在改善整体系统反应，通过拓扑感知优化，减少资源本地化加工持续时间。

关键字---拓扑优化；L3集成；结构化的P2P网络

I 引言

拓扑优化问题在早期的P2P系统设计和发展中就成为争论的焦点。研究者主要聚焦在P2P数据传输的的路由优化上，当然这是因为P2P数据传输能明显的降低网络的利用。然而很少有人关注P2P控制信息的优化，它影响资源本地化处理的整个时期。

本文介绍DHTS，是P2P控制协议查询加速器。DHTS是一个创新的P2P路由层。它与网络的TCP/IP堆栈层（L3）协同工作。DHTS可以这样理解：它是由某一网络提供的适用于任何应用的服务，它优化结构化的P2P协议。它同时也可以用来建立分布式查询服务。DHTS的高效源于其独特的设计，由HT覆盖层激励。与其他解决方案不同，DHTS可以在查询路由阶段引导P2P传输-----通过DHTS所在网络的分块。P2P协议利用DHTS不需要做任何扩展。

与其他拓扑优化方案不同，DHTS不依赖于由对信号站的测量或者L3的“神谕”得到的信息，正相反，它运行在IP路由器上，通过P2P包选择性优化已选择路径。设计这样一个系统主要的体现在于克服部署的障碍和保持路由层的扩展性和效率。DHTS的设计解决了上述问题。DHTS是高效的、可扩展性的，因为DHTS无状态，使用最好的网络资源，并且利用标准的现场已证实的解决方案，像现在被每个现代路由器支持的IP路由器警告选择。另外，由于DHTS没有必要运行在每个路由器上，因此它在网络层上占用极少的开支。DHTS可以只工作在选定的路由器上，但已经足以高效的引导P2P传输。最后但同样重要的是，DHTS可以在不影响现存P2P传输的情况下很容易地、逐步的部署。

2综述

DHTS这个概念结合了经典的平面地址空间路由与标准IP路由元素。与DHT覆盖层相一致，DHTS使用平面地址空间作为节点和关键字的标识符，但是与那些协议相比之下，并没有对覆盖结构施加任何规则。DHTS，作为一个结构自由协议，将保持节点间连接的任务转移给了SMP（结构管理协议），SMP是一个单独的专门的P2P协议，例如Kademlia。

DHTS路由表中的路由基于它们的源是分割成单独的类（集合）。当前的两个集：vset和tset，将来可能还有扩展。Vset是唯一的一个强制的集合，它取决于选定的SMP。结构管理协设计的不同导致初始化vset不同。例如，在Chord中，作为SMP的脚本，vset将会包含Chord指数表。DHTS拓扑认知通过tset方式实现。Tset基于IP路由协议提供的数据计算。

P2P控制包以一跳接一跳的方式引导，直到它们的路径得到优化并且没有其他优化可做或者最终的目的达到为止。通过将下一跳与目的地址比较，DHTS可以识别出某一控制包是否还需要优化。不论何时存在通过进一步的优化可以缩短路由路径，即当目的地与吓一跳地址不同的时的解决方案，实现DHTS的路由器会在IP控制包发送出去之前在其上标记NO（not optimal）作为IP_RA[6]（IP路由警报选择）实现。通常在RSVP（资源预留协议，译者注）中使用的IP_RA选择暗指控制包应该由实现IP_ RA的中转路由器严密检查。基于NO存在标识的中转DHTS路由器能够在IP控制包上执行优化尝试。

3DHTS

A． 架构

由客户端产生的查询基于DHTSL3网络元素（超级对等网络中）得到路由。DHTS包括四个单独的逻辑组件，分别是DHTS路由器，代理，门和一个客户端。

图1（a）客户端，门及代理之间的关系。（b）CNP和NNP

客户端通过当前未定义的CNP（客户端-网络协议）连接到DHTS代理。CNP的主要目标是键值的广播，从客户端应用程序到代理（Proxy），这个客户端应用程序即一个P2P共享文件程序。此外，DHTS代理处理客户端的查询请求。客户端应用程序可以利用CNP自然地连接到代理，应用程序不支持CNP的情况下，是通过Gate（图1a）与代理相连。Gate（门）是一个逻辑组件，负责应用程序具体请求到响应CNP请求间的翻译，然而代理为用户建立DHTS存在的点，并且代表客户端负责查询DHTS网络。

CNP用来做客户端-代理通信，然后NNP（网络-网络协议），如图1b，用来做代理-路由器通信。NNP是一种简单的、可扩展性的、轻量级的DHT（分布式散列表，译者注）管理协议，它提供GET/PUT功能与相关数据（元信息）进行查询和存储键值。为了查询DHT服务，代理服务器必须对DHTS网络有些许了解并且至少有一个DHTS路由器指向附近其他DHTS路由器。代理能够作为后台程序运行在附近专用的服务器上，或者集成到边缘DHTS路由器。

节点和键值的标识符使用无符号整型。键值与节点共享同一平面标识空间。标识符是固定并且位置独立的。另外，路由器的标识必须是唯一的，举例来说，能够通过散列RID（Router ID） IP地址获得。

DHTS路由器提供一组键值，这组键值已经映射其上并且参与NNP路由。键值是基于与路由器的DHTS标识接近程度来决定映射到某一路由器。接近度依赖于选定的SMP，例如可以使用两标识符作差的绝对值或者两标识符的异或结果。

B． 路由

DHTS由若干组件构成，其中路由子系统与NNP最为重要。DHTS构建于IP层上，并且定义了单独的协议用来负载NNP控制信息。如get，reply，put，put_ack这样的控制信息都作为DHT管理协议。

无论何时，当DHTS代理（源）发送以控制信息到另一代理（目的地）时，通过该信息的路由，源与终点的定位，路由器可能会通过将信息的下一条的值域改作离目的地更近的节点的值改变信息在网络中的传送。关于下一跳的改变或者是由于路由，或者是由于所谓的路由优化处理的结果。DHTS路由就是一通向终点过程中路由器之间转送NNP控制信息的过程。它的路由算法相当简单。协议信息贪婪的向具有最近标识符的节点路由，直到到达终点为止。路由发生在每当非终点且具有DHTS能力的路由器接收到NNP包时，NNP包将自己定位到IP层，但当转发到另一DHTS路由器时，是定位在DHTS层。非终点路由器必须通过查询DHTS路由表，然后将NNP包转发到离终点近的DHTS路由器。

DHTS的设计因经典网络重构层的差异而不同，因为DHTS包由IP路由器与常规IP传输协同处理。每一具备DHTS功能的路由器至少维护两个单独的路由表：IP路由表与DHTS路由表。DHTS路由表是独立路由集合的总和。每一路由集中的路由路径的数量因不同的节点而不同并且依赖于节点在网络中位置。

C． Tset

拓扑集是可选的路由集，它与到附近具有DHTS功能的的路由器的路径数量正相关，它用来改善路由优化效率的。DHTS既不定义也不强加任何路由选择标准。因此，tset的内容依赖于网域政策并且是政策的贯彻者。Tset可以由不同源包括但不仅限于IGPs（即来自TED/LSDB）,MPLS标签分发协议（即特殊目的的LDP TLV，它们广播元组），BGP（专门的SAFI），PCE[10]，DHTD静态路由（）或者任何上面的组合。

D． 优化

DHTS优化在两两面与DHTS路由不同。首先，某一优化只适用于在IP报头设置IP_RA选择来转发NNP包。然后，如果NNP包已经在遵循某一优化的路径择本次的优化尝试可能不会成功。因此，不是所有控制包都受到DHTS路由优化处理的支配。IP_RA选项只为get和put包设置，因为为这些包类型做的路由不能保证是最佳的。其余的DHTS包类型，如reply，put_ack总是遵循IP最短路径，因此没有必要再做优化或者DHTS路由。

Figure2 shows how both processes work in practice by illustrating how get, and generated in response reply, messages traverse the network。图表描述了一个包含8个路由器，其中6个运行DHTS协议的网络的一部分。示例中的SMP拥有8bit的平面地址空间来标识键值和节点ID，并且使用两标识符差的绝对值作为距离（权值，译者注）。

关系每一个具有DHTS能力节点的路由表在节点上是以destination_id->Next-Hop_IP（由于受到抵制空间的限制，只呈现IP的最后八位）元组的形式呈现。SMP在标识符虚拟环上建立到后继与前驱的路由（with wrapping around zero：译者以为大概意思应该是负数表示前驱，整数表示后继）。除此之外，一些节点还拥有从其他路由集中得到的路由表入口。

最左侧的路由器由id0x55标识，并且以RID为192.0.2.10作为DHTS代理。让我们假设，0x55节点在客户端做查询操作，终点具有的键值是0x8A，存储在标识符为0x88节点上。本事件的顺序看似应该是：a)代理/路由器查询路由表，然后发送NNP get信息，该信息带有IP_RA设置，拥有在DHTS层（dhts_dst）上标识为0x8A（键值）的终点地址，并且设置IP目的地址为最近（以两标识符之间差的绝对值为标准）的DHTS路由器0x60，这个路由器作为下一跳；b)由于192.0.2.133不支持DHTS，因此只是普通的IP路由；c)路由器0x60接到get消息，然后将它（DHTS路由）指向节点0x73，同时改变DHTS下一跳为0x73，并且修改相应的IP源/目的地地址；d)普通IP路由；e)具有DHTS能力路由器0x1F基于IP_RA序列拦截NNP

图2 NNProuting and optimization

包，优化尝试未成功（没有更好的方式），因此没有对DHTS/IP下一跳/目的地地址做改变，然后将NNP包发送到0x73；f)0xC3路由器拦截数据包（IP_RA）并且成功做了优化，改变了DHTS下一跳的值，同时改变了IP src/dst（源/目的地）地址；g)由于f中的成功优化get消息经由选定的路由而不再到达0x73；h)0x88收到get消息，执行关键字查询，然后直接向代理发回相应信息reply，而不再有IP_RA(常规IP路由)（路径已经选好，译者注）。

E．  执行

传输引导系统的到来并不是免费的。DHTS在路由器的控制与转发计划上提高资源的利用率[11]。控制计划维护DHTS路由表、相关键值并且运行结构管理协议。控制元素也期望填入可选tset（使用一项或者几项技术的组合，将在第三部分C中提到）。

转发计划必须适应DHTS转发表并执行实际的路由和NNP包的优化。Processing NNPrequests send directly to router or with IP_RA option set implies handlingexception packets.这些数据包必须在PFE（Physical Forwarding Element）网络处理者水平检测或者发送到控制元素作路由/优化决断。现代路由器架构经常提供专门的高扩展性的硬件以PFE水平来处理不同类型的异常包。由于这样的硬件的帮助，控制简化得以卸载。

尽管DHTS使用控制和转发计划资源，但是它还是相对轻量级的，因为路由和优化处理的目标只是控制包而不是数据包。一次DHT查询操作只需一次get消息（如果没有流行的DHTS代理准备就绪），考虑到核心平均长度一般转化成~3-6跳，评估结果显示需要1-4次在非终点路由器上的优化尝试（IP_ RA）和~2次DHTS路由事件包括在终点上的关键字查询操作。其余的查询资源（如put_ack，译者注）和数据传输过程不需要转发路由器的参与而是仅仅依靠IP单播数据报。

4评估

我们使用ns-3[12]做模拟实验评价DHTS。我们的测试主要集中在NNP协议和它的传输引导系统上。基于这个目的，NNP与作为结构管理协议的Chord[5]一起在ns-3.3RC2上实现。之所以选择Chord，是因为不仅因为它众所周知、评估简单，而且相对容易实现。我们利用后退指数扩展和建立顺逆时针方向路由来实现Chord。

所有的测试均运行在人工产生的网络拓扑上，这样的设计是基于普通ISP core/aggregation（核心/凝聚）模型，鉴于冗余考虑，每一凝聚路由器都至少连接两个核心节点。拓扑结构是利用IGen[13](v0.12)产生的，分别使用K-Medoids(聚类相似度得算法，译者注)和Spint（数据挖掘中的分类算法，译者注）作为聚集和筛选方法。除了用于物理网络拓扑结构的产生，IGen还用在了L3网络的设计上。在设定的网络中，节点的数量设置为800，这个数字比当前平均ISP基础规模还要大。我们选择OSPF（开放式最短路径优先算法，译者注）作为IGP（内部网关协议，译者注），之所以这么选是因为IGen与ns-3支持。由K-Medoids产生的节点簇集组织在各个OSPF区域。这个方案反映出真实的网路设计，即地理位置相近的节点通常隶属于同一IGP区域并且通过低廉的连接成本在内部互通。

Tset基于IGP连接状态数据库内容产生。这是内部网域DHTS模拟的自然选择，因为已经在使用的是OSPF算法。OSPF以不透明扩展[14]的方式促进承载辅助的路由数据，这种不透明扩展定义了三种附加的LSA（链路状态广播，译者注）类型---link（type 9）、area（type 10）、domain（type 11）洪泛领域。我们认为LSA type 10（广泛应用于推进在MPLS/RSVP-TE 环境下的TED数据库）可以胜任这项工作，因为在同一区域内的路由器通常在地理位置上都是相近的，所以位置得以确保。因此，我的方案利用OSPF LSA Type 10承载DHTS元组。

我们测试过程中假设网络的中心和聚集部分比起系统的终端相对稳定。因此，我们不准备做任何搅动或者系统分离测试（就是说不去测试其他情况下，也不单独测试某一部分）。这些事件的类型只影响vset和它们的结果，取决于选定的SMP，这些内容超出了本文的范围。

A． 节点密度与tset规模

经过上述一系列的试验，我们研究了DHTS节点密度与P2P查询传输引导之间的关系。主要目标是为NNP包确定若有被动扩展时同一区域内多个DHTS路由器之间可能存在的交互关系，确定包数据经过的跳的数目与源与目的地之间最短路径长度的比率。另外，我们根据成功优化尝试的数目来测量DHTS路由优化处理的效率。

由于节点密度与tset效率彼此相互依赖，我们将它们结合在一起测试。我们在同一拓扑结构上做了一组共12次试验，根据特定的场景，这个拓扑结构分为5,10或20个不等的区域，使用OSPF中心区域互联。每一个上述场景都由四种专门的密度变式对比测试，分别是网络中的25%、50%、75%和100%的DHTS节点。支持DHTS的节点每次都是以给定的百分比从800节池中随机挑选。

我们通过追踪NNP get 控制消息在DHTS路由器之间转发，对优化处理和被动扩展做密度效果测试。只有get和put消息经历进一步路由优化，而其余的消息（reply和put_ack）遵从最短IP路径设计，这是一个符合人的理性的选择。每一项测试都包括两个阶段，即初始化和测试阶段。在初始化阶段，5000对DHTS代理和键值存储路由器随机的从所有能用的DHTS节点池中挑选出。代理路由器充当客户端（源），向关键字（存储在目的路由器上）产生查询信息（NNP get 消息）。测试阶段包括一条5000关键字的请求序列，每一关键字请求都在不同的源/目的地元组之间。

Figure 3. Stretchin relation to DHTS node density and the number of areas

Figure 4.Optimization effectiveness in relation to DHTS node density and number of areas

Figure 5. (a)Stretch and (b) successful optimization rate depending on DHTS-enabled routerlocation

图3中的结果显示了DHTS节点密度与被动扩展值之间的交互关系。在每一场景中，节点密度的增加总是伴随着扩展值的减少。这是由于优化处理的结果。如果NNP get 或put 消息经过DHTS路由器，则该消息就会得到优化。DHTS节点密度越高，消息经过这些节点中的一个时，得到路由和成功优化的机会就越大。

另一个观察结果是在被动产生的扩展的密度效果严重地依赖于L3网络的设计。当路由网域被划分为较少数量的区域时，整体的扩展比在较多数量区域时低得多。这是由于tset在路由和优化处理中的规模和地位所致。括约DHTS路由器较多的区域产生较大的tset数据库，这有助于提高路由和优化处理的效率。

DHTS节点密度的显著性在一些情景中下降，这些情景是中路由网域分成小数量的区域，自然每个区域内的节点数量就是相对多。对于5个和20个区域的场景，扩展值在25%与100%密度变式之间，平均差值是0.06与0.17。这一发现可以由前面提到的tset规模因素与其在路由和优化机制的效率解释。

扩展测试同时，我们还研究了成功优化尝试的数目与节点密度之间的关系。每当NNP包的目的地被执行优化的路由器改变，则表示优化尝试成功。图4的结果表明通常优化尝试在较低密度的变式下更容易成功。更甚者，当路由网络被划分为较多数量的小区域时，优化尝试更容易成功。上述的发现归根结底都是tset的规模因素。

B． 节点位置

接下来的一系列试验的目的是为了测试节点的位置因素和它对P2P查询传输引导系统影响。我们的测试运行在具有800节点、10%（80）DHTS路由器的网络中。所有的节点分成10个L3路由区域，通过共同的中心区域相互联系。取决于具体的场景，所有80个DHTS路由器可以都是从区域边界路由器（ABRs）中选出，或者是路由器是平常区域的一般路由器，或者，最后一种情形，是从800个节点中随机选出。除了固定节点位置外，我么主要使用在4.A中提到的两阶段测试步骤。对每一测试，分别记录扩展值和各种优化参数。

图5显示了扩展测试结果（a）和成功优化率（b）。当DHTS路由器都选自ABRs池时导致的扩展明显比其他场景低。这是由于ABRs的位置大大减轻了DHTS优化处理的困难。ABR参与区域间的路由并且它的tset数据库建立了它从属的每个路由器。前一个原因（每一个NNP包，携带IP_RA选择设置，都通过ABR路由）是DHTS优化处理的动机。后者提够了成功优化的机会。

Figure 6.Comparison with Chord

测试扩展的同时，我们还测量了成功优化尝试率，使用与在4.A中相似的方式。结果与在扩展测试中的测量值一致并且表明在ABR场景中成功优化率较其他节点布局都要低。有两方面的原因。第一，从具备DHTS能力的ABR路由器始发时，更多的NNP包遵循原来的优化路由（L3 IP最短路径选择，译者注）。第二，每当NNP包到达ABR并且经历优化处理时，很大的可能是路由已经非常接近最优，因此进一步的优化尝试可能不会成功。

C． 与分布式结构化P2P协议的比较

与其他的出名的P2P系统比较对于评价DHTS的设计目标（比如，路由优化、最小延迟和使用网络费用较低等）是否达到何有必要。我们测试以Chord[5]SMP的DHTS，并且与不依赖于DHTS的单独版Chord模拟结构比较。二者均使用第四部分引入的后退指数扩展，分享相同的32为关键字长度。

Chord测试的结果产生的拓扑结构分别用到有无DHTS支持两个场景中。前者利用传输引导系统，以25%的节点（随机选择）密度变式，使用SChord作为SMP。后者只依赖Chord。我们测试的焦点在于资源定位处理和4.A描述的两阶段步骤的分析。

图6得到的结果表明DHTS更高效。当使用DHTS P2P查询传输引导系统时，导致的扩展明显较低。Chord的得分糟糕，主要但不仅仅在缩短2-5跳的路径上，原因在于重构层本质上。即使Chord所要查询的节点就在路由器Chord附近，除非有一个直接的指数，Chord也不会察觉而且常常必须将包发送到远端节点，从IP视图上，发送到的这个节点在虚拟的标识符环上看与目的地较近，而且很可能之后会折返（从IP透视图上看）到正确的节点。DHTS通过执行必要的优化避免了P2P控制查询消息“来来回回”传输，这样做抛弃了核心的链路，降低了资源定位延时。

5.结论与进一步工作

本文提出了DHTS,这个全新的拓扑感知P2P控制传输引导系统。DHTS的设计遵从IP网络原则：DHTS NNP是无状态、轻量级协议（在路由器上施加极少开销）。不止如此，DHTS可以很容易地、逐步地部署到现有网络。模拟结果显示，DHTS能够有效引导传输，即使在网络中很小的一部分。

DHTS明显的应用是高效分布式目录，如P2P-SIP分布式注册服务。直到现在，P2P系统主要的被认为是应用层得重构网。试图使P2P系统拓扑感知通常以修理重构层拓扑结构的形式。毫无疑问，我们DHTS的设计可以改善，系统还需要大量的进一步工作—当前，最重要的工作是表明，DHTS确实可以在IP层融入到结构化P2P路由当中。

深入工作包括研究DHTS如何应用到非结构化的网络中。

参考文献

[1] H. Xie, A. Krishnamurthy, A. Silberschatz, and R. Y. Yang, “P4p:Explicit communications for cooperative control between p2p and network providers.”

[2] “Application-layer traffic optimization.” [Online]. Available: www.ietf.org/html.charters/alto-charter.html

[3] V. Aggarwal, A. Feldmann, and C. Scheideler, “Can isps and p2p users cooperatefor improved performance?” vol. 37, no. 3. New York, NY, USA: ACM, 2007, pp. 29–40.

[4] A. I. T. Rowstron and P. Druschel, “Pastry: Scalable, decentralized objectlocation, and routing for large-scale peer-to-peer systems,” in Middleware ’01:Proceedings of the IFIP/ACM International Conference on Distributed SystemsPlatforms Heidelberg. London, UK: Springer-Verlag, 2001, pp. 329–350.

[5] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan,“Chord:A scalable peer-to-peer lookup service for internet applications,”in SIGCOMM ’01:Proceedings of the 2001 conference on Applications,technologies, architectures,and protocols for computer communications.New York, NY, USA: ACM, 2001, pp. 149–160.

[6] D. Katz, “rfc2113: Ip router alert option,” IETF, February 1997.

[7] P. Maymounkov and D. Mazières, “Kademlia: A peer-to-peer information systembased on the xor metric,” 2002, pp. 53–65.

[8] B. Yang and H. Garcia-Molina, “Designing a super-peer network,” vol.0.Los Alamitos, CA, USA: IEEE Computer Society, 2003, p. 49.

[9] “Kazaa.” [Online]. Available: http://kazaa.com

[10] J. A. A. Farrel, J.-P. Vasseur, “rfc4655: A path computation element (pce)-basedarchitecture,” IETF, August 2006.

[11] T. A. R. G. L. Yang, R. Dantu, “rfc3746: Forwarding and controlelement separation (forces) framework,” IETF, April 2004.

[12] “Ns-3 network simulator.” [Online]. Available: http://www.nsnam.org/

[13] “Igen.” [Online]. Available: http://www.info.ucl.ac.be/ bqu/igen/

[14] R. Coltun, “rfc2370:The ospf opaque lsa option,” IETF, July 1998.