单一子流上传P2P覆盖网络中配置对等端的方法和设备

摘要

本发明涉及一种用于配置包括流源和布置在分布层中的多个对等端的P2P覆盖网络的方法和设备，该流源布置为将准备流播的数据内容分成一起形成数据内容的多个内容子流并且分发该多个内容子流到网络对等端。该方法包括确定单个对等端准备布置在复数个分布层的哪个层中，并且将这些对等端组成多个对等端组的步骤，每个对等端组由来自相同分布层的对等端组成并且被进一步布置为负责分布相应的内容子流。并且，给每个对等端组分配任务，即分发所述相应内容子流给布置在相同分布层中的其他对等端组的对等端以及给布置在紧接后续层中的、进一步属于负责该被分布的相应子流的对等端组的对等端。

说明书

技术领域

本发明涉及一种配置P2P覆盖网络的方法和设备。

背景技术

对于传统客户端-服务器架构网络中的实时流媒体，流媒体视频从流媒体服务器 (即流源)下载到客户端。视频流由一组连续数据块或数据子集组成，客户端通过 周期性请求以播放视频。可扩展的实时流媒体服务需要高的流媒体服务器带宽以满 足因特网上越来越多的客户端。为了降低流媒体服务器的成本，对等(P2P)实时流 媒体已经被开发。P2P实时流媒体的基本概念是使客户端，本文中被称为对等端，与 流媒体服务器共享负载。

P2P实时流媒体系统在近些年来被越来越被引起兴趣，因其具有不必提供所有需 求的带宽就可以将流源(例如直播视频)数据内容传播给大量对等端的优点。这是 通过利用对等端的上传容量帮助流源将数据内容传播给对等端来完成的。

P2P网络包含了由实体组成的任何网络，每个对等端可以让其它对等端访问其一 部分资源(例如处理容量、盘存储、和/或带宽)。P2P概念不同于传统客户端-服务 器架构的网络，其中一个或多个对等端(例如计算机)可以在网络中为其它对等端 服务。通常，P2P网络中的对等端运行相似的网络协议和软件。P2P网络的应用不计 其数，例如，其可以在英特网上传输和/或存储数据，比如为内容所有者传播视频。

现有技术中已经研发出许多方法来高效地利用对等端的上传容量，这些方法主 要分为两种：

基于树的系统是以覆盖网络中的一个或多个构造树为基础构建的，其中在每个 树上部的对等端供应下方的对等端。该方法在对等端于高频状态时没有连接系统或 者离开系统时工作良好，因为对等端之间不需要进一步的信息就可以获得数据流。 然而，在高冲击环境中，树的维护是非常昂贵的，甚至有时候需要摧毁和重建树。

基于网格系统不需要树的构建，换句话说对等端连接不形成特定覆盖，并且对 等端之间是非结构化相互连接。对等端通过所谓的流言通信或者通过彼此发送数据 请求消息来交换数据。基于网格系统的缺点在于，由于各节点间需要相互协商来找 到对等端，对等端的相互连接需要较长的建立时间。然而很多系统都使用这种基于 网格系统，因为它能耐受高冲击环境。在该系统中每个对等端具有多个潜在地可用 来下载数据的相邻对等端，因此任何相邻对等端出现故障不会像基于树的系统那样 严重。

虽然基于网格系统中的单个对等端不需要考虑全局，但是考虑到节点活动，其 仍然可以达到与基于树的系统相当的节省，这主要是因为基于网格系统不需要维持 全局连接结构的日常开销。

在基于树的系统中，视频流可以分成若干子流或者带条。例如，取代让一个对 等端从相邻对等端下载给定数据内容，它可以从第一相邻对等端下载一半内容作为 一个子流，从第二相邻对等端下载另一半内容作为一个子流。将数据内容划分成若 干个子流具有这样的优点，如果可以仔细地构造拓扑图，那么系统可以变得对故障 更有弹性。对数据内容使用带条的一种已知P2P系统是SplitStream，其中拓扑图设 计为，单个对等端故障仅导致在它的下载对等端中单个带条的丢失。如果子流利用 允许冗余例如多编码描述符(MDC)和前向纠错(FEC)的原理构造，那么单个带 条的丢失将不导致终端用户的视频体验的主要中断。关于SplitStream方法的一个问 题是它在P2P系统中连接对等端方面相对缺乏灵活性。

