Simulated Annealing Based Hierarchical Q-routing: a Dynamic Routing Protocol

Abstract

The focus of this paper is to provide an efficient solution to the routing problem by making use of reinforcement learning and other heuristics. The thesis describes a routing algorithm called Q-Routing based on the Q-learning algorithm that will be used as the base for the proposed Simulated Annealing based Hierarchical Q-Routing approach. The proposed approach adds functionality layers to provide a more hierarchical view of the network. Providing hierarchy by defining network areas and roles to routers within these areas allows us to have more updated global information and therefore much better decision making when routing packets across the network. The addition of simulated annealing as an exploration method also plays an important role in the improvement of the original Q-Routing approach. The results from every experiment that was performed show SAHQ-Routing to be a much more robust and efficient routing algorithm than Q-Routing.