基于阻尼牛頓法的擁塞速率控制算法

黃玉濤

摘 要 本文使用阻尼牛頓法來進行鏈路價格的計算，提出一種基于阻尼牛頓法的擁塞速率控制算法，仿真結果表明，本文所提出的算法具有更快的收斂速度，算法性能優于基于梯度下降法的鏈路價格計算算法。

關鍵詞 擁塞 速率控制 阻尼牛頓法

中圖分類號：TP393 文獻標識碼：A

Congestion Rate Control Algorithm Based on Damping Newton Method

HUANG Yutao

（Nanjing Foreign Language School in Xianlin， Nanjing， Jiangsu 210007）

Abstract This paper present a congestion rate control algorithm based on damping Newton method to calculate link price. The simulation results show that the algorithm is superior to the algorithm based on gradient descent method with more rapid speed.

Key words Congestion； Rate Control； Damping Newton Method

0 引言

擁塞速率控制對于提高計算機的網絡性能具有重要作用。文獻[1]，[2]將網絡擁塞度量表示為鏈路價格，建立了進行理論分析的最優速率模型。該模型使用非線性優化模型來求取各個用戶的最優發送速率，奠定了使用鏈路價格對網絡擁塞控制進行研究的基礎。

然而，文獻[1]，[2]中所提出的最優速率模型采用了梯度下降法來計算鏈路價格，但梯度下降法存在收斂速度慢的缺點。阻尼牛頓法既保持了牛頓法快速收斂的優點，極值點又不敏感于初始數值的選取。因此，本文提出一種使用阻尼牛頓法[3]來計算鏈路價格的擁塞速率控制算法。

1 最優速率模型

最優速率模型中，為用戶連接分配的速率，（）為的效用值，優化的目標函數為：（） （1）

約束條件為：≤，≥0 （2）

公式中，為鏈路的帶寬，數據流的集合為。

公式（1）、（2）為約束優化問題，將約束優化轉化為無約束優化：（） = （）（） （3）

基于梯度下降法，用戶最優速率的求?。?/p>

= （） = （） = 0 （4）

式中，用戶鏈路價格和為。

發送方計算公式為： = （） （5）

每個鏈路的路由器計算公式為：

（ + 1） = [（） + （ ）]+ （6）

式中，鏈路上全部用戶速率之和為，步長為。

2 基于阻尼牛頓法的擁塞速率控制算法

文獻[1]，[2]中采用式（6）的梯度下降法進行鏈路價格的計算，但梯度下降法存在收斂速度慢的缺點，Internet網絡流量變化較快，要想較好地實現擁塞速率控制，必須提高擁塞控制算法的計算速度，阻尼牛頓法既保持了牛頓法快速收斂的優點，極值點又不敏感于初始數值的選取。為此，本文提出一種基于阻尼牛頓法的擁塞速率控制算法，算法描述如下。

已知目標函數（）及其梯度 （），問題的維數，終止限。選取初始點， = 0，給定終止限>0。

（1）計算 （），若|| （）||≤，停止迭代，輸出，否則， 轉到步驟（2）。

（2）計算[ 2（）]-1以及 = [ 2（）]-1 （）。

（3）沿進行搜索來求取步長。

（4）令 = + ， = + 1，返回（1）。

用戶的最優擁塞速率為：

（ + 1） = （（ + 1）） （7）

3 仿真試驗

為了對本文所提出的算法進行驗證，該算法在NS2網絡仿真器[4]進行了編程實現，并與基于梯度下降法進行性能仿真對比，圖1為試驗用網絡拓撲。

圖1 試驗用網絡拓撲

試驗用網絡拓撲中存在兩個數據流，數據流1：S1-D1，數據流2：S2-D2，分組長度大小為1024字節。路由器R1與R2之間的傳輸速度為100Mb/s，時延大小為15ms，緩沖區容許最大分組個數為250。發送方與路由器R1之間的傳輸速度為100Mb/s，時延大小為10ms。接收方與路由器R2之間傳輸速度為100Mb/s，時延大小為10ms。

（下轉第82頁）（上接第58頁）

圖2 兩種算法速率對比

仿真時間為50秒，數據流1使用梯度下降法來計算鏈路價格，數據流2使用阻尼牛頓法來計算鏈路價格， = 0.001。兩個數據流連接的最優擁塞速率如圖2所示。

