Некоторые задачи планирования сети магистрального оператора Бутурлин И.А. Российский Университет Дружбы Народов

2 Содержание 1.Задача расчета матрицы трафика 2.Задача планирования первичной сети 3.Задача расчета OSPF-метрик по заданной маршрутизации

Определение 3 Опр. Матрица трафика, где – объем трафика, передаваемого между парой узлов. Матрица трафика может быть представлена в виде вектора. Выделяют следующие типы матрицы трафика Для сети с 20 POP, 500 маршрутизаторами и 3000 звеньями

Цель: Получить матрицу трафика, используя данные по сети, которые легко измерить Задача: Оценить матрицу трафика, используя данные из SNMP по загрузкам звеньев сети Обозначим: – маршрутная матрица – искомая матрица трафика, представленная в виде вектора – вектор нагрузок на звенья сети Сложность задачи: - узлов в сети - загрузок звеньев (известно) - запросов (неизвестно) - Необходимо учитывать дополнительную информацию по сети Множество алгоритмов решения: - Гравитационная модель (самый простой, пропорция) - Iterative Proportional Fitting ( Kruithofs Projection) - Maximum Likelihood Estimation - Entropy maximization - Bayesian statistics (model prior knowledge ) - и т.д. Постановка задачи 4 (1)

5 Постановка задачи (пример) Множество решений:Дополнительная информация: Например, «гравитационная» модель – каждый источник посылает некоторый процент трафика определенному получателю, равный доле суммарного трафика потребляемая этим получателем. Пусть, суммарный трафик из источник 1 составляет 50 Мбит/с. Получатель 2 потребляет 2% всего трафика, получатель 3 - 8%. Тогда Итоговое решение :

Эволюция методов расчета 6 NetFlow, RSVP, LDP, Layer 2,... Высокая вычислительная сложность для достижения точных оценок Множество решений основанных на статистике по звеньям (в том числе Tomogravity метод ). Получаемая матрица трафика не является точной, но достаточной для планирования сети. Методы основанные на статистике по звеньям сети (SNMP, …) используются как стандарт (надежный, доступный). В алгоритмах используются регрессионные методы для корректировки данных, в соответствии с полученной статисткой по загруженности звеньев сети.

Методы расчета Линейное программирование 7 1. Использование методов оптимизации для поиска оптимального решения для различных вариантов целевой функции и ограничивающих условий (множество решений (1) является бесконечным). При этом дополнительная информация по сети (например, статистика по загруженности звеньев), служит в качестве ограничений, что существенно повышает точность решения. Пример. [1] O. Goldschmidt. ISP Backbone Traffic Inference Methods to Support Traffic Engineering. In Internet Statistics and Metrics Analysis (ISMA) Workshop, San Diego, CA, December множество потенциальных запросов - множество интерфейсов - требуемая ШПП для запроса - доля трафика запроса для интерфейса - измеренная нагрузка для интерфейса

Методы расчета Метод Tomogravity 8 Шаг 1. На первом этапе рассчитываются начальные значения матрицы трафика,используя гравитационный метод (пропорция). Шаг 2. Шаг 3. [2] Y. Zhang, M. Roughan, N. Duffeld, and A. Greenberg, Fast accurate computation of large-scale IP traffic matrices from link loads, ACM SIGMETRICS, San Diego, USA, June задача линейного программирования

Методы расчета Статистические методы (идея) 9

Задача оптимизации затрат при планировании первичной сети (1) 10 Матрица «достижимости»*: Что есть DWDM (Dense Wavelength-Division Multiplexing) мультиплексирование с разделением по длине волны X км

Задача оптимизации затрат при планировании первичной сети (2) 1 Постановка задачи Дано: -Требования по IP-трафику -Матрица достижимости, топология сети -Текущая нагрузка на сеть (порты) -Список оборудования и его стоимость Необходимо минимизировать затраты на необходимое умощнение сети, при этом маршруты должны быть минимальной длины и максимально задействованы.

12 Задача расчета OSPF-метрик по заданной маршрутизации Дано: - Новая маршрутная матрица (DORA,MIRA,…) - Старая маршрутизация – OSPF метрика (веса) Необходимо использовать новую маршрутизацию, используя OSPF метрику