網(wǎng)絡(luò)演算的矩陣解釋

1、網(wǎng)絡(luò)演算的矩陣解釋A Matrix Interpretation of Network Calculus 樊葆華，竇 強(qiáng)，張鶴穎FAN Bao-hua, DOU Qiang, ZHANG He-ying（國防科技大學(xué) 計算機(jī)學(xué)院 長沙 410073）(School of Computer Science, National University of Defense Technology, 410073, ChangSha, China)摘要：網(wǎng)絡(luò)演算是離散事件動態(tài)系統(tǒng)理論在計算機(jī)網(wǎng)絡(luò)中的應(yīng)用，網(wǎng)絡(luò)演算通過到達(dá)曲線和服務(wù)曲線計算網(wǎng)絡(luò)的性能參數(shù)，這兩個概念封裝了復(fù)雜的理論背景，從而易于在實際中應(yīng)

2、用，但對到達(dá)曲線和服務(wù)曲線概念的理論研究比較缺乏。本文采用冪等矩陣的角度描述到達(dá)曲線和服務(wù)曲線，演算的過程成為矩陣運算，通過結(jié)合矩陣雙子理論和余理論的研究結(jié)果，得出了由矩陣表演算的基本定理。研究表明，冪等矩陣?yán)碚摓榫W(wǎng)絡(luò)演算提供了很好的理論解釋。本文還提出一種基于變換矩陣的方法求某些網(wǎng)絡(luò)元素的服務(wù)曲線。Abstract: Network calculus is the application of Discrete Event Dynamic System theory in computer networks. Network calculus uses arrival curve and s

3、ervice curve to calculate performance parameters. The definition of arrival curve and service curve encapsulates complex theoretical background, so it is more compatible in practice. Unfortunately there is a lack of theoretical study on arrival and service curve. We regard arrival curve and service

4、curve as idempotent matrices, and the calculation process can be represented by matrix operations. By corresponding results in idempotent matrix theory and residuation theory, we obtain the basic theorem of matrix network calculus. Our research proves that idempotent matrix theory give network calcu

5、lus a good theoretic interpretation. 關(guān)鍵詞：離散事件動態(tài)系統(tǒng); 網(wǎng)絡(luò)演算; 到達(dá)矩陣; 服務(wù)矩陣; 冪等矩陣; 余理論Key words: Discrete Event Dynamic System; Network calculus; Arrival matrix; Service matrix; Idempotent matrix; Residuation Theory中圖分類號：TP323 文獻(xiàn)標(biāo)識碼：A1引言離散事件動態(tài)系統(tǒng)DEDS(Discrete Event Dynamic System)理論可以應(yīng)用于計算機(jī)網(wǎng)絡(luò)建模分析，這一領(lǐng)域有兩個研究方向

6、：一是直接將DEDS理論應(yīng)用于計算機(jī)網(wǎng)絡(luò)，如文獻(xiàn)1 3 ，這一方向偏重理論分析，對系統(tǒng)的穩(wěn)定性、因果性以及周期性等性質(zhì)有較為深入的研究；另一個方向是針對計算機(jī)網(wǎng)絡(luò)的特點對DEDS理論進(jìn)行簡化，采用到達(dá)曲線和服務(wù)曲線等概念對網(wǎng)絡(luò)進(jìn)行分析，降低了計算和分析復(fù)雜度，增強(qiáng)了理論的實用性，這種方法被稱為網(wǎng)絡(luò)演算(Network Calculus)6 。R. L. Cruz于1991年首次提出網(wǎng)絡(luò)演算的概念1 ，隨著研究的深入，網(wǎng)絡(luò)演算與DEDS以及其它理論的關(guān)系得到重視。Boudec6 將服務(wù)曲線看作是服務(wù)器的沖激響應(yīng)；Chang7 8 9 采用極小代數(shù)動態(tài)濾波器(Dynamic Filter)模型對計

7、算機(jī)網(wǎng)絡(luò)進(jìn)行分析；Chang4 還采用矩陣方法分析了多輸出輸出流時的服務(wù)器性能。許多新的理論方法也被引入了網(wǎng)絡(luò)演算的研究：Fidler10 提出了基于勒讓德(Legendre)變換的共軛(Conjugate)網(wǎng)絡(luò)演算，在這一理論中極小卷積(Min-plus Convolution)可以被看成勒讓德變換下的加法，從而降低了計算復(fù)雜度。Jiang11 提出了一種基于模糊邏輯(Fuzzy Logic)的方法。國內(nèi)學(xué)術(shù)界也重視網(wǎng)絡(luò)演算的研究，張信明等采用網(wǎng)絡(luò)演算分析某些特殊的網(wǎng)絡(luò)元素，如無緩沖區(qū)整形器，GPS服務(wù)器等16 17 18 。高文宇等發(fā)表了對網(wǎng)絡(luò)演算的綜述性文獻(xiàn)21 。張連明等采用網(wǎng)絡(luò)演算的

8、理論對網(wǎng)絡(luò)中的某些特殊流如自相似流等進(jìn)行了分析20 。國內(nèi)對離散事件動態(tài)系統(tǒng)理論的研究達(dá)到國際先進(jìn)水平，清華大學(xué)的鄭大中等對DEDS進(jìn)行了系統(tǒng)研究13 ，蔡研等更是直接將DEDS理論運用于網(wǎng)絡(luò)分析14 。但作為DEDS在計算機(jī)網(wǎng)絡(luò)中的典型應(yīng)用的網(wǎng)絡(luò)演算，國內(nèi)研究大多集中在實際應(yīng)用，理論研究相對缺乏。根據(jù)以上文獻(xiàn)的研究內(nèi)容，可知網(wǎng)絡(luò)演算與DEDS理論有深刻聯(lián)系。DEDS是一種冪等(Idempotent)的線性系統(tǒng)理論，主要采用矩陣進(jìn)行分析， 特征值、沖激響應(yīng)矩陣、Cayley-Hamilton定理等矩陣論的經(jīng)典結(jié)果都在DEDS理論研究中發(fā)揮了重要作用。因此如果能將整個網(wǎng)絡(luò)演算采用矩陣來解釋，將有

9、助于對這一理論的深入研究并進(jìn)一步得到新的結(jié)論。本文是對網(wǎng)絡(luò)演算的理論研究，直接采用矩陣來描述到達(dá)曲線和服務(wù)曲線，得到到達(dá)矩陣與服務(wù)矩陣的概念，從而將網(wǎng)絡(luò)演算與DEDS理論以及冪等矩陣?yán)碚摼o密聯(lián)系。研究表明到達(dá)矩陣和服務(wù)矩陣是比到達(dá)曲線和服務(wù)曲線更為深刻的概念?；诘竭_(dá)矩陣和服務(wù)矩陣，采用余理論(Residuation Theory)可以得矩陣演算的基本定理，這一基本定理比網(wǎng)絡(luò)演算中的定理更具一般性，更能反映網(wǎng)絡(luò)的本質(zhì)，矩陣網(wǎng)絡(luò)演算的主要結(jié)論可以根據(jù)基本定理得出。從形式上看，本文的工作與文獻(xiàn)4 相似，但實際上兩者是完全不同的研究，不同之處主要表現(xiàn)在如下幾個方面：(1) 本文采用冪等數(shù)學(xué)(Idem

10、potent mathematics)以及余理論研究到達(dá)矩陣和服務(wù)矩陣的性質(zhì)，得出了矩陣演算的基本定理。而文獻(xiàn)4 中直接對矩陣進(jìn)行推理；(2) 本文是對單入單出(SISO)服務(wù)器的進(jìn)一步深入研究，文獻(xiàn)4 是用矩陣方法將一般的網(wǎng)絡(luò)演算擴(kuò)展到多入多出(MIMO)的情形。 可以說本文是對網(wǎng)絡(luò)演算在深度上的擴(kuò)展，而文獻(xiàn)4 是對網(wǎng)絡(luò)演算在廣度上的擴(kuò)展；(3) 本文對網(wǎng)絡(luò)中數(shù)據(jù)流的生成矩陣進(jìn)行了分類，定義了一階以及二階生成矩陣，結(jié)合到達(dá)矩陣與服務(wù)矩陣的性質(zhì)可以對矩陣演算進(jìn)行分類，文獻(xiàn)4 中矩陣的意義與本文完全不同。本文其余部分結(jié)構(gòu)如下：第2節(jié)介紹相關(guān)理論基礎(chǔ)，包括冪等數(shù)學(xué)、雙子、余理論和確定性網(wǎng)絡(luò)演算；第

11、3節(jié)研究廣義增矩陣以及定義在其上的雙子結(jié)構(gòu)，采用余理論研究了矩陣乘法及其余運算的性質(zhì)；第4節(jié)研究到達(dá)曲線與服務(wù)曲線的矩陣表示，定義了到達(dá)矩陣和服務(wù)矩陣，得出了矩陣演算的基本定理；第5節(jié)提出一種采用變換矩陣求服務(wù)矩陣的方法；第6節(jié)研究矩陣演算的應(yīng)用，得出了一種保證流量服務(wù)器以及令牌桶的服務(wù)矩陣和服務(wù)曲線；最后一節(jié)總結(jié)全文的工作并提出下一步的研究計劃。2 相關(guān)工作2.1 冪等數(shù)學(xué)冪等是指對于某個代數(shù)結(jié)構(gòu)中的加法，性質(zhì)成立12 。在計算機(jī)網(wǎng)絡(luò)分析中，如果采用冪等的加法， 則可將網(wǎng)絡(luò)近似看作冪等線性系統(tǒng)，網(wǎng)絡(luò)演算也可看作是基于冪等數(shù)學(xué)的一種確定性排隊理論。冪等數(shù)學(xué)中最重要的代數(shù)結(jié)構(gòu)是雙子(Dioid)

