● 摘要
流量工程技术是利用网络流量信息调节网络流量的分布，从而优化某些性能指标的技术．由于网络中转发节点数目的庞大，流量工程问题的规模往往也是很庞大的. 因此如何利用问题的特点设计高效算法是流量工程应用的前提. 本文考虑了流量工程中目标函数为最大弧利用率和M/M/1 延迟函数的逐段线性近似的流量工程问题（分别简称为MAU-TEP 和FT-TEP），针对与这两类问题等价的线性规划问题本文做了以下三方面的工作．首先，我们选用著名的邻近解析中心削平面法. 该方法在每次迭代的过程中利用邻近解析中心削平面法求解等价线性规划问题的拉格朗日对偶问题，并且利用Dijkstra 最短路径算法求出原始变量. 此外，我们根据流量工程问题的特点，采用积极集策略降低对偶问题的规模，从而加速算法的收敛速度.其次，我们设计一种特殊的原始-对偶内点法. 尽管一般的内点法对求解线性大规模问题是有效的，但由于流量工程问题本身的特点，导致一般内点法在求解此类问题时效率往往很低. 为了克服这个缺点，我们利用流量工程问题的结构特点，在求解牛顿方向时运用分块技术，结合共轭梯度法和稀疏Cholesky 分解技术来降低待求解线性方程组的规模. 从而达到加速算法的效果.最后，数值仿真结果表明算法是可行的，对于一些问题算法也是有效的，并指出了有可能提高算法效率的一些措施.
相关内容
相关标签