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

'''Теорема 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].

Как правило, гостевая сеть G эмулируется хостовой сетью H за счет вложения G в H. Узлы сети G отображаются на узлы сети H, а ребра G – на пути в H. Если P – множество из e путей (каждый из которых соответствует ребру в гостевой сети G), то нагруженность и протяженность определяются аналогично задаче с множеством путей P, то есть c обозначает максимальное количество путей, использующих любое ребро H, а d – длину самого длинного пути в P. Кроме этого, нагрузка l определяется как максимальное число вершин в G, отображенных на одну вершину H. После вложения G в H сеть H может эмулировать сеть G следующим образом. Каждая вершина H эмулирует локальные вычисления, выполняемые l (или меньшим числом) вершин, отображаемых на нее, за время O(l). Тогда для каждого пакета, пересылаемого вдоль ребра сети G, сеть H пересылает пакет по соответствующему пути во вложении; согласно оффлайновому результату LMR, на это требуется O(c + d) шагов. Таким образом, H может эмулировать каждый шаг в G за O(c + d + l) шагов.

Рассмотрим задачу планирования для заданий j1, ..., jr и машин m1, ..., ms, в которой каждое задание должно выполняться на заданной последовательности машин (в заданном порядке). Предположим, что каждое задание тратит единицу времени на каждой машине и что ни одна машина не должна выполнять какое-либо задание более одного раза (на языке составления расписаний имеет место ациклическая задача планирования с единичными заданиями без вытеснения). Существует отображение последовательностей машин на пути и заданий на пакеты, представляющее собой иную формулировку основной задачи маршрутизации пакетов, в которой c теперь обозначает максимальное количество заданий, которые должны выполняться на любой отдельной машине, а d – максимальное количество различных машин, выполняющих любое отдельное задание; для соответствующего экземпляра задачи маршрутизации пакетов O(c) теперь обозначает нагруженность, а O(d) – протяженность. Оффлайновый результат LMR показывает, что существует план, при котором все задания выполняются за O(c + d) шагов и, кроме того, время ожидания между последовательными машинами для каждого задания составляет не более константного количества шагов (к тому же размер очереди заданий, ожидающих некоторую конкретную машину, всегда будет ограничен константой). Техники, аналогичные использованным в статье о LMR, были впоследствии применены к более общим задачам планирования набора заданий; см. работы [4, 11].

Основная нерешенная проблема заключается в том, существует ли рандомизированное онлайновое планирование пакетов, соответствующее границам оффлайнового алгоритма LMR,составляющим O(c + d). Приведенная в работе [ ] граница близка к нему, но все же логарифмически возрастает вместе с ростом числа пакетов.

В контексте задачи планирования набора заданий неизвестно, можно ли улучшить алгоритм аппроксимации с константным коэффициентом для ациклической задачи планирования набора заданий с единичной длиной без вытеснения, подразумеваемой LMR, до PTAS. Неизвестно также, существует ли алгоритм аппроксимации с константным коэффициентом для заданий произвольной длины.