用於在對等覆蓋網絡中事件分發和路由的方法和裝置的製作方法

2023-05-11 18:21:36

專利名稱：用於在對等覆蓋網絡中事件分發和路由的方法和裝置的製作方法
技術領域：
本申請總體上涉及覆蓋網絡(overlay network)的操作，更具體地，涉及用於在對 等覆蓋網絡中的事件分發(distribution)和路由的方法和裝置。
背景技術：
本文將在沒有基於伺服器的架構的情況下成員節點在其中獲得服務的網絡稱為 「對等(peer-to-peer)」覆蓋網絡。在對等覆蓋網絡中，對等節點彼此協同操作以提供服務 並維持網絡。對等覆蓋網絡可以構造在諸如利用網際協議(IP)網絡之類的底層網絡的頂 部上。通常，在對等覆蓋網絡上的事件的路由呈現出與路由等待時間、帶寬利用率和路 由表大小有關的折衷。例如，在對事件進行路由時希望等待時間較短。然而，為了實現較短 的等待時間，就會導致產生較大的路由表，這就與參與到覆蓋網絡中的節點的可用資源不 匹配。而且，較大的路由表會導致較差的帶寬利用率，因為需要相當大的帶寬來通過覆蓋網 絡傳輸路由表及隨時間出現的任何變化。傳統系統利用了試圖管理上述折衷的多種技術。例如，一些系統利用了非常 大的路由表，如上所述，其會減小等待時間，但也會使在參與節點處的資源變得緊張或 者超出該資源。其它系統利用了覆蓋網絡中的特定節點，這些特定節點對於事件傳播 (dissemination)具有更大的響應度。然而，在這些特定節點上的帶寬需求是相當大的，以 致於需要合理地提供它們。不幸的是，傳統系統所使用的技術會導致在不同節點上的路由表並不一致，這就 引起了傳播延遲。此外，不同路由表會具有不同的長度和條目，這會導致以不同的傳播樹來 從同一事件發信方傳播事件。而且，不同路由表會導致「空洞」，以致於一些節點可能不會接 收到所傳播的事件。因此，希望具有一種用於在對等覆蓋網絡中的事件分發和路由的有效機制，其克 服了與傳統系統有關的問題。

發明內容
在一個或多個方案中，為在對等覆蓋網絡中的事件分發和路由提供了包括方法和裝置的事件分發系統。在一個方案中，提供了一種用於在包括多個節點的對等覆蓋網絡中的事件分發和 路由的方法。該方法包括確定該對等覆蓋網絡上的多個區段(bucket)，其中，每一個區 段都分別包括一個或多個節點；確定區段組，其中，每一個區段組都分別包括選定數量的區 段；基於區段組來分發事件；並且基於事件來更新路由表。在一個方案中，提供了一種用於在包括多個節點的對等覆蓋網絡中的事件分發和 路由的裝置。該裝置包括用於確定該對等覆蓋網絡上的多個區段的模塊，其中，每一個區 段都分別包括一個或多個節點；用於確定區段組的模塊，其中，每一個區段組都分別包括選 定數量的區段；用於基於區段組來分發事件的模塊；以及用於基於事件來更新路由表的模 塊。在一個方案中，提供了一種節點，其被配置用於在包括多個節點的對等覆蓋網絡 中的事件分發和路由。該節點包括收發機和耦合到收發機的處理器。該節點被配置為確 定該對等覆蓋網絡上的多個區段，其中，每一個區段都分別包括一個或多個節點；確定區段 組，其中，每一個區段組都分別包括選定數量的區段；基於區段組來分發事件；並且基於事 件來更新路由表。在一個方案中，提供了一種電腦程式產品，用於在包括多個節點的對等覆蓋網 絡中的事件分發和路由。該電腦程式產品包括計算機可讀介質，該計算機可讀介質包含 可執行來進行以下操作的代碼確定該對等覆蓋網絡上的多個區段，其中，每一個區段都分 別包括一個或多個節點；確定區段組，其中，每一個區段組都分別包括選定數量的區段；基 於區段組來分發事件；並且基於事件來更新路由表。在閱讀了以下提出的附圖的簡要說明、說明和權利要求後，其它方面會變得明顯。


通過結合附圖參考以下的說明，本文所述的前述方案會變得顯而易見圖1顯示了示出事件分發系統的各個方案的網絡；圖2顯示了根據事件分發系統而產生的傳播樹；圖3顯示了根據事件分發系統的方案，被配置為進行兩跳(two-hop)路由的對等 覆蓋網絡；圖4顯示了對等覆蓋網絡，其示出了根據事件分發系統的方案的兩跳路由的過 程；圖5顯示了表格，其示出了根據事件分發系統的各種路由實施方式的比較；圖6顯示了在事件分發系統的方案中，在節點處使用的示例性分發處理器；圖7顯示了根據事件分發系統，用於根據事件分發系統在對等覆蓋網絡中提供事 件路由的示例性方法；圖8顯示了在事件分發系統的方案中，在節點處使用的示例性分發處理器。
具體實施例方式以下描述說明了用於在對等覆蓋網絡中的事件分發和路由的事件分發系統的多 個方案。在一個方案中，確定固定數量的「區段(bucket)」，其用於構成施加在一個節點的路由表上的「視圖(view)」。例如，將參與覆蓋網絡的節點分配給特定的區段。作為結果， 由所確定的區段構成傳播樹，且傳播樹的陣列表示具有固定的長度。系統通過提供能夠有 效地管理與等待時間、帶寬利用率和路由表大小有關的折衷的一跳、二跳和三跳路由，來管 理這些折衷。這個系統尤其適合於使用IP網絡環境的對等覆蓋網絡，但也可以用於任何類型 的網絡環境中，包括但不限於通信網絡、公用網絡、諸如虛擬專用網絡(VPN)之類的專用 網絡、區域網、廣域網、長程網(long haul network)，和/或任何其它類型的網絡環境。通過參考以下解釋，本文描述的前述方案會變得更顯而易見。覆蓋網絡覆蓋網絡是這樣的網絡，即在該網絡中對等節點彼此協同操作以提供服務並維持 網絡。覆蓋網絡可以虛擬地包括任何數量的節點。區段是多個臨近節點的分組。覆蓋網絡可以包括多達該覆蓋網絡中節點數量的總 共「N」個區段，在此情況下，每一個區段都會包括一個節點。例如，覆蓋網絡可以包括1000 個節點，將它們分組為總共N= 100個區段，其中，每一個區段都包括10個節點。然而，應 注意在每一個區段中的節點數量可以不同。兄弟節點(sibling node)一個區段中的節點被稱為兄弟「S」。區段鉬.(bucket Rroup)區段組是多個區段的分組，用以實現預期的覆蓋網絡組織和路由。「η」表示區段組 的總數。每一個區段組包括「III」個區段，從而使得區段的總數為(n*m) =N0為了易於呈 現，如相關附圖所示，每一個區段組都由具有相同陰影的區段來表示。夥伴區段(buddy bucket)指的是在同一區段組中的區段。鄰域(neiRhborhood)鄰域是多個區段的一個集合，該集合包括來自η個區段組中每一個區段組的至少 一個區段。事件當節點加入或離開覆蓋網絡時，或者當進行鄰域更新時，發生事件。多級分組在多級分組中，將區段組自身再分組到另外的組中。例如，在兩級分組中，定義ο 個組，且每一個組由η個區段組組成，以便可以根據N= (o*n*m)來確定區段的總數。還可 以有多於兩級的分組；然而，應該針對路由表大小或等待時間的增加而對分組的級進行平圖1顯示了用於示出事件分發系統的方案的網絡100。網絡100包括底層網絡 (underlying network) 102，其包括諸如網際協議網絡之類的任何類型的網絡。儘管將底層 網絡102顯示為單個實體，但底層網絡可以包括諸如WAN、LAN、無線網絡或者其他任何類型 的網絡之類的任何數量或類型的網絡。對等覆蓋網絡104包括底層網絡102的節點的子集，並利用底層網絡102的服務來進行操作，以允許這些節點進行通信。例如，在106處一般性地顯示的多個節點由通信鏈 路連接，以構成圍繞對等覆蓋網絡104的環形路由通路。通信鏈路可以是由底層網絡102 提供的安全隧道。應注意，對等覆蓋網絡104可以具有用以實現任何路由模式的任意拓撲 布局或架構，它不限於圖1所示的路由。例如，覆蓋網絡104的節點106可以具有更多的互 連，以提供除了所示的環形通路之外的其他路由通路。在該事件分發系統的操作期間，將對等覆蓋網絡拓撲布局分為在108處一般性地 顯示的N個區段。覆蓋中的每個節點都基於其在覆蓋網絡拓撲布局中的位置而被分配給一 個區段，以使得每一個區段都包括s個兄弟節點。應注意，在每一個區段中的兄弟節點的數 量可以不同。隨後，以一種或多種方式將這些區段進行分組。例如，產生η個區段組，以使 得每一組都包括選定數量m個區段。為了易於呈現，每一個區段組都通過具有相同陰影的 區段來圖形化地進行表示。產生鄰域，其包括來自每一個區段組的至少一個區段。為了有 利於多跳路由，構成多個組，其中所述組包括區段組的分組。再次參考圖1，根據事件分發系統來組織對等覆蓋網絡104，以便包括區段 (0-14)。將每一個節點106都分配給一個區段。在一個實施方式中，將在兩個區段之間的 所有節點都分配給前一個區段。例如，節點標識符的高位比特用於確定區段標識符。然而， 應注意，任何算法或分配技術都可以用於將節點分配給每一個區段。在同一個區段中的節 點彼此是兄弟。由於區段的數量是固定的，因此用區段構成的傳播樹意味著所有節點構成 傳播樹的同一視圖。例如，所有節點都知道將消息路由經過覆蓋網絡104時所通過的區段 的準確順序。在一個實施方式中，一個特定節點充當事件分發伺服器，並操作以確定區段及相 應的區段組。例如，在覆蓋網絡104中，節點110充當事件分發伺服器。節點110包括分發 處理器(DP) 112，其操作以確定區段(0-14)，並從而將節點分配給這些區段。DP 112還根據 本文所述的事件分發系統操作以確定區段組。在本文的另一節中更詳細描述了分發處理器 (DP)112的操作。還應注意，可以以其他方式執行對區段和區段組的確定。例如，可以使用 一種分發過程以使得多個節點操作以確定區段和區段組。在另一個實施方式中，在網絡配 置、初始化或註冊期間，為每一個節點提供區段信息。圖2顯示了根據事件分發系統而產生的傳播樹200。例如，該傳播樹200由圖1所 示的區段(0-14)構成，並且表示固定長度的陣列。對於事件傳播，在一個特定區段中的節 點通知其自己的區段中的兄弟和在其兩個孩子區段(child bucket)中的一個或多個節點。 例如，區段5中的節點通知在區段5中的其兄弟節點和在其兩個子區段4和6中的節點。因此，在該事件分發系統的一個實施方式中，確定固定數量的區段，並且這些區段 操作以提供在覆蓋網絡104中所有節點處的傳播樹的相同視圖，從而減輕了傳統系統中會 出現的路由表差異所造成的影響。一跳路由和分析(無兄弟)以下是對於與圖2所示的傳播樹200有關的一跳路由的分析。例如，以下傳輸是 響應於要通過對等覆蓋網絡104傳播的事件而相對於節點進行的。1. 一個節點從其父區段中的一個節點接收與該事件有關的一條消息。2.該節點向其父區段的所述節點發送一個確認。3.該節點將該消息轉發到每一個子區段中的一個或多個節點。
4.該節點從每一個子區段中的所述一個或多個節點接收一個確認。5.該節點將該消息轉發到其自己區段中的所有兄弟。6.該節點從其自己區段中的所有兄弟接收確認。此外，假定了 二叉傳播樹，其中應用以下條件。1. 一半的節點是葉子。2. 一個節點是用於一半事件的葉子。3. 一個節點必須僅轉發一半事件。在一個示例中，為了分析與傳播樹200相關的一跳路由，將假定以下信息。1.消息大小=X字節。2.報頭大小=確認大小=y字節。3.事件率=r個事件/秒。4.在每一個區段內不存在兄弟。對於下遊分析，以下傳輸發生。1.來自父親的、對於每一個事件的一條消息產生每秒r*(x+y)字節的傳輸速率。2.來自每一個孩子的、對於一半事件的確認產生每秒2*(r/2)*y字節的傳輸速率。3.對於一跳的總下遊帶寬是D1 = r*(x+2y)。對於上遊分析，以下傳輸發生。1.發送到孩子的、對於一半事件的兩條消息產生2*(r/2)*(x+y)。2.發送到父親的、對於每一個事件的一個確認產生每秒r*y字節。3.對於一跳路由的總上遊帶寬是每秒U1 = r*(x+2y)字節。因此，在覆蓋網絡包括一百萬個節點，並確定了一百萬個區段(即無兄弟)的情況 下，可以使用以下假設來執行帶寬和路由表大小的分析。1. r =每秒200個事件。2· χ = 20 字節。3. y = 30 字節。4.路由表條目是40位元組。通過將這些假設代入以上等式，獲得了以下一跳帶寬和路由表大小。1.帶寬=128kbpSo2.路由表大小=40兆字節。一跳路由和分析(有兄弟)以下是對於與傳播樹200相關的一跳路由的分析，其中，假定在每一個區段中存 在s個兄弟節點。結果，每一個節點有(s-1)個兄弟。例如，以下傳輸響應於要傳播的事件 而相對於一個節點發生。對於下遊分析，以下傳輸發生。1.來自父親的、對於每一個1/s事件的一條消息產生每秒(r/s)*(x+y)字節的傳 輸速率。2.來自兄弟的、對於(s-l)/s個事件的一條消息產生(s-1)/s*r*(x+y)。3.來自孩子的、對於一半事件的兩個確認產生每秒2*(r/2)*y字節的傳輸速率。
4.來自(s-1)個兄弟的、對於所有接收到的事件的一個確認產生(s_l)*r/ s*(x+y)ο5.對於一跳的總下遊帶寬是D1 = r*(x+2y)。對於上遊分析，以下傳輸發生。1.發送到孩子的、對於一半事件的兩條消息產生2*r/2* (x+y) = r/s (x+y)。2.發送到兄弟的、對於所有接收到的事件的(s-1)條消息產生(s-1)*r/s*(x+y)。3.發送到父親的、對於每一個事件的一個確認產生每秒r/s*y字節。4.發送到兄弟的、對於(s-1)/s個事件的一個確認產生(s-l)/s*r*y。5.對於一跳路由的總上遊帶寬是每秒U1 = r*(x+2y)字節。因此，在每一個區段都包括s個節點的情況下，可以發現帶寬需求獨立於兄弟的 數量。兄弟的數量影響上遊業務量的突發性，這可以用於節能目的。一跳路由和K-ary事件傳播樹以下是對於利用k-ary樹來代替二叉樹進行事件傳播的一跳路由的分析。在完全 k-ary樹中，節點的大約(k_l)/k是葉子。一個節點對於所有事件中的(k_l)/k部分是葉 子，並且一個節點僅需轉發消息中的Ι/k部分。對於下遊分析，以下傳輸發生。1.來自父親的一條消息產生每秒r*(x+y)字節的傳輸速率。2.來自孩子的、對於事件的Ι/k的k個確認產生每秒k*r/k*y字節的傳輸速率。3.對於一跳的總下遊帶寬是Dlk = r*(x+2y)。對於上遊分析，以下傳輸發生。1.發送到孩子的、對於事件中的Ι/k部分的k條消息產生k*r/k*(x+y) =r(x+y)。2.發送到父親的一個確認產生每秒r*y字節。3.對於一跳路由的總上遊帶寬是每秒Ulk = r*(x+2y)字節。因此，在使用k-ary傳播樹的情況下，可以發現帶寬需求獨立於樹的級。樹的級的 增加影響上遊業務量的突發性，這可以用於節能目的。兩跳路由圖3顯示了根據事件分發系統的方案，被配置為進行兩跳路由的對等覆蓋網絡 300。在覆蓋網絡300中，將N個區段分為η個組，每組m個區段。因此，可以由N = (n*m)來確定區段的總數N。例如，覆蓋網絡300示出了 N= 16個區段，將其分為η = 4個 區段組，每組包括m = 4個區段。為了簡潔，用編號和陰影來標識每一組中的區段。例如， 圖3示出了以下區段組。1.組 l_g(l，x)黑色陰影2.組 2_g(2，x)灰色陰影3.組 3_g(3，x)斑紋陰影4.組4_g(4，x)無陰影(空白的)圖3中的每一個區段都由組和各自的編號(即g(組#，區段#))來表示。還顯示 了鄰域(1-4)，其中每一個鄰域都包括來自每一組的一個區段。網絡300還包括位於區段 g(l，l)中一個節點處的DP 302。DP 302操作以根據事件分發系統來確定區段的數量、節點到區段的分配、組的數量以及每一組中區段的數量。應注意，DP 302適於用作圖1所示的 DP 112。在第一實施方式中，在同一組中的兩個連續區段之間的距離總是每一組的區段數 m。在組中的區段的順序對於所有組而言都是相同的；類似的，在鄰域中的區段的順序對於 所有鄰域而言都是相同的。應注意，圖3中所用的分組分配用於隨後所有圖示。在第二實施方式中，用映射函數來選擇在具有相同陰影的兩個連續區段之間的距 離。由於隨機化的可能性，這個方案具有預期的安全特性。在這些實施方式中，覆蓋網絡300的節點知道以下信息，1. 一個節點知道在包含其自己的區段的其鄰域中m個區段中的所有節點。鄰域 由m個區段的圓弧來表示。在第一選項中，在其自己的區段的任一側都具有其鄰域中一半 的區段。因此，這是這樣的一個由m個區段構成的鄰域，即其自己的區段在中間。在第二選 項中，鄰域由包含該節點的、任意m個區段的圓弧來表示。2. 一個節點知道在其組中所有區段中的所有節點。這些區段被稱為「夥伴」區段， 並且它們一起構成夥伴網絡。兩跳路由示例圖4顯示了對等覆蓋網絡400，其示出了根據事件分發系統的方案的兩跳路由的 過程。在以下描述中，將一跳路由定義為從第一節點到在該第一節點自己的鄰域中的m個 區段中所有其他節點的路由。將兩跳路由定義為從第一節點到在該第一節點的區段組中、 但在不同的鄰域中的第二節點的路由，隨後路由到在該第二節點的鄰域中的目標節點。例 如，參考圖4，當從鄰域3中的區段g(l，3)中的節點向鄰域1中夥伴區段g(l，l)中的節點 發送消息時，第一跳402發生，其中，鄰域1是目標節點的鄰域。當從鄰域1中的夥伴區段 g(l，l)中的這個節點向鄰域1中的區段W4，l)中的目標節點發送消息時，第二跳404發 生。以下說明了根據事件分發系統的方案，用於兩跳路由的區段配置，其中假定了以 下fe息。1. 一個一百萬個節點的網絡，其中，η = m = 1000。2.每一個節點都知道在其鄰域中的1000個節點(包括自己)。3.每一個節點都知道在其夥伴網絡中的1000個節點(包括自己)，並且其夥伴網 絡中的1000個節點中的每一個都知道1000個其他的節點(包括自己)。4.與所有夥伴區段相關的鄰域圓弧彼此不重疊，從而相互排斥。5.所有夥伴區段的鄰域圓弧覆蓋了該覆蓋網絡中的所有區段，以使得它們總體上 是無遺漏的。結果，每一個節點都可以到達1000*1000 = 1，000，000個節點。例如，一個節點可
以在一跳中到達其鄰域中的所有1000個節點。此外，一個節點可以使用其夥伴節點在兩跳 中到達所有其他的節點(即，第一跳到達目標節點的鄰域中的夥伴節點，第二跳從目標節 點的鄰域中的該夥伴節點到達該目標節點)。在兩跳路由中的事件傳播為了支持兩跳路由，一個節點知道在其自己的鄰域中所有區段中和所有其夥伴區 段中的加入/離開。將兩個二叉樹用於事件傳播。一個樹包括在節點自己的鄰域中的所有區段，其被稱為本地樹。另一個樹包括所有夥伴區段，其被稱為夥伴樹。在完美的離開過程 中，節點在離開之前通知所有其他的節點。對於節點失敗(即不完美的離開)，監視節點檢 測到節點失敗，並向在該失敗節點的夥伴區段中的節點傳播事件。應注意，監視節點的夥伴區段可以具有與失敗節點的區段不同的陰影(即，失敗 節點在與監視節點不同的組中)。在此情況下，監視節點的夥伴區段中的節點通知失敗節點 的夥伴區段中的節點，這可以利用一個附加跳來進行。例如，在黑色區段中的節點失敗，且 在該區段中沒有其他節點存在。會假定在灰色區段中的節點檢測到這個失敗，並向該組中 的所有灰色區段傳播與這個失敗事件有關的信息。在灰色區段中的節點隨後通知相鄰的黑 色區段。兩跳路由分析以下是對於根據事件分發系統的方案的兩跳路由的分析。假定了以下參數。1.區段的總數=N，定義η個組，每個組有m個區段，以使得n*m = N2.消息大小=χ3.報頭大小=y4.系統事件率=r個事件/秒5.每一個鄰域中的事件率=r*(m/N) = r/n6.夥伴網絡中的事件率=r*(η/Ν) = r/m7.假定區段中沒有兄弟，並完美地加入和離開。對於下遊分析，以下傳輸發生。1.來自本地樹中父親的一條消息產生(r/n)*(x+y)。2.來自夥伴樹中父親的一條消息產生(r/m)*(x+y)。3.來自本地樹中孩子的、對於一半本地事件的兩個確認產生2*(r/2n)*y。4.來自夥伴樹中孩子的、對於一半夥伴事件的兩個確認產生2*(r/2m)*y。5.對於兩跳路由的總下遊帶寬是 D2 = r* (x+2y) * ((m+n) /mn = D1* (m+n) /mn。對於上遊分析，以下傳輸發生。1.發送到本地樹中孩子的、對於一半本地事件的兩條消息產生2*(r/2n)*(x+y)。2.發送到夥伴樹中孩子的、對於一半本地事件的兩條消息產生2* (r/2m) * (x+y)。3.發送到本地樹中父親的一個確認產生(r/n)*y。4.發送到夥伴樹中父親的一個確認產生(r/m)*y。5.對於兩跳路由的總上遊帶寬是 U2 = r*(x+2y)*((m+n)/mn) = UjOn+rO/mn。可由以上等式發現，在兩跳路由中，當使(m+n)/mn最小時，帶寬最小。然而，m*n是 固定的(S卩，m*n等於區段的總數N)。因此，對於固定的m*n，當m = η = sqrt(m*n)時，量 值(m+n) /mn最小。作為示例，假定以下參數。1.網絡包括IO6個節點2. χ = 20 字節3. y = 30 字節4. m = η = sqrt(106) = IO35.路由表條目大小=40位元組
將以上參數帶入兩跳路由的等式，產生以下結果。1.帶寬=256bps2.路由表大小=(m+n)*40 = 2000 條目 *40 = 80kB。為具有IO8個節點的網絡重複以上操作，且r等於2000個事件/秒，產生以下結^ οLm = η =IO42.帶寬=2. 56kbps3.路由表大小=20000 條目 *40 = 800kB。因此，可以發現，與一跳路由相比，兩跳路由提供了減小的帶寬和較小的路由表。三跳路由在事件分發系統的另一個實施方式中，提供了三跳路由。在三跳路由中，將兩級分 組的所有區段N分為ο個組，每個組包含η個區段組，每個區段組包含m個區段。例如，在 IO6個節點網絡中，其中ο = η = m = 100，每一個節點都知道以下內容。1.在其鄰域中的100個節點(到100個節點的一跳路由)2. 100個其他節點，其每一個在最多一跳中都可以到達100個更多的節點(提供了 到1000個節點的兩跳路由)。3. 100個更多的節點，其每一個在最多兩跳中都可以到達10000個節點(提供了到 IO6個節點的三跳路由)。三跳路由分析以下是對於根據事件分發系統的方案的三跳路由的分析。假定了以下參數。1.區段的總數=N，其中，m*n*o = N2.對於固定的 m*n*o ,當 m = η = ο = cuberoot (m*n*o)(立方根((m*n*o)))時， 量值(m+n+o) /mno最小3.消息大小=χ給定以上參數，可以使用與以上提供的分析類似的分析來確定以下下遊和上遊帶
覓ο1.下遊帶寬D3 = r氺(x+2y)氺(m+n+o) /mno = D1* (m+n+o) /mno2.上遊帶寬U3 = r氺(x+2y)氺(m+n+o) /mno = U1* (m+n+o) /mno為了說明三跳路由，假定以下參數。1.網絡包括IO6個節點2. χ = 20 字節3. y = 30 字節4. m = η = ο = 1005.路由表條目大小=40位元組將以上參數帶入三跳路由的等式中，產生以下結果。1.帶寬=38. 4bps2.路由表大小=(m+n+o) *40 = 300 條目 *40 = 12kB
為具有IO9個節點的網絡重複以上操作且r等於200，000個事件/秒，產生以下結果。1. m = η = ο = 10002.帶寬=384bps3.路由表大小=3000 條目 *40 = 120kB多種路由實施方式的比較圖5顯示了表500，其示出了根據事件分發系統的各種路由實施方式的比較。通 常，對於η跳路由實施方式，可以由以下來確定帶寬和路由表大小。1.帶寬 Dn_K*r*(x+2y)其中，K = (m1+m2+m3+. . . +mn) / 0 *! *! *. . . *mn)2.路由表大小是0* (N的η次方根)其中，N是節點/區段的總數量。如圖5所示，顯示了路由類型502、節點數量504、帶寬506和路由表大小508。因 此，表500可以用於管理在等待時間與帶寬或路由表大小之間的折衷。例如，在具有IO6個 節點的覆蓋網絡中，提供三跳路由的分組配置產生了圖5所示的最小的路由表大小。圖6顯示了用於事件分發系統的方案的示例性分發處理器600。例如，DP 600適 於在對等覆蓋網絡中的節點處使用，例如，如同圖3所示的DP 302 —樣。DP 600包括處理 器602、區段配置邏輯604、存儲器606和收發機608，其全部都耦合到數據總線610。應注 意，DP 600僅僅是一個實施方式，在所述方案的範圍內其它實施方式也是可行的。收發機608包括硬體和/或硬體執行的軟體，其操作以允許DP 600與對等覆蓋網 絡上的多個節點進行數據、事件或其它信息的傳遞。在一個方案中，收發機608用於與對等 覆蓋網絡的節點建立一條或多條通信鏈路612。例如，利用底層IP網絡的服務來構成通信 鏈路612。存儲器606包括用於存儲路由表614的任何適合的存儲設備，路由表614描述了 使用所確定的區段在對等覆蓋網絡上進行的消息路由。例如，路由表614提供路由信息，以 允許根據如本文所述的事件分發系統的一跳、兩跳或三跳路由。存儲器606還用於存儲分 發模塊614，其包括一個或多個包含指令或代碼的模塊，所述指令或代碼可由處理器602執 行以提供本文所述的功能。處理器602包括CPU、處理器、門陣列、硬體邏輯電路、存儲單元和/或硬體執行的 軟體中的至少一個。在一個方案中，處理器模塊602執行分發模塊616的指令或代碼，以控 制DP 600模塊來執行本文所述的功能。在一個實施方式中，處理器602接收覆蓋網絡配置參數，其包括節點標識符、區段 標識符和區段組標識符。在網絡配置、初始化或註冊過程中，可以從覆蓋網絡中的一個或多 個節點接收覆蓋網絡配置參數，或者從中央伺服器接收覆蓋網絡配置參數。還可以從用戶 輸入接收覆蓋網絡配置參數。覆蓋網絡配置參數存儲在存儲器606中，處理器602使用這 些配置參數來初始地產生路由表，該路由表作為路由表614存儲在存儲器606中。路由表 614可以被配置為提供一跳、兩跳或三跳路由。在另一個實施方式中，區段配置邏輯604操作以產生覆蓋網絡配置參數。區段配 置邏輯604包括CPU、處理器、門陣列、硬體邏輯電路、存儲單元和/或硬體執行軟體中的至少一個。區段配置邏輯604操作以確定固定數量的區段以及分配給這些區段的節點。區段 配置邏輯電路604還操作以執行區段分組，以便實現如本文所述的一級或多級分組。由區 段配置邏輯604產生的覆蓋網絡配置參數隨後存儲在存儲器606中，並使用收發機608分 發到覆蓋網絡中的其他節點。處理器602隨後可以獲得這些配置參數，以初始地產生路由 表614。在覆蓋網絡中的其他節點執行相同的功能以初始地產生其自己的路由表。在操作期間，收發機608操作以接收一個或多個事件，並將這些事件傳送到處理 器602。處理器602操作以基於路由表614中的區段組來分發事件。處理器602還操作以 基於接收到的事件來更新路由表614。例如，當節點加入、離開或發生對鄰域的更新時，處理 器602接收與這些事件有關的消息。處理器602使用路由表614來將這些事件在覆蓋網絡 上進行路由。處理器602還操作以更新路由表614，以便反映這些變化。在覆蓋網絡中的其 他節點處重複這個操作，以使得每一個節點都更新其自己的路由表。因此，系統為在對等覆 蓋網絡中的事件分發和路由提供了有效的機制。在一個方案中，事件分發系統包括電腦程式產品，其具有由存儲或包含在機器 可讀介質上的一條或多條程序指令「指令」或「代碼」構成的電腦程式。當由至少一個處 理器(例如處理器60 執行所述代碼時，所述代碼的執行使得DP 600提供本文所述的事 件分發系統的各個功能。例如，機器可讀介質包括軟盤、CDR0M、光碟、存儲卡、快閃記憶體設備、 RAM、ROM，或者可以與DP 600交互的任何其他類型的存儲設備或機器可讀介質。在另一個 方案中，可以從外部設備或通信網絡資源將代碼下載到DP 600中，並存儲在機器可讀介質 中，用於稍後執行。代碼集當被執行時，操作以提供本文所述的事件分發系統的各個方案。圖7顯示了根據事件方法系統的示例性方法700，用於在對等覆蓋網絡中提供事 件路由。例如，可以在一個節點處由圖6所示的DP 600來執行方法700。為了清楚起見，以下將方法700描述為由圖6所示的DP 600來執行。在一個方案 中，處理器602執行存儲在存儲器606中的分發模塊616的一個或多個代碼，以控制DP 600 執行以下所述的功能。在塊702，確定包括對等覆蓋網絡中一個或多個節點的固定數量的區段。例如，處 理器602操作以確定這些區段。在一個方案中，處理器602基於存儲在存儲器606中的配 置信息來確定這些區段。例如，基於區段在覆蓋網絡上的位置，將在覆蓋網絡上的節點分配 給每一個區段。例如，節點標識符的高位比特用於確定區段標識符。在一個實施方式中，將 在兩個區段之間的所有節點都分配給與較小標識符相關聯的區段。然而，應注意，任何算法 或分配技術都可以用於將節點分配給每一個區段。在塊704，確定包括一個或多個區段的固定數量的區段組。例如，處理器602操作 以確定區段組。在一個方案中，處理器602基於存儲在存儲器606中的配置信息來確定區 段組。在塊706，基於區段組來初始地產生路由表，以便提供一跳、兩跳或三跳路由。在一 個方案中，處理器602操作以基於區段組操作來產生路由表。在塊708，基於路由表的區段組，來分發接收到的事件。在一個實施方式中，這些事 件包括加入、離開或鄰域更新。例如，處理器602操作以基於路由表614的區段組來分發事 件。用收發機608在覆蓋網絡上分發事件。在塊710，基於事件來更新路由表。例如，處理器602基於接收到的加入、離開或鄰域更新來更新路由表614。因此，可以執行方法700以根據事件分發系統在對等覆蓋網絡中提供事件分發和 路由表更新。應注意，方法700僅是一個實施方式，在多個方案的範圍內可以重新排列或者 修改方法700的各個操作。因此，在本文所述的多個方案的範圍內，其他實施方式也是可行 的。圖8顯示了在事件分發系統的多個方案中，在節點處使用的示例性分發處理器 800。例如，分發處理器800可以實現為圖6中所示的分發處理器600。在一個方案中，分發 處理器800由包括一個或多個模塊的至少一個集成電路來實現，所述模塊被配置為提供本 文所述的事件分發系統的多個方案。例如，在一個方案中，每一個模塊都包括硬體和/或硬 件執行軟體。分發處理器800包括第一模塊，其包括用於確定覆蓋網絡上的多個區段的模塊 (802)，其中，每一個區段都分別包括一個或多個節點，在一個方案中，第一模塊包括處理器 602。分發處理器800還包括第二模塊，其包括用於確定區段組的模塊(804)，其中，每一個 區段組都分別包括選定數量的區段，在一個方案中，第二模塊包括處理器602。分發處理器 800還包括第三模塊，其包括用於基於區段組來分發事件的模塊(806)，在一個方案中，第 三模塊包括收發機608。分發處理器800還包括第四模塊，其包括用於基於事件來更新路由 表的模塊(808)，在一個方案中，第四模塊包括處理器602。可以採用通用處理器、數位訊號處理器(DSP)、專用集成電路(ASIC)、現場可編程 門陣列(FPGA)或其他可編程邏輯器件、分立門或電晶體邏輯電路、分立硬體組件，或者被 設計為執行本文所述功能的其任意組合，來實現或執行結合本文所公開的各個方案所述的 各種示例性邏輯、邏輯塊、模塊和電路。通用處理器可以是微處理器，但可替換地，該處理器 可以是任何常規處理器、控制器、微控制器，或狀態機。處理器還可以實現為計算設備的組 合，例如DSP與微處理器的組合、多個微處理器的組合、結合了 DSP內核的一個或多個微處 理器的組合，或者任何其他這種結構。結合本文所公開的各個方案所述的方法或算法的步驟可以直接包含在硬體中、由 處理器執行的軟體模塊中，或者二者的組合中。軟體模塊可以位於RAM存儲器、快閃記憶體存儲 器、ROM存儲器、EPROM存儲器、EEPROM存儲器、寄存器、硬碟、可移動盤、CD-ROM，或者本領域 已知的任何其他形式的存儲介質中。示例性存儲介質耦合到處理器，以使得處理器能夠從 存儲介質讀取信息，並向其寫入信息。可替換地，存儲介質可以集成到處理器中。處理器和 存儲介質可以位於ASIC中。ASIC可以位於無線通信設備中。可替換地，處理器和存儲介 質可以作為分立組件位於無線通信設備中。提供了所公開的各個方案的描述以允許本領域普通技術人員能夠實現或使用本 發明。在不背離本發明的精神或範圍的情況下，對這些方案的各種修改對於本領域技術人 員而言都是顯而易見的，並且本文定義的普遍性原理可以適用於其他方案，例如用於即時 消息發送服務或任何常用無線數據通信應用中。因此，本發明不是旨在限於本文所示的這 些方案，而是與符合本文所公開的原理和創新性特點的最廣泛的範圍相一致。本文專有地 使用了詞語「示例性」，意思是「用作示例、實例或說明」。本文描述為「示例性」的任何方案 都不必解釋為優選的，或者比其他方案更有優勢。因此，儘管本文示出並描述了事件分發系統的多個方案，但會意識到，在不背離其精神或基本特性的情況下，可以對這些方案做出各種變化。因此，本文的公開文本和描述對 於以下權利要求中闡明的本發明範圍旨在是示例性的，而不是限制性的。
權利要求
1.一種用於在包括多個節點的對等覆蓋網絡中的事件分發和路由的方法，所述方法包括確定所述對等覆蓋網絡上的多個區段，其中，每一個區段都分別包括一個或多個節點。確定區段組，其中，每一個區段組都分別包括選定數量的區段； 基於所述區段組分發事件；並且 基於所述事件更新路由表。
2.如權利要求1所述的方法，其中，所述事件包括加入、離開和鄰域更新中的至少一個。
3.如權利要求1所述的方法，其中，所述更新包括更新所述路由表，以便構成具有固 定陣列長度的傳播樹。
4.如權利要求1所述的方法，其中，所述確定多個區段包括確定所述多個區段，以使 得有總共N個區段。
5.如權利要求4所述的方法，其中，所述確定區段組包括確定所述區段組，以便構成 總共η個區段組，每一個區段組包括m個區段，其中，N = n*m。
6.如權利要求1所述的方法，其中，所述更新路由表包括基於所述事件來更新所述路 由表，以便進行兩跳路由。
7.如權利要求4所述的方法，其中，所述確定區段組包括確定所述區段組，以便構成 總共ο個組，每一個組包括η個區段組，每一個區段組包括m個區段，其中，N = n*m*o。
8.如權利要求7所述的方法，其中，所述更新路由表包括基於所述事件來更新所述路 由表，以便進行三跳路由。
9.如權利要求1所述的方法，還包括基於所述區段組來初始地產生所述路由表。
10.一種用於在包括多個節點的對等覆蓋網絡中的事件分發和路由的裝置，所述裝置 包括用於確定所述對等覆蓋網絡上的多個區段的模塊，其中，每一個區段都分別包括一個 或多個節點；用於確定區段組的模塊，其中，每一個區段組都分別包括選定數量的區段； 用於基於所述區段組來分發事件的模塊；以及 用於基於所述事件來更新路由表的模塊。
11.如權利要求10所述的裝置，其中，所述事件包括加入、離開和鄰域更新中的至少一個。
12.如權利要求10所述的裝置，其中，所述用於更新的模塊包括用於更新所述路由表 以便構成具有固定陣列長度的傳播樹的模塊。
13.如權利要求10所述的裝置，其中，所述用於確定多個區段的模塊包括用於確定所 述多個區段以使得有總共N個區段的模塊。
14.如權利要求13所述的裝置，其中，所述用於確定區段組的模塊包括用於確定所述 區段組以便構成總共η個區段組且每一個區段組包括m個區段的模塊，其中，N = n*m。
15.如權利要求10所述的裝置，其中，所述用於更新路由表的模塊包括用於基於所述 事件來更新所述路由表以便進行兩跳路由的模塊。
16.如權利要求13所述的裝置，其中，所述用於確定區段組的模塊包括用於確定所述 區段組以便構成總共ο個組且每一個組包括η個區段組，每一個區段組包括m個區段的模 雙，胃巾，N = rpKm氺ο。
17.如權利要求16所述的裝置，其中，所述用於更新路由表的模塊包括用於基於所述 事件來更新所述路由表以便進行三跳路由的模塊。
18.如權利要求10所述的裝置，還包括用於基於所述區段組來初始地產生所述路由 表的模塊。
19.一種被配置用於在包括多個節點的對等覆蓋網絡中的事件分發和路由的節點，所 述節點包括收發機；以及耦合到所述收發機的處理器，所述處理器被配置為確定所述對等覆蓋網絡上的多個區段，其中，每一個區段都分別包括一個或多個節佔.^ w\ 確定區段組，其中，每一個區段組都分別包括選定數量的區段； 基於所述區段組來分發事件；並且 基於所述事件來更新路由表。
20.如權利要求19所述的裝置，其中，所述事件包括加入、離開和鄰域更新中的至少一個。
21.如權利要求19所述的裝置，其中，所述處理器被配置為更新所述路由表，以便構 成具有固定陣列長度的傳播樹。
22.如權利要求19所述的裝置，其中，所述處理器被配置為確定所述多個區段，以使 得有總共N個區段。
23.如權利要求22所述的裝置，其中，所述處理器被配置為確定所述區段組，以便構 成總共η個區段組，每一個區段組包括m個區段，其中，N = n*m。
24.如權利要求19所述的裝置，其中，所述處理器被配置為基於所述事件來更新所述 路由表，以便進行兩跳路由。
25.如權利要求22所述的裝置，其中，所述處理器被配置為確定所述區段組，以便構 成總共ο個組，每一個組包括η個區段組，每一個區段組包括m個區段，其中，N = n*m*o。
26.如權利要求25所述的裝置，其中，所述處理器被配置為基於所述事件來更新所述 路由表，以便進行三跳路由。
27.如權利要求19所述的裝置，其中，所述處理器被配置為基於所述區段組來初始地 產生所述路由表。
28.一種電腦程式產品，用於在包括多個節點的對等覆蓋網絡中的事件分發和路由， 所述電腦程式產品包括計算機可讀介質，包含可執行來進行以下操作的代碼確定所述對等覆蓋網絡上的多個區段，其中，每一個區段都分別包括一個或多個節佔.^ w\ 確定區段組，其中，每一個區段組都分別包括選定數量的區段； 基於所述區段組來分發事件；並且基於所述事件來更新路由表。
29.如權利要求觀所述的計算機可讀介質，其中，所述事件包括加入、離開和鄰域更新 中的至少一個。
30.如權利要求觀所述的計算機可讀介質，其中，所述代碼被配置為更新所述路由 表，以便構成具有固定陣列長度的傳播樹。
31.如權利要求觀所述的計算機可讀介質，其中，所述代碼被配置為確定所述多個區 段，以使得有總共N個區段。
32.如權利要求31所述的計算機可讀介質，其中，所述代碼被配置為確定所述區段 組，以便構成總共η個區段組，每一個組包括m個區段，其中，N = n*m。
33.如權利要求觀所述的計算機可讀介質，其中，所述代碼被配置為基於所述事件來 更新所述路由表，以便進行兩跳路由。
34.如權利要求33所述的計算機可讀介質，其中，所述代碼被配置為確定所述區段 組，以便構成總共ο個組，每一個組包括η個區段組，每一個區段組包括m個區段，其中，N =η氺m氺ο。
35.如權利要求34所述的計算機可讀介質，其中，所述代碼被配置為基於所述事件來 更新所述路由表，以便進行三跳路由。
36.如權利要求33所述的計算機可讀介質，其中，所述代碼被配置為基於所述區段組 來初始地產生所述路由表。
全文摘要
用於在對等覆蓋網絡中的事件分發和路由的方法和裝置。提供了一種用於在包括多個節點的對等覆蓋網絡中的事件分發和路由的方法。該方法包括確定所述對等覆蓋網絡上的多個區段，其中，每一個區段都分別包括一個或多個節點；確定區段組，其中，每一個區段組都分別包括選定數量的區段；基於所述區段組來分發事件；並且基於所述事件來更新路由表。節點包括收發機和耦合到收發機的處理器，所述處理器被配置為確定所述覆蓋網絡上的多個區段，其中，每一個區段都分別包括一個或多個節點；確定區段組，其中，每一個區段組都分別包括選定數量的區段；基於所述區段組來分發事件；並且基於所述事件來更新路由表。
文檔編號H04L29/08GK102067564SQ200980122817
公開日2011年5月18日 申請日期2009年6月19日 優先權日2008年6月19日
發明者E·T·L·哈迪, L·R·東代蒂, R·S·賈亞拉姆, V·納拉亞南 申請人:高通股份有限公司