Routing games for traffic engineering

Abstract

Current data network scenario makes traffic engineering (TE) a very challenging task. The ever growing access rates and new applications running on end-hosts result in more variable and unpredictable traffic patterns. By providing origin-destination pairs with several possible paths, load-balancing has proved itself an excellent tool to face this uncertainty. In particular, mechanisms where routers greedily minimize a path cost function (thus requiring minimum coordination) have been studied from a game-theoretic perspective in what is known as a routing game (RG). The contribution of this paper is twofold. We first propose a new RG specifically designed for elastic traffic, where we maximize the total utility through load-balancing only. Secondly, we consider several important RGs from a TE perspective and, using several real topologies and traffic demands, present a thorough comparison of their performance. This paper brings insight into several RGs, which will help one in choosing an adequate dynamic load-balancing mechanism. The comparison shows that the performance gain of the proposed game can be important.