Continuous Models for Capacity Design of Large Packet-Switched Telecommunication Networks

We formulate nonlinear programming models for design of large-scale packet-switched telecommunication networks. In these models, the network’s link capacities and source-destination message routes are chosen simultaneously. Although leased communication lines are available only in discrete units of capacity, public telephone lines with high-speed modems can be used to augment them, thus effectively obtaining fractional equivalents of leased-line capacity. Therefore, our network-design models contain continuous link-capacity variables. These continuous models can be solved for ϵ-optimal solutions, even for networks with hundreds or thousands of nodes. We examine conventional link delay functions used by previous researchers and suggest an alternative class of convex delay functions. Using computer simulation to analyze link delays, we compare the convex delay function to the conventional one. We conclude, for our assumed message-length distribution, that the convex delay function predicts the simulated delays more accurately than the conventional one when flow-capacity ratios larger than or equal to 0.80 are ignored. However, the conventional delay function fits the simulated delays more accurately than the convex one when these high-congestion ratios are considered. Thus, in network-design models in which flow-capacity ratios must be less than 80%, our convex model can be more accurate than the nonconvex conventional one. Computational results show that our models give very good solutions for different size networks with up to 100 nodes.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.