План-конспект урока по теме Методы и алгоритмы управления перегрузками

Этапы урока

Содержание этапов урока

1. Организационный момент.

Цели для преподавателя:

- создать условия для возникновения у обучающихся внутренней потребности включения в учебную деятельность;

- способствовать повышению мотивации учения.

Цели для обучающихся:

- включиться в учебную деятельность;

- подготовиться к восприятию нового учебного материала.

Цели этапа занятия достигаются посредством:

-объявления темы занятия и постановки общих целей;

- разъяснения роли изучаемого содержания в процессе формирования конкретных общих и профессиональных компетенций;

- раскрытия значения изучаемого содержания для будущей профессиональной деятельности;

1. Вводный инструктаж

1.1. Проверка наличия обучающихся. Повторение техники безопасности в кабинете информатики.

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

1.2. Целевая установка на урок.

Сегодня у нас новая тема «Методы и алгоритмы управления перегрузками: как алгоритмы с разрешением перегрузок, так и алгоритмы предотвращения перегрузок и управления потоком», запишите тему занятия в тетрадях.

Обучающиеся записывают тему занятия.

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

2. Изучение нового учебного материала (способов действий).

Цели для преподавателя:

- обеспечить понимание планируемого результата деятельности, основных путей его достижения;

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

Цели для обучающихся:

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

- рассмотреть алгоритмы с разрешением перегрузок

- рассмотреть алгоритмы предотвращения перегрузок и управления потоком

Цели этапа занятия достигаются посредством:

- обеспечения понимания планируемого результата деятельности, основных путей его достижения;

- определения критериев, позволяющих обучающимся самостоятельно определять степень достижения запланированного результата;

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

2. Теоретическая часть.

Когда в транспортной среде находится в одно и тоже время слишком много пакетов, ее производительность начинает падать. Когда число пакетов, отправляемых абонентскими машинами в сеть, пропорционально возможностям сети, то число посланных пакетов пропорционально числу доставленных пакетов. Однако если число пакетов, поступающих в сеть, становится слишком большим, они начинают пропадать. При перегрузке сети может случиться, что доставка пакетов практически прекратится.
Перегрузка может возникнуть в силу нескольких причин. Например, если сразу несколько потоков, поступающих по нескольким входным линиям, устремятся на одну и ту же выходную линию. Очередь на этой линии может расти бесконечно, и пакеты начнут посылаться повторно, так как они слишком долго будут находиться в очереди. Если буфер маршрутизатора переполнится, то пакеты начнут теряться. Увеличение памяти в этом случае вряд ли исправит положение. Пакеты долго будут находиться в памяти, и отправители начнут их дублировать.
Перегрузки могут случаться и из-за недостаточной скорости процессора. Если процессор будет не в состоянии справиться своевременно с рутинными задачами (размещения пакета в буфере, корректировка таблиц и т.п.), то даже при наличии линий с достаточной пропускной способностью очередь будет расти. Аналогичная картина может случиться при быстром процессоре, но медленном канале и наоборот. Таким образом, источник проблемы - несбалансированность производительности компонентов системы.
Перегрузки имеют тенденцию к самостоятельному росту и ухудшению ситуации. Если у маршрутизатора не хватает памяти буфера, то он начинает сбрасывать пакеты. Отправитель, не получая пакеты, начинает их повторять снова и снова, усугубляя положения получателя.
Надо различать управление перегрузками сети и управление потоком. Перегрузка - это глобальная проблема в сети. Управление перегрузками - это такая организация потоков в транспортной среде, при которой потоки соответствуют пропускной способности подсети и не превышают ее. Это глобальная проблема в сети, затрагивающая поведение всех хостов и всех маршрутизаторов.
Управление потоком возникает между парой взаимодействующих машин. Это локальная проблема, касающаяся двух взаимодействующих машин. Ее решение гарантирует, что быстрый отправитель сообщений не «завалит» нерасторопного получателя. Здесь яркими примерами могут быть: один быстрый компьютер передает файл в 1 Гб более медленному компьютеру через сеть с пропускной способностью 1 Тбит/сек. со скоростью 1 Гбит/сек. Ясно, что здесь не будет перегрузки, хотя быстрый компьютер может создать такой поток пакетов, что он захлестнет медленный. В тоже время, если в сети с линиями на 1 Мбит/сек. и 1000 компьютеров хотя бы половина машин начнет передавать файлы со скоростью 100 Кбит/сек. другой половине, то ясно, что перегрузки не избежать.
Часто управление перегрузкой и управление потоком путают из-за того, что и там и там применяют одинаковые приемы, например, направляют источникам специальные пакеты, тормозящие нарастание потоков.
Основные принципы управления перегрузками.

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

• Наблюдение за системой для определения, где и когда началась перегрузка

• Передача данных туда, где будут предприняты надлежащие меры

• Перестройка функционирования системы для устранения проблемы

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

• процент пакетов, сброшенных из-за нехватки памяти в буферах

• средняя длина очередей в системе

• число пакетов, для которых наступил time_out и для которых были сделаны повторные передачи

• средняя задержка пакета при доставке и среднее отклонение задержки при доставке пакета

Следующий шаг при использовании обратной связи - передать информацию о перегрузке туда, где что-то может быть сделано, чтобы исправить положение. Например, маршрутизатор, обнаруживший перегрузку, может направить сообщение о перегрузке всем источникам сообщений. Ясно, что это увеличит нагрузку в сети, причем именно в тот момент, когда это менее всего желательно. Однако есть и другие возможности. Например, в каждом пакете зарезервировать специальный бит перегрузки, и если какой-то маршрутизатор обнаружил перегрузку, то он устанавливает этот бит, тем самым сообщая другим о ней (вспомним структуру кадра во Frame Relay).
Другое решение напоминает прием, используемый некоторыми радиостанциями: направлять несколько автомашин по дорогам, чтобы обнаруживать пробки, а затем сообщать о них по радиоканалам, предупреждая другие машины, призывая их пользоваться объездными путями. По аналогии с этим решением в сети рассылаются специальные пробные пакеты, которые проверяют нагрузку, и если где-то обнаружена перегрузка, то о ней сообщается всем и происходит перенаправление пакетов так, чтобы обогнуть перегруженные участки.
Алгоритмы управления перегрузками подразделяются, как мы уже сказали, на решения с открытым и решения с закрытым контуром. Решения с открытым контуром, в свою очередь, делятся на две группы: воздействующие на источники и воздействующие на получателей. Решения с закрытым контуром - с явной обратной связью и неявной обратной связью. Явная обратная связь предполагает, что источнику посылается специальный пакет, который информирует его о перегрузке. Неявная обратная связь основана на том, что источник сам определяет факт перегрузки на основе своих локальных наблюдений за трафиком, например, по величине задержки на поступление уведомления о доставке пакета.
Появление перегрузки означает, что нагрузка превысила, возможно временно, ресурсы системы или некоторой ее части. Есть два выхода из этого положения: увеличить ресурсы и сократить нагрузку. Увеличить ресурсы чаще всего невозможно. Тогда остается только сокращение нагрузки. Для этого есть несколько способов: отказать некоторым пользователям в сервисе, ухудшить сервис всем или некоторым пользователям, заставить пользователей планировать свои потоки определенным образом. Методы, предотвращающие перегрузки.

Рассмотрение методов, предотвращающих перегрузки, начнем с методов для систем с открытым контуром. Эти методы ориентированы на минимизацию перегрузок при первых признаках их проявлений, а не на борьбу с перегрузками, когда они уже случились.
Таблица 5-22. Факторы, влияющие на перегрузки

Начнем с канального уровня. Вызвать перегрузку может повторная пересылка кадров. Если у источника сообщений часто возникает time_out и он начинает повторно передавать пакет, то тем самым он лишь усугубляет положение. Близко к этому фактору стоит нарушение порядка следования пакетов при передаче. Если получатель часто сбрасывает пакеты, поступившие не в надлежащем порядке от источника, то их повторная передача будет также усугублять перегрузку.
Организация рассылки уведомлений также влияет на перегрузку. Если уведомление происходит немедленно и специальными пакетами, то это увеличивает трафик и следовательно может привести к перегрузкам. Если для уведомления используются пакеты с сообщениями (прием piggybacking), то возможны time_out из-за отсутствия уведомлений вовремя и, как следствие, повторные пересылки пакетов, что может привести к перегрузкам. В то же время жесткая схема управления потоком (небольшое окно) сдерживает нарастание трафика и предотвращает появление перегрузок.
На сетевом уровне выбор схемы работы - с виртуальными соединениями или дейтаграммами - влияет на появление перегрузок. На этом уровне большинство методов борьбы с перегрузками ориентированы на виртуальные соединения. Методы управления очередями, организация очередей: одна общая на входе или одна общая на выходе; по одной на каждую входную линию или на каждую выходную; по одной очереди на каждую входную и выходную - все это влияет на появление перегрузок. Выбор метода сброса пакетов также влияет на перегрузки.
Правильная маршрутизация, равномерно использующая каналы в транспортной среде, позволяет избежать перегрузки. Методы, регулирующие время жизни пакета в сети, также влияют на образование перегрузок. Если пакет долго блуждает в сети, прежде чем будет принято решение о его сбросе, то это плохо, так как увеличивает трафик и может привести к перегрузке. Если поторопиться, то преждевременный сброс пакета может привести к повторным передачам, что опять-таки увеличит нагрузку.
На транспортном уровне возникают те же самые проблемы, что и на канальном, однако определить величину time_out намного сложнее. Дело в том, что оценить время передачи через СПД много сложнее, чем время передачи по каналу «точка-точка» между двумя маршрутизаторами. Если оно будет слишком большим, то это снизит вероятность перегрузки, но повлияет на производительность из-за длительного ожидания поступления пакета. Если сделать его коротким, то появятся лишние пакеты.
Формирование трафика.

Одной из основных причин перегрузки является нерегулярный, взрывообразный трафик в сети. Если бы он был равномерным, то перегрузок можно было бы избежать. Один из методов с открытым контуром, часто используемым особенно в АТМ-сетях, - метод формирования трафика (shaping - т.е. придание формы), когда скорость передачи пакетов контролируется и регулируется.
Формирование трафика регулирует среднюю скорость передачи данных так, чтобы сделать его по возможности гладким. Следует обратить внимание, что протокол скользящего окна, который мы рассматривали при изучении канального уровня, лишь регулирует объем данных, передаваемых за один раз, но не скорость передачи. Здесь же речь идет именно о скорости передачи. Когда виртуальное соединение устанавливается, то пользователь договаривается с транспортной средой о форме трафика. Если пользователь обеспечивает договоренную форму трафика, то транспортная среда обеспечивает ему доставку трафика с определенной скоростью. Для таких приложений, как передача видео- и аудиоданных в реальном времени, это очень важно. Здесь уместно вспомнить организацию работы СПД Frame Relay.
Когда пользователь и транспортная среда договариваются о форме трафика, то они приходят к соглашению не только о форме трафика, но также и о том, что произойдет, если эта форма будет нарушена пользователем. Это соглашение называется соглашением о трафике. Использование техники формирования трафика и соглашения о трафике легче всего реализовать при использовании виртуальных соединений, чем в случае дейтаграмм. В случае дейтаграмм эти идеи могут быть применены к соединениям на транспортном уровне.

В качестве регулятора скорости поступления пакетов можно использовать системные часы. В этом случае устанавливается предел числа пакетов, которые процесс может направить в сеть за один промежуток времени. Этот прием дает хорошие результаты, когда пакеты имеют фиксированную длину, как в АТМ. В случае пакетов переменной длины это соглашение ограничивает количество байтов, направляемых в сеть.
Алгоритм текущего ведра позволяет сгладить трафик, убрать нерегулярность. Однако в целом ряде приложений бывает полезно разрешить, при всплеске трафика и наличии необходимых ресурсов, ускорить на некоторое время передачу пакетов в сеть. Один из алгоритмов, позволяющих это сделать, - алгоритм ведра с маркерами.
Другое отличие алгоритма ведра с маркером - при переполнении буфера хосту будет временно запрещено передавать пакеты. Здесь опять существуют разные варианты в зависимости от длины пакетов, правила работы со счетчиком маркеров и т.д. Для реализации алгоритма ведра с маркерами нужна лишь переменная, значение которой увеличивается каждые ΔТ сек. и уменьшается с каждым посланным пакетом. В случае пакетов переменной длины значение этой переменной увеличивается на k байтов каждые ΔТ сек. и уменьшается на длину каждого посланного пакета. Нетрудно рассчитать длительность всплеска при передаче на основе уравнения
C + ρ S = MS
где С – объем буфера, S – длительность всплеска, ρ – скорость поступления маркера, М – максимальная скорость «вытекания» данных.
Таким образом, S = C/(M - ρ).
Спецификация потока.

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

Прием, который широко используется, чтобы сдержать уже возникшую перегрузку и не дать положению ухудшиться - это контроль на входе. Идея очень проста - если обнаружена перегрузка, то все, что способствует увеличению трафика, запрещено. Прежде всего, запрещается создание новых виртуальных соединений. Таким образом, запрещается создание новых соединений на транспортном уровне. Этот метод хотя и грубоват, но прост в реализации и хорошо апробирован в телефонных сетях.
Другой подход разрешает установку новых виртуальных соединений, но только при наличии не перегруженных маршрутов, т.е. таких маршрутов, которые не пересекаются с перегруженными участками, даже если такие маршруты далеко не оптимальны. Рисунок 5-27 иллюстрирует этот подход.
Рисунок 5-27. (а) Участок сети с перегрузкой; (b) Измененный участок сети без перегрузки с виртуальным каналом АВ
Третий подход уже упоминался: хост и транспортная среда договариваются перед установкой виртуального соединения о форме трафика, объеме передаваемых данных, качестве сервиса и т.п. После этого транспортная среда резервирует необходимое количество ресурсов, необходимых ей для выполнения этих соглашений. Это резервирование может происходить постоянно, а может быть сделано только при возникновении перегрузок. Плата за резервирование - неоптимальное использование пропускной способности каналов.
Подавляющие пакеты.

Теперь рассмотрим приемы, используемые как в средах с виртуальными каналами, так и в средах с дейтаграммами. Каждый маршрутизатор может контролировать степень загрузки своих выходных линий и другие ресурсы. Например, он может периодически вычислять степень загруженности своих выходных линий. Всякий раз, когда степень загруженности при очередном вычислении оказывается выше некоторого порога, эта линия переводится в состояние предупреждения. Каждый пакет, маршрутизируемый через такую линию, вызывает генерацию подавляющего пакета, направляемого отправителю маршрутизируемого пакета. этом в пакете отправителя проставляется определенный разряд, предотвращающий генерацию подавляющих пакетов другими маршрутизаторами в дальнейшем.
Когда отправитель получает подавляющий пакет, он сокращает интенсивность своего трафика на определенную величину. Поскольку пакеты, направляемые одному и тому же получателю, могут маршрутизироваться по-разному, то отправитель вправе ожидать несколько подавляющих пакетов. В течение определенного времени отправитель будет игнорировать подавляющие пакеты, поступающие с направления получателя. По истечении этого периода времени отправитель ожидает появления подавляющих пакетов в течение следующего интервала. Если появился хоть один подавляющий пакет, то линия перегружена и отправитель ждет. в течение очередного интервала не поступило ни одного подавляющего пакета, то отправитель может увеличить интенсивность трафика.
Существует много вариантов этого алгоритма. Так, например, можно использовать не только загруженность линии, но и длину очереди, заполненность буфера и параметры спецификации трафика.
У методов на основе подавляющих пакетов есть один недостаток. Если есть несколько отправителей, работающих через одну и ту же выходную линию, то при определенных условиях маршрутизатор всем им пошлет подавляющие пакеты. Однако, так как отправители независимы, то один, например, сократит трафик значительно, тогда как другие лишь незначительно. Это приведет к несправедливому использованию пропускной способности канала между ними.
Для предотвращения такой ситуации был предложен алгоритм справедливого чередования. Суть его состоит в том, что для каждого отправителя у выходной линии строится своя очередь. Отправка пакетов из этих очередей происходит по кругу. Поэтому, если кто-то из отправителей незначительно сократит трафик, то это лишь увеличит скорость роста его очереди.
И у этого алгоритма есть недостаток: если один отправитель использует длинные пакеты, а другой - короткие, то последний получит меньшую долю пропускной способности линии. Для борьбы с этой несправедливостью в алгоритм обслуживания очередей вносят модификацию: пакеты из очередей передаются побайтно, а не весь пакет сразу.
Другие модификации алгоритма чередования связаны с установкой приоритетов между очередями, что дает большую гибкость в обслуживании отправителей. Так, если есть очереди для сервера и для клиента, то естественно обслуживать очередь сервера быстрее.
Представленные здесь алгоритмы с подавляющими пакетами плохо работают в высокоскоростных сетях и на больших расстояниях. Дело в том, что пока подавляющий пакет дойдет до отправителя, пройдет много времени и отправитель успеет «напихать» в сеть много пакетов. Для исправления этой ситуации была предложена его модификация – алгоритм с подавлением по скачкам. Суть его в том, что как только обнаружится перегрузка на выходной линии и маршрутизатор отправит подавляющий пакет, то ближайший маршрутизатор, получивший этот подавляющий пакет, сократит трафик к маршрутизатору, пославшему подавляющий пакет. И так скачок за скачком трафик будет быстро падать. Естественно, этот прием увеличит нагрузку на буфера маршрутизаторов, сокращающих трафик, но обеспечит быструю реакцию на возникающую перегрузку. ^

Сброс нагрузки.

Когда ни один из упомянутых выше приемов не срабатывает, маршрутизатор может применить «тяжелую артиллерию» – сброс нагрузки. Было бы слишком примитивно предполагать, что маршрутизатор, при возникновении перегрузки просто начинает сбрасывать пакеты. Идея метода и его название пришли из области передачи электроэнергии. Там при возникновении перегрузок в сети, начинают отключать отдельные группы потребителей, чтобы сохранить работоспособность системы.
Маршрутизатор может сбрасывать пакеты, исходя из информации о приложении, пославшем эти пакеты. Если, например, передается файл, то старые пакеты, т.е. расположенные ближе к концу файла, сбрасывать лучше, поскольку приложение может потребовать перепослать все пакеты, начиная с пропущенного пакета. В этом случае, чем старее пакет, тем меньше придется перепосылать. Есть приложения, для которых все наоборот. Лучше сбрасывать новые пакеты, т.е. ближе к началу передачи, чем старые.
В общем случае подход на основе сброса нагрузки предполагает определенное взаимодействие между приложением и маршрутизатором. Например, при передаче изображений в целях компрессии сначала посылают всю картинку, а потом лишь ее изменения. Ясно, что потеря одного из изменений лишь ухудшит изображение на некоторое время, в то время, как потеря картинки будет означать потерю изображения вовсе. Для обеспечения такого взаимодействия с приложением вводят приоритеты среди пакетов. Это позволяет маршрутизатору минимизировать потери для приложения, когда маршрутизатор вынужден сбрасывать пакеты.
Для того, чтобы приложение не злоупотребляло приоритетными пакетами, можно увязать приоритет пакетов с величиной оплаты за трафик. Чем больше приоритетных пакетов, тем выше стоимость передачи. Приоритеты можно использовать также в целях формирования трафика. Например, при использовании алгоритма ведра с маркерами, если пакет пришел, а маркеров нет, можно применить прием, когда пакет все же будет передан, но низким приоритетом.
Приоритеты используются, например, в протоколах Frame Relay. Пока величина трафика находится в заранее оговоренных пределах, все пакеты идут с определенным приоритетом. При пиковых нагрузках, превосходящих номинальную величину, приоритеты пакетов начинают падать в зависимости от времени. Если увеличение размера трафика продолжается недопустимо долго, то вскоре приоритеты пакетов достигнут минимума, и при первых же признаках перегрузки их начнут сбрасывать.сУправление перегрузками при групповой передаче.

Все алгоритмы управления перегрузками, которые мы до сих пор рассматривали, относились к случаю, когда был один источник и один получатель. В этом разделе мы рассмотрим случай управления нагрузкой при групповой передаче, т.е. когда есть несколько источников и несколько получателей. Примером могут служить системы кабельного телевидения. Например, в системе может быть несколько источников телепередач (станций вещания), и зрители могут по желанию переключаться с одной станции на другую. Аналогичная ситуация может иметь место в системе видеоконференций, когда слушатели могут переключаться с одной конференции на другую.
Во многих подобных приложениях группы могут возникать и изменяться по составу динамически. В этих условиях прием, когда источник сообщений резервирует заранее необходимые для передачи ресурсы, не работает эффективно. Источнику сообщений придется при каждом изменении группы генерировать дерево связей. В случае кабельного телевидения, когда группы содержат миллионы зрителей, такой подход не годится.
Одно из возможных решений для подобных случаев было предложено в 1993 году – это RSVP-протокол (Resource reSerVation Protocol – протокол резервирования ресурсов). Он позволяет нескольким отправителям передавать сообщения группам получателей, отдельным получателям переходить из группы в группу, оптимизировать использование пропускной способности каналов, избегая перегрузок.
В простейшей форме этот протокол для групповой маршрутизации использует дерево связей так, как мы уже рассматривали ранее. Каждой группе приписана группа адресов.  При отправке пакета отправитель помещает в него весь список адресов группы. После этого стандартный алгоритм групповой маршрутизации строит дерево связей, покрывающее все адреса группы. Собственно маршрутизация не является частью RSVP.
Чтобы избежать перегрузок, любой получатель в группе шлет надлежащему отправителю резервирующее сообщение. Это сообщение с помощью алгоритма пересылки вдоль обратного пути, рассмотренного в разделе 5.2.9, движется к отправителю и вызывает резервирование необходимой пропускной способности на каждом узле, через который оно проходит. Если при прохождении очередного узла ему не удается зарезервировать необходимую пропускную способность, то получателю направляется отказ в установлении соединения.

4. Задание на дом.

Цели для преподавателя:

- провести анализ и оценку успешности достижения цели урока, перспектив последующей работы;

- мобилизовать обучающихся на рефлексию результатов учебной деятельности;

- поставить цели самостоятельной работы для обучающихся (что должны сделать обучающиеся в ходе выполнения домашнего задания).

Цели для обучающихся:

- уяснить цели и содержание домашнего задания.

Цели этапа урока достигаются посредством:

- достижения открытости обучающихся в осмыслении своих действий и самооценки;

- определения для обучающихся содержания и объема домашнего задания.

4.Заключительная часть. Подведение итогов, выставление отметок.

Сегодня мы с вами: рассмотрели методы и алгоритмы управления перезагрузками и алгоритмы с разрешением перегрузок, рассмотрели алгоритмы предотвращения перегрузок и управления потоком

Задание. К следующему занятию выучите лекцию. Составить инструкционную технологическую карту.