Comparison of Router Intelligent and Cooperative Host Intelligent Algorithms in a Continuous Model of Fixed Telecommunication Networks

Authors: Dávid Csercsik, Sándor Imre

Abstract:

The performance of state of the art worldwide telecommunication networks strongly depends on the efficiency of the applied routing mechanism. Game theoretical approaches to this problem offer new solutions. In this paper a new continuous network routing model is defined to describe data transfer in fixed telecommunication networks of multiple hosts. The nodes of the network correspond to routers whose latency is assumed to be traffic dependent. We propose that the whole traffic of the network can be decomposed to a finite number of tasks, which belong to various hosts. To describe the different latency-sensitivity, utility functions are defined for each task. The model is used to compare router and host intelligent types of routing methods, corresponding to various data transfer protocols. We analyze host intelligent routing as a transferable utility cooperative game with externalities. The main aim of the paper is to provide a framework in which the efficiency of various routing algorithms can be compared and the transferable utility game arising in the cooperative case can be analyzed.

Keywords: Routing, Telecommunication networks, Performance evaluation, Cooperative game theory, Partition function form games

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1087668

References:

1] S. Ryu, C. Rump, and C. Qiao, “Advances in internet congestion control,” Communications Surveys Tutorials, IEEE, vol. 5, no. 1, pp. 28 –39, quarter 2003.
[2] H. Wedde and F. Muddassar, “A comprehensive review of nature inspired routing algorithms for fixed telecommunication networks,” Journal of Systems Architecture, vol. 52, no. 8, pp. 461–484, Aug. 2006. (Online). Available: http://dx.doi.org/10.1016/j.sysarc.2006.02.005
[3] E. Altman, T. Boulognea, R. El-Azouzi, T. Jimenez, and L.Wynter, “A survey on networking games in telecommunications,” Computers & Operations Research, vol. 33, pp. 286 – 311, 2006.
[4] J. Nash, “The bargaining problem,” Econometrica, vol. 18, pp. 155 – 62, 1950.
[5] H. Park and M. van der Schaar, “Bargaining strategies for networked multimedia resource management,” Signal Processing, IEEE Transactions on, vol. 55, no. 7, pp. 3496 –3511, july 2007.
[6] C. Touati, E. Altman, and J. Galtier, “Utility based fair bandwidth allocation,” in Proceedings of the IASTED International Conference on Networks, Parallel and Distributed Processing and Applications (NPDPA 2002), 2002, pp. 126–131.
[7] ——, “Generalized Nash bargaining solution for bandwidth allocation,” Computer Networks, vol. 50, no. 17, pp. 3242 – 3263, 2006.
[8] H. Yaiche, R. Mazumdar, and C. Rosenberg, “A game theoretic framework for bandwidth allocation and pricing in broadband networks,” Networking, IEEE/ACM Transactions on, vol. 8, no. 5, pp. 667 –678, oct 2000.
[9] R. Mazumdar, L. Mason, and C. Douligeris, “Fairness in network optimal flow control: optimality of product forms,” Communications, IEEE Transactions on, vol. 39, no. 5, pp. 775 –782, may 1991.
[10] F. Kelly, “Charging and rate control for elastic traffic,” European Transactions on Telecommunications, vol. 8, no. 1, pp. 33–37, 1997.
[Online]. Available: http://dx.doi.org/10.1002/ett.4460080106
[11] C. Douligeris and R. Mazumdar, “A game theoretic perspective to flow control in telecommunication networks,” Journal of the Franklin Institute, vol. 329, no. 2, pp. 383 – 402, 1992. (Online). Available: http://www.sciencedirect.com/science/article/pii/001600329290041E
[12] R. Johari, S. Mannor, and J. Tsitsiklis, “A contract-based model for directed network formation,” Games and Economic Behavior, vol. 56, no. 2, pp. 201 – 224, 2006.
[13] E. Arcaute, R. Johari, and S. Mannor, “Network formation: Bilateral contracting and myopic dynamics,” in Internet and Network Economics, ser. Lecture Notes in Computer Science, X. Deng and F. Graham, Eds. Springer Berlin Heidelberg, 2007, vol. 4858, pp. 191–207.
[14] W. Saad, Z. Han, M. Debbah, and A. Hjorungnes, “Network formation games for distributed uplink tree construction in ieee 802.16j networks,” in Global Telecommunications Conference, 2008. IEEE GLOBECOM 2008. IEEE, 30 2008-dec. 4 2008, pp. 1 –5.
[15] W. Saad, Z. Han, T. Basar, M. Debbah, and A. Hjorungnes, “A selfish approach to coalition formation among unmanned air vehicles in wireless networks,” in Game Theory for Networks, 2009. GameNets ’09. International Conference on, may 2009, pp. 259 –267.
[16] W. Saad, Z. Han, M. Debbah, A. Hjorungnes, and T. Basar, “Coalitional game theory for communication networks,” Signal Processing Magazine, IEEE, vol. 26, no. 5, pp. 77 –97, september 2009.
[17] W. Saad, Z. Han, M. Debbah, and A. Hjorungnes, “A distributed merge and split algorithm for fair cooperation in wireless networks,” in Communications Workshops, 2008. ICC Workshops ’08. IEEE International Conference on, may 2008, pp. 311 –315.
[18] W. Saad, “Coalitional game theory for distributed cooperation in next generation wireless networks,” Ph.D. dissertation, University of Oslo, 2010.
[19] W. Saad, Z. Han, M. Debbah, A. Hjorungnes, and T. Basar, “Coalitional games for distributed collaborative spectrum sensing in cognitive radio networks,” in INFOCOM 2009, IEEE, april 2009, pp. 2114 –2122.
[20] J. Wardrop, “Some theoretical aspects of road traffic research,” Proc. Inst. Civ. Eng., vol. 1, pp. 325 – 378, 1952.
[21] T. Roughgarden, Selfish Routing and the Price of Anarchy. 55Hayward Street Cambridge, MA 02142-1493 USA: MIT Press, 2005.
[22] ——, “Selfish routing and the price of anarchy,” Department of Computer Science, Stanford University, Tech. Rep., Jan. 2006. (Online). Available: http://theory.stanford.edu/ tim/papers/optima.pdf
[23] R. Thrall and W. Lucas, “n-person games in partition function form,” Naval Research Logistics Quarterly, vol. 10, no. 4, pp. 281–298, Dec. 1963.
[24] L. Á. Kóczy, “A recursive core for partition function form games,” Theory and Decision, vol. 63, no. 1, pp. 41–51, August 2007.
[25] ——, “Sequential coalition formation and the core in the presence of externalities,” Games and Economic Behavior, vol. 66, no. 1, pp. 559– 565, May 2009.