淺談IP組播路由算法

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

1 前言

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

2 組播簡介

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

3 組播路由算法

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

3.1 靜態(tài)算法和動態(tài)算法

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

3.2 Steiner樹算法和CBT算法

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

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

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

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

圖2 Steiner樹

圖3 CBT算法樹

3.3 集中式和分布式算法

按其實現(xiàn)的方式的不同， 組播路由算法還可以分為集中式算法和分布式算法。集中式路由算法是在節(jié)點掌握了整個網(wǎng)絡的拓撲結構后，才確定的組播路由。它的缺點是容易導致?lián)砣a(chǎn)生延時。而分布式組播路由計算則由發(fā)送節(jié)點和接收的節(jié)點間的網(wǎng)絡節(jié)點分布計算組成，不需要所有組成員都知道網(wǎng)絡的拓撲，每個組成員只利用局部信息就可以確定路由。它的優(yōu)點是算法簡單并且只需部分節(jié)點參與路由算法的計算。

3.4 有約束和無約束的算法

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

4 結論

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

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

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

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

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