Designing the link topology and selecting capacities in a backbone network of a communication system involve complex tradeoffs between investment and operating costs and service considerations such as network reliability and vulnerability, delays, and blocking. Incorporating all these design criteria simultaneously in a comprehensive model results in a large-scale, nonlinear, discrete optimization problem that is intractable. This paper proposes an alternate optimization-based methodology to generate several cost-effective backbone network designs with varying cost and performance characteristics. Network planners can use this method together with detailed performance evaluation techniques to select a design that achieves the proper balance between conflicting objectives. To generate different configurations, the method parametrically varies a set of hop constraints that restrict the number of links over which messages can be transmitted. Reducing the maximum number of hops increases the number of alternate routes but incurs higher total cost for the communication system. For a given set of hop constraints, we develop a Lagrangian-based algorithm to identify a cost-minimizing network design that satisfies all internode traffic requirements. Our extensive computational tests using randomly generated networks demonstrate that, even for relatively large problems, the method identifies good heuristic solutions and tight lower bounds that confirm the near-optimality of the selected designs. Using a 25-node example, we illustrate how the model can be used to evaluate the cost versus performance tradeoff. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
No takes yet. Share an insight, caveat, or question.
Balakrishnan et al. (1992) studied this question.