Method of optimally placing concentrator switches in a network

Abstract

A method of locating concentrator switches in an existing network that includes a plurality of sites interconnected by existing links so as to minimize total network cost in terms of transmission cost, equipment cost, and facility cost, while meeting all traffic demands. The method uses a Lagrange relaxation technique to perform the optimization. First, the method assigns to each site j an initial Lagrange multiplier .lambda..sub.j. Then the method selects from the sites a set of core nodes j such that the facility cost v.sub.j for each selected core node j is less than the Lagrange multiplier .lambda..sub.j for the site multiplied by the number of ports k.sub.1 in a concentrator switch, inherently forming a set of remaining source nodes i. Then the method homes the source nodes i to the core node j such that the cost to connect a source node i to a selected core node j plus the Lagrange multiplier .lambda..sub.j for the selected core node j multiplied by the traffic a.sub.i from said source node i is a minimum. The method calculates an upper bound and a lower bound for the cost of the network. Then, the method subtracts the lower bound from the upper bound and determines whether the difference is less than a predetermined value. If the difference between the upper bound and the lower bound is not less than the predetermined value, the method uses a subgradient technique to adjust the Lagrange multiplier .lambda..sub.j for each site j. The method performs iterations of adjusting the Lagrange multipliers .lambda..sub.j, selecting core nodes j, and homing source nodes i until the difference between the upper bound and the lower bound is less than the predetermined value.