LABORATORY 10
Laboratory of Communications Network Theory
Head of Laboratory – Dr.Sc.
(Mathematics) Valerii Polesskii
The leading researchers of the laboratory include:
|
Dr.Sc. (Math.) |
N. Vvedenskaya |
Dr. |
V. Mikhailov |
|
|
Dr.Sc. (Techn.) |
A. Kuznetsov |
Dr. |
I. Orlov |
|
|
Dr.Sc. (Techn.) |
I. Levshin |
Dr. |
V. Polyakov |
|
|
Dr.Sc. (Techn.) |
B. Tsybakov |
Dr. |
A. Rubinov |
|
|
Dr. |
N. Likhanov |
Dr. |
S. Fedortsov |
|
Directions of activity:
·
network reliability theory;
·
self-similar traffic in ATM networks;
·
multiple access packet communications networks;
·
asymptotical investigation of large queuing systems;
·
coding and signal processing for storage systems;
·
imitational processes for hydroacustic information transmission systems.
MAIN RESULTS
V. P.
Polesskii’s works belong to the mathematical theory of reliability. He works in
the theory more than thirty years. This experience allowed to him to declare
existing some independent subject in the theory. It is "the theory of
bounds on network reliability". Polesskii gave its qualitative description
[3].
The bounds on
the monotone structure reliability lie in the beginning of the theory. V. P.
Polesskii constructed some combinatorial base for the existing bounds and developed
new results that are generalization and improvement of the existing results.
The
combinatorial base contains (revealed by Polesskii) some untying transformation
of clutter-family supports and the fact that the transformation does not
decrease the clutter-sum reliability. Such a reliability generalizes the
classical monotone structure reliability. The following network reliability
measure can be an example. It is the probability that there exists a connection
between some central vertex and at least one peripheral vertex from a vertices
group. Polesskii developed record bounds on the clutter-sum reliability.
P. V. Polesskii
developed new, record, efficiently computable bounds on the monotone structure
reliability also. The existing inclusion-exclusion bounds (the Bonferroni’s
bounds) and the classical Esary-Proschan bounds demand all knowledge of the
clutter. It is not good since the network clutter size can grow exponentially
with the network size.
The existing
packing bounds are efficiently computable, however, they depand on selecting
"good" packings and are week. Arbitrary subclutter can not be used to
estimate the monotone structure reliability since its reliability calculation
demands the full enumeration (i.e., a large time).
The new bounds
use principally arbitrary subclutter, for example, the subclutter of the most
or least reliable paths or cuts, respectively.
Using the
bounds Polesskii developed new, record, efficiently computable bounds on the
k-terminal and two-terminal network reliability also. In contrast to the
packing bounds, using packings of paths (cuts), the new bounds use
"quasi-packings". They are arbitrary path (cut) families obtained by
addition of paths (cuts) to the packings. The new members are met and meet
members of the packings, generally.
With the
current interest in offering differentiated Quality of Service (QoS) in high
speed networks there is an increasing interest in service disciplines such as
Head of Line (HOL) priority and Generalized Processor Sharing (GPS) or Weighted
Fair Queueing (WFQ).One of the reasons for the attractiveness of the GPS policy
is the service protection property in that each buffer is guaranteed a minimum
server capacity or bandwidth but may receive more if other buffers are empty.
In which case the residual capacity is reapportioned to the nonempty buffers
according to the GPS weights. Large buffer asymptotic in buffers served
according to the GPS policy was found by N. B. Likhanov. The heterogeneous
session arrival model in each buffer have been
considered. Obtained results give the order of the queue length decay asymptotic.
N. D.
Vvedenskaya consideres the models of queueing systems using in her considerations
asymptotical approach. These investigations can be used to estimate the large
system performance parameters because the parameters of asymptotic dynamical
systems are close to thouse of finite systems defined by Markov processes. The
Jachson networks and fast Jachson networks are investigated in case where fue
service time of tasks in constant. Also asymptotical methods are used to
consider TCP-type system with large number of uses (windows) and one buffer.
Sure the asymptotical problem is reduced to a dynamical system with different
time shaling for different variables (in other words a problem with fast and
slow variables in considered.
A new random
process was presented by B. S. Tsybakov. This process is a generalization of
the known Cinlar semiregenerative process and process presented by B. S.
Tsybakov (Problems of Information Transmission, vol. 29, No. 2, pp. 163-175,
1993). The introduced process has the cycles as the regenerative process.
However, the cycle stopping time is not the Markov moment of the process. It
can not be computed with the known previous values of the process. The theorem,
which is similar to the Smith regenerative process theorem, is given. It was
shown how to apply this theorem for calculation of mean packet delay and
transmission rate for random multiple access stack and part-and-try algorithms
in their supercritical regions. The results are presented as analytical
equations and curves showing delays and rates as the functions of incoming
traffic rate. They show, in particular, that the part-and-try algorithm has the
maximum throughput among all known random multiple-access algorithms not only
in the region where it transmits the packets with finite mean delay (as it was
known before) but also in total span of input traffic rates. The results of
this research were published in [10].
A. V. Kuznetsov
developed low density parity-check codes constructed from Steiner system, and
their application in perpendicular magnetic recording.
The cycle of
the research of the underwater communication problems is developed (1997-2001).
The characteristics of the acoustic signals in the underwater communication
systems are investigated and simulation models of the sofisticated information
technics systems construction are considered. The theoretic basis of the
phenomena models on the underwater channel communication is developed and
generalized. This models are adequate reflection of the ocean media influense
on the thin structure and the statistical characteristics of the information
signals and the methods of the theory of the stochastic timevariant channels
for the optimal information transmission systems investigation and construction
are and ensure employed. The effective algorithms to be ensure succses of the
simulation model on the modern computers are developed. The result of the
investigations at the monograf preparated.
GRANTS FROM:
·
Russian Basic
Research Foundation (No. 99-01-00003): "Mathematical methods of
classical statistical mechanics and their applications to multicomponent
queueing systems" (project leader N. D. Vvedenskaya).
Publications in 2001
1. Polesskii V.P.
Untying clutter-family supports and its role for monotone-structure reliability
theory // Probl. Peredachi Inf. 2001. V. 37. No. 2. P. 62-76.
2. Krivoulets
V.G., Polesskii V.P. Quasipacking bounds for network reliability // Information
Processes. 2001. V. 1. No. 2. P. 126-146. http://www.jip.ru
.
3. Krivoulets
V.G., Polesskii V.P. What is theory of bounds for network reliability? //
Information processes. 2001. V. 1. No. 2. P. 199-203. http://www.jip.ru .
4. Krivoulets
V.G., Polesskii V.P. Monotone structures. The best possible bounds of their
reliability // Information processes. 2001. V. 1. No. 2. P. 188-198.
5. Krivoulets
V.G., Polesskii V.P. On bounds for monotone structure reliability. Probl.
Peredachi Inf. 2001., V. 37. No. 4. P. 121-138.
6. Kotopoulas,
Likhanov N., Mazumdar R. Asymptotic analysis of GSP systems fed by heteregeneous
long-tailed sources // IEEE INFOCOM 2001, Anchorage, USA, 2001. P. 299-308.
7. Vvedenskaya
N.D. Asymptotic and numerical method of queueing system investugations // Dr.
Thesis Phis. Math. s.c.i. 2001, 35 p.
8. Vvedenskaya
N.D., Suhov Yu.M. Differential equations arising in queueing theory //
Functional Differential Equations. 2001. V. 8. No. 3-4. P. 447-457.
9. Adjih C.,
Jacquet Ph., Vvedenskaya N. Performance evaluation of a single queue under
multi-user TCP/IP connections // Rapport de recherche, INRIA, Rocquencourt, France, p.
1-40.
10. Tsybakov B. One stochastic process and its application to multiple
access In supercritical region. IEEE Transactions on Information Theory. 2001.
V. 47. No. 4. P. 1561-1569,
11. Tsybakov B. Probability of heavy traffic period in third
generation CDMA mobile communication // Mobile Networks and Applications. 2001.
V. 6. No. 5. P. 463-470.
12. Kuznetsov A.V. Coded Modulation for EEPR4 and MEEEPR4 Channels //
IEEE Trans. on Magnetics. November 2000. V. 36. No. 6. P. 4036-4043.
13. Kuznetsov A.V. Coded Modulation Schemas with Turbo and List
Detection for High-Order Patrial Response Channels // IEEE Trans. On Magnetics.
March 2001. V. 37. No. 2. P. 729-736.
14. Levshin I.P., Orlov I.A. The computer simulation method of the
relative receiv ing-transmission of the information for the underwater sound
channel information transmission // Proc. of the XXYIII Intern. Conference and
Discussion Club: Information Technologies in Science Education and Business,
IT’+SE’2001, May,s session, F. New technology in telecommunication. Ukraine,
Crimea, Yalta-Hurzuf, 20-29 may, 2001, p. 37-41