Preemptive Strategies to Improve Routing Performance of Native and Overlay Layers

Overlay routing is known to cause undesired instability in a network by operating in a selfish manner. The objectives of overlay routing, such as optimizing end-to-end latency, are often in conflict with the objectives of traffic engineering in the native layer, which is concerned about balancing load. In our work, we build on past research that has investigated the recurring non-cooperative interaction between overlay routing and traffic engineering, and develop strategies that improve the routing performance of a particular layer with incomplete information about the other layer. In our strategies, one layer acts as a leader that predicts the follower´s reaction and undertakes countermeasures to prevent future deterioration in performance. Specifically, we propose two classes of strategies - friendly or hostile - for each layer. By simulating under different network characteristics, we show that these preemptive strategies achieve near-optimal performance for the leader and increase the overall stability of the network. Furthermore, we observe that the best performance for a particular layer is achieved only when the goals of the other layer are completely violated, thereby motivating a higher level of selfishness.