Теормин, страница 2

Частично упорядоченное множество (W, <) называется фундированным, если из его элементов нельзя составить бесконечно убывающую последовательность.

Определение 3.4.

Пусть заданы система переходов S и утверждение P. Функция f, отображающая множество C в фундированное множество W, называется функцией нормировки (по отношению к P), если для каждого перехода y -> z, либо выполняется f(y) > f(z), либо P(z) принимает истинное значение.

Теорема 3.3.

Пусть заданы система переходов S и утверждение P. Если S правильно завершает выполнения, и существует функция нормировки f (по отношению к P), то для каждого выполнения S утверждение P становится истинным в некоторой конфигурации.

Теорема 3.4.

Утверждение P является инвариантом алгоритма раздвижного окна.

Теорема 3.5.

Симметричный протокол раздвижного окна удовлетворяет требованию безопасной доставки сообщений, т.е. в каждой достижимой конфигурации протокола выполняются соотношения out_p[0..s_p-1]=in_q[0..s_p-1], out_q[0..s_q-1]=in_p[0..s_q-1]

Лемма 3.1.

В любой достижимой конфигурации выполняются неравенства s_p - l_q <= a_р <= s_q <= a_q + l_p <= s_p + l_p

Лемма 3.2.

В любой достижимой конфигурации допустимо хотя бы одно из двух действий: отправление пакета (расk, in_p[s_q], s_q) процессом р или отправление пакета (расk, in_q[s_p], s_p) процессом _q.

Теорема З.6.

Симметричный протокол раздвижного окна удовлетворяет требованию неизбежной доставки сообщений, т.е. для каждого целого числа к >= 0 , в ходе любого выполнения протокола будет достигнуты конфигурация, в которой s_p >= k и s_q >= k.

Пусть L = l_р + l_q

Лемма 3.3.

Отправление пакета (расk, w, i) процессом p допустимо только тогда, когда i < a_p + L.

Лемма 3.4.

Если out_p[i] ≠ udef, то выполняется неравенство i < s_p + L.

Такой вариант алгоритма раздвижного окна называется протоколом чередующихся (альтернирующих) битов; он предназначен для односторонней передачи данных (L=1).

1. Коммуникационный протокол с таймерами. Допущения о времени. Таймеры. Устройство протокола с таймерами. Обоснование корректности протокола с таймерами. Модификации протокола.

Упрощённый протокол сквозной передачи сообщений:

1. Однонаправленность. Передача данных идет только в одном направлении от процесса p к процессу q. Мы будем называть процесс p отправителем, а процесс q — получателем.

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

3. Упрощенные допущения о времени. Используется минимальное количество таймеров. Например, предполагается, что подтверждение может быть отправлено в любое время до тех пор, пока получатель поддерживает соединение открытым.

4. Пакеты состоят из одного слова. В каждый пакет данных отправитель может поместить одно-единственное слово.

Таймеры — устройства, измеряющие физическое время

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

2. Ограниченное время жизни пакета

3. Таймер — это вещественная переменная X_t, значение которой со временем постоянно убывает (или присваивается этой переменной явным образом).

Утверждение:

Никакой протокол не может предоставить гарантии того, что слово будет доставлено по назначению за ограниченный срок времени. (т.е. невозможно одновременное отсутствие потерь и сохранение порядка)

<дальше шёл алгоритм, доказательство его корректности, безопасности, инварианта, …> см. слайды

Теорема 4.3. (об отсутствии потерь)

Каждое слово массива in_p либо достигает процесса q, либо отмечается процессом p как утраченное в течение U + 2µ + R + λ единиц времени после поступления этого слова процессу р.

Теорема 4.4. (о сохранении порядка вручения)

Слова, доставленные процессом q потребителю, расположены в строго возрастающем порядке в массиве in_p.

1. Задача маршрутизации. Маршрутизация на основе узлов-адресатов. Задача построения кратчайших путей для всех пар вершин. Алгоритм Флойда-Уоршалла. Алгоритм Туэга. Алгоритм Мерлина-Сигалла. Алгоритм Чанди-Мисры.

Из каждого узла пакеты информации могут непосредственно передаваться только некоторому подмножеству других узлов, которые называются соседями этого узла.

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

Задачу маршрутизации можно разбить на две алгоритмические составляющие:

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

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

Критерии оценки качества методов маршрутизации учитывают следующие показатели.

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

2. Эффективность. Алгоритм должен отправлять пакеты по «наилучшим» путям.

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

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

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

6. Справедливость. Алгоритм должен обслуживать всех пользователей в равной мере.

Несколько вариантов понятия «наилучший путь» :

1. Минимальное количество звеньев.

2. Минимальная стоимость.

3. Минимальная задержка.

Основные допущения о свойствах маршрутов:

