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

Вернемся ненадолго к первой задаче, а именно – к предварительному построению набора путей. Очевидно, наша цель заключается в нахождении для конкретного множества пакетов, с заранее заданными источниками и пунктами назначения, множества путей, которое минимизирует сумму с + d. Шринивасан и Тео [12] разработали оффлайновый алгоритм, выдающий множество путей, для которого сумма c + d доказуемо отличается от оптимальной не более чем на константный коэффициент. Вместе с оффлайновым результатом LMR получаем задачу аппроксимации с постоянным коэффициентом для оффлайновой задачи маршрутизации пакетов с промежуточным хранением. Стоит отметить важность подхода, стремящегося минимизировать c + d, а не только c; получить планы, отличающиеся на константный коэффициент от оптимальных для нагруженности c, очень непросто, и было показано, что это связано с разрывом целостности при управлении несколькими товарными потоками [1, 2].

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

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