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

Содержание

Введение

1. Анализ методов маршрутизации вызовов на междугородней сети общего пользования

1.1 Современные тенденции развития электросвязи

1.2 Маркетинговое исследование

1.3 Маршрутизация в сети

1.3.1 Типы алгоритмов

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

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

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

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

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

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

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

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

1.4.8 Сравнительный анализ алгоритмов детерминированной маршрутизации

1.5 Существующая междугородняя сеть Республики Казахстан

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

2.1 Построение модели

2.2 Процесс установления соединения на междугородней телефонной сети

2.3 Два варианта модели прямого пучка каналов МТС

3. Расчет уточненной модели прямого пучка междугородной телефонной сети

3.1 Базовая модель

3.2 Приближенный алгоритм расчета модели, основанный на использовании формулы Эрланга

3.3 Преобразование модели полнодоступного пучка простейшего типа

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

4.1 Модель сети связи

4.2 Задача распределения потока

4.3 Метод отклонения потока

4.3.1 Алгоритм Флойда отыскания множества кратчайших путей

4.3.2 Оптимальный алгоритм отыскания потока для выбора маршрутов

4.3.3 Алгоритм отыскания реализуемого начального потока

Приложения

Введение

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

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

Стратегическими направлениями отрасли определены:

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

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

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

1. Анализ методов маршрутизации вызовов на междугородней сети общего пользования

1.1 Современные тенденции развития электросвязи

Связь развивалась по пути цифровизации всех видов информации. Это стало генеральным направлением, обеспечивающим экономичные методы не только ее передачи, но и распределения, хранения и обработки. Вслед за ИКМ-24 появляются ИКМ-30, ИКМ-120, ИКМ-480, ИКМ-1920, а затем системы передачи синхронной цифровой иерархии (СЦИ).

Интенсивное развитие цифровых систем передачи объясняется существенными достоинствами этих систем по сравнению с аналоговыми системами передачи: высокой помехоустойчивостью; слабой зависимостью качества передачи от длины линии связи; стабильностью электрических параметров каналов связи; эффективностью использования пропускной способности при передаче дискретных сообщений и др.

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

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

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

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

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

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

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

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

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

1.2 Маркетинговое исследование

маршрутизация вызов телефонный алгоритм

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

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

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

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

Общая рыночная сегментация услуг электросвязи осуществляется по трём основным сегментам предоставления услуг связи:

- местной телефонной;

- международной телефонной;

- подвижной.

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

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

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

1.3 Маршрутизация в сети

В общедоступном значении слова маршрутизация означает передвижение информации от источника к пункту назначения через объединенную сеть. При этом, как правило, на пути встречается по крайней мере один узел. Маршрутизация часто противопоставляется объединению сетей с помощью моста, которое, в популярном понимании этого способа, выполняет точно такие же функции. Основное различие между ними заключается в том, что объединение с помощью моста имеет место на Уровне 2 эталонной модели ISO, в то время как маршрутизация встречается на Уровне 3. Этой разницей объясняется то, что маршрутизация и объединение по мостовой схеме используют различную информацию в процессе ее перемещения от источника к месту назначения. Результатом этого является то, что маршрутизация и объединение с помощью моста выполняют свои задачи разными способами; фактически, имеется несколько различных видов маршрутизации и объединения с помощью мостов.

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

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

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

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

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

Таблица 1.1 - Таблица маршрутизации

To reach network:	Send to:
27	Node A
57	Node B
17	Node C
24	Node A
52	Node A
16	Node B
26	Node A

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

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

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

Цели разработки алгоритмов маршрутизации.

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

- оптимальность;

- простота и низкие производительные затраты;

- живучесть и стабильность;

- быстрая сходимость;

- гибкость.

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

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

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

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

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

1.3.1 Типы алгоритмов

Алгоритмы маршрутизации могут быть классифицированы по типам. Например, алгоритмы могут быть:

- статическими или динамическими;

- одномаршрутными или многомаршрутными;

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

- с интеллектом в главной вычислительной машине или роутере;

- внутридоменными и междоменными;

- алгоритмами состояния канала или вектора расстояний.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- длина маршрута;

- надежность;

- задержка;

- ширина полоса пропускания;

- нагрузка;

- стоимость связи.

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

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

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

Полоса пропускания относится к имеющейся мощности трафика какого-либо канала. При прочих равных показателях, канал 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:

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

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

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

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

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

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

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

Суть предлагаемого метода состоит в следующем:

- количество прямых направлений АМТС - АМТС сведено к минимуму;

- каждая АМТС опирается как минимум на два транзитных узла;

