基于虛電路的可靠組播

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

關鍵詞：虛電路；可靠組播；資源預留；間隙整形；多路徑路由

中圖分類號：TP393文獻標志碼：A

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

0引言

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

近年來，高效的可靠組播（Reliable Multicast，RM）機制成為研究的重要方向。目前主要有三類RM組播協議，即云狀可靠組播協議、環狀可靠組播協議和樹狀可靠組播協議。①云狀可靠組播協議直接利用IP組播協議所建立的組播轉發樹。根據誰負責發現錯誤的原則這類協議又可分為：基于ACK（ACKnowledgecharacter）[1，2]的可靠組播協議和基于NAK（Negative Acknowledgment）的可靠組播協議[3]。在基于ACK可靠組播協議中，接收方收到正確的數據包后就發送ACK消息給發送源，早期如XTP[4]（Xpress Transport Protocol）采用這種方式；在基于NAK的可靠組播協議中，接收方負責核對是否收到數據包，如果發現有丟包，向發送方發送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）等屬于這類協議。②環狀可靠組播協議利用令牌來保證成功發送。TRP[10]（Token Ring Protocol）、RMP[11，12]（Reliable Multicast Protocol）等屬于這類協議。③樹狀可靠組播協議將所有的節點組成層次式的樹狀結構，由樹狀頂層向下一層發送，依此類推，并負責確認下一層是否收到。TMTP[13]（Tree－based Multicast Protocol）、RMTP[14]（Reliable Multicast Transport Protocol）屬于這類協議。

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

1可靠組播的關鍵因素

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



（1）影響數據吞吐率的因素

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

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

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

數據丟失主要有以下三個原因：

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

②網絡擁塞造成數據包的丟失，這也是丟失數據包的主要原因。在擁塞嚴重的情況下，重傳數據包將會加重擁塞，導致更多的數據丟失，同時如果數據包大量丟失，容易引起NAK風暴。現在出現了一些組播擁塞控制方法，如基于窗口或速率的擁塞控制方法。本文設計中采用了資源預留和間隙整形機制，網絡基本不會出現擁塞。同時，采用了多路徑方法，重傳數據和原始組播數據通過不同路徑傳送，所以不會出現重傳數據加重網絡擁塞情況。

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

（2）恢復時延

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

2基于虛電路的可靠組播機制

（1）資源預留

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

（2）間隙整形

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

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

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

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

(4)優先級策略

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

(5)多路由機制

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

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

(1)建立組播

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

(2)傳送數據

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

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

(4)鏈路恢復過程

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

通過鏈路恢復方法可以實現在鏈路故障時快速地恢復通信，提高了組播的可靠性。

4結束語

本文分析了可靠組播性能的要素，結合虛電路的特性提出了一種全新的基于虛電路的可靠組播模型，并介紹了保證組播可靠性的幾種機制，詳細描述了在鏈路故障時的恢復方法。由于現階段實驗環境還不成熟，只是在小環境內進行測試。在未來的工作中，將加強實驗環境的建設，實現在局域網、廣域網和其他網絡環境中對這種組播方法進行測試和實驗。

參考文獻：

［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]曹佳，魯士文.組播技術研究[J].信息技術快報，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.

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