TW200803303A - Inter-proximity communication within a rendezvous federation - Google Patents

Description

200803303 九、發明說明： 【發明所屬之技術領域】 本發明係關於用於促進匯集聯合體内之鄰近間通訊的 方法、系統及電腦程式產品。 、 【先前技術】 電腦系統及相關技術對社會之諸多方面產生影響。事 實上，電腦系統能夠處理資訊之功能已經改變了吾人之 活及工作方式。在出現電腦系統之前由手工執行之大量= 務（例如，文字處理、排程及資料庫管理）現在通常 電腦糸統執行。新％，電腦系統被耦接至另-電腦系統且 八他電子裝置，以形成有線及無線電腦網路，該等 ;電腦^統及其他電子裝置可經由該等電腦網路傳輸電子資 科。結果’許多在一電腦系統中執行之任 通訊、存取雷不顏从 口 9 印文件）、、：子料、控制家用電子產品、冑覽網頁及列 及、、星由有線及/或無線電腦網路在許多電腦系 既及/或其他雷 他電子裝置之間交換電子訊息。 疋’為了利用一網路資源來執行由電腦完成之任 得，一電腦条β、 、、必須擁有某種方式來識別及存取該網路資 源。相應地， ^ ’該等資源通常被指派惟一識別碼（例如，網 路位址）， 、 、 識別該等資源且可用於將一資源與其他資 源區分開來。 u此，一希望利用一資源之電腦系統可使用 對應於該資； / 貝碌之網路位址連接該資源。但是，如果一電腦 糸統事先不4 & 卜# % —網路資源之網路位址，則難以存取一網 路資源。舉你丨 _ 牛列而g ，如果一電腦系統（或另一網路電腦系 5 200803303 統） 上列 域名 散式 之資 如， 發應 同機 應用 (即 是自 且具 需要 相容 散式 能被 致問 “鍵 器來 記錄 此， 不知道一網路印表機之位址，則不能在該網路印表機 印文件。 祁馬処，〇规苟冤腦糸統開發了各種機制，例如，網 稱糸統（DNS )、Active Directory( “AD” ）、八 檔案系統（“ DFS” ），用以識別（及存取）先前未知 源。但是，由於可經由不同電腦網路存取之資源（例 裝置及服務）的數量及差異性，開發人員經常需要開 用程式來實施各種不同資源識別及存取機制。每一= 制可具有不同編碣要求，也許不能為開發人員提供一 程式中所需要之全部功能。 ^ 舉例而言’儘管網域名稱系統具有一八 ^ ^ 刀散式管理牟 不需要集中式管理），但網域名稱系統之 切恶不足、不 組織的（self-organizing)，支援一弱 ^ x 貝枓及查詢模型， 有一固定根集合。另一方面，AD是足^ 集中式管理。另外，不同機制之態樣：動態的，但 。舉例而言，使用網域名稱系統識 犯不 〈資源可能邀八 檔案系統路由通訊協定不相容。因此， ί 迫選擇最合適之機制，而玫棄其他機制之開發人員可 用於識別資源之機制在點辦點網路中β 點。 了成尤其容县道 題。網域名稱系統提供一查閱服務， 易導 ”，以ip位址作為“值”，其依賴於〜，機名稱作為 實施查閱要求。另外，網域名稱系統需要管理次x伺服 )，以允許用戶端能夠在名稱伺服器貝訊（Ns 必須在將一資源輸入網域名稱系统中 見。因 、、之後，才可以在 6 200803303 一網路上識別該資源。在更大規模網路中，節點經常連接 該網路及從該網路斷開連接，依靠資訊項並非總是實際可 行。此外，網域名稱系統是專門用於查找主機或服務等任 務的，通常不適用於其他類型之資源。 相應地，已經開發了其他用於資源識別及存取之機 制，以嘗試克服該等缺點。大量機制包括分散式查閱通訊 協定，該等通訊協定較之網域名稱系統更具有擴充性。此 等機制使用各種節點配置及路由演算法，以將要求路由至 相應資源，及儲存查閱資訊。 該等機制中之至少一種機制利用一網路中每一節點之 本機多位準鄰居圖，以將訊息路由至一目的節點。此實質 上導致一種架構，在此架構中，每一節點係一相應節點樹 之“根節點”，（該等節點位於該根節點之鄰居圖中）。訊 息被逐位遞增路由至一目的識別碼（例如， ***6 = >**46 = >，*346 = >2346，其中*s表示萬用字元此等 類逛機制之路由效率為0(log N)路由躍點，需要節點維護 〆Ο (log N)大小之路由表。 該等機制中至少一其他機制為節點指派一惟一識別 麟，該識別碼取自一線性數字環。節點維護路由表，該等 表中包含指向其直接後續節點（根據識別碼值）之指標， 以及指向其識別碼值最接近識別碼+ 2 L值之後續節點的指 標。此專類型機制之路由效率也為O(logN)路由躍點，需 要節點維護一 〇 (1 〇 g N )大小之路由表。 至少再一其他機制需要0(1〇g Ni/d)路由躍點，需要節 7 200803303 點維護~ Orm丄 WU)大小之路由表。因此，所有 效率取決於r ^機制之路由 必（至少部分取決於）系統中之節點數目。 另外，由於（對於該等機制中之至少一部分 別碼可在一供^ ’带』）識 5衣内被均勻分佈，所以總是存在某一可< 使該環内節點之間的路由導致某種較低效率。I例：：：

路由躍點可以跨躍廣闊地理距離，跨躍更昂貴鏈路， 穿過不安全網域，等等。另夕卜，當訊息路由涉及多個躍： 時，此等事件有可能發生多次。遺撼地是，此等機制沒有 考慮節點相互之間的鄰近性（實體鄰近或其他 八）〇例 如，根據一環中之節點分佈，將一訊息由紐約路由至波士 頓可能涉及將該訊息從紐約路由至倫敦、至亞特蘭大 至 東京，然後到達波士頓。 相應地，至少一種其他最近機制考慮了鄰近性，其方 法是將鄰近性定義為單一純量鄰近量度（例如，ip路由躍 點或地理距離）。此等機制利用基於鄰近性之概念來選擇路 由表項。由於對於每一路由表項存在許多“正確，，備選節 點，所以此等機制嘗試從該等備選節點中選擇一鄰近節 點。對於此等機制可以提供一種功能，使每一節點能夠確 定一具有既定ip位址之節點與其自身之“距離”。在將訊 息路由至一更遠節點之前，可以在更鄰近環中之節點間路 由該等訊息，以朝向一目的前進。因此，可以節省一些資 源，且路由效率更高。 遺憾的是，此等現有機制通常沒有提供：節點間之對 稱關係（即，如果一第一節點將一第二節點看作其夥伴， 8 200803303 該第二節點也將該第一節點 (順時針方向及逆時針方向 近量度分割節點之鏈接串列 鄰近量度路由訊息，等等。 之節點間動態、分散式及高 路之所有節點廣播資料時。 看作其夥伴）、在一環之兩方向 )上路由訊息、基於複數個鄰 (Hnkedlist)以及基於複數個 此等缺點可能會限制在一網路 效地傳輸資料，例如在向該網

【發明内容】 本發明提供用於促進匯集聯合體内之鄰近間通訊的方 法、系統及電腦程式產品。在一些具體實施例中，維護對 於〆節點之間接環（collateral ring )集合登錄表。一節點 存取一間接環集合登錄表，該表被組態用於儲存該節點之 間换環集合登錄。每一間接環集合登錄被組態用於指示該 節黠之一間接環，及該節點之間接環内之至少—相應登錄 節點。從維護有關於該環樹（tree of rings )之組態的可用 實源中搜尋間接環集合登錄表資訊。基於所發現之間接環 集合登錄表資訊，用適當間接環集合登錄狀態更新該間接 環集合登錄表。該適當間接環集合登錄狀態包括該節點之 ，間接環，及該節點之間接環内之至少一相應登錄節點。 在其他具體實施例中，鄰近間通訊在一環樹中被發 送。在鄰近間通訊之一具體實施例中，確定一節點將向該 節雜之一指定間接環中傳送一訊息。該節點存取一間接變 集合登錄表，該表被組態用於儲存該節點之間接環集合登 錄。母一間接環集合登錄被組態用於指示該節點之一間接 環，及該節點之間接環内之至少一相應登錄節點。從該節 9 200803303 點之間 環集合 合登錄 送到至 在 希望向 内一目 識別， 之上階 別之登 析至一 之一被 提 念，在 “發明 基本特 圍。 其 明部分 附申請 發明之 更全面 施本發 【實施 接環集合登錄表中識別該指定間接環之至少一間 登錄。該等至少一間接環集合登錄之母一間接環 指示該指定間接環之至少一登錄節點。該訊息被 少一被指示登錄節點。 鄰近間通訊之另一具體實施例中，確定一起始節 一目的節點路由一訊息，該目的節點最接近該環 標鄰近環的既定節點識別碼。一或多個登錄節點 已知該等登錄節點為該目標鄰近環與該目標鄰近 環中至少之一的成員節點。該訊息被傳送至一被 錄節點。該訊息指示該被識別登錄節點將該訊息 節點，該節點之節點識別碼最接近該目標鄰近環 指示目的節點。 供本“發明内容”係為了以一簡化方式介紹一組 下文之“實施方式”中將進一步對其進行描述。 内各無意於確定本申請專利之發明的關鍵特徵 徵’也無意於用來辅助確定本申請專利之發明的 他特徵與優點將在隨後之說明中列出，且可由該 理解，或者透過實踐本文之講授來學習。利用在 專利範圍内特別指定之儀器及組合可實現及獲得 特徵及優點。從以下說明及隨附申請專利範圍可 地明瞭本發明之特徵，或者可藉由如下文所列來 明來對學習該等特徵。 方式】 接 集 發 點 樹 被 環 識 解 中 概 本 或 範 說 隨 本 以 實 10 200803303 本發明提供用於促進匯集聯合體内之鄰近間通訊 法、系統及電腦程式產品。在一些具體實施例中，維 於一節點之間接環集合登錄表。一節點存取一間接環 登錄表，該表被組態用於儲存該節點之間接環集合登 每一間接環集合登錄被組態用於指示該節點之一間接 及進入該節點之間接環内之至少一相應登錄節點。從 有關於該環樹之組態的可用資源中搜尋間接環集合登 資訊。基於所發現之間接環集合登錄表資訊，用適當 環集合登錄狀態更新該間接環集合登錄表。該適當間 集合登錄狀態包括指示該節點之一間接環，及進入該 之間接環内之至少一相應登錄節點。 在其他具體實施例中，在一環樹中發送鄰近間通 在鄰近間通訊之一具體實施例中，確定一節點將向該 之一指定間接環中傳送一訊息。該節點存取一間接環 登錄表，該表被組態用於儲存該節點之間接環集合登 每一間接環集合登錄被組態用於指示該節點之一間接 及進入該節點之間接環内之至少一相應登錄節點。從 點之間接環集合登錄表中識別該指定間接環之至少一 環集合登錄。該等至少一間接環集合登錄之每一間接 合登錄指示該指定間接環之至少一登錄節點。該訊息 送到至少一被指示登錄節點。 在鄰近間通訊之另一具體實施例中，確定一起始 希望向一目的節點路由一訊息，該目的節點最接近該 内一目標鄰近環的既定節點識別碼。一或多個登錄節 的方 護對 集合 錄。 環， 維護 錄表 間接 接環 節點 訊。 節點 集合 錄。 環， 該節 間接 環集 被發 節點 壞樹 點被 11 200803303 識別，已知該等登錄節點為誃 之上階環中至少之一的成員二標鄰近環與該目標鄰近環 別之登錄節點。該訊息指=點°該訊息被傳送至一被識 析至-節點，該節點之節點^破識別登錄節點將該訊息解 之一被指示目的節點。 β别碼最接近該目標鄰近環中 本發明之申請專利範園内 取搵胪，铯μ )具體實施例包括電腦可讀 取媒體，其用於承載或於其 貝 社爐。+德帝 T儲存電腦可執行指令或資料 、、、口構。此種電腦可讀取媒體 叶 存取之任意可用拔辨。、，、了由一通用或專用電腦系統 " 、。以實例而非限制方式說明之，電腦 可讀取媒體可包括實體儲存 媒體，例如，隨機存取記憶體、 ::㈣、電性可抹除可程式化唯讀記憶體、唯讀光碟 、他光碟健存裝置、磁碟儲存或其他磁碟儲存裝置、或 :何其他可被用於以電腦可執行指令、電腦可讀指令或 二料結構方式健存或承載所需要程式碼構件之媒體，且該 等媒體可由一通用或專用電腦系統存取。 在此說明及隨後之申請專利範圍内，一“網路”被定 義為（可能性相異速度之）一或多個資料鏈接，其允許在 電腦系統及/或模組（例如硬體及/或軟體模組）之間傳輸 電子資料。當經由一網路或另一通訊連接（可以是固線、 無線或固線及無線之組合）向一電腦系統傳輸或提供資訊 時’該連接被適當地視為一電腦可讀取媒體。因此，任何 這樣的鏈接適當地視為一電腦可讀取媒體。上述的組合也 應該包含在電腦可讀媒體之範圍内。電腦可執行指令包括 (例如）可導致一通用電腦系統或專用電腦系統執行特定 12 200803303 功能或一組功能之指令及資料。該電腦可執行指令可以為 (例如）二進位、中間格式指令，例如組合語言，甚至是 源代碼。在一些具體實施例中，諸如專用積體電路或閘陣 列之類的硬體模組被最佳化’以實施本發明之原理。 在此說明及隨後之申請專利範圍内，“節點，，被定義 為一或多個軟體模組、一或多個硬體模組，或兩者之組合， 其一起合作以對電子資料執行操作。舉例而言，節點之定 義包括一個人電腦之硬體組件，也包括軟體模組，例如該 個人電腦之作業系統。該等模組之實體佈局並不重要。一 節點可包括一或多個經由一網路耦接之電腦。與此類似， 一節點可包括單一實體裝置（例如，一行動電話或個人數 位助理 PDA” ），其中内部換組（例如一記憶體及處理器） 一起合作以對電子資料執行操作。另外，一節點可包括專 用硬體，例如一包括專用積體電路之路由器。 热習此項技術應理解，本發明可被實施於具有許多類 型之節點組態的網路計算環境中，包括：個人電腦、膝上 型電腦、手持式裝置、多處理器系統、基於微處理器或可 程式化消費型電子產品、網路個人電腦、迷你電腦、大梨 電腦、行動電話、PDA、呼叫器、路由器、閘道、代理設 備（broker )、代理（pr〇xy )、防火牆、重新導向器、網路 位址轉譯機’等等。本發明也可被實施於分散式系統環境 中’在此環境中，本機及遠端節點均執行任務，經由一網 路將該等郎點鏈接在一起（既可藉由固線資料鏈接、無線 貝料鍵接’也可藉由固線及無線資料鏈接之組合）。在一分 13 200803303 散式系統環境中，程式模組可位於本機及遠端記憶體儲存 裝置中。 聯合體架構 第1圖說明一聯合體基礎建設之實例1 〇 0。該聯合體 基礎建設100包括節點101、i 02、103，其可構成不同類 型之聯合夥伴關係。舉例而言，節點1 〇 1、1 〇 2、1 〇 3可被 相互聯合為沒有根節點之對等節點。節點1 〇 1、丨02及1 〇3 中之每一節點各別具有一相應識別碼1 7 1、1 8 2及1 9 3。 一般來說，節點101、102、103可利用聯合通訊協定 來構成夥伴關係且交換資訊（例如，與其他節點進行互動 之相關狀態資訊）。夥伴關係之形成及資訊之交換促進了對 資源之更有效及更可靠存取。其他中間節點（未示出）可 存在於節點1 〇 1、丨0 2及1 0 3之間（例如，其識別碼介於 1 7 1與1 93之間的節點）。因此，例如在節點1 0 1及節點1 〇3 之間路由的訊息可經過一或多個其他中間節點。 聯合體基礎建設1 〇 〇中之節點（包括其他中間節點） 可包括相應之匯集通訊協定堆疊。舉例而言，節點1 〇 t、 102及103各別包括相應匯集通訊協定堆疊丨41、142及 143。該等通訊協定堆疊141、M2及143中之每一堆疊包 括一應用層（例如，應用層121、122及123 )及其他較低 層（例如，其他相應較低層1 3 1、1 3 2及1 3 3 )。一匯集通 訊協定堆疊中之每一層負責有關將一資源要求與一相應資 源匯集之不同功能。 舉例而言，其他較低層可包括一通道層、一路由層及 14 200803303 一功能層。一般來說，一通道層負責從一端點向另一 (例如，從節點1 0 1向節點1 03 )可靠傳輸一訊息（1 使用 WS-ReliableMessaging及簡單物件存取 (SOAP))。該通道層還負責處理傳入及輸出可靠袭 頭，及維護與可靠發訊會話相關之狀態。 一般來說，一路由層負責計算朝向一目的之下一 (hop )。該路由層還負責處理傳入及傳出定址及路由 標頭及維護路由狀態。一般來說，一功能層負責發出 理匯集通訊協定訊息，例如加入與脫離要求、偵測、 及其他訊息，還產生對此等訊息之回應。該功能層處 自路由層之要求訊息，如果存在相應回應資訊，則使 路由層將其發送回起始端。該功能層還起始化要求訊 利用該路由層來傳輸要求訊息。 一般來說，一應用層處理由該功能層傳輸而來之 集通訊協定專用資料（即應用訊息）。該功能層可存取 該應用層之應用資/钭，且獲取及將應用資料置於匯集 協定訊息中（例如，偵測及更新）。即，該功能層可導 用資料被捐1負於匯鱼、$ Λ 應集通訊協定訊息上，並可導致該應 料被傳回該接收藤m、s _❹^ Η又應杲通訊協定節點中之應用層。在一 體貫施例中，廣用咨刺 馬用貝枓可用於識別資源及資源興趣。因 該應用層可包乜„ 枯辱用邏輯與狀態，其處理從其他較低 收之資料及發ill 5 A & u 如廷至該等其他較低層之資料，用於識別 及資源興趣。 遵合機 -端點 Η如， 協定 訊標 躍點 訊息 及處 更新 理來 用該 息且 非匯 來自 通訊 致應 用資 些具 此， 層接 資源 15 200803303 節點可利用各種不同機制進行聯合。一第一聯合 制包括向所有其他對等節點轉遞資訊之對等節點。當一 點準備加入一聯合體基礎建設時，該節點利用一廣播/多 搜尋通訊協定（例如，WS-Discovery)來宣告其存在， 發出廣播/多播尋找訊息以偵測其他節點。於是，該節點 該網路中已經存在之其他節點建立一種簡單之轉遞夥伴 係，且接受與新加入節點之新夥伴關係。之後，該節點 單地向其所有夥伴節點轉遞全部專用訊息。 一第二聯合機制包括向其目的最高效地傳輸專用訊 之對等節點。當一新節點準備加入一聯合體基礎建設時 該新節點利用一廣播/多播搜尋通訊協定（例如 WS-Discovery)來宣告其存在，且發出廣播/多播尋找訊 以偵測作為該聯合體基礎建設之部分的其他節點。在偵 到另一節點時，該新節點與其他節點建立一夥伴關係。 所建立之夥伴關係，該新節點知曉其他已經加入該聯合 基礎建設之節點的存在。於是，其與此等新知曉節點建 夥伴關係，且接受任何新進入夥伴關係要求。 節點到達/脫離及特定專用訊息中之興趣註冊都經 該聯合體基礎建設氾濫廣播（flood )，導致所有節點均 面知曉其他夥伴節點及專用訊息中之興趣註冊。利用這 全域知識，任意節點可將專用訊息直接發送到對該專用 息表示興趣之節點。 一第三聯合機制包括將全部專用訊息間接轉遞至其 的之對等節點。在此第三機制中，節點被指派識別 機 /r/r 即 播 且 與 關 簡 息 息 測 由 體 立 由 全 訊 因 碼 16 200803303 (ID )，例如，一 12 8位元或1 60位元之識別碼。藉由將 一既定專用訊息之目的識別（例如，URI )對映（例如， 雜湊）至此1 2 8位元或1 6 0位元識別碼空間，可以獲得一 識別碼，可以確定一最接近此識別碼之節點，作為負責在 該既定專用訊息中維護興趣註冊之節點。 在此第三機制中，節點之到達與脫離均被經由該整體 結構氾濫廣播。另一方面，在特定專用訊息中之興趣註冊 被轉遞至被確定用來負責維護此註冊資訊之節點。為具有 可延展性、負載平衡及容錯性，接收特定專用訊息中之興 趣註冊的節點能夠可靠地在其鄰域集合中氾濫廣播該註冊 資訊。一特定節點之鄰域集合可被確定為具有以下特點之 集合：其識別碼落於該指定節點之識別碼兩側的預定範圍 内。 與該第二機制類似，一新加入節點利用一廣播/多播搜 尋通訊協定（例如，WS-Discovery)來宣告其存在，且發 出廣播/多播尋找訊息以偵測已作為該聯合體基礎建設之 部分的節點。該新節點與所發現之節點建立夥伴關係，且 利用該夥伴關係暸解其他加入該聯合體基礎建設之新節點 的存在。然後，該新節點與此等新發現之節點建立夥伴關 係，且接受新傳入夥伴關係要求。該新節點從其夥伴接受 一特定應用層專用資源中之傳入興趣註冊，其對此負責， 且在其鄰域集合中氾濫廣播它們。因此，訊息通常可被經 由中間路由節點（例如，新加入節點與其有夥伴關係之節 點或者一夥伴節點知曉之節點）轉遞至其最終目的。 17 200803303 回應接收到該傳

至該夥伴節點，I可A ^將該訊‘I 冊資訊。因此，在使：：責為該”所指定目的維讀 之所有節點全面知 ^體基礎建 分割於該等節點之間。：他lp S該註冊資訊# 在其專用訊息中維i僅經由該夥伴之節點（其可能 目的。因此，藉=冊資訊1將專用訊息傳輸至其 息中之興趣註冊資却、^ ^ ^ 轉遞來完成間接傳輪。這一點 一機制形成對比，扃楚 , 和 在第—機制中，籍由向所有該等移 點傳遞來元成該間接傳輸。 第：聯合機制包括向其他對等節點路由訊息之 即點。此第四機制與第三機制之不同點至少包括.兮 到請離及特定專用訊息中之興趣註冊均被全部路 不是被泛溢廣播。政士、s 4 Μ 、訊協定被設計用於保證專用 及註冊訊息（其表示對此等專用訊息之興趣）之間的@ 第2圖說明一電腦架構2〇〇之實例，其促進將要 接路由至移伴。電腦架冑200描述不同類型之電腦系 裝置，其可能分散於多個參與—聯合體基礎建設之局 哥範圍。 工作站233可包括一已註冊ΡηΡ提供者執行布 為向其夥伴通知此Ρ η Ρ提供者執行個體之存在，工作立 經由該聯合體基礎建設路由註冊要求2〇1。註冊要求 起始被轉遞至膝上型電腦231，該膝上型電腦231又 冊要求201轉發至訊息代理器叫，其又將註冊要^ 轉遞 該註 設中 有效 負責 最終 理訊 與第 伴節 對等 節點 由而 訊息 求間 統及 部搜 體。 5 233 201 將註 • 201 18 200803303 轉遞至訊息閘道24 1。訊息閘道24 1將該註冊資訊註冊要 求201保存在其資料庫中，且向工作站233返回成功訊息 204 〇

