受限廣播、dht之間的對等化、僅廣播受限內容的put的製作方法

2023-07-21 12:07:46

專利名稱：受限廣播、dht之間的對等化、僅廣播受限內容的put的製作方法
受限廣播、DHT之間的對等化、僅廣播受限內容的PUT技術領域
本申請一般地涉及對等網絡，更具體地涉及對廣播泛洪(flooding)進行限制、分 布式散列表(DHT)之間的對等化以及對諸如PUT之類的廣播存儲消息的內容進行限制。
背景技術：
對等網絡是覆蓋在另一網絡(在此情況中，網際網路)上的(有限量的對等設備的) 網絡的一個示例。在這樣的網絡中，通常是如下這種情況一個對等者所需的內容片段或服 務可由該覆蓋型網絡中的一個以上的其它節點提供。
分布式散列表(DHT)是一類分散化(decentralized)的分布式系統，這些系統提 供類似於散列表的查找服務多個(名稱，值)對存儲在DHT中，並且任意參與節點都能夠 高效地取回(retrieve)與給定名稱相關聯的值。維護從名稱到值的映射的責任以使得參 與者集合的改變引起最少量的破壞(disruption)的方式分布在節點之間。這有利地使得 DHT可以擴大到極大量的節點並且可以處理不間斷的節點到達、離開和失敗。DHT形成了可 用於構建更複雜服務的基礎設施，所述更複雜服務例如是分布式文件系統、對等文件共享 和內容分布系統、協作的web緩存、多播、任意播、域名服務和即時消息傳遞。


