A detailed analysis of convergence rate is presented for an iterative path formulated optimal routing algorithm. The primary objective is to quantify, analytically, how the convergence rate changes as the number of nodes in the underlying graph increases. The analysis is motivated by a particular path formulated gradient projection algorithm that has demonstrated excellent convergence rate properties through extensive numerical studies. In particular, the empirical data suggests that the number of iterations required for convergence to within a small fraction of the optimal cost is relatively independent of the number of nodes. Deriving a correspondingly tight analytical bound for the number of iterations required for convergence, as a function of problem size, proves to be a formidable task, primarily because the dimension of the underlying optimization problem (i.e., the total number of paths connecting all origin-destination pairs) generically grows with a super-polynomial function of the number of nodes. The main result of this paper is that the number of iterations for convergence depends on the number of nodes only through the network diameter.

Date of this Version

October 1992