Определение задержки в сети передачи данных

Оглавление

Рассмотрим характеристики сети ПД, связанные с ее пропускной способностью и надежностью доставки информации. Сеть ПД является стохастической системой, поскольку на ее вход поступает случайный поток сообщений от РС и серверов, а обслуживающие приборы - каналы и узлы связи подвержены отказам; в каналах связи имеются случайные помехи, влияющие на время передачи сообщений. Таким образом, сеть ПД - это сложная СМО с большим количеством обслуживающих приборов.

Определим величину задержки сообщений в i-х каналах сети и сети в целом. Эти величины будем определять как при известных законах распределения случайных велич T и T_i:

T = T_k + T_обр + Т_ож

Декомпозируем сеть, выделив из нее один из путей передачи сообщений p_ij. Он состоит из нескольких узлов и каналов (Рис.1).

Рис.1

Для анализа делается ряд упрощающих предположений:

Фиксированная маршрутизация (для любого сообщения существует только один путь передачи).
Канал рассматривается односторонний.
Сеть состоит из n - узлов и m - каналов.
Каналы безотказны (нет шумов, следовательно, не возникают ошибки, которые система бы отлавливала и повторно запрашивала сообщение).
Время обработки сообщений в узлах является постоянной величиной.
Каждому i-ому каналу ставятся в соответствие пропускная способность канала C_i [бит/с] и среднее время обслуживания и ожидания обслуживания - T_i [с].
Средняя длина сообщений [бит/сообщ].

Определим связь между и T_i.
Если - среднее время задержки в сети, то среднее число пакетов, находящихся в сети:

[сообщ],

где

- суммарная интенсивность сообщений,
g_jk [сообщ/с] - Пуассоновский поток, j - входящий узел, k - исходящий узел.

С другой стороны, число пакетов, находящихся в очереди к каналу = l_iT_i, где l_i [сообщ/с] - интенсивность на входе каждого канала, которая определяется процедурой маршрутизации.
Тогда количество сообщений, находящихся в очереди во всех каналах сети:

[сообщ]

Приравнивая и суммируя, получим:

Рассмотрим время обслуживания сообщения в канале T_i. Оно пропорционально длине сообщения l. В очереди к каналу i находятся сообщения из других линий, а также поступившие в сеть, т.е. они вышли из разных очередей, поэтому интервалы между поступлениями распределены по сложному закону. Решить эту задачу можно только представив рассматриваемую систему простейшей M/M/1. Это означает, что на вход i-той очереди поступает пуассоновский поток сообщений с интенсивностью l_i, а время обслуживания распределено по экспоненциальному закону .

Фактически, это означает, что длина сообщения l выбирается всякий раз новая при поступлении в следующий узел в соответствии с экспоненциальным законом распределения:

Р(l) = mе^-^m^l, l >= 0

Тогда одиночный канал в сети можно представить простейшей одноканальной СМО типа М/М/1. Для такой системы время обслуживания:

где m - время обсуживания в данной СМО.

Для СПД: m=1/l,

где l - длина сообщения в битах.

Подставляем T_i в выражение для

- среднее время сообщений с сети.

Здесь не учитывается t_{обработки} в узле и время распространения сигнала. Это может быть учтено. Каналы здесь симплексные, несимметричные, их можно сделать симметричными, сформировав матрицу l_i соответствующим образом. Также здесь не учтены трафик управления, связь с квитанциями на предъявляемое сообщение. Из формулы для

видно, что если знаменатель mC_i - l_i = 0, то

.
Таким образом, минимальная величина

дает пороговое значение.

Таким образом, зависит от С_i, его надо нормировать по стоимости.
Для этого будем использовать линейную функцию стоимости:

Задача оптимизации:

l_i,
- min,
C_i - варьируем,
- задано.

Для решения такой задачи используется метод множителей Лагранжа. При этом составляется функция Лагранжа, которая через коэффициент b включает ограничения по D.

По методу Лагранжа берем частную производную функции L и приравниваем полученный результат к нулю:

Подставляя

и дифференцируя получим:

Из этого выражения находится неопределенный множитель Лагранжа b и выражение для оптимальных С_i имеет вид:

(1)

(2)

D - полная стоимость, D_e - добавочная стоимость для увеличения С_i.
Здесь каждый i-ый канал будет иметь минимальную пропускную способность

и некоторую добавочную пропускную способность. Это названо распределением С_i пропорционально квадратному корню.

- стоимость минимальной суммарной емкости сети, если D_e = 0, то

.
Подставив выражения (1) в формулу для

, получим:

(3)

- характеристика топологии сети.
Это равенство определяет

в сети, когда пропускные способности выбраны оптимально.

Если D_e > 0 – задача ВПС реализуема, D_e < 0 – не реализуема.

Для рассмотрения зависимости упростим формулу (1), положив d_i = d = 1 ( однородная сеть) и

. Тогда

где

- коэффициент использования пропускной способности,
g/l - средняя скорость, с которой входят сообщения в сеть,

Трафик зависит от , значит, топологию нужно выбирать полносвязную. Отметим, что равенства получены в предположении, что g_jk постоянны. Если они меняются во времени, то нельзя найти трафик в каналах l_i и оптимально выбрать С_i, т.е. сеть не будет оптимальной. Для согласования можно использовать адаптивный выбор маршрутов, допускающий загрузку недогруженных каналов.

Предыдущий

Следующий