А. В. Тимофеев Санкт-Петербургский институт информатики и автоматизации Российской академии наук

Вид материала

Содержание

1. Эволюция ТКС и интеллектуализация сетевого управления
2.Оптимизация управления трафиком и маршрутизации информационных потоков
3. Модели и методы адаптивной и мульти-агентной маршрутизации

Подобный материал:

ПРИНЦИПЫ ПРОЕКТИРОВАНИЯ КОМПЬЮТЕРНЫХ СЕТЕЙ НОВОГО ПОКОЛЕНИЯ НА БАЗЕ АДАПТИВНОЙ МАРШРУТИЗАЦИИ И МУЛЬТИ-АГЕНТНОГО УПРАВЛЕНИЯ

А.В.Тимофеев

Санкт-Петербургский институт информатики и автоматизации Российской академии наук

Тел.: (812) 328-04-21, e-mail: tav@iias.spb.su

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

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

Альтернативным путём совершенствования сетевого управления потоками данных в глобальных ТКС является его автоматизация на базе динамических моделей ТКС как сложных сетевых объектов управления, методов оптимизации процессов маршрутизации потоков данных и принципов адаптивного и интеллектуального управления трафиком с использованием мульти-агентных технологий и протоколов нового поколения (например, IPv6-протоколов). На этом новом пути возможен как учёт реальной динамики ТКС, т.е. фактического изменения структуры (топологии) и параметров (весов каналов связи) ТКС в реальном времени, так и адаптация к различным факторам неопределённости на основе мониторинга и функциональной диагностики ТКС.

В докладе рассматриваются динамические модели глобальных ТКС с переменной структурой, математические модели, оптимизационные алгоритмы и протоколы динамической, адаптивной, нейросетевой и мульти-агентной маршрутизации потоков данных. Эти модели, методы и протоколы нового поколения являются важной составляющей частью современной теории адаптивного и интеллектуального управления информационными потоками в глобальных ТКС. Они отражают опыт и научный задел, полученные в процессе выполнения в 2002-2004 гг. госконтракта №37.029.0027 на тему “Адаптивными методы управления потоками данных в телекоммуникационных системах нового поколения” Федерального агентства по науке и инновациям в рамках ФЦНТП “Исследования и разработки по приоритетным направлениям развития науки и техники”.

1. Эволюция ТКС и интеллектуализация сетевого управления

Глобализация и другие современные тенденции развития ТКС привели не только к существенному пересмотру основных телекоммуникационных концепций, но и к значительным технологическим сдвигам, а именно [1-3]:

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

С учетом сложившихся тенденций возможны два сценария развития ТКС: революционный и эволюционный. Революционный сценарий заключается в быстрой замене существующего электронного оборудования ТКС оптическими системами с пропускной способностью до тысяч Гбит/с. Реализация этого сценария требует очень больших инвестиций для разработки и массового производства стандартизированных оптических компонентов глобальных ТКС. Эволюционный сценарий развития ТКС основывается на их постепенной модернизации путём совершенствования систем, протоколов и технологий управления передаваемыми информационными потоками. Сегодня реализация этого сценария идет очень быстрыми темпами и приводит к созданию корпоративных и глобальных ТКС новых поколений.

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

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

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

Новые задачи и требования к IP-технологиям привели к широкому использованию четвёртой версии классического протокола (IPv4) и разработке его шестой версии (IPv6), обеспечивающей следующее [1, 2]:

увеличение адресного поля служебной части пакета до 128 бит, что увеличивает количество IP-адресов до 1020 на каждый узел ТКС;
увеличение длины заголовка пакета до 320 бит с локализацией информации, необходимой для работы маршрутизатора;
повышение эффективности за счет агрегирования адресов и фрагментации больших пакетов;
обеспечение безопасности информации за счет аутентификации узлов-источников и узлов-приемников информации, шифрования и поддержания целостности передаваемых данных.

Архитектура глобальной ТКС состоит из четырёх основных (базисных) подсистем [3]:

1. Распределённая система связи (РСС);
2. Сетевая система управления (ССУ);
3. Распределённая информационная система (РИС);
4. Распределённая транспортная система (РТС).

