A Tabu Search Based Routing Optimization Algorithm for Packet Switching Networks

摘要

In this paper, we present a tabu-search based algorithm that optimizes routing for packet switching networks. The problem of routing optimization can be seen as the search of the shortest path in a graph, where the bandwidths of connections, together with their traffic, can be considered as weights. This kind of optimization is usually carried out by means of the well-known Dijkstra algorithm or its various implementations. However, an exhaustive research tends to be very heavy, from a computational point of view, when the number of nodes gets high. For this reason, we opt for a meta-heuristic algorithm, particularly tabu search, capable of finding a non-optimal solution, that can be considered quite good, even without the need of an exhaustive research.