TOPOLOGICAL DESIGN OF A 2-LEVEL NETWORK WITH RING STAR CONFIGURATION

This paper deals with topological design of a hierarchical two-level n etwork where the upper-level hub network is of ring type and the lower -level local access networks are of star-type. The problem is modeled as a mixed 0-1 integer programming, the special structure of which is exploited for the development of a dual-based lower bounding procedure . A heuristic procedure is developed to construct a primal feasible so lution from the dual solution obtained by the dual procedure. The perf ormance of our method is well demonstrated by the computational experi ments conducted with a variety of test problems ranging up to 20 hub n odes and 50 user nodes.