Планы и их продолжительность

Перейдем от примеров к теме планирования пакетов и управления очередями в произвольной сети G. Для заданных пакетов 1, 2, …, N и связанных с ними путей P1, P2, …, PN план передачи пакетов определяет для каждого ребра e и каждого кванта времени t, какой пакет будет передан по ребру e на шаге t.

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

Что может помешать построению плана с низкой продолжительностью? Одним препятствием может стать очень длинный путь, по которому должен пройти некоторый пакет; очевидно, продолжительность не может быть меньше длины этого пути.

Другое потенциальное препятствие — одно ребро e, по которому должны быть переданы многие пакеты; так как каждый из пакетов передается по e на отдельном шаге, это тоже устанавливает нижнюю границу для продолжительности.

Итак, для максимальной длины d по множеству путей {P1, P2, …, PN}   и максимальной загрузки c множества путей (максимальное количество путей, имеющих одно общее ребро) продолжительность передачи не может быть меньше.

В 1988 году Лейтон, Маггс и Рао (Leighton, Maggs, Rao) доказали следующий неожиданный результат: максимальная длина и максимальная загрузка являются единственными препятствиями для поиска быстрых планов — в том смысле, что всегда существует план с продолжительностью O(c + d).

Формулировка утверждения очень проста, но доказать его невероятно сложно; и результатом является только очень сложный метод построения такого плана.

Вместо того чтобы доказывать это утверждение, мы проанализируем простой алгоритм (также предложенный Лейтоном, Маггсом и Рао), который легко реализуется в распределенной среде и обеспечивает продолжительность, которая отличается в худшую сторону только логарифмическим множителем: O(c + d log(mN)), где  m — количество ребер, а N — количество пакетов.