Разработка алгоритма Простой рандомизированный план

Если каждое ребро просто передает на каждом шаге случайный ожидающий пакет, очевидно, полученный план имеет продолжительность O(cd): в худшем случае пакет может быть заблокирован c - 1 другими пакетами на каждом из d ребер своего пути.
Для снижения этой границы необходимо принять меры к тому, чтобы каждый пакет мог проводить в ожидании передачи существенно меньшее количество шагов.

Такая большая граница, как O(cd), может возникнуть из-за очень плохой син- хронизации пакетов по отношению друг к другу: блоки из c пакетов одновременно встречаются у одного ребра, а когда «затор» устраняется, то же самое происходит у следующего ребра. Ситуация может показаться аномальной, но следует помнить, что на рис. 13.4 она возникла из-за вполне естественной политики управления очередью. Тем не менее такое нежелательное поведение обусловлено крайне не- удачным стечением обстоятельств при синхронизации перемещения пакетов; если ввести в управление пакетами рандомизацию, такое поведение становится мало- вероятным. Проще всего включить случайный сдвиг по времени выхода пакетов из источника. Даже если через одно ребро должно пройти много пакетов, вряд ли они подойдут одновременно, так как конкуренция за ребра была «сглажена». Сейчас мы покажем, что такая рандомизация при правильной реализации работает достаточно эффективно.

Для начала рассмотрим следующий алгоритм, который на самом деле не рабо- тает. В нем задействован параметр r, значение которого будет определено позднее.

Каждый пакет i ведет себя следующим образом: i выбирает случайную задержку і от 1 до r i ожидает у источника і шагов

i движется вперед на полной скорости, по одному ребру за шаг, пока не достигнет конечной точки

Если случайные задержки действительно будут выбираться так, что никакие два пакета никогда не «столкнутся» (не подойдут к одному ребру одновременно), то этот план будет работать так, как предполагалось; его продолжительность не превысит суммы r (максимальная исходная задержка) и d (максимальное количе- ство ребер по всем путям). Но если r не будет очень большим, где-то в сети может произойти конфликт и в алгоритме произойдет сбой: два пакета одновременно подойдут к ребру e на одном шаге t, и оба должны будут пересечь e на следующем шаге.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Разработка алгоритма Простой рандомизированный план:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. План Третий шаг: план.
  3. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  4. АЛГОРИТМ УДАЧИ
  5. АЛГОРИТМ
  6. Алгоритм исцеления:
  7. Алгоритм избавления от боли
  8. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  9. Алгоритм обработки результатов.
  10. 2. Специфика и алгоритмы работы с источниками.
  11. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  12. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
  13. План –
  14. 37. План внешнего управления
  15. Разработка Плана
  16. План:
  17. 2.7. Разработка анкеты
  18. 3.3.5. Организационный план исследования