Multi-exit discriminator game for BGP routing coordination

Inter-Autonomous System (AS) links represent nowadays the real bottleneck of the Internet. Internet carriers may coordinate to efficiently balance the load, but the current practice is often based on an uncoordinated selfish routing. Firstly, we assess this issue by characterizing BGP route deviations across top-tier interconnections we could detect using recent Internet routing history data. Then, in order to improve the current practice, we present a novel gametheoretical framework to efficiently coordinate the routing on inter-AS links while modeling the non-cooperative carrier behavior. It relies on a coordinated use of the Multi- Exit Discriminator (MED) attribute of BGP, hence it is nick- named ClubMED (Coordinated MED). We define the routing policy that shall be implemented upon Nash equilibria and Pareto-efficient profiles. We emulated the interconnection between the Internet2 and the Geant2 networks, comparing our proposition to the current BGP practice. The results show that the route stability can significantly be reinforced, the global routing cost can be significantly reduced, and the inter-AS link congestion can be avoided.