接下來，另一已註冊提供者執行個體（此次為運行服 務之執行個體）在該工作站2 3 3中變為活動狀態。此時， 接要息 直冊訊 05註功 2 訊成 求資回 要冊返 冊註33 註該 2 將將站 及41作 冊 2 工 註道向 責 間 且 負息 ， 41訊中 2 。 庫 道41料 閘 2 資 息道其 訊閘在 解息存 瞭訊保 點至05 節遞 2 該轉求 接下來，印表機236 (例如，一 UpnP印表機）被啟動 電源，且發送宣告2 0 7。伺服器2 3 4偵測宣告2 0 7，且將註 冊要求208路由至訊息代理器237。訊息代理器237將註 冊要求208轉遞至訊息閘道241。訊息閘道241將該註冊 資訊註冊要求208保存在其資料庫中，且向伺服器234返 回成功訊息2 1 0。 接下來，個人電腦242發出查閱要求211以搜尋所有 裝置。由於個人電腦212不知道向何處轉遞查閱要求21卜 所以其經由工作站243路由查閱要求211。當註冊要求及 查閱要求被路由至相同目的時，該路由通訊協定基本保證 該等兩個要求（導致工作站242向訊息閘道241轉遞搜尋 要求2 11 )之間的匯集。訊息閘道24丨查閱由其維護之註 冊訊息，且將搜尋要求2 1 1轉遞至該工作站2 3 3及伺服器 234。工作站23 3及伺服器234各別將回應訊息214及216 發送至個人電腦242。 19 200803303 此第四機制工作時僅將一要求路由（而不是氾濫廣播） 到全面瞭解一要求所指定註冊資訊的節點（訊息閘道 241)。下文將進一步詳盡說明，此第四機制基本保證該路 由可在0(1 ogN)個躍點内完成，其中N為參與該聯合體基 礎建設之節點數目。由於此第四機制有效地分割節點夥伴 關係及註冊資訊，其可以擴展至非常大之網路，甚至是網 際網路。 儘管已經描述了許多聯合機制，但熟習此項技術者在 閱讀此說明之後應暸解，其他聯合體機制亦係可能。 一聯合體内節點之間的關係 相應地，一聯合體由一組節點組成，該等節點相互合 作，以形成一動態、可擴展網路，在此網路中，可以系統 高效地分發及定位資訊。使用一二進位關係將節點組織為 一有序串列，以加入一聯合體，該二進位關係自反的、非 對稱的、遞移的、整體的，且定義於節點識別域上。該有 序串列之兩端被聯結，從而形成一環。因此，該串列中之 每一節點認為自身位於該有序串列之中間（使用模運算之 結果）。另外，該串列被雙向鏈結，從而任意節點可在任一 方向上行旅該串列。 每一聯合節點可被指派一識別碼（例如，藉由一具有 重複值偵測之隨機數產生器指派），該識別碼來自一固定識 別碼集合，介於0至某一固定上限之間。因此，向該固定 上限之識別碼加1會導致該識別碼為零（即，從該鏈接串 列之結尾移至該鏈接串列之開頭）。此外，由該節點識別域 20 200803303 向該節點本身定義一個一對一對映函數。 第3圖描述一實例鏈接串列3 0 4及相應環3 0 6。對於 一此種既定環，可以定義以下函數：

RouteNumerically(V，Msg) ··給定該節點識別值域之一 值V及一訊息“ Msg” ，將該訊息傳輸至節點X，可使用 該對映函數將該節點X之識別對映至V。

Neighborhood(X，S):鄰域係指位於節點X之兩側、 其基數等於S之節點集合。 當該聯合體内之所有節點均全面知曉該環時，藉由直 接將M s g發送至節點X(其識別係藉由向v應用該對映函 數而獲得）而實施RouteNumerically(V，Msg)。或者，當節 點具有其他節點之有限知識時（例如，僅直接相鄰節點之 知識），可藉由將訊息轉遞至沿該環之連續節點，直到其到 達目標節點X為止’以此實施R〇uteNumerically(V，Msg)。 另者（也是最佳方式），節點可儲存有關該環之足夠資 訊，以執行一分散式二進位搜尋（不必擁有全面資訊或實 施直接相鄰相點之間的路由）。該環資訊之數量可被組態， 使得維護環資訊對於每一節點的影響足夠小，但允許透過 減少路由躍點數目來提高路由效能。 如前所述，可使用定義於一足夠大之有界自然數集上 的“ < ”（小於）關係來指派識別碼，即其範圍係介於0 至某一固定值（含）之間的有限數集。因此，參與該聯合 體之母一卽點被指派一自然數，該自然數介於〇與某一適 當選擇之上限（含）之間。該範圍不一定非常緊密，在被 21 200803303 指派給節點之數字之間可以存在間隔。被指派給一節點之 數字用作其在該環中之識別。該對映函數將一介於兩節點 識別之間的數字對映至其識別在數值上最接近該數字之節 點，從而導致（account for)該數字空間中的間隔。 此方法具有許多優點。藉由為每一節點指派一均勻分 佈之數位，從而提高了該環之所有分段均被均勻填充之可 能性。另外，利用模運算可以有效地完成後續、前置及鄰 域計算。 在一些具體實施例中，聯合節點被指派來自一識別碼 空間之識別碼，該識別碼空間非常大，從而使得兩個節點 被指派相同識別碼之機會非常小（例如，當使用隨機數產 生方式時）。舉例而言，一節點可被指派一 〇至bn-1範圍 内之識別碼，其中b等於（例如）0或16，η等於（例如） 128位元或1 60位元等價數字。相應地，可以為一節點指 派一 0至164G-1 (或大約1.461 502Ε48 )範圍内之識別碼。 0至1 64G-1之範圍提供（例如）之識別碼數目足夠為網際 網路上之每一節點指派一惟一識別碼。 因此，一聯合體内之每一節點可具有： 一識別碼，其係均勻分佈於〇至bn-1範圍内之一數字 值；以及 一路由表，其包括（所有運算均以bn為模完成）·· 後續節點（s ); 前置節點（P ); 鄰域節點（Pk，…，Pi，P，s，Si，…，Sj)，Sj.s.id > (id + 22 200803303 u/2)，j g v/2-l，pk.p.id<(id-u/2)，k $ v/2-1 路由節點（r-(n_i)， ···， r-i， ri ? ···， rn_i)，

RouteNumerically(id 士 b1，Msg)。 其中b為數基，n是域大小（其單位係數位之> u為鄰域範圍，v為鄰域大小，該運算係以bn為模而 為獲得良好路由效率及容錯性能，u與v之值可以 且v2max(log2(N)，4)，其中N是實體參與該聯合 點總數。N可以由出現在一環分段中之節點數目估 長度大於或等於b，例如，當存在識別碼之均勻分4 與η之典型值為b = 8或16，n= 128位元或160位元 位。 相應地，路由節點可以形成跨越一環之對數索 決於一環上之節點位置，例如在id土W集合中之每 處均存在一現有節點時，其中i = (l，2, · · ·（η-I))， 數索引係有可能的。但是，有可能並非在集合中之 字處均存在現有節點。在此情況下，最接近id 土 b1 可以被選作一路由節點。所得到之對數索引並不準 至對於該集合中之某些數字缺少惟一路由節點。 再次參考第3圖，第3圖說明一聯合體基礎建 點之間的實例二進位關係，該基礎建設採用有序串 及相應環3 06之形式。有序串列3 04之識別碼空間 至28-1 (或25 5 )範圍内。即b = 2及n = 8。因此， 中所述之節點被指派介於0至2 5 5範圍内的識別碼 串列3 04利用一二進位關係，該二進位關係是自反 ;以及 r 土i = ί固數）， 完成。 是u = b 體之節 計，其 Μ寺。b 等價數 引。取 一數字 精確對 每一數 之節點 確’甚 設中節 歹丨J 304 介於0 第3圖 。有序 的、非 23 200803303 對稱的、遞㈣、整體的，及定義於節點識別域上。有序 串列304之兩端被鏈結’從而形成一環3〇6。此使得第3 圖中之每—節點可以認為自身位於該有序串歹"04之中 間。該有序串歹"04被雙向鍵結，從而任意節點可在任一 方向上行旅該有序串列304。可以28為模執行用於行旅有 序串列304 (或環306)之運算。因此，25 5 (或該有序串 列3 04之末尾）+1=0 (或有序串列3〇4之開碩）。 該 路 由 表 指示識別碼 64之後續識別碼為謂 i別 碼7 6( 以 順 時 針 方 向 緊 隨在識別碼 64之後的識別碼）。 舉 例而 言 ， 當 一 新 節 點 ( 例如，識別碼為71的節點）加入 該 聯合 體 基 礎 建 設 或 一 現 有節點（例 如’識別碼76 )脫離 該 聯合 體 基 礎 建 設 時 ， 該 後續節點可 能變化。與此類似， 該 路由 表 指 示 識 別 碼 6 4 . 之前置識別i 馬為識別碼5 0 (以逆 時 針方 向 緊 臨 在 識 別 碼 6 4之刖的識別碼）。舉例而言，當一 :節黑J 例 如 識. 別‘ 碼 為 59的節點） 加入該聯合體基礎建 設 或一 現 有 節 點 ( 例 如 ， 識別碼50 ) 脫離該聯合體基礎建 設 時， 該 前 置 節 點 可 能 變 化。 該 路 由 表 進一步指示 識別碼64之鄰域節 點 集合 擁 有 識 別 碼 83 ' 76 、 50 及 46 。鄰域節點集合可以 是 指定 數 S 個 節 點 ( 即 9 鄰域大小V)，該等節點位於識別 1喝 丨64 之 指 定 範 圍 ( 即 ， 鄰居範圍u )之内。各種不同鄰 域 大小 及 鄰 居 範 圍 ( 例 如 ，V = 4 及 U = =1 0 )可被用於識別該 鄰 域節 點 集 合 〇 舉 例 而 言 ，當節點加 入或脫離該聯合體基 礎 建設 或 當 指 定 節 點 數 S 或指定範圍 變化時’一鄰域集合 可: 能變 化 〇 24

200803303 該路由表進一步指示識别碼 200、2、30、46、50、64、μ 可路由至 t 64 、 64 、 64 及2 00之節點。藉由識別 之節點，可以產生此“卜其接中'，集厂以中」 即b = 2及,^舉例而言’可以藉由(計2算=，近5 或72之節點而識別具有識別碼π 心郎點。 一節點可以將訊息（例如， 用於存取資游夕』 接路由至一前置節點、一後嘖 ’、一 〇 便_即點、鄰域節點集4 忍郎點，或者任意路由節點。 ^ 坚具體實施例1 實施數字路由函數，以路由邙自 m

峪由訊息。因此，可在節，S R〇UteNumericaUy(V，Msg)’ 以將 Msg 傳輸到聯名 節點Y (其識別碼在數值上最接近V)，且將節點 別碼返回節點X。舉例而言，具有識別碼64之高 實施 R〇ixteNUmeriCally(243, Msg)，使一訊息被路由 識別碼2 5 0之節點。但是，由於識別碼2 5 0不是識 之路由節點，所以識別碼64可以將該訊息路由至詞 (與243最接近之路由節點）。具有識別碼2之節點 施 RouteNumerically(243，Msg)，使該訊息被路由 識別碼 250 之節點（直接路由或經由其他中間 由）。因此，RouteNumerically函數被遞迴叫用，每 將一訊息路由至更接近目的之節點。 有利地，本發明之其他具體實施例可根據—或 近類別（例如，地理界限、路由特徵（例如’ IP路由 管理域、管理界限，等等）之複數個鄰近準則，將 i別碼為 98 、 135 ί： 一數字 6, 7) 〇 64 + 23 •求）直 ‘中之任 ，節點 X實施 體中之 Υ之識 點可以 至具有 別碼64 泛別碼2 又可實 至具有 節點路 次叫用 多個鄰 躍點）、 —環分 25 200803303 割為環之環或環之樹。應理解，可利用相同類： 則將一環分割多於一次。舉例而言，可根據一； 及一國家鄰近準則（均為一地理界限鄰近類別 分割一環。 由於識別碼可在一識別碼空間中均勻分散 生之結果），一圓型識別碼空間中之任意既定分 不同鄰近類別之節點的可能性非常大（前提是 大體相同之基數）。當節點數目足以獲得有意義 時，此種機率會進一步增大。 因此，從鄰近的角度來看，任意既定節點 通常都被很好地分散。由於所公佈的應用程式 鄰域節點中複製，所以從鄰近的角度來看，該 也可被很好地分散。 第4圖說明一環之環400，其促進鄰近路 可被看到一主控環或根環，其包含環402、403 一環之所有節點。環4 0 2、4 0 3及4 0 4之每一環 401之一節點子集，該等節點被依據一指定丨 割。舉例而言，環4 0 1可被依據地理位置劃分， 包含北美之節點，環403包含歐洲之節點，環 洲之節點。 在包含65,536 (216)個識別碼之數值空間中 由具有識別碼5345之北美節點路由至具有識別 亞洲節點的過程包括在環4〇2内路由該訊息， 亞洲節點之一鄰近節點為止。於是該鄰近節點 _之鄰近準 洲鄰近準則 中之準則） (隨機數產 段包括屬於 此等類具有 之平均特性 之鄰域節點 狀態可以在 被公佈資訊 由。環401 及404中每 包含來自環 鄭近準則分 其中環402 404包含亞 ，將一訊息 瑪23345之 直到識別該 可將該訊息 26 200803303 及一亞洲節點進 β —種資源高效 路由至該亞洲節點。因此，在一北美節點 行單一躍點（而不是多個躍點）。相應地， 方式執行路由。 布」鬩說明一⑴入鄰近之實例分割 飿w政士上 J王长樹500，其促進 鄰近路由。根據描述，分割環樹50〇包 中一 Pi ^ Λ I括許多環。該等環 τ之母 ¥表示一有序鏈結串列之一八

77副部分。每一環包 括複數個節點，該等節點擁有該有 值& β 另斤鏈結串列中之識別 碼。仁疋，為清晰起見，因為潛在節 …机1你即.，、、占數目之原因，該等 節點未被明確描述於該等環中（ ] 分割樹500之識別 碼空間可能為b = 16及η = 4〇)。 在分割樹500巾，可根據準貝571 (―第一管理域界 限準則）將根m 5G1分割為複數個子環，包括子環5ΐι、 512、513及514。舉例而言，一網域名稱系統名稱之每一 成分可被看作一鄰近準則’丨中之部分順序是根據他們從 右向左讀取時在網域名稱系統名稱中的出現順序。相應 地，可根據準則581 ( —第二管理域界限準則）將子環511 進一步分割為複數個子環，包括子環521、522及523。 可根據準則572 ( —地理界限準則）將子環522進一 步分割為複數個子環，包括子環531、532及533。可根據 洲、國家、郵遞區號等，對基於位置之鄰近準則進行部分 排序。郵遞區號本身之組織即為階層式的，即可將它們看 作進一步引入鄰近準則之一部分有序子環列。 可根據準則573 ( —第一組織界限準則）將子環53 1 進一步分割為複數個子環，包括子環54卜542、543及544。 27 200803303 根據一既定公司之結構組織方式（例如，分公司、部門及 產品群組）引入鄰近準則之一部分有序串列。相應地，可 根據準則5 83 ( —第二組織界限準則）將子環543進一步 分割為複數個子環，包括子環551及552。 在分割樹500中，每一節點具有單一識別碼，且沿一 由該根至葉之相應分割路徑參與環中。舉例而言，參與子 環552之每一節點還將參與子環543、531、522、511及 根501。可藉由一 RouteProximaiiy函數完成向一目的節點 (識別碼）之路由，如下所示： ROUteProximally(V，Msg，P) ··給定該節點識別域之一值 V及一訊息“ Msg” ，將該訊息傳輸至節點γ，其識別可 被對映至某些節點（根據鄰近準則P，該等節點可被看作 是等價的）中之V。 因此’可藉由以下方式完成路由：在一既定環中逐漸 向更接近於目的節點之位置移動，直到在該環中路由時不 能再前進為止，其判斷條件是該目的節點位於目前節點及 其後續節點或前置節點之間。在該點，該目前節點經由其 參與之下一更大環中的夥伴節點開始路由。根據 RouteProximally叫用中之起始指定，藉由沿著朝向根環之 分割路徑而逐漸移向目的節點，當所要求之鄰近環境中到 達最接近該目的節點之節點時，該逐漸移動過程終止。 路由躍點可一直保持於發起該要求之節點的鄰域内， 直到由於目標節點位於該鄰域之外而不能再在該鄰域内前 進為止。在此點，該鄰近準則被放鬆，以增大該鄰近鄰域 28 200803303 之大小，從而進一步前進。該過程將被重複，直到該鄰近 鄰域被擴展之程度足以包括該目的節點（識別碼）為止。 在鄰近鄰域準則之每一後續放鬆之後所進行之路由躍點可 能是鄰近空間中之更大跳躍，而相比於前一躍點，可以在 數值空間内進行相應較小之跳躍。因此，在到達目的之前， 僅進行絕對需要數目之此類（環間）跳躍。 實際情況可能是：當所公佈之應用資料在該目的節點 之鄰域節點中被複製時，該資料沿該分割樹向下複製，因 此，為查閱訊息而避免一些躍點。 為完成鄰近路由，每一聯合體節點維護其作為成員所 參與之全部環中的後續節點及前置節點（鄰近前置、鄰近 後續及鄰近鄰域，類似於單一環中之後續節點及前置節點） 之引用。為高效率地進行路由，該等節點還可維護對一些 其他節點之引用作為路由夥伴，該等其他節點位於該環内 所討論節點之任意一側，與所討論節點的距離呈指數增 加，（類似於一單一環之路由節點）。在一些具體實施例中， 位於一對連續後續節點或前置節點之間的路由夥伴節點參 與一最低環，該最低環環由目前節點及該等後續節點或前 置節點對中在數值上最接近該目前節點之節點共用。因 此，僅當絕對需要進一步前進時，路由躍點轉而使用一經 放鬆之鄰近準則（即轉向一較高環）向一目的節點前進。 相應地，可以高效地將訊息與一相應聯合體節點匯集。 在一些具體實施例中，節點實施一鄰近路由函數，以 根據等價準則關係路由訊息。因此，既定一數字V及一訊 29 200803303 息 ’’Msg”，一節點可實施 R〇utePr〇ximally(v，Msg，P)，以 將該訊息傳輸給節點Υ，節點γ之識別可被對映至被鄰近 準則Ρ認為等價之節點中的V。鄰近準則Ρ識別分割樹中 之最低環，該分割樹是所有被該準則認為鄰近等價之節點 的共同上階。其可以被表示為一藉由以下方法獲得之字 串：將沿著由根環至其所識別環之路徑發現的搜索準則串 接起來’且使用路徑分隔字元，/，分隔。例如，由子環542 識別 之鄰近 準則可 表示為 ： "Proximity:/.COM/Corp2/LocationA/Div2M。分割樹 500 中 之每一環可被指派一惟一數字，例如，藉由使用一基於SHA 演算法對其表示字串進行雜湊操作。如果數字〇被保留用 於根節點，則可以推斷：R0UteNumerically(V，Msg)= RouteProximally(V，Msg，0)。 例如，子環544中之一節點可實施RouteProximally 以識別子環5 3 1中之一更近節點（例如，更接近子環5 1 3 中之一節點）。接下來，子環531可實施RouteProximally， 以識別子環5 2 2中之一更接近節點。與此類似，子環5 2 2 可實施RouteProximally，以識別子環5 11中之一更接近節 點。與此類似，子環5 11可實施R 〇 u t e P r ο X i m a 11 y，以識別 子環501中之一更接近節點。因此，RouteProximally函 數被遞迴叫用，每次叫用將一訊息路由至更接近目的之節 點。 因此，當考慮鄰近準則時，至一最終目的之路徑上的 路由節點可以繼續停留在發起該要求之節點的鄰近區域内 30 200803303 (同時在一 進行大幅前 擇鄰近準則 放鬆程度足 之被放鬆程 利用上 環内。舉例 其信任網域 向其網域之 方式，為對 可以滿足第 節點内複製 訊息時，都 此，在一組 於其内部之 此外， 聯合。舉例 戶場所之網 銷售人員之 資訊，及/或 聯合。通常 一情況，需 η 〇 d e )。此等 數字空間内，於該起始節點及該目的節點 進），直到或者到達該目標節點，或者根據 不能再進一步前進為止，此時對該鄰近準 以進一步向該目的前進。舉例而言，鄰近 度足以將一訊息由環5 3 1向上路由矣5 22 述鄰近方法，有可能將公佈資訊限定於一 而言，組織可能希望確保組織專用資訊不 之外的實體使用，既不能經由（1 )隱式方 外的節點進行鄰近複製，也不能經由（2 ) 此等資訊之查閱要求提供服務。藉由以下 一態樣：僅在該指定環内鄰近該目標識別 所公佈資訊。因為在路由一節點所發出之 是藉由朝根環方向連續向上攀登其所屬環 織内發出之全部查閱要求非常有可能定位 公佈資訊，從而隱式滿足該第二態樣。 組織不喜歡節點自動與其信任網域之外的 而言，當一銷售人員將其攜帶型電腦連接 路時’即會發上述情況。理想狀態下，屬 攜帶型電腦希望能夠定位在其本籍網域公 在其最低較佳鄰近環内與其本籍網域中之 不允許與該客戶網域内之節點聯合。要支 要能夠定位該本籍網域内之種子節點（ 種子節點可被用於定位在該本籍區域内公 之間 所選 則之 準則 ，等 既定 能被 式， 顯式 方式 碼之 所有 ，因 限制 節點 到客 於該 佈之 節點 援這 seed 佈之 31 200803303 貝 -----ν^，叩匯入 及匯出公佈資訊。種子節點有時也被稱為“訊息閘道”。 節點具體實施例中，一實體在該根環中公佈對種子 Ρ 之引用。可在與該環關聯之惟一數帛（例# 湊其代表字串所獲得惟— ^ /、 種早筋赴 $數子）（作為目標識別碼）公佈

Μ ’’。根據需要，種子節點資訊可進_步被各個環中 之即點快取’肖等環位於朝向該根環中相應目標識別碼的 路徑上。此種隨需快取提供了改良效能、減少了作用點 (hotspot )，|非常頻繁地查閱半靜態資訊時可能發生此 種情況。《子節點資訊還可經由諸如網域名稱系統等复他 方法獲得。 ^ 為提供受限公佈資訊之容錯性能，每一節點可維護一 鄰域節點集合，該等節點屬於其參與之所有環。給定以上 内容，由一節點維護之狀態可總結如下： •一識別碼，其係均勻分佈於〇至bn—丨範圍内之一數字 值0 •一路由表’由以下節點組成（所有運算均係對bn取 模執行）： (對於該節點所參與之每一環，例如環d ) 後續節點（Sd) 前置節點（Pd) 鄰域節點（Pkd，…，Pid，Pd，sd，sld5 ··，Sjd)，使得 Sjd.sd.id > (id + u/2)，j > v/2-1，pkd.Pd.id < (id . u/2)&k tv/2-1 。 32 200803303 路由節點（r.(n_i)5 …，r_i，η，…，rn-i)，使

RouteProximally(id 士 b1，updateMsg，d)，使得 Sd Ssd+i 或 Pd+i S id - b1 $ pd (根據需要）。 其中b為數基，n是域大小（單位係數位個； 鄰域範圍，ν為鄰域大小。 注意，由環“ d”中一既定節點維護之鄰域節 再次出現，作為子環“ d+1 ”中之鄰域節點，該 也參與該子環“ d+1” 。因此，吾人可以推斷， 節點在所有 D 環上維護之鄰域節點總數& D*max(u，v)/2。其考慮到僅保留一既定節點之引 情況之上限是對於一平衡樹之情況。 應注意，當一環被分割為複數個相應的同胞 子環時，允許一指定節點同時參與該等複數個相 環中之多於一個子環，例如，藉由別名方式。別 施用以將（例如）來自不同子環之不同狀態與該 關聯。因此，儘管一既定節點之別名具有相同識 每一別名可具有與其相關聯之不同狀態。別名允 節點參與多個具有不同鄰近準則之環，該等環不 體鄰近準則之共同上階。即，該指定節點可以參 樹之多個分枝。 舉例而言，可以認為一雙NIC (有線及無線 電腦鄰近等價於其他與該膝上型電腦共用相同區 段之無線及有線節點。但是，這兩個不同鄰近準 為子準則，它們僅能在應用不同更高優先權之鄰ϋ 得 r±i = < id + b1 敗），u為 點子集可 既定節點 由一既定 上限為 用，最差 (sibling ) 應同胞子 名可被實 指定節點 別碼，但 許該指定 必是更具 與該鄰近 )膝上型 域網路分 則可建模 ί準則（例 33 200803303 如，一基於組織關係之準則）之後應用。由於該膝上型電 腦屬於同一組織，所以兩個表示1 )有線成員關係及2 )無 線區域網路分段成員關係之子環中的具有別名節點被合併 為一單一節點，該單一節點位於表示該膝上型電腦所屬組 織之環中。應暸解，RouteProximally可如預期工作，而不 需要因為存在別名而進行任何修改。 可根據（可能不同之）環參數對每一鄰近環進行組態。 環參數可被用於定義一鄰域（例如，環參數可表示一鄰域 範圍、一鄰域大小、偵測訊息與脫離訊息定時以及用於偵 測及脫離訊息之分佈態樣），指示一特定聯合機制（例如， 選自上述第一至第四聯合機制或其他聯合機制），或定義相 同鄰近環中路由夥伴之間的通信具體事項。一些環參數可 能更具一般性，應用於複數個不同聯合體制，而其他環參 數更為專用，應用於特定類型之聯合機制。 用於配置一更高位準環之環參數可由較低位準之鄰近 環在一些具體實施例中繼承。例如，環543可繼承環53 1 之一些環參數（環531又由環522繼承，等等）。因此，與 環5 3 1相關聯之鄰域大小及鄰域範圍也與環5 4 1相關聯。 但是，被繼承環參數可被修改，及/或可根據不同環參 數各別組態鄰近環。舉例而言，環5 1 1可能是用於包含大 量節點之管理節點，因此上述第四聯合機制更適合於環 5 11。另一方面，環5 2 1可用於具有較少量節點之小型交 易，因此上述第二種聯合機制更適合於環5 2 1。因此，與 環52 1相關聯之環參數可被設定為（或被繼承參數改變為） 34 200803303 不同於與環5 1 1相關聯之環參數的值。舉例而言， 及5 21之間，指示特定類型之聯合機制的環參 同。類似地，在環51 1及5 21之間，定義一鄰域 可不同。另外，可根據專用於上述第二聯合機制 數組態環5 2 1，而可根據專用於上述第四聯合機 參數組態環5 11。 相應地’可根據鄰近環内節點之特性（例如 所包含資源，等等）靈活組態該等鄰近環。舉例 管理員可使用一組態程序（例如，經由一使用者 鄰近環選擇環參數。一組態程序可促進鄰近環之 係的組態，以及各別鄰近環之組態，例如，用以 承之環參數。 第8圖說明用於分割一聯合體基礎建設節 8 00的實例流程圖。下文將參考第5圖之分割樹 描述方法800。方法800包括存取一有序鏈結串 (操作8 0 1 )，該串列包含已經被指派給一聯合基 之節點的節點識別碼。舉例而言，可以存取由環 之有序鏈結串列。該有序鏈結串列之節點識別碼（ 中描述之節點）可表示一聯合體基礎建設（例如 基礎建設100)中之節點。 方法800包括一存取代表複數個不同鄰近準 類別以分割該有序鏈結串列之操作（操作 8 02 ) 言，代表網域界限5 6 1、地理界限5 6 2及組織界 鄰近準則可被存取。但是，其他鄰近準則，例如 在環5 11 數可以不 之參數也 之特定參 制之特定 ，數目、 而言 ，一 介面）為 間繼承關 覆蓋所繼 點之方法 5 0 0之環 列之操作 礎建設中 501表示 在環501 ，聯合體 則之鄰近 。舉例而 限563之 信任網域 35 200803303 界限，也可出現 先前創建的部分 近準則串列對一 方法800包 分割為一或多個 多個第一子串列 少一節點識別碼 分割為子環5 11 及514之每一子 集。 方法800包 串列之第一子ϊ 804)’該等一或 第一子串列中之 據準則5 8 1將子 521、522 及 523 點識別碼子集。 第9圖說明 流程圖。將參考 述該方法900。 中之操作（操作 一方向上位於該 之節點可以被插 前節點）之前置 在被存取鄰近準則中。鄰近類別可以包括 有序鄰近準則串列。可根據部分有序之鄰 串進行分割。 括根據複數個鄰近準則將該有序鏈結串列 第一子串列之操作（操作8 〇 3 )，該等一或 之每一串列包含來自該有序鏈結串列之至 子集。舉例而言’可根據準則5 7 1將環5 0 1 、512、 513 及 514。子環 511、 512、 513 環可包含來自環5 0 1之不同節點識別碼子 括根據一第二鄰近準則將選自一或多個子 声列分割為一第二子串列之操作（操作 多個子串列之每一子串列包含一包含於該 至少一節點識別碼子集。舉例而言，可根 環511分割為子環521、522及523。子環 之每一子環可包含來自子環511之不同節 用於填充一節點路由表之方法9 0 〇的實例 第3圖中之有序鏈結串列304及環306描 方法900包括將一前置節點插入一路由表 9 0 1 )，該前置節點在一有序鏈結串列之第 目前節點之前。舉例而言，具有識別碼5 0 入至該路由表中，作為具有識別碼64 (目 節點。沿順時針方向3 2 1 (從有序鏈結串 36 200803303 列304之A端向該有序鏈結串列304之B端）移動， 識別碼5 0之節點位於具有識別碼64之節點之前。插 前置節點可以在該目前節點及該前置節點之間建立一 夥伴關係，使目前節點成為前置節點之一夥伴，該前 點成為該目前節點之一夥伴。 方法 900包括將一後續節點插入一路由表中之 (操作902 )，該後續節點位於在一有序鏈結串列之第 向上位於該目前節點之後。舉例而言，具有識別碼76 點可以被插入至該路由表中，作為具有識別碼6 4 (目 點）之後續節點。沿一逆時針方向3 22移動，具有識 76之節點位於具有識別碼64之節點之後。插入一後 點可以在該目前節點及該後續節點之間建立一對稱夥 係，使目前節點成為後續節點之一夥伴，該後續節點 該目前節點之一夥伴。 方法900包括向該路由表中插入適當鄰域節點之 (操作903 )，根據一鄰域範圍及鄰域大小，在該第一 及一第二相反方向等兩個方向上，可由該有序鏈結串 識別該等鄰域節點。舉例而言，具有識別碼 83、76 及 46之節點可以被插入至該路由表中，作為具有識 64 (目前節點）之鄰域節點。根據鄰域範圍20及鄰域 4，具有識別碼8 3及76之節點可以在順時針方向3 2 1 識別，具有識別碼5 0及46之節點可以在逆時針方向 (從該有序鏈結串列304之B端向有序鏈結串列304 端移動）被識別。在某些環境中有可能未識別適合的 具有 入一 對稱 置節 操作 一方 之節 前節 別碼 續節 伴關 成為 操作 方向 列中 '50 別碼 大小 上被 322 之A 鄰域 37

200803303 π姑1以 間建立一對稱夥伴 -目則節 1承’使目 伴，該鄰域節點成Α 卩點成 战為該目前節點之一 ρ 方法900包括向該 夥1 / , $表中拖入、益 (操作904 )，根據該聯 、 烤绝體基礎建設之 該第一方向及第二方向上 J上識別來自 節點，該等路由節點代表該 μ有 、第一 結串列的對數數基。舉例一 一 ^ ^ ，具有識 46 、 50 、 64 ' 64 、 64 、 64 、 64 之節點可以被插入該路由表中 农甲，作為具有 點的路由節點。根據數基2及域大小8， 64 、 76 、 83 、 98 、 135 及 200 之銘抓 1 心即點可在 別，具有識別碼64、64、50、46、3〇、2 以在方向322上被識別。如在環3〇6内所 點表示該有序鏈結串列3 0 4在順時針方向 向3 22兩個方向上之對數索引。插入一路 目前節點及該路由節點之間建立一對稱夥 節點成為路由節點之一夥伴’該路由節點 之一夥伴。 第7圖說明用於填充’節點路由表之 流程圖，該方法考慮了鄰近準則。下文針 描述方法700。方法7〇0包括以下操作： 與之每一階層式分割路由環，向一路由表 點（操作70 1 )。在目前節點所參與之每一 及該鄰域節點之 鄰域節點之一夥 〇 路由節點之操作 :基與域大小’在 鏈結串列之路由 方向中之有序鏈 碼 200、2、30、 98、135 及 200 識別碼 64之節 具有識別碼6 4、 方向321上被識 及200之節點可 示’該荨路由節 3 2 1及逆時針方 由郎點可以在該 伴關係，使目前 成為該目前節點 方法700的實例 對第5圖中之環 對於目前節點參 申插入一前置節 階層式分割路由 38 200803303 環中，每一前置節點在一第一方向（例如，順時針方向） 上位於目前節點之前。該等階層式分割路由環被根據相應 鄰近準則分割，且包含一雙向鏈結串列之至少部分子集（可 能包含整個雙向鏈結串列）。舉例而言，一指定節點可能參 與根環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及 5 42之每一環中為該指定節點識別鄰域節點。 方法700包括以下操作：對於目前節點參與之每一階 層式分割路由環，向該路由表中插入適當路由節點（操作 704)。舉例而言，從環 501 及子環 511、522、523、531 及542之每一環中為該指定節點識別路由節點。 39 200803303 在一些具體實施例中，對於除節點γ所參j 使用別名之具體實施例中為多個葉環）之外的 d，插入適當路由節點。可根據以下運算式插入 點： 如果 Y.sd.id < Y.id + b1 < Y.sd +卜id 為真，j 或者

如果 Y.pd.id < Y.id - bi < Y.pd+卜id 為真，J 如果在上一步驟中未識別一環，則使用葉 環5 01 )作為環d。現在，環d就是節點Y應 找最接近z之路由移伴的鄰近環。 第 10 圖說明用於向一目的節點路由一 1000的實例流程圖。將參考第3圖中之有序凝 及環306描述該方法1000。方法1000包括一 收一訊息以及一指示目的之數字的操作（操作 例而言，具有識別碼 64之節點可以接收一指 之訊息。 方法 1 000包括一確定該接收節點至少符 件之一的操作（操作 1 002 ):該接收節點在數 之距離遠於一相應前置節點，該接收節點在數 之距離遠於一相應後續節點。舉例而言，在方 識別碼64距離目的212遠於識別碼50，在方 識別碼64距離目的2 1 2遠於識別碼76。方法 確定該目標不屬於與該接收節點所對應之節 (操作1 003 )。舉例而言，識別碼64之節點可4 咚之葉環（在 每一鄰近環 適當路由節 的使用環d ; i>J使用環d。 環（例如， 當在其中尋 訊息之方法 I結串列304 接收節點接 1001 ) 〇 舉 示目標 212 合以下兩條 字上與目的 字上與目的 向322中， 向321上， 1 000包含一 點鄰域集中 【定目的212 40 200803303 不屬於83、76、50及46之鄰域集。 方法 1 000包括從一對應於接收節點之路由表 中間節點之操作（操作 1 004 )，該中間節點在數值 該目的近於相應路由表中的其他路由節點。舉例而 有識別碼64之節點可確定具有識別碼200之路由節 值上距離目的212要近於其他路由節點。方法1000 該中間節點傳輸該訊息之操作（操作 1 005 )。舉例 具有識別碼64之節點可以向具有識別碼200之節點 息。 第 11圖說明用於根據鄰近準則向一目的節點 訊息之方法11 0 0的實例流程圖。下文針對第4圖 圖中之環描述方法1100。方法1100包括一接收節 一訊息以及一指示目的之數字和一鄰近準則的操作 11 0 1 )。該鄰近準則定義一或多個節點類。該接收節 一目前節點類之一部分而接收該訊息，該目前節點 據鄰近準則選自該等一或多個節點類中。舉例而言 識別碼1 72之節點可以接收一訊息（其指示一目的 以及鄰近準則（其指示該目的節點係由環40 1所表 一部分）。具有識別碼1 72之節點作為環404之一部 收該訊息。 方法 11 00包括一確定該接收節點至少符合以 件之一的操作（操作 11 02 ):在所選擇之節點類中 收節點在數字上與目的之距離遠於一相應前置節點 收節點在數字上與目的之距離遠於一相應後續節點 中識別 上距離 言，具 點在數 包括向 而言， 傳送訊 路由一 與第5 點接收 (操作 點作為 類係根 ，具有 201 ) 示類之 分可接 下兩條 ，該接 ，該接 。舉例 41 200803303 而言，在環404内，在順時針方向上，具有識別碼172之 節點距離目的20 1遠於具有識別碼丨74之節點，在逆時針 方向上，距離目的20 1遠於具有識別碼i 5 3之節點。

