組播分發系統和組播分發方法

2023-07-15 20:09:16

專利名稱：組播分發系統和組播分發方法
技術領域：
本發明涉及用於在網狀虛擬網絡中分發數據包的組播分發系統 及其方法。
背景技術：
目前，為分發組播數據包，已使用諸如PIM-SM (稀疏模式獨立 組播協議)、PIM-DM (密集模式獨立組播協議)或DVMRP (距離矢 量組播路由選擇協議)的組播路由協議來構建組播樹，用以構建具有 最小跳轉數的路徑以減少通信延遲，並且利用由此產生的組播樹進行 數據包分發(參見公開號為2004-531143的日本本國專利)。
公開號為2004-531143的日本本國專利披露了虛擬組播網絡方 法和系統，其中，通過使用並不支持組播分發的網絡中的虛擬組播路 由器，基於諸如PIM-SM、 PIM-DM或DVMRP的組播路由協議來進 行數據包分發。
然而，如果在網狀虛擬網絡中使用諸如PIM-SM、 PIM-DM或 DVMRP的組播路由協議，則數據包會從分發源路由器發送到所有路 由器，並且因此會將大負荷施加到分發源路由器。而且，所要求的帶 寬、延遲量等在組播群(數據包分發目的地)間有所不同，這根據應 用軟體(下文稱為應用)來構建。

發明內容
本發明提供了一種組播分發系統和組播分發方法，其創建用以 確定分發路徑的組播樹，以便滿足根據應用軟體而構建的組播群的特 性，並基於由此產生的組播樹而進行數據分發。
本發明提供了一種組播分發系統。在該系統中，從分發源路由 器向構成在網狀虛擬網絡上所形成的組播網絡的多個分發目的地路由器進行組播分發，其中，分發源路由器包括第一監視裝置，其被 配置成用以監視和檢測分發源路由器的CPU負荷率、在組播網絡上 所構建的組播群的通信特性以及網狀虛擬網絡的路徑特性；存儲裝 置，其被配置成用以存儲CPU負荷率的閾值和組播群的通信特性的 閾值；以及第一控制裝置，其被配置為基於由所述第一監視裝置檢 測到的網狀虛擬網絡的路徑特性以及至少是下述兩個比較結果其中 之一，開始重構建定義了從分發源路由器開始的數據包分發路徑的組 播樹，並且基於組播樹開始重創建確定了組播分發路徑的路由表，其 中所述兩個比較結果為由所述第一監視裝置檢測到的CPU負荷率 和存儲在所述存儲裝置中的CPU負荷率的閾值之間的比較結果以及 由所述第一監視裝置檢測到的組播群的通信特性和存儲在所述存儲 裝置中的組播群的通信特性的閾值之間的比較結果。藉助於這樣的構造，分發源路由器向組播網絡上所構建的組播 群的分發目的地路由器進行組播分發。在網狀虛擬網絡上形成組播網絡。分發源路由器監視分發源路由器中的CPU負荷率、組播群的通信特性以及網狀虛擬網絡的路徑特性。組播群的通信特性至少包括其 帶寬和通信延遲其中之一，並且通過監視組播群的數據包而計算得 到。網狀虛擬網絡的路徑特性至少包括其帶寬和其通信特性其中之 一，並且通過監視網狀虛擬網絡上流過的數據包計算得到。而且，分發源路由器存儲CPU負荷率和組播群的通信特性。另外，基於網狀 虛擬網絡的路徑特性以及至少是CPU負荷率同其閾值之間的比較結 果和組播群的通信特性同其閾值之間的比較結果其中之一，分發源路 由器開始重構建組播樹。分發源路由器基於重構建的組播樹而重創建 路由表。結果，可以根據分發源路由器的負荷狀態、組播群的通信特 性以及網狀虛擬網絡的路徑特性來選擇組播分發路徑。因此，可以通 過選擇滿足組播群所要求的通信特性的通信路徑來執行組播分發。即 使由於諸如數據包分發數量增大等原因而致使大負荷施加到分發源 路由器，分發源路由器的CPU負荷率也可以維持在或者低於某一值 (閾值)。而且，即使由於諸如流過網狀虛擬網絡的數據包數量增大 等原因而致使在網狀虛擬網絡的部分虛擬路徑中引發通信延遲之類6的問題，也通過選擇具有路徑特性餘裕的路徑來進行組播分發，由此 可進行組播分發而不會引起通信延時之類的問題。以這樣的方式，由 於可減小分發源路由器的負荷和構成網狀虛擬網絡的實際路徑的帶 寬負荷，所以能夠確保組播分發的可量測性而不要求分發源路由器和 實際網絡的硬體設備投入。
在本發明的組播分發系統中，分發源路由器的所述第一控制裝 置可被這樣配置即，在至少是由所述第一監視裝置監視到的CPU 負荷率的值以及由所述第一監視裝置監視到的組播群的通信特性的 值其中之一超過其閾值的情況下，改變組播樹的分支數量和深度，並 基於改變後的組播樹的分支數量和深度以及所述網狀虛擬網絡的路 徑特性而開始重構建組播樹。
藉助於這樣的構造，在至少是CPU負荷率和組播群的通信特性 其中之一超過其閾值的情況下，分發源路由器改變組播樹的分支數量 和深度。基於改變後的組播樹的分支數量和深度以及網狀虛擬網絡的 路徑特性，分發源路由器開始重構建組播樹。藉助於重構建的組播樹， 組播數據包可經由分發目的地路由器而分發，而無需從分發源路由器 向所有分發目的地路由器直接分發組播數據包，由此可確實地分散分 發源路由器的負荷。
而且，在本發明的組播分發系統中，每個分發目的地路由器可 包括第二監視裝置，其被配置成用以監視所述網狀虛擬網絡的路徑 特性；通信裝置，其被配置成分發和接收用於指示數據包分發的分發 信息；第二控制裝置，其被配置為基於包含在所述分發信息中的組 播樹分支數量和深度以及由所述第二監視裝置所獲取的所述網狀虛 擬網絡的路徑特性，而對定義了從分發源路由器開始的數據包分發路 徑的組播樹實施重構建，並且基於組播樹來對確定了組播分發路徑的 路由表實施重創建；以及其中，當所有分發目的地路由器的路由表的 重創建完成時，分發源路由器的所述第一控制裝置完成組播樹。
藉助於這樣的構造，基於組播樹的分支數量和深度以及網狀虛 擬網絡的路徑特性，每個分發目的地路由器對指定了從分發源路由器 開始的數據包分發路徑的組播樹實施重構建。分發目的地路由器監視網狀虛擬網絡的路徑特性並基於網狀虛擬網絡的路徑特性而確定數 據包分發路徑。分發目的地路由器基於重構建的組播樹而實施路由表 的重創建。當所有分發目的地路由器的路由表的重創建完成時，組播 樹完成。這樣，可確定從分發目的地路由器開始的數據包分發路徑， 以便考慮到分發目的地路由器的網狀虛擬網絡的路徑特性而選擇具 有餘裕的通信路徑。結果，分發目的地路由器能夠減小實際網絡的帶 寬負荷，該實際網絡分發來自分發目的地路由器的組播數據包並構成 網狀虛擬網絡，因此，確保組播分發的可量測性而無需實際網絡的硬 件設備投入成為可能。而且，在本發明的組播分發系統中，分發源路由器的所述存儲 裝置可將分發源路由器的所述第一監視裝置最初所檢測到的組播群 的通信特性作為組播群的通信特性的閾值而存儲。藉助於這樣的構造，最初檢測到的組播群的通信特性用作組播 群的通信特性的閾值。結果，在組播分發時，對於組播群而言，可自 動地設置組播群的通信特性的閾值，由此可根據組播群所要求的通信 特性而自動地創建路由表。在本發明的組播分發系統中，在組播分發時，分發源路由器的 所述第一控制裝置可在預定定時判斷是否應該重構建組播樹。藉助於這樣的構造，在根據例如時間或發送的數據包數量而設 置的預定定時，判斷是否應該重構建組播樹，由此，可根據路由器負 荷狀態以及形成組播群的組播網絡的帶寬和通信延遲的改變，而在組 播分發時動態地重構建組播樹。例如，可響應於組播分發期間路由器 負荷的增加或組播群虛擬路徑上數據包數量的增加，而動態地重構建 組播樹。結果，可在選擇滿足組播群所要求的通信特性的路徑的任何 情況下進行組播分發。本發明提供了一種組播分發方法，在該方法中，從分發源路由 器向構成在網狀虛擬網絡上形成的組播網絡的多個分發目的地路由 器進行組播分發，該方法包括下述步驟由分發源路由器監視和檢測 分發源路由器的CPU負荷率、在組播網絡上所構建的組播群的通信 特性以及網狀虛擬網絡的路徑特性；由分發源路由器讀取已存儲在存儲裝置中的CPU負荷率的閾值和組播群的通信特性的閾值；以及在 至少是CPU負荷率的值以及組播群的通信特性的值其中之一超過 CPU負荷率的閾值或者組播群的通信特性的閾值的情況下，由分發 源路由器改變組播樹的分支數量和深度，基於組播樹的分支數量和深 度以及所述網狀虛擬網絡的路徑特性，開始重構建組播樹以從分發源 路由器分發數據包，並且基於組播樹而開始重創建確定了組播分發路 徑的路由表。
根據本發明，根據分發源路由器的負荷狀態和組播群的通信特 性來重構建組播樹，因此，可通過選擇滿足組播群所要求的通信特性 的通信路徑來執行組播分發。


