Modeling non-convex costs in an LP (for traffic engineering on WANs)
Srikanth Kandula, Brendan Lucier, Ishai Menache, Mohit Singh · 2015
1 Traffic Engineering We describe a Traffic Engineering (TE) solution which can incorporate non-linear link costs. TE decides on the actual assignment of requests’ flow to (time, path) pairs. Formulation. A byte request, indexed by i, has a quantity of data di to be routed, and a value per byte vi. The request indicates the source Si and target Ti; data must be transmitted along a path from Si to Ti. Write Ri for the set of admissible paths (or routes) for request i. Let Xirt denote the number of bytes from request i transmitted along route r ∈ Ri at time t. The quantities X = (Xirt) fully describe a schedule of transfers. The objective of TE is to maximize welfare (values minus costs). Formally, the objective is