安 軍

（ 銅仁學院 物理與電子科學系，貴州 銅仁 554300 ）

淺析Internet區(qū)分服務(wù)中組播技術(shù)

安 軍

（ 銅仁學院 物理與電子科學系，貴州 銅仁 554300 ）

本文主要研究Internet 區(qū)分服務(wù)體系提供服務(wù)質(zhì)量保證問題，分析了端到端服務(wù)質(zhì)量體系結(jié)構(gòu)、組播技術(shù)，以及區(qū)分服務(wù)中存在著一些問題，以此，結(jié)合網(wǎng)絡(luò)編碼技術(shù)，本文提了基于網(wǎng)絡(luò)編碼的最大流單源組播路由算法。

QoS； 區(qū)分服務(wù)； 組播； 網(wǎng)絡(luò)編碼

隨著網(wǎng)絡(luò)技術(shù)與多媒體技術(shù)的迅速發(fā)展，人們越來越期望網(wǎng)絡(luò)能提供某種程度的服務(wù)質(zhì)量（Quality of Services，QoS）保證，即為端到端的服務(wù)提供高吞吐量、低延時和低錯誤率等。為了提供QoS保證，人們提出各種方案：改變網(wǎng)絡(luò)流量結(jié)構(gòu)、增加特定流量的互連帶寬或降低其它流量的帶寬、提高特定流量的優(yōu)先級或降低其它流量的優(yōu)先級、依服務(wù)類型進行管理和分配資源、端到端的資源預留、節(jié)點控制、整網(wǎng)或局部網(wǎng)絡(luò)控制、IP組播技術(shù)等等。

其中，組播技術(shù)是單個發(fā)送者對應多個接收者的一種網(wǎng)絡(luò)通信，它通過向多個接收方傳送單信息流方式，可以減少具有多個接收方同時收聽或查看相同資源情況下的網(wǎng)絡(luò)通信流量。IP組播技術(shù)有效地解決了單點發(fā)送多點接收的問題，實現(xiàn)了IP網(wǎng)絡(luò)中點到多點的高效數(shù)據(jù)傳送。在組播網(wǎng)絡(luò)中，即使用戶數(shù)量成倍增長，主干帶寬也不需要隨之增加，同樣的信息不用重復多次復制發(fā)送，大大節(jié)約了網(wǎng)絡(luò)資源、降低了網(wǎng)絡(luò)負載，從而實現(xiàn)網(wǎng)絡(luò)資源的高效利用。更重要的是，它可以利用網(wǎng)絡(luò)的組播特性方便地提供一些新的增值業(yè)務(wù)，滿足用戶的多媒體業(yè)務(wù)需求。

另一方面，Internet工程任務(wù)組（Internet Engineering Task Force，IETF）提出的區(qū)分服務(wù)（differentiated services，DiffServ）模型，具有良好的可擴展性和簡單性，成為最有可能在下一代網(wǎng)絡(luò)（Next Generation Network，NGN）主干中實施的QoS模型。區(qū)分服務(wù)模型的基本思想是在網(wǎng)絡(luò)的入口處為數(shù)據(jù)包標記一個碼點（code point），碼點用于指示數(shù)據(jù)包在網(wǎng)絡(luò)轉(zhuǎn)發(fā)路徑的中間節(jié)點上應該被處理的方式。這樣對每個數(shù)據(jù)包進行的復雜處理被推到了網(wǎng)絡(luò)邊緣，核心網(wǎng)的主要任務(wù)只是根據(jù)數(shù)據(jù)包首部的碼點對其采用相應的轉(zhuǎn)發(fā)措施。

區(qū)分服務(wù)體系結(jié)構(gòu)提供了一種可擴展的QoS解決方案，從直觀上看DiffServ可以滿足用戶對不同服務(wù)質(zhì)量的需求，而組播傳輸則提供了一種節(jié)約網(wǎng)絡(luò)資源的有效方法，二者的集成成為必然趨勢。但是由于傳統(tǒng)的IP組播模型和DiffServ體系結(jié)構(gòu)之間存在著一些基本結(jié)構(gòu)上的沖突，導致二者的集成并不是簡單的疊加就可以完成的。在區(qū)分服務(wù)中實現(xiàn)多播還存在一些問題：如被忽視的預留子樹NRS、異構(gòu)組播組問題、服務(wù)類間的公平性、共享樹的流量監(jiān)控等[1]。

綜上所述，本文以“區(qū)分服務(wù)中組播技術(shù)”為研究主題，主要研究了以下內(nèi)容：（1）區(qū)分服務(wù)中組播技術(shù)分析；（2）網(wǎng)絡(luò)編碼技術(shù)；（3）區(qū)分服務(wù)基于網(wǎng)絡(luò)編碼的最大流單源多播路由。

1．區(qū)分服務(wù)中組播技術(shù)分析

在下一代Internet中，越來越多的應用將會需要網(wǎng)絡(luò)提供一定的服務(wù)質(zhì)量以及進行組播傳輸；因為區(qū)分服務(wù)體系結(jié)構(gòu)提供了一種可擴展的QoS 解決方案，而多播傳輸則提供了一種節(jié)約網(wǎng)絡(luò)資源的有效方法，二者的集成成為必然趨勢。

2．1．區(qū)分服務(wù)中組播技術(shù)

隨著網(wǎng)絡(luò)技術(shù)與多媒體技術(shù)的迅速發(fā)展，涌現(xiàn)了大量的實時多媒體應用，它們對網(wǎng)絡(luò)帶寬的需求量比較大，同時對延時、延時抖動等服務(wù)質(zhì)量也有了嚴格的要求。IETF提出的區(qū)分服務(wù)模型通過合理利用有限的網(wǎng)絡(luò)資源來保證用戶申請的服務(wù)質(zhì)量，并且以其較好的可擴展性成為了最有可能在下一代網(wǎng)絡(luò)主干中實施的QoS模型，采用組播傳輸技術(shù)可以實現(xiàn)網(wǎng)絡(luò)資源的高效利用，因此二者之間的互補結(jié)合便成為一個有效的多媒體應用的QoS解決方案。然而，由于基本結(jié)構(gòu)上的沖突，二者的簡單集成存在著非預留資源子樹（Neglected Reservation Subtree，NRS）、可擴展性、異構(gòu)性、服務(wù)類間的公平性、共享樹的流量監(jiān)控、以及組播路由等問題。

2．2．區(qū)分服務(wù)中組播路由

DiffServ采用聚合的機制將具有相同特性的若干業(yè)務(wù)流聚合起來，為整個聚合流提供服務(wù)，而不再面向單個業(yè)務(wù)流。也就是說在DiffServ網(wǎng)絡(luò)邊界路由器上保持每流狀態(tài)，核心路由器只負責數(shù)據(jù)包的轉(zhuǎn)發(fā)而不保持狀態(tài)信息。區(qū)分服務(wù)實質(zhì)上是在邊界路由器將流量按訂購級別分類，然后由核心路由器進行存儲轉(zhuǎn)發(fā)，其屬于單播問題。隨著多媒體技術(shù)的發(fā)展，會存在越來越多的由單源節(jié)點向多節(jié)點發(fā)送數(shù)據(jù)的需求，即某分組在邊界路由器被標記服務(wù)級別后，在核心域要轉(zhuǎn)發(fā)到多個目的結(jié)點，但由于區(qū)分服務(wù)核心路由器只負責數(shù)據(jù)包的轉(zhuǎn)發(fā)而不保持狀態(tài)信息，因此，區(qū)分服務(wù)中結(jié)合組播技術(shù)為網(wǎng)絡(luò)提供QoS服務(wù)存在兩個方面的問題：尋找組播路由和如何針對不同的服務(wù)需求提供不同的QoS服務(wù)。

2．區(qū)分服務(wù)中基于網(wǎng)絡(luò)編碼的最大流單源組播路由

網(wǎng)絡(luò)編碼是一種能顯著提升組播傳輸性能的通信機制。在組播網(wǎng)絡(luò)中部署和實施網(wǎng)絡(luò)編碼，必須建立傳輸路由和確定編碼模式。對于后者，許多學者提出了有效的解決方法，而對于路由問題的研究則相對較少。由于網(wǎng)絡(luò)編碼自身固有的特點，基于網(wǎng)絡(luò)編碼的組播傳輸與傳統(tǒng)的IP組播在建立傳輸路由的方式上有所不同。但結(jié)合網(wǎng)絡(luò)編碼技術(shù)可以為區(qū)分服務(wù)中結(jié)合組播技術(shù)實現(xiàn)QoS服務(wù)提供解決方案，鑒于此，本文在這里介紹一種區(qū)分服務(wù)中基于最大流的網(wǎng)絡(luò)編碼組播路由算法。

2．1．網(wǎng)絡(luò)編碼技術(shù)

網(wǎng)絡(luò)編碼（Network Coding，NC）是一種融合編碼和路由的信息交換技術(shù)。網(wǎng)絡(luò)編碼是信息傳輸理論研究領(lǐng)域上的最新研究成果，它徹底改變了通信網(wǎng)絡(luò)中信息處理和傳輸?shù)姆绞?。其核心思想是在組播通信中允許節(jié)點對傳輸?shù)男畔⑦M行操作和處理，而不再限于傳統(tǒng)的存儲和轉(zhuǎn)發(fā)。

網(wǎng)絡(luò)編碼在提高網(wǎng)絡(luò)吞吐量、改善負載均衡、減小傳輸延遲、節(jié)省節(jié)點能耗、增強網(wǎng)絡(luò)通用性能等方面均顯示出其優(yōu)越性。在組播網(wǎng)絡(luò)中部署和實現(xiàn)網(wǎng)絡(luò)系統(tǒng)編碼，必須建立傳輸路由和確定編碼模式。[1]在傳統(tǒng)存儲轉(zhuǎn)發(fā)的路由方法基礎(chǔ)上，通過允許對接收的多個數(shù)據(jù)包進行編碼信息融合，增加單次傳輸?shù)男畔⒘?，提高網(wǎng)絡(luò)整體性能。組播網(wǎng)絡(luò)中的某些節(jié)點附加額外的編碼操作能使組播源與組播成員間達到最大流最小割的組播速率。網(wǎng)絡(luò)編碼的工作原理是把不同的信息轉(zhuǎn)化成位數(shù)更小的“痕跡”，然后在目標節(jié)點進行演繹還原，這樣就不必反復傳輸或者復制全部信息了。痕跡可以在多個中間節(jié)點間的多條路徑上反復傳遞，然后再被送往最終的目的端點。它不需要額外的容量和路由，只需把信息的痕跡轉(zhuǎn)換成位流即可。

2．2．單播路由和組播路由

2．2．1．單播路由

單播路由是通過路由器將到網(wǎng)絡(luò)上某一位置的信息從源主機轉(zhuǎn)發(fā)到目的主機的傳輸數(shù)據(jù)過程。然而在路由路徑的選擇過程中，路由算法的選擇和設(shè)計是至關(guān)重要的。在路由選擇方面的算法很多，下面介紹其中比較有代表性的一種。

Dijkstra算法是一種比較經(jīng)典的單播路由算法，下面是它的設(shè)計基本過程：

（1）路由器建立一張網(wǎng)絡(luò)圖，并且確定源節(jié)點和目的節(jié)點，在這個例子里我們設(shè)為V1和V2。然后路由器建立一個矩陣，稱為“鄰接矩陣”。在這個矩陣中，各矩陣元素表示權(quán)值。例如，[i,j]是節(jié)點Vi與Vj之間的鏈路權(quán)值。如果節(jié)點Vi與Vj之間沒有鏈路直接相連，它們的權(quán)值設(shè)為“無窮大”。

（2）路由器為網(wǎng)路中的每一個節(jié)點建立一組狀態(tài)記錄。此記錄包括三個字段：前序字段——表示當前節(jié)點之前的節(jié)點。長度字段——表示從源節(jié)點到當前節(jié)點的權(quán)值之和。標號字段——表示節(jié)點的狀態(tài)。每個節(jié)點都處于一個狀態(tài)模式：“永久”或“暫時”。

