4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 9: | Строка 9: | ||
== Основные результаты == | == Основные результаты == | ||
Неожиданный и | Неожиданный и очень эффектный результат LMR выглядит следующим образом. | ||
Теорема [5]. Для любой сети G с заранее определенным множеством путей P с нагруженностью c и протяженностью d существует план длины O(c + d), в котором | '''Теорема 1 [5]. Для любой сети G с заранее определенным множеством путей P с нагруженностью c и протяженностью d существует план длины O(c + d), в котором размеры очередей при каждом ребре всегда ограничены константой.''' | ||
Доказательство теоремы в статье о LMR не является конструктивным. Оно использует лемму о локальности [3] для доказательства существования такого плана, но не дает способов его нахождения. В своей книге [10] Шайделер показал, что фактически существует план длины O(c + d), размер очередей при ребрах в котором ограничен 2, и дал более простое доказательство изначального результата LMR. В последующей статье Лейтон, Мэггз и Рича [6] в 1999 году предложили конструктивную версию LMR, которая выглядит следующим образом. | |||
Теорема [6]. Для любой сети G с заранее определенным множеством путей P с нагруженностью c и протяженностью d существует план длины O(c + d). Более того, этот план может быть найден за время | '''Теорема 2 [6]. Для любой сети G с заранее определенным множеством путей P с нагруженностью c и протяженностью d существует план длины O(c + d). Более того, этот план может быть найден за время <math>O(p \; log^{1 + \epsilon} p \; log^* (c+d))</math> для любого <math>\epsilon > 0</math>, где p – сумма длин путей, взятых по пакетам, а <math>\epsilon</math> включено в константу, спрятанную в скобках O большого в выражении для длины плана.''' | ||
Строка 31: | Строка 31: | ||
Вернемся ненадолго к первой задаче, а именно к предварительному построению набора путей. Очевидно, наша цель заключается в нахождении для конкретного множества пакетов, с заранее заданными источниками и пунктами назначения, множества путей, которое минимизирует сумму с + d. Шринивасан и Тео [ ] разработали оффлайновый алгоритм, выдающий множество путей, для которого сумма c + d доказуемо отличается от оптимальной не более чем на константный коэффициент. Вместе с оффлайновым результатом LMR получаем задачу аппроксимации с постоянным коэффициентом для оффлайновой задачи маршрутизации пакетов с промежуточным хранением. Стоит отметить важность подхода, стремящегося минимизировать c + d, а не только c; получить планы, отличающиеся на константный коэффициент от оптимальных для нагруженности c, очень непросто, и было показано, что это связано с разрывом целостности при управлении несколькими товарными потоками [1, 2]. | Вернемся ненадолго к первой задаче, а именно к предварительному построению набора путей. Очевидно, наша цель заключается в нахождении для конкретного множества пакетов, с заранее заданными источниками и пунктами назначения, множества путей, которое минимизирует сумму с + d. Шринивасан и Тео [ ] разработали оффлайновый алгоритм, выдающий множество путей, для которого сумма c + d доказуемо отличается от оптимальной не более чем на константный коэффициент. Вместе с оффлайновым результатом LMR получаем задачу аппроксимации с постоянным коэффициентом для оффлайновой задачи маршрутизации пакетов с промежуточным хранением. Стоит отметить важность подхода, стремящегося минимизировать c + d, а не только c; получить планы, отличающиеся на константный коэффициент от оптимальных для нагруженности c, очень непросто, и было показано, что это связано с разрывом целостности при управлении несколькими товарными потоками [1, 2]. | ||
== Применение == | == Применение == | ||
'''Эмуляция сети''' | '''Эмуляция сети''' |
правка