Edoardo Amaldi

Title of Presentation: Optimizing Internet Routing: A Bilevel Approach


The ability of traffic flows to adapt their rate and fairly use all available resources is one of the Internet’s pillars. However, this traffic characteristic, often referred to as elasticity, has not yet been fully considered in the optimization literature.

We present a new approach to network routing with elastic demands, where the interaction between the network operator and the congestion control scheme is modeled as a Stackelberg game, whose equilibrium can be computed by solving a bilevel optimization problem. In the first level, the network operator chooses a routing path for each origin-destination pair so as to maximize a utility function while, in the second level, the congestion control scheme determines a bandwidth allocation to the flows by maximizing a fairness measure.

After discussing structural properties and complexity issues, we describe single-level mixed-integer programming formulations or approximations for two known fairness measures. Then we summarize our work on exact and heuristic methods and report some computational results. The numerical experiments confirm the substantial difference between the advocated traffic engineering approach and the standard ones which neglect the bilevel nature of Internet routing.T

he talk is based on joint works with Antonio Capone, Stefano Coniglio, Luca Gianoli and Leonardo Taccari.


Professor Amaldi Professor of Operations Research at the Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano, Italy. He received the “Diplome” in Mathematical Engineering and the “Doctorat ès Sciences” (PhD) from the Swiss Federal Institute of Technology at Lausanne (EPFL). Dr. Amaldi’s main research interests are in Discrete Optimization with an emphasis on problems related to graphs, networks and infeasible linear systems, and with applications in areas such as telecommunications, data mining and energy.