Publication

Abstract : This paper addresses the problem of locating the concentrator gateways of different densities in a high speed interconnection of networks that are connected in a hierarchical fashion. The organization of gateways can be viewed as an uprooted tree, where gateways would be connected to each other in a hierarchy. Gateways at different levels of the tree will have different densities, and the higher is the level, the greater is the density. Such a multidensity gateway facilitates the sharing of a high speed, high capacity intergateway link among multiple local networks. The objective of this work is to minimize the cost of setting up plus the cost of operating multidensity gateways in an internetwork, subject to some capacity constraint. A mathematical programming model of the problem is developed, and a subgradient heuristic is used to develop a solution procedure for the model. The algorithm is efficient, and produces near optimal solutions always. Extensive simulation studies were conducted to test the performance of the heuristic. Internetworks, consisting upto thousands of local networks and hundreds of potential gateways locations, were considered to verify the algorithm.