自組網環境中的組播路由協議

2019-11-04 12:08:02

字體：大中小

來源：轉載

供稿：網友

　　關于組播路由協議的研究是自組網研究中的一個突出問題。本文將說明自組網中組播協議研究所面臨的主要問題，并將簡單介紹和分析當前已提出的一些自組網組播協議。
　　
　　----在典型的自組網環境中，網絡主機通過群組協作來完成一項預定的任務。因此，組播在自組網中扮演了一個重要角色。圖1繪出了自組網中的一個組播數據發送過程。
　　　

　　Internet中的組播協議包括組治理協議IGMP和組播路由協議（DVMRP、MOSPF、PIM等）。IGMP負責本地路由器到直接與它相連的子網的組播分組的發送，并不關心路由器間或跨越中間網絡的組播分組轉發。組播路由協議則完成路由器間和跨網絡的組播分組的轉發任務。
　　
　　----在目前研究較多的單跳的、基于蜂窩模型的無線網絡中，主機到基站只有一跳，相當于在同一子網中，所以不必考慮組播路由的問題，只需實現組治理協議。然而，由于自組網是一種多跳的無線網絡，每個節點都兼有主機和路由器的功能，所以組播路由協議就必不可少。
　　
　　----然而，用于靜態網絡的組播協議（例如，距離矢量組播路由協議(DVMRP）、組播開放最短路徑優先協議（MOSPF）、基于核心樹的組播協議（CBT）和協議無關的組播協議（PIM））在自組網中不能很好地運行，因為在動態的自組網中，分發樹結構輕易被破壞并且必須因連接變化而調整。此外，分發樹通常需要一個全局的路由結構，諸如鏈路狀態或距離矢量。由持續的拓撲結構變化而引發的節點間路由矢量或鏈路狀態表的頻繁交換，產生了額外的信道和處理開銷。鑒于自組網自身的特點，一些針對自組網的組播路由協議相繼提出。下面我們就簡單介紹并比較一種比較有代表性的自組網路由協議。
　　
　　幾種典型組播路由協議
　　----組播路由算法的一種常見的思路是在群組成員之間構造一棵分發樹。組播數據在這顆分發樹上傳播，所有接收者都能收到。在自組網中，這仍是一個基本思路。自組網中還有一些組播算法試圖利用更多的路由信息以獲得更好的可靠性或數據傳送性能。這些路由信息構成了節點之間的網格，所以這些方法稱為基于“網格”的組播路由協議。
　　----AMRoute
　　
　　----MRoute（Adhoc Multicast Routing）是一個基于樹的組播協議。它利用單播通道提供組成員之間的連接，創建一棵雙向的共享分發樹。AMRoute 協議分為兩個過程。第一個過程為構造網格。第二個過程為在網格基礎上形成共享分發樹。兩個過程可以同時進行。
　　
　　----【第一個過程】開始時，網格是由一個個獨立的網段組成，每個網段由一個組成員承擔核心的角色。每個核心利用擴展環搜索法周期性地擴散JOIN REQ分組來發現其他網段上的本組成員。當A成員節點收到來自B的JOINREQ分組時，A用JOINACK分組回答并將B作為同組鄰居節點。B收到JOINACK分組后，也將A作為它的同組鄰居。其中A和B還將采用分布式的核心選舉算法決策誰將保留核心地位。這個不同網段的合并過程不斷進行，最終將形成一個網格，網格上的每個節點對應于一個群組成員節點，有一個邏輯核心負責成員信息和網格結構。
　　
　　----【第二個過程】核心周期性地傳送 TREECREATE分組給本組鄰居用以建立共享樹，其中每個TREECREATE分組可以被唯一標識。當A成員節點收到一個非重復的來自B的TREECREATE分組后，它將其轉發到所有其他網格鏈路上。假如收到了來自C的重復的TREECREATE分組，將沿接收鏈路返回一個TREECREATENAK分組。C收到TREECREATENAK分組后，將標記 C→A的鏈路為網格鏈路而不是樹鏈路。想離開組的節點向鄰居發送JOINNAK，退出所在的網格，并不再轉發任何組播數據分組。如圖2所示。
　　　

　　AMRoute的要害特征是它利用虛擬網格鏈路建立組播樹。因此，當網絡拓撲結構改變時只要樹成員之間通過網格鏈路的路徑仍然存在，樹就不需要作調整。非成員不轉發數據分組并且不需要支持任何組播協議。這樣，僅僅樹上的成員節點引入了處理和存儲開銷。這個開銷主要是：每個節點需要周期性地“廣播”JOINREQ 分組，核心需要周期性地“廣播”TREECREATE分組，以及“廣播”分組傳播和中間節點處理“廣播”分組所需的開銷。這里的“廣播”是指組成員節點通過底層的單目標分組傳輸實現在虛擬網格上廣播的過程。AMRoute依靠于底層的單播協議維護組成員節點之間的連接，任何單播協議都可應用。協議主要的缺點是它存在暫時性的回路并且當節點移動時樹結構得不到優化。
　　
　　----ODMRP
　　
　　----按需組播路由協議（ODMRP，On-Demand Multicast Routing PRotocol）使用基于網格的方法。它創建一個節點的網格，組播分組在該網格中擴散，以提供路徑冗余性。ODMRP的一個基本思想是通過按需的方式獲得路徑信息。
　　
　　----與按需的單播路由協議相似，協議由請求階段和回答階段組成。當源節點有組播數據發送，但沒有路徑或成員信息時，它們擴散一個JOIN-DATA 分組。當一個節點收到一個非重復的JOIN-DATA，它保存上游節點ID并再廣播該分組。假如這個節點同時是組播接收者，它就構造一個JOIN-TABLE，并廣播給鄰居。
　　
　　----JOIN-TABLE包含了該節點到各個源節點的反向路徑的下一跳節點的ID。當鄰居節點收到這個JOIN-TABLE時，假如它的ID和JOIN-TABLE中的某個下一跳節點的ID匹配，該節點將意識到它是在到源節點的路徑上，因此是轉發群組的一部分。然后它構造并廣播自己的JOIN-TABLE。這樣，JOIN-TABLE就被每一個轉發群組成員轉播直到它通過最短路徑到達組播源節點。這個過程構造或更新了從源節點到接收節點的路徑并且建立了一個節點的網格，即轉發群組。組播發送者通過周期性發送JOIN-DATA 來刷新成員關系信息并更新路由信息。
　　
　　----當傳送組播數據時，假如當前節點是轉發節點并且收到的分組是不重復的，節點將轉發這些數據。由于所有的轉發節點都中繼數據，當主路徑由于節點的移動而失效時，冗余路徑有助于數據的遞交。另一個ODMRP的獨特屬性是它的單播能力。ODMRP不僅能和任何單播路由協議并存，還能有效地起到一種單播路由協議的作用。這樣，配置了ODMRP的網絡就不再需要一個獨立的單播協議了。
　　
　　----在擁有GPS（全球定位系統）的網絡環境中，ODMRP 還能利用運動猜測來適應節點的移動。通過利用GPS所支持的位置和運動信息，ODMRP 可以估算路徑的過期時間，接受者可以選擇有效時間最長的路徑作回答。使用運動猜測的方法，源節點可以在預計路徑失效時重新選擇路徑。這樣，在節點移動方面，協議會更有彈性。
　　
　　----AMRIS
　　
　　----利用遞增序號的自組網路由協議（AMRIS，Ad hoc Muticast Routing protocol utilizing Increasing idnumberS）是一個基于共享分發樹的組播路由協議。網絡中的每個節點分配一個組播會話成員ID號（msm-id），該ID號的大小將用于指導組播數據的流向。
　　
　　----開始時，一個被稱為會話節點（Sid）的特定節點根據群組會話需要廣播一個NEWsession分組。通過廣播該分組，建立一個從會話節點向外輻射狀msm-id遞增的分層邏輯結構，該結構類似于網格的概念。具體過程如下：NEW- SESSION分組包含會話節點的msm-id，鄰居節點收到該分組后，就計算它們自己的msm-id，取值要大于分組中指定的那個。然后，節點將分組中的msm-id用它們自己的替換后繼續轉發NEW-SESSION分組。
　　
　　----一個節點可以通過發送JOINREQ來加入一個組播會話，并因此形成一個新的或加入一個已存在的共享分發樹。具體過程如下：節點A在具有比自己更小的msm-id的潛在父親節點列表中選擇一個節點，比如節點B，并向其發送一個單目標JOIN-REQ分組。B接收到JOIN-REQ后，假如它已經加入了該組播會話，就送回一個 JOIN-ACK分組。否則，它發送一個JOIN-REQ.PASSIVE給它的潛在父親。假如A接收 JOIN-ACK失敗或在發送了JOIN-REQ之后收到一個JOIN-NAK，它就執行“枝葉重構” （ Branch ReconstrUCtion，BR）過程。BR過程的作用就是在共享分發樹發生變化的時候局部地動態修復分發樹。它采用擴展環搜索算法使得本節點成功地加入已有的共享分發樹，從而加入組播會話。
　　
　　----每個群組節點需要周期性地廣播信標消息（beacon）給它的鄰居。信標消息包含節點id、msm-id、成員關系狀態、登記的父親和孩子的id以及它們的msm-id。AMRIS協議通過信標機制監測鏈路失效。假如在一個給定的時間間隔內沒有接收到鄰居節點發送的信標，節點就認為鄰居已經移出了通信范圍。假如先前的鄰居是一個父親節點，該節點必須給一個新的潛在父親節點發送JOINREQ以重新加入會話中。假如此節點加入任務失敗或沒有合格的鄰居存在，它將執行“枝葉重構”（ Branch Reconstruction， BR）過程。
　　
　　----數據轉發通過樹中的節點完成。每個節點只對來自登記的父親或孩子節點的組播數據分組才進行轉發。假如樹鏈路損壞，分組將丟失直到樹被重新構造為止。像ODMRP一樣，AMRIS也不需要獨立的單播路由協議。
　　
　　----CAMP
　　
　　----借助核心的網格協議（CAMP，CoreAssisted Mesh Protocol）通過創建一個共享的網格結構支持組播，它需要底層單播路由協議的支持。CAMP 將網絡中的節點分為雙工成員、單工成員和非成員。雙工成員是組播網格的完全成員，既發送又接收；而單工成員緊緊向其他群組成員發送組播數據；非成員不參與組播數據的傳送。
　　
　　----CAMP的基本思想是設置若干“核心”節點，普通節點通過向“核心”發送JOINREQUEST來加入群組。這樣能夠起到限制JOINREQUEST 分組的流量的作用。然后，接收節點再根據單播路由信息來優化。
　　
　　----具體地說，CAMP包括網格創建和維護兩個階段。一個想加入組播網格的節點首先判定它是否有已經是網格成員的鄰居。假如有，此節點通過一個 CAMPUPDATE聲明其成為一個成員。否則，此節點或者發送一個JOINREQUEST給一個群組“核心”，或者嘗試通過擴展環搜索的方法找到一個成員節點。任何雙工成員都可以用一個JOIN-ACK響應。
　　
　　----接收節點周期性地審查它的分組緩存區，判定作為接收分組來源的鄰居節點是否是在到源節點的反向最短路徑上。假如不是，此節點將沿反向最短路徑給源節點發送一個HEARTBEAT或PUSHJOIN消息。這個過程保證了網格包含從所有接受者到所有發送者的反向最短路徑。CAMP依靠于底層的單播路由協議，并要求單播路由協議能夠在有限的時間內給出到所有目的節點的正確距離。基于BellmanFord算法的路由協議不能用于CAMP。CAMP也需要作一定的擴展才能用于按需的單播路由協議。
　　
　　幾種協議的比較
　　----下表總結了這幾種組播路由協議的要害特征。
　　

　　AMRoute
　　
　　----在簡單性和發送節點個數的可擴展性方面給出了一定的承諾。然而，單向鏈路的存在妨礙了可靠的數據遞交。當移動性更強的時候這個問題就更嚴重。AMRoute的其他缺點是存在回路、樹的效率較差。針對AMRoute的可能的改進是在選擇樹枝時考慮可達性信息。使用這種方法，單向鏈路的影響就會減小。另外，給協議增加一點可適應性（例如，周期性發送TREECREATE）可建立更優化的樹。最重要的是，必須應用一種防止回路的機制來提高AMRoute的效率。
　　
　　----ODMRP
　　
　　----通過構造網格提供冗余路徑，從而增強了協議對節點移動的可靠性。當網絡高度移動時，協議不產生額外開銷，因為沒有因鏈路斷開而引發任何控制分組。然而，當存在大量組播發送節點時，協議可能會承受過多的控制開銷。對大群組的可擴展性必須增強。
　　
　　----AMRIS
　　
　　----AMRIS的性能對移動性和網絡負載很敏感。性能較差的主要原因是控制分組的數量和信標的大小。信標分組將會引起一些分組碰撞，在更密集的網絡中，性能會變得更差。我們認為使用類似于CAMP的信標機制會改進AMRIS的性能。假如只有當一個給定期間內沒有分組傳輸時才發送信標，節點信息仍然能夠傳遞給鄰居節點，同時信標傳送的數量就能減少。另外Sid的選擇會影響樹的外形并且可能影響它的性能。關于Sid選擇算法的研究將有助于改進AMRIS。
　　
　　----CAMP
　　
　　----當群組增大時具有良好的控制分組數量的可擴展性。因為JOINREQUEST當到達一個網格成員時就停止擴散，所以當節點數量和群組成員數增加時，CAMP不會引起組播更新分組的指數增長。然而，當節點移動時，在網絡收斂性和控制分組數量增長等方面的表現上，它是依靠于單播路由協議的。
　　
　　----研究表明，基于網格的協議在移動場景中的性能明顯比基于分發樹的協議要好。在基于分發樹的協議中，當路徑由于節點移動而失效時，分組必須被緩存或丟棄直到樹被重建。另一方面，面對節點移動和鏈路斷開，網格中的冗余路徑為數據遞交提供了可選擇的路徑。當主路徑正在重構時，數據分組仍然能到達目的節點。

上一篇：常用路由協議的分析及比較

下一篇：ISP如何在網內部署BGP路由協議