Маршрутизация

Маршрутизация (Routing) — процедура, используемая для определения маршрута пакета в сети с коммутацией пакетов. Маршрутизация может быть постоянной (вычисляемой однажды в начале работы системы или в начале сеанса) или динамической (перевычисляемой периодически или при смене пакетов). Маршрутизация может быть централизованной или распределенной (вычисляемой в различных узлах независимо друг от друга).

Ключевые слова и синонимы

Алгоритмы маршрутизации; сетевые потоки; маршрутизация в отсутствие информации о потребностях в ресурсах

Постановка задачи

Маршрутизация является одной из самых широко используемых техник в современных компьютерных сетях. Под маршрутизацией понимается выбор путей в сети, по которым следует отправлять данные. Спрос обычно возникает случайным образом в некоторых узлах сети, и алгоритмы маршрутизации должны быть способны отправить данные по месту их назначения. Данные пересылаются через промежуточные узлы при помощи соединительных звеньев, учитывая топологию сети. Пользователь ждет от сети гарантии наличия необходимой пропускной способности в процессе передачи данных, что означает, что сеть ведет себя так, словно ее узлы напрямую соединены физическим каналом связи. Подобный сервис носит название постоянного виртуального соединения (permanent virtual circuit, PVC). Для моделирования реальных ситуаций будем предполагать, что спрос возникает в режиме онлайн, задается точкой-источником и точкой-получателем и включает требования к пропускной способности.

Аналогичные задачи маршрутизации возникают в других областях, например, в параллельных вычислениях. В данном случае имеются несколько процессоров, соединенных кабелями. В ходе работы у определенных процессоров появляются некоторые данные, которые должны быть переданы в конкретную точку назначения. В данном случае также требуется решать задачу маршрутизации. Далее будет рассматриваться главным образом сетевая модель, а не модель с параллельными компьютерами.

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

Существуют два фундаментальных подхода к разработке алгоритмов маршрутизации. Первый подход заключается в адаптивной маршрутизации (adaptive routing), учитывающей фактическую загрузку узлов или каналов связи. Второй подход представляет собой маршрутизацию в отсутствие информации (oblivious routing), без использования каких-либо данных о текущем состоянии сети. Далее будет рассматриваться только второй подход.

Нотация и определения

Математическая модель задачи маршрутизации в сети выглядит следующим образом.

Пусть дана сеть с учетом пропускной способности G = (V, E, c), где V– множество вершин, а E – множество дуг с функцией пропускной способности [math]\displaystyle{ c: E \to R^+ }[/math]. Пусть |V| = n, |E| = m. Можно предположить, что сеть G является ориентированной, поскольку в противном случае для каждого неориентированного ребра e = (u, v) можно добавить к графу две новых вершины x, y и четыре новых ориентированных ребра [math]\displaystyle{ e_1 = (u, x), e_2 = (v, x), e_3 = (y, u), e_4 = (y, u) }[/math] с бесконечной пропускной способностью. Если e рассматривается как неориентированное ребро с той же пропускной способностью, то получается ориентированная сеть, эквивалентная исходной.

Определение 1. Множество функций [math]\displaystyle{ f := \{f_{ij} | i, j \in V, f_{ij}: E(G) \to R^+ \} }[/math] называется задачей о многопродуктовом потоке, если соотношение [math]\displaystyle{ \sum_{e \in E^+_k} f_{ij}(e) = \sum_{e \in E^-_k} f_{ij} (e) }[/math] выполняется для всех [math]\displaystyle{ k \ne i, k \ne j }[/math], где [math]\displaystyle{ k \in V }[/math], а [math]\displaystyle{ E^+_k, E^-_k }[/math] – множества ребер, выходящих из k и входящих в k, соответственно. Каждая функция [math]\displaystyle{ f_{ij} }[/math] определяет однопродуктовый поток из i в j.

Определение 2. Значение многопродуктового потока задается матрицей размера n x n [math]\displaystyle{ T_f = (t_{ij}^f) }[/math], где [math]\displaystyle{ t^f_{ij} = \sum_{e \in E^+_i} f_{ij}(e) - \sum_{e \in E^-_i} f_{ij} (e) }[/math], если [math]\displaystyle{ i \ne j }[/math] и [math]\displaystyle{ v^f_{ii} = 0 }[/math] для всех [math]\displaystyle{ i, j \in V }[/math].

