Approximate on-line implementable algorithms for dynamic routing in communication networks

The dynamic routing problem in multiple destination data communication networks is addressed by minimizing the minimum time cost functional associated with Segall´s [1] linear model. The optimal solution is characterized by examining the competition of bottlenecks associated with each destination. An algorithm for the multidestination problem proceeding through an iterative link-by-link optimization is presented. This algorithm either in its centralized or in its distributed implementation is of exponential complexity and unsuitable for on-line application even for medium sized networks. We further investigate a differential version of the same algorithm. Based on the solution corresponding to a given data set, we propose a scheme for solving problems with data lying in the neighbourhood of the original set, thus reducing the computational burden for on-line applications.