基于虛電路的可靠組播

摘要：提出了一種新的基于虛電路的可靠組播技術(shù)。首先分析了可靠組播的幾個要素，然后介紹了基于虛電路的可靠組播機(jī)制，如資源預(yù)留、間隙整形、優(yōu)先級策略等，最后設(shè)計了基于虛電路的組播模型。該模型結(jié)合多路徑備份方法和特殊的重傳機(jī)制，可以實(shí)現(xiàn)在某條鏈路出現(xiàn)故障的情況下迅速地恢復(fù)正常通信，大大地提高了組播的可靠性。

關(guān)鍵詞：虛電路；可靠組播；資源預(yù)留；間隙整形；多路徑路由

中圖分類號：TP393文獻(xiàn)標(biāo)志碼：A

文章編號：1001－3695(2007)07－0191－04

0引言

組播（也稱多播廣播或多播）技術(shù)是一種允許一臺或多臺主機(jī)（組播源）發(fā)送單一的數(shù)據(jù)包到多臺主機(jī)的（一次的、同時的）網(wǎng)絡(luò)技術(shù)。在實(shí)際中使用組播技術(shù)具有帶寬利用率高、可擴(kuò)展等優(yōu)點(diǎn)，但由于組播使用用戶數(shù)據(jù)包協(xié)議（User Datagram Protocol，UDP），組播報文的傳輸是不可靠的。IP層的組播通信只提供盡力而為的服務(wù)，不能保證組播數(shù)據(jù)報文的可靠性傳輸。

近年來，高效的可靠組播（Reliable Multicast，RM）機(jī)制成為研究的重要方向。目前主要有三類RM組播協(xié)議，即云狀可靠組播協(xié)議、環(huán)狀可靠組播協(xié)議和樹狀可靠組播協(xié)議。①云狀可靠組播協(xié)議直接利用IP組播協(xié)議所建立的組播轉(zhuǎn)發(fā)樹。根據(jù)誰負(fù)責(zé)發(fā)現(xiàn)錯誤的原則這類協(xié)議又可分為：基于ACK（ACKnowledgecharacter）[1，2]的可靠組播協(xié)議和基于NAK（Negative Acknowledgment）的可靠組播協(xié)議[3]。在基于ACK可靠組播協(xié)議中，接收方收到正確的數(shù)據(jù)包后就發(fā)送ACK消息給發(fā)送源，早期如XTP[4]（Xpress Transport Protocol）采用這種方式；在基于NAK的可靠組播協(xié)議中，接收方負(fù)責(zé)核對是否收到數(shù)據(jù)包，如果發(fā)現(xiàn)有丟包，向發(fā)送方發(fā)送NAK消息。SRM[5，6]（Scalable Reliable Multicast）、MFTP[7]（Starburst Multicast File Transfer Protocol）、RAMP[8]（Reliable Adaptive Multicast Protocol）、LBRM[9]（Log－Based Receiver－reliable Multicast）等屬于這類協(xié)議。②環(huán)狀可靠組播協(xié)議利用令牌來保證成功發(fā)送。TRP[10]（Token Ring Protocol）、RMP[11，12]（Reliable Multicast Protocol）等屬于這類協(xié)議。③樹狀可靠組播協(xié)議將所有的節(jié)點(diǎn)組成層次式的樹狀結(jié)構(gòu)，由樹狀頂層向下一層發(fā)送，依此類推，并負(fù)責(zé)確認(rèn)下一層是否收到。TMTP[13]（Tree－based Multicast Protocol）、RMTP[14]（Reliable Multicast Transport Protocol）屬于這類協(xié)議。

上述研究均是在數(shù)據(jù)包結(jié)構(gòu)下進(jìn)行的。本文研究了基于虛電路的可靠組播的方法和機(jī)制，其描述的基于虛電路的可靠組播協(xié)議具有如下特點(diǎn)：結(jié)合資源預(yù)留機(jī)制、間隙整形機(jī)制的虛電路網(wǎng)絡(luò)不會發(fā)生擁塞，不會出現(xiàn)因網(wǎng)絡(luò)擁塞而丟失數(shù)據(jù)包的情況；采用基于NAK的重傳機(jī)制減少發(fā)送端負(fù)擔(dān)；采用多路徑路由機(jī)制和特殊的鏈路恢復(fù)機(jī)制使組播在某條鏈路出現(xiàn)故障的情況下，能夠快速恢復(fù)通信，增強(qiáng)組播的可靠性。

1可靠組播的關(guān)鍵因素

