用于检测对等网络中故障对等体的对等体、应用和方法

摘要

用于确定结构化对等覆盖网络中故障对等体的应用、对等体和方法。覆盖网络包括除故障对等体外的许多对等体。方法包括确定沿第一路径从给定对等体发送到目标对等体的消息未到达目标对等体；确定消息已到达的中间对等体；使用第二路径将消息从给定对等体发送到目标对等体；确定消息在第二路径上已到达目标对等体；调整目标对等体和中间对等体中至少之一的节点标识符(nodeID)以获得新目标对等体或新中间对等体；以及再使用第一和第二路径将消息发送到新目标对等体或新中间对等体，直至检测到故障对等体。

说明书

技术领域

本发明一般涉及系统、软件和方法，并且更具体地说，涉及用于检测对等(P2P)网络中故障对等体的机制和技术。

背景技术

今天，P2P网络在各种环境中被加以利用，例如用于文件共享或话音IP。P2P网络分为结构化和非结构化网络。结构化P2P网络采用全局一致协议以确保任何对等体能够有效地将搜索路由到具有所需文件或服务的某个对等体。为实现此操作，采用了覆盖链路的结构化模式。最常见类型的结构化P2P网络是基于DHT（分布式散列表）网络。P2P DHT网络的示例是Chord（参阅Stoica等人所著“Chord：用于因特网应用的可扩展对等查找服务”(“Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications,” 在Proceedings of the ACM SIGCOMM ’01会议中, San Diego, California, Aug. 2001, pp. 149)。

在DHT中，信息以带有几个<关键字，值>对的散列表形式存储在所有对等体之间。覆盖中的对等体需要某些信息时，对等体要执行关键字的查找，并且随后如果关键字存储在另一对等体中，则检索与关键字相关联的值。传统DHT算法使用指针表的概念以便通过覆盖路由分组。使用Chord DHT的P2P覆盖中的每个对等体具有指针表。指针表包括指向其它对等体的指针列表和邻居表，邻居表是位置距离给定对等体一个或几个跳的对等体列表。在此上下文中中对等体被视为是装置。

为保持完全正常工作的P2P网络，其对等体需要不断维护其指针表。这通过探测其它对等体和观察结果来实现。由于P2P网络的性质，在所有对等体具有正确指针表时，从路由选择角度而言，整个P2P网络是稳定的。然而，在现实世界中，对等体不断加入和离开P2P网络，由此要求剩余对等体不断更新其指针表。另外，存在丢弃收到数据或者将收到的数据路由到错误对等体（数据转发问题）的有缺陷或恶意对等体，并且这些动作破坏了P2P网络的功能性。有缺陷的对等体无意破坏数据业务，而恶意对等体具有该意图。因此，对等体能够以许多方式破坏网络。有缺陷或恶意的所有这些对等体在本文中通称为故障对等体。

由于存在故障对等体，因此，网络及其对等体不能辨别数据转发问题是由波动（加入和/或离开）造成，还是由具有破坏网络的正常操作动机的恶意对等体造成。换而言之，将信息发送到P2P网络的对等体不能知道业务是否到达了目的地对等体。另外，即使知道在进行的攻击，由于肇事者未知，因此，对等体也难以减轻攻击的影响。

P2P覆盖中恶意对等体的检测是尚待彻底解决的存在问题。当前P2P网络不能检测将分组错误路由的恶意对等体，也不能检测节点是否在丢弃分组。

有一些方案用于实现如本文中讨论的此功能性。然而，这些方案具有其限制。一种方案是跳测试。它包括使用迭代路由选择来检测路由中每个跳的行为。在没有迭代路由选择的情况下，此测试不可使用，并且如果恶意对等体位置足够靠近目标对等体，则它的效率低。另外，此方案成本高，这是因为它要求在各种对等体之间交换大量的消息。

