Московский Физико-Технический Институт

(Государственный Университет)

На правах рукописи

Гончаров Андрей Андреевич

Исследование условий обеспечения гарантированного

качества обслуживания в сети Интернет

Специальность 05.12.13 Системы, сети и устройства телекоммуникаций

Автореферат

диссертации на соискание учёной степени кандидата технических наук

Москва 2007

Работа выполнена на кафедре инфокоммуникационных технологий Московского физико-технического института (ГУ).

Научный руководитель: кандидат физико-математических наук, доцент Семёнов Юрий Алексеевич

Официальные оппоненты:

доктор технических наук, ведущий научный сотрудник Ляхов Андрей Игоревич кандидат технических наук, доцент Кулагин Михаил Викторович

Ведущая организация:

Государственный научный центр Российской Федерации – Российский научный центр «Курчатовский институт»

Защита состоится «22» мая 2007 г. в 15:30 на заседании диссертационного совета К212.156.04 при Московском физико-техническом институте (ГУ) по адресу: 141700, г. Долгопрудный, Московской обл., Институтский пер., д.9, ауд. 204 Нового корпуса.

С диссертацией можно ознакомиться в библиотеке Московского физикотехнического института (ГУ).

Автореферат разослан «16» апреля 2007 г.

Ученый секретарь диссертационного совета кандидат технических наук, доцент Куклев Л.П.

Общая характеристика работы

Актуальность темы. Эффективность использования полосы пропускания канала всегда была актуальной задачей, но её важность возросла в последние годы в связи с появлением всё более жестких требований к качеству обслуживания (QoS).

Для обеспечения необходимых требований к различным потокам данных используются два метода QoS: управление перегрузкой (congestion management) и предотвращение перегрузок (congestion avoidance). Первый метод основан на присвоении квот и приоритетов потокам, и в случае перегрузки, потоки получают качество, ограниченное их квотой и приоритетом (например, WFQ- Weighted Fair Queuing). Второй метод ограничивает размер очереди, сигнализируя источникам данных о необходимости уменьшить скорость передачи информации (например, WRED - Weighted random early detection).

Ведётся активное исследование в области методов, ограничивающих размер очереди. Можно перечислить лишь некоторые, наиболее известные модификации алгоритма RED1: WRED, GRED (Gentle RED), DRED (Dynamic RED), SRED (Stabilized RED), ARED (Adaptive RED), RED-PD.

Отдельно следует упомянуть учёных, которые первыми начали решать проблему предотвращения и борьбы с перегрузками: Салли Флойд (Sally Floyd), Ван Якобсон (V. Jacobson), Кевин Фолл (Kevin Fall), Ратул Махаджан (Ratul Mahajan), Мартин Мэй (Martin May), Жан Болот (Jean Bolot), Вишал Мисра (Vishal Misra), Вейбо Гонг (WeiBo Gong), Дон Тоуслей (Don Towsley), Томас Зейглер (Thomas Ziegler), Давид Везерол (David Wetherall), Добрушин Р.Л., Кузнецов Н.А.,Вишневский В.М., Ляхов А.И., Богуславский Л.Б., Дрожжинов В.И., Башарин Г.П., Бочаров П.П..

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

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

1. Floyd S., Jacobson V., «Random Early Detection Gateways for Congestion Avoidance», IEEE/ACM Transactions on Networking, pp.397- 413, August К числу параметров качества обслуживания следует отнести доступную полосу пропускания, вероятность потери пакета, разброс времени доставки и само время доставки пакета от отправителя до получателя. Все эти параметры зависят от алгоритмов формирования и обслуживания очередей пакетов в сетевых устройствах (переключателях и маршрутизаторах). В современных сетевых устройствах применяются алгоритмы RED/WRED (random early detection/weighted random early detection), PQ (priority queueing), WFQ (weighted fair queueing), LLQ (low latency queueing), CBWFQ (class based weighted fair queueing) и т.д. В данной работе выполнено практическое исследование модели DiffServ (Differentiated Services – механизм который в зависимости от требований к качеству обслуживания записывает в IP заголовки пакетов специальные метки DSCP - Diff-Serv Code Point, значение которых учитывается сетевым оборудованием при передача пакета через сеть) в том виде, как она реализована в сетевом оборудовании на сегодняшний день. В результате исследований современных средств обеспечения качества обслуживания (QoS, DiffServ, MPLS-TE - Multiprotocol Label Switching Traffic Engineering, RSVP-TE) были сформулированы практические рекомендации для сервиспровайдеров, желающих предоставить определенные параметры качества обслуживания своим клиентам (полосу пропускания, гарантированную задержку и ее дисперсию, минимальную вероятность потери пакетов).

