Алгоритмы прямой маршрутизации
Ключевые слова и синонимы
срочная маршрутизация; безбуферная коммутация пакетов; бесконфликтное планирование пакетов
Постановка задачи
На эффективность коммуникационных сетей серьезно влияет перекрытие, или конфликт пакетов, которое случается, когда два или несколько пакетов одновременно оказываются в одном и том же узле сети (маршрутизатора), и все эти пакеты пытаются покинуть узел по одному и тому же исходящему каналу. Поскольку пропускная способность каналов ограничена, конфликтующие пакеты вынуждены ждать в буферах, пока конфликты не будут разрешены. Конфликты вызывают задержки в доставке пакетов и снижают эффективность работы сети.
Прямая маршрутизация представляет собой метод доставки пакетов, позволяющий избежать конфликтов пакетов в сети. После того, как пакет вброшен в сеть, он следует своим путем по направлению к месту назначения, не конфликтуя с другими пакетами и, вследствие этого, не испытывая задержек из-за ожидания в буферах, пока не достигнет узла-адресата. Задержка может произойти только в узле-источнике, пока пакет ожидает вброса в сеть.
В формулировке задачи прямой маршрутизации сеть моделируется графом, в котором все узлы синхронизированы с одним общим датчиком времени. Каналы сети являются двунаправленными, и в каждый момент времени каждый канал могут пересекать только два пакета – по одному в каждом направлении. Время маршрутизации для заданного набора пакетов определяется как промежуток между вбросом первого пакета и доставкой последнего.
Рассмотрим набор из N пакетов, в котором у каждого пакета имеется свой узел-источник и свой узел-адресат. Цель задачи прямой маршрутизации состоит в первую очередь в нахождении набора путей по сети для пакетов, а затем в нахождении подходящего времени вброса пакетов в сеть, так что вброшенные в нужный момент пакеты смогут проследовать до места назначения без конфликтов. Задача прямого планирования представляет собой вариацию задачи прямой маршрутизации, в которой пути пакетов заданы априори, и нужно только вычислить подходящее время для вброса пакетов в сеть.
Цель любого алгоритма (как прямой маршрутизации, так и прямого планирования) заключается в достижении минимального времени маршрутизации для пакетов. Обычно прямые алгоритмы являются оффлайновыми, т.е. пути и план вброса рассчитываются заблаговременно, до момента собственно вброса, поскольку для расчетов требуется наличие информации обо всех пакетах, чтобы гарантировать отсутствие конфликтов между ними.
Основные результаты
Буш, Магдон-Исмаил, Маврониколас и Спиракис представили в своей книге [6] исчерпывающее исследование прямых алгоритмов. Они изучали различные аспекты прямой маршрутизации – такие как вычислительная сложность задач прямых вычислений и построение эффективных прямых алгоритмов.
Трудности прямой маршрутизации
В главе 4 [6] показано, что оптимальная задача прямого планирования, в которой пути заранее заданы и требуется вычислить оптимальный план вброса пакетов, обеспечивающий достижение минимального времени маршрутизации, является NP-полной. Этот результат был получен при помощи редукции алгоритма раскраски вершин; задача раскраски вершин преобразуется в соответствующую задачу прямого планирования на двумерной решетке. Кроме того, было показано, что найти приближенные решения задачи прямого планирования так же сложно, как приближенные решения задачи раскраски вершин. Вопрос о том, какие виды аппроксимаций можно получить за полиномиальное время, изучается в той же работе для графов общего вида и некоторых отдельных разновидностей.
Прямая маршрутизация в графах общего вида
В главе 3 [6] приводится прямой алгоритм, решающий в приближенном виде задачу оптимального прямого планирования в сетях с топологиями общего вида. Пусть имеются набор пакетов и соответствующие пути. Вычисление плана вброса занимает полиномиальное время относительно размера графа и числа пакетов. Время маршрутизации характеризуется такими параметрами, как C – нагруженность путей передачи пакетов (максимальное число пакетов, использующих ребро графа), и D – протяженность (максимальная длина любого пути).
В [6] установлено существование простого жадного алгоритма прямого планирования с временем маршрутизации [math]\displaystyle{ rt = O(C \cdot D) }[/math]. В этом алгоритме пакеты обрабатываются в произвольном порядке; каждому пакету назначается наименьшее возможное время вброса. Полученное время маршрутизации является оптимальным в наихудшем случае, поскольку существуют примеры задач прямого планирования, для которых ни один алгоритм прямого планирования не может обеспечить лучшего времени маршрутизации. Тривиальная нижняя граница времени маршрутизации любой задачи прямого планирования составляет [math]\displaystyle{ \Omega (C + D) \; }[/math], поскольку ни один алгоритм не может доставить пакеты быстрее, чем позволяют значения нагруженности и протяженности путей. Таким образом, в общем случае время маршрутизации для алгоритма в [6] составляет [math]\displaystyle{ rt = O((rt^*)^2) \; }[/math], где rt* - оптимальное время маршрутизации.
Прямая маршрутизация в графах некоторых отдельных разновидностей
Для сетей определенной топологии представлены специальные прямые алгоритмы. Эти алгоритмы решают задачу прямой маршрутизации, в которой вначале строятся хорошие пути, а затем вычисляется эффективный план вброса пакетов. Пусть для некоторого набора пакетов C* и D* обозначают оптимальные значения нагруженности и протяженности, соответственно, для всех возможных наборов путей прохождения пакетов. Очевидно, что оптимальное время маршрутизации составляет [math]\displaystyle{ rt* = \Omega(C^* + D^*) \; }[/math]. Верхняя граница прямого алгоритма из [6] выражается в терминах этой нижней границы. Все алгоритм исполняются за время, полиномиальное относительно размера входного графа.
Дерево. Пусть граф G представляет собой произвольное дерево. Алгоритм прямой маршрутизации (глава 3.1, [6]) обеспечивает движение каждого пакета по кратчайшему пути из точки вброса до места назначения. План вброса вычисляется при помощи жадного алгоритма с учетом порядка пакетов. Время маршрутизации этого алгоритма является асимптотически оптимальным: [math]\displaystyle{ rt \le 2C^* + D^* -2 \lt 3 \cdot rt^* \; }[/math].
Сотовая сеть. Граф G представляет собой d-мерную сотовую сеть (решетку) с n узлами [10]. Алгоритм прямой маршрутизации (глава 3.2, [6]) вначале строит эффективные пути для пакетов с нагруженностью [math]\displaystyle{ C = O(d \; log n \cdot C^*) }[/math] и протяженностью [math]\displaystyle{ D = O(d^2 \cdot D^*) }[/math] (нагруженность с высокой вероятностью гарантирована). Затем, используя эти пути, вычисляется план вброса; при этом используется прямой алгоритм с временем маршрутизации [math]\displaystyle{ rt = O(d^2 log^2 n \cdot C^* + d^2 \cdot D^*) = O(d^2 log^2 n \cdot rt^*) }[/math].
Этот результат следует из более общего, приведенного там же, который утверждает, что если пути содержат не более b «поворотов», т.е. изменений размерности, то существует алгоритм прямого планирования с временем маршрутизации [math]\displaystyle{ O(b \cdot C + D) \; }[/math]. Это следует из того, что сконструированные пути имеют [math]\displaystyle{ b = O(d \; log n) }[/math] поворотов.
Бабочка. Граф G представляет собой сеть в форме бабочки с n входными и n выходными узлами [10]. В главе 3.3 [6] авторы исследовали задачу маршрутизации перестановок в бабочке, где каждый входной (выходной) узел является источником (адресатом) ровно одного пакета. Эффективный алгоритм прямой маршрутизации [6] вначале вычисляет хорошие пути для пакетов, используя метод Валианта [14, 15]: две бабочки соединяются «спина к спине», и каждый путь строится путем выбора случайного промежуточного узла в выходной части первой бабочки. Выбранные пути имеют нагруженность [math]\displaystyle{ C = O(lg \; n) }[/math] (с высокой вероятностью) и протяженность [math]\displaystyle{ D = 2 \; lg \; n = O(D^*) \; }[/math]. Затем, используя эти пути, вычисляется план вброса с временем маршрутизации, очень близким к оптимальному – [math]\displaystyle{ rt \le 5 \; lg \; n = O(rt^*) \; }[/math].
Гиперкуб. Граф G представляет собой гиперкуб с n узлами [10]. Прямой алгоритм маршрутизации в главе 3.4 [6] решает задачу маршрутизации перестановок: вначале он вычисляет хорошие пути для пакетов путем выбора единственного случайного промежуточного узла для каждого пакета; затем строится подходящий план вброса с временем маршрутизации [math]\displaystyle{ rt \lt 14 \; lg \; n }[/math], являющимся оптимальным в наихудшем случае, поскольку существуют перестановки, для которых [math]\displaystyle{ D^* = \Omega (lg \; n) }[/math].
Нижняя граница для буферизации
В главе 5 в [6] рассматривалась также дополнительная задача, касающаяся объема буферизации, необходимого для обеспечения малого времени маршрутизации. Было показано, что существует задача прямого планирования, для которой каждому прямому алгоритму требуется время маршрутизации [math]\displaystyle{ \Omega (C \cdot D) \; }[/math]; в то же время [math]\displaystyle{ C + D = \Theta (\sqrt{C \cdot D} = o(C \cdot D) }[/math]. Если буферизация пакетов допускается, то существуют известные алгоритмы планирования пакетов ([11, 12]) с временем маршрутизации, очень близким к оптимальному [math]\displaystyle{ O(C + D) \; }[/math]. В [6] было показано, что в случае конкретной задачи планирования пакетов для того, чтобы превратить прямой план вброса с временем маршрутизации [math]\displaystyle{ O(C \cdot D) \; }[/math] в план пакетов с временем маршрутизации [math]\displaystyle{ O(C + D) \; }[/math], необходимо выполнять буферизацию пакетов в узлах сети в сумме [math]\displaystyle{ \Omega (N^{4/3}) \; }[/math] раз. Здесь буферизация пакета заключается в хранении пакета в промежуточном буферном узле на протяжении одного временного такта; N – количество пакетов.
Родственные работы
Единственное более раннее исследование алгоритмов прямой маршрутизации относилось к задаче перестановок на деревьях [3, 13]. В этих статьях было получено время маршрутизации O(n) для любого дерева с n вершинами. Это время является оптимальным в наихудшем случае, тогда как результат в [6] является асимптотически оптимальным для всех задач маршрутизации на деревьях.
Сайфер и коллеги [7] изучали онлайн-версию задачи прямой маршрутизации, в которой червь (пакет длины L) может быть повторно передан в случае, если он был брошен (они также допускали пропускную способность каналов равной [math]\displaystyle{ B \ge 1 \; }[/math]). Адлер и коллеги [1] изучали задачу прямой маршрутизации с ограничением по времени, в которой требуется спланировать в рамках заданного интервала времени максимальное количество пакетов. Они показали, что версия этой задачи с ограничением по времени является NP-полной, а также рассмотрели аппроксимационные алгоритмы на деревьях и сотовых сетях. Кроме того, был рассмотрен вопрос, насколько буферизация эффективна в решении этой задачи.
В число других моделей безбуферной маршрутизации входят маршрутизация с сопоставлением [2], при которой пакеты движутся к местам назначения за счет обмена пакетами в смежных узлах, и срочная маршрутизация [4, 5, 8, 9], при которой пакеты следуют по каналам, ведущим их ближе к месту назначения, а если они не могут переместиться ближе из-за конфликтов, они перебрасываются на альтернативные направления.
Применение
Прямая маршрутизация применяется в бесконфликтных протоколах коммуникации, в которых пакеты проводят в сети после вброса минимально возможное время. Этот тип маршрутизации хорошо подходит для сред с ограничениями по мощности или ресурсам – таких как оптические сети, в которых буферизация пакетов слишком дорога, или сенсорные сети с ограниченными энергоресурсами. Прямая маршрутизация также играет важную роль при обеспечении качества обслуживания сетей. Существуют области применения, в которых необходимо гарантировать определенное время доставки пакетов после их вброса в сеть – например, при потоковой трансляции аудио- и видеофайлов. Прямая маршрутизация может применяться в подобных областях.
См. также
Литература
1. Adler, M., Khanna, S., Rajaraman, R., Rosen, A.: Time-constrained scheduling of weighted packets on trees and meshes. Algorithmica 36,123-152 (2003) 2. Alon, N., Chung, F., Graham, R.: Routing permutations on graphs via matching. SIAM J. Discret. Math. 7(3), 513-530 (1994) 3. Alstrup, S., Holm, J., de Lichtenberg, K., Thorup, M.: Direct routing on trees. In: Proceedings of the Ninth Annual ACM-SIAM, Symposium on Discrete Algorithms (SODA 98), pp. 342-349. San Francisco, California, United States (1998) 4. Ben-Dor, A., Halevi, S., Schuster, A.: Potential function analysis of greedy hot-potato routing. Theor. Comput. Syst. 31(1), 41-61 (1998) 5. Busch, C., Herlihy, M., Wattenhofer, R.: Hard-potato routing. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pp. 278-285. Portland, Oregon, United States (2000) 6. Busch, C., Magdon-Ismail, M., Mavronicolas, M., Spirakis, P.: Direct routing: Algorithms and Complexity. Algorithmica 45(1), 45-68 (2006) 7. Cypher, R., Meyer auf der Heide, F., Scheideler, C, Vocking, B.: Universal algorithms for store-and-forward and wormhole routing. In: Proceedings of the 28th ACM Symposium on Theory of Computing, pp. 356-365. Philadelphia, Pennsylvania, USA (1996) 8. Feige, U., Raghavan, P.: Exact analysis of hot-potato routing. In: IEEE (ed.) Proceedings of the 33rd Annual, Symposium on Foundations of Computer Science, pp. 553-562, Pittsburgh (1992) 9. Kaklamanis, C., Krizanc, D., Rao, S.: Hot-potato routing on processor arrays. In: Proceedings of the 5th Annual ACM, Symposium on Parallel Algorithms and Architectures, pp. 273-282, Velen(1993) 10. Leighton, F.T.: Introduction to Parallel Algorithms and Architectures: Arrays - Trees - Hypercubes. Morgan Kaufmann, San Mateo(1992) 11. Leighton, F.T., Maggs, B.M., Rao, S.B.: Packet routing and job-scheduling in O(congestion+dilation) steps. Combinatorica 14,167-186(1994) 12. Leighton, T., Maggs, B., Richa, A.W.: Fast algorithms for finding O(congestion + dilation) packet routing schedules. Combinatorica 19, 375^01 (1999) 13. Symvonis, A.: Routing on trees. Inf. Process. Lett. 57(4), 215-223(1996) 14. Valiant, L.G.: A scheme for fast parallel communication. SIAM J.Comput. 11,350-361 (1982) 15. Valiant, L.G., Brebner, G.J.: Universal schemes for parallel communication. In: Proceedings of the 13th Annual ACM, Symposium on Theory of Computing, pp. 263-277. Milwaukee, Wisconsin, United States (1981)
