淺談IP組播路由算法

杭州職業技術學院信息工程學院 吳功才 馮 霞 楊乃如

1 前言

計算機在網絡中傳送IP分組信息主要通過單播、組播、廣播三種方式。近幾年來，隨著網絡及信息共享的普及，網絡組播技術的應用越來越廣泛，不斷賦予了Int er net網絡一些新的應用，如網絡音頻/視頻的廣播或直播、網絡視頻會議、遠程會診、多媒體遠程教育等，本文就淺談一下IP組播路由算法。

2 組播簡介

單播是在發送者和接收者之間實現點對點數據通信的方式；組播指的是同時把數據分組發送給網絡中的一組主機，實現一對多發送分組信息；廣播則實現了向子網內全部的節點廣播數據包。與廣播相比，組播只有相關的路由器和部分主機參與組播信息的發送和接收，而廣播則只能很死板的將分組信息發送到全部的主機（可能部分主機根本不想接收此分組信息）。在組播中，最理想的情況是發送方只需發送每個分組一次，而每條物理鏈路上也最多只有一個分組通過該分組信息。而在單播中要實現一對多發送分組信息的目的，則必須將同一個分組復制多方并多次發送。示意圖如圖1所示。

3 組播路由算法

組播的最終目標是：實現從發送節點到網絡中的一組（而不是全部）接收節點發送分組信息。如圖1所示，在組播應用中，通常發送節點（S）和接收節點（R1、R2）都是確定的。組播路由算法主要功能就是根據網絡拓撲結構以及鏈路狀態，在滿足約束條件的前提下確定發送節點（S）通過哪些中間節點（如：R0、R3等）將分組信息轉發到接收節點（R1、R2）。組播路由算法的最終運算結果為：在網絡拓撲結構中建立一棵組播樹，通過該組播樹發送節點可以沿著樹的分支并行的將分組信息傳送到各接收節點，分組信息只在樹的分支處進行復制，從而使復制的份數盡可能的少。

3.1 靜態算法和動態算法

按照是否允許網絡成員隨時加入或離開組播組，組播路由算法可以分為靜態路由算法和動態路由算法。靜態組播路由算法針對初始的組播組成員構造一棵組播樹，它認為網絡的拓撲和狀態信息是固定不變的，不適應網絡狀態的動態變化。動態組播路由算法則在網絡的狀態發生變化時（成員加入或者離開時），能夠對組播樹的結構進行一定的調整及時的更新組播樹。

3.2 Steiner樹算法和CBT算法

在數據結構的理論中有一個稱作為最小生成樹的數據模型，其定義為：在一給定的無向圖G=(V,E)中，(u,v)代表連接頂點u與頂點v的邊，而w(u,v)代表此邊的權重，若存在T=(V,E1）的無循環圖，其中E1為E的子集，使得的w(T) 最小，則此T為G的最小生成樹。最小生成樹的應用非常廣泛，最典型的應用就是解決如何在n個城市之間鋪設光纜以便可以相互通信，并且鋪設的費用又最節省的問題。

在構造組播路由算法時，一般用組播樹的費用來衡量組播樹的好壞，組播樹的費用是指樹中所有鏈路費用的總和。這里，費用是一個廣義的概念，可以代表鏈路上的時延，鏈路的造價，帶寬等[1]。在組播網絡中，建立一棵以發送節點為根，覆蓋所有接收節點的最小生成樹的問題，在數學上歸結為St einer樹問題。也就是說St einer樹其實就是在在組播網絡中建立的一棵最小生成樹，這棵樹的節點包括組播發送節點、接收節點以及中間的分組轉發節點。實現建立St einer樹的算法有很多，如：KMB算法、MPH算法、ADH算法等。

CBT算法是近年來才提出的一種構造組播樹的新方法，最早于1993年由Bal l ar die提出[2]，其基本思想是選定一個中心作為根，其他的組成員則按照最短路由的原則與此中心相連接，從而構成一棵由所有發送節點共享的樹。

St einer樹算法和CBT算法主要區別：1）St einer樹算法的根節點肯定是發送節點，而CBT算法是選定一個中心作為根。2）St einer樹其實就是一棵最小生成樹，而CBT算法構建的樹則并非一定是最小生成樹。下面兩圖表示的是a為發送節點，b、c、d、e、f、g、h為接收節點構成的組播網絡，圖2為St ei ner樹，圖3為以c節點為中心構建的CBT算法樹。

圖2 Steiner樹

圖3 CBT算法樹

3.3 集中式和分布式算法

按其實現的方式的不同， 組播路由算法還可以分為集中式算法和分布式算法。集中式路由算法是在節點掌握了整個網絡的拓撲結構后，才確定的組播路由。它的缺點是容易導致擁塞，產生延時。而分布式組播路由計算則由發送節點和接收的節點間的網絡節點分布計算組成，不需要所有組成員都知道網絡的拓撲，每個組成員只利用局部信息就可以確定路由。它的優點是算法簡單并且只需部分節點參與路由算法的計算。

3.4 有約束和無約束的算法

按照是否有QoS約束，組播路由算法可以分為無約束和有約束的組播路由算法[3]。無約束組播路由算法通常應用于非實時網絡中，此種網絡對組播分組信息的時延、正確率等均不做特殊的要求。有約束的組播路由算法則通常應用在實時網絡等，對分組信息的時延、分組信息的邏輯順序等有一定的要求。

4 結論

盡管目前組播網絡存在連接成功率、路由優化片面、部署困難等問題，但由于組播技術具有“一次發送，多點傳輸”[4]，同時又具有節省帶寬及分組通信的優點，因此組播技術在計算機網絡有著十分廣泛的應用。相信組播的應用會越來越廣泛，組播路由算法也會有更深入的研究。

[1]田捷.組播路由算法研究[D].武漢理工大學,2004.

[2]王慧.時延受限組播路由算法的研究[D].重慶大學,2014.

[3]鄒德莉.QoS組播路由關鍵算法研究[D].大連理工大學,2006.

[4]葛連升,江林,秦豐林.QoS組播路由算法研究綜述[J].山東大學學報(理學版),2010(01).