FAST HEURISTICS FOR PRACTICAL TDM NETWORK DESIGN

Many large scale core data networks are now based on the new generatio n of intelligent time division multiplexers. These allow permanent vir tual circuits between any network nodes and automatic rerouting of los t 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 ma trix the number of possible network topologies, link capacity selectio ns, and circuit routings, even between a small number of nodes, is rel atively large. When taking into account the additional requirements of optimising the overall link capacity of a network and ensuring its re silience to failure by specifying link disjoint primary and backup pat hs, 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 d esign results. The following paper describes the modules of a heuristi c method that has been successfully used on a standard personal comput er to provide minimum cost optimum designs based on the described netw ork characteristics. The heuristics incorporate a speed versus accurac y trade-off factor so that rapid approximate designs may be examined f or differing traffic conditions. (C) 1997 Elsevier Science B.V.