P2P中有效的广播结构

Efficient Broadcast in Structured P2P Networks | SpringerLink

在这篇论文中，在继续结构化的分布式哈希表P2P网络中，我们提出了有效的执行广播操作的算法并伴随着最小的代价。在一个N个节点的系统，从任意地点发出的广播信息节点经过N−1个消息后到达所有其他节点。我们强调对一类DHT系统的感知形式作为分布式k-ary搜索的一种形式，我们利用这种感知构造一个生成树用于有效的广播。我们认为广播是对现有服务的补充，使用任意的查询进行搜索以及传播全局信息的能力。

1 介绍

P2P系统的研究产生了许多对于数据资源的定位系统。俩个方法被用来解决这个问题；洪水法和分布式哈希表方法。俩种方法的共同特点是构建应用层覆盖网络。表1包含了俩种方法主要的不同

FloodingDHT
QueriesArbitraryKey Lookup
Query-Induced TrafficO(N)O(log(N))
Hit GuaranteesLowHigh
Connectivity GraphRandomStructured

表1：泛洪法 vs 分布式哈希表方法

DHT方法具有结构化覆盖的网络、确定性、相对低的流量和高的保证，在P2P的研究社区中被认为是一个合理的方法，Tapestry，Pastry，CAN，Chord，Kademlia。与此相反，基于泛洪的方法主要被认为是不可扩展的基于流量的一些分析。

大部分分布式哈希表中缺少的一个特性是基于任意查询而不是键查找执行特定搜索的能力。需要提供此功能需要对现有的DHT进行扩展。在泛洪法的系统中，通过广播实现了任意的查询。然而覆盖网络的随机性，使得该方案成本高，保证度低。

在这篇论文中，我们展示了我们在扩展DHT进行有效广播层的工作状态。我们主要在调查，如何利用DHT覆盖网络结构化的特性执行有效的广播。我们提供广播服务作为分布式哈希表（DHTs）的一项基本服务，该服务应当被部署用于任何类型的全球数据传播/收集。

在下一节中，我们将介绍相关工作。在第三节中，我们基于将一类分布式哈希表（DHTs）视为执行分布式k-ary搜索系统的认知来解释我们的方法。在第四节中，我们为其中一种DHT，即Chord，提出了一种广播算法。第六节展示了初步的模拟结果。最后，在第七节中，我们进行总结并展示未来的工作计划。

2 相关工作

我们的工作可以归类为支持任意搜索的分布式哈希表扩展，从这个角度来看，下面的研究有相同的目标。

DHT中的复杂查询。其中，建议对现有DHT系统进行扩展以增加执行复杂查询的能力。该方法通过构造索引允许执行类似数据库的查询。这个方法不同于我们，我们不像DHT添加额外的索引。在撰写本文时，还没有对构建、维护和执行连接操作的成本进行分析。

广播是一种群体沟通的形式，我们可以将这项工作视为群体沟通支持，在这种情况下，下面的研究是相关的。

Multicast：[13,9]中的工作解决了结构化P2P网络中的多播问题，然而，我们还不知道有任何研究解决了基于DHT的结构化P2P网络中的广泛传播问题。

我们的方法

3.1 DHT和分布式k-ary查询

通过观察具有对数性能界限的DHT系统，如Chord， Tapestry，Pastry和Kademlia，我们可以观察到它们背后操作的基本原理是执行一种k-ary搜索。在Chord的情况下，执行二进制搜索。对于其他的系统，类似TApestry和pastry的arity（分支因子）更高。

在这篇论文中，我们将Chord系统感知解释为分布式k-ary搜索中的一个特例，在本文中，我们将Chord系统视为分布式k-ary搜索的一个特例进行解释。这些论述同样适用于更高搜索arity的情况。假设读者熟悉Chord系统和它的术语。我们重申路由表的结构。每个Chord节点有一个标识符，表示它在大小为N的圆形标识符空间中的位置。一个节点保持M=Log2（N）路由条目，叫做手指表。节点n的一个手指[i]表示标识符为$n+2^{i-1}$的节点的地址。如果这样的节点不存在，它在圆空间中被第一个后继者保存。

图1：（a）在一个完全填充的8节点Chord网络中，起源于节点0的查询的决策树（二分查询）（b）相同的查询没有虚拟跳，也是一个覆盖整个系统的生成树

为了描述k-ary查询的想法，而不失普适性，我们假设Chord系统标识符大小为8。系统已经完全填充，即，一个节点表示空间中的每个标识符。在图1.a中，我们展示了从节点0开始，查找查询的决策树。给定对标识符为x的键的查询，节点0开始查询负责x的节点，将所有标识符视作候选标识符。基于关于x的所属区间（arc标签在图1.a），该查询被转发，并重复该过程，搜索范围减小到前一个的一半。因此所有的节点都可以通过查询引导路径最多H=log2（N）跳来到达。

注意一些跳从自身到达了自身，即虚拟跳，图1.b展示了相同的决策树而去除了虚拟跳。对Chord作为k-ary搜索的感知进行了更详细的解释。

3.2 问题定义

强调了分布式k-ary搜索之后，我们给了如下的问题定义，以及提供了基于k-ary查询的看法。

问题：给定一个由P2P DHT系统构建的覆盖网络，找到一个算法进行消息广播。该算法必须不依赖成员的全局共识，必须对系统中所有成员具有相等的代价。

在这个问题中我们强调p2p假设，即，缺乏中央协调并且每个对等节点遭受的成本相同。

3.3 我们的方案

我们的解决方案基于一个事实，k-ary查询的树实际上是一个生成树。覆盖系统中的所有节点。图1.b展示了k-ay查询决策树的8个节点系统，它也是一个系统的生成树。在下一节中，我们将展示如何用分布式的方式构造此树。

4 广播算法

4.1 系统模型与符号

我们假设一个分布式系统由一组节点建模，这些节点通过通过通信网络传递的消息进行通信：1 连接2要不3可靠4提供先进先出通信。

使用规则的形式描述了运行在系统节点上的分布式算法

$$ \frac{receive(Sender : Receiver : Message(arg_1, .., arg_n))}{Action(s) ....} $$

该规则描述了在Receiver节点上接受消息的事件Message以及为了处理该事件而采取的操作。一个发送者执行语句$receive(Sender : Receiver : Message(arg_1, .., arg_n))$来发送消息到接受者。

4.2 规则

初始化广播 一个广播在任何节点初始化，就如同用户请求的结果。即，用户层级的实体P可以发送节点Q一个信息InitBroadcast(info)其中info是一条必须被广播的消息，任意的搜索查询统计查询，通知等。

receive(P : Q : InitBroadcast(Info))
for i in 1 to M − 1 do
    //Skip a redundant finger
    if Finger[i] != Finger[i + 1]
        R := Finger[i]
        Limit := Finger[i + 1]
        send(Q:R:Broadcast(Info, Limit))
    end
end
//Process the last finger
send(Q:Finger[M]:Broadcast(Info, Q))

图2 初始化广播信息

节点Q的作用是作为生成树的跟。如图2中的规则所示,Q通过向所有邻居发送Broadcast消息来实现这一点。记住，除非标识符空间被完全填充，Chord手指表包含了许多冗余的手指。对于冗余手指的序列，最后一个被用于转发其他的则被跳过

一个Broadcast信息包含了要被广播的info和Limit参数。Limit用来限制接受节点的转发空间。Finger[i]的Limit是Finger[i + 1]，（1 ≤ i ≤ M − 1）其中M是路由表实体的数量。最后的手指limit是一个特例，其中Limit是一组转发者的标识符。例如我们使用在3.1章中给出的简单的Chord网络，当节点0初始化广播，它想把它扩展到整个标识空间。它发送给节点1,2,4。分别给出2和4和0的limit。这样做实际上是在指示节点4覆盖区间 [4, 0)，即一半的空间。它还指示节点4覆盖区间 [2, 4)，即四分之一的空间，最后，指示节点1覆盖区间 [1, 2)，即八分之一的空间。

处理广播。当节点Q接收到一个 Broadcast(Info, Limit) 消息时，它负责在一个由区间 (Q, Limit) 限定的子树中进行广播。除了跳过冗余的指针外，Q 还会将消息转发给所有标识符位于 Limit 之前的指针。此外，在向任何指针转发时，它会给该指针提供一个 NewLimit，以定义一个更小的子树。请注意，这只有在 NewLimit 属于 (Q, Limit) 区间内时才会发生，即 NewLimit 不会超过由父节点给出的 Limit。如果 NewLimit 超过了 Limit，则使用父节点给出的 Limit。下图包含了处理广播消息的规则。

receive(P : Q : Broadcast(Info, Limit))

for i in 1 to M − 1 do
    //Skip a redundant finger
    if Finger[i] = Finger[i + 1] then
        //Forward while within ”Limit”
        if Finger[i] ∈]Q,Limit[ then
            R := Finger[i]
            //NewLimit must not exceed Limit
            if Finger[i + 1] ∈]Q,Limit[ then
                NewLimit := Finger[i + 1]
            else
                NewLimit := Limit
            fi
            send(Q:R:Broadcast(Info,NewLimit))
        fi
        else
        exit for
        fi
    fi
end
//Process the last finger
if Finger[M] ∈]Q,Limit[ then
    send(Q:Finger[M]:broadcast(Info, Q))
fi

图3：处理广播消息

复制 我们考虑将回复广播源的问题视为一个独立的问题，它依赖于 Broadcast 消息的 Info 参数。对于回复可以考虑几种策略，例如：

(i) 在每个广播消息中附带广播源的信息，这样希望回复的节点可以直接联系到广播源； (ii) 回复通过相同的生成树传播回根节点。

5 成本与担保

例如，在Chord系统中，假设我们有一个8个节点的环形网络，标识符空间大小为8。如果节点0发起广播，它会向节点1、2和4发送广播消息，并分别为它们设置 Limit 为2、4和0。这意味着：

  • 节点4需要覆盖从4到0之间的区间（即另一半的环）。
  • 节点2需要覆盖从2到4之间的区间（即四分之一的环）。
  • 节点1需要覆盖从1到2之间的区间（即八分之一的环）。

当这些节点进一步转发广播消息时，它们会根据各自的 Finger 表来确定新的 NewLimit，并且这些 NewLimit 会继续缩小，直到消息到达目标区间的末端。通过这种方式，Limit 的作用是逐步缩小广播的范围，而不是扩大，从而有效地控制了消息的数量，保证了广播的高效性。

在提出针对基于DHT的P2P网络中广播的一个高效算法时，我们意识到N-1条消息的成本，特别是在大型P2P系统中，对于许多应用来说可能是难以承受的。关键在于我们提供广播作为一种基础服务，对于愿意承担此成本的对等节点（Peer）来说是可用的。我们的算法提供了强大的保证和为此承担的成本下的流量利用效率。为了在一个与我们相同大小的Gnutella风格的网络中提供相同的保证，需要支付显著更高的成本。下一节将更详细地讨论这种比较。

可预测的保证。如第4节所述的广播提供了强有力的保证，因为它遍历了网络中的每一个节点。可以对算法进行小的修改，以确定性地减少广播的范围，从而提供较弱但仍然可预测的保证。例如，通过仅发送给最后一个（或除最后一个以外的所有）指针来启动广播，这样只能覆盖网络的50%。类似的剪枝策略可以根据需要应用以实现不同的覆盖率。

不同的遍历策略。该算法还可以被修改以支持迭代加深策略。此策略在[14]中被建议用于非结构化的覆盖网络。我们认为，将这一策略与我们的算法相结合可以降低消息传递成本，尤其是在一个查询命中就足够作为结果的情况下。

6 模拟结果

7 结论和将来工作

在这篇论文中，我们展示了我们在扩展DHT为一个能够有效进行广播工作的进展。我们的方法主要依赖于对，Chord，Tapestry, Pastry, and Kademlia等系统作为分布式k-ary查询的感知。我们展示了如何遍历搜索树从而构造一棵包含DHT构成的覆盖网络中所有节点的生成树。

我们所有的实现都是基于Chord作为一个简单系统来实现二分查找。在之后的文章中我们打算阐述如何在更高的系统中构造生成树。

我们提出了一些策略，通过这些策略，部署搞笑的广播算法可以通过修建生成树来减少其范围，以产生更少的流量，然而，有能力确定广播中覆盖的网络成员的百分比，从而提供可预测性的保证，需要做更多的实验来评估这些策略。

对于动态网络（join / leaf）的问题，我们认为我们的算法将与底层DHT系统一样出色，知道节点的路由表是不断变化的，需要更多的实验结果来量化过时路由表对高效广播算法提供的属性的影响。

Last modification：January 2, 2025
© Allow specification reprint
如果觉得我的文章对你有用，请随意赞赏