Optimal design of LAN-WAN internetworks: An approach using simulated annealing

This paper addresses the problem of designing LAN-WAN (Local Area Network, Wide Area Network) computer networks with transparent bridges. Bridges are high performance devices that are used to interconnect LANs at the MAC (Medium Access Control) level in the protocol hierarchy. LANs in remote areas are connected by leased telecommunications lines such as T1 and DDs. A requirement of transparent bridges is that networks must be configured in a spanning tree topology. The authors have developed mathematical models of LAN-WAN networks and formulated an optimization problem. This problem is a nonconvex, nonlinear, mixed integer program. A simulated annealing algorithm is proposed. The algorithm generates sequences of neighboring spanning trees and evaluates design constraints based on maximum flow, bridge capacity, and end-to-end delay. As the annealing temperature parameter is lowered the algorithm moves towards the global optimal solution. Experimental results have shown that LAN-WAN designs using simulated annealing are better than 99.99% of all feasible designs.