Распределенные алгоритмы — страница 2

  • Просмотров 11054
  • Скачиваний 574
  • Размер файла 960
    Кб

3 PAGEREF _Toc423280473 \h 88 Раздел 3.1 PAGEREF _Toc423280474 \h 88 Раздел 3.2 PAGEREF _Toc423280475 \h 89 4 Алгоритмы маршрутизации PAGEREF _Toc423280476 \h 89 4.1 Адресат-основанная маршрутизация PAGEREF _Toc423280477 \h 91 4.2 Проблема кротчайших путей всех пар PAGEREF _Toc423280478 \h 95 4.2.1 Алгоритм Флойда-Уошала PAGEREF _Toc423280479 \h 95 4.2.2 Алгоритм кротчайшего пути.(Toueg) PAGEREF _Toc423280480 \h 98 4.2.3 Обсуждение и Дополнительные Алгоритмы PAGEREF _Toc423280481 \h 102 4.3 Алгоритм Netchange PAGEREF _Toc423280482 \h 106 4.3.1 Описание алгоритма PAGEREF _Toc423280483 \h

107 4.3.2 Корректность алгоритма Netchange PAGEREF _Toc423280484 \h 112 4.3.3 Обсуждение алгоритма PAGEREF _Toc423280485 \h 113 4.4 Маршрутизация с Компактными Таблицами маршрутизации PAGEREF _Toc423280486 \h 114 4.4.1 Схема разметки деревьев PAGEREF _Toc423280487 \h 115 4.4.2 Интервальная маршрутизация PAGEREF _Toc423280488 \h 118 4.4.3 Префиксная маршрутизация PAGEREF _Toc423280489 \h 125 4.5 Иерархическая маршрутизация PAGEREF _Toc423280490 \h 127 4.5.1 Уменьшение количества решений маршрутизации PAGEREF _Toc423280491 \h 128 Упражнения к Части

4 PAGEREF _Toc423280492 \h 130 Раздел 4.1 PAGEREF _Toc423280493 \h 130 Раздел 4.2 PAGEREF _Toc423280494 \h 131 Раздел 4.3 PAGEREF _Toc423280495 \h 131 Раздел 4.4 PAGEREF _Toc423280496 \h 131 Раздел 4.5 PAGEREF _Toc423280497 \h 132 5 Беступиковая коммутация пакетов PAGEREF _Toc423280498 \h 132 5.1 Введение PAGEREF _Toc423280499 \h 133 5.2 Структурированные решения PAGEREF _Toc423280500 \h 134 5.2.1 Буферные Графы PAGEREF _Toc423280501 \h 135 5.2.2 Ориентации G PAGEREF _Toc423280502 \h 138 5.3 Неструктурированные решения PAGEREF _Toc423280503 \h 141 5.3.1 Контроллеры с прямым и обратным счетом PAGEREF

_Toc423280504 \h 141 5.3.2 Контроллеры с опережающим и отстающим состоянием PAGEREF _Toc423280505 \h 142 5.4 Дальнейшие проблемы PAGEREF _Toc423280506 \h 144 5.4.1 Топологические изменения PAGEREF _Toc423280507 \h 145 5.4.2 Другие виды тупиков PAGEREF _Toc423280508 \h 146 5.4.3 Лайфлок (livelock) PAGEREF _Toc423280509 \h 147 Упражнения к Главе 5 PAGEREF _Toc423280510 \h 149 Раздел 5.1 PAGEREF _Toc423280511 \h 149 Раздел 5.2 PAGEREF _Toc423280512 \h 149 Раздел 5.3 PAGEREF _Toc423280513 \h 149 6 Волновые алгоритмы и алгоритмы обхода PAGEREF _Toc423280514 \h 149 6.1 Определение и

использование волновых алгоритмов PAGEREF _Toc423280515 \h 150 6.1.1 Определение волновых алгоритмов PAGEREF _Toc423280516 \h 151 6.1.2 Элементарные результаты о волновых алгоритмах PAGEREF _Toc423280517 \h 153 6.1.3 Распространение информации с обратной связью PAGEREF _Toc423280518 \h 155 6.1.4 Синхронизация PAGEREF _Toc423280519 \h 156 6.1.5 Вычисление функций инфимума PAGEREF _Toc423280520 \h 156 6.2 Волновые алгоритмы PAGEREF _Toc423280521 \h 158 6.2.1 Кольцевой алгоритм PAGEREF _Toc423280522 \h 158 6.2.2 Древовидный алгоритм PAGEREF _Toc423280523

\h 159 6.2.3 Эхо-алгоритм PAGEREF _Toc423280524 \h 161 6.2.4 Алгоритм опроса PAGEREF _Toc423280525 \h 163 6.2.5 Фазовый алгоритм PAGEREF _Toc423280526 \h 164 6.2.6 Алгоритм Финна PAGEREF _Toc423280527 \h 167 6.3 Алгоритмы обхода PAGEREF _Toc423280528 \h 169 6.3.1 Обход клик PAGEREF _Toc423280529 \h 170 6.3.2 Обход торов PAGEREF _Toc423280530 \h 171 6.3.3 Обход гиперкубов PAGEREF _Toc423280531 \h 172 6.3.4 Обход связных сетей PAGEREF _Toc423280532 \h 173 6.4 Временная сложность: поиск в глубину PAGEREF _Toc423280533 \h 175 6.4.1 Распределенный поиск в глубину PAGEREF _Toc423280534 \h 176 6.4.2