Method of optimally placing concentrator switches in a network

Details Method of optimally placing concentrator switches in a network Method of optimally placing concentrator switches in a network

1996-12-27

1998-11-24

Pham, Chi H.

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

370400, H04J 1100

Patent

active

058417583

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.

REFERENCES:
patent: 5317566 (1994-05-01), Joshi
Chung et al, "An Enhanced Zero-One Optimal Path Set Selection Method", Department of Computer Science and Information Engineering, National Chiao Tung University, Hsin-Chu, Taiwan, Republic of China, Oct. 1996.

Affiliated with

Also associated with

Rating

Method of optimally placing concentrator switches in a network does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of optimally placing concentrator switches in a network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of optimally placing concentrator switches in a network will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1711050