基于阻尼牛頓法的擁塞速率控制算法
2014-12-29 13:00:44黃玉濤
科教導(dǎo)刊 2014年36期
黃玉濤
摘 要 本文使用阻尼牛頓法來進(jìn)行鏈路價格的計(jì)算，提出一種基于阻尼牛頓法的擁塞速率控制算法，仿真結(jié)果表明，本文所提出的算法具有更快的收斂速度，算法性能優(yōu)于基于梯度下降法的鏈路價格計(jì)算算法。
關(guān)鍵詞 擁塞 速率控制 阻尼牛頓法
中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：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 引言
擁塞速率控制對于提高計(jì)算機(jī)的網(wǎng)絡(luò)性能具有重要作用。文獻(xiàn)[1]，[2]將網(wǎng)絡(luò)擁塞度量表示為鏈路價格，建立了進(jìn)行理論分析的最優(yōu)速率模型。該模型使用非線性優(yōu)化模型來求取各個用戶的最優(yōu)發(fā)送速率，奠定了使用鏈路價格對網(wǎng)絡(luò)擁塞控制進(jìn)行研究的基礎(chǔ)。
然而，文獻(xiàn)[1]，[2]中所提出的最優(yōu)速率模型采用了梯度下降法來計(jì)算鏈路價格，但梯度下降法存在收斂速度慢的缺點(diǎn)。阻尼牛頓法既保持了牛頓法快速收斂的優(yōu)點(diǎn)，極值點(diǎn)又不敏感于初始數(shù)值的選取。因此，本文提出一種使用阻尼牛頓法[3]來計(jì)算鏈路價格的擁塞速率控制算法。
1 最優(yōu)速率模型
最優(yōu)速率模型中，為用戶連接分配的速率，（）為的效用值，優(yōu)化的目標(biāo)函數(shù)為：（） （1）
約束條件為：≤，≥0 （2）
公式中，為鏈路的帶寬，數(shù)據(jù)流的集合為。
公式（1）、（2）為約束優(yōu)化問題，將約束優(yōu)化轉(zhuǎn)化為無約束優(yōu)化：（） = （）（） （3）
基于梯度下降法，用戶最優(yōu)速率的求取：
= （） = （） = 0 （4）
式中，用戶鏈路價格和為。
發(fā)送方計(jì)算公式為： = （） （5）
每個鏈路的路由器計(jì)算公式為：
（ + 1） = [（） + （ ）]+ （6）
式中，鏈路上全部用戶速率之和為，步長為。
2 基于阻尼牛頓法的擁塞速率控制算法
文獻(xiàn)[1]，[2]中采用式（6）的梯度下降法進(jìn)行鏈路價格的計(jì)算，但梯度下降法存在收斂速度慢的缺點(diǎn)，Internet網(wǎng)絡(luò)流量變化較快，要想較好地實(shí)現(xiàn)擁塞速率控制，必須提高擁塞控制算法的計(jì)算速度，阻尼牛頓法既保持了牛頓法快速收斂的優(yōu)點(diǎn)，極值點(diǎn)又不敏感于初始數(shù)值的選取。為此，本文提出一種基于阻尼牛頓法的擁塞速率控制算法，算法描述如下。
已知目標(biāo)函數(shù)（）及其梯度 （），問題的維數(shù)，終止限。選取初始點(diǎn)， = 0，給定終止限>0。
（1）計(jì)算 （），若|| （）||≤，停止迭代，輸出，否則， 轉(zhuǎn)到步驟（2）。
（2）計(jì)算[ 2（）]-1以及 = [ 2（）]-1 （）。
（3）沿進(jìn)行搜索來求取步長。
（4）令 = + ， = + 1，返回（1）。
用戶的最優(yōu)擁塞速率為：
（ + 1） = （（ + 1）） （7）
3 仿真試驗(yàn)
為了對本文所提出的算法進(jìn)行驗(yàn)證，該算法在NS2網(wǎng)絡(luò)仿真器[4]進(jìn)行了編程實(shí)現(xiàn)，并與基于梯度下降法進(jìn)行性能仿真對比，圖1為試驗(yàn)用網(wǎng)絡(luò)拓?fù)洹?/p>
圖1 試驗(yàn)用網(wǎng)絡(luò)拓?fù)?/p>
試驗(yàn)用網(wǎng)絡(luò)拓?fù)渲写嬖趦蓚€數(shù)據(jù)流，數(shù)據(jù)流1：S1-D1，數(shù)據(jù)流2：S2-D2，分組長度大小為1024字節(jié)。路由器R1與R2之間的傳輸速度為100Mb/s，時延大小為15ms，緩沖區(qū)容許最大分組個數(shù)為250。發(fā)送方與路由器R1之間的傳輸速度為100Mb/s，時延大小為10ms。接收方與路由器R2之間傳輸速度為100Mb/s，時延大小為10ms。
（下轉(zhuǎn)第82頁）（上接第58頁）
圖2 兩種算法速率對比
仿真時間為50秒，數(shù)據(jù)流1使用梯度下降法來計(jì)算鏈路價格，數(shù)據(jù)流2使用阻尼牛頓法來計(jì)算鏈路價格， = 0.001。兩個數(shù)據(jù)流連接的最優(yōu)擁塞速率如圖2所示。
仿真結(jié)果表明，使用基于阻尼牛頓法的擁塞速率控制算法，數(shù)據(jù)流的最優(yōu)速率以及鏈路價格具有更快的收斂速度，本文所提出的算法性能明顯優(yōu)于基于梯度下降法的鏈路價格計(jì)算算法。
4 結(jié)論
文獻(xiàn)[1]，[2]中所提出的最優(yōu)速率模型采用了梯度下降法來計(jì)算鏈路價格，但梯度下降法存在收斂速度慢的缺點(diǎn)。Internet網(wǎng)絡(luò)流量變化較快，要想較好地實(shí)現(xiàn)擁塞速率控制，必須提高擁塞控制算法的計(jì)算速度。為此，本文使用阻尼牛頓法來進(jìn)行鏈路價格的計(jì)算，提出一種基于阻尼牛頓法的擁塞速率控制算法，仿真結(jié)果表明，本文所提出的算法具有更快的收斂速度，算法性能優(yōu)于基于梯度下降法的鏈路價格計(jì)算算法。
參考文獻(xiàn)
[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
摘 要 本文使用阻尼牛頓法來進(jìn)行鏈路價格的計(jì)算，提出一種基于阻尼牛頓法的擁塞速率控制算法，仿真結(jié)果表明，本文所提出的算法具有更快的收斂速度，算法性能優(yōu)于基于梯度下降法的鏈路價格計(jì)算算法。
關(guān)鍵詞 擁塞 速率控制 阻尼牛頓法
中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：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 引言
擁塞速率控制對于提高計(jì)算機(jī)的網(wǎng)絡(luò)性能具有重要作用。文獻(xiàn)[1]，[2]將網(wǎng)絡(luò)擁塞度量表示為鏈路價格，建立了進(jìn)行理論分析的最優(yōu)速率模型。該模型使用非線性優(yōu)化模型來求取各個用戶的最優(yōu)發(fā)送速率，奠定了使用鏈路價格對網(wǎng)絡(luò)擁塞控制進(jìn)行研究的基礎(chǔ)。
然而，文獻(xiàn)[1]，[2]中所提出的最優(yōu)速率模型采用了梯度下降法來計(jì)算鏈路價格，但梯度下降法存在收斂速度慢的缺點(diǎn)。阻尼牛頓法既保持了牛頓法快速收斂的優(yōu)點(diǎn)，極值點(diǎn)又不敏感于初始數(shù)值的選取。因此，本文提出一種使用阻尼牛頓法[3]來計(jì)算鏈路價格的擁塞速率控制算法。
1 最優(yōu)速率模型
最優(yōu)速率模型中，為用戶連接分配的速率，（）為的效用值，優(yōu)化的目標(biāo)函數(shù)為：（） （1）
約束條件為：≤，≥0 （2）
公式中，為鏈路的帶寬，數(shù)據(jù)流的集合為。
公式（1）、（2）為約束優(yōu)化問題，將約束優(yōu)化轉(zhuǎn)化為無約束優(yōu)化：（） = （）（） （3）
基于梯度下降法，用戶最優(yōu)速率的求?。?/p>
= （） = （） = 0 （4）
式中，用戶鏈路價格和為。
發(fā)送方計(jì)算公式為： = （） （5）
每個鏈路的路由器計(jì)算公式為：
（ + 1） = [（） + （ ）]+ （6）
式中，鏈路上全部用戶速率之和為，步長為。
2 基于阻尼牛頓法的擁塞速率控制算法
文獻(xiàn)[1]，[2]中采用式（6）的梯度下降法進(jìn)行鏈路價格的計(jì)算，但梯度下降法存在收斂速度慢的缺點(diǎn)，Internet網(wǎng)絡(luò)流量變化較快，要想較好地實(shí)現(xiàn)擁塞速率控制，必須提高擁塞控制算法的計(jì)算速度，阻尼牛頓法既保持了牛頓法快速收斂的優(yōu)點(diǎn)，極值點(diǎn)又不敏感于初始數(shù)值的選取。為此，本文提出一種基于阻尼牛頓法的擁塞速率控制算法，算法描述如下。
已知目標(biāo)函數(shù)（）及其梯度 （），問題的維數(shù)，終止限。選取初始點(diǎn)， = 0，給定終止限>0。
（1）計(jì)算 （），若|| （）||≤，停止迭代，輸出，否則， 轉(zhuǎn)到步驟（2）。
（2）計(jì)算[ 2（）]-1以及 = [ 2（）]-1 （）。
（3）沿進(jìn)行搜索來求取步長。
（4）令 = + ， = + 1，返回（1）。
用戶的最優(yōu)擁塞速率為：
（ + 1） = （（ + 1）） （7）
3 仿真試驗(yàn)
為了對本文所提出的算法進(jìn)行驗(yàn)證，該算法在NS2網(wǎng)絡(luò)仿真器[4]進(jìn)行了編程實(shí)現(xiàn)，并與基于梯度下降法進(jìn)行性能仿真對比，圖1為試驗(yàn)用網(wǎng)絡(luò)拓?fù)洹?/p>
圖1 試驗(yàn)用網(wǎng)絡(luò)拓?fù)?/p>
試驗(yàn)用網(wǎng)絡(luò)拓?fù)渲写嬖趦蓚€數(shù)據(jù)流，數(shù)據(jù)流1：S1-D1，數(shù)據(jù)流2：S2-D2，分組長度大小為1024字節(jié)。路由器R1與R2之間的傳輸速度為100Mb/s，時延大小為15ms，緩沖區(qū)容許最大分組個數(shù)為250。發(fā)送方與路由器R1之間的傳輸速度為100Mb/s，時延大小為10ms。接收方與路由器R2之間傳輸速度為100Mb/s，時延大小為10ms。
（下轉(zhuǎn)第82頁）（上接第58頁）
圖2 兩種算法速率對比
仿真時間為50秒，數(shù)據(jù)流1使用梯度下降法來計(jì)算鏈路價格，數(shù)據(jù)流2使用阻尼牛頓法來計(jì)算鏈路價格， = 0.001。兩個數(shù)據(jù)流連接的最優(yōu)擁塞速率如圖2所示。
仿真結(jié)果表明，使用基于阻尼牛頓法的擁塞速率控制算法，數(shù)據(jù)流的最優(yōu)速率以及鏈路價格具有更快的收斂速度，本文所提出的算法性能明顯優(yōu)于基于梯度下降法的鏈路價格計(jì)算算法。
4 結(jié)論
文獻(xiàn)[1]，[2]中所提出的最優(yōu)速率模型采用了梯度下降法來計(jì)算鏈路價格，但梯度下降法存在收斂速度慢的缺點(diǎn)。Internet網(wǎng)絡(luò)流量變化較快，要想較好地實(shí)現(xiàn)擁塞速率控制，必須提高擁塞控制算法的計(jì)算速度。為此，本文使用阻尼牛頓法來進(jìn)行鏈路價格的計(jì)算，提出一種基于阻尼牛頓法的擁塞速率控制算法，仿真結(jié)果表明，本文所提出的算法具有更快的收斂速度，算法性能優(yōu)于基于梯度下降法的鏈路價格計(jì)算算法。
參考文獻(xiàn)
[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
摘 要 本文使用阻尼牛頓法來進(jìn)行鏈路價格的計(jì)算，提出一種基于阻尼牛頓法的擁塞速率控制算法，仿真結(jié)果表明，本文所提出的算法具有更快的收斂速度，算法性能優(yōu)于基于梯度下降法的鏈路價格計(jì)算算法。
關(guān)鍵詞 擁塞 速率控制 阻尼牛頓法
中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：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 引言
擁塞速率控制對于提高計(jì)算機(jī)的網(wǎng)絡(luò)性能具有重要作用。文獻(xiàn)[1]，[2]將網(wǎng)絡(luò)擁塞度量表示為鏈路價格，建立了進(jìn)行理論分析的最優(yōu)速率模型。該模型使用非線性優(yōu)化模型來求取各個用戶的最優(yōu)發(fā)送速率，奠定了使用鏈路價格對網(wǎng)絡(luò)擁塞控制進(jìn)行研究的基礎(chǔ)。
然而，文獻(xiàn)[1]，[2]中所提出的最優(yōu)速率模型采用了梯度下降法來計(jì)算鏈路價格，但梯度下降法存在收斂速度慢的缺點(diǎn)。阻尼牛頓法既保持了牛頓法快速收斂的優(yōu)點(diǎn)，極值點(diǎn)又不敏感于初始數(shù)值的選取。因此，本文提出一種使用阻尼牛頓法[3]來計(jì)算鏈路價格的擁塞速率控制算法。
1 最優(yōu)速率模型
最優(yōu)速率模型中，為用戶連接分配的速率，（）為的效用值，優(yōu)化的目標(biāo)函數(shù)為：（） （1）
約束條件為：≤，≥0 （2）
公式中，為鏈路的帶寬，數(shù)據(jù)流的集合為。
公式（1）、（2）為約束優(yōu)化問題，將約束優(yōu)化轉(zhuǎn)化為無約束優(yōu)化：（） = （）（） （3）
基于梯度下降法，用戶最優(yōu)速率的求取：
= （） = （） = 0 （4）
式中，用戶鏈路價格和為。
發(fā)送方計(jì)算公式為： = （） （5）
每個鏈路的路由器計(jì)算公式為：
（ + 1） = [（） + （ ）]+ （6）
式中，鏈路上全部用戶速率之和為，步長為。
2 基于阻尼牛頓法的擁塞速率控制算法
文獻(xiàn)[1]，[2]中采用式（6）的梯度下降法進(jìn)行鏈路價格的計(jì)算，但梯度下降法存在收斂速度慢的缺點(diǎn)，Internet網(wǎng)絡(luò)流量變化較快，要想較好地實(shí)現(xiàn)擁塞速率控制，必須提高擁塞控制算法的計(jì)算速度，阻尼牛頓法既保持了牛頓法快速收斂的優(yōu)點(diǎn)，極值點(diǎn)又不敏感于初始數(shù)值的選取。為此，本文提出一種基于阻尼牛頓法的擁塞速率控制算法，算法描述如下。
已知目標(biāo)函數(shù)（）及其梯度 （），問題的維數(shù)，終止限。選取初始點(diǎn)， = 0，給定終止限>0。
（1）計(jì)算 （），若|| （）||≤，停止迭代，輸出，否則， 轉(zhuǎn)到步驟（2）。
（2）計(jì)算[ 2（）]-1以及 = [ 2（）]-1 （）。
（3）沿進(jìn)行搜索來求取步長。
（4）令 = + ， = + 1，返回（1）。
用戶的最優(yōu)擁塞速率為：
（ + 1） = （（ + 1）） （7）
3 仿真試驗(yàn)
為了對本文所提出的算法進(jìn)行驗(yàn)證，該算法在NS2網(wǎng)絡(luò)仿真器[4]進(jìn)行了編程實(shí)現(xiàn)，并與基于梯度下降法進(jìn)行性能仿真對比，圖1為試驗(yàn)用網(wǎng)絡(luò)拓?fù)洹?/p>
圖1 試驗(yàn)用網(wǎng)絡(luò)拓?fù)?/p>
試驗(yàn)用網(wǎng)絡(luò)拓?fù)渲写嬖趦蓚€數(shù)據(jù)流，數(shù)據(jù)流1：S1-D1，數(shù)據(jù)流2：S2-D2，分組長度大小為1024字節(jié)。路由器R1與R2之間的傳輸速度為100Mb/s，時延大小為15ms，緩沖區(qū)容許最大分組個數(shù)為250。發(fā)送方與路由器R1之間的傳輸速度為100Mb/s，時延大小為10ms。接收方與路由器R2之間傳輸速度為100Mb/s，時延大小為10ms。
（下轉(zhuǎn)第82頁）（上接第58頁）
圖2 兩種算法速率對比
仿真時間為50秒，數(shù)據(jù)流1使用梯度下降法來計(jì)算鏈路價格，數(shù)據(jù)流2使用阻尼牛頓法來計(jì)算鏈路價格， = 0.001。兩個數(shù)據(jù)流連接的最優(yōu)擁塞速率如圖2所示。
仿真結(jié)果表明，使用基于阻尼牛頓法的擁塞速率控制算法，數(shù)據(jù)流的最優(yōu)速率以及鏈路價格具有更快的收斂速度，本文所提出的算法性能明顯優(yōu)于基于梯度下降法的鏈路價格計(jì)算算法。
4 結(jié)論
文獻(xiàn)[1]，[2]中所提出的最優(yōu)速率模型采用了梯度下降法來計(jì)算鏈路價格，但梯度下降法存在收斂速度慢的缺點(diǎn)。Internet網(wǎng)絡(luò)流量變化較快，要想較好地實(shí)現(xiàn)擁塞速率控制，必須提高擁塞控制算法的計(jì)算速度。為此，本文使用阻尼牛頓法來進(jìn)行鏈路價格的計(jì)算，提出一種基于阻尼牛頓法的擁塞速率控制算法，仿真結(jié)果表明，本文所提出的算法具有更快的收斂速度，算法性能優(yōu)于基于梯度下降法的鏈路價格計(jì)算算法。
參考文獻(xiàn)
[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
