1 (1131253), страница 37

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

Текст из файла (страница 37)

Рисунок 5-16. Иерархическая маршрутизация

Однако за эту экономию приходится платить эффективностью маршрутизации. Например, наилучший маршрут от 1А к 5С проходит через регион 2, однако в данном случае он пройдет через регион 3, поскольку большинство машин в регионе 5 действительно эффективнее достигнуть через регион 3.

При построении иерархии возникает сразу несколько вопросов. Один из них: сколько уровней должно быть в иерархии при заданном размере сети? Например, если наша транспортная среда содержит 920 маршрутизаторов, то без иерархии таблица каждого будет иметь 920 строк. Если транспортную среду разбить на 40 регионов, то размер таблиц будет равен 23 строки для маршрутизации внутри региона плюс 40 для маршрутизации между регионами. Если использовать трехуровневую иерархию и объединить регионы в кластеры, то при 5 кластерах, по 8 регионов с 23 маршрутизаторами в каждом у таблицы будет 23 входа для внутрикластерной маршрутизации, плюс 7 входов для межкластерной, плюс 5 входов для межрегиональной маршрутизации. Итого 35 входов.

Клейнрок и Камоун показали, что оптимальное число уровней иерархии в транспортной среде при N узлах будет равняться lnN, при e*lnN строках в таблице маршрутизатора.

Маршрутизация для мобильного узла.

На рисунке 5-17 показана модель WAN с мобильным узлом. Всех пользователей мы можем разделить на две большие группы. Стационарные - это большая группа, их компьютеры подключены к сети стационарными средствами (проводами, кабелями) и редко меняют свое место положение. Другая группа постоянно меняет свое местоположение и стремится поддерживать связь с сетью. Этих пользователей мы будем называть мобильными.

Рисунок 5-17. Модель WAN с мобильным узлом

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

Как только мобильный узел подключается к местной, локальной сети, он регистрируется у агента визитеров. Эта процедура примерно выглядит так:

1. Периодически агент визитеров рассылает по своей области пакет, где указано местоположение этого агента и его адрес. Если мобильный узел, подключившись к сети, долго не видит такого пакета, он рассылает свой пакет с просьбой агенту визитеров объявить свои координаты.

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

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

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

1. Агент визитеров, получив подтверждение от домашнего агента, заносит данные о мобильном узле в свои таблицы и регистрирует его.

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

Рассмотрим теперь, что происходит, когда кто-то посылает сообщения мобильному узлу (рисунок 5-18). Пакет поступает на адрес домашнего местоположения пользователя, где его перехватывает домашний агент. Домашний агент инкапсулирует этот пакет в свой пакет, который он отправляет по адресу агента визитеров той области, откуда последний раз был сеанс связи с пользователем. Одновременно с этим домашний агент посылает сообщение отправителю пакета, чтобы он все последующие пакеты мобильному узлу инкапсулировал в сообщениях, направляемых по адресу агента визитеров. Такой механизм инкапсулирования одних пакетов в другие называется туннелированием, и мы его подробно рассмотрим позднее.

Рисунок 5-18. Маршрутизация пакетов для мобильных пользователей

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

Маршрутизация при вещании.

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

Первый способ: источник знает, кому надо послать, и генерирует столько сообщений, сколько получателей. Это одно из самых плохих решений. Оно не требует никаких специальных средств, однако весьма накладно. Тратится не только пропускная способность каналов, но и память – ведь где-то кому-то надо хранить весь лист рассылки.

Метод лавины – другое решение. Однако, как мы уже видели, он затратен для каналов «точка-точка». Он слишком сильно расходует пропускную способность.

Третий подход – маршрутизация множественной доставки. Здесь каждый пакет должен иметь либо лист рассылки, либо карту рассылки. Каждый маршрутизатор, получив такой пакет, отправляет и дублирует его в соответствии с картой рассылки.

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

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

Этот метод называется пересылкой вдоль обратного пути. На рисунке 5-19 показан пример работы этого алгоритма. На рисунке 5-19 (a) показана топология транспортной среды. На рисунке 5-19 (b) показано дерево захода для вершины I, часть (c) показывает, как работает этот алгоритм. Сначала в вершине I было сгенерировано и разослано 4 пакета. Во всех четырех вершинах (F, H, J, N), куда поступили эти пакеты, они поступили с предпочтительного для I направления. Из восьми пакетов, сгенерированных на следующем этапе, дереву захода только пять поступили по предпочтительному для I направлению. На третьем этапе из шести сгенерированных пакетов только три поступили по предпочтительному направлению (G, D, N поступили дубликаты). После того, как пять этапов пройдены и сгенерированы 23 пакета, рассылка прекращается. Достоинством этого метода является простота и легкость в реализации.

Рисунок 5-19. Пересылка вдоль обратного пути (а) Подсеть; (b) Связующее дерево; (с) Дерево, построенное методом пересылки вдоль обратного пути

Маршрутизация при групповой передаче.

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

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

Алгоритм групповой маршрутизации, как правило, основан на дереве связей. Каждый маршрутизатор в транспортной среде вычисляет дерево связей, охватывающее все другие маршрутизаторы. На рисунке 5-20 (а) приведен пример транспортной среды, состоящей из двух групп (их номера указаны у вершин). Некоторые вершины принадлежат как группе 1, так и группе 2. На рисунке 5-20 (b) показано дерево связей для самой левой вершины. Когда процесс посылает групповой пакет, первый же маршрутизатор обрезает свое дерево связей, убирая из него все связи, которые не ведут в вершины, не являющиеся членами группы. На рисунке 5-20 (с) показано сокращенное дерево связей для группы 1. На рисунке 5-20 (d) дано сокращенное дерево связей для группы 2.

Рисунок 5-20. Групповая маршрутизация

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

Билет № 37.

Сетевой уровень: проблемы построения сетевого уровня (Сервис, внутренняя организация сетевого уровня). Алгоритмы управления перегрузками на сетевом уровне (Основные принципы управления перегрузками, методы предотвращения перегрузок: формирование трафика, спецификация потока, управление перегрузками в сетях с виртуальными каналами; методы устранения перегрузок: подавляющие пакеты, сброс трафика; управление перегрузками при вещании).

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

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

Перегрузки могут случаться и из-за недостаточной скорости процессора. Если процессор будет не в состоянии справиться своевременно с рутинными задачами (размещения пакета в буфере, корректировка таблиц и т.п.), то даже при наличии линий с достаточной пропускной способностью очередь будет расти. Аналогичная картина может случиться при быстром процессоре, но медленном канале и наоборот. Таким образом, источник проблемы - несбалансированность производительности компонентов системы.

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

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

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

Характеристики

Список файлов ответов (шпаргалок)