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

Как правило, гостевая сеть 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].