12、：在集合上定義運算和，這兩種運算都滿足結(jié)合律并且分別有中立元和，可交換并且是冪等的，對滿足分配率，對 運算吸收，此時稱為雙子。下面列舉幾個常用的雙子：(1) 極小代數(shù)：;(2) 考慮所有定義在的非負(fù)廣義增函數(shù)(即非減函數(shù))的集合， 在其中定義運算：(a);(b)；(c) .則構(gòu)成一個可交換雙子。雙子中可以根據(jù)加法定義一種序關(guān)系：，定義 當(dāng)且僅當(dāng)。稱為引起的序，在極小代數(shù)中的序關(guān)系就是通常的。 在雙子理論中，半連續(xù)(Semi-continuous)映射占有重要地位。上半連續(xù)(Upper-semi-continuous)映射是指在兩個雙子間的某個映射，對的任意子集 ： 將上面定義中的改為，便得到下

13、半連續(xù)映射(Lower-semi-continuous)的概念。2.2 余理論余理論是雙子的主要分析工具之一2 5 ，其主要研究對象是余映射和對偶余映射。定義 1.(余映射2 ) 是從有序集的保序映射，如果對所有，子集存在最大元，則稱是余映射(Residuated Mapping)，該最大元記作，映射稱作的余(Residual)。 如果對所有, 子集存在最小元，則是對偶余映射(Dual-residuated Mapping)，該最小元記作，映射稱為的對偶余(Dual-residual)。余映射在實際應(yīng)用中較為常見，例如映射既是余映射也是對偶余映射。文獻(xiàn)2 證明，雙子到之間的映射是余映射的充要條

14、件為其將中最大元映射為中最大元并且是下半連續(xù)映射。雙子到之間的映射是對偶余映射的充要條件為其將中最小元映射為中最小元并且是上半連續(xù)映射。余映射和對偶余映射主要有以下性質(zhì)：定理 1. (余映射的性質(zhì)2 ) 為從完全雙子到完全雙子上的映射，如下性質(zhì)成立：(1) ,，(2) ,；(3) ；(4) ;(5) ；(6) ，；(7) ，。其中，分別為上的恒等映射。容易證明，對任意，映射，是對偶余映射，其對偶余為:， 因此可以用余理論分析極小卷積的性質(zhì)。冪等數(shù)學(xué)一個重要結(jié)論是Bellman定理，敘述如下：定理 2. (Bellman定理12 ) 令為雙子，設(shè), 則對的最小解為。2.3 網(wǎng)絡(luò)演算本小節(jié)根據(jù)文獻(xiàn)

15、6 簡單的介紹網(wǎng)絡(luò)演算，假設(shè)服務(wù)器是工作保持(Work-conserving)的，采用FIFO排隊規(guī)則。流(Flow)用其流量累積函數(shù)(Cumulative Traffic Function)表示，如果是某個服務(wù)器的輸入流，則示到時刻為止該流到達(dá)服務(wù) 器的總流量。 總是用代表某個服務(wù)器輸入流， 代表相應(yīng)的輸出流，其各自的流量累積函數(shù)分別記作，顯然，。定義 2. (到達(dá)曲線)設(shè)，對于一個累積函數(shù)為 的流，如果對所有，則稱是流 的到達(dá)曲線。定義 3. (服務(wù)曲線)假設(shè)網(wǎng)絡(luò)元素，其輸入和輸出流量累積函數(shù)分別為。稱提供服務(wù)曲線，當(dāng)且僅當(dāng)以下條件同時成立：(1) ，；(2) 。根據(jù)到達(dá)曲線與服務(wù)曲線可以

16、計算網(wǎng)絡(luò)性能參數(shù)的確界。定理 3.(確定性網(wǎng)絡(luò)演算基本定理6 ) 經(jīng)過網(wǎng)絡(luò)元素的流有到達(dá)曲線，提供服務(wù)曲線，則：(1) 在時刻, 的最大積壓滿足： ； (2) 在時刻所有到達(dá)分組經(jīng)歷的最大延遲滿足： (3) 有到達(dá)曲線。3 冪等矩陣研究離散時間系統(tǒng)中，函數(shù)可以寫成向量形式，由廣義增函數(shù)得到的向量稱為廣義增向量。基于廣義增向量的概念，可以定義廣義增矩陣：定義 4. (廣義增矩陣) 廣義增矩陣是指每一行從左到右，每一列從下到上都是廣義增向量的矩陣。本文用加黑的大寫字母表示矩陣，如，當(dāng)時，用表示維矩陣位于第行第列的元素。設(shè)為整數(shù)，表示所有的廣義增矩陣集合。對定義如下運算：設(shè)，(1) ；(2) 。構(gòu)成

