Reconciling the Overlay and Underlay Tussle

In the presence of multiple overlays and underlays, the emerging global network behavior is the result of interactions of self-serving overlay routing decisions and independent underlay management actions. It is crucial for network operators, service, and content providers to have a good grasp of the underlying principles in order to better design and manage current and future networks and services. In this paper, we describe special game scenarios wherein the interaction of noncooperative overlays and underlays in multidomain networks can result in an operable global configuration in linear time and the overall convergence is polynomial in the unweighed case. For weighted games, we find that weighted Shapley potential can achieve linear time convergence to an operable state. Furthermore, we analyze the interaction of overlays and underlays as a two-stage congestion game and recommend simple operational guidelines to ensure global stability. We further explore the use of Shapley value as an enabler of mutual cooperation in an otherwise competitive environment. Our simulation results confirm our findings and demonstrate its effectiveness in general networks.