Comparison of Router Intelligent and Cooperative Host Intelligent Algorithms in a Continuous Model of Fixed Telecommunication Networks
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.
<p>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.</p>
<p>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.</p>
@article{"International Journal of Electrical, Electronic and Communication Sciences:65042", author = "Dávid Csercsik and Sándor Imre", title = "Comparison of Router Intelligent and Cooperative Host Intelligent Algorithms in a Continuous Model of Fixed Telecommunication Networks", 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", volume = "7", number = "9", pages = "1161-9", }
