  We consider a general online network design problem where a sequence of N
requests arrive over time, each of which needs to use some subset of the
available resources E. The cost incurred by any resource e is some function
$f_e$ of the total load $L_e$ on that resource. The objective is to minimize
the total cost $\sum_{e\in E} f_e(L_e)$. We focus on cost functions that
exhibit (dis)economies of scale, that are of the form $f_e(x) = \sigma_e +
\xi_e\cdot x^{\alpha_e}$ if $x>0$ (and zero if $x=0$), where the exponent
$\alpha_e\ge 1$. Optimization problems under these functions have received
significant recent attention due to applications in energy-efficient computing.
Our main result is a deterministic online algorithm with tight competitive
ratio $\Theta\left(\max_{e\in E}
\left(\frac{\sigma_e}{\xi_e}\right)^{1/\alpha_e}\right)$ when $\alpha_e$ is
constant for all $e\in E$. This framework is applicable to a variety of network
design problems in undirected and directed graphs, including multicommodity
routing, Steiner tree/forest connectivity and set-connectivity. In fact, our
online competitive ratio even matches the previous-best (offline) approximation
ratio for generalized network design.