1. Стоимость отправления пакета по пути P не зависит от того, используются ли ребра пути P для продвижения других сообщений. Поэтому стоимость C(P) пути P — это функция, зависящая только от самого пути.

2. При последовательном соединении двух путей образуется новый путь, стоимость которого равна сумме стоимостей двух исходных путей, т.е. C({u₀, u₁, ..., u_k}) = C({u₀, ..., u_i}) + C({u_i, ..., u_k}).

Стоимость пустого пути {u₀} равна 0.

1. В графе нет циклов отрицательной стоимости.

Путь из вершины u в вершину v называется оптимальным если нет пути меньшей стоимости из u в v.

Лемма 5.1. (о простых путях).

Пусть u и v — вершины графа G. Если в графе G есть путь P из u в v, то имеется также и простой путь из u в v, который является при этом оптимальным.

Теорема 5.1. (о дереве оптимальных путей).

Для каждой вершины u ∈ V связного графа G существует такое дерево T_u = (V, E_u), E_u ⊆ E, в котором для любой вершины v ∈ V, единственный путь из v в u в дереве T_u является оптимальным путем из v в u в графе G.

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

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

Лемма 5.2. (об ациклических таблицах)

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

S-путь – путь через вершины подмножества S всех вершин V.

Алгоритм Флойда-Уоршалла

<описание алгоритма Флойда-Уоршалла> см. слайды

Допущения:

1. Каждый цикл имеет положительный вес

2. Каждый процесс располагает информацией об отличительных признаках всех узлов системы

3. Каждый процесс знает кто его соседи (знает их отличительные признаки) и вес соединяющих их каналов

Теорема 5.3. (об алгоритме Флойда-Уоршалла)

Алгоритм Флойда-Уоршалла вычисляет расстояние между всеми парами вершин за θ(N³) шагов.

Алгоритм Туэга

В основу алгоритма Туэга (Toueg) положен централизованный алгоритм Флойда-Уоршалла.

<описание алгоритма Туэга (Toueg)> см. слайды

Допущения:

1. Каждый цикл имеет положительный вес

2. Каждый процесс располагает информацией об отличительных признаках всех узлов системы

3. Каждый процесс знает кто его соседи (знает их отличительные признаки) и вес соединяющих их каналов

Теорема 5.5. (корректности и сложности алгоритма Туэга)

Для каждой пары вершин u и v алгоритм Туэга вычисляет расстояние между u и v. Если это расстояние конечно, то он также определяет первый канал в кратчайшем пути.

По ходу работы алгоритма по каждому каналу проходит O(N) сообщений, O(N²W) битов информации. Таким образом, суммарно по ходу работы алгоритма передается O(N _*|Е|) сообщений и O(N³ _* W) битов информации. Кроме того в каждом узле используется память, объем которой составляет O(N _* W) битов.

Алгоритм Туэга:

Достоинства: Прост, имеет небольшую сложность, и строит оптимальные маршруты.

Недостатки:

1. Плохая устойчивость («робастость»): при изменении топологии сети все вычисления нужно проводить заново.

2. Согласованный выбор очередной опорной вершины (w) всеми узлами сети предполагает, что множество участвующих в алгоритме процессов заранее известно.

3. В алгоритме Туэга часто применяется неравенство треугольника d(u, v) < d(u, w) + d(w, v). Для вычисления правой части этого неравенства (в узле u) требуется «глобальная» информация о d(w, v), которой не обладает ни процесс u, ни его соседи. Зависимость от удаленных данных вынуждает нас организовать доставку этой информации удаленным вершинам.

Алгоритм Мерлина-Сигалла

<алгоритм Мерлина-Сигалла> см. слайды

Особенности:

1. Алгоритм может быть приспособлен к изменяющейся топологии.

2. Вычисления для разных вершин адресатов проводятся независимо.

3. Походу вычислений таблицы всегда находятся в ациклическом состоянии.

Теорема 5.6. (корректности и сложности алгоритма Мерлина-Сигалла)

Алгоритм Мерлина—Сигалла вычисляет таблицы маршрутизации по кратчайшим путям, совершая при этом обмен O(N²) сообщениями и передавая O(N² _* W) битов информации по каждому каналу связи, имея, таким образом, коммуникационную сложность O(N² _* |Е|) и битовую сложность O(N² _* |E|W).

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

Подробнее см. слайды.

Сложность Чанди-Мисры совпадает со сложностью Мерлина-Сигалла.

(я не вижу разницы между этими алгоритмами)

1. Алгоритм маршрутизации Netchange. Описание алгоритма. Инварианты алгоритма Netchange. Корректность алгоритма Netchange. Сходимость алгоритма Netchange. Особенности реализации алгоритма. Другие виды маршрутизации: интервальная, префиксная, иерархическая.

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