A TABU-SEARCH APPROACH FOR DESIGNING COMPUTER-NETWORK TOPOLOGIES WITHUNRELIABLE COMPONENTS

The topological design of computer networks is a part of network plann ing, and consists of finding a network topology configuration that min imizes the total communication cost, while considering some performanc e & reliability constraints. Given the computational complexity of tec hniques that allow an optimal solution to this problem, heuristic meth ods are often proposed to reduce the search of candidate topologies an d provide suboptimal solutions. The tabu search (TS) approach in this paper is one such method. Our adaptation of TS to the topological desi gn of computer networks applies some moves to a starting topology in o rder to reduce its total link-cost and/or to improve its average delay . In this sense, a neighbor of each current topology is then generated and, at each iteration, the topology which satisfies a reliability co nstraint at the lowest cost is chosen. The process is repeated until n o further improvement is found in the neighborhood of the current topo logy. Such an approach is an attempt to generalize a local-search meth od, Simulation results confirm the efficiency & robustness of this met hod for designing backbone networks interconnecting between 12 and 30 nodes. Our implementation of TS generally pro,ides better solutions th an CS, SA, and GA. The TS performance depends largely on: 1) the choic e of the neighborhood structure, 2) the length of the tabu list, and 3 ) other parameters that can affect the quality of results. These param eters are usually difficult to define & manipulate. Our implementation of TS uses a routing strategy where packets travel according to the s hortest distances between nodes. This strategy is easy to implement an d allows the direct evaluation of flow & delay, but has some shortcomi ngs, The routes do not vary according to the charge of the network, In practice, it is suitable to use the dynamic routing strategy where ro utes vary according to the traffic supported by the network. The lengt h of the tabu list can noticeably affect the final results, therefore the use of dynamic fist is entirely suitable. Similarly, the use of ce rtain features of TS, such as intensification and diversification, can severely affect the execution time and the quality of the final solut ion. Future work can evaluate the effect of load variations and conges tion problems, The combination of TS with other methods such as simula ted annealing and genetic algorithm might provide important contributi on for solving the problem of topological design of packet switched ne tworks.