網(wǎng)絡擁塞控制若干策略研究及穩(wěn)定性分析楊木易

1、網(wǎng)絡擁塞控制若干策略研究及穩(wěn)定性分析 答辯人： 導 師： 井元偉 教授結論與展望 主要工作緒論2022/9/2擁塞的定義及產(chǎn)生的原因 第一章 緒 論網(wǎng)絡擁塞的基本概念 當網(wǎng)絡中存在過多的數(shù)據(jù)包時，網(wǎng)絡的性能就會下降，這種現(xiàn)象稱為擁塞。 圖1.1 網(wǎng)絡負載與吞吐量及響應時間的關系2022/9/2第一章 緒 論TCP網(wǎng)絡擁塞控制算法的研究概況 基于源端的擁塞控制算法 源端的擁塞控制算法中使用最廣泛的是TCP協(xié)議中基于滑動窗口的擁塞控制算法?？梢苑譃樗膫€階段： 基于路由器的主動隊列管理算法 慢啟動擁塞避免快速恢復快速重傳減小路由器的分組丟失 減小分組通過路由器的延時 避免死鎖現(xiàn)象的發(fā)生 主要優(yōu)點包括

2、以下幾個方面 2022/9/2第一章 緒 論主動隊列管理算法的分類 隨機早期檢測(RED)及其改進算法 基于優(yōu)化理論的擁塞控制算法 基于控制理論的擁塞控制算法 2022/9/2第一章 緒 論網(wǎng)絡擁塞控制中的經(jīng)濟學方法 網(wǎng)絡價控基本策略 對于不同的業(yè)務流類型、不同的服務質量需求，網(wǎng)絡資源有不同的價格。價格要動態(tài)反映網(wǎng)絡節(jié)點的負載狀態(tài)，進一步影響需求變化。 (3) 具有分布式特點。局部節(jié)點的價格由局部信息決定，不需要全局信息。(4) 簡化系統(tǒng)實現(xiàn)，使算法具有可操作性。 2022/9/2第一章 緒 論對策論在網(wǎng)絡擁塞控制中的應用 在網(wǎng)絡工程中，對策的參與者是計算機軟件，有精確的計算能力也不會出錯，只

3、要其符合用戶的要求(用戶指定的優(yōu)化目標)，用戶就沒有理由替換它。因而對策論更適合于描述計算機交互作用中的分布式控制問題，從而可以為網(wǎng)絡擁塞控制問題提供有效的分析方法。2022/9/2第五章基于Kelly模型的滑模變結構AQM算法 第四章基于改進Kelly算法的擁塞控制策略 的穩(wěn)定性分析 第二章對策論在網(wǎng)絡擁塞控制中的應用 第一章 緒 論第三章市場供求原理在網(wǎng)絡擁塞控制中的應用 第六章基于對偶算法的擁塞控制策略全局穩(wěn)定性分析 本文的主要工作 2022/9/2第二章對策論在網(wǎng)絡擁塞控制中的應用Nash 均衡在對策中，如果資源分配向量中，任一用戶占用的資源都是在給定其余用戶所占用資源的情況下，用戶i

4、的最佳對策，即：或者用另一種表達方式，是下述最大化問題的解：則稱構成G的一個Nash均衡。(2.4) (2.5) 對策論在網(wǎng)絡中應用的主要概念及定理 2022/9/2第二章對策論在網(wǎng)絡擁塞控制中的應用激勵Stackelberg策略其中是的待確定的任意函數(shù)。是網(wǎng)絡管理者要求的速率期望點。(2.17) (2.18) (2.19) 2022/9/2第二章對策論在網(wǎng)絡擁塞控制中的應用TCP速率分配的優(yōu)化條件：激勵主從策略在TCP價控中的應用Maximize:over :Maximize:over :Subject to :(2.9) (2.10) 2022/9/2用戶的目標函數(shù)為：取用戶的效用函數(shù)為：

5、設當時，由 (2.20) 2022/9/2第二章對策論在網(wǎng)絡擁塞控制中的應用圖2.4 用戶的效用函數(shù)曲線圖2.5 非線性激勵策略的仿真曲線 數(shù)值例子與仿真結果2022/9/2第二章對策論在網(wǎng)絡擁塞控制中的應用圖2.6 串聯(lián)鏈路中的兩類用戶基于Nash平衡點的主從策略在串聯(lián)鏈路價控中的應用（1）系統(tǒng)1： 對于第一類用戶來說，每個用戶的目標函數(shù)如下： 對于前連續(xù)N條串聯(lián)鏈路的第二類用戶說，每個用戶的目標函數(shù)如下：(2.22) (2.23) 2022/9/2第二章對策論在網(wǎng)絡擁塞控制中的應用如果存在一個獨立的Nash平衡點，那么，管理者（主方）的收入問題：（2）系統(tǒng)2：類似地，對于后連續(xù)條串聯(lián)鏈路的

6、第二類用戶來說，每個用戶的目標函數(shù)如下：Nash平衡問題可由下式來表示：(2.25) (2.26) (2.27) 2022/9/2第二章對策論在網(wǎng)絡擁塞控制中的應用 二者共同決定著整個系統(tǒng)的狀態(tài)。管理者總的收入為：目標函數(shù)分別對 x 求偏導，并使其為0，即：可見，系統(tǒng)1與系統(tǒng)2是息息相關的， (2.29) (2.30) 2022/9/2可以導出一個關于的方程記為由時，可得：當,且函數(shù)在區(qū)間上為單調遞減，因此，在這個區(qū)間存在唯一的解，當且僅當?shù)诙聦Σ哒撛诰W(wǎng)絡擁塞控制中的應用2022/9/2第二章對策論在網(wǎng)絡擁塞控制中的應用 此時：(2.35) （2）系統(tǒng)2： 用類似的方法可求得：(2.39)

7、2022/9/2第二章對策論在網(wǎng)絡擁塞控制中的應用 使用對策論方法可以對網(wǎng)絡資源進行合理的分配，而且能夠在網(wǎng)絡處于輕度擁塞控制的狀況下，引導用戶合理的利用緊張的網(wǎng)絡資源，避免或是減輕擁塞的發(fā)生，表現(xiàn)出了較好的效果。在擁塞發(fā)生時，網(wǎng)絡方可以通過價格的調整，通過經(jīng)濟的手段對用戶的資源使用量進行間接的控制，從而達到擁塞控制的目的。 本章小結 2022/9/2第三章 市場供求原理在網(wǎng)絡擁塞控制中的應用 基于市場供求平衡的網(wǎng)絡價格控制均衡狀態(tài)時，資源配置最優(yōu)，系統(tǒng)總效用最大。 價控策略基于供求的經(jīng)濟模型的主要思想是：以價格為杠桿調節(jié)網(wǎng)絡資源分配，當供給大于需求時，價格下調，刺激消費；當供給小于需求時，價

8、格上升，抑制消費。直到系統(tǒng)達到圖3.1 價格策略函數(shù)曲線 (3.2) (3.3) 2022/9/2第三章 市場供求原理在網(wǎng)絡擁塞控制中的應用 需求反應函數(shù)為需求度；為需求彈性，反映在一個特定服務下用戶消費的敏感性。 (3.6) (3.5) (3.7) (3.4) 2022/9/2第三章 市場供求原理在網(wǎng)絡擁塞控制中的應用；供求平衡點：網(wǎng)絡市場穩(wěn)定的條件是：(1)(3)(2)及是連續(xù)的，且當時，時，是單調增的，是單調減的； (3.8) 2022/9/2情況3: 調整供應指數(shù)對供求平衡點的影響：情況1 ： 不同基本流量單價下的供求平衡：情況2 ： 不同需求度下供求平衡：數(shù)值例子及仿真結果第三章 市