另一种方案是如果原路由选择路径发生故障，则使用备选路由选择路径。此方案在于分析可能恶意对等体的回复，即，如果对等体在某个超时后未回复，或者如果回复到达太迟（因此未正确路由）。如果发生此情况，则通过备选路径重复查询。此方案通过尝试不同路径，仅减轻了问题，但它无助于定位恶意对等体。

还有的另一方案实现平行路由选择。此方案评估节点是否负责某个关键字。方案使用正常路由选择将一个消息发现到可疑节点，随后，它使用迭代路由选择发送测试消息，并且备选路径被开放。此方法由于经常生成错误肯定，因此，通常不使用它。方法也要求特殊格式化的消息。

从传统方案的以上讨论中，注意到它们致力于确保消息到达目的地，而不是检测对不正确路由选择负责的对等体和阻止它们继续此类行为。另外，如果攻击者位置靠近受害者，或者如果网络密度不同，则现有方案未能阻止此类行为。现有方案也要求有关完全路径路由的一定量的信息，或通过使用昂贵的迭代路由选择，要求为每个对等体使用直接消息。另外，这引起方案要由几个节点协作执行。

因此，需要开发能够由单个节点执行，不需要补充信息并且也能够检测恶意软件的位置的新方案。相应地，希望提供避免上述问题和缺陷的装置、系统和方法。

发明内容

P2P覆盖网络中具有一个或更多个故障对等体的可能性是可能的。因此，需要准备好能够检测故障对等体的机制（例如，要在计算装置中实现的应用）。在一个实施例中，覆盖网络中的给定对等体在沿第一路径将消息发送到目标对等体时确定存在此类故障对等体。已收到消息并且沿第一路径位于故障对等体之前的中间对等体回复给定对等体。给定对等体的应用配置成使用与第一路径不同的第二路径传送消息到目标对等体。可能此路径有效，并且随后故障对等体被确定成位于在目标对等体与中间对等体之间。修改目标对等体或中间对等体的至少一个节点id，以获得新目标对等体或新中间对等体。其它消息从给定对等体发送到新目标对等体和/或新中间对等体以缩小故障对等体的位置。重复进行这些步骤，直至新目标对等体或新中间对等体与故障对等体位置相邻。

根据一个示范实施例，有用于确定结构化对等P2P覆盖网络中故障对等体的应用。覆盖网络包括除故障对等体外的许多对等体。应用配置成执行确定沿第一路径从给定对等体发送到目标对等体的消息未到达目标对等体的步骤、确定消息已到达的沿第一路径在给定对等体与目标对等体之间中间对等体的步骤。应用也包括使用第二路径将消息从给定对等体发送到目标对等体的步骤，其中，第二路径与第一路径不同；以及确定消息已到达目标对等体的步骤。基于此信息，应用调整目标对等体和中间对等体中至少之一的节点标识符(nodeID)以获得新目标对等体或新中间对等体；以及再使用第一和第二路径将消息发送到新目标对等体或新中间对等体，直至检测到故障对等体。

根据另一示范实施例，有用于确定结构化对等P2P覆盖网络中故障对等体的方法。覆盖网络包括除故障对等体外的许多对等体。方法包括确定沿第一路径从给定对等体发送到目标对等体的消息未到达目标对等体的步骤、确定消息已到达的沿第一路径在给定对等体与目标对等体之间的中间对等体的步骤、使用第二路径将消息从给定对等体发送到目标对等体的步骤，其中，第二路径与第一路径不同。方法随后确定消息已到达目标对等体；并且调整目标对等体和中间对等体中至少之一的节点标识符(nodeID)以获得新目标对等体或新中间对等体。方法再使用第一和第二路径将消息发送到新目标对等体或新中间对等体，直至检测到故障对等体。

