Скачать 

М.Н. Калимолдаев, Г.Е. Тулемисова

Институт проблем информатики и управления МОН РК  

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

______________________________________

Калимолдаев М.Н., Тулемисова Г.Е.
ИНТЕГРАЛЬДЫ ҚЫЗМЕТ КӨРСЕТУ ЖЕЛІЛЕРІНІҢ АҚПАРАТТЫҚ АҒЫМЫН БЕЙІМДІ МАРШРУТТАУДЫҢ МАТЕМАТИКАЛЫҚ МОДЕЛІ 

Мақалада топология желісінің өзгерістеріне шапшаң назар аудару қабілеті бар бейімдеу бағдарының мәселелері қарастырылады. Бейімдеу бағдары — бағдарлау алгоритмінің негізгі түрі екенін біле отырып, бағдарлау мен иерархиялық аймақтық дербестендіру қағидасы бойынша бағдарлау аймағын бөлудің формальды әдісі ұсынылды. Бұл интегралды қызмет көрсету желісіндегі  ағын көлемін басқару мен бағдарлаудың мәселелерін шешудің жолы болуы мүмкін. Қызметтік ақпараттар санын азайту мақсатымен  аймақтық дербестік пен аймақтық қызметтік ақпарат жіберуді тиімді пайдалану ұсынылады. Бұл қызметтік трафикті азайтуға және кейбір жолдарды ұзартудың есебінен ИҚЖ-ның өндірісін арттыруға мүмкіндік береді.
Кілт сөздер: интегралды кызмет көрсету желілері (ИҚЖ), бейімдеу бағдары, аймақтарды дербестендіру,  аймақтық тарату.

______________________________________

Kalimoldayev M. N., Tulemisova G. Y.
A MATHEMATICAL MODEL OF ADAPTIVE ROUTING OF INFORMATION FLOW OF THE INTEGRATED SERVICES NETWORKS

The paper addresses the issue of adaptive routing with its ability to react quickly to changes in network topology. Knowing that the adaptive routing is the main form of routing algorithms we proposes formal method for isolating zones on the principle of hierarchical routing zonal addressing and routing. Possibly, this is a solution of the routing problem and flow control in integrated services networks. To reduce the amount of overhead information we propose to rationally apply, in addition to addressing the zonal, zonal newsletter service information. This will reduce the service traffic and increase the performance of SPI due to some elongation of the tract routing. 
Key words: Network Integrated Services (NIS), adaptive routing, zone addressing, zonal distribution. 

     Как известно, в информационных сетях выделяют 2 метода управления: централизованный и децентрализованный. При централизованном управлении необходимая служебная информация о состоянии сети собирается в центральном управляющем узле (ЦУУ) от всех УК, а обратно, т.е. к УК, рассылаются соответствующие команды. Децентрализованное (распределенное) управление является локальным, т.е. реализуется непосредственно на каждом УК.

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

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

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

1. Разработка аналитической модели вычисления оптимальных значений вероятностно – временных характеристик качества обслуживания   ISDN.

2. Построение квазистатического распределенного алгоритма решение исходной задачи.

Для осуществления первого этапа исследуются следующие вопросы:

• анализ подсети КК с обходными направлениями;
• анализ подсети КК с ожиданием;
• математическая постановка исходной задачи;
• получение аналитического решения задачи;
• анализ полученного решения.

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

• разработка алгоритма решения;
• исследование сходимости алгоритма;
• реализация алгоритма.

Ранее мы рассматривали вопросы разработки аналитической модели вычисления оптимальных значений вероятностно – временных характеристик качества обслуживания   ISDN[my].

 Данная статья посвящена построение квазистатического распределенного алгоритма решение вышеназванной задачи. Проблемами совершенствования адаптивных алгоритмов маршрутизации в вычислительных сетях занимались такие авторы, как Д. Бертсекас, Д. Гарсиа-Диас, П. Гупта, А.Б. Гольдштейн, Б.С. Гольдштейн, Д. Кантор, О.Я.Кравец, Д.В. Куракин, И.П. Норенков, А. Филипс, С. Флойд, Р. Форд, Д. Фулкерсон ,Л. Беллман, Г. Габов, С. Гудман, Е. Дейкстра, В.А. Евстигнеев, В.Н. Касьянов, Р. Сэджвик, Р. Тарьян, С. Флойд, Р. Форд, Д. Фулкерсон и другие.

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

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

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

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

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

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

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

Возможным решением проблемы маршрутизации и управления объемом потоков в СИО является применение принципа иерархической  зоновой     адресации  и  маршрутизации   [1].

До настоящего времени  не  решены вопросы выделения  зон маршрутизации, поэтому рассмотрим возможность решения этой задачи   применительно   к   СИО.   Иерархическая   адресация   заключается  в m-уровневом  разбиении  множества   узлов коммутации (УК),  базирующемся на определении расстояния между узлами в некоторой метрике. Разбиение состоит в группировании узлы коммутации  сети (зон 0-го уровня) в зоны первого уровня, в которых выбираются «центральные» УК (узлы, через которые будет производиться обмен информацией с вышестоящими уровнями). Центральные УК вместе с  каналами связи, их соединяющими, образуют подсеть 2-го уровня. Затем подсеть 2-го уровня делится на зоны 2-го уровня и так далее до тех пор, пока не будет образована подсеть (зона) m-го уровня. Назначение УК зонам на различных уровнях может быть выполнено при использовании различных методов разбиения графов  [2].

Литература

1  Воронкин Е.А. Советов Б.Я., Яковлев С.А. Оценка эффективности информационно-управляющей системы интегральной сети связи//Применение теории информации для повышения эффективности и качества сложных радиоэлектронных систем: Тез. докл. Всес. науч.-техн. конф. М.: Радио и связь, 1984.-с.44-45.

2.  арари Ф. Теория графов. М.: Мир, 1973.-300с.

3   Воронкин Е.А., Яковлев С.А. Решение задачи маршрутизации в интегральных сетях обмена информацией//Вычислительные сети коммутации пакетов. Тез. докл. 3-й Всес. конф. – Рига: ИЭ и ВТ АН Латв. ССР, 1983.- С.15-16.

4   Кулябов Д. С., Королькова А. В. Архитектура и принципы построения современных сетей и систем телекоммуникаций: Учеб. пособие. — М.: РУДН, 2008. — 281 с.: ил.

5  В.И.Басов, Г.И. Загарий, В.Н.Самсонкин, Ю.Н.Терещенко/Цифровые интегральные сети связи./под ред. Ю.Н.Терещенко. Харьков, КФИ «Транспорт Украины» — 2000.-168 с.

6  Замятин Н.В. Цифровые сети интегрального обслуживания. Учебное пособие. Томск.: ЦДО, 2002.-60с

7 Лазарев В.Г., Паршенков Н.Я., Кошелев В.Н. Методы адаптивного управления потоками на интегральных сетях связи// Распределенные системы передачи и обработки информации. М., 1985.-С.52-61.