摘要
基于最小集覆盖理论的拥塞链路推理算法,仅对共享瓶颈链路进行推理,当拥塞路径存在多条链路拥塞时,算法的推理性能急剧下降.针对该问题,提出一种基于贝叶斯最大后验(Bayesian maximum a-posterior,简称BMAP)改进的拉格朗日松弛次梯度推理算法(Lagrange relaxation sub-gradient algorithm based on BMAP,简称LRSBMAP).针对推理算法中链路覆盖范围对算法推理性能的影响,以及探针部署及额外E2E路径探测发包的开销问题,提出设置度阈值(degree threshold value,简称DTV)参数预选待测IP网络收发包路由器节点,通过引入优选系数?,在保证链路覆盖范围的基础上,兼顾开销问题,确保算法的推理性能.针对大规模IP网络多链路拥塞场景下,链路先验概率求解方程组系数矩阵的稀疏性,提出一种对称逐次超松弛(symmetry successive over-relaxation,简称SSOR)分裂预处理共轭梯度法(preconditioned conjugate gradient method based on SSOR,简称PCG_SSOR)求解链路先验概率近似唯一解的方法,防止算法求解失败.实验验证了所提算法的准确性及鲁棒性.
Congested link inference algorithms only infer the set of share links based on methods of smallest set coverage. When some congested path contains more than one congested link, the inference performance is obviously descending. Aiming at this problem, a version of Lagrange relaxation sub-gradient algorithm based on Bayesian maximum a-posterior （LRSBMAP） is proposed. Aiming at the impacts of congested link inference performance in the different link coverage, and the cost problems of probe deployments and additional E2E active detection, the paper proposes a preliminary selection method for transceiver nodes by optimally selecting degree threshold value （DTV） parameter of IP networks. Through introducing the optimization coefficient ρ, problems of cost and link coverage can be both considered to ensure the performance of inference algorithm. In addition, according to the sparsity of coefficient matrix in link prior probability solution equations, a preconditioned conjugate gradient method based on symmetry successive over-relaxation （PCG_SSOR） is proposed to obtain approximate unique solutions, helping to avoid the solution failures in large scale IP networks under the scenarios of multiple link congestion. Experiments demonstrate that the algorithms proposed in this paper have higher accuracy and robustness
出处
《软件学报》
EI
CSCD
北大核心
2017年第7期1815-1834,共20页
Journal of Software
基金
国家重点基础研究发展计划(973)(2012CB315901
2013CB329104)
河南省高等学校重点科研项目(18A510019)~~
