1、TCP/IP網絡擁塞控制若干問題的研究,答辯人： 何 凌 導 師： 井元偉 教授,結論與展望,主要工作,緒論,第一章 緒論,網絡擁塞的基本概念 擁塞是一種持續(xù)過載的網絡狀態(tài)。此時用戶對網絡資源的需求超過了其固有的容量。 網絡擁塞產生的原因 存儲空間不足 帶寬容量不足 處理器速度慢、能力弱 擁塞控制的基本思想 采取某種控制措施減少或避免網絡中出現(xiàn)擁塞現(xiàn)象。,圖1.1 網絡負載與吞吐量及響應時間的關系,基于源端的TCP擁塞控制機制,“和式增加積式減少（AIMD）”,基于窗口的閉環(huán)控制方式,慢 啟 動,擁 塞 避 免,快 速 重 傳,快 速 恢 復,第一章 緒論,基于路由器的IP擁塞控制機制,通過路

2、由器等中間節(jié)點設備采用隊列算法實現(xiàn),第一章 緒論,在這類算法中TCP的連接是一種互動的行為，AQM控制器可以看作一個梯度優(yōu)化問題，算法的目標是最大化網絡利用率。 Kelly等學者基于優(yōu)化理論49提出了一個分散擁塞控 制框架，從而建立了TCP速率控制的模型。 Kunniyur在Kelly源端速率模型的基礎上提出AVQ算 法。 Low等基于優(yōu)化理論提出了TCP/AQM對偶性模型。,基于優(yōu)化理論的擁塞控制算法,第一章 緒論,基于控制理論的擁塞控制算法,第一章 緒論,從控制理論角度，擁塞控制算法分為開環(huán)控制和閉環(huán)控制兩大類。,Misra等63提出了TCP/AQM微分方程模型。,圖1.8 TCP擁塞控制

3、與AQM算法組成的反饋控制模型,文獻64運用經典控制理論證明了采用RED控制的的系統(tǒng)中穩(wěn)定時控制器參數所要滿足的條件,Hollot等65研究了在AQM中采用經典的PI控制器的設計方法。,文獻67則直接運用狀態(tài)反饋控制理論，給出了狀態(tài)反饋控制器的設計。,現(xiàn)有算法存在的問題,第一章 緒論,已有的AQM設計大多是依賴于確定的網絡模型， 沒有考慮到參數的時變性以及模型的不確定性的 影響。 擁塞控制系統(tǒng)的穩(wěn)定性分析是控制理論的難點課題。,第五章 基于顯式速率反饋的擁塞控制算法,第四章 基于自適應灰色預測的VRC虛速率算法,第二章 基于IMC-Smith算法的AQM策略,第一章 緒 論,第三章 AQM中的

4、模糊-Smith算法,第六章 基于價格策略的擁塞控制機制,本文的主要工作,第七章 網絡擁塞控制算法的穩(wěn)定性分析,TCP流量窗口控制機制動態(tài)模型：,第二章 基于IMC-Smith的AQM策略,圖2.5 基于TCP流體模型的網絡擁塞反饋控制結構圖,網絡控制系統(tǒng)建模,圖2.2 啞鈴型拓撲結構的分組交換網絡,Smith預估控制系統(tǒng)轉換成如下圖的等價結構：,得到Smith預估控制系統(tǒng)的內模控制結構,按照內?？刂扑惴ㄔO計控制器,第二章 基于IMC-Smith的AQM策略,(2.24),圖2.7 IMC-Smith控制系統(tǒng)結構框圖,仿真研究,圖2.8 模型匹配時IMC-Smith控制算法仿真曲線,圖2.9