文獻(xiàn)[15]中提出評價可靠組播性能的要素有兩個方面：①數(shù)據(jù)吞吐率，即發(fā)送有用數(shù)據(jù)同冗余數(shù)據(jù)和控制報文的比例；②恢復(fù)的時延，最理想的可靠組播應(yīng)當(dāng)是吞吐率最大，而恢復(fù)的時延最小。



（1）影響數(shù)據(jù)吞吐率的因素

要使吞吐率最大即要使冗余數(shù)據(jù)和控制報文最小。

控制報文主要是接收端向發(fā)送端發(fā)送的反饋信息。如果采用接收端每收到一個數(shù)據(jù)包就向發(fā)送端返回一個ACK的方法控制報文相對較多;如果采用返回NAK的方法一般情況下控制報文極少。因此影響吞吐率的因素取決于冗余數(shù)據(jù)。

冗余數(shù)據(jù)主要指重傳報文。如果采用基于ACK的方法，發(fā)送端比較接收端等待接收的包序號i和自己已發(fā)送的包序號j，如果i

數(shù)據(jù)丟失主要有以下三個原因：

①發(fā)送端負(fù)載太大而造成數(shù)據(jù)包丟失，發(fā)送端需要發(fā)送原始組播數(shù)據(jù)，處理控制報文及重傳數(shù)據(jù)。一般來說，發(fā)送端的原始組播數(shù)據(jù)造成的負(fù)荷是數(shù)據(jù)傳送前設(shè)計者應(yīng)該考慮到的，是發(fā)送者可以承受的負(fù)荷。而一般的設(shè)計都是在發(fā)送端空閑時才會傳送重傳數(shù)據(jù)，重傳數(shù)據(jù)也不會造成發(fā)送端負(fù)載過大。所以在設(shè)計中應(yīng)該考慮如何減少控制報文。

②網(wǎng)絡(luò)擁塞造成數(shù)據(jù)包的丟失，這也是丟失數(shù)據(jù)包的主要原因。在擁塞嚴(yán)重的情況下，重傳數(shù)據(jù)包將會加重?fù)砣瑢?dǎo)致更多的數(shù)據(jù)丟失，同時如果數(shù)據(jù)包大量丟失，容易引起NAK風(fēng)暴。現(xiàn)在出現(xiàn)了一些組播擁塞控制方法，如基于窗口或速率的擁塞控制方法。本文設(shè)計中采用了資源預(yù)留和間隙整形機(jī)制，網(wǎng)絡(luò)基本不會出現(xiàn)擁塞。同時，采用了多路徑方法，重傳數(shù)據(jù)和原始組播數(shù)據(jù)通過不同路徑傳送，所以不會出現(xiàn)重傳數(shù)據(jù)加重網(wǎng)絡(luò)擁塞情況。

③接收端負(fù)載太大也會導(dǎo)致數(shù)據(jù)包的丟失。接收端需要接收數(shù)據(jù)包來判斷是否出現(xiàn)丟失包現(xiàn)象，并向發(fā)送端發(fā)送NAK報文，接收重傳數(shù)據(jù)包。在組播情況下，接收端負(fù)載比發(fā)送端小。在設(shè)計中，筆者采用了資源預(yù)留機(jī)制使得接收端有足夠的能力處理所有事務(wù)。

（2）恢復(fù)時延

可靠組播性能的另一個要素是恢復(fù)時延，即根據(jù)組播通信過程中丟失分組報文的情況來迅速、高效地恢復(fù)丟失的報文，使得接收者接收到正確、有序的報文。在設(shè)計中采用重傳機(jī)制來恢復(fù)丟失的報文，并且結(jié)合虛電路的特性本文介紹了在數(shù)據(jù)鏈路故障時怎樣恢復(fù)通信。

2基于虛電路的可靠組播機(jī)制

（1）資源預(yù)留

