Например, Бобцов

РАСПРЕДЕЛЕНИЕ ФРАГМЕНТИРОВАННЫХ КАДРОВ ПО РЕЗЕРВИРОВАННЫМ КАНАЛАМ ВЫЧИСЛИТЕЛЬНОЙ СЕТИ

РАСПРЕДЕЛЕНИЕ ФРАГМЕНТИРОВАННЫХ КАДРОВ …
4 КОМПЬЮТЕРНЫЕ СИСТЕМЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
УДК 681.3
РАСПРЕДЕЛЕНИЕ ФРАГМЕНТИРОВАННЫХ КАДРОВ ПО РЕЗЕРВИРОВАННЫМ КАНАЛАМ ВЫЧИСЛИТЕЛЬНОЙ СЕТИ
А.В. Осипов
Предложен алгоритм распределения кадров по резервированным гетерогенным каналам, учитывающий физические особенности каналов. Приведена имитационная модель работы алгоритма на базе MATLAB/Simulink, подтверждающая преимущества предлагаемого алгоритма по сравнению с алгоритмами RoundRobin и RateBalance. Ключевые слова: резервирование каналов, канальный уровень.
Введение
Потребность в построении высокопроизводительных вычислительных сетей в условиях ограниченных ресурсов послужила одной из причин развития технологий агрегации, которые используют существующие физические каналы передачи данных для построения канала с большей пропускной способностью [1, 2]. Агрегирование каналов позволяет не только повысить суммарную пропускную способность сети [3], но и более эффективно использовать существующие каналы передачи данных [4]. Одновременное использование нескольких каналов связано с вариантностью организации межмашинного обмена. Реализация эффективного обмена при объединении в единую резервированную среду нескольких каналов требует исследования методов распределения кадров по физическим каналам и оценки их эффективности [5–10].
Алгоритмы распределения кадров по резервированным каналам
Эффективность использования пропускной способности магистралей при объединении на канальном уровне в значительной степени определяется алгоритмом распределения кадров по физическим каналам. В существующих технологиях агрегирования применяется алгоритм RoundRobin, циклически распределяющий поток кадров по имеющимся магистралям. Однако алгоритм RoundRobin, обеспечивая балансировку нагрузки, может не сохранять порядок следования кадров. Согласно алгоритму RoundRobin, каждый следующий кадр передается через очередную магистраль независимо от времени доставки предыдущего кадра. Доля инверсий в потоке принятых кадров может быть низка только при агрегировании абсолютно идентичных физических каналов. Функция исправления инверсий (нарушений порядка доставки кадров) может быть реализована на верхних уровнях сетевой модели, однако, ввиду ограниченности размера буферов передатчика и приемника, процесс исправления инверсий ведет к резкому снижению эффективности использования гетерогенных каналов, так как максимальная пропускная способность в каждом канале ограничена минимальным из значений пропускных способностей всех каналов.
В работе [11] для распределения кадров по физическим каналам передачи данных предложен адаптивный алгоритм RateBalance. В основу алгоритма RateBalance положен следующий принцип: кадр передается по тому каналу, который доставит его раньше. Для каждого физического канала i хранится время ti окончания передачи кадров, поставленных в очередь отправки канала. Алгоритм выполняет распределение кадров по N доступным каналам, основываясь на оценке времени доставки кадра. Номер ка-
нала i для отправки кадра размером s выбирается, исходя из соотношения i  min f s, j , где j
f s, j  t j  s / bj , bj – пропускная способность канала j. При этом время ti освобождения канала i кор-
ректируется по формуле ti : ti  s / bi [11]. Для каналов с различной производительностью пропускная способность агрегированного канала,
использующего RateBalance, заметно выше. При этом RateBalance дает хорошее приближение к пиковой производительности (равной сумме производительностей физических каналов, составляющих агрегированный канал). Алгоритм RateBalance лучше сохраняет исходный порядок кадров, соседние кадры входной последовательности находятся рядом и в выходной. Соответственно, сдвиг скользящего окна будет выполняться непрерывно и без задержек, в отличие от алгоритма RoundRobin.
Существующие алгоритмы распределения кадров по каналам не определяют оптимальный вариант фрагментации пакетов. В настоящей работе предложен алгоритм распределения кадров по агрегированным каналам, осуществляющий оптимальную фрагментацию пакетов.
Оптимальная фрагментация и распределение кадров по каналам
Для повышения эффективности использования пропускных способностей физических каналов предлагается осуществлять оптимальную фрагментацию каждого пакета на кадры, причем длины кадров,
84 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 2 (84)

А.В. Осипов

пересылаемых по физическим каналам, должны соответствовать оптимальному размеру для каждого физического канала. Таким образом, пакет может быть разбит на кадры разной длины.
Предлагаемый алгоритм DPB (Delivery probability balancing) учитывает следующие параметры:
 параметры пакетов, поступающих на отправку:
 длина пакета (бит) – l ;
 параметры используемых физических каналов:
 средняя величина задержки начала отправки кадра (с) – td ;
 вероятность возникновения битовой ошибки – BER;
 скорость передачи данных (бит/с) – br ;
 оптимальная длина кадра (бит) – lo ;
 объем служебной информации, присоединяемой к кадру (бит) – lh .
