Application of aggregation strategies in the solution of the optimal routing problem in data networks
Javier A Barria, L.F. Turner · IEE Proceedings - Computers and Digital Techniques · 1996
The paper is concerned with finding acceptable practical methods for evaluating and predicting the performance of data communication networks of arbitrary topologies and complexities. The performance indicator used is the value of the objective function of an optimal routing problem (ORP). Since the exact evaluation of the performance of data networks becomes very time consuming as the system grows in dimension and complexity, emphasis is placed on the reduction in computational time that can be had from the new numerical techniques proposed in the paper. The study of fast approximate solutions is also addressed. In particular, the aggregation policy obtained from a network decomposition algorithm is used to study three strategies for speeding up the solution of the ORP, when using as a baseline, the standard gradient projection (GPM) algorithm. The first strategy, solves a totally, or partially, aggregate network and obtains only approximate results; the second strategy finds a better initial point before starting the standard GPM, and the third strategy considers the application of three different switching mechanisms while the GPM algorithm is in progress. Depending on the traffic and topological characteristics of the network, a saving in computational time of between 10% and 53% can be had when using the acceleration techniques, and a saving of one order of magnitude can be achieved when using the approximation technique.