根据另一示范实施例，有配置成运行应用以确定结构经对等P2P覆盖网络中故障对等体的给定对等体。覆盖网络包括除给定和故障对等体外的许多对等体。给定对等体包括配置成与目标对等体交换消息的接口和连接到接口的处理器。处理器配置成确定沿第一路径发送到目标对等体的消息未到达目标对等体；确定消息已到达的沿第一路径在给定对等体与目标对等体之间的中间对等体；以及使用第二路径将消息发送到目标对等体，其中，第二路径与第一路径不同。处理器还配置成确定消息已到达目标对等体；并且调整目标对等体和中间对等体中至少之一的节点标识符以获得新目标对等体或新中间对等体。处理器随后再使用第一和第二路径将消息发送到新目标对等体或新中间对等体，直至检测到故障对等体。

根据还有的另一示范实施例，有在结构化对等P2P覆盖网络的给定对等体中实现的应用。覆盖网络包括除给定对等体外的许多对等体。应用配置成处理在从给定对等体发送到目标对等体的消息中专用的多个字段；以及填充消息中的方向字段，其中，方向字段指示在闭合环路中提供多个对等体时，消息是沿顺时针路径还是逆时针路径行进。除顺时针指针表外，应用也在给定对等体保持逆时针指针表。顺时针指针表指示在消息沿顺时针路径行进时在多个节点之间的关系，并且逆时针指针表指示在消息沿逆时针路径行进时在多个节点之间的关系。

因此，目的是克服前面部分中讨论的一些缺陷并且提供不但确定故障对等体的存在，而且确定其位置并对网络的破坏极小的机制。一个或更多个独立权利要求项有利地提供了用于确定故障对等体的此类机制。

附图说明

附图结合在说明书中并构成其一部分，示出一个或多个实施例，并与描述一起解释这些实施例。在图中：

图1是根据一示范实施例，具有故障对等体的P2P网络的示意图；

图2是根据一示范实施例的消息报头的示意图；

图3是根据一示范实施例，具有顺时针和逆时针表的对等体的示意图；

图4是根据一示范实施例，用于检测P2P网络中故障对等体的方法的流程图；

图5是根据一示范实施例，示出解除P2P网络中故障对等体的权利的示意图；以及

图6是其中可实现权利要求4的方法的对等体的示意图。

具体实施方式

示范实施例的以下描述参照附图。不同图中的相同参考标号识别相同或类似的元素。以下详细描述不限制本发明。相反，本发明的范围由随附权利要求书限定。为简明起见，下面的实施例根据P2P DHT网络的术语和结构进行论述。然而，新颖的实施例不限于此网络，而是可应用到其它类型的网络。

说明书通篇对“一个实施例”或“一实施例”的引用指结合一实施例描述的特定特征、结构或特性包括在本发明的至少一个实施例中。因此，在说明书通篇各个位置出现的“在一个实施例中”或“在一实施例中”短语不一定全部指相同的实施例。此外，特定的特征、结构或特性可在一个或多个实施例中以任何适合的方式组合。

根据一示范实施例，有用于检测行为不当或者未根据结构化P2P覆盖网络中预期行为操作的故障对等体（无论是否恶意）的方法。行为不当或以非预期方式操作的原因与本发明的目的不相关。在一个应用中，方法确定一个特定对等体是否有故障而无需迭代路由选择。此外，方法可有助于缩小怀疑丢弃消息的对等体所处的覆盖区域。在一个应用中，方法确定覆盖网络中故障对等体的确切位置。

在诸如Chord等DHT覆盖网络10中，沿闭合环路（例如，环）11 分布多个对等体12。在图1所示实施例中，假设给定对等体14将消息22发送到目标对等体16。任何对等体12可执行下面为给定对等体14描述的动作。假设故障对等体18未将消息从给定对等体14传送到目标对等体16。可想象故障对等体18不传送消息的各种机制。认为新颖的特征宽广到足以包括任何这些机制。

默认情况下，沿第一路径24，例如图1中的顺时针方向路由消息22。即使默认值是不同路径，新颖的特征也适用。消息由中间对等体转发，直至消息到达其目的地，例如，目标对等体16。转发消息22的备选方式是沿第二路径26，即，图1中的逆时针方向。因此，在逆时针路径中的消息以相对于顺时针路径相反的方向转发。新颖的机制的工作原理是将顺时针和逆时针消息发送到位于故障对等体所处区域中的对等体。在一个应用中，执行几次迭代，直至找到故障节点。

为跟踪消息22是沿第一还是第二路径行进，除现有专用字段30（例如，消息已遍历的节点列表、消息应遍历的节点列表、存活时间等）外可能在消息22的报头中引入新字段32，如图2所示。例如，在基于Chord的协议中，像作为在因特网工程任务组(IETF)中标准化的P2P信令协议的资源位置和发现(RELOAD)中 ，可能引入新字段32以跟踪消息是沿顺时针路径24还是逆时针路径26行进。因此，新字段32可以是单个比特。

换而言之，此新字段识别应如何转发消息，即，在顺时针方向还是在逆时针方向。对等体（即，节点，其中节点可以是计算机、移动电话、平板等）接收顺时针消息时，对等体将通过覆盖10正常路由它。逆时针消息将暗示在反方向路由它。传统覆盖网络具有与每个对等体相关联的指针表。换而言之，每个对等体在存储装置中存储在逆时针方向转发消息到下一对等体所需要时使用的指针表。要注意的是，在传统覆盖网络中，消息默认在单个方向中传送。在一示范实施例中，具有下面要讨论的新颖应用的每个对等体具有用于逆时针路由选择的另外指针表。

新颖的特征可视为要嵌入对等体以便确定故障对等体的新机制或方法或应用。因此，对方法或机制或应用的引用在本文中要理解成表示新颖特征的一个可能实现。仍相对于图1，现在考虑给定对等体14如何检测故障对等体18的位置。要注意的是，图1中的对等体在环路11中具有某个位置/顺序，例如，给定对等体14占用位置1，目标对等体16占用位置12，故障对等体18占用位置10等。

根据新颖方法，给定对等体14沿逆时针路径24将消息22发送到目标对等体16。消息22要理解成包括如图2所示的结构化报头，报头包括已知字段30和上面提及的新颖字段32。新颖字段32可称为方向字段，这是因为此字段指示消息沿闭合环路的传播方向。如果从目标对等体16收到确认，则给定对等体14断定沿路径24无故障对等体。

然而，如果给定对等体14未收到确认或者等待超时，则给定对等体14确定沿路径24在给定对等体14与目标对等体16之间存在故障对等体。覆盖网络可配置成使得收到来自给定对等体14的消息22的最后对等体确认它接收到消息。这样，给定对等体14变得知道中间对等体20是收到消息22的最后对等体。

因此，此时给定对等体14知道故障对等体18存在，并且它位于在目标对等体16与中间对等体20之间。然而，给定对等体14仍不知道故障对等体18的确切位置。给定对等体14现在使用第二路径26将消息22发送到目标对等体16，第二路径是逆时针路径。假设无其它故障对等体存在，给定对等体14应接收沿第二路径26来自目标对等体16的确认消息。这确认故障对等体18位于目标对等体16与中间对等体20之间。

接着，方法可选择性地再次沿第一路径24从给定对等体14发送消息22到目标对等体16，并且随后可沿第二路径26将消息22从给定对等体14发送到中间对等体20以确认故障对等体18位于目标对等体16与中间对等体20之间和/或收集更多信息。在一个应用中，给定对等体14发送四个消息，即两个消息发送到中间对等体20（每个沿不同路径），以及将两个消息发送到目标对等体16（每个沿不同路径）。这促使查找在目标对等体与中间对等体之间更多工作的对等体（在此情况下，它们变成新目标或中间对等体）或者不查找其它对等体。

如果发生第二种情形，即，确定故障对等体18位于目标对等体16与中间对等体20之间，并且在中间对等体20与故障对等体18之间不存在其它对等体（表现在给定对等体14知道它），则方法将目标对等体16或中间对等体20至少之一的节点标识符(nodeID)修改某个常数值。常数值例如可以是为1。

