We present the first constant-factor approximation algorithm for network
design with multiple commodities and economies of scale.  We consider
the {\em rent-or-buy} problem, a type of multicommodity buy-at-bulk
network design in which there are two ways to install capacity on any
given edge.  Capacity can be {\em rented}, with cost incurred on a
per-unit of capacity basis, or {\em bought}, which allows unlimited use
after payment of a large fixed cost.  Given a graph and a set of
source-sink pairs, we seek a minimum-cost way of installing sufficient
capacity on edges so that a prescribed amount of flow can be sent
simultaneously from each source to the corresponding sink.

Recent work on buy-at-bulk network design has concentrated on the
special case where all sinks are identical; existing constant-factor
approximation algorithms for this special case make crucial use of the 
assumption that all commodities ship flow to the same sink vertex and do
not obviously extend to the multicommodity rent-or-buy problem.  Prior 
to our work, the best heuristics for the multicommodity rent-or-buy 
problem achieved only logarithmic performance guarantees and relied on 
the machinery of relaxed metrical task systems or of metric embeddings.
By contrast, we solve the network design problem directly via a novel
primal-dual algorithm.