方法1100包括一操作（操作11〇3 )，其對於由鄰近準 則定義之一或多個節點類中的任意一類，確定該目的不在 該接收節點之鄰域節點集中。舉例而言，具有識別碼172 之節點可以確定目的201不在環4〇4或環4〇1中之相應鄰 域集中。 方法1100包括從該接收節點之路由表中識別中間節 點之操作（操作1104)，該中間節點在數值上距離該目標 近於路由表中的其他路由節點。舉例而言，具有識別碼172 之節點可確定具有識料194之路由節點在數值上距離目 的要近於環404中之其他路由節點。方法t⑽包括 向該中間節點傳輸該訊息之操作（操作U()5)。舉例而言， 具有識別石馬172之節點可以向具有識別碼！94之節點傳送 戶:接收到之訊息。具有她172之節點可以向具有識別 碼1 94之節點發送所接收到之訊氡， & 〜 乂遵從一先前定義之 一近準則部分有序串列。 即點194在環404中可以與目的％儘可能接近。因 可以僅將鄰近準則放鬆至恰能在下—步中於環4〇1中 =步向目的路由。即’由於在環“04上不能再進一步向 %進，所以路由從環彻轉移到環術。或者，具有 = =2G1之節點位於具有識別碼194之節點在環401中 錢内’導致不能進一步路由。…在-些具體實施 42 200803303 例中’放鬆鄰近準則以到達下一個更高環，就足以導致進 一步路由。 但疋，在其他具體實施例中，將逐步放鬆鄰近準則， 導致向下一更雨環之傳輸，這一過程將一直持續，直到可 以發生進一步路由為止（或者到達根環為止）。即，在可 以進行進一步路由過程之前，會發生複數個向更高環之 轉移。舉例而s ’現在參考第5圖，在環531不能再進一 步進行路由過程時，可以放鬆鄰近準則，以足以轉移到環 5 11，甚至轉移到根環5 0 1。 節點階段 一參與聯合體基礎建設之節點可工作於不同工作階 段。一節點之有效階段值可被定義為一有序集合之成員。 舉例而言 ’ {NodeId}.{InstanceIds}.{Phase Value [Phase- State Values: Inserting， Syncing， Routing，

Operating] 〇 [Phase·Unknown Indication: phase known at time of transmission, phase unknown at time of transmission]}定義一可能有序集，其代表在一聯合體基礎 建設中一既定節點之階段空間。一節點實例可轉移（或前 進）至所有節點階段狀態，依次為從Inserting至Syncing， 至Routing ,至Operating。此外，在某些具體實施例中， 一節點實例可被組態，從而防止該節點實例轉移至先前節 點階段狀態。在某些具體實施例中，一節點每次上升時， 該節點前進其實例識別碼。 舉例而言，一節點實例可防止由 Routing轉移回 43 200803303

Synching (或轉移回Inserting )，等等。相應地，在一些具 體實施例中，如果吾人已知一既定節點實例（例如，由 (Nodeld，Instanceld)確定）已經前進至一特定節點階段狀 態（例如，Operating )，則吾人亦知曉該既定節點實例不太 可能返回至一先前節點階段狀態（例如，返回Routing、 Syncing或Inserting )，在某些具體實施例中的確不會返回 一先前節點階段狀態。因此，該特定節點階段狀態之前的 節點狀態中的任意節點實例非常有可能是一新的節點實體 (或已經前進之節點實例）。 在一些具體實施例中，階段資訊與相應實例識別碼（其 隨者節點之上升而前進）被一起傳送。因此，有可能確定 同一實例之較小節點階段狀態比較舊。另外，如果已知一 較新節點實例（處於任意階段狀態值），則認為有關較舊實 例的任何資訊均已過期。 有時，節點可能重新啟動或相互失去通信，例如，在 第一次啟動時、完全脫離時，或者由於非正常終止（損毁）。 因此’處於任意節點階段狀態之節點有可能重新啟動或失 去與其他節點之通信。舉例而言，一損毁可能導致路由 (Routing )階段狀態之節點重新啟動。在重新啟動或失 去通信期間，無法確定一節點處於哪一節點階段狀態。相 應地’當一節點正在重新啟動或者失去與一節點之通信 時’可以設定[Phase.Unknown Indication]，以指示目前不 知曉該節點之階段狀態。但是，一節點之任意先前已表示 及/或已偵測階段狀態可被維持，不會丟失。 44 200803303

[Phase.Unknown Indication]可用於指示在傳輸一階 段狀態值時（例如，未被設定pahse.unknown之階段值）， 一階段狀態是否已知，或者在該階段狀態值被傳輸時（已 設定pahse.unknown的階段值），一階段狀態是否是先前 表示之階段狀態或者階段狀態未知。因此，一節點之階段 (其階段值）可使用一階段狀態值及一 phase.unknown指 示來表明。 加入通訊協定 有時，節點可加入和脫離現有聯合體。該等節點可實 施用於加入及脫離聯合體的適當通訊協定。例如，一節點 可實施Join()函數，以成為一現有聯合體之部分。一實施 J〇in()函數之節點在到達最終操作階段狀態之前可經歷所 有三個有序階段狀態：一插入階段狀態、一同步階段狀態 及一路由階段狀態。在其他具體實施例中，這些特定有序 階段狀態可能不存在，可定義其他階段狀態。第丨2 A圖說 明在一聯合體基礎建設内建立成員關係之一節點實例。第 1 2B圖說明在一聯合體基礎建内交換訊息之節點的實例。 插入階段：一節點γ藉由發出一加入訊息（其至少包 括其節點識別碼且指示加入該聯合體之操作）來進入此階 段狀態。一加入訊息可以是由一新加入節點（節點γ)傳 达之路由訊息，其目的屬性被設定為該新加入節點之識 別。在此階段狀態中，一新加入.節點被插入其在該聯合體 内之前置節點與後續節點之間。該插入階段狀態可根據以 下演算法實施（所有運算均以bn為模進行計算）： 45 200803303 IP 1。Y識別一現有節點，該節點已經是一最低環之一 部分，該加入節點希望從該最低環加入該聯合體。可使用 DHCP及/或網域名稱系統及/或WS-Discovery或一（潛在 習知）常數統計組態或動態搜尋該節點。假定此現有聯合 體節點為E。 IP2。Y 叫用 E.RouteNumerically(Y，joinMsg)，以確 定節點X，其識別碼的數值在節點Y所參與之所有鄰近 環中最接近於 Y.id。其可包括向多個節點路由一加入訊 息。 IP 3。確定該數字後續節點（s )與前置節點（p )。（注 意，進行以下接收所需要之資料可能在該加入訊息及其回 應中攜帶。因此，不需要附加往返。） 情況 1 ·· X.id>Y.id

Y.s = X，Υ·ρ = X.p，X.p.s = Y 及 X.p = Y 情況 2 : X.id<Y.id

Υ·ρ = X、Y.s = X.s、X.s.p = Y 及 X.s = Y 回應該加入訊息，節點X (處理該加入訊息之節點） 可將一加入回應訊息發回節點Υ。該加入訊息可指示節點 Υ之前置節點（γ·ρ )與後續節點（Υ· S )。節點Υ可接收 該加入回應訊息且處理該加入回應資訊，以知曉其前置節 點及後續節點。在處理該加入回應訊息之後，節點Υ可以 成為該聯合體中之一弱路由參與節點。舉例而言，節點可 以簡單地將發送給自己的訊息轉遞給其後續節點或前置節 點。因此，節點Υ被插入到該聯合體基礎建設中，但路由 46 200803303 將 點 送 同 其 含 加 階 要 例 訊 ， 息 負 可 用 域 料 處 同 表及鄰域表未被填充。在到達此點之前，節點Y將藉由 一狀態訊息返回給向其發送訊息之其他節點，指示該節 Υ之活躍度狀態處於一插入階段狀態，從而要求該等發 節點重新定向經由一不同節點發送給自己之訊息。 一般來說，節點有時可交換同步要求及回應訊息。 步要求及同步回應訊息可包括從該發送者角度所觀察之 他節點的活躍度資訊（例如，標頭）。鄰域狀態也可被包 在同步要求與回應訊息中，使得鄰域内的應用層暸解另 層之狀態。交換同步要求及回應訊息之時機實例是在一 入節點的同步階段狀態期間。但是，也可以在其他操作 段狀態（例如，在Operating階段狀態）期間交換同步 求及回應訊息。 第16圖說明一訊息模型及相關處理模型之實 16 00。如第16圖所述，一節點可傳送及接收同步要求 息。舉例而言，可在應用層1 6 5 1由一新插入節點（例如 第12B圖中具有識別碼144之節點）中接收同步要求訊 1601。應用資料16〇2 (例如，命名空間訂閱）可被揹 (Piggybacked)於同步要求訊息16〇1中。功能層1651 以向應用層1 652通知包含於同步要求訊息中之任意應 負料。舉例而言，功能層i 6 5 1可向應用層1 6 5 2叫用鄰 狀態同步事件1 603，包括應用資料16〇2。包括應用資 1 607之同步要求1631也可被發送到另一節點，該節點 理同步要求1631之方式類似於在處理模型1600中處理 步要求1601之方式。 47 200803303 回應一些功能層事件（例如，同步要求訊息1 60 1、 步回應訊息1 64 1，或偵測訊息1 6 1 2 )，功能層1 65 1可以 用應用層1652中之鄰域狀態要求功能1 604。鄰域狀態 求1 604係對應用層之一要求，以獲得需要在該鄰域内傳 之狀態。回應鄰域狀態要求1 604，應用層1 652可向功 層1651提供鄰域狀態1606，包括可選應用資料1607。 者，應用層1652可以作為對一些應用層事件之回應， 送鄰域狀態1 6 0 6，包括可選應用資料1 6 0 7。使用類似 上述之機制，功能層1 65 1可發送同步回應訊息1 608， 括可選應用資料1 607，以傳播應用層鄰域狀態。 同步階段：在處理一加入回應訊息之後，節點Y由 插入階段狀態轉移至同步（syncing )階段狀態。在該同 階段狀態中，新插入節點Y與鄰域内之節點同步資訊。 常，節點Y可以向在插入階段狀態中識別之至少前置節 及後續節點發送同步訊息。此等處理該等同步訊息之節 可以返回同步回應訊息，其指示此等處理節點之相應鄰 及路由夥伴節點。在一更具體之實例中，該同步階段狀 可根據以下演算法實施（所有運算均以bn為模進行計算 SP1。在節點 γ 參與之每一鄰近環内，聯 Neighborhood(Y.s) 及 Neighborhood( Υ·ρ) 計 Neighborhood(Y)。該聯合計算可採用以下方式完成： (Sj，.··，sb s，p，pi，…，pk)使得 Sj.s.id > (Y.id + u/2) 2 v/2-1，pk.p.id <(Y.id-u/2)及 k2v/2-l SP2。簡單地參考第16圖，經由一鄰域狀態要求（ 同 叫 要 播 能 或 發 於 包 步 通 點 點 域 態 ): 合 算 ，j 例 48 200803303 如，鄰域狀態要求）1 604查詢Y之本機應用層（例如 用層 1 6 5 2 )，以獲得可選專用鄰域資料（例如，專用 1607)。 SP3、向至少該鄰近後續節點及前置節點傳送同 息，包括從Υ之角度觀察，每一鄰近鄰域及路由夥伴 之至少活躍度狀態資訊。可經由SP2存取之任意可用 鄰域資料（例如，應用資料1 607 )包含於該同步要求 中。 SP3。Υ從該等處理在SP2中所發送同步訊息之 處接收同步回應訊息。舉例而言，節點Υ可與其所計 域内之一或多個節點交換同步訊息（要求/回應）。在 點Υ之鄰域節點之中至少一節點（也可能是全部節點 換同步訊息之後，所計算之鄰域節點可交換其他訊息 傳播同步資料。一同步訊息（要求或回應）可以是由 點發送之非路由訊息，用於與一目標節點（該目標節 如位於該節點鄰域内）主動同步其資料。 SP4。當SP3中之同步回應訊息被接收聘（例如 步回應訊息 1 64 1 )，這些被接收同步回應訊息中出現 意可選專用鄰域資料（例如，應用資料1 622 )可被經 域狀態同步事件1 603提供至Υ之應用層1 652。 作為同步階段狀態之一部分，鄰近後續節點（例 Y.s )及前置節點（Υ·ρ )可與該新插入節點（例如， 交換其路由表。注意，可藉由發送同步回應訊息來回 收同步訊息。同步回應訊息攜帶之資料類似於同步訊 ，應 資料 步訊 節點 專用 1631 節點 算鄰 與節 )交 ，以 ArAr 一即 點例 ，同 之任 由鄰 如， Υ) 應接 息， 49 200803303 只是其係從回應節點之角度來觀察。同步訊息與同 訊息均攜帶（或措負）應用資料。因此，在同步階 期間，應用資料可以在節點之間被傳播。當同步階 完成時，該節點可處理以其為目的之訊息，而不是 將該等訊息轉遞至一後續節點或前置節點。但是， 仍然可以被看作一弱路由參與節點，因為其路由表 充。 路由階段：在同步階段狀態完成之後，一節點 路由階段狀態。在路由階段狀態中，新同步之節點< 節點Y )計算其路由節點。該路由階段狀態可根據 算法實施（所有運算均以bn為模進行計算）： RP 1。如果該路由階段狀態係作為該平衡程序 對此進行解釋）之一部分被執行，請確保該後續節j 及前置節點（Υ·ρ )在該節點Y所參與之所有鄰近 是活動的。如果兩節點有任一節點不是活動狀態， 考慮環中之鄰域節點中選擇下一最佳後續節點及 點’以代替有故障節點。 RP2。對於 lSiSn-1

