Содержание к диссертации
Введение
Глава 1 Анализ передачи разнородного трафика в информационных системах и сетях 12
1.1 Особенности построения информационных сетей 12
1.1.1 Общая характеристика мобильных информационных сетей 12
1.1.2 Влияние каналов связи на построение и функционирование радиосетей 13
1.2 Основные характеристики и особенности типов трафика в информационных сетях 17
1.2.1 Особенности передачи речевых сигналов 18
1.2.2 Передача факсимильной информации 23
1.2.3 Передача видеоинформации 24
1.2.4 Особенности передачи данных 25
1.2.5 Особенности передачи мультимедийного трафика 26
1.3 Исследование эффективности распределения мультимедийного трафика в информационной системе с разноскоростными выходными цифровыми каналами связи 27
1.3.1 Исходные данные для задачи на исследование 27
1.3.2 Описание объектов модели сети с пакетной коммутацией на языке моделирования систем массового обслуживания GPSS/PC 29
1.3.3 Модельное представление процессов передачи в каналах связи 32
1.3.4 Результаты моделирования 35
1.3.5 Исследования мультиплексирования разнородных потоков в детерминированной структуре сетевой информационной сети 39
1.4 Проблемы передачи информации в пакетных радиосетях 44
1.4.1 Множественный доступ в информационных сетях 45
1.4.2 Влияние топологии на характеристики информационных сетей 48
1.4.3 Маршрутизация в информационных сетях 49
1.5 Постановка цели и задачи исследования 52
Глава 2 Синтез структур сложных информационных сетей 54
2.1 Представление информационного метрического пространства в системах коммутации и сетях с различной масштабностью 54
2.1.1 Геометрическое истолкование модели идеальной информационной системы 54
2.1.2 Представление изменения метрики информационного пространства в идеальной сложной информационной сети 57
2.2 Связь компонентов метрического тензора с нечетким определением топологии информационной сети 60
2.3 Использование мягких графов для описания топологий информационных сетей 63
2.4 Синтез структур детерминированных сложных информационных сетей 65
Выводы 71
Глава 3 Разработка сетевой информационной системы с виртуальными подсетями для ускоренной передачи сообщений 72
3.1 Особенности пакетных сетей с избыточной структурой 72
3.2 Анализ случайного множественного доступа при взаимном изменении взаимодействующих потоков 74
3.3 Принцип повышения скорости передачи информации между парой отправитель — адресат с использованием виртуальных подсетей 80
3.4 Метод организации ускоренной передачи сообщений с применением виртуальных подсетей 85
3.5 Вычисление потребного ресурса виртуальной сети 86
3.6 Структурная схема приемной многоканальной системы, реализующей режим параллельной передачи сообщений по виртуальным подсетям 89
Глава 4 Оценка эффективности сетевой информационной системы с виртуальными подсетями для ускоренной передачи сообщений 93
4.1 Особенности организации режима ускоренной передачи в пакетной радиосети с использованием виртуальных сетей 93
4.1.1 Вход в пакетную радиосеть 95
4.1.2 Построение таблиц связности и качества 97
4.1.3 Построение таблицы виртуальных сетей 98
4.1.4 Организация резервирования ресурса виртуальной подсети 99
4.1.5 Обработка пакетов на транзитном участке 100
4.2 Исследование модели сети со случайной топологией и алгоритмом маршрутизации с определением кратчайших путей 100
4.3 Модель сетевой информационной системы с режимом параллельной передачи по виртуальным подсетям 104
4.4 Сравнительный анализ функционирования пакетных радиосетей на основе выбора кратчайших путей и сетевой информационной системы на базе пакетных радиосетей с применением метода параллельной передачи по виртуальным подсетям 108
Выводы 114
Заключение 115
Список используемых источников 118
Приложение
- Влияние каналов связи на построение и функционирование радиосетей
- Связь компонентов метрического тензора с нечетким определением топологии информационной сети
- Анализ случайного множественного доступа при взаимном изменении взаимодействующих потоков
- Исследование модели сети со случайной топологией и алгоритмом маршрутизации с определением кратчайших путей
Введение к работе
Возрастающие объемы информации, ее мультимедийный характер накладывают на информационные системы (ИС), объединенные в различного рода сети, требования по интеграции услуг и повышению производительности последних, повышению скрытности передаваемой информации и надежности ее доставки. Оптимальное объединение разнородного трафика в единые информационные потоки и эффективные их перераспределения по различным ИС с учетом требований повышенной скорости и скрытности являются сложной задачей. В условиях, когда часть ИС может обладать ограниченными скоростными характеристиками, важными являются разработка методов организации их функционирования и эффективное использование ресурса систем и сетей [1-7].
В основу решения задач по обслуживанию и передаче трафика в ИС, объединенных в сетевые структуры, положены основы: теории систем массового обслуживания [2,4,6,10] - для исследования широкого спектра протоколов ИС и сетей, теории графов [11-14] - в основном при решении задач сетевого уровня, теории управления [4,15] — в потоковых моделях распределения и управления трафиком, теории нечетких множеств (ТИМ) [16-21] - в задачах с нечетко заданными параметрами, теории фракталов [22— 24] - при рассмотрении свойств входного трафика; а также тензорная методология Г.Крона [25-31] - при решении канальных, сетевых вопросов ИС и организации баз данных на основе совмещения характеристик трафика и ИС. Вместе с тем для оценки эффективности применяемых, исследуемых и разрабатываемых методов остается имитационное моделирование процессов в ИС и сетях [6,7,24,26-37].
Одной из сложностей в обслуживании трафика является согласование разнородного входного потока с возможностями ИС и сетей (в настоящее время такое согласование осуществляется на основе соглашения между пользователем и сетью для заданных параметров трафика - скорости,
пачечности, задержки, надежности доставки). В информационно-аппаратно-программном смысле важным является согласование потоков ИС со структурой, в которую они организованы (для этой задачи может использоваться тензорная методология Г. Крона [25]). Ввиду разных возможностей ИС, большого их количества в объединенных сетевых структурах эффективным является использование регулярных топологий [35,38] совместно со специальными методами маршрутизации. Во-первых, выигрыш в этом случае возможен за счет использования только локальной информации в ИС при маршрутизации и управлении потоками (совместно с использованием информации об исходных данных и методе построения избыточных нечетких самоподобных структур [30,39,40]); во-вторых, использование избыточности позволит применить режим параллельной обработки и передачи информации. Кроме того, регулярные структуры обладают высокой структурной надежностью и содержат большое количество альтернативных путей равной длины [39]. Отрицательной особенностью таких сетей является их неприспособленность для передачи разнородного трафика.
В связи с этим актуальной является задача организации сетевых информационных систем (СИС) в виде сетевых ячеек, каждая из которых может быть представлена как распределенная информационная система, реализующая сетевые технологи и обслуживающая с заданными критериями качества разнородный трафик пользователей.
Объект исследований: сетевая информационная система.
Предмет исследования: процедурные модели сетевой информационной системы с виртуальными подсетями повышенной производительности.
Цель диссертационной работы: повысить эффективность
взаимодействия пользователей информационной сети путем разработки
метода формирования виртуальных подсетей повышенной
производительности.
Задачи исследования:
- оценить эффективность распределения информационных потоков в
ИС и сетях с учетом их стохастических свойств;
выявить возможность построения и предложить организацию разнородных структурированных СИС на основе организации разнородных ИС;
построить виртуальные подсети в СИС с динамическими структурами;
- разработать процедурную модель настройки СИС для ускоренной
передачи информации в виртуальных подсетях;
- оценить информационную эффективность пакетной передачи
информации в разработанной СИС с виртуальными подсетями повышенной
эффективности.
Научная новизна работы:
впервые решена задача использования избыточности структуры СИС для формирования виртуальных подсетей, обеспечивающих повышение производительности путем введения режима параллельной передачи пакетов;
разработан метод ускоренной передачи сообщений в виртуальных подсетях СИС;
предложена процедурная модель настройки СИС для передачи информации по виртуальным подсетям в режиме ускоренной передачи, заключающейся в формировании сетевой ячейки для передачи сообщения в параллельном режиме.
разработана структура СИС, реализующая метод ускоренной передачи сообщений, с блоками определителя категорий сообщений с базой данных характеристик сообщений, вычислителя потребного ресурса виртуальной подсети, блока настройки виртуальной подсети и режима передачи, имеющего базу данных топологий виртуальных подсетей и формирователь текущей топологии сети.
Практическая значимость работы заключается в полученных рекомендациях по использованию режима ускоренной передачи для низкоскоростной СИЄ на базе ПРС с сильной связностью; и фиксированным числом абонентов, а также в возможности использования полученных процедурных моделей при' проектировании новых и анализе уже существующих сетевых информационных систем инженерами-проектировщиками.
Полученные.в ходе работы результаты использованы::.
1) в НИР «Эфир-ЕС», проводимой в; ОАО «Тамбовский научно-
исследовательский институт радиотехники «Эфир» по вопросам повышения
эффективности;информационных- систем^ в. результате которой выработаны
рекомендации по использованию современных сетевых, информационных
систем;.
2) при обучении студентов специальности «Информационные системы
и защита информации» на факультете информационных технологий ГОУ.
ВПО ТГТУ, что позволило повысить качество и эффективность учебного
процесса; .'. '
В первой главе диссертации в результате- анализа современных ИС и
сетей, а также проведенных исследований: сформулированы замечания,,
позволяющие: осуществить постановку задачи. В частности: рассмотрены
особенности построения/информационных сетей, использующих различного
родаИС при передаче пакетов; проведен анализ основных характеристик и
особенностей типов трафика - речи;..' факсимильных сообщений, данных,
видеосообщений; проведено исследование статистического
мультиплексирования информационных потоков разнородного трафика в. ИС,:имеющей? разноскоростные выходные каналы связи. (КС) и аналогичное распределение его* в: сегменте упорядоченной структуры; сети с пакетной коммутацией.. В- результате сформулированных замечаний указано' на необходимость разработки СИС со структурной избыточностью; С целью повышения информационной эффективности СИС необходимо формировать
детерминированные, на интервале рассмотрения устойчивые подструктуры СИС, которые исходя из минимального числа транзитных участков позволяют организовать режим параллельной передачи по непересекающимся маршрутам. Это одновременно должно минимизировать, при определенных условиях, конфликтные ситуации при множественном доступе и существенно упростить задачу маршрутизации с использованием виртуальных подсетей.
Во второй главе показан вариант представления взаимного информационного воздействия подсетей с использованием метрики информационного пространства и связь последней с описанием нечетких структур информационных сетей. Показано,- что для интегрированной информационной сети «вклад» каждой подсети в информационном плане характеризуется своим углом поворота своей подсистемы в едином информационном пространстве. Так как модуль косинуса угла поворота лежит в интервале [0,1], то в целом различные подсети можно характеризовать значениями функций принадлежности к некоторой универсальной (объединяющей всех элементов) сети. Указанное выше означает, что значениями косинусов углов, т.е. коэффициентами в интервале [0,1], можно количественно регулировать передачу объемов информации при переходе от одной подсети к другой. Раскладывая описанную таким образом информационную сеть по уровням декомпозиции, всегда можно осуществлять управление подсетями на основе применения нечеткой логики. В главе показан вариант получения нечеткой структуры сети, который соответствует построению n-мерных гиперкубов, с той лишь разницей, что его вершины будут соответствовать нечетким подмножествам, приведена процедурная модель формирования таких самоподобных структур.
В третьей главе исследован алгоритм случайного множественного доступа с контролем несущей и обнаружением конфликтов (СМД КН/ОК), в результате чего определен диапазон значений вероятностей настойчивой передачи источниками в общий ресурс ИС, показано, что в условиях средней
информационной нагрузки (несущественные потери информации) эффективным является управление потоками информации, в том числе их пульсациями. В результате предложено потоки распределять в СИС в параллельном режиме. Предложен подход формирования СИС с виртуальными подсетями для ускоренной передачи информации, разработаны метод ускоренной передачи в СИС с виртуальными подсетями и ее структура.
В четвертой главе рассмотрены особенности организации параллельной передачи в СИС на базе низкоскоростной пакетной радиосети (ПРС), разработана процедурная модель настройки СИС на передачу информации по виртуальным подсетям, предложена структура канала для организации виртуальных подсетей, проведено моделирование двух моделей информационных сетей: с общеизвестными протоколами, реализующими поиск кратчайших путей на графе, и СИС с предложенным методом ускоренной передачи. В результате исследований методом имитационного моделирования сделаны выводы и предложены рекомендации по применению СИС на базе низкоскоростной ПРС.
В заключении приведены выводы по работе. В общем, структура работы состоит из введения, четырех глав, заключения, списка используемых источников из 74 наименований и приложения. Общий объем диссертации составляет 125 страниц, из них список использованных источников - 8 страниц. Основной текст диссертации содержит 39 рисунков, 7 таблиц.
Влияние каналов связи на построение и функционирование радиосетей
Сеть обмена данными (ООД) на основе радиорелейных: линий, связи; (РРЛС); Построение СОД средних размеров (до 20 сетевых узлов) на основе-РРЛС, работающих в миллиметровом; диапазоне (например для-"Астра-Ц" :— 10,38... 11,7 ГГц), является экономически; более выгодным нецелесообразным, чем. использование для этой цели волоконно-оптических, линий связи (ВОЛС). Основным недостатком радиорелейных; линий связи является их относительно невысокая надежность по сравнению с ВОЛС. Этот недостаток может быть компенсирован включением в опорную сеть резервных каналов-связи, организованных с помощью РРЛС.
Одной из важнейших характеристик СОД считается скорость переключения трафика с. основных линий в случае их отказа;, на резервные; Переключение: должно; происходить быстро- и автоматически. Если распространенным- способом организации отказоустойчивой сети на основе ВОЛС является применение метода одинарного резервирования: (сеть строится в виде кольца), то для обеспечения устойчивой работы; СОД, построенной на базе радиорелейных станций; используется другой способ -организация дополнительных; резервных каналов связи (КС). При этом ре: . ализация схемы переключения может быть произведена на уровне IP с использованием протоколов динамической маршрутизации OSPF (Open Shortest Path First) или BGP (Border Gateway Protocol). Метод предусматривает подключение каналов связи напрямую в маршрутизаторы.
Такая организация сети проста, однако она обладает некоторыми недостатками. Весь поток данных, проходящий через такую сеть, на пути его следования обрабатывается каждым маршрутизатором. При этом в каждом из узлов сети должен быть установлен маршрутизатор, способный обработать поток данных на скорости физического канала. Например, для канала с пропускной способностью 10 Мбит/с требуются мощные маршрутизаторы, производительность которых должна быть соответственно не ниже 10 Мбит/с. При соединении в узловой точке нескольких каналов необходим маршрутизатор, обрабатывающий трафик их суммарной мощности.
Использование столь мощных маршрутизаторов в сетях малого и среднего масштаба экономически невыгодно. К тому же при такой технологии появляются значительные задержки в обработке пакетов данных и, что еще более важно, возникают неконтролируемые вариации задержек.
Одним из эффективных методов, позволяющих существенно уменьшить задержки, возникающие при переключении трафика с основного канала на резервный, является подключение РРЛС не к маршрутизаторам, а к коммутаторам. При этом используется, STP - протокол, реализованный практически во всех коммутаторах, предназначенный для выявления и блокирования циклических потоков данных. В сети, имеющей резервные каналы связи, использование STP необходимо, но недостаточно для ее нормального функционирования. С помощью данного протокола трафик при сбоях в сети успешно переключается с основных каналов на резервные. Однако в радиорелейных линиях связи в случаях, когда трафик передается по каналу в одном направлении, протокол STP не способен осуществить правильное регулирование: хотя включение резервного канала и произойдет, исходный канал будет продолжать работать в одном направлении. В результате трафик будет передаваться циклично, "по кругу", что может привести к перегрузке сети.
Для того чтобы избежать появления циклических потоков, вместе с протоколом STP на портах коммутаторов, к которым подключены радиорелейные станции, используется функция UDLD. Она позволяет обнаружить момент времени, с которого КС начинает работать в одном направлении, и немедленно отключает такой канал. Функция организуется на коммутаторах с обеих сторон канала. UDLD производит постоянный обмен пакетами. На основе анализа их прохождения или непрохождения делается вывод о работоспособности КС.
Совместное использование протоколов STP и UDLD позволяет построить отказоустойчивую сеть, имеющую хорошие характеристики времени переключения с одного канала на другой и надежно работающую в условиях возможных сетевых сбоев.
На базе РРЛС можно успешно создавать опорные сети передачи данных, в общем случае, с ячеистой топологией. Использование этих станций является весьма выгодным с экономической точки зрения и эффективным - с технической. РРЛС миллиметрового диапазона "Астра-Ц" сертифицированы Минсвязи России. Станции имеют малую мощность потребления и длительный срок эксплуатации. Они достаточно компактны, не требуют дополнительного программного обеспечения и функционируют с различными сетевыми протоколами и операционными системами.
Рассматриваемый принцип построения сети на основе радиорелейных линий связи соответствует варианту построения типовой однородной сети, в которой дальность между приемопередатчиками одного транзитного участка определяется дальностью прямой видимости (до 30-40 км). Аналогичные ИС и сети имеют место в УКВ диапазоне - ПРС DARPA [41]. Высокой канальной гибкостью обладают системы ПРС, построенные на базе объединенной системы распределения тактической информации и относительной навигации JTIDS [48]. Система предполагает функционирование множества двухскачковых сетей с количеством абонентов, не превышающих 31.
Указанные ИС характеризуются относительно высокими скоростями передачи информации в КС, однако при больших пространствах они значительно усложняются. В этом случае эффективно могут использоваться спутниковые системы связи (в том числе с пакетной коммутацией), наземные опорные сети связи.
Важное значение в условиях передачи на большие расстояния имеют ИС декаметрового (ДКМ) диапазона [49]. Например, сеть ITF [33] обеспечивает передачу зашифрованных речевых сигналов до 1000 км и более. В зависимости от используемых мощностей радиопередающих устройств в данном диапазоне можно формировать глобальные, регионального и локального уровней информационные сети. Особенностью таких сетей является малая скорость передачи информации по КС - до 2400 бит/с, 4800 бит/с, 9600 бит/с.
Связь компонентов метрического тензора с нечетким определением топологии информационной сети
В (2.5), (2.6), (2.9) показано, что входящие в метрический тензор компоненты, определяющие состояние сети, характеризуются коэффициентами, которые соответствуют косинусам углов поворота базисных векторов.
Если применить понятие опорной, или интегрированной информационной сети, то «вклад» каждой подсети в информационном плане для нее будет характеризоваться своим углом поворота своей системы координат в едином информационном пространстве. Так как модуль косинуса угла поворота лежит в интервале [0,1], то в целом различные подсети можно характеризовать значениями функций принадлежности, в информационном плане, к некоторой универсальной (объединяющей все элементы, т.е. опорной) сети. Сказанное выше также означает, что значениями косинусов углов, т.е. коэффициентами в интервале [0,1], можно количественно регулировать передачу объемов информации при использовании нескольких подсетей.
Раскладывая описанную, таким образом, информационную сеть по уровням декомпозиции, всегда можно осуществлять управление подсетями на основе применения нечеткой логики.
Графически, чисто качественно, это можно представить рисунком 2.3. Подсети аг уровней, где / - номер подсети, характеризуются значениями а, которые соответствуют степени изменения масштабности количества передаваемой информации в опорной сети. Очевидно, в каждой подсети имеет место взаимная энтропия, привносимая одновременным функционированием элементов подсети (другими словами, дополнительные затраты ресурса системы). Это вводит неортогональность в системах координат каждой подсети а,- уровня. Поэтому значения а, могут находиться в некоторых (допустимых) интервалах, определяясь (определяя) некоторой шкалой степени использования ресурса опорной сети. Изменение значений а, может быть обусловлено не только типом трафика, но и топологией подсетей. Представим, что выделяемые по подсетям виртуальные пути имеют различные физические возможности по передаче информации. Для одного и того же сообщения, требующего передачи информации с использованием ретрансляционных участков, могут быть выделены виртуальные линии различной мощности в смысле передачи информации. Замечание 1. Как видно, имеется возможность использовать метрические характеристики - значения направляющих косинусов - как по передаваемым типам сообщений с учетом их степени удлинения (укорачивания) длин пакетов, так и по градации структур с использованием нормированных характеристик виртуальных линий по пропускной способности. И в первом, и во втором случае в качестве применяемого параметра можно использовать функцию принадлежности к некоторым подсетям, которая принимает значение в диапазоне [0,1]. Другими словами, в основу построения топологии опорной (интегральной) сети, учитывающей дискретное, но плавное изменение подсетей, исходя из потоковой ситуации в работе предлагается использовать ТЕМ [17]. Замечание 2. Формирование подсетей на основе ТРІМ, где состояние каждой сети в информационном плане отображается на состояние опорной сети, позволяет использовать в опорной информационной сети виртуальные подсети различных а,- уровней для решения задач, например, ускоренной передачи информации. Особенностью сетевых задач является согласованное функционирование всех узлов сети и эффективная передача всего сетевого трафика в соответствии с реализацией алгоритмов маршрутизации потоков. Важное значение при этом имеют виды используемых сигналов, методы кодирования, протоколы передачи, обслуживания, множественный доступ (особенно подуровень доступа к среде канального уровня ЭМВОС) [3 - 6, 8, 9, 33 - 38, 66], которые существенно определяют эффективность передачи информации. В свою очередь, их применение зависит от статистических свойств трафика и от топологии сети. Очевидно, малая А:-связность сети приводит к концентрации потоков, что более эффективно сказывается на функционировании сети, однако вопросы надежности сети, увеличения длины маршрутов ограничивают снизу и требуемую связность. Если сеть сильно связна, то имеют место проблемы множественного доступа, особенно когда трафик недостаточно большой, поэтому чтобы применить строгое упорядочение в протоколах доступа, и используются механизмы случайного множественного доступа. В первой главе показано, что в случае мультимедийного трафика, с одной стороны, а с другой — при наличии различных по скоростным возможностям сетей передачи информации имеется возможность статистически уплотнять потоки, основываясь на занятости-различных по пропускной способности каналов связи.
Анализ случайного множественного доступа при взаимном изменении взаимодействующих потоков
Одним из наиболее распространенных является СМД с обнаружением конфликтов и детектированием несущей (CSMA/CD, используется в сетях Ethernet) [67]. Очевидно, свойство контроля несущей (ее детектирование) и обнаружение конфликтов позволяют минимизировать конфликты в канале с общим ресурсом. Помимо этого, на эффективность функционирования канала СМД влияет степень активности пользователей в условиях неопределенности состояния канала.
В условиях, когда интенсивность входных потоков соизмерима со средней скоростью обслуживания, разумно использовать протокол Р-настойчивой передачи. При этом пакет, поступающий для передачи по каналу, считается изначально попавшим в конфликт, а его передача осуществляется с вероятностью Р.
Структурная схема модели передачи пакетов информации двумя независимыми источниками в канал общего доступа (в дальнейшем - канал СМД) приведена на рисунке 3.2. Среднее время между пакетами одинаково для обоих источников и равно tcp условных единиц (в дальнейшем - с). Пуассоновские потоки сгенерированных пакетов поступают в накопительные буфера соответствующих входных каналов. Перед передачей информации в канал СМД пакет помещается в буфер передачи единичной емкости и уничтожается только после того, как его копия будет успешно передана по этому каналу. Сегментация временных интервалов (модель синхронной ALOHA) осуществляется схемой управления ключом: ключ «открывает» канал связи СМД на промежутки ґ„е/,= 10с, продолжительность которых соизмерима с временем передачи одного пакета. В начале периода каждого интервала осуществляется имитация начала передачи пакета из буфера передачи 1 с вероятностью Рх и из буфера передачи 2-е вероятностью Р2. По окончании интервала времени tnep производится анализ процесса совместной передачи: если КС был занят двумя пакетами одновременно, осуществляется попытка повторной передачи при следующем открытии ключа. При считывании одного пакета (из какого-либо входного КС) принимается решение об его успешной передаче, освобождается соответствующий буфер передачи для очередного пакета из накопительного буфера.
Результаты моделирования показывают, что для передачи данных с минимальной задержкой время между поступающими пакетами должно быть ґф 45с. При tcp = 45c и вероятностях Р\ = Р2, значения которых лежат в интервале [0,5...0,.6], эффективность функционирования канала наибольшая (рисунок 3.3).
При настойчивой передаче пакетов по одному входному КС, с целью минимизации повторных передач, вероятность передачи во втором канале должна быть малой. На рисунке 3.4 а,б показаны результаты моделирования: вероятность повторной передачи в первом канале принята равной Р\ - 0,9, во втором - меняется в диапазоне от Pi = 0,4 до Ргя 0,65. Как видно, эффективность первого канала достигается временными потерями во втором канале.
Для определения влияния пульсирующего трафика (под пульсирующим трафиком понимается поток пакетов, интенсивность которого периодически меняется на определенную величину) одного канала на второй проведено моделирование, когда во втором канале интенсивность уменьшалась на 50% в полупериоде входящего потока. В этом случае величина tcp во входных каналах может быть меньшей: tcp 40 с. На рисунке 3.5 (при среднем интервале между поступлениями пакетов, равном 40 с) показано, что пульсация потока во втором канале может существенно снизить задержку в параллельном канале (в первом).
Исследование модели сети со случайной топологией и алгоритмом маршрутизации с определением кратчайших путей
Сеть состоит из N=30 узлов. Наличие связи между двумя узлами определяется случайным образом с вероятностью Рсв = 0,5. В модели с целью упрощения процессов передачи принято условие симметрии каналов связи. При построении топологии исключались случаи формирования несвязного графа. Пропускная способность каналов связи С, =2400 бит/с. Топология, выбранная случайным образом, в течение цикла моделирования не меняется. Для формирования статистики для одних и тех же исходных значений параметров случайный выбор топологии выполнялся 10 раз. Б. Формирование потоков и типов сообщений
Каждым узлом сети формируется пуассоновский поток сообщений с интенсивностями: 0,001+1/12 к (к=0,1,...9) в секунду. Каждое сообщение делится на пакеты длиной 300 бит (десятая часть от значения пропускной способности). Количество пакетов для каждого сообщения принято равным восьми. Адресат для каждого сообщения выбирается равновероятно. В. Передача пакетов по каналам связи
Каждое сообщение направляется по кратчайшему пути, определенному по алгоритму Дийкстры. В качестве стоимости применяется число транзитных участков. В случае наличия нескольких одинаковых путей выбирается путь с наименьшим числом пакетов в буферах промежуточных узлов. Если таких путей несколько, то выбирается путь с наименьшим геометрическим расстоянием. При наличии нескольких путей с наименьшим геометрическим расстоянием выбирается последний.
Формально алгоритм Дийкстра требует, чтобы длины всех дуг были положительны (это выполняется в сетях передачи данных). Объем вычислений, в худшем случае, для него значительно меньше, чем у алгоритма Беллмана - Форда. Так как число операций, выполняемых алгоритмом Дийкстры на каждом шаге, пропорционально N, а шаги итерируются N - 1 раз, то объем вычислений в худшем случае равен О (N"), а не О (N3), как у алгоритма Беллмана - Форда [4].
Основная идея алгоритма состоит в том, чтобы отыскивать кратчайшие пути в порядке возрастания длины пути [4]. Кратчайшим среди всех кратчайших путей от узла 1 является путь, состоящий из одной дуги, соединяющей узел 1 с ближайшим соседним узлом, так как любой путь, состоящий из нескольких дуг, будет всегда длиннее длины первой дуги вследствие предположения о положительности всех дуговых длин.
Следующим, кратчайшим среди кратчайших путей, должен быть либо путь из одной дуги к следующему ближайшему соседу узла 1, либо кратчайший путь из двух дуг, проходящий через узел, выбранный на первом шаге, и т. д.
Для формального описания алгоритма будем считать, что каждый узел і имеет метку Д , означающую оценку длины кратчайшего пути от узла 1 (рисунок 4.3). В случае, когда оценка становится неизменной, узел окончательно помечается. Множество окончательно помеченных узлов обозначим через М. Узел, который будет добавлен на очередном шаге к М, является ближайшим к узлу 1 среди всех узлов, еще не вошедших в М
На к-м шаге имеется множество М из к ближайших узлов к узлу 1, D, -кратчайшее расстояние от узла 1 до каждого узла /из М. Среди всех путей, соединяющих узел 1 с каким-либо узлом не из М, самый кратчайший путь должен пройти по узлам из М (так как dtJ 0). Поэтому (к+1)-й - ближайший узел и соответствующее кратчайшее расстояние получается минимизацией по j М величины тіпієм {D, + d0}.
Формально алгоритм работает следующим образом [4]. Исходное состояние: М = {1}, D\ = О и D} = dy} для ]Ф1.
Каждый узел после формирования сообщения и его разбивки на пакеты начинает передачу с вероятностью Р=0,8 в канал связи с определенной пропускной способностью. Передача осуществляется в течение одного интервала окна передачи (окно передачи равно восьми пакетам). После этого следует тайм-аут для условного подтверждения получения пакетов данного окна. После тайм-аута осуществляется .дальнейшая передача пакетов. Каждый пакет имеет параметр - время жизни. Если оно превышает заданное (в модели установлено 60 с), то осуществляется уничтожение пакета и фиксирование его как потерянного. Процесс восстановления сообщений не рассматривается. Размер буфера для промежуточного хранения равен 1000. Г. Упрощенный учет множественного доступа
В случае, когда фиксируется состояние нескольких передач одному узлу, последний на основе вычислений кратчайшего геометрического пути осуществляет прием одной серии пакетов (идеальный захват). Остальные пакеты перемещаются в конец буферов узлов-отправителей. После тайм-аута начинается следующая передача с вероятностью Р=0,8 для всех узлов, в том числе для ближнего отправителя.
Оценка эффективности функционирования модели сети осуществляется по определению ее производительности, временной задержки и оценки информационных потерь (рисунки 4.6 - 4.8 соответственно).
