|
Abstract:
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.
We explore two pricing schemes to resolve the above issues.
We show that by incorporating a proper pricing scheme,
the overlay routing game can be led to the desired equilibrium
and avoid the problems mentioned above.
Extensive fluid-based simulations are performed to support the theoretical claims.
Publications:
- Joe W.J. Jiang, Dah-Ming Chiu, John C.S. Lui.
``On the Interaction of Multiple Overlay Routing''.
Journal of Performance Evaluation, 62(1-4), October, 2005.
(Best Student Paper) (AR: 29/132=21%)
- Joe W.J. Jiang, John C.S. Lui, Dah-Ming Chiu.
``Interaction of Overlay Networks: Properties and Implications''.
ACM Sigmetrics Evaluation Review (PER) 33(2), September, 2005.
|
