Маршрутизация пакетов: различия между версиями

Перейти к навигации Перейти к поиску
Строка 9: Строка 9:


== Основные результаты ==
== Основные результаты ==
Неожиданный и примечательный результат LMR выглядит следующим образом.
Неожиданный и очень эффектный результат LMR выглядит следующим образом.




Теорема [5]. Для любой сети G с заранее определенным множеством путей P с нагруженностью c и протяженностью d существует план длины O(c + d), в котором размер очередей при каждом ребре всегда ограничен константой.
'''Теорема 1 [5]. Для любой сети G с заранее определенным множеством путей P с нагруженностью c и протяженностью d существует план длины O(c + d), в котором размеры очередей при каждом ребре всегда ограничены константой.'''




Изначальное доказательство теоремы в статье о LMR не является конструктивным. Оно использует лемму о локальности [ ] для доказательства существования такого плана, но не дает способов его нахождения. В своей книге [10] Шайделер показал, что фактически существует план длины O(c + d), размер очередей при ребрах в котором ограничен 2, и дал более простое доказательство изначального результата LMR. В последующей статье Лейтон, Мэггз и Рича [6] в 1999 году предложили конструктивную версию LMR, которая выглядит следующим образом.
Доказательство теоремы в статье о LMR не является конструктивным. Оно использует лемму о локальности [3] для доказательства существования такого плана, но не дает способов его нахождения. В своей книге [10] Шайделер показал, что фактически существует план длины O(c + d), размер очередей при ребрах в котором ограничен 2, и дал более простое доказательство изначального результата LMR. В последующей статье Лейтон, Мэггз и Рича [6] в 1999 году предложили конструктивную версию LMR, которая выглядит следующим образом.




Теорема [6]. Для любой сети G с заранее определенным множеством путей P с нагруженностью c и протяженностью d существует план длины O(c + d). Более того, этот план может быть найден за время 0(p\og1+p\og*(c+ d)) для любого e>0, где p – сумма длин путей, взятых по пакетам, а " включено в константу, спрятанную в скобках O большого в выражении для длины плана.
'''Теорема 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].
 
== Применение ==
== Применение ==
'''Эмуляция сети'''
'''Эмуляция сети'''
4551

правка

Навигация