Оптимизация входных параметров телекоммуникационных сетей по заданным параметрам

Размещено на http://allbest.ru

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СВЯЗИ, ИНФОРМАТИЗАЦИИ И ТЕЛЕКОММУНИКАЦИИ РЕСПУБЛИКИ УЗБЕКИСТАН

ТАШКЕНТСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

Самостоятельная работа

На тему: Оптимизация входных параметров телекоммуникационных сетей по заданным параметрам

Подготовил: Ибрагимов Галим

Гр. 224-12

Ташкент 2015.

План

Введение

Объект оптимизации

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

Маршрутизация информационных потоков для обеспечения заданного качества обслуживания

Заключение

Список литературы

Введение

При достижении заданного уровня отказоустойчивости функционирования элементов сети телекоммуникаций одной из главных проблем обеспечения гарантированного качества предоставляемых услуг является определение маршрутов, которые удовлетворяли бы QoS-требованиям [1-7].

Однако выбранный самый короткий путь не всегда является оптимальным. На практике гораздо важнее не столько длина телекоммуникационного пути, сколько выбор такого пути, при котором обеспечивались бы заданные пропускные способности каналов при минимальной стоимости передачи единицы потока информации. Одновременно к требованиям обеспечения заданных пропускных способностей и минимальной стоимости передачи информации добавляются требования QoS сетей телекоммуникаций. В такой постановке проблема нахождения оптимального пути между источником и конечным узлом, при котором бы обеспечивалось заданное качество обслуживания и при этом стоимость передачи единицы потока была минимальной, специалистами изучена недостаточно полно.

Даны узлы сети в некоторых географических точках и прогнозируемые потребности (спрос) емкости каналов связи при передаче данных. Также даны множества возможных техно-логий для сетей передачи данных. В условиях ограниченных ресурсов необходимо сделать следующее. Решить, какие узлы связать физическими линиями.

Выбор топологии нужно осуществлять в определенном классе сетей: звездообразных, древовидных, иерархических, т.е. за-фиксировать тип структуры. Необходимо также определить для каждой линии ее тип и пропускную способность. Далее показано, что для решения этой проблемы можно использовать одну математическую модель.

Основное же требование при проектировании сетей телекоммуникаций состоит в следующем: сеть должна быть надежна, иметь низкую стоимость, быть простой в ксплуатации, удовлетворять прогнозные потоки (требования) между конечными узлами, обеспечивать заданное качество предоставляемых услуг (Quality of Service - QoS).

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

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

Выбор параметров сети зависит как от самой сети, так и от целей решаемой задачи - разработки вычислительных алгоритмов и реализующего их программного обеспечения (ПО) с целью численной оценки выходных характеристик качества обслуживания QoS телекоммуникационных сетей в условиях самоподобности речевого трафика в различных сетевых окружениях разработки алгоритмов и ПО численной оптимизации входных параметров ТС с целью обеспечения QoS и оценки влияния самоподобности речевого трафика на параметры качества обслуживания

Объект оптимизации

В качестве конкретного объекта оптимизации выбран участок беспроводного доступа в телекоммуникационной сети .

Возможный вариант состава ТС с асимметричным трафиком для мобильных абонентов движущихся со скоростью до 200 км/час, с участком беспроводной сети доступа в миллиметровом диапазоне, расположенным вдоль автомобильной либо железнодорожной трассы приведен в работе [1].

Беспроводная сеть доступа в рассматриваемом объекте организуется в миллиметровом диапазоне частот. Сигнал поступает на базовые станции (БС) через направленные ответвители (НО) по оптоволоконной линии, соединяющей ретрансляторы (РТР) с базовыми станциями.

Мобильный терминал (МТ) абонента содержит два комплекта оборудования. Один для приема мультимедийных услуг по высокоскоростному каналу в миллиметровом диапазоне частот с одной антенной (либо с несколькими антеннами в случае применения MIMO технологии).

Второй комплект оборудования для организации запросного канала и выполнения ряда интерактивных функций. Перечисленные концептуальные положения построения ИГТС предполагают вариации ряда параметров для оптимизации сети по выбранному критерию.

Такими варьируемыми параметрами могут быть: диапазон частот на участке беспроводного доступа; тип магистрального канала (оптоволоконный либо спутниковый канал); количество «крыльев», а следовательно и количество базовых станций в сегменте сети; ширина полосы рабочих частот приемника мобильного абонента и его эквивалентная шумовая температура входа и т.п.

Различные сочетания перечисленных параметров порождают дискретное множество систем, отвечающих требованиям технического задания. Оптимизация на дискретном множестве указанных систем позволяет при проектировании определить лучшую из систем по заданному критерию

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

Предложена модификация задачи динамического топологического проектирования на макромодели с расширенной системой ограничений финансового характера, адаптированная под цели задач бизнес-планирования и инвестиционного проектирования.

Разработан эвристический алгоритм оптимизации структуры ТС на графо-матричной модели с использованием функций полезности, на тестовых примерах по критерию глубины спуска превзошедший сравниваемые аналоги.

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

Пусть V есть множество всех узлов проектируемой телекоммуникационной сети, т.е. множество V состоит из узлов логической телекоммуникационной сети (станции, маршрутизаторы, коммутаторы, мосты, хост-системы, внешние сети, средства спутниковой связи и т.д.)

Задан граф требований H=(V, D) [8], содержащий ребро (s, t)€D всякий раз, когда имеется требование для передачи данных между s и t. Для каждого требования (s, t) € D графа H задается положительное число d(s, t) € Z+, которое называется функцией трафика и рассматривается как средний суммарный объем информации между узлами s и t, определенный статистически на основе прогноза роста информационных потоков [8].

В задаче проектирования топологии сети по графу требований H необходимо определить граф топологии G=(V, E) (рис. 1). Можно считать, что множества вершин у обоих графов совпадают. Вершинам графа G соответствуют узлы телекоммуникационной корпоративной сети, а ребрам - множество каналов связи, которые потенциально могут быть использованы (существуют на текущий момент либо могут быть проложены); например, оптоволокно, медные линии, радиоволновые линии, спутниковые каналы и т.д. Если между двумя узлами сети имеется несколько различных линий связи, то они представляются параллельными ребрами, отвечающими разным технологиям: Ethernet, Frame Relay, ISDN, ATM и т.д.

Рис. 1. Постановка задачи

Под пропускной способностью y(e) канала eОE понимаются как возможные физические пропускные способности линий (при использовании выделенных и коммутируемых линий связи для осуществления соединений типа «точка-точка» между узлами сети), так и скорость, на которой может осуществляться подключение к глобальной сети общего пользования.

В информационных сетях каждый канал связи при передаче информации ориентирован: один узел передает информацию, а другой принимает.

Установление линии связи между i и j позволяет передать некоторое количество информации в единицу времени между i и j и такое же количество информации между j и i, если подключение синхронное, и суммарное (от i к j + от j к i) количество информации, если подключение асинхронное.

Различают два случая сформулированной задачи: проектирование топологии и технологии телекоммуникационной сети и модернизация топологии и выбор технологии существующей сети. При этом, как будет показано ниже, существуют математические модели, которые являются общими для обоих случаев. Для этого можно считать, что каждому ребру e графа топологии G изначально приписана начальная пропускная способность C0(e) € Z+, e € E. Она отражает настоящее состояние каналов связи между вершинами, соединенными ребром e. Если на сегодняшний день таких каналов связи нет, то полагаем C0(e)=0.

Пусть каждый канал (s, t)ОE определяется посредством соответствующего весового вектора с компонентами m аддитивных QoS-канальных весов wi(s, t)і 0 для всех 1ЈiЈm [8, 9].

Для аддитивных QoS-параметров вес пути P=n1®n2®…®nh+1, состоящего из h узлов (каналов), равен вектор-сумме весов составляющих его каналов, где n - длина хопа, h - число хопов в пути:

Далее в [1] производится выбор нескольких кратчайших путей от некоторого источника до конечного узла, удовлетворяющих критериям QoS, а затем проводится оптимизация по одному критерию - стоимости.

Отличие данного исследования от результатов, изложенных в [1], состоит в том, что оптимизация выбора пути проводится одновременно по двум критериям - стоимости и обеспечению заданного качества обслуживания, т.е. QoS.

Задачи выбора топологии и технологий телекоммуникационной сети можно классифицировать по следующим признакам пропускных способностей дуг:

- без ограничений на пропускные способности (предполагается, что пропускных способностей стандартных линий связи будет вполне достаточно);

- непрерывные пропускные способности, т.е. ye принимает значения из интервала [Cmin, Сmax];

- дискретные пропускные способности, т.е. ye принимает одно из конечного множества C0, C1,…,Ck;

- кратные пропускные способности, т.е. {C0, kC0, k2C0, k3C 0,…}

В современных технологиях непрерывные пропускные способности редко встречаютсяна практике. Значительно чаще каналы связи имеют дискретные или кратные пропускные способности .

Задано множество технологий Т={ф1,…,фn} (коммутируемая линия, выделенная линия, оптоволоконная линия, подключение к общественной сети).

Каждой технологии фОТ соответствует базисная пропускная способность Cф.

Обозначим через P(u; s, t) множество всех путей из s в t (u показывает операционное состояние сети, при u=0 все узлы и ребра являются работоспособными) в графе G=(V, E).

Конкретный путь Р из P(0; s, t), содержащий ребро e (или вершину u), обозначим Р€P(0; s, t):eР, u€Р.

Пусть f(0; s, t; P) - величина потока типа (s, t) вдоль пути Р€P(0; s, t).

По аналогии с [7] введем понятие стоимости передачи единицы потока по пути РОP(0; s, t) для требования (s, t) как

где K(s, t; e) - стоимость передачи по дуге e единицы информации.

В работе задача проектирования оптимальной телекоммуникационной сети представлена в виде следующей модели:

В выражении (3) оптимизация производится по критерию стоимости. Запишем задачу оптимизации по критериям стоимости с учетом обеспечения QoS. Введем функцию Fi(s, t), которая характеризует длину пути и зависит от m ограничений Li, где Li есть ограничения, обеспечивающие заданное качество обслуживания: полосу пропускания, время ответа конечных узлов, вариации времени ответа, количество потерянных пакетов. В данном случае m=4. Необходимо отметить, что перечень ограничений, обеспечивающих заданный уровень качества обслуживания, может быть расширен и дополнен.

Итак,

По аналогии с [8] используя Fi(s, t), задача выбора оптимальной топологии по критериям стоимости и QoS для дискретных пропускных способностей может быть представлена в виде следующей задачи целочисленного линейного программирования:

Предполагается, что каждое ребро e € E графа топологии уже оборудовано начальной пропускной способностью С0(e) (возможно С0(e)=0), которая называется исходной пропускной способностью.

Так как предполагается, что пропускная способность C0(e) установлена изначально, то полагается x0(e)=1.

Выбор пропускной способности Cф(e), 0€ ф € t(e) для ребра эквивалентен тому, что x0(e)=x1(e)=…=xф (e)=1 и xф+1 (e)=…=xф(e)(e)=0.

Задача выбора оптимальной топологии сети по критериям стоимости и QoS для кратных пропускных способностей каналов связи аналогично может быть представлена в виде следующей задачи линейного программирования:

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

Маршрутизация информационных потоков для обеспечения заданного качества обслуживания

Задача маршрутизации будет сформулирована как задача о мультипотоках в сети c дискретными или кратными пропускными способностями y(e).

Мультипотоком в сети G называется множество неотрицательных чисел [8];

поставленных в соответствие для каждого требования (s, t) каждой дуге e и удовлетворяющих следующим линейным ограничениям (уравнения баланса мультипотока):

Первая сумма берется по дугам e, ведущим в узел v, а вторая сумма - по дугам e, ведущим из узла v. Вектор (Z: (s, t)ОD) называется величиной мультипотока.

Также необходимо добавить ограничения на пропускные способности ребер (для синхронных технологий):

или ограничения на пропускные способности дуг (для асинхронных технологий): которые выражают тот факт, что суммарная величина потоков всех типов в обоих направлениях по любому ребру не может превосходить пропускной способности этого ребра.

Для маршрутизации по критериям QoS к вышеописанным функциям необходимо также

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

Пакеты выстраиваются в очередь, формируемую буфером маршрутизатора. Очень важным является закон обслуживания поступающих заявок. Описание очереди в системе с задержками передачи данных возможно упростить при использовании модели M/M/l. Как следует из формулы Клейнрока для средней задержки пакета [9, 10], ограничения должны быть следующими:

где: Tmax(s,t) - максимально допустимая задержка;

1/m - средняя длина пакета (биты/пакет);

Pe - задержка передачи пакета по дуге e;

Ke - задержка связанная с обработкой пакета в узлах дуги e;

T- полный трафик в сети (пакеты/секунда).

Существуют способы определения максимально возможной задержки. Как один из вариантов, возможно определить задержку эмпирически. Например, соответствующую требованиям какого-либо приложения. В [11] предложены алгоритмы определения максимальной задержки каждого маршрута, состоящего из любых дуг, а также сети в целом.

Представленная функция могла быть более сложной и включать кроме задержек и другие требования QoS например, стоимость задержки для каждой ссылки дуги e [11]:

где KT(s,t,e) - стоимость задержки для дуги, принадлежащей (s,t),

b - стоимостной коэффициент.

маршрутизация трафик информационный

Заключение

Представлена оптимизация выбора топологии сетей телекоммуникаций для маршрутизации информационных потоков с учетом требований обеспечения функциональности, минимальной стоимости передачи информации и заданного качества обслуживания.

Разработанные модели отличаются от известных (например, представленных в [1]) тем, что при выборе оптимального пути с точки зрения минимальной стоимости единицы передаваемой информации учитывается также требование обеспечения заданного качества обслуживания

Полученные результаты в виде задач и моделей в совокупности составляют теоретическую основу для дальнейшего развития теории моделирования и оптимизации сетей и систем, разработки оптимальной структуры сетей телекоммуникаций. Обеспечение необходимого качества обслуживания в компьютерных сетях может быть достигнуто путем выбора соответствующего пути между узлами. При этом сам путь не обязательно должен быть самым коротким в терминах длины. Более важным является обеспечение необходимого качества обслуживания, т.е. выполнение условия (1), при минимальной стоимости передачи единицы информации (3.

Нестандартно и более широко в системотехническом плане трактуется принцип оптимальности задачи оптимизации структуры ТС, смысл которого состоит в том, что этапу "внутреннего" проектирования сети должен предшествовать этап "внешнего" проектирования, связанный с согласованием исходных данных. Пренебрежение последним на практике оборачивается образованием "узких" мест сети, недоиспользованием сетевых ресурсов и узкой областью работоспособности ТС, установить которые с помощью эвристических алгоритмов оптимизации весьма трудно

Список литературы

1. Stoica H.Lira // In proc. of NOSSDAV'98. 1998. P. 167-203.

2. Floyd S. // IEEE ACM transactions on networking. 1995. Vol. 3, №4. P. 365-386.

3. Floyd S. // IEEE ACM transactions on networking. 1993. Vol. 1, №4. P. 397-413.

4. Mieghem P. // Computer Networks. 2001. Vol. 37, №3-4. P. 407-423.

5. Листопад Н.И. Моделирование и оптимизация глобальных сетей. Минск, 2000.

6. Quality of Service Routing [Electronic resource]. Mode of access:

www.nas.its.tudelft.nl/people/Piet/papers/chap2qosroutingfinal.pdf.

7. Girlich E., Kovalev M.M., Listopad N.I. Optimal choice of the capacities of telecommunication networks to pro-

vide QoS-Routing. 2009. №21. P. 14.

8. Resende M., Pardalos P. // Springer Science-t-Business Media. 2006. P. 1134.

Библиотека

9. http://tekhnosfera.com/razrabotka-sistemy-matematicheskogo-modelirovaniya-vychislitelnyh-i-telekommunikatsionnyh-setey

10. http://tekhnosfera.com/vliyanie-samopodobnosti-rechevogo-trafika-na-kachestvo-obsluzhivaniya-v-telekommunikatsionnyh-setyah

Размещено на Allbest.ru