| 摘要 |
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 j. Then the method selects from the sites a set of core nodes j such that the facility cost vj for each selected core node j is less than the Lagrange multiplier lambda j for the site multiplied by the number of ports k1 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 j for the selected core node j multiplied by the traffic ai 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 j for each site j. The method performs iterations of adjusting the Lagrange multipliers lambda 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. |