為了提高組播可靠性，保證服務(wù)質(zhì)量，在基于虛電路的可靠組播中加入資源預(yù)留機(jī)制。在組播之前，發(fā)送端沿路徑發(fā)送建立組播組。在建立組播組時，發(fā)送端向組播組成員發(fā)送一個包含狀態(tài)信息的建立虛電路消息。其中包含了此次組播需要的帶寬、優(yōu)先級等信息。該消息由沿路徑的路由器逐條傳送，沿路的路由器均被告知準(zhǔn)備預(yù)留資源。接收方收到消息后，如果同意建立虛電路，則向其上游節(jié)點(diǎn)發(fā)送一個確認(rèn)消息。沿途的路由器收到確認(rèn)消息后，看自己是否可以分配資源，如果可以，則修改虛電路表信息，然后將確認(rèn)消息繼續(xù)向上游轉(zhuǎn)發(fā)；如果拒絕，則返回錯誤信息。最后當(dāng)確認(rèn)消息傳回發(fā)送端時，已預(yù)留資源的從發(fā)送端到接收端的虛電路已經(jīng)建立好了。可見在基于虛電路的組播中，建立虛電路時就已經(jīng)對沿路節(jié)點(diǎn)進(jìn)行了資源預(yù)留，并不需要單獨(dú)的過程進(jìn)行資源預(yù)留，這樣提高了系統(tǒng)的效率。

（2）間隙整形

間隙整形主要是通過在隊(duì)列頭使用整形器來對分組進(jìn)行排序，從而減少網(wǎng)絡(luò)擁塞的概率。現(xiàn)在常用的間隙整形速率限制工具有兩種，即漏桶算法和令牌桶算法。漏桶速率限制算法把突發(fā)的分組流轉(zhuǎn)換成常用的空間相等的分組流；令牌桶速率限制算法強(qiáng)制實(shí)現(xiàn)長期平均傳輸速率，同時允許約定的突發(fā)速率。在設(shè)計中從發(fā)送端到接收端的每一個節(jié)點(diǎn)都要對數(shù)據(jù)包進(jìn)行間隙整形，不會存在大量突發(fā)數(shù)據(jù)包的情況，所以本文采用漏桶算法對數(shù)據(jù)包進(jìn)行整形（圖1）。

在基于虛電路的可靠組播中，從發(fā)送端到接收端的每一個節(jié)點(diǎn)均需要對數(shù)據(jù)包進(jìn)行間隙整形。數(shù)據(jù)包的發(fā)送速率由預(yù)留的資源決定，設(shè)預(yù)留的資源為P，包的長度為L，則上游節(jié)點(diǎn)向下游節(jié)點(diǎn)發(fā)送包的間隙時間ΔT為L/P。由于數(shù)據(jù)包在網(wǎng)絡(luò)上的傳輸時間Tp是恒定的，通過間隙整形，下游節(jié)點(diǎn)幾乎是勻速地收到數(shù)據(jù)包，而節(jié)點(diǎn)也為處理數(shù)據(jù)包預(yù)留了足夠的資源。通過上述分析可以看出，結(jié)合資源預(yù)留和間隙整形機(jī)制不會造成網(wǎng)絡(luò)擁塞，從而不會因?yàn)榫W(wǎng)絡(luò)擁塞而丟失數(shù)據(jù)包，增強(qiáng)了組播的可靠性。

(3)基于NAK的重傳機(jī)制

數(shù)據(jù)檢查協(xié)議可分為基于發(fā)送方的可靠組播協(xié)議和基于接收方的可靠組播協(xié)議。在基于發(fā)送方的可靠組播協(xié)議中發(fā)送源在發(fā)送數(shù)據(jù)包時加上序列號，接收節(jié)點(diǎn)收到正確的數(shù)據(jù)包后就發(fā)送ACK消息給發(fā)送源。由于接收節(jié)點(diǎn)比較多，在發(fā)送源附近可能出現(xiàn)大量的ACK消息，會占用大量的網(wǎng)絡(luò)帶寬，也會使發(fā)送源浪費(fèi)資源來處理這些ACK消息。在基于接收方的協(xié)議中，發(fā)送源在發(fā)送數(shù)據(jù)包時加上序列號，接收節(jié)點(diǎn)負(fù)責(zé)核對是否收到數(shù)據(jù)包，如果發(fā)現(xiàn)有丟包，向發(fā)送源發(fā)送NAK消息，發(fā)送源重新發(fā)送丟失的包。文獻(xiàn)[16]分析了采用基于接收方的方法所占用的發(fā)送者開銷最小。因?yàn)樘撾娐肪W(wǎng)絡(luò)結(jié)合了資源預(yù)留和間隙整形機(jī)制，不會發(fā)生網(wǎng)絡(luò)擁塞，所以數(shù)據(jù)丟失率非常小，NAK消息也非常少。采用基于NAK的重傳機(jī)制，既減少了發(fā)送端的負(fù)載，也減少了網(wǎng)絡(luò)負(fù)載。

(4)優(yōu)先級策略

