Auction-based Optimal Dimensioning of MPLS Tunnels

Using MPLS for efficient traffic engineering crucially depends on the optimal dimensioning of Label Switched Paths (LSPs). The standard formulation as multi-commodity flow problem periodically solves a mixed integer programming problem that maximizes total network revenue, assuming fixed charges for carrying traffic of a certain QoS (Quality-of-Service). This paper generalizes this approach: charges are assumed no longer to be fixed, but may vary dynamically according to network congestion. To this end, second-price auctions are used to determine the current market price of a commodity. Here, each user has to specify a bid for her request. Bandwidth is distributed according to the bid order, whereas all winning bidders pay an identical charge, derived from the highest losing bid. This grants incentive compatibility, i.e. the user is forced to reveal her true evaluation of the worth of the commodity. This pape