將資源請求與對應的資源會合的製作方法

2023-10-08 18:04:44

專利名稱：將資源請求與對應的資源會合的製作方法
技術領域：
本發明涉及訪問資源，尤其涉及將資源請求與對應的資源會合。
背景技術：
計算機系統和相關技術影響了社會的許多方面。實際上，計算機系統處理信息的能力已經轉變了人們生活和工作的方式。計算機系統現在通常執行在計算機系統出現之前手動執行的大量任務(例如，文字處理、調度和資料庫管理)。最近，計算機系統被彼此耦合且耦合至其它電子設備以形成有線和無線計算機網絡，通過該計算機網絡，計算機系統和其它電子設備能夠傳輸電子數據。結果，在計算機系統處執行的許多任務(例如，語音通信、訪問電子郵件、控制家用電器、web瀏覽和列印文檔)包括多個計算機系統和/或其它電子設備之間經由有線和/或無線計算機網絡的電子通信。
然而，為利用網絡資源來執行計算機化的任務，計算機系統必須具有標識和訪問網絡資源的某些方式。因此，通常向資源分配唯一標識符，例如網絡地址，該標識符唯一地標識了資源並可用於將一個資源與其它資源區別開來。由此，希望利用資源的計算機系統能夠使用對應於該資源的網絡地址連接到該資源。然而，如果計算機系統對於網絡資源的網絡地址沒有先驗知識，則訪問網絡資源是困難的。例如，計算機系統無法在網絡印表機上列印文檔，除非計算機系統(或另一網絡化計算機系統)知道該網絡印表機的網絡地址。
因此，開發了各種機制(例如，域名系統(「DNS」)、現用目錄(「AD」)、分布式文件系統(「DFS」))以使計算機系統能夠標識(和訪問)先前未知的資源。然而，由於可通過不同計算機網絡訪問的資源(例如，設備和服務)的量和多樣性，通常要求開發者開發實現各種不同的資源標識和訪問機制的應用程式。每一不同的機制可具有不同的編碼要求，並且可能不向開發者提供應用程式中所需的所有功能。
例如，儘管DNS具有分布式管理體系結構(即，不需要集中式管理)，然而DNS不夠動態、不是自組織的、支持弱數據和查詢模型、且具有一組固定的根。另一方面，AD足夠動態，但需要集中式管理。此外，不同機制的各方面可能不彼此兼容。例如，使用DNS標識的資源可能不與DFS路由協議兼容。由此，開發者可能被迫選擇最合適的機制並放棄其它機制的優點。
用於標識資源的機制在對等網絡中尤其是有問題的。DNS提供了一種查找服務，它以主機名作為關鍵字並以IP位址作為值，它依賴於一組特殊根伺服器來實現查找請求。此外，DNS需要信息(NS記錄)的管理以允許客戶機分層地導航名稱伺服器。由此，在能夠在網絡上標識資源之前，必須將資源輸入到DNS中。在節點頻繁地連接到網絡和與網絡斷開的更大規模的網絡中，依賴於信息的輸入並非總是切實可行的。另外，DNS被專門化為找出主機或服務的任務，並且一般不適用於其它類型的資源。
因此，開發了用於資源標識和訪問的其它機制以試圖克服這些缺點。多種機制包括比DNS更可伸縮的分布式查找協議。這些機制使用各種節點排列和路由算法將請求路由到對應的資源並儲存用於查找的信息。
這些機制中的至少一種利用了網絡中每一節點處的本地多層近鄰映射以將消息路由到目的地節點。這本質上導致這樣一種體系結構每一節點是對應的節點樹(其近鄰映射中的節點)的根節點。消息被逐位遞增地路由到目的地ID(例如，***6＝＞**46＝＞，*346＝＞2346，其中*表示通配符)。這些類型機制的路由效率是O(logN)個路由中繼段，並且要求節點維護大小為O(logN)的路由表。
這些機制中的至少一種其它機制向節點分配從線性數字環中取出的唯一ID。節點維護包含指針的路由表，該指針指向其直接後繼節點(依照ID值)並指向其ID值是值ID+2L的最接近後繼節點的那些節點。這些類型的機制的路由效率也是O(logN)個路由中繼段，並要求節點維護大小為O(logN)的路由表。
至少一種另外的機制需要O(log N1/d)個路由中繼段，且需要節點維護大小為O(D)的路由表。由此，所有這些機制的路由效率至少部分地依賴於系統中的節點數。
此外，由於ID(對於至少某些機制)可以圍繞環均勻地分布，因此總是存在環上節點之間的路由將導致某種低效率的可能性。例如，路由中繼段可穿越極大的地理距離、穿越更昂貴的鏈路、或通過不安全的域等等。另外，當消息路由涉及多個中繼段時，存在這一事件將發生多次的某種機會。不幸的是，這些機制未考慮節點相對於彼此的(物理或其它)鄰近性。例如，取決於節點在環上的分布，將消息從紐約路由到波士頓可涉及將消息從紐約路由到倫敦到亞特蘭大到東京然後到波士頓。
因此，至少一種其它更新近的機制通過將鄰近性定義為單個標量鄰近性度量(例如，IP路由中繼段或地理距離)來考慮鄰近性。這些機制使用基於鄰近性的路由表條目選擇的概念。由於對每一路由表條目存在許多「正確的」候選節點，因此這些機制試圖從候選節點中選擇一個最接近的節點。從這些機制中，可以提供允許每一節點確定具有給定IP位址的節點到其自身的「距離」的功能。消息在更接近的鄰近節點之間路由，以在路由到較遠的節點之前朝向目的地前進。由此，可保存某些資源，且路由更有效。
不幸的是，這些現有機制通常不提供節點之間的對稱關係(即，如果第一節點將第二節點認為是其夥伴，則第二節點也將第一節點認為是其夥伴)、在環上兩個方向上(順時針和逆時針)路由消息、基於多個鄰近性度量劃分節點的鍊表、以及基於多個鄰近性度量路由消息等等。因此，利用這些機制將資源請求與對應的資源會合的系統、方法、電腦程式產品將是有利的。

發明內容
本發明的原理克服了現有技術的上述問題，本發明針對用於將資源請求與對應的資源會合的方法、系統和電腦程式產品。在某些實施例中，劃分聯盟基礎結構的節點。訪問包含分配給聯盟基礎結構中的節點的節點ID的已排序鍊表。訪問表示用於劃分該已排序鍊表的多個不同的鄰近性準則的鄰近性類別。該已排序鍊表基於第一鄰近性準則被劃分成一個或多個第一子列表，這一個或多個第一子列表中的每一個包含來自該已排序鍊表的節點ID的至少一個子集。從一個或多個第一子列表中選擇的第一子列表基於第二鄰近性準則被劃分成一個或多個第二子列表，這一個或多個第二子列表的每一個包含第一子列表中包含的節點ID的至少一個子集。
在其它實施例中，例如，如圖3所示，填充節點路由表。將一直接前導節點插入到該路由表中。將一直接後繼節點插入到該路由表中。將適當的鄰域節點標識符插入到該路由表中，鄰域節點是基於預定或估算的鄰域範圍和鄰域大小在第一方向和第二相反方向上從已排序鍊表中標識的。將適當的節點標識符插入到該路由表中，路由節點是基於聯盟基礎結構的ID空間的數基和欄位大小在第一和第二方向上從已排序鍊表中標識的，路由節點表示已排序鍊表在第一和第二方向上的對數索引。
在又一些其它實施例中，可考慮到鄰近性準則來填充節點路由表。將當前節點所參與的每一分層劃分的路由環的前導節點插入到路由表中，每一分層劃分的路由環是依照對應的鄰近性準則來劃分的，且包含父環的雙向鍊表的至少一個子集。將當前節點所參與的每一分層劃分的路由環的後繼節點插入到該路由表中。將當前節點所參與的每一分層劃分的路由環的適當的鄰域節點插入到該路由表中。將當前節點所參與的每一分層劃分的路由環的適當的路由節點插入到該路由表中。
在再一些其它實施例中，潛在低基於定義對應的一個或多個節點類的一個或多個鄰近性準則將消息向目的地節點路由。接收節點接收消息以及知識目的地節點的目的地號和可任選的一個或多個鄰近性準則。可能在當前節點類的節點之中的接收節點確定它是下列的至少之一在數字上比對應的前導節點離目的地號更遠，以及在數字上比對應的後繼節點離目的地號更遠。確定目的地不在對應於接收節點的一組鄰域節點中，該組鄰域節點可能在當前節點類的節點中。
從路由表中標識對應於接收節點的中間節點，該中間節點在數字上比對應的路由表中的其它路由節點離目的地號更近。消息被發送到該中間節點。該中間節點可繼續路由消息。當接收該消息的節點在數字上比其後繼或前導節點離目的地號更近時，該消息最終到達目的地節點。在路由是基於一個或多個鄰近性準則的實施例中，該數字接近性可以相對於選中節點類中的節點。
由此，基於鄰近性準則路由消息包括通過在給定的鄰近環(節點類)中漸進地移向離目的地節點更近，直到無法通過在該環內路由來作出更多的前進，來路由到目的地節點(ID)。確定無法作出更多的前進是在目的地號位於當前節點的ID與其後繼或前導節點的ID之間時發生的。在這一點上，當前節點通過它所參與的下一更大的鄰近環中其父節點來開始路由。通過沿朝向根環的劃分路徑攀爬來漸進地移向目的地的這一過程在到達目的地節點時終止。
本發明的這些和其它目的和特徵可以從以下描述和所附權利要求書中完全清楚，或可以通過如下所述的對本發明的實踐而學到。


為進一步闡明本發明的上述和其它優點和特徵，將參考附圖中所示的其具體實施例來呈現本發明的更具體描述。可以理解，這些附圖僅描述了本發明的典型實施例，並且因此不被認為是限制其範圍。本發明將通過使用附圖用附加的特殊性和細節來描述和解釋，附圖中圖1示出了聯盟基礎結構的一個示例。
圖2示出了便於將請求間接路由到夥伴的計算機體系結構的示例。
圖3示出了聯盟基礎結構中節點之間已排序列表和對應的環的形式的示例性二元關係。
圖4示出了便於鄰近性路由的環的示例環。
圖5示出了便於鄰近性路由的環的示例性由鄰近性導出的分區樹。
圖6示出了用於本發明的原理的合適的操作環境。
圖7示出了考慮鄰近性準則來填充節點路由表的方法的示例流程圖。
圖8示出了劃分聯盟基礎結構的節點的方法的示例流程圖。
圖9示出了填充節點路由表的方法的示例流程圖。
圖10示出了數字地將消息朝向目的地節點路由的方法的示例流程圖。
圖11示出了鄰近地將消息朝向目的地節點路由的方法的示例流程圖。
具體實施例方式
本發明的原理克服了現有技術的上述問題，本發明針對用於將資源請求與對應的資源會合的方法、系統和電腦程式產品。在某些實施例中，劃分聯盟基礎結構的節點。訪問包含分配給聯盟基礎結構中的節點的節點ID的已排序鍊表。訪問表示用於劃分該已排序鍊表的多個不同的鄰近性準則的鄰近性類別。該已排序鍊表基於第一鄰近性準則被劃分成一個或多個第一子列表，這一個或多個第一子列表中的每一個包含來自該已排序鍊表的節點ID的至少一個子集。從一個或多個第一子列表中選擇的第一子列表基於第二鄰近性準則被劃分成一個或多個第二子列表，這一個或多個第二子列表的每一個包含第一子列表中包含的節點ID的至少一個子集。
在其它實施例中，例如，如圖3所示，填充節點路由表。將一直接前導節點插入到該路由表中。將一直接後繼節點插入到該路由表中。將適當的鄰域節點標識符插入到該路由表中，鄰域節點是基於預定或估算的鄰域範圍和鄰域大小在第一方向和第二相反方向上從已排序鍊表中標識的。將適當的路由節點標識符插入到該路由表中，路由節點是基於聯盟基礎結構的ID空間的數基和欄位大小在第一和第二方向上從已排序鍊表中標識的，路由節點表示已排序鍊表在第一和第二方向上的對數索引。
在又一些其它實施例中，可考慮到鄰近性準則來填充節點路由表。將當前節點所參與的每一分層劃分的路由環的前導節點插入到路由表中，每一分層劃分的路由環是依照對應的鄰近性來劃分的，且包含父環的雙向鍊表的至少一個子集。將當前節點所參與的每一分層劃分的路由環的後繼節點插入到該路由表中。將當前節點所參與的每一分層劃分的路由環的適當的鄰域節點插入到該路由表中。將當前節點所參與的每一分層劃分的路由環的適當的路由節點插入到該路由表中。
在再一些其它實施例中，潛在地基於定義對應的一個或多個節點類的一個或多個鄰近性準則將消息向目的地節點路由。接收節點接收消息以及指示目的地節點的目的地號和可任選的一個或多個鄰近性準則。可能在當前節點類的節點之中的接收節點確定它在數字上比對應的前導節點離目的地號更遠，並在數字上比對應的後繼節點離目的地號更遠。確定目的地不在對應於接收節點的一組鄰域節點中，該組鄰域節點可能在當前節點類的節點中。
從路由表中標識對應於接收節點的中間節點，該中間節點在數字上比對應的路由表中的其它路由節點離目的地號更近。消息被發送到該中間節點。該中間節點可繼續路由消息。當接收該消息的節點在數字上比其後繼或前導節點離目的地號更近時，該消息最終到達目的地節點。在路由是基於一個或多個鄰近性準則的實施例中，該數字接近性可以相對於選中節點類中的節點。
由此，基於鄰近性準則路由消息包括通過在給定的鄰近環(節點類)中漸進地移向離目的地節點更近，直到無法通過在該環內路由來做出更多的前進，來路由到目的地節點(ID)。確定無法做出更多的前進是在目的地號位於當前節點的ID與其後繼或前導節點的ID之間時發生的。在這一點上，當前節點通過它所參與的下一更大的鄰近環中其父節點來開始路由。通過沿朝向根環的劃分路徑攀爬來漸進地移向目的地的這一過程在到達目的地節點時終止。
本發明範圍內的實施例包括用於承載或其上具有計算機可執行指令或數據結構的計算機可讀介質。這一計算機可讀介質可以是可由通用或專用計算機系統訪問的任何可用介質。作為示例而非局限，這一計算機可讀介質可包括諸如RAM、ROM、EPROM、CD-ROM或其它光碟存儲、磁碟存儲或其它磁存儲設備等物理存儲介質，或可用於以計算機可執行指令、計算機可讀指令或數據結構的形式承載或儲存期望的程序代碼手段並可由通用或專用計算機系統訪問的任何其它介質。
在本說明書以及所附權利要求書中，「網絡」被定義為允許在計算機系統和/或模塊(例如，硬體和/或軟體模塊)之間傳輸電子數據的一個或多個數據鏈路(可能具有不同的速度)。當信息通過網絡或另一通信連接(硬布線、無線或硬布線和無線的組合)傳輸或提供給計算機系統時，該連接被適當地視為計算機可讀介質。由此，任何這樣的連接被適當地稱為計算機可讀介質。上述組合也應當被包括在計算機可讀介質的範圍之內。計算機可執行指令包括，例如使通用計算機系統或專用計算機系統執行某一個功能或一組功能的指令和數據。計算機可執行指令可以是，例如二進位代碼、諸如彙編語言等中間格式指令、或甚至是原始碼。在某些實施例中，例如，諸如專用集成電路或門陣列等硬體模塊被優化成實現本發明的原理。
在本說明書以及所附權利要求書中，「節點」被定義為共同工作以在電子數據上執行操作的一個或多個軟體模塊、一個或多個硬體模塊或其組合。例如，節點的定義包括個人計算機的硬體組件，以及諸如個人計算機的作業系統等軟體模塊。模塊的物理布局不是重要的。節點可包括通過網絡耦合的一個或多個計算機。同樣，節點可包括單個物理設備(諸如行動電話或個人數字助理「PDA」)，其中內部模塊(諸如存儲器和處理器)共同工作以在電子數據上執行操作。此外，節點可包括例如，諸如包括專用集成電路的路由器等專用硬體。
本領域的技術人員可以理解，本發明可以在具有許多類型的節點配置的網絡計算環境中實施，包括個人計算機、膝上型計算機、手持式設備、多處理器系統、基於微處理器或可編程消費者電子產品、網絡PC、小型機、大型計算機、行動電話、PDA、尋呼機、路由器、網關、代理程序、代理伺服器、防火牆、重定向器、網絡地址轉換器等等。本發明也可在分布式系統環境中實施，其中通過網絡連接(經由硬布線數據鏈路、無線數據鏈路或通過硬布線和無線數據鏈路的組合)的本地和遠程節點都執行任務。在分布式系統環境中，程序模塊可位於本地和遠程存儲器存儲設備兩者中。
聯盟基礎結構圖1示出了聯盟基礎結構100的一個示例。聯盟基礎結構100包括可形成不同類型的聯盟夥伴關係的節點101、102、103。例如，節點101、102、103可以作為對等體在彼此之間聯盟而不需要根節點。節點101、102和103的每一個分別具有對應的ID 171、182和193。
一般而言，節點101、102、103可利用聯盟協議來形成夥伴關係並交換信息(例如，涉及與其它節點的交互的狀態信息)。夥伴關係的形成和信息的交換便於更有效且更可靠地訪問資源。其它中間節點(未示出)可存在於節點101、102和103(例如，具有171和193之間的ID的節點)之間。由此，例如，在節點101和103之間路由的消息可以通過一個或多個其它中間節點。
聯盟基礎結構100中的節點(包括其它中間節點)可包括對應的會合協議棧。例如，節點101、102和103分別包括對應的會合協議棧141、142和143。協議棧141、142和143的每一個包括一應用層(例如，應用層121、122和123)以及其它較低層(例如，對應的其它較低層131、132和133)。會合協議棧中的每一層負責涉及將資源請求與對應的資源會合的不同功能。
例如，其它較低層可包括信道層、路由層和功能層。一般而言，信道層負責將消息(例如使用WS可靠消息通信(WS-ReliableMessaging)和簡單對象訪問協議(「SOAP」)從一個端點可靠地傳輸到另一端點(例如，從節點101傳輸到節點103)。信道層也負責處理傳入和傳出的可靠消息通信報頭和維護涉及可靠消息通信會話的狀態。
一般而言，路由層負責計算朝向目的地的下一中繼段。路由層也負責處理傳入和傳出的尋址和路由消息報頭和維護路由狀態。一般而言，功能層負責發出和處理諸如加入和離開請求、查驗、更新和其它消息等會合協議消息，以及對這些消息的響應的生成。功能層處理來自路由層的請求消息，並且如果有任何對應的響應消息，使用路由層將其發送回始發節點。功能層也起動請求消息，並使用路由層來傳送請求消息。
一般而言，應用層處理從功能層傳送的非會合協議專用數據(即，應用消息)。功能層可訪問來自應用層的應用程式數據，並獲得應用數據並將其放置在會合協議消息中(例如，查驗和更新)。即，功能層可使應用程式數據在會合協議消息上捎帶確認，並可使應用數據被傳回到接收會合協議節點中的應用層。在某些實施例中，應用數據用於標識資源和資源興趣。由此，應用層可包括處理從其它較低層接收到和發往其它較低層的數據的應用專用邏輯和狀態，用於標識資源和資源興趣。
聯盟機制節點可使用各種不同的機制來聯盟。第一種聯盟機制包括對等節點將信息轉發到所有其它對等節點。當節點要加入一聯盟基礎結構時，該節點利用諸如WS發現(WS-Discovery)等廣播/組播發現協議來通告其存在，並發出一廣播/組播查找來檢測其它節點。該節點然後與已經存在於網絡上的其它節點建立簡單的轉發夥伴關係，並接受與新加入的節點的新夥伴關係。之後，該節點只需將所有的應用專用消息轉發到所有其夥伴節點。
第二種聯盟機制包括對等節點將應用專用消息最有效地發送到其目的地。當新節點要加入聯盟基礎結構時，該新節點利用諸如WS發現等廣播/組播發現協議來通告其存在，並發出一廣播/組播查找以檢測作為該聯盟基礎結構的一部分的其它節點。在檢測到另一節點之後，該新節點與該另一節點建立夥伴關係。從所建立的夥伴關係，該新節點獲知已經參與到聯盟基礎結構中的其它節點的存在。它然後與這些新獲知的節點建立夥伴關係，並接受任何新傳入的夥伴關係請求。
節點的到達/離開和對某些應用專用消息中感興趣的註冊都通過聯盟基礎結構來洪泛，導致每一節點具有關於其它夥伴節點以及對應用專用消息感興趣的註冊的全局知識。有了這一全局知識，任何節點可向已表達了對應用專用消息的興趣的節點直接發送應用專用消息。
第三種聯盟機制包括對等節點將所有應用專用消息間接轉發到其一個或多個目的地。在第三種機制中，向節點分配標識符(ID)，例如128位或160位ID。負責維護對給定應用專用消息感興趣的註冊的節點可被確定為其ID最接近於通過將應用專用消息的目的地身份(例如，URI)映射(例如，散列)到該128位或160位ID空間而獲得的節點。
在該第三種機制中，節點到達和離開在整個組織上洪泛。另一方面，對某些應用專用消息感興趣的註冊被轉發到被認為是負責這一註冊信息的節點。對於可伸縮性、負載平衡和容錯，接受對某些應用專用消息感興趣的註冊節點能夠可靠地將該註冊信息在其鄰域集中洪泛。指定節點的鄰域集可被確定為具有在指定節點的ID的任一側上的預定義範圍內的ID的節點集。
類似於第二種機制，新加入的節點利用諸如WS發現等廣播/組播發現協議來通告其存在，並發出一本地廣播/組播查找以檢測已經是該聯盟基礎結構的一部分的節點。該新節點與所發現的節點建立夥伴關係，並使用該夥伴關係來獲知參與該聯盟基礎結構的其它新節點的存在。該新節點然後與新發現的節點建立進一步的夥伴關係，並接受任何新的傳入夥伴關係請求。該新節點接受來自它所負責的夥伴的對某些應用層專用消息感興趣的傳入註冊，並可將它們在其鄰域集中洪泛。由此，消息一般可通過中間路由節點(例如，新加入的節點與其建立夥伴關係的節點或夥伴節點知道的節點)被轉發到其最終目的地。
響應於接收傳入的應用專用消息，新節點將該消息轉發到可能負責維護該消息中指定的目的地的註冊信息的夥伴節點。由此，當使用該第三種機制時，聯盟基礎結構中的每一節點具有關於所有其它節點的全局知識，但是註冊信息被有效地在節點之間劃分。應用專用消息僅通過可能負責維護對那些應用專用消息感興趣的註冊信息的夥伴節點被發送到其最終目的地。由此，通過僅轉發到具有關於所處理的消息的感興趣的註冊信息的全局消息的夥伴節點，實現了間接性。這與第一種機制相反，在第一種機制中，間接性是通過轉發到所有夥伴節點來實現的。
第四種聯盟機制包括對等節點將消息路由到其它對等節點。該第四種機制至少在節點到達/離開和對某些應用專用消息感興趣的註冊都被路由而非被洪泛的方面與第三種機制不同。路由協議被設計成確保應用專用消息和表達對那些應用專用消息的興趣的註冊消息之間的會合。
圖2示出了便於將請求直接路由到夥伴的計算機體系結構200的一個示例。計算機體系結構200描述了不同類型的計算機系統和設備，它們可能在參與聯盟基礎結構的多個本地發現範圍內分布。
工作站233可包括已註冊的PnP提供者實例。為向其夥伴通知該PnP提供者實例的存在，工作站233通過聯盟基礎結構路由註冊請求201。註冊請求201最初被轉發到膝上型計算機231，膝上型計算機231進而將註冊請求201轉發到消息代理程序237，消息代理程序237進而將註冊請求201轉發到消息網關241。消息網關241將註冊信息註冊請求201保存在其資料庫中，並向工作站233返回成功消息204。
隨後，另一已註冊提供者實例(這次是運行服務的實例)在工作站233中活躍起來。這一次，該節點知道消息網關241負責註冊，並將註冊請求205直接轉發到消息網關241。消息網關241將註冊信息註冊請求205保存在其資料庫中，並向工作站233返回成功消息206。
隨後，印表機236(例如，UPnP印表機)被通電，並發送通告207。伺服器234檢測到通告207，並將註冊請求208路由到消息代理程序237。消息代理程序237將註冊請求208轉發到消息網關241。消息網關241將註冊信息註冊請求208保存在其資料庫中，並向伺服器234返回成功消息210。
隨後，個人計算機242發出查找請求211以發現所有設備。由於個人計算機242不知道將查找請求211轉發到何處，因此它通過工作站243路由查找請求211。當註冊和查找請求被路由到同一目的地時，路由協議本質上確保了這兩個請求之間的會合，導致工作站243將查找請求211轉發到消息網關241。消息網關241查找由其維護的註冊信息，並將查找請求211轉發到工作站233和伺服器234。工作站233和伺服器234分別向個人計算機242發送響應消息214和216。
該第四種機制通過將請求路由(而非洪泛)到具有關於請求中指定的註冊的全局知識的節點(消息網關241)來工作。如下文將詳細描述的該第四種機制本質上確保路由可以在O(log N)個中繼段內實現，其中N是參與聯盟基礎結構的節點數。由於該第四種機制本質上劃分了節點夥伴關係和註冊信息，因此它能夠伸縮至非常大的網絡，甚至是網際網路。
儘管描述了多種聯盟機制，然而本領域的技術人員在閱讀了本說明書之後可以清楚，其它聯盟機制是可能的。
聯盟中節點之間的關係因此，聯盟由一組節點構成，這些節點在它們之間協調以形成其中可以系統地且有效地散布和定位信息的動態且可伸縮網絡。節點使用一種二元關係被組織成已排序列表來參與聯盟，該二元關係是自反的、反對稱的、傳遞的、總的、且在節點身份的域上定義的。已排序列表的兩端被連接，由此形成一個環。因此，列表中的每一節點可將其本身視為處於該已排序列表的中間(作為使用模運算的結果)。此外，該列表是雙向連結的，使得任何節點可在任何方向上遍歷該列表。
每一聯盟節點可被分配一個ID(例如，由具有重複檢測的隨機數生成器)，該ID來自0和某一固定上限的一組固定的ID。由此，固定上限的ID加1將導致ID 0(即，從鍊表的末端移回到鍊表的始端)。另外，定義了從節點身份的值域到節點本身的1∶1映射函數。
圖3描述了示例性鍊表304和對應的環306。給定這一環，可定義以下函數RouteNumerically(V，Msg)給定來自節點身份的值域的值V和消息「Msg」，將該消息傳遞到其身份可使用映射函數被映射到V的節點X。
Neighborhood(X，S)鄰域(Neighborhood)是基數等於S的節點X的任意側上的一組節點。
當聯盟中的每一節點具有關於環的全局知識時，通過將Msg直接發送到節點X實現RouteNumerically(V，Msg)，該節點X的身份可通過向V應用映射函數來獲得。或者，當節點具有關於其它節點(例如，僅直接相鄰的節點)的有限知識時，通過沿環將消息轉發到相繼的節點直到它到達目的地節點X來實現RouteNumerically(V，Msg)。
作為替代(且有利地)，節點可儲存關於環的足夠知識，來執行分布式二分搜索(而無需具有全局知識或實現直接相鄰節點之間的路由)。環知識的量是可配置的，使得維護環知識對於每一節點有足夠小的影響，但允許從減少路由中繼段數所得的提高的路由性能。
如上所述，可使用在足夠大的一組有界自然數上定義的「＜」(小於)關係來分配ID，這意味著其範圍是在0和某一固定值之間的一組有窮的數字上，包括0和該固定值。由此，參與聯盟的每一節點被分配位於0和某一適當選擇的上界之間(0和該上界包括在內)的自然數。該範圍不必是緊湊的，在分配給節點的數字之問可以有間隙。分配給節點的數字擔當節點在環中的身份。映射函數通過將落入兩個節點身份之間的數字映射到其身份在數字上最接近於該數字的節點，解決了數字空間之間的間隙。
該方法具有若干優點。通過向每一節點分配均勻分布的數字，更可能使得環的所有分段都是均勻地填充的。此外，可以使用模運算來有效地完成後繼、前導和鄰域計算。
在某些實施例中，向聯盟節點分配來自一ID空間內的ID，該ID空間足夠大，使得向兩個節點分配同一ID的機會是極其不可能的(例如，當使用隨機數生成時)。例如，可向一個節點分配在0到bn-1之間的ID，其中b等於例如8或16，而n等於例如128位或160位的等效位數。因此，可向節點分配例如來自0到1640-1(或約為1.461502E48)範圍內的ID。0到1640的範圍可提供例如足夠的ID數以向網際網路上的每一節點分配唯一的ID。
由此，聯盟中的每一節點可具有一ID，它是在0到bn-1的範圍內均勻分布的數字值；以及一路由表，它由以下各項構成(所有的運算都是模bn來完成的)後繼節點(s)；前導節點(p)；鄰域節點(pk，...，p1，p，s，s1，...，sj)，使得sj.s.id＞(id+u/2)，j≥v/2-1，且pk.p.id＜(id-u/2)，且k≥v/2-1；以及路由節點(r-(n-1)，...，r-1，r1，...，rn-1)，使得r±i＝RouteNumerically(id±bi，Msg)。其中，b是數基，n是用位數來標識的欄位大小，u是鄰域範圍，v是鄰域大小，且運算是模bn來執行的。對於好的路由效率和容錯，u和v的值可以是u＝b且v≥max(log2(N)，4)，其中N是物理地參與該聯盟的節點的總數。N可以從其長度大於或等於b的環分段上存在的節點數中估算，例如，當存在I的均勻分布時。b和n的典型值是b＝8或16，而n＝128位或160位的等效位數。
因此，路由節點可以形成跨越環的對數索引。取決於節點在環上的位置，精確的對數索引是可能的，例如，當在id±b1的集合中的每一數字上有一現有節點時，其中i＝(1，2，...(n-1))。然而，情況可以是在該集合中的每一數字上沒有現有節點。在這些情況下，可選擇最接近於id±bi的節點作為路由節點。所得的對數索引是不精確的，且對於集合中的某些數字可能缺少唯一的路由節點。
再次參考圖3，圖3示出了聯盟基礎結構中節點之間已排序列表304和對應的環306形式的二元關係的一個示例。已排序列表304的ID空間在0到28-1(或255)的範圍之內。即，b＝2且n＝8。由此，圖3所描述的節點被分配範圍從0到255的ID。已排序列表304使用了一種二元關係，該二元關係是自反的、反對稱的、傳導的、總的、且在節點身份的域上定義的。已排序列表304的兩端被連接，由此形成了環306。這使得圖3中的每一節點可能將其自身視為在已排序列表304的中間。已排序列表304是被雙向連結的，使得任一節點可以在任何方向上遍歷已排序列表304。用於遍歷已排序列表304(或環306)的運算是模28來執行的。由此，255(或已排序列表304的末端)+1＝0(或已排序列表304的始端)。
該路由表指出ID 64的後繼節點是ID 76(從ID 64開始順時針第一個ID)。例如，當新節點(例如，具有ID 71)加入或現有節點(例如，ID 76)離開聯盟基礎結構時，後繼節點可以改變。同樣，該路由表指出，ID 64的前導節點是ID 50(從ID 64開始逆時針第一個ID)。例如，當新節點(例如，具有ID 59)加入或現有節點(例如，ID 50)離開聯盟基礎結構時，前導節點可以改變。
該路由表還指出，ID 64的一組鄰域節點具有ID 83、76、50和46。一組鄰域節點可以是處於ID 64的指定範圍(即，鄰域範圍u)之內的指定數量的節點(即，鄰域大小v)。可能能夠使用各種不同的鄰域大小和鄰域範圍，諸如V＝4且U＝10，來標識該組鄰域節點。例如，當節點加入或離開聯盟基礎結構或當指定的節點數或指定範圍改變時，鄰域集合可以改變。
該路由表還指出，ID 64可以路由到具有ID 200、2、30、46、50、64、64、64、64、76、83、98、135和200的節點。該列表是通過標識id±2i的集合中最接近於每一數字的節點來生成的，其中i＝(1，2，3，4，5，6，7)。即，b＝2且n＝8。例如，具有ID 76的節點可以通過計算最接近於64+23，即72的節點來標識。
節點可將消息(例如，對資源的訪問請求)直接路由到前導節點、後繼節點、一組鄰域節點中的任一節點、或任一路由節點。在某些實施例中，節點實現一數字路由函數來路由消息。由此，RouteNumerically(V，Msg)可以在節點X處實現以將Msg傳送到聯盟中其ID在數字上最接近於V的節點Y，並將節點Y的ID返回給節點X。例如，具有ID 64的節點可實現RouteNumerically(243，Msg)以使消息被路由到具有ID 250的節點。然而，由於ID 250不是ID 64的路由節點，因此ID 64可將該消息路由至ID 2(最接近於243的路由節點)。具有ID 2的節點進而可實現RouteNumerically(243，Msg)以使消息被路由(直接或通過更多的中間節點)到具有ID 250的節點。由此，情況可以是遞歸地調用RouteNumerically函數，其中每一調用將消息路由到更接近於目的地之處。
有利的是，本發明的其它實施例便於基於一個或多個鄰近性類別(例如，地理邊界、路由特徵(例如，IP路由中繼段)、管理域、組織邊界等)中的多個鄰近性準則將環劃分成環的環或環的樹。應當理解，使用同一類型的鄰近性準則，環可以被劃分一次以上。例如，環可以基於陸地鄰近性準則和國家鄰近性準則(地理邊界鄰近性準則)來劃分。
由於ID可在ID空間中均勻地分布(隨機數生成的結果)，環形ID空間的任一給定分段很有可能包含屬於不同鄰近性類的節點，只要那些類具有近似相同的基數。這一概率在有足夠數量的節點時進一步增長以獲取有意義的統計行為。
由此，任一給定節點的鄰域節點通常是從鄰近性的觀點較好地散布的。由於所發布的應用程式狀態可以在鄰域節點之間重複，因此所發布的信息可以與從鄰近性觀點一樣好地散布。
圖4示出了便於鄰近路由的環的環400。環401可以被視為主環或根環，並包含環402、403和404的每一個中的所有節點，環402、403和404的每一個包含來自環401的節點的一個子集，環401基於一指定的鄰近性準則來劃分。例如，環401可以基於地理位置來劃分，其中環402包含北美洲的節點，環403包含歐洲的節點，環404包含亞洲的節點。
在包含65,536(216)個ID的數字空間中，將消息從具有ID 5,345的北美洲節點路由到具有ID 23,345的亞洲節點可包括在環402內路由該消息，直到標識了亞洲節點的一個相鄰節點。該相鄰節點然後可將該消息路由到亞洲節點。由此，在北美洲節點和亞洲節點之間做出單個中繼段(與多個中繼段相反)。因此，路由是以資源有效的方式來執行的。
圖5示出了便於鄰近路由的一個示例性由鄰近性導出的環的分區樹500。如圖所示，環的分區樹500包括多個環。每一個環表示已排序鍊表的一個分區。每一個環包括具有已排序鍊表中的ID的多個節點。然而，為清楚起見，由於潛在節點的個數，節點未在環上明確地描述(例如，分區樹500的ID空間可以是b＝16且n＝40)。
在分區樹500內，基於準則571(第一管理域邊界準則)，根環501被劃分成多個子環，包括子環511、512、513和514。例如，DNS名的每一分量可被認為是一種鄰近性準則，它們之中的局部順序是根據其在DNS名中從左讀到右的出現順序來導出的。因此，基於準則581(第二管理域邊界準則)，子環511可被進一步劃分成多個子環，包括子環521、522和523。
基於準則572(地理邊界準則)，子環522可被進一步劃分成多個子環，包括子環531、532和533。可按照大陸、國家、郵政編碼等對基於位置的鄰近性準則進行局部排序。郵政編碼本身是分層地組織的，意味著它們可被視為進一步導出鄰近性準則的局部排序的子列表。
基於準則573(第一組織邊界準則)，子環531可以被進一步劃分成多個子環，包括子環541、542、543和544。鄰近性準則的局部排序列表可以按照給定公司是如何在組織上結構化的來導出，諸如分公司、部門和產品組。因此，基於準則583(第二組織邊界準則)，子環543可以被進一步劃分成多個子環，包括子環551和552。
在分區樹500內，每一節點具有單個ID，並沿著從根到葉子的對應分區路徑參與各環。例如，參與子環552的每一節點也參與子環543、531、522、511和根501。路由到目的地節點(ID)可以通過如下實現RouteProximally函數來完成RouteProximally(V，Msg，P)給定來自節點身份域的值V和消息「Msg」，將該消息傳送到被鄰近性準則P認為是等效的節點中其身份可以被映射到V的節點Y。
由此，路由可以如下完成在給定環內漸進地移至更接近於目的地節點，直到如從目的地節點位於當前節點及其後繼或前導節點之間的條件中所確定的不能通過在該環內路由來做出更多前進。在這一點上，當前節點通過它所參與的下一更大的環中的夥伴節點開始路由。通過沿朝向根節點的分區路徑攀爬來漸進地移向目的地節點的這一過程在所請求的鄰近環境內到達與目的地節點最接近的節點時終止，如最初由RouteProximally調用所指定的。
路由中繼段可以保留在始發該請求的節點的鄰近鄰域中，直到目的地節點位於該鄰域中之外而在該鄰域中不能做出更多的前進。在這一點上，放鬆鄰近性準則，以增加鄰近鄰域的大小來做出更多前進。重複該過程，直到足夠地擴展了鄰近鄰域以包括目的地節點(ID)。在鄰近鄰域準則的每一次連續的放鬆之後做出的路由中繼段可以是鄰近空間中可能更大的跳躍，同時在數字空間中做出與前一中繼段相比相應較小的跳躍。由此，在到達目的地之前，僅做出絕對需要的數量的這些(環間)中繼段。
情況可以是避免某些中繼段來查找消息，因為當發布的應用程式數據在目的地節點的鄰域節點之間重複時，該數據沿分區樹向下重複。
為實現鄰近路由，每一聯盟節點維護對它作為成員參與的所有環中其後繼節點和前導節點(類似於單個環的後繼節點和前導節點)，即鄰近前導節點、鄰近後繼節點和鄰近鄰域的引用。為使路由有效，節點也可維護對最接近於在環的任一半上的指數增長距離的作為路由夥伴的其它節點(類似於單個環的路由節點)的引用。在某些實施例中，位於一對連續的後繼節點或前導節點之間的路由夥伴節點參與同一較低的環，該環由當前節點和數字上分別最接近於後繼節點或前導節點對的節點共享。由此，僅當絕對需要做出更多的前進時，路由使用放鬆的鄰近性準則(即，轉移到更高的環)跳向朝向目的地節點的轉移。因此，消息可以與對應的聯盟節點有效地會合。
在某些實施例中，節點實現一鄰近路由函數以基於等效的準則關係來路由消息。由此，給定數字V和消息「Msg」，節點可實現RouteProximally(V，Msg，P)以將消息傳送到被鄰近性準則P認為是等效的節點中其身份可被映射到V的節點Y。鄰近性準則P標識了分區樹中最低的環，該環是被它認為鄰近性上等效的所有節點的公共祖先。它可被表示為通過串接沿根環到由其標識的環的路徑找到的鄰近性準則而獲得的串，用路徑分隔符「/」來分隔。例如，標識子環542的鄰近性準則可以被表示為「Proximity/.COM/Corp2/LocationA/Div2」。分區樹500中的每一個環可以例如通過用基於SHA的算法來散列其表示串而被分配唯一的數字。如果保留數字0用於根環，則可以推導出RouteNumerically(V，Msg)≡RouteProximally(V，Msg，0)。
例如，子環544中的節點可以實現RouteProximally來標識子環531中更接近的節點(例如，對於子環513中的節點)。進而，子環531可實現RouteProximally來標識子環522中更接近的節點。同樣，子環522可實現RouteProximally來標識子環511中更接近的節點。類似地，子環511可實現RouteProximally來標識子環501中更接近的節點。由此，情況可以是遞歸地調用RouteProximally函數，每一次調用將消息路由到更接近於目的地之處。
由此，當考慮鄰近性準則時，到最終目的地的路徑上的路由中繼段可以保留在始發請求的節點的附近，同時在數字空間中在始發節點和目的地節點之間做出顯著的前進，直到到達目的地節點或在所選擇的鄰近性準則下不能做出更多的前進，此時，將準則放鬆到剛好足夠以做出朝向目的地的更多前進。例如，可足夠放鬆鄰近性準則以使消息能夠從環531向上路由到522等等。
使用上述鄰近性方法，可能將發布的信息限制到給定的環。例如，組織可能希望確保組織專用信息對於其信任域之外的實體是不可用的，這些實體或者(1)隱含地以對其域之外的節點的鄰域複製的形式，或者(2)明確地以對這一信息的服務查找請求的形式。第一方面是通過僅在指定環內目標ID鄰近的節點之間複製發布的信息來滿足的。由於由一個節點始發的所有消息都是通過連續地攀爬它所屬的環到根環來路由的，因此在一個組織內始發的所有查找請求很有可能能夠定位限定到它的所發布信息，由此隱含地滿足了第二方面。
同樣，與節點不同，組織自動地與其信任域之外的節點聯盟。例如，當在顧客的前提下訪問的銷售人員將他/她的膝上型計算機連接到網絡時，可發生這一情況。理想的是，屬於該銷售人員的膝上型計算機希望定位在其主域中發布的信息和/或與其主域中在其最低的較佳鄰近性環中開始的節點聯盟。通常準許與顧客域中的節點聯盟。假定這一情形需要定位主域中的種子節點的能力。這一種子節點可用於定位主域中發布的信息、加入主聯盟、以及選擇性地導入和導出跨域所發布的信息。種子節點有時候也被稱為消息網關。
在其它實施例中，實體發布對根環中種子節點的引用。種子節點可以在與該環相關聯的唯一數字(諸如通過散列其表示串而獲得的數字)(作為目標ID)處發布。種子節點信息還可以由各環中的節點按需高速緩存，這些節點在通往根環中的對應目標ID的路徑上。這一按需高速緩存提供了改進的性能，以及當相當頻繁地查找半靜態信息可能出現的熱點的減少。種子節點信息也可以通過諸如DNS等其它手段來獲得。
為向限定的發布信息提供容錯，每一節點可維護它所參與的所有環中的一組鄰域節點。給定以上內容，由節點維護的狀態可被總結如下●ID，它是在0到bn-1的範圍內均勻分布的數字值。
●路由表，它由下列各項構成(所有運算都是模bn來完成的)○節點所參與的對於每一個環，如環d■後繼節點(sd)■前導節點(pd)■鄰域節點(Pkd，...，P1d，pd，sd，s1d，...，sjd)，使得sjd.sd.id＞(id+u/2)，j≥v/2-1，Pkd.Pd.id＜(id-u/2)，且k≥v/2-1。
○路由節點(r-(n-1)，...，r-1，r1，...，rn-1)，使得r±i＝RouteProximally(id±bi，updateMsg，d)，使得在適當時sd≤id+bi≤sd+1或Pd+1≤id-bi≤pd。
其中b是數基，n是按位數表示的欄位大小，u是鄰域範圍，v是鄰域大小。
注意，由環「d」中的給定節點維護的鄰域節點的子集可以再次作為給定節點也參與的子環「d+1」中的鄰域節點出現。由此，可導出給定節點在它所參與的所有D環中維護的鄰域節點的總數的上界，為D*max(u，v)/2。這考慮僅保持對給定節點的一個引用，且最壞情況的上界是用於平衡樹。
應當注意，當環被劃分成多個對應的兄弟子環時，可例如通過起別名，準許指定的節點同時參與多個對應兄弟子環中一個以上子環。起別名可以被實現以將例如來自不同子環的不同狀態與給定節點相關聯。由此，儘管對給定節點的別名具有相同的ID，每一別名可具有與其相關聯的不同狀態。起別名允許指定的節點參與具有不同鄰近性準則的多個環，這些鄰近性準則不必要是更特定鄰近性準則的公共祖先。即，指定的節點可參與鄰近性樹的多個分支。
例如，雙NIC(有線和無線)膝上型計算機可被認為是在鄰近性上等效於與膝上型計算機通向同一LAN的其它無線和有線節點。但是，這兩個不同的鄰近性準則可被建模為子準則，這些子準則僅在應用了諸如基於組織成員資格的準則等不同的更高優先級鄰近性準則之後才適用。當膝上型計算機屬於同一組織時，兩個子環中表示(1)有線LAN段中的成員資格，以及2)無線LAN段中的成員資格的起別名的節點合併成環中表示該膝上型計算機所屬的組織的單個節點。應當理解，RouteProximally如所預期地工作，而不會對起別名的存在有任何修改。
每一鄰近性環可以依照(可能不同的)環參數來配置。環參數可用於定義鄰域(例如，環參數可表示鄰域範圍、鄰域大小、查驗消息和離開消息定時以及查驗和離開消息的的分布模式)、指示特定的聯盟機制(例如，來自先前所描述的上述第一到第四聯盟機制，或來自其它聯盟機制)、或定義同一鄰近環中的路由夥伴之間的通信細節。某些環參數可以更一般，從而適用於多個不同的聯盟機制，而其它環參數是更具體的，並適用於特定類型的聯盟機制。
用於配置較高級鄰近環的環參數在某些實施例中可以由較低級鄰近環繼承，例如，環543可以繼承環531的某些環參數(環531進而從環522繼承，等等)。由此，與環531相關聯的鄰域大小和鄰域範圍也與環541相關聯。
然而，繼承的環參數可以被更改，和/或鄰近環可以依照不同的環參數來個別地配置。例如，環511可以用於包含大量節點的管理域，由此上述第四種聯盟機制更適用於環511。另一方面，環521可以用於具有相對較少數量的節點的小企業環境，由此上述第二種聯盟機制更適用於環521。由此，與環521相關聯的環參數可以被設為(或者繼承的參數可以被改為)與關聯於環511的環參數不同的值。例如，指示特定類型的聯盟機制的環參數可以在環511和521之間不同。定義鄰域的類似參數可以在環511和521之間不同。此外，環521可以依照對上述第二種聯盟機制專用的特定參數來配置，而環511另外依照對上述第四種聯盟機制專用的特定參數來配置。
因此，鄰近環可以基於該鄰近環中節點的特徵(例如，號碼、包括的資源等)來靈活地配置。例如，管理員可使用一配置過程(例如，通過用戶界面)為鄰近環選擇環參數。配置過程可便於鄰近環之間的繼承關係的配置，以及個別鄰近環的配置，諸如用於覆蓋以其它方式繼承的環參數。
圖8示出了劃分聯盟基礎結構的節點的方法800的示例流程圖。方法800將相對於圖5中的分區樹500的環來描述。方法800包括訪問包含被分配給聯盟基礎結構中的節點的節點ID的已排序鍊表的動作(動作801)。例如，可訪問由環501表示的已排序鍊表。已排序鍊表的節點ID(在環501上描述的節點)可表示聯盟基礎結構(例如，聯盟基礎結構100)中的節點。
方法800包括訪問表示用於劃分已排序鍊表的多個不同鄰近性準則的鄰近性類別的動作(動作802)。例如，可訪問表示域邊界561、地理邊界562和組織邊界563的鄰近性準則。然而，在所訪問的鄰近性準則中也可表示諸如信任域邊界等其它鄰近性準則。鄰近性類別可包括先前所創建的鄰近性準則的局部排序的列表。環可以基於該鄰近性準則的局部排序的列表來劃分。
方法800包括基於第一鄰近性準則將已排序鍊表劃分成一個或多個第一子列表的動作(動作803)，這一個或多個第一子列表的每一個包含來自己排序鍊表的節點ID的至少一個子集。例如，環501可以基於準則571被劃分成子環511、512、513和514。子環511、512、513和514的每一個可包含來自環501的節點ID的一個不同的子集。
方法800包括基於第二鄰近性準則將從一個或多個第一子列表中選擇的第一子列表劃分成一個或多個第二子列表的動作(動作804)，這一個或多個第二子列表的每一個包含第一子列表中包含的節點ID的至少一個子集。例如，子環511可以基於準則581被劃分成子環521、522和523。子環521、522和523的每一個可包含來自子環511的節點ID的一個不同的子集。
圖9示出了填充節點的路由表的方法900的示例流程圖。方法900將相對於圖3中的已排序鍊表304和環306來描述。方法900包括將一前導節點插入到路由表中的動作(動作901)，該前導節點相對於當前節點在已排序鍊表的第一方向上在該當前節點之前。例如，具有ID 50的節點可作為具有ID 64的節點(當前節點)的前導節點被插入到路由表中。在順時針方向321上移動(從已排序鍊表304的一端A移動向已排序鍊表304的一端B移動)，具有ID 50的節點在具有ID 64的節點之前。插入前導節點可以建立當前節點與前導節點之間的對稱夥伴關係，使得當前節點是前導節點的夥伴，而前導節點是當前節點的夥伴。
方法900包括將一後繼節點插入到路由表中的動作(動作902)，該後繼節點相對於當前節點在已排序鍊表的第一方向上在當前節點之後。例如，具有ID 76的節點可作為具有ID 64的節點(當前節點)的後繼節點被插入到路由表中。在逆時針方向322上移動，具有ID 76的節點在具有ID 64的節點之後。插入後繼節點可建立當前節點和後繼節點之間的對稱夥伴關係，使得當前節點是後繼節點的夥伴，後繼節點是當前節點的夥伴。
方法900包括將適當的鄰域節點插入到路由表中的動作(動作903)，該鄰域節點是基於鄰域範圍和鄰域大小在第一方向和相反的第二方向上從已排序鍊表中標識的。例如，具有ID 83、76、50和46的節點可作為具有ID 64(當前節點)的鄰域節點被插入到路由表中。基於鄰域範圍20和鄰域大小4，具有ID 83和76的節點可在順時針方向321上標識而具有ID 50和46的節點可在逆時針方向322上標識(從已排序鍊表304的一端B向已排序鍊表304的一端A移動)。在某些環境中，可能無法標識適當的鄰域節點。插入鄰域節點可建立當前節點和鄰域節點的對稱夥伴關係，使得當前節點是鄰域節點的夥伴，鄰域節點是當前節點的夥伴。
方法900包括將適當的路由節點插入到路由表中的動作(動作904)，該路由節點是基於聯盟基礎結構的ID空間的數基和欄位大小在第一和第二方向上從已排序鍊表中標識的，該路由節點表示已排序鍊表在第一和第二方向上的對數索引。例如，具有ID 200、2、30、46、50、64、64、64、64、64、76、83、98、135和200的節點可作為具有ID 64的節點的路由節點被插入到路由表中。基於數基2和欄位大小8，具有ID 64、64、76、83、98、135和200的節點可在方向321上標識，而具有ID 64、64、50、46、30、2和200的節點可在方向322上標識。如在環306內所描繪的，路由節點表示已排序鍊表304在順時針方向321和逆時針方向322上的對數索引。插入路由節點可建立當前節點和路由節點之間的對稱夥伴關係，使得當前節點是路由節點的夥伴，路由節點是當前節點的夥伴。
圖7示出了考慮鄰近性準則來填充節點路由表的方法700的示例流程圖。方法700將相對於圖5中的環來描述。方法700包括對當前節點所參與的每一分層劃分的路由環將一前導節點插入到路由表中的動作(動作701)。每一前導節點在當前節點所參與的每一分層劃分的路由環中在第一方向(例如，順時針)上在當前節點之前。分層劃分的路由環依照對應的鄰近性準則來劃分，並包含雙向連結的列表的至少一個子集(可能是整個雙向連結的列表)。例如，指定的節點可以參與根環501和子環511、522、523、531和542。由此，從環501和子環511、522、523、531和542的每一個中對指定的節點選擇前導節點。
方法700包括對當前節點所參與的每一分層劃分的路由環將一後繼節點插入到路由表中的動作(動作702)。每一後繼節點在當前節點所參與的每一分層劃分的路由環中在第一方向上在當前節點之後。例如，從環501和子環511、522、523、531和542的每一個中對指定的節點選擇後繼節點。
方法700包括對當前節點所參與的每一分層劃分的路由環將適當的鄰域節點插入到路由表中的動作(動作703)。鄰域節點可以基於鄰域範圍和鄰域大小在第一方向(例如，順時針)和相反的第二方向(例如，逆時針)上從當前節點所參與的分層劃分的路由環中標識。例如，可以從環501和子環511、522、523、531和542的每一個中對指定節點標識鄰域節點。
方法700包括對當前節點所參與的每一分層劃分的路由環將適當的路由節點插入到路由表中的動作(動作704)。例如，可以從環501和子環511、522、523、531和542的每一個中對指定的節點標識路由節點。
在某些實施例中，對節點Y所參與的除葉子環(或在使用別名的實施例中的葉子環)之外的每一鄰近性環插入適當的路由節點。適當的路由節點可基於以下表達式來插入如果Y.sd.id＜Y.id+bi＜Y.sd+1.id為真，則使用環d；或者如果Y.pd.id＜Y.id-bi＜Y.pd+1.id為真，則使用環d。
如果在前一步驟中尚未標識環，則使用領導環(例如，環501)作為環d。現在，環d是其中節點Y應當查找最接近於z的路由夥伴的鄰近性環。
圖10示出了將消息朝向目的地節點路由的方法1000的示例流程圖。方法1000將相對於圖3中的已排序鍊表304和環306來描述。方法1000包括接收節點接收消息以及指示目的地的數字的動作(動作1001)。例如，具有ID 64的節點可接收指示目的地212的消息。
方法1000包括確定接收節點是在數字上比對應的前導節點離目的地更遠以及在數字上比對應的後繼節點離目的地更遠的至少一種的動作(動作1002)。例如，在方向322上，ID 64比ID 50離目的地212更遠，在方向321上，ID 64比ID 76離目的地212更遠。方法1000包括確定目的地不在對應於接收節點的鄰域節點集內的動作(動作1003)。例如，具有ID 64的節點可確定目的地212不在83、76、50和46的鄰域集內。
方法1000包括從對應於接收節點的路由表中標識中間節點的動作(動作1004)，該中間節點數字上比對應的路由表中的其它路由節點更接近於目的地。例如，具有ID 64的節點可將具有ID 200的路由節點標識為在數字上比其它路由節點更接近於目的地212。方法1000包括將消息發送到中間節點的動作(動作1005)。例如，具有ID 64的節點可將消息發送到具有ID 200的節點。
圖11示出了基於鄰近性準則將消息朝向目的地節點路由的方法1100的示例流程圖。方法1100將相對於圖4和圖5中的環來描述。方法1100包括接收節點接收消息以及指示目的地的數字以及鄰近性準則的動作(動作1101)。鄰近性準則定義了一個或多個節點類。接收節點接收作為基於鄰近性準則從一個或多個節點類中選擇的當前節點類的一部分的消息。例如，具有ID 172的節點可接收指示目的地201的消息以及指示目的地節點是由環401所表示的類的一部分的鄰近性準則。具有ID 172的節點可接收作為環404的一部分的消息。
方法1100包括確定在所選擇的節點類的節點中，接收節點是在數字上比對應的前導節點離目的地更遠以及在數字上比對應的後繼節點離目的地更遠中的至少一種的動作(動作1102)。例如，在環404內，具有ID 172的節點在順時針方向上比具有ID 174的節點離目的地201更遠，且在逆時針方向上比具有ID 153的節點離目的地201更遠。
方法1100包括對於由鄰近性準則定義的一個或多個節點類的任一個，確定目的地不在接收節點的鄰域節點集之內的動作(動作1103)。例如，具有ID 172的節點可確定目的地201不在環404或環401中對應的鄰域集內。
方法1100包括從接收節點的路由表中標識中間節點的動作(動作1104)，該中間節點在數字上比路由表中的其它路由節點更接近於目的地。例如，具有ID 172的節點可將具有ID 194的節點標識為在數字上比環404中的其它路由節點更接近於目的地201。方法1100包括將消息發送到中間節點的動作(動作1105)。例如，具有ID 172的節點可將接收到的消息發送到具有ID 194的節點。具有ID 172的節點可將接收到的消息發送到具有ID 194的節點，以遵從先前定義的鄰近性準則的局部排序列表。
節點194可以在環404內儘可能地接近於目的地201。由此，可以放鬆鄰近性到剛好足夠的程度，以使在下一路段中在環401內作出朝向目的地的進一步路由。即，路由從環404轉移到環401，因為在環404上不能做出朝向目的地的進一步前進。或者，情況可以是具有ID 201的節點在環401內在具有ID 194的節點的鄰域內，導致沒有進一步的路由。由此，在某些實施例中，放鬆鄰近性準則以到達下一較高的環足以引起進一步的路由。
然而，在其它實施例中，促使轉移到下一較高環的鄰近性準則的遞增放鬆繼續，直到可發生進一步的路由(或直到遇到根環)。即，在可做出進一步的路由前進之前發生到較高環的多次轉移。例如，現在參考圖5，當在環531上不能做出進一步的路由前進時，可足夠放鬆鄰近性準則以轉移到環511或甚至轉移到根環501。
圖6及以下討論旨在提供對適於在其中實現本發明的計算環境的簡要概括描述。儘管並非所需，但本發明將在諸如由計算機系統執行的程序模塊等計算機可執行指令的一般上下文中描述。一般而言，程序模塊包括例程、程序、對象、組件、數據結構等等，它們執行特定的任務或實現特定的抽象數據類型。計算機可執行指令、相關聯的數據結構以及程序模塊表示了用於執行此處所揭示的方法的步驟的程序代碼手段的示例。
參考圖6，用於實現本發明的示例系統包括計算機系統620形式的通用計算設備，包括處理單元621、系統存儲器622以及將包括系統存儲器622的各類系統組件耦合至處理單元621的系統總線623。處理單元621可以執行被設計成實現計算機系統620的特徵的計算機可執行指令，包括本發明的特徵。系統總線623可以是若干種總線結構類型的任一種，包括存儲器總線或存儲器控制器、外圍總線以及使用各類總線體系結構的局部總線。系統存儲器包括只讀存儲器(ROM)624和隨機存取存儲器(RAM)625。基本輸入/輸出系統(BIOS)626，包含如在啟動時協助在計算機620內的元件之間傳輸信息的基本例程，可儲存在ROM 624中。
計算機系統620也可包括用於對磁硬碟639進行讀寫的磁硬碟驅動器627、用於對可移動磁碟629進行讀寫的磁碟驅動器628以及用於對可移動光碟631，如CD-ROM或其它光介質進行讀寫的光碟驅動器630。磁硬碟驅動器627、磁碟驅動器628以及光碟驅動器630分別通過硬碟驅動器接口632、磁碟驅動器接口633和光碟驅動器接口634連接至系統總線623。驅動器及其相關的計算機可讀介質為計算機系統620提供了計算機可執行指令、數據結構、程序模塊和其它數據的非易失性存儲。儘管這裡描述的示例環境採用了磁硬碟639、可移動磁碟629以及可移動光碟631，然而也可以使用用於儲存數據的其它類型的計算機可讀介質，包括盒式磁帶、快閃記憶體卡、數字多功能盤、Bernoulli盒式磁碟、RAM、ROM等等。
包括一個或多個程序模塊的程序代碼裝置可儲存在硬碟639、磁碟629、光碟631、ROM 624或RAM 625中，包括作業系統635、一個或多個應用程式636、其它程序模塊637以及程序數據638。用戶可以通過鍵盤640、指點設備642或其它輸入設備(未示出)，如麥克風、操縱杆、遊戲墊、掃描儀等等向計算機系統620輸入命令和信息。這些和其它輸入設備可以通過耦合至系統總線623的輸入/輸出接口646連接到處理單元621。輸入/輸出接口646邏輯上表示各種各樣不同的接口中的任一種，諸如串行埠接口、PS/2接口、並行埠接口、通用串行總線(USB)接口、或電子與電器工程師協會(「IEEE」)1394接口(即，火線接口)、或甚至在邏輯上表示不同接口的組合。
監視器647或其它顯示設備也通過視頻接口648連接到系統總線623。揚聲器669或其它音頻輸出設備也通過音頻接口649連接到系統總線623。其它外圍輸出設備(未示出)，如印表機也可連接到計算機系統620。
計算機系統620可連接到網絡，諸如辦公室範圍或企業範圍計算機網絡、家庭網絡、內聯網和/或網際網路。計算機系統620可通過這類網絡與諸如遠程計算機系統、遠程應用程式和/或遠程資料庫等外部源交換數據。
計算機系統620包括網絡接口653，通過該接口，計算機系統620從外部源接收數據和/或將數據發送到外部源。如圖6所示，網絡接口653便於通過鏈路651與遠程計算機系統683交換數據。網絡接口653邏輯上可表示一個或多個軟體和/或硬體模塊，諸如網絡接口卡和對應的網絡驅動器接口規範(「NDIS」)棧。鏈路651表示網絡的一部分(例如，乙太網段)，而遠程計算機系統683表示網絡的節點。
同樣，計算機系統620包括輸入/輸出接口646，通過該接口，計算機系統620從外部源接收數據和/或將數據發送到外部源。輸入/輸出接口646通過鏈路659耦合至數據機654(例如，標準數據機、電纜數據機或數字用戶線(「DSL」)數據機)，通過鏈路659，計算機系統620從外部源接收數據和/或將數據發送到外部源。如圖6所示，輸入/輸出接口646和數據機654便於通過鏈路652與遠程計算機系統693交換數據。鏈路652表示網絡的一部分，而遠程計算機系統693表示網絡的節點。
儘管圖6表示了用於本發明的合適的操作環境，然而本發明的原理可用於在適當的修改下(如有必要)能夠實現本發明的原理的任一系統。圖6所示的環境僅是說明性的，並且決不表示其中可實現本發明的原理的各種各樣的環境中的即使一小部分。
依照本發明，節點、應用層和其它較低層、以及包括路由表和節點ID的相關聯的數據可被儲存並從與計算機系統620相關聯的任一計算機可讀介質中訪問。例如，這些模塊的各部分以及相關聯的程序數據的各部分可包括在作業系統635、應用程式636、程序模塊637和/或程序數據638中，以儲存在系統存儲器622中。
當諸如磁硬碟639等大容量存儲設備耦合至計算機系統620時，這些模塊和相關聯的程序數據也可被儲存在大容量存儲設備中。在聯網環境中，相對於計算機系統620所描述的程序模塊或其部分可被儲存在遠程存儲器存儲設備中，諸如與遠程計算機系統683和/或遠程計算機系統693相關聯的系統存儲器和/或大容量存儲設備。這些模塊的執行可如上所述地在分布式環境中執行。
本發明可以用其它具體形式來實施而不脫離其精神或本質特徵。所描述的實施例在各方面都被認為僅是說明性而非限制性的。因此，本發明的範圍由所附權利要求書而非以上說明書來標識。落入權利要求書的等效技術方案的意義和範圍之內的所有改變都包含在其範圍之內。
權利要求
1.在聯盟基礎結構中，一種用於將消息路由到目的地節點的方法，所述方法包括接收節點接收消息以及指示目的地的目的地標識符的動作，所述接收節點包括在被配置成用於雙向路由的節點環中；基於所述接收節點在所述節點環中的位置確定要接收所述消息的下一適當節點的動作，所述下一適當節點在數字上比所述接收節點的路由表中的其它路由節點更接近於所述目的地，所述路由表至少表示所述節點環中的其它節點的對數索引，所述路由表至少是基於用於生成標識符空間的數基來填充的，所述標識符空間用於生成所述聯盟基礎結構中的標識符，所述接收節點與所述接收節點的路由表中的節點具有對稱關係；以及將所述消息發送到下一適當組件的動作。
2.如權利要求1所述的方法，其特徵在於，確定要接收所述消息的下一適當節點的動作包括標識在數字上比所述接收節點的路由表中的其它路由節點更接近於所述目的地的中間節點的動作。
3.如權利要求2所述的方法，其特徵在於，標識中間節點的動作包括將所述中間節點標識為包括在所述接收節點的路由表中的節點的動作。
4.如權利要求1所述的方法，其特徵在於，確定要接收所述消息的下一適當節點的動作包括從所述接收節點先前向其發送消息的節點處接收狀態消息的動作。
5.如權利要求4所述的方法，其特徵在於，接收狀態消息的動作包括接收包含節點存在信息的狀態消息。
6.如權利要求4所述的方法，其特徵在於，接收狀態消息的動作包括接收促使所述接收節點標識一不同的下一適當組件的狀態消息。
7.如權利要求4所述的方法，其特徵在於，還包括從所接收的狀態消息中確定所接收的消息不應當再由所述接收節點進一步發送的動作。
8.如權利要求7所述的方法，其特徵在於，從所接收的狀態消息中確定所述消息不應當再被進一步發送的動作還包括從所接收的狀態消息中確定所述消息被傳送到至少一個目的地節點的動作。
9.如權利要求7所述的方法，其特徵在於，從所接收的狀態消息中確定所述消息不應當再被進一步發送的動作包括確定所述消息未被傳送到任何目的地節點的動作。
10.如權利要求1所述的方法，其特徵在於，還包括將涉及所接收的消息的狀態消息發送到向所述接收節點發送所述消息的節點的動作。
11.如權利要求10所述的方法，其特徵在於，發送涉及所接收消息的狀態消息的動作包括將先前接收的狀態消息發回將所接收的消息發送到所述接收節點的節點的動作。
12.如權利要求1所述的方法，其特徵在於，確定要接收所述消息的下一適當節點的動作包括將所述接收節點標識為所述下一適當節點的動作。
13.如權利要求12所述的方法，其特徵在於，將所述接收節點標識為所述下一適當節點的動作包括確定所述接收節點的標識符更接近地與所述目的地標識符匹配的動作。
14.如權利要求13所述的方法，其特徵在於，確定所述接收節點的標識符與更接近地與所述目的地標識符匹配的動作包括確定所述接收節點的標識符與所述目的地標識符完全匹配的動作。
15.如權利要求13所述的方法，其特徵在於，還包括將所接收的消息轉發到所述接收節點的直接相鄰節點的動作，所述直接相鄰節點在所述接收節點的當前環中。
16.如權利要求15所述的方法，其特徵在於，將所接收的消息轉發到所述接收節點的直接相鄰節點的動作包括確定所述目的地標識符落入所述接收節點和所述接收節點的直接前導相鄰節點之間的動作。
17.如權利要求15所述的方法，其特徵在於，將所接收的消息轉發到所述接收節點的直接相鄰節點的動作包括確定所述目的地標識符落入所述接收節點和所述接收節點的直接後繼相鄰節點之間的動作。
18.如權利要求15所述的方法，其特徵在於，還包括所述接收節點的直接相鄰節點將涉及所轉發的消息的狀態消息發回所述接收節點的動作。
19.如權利要求18所述的方法，其特徵在於，還包括所述接收節點的直接相鄰節點在所述狀態消息中包括節點存在信息的動作。
20.如權利要求18所述的方法，其特徵在於，所述接收節點的直接相鄰節點將涉及所轉發的消息的狀態消息發回所述接收節點的動作還包括由所述接收節點的直接相鄰節點發送至少包括對於所述接收節點被認為是所述消息的最佳下一適當節點的指示的狀態消息。
21.如權利要求18所述的方法，其特徵在於，所述接收節點的直接相鄰節點將涉及所轉發的消息的狀態消息發回所述接收節點的動作包括發送包括節點存在信息的狀態消息。
22.如權利要求18所述的方法，其特徵在於，所述接收節點的直接相鄰節點將涉及所轉發的消息的狀態消息發回所述接收節點的動作包括發送包括對於所接收的消息不應當再由所述接收節點進一步發送的指示的狀態消息。
23.如權利要求12所述的方法，其特徵在於，將所述接收節點標識為所述下一適當節點的動作包括所接收的消息促使將所述接收節點標識為所述下一適當節點的動作。
24.如權利要求1所述的方法，其特徵在於，將所述消息發送到下一適當組件的動作包括將所述消息發送到所述下一適當節點的動作。
25.如權利要求24所述的方法，其特徵在於，將所述消息發送到所述下一適當節點的動作包括所述接收節點在發送到所述下一適當節點的消息中包括額外的節點存在信息的動作。
26.如權利要求1所述的方法，其特徵在於，將所述消息發送到下一適當組件的動作包括所述接收節點擔當所述消息的最終目的地的動作。
27.如權利要求26所述的方法，其特徵在於，所述接收節點擔當所述消息的最終目的地的動作包括將所述消息傳送到與所述接收節點相關聯的應用組件的動作。
28.如權利要求26所述的方法，其特徵在於，還包括將與所接收的消息相關聯的狀態消息發回將所接收的消息發送到所述接收節點的節點的動作。
29.在包括已劃分的節點類的分層結構的聯盟基礎結構中，一種基於鄰近性準則將消息路由到目的地節點的方法，包括接收節點接收消息以及目的地標識符和鄰近性準則的動作，所述鄰近性準則定義節點類分層結構中的一個或多個節點類，所述接收節點是所述節點類分層結構中當前節點類的一部分，所述當前節點類是從所述節點類分層結構中的一個或多個節點類中選擇的；從所述接收節點的路由表中標識一適當的節點的動作，所述適當的節點在數字上比所述路由表中的其它路由節點更接近於所述目的地，而同時仍在由所述鄰近性準則定義的一個或多個節點類中，所述路由表至少表示由鄰近性準則定義的一個或多個節點類中的其它節點的對數索引，所述路由表是基於用於生成所述聯盟基礎結構的ID空間的數基來填充的；以及將所述消息發送到下一適當節點的動作。
30.如權利要求29所述的方法，其特徵在於，接收節點接收消息以及目的地標識符和鄰近性準則的動作包括接收節點訪問先前定義的鄰近性準則局部排序列表的動作。
31.如權利要求30所述的方法，其特徵在於，接收節點訪問先前定義的局部排序的鄰近性準則列表的動作包括接收先前定義的鄰近性準則局部排序列表的動作。
32.如權利要求29所述的方法，其特徵在於，將所述消息發送到下一適當節點的動作包括將所述消息發送到所述下一適當節點以遵從先前定義的鄰近性準則局部排序列表的動作。
33.在包括已劃分節點類的分層結構的聯盟基礎結構中，一種用於將消息路由到充足目的地節點的方法，所述方法包括接收節點接收消息以及目的地標識符和鄰近性準則的動作，所述鄰近性準則定義了所述節點類分層結構中一個或多個節點類中的最高節點類，所述接收節點是所述節點類分層結構中至少一個當前節點類的一部分，所述當前節點類是從所述節點類分層結構中的一個或多個節點類中選擇的；標識所述消息的充足目的地節點的動作，所述充足目的地節點是由所接收的鄰近性準則定義的最高節點類的成員，所述充足目的地節點在所述最高節點類的目的地標識符的鄰域內；以及將所述消息發送到所述充足目的地節點的動作。
34.如權利要求33所述的方法，其特徵在於，標識充足目的地節點的動作包括基於所述鄰近性準則至少從所述接收節點的路由表中標識充足目的地節點的動作。
35.如權利要求33所述的方法，其特徵在於，標識充足目的地節點的動作包括與所述接收節點相關聯的應用組件的應用邏輯標識充足目的地節點的動作。
36.如權利要求33所述的方法，其特徵在於，還包括限定所述充足目的地節點在所述最高節點類的目的地標識符的鄰域中的動作。
37.如權利要求36所述的方法，其特徵在於，限定所述充足目的地節點在所述最高節點類的目的地標識符的鄰域內的動作包括所述接收節點使用所述接收節點的路由表進一步限定所述充足目的地節點也在數字上最接近於所述最高節點類中的目的地標識符的動作。
38.如權利要求33所述的方法，其特徵在於，還包括限定所述充足目的地節點是所述接收節點的動作。
39.一種包括多個分層地劃分的節點類的系統，所述系統包括較高節點環，所述較高節點環中的每一節點具有指示已排序鍊表節點中的位置的節點標識符；第一較低節點環，所述第一較低節點環中的每一節點具有第一節點子列表中的節點標識符，所述第一節點子列表是從所述已排序鍊表中劃分的，使得所述第一較低環中的節點也是所述較高環中的節點，所述第一子列表是依照指示如何對節點環分類的鄰近性準則從所述已排序鍊表中劃分的，所述第一節點環被配置成允許路由的消息通信量在所述第一節點環內路由時繞過包括在所述鍊表中的至少某些節點；以及第二較低節點環，所述第二較低節點環中的每一節點具有第二不同的節點子列表中的節點標識符，所述第二節點子列表是從所述已排序鍊表中劃分的，使得所述第二較低環中的節點也是所述較高環中的節點，所述第二子列表是依照所述鄰近性準則從所述已排序鍊表中劃分的，使得所述第一較低環和所述第二較低環是相對於所述較高環的鄰近性準則等價地分類的，所述第二節點環被配置成允許路由的消息通信量在所述第二節點環內路由時繞過包括在所述第一節點環中的至少某些節點。
40.如權利要求39所述的系統，其特徵在於，所述消息通信量被限於所述較高節點環。
41.如權利要求39所述的系統，其特徵在於，所述消息通信量被限於所述第一較低節點環。
42.如權利要求39所述的系統，其特徵在於，所述消息通信量被限於所述第二較低節點環。
43.如權利要求39所述的系統，其特徵在於，配置所述系統，使得定向到所述較高節點環中的目的地節點的消息在所述消息的路由在所述較高節點環中繼續之前，在所述第一較低節點環中做出朝向所述目的地節點的儘可能多的前進。
44.如權利要求39所述的系統，其特徵在於，配置所述系統，使得定向到所述較高節點環中的目的地節點的消息在所述消息的路由在所述較高節點環中繼續之前，在所述第二較低節點環中做出朝向所述目的地節點的儘可能多的前進。
45.如權利要求39所述的系統，其特徵在於，配置所述系統，使得定向到所述較高節點環中的目的地節點的消息在所述消息在已表達等價節點類的目的地節點的鄰域內的節點處接收之後可被傳送到與所述目的地節點相關聯的應用組件。
46.如權利要求39所述的系統，其特徵在於，配置所述系統，使得所述較高節點環中的節點之間的路由關係是對稱的。
47.如權利要求39所述的系統，其特徵在於，配置所述系統，使得所述較高節點環中的節點之間的路由關係是雙向的。
48.如權利要求39所述的系統，其特徵在於，所述第一較低節點環中的每一節點具有第一節點子列表中的節點標識符包括所述第一較低節點環中的每一節點具有來自較高節點環的節點標識符。
49.如權利要求39所述的系統，其特徵在於，所述第二較低節點環中的每一節點具有第二節點子列表中的節點標識符包括所述第二較低節點環中的每一節點具有來自較高節點環的節點標識符。
50.如權利要求39所述的系統，其特徵在於，所述第一較低節點環中的一個或多個節點也包括在所述第二較低節點環中。
51.如權利要求50所述的系統，其特徵在於，所述第一較低節點環中的一個或多個節點包括在所述第二較低節點環中包括所述第一較低節點環中的一個或多個節點在所述第二較低節點環中被起別名。
全文摘要
本發明涉及用於將資源請求與對應的資源會合的方法、系統和電腦程式產品。使用模運算在兩個方向上遍歷雙向連結的已排序列表。已排序列表可以基於多個鄰近性度量來劃分。節點路由表提供了聯盟基礎結構的ID空間內對節點的對數索引，以便於更有效的路由。消息可被路由到環內的節點並可被鄰近地路由到其它已劃分環內的節點。
文檔編號H04L12/58GK1764171SQ200510116209
公開日2006年4月26日 申請日期2005年10月21日 優先權日2004年10月22日
發明者G·K·R·卡基法亞, R·L·哈薩, T·L·洛德赫菲 申請人:微軟公司