前面已闡述了在建立虛電路的過程中，發(fā)送端向組播組成員發(fā)送的建立虛電路消息包含數(shù)據(jù)的優(yōu)先級等信息。沿途的節(jié)點(diǎn)需要標(biāo)記優(yōu)先級并根據(jù)其優(yōu)先級提供服務(wù)。優(yōu)先級太多會降低中間節(jié)點(diǎn)的性能，太少不能滿足需要。在設(shè)計中有三種優(yōu)先級，即緊急數(shù)據(jù)的優(yōu)先級最高，其次是實(shí)時語音視頻數(shù)據(jù)，文本數(shù)據(jù)和控制數(shù)據(jù)的優(yōu)先級最低。每個節(jié)點(diǎn)在處理數(shù)據(jù)包時先處理優(yōu)先級高的數(shù)據(jù)，再處理優(yōu)先級低的數(shù)據(jù)。這樣的優(yōu)先級策略能保證緊急數(shù)據(jù)能最及時的組播，而流媒體組播最重要的是實(shí)時性，采用這樣的優(yōu)先策略可以保證流媒體組播的實(shí)時性。文本數(shù)據(jù)對實(shí)時性的要求最小，相應(yīng)的優(yōu)先級最低。

(5)多路由機(jī)制

為了增強(qiáng)組播的可靠性，保證在某些鏈路出現(xiàn)故障時接收端仍能正常接收數(shù)據(jù)，采用多路徑路由方法，在組播源和每個接收者間通過兩條路徑建立虛電路。一條路徑是利用單播路由算法（Dijkstra）計算出從源端到接收端的最短路徑；另一條路徑通過Spanning－Join協(xié)議建立。該協(xié)議使新成員采用廣播方式（反向路徑轉(zhuǎn)發(fā)技術(shù)，RPF）發(fā)出join－request報文以尋找樹節(jié)點(diǎn)（on－tree－node）。當(dāng)一個在樹節(jié)點(diǎn)接收到j(luò)oin－request報文時，返回一個應(yīng)答報文ack給新成員。這個由單播路由協(xié)議決定的ack傳輸路徑即為一條候選組播路徑。所以在發(fā)送端和每個接收端之間都有兩條路徑，結(jié)合下文介紹的鏈路恢復(fù)方法可以實(shí)現(xiàn)在鏈路故障時短時間內(nèi)恢復(fù)正常通信。

3基于虛電路的組播模型

(1)建立組播

將用Dijkstra算法建立的組播稱為組播組1，通過Spanning－Join協(xié)議建立的組播稱為組播組2。如圖2，假設(shè)發(fā)送者為A，接收者為B和C，發(fā)送前沿虛線箭頭路徑建立組播組1，沿實(shí)線箭頭路徑建立組播組2。

(2)傳送數(shù)據(jù)

①通過組播樹1傳送的數(shù)據(jù)包。組播組1主要用于傳送原始組播流及NAK，另一個作用是在組播組2出現(xiàn)故障時重傳數(shù)據(jù)。組播組1的建立可以采取兩種方式：第一種方式是在發(fā)送端和接收端間建立雙向虛電路，即組播流與NAK共用一條虛電路；第二種方式是發(fā)送端和接收端間建立正反兩條單向虛電路，每條虛電路都進(jìn)行資源預(yù)留。

②通過組播組2傳送的數(shù)據(jù)包。組播組2主要用于傳送重傳數(shù)據(jù)，并且在組播組1出現(xiàn)故障時傳送NAK和原始組播流。因?yàn)榻M播組2是組播組1的備份路徑，所以將組播組2設(shè)計成與組播組1一致。同樣在發(fā)送端和接收端建立正反兩條虛電路，重傳數(shù)據(jù)及原始組播流通過正向虛電路傳送，NAK通過反向虛電路傳送。預(yù)留帶寬也與組播組1一致。

(4)鏈路恢復(fù)過程

由于結(jié)合資源預(yù)留和間隙整形機(jī)制的虛電路網(wǎng)絡(luò)數(shù)據(jù)丟失率很小，連續(xù)丟失數(shù)據(jù)包的幾率極小，只有在網(wǎng)絡(luò)出現(xiàn)故障時才會出現(xiàn)連續(xù)丟失兩個或兩個以上數(shù)據(jù)包的情況。如果組播組1的網(wǎng)絡(luò)出現(xiàn)故障，會導(dǎo)致連續(xù)兩個或以上NAK丟失；如果組播組2的網(wǎng)絡(luò)出現(xiàn)故障，會導(dǎo)致連續(xù)兩個或以上重傳數(shù)據(jù)包丟失。但對于接收端來講，其并不知道是哪個網(wǎng)絡(luò)出現(xiàn)問題導(dǎo)致它不能正確接收數(shù)據(jù)。分析了所有網(wǎng)絡(luò)故障導(dǎo)致丟包的情況后，采取以下措施：如果接收端發(fā)送四個相同NAKi都未收到重傳數(shù)據(jù)包則通過組播組2發(fā)送NAKi，發(fā)送端接收同一接收端發(fā)出的三個相同NAKi則通過組播組1發(fā)送重傳數(shù)據(jù)包。通過這種方式可以保證組播的可靠性。