17、了完全雙子，稱為矩陣雙子(Matrix Dioid)。零元為所有元素為的矩陣，單位元為對角線及對角線以下元素為,其余元素為的矩陣。其中分別代表極小代數(shù)雙子中的單位元與零元。矩陣雙子中的序關(guān)系定義為當(dāng)且僅當(dāng) 。矩陣的閉包運算定義為： 其中，。設(shè)，定義的映射： 在矩陣雙子中，乘法不一定是可交換順序的，所以以上定義的稱作右乘映射。 還可定義左乘映射，本文僅研究右乘映射。可以證明是上半連續(xù)映射，證明可參考文獻(xiàn)6 ：定理 4. 設(shè)，則 是從 的上半連續(xù)映射。由映射的上半連續(xù)性，可得如下重要定理：定理 5. 是對偶余映射，其對偶余為，其中。 證明：因為，所以不等式的解集不空，設(shè)為，根據(jù)上半連續(xù)性，。于是的

18、最小解存在。其次證明是不等式的解： 最后證明如果是不等式的解，則 ，設(shè)，即 于是 根據(jù)定理 5，不難結(jié)合定理 1得出矩陣乘法及其余運算的如下性質(zhì)推論 1.(矩陣雙子的性質(zhì)) 設(shè)，則：(1) ；(2) ;(2) ；(3) ；(4) 。4 網(wǎng)絡(luò)演算的矩陣解釋本節(jié)給出給出矩陣網(wǎng)絡(luò)演算的基本結(jié)論。首先定義到達(dá)矩陣和服務(wù)矩陣，然后根據(jù)這兩個概念得出矩陣演算的基本定理。4.1到達(dá)矩陣和服務(wù)矩陣上一節(jié)研究了廣義增矩陣雙子的性質(zhì)，在網(wǎng)絡(luò)分析中，經(jīng)常遇到由某個數(shù)據(jù)流生成的矩陣，設(shè)為某個流的流量累積函數(shù)，對固定的，根據(jù)可得到如下兩個矩陣，對所有：(1);(2).稱為流在時刻的一階生成矩陣；稱為流在時刻的二階生成矩

19、陣或自相關(guān)矩陣。 顯然如果是廣義增函數(shù)，則都是廣義增矩陣。 定義為某個時刻，中所有函數(shù)的時不變生成矩陣集合，為相應(yīng)的時變生成矩陣的集合。容易證明對固定的，與都是雙子，并且前者的乘法是可交換的，后者的乘法是不可交換的，后文在不至引起混淆的前提下省略下標(biāo)。仿照網(wǎng)絡(luò)演算中的定義公式，可以給出如下到達(dá)矩陣和服務(wù)矩陣的定義：定義 5. (矩陣的到達(dá)矩陣) 對于矩陣，如果存在矩陣使得，則稱為的到達(dá)矩陣。以上定義中的可以為時變或時不變的矩陣。根據(jù)這一定義，到達(dá)矩陣也可寫作。即矩陣是的一個上界，或者說限制了矩陣在意義上的“差分”行為。到達(dá)矩陣與冪等矩陣論中的特征值問題有很大聯(lián)系，根據(jù)可得： 為映射的一個特征矩

20、陣，其特征值為。以上定義的到達(dá)矩陣是脫離網(wǎng)絡(luò)中數(shù)據(jù)流定義的一個抽象概念，在實際的在網(wǎng)絡(luò)演算中，要將到達(dá)矩陣的概念與流的概念結(jié)合來定義流的到達(dá)矩陣，因為每個流可以有兩種生成矩陣，所以對一個數(shù)據(jù)流可以定義兩種到達(dá)矩陣：定義 6. (數(shù)據(jù)流的到達(dá)矩陣) 設(shè)為網(wǎng)絡(luò)中某個流的流量累積函數(shù)，在某個時刻，的一階生成矩陣有到達(dá)矩陣，則稱在時刻流有一階到達(dá)矩陣；如果流 在時刻的二階生成矩陣有到達(dá)矩陣，則流在時刻有二階到達(dá)矩陣。流的到達(dá)矩陣描述了該流的差分行為的上界?？梢宰C明，當(dāng)?shù)竭_(dá)矩陣是時不變矩陣時，(即時只與有關(guān))，一階到達(dá)矩陣和二階到達(dá)矩陣是等價的：定理 6. 設(shè)，并且是時不變矩陣，為某個流的累積函數(shù)，為流

21、的一階生成矩陣，為流的二階生成矩陣 ，則下面兩個命題等價：(1)；(2)。證明：根據(jù)到達(dá)矩陣定義：，。 如果是一階生成矩陣，則：。 如果是二階生成矩陣，則有： 顯然兩種定義是等價的。 從定理 6的證明過程可以看出，如果到達(dá)矩陣是時變矩陣，則一階和二階到達(dá)矩陣定義不一定 等價，一階到達(dá)矩陣的定義包含了二階到達(dá)矩陣的定義，如下推論所述，證明簡單故略去。推論 2. 設(shè)，并且是時變矩陣，為某個流的累積函數(shù)，為流的一階生成矩陣，為流的二階生成矩陣則 可以用到達(dá)矩陣的觀點看待時不變網(wǎng)絡(luò)演算中的到達(dá)曲線定義，解釋如下：如果流有到達(dá)曲線，則在任意時刻，根據(jù)到達(dá)曲線定義可得： 從而有，其中是由時不變到達(dá)曲線生成

