Research Interests:

• Performance Evaluation and Optimization of TCP/IP
• Mathematical Analysis of Google PageRank
• Theory of Singular and Analytic Perturbations
• Singularly Perturbed Markov Chains and Decision Processes
• Queueing Theory
• Iterative Learning Control
• Miscellaneous

TCP/IP is a reliable transport protocol responsible for the Internet traffic congestion control. For instance, Web browsing and FTP applications are based on TCP. We are interested in the performance evaluation of the TCP/IP networks in terms of packet losses, packet delays, throughputs and latencies of file transfers.

• K. Avrachenkov, U. Ayesta, and A. Piunovskiy, Optimal choice of the buffer size in the Internet routers, Proceedings of IEEE CDC/ECC'05, pp.1143-1148, Seville, Spain, December 2005.
• E. Altman, K.E. Avrachenkov, and B. J. Prabhu, Fairness in MIMD congestion control algorithms, Proceedings of IEEE INFOCOM 2005, Miami, March 2005. An extended version has appeared in Telecommunication Systems, v.30(4), pp.387-415, 2005.
• K.E. Avrachenkov, U. Ayesta, P. Brown, and E. Nyberg, Differentiation between Short and Long TCP flows: Predictability of the response time, Proceedings of IEEE INFOCOM 2004, Hong Kong.
• E. Altman, K.E. Avrachenkov, C. Barakat and R. Nunez-Queija, State-dependent M/G/1 Type Queueing Analysis for Congestion Control in Data Networks, Proceedings of IEEE INFOCOM 2001, Anchorage, Alaska, pp.1350-1359. A more detailed version: CWI report PNA-R0005.
• E. Altman, K.E. Avrachenkov and C. Barakat, A stochastic model of TCP/IP with stationary random losses, ACM SIGCOMM 2000, Stockholm, Sweden. An extended version has appeared in IEEE/ACM Trans. on Networking, v.13(2), April 2005, pp.356-369.
• E. Altman, K.E. Avrachenkov and C. Barakat, Impact of bursty losses on TCP performance, Performance Evaluation, v.42, no.2-3, pp.129-147, October 2000, also in the Proceedings of ACM SIGMETRICS 2000.

Back to the top

Google search engine lists Web pages according to their PageRank which reflects popularity of a page. From mathematical point of view, the PageRank is a stationary distribution of a Markov chain whose state space is the set of all pages and transition matrix is a convex combination of a hyperlink matrix and a uniform perturbation matrix. Thus, Google is a wonderful application of Markov chain theory and perturbation theory.

• K. Avrachenkov, N. Litvak, and K.S. Pham, Distribution of PageRank Mass Among Principle Components of the Web, Proceedings of the 5th Workshop on Algorithms and Models for the Web-Graph (WAW2007), also Arxiv extended version, September 2007.
• K. Avrachenkov and D. Lebedev, PageRank of Scale Free Growing Networks, Internet Mathematics, v.3, no.2, pp.207-231, 2006, also INRIA Research Report no. 5858, March 2006.
• K. Avrachenkov, N. Litvak, D. Nemirovsky, and N. Osipova, Monte Carlo methods in PageRank computation: When one iteration is sufficient, SIAM Journal on Numerical Analysis, v.45, no.2, pp.890-904, 2007, also University of Twente Research Report, February 2005.
• K.E. Avrachenkov and N. Litvak, The effect of new links on Google PageRank, Stochastic Models, v.22, no.2, pp.319 - 331, 2006. Also INRIA Research Report no. 5256, July 2004.
• K.E. Avrachenkov and N. Litvak, Decomposition of the Google PageRank and optimal linking strategy, INRIA Research Report no. 5101, January 2004.

Back to the top

Analytic perturbation theory deals with a wide spectrum of mathematical problems (e.g., the inversion of linear operators, the eigenvalue problems, the systems of linear and nonlinear equations, mathematical programming) whose data depend analytically on a "small" perturbation parameter. There are at least two motivations to study this class of problems. Firstly, it is often necessary to describe the behaviour of a problem solution with respect to the change of its parameters. Secondly, admitting that we never have precise data, it is of great importance to analyse the influence of data perturbations. Sometimes even small perturbations of the data cause dramatic changes in the properties of the problem. The latter case is called the singular perturbation and it is of particular interest for our research.

• K.E. Avrachenkov, Analytic Perturbation Theory and its Applications, (compressed postscript file), University of South Australia, 1999.

• K.E. Avrachenkov and M. Haviv, Perturbation of null spaces with application to the eigenvalue problem and generalized inverses, Linear Algebra and its Applications, v.369, pp.1-25, 2003.
• K.E. Avrachenkov and J.B. Lasserre, Analytic perturbation of Sylvester and Lyapunov matrix equations, IEEE CDC 2000, Sydney, Australia, pp.1968-1973. An extended version is appeared in IEEE Trans. Auto. Contr., v.47, no.7, pp.1116-1119, 2002.
• J.A. Filar, E. Altman and K.E. Avrachenkov, An asymptotic simplex method for singularly perturbed linear programs, Operations Research Letters, v.30, no.5, pp.295-307, October 2002.
• K.E. Avrachenkov, M. Haviv and P.G. Howlett, Inversion of analytic matrix functions that are singular at the origin, SIAM Journal on Matrix Analysis and Applications, v.22, no.4, pp.1175-1189, 2001.

Back to the top

Here we apply the results of the general analytic perturbation theory to singularly perturbed Markov chains and Markov decision processes. The singularly perturbed Markov chain is an appropriate model for a complex stochastic system which consists of several weakly connected subsystems.

• E. Altman, K.E. Avrachenkov, and R. Nunez-Queija, Perturbation Analysis for Denumerable Markov Chains with Application to Queueing Models, Advances in Applied Probability, v.36, no.3, September 2004.
• K.E. Avrachenkov and M. Haviv, The first Laurent series coefficients for singularly perturbed stochastic matrices, Linear Algebra and its Applications, v.386, pp.243-259, July 2004.
• K.E. Avrachenkov, J.A. Filar and M. Haviv, Singular perturbations of Markov chains and decision processes. A Survey, a chapter in Handbook of Markov Decision Processes: Methods and Applications, (eds) E.A. Feinberg, A. Shwartz, v.40 in the series "International Series in Operations Research and Management Science", Kluwer Academic Publishers, pp.113-153, January 2002.
• K.E. Avrachenkov, Singularly perturbed finite Markov chains with general ergodic structure, in Discrete Event Systems: Analysis and Control, R. Boel and G. Stremersch (Eds.), pp.429-432, Kluwer, 2000.

Back to the top

One can still obtain new interesting results for classical queueing models...

• E. Altman, K. Avrachenkov and U. Ayesta, A survey on discriminatory processor sharing Queueing Systems, v.53(1-2), pp.53-63, 2006.
• K. Avrachenkov, U. Ayesta, P. Brown, R. Nunez-Queija, Discriminatory processor sharing revisited, Proceedings of IEEE INFOCOM 2005, Miami, March 2005.
• K. Avrachenkov, U. Ayesta and P. Brown, Batch arrival processor-sharing with application to multi-level processor sharing scheduling, Queueing Systems, v.50(4), pp.459-480, 2005.
• K.E. Avrachenkov, N.O. Vilchevsky, and G.L. Shevlyakov, Priority queueing with finite buffer size and randomized push-out mechanism, Performance Evaluation, v.61(1), pp.1-16, 2005.

Iterative learning control (ILC) is designed to improve the performance of a cyclic system. The basic idea of ILC is to correct the control input for the next cycle using the information about the error from the current and previous cycles. If the unknown part of the system can be represented as a regular perturbation, then we propose to use fast convergent quasi-Newton-type methods. However, if the unknown part of the system is a singular perturbation, then we recommend to use robust methods based on H-infinity controller design.

Selected publications:

• K.E. Avrachenkov and R.W. Longman, Iterative learning control for over-determined, under-determined, and ill conditioned systems, Int. J. Appl. Math. Comput. Sci., v.13, no.1, pp.113-122, 2003.
• K.E. Avrachenkov, H.S.M. Beigi, and R.W. Longman, Updating procedures for iterative learning control in Hilbert space, Intelligent Automation and Soft Computing, v.8, no.2, pp.183-189, 2002.
• K.E. Avrachenkov, Iterative learning control based on quasi-Newton methods, IEEE CDC'98 Proceedings, 1998.
• K.E. Avrachenkov and A.A. Pervozvanskii, Iterative learning control for singularly perturbed systems, (extended version), Proceedings of ILC workshop, 1998.
• A.A. Pervozvanskii and K.E. Avrachenkov, Learning control algorithms: convergence and robustness, Proceedings of Australian Control Conference, pp.366-371, October 1997.

Back to the top

This is a panopticon of cute results that cannot be classified into any of the above topics.

• J.B. Lasserre and K.E. Avrachenkov, Integration on a simplex: The multi-dimensional version of $\int_a^b x^p dx$, Amer. Math. Monthly, v.108, pp.151-154, February 2001.
• K.E. Avrachenkov and E. Sanchez, Fuzzy Markov Chains and Decision-Making, Fuzzy Optimization and Decision Making, v.1, no.2, pp.143-159, June 2002.

Back to the top