Средняя величина задержки начала отправки кадра определяется используемым протоколом передачи данных в физическом канале и битовой скоростью в канале. Физический канал может обладать нулевой задержкой, например, в случае использования системы Aloha со случайным доступом. В случае использования механизма CSMA/CA при обнаружении занятого состояния канала происходит задержка повторной попытки отправки на случайное число слотов ожидания из интервала [0, 2BE − 1], где –BE (Backoff exponent) – показатель степени границы интервала количества слотов ожидания. Алгоритм DPB при распределении данных по физическим каналам учитывает среднюю величину суммарной временной задержки физического канала перед отправкой кадра.
Вероятность возникновения битовой ошибки (BER – bit error rate) в физическом канале определяется мощностью сигнала на приемнике (которая зависит от мощности передатчика), спектральной плотностью шумов и используемой модуляцией. Если допустить, что спектральная плотность шумов и функциональная зависимость мощности на приемнике от мощности передатчика остаются неизменными в процессе функционирования сети, то значение BER можно определить расчетным путем даже при изменении скорости, мощности и типа модуляции на передатчике в процессе функционирования сети.
В зависимости от особенностей вычислительной сети (производительность узлов, наличие или отсутствие необходимости снижения энергопотребления) используемые в алгоритме значения параметров физических каналов и оптимальной фрагментации могут быть определены на этапе создания/настройки сети или же определяться динамически перед отправкой каждого пакета, либо при изменении физических параметров канала (например, битовой скорости). Рассмотрена оценка эффективности алгоритма распределения для стационарного режима работы сети, при котором интенсивность запросов и средняя длина пакетов не меняется во времени.
Задача определения оптимальной длины кадра для одного физического канала, учитывающая физические параметры канала, рассмотрена в [12]. Определение оптимальной длины кадров может быть выполнено однократно при проектировании/настройке сети, либо, если узлы сети обладают достаточными вычислительными и энергетическими ресурсами, может выполняться по расписанию или перед каждой отправкой пакета.
Распределитель кадров по алгоритму DPB схематично представлен на рис. 1.

Сообщение l

Распределитель DPB

Очередь 1

Канал 1

C1(td,BER,br,lo,lh)

Кадры

Очередь 2

Канал 2 C2(td,BER,br,lo,lh)

……………………………

Очередь n

Канал n Cn(td,BER,br,lo,lh)

Рис. 1. Распределитель DPB

Научно-технический вестник информационных технологий, механики и оптики, 2013, № 2 (84)

85

РАСПРЕДЕЛЕНИЕ ФРАГМЕНТИРОВАННЫХ КАДРОВ …

Задача оптимального распределения кадров по нескольким физическим каналам сводится к минимизации функции максимального времени отправки всех кадров из одной очереди:

F



max

 

  

lo1  lh1 br1



td

1

  



k1

,

  

lo

2  lh2 br2

 td 2

  



k2

,

...,

  

lon  lhn brn

 tdn

 



kn



 

,

где n – число агрегированных физических каналов (шт); lon – оптимальная длина кадра для физического

канала n (бит); lhn – объем служебной информации, присоединяемой к кадру в физическом канале n

(бит); brn – битовая скорость передачи в физическом канале n (бит/с); tdn – средняя величина задержки

начала отправки кадра в физическом канале n (с); kn – число кадров исходного пакета, определяемых к отправке через физический канал n (шт).

Для алгоритмов RoundRobin, RateBalance и DPB построены имитационные модели с использова-

нием библиотеки SimEvents пакета MATLAB/Simulink. Имитационная модель представлена на рис. 2.

Рис. 2. Имитационная модель сети с тремя параллельными каналами

Рис. 3. Процесс фрагментации, реализованный в Simulink
Процесс фрагментации, осуществляемый алгоритмом DPB, представлен на рис. 3. Модель описывает вариант организации системы, в которой оптимальная длина кадра при заданной загрузке для каж-
86 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 2 (84)

А.В. Осипов

дого канала определяется по априорно известным данным или по статистическим данным, собранным в процессе эксплуатации. Следовательно, при стационарности процессов передачи, когда интенсивность запросов и средняя длина пакетов не меняется во времени, на поиск оптимального варианта фрагментации отправляемого пакета время не тратится.
Адекватность модели проверена со следующими исходными значениями. 1. При установлении пропускных способностях второго и третьего канала, близких к нулю, передача
данных происходит только по первому каналу. Все три алгоритма показывают одинаковое среднее время пребывания требования в системе. 2. При установлении равных пропускных способностей для всех каналов алгоритмы RoundRobin и RateBalance показывают одинаковое среднее время пребывания требования в системе, а алгоритм DPB – втрое меньшее (так как алгоритм осуществляет фрагментацию каждого пакета на кадры, и кадры отправляются по трем каналам одновременно).
Произведено имитационное моделирование вычислительной сети, функционирующей по трем параллельным каналам передачи данных с пропускными способностями соответственно 4 Мбит/с, 10 Мбит/с и 20 Мбит/с. Сеть осуществляет передачу тестовых пакетов длиной 120 кбит. В ходе первого этапа имитационного моделирования измеряется число отправленных пакетов N за время работы сети t, равное 0,1 с. Результаты измерений приведены на рис. 4.
N, шт
25
20
15
10
5

