Алгоритм передачи сообщения по маршруту

Вернемся к рассмотрению сети процессов, показанной на рис. 9.12. Для процесса Р0 мы уже построили основное дерево и определили веса всех маршрутов от узла Р0 до остальных. Предположим, что теперь нам требуется послать сообщение от процесса Р0 процессу Р5. Какие структуры данных при этом должен использовать процесс Р0 и каким образом он должен построить эти структуры данных? Попробуем в этом разобраться.

Мы уже знаем минимальное остовное дерево с корнем в Р0 для этой сети, оно на рис. 10.24. По этому остовному дереву процесс Р0 может построить табл. 10.1.

Таблица маршрутов для процесса Р0

Пункт назначения

Сосед

Pi

Ps

Р2

Ps

Рз

Ps

Ра

Ра

Ps

Ps

По ней можно определить, что для того, чтобы направить сообщение кратчайшим путем процессу Р3 нужно отправить его своему соседнему процессу Р5, ибо непосредственной связи между Р0 и Р3 нет. Таким образом, если какой-либо из алгоритмов требует передачи сообщения из Р0 в Р3, то это сообщение должно направиться через посредников, первым из которых будет соседний с Р0 процесс, Р3. А каким образом промежуточный процесс определит, какому из своих соседей требуется передать сообщений, если, скажем, процесс назначения не является соседним? В нашем случае процесс Р0 имеет полную информацию о маршруте. Может ли Р0 при передаче сообщения для Р3 процессу Р0 сообщить, через какие промежуточные процессы сообщение должно доставляться? Да, конечно. Однако в каждом сообщении должна содержаться информация о маршруте для всех промежуточных процессов. Предположим, что минимальным остовным деревом нашей сети оказалось бы не дерево на рис. 10.24, а дерево с рис. 10.23. Тогда процессу Р0 для сообщения Р3 потребовалось бы передать своему соседу, Р4 информацию о том, что тому следует передать сообщение Р]3 а тот должен передать его Р5 и т. д., т. е. в первоначальном сообщении должна передаваться служебная информация о полном маршруте Р0 —» Р4 —» Р} —> —» Р5 —> Р2 —» Р3. Возможно ли это? Конечно. Удобно ли это? Очевидно, нет. Мало того, что в сообщении должна передаваться служебная информация неизвестного заранее размера, возможно, превышающая размер самого сообщения, любое изменение топологии сети, как то: исчезновение процесса, отказ связи, приведет к отказу в доставке сообщения.

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

Построим такие таблицы маршрутов для всех процессов в качестве корневых узлов (табл. 10.2).

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

Таблица 10.2

Таблица маршрутов для процесса Р1

Пункт назначения

Сосед

Ро

Р2

Рз

Рз

Рз

Рл

Рз

Рз

Рз

Таблица 10.3

Таблица маршрутов для всех процессов

Откуда

Ро

Pi

р2

Рз

Рл

Рз

Ро

Ро

Pi

Рз

Pi

Pi

р2

р2

Рз

Рз

р2

р2

Рз

Рз

Рз

Рз

Рз

Рз

Рл

Рл

Рз

Рл

Рл

Рл

Рз

Рз

Рз

Pi

Рз

Как только каждый из процессов построит свою таблицу достижимости, для маршрутизации сообщений не потребуется указывать маршрут в дополнительной информации сообщений. Действительно, теперь достаточно знать пункт назначения сообщения. Например, если процессу Р4 нужно передать сообщение в Р3, то он отправляет сообщение своему соседу Р] согласно своей таблице, тот — процессу Р5, согласно своей, и т. д., пока сообщение не будет доставлено в Р3.

Этот алгоритм — двухфазный, для стационарных систем он дает результаты, близкие к оптимальным. Однако этап вычисления таблиц первой фазы пока неэффективен, так как состоит из N независимых исполнений алгоритма остовного дерева, после которого потребуется еще этап формирования таблицы. Для централизованных систем имеется алгоритм Флойда — Уоршалла (FloydWarshall), который непосредственно строит такую таблицу. Вариант алгоритма Флойда — Уоршалла для распределенных систем предложен Туэгом (Toueg) и носит его имя.

Вопросы и задания к теме

Возможно ли послать сообщение другому процессу без построения таблиц достижимости? Если да, то напишите рабочую функцию такого алгоритма.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >