Network partition for switched industrial ethernet using combined search heuristics

Abstract

A large industrial company needs a cost efficient telecommunication network to support heavy telecommunication needs among its different departments which are distributed in various locations. Because of the huge amount of daily communications, the network designer must partition the communicating devices into subnets each of which is supported by a high speed Ethernet. Then, the subnets are connected by a second level switch device called controller which handles inter-subnet communications. An optimization problem is how to partition n communicating devices into k groups such that the amount of intra-network traffic is balanced among the k groups and at the same time the inter-network traffic is minimized for a given traffic demand. This problem is known as the Network Partition Problem (NPP). The NPP problem has been studied by some researchers, but because of its NPhardness, only limited progress has been reported by two recent papers. The later one slightly improved on the results obtained by the previous one, and both papers used genetic algorithms. This thesis investigated the NPP problem and concluded by extensive tests that it is very difficult to improve further if we purely follow the method of genetic algorithms. Motivated by searching for new approaches, this thesis tried another evolutionary algorithm, i.e., the simulated annealing (SA) to see any hope to get a breakthrough. Encouraging results were obtained for some cases but not show overall superiority. Finally, this thesis investigated the approach that combines these two methods in searching for a better result. Extensive simulations demonstrated that this method work efficiently. By the combination of these two methods, we obtained obvious improvements on previous published results. This approach studied in this thesis can be applicable to practically solving other NP-hard problems also.