因特網(wǎng)絡(luò)擁塞控制機(jī)制的數(shù)學(xué)架構(gòu)研究

徐 輝，寧國強(qiáng)

（西安通信學(xué)院 陜西 西安 710106）

因特網(wǎng)技術(shù)是人類進(jìn)入信息化社會最為關(guān)鍵的技術(shù)之一，隨著因特網(wǎng)用戶數(shù)的日益增加，業(yè)務(wù)種類越來越多，要實(shí)現(xiàn)因特網(wǎng)對用戶業(yè)務(wù)需求的良好滿足，擁塞控制是主要技術(shù)之一。從因特網(wǎng)設(shè)計(jì)的初衷來看，該網(wǎng)絡(luò)是被設(shè)計(jì)為一種“盡力而為”（Best Effort）服務(wù)，是由所有網(wǎng)絡(luò)用戶來競爭網(wǎng)絡(luò)的有限資源，但是，隨著因特網(wǎng)業(yè)務(wù)的發(fā)展和用戶數(shù)的激增，現(xiàn)在因特網(wǎng)所處環(huán)境和其設(shè)計(jì)之處，發(fā)生了巨大的變化，因特網(wǎng)需要利用有限的資源為用戶提供多樣化服務(wù)，擁塞控制機(jī)制是因特網(wǎng)滿足用戶服務(wù)需求，保證網(wǎng)絡(luò)資源合理化使用的重要手段之一，在因特網(wǎng)技術(shù)研究中一直占據(jù)重要地位。但是，由于因特網(wǎng)規(guī)模大，結(jié)構(gòu)復(fù)雜，因此，傳統(tǒng)擁塞控制多采用基于經(jīng)驗(yàn)和實(shí)驗(yàn)方式，使得具有很大主觀性和片面性；隨著擁塞控制技術(shù)的發(fā)展，為了提高其科學(xué)合理性，多種數(shù)學(xué)工具被引入到擁塞控制的設(shè)計(jì)中，文中對現(xiàn)有因特網(wǎng)擁塞控制機(jī)制的數(shù)學(xué)模型進(jìn)行了分析，提出了一個(gè)用于因特網(wǎng)的分析和設(shè)計(jì)的統(tǒng)一的數(shù)學(xué)框架，對研究熱點(diǎn)問題了進(jìn)行了分析和研究，為進(jìn)一步研究奠定了基礎(chǔ)。

1 擁塞控制數(shù)學(xué)框架構(gòu)建

在因特網(wǎng)擁塞控制技術(shù)的研究中，最初采用基于采用經(jīng)驗(yàn)加技巧的方式進(jìn)行，由于其構(gòu)造和評價(jià)過程過于依賴試驗(yàn)和仿真，所以這種方法具有很大的主觀和片面性。對因特網(wǎng)擁塞控制進(jìn)行數(shù)學(xué)建模，然后根據(jù)數(shù)學(xué)模型進(jìn)行設(shè)計(jì)和分析，則是較先進(jìn)的方式。采用這種方式，由于將擁塞控制問題轉(zhuǎn)化為精確的數(shù)學(xué)模型進(jìn)行求解，因而提高了算法的理論保證，同時(shí)便于為擁塞控制算法的設(shè)計(jì)提供一個(gè)統(tǒng)一的理論構(gòu)架。在因特網(wǎng)擁塞控制技術(shù)的發(fā)展中，先后有經(jīng)濟(jì)學(xué)模型、最優(yōu)化理論、博弈論和控制論等多種數(shù)學(xué)模型提出，通過對這些模型的分析發(fā)現(xiàn)，因特網(wǎng)擁塞控制的本質(zhì)是如何控制網(wǎng)絡(luò)業(yè)務(wù)接入以最優(yōu)化使用網(wǎng)絡(luò)有限資源，最大化滿足網(wǎng)絡(luò)用戶業(yè)務(wù)需求，因此，控制論和最優(yōu)化理論是因特網(wǎng)擁塞控制理論建模的關(guān)鍵，其統(tǒng)一數(shù)學(xué)架構(gòu)可由圖1所示結(jié)構(gòu)來表示。在該結(jié)構(gòu)中包括擁塞控制算法的設(shè)計(jì)和擁塞控制算法的分析兩個(gè)部分。

擁塞控制算法的設(shè)計(jì)問題就是根據(jù)最優(yōu)化模型確立擁塞控制源端算法和鏈路算法的過程。在這方面的研究中，Low[1-3]等 人 剖 析 了 常 見 的 TCPAQM策 略 （RenoDrop Tail、RenoRED、RenoREM、VegasDrop Tail和 Vega sREM），定義了一組對偶的擁塞控制算法：