В рамках измерений и моделирования виртуального канала (с привлечением программного пакета NS-2) показано, что при некоторых конфигурационных параметрах возможны осцилляции длины очереди (особенно для потоков среднего и низкого приоритета). Этот эффект связан с механизмом вычисления усредненного значения длины очереди в алгоритмах WRED и RIO (RED with Input Output). Такие осцилляции могут привести к росту дисперсии RTT (Round Trip Time - сумма времен доставки сегмента от отправителя до получателя и отклика от получателя до отправителя), что крайне нежелательно для работы с мультимедийными данными и при решении задач управления в реальном масштабе времени.

Осцилляции усредненной длины очереди понижают также эффективность использования канала. Выработаны рекомендации и получены аналитические оценки значений конфигурационных параметров, минимизирующих влияние этого явления. Определена зависимость амплитуды этих осцилляций и постоянной затухания от T1, T2, pc, wq и отношения (квота полосы), где T1 и T2 - нижний и верхний порог отбрасывания WRED, pc -максимальная вероятность отбрасывания, wq коэффициент усреднения, / - коэффициент перегрузки канала, где – интенсивность входящего потока, а -полоса пропускания потока в выходном канале. Коэффициент перегрузки канала задаётся с помощью механизма WFQ. В рамках данного исследования механизм WFQ позволяет задавать квоту полосы канала, доступную для приоритетного потока. Для очередей с высоким приоритетом усредненная длина очереди не должна превышать уровня Т2, иначе возникают осцилляции длины очереди и, как следствие, принудительное отбрасывание пакетов. Анализ осцилляций очередей показал, что следует внимательно относиться к выбору параметров протокола WRED и WFQ (квоты полосы канала). В противном случае ресурсы канала будут использоваться неэффективно.

Неоптимальный выбор T1, T2, wq и pc может существенно увеличить дисперсию RTT, и вероятность потери пакетов. Разработан комплекс программ для измерения параметров качества обслуживания (полосы пропускания, RTT, дисперсии RTT и вероятности потери пакетов, а также корреляций этих характеристик), расчета характеристик осцилляций усредненной длины очереди и графического отображения эволюции параметров QoS.

Цель диссертационной работы - исследование методов обеспечения гарантированного качества обслуживания для привилегированных субпотоков и поиск оптимальных параметров работы алгоритма WRED. В задачи исследования входило:

1. Разработка рекомендаций по проектированию и диагностике сетей для обеспечения требуемого качества обслуживания потоков, проходящих через сеть Интернет (рассматриваются следующие параметры качества обслуживания: полоса пропускания, RTT, дисперсии RTT и вероятности потери пакетов, а также корреляции этих характеристик). Исследование влияния осцилляций длин очередей в буферах маршрутизаторов на значения параметров качества обслуживания 2. Разработка средств измерения параметров качества обслуживания в Интернет.

3 Разработка алгоритма измерения процента потерь пакетов в удалённых сетевых сегментов для отслеживания качества предоставленных услуг.

4 Разработка алгоритма для выявления причин потерь пакетов в сетевом канале. (Потери из-за переполнения буферов в сетевых устройствах по пути следования или повреждение пакетов при транспортировке).

5 Разработка методик оптимизации конфигурационных параметров для получения нужных параметров QoS.

6 Моделирование процессов в сети Интернет, влияющих на качество обслуживания.

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

Научная новизна. В представленной работе предлагаются два новых метода отслеживания качества обслуживания в удалённых сегментах сети.

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

