Разработка программного обеспечения для оптимизации мультисервисных сетей

Оптимизация дизайна LSP Телекоммуникационная сеть может быть представлена в виде узлов-вершин (системы коммутации, маршрутизации и т. д.) и звеньев-ребер (системы передачи, линия связи и т. д.), которые соединяют узлы-вершины между собой. То есть любую сеть связи можно представить в виде графа и использовать методы теории графов для исследования и оптимизации сетей. При этом сеть может быть сопоставлена с неким направленным, сильно связанным графом с множеством вершин и множеством ребер . Для сети задана матрица требований (трафик-матрица) .

1. 
   Метод максимального потока (минимального разреза) Это метод определяет множество рёбер, при удалении которых сеть делится на две несвязанные части, а также максимальную нагрузку на это множество ребер. Пропускная способность этих ребер ограничивает объем трафика между двумя частями сети.
   
2. 
   Метод линейного программирования. Одним из способов реализации линейного программирования является симплекс-алгоритм, который может почти всегда, за исключением некоторых случаев, найти оптимальное решение. В основе этого алгоритма лежит полный перебор возможных вариантов решения задачи.
   
3. 
   Эвристические методы. Данные методы направлены на сокращение перебора. Хотя методы позволяют получить лишь квазиоптимальный дизайн LSP, в некоторых случаях только они являются единственным возможным решением, к тому же эти методы намного быстрее линейного программирования отражают изменения внутренней топологии сети на дизайне.
   

Сравнение алгоритмов оптимизации Существует несколько параметров, по которым можно проводить сравнение алгоритмов оптимизации сетей MPLS. В данном случае сравнение мы будем проводить по сложности алгоритмов и по полученному весу дизайна LSP.

1. 
   Kehang Wu and Douglas S. Reeves Link Dimensioning and LSP Optimization for MPLS Networks Supporting DiffServ EF and BE traffic classes http://reeves.csc.ncsu.edu/papers-and-other-stuff/2003-09-itc18-link-dimensioning-mpls-paper.pdf
   
2. 
   Alpar Juttner, Balazs Szviatovszki,Aron Szentesi, Daniel Orincsay, Janos Harmatos On–demand optimization of label switched paths in MPLS networks IEEE ICCCN 2000
   
3. 
   Ahuja, R.K.; Magnanti, T.L.; Orlin J.B.: Network Flows: Theory, Algorithms and Aplications. Prentice Hall, Englewood Cliffs, 1993
   
4. 
   Christofides, N.: Graph Theoriy- An Algprithmic Approach. New York: Academic Press, 1975
   
5. 
   Neuman, Klaus; Morlock, Martin: Operations Research. München Wien: Carl Hanser Verlag, 1993
   
6. 
   Э. Майника Алгоритмы оптимизации на сетях и графах. M.: 1981г., 323стр.
   
7. 
   http://algolist.manual.ru/maths/graphs/shortpath/ Задача о кратчайших путях.
   
8. 
   http://program.rin.ru/razdel/html/973.html Оценка времени исполнения. Символ O()