Рациональный выбор длины пакета
для передачи сообщений в сети ЭВМ

П.

Московская финансово-юридическая академия

1.  Постановка задачи. При передаче данных в сети ЭВМ сообщения разбиваются на части – пакеты, длины которых фиксированы. Если длина сообщения не кратна длине сообщения, то к сообщению добавляются пробелы. Каждый пакет снабжается служебной частью – заголовком, который позволяет правильно собрать пакеты в точке приёма и восстановить сообщение.

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

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

Предположим, что длины сообщений aк случайны, независимо и одинаково распределены с функцией распределения А(), а моменты возникновения помех, приводящих к разрушению пакета, образуют процесс восстановления с функцией распределения В() интервалов bк между моментами регенерации. Длину маркера в байтах обозначим d, а длину пакета s. В качестве единицы измерения времени примем время, необходимое для передачи одного байта.


Обозначим s(t) – число байт данных переданных без искажений за время t. Скорость передачи информации R(s) канала определим как предел по вероятности отношения

Далее будет получена связь между скоростью передачи информации R(s) и параметрами задачи в явном виде, что позволит определить оптимальное значение для длины пакета.

НЕ нашли? Не то? Что вы ищете?

2. 


Скорость передачи информации при отсутствии помех. Если помехи в канале отсутствуют, то для пересылки сообщения длины L, необходимо передать éL/sù пакетов, где éхù - минимальное целое, не меньшее, чем х. Обозначим k(t) число сообщений, переданных по каналу за время t, т. е. положим

где (ai)i>0 – длины передаваемых сообщений.

В силу сделанных предположений, случайные величины éai/(s+d)ù (s+d) – независимы и одинаково распределены. Следовательно k(t) – процесс восстановления, порождаемый этими величинами. Суммарная длина переданных за время t сообщений составит s(t)=a1+…+ak(t), являясь, таким образом, аддитивным функционалом от процесса восстановления k(t). В соответствии с теорией процессов восстановления [1] существует предел по вероятности при t®¥


После очевидных преобразований получим


Скорость передачи информации для простейшего потока помех Для передачи одного пакета в указанных условиях фактически необходимо переслать q пакетов, где q - случайная величина, имеющая геометрическое распределение:
P(q=k)=e-m(s+d)(1- e-m(s+d))k-1, k=1,2,… Таким образом, для передачи сообщения длиной L требуется время



где (qj)j>0 – независимые и одинаково распределённые случайные величины. Рассмотрим процесс восстановления k(t), определив его формулой

где (τii)i>0 независимые и одинаково распределённые случайные величины

По причинам, аналогичным отмеченным в пункте 2, имеем


Полученная формула позволяет определить скорость передачи информации в случае, если моменты помех образуют пуассоновский поток.

4.  Формула для скорости передачи информации в общем случае. Пусть r(n) – суммарная длина сообщений, которые можно передать с помощью n пакетов, а n(t)- число пакетов, переданных за время t без искажений.


Очевидно, что s(t)=r(n(t)) и


Используя независимость длин пакетов и интервалов между помехами легко показать, что

Поскольку
r(n) есть сумма независимых случайных величин a1,…,ak(n), где k(n)- процесс восстановления, порождаемый последовательностью независимых одинаково распределённых случайных величин éai/sù, то


Моменты появления помех gi =Sj£ibj порождают процесс восстановления с запаздыванием. Введём полумарковский процесс x(t), который совершает скачки в моменты появления помех gi, а его значение xi в момент i-ого скачка равно времени между появлением помехи и началом передачи пакета, разрушенного этой помехой.

Множество состояний процесса x(t) составляет полуинтервал [0,s+d), а переходные вероятности вложенной цепи Маркова равны


Процесс n(t) является аддитивным функционалом от процесса x(t).

Если предположить, что распределение B(x) неарифметическое, то из [2] следует, что рассматриваемый предел существует и


где q(dx) – инвариантная мера вложенной цепи Маркова, которая эргодична при указанных выше условиях.


Мера q(dx) удовлетворяет уравнению

Единственным (с точностью до множителя) решением этого уравнения является мера Лебега q(dx)=dx/(s+d).


Следовательно

Таким образом, доказано следующее

Предложение. Пусть распределение интервалов между помехами является неарифметическим, первые моменты распределений А() и В() – конечны, В(х)<1 при всех х³0, то предел


существует и


5.  Экспоненциальный случай. Предположим, что P(a>t)=e-lt, P(b>t)=e-mt.

Тогда из (3) следует, что


Функция дифференцируема R(s), неотрицательна - R(s)³0 при s³0, R(0)=R(¥)=0, производная обращается в 0 в единственной точке, которая по необходимости является точкой минимума. Эта точка удовлетворяет уравнению


При s³0 левая часть уравнения (4) монотонно возрастает от 0 до бесконечности, а правая часть также возрастает от положительной величины d/(1+md) до 1/m. Заменяя правую часть уравнения (4) последовательно на d/(1+md) и 1/m, получим оценки справа и слева для корня уравнения (4), а именно


Указанные границы позволяют получить эффективный алгоритм для нахождения оптимальной длины пакета в экспоненциальном случае.

6.  Пример расчётов. Результаты расчётов для экспоненциального случая при длине маркера 32 байта приводится в виде таблицы. В таблице а – средняя длина сообщений в байтах, вероятность ошибки при передаче одного символа p=10-n, sopt – оптимальная длина пакета, c(sopt) – соответствующая пропускная способность, numpack – среднее число пакетов.

Таблица оптимальных длин пакетов

a

sopt

c(sopt)

numpack

1024

132,02

0,6409

7,76

4096

153,69

0,6747

26,65

16384

160,95

0,6844

101,80

65536

162,92

0,6870

402,25

262144

163,43

0,6876

1604,01

1048576

163,56

0,6878

6411,07

4194304

163,59

0,6878

25639,29

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

В частности, при р=10-3 пропускная способность канала практически не зависит от длин сообщений и выбора длины пакета.

7. Выводы Получены формулы для вычисления скорости передачи информации R(s) как функции от длины пакета s в предположении, что длины случайны и в канале возможны помехи, моменты появления которых образуют произвольный поток восстановления. Функция R(s) равна отношению объёма фактически передаваемых данных к тому объёму, который мог бы быть передан при отказе от формирования пакетов и отсутствию помех в канале. Поскольку формула для функции R(s) получена в явной форме, можно получить алгоритм определения оптимальную длину пакета при заданных функциях распределения длины сообщений и интервалов между сообщениями. Анализ результатов вычисления показывает сильную зависимость пропускной способности от уровня ошибок в канале.

Литература

1. Çinlar E. Markov renewal theory. Adv. Appl. Prob. 1, 1969, p. 123-187.

2. Черенков аддитивных функционалов от полумарковских процессов с произвольным множеством состояний. «Математические заметки» т.21, выпуск 2,1977, с 213-221.