TOPOLOGY DESIGN AND BRIDGE-CAPACITY ASSIGNMENT FOR INTERCONNECTING TOKEN RING LANS - A SIMULATED ANNEALING APPROACH

We address the problem of determining the topology and bridge-capacity assignments for a network connecting a number of token rings via sour ce-routing bridges. The objective is to minimize the cost of bridge in stallations while meeting the network users' performance requirements. The problem is modeled as a mixed 0-1 integer program. A comparison i s given between two solution algorithms: a simulated annealing algorit hm using the flow-deviation algorithm for each routing subproblem, and a drop algorithm using the simplex method for the same subproblems to provide benchmark solutions. In the former algorithm, the routing sub problem is formulated as a nonlinear program with penalty functions to model node and link capacity constraints, and in the latter as a mult icommodity flow model with the same capacity constraints. Computationa l results show that the simulated-annealing/flow-deviation algorithm p roduced substantially better solutions than the LP-based drop algorith m.