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

1 前言

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

2 組播簡介

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

3 組播路由算法

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

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

按照是否允許網(wǎng)絡(luò)成員隨時(shí)加入或離開組播組，組播路由算法可以分為靜態(tài)路由算法和動(dòng)態(tài)路由算法。靜態(tài)組播路由算法針對初始的組播組成員構(gòu)造一棵組播樹，它認(rèn)為網(wǎng)絡(luò)的拓?fù)浜蜖顟B(tài)信息是固定不變的，不適應(yīng)網(wǎng)絡(luò)狀態(tài)的動(dòng)態(tài)變化。動(dòng)態(tài)組播路由算法則在網(wǎng)絡(luò)的狀態(tài)發(fā)生變化時(shí)（成員加入或者離開時(shí)），能夠?qū)M播樹的結(jié)構(gòu)進(jìn)行一定的調(diào)整及時(shí)的更新組播樹。

3.2 Steiner樹算法和CBT算法

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

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

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

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

圖2 Steiner樹

圖3 CBT算法樹

3.3 集中式和分布式算法

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

3.4 有約束和無約束的算法

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

4 結(jié)論

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

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

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

[3]鄒德莉.QoS組播路由關(guān)鍵算法研究[D].大連理工大學(xué),2006.

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