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

маршрутизации

и 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%.
Тогда

Итоговое решение :

достижения точных оценок

Множество решений основанных на статистике по звеньям (в том числе Tomogravity метод).

Получаемая матрица трафика не является точной, но достаточной для планирования сети.

Методы основанные на статистике по звеньям сети (SNMP, …) используются как стандарт (надежный, доступный).
В алгоритмах используются регрессионные методы для корректировки данных, в соответствии с полученной статисткой по загруженности звеньев сети.

различных вариантов целевой функции и ограничивающих условий (множество решений (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.

- множество потенциальных запросов

- множество интерфейсов

- требуемая ШПП для запроса

- доля трафика запроса для интерфейса

- измеренная нагрузка для интерфейса

?

трафика ,используя гравитационный метод (пропорция).


Шаг 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.

- задача линейного программирования

(Dense Wavelength-Division Multiplexing)
мультиплексирование с разделением по длине волны

X км

IP-трафику
Матрица достижимости, топология сети
Текущая нагрузка на сеть (порты)
Список оборудования и его стоимость

Необходимо минимизировать затраты на необходимое умощнение сети, при этом маршруты должны быть минимальной длины и максимально задействованы.

маршрутизация – OSPF метрика (веса)

Необходимо использовать новую маршрутизацию, используя OSPF метрику