仿真結果表明，使用基于阻尼牛頓法的擁塞速率控制算法，數據流的最優速率以及鏈路價格具有更快的收斂速度，本文所提出的算法性能明顯優于基于梯度下降法的鏈路價格計算算法。

4 結論

文獻[1]，[2]中所提出的最優速率模型采用了梯度下降法來計算鏈路價格，但梯度下降法存在收斂速度慢的缺點。Internet網絡流量變化較快，要想較好地實現擁塞速率控制，必須提高擁塞控制算法的計算速度。為此，本文使用阻尼牛頓法來進行鏈路價格的計算，提出一種基于阻尼牛頓法的擁塞速率控制算法，仿真結果表明，本文所提出的算法具有更快的收斂速度，算法性能優于基于梯度下降法的鏈路價格計算算法。

參考文獻

[1] S. Bhandarkar， S. Jain， A.N. Reddy LTCP： a layering technique for improving the performance of TCP in highspeed networks[R].INTERNET DRAFT： draft bhandarkar -ltcp-01.txt，2004.

[2] D. Katabi， M. Handley， C. Rohrs. Congestion control for high bandwidth delay product networks [J].Computer Communications Review，2002.32（4）：89-102.

[3] 陳秀琴.修正阻尼牛頓算法[J].科技信息，2009（1）.

[4] Ns-2.Network Simulator.http：//www.isi.edu/nsnam/ns.endprint

摘 要 本文使用阻尼牛頓法來進行鏈路價格的計算，提出一種基于阻尼牛頓法的擁塞速率控制算法，仿真結果表明，本文所提出的算法具有更快的收斂速度，算法性能優于基于梯度下降法的鏈路價格計算算法。

關鍵詞 擁塞 速率控制 阻尼牛頓法

中圖分類號：TP393 文獻標識碼：A

Congestion Rate Control Algorithm Based on Damping Newton Method

HUANG Yutao

（Nanjing Foreign Language School in Xianlin， Nanjing， Jiangsu 210007）

Abstract This paper present a congestion rate control algorithm based on damping Newton method to calculate link price. The simulation results show that the algorithm is superior to the algorithm based on gradient descent method with more rapid speed.

Key words Congestion； Rate Control； Damping Newton Method

0 引言

擁塞速率控制對于提高計算機的網絡性能具有重要作用。文獻[1]，[2]將網絡擁塞度量表示為鏈路價格，建立了進行理論分析的最優速率模型。該模型使用非線性優化模型來求取各個用戶的最優發送速率，奠定了使用鏈路價格對網絡擁塞控制進行研究的基礎。

然而，文獻[1]，[2]中所提出的最優速率模型采用了梯度下降法來計算鏈路價格，但梯度下降法存在收斂速度慢的缺點。阻尼牛頓法既保持了牛頓法快速收斂的優點，極值點又不敏感于初始數值的選取。因此，本文提出一種使用阻尼牛頓法[3]來計算鏈路價格的擁塞速率控制算法。

1 最優速率模型

最優速率模型中，為用戶連接分配的速率，（）為的效用值，優化的目標函數為：（） （1）

約束條件為：≤，≥0 （2）

公式中，為鏈路的帶寬，數據流的集合為。

公式（1）、（2）為約束優化問題，將約束優化轉化為無約束優化：（） = （）（） （3）

基于梯度下降法，用戶最優速率的求取：

= （） = （） = 0 （4）

式中，用戶鏈路價格和為。

發送方計算公式為： = （） （5）

每個鏈路的路由器計算公式為：

（ + 1） = [（） + （ ）]+ （6）

式中，鏈路上全部用戶速率之和為，步長為。

2 基于阻尼牛頓法的擁塞速率控制算法

文獻[1]，[2]中采用式（6）的梯度下降法進行鏈路價格的計算，但梯度下降法存在收斂速度慢的缺點，Internet網絡流量變化較快，要想較好地實現擁塞速率控制，必須提高擁塞控制算法的計算速度，阻尼牛頓法既保持了牛頓法快速收斂的優點，極值點又不敏感于初始數值的選取。為此，本文提出一種基于阻尼牛頓法的擁塞速率控制算法，算法描述如下。

已知目標函數（）及其梯度 （），問題的維數，終止限。選取初始點， = 0，給定終止限>0。

（1）計算 （），若|| （）||≤，停止迭代，輸出，否則， 轉到步驟（2）。

（2）計算[ 2（）]-1以及 = [ 2（）]-1 （）。

（3）沿進行搜索來求取步長。

（4）令 = + ， = + 1，返回（1）。

用戶的最優擁塞速率為：

（ + 1） = （（ + 1）） （7）

3 仿真試驗

為了對本文所提出的算法進行驗證，該算法在NS2網絡仿真器[4]進行了編程實現，并與基于梯度下降法進行性能仿真對比，圖1為試驗用網絡拓撲。

圖1 試驗用網絡拓撲

試驗用網絡拓撲中存在兩個數據流，數據流1：S1-D1，數據流2：S2-D2，分組長度大小為1024字節。路由器R1與R2之間的傳輸速度為100Mb/s，時延大小為15ms，緩沖區容許最大分組個數為250。發送方與路由器R1之間的傳輸速度為100Mb/s，時延大小為10ms。接收方與路由器R2之間傳輸速度為100Mb/s，時延大小為10ms。

（下轉第82頁）（上接第58頁）

圖2 兩種算法速率對比

仿真時間為50秒，數據流1使用梯度下降法來計算鏈路價格，數據流2使用阻尼牛頓法來計算鏈路價格， = 0.001。兩個數據流連接的最優擁塞速率如圖2所示。

仿真結果表明，使用基于阻尼牛頓法的擁塞速率控制算法，數據流的最優速率以及鏈路價格具有更快的收斂速度，本文所提出的算法性能明顯優于基于梯度下降法的鏈路價格計算算法。

4 結論

文獻[1]，[2]中所提出的最優速率模型采用了梯度下降法來計算鏈路價格，但梯度下降法存在收斂速度慢的缺點。Internet網絡流量變化較快，要想較好地實現擁塞速率控制，必須提高擁塞控制算法的計算速度。為此，本文使用阻尼牛頓法來進行鏈路價格的計算，提出一種基于阻尼牛頓法的擁塞速率控制算法，仿真結果表明，本文所提出的算法具有更快的收斂速度，算法性能優于基于梯度下降法的鏈路價格計算算法。

參考文獻

[1] S. Bhandarkar， S. Jain， A.N. Reddy LTCP： a layering technique for improving the performance of TCP in highspeed networks[R].INTERNET DRAFT： draft bhandarkar -ltcp-01.txt，2004.

[2] D. Katabi， M. Handley， C. Rohrs. Congestion control for high bandwidth delay product networks [J].Computer Communications Review，2002.32（4）：89-102.

[3] 陳秀琴.修正阻尼牛頓算法[J].科技信息，2009（1）.

[4] Ns-2.Network Simulator.http：//www.isi.edu/nsnam/ns.endprint

摘 要 本文使用阻尼牛頓法來進行鏈路價格的計算，提出一種基于阻尼牛頓法的擁塞速率控制算法，仿真結果表明，本文所提出的算法具有更快的收斂速度，算法性能優于基于梯度下降法的鏈路價格計算算法。

關鍵詞 擁塞 速率控制 阻尼牛頓法

中圖分類號：TP393 文獻標識碼：A

Congestion Rate Control Algorithm Based on Damping Newton Method

HUANG Yutao

（Nanjing Foreign Language School in Xianlin， Nanjing， Jiangsu 210007）

Abstract This paper present a congestion rate control algorithm based on damping Newton method to calculate link price. The simulation results show that the algorithm is superior to the algorithm based on gradient descent method with more rapid speed.

Key words Congestion； Rate Control； Damping Newton Method

0 引言

擁塞速率控制對于提高計算機的網絡性能具有重要作用。文獻[1]，[2]將網絡擁塞度量表示為鏈路價格，建立了進行理論分析的最優速率模型。該模型使用非線性優化模型來求取各個用戶的最優發送速率，奠定了使用鏈路價格對網絡擁塞控制進行研究的基礎。

然而，文獻[1]，[2]中所提出的最優速率模型采用了梯度下降法來計算鏈路價格，但梯度下降法存在收斂速度慢的缺點。阻尼牛頓法既保持了牛頓法快速收斂的優點，極值點又不敏感于初始數值的選取。因此，本文提出一種使用阻尼牛頓法[3]來計算鏈路價格的擁塞速率控制算法。

1 最優速率模型

最優速率模型中，為用戶連接分配的速率，（）為的效用值，優化的目標函數為：（） （1）

約束條件為：≤，≥0 （2）

公式中，為鏈路的帶寬，數據流的集合為。

公式（1）、（2）為約束優化問題，將約束優化轉化為無約束優化：（） = （）（） （3）

基于梯度下降法，用戶最優速率的求?。?/p>

= （） = （） = 0 （4）

式中，用戶鏈路價格和為。

發送方計算公式為： = （） （5）

每個鏈路的路由器計算公式為：

（ + 1） = [（） + （ ）]+ （6）

式中，鏈路上全部用戶速率之和為，步長為。

2 基于阻尼牛頓法的擁塞速率控制算法

文獻[1]，[2]中采用式（6）的梯度下降法進行鏈路價格的計算，但梯度下降法存在收斂速度慢的缺點，Internet網絡流量變化較快，要想較好地實現擁塞速率控制，必須提高擁塞控制算法的計算速度，阻尼牛頓法既保持了牛頓法快速收斂的優點，極值點又不敏感于初始數值的選取。為此，本文提出一種基于阻尼牛頓法的擁塞速率控制算法，算法描述如下。

已知目標函數（）及其梯度 （），問題的維數，終止限。選取初始點， = 0，給定終止限>0。

（1）計算 （），若|| （）||≤，停止迭代，輸出，否則， 轉到步驟（2）。

（2）計算[ 2（）]-1以及 = [ 2（）]-1 （）。

（3）沿進行搜索來求取步長。

（4）令 = + ， = + 1，返回（1）。

用戶的最優擁塞速率為：

（ + 1） = （（ + 1）） （7）

3 仿真試驗

為了對本文所提出的算法進行驗證，該算法在NS2網絡仿真器[4]進行了編程實現，并與基于梯度下降法進行性能仿真對比，圖1為試驗用網絡拓撲。

圖1 試驗用網絡拓撲

試驗用網絡拓撲中存在兩個數據流，數據流1：S1-D1，數據流2：S2-D2，分組長度大小為1024字節。路由器R1與R2之間的傳輸速度為100Mb/s，時延大小為15ms，緩沖區容許最大分組個數為250。發送方與路由器R1之間的傳輸速度為100Mb/s，時延大小為10ms。接收方與路由器R2之間傳輸速度為100Mb/s，時延大小為10ms。

（下轉第82頁）（上接第58頁）

圖2 兩種算法速率對比

仿真時間為50秒，數據流1使用梯度下降法來計算鏈路價格，數據流2使用阻尼牛頓法來計算鏈路價格， = 0.001。兩個數據流連接的最優擁塞速率如圖2所示。

仿真結果表明，使用基于阻尼牛頓法的擁塞速率控制算法，數據流的最優速率以及鏈路價格具有更快的收斂速度，本文所提出的算法性能明顯優于基于梯度下降法的鏈路價格計算算法。

4 結論

文獻[1]，[2]中所提出的最優速率模型采用了梯度下降法來計算鏈路價格，但梯度下降法存在收斂速度慢的缺點。Internet網絡流量變化較快，要想較好地實現擁塞速率控制，必須提高擁塞控制算法的計算速度。為此，本文使用阻尼牛頓法來進行鏈路價格的計算，提出一種基于阻尼牛頓法的擁塞速率控制算法，仿真結果表明，本文所提出的算法具有更快的收斂速度，算法性能優于基于梯度下降法的鏈路價格計算算法。

參考文獻

[1] S. Bhandarkar， S. Jain， A.N. Reddy LTCP： a layering technique for improving the performance of TCP in highspeed networks[R].INTERNET DRAFT： draft bhandarkar -ltcp-01.txt，2004.

[2] D. Katabi， M. Handley， C. Rohrs. Congestion control for high bandwidth delay product networks [J].Computer Communications Review，2002.32（4）：89-102.

[3] 陳秀琴.修正阻尼牛頓算法[J].科技信息，2009（1）.

[4] Ns-2.Network Simulator.http：//www.isi.edu/nsnam/ns.endprint