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

Вернемся ненадолго к первой задаче, а именно – к предварительному построению набора путей. Очевидно, наша цель заключается в нахождении для конкретного множества пакетов, с заранее заданными источниками и пунктами назначения, множества путей, которое минимизирует сумму с + d. Шринивасан и Тео [12] разработали оффлайновый алгоритм, выдающий множество путей, для которого сумма 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. Неизвестно также, существует ли алгоритм аппроксимации с константным коэффициентом для заданий произвольной длины.