5、滯后時間變化時仿真曲線,第二章 基于IMC-Smith的AQM策略,圖2.10 模型失配時仿真曲線,圖2.11 激活的TCP連接數變化時的仿真曲線,第二章 基于IMC-Smith的AQM策略,本章小結 本章從控制理論的角度描述了帶AQM的網絡擁塞閉環(huán)控制系統(tǒng)結構，給出了IP網絡系統(tǒng)受控對象的一種傳遞函數模型。并提出了一種結合內?？刂破骱蚐mith預估補償控制器的IMC-Smith控制算法，通過仿真實驗表明，該策略能有效克服網絡時延的影響，對網絡模型參數的變化具有較好的魯棒性。,第三章 AQM中的模糊-Smith算法,設計目標：基于模糊Smith設計一個AQM控制器來穩(wěn)定路由器 中的隊列長度使其

6、在目標隊列附近,圖 3.1 模糊-Smith系統(tǒng)結構,圖3.4 改進的Smith 預估補償控制原理圖,第三章 AQM中的模糊-Smith算法,在原對象模型與Smith預估器模型的比較器之后串上一個低通濾波器，可以大大減少模型失配的敏感，增加Smith預估控制系統(tǒng)魯棒性。,由二維模糊控制器實現(xiàn),隊列長度的誤差及誤差的變化率作為模糊控制器的輸入,隊列長度的誤差分為五個模糊子集，為負小、負大、零、正小、正大,誤差的變化率也分為五個模糊子集，為負小、負大、零、正小、正大,模糊控制器的設計,丟棄概率作為模糊控制器的輸出,第三章 AQM中的模糊-Smith算法,E,表3.3 模糊控制器的控制規(guī)則表,模糊控

7、制器的輸出由下式給出：,(3.6),第三章 AQM中的模糊-Smith算法,仿真,圖3.8 小時滯時三種控制器比較,圖3.9 大時滯時三種控制器比較,圖3.10 參數變化時三種控制器比較,第三章 AQM中的模糊-Smith算法,本章小結 本章從控制理論的角度描述了帶AQM的網絡擁塞閉環(huán)控制系統(tǒng)結構，提出了一種結合模糊控制器和Smith預估補償控制器的模糊Smith控制算法，通過仿真實驗表明，該策略能有效克服網絡時延的影響，對網絡模型參數的變化具有較好的魯棒性。,第三章 AQM中的模糊-Smith算法,第四章 基于灰色預測自適應PID理論的VRC算法,圖4.2 灰色預測自適應PID網絡控制系統(tǒng)框

8、圖,AQM算法分為兩種類型：1)基于速率的擁塞控制，控制擁塞鏈 路的數據流的速率； 2)基于隊列的擁塞控制，控制擁塞鏈 路的隊列長度。,文獻97, 98提出了一種虛速率控制算法(VRC),VRC的標記概率表達式：,(4.10),(4.14),我們采用自適應的形式，將上式寫成,式中 ：,第四章 基于灰色預測自適應PID理論的VRC算法,設 ：,(4.16),(4.18),(4.19),設系統(tǒng)的性能指標為,式中d為下文所指的預測時間。,第四章 基于灰色預測自適應PID理論的VRC算法,灰色預測器的輸入時間序列如下：,得到原始數據對t+d時刻的預測為,(4.20),(4.24),(4.25),(4.

9、35),穩(wěn)定性分析,設離散Lyapunov函數為：,第四章 基于灰色預測自適應PID理論的VRC算法,當 時，系統(tǒng)穩(wěn)定,(4.36),(4.37),瓶頸鏈路中單路TCP連接,圖4.3 局域網無參數改變時的隊列長度,仿真性能分析,圖4.4 局域網參數改變時的隊列長度,第四章 基于灰色預測自適應PID理論的VRC算法,圖4.5 廣域網無參數改變時的隊列長度,圖4.6 廣域網參數改變時的隊列長度,瓶頸鏈路中多路TCP連接,圖4.7 TCP連接帶寬,第四章 基于灰色預測自適應PID理論的VRC算法,圖4.8 局域網無參數改變時的隊列長度,圖4.9 局域網參數改變時的隊列長度,圖4.10 廣域網無參數改

10、變時的隊列長度,圖4.11 廣域網較壞網絡狀況時的隊列長度,本章小結 本章針對基于PID控制的虛速率VRC主動隊列管理算法加以改進，提出了一種新的VRC算法。將二次型性能指標引入到PID控制器的整定過程中，按照性能指標的負梯度方向修改加權系數，實現(xiàn)了PID的自適應最優(yōu)控制，同時將自適應PID與灰色預測器相結合，用預測結果代替被控對象測量值，補償了網絡時滯，實現(xiàn)了“事先調節(jié)”。并且對算法進行了穩(wěn)定性分析。此外，本章通過細致的仿真實驗分析了算法在改善網絡性能方面的有效性。算法能穩(wěn)定地適應網絡環(huán)境動態(tài)變化，超調量小，振蕩輕微，快速收斂于路由器隊列長度期望值，自適應克服了網絡干擾和滯后特性的影響。,第

11、四章 基于灰色預測自適應PID理論的VRC算法,緩沖器中某一TCP連接的隊列長度可由下列方程所確定：,第五章 基于顯式速率反饋的擁塞控制算法,(5.1),控制器設計,控制性能指標：,穩(wěn)定性條件：當 ， 。 充分利用帶寬條件：當 ，隊列長度 。,圖5.3 控制系統(tǒng)圖,系統(tǒng)的閉環(huán)特征方程為：,(5.4),令閉環(huán)特征方程在 處有雙重極點,(5.6),(5.7),第五章 基于顯式速率反饋的擁塞控制算法,設計濾波器,第五章 基于顯式速率反饋的擁塞控制算法,令 輸入到 的期望傳遞函數 為：,(5.8),令,(5.9),第五章 基于顯式速率反饋的擁塞控制算法,控制算法仿真研究,瓶頸鏈路中僅有單路TCP連接,

12、圖5.6 局域網無參數改變時的隊列長度,圖5.7 局域網參數改變時的隊列長度,圖5.8 廣域網無參數改變時的隊列長度,圖5.9 廣域網參數改變時的隊列長度,瓶頸鏈路中多路TCP連接,圖4.7 TCP連接帶寬,圖5.11 局域網無參數改變時的隊列長度,圖5.12 局域網參數改變時的隊列長度,圖5.13 廣域網無參數改變時的隊列長度,圖5.14 廣域網較壞網絡狀況時的隊列長度,第五章 基于顯式速率反饋的擁塞控制算法,第五章 基于顯式速率反饋的擁塞控制算法,本章小結,本章將Smith控制算法應用于TCP擁塞控制，較好地克服了網絡的傳播時延給擁塞控制所帶來的不利影響，使源端的TCP發(fā)送窗口能快速響應網

13、絡狀態(tài)的變化，即避免了擁塞的發(fā)生，又保證了瓶頸鏈路的帶寬得到充分利用，使網絡處于良好的運行狀態(tài)。而且，當控制系統(tǒng)進入穩(wěn)定后，能使TCP發(fā)送窗口的變化很平穩(wěn)?？刂葡到y(tǒng)的良好魯棒性又使本方案具有很大的實用價值。,第六章 基于價格策略的擁塞控制機制,系統(tǒng)模型與分析,考慮一個具有資源集合的網絡，資源的有限容量為 C,集合N中的用戶以 的速率來使用網絡，對于整個網絡來說，資源負載為 ,資源使用率為 。 對于每一個用戶，其總體效用如下：,整個系統(tǒng)的總體效用如下：,(6.1),(6.2),用戶效用最大化的解,系統(tǒng)效用最大化的解,第六章 基于價格策略的擁塞控制機制,基于資源占有率的價格策略,規(guī)定在資源使用率為

14、 時，價格函數設定為 。,令,第六章 基于價格策略的擁塞控制機制,(6.11),基于激勵Stackelberg的價格策略,Stackelberg激勵策略是對策論中的一種策略，又稱主從策略。在激勵策略中，分為主方和從方。主方發(fā)布激勵策略，當從方與主方提供的目標不一致時，懲罰函數將激勵或迫使從方采取對整個整體有益的行為。一個資源分配向量構成Nash 均衡,意味著沒有用戶有單方面改變自己策略(所使用資源的數量) 的動機。,第六章 基于價格策略的擁塞控制機制,在這里的這個策略中，網絡商是主方，用戶是滿足Nash平衡點的從方，允許網絡方和用戶方任意改變速率xs，s=1,2,n。引入Stackelberg

15、策略： 其中 是 待確定的函數。 是系統(tǒng)效用最大化的解。,(6.19),線性激勵策略,假設 為線性函數，即：,令,第六章 基于價格策略的擁塞控制機制,(6.22),(6.23),非線性激勵策略,當資源占有率小于等于20%，即 時，考慮非線性策略： 當資源占有率大于等于90%，即 時，考慮非線性策略：,第六章 基于價格策略的擁塞控制機制,(6.25),(6.26),數值例子和仿真,圖6.2 用戶 的效用函數曲線,圖6.3 系統(tǒng) 的效用函數曲線,第六章 基于價格策略的擁塞控制機制,圖6.4 采取了基于資源占有率的價格策略后用戶的效用函數曲線,圖6.5 的情況下采取線性激勵策略后的用戶效用函數等高線

16、圖,圖6.6 情況下采取了非線性激勵策略后用戶效用函數的等高線圖,圖6.7 情況下采取了非線性激勵策略后的價格曲線,第六章 基于價格策略的擁塞控制機制,本章小結 本章從經濟學的角度出發(fā)，應用價格手段來實現(xiàn)網絡的擁塞控制提出了兩種價格策略，首先將資源占有率引入到價格策略中，構造了基于資源占有率的價格策略；另外將網絡中的效用函數模型同對策論中的激勵Stackelberg策略相結合，提出了基于激勵Stackelberg的價格策略。通過仿真實驗，得到了理想的結果，證明了兩種策略的有效性。,TCP/AQM對偶性模型主導思想,鏈路,源端 （用戶）,反饋,價格,發(fā)送速率,調整,影響,效用函數,第七章 網絡擁

17、塞控制算法的穩(wěn)定性分析,對偶控制算法,對效用函數有如下兩個假設:,在區(qū)間 中效用函數 是單調增的、嚴格凹的，并且連續(xù)二次可微的。 的曲率被限制遠離零的,即在 上: 對所有的 有,第七章 網絡擁塞控制算法的穩(wěn)定性分析,原始問題 （擁塞控制的目標）,選取發(fā)送速率，使得：,第七章 網絡擁塞控制算法的穩(wěn)定性分析,(7.4),對偶問題,目標為選取擁塞度量(即對偶變量),使得：,定義 Lagrangian 式子,第七章 網絡擁塞控制算法的穩(wěn)定性分析,(7.5),(7.9),(7.7),(7.8),對偶問題的梯度算法,第七章 網絡擁塞控制算法的穩(wěn)定性分析,(7.11),(7.13),對偶梯度算法的全局穩(wěn)定性

18、分析,第 個緩沖器中的隊列將有如下排隊動態(tài)變化,第七章 網絡擁塞控制算法的穩(wěn)定性分析,(7.14),(7.16),定理 1 忽略傳輸時延的情況下，由式 (7.9), (7.12), (7.14)以及 (7.13)組成的閉環(huán)系統(tǒng)(7.16)是全局穩(wěn)定的。,證明： 定義如下Lyapunov函數：,第七章 網絡擁塞控制算法的穩(wěn)定性分析,定義一對角矩陣,由假設(2)有 0,這里 是一指示函數，如果 成立則 ，否則為0。,第七章 網絡擁塞控制算法的穩(wěn)定性分析,定義如下矩陣,定理得證。,第七章 網絡擁塞控制算法的穩(wěn)定性分析,定理 2 式(7.28) 的單源單鏈路閉環(huán)系統(tǒng)全局穩(wěn)定的 條件是 ， 。,證明： 定義如下Lyapun