Применение математического аппарата для параллельных конечных марковских цепей для оценки доставки сообщений в компьютерных сетях

Во всех современных протоколах доставки сообщений используется обратная связь, при этом формально процесс доставки фрейма, кадра, пакета можно представить следующим образом:

Имеются 2 абонента в нек. Момент времени T1 абонент А формирует пакет данных, он поступает в В во время t2. T1-t2 определяется средой, способами обработки, а надежность доставки в основном характеризуется длиной передаваемого пакета, моделью использованного канала связи и параметрами этой модели. Предположим, что пакет данных передается по радиоканалу в системе вайфай. При этом модель канала биномиальная, веротяность искажения элементарно символа P0=10^-3.

Рис4

С целью повышения надежности и верности доставки пакетов сообщений каждый пакет снабжается контрольной суммой

3

Т

crc

Lp=1000

Представляющая собой хэш сумму.

Таким образом пакет данных имеет структуру заголовок, пакет данных и crc. Тогда если P0 – вероятность искажения одного символа в пакете сообщения, то вероятность доведения пакета с одного повтора будет определяться как Рn=(1-Р0)^Lф

Рn=0,368

Тогда на приемной стороне принятый пакет подвергается обработке, расчитывается crc и сравнивается с crc в полученном пакете.

Если crc рассчитаная в пункте В и crc принятая в пакете совпадают, то считается, что пакет принят верно.

Сторона В отправляет свою crc и сторона А считает свою crc, если совпадает с полученным значением, то считается, что квитанция доведена и передача пакета прекращается.

Если сторона В при вычислении crc обнаруживает несовпадение crc пакета или сторона А обнаруживает не совпадение crc квитанции, то в зависимости от особенностей протокола передачи с ожиданием или с непрерывной передачей абонент А, не дождавшись квитанции в течении таймаута, передает тот же пакет данных вторично. Повторяется, пока не будет истрачено заданное количество повторов, которое вычисляется аналитически.

Каким образом принять решение на установление числа повторов, чтобы вероятность доведения пакетов сообщения была бы нениже требуемой, для ответа на этот вопрос используют математический аппарат дискретных конечных марковских цепей.

Первая часть этого матаппарата во много повторяет матаппарат теории массового обслуживания, но так как марковский процесс с дискретным состоянием и дискретным временем описывается вероятностями, а не интенсивностями, то в этом случае дуги соединяющие состояние системы будут раскрашены соответствующими вероятностями.

Предположим, что осуществляется одна попытка передачи пакета, тогда граф состояний и переходов примет вид:

Рис 5

S0 – абонент А сформировал и передает пакет данных

Тогда с Р01=0,368 этот пакет будет доведен до S1

С Р00=1-Р01 будет не доведен

Р12 будет доведена до абонента А

1-Р12 не будет доведена до А

Если А получил квитанцию и алгоритм получения crc выполняется, то это характеризуется вероятностью Р22=1

Состояние S2 называется поглащающим

В процессе длительной передачи в таком графе будут возникать финальные вероятности Р0,Р1,Р2

Р2 будет определять вероятность доведения пакета сообщений.

Такой процесс описывается матрицей состояний и переходов, в данном случае это будет:

P[2,2]=

Р00	Р01	0
0	1-Р12	Р12
0	0	1

=

0,632	0,368	0
0	0.368	0.632
0	0	0

В дальнейшем расчет вероятностей осуществялется с помощью уравнений Колмогорова-Чепмена, которое имеет вид:

Р[I]=P(0)*P[n,n]

P(I) – вероятность нахождения системы в и-ом состоянии

Р(0) – вектор исходного состояния

Р[n,n] – матрица переходов и состояний в степени i, так как операция возведения в степень матриц является неудобной для программирования и работы компьютеров, то уравнение Коломогорова-Чепмена переписывают в виде итерационной процедуры.

Р[I]=P[I-1]*P[n,n]

P[I] – вероятность нахождения системы в i-ом состоянии

P[I-1] – веротяность нахождения в предыдущем состоянии

Р[n,n] – невозводимая в степень I

Р(0)=<1 0 0>

P[1]=P(0)*P[n,n]

P[1]=

00.632

0.368

0

Матрица переходов состояний является стохастической – сумма элементов строки равна 1. Следовательно все остальные будут давать 1.

Предположим требуется вероятность доведения 0,99

Р[2]=P[1]*P[n.n]=<0.399, 0.433. 0.233>

И пока не получим нужную точность