RP2a。計算 z = Y.id ± V RP2b。如果環d不是最具體鄰近環，尋找節點 與之鄰近環d，其滿足以下條件：Y.sd.id < Y.id Y.s“Md 或 Y.Pd.id < Y.id 6' < Y.pcm.id。否貝ij ， 成為最具體鄰近環。環d就是節點Y應當在其中尋 近2之路由夥伴的鄰近環。設Q為是Y.sd.r±i和 步回應 段狀態 段狀態 簡單地 該節點 未被填 轉換為 例如， 以下演 (後文 M Y.s) 環是都 請在所 前置節 Υ所參 + < 使環d 找最接 Υ· P d·Γ土 i 50 200803303 之間在數值上最接近z之節點。如果丨Q id_z丨在bi的可組態 百刀比範圍内（通常為20% )，則簡單地使Y.r±i = Q。如果 Q]d比（Y.Sd.ld ± bi)或（γ pd士 更接近z，則意味 著與Y.Sd或Y.Pd相比，節點Y是鄰近環d中節點Q的 更佳夥伴路由節點。因此，向節點Q發送updateMsg，如 果其尚未被發送，則提供i和節點γ作為參數，使節點Q 可以將節點Υ作為其在rj之夥伴路由節點。 RP2c。如果此階段狀態被作為該平衡程序之一部分執 行，且如果 Y.Sd r±i id = = Y pd.r±i id，則在（Y h id士bi)與 (Y.Pd.idib1)之間的數值範圍内僅存在一節點。該節點係由 該後續節點（或前置節點）之路由節點r±i所指向之節點。 因此’只需要使YwrY.Sd.hi.i。 RP2d否則’精由對於卽點Q叫用RouteProximally (鄰近準則被設定為環d之節點），計算該路由夥伴Y.r土卜 此意味著 Y.r±i = Q.R〇uteProximally(z，UpdateMsg，d)。 RP3。此時，節點γ不僅可以處理以其為目的之訊息， 也可路由訊息。 RP4。如果還沒有為夥伴路由節點之端點識別碼訂閱 由應用層發送之活躍度通知事件，則進行此操作。此外， 撤銷以前使用應用層為已經不再是夥伴路由節點之節點建 立之活躍度事件訂閱。舉例而言，訂閱及/或撤銷要求可以 被向上傳輸至一應用層（例如，應用層1 2 1 ),其為一相應 應用程式（例如，一命名空間應用程式）實施公佈-訂閱子 邏輯。在應用層接收到後續專用活躍度訊息（例如，其係 51 200803303 由命名空間訂閱得到）時，通知（事件）可以向下傳送到 其他較低層（例如，其他較低層1 3 1 )進行處理。 第17圖說明許多可發生於一功能層1751及一應用層 1 7 5 2之間的活躍度互動之實例。如第1 7圖所示，端點例 如為表示各種節點之公共/訂閱主題（例如，由URL或URI 表示），且例如可以為聯合體節點。可以從功能層1 75 1向 應用層1 752叫用“訂閱活躍度事件” 1 70 1，以訂閱一活躍 度事件（例如，用以公佈/訂閱主題）。可以從功能層1 75 1 向應用層1 752叫用“撤銷活躍度訂閱” 1702,以撤銷對一 活躍度事件之訂閱。可以由應用層1752向功能層1751發 送“端點當機” 1 703，以指示一端點可能當機，且向功能 層1751提示一可選替代端點。“端點當機事件” 1 703可 被根據一先前訂閱（例如，“訂閱活躍度事件” 1 70 1 )異 步發送。 可由功能層 1751向應用層 1 752叫用“節點當機” 1 704，以指示功能層1 75 1 (或某一其他更低層）已經偵測 到一故障節點，且可根據需要為應用層1 752提供一替代節 點。應用層1 752可在以後向其他關注方傳播：偵測到一可 能故障節點。在功能層1 75 1或某一其他較低層偵測到一可 能故障節點之任意時間，“節點當機事件” 1 704可被異步 發送。當應用層1 7 5 2偵測到一節點當機時（例如，由節點 當機事件1704或由某一其他帶外機制），可以從應用層 1 752向功能層1751叫用“發送活躍度事件” 1 706。 “發 送活躍度事件” 1 706可導致功能層1751發送一活躍度訊 52

200803303 息。在應用層1 7 5 2俏 偵測到一節點當機且 已建立之訂閱（緩ώ ^ 、 由盯閱活躍度） 躍度事件” 1706也 - T被異步叫用。 因此，在某些 ，、體貝施例中，功能戶 用。舉例而言，" 增丄0 1可向應用層 節點中之興趣（例如，在 係向上或向下之特 1 752可以為有關讀指定節點之通知公式^ 後再次利用功能層175卜以將該公式=旬 合體節點中之適當相應應用層1 752實例 聯合體節點中之應用層1 752實施一 性，則功能層1751可向管理該指定節點 閱管理者路由該訂閱，該公佈/訂閱管理者 體節點之應用層1 752的至少一每 口丨刀實施 1751被用於功能層1751所導致產生之訂 制也可被用於取消訂閲，成者扣—‘ J m X有知不在該指 趣0 操作階段··在該路由階段狀態完成之 至操作階段狀態。該節點可維持一操作階 當機（例如，重新啟動）為止。在操作階 點可不時向路由夥伴發送更新訊息。更新 及更新回應）可包括該發送節點（例如， 有鄰近鄰域）之鄰域節點活躍度資訊。此 訊還可包括發送者之活躍度資訊。更新訊 發出之路由節點，以周期性更新其路由夥 -取決於任意先前 ，時間’ “發送活 1 7 5 1被遞迴使 1752指示一指定 定節點）。應用層 匕一專用訂閱，然 •閱通信至其他聯 。舉例而言，如果 空間公佈/訂閱特 之通知的公佈/訂 被作為相關聯合 。相應地，功能層 閱。類似遞迴機 定節點不再有興 後，一節點轉移 段狀態’直到其 段狀態中，該節 訊息（更新要求 對於感興趣之所 被發送活躍度資 息可以是由節點 伴節點。應用資 53 200803303 料可被揹負於更新訊息，使應用資料可在路由夥伴更 間被傳播。該訊息目的被設定為在期望路由索引之正 由夥伴的識別。此訊息之MessagelD屬性被指派一應 號’使處理此訊息之節點能夠確定最新訊息，且此訊 鄰近路由。 —接收更新訊息之節點可以回應一更新回應訊息 更新回應訊息攜帶之資料與更新訊息攜帶之資料相同 是該資料是從回應節點之角度觀察的。藉由交換更新 與更新回應訊息，節點可以交換路由資訊。有時，操 點可更新路由夥伴。 有時，操作節點也可發送偵測訊息（例如，偵測 611) 偵測訊息是由一節點發送之單向訊 以周期宣佈其存在，且在其鄰域内傳播有關其鄰域/路 點之資訊及複製（例如，揹負（Piggybacked))應用資 、起始即點可向其一或多個直接前置鄰域節點及 鄰域即點發送一偵測訊息。因此，根據該偵測分佈 (P被發送摘測訊息之節點），與起始節點有關之資 傳至％之其他即點，該環位於該起始節點之鄰域 舉〇而^該起始節點僅向其直接前置節點及後續節 送^一彳貞測訊息，該彳自：目1丨4 . 飞價測訊息由該起始節點之位置（節 別碼）沿該環在兩個方向上朝向該起始節點之鄰域邊 外傳播《者’該起始節點在其前置節點方向及後續 方σ t向其4域内之所有帛η個節點發送一偵測訊息 每接收一偵測訊息之節點從一鄰域範圍之角度 新期 確路 用序 息被 9 只 訊息 作節 訊息 息， 由節 料。 後續 型樣 訊被 内。 點發 點識 緣向 節點 〇 檢查 54 200803303 其在該起始節點之興趣。如果不被關 饭關，主，其丟棄該偵測訊 息。如果被關注，則其處理該偵測訊* 4 Λ恩，而且如此轉遞被 限制到該起始節點之鄰域内，則根摅i ⑴很據其指定偵測型樣轉遞

該偵測訊息。舉例而言，在處理一偵測訊息之後，如果該 發送及起始節點位於其前置節點集合中，_該#測訊息 轉發到至少其後續節點，如果該發送及起始節點位於其後 續節點集合中，則將該偵測訊息轉遞到至少其前置節點。

因此，當該訊息到達該起始節點周圍之鄰域節點邊緣 時’該等偵測訊息之向外傳播停止。偵測訊息之Message ID 屬性被指派一應用序號，使處理此訊息之節點可以確定來 自該起始節點之最新訊息，且避免重複處理及不必要之轉 遞。 再次參考第1 6圖，可以在功能層1 65 1從一鄰域節點 接收偵測訊息1 6 0 9。應用資料1 6 1 2 (例如，命名空間訂閱） 可被揹負於偵測訊息1 609中。功能層i 65 i可以向應用層 1 6 5 2通知包含於偵測訊息中之任意應用資料。類似地，功 能層1651可以向應用層1652通知包含於同步要求訊息中 之任意應用資料。這兩種傳輸情況均可經由向應用層丨6 5 2 發送一鄰域狀態同步事件1 6 0 3(包括應用資料！ 6 1 2 )完成。 回應某一功能層事件（例如，所接收之偵測訊息 1609)，功能層1651可向應用層1652發送鄰域狀態要求 16 04。鄰域狀態要求1 604在應用層1 652上被叫用，以獲 得需要視情況在該鄰域内傳播之狀態。回應鄰域狀態要求 16 04，應用層1652可向功能層1651返回鄰域狀態1606, 55 200803303 包括可選應用資料1607。功能層1651可發送偵測（ping) 訊息1 6 11 (包括可選應用資料1 607 )，以傳播鄰域節點及 路由夥伴節點活躍度資訊，以及可選應用層鄰域狀態。功 能層 1651還可發送同步回應 1 608，包括可選應用資料 1607，以傳播應用狀態。 脫離通訊協定 當一節點適於脫離一聯合體時，該節點可實施一 Depart功能，以從該聯合體中被完美去除。一節點藉由向 其直接鄰近前置節點及後續節點（可能還有相同鄰近鄰域 中之其他節點）來脫離一現有聯合體。因此，根據該脫離 分佈型樣（即，被發送脫離訊息之節點），與脫離節點有關 之資訊被傳播至一環之其他節點，該環位於該脫離節點之 鄰域内。一脫離訊息是由一正在脫離之節點發出的單向訊 息，以向其鄰近鄰域中至少一鄰域中之一或多個其他節點 通知其正準備脫離。該脫離節點以一種類似於偵測訊息之 傳播的方式傳播該脫離訊息（例如，在其鄰域内）。舉例而 言，具有識別碼3 0之節點可以向具有識別碼1 7及4 0之節 點傳送脫離訊息1 2 1 9。具有識別碼3 0之節點於是從一既 定鄰近環之角度將其自身從該聯合體基礎建設中去除。注 意，一節點有可能將其自身從一鄰近鄰域中去除，但沒有 從其所屬之其他鄰域中去除。 因為在具有識別碼3 0之節點被去除之後，具有識別碼 1 7及40之節點（即該等前置節點及後續節點）可能是最 接近識別碼3 0之節點，所以具有識別碼1 7及4 0之節點知 56 200803303 曉具有識別碼3 0之節點脫離。因此，其他被傳送到識別碼 3 0之節點的訊息被適當地在具有識別碼1 7及4 〇之節點声 理。具有識別碼17及40之節點可以向環1206上之其他節 點通知有關識別碼3 0之節點的脫離。當不存在具有識別焉 30之節點時，具有識別碼1 7及40之節點也重新計算前置 指標及後續指標，可能相互指向對方。 一脫離訊息之MessagelD屬性被指派之應用序列識別 碼與偵測訊息之應用序列識別碼相同，使處理該脫離气阜、 之節點能夠確定由一起始節點所發送一系列偵測及脫離= 息中的最新訊息。從一聯合體鄰近環的完美脫離是可選 的，但鼓勵這樣做。但是，該聯合體之設計使得在有節點 突然離開時能夠自愈（s e 1 f - h e a 1 )。 ° 活躍度 在-聯合體生存期間，節點可交換活躍度資訊，以維 持該聯命體。活躍度資訊採用“活躍度訊息標頭，，之方式 幾乎可以包含於任—在聯合體内交換之訊息中。舉例= 言，加入訊息、加入回應訊息、同步訊息、同步回應訊息、 更新訊息、更新回應訊息、|用訊息、活躍度訊息及偵'則 訊息均可包含活躍度資訊標頭。當一聯合體節點發送任意 訊息或回應訊息時，該節點可包括供其他節點處理之活躍 度資訊。活躍度資訊可被包含於活躍度訊息之活躍度資訊 標頭中。 指示一節點之活躍度狀態之活躍度資訊可使用以下屬 性表示： 57 200803303 [Node]:確定表示哪一節點之活躍度狀態。可根據進 一步包含[Instance ID]之[Reference Properties]識別一節 [Reference Properties] : WS-定址規格中指定之元素資 訊項。WS-定址定義包含於引用屬性集中之[Instance iD] 引用屬性。

[Instance ID]: —識別一節點之特定實例之數字。一 遞增根計數可用作一節點之實例識別碼。 [Phase]:表示被識別節點之階段。 [Phase-State Value] ·•表示已知被指示節點實例所達到 之最兩階段狀態（插入、同步、路由、操作）。 [Phase.Unknown Indication]，一 指示器，复本一 ^ σσ ，、衣示目前 階段為已知還是未知。 [Freshness]:表示該資訊之新鮮程度，复 又丹取值範圍介 於0至MaxFreshness之間。該值越高，該資如 ^ 坎貝訊越新鮮，〇 表示無資訊，MaxFreshness係一通訊協定定義批 〈㊉數。 [Color]:識別該節點所屬之鄰近等價類 ^ m ^ 兩個具有相 同顏色值之節點總被認為是最接近的，因為它 1門均屬於由 該顏色值所識別之相同等價類。由於更多節 文夕即點加入聯合 體，所以鄰近等價類之數目可隨著時間而增大。 [Weight] ··提供節點容量量度，其取值範園為〇至 MaxWeight。其量測一聯合體節點之期望特 μ主何丨王，例如，大 計算功能、高網路頻寬，及長執行時間。從夥 τ _係之角 度來看，該值越高，其越能符合夥伴之需要。 58 200803303 在一些具體實施例中，在諸如[Origin]及[Sender]訊息 標頭之一更大範圍内傳送一節點之 [Node]及 [Freshness]，如此，在活躍度標頭中包含上述屬性將是重 複的。舉例而言，一訊息之發送者僅傳輸其目前階段、顏 色及重量資訊，而其識別碼、實例識別碼在訊息定址標頭 中被提供，其新鮮度係隱含的。 根據以下定義之”<”二進位關係，活躍度狀態至少是部 分有序的： 當滿足以下條件時，”Ll<L2n為真： 1· ”Ll.[Node]· [Name] == L2.[Node].[Name]n 為 真，並且在有序串列中中執行測試及短路時，下式之一為 真： LI.[Node].[Reference Properties]. [Instance ID] < L2. [Node]. [Reference Properties]. [Instance ID] LI.[Phase.Unknown Indication] ! = true AND L2. [Phase.Unknown Indication] != true AND L 1.[Phase-State] < L2.[Phase-State] LI.[Freshness] < L2.[Freshness] 2· 或者，"Ll.[Color] == L2. [Color]"為真，且在該 有序串列中執行測試且短路時，以下之一為真： LI.[Phase- State] < L2.[Phase- State] LI.[Weight] < L2.[Weight] 此外，當偵測到或懷疑一指定節點已經不可用時（例 如，當機狀態），可向一指定節點發送一活躍度“當機，，訊 59 200803303 息。例如，當一應用層（例如，應用層121)偵測到另一 應用層（例如，應用層123)或一主控另一應用層之節點 當機時，該偵測應用層例如可根據訊息模型及相關處理模 型1 6 0 0及/或1 7 0 0，通知其他較低層（例如，其他較低層 t 1 3 1 ):該節點可能當機。此種通知可能導致其他較低層（例 如，功能層1 6 5 1 )發送活躍度當機訊息。這僅是產生活躍 • 度當機訊息之動因實例。 由於活躍度當機訊息被路由，從而被傳輸至一最接近 該等被懷疑當機之節點的節點’所以’如果一指定節點之 活躍度當機訊息被傳輸回該指定節點，則或者該指定節點 從未當機，或者該指定節點係一不同實例（例如，具有不 同實例識別碼）。另〆方面’如果該活躍度當機訊息被傳輸 至另一節點，其指系該指定節點確實表現為已經當機。相 應地，如果接收該潘躍度▲機訊息之節點將其自身看作位 於該指定節點之鄰近鄰域内，其可以向鄰近鄰域内為該指 定節點發出一脫離訊息（如前所述），且向其應用層（例如， 使用Node Down 1704)指示該指定節點可能當機，該接收 節點係其替代節點。該指定節點之活躍度當機訊息可利用 其目標識別碼集合被鄰近路由至可能當機之節點。 平衡程序 本發明之實施例被設計為允許大量節點在祐R主问〜 甘姐日等間内加 入及脫離該聯合體。如果在該等各節點維護之m^ 无 < 對數搜尋樹 變為不平衡，則網路中之此等變化會導致路由 印把呀。即， 如果一環中一側之節點多於另一側之節點。Λw η 馬促進最佳路 60 200803303 聯合體之節點執行該 由效率，在滿足特定準則時，參與一 平衡程序。 ’任意節點可執 而獲得最佳路由 例如，當以下條件中任一條件為真時 行該平衡程序，以確保一平衡路由表，從 效率： 接收到上述被組態數目之活躍度訊_。 $接收到上述最後活躍度訊息之後已經過去' 目之時間。 鄰域已經發生變化’即某些新節點已經㈣，或者某 些現有節點已經脫離。 平衡路由表是-個簡單過程。例如，具有非平衡路由 表之節點可以重新執行加入通訊協定之同步及路由階段狀 當聯合節點非常快速地加入及脫冑，且數量很大時， 在接收到活躍度訊息之後，執行操作Rp2b、及， 2結合ο尋找最接近一數值之路由節點，2)由完美離開 一聯合體之節點所遵循之脫離通信協定，及3)由接收活 躍度訊息之節點所遵循之平衡程序，將會更快速地復原系 統。 狀態訊息 狀態訊息是由一接收節點向一發送節點傳送之非路由 訊息，以通知該發送節點先前向該接收節點轉遞之相關資 訊的路由成功/失敗。第1 8圖說明在一環上之節點間如何 路由訊息之實例，該等訊息構成一要求·回應訊息交換型樣 61 200803303 之部分。一狀態訊息可包括識別原始相關訊息 原始相關訊息之路由狀態將被報告。同樣，狀 於節點之間’以指示該訊息被成功地從一節點 節點。舉例而言，從節點1801向節點1 806路 1811之過程包括經由節點18〇2、18〇3、18〇4>ξ 要求1 8 1 1。相應級聯成功狀態訊息（狀態J 8 1819、1829及1821)可各別由節點1806發送 節點1805發送至1804、由節點1804發送至節 節點1 8 0 3發送到節點丨8 〇 2、由節點1 8 〇 2發送 為對要求1811之回應，可將回應ι816以端對 點1 8 0 7發送至節點1 8 〇丨。回應1 8丨6係可選訊 訊息交換態樣中可能不存在該回應。 第1 3圖說明一節點加入一聯合體基礎建 法1 3 0 0的實例流程圖。將針對第丨2 a圖及第 環1206描述方法13〇〇。方法ι3〇〇包括向一聯 設發出一加入訊息之操作（操作13〇1)。舉例 識別碼1 44之節點可以向包括環丨2〇6之聯合體 送加入訊息1201。方法13〇〇包括從一聯合體 收一加入訊息之操作（操作丨3 〇 8 )。舉例而言， 之聯合體中之一現有節點可接收加入訊息丨2〇 i 方法1300包括向一處理節點路由一加入 (操作1 309 )。該處理節點可能是在路由該加 與聯合體基礎建設中之其他作用節點相比，其 值上更接近於該加入節點之識別碼。舉例而言 之標頭，該 態訊息可用 路由至下一 由要求訊息 l 1 805發送 17 、 1818 、 至1805 、由 點1 803、由 至1 8 0 1。作 端方式由節 息，在單向 设郎點之方 12B圖中之 合體基建建 而言，具有 基礎建設發 基建建設接 包括環1 2 0 6 〇 訊息之操作 入訊息時， 識別碼在數 ，在起始時 62 200803303 於具有識別碼6 4之節點接收加入訊息1 2 0 1 ’將其路由至 具有識別碼1 3 5之節點，且路由至具有識別碼1 5 1之節點。

方法1 3 00包括為該加入節點計算一或多個前置節點 及一或多個後續節點之操作（操作1 3 1 〇 ) ^舉例而言，具 有識別碼1 5 1之節點可以為具有識別碼1 44之節點計算一 直接前置節點及一直接後續節點。在環1 206中，具有識別 碼1 5 1之節點可以計算具有識別碼丨3 5之節點係一直接前 置節點，具有識別碼1 5 1之節點係一直接後續節點。對其 他鄰近環可執行類似計算。 〇 1300包括為該加入節點計算一或多個路由節點 (操作1311)。舉例而言’具有識別碼151之節點 碼…=識別碼144之節點計算路由節點（從具有識別 之節點可= '角度觀察)。在環1206中，具有識別瑪⑸ 有識^:二？）具有識別碼218及40之節點為具 似計算。…點的路由節點。對其他鄰近環可執行類 作（操作⑴”。既定發送—加八訊息之操 該處理節點進行計算後—之目前视圖，藉由 全部前置鄰域、後續鄰域:：：回應：識别該加入節點之 入回應t自 —路由夥伴節點。舉例@ 一 •訊息1202可識別至少且古嫌 牛1J而吕，加 識別碼I 4 d 有5戠別碼1 3 5之節點必 ^ 144之節點的直接& $ μ 又即點係具有 1 5 1之節點Α呈 則置卽點，可以識別具有$ 點為具有識別碼 力；別螞 以識別在農 卽點的直接後續節％ 涔有識別碼i 5丨 丨點，可 即點處為節點識別碼1 44 〈該 63 200803303 新加入節點）所計算之任意路由節點（對於具有識別碼144 之節點）。 方法1300包括從一處理該加入訊息之聯合體基建建 設接收一加入回應訊息之操作（操作1 3 0 2 ) °舉例而言’ 具有識別碼1 4 4之節點可以從具有識別碼1 5 1之節點接收 加入回應訊息1 2 0 2。 方法13 00包括向至少每一該等直接鄰近前置節點及 直接鄰近後續節點發送一同步要求之操作（操作13 3)。 舉例而言，現在參考第12B圖’具有識別碼144之節點可 以向具有識別碼135及151之節點發送同步要求1203。同 步要求1203可以包括具有識別碼144之節點的任意鄰域節 點之識別及具有識別碼1 44之節點的任意路由夥伴之識 具有識別碼13 5及151之節點可以接收同步要求 1 203。作為對接收同步要求1 203之回應，具有識別碼135 及1 5 1之節點可以從相應路由表中識別其鄰域節點及路由 夥伴節點。具有識別碼1 3 5及1 5 1之節點可以在同步回應 1 2 04中包括其被識別鄰域節點及路由夥伴節點之活躍度 資訊，且向具有識別碼144之節點發送同步回應1204。 方法1 3 00包括從該等鄰近前置節點及後續節點中之 每一節點接收一同步回應之操作（操作1 304 )。舉例而言， 具有識別碼1 44之節點可以從具有識別碼1 3 5及1 5 1之節 點接收同步回應訊息1 2 0 4 °同步回應1 2 0 4可包括一聯合 體基礎建設中之環1 206及其他環上的一或多個節點的活 64 200803303 躍度資訊。同步回應12〇4還可為具有識别 別任意預期路由夥伴節點。 方法1 3 00包括計算鄰域節黠之操作 例而言，具有識別碼丨44之節點玎以根相 及1 5 1之節點的鄰域節點之聯合，計算相 根據該加入回應訊息及任意同步回應訊息 計算鄰域節點。 方法1 300包括計算路由節點之操作 例而言，具有識別碼丨44之節點$以從環 算路由節點。可根據該加入回應訊息及任 之一總結視圖，計算路由節點。 方法1300包括與所計算之路由夥伴 點資訊之操作（操作1 3 0 7 )。舉例而言’ 之節點及具有識別碼2丨8之節點（所計算 以交換對應於其各別鄰域節點之狀態資訊 別碼、階段狀態，等等）。此等交換係藉由 至少每一惟一計算之路由夥伴發送（路由 而完成，如在上文之“路由階段狀態”文 從該新加入節點接收此等更新訊息之反應 訊息之郎點將發送相應Update回應訊息 訊息至少包括其自身及其鄰域節點之活躍 方法13〇0還可包括向至少一鄰域節 起始傳播的操作。例如，具有識別碼1 4 4 測訊息中包括所計算之鄰域及路由夥伴節 丨碼144之節點識 (操作1 3 0 5 )。舉 I具有識別碼1 3 5 應鄰域節點。可 之一總結視圖， (操作1 306 )。舉 1 2 0 6之節點中計 意同步回應訊息 交換至少鄰域節 具有識別碼 1 4 4 之路由夥伴）可 (例如，實例識 該新加入節點向 )一 Update 訊息 本中所述。作為 ，處理該Update 。該Update回應 度資訊。 點啟動路由表之 之節點可在一债 點，且向具有識 65 200803303 別碼1 74之節點發送偵測訊息（例如，該等所計算之鄰域 節點之一）。具有識別碼1 74之節點可接收該偵測訊息且利 用在具有識別碼1 44之節點發出的活躍度資訊更新一相應 路由表。具有識別碼1 74之節點還可在第二偵測訊息中包 括其相應路由表，且在將來某一時間向具有識別碼1 44之 節點發送該第二偵測訊息。具有識別碼1 44之節點可接收 該第二偵測訊息，且使用包含於第二偵測訊息中之活躍度 資訊中的節點（即在具有識別碼1 74之路由表中之節點） 更新其相應路由表。具有識別碼1 44之節點可以用環1 206 中之其他鄰域節點重複發送偵測訊息。 應理解，當一新加入節點加入一聯合體時，該新加入 節點也許不能找到一現有聯合體成員，從而變成惟一成 員。因此，可能不存在指派給該新加入節點之前置節點、 後續節點或鄰域節點。相應地，該新加入節點在所有情況 下被對映為最佳路由夥伴。 此外，儘管已經針對一單一環（環1 2 0 6 )描述了方法 1 3 00，但應理解，在一些具體實施例中，原本加入一環之 節點亦可加入一或多個其他環。舉例而言，再次簡要參考 第5圖，原本加入環551之節點也可加入環543、531、522、 5 11及5 0 1。因此，方法1 3 0 0可以被實施，以加入複數個 環。在其他具體實施例中，在加入複數個環中時，方法1 3 00 中之一些或全部操作可被重複。舉例而言，再次參考第5 圖，當一節點加入環5 5 1及環5 1 4 (例如，別名）兩環時， 方法1 3 0 0之一或多個操作可被重複。在任意事件中，一加 66 200803303 入節點識別碼可被存取且用於識別一有序鏈結串列中之 入節點，以及該加入節點將參與之相應階層式分割子 列。一接收節點被從該有序鏈結_列及每一分割子串列 識別。該加入訊息被路由至該有序鏈結串列及每一分割 串列之處理節點（例如，根據識別碼）。一加入回應被從 有序鏈結串列及每一分割子串列中接收。 第1 4圖說明一節點維護在一聯合體基礎建設之成 關係之方法1400的實例流程圖。將參考環1206描述該 法1400。方法1400包括向一鄰域節點發送一第一偵測 息之操作（操作 1 40 1 )。第一偵測訊息指示一發送該第 偵測訊息之目前節點係該鄰域節點之鄰域。該第一偵測 息也可包括該目前節點之路由夥伴及鄰域節點之狀態。 例而言，具有識別碼1 44之節點可以向具有識別碼1 5 1 節點傳送一偵測訊息。在接收到該第一偵測訊息時，具 識別碼1 5 1之節點瞭解到具有識別碼1 44之節點係具有 別碼1 5 1之節點的鄰近節點。作為這一操作之副作用， 點151也可搜尋來自節點144之更新活躍度資訊（對於 1206之其他節點）。 根據（例如）與一鄰近環（該偵測訊息被發送至該 近環）相關之組態狀態，以一指定頻率周期重複偵測訊J 該頻率可根據該組態狀態變化。舉例而言，一廣域網路 指定偵測頻率可以不同於一區域網路之指定頻率。也可 據一偵測分佈型樣發送偵測訊息。一起始節點之偵測分 型樣可以包括在一環之兩個方向上向鄰域節點發送之偵 加 串 中 子 該 員 方 訊 訊 舉 之 有 識 節 環 鄰 〇 之 根 佈 測 67 200803303 訊息。舉例而言，具有識別碼144之節 碼1 3 5之節點的方向上以及在具有識別 向上發送偵測訊息。偵測分佈型樣及頻 環發生變化。 方法1400包括從該鄰域節點接受 操作（操作1 4 〇 2 )。該第二偵測訊息向 示發出該第二偵測訊息之鄰域節點係該 點。該第二偵測訊息也可包括該發起鄰 及鄰域節點之狀態。舉例而言，具有識 以向具有識別碼1 44之節點傳送一第二 到該第二偵測訊息時，具有識別碼1 44 識別碼1 5 1之節點係具有識別碼1 4 4之 該第二偵測訊息亦可包括環1 2 0 6上其 訊。因此，一般來說，偵測訊息可在一 用於維持鄰域成員關係（對於每一鄰近 在該聯合體内之節點的近似公共鄰域視 一被接收之偵測訊息可被周期性Η 近鄰域（由該起始節點發送之偵測訊息 鄰域）内之其他節點。也可根據一偵測 遞之偵測訊息。一轉遞節點之偵測分佈 遠離一起始節點之方向上向鄰域節點發 例而言，具有識別碼1 1 5 1之節點可在具 向上轉遞由具有識別碼1 44之節點所發 測轉遞分佈型樣例如可根據鄰近環發生， 點可以在具有識別 石馬1 5 1之節點的方 率例如可根據鄰近 —第二偵測訊息之 該目前節點至少指 目前節點之相鄰節 域節點之路由夥伴 別碼1 5 1之節點可 偵測訊息。在接收 之節點瞭解到具有 節點的鄰近節點。 他節點之活躍度資 鄰域内被交換，可 成員關係）及出現 圖。 ^重複/轉遞至一鄰 即被傳遞至該鄰近 分佈型樣發送被轉 型樣可以包括在一 送之偵測訊息。舉 有識别螞174之方 之偉剩訊息。偵 化。 68 200803303 節點可被組態用於以相應間隔接收偵測訊息。 收到期望偵測訊息時，一節點可解釋一通信失敗， 應當已經發出該期望（但至少是最新）偵測訊息之 將另一卽點之phase.unknown設定為真。 方法1400包括向一正確路由節點鄰近路由— 求訊息之操作（操作1 4 0 3 )。該更新要求訊息向接 路由更新要求之路由節點指示：該目前節點正在作 收路由節點之路由夥伴參與。該更新要求訊息也可 少該目前節點之鄰域節點之識別（例如，以活躍度 形式）。舉例而言，具有識別碼丨44之節點可以將更 13 16路由至具有識別碼208之節點（由64從144 路由夥伴偏置）。因此節點2 1 0 ( —先前計算之路由 最接近208 ’所以其將接收及處理該被路由更新要 接收到該更新訊息1 2 1 6時，具有識別碼2 1 〇之節點 (或被補充）具有識別碼丨44之節點係具有識別碼 節點的路由夥伴。 方法1400包括從該處理（接收）路由節點接受 回應訊息之操作（操作1 4 0 4 )。該更新回應向該目 指示該處理路由節點正在作為該目前節點之一路由 與。該更新回應訊息也可包括至少該處理路由夥伴 節點之識別。舉例而言，具有識別碼2丨〇之節點可 有識別碼1 44之節點傳送更新回應訊息1 2〇7。在接 新訊息1 207時，具有識別碼i 44之節點瞭解到具有 2 1 0之節點係具有識別碼1 44之節點的路由夥伴。 當未接 且對於 節點， 更新要 收一被 為該接 包括至 資訊之 新訊息 之正確 節點） 求。在 瞭解到 210之 一更新 前節點 夥伴參 之鄰域 以向具 收到更 識別碼 69 200803303 方法1400還可以包括適當更新節點資訊之操 示該目前節點及鄰域節點都作為鄰近節點參與且 ： 節點及該鄰近節點也作為路由夥伴參與。舉例了呈: 識別碼144之節點可以更新對應於具有識別碼^之 :節點資訊’以指示具有識別碼14…41之節點正：來 p (鄰近m類似地’具有識別碼 二 更新對應於具有識別碼21〇之節點的節點資訊时_呈 有識別碼144及210之節點正在作為路由夥伴參與。a不八 在某些具體實施例中’使用可靠氾濫廣播通訊協定 在一指定節點X之鄰域（X)中複製於該 ^疋， ^儲存之應用 狀態。應用狀態中之母一項均具有一被指派擁有者，其可 能是創建該項之節點。應用狀態中之每一項還具有一由^ 擁有者給定之相關時間戳記（也稱作序號）。該時間戳記擁 有至少三個成分： 擁有實體之實例識別碼（例如，一未指派整數）。必須 至少是單調（> 1 )逐增的。 序列識別碼（例如，一 URI )，識別由一所有者產生之 特定序列。此成分使同一所有者能夠產生多個獨立序列。 序數號（例如，一未指派整數），識別在該被識別應用 程式序列識別碼中之偏移。 項時間戳記被用於在複製期間偵測與該對應項相關之 最新資訊，因為項時間戳記的 < 實例識別碼、序列識別碼 及偏移 > 三項組合至少是部分有序的。如果存在一本機時 間戳記，則將與一被複製項相關聯之時間戳記與該本機時 70 200803303 間戳記進行對比，以偵測最新時間戳記。項時間戳記也可 用於支援創建/更新/刪除操作之恆效語義。例如，當一節 點接收一要求，以更新該應用狀態中之現有項時，僅當與 該更新要求相關之時間戳記高於與該本機項相關之時間戳 記時，才接受該更新。在不能為項指派單一所有者時，可 使用基於向量時間戳記之衝突解決技術。應用狀態複製提 供了容錯特性，且促進了鄰域節點之間的負載平衡要求。 作為一種可選特性，（在一段時間之後）未偵測到來自 (起始）其他夥伴（路由及/或夥伴）節點之期望更新或偵 測訊息的節點可以考慮階段狀態未知、將 phase.unknown 指示設定為真，且將其報告給第三方節點。換言之，可能 需要周期產生更新及偵測訊息此要求及實際超時值可能是 各種鄰近環之一屬性。舉例而言，一環可能對於一些子環 (例如，在一區域網路分段中）具有更嚴格之時間要求， 節點故障偵測/報告較快。另一方面，一環對於其他子環（例 如，在網際網路上）具有嚴格程度較低之定時要求（甚至 沒有定時要求 >，主動節點錯誤偵測/報告較長（或不存 在）。 第1 5圖說明用於搜尋另一節點之活躍度資訊之方法 1 5 00的實例流程圖。將針對第12A圖及第12B圖中之環 12 06描述方法 1 500。一般來說，任意訊息，例如，同步 1203、同步回應1204、更新1216、更新回應1207，等等， 可包括至少一活躍度標頭。在一些具體實施例中，一活躍 度標頭包括一節點之 < 節點識別碼、實體識別碼、階段 71 200803303 [phase-state valueUphase.xmknown indication]、新鮮度 值、顏色（鄰近）值及重量值 >。在其他具體實施例中， 一 活躍度標頭 包括 < 階段 [phase-state value].[phase.unkn〇wn indication]、新鮮度值、顏色（鄰 近）值及重量值 >。在此等其他具體實施例中，活躍度標 頭可被用於補充定址標頭’其已經包含該發送及起始節點 之節點識別碼及實例識別碼。由於定址標頭已經包含節點 識別碼及實例識別碼，所以可從該活躍度標頭中省略此資 訊0 方法1 5 0 0包括接收一活躍度標頭之操作（操作 15 0.1 )，該標頭表示一參與一聯合體基礎建設之節點的狀態 資訊。該活躍度標頭包括至少一所接收參與節點識別碼、 所接收節點之實例識別碼、所接收之階段值，以及所接收 之新鮮度值。舉例而言，具有識別碼1 44之節點可以從具 有識別碼1 5 1之節點接收同步回應訊息1 204中之第一活躍 度標頭。該第一活躍度標頭可包括具有識別碼1 74之節點 的 < 參與節點識別碼、實例識別碼、階段值[phase-state value].[phase.unknown indication]、新鮮度值、一顏色（鄰 近）值，以及一重量值 >。該階段狀態值（例如，插入階 段、同步階段、路由階段、操作階段）識別具有識別碼1 74 之節點在該第一新鮮度值之時間的所表示階段。該階段狀 態值（例如，階段狀態：[Inserting，Syncing, Routing， Operating]及phase .unknown)識別具有識別碼174之節點 在該第一新鮮度值之時間的所表示及/或所偵測階段資訊。 72 200803303 但是，由於通信延缓，一新鮮度值可能打折扣。一新 鮮度值還可能隨著時間之流逝而衰減。對於不同階段狀態 (包括未知狀態），一新鮮度值之衰減曲線可能不同（可能 不是線性或對稱的）。因此，在不同節點階段之間，一新鮮 度值之誤差可能是非線性及/或非對稱的。 方法1500包括存取該參與節點之至少一目前實例識 別碼、目前階段值及目前新鮮度值的操作（操作15〇2)，

該等資訊維護於該目前節點上。舉例而言，具有識別碼144 之節點可以存取具有識別碼174之節點的先前接收及儲存 實例識別碼、階段值[phaSe-sate vaiue.][phase.unkn〇wn indication]，以及新鮮度值。 方法1 500包括將至少所接收實例識別碼、所接收階段 值及所接收新鮮度值各別與一目前節點的目前實例識別 碼、目前階段值及目前新鮮度值進行對比的操作（操作 1 503 )。舉例而言，具有識別碼144之節點可以將具有識別 碼1 74之節點的先前接收及儲存之實例識別碼、階段值 [phase-sate value.][phase.unknown indication]及新鮮度值 與在該活躍度標頭中接收之實例識別碼、階段值 [phase-sate Value.][phase.unkn〇wn indicati〇n]及新鮮度值 進行對比。 具有識別碼1 44之節點可以根據（依順序）該第一實 例識別碼大於具有節點〗74之節點的目前儲存實例識別 碼、根據第一階段值高於具有識別碼174之節點的目前儲 存階段狀態值，或者根據該第一新鮮度值係大於具有識別 73 200803303 碼1 74之節點的目前儲存新鮮廑佶 又值，從而確定且古 1 74之節點的目前狀態資訊（例如， ”胥識別螞

、如，自具有節點H 點接收）過時。具有識別碼1 4 4夕* 〈郎 一 之即點還可以確定至小 phase.unkown指示（或者是目前健亡 一 夕〜 仔指示’或者县太 躍度標頭中接收），指示在偵測/偯〆 疋在該活 寻輸一階段狀態時， 段狀態已知。 呀該階 方法1 500包括操作1 504 ·•奸诚 根據該對比結果，確 否應當在目前節點更新該泉盥飭那 蜂疋是 ^ 一即點之狀態資訊。 吕，根據具有識別碼174之節點的取值對比，且舉例而 144之節點可以確定應當更，1^ ，具有識別石馬 態資訊。為具有識別碼174之節=碼174之節點的狀 程可包括用該活躍度標頭中包括4過期^態資訊之過 如，實例識別螞、階段狀態 取代目前儲存值（例 鮮度值)。舉例而言，具有 h:一。 八另喊別碼14 4之筋點可丨vθ 別碼174之節點更新狀態資訊 有為，、有識 即點已經轉換至—更高階之階段狀態。 ”之 節點在具體實施例I可以偵測到已經失去與該參與 到之、仏。舉例而言，具有識別碼"4之節點可以偵測 已經失去與具有識料151之節點之通信。簡單參考第 1 7圖，回應先前 則 J對活躍度事彳1701之訂閱（利用具有識 】瑪1 5 1之節點的端點） 旧~點），應用層1752可以向功能層17S1 送端點當機事件17G3(利用具有識別碼151之節點的端 ”、）在此等具體實施例中，此等被横測之活躍度條件可以 在活耀廣誊邙Φ - ° 心不 將Phase.Unknown指示項設定為 74 200803303 “真”，再利用最新已知階段狀態值。 方法1 500可以進一步包括從該聯合體基礎建設中一 第二不同節點接收包括一第二活躍度標頭之訊息的操作。 舉例而言，具有識別碼1 44之節點可以接收包括一第二活 躍度標送之狀態訊息（從具有識別碼1 0 3之節點或者環 1206中之其他節點）。該第二活躍度標頭可包括具有識別 碼1 74之節點的 < 參與節點識別碼、第二實例識別碼、第 二 階段值 [phase-state value], [phase.unknown indication]、第二新鮮度值、第二顏色（鄰近）值，以及 一第二重量值 >。該第二階段狀態值（例如’階段狀態： [Inserting，Syncing，Routing，Operating] phase.unknowii 指示）識別具有識別碼1 7 4之節點在該第二新鮮度值之時 間的所表示及/或所偵測階段。 或者，在接收到該第一活躍度標頭之後’具有識別碼 144之節點可以嘗試直接與具有識別碼174之節點通信。 如果該通信成功，則具有識別碼1 74之節點可以返回一訊 息（例如，同步回應），該訊息在一定址標頭中具有節點識 別碼及第二實例識別碼，且擁有一活躍度標頭’該標頭包 括< 第二階段值、第二新鮮度值、第二顏色（鄰近）值’ 及第二重量值 >。如果偵測到一故障’具有識別碼144之 節點產生一内部活躍度狀態變化（例如，新鮮度=最大值， phase.unknown指示=真），且處理該狀悲改變，就像從另 一節點接收到該狀態變化一樣。此種狀態變化具有最高新 鮮度值。 75 200803303 方法1 500還可包括將該第二實例識別碼、第 及第二新鮮度值各別與該目前實例識別碼、目前 目前新鮮度值進行對比之操作（操作15〇6)。舉 在從具有識別碼1 03之節點接收到一狀態訊息之 .- 識別碼144之節點可以（按照順序）根據第二實 .大於第一實例識別碼、第二階段比第一階段值更 者第二新鮮度值大於第一階段值，從而維定具 、 Ϊ51之節點的目前狀態值過時。 方法1 500還可包括根據該對比結果確定是 該參與節點之狀態資訊的操作。舉例而言，根據 碼1 74之節點的取值對比，具有識別碼丨44之節 疋應當更新具有識別碼1 7 4之節點的狀態資訊。 別碼1 74之節點更新過期狀態資訊之過程可包括 活躍度標頭中包括之值取代目前儲存值（例如， 崎、階段狀值、phase.unknown指示或新鮮度$ 而言，具有識別碼1 44之節點可以為具有識別碼 點更新狀態負訊’以指示具有識別碼1 7 4之節點 至一更高階之階段狀態。 在一些具體實施例中，在相等顏色值之環境 、 段值。如前所述，一節點可參與多個鄰近環。當 v 具體環隱含著參與一更一般環（沿一公共脊椎（ 時’可能會發生參與多個鄰近環之情況。舉例而 參考第5圖，一節點參與環532也隱含著該節點 % 522、511及501。因此，一更具體環之顏色可 二階段值 階段值及 例而言， 後，具有 例識別碼 高階，或 有識別碼 否應更新 具有識別 點可以確 為具有識 用該第二 實例識別 i )。舉例 174之節 已經轉換 中對比階 參與一更 Spine)) 言，再次 正在參與 表示所有 76 200803303 父鄰近環。仍如前文所述，當一環中之節點被設定 至一或多個其他環時（可能沿著不同脊椎），可能發 多個鄰近環之情況。舉例而言，仍然參考第5圖， 環5 3 2之節點可被設定別名至環5 3丨中，（甚至是 中，其隱含著參與環531、522、511及501 )。因此 (例如’環5 3 1 )之顏色可被看作另一環（例如，: 之一對等顏色（或鄰近顏色）。 當一節點以別名方式參與複數個鄰近環時，在 近環之間，該節點之階段值（例如，階段狀態崔 phase.unknown指示）可能不同。因此，接收另一 狀態資訊的節點，在確定是否對於該節點及顏色更 狀態資訊之前，為該狀態資訊（顏色）識別相應鄰 舉例而言，具有識別碼1 44之節點在將所接收之狀 與目前狀態資訊進行對比之前，可以為對應於具有 1 74之節點的所接收狀態資訊來確認該相應鄰近環。 識別一適當鄰近環可包括將一所接收顏色值與 個目前顏色值進行對比。當所接收顏色值與一目前 相等時，可以將其他狀態資訊（例如，目前實例識 目前階段值及一目前新鮮度值）與所接收之相應狀 (例如所接收實例識別碼、所接收階段值及一所接 度值）進行對比。另一方面，當所接收顏色值與— 色值不同時，不再進一步進行對比。 可以採用多種方式得到顏色值之相等。舉例而 一目前顏色值與一所接收顏色值指示相同鄰近環（ 別名， 生參與 一參與 環541 ’一環 最 532 ) 不同鄰 L及/或 節點之 新目前 近環。 態資訊 識別碼 一或多 顏色值 別碼、 態資訊 收新鮮 目前顏 言，當 例如， 77 200803303 環532 )時，可得到顏色值之間的相等。另外，當一更具 體顏色值與一相應父顏色值（例如，沿相同脊椎之另一環） 進行對比時，可能得到顏色值之間的相等）。舉例而言，將 環532之顏色值與環511之顏色值（或者環522或501) 進行對比可得到相等性。因此，該子鄰近性是父鄰近性， 但更具體。 因此，一般來說，一聯合體基礎建設中之目前工作節 點可以交換所表示及偵測到之其他節點的活躍度狀態資 訊，甚至在推動與該等其他節點之通信時亦能交換。 啟動載入機制 一般來說，為使一節點成為一聯合體之活動成員（例 如，加入），該節點必須與至少一其他節點通信，而該其他 節點已經是該節點希望加入之葉環的活動成員。為幫助確 保此起始通信方式可供使用，聯合體可利用一啟動載入機 制。當其他類型之通信不能識別一葉環之活動成員時，或 者安全約束條件要求一新加入節點在開始時能夠與一特殊 節點集合（例如，種子節點）中之至少一節點進行通信時， 啟動載入機制可用作一最終手段。即，當其他類型之通信 失敗，或者由於安全要求之原因，一啟動載入機制可被用 於識別一葉環之活動成員節點。 在一些具體實施例中，種子節點可用於與一聯合體之 啟動載入通信。種子節點可為一些類型之跨鄰近環（鄰近 間）通信提供習知登錄點。種子節點可以幫助解決由於基 礎建設故障/恢復及一般推動力所導致之環分割。每一環擁 78 200803303 有至少_工 作路子節點，以便為一聯合體 入特性。 W 口體钕供基本啟動載 對等種Ia t 如，雙向鍵：:二可相至通信’以維護-鄰近之環樹構(例 成。-專用：子：該鄰近由其至少全部活動種子節點組 點裎徂 印點同步通訊協定可被用於為每一種子μ 點k供至少所古甘 種子郎 所有其他種子節點之目前（活 知識。一活動絲2 ^ 勒彡狀態之全部 動種子卽點係其所在鄰近葉環及該荦 其他上階環之成員節點。因此，一種子“可之所有 之整個脊梏，如i 禋于即點可表示鄰近環 插y 從該種子節點之葉環至根環。相A地 種子郎點可以用作此等鄰〜 應地， 登錄郎點。結果，對於一聯合體内之各種通 及“° 鄰近間通信），有關種子^ ^ 例如， 男關種子即點之存在狀態可能 應地，種子節點可# 有用。相 點之習知‘ 種特殊屬性，，用作加入節 建^α入點’用作一安全環授權，辅助處理某礎 建以參！，以及用作此等鄰近中每土 點”。 处4穩疋登錄節 為提供存在資料，一種子節點 古主冊幺少益L ^ , j運及有序脫離可被

