Некоторые задачи планирования сети магистрального оператора

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

Определение
Выделяют следующие типы матрицы трафика
Для сети с 20 POP, 500 маршрутизаторами и 3000 звеньями

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

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

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

Методы расчета
Линейное программирование
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 2000.
- множество потенциальных запросов
- множество интерфейсов
- требуемая ШПП для запроса
- доля трафика запроса для интерфейса
- измеренная нагрузка для интерфейса
?

Методы расчета
Метод Tomogravity
Шаг 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 2003.
- задача линейного программирования

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

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

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