[attachment=10736]
Introduction
Routing is a fundamental engineering task on the Internet. It consists in finding a path from a source to a destination host. Routing is complex in large networks because of the many potential intermediate destinations a packet might traverse before reaching its destination .
The page link weights are assigned by the network operator. The lower the weight, the greater the chance that traffic will get routed on that page link . When one sends or receives data over the Internet, the information is divided into small chunks called packets or datagrams. A header, containing the necessary transmission information, such as the destination Internet Protocol (IP) address, is attached to each packet. The data packets are sent along links between routers on Internet. When a data packet reaches a router, the incoming datagrams are stored in a queue to await processing. The router reads the datagram header, takes the IP destination address and determines the best way to forward this packet for it to reach its final destination .
The configuration of network protocols is widely considered a black art and is normally performed based on network administrators’ experience, trial and error, etc... These manual methods are often error-prone and not scalable to large complex networks. The emphasis of the search algorithm should be on finding a better operating point within the limited time frame instead of seeking the strictly global optimum. Network conditions vary with time and the search algorithm should quickly find better network parameters before significant changes in the network occur.
Another feature of these problems; for example, AT&T’s network has 1000s of routers and links. If all OSPF page link weights of this network are to be configured, there will be thousands of parameters present in the optimization.
Problem Statement
Single Source Shortest Path (SSSP) problem in the Internet routing environment especially when time is not a critical resource, the cost of sending packets is very high, and the nature of the application permits the finding of an optimal solution in a large search space. So finding a solution which determines a shortest path from source to destination in a limited time and reaching the optimality is critical concern.
Literature Survey
Many traditional and optimal search techniques are not guaranteed to yield the overall optimal solution, since they are not complete and are only searching a subset of the search space. Other algorithms that focus on enumerative methods are not efficient when the search space is too large. The Dijkstra algorithm is considered as the most efficient method. But when the network is very big, then it becomes inefficient since a lot of computations need to be repeated. Also it cannot be implemented in the permitted time.
We consider the GA search approach throughout. It is recognized that there are a large number of deterministic and heuristic search algorithms can be used to find a high performance solution for large search space problems. However, the approach of this project is to incorporate some heuristic knowledge into the genetic mechanism to improve the overall performance.
Methodology
As a special kind of stochastic search algorithms, genetic algorithm is a problem solving method which is based on the concept of natural selection and genetics. I use the following algorithm.
The steps of a GA are:
1. Choose initial population
2. Evaluate the fitness of each individual in the population
3. Repeat
a. Select best-ranking individuals to reproduce
b. Breed new generation through crossover and mutation (genetic operations) and give birth to offspring
c. Evaluate the individual fitnesses of the offspring
d. Replace worst ranked part of population with offspring
4. Until <terminating condition>