Chen Yongxin, Georgiou Tryphon T, Pavon Michele, Tannenbaum Allen
School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA 30332.
Department of Mechanical and Aerospace Engineering, University of California, Irvine, CA 92697, USA.
IEEE Trans Control Netw Syst. 2020 Jun;7(2):923-931. doi: 10.1109/tcns.2019.2935623. Epub 2019 Aug 15.
We seek network routing towards a desired final distribution that can mediate possible random link failures. In other words, we seek a routing plan that utilizes alternative routes so as to be relatively robust to link failures. To this end, we provide a mathematical formulation of a relaxed transport problem where the final distribution only needs to be close to the desired one. The problem is cast as a maximum entropy problem for probability distributions on paths with an added terminal cost. The entropic regularizing penalty aims at distributing the choice of paths amongst possible alternatives. We prove that the unique solution may be obtained by solving a of equations. An iterative algorithm to compute the solution is provided. Each iteration of the algorithm contracts the distance (in the Hilbert metric) to the optimal solution by more than 1/2, leading to extremely fast convergence.
我们寻求朝着期望的最终分布进行网络路由，该分布能够应对可能出现的随机链路故障。换句话说，我们寻求一种路由方案，该方案利用备用路由，从而对链路故障具有相对较强的鲁棒性。为此，我们给出了一个松弛传输问题的数学公式，其中最终分布仅需接近期望分布。该问题被转化为一个关于路径上概率分布的最大熵问题，并附加了终端成本。熵正则化惩罚旨在在可能的替代方案中分配路径选择。我们证明可以通过求解一组方程得到唯一解。提供了一种用于计算解的迭代算法。该算法的每次迭代都会使到最优解的距离（在希尔伯特度量下）收缩超过1/2，从而实现极快的收敛。