22、的一階矩陣。在矩陣雙子中可以定義服務(wù)矩陣的概念，和到達(dá)矩陣的不同之處在于服務(wù)矩陣不能脫離網(wǎng)絡(luò)元素而單獨給出抽象的定義。和到達(dá)矩陣一樣，服務(wù)矩陣也存在一階和二階的區(qū)分：定義 7.(服務(wù)矩陣) 網(wǎng)絡(luò)元素的輸入流為，輸出流為，在時刻，設(shè)為的一階生成矩陣，分別為的二階生成矩陣。(1) 如果存在矩陣，使成立，則稱在時刻提供一階服務(wù)矩陣。(2) 如果存在矩陣，使成立，則稱在時刻提供二階服務(wù)矩陣。一階服務(wù)矩陣描述了服務(wù)器的服務(wù)能力，對輸出流的特征進(jìn)行了描述，而二階服務(wù)矩陣則對輸出流的差分特征進(jìn)行了描述。對于服務(wù)矩陣，不管其是時變或時不變矩陣，一階服務(wù)矩陣與二階服務(wù)矩陣定義都不等價。以下對服務(wù)矩陣的意義進(jìn)行討

23、論，以一階服務(wù)矩陣為例：設(shè)提供一階服務(wù)矩陣，如果可以被近似看作一個一階線性系統(tǒng)，則對任意輸入，存在唯一的一階線性響應(yīng)矩陣。于是對某個輸入的一階生成矩陣，可得： 其中為輸出流的一階生成矩陣，于是： 顯然時上面等式成立。如果，等式變成，根據(jù)線性響應(yīng)矩陣的唯一性，可以得，又因為這一結(jié)論對所有階生成矩陣都成立，所以最后有，即一階線性響應(yīng)矩陣是最小的一階服務(wù)矩陣。對二階服務(wù)矩陣可得到相同結(jié)論，即 ?？梢愿鶕?jù)到達(dá)矩陣和服務(wù)矩陣是時變或是時不變矩陣將網(wǎng)絡(luò)演算分為時變和時不變網(wǎng)絡(luò)演算；而根據(jù)到達(dá)矩陣和服務(wù)矩陣定義中 流的生成矩陣的階數(shù)，又可以將網(wǎng)絡(luò)演算分為一階網(wǎng)絡(luò)演算和二階網(wǎng)絡(luò)演算；因此總共可以組合成如表1所

24、示的四種矩陣演算。 網(wǎng)絡(luò)演算分類 輸入輸出矩陣服務(wù)矩陣 相關(guān)文獻(xiàn)一階時不變一階時不變6 一階時變一階時變9 二階時不變二階時不變本文二階時變二階時變本文表1: 網(wǎng)絡(luò)演算的分類一般來說，時變網(wǎng)絡(luò)演算用于描述服務(wù)器的動態(tài)行為，而二階網(wǎng)絡(luò)演算則用于描述服務(wù)器輸出流的差分行為。以往文獻(xiàn)并未仔細(xì)區(qū)分這一區(qū)別，本文首次對其中的區(qū)別進(jìn)行了研究。 這種分類法也可用于非矩陣的網(wǎng)絡(luò)演算，如文獻(xiàn)6 7 中的網(wǎng)絡(luò)演算可以認(rèn)為是屬于一階時不變網(wǎng)絡(luò)演算，而文獻(xiàn)9 中的網(wǎng)絡(luò)演算則屬于一階時變網(wǎng)絡(luò)演算，二階演算尚屬于待研究的領(lǐng)域，下一節(jié)的研究表明這四種矩陣演算可以用統(tǒng)一的方法分析。4.2矩陣演算

25、的基本定理四種網(wǎng)絡(luò)演算都可以用冪等矩陣?yán)碚摲治觯紫茸C明如下重要引理：引理 1. 設(shè)，則。證明：根據(jù)推論 1可得，兩邊右乘得到，于是。 根據(jù)引理1，可以得到在矩陣演算的基本定理：定理 7. (矩陣演算基本定理) 一階(二階)到達(dá)矩陣為的流經(jīng)過一個提供一階(二階)服務(wù)矩陣的服務(wù)器, 輸入和輸出的一階(二階)生成矩陣分別為和，則 。證明：根據(jù)到達(dá)矩陣與服務(wù)矩陣定義可得： 根據(jù)矩陣乘法的單調(diào)性以及引理1： 。 以上基本輸入輸出關(guān)系式之所以叫基本定理是因為這一定理對任何一種矩陣網(wǎng)絡(luò)演算都成立，無論是一階還是二階演算，也無論是時變還是時不變演算。網(wǎng)絡(luò)演算的主要結(jié)論都可以根據(jù)這一定理得出，以一階時不變網(wǎng)絡(luò)

26、演算為例：(1) 在一階時不變網(wǎng)絡(luò)演算中，有，于是 從而，即有到達(dá)矩陣。(2) 根據(jù), 可得 ，這意味著 ； 并且恰為最大積壓的表達(dá)式。對二階演算可以進(jìn)行相似的討論?？梢宰C明對二階網(wǎng)絡(luò)演算，以上討論的(1)仍然成立：推論 3. 二階到達(dá)矩陣為的流經(jīng)過一個提供二階服務(wù)矩陣的服務(wù)器, 輸入和輸出的二階生成矩陣分別為和，則輸出流有二階到達(dá)矩陣。證明：注意到如下等式成立：，即，根據(jù)可得 。 以下定理給出了串聯(lián)網(wǎng)絡(luò)元素提供的服務(wù)矩陣：定理 8.(串聯(lián)) 設(shè)網(wǎng)絡(luò)元素在時刻的一階(二階)服務(wù)矩陣為，則由串連組成的系統(tǒng) 提供的一階(二階)服務(wù)矩陣為。證明：根據(jù)矩陣乘法的單調(diào)性容易證明結(jié)論。 5 基于變換矩陣求

27、服務(wù)曲線可以采用矩陣方法來求某些網(wǎng)絡(luò)元素的服務(wù)曲線，即先求得一階服務(wù)矩陣，再將其寫成函數(shù)形式。 定義如下一組矩陣為傳輸矩陣： : 其中 定義為： 對于， 通過將最右邊一列移走而在左邊增加一列零向量得到，例如: 網(wǎng)絡(luò)演算中一般假設(shè) 。因此定義如下初始條件矩陣， 。其中為元素全為 的列向量，而為元素全為的列向量。 可被用作雙子中的變換矩陣。 例如考慮遞歸式，初始條件為，矩陣為函數(shù)的一階生成矩陣，原式可以寫成 ，根據(jù)Bellman定理這個方程的解為 。 可以用于解中的不等式。如不等式, 這個不等式可以寫成等式，矩陣形式為， 這個方程的解為。本文假設(shè)對于階遞歸式，其初始條件為, 所以矩陣 的前列為向量

28、, 對于不同的初始條件，要對 的前列作相應(yīng)修改。采用矩陣 作為變換矩陣的一個原因是這個矩陣的閉包比較容易計算，如下定理所述 ：定理 9. (1) 矩陣 的閉包為：(2) 證明：根據(jù)圖論知識, 代表生成圖中2個節(jié)點 之間的最短距離，可以證明如下性質(zhì)：(1)如果 ，則；(2)如果 ，則。性質(zhì)(1)明顯成立，下面給出性質(zhì)(2)的簡單證明： 對 , 只能取 或 ， 如果 ， 則存在 之間的一條路徑，記為，并且每個。但根據(jù) 的定義可知如果 , 則對所有 ， , 于是 。根據(jù)性質(zhì)(1)和性質(zhì)(2)可得。以求 的閉包為例。畫出矩陣 的生成圖(precedence graph)(圖1)，可得到結(jié)論。:圖 1

29、: 矩陣 的生成圖 可通過 得到. 對于的情況，可以采用相同的方法。于是根據(jù)定理 9，的解為；的解為，即 。6 矩陣網(wǎng)絡(luò)演算的若干應(yīng)用在這一節(jié)，我們用兩個例子解釋矩陣方法在網(wǎng)絡(luò)分析中的應(yīng)用。6.1 保證流量服務(wù)器保證速率(Guaranteed Rate)服務(wù)器是一種常見的服務(wù)器模型，文獻(xiàn)6 采用網(wǎng)絡(luò)演算分析了該服務(wù)器的性能。但GR服務(wù)器本質(zhì)上是基于極大代數(shù)定義的，本節(jié)定義一種與GR服務(wù)器對偶(Dual)的服務(wù)器模型，采用極小代數(shù)定義，稱之為保證流量服務(wù)器(Guaranteed Traffic)服務(wù)器，然后采用矩陣方法求其服務(wù)矩陣進(jìn)一步得到其服務(wù)曲線：定義 8. (保證流量服務(wù)器) 設(shè)某個服務(wù)器

30、，輸入輸出累計函數(shù)分別為, 為服務(wù)速率，定義序列如下： 如果服務(wù)器保證在任何時刻 , , 則稱 為保證流量服務(wù)器。和GR服務(wù)器不同，GT服務(wù)器對服務(wù)器輸出的流量作出了保證. 我們使用矩陣方法可以得到GT服務(wù)器的服務(wù)曲線，并進(jìn)而研究其輸入輸出特性，將等式 寫成矩陣形式: 為對應(yīng)的一階生成矩陣，這個方程的解為, 設(shè)的生成矩陣為，則 可以寫成 ，得到GT服務(wù)器的服務(wù)矩陣為 。于是GT服務(wù)器的服務(wù)曲線為 。6.2令牌桶的服務(wù)矩陣矩陣方法不僅可以應(yīng)用于極小代數(shù)演算，也可用于極大代數(shù)演算，和極小代數(shù)演算相似，極大代數(shù)下也可定義到達(dá)矩陣和服務(wù)矩陣，不同之處在于極大代數(shù)下的加法定義為。在極大代數(shù)演算中，輸入輸

