在对等网络中限制存储消息

IPRDB

API 数据接口

专利申请

使用指引 chat嘟嘟

会员体验

联系我们

交流群

现在联系顾问~

在对等网络中限制存储消息
申请号	CN201080001586.3	申请日	2010-05-17	公开(公告)号	CN102037711A	公开(公告)日	2011-04-27
申请人	思科技术公司;			发明人	马尼什·巴德瓦耶; 济宁·田;
摘要	在不是彼此完全网合的DHT环的系统中，通过如下方式来限制PUT和GET消息的泛洪：将指示出来自内容提供商的内容的实际存储位置的内容键仅PUT到与该内容提供商相关联的根DHT，并且将指示出来自该内容提供商的内容可能存储在的DHT环的子集的辅助键仅PUT到内容提供商希望内容在其中可得的DHT环。当DHT接收到GET时，其首先根据内容键来判断其是否可提供内容，如果不能，则DHT从辅助键获得DHT环的子集并将对内容键的GET转发到相应的根DHT。
权利要求	1.一种装置，包括：在网络系统中的第一网络中的处理器，所述系统中的网络不是完全彼此网合；计算机可读存储介质，承载了用于使得处理器执行如下操作的指令：通过生成指示出内容片段的存储位置的内容描述符来对该内容的存储作出响应，所述内容是通过内容提供商在所述网络系统中的网络子集中存储内容来提供的，所述网络子集不是整个网络系统；将所述内容描述符仅发送到所述网络子集；以及将所述网络子集的描述符仅公布到所述网络系统中除了所述网络子集之外的希望网络，所述希望网络由所述内容提供商限定。 2.根据权利要求1所述的装置，其中，所述网络子集的描述符是使用PUT来公布的。 3.根据权利要求1所述的装置，其中，所述内容描述符被使用多播PUT仅发送到所述网络子集中的各个根节点。 4.根据权利要求1所述的装置，其中，所述网络系统是覆盖型分布式散列表(DHT)网络。 5.根据权利要求1所述的装置，其中，所述网络子集的描述符仅在所述网络子集改变时才被公布到所述希望网络。 6.根据权利要求1所述的装置，其中，如果由内容提供商“b”创建了内容“a”，则该内容“a”与形式为xri://a.b的可扩展资源指示符(xri)相关联，并且使用hash(xri://a.b)对该xri进行散列以生成所述内容描述符，所述网络子集的描述符是使用hash(xri://b)生成的。 7.一种有形的计算机可读介质，承载着可由与覆盖型网络中的节点相关联的计算机处理器执行来进行如下操作的指令：从请求者接收对来自内容提供商的内容的请求；对所述内容的可扩展资源标识符(xri)进行散列以生成内容键；对所述内容键执行GET；如果所述内容在所述节点中可得，则取回所述内容的内容位置描述符并将该内容位置描述符发送到所述请求者；否则生成内容提供商标识(CPI)键，该CPI键指示出所述覆盖型网络中来自所述内容提供商的内容所存储在的存储节点的子集；对所述CPI键执行GET以获得所述存储节点的子集的标识；以及将所述内容键的GET转发到与所述存储节点的子集的标识相关联的节点。 8.根据权利要求7所述的介质，其中，所述指令还使得所述处理器：从所述存储节点的子集中的至少一个节点取回指示出自其下载所述内容的相应资源的相应内容位置描述符；以及将一个或多个所述内容位置描述符返回到所述请求者。 9.根据权利要求8所述的介质，其中，所述覆盖型网络是DHT网络。 10.根据权利要求9所述的介质，其中，所述内容位置描述符被转发到所述存储节点的子集中的根DHT。 11.根据权利要求7所述的介质，其中，如果GET失败，则所述处理器生成去往所有其它对等节点的广播GET以找到所述内容位置描述符。 12.根据权利要求7所述的介质，其中，取回所述内容的所述处理器在将自身指示为资源的情况下在本地公布所述内容的内容位置描述符，从而允许来自同一请求者的其它请求在本地找到所述内容。 13.一种计算机实现的方法，包括：将指示出来自内容提供商的内容的实际存储位置的内容键仅PUT到与该内容提供商相关联的根分布式散列表(DHT)；将指示出来自所述内容提供商的内容可能存储在的DHT环的子集的辅助键仅PUT到所述内容提供商希望可得所述内容的DHT环；当接收到针对所述内容的GET时，根据所述内容键来判断是否可在本地提供所述内容，如果不能，则从所述辅助键获得与所述DHT环的子集相关联的标识信息并将针对所述内容的GET转发到相应的根DHT。 14.根据权利要求13所述的方法，其中，所述方法由DHT的网关组件中的处理器执行。 15.根据权利要求13所述的方法，其中，如果GET失败，则所述方法生成去往所有其它对等节点的广播GET以找到所述内容。 16.根据权利要求13所述的方法，包括使用多播PUT来发送所述内容键。 17.根据权利要求13所述的方法，包括仅在所述DHT环的子集改变时才PUT所述辅助键。 18.根据权利要求13所述的方法，其中，如果由内容提供商“b”创建了内容“a”，则该内容“a”与形式为xri://a.b的可扩展资源指示符(xri)相关联，并且对该xri进行散列以生成形式为hash(xri://a.b)的内容键，所述辅助键是通过对xri中的内容提供商字符串进行散列以产生形式为hash(xri://b)的描述符来生成的。 19.根据权利要求13所述的方法，其中，所述辅助键是内容提供商标识键。 20.根据权利要求13所述的方法，其中，所述内容键是每次所述内容提供商公布新的内容片段或者移动内容片段时放入的。
说明书全文	在对等网络中限制存储消息技术领域 [0001] 本申请一般地涉及对等网络，更具体地涉及对存储消息的广播泛洪(flooding)进行限制。背景技术 [0002] 对等网络是覆盖在另一网络(在此情况中，因特网)上的(有限量的对等设备的)网络的一个示例。在这样的网络中，通常是如下这种情况：一个对等者所需的内容片段或服务可由该覆盖型网络中的一个以上的其它节点提供。 [0003] 示例对等网络可以包括基于分布式散列表(DHT)的网络。DHT是一类分散化(decentralized)的分布式系统，这些系统提供类似于散列表的查找服务：多个(名称，值)对存储在DHT中，并且任意参与节点都能够高效地取回(retrieve)与给定名称相关联的值。维护从名称到值的映射的责任以使得参与者集合的改变引起最少量的破坏(disruption)的方式分布在节点之间。这有利地使得DHT可以扩大到极大量的节点并且可以处理不间断的节点到达、离开和失败。DHT形成了可用于构建更复杂服务的基础设施，所述更复杂服务例如是分布式文件系统、对等文件共享和内容分布系统、协作的web缓存、多播、任意播、域名服务和即时消息传递。附图说明 [0004] 参考附图可以最佳地理解本发明在结构和操作二者上的细节，附图中相似标号指示相似部分，并且其中： [0005] 图1是根据本发明原理的示例系统的框图； [0006] 图2是图1所示系统的一部分的框图； [0007] 图3是用于PUT的示例逻辑的流程图；以及 [0008] 图4是用于GET的示例逻辑的流程图。具体实施方式 [0009] 概述 [0010] 在此可以理解，可通过在对等化的DHT之间广播Put(放入)和Get(取得)消息(分别地，力图放置数据的消息和力图获取数据的消息)来实现DHT之间的对等化(例如，在实现DHT的服务提供商之间的对等化，与之形成对照的是在单个服务提供商领域内的各个客户端之间的对等化)。如果所有DHT与所有其它DHT直接相连，则广播是直接的，但是在此可以理解，如果进行对等化的DHT之间的关系在拓扑上更加复杂，使得一些DHT不与其它DHT直接相连(与在多个服务提供商之间的对等化的情况一样)，则泛洪Put和Get消息可能是昂贵的。事实上，在此可进一步理解，在所有其它DHT环中复制记录的这种要求极大地增大了各个DHT环中通过广播PUT而放置的记录的数目，这不利地影响了数据库查找等待时间。此外，广播GET消息导致在每一个DHT环中查找，这增大了消息传递开销。考虑到这些认知，提供了以下描述。 [0011] 在第一实施例中，一种装置具有在网络系统中的第一网络中的处理器。系统中的这些网络并不完全彼此网合(mesh)。一种计算机可读存储介质承载指令，用以使得处理器通过生成指示出内容片段的存储位置的内容描述符来对该内容的存储作出响应。内容由内容提供商来提供，内容提供商仅将内容存储在网络系统中的网络子集中。内容描述符仅被发送到该网络子集，而该网络子集的描述符仅被公布给网络系统中的希望网络。这些希望网络由内容提供商来限定。 [0012] 在一些示例中，使用PUT来公布网络子集的描述符。可使用多播PUT将内容描述符仅发送到网络子集的各个根节点。网络系统可以是覆盖型分布式散列表(DHT)网络，并且如果需要，仅在网络子集改变时才将网络子集的描述符公布给这些希望网络。 [0013] 在一些非限制性示例中，如果内容提供商“b”创建了内容“a”，则内容“a”与具有xri://a.b形式的可扩展资源指示符(xri)相关联。xri可以被散列化以生成内容描述符键。具体而言，可通过运算hash(xri://a.b)来生成内容描述符键，其中，网络子集的描述符由通过对xri中的内容提供商字符串进行散列化而生成的内容提供商键来索引。具体而言，可通过运算hash(xri://b)来生成网络子集的内容提供商描述符键。 [0014] 在另一实施例中，有形的计算机可读介质承载可由与覆盖型网络中用于从请求者接收对来自内容提供商的内容的请求的节点相关联的计算机处理器执行的指令。响应于该请求，内容的可扩展资源标识符(xri)被散列化来生成内容键，并且该内容键被执行GET。如果该内容在该节点上可得，则取回该内容的内容位置描述符并将其发送到请求者。否则，生成内容提供商标识(CPI)键，该CPI键指示出覆盖型网络中来自内容提供商的内容所存储在的存储节点的子集。对CPI键执行GET以获得这些存储节点的子集的标识，并将内容键的GET转发到与这些存储节点的子集的标识相关联的节点。 [0015] 在一些示例实施例中，指令还可使得处理器从存储节点的子集中的至少一个节点取回指示出要从其下载内容的相应资源的相应内容位置描述符。如果GET失败，则处理器可生成去往所有其它对等节点的广播GET以找到内容。如果需要，取回内容的处理器可以在本地DHT中公布内容的内容位置描述符，以指示出其自身为资源，从而允许同一DHT内的其它请求在本地找到内容。 [0016] 在另一实施例中，一种计算机实现的方法设想了将指示出来自内容提供商的内容的实际存储位置的内容位置描述符仅放入(PUT)与内容提供商相关联的根分布式散列表(DHT)。该方法包括将指示出来自内容提供商的内容可能存储在的DHT环的子集的辅助键(secondary key)仅放入内容提供商希望内容在其中可得的DHT环。当接收到对内容的GET时，根据内容键来判断是否可在本地提供内容，并且如果不能，则从辅助键获得与DHT环的子集相关联的标识信息。随后将针对该内容的GET转发到相应的根DHT。 [0017] 示例实施例 [0018] 本文中使用了如下首字母缩写词和定义： [0019] 自治DHT(AD)：独立于其它DHT而操作的DHT，其中，AD中的节点服务于整个DHT ID键空间。 [0020] 对等网关：DHT中的指定节点，该节点具有与其它AD中的一个或多个对等网关的因特网协议(IP)连通性，并且在本地DHT和(一个或多个)对等者之间转发Put、Get和对Get的响应。 [0021] 本源或原宿DHT：内容片段最初存储在的DHT，其是该内容的权威性源。 [0022] 本发明的原理适用于一个或多个使用情形。例如，在一个情形中，在单个提供商内提供了多个自治系统。更具体地，出于操作的原因，单个服务提供商可以选择将网络操作为自治系统(AS)的集合。各个AS可由不同的组织来运行。这些AS在路由的意义上不一定必须是真实AS。例如，AS可以是“自治DHT”(AD)。自治DHT是形成自己的独立DHT环并且与在很大程度上独立于其它AD而操作的一群节点。每一个AD有权访问完整的DHT ID空间，但是可以存储或者可以不存储其它AD中所存储的内容。在此情况中希望可选择性地从一个AD访问位于另一个AD中的内容。这种情形存在许多变体，例如，提供商具有一个作为提供商的内容的宿主(host)的AD，以及多个服务于不同区域或者不同类别的客户(例如，移动、DSL等)的AD。 [0023] 另一使用情形是在提供商之间的对等化，其中，操作DHT的服务提供商可能希望彼此对等化。这种情形与前一种情况的不同主要在于如下事实：无法在竞争的提供商之间假设高度协作或信任。因此，这种情形要求提供商之间适当水平的隔离和策略控制。这种情形的变体包括一些提供商其主要功能是作为内容的宿主，它们随后与主要功能是将客户连接到内容的提供商进行对等。其它变体可以包括一些提供商提供小型提供商与“主干”提供商之间的连通性。在上面两种使用情形中，提供商的图谱都不应当被假定为具有任意特定结构。 [0024] 因此，现在转向图1，网络12的系统10被组织成了层级，可以预期该层级在对等内容提供商之间发展。不应当假设严格的层级(在网络12当中仅具有单个根，并且每一个网络是至多一个父网络的子网络)，因为这种假设在实际情况中太有限制性。每一个网络12可以建立分布式散列表(DHT)。 [0025] 如图所示，每一个网络12可以包括如图所示的相应多个DHT存储节点14。每一个DHT存储节点14可以是DHT本身或者可以是另一个如同DHT的实体，该实体尽管在内部可能以某种其它方式来实现，但是仍支持DHT的Put/Get接口。在一个示例实施例中，每一个网络可以服务于完整的DHT键空间中的任意键的放入和取得。 [0026] 每一个网络12包括相应的网关节点16(下面将进一步论述)，其与其它网络12的一个或多个网关节点通信。因此，不是所有的存储节点14都与其它网络通信；而是，仅仅各个网络12的网关节点16与其它网络通信。通常，网关16执行下面的逻辑，但是如果需要，则网络12中的节点14可以代表网络执行该逻辑的全部或一部分。 [0027] 在图1所示的示例实施例中，网络12标有字母“A”-“F”，并且图1图示出可以不在网络12之间实现严格的自顶向下的层级。取代之，如图所示，网络“A”与网络“B”和“C”直接通信并且不与其它网络直接通信，而网络“B”与网络“A”、“E”和“F”直接通信。网络“E”和“F”彼此直接通信。网络“C”除了如上所述与网络“A”直接通信之外，还与仅仅一个其它网络(即，网络“D”)直接通信，而网络“D”不再与其它网络直接通信。 [0028] 于是，现在可以了解，DHT之间的对等可以是选择性的，就如同因特网服务提供商之间的对等是选择性的一样。因此，DHT之间的对等关系的图谱是任意的而不是完全网合，因为并不是每一个DHT都与系统10中的每一个其它DHT直接通信，尽管系统中的所有DHT都可通过其它DHT彼此间接通信。 [0029] 图2示出了一个网络(在此情况中，来自图1的网络A)的简化视图。如图所示，网络可以包括多个成员18(例如，上述DHT存储节点14之一)，每一个成员18通常具有一个或多个处理器20，处理器20访问一个或多个计算机可读存储介质22，例如但不限于固态存储装置和盘存储装置。通常，网络还包括至少一个相应网关24(例如，上述网关节点16)，网关24具有其自身的处理器26和计算机可读存储介质28，介质28可以包含由处理器26执行的当前逻辑。逻辑的其它部分可以由网络的一个或多个其它成员来实现。网络成员18可以包括但不限于端用户客户端设备、因特网服务器、路由器、交换机等。 [0030] 起初，通过执行PUT(键，值)操作来将数据存储在DHT中；值被存储在通常是一个并且仅仅一个DHT存储节点中由PUT消息的固定长度键字段指示的位置处。使用GET(键)操作来取回数据，这返回存储在由GET消息中的键字段指示的位置处的值。略加详细而言，通过对内容的可扩展资源标识符(xri)进行散列化以生成键来索引内容。键的值是包含内容所存储的位置(资源)的描述符。随后可通过如下方式来定位内容：对该xri进行散列化并且对生成的键执行GET以取回描述符，然后从描述符所列出的资源下载内容。在一些示例实施例中，单个平坦的键空间由所有DHT共用，并且所有DHT都可以PUT和GET通过该键空间中的键而索引的值。 [0031] 本发明的原理认识到可扩展资源标识符(xri)通常不仅仅包含内容的名称，而且包含附加信息，包括内容提供商的标识。在此还认识到，内容提供商的数目通常远小于内容片段的数目，并且很可能内容提供商和DHT运营商(服务提供商)将对内容公布达成协议，这意味着特定内容提供商将仅在DHT环的子集并且是不会频繁改变的子集中公布内容。 [0032] 因此，现在转向图3，不是使用广播PUT而是使用如下所述的多播PUT来在覆盖型网络(例如，上述的一个覆盖型网络)中公布内容。在块30，内容提供商/服务提供商对内容的xri进行散列化以生成内容键。于是，例如，由内容提供商“b”创建的内容“a”具有形式为xri://a.b的xri，并且xri被散列化以生成内容键＝hash(xri://a.b)。该内容键指示出内容位置描述符的实际存储位置。 [0033] 在块32，对xri中嵌入的内容提供商字符串进行散列化以生成辅助键，在此称为“内容提供商id”(CPI)键＝hash(xri://b)。CPI键为内容提供商描述符提供索引，该内容提供商描述符指示出覆盖型网络中来自相应内容提供商的内容可能存储在的存储节点(例如，DHT环)的子集。作不同表述，CPI键利用指向内容提供商(在上面的示例中，内容提供商“b”)已经放置或者有望放置内容的DHT的链接来为描述符提供索引。这些链接可以是这些DHT的公知对等节点(类似于BGP中的边界网关)，或者它们可以是环标识。在一些实施例中，通过CPI键建立的描述符对于不同DHT可以不同。例如，如果DHT“C”与DHT“B”具有特殊的对等关系，则在DHT“C”中公布的描述符(CPI键)可以仅仅包含到DHT“B”的链接，从而辅助基于每一个内容提供商存在复杂的对等关系。 [0034] 移至块34，将第一键(内容键)PUT到至少一个“根”DHT。“根”DHT的数目少于覆盖型网络中DHT的总数目，因而在块34处的PUT并非广播PUT而仅仅是多播PUT。实质上，第一(内容)键被PUT到特定服务提供商在其中公布的那些DHT环的根DHT，并且仅仅被PUT到那些根DHT。 [0035] 另一方面，在块36，将第二键(CPI键)PUT到内容提供商希望内容在其中可得的所有DHT环。在此可以理解，虽然在块36处PUT看起来是广播PUT，但是内容提供商在其中公布的DHT环的集合不可能频繁地改变，因而该PUT操作仅在内容提供商希望从其可搜索环的列表中添加/删除DHT环时才是必需的。 [0036] 因此，由CPI键表示的描述符建立了供内容提供商用来控制对其内容的访问的策略机制。预期内容提供商的数目远小于内容片段的数目，因而预期内容提供商描述符的数目将招致较小的存储开销。 [0037] 此外，虽然每次内容提供商公布新的内容片段或者移动内容片段时，需要将内容键多播PUT到内容提供商的“根”DHT，但是在诸如该内容提供商的“根”DHT改变之类的时间之前，即，在诸如内容提供商在其中公布内容的环的列表改变之类的时间之前，不需要PUT CPI键。 [0038] 图4图示出如何使用多播GET在上述覆盖型网络中取回内容。在块38，DHT中处理对内容的请求的节点在块40对内容的全部公布的xri进行散列化并且对生成的内容键执行GET。如果判定菱形块42指示出内容在该DHT中可得，则在块44取回内容的描述符。否则(即，在判定菱形块42处，GET失败)，逻辑流至块46以对(根据上述原理得出的)CPI键执行GET，因而取回来自该提供商的内容可能可得的DHT的列表。在块48，经由多播将对内容键的GET转发到在块46发现的“根”DHT。在块50，取回一个或多个内容位置描述符，这些描述符指示出要从其下载内容的资源，并且将这(一个或多个)描述符返回到发起GET的节点。 [0039] 于是，从根DHT取回的不是键而是由键所索引的描述符，如上所述，描述符是通过对内容的xri进行散列而生成的。当经由门户(portal)来广告内容时，使得xri对于作出请求的服务节点可得。 [0040] 在陈旧的CPI描述符或者对等DHT不向特定DHT提供内容的策略的情况下，图4中的GET可能失败。如果这种情况发生，则节点可借助于去往所有其它对等DHT的广播GET，作为查找内容的最后尝试。 [0041] 在一些示例实现方式中，作为进一步的增强，取回内容的节点随后基于策略以其自身作为资源在其本地DHT中公布内容的描述符，从而允许来自同一DHT的其它请求在本地找到内容并避免多播GET。所生成的这个描述符的寿命/刷新率可以取决于通过用于该内容提供商的描述符而强加的策略。例如，如果内容提供商指定“单次使用”，则该本地描述符将不被生成。 [0042] 如果需要，节点不必将其DHT添加作为该内容提供商的可能“根”，因为内容提供商已经通过将其添加到内容提供商描述中的DHT列表来完成这个动作。这消除了在从一个DHT向另一个DHT传递内容时在所有DHT中再次公布CPI描述符的需要。 [0043] 在一些实施例中，可以建立CPI键的结构/内容来建立对等关系、优选顺序、使用限制和其它策略细节。例如，CPI键可被用来不仅建立根节点的列表，而且例如通过从最优选到最不优选的顺序对根节点排序来建立对于访问由键表示的DHT的顺序的偏好。 [0044] 虽然在此示出并详细描述了具体的“在对等网络中限制存储消息”，但是应当了解，本公开所包含的主题仅由权利要求来限制。