ДонНТУ   Портал магистров

Реферат по теме выпускной работы

Содержание

Введение

Современные средства коммуникаций используют преимущественно каналы связи с пакетной коммутацией. Это позволяет повысить эффективность использования каналов, однако приводит к снижению надежности доставки информации. При перегрузке канала с пакетной коммутацией возможна ситуация, когда пакет на входе канала не поместится во входной буфер и будет отвергнут. Для обеспечения гарантированной доставки по каналам без гарантированной доставки были разработаны специальные протоколы. Один из самых популярных – это протокол TCP из стека протоколов TCP/IP. Он проектировался для доставки данных служб обмена файлами, электронной почты и т.п.. Для этих служб основным требованием была корректная доставка информации. При этом время доставки не является критическим фактором. Развитие мультимедийных технологий поставило задачу доставки сообщений при соблюдении высоких требований качества обслуживания: малая задержка и малая вариация задержки. Эта задача решается с помощью регулирования скорости передачи и приема сообщений.

Управление скоростью передачи осуществляется с помощью алгоритма управления перегрузкой (TCP congestion control algorithm). Именно он управляет шириной скользящего окна и контролирует интенсивность передачи данных tcp-передатчиком. В нем реализованы обработчики следующих событий: прием ответа-подтверждения доставки от приемника, потеря пакета в буфере маршрутизатора (на дороге доставки пакета), превышение времени ожидания ответа приемника. Протокол TCP проектировался для распределенных сетей со значительным временем доставки. Сначала в протокол был заложен простой алгоритм с минимальным вычислительным нагрузкой на процессор системы. Производительность процессоров за последние 30 лет выросла многократно, пропускная способность каналов связи увеличилось в тысячи раз, а время доставки для высокоскоростных локальных и глобальных сетей составляет доли микросекунд. Согласно технического прогресса развивался и протокол TCP.

1. Актуальность теми

Проблема перегрузки в сетях TCP/IР возникает в случае, когда количество передаваемых данных начинает приближаться к значению допустимой пропускной способности сети. При этом ухудшаются основные показатели качества обслуживания. Эти ухудшения могут выражаться в увеличении числа потерянных пакетов и времени задержек. Управление перегрузками является актуальной задачей, поскольку количество конечных пользователей глобальной сети, а, следовательно, объемы передаваемых данных, постоянно увеличиваются. Растет также доля мультимедийного трафика реального времени, влияние перегрузок на который особенно критично. Задача механизмов управления перегрузками заключается в том, чтобы поддерживать количество данных, передаваемых по сети, ниже уровня, при котором пропускная способность сети начинает резко падать, ограничивая потоки входящего и исходящего трафика.

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

Магистерская работа посвящена актуальной научной задачи оценки эффективности работы алгоритмов для борьбы с перегрузкой протоколов транспортного уровня стека TCP/IP. В качестве математического модели используется гидродинамическая модель потока, которая позволяет учесть все особенности работы противоперегрузочных алгоритмов.

2. Цель и задачи исследования

Целью исследования является моделирование и оценка эффективности работы алгоритмов для борьбы с перегрузкой протоколов транспортного уровня стека TCP/IP.

Основные задачи исследования:

  1. Проанализировать основные алгоритмы, используемые в протоколе ТСР для борьбы с перегрузками.
  2. Разработать реализацию математической гидродинамической модели для выбранных противопергрузочных алгоритмов.
  3. Провести моделирование работы выбранных алгоритмов при различных входных параметрах.
  4. На основе полученных результатов провести анализ и сравнить работу различных алгоритмов в одинаковых условиях.

Объект исследования: мультисервисная сеть

Предмет исследования: алгоритмы для борьбы с перегрузкой протоколов транспортного уровня стека TCP/IP

3. Научная новизна

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

4. Анализ существующих исследований и публикаций

Проблема перегрузки в каналах связи сетей TСР/ІР является весьма актуальной на данный момент, поэтому ей посвящено большое количество работ, в которых раскрывается сущность данной проблемы, причины ее возникновения и пути решения [1, 2,7,8,9].

Исследование работы противоперевантажних алгоритмов транспортного уровня стека TСР/ІР описано в работах [3 - 5, 10].

В настоящее время очень распространена гидродинамическая модель потока (fluid flow model), которая приведена в работе [6], т.к. у для наблюдения поведения алгоритмов для борьбы с перегрузкой необходимо использовать такую математическую модель, которая будет учитывать все особенности работы алгоритма.

5. Моделирование и оценка эффективности алгоритмов TCP Reno и TCP Vegas

На данный момент существует целый ряд реализаций методов управления перегрузками в протоколе TCP, различающихся в применимости к решениям различных задач. Например, TCP Vegas позволяет учитывать состояние канала связи, TCP Westwood учитывает высокий уровень потерь в каналах связи, TCP Hamilton используется для локальных сетей с высокой пропускной способностью. Наиболее распространенными реализациями протокола являются TCP Reno и TCP Vegas, которые будем использовать для дальнейшего исследования работы противопергрузочных алгоритмов.

5.1 Анализ работы алгоритмов TCP Reno и TCP Vegas

В TCP Reno в нормальной ситуации размер окна меняется циклически. Размер окна увеличивается при каждом цикле до потери пакета. Когда произойдет потеря пакета, TCP Reno уменьшает размер окна до половины текущего размера. Это называется аддитивное увеличение и мультипликативное уменьшение.

TCP Reno имеет два этапа изменения размера окна:

1) фаза медленного старта

2) фаза избежание перегрузки

Когда отправитель получает подтверждение доставки в момент времени t + tA [с] текущее значение размер окна перегрузки cwnd(t) преобразуется в cwnd(t + tA) согласно (1):

Формула 1

где ssth(t) [пакет] – значение порога, при котором TCP переходит от фазы медленного старта в фазу избежания перегрузки.

Когда вследствие таймаута обнаружены потери пакетов, значение cwnd(t) и ssth(t) обновляются следующим образом:

Формула 2

С другой стороны, когда TCP обнаруживает потери пакетов согласно алгоритму быстрой передачи, cwnd(t) и ssth(t) обновляются иначе:

Формула 3

TCP Reno затем переходит к фазе быстрого восстановления. На этом этапе размер окна увеличивается на один пакет, когда получается дублирующие подтверждение. С другой стороны, cwnd(t) равна ssth(t) при поступлении подтверждения на пакет, который был направлен снова.

В случае таймаута cwnd(t) и ssth(t) принимают вид (2).

Как можно легко увидеть, механизм избежания перегрузок, принятый в TCP Reno, вызывает периодические колебания через постоянное обновление размера окна. Скорость, с которой каждое соединение обновляет размер окна зависит от цикла задержки соединения. Итак соединения с коротким задержки может обновить размер окна быстрее, чем соединение с большим временем задержки и тем самым несправедливо украсть долю пропускной способности [4].

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

Формула 4

где Expected – ожидаемая скорость, Actual – фактическая скорость, BaseRTT – минимальное значение RTT при первом подключении.

Детали алгоритма:

1. Источник вычисляет ожидаемую скорость потока по формуле

Формула 5

где CWND – текущий размер окна.

2. Источник оценивает текущую скорость потока с помощью фактического RTT:

Формула 6

де RTT – время прохождения сигнала туда и обратно.

Источник, используя ожидаемую и фактическую скорость потока вычисляет оценку отставания в очереди по формуле (4)

Источник обновляет размер окон следующим образом:

Формула 7

Рис. 1 иллюстрирует поведение TCP Vegas. Рассмотрим простую сеть с одним подключением и одним каналом емкостью. Пусть BaseRTT быть задержка минимального прохождения сигнала туда и обратно. Пропускная способность этого соединения является window/(BaseRTT) когда window < C*BaseRTT.

Рисунок 1 – Управление размером окна TCP Vegas [2]

Рисунок 1 – Управление размером окна TCP Vegas

На рис. 1, w соответствует размеру окна, где window = C*BaseRTT. Когда window>w, начинает образовываться очередь и (Expected - Actual)>0. TCP Vegas увеличивает размер окна при следующем прохождении сигнала, если window <(w + а). TCP Vegas уменьшает размер окна , если window> (w + b). В противном случае, он оставляет размера окна без изменения.

На рис. 1, Diff оценивает размер очереди. TCP Vegas пытается держать приняты а пакеты, но не более, чем b пакетов в очереди. Причиной этого является TCP Vegas попытается выявить и использовать дополнительную пропускную способность, когда она становится доступна без перегрузок в сети. Таким образом, когда есть только одно подключение, размер окна TCP Vegas сходится к точке, лежащей между w + а и w + b.

Обратим внимание, что этот механизм принципиально отличается от того, что используются TCP Reno. TCP Reno всегда обновляет размер окна, чтобы гарантировать полной утилизации пропускной способности, что ведет к постоянной потере пакетов, тогда как TCP Vegas вызывает каких-либо колебания в размере окна после того, как он сходится к точка равновесия [4].

