학술논문
Relaxed Schrödinger Bridges and Robust Network Routing
Document Type
Periodical
Author
Source
IEEE Transactions on Control of Network Systems IEEE Trans. Control Netw. Syst. Control of Network Systems, IEEE Transactions on. 7(2):923-931 Jun, 2020
Subject
Language
ISSN
2325-5870
2372-2533
2372-2533
Abstract
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 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 generalized Schrödinger system 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.