Лекция 14 адаптивные модели и алгоритмы (продолжение)

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

Пример адаптивной маршрутизации.

Классическим примером адаптивной маршрутизации является сеть ARPANET, ставшая родоначальницей сети Internet.. В ней использовался динамический каталог маршрутизации. Она также являлась при­мером распределенной пакетной системы.

Каждый узел такой сети сохраняет осведомленность о топологии всей сети и неза­висимо вычисляет оптимальный (кратчайший) путь к каждому узлу назначения. Адаптивные сети функционируют на основе концепции знания смежных узлов, т.е. каждый данный узел осведомлен о статусе всех узлов, которые смежны с ним. На рис. 1 представлен процесс адаптивной маршрутизации, который демонстрирует действие таблицы маршрутизации для узла D. Таблица состо­ит из нескольких входов, три из которых представлены на рисунке: - конечное назначение (КН), следующий узел (СУ) и вычисленную общую задержку. Если узел D желает передать пакеты в узел А, он выполняет просмотр таблицы на предмет поиска конечного назначения А и определяет, что следующим узлом, в который надо переслать пакеты, является С. Общая задержка от D к С, затем к В, затем к А составляет 7 единиц времени -короче, чем любой другой путь в А.

Как только пакеты посланы из узла D в смежные узлы (С, Е, G), программа в узле D делает запись о времени, которое потребовалось для получения АСК (ACKnowlogy - подтверждение) из смежных узлов. Кроме того, каждый узел знает, сколько у него пакетов осталось для других узлов. Каждые десять секунд узел вычисляет задержки на своих выходящих связях. Любое существенное отклонение при изменении задержки рассылается пакетной волной во все остальные узлы. После этого узлы могут использовать получен­ную информацию для перестройки таблицы маршрутизации. Наименование «динамическая» или «адаптивная» маршрутизация потому и использовано, поскольку логика маршрутизации производится на основе оценки состояния сети. Основными целями адаптивной маршрутизации являются:

• обеспечить гибкость сети, достаточную для работы с меняю­щимися условиями потоков данных, и

• обеспечить быстрый и доступный метод для решения проблемы обхода узлов.

На­пример, сеть ARPANET обрабатывала более 20 млн. пользова­тельских пакетов и отдавала пользователям свыше 99% полезно­го времени. Эта замечательная производительность достигалась в то время, как каждые две недели в систему добавлялся но­вый узел связи.

Проблемы маршрутизации

Адаптивная маршрутизация имеет свои проблемы. Во-первых, программы для обработки этой мощной схемы маршрути­зации довольно сложны. Во-вторых, существует вероятность, что пакет начнет «автоколебание» и потеряется в сети, когда будет двигаться от одного узла к другому во время, когда их таблицы маршрутизации изменяются. Однако, если таблицы маршрути­зации изменяются не часто, проблема потери пакетов не выгля­дит серьезно. Первоначально узлы сети ARPANET обменива­лись пакетами обновления со своими соседними узлами каж­дые 128 мс, что создавало множество проблем. При современ­ном подходе узлы обновляют свои таблицы каждые 10 с.

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

Кроме того существуют проблемы, характерные для многих пакетных сетей, в том числе и в ЦСИО: по­тери пакетов, их дублирование, проблемы управления, чистка сети, снятие пакетов.

Чтобы описать проблему потери пакетов, представим, что пакет направлен к узлу D через узел коммутации В, который оповестил узел А сообщением АСК (рис. "Потеря пакета"). Однако узел, который дал ответ АСК (т.е. узел В), не отправляет сам пакет, поскольку этот узел вышел из строя до отсылки пакета. Очевидно, пакет потерян. И если другие пакеты из этого сеанса в конце концов все-таки прибывают в узел конечного назначения, то потерян­ный пакет найти уже невозможно.

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

На рис. "Дублирование пакетов" показана проблема дублирования пакетов.

В этом случае ответ АСК из узла В не возвращается в А даже в случае успешной отправки пакета в узел D. Следовательно узел А предполагает, что узел В вышел из строя и повторно посылает пакет через узел С. Узел С перешлет пакет в D, кото­рый, очевидно, ранее уже получил пакет из В.

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

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

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

Проблема очи­стка сети, когда пакеты могут потеряться, представлена на рис. "Очистка сети".

Из-за различных возможных проблем (ошибки последовательности, проблемы временные и т.д.) сеть выпускает управляющий пакет (пакет очистки, сброса и рестарта), кото­рый должен завершить сеанс пользователя . Обычно, когда этот пакет прибывает в узел D, последующие пакеты этого же сеанса в этом случае не принимаются узлом D. Поэтому пакеты 2 и 3 не будут восприняты и протокол более высокого уровня должен начать восстановление этих пакетов.

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