Elastic Traffic Engineering Subject to a Fair Bandwidth Allocation via Bilevel Programming

The ability of TCP’s congestion control scheme to adapt the rate of traffic flows and fairly use all the avail- able resources is one of the Internet’s pillars. So far, how- ever, the elasticity of traffic has been disregarded in traffic engineering (TE) methodologies mainly because, only recently, the increase in access capacity has moved the bottlenecks from the access network to the operator network and hungry cloud-based applications have begun to use all the available bandwidth. We propose a new approach to TE with elastic demands which models the interaction between the network operator and the end-to-end congestion control scheme as a Stackelberg game. Given a set of elastic traffic demands only specified by their origin-destination pairs, the network operator chooses a set of routing paths (leader’s problem) which, when coupled with the fair bandwidth allocation that the congestion control scheme would determine for the chosen routing (follower’s problem), maximizes a network utility function. We present bilevel pro- gramming formulations for the above TE problem with two widely-adopted bandwidth allocation models, namely, max-min fairness and proportional fairness, and derive corresponding exact and approximate single-level mathematical programming reformulations. After discussing some key properties, we report on computational results obtained for different network topolo- gies and instance sizes. Interestingly, even feasible solutions to our bilevel TE problems with large optimality gaps yield substantially higher network utility values than those obtained by solving a standard single-level TE problem and then fairly reallocating the bandwidth a posteriori.