Балансировка интернет-трафика с помощью статической маршрутизации как задача оптимизации
Скачать 103.86 Kb.
|
| БАЛАНСИРОВКА ИНТЕРНЕТ-ТРАФИКА С ПОМОЩЬЮ СТАТИЧЕСКОЙ МАРШРУТИЗАЦИИ КАК ЗАДАЧА ОПТИМИЗАЦИИ Казаковцев Л.А. Красноярский государственный аграрный университет, Красноярск, Россия 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 – число интерфейсов, Pj – функция стоимости трафика, маршрутизируемого через j-й интерфейс за расчетный период, ее аргумент – прогноз объема потребляемого трафика, vj0 – объем трафика, уже израсходованого через j-й интерфейс, v*i – среднее значение используемого объема трафика i-го класса, вычисленное за единицу времени, q – число этих единиц времени до конца расчетного периода (здесь мы учитываем только рабочее время организации), pij =0 если трафик i-го класса, маршрутизируемый через j-й интерфейс бесплатен, иначе pij=1, xij – булева переменная, означающая маршрутизацию трафика i-го класса через j-йинтерфейс, X – матрица переменных xij. Ограничения для нашей задачи:  (2)Рассмотрим вторую цель – повышение общей пропускной способности как задачу достижения равномерной загрузки каналов. Время простоя канала в те моменты, когда другие каналы сильно загружены, должно быть минимизировано. Если общая загрузка системы высока, то оптимальная загрузка каждого канала достигается, когда  , (3)где ai – средний объем i-го класса трафика в секунду, вычисленный только в периоды, когда загрузка хотя бы одного из каналов высока [8], cj – скорость передачи 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 3rd USENIX Symposiom on Internet Technologies and Systems, March 2001. 9. Казаковцев Л.А. Адаптация метода изменяющихся вероятностей для задач ассортиментного планирования и других. Вестник НИИ СУВПТ, выпуск 6, НИИ СУВПТ, Красноярск, 2001, с. 42-50. 10. Антамошкин А.Н. Оптимизация функционалов с булевыми переменными. – Издательство Томского университета, Томск, 1987. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Добавить документ в свой блог или на сайт
Похожие:
 | Реферат По предмету: «Технические средства контроля диагностики и... В связи с увеличением потребления трафика в локальных сетях встречаются ситуации, когда одни приложения монополизируют весь сетевой... |  | О порядке маршрутизации больных эндокринологического профиля в городе Челябинске Порядок маршрутизации больных эндокринологического профиля для оказания первичной специализированной помощи на амбулаторно-поликлиническом... |
| Русакова Наталия Михайловна, Учитель гбоу лицея №95 Эта приоритетная задача решается, в том числе, и с помощью использования здоровьесберегающих технологий. Одна из них обучение диафрагмально-релаксационному... | | Задача 1 22 Вариант 3 22 Задача 1 22 Вариант 4 23 Задача 1 23 Задача... «Менеджмент». Дисциплина реализуется кафедрой экономики и управления. Дисциплина нацелена на формирование общекультурных компетенций... |
| Наиболее часто встречающиеся угрозы при работе в Интернет ... | | Задача оптимизации защищенности каналов управления робототехническими системами С тех пор и до сих пор постоянно растет количество молодых ученых и специалистов, которые в этом участвуют |
| Задача формирования познавательных интересов очень актуальна для... «Познавательный интерес как фактор развития активности и самостоятельности школьника» | | Ресурсы сети Интернет для родителей и их описание С помощью современных поисковых систем можно проводить поиск самых разных электронных ресурсов сети Интернет, использование которых... |
| Является пpиобpетение студентами теоретических и практических знаний... Задачей дисциплины является ознакомление студентов с основными интернет-технологиями и развитие навыков создания с их помощью web-представительств... | | Урок по информатике 8 класс Тема: «Поиск информации в Интернет» Интернет. Сегодня на уроке вы познакомитесь, как искать информацию в Интернет. Как сохранять информацию, полученную из Интернета.... |
| «Исследование операций и методы оптимизации» Теоретическая и практическая подготовка в области общенаучных исследований количественной стороны массовых социально-экономических... | | “Интернет-ресурсы на уроках английского яз В настоящее время перед всеми педагогами стоит задача научиться использовать Всемирную сеть в целях совершенствования содержания... |
| Понятие Интернет-зависимости, её причины, типы, признаки, последствия Таким образом, на сегодняшний день каждый третий житель России является пользователем Интернета, а каждый седьмой посещает Интернет... | | Тематический план изучения курса учебной дисциплины «Здоровый образ жизни и его составляющие» Здоровье как государственная задача и личная потребность человека. Основные понятия категории здоровье. Здоровье как государственная... |
| Сведения по практической балансировке Балансировка роторов – процесс компенсации их дисбалансов путем установки корректирующих масс в доступные плоскости коррекции | | Протокол маршрутизации (IP)? В текстовом редакторе основными параметрами при задании параметров абзаца являются… |
