A gateway allocation algorithm for interconnecting existing data networks

The problem of interconnecting two virtual circuit networks is considered. More specifically, the problem is to determine: (1) which nodes (one from each network) should be connected by gateways; and (2) the routing assignments to minimize the routing costs subject to a limitation on the cost of the gateways. This problem is NP-hard. The problem is formulated here as a linear combinatorial optimization problem. A two-phase algorithm is proposed to obtain good solutions. The first phase is a greedy heuristic algorithm. The second phase is an algorithm based on Lagrangian relaxation with the subgradient method. This method has been implemented. In the present computational experiments, the method determines gateway locations to interconnect networks (of various sizes) that are within a few percent of an optimal solution in a few minutes of CPU time