【文章內(nèi)容簡介】 分發(fā)模型逐步向基于P2P覆蓋網(wǎng)絡(overlay network)架構(gòu)的分布式結(jié)構(gòu)過渡。IP層組播是面向組通信應用的，被認為是大規(guī)模數(shù)據(jù)分發(fā)的最佳方法。然而口組播增加了網(wǎng)絡層的復雜性，而且需要對現(xiàn)有網(wǎng)絡的底層設備進行巨大改動，因此至今口層組播仍然無法廣泛部署。疊加網(wǎng)(Overlay Networks)是一個位于一個或多個己知網(wǎng)絡上的獨立的虛擬網(wǎng)絡。它的主要優(yōu)點在于它的架構(gòu)，它不需要改變底層網(wǎng)絡的結(jié)構(gòu)，可以快速部署所需的網(wǎng)絡功能。如果在疊加網(wǎng)的基礎上實現(xiàn)組播，可以把組播實現(xiàn)提高到應用層。端系統(tǒng)實現(xiàn)組播業(yè)務的思想是將組播作為一種疊加的業(yè)務，實現(xiàn)為應用層的服務，由此構(gòu)成了應用層組播(application layer multicast)應用層組播是在疊加在m層之上的用于實現(xiàn)組播業(yè)務邏輯的功能性網(wǎng)絡，應用層組播網(wǎng)絡中的節(jié)點是由組播中的成員主機構(gòu)成的，并由它們完成數(shù)據(jù)路由、復制和轉(zhuǎn)發(fā)功能。因為不再依靠網(wǎng)絡層路由器來實現(xiàn)，所以不需要任何網(wǎng)絡底層架構(gòu)的改變，只需改變端系統(tǒng)，便于實現(xiàn)和推廣。圖3．1對m組播和應用層組播的數(shù)據(jù)傳輸方式進行了比較：圖3．1 m組播和應用層組播的數(shù)據(jù)傳輸方式比較圖3．1中假設A、B、C、D為四個端系統(tǒng)主機，R1，R2為路由器，箭頭方向代表數(shù)據(jù)包的發(fā)送方向。圖3．1(a)為IP組播，A為網(wǎng)絡中的源節(jié)點，數(shù)據(jù)包從A發(fā)到R1，再由R1轉(zhuǎn)發(fā)給B和R2，R2再將收到的數(shù)據(jù)包轉(zhuǎn)發(fā)給C和D。圖3．1(b)為應用層組播，A發(fā)送兩份相同的數(shù)據(jù)包分別給B和C，再由C復制一份給D。從圖3．1(b)可以看到應用層組播有以下一些優(yōu)點：1．所有數(shù)據(jù)包都是通過單播傳輸?shù)模瑹o需路由器的支持，節(jié)點只需安裝應用層軟件即可，操作方便、易于廣泛部署；，而節(jié)點僅需要保存該組少量其它鄰近成員的信息，可擴展性好；3．利用單播，可以有效地采取適合流媒體應用特點的錯誤恢復、流量控制、擁塞控制等策略，提供端到端的服務質(zhì)量保證；4．不但能跨越空間維，還能跨越時間維進行數(shù)據(jù)傳輸，可犧牲同步性能來獲得更好的服務質(zhì)量保證；5．地址可采用層次結(jié)構(gòu)，可有效地擴大地址空間。但從圖3．1中可以看出應用層組播存在的一些固有問題，如效率不高，多條覆蓋網(wǎng)絡上的邏輯鏈路可能經(jīng)過物理網(wǎng)絡的同一鏈路；延遲大，兩個節(jié)點之間的通訊可能要通過其它節(jié)點：同步性能差，所有節(jié)點之間很難同步接收數(shù)據(jù)；可能跨越多個節(jié)點，丟包概率增大。應用層組播的效率比P組播的效率要低，因為不可避免的會有組播路徑重復的經(jīng)過同一條底層鏈路，也就必然帶來冗余的流量，例如在圖3．1(b)中(A，R1)和(R2，C)這兩條鏈路上有兩個相同的數(shù)據(jù)包重復經(jīng)過同一條底層鏈路，而圖3．1(a)的口組播則只有一次。另外，兩個端系統(tǒng)之間的通信，可能要通過中間其他端系統(tǒng)的轉(zhuǎn)發(fā)來實現(xiàn)，這也不可避免的造成兩個通信節(jié)點之間延時的增加。二 應用層組播路由協(xié)議應用層組播協(xié)議通常都按照兩個拓撲結(jié)構(gòu)組織組成員，一個是控制拓撲，一個是數(shù)據(jù)拓撲，控制拓撲的組成員周期性地交互刷新消息以相互標識身份并從節(jié)點失效中恢復。而數(shù)據(jù)拓撲通常是控制拓撲的子集，它用于標識組播轉(zhuǎn)發(fā)時使用的數(shù)據(jù)路徑。數(shù)據(jù)拓撲作為應用層組播協(xié)議的重要組成部分，即組播中文件數(shù)據(jù)的如何路由是本文討論的重點。一般來說，組播組用于標識組播轉(zhuǎn)發(fā)時用的數(shù)據(jù)路徑通常是一棵組播樹。其中在組播中最基本兩種數(shù)據(jù)轉(zhuǎn)發(fā)方式是：建立最短路徑樹和最小生成樹，常見的路由算法為：Bellman—Ford最短路徑樹算法、Dijstra最短路徑樹算法和Prim最小生成樹算法。最短路徑樹是從源節(jié)點到所有接收節(jié)點的每條路徑上鏈路權值之和最小的組播樹。如果所有的鏈路的權值都表1，則為最小跳樹。如果權值代表鏈路延時，則為最小時延樹。最小生成樹是指覆蓋所有組成員且權值最小的組播樹。此外，還有基于Steiner樹的問題致力于使組播樹的總代價最小，這已經(jīng)證明了是圖論中一個NP．plete問題。如果組播樹包含了樹中所有節(jié)點，Stoner樹問題轉(zhuǎn)化為最小生成樹問題。一般通過啟發(fā)式算法求解，典型的啟發(fā)式算法有：MST、RS、KMB[31，321。Steiner樹問題可以擴展到包括其它的鏈路約束。例如延時、延時抖動或者它們的組合。通常這些問題是NP．Complete的，所以也需要采用啟發(fā)式算法解決。第二節(jié) 基于網(wǎng)絡編碼的應用層組播路由算法在日常生活中，我們經(jīng)常要使用到比較大規(guī)模的通信網(wǎng)絡，我們都希望通信網(wǎng)絡能為我們提供更為安全、快速的網(wǎng)絡服務。于是我們提出了實現(xiàn)在已有通信網(wǎng)絡中達到最大數(shù)據(jù)流的目標。由前一章可知，網(wǎng)絡編碼可以實現(xiàn)網(wǎng)絡的最大流傳輸。網(wǎng)絡信息理論的研究指出：在組播通信中，每個接收節(jié)點可以以網(wǎng)絡拓撲中信源發(fā)送點與信宿接收點之間的最大流容量進行信息傳遞。然而，從信源到不同信宿之間的最大流經(jīng)過的傳輸路徑可能在網(wǎng)絡拓撲的鏈路上形成交叉共享鏈路，因此采用傳統(tǒng)的存儲轉(zhuǎn)發(fā)模式即P組播的方式，無法達到最大流最小割的理論上限。網(wǎng)絡編碼，作為一種協(xié)同工作的理念，將原先分立于物理層和網(wǎng)絡層的兩個核心概念——編碼和路由有機地融為一體，通過在中間節(jié)點中進行傳遞信息的編碼組合運算，建立起一種異于傳統(tǒng)存儲轉(zhuǎn)發(fā)的全新網(wǎng)絡信息傳輸模式。應用層組播是以端系統(tǒng)為基礎的邏輯覆蓋網(wǎng)(overlay network)，不同與以往m層組播中的路由器節(jié)點，端系統(tǒng)可以提供更為強大的功能，如能夠?qū)?shù)據(jù)進行編碼組合運算，這為網(wǎng)絡編碼在覆蓋網(wǎng)絡上的應用提供了技術支撐。本節(jié)的主要內(nèi)容就是建立一種基于網(wǎng)絡編碼的啟發(fā)式應用層組播路由算法，目的在于利用網(wǎng)絡編碼技術在分布式網(wǎng)絡中建立數(shù)據(jù)分發(fā)拓撲使得網(wǎng)絡傳輸容量趨于組播容量上限。在分布式拓撲中運用隨機線性網(wǎng)絡編碼技術，即中間節(jié)點對發(fā)往不同目的節(jié)點的組播數(shù)據(jù)進行編碼組合后再轉(zhuǎn)發(fā)，以避開數(shù)據(jù)流對鏈路的競爭沖突，提高組播通信的吞吐量。一、冗余路徑考慮到網(wǎng)絡編碼在提高網(wǎng)絡的吞吐量方面的優(yōu)點，為了進一步改善應用層組播的性能，從而我們引入了網(wǎng)絡編碼技術。但是網(wǎng)絡編碼不是萬能的，不是所有的網(wǎng)絡組播拓撲都能使用。應用層組播要結(jié)合網(wǎng)絡編碼技術，在路由選擇方面必須滿足兩個條件：(1)網(wǎng)絡中存在冗余的路徑；(2)具有相同目的節(jié)點的路徑之間不能存在共用的路徑。 不相交的冗余路徑(對于Tl而言，S．U1．T1和SU2．U3U4T1分別是S．T1的兩路不相交路徑)圖3．2我們可以看到對于網(wǎng)絡中的目的節(jié)點T1存在兩條不相交的路徑通向源節(jié)點S，因此目的節(jié)點能同時收到多路獨立數(shù)據(jù)流。所謂不相交路徑是指對同～目的節(jié)點而言的不同路徑之間不存在共用的鏈路。不相交性保證了對于發(fā)送至同一個目的節(jié)點的不同路徑的數(shù)據(jù)之間不會存在時間上的競爭，它們之間是線性無關的。此時，對于不同目的節(jié)點的路徑之間必然存在鏈路的公用問題而產(chǎn)生的瓶頸鏈路，網(wǎng)絡編碼的引入可以很好的解決瓶頸鏈路的問題。圖3．2中，鏈路m3，U4)就是目的節(jié)點T1和T2之間的瓶頸鏈路，在節(jié)點U3進行網(wǎng)絡編碼就可以實現(xiàn)網(wǎng)絡的最大流傳輸，達到網(wǎng)絡的最大容量2。(假設定義網(wǎng)絡中鏈路的帶寬均為l，由最大流最小割定理可以算的圖3．2所示網(wǎng)絡結(jié)構(gòu)的最大流為2)。這里，多條不相交的數(shù)據(jù)傳輸路徑的存在使得以往組播進行數(shù)據(jù)通信的組播樹演變成組播圖，即由多棵組播樹的疊加而成。二、一種基于網(wǎng)絡編碼的應用層組播路由算法和分析為了使應用層多播的整體性能盡可能逼近口多播性能，在本節(jié)中，我們設計了一種基于網(wǎng)絡編碼的應用層組播路由算法，它是面向異構(gòu)化接入不同類型客戶機的應用層覆蓋網(wǎng)絡組播路由算法，并且充分考慮因網(wǎng)絡編碼的構(gòu)造采用多路徑方法。本節(jié)提出的算法作為啟發(fā)式算法的一種，適合運用在P2P等分布式網(wǎng)絡中，相對于傳送未編碼原始數(shù)據(jù)塊的傳統(tǒng)分布式內(nèi)容分發(fā)及P2P對等通信，通過在由采集節(jié)點、存儲節(jié)點、客戶機所構(gòu)造的覆蓋網(wǎng)中Peer之間傳輸經(jīng)過網(wǎng)絡編碼的數(shù)據(jù)分組，可以有效提高覆蓋網(wǎng)絡數(shù)據(jù)吞吐能力。這里建立組播拓撲圖是以在源節(jié)點和目的節(jié)點之間建立兩條傳輸路徑為例展開說明，并且兩條路徑在建立過程中分別遵循最大接入帶寬和最小傳輸時延原則。兩條傳輸路徑的組播拓撲圖是按以下步驟完成的：(圖3．3為算法流程圖)步驟1：目的節(jié)點申請加入組