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

'''Теорема 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 большого в выражении для длины плана.'''

Алгоритм в этой статье является рандомизированным, хотя авторы утверждают, что его можно дерандомизировать с помощью метода условных вероятностей. Тем не менее, хотя алгоритм Лейтона, Мэггза и Ричи является конструктивным, он остается оффлайновым; иначе говоря, для построения расписания требуется полное знание всех пакетов в сети и точных путей, по которым будет проходить каждый из них. В исходной работе 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].