(For source code see this updated post.)
Introduction
This post describes the use of a tool written in C++ that could be used to assist a network designer in establishing an optimal set of virtual paths in ATM networks.
In broadband ATM networks, the cellD based switching capacity is frequently built over digital cross connect system (DCS) networks. The DCS network can be considered the backbone for connecting ATM switches and for reconfiguration. As a consequence, the problem confronted by the system designer is how to configure the optimal topology and capacities within the DCS network.
In ATM we have the concept of an express pipe, which is used to directly connect two ATM switches via the DCS network but without the need to introduce intermediate ATM switching between them. In other words, different embedded topologies may be established from the backbone by way of introducing variations in express pipes. It is also possible to make further configurations in order to accommodate variations in traffic demands.
In the example given here, the objective is to obtain a routing policy such that the average packet delay is minimized. For this example, the network delay is based on the Kleinrock Independence Assumption in that the ATM network consists of independent M/M/1 queues. Propagation delays have been excluded from the delay calculation since they are only marginally affected by the topology and have little effect on the overall calculation.
Using the software
The optimization algorithm utilizes a standard depth-first search (DFS) algorithm to ascertain all path combinations between communicating end nodes. Each solution generated by the optimization algorithm is evaluated according to its average packet delay i.e. lower average packet delays correspond to higher fitness values. A ‘survival of the fittest’ mechanism is used to select promising routing policies at the expense of those that make less efficient use of the available bandwidth.
Solutions that violate design constraints such as traffic flows not exceeding link capacities have their fitnesses degraded so as to further discourage them from prevailing. Standard genetic operators crossover and mutation are used to aggressively explore the available solution space.The software has been designed so as to be reasonably intuitive in its use and generate good solutions within reasonable time scales.
Allocating the network nodes
The first stage is to allocate the set of network nodes. To do this, simply right-click on the drawing area and select ‘Add Node’ from the drop-down menu that appears:
By default, the nodes are labelled in ascending numerical order, but can be renamed easily enough by right-clicking on the node, selecting ‘Node Properties’ and changing the node label:
Allocating the link interconnections
To establish connections between the nodes, double-click the mouse pointer over the ‘start’ node (eg Exeter), and move the mouse pointer towards the intended ‘target’ node (eg Fleet). You will notice that double-clicking over a node will cause a line to be drawn between the start node and wherever the mouse pointer is located. When the mouse pointer is located in the vicinity of the target node, simply click the left mouse button to draw the link between the two end nodes:
Repeat this step until you have added all of your network interconnections:
The number in brackets on each link represents the capacity in kbits/sec on each link, and this defaults to 128 kbits/sec each time a new link is added. To change the link capacity, right-click over the link and select ‘Link Properties’ from the drop-down menu that appears:
Setting the network properties
For this example the link capacities remain unchanged. The next step is to set the average packet size, in bits, which is used in the calculation of average packet delay. In this example the default value of 1000 bits is used. To set this value, select the ‘Network Properties’ dialog from the Edit menu:
Setting traffic demands between communicating end nodes
The last step is to establish the traffic demands between communicating end nodes. From the Edit menu, select Network Traffic and use this dialog to set all traffic flow requirements:
Running the Genetic Algorithm based route optimization
To find the optimal set of routes ie those that minimize average packet delay, simply select the ‘Run’ option from the Action menu or click the Run icon:
Pressing ‘Start’ will invoke the algorithm to run for a set number of iterations but can be stopped at any time during the process.
To view the optimization results
To view the results of the optimization, press the View Solution Summary icon , to get a summary of the link usage statistics. This summary show the aggregate links flows resulting from the routing of all peak traffic demands as well as individual link utilizations:
To view the best combination of routes discovered by the optimization algorithm (not necessarily minimum-hop paths), select the View / Edit Routes icon :
This is but a rough-and-ready prototype at the moment, which can easily be refined to include a much richer set of features – enable the user to modify and re-evaluate the routes for example. Or perhaps optimize for cost as well as delay. Any comments and feedback would be much appreciated. Watch this space!
Download the Windows executable and source code:
