In this paper Augmented Infinitesimal Perturbation Analysis (APA) is used for gradient estimation in a hybrid simulation/analytic system for computer communications network capacity planning called ATM Network Design (AND) System. Usage of APA provides an alternative to traditional network planning methods that assume independence of packet service times. A steepest descent algorithm determines locally optimal minimum average network delays based on these APA estimates. The algorithm employs an Armijo line search. In addition a linear, separable capacity constraint is assumed. It is assumed that input regulators (e.g., leaky bucket regulators) are used at the source of each virtual circuit. All virtual circuit external arrivals are modeled as independent Poisson processes. Regenerative simulation is used.