0 0,01
T, c 0,07 0,06 0,05 0,04 0,03 0,02 0,01

0,02 0,03 0,04 0,05 0,06 0,07 0,08 0,09 t, с

RoundRobin

RateBalance

DPB

Рис. 4. Сравнение числа отправленных пакетов

0 0,05 0,1 0,15 0,2 0,25 0,3 0,35 0,4 0,45 t, с

RoundRobin

RateBalance

DPB

Рис. 5. Сравнение среднего времени пребывания требования в системе

Результаты имитационного моделирования показывают, что исследуемая вычислительная сеть, использующая алгоритм RoundRobin, обслуживает вдвое меньшее число заявок на отправление пакетов по сравнению с алгоритмами RateBalance и DPB. В ходе второго этапа имитационного моделирования за время работы сети t, равное 0,5 с, измеряется среднее время пребывания требования в системе T. Как видно из рис. 5, в процессе функционирования сети с алгоритмом RoundRobin среднее время пребывания требования в системе постоянно увеличивается. Это объясняется нарушением условия эргодичности системы, при котором общая интенсивность обслуживания системы должна превосходить интенсивности входного потока требований.

Научно-технический вестник информационных технологий, механики и оптики, 2013, № 2 (84)

87

АППРОКСИМАЦИЯ ВЕРОЯТНОСТНЫХ РАСПРЕДЕЛЕНИЙ …
Эффективность использования пропускной способности гетерогенных каналов (для значений пропускной способности 4 Мбит/с, 10 Мбит/с, 20 Мбит/с) алгоритмом RoundRobin слишком низка, чтобы обслужить имеющийся входящий поток требований. Алгоритм RateBalance позволяет сохранить условие эргодичности системы, однако среднее время пребывания требования в системе вдвое больше по сравнению с алгоритмом DPB.
Заключение Предложен алгоритм распределения кадров по резервированным каналам, производящий оптимальную фрагментацию пакета перед отправкой, что позволяет сократить среднее время пребывания требования в системе. Построена имитационная модель стационарного процесса передачи в вычислительной сети для алгоритмов RoundRobin, RateBalance и DPB, подтверждающая преимущества алгоритма DPB в случае стационарности процесса передачи.
Литература 1. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. – СПб: Питер,
2010. – 944 с. 2. Таненбаум Э. Компьютерные сети. – 5-е изд. – СПб: Питер, 2012. – 960 с. 3. Tunnel provisioning with link aggregation: United States Patent Application Publication, Inventor: Ronen
Solomon. – Pub. Date: Oct. 27, 2011. – Pub. No.: US 2011/0261829 A1. 4. McLean I., Christensen K. Reducing Energy Use: A Dual-Channel Link // IEEE Communications Letters. –
2012. – V. 16. – № 3. – P. 411–413. 5. Богатырев В.А. К управлению взаимосвязью при резервировании неполносвязных магистралей ло-
кальной сети // Электронное моделирование. – 1998. – № 4. – С. 28–32. 6. Богатырев В.А. Комбинаторный метод оценки отказоустойчивости многомагистрального канала //
Методы менеджмента качества. – 2000. – № 4. – С. 30–35. 7. Богатырев B.А. Оценка надежности резервированного канала с межмагистральной ретрансляцией
кадров // Автоматизация и современные технологии. – 2000. – № 4. – С. 2–4. 8. Богатырев В.А. Оценка вероятности полной связности локальных сетей при неполнодоступности ре-
зервированных магистралей // Электронное моделирование. – 1999. – № 5. – С. 102–112. 9. Богатырев В.А., Евлахова А.В., Котельникова Е.Ю., Богатырев С.В., Осипов А.В. Организация меж-
машинного обмена при резервировании магистралей // Научно-технический вестник СПбГУ ИТМО. – 2011. – № 2 (72) – С. 171. 10. Осипов А.В., Богатырев В.А. Варианты объединения разнотипных каналов вычислительной сети // Научно-технический вестник информационных технологий, механики и оптики. – 2012. – № 2 (78). – С. 145. 11. Поляков А.Ю. Адаптивный подход к распределению информационных блоков по каналам передачи данных // Электросвязь. – 2009. – № 6. – С. 32–35. 12. Осипов А.В., Фролова Н.И. Задача оптимизации при сегментации пакетов в беспроводных сетях // Сборник трудов молодых ученых и сотрудников кафедры ВТ. – СПб: СПбГУ ИТМО, 2012. – Вып. 3. – С. 44–46.
Осипов Андрей Владимирович – Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, аспирант, osipov-andrey@mail.ru
88 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 2 (84)