P2P模式下使用二部对等端覆盖在对等端之间传播内容数据的设备和方法

摘要

一种在对等模式下在连接至至少一个通信网络(CN)的对等端(P1-P15)之间传播内容数据的方法，包括以下步骤：i)使对等端(P1-P15)之间交换邻域信息，以构建包括第一组(G1)和第二组(G2)的二部对等端覆盖，第一组(G1)包括具有要传播的完整内容的对等端，第二组(G2)包括不具有所述内容或者仅具有所述内容的一部分的对等端并且这些对等端之间具有链路，ii)根据二部对等端覆盖，从第一组(G1)的对等端向第二组(G2)的第一对等端传播定义所述内容的数据(优选地，利用纠删码来编码的数据)，iii)根据二部对等端覆盖，向第二组(G2)的其他对等端传播由第一对等端接收到的数据，以及iv)当第二组(G2)的一对等端完全完成了所述内容时，更新二部对等端覆盖。

说明书

技术领域

本发明涉及对等(或“P2P”)环境(或网络)中对等端之间的内容传播。

这里“对等端”是指在P2P模式下能够与其他对等端或网络设备交换数据(或符号)的用户通信设备，因为对等端包括至少一个可执行P2P通信应用。从而，对等端可以是固定个人计算机、膝上型计算机、内容接收机(例如，位于用户家庭房屋中的家庭网关或机顶盒(STB))、移动或蜂窝电话、固定电话、或个人数字助理(PDA)(假定其包括通信调制解调器(或者任何等同通信装置))。

此外，“符号”是指数据块或数据分组。

背景技术

如本领域技术人员所知，在诸如对等网络之类的分布式系统中，在对等端之间传播一些内容，以便这些对等端之中的每一个自行处理这些内容。

可以通过使用树的类似组播的协议，或者通过完全分散和随机协议，来执行传播。

(随机)传播协议是一种协议，该协议需要为该协议所运行的每个对等端提供其他对等端的随机采样。对等端的这些随机采样例如可以由基于闲话(gossip)的对等端采样协议来确定。基于闲话的对等端采样协议允许在没有中央服务器的情况下构建邻域，因此适合于邻域的频繁更新。

在基于闲话的对等端采样中，对等端周期性选择随机邻域，对等端与邻域之间交换它们相应的与其他对等端有关的知识，并且将它们自己的知识与从其他对等端接收到的知识合并，以便排除旧知识(例如，潜在失效对等端)而同时使信息丢失最小化。实际上，为了避免丢失信息，在两个对等端之间交换邻域信息之后，这两个对等端所保持的信息必须仍足够不同。这种基于闲话的对等端采样协议产生随机图作为覆盖(即，逻辑网络)。可以在Spyros Voulgaris等人的文章“Gossip-Based Peer Sampling”，ACM Transaction on Computer Systems2007，Volume 25中找到与基于闲话的对等端采样协议有关的更多信息。

可以将随机传播协议分为拉协议和推协议。

当实现拉协议时，对等端必须要求它们的邻域遗漏部分内容。从而，这种类型的传播协议需要对等端之间的双向信道以及重要的控制开销。用于传播内容的主要拉协议之一是Bittorrent协议。在Bittorrent中，将内容分割成块或组块，所有对等端以互逆的(reciprocal)方式协作，使得每个对等端获取该内容的所有组块。该技术通常被称作“内容群集(swarming)”。

如Bittorrent之类的拉协议不会受到数据开销的影响，但是它们会引起重要控制开销。此外，所获得的传播启动慢并具有高延迟。因此，所获得的传播不适合于低延迟传播。

当实现推协议时，接收内容的块或组块的对等端随机选择F个邻域，并向这些邻域转发接收到的组块。每个组块具有使用期限，该使用期限是该组块经历的跳跃次数，每次组块从一个对等端被转发至另一个对等端时该组块的使用期限减小。当使用期限变为零时，不再转发组块。推协议确保快速启动。推协议不需要反馈信道，并且具有低控制开销。

推协议主要由以下两个参数来控制：“扇出(fanout)”，是块或组块被转发至的随机对等端的数目；以及使用期限。扇出严重影响延迟，并且扇出与使用期限的乘积影响完成的程度(即，有多少个对等端获得完整内容)。该乘积越高，数据开销也就越高。这里“数据开销”是指对等端多于一次地接收到的数据。