9、場供求原理在網(wǎng)絡擁塞控制中的應用2022/9/2第三章 市場供求原理在網(wǎng)絡擁塞控制中的應用基于Nash平衡點的網(wǎng)絡收益優(yōu)化策略 圖3.5 網(wǎng)絡拓撲結構定義每個用戶的目標函數(shù)如下： (3.10) 2022/9/2第三章 市場供求原理在網(wǎng)絡擁塞控制中的應用這里令圖3.6 市場供求平衡點的確定 (3.20) (3.21) 根據(jù)式 (3.19) (3.22) 2022/9/2N x*kpp+NkL(x)Wi(x*)44.5700.0550.2830.5039.1952.62354.5920.0440.2830.50311.5492.63264.6030.0360.2830.49913.7812.657

10、74.6120.0300.2830.49316.1422.70184.6160.0260.2830.49118.4272.733204.6290.0110.2870.50146.1322.669504.6310.0040.2970.497115.332.6931004.6320.0020.2980.498230.662.104表3.1 N增加時各相關量的變化趨勢第三章 市場供求原理在網(wǎng)絡擁塞控制中的應用2022/9/2第三章 市場供求原理在網(wǎng)絡擁塞控制中的應用 本章小結 本章在分析了網(wǎng)絡價控中的供求平衡點之后將對策論中的Nash均衡理論同市場供求平衡原理相結合，可使用戶達到系統(tǒng)所期望的運行點，

11、從而使雙方的利益趨于平衡。對抑制網(wǎng)絡擁塞具有重要的現(xiàn)實意義。2022/9/2第四章 基于改進Kelly算法的擁塞控制策略的穩(wěn)定性分析 網(wǎng)絡模型描述 Johari 等將Kelly的原始算法離散化(4.1)(4.2)圖4.1 帶延時的網(wǎng)絡模型 2022/9/2BACKGROUND第四章 基于改進Kelly算法的擁塞控制策略的穩(wěn)定性分析 最大-最小Kelly算法(MKA) 穩(wěn)定的擁塞控制策略 其次，為避免速率間的不公平性，必須使每個終端用戶的控制參數(shù)相同進而建立一個統(tǒng)一的系統(tǒng)方程。 用 來代替則Kelly 算法的離散化(4.5)令方程如下：(4.6)(4.7)稱式(4.5)-(4.7)是最大最小Ke

12、ll算法(MKA). 2022/9/2 MKA穩(wěn)定性分析 定理4.1：假設非延時的線性系統(tǒng)L如下所述：(4.8)如果系數(shù)矩陣 是實對稱的，那么當且僅當L是穩(wěn)定時延時系統(tǒng) (4.9)是漸進穩(wěn)定的。第四章 基于改進Kelly算法的擁塞控制策略的穩(wěn)定性分析 2022/9/2第四章 基于改進Kelly算法的擁塞控制策略的穩(wěn)定性分析 其中推論4.1：假設一個N維非線性系統(tǒng)N如下式所示：系統(tǒng)的非線性函數(shù)。如果系統(tǒng)的Jacobian矩陣是(4.20)是局部漸進穩(wěn)定的當且僅當 實對稱的，則系統(tǒng) (4.19)在平衡點 N 在 是局部漸進穩(wěn)定的?；谝陨系耐普?，接下來證明MKA局部漸進穩(wěn)定性。2022/9/2第四

13、章 基于改進Kelly算法的擁塞控制策略的穩(wěn)定性分析 為運用定理4.1，先要證明如下非延時系統(tǒng)的穩(wěn)定性： 不受延時約束的穩(wěn)定性分析 (4.21) (4.23) (4.22) 2022/9/2第四章 基于改進Kelly算法的擁塞控制策略的穩(wěn)定性分析 處線性化，可以得到：其中 因此系統(tǒng)的Jacobian矩陣為： 在 (4.27) (4.28) (4.30) (4.31)2022/9/2第四章 基于改進Kelly算法的擁塞控制策略的穩(wěn)定性分析 特征值 其中 當非線性系統(tǒng)(4.23)的Jacobian矩陣J的特征值都在單位圓以內，則系統(tǒng)是局部漸進穩(wěn)定的。因此，可以得到如下充分必要條件： (4.34)

