|
|
|
|
|
|
|
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 the 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. The collaborators of this work include Joe W.J. Jiang and Dah-Ming Chiu. Bio: John C.S Lui was born in Hong Kong and is currently the chairman of the Department of Computer Science & Engineering in the Chinese University of Hong Kong. He received his Ph.D. in Computer Science from UCLA. When he was a Ph.D student at UCLA, he spent a summer working in the IBM T. J. Watson Research Laboratory. After his graduation, he joined the IBM Almaden Research Laboratory/San Jose Laboratory and participated in various research and development projects on file systems and parallel I/O architectures. He later joined the Department of Computer Science and Engineering at the Chinese University of Hong Kong. For the past several summers, he has been a visiting professor in computer science departments at UCLA, Columbia University, University of Maryland at College Park, Purdue University, University of Massachusetts at Amherst and Universit degli Studi di Torino in Italy. Currently, he is leading a group of research students in the Advanced Networking & System Research Group in doing some interesting and exciting networking research. His research interests span both in system and in theory/mathematics. His current research interests are in theoretic/applied topics in data networks, distributed multimedia systems, network security, OS design issues and mathematical optimization and performance evaluation theory. John received various departmental teaching awards and the CUHK Vice-Chancellor's Exemplary Teaching Award in 2001. He is a co-recipient of the IFIP WG 7.3 Performance 2005 Best Student Paper Award. Currently, he is an associate editor in the Performance Evaluation Journal, an elected member in the IFIP WG 7.3. John was the TPC co-chair of ACM Sigmetrics 2005 and is currently on the Board of Directors in ACM SIGMETRICS. His personal interests include films and general reading.
|
|
|
|
|
|
|
|