- •А.В.Тимофеев, а.В.Сырцев Модели и методы маршрутизации потоков данных в телекоммуникационных системах с изменяющейся динамикой
- •Содержание
- •1. Эволюция глобальных ткс и принципов управления потоками данных
- •1.1. Рост объема и изменение структуры трафика в глобальных ткс
- •1.2. Современные тенденции развития глобальных ткс
- •1.3. Pазвитие ip-технологий маршрутизации и передачи потоков данных
- •1.4. Архитектура глобальных ткс и роль сетевой системы управления
- •1.5. Принципы построения адаптивных и интеллектуальных систем сетевого управления
- •1.6. Анализ ткс как информационного объекта управления
- •1.6.1. Графовые модели ткс
- •1.6.2. Матричные модели ткс и их взаимосвязь
- •1.6.3. Критерии коммуникабельности ткс
- •2. Методы статической маршрутизации потоков данных в мульти-агентных ткс
- •2.1. Задачи маршрутизации потоков данных и их роль в сетевом управлении ткс
- •2.2. Постановка задачи оптимальной статической маршрутизации
- •2.3. Модели и алгоритмы статической маршрутизации
- •2.3.1. Дерево кратчайших маршрутов для ткс с односторонними связями
- •2.3.2. Каталог узлов и оптимальных маршрутов для статических ткс
- •2.3.3. Метод статической лавинной маршрутизации
- •2.3.4. Методы вероятностной маршрутизации
- •2.3.5. Метод оптимальной маршрутизации, основанный на построении остова минимальной стоимости графовой модели ткс
- •2.4. Групповая маршрутизация в статических ткс
- •2.6. Оптимальная статическая маршрутизация в глобальных мульти-агентных ткс
- •3. Методы и средства динамической маршрутизации в глобальных ткс
- •3.1. Постановка задачи динамической маршрутизации
- •3.2. Основные алгоритмы динамической маршрутизации
- •3.2.1. Алгоритм Беллмана-Форда и его модификации
- •3.2.2. Алгоритм Дейкстры
- •3.3. Критерии существования оптимальных маршрутов передачи данных в динамических ткс на основе простых карт и таблиц маршрутизации
- •3.3.1. Критерий маршрутизируемости
- •3.3.2. Оптимальные таблицы и карты маршрутизации и вычисление оптимальных маршрутов
- •3.5. Много-адресная маршрутизация в динамических ткс
- •3.6. Многопотоковая маршрутизация в динамических ткс
- •3.7. Алгоритм 2-потоковой динамической маршрутизации
- •4. Модели и методы адаптивной и нейросетевой маршрутизации в мульти-агентных ткс
- •4.1. Особенности адаптивной маршрутизации в ткс с неопределённой днамикой
- •4.2. Принципы и модели централизованной, децентрализованной и мульти-агентной маршрутизации
- •4.3. Особенности организации распределительных таблиц и карт для адаптивной маршрутизации
- •4.4. Критерии корректности распределяющих карт маршрутизации
- •4.5. Расширение карт маршрутизации и интенсивность потоков данных
- •4.6. Централизованная и распределённая маршрутизации в мульти-агентных ткс
- •4.7. Нейросетевая маршрутизация в мульти-агентных ткс
- •Список литературы
- •Сведения об авторах
1. Эволюция глобальных ткс и принципов управления потоками данных
Глобальные ТКС (Wide Area Networks, WAN) обычно охватывают большие географические области (страну, континент и т.п.) и требуют пересечения государственных границ общедоступными узлами и каналами связи. Магистральные сети этих ТКС включают в себя определенное количество взаимосвязанных коммутирующих или маршрутизирующих узлов, т.е. маршрутизаторов.
Сообщения, передаваемые через оборудование и интерфейс пользователей проходят по определённым маршрутам через внутренние узлы глобальной ТКС к адресату-получателю данных. Все эти узлы, включая и граничные узлы, не затрагивают информационное содержание (семантику) передаваемых данных. Их роль заключается только в том, чтобы обеспечить необходимую коммутацию или маршрутизацию, гарантирующую передачу (транспортировку) потока данных от узла к узлу глобальной ТКС, пока он не достигнет адресата.
Таким образом, коммуникационная роль ТКС отделена от информационной роли узловых компьютеров (хостов, серверов и т.п.) компьютерной сети (КС), предназначенных для предоставления информационных ресурсов и исполнения программ пользователя, называемых приложениями. Благодаря такому разделению ролей структура ТКС и КС значительно упрощается.
1.1. Рост объема и изменение структуры трафика в глобальных ткс
Главной задачей глобальной ТКС является управляемая передача сообщений в форме потока данных от одного узлового компьютера к другому подобно тому, как телефонные ТКС переносят речь говорящего (источника) к слушающему (приёмнику). В качестве узловых компьютеров в глобальных ТКС обычно используются специализированные коммуникационные компьютеры, называемые коммутаторами или маршрутизаторами [1–4].
Когда поток данных посылается от одного коммуникационного узла к другому через промежуточные узлы, он поступает на вход каждого промежуточного узла TKC и целиком хранится в нем до тех пор, пока не освободится требуемая маршрутом линия связи, по которой затем этот поток передается к следующему узлу. Этот принцип работы подсети называется “от точки к точке” (Point-to-Point) или “с промежуточным хранением” (Store-and-Forward).
С узлами глобальной TKC как распределённой транспортной подсети обычно связаны автономные информационные компьютеры (хосты, серверы и т.п.), являющиеся носителями информационных ресурсов и приложений и образующие глобальную компьютерную сеть (КС). Связь между компьютерами этой КС и ТКС осуществляется с помощью каналов связи (медный кабель, волоконная оптика, радиоканалы высокой частоты, спутники связи и т.п.).
На протяжении ряда десятилетий глобальные ТКС использовались в основном для обслуживания речевого трафика. Этот трафик сначала формировался в стационарных (фиксированных) локальных и глобальных телефонных ТКС, а затем распространился в мобильные ТКС различного масштаба, имеющих значительную географию охвата.
В течение последнего десятилетия речевой трафик возрастал на 5-7% в год. Поэтому он продолжает стимулировать быстрое развитие мировых фиксированных (стационарных) и мобильных ТКС, обеспечивающих телефонную связь на больших расстояниях.
В этот период трафик данных составлял лишь проценты от суммарного речевого трафика ТКС. Этот трафик начал формироваться и развиваться в системах электронной почты и локальных ТКС с относительно низкой скоростью передачи данных.
Однако появление всемирной сети Internet радикально изменило ситуацию в области трафика данных. Начиная примерно с 1995 года, удельный объем трафика данных стал неуклонно расти. Более того, с 2000-го года суммарный трафик данных в Internet стал удваиваться через каждые 4-5 месяцев. Столь значительное возрастание трафика данных определяется различными Internet-приложениями, в первую очередь www-приложениями.
Сегодня объемы трафика данных и связанного с ним трафика в Internet достигли объемов традиционного телефонного речевого трафика. При этом число пользователей глобальной сети Internet возрастает очень быстрыми темпами – более, чем на 50% в год. К этому нужно добавить, что трафик в крупномасштабных корпоративных ТКС также растет примерно на 50% в год.
На рис. 1.1.1 представлена сравнительная картина фактического и прогнозируемого роста глобального трафика речи и трафика данных за последнее десятилетие. Из представленных графиков следует, что, начиная с 2003 года, в глобальных ТКС будет преобладать трафик данных. Поэтому именно этот трафик является главным объектом изучения и управления в глобальных ТКС нового поколения [12].
Рис. 1.1.1. Эволюция глобального трафика речи и данных.
Описанные выше тенденции изменения структуры и объемов трафика оказывают значительное влияние на эволюцию глобальных ТКС и разработку новых поколений таких ТКС. Дело в том, что трафик данных (в том числе, трафик данных реального времени) менее чувствителен к задержкам, чем трафик речи, где предельно допустимое время задержки не должно превышать 250 мс.
Допустимые задержки при передаче информации у КС (вычислительные и информационные ресурсы) лежат в широком диапазоне – от нескольких секунд до сотен минут. Этот факт определяет возможность коммутации пакетов или ячеек как основного вида коммутации в корпоративных и глобальных ТКС передачи данных.
Лавинообразный рост трафика данных определяет фундаментальную тенденцию перехода от узкополосных ТКС с пропускной способностью до 2 Мбит/с к широкополосным ТКС с пропускной способностью порядка десятков и сотен Гбит/с. Анализ ожидаемых в ближайшие годы потоков данных свидетельствует о том, что пропускные способности мировых глобальных ТКС, охватывающих США и Европу, достигнут 5 Тбит/с, в то время как национальные глобальные ТКС (например, во Франции и Германии) будут составлять 1-2 Тбит/с.
Рост производительности каналов связи ТКС, связанный с переходом к волоконно-оптическим каналам, приводит к необходимости создания узлов с аналогичной производительностью (оптические и квантовые компьютеры и т.п.). Можно ожидать, что производительность узлов глобальных ТКС, достигающая сегодня 40 Гбит/с, возрастет к 2003 году до 2 Тбит/с.
Быстрое развитие сетевых технологий породило экспоненциальный рост числа телекоммуникационных служб. В последние годы основные услуги были связаны с речевым трафиком и голосовыми приложениями. Однако в ближайшем будущем будет возрастать удельный объем трафика данных и роль мультимедийных служб. Это приведет к все большей интеграции информационных и телекоммуникационных технологий.
Глобализация и другие современные тенденции развития ТКС привели не только к существенному пересмотру основных телекоммуникационных концепций, но и к значительным технологическим сдвигам. К числу важнейших тенденций и преобразований можно отнести следующие:
-
от речевого трафика – к трафику данных и мультимедийному трафику;
-
от специализированных ТКС к активно взаимодействующим глобальным ТКС нового поколения;
-
от локальных специализированных услуг – к мультимедийным универсальным услугам и приложениям с гарантированным качеством в любое время и в любом месте.
На ускоренное развитие и совершенствование глобальных ТКС будут влиять новые потребности современного информационного общества (электронная коммерция, телемедицина, дистанционное обучение, ядерная физика, генная инженерия и т.п.). В результате этого для пользователей ТКС будут стираться грани между домом, где они живут, и учреждением, где они работают, между страной проживания и другими странами, между реальным присутствием (например, на лекции или на конференции) и виртуальным телеприсутствием и «живым» участием.
Таким образом, развитие и глобализация ТКС приведут к значительному улучшению условий жизни и работы людей в XXI веке. Согласно прогнозу компании British Telecom, к 2010 году около 40% учреждений будут преобразованы в «виртуальные учреждения», сотрудники которых смогут выполнять основную часть своей работы дома или в иных местах, не связанных непосредственно с конкретным местом работы.