Fast heuristics for practical TDM network design |
Many large scale core data networks are now based on the new generation of intelligent time division multiplexers. These allow permanent virtual circuits between any network nodes and automatic rerouting of lost connections should link failures occur. The design requirements for such networks are very different to those more usually associated with standard packet switched network arrangements. For a given traffic matrix the number of possible network topologies, link capacity selections, and circuit routings, even between a small number of nodes, is relatively large. When taking into account the additional requirements of optimising the overall link capacity of a network and ensuring its resilience to failure by specifying link disjoint and primary backup paths, the design complexity becomes very large. It is also necessary to use commercial link costs for all the link specifications likely to be selected from the various PTT service providers to ensure realistic design results.
Ray GP, Sanders P, Stockel CT
The following paper describes the modules of a heuristic method that has been successfully used on a standard personal computer to provide minimum cost optimum designs based on the described network characteristics. The heuristics incorporate a speed versus accuracy trade-off factor so that rapid approximate designs may be examined for differing traffic conditions.