发明内容

本发明的一个目的是解决或至少减轻现有技术中的这些问题。

该目的在本发明的第一方面，由一种配置P2P覆盖网络的方法来实现，所述P2P 覆盖网络包括流源和布置在复数个分布层中的多个对等端，该流源布置为将准备流 播的数据内容分成可以一起形成数据内容的多个内容子流并且分发该多个内容子流 到网络对等端。该方法包括确定单个对等端准备布置在复数个分布层的哪个层中， 并且将这些对等端组成多个对等端组的步骤，每个对等端组包含了来自相同分布层 的对等端并且被进一步布置为负责分发相应的内容子流。进一步地，给每个对等端 组分配任务，即分发所述相应内容子流给布置在相同分布层中的其他对等端组的对 等端以及给布置在紧接后续层中的、属于负责该被分发的相应子流的对等端组的对 等端。

该目的在本发明的第二方面，由一种配置P2P覆盖网络的设备来实现，所述P2P 覆盖网络包括流源和布置在复数个分布层中的多个对等端，该流源布置为将准备流 播的数据内容分成可以一起形成数据内容的多个内容子流并且分发该多个内容子流 到网络对等端。该设备包括处理单元，其被设置为确定单个对等端准备布置在复数 个分布层的哪个层中，并且将这些对等端组成多个对等端组，每个对等端组包含了 来自相同分布层的对等端组成并且被进一步布置为负责分布相应的内容子流。进一 步地，该处理单元被设置为，给每个对等端组分配任务，即分发所述相应内容子流 给布置在相同分布层中的其他对等端组的对等端以及给布置在紧接后续层中的、属 于负责该被分布的相应子流的对等端组的对等端。

因此，本发明的优点是，以这样的方式将P2P覆盖网络中的对等端连接到彼此， 能够高效地获取所有可获得的对等端带宽并且与此同时将这些对等端布置在对故障 有弹性的覆盖网络中。通过将数据内容分成多个子流/带条，对等端被允许上传数据 内容流媒体的子组，即使对等端上传带宽小于回放流播速率。本发明有助于更好地 使用P2P网络-通过限制对等端从紧接在前分布层下载单个子流，而是从在相同层中 的另一个对等端组的对等端下载形成由流源分发的数据内容的剩余子流-由于多树构 造被允许，其中两个对等端可以彼此同时上传和下载。进一步地，P2P网络变得对故 障具有高度弹性，尤其是如果使用误差校正算法例如MDC和/或FEC的话，因为丢 失的子流可以从剩余子流中产生。因此，如果在网络中的任意对等端出现故障，从 故障对等端下载的其他对等端将不受影响，因为它们仅依赖于故障对等端的一个子 流并且这个丢失的子流可以从剩余子流中产生，直到实施覆盖维护和故障被处理掉。 覆盖维护被周期性地完成，在实践中，覆盖网络被从上层，即最靠近流源的那些层 重建，并且当保留系统限制时，对等端被添加到较低层。

在本发明的实施例中，流源被命令来分发基本相等数量的不同内容子流给布置 在最靠近流源的分布层。应该注意，该限制可以被编程到流源中以便它总是与之一 致。因此，在每次实施覆盖维护时可能不必须命令流源平均分布子流。在另一个实 施例中，每个分布层的对等端还被命令来分布基本相同数量的不同内容子流。优选 地，通过在所有子流上或多或少地平均分布流源上传容量，即通过使最靠近该源的 分布层，接收相等数量的每个单个子流，其中每个单个子流仅由负责上传该带条的 对等端组接收(并且对于每个子流具有平均分布的对等端上传容量)，在子流静止之 前，没有单个子流用完可获得的上传者。

在本发明的另一个实施例中，对于从布置在最靠近流源的层开始的每个分布层， 将可以分发给布置在单个分布层中的对等端的子流的最大数量确定为可以从所述单 个分布层分发的子流数量和可以从紧接在前分布层分发的子流数量的总和。此后， 布置对等端在这些分布层中直到所有的对等端被分配给相应的分布层。其优点是给 每个下载对等端提供的上传源数量可以增加或甚至最大化。进一步的优点是其考虑 了对等端在上传带宽方面的可能变化。这样，在P2P覆盖网络中配置对等端时，每 个对等端的单个带宽得到了解释。

在本发明的另一个实施例中，在之前提及的总和超过可以从紧接在前分布层分 发的子流的数量的情况下，将可以分发给准备布置在单个分布层中的对等端的子流 的最大数量设置为等于可以从紧接在前分布层分发的子流的数量。这样的优点在于， 确保没有比其前层具有的座位更多的对等端被布置在给定层中。

在本发明的另一个实施例中，对等端连接度要保证，在相应对等端组的每个对 等端被命令来从紧接在前分布层中的对等端下载它的相应内容子流，以及从布置在 相同层中的其他对等端组的对等端下载剩余内容子流。

在本发明的又另一个实施例中，在相应对等端组中的每个对等端下载哪个具体 内容子流的命令被进一步改进为关于被命令的对等端，针对紧接在前分布层中的每 个对等端组确定相应对等端组能够分发的子流的数量。此后，具体内容子流被选择 从具有最小确定分发容量的对等端下载。其优点是，具有最小上传座位量的子流被 选择以便在网络中的内容子流之间均匀地分配对等端的上传容量。

在本发明的又另一个实施例中，在至少一个所选对等端具有未使用容量的情况 下，至少一个所选对等端被分配任务，即分布其负责的相应子流给布置在紧接后续 层中的、需要具体内容子流的、但其负责不同子流的至少一个对等端。因此，该上 传被执行，即使两个对等端不负责相同的子流。其优点是，在之前层中的对等端的 未使用容量被使用，是流播数据内容的一种有效方法。并且，减少了跳次数，因为 在后续层中的对等端不需要从在相同层中的另一个对等端下载请求的子流，其直接 转化为更小回放延迟。最后，该方法释放了可能已经被从后续层使用来分发具体子 流的容量。应该注意，实践中，该方法被较低频率地使用，在包括成百上千个对等 端的层中通常每层不超过一对对等端。

在本发明的又另一个实施例中，至少一个所选对等端被分配任务，即分发其不 负责但已经下载的至少一个内容子流给布置在相同分布层中的、需要该至少一个内 容子流的至少一个对等端，在布置在相同分布层中的所述至少一个对等端可能必须 从流源下载所需数据内容子流的情况下。因此，从带宽使用的角度来看，从另一个 对等端下载所需子流比从流源下载有具优点，即使该具体对等端不属于负责所需子 流的对等端组。如之前描述实施例的情况，在P2P覆盖网络中给定对等端任务的总 数量是相对不常用的方法。

请注意，本发明涉及权利要求中描述的特征的所有可能组合。通过从属权利要求和 下面的描述，本发明的附加特征和优点将变得更加清晰。本领域的技术人员明白，将本 发明的不同特征组合还能得到除了以下描述之外的实施方式。

附图说明

现在参考附图和实施例来描述本发明，其中：

图1为现有技术中具有单树覆盖的P2P网络示意图；

图2为图1的P2P覆盖网络示意图，但其中使用了SplitStream覆盖网络构造方 法；

图3为图1和图2中示出的P2P网络示意图，但其中对等端已经布置在根据本 发明实施例的覆盖网络中；

图4a为本发明实施例的P2P网络示意图；

图4b为根据本发明实施例的一种配置P2P覆盖网络的方法示意图；

图5为布置在根据本发明实施例的P2P覆盖网络中的对等端示意图；

图6为准备配置在P2P覆盖网络中的对等端示意图；

图7为根据本发明实施例的对等端配置示意图；

图8为根据本发明另一个实施例的对等端配置示意图；

图9为根据本发明又另一个实施例的对等端配置示意图；以及

图10为根据本发明又另一个实施例的对等端配置示意图。

具体实施方式

下面通过附图和一些实施例对本发明进行详细描述。本发明可以以许多不同形 式来实施并且不应该解释为被本文中的实施例所限制；相反，通过这些实施例的描 述使本发明更全面和完整，并且可以将本发明范围全面地传递给本领域技术人员。

图1示例现有技术中具有单树覆盖的P2P网络。可以看到，对等端布置成多排 或布置在复数个分布层中。因此，两个对等端布置在分布层1中，即靠近流源S的 层，4个对等端布置在分布层2中，8个对等端布置在分布层3中。为了举例说明， 流源S分发给定数据内容给对等端P1，它继而分发数据内容给对等端P3和P4。最 后，对等端P3分发给定数据内容给对等端P7和P8，而对等端P4分发数据内容给 对等端P9和P10。图1的单树覆盖的缺点在于，在最后一排中的对等端是空闲的， 并且它们的上传容量未被使用。这是一种低效率的方法，其导致在剩余对等端和流 源上的更高负载。

图2表示图1的P2P网络，但其中使用了SplitStream覆盖网络构造方法。该方 法的主要优点是利用了网络中的所有对等端的上传带宽。与图1的覆盖构造相比， SplitStream方法可以具有这样的效果，就分布层而言，靠近源S的一些对等端现在 更远离该源(即它们将具有更大的回放延迟时间)，而远离该源的其他对等端现在更 靠近该源。然而从流源起的分布层的数量却不会增加。如之前所述，该方法使用子 流，也称为带条。因此，数据内容流被分成多个子流，有时候也称为带条。例如， 如果数据内容流速率为1Mbps，并且使用四个带条，每个带条将组成256kbps的子 流。假设具有1.5Mbps的上传容量的一个对等端，其分发数据给六个具有256kbps 最大上传容量的其他对等端，那么该对等端被认为具有六个“座位”，因为它可以通 过预定上传带宽同时上传六个带条给其他对等端。带宽和座位的这种划分使得在P2P 覆盖网络中的对等端配置设备可设置成对等端的带宽/上传容量的简单模型。在原始 流的数据通过多个子流传播的情况中，没有子流包含重叠的数据，每个对等端需要 下载所有的子流以便能够完整重构原始流。该系统更有效地利用了在网络中的每个 对等端的容量。

在图2中，原始流被分成两个带条，其中带条1由实线表示，带条2由虚线表 示。可以看到每个对等端下载带条1和带条2以便原始流可以被重构。在回放延迟 时间上，考虑以下几点：对于在图1中的对等端P1和P2，关于流源实时回放点，其 回放一块内容的延迟时间为T，对于P3-P6该延迟时间为2×T，对于P7-P14该延迟 时间为3×T，等等。

假设图2中的每个对等端的带宽与图1的带宽相同，那么带条1将在时间T中 从流源S上传到P1，但另一方面带条2将经由P11和P3被上传到P1。假设图1的 内容块对应于图2中的带条1和带条2，那么对于相同内容块，P1的延迟时间将因 此等于3T。可以对P2作出类似推理。另一方面，在例如P6的情况中，带条1将在 时间T+T＝2T中经由P1从S上传，带条2将在时间T+T＝2T中经由P11和P6上传 (假设P6具有从P1上传带条1和从P11上传带条2的容量)。因此将花费时间2T 来上传带条1+带条2。对于相同内容块，P6的延迟时间将因此等于T。结果，当将 图2的覆盖网络与图1的覆盖网络相比时，P1将经历比P6更长的延迟时间。

然而，因为在图2的覆盖网络中的所有对等端能够分发数据内容，所以在流源 带宽方面的节省将提高。然而该方法的实施需要执行分布式哈希表(DHT)，其增加 了附加的负载并且需要数据处理以实现负载平衡以及在网络中的高性能。另外，该 SplitStream方法不能处理对等端之间的变化带宽，因此假设在网络中的所有对等端 具有相同的上传带宽。

图3示出在图1和图2中提出的P2P网络，但其中对等端已经布置在根据本发 明实施例的覆盖网络中。如前面提及，本发明方法实施例的覆盖网络构造的主要优 点在于，除了使用网络中的所有对等端的上传带宽外，分布层的数量被最小化，或 者至少被减少，因为全部上传容量被使用于布置得更靠近流源的对等端。因此，从 流源跳到对等端的平均数量减少，其直接转化成更小的回放延迟时间。因此，与在 图1和图2中图示的网络覆盖相比，借由本发明产生的网络覆盖既以高效方式使用 对等端带宽又减少回放延迟时间。

当P2P覆盖网络建立并且运行时，如图3所示，对等端和流源获得主动角色， 而称为追踪器(图3中未示出)的设备则显得更被动。然而，当覆盖网络最初准备 建立时，或者在例如出现对等端故障的情况时，或者如果对等端离开网络并且新的 对等端进入网络时，等等，追踪器都是网络关键部件。如前面已经提及，覆盖维护 被周期性地进行，并且实际上，覆盖网络被从上层，即最靠近流源的那些层重建， 并且当保留系统限制时，对等端被添加到较低层。这由追踪器实施。

图4a表示本发明可以在其中实施的P2P网络。多个对等端P₁、P₂、P₃、…、P_n由追踪器41布置在覆盖网络(例如，如图3所示)中，对等端经由接口42与追踪 器41通讯。并且，追踪器能够与流源44通讯，流源44给对等端提供数据内容。例 如，追踪器可能需要关于源的流播容量的信息，追踪器关于如何分发数据内容给在 最靠近源布置的分布层中的对等端可能需要给源发送指令。追踪器41通常为具有由 微处理器43实现的计算能力的设备。通常，追踪器通过计算机执行存储在相关存储 器中用于获得所需功能性的适当软件来实施。然而，可以使用具有计算能力的其他 合适设备，例如，专用集成电路(ASIC)、现场可编程逻辑门阵列(FPGA)、复杂可 编程逻辑设备(CPLD)、等等，以便根据本发明控制P2P系统、布置覆盖，同时执 行存储在合适存储区域，例如RAM、闪存或硬盘中的可下载软件。在P2P网络中， 追踪器41接收加入和当前的对等端P₁、P₂、P₃、…、P_n的信息，例如，每个对等端 的带宽容量以及确定加入的对等端准备布置在哪个分布层中，或者当前对等端准备 转移到哪个层。为此，追踪器可能给每个对等端发送该对等端可以连接到的其他对 等端的列表。这样，产生了完整的P2P覆盖结构。

进一步参考图4b，在本发明实施例中，图4a在第一步骤S401中追踪器41确定 单个对等端准备布置哪个分布层r_i中。

因此，在步骤S402中，对于每个分布层r_i，对等端被组成h个组，表示为ψ(r_i,k)， 其中，k属于{1,…,h}。因此，在组ψ(r_i,k)中，对等端负责上传子流k给在紧接后续 层r_i+1中的对等端以及给在相同层r_i中的对等端。结果，在某个层中的每个单个对等 端组负责分发某些子流。追踪器在步骤S403中分配该任务给对等端以便对等端与该 限制一致。

随后，追踪器实现对等端连接度以便在组ψ(r_i,k)中的每个对等端从负责那个具体 子流的在紧接在前层中的对等端ψ(r_i-1,k)接收子流k，并且进一步从在相同层中的负 责其它子流k’的对等端ψ(r_i,k’)接收任何其他子流k’。因此，在相应对等端组中的每 个对等端由追踪器命令来从在紧接在前分布层中的对等端下载其中一个内容子流以 及从布置在相同层中的另一个对等端组的对等端下载剩余内容子流。

如本文上述所讨论，因为在组ψ(r_i,k)中的对等端负责上传子流k给在相同层r_i中的对等端以及给在紧接后续层中的所选对等端ψ(r_i+1,k)，所以在覆盖网络中的层在 本发明的实施例中构造为，在组ψ(r_i,k)中的对等端的上传容量必须至少等于 |ψ(r_i+1，k)|+∑_k'，k≠k|ψ(r_i+1，k')|。

这在图5中被示出，其中组ψ(r_i,1)中的对等端上传子流1给在组ψ(r_i,2)、ψ(r_i,3) 和ψ(r_i+1,1)中的对等端。在组ψ(r_i,2)中的对等端上传子流2给在组ψ(r_i,1)、ψ(r_i,3)和 ψ(r_i+1,2)中的对等端，而在组ψ(r_i,3)中的对等端上传子流3给在组ψ(r_i,1)、ψ(r_i,2)和 ψ(r_i+1,3)中的对等端。

为了将对等端上传带宽方面的可能变化考虑进来，规定了对等端带宽。在P2P 网络中，总数U个的对等端被连接。属于U的每个对等端u具有下载带宽容量c_i(u) 和上传带宽容量c₀(u)。假设c_i(u)总是等于或大于从该源流播的数据内容的回放流速 率ω。如果它小于，将不能够回放。每个对等端因此能够上传下面数量的子流：

其中α是所谓的下载回放流速率因子。较高的α值意味着，下载对等端将能够 更快地填充它的回放缓冲。如前面已经提及，对等端可以上传的子流的数量s₀(u)称 为对等端u的落座容量。换句话说，对等端u具有s₀(u)个可用于下载的座位。

每个层r_i包含多个对等端P(r_i)，而第一层r₀包含流源(s)。根据本发明的实施 例，在排r_i(i>0)中的给定对等端可以从下述对等端下载子流：

在紧接在前分布层中的对等端P(r_i-1)；或者

在自己层中的对等端P(r_i)。

每个层具有s_a(r_i)个可获得座位，其可以被P(r_i+1)个对等端使用于下载子流。在第 i层中的可获得座位被计算为：

$s_a\left(r_i\right)=\underset{u^{\text{'}}\in P\left(r_i\right)}{\Sigma }{s}_o\left(u^{\text{'}}\right)+s_a\left(r_{i-1}\right)-\left|P\left(r_i\right)\right|h.---\left(2\right)$

因此，追踪器从层r₀开始(即流源所在分布层)，并且根据下式计算可以附接到 层r₀的对等端的最大数量：

其中追踪器目的在于找到可以由它上面的层中的自由座位以及它自身层中的座 位提供的对等端的最大数量。

换句话说，追踪器针对从流源所在的层开始的每个分布层，将可以被分发到准 备布置在给定分布层中的对等端的子流的最大数量确定为可以从给定分布层分发的 子流的数量和可以从紧接在前分布层分发的子流的数量的总和。此后，追踪器将对 等端布置在分布层中直到所有的对等端已经被分配到相应的分布层。

在本文上述提及，追踪器可以给对等端提交它可以连接到的一系列其他对等端 的列表。然而，应该注意，为下载内容子流，被分配给最靠近流源的分布层的对等 端被命令来连接到流源，以及连接到布置在相同分布层中但属于另一个对等端组的 至少另一个对等端。

对等端在它们交换子流的能力方面受到它们的上传容量s₀(u)的限制，其当然可 以是确定层中对等端P(r_i)的数量方面的限制因子。然而，本发明实施例的一个特征 在于，每个对等端P(r_i)应该能够从紧接在它前面的层下载至少一个子流。因此，可 以从层r_i+1下载的对等端的数量具有上边界，其由s_a(r_i)规定。也就是，P(r_i)≤s_a(r_i)， 或者换句话说，追踪器不能布置比其前层具有的座位更多的对等端在给定层中。因 此，在本发明的实施例中，追踪器试图找到程式3的最大值，方程式3的总和应该 超过可以从紧接在前分布层分发的子流的数量，可以被分发到给定分布层中的对等 端的子流的最大数量将被设置为等于可以从紧接在前分布层分发的子流的数量。当 所有对等端已经被分配给这些层时，或者当该排上传容量s_a(r_i)下降到没有单个的对 等端可以被提供时，追踪器完成处理流程。

在本发明的实施例中，可以进一步地改进在相应层组中的每个对等端下载哪个 具体内容子流的命令。在该实施例中，追踪器从最靠近流源的层开始，在包含下载 对等端的所有层上循环。在当前层中的每个对等端被分配来从在紧接在前层中的对 等端下载具体子流k，该对等端包括在对等端组ψ(r_i,k)中。对于每排r_i和子流k，限 定了在组ψ(r_i,k)中的对等端能够上传的子流的总数量ρ(r_i,k)。

追踪器根据下式为对等端选择“最佳”子流k来下载：

$k=\arg \underset{l\in \{0,...,h-1\}}{\min }\{\rho (r_i,l)+\rho (r_{i-1},l)|\rho (r_{i-1},l)>0\}---\left(4\right)$

因此，追踪器选择下载具有最小上传座位数量的子流以便在网络中的h个子流 之间均匀地分布对等端的上传容量。结果，在该实施例中，关于被命令来下载具体 内容子流的对等端，针对在紧接在前分布层中的每个对等端组，追踪器确定相应对 等端组能够分布的子流的数量。此后，追踪器从具有最小的被确定分布容量的对等 端组中选择单个内容子流中的一个下载。

应该注意，在对等端具有未使用分发容量的情况下，追踪器可以给对等端分配 任务，让这些对等端分发其负责的相应内容子流给需要具体内容子流的、布置在后 续层中的一个或多个其他对等端，该其他对等端负责不同的子流，以便使用被分配 该任务的对等端的未使用容量。

还应该注意，追踪器可以给对等端分配分发它不负责(但已经下载)的一个或 多个子流给在相同分布层中的、需要内容子流的其他对等端的任务，在这些其他对 等端可能必须从流源下载所需内容子流的情况下。因此，从带宽使用的观点来看， 从另一个对等端下载所需子流比从流源下载有利，即使该具体对等端不属于负责所 需子流的对等端组。

实践中，这两个在P2P覆盖网络中给定对等端任务总数量的方式相对较少被使 用。通常，这些类型的任务分配仅使用于一层中较小百分比的对等端(在通常包括 成百上千个对等端的层中这个值很少超过1％)。

在本发明的另一个实施例中，对等端的分配通过使用线性求和分配方法来进一 步提高。分配给对等端座位-即分配对等端给(a)在紧接后续层中的对等端和/或(b) 在相同层中的对等端-因此可以由追踪器当作线性求和分配问题(LSAP)建模。需要 为每两个连续的分布层解决LSAP的情况。例如，拍卖(Auction)算法是用于解决 LSAP的已知和通常使用算法。提供给对等端子流是以这种方式进行，即要防止没有 可获得的上传对等端来给需要子流的对等端提供该子流的情况发生。并且，LSAP允 许关于一些预定特定度量例如网络紧接度(其影响延迟时间)和NAT连接度(其会 影响对等端上的数据流播限制)，优化对等端连接度。

在本文中，从任意给定座位下载单个子流k的来自对等端u的请求被定义为d_uk。 根据本发明实施例的分配给对等端座位由追踪器在图6-图10示出的四个不同步骤中 实施。如上文提及，对于从i＝0开始并且在最后层结束的每两个连续分布层r_i和r_i+1， 解决了LSAP，其导致分配给对等端座位的优化。因此，在分布层r_i+1中的一组对等 端P(r_i+1)与在紧接在前分布层r_i中的相应一组上传座位s_a(r_i)之间根据预定度量经历 了优化过程。给对等端座位的每个潜在分配与代表预定度量的质量测量值相关，即， 该值表示“良好的”连接如何给予预定度量。LSAP的目的在于以最大分配值分配每 个对等端到一个座位。

图6示出具有在第一层r_i中的四个对等端和在后续第二层r_i+1中的七个对等端的 P2P覆盖网络的一部分。进一步地，两个不同的子流准备被上传。因此，每个对等端 需要两个子流来完整补充由该源流播的子流。根据本发明的实施例，在两个对等端 属于负责相同子流的相应组的情况下，一个对等端被允许上传子流给在紧接后续层 中的另一个对等端。在图6中，在第二层中的对等端仍然还没有分配给座位。在对 等端中的数字1和2表示每个对等端将负责上传的相应子流。为了示意之目的，子 流1用白色表示在对等端处，而子流2用黑色表示在对等端处。虚线表示为了下载 子流1在第二层中的对等端可能分配到第一层中的座位，而点线表示为了下载子流2 在第二层中的对等端可能分配到第一层中的座位。

在第一步骤中，在ψ(r_i+1,k)中的每个对等端u对单个子流作出请求d_uk。上传座 位是对在ψ(r_i-1,k)中的每个对等端u的可获得座位s_a(u)。对于重复该过 程。为了示例，在层r_i+1中的最左边对等端可以从在层r_i中左边起第二个或第四个对 等端下载子流2。这仅是为了示例之目的；实践中，一个对等端可以具有对期望子流 的成百甚至上千个潜在上传对等端。因此，在如上文讨论的预定度量的基础上，用 公式表达了LSAP，并且作为其结果获得了分配值。

参考图7，在第一步骤中作出的分配由实线表示。例如，从图中可以看出，LSAP 和相关分配值提倡从在层r_i左边起第二个对等端下载子流2给第二层r_i+1中最左边的 对等端。进一步地，会出现一个对等端在已经经历对等端任务分配之后具有自由容 量的情况。在该具体示例中，在第一层中的最右边对等端具有上传其他子流的容量， 并且在P2P覆盖网络中没有自由容量最终被浪费。因此，如果该情况发生，在本发 明实施例中的子流可以由布置在层r_i中的对等端上传到后续层r_i+1的对等端，即使两 个对等端不负责上传相同的子流。在图7中，借由四条虚线指示对等端可能分配到 由在层r_i中的最右边对等端占有的自由座位。

在第二步骤中，在P(r_i+1)中的每个对等端u对未分配给该对等端的每个单个子流 k作出请求d_uk。上传座位都是对在P(r_i)中的每个对等端u的可获得座位s_a(u)。因此， 在预定度量的基础上，用公式表达LSAP，并且，参考图8，作为其结果的所获得的 分配值指示，在层r_i中的最右边对等端将上传子流2给层r_i+1中的最右边对等端。因 此，即使两个对等端不负责相同的子流，也可以实现该上传。然而，布置在第一层 中的对等端不再具有未使用容量，这是一种流播数据内容的高效方法。进一步地， 对于在第二层中的最右边对等端减少了跳的数量，其直导致为更小的回放延迟时间。 最后，该方法释放了本来已经从层r_i+1使用来分发具体子流的容量。

图8进一步示出，根据本发明的实施例，对等端被允许上传它负责的子流给在 相同层中的、负责其他子流的其他对等端。在图8中，在第二层中的对等端仍然还 没有补充由流源流播的数据内容所需要的两个子流的其中一个。这些可能的分配-即 在第二层中的对等端分配到在第二层中的座位用于下载剩余的所需子流-借由点线指 示。例如，可以看出，在层r_i+1中最左边的对等端可以从在层r_i+1中的、属于负责分 发子流1的一个组的四个不同对等端中任意一个下载子流1。

因此，在第三步骤中，在P(r_i+1)中的每个对等端u对单个子流k作出请求d_uk。 上传座位都是对在ψ(r_i,k)中的对等端的可获得座位。对于重复该过程。 再次，在预定度量的基础上，用公式表达LSAP，并且作为其结果获得了分配值。参 考图9，在该分配值的基础上，对等端被分配座位，其借由实线指示。以第二层中最 左边对等端为例，从获得的分配值确定应该从它的相同层中的相邻对等端下载子流 1。

现在，可以从图9中看出，在层r_i+1中的所有对等端除了从右边起第二个对等端 外均被提供，即已经下载两个子流以便数据内容可以完整地被补充。(在两层中的) 所有对等端中仅两个对等端具有上传其他子流的自由容量，其借由虚线指示。然而， 可以从图9推出，该两个对等端高效地负责上传子流1，并且从层r_i+1右边起的第二 个对等端不需要子流2。另一方面，该两个对等端具有容量，并且仅有可能的其它选 择是将可能从流源下载，但这是不期望的。因此，在本发明的实施例中，这是通过 使具有可获得容量的两个对等端中的任意一个上传被请求子流给不完全负责的对等 端来解决的。因此，在第四步骤中，在P(r_i+1)中的每个对等端u对未分配给该对等端 的每个子流k作出请求d_uk。上传座位都是在P(r_i)中的每个对等端u的可获得座位。 再次，在预定度量的基础上，用公式表达LSAP，并且对等端从哪里下载所需子流的 分配值规定应该被执行。

图10示出最终分配，该计算的分配值指定，在第二层中的最右边对等端将上传 子流2给现在完全负责的相邻对等端的对等端。因此，最右边对等端将上传子流2， 即使它高效地负责上传子流1，因为子流2可能必须被从流源上传。因此，从带宽使 用的角度看，从另一个对等端下载所需子流比从流源下载更有利，即使该具体对等 端不属于负责所需子流的对等端组。

现在，从图9可以看出，在层r_i+1中除了从右边起第二个对等端之外的所有对等 端被提供，即已经下载两个子流以便数据内容可以完整地被补充。(在两层中的)所 有对等端中仅两个对等端具有上传其他子流的自由容量，其借由虚线指示。然而， 如可以从图9推出，该两个对等端高效地负责上传子流1，并且从在层r_i+1右边起的 第二个对等端不需要子流2。另一方面，该两个对等端具有容量，并且仅有的其它选 择是将从流源下载，但这是不期望的。因此，在本发明的实施例中，通过使两个具 有空余容量的对等端中的任意一个上传请求的子流给不完全负责的对等端来解决这 个问题。

即使本文已经通过一些实施例来描述本发明，但对于本领域的技术人员来说， 对本发明所做的任何显而易见的改变和修改都落入本发明保护范围。本发明所述实 施例不是对本发明保护范围的限制。