tanenbaum_seti_all.pages (525408), страница 109

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

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

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

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

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

Для примера рассмотрим ситуацию, показанную на рис. 5А. Предположим, что график между станциями А и А ', В и В; а также С и С' настолько интенсивный, что горизонтальные линии связи оказываются полностью насыщенными. Чтобы максимизировать общий поток данных, трафик между станциями Х и Х' следовало бы совсем отключить.

Однако станции Х и Х', скорее всего, имеют другую точку зрения по данному вопросу. Очевидно, необходим компромисс между СПраведливым выделением графика всем станциям и оптимальным использованием канала в глобальном смысле, В' Рис. Вин Конфликт спрааадлиаости и оптимальности 408 Глава 5. Сетевой уровень Прежде чем пытаться искать приемлемое соотношение справедливости и оптимальности, следует решить, что именно мы будем стремиться оптимизировать, Можно попробовать минимизировать среднее время задержки или увеличить общую пропускную способность сети.

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

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

Принцип оптимальности маршрута Прежде чем перейти к рассмотрению отдельных алгоритмов, возможно, следует привести некие общие положения, описывающие оптимальные маршруты, вне зависимости от топологии или графика. Такой основополагающей идеей является принцип оптимальности. В соответствии с этим принципом, если маршрутизатор В располагается на оптимальном маршруте от маршрутизатора А к маршрутизатору С, то оптимальный маршрут от маршрутизатора В к маршрутизатору С совпадет с частью первого маршрута. Чтобы убедиться в этом, обозначим часть маршрута от маршрутизатора А к маршрутизатору В как ге а остальную часть маршрута — гк Если бы существовал более оптимальный маршрут от маршрутизатора В к маршрутизатору С, чем ге то его можно было объединить с гл чтобы улучшить маршрут от маршрутизатора А к маршрутизатору С, что противоречит первоначальному утверждению о том, что маршрут Пг, является оптимальным.

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

У одной сети могут существовать несколько входных деревьев с одинаковыми длинами путей. Цель всех алгоритмов выбора маршрутов заключается в вычислении н использовании входных деревьев для всех маршрутизаторов. Рис. 6.5. Подсеть (а); входное дерево длв маршрутизатора В гб) Поскольку входное дерево действительно является деревом, оно не содержит петель, поэтому каждый пакет будет доставлен за конечное и ограниченное число пересылок. На практике все это не так просто. Линии связи и маршрутизаторы могут выходить нз строя и снова появляться в сети во время выполнения операции, поэтому у разных маршрутизаторов могут оказаться различные представления о текущей топологии сети.

Кроме того, мы обошли вопрос о том, собиРает ли маршрутизатор информацию для вычисления входного дерева сам или эта информация каким-то другим образом поступает к нему. Мы вскоре рассмотрим втот вопрос. Тем не менее, принцип оптимальности и входное дерево — это те точки отсчета, относительно которых можно измерять эффективность различных алгоритмов маршрутизации. Выбор кратчайшего пути Начнем наше изучение алгоритмов выбора маршрутов с метода, широко применяемого в различных формах благодаря его простоте и понятности. Идея заключается в построении графа подсети, в котором каждый узел будет соответствовать маршрутизатору, а каждая дуга — линии связи (часто называемой просто счязью), При выборе маршрута между двумя маршрутизаторами алгоритм просто находит кратчайший путь между ними на графе. Концепция кратчайшего пути требует некоторого пояснения.

Один из способов измерения длины пути состоит в подсчете количества транзитных участков, В таком случае пути АВС и АВЕ на рис, 5,6 имеют одинаковую длину. Можно из'мерять расстояния в километрах. В таком случае окажется, что путь АВС значительно длиннее пути АВЕ (предполагается, что рисунок изображен с соблюдени- ем масштаба). 410 Глава 5. Сетевой уровень в(2, Я) В 7 с(,-) 0 Я 0 (со, -) Н (со, -) 6(6, Я) б с(9, в) В(2, Я) В(2, Я) С(9, В) 0(со,-) Я 0(со, 1) 6(6,Я) Н(со, -) 6(6, Е) г н(,,-) в(г,я) с(9, в) В(2, Я) С(9, В) 0(ос,-) Я 0 (со, -) 6(6, Е) д Н(9, 6) 6(6, Е) тв н(6, Е) е рио.

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

В общем случае параметры дуг графа являются функциями расстояния, пропускной способности, средней загруженности, стоимости связи средней длины очереди, измеренной величины задержки и других факторов. Изменяя весовую функцию, алгоритм может вычислять кратчайший путь с учетом любого количества критериев в различных комбинациях. Известно несколько алгоритмов вычисления кратчайшего пути между двумя у~лами гРафа. Один из них был создан знаменитым дейкстрой (О()Ь(га) в 1959 году.

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

Список файлов книги