DYNAMIC ROUTING AND QUEUE MANAGEMENT VIA BUNDLE SUBGRADIENT METHODS

Almir Mutapcic, Majid Emami, Keyvan Mohajer

2004

Abstract

In this paper we propose a purely distributed dynamic network routing algorithm that simultaneously regulates queue sizes across the network. The algorithm is distributed since each node decides on its outgoing link flows based only on its own and its immediate neighbors' information. Therefore, this routing method will be adaptive and robust to changes in the network topology, such as the node or link failures. This algorithm is based on the idea of bundle subgradient methods, which accelerate convergence when applied to regular non-differentiable optimization problems. In the optimal network flow framework, we show that queues can be treated as subgradient accumulations and thus bundle subgradient methods also drive average queue sizes to zero. We prove the convergence of our proposed algorithm and we state stability conditions for constant step size update rules. The algorithm is implemented using Matlab and its performance is analyzed on a test network with varying data traffic patterns.

Paper Citation

in Harvard Style

Mutapcic A., Emami M. and Mohajer K. (2004). DYNAMIC ROUTING AND QUEUE MANAGEMENT VIA BUNDLE SUBGRADIENT METHODS . In Proceedings of the First International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO, ISBN 972-8865-12-0, pages 12-19. DOI: 10.5220/0001144800120019

in Bibtex Style

@conference{icinco04,
author={Almir Mutapcic and Majid Emami and Keyvan Mohajer},
title={DYNAMIC ROUTING AND QUEUE MANAGEMENT VIA BUNDLE SUBGRADIENT METHODS},
booktitle={Proceedings of the First International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO,},
year={2004},
pages={12-19},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001144800120019},
isbn={972-8865-12-0},
}

in EndNote Style

TY - CONF
JO - Proceedings of the First International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO,
TI - DYNAMIC ROUTING AND QUEUE MANAGEMENT VIA BUNDLE SUBGRADIENT METHODS
SN - 972-8865-12-0
AU - Mutapcic A.
AU - Emami M.
AU - Mohajer K.
PY - 2004
SP - 12
EP - 19
DO - 10.5220/0001144800120019