A communication network routing problem: Modeling and optimization using non-cooperative game theory

Dubey, Sapana P. ; Kedar, Ganesh D. ; Ghate, Suresh H.

International Journal of Applied Mathematics and Computer Science, Tome 31 (2021) no. 1, pp. 155-164.

Résumé

We consider a communication network routing problem wherein a number of users need to efficiently transmit their throughput demand in the form of data packets (incurring less cost and less delay) through one or more links. Using the game theoretic perspective, we propose a dynamic model which ensures unhindered transmission of data even in the case where the capacity of the link is exceeded. The model incorporates a mechanism in which users are appropriately punished (with additional cost) when the total data to be transmitted exceeds the capacity of the link. The model has multiple Nash equilibrium points. To arrive at rational strategies, we introduce the concept of focal points and get what is termed focal Nash equilibrium (FNE) points for the model. We further introduce the concept of preferred focal Nash equilibrium (PFNE) points and find their relation with the Pareto optimal solution for the model.

Détail

Keywords: communication network, routing problem, game theory, focal points, Nash equilibrium, Pareto optimal solution
Mots-clés : sieć komunikacyjna, teoria gier, punkt ogniskowy, równowaga Nasha

Bibliographie

[1] [1] Altman, E., Basar, T., Jimenez, T. and Shimkin, N. (2002). Competitive routing in networks with polynomial cost, IEEE Transactions on Automatic Control 47(1): 92–96.

[2] [2] Altman, E. and Wynter, L. (2004). Equilibrium, games, and pricing in transportation and telecommunication networks, Networks and Spatial Economics 4: 7–21, DOI: 10.1023/B:NETS.0000015653.52983.61.

[3] [3] Banner, R. and Orda, A. (2007). Bottleneck routing games in communication networks, IEEE Transactions on Automatic Control 25(6): 1173–1179, DOI: 10.1109/JSAC.2007.070811.

[4] [4] Ignatenko, O.P. (2016). Game theoretic modeling of AIMD network equilibrium, Problems of Programming 25(1): 116–128.

[5] [5] Massey, W.A. (2002). The analysis of queues with time varying rate for telecommunication models, Telecommunication Systems 21: 2–4, DOI: 10.1023/A:1020990313587.

[6] [6] Nguyen, P.H., Kling, W.L. and Ribeiro, P.F. (2013). A game theory strategy to integrate distributed agent-based functions in smart grids, IEEE Transactions Smart Grid 4(1): 568–576, DOI: 10.1109/TSG.2012.2236657.

[7] [7] Orda, A., Rom, R. and Shimkin, N. (1993). Competitive routing in multi-user communication networks, IEEE/ACM Transactions on Networking 1(5): 510–521, DOI: 10.1109/90.251910.

[8] [8] Qin, X., Wang, X., Wang, L., Lin, Y. and Wang, X. (2019). An efficient probabilistic routing scheme based on game theory in opportunistic networks, Computer Networks 149: 144–153, DOI: 10.1016/j.comnet.2018.11.022.

[9] [9] Sahin, I. and Simaan, M.A. (2006). A flow and routing control policy for communication networks with multiple competitive users, Journal of the Franklin Institute 343(2): 168–180.

[10] [10] Schelling, T.C. (1960). The Strategy of Conflict, 1st Edn, Harvard University Press, Cambridge.

[11] [11] Wellons, J., Dai, L., Xue, Y. and Cui, Y. (2008). Predictive or oblivious: A comparative study of routing strategies for wireless mesh networks under uncertain demand, 5th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, San Francisco, USA, pp. 215–223, DOI: 10.1109/SAHCN.2008.35.

[12] [12] Zhang, Z., Zhang, M., Greenberg, A., Charlie Hu, Y., Mahajan, R. and Christian, B. (2010). Optimizing cost and performance in online service provider networks, 7th USENIX Symposium on Networked Systems Design and Implementation, San Jose, USA, pp. 33–47.