5.2 Математическое описание гидродинамической модели потока для алгоритмов TCP Reno и TCP Vegas

Расчет изменения размера окна и длины очереди выполняется с помощью гидродинамической модели потока. Для каждого алгоритма разрабатывается своя гидродинамическая модель, учитывающая конкретные особенности данного алгоритма. В данном случае используется алгоритмы TCP Reno и TCP Vegas.

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

Формули 8-10

где W(t) обозначает средний размер окна TCP [пакеты], Q(t) – средняя длина очереди [пакеты], R(t) – RTT [секунды], С – пропускная способность канала [пакет/с], N(t) – количество TCP сессий, p(t) – вероятностное функция маркировки пакета, G(x) – нелинейная функция, описывающая изменение размера окна.

Функция G(x) описывается выражением:

Формула 11

Дифференциальные уравнения (8) и (9) описывают динамическое управление окна TCP. Первый элемент 1/Ri в (8) описывает аддитивное увеличение фазы, второй элемент W(t)/2 – мультипликативное уменьшение фазы (в том числе вероятностная функция маркировки пакета). Элемент G(a-Diff) в уравнении (9) описывает увеличение размера окна на 1, а второй элемент G(Diff-b) – уменьшение размера окна на 1.

Уравнение (10) описывает длину очереди узким местом, как разницу между скоростью прибытия пакета NW/R и пропускной способностью С, предполагая, что там нет внутренней динамики в узком месте (грубо говоря, простых интеграторов).

С помощью гидродинамической модели потока активное управление очередь можно интерпретировать как обратную связь проблемы контроля, где действие контроля состоит из маркировки пакетов (с вероятностью p) в зависимости от длины измеренной очереди Q [6].

Для лучшего понимания принципа модели гидродинамического потока представим уравнения (8) и (10) схемой, которая приведена на рис. 2

Рисунок 2 - Схема режима управляння потоком во избежание перегрузки в узком месте для TCP Reno[2]

Рисунок 2 – Схема режима управляння потоком во избежание перегрузки в узком месте для TCP Reno

Принцип гидродинамической модели потока для TCP Vegas приведены на рис. 3.

Рисунок 3 - Схема режима управляння потоком во избежание перегрузки в узком месте для TCP Vegas

Рисунок 3 – Схема режима управляння потоком во избежание перегрузки в узком месте для TCP Vegas

5.3 Метрики оценки работы противоперегрузочных алгоритмов

Для оценки качества работы противоперегрузочных алгоритмов транспортного уровня стека ТСР/ІР наиболее часто используют следующие метрики:

5.4 Моделирование работы алгоритмов TCP Reno и TCP Vegas и анализ полученных результатов

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

На рис.4 приведена топология такой сети. С помощью s1, s2, ..., sN — обозначены отправители трафика, r1, r2, ..., rN — получатели, R — маршрутизаторы канала. Узкое место приводит к тому, что пропускная способность всей сети ограничена одним или несколькими компонентами, которые называются критическими элементами. В нашем случае, критическими элементами являются маршрутизаторы канала.

Рисунок 4 - Топология сети с узким местом

Рисунок 4 – Топология сети с узким местом

(анимация: 7 кадров, задержка между кадрами 1 с, количество циклов повторения — бесконечное, размер 145 Кбайт, создана при помощи gifovina.ru)

Для моделирования используем пакет прикладных программ MATLAB.

Входные параметры моделирования: RTT R = 0,1 с, максимальная длина очереди Qmax = 200 пакетов, количество отправителей s меняется динамически.

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

Рисунок 5 - График зависимости размера окна W (t)

Рисунок 5 – График зависимости размера окна W(t)

Рисунок 6 - График зависимости длины очереди Q (t)

Рисунок 6 — График зависимости длины очереди Q(t)

Проанализировав графики, приведенные на рис.5 – 6, можно отметить, что во первых, средний размер окна TCP Vegas менее в TCP Reno, но за счет меньшего колебания, TCP Vegas передает большее количество данных, во-вторых, среднее значение очереди при использовании алгоритма TCP Vegas меньше, чем при использовании TCP Reno, т.к. TCP Vegas обеспечивает больший объем переданных данных.

Для расчета справедливости распределения пропускной способности получим следующее выражение

Формула 3
Формула 4

Расчет индекса справедливости для количества потерянных пакетов

Формула 5
Формула 6

где vli – количество потерянных пакетов для і-го пользователя.

На основе полученных результатов можно сделать вывод, что при использовании TCP Reno распределение пропускной способности между пользователями более неравномерное, чем при использовании TCP Vegas. Вследствие такого распределения пропускной способности алгоритмом TCP Reno возникает большее количество потерь пакетов, чемв канале связи с использованием TCP Vegas. Также стоит отметить, что количество переданных данных в случае использования алгоритма TCP Vegas больше, чем в случае использования алгоритма TCP Reno. Данное явление можно объяснить тем, что при использовании TCP Vegas наблюдается меньшее колебание размера окна, чем при использовании TCP Reno.

Выводы

Моделирование работы алгоритмов протоколов TCP Reno и TCP Vegas показало что двухфазная работа первого алгоритма приводит к значительным колебаниям нагрузки на сеть и большему уровню потерь, чем у алгоритма TCP Vegas. За счет реализации более сложной схемы управления пропускной способностью в TCP Vegas, достигнуто уменьшение уровня колебаний полезной нагрузки на сеть и уменьшение потерь.

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

Проведенное моделирование показывает, что алгоритм TCP Vegas более эффективно использует пропускную способность канала связи, чем TCP Reno за счет меньшего колебания размера окна.

Примечание

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

Перечень ссылок

  1. Кучерявый Е.А. Управление трафиком и качество обслуживания в сети Интернет / Кучерявый Е.А. – СПб.: Наука и техника, 2004. – 336 с.
  2. Джамалипур А. Беспроводной мобильный Интернет. Архитектура, протоколы и сервисы/Джамалипур А. ; [пер.с англ. Ш. Салиев, В. Орлов] – М., Техносфера, 2009 – 496 с.
  3. Fall K. Simulation based comparisons of Tahoe, Reno and SACK TCP / K. Fall , S. Floyd – Computer Communications Review, , July 1996. —26(3):5Режим доступу до статті21.
  4. Analysis and comparison of TCP Reno and Vegas [Электронный ресурс] /Jeonghoon Mo, Richard J. La, Venkat Anantharam, Jean Walrand//INFOCOM – 1999 – Режим доступа: http://www.eecs.berkeley.edu/~ananth/1999-2001/Richard/MoLaInfocom1999.pdf
  5. Bonald Thomas Comparison of TCP Reno and TCP Vegasvia Fluid Approximation [Электронный ресурс]/Bonald Thomas// RR3563, Unite de recherche INRIA Sophia Antipolis Cedex (France) – 1998 – 34 pages, Режим доступа: netlab.caltech.edu/FAST/references/bonald_comparison.pdf
  6. A control theoretic analysis of RED [Электронный ресурс] / C.V. Hollot, Vishal Misra, Don Towsley, Wei-Bo Gong//INFOCOM — – 2001 – Режим доступа: ftp://gaia.cs.umass.edu/pub/MisraInfocom01-RED-Control.pdf
  7. Jacobson V. Congestion Avoidance and Control/ V. Jacobson – Proceedings, SIGCOMM '88, Computer Communication Review, August 1988; reprinted in Computer Communication Review – January 1995.
  8. Jacobson V. Modified TCP Congestion Avoidance Algorithm/ V. Jacobson - End2 end-interest mailing list, 20 – April 1990.
  9. Srikant, R. The Mathematics of Internet Congestion Control (Systems and Control: Foundations and Applications)/ Rayadurgam Srikant – Birkhauser Boston, 2004.
  10. Батыр С.С. Построение модели сети передачи данных для исследований технологии AQM/Батыр С.С., Хорхордин А.В. // Сборник научных трудов ДонИЖТ Выпуск:28 . – Донецк, 2011 с.108-116
  11. Jain R. A Quantitative Measure of fairness and discrimination for resource allocation in systems/ R. Jain ,D.M. Chiu ,W. Hawe – DEC TR-301, Littleton, MA: Digital Equipment Corporation, 1984.
  12. Митчел Брэдли Пропускная способность и задержка [Электронный ресурс]/[перевод с англ. Дениса Матвеева]//Нестор – 2002. – №12 – Режим доступа: http://www.nestor.minsk.by/sr/2002/12/2122201.html
  13. Семенов Ю.А. Протокол TCP [Электронный ресурс]// Режим доступа: http://book.itep.ru/4/44/tcp_443.htm

вернуться в начало
страницы