Routing algorithms for communication networks with unreliable links

Abstract

This thesis considers routing problems associated with three different communication networks with unreliable links. Mathmatical models and the associated solution procedures are developed. A new approach is proposed for the joint selection of primary and secondary paths in communication networks where links are subject to failure and multiple links are allowed to be in failure state simultaneously. The problem is analyzed by transforming it into a stochastic multicommodity flow problem with recourse to find the optimal route set. The expected average packet delay in chapter 2 and 3, and the expected average cell loss rate in chapter 4 are used as performability measure to reflect the degradation in performance which may incur at any failure. The stochastic behavior of the network can be conveniently described by use of some solution characterization methodologies including aggregate stochastic subgradient method. Routing problems for datagram networks with unreliable links, for virtual circuit data networks and for ATM networks are considered in chapter 2, 3 and 4, respectively. These routing problems with unreliable links are approached by a restoration algorithm based on a distributed self-healing algorithm with preplanned, path restoration scheme. Heuristic methods are also suggested for finding good initial feasible solutions. And the algorithms are tested for their performance evaluation.