NP-completeness and integer programming model for station permutation in performance optimization of ring LANs

In a ring LAN, performance characteristics such as message transfer time, throughput, and bandwidth utilization depend on its station permutation. As ring LANs adopt fiber optics or other high speed transmission media, extend their geographical coverage, and hence contain more stations, such a dependency becomes more significant. The paper formulates the ring performance optimization problem associated with such a dependency, proves the NP-completeness of the problem, and establishes an integer programming model for solving the problem