A genetically-motivated heuristic for route discovery and selection in packet-switched networks.

摘要

Route discovery and selection are fundamental to packet-switched networks. As a packet transits a network, routers determine the path on which the packet will be forwarded. The primary objective of a routing system is to discover feasible and efficient routes for packets to follow in the network.; Finding the minimum-delay route that does not exceed capacity constraints is a difficult problem. Besides being inherently complex, the problem is intrinsically distributed with strong real-time constraints. In addition, the input to the problem may be unrealistically large or simply unavailable. Therefore, the input is often simplified and approximated, sometimes using broad and unrealistic assumptions. Because these assumptions introduce error, solving the routing problem precisely is of limited value. Heuristic approaches offer a potential balance between accuracy and computational feasibility.; The purpose and contribution of this research is to evaluate both the analytical and empirical performance of an adaptive routing heuristic that bases its operation on a genetic metaphor. The system simulates evolution, borrowing from nature's familiar operators of reproduction, mutation, and selection. As the landscape changes, the system evolves with it. By modeling nature's “survival of the fittest” optimization operator, near-optimal routing tables can be cultured in the network “petri dish.” The proposed heuristic operates without an explicit knowledge of the network's topology or traffic characteristics. As such, it is well suited to an environment where this information is unavailable or changing. In addition, the proposed heuristic is simple, both in concept and implementation. This research demonstrates that the method is capable of finding near-optimal routes in the topologies studied. Analysis is provided to demonstrate that the behavior of the heuristic can be modeled and accurately predicted.; The approach has limitations and shortcomings. However, like the genetic mutations it seeks to model, this approach represents an evolutionary step in routing protocol design. Hence, understanding its strengths and weaknesses is essential to determine if, when, and how characteristics of the heuristic are to be incorporated into future routing protocols. Developing this understanding is the motivation for this research.