Hostname: page-component-8448b6f56d-mp689 Total loading time: 0 Render date: 2024-04-19T17:08:21.560Z Has data issue: false hasContentIssue false
  • English
  • Français

PERFORMANCE OF NON-COOPERATIVE ROUTING OVER PARALLEL NON-OBSERVABLE QUEUES

Published online by Cambridge University Press:  19 May 2016

Olivier Brun
Olivier Brun*
Affiliation:
LAAS-CNRS, Université de Toulouse, 7 Avenue du Colonel Roche, 31077 Toulouse, France E-mail: brun@laas.fr
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Autonomic computing is emerging as a significant new approach to the design of computer services. Its goal is the development of services that are able to manage themselves with minimal direct human intervention, and, in particular, are able to sense their environment and to tune themselves to meet end-user needs. However, the impact on performance of the interaction between multiple uncoordinated self-optimizing services is not yet well understood. We present some recent results on a non-cooperative load-balancing game which help to better understand the result of this interaction. In this game, users generate jobs of different services, and the jobs have to be processed on one of the servers of a computing platform. Each service has its own dispatcher which probabilistically routes jobs to servers so as to minimize the mean processing cost of its own jobs. We first investigate the impact of heterogeneity in the amount of incoming traffic routed by dispatchers and present a result stating that, for a fixed amount of total incoming traffic, the worst-case overall performance occurs when each dispatcher routes the same amount of traffic. Using this result we then study the so-called Price of Anarchy (PoA), an oft-used worst-case measure of the inefficiency of non-cooperative decentralized architectures. We give explicit bounds on the PoA for cost functions representing the mean delay of jobs when the service discipline is PS or SRPT. These bounds indicate that significant performance degradations can result from the selfish behavior of self-optimizing services. In practice, though, the worst-case scenario may occur rarely, if at all. Some recent results suggest that for the game under consideration the PoA is an overly pessimistic measure that does not reflect the performance obtained in most instances of the problem.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 30 , Issue 3: Erol Gelenbe's 70th Birthday , July 2016 , pp. 455 - 469
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
Copyright © Cambridge University Press 2016

References

1.Akella, A., Seshan, S., Karp, R., Shenker, S., & Papadimitriou, C. (2002). Selfish behavior and stability of the internet: a game-theoretic analysis of TCP. In Proceedings of the 2002 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, Pittsburgh, Pennsylvania, USA, 19–23 August 2002.Google Scholar
2.Altman, E., Ayesta, U., & Prabhu, B.J. (2011). Load balancing in processor sharing systems. Telecommunication Systems 47(1–2): 35–48.CrossRefGoogle Scholar
3.Altman, E., Basar, T., Jiménez, T., & Shimkin, N. (2001). Routing into two parallel links: Game-theoretic distributed algorithms. Journal of Parallel and Distributed Computing 61(9): 1367–1381.Google Scholar
4.Altman, E., Boulogne, T., Azouzi, R.E., Jimenez, T., & Wynter, L. (2006). A survey on networking games in telecommunications. Computers and Operations Research 33(2): 286–311.Google Scholar
5.Anselmi, J. & Gaujal, B. (2010). Optimal routing in parallel, non-observable queues and the price of anarchy revisited. In 22nd International Teletraffic Congress (ITC), Amsterdam.Google Scholar
6.Anselmi, J. & Gaujal, B. (2010). The price of anarchy in parallel queues revisited. In ACM Sigmetrics, New-York, USA, pp. 353–354.Google Scholar
7.Anselmi, J. & Gaujal, B. (2011). The price of forgetting in parallel and non-observable queues. Performance Evaluation 68(12): 1291–1311.Google Scholar
8.Anselmi, J., Gaujal, B., & Nesti, T. (2015). Control of parallel non-observable queues: asymptotic equivalence and optimality of periodic policies. Stochastic Systems 5(1): 120–145.Google Scholar
9.Ayesta, U., Brun, O., & Prabhu, B.J. (2011). Price of anarchy in non-cooperative load balancing games. Performance Evaluation 68: 1312–1332.CrossRefGoogle Scholar
10.Bell, C.H. & Stidham, S. (1983). Individual versus social optimization in the allocation of customers to alternative servers. Management Science 29: 831–839.Google Scholar
11.Brun, O. & Prabhu, B. (2014). Worst-case analysis of non-cooperative load balancing. Annals of Operations Research 1–25. http://dx.doi.org/10.1007/s10479-014-1747-7.Google Scholar
12.Brun, O., Prabhu, B., & Seregina, T. (2013). On the convergence of the best-response algorithm in routing games. In Proceedings of the Seventh International Conference on Performance Evaluation Methodologies and Tools (ValueTools’13) pp. 136–144.Google Scholar
13.Brun, O., Wang, L., & Gelenbe, E. (2016). Data driven self-managing routing in intercontinental overlay networks. Accepted for publication in the IEEE Journal on Selected Areas in Communications, p. 9.Google Scholar
14.Charilas, D.E. & Panagopoulos, A.D. (2010). A survey on game theory applications in wireless networks. Computer Networks 54(18): 3421–3430.Google Scholar
15.Chen, H.-L., Marden, J.R., & Wierman, A. (2008). The effect of local scheduling in load balancing designs. SIGMETRICS Performance Evaluation Review 36(2):110–112.Google Scholar
16.Cominetti, R., Correa, J.R., & Stier-Moses, N.E. (2009). The impact of oligopolistic competition in networks. Operations Research 57(6): 1421–1437.Google Scholar
17.Coucheney, P., Gaujal, B., & Mertikopoulos, P. (2014). Penalty-regulated dynamics and robust learning procedures in games. Technical Report, Inria Grenoble - Rhône-Alpes and LIG (Laboratoire d'Informatique de Grenoble), April 2014. https://hal.inria.fr/hal-01073497Google Scholar
18.Czumaj, A., Krysta, P., & Vocking, B. (2010). Selfish traffic allocation for server farms. SIAM Journal on Computing 39(5): 1957–1987.Google Scholar
19.Doncel, J., Ayesta, U., Brun, O., & Prabhu, B. (2014). Is the price of anarchy the right measure for load-balancing games? ACM Transactions on Internet Technology (TOIT) 14(2–3): 18.1–18.20.CrossRefGoogle Scholar
20.Ganek, A.G. & Corbi, T.A. (2003). The dawning of the autonomic computing era. IBM Systems Journal 42(1): 5–18.CrossRefGoogle Scholar
21.Garg, R., Kamra, A., & Khurana, V. (2002). A game-theoretic approach towards congestion control in communication networks. ACM SIGCOMM Computer Communication Review 32(3): 47–61.Google Scholar
22.Gelenbe, E. (2003). Sensible decisions based on QoS. Computational Management Science 1(1): 1–14.Google Scholar
23.Gelenbe, E., Lent, R., & Nunez, A. (2004). Self-aware networks and QoS. Proceedings of the IEEE 92(9): 1478–1489.Google Scholar
24.Gelenbe, E. & Timotheou, S. (2008). Random neural networks with synchronized interactions. Neural Computation 20(9): 2308–2324.Google Scholar
25.Gunturi, S., Paganini, F., Instruments, T., and Bangalore, I.. (2003). Game theoretic approach to power control in cellular CDMA. In Vehicular Technology Conference. VTC 2003-Fall.Google Scholar
26.Han, Z., Ji, Z., & Liu, K. (2007). Non-cooperative resource competition game by virtual referee in multi-cell OFDMA networks. IEEE Journal on Selected Areas in Communications 25(6): 1079–1090.Google Scholar
27.Hassin, R. & Haviv, M. (2003). To queue or not to queue- equilibrium behavior in queueing systems. Springer US.Google Scholar
28.Haviv, M. & Roughgarden, T. (2007). The price of anarchy in an exponential multi-server. Operations Research Letters 35: 421–426.Google Scholar
29.Keidar, I., Melamed, R., & Orda, A. (2009). Equicast: Scalable multicast with selfish users. Computer Networks 53(13): 2373–2386.Google Scholar
30.Kephart, J.O. & Chess, D.M. (2003). The vision of autonomic computing. Computer 36(1): 41–50.Google Scholar
31.Korilis, Y., Lazar, A., & Orda, A. (1997). Capacity allocation under noncooperative routing. IEEE Transactions on Automatic Control 42(3): 309–325.Google Scholar
32.Korilis, Y., Lazar, A., & Orda, A. (2006). Architecting noncooperative networks. IEEE Journal on Selected Areas in Communications 13(7): 1241–1251.Google Scholar
33.Korilis, Y.A., Lazar, A.A., & Orda, A. (1997). Achieving network optima using stackelberg routing strategies. IEEE/ACM Transactions on Networking 5(1): 161–173.Google Scholar
34.Koutsoupias, E. & Papadimitriou, C.H. (1999). Worst-case equilibria. In STACS 1999.Google Scholar
35.Leshem, A. & Zehavi, E. (2008). Cooperative game theory and the Gaussian interference channel. IEEE Journal on Selected Areas in Communications 26: 1078–1088.CrossRefGoogle Scholar
36.Libman, L. & Orda, A. (1999). The designer's perspective to atomic noncooperative networks. IEEE/ACM Transactions on Networking (TON) 7(6): 875–884.CrossRefGoogle Scholar
37.López, L., del Rey Almansa, G., Paquelet, S., & Fernández, A. (2005). A mathematical model for the TCP tragedy of the commons. Theoretical Computer Science 343(1–2): 4–26.Google Scholar
38.MacKenzie, A.B. & Wicker, S.B. (2001). Game theory in communications: motivation, explanation and application to power control. In IEEE Global Telecommunications Conference, San Antonio, Texas, USA, 25–29 November 2001, pp. 821–826.Google Scholar
39.Menon, R., MacKenzie, A., Hicks, J., Buehrer, R., & Reed, J. (2009). A game-theoretic framework for interference avoidance. IEEE Transactions on Communications 57(4): 1087–1098.Google Scholar
40.Mertzios, G. (2009). Fast convergence of routing games with splittable flows. In Proceedings of the 2nd International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS), Orlando, FL, USA, July, pp. 28–33.Google Scholar
41.Monderer, D. & Shapley, L.S. (1996). Potential games. Games and Econ. Behavior 14: 124–143.Google Scholar
42.Nisan, N., Roughgarden, T., Tardos, E., & Vazirani, V. (eds.) (2007). Algorithmic Game Theory. New York, NY, USA: Cambridge University Press.Google Scholar
43.Niyato, D. & Hossain, E. (2008). Competitive pricing for spectrum sharing in cognitive radio networks: dynamic game, inefficiency of NASH equilibrium, and collusion. IEEE Journal on Selected Areas of Communications 26(1): 192–202.Google Scholar
44.Niyato, D. & Hossain, E. (2008). Competitive spectrum sharing in cognitive radio networks: a dynamic game approach. IEEE Transactions on Wireless Communications 7(7): 88–94.Google Scholar
45.Orda, A., Rom, R., & Shimkin, N. (1993). Competitive routing in multi-user communication networks. IEEE/ACM Transactions on Networking 1: 510–521.Google Scholar
46.Roughgarden, T. (2005). Selfish routing and the price of anarchy. Cambridge, MA, USA: MIT Press.Google Scholar
47.Schrage, L.E. (1968). A proof of the optimality of the shortest remaining processing time discipline. Operations Research 16: 678–690.Google Scholar
48.Schrage, L.E. & Miller, L.W. (1966). The queue M/G/1 with the shortest remaining processing time discipline. Operations Research 14: 670–684.Google Scholar
49.Shenker, S.J. (1995). Making greed work in networks: a game-theoretic analysis of switch service disciplines. IEEE/ACM Transactions on Networking (TON) 3(6): 819–831.Google Scholar
50.Smith, D. (1976). A new proof of the optimality of the shortest remaining processing time discipline. Operations Research 26: 197–199.Google Scholar
51.Suris, J., DaSilva, L., Han, Z., & MacKenzie, A. (2007). Cooperative game theory for distributed spectrum sharing. In IEEE International Conference on Communications, Glasgow, Scotland, 24–28 June 2007, pp. 5282–5287.Google Scholar
52.Wang, L. & Gelenbe, E. (2015). Adaptive dispatching of tasks in the cloud. IEEE Transactions on Cloud Computing PP(99): 1.Google Scholar
53.Wang, L. & Gelenbe, E. (2015). Experiments with smart workload allocation to cloud servers. In IEEE Fourth Symposium on Network Cloud Computing and Applications, Munich, Germany, pp. 31–35, doi:10.1109/NCCA.2015.15.Google Scholar
54.Wu, T. & Starobinski, D. (2008). A comparative analysis of server selection in content replication networks. IEEE/ACM Trans. Netw. 16(6): 1461–1474.Google Scholar
55.Yaïche, H., Mazumdar, R.R., & Rosenberg, C. (2000). A game theoretic framework for bandwidth allocation and pricing in broadband networks. IEEE/ACM Transactions on Networking (TON) 8(5): 667–678.Google Scholar