Моделирование алгоритма маршрутизации

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

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

Полоса пропускания относится к имеющейся мощности трафика какого-либо канала. При прочих равных показателях, канал Ethernet 10 Mbps предпочтителен любой арендованной линии с полосой пропускания 64 Кбайт/сек. Хотя полоса пропускания является оценкой максимально достижимой пропускной способности канала, маршруты, проходящие через каналы с большей полосой пропускания, не обязательно будут лучше маршрутов, проходящих через менее быстродействующие каналы.

 

1.4 Классификация методов маршрутизации вызовов

На междугородных телефонных сетях общего пользования (ТфОП) можно выделить два основных класса методов маршрутизации вызовов: альтернативные (фиксированные) и адаптивные (динамические).

Методы фиксированной маршрутизации были широко распространены на междугородных телефонных сетях до конца 70-х годов. Сети того времени характеризовались следующими особенностями:

- иерархической  структурой построения;

- электромеханическим  коммутационным оборудованием;

- аналоговой  каналообразующей аппаратурой;

- распределенной  системой планирования и управления  сетью.

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

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

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

 В  свою очередь можно выделить  два вида методов динамической  маршрутизации: детерминированные  и статистические.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 1.1 – Методы маршрутизации на междугородней телефонной

сети

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

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

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

 

 

 

 

 

 

1.4.1 Фиксированная маршрутизация

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

- иерархической  структурой сети;

- наличием, в основном, аналоговых систем  передачи;

- малым  числом АМТС с управлением  по записанной программе;

-отсутствием средств управления потоками вызовов в реальном масштабе времени;

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

 

 

1.4.2 Методы детерминированной маршрутизации

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

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

- изменение таблиц маршрутизации базируется на измерениях нагрузки на сети и производится автоматически;

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

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

 

 

1.4.3 Групповой метод динамической статистической маршрутизации

В середине 80-х годов компания АТ&Т произвела серьезные изменения в маршрутизации на междугородной сети США, что означало отход т альтернативного метода. На сети был внедрен метод динамической маршрутизации DNHR (Dynamic Nonhierarchical Routing), относящийся к классу групповых статистических методов.

Наиболее важный элемент концепции DNHR- отказ от иерархических связей между станциями. Число коммутируемых участков на обходном направлении было ограничено двумя.(рисунок 1.2)

Рисунок 1.2 – Коммутируемые участки

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

Рисунок 1.3 – Потоки данных между подсистемами DNHR

На рисунке 1.3 приведены потоки данных между подсистемами DNHR. Опыт эксплуатации сети с DNHR показал, что для полномасштабной национальной сети AT&T, состоящей из из более 100 телефонных станций, экономия средств составила приблизительно 14...16 процентов по сравнению с фиксированной маршрутизацией.

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

Другая особенность системы управления сетью – возможность эмулировать работу оператора, используя базу знаний. Эта технология первоначально была опробавана в экспертной системе управления сетью NEMESYS.

В NEMESYS применяется база знаний, созданная на основе навыков экспертов в области управления сетью для разрешения сетевых проблем. Применение систем на основе базы знаний представляет собой решающий шаг в направлении к полной автоматизации операции управления нагрузкой. Однока использование подобных систем часто сталкивается с недостатком знаний в базе знаний, необходимых в необычных непредсказуемых ситуациях. Для этого в экспертной системе встроены системы накопления знаний для анализа и обучения поведению в новых ситуациях.

1.4.4 Разовый метод динамической статистической маршрутизации

Внедрение новйх принципов коммутации передачи резкоувеличило объем доступной информации о сети, требуемой для осуществления функций контроля и управления. Это сделало возможным внедрением самых сложныхметодов маршрутизации – разовых методов адаптивной маршрутизации. Пример таких методов – метод DAR (Dynamic Alternate Routing), основанный на прогнозе нагрузки.

Метод базируется на следующих положениях:

- маршрутизация ограничена двумя коммутируемыми участками;

- введено состояние защиты;

- новые вызовы в первую очередь направляются на прямые пути;

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

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

Состояние защиты (или уровень резерва) существует для того, чтобы защитить вызовы, обслуживаемые по прямому пути, от блокировки вследствие вызовов, поступивших с перегруженных направлений. Уровень резерва достигается установкой индивидуального порога для каждого направления. Когда число каналов превысит этот порог, вызов, идущий по альтернативному маршруту, не будет пропущен по данному направлению.

Схема может быть расширена путем использования:

- циклического порядка для выбора транзитного узла;

- нестандартного алгоритма выбора транзитного узла на первом этапе принятия решения;

- нового параметра. Если нагрузка на направлении превысит введенный параметр, то до поступления отказа в соединении по прямому пути, выбирается новый транзитный узел. Иными словами, выбор нового транзитного узла должен происходить до блокировки вызова, позволяя тем самым получить более высокую производительность;

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

 

1.4.5 Групповой метод динамической детерминированной маршрутизации по остаточной емкости

Из всех методов маршрутизации, используемых или предполагаемых к применению на сети, разовый метод динамической детерминированной маршрутизации по остаточной емкости RCAR (Residual Capacity Routing) нуждается в наибольшем объеме информации для принятия решения по маршрутизации: здесь используется преиодически обновляемая информация о состоянии каналов на всех участках сети.

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

Рисунок 1.4 – Двухуровневая сеть

Благодаря адаптивному характеру маршрутизации, для сбора необходимой информации возможно использование ОКС7 или другой системы, способной взять на себя эти функции.

Внедренная технология, первоначально названная высокопроизводительной маршрутизацией HPR (High – Performance Routing), известна под названием динамической маршрутизации вызовов DCR (Dynamic Call Routing). Суть метода состоит в том, что поступающие вызовы направляются по путям, на которых ожидается наибольшее число свободных каналов.

 

1.4.6 Разовый метод динамической детерминированной маршрутизации по наименьшей нагрузке LBR (Least Busy Routing)

Был разработан на замену метода DNHR для междугородней телефонной сети.

Основные методы положения метода LBR:

- альтернативная маршрутизация ограничена только одним транзитом;

- введено состояние защиты;

- новые вызовы в первую очередь предлагаются на прямые пути;

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