Interaction of Overlay Routing
(John C.S. Lui)

In the past few years, overlay networks have received much attention but there has been little study on the ``interaction'' of multiple, co-existing overlays on top of a physical network. In addition to previously introduced concept of overlay routing strategy such as selfish routing, we introduce a new strategy called ``overlay optimal routing''. Under this routing policy, the overlay seeks to minimize its weighted average delay by splitting its traffic onto multiple paths. We establish that (i) the overlay optimal routing can achieve better delay compared to selfish routing, and (ii) there exists a Nash equilibrium when multiple overlays adopt this strategy. Although an equilibrium point exists for overlay optimal routing and possibly for selfish routing, we show that the interaction of multiple overlay routing may not be Pareto optimal and that some fairness anomalies of resource allocation may occur. This is worthy of attention since overlay may not know the existence of other overlays and they will continue to operate at this sub-optimal point.