圖1是用於說明在連接到網狀虛擬網絡的路由器間進行組播分 發的圖2是示出圖1所示各路由器的結構的框圖3是用於說明圖1所示分發源路由器的檢索用資料庫的圖4圖示出通過分發源路由器執行路由表創建過程所創建的分
發源路由器的目的地列表，同時圖示出網狀虛擬網絡。
圖5圖示出通過分發源路由器執行路由表創建過程所創建的分 發源路由器的目的地列表和下一個目的地列表，同時圖示出網狀虛擬 網絡。
圖6圖示出通過分發源路由器執行路由表創建過程所創建的分 發源路由器的路由表以及從分發源路由器向兩個分發目的地路由器 發送的目的地列表和下一個目的地列表，同時圖示出網狀虛擬網絡。
圖7圖示出通過兩個分發源路由器執行路由表創建過程所創建 的這兩個分發目的地路由器的路由表、目的地列表和下一個目的地列 表，同時圖示出網狀虛擬網絡；
圖8圖示出在兩個路由器執行路由表創建過程中從兩個分發目 的地路由器向三個子路由器發送的目的地列表和下一個目的地列表， 同時圖示出分發源路由器的路由表和兩個分發目的地路由器以及網
9狀虛擬網絡；圖9圖示出通過三個子路由器執行路由表創建過程所創建的從 子路由器向兩個父路由器所發送的子路由器的路由表和下一個目的 地列表，同時圖示出分發源路由器和父路由器的路由表以及網狀虛擬 網絡；圖IO圖示出通過兩個父路由器執行路由表創建過程所創建的從 父路由器向分發源路由器所發送的父路由器的路由表和下一個目的 地列表，同時圖示出分發源路由器和子路由器的路由表以及網狀虛擬 網絡；圖11圖示出通過分發源路由器執行路由表創建過程所創建的分 發源路由器的路由表，同時圖示出父路由器和子路由器的路由表以及 網狀虛擬網絡；圖12是示出了分發源路由器執行路由表創建過程的流程圖；以及圖13是示出了分發目的地路由器和分發源路由器執行路由表創 建過程的流程圖。
具體實施方式
圖1圖示說明了在連接到網狀虛擬網絡上的多個路由器間所進 行的組播分發。如圖1所示，路由器R (Rs及Rl至R5)連接到網 狀虛擬網絡，並且連接分別由諸如個人計算機或蜂窩電話等所實現的 通信設備PC (PCs及PCl至PC5)中的相應設備。在該圖示說明的 實例中，路由器Rs是分發源路由器，其向其他路由器進行組播分發。 具體地，路由器Rs從在通信設備PC上運行的有關組播分發的應用 接收組播數據包，並向與該應用有關的諸如路由器Rl至R5的分發 目的地路由器進行組播分發。為此，在網狀虛擬網絡中，分發源路由 器Rs創建構成了從路由器Rs到分發目的地路由器的組播數據包通 信路徑的組播網絡，並且根據該應用而在該組播網絡中創建組播群。 組播群由組播數據包分發目的地地址(路由器R1至R5的地址)表 示。在進行從路由器Rs的組播分發時，在預定定時，路由器Rs將 路由器Rs中的CPU負荷率同其閾值進行比較，以及將組播群的通信 特性同其閾值進行比較。路由器Rs中的CPU負荷率表示路由器Rs 的CPU的負荷率。CPU負荷率的閾值為用戶事先設定的其閾值。組 播群的通信特性是定期測量的，並至少包括組播群的帶寬和通信延遲 其中之一。組播群通信特性的閾值包括至少是組播群的帶寬和通信延 遲其中之一的閾值。在本實施方式中，組播群通信特性的閾值是最初 測定的通信特性的值。在組播群通信特性僅包括帶寬或通信延遲的情況下，帶寬或通 信延遲的閾值用作組播群通信特性的閾值。在組播群通信特性既包括 帶寬又包括通信延遲的情況下，帶寬和通信延遲的閾值用作組播群通 信特性的閾值。在CPU負荷率等於或小於其閾值並且組播群通信特性等於或小 於其閾值的情況下，分發源路由器Rs通過參照已有的路由表來分發 組播數據包。在CPU負荷率超過其閾值或者組播群通信特性超過其 閾值的情況下，路由器Rs改變組播樹的分支數量和深度。而後，基 於改變後的分支數量和深度以及網狀虛擬網絡的路徑特性，路由器 Rs開始重構建組播樹以及開始重創建路由表。在開始重構建組播樹時，分發源路由器Rs創建從路由器Rs到 分發目的地路由器R (例如，路由器R1和R5)的樹，數據包從路由 器Rs直接分發至該分發目的地路由器R。而後，對於各分發目的地 路由器R也順次執行樹的重構建。當所有分發目的地路由器R的樹 的重構建完成時，組播樹即完成。在開始重創建路由表時，分發源路 由器Rs基於從路由器Rs到分發目的地路由器R的樹而登記分發目 的地路由器R的地址。對於各分發目的地路由器R也順次執行路由 表的重創建。當所有分發目的地路由器R的路由表的重創建完成時， 組播樹即完成。而後，組播樹的內容被反映到路由器Rs的路由表上， 由此，路由器Rs、 R的路由表即完成。從組播群的通信特性獨立測量為完成組播樹和路由表所需的網 狀虛擬網絡的路徑特性。路徑特性至少包括網狀虛擬網絡的帶寬和通信延遲其中之一。
在組播樹和路由表如上所述地完成後，路由器Rs基於重構建的 路由表分發組播數據包。在不滿足用於數據包分發的組播群所要求的 通信特性的情況下，由分發源路由器Rs和分發目的地路由器R自動 創建適合於組播群通信特性的組播樹和路由表，並且使用路由表進行
組播數據包分發。在例如超過閾值的情況下，路由器Rs開始重構建
組播樹以及重創建路由表，並且在完成重構建和重創建之後，以下述
順序將組播數據包從路由器Rs分發至其他路由器Rl至R5。
首先，分發源路由器Rs將數據包分發至路由器Rl、 R5。接下 來，接收數據包的路由器Rl將數據包分發至路由器R2、 R3，以及 路由器R5將數據包分發至路由器R4。照這樣，路由器Rs和其他路 由器Rl至R5虛擬地布置在樹狀結構中，在該樹狀結構中，路由器 Rs作為頂端節點，並且被設置為父節點(路由器R1、 R5)的路由器 分發數據包至被設置為子節點(路由器R2、 R3、 R4)的路由器(如 圖1中的網狀虛擬網絡中黑體箭頭所示)，由此，路由器Rs能夠將 組播數據包分發至所有路由器Rl至R5。如上所述，在例如組播群 所要求的路由器Rs中的CPU負荷率變大或者組播群通信特性超過其 閾值的情況下，進行組播樹的重構建和路由表的重創建，以消除將數 據包從路由器Rs直接分發至所有路由器Rl至R5的必要性，由此可 以減小路由器Rs的CPU負荷。
接下來，參照圖2描述路由器R的結構，該圖為示出了各路由 器R的結構的框圖。分發源路由器Rs和分發目的地路由器R1至R5 具有與另一方基本相同的結構。下面，以路由器Rs作為代表性示例 進行描述，並且此外，描述路由器Rs與其他路由器Rl至R5之間的 差別。如圖2所示，路由器Rs包括路由表(Table—new) 10、接口單 元11、轉發引擎12、監視單元13 (更具體地，監視裝置)、檢索用 資料庫14 (存儲裝置)以及路由表管理單元15 (控制裝置)。
路由表IO存儲有多個條目，在各條目中寫有表示數據包目的地 的網絡地址和表示將要使用的網絡接口的信息。當路由器Rs向其他 路由器R1至R5中的任意路由器傳送數據包時，轉發引擎12參照該
12路由表10。具體地，轉發引擎12檢査存儲在路由表10中的條目是 否包括描述了表示數據包目的地的網絡地址的條目，並且如果這樣的 條目存儲在路由表10中，則從那個條目中所寫的網絡接口向具有其
內所寫的網絡地址的路由器R發送數據包。如果數據包目的地未寫 在路由表10中的任何條目中，則轉發引擎12向設置為默認網關的路 由器R發送數據包。
接口單元11是與構成網狀虛擬網絡的實際網絡的接口部分，並 且與實際網絡連接用以發送和接收數據。具體地，接口單元ll向實
際網絡輸出自轉發引擎12輸入的數據包，並且向轉發引擎12輸出自 實際網絡輸入的數據包。
路由器Rs的轉發引擎12參照路由表10，並且經由接口單元11 而向其他路由器Rl至R5進行數據發送，或從其他路由器Rl至R5 進行數據接收。在重創建路由表10時，轉發引擎12經由接口單元 11向路由器Rl至R5發送以及從路由器Rl至R5接收重創建路由表 10所必需的列表信息(目的地列表、下一個目的地列表以及組播樹 (下文稱為樹)的分支數量和深度)。
更具體地，當從接口單元11輸入數據包時，轉發引擎12參照 路由表10以獲取一個或多個數據包目的地(發送目的地路由器R的 網絡地址)，並且經由接口單元11向發送目的地路由器R輸出自接 口單元11輸入的數據包。這時，取決於將要輸出到接口單元11的數 據包數量，如果數據包等級低，則轉發引擎12能夠破壞數據包。
在重創建路由表10時，轉發引擎12向路由表管理單元15輸出 自路由器Rl至R5中的任意路由器輸入的列表信息，並且向路由表 管理單元15所指定的一個或多個路由器R輸出自路由表管理單元15 輸入的列表信息。
路由器Rs的監視單元13經由接口單元11而定期測量組播群的 通信特性和網狀虛擬網絡的路徑特性，並且向檢索用DB14輸出測量 結果。監視單元13還測量路由器Rs中的CPU負荷率，並向路由表 管理單元15輸出測量結果。其他路由器Rl至R5的監視單元13各 自定期地僅測量網狀虛擬網絡的路徑特性。組播群的通信特性至少包括通過監視組播網絡中所形成的組播 群的數據包而計算得到的帶寬和通信延遲其中之一。網狀虛擬網絡的 路徑特性至少包括通過監視網狀虛擬網絡上流過的數據包計算得到 的帶寬和通信延遲其中之一。組播群的通信特性和網狀虛擬網絡的路 徑特性彼此不同之處在於組播群的通信特性是基於組播網絡上組播 群的組播數據包的流而計算得到的，而網狀虛擬網絡的路徑特性是基 於例如網狀虛擬網絡上的組播數據包或單播數據包的流而計算得到 的。
圖3示出了路由器RS中的檢索用資料庫(下文稱為檢索用DB)
的結構。檢索用DB14包括CPU負荷率閾值表、組播群通信特性閾 值表、網狀虛擬網絡的路徑特性表以及組播群通信特性表(下文稱為 CPU閾值表、通信特性閾值表、路徑特性表和通信特性表)。路由 器Rl至R5的檢索用DB14各自僅包括路徑特性表。在下面的描述 中，假設組播群的通信特性和網狀虛擬網絡的路徑特性各自包括帶寬 和通信延遲。
路由器Rs中的CPU負荷率的閾值登記到CPU閾值表中。CPU 負荷率的閾值由用戶設定。如前所述，當路由器Rs的CPU負荷率超 過其閾值時，進行組播分發的路由器Rs開始重構建樹，並且開始重 創建路由表10。
在通信特性閾值表中，組播群所要求的帶寬和通信延遲的閾值 被登記為組播群通信特性的閾值。在本實施方式中，由路由器Rs的 監視單元13在組播分發時最初所測量到的組播群通信特性的值被登 記為組播群的通信特性的閾值，由此，對於每一組播群可自動地設置 通信特性的閾值。
定期在各路由器R的路徑特性表中登記網狀虛擬網絡的帶寬和 通信延遲。對於從各路由器R到其他路由器R1至R5的每一虛擬路 徑，網狀虛擬網絡的路徑特性值被測量，並被登記到路徑特性表中。 由監視單元13定期更新路徑特性值。基於路徑特性表中登記的網狀 虛擬網絡的路徑特性，路由器Rs選擇具有路徑特性餘裕的通信路徑， 並創建路由器Rs的路由表10。同樣在其他路由器Rl至R5中，以類似的方式定期更新路徑特性表，並且創建路由器Rl至R5的路由 表10，同時基於路徑特性表中登記的網狀虛擬網絡的路徑特性而選
擇各自具有路徑特性餘裕的通信路徑。
在路由器Rs的通信特性表中，各組播群的帶寬和通信延遲被登 記為該群的通信特性。對於從路由器Rs到組播群的其他路由器Rl 至R5的每一虛擬路徑，登記組播群的通信特性，並由監視單元13 定期更新。如同CPU負荷率，各組播群的通信特性用作判斷值以判 斷是否應該重構建樹。具體地，如果組播群的通信特性超過其閾值， 則開始樹的重構建。如果組播群的通信特性未超過閾值，則不進行樹 的重構建，並且照現在的樣子使用已有的路由表IO執行組播分發。
在上述描述中，假設分發源路由器Rs具有圖3所示的檢索用 DB14以及分發目的地路由器Rl至R5各自在檢索用DB14中僅具有 路徑特性表。然而，當路由器Rl至R5中的任一路由器用作分發源 路由器時，那個路由器當然具有圖3所示的檢索用DB14。
路由表管理單元15創建及重創建路由表10。在重創建路由表 10時，路由表管理單元15基於CPU負荷率及其閾值或者基於組播 群的通信特性及其閾值，而確定樹的分支數量和深度。而後，基於網 狀虛擬網絡的路徑特性，路由表管理單元15開始重創建路由表10。
更具體地，在創建組播群時，路由表管理單元15通過通用方法 創建默認的路由表IO。即，路由表管理單元15計算從路由器Rs到 其他路由器Rl至R5的路徑跳轉數，並創建組播分發的默認路由表 10，從而使得數據包經過具有最小跳轉數的路徑。在使用默認的路由 表10進行組播分發的情況下，數據包從路由器Rs直接分發到其他 路由器R1至R5中的每一個。
在預定定時，路由器Rs的路由表管理單元15判斷是否有必要 重構建樹，即，是否有必要重創建路由表10，並且如果必要，則開 始重創建路由表10。路由表管理單元15通過判斷路由器Rs中的CPU 負荷率或者組播群的通信特性是否超過其閾值，來判斷是否有必要重
創建路由表10。如果路由器Rs中的CPU負荷率或組播群的帶寬超 過閾值，則路由器Rs的路由表管理單元15將樹的分支數量設置到其當前設定值的一半。組播群帶寬超過閾值表示組播群的帶寬變得比 閾值窄。如果組播群的通信延遲超過其閾值，樹的深度被設置到比當 前設定值深一級的深度。基於樹的分支數量和深度的設定值以及虛擬 網絡的路徑特性，路由表管理單元15開始重構建樹。
在最初進行自分發源路由器RS的組播分發的定時，判斷是否有 必要重構建樹。在隨後定時可進行類似的判斷，對於每一組播群而言， 這由用戶設置或自動設置所述定時。例如，根據時間設置定時，如， 每十秒或每一分鐘一次；或者根據被分發數據包的數量，如，每100
個或IOOO個數據包一次。可選地，這樣設置定時使得每次進行數據
包分發時都進行該判斷。
而且，路由表管理單元15在預定定時重置路由表10。具體地， 每當已進行10次或20次有關樹是否應被重構建的判斷時，或者每當 樹已被重構建5次或IO次時，路由表管理單元15通過通用方法重創
建路由表IO。結果，即使通過路由器R的數據包臨時增加並且樹被 構建為具有小的分支數量和深的深度，在臨時數據包的增加被消除後
的預定定時，樹也被重置，並且因此重構建樹是可能的，從而符合組 播群在那時所要求的通信特性。
接下來，參照圖4至13，將給出重構建樹及基於樹重創建路由 表10的流程描述。圖4至11示出在路由器R所執行的路由表創建 過程中順次創建的目的地列表、路由表等。以圖4至11所示順序重 構建樹，由此實現路由表10的重創建。圖12示出為重構建樹以及重 創建路由表而由分發源路由器執行的過程。圖13示出由各分發目的 地路由器和分發源路由器執行的類似過程。下面，將以這樣的實例情 況給出重創建路由表IO的過程描述EP，在從路由器Rs到組播群A (路由器Rl至R5)的組播分發過程中所使用的樹被重構建，並且 路由器Rs用作頂端節點。假設路由器Rs存儲有圖3所示的檢索用 DB14，並且其他路由器R1至R5被布置得如圖4至ll所示。如圖4 所示，以逆時針方向將路由器R和網狀虛擬網絡之間的接口稱作接 □ IF1至IF5。
首先，參照圖12描述分發源路由器Rs的操作。在圖12所示的路由表創建過程(1)中，路由器Rs的路由表管理單元15檢査是否 完成初始設定(S101)。通過判斷組播群A的通信特性的閾值是否 已被登記到檢索用DB14的通信特性閾值表(參見圖3)中，來判斷 是否完成初始設定。由於在初次分發數據包時己登記通信特性閾值， 所以判斷出當分發第二個數據包或後續數據包時初始設定已完成。 如果初始設定完成(即，如果組播群A的通信特性已經登記)
(S101判斷結果為是)，則過程行進到步驟S103。另一方面，如果 初始設定未完成(即，如果組播群A的通信特性未登記)(S101判 斷結果為否)，則路由表管理單元15將由監視單元13測量到的組播 群A通信特性的值作為通信特性閾值登記到通信特性閾值表中
(S102)，並且過程行進到步驟S103。
在步驟S103，路由表管理單元15參照檢索用DB14中的通信特 性表(參見圖3)，並獲取組播群的通信特性。組播群的通信特性由 監視單元13定期測量，並反映到通信特性表中。
路由表管理單元15獲取由監視單元13測量到的CPU負荷率， 並檢査CPU負荷率是否超過檢索用DB14中的CPU閾值表(參見圖 3)中登記的CPU負荷率閾值(50%) (S104)。如果閾值超過(S104 判斷結果為是)，則過程行進到步驟S106。
如果CPU負荷率未超過閾值(50%) (S104判斷結果為否)， 則檢査通信特性表中登記的組播群A的帶寬CAw是否超過通信特性 閾值表中登記的組播群A的帶寬的閾值Aw (S105)。換言之，檢査 由監視單元13測量到的組播群A的最新帶寬CAw是否超過閾值 Aw。組播群帶寬超過其閾值表示組播群帶寬變得比閾值窄。如果超 過閾值Aw (S105判斷結果為是)，則過程行進到步驟S106。
在步驟S106中，路由表管理單元15將樹的分支數量設置到當 前設定值的一半，並且過程行進到步驟S109以開始重構建樹。這時， 更新樹的深度以便與步驟S106中所設置的樹的分支數量相對應。
如果通信特性表中登記的組播群A的帶寬CAw未超過閾值Aw
(S105判斷結果為否)，路由表管理單元15則檢查通信特性表中登 記的組播群A的通信延遲CAd是否超過通信特性閾值表中登記的組
17播群A的通信延遲的閩值Ad (S107)。也就是說，檢查由監視單元 13測量到的組播群A的最新通信延遲CAd是否超過閾值Ad。如果 超過閾值Ad (S107判斷結果為是)，路由表管理單元15則將樹的 深度設置到比當前設置值深一級的深度(S108)，並且過程行進到 步驟S109以開始樹的重構建。這時，更新樹的分支數量以便與步驟 S108中所設置的樹的深度相對應。
如果通信特性表中登記的組播群A的通信延遲CAd未超過閾值 Ad (S107判斷結果為否)，則過程結束。在那樣的情況下，使用一 般的路由表10進行組播數據包分發。
應該指出的是，在本實施方式中，以CPU負荷率、帶寬和通信 延遲是否超過閾值這樣的順序進行判斷。然而，可以CPU負荷率、 通信延遲和帶寬是否超過閾值這樣的順序進行判斷。還能夠判斷CPU 負荷率和帶寬是否超過閾值或者判斷CPU負荷率和通信延遲是否超 過閾值。以這種方式，首先判斷CPU負荷率是否超過閾值，從而確 保避免路由器Rs變成高負荷狀態。如果不滿足組播群所要求的通信 特性，則路由器Rs開始重構建組播樹，並且因此，可以執行滿足組 播群所要求的通信特性的組播分發。
在步驟S109中，路由表管理單元15創建目的地列表(List—dest)， 在該列表中登記有數據包發送目的地路由器Rl至R5。接下來，路 由表管理單元15參照路徑特性表中登記的虛擬路徑a到c的路徑特 性(帶寬和通信延遲)(S110)，並且基於路徑特性而對目的地列 表中登記的路由器Rl至R5的等級進行排序(S111)。也就是說， 基於已由監視單元13所測量到的網狀虛擬網絡中虛擬路徑的最新帶 寬和通信延遲來對目的地列表中登記的路由器Rl至R5的等級進行 排序。這時，路由器Rl至R5的等級以帶寬降低的順序而變高，以 及以通信延遲增大的順序而變高。在路由器Rl至R5的虛擬路徑中， 路由器Rs選擇並利用具有路徑特性餘裕的虛擬路徑，由此構成從路 由器Rs到路由器R1至R5的虛擬路徑的實際網絡的帶寬負荷可被減 小。結果，如圖4所示，路由器Rs的目的地列表被創建，其中以路 由器R1、 R5、 R4、 R2、 R3的順序進行排序。下面，為簡化說明，假設通過步驟S101至S108的處理過程將樹的分支數量設置為2。路由表管理單元15將目的地列表分割成分支的設置數量(=2) (S112)，並且將已分割的目的地列表的初始地址(路由器Rl、 R5)登記到下一個目的地列表(List_nexthop)(SU3)，從而創建路由器Rs的目的地列表和下一個目的地列表，如圖5所示。
路由表管理單元15將下一個目的地列表中登記的地址(路由器Rl、 R5)和路由器R1、 R5同網狀虛擬網絡之間的接口 IF1、 IF5登記到路由表(Table_new) 10中(S114)。接下來，路由表管理單元15將列表信息(目的地列表、下一個目的地列表以及樹的分支數量和深度)輸出至轉發引擎12。轉發引擎12經由接口單元11向下一個目的地列表中登記的路由器R1、 R5發送各個列表信息(S115)。結果，創建如圖6所示的路由器Rs的路由表10，並且將目的地列表和下一個目的地列表分別發送到路由器R1、 R5。
接下來，參照圖13，將給出從路由器Rs接收列表信息的路由器Rl的操作描述，同時為簡化說明而省略路由器R5的操作描述。如圖13所示，路由器R1的轉發引擎12經由接口單元11從路由器Rs接收列表信息(目的地列表、下一個目的地列表以及樹的分支數量和深度)，並且將列表信息輸出至路由表管理單元15 (S116)。路由表管理單元15檢査發送源地址(路由器Rs)是否登記到路由器Rl中所存儲的路由表10中(S117)。由於發送源地址未登記(S117判斷結果為否)，所以將發送源地址(路由器Rs)以及路由器Rs同網狀虛擬網絡之間的接口 IF5登記到路由表10中(S118)。
路由器Rl的路由表管理單元15檢查地址是否已在存儲於路由器R1中的目的地列表中登記(S119)。由於地址已登記在目的地列表中(S119判斷結果為是)，因此路由表管理單元15參照路由器Rl的路徑特性表中登記的虛擬路徑的路徑特性(帶寬和通信延遲)(S120)，並且基於該路徑特性而對目的地列表中登記的路由器R2、R3的等級進行排序(S121)。具體地，基於已由監視單元13所測量到的網狀虛擬網絡中虛擬路徑的最新帶寬和通信延遲來對目的地列表中登記的路由器R2、 R3的等級進行排序。這時，路由器R2、 R3的等級以帶寬降低的順序而變高，以及以通信延遲增大的順序而變高。在到路由器R2和R3的虛擬路徑中，路由器R1選擇並利用具有路徑特性餘裕的虛擬路徑，使減小構成從路由器Rl到路由器R2、R3的虛擬路徑的實際網絡的帶寬負荷成為可能。
接下來，路由表管理單元15將目的地列表分割成樹的分支數量(=2) (S122)，並且將已分割的目的地列表的初始地址(路由器R3、 R2)加到下一個目的地列表(S123)。此外，路由表管理單元15將下一個目的地列表中登記的地址(路由器R3、 R2)和路由器R3、 R2同網狀虛擬網絡之間的接口 IF2、 IF1登記到路由表10中(S124)。結果，創建如圖7所示的路由器R1的目的地列表、下一個目的地列表和路由表10。而且，以與路由器R1相同的過程創建如圖7所示的路由器R5的目的地列表、下一個目的地列表和路由表10。
路由器Rl的路由表管理單元15向轉發引擎12輸出列表信息(目的地列表、下一個目的地列表以及樹的分支數量和深度)。轉發引擎12經由接口單元11向下一個目的地列表中登記的路由器R3、R2發送列表信息(S125)。結果，如圖8所示，目的地列表和下一個目的地列表分別從路由器R1發送到路由器R3、 R2。如圖8所示，以與路由器R1相同的過程，也將目的地列表和下一個目的地列表從路由器R5發送到路由器R4。這樣， 一個方向的樹完成，在該樹中路由器Rs用作頂端節點。
接下來，參照圖13，將給出從路由器R1接收列表信息的路由器R2的操作描述。為簡化說明，省略從路由器R1、 R5分別接收列表信息的路由器R3、 R4的操作描述。如圖13所示，路由器R2的轉發引擎12經由接口單元11從路由器R1接收列表信息(目的地列表、下一個目的地列表以及樹的分支數量和深度)，並且將列表信息輸出至路由表管理單元15 (S116)。路由表管理單元15檢査發送源地址(路由器Rs)是否登記到路由器R2中所存儲的路由表10中(S117)。由於發送源地址未登記(S117判斷結果為否)，所以轉發引擎12將發送源地址(路由器Rl)以及路由器Rl同網狀虛擬網絡之間的接
20口 IF5登記到路由表10中(S118)。
路由器R2的路由表管理單元15檢查地址是否登記在存儲於路由器R2中的目的地列表中(S119)。由於沒有地址登記在目的地列表中(S119判斷結果為否)，所以路由表管理單元15檢査路由器R2是否為頂端節點(S126)。由於路由器R2不是頂端節點(S126判斷結果為否)，所以路由表管理單元15將路由器R2的父地址(路由器R1)作為默認路徑登記到路由表10中(S127)，並且將列表信息(下一個目的地列表)輸出至轉發引擎12。轉發引擎12經由接口單元11向路由器R1 (路由器R2的父地址)發送列表信息(S128)。結果，如圖9所示的路由器R2的路由表10完成，並將下一個目的地列表發送到路由器Rl。藉助於與路由器R2相同的過程，創建路由器R3、 R4的路由表10，並將下一個目的地列表分別發送到路由器R1、 R5。
接下來，參照圖13，將給出從路由器R2、 R3接收列表信息(下一個目的地列表)的路由器R1的操作描述。應當指出的是，為簡化說明而省略從路由器R4接收列表信息的路由器R5的操作描述。如圖13所示，路由器Rl的轉發引擎12將經由接口單元11而從路由器R2、 R3接收到的列表信息(下一個目的地列表)輸出至路由表管理單元15 (S116)。路由表管理單元15檢査是否有一個或多個發送源地址(路由器R2、 R3)登記到路由器R1中所存儲的路由表10中
(S117)。由於發送源地址已登記(S117判斷結果為是)，所以路由表管理單元15檢査地址是否登記到路由器Rl中所存儲的目的地列表中(S119)。由於沒有地址登記到目的地列表中(S119判斷結果為否)，因此路由表管理單元15檢査路由器Rl是否為頂端節點
(S126)。由於路由器R1不是頂端節點(S126判斷結果為否)，所以路由表管理單元15將路由器R1的父地址(路由器Rs)作為默認路徑登記到路由表10中(S127)，並且將列表信息(下一個目的地列表)輸出至轉發引擎12。轉發引擎12經由接口單元11向位於路由器R1的父地址的路由器Rs發送列表信息(S128)。結果，如圖IO所示的路由器RI的路由表IO完成，並且將下一個目的地列表發送到路由器Rs。藉助於與路由器R1類似的過程，如圖10所示的路由器R2的路由表10完成，並且將下一個目的地列表發送到路由器Rs。
接下來，參照圖13，將給出從路由器R1、 R5接收列表信息(下一個目的地列表)的路由器Rs的操作描述。如圖13所示，路由器Rs的轉發引擎12經由接口單元11接收列表信息(下一個目的地列表)，並且將列表信息輸出至路由表管理單元15 (S116)。路由表管理單元15檢査發送源地址(路由器R1)是否登記到路由器Rs中所存儲的路由表10中(S117)。由於發送源地址已登記(S117判斷結果為是)，所以路由表管理單元15檢査地址是否登記到路由器Rs中所存儲的目的地列表中(S119)。由於沒有地址登記在目的地列表中(S119判斷結果為否)，因此路由表管理單元15檢查路由器Rs是否為頂端節點(S126)。由於路由器Rs是頂端節點(S126判斷結果為是)，所以路由表管理單元15將已登記在下一個目的地列表中的地址登記到路由表10中(S129)，由此完成如圖11所示的路由器Rs的路由表10。
結果，來自路由器Rs的組播分發中所使用的路由器R的路由表IO完成。BP,雙方向樹完成，在該樹中路由器Rs用作頂端節點。具體地，在從路由器Rs開始的組播分發過程中由路由器R所使用的路由器R的路由表IO完成。路由器Rs基於已完成的路由表IO而進行數據包分發。
應當指出的是，在本實施方式中，網狀虛擬網絡由6個路由器R形成，但是這並非限定性的。網狀虛擬網絡可以由任意多個路由器R形成。構成另一個組播樹的路由器R可連接到該網狀虛擬網絡。在本實施方式中，對於每一個路由器R連接一個通信設備PC，但是這並非限定性的。對於每一個路由器R可連接多個通信設備PC。
如上所述，在本實施方式提供的組播分發系統中，當在連接到網狀虛擬網絡的路由器R之間進行組播分發時，為每一組播群設置通信特性的閾值，並且如果組播群的通信特性超過閾值，則基於網狀虛擬網絡的路徑特性重構建樹，由此創建組播群的路由表10。結果，組播分發系統能夠藉助於組播群所要求的通信特性進行組播分發。
利用遵從組播群所要求的通信特性的路由表10，進行組播分發
的路由器Rs用作頂端節點，並且其他路由器R1至R5虛擬地布置為
樹狀結構，由此數據包從設置為父節點的路由器向設置為子節點的路
由器順次分發。結果，進行組播數據包分發的路由器Rs不必直接向
所有其他路由器Rl至R5分發數據包，因此可以減小進行組播數據
包分發的路由器Rs的CPU負荷。
隨著分發組播數據包的路由器Rs的CPU負荷的減小，可以減小在來自路由器Rs的組播數據包分發時的實際網絡帶寬負荷。結果，即使路由器Rs的CPU負荷增大或者真實網絡帶寬負荷增大，滿足組播群所要求的通信特性的組播分發也可以通過改變組播數據包分發路徑來實現，而無需增加硬體，諸如為路由器Rs增加更多CPU或者擴展實際網絡帶寬。因此，可以抑制不經濟的設備投資並可確保組播分發的可量測性。
通常，如果由於諸如從路由器R1至R5發送來並且通過網狀虛擬網絡的數據包數量增加而使帶寬變窄，則通過破壞自路由器R分發來的數據包而產生通信延遲。然而，本實施方式的路由器R定期重創建路由表10，由此可以進行分發而無需破壞組播數據包。
在本實施方式的路由器R中，路由表IO被定期重置為用以從路由器Rs直接向其他路由器Rl至R5分發組播數據包的默認路由表10。在組播分發時，路由器R判斷是否滿足通信特性閾值，並且重創建路由表10。結果，即使通過網狀虛擬網絡的數據包數量臨時增加而導致通信延遲，也可以在通信延遲消除並且可執行組播數據包分發時改變通信路徑。以這樣的方式，由於可以根據網狀虛擬網絡的路徑特性改變路由表10，所以路由器R能夠根據網狀虛擬網絡的路徑特性，通過選擇具有組播群所要求的通信特性的通信路徑來執行組播數據包分發。
工業適用性
根據本發明，可以根據分發源路由器負荷狀態和已連接的組播
23群的通信特性來重構建組播樹，由此可以通過選擇滿足組播群所要求的通信特性的通信路徑來執行組播分發。
權利要求
1.一種組播分發系統，在該系統中，從分發源路由器向構成在網狀虛擬網絡上形成的組播網絡的多個分發目的地路由器進行組播分發，其中，分發源路由器包括第一監視裝置，其被配置成用以監視和檢測分發源路由器的CPU負荷率、在組播網絡上所構建的組播群的通信特性以及所述網狀虛擬網絡的路徑特性；存儲裝置，其被配置成用以存儲CPU負荷率的閾值和組播群的通信特性的閾值；以及第一控制裝置，其被配置為基於由所述第一監視裝置檢測到的所述網狀虛擬網絡的路徑特性以及至少是下述兩個比較結果其中之一，開始重構建定義了從分發源路由器開始的數據包分發路徑的組播樹，並且基於組播樹開始重創建確定了組播分發路徑的路由表，其中所述兩個比較結果為由所述第一監視裝置檢測到的CPU負荷率和存儲在所述存儲裝置中的CPU負荷率的閾值之間的比較結果以及由所述第一監視裝置檢測到的組播群的通信特性和存儲在所述存儲裝置中的組播群的通信特性的閾值之間的比較結果。
2. 根據權利要求1所述的組播分發系統，其中，分配源路由器 的所述第一控制裝置被配置為在至少是由所述第一監視裝置監視到 的CPU負荷率的值以及由所述第一監視裝置監視到的組播群的通信 特性的值其中之一超過其閾值的情況下，改變組播樹的分支數量和深 度，並基於改變後的組播樹的分支數量和深度以及所述網狀虛擬網絡 的路徑特性而開始重構建組播樹。
3. 根據權利要求1或2所述的組播分發系統，其中，每個分發 目的地路由器包括第二監視裝置，其被配置成用以監視所述網狀虛擬網絡的路徑特性；通信裝置，其被配置成分發和接收用於指示數據包分發的分發〈曰息；第二控制裝置，其被配置為基於包含在所述分發信息中的組 播樹分支數量和深度以及由所述第二監視裝置所獲取的所述網狀虛 擬網絡的路徑特性，而對定義了從分發源路由器開始的數據包分發路 徑的組播樹實施重構建，並且基於組播樹來對確定了組播分發路徑的 路由表實施重創建；以及其中，當所有分發目的地路由器的路由表的重創建完成時，分 發源路由器的所述第一控制裝置完成組播樹。
4. 根據權利要求1至3中任意一項所述的組播分發系統，其中， 分發源路由器的所述存儲裝置將分發源路由器的所述第一監視裝置 最初所檢測到的組播群的通信特性作為組播群的通信特性的閾值而 存儲。
5. 根據權利要求1至4中任意一項所述的組播分發系統，其中， 在組播分發時，分發源路由器的所述第一控制裝置在預定定時判斷是 否應該重構建組播樹。
6. —種組播分發方法，在該方法中，從分發源路由器向構成在 網狀虛擬網絡上形成的組播網絡的多個分發目的地路由器進行組播 分發，該方法包括下述步驟由分發源路由器監視和檢測分發源路由器的CPU負荷率、在組 播網絡上所構建的組播群的通信特性以及所述網狀虛擬網絡的路徑 特性；由分發源路由器讀取已存儲在存儲裝置中的CPU負荷率的閾值 和組播群的通信特性的閾值；以及在至少是CPU負荷率的值以及組播群的通信特性的值其中之一 超過CPU負荷率的閾值或者組播群的通信特性的閾值的情況下，由 分發源路由器改變組播樹的分支數量和深度，基於組播樹的分支數量和深度以及所述網狀虛擬網絡的路徑特性，開始重構建組播樹以從分 發源路由器分發數據包，並且基於組播樹而開始重創建確定了組播分 發路徑的路由表。
全文摘要
本發明提供了一種組播分發系統，其可以通過選擇滿足組播群所要求的通信特性的通信路徑來進行組播分發。分發源路由器(Rs)經由連接到多個路由器的網狀虛擬網絡、基於應用而向構成組播群的路由器(R1至R5)進行組播分發。當CPU負荷率和組播群的通信特性超過閾值時，分發源路由器更新組播樹的分支數量和深度，該組播樹分發來自路由器的數據包，並開始重構建組播樹。當重構建組播樹時，分發源路由器參照網狀虛擬網絡的路徑特性，以較高優先級選擇具有足夠的路徑特性的通信路徑，並基於組播樹而生成路由表。
文檔編號H04L12/56GK101658001SQ20088001170
公開日2010年2月24日 申請日期2008年4月9日 優先權日2007年4月12日
發明者梅島慎吾 申請人:山葉株式會社