Балансировка интернет-трафика с помощью статической маршрутизации как задача оптимизации

Размещено на http://www.allbest.ru/

БАЛАНСИРОВКА ИНТЕРНЕТ-ТРАФИКА С ПОМОЩЬЮ СТАТИЧЕСКОЙ МАРШРУТИЗАЦИИ КАК ЗАДАЧА ОПТИМИЗАЦИИ

Abstract

Organizing a relevant and stable data transfer in rural and sparsely populated areas with unstable telecommunication networks and expensive data traffic using multiple telecommunication channels is sometimes a non-trivial problem. We offer an approach to adapted static routing for organizing reliable data transfer with minimum cost.

Качественное улучшение каналов связи и развитие технологий широкополосного доступа, типичные для мегаполисов, менее заметны в удаленных областях, где сети, тем не менее, жизненно необходимы. Как правило, неразвитость традиционных сетей, телефонных, электрических и т.д., ограничивает применение, например, технологии ADSL, которая в случае шумных телефонных линий вырождается в узкополосную технологию. Технологии радиодоступа дороги и ненадежны. Модемные dial-up соединения все еще популярны наряду с модемами для физических линий. На рис. 1 показана типичная сеть организации (“последняя миля” Интернета).

Для гарантированного доступа к Internet сетевые администраторы используют каналы связи различных провайдеров или разные технологии доступа, которые могут сильно различаться ценой трафика. Зависимость стоимости трафика и его объема может быть нелинейной. Так, в случае использования выделенных линий и радиоканалов, провайдеры могут устанавливать фиксированную стоимость, включающую некий объем трафика, а за трафик сверх нормы устанавливать дополнительный тариф (см. рис.2). Задача администратора сети состоит в снижении стоимости потребленного трафика при обеспечении гарантированной быстрой и бесперебойной передачи. Здесь мы рассматриваем и решаем эту задачу как 2-критериальную задачу оптимизации.

Рассматриваемая проблема часто обсуждается на форумах специалистов и в научных работах [1,2]. Некоторые работы предлагают готовое решение отдельных аспектов проблемы. Организация VPN-соединений поверх нескольких физических каналов со статической или динамической маршрутизацией (или с использованием статических таблиц, изменяемых по некоторым правилам) детально изучена [3,4]. Подходы в этих работах дают либо общее увеличение суммарной пропускной способности, либо создание оптимизированных статических таблиц по заранее исследованному потреблению трафика. Использование VPN возможно лишь для оптимизации использования каналов внутри одной организации и неприемлемо для оптимизации расходования собственно трафика Интернет [6]. Зачастую мы не можем предсказать потребление трафика из-за его скачкообразности и самоподобности [5]. Поэтому прогноз должен постоянно корректироваться, чтобы критически важные классы трафика занимали наиболее надежные в настоящий момент каналы, оставляя менее важным классам другие, дешевые каналы. Использование динамической маршрутизации требует либо использования VPN, либо возможности управления маршрутизацией в сетях провайдера, что, в общем случае, практически невозможно [5,6].

Рис.1. Схема сети

Рис.2. Стоимость трафика для трех интерфейсов

Вышеперечисленные причины определяют использование статических таблиц маршрутизации с возможностью их изменения. Нежелательно менять маршруты открытых TCP-соединений, однако, если использовавшийся канал прекратил работу, такое переключение является единственно верным решением. Приложения, не создающие долгих ТСР-соединений, например, DNS-серверы, позволяют переключать маршруты без серьезных сложностей. Другие, как https- или rdp-соединения, чувствительны к переключению, даже если долго бездействуют. Таким образом, мы должны разделить трафик по классам и в соответствии с приоритетом, и с возможностью его безболезненного переключения. Возможности управления таблицами маршрутизации (утилита “route”) есть в ОС Unix/Linux и Win2003/2008.

Кроме того, оптимальное управление трафиком требует наличия средств измерения объемов трафика по классам. Мы должны иметь возможность определять текущее потребление трафика за единицу времени и потребленный объем за расчетный период (как правило, месяц). Встроенных возможностей Linux, например, утилиты “iptables”, вполне достаточно [7]. В этом случае мы создаем “цепочку” iptables для каждого класса трафика, и используем эту же утилиту для учета потребленного трафика по цепочкам.

Как алгоритмический язык, использован Perl. В качестве СУБД для хранения данных учета трафика мы использовали MySQL.

Здесь мы не решаем задачу обеспечения приоритетности трафика и выделения полос под трафик определенных классов. Мы предполагаем, что эта задача уже решена каким-либо способом, например, тем же iptables.

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

Одна из наших целей - снижение общих затрат на трафик. Мы можем оперировать только прогнозами стоимости трафика за расчетный период.

(1)