（3）路由器初始化（所有節(jié)點的）狀態(tài)記錄集參數(shù)，將它們的長度設(shè)為“無窮大”，標號設(shè)為“暫時”。

（4）路由器設(shè)置一個T節(jié)點。例如，如果設(shè)V1是源T節(jié)點，路由器將V1的標號更改為“永久”。當一個標號更改為“永久”后，它將不再改變。一個T節(jié)點僅僅是一個代理而已。

（5）路由器更新與源T節(jié)點直接相連的所有暫時性節(jié)點的狀態(tài)記錄集。

（6）路由器在所有的暫時性節(jié)點中選擇距離V1的權(quán)值最低的節(jié)點。這個節(jié)點將是新的T節(jié)點。

（7）如果這個節(jié)點不是V2（目的節(jié)點），路由器則返回到步驟5。

（8）如果節(jié)點是V2，路由器則向前回溯，將它的前序節(jié)點從狀態(tài)記錄集中提取出來，如此循環(huán)，直到提取到V1為止。這個節(jié)點列表便是從V1到V2的最佳路由。

2．2．2．組播路由

組播路由就是尋找從源結(jié)點到一組目的節(jié)點的一棵樹，信息沿著此樹傳送到所有的接收者。成組的組播則是尋找一組樹的集合，每一棵樹對應一個節(jié)點的組播路由。通過組播路由，有組播功能的路由器互相交換多播組成員身份信息，以便通過互連網(wǎng)絡(luò)作出智能化組播轉(zhuǎn)發(fā)決定。實現(xiàn)組播通信的最普遍方法是構(gòu)造樹型路由，這是因為樹型路由有以下兩個優(yōu)點：（1）分組以并行方式沿樹枝到達不同的接收者；（2）分組的復制僅在分叉處進行，使得網(wǎng)絡(luò)中所傳送的分組數(shù)最少。

目前在構(gòu)建多播樹的算法中，主要有泛洪（Flooding）、生成樹（Spanning Tree，ST）、最短路徑樹（Shortest Path Tree,SPT）、最小生成樹（Minimum Spanning Tree，MST）、最大帶寬樹（Maximum Bandwidth Tree，MBT）、反向路徑廣播（Reverse Path Broadcasting，RPB）、反向路徑多播（Reverse Path Multicasting，RPM）和核心樹（Core-Based Tree，CBT）等算法。

3．3．基于網(wǎng)絡(luò)編碼的最大流單源組播路由

基于網(wǎng)絡(luò)編碼的最大流單源組播路由采用網(wǎng)絡(luò)編碼技術(shù)實現(xiàn)最大流，以提高網(wǎng)絡(luò)利用效率，其主要是因為單源組播路由問題實際上就是一個發(fā)送端對應多個接收端的數(shù)據(jù)傳輸路徑問題。在參考文獻[3]中指出網(wǎng)絡(luò)編碼能夠?qū)崿F(xiàn)的組播最大流等于信源至各信宿之間的最大流的最小值，即h=minf(S,t)，其中f(S,t)為信源S與信宿t∈T之間的最大流。組播的最大流也稱為組播的理論傳輸容量（Multicast Capacity）。在傳統(tǒng)基于存儲和轉(zhuǎn)發(fā)的IP組播中，組播的理論容量往往是無法實現(xiàn)的。但是如果采用合適的線性網(wǎng)絡(luò)編碼（Linear Network Coding，LNC），總能實現(xiàn)組播的最大流。因此，基于網(wǎng)絡(luò)編碼的最大流單源組播路由采用網(wǎng)絡(luò)編碼技術(shù)實現(xiàn)最大流。

3．3．1．算法思想

基于網(wǎng)絡(luò)編碼的最大流單源組播路由主要設(shè)計目標是在保證網(wǎng)絡(luò)帶寬共享公平性的同時提高資源利用率。其主要設(shè)計思想是：（1）找出基于“最大流網(wǎng)絡(luò)編碼算法”的關(guān)鍵節(jié)點。（2）對區(qū)分服務(wù)中不同QoS需求的服務(wù)分類，在關(guān)鍵節(jié)點處，根據(jù)不同的QoS需求確定是否實施編碼策略。

從網(wǎng)絡(luò)編碼組播的工作原理可以看出，要實現(xiàn)網(wǎng)絡(luò)編碼組播的最大流，必須保證各信宿節(jié)點能夠收到h個編碼信息T，而且這些編碼信息對應的編碼向量應該是線性獨立的，否則信宿節(jié)點無法還原出原始信息。[2]在網(wǎng)絡(luò)編碼組播的傳輸路徑上，存在兩類節(jié)點：（1）包含一個輸入鏈路的節(jié)點，稱為路由節(jié)點（Routing nodes）；（2）包含多個輸入鏈路的節(jié)點，稱為關(guān)鍵節(jié)點（Key nodes）。在尋找出的路徑節(jié)點上，執(zhí)行編碼構(gòu)造算法，如隨機網(wǎng)絡(luò)編碼，便構(gòu)成了實際的網(wǎng)絡(luò)編碼組播通信系統(tǒng)。因為關(guān)鍵節(jié)點是指包含多個輸入鏈路的節(jié)點，所以關(guān)鍵節(jié)點必定是重合鏈路的端節(jié)點，在重合鏈路的端節(jié)點上，如果采用傳統(tǒng)存儲和轉(zhuǎn)發(fā)的路由方法，節(jié)點的多個輸入信息只能順序地發(fā)送，這樣必定會造成信息發(fā)送的延遲，降低組播網(wǎng)絡(luò)的吞吐量或者丟失某些信息。而如果在關(guān)鍵節(jié)點使用網(wǎng)絡(luò)編碼，則可將全部的輸入信息通過線性組合的方式合并，在信宿節(jié)點中通過譯碼操作加以區(qū)分，最終恢復原始的信息，從而實現(xiàn)組播理論容量。

另一方面，在利用網(wǎng)絡(luò)編碼技術(shù)解決網(wǎng)絡(luò)傳輸效率問題中，并不需要在每一個結(jié)點上都要使用網(wǎng)絡(luò)編碼技術(shù)，而只需要定義傳輸路徑上的關(guān)鍵。利用算法找出各路徑上的關(guān)鍵節(jié)點，然后結(jié)合區(qū)分服務(wù)體系組播技術(shù)的實現(xiàn)問題，只在關(guān)鍵節(jié)點處實現(xiàn)網(wǎng)絡(luò)編碼技術(shù)。在已知源節(jié)點和目的節(jié)點間所有可行路徑的前提下，關(guān)鍵是通過計算源和目的間的最短路徑獲得最短路徑通過條數(shù)最多的節(jié)點。顯然這些節(jié)點是發(fā)生局部擁塞和高負載的最可能的地方。為了避免擁塞的情況發(fā)生，就需要控制關(guān)鍵節(jié)點上某一時刻的流量分配，從而減輕關(guān)鍵節(jié)點的壓力。而對于其它的節(jié)點，因為這些節(jié)點僅含有一條輸入鏈路，編碼操作并不能提升網(wǎng)絡(luò)的性能，這類節(jié)點無需執(zhí)行網(wǎng)絡(luò)編碼操作。所以，當且僅當是關(guān)鍵節(jié)點時，才需執(zhí)行網(wǎng)絡(luò)編碼操作。

3．3．2．算法分析與描述

（1）網(wǎng)絡(luò)路徑的初始化。確認在物理上與之相連的路由器并獲得它們的IP地址。將每個路由器視為一個結(jié)點，當一個路由器開始工作后，標記各路由器的工作狀態(tài)。

（2）關(guān)鍵節(jié)點的尋找。參考文獻[4]中給出了尋找關(guān)鍵節(jié)點的方法，即我們可以運用一種基于等位簇的多路徑路由算法KNMRA找出基于“最大流網(wǎng)絡(luò)編碼算法”的關(guān)鍵節(jié)點。

（3）QoS需求的服務(wù)分類。在區(qū)分服務(wù)中根據(jù)不同QoS需求的進行服務(wù)分類，找出一種適合于區(qū)分服務(wù)網(wǎng)絡(luò)的多播路由算法。

