We investigate the impact of the locations of the gateways on the performance of the internet. We consider the problem of determining (i) the routing assignments for the intranet and internet traffic and (ii) the number of gateways and their locations to interconnect existing data networks to minimize a linear combination of the average internet and intranet packet delays subject to a cost constraint on the amount to be spent to establish the gateways. This joint routing and topological design problem is important in the design of internets and should be solved before networks are actually interconnected. This problem is formulated as a nonlinear combinatorial optimization problem. When the gateway locations are fixed, the resulting routing problem is not a convex programming problem. This is unexpected since the routing problem in datagram networks is usually formulated as a convex program. We develop an algorithm based upon Lagrangian relaxation to solve this problem. In the computational experiments, the algorithm was shown to be effective in interconnecting (i) two WANs and (ii) two grid networks. The experiments also showed that the algorithm finds better feasible solutions than an exchange heuristic.>

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.>