Здесь m - число классов трафика, n - число интерфейсов, P_j - функция стоимости трафика, маршрутизируемого через j-й интерфейс за расчетный период, ее аргумент - прогноз объема потребляемого трафика, v_j0 - объем трафика, уже израсходованого через j-й интерфейс, v^*_i - среднее значение используемого объема трафика i-го класса, вычисленное за единицу времени, q - число этих единиц времени до конца расчетного периода (здесь мы учитываем только рабочее время организации), p_ij =0 если трафик i-го класса, маршрутизируемый через j-й интерфейс бесплатен, иначе p_ij=1, x_ij - булева переменная, означающая маршрутизацию трафика i-го класса через j-йинтерфейс, X - матрица переменных x_ij.

Ограничения для нашей задачи:

(2)

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

,(3)

где a_i - средний объем i-го класса трафика в секунду, вычисленный только в периоды, когда загрузка хотя бы одного из каналов высока [8], c_j - скорость передачи j-го канала. Сформулируем вторую цель:

(4)

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

Выражения (1), (4) и (2) составляют 2-критериальную задачу оптимизации псевдобулевых функций с ограничениями. Подход [9] позволяет решать такие задачи как задачи с 1 критерием, если мы имеем единую шкалу для количественной (денежной) функции (1) и качественной оценки (4). Определим денежную оценку неиспользованной полосы пропускания (4). Коэффициент k - стоимость увеличения общей полосы пропускания на 1%. Так, если мы готовы платить на 1% больше за среднее увеличение общей полосы пропускания на 1%, то k=1. Запишем целевую функцию так:

(5)

Для задач большой размерности, к которым наша задача относится при большом числе классов трафика и интерфейсов, мы можем использовать гибридный алгоритм [9] на базе метода изменяющихся вероятностей [10].

Для оценки эффективности метода мы использовали сеть, показанную на рис.1. Интерфейс 1 - модем для физических линий (92 кбит/с), интерфейс 2 - Ethernet (кампусная сеть) с выходом в Интернет (300-500 кбит/с), интерфейс 2 - ADSL (менее 1 мбит/с). Входящий трафик потребляется офисом 1 (около 8 Гбайт в месяц), пользователи офиса 2 не потребляют входящий трафик непосредственно. Трафик VPN-соединения бесплатен. Пользователи офиса 1 подключены к Интернету через интерфейс 1, интерфейс 2 непосредственно или через интерфейс 3 через VPN и роутер 2. Выделено 42 класса трафика.

Итоговые данные за месяц с использованием алгоритма оптимизации приведены в таблице 1. Объем и стоимость трафика без использования алгоритма оценены исходя из статических таблиц маршрутизации.

Для оценки качества мы должны оценить способность системы максимально загружать каналы связи в моменты, когда система максимально загружена трафиком критически важных классов. Мы провели эксперимент. В соответствии с лог-файлом мы симулировали сетевую активность с четырьмя классами трафика. Мы рассчитывали возможный простой каналов связи при использовании нашего алгоритма и без него (объемы трафика - из реального лог-файла). Результаты даны в таблице 2.

Таблица 1. Стоимость каналов передачи данных

Таблица 2. Средний битрейт без использования алгоритма и с ним

Предложенная система эффективна для снижения издержек, что подтверждено измерениями. Качество сервиса при этом также повышается, что подтверждается как расчетами, так и субъективной оценкой пользователей, таким образом, наша 2-критериальная задача оптимизации решена.

Литература

1. Johnson Y. Smart Routing Against Congestion. http://www.osp.ru/nets/2002/04/025.htm

2. Ash G.R., Dynamic Routing in Telecommunication Networks, AT&T, 1997.

3. Северов М. Оптимизация IP-трафика, http://zeus.sai.msu.ru:7000/nets/hard/accelerator

4. Rudin H., Mueller H., Dynamic Routing and Flow Control, IEEE Trans.on Comm., vol. Com-28, No.7, July 1980.Chu Y., Rao S.G., Zhang H. A Case For End System Multicast, in Proc. ACM SIGMETRICS, June 2000

5. Petrov V.V., Self-Similar Netork Traffic; From Chaos and Fractals to The Prognose and Quality of Service, Conference NEW2AN, Abstracts, S.-Petersbourg, 2004, pages 110-118.

6. Khanvilkar S., Khokhar A., Virtual Private Networks: An Overview with Performance Evaluation. Communications Magazine, IEEE, vol.42, issue 10, pages 146-154.

7. Diehl M., Generating Firewall Rules with Perl, Linux Journal, vol. 2006, Issue 143 (March 2006), page 4.

8. Lai K. And Baker M., Nettimer: A Tool for Measuring Bottleneck Link Bandwidth, in Proc. of the 3^rd USENIX Symposiom on Internet Technologies and Systems, March 2001.

9. Казаковцев Л.А. Адаптация метода изменяющихся вероятностей для задач ассортиментного планирования и других. Вестник НИИ СУВПТ, выпуск 6, НИИ СУВПТ, Красноярск, 2001, с. 42-50.

10. Антамошкин А.Н. Оптимизация функционалов с булевыми переменными. - Издательство Томского университета, Томск, 1987.

Размещено на Allbest.ru