ON THE MULTIDENSITY GATEWAY LOCATION PROBLEM FOR A MULTILEVEL HIGH-SPEED INTERNETWORK

This paper addresses the problem of locating the concentrator gateways of different densities in a high speed interconnection of networks th at are connected in a hierarchical fashion. The organization of gatewa ys can be viewed as an uprooted tree, where gateways would be connecte d to each other in a hierarchy. Gateways at different levels of the tr ee will have different densities, and the higher is the level, the gre ater is the density. Such a multidensity gateway facilitates the shari ng of a high speed, high capacity intergateway link among multiple loc al networks. The objective of this work is to minimize the cost of set ting up plus the cost of operating multidensity gateways in an interne twork, subject to some capacity constraint. A mathematical programming model of the problem is developed, and a subgradient heuristic is use d to develop a solution procedure for the model. The algorithm is effi cient, and produces near optimal solutions always. Extensive simulatio n studies were conducted to test the performance of the heuristic. Int ernetworks, consisting upto thousands of local networks and hundreds o f potential gateways locations, were considered to verify the algorith m. (C) 1997 Elsevier Science B.V.