Network Routing with Extended Genetic Algorithms

E. Gelenbe, Z. Xu, and A.S. Wu (USA)


routing, packet networks, quality of service, genetic algorithms


Routing of packets in networks requires that a path be selected either dynamically while the packets are being forwarded, or statically (in advance) as in source routing from a source node to a destination. Typically, routes are selected so that some criterion of performance can be satisfied, in addition to the most elementary need of conveying data from a specified source to a specified destination. Recently, we have developed a Quality of Service (QoS) driven routing protocol called “Cognitive Packet Network” (CPN) which dynamically selects paths through a store and forward packet network so as to provide best effort QoS to route peer-to-peer user traffic. This technique uses smart packets to select routes based on the user’s QoS requirements. In this paper we extend the path discovery process in CPN to include a genetic algorithm which can help discover new paths that may not have been discovered by smart packets. We propose a genetic algorithm approach to the construction and selection of routes when the user, or the system, are able to specify some desired QoS property. We show how possible routes can be “evolved” from prior knowledge or can be generated at random, and are then selected based on their “fitness” with respect to some desirable QoS property. We detail the design of the algorithm and of its implementation in the Cognitive Packet Network test-bed and report the resulting QoS measurements.

Important Links:

Go Back