Stochastic Traffic Engineering, with Applications to Network Revenue Management

We present a stochastic traffic engineering framework for optimizing bandwidth provisioning and path selection in networks. The objective is to maximize revenue from serving demands,which are uncertain and specified by probability distributions. We consider a two-tier market structure, where demands in the two markets are associated with different unit revenues and uncertainties. Based on mean-risk analysis, the optimization model enables a carrier to maximize mean revenue and contain the risk that the revenue falls below an acceptable level. Our framework is intended for off-line traffic engineering design, which takes a centralized view of network topology, link capacity, and demand. We obtain conditions under which the optimization problem is an instance of convex programming and therefore efficiently solvable. We derive properties of the optimal solution for the special case of Gaussian distributions of demands. We focus on the impact of demand variability on various aspects of traffic engineering, such as link utilization, routing, capacity provisioning, and total revenue.