»冊為在每一此等鄰近中之一匯集點的穩A 例而言，註冊訊息可被路由至一固定uri即點。舉 係字_ "Proximity··/”之SHA·!雜湊。在一具體:的識別碼 用作穩定登錄節點之種子節點以此種方式：：例中’ 時存在其他具體實施例，在此等且體奋”，、自已，同 非種子節…以相同方式及：广施例中’被選擇之 丨』万式及本文為種子節點所

同或類似通訊協定來註冊其自身。 >L 田穩疋登錄節點（例 79 200803303 如一種子節點）註冊時，該穩定登錄節點可指示 環之成員。因此，在此固定URI所識別之匯集點 訊本質上係穩定登錄節點及其對應環成員關係之 應地，任意節點可參考由此固定URI所識別之匯 獲得可用穩定登錄節點及其環成員關係之串列。 在一具體實施例中，該穩定登錄節點直接註 及脫離事件。在另一具體實施例中，該穩定登錄 在其直接鄰近環内之一匯集點處註冊該等事件， 透明地（直接或間接）促進更新其餘鄰近環中所 應匯集點點，該註冊/取消註冊穩定登錄節點屬於 鄰近環。一聯合體之應用狀態序列及傳播特性可 護及傳播此穩定登錄節點註冊資訊。舉例而言， 氾濫廣播通訊協定可被用於在一節點之鄰域節點 儲存之應用狀態。 向該根環傳播穩定登錄節點之存在資料，可 合體内之其他節點能夠查閱每一鄰近環中之至少 點。藉由向最低公共上階環（“ LCAR” ）中之上 之匯集點路由一節點查閱訊息來促進“登錄節點 該最低公共上階環係執行該查閱之節點的葉環及 環之最低公共上階環。舉例而言，參考第5圖， 之一節點可能希望與環5 3 3中之一節點通信。但； 中之節點可能不具備有關環5 3 3中任一節點之直 因此，環541中之節點可以向環522 (環541及 最低公共上階環）發送一“節點查閱訊息”。環 其係哪些 維護的資 串列。相 集點，以 冊其到達 節點直接 該匯集點 有其他適 該等剩餘 被用於維 一可靠之 中複製所 以使一聯 一登錄節 文所確定 查閱”， 期望鄰近 環54 1中 t ，環 541 接知識。 環53 3之 522中處 80 200803303 理登錄節點存在資訊之一匯集點節點（例如，由於 節點所發出之註冊訊息而存在於該系統中），可以 “查閱回應訊息”，其中具有關於環5 3 3中至少一 穩定登錄節點之聯絡資訊。 在一些具體實施例中，穩定登錄節點係種子節 被特殊組態為穩定登錄節點，用於維護各種鄰近之 料。在其他具體實施例中，其他類型之節點也可用 各種鄰近之存在資料的穩定登錄節點，也可被組態 行其他操作。舉例而言，其他特定類型之節點可被魚 如由一管理員）為高度可用，從而適於用作一穩定 點（即，按上文方式被註冊）。但是，其他類型之節 不包含附加種子節點功能（例如，未獲取作為安全 之信任）。在其他具體實施例中，為其直接鄰近環維 節點存在狀態之匯集點可將其自己註冊為上階環中 登錄節點。 鄰近間通信 本發明之具體實施例還可促進鄰近間通信，例 環樹之不同鄰近分支中節點之間的通信。鄰近間通 於向一鄰近分割環基礎建設之一或多個鄰近環（可 部鄰近環）通信，或是在該等一或多個鄰近環之間 現在參考第5A圖，第5A圖說明一引入鄰近之實例 500的，其中具有分割樹500之附加位準細節。鄰 訊可發生於第5 A圖之各節點之間。 如第5A圖所述，環分割樹500額外包括在環 該登錄 返回一 已註冊 點，其 存在資 作維護 用於執 .態（例 登錄節 點可能 環授權 護登錄 之穩定 如，一 信可用 能是全 通信。 分割樹 近間通 513下 81 之各子節點。該等附加環中之每-環表示-之刀割邛为。如前文對第$圖之所述，在

52 1、522及523。根據其他準則進一步分割 其他子環。 200803303 可根據準貝1】5 7 !(一第一管理域界限準則） :為複數個子環，包括子環5"、512、513 前文對第5圖之所述，可根據準貝"81 ( 一 限準則）將子環5 11進一步分割為複數個子 如前文所述，在分割樹500中，每一節 別碼，且沿一由該根至葉之相應分割路徑（ 環中。舉例而言，參與子環552之每一節點 543、531、522、511 及根 501。 在第5A圖甲，子環513還可根據其他 州官轄權限）進一步被分割為複數個子環， 及5 62。子環562還可根據其他準則（例如 限）進一步被分割為複數個子環，包括子環 相應地，在第5 A圖中，鄰近間通信可被用 一節點向環572之一節點發送一訊息，不需要 至根節點5 0 1之脊椎向上通訊，然後再從根 向下返回。 鄰近間通訊可包含作為實施於一環樹中 部分，例如，廣播、多播或任意傳播。廣播 樹中之所有活動節點發送一訊息。多播可包 之一組節點發送一訊息。任意傳播可包括向 有序鏈結串列 卜割樹500中， 將根環5 0 1分 及5 1 4。亦如 第二管理域界 J袠’包括子環 子環522下之 點具有單一識 一脊椎）參與 還將參與子環 準則（例如， 包括子環5 6 1 ’城市管轄權 571 及 572 〇 於從環5 4 1之 沿著從環5 4 1 5 〇 1向環5 7 2 之通信型樣之 可包括向一環 括向一環樹中 一環樹中之至 82 200803303 少一節點發送一訊息。 之實例分割環樹1900,其促 第l9A圖說明一弓丨入鄰近 進鄰近間通信。在分割壤樹j 9〇义风4

如，一第一管理域界限準則〇〇中，可根據所選擇準則（例 環，包括子環1、2、3及4將根裱丨9〇 1分割為複數個子 11、21、31及41。子環ι 4。子環1被進一步分割為子環 及311。子環被進〜\ L被進一步分割為子環111、211 及521。儘管未被明確： '副為子之121、221、321、421 逆，但其他環，例如，子環2、3、 4、31及41，也可被進一牛八金丨 步分割。 引入鄰近之分割環樹19〇〇中環的數位約定被組態，使 得第一數位之後的任意數位指示一環之父環。舉例而言， 環“ 3 11中之 11指示環1 1係環3 11之父環類似地， 環“41”中之“1”指示環1係環41之父環整體環1901 係所有以單一數位編號之環（例如，環1、2、3及4 )的 父環。與第5 A圖中之引入鄰近分割環樹5 0 0類似，可根 據各種鄰近準則分割環樹1 9 〇 〇。 在本說明書及以下申請專利範圍内，標記 R[”<number>”]被用於指代一環編號。例如，Μ”11Ί指環 11 。在本說明書及以下申請專利範圍内，標記 N["<number>"]被用於指代一節點編號。例如，Ν！ 3 j i，，] 指節點1 3 1 1。 為促進一環樹中之通信，節點可維護一登錄表，其將 環匹配至該等環中之相應登錄節點。如前所述，根據分割 環樹1 900之組態，一父環包含所有來自其每一子環之節 83 200803303 點。舉例而言，環11包含來自尺["111”]、&["211"]及“”311，，] 之全部節點。因此，向環U發送一訊息就足以使該訊自、到 達環R[”211，，]及R["311"]之任意節點。相應二， 在一些具體實施例中，一節點之登錄表可被精簡至一歧環 中之登錄，該等環不同於從該節點所在環之角度。例如， ΝΠ111]可簡單地維護R[”21”] _ N[1121]之登錄，因為維護 多個子環或R[”21”]之登錄將是冗餘的。 創建及維護間接環集合 在本說明書及以下申請專利範圍中，一指定環音 對等環被定義為該指定環之‘‘間接環，，。纟本說 ： 下申請專利範圍中，一指宗戸μ你匕β " ,Λ^ r <(彳日^上階*之任意對等環也被定 義為則…< Fb，接環”。-指定環之任意間接環” 該指定環中所包含之全部節點之間接環。 疋 因此，舉例而言，仍然參考第19A圖， 是R["m"]之對等環，所] 叩3Π])之間接環。另外，由於R[,mR["如， π⑴"]之-上階環）之對等環’所以R["21 ; 之間接環，也是包含在R["⑴"]中之任意 如，N[1 111])之間接環。 、例 在本說明書及以下申請專利範圍中，“間接 (“ CRS” ）被定 ϋ 么^ _ 為從一私疋環或一指定環之節點的 度來看’-或多個間接環之集合。舉例而言，在第ΐ9Α圖， Rr221"]之一間接環集合’也是環μ"。”]中任意節點（例 84 200803303 如，N[822 1])之平行一環集合，包括 R[nll"]、R[n121·’]、 R[f’3r’]、R[n41’’]、R[n2’’]、R[n3n]及 R[n4n]。 因此，為促進鄰近間通訊，一節點可維護一間接環集 合登錄表，其包括一或多個間接環，以及一或多個對應於 該等一或多個間接環之登錄節點。一間接環集合登錄表可 係一資料結構，其包括一或多個 < 間接環，1至N個登錄節 點 >項，其中，N為某一整數。舉例而言，該資料結構可以 為 < 間接環〇 1，登錄節點〇 1，登錄節點02，… > 之格式，其 中，省略號表示間接環0 1中之一或多個附加登錄節點。 為創建一間接環集合登錄表，一節點可利用本機知 識、用於在一環樹中傳播狀態之通訊協定訊息（例如，偵 測訊息、更新訊息及更新回應訊息）、應用訊息，以及用於 促進在一環樹中之指定通訊型樣（例如，廣播、多播及任 意傳播）之訊息。 一節點可以從一節點所參與之任意環位準使用本機知 識，例如，路由表資訊。舉例而言，仍然參考第 19圖， N[ 1121]可以是R[’’r’]中N[1311]的鄰居。從N[1121]之角 度來看，N[1311]之一間接環為R[n21·’]。相應地，N[1311] 可以將（R[”21，’]，N[1121])對（在此情況下，是具有單一登 錄節點之項）插入N[ 1 3 11 ]之間接環集合登錄表中。利用 此種類型之本機知識，一節點可向間接環集合登錄表中插 入登錄。 除特別預期之訊息之外，節點可以在用於其他目的之 訊息中傳播其間接環集合登錄表資訊，例如，用於傳播鄰 85 200803303 域及路由夥伴狀邊資訊。例#，節點可以在發送至鄰域節 點之偵測訊息中以及在路由夥伴節點之間交換的更新訊息 及更新回應訊息中包括間接環集合登錄表狀態。從另一節 點接收間接環集合登錄表狀態之節點可以使用所接收之間 接環集合登錄表狀態來增大及/或維護其自己的間接環隼 合登錄表。 x 舉例而g，當一節點與其鄰域/夥伴節點交換匯集偵測 /更新訊息_ (例#，在—匯#通訊協定層），肖節點還可 以交換（至少部分，可能是全部）其間接環集合登錄表（且 使用從其鄰居/夥伴接收之間接環集合登錄表來更新其自 己的表）。舉例而言，假定N [丨3 1 1 ]不具有R [，，3 ” ]中任意節 點之先驗知識（在環1901之環境中）。但是，n[1311]的確 有一個鄰居N[8221](在R["i，，]中），且n[8221]的間接環 集合登錄表具有（R["3，，]，N[8223])項。至少因為N[13ll] 及N[8221]是鄰居，所以n[1311]及N[8221]可以不時相互 發送偵測訊息。N[8221]可在發送至N[1311]的偵測訊息中 包括（至少部分，可能是全部）其間接環集合登錄表。因 此，當N[13 11]從N[8221]接收一偵測訊息時，該偵測訊息 可包括N[8221]之間接環集合登錄表。從N[8221]的間接環 集合登錄表，N[1311]可識別 <R[，，3，，]，N[8223]，···>項，且 在其自己的間接環集合登錄表中包括<R["3”]， N[8223]，··>項。N[13 11]還可識別其間接環集合中其他環 的其他項，且在其自己之間接環集合登錄表中包含該等其 他項。 86 200803303 可以在一環中路由夥伴之間交換的更新訊息及更新回 應之間類似地交換間接環集合登錄表狀態。此外，任意路 由通訊協定訊息可用於學習有關間接環集合登錄節點之資 訊（例如，活躍度資訊）。此外，可以使用意欲維護間接環 集合登錄表之特定訊息。 間接環集合登錄表狀態也可在促進一環樹中之指定通 信型樣（例如，廣播、多播及任意傳播）的訊息中搜尋。 舉例而言，為向一環樹中之所有節點廣播一訊息，一廣播 演算法可使用專用於廣播之各種類型訊息。發送廣播專用 訊息之節點可在其廣播專用訊息中包括間接環集合登錄表 狀態。類似地，在向一節點群組中之每一節點多播一訊息 時，一多播演算法可使用專用於多播之各種類型訊息。發 送多播專用訊息之節點可在其多播專用訊息中包括間接環 集合登錄表狀態。類似地，在向至少一節點任意傳播一訊 息時，一任意傳播演算法可使用專用於任意傳播之各種類 型訊息。發送任意傳播專用訊息之節點可在其任意傳播專 用訊息中包括間接環集合登錄表狀態。接收通信型樣特定 訊息之節點可以識別適當項（例如，< 間接環，登錄節點> 項），且在其自己之間接環集合登錄表中包括此等項之部分 或全部狀態。 在應用程式之間交換的應用程式組件訊息中也可搜尋 間接環集合狀態。簡單地參考第1圖，應用層121、122 及/或123可交換包括間接環集合狀態之應用程式組件訊 息。在接收到包含間接環集合狀態之應用程式組件訊息 87 200803303 時，一應用層可以將該間接環集合狀態向下傳遞到相應的 其他較低層，例如，傳遞到匯集通訊協定層，以增加現有 間接環集合狀態。 間接環集合狀態可由應用程式提供及/或硬佈線，且可 由一環樹中之節點組態。 再次參考第1 9 A圖，如果一節點發現其知曉相同環之 複數個登錄節點，其可以決定為該環保留兩或多個登錄節 點。在一些具體實施例中，該節點從所保留之任意登錄節 點中隨機選擇一登錄節點。在其他具體實施例中，應用一 原則，用以幫助從所保留之任意登錄節點中選擇一指定登 錄節點。一原則可指示每次所選擇之登錄節點是相同登錄 節點。或者，一原則可指示所選擇之登錄節點可以在所保 留之任意登錄節點之間變化。舉例而言，在一些具體實施 例中，以一種循環方式選擇登錄節點，以使負載被均勻地 分佈在所保留之任意登錄節點之間。 此外，在保留多個登錄節點時，例如，如果一第一被 選登錄節點發生故障、忙或其他不可用原因，則一節點可 以有效地轉移至一不同登錄節點。 或者，一節點可為該環保留單一登錄節點。 一節點可不時為一環偵測額外登錄節點。在一些具體 實施例中，當一節點保留一單一登錄節點或者缺少儲存額 外登錄節點之記憶體時，該節點可以決定一新被接收之登 錄節點是否應取代一現有登錄節點。在一些具體實施例 中，一節點可以利用一函數，根據以下參數計算每一備選 88 200803303 登錄節點之等級：該登錄節點之距離、該登錄節點資訊之 新鮮度，以及該登錄節點之重量（例如，組態偏好）。一具 有較高等級之登錄節點被保留。 一間接環集合登錄表可以完整，也可以不完整。一完 整間接環集合登錄表包括一節點之間接環集合中每一環的 至少一個登錄節點。例如，節點1 3 11之一完整間接環集合 登錄表將包括環111、211、21、31、41、2、3及4中每一 環之至少一個登錄節點。 利用上述機制，有可能從一或多個環及/或一鄰近環階 段中節點之角度來構建完整間接環集合登錄表。在一些具 體實施例中，路由表狀態資訊可能獨立構成該環樹中每一 節點之完整間接環集合登錄表。舉例而言，關於在環樹 1 900中傳播資訊（例如，在偵測訊息、更新要求訊息及更 新回應訊息中）之路由表可以為所述每一環中之所有節點 形成一完整間接環集合登錄表。 但是，在其他分散式網路環境中，該環之動態本質及/ 或狀態相關登錄表之交換中的延遲可能妨礙一完整登錄表 之構成。換言之，在此等其他環境中，在一環或一節點之 間接環集合中，可能存在該節點或環在任意既定時間所不 知曉之一或多個環。舉例而言，再次參考第1 9 A圖，假定 N[8 004]剛剛加入，而且在此之前不存在屬於 R[n4n]之節 點，在訊息流量（例如，偵測/更新訊息）或其他行為導致 在整個環基礎建設中散發資訊之前，大多數節點將不具有 r[”4”]之登錄節點。因此，由於網路之動態性（例如，節 89 200803303 點故障、通信故障、通信延遲、節點增加，等等），在一節 點維護一完整間接環集合登錄表並非總係可能的。相應 地，在許多環境中，一節點維護一部分間接環集合登錄表， 其包含有該節點之間接環集合中之部分環（而非全部環） 的登錄節點。 使用間接環集合登錄表進行鄰近間通訊 一節點可以使用間接環集合登錄表中之資訊進行鄰近 間通信（例如，不必向發送環及目的環之最低公共上階環 路由一訊息）。仍然參考第19 A圖，根據一間接環集合登 錄表中之合適項，N [ 1 3 1 1 ](例如，一發佈節點）也許能夠 將鄰近間通信資訊直接發送至 R[nm’’]、R[n2iin]、 R[n2 1，，]、R[’，3 1n]、R[n4r’]、R[’’2n]、R[n3’’]及 R[，’4n]中之 一或多個。例如，在某一時間，N [ 1 3 1 1 ]之一間接環集合登 錄表可包括以下項： R[n2f,] : N[1112] R[n3M] : N[8223] R[’，21"] : N[1121] R["31，，] : N[1131] R[，，lll，，] : N[llll] R[f,2Hn] : N[1211] 此等項可被用於直接向R[”lll”]、R[”2U”]、R["21"]、 R [，’3 1]、R["2’，]及 R[n3f’]通信。舉例而言，N[1311]可以向 R[f’mf’]發送通信訊息52，N[13 11]可以向R[n21 1"]發送通 信訊息 51， N[1311]可以向 R[n21，’]發送通信訊息 53 90 200803303 (N[112 1]是 R[，’2r’]及 R[”221n]之成員），N[1311]可以向 R[，，3Γ，]發送通信訊息56，N[1311]可以向R[π2n]發送通信 訊息57，N[13 11]可以向R[’’3n]發送通信訊息58。隨著時 間之流逝，Ν[” 1311π]可識別R[n41’’]及R[，’4M]之項（例如， <間接環，登錄節點 > 項）。可以從經更新之本機知識、從 包含在匯集通訊協定訊息（例如，偵測訊息、更新訊息及 更新回應訊息）中之間接環集合登錄表，經由包含在通信 型樣專用訊息中之間接環集合登錄表狀態，且經由其他機 制（例如，一應用程式組件）來識別該等項。 向下路由演算法 在一匯集聯合體中（具有或不具有間接環集合登錄 表），一訊息可能被路由至最接近一指定鄰近環中一既定節 點識別碼之節點，該指定鄰近環不是發出該訊息之葉環的 上階環（下文中將之稱為“向下路由”）。此一實例係在起 始環中之節點不知道該間接環中一登錄節點時，促進從一 起始環中之節點向一間接環之鄰近間通訊。第1 9B圖說明 引入鄰近之實例分割環樹1 900之另一視圖。舉例而言，現 在參考第19B圖，N[1311]可能發送一以R[，’4’，]或R[”41’，] 之節點為目的之通信。 對於一此種既定匯集聯合體，可以定義以下函數： 尺0\116〇0^^11(^1，？，1〇):該聯合體向最接近鄰近？中1〇 之節點傳遞訊息Μ。鄰近P可以是聯合體中之任意鄰近環 (葉環或中間環），其不是該起始節點之葉款的上階環。 在一些具體實施例中，從來不會在該起始節點之葉環 91 200803303 及該目標鄰近環p之最低公共上階環中，向上路由訊息 Μ。舉例而言，可實施從N [ 1 3 1 1 ]至R [ ’’ 4 1 ” ]之向下路由， 可能不需要將一訊息向上路由至 R [ ” 1 ’’ ] C R [ ’’ 3 1 1 ” ]及 R[n4 1"]之最低公共上階環）。但是，在其他具體實施例中， 如果合適，一訊息可被路由至一最低公共上階環之上方。

RouteDown(M? P，ID)函數可以包括識別一登錄節 點，已知該登錄節點係該目標鄰近環P之一成員。一發送 節點可以使用各種不同機制識別一目標鄰近環中之一登錄 節點。一發送節點可以係一起始節點（該第一發送節點）。 一發送節點也可以是一中間節點，其從該起始節點或另一 中間節點接收訊息，然後轉遞該訊息。 一發送節點可以使用本機知識，例如，组態或本機快 取之資訊以及一間接環集合登錄表），來識別一目標鄰近環 中之登錄節點。舉例而言，N [ 1 3 1 1 ]可存取快取及組態 1 902,其中包括有關環樹1 900中之環的組態及本機快取資 訊。在一些環境中，經由該聯合體之外的通信機制（例如， 帶外）獲得關於一聯合體之本機知識。本機知識可用於識 別確切目標鄰近環P中之任意節點。如果找到確切目標鄰 近環中之任意節點，則訊息Μ可被轉遞至其中任一節點。 舉例而言，Ν [ 1 3 1 1 ]也許能夠使用快取及組態 1 902，以確 定Ν[8 004]，且將訊息1 903轉遞至R[n4’’]。 一發送節點可使用一間接環集合登錄表來定位該目標 鄰近環P中之任意登錄節點。如果找到該目標鄰近環中之 任意登錄節點，則可以將訊息Μ轉遞至該目標鄰近環P中 92 200803303 之一登錄節點。舉例而言，當n[752 1 ]為訊息19〇3之目的 時，N[13 11]可確定N[652 1 ]作為之登錄節點。相 應地，訊息1 903可被路由至n[6521]或（至R[，，52i”])。 在R[”5 2 1”]内，N[652 l]於是可以嘗試使用環内通訊將訊息 1903路由至N[7521]。因此，如果一發送節點能夠識別該 目標鄰近環之一登錄節點，其將該訊息轉遞至該確切目標 鄰近環。例如，如果N [" 6 5 2 1 "]能夠識別R [ ” 2 1 ” ]之登錄節 點，其將訊息1 9 0 3轉遞至R [ ” 2 Γ，](虛線）。 另一方面，當發送節點（例如，從本機知識或一間接 環集合登錄表）不能識別該目標鄰近之任意登錄節點時， 該發送節點可以檢查其間接環集合登錄表，以定義該目標 鄰近環之任意上階環之登錄節點。舉例而言，N [ 1 3 1 1 ]能夠 嘗試向R[” 121"]中之節點發送一訊息，但是，n[1 3 11]不能 識別R[”121”]之登錄節點。相應地，n[1311]可參考間接環 集合登錄表1 904，以定位N[652 1 ] ( R[，f21 ’’]中之登錄節 點）。>1[1311]可將該訊息轉遞至n[6521]，其現在成為該 訊息之發送節點。 在邏輯上，由於N[6521]也是R[21]之一節點，所以訊 息1 903現在可以被看作“位於” R[”2 1Π]。N [652 1 ]於是可 以嘗試識別R [ 2 2 1 ](該目標鄰近）中之一登錄節點。舉例 而言，N[6521]可查閱本機知識、一間接環集合登錄表，及 /或可以（遞迴）應用該向下路由演算法。N [652 1 ]可將 >^[3 22 1 ]識別為11[221]之登錄節點。相應地，>^[652 1 ]可以 將訊息1903發送至N[3221]°N[3321]於是可以使用環内 93 200803303 通訊將訊息1903路由到R[221]中之一適當節點。 在適當時（例如，在深於第1 9 B圖中所示之樹中）， 一訊息可以被傳遞到其上階，該等上階越來越接近該目標 鄰近環，直到目標鄰近環中之登錄節點被識別，或者不再 有可用上階環時為止。 一發送節點還可以路由一登錄節點查閱要求，其至少 包含向登錄節點目錄機制提出之目標鄰近要求，例如，用 於啟動載入該聯合體。一登錄節點查閱要求之路由可被限 制於該發送節點及該目標環之最低公共上階環。舉例而 言，N[1311]可將查閱要求1906路由至匯集點7651，以要 求R[” 3 Γ，]之登錄節點。一登錄節點目錄機制可返回潛在登 錄節點之串列。舉例而言，匯集點7 6 5 1可返回一潛在登錄 節點之串列（包括 N[843 1 ])，以及至少在查閱回應 1907 中以該目標鄰近之匯集點註冊之種子節點。 該發送節點考慮在一查閱回應訊息（自該匯集點發送） 識別之新發現節點，且將訊息M轉遞至該等登錄節點之 一。考慮新被發現之節點可以導致該間接環集合登錄表（以 及其他本機快取之節點存在知識）被增加或維護。查閱回 應訊息還可包括其他節點存在資訊。舉例而言，已知對於 該發送節點很重要之特定登錄節點可能包含於該發送節點 之間接環集合登錄表中。 因此，如果一或多個可用機制在該目標鄰近環中產生 至少一登錄節點，則該訊息Μ被發送（或者由該起始發送 節點，或者由該目標鄰近之上階環中之一登錄節點，或者 94 200803303 由一查閱登錄節點）至該目標環中此等登錄綺點中之至少 一個。該訊息Μ可包含用於該鄰近目標環之备錄節點的指 令，以將訊息Μ路由至ID。另一方面’如果：任一可用機 制均未產生該目標鄰近環中之一登錄節點’貝M RouteDown 要求被錯誤地向該原始發送節點返回。 在一些具體實施例中，一起始節點游一端對端 RouteDown訊息標頭附加至該訊息，其中該K^outeDown訊 息標頭指定該目標鄰近URI。 如果任一上述機制識別多個“下一躍點”節點，則可 選擇單一節點。在選擇一單一節點時（例如，中斷一連接）， 更接近該目標鄰近P之節點可被選擇’之後，具有更高重 量之節點可被選擇，之後，更接近目標M識別碼之節點 可被選擇。如果沒有機制導致選擇’於是一節點可被隨機 選擇。如果當存在多個候選節點、未能成功傳遞訊息 Μ 時，只要存在未發生錯誤之候選節點，就可以重新嘗試轉 遞。 可以建立一逆向狀態/錯誤訊息路徑，該應用訊息從該 發起者經由中間節點到達最終目的節點。一旦一訊息被傳 遞至該目的節點或偵測到一錯誤，可沿此路徑向該發起者 發送一相應錯誤/狀態訊息。 第1 9 C圖說明引入鄰近之實例分割環樹1 9 0 0之一部 分的分割視圖。第1 9D圖說明實例引入鄰近之分割環樹 1 9 0 0之不11的放大視圖。第2 0圖說明為維護環樹中一節 點維護一間接環集合之方法2000的實例流程圖。將針對第 95 200803303 19 C圖及第 19 D圖中之環、節點、訊息及資 2000 〇 方法 2000包含一節點存取一間接環集会 作（操作 200 1 )，該間接環集合登錄表被組態 節點之間接環集合登錄。每一間接環集合登錄 指示該節點之一間接環，及該節點之間接環内 應登錄節點。舉例而言，N [ 1 3 11 ]可存取間接環 1 904，其被組態用於儲存N [ 1 3 1 1 ]之間接環集 格式為 < 間接環，1至N個登錄節點 >，其中N J 因此，間接環集合登錄表1 904可包括零或多{ 登錄節點 > 項，每一被包含項指示N [ 1 3 1 1 ]之一 該間接環中之一或多個相應登錄節點。舉例而Ί 圖中所示，間接環集合登錄表1 904包括間接 <R[f’5 1f’]，N[865 1 ]，···>，表示 N[865 1 ]係 R[51]( R [" 3 11 ’’ ]之一間接環）之1至N個登錄節點之- 方法2000從可用資源中搜尋間接環集合 之操作（操作 2002 )，該等可用資源維護有闢 態的資訊。舉例而言，N [ 1 3 1 1 ]可以從維護有| 之組態資訊的資源中搜尋間接環集合登錄表資 述，間接環集合登錄表資訊之各種不同來源可 用。舉例而言，一節點可存取本機知識，例如 快取資訊；可存取包含於匯集通訊協定訊息中 合相關狀態，該等訊息例如為偵測訊息、更新 回應，用於在環樹中傳播狀態；可存在包含於 料描述方法 登錄表之操 用於儲存該 被組態用於 之至少一相 集合登錄表 合登錄，其 b某一整數。 目 < 間接環， 間接環，及 r，如第19C 環集合登錄 N[1311]及 一 〇 登錄表資訊 該環樹之組 ^環樹 1900 訊。如前所 供一節點使 本機組態及 之間接環集 訊息及更新 應用訊息中 96 200803303 之間接環集合相關狀態，且可以從用於促進一環樹中之指 定通信型樣的訊息中存取間接環集合，該等通信型樣例如 為廣播、多播及任意傳播。 因此，在第19C圖中，n[1311]可能存取本機組態 1 92 1。從本機組態1 92 1，N [ 1 3 1 1 ]可搜尋間接環集合登錄 <R["111”]，N[llll]，···>表示 N[llll]係 R["llln]( N[1311] 及R[n3 11’，]之間接環）中登錄節點至少之一。N[1 3 11]還可 接收應用訊息1 9 7 1。N [ 1 3 1 1 ]可以從應用訊息1 9 7 1中搜尋 間接環集合資訊1 9 7 2。間接環集合資訊1 9 7 2可包含（或 可不包含）N [ 1 3 1 1 ]之間接環集合中之環的間接環集合狀 態。N[13 11]還可接收通信型樣專用訊息1 973。N[1 3 11]可 以從通信型樣專用訊息1 973中搜尋間接環集合狀態 1974。間接環集合狀態1974可包含（或可不包含）n[1311] 之間接環集合中之環的間接環集合狀態。 現在參考第19D圖，N[1311]可以在匯集通訊協定訊 息中搜尋及交換間接環集合狀態。由於N[llll]是R["llln] 之一成員，N[12ll]是R[”2il”]之一成員及N[1311]是 11[’’311”]之一成員，所以節點1^[1111]、川1211]、川1311] 中之每一節點也是R [" 11 ”]之成員。如前所述，作為一公共 環之成員的節點可以交換偵測訊息、更新訊息及更新回 應’以維護路由表資訊。因此，r[” 11 ”]之節點可交換偵測 訊息、更新訊息及更新回應，以維護R[”ll”]之路由表資 訊。間接環集合狀態可包含於在節點之間交換的偵測訊 息、更新訊息及更新回應訊息，以及其他匯集通訊協定及 97 200803303 應用訊息流量。

舉例而言，N[A11] ( R[，，ll’’]中N[1311]之一鄰居）可 向N [ 1 3 1 1 ]發送偵測訊息1 9 3 1 ’包括間接環集合狀態 1 932。從間接環集合狀態1 932，Μ1 31丨]可捷尋間接環集 合登錄 <R[，，3 1，，]，N[113 1]，···>，表示 N[113l]係 R[”31”] (N [ 1 3 1 1 ]及R [" 3 1 1 ” ]之間接環）中之一個登錄節點。間接 環集合登錄1932可係N[A11]之間接環集合登錄表中之間 接環集合登錄之完整或部分串列。N[1311]還可以向其鄰居 發送包括間接環集合登錄狀態之偵測訊息。舉例而言， !^[1311]可向^^斤11](11["11’’]中>1[1311]之一鄰居）發送 偵測訊息1 945，包括間接環集合狀態1 934。間接環集合登 錄1 934可包括來自間接環集合登錄表1 904中間接環集合 登錄之完整或部分串列。 N [ 1 3 11 ]還可發送和接收包括間接環集合相關資訊之 更新訊息及更新回應。舉例而言，N [ 1 3 1 1 ]可向 N [D j i ] (R[”ll"]中N[13 11]之一鄰居）發送更新訊息i 93 3，包括 間接環集合狀態1 934。N[D11]可藉由向NU331]發送包含 間接環集合登錄1 938之更新回應訊息ι 937作為回應。間 接環集合登錄1 93 8可係N[DU]之間接環集合登錄表中之 間接環集合登錄之完整或部分串列。類似地，N[1 3 u]可從 川〇1](11[，，11”]中川1311]之一鄰居）接收更新訊息1941， 包括間接環集合登錄1 942。間接環集合登錄1 942可係 N[C11]之間接環集合登錄表中之間接環集合登錄之完整 或部分串列。ΝΠ3Π]可藉由向N["C11,,]發送包含間接環 98 200803303 集合登錄1 9 3 4之更新回應訊息1 9 4 3作為回應。 一節點還可以從可用資源中接收間接環集合登錄表相 關之資訊，其（直接或間接）指示一間接環集合登錄不再 有效，例如，指示一登錄節點不能被聯絡。任何用於發送 間接環集合相關狀態之資源也可被用於發送一指示，其可 被解釋為一間接環集合登錄不再有效。因此’一節點可能 不時接收間接環集合相關狀態’其導致一或多個間接環集 合登錄被添加到其間接環集合登錄表’還接故指示’其可 能導致已經不再適合之一或多個間接環集合登錄被去除。 方法2000包括一操作（操作2003 ):根據所發現之間 接環集合登錄表資訊，用適當間接環集合登錄狀態更新該 間接環集合登錄表。每一適當間接環集合登錄狀態包括指 示該節點之一間接環，及該節點之間接環内之至少一相應 登錄節點。舉例而言，N[1311]可包括在第19C圖及第19D 圖中接收之間接環集合登錄表1 9 0 4中的任思、間接壞集合 登錄。N [ 1 3 1 1 ]也可從間接環集合登錄表1 9 0 4中去除被指 示為可能不再適當之間接環集合登錄（例如’在組態、匯 集通訊協定訊息、應用訊息或通信型樣專用訊息中指示）。 相應地，一節點之間接環集合登錄表可被更新’以適當地 反映一匯集聯合體之變化結構。 第19E圖說明引入鄰近之實例分割環樹i9〇〇之再一 視圖。第1 9 E圖中所述係間接環集合登錄表1 9 0 4，其可能 被根據第1 9 C圖及第1 9 D圖中交換之間接環集合狀態傳 播。第21圖說明一方法21 0 0之一實例流程圖，該方法用 99 200803303 於在一環樹中發送鄰近間通訊。下文針對第L 9 F圖中之節 點、環、訊息及資料描述方法2丨〇 〇。 方法2 1 0 0包括確定一節點將向該節點之間接環發送 一訊息之操作（操作2 1 0 1 )。舉例而言，N [ 1 3 1 1 ]可接收其 、 應向R[’’2’’]發送一訊息1 976之指示。表示應當向間接環發 V 送一訊息之指示可以從另一節點接收、可以作為路由邏輯 函數、N[13 11]之一應用程式、一多播設備、一廣播設備、 一任意傳播設備，等等。 方法2 1 00包含該節點存取一間接環集合登錄表之操 作（操作2 1 0 2 )，該間接環集合登錄表被組態用於健存該 節點之間接環集合登錄。每一間接環集合登錄被組態用於 指示該節點之一間接環，及該節點之間接環内之至少一相 應登錄節點。舉例而言，N[1 3 n]可存取間接環集合登錄表 1 9 04。間接環集合登錄表19〇4中之每一間接環集合登錄可 指示N[13 11]之一間接環，及N[1311]之該間捿環中之至少 一相應登錄節點。舉例而言，項<R [”丨丨丨”]，N [丨丨丨i ],.. > 才曰不R["lll”]係N[13ll]之一間接環，川1111；|係R [”j u"] 中之至少一登錄節點。 方法2100包括從該節點之間接環集合登錄表中為該 〜 間接環識別至少一間接環集合登錄之操作（操作2 1 03 )。 • 該等至少一間接環集合登錄之每一間接環集合登錄指示該 間接環之一至少一登錄節點。舉例而言，N [丨3丨丨]可以從間 接裱集合登錄表1 904中識別R[”2”]之項<r[”2，，]， N[U12]，..·>。項 <R[”2，，]，N[1112]， >指示 ιΐ2](可 100 200803303 能還有其他節點）係R[”2n]之一登錄節點。 根據包含於一被識別間接環集合登錄中所包含之 登錄節點數目（例如，當存在兩個或多個登錄節點時） 法2 1 00還可包括將一間接環之複數個登錄節點分解 錄節點之一適應子集之操作，有可能是分解1 一單一 登錄節點。舉例而言，可根據起始環與目標鄰近P之 接近程度、根據可選擇之節點重量、根據至一目的識 之接近程式來分解適當登錄節點之一子集，也可隨機 選擇。 方法2 1 0 0包括向至少一被指示登錄節點傳送訊 操作（操作 2 1 04 )。舉例而言，N [ 1 3 1 1 ]可以將訊息 發送至N [ 1 1 1 2]。向至少一節點發送一訊息之過程可 夠將一訊息發送到複數個節點中之全部登錄節點、發 一被分解至適當登錄節點子集中之每一登錄節點，或 送到一單一適當登錄節點。在一些具體實例例中，當 息未能發送至一登錄節點時，可以嘗試一或多個其他 節點。作為一嘗試失敗之結果，一發送節點還可能識 節點。 第22圖說明在一環樹中發送鄰近間通訊之方法 的實例流程圖。下文針對第1 9 F圖及第1 9 G圖中之笱 環、訊息及資料描述方法2200。 方法2200包括確定一起始節點希望向一目的節 由一訊息之操作（操作220 1 )，該目的節點最接近於 樹中目標鄰近環中一既定節點識別碼。該目標鄰近璟 相應 ，方 至登 適當 間的 別碼 進行 息之 1976 以能 送到 者發 —訊 登錄 別新 2200 ί點、 點路 * ^ % :可以 101 200803303 疋該起始節點之一間接環或者該起始節點之一間接環之子 環。舉例而言’ N[1 3 11]可接收其應向r[” 1221”](該目標 鄰近環）朝向識別碼30路由一訊息1 998之指示。表示應 當向間接環或一間接環之子環發送一訊息之指示可以從另 一節點接收、從關於N [ 1 3 1 1 ]之一應用程式、一多播設備、 一廣播設備、一任意傳播設備，等等。 方法2 2 0 〇包括識別一或多個登錄節點之操作（操作 22 02 )，已知該等登錄節點為該目標鄰近環與該目標鄰近環 之上階環中至少之一的成員節點。舉例而言，N [ 1 3 1 1 ]可識 別N[4122 1](具有節點識別碼56 )作為R[”l 221"]之一登 錄節點。各種不同機制可用於識別 N[41221]。N[1311]可 查閱本機知識，以嘗試識別該鄰近目標環中之一登錄節 點。舉例而言，N [ 1 3 1 1 ]可查閱快取及組態 1 902，以嘗試 識別R[nl 221”]之一登錄節點。 N[1311]還可查閱間接環集合登錄表，以確定該鄰近目 標環之上階環中的登錄節點（例如，在未確定該目標鄰近 環中之登錄節點時）。子環R [π 3 2 1π ]可能促進節點N [4 3 2 1 ] 作為R[n21n]之一登錄節點。類似地，R[n222l"]可能促進 節點 N[12221]作為 R["221”]之一登錄節點。當未識別 R[1221]中一登錄節點時，N[1311]可嘗試識別 R["221”]中 之一登錄節點，例如N[ 12221]。N[ 1331]還可嘗試識別 R[n21，，]中之一登錄節點，例如N[4321]。 在未識別一指定目標鄰近中之登錄節點時，一節點嘗 試識別於更接近上階環中之登錄節點，之後才嘗試識別另 102 200803303 一上階環中（從該指定目標鄰近之角度觀察）的登錄節點。 舉例而言，在未識別R[” 1221，，]中之一登錄節點時，N[1 3 11] 可以首先嘗試識別 R[n221"]中之登錄節點。在未識別 R[” 22 1"]中之一登錄節點時，N[1 3 11]可以隨後嘗試識別 R[n2 1M]中之登錄節點。 N [ 1 3 1 1 ]還可利用啟動載入機制，例如’種子節點。舉 例而言，N [ 1 3 1 1 ]可以向一習知匯集點（例如，匯集點 N [765 1 ])路由一登錄節點查閱要求，要求習知（已註冊） 登錄節點（種子節點作為實例）。回應一查閱要求，一匯集 點可返回（發送）包括任意習知登錄節點之查閱回應訊息。 舉例而言，可以從匯集點N [7 6 5 1 ]向N [1 3 1 1 ]查閱回應 1997。查閱回應1997可包括用匯集節點N[7651]註冊之任 意登錄節點的位置。 此等機制之一或多種機制可將N [422 1]識別為一 R[n221 ’’]中之登錄節點。 在一些具體實施例中，一些登錄節點識別機制首先被 利用，之後再利用其他登錄節點識別機制。舉例而言’一 發送節點可以查閱本機知識’然後嘗試識別該目標環之一 上階環中之登錄節點，或者路由一登錄節點查閱要求。在 此等相同實施例中，一發送節點在路由登錄節點查閱要求 之前，還嘗試識別該目標環之上階環中的登錄節點。但是， 在其他具體實施例中，可採用不同順序利用登錄節點識別 機制，或將其省略。 方法2 2 0 0包括向該被識別登錄節點發送訊息之操作 103 200803303 (操作2 2 0 3 )。該訊息指示該被登錄節點應备該訊息解析 至一節點，該節點之節點識別碼最接近該目歡鄰近環中之 一被指示目的節點。舉例而言，由實線表示，：N [ 1 3 1 1 ]可向 川41221](11[”1221”]之一登錄節點，具有節粟去識別碼56) 發送訊息1 9 9 8，其指示該訊息將被解析至節點？識別瑪3 〇。 N [4 1221]可以存取其路由表及鄰域，以確定避節點識別石馬 30之最接近節點識別碼，其瞭解N[6 1221]具會節點識別瑪 25。類似地，N[61 221]可以存取其路由表及離域，以確定 距節點識別碼3 0之最接近節點識別碼，其暸解N [ 7 I 2 2 1J 具有節點識別碼28。N [71221]可查詢其表及/或鄰域，以 確定其節點識別碼（節點識別碼28 )是最接迕節點識別石馬 3 0之習知節點識別碼，以傳遞該訊息。 前述路由演算法也可被用於路由 R[" 221”]中之訊卓 1 998 〇 當一訊息被發送至作為一上階環或目標_近環之成員 的被識別登錄節點時，方法2200可被遞迴應用於該被識別 登錄節點。即，該上階環中之被識別登錄節點又可嘗試識 別該目標鄰近環中之一登錄節點。舉例而言，如點線所示， 方法2200之一應用可導致訊息1 998被發迸至登錄節點 N[ 12221 ]( R「22 1’’]之登錄節點由子環r[ ”2221，，]貢獻）。 N[12221](從R[’’222 1n]之角度）可被識別為r[” 1221，，]之 登錄節點。因此，在N[ 1222 Π對方法2200之一遞迴應用 可導致訊息I"8被發送至^41221]。 如果該上階環中之被識別登錄節點不知道該目標鄰近 104 200803303 環中之一登錄節點’該被識別登錄節點可嘗試識別更接近 該目標鄰近之另一上階環中的登錄節點。該上階環中之登 錄節點於是將該訊息轉遞至更接近該目標鄰近環之階環中 的登錄節點。 舉例而言，如虛線所示，方法2 2 0 0之一應用可導致訊 息1 9 9 8被發送至登錄節點N [4 3 2 1 ]( R [ ” 2 1 ·’ ]之登錄節點由 子環 R[，，321 ’，]貢獻）。但是，Ν[43 2 1 ](從 R[n3 21 ’’]之角度） 也許不能識別R [ ’’ 1 2 2 Γ’ ]之登錄節點。因此’ N [ 4 3 2 1 ](從 R[，，3 21，，]之角度）可識別 R[，，221 Ί之登錄節點。相應地， 在N[ 12221]對方法2200之一第一遞迴應用可導致訊息 1 998被發送至N[1 2221]。在N[ 1 222 1 ]對方法2200之一第 二遞迴應用可隨後導致訊息1998被發送至^^41221]。 但是，如果N[432 1]的確識別R[n1221”]中之一登錄節 點，其可將訊息1 998直接發送至該登錄節點。因此，在適 當時，一上階環中之登錄節點可將一訊息轉遞至該目標鄰 近環或該目標鄰近環之更接近上階環中之一登錄節點（該 更接近上階環通常在該轉遞登錄節點之間接環集合中）。如 上所述，在適當時，該更接近上階環中之登錄節點可將該 訊息轉遞至該目標鄰近環或該目標鄰近環之又一更接近上 階環中之一登錄節點（該更接近上階環通常在該轉遞“更 接近，，登錄節點之間接環集合中）。此過程可重複（例如， 經由遞迴應用方法2200 )，直到到達該目標鄰近環登錄節 點為止。 在到達該目標鄰近環時，前述路由演算法可被用於在 105 200803303 該目標鄰近環中路由該訊息。 第6圖及以下討論意欲對適於實施本發明之計算環境 進行簡單、一般性描述。儘管未受要求’但將在由電腦系 統執行之電腦可執行指令（例如’程式模組）之一般環境 中描述本發明。一般來說，程式模組包括常式、程式、物 件、組件、資料結構，等等，其執行特定任务或實施特定 抽象資料類型。本文揭示電腦可執行指令、相關資料結構 以及程式模組，其代表執行本發明之操作的程式代碼構件 實例。 參考第6圖，一實施本發明之實例系統包括採用電腦 系統620之形式的通常計算裝置，包括一處理單元621、 一系統記憶體6 2 2及一系統匯流排6 2 3 ’其將^包括糸統記 憶體6 2 2之各種系統元件耦接至處理單元6 2 1。處理單元 6 2 1可執行設計用於實施電腦系統6 2 0之特徵（包括本發 明之特徵）的電腦可執行指令。系統匯流排6 2 3可係若干 匯流排結構之任一結構，包括一記憶體匯流排或記憶體控 制器、一周邊裝置部級及一本機匯流排，其使用各種匯流 排架構之任意一種。系統記憶體包括唯言買記憶體 (“ ROM” ）624及隨機存取記憶體（“ RAM” ）625。一 基本輸入/輸出系統（“ BIOS” ）626，包括用於幫助在電 腦系統6 2 0中之元件間傳播資訊的常式（例如’在啟動期 間），可被儲存於唯讀記憶體624中。 電腦系統620還可包括··用於向磁硬碟639寫入資料 及從中讀取資料之磁硬碟機 627;用於從可移除磁碟 629 106 200803303 寫入資料及從中讀取資料之磁碟機6 2 8 ;以及用於從可移 除光碟631(例如，一光碟或其他光學媒體）讀取資料或 向其寫入資料之光碟機630。該磁硬碟機627、磁碟機628 及光碟機639被各別藉由硬磁機介面632、磁碟機介面633 及光碟機介面634連接至該系統匯流排623。該等驅動器 ·,- 及其相關電腦可讀媒體為該電腦系統620之電腦可執行指 令、資料結構、程式模組及其他資料提供了非揮發性儲存。 ，、 儘管本文所述之實例環境採用磁硬碟機6 3 9、可移除磁碟 629及可移動光碟631，但也可使用其他類型之電腦可讀媒 體來儲存資料，包括磁帶、快閃記憶體卡、數位通用光碟、 Bernoulli卡匣、隨機存取記憶體、唯讀記憶體，等等。 包括一或多個程式模纽之程式代碼構件可被儲存在硬碟 639、磁碟629、光碟631、唯讀記憶體624或隨機存取記 憶體625上，該等構件包括一作業系統63 5、一或多個應 用&式6 3 6、其他程式模組6 3 7及程式資料6 3 8。一使用者 可經由鍵盤640、指標裝置642或其他輪入裝置（未示出）， U 例如一麥克風、搖桿、遊戲台、掃描儀或其他裝置向電腦 系統620中輸入命令及資訊。此等及其他輸入裝置可被經 由耦接至系統匯流排623之輸入/輸出介面646連接至處理 —· 單元Ml。輸入/輪出介面646邏輯上代表種類眾多之不同 • 介面中的任何一個，例如，一串列埠介面、一 PS/2介面、 一平行埠介面、一通用串列匯流排（“ USB” ）介面，或 一電機電子工程師學會（IEEE) 1 394介面（即 介面）’甚至可以在邏輯上代表不同介面之組合。 107 200803303 一監視器647或其他顯示裝置也被經由視^訊介面648 連接至系統匯流排6 2 3。揚聲器6 6 9或其他聲頻輸出裝置 也被經由聲頻介面6 4 9連接至系統匯流排6 2 $。其他周邊 輸出裝置（未示出），例如印表機，也可被連接至電腦系統 620 ° 電腦系統6 2 0可被連接至網路’例如’ 一辦公室範圍 或企業範圍電腦網路、一家庭網路、一企業内部網路及/ 或網際網路。電腦系統620可經由此等網路與外部資源交 換資料，例如，遠端電腦系統、遠端應用程式，及/或遠端 資料庫。 電腦系統6 2 0包括網路介面6 5 3 ’電腦系統6 2 0經由 網路介面6 5 3從外部資料源接收資料及/或向外部資源傳 輸資料。如第6圖所述，網路介面6 5 3促進經由鏈接6 5 1 與遠端電腦系統6 8 3交換資料。網路介面6 5 3可以在邏輯 上代表一或多個軟體及/或硬體模組’例如’ 一網路介面卡 及相慶的硬體網路驅動介面規格（“ N D1S ” ）堆疊。鏈接 6 5 1代表一網路之一部分（例如’一乙太網路分段）’遠端 電腦系統6 8 3代表該網路之一節點。 類似地，電腦系統6 2 0包括輸入/輸出介面6 4 6，電腦 系統6 2 0經由該輸入/輸出介面6 4 6從外部資料源接收資料 及/或向外部資源傳輸資料。輸入’輸出介面6 4 6經由鏈接 659被耦接至數據機654 (例如，一標準數據機、一電纜數 據機或數位用戶線（“ DSL” ）數據機）’電腦系統620經 由數據機654從外部資料源接收資料及/或外部資料源傳 108 200803303 輸資料。如第6圖所述，輸入/輸出介面646及數據機654 促進經由鏈接6 5 1與遠端電腦系統6 9 3交換資料。鏈接6 5 2 代表一網路之一部分，遠端電腦系統6 9 3代表該網路之一 節點。 儘管第6圖代表本發明之一適當操作環境，但本發明 之原理亦可實施於任意能夠實施本發明之原理的系統中 (必要時，可以進行適當修改）。第6圖中所說明之環境僅 係說明性環境，決不代表甚至是各種環境之一小部分’本 發明之原理可以在該等環境中實施。 根據本發明’節點、應用層及其他較低層，以及相關 資料（包括路由表及節點識別碼）可被儲存於與電腦系統 6 20相關之任意電腦可讀媒體，且可從中訊數該等相關資 料。舉例而言，此等模組之部分及相關程式資料之部分可 被包含於作業系統6 3 5、應用程式6 3 6、程式模組6 3 7及/ 或程式資料6 3 8 ’儲存於系統記憶體6 2 2中。 當一大量資料儲存裝置，例如’磁硬碟 6 3 9，被耦接 到電腦系統620，此等模組及相關程式資料亦可儲存於大 量資料儲存裝置中。在網路環境中，相對於電腦系統620 所述之程式模組或其部分可被儲存於遠端内在儲存裝置 中，例如，系統記憶體及/或與遠端電腦糸統6 8 3及/或遠 端電腦系統693相關之大量資料儲存裝置。此等模組之執 行可在一分散式環境中執行，如前所述。 在不背離本發明之精神及基本特徵的情況下，可以採 用其他特定形式實施本發明。所述實施例在任何方面都應 109 200803303 當被認為是說明性的，而非限制性的。因此’本發明之範 圍由隨附申請專利範圍指示，而不是由上述說明指示。在 該等申請專利範圍之等價含意及範圍内的所有變化都包含 於此範圍内。 【圖式簡單說明】 為了描述可獲得上述及其他好處及特徵之方式，將參 考在隨附圖式中所說明之特定具體實施例’對於以上簡述 之發明進行更具體之描述。請理解’此等圖式僅描述典型 具體實施例，因此不應理解為對申請專利範圍之限制，將 利用隨附圖式描述及解釋具體實施例，包括附加特徵及細 節。 第1圖說明一聯合體基礎建設之實例。 第2圖說明一電腦架構之實例’其促進將要求間接路 由至夥伴。 第3圖說明一聯合體基礎建設中節點之間的實例二進 位關係，該基礎建設採用有序串列及相應環之形式。 第4圖說明一實例環之環，其促進鄰近路由。 第5圖說明一引入鄰近之實例分割環樹，其促進鄰近 路由。 第5 A圖說明第5圖之引入鄰近之實例分割環樹，其 具有第5圖分割環樹一些部分的附加細節。 第6圖說明一適用於本發明之原理的操作環境。 第7圖說明用於填充一節點路由表之方法的實例流程 圖，該方法考慮了鄰近準則。 110 200803303 第8圖說明用於分割一聯合體基礎建設節點之方法的 實例流程圖。 第9圖說明用於填充一節點路由表之方法的實例流程 圖。 第10圖說明用於以數字方式向一目的節點路由一訊 息之方法的實例流程圖。 第11圖說明用於以鄰近方式向一目的節點路由一訊 息之方法的實例流程圖。 第1 2 A圖說明在一現有聯合體内建立成員關係之一節 點實例。 第1 2B圖說明在一聯合體基礎建内交換汛息之節點的 實例。 第1 3圖說明用於在一聯合體基礎建設内建立成員關 係之方法的實例流程圖。 第14圖說明用於在一聯合體基礎建設内維持成員關 係之方法的實例流程圖。 第1 5圖說明用於搜尋另一節點之活躍度資訊之方法 的實例流程圖。 第1 6圖說明一訊息模型及相關處理模型之實例。 第17圖說明許多可發生於一功能層及一應用層之間 的活躍度互動之實例。 第1 8圖說明在一環上之節點間路由之訊息的實例，該 等訊息構成一要求-回應訊息交換型樣之部分。 第1 9 A圖說明一引入鄰近之實例分割環樹，其促進鄰 111 200803303 近間通信 第19B圖說明第ι9λ面 Α圖中之引入鄰近之實例分割環樹 之另一視圖。 第19C圖說明第 Α圖中之引入鄰近之實例分割環樹 之一部分的分割視圖。 第19D圖說明第 Α圖中之引入鄰近之實例分割環樹 之中間環的放大視圖。 第19Ε圖說明第間 Α圖中之引入鄰近之實例分割環樹 之又一視圖。 第19F圖說明第 圖中之引入鄰近之實例分割環樹 之再一視圖。 第19G圖說明第19 i ^^圖之一部分的放大視圖。 第2 0圖說明為維嘴 m濩％樹中一節點維護一間接環集合 之方法的實例流程圖。 第 2 1圖說明在— ^樹中發送鄰近間通訊之方法的實 例流程圖。 第22圖說明在一環樹中發送鄰近間通訊之另一方法 的實例流程圖。 【主要元件符號說明】 1、 2、 3、 4、 11、 21、 31、 40、 41、 51、 111、 211、 221、 311、 321 、 322、 401、 402、 403、 404、 421、 511、 512、 513、 514、 521、 522、 523、 531、 532、 533、 541、 542 、 543 、 544 、 551 、 552 、 561 、 562 、 572 、 1221 環 30、 46、 50、 59、 64、 71、 76、 83、 98、 101、 102、 112 200803303 103、135、250、151、153、171、172、174、180、182、 183、184、188、190、193、194、198、218、1111、1112、 1121、 1131、 1311、 1801、 1802、 1803、 1804、 1805、 1806、 2221 、 3221 、 6521 、 8004 、 8221 、 8223 、 8651 節點 100 聯 合 體 基 礎 建 設 12 1、 122、 123 應 用 層 13卜 132、 133 較 低 層 141、 142 > 143 匯 集 通 訊 協 定 堆 疊 200 電 腦 架 構 201 註 冊 要 求 204 成 功 訊 息 205 註 冊 要 求 206 成 功 訊 息 207 官 告 208 註 冊 資 訊 註 冊 要 求 210 成 功 訊 息 214 > 216 回 應 訊 息 231 膝 上 型 電 腦 233 工 作 站 234 伺 服 器 236 印 表 機 237 訊 息 代 理 器 241 訊 息 閘 道 242 個 人 電 腦 113 200803303 243 工作站 304 鏈接串列 306 環 40 0 環之環 500 分割環樹 501 根環 571 第一管理域界限準則 573 第一組織界限準則 581 第二管理域界限準則 583 第二組織界限準則 620 電腦糸統 621 處理單元 622 系統記憶體 623 糸統匯流排 624 唯讀記憶體 625 隨機存取記憶體 626 基本輸入/輸出系統 627 磁硬碟機 628 磁碟機 629 可移除磁碟 630 光碟機 631 可移除光碟 632 硬磁機介面 633 磁碟機介面 114 200803303 634 光 碟 機 介 面 635 作 業 系 統 636 應 用 程 式 637 程 式 模 組 638 程 式 資 料 639 磁 硬 碟 機 640 鍵 盤 642 指 標 裝 置 646 輸 入 /輕 !w llj J ffi 介 ‘面 647 監 視 器 648 視 訊 介 面 649 聲 頻 介 面 651 鍵 接 652 鏈 接 653 網 路 介 面 654 數 據 機 659 鍵 接 683 遠 端 電 腦 系 統 693 遠 端 電 腦 系 統 1201 加 入 訊 息 1202 加 入 回 應 訊 息 1203 同 步 要 求 1204 同 步 回 應 1206 環 115 200803303 1207 更新回應訊息 1216 更新 1219 脫離訊息 1600 訊息模型及相關處L理模型 1601 同步要求訊息 1602 應用資料 1603 鄰域狀態同步事半 1604 鄰域狀態要求功紇 1607 應用資料 1608 同步回應訊息 1609 偵測訊息 1611 偵測訊息 1612 偵測訊息 1622 應用資料 1641 同步回應訊息 165 1 功能層 1652 應用層 1701 訂閱活躍度事件 1702 撤銷活躍度訂閱 1703 端點當機事件 1704 節點當機 1706 發送活躍度事件 1751 功能層 1752 應用層 116 200803303 1811 要 求 訊 息 1816 回 應 1817、 1818 、 1819 、 1820 > 1821 狀 態 訊 1900 分 割 環 樹 1901 根 環 1902 快 取 及 組 態 1903 訊 息 1904 間 接 環 集 合 登 錄 表 1906 查 閱 要 求 1907 查 閱 回 應 1921 本 機 組 態 193 1 偵 測 訊 息 1932 間 接 環 集 合 登 錄 193 3 更 新 訊 息 1934 間 接 環 集 合 狀 態 1937 更 新 回 應 訊 息 1938 間 接 環 集 合 登 錄 1941 更 新 訊 息 1942 間 接 環 集 合 登 錄 1943 更 新 回 應 訊 息 1945 偵 測 訊 息 1971 應 用 訊 息 1972 間 接 環 集 合 資 訊 1973 通 信 型 樣 專 用 訊 息 117 200803303 1974 間接環集合狀態 1976 訊息 1998 訊息 765 1 匯集點 118

Claims (1)

1. 200803303 十、申請專利範圍： 1 . 一種於一電腦系統上且在一環樹中傳送鄒近間通訊之 方法，該方法包括： 決定步驟，其係用於決定一節點傳送一訊患至該節點之 一特定的間接環（collateral ring )； 存取步驟，其係用於該節點存取一間接環嚷合登錄表， 該間接環集合登錄表被組態用於儲存該節點之間接環集合 登錄，每一間接環集合登錄被組態用於指示該節點之一間 接環，及進入該節點之該間接環之相應的至少一登錄節點； 識別步驟，其係用於識別來自該節點之間接環集合登錄 表的該特定的間接環之至少一間接環集合登錄’該至少一 間接環集合登錄之各者指示該特定的間接環之至少一登錄 節點；及 傳送步驟，其係用於傳送該訊息至至少一經指示的登錄 節點。 2 ·如申請專利範圍第1項所述之方法，.其中決定一節點傳 送一訊息至該節點之一特定的間接環的步驟包含接收 步驟，其係用於自與該節點相關之一應用裎式接收一指 示0 3.如申請專利範圍第1項所述之方法’其中決定一節點傳 送一訊息至該節點之一特定的間接環的步驟包含接收 步驟，其係用於自該環樹中之另一節點接收一指示。 119 200803303 4 ·如申請專利範圍第1項所述之方法，其中決定一節點傳 送一訊息至該節點之一特定的間接環的步驟包含存取 間接環/登錄節點項步驟，其係用於該節沒存取一或多 個間接環/登錄節點項。 5 ·如申請專利範圍第1項所述之方法，其中蠘別來自該節 點之間接環集合登錄表的該特定的間接環之至少一間 接環集合登錄的步驟包含識別間接環/鲞錄節點項步 驟，其係用於識別確定該特定的間接環及達入該特定的 間接環之複數登錄節點的一間接環/登錄節點項。 6. 如申請專利範圍第5項所述之方法，其更包含： 解析步驟，其係用於將該複數登錄節點解柯至該等登錄 節點之一適當子集合。 7. 如申請專利範圍第5項所述之方法，其更包含： 解析步驟，其係用於將該複數登錄節點解析至一單一適 當登錄節點。 8 · —種於一電腦系統上且在一環樹中傳送鄰近間通訊之 方法，該方法包括： 決定步驟，其係用於一節點決定一起始節點欲向一目的 節點路由一訊息，該目的節點最接近該環樹内一目標鄰近 120 200803303 環的一既定節點識別碼·’ 識別步驟，其係用於識別一或多個登錄節激，其中已知 該等登錄節點為該目標鄰近環與該目標鄰近琴之一上階環 中至少之一者的成員節點；及 傳送步驟，其係用於將該訊息傳送至一經_別之登錄節 點，該訊息指示該經識別登錄節點將該訊息解析至一節 點，該節點之節點識別碼最接近該目標鄰近殘中之一經指 示的目的節點。 9 ·如申請專利範圍第8項所述之方法’其中钱一節點決定 一起始節點欲向最接近該環樹内一目標鄰近環的一既 定節點識別碼之一目的節點路由一訊息的步驟包含存 取步驟，其係用於該節點存取一起始節點欲向最接近該 環樹内一目標鄰近環的一既定節點識別碼之一目的節 點路由一訊息的一指示。 10.如申請專利範圍第9項所述之方法，其中該節點存取一 起始節點欲向最接近該環樹内一目標鄰近環的一既定 節點識別碼之一目的節點路由一訊息的一指示之步驟 包含接收步驟’其係用於該節點接收一傳送節點欲向最 接近且為該傳送節點之一間接環之一目標鄰近環中的 一既定節點識別碼之一目的節點路由一訊息的一指示。 1 1 .如申請專利範圍第9項所述之方法’其中該節點存取一 121 200803303 起始節點欲向最接近該環樹内一目標鄰近環的一 節點識別碼之一目的節點路由一訊息的~指示之 包含接收步驟，其係用於該節點接收一傳送節點欲 接近且為該傳送節點之一間接環之一子環之一目 近環中的一既定節點識別碼之一目的節黑占路由一 的一指示。 12.如申請專利範圍第9項所述之方法，其中存取一起 點欲向最接近且為該節點之間接環之一目標鄰近 之一既定節點識別碼之一目的節點路由—訊息的 示之步驟包含接收指示步驟，其係用於接收來自與 點相關之一應用程式的一指示。 1 3 ·如申請專利範圍第9項所述之方法’其中存取一起 點欲向最接近且為該節點之間接環之一目標鄰近 之一既定節點識別碼之一目的節點路由一訊息的 示之步驟包含接收另一訊息中之指示步驟，其係用 收另一訊息中的一指示。 14.如申請專利範圍第13項所述之方法，其中接收另一 中的一指示之步驟包含自該環樹中之另一節點接 訊息中之一指示的步驟。 1 5.如申請專利範圍第9項所述之方法，其中該一節點 既定 步驟 向最 標鄰 訊息 始節 環中 一指 該節 始節 環中 一指 於接 訊息 收一 存取 122 200803303 既 步 近 S Λ-/Γ 即 識 接 /τ/Γ 即 § 定 既 該 標 該 者 步 的 一起始節點欲向最接近該環樹内一目標鄉近環的一 定節點識別碼之一目的節點路由一訊息的一指示之 驟包含接收步驟，其係用於接收一起始節點欲向最接 該起始節點之一間接環中之一既定節點識別碼之一 的節點路由一訊息的一指示。 ，7 1 6 .如申請專利範圍第9項所述之方法，其中存取一起始 點欲向最接近該環樹内一目標鄰近環的一既定節點 別碼之一目的節點路由一訊息的一指示之步驟包含 收步驟，其係用於接收一起始節點欲向最接近該起始 點之一間接環中之一子環的一既定節點識別碼之一 的節點路由一訊息的一指示。 1 7.如申請專利範圍第8項所述之方法，其中該一節點決 一起始節點欲向最接近該環樹内一目標鄰近環的一 定節點識別碼之一目的節點路由一訊息的步驟包含 起始節點決定該起始節點欲向最接近該環樹内一目 \ / ' 鄰近環的一既定節點識別碼之一目的節點路由一訊息 1 8.如申請專利範圍第8項所述之方法’其中識別已知為 目標鄰近環與該目標鄰近環之一上階環中至少之一 # 的成員節點的一或多個登錄節點之步驟包含查閱 驟，其係用於在該節點查閱本地知識，藉以識別該目 鄰近環中之任何節點。 123 200803303 1 9.如申請專利範圍第8項所述之方法’其中識別已知為該 目標鄰近環與該目標鄰近環之一上階環和至少之一者 的成員節點的一或多個登錄節點之步驟包含識別登錄 節點步驟，其係用於識別為該目標鄰近環之一成員的一 登錄節點。 2 0.如申請專利範圍第8項所述之方法，其中識別已知為該 目標鄰近環與該目標鄰近環之一上階環令至少之一者 的成員節點的一或多個登錄節點之步驟包含識別登錄 節點步驟，其係用於識別為該目標鄰近環之一上階環之 一成員的一登錄節點。 21 ·如申請專利範圍第20項所述之方法’其中該識別為該目 標鄰近環之一上階環之一成員的一登錄節點的步驟包 含識別為該目標鄰近環之最接近上階環之該目標鄰近 環的一上階環之一成員的一登錄節點之步驟。 22.如申請專利範圍第8項所述之方法，其中識別已知為該 目標鄰近環與該目標鄰近環之一上階環中至少之一者 的成員節點的一或多個登錄節點之步驟包含： 查閱步驟，其係用於查閱一間接環集合登錄表以識別位 於該目標鄰近環的一上階環之一傳送節點的間接環集合登 錄表中的一節點；及 傳送訊息步驟，其係用於將該訊息傳送至該上階環中之 124 200803303 該經識別的節點。 23·如申請專利範圍第22項所述之方法，其更电含： 閱 該 近 該 者 步 識 利 之 查閱本地知識步驟，其係用於該上階環中之該節點查 本地知識，藉以識別該目標鄰近環中之任何辭點。 24·如申請專利範圍第22項所述之方法，其更岜含： 查閱間接環集合登錄表步驟，其係用於該上階環中之 節點查閱一間接環集合登錄表，藉以識別位在該目標鄰 環的該最接近上階環之該經識別節點的間接環集合中的 進一步節點；及 傳送該訊息至該進一步節點的步驟。 2 5 ·如申請專利範圍第8項所述之方法，其中識別已知為 目標鄰近環與該目標鄰近環之一上階環中至少之一 的成員節點的一或多個登錄節點之步驟包含利用 驟，其係用於該節點利用一登錄節點目錄機制，藉以 別已知為該目標鄰近環之一成員節點的一登錄節點。 26.如申請專利範圍第25項所述之方法，其中該傳送節點 用一登錄節點目錄機制以識別已知為該目標鄰近環 一成員節點的一登錄節點之步驟包含： 路由步驟，其係用於路由一登錄節點查閱請求訊息至 集結點；及 125 200803303 接收登錄節點查閱請求訊息步驟’其係用汾接收相應於 該查閱請求之一登錄節點查閱回應’該登錄_點查閱回應 包含複數登錄節點。 2 7 .如申請專利範圍第2 6項所述之方法’其中手妾收相應於該 查閱請求之一登錄節點查閱回應的步驟包含自該集結 點接收一登錄節點查閱回應的步驟。 2 8 .如申請專利範圍第2 6項所述之方法’其中轾收相應於該 查閱請求之一登錄節點查閱回應的步驟包含接收包括 被註冊以一登錄節點目錄機制之一或多個登錄節點的 一登錄節點查閱回應的步驟。 2 9 .如申請專利範圍第2 8項所述之方法’其中接收包含被註 冊以一登錄節點目錄機制之一或多個登錄節點的一登 錄節點查閱回應的步驟包含接收包括被言主冊以該集結 點之一或多個登錄節點的一登錄節點查閱回應的步驟。 3 0.如申請專利範圍第2 8項所述之方法’其中接收包含被註 冊以一登錄節點目錄機制之一或多個登錄節點的一登 錄節點查閱回應的步驟包含接收包括本身註冊以該集 結點之一登錄節點的一登錄節點查閱回應的步驟。 3 1.如申請專利範圍第2 8項所述之方法’其中接收包含被註 126 200803303 冊以一登錄節點目錄機制之一或多個登錄節點的一登 錄節點查閱回應的步驟包含接收包括由另一方而被註 冊以該登錄節點目錄機制之一登錄節點的一登錄節點 查閱回應的步驟。 3 2.如申請專利範圍第3 1項所述之方法，其中接收包括由另 一方而被註冊以該登錄節點目錄機制之一登錄節點的 一登錄節點查閱回應的步驟包含接收包括由另一集節 點而被註冊以該登錄節點目錄機制之一登錄節點的一 登錄節點查閱回應的步驟。 33.如申請專利範圍第26項所述之方法，其更包含： 接收針對一登錄節點之一登錄節點註冊請求的步驟；及 以該集節點註冊該登錄節點的步驟。 3 4. —種用於一電腦系統之電腦程式產品’該電腦程式產品 用於實施一在一環樹中傳送鄰近間通訊之方法，該電腦 程式產品包括一或多個電腦可讀儲存媒體’該電腦可讀 儲存媒體其中儲存了電腦可執行指令’在由一處理器執 行該等可執行指令時，導致一節點執行以下各項： 決定^一節點傳送^一訊息至該節點之一特疋的間接壤， 存取一間接環集合登錄表，該間接環集合登錄表被組態 用於儲存該節點之間接環集合登錄’每一間接環集合登錄 被組態用於指示該節點之一間接環，及進入該節點之該間 127 200803303 接環之相應的至少一登錄節點； 識別來自該節點之間接環集合登錄表的矮特定的間接 環之至少一間接環集合登錄，該至少一間接綠集合登錄之 各者指示該特定的間接環之至少一登錄節點；及 傳送該訊息至至少一經指示的登錄節點。 3 5 .如申請專利範圍第3 4項所述之電腦程式產品，其中該電 腦可讀儲存媒體包括系統記憶體。 36.如申請專利範圍第34項所述之電腦程式產品，其中該電 腦可讀儲存媒體包括一磁碟。 3 7. —種用於一電腦系統之電腦程式產品’該電腦程式產品 用於實施一在一環樹中傳送鄰近間通訊之方法，該電腦 程式產品包括一或多個電腦可讀儲存媒體，該電腦可讀 儲存媒體其中儲存了電腦可執行指令’在由一處理器執 行該等可執行指令時，導致一節舜執行以下各項·· 決定一起始節點欲向一目的節點路由一訊息，該目的節 點最接近該環樹内一目標鄰近環的一既定節點識別碼； 識別一或多個登錄節點，其中已知該等登錄節點為該目 標鄰近環與該目標鄰近環之一上階環中至少之一者的一成 員節點；及 將該訊息傳送至一經識別之登錄節點，該訊息指示該經 識別登錄節點將該訊息解析至一節點，該節點之節點識別 128 200803303 碼最接近該目標鄰近環中之一經指示的目的辭點。 3 8 ·如申請專利範圍第3 7項所述之電腦程式產品，其中該電 腦可讀儲存媒體包括系統記憶體。 3 9 ·如申請專利範圍第3 7項所述之電腦程式產品，其中該電 腦可讀儲存媒體包括一磁碟。 129