Quality of Service Routing in MPLS Networks using Decentralized Learning

TitleQuality of Service Routing in MPLS Networks using Decentralized Learning
Publication TypeReport
Year of Publication2008
AuthorsHeidari, F., S. Mannor, and L. G. Mason
Date Published06/2008
InstitutionDepartment of Electrical and Computer Engineering, McGill University
CityMontreal, QC, Canada
TypeTechnical Report

Thispaperpresentsseveraldecentralizedlearningalgorithms for on-line intra-domain routing of bandwidth guaranteed paths in MPLS networks when there is no a-priori knowledge of traffic demand. The pre- sented routing algorithms use only their locally observed events and up- date their routing policy using learning schemes. The employed learning algorithms are either learning automata or the multi-armed bandit algo- rithms. We investigate the asymptotic behavior of the proposed routing algorithms and prove the convergence of one of them to the user equi- librium. Discrete event simulation results show the merit of these algo- rithms in terms of increasing the network admissibility compared with shortest path routing. We investigate the performance degradation due to decentralized routing as opposed to centralized optimal routing poli- cies in practical scenarios. The system optimal and the Nash bargaining solutions are two centralized benchmarks used in this study. We pro- vide nonlinear programming formulations of these problems along with a distributed recursive approach to compute the solutions. An on-line partially-decentralized control architecture is also proposed to achieve the system optimal and the Nash bargaining solution performances. The results of this study indicate that decentralized learning techniques pro- vide efficient, stable and scalable approaches for routing the bandwidth guaranteed paths.

heidari_TechReport08.pdf435.67 KB