其中Fs表示TCP源端算法的更新方程，Gl表示AQM鏈路算法的更新方程，qr為源端接收到的聚合定價(jià)，這樣擁塞控制算法便可以通過一個(gè)3元組（F，G，U）來描述。為每種策略定義了3元組（F，G，U），并根據(jù)每個(gè)三元組詳細(xì)討論了這些算法的具體性能在獲知擁塞控制的對偶算法式（1）后，便可根據(jù)控制論知識或優(yōu)化理論來分析該擁塞控制算法的動力學(xué)特性和均衡特性。擁塞控制的分析問題就是對當(dāng)前擁塞控制進(jìn)行理論分析，其關(guān)鍵之處在于根據(jù)當(dāng)前的擁塞控制算法建立合適的對偶算法式（1），然后進(jìn)行動力學(xué)特性和均衡分析。常見的描述擁塞控制算法的動力學(xué)特性參數(shù)有穩(wěn)定性、收斂性和可擴(kuò)展性等，常見的均衡特性參數(shù)有吞吐量、丟失率、時(shí)延、排隊(duì)長度和公平性等。

圖1幾乎涵蓋了所有的理論研究和擁塞控制算法的問題，囊括了絕大多數(shù)的有關(guān)因特網(wǎng)擁塞控制建模的研究要點(diǎn)，但此處僅就當(dāng)前研究的熱點(diǎn)加以介紹。

圖1 因特網(wǎng)擁塞控制數(shù)學(xué)模型的體系結(jié)構(gòu)Fig．1 Architecture of themathematicmodeling about internet congestion controlmechanism

2 因特網(wǎng)擁塞控制研究熱點(diǎn)分析

2.1 公平性特性的研究

有關(guān)公平性的研究一直是因特網(wǎng)擁塞控制建模領(lǐng)域的熱點(diǎn)，它表征了不同用戶使用網(wǎng)絡(luò)資源的差異，反映了因特網(wǎng)資源的配置情況。最常見的公平性準(zhǔn)則是最大最小公平（Max-Min Fairness）或稱為瓶頸最優(yōu)準(zhǔn)則[4]。該公平性準(zhǔn)則給每個(gè)用戶相同的權(quán)限，確保了共享同一瓶頸的用戶能獲得相同的資源。為了表征不同的用戶在面對相同的擁塞時(shí)表現(xiàn)出不同的響應(yīng)，Kelly[5]建議了一種比例公平準(zhǔn)則（Proportional Fairness），該準(zhǔn)則要求網(wǎng)絡(luò)資源的分布同自身的業(yè)務(wù)相關(guān)。從網(wǎng)絡(luò)傳輸時(shí)延角度考慮，文獻(xiàn)[6]提出了一種最小潛在時(shí)延的公平性準(zhǔn)則（Potential Delay Minimization）。 更一般的，文獻(xiàn)[7]提出了一種通用公平性準(zhǔn)則——基于效用函數(shù)的公平性，在文中，作者定義了一類特殊的效用函數(shù)：

作者指出，不同的參數(shù)α將會使網(wǎng)絡(luò)獲得不同的公平性：

α=0，網(wǎng)絡(luò)將獲得最大吞吐量的資源配置；

α=1，網(wǎng)絡(luò)將獲得比例公平的資源配置；

α=2，網(wǎng)絡(luò)將獲得最小潛在時(shí)延的資源配置；

α→∞，網(wǎng)絡(luò)的資源配置將趨近于最大最小公平。

在文獻(xiàn)[7]的基礎(chǔ)上，文獻(xiàn)[8]從更深層次上對公平性進(jìn)行了研究并指出最優(yōu)化模型 （2）最終會使網(wǎng)絡(luò)的資源配置達(dá)到Pareto最優(yōu)[9]，并且作者還找尋到了常見公平性準(zhǔn)則的物理意義：

最大吞吐量公平性準(zhǔn)則會使用戶吞吐量的算術(shù)平均值（Arithmetic Mean）最大；

比例公平準(zhǔn)則會使用戶吞吐量的幾何平均值（Geometric Mean）最大；

最小潛在時(shí)延公平準(zhǔn)則會使用戶吞吐量的調(diào)和平均值（Harmonic Mean）最大。

對于實(shí)際因特網(wǎng)所滿足的公平性準(zhǔn)則，Kelly[5]指出TCPAQM算法最終能使網(wǎng)絡(luò)達(dá)到加權(quán)比例公平。而Low[1]通過對偶理論的研究，指出當(dāng)前的基于TCPRenoRED的因特網(wǎng)應(yīng)當(dāng)滿足加權(quán)最小潛在時(shí)延的公平性準(zhǔn)則。

2.2 穩(wěn)定性的研究

穩(wěn)定性是表征網(wǎng)絡(luò)是否健壯的參數(shù)，有關(guān)因特網(wǎng)穩(wěn)定性的研究也一直是因特網(wǎng)理論研究領(lǐng)域的熱點(diǎn)。

Kelly[5]基于最優(yōu)化理論提出了一類擁塞控制框架，并利用Lyapunov穩(wěn)定性理論分析了擁塞控制系統(tǒng)的穩(wěn)定性。

文獻(xiàn) [10]使用了流的思想和隨機(jī)微分方程理論為TCPAQM擁塞控制算法建立了一個(gè)動態(tài)的微分方程系統(tǒng)：

其中，R（t）=q（t）/C+Tp，W 為 TCP 窗口，q 為擁塞隊(duì)列長度，R為RTT時(shí)間，C為排隊(duì)容量，Tp為傳輸時(shí)延，N為TCP的會話數(shù)目，p為包丟失概率。