Определение 3. Пусть D – неотрицательная матрица размера n х n, диагональные элементы которой равны 0. Матрица D называется матрицей спроса. Поток по ребру [math]\displaystyle{ e \in E }[/math] с маршрутизацией согласно матрице спроса D по маршруту r определяется функцией [math]\displaystyle{ flow(e, r, D)= \sum_{i, j \in V} d_{ij} r_{ij}(e) }[/math], а нагруженность ребра – соотношением [math]\displaystyle{ con(e, r, D) = \frac{flow(e, r, D)}{c(e)} }[/math].

Нагруженность спроса D по маршруту r составляет [math]\displaystyle{ con(r, D) = max_{e \in E} con(e, r, D) }[/math].

Определение 4. Многопродуктовый поток r называется маршрутом, если [math]\displaystyle{ t^r_{ij} = 1 }[/math] и если [math]\displaystyle{ i \ne j }[/math] для всех [math]\displaystyle{ i, j \in V }[/math].

Маршрутизация представляет собой способ передачи информации по сети. Реальная нагрузка ребер может быть представлена при помощи приведения нагруженности ребра к масштабу спроса.

Определение 5. Коэффициент эффективности [math]\displaystyle{ P_r }[/math] маршрутизации r в отсутствие информации равен [math]\displaystyle{ P_r = sup_D \bigg\{ \frac{con(r, D)}{opt(D)} \bigg\} }[/math], где opt(D) – оптимальная нагруженность, которая может быть достигнута для D. Оптимальный коэффициент эффективности маршрутизации в отсутствие информации для сети G обозначается opt(G), где [math]\displaystyle{ opt(G) = min_r P_r }[/math]

Задача

Дано: Сеть с учетом пропускной способности G = (V, E, c).

Требуется: Найти маршрут r в отсутствие информации с минимальным [math]\displaystyle{ P_r }[/math].

Основные результаты

Теорема 1. Существует алгоритм с полиномиальным временем выполнения, который для любой сети G (ориентированной или неориентированной) находит оптимальный коэффициент эффективности маршрутизации в отсутствие информации и соответствующий маршрут r.

Теорема 2. Существует ориентированный граф G с n вершинами, такой, что opt(G) оказывается не менее [math]\displaystyle{ \Omega(\sqrt{n}) }[/math].

Литература

• Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.

1. Applegate, D., Cohen, E.: Making routing robust to changing traffic demands: algorithms and evaluation. IEEE/ACM Trans Netw 14(6), 1193-1206 (2006). doi:10.1109/TNET.2006.886296

2. Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., Waarts, O.: On-line routing of virtual circuits with applications to load balancing and machine scheduling. J. ACM 44(3), 486-504 (1997)

3. Azar, Y., Chaiutin, Y.: Optimal node routing. In: Proceedings ofthe 23rd International Symposium on Theoretical Aspects of Computer Science, 2006, pp. 596-607

4. Azar, Y., Cohen, E., Fiat, A., Kaplan, H. Racke, H.: Optimal oblivious routing in polynomial time. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, 2003, pp. 383-388

5. Bansal, N., Blum, A., Chawla, S.: Meyerson, A.: Online oblivious routing. In: Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms, 2003, pp. 44-49

6. Borodin, A., Hopcroft, J.E.: Routing, merging and sorting on parallel models of computation. J. Comput. Syst. Sci. 30(1), 130-145(1985)

7. Hajiaghayi, M.T., Kleinberg, R.D., Leighton, T., Racke, H.: Oblivious routing on node-capacitated and directed graphs. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, pp. 782-790

8. Hajiaghayi, M.T., Kim, J.H., Leighton, T., Racke, H.: Oblivious routing in directed graphs with random demands. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, pp. 193-201

9. Kaklamanis, C., Krizanc, D., Tsantilas, A.: Tight bounds for oblivious routing in the hypercube. In: Proc. 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, 1990, pp. 31-36

10. Leighton, F.T.: Introduction to Parallel Algorithms and Architectures Arrays,Trees, Hypercubes. Morgan Kaufmann Publishers, San Fransisco (1992)

11. Leonardi, S.: On-line network routing. In: Fiat, A., Woeginger, G. (eds.) Online Algorithms - The State of the Art. Chap. 11, pp. 242-267. Springer, Heidelberg (1998)

12. Racke, H.: Minimizing Congestions in General Networks. In: Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002, pp. 43-52

13. Raghavan, P., Thompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7, 365-374 (1987)

14. Spring, N., Mahajan, R., Wetherall, D.: Measuring ISP topologies with Rocketfuel. In: Proceedings of the ACM SIGCOMM'02 Conference. ACM, New York (2002)

15. Valiant, L.G., Brebner, G.: Universal schemes for parallel communication. In: Proceedings of the 13th ACM Symposium on Theory of Computing, 1981, pp. 263-277