31、出分別表示第個分組到達(dá)與離開服務(wù)器的時間。下面用矩陣方法求一個桶高為，令牌產(chǎn)生速率為的離散令牌桶在極大代數(shù)下的整形矩陣。 假設(shè)表示時刻第個被接受(即未丟棄)的令牌產(chǎn)生的時刻，如果要第個到達(dá)的分組離開令牌桶，需要同時滿足如下兩個條件，令表示每產(chǎn)生一個令牌所需時間：(1)令牌桶接受了一個新令牌，因為已經(jīng)用掉了個被接受的令牌，從而該時刻為；(2)第個分組已經(jīng)到達(dá)，該時刻為。于是得到 ，改用極大代數(shù)的符號： 初始條件為，和第一個GT服務(wù)器例子不同的是本例得到一個方程組，令 ，為相應(yīng)的一階生成矩陣，可得 對方程組中第一個方程，依次左乘矩陣可以得到 將方程由下而上的迭代，可以得出： 而由矩陣與其有向圖之間

32、的關(guān)系可知，所以，結(jié)合圖論方法可得： 從而： 因此得到在極大代數(shù)網(wǎng)絡(luò)演算下，令牌桶的極大整形曲線為 通過這個例子可以看出，矩陣演算的一個好處是可以將許多矩陣論中的工具和方法用于計算機(jī)網(wǎng)絡(luò)分析。7 總結(jié)本文采用冪等矩陣?yán)碚搶W(wǎng)絡(luò)演算中到達(dá)曲線和服務(wù)曲線等概念進(jìn)行了解釋，并對網(wǎng)絡(luò)演算進(jìn)行了分類，得出了矩陣演算的基本定理，分析的主要工具是余理論與冪等矩陣?yán)碚摗?采用矩陣分析網(wǎng)絡(luò)演算的工作有以下幾個優(yōu)點：(1) 矩陣形式更易于理解，在矩陣演算中，極小卷積變成了較為常見的矩陣乘法并且可以采用研究結(jié)果較為成熟的冪等矩陣?yán)碚撨M(jìn)一步研究網(wǎng)絡(luò)演算；(2) 矩陣演算為網(wǎng)絡(luò)演算與DEDS理論、網(wǎng)絡(luò)演算與圖論之間架起

33、一座橋梁；(3) 不管是時變還是時不變網(wǎng)絡(luò)演算，都可以用統(tǒng)一的矩陣形式來表達(dá)，矩陣演算的基本定理都成立。下一步研究可在如下兩個方面展開：(1) 矩陣與隨機(jī)網(wǎng)絡(luò)演算的結(jié)合，采用矩陣解釋隨機(jī)網(wǎng)絡(luò)演算；(2) 冪等矩陣?yán)碚撓嚓P(guān)結(jié)果在網(wǎng)絡(luò)演算中的進(jìn)一步應(yīng)用。例如文獻(xiàn)2 中的映射理論以及矩陣的最小實現(xiàn)問題等。致謝感謝挪威科技大學(xué)的Jiang Yuming教授對本文提出了若干中肯的意見；感謝審稿人的辛勤工作。參考文獻(xiàn): 1 R. L. Cruz. A calculus for network delay, part i: Network elements in isolation. IEEE Transa

34、ctions on Information Theory, 1991, 36(2):114131.2 F. Baccelli, G. Cohen, et al. Synchronization and Linearity, an algebra for discrete event systems. West Sussex, Great Britain: John Wiley and Sons, 1992.3 F. Baccelli, D. Hong. Tcp is max-plus linear: and what it tells us on its throughput./In Proc

35、eedings of ACM SIGCOMM, August 2000.4 C. S. Chang. Matrix extensions of the filtering theory for deterministic traffic regulation and service guarantees. IEEE Journal Selected Areas in Communications, 1998, 16:708718. 5 T. S. Blyth and M. F. Janovitz. Residuation Theory. Pergamon Press, United Kingd

36、om, 1972.6 J. Y. L. Boudec, P. Thiran. Network calculus: a theory of deterministic queuing system for the Internet. LNCS 2050, Online Version, 2004.7 C. S. Chang. On deterministic traffic regulation and service guarantees: a systematic approach by filtering. Transactions on Information Theory, 1998,

37、 44(3):10961107.8 C. S. Chang. Performance Guarantees in Communication Networks. Springer, TNCS, 2000.9 C. S. Chang, R. L. Cruz, et al. A (min, +) system theory for constrained traffic regulation and dynamic service guarantees. IEEE/ACM Transactions on Networking, 2002, 10(6):805817.10 M. Fidler, S.

