Fault-Tolerant Virtual Path Layout in ATM Networks

Asynchronous Transfer Mode (ATM) is a communications architecture for the provision of broadband integrated services digital networks. Two fundamental features of ATM networks are hierarchical routing and statistical multiplexing. This paper addresses the problem of laying out virtual paths (VPs), which are logical network links that provide direct connections between certain nodes. A bi-criteria integer-programming model is developed that includes a throughput-maximization objective, a delay/overhead minimization objective, and a diversity constraint whereby link-disjoint VPs are found so as to provide fault tolerance. The formulation employs a new model for approximating the effects of statistical multiplexing. An approximate solution method is developed, which employs constraint generation for bound tightening, and heuristics based on rounding of a linear programming solution.