通信網絡中的子組多播的製作方法
2023-09-23 14:55:00 1
專利名稱：通信網絡中的子組多播的製作方法
技術領域：
本發明涉及組網和通信技術，並且更具體地涉及數字通信網絡中從信源節點中多播信息給一個或多個目的節點。
背景技術：
諸如網際網路的數字通信網絡是允許將儲存在一個位置上的信息分發給位於不同地理位置上的一個或多個用戶的公知系統。此信息(在本文中也稱為「消息」)能夠採用多種形式之中的任何一種形式，包括但不限於，文本、靜止圖象、音頻和視頻信息的形式。
雖然把數字通信網絡用於將信息(例如，文件)從一個信源移動到一個目的地不是與眾不同的，但日益希望將同一信息從一個信源傳送至多個目的地。例如，對於許多接收器來說，通常觀看在單一網際網路網站上始發的諸如流視頻的同一信息。
允許信息在多個信源和目的地之間進行傳送的一種技術稱為「多播」。例如，已如下定義利用網際協議(IP)支持的多播「IP多播是將IP數據報有效傳輸至利用單個IP目的地址識別的一組零個或多個主機的有效傳輸方式」(Deering，1989)。現在將更具體討論多播。
在下面，討論IP多播。IP(和其他類型的)多播通過使信源能夠發送消息的單個拷貝給利用單個IPD類別多播地址間接識別的確實想接收信息的多個接收器來有效地支持一對多和多對多傳輸。此種機制遠比同時發送多個消息給每個接收器或將此消息廣播給網絡上的所有節點有效得多。通過在網絡中合適的點上而不是在終端系統上複製數據，IP多播由於類似生成樹的數據分布樹的效率是多方會議的一種自然解決方案。
多播基於「駐留在已有協議頂部」的一系列特定協議，以便將數據有效分發給所有感興趣方。利用IP多播，接收機並不需要為了從發送器中接收業務而知道發送器是誰或在哪裡。發送器不會知道接收機是誰。因為網絡優化傳送，所以發送器或接收器都不需要關心網絡技術。
多播是一種基於接收機的概念；接收機通過利用諸如網際網路組管理協議(Internet Group Management Protocol)(IGMP)的協議將其意圖通知其子網絡上的多播路由器來加入特定的多播對話組。隨後利用網絡基礎結構將業務傳送至那個組的所有成員。為了驗證當前的成員資格，本地多播路由器周期性地發送IGMP主機成員資格查詢給「所有主機(all hosts)」組。為了避免在每個成員主機都對此查詢應答時將會出現的擁塞，每個主機將其報告的傳輸延遲隨機的時間間隔。在此時間間隔結束時，此主機僅在它未發現來自另一主機的同一組的報告時才發送其報告。結果，對於每個有效組地址來說，儘管許多主機可能具有成員資格，但在應答中只發送一個成員資格報告。IGMP也可以用於將組成員資格信息從本地路由器傳送至其他的多播路由器。
為了將多播分組從信源傳送至其他網絡上的目的地節點，多播路由器需要交換其已從直接連接至這些多播路由器的主機的組成員資格中收集的信息。具有許多不同的算法和協議用於交換此路由選擇信息，諸如距離矢量多播路由選擇協議(Distance Vector MulticastRouting Protocol)(DVMRP)、首先朝向開放式最短路徑的多播擴展(Multicast extension to Open Shortest Path First)(MOSPF)和與協議無關的多播(Protocol Independent Multicast)(PIM)。根據通過這些協議之一獲得的路由選擇信息，在將多播分組發送給多播組時，多播路由器決定是否將此分組傳送至它們的網絡。最後，葉子路由器根據IGMP信息確定在其物理連接的網絡上是否具有那個特定組的任何成員並決定是否傳送此分組。
如果發送器將其信息(例如，視頻或音頻)流分層，不同的接收機能夠選擇接收不同的業務量並因此接收不同的質量。為此，此發送器必須將此信息編碼為基本層(可接受的最低質量)和許多增強層，每個增強層以更多帶寬為代價附加更多質量。例如，如果此信息是視頻信息，這些附加層可以增加幀速率或增加圖象的空間解析度或同時增加這二者。將每個層發送給不同的多播組並且接收機能夠單獨決定籤約多少層。
圖1表示IP多播情況的一個示例，其中將信息流(例如，視頻流)發送給四個接收器之中的每個接收器第一客戶機101、第二客戶機103、第三客戶機105和第四客戶機107。第一多播路由器(MR1)109能夠在信源111和第二多播路由器(MR2)113與第三多播路由器(MR3)115之中每一個路由器之間為信息選擇路由。第一客戶機101與第二客戶機103通過通知第二多播路由器113加入此組；並且第三客戶機105與第四客戶機107利用第三多播路由器115進行同樣操作。第一客戶機101接收諸如適於優化用於無線環境的編解碼器的基本層(表示為「A1」的分組)，而第二客戶機103為了更好的服務質量(例如，更好的視頻質量)而接收此基本層和附加層(表示為「A2」的分組)。第三客戶機105與第四客戶機107均接收表示為B1的分組的不同基本層，例如，適於有線線路編解碼器的層。
為了實現有效傳輸，構造連接此多播組的所有成員的生成樹。只有多播消息的一個拷貝通過(源伺服器111與第一多播路由器MR1 109之間)網絡中的任何鏈路，並且僅當路徑在路由器上(例如，在這三個多播路由器MR1 109、MR2 113與MR3 115上)發散時才進行此消息的拷貝。注意業務複製點(諸如MR1 109、MR2 113和MR3 115)上多播流的「合併」涉及複合算法。
有關IP多播的更多信息可在Andrew S.Tanenbaum，ComputerNetworks，Third Edition，Prentice-Hall，New Jersey，1996上以及在網際網路的「IP Multicast Initiative(IPMI)」的網站www.ipmulticast.com上找到。
在下面，討論可靠多播情況。IP多播是不可靠的(基於用戶數據報協議或「UDP」)並提供盡力傳送，這導致偶爾的分組丟失。對於實時操作的諸如音頻與視頻的許多多播應用來說，這可能是可接受的(只要分組丟失在合理的限制內)。然而，對於例如複製品之間的同步消息的一些應用來說，必須保證不丟失關鍵信息。
可靠多播協議必須解決處理的一些典型問題如下●確認分組接收(ACK)或表示分組丟失(NACK)(也稱為ACK/NACK內爆效應)時的網絡負載，這通常利用聚合機理來解決。
●組管理；封閉、開放限制和開放無限制組。
●擁塞控制●可放縮性各種可靠協議與框架(例如，可靠多播框架)已被建議用於多播數據傳送。不同於其中可靠的順序數據傳送的要求相當籠統的單播情況，不同的多播應用對於可靠性要求非常不同。例如，一些應用要求傳送遵守總的順序，而許多其他的應用並不如此要求。一些應用使許多或所有成員發送數據，而其他的應用僅僅具有一個數據源。一些應用具有複製數據，因此幾個成員能夠發送數據項，而對於其他應用來說，在單個信源上始發所有數據。這些不同都會影響可靠多播協議的設計。一些示例的可靠多播協議為可靠多播協議(ReliableMulticast Protocol)(RMP)、可放縮可靠多播(Scalable ReliableMulticast)(SRM)、可靠多播傳送協議(Reliable MulticastTransport Protocol)(RMTP)、(Multicast File Transfer Protocol)多播文件傳送協議(MFTP)。
IETF中的RMT(可靠多播傳送Reliable Multicast Transport)工作組期望開始標準化不同的協議示例用於一對多多播應用。參見IETF的可靠多播傳送(RMT)工作組的網站www.iftf.org/html.charters/rmt-charter.htm/。
例如，有關可靠多播的更多信息能夠在IP MulticastInitiative(IP多播初始)(IPMI)網站www.ipmulticast.com上找到。
I在下面，討論實時傳送(控制)協議，即RT(C)P。實時傳送協議(RTP)提供端對端網絡傳送功能，適於通過多播或單播網絡服務來發送諸如音頻、視頻或仿真數據的實時數據的應用。RTP提供的功能包括有效負載類型識別、順序編號、時間標記和傳送監視。
利用控制協議(RTCP)擴充數據傳送功能，此協議用於監視服務質量(QoS)並傳送有關正在進行的對話中的參與者的信息。會議中的每個媒體流利用單獨的RTCP流作為單獨的RTP對話進行發送。RTCP報告提供有關從特定信源接收的數據的統計信息，諸如自前一報告以來丟失的數據分組的數量、丟失數據分組的累積數量、到達間抖動等。
在下面，討論複製和例如類似於Quorum Consensus(定數一致)同步的同步情況。在服務或資源在系統的不同接點上出現多個邏輯上相同的示例時，「複製」此服務或資源。接入此資源的請求能夠傳送給其任何一個示例。幾種機理可用於同步不同的拷貝也稱為複製並使之一致。在複製中，不同的服務接入點(例如，IP位址)用於每種服務示例。
複製服務的主要原因如下●負載分布(拷貝到多個主機上的服務)●性能增加(服務被拷貝到多個主機並且有可能更靠近實際客戶機)●可利用性(服務被拷貝到多個主機的服務)一般在所有客戶機需要寫訪問整個服務時(或在此服務不能分離成獨立實體時)進行複製。
在下面，討論複製同步情況。在通過網絡共享數據的情況中，參與者也許試圖(幾乎)同時操縱共享目標。對共享目標實施同時動作可以導致用戶之間不一致的觀點。如果不仔細協調，連續的同時動作很快就會引起對於什麼應該是同一共享數據的不同觀點。
複製資源需要保持同步/一致/相干；即，任何寫訪問必須傳送給所有的複製品。大致有兩種方案用於這樣的同步在下面，討論主/從策略。對於此方案，具有保持主拷貝的一個主伺服器和(用於每個複製品)幾個從屬伺服器。主拷貝服務於所有的更新請求，但從屬複製品是通過從主伺服器中接收改變或從主伺服器中進行拷貝來更新的(同步的)客戶機可以從主機和從機兩者的樣本讀取數據。
主伺服器可以是可變的或固定的。在可變的主伺服器的情況中，能寫到任何伺服器上。相應伺服器隨後負責更新所有的複製品。此程序稱為Read-One-Write-All(讀取一個寫入所有)(ROWA)。在固定的伺服器(也稱為「簡單ROWA」)的情況中，必須對那個伺服器完成所有的寫入操作。雖然此機制具有故障中心點(主伺服器)，但集中控制使之相對容易解決請求之間的衝突和保持一致性。已定義了幾種增強情況用於可變的和固定的主伺服器模型。
在下面，討論分布式更新控制(表決)情況。此方案比主/從策略更堅固，這是因為不需要故障(主)中心點。基本思想是要求客戶機在讀或寫複製的文件之前請求並獲得多個伺服器的準許。相應策略稱為Quorum-Consensus(定數一致)QC機制。
已經定義幾種變化情況，諸如一致多數QC對於每次寫或讀訪問來說，需要大多數伺服器的準許。
加權多數QC類似於一致多數QC，但現在一個伺服器可以具有一票以上的表決權(例如，可靠或高速伺服器)。
鬼影表決(voting with ghosts)偽(鬼影)伺服器被用於出現故障的每個伺服器。此鬼影伺服器只參與寫定數。此機制保證寫定數一致在幾個伺服器出現故障的情況中仍然是有可能的(因為寫定數通常由大多數伺服器構成)。
已定義許多其他的機制。一般策略總是減小(用於寫與讀訪問)定數的大小，以加速同步處理(並減少網絡通信)；和限制伺服器故障的影響(例如，鬼影表決)。
相干協議是相干/同步模型的特定實施方式。可以有幾種協議用於單個模型。至於哪個協議是最佳的，這取決於諸如讀/寫速率、同時接入服務的客戶機的數量等問題。用於測量所有模型的標準是順序一致的，這表示所有處理以同一順序查看所有存儲基準。因果一致性、流水線式隨機存取存儲器(PRAM)一致性和處理器一致性都削弱了處理以同一順序查看所有存儲基準的概念。另一方案是弱一致性、釋放一致性和入口一致性，其中存儲不總是一致的，但編程者能夠利用諸如進入或離開關鍵區域的某些動作來迫使它變得一致。
在區域網(LAN)中，使用中央協調程序負責不同複製品之間的同步是可行的。然而，在廣域網(WAN)中，此中央協調方案通常由於所牽涉的高等待時間(花費太多的時間來更新所有的複製品)和故障中心點而不是可行的。在WAN中，因此需要分布式解決方案。有關同步策略的更多細節能夠在Andrew S.Tanenbaum，DistributedOperating Systems，Prentice-Hall，New Jersey，1995；以及Coulouris等人的Distributed SystemsConepts and Design，Addison-Wesley，Wokingham，1991中找到。
利用多播，總是將信息發送至已登記相應多播組(並且正在監聽此多播埠)的所有客戶機。在封閉多播組的情況中，可以知道客戶機的數量。
可以在網際網路的http//search.ietf.org/internet-drafts/draft-ietfidmr-igmp-v3-04.tex上找到的Internet GroupManagement Protocol，版本3(IGMPv3)的草案將增加信源選擇可能性，諸如只監聽一些信源或監聽除了不需要的信源組之外的所有信源。然而，問題在於還沒有預知能夠只多播給一個子集的成員資格主機的機制。
有時(例如，對於QC同步來說)，可能需要一種類型的多播，其中能夠在總的多播組中定義子組的大小，這表示定義某一多播消息的接收器的數量。在QC同步的情況中，能夠定義應接收某一同步消息的接收器的數量。
如上所述，RTCP用於傳送有關正在進行的對話中的參與者的信息。此信息通過端對端來提供，即，從目的地將此信息提供給信源並且此信息只在RTP協議用於傳送通常為實時的多媒體數據的情況中起作用。
最近的IETF草案(即，可通過網際網路在網址http//search.ietf.org/internet-drafts/draft-dhelder-somcast-00.txt上獲得的「Ipv4 Option for Somecast」)描述「某些播(Somecast)」，這是在IP標題中包括多達9個的目的地址並當這些目的地必須使用同樣的鏈路時就執行組合單播路由選擇的機制。在路由器確定目的地使用了不同的鏈路時，將分組作為通常單播進行發送。同樣，如IETF草案中所述，此解決方案不是可擴展的。而且，此解決方案具有諸如要求信源必須已經知道所有目的地的缺點。
因此，需要一種機制，使消息能夠只多播給給定的成員資格主機集之中的一個子組。
發明概述應強調在此說明書中使用的術語「包括」與「包含」用於指定所述特性、整數、步驟或組成部分的存在，並且這些術語的使用不排除一個或多個其他特性、整數、步驟、組成部分或組組的存在或增加。
根據本發明的一個方面，利用在包括一個或多個具有多播能力路由器的通信網絡中用於將消息從一個信源分發給一個或多個主機的方法和設備來實現上述與其他目的。這利用以下步驟來實現在第一具有多播能力路由器中，生成第一表，此第一表識別連接至第一具有多播能力路由器的分支，並且對於每個被識別分支來說，此第一表包含它能夠從中確定多少主機是此分支的一部分的成員資格相關信息。第一具有多播能力路由器能夠接收將被分發的消息和第一值N1，此第一值N1指定此消息將分發給多少主機。第一具有多播能力路由器隨後利用第一表來識別N1個主機及其相應分支，並將此消息與第二值N2一起分發給每個被識別分支，此第二值N2指定此消息將分發給此分支內的多少主機。
在本發明的另一方面中，至少一個被識別分支包括第二具有多播能力路由器；並且此技術還包括在每個第二具有多播能力路由器中，生成第二表，此第二表識別連接至第二具有多播能力路由器的分支，並且對於每個識別分支來說，此第二表包含它從中能夠確定多少主機是此分支的一部分的成員資格相關信息；在第二具有多播能力路由器中，利用第二表來識別N2個主機及其相應分支；而且在第二具有多播能力路由器中，將此消息與第三值N3一起分發給每個被識別分支，此第三值N3指定此消息將分發給此分支內的多少主機。以這種方式，實現將消息分發給子組的遞歸技術。
在可選擇實施例中，分支可以只將此消息分發給此分支內的所有主機。在其他的選擇方案中，可以將此消息單播給此分支內的特定主機。
在本發明的其他實施例中，所生成的表還包括與每個分支主機相關的一個或多個度量。各種度量可以選擇地指示下面任何一個度量此分支主機與第二具有多播能力路由器之間的距離；此分支主機與第二具有多播能力路由器之間的延遲；和此分支主機與第二具有多播能力路由器之間的通信相關的費用；和此分支主機與第二具有多播能力路由器之間的通信相關的帶寬；此分支主機與第二具有多播能力路由器之間的傳輸延遲；和/或可靠性度量。
本發明還包括用於確定多少主機位於通信網絡的分支內的技術。
附圖的簡要描述通過結合附圖閱讀下面的具體描述將明白本發明的目的和優點，其中圖1表示數字通信網絡中將視頻流發送給四個接收器的IP多播情況的一個示例；圖2是根據本發明的通信網絡的一部分的方框圖，其中此通信網絡包括利用具有多播能力路由器(R1，R3，R6，R7，R8)和標準(不具有多播能力)路由器(R2，R4，R5)以各種方式互連的許多主機(H1，H2，H3，H4，H5，H6，H7，H8)；圖3是表示根據本發明的一個實施例用於將信息多播給許多主機的技術的流程圖；和圖4是表示根據本發明的另一方面用於確定分支成員資格信息的技術的流程圖。
具體描述現在將結合附圖描述本發明的各種特性，其中相同部分利用相同標號來標識。
現在將結合許多示例性實施例來更具體地描述本發明的各個方面。為了便於理解本發明，根據利用計算機系統和/或通信網絡的單元執行的動作的順序來描述本發明的許多方面。將認識到在每個實施例中，各種動作能夠利用專用電路(例如，互連以執行特殊功能的分立邏輯門電路)、利用由一個或多個處理器執行的程序指令或利用這二者的組合來執行。而且，另外能夠認為可以在包含適當的使處理器完成本文所述技術的計算機指令集的任何形式的諸如固態存儲器、磁碟、光碟或載波(諸如射頻、音頻或光頻載波)的計算機可讀載體內完全實施本發明。因而，本發明的各個方面可以以多種不同形式來實施，並且所有這樣的形式都認為在本發明的範疇內。對於本發明的各個方面之中的每個方面，任何如此形式的實施例在本文中可以稱做為執行所述動作「而被構造的邏輯」或可選擇地稱做用於執行所述動作的「邏輯」。
本發明提出使之有可能將消息只多播給整個多播接收器分組之中的一個子組的多播接收器的方法和設備。此子組的多播接收器能夠分布在此網絡的不同分支中或者能夠位於單個分支內。為了說明本發明的各個方面，參見圖2，圖2是包括利用具有多播能力路由器(R1，R3，R6，R7，R8)和標準(不具有多播能力)路由器(R2，R4，R5)以各種方式互連的許多主機(H1，H2，H3，H4，H5，H6，H7，H8)的通信網絡的一部分的方框圖。能看出相對任何一個路由器R1，...，R8，可以定義許多分支。例如，分支201是路由器R1的許多分支之一。分支201包括路由器R7與R8和主機H7與H8。任何一個分支內的路由器自身也可以具有分支。例如，相對(包括在分支201內)路由器R7來說，定義兩個分支包括路由器R8與主機H8的第一分支203；和只包括主機H7的第二分支。
為了能夠執行其中信源(或任何其他示例情況)定義消息接收器數量的子組多播，可以完成以下步驟1.如果未能通過例如管理的某一其他方式獲得此信息，計算將執行子組多播的實體可利用的接收器的總數。
2.計算每個分支的接收器的數量。
3.將此信息只多播給整個組的多播接收器之中的一個子組的多播接收器。
為了使子組多播是有效的，可以根據用於(多播)路由選擇協議的任何一個度量(諸如距離、延遲、費用、帶寬、可靠性等)來進行子組多播。在本發明的可選擇實施例中，子組多播能夠基於度量的組合而不是僅僅基於單一度量。僅僅為了便於本發明的理解，只在此所述的示例性實施例中說明單一度量。
應明白對於實施本發明來說，單獨執行上述三個步驟不是關鍵的。例如，能夠構造其中通過每個分支的接收器數量的計算也知道將執行子組多播的實體可利用的接收器的總數的實施例，因此步驟1與2實際組合成單個步驟。
還應明白子組多播可以是遞歸處理，從而每個具有多播能力路由器將消息傳送至具有無多播能力路由器的分支，因而那個分支中的每個主機將例如通過單播來接收此消息，或反而生成並將它自己的子組多播命令發送給它的一個或多個分支，結果讓這些分支之中的每個分支內的一個或多個具有多播能力路由器確切地確定哪些主機將接收此消息。當然，不要求具有多播能力路由器在將消息傳送至其分支時使用多播，它也能夠選擇根據接收的多播消息只將專用的單播消息發送至必須通知的一定數量的成員。
通過採用諸如在此公開文本的背景技術部分所述的任何一種可靠多播機制與協議可以獲得可靠性能。
用於從具有多播能力路由器中將消息多播給一個或多個主機的技術的示例性實施例表示在圖3的流程圖中。此具有多播能力路由器可以從另一路由器中接收消息以及表示此消息所希望的接收器的數量是數字的一個值，N1(步驟301)。可選擇地，如果具有多播能力路由器是此消息的信源，則在本地確定N1的值。
如果還未這樣做，則此具有多播能力路由器生成識別連接至第一具有多播能力路由器的分支的一個表。對於每個識別分支來說，此表包括它從中能夠確定多少主機是此分支一部分的成員資格相關的信息。選擇地，根據一些實施例，所生成的表還包括與每個分支主機相關的一個或多個度量(步驟303)。
此具有多播能力路由器使用此表來識別N1個主機及其相應分支(步驟305)。在優選實施例中，識別主機包括查找其相關的一個或多個度量滿足諸如最接近此具有多播能力路由器的某一準則的那些主機。
隨後將此消息與第二值N2一起分發給每個識別分支，N2值指定此消息將分發給此分支內的多少主機(步驟307)。這允許接收的具有多播能力路由器對其下行主機執行同一多播處理，這次將值N2用作所希望的消息接收器的數量。
現在將描述一個示例來說明本發明的許多方面。
客戶機可以利用IGMP向最靠近的路由器進行登記。在現有技術的協議(例如，MOSPF)中，在這些多播路由器之間建立生成樹(或任何其他類型的圖形優化樹)。在圖2所示的示例性結構中，R1是根，具有三個分支(R3，R6，R7-R8)。
如上所述，對於子組多播來說，優選執行下面的基本步驟1.計算將要執行子組多播的實體可利用的接收器的總數(如果還未通過例如管理的某一其他方式獲得此信息的話)。
如上所述，本地路由器只從特定多播組的一個成員中接收信息。只要另一成員已報告其成員資格信息，就制止其他成員發送其成員資格信息。解決此問題的兩種方案是a)使每個成員將其成員資格多播給本地路由器以及連接至本地網絡的所有其他主機；或更有效地b)使每個成員將其成員資格單播給本地路由器。本地路由器能夠在IGMP成員資格查詢消息中指示所期望的成員資格報告方法(例如，參見IGMPv3)。
在一個單一或幾個客戶機已向多播路由器登記之後，那個路由器將連接的主機數量通知位於至根多播路由器的路徑上的下一個多播路由器。為了在此機制中考慮相應的度量，不僅發送主機的數量，而且發送這些度量。利用此信息可以擴充這些多播路由器之間的任何已有多播路由選擇消息或IGMP消息。
用於確定分支成員資格信息的程序表示在圖4所示的流程圖中。路由器通過發送成員資格查詢消息給此分支來啟動此程序(步驟401)。為了響應此查詢，路由器從此分支中接收成員資格信息應答(步驟403)。對於此分支來說，此成員資格信息應答識別此分支中的每個具有多播能力路由器的身份。對於每個識別的具有多播能力路由器來說，此成員資格信息應答還包括代表連接至此識別的具有多播能力路由器的主機數量的一個值。選擇地，在本發明的某些實施例中，對於連接至此分支中的每個具有多播能力路由器的每個主機來說，此成員資格信息應答還包括一個或多個相應度量。
在圖2的示例中，利用相應的多播路由器發送下面的附加信息，例如，假定相關的度量是從主機至此路由器的距離(注意非多播路由器透明地轉發此信息)自/至路由器 主機距離R3/R12 1R6/R12 1R8/R71 1R7/R11 2「/」 1 1從接收的所有信息中並考慮這些多播路由器自身之間的距離，R1將生成諸如下面的一個表經由 主機距離直接(通過IGMP) 1 1R2 2 3R4 2 4R7 1 2」 1 3主機的總數7每個多播路由器現在知道其相應分支中接收器的總數以及相關距離。這暗示根(即，此示例性拓撲中的R1)知道接收器的總數。
所收集的有關多播組成員數量的信息能夠用於標註尺寸、統計、記帳等。如下所述，一種應用是將多播消息用作定數一致(QC)同步消息。
主機/伺服器或多播傳送樹的根的請求能夠觸發對每個分支的成員的數量的計算。而且，現有的多播傳送樹建立協議可以利用此信息來擴充。在由主機/伺服器或根觸發時，可以使用遞歸傳送至多播傳送樹的分支的簡單的請求/應答機制。也可以周期性(例如，每隔10分鐘)進行此計算，這是因為多播組成員的數量可能動態改變。
2.計算每個分支的接收器的數量。
參見上面的要點1所生成的表包括從中能夠確定每個分支的接收器的數量及其相關度量的信息。例如，從所生成的樹中能夠看到，兩個主機可通過路由器R7接入一個主機位於「2」的距離上，並且另一個主機位於「3」的距離上(這種情況中的相關度量為「距離」)。
3.只將此信息多播給整個多播接收器組之中的一個子組。
信源將具有有關必須接收此消息的那個分支中的接收器的數量的信息的多播消息(例如，QC同步消息)發送給此多播組。隨後執行遞歸處理，從而每個分支內的多播路由器執行上述相同的步驟，以便在需要時還將此消息只多播給選擇分支中一定數量的主機，以保證正確數量的主機接收此消息。
例如，假定將此消息發送給四個接收器，將出現以下情況R1將接收此消息並在其表中查找距離此多播組「最靠近」的四個接收器。(此處假定度量代表距離，並且主機的選擇是基於哪些主機最靠近發送器；這些條件對於實施本發明都不是至關重要的)。(從此表中的距離確定的)四個最接近主機是直接連接的主機(距離1上的主機H1)、連接至R7的主機(距離2上的主機H7)、以及連接至R3的2個主機(距離3上的主機H 3與H4)或這些主機之一(主機H3或H4的任何一個)和連接至R8的主機(距離3上的主機H8)。為了說明而假定選擇連接至R3的兩個主機，R1將發送出下面的信息給多播路由器至 被通知的主機的數量R2 2R7 1注意此時不確定主機的身份。相反地，此確定是在每個「下行」具有多播能力路由器中遞歸執行此技術的結果。因而，繼續以此為示例，R2(依次)將發送消息給R3，表示將通知兩個主機。
注意不發送消息給R4(因為其主機都不足夠靠近此信息消息的信源)。
接收表示被通知的其本地網絡中的成員的數量的消息的多播路由器為了提供此信息而具有一些選擇-它可以一直在本地網絡上多播此消息，這是因為許多應用並不關心是否有太多成員接收消息，這使此機制簡單。在一些實施例中，通過給多播消息附加指示符來(例如，在諸如標準IP可選標題擴展的可選標題擴展中)通知接收器是否允許它將此消息多播給太多成員(即，多於此子組多播消息中實際指定的數量)，將此指示符僅僅作為一個選擇也許是有益的。
-可選擇地，由於此多播路由器從步驟1所述的解決方案中知道了成員，所以它能夠根據接收的子組多播消息將專用的單播消息只發送給必須通知的一定數量的成員。如果此成員數量小於或等於此消息中所示的數量，則將利用本地網絡中的多播通知所有成員。
-在其他的選擇方案中，此多播路由器自己使用上述子組多播技術，從而允許「下行」具有多播能力路由器確定哪些主機應是接收者。
注意利用定義用於可靠多播協議的確認(來自接收器)獲得可靠性.這適用於上表中的步驟3。
多播是「盡力」多播，這表示消息的發送器不知道成員是否已接收到此消息以及多少成員已接收到此消息。如上所述，可靠多播協議可以提供肯定(ACK)或否定(NACK)的確認。
除了現有的可靠多播機制之外，子組多播還可以如下總計確認本地多播路由器從直接連接的成員中接收確認並將此編譯為確認消息，在朝向根的路徑上將此確認消息發送給下一個多播路由器。此消息表示此分支中(肯定)確認此消息接收的成員的數量。每個多播路由器都這樣做，並且根接收整個網絡(多播傳送樹)的確認的總數。
注意上述機制也適用於共享多播傳送樹，其中許多發送器使用一個多播傳送樹。在這樣的共享樹中，具有幾個根。
從本發明中獲得許多益處。首先，本發明使之有可能將消息只多播給定義集合的成員資格主機之中一個子組的成員資格主機。
與使用RTCP傳送有關對話參與者的信息相比，此機制也能夠在對話開始之前提供此信息。本發明也將有關連接至不同分支的主機的數量的信息提供給不同的多播路由器。此信息隨後還可以用於其他目的。
上述解決方案也提供計算網絡中每個分支的多播組成員的數量的機制。將此信息報告給位於到多播路由選擇樹的根(或基準點)的路徑上的其他多播路由器，在這些多播路由器中此信息能夠用於幾個目的(例如，標註尺寸、統計、記帳、服務分發決定等)。一旦知道多播組成員的總數，就將此信息用於提供更有效的子組多播。信源能夠指定應接收特定多播消息的成員的數量並且此路由選擇機制確保最靠近的主機(或滿足某一其他基於度量準則的主機)接收此消息。最靠近的度量可以是當今特定用於IP的任何度量。
此有效機制的一種示例應用是用於複製伺服器的QuorumConsensus(定數一致)同步。在此，為了滿足對其施加的總容量和延遲要求，在網絡中複製伺服器。客戶機連接任何一個不同的複製品。對於特定的客戶機來說，複製品的選擇可以基於諸如距離、可利用性等的考慮。利用伺服器提供給客戶機的服務是實時交互式服務，諸如多用戶遊戲或虛擬世界。客戶機與此服務(環境)交互作用並從此服務環境中實時接收更新信息。由於此服務的多用戶與實時交互特性，需要伺服器相互保持同步。
此同步能夠有益地採用上述基於度量的子組多播技術。例如，一旦伺服器執行本地更新，它通過將更新通知其他伺服器/複製品來同步這些其他伺服器/複製品。傳統上，將這樣的更新發送給所有的複製品。然而，利用定數一致同步，只需要同步一個子集的複製品(即，此系統只需形成更新一致就可以)。如果知道複製品的總數，就從將被採用的相應機制中知道用於定數一致同步的子集的大小。使用數字作為示例，假定複製品的總數是10並且要同步的子集是6。基於度量的子組多播能夠用於將5個最靠近的複製品與其中已完成初始更新的複製品同步(例如，利用延遲度量來定義「最靠近」)。同一方案能夠用於讀訪問。在那種情況中，使用同一數字作為示例，必須對5個複製品的子集進行讀，以保證至少一個複製品具有最新(即，正確)狀態。
因而，假定總共10個複製品，只需要對至少6個複製品進行寫訪問並且只需要從至少5個複製品中執行讀訪問。基於延遲距離度量的子組多播保證對於寫訪問來說，聯絡最靠近的6個複製品，並且對於讀訪問來說，聯絡最靠近的5個複製品。從此方案中獲得的益處在於利用多播的有效傳輸，並且只聯絡最少數量的複製品，從而有效使用網絡通信資源。
已經結合特定實施例描述了本發明。然而，對於本領域技術人員來說，顯然有可能利用除上述優選實施例之外的特定形式來實施本發明，這可以不脫離本發明的精神來完成。
例如，已經描述了多播路由器可以如何請求有關分支中的成員數量的信息。然而，在可選擇實施例中，也可以由主機或伺服器來進行此請求，這能夠容易地利用查詢/應答機制來完成。
並且，根據其中消息表示將接收此消息的主機的數量的實施例已經描述了本發明。然而，在可選擇的實施例中，此消息反而可以表示將接收此消息的成員的百分比。(例如，此消息可以表示30％的成員將接收此消息)。在這樣的實施例中，根多播路由器隨後能夠將其生成表中的信息(即，表示成員總數的信息)用於將以百分比表示的值映射為實際的成員數量。
因而，這些優選實施例只是示意性的並且不應認為是任何方式的限制。本發明的範疇利用所附的權利要求書給出，而不是利用前面的描述來給定，並且落入權利要求書範圍內的所有變化與等效變換都預定包含在其中。
權利要求
1.在包括一個或多個具有多播能力路由器的通信網絡中從信源中分發消息給一個或多個主機的一種方法，此方法包括在第一具有多播能力路由器中，生成第一表，此第一表識別連接至第一具有多播能力路由器的分支，並且對於每個識別分支來說，此第一表包含它能夠從中確定多少主機是此分支的一部分的成員資格相關信息；在第一具有多播能力路由器中，接收將進行分發的消息和第一值N1，此第一值N1指定此消息將分發給多少主機；在第一具有多播能力路由器中，利用第一表來識別N1個主機及其相應分支；和在第一具有多播能力路由器中，將此消息與第二值N2一起分發給每個識別分支，此第二值N2指定此消息將分發給此分支內的多少主機。
2.根據權利要求1的方法，其中至少一個識別分支包括第二具有多播能力路由器；和此方法還包括在每個第二具有多播能力路由器中，生成第二表，此第二表識別連接至第二具有多播能力路由器的分支，並且對於每個識別分支來說，此第二表包含它從中能夠確定多少主機是此分支的一部分的成員資格相關信息；在第二具有多播能力路由器中，利用第二表來識別N2個主機及其相應分支；和在第二具有多播能力路由器中，將此消息與第三值N3一起分發給每個識別分支，此第三值N3指定此消息將分發給此分支內的多少主機。
3.根據權利要求1的方法，其中對於每個識別分支來說，第一表還包括與每個分支主機相關的第一度量；和對於每個表項目來說，利用第一表識別N1個主機及其相應分支的步驟包括檢查第一度量以確定主機是否滿足被選擇為N1個主機之一的準則。
4.根據權利要求3的方法，其中此表還包括至少一個附加度量；和對於每個表項目來說，利用第一表識別N1個主機及其相應分支的步驟還包括檢查至少一個附加度量以確定主機是否滿足被選擇為N1個主機之一的準則。
5.根據權利要求3的方法，其中每個第一度量指示此分支主機與第二具有多播能力路由器之間的距離。
6.根據權利要求5的方法，其中利用第一表識別N1個主機及其相應分支的步驟包括利用第一表識別N1個最近主機及其相應分支。
7.根據權利要求3的方法，其中每個第一度量指示此分支主機與第二具有多播能力路由器之間的延遲。
8.根據權利要求3的方法，其中每個第一度量指示和此分支主機與第二具有多播能力路由器之間的通信相關的費用。
9.根據權利要求3的方法，其中每個第一度量指示和此分支主機與第二具有多播能力路由器之間的通信相關的帶寬。
10.根據權利要求3的方法，其中每個第一度量指示此分支主機與第二具有多播能力路由器之間的傳輸延遲。
11.根據權利要求10的方法，還包括在第一多播路由器中，確定此第一多播路由器與此分支主機之間的傳輸延遲。
12.根據權利要求3的方法，其中每個第一度量指示此分支主機與第二具有多播能力路由器之間通信的可靠性。
13，根據權利要求1的方法，其中至少一個識別分支包含不具有多播能力的路由器。
14.根據權利要求1的方法，其中生成第一表的步驟包括從第一具有多播能力路由器中發送成員資格查詢消息給連接至第一具有多播能力路由器的每個分支；作為對此成員資格查詢消息的響應，從每個分支中接收一個成員資格信息應答，其中對於此分支來說，每個成員資格信息應答識別此分支中的每個具有多播能力路由器的身份； 和從這些分支中接收的成員資格信息應答中生成第一表。
15.根據權利要求14的方法，其中對於此分支來說，每個成員資格信息應答還識別此分支中的所述每個主機的相應第一度量。
16.根據權利要求14的方法，其中每個分支中的每個具有多播能力路由器通過以下步驟來響應此成員資格查詢消息的接收確定延遲時間；和僅在所述每個分支中的所述每個具有多播能力路由器未檢測到由所述每個分支中不同的具有多播能力路由器發送的成員資格信息應答時，才在此延遲時間過去之後發送成員資格信息應答。
17.根據權利要求1的方法，其中周期性地生成第一表。
18.根據權利要求1的方法，其中至少一個識別分支包括第二具有多播能力路由器；和此方法還包括在每個第二具有多播能力路由器中，將此消息單播給此分支內的一個或多個主機。
19.根據權利要求18的方法，其中從每個第二具有多播能力路由器中，將此消息單播給此分支內的N2個主機。
20.根據權利要求1的方法，其中至少一個識別分支包括第二具有多播能力路由器；和此方法還包括在每個第二具有多播能力路由器中，將此消息多播給此分支內的所有主機。
21.根據權利要求20的方法，還包括在每個第二具有多播能力路由器中，在將此消息多播給此分支內的所有主機之前，首先從此消息中確定是否允許將此消息分發給N2個以上的主機。
22.根據權利要求21的方法，其中是否允許將此消息分發給N2個以上主機的指示包含在此消息的可選標題擴充部分中。
23.在包括一個或多個具有多播能力路由器的通信網絡中從信源中分發消息給一個或多個主機的一種方法，此方法包括在第一具有多播能力路由器中，生成第一表，此第一表識別連接至第一具有多播能力路由器的分支，並且對於每個識別分支來說，此第一表包含它從中能夠確定多少主機是此分支的一部分的成員資格相關的信息；在第一具有多播能力路由器中，接收將進行分發的消息和第一值N1，此第一值N1指定此消息將分發至的所有多播組成員的百分比；在第一具有多播能力路由器中，利用第一表來識別構成所有多播組成員主機的N1百分比的一組主機及其相應分支；和在第一具有多播能力路由器中，將此消息與第二值N2一起分發給每個識別分支，此第二值N2指定此消息將分發給此分支內的多少主機。
24.在數字通信網絡中確定多少主機是連接至路由器的分支的成員的一種方法，此方法包括從此路由器中發送成員資格查詢消息給此分支；和作為對此成員資格查詢消息的響應，從此分支中接收成員資格信息應答，其中對於此分支來說，此成員資格信息應答識別此分支中的每個具有多播能力路由器的身份和表示連接至所述每個具有多播能力路由器的主機的數量的一個值。
25.根據權利要求24的方法，其中此分支中的每個具有多播能力路由器通過以下步驟來響應此成員資格查詢消息的接收；確定延遲時間；和僅在所述每個分支中的所述每個具有多播能力路由器未檢測到由所述每個分支中不同的具有多播能力路由器發送的成員資格信息應答時，才在此延遲時間過去之後發送成員資格信息應答。
26.根據權利要求24的方法，其中對於此分支來說，此成員資格信息還識別連接至此分支中的所述每個具有多播能力路由器的每個所述主機的相應第一度量。
27.根據權利要求26的方法，其中第一度量指示此主機與此具有多播能力路由器之間的距離。
28.根據權利要求24的方法，其中每個分支通過以下步驟來遞歸生成成員資格信息應答將成員資格查詢消息下行傳播給此分支內的每個具有多播能力路由器；並且在從一個具有多播能力路由器上行返回成員資格信息應答給下一個具有多播能力路由器時，更新成員資格信息應答。
29.根據權利要求24的方法，還包括通過以下步驟來生成表示連接至所述每個具有多播能力路由器的主機的數量的值從此分支中的每個成員中將成員資格信息多播給此分支的本地路由器以及連接至本地網絡的所有其他主機。
30.根據權利要求24的方法，還包括通過以下步驟來生成表示連接至所述每個具有多播能力路由器的主機的數量的值從此分支的每個成員中將成員資格信息單播給此分支的本地路由器；和根據從此分支的所述每個成員中接收的成員資格信息，在本地路由器中生成成員資格信息應答。
31.用於在包括一個或多個具有多播能力路由器的通信網絡中從信源中分發消息給一個或多個主機的一種設備，此設備包括在第一具有多播能力路由器中，生成第一表的邏輯，此第一表識別連接至第一具有多播能力路由器的分支，並且對於每個識別分支來說，此第一表包含它從中能夠確定多少主機是此分支的一部分的成員資格相關的信息；在第一具有多播能力路由器中，接收將進行分發的消息和第一值N1的邏輯，此第一值N1指定此消息將分發給多少主機；在第一具有多播能力路由器中，利用第一表識別N1個主機及其相應分支的邏輯；和在第一具有多播能力路由器中，將此消息與第二值N2一起分發給每個識別分支的邏輯，此第二值N2指定此消息將分發給此分支內的多少主機。
32.根據權利要求31的設備，其中至少一個識別分支包含第二具有多播能力路由器；和此設備還包括在每個第二具有多播能力路由器中，生成第二表的邏輯，此第二表識別連接至第二具有多播能力路由器的分支，並且對於每個識別分支來說，此第二表包含它從中能夠確定多少主機是此分支的一部分的成員資格相關的信息；在第二具有多播能力路由器中，利用第二表識別N2個主機及其相應分支的邏輯；和在第二具有多播能力路由器中，將此消息與第三值N3一起分發給每個識別分支的邏輯，此第三值N3指定此消息將分發給此分支內的多少主機。
33.根據權利要求31的設備，其中對於每個識別分支來說，第一表還包含與每個分支主機相關的第一度量；和對於每個表項目來說，利用第一表識別N1個主機及其相應分支的邏輯包含檢查第一度量以確定主機是否滿足被選擇為N1個主機之一的準則的邏輯。
34.根據權利要求33的設備，其中此表還包含至少一個附加度量；和對於每個表項目來說，利用第一表識別N1個主機及其相應分支的邏輯包含檢查第一度量和至少一個附加度量以確定主機是否滿足被選擇為N1個主機之一的準則的邏輯。
35.根據權利要求33的設備，其中每個第一度量指示此分支主機與第二具有多播能力路由器之間的距離。
36.根據權利要求35的設備，其中利用第一表識別N1個主機及其相應分支的邏輯包括利用第一表識別N1個最近主機及其相應分支的邏輯。
37.根據權利要求33的設備，其中每個第一度量指示此分支主機與第二具有多播能力路由器之間的延遲。
38.根據權利要求33的設備，其中每個第一度量指示和此分支主機與第二具有多播能力路由器之間的通信相關的費用。
39.根據權利要求33的設備，其中每個第一度量指示和此分支主機與第二具有多播能力路由器之間的通信相關的帶寬。
40.根據權利要求33的設備，其中每個第一度量指示此分支主機與第二具有多播能力路由器之間的傳輸延遲。
41.根據權利要求40的設備，還包括在第一具有多播能力路由器中用於確定第一多播路由器與此分支主機之間的傳輸延遲的邏輯。
42.根據權利要求33的設備，其中每個第一度量指示此分支主機與第二具有多播能力路由器之間通信的可靠性。
43.根據權利要求31的設備，其中至少一個識別分支包含不具有多播能力的路由器。
44.根據權利要求31的設備，其中生成第一表的邏輯包括用於從第一具有多播能力路由器中發送成員資格查詢消息給連接至第一具有多播能力路由器的每個分支的邏輯；用於從每個分支中接收響應成員資格查詢消息的成員資格信息應答的邏輯，其中對於此分支來說，每個成員資格信息應答識別此分支中的每個具有多播能力路由器的身份；和用於從這些分支中接收的成員資格信息應答中生成第一表的邏輯。
45.根據權利要求44的設備，其中對於此分支來說，每個成員資格信息應答還識別此分支中的所述每個主機的相應第一度量。
46.根據權利要求44的設備，其中每個分支中的每個具有多播能力路由器包含響應成員資格查詢消息的接收的邏輯，所述邏輯包括確定延遲時間的邏輯；和僅在所述每個分支中的所述每個具有多播能力路由器未檢測到由所述每個分支中不同的具有多播能力路由器發送的成員資格信息應答時才在此延遲時間過去之後發送成員資格信息應答的邏輯。
47.根據權利要求31的設備，其中周期性地生成第一表。
48.根據權利要求31的設備，其中至少一個識別分支包含第二具有多播能力路由器；和此設備還包括在每個第二具有多播能力路由器中，將此消息單播給此分支內的一個或多個主機的邏輯。
49.根據權利要求48的設備，其中從每個第二具有多播能力路由器中，將此消息單播給此分支內的N2個主機。
50.根據權利要求31的設備，其中至少一個識別分支包含第二具有多播能力路由器；和此設備還包括在每個第二具有多播能力路由器中，將此消息多播給此分支內的所有主機的邏輯。
51.根據權利要求50的設備，還包括在每個第二具有多播能力路由器中，在將此消息多播給此分支內的所有主機之前首先從此消息中確定是否允許將此消息分發給N2個以上的主機的邏輯。
52.根據權利要求51的設備，其中是否允許將此消息分發給N2個以上的主機的指示被包含在此消息的可選擇標題擴充部分中。
53.用於在包括一個或多個具有多播能力路由器的通信網絡中從信源中分發消息給一個或多個主機的一種設備，此設備包括在第一具有多播能力路由器中，生成第一表的邏輯，此第一表識別連接至第一具有多播能力路由器的分支，並且對於每個識別分支來說，此第一表包含它從中能夠確定多少主機是此分支的一部分的成員資格相關的信息；在第一具有多播能力路由器中，接收將進行分發的消息和第一值N1的邏輯，此第一值N1指定此消息將分發至的所有多播組成員的百分比；在第一具有多播能力路由器中，利用第一表識別一組主機的邏輯，此組主機構成所有多播組成員主機及其相應分支的的N1百分比；和在第一具有多播能力路由器中，將此消息與第二值N2一起分發給每個識別分支的邏輯，此第二值N2指定此消息將分發給此分支內的多少主機。
54.用於在數字通信網絡中確定多少主機是連接至路由器的分支的成員的一種設備，此設備包括用於從此路由器中發送成員資格查詢消息給此分支的邏輯；和用於從此分支中接收響應成員資格查詢消息成員資格信息應答的的邏輯，其中對於此分支來說，此成員資格信息應答識別此分支中的每個具有多播能力路由器的身份和代表連接至所述每個具有多播能力路由器的主機的數量的一個值。
55.根據權利要求54的設備，其中此分支中的每個具有多播能力路由器包含響應成員資格查詢消息的接收的邏輯，所述邏輯包括確定延遲時間的邏輯；和僅在所述每個分支中的所述每個具有多播能力路由器未檢測到由所述每個分支中不同的具有多播能力路由器發送的成員資格信息應答時才在此延遲時間過去之後發送成員資格信息應答的邏輯。
56.根據權利要求54的設備，其中對於此分支來說，此成員資格信息還識別連接至此分支中的所述每個具有多播能力路由器的所述每個主機的相應第一度量。
57.根據權利要求56的設備，其中第一度量指示此主機與此具有多播能力路由器之間的距離。
58.根據權利要求54的設備，其中每個分支包含通過將成員資格查詢消息下行傳播給此分支內的每個具有多播能力路由器來遞歸生成成員資格信息應答的邏輯，並且此邏輯在成員資格信息應答從一個具有多播能力路由器上行返回給下一個具有多播能力路由器時更新成員資格信息應答。
59.根據權利要求54的設備，還包括通過以下步驟生成表示連接至所述每個具有多播能力路由器的主機的數量的值的邏輯從此分支中的每個成員中將成員資格信息多播給此分支的本地路由器以及連接至本地網絡的所有其他主機。
60.根據權利要求54的設備，還包括通過以下步驟生成表示連接至所述每個具有多播能力路由器的主機的數量的值從此分支的每個成員中將成員資格信息單播給此分支的本地路由器；和根據從此分支中的所述每個成員中接收的成員資格信息，在本地路由器中生成成員資格信息應答。
全文摘要
在包括一個或多個具有多播能力路由器的通信網絡中從信源中分發消息給一個或多個主機。為此，第一具有多播能力路由器生成第一表，此第一表識別連接至第一具有多播能力路由器的分支，並且對於每個識別分支來說，此第一表包含它能夠從中確定多少主機是此分支的一部分的成員資格相關信息以及(選擇地)包含與每個分支主機相關的度量。第一具有多播能力路由器隨後接收將進行分發的消息和第一值N1，此第一值指定此消息將分發給多少主機，並且第一具有多播能力路由器利用第一表來識別N1個主機及其相應分支。第一具有多播能力路由器將此消息與第二值一起分發給每個識別分支，此第二值指定此消息將分發給此分支內的多少主機。
文檔編號H04L12/18GK1475063SQ01819006
公開日2004年2月11日 申請日期2001年10月24日 優先權日2000年11月16日
發明者H·哈梅萊爾斯, F·亨德謝德特, H 哈梅萊爾斯, 灤壞綠 申請人:艾利森電話股份有限公司