Лекции 2010-го года (1130544), страница 63
Текст из файла (страница 63)
Маршрутизация при групповой передачеЭтот вид передачи используют, когда надо обеспечить взаимодействие группывзаимосвязанных процессов, разбросанных по сети. Такие ситуации часто встречаются враспределенных базах данных. Если группа велика по сравнению с размерами сети, томожно воспользоваться методами вещания. Однако если ее размер мал относительноразмера всей сети, то такой подход будет неэкономичен. Кроме того, если рассылаемая вгруппе информация конфиденциальная, то алгоритмы вещания не подходят.
Этот видмаршрутизации называют групповой маршрутизацией.В случае обмена информации в группе, кроме алгоритма групповой маршрутизации,нужны алгоритмы управления группой, которые должны обеспечивать средства дляреконфигурации группы: включение новых членов, удаление старых и т.п. Однако этипроблемы не затрагивают алгоритм групповой маршрутизации, поэтому мы их здесьрассматривать не будем.Алгоритм групповой маршрутизации, как правило, основан на дереве связей. Каждыймаршрутизатор в транспортной среде вычисляет дерево связей, охватывающее все другиемаршрутизаторы.
На рисунке 5-20 (а) приведен пример транспортной среды, состоящей издвух групп (их номера указаны у вершин). Некоторые вершины принадлежат как группе1, так и группе 2. На рисунке 5-20 (b) показано дерево связей для самой левой вершины.Когда процесс посылает групповой пакет, первый же маршрутизатор обрезает свое деревосвязей, убирая из него все связи, которые не ведут в вершины, не являющиеся членамигруппы. На рисунке 5-20 (с) показано сокращенное дерево связей для группы 1. Нарисунке 5-20 (d) дано сокращенное дерево связей для группы 2.Рисунок 5-20.
Групповая маршрутизация25Для обрезания дерева связей используются разные алгоритмы. Наиболее простой основанна применении алгоритма маршрутизации на основе состоянии канала. В этом случаекаждый маршрутизатор имеет полную конфигурацию транспортной среды. Сокращениедерева связей начинается от вершин – членов группы и разворачивается в сторону корня,удаляя все маршрутизаторы, которые не ведут к членам группы. Существуют и другиеподходы.Раздел 5.3.
Алгоритмы управления перегрузкамиКогда в транспортной среде находится в одно и тоже время слишком много пакетов, еепроизводительность начинает падать. На рисунке 5-21 показано явление перегрузки.Когда число пакетов, отправляемых абонентскими машинами в сеть, пропорциональновозможностям сети, то число посланных пакетов пропорционально числу доставленныхпакетов.
Однако если число пакетов, поступающих в сеть, становится слишком большим,они начинают пропадать. При перегрузке сети может случиться, что доставка пакетовпрактически прекратится.Рисунок 5-21. Перегрузка26Перегрузка может возникнуть в силу нескольких причин. Например, если сразу несколькопотоков, поступающих по нескольким входным линиям, устремятся на одну и ту жевыходную линию.
Очередь на этой линии может расти бесконечно, и пакеты начнутпосылаться повторно, так как они слишком долго будут находиться в очереди. Если буфермаршрутизатора переполнится, то пакеты начнут теряться. Увеличение памяти в этомслучае вряд ли исправит положение. Пакеты долго будут находиться в памяти, иотправители начнут их дублировать.Перегрузки могут случаться и из-за недостаточной скорости процессора. Если процессорбудет не в состоянии справиться своевременно с рутинными задачами (размещения пакетав буфере, корректировка таблиц и т.п.), то даже при наличии линий с достаточнойпропускной способностью очередь будет расти. Аналогичная картина может случитьсяпри быстром процессоре, но медленном канале и наоборот. Таким образом, источникпроблемы - несбалансированность производительности компонентов системы.Перегрузки имеют тенденцию к самостоятельному росту и ухудшению ситуации.
Если умаршрутизатора не хватает памяти буфера, то он начинает сбрасывать пакеты.Отправитель, не получая пакеты, начинает их повторять снова и снова, усугубляяположения получателя.Надо различать управление перегрузками сети и управление потоком. Перегрузка - этоглобальная проблема в сети. Управление перегрузками - это такая организация потоков втранспортной среде, при которой потоки соответствуют пропускной способности подсетии не превышают ее.
Это глобальная проблема в сети, затрагивающая поведение всеххостов и всех маршрутизаторов.Управление потоком возникает между парой взаимодействующих машин. Это локальнаяпроблема, касающаяся двух взаимодействующих машин. Ее решение гарантирует, чтобыстрый отправитель сообщений не «завалит» нерасторопного получателя. Здесь яркимипримерами могут быть: один быстрый компьютер передает файл в 1 Гб более медленномукомпьютеру через сеть с пропускной способностью 1 Тбит/сек. со скоростью 1 Гбит/сек.Ясно, что здесь не будет перегрузки, хотя быстрый компьютер может создать такой потокпакетов, что он захлестнет медленный. В тоже время, если в сети с линиями на 1Мбит/сек.
и 1000 компьютеров хотя бы половина машин начнет передавать файлы соскоростью 100 Кбит/сек. другой половине, то ясно, что перегрузки не избежать.27Часто управление перегрузкой и управление потоком путают из-за того, что и там и тамприменяют одинаковые приемы, например, направляют источникам специальные пакеты,тормозящие нарастание потоков.5.3.1. Основные принципы управления перегрузкамиВ терминологии теории управления все методы управления перегрузками в сетях можноразбить на две большие группы: с открытым контуром управления и закрытым контуромуправления.
Методы с открытым контуром предполагают, что все продумано ипредусмотрено заранее в конструкции системы, и если нагрузка находится в заданныхпределах, то перегрузки не происходит. Если же нагрузка начинает превышатьопределенные пределы, то заранее известно, когда и где начнется сброс пакетов, в какихточках сети начнется перепланировка ресурсов, и т.п. Главное, что все эти меры будутприниматься вне зависимости от текущего состояния сети.Решения, основанные на закрытом контуре, используют обратную связь. Эти решениявключают три этапа:• Наблюдение за системой для определения, где и когда началась перегрузка• Передача данных туда, где будут предприняты надлежащие меры• Перестройка функционирования системы для устранения проблемыПри наблюдении за системой используются разные метрики для определения перегрузки.Основными среди них являются:• процент пакетов, сброшенных из-за нехватки памяти в буферах• средняя длина очередей в системе• число пакетов, для которых наступил time_out и для которых были сделаныповторные передачи• средняя задержка пакета при доставке и среднее отклонение задержки при доставкепакетаСледующий шаг при использовании обратной связи - передать информацию о перегрузкетуда, где что-то может быть сделано, чтобы исправить положение.
Например,маршрутизатор, обнаруживший перегрузку, может направить сообщение о перегрузкевсем источникам сообщений. Ясно, что это увеличит нагрузку в сети, причем именно в тотмомент, когда это менее всего желательно. Однако есть и другие возможности. Например,в каждом пакете зарезервировать специальный бит перегрузки, и если какой-томаршрутизатор обнаружил перегрузку, то он устанавливает этот бит, тем самым сообщаядругим о ней (вспомним структуру кадра во Frame Relay).Другое решение напоминает прием, используемый некоторыми радиостанциями:направлять несколько автомашин по дорогам, чтобы обнаруживать пробки, а затемсообщать о них по радиоканалам, предупреждая другие машины, призывая ихпользоваться объездными путями.
По аналогии с этим решением в сети рассылаютсяспециальные пробные пакеты, которые проверяют нагрузку, и если где-то обнаруженаперегрузка, то о ней сообщается всем и происходит перенаправление пакетов так, чтобыобогнуть перегруженные участки.Алгоритмы управления перегрузками подразделяются, как мы уже сказали, на решения соткрытым и решения с закрытым контуром. Решения с открытым контуром, в своюочередь, делятся на две группы: воздействующие на источники и воздействующие на28получателей. Решения с закрытым контуром - с явной обратной связью и неявнойобратной связью.
Явная обратная связь предполагает, что источнику посылаетсяспециальный пакет, который информирует его о перегрузке. Неявная обратная связьоснована на том, что источник сам определяет факт перегрузки на основе своихлокальных наблюдений за трафиком, например, по величине задержки на поступлениеуведомления о доставке пакета.Появление перегрузки означает, что нагрузка превысила, возможно временно, ресурсысистемы или некоторой ее части. Есть два выхода из этого положения: увеличить ресурсыи сократить нагрузку. Увеличить ресурсы чаще всего невозможно.
Тогда остается толькосокращение нагрузки. Для этого есть несколько способов: отказать некоторымпользователям в сервисе, ухудшить сервис всем или некоторым пользователям, заставитьпользователей планировать свои потоки определенным образом.5.3.2. Методы, предотвращающие перегрузкиРассмотрение методов, предотвращающих перегрузки, начнем с методов для систем соткрытым контуром. Эти методы ориентированы на минимизацию перегрузок при первыхпризнаках их проявлений, а не на борьбу с перегрузками, когда они уже случились.Основные факторы, влияющие на перегрузки на канальном, сетевом и транспортномуровнях, перечислены в таблице 5-22.Таблица 5-22.
Факторы, влияющие на перегрузкиУровеньФакторыТранспортныйПовторная передачаПорядок передачи битУведомленияУправление потокомЗначение timeoutСетевойВиртуальные каналы vs. дейтаграммы внутри подсетиОчередность пакетов и сервисыСброс пакетаАлгоритм маршрутизацииУправление временем жизни пакетовКанальныйПовторная передачаПорядок передачи битУведомленияУправление потокомНачнем с канального уровня. Вызвать перегрузку может повторная пересылка кадров.Если у источника сообщений часто возникает time_out и он начинает повторно передаватьпакет, то тем самым он лишь усугубляет положение.
Близко к этому фактору стоитнарушение порядка следования пакетов при передаче. Если получатель часто сбрасывает29пакеты, поступившие не в надлежащем порядке от источника, то их повторная передачабудет также усугублять перегрузку.Организация рассылки уведомлений также влияет на перегрузку. Если уведомлениепроисходит немедленно и специальными пакетами, то это увеличивает трафик иследовательно может привести к перегрузкам. Если для уведомления используютсяпакеты с сообщениями (прием piggybacking), то возможны time_out из-за отсутствияуведомлений вовремя и, как следствие, повторные пересылки пакетов, что можетпривести к перегрузкам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