結(jié)合上述微分動力系統(tǒng)，文獻(xiàn)[11]使用了經(jīng)典控制理論對擁塞控制的穩(wěn)定性進(jìn)行了分析，建立了一個(gè)通用的線性時(shí)延反饋控制系統(tǒng)（圖2）。在這個(gè)模型當(dāng)中，反饋控制系統(tǒng)包含有：Plant，代表一個(gè)子系統(tǒng)的組合，包括TCP源、鏈路以及TCP接收端；AQM控制器，產(chǎn)生分組丟棄概率pd作為一個(gè)控制信號來控制進(jìn)入路由器隊(duì)列的分組到達(dá)速率；作為Plant變量的路由器的隊(duì)列長度（就是受控制的變量）Qt；路由器中期望的隊(duì)列長度 Qref；反饋信號（采樣的系統(tǒng)輸出）e（t）=Qref-Qt。根據(jù)這一模型，只要確定該模型中的各個(gè)要素，便會很容易的判定網(wǎng)絡(luò)的穩(wěn)定特性。

圖2 擁塞控制的線性時(shí)延反饋控制系統(tǒng)Fig．2 Linear time-delay feedback control system for internet congestion control

不同于文獻(xiàn)[11]的研究，Low等人建立了一個(gè)基于對偶理論的控制論模型[1]（圖3）。該模型是一個(gè)拉普拉斯域上的多變量的魯棒控制系統(tǒng)，在該模型中，源端的發(fā)送速率x同鏈路定價(jià)p互為對偶；源端接收到的聚合定價(jià)q同鏈路上的聚合速率 y互為對偶，Af（s）和 Ab（s）分別為前向和后向的傳輸矩陣，F(xiàn)（·）和G（·）分別為源端算法和鏈路算法。在文獻(xiàn)[12]中，Paganini使用了現(xiàn)代控制理論和奈奎斯特準(zhǔn)則對該模型進(jìn)行了討論和分析。

圖3 擁塞控制的魯棒控制系統(tǒng)Fig．3 Robust control system about internet congestion control

3 結(jié)束語

文中主要對因特網(wǎng)擁塞控制的統(tǒng)一數(shù)學(xué)構(gòu)建進(jìn)行了研究，分析了其主要研究熱點(diǎn)，從對因特網(wǎng)進(jìn)行簡單的考慮開始，到對其進(jìn)行成熟的建模，這里面包含了眾多的研究成果，但是，由于因特網(wǎng)的復(fù)雜性和不斷發(fā)展，對因特網(wǎng)擁塞控制建立準(zhǔn)確的數(shù)學(xué)模型不可能一蹴而就，還有很多問題尚待研究。對整個(gè)因特網(wǎng)的公平性、穩(wěn)定性、可擴(kuò)展性的分析由于受復(fù)雜網(wǎng)絡(luò)的影響，很難進(jìn)行全局的動力學(xué)理論分析。像因特網(wǎng)這樣的一個(gè)復(fù)雜的系統(tǒng)，對其分析與控制，只有通過通信、

控制、經(jīng)濟(jì)學(xué)和數(shù)學(xué)等多學(xué)科的共同努力，才有望獲得突破性的成果。

[1]Low SH， Paganini F，Doyle JC．Internet congestion control[J]．IEEE Control Systems Magazine，2002，22（1）：28-43．

[2]Low S H．A duality model of TCP and queue management algorithms[J]．IEEE/ACM Trans．on Networking，2003，11（4）：525-536．

[3]Low SH，Srikant R．A mathematical framework for designing a low-loss， low-delayinternet[J]．Networkand SpatialEconomics，2004，4（1） ：75-102．

[4]Jaffe JM．Bottleneck flow control[J]．IEEE Trans，1981，29（29）：954-962．

[5]Kelly F P，Maulloo A，Tan D．Rate control in communication networks：shadow prices， proportional fairness and stability[J]．Journal of the Operational Research Society，1998（49）：237-252．

[6]Massoulie L，Roberts J．Bandwidth sharing：objectives and algorithms[C]//Proc．of the IEEE INFOCOM’99，March 1999：1395-1403．

[7]Mo J，Walrand J．Fair end-to-end window-based congestion control[J]．IEEE/ACM Transactions on Networking，2000，8（5）：556-567．

[8]Bonald T，Massoulie T．Impact of fairness on Internet performance[C]//In Proceedings of ACM Sigmetrics，2001：82-91．

[9]瓦里安．微觀經(jīng)濟(jì)學(xué) [M]．3版．北京：經(jīng)濟(jì)科學(xué)出版社，1997．

[10]Misra V，Gong W B，Towsley D．Fluid-based analysis of a network of AQM routers supporting tcp flows with an application to RED[C]//Proc．ACM SIGCOMM，2000：151-160．

[11]Hollot C V．A Control Theoretic Analysis of RED[C]//Proc．INFOCOM 2001，2001：1510-1519．

[12]Paganini F．A global stability result in network flow control[J]．Systems and Control Letters，2002，46（3）：153-163．