例如，方法可将中间对等体20的nodeID从8增大到9，以确定新中间对等体20’，或者可将目标对等体16的nodeID从12降低到11以确定新目标对等体16’。这样，方法缩小了在故障对等体18周围的间隔。在一个实施例中，方法可同时增大一个nodeID和降低另一nodeID以获得新目标对等体16’和新中间对等体20’。

在找到新工作节点的同时，增大用于新目标对等体或新中间对等体的至少一个nodeID的步骤可继续。工作节点可称为锚点。这样，方法扫描在使用DHT本身的锚点之间的ID空间。因此，新颖方法在初始迭代时速度快。在一些迭代后，将有夹住故障对等体18的两个锚点（新目标对等体和新中间对等体），并且不能找到新锚点。这指示故障对等体18的位置已找到，并且因此完成过程并且验证故障对等体的故障。

如上所述，由于覆盖网络10中的节点需要知道沿顺时针路径和逆时针路径的其后续节点，因此，如图3所示的对等体14需要不但保持用于沿顺时针路径24的后续节点的顺时针指针表40，而且保持用于沿逆时针路径26的后续节点的逆时针指针表42。上述用于检测故障对等体的位置的步骤可实现为在对等体14中存储的应用44，并且例如由对等体14的处理器运行。

新颖方法的一个优点是无需昂贵的迭代路由选择。此外，方法能够用于通过适当选择两个锚点，验证覆盖网络的任何部分。需要添加到消息22的新字段32可只用一个比特表示顺时针或逆时针信息。因此，另外的报头大小为极小。

现在相对于图4描述实现上述机制的一种方法。方法包括确定沿第一路径从给定对等体发送到目标对等体的消息未到达目标对等体的步骤400、确定消息已到达的沿第一路径在给定对等体与目标对等体之间中间对等体的步骤402；使用第二路径将消息从给定对等体发送到目标对等体的步骤404，其中，第二路径与第一路径不同；以及确定消息沿第二路径已到达目标对等体的步骤406；调整目标对等体和中间对等体中至少之一的节点标识符以获得新目标对等体或新中间对等体的步骤408；以及再使用第一和第二路径将消息发送到新目标对等体或新中间对等体，直至检测到故障对等体的步骤410。

已确定故障对等体的位置后，其它对等体可配置成忽略该故障对等体。例如，如果大多数对等体实现上述新颖方法，则即使故障对等体是覆盖网络环的一部分，它们最终也将被忽略。在一个应用中，有在对等体之间共享的安全性证书。那些证书还需要撤销。此撤销可如随后所述来实现。

假设图5所示DHT覆盖50是负责指派证书到覆盖中所有对等体54的相同认证机构（即，注册服务器52）的一部分。托管注册服务器52并且负责存储和管理安全性证书（例如，证书对等体）的对等体56能够请求其它对等体54提供列表，该列表包括被感知或检测为故障对等体的对等体。证书对等体56能够将这些列表相关，并且确定在预确定数量的列表（由网络的管理员定义）中出现的那些对等体58。在识别可能的故障对等体58后，证书对等体56可配置成执行适当的动作，如撤销故障对等体的证书，或者添加怀疑的故障对等体到黑名单等。在一个应用中，注册服务器在步骤60中通知故障对等体有关此证书撤销动作或者黑名单动作，以便故障对等体被意识为到在其系统中的失常。

基于上述实施例，要注意的是，新颖机制有利地允许给定对等体定位故障对等体，并且在形成P2P网络的本地视图时忽略它。故障对等体行为不当的原因可以不是主动攻击，而它也可能是网络有关的错误。在一个示例实施例中，新颖机制允许扫描在两个对等体之间和怀疑的故障对等体附近的区域，以便确定故障对等体的位置。新颖机制不要求网络范围的解决方案或覆盖中的特殊状态（即，超对等体状态）。相反，新颖机制可在单独对等体实现，并且它们在本地存储检测的结果。因此，实现此机制无硬件升级要求。覆盖网络中的任何对等体能够配置（提供有适当应用）成分析怀疑的对等体是否有故障。

备选，新颖机制不要求在对等体之间交换的文本消息的特殊有效负载，并且因此避免了消息可能为恶意对等体不信任的一些现有方案的问题。另一优点是新颖方法提供用于警告和通知故障对等体有关此类状态和撤销其安全性证书的机制。还值得提及的是，新颖机制适合用于多个DHT算法和多个P2P信令协议，并且RELOAD只是一种可能情况。在一个应用中，单个对等体足以验证和查找覆盖网络中的可能故障对等体。

为便于说明而不是限制，图6中示出能够执行根据示范实施例的操作的代表性对等体结构的一个示例。硬件、固件、软件或其组合可用于执行本文所述的各种步骤和操作。

适合执行示范实施例中所述活动的示范对等体结构600可包括或不包括服务器601。此类服务器601可包括耦合到随机存取存储器(RAM) 604和只读存储器(ROM) 606的中央处理器(CPU) 602。ROM 606也可以是存储程序的其它类型的存储介质，如可编程ROM (PROM)、可擦除PROM (EPROM)等。处理器602可通过输入/输出(I/O)电路608和总线610与其它内部和外部组件进行通信以提供控制信号及诸如此类。如软件和/或软硬件指令指示的一样，处理器602执行如技术领域中熟知的多种功能。

服务器601也可包括一个或多个数据存储装置，包括硬盘和盘驱动器612、CD-ROM驱动器614及能够读取和/或存储信息的其它硬件，如DVD等。在一个实施例中，用于执行上述步骤的软件可在CD-ROM 616、可拆卸介质618或能够以便携方式存储信息的其它形式的介质上存储和分发。这些存储介质可插入诸如CD-ROM驱动器614、盘驱动器612等装置中并由其读取。服务器601可耦合到显示器620，显示器可以是任何类型的已知显示器或显示屏幕，如LCD显示器、LED显示器、等离子显示器、阴极射线管(CRT)等。提供了用户输入接口622，包括诸如鼠标、键盘、麦克风、触摸垫、触摸屏、话音识别系统等一个或多个用户接口机制。

服务器601可经网络耦合到其它计算装置，如地线和/或无线终端。服务器可以是如在诸如因特网628等全球网(GAN)中更大网络配置的一部分，这允许最终连接到各种地线和/或移动客户端/监视器装置。

公开示范实施例提供用于在用户终端接收位于来自通信网络的核心网络下游的缓存的内容时，防止分组信道超时的对等体装置、方法和计算机程序产品。应理解，此描述无意限制本发明。相反，示范实施例旨在涵盖在如随附权利要求书定义的本发明的精神和范围中包括的备选、修改和等效物。此外，在示范实施例的详细描述中，陈述了许多特定的细节以提供所述发明的详尽理解。然而，本领域的技术人员将理解，在无此类特定细节的情况下可实践各种实施例。

正如本领域的技术人员也将理解的一样，示范实施例可在无线通信装置、电信网络中实施为方法，或者在计算机程序产品中实施。相应地，示范实施例可采用完全硬件实施例或组合硬件和软件方面的实施例的形式。此外，示范实施例可采用在计算机可读存储介质上存储的计算机程序产品形式，在介质中包含有计算机可读指令。可利用任何合适的计算机可读介质，包括硬盘、CD-ROM、数字多功能盘(DVD)、光学存储装置或磁存储装置，如软盘或磁带。计算机可读介质的其它非限制性示例包括闪存类型的存储器或其它已知存储器。

虽然所示示范实施例的特征和实施例在特定组合的实施例中描述，但每个特征或元素可单独使用而无实施例的其它特征和元素，或者以带有或没有本文中公开的其它特征和元素的各种组合形式使用。本申请中提供的方法或流程图可在计算机可读介质中有形地包含的计算机程序、软件或固件中实现以便由专门编程的计算机或处理器执行。