Source routing in the internet with reinforcement learning and genetic algorithms
Zhiguang Xu · 2006
Abstract: Source routing of packets in the Internet requires that a path be selected in advance and stored at the source nodes. Path selection is typically based on Quality of Service (QoS) criteria like packet delay, delay jitter, and loss. A new protocol called the “Cognitive Packet Network ” (CPN) [18, 19, 20, 21] has been proposed which is capable of dynamically choosing paths through a store and forward packet switching network like the Internet so as to provide best effort QoS to peer-to-peer connections. A CPN-enabled network uses smart packets to discover routes based on QoS requirements; acknowledgement (ACK) packets to deliver the routes back to source nodes; dumb packets to carry user-payload; and reinforcement learning to conduct path selection. We extended the path discovery process in CPN by introducing a genetic algorithm (GA) that can help discover new paths that may not have been discovered by smart packets [28]. In this paper, we further extend CPN with GA by prioritizing paths discovered based on their ages, adopting a progressive fitness evaluation system, and introducing a new genetic operator – mutation. The simulation topology has also been upgraded from a 10 by 10 grid to an arbitrarily connected network. We detail the design of the algorithms and their implementations, and finally report on resulting QoS measurements. Key-Words: Routing, quality of service, packet switching, reinforcement learning, genetic algorithms 1