基于阻尼牛顿法的拥塞速率控制算法
2014-12-29 13:00黄玉涛
科教导刊 2014年36期
黄玉涛
摘 要 本文使用阻尼牛顿法来进行链路价格的计算，提出一种基于阻尼牛顿法的拥塞速率控制算法，仿真结果表明，本文所提出的算法具有更快的收敛速度，算法性能优于基于梯度下降法的链路价格计算算法。
关键词 拥塞 速率控制 阻尼牛顿法
中图分类号：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）
基于梯度下降法，用户最优速率的求取：
= （） = （） = 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
