Simulated Annealing Based Hierarchical Q-Routing: A Dynamic Routing Protocol
Antonio Mira Lopez, Douglas R. Heisterkamp · 2011
Network routing is the mechanism chosen to send packets from any source to a destination in the network. The goal of any routing algorithm is to find an efficient path to send a packet to any destination taking into account all the obstacles that may be taking place in the network at any time. 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 paper proposes a routing algorithm called Simulated Annealing based Hierarchical Q-Routing which is based on an Q-Routing. Providing an 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 temperature in simulated annealing adapts as a function of the waiting queue utilization of specific routers in the network. Experiments with different topologies and network loads show that the proposed method is able to improving convergence, loop avoidance, and scalability in comparison to Q-Routing.