14、(4.33) 2022/9/2第四章 基于改進Kelly算法的擁塞控制策略的穩(wěn)定性分析 由此可見，延時系統(tǒng)的(4.21)-(4.22)的穩(wěn)定性條件是不受延時約束的。2022/9/2指數(shù)MKA (4.40)第四章 基于改進Kelly算法的擁塞控制策略的穩(wěn)定性分析 2022/9/2第四章 基于改進Kelly算法的擁塞控制策略的穩(wěn)定性分析 (4.43)2022/9/2第四章 基于改進Kelly算法的擁塞控制策略的穩(wěn)定性分析 數(shù)值仿真 圖4.2 時 的軌跡 圖4.3時 的軌跡 2022/9/2第四章 基于改進Kelly算法的擁塞控制策略的穩(wěn)定性分析圖4.5 圖4.4 時 的軌跡 的軌跡 時 的軌跡 2

15、022/9/2第四章 基于改進Kelly算法的擁塞控制策略的穩(wěn)定性分析本章基于Kelly 所提出的模型，針對網(wǎng)絡中存在的往返傳播時延將原有模型的參數(shù)做了兩個改變。通過建立系統(tǒng)對稱的Jacobian矩陣來分析使系統(tǒng)穩(wěn)定時參數(shù)所應滿足的取值范圍。通過分析及仿真結果可知該算法可以很快達到穩(wěn)定，有效地避免了網(wǎng)絡發(fā)生擁塞的可能，對于高速網(wǎng)絡來說，此種擁塞控制策略具有重要的現(xiàn)實意義。 本章小結2022/9/2第五章 基于Kelly模型的滑模變結構AQM算法 比例公平(PFC)算法 在基于經(jīng)濟學效用函數(shù)的AQM算法設計過程中，擁塞控制框架由用戶和網(wǎng)絡兩部分構成。網(wǎng)絡子優(yōu)化問題根據(jù)比例公平準則決定用戶速率。在

16、此優(yōu)化框架下，可以得到源端速率模型： (5.2)(5.3)經(jīng)簡化的源端動力學行為可表示為：瓶頸節(jié)點隊列長度的動態(tài)行為為下式： (5.4)由式(5.3)，(5.4)得到下面非線性狀態(tài)空間方程 (5.5)(5.6)；式中 。是期望的隊列長度。 2022/9/2第五章 基于Kelly模型的滑模變結構AQM算法基于Kelly模型的滑模變結構AQM算法(PSMC-AQM) PSMC-AQM控制器設計 (5.8)(5.7)(5.9)定義滑模面如下到達滑模面可以表示為 ,即 此時，將(5.8)代入(5.5)得出滑模運動方程為由上式可得 (5.10)其中，代表初始時刻。由上式可知，只要保證 ，滑模運動方程(5

17、.9)漸近穩(wěn)定。由 ，可以得出等價控制律 (5.11)2022/9/2第五章 基于Kelly模型的滑模變結構AQM算法標記概率的實際意義我們設計更合理的變結構AQM控制器。假設有如下變結構控制律：(5.12) 定理5.1：如果選擇 ，則選擇變結構控制律(5.12)能驅動系統(tǒng)到達滑模面。 證明：欲證滑模面可到性需證明系統(tǒng)滿足到達條件 。 當 時有 因此，當 時，選擇 滿足到達條件 。 的限制式(5.11)的形式有助于啟發(fā)2022/9/2第五章 基于Kelly模型的滑模變結構AQM算法當 時有 因此，當 時，選擇 滿足到達條件 。 2022/9/2第五章 基于Kelly模型的滑模變結構AQM算法仿

