Topology design and bridge-capacity assignment for interconnecting token ring LANs: A simulated annealing approach

Autor: Larry J. LeBlanc, Varadharajan Sridhar, Joakim Kalvenes, June S. Park
Rok vydání: 1996
Předmět:
Zdroj: Telecommunication Systems. 6:21-43
ISSN: 1572-9451
1018-4864
DOI: 10.1007/bf02114284
Popis: We address the problem of determining the topology and bridge-capacity assignments for a network connecting a number of token rings via source-routing bridges. The objective is to minimize the cost of bridge installations while meeting the network users' performance requirements. The problem is modeled as a mixed 0---1 integer program. A comparison is given between two solution algorithms: a simulated annealing algorithm 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 subproblem is formulated as a nonlinear program with penalty functions to model node and link capacity constraints, and in the latter as a multicommodity flow model with the same capacity constraints. Computational results show that the simulated-annealing/flow-deviation algorithm produced substantially better solutions than the LP-based drop algorithm.
Databáze: OpenAIRE
Externí odkaz: