LABORATORY 10
Laboratory of Communications Network Theory
Head of Laboratory – Dr.Sc. (Math) Vladimir Rykov
The leading researchers of the laboratory include:
|
Dr.Sc. (Math.) |
N. Vvedenskaya |
Dr. |
N. Likhanov |
|
Dr.Sc. (Techn.) |
A. Kuznetsov |
Dr. |
V. Mikhailov |
|
Dr.Sc. (Techn.) |
I. Levshin |
Dr. |
I. Orlov |
|
Dr.Sc. (Techn.) |
B. Tsybakov |
Dr. |
A. Rubinov |
|
|
|
|
|
Directions of activity:
· network reliability theory;
· controllable queueing systems;
· multiple access packet and virtual connection communications networks;
· analysis of structure of information flows in telecommunication networks;
· coding and signal processing for storage systems;
· simulation models for hydroacustic information transmission systems.
MAIN RESULTS
Traditional for the laboratory investigations in the reliability of complex hierarchical systems were prolonged in 2004 in the direction of stochastic methods application. Especially, based on previous study the model of complex hierarchical system with different repair regimes was elaborated. Algorithms for stationary and non-stationary reliability characteristics for such systems with different repair regimes were constructed. The results were presented on the Forth International Conference on Mathematical Methods in Reliability (MMR-2004) in Santa Fe, July, 2004 (New Mexico, USA) and on the First Russian-France International Conference on Longevity, Aging and Degradation Models in Reliability, Medicine and Biology, June 2004 (LAD-2004) and were published in their Proceedings. The model for reliability control of fault tolerance units with controllable failures also was proposed jointly with algorithms and computer tools for numerical analysis. The results also were presented on the Forth International Conference on Mathematical Methods in Reliability (MMR-2004) in Santa Fe, July 2004 (New Mexico, USA), on the First Russian-France International Conference on Longevity, Aging and Degradation Models in Reliability, Medicine and Biology, June 2004 (LAD-2004) and on the XXIV International Seminar on Stability Problems for Stochastic Models, and were published in their Proceedings. Now the investigations are continuing in direction for elaboration of computer tools of reliability of complex hierarchical systems analysis. (V. Rykov, Ph.D. students).
With the aim of investigation of structural reliability of telecommunication networks methods for comparing of graphs were proposed. The method is based on comparing of elements and structure of their sub-graphs. Discriminant metrics for graphs are studied and effective for tree-type graphs comparing algorithms are proposed. The results also could be applied for chenical structures comparing. As an additional network reliability measure the number of 2-cuts was considered. In the class of 2-connectrd 2-tree graphs a graph with maximal number of 2-cuts was found. Another additional measure of network structural reliability is a number of graph’s skeletons. In a class of 2-connected 2-tree graphs a sub-class of graphs with mimimal number of skeletons was found. This sub-class is characterisecl with minimal releability. (A. Rubinov, V. Petrunin).
Another direction of activity of this group is an investigation of controllable queueing systems. Especially, the previous investigations of controllable multi-servers systems with heterogeneous servers were continued in 2004. New criteria, more general input (Markov arrival processes – MAP) and service time distributions (PH-distributions) were involved into investigations. The model has numerous applications including those for the calls routing in computer communication systems. The qualitative properties of optimal policies were studied. It was shown that in this case also as in a Markov case the optimal control policy for such systems has a threshold property and require to use the best (fastest or most economical) server among non-busy if necessary. These results were obtained partially by analytical methods, partially with the help of specially elaborated computer tools. The numerical experiments show an essential stability of optimal policies with respect to structure of input flows and service times distributions. The results of study were used in PhD Thesis, and were published in series of papers. (V. Rykov, Ph.D. students).
The next direction of investigations concerns to study of non-stationary input processes. It is well known that the input information in computer communication systems is characterized by essential non-stationary properties. The connection between non-stationary Poisson Process (NPP) and Almost Luck of Memory (ALM) distributions were studied. This connection gives both the new knowledge about structure and the behavior of NPP and the effective approach it for statistical analysis of such processes. For a real statistical analysis of NPP and ALM-distributions algorithms, computer procedures and tools were elaborated. The results were proposed on Hawaii International Conference on Statistics and Related fields and were published in their Proceedings. (V. Rykov).
Implementation possibility of the shortest path routing algorithms in BISDN was investigated. Sensitivity of this algorithms to the traffic parameters changing was considered. It was shown that in some special cases of the network topology "oscillations" can occur when final routing plan becomes unsatisfactory. A new method of avoidance for such "unpleasant" situations was proposed. The main parameters of the shortest path algorithms, such as complexity, fastness and so on, was investigated also. (V. Mikhailov).
For the feedforward arbitrary configuration network and On/Off traffic N. Likhanov developed approach to estimate packet loss and buffer overflow probabilities for any given node of the network. This result is an essential generalization of the previously obtained results for the case of separately analyzed node. Developed analytical results give possibility to obtain network performance parameters with minimal computer complexity and they are also useful for the quality analysis of the considered systems.
Vvedenskaya N. D. continued the investigations of large networks with dynamic routing. A paper about a network with large number of servers that may be temporary broken is prepared for the publication. It is shown that when a call is directed to a least loaded selection out of two randomly selected servers the probability of large queues at the servers decreases superexponentially, but it turned out that the mean number of idle servers with non-empty queue in such network with dynamic routing is larger then in a network where the servers are selected randomly. A Markov model of a queueing system with large number of sources directing packeted calls to one server with a (large) buffer was considered in case where the TCP protocol is used. The equations that describe the distribution of the calls lengths and of the free buffer space are presented and investigated. Using the methods of large deviations we investigated the probability of large calls delay in a system with two servers and three Poissson flows. The case of general service time distribution is considered. In our model the calls from the first and the second flows are directed to the first and second servers correspondingly while the calls of the third flow are directed to the server that is least busy at the time of a call from arrival upon the system. The explicit formulas for the main term of logarithm of large delay probability for the virtual message put into the third flow are presented. The simulations of the system performance show that these formulas give good predictions for the logarithm of probability of the moderate delay.
It was considered the problem of orthogonal variable spreading. Walsh-code assignments for the users of the wireless network. Considered assignments use a partition of all users into several pools. Each pool can use its own codes that are different for different pools. Each user has only a few codes assigned to it within the pool. It was defined matrix M which depends on n, the number of users in a pool; k, the total number of Walsh codes in the pool; and l, the number of Walsh codes assigned to each user within the pool. It was constructed matrix M, which has the assignment property defined in the paper. Necessary condition of existence of matrix M with assignment property was proved. Two constructions of such M was presented. The constructions are optimal in the sense that they give the minimal number l for given n and k. The implementation complexity associated with the presented optimal assignment was found. (B. Tsybakov).
Iterative detection has generated strong interest in the signal processing area of the disc drive industry, nevertheless of this technology has been rather limited. In the project completed by A. V. Kuznetsov in 2004, he review the benefits that the most interesting iterative detectors have over the industry standard partial response maximum-likelihood (PRML) detectors, and examine the hardware complexity issues that have so far stood in the way of practical implementation. The results of this research were published in a chapter in the book and the US patent present earlier results on application of combinatory designs for the design and implementation of iterative detection channels based on Low Density Parity Check (LDPC) codes.
The method of the underwather sound transmission channel capacity (on Shannon sense) estimation is elaborated of I. P. Levshin. The method is based on information technology of the Monte-Karlo simulation of the second order random field. The energy and correlation characteristics of the random underwather sound field is based on the radiation transport equation with the hidrophisics parameters of the ocean media as the coefficients this equation. The graphs of the capacity of the partial ray tubes with given theoretical statistics and of the real path underwather sound propagation is demonstrated.
Work with young scientists
Rykov V. – professor of the department of Applied Mathematics and Computer Modeling Russih State OIL and Gas University after I.M. Gubkin. Supervisor of 3 Ph.D students and 3 Master Degree students. In 2004 one Ph.D student prepare his Thesis and 1 Tex-book was printed.
Mikhailov V. – associate professor Moscow Institute of Phisics and Technology.
Likhanov N. – associate professor Moscow Institute of Phisics and Technology. Supervisor of 4 Ph.D students and 3 Master Degree students.
GRANTS FROM:
· Russian Basic Research Foundation (No. 02-01-00068): "Asymptotic methods for multi-component systems analysis of statistical physics for queueing systems" (N. D. Vvedenskaya, together with the Dobrushin's laboratory).
· Russian Basic Research Foundation (No.04-07-901156). “Development of methods and Computer tools for investigation of information flows in telecommunication networks on the base of regenerative approach”. V. Rykov.
· Russian Basic Research Foundation (No.04-01-10549-з) Travel Grant. “International Conference on Mathematical Methods in Reliability Theory (MMR-2004). V. Rykov.
Publications in 2004
Books, monographs, text-books
1. Рыков В.В. Надежность технических систем и техногенный риск. М.: РГУ нефти и газа им. И. М. Губкина, 2004.
2. Vasic B., Kurtas E., Kuznetsov A. V., Milenkovic O. Structured Low-Density Parity-Check Codes. Chapter in the book Signal Processing and Coding For Recording Systems. Еds. B. Vasic, E. Kurtas. CRC Press, 2004.
1. Ефросинин Д.В. Управляемые системы массового обслуживания с неоднородными приборами. Диссертация на соискание ученой степени к.ф.-м.н. РУДН, 2004.
2. Левшин И.П. Параллельный алгоритм решения системы дифференциальных уравнений 2-го порядка в задачах определения траекторий лучей при подводном распространении звука. Труды II Международной конференции Параллельные вычисления и задачи управления. М: ИПУ РАН, PACO’2004, 4-6 октября 2004 г., стр. 101-109.
3. Левшин И.П. Пропускная способность гидроакустического канала передачи информации. Труды VII Международной конференции Прикладные технологии гидроакустики и гидрофизики. C-Петербург: Морфизприбор, 8-10 июня 2004 г., стр. 337-341.
4. Петрунин В.И., Полесский В.П. 2-связанный 2 лесистый граф с заданным числом вершин и ребер с минимальным числом остовов. Информационные процессы, 2004, том 4, № 4, стр. 275-283.
5. Петрунин В.И., Полесский В.П. 2-связанный 2-лесистый граф с заданным числом вершин и ребер с максимальным числом 2-разрезов. Информационные процессы, 2004, том 4, № 4, стр. 261-268.
6. Рубинов А.Р. Методы прогноза пассажиропотоков. Железнодорожный транспорт, 2004, № 1, стр. 50-56.
7. Dimitrov B., Green D., Rykov V., Stanchev P. Reliability Model for Biological Objects. Longevity, Aging and Degradation Models. Transactions of the First Russian-French Conference LAD-2004. Saint Petersburg , June 7-9, 2004, Ed. V. Antonov, C. Huber, M. Nikulin, V. Polischook, Saint Petersburg State Politechnical University, SPB, 2004, vol. 2, pp. 230-240.
8. Dimitrov B., Krougly Z., Rykov V. Periodic Poisson Processes and Almost-luck of memory Diostrivbutions. Autom. And Remote Control, 2004, vol. 65, no. 10, pp. 1597-1610.
9. Lynch R., Kurtas E.M., Kuznetsov A.V., Yeo E., Nikolić B. The Search for a Practical Iterative Detector for Magnetic Recording. IEEE Trans. on Magnetics, 2004, vol. 40, No. 1.
10. Ozturk O., Mazumdar R., Likhanov N. Many sources asymptotics for networks with small buffers. Queueing Systems, 2004, 46, pp. 129-147.
11. Rykov V., Buldaeva E. On reliability control of fault tolerance units: regenerative approach. Transactions of XXIV International Siminar on Stability Problems for Stochastic Modes, September 10-17, 2004, Jurmala, Latvia. Transport and Telecommunication Institute, Riga, Latvia, 2004.
12. Rykov V., Efrosinin D. Optimal Control of Queueing Systems with Heterogeneous Servers. Queueing Systems: Theory and Applications, 2004, vol. 46, pp. 389-407.
13. Rykov V., Efrosinin D. Reliability Control of Biological Systems with failures. Longevity, Aging and Degradation Models. Transactions of the First Russian-French Conference LAD-2004. Saint Petersburg, June 7-9, 2004, Ed. V. Antonov, C. Huber, M. Nikulin, V. Polischook, Saint Petersburg State Politechnical University, SPB, 2004. vol. 2, pp. 241-255.
14. Tsybakov B. On Walsh code assignment. IEEE Transactions on Information Theory, 2004, vol. 50, no. 6, pp.1073-1078.
15. Vvedenskay N.D., Duffy K., Malone D., Pechersky E.A., Syhov Y.M. Large deviation provide good approximation to queueing system with dynamic routing. Preprint. Dublin Institute for Advanced Studies, 2004, DIAS-STP-04-15.
16. Vvedenskaya N.D., Pechersky E.A., Syhov Y.M. Large deviation in two-server system with dynamic routing. Preprint. Network Institute for Math. Sci., Cambridge, UK, 2004, no. I 03075-IGS.
Accepted papers
1. Rubinov A.R. Diversity of synthetically accessible compounds. Journal of Computer-Aided Molecular Design.
Thesis
1. Vvedenskaya N.D., Pechersky E.A., Syhov Y.M. Large devilation in two- server system with dynamic routing. IEEE International Symposium on Information Theory. Proceedings, 2004, p. 114.
2. Dimitrov B., Green D., Rykov V., Stanchev P. Reliability of complex hierarchical fault tolerance systems. Thesis of the International Conference MMR-2004. Santa Fe (U.S.A.), June 21-25, 2004. Published on CD.
3. Петрунин В.И. Эвристика выбора минимальных путей и минимальных разрезов для оценок двухполосной надежности. Тезисы докладов V Международного семинара "Информационные сети, системы и технологии". Москва, 26-27 октября 2004 г., с.174-178.
4. Rykov V., Efrosinin D. Reliability control of fault tolerance units. Thesis of the International Conference MMR-2004. Santa Fe (U.S.A.), June 21-25, 2004. Published on CD.
5. Rykov V.V., Stepanov D.V., Lepikhin A.N., Minenko R.A. Decision Support System for Reliability Analysis. Accepted by International Conference on Stochastic Models in Reliability, Safety, Security and Logistics (SMRSSL’05). 16-18 February 2005, Beer Sheva, Israel.