Following on from a previous posting on genetic algorithm based routing optimization, further improvements have been made and the source code has been made available. This software is written using MFC / C++ and is essentially a single document interface allowing the user to create network nodes and links by way of standard mouse click actions and enter network parameters using the available menu items.
This post re-iterates the steps needed to create and set up your network topologies, traffic demands etc and gives some pointers on how you might tweak the settings to further improve your results. This is my first prototype, so any comments, suggestions and bug reports are always welcome. In fact, please give this a rigorous trying-out and let me know what you think, especially if you feel if there any improvements that could be made or other things that should be added.
1. Set the network properties
Leave the ‘Bi-directional links’ checked if you want links between nodes to be bi-directional. For directed graphs (uni-directional links) leave this box unchecked. The average size of a packet, is used in the calculation of queuing delay. When the algorithm tries to determine the most optimal paths, you can either let the algorithm consider all possible combinations of paths between communicating end nodes, or restrict it to the k number of shortest paths, so that the size of the search space is limited allowing the algorithm to possibly find better solutions within the available computation time. Please feel free to experiment with this.
2. Create the network nodes
And add the required number of nodes for your network:
3. Create the interconnecting links
To add a link between a pair of network nodes, double-click the left mouse button on or very near the start node, and move the mouse pointer towards end node. Notice how a line is drawn between the start node and the current position of the mouse pointer. When the mouse pointer has reached the end node, click the left mouse button:
Continue doing this for the remaining links:
4. Update the link bandwidths
Notice that all new links are allocated default bandwidths of 128 Kbps. To change these, simply right-click the link and select Link Properties:
And select the bandwidth you desire:
And do this for any other links you wish to change:
5. Set the traffic requirements between communicating end nodes:
Select Edit → Network Traffic and use this dialog to set all traffic flow requirements. (Alternatively click on the Traffic demands icon):
6. Set the Optimizer Properties
Modify these settings to decide if you wish to optimize the routes for average packet delay or if you wish to minimize the overall link utilization.
7. Save the network topology, traffic etc settings
Either by File → Save or by clicking the Save icon.
8. Run the genetic algorithm optimization algorithm
Either by Action → Run or by clicking the Run Optimization icon:
And click the start button. This optimization runs as a separate thread in the background and can be interrupted any time (without losing the best solution obtained so far) by clicking the Stop button.
9. View the results of the optimization:
Select Edit → Routes to view the results of the optimization. The Routing Solution dialog summarizes the best delay/utilization obtained, as well as the individual routes for each communicating node pair:
The top list box shows the paths taken for each source-destination, while the bottom list box shows the traffic flow and utilization for individual links:
For example, for link [0-1], the source-destination paths that use this link and their traffic demands can be seen to be:
0 → 1 (4)
1 → 4 (4)
1 → 6 (4)
2 → 5 (8)
3 → 5 (2)
5 → 6 (4)
So we would expect the total flow on link [0-1] to be 4 + 4 + 4 + 8 + 2 + 4 = 26, which is what is displayed here.
This following graph shows the average packet delay achieved versus the iteration, the best solution obtained so far being recorded at each iteration for this following network example ‘top1‘:
Download source code
Download the Visual Studio 2003 project and code:
Some other genetic algorithm related posts you might be interested in:
Genetic Algorithms Applied to Travelling Salesman Problems in C++
A Genetic Algorithm Function Optimizer in C++
A Genetic Algorithm Based Routing Optimization Tool
And also another post dealing with routing optimization:
