Маршрутизация
Маршрутизация (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 = (x, 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].
Применение
С точки зрения применения этих результатов самое важное заключается в том, что с их помощью можно рассчитать наилучшую стратегию маршрутизации для топологии сети с ограничениями на пропускную способность. Это исключительно полезный инструмент для планирования сетей. Используя данные механизмы анализа, эффективность имеющейся топологии можно проверить, не имея информации о трафике в сети.
Многие исследователи изучали различные варианты задач маршрутизации. Обзоры самых значимых моделей и результатов можно найти в работах [10] и [11]. Алгоритмы маршрутизации в отсутствие информации первыми проанализировали Валиант и Бребнер [15]. Они рассматривали модель параллельного компьютера и исследовали конкретные архитектуры, такие как гиперкуб, квадратные решетки и т. п. Бородин и Хопкрофт изучали сети общего вида [6]. Они показали, что такие простые детерминированные стратегии, как маршрутизация в отсутствие информации, не могут быть по-настоящему эффективными для онлайновой машрутизации, и доказали нижнюю границу коэффициента конкурентоспособности алгоритмов маршрутизации в отсутствие информации. Эта нижняя граница впоследствии была улучшена Какламанисом и др. [9], они также предложили оптимальный детерминированный алгоритм маршрутизации в отсутствие информации для гиперкуба.
В 2002 году Ракке построил полилогарифмический конкурентный рандомизированный алгоритм для неориентированных сетей общего вида. Точнее говоря, он доказал, что для любого значения спроса существует маршрутизация, такая, что максимальная нагруженность ребра не более чем в polylog(n) раз превышает оптимальную для этого спроса [12]. Азар и др. в своей работе дополнили этот результат, предложив полиномиальный метод для расчета оптимальной маршрутизации в отсутствие информации для сети. Они также доказали, что для ориентированных сетей не существует логарифмического коэффициента эффективности маршрутизации в отсутствие информации. Недавно Хаджиагаи и др. предложили алгоритм маршрутизации в отсутствие информации, являющийся [math]\displaystyle{ O(log^2 n) }[/math]-конкурентным с высокой вероятностью в ориентированных сетях [8].
Специальная онлайновая модель исследовалась в работе [5], авторы которой определили так называемую формулировку «повторяющейся игры», в которой алгоритм может ежедневно выбирать новый маршрут. Это означает, что алгоритм не имеет информации о спросе, который возникнет на следующий день. Авторы представили [math]\displaystyle{ 1 + \varepsilon }[/math]-конкурентный алгоритм для этой модели.
Для адаптивного случая существуют более эффективные алгоритмы, например, представленные в [2]. Рагхаван и Томпсон предложили эффективный алгоритм для оффлайнового случая [13].
Открытые вопросы
В данной статье рассматривалась нагруженность ребер, однако в практическом плане нагруженность вершин может быть не менее интересна. Под нагруженностью вершины понимается отношение общего объема трафика через эту вершину к ее пропускной способности. Некоторые результаты для этой задачи можно найти в работах [7] и [3]. Остается открытым вопрос, можно ли применить для этой модели метод, разработанный для анализа нагруженности ребер. Еще один любопытный нерешенный вопрос заключается в том, существует ли более эффективный алгоритм для вычисления оптимального коэффициента эффективности маршрутизации в отсутствие информации для сети [1, 14].
Экспериментальные результаты
Авторы [4] применили свой метод к топологиям сетей поставщиков услуг Интернета и обнаружили, что полученные оптимальные коэффициенты эффективности для маршрутизации в отсутствие информации на удивление малы – от 1,4 до 2. Другие исследования этого вопроса привели к похожим результатам [1, 14].
См. также
Литература
- Толковый словарь по вычислительным системам. — М.: Машиностроение, 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