- в случае отказа в соединении на каком - либо участке процедура обработки вызова возвращается к исходящей АМТС и пробуется следующий транзитный узел и так далее.

1.4.8 Сравнительный анализ алгоритмов детерминированной маршрутизации

Для сравнения методов детерминированной маршрутизации авторами было проведено исследование их эффективности. В качестве объекта выбран класс разовых динамических методов маршрутизации. Его обобщенный алгоритм приведен в приложении Б. Из алгоритма видно, что все эти методы сходны между собой и различаются только способами выбора ТУ. Уровень резерва обычно выбирают равным 2...3 процента от общего количества каналов на направлении.

Отличие методов состоит в объеме информации, необходимой для принятия решения по маршрутизации. Максимальное количество данных требуют методы DCR и LBR. Следовательно, для их применения необходимо иметь систему сбора информации, которая в полном объеме предоставляет данные о состоянии всех каналов на сети. Напротив, метод DAR не требует такого количества информации. Решение принимается сначала на базе прогноза, а далее случайным образом. Таким образом, в системе DAR текущая информация запрашивается только системой прогнозирования.

Сравнение методов детерминированной маршрутизации для не иерархической сети было проведено методом имитационного моделирования на модели со следующими параметрами:

- полносвязная симметричная иерархическая сеть с 5, 10 и 15 узлами;

- все каналы на сети - двунаправленные и цифровые;

- информация о состоянии сети собирается каждые 10 секунд;

- уровень защиты - 3 процента;

- пуассоновское распределение потоков поступающих вызовов;

- интенсивность нагрузки на каждом направлении - 45 Эрланг.

На рисунке 1.5 приведены полученные кривые эффективности алгоритмов ДМ и ее изменение в случае возникновения перегрузок на сети. Анализ результатов показывает, что алгоритм LBR - наилучший по параметру потерь, а DAR обладает высокой эффективностью. Изменение эффективности алгоритмов маршрутизации при различном числе узлов на сети показано на рисунке 1.6.

Рисунок 1.6 - Кривая изменения эффективности алгоритмов маршрутизации

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

Выводы:

1 При цифровизации сетей имеет место общая тенденция изменения структуры сети от иерархической к неиерархической и метода маршрутизации - от фиксированного к разовому динамическому.

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

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

1.5 Существующая междугородняя сеть Республики Казахстан

Темпы цифровизации телефонной сети Республики Казахстан, особенно междугородной, превысили самые оптимистические прогнозы. Успехами в телекоммуникационном строительстве республика обязана прежде всего усилиям своего энергичного оператора ОАО "Казахтелеком". Коммутационная сеть междугородней связи на сегодняшний день полностью оснащена цифровыми станциями типа EWSD, AXE-10, Alkatel 1000 S-12. Современная коммутационная техника на междугородней сети позволяет практически полностью автоматизировать междугородный телефонный обмен, резко повысить качество и количество представляемых услуг. Как показывает опыт, переход на следующее поколение АМТС, даже на тех же каналах, позволяет в 1,5 - 2 раза увеличить пропускаемый трафик при повышении качества предоставляемых услуг. Наличие программного обеспечения в цифровых системах коммутации и передачи, внедрение системы сигнализации по ОКС 7 создают предпосылки для автоматизации управления сетью. На сети созданы два Международных центра коммутации (МЦК) в городах Алматы и Астана, что позволило Казахстану перейти на международные принципы организации связи. К МЦК подключены АМТС всех областных центров, МЦК стран СНГ и дальнего зарубежья. В результате жители республики имеют ныне цифровую связь со всем миром.

Концепция управления сетью достаточно глубоко проработана и закреплена в рекомендациях МСЭ-Т серии М под условным названием TMN (Telecommunication Management Network). Одной из функциональных систем TMN является подсистема управления трафиком.

Существующая сеть междугородней телефонной сети республики показана в приложении А.

1.6 Постановка задачи

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

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

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

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

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

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

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

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

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

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

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

Влияние ПВ на качество функционирования АМТС было исследовано сотрудником Ленинградской междугородной станции (ЛМТС) и Института проблем передачи информации АН СССР.

Рассмотрим вопросы, связанные с построением и разработкой методов расчета математической модели прямого пучка каналов ЛМТС, в которой учитывается эффект влияния ряда практических задач - тема отдельной статьи. Материал данной статьи является расширенным вариантом доклада, тезисы которого опубликованы в Трудах 11-го международного конгресса по телетрафику. Из зарубежных разработок наиболее близкими к данному исследованию можно считать работы П. Ле Галля (Франция) и Г. Гостони (Венгрия).

...