4551
правка
Маршрутизация пакетов: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Маршрутизация с промежуточным хранением; оптимально миним…») |
Irina (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
== Основные результаты == | == Основные результаты == | ||
Неожиданный и примечательный результат LMR выглядит следующим образом. | |||
Теорема [5]. Для любой сети G с заранее определенным множеством путей P с нагруженностью c и протяженностью d существует план длины O(c + d), в котором размер очередей при каждом ребре всегда ограничен константой. | |||
Изначальное доказательство теоремы в статье о LMR не является конструктивным. Оно использует лемму о локальности [ ] для доказательства существования такого плана, но не дает способов его нахождения. В своей книге [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 большого в выражении для длины плана. | |||
Алгоритм в этой статье является рандомизированным, хотя авторы утверждают, что его можно дерандомизировать с помощью метода условных вероятностей. Тем не менее, хотя алгоритм Лейтона, Мэггза и Ричи является конструктивным, он остается оффлайновым; иначе говоря, для построения расписания требуется полное знание всех пакетов в сети и точных путей, по которым будет проходить каждый из них. В исходной работе LMR также был приведен простой рандомизированный онлайновый алгоритм, который, за счет назначения задержек пакетам независимым и равномерно случайным образом в зависимости от соответствующего интервала, позволяет составить намного более эффективный график по сравнению с результатами работы жадных алгоритмов, хотя и не настолько эффективный, как оффлайновые построения. | |||
Теорема [5]. Существует простой рандомизированный оффлайновый алгоритм для получения с высокой вероятностью плана длины O(c + dlog(Nd)), использующего очереди размера O(log(Nd)), где c обозначает нагруженность, d - протяженность, а N - число пакетов. | |||
В специальном случае, когда предполагается, что все пакеты следуют по кратчайшим путям в сети, Мейер ауф дер Хайде и Воккинг создали простой рандомизированный онлайновый алгоритм, который с высокой вероятностью вычисляет план из O(c + d + log Nd) шагов, однако очереди могут быть иметь размер O(c) [7]. Для произвольных путей онлайновый результат LMR был в конечном итоге улучшен до O(c + d + log +€ N) шагов для любого e>0 с высокой вероятностью, с чем можно подробнее ознакомиться в серии из двух работ Рабани и Тардош [ ], а также Рабани и Островского [8]. Онлайновые протоколы также изучались в условиях, когда дополнительные пакеты динамически впрыскиваются в сеть в состязательной ситуации; обзор см. в работе [ ]. | |||
Затем обсуждение ненадолго вернулось к первой задаче, а именно к предварительному построению набора путей. Очевидно, задача заключается в нахождении для конкретного множества пакетов с заранее заданными источниками и пунктами назначения множество путей, которое минимизирует сумму с + d. Шринивасан и Тео [ ] разработали оффлайновый алгоритм, выдающий набор путей, для которого сумма c + d доказуемо отличается от оптимальной не более чем на константный коэффициент. Вместе с оффлайновым результатом LMR получаем задачу аппроксимации с постоянным коэффициентом для оффлайновой задачи маршрутизации пакетов с промежуточным хранением. Стоит отметить важность подхода, стремящегося минимизировать c + d, а не только c; получить планы, отличающиеся на константный коэффициент от оптимальных для нагруженности c, очень непросто, и было показано, что это связано с разрывом целостности при управлении несколькими товарными потоками [1,2]. | |||
== Применение == | |||
Эмуляция сети | |||