參考附圖可以最佳地理解本發明在結構和操作二者上的細節，附圖中相似標號指 示相似部分，並且其中
圖1是根據本發明原理的示例系統的框圖2是圖1所示系統的一部分的框圖3是用於轉發Get (取得)消息的示例邏輯的流程圖；以及
圖4是用於轉發Put (放入)消息的示例邏輯的流程圖。
具體實施方式
概述
在此可以理解，可通過在對等化的DHT之間廣播Put和Get消息(分別地，力圖放 置數據的消息和力圖獲取數據的消息)來實現DHT之間的對等化(例如，在實現DHT的服 務提供商之間的對等化，與之形成對照的是在單個服務提供商領域內的各個客戶端之間的 對等化)。如果所有DHT與所有其它DHT直接相連，則廣播是直接的，但是在此可以理解，如 果進行對等化的DHT之間的關係在拓撲上更加複雜，使得一些DHT不與其它DHT直接相連 (與在多個服務提供商之間的對等化的情況一樣)，則泛洪Put和Get消息可能是昂貴的。
在鏈路狀態路由協議中泛洪消息的技術不是很容易就可轉換到DHT對等化。首 先，與通過路由協議執行的相對不那麼頻繁的更新相比，對預期要頻繁廣播的Put和Get進 行泛洪的開銷在DHT對等化中更值得關注。其次，本文中所設想的在網絡之間的消息傳遞 與路由廣告不同，因為網關不保留關於先前看到的消息的狀態，這使得將泛洪解決方案從路由廣告問題轉移到在網絡之間傳遞消息的問題成為問題。
本發明的原理涉及減輕上述缺點中的一個或多個。
因此，一種裝置包括在網絡系統的第一網絡中的處理器。該系統中的網絡並不完 全彼此網合(mesh)。計算機可讀存儲介質承載指令，這些指令用以使得處理器從發送網絡 接收分布式散列表(DHT)數據傳送消息並在實現泛洪限制措施的情況下將該消息轉發到 其它網絡。如果該消息是PUT消息，則該PUT消息包含數據存儲鍵(key)位置、標識出存儲 與該PUT相關聯的內容的實體的數據存儲實體標識、以及返回到該數據存儲實體的網絡路 徑。
當數據傳送消息是DHT Put或Get消息時，泛洪限制措施可以包括在將消息繼續 轉發到其它網絡之前向接收到的Put或Get消息中的「已拜訪」列表附加接收網絡的標識， 並且不向出現在消息的「已拜訪」列表中的網絡轉發消息。可替代地或者除此之外，泛洪限 制措施可以包括如果消息的跳數超過閾值則不繼續轉發消息。當消息是DHT Put消息時， 泛洪限制措施可以包括當內容被更新時不在數據存儲實體處生成PUT。
在另一實施例中，一種有形的計算機可讀介質承載著指令，所述指令可由對象網 絡中的計算機處理器執行以用於在內容被存儲在該對象網絡中時而不是在內容在隨後被 更新時生成PUT消息。PUT消息包括對象網絡中的數據存儲位置鍵和到對象網絡的路徑。 所述指令包括將PUT消息發送到至少一個其它網絡。
在此實施例的示例實現方式中，對象網絡是並不彼此完全網合的網絡系統中的網 絡。即，至少第一 DHT不與第二 DHT直接通信，但通過第三DHT與第二 DHT間接通信。在這 種環境中，可能有必要通過在Put和Get消息從一個網絡傳遞到另一網絡時將關於Put或 Get消息已經經過的網絡集合的信息記錄在Put和Get消息中來跟蹤這些已經經過的網絡 的集合。當通過分布式散列表(DHT)來建立網絡時，介質可被實現在DHT的網關組件中。
在又一個實施例中，一種計算機實現的方法包括在對象網絡中的一組件處從不 完全網合的網絡系統中的發送網絡接收分布式散列表(DHT)數據傳送消息。如果消息是 Put或GET消息，則指令包括將對象網絡的標識添加到消息中的已拜訪網絡的列表，並將該 消息僅轉發到不在已拜訪網絡列表上的、對象網絡與其直接通信的其它網絡。此外，如果消 息是GET消息並且對象網絡存儲著作為GET消息的對象的內容，則指令包括使用已拜訪網 絡的列表將該內容發送到作出請求的網絡。另一方面，如果消息是PUT消息，則指令包括向 PUT消息添加接收到該PUT消息的網絡的標識，以使得PUT消息包含可動態改變的、從接收 網絡到存儲著與該PUT消息相關聯的內容的網絡的網絡路徑。換而言之，每當Put或Get 消息拜訪一序列的網絡時，都記錄指回到發起網絡的路徑，並且該路徑被記錄在消息自身 中以使得當路徑改變時，關於如何將路徑回溯到發起者的信息被包含在消息中。
示例實施例
本文中使用了如下首字母縮寫詞和定義
自治DHT(AD)獨立於其它DHT而操作的DHT，其中，AD中的節點服務於整個 DHT-ID鍵空間。
對等網關DHT中的指定節點，該節點具有與其它AD中的一個或多個對等網關的 網際網路協議(IP)連通性，並且在本地DHT和(一個或多個)對等者之間轉發Put、Get和對 Get的響應。
本源或原宿DHT 內容片段最初存儲在的DHT，其是該內容的權威性源。
本發明的原理適用於一個或多個使用情形。例如，在一個情形中，在單個提供商內 提供了多個自治DHT(AD)。每一個AD可以由不同組織來運行。在路由的意義上，這些AD可 以駐留或者可以不駐留在不同自治系統中。每一個AD都有權訪問完整的DHT-ID空間，但 是可以存儲或者可以不存儲其它AD中所存儲的內容。在此情況中希望可選擇性地從一個 AD訪問位於另一個AD中的內容。這種情形存在許多變體，例如，提供商具有一個作為提供 商的內容的宿主(host)的AD，以及多個服務於不同區域或者不同類別的客戶(例如，移動、 DSL 等)的 AD。
另一使用情形是在提供商之間的對等化，其中，操作DHT的服務提供商可能希望 彼此對等化。這種情形與前一種情況的不同主要在於如下事實無法在競爭的提供商之間 假設高度協作或信任。因此，這種情形要求提供商之間適當水平的隔離和策略控制。這種 情形的變體包括一些提供商其主要功能是作為內容的宿主，它們隨後與主要功能是將客戶 連接到內容的提供商進行對等。其它變體可以包括一些提供商提供小型提供商與「主幹」提 供商之間的連通性。
在上面的任一使用情形中，提供商的圖譜都不應當被假定為具有任意特定結構。
因此，現在轉向圖1，網絡12的系統10被組織成了寬鬆層級，可以預期這種寬鬆層 級在對等內容提供商之間發展。嚴格層級是這樣一種層級其中，在網絡12當中僅具有單 個根，並且每一個網絡是至多一個父網絡的子網絡。不應當假設這樣的嚴格層級，因為這種 假設在實際情況中太有限制性。每一個網絡12可以建立分布式散列表(DHT)。
如圖所示，每一個網絡12可以包括如圖所示的相應多個DHT存儲節點14。每一個 網絡12可以是DHT本身或者可以是另一個在如下意義上如同DHT的實體該實體儘管在內 部可能以某種其它方式來實現，但是仍支持DHT的Put/Get接口。在一個示例實施例中，每 一個網絡可以服務於完整的DHT鍵空間中的任意鍵的PUT和GET。
每一個網絡12包括相應的網關節點16(下面將進一步論述)，其與其它網絡12的 一個或多個網關節點通信。因此，不是所有的存儲節點14都與其它網絡通信；而是，僅僅各 個網絡12的網關節點16與其它網絡通信。通常，網關16執行下面的邏輯，但是如果需要， 則網絡12中的節點14可以代表網絡執行該邏輯的全部或一部分。
在圖1所示的示例實施例中，網絡12標有字母「A」- 「F」，並且圖1圖示出可以不 在網絡12之間實現嚴格的自頂向下的層級。取代之，如圖所示，網絡「A」與網絡「B」和「C」 直接通信並且不與其它網絡直接通信，而網絡「B」與網絡「A」、「E」和「F」直接通信。網絡 「E」和「F」彼此直接通信。
網絡「C」除了如上所述與網絡「A」直接通信之夕卜，還與僅僅一個其它網絡(S卩，網 絡「D」)直接通信，而網絡「D」僅與一個其它網絡「C」直接通信。
於是，現在可以了解，DHT之間的對等可以是選擇性的，就如同網際網路服務提供商 之間的對等是選擇性的一樣。因此，DHT之間的對等關係的圖譜是任意的而不是完全網合， 因為並不是每一個DHT都與系統10中的每一個其它DHT直接通信，儘管系統中的所有DHT 都可通過其它DHT彼此間接通信。
圖2示出了一個網絡(在此情況中，來自圖1的網絡A)的簡化視圖。如圖所示， 網絡可以包括多個成員18 (例如，上述DHT存儲節點14之一)，每一個成員18通常具有一個或多個處理器20，處理器20訪問一個或多個計算機可讀存儲介質22，例如但不限於固態 存儲裝置和盤存儲裝置。通常，網絡還包括至少一個相應網關M (例如，上述網關節點16)， 網關M具有其自身的處理器沈和計算機可讀存儲介質觀，介質觀可以包含供處理器沈 執行的當前邏輯。邏輯的其它部分可以由網絡的一個或多個其它成員來實現。網絡成員18 可以包括但不限於端用戶客戶端設備、網際網路伺服器、路由器、交換機等。
圖3圖示出了示例「GET」消息邏輯。首先，在塊30通過執行PUT (鍵，值)操作將 數據存儲在DHT中；該值被存儲在通常一個並且僅僅一個DHT中的由PUT消息的固定長度 鍵欄位指示的位置處。使用GET(鍵)操作來取回數據，該操作返回存儲在由GET消息中的 鍵欄位指示的位置處的值。在一些示例實施例中，單個平坦的鍵空間由所有DHT共用，並且 所有DHT都可以PUT和GET通過該鍵空間中的鍵而索引的值。
當需要在塊30存儲的內容片段或其它數據時，在塊32由需要該內容的節點廣播 GET消息。在網絡12中的一個網絡中廣播的GET必須被泛洪到作出請求的網絡與其具有對 等關係的所有網絡；這些網絡必需將該GET泛洪到它們的對等者；依此類推，直到所有網絡 12都已被聯繫為止。
在此可以理解，希望限制泛洪的範圍和消息傳遞量。因此，在塊34，每一個被泛洪 的GET消息被接收到該消息的網絡12增大以包含已經拜訪過的DHT/網絡的列表。可以假 設實現一種命名協定，通過該命名協定可以唯一地標識各個DHT/網絡。一旦消息第二次到 達一個DHT/網絡，例如在塊36，該消息不被再次轉發到該GET消息中包含的列表上的DHT。
此外，通過將該已拜訪DHT/網絡的列表保持作為有序列表，建立了返回到作出請 求的DHT的可行路徑。例如，如果從圖1中的網絡A向網絡B再向網絡F泛洪GET消息，並 且對鍵的查找在網絡F中成功，則在塊38，查找的結果被往回發送到網絡B，然後到網絡A， 然後返回到請求了原始的GET操作的網絡中的節點18。
如果需要，在塊40，可以在廣播消息中使用跳數來限制它們的傳播。S卩，每次GET 消息拜訪網絡時，就將GET消息中的跳數欄位遞增1，並且當跳數達到閾值時，達到閾值的 網絡不再轉發該GET消息。
圖4圖示出了可用於例如流行內容(popular content)的示例廣播PUT邏輯。在 塊42，當在一個DHT/網絡中執行PUT操作時，在塊44將該PUT操作泛洪到所有其它網絡。 但是，如塊44所示，PUT中僅包括指回到存儲網絡的指針。即，Put消息傳達存儲了內容的 網絡的身份，但是不傳達內容自身。這消除了每次內容被更新時都廣播新的廣播PUT的需 要，與此同時還去除了對廣播GET的需要。在除了存儲了內容的DHT之外的任意DHT中的 GET可被直接轉發到存儲了內容的「原宿DHT」，而不是被廣播。
例如，如果新的內容片段存儲在圖1的網絡A中，則消息被泛洪到所有其它網絡。 該消息包含原始PUT中使用的鍵、以及網絡A的標識符。當消息到達各個新網絡時，在塊 46，保持已拜訪的網絡序列的記錄，並且在各個網絡中，序列記錄(而不是內容自身，內容 僅僅存儲在單個網絡中)被存儲在由來自存儲網絡的鍵指示出的接收網絡中的相應位置， 並且在繼續轉發之前，已拜訪網絡的名稱被添加到PUT。例如，在網絡A中的位置「k」處執 行的PUT被轉發到網絡B並被存儲在網絡B中的位置「k」處。PUT隨後被轉發到網絡F，網 絡F在網絡F中的位置「k」處維護經由網絡B往回指向網絡A的記錄。這樣，除了存儲內 容的DHT ( 「原宿DHT」 )的「名稱」之外，還存儲了回到該DHT的路徑，從而使得PUT消息具7有Put (鍵，值，路徑)和Get (鍵，路徑)的格式，而對等網絡16對路徑實現操作以(a)防 止形成環路和(b)將Get轉發回適當DHT以獲得內容。
其結果是，所有網絡都了解如何獲得特定內容片段，即使內容僅被存儲在單個「原 宿」網絡中也是如此。在原宿網絡中執行對內容的更新，而不通知任何其它網絡。
除了上述以外，本發明的原理還在一些示例實施例中設想可通過策略來影響PUT 和GET消息在網絡之間的轉發。例如，當內容片段存儲在給定DHT中時，策略可以如下這麼 簡單「不要使任何其它DHT可獲得該內容片段」或者「僅使DHT B可獲得該內容」。
現在可以了解，在DHT之間對PUT和GET的泛洪機制被提供來使得在一個DHT中 公布的內容可在另一個DHT中取回。還應當了解，本發明的原理不要求DHT之間的完全網 合連通性，此外，可以輔助將內容選擇性地公布給選定的DHT。作為優化，還包括一種用於存 儲往回指向內容片段的原宿DHT的指針的機制。
有利地，在上述示例邏輯中，DHT不必完全網合，並且可以定位流行的頻繁更新的 內容而無需完全廣播GET並且無需在內容被更新時再次廣播PUT。而且，如果需要，則可由 各個DHT獨立地實現用於控制內容流動的策略。
雖然在此示出並詳細描述了具體的「受限廣播、DHT之間的對等化、僅廣播受限內 容的PUT」，但是應當了解，本公開所包含的主題僅由權利要求來限制。
權利要求
1.一種裝置，包括在網絡系統中的第一網絡中的處理器，所述系統中的網絡不是完全彼此網合； 計算機可讀存儲介質，承載了用於使得處理器執行如下操作的指令 從發送網絡接收分布式散列表(DHT)數據傳送消息； 將該消息繼續轉發到其它網絡； 實現至少一個泛洪限制措施；以及如果所述消息是PUT消息，則該PUT消息包含數據存儲鍵位 置、標識出存儲了與該PUT相關聯的內容的實體的數據存儲實體標 識、和返回到所述數據存儲實體的網絡路徑。
2.根據權利要求1所述的裝置，其中，所述數據傳送消息是DHTPut消息，並且所述泛 洪限制措施包括在所述內容被更新時不在所述數據存儲實體處生成PUT。
3.根據權利要求1所述的裝置，其中，所述數據傳送消息是DHTPut消息或DHT Get消肩、ο
4.根據權利要求3所述的裝置，其中，所述泛洪限制措施包括在將接收到的DHT消息繼 續轉發到其它網絡之前向該DHT消息中的「已拜訪」列表附加接收網絡的標識。
5.根據權利要求4所述的裝置，其中，所述泛洪限制措施包括不將消息繼續轉發到出 現在該消息的「已拜訪」列表中的網絡。
6.根據權利要求4所述的裝置，其中，所述泛洪限制措施包括如果消息中的跳數超過 了閾值，則不繼續轉發該消息。
7.一種方法，包括從發送網絡接收分布式散列表(DHT)數據傳送消息； 將該消息繼續轉發到其它網絡； 實現至少一個泛洪限制措施；以及如果所述消息是PUT消息，則在PUT消息中實現數據存儲鍵，該PUT消息包含數據存儲 鍵位置、標識出存儲了與該PUT相關聯的內容的實體的數據存儲實體標識、和返回到所述 數據存儲實體的網絡路徑。
8.根據權利要求7所述的方法，其中，所述數據傳送消息是DHTPut消息，並且所述泛 洪限制措施包括在所述內容被更新時不在所述數據存儲實體處生成PUT。
9.根據權利要求7所述的方法，其中，所述數據傳送消息是DHTPut消息或DHT Get消肩、ο
10.根據權利要求9所述的方法，其中，所述泛洪限制措施包括在將接收到的DHT消息 繼續轉發到其它網絡之前向該DHT消息中的「已拜訪」列表附加接收網絡的標識。
11.根據權利要求10所述的方法，其中，所述泛洪限制措施包括不將消息繼續轉發到 出現在該消息的「已拜訪」列表中的網絡。
12.根據權利要求10所述的方法，其中，所述泛洪限制措施包括如果消息中的跳數超 過了閾值，則不繼續轉發該消息。
13.一種計算機實現的方法，包括在對象網絡中的組件處從不完全網合的網絡系統中的發送網絡接收分布式散列表 (DHT)數據傳送消息；如果所述消息是與內容相關聯的PUT或GET消息，則向該PUT或GET消息中的已拜訪 網絡列表添加所述對象網絡的標識；如果所述消息是PUT或GET消息，則將該PUT或GET消息僅轉發到不在所述已拜訪網 絡列表中的、與所述對象網絡直接通信的其它網絡；以及如果所述消息是GET消息並且所述對象網絡存儲著作為該GET消息的對象的內容，則 使用所述已拜訪網絡列表將所述內容發送到作出請求的網絡。
14.根據權利要求13所述的方法，其中，所述方法由DHT的網關組件中的處理器執行。
15.根據權利要求13所述的方法，包括在內容被更新時不生成PUT消息。
16.根據權利要求13所述的方法，包括通過將與內容相關聯的PUT消息已拜訪的網絡 列表存儲在已由該PUT消息拜訪的每一個DHT中來存儲返回到所述內容的路徑。
17.根據權利要求16所述的方法，包括在將接收到的PUT或GET消息繼續轉發到其它 網絡之前，將接收網絡的標識附加到該接收到的消息中的「已拜訪」列表。
18.根據權利要求17所述的方法，包括不將消息繼續轉發到出現在該消息的「已拜訪」 列表中的網絡。
19.根據權利要求16所述的方法，包括如果消息中的跳數超過了閾值則不繼續轉發該消息。
20.一種計算機裝置，包括數據存儲介質，承載著可由處理器執行來進行以下操作的指令在對象網絡中的組件處從不完全網合的網絡系統中的發送網絡接收分布式散列表 (DHT)數據傳送消息；如果所述消息是與內容相關聯的PUT或GET消息，則向該PUT或GET消息中的已拜訪 網絡列表添加所述對象網絡的標識；如果所述消息是PUT或GET消息，則將該PUT或GET消息僅轉發到不在所述已拜訪網 絡列表中的、與所述對象網絡直接通信的其它網絡；以及如果所述消息是GET消息並且所述對象網絡存儲著作為該GET消息的對象的內容，則 使用所述已拜訪網絡列表將所述內容發送到作出請求的網絡。
21.根據權利要求20所述的裝置，其中，所述方法由DHT的網關組件中的處理器執行。
22.根據權利要求20所述的裝置，所述指令包括在內容被更新時不生成PUT消息。
23.根據權利要求20所述的裝置，所述指令包括通過將與內容相關聯的PUT消息已拜 訪的網絡列表存儲在已由該PUT消息拜訪的每一個DHT中來存儲返回到所述內容的路徑。
24.根據權利要求23所述的裝置，所述指令包括在將接收到的PUT或GET消息繼續轉 發到其它網絡之前，將接收網絡的標識附加到該接收到的消息中的「已拜訪」列表。
25.根據權利要求M所述的裝置，所述指令包括不將消息繼續轉發到出現在該消息的 「已拜訪」列表中的網絡。
26.根據權利要求23所述的裝置，所述指令包括如果消息中的跳數超過了閾值則不繼 續轉發該消息。
全文摘要
在不是完全彼此網合併且能夠處理分布式散列表(DHT)Put和Get消息的網絡系統中，通過維護GET 拜訪過的DHT的列表來限制GET消息的消息泛洪。此外，PUT消息不僅包括原宿網絡中的存儲位置鍵而且還包括PUT已拜訪的網絡的列表，這實質上在PUT內建立了返回到原宿網絡的動態改變的路徑。
文檔編號H04L29/08GK102037712SQ201080001587
公開日2011年4月27日 申請日期2010年5月17日 優先權日2009年5月18日
發明者布魯斯·斯圖爾特·戴維, 濟寧·田, 簡·莫德韋德 申請人:思科技術公司