38、 Recker. Conjugate network calculus: A dual approach applying the Legendre transform. Computer Networks, 2006, 50(8):10261039.11 X. Jiang. New perspectives on network calculus. ACM SIGMETRICS Performance Evaluation Review, 2008, 37(1):9597.12 G. L. Litvinov, V. P. Maslov, G. B. Shpiz. Idempotent fun

39、ctional analysis: An algebraic approach. Mathematical Notes, 2001, 69(5-6):696729. 13 Zheng Dazhong, Zhao Qianchuan. Discrete Event Dynamic System. Beijing: Tsinghua University Press, 2000.(鄭大鐘, 趙千川. 離散事件動態(tài)系統(tǒng). 北京：清華大學(xué)出版社. 2000.)14 Caiyan, Zhao Qianchuan. The Analysis of TCP Protocol Based on Max-Plu

40、s. Chinese Journal of Computer, 2002, 25(11):1133-1143.(蔡研, 趙千川. 基于極大代數(shù)的TCP協(xié)議分析. 計算機(jī)學(xué)報, 2002, 25(11):1133-1143.)15 Chen Wende, Qi Xiangdong. Discrete event dynamic system: a max-plus approach. Beijin: Science Press, 1994.(In Chinese)(陳文德, 齊向東. 離散事件動態(tài)系統(tǒng)：極大代數(shù)方法. 科學(xué)出版社, 北京, 1994.)16 Zhang Xinming, Chen

41、g Guoliang, et al. A traffic shaping framework based on network calculus. Journal of Software, 2002, 13(12): 2225-2230.(張信明, 陳國良, 等. 基于網(wǎng)絡(luò)演算的流量整形模型. 軟件學(xué)報, 第13卷第12期，2002.)17 Zhang Xinming. Research on the aggregate traffic characterization and QoS performance bounds. Computer Science, 2004, 31(2): 31-

42、33.(張信明. 聚集業(yè)務(wù)流特性與QOS性能界限的研究. 計算機(jī)科學(xué), 2004, 31(2): 31-33.)18 Zhang Xinming, Cheng Guoliang, et al. On the computation of end-to-end delay bound in guaranteed service by network calculus. Journal of Software, 2002, 12(6): 889-893.(張信明, 陳國良, 顧鈞. 基于網(wǎng)絡(luò)演算計算保證服務(wù)端到端延遲上界.軟件學(xué)報, 2002, 12(6): 889-893.) 19 Chen Z

43、higang, Zhang lianming, et al. Performance analysis of generalized processor sharing based on fractal leaky bucket regulators. Journal on Communications, 2006, 27(6): 29-35.(陳志剛, 張連明, 鄧曉衡, 趙明. 基于分形漏桶整形器的通用處理器共享系統(tǒng)性能分析. 通信學(xué)報, 2006, 27(6): 29-35.)20 Zhang Lianming, Chen Zhigang, et al. Deterministic up

44、per bounds on performance of generalized processor sharing based on fractal regulators. Journal on Communications, 2007, 28(2): 51-57.(張連明, 陳志剛, 等. 基于分形整形器的GPS系統(tǒng)性能確定上界研究. 通信學(xué)報, 2007, 28(2): 51-57.)21 Gao Wenyu, Chen Songqiao, et al. A Survey on network calculus. Microelectronics & Computer, 2004

45、, 21(11): 76-80.(高文宇, 陳松喬, 等. 網(wǎng)絡(luò)微積分學(xué)研究. 微電子學(xué)與計算機(jī), 2004, 21(11): 76-80.)Fan Baohua，born in 1977, Receive B.As degrees in computer science & technology from the University Of Science and Technology of China(USTC), Hefei. China in 2001 and receive M.As degrees in computer science and techniques fro

46、m National University of Defense Technology（NUDT）,Changsha, China. From 2004, he became the Ph.D. candidate in computer science and techniques from National University of Defense Technology（NUDT）. His current research interests include performance analysis of computer networks, network calculus. 樊葆華

47、，男，1977年生，在中國科學(xué)技術(shù)大學(xué)獲得計算機(jī)科學(xué)與技術(shù)學(xué)士學(xué)位，在國防科學(xué)技術(shù)大學(xué)獲得計算機(jī)科學(xué)技術(shù)碩士學(xué)位，目前為國防科技大學(xué)計算機(jī)學(xué)院博士研究生，研究方向為計算機(jī)網(wǎng)絡(luò)建模，網(wǎng)絡(luò)演算等。Email: fanbaohua。Dou Qiang, born in 1976. He is associate professor of School of Computer, National University of Defense Technology (NUDT）. His main research interests are High-speed network interconnection, computer architecture.竇強(qiáng)，男，1976年生，湖南長沙人，國防科技大學(xué)計算機(jī)學(xué)院副教授，主要研究方向為高速網(wǎng)絡(luò)互聯(lián)，計算機(jī)體系結(jié)構(gòu)等Zhang Heying, born in 1964. She has been professor of National University of Defense Technology（NUDT）since 2000. Her main research interests are computer network