The approach to modeling the process of information exchange on the TCP, based on the theory of finite Markov chains

Full Text

Подход к моделированию процесса информационного обмена по протоколу ТСР на основе теории конечных марковских цепей д.т.н. проф. Цимбал В.А., Якимова И.А., к.т.н. Тоискин В.Е., Рябцев С.В. Университет машиностроения 8(4967)35-31-93, 8(4967)76-33-08 Филиал Военной академии РВСН имени Петра Великого (г. Серпухов) 8(4967)78-92-23 МОУ «Институт Инженерной Физики» (г. Серпухов) 8(4967)75-22-03 Аннотация. В статье представлен подход к моделированию процесса информа- ционного обмена по протоколу TCP. Ключевые слова: сеть передачи данных (СПД), конечная марковская цепь (КМЦ), шаг перехода из состояния в состояния КМЦ, временные характери- стики, вероятностно-временные характеристики, протокол ТСР. Основным этапом работы протокола ТСР является ведение информационного обмена по установленному логическому соединению [1]. Осуществим моделирование процесса ин- формационного обмена по указанному протоколу с использованием теории конечных мар- ковских цепей [2, 3, 4, 5]. Для начала рассмотрим простейший случай передачи одного сегмента с возможностью одного повтора, граф переходов которого представлен на рисунке 1. Рисунок 1. Граф переходов поглощающей конечной марковской цепи (ПКМЦ) для варианта доведения односегментного сообщения и одного повтора Формализуем состояния указанной ПКМЦ: состояние S0 - хост А передал сегмент хо- сту В; состояние S1 - хост В получил сегмент от хоста А, передал квитанцию; состояние S2 - по истечению тайм-аута повторной передачи (τпп) хост А не получил квитанции от хоста В; повторно передал сегмент хосту В; состояние S3 - хост В получил сегмент от хоста А после повторной передачи, передал квитанцию; состояние S4 - хост А получил квитанцию от хоста В. Сообщение передано; состояние S5 - по истечению двухкратного значения тайм-аута по- вторной передачи (2τпп) хост А не получил квитанции от хоста В; разрыв соединения; воз- врат к процедуре установления соединения. Таким образом, в данной ПКМЦ имеется два поглощающих состояния - S4 и S5. Матрица переходных вероятностей (МПВ) для данной ПКМЦ имеет вид: 0 0 0 0 0 0 0 0 0 p01 p02 0 0 0 p12 0 P  0 p23 p14 0 0 p25 (1) 6;6 0 0 p34 p35 0 0 p44 0 0 0 0 0 0 p55 Для нахождения компонентов МПВ (1) введем обозначения:pс - вероятность доведения сегмента от хоста А до хоста В, которая определяется по формуле:  1 Lc  2 Lc   k  Lc  pc  ( 1 p0 ) ( 1 p0 ) k   ( 1 p0 ) , (2) где: Lc длина пакета в битах; p0 вероятность ошибки в k-м канале связи; pкв - вероятность доведения квитанции, которая определяется по формуле:  1 Lкв  2 Lкв   k  Lкв  pкв  ( 1 p0 ) ( 1 p0 )  ( 1 p0 ) , (3) где: Lкв длина квитанции в битах. При этом qс - вероятность неприема сегмента; qкв - вероятность неприема квитанции определяются как qc  1 pс , qкв  1 pкв . Переходные вероятности матрицы (1) находятся так. Переход из состояния S0 в состоя- ние S1, а также из состояния S2 в состояние S3 возможен тогда, когда сегмент, переданный хостом А, принят хостом В. Вероятность такого события равна вероятности доведения сег- мента. Переход из состояния S1 в состояние S4, а также из состояния S3 в состояние S4 возмо- жен, когда квитанция о приеме сегмента, переданная хостом В, принята хостом А. Вероят- ность такого события равна вероятности доведения квитанции. Анализируемый процесс перейдет из состояния S0 в состояние S2, а также из состояния S2 в состояние S5, тогда, когда при передаче сообщения сегмент не был принят хостом В. Ве- роятность такого события равна вероятности неприема сегмента. Переходы из состояния S1 в состояние S2 и из состояния S3 в состояние S5 осуществляются с вероятностью неприема квитанции. Определив соответствующие значения pс, pкв, qс, qкв, можно получить все компоненты искомой МПВ. Матрица шагов переходов рассматриваемого процесса имеет вид: 0  01  02 0 0 0 0 0 12 0 14 0 0 0 0  23 0  25 (4) T6;6  0 0 0 0 34 35 0 0 0 0  44 0 0 0 0 0 0 55 Значения компонентов МШП определяются так:     Lс ,     Lk ,      ,     2 ,    1 , (5) 01 23 Vпи 14 34 Vпи 02 12 пп 25 35 пп 44 55 При передаче двухсегментного сообщения по установленному логическому соедине- нию появляется возможность рассмотреть процедуру «скользящее окно». На рисунке 2 представлен граф ПКМЦ для случая, когда «скользящее окно» равно од- ному сегменту, а также возможен один повтор. p01 τ01 p12 τ12 p23 τ23 p38 τ38 p04 S0 S1 S2 p15 p52 p26 S3 p36 p78 p88 S8 τ88 τ04 τ15 τ52 τ26 τ36 τ78 p45 τ45 p67 τ67 S4 S5 S6 S7 p p49 p59 p69 79 τ49 τ59 τ69 τ79 S9 p99 τ99 Рисунок 2. Граф переходов ПКМЦ для варианта доведения двухсегментного сообщения, одного повтора и «скользящим окном» равным одному сегменту Матрица переходных вероятностей описанного процесса имеет вид: P10;10  0 p01 0 0 p04 0 0 0 0 0 0 0 p12 0 p14 0 0 0 0 0 0 0 0 p23 0 0 p26 0 0 0 0 0 0 0 0 0 p36 0 p38 0 0 0 0 0 0 p45 0 0 0 p49 0 0 p 0 0 0 0 0 0 p 0 0 0 0 0 0 0 p67 0 p69 0 0 0 0 0 0 0 0 p78 p79 0 0 0 0 0 0 0 0 p88 0 0 0 0 0 0 0 0 0 0 p99 52 59 (6) Матрица шагов переходов строится аналогично выражению (6) Переходные вероятности и времена шагов переходов определяются так же, как и для случая передачи односегментного сообщения. Проведенный анализ процесса передачи сообщений в соединении «точка-точка» с раз- личным количеством сегментов (w), повторов(m) и размером скользящего окна(v), показыва- ет, что графы ПКМЦ, описывающих процесс доведения многопакетного сообщения (МПС) с большим числом w, m и v, будут строится аналогично графам ПКМЦ, описывающих процесс доведения МПС с меньшим числом w, m и v. При этом граф процесса передачи сообщения с бόльшими значениями указанных параметров будет включать в себя граф с меньшими зна- чениями w, m и v. Следовательно, появляется возможность автоматизированного синтеза ПКМЦ, описывающих исследуемый процесс. Номера состояний графа и их взаимосвязи отображаются переходными вероятностями, а последние, в свою очередь, определяются своими индексами. Исходя из изложенного, за- дача нахождения (синтеза) элементов МПВ выливается в задачу нахождения соответствую- щих им индексов. Прежде всего отметим, что количество состояний процесса передачи - n в зависимости от описанных параметров равно:  v1  n  2  (m 1)  w  (w  i)  , (7)  i0  где: w - количество сегментов; m - количество повторов сегмента по истечению тайм-аутов; v - размер скользящего окна в сегментах. При этом состояние с номером n-1 для всех вариантов будет определять состояние раз- рыва соединения хостом А (передающая сторона) по истечению m-кратного значения тайм- аута повторной передачи, а состояние с номером n-2 - состояние успешного окончания ин- формационного обмена. Данные состояния во всех графах будут поглощающими. Введем параметры i и j и выразим через них текущие номера состояний k графа перехо- дов. Параметр j показывает в графе номер ряда, в котором находится состояние Sk, а пара- метр i пробегает все значения от 0 до (n-j). Тогда алгоритм такого синтеза МПВ следующий. Тогда элементы МПВ могут быть построены по следующим правилам П1 - П18: П1. P2(i jw),2(i jw)1 c c  vp (1 p )v1 , где 0  i  w  v , 0  j  m ; П2. P2(i jw),2(i jw)1 c c  (w  i) p (1 p )wi1 , где w  v 1  i  w 1, 0  j  m ; П3. П4. P2(iwj )1,2(iwj )2  Pk , где 0  i  w  2 , 0  j  m ; P2(i jw)1,n2  Pk , где i  w 1, 0  j  m ; v П5. P2(i jw),2(i jw)2w  (1 pc ) , где 0  i  w  v , 0  j  m 1; wi П6. P2(i jw),2(i jw)2w  (1 pc ) v , где w  v 1  i  w 1, 0  j  m 1; П7. P2(imw),n1  (1 pc ) , где 0  i  w  v ; wi П8. P2(imw),n1  (1 pc ) , где w  v 1  i  w 1; П9. P2i1,2(iwj )  1 pk , где 0  i  wm 1, j  1 ; П10. P2(iw)1,n1  1 pc , где 0  i  wm 1; П11. P 2(i jw),m1 lw l 1l 2 w1l  ji v c c  Cl pl 1 p vl , где 0  i  w  v , 0  j  m ;  2    П12. P  Cl pl 1 p wi1 , где w  v 1  i  w 1, 0  j  m ; 2(i jw),m1lw l 1l 2 w1l  ji wi c c  2    П13. P      p , где 0  i  w  l 1, 0  j  m ; m1 lw l 1l 2 w1l  j i,2l 2i k  2    П14. P      p , где i  w  l , 0  j  m ; m1 lw l 1l 2 w1l  ji,n2 k  2    П15. P  l  l    1 pk , где 0  j  m 1, 0  i  w  l ;  m1 lw  1 2 2 w1l  j i,2(i j w)   П16. P  l  l    1 pk , где j  m , 0  i  w  l ;  m1 lw  1 2 2 w1l  j i,n1 П17. П18.   Pn2,n2  1; Pn1,n1  1 . Остальные элементы МПВ равны нулю. Таким образом, сформулированы правила автоматизированного синтеза матриц переходных вероятностей описывающих процесс доведения МПС по стеку протоколов TCP/IP с процедурой «скользящее окно». На этой базе можно создать программную реализацию ма- тематической модели описывающей данный процесс с целью дальнейшего её исследования.

About the authors

V. A Tsymbal

Moscow State University of Mechanical Engineering (MAMI)

Dr.Eng., Prof.

I. A Efimova

Moscow State University of Mechanical Engineering (MAMI)

V. E Toiskin

The branch of the Military Academy of the Strategic Missile Forces named after Peter the Great (Serpukhov)

Ph.D.

S. V Ryabtsev

Institute of Engineering Physics (Serpukhov)

References

Supplementary files