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

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