РАСЧЕТ ЗАДЕРЖКИ ПРИ ИСПОЛЬЗОВАНИИ КОДИРОВАНИЯ НА ТРАНСПОРТНОМ УРОВНЕ СЕТИ ПЕРЕДАЧИ ДАННЫХ
45
УДК 519.711.4
Е. А. КРУК, Д. А. МАЛИЧЕНКО
РАСЧЕТ ЗАДЕРЖКИ ПРИ ИСПОЛЬЗОВАНИИ КОДИРОВАНИЯ НА ТРАНСПОРТНОМ УРОВНЕ СЕТИ ПЕРЕДАЧИ ДАННЫХ
Рассматривается задача определения выигрыша от использования кодирования на транспортном уровне сети передачи данных. Рассчитана задержка кодированных сообщений с учетом неэкспоненциального характера задержки входящих в сообщения пакетов. Ключевые слова: транспортное кодирование, коды, исправляющие ошибки.
Введение. Для уменьшения средней задержки передачи сообщений в сетях с коммутацией пакетов Г. А. Кабатянский и Е. А. Крук [1, 2] предложили метод транспортного кодирования, или кодирования на транспортном уровне сети.
При кодировании на транспортном уровне пакеты, из которых состоит подготовленное к передаче сообщение, рассматриваются как символы некоторого алфавита, а само сообщение — как вектор над этим алфавитом. Вектор-сообщение кодируется с помощью некоторого помехоустойчивого кода, в результате чего к сообщению добавляются избыточные символы — пакеты и получается кодированное сообщение.
При передаче кодированных сообщений возрастает нагрузка на сеть, что ведет к увеличению среднего времени задержки при передаче пакетов, входящих в сообщение. Однако для восстановления сообщения узлу-адресату в силу свойств помехоустойчивого кода не требуются все переданные пакеты. Сообщение может быть восстановлено по их части, что позволяет при сборке сообщения не ждать некоторых „задержавшихся“ пакетов. Таким образом,
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
46 Е. А. Крук, Д. А. Маличенко
использование транспортного кодирования приводит к двум противоположным эффектам —
негативному, состоящему в увеличении среднего времени передачи пакетов, и позитивному,
связанному с облегчением правил приема сообщений. При довольно общих ограничениях на
организацию сети суммарное влияние указанных эффектов приводит к уменьшению средней
задержки сообщений в сети.
Транспортное кодирование рассматривалось в значительном числе публикаций [3—11].
В настоящей статье выполнен расчет условий использования кодирования на транспортном
уровне сети.
Модель сети. Рассмотрим модель сети передачи данных с коммутацией пакетов. Сеть
имеет M каналов, емкость i -го канала равна Ci . Будем считать, что каналы сети абсолютно надежны, если всегда выполняется следующее неравенство
Pош < Pош.д ,
(1)
где Pош — вероятность получения узлом-адресатом искаженного сообщения, Pош.д — допус-
тимая вероятность ошибки при получении адресатом сообщения. Все узлы сети предполага-
ются абсолютно надежными и выполняющими операции по коммутации пакетов. Считается,
что время обработки пакета в узле пренебрежимо мало. Время передачи пакета по каналу
имеет экспоненциальное распределение с математическим ожиданием 1/ µ . Если канал занят,
пакет встает в очередь. Каждое сообщение, поступающее в сеть, разбивается на K одинако-
вых пакетов. Длина каждого пакета составляет s бит. Трафик, поступающий в сеть от внеш-
них источников, образует пуассоновский процесс с интенсивностью γ (пакетов в секунду).
Обозначим через λi среднее число пакетов, проходящих по i -му каналу в секунду, тогда полный трафик сети равен
M
λ = ∑λi . i=1
Определить закон распределения времени задержки пакета в сети довольно сложно. Ин-
тервал времени между последовательными моментами поступления двух пакетов в канал не
может быть меньше времени передачи первого из них по указанному каналу. Таким образом,
задержки пакетов в сети являются зависимыми величинами. Однако если пакеты, передаю-
щиеся по одному каналу, пришли из разных каналов или если пакеты, пришедшие по одному
каналу, отправляются по разным каналам, можно предположить, что эта зависимость умень-
шится. Как показал Клейнрок [12, 13], для сетей со средней связанностью задержки пакетов
можно считать независимыми случайными величинами. В этом случае i -й канал можно
представить в виде системы массового обслуживания с потоком интенсивностью λi , на входе распределенным по пуассоновскому закону, и временем обслуживания, распределенным по
показательному закону со
средним
1 µCi
.
В реальной сети закон распределения времени задержки пакета, очевидно, зависит от
топологии сети, процедуры маршрутизации и т.д. Однако известно, что для многих реальных
сетей закон распределения времени задержки пакета близок к экспоненциальному [12, 13].
Тогда можно предположить, что время задержки пакета в сети распределено экспоненциаль-
но с математическим ожиданием [12]:
∑t
(λ,µ) =
M λi i=1 γ
1 µCi − λi
.
(2)
Если рассмотреть случай, когда все M каналов имеют одинаковую пропускную спо-
собность, а внешний трафик равномерно распределяется между каналами (так что интенсив-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
Расчет задержки при использовании кодирования сети передачи данных
47
ности потоков пакетов для всех каналов одинаковы), то выражение (2) можно записать сле-
дующим образом:
∑t
(λ,
µ)
=
M i=1
l µC
1 1− ρ
,
(3)
где
l =λ γ
— средняя длина пути, проходимого пакетом по сети,
ρ
=
λ µC
— загрузка сети,
M
C = ∑ Ci — суммарная емкость каналов сети. Значение загрузки сети в данном случае совпаi=1
дает
с
ρi
=
λi µCi
— загрузкой канала сети. Заметим, что для сетей средней и большой связан-
ности с достаточно большим числом узлов значение ρi стремится к ρ .
Транспортное кодирование при экспоненциальной задержке пакетов. Рассмотрим
модель сети с абсолютно надежными каналами, т.е. в предположении, что для каналов сети
справедливо неравенство (1). В дополнение к сформулированной выше модели сети предпо-
ложим, что время задержки пакета имеет экспоненциальное распределение, а его математи-
ческое ожидание t является функцией от λ и µ и определяется формулой (3). Такое предпо-
ложение, по-видимому, справедливо для сетей с малой загрузкой.
Время задержки некодированного сообщения в сети T определяется максимальным
временем задержки среди K пакетов данного сообщения
T = max{t1,...,tK } ,
(4)
где ti — задержка i -го пакета сообщения. Таким образом, время задержки сообщения равно времени задержки пакета, пришедшего последним. Если переобозначить задержки пакетов
сообщения в порядке возрастания t1:K ≤ t2:K ≤ ... ≤ tK:K , то T = tK:K . В этом случае задержка
кодированного сообщения Tcod будет равна
Tcod = tK:N . Воспользовавшись аппаратом ранговых статистик [14], математическое ожидание вре-
мени задержки i -го пришедшего пакета (при общем числе пакетов N) можно записать сле-
дующим образом:
1
∫M [ti:N ] = NCNi−−11 P−1(u)ui−1[1− u]N −i du , 0
(5)
где P(t) — функция распределения времени задержки пакета в сети, P−1(u) — функция, об-
ратная к P(t) . Для случая экспоненциального распределения времени задержки пакета в сети
с использованием стандартного аппарата ранговых статистик формулу (5) можно переписать
в следующем виде:
N
∑M[ti:N ] = t (λ,µ)
j−1 ,
j=N −i+1
(6)
где t (λ,µ) — среднее время задержки пакета в сети. Тогда среднюю задержку в сети некоди-
рованного сообщения T1 можно записать как
K
∑T1 = M [ti:K ] = t (λ,µ) j−1 , j=1
(7)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
48 Е. А. Крук, Д. А. Маличенко
где t (λ,µ) определяется равенством (3). Сумму в правой части равенства (7) можно предста-
вить следующим образом [15]:
∑ ∑K
j =1
j −1
=
ε
+ ln
K
+
1 2K
−
∞ i=2
K(K
Ai + 1)...( K
+i
−1)
,
(8)
где ε = 0,577... — постоянная Эйлера,
∫Ai
=
1 i
1 0
x(1 −
x)(2
−
x)(3
−
x)...(i
−1−
x)dx.
Отсюда получим оценку средней задержки некодированного сообщения:
T1 ≥ (ε + ln K )t (λ,µ).
(9)
Среднюю задержку кодированного сообщения T2 для заданного N , в соответствии с (6), можно записать следующим образом:
∑T2 = M [tK:N ] = min ⎪⎧⎨t (λ / R,µ) N
j
−1
⎫⎪ ⎬
,
R ⎩⎪
j=N −K +1 ⎭⎪
(10)
где t (λ R,µ) — среднее время задержки пакета при трафике, возросшем в результате ис-
пользования кодированных сообщений в 1 R раз. Отсюда с учетом (8) получим
T2
≤
min
R
⎨⎧t ⎩
(λ
/
R,
µ)
ln
⎛ ⎝⎜
1 1− R
⎟⎞⎠⎭⎫⎬.
(11)
Среднюю задержку пакета при трафике, возросшем в 1 R раз, можно в соответствии с
(3) записать как
t
(λ /
R,µ) =
l µC
R
R −
ρ
.
(12)
Минимизируя (11) по R , получим
T2
≤
l µC
4ρ (1− ρ)2
.
(13)
Выигрыш при использовании кодирования на транспортном уровне сети может быть
получен в случае:
T1 − T2 > 0.
(14)
Подставив (8) и (13) в (14), получим условие выигрыша от использования кодирования
ε
+
ln
K
>
4ρ 1−ρ
,
(15)
откуда видно, что применение кодирования на транспортном уровне сети, например при K = 7 , выгодно при умеренной загрузке сети ρ < 0, 4 . В этом случае при загрузке ρ = 0, 3 средняя за-
держка сообщения при использовании кодирования уменьшается более чем в 1,5 раза. Очевид-
но, что с увеличением K диапазон загрузок сети, пригодных для использования кодирования,
увеличивается. Расчеты по точным формулам показывают, что введение кодирования на
транспортном уровне сети снижает среднюю задержку сообщения практически при любых
значениях начальной загрузки сети, хотя выигрыш уменьшается с ростом ρ .
Транспортное кодирование при неэкспоненциальных моделях задержки. Выше для
расчета задержки сообщения использовалась экспоненциальная модель задержки пакета. Да-
лее расчет выполним с помощью программы имитационного моделирования. Программа мо-
делирует ожидание пакетов в очереди и передачу по каналу. Каждый отдельный канал пред-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
Расчет задержки при использовании кодирования сети передачи данных
49
ставляет собой систему массового обслуживания. Имитационная модель задается следующими параметрами:
1) топология сети, представленная с помощью матрицы смежности; 2) матрица интенсивностей потока; 3) матрица емкостей каналов; 4) таблица маршрутизации. Распределение задержки пакетов обусловлено только самой имитационной моделью. Так же, как и ранее, будут рассматриваться сети, вся нагрузка по передаче пакетов в которых распределяется равномерно по всей сети, т.е. все каналы одинаково загружены. Чтобы задать такую сеть для программы имитационного моделирования, сделаем одно дополнительное допущение. Будем считать, что трафик между каждой парой узлов „источник—получатель“ одинаков и параметры маршрутов (длина и количество) также одинаковы. Тогда зададим только одну пару узлов „источник—получатель“ с числом маршрутов, равным длине сообщения. Чтобы учесть увеличение загрузки сети, например, при использовании транспортного кодирования, будем пропорционально увеличивать загрузку на каждом канале. В случае использования транспортного кодирования загрузка каналов возрастет в R раз по сравнению со случаем без кодирования, где R — скорость используемого кода. Емкость всех каналов положим равной единице.
На рис. 1 представлены зависимости выигрыша T1 T2 от скорости кода при k=8. Выиг-
рыш рассчитан с использованием экспоненциальной модели задержки пакета и с помощью имитационной модели (цифры со штрихом) для разной длины путей (а — 1, б — 3) между отправителем и получателем сообщений при разных значениях загрузки сети ρ (1, 1′ — 0,2;
2, 2′ — 0,4; 3, 3′ — 0,6).
а) Т1/Т2
3 1
1′ 2
2
1 2′ 3 3′
0 б) Т1/Т2
3
0,2 0,4 0,6 0,8 R
2
1 1′ 1
2 2′ 3 3′
0 0,2 0,4 0,6 0,8 R Рис. 1
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
50 Е. А. Крук, Д. А. Маличенко
Из рисунка видно, что с увеличением путей возрастает погрешность расчета, связанная
с допущением об экспоненциальной задержке пакетов. Для иллюстрации этого факта гисто-
граммы экспоненциального распределения (1) и полученного имитационным моделирова-
нием распределения (2) при длине пути 3 приведены на рис. 2.
0,3 Из рисунка видно, что распределения
1
2 3
0,2 4
сильно различаются по форме. Дисперсии распределений также различны. Рассмотрим причины изменения. С увеличением длины маршрута до трех каждый пакет на пути от источника до получателя сообщения должен пройти
три системы массового обслуживания. Таким
образом, задержка пакета представляет собой
сумму как минимум трех случайных величин,
0,1 распределенных по одному и тому же экспо-
ненциальному закону. Точное количество слу-
чайных величин в сумме зависит от размера
очереди в каждой системе массового обслужи-
0 –5 0
вания, т.е. от загрузки сети. Известно, что сум-
5 10 15 20 ма r случайных величин, распределенных по
Рис. 2
одному и тому же экспоненциальному закону,
распределена по закону Эрланга. На рис. 2 также приведены распределения Эрланга 3-го по-
рядка (3) и нормального распределения (4). Математические ожидания всех четырех распре-
делений одинаковы. Дисперсия нормального закона распределения задана такой же, как у
распределения, полученного с помощью имитационной модели. В остальных распределениях
дисперсия рассчитывается по уже заданным параметрам.
Значение выигрыша от кодирования, рассчитанное с использованием экспоненциально-
го распределения (рис. 1, б), существенно больше значения, полученного с помощью имитационного моделирования. В качестве альтернативы экспонен-
Т1/Т2 3
1
циальному закону распределения для расчета задерж-
ки сообщения рассмотрим закон распределения Эрланга и нормальный закон.
На рис. 3 представлен выигрыш от кодирования
2
32
в зависимости от скорости кода, рассчитанный с помощью этих двух законов распределения (2 — ими-
1
4
тационная модель). Видно, что оценки выигрыша от
кодирования, основанные на эрланговом распределе-
нии задержки пакета (3) и на нормальном распределении точнее соответствующей оценки, основанной
0,2
0,4 0,6 Рис. 3
0,8 R
на экспоненциальном законе распределения (1).
Выводы. Сравнение значений выигрыша от использования кодирования на транспорт-
ном уровне сети передачи, полученных в результате расчетов и имитационного моделирова-
ния, показали, что:
— существует широкий набор параметров сети, для которых использование транспорт-
ного кодирования обеспечивает выигрыш по средней задержке сообщений;
— принятая в работах [1, 2] для аналитических расчетов модель, основанная на экспо-
ненциальном характере задержки пакетов сети, имеет ограниченные пределы использования.
Во многих случаях более точные результаты дает использование моделей, предполагающих,
что задержка пакетов распределена по закону Эрланга или нормальному закону;
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
Расчет задержки при использовании кодирования сети передачи данных
51
— подбор закона распределения задержки пакетов для проведения аналитических расчетов требует учета длины путей, проходимых пакетами в сети.
СПИСОК ЛИТЕРАТУРЫ
1. Кабатянский Г. А., Крук Е. А. Кодирование уменьшает задержку // Х Всесоюз. школа-семинар по вычислительным сетям. Ч. 2. М.-Тбилиси, 1985. С. 23—26.
2. Кабатянский Г. А., Крук Е. А. Об избыточном кодировании на транспортном уровне сети передачи данных // Помехоустойчивое кодирование и надежность ЭВМ. М.: Наука, 1987. С. 143—150.
3. Vvedenskaya N. D. Large Queuing System where Messages are Transmitted via Several Routes // Problems of Information Transmission. 1998. Vol. 34, N 2. P. 180—189.
4. Krouk E., Semenov S. Application of Coding at the Network Transport Level to Decrease the Message Delay // Proc. of 3rd Intern. Symp. on Communication Systems Networks and Digital Signal Processing. Staffordshire University, UK, 2002. P. 109—112.
5. Крук Е. А., Прохорова В. Б. Расчет вероятностных характеристик для дискретных каналов с памятью // ИУС. 2007. № 5(30). С. 56—57.
6. Башун В. В., Сергеев А. В. Модель и протокол передачи видеоданных в реальном времени по беспроводному каналу // ИУС. 2007. № 6(31). С. 20—27.
7. Alon N., Luby M. A linear time erasure codes with nearly optimal recovery // IEEE Trans. on Inf. Theory. 1996. Vol. 42, N 6. P. 1732—1736.
8. Luby M., Mitzenmacher M., Shokrollahi M. A., Spielman D. A., Stemann V. Practical loss-resilient codes // Proc. of the 29th Ann. Symp. Theory of Computing. 1997. Vol. 42, N 6. P. 150—159.
9. Luby M. LT Codes // Proc. of the 43rd Annual IEEE Symp. on Foundations of Comp. Science. 2002.
10. Krouk E. E., Semenov S. Transmission of a Message During Limited Time with the Help of Transport Coding // Proc. of ICETE 2005. Intern. Conf. on E-business and Telecommunication Networks. 2005. P. 88—93.
11. Kabatiansky G., Krouk E., Semenov S. Error Correcting Coding and Security for Data Networks. Analysis of the Superchannel Concept. Wiley, 2005. 288 р.
12. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979. 600 с.
13. Клейнрок Л. Коммуникационные сети. Стохастические потоки и задержки сообщений. М.: Наука, 1970. 256 с.
14. Дэйвид Г. Порядковые статистики. М.: Наука, 1979. 340 с.
15. Градштейн И. С., Рыжик И. Р. Таблицы интегралов, сумм, рядов и произведений. М., 1963. 1100 с.
Сведения об авторах
Евгений Аврамович Крук
— д-р техн. наук, профессор; Санкт-Петербургский государственный
университет аэрокосмического приборостроения, кафедра безо-
пасности информационных систем; E-mail: ekrouk@vu.spb.ru
Дмитрий Александрович Маличенко — Санкт-Петербургский государственный университет аэрокосмиче-
ского приборостроения, кафедра безопасности информационных
систем; ассистент; E-mail: dml@vu.spb.ru
Рекомендована кафедрой № 51 безопасности информационных систем
Поступила в редакцию 01.02.13 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
УДК 519.711.4
Е. А. КРУК, Д. А. МАЛИЧЕНКО
РАСЧЕТ ЗАДЕРЖКИ ПРИ ИСПОЛЬЗОВАНИИ КОДИРОВАНИЯ НА ТРАНСПОРТНОМ УРОВНЕ СЕТИ ПЕРЕДАЧИ ДАННЫХ
Рассматривается задача определения выигрыша от использования кодирования на транспортном уровне сети передачи данных. Рассчитана задержка кодированных сообщений с учетом неэкспоненциального характера задержки входящих в сообщения пакетов. Ключевые слова: транспортное кодирование, коды, исправляющие ошибки.
Введение. Для уменьшения средней задержки передачи сообщений в сетях с коммутацией пакетов Г. А. Кабатянский и Е. А. Крук [1, 2] предложили метод транспортного кодирования, или кодирования на транспортном уровне сети.
При кодировании на транспортном уровне пакеты, из которых состоит подготовленное к передаче сообщение, рассматриваются как символы некоторого алфавита, а само сообщение — как вектор над этим алфавитом. Вектор-сообщение кодируется с помощью некоторого помехоустойчивого кода, в результате чего к сообщению добавляются избыточные символы — пакеты и получается кодированное сообщение.
При передаче кодированных сообщений возрастает нагрузка на сеть, что ведет к увеличению среднего времени задержки при передаче пакетов, входящих в сообщение. Однако для восстановления сообщения узлу-адресату в силу свойств помехоустойчивого кода не требуются все переданные пакеты. Сообщение может быть восстановлено по их части, что позволяет при сборке сообщения не ждать некоторых „задержавшихся“ пакетов. Таким образом,
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
46 Е. А. Крук, Д. А. Маличенко
использование транспортного кодирования приводит к двум противоположным эффектам —
негативному, состоящему в увеличении среднего времени передачи пакетов, и позитивному,
связанному с облегчением правил приема сообщений. При довольно общих ограничениях на
организацию сети суммарное влияние указанных эффектов приводит к уменьшению средней
задержки сообщений в сети.
Транспортное кодирование рассматривалось в значительном числе публикаций [3—11].
В настоящей статье выполнен расчет условий использования кодирования на транспортном
уровне сети.
Модель сети. Рассмотрим модель сети передачи данных с коммутацией пакетов. Сеть
имеет M каналов, емкость i -го канала равна Ci . Будем считать, что каналы сети абсолютно надежны, если всегда выполняется следующее неравенство
Pош < Pош.д ,
(1)
где Pош — вероятность получения узлом-адресатом искаженного сообщения, Pош.д — допус-
тимая вероятность ошибки при получении адресатом сообщения. Все узлы сети предполага-
ются абсолютно надежными и выполняющими операции по коммутации пакетов. Считается,
что время обработки пакета в узле пренебрежимо мало. Время передачи пакета по каналу
имеет экспоненциальное распределение с математическим ожиданием 1/ µ . Если канал занят,
пакет встает в очередь. Каждое сообщение, поступающее в сеть, разбивается на K одинако-
вых пакетов. Длина каждого пакета составляет s бит. Трафик, поступающий в сеть от внеш-
них источников, образует пуассоновский процесс с интенсивностью γ (пакетов в секунду).
Обозначим через λi среднее число пакетов, проходящих по i -му каналу в секунду, тогда полный трафик сети равен
M
λ = ∑λi . i=1
Определить закон распределения времени задержки пакета в сети довольно сложно. Ин-
тервал времени между последовательными моментами поступления двух пакетов в канал не
может быть меньше времени передачи первого из них по указанному каналу. Таким образом,
задержки пакетов в сети являются зависимыми величинами. Однако если пакеты, передаю-
щиеся по одному каналу, пришли из разных каналов или если пакеты, пришедшие по одному
каналу, отправляются по разным каналам, можно предположить, что эта зависимость умень-
шится. Как показал Клейнрок [12, 13], для сетей со средней связанностью задержки пакетов
можно считать независимыми случайными величинами. В этом случае i -й канал можно
представить в виде системы массового обслуживания с потоком интенсивностью λi , на входе распределенным по пуассоновскому закону, и временем обслуживания, распределенным по
показательному закону со
средним
1 µCi
.
В реальной сети закон распределения времени задержки пакета, очевидно, зависит от
топологии сети, процедуры маршрутизации и т.д. Однако известно, что для многих реальных
сетей закон распределения времени задержки пакета близок к экспоненциальному [12, 13].
Тогда можно предположить, что время задержки пакета в сети распределено экспоненциаль-
но с математическим ожиданием [12]:
∑t
(λ,µ) =
M λi i=1 γ
1 µCi − λi
.
(2)
Если рассмотреть случай, когда все M каналов имеют одинаковую пропускную спо-
собность, а внешний трафик равномерно распределяется между каналами (так что интенсив-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
Расчет задержки при использовании кодирования сети передачи данных
47
ности потоков пакетов для всех каналов одинаковы), то выражение (2) можно записать сле-
дующим образом:
∑t
(λ,
µ)
=
M i=1
l µC
1 1− ρ
,
(3)
где
l =λ γ
— средняя длина пути, проходимого пакетом по сети,
ρ
=
λ µC
— загрузка сети,
M
C = ∑ Ci — суммарная емкость каналов сети. Значение загрузки сети в данном случае совпаi=1
дает
с
ρi
=
λi µCi
— загрузкой канала сети. Заметим, что для сетей средней и большой связан-
ности с достаточно большим числом узлов значение ρi стремится к ρ .
Транспортное кодирование при экспоненциальной задержке пакетов. Рассмотрим
модель сети с абсолютно надежными каналами, т.е. в предположении, что для каналов сети
справедливо неравенство (1). В дополнение к сформулированной выше модели сети предпо-
ложим, что время задержки пакета имеет экспоненциальное распределение, а его математи-
ческое ожидание t является функцией от λ и µ и определяется формулой (3). Такое предпо-
ложение, по-видимому, справедливо для сетей с малой загрузкой.
Время задержки некодированного сообщения в сети T определяется максимальным
временем задержки среди K пакетов данного сообщения
T = max{t1,...,tK } ,
(4)
где ti — задержка i -го пакета сообщения. Таким образом, время задержки сообщения равно времени задержки пакета, пришедшего последним. Если переобозначить задержки пакетов
сообщения в порядке возрастания t1:K ≤ t2:K ≤ ... ≤ tK:K , то T = tK:K . В этом случае задержка
кодированного сообщения Tcod будет равна
Tcod = tK:N . Воспользовавшись аппаратом ранговых статистик [14], математическое ожидание вре-
мени задержки i -го пришедшего пакета (при общем числе пакетов N) можно записать сле-
дующим образом:
1
∫M [ti:N ] = NCNi−−11 P−1(u)ui−1[1− u]N −i du , 0
(5)
где P(t) — функция распределения времени задержки пакета в сети, P−1(u) — функция, об-
ратная к P(t) . Для случая экспоненциального распределения времени задержки пакета в сети
с использованием стандартного аппарата ранговых статистик формулу (5) можно переписать
в следующем виде:
N
∑M[ti:N ] = t (λ,µ)
j−1 ,
j=N −i+1
(6)
где t (λ,µ) — среднее время задержки пакета в сети. Тогда среднюю задержку в сети некоди-
рованного сообщения T1 можно записать как
K
∑T1 = M [ti:K ] = t (λ,µ) j−1 , j=1
(7)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
48 Е. А. Крук, Д. А. Маличенко
где t (λ,µ) определяется равенством (3). Сумму в правой части равенства (7) можно предста-
вить следующим образом [15]:
∑ ∑K
j =1
j −1
=
ε
+ ln
K
+
1 2K
−
∞ i=2
K(K
Ai + 1)...( K
+i
−1)
,
(8)
где ε = 0,577... — постоянная Эйлера,
∫Ai
=
1 i
1 0
x(1 −
x)(2
−
x)(3
−
x)...(i
−1−
x)dx.
Отсюда получим оценку средней задержки некодированного сообщения:
T1 ≥ (ε + ln K )t (λ,µ).
(9)
Среднюю задержку кодированного сообщения T2 для заданного N , в соответствии с (6), можно записать следующим образом:
∑T2 = M [tK:N ] = min ⎪⎧⎨t (λ / R,µ) N
j
−1
⎫⎪ ⎬
,
R ⎩⎪
j=N −K +1 ⎭⎪
(10)
где t (λ R,µ) — среднее время задержки пакета при трафике, возросшем в результате ис-
пользования кодированных сообщений в 1 R раз. Отсюда с учетом (8) получим
T2
≤
min
R
⎨⎧t ⎩
(λ
/
R,
µ)
ln
⎛ ⎝⎜
1 1− R
⎟⎞⎠⎭⎫⎬.
(11)
Среднюю задержку пакета при трафике, возросшем в 1 R раз, можно в соответствии с
(3) записать как
t
(λ /
R,µ) =
l µC
R
R −
ρ
.
(12)
Минимизируя (11) по R , получим
T2
≤
l µC
4ρ (1− ρ)2
.
(13)
Выигрыш при использовании кодирования на транспортном уровне сети может быть
получен в случае:
T1 − T2 > 0.
(14)
Подставив (8) и (13) в (14), получим условие выигрыша от использования кодирования
ε
+
ln
K
>
4ρ 1−ρ
,
(15)
откуда видно, что применение кодирования на транспортном уровне сети, например при K = 7 , выгодно при умеренной загрузке сети ρ < 0, 4 . В этом случае при загрузке ρ = 0, 3 средняя за-
держка сообщения при использовании кодирования уменьшается более чем в 1,5 раза. Очевид-
но, что с увеличением K диапазон загрузок сети, пригодных для использования кодирования,
увеличивается. Расчеты по точным формулам показывают, что введение кодирования на
транспортном уровне сети снижает среднюю задержку сообщения практически при любых
значениях начальной загрузки сети, хотя выигрыш уменьшается с ростом ρ .
Транспортное кодирование при неэкспоненциальных моделях задержки. Выше для
расчета задержки сообщения использовалась экспоненциальная модель задержки пакета. Да-
лее расчет выполним с помощью программы имитационного моделирования. Программа мо-
делирует ожидание пакетов в очереди и передачу по каналу. Каждый отдельный канал пред-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
Расчет задержки при использовании кодирования сети передачи данных
49
ставляет собой систему массового обслуживания. Имитационная модель задается следующими параметрами:
1) топология сети, представленная с помощью матрицы смежности; 2) матрица интенсивностей потока; 3) матрица емкостей каналов; 4) таблица маршрутизации. Распределение задержки пакетов обусловлено только самой имитационной моделью. Так же, как и ранее, будут рассматриваться сети, вся нагрузка по передаче пакетов в которых распределяется равномерно по всей сети, т.е. все каналы одинаково загружены. Чтобы задать такую сеть для программы имитационного моделирования, сделаем одно дополнительное допущение. Будем считать, что трафик между каждой парой узлов „источник—получатель“ одинаков и параметры маршрутов (длина и количество) также одинаковы. Тогда зададим только одну пару узлов „источник—получатель“ с числом маршрутов, равным длине сообщения. Чтобы учесть увеличение загрузки сети, например, при использовании транспортного кодирования, будем пропорционально увеличивать загрузку на каждом канале. В случае использования транспортного кодирования загрузка каналов возрастет в R раз по сравнению со случаем без кодирования, где R — скорость используемого кода. Емкость всех каналов положим равной единице.
На рис. 1 представлены зависимости выигрыша T1 T2 от скорости кода при k=8. Выиг-
рыш рассчитан с использованием экспоненциальной модели задержки пакета и с помощью имитационной модели (цифры со штрихом) для разной длины путей (а — 1, б — 3) между отправителем и получателем сообщений при разных значениях загрузки сети ρ (1, 1′ — 0,2;
2, 2′ — 0,4; 3, 3′ — 0,6).
а) Т1/Т2
3 1
1′ 2
2
1 2′ 3 3′
0 б) Т1/Т2
3
0,2 0,4 0,6 0,8 R
2
1 1′ 1
2 2′ 3 3′
0 0,2 0,4 0,6 0,8 R Рис. 1
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
50 Е. А. Крук, Д. А. Маличенко
Из рисунка видно, что с увеличением путей возрастает погрешность расчета, связанная
с допущением об экспоненциальной задержке пакетов. Для иллюстрации этого факта гисто-
граммы экспоненциального распределения (1) и полученного имитационным моделирова-
нием распределения (2) при длине пути 3 приведены на рис. 2.
0,3 Из рисунка видно, что распределения
1
2 3
0,2 4
сильно различаются по форме. Дисперсии распределений также различны. Рассмотрим причины изменения. С увеличением длины маршрута до трех каждый пакет на пути от источника до получателя сообщения должен пройти
три системы массового обслуживания. Таким
образом, задержка пакета представляет собой
сумму как минимум трех случайных величин,
0,1 распределенных по одному и тому же экспо-
ненциальному закону. Точное количество слу-
чайных величин в сумме зависит от размера
очереди в каждой системе массового обслужи-
0 –5 0
вания, т.е. от загрузки сети. Известно, что сум-
5 10 15 20 ма r случайных величин, распределенных по
Рис. 2
одному и тому же экспоненциальному закону,
распределена по закону Эрланга. На рис. 2 также приведены распределения Эрланга 3-го по-
рядка (3) и нормального распределения (4). Математические ожидания всех четырех распре-
делений одинаковы. Дисперсия нормального закона распределения задана такой же, как у
распределения, полученного с помощью имитационной модели. В остальных распределениях
дисперсия рассчитывается по уже заданным параметрам.
Значение выигрыша от кодирования, рассчитанное с использованием экспоненциально-
го распределения (рис. 1, б), существенно больше значения, полученного с помощью имитационного моделирования. В качестве альтернативы экспонен-
Т1/Т2 3
1
циальному закону распределения для расчета задерж-
ки сообщения рассмотрим закон распределения Эрланга и нормальный закон.
На рис. 3 представлен выигрыш от кодирования
2
32
в зависимости от скорости кода, рассчитанный с помощью этих двух законов распределения (2 — ими-
1
4
тационная модель). Видно, что оценки выигрыша от
кодирования, основанные на эрланговом распределе-
нии задержки пакета (3) и на нормальном распределении точнее соответствующей оценки, основанной
0,2
0,4 0,6 Рис. 3
0,8 R
на экспоненциальном законе распределения (1).
Выводы. Сравнение значений выигрыша от использования кодирования на транспорт-
ном уровне сети передачи, полученных в результате расчетов и имитационного моделирова-
ния, показали, что:
— существует широкий набор параметров сети, для которых использование транспорт-
ного кодирования обеспечивает выигрыш по средней задержке сообщений;
— принятая в работах [1, 2] для аналитических расчетов модель, основанная на экспо-
ненциальном характере задержки пакетов сети, имеет ограниченные пределы использования.
Во многих случаях более точные результаты дает использование моделей, предполагающих,
что задержка пакетов распределена по закону Эрланга или нормальному закону;
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
Расчет задержки при использовании кодирования сети передачи данных
51
— подбор закона распределения задержки пакетов для проведения аналитических расчетов требует учета длины путей, проходимых пакетами в сети.
СПИСОК ЛИТЕРАТУРЫ
1. Кабатянский Г. А., Крук Е. А. Кодирование уменьшает задержку // Х Всесоюз. школа-семинар по вычислительным сетям. Ч. 2. М.-Тбилиси, 1985. С. 23—26.
2. Кабатянский Г. А., Крук Е. А. Об избыточном кодировании на транспортном уровне сети передачи данных // Помехоустойчивое кодирование и надежность ЭВМ. М.: Наука, 1987. С. 143—150.
3. Vvedenskaya N. D. Large Queuing System where Messages are Transmitted via Several Routes // Problems of Information Transmission. 1998. Vol. 34, N 2. P. 180—189.
4. Krouk E., Semenov S. Application of Coding at the Network Transport Level to Decrease the Message Delay // Proc. of 3rd Intern. Symp. on Communication Systems Networks and Digital Signal Processing. Staffordshire University, UK, 2002. P. 109—112.
5. Крук Е. А., Прохорова В. Б. Расчет вероятностных характеристик для дискретных каналов с памятью // ИУС. 2007. № 5(30). С. 56—57.
6. Башун В. В., Сергеев А. В. Модель и протокол передачи видеоданных в реальном времени по беспроводному каналу // ИУС. 2007. № 6(31). С. 20—27.
7. Alon N., Luby M. A linear time erasure codes with nearly optimal recovery // IEEE Trans. on Inf. Theory. 1996. Vol. 42, N 6. P. 1732—1736.
8. Luby M., Mitzenmacher M., Shokrollahi M. A., Spielman D. A., Stemann V. Practical loss-resilient codes // Proc. of the 29th Ann. Symp. Theory of Computing. 1997. Vol. 42, N 6. P. 150—159.
9. Luby M. LT Codes // Proc. of the 43rd Annual IEEE Symp. on Foundations of Comp. Science. 2002.
10. Krouk E. E., Semenov S. Transmission of a Message During Limited Time with the Help of Transport Coding // Proc. of ICETE 2005. Intern. Conf. on E-business and Telecommunication Networks. 2005. P. 88—93.
11. Kabatiansky G., Krouk E., Semenov S. Error Correcting Coding and Security for Data Networks. Analysis of the Superchannel Concept. Wiley, 2005. 288 р.
12. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979. 600 с.
13. Клейнрок Л. Коммуникационные сети. Стохастические потоки и задержки сообщений. М.: Наука, 1970. 256 с.
14. Дэйвид Г. Порядковые статистики. М.: Наука, 1979. 340 с.
15. Градштейн И. С., Рыжик И. Р. Таблицы интегралов, сумм, рядов и произведений. М., 1963. 1100 с.
Сведения об авторах
Евгений Аврамович Крук
— д-р техн. наук, профессор; Санкт-Петербургский государственный
университет аэрокосмического приборостроения, кафедра безо-
пасности информационных систем; E-mail: ekrouk@vu.spb.ru
Дмитрий Александрович Маличенко — Санкт-Петербургский государственный университет аэрокосмиче-
ского приборостроения, кафедра безопасности информационных
систем; ассистент; E-mail: dml@vu.spb.ru
Рекомендована кафедрой № 51 безопасности информационных систем
Поступила в редакцию 01.02.13 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8