（4）使用一個合適的算法，確定網(wǎng)絡(luò)中兩個節(jié)點之間的最佳路由。確定區(qū)分服務(wù)中組播條件下可實現(xiàn)的最終關(guān)鍵節(jié)點。

（5）在最終關(guān)鍵節(jié)點處實現(xiàn)網(wǎng)絡(luò)編碼技術(shù)。

4．結(jié)論

本文在區(qū)分服務(wù)體系結(jié)構(gòu)下，介紹了一種基于網(wǎng)絡(luò)編碼的最大流單源組播路由算法，分析了該方案的特點，然后說明了該方案的基本設(shè)計思想。通過對區(qū)分服務(wù)中不同QoS需求的服務(wù)分類，在關(guān)鍵節(jié)點處，實施不同的編碼策略，根據(jù)不同的QoS需求確定是否實施編碼策略，從而實現(xiàn)了基于網(wǎng)絡(luò)編碼的最大流單源組播路由，最終有效地提高了網(wǎng)絡(luò)數(shù)據(jù)傳輸效率。

[1] 高茜，羅軍舟．區(qū)分服務(wù)網(wǎng)絡(luò)中IP多播:問題與解決方案[J]．計算機研究與發(fā)展，2005，42（5）：823-829．

[2] 劉正藍．QoS研究綜述[D]．浙江大學博士學位論文，2004，2[7]：5-24．

[3] 陶少國，黃佳慶，楊宗凱，程文青，Rami S.Youail．基于最大流的網(wǎng)絡(luò)編碼組組播路由算法[J]．計算機科學，2008，35（6）：107-109．

[4] 郭 磊，汪斌強，陳庶樵．一種面向關(guān)鍵節(jié)點的多路徑路由算法[J]．計算機工程與應用，2008，44（26）：119-121．

[5] 謝希仁．計算機網(wǎng)絡(luò)(第五版)[M]．電子工業(yè)出版社，2007：164-166．

[6] 郭建勇，趙振東，戚銀城，李潔．解決IP 服務(wù)質(zhì)量的綜合方案及其應用[J]．電力系統(tǒng)通信，2004，（6）：35-42．

[7] 王立梅．支持QoS 的組播策略研究[J]．中國科技信息，2008，5：106-108．

[8] 黃程波，周 杰，張 凌．區(qū)分服務(wù)網(wǎng)絡(luò)端到端服務(wù)質(zhì)量保證的組播方案[J]．計算機工程，2006，42，（4）：39-41．

[9] 楊林，鄭剛，胡小惠．網(wǎng)絡(luò)編碼的研究進展[J]．計算機研究與發(fā)展，2008，45（3）：400-407．

[10] 高茜，萬小燕．一種適合于區(qū)分服務(wù)網(wǎng)絡(luò)的多播路由算法[J]．計算機應用，2009，29（2）：507-510．

[11] 朱慧玲，杭大明，馬正新，曹志剛，李安國．Qos路由選擇：問題與解決方法綜述[J]．電子學報，2000，（1）：109-116．

[12] 林闖，單志廣，盛立杰，吳建平．Internet區(qū)分服務(wù)及其幾個熱點問題的研究[J]．計算機學報，2000，23（4）：419-433．

Abstract:In this paper, the author mainly studied that differentiated Internet services quality guarantee systems, and architecture of end to end service quality. Multicast technology and some problems in differentiated services are also analysised. Combined with network coding technology, the largest single-source multicast routing algorithm based on network coding is put forward in this article.

Key words:QOS; differentiated services; multicast; network coding

（責任編輯 王婷婷）

Analysis of Multicast in Differentiated Internet Services

AN Jun
( Department of Physics and Electronic Science, Tongren University, Tongren, Guizhou 554300, China )

TP393.07

A

1673-9639 (2010) 05-0141-04

2010-09-01

安 軍（1974-），男，貴州德江人，銅仁學院物理與電子科學系講師。主要研究：電視視頻制作和計算機網(wǎng)絡(luò)。