ЛЕКЦИЯ 14

АДАПТИВНЫЕ МОДЕЛИ И АЛГОРИТМЫ (продолжение)

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

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

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

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

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

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

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

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