2.Второй метод позволяет выявить участки сети, содержащие источники наводок и искажений. Второй метод основывается на зависимости вероятности потери пакета от длины пакета. Он позволяет определять характер потерь пакетов (потерь, сопряженных с искажениями передаваемых кадров).

3.Впервые произведено подробное исследование причин и следствий осцилляций длин очередей в буфере маршрутизатора. Определено влияние осцилляций на параметры качества обслуживания. 4.Предложены методы минимизации осцилляций длин очередей в буфере маршрутизатора.

5.Решена проблема идентификации откликов при использовании нескольких независимых потоков ICMP.

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

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

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

Апробация результатов работы. Основные результаты диссертации докладывались:

- на научных конференциях Московского Физико-технического института (г. Долгопрудный) в 2002, 2004, 2005, 2006 гг.

- на школе-семинаре по компьютерной автоматизации и информатизации, ACS`2002 (г. Москва 2002 г.) - на III Международной Конференции "Интернет нового поколения IPv6" (г. Москва 2004 г.) Положения, выносимые на защиту.

1.Рекомендации по проектированию и диагностике сетей для обеспечения требуемого качества обслуживания потоков, проходящих через сеть Интернет. Результаты исследования влияния осцилляций длин очередей в буферах маршрутизаторов на значения параметров качества обслуживания 2.Средства диагностики и методы измерения параметров качества обслуживания в Интернет.

3.Методика оптимизации конфигурационных параметров для получения нужных значений параметров QoS.

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

5.Результаты сопоставления моделирования и результатов измерений.

Публикации по теме работы. Результаты диссертации опубликованы в работах из которых 5 работ в электронных журналах, 6 публикаций в виде тезисов докладов на конференциях, 1 публикация в печатном виде в научно-техническом журнале.

Структура и объём диссертации. Работа состоит из введения, четырёх глав, заключения и списка литературы. Общий объём диссертации страниц, приведено 98 рисунков, 9 таблиц. Список литературы включает наименований.

Содержание работы Во Введении приводятся названия существующих алгоритмов и технологий QoS. Приводится список Зарубежных и отечественных учёных занимавшихся проблемой обеспечения качества обслуживания.

В первой главе приводится краткий обзор литературы по теме диссертации, приводится обзор того, что было сделано в мире по данной теме, формулируется постановка задачи и цель работы. В основе рекомендаций для обеспечения требуемого качества обслуживания потоков лежит оптимальный выбор параметров для алгоритмов управления очередями WFQ и WRED. Исследовались возможности механизмов WRED и WFQ и влияние конфигурации этих алгоритмов на качество услуг. Для подбора параметров использовались результаты экспериментальных измерений в тестовом канале и в программе моделирования NS-2. Для решения задачи анализировались различные модели доставки пакетов в рамках протоколов ICMP, UDP и TCP. Для каждого потока задавался набор параметров: T1, T2, pс, wq, /. Для каждого субпотока задавался процент доступной полосы пропускания (настройка WFQ). В экспериментах строились зависимости разных параметров QoS (потерь, задержек RTT) при изменении одного из параметров WFQ или WRED. После измерения и сравнения всех возможных случаев делается вывод об оптимальной настройке параметров WRED и WFQ.

Во второй главе описываются два механизма удалённой диагностики локальных сетей. Проблема обеспечения качества обслуживания многогранна, и в ранних исследованиях изучался вопрос о выявлении проблемных участков сети, в которых происходят потери пакетов, исследовался механизм накопления потерь пакетов. В рамках данного исследования было разработано два алгоритма удалённой диагностики локальных сетей. Эти алгоритмы, опробованные на практике [5,6,7], они позволяют находить в сети проблемные участки, которые могут сильно влиять на качество передачи данных через эти участки.

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

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

N1, N2,..., Nn – активные сетевые устройства, т.е. такие приборы, где происходит буферизация пакетов и возможна их потеря.

А, В,…. – это подмножество машин из сетевых сегментов 1, 2,…, n, чьи сетевые интерфейсы не очень загружены (например, слабо загруженные рабочие станции).

Тестовая ЭВМ находится в сегменте, подключенном к сетевому устройству N1. На ЭВМ установлена программа, которая последовательно посылает ICMP запросы к подмножествам А, В, … машин из сегментов N1, N2,..., Nn. Та же тестовая ЭВМ обрабатывает ICMP отклики, пришедши из сегментов. ICMP отклики имеют ту же длину, что и ICMP запросы. Считается, что вероятности потери в промежуточном устройстве для запроса и отклика во время эксперимента не меняются и равны между собой.

Если на вход канала в N1 поступило S пакетов, направленных в субсеть n, то из N1 в N2 поступит S*(1-1), где 1 - вероятность потери пакета в активном устройстве N1.

По аналогии получим выражение для количества пакетов, дошедших до сегмента n и вернувшихся обратно отправителю – тестовой ЭВМ:

R = S·(1-1)2·(1-2)2·(1-n-1)2·(1-n), где n – процент потерянных пакетов в удаленном сегменте n.

Степень 2 возникает из-за того, что пакеты могут теряться в сетевых устройствах как по пути туда, так и обратно. При этом предполагается, что вероятности потери пакета на пути туда и обратно равны. При отправке отклика из машины сегмента n потеря невозможна, по этой причине сомножитель (1-n) представлен в первой степени, На практике измеряются величины (1-1)2, (1-2)2,….

Из базы данных берётся информация о принадлежности того или иного IP-адреса ЭВМ к представляющему интерес сегменту и производится зондирование всех машин субсети. Каждая ЭВМ зондируется последовательно сериями по три пакета. Если все три пакета не дали отклика, машина считается выключенной, и эти данные не учитываются при оценке вероятности потери пакета. Такой подход приводит к определенному занижению вероятности потерь, но эффект незначителен, так как 3 даже при вероятности потери =0,1 составляет лишь 0,1%, и его влиянием можно пренебречь. При измерениях не происходит завышения вероятности потерь пакетов за счет отключенных в данный момент ЭВМ.

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

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

Если потери сопряжены с искажениями пакетов при транспортировке, то зависимость вероятности потерь PL от длины L пакета должна характеризоваться зависимостью PL=L(1-p(1-p)L), где p – вероятность повреждения одного бита (BER - Bit Error Rate), L – количество бит в пакете, и имеет размерность штук.

С учетом того, что BER лежит в диапазоне 10-3-10-10, а L>512 бит, при малых L имеет место приближённая формула PL=(1- p(1-L·p + 0,5*p3L(L-1))). Таким образом, можно приближённо ожидать квадратичную зависимость вероятности потерь от длины пакета для малых L. Это обстоятельство можно использовать для анализа свойств каналов и причин измерения вероятности потерь.

Измеряя зависимость вероятности потерь от длины пакета и, идентифицировать причины потерь. Были проведены исследования потерь пакетов для двух маршрутов. Для канала ПРАН - Санкт-Петербургское математическое общество и ПРАН – (ИММ) Екатеринбург. Были проведены измерения вероятности потери для длин пакетов 64, 128, 256, 512, 1024 и 1450 байт. Для каждой из длин было послано по 2000 ICMPпакетов. Результаты измерений показаны на рис. 2. и 3.

Рис. 2. Зависимость числа потерянных пакетов (из 2000 посланных пакетов) от длины пакета для маршрута ПРАН – Санкт-Петербургское математическое общество. По вертикали отложено число потерянных пакетов, по горизонтальной оси отложена длина В общем виде имеет место утверждение: Сpath = PL +F(L), где Сpath полная вероятность потери пакета на всём маршруте, L- число бит в пакете.

Аппроксимация полиномом второй степени по методу наименьших квадратов дает следующую зависимость вероятности потери пакета от его длины.

Сpath = (14,33 ± 6) + (0.298 ± 0.04)·L - ·(0.00012 ± 3·10 ) L Рис. 3. Зависимость числа потерянных пакетов (из 2000 посланных пакетов) от длины пакета для маршрута ПРАН – ИММ (Екатеринбург). По вертикальной оси отложено число потерянных пакетов, по горизонтальной оси отложена длина пакетов в байтах Для второго случая зависимость полной вероятности потери пакета от его длины может быть приближено следующей формулой.

Сpath = (25.56 ± 4.42) + (0.00167 ± 0.01)·L - (9.46·10 ± 1.23·10 )·L Значение вероятности потери пакетов для пакетов интересующей длины можно получить из рис. 2 и 3, поделив число потерянных пакетов на общее число отправленных пакетов (для каждой длины отправлялось пакетов).

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

3 - вероятность потери определяется переполнением буфера, емкость которого задается в сегментах.

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

В третьей главе описаны результаты экспериментов по обеспечению QoS в среде моделирования NS-2. Цель данного моделирования - разработка дополнительных средств измерения и анализа параметров QoS. Мы также хотели иcследовать возможность применения модельных методов оценки параметров качества обслуживания.

1) Проведены исследования алгоритмов RIO-C и WRED для разных моделей назначения порогов. Было также исследовано влияние алгоритмов-диспетчеров на предоставляемое качество обслуживания.

Установлены оптимальные границы работы алгоритмов WRED и RIO, при которых использование этих алгоритмов является наиболее эффективным.

2) К встроенным в NS-2 функциям были добавлены утилиты для расчета и отображения значений средневзвешенных очередей и вероятности отбрасывания пакетов. Это было необходимо для изучения и интерпретации поведения нашей тестовой сети.

3) Получены зависимости длин очередей от времени, длин средневзвешенных очередей от времени и вероятности отбрасывания пакетов от времени. Выполнен также анализ этих зависимостей и выработаны рекомендации по установке параметров алгоритмов WRED и RIO для достижения оптимальной работы (для модели).

4) Произведён подбор параметров модели виртуальной сети таким образом, чтобы она адекватно отражала работу тестовой сети. Было произведено полномасштабное моделирование для широкого набора параметров, были получены условия, при которых модель и эксперимент на реальной сети ведут себя подобным образом.

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

Усреднение длины очереди является важным компонентом алгоритма управления процессом буферизации. Без усреднения процесс буферизации был бы подвержен сильному влиянию случайных флуктуаций входного потока пакетов. Но именно усреднение является причиной возникновения осцилляции длины очереди. Ведь зависимость принятия решения об отбрасывании того или иного пакета определяется значением усреднённой длины очереди, которое может сильно отличаться от текущего значения длины очереди. Амплитуда вариации текущего значения длины очереди существенно больше усреднённого. Расчёты показывают, что при определённых параметрах текущая длина очереди может достигать в максимуме полного объёма буфера, а в минимуме нуля (т.е. буфер уже пуст, а отбрасывание пакетов продолжается см. рис. 4).

Рис. 4. Зависимость от времени Q и Q (wq=0,002; pc= 0,2; Т1=25; Т2=60; размер буфера = На рис. 4 ромбиками отмечена зависимость текущего значения длины очереди от времени. Отсюда видно, что усредненные значения длины очереди на начальном участке зависимости уступают текущей длине более, чем в два раза. В расчётах входной поток и выходной задавались в битах в секунду. В области от 0 до T1 рост длины очереди определяется произведением (-)t. После достижения уровня Т1 скорость роста длины очереди замедляется, так как часть пакетов отбрасывается, зависимость становится квадратичной. Прекращение роста и начало спада Q происходит в момент, когда Q достигает уровня Т2. Расчёты проводились с привлечением пакета программ NS-2. Значения Т1 и Т2 задавались в пакетах.

На рис. 5 показана зависимость осцилляций длины очереди от фактора усреднения wq. (T1=25, T2=40, /=1,4, pc=0,1). Из рисунка видно, что приемлемые значения лежат в области wq>0,003. При меньших значениях wq осцилляции не затухают даже через 10 с после начала перегрузки.

Равновесное значение Q ~ T2=40.

Оптимальный выбор параметров алгоритма WRED позволяет увеличить эффективность использования буферов маршрутизатора и, как следствие, поднять пропускную способность или улучшить уровень QoS.

Подобным образом проводились вариации всех параметров WRED.

Из полученных данных был сделан вывод, что приемлемый набор параметров с точки зрения осцилляций длины очереди соответствует: