Р.Л. Смелянский - Компьютерные сети. Том 2. Сети в ЭВМ (1130083), страница 12
Текст из файла (страница 12)
Маршрутизация при вещании В некоторых приложениях возникает потребность пересылки одного и того же сообщения всем машинам, например прогноза погоды, новостей и т.д. Такой режим передачи, как известно, называется вещанием. Есть несколько решений реализации этого режима. Первое решение — источник знает, кому и что надо послать, и генерирует столько сообщений, сколько имеется получателей. Это одно из самых плохих решений. Оно не требует никаких специальных средств, однако весьма затратно. Тратится не только пропускная способность каналов, но и память, так как где-то необходимо хранить весь лист рассылки и экземпляры рассылаемого сообщения.
Второе решение — использование метода лавины. Однако, как мы уже видели, он затратен для каналов типа точка — точка; слишком сильно расходуется пропускная способность. Третье решение — маршрутизация множественной доставки. В этом случае каждый пакет должен иметь либо лист рассылки, либо маршрут рассылки. Лист рассылки содержит лишь адреса получателей, а маршрут рассылки — последовательность маршрутизаторов, через которые должен проследовать пакет. Каждый маршрутизатор, получив такой пакет, отправляет и дублирует его в соответствии с маршрутом рассылки. Четвертое решение — использование дерева захода либо любого другого подходящего дерева связей. Дерево захода позволяет избежать циклов и ненужного дублирования пакетов.
В этом случае каждый маршрутизатор дублирует пакет вдоль линий, соответствующих дереву захода, кроме той линии, по которой пакет пришел. При таком решении очень рационально используется пропускная способность каналов и генерируется абсолютный минимум пакетов при рассылке. Однако у каждого маршрутизатора должны быть деревья захода.
Пятое решение — неявное использование дерева связей. В этом случае, когда пакет поступает, маршрутизатор проверяет, по какой линии он поступил. Если пакет поступил по линии, которая используется для отправления пакетов источнику вещательного пакета, то вещательный пакет дублируется и рассылается по всем линиям, кроме той линии, по которой пакет пришел. Если пакет поступил не по этой линии, то он сбрасывается.
Данный метод реализации вещания называется пересылкой вдоль обратного пути. Рассмотрим пример использования этого метода 1191. На рис. 2.13, а показана топология транспортной среды, на рис. 2.13, б — дерево захода для вершины 1, а на рис. 2.13, в — схема работы этого алгоритма. Сначала в вершине У были сгенерированы, а затем разосланы четыре пакета. Во все четыре вершины (Г, Н, У, М), куда поступили эти пакеты, они пришли с направления, предпочтительного для достижения вершины 1. Из восьми пакетов, сгенериро- 50 '':.
Рис. 2ЛЗ. Транспортная среда (а), дерево захода для вершины з'(б) и дерево, построенное методом пересылки вдоль обратною пути (в) ,::::; ': ванных на следующем этапе, согласно дереву захода только пять ,',, поступили по предпочтительному для 1 направлению. На третьем '- этапе из шести сгенерированных пакетов только три поступили по ;:, .предпочтительному направлению (в с, Р, Ж поступили дубликаты) После пяти этапов сгенерированы 23 пакета, и рассылка прекращается. Достоинствами этого метода являются простота и легкость реализации, а сложность заключается в построении дерева заходов для каждого случая рассылки 2.2.
11. Маршрутизации при групповой передаче Групповая передача используется, когда надо обеспечить взаимо— действие группы взаимосвязанных процессов, разбросанных по сети "~,:'.::,'Такие ситуации часто встречаются в распределенных приложениях, ", "'.'' например при работе с распределенными базами данных.
Если размер -'':!=",: такой группы сравним с размерами сети, то можно использовать методы вешания, олнако при маленьком размере группы такой подход будет неэкономичным. Кроме того, если рассылаемая в группе информация конфиденциальная, то алгоритмы вещания не подходят. Так мы приходим к проблеме групповой маршрутизации В случае обмена информацией в группе кроме алгоритма группо',!,',::; вой маршрутизации необходимы алгоритмы управления группой, ::„:,:,:,. которые должны обеспечивать средства для ее реконфигурации: ;::,' .
включение новых членов, удаление старых и т.п. Однако эти про-::=: блемы не затрагивают алгоритм групповой маршрутизации, поэтому здесь мы их рассматривать не будем Алгоритм групповой маршрутизации, как правило, основывается .:-- на дереве связей, т, е. каждый маршрутизатор в транспортной среде .
'':„: в(ычисляет дерево связей, охватывающее все остальные маршрутиза-'торы. Рис. 2.14. 1рупповая маршрутизация: а — топология ТС; б — дерево связей для групп 1 и 2 узлов; в — дерево связей для группы 1; г — дерево связей для группы 2 На рис. 2.14, а приведен пример транспортной среды, состоящей из двух групп (их номера указаны у вершин), в которой некоторые вершины принадлежат как группе 1, так и группе 2. На рис. 2.14, б показано дерево связей для самой левой вершины.
Когда процесс посылает групповой пакет, первый же маршрутизатор редуцирует в своем дереве все связи, которые не ведут в вершины, не являющиеся членами группы. На рис. 2.14, в показано редуцированное дерево связей для группы 1, а на рис. 2.14, е — для группы 2. Для редукции дерева связей используются разные алгоритмы, наиболее простой из которых основывается на применении алгоритма маршрутизации по состоянию канала. В этом случае каждый маршрутизатор имеет полную конфигурацию транспортной среды.
Редукция дерева связей начинается от вершин — членов группы — и разворачивается в сторону корня, удаляя все маршрутизаторы, которые не ведут к членам группы. Следует отметить, что такая редукция требует дополнительных накладных расходов на обмен служебной информацией между маршрутизаторами в транспортной среде. Подробнее алгоритмы маршрутизации рассмотрены в 111, 28].
2.3. Алгоритмы управления перегрузками 2.3. т. Общие сведения Когда в транспортной среде находится в одно и то же время слишком много пакетов, ее производительность начинает падать. Когда 52 З гг,число пакетов, отправляемых абонентскими машинами в сеть, пропорционально пропускной способности сети, то число посланных пакетов пропорционально числу доставленных пакетов. Когда число отправляемых пакетов начинает расти, а число доставленных пакетов .начинает непропорционально снижаться, происходит перегрузка .:., транспортной среды, при которой доставка пакетов может практически прекратиться.
Перегрузка может возникнуть в силу нескольких причин. Например, если сразу несколько потоков данных, поступающих по несколь;.'-, ким входным линиям, устремятся на одну и ту же выходную линию. ОчеРедь на этой линии может расти бесконечно, и пакеты начнут ' ..посылать повторно, так как они слишком долго будут находиться в . "',,- .. очереди. Если буфер маршрутизатора переполнится, то маршрутиза.: тор начнет терять пакеты.
Увеличение памяти в этом случае вряд ли ..исправит положение. Пакеты долго будут находиться в памяти, и от.правители начнут их дублировать Перегрузки могут возникнуть и из-за недостаточной скорости .процессора. Если процессор будет не в состоянии справиться своевременно с рутинными задачами (с размещением пакета в буфере, .корректировкой таблиц и т. п.), то даже при наличии линий с доста:;,-': -:точной пропускной способностью очередь будет расти. Аналогичная .;:,.;,картина может случиться при быстром процессоре, но медленном канале, и наоборот Таким образом, причина возникновения перегрузок — несбалап- .~;,: сированность производительности компопентов транспортной среды Перегрузки имеют тенденцию к усилению, т. е.
увеличению числа «потерянных» пакетов и ухудшению ситуации. Если у маршрутиза„':;.,!-" тора не хватает памяти буфера, то он начинает сбрасывать пакеты, а отправитель начинает посылать их снова и снова, увеличивая загруженность транспортной среды Следует различать управление перегрузками и управление пото:„::-:,' ком. Перегрузка — это глобальная проблема в сети. Управление пере!':: 'грузками — это процесс регулирования потоков данных в транспорт;,:;,','ной среде, при котором эти потоки пе превышают ее пропускной способности.
Эта глобальная проблема затрагивает поведение всех абонентских машин и всех маршрутизаторов в сети. Управление потоком возникает между парой взаимодействующих ..:-::„', машин. Это локальная проблема, касающаяся только двух взаимодействующих машин. Ее решение гарантирует, что быстрый отправитель сообщений не «завалит» нерасторопного получателя. Напри.,;.
' мер, один быстрый компьютер передает со скоростью! Гбит/с файл ;, '. ' размером 1 Гбит более медленному компьютеру через СЛД с пропускной способностью 1 Тбит/с. Ясно, что здесь не будет перегрузки, '.,-.:. хотя быстрый компьютер может создать такой поток пакетов, что он захлестнет медленный компьютер. В то же время если сеть, в СПД которой пропускная способность любой линии не превышает 1 Мбит!с, будет содержать 1 000 компьютеров и хотя бы половина из них начнет передавать файлы со скоростью 100 Кбит(с другой половине, то ясно, что при неудачной топологии СПД перегрузки не избежать.
с1асто управление перегрузкой и управление потоком путают из-за того, что и там, и там применяются одинаковые приемы, например направление источникам специальных пакетов, подавляющих нарастание потоков. 2.3.2. Основные принципы управления перегрузками В терминологии теории управления все метолы управления перегрузками в сетях можно разбить на две большие группы: с открытым контуром управления и с замкнутым контуром управления.
Методы с открытым контуром управления предполагают, что все продумано и предусмотрено заранее в конструкции системы, и если нагрузка находится в заданных пределах, то перегрузки не происходит. Если же нагрузка начинает превышать определенные пределы, то заранее известно, когда и где начнется сброс пакетов, в каких точках сети начнется перепланировка ресурсов и т.и. Главное, что все это будет происходить вне зависимости от специфики текущего состояния сети. Методы управления с замкнутым контуром основаны на использовании обратной связи и включают в себя следующие три этапа: ° наблюдение за сетью для определения, где и когда началась перегрузка; ° передача данных туда, где требуется предпринять надлежащие меры; ° перестройка функционирования сети для устранения проблемы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
