优化D2B覆盖网络路由的方法

摘 要：D2B是基于de Bruijn图的内容寻址网络。它利用分布式哈希表（DHT）实现了文件消息和存储位置的有效映射。D2B具有良好的容错性和可扩展性，是完全自组织的覆盖网络。然而，它没有有效地解决系统的路由和负载均衡。本文中，我们对D2B的路由和负载均衡提出了一些改进：通过增强的de Bruijn （EB）优化路由链接和负载；利用最短标识符优化路由并且用最短标识符扩展优化负载均衡。标准的D2B路由算法是利用de Bruijn图完成的，而我们的算法（ED2B）利用增强的de Bruijn图实现。利用EB，当节点数达到2i （i是非负整数）且系统中所有节点的标识符长度相等时，所有节点的度相同，因此系统达到了较好的负载均衡。

关键词：D2B；de Bruijn图；覆盖网络；负载均衡

1. 引言

在结构化P2P系统中，每个节点只存储特定的信息或特定信息的索引。当用户需要在P2P系统中获取信息时，它们必须知道这些信息（或索引）可能存在于哪些节点中。由于用户预先知道应该搜索哪些节点，避免了非结构化P2P系统中使用的泛洪式查找，因此提高了信息搜索的效率。但是，结构化P2P也引入了新的问题：首先，既然信息是分布存储的，那么如何将信息分布存储在覆盖网中的节点上。其次，由于节点动态的加入和离开覆盖网，如何将拓扑的更新信息通知其他节点。DHT的引入基本解决了上面的问题，因此自从DHT协议出现后，结构化P2P的应用得到了快速的发展。如：Tapestry，Chord，Pastry和CAN等都采用了较为成熟的DHT协议。

P2P系统最基本的问题是如何高效地查找到存放文件的节点。D2B是基于de Bruijn图的内容寻址网络，它利用DHT实现了文件信息和存放位置的有效映射，具有良好的可扩展性和容错性，是完全自组织的覆盖网络。负载均衡是P2P系统设计时需要考虑的公平性问题之一。在D2B中，节点的负载表现为其标识符的长度。本文对D2B的路由和负载均衡提出了优化措施：利用最短标识符优化路由并且用最短标识符扩展优化负载均衡。

2. 优化D2B

本节提出了两种对D2B的改进措施：通过采用最短标识符提高路由效率和应用最短标识符扩展均衡负载。

2.1 利用最短标识符提高路由效率

d-维的D2B系统中节点的标识符是基为d的de Bruijn串，且根据标识符和de Bruijn图的链接规则组织节点。节点的标识符也是其所占区域的标识，标识符越长，节点所占的区域越小。在D2B系统中的路由策略和de Bruijn图相似，路由到目的地S在唯一的节点u处停止，此节点的标识符是S的前缀。本文中，我们提出一种利用最短标识符的新颖的路由算法。也就是说，当节点路由消息时，它们选择一个具有最短标识符的邻居节点。这样做的理论依据是：在系统中，节点拥有的标识符越长则其所占的区域越小。所以按节点最短标识符路由经过的节点数必然减少。

令lengthmin是具有最短标识符的邻节点拥有的标识符长度。路由操作如下：

{

Set lengthmin=0；

For （所有邻节点）

If （第i个邻节点的标识符长度

Set lengthmin=第i个邻节点的标识符长度且向它发送请求；

}.

2.2 利用最短标识符扩展均衡负载

由于在D2B中节点的负载可通过标识符的长度来表示，因此，我们提出一种最短标识符扩展的方法均衡负载。下面我们简单地介绍利用最短标识符扩展均衡负载的措施。

当新节点加入系统时，加入消息发送给一些随机的没有失效的节点。在D2B系统中，已存在节点不仅知道自己的标识符，还知道其邻节点的标识符。因此，新节点最终找到一个节点u，此时并不是直接扩展节点u的标识符，而是比较节点u和其各邻节点的标识符长度，然后选出一个标识符最短的节点进行扩展。这样就可获得更好的均衡性。

当节点离开系统时，需要为离开的节点找取代点。这将引起标识符的合并。为了有更好的负载均衡，D2B试图合并具有最短标识符的节点。离开节点产生一个离开消息。从此节点开始向具有较短标识符的邻节点发送离开消息，一直到达不再有更短邻节点的节点，并为此节点找到一个关键对。然后合并具有最短标识符的关键对。在离开过程中，一旦离开消息发送一次，节点标识符的长度至少减少一位。

由于使用均衡的哈希函数将键值分配在节点空间中，键被系统中当前的节点管理当且仅当此节点是键的一个前缀，故各节点保存的键值数目与节点标识符长度成正比。也就是说，节点的标识符越长，该节点承担的负载越小。因此，最短标识符方法使得D2B系统得到了较好的负载均衡。

3. 结论

P2P系统在传统的客户/服务器系统上提出了大量的改进，如可扩展性、容错性和自组织性。然而，此系统对处理安全性、路由效率和负载均衡问题仍存在很大的挑战。

本文给出了改进D2B的负载均衡和路由效率的两种措施。根据我们的方法，它有效地改进了系统的路由效率和负载均衡。