18、真分析 圖5.2 RED算法控制隊列長度平均值圖5.3 PSMC算法控制隊列長度平均值2022/9/2第五章 基于Kelly模型的滑模變結構AQM算法基于Kelly模型的終端滑模AQM算法(TSMC-AQM) 終端滑模面設計 。 終端滑模面的設計原則不是使其上的滑模運動漸近穩(wěn)定，而是使其上的滑模運動在有限的時間內到達平衡點，從而提高路由器中隊列長度向期望值收斂的速度，由于收斂速度得到了加快，因此必將提高擁塞控制的性能。 所設計的終端滑模面具有如下的形式 (5.17) 其中：，均為大于零的常數(shù)，和 為正奇數(shù)，且滿足 。當系統(tǒng)狀態(tài)運動到該終端滑模面上時， 此時由式(5.17)能夠得到下式(5.18

19、) 將式(5.18)代入到式(5.5)中即得如下的滑模運動方程 (5.19) 2022/9/2第五章 基于Kelly模型的滑模變結構AQM算法 為了證明滑模運動方程(5.19)能夠在有限的時間內收斂到平衡點，引入如下的引理。引理5.1156：如果正定函數(shù) 的導數(shù)滿足如下的微分不等式 ， ， (5.20) 其中:， 均為常數(shù)，那么 滿足如下的不等式 ， (5.21) 并且 ， (5.22) 其中 由下式確定 (5.23) 2022/9/2第五章 基于Kelly模型的滑模變結構AQM算法， 那么 沿滑模系統(tǒng)(5.19)的導數(shù)為 定理5.3：所設計的終端滑模面(5.17)能夠保證其上的滑模運動方程(

20、5.19)在 時間內到達平衡點， 并且時間 由下式確定 (5.24) 其中： 證明：取如下形式的Lyapunov函數(shù) (5.25) 根據(jù)式(5.25)得到下式 (5.27) (5.26) 根據(jù)引理5.1得 (5.28) 2022/9/2第五章 基于Kelly模型的滑模變結構AQM算法終端滑模AQM控制器的設計 定理5.4：對于系統(tǒng)(5.5)和(5.6)，設計如下形式的終端滑模AQM控制器， (5.32) 其中： 那么該控制器將滿足到達條件。 證明: 選擇 Lyapunov函數(shù)如下 (5.33) 2022/9/2第五章 基于Kelly模型的滑模變結構AQM算法沿著系統(tǒng)軌跡(5.4)，(5.5)的

21、微分為 將式(5.21)代入上式，得到因此，終端滑模AQM控制器(5.32)能夠滿足到達條件，定理證畢。 2022/9/2第五章 基于Kelly模型的滑模變結構AQM算法仿真分析 在這一部分中，通過仿真來驗證本節(jié)算法(TSMC)的有效性。為了比較的目的，也對普通的滑模AQM控制器SMVS進行了仿真。圖5.5 使用SMVS控制器時的隊列長度 圖5.6 使用TSMC控制器時的隊列長度2022/9/2第五章 基于Kelly模型的滑模變結構AQM算法圖5.7 網(wǎng)絡參數(shù)N變化時的比較 圖5.8 網(wǎng)絡參數(shù)C變化時的比較 圖5.9 往返時延變化時的比較 2022/9/2第五章 基于Kelly模型的滑模變結構

22、AQM算法 本章小結 本章提出了有效的AQM控制方案。為了改善網(wǎng)絡流量動態(tài)變化時的響應，采用基于Kelly比例公平模型的滑模控制器(PSMC)作為AQM控制器。終端滑模AQM控制器(TSMC)，通過設計一個非線性的滑模面使路由器中的隊列長度能夠在有限的時間內到達期望值，并給出了這一時間上界的具體表達式，提高了隊列長度的收斂速度。 2022/9/2第六章 基于對偶算法的擁塞控制策略全局穩(wěn)定性分析 對偶算法 (6.4) (6.5) (6.6)將式(6.4)-(6.6)稱為對偶算法 2022/9/2第六章 基于對偶算法的擁塞控制策略全局穩(wěn)定性分析穩(wěn)定性分析 為了研究系統(tǒng)在平衡點附近的動態(tài)特性，考慮如下系統(tǒng)：單鏈路單用戶的穩(wěn)定性 (6.7) (6.12) 取如下形式的Lyapunov函數(shù)：(6.13)(6.14)2022/9/2第六章 基于對偶算法的擁塞控制策略全局穩(wěn)定性分析往返延時下的單鏈路單用戶穩(wěn)定性分析 (6.15) 與式(6.12)類似，定義如下系統(tǒng)： (6.16) 2022/9/2第六章 基于對偶算法的擁塞控制策略全局穩(wěn)定性分析取Lyapu