Эти подсистемы связаны между собой и предназначены для управляемой передачи пользователям глобальной ТКС распределённых информационных и вычислительных ресурсов, хранящихся в КС [7-10].

ССУ глобальных ТКС нового поколения должны быть адаптивными и интеллектуальными [3-11], т.е. обладать способностями к:

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

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

2.Оптимизация управления трафиком и маршрутизации информационных потоков

Задача управления трафиком в глобальных ТКС распадается на две взаимосвязанные задачи:

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

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

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

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

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

изменение стоимости каналов связи ТКС (например, при их замене);
отказ (выход из строя) в ТКС одного или нескольких каналов связи;
добавление в ТКС новых каналов связи;
отказ (выход из строя) одного или нескольких узлов ТКС;
добавление в ТКС новых узлов;
перегрузка каналов связи ТКС;
перегрузка (переполнение) буферов узлов ТКС.

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

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

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

3. Модели и методы адаптивной и мульти-агентной маршрутизации

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

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

обеспечивает работоспособность и надежность ССУ при непредсказуемых изменениях их структуры или параметров ТКС;
приводит к более равномерной загрузке узлов и каналов связи ТКС за счет «выравнивания» нагрузки;
упрощает управление передачей потоков данных при сетевых перегрузках;
увеличивает время безотказной работы и производительность ТКС при высоком уровне предоставляемых услуг при непредсказуемых изменениях сетевых параметров и структуры ТКС.

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

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

Модели и принципы адаптивной маршрутизации потоков данных в глобальных ТКС можно разбить на три класса [3, 5-7]:

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

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

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

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

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

Работа выполнена при частичной поддержке гранта РФФИ №03–01–00224а, гранта РГНФ №03–06–12016в и госконтракта Министерства образования и науки РФ №37.029.0027.

Литература

1. Хелеби С., Мак-Ферсон Д. Принципы маршрутизации в Internet. 2-е издание.: Пер. с англ. – М: Издательский дом «Вильямс», 2003. – 448 с.

2. Столлингс В. Современные компьютерные сети. – СПб: Питер, 2003, – 783с.

3. Тимофеев А.В. Проблемы и методы адаптивного управления потоками данных в телекоммуникационных системах. – Информатизация и связь, № 1-2, 2003, с. 68–73.

4. Тимофеев А.В. Методы высококачественного управления, интеллектуализации и функциональной диагностики автоматических систем. – Мехатроника, автоматизация, управление, 2003, № 2, с. 13–17.

5. Syrtzev A.V., Timofeev A.V. Neural and Multi-Agent Routing in Telecommunicational Networks. – International Journal “Information Theories and Their Applications”, 2003 , № 2.

6. Timofeev A.V. Models for Multi-Agent Dialogue and Informational Control in Global Telecommunicational Networks. – International Journal “Information Theories and Their Applications”, 2003, № 1.

7.Тимофеев А.В. Архитектура и принципы построения мульти-агентных телекоммуникационных систем нового поколения. – Труды 11-ой Всероссийской научно-методической конференции “Телематика–2004” (Санкт-Петербург, 7–10 июня 2004 г.), том 1, с. 172–174.

8.Тимофеев А.В., Остюченко И.В. Мульти-агентное управление качеством в телекоммуникационных сетях. – Труды 11-ой Всероссийской научно-методической конференции “Телематика–2004” (Санкт-Петербург, 7–10 июня 2004 г.), том 1, с. 177–179.

9. Timofeev A.V. Multi-Agent Information Processing and Adaptive Control in Global Telecommunication and Computer Networks. – International Journal “Information Theories and Their Applications”, 2003, № 10, pp. 54–60.

10. Timofeev A.V. Intellectualization for Man-Machine Interface and Network Control in Multi-Agent Infotelecommunication Systems of New Generation. – Proceedings of 9-th International Conference “Speech and Computer”(20–22 September, 2004), Saint-Petersburg, Russia, pp. 694–700.

11. Timofeev A.V., Syrtsev A.V., Kolotaev A.V. Network Analysis, Adaptive Control and Imitation Simulation for Multi-Agent Telecommunication Systems. – Proceedings of International Conference Phys Con 2005 (August 24-26, 2005, Saint-Petersburg, Russia).

Blog