通過鏈路恢復(fù)方法可以實(shí)現(xiàn)在鏈路故障時快速地恢復(fù)通信，提高了組播的可靠性。

4結(jié)束語

本文分析了可靠組播性能的要素，結(jié)合虛電路的特性提出了一種全新的基于虛電路的可靠組播模型，并介紹了保證組播可靠性的幾種機(jī)制，詳細(xì)描述了在鏈路故障時的恢復(fù)方法。由于現(xiàn)階段實(shí)驗(yàn)環(huán)境還不成熟，只是在小環(huán)境內(nèi)進(jìn)行測試。在未來的工作中，將加強(qiáng)實(shí)驗(yàn)環(huán)境的建設(shè)，實(shí)現(xiàn)在局域網(wǎng)、廣域網(wǎng)和其他網(wǎng)絡(luò)環(huán)境中對這種組播方法進(jìn)行測試和實(shí)驗(yàn)。

參考文獻(xiàn)：

［1］LI V O K，ZHANG Zaichen.Internet multicast routing and transport control protocols[J].Proceeding of the IEEE，2002，90(3):360－391.

[2]TALPADE R，AMMAR M H.Single connection emulation(SCE):an architecture for providing a reliable multicast transport service:proc. of IEEE International Conference on Distributed Computing Systems[C].Vancouver:[s.n.]，1995.

[3]RAMAKRISHNAN S，JAIN B N.A negative acknowledgement with periodic polling protocol for multicast over LAN:proc. of IEEE INFOCOM’97[C].[S.l.]:[s.n.]，1997.

[4]XTP protocol definition 3.6，protocol engines incorporated，PEI 92－10 Mountain View[R].CA:[s.n.]，1992.

[5]FLOYD S，JACOBSON V，LIU Chinggung，et al.A reliable multicast framework for light－weight sessions and application level framing(SRM):proc.of ACM SIGCOMM’95[C].[S.l.]:[s.n.]，1995:342－356.

[6]FLOYD S，JACOBSON C，LIU C，et al.A reliable multicast framework for light－weight sessions and application level framing[J].IEEE/ACM Transactions on Networking，1997，5(6):784－803.

[7]MILLER C K.Reliable multicast protocols:a practical view[J].Proc. of Local Computer Networks，1997，11:369－378.

[8]BRAUDES R，ZABELE S.RFC－1458 Requirements for multicast protocols(RAMP)[S].[S.l.]:IETF，1993.

[9]HOLBROOK H W.SINGHAL S K，CHERITON D R.Log－based receiver reliable multicast for distributed interactive simulation (LBRM):proc. of ACM SIGCOMM’95[C].New York:ACM Press，1995:328－341.

[10] CHANG J M，MAXEMCHUK N F.Reliable broadcast protocols[J].ACM Transactions on Computer Systems，1984，3(3):251－273.

[11]WHETTEN B，KAPLAN S，MONTGOMERY T.A high performance totally ordered multicast protocol:proc. of INFOCOM[C].[S.l.]:[s.n.]，1995:128－137.

[12]WHETTERN B，MONTGOMERY T，KAPLAN S.A high performance totally ordered multicast protocol，theory and practice in distributed system[M]:Dagstuhl Castle:Springer－Verlag，1994:33－57.

[13]YAVATKAR R，GRIFFIOEN J，SUDAN M.A reliable dissemination protocol for interactive collaborative applications:proc. of ACM Multimedia[C].[S.l.]:[s.n.]，1996.

[14] PAUL S，SABNANI K K，LIN J C，et al.Reliable multicast transport protocol(RMTP)[J].IEEE Journal on Selected Areas in Communications，1997，15(3):407－421.

[15]曹佳，魯士文.組播技術(shù)研究[J].信息技術(shù)快報，2004，2(11):2－7.

[16]WANG Jun，WU Zhimei.Reliable multicast for real－time continuous－media streams over switch Ethernet[J].Journal of Software，2004，15(2):229－237.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”