A ROUTING ALGORITHM FOR VIRTUAL CIRCUIT DATA-NETWORKS WITH UNRELIABLE LINKS

Abstract

This paper considers a routing problem for virtual circuit data networks with unreliable links. The problem is analyzed by transforming it into a stochastic multicommodity flow problem with recourse to find the optimal route set (primary and secondary routes for all origin-destination pairs) that minimizes the expected average packet delay. Both the Lagrangian relaxation and the aggregate stochastic subgradient optimization methods are used to find the optimal solution (route set), for which a stochastic version of the K(O)-ordering method is newly exploited to find the initial feasible solution.