Informatics and Applications
2014, Volume 8, Issue 1, pp 28-35
EQUILIBRIUM PRINCIPLE APPLICATION TO ROUTING CONTROL IN PACKET DATA TRANSMISSION NETWORKS
Abstract
Annual exponential growth of data flows in large scale networks impels to search not only network
hardware improvements but also more perfect routing control algorithms. In networks, it is impossible to use
centralized algorithms of routing control. Parallel algorithms choice must be based on the principles of functional
effectiveness and stability (equilibrium). In large-scale networks, there is a huge number of users’ pairs trying
to achieve the maximally possible rate of data transmission by routing control. Thus, control must be based on
multicriteria optimization ideas and methods. The Nash equilibrium (game formulation of the routing problem)
formally presents optimality of transmission control in distributed systems. In the present paper, the equilibrium
routing is proved to exist under general conditions. The solution is additionally shown to be effective in Pareto
sense and computationally stable. An effective (quick and parallel) game theory algorithm is suggested and its
convergence is proved.
[+] References (15)
- Bertsecas, D. P., and R. Gallager. 1987. Data networks.
Englewood Cliffs: Prentice Hall. 544 p.
- Vasilyev, N. S., and V. V. Fedorov. 1996. O ravnovesnoy
marshrutizatsii v setyakh peredachi dannykh [Equilibrium
routing in data-transmission networks]. Vestn. Mosk.
Univ. Ser. 15: Vychisl. Mat. Kibern. [Bulletin of Moscow
State University. Ser. 15: Comput. Math., Cybern.] 4:47–
52.
- Korilis, Y. A., A.A. Lazar, and A. Orda. 1997. Capacity
allocation under noncooperative routing. IEEE Trans.
Automat. Contr. 42(3):309–325.
- Vasilyev, N. S. 1998. Nash equilibrious routing in ring
networks. Int. J. Math. Game Theory Algebra 7(4):221–
234.
- Vasilyev, N. S. 1997. O svoystvakh resheniy zadachi
marshrutizatsii seti s virtual’nymi kanalami [Properties of
the solutions to the problemof routing in network with virtual channels]. Zh. Vychisl. Mat. Mat. Fiz. [Computational
Mathematics and Mathematical Physics] 37(7):785–793.
- Vasilyev, N. S. 1998. O svoystvakh resheniy zadachi dinamicheskoy
marshrutizatsii seti [Properties of the solutions
to the problem of dynamic routing in networks]. Zh.
Vychisl. Mat. Mat. Fiz. [Computational Mathematics and
Mathematical Physics] 38(1):42–52.
- Sokolov, I.A., and S. Ya. Shorgin. 2001. Model’ i
matematicheskie metody rascheta kharakteristik seti, ispol’zuyushchey
tekhnologii X.25 i Frame relay [Models
and mathematical methods of characteristics calculation
for X.25 and Frame relay network]. Sistemy i Sredstva Informatiki.
Spec. vyp. “Matematicheskie metody informatiki”
[Systems andMeans of Informatics. Spec. ed. “Math.Meth.
of Informatics”]. Moscow: Nauka, Fizmatlit. 43–66.
- Vasilyev, N. S., and V. V. Fedorov. 2005. O postroenii algoritmov
marshrutizatsii paketnykh setey na osnove vektornykh
kriteriev [On routing algorithms in packet networks
on the base of vector criterias]. IzvestijaRAN.Teorija
i sistemy upravlenija [Bulletin of RAS. Theory and Control
Systems] 3:36–47.
- Vasilyev, N. S. 2008. Zadacha o kratchayshikh marshrutakh
v setyakh s peremennoymetrikoy [The shortest paths
problem in networks with changeable metric]. Vestnik
MGTU im. N. E. Baumana, Ser. Estestv. Nauki [Bulletin of
Bauman MSTU. Ser. Natural Sciences] 1:70–75.
- Konovalov, M.G. 2012. Optimizatsiya raboty vychislitel’nogo
kompleksa s pomoshch’yu imitatsionnoy modeli
i adaptivnykh algoritmov [Optimization of computational
complexwork on the base of imitationalmodels and adaptive
algorithms]. Informatika i Ee Primeneniya — Inform.
Appl. 6(1):37–48.
- Vasilyev, F. P. 1980. Chislennye metody resheniya ekstremal’nykh
zadach [Numerical methods for extremum
problems].Moscow: Nauka. 520 p.
- Ioffe, A.D., and V.M. Tihomirov. 1974. Teoriya ekstremal’nykh
zadach [Theory of extremum problems].
Moscow: Nauka. 481 p.
- Podinovskij, V. V., and V.D. Nogin. 1982. Paretooptimal’nye
resheniya mnogokriterial’nykh zadach [Pareto
optimal solutions in multicriteria problems]. Moscow:
Nauka. 256 p.
- Cristofides, N. 1975. Graph theory: An algorithmic approach.
London: Academic. 430 p.
- Fedorov, V. V. 1979. Chislennye metody maksimina [Numerical
methods of maximin]. Moscow: Nauka. 280 p.
[+] About this article
Title
EQUILIBRIUM PRINCIPLE APPLICATION TO ROUTING CONTROL IN PACKET DATA TRANSMISSION NETWORKS
Journal
Informatics and Applications
2014, Volume 8, Issue 1, pp 28-35
Cover Date
2014-03-31
DOI
10.14357/19922264140104
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
packet network; data flows; network metric; routing; vector criteria; multicriteria optimization; game
problem; Nash equilibrium; Pareto effectiveness
Authors
N. S. Vasilyev 
Author Affiliations
Bauman Moscow State Technical University, 5, 2nd Baumanskaya Str., Moscow 105005, Russian Federation
|