Virtual path design in service-specific ATM networks

This paper addresses the problem of virtual path management in ATM networks, which is the problem of jointly selecting efficient virtual trunk routes and sizing them to meet end-to-end grade-of-service requirements. The problem is posed over capacitated networks and is formulated as a two-level multi-commodity network flow problem with linear side-constraints (physical layer capacity) and non-linear side constraints (end-to-end/link blocking). Through a variety of examples we show the method (i) generates solutions that agree with engineering judgement, (ii) can solve VP layout management for realistic size networks (of up to 200 nodes) in reasonable time and (iii) provides upper bounds on how far the solution strays from the mathematically optimal design.