Планы и их продолжительность
Перейдем от примеров к теме планирования пакетов и управления очередями в произвольной сети 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 — количество пакетов.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Разработка универсального класса хеш-функций
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу