Reduction of Routing Complexity in Telecommunication Networks by a Novel Decomposition Method

Routing problems are often encountered when designing and managing telecommuni- cation networks. Today, routing problems are affected by the growing sizes of networks, which increase the complexity, and by introduction of new services and technologies, which rise the demands. Rather than resorting to entirely heuristic algorithms and/or large data bases with off-line precomputed routing information for various situations, we propose a a new decomposition method whereby any routing algorithm is speeded up considerably, thus permitting the deployment of well founded routing algorithms even for real time purposes. In our paper, we present this new method in formal terms, and apply it to a real routing problem. Finally, investigating the performance of our fast implementation by comparing it to the optimal, non-accelerated solution, we find that considerable time savings can be made at a limited cost in terms of non-optimality of the final solution. It is also emphasised that in real-time applications with non-constant traffics, this nominal degradation might be more than compensated for by the prompt delivery.This article is written under the Project "VP and VC Assignment and Routing