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

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

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

Даже если через одно ребро должно пройти много пакетов, вряд ли они подойдут одновременно, так как конкуренция за ребра была «сглажена». Сейчас мы покажем, что такая рандомизация при правильной реализации работает достаточно эффективно.

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

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

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

Но если r не будет очень большим, где-то в сети может произойти конфликт и в алгоритме произойдет сбой: два пакета одновременно подойдут к ребру e на одном шаге t, и оба должны будут пересечь e на следующем шаге.