在不需要全内容完成时，推协议是适用的。实际上，很难达到最后的对等端(即使使用利用前向纠删(forward erasure correcting)(FEC)码的编码)，因此必须增大使用期限和扇出，这增大了数据开销。

可以在Patrick T.Eugster等人的文章“From Epidemics to Distributed Computing”，IEEE Computer，Volume 37，2004中找到与推协议有关的更多信息。

也可以实现第三种类型的传播协议。该第三种类型的传播协议包括推拉协议。在该第三种类型的协议中，推阶段在拉阶段之前。在推阶段期间遗漏了内容的一些部分的对等端在后续拉阶段期间请求该内容的遗漏部分。与可用内容块有关的信息附着至内容数据，控制开销较低。

这些推拉协议具有低延迟和低控制开销，这是由于推阶段确保低延迟，拉阶段确保完整。从而，不需要增大扇出或使用期限。此外，每个对等端附近的全内容传播不会引起数据开销的增加。这些推拉协议的主要缺陷是不容易实现，这是由于这些推拉协议更加复杂并且这些推拉协议的参数更难调整(并且尤其是定义何时处于推模式或拉模式的参数)。

可以在Sujay Sanghavi等人的文章“Gossiping with multiple messages”，IEEE International Conference on Computer Communication，2007(INFOCOMM 2007)中找到与推拉协议有关的更多信息。

发明内容

从而，本发明的目的是通过新传播协议来改进内容传播。

为此，本发明提供了一种在对等模式下在连接至至少一个通信网络的对等端之间传播内容数据的方法，包括以下步骤：

i)使对等端之间交换邻域信息，以构建包括第一组和第二组的二部(bipartite)对等端覆盖，所述第一组包括具有要传播的完整内容的对等端，所述第二组包括不具有所述内容或者仅具有所述内容的一部分的对等端并且这些对等端之间具有链路(优选地，随机链路)，

ii)根据二部对等端覆盖，从第一组的对等端向第二组的第一对等端传播定义该内容的数据，

iii)根据二部对等端覆盖，向第二组的其他对等端传播由这些第一对等端接收到的数据，以及

iv)当第二组的一对等端完全完成了所述内容时，更新二部对等端覆盖。

根据本发明的方法可以包括分开或组合考虑的附加特征，并且特别地：

-在步骤i)和/或iv)中，可以通过基于闲话的对等端采样协议来构建和/或更新二部对等端覆盖，基于闲话的对等端采样协议被(略微)修改为分别根据对等端是属于第一组还是属于第二组来考虑第一对等端状态和第二对等端状态；

在步骤i)和/或iv)中，当对等端接收到来自另一对等端的包含邻域信息的消息时，该对等端可以通过移除每个重复的对等端和每个第一组对等端和至少一个最早已知的对等端和/或至少一个最近已知的对等端和/或至少一个随机选择的对等端，来将该邻域信息与该对等端自己的邻域信息合并，以便更新二部对等端覆盖(并因此更新对该对等端的邻域对等端的知识)；

-在步骤iii)中，可以以所选的次数(由使用期限限定)将接收到的内容数据从对等端向对等端传播；

-在步骤iii)中，可以通过选自协议组的传播协议，从对等端向对等端传播接收到的内容数据，该协议组包括推传播协议和推拉传播协议；

-在步骤ii)中，第一组的对等端可以向随机选择的第二组对等端传播内容数据；

-在第一变型中，在步骤ii)中，第一组的对等端可以向根据至少一个准则选择的第二组的对等端传播内容数据；

-在第二变型中，在步骤ii)中，第一组的对等端可以向作为邻域对等端的第二组对等端传播内容数据；

-在步骤ii)中，第一组的对等端可以在利用纠删码对内容数据进行编码之后传播这些内容数据。

本发明还提供了一种用于控制在对等模式下对从连接至通信网络的对等端向其他对等端传播内容数据的设备，包括：

-第一装置，被配置为根据所述第一装置的对等端与其他对等端交换的邻域信息，来参与构建包括第一组和第二组的二部对等端覆盖，所述第一组包括具有要传播的完整内容的对等端，所述第二组包括不具有所述内容或者仅具有所述内容的一部分的对等端并且这些对等端之间具有链路(优选地，随机链路)，

-第二装置，被布置为根据二部对等端覆盖来命令所述第二装置的对等端向第二组的对等端传播至少部分地定义内容的数据，

-第一装置还被布置为当第二组的一对等端完全完成了所述内容时，更新二部对等端覆盖(因此更新对所述第一装置的对等端的邻域对等端的知识)。

根据本发明的系统可以包括分开或组合考虑的附加特征，并且特别地：

-该系统的第一装置可以被布置为：当所述第一装置的对等端接已收到来自另一对等端的包含邻域信息的消息时，通过移除每个重复的对等端和每个第一组对等端和至少一个最早已知的对等端和/或至少一个最近已知的对等端和/或至少一个随机选择的对等端，来将该邻域信息与自己的邻域信息合并，以便更新二部对等端覆盖(并因此更新对该第一装置的对等端的邻域对等端的知识)；

-该系统的第二装置可以被布置为命令所述第二装置的对等端通过选自协议组的传播协议向其他对等端传播接收到的内容数据，该协议组包括推传播协议和推拉传播协议；

-该系统的第二装置可以被布置为将所述第二装置的对等端必须向其传播内容数据的对等端随机地确定到第二组中；

-在第一变型中，该系统的第二装置可以被布置为，用于根据至少一个准则将所述第二装置的对等端必须向其传播内容数据的对等端确定到第二组中；

-在第二变型中，该系统的第二装置可以被布置为将作为所述第二装置的对等端的邻域对等端并且所述第二装置的对等端必须向其传播内容数据的对等端确定到第二组中。

附图说明

基于对以下详细描述和附图，本发明的其他特征和优点将变得显而易见，在附图中：

图1示意性且功能性示出了连接至通信网络的4个对等端，其中每个对等端包括根据本发明的设备的实施例示例；

图2示意性示出了二部对等端覆盖的非常简单的示例，该二部对等端覆盖包括由6个对等端组成的第一组和由9个对等端组成的第二组(可以设想一些覆盖可以包括几百甚至上千对等端)。

具体实施方式

附图不仅用于实现本发明而且如果需要还贡献于其限定。

本发明的目的在于提供一种允许在对等(P2P)模式下在连接至至少一个通信网络(CN)的对等端(Pj)之间传输内容数据的过程和关联的控制设备(D)。

在以下描述中，将考虑到，通信网络(CN)是有线(或固定)网络，例如，DSL网络或光纤网络或有线网络。但是本发明不限于这种类型的通信网络。实际上，通信网络也可以是无线通信网络，例如，移动或蜂窝或无线电通信网络。

此外，在以下描述中，将考虑到，对等端(Pj)是用户通信设备，例如，固定个人计算机。但是本发明不限于这种类型的通信设备。实际上，本发明涉及包括至少一个可执行P2P通信应用并且能够在P2P模式中与其他通信设备(或对等端)或网络设备交换数据(或符号)的任何类型的通信设备。从而，对等端也可以是膝上型计算机、内容接收机(例如，位于用户家庭房屋中的家庭网关或机顶盒(STB))、移动或蜂窝电话、固定电话、或个人数字助理(PDA)(假定其包括通信调制解调器(或者任何等同通信装置))。

此外，在以下描述中，将考虑到，要传播的内容是信息数据的文件。但是本发明不限于这种类型的内容。实际上，本发明涉及只有已经被完成时才能使用的任何类型的内容，特别是，视频、电视节目、无线电节目和软件更新。

如图1示意性所示，本发明涉及通过通信网络CN来彼此连接的对等端Pj(这里，j＝1到4)组。在该非限制示例中，该组包括4个对等端(P1-P4)，也可以包括3个对等端或多于4个对等端(在图2所示非限制示例的情况下尤为如此，其中，该组包括15个对等端(j＝1到15))，并且可以包括几百或几千个对等端。

本发明提出了一种方法，用于在对等(P2P)模式下在对等端Pj之间传播内容数据。该传播方法包括4个主要步骤，并且根据本发明，可以由分别与对等端Pj相关联的控制设备D来实现。

这里“关联”是指对等端Pj配备有控制设备D(如图1所示)。但是在变型中，也可以是指控制设备D与对等端Pj耦接(例如，连接)。

如所示，控制设备D至少包括第一装置(或模块)M1和第二装置(或模块)M2。

根据本发明的方法的第一主要步骤(i)包括：使对等端Pj之间交换邻域信息，以便构建二部对等端覆盖。这里“二部对等端覆盖”是指包括第一组G1和第二组G2的覆盖(或逻辑网络)，其中，第一组G1包括具有必须全部传播的完整内容的对等端Pj，第二组G2包括还没有接收到该内容或者仅接收到该内容的一部分的对等端Pj’并且这些的对等端Pj’之间具有链路(优选地随机链路)。

二部对等端覆盖可以被看作随机图与二部图的组合。这获得分裂图，分裂图是具有完全连接的组件(随机部分-第二组G2的对等端)和所述组件周围隔离的对等端(二部部分-第一组G1的对等端)的图。仅第二组G2的对等端具有输入边缘。任何其他对等端都不知道第一组G1的对等端。

在图2所示非限制示例中，第一组G1在给定时刻包括6个对等端(P1、P4、P5、P6、P8和P13)，第二组G2在相同给定时刻包括9个对等端(P2、P3、P7、P9、P10、P11、P12、P14和P15)。

可以根据对等端Pj通过与其他对等端Pj’交换而获得的邻域信息，由这些对等端Pj的控制设备D的第一装置M1来构建二部对等端覆盖。例如，可以通过基于闲话的对等端采样协议，由对等端Pj来执行这些交换，其中，所述基于闲话的对等端采样协议被(略微)修改为分别根据对等端是属于第一组G1还是第二组G2来考虑第一对等端状态和第二对等端状态。事实上，每个对等端Pj从其邻域Pj’收集邻域信息，然后在二部对等端覆盖中构成其自身部分，这是构成二部对等端覆盖的所有这些部分的合并。

例如，协议具有以下周期性任务：选择对等端Pj的随机邻域，并且发送具有与网络的本地知识有关的信息的消息。当对等端Pj从另一对等端Pj’接收到这样的消息时，将该消息的内容与对等端Pj的本地邻域信息(或知识)合并。例如，这种合并包括：移除每个重复的对等端和每个第一组对等端和至少一个最早已知的对等端和/或至少一个最近已知的对等端和/或至少一个随机选择的对等端。例如，可以移除H个最早对等端，其中H＝2或3(例如)，使得覆盖具有自恢复属性，然后可以移除S个第一对等端，其中S＝4或5(例如)，这是由于可以考虑到可能已经从一些对等端适当地获知这些第一对等端。这使信息丢失最小化。可以随机移除一些对等端，以便使包含在二部对等端覆盖的一部分中的对等端数目对于每个对等端Pj保持不变。

可以将二部对等端覆盖的具体涉及对等端Pj的一部分存储在与该对等端Pj相关联的控制设备D的存储装置M3中(如图1所示)。该存储装置M3可以是本领域技术人员已知的任何类型。从而，该存储装置M3例如可以是存储器。例如，该部分可以包括与对等端Pj连接并从而构成该对等端Pj的邻域之一的每个对等端Pj’的标识符。

重要的是注意到，也可以根据每个对等端Pj所传输的邻域信息，由连接至通信网络CN的中央服务器来构建二部对等端覆盖。在这种情况下，不使用基于闲话的对等端采样协议，而是由中央服务器为任何对等端Pj提供二部对等覆盖中属于该对等端Pj自己的部分(也被称作“对等端视图”或“邻域”-即，对等端必须已知的最小对等端集合)。

根据本发明的方法的第二主要步骤(ii)包括：根据二部对等端覆盖，从第一组G1的对等端Pj向第二组G2的第一对等端Pj’传播必须完全传播的数据。在图2所示非限制示例中，第二组G2的第一对等端是P2、P3、P10、P11、P12、P14和P15。

例如，第一组G1中的每个对等端Pj可以根据二部对等端覆盖中该对等端Pj的特定部分，来选择该对等端Pj必须向其传输内容数据(出于传播目的)的第二组G2的第一对等端。

这种选择可以在第二组G2的每个对等端之中随机进行，或者根据一个或多个准则(例如，近似准则或完整准则(例如，至少一个第一对等端是已经拥有最为完整内容(但不是全部内容)的已知对等端，即使该对等端不是二部对等端覆盖中第一对等端的邻域))进行，或者在第二组G2中作为邻域考虑的每个对等端之间进行。这允许一些对等端快速地完成内容并然后快速地编程第一组G1的对等端。

第一组对等端必须向其传输内容数据的第二组G2的第一对等端可以由与该第一组对等端关联的控制设备D的第二装置M2来确定(或选择)。

该第二装置M2还被布置为：一旦该第二装置M2已经确定了第一对等端，就命令与该第二装置M2相关联的对等端Pj(如果该对等端Pj属于第一组G1)根据二部对等端覆盖中属于该对等端Pj自己的部分(例如，存储到存储装置M3中的部分)向这些第一对等端传播内容数据。为此，第二装置M2可以向与该第二装置M2相关联的对等端Pj提供所选第一对等端的标识符，使得该对等端Pj能够向这些第一对等端传输该对等端Pj所拥有的内容数据。

优选地，在步骤ii)中，第一组G1中的对等端在对内容数据进行编码之后传播这些内容数据。可以例如通过无速率(rateless)纠删码或低速率纠删码来执行这种编码，以避免不同对等端所推送的内容数据之间的冗余。

当第一对等端从第一组对等端接收内容数据(或符号)时，该第一对等端可以将该内容数据添加至该第一对等端所包括的专用本地缓冲器。如果接收到的内容数据(或符号)是最后遗漏的内容数据(或符号)，则内容是完整的，并且第一对等端变成第一组G1的对等端。当将内容数据(或符号)添加至缓冲器时，如果该缓冲器已满，则优选地移除最早的内容数据(或符号)。

被第一组对等端用来向第一对等端传播内容数据的传输协议是常规推协议。

根据本发明的方法的第三主要步骤(iii)包括：根据二部对等端覆盖，向第二组G2的其他对等端传播由第一对等端接收到的数据，然后，如果需要的话，从这些其他对等端向第二组G2中另外的其他对等端传输该数据。内容数据可以(在对等端Pj、Pj’之间)经历的跳跃数目由这些内容数据的使用期限来定义。

第二组对等端Pj必须向其传输内容数据的第二组G2的对等端(邻域)，由与该对等端Pj相关联的控制设备D的第二装置M2来确定(或选择)。重要的是注意到，由第二装置M2执行的对等端确定(或选择)可以根据与第二装置M2相关联的对等端Pj属于哪个组(G1、G2)来随时间变化。

同样重要的是注意到，接收到内容数据的每个第二组对等端将其缓冲器的全部内容传输至由与该第二组对等端相关联的控制设备D的第二装置M2确定(选择)的第二组G2的对等端(邻域)。每次从第二组对等端向其他第二组对等端传播内容数据时，就减小该内容数据的使用期限。

同样重要的是注意到，如果在步骤ii)中第一组G1的对等端在编码了内容数据之后传播该内容数据，则在步骤iii)中，第二组G2的对等端传播接收到的编码内容数据。

被第二组对等端用来向其他第二组对等端传播接收到的数据的传播协议可以是常规推协议。但是也可以是推/拉协议。

根据本发明的方法的第四主要步骤(iv)包括：当第二组G2中有对等端完全完成了有关内容时，更新二部对等端覆盖。实际上，在这种情况下，不再将该对等端视为第二组G2的成员，而是视为第一组G1的成员。

当对等端Pj完全完成了要传播的内容时，由对等端Pj的第一装置M1自动执行该更新。该第一装置M1更新其对等端Pj的二部对等端覆盖的一部分(存储在存储装置M3中)，该第一装置M1的对等端Pj必须将该对等端Pj的状态改变(从G2到G1)通知给其他对等端Pj’。等端Pj可以通过根据本发明被(略微)修改(即，被修改为：分别根据对等端是属于第一组G1还是属于第二组G2来考虑考虑第一对等端状态和第二对等端状态)的基于闲话的对等端采样协议，来执行该通知。

在由中央服务器来构建二部对等端覆盖的情况下，每次对等端Pj将其状态改变(即，从G2到G1)通知给中央服务器时，中央服务器还进行二部对等端覆盖的更新。

优选地，控制设备D(特别地，控制设备D的第一装置M1和第二装置M2)至少部分地由软件模块构成。但是控制设备D也可以由电子电路或硬件模块、或者硬件和软件模块的组合(在这种情况下，控制设备D还包括允许硬件与软件模块之间交互的软件接口)构成。在控制设备D仅由软件模块构成的情况下，可以将该控制设备D存储在网络设备CS的存储器中或任何计算机软件产品中。

本发明提出了低延迟和低开销的传播。此外，通过使对等端不相同，由于一些对等端能够快速重新编码数据，因此可用资源被最优地使用。

本发明不限于上述传播方法、控制设备和对等端的实施例，而是仅作为示例，但是本发明涵盖所附权利要求范围内本领域技术人员可以想到的所有备选实施例。