Locating internet gateways to minimize nonlinear congestion costs

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