CUED Publications database

Stability and instability in primal-dual algorithms for multi-path routing

Holding, T and Lestas, I (2015) Stability and instability in primal-dual algorithms for multi-path routing. In: UNSPECIFIED pp. 1651-1656..

Full text not available from this repository.


We consider a problem of multi-path routing in a communication network, where flow control is implemented with a prescribed number of routes available for each source/destination pair. A classical approach is to formulate this as a network optimization problem where decentralized update rules converge to its optimal solution. It has been reported in the literature that the problem is in this case not strictly convex leading to oscillatory behaviours when classical primal/dual dynamics are implemented. In this paper we show that the use of appropriate higher order dynamics, which are fully localized, can provide guarantees for convergence to the optimal solution. Furthermore, we show that the instability observed in the unmodified scheme can be severe, leading to unbounded behaviour with arbitrarily small noise perturbations. The results are also illustrated with simulations showing how these modifications can lead also to improved performance.

Item Type: Conference or Workshop Item (UNSPECIFIED)
Divisions: Div F > Control
Depositing User: Cron Job
Date Deposited: 26 Sep 2018 20:11
Last Modified: 22 Jul 2021 05:29
DOI: 10.1109/CDC.2015.7402447