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

• Autorzy: Dubey Sapana P. , Kedar Ganesh D. , Ghate Suresh H.

Identyfikatory

DOI

10.34768/amcs-2021-0011

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

communication network; routing problem; game theory; focal points; Nash equilibrium; Pareto optimal solution

PL

sieć komunikacyjna; teoria gier; punkt ogniskowy; równowaga Nasha

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2021
• Tom: Vol. 31, no. 1
• Strony: 155--164
• Opis fizyczny: Bibliogr. 12 poz., rys., tab.

Twórcy

autor

Dubey Sapana P.

• Department of Applied Mathematics, Priyadarshini Institute of Engineering and Technology, Priyadarshini Campus, Digdoh Hills, Hingna Road, Nagpur, 440019 India

autor

Kedar Ganesh D.

• Department of Mathematics, RTM Nagpur University, Amravati Road, Nagpur, 440033 India

autor

Ghate Suresh H.

• Department of Mathematics, RTM Nagpur University, Amravati Road, Nagpur, 440033 India

Bibliografia

• [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] 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] 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] Ignatenko, O.P. (2016). Game theoretic modeling of AIMD network equilibrium, Problems of Programming 25(1): 116–128.
• [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] 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] 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] 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] 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] Schelling, T.C. (1960). The Strategy of Conflict, 1st Edn, Harvard University Press, Cambridge.
• [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] 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.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).