Содержание к диссертации
Введение
Глава 1 Методы и алгоритмы маршрутизации 11
1.1 Основные положения 11
1.2 Классификация алгоритмов маршрутизации 12
1.3 Требования, предъявляемые к алгоритмам динамической маршрутизации 24
1.4 Маршрутизация в мультисервисных сетях 25
1.5 Протоколы маршрутизации мультисервисных сетей 28
1.5.1 Протокол OSPF 29
1.5.2 Протокол IS-IS 30
1.5.3 Протокол BGP 32
1.6 Выводы 35
Глава 2 Разработка метода адаптивной маршрутизации..37
2.1 Управление трафиком 37
2.2 Постановка задачи маршрутизации 43
2.3 Уровень резервирования пропускной способности 44
2.4 Уровень формирования допустимых маршрутов 46
2.5 Уровень распределения потоков 46
2.6 Статистические характеристики трафика 49
2.7 Разработка алгоритма. Создание набора допустимых маршрутов 51
2.8 Процедура устранения «тупиковых» маршрутов 59
2.9 Алгоритм проверки связности графа 60
2.10 Распределение трафика 66
2.11 Распределение потоков с учетом приоритетов маршрутов 73
2.12 Распределение трафика с учетом приоритетов направлений 74
2.13 Особенности применения резервирующего алгоритма 79
2.14 Выводы
Глава З Программная реализация маршрутизации с учетом приоритетов маршрутов 81
3.1 Обоснование выбора среды разработки 81
3.1.1 Особенности среды разработки Delphi 7 81
3.1.2 Особенности объектно - ориентированного программирования в языке Object Pascal 83
3.2 Использование объектно-ориентированного программирования в программной реализации 84
3.3 Работа с интерфейсом программы 90
3.4 Выводы 102
Глава 4 Анализ эффективности разработанного адаптивного метода маршрутизации 103
4.1 Методы оценки эффективности 103
4.2 Моделирование системы анализа 104
4.3 Анализ результатов 109
4.4. Выводы 118
Заключение 120
Литература
- Классификация алгоритмов маршрутизации
- Уровень резервирования пропускной способности
- Особенности объектно - ориентированного программирования в языке Object Pascal
- Использование объектно-ориентированного программирования в программной реализации
Введение к работе
Актуальность темы
Характерной тенденцией современного этапа развития компьютерных сетей является принципиальное изменение структуры передаваемого трафика. Анализ статистики агрегированного трафика большинства сетей доступа в Интернет явно показывает высокую долю в нем аудио- и видео-потоков данных. Можно определенно утверждать, что трафик сетей доступа в Рїнтернет, а также сетей крупных предприятий, стал мультимедийным. При этом постоянно разрабатываются и внедряются новые алгоритмы, протоколы и технологии, которые в определенной степени улучшают качество передачи трафика реального времени в IP-сетях. Следствием этого является существенное усложнение архитектуры сетей TCP/IP, которые теперь характеризуются не просто как сети передачи данных, а как мультисервисные.
Между тем, каналы передачи данных, подходящие для предоставления одной услуги, не всегда подходят для предоставления другой. Увеличение объемов предоставляемых услуг заставляет операторов и провайдеров параллельно развивать несколько различных сетей. Это требует больших затрат и часто сопряжено со значительными техническими трудностями.
Маршрутизация на сегодняшний день определяется не формальными правилами и описаниями, характерными для сетей предыдущих поколений, а требованиями клиента и экономическими соображениями оператора связи. Чтобы оптимизировать работу сетей, разрабатываются различные методы маршрутизации, обеспечивающие сбалансированную нагрузку всех сетевых ресурсов. Среди зарубежных ученых, изучающих данную проблему, стоит особо выделить D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, J. McManus, S. Hiroyuki, M. Yasuhiro, Y. Makiko и др.
Чтобы успешно передать по сети потоки информации самого различного рода необходимо, чтобы алгоритм маршрутизации учитывал требования, предъявляемые данными потоками к уровню качества обслуживания (Quality of Service, QoS). Для этого весь трафик подразделяют на классы сервиса. И
тогда маршрутизация по всей сети будет осуществляться в соответствии с классом сервиса каждого отдельного потока. В России вопросами маршрутизации и смежными с ними проблемами занимаются Б.С. Гольдштейн, В. М. Вишневский, Ю.А.Семенов, В. Н. Тарасов, А. В. Росляков и др.
Для получения оптимального решения необходимо одновременное рассмотрение всех потоков на полном множестве маршрутов. Однако в мультисер-висных сетях с большим количеством узлов размер задачи маршрутизации при этом может оказаться весьма существенным, что не позволит решить ее за приемлемое время. Поэтому задача разработки новых методов адаптивной маршрутизации является актуальной.
Объектом исследования являются сети с пакетной коммутацией (муль-тисервисные сети).
Предметом исследования является набор минимальных допустимых маршрутов, который необходимо выделить в сети, для того, чтобы передать разнородные потоки трафика, предъявляющие требования к QoS.
Цель работы и задачи исследования
Цель диссертации состоит в уменьшении размерности задачи маршрутизации в мультисервисных сетях.
Для достижения поставленной цели необходимо провести анализ существующих методов маршрутизации и решить следующие задачи:
- разработать алгоритм определения набора допустимых оптимальных
маршрутов;
разработать способ распределения потоков трафика по набору допустимых маршрутов;
создать объектно-ориентированную модель работы предложенного алгоритма;
выполнить программную реализацию разработанного алгоритма;
провести компьютерное моделирование процесса маршрутизации сети с использованием разработанного алгоритма.
7 Методы исследования
Для решения сформулированных задач в работе используются методы теории графов, теории вероятности и математической статистики, теории массового обслуживания.
Достоверность результатов
Достоверность результатов обеспечивается адекватностью использованных методов теории графов и теории массового обслуживания. Достоверность положений и выводов работы подтверждается результатами компьютерных экспериментов.
Научная новизна результатов.
Предложен и разработан алгоритм, обеспечивающий существенное уменьшение размерности задачи маршрутизации за счет нахождения допустимых маршрутов.
Предложены способы распределения потоков трафика с учетом приоритетов маршрутов, приоритетов направлений, а также с разделением одного вида трафика на составляющие.
Личный вклад. Все результаты, составляющие содержание диссертационной работы получены автором самостоятельно.
Практическая ценность и реализация результатов работы
Основные теоретические и практические результаты, полученные в диссертационной работе, переданы для эксплуатации в Центр информационных технологий Оренбургского государственного университета и в ОАО «Инфосфера», а также использованы в учебном процессе ПГУТИ.
Апробация работы
Основные положения диссертационной работы докладывались и обсуждались на VII Международной НТК «Проблемы техники и технологии телекоммуникаций» (Самара, 2006), XIII Международной НТК «Радиолокация. Навигация. Связь» (Воронеж, 2007), XII Всероссийской НТК «Новые информационные технологии в научных исследованиях и в образовании» (Рязань, 2007), Пятой Всероссийской НТК «Современные проблемы создания и эксплуатации
8 радиотехнических систем» (Ульяновск, 2007), III Международной НТК (Винница, 2007), Международной НТК ТЕЛЕКОМ-2007 (Ростов-на-Дону, 2007), 63-й научной сессии, посвященной Дню радио (Москва, 2008), российских НТК профессорско-преподавательского состава ПГАТИ (Самара, 2006 - 2009).
Публикации
По теме диссертации опубликовано 16 работ, в том числе 1 статья в журнале, входящем в перечень ВАК РФ, 14 тезисов и текстов докладов.
Основные положения, выносимые на защиту
Формализованная в терминах теории графов задача построения минимального направленного графа.
Графовая модель набора допустимых маршрутов между узлами мультисервисной сети.
Алгоритм маршрутизации на основе метода минимальных направленных графов.
Способы распределения потоков трафика по набору допустимых маршрутов.
Комплекс программных средств, реализующих предложенный алгоритм.
Результаты моделирования маршрутизации, с использованием предложенного алгоритма.
Структура и объем работы
Диссертационная работа состоит из введения, четырех глав, списка литературы. Работа содержит 130 страниц машинописного текста, 38 рисунков и 3 таблицы. Список литературы включает в себя 70 наименований.
В первой главе приведены основные понятия, определения и положения процесса маршрутизации. Приведена наиболее полная классификация существующих на сегодняшний день алгоритмов маршрутизации. Приведенная классификация основывается на том, что изменения параметров трафика и состояния линий в сети влияют на выбираемые маршруты.
Значительное внимание в первой главе уделено требованиям, предъявляемым чаще всего к алгоритмам динамической маршрутизации. Наиболее важным из условий является обеспечение выбора рационального маршрута. Показаны основные положения мультисервисных сетей. Рассматривается наиболее перспективная основа для построения мультисервисных сетей следующего поколения (NGN) — сеть MPLS. В первой главе также приводится описание и принципы действия основных протоколов маршрутизации, наиболее часто используемых в мультисервисных сетях.
Вторая глава посвящена разработке предложенного адаптивного метода маршрутизации. Задача маршрутизации заключается в определении эффективных путей прохождения потоков трафика через сеть передачи данных. Для этого чаще всего применяется декомпозиция на три уровня:
Резервирование необходимой пропускной способности.
Определение множества допустимых маршрутов.
Размещение потоков по полученным допустимым маршрутам.
Задача первого уровня сводится к определению значения доступной пропускной способности для дополнительного трафика определенного класса сервиса через допустимую пропускную способность линии и значение реального проходящего потока трафика по той же линии. Второй уровень обшей задачи маршрутизации решается с помощью метода минимальных направленных графов (МНГ) для того, чтобы понизить сложность задачи путем накладывания дополнительных ограничений при поиске допустимых маршрутов. В результате построения минимального направленного графа образуется набор допустимых маршрутов, по которому необходимо распределить потоки информации. Это является задачей третьего уровня.
В третьей главе описана программная реализация разработанного алгоритма «Маршрутизация с учетом приоритетов маршрутов», приведены примеры с подробным описанием каждого шага, демонстрирующие его работу. Программа содержит семь основных этапов, пять из которых («Исходный графа», «Ранг и нумерация вершин», «Направление», «Устранение тупиковых маршру-
10 тов», «Проверка связности») предназначены для построения минимального направленного графа с проверкой на связность, а оставшиеся («Маршруты» и «Расчет задержек в линиях») - для вывода полученных результатов.
Четвертая глава содержит описание дополнения к программе "Маршрутизация с учетом приоритетов маршрутов", моделирование системы анализа алгоритма, а также результаты исследований. Исследовался диапазон чисел узлов сети от 3 до 40. При этом эксперименте диапазон разбивался на несколько поддиапазонов с целью уменьшения затрат процессорного времени при выполнении расчетов в программе. Такое разбиение возможно благодаря тому, что результаты исследований различных этапов не зависят друг от друга. В исходных данных задавалась вероятность генерации ребра, равная 0,5, и количество итераций для фиксированного числа узлов, равное 100. По окончании эксперимента, данные со всех этапов были сведены в одну систему координат.
В заключении обобщены выводы, сделанные по результатам каждой главы диссертации, и в тезисном виде изложены основные научные и практические результаты диссертационного исследования.
В приложении содержатся акты внедрения результатов диссертации.
Классификация алгоритмов маршрутизации
Существует несколько ключевых подходов к классификации алгоритмов маршрутизации. Во-первых, в зависимости от конкретных задач, влияющих на результирующий протокол маршрутизации, которые решает разработчик алгоритма. Во-вторых, различные типы алгоритмов маршрутизации по-разному влияют на сеть и ее ресурсы. И, наконец, алгоритмы маршрутизации используют разнообразные показатели, которые влияют на расчет оптимальных маршрутов. Кроме этого, методы маршрутизации отличаются друг от друга и тем, где хранится и как формируется маршрутная информация.
Наиболее распространенным является подход, в котором классификация основывается на том, влияют ли изменения параметров трафика и состояния линий в сети на выбираемые маршруты.
Существуют такие способы передачи данных, при которых не требуется наличие таблиц маршрутизации в устройствах. К таким относит маршрутизации от источника [5], [25]. В этом случае, при передаче данных полный маршрут следования потока трафика по сети формируется в узле-источнике в виде последовательности адресов тех узлов, через которые должны пройти пакеты, чтобы достигнуть узла-получателя, и целиком включается в состав этих пакетов. В этом случае промежуточные компоненты сети при определении дальнейшего направления движения трафика не принимают самостоятельно никаких решений, а следуют указаниям, содержащимся в пакетах. Маршрутизация от источника легко реализуется на промежуточных узлах в сети, но требует полного знания всех маршрутов на конечных компонентах. Из-за этого конечные узлы должны обладать высокой производительностью, чтобы хранить все таблицы маршрутизации. Это особенно касается сетей с большим количеством компонентов.
При одношаговой маршрутизации все компоненты сети, принимающие участие в передаче потоков, самостоятельно определяют, какому следующему узлу их необходимо отправить. Решение принимается на основании анализа содержащегося в пакете адреса получателя. При этом полный маршрут для передачи трафика складывается из одношаговых решений, принятых компонентами сети. К таким технологиям, например, относится многопротокольная коммутация информационных потоков по меткам (Multiprotocol Label Switching, MPLS).
В зависимости от способа формирования таблиц маршрутизации, одно-шаговую маршрутизацию можно разделить на три класса [1-3], [5-7] (рис. 1.1): - простая (по умолчанию); - фиксированная (статическая); - адаптивная (динамическая).
Простая {по умолчанию) маршрутизация осуществляется по принципу устройств канального уровня (повторители, коммутаторы). В общем случае для простой маршрутизации на выбор дальнейшего пути пакета влияет лишь статическое априорное состояние сети. Ее текущее состояние: загрузка и изменение топологии из-за отказов - не учитывается. В алгоритмах простой маршрутизации таблица маршрутизации либо вовсе не используется, либо строится без участия протоколов маршрутизации. Имеется три вида такого способа маршрутизации: случайная маршрутизация, лавинная маршрутизация и маршрутизация по опыту (рис. 1.1) [4].
При случайной маршрутизации каждый маршрутизатор (роутер), получив пакет, отправляет его на случайный интерфейс. Такой подход не гарантирует быстрой и качественной доставки пакета адресату. А в ряде случаев пакет вообще уничтожается при превышении TTL (Time То Live) — времени жизни [7]. При лавинной маршрутизации роутер шлет пакет по всем активным интерфейсам (портам, подключенным к маршрутизатору). Недостаток этого алгоритма — засорение сети избыточной служебной информацией.
При случайной и лавинной маршрутизациях не используются таблицы маршрутизации, в которых отражена топология сети на данный момент времени. В самом общем случае таблица маршрутизации содержит адрес сети назначения, адрес следующего узла на пути к этой сети и метрику (стоимость) пути.
При маршрутизации по опыту шлюз накапливает информацию о маршрутах, пересылая данные лавинным образом. После составления некоторой таблицы, он учится направлять пакеты по нужному направлению.
Алгоритмы данного метода маршрутизации просты в реализации, но при этом не гарантируют доставку пакета по указанному адресу за приемлемое время и по рациональному маршруту без перегрузки сети. Поэтому простая маршрутизация не нашла применения в больших сетях.
Уровень резервирования пропускной способности
Задача маршрутизации заключается в определении эффективных путей прохождения потоков трафика через сеть передачи данных. Эффективность выражается, во-первых, в предоставлении каждому потоку гарантированного качества обслуживания (в соответствии с его классом сервиса), а во-вторых, в рациональном использовании ресурсов сети. Решение этой задачи в общем виде является достаточно сложным, поэтому чаще всего применяется её декомпозиция на три уровня. На первом уровне для каждого класса сервиса осуществляется резервирование необходимой пропускной способности. На выходе первого уровня для каждого класса s формируется наложенный на исходную сеть граф Gv =(V", Es). Узлы Vs графа представляют собой доступные для трафика класса сервиса s узлы коммутации (маршрутизаторы), а ребра ES — доступные для трафика класса s каналы связи. Следует отметить, что множество узлов Vs также включает в себя узлы-источники трафика класса s и узлы-приемники. На втором уровне по графу Gs определяется множество допустимых маршрутов, на третьем уровне решается оптимизационная задача размещения потоков класса s по полученным допустимым маршрутам. Ниже рассматривается постановка задачи каждого уровня.
Для каждого класса сервиса seS определяется значение максимально допустимого коэффициента загрузки р оп. р лол - показывает, какую долю от пропускной способности линии может использовать трафик класса сервиса 5. Тогда максимально допустимый поток класса сервиса s, который может пройти через линию (k,l):
Суммарный допустимый коэффициент загрузки линии (,/) потоками класса сервиса s и более приоритетными классами сервиса: R" =YPS . ДОП / J г доп
Коэффициент R №n определяет максимальную пропускную способность линии (,/), которую может использовать суммарный поток Л Я0П, т.е. максимально допустимый поток класса сервиса s и более приоритетных классов сервиса.
В момент появления новых потоков или при изменении средних интенсивностеи существующих на заранее определенное значение в сети уже могут передаваться потоки трафика некоторых классов сервиса. Определим значение доступной пропускной способности ДЛ, для дополнительного трафика класса сервиса s и более приоритетных классов.
Пусть Л„ реальный поток трафика класса s и более приоритетных классов, проходящий по линии (,/). Тогда АЛИ=ЛИДОО-ЛІ,.
Отметим, что если доступная пропускная способность какой-либо линии для трафика класса s равна нулю, то данная линия не учитывается при построении графа G .
Суммарный поток трафика класса s и более приоритетных классов сервиса (Лурас), который может передаваться по линии (,/) определяется следующим выражением: ., Крас ЄСЛИДЛ Ирас 0 Лк1 рас - І .., .. W [Лид,», еслиДЛ О ГДЄ Л1,рас=Х(Л1+ рас), АЛИ рас Ли доп - Аи рас . Значения интенсивности потока Лрас определяются в ходе решения задачи третьего уровня.
Выражения (1) позволяют реализовать в сети механизм приоритетной подмены, благодаря которому трафик более приоритетного класса сервиса может вытеснять менее приоритетный. В данном случае рассматривается простейшая схема приоритетной подмены, когда любой поток приоритета s может вытеснять любые менее приоритетные потоки.
Особенности объектно - ориентированного программирования в языке Object Pascal
Для программной реализации поставленной задачи по созданию набора допустимых маршрутов и дальнейшему распределению по ним потоков трафика использовалась интегрированная среда разработки Delphi 7. Указанная среда является комбинаций нескольких важнейших технологий: - высокопроизводительный компилятор в машинный код; — объектно — ориентированная модель компонент; - визуальное построение приложений из программных прототипов; — масштабируемые средства для построения баз данных.
Достоинства и возможности компилятора Delphi 7 полностью зависят от возможностей и достоинств базовой платформы .Net Framework. По существу, возможности базового компилятора ограничены тем, что предусмотрел для него производитель. При разработке на платформе .Net возможно буквально все, от обычного сложения двух целых чисел до создания компилятором кода, который управляет элементами и типами самой платформы .Net Framework [46]. Во все редакции Delphi 7 включена предварительная версия (preview) компилятора Delphi for .Net, позволяющая создавать приложения для платформы .Net [47]. Поэтому компилятор Delphi 7 позволяет легко осуществить задуманную реализацию предложенного алгоритма.
В процессе построения приложения разработчик выбирает из палитры уже готовые компоненты. Еще до компиляции он видит результаты своей работы: после подключения к источнику данных они отображаются на форме. В этом смысле проектирование в Delphi мало чем отличается от проектирования в интерпретирующей среде, однако, после выполнения компиляции получается код, который исполняется в 10 — 20 раз быстрее, чем то же самое, сделанное при помощи интерпретатора. Кроме- того, в Delphi компиляция производится непосредственно в «родной» машинный код, в то время как существуют компиляторы, превращающие программу в так называемый р-код, который затем интерпретируется виртуальной р-машиной. Это не может не сказаться на фактическом быстродействии готового приложения.
Delphi позволяет разработчикам строить приложения весьма быстро из заранее подготовленных объектов, а также дает им возможность создавать свои собственные объекты для среды. Никаких ограничений по типам объектов, которые могут создавать разработчики, не существует. Все в Delphi написано на нем же, поэтому разработчики имеют доступ к тем же объектам и инструментам, которые использовались для создания среды разработки. В результате нет никакой разницы между объектами, поставляемыми Borland или третьими фирмами, и объектами, которые возможно создать самому. Все это упрощает задачу разработчикам различных приложений.
В стандартную поставку Delphi входят основные объекты, которые образуют иерархию более чем из 270 базовых классов. Но если возникнет необходимость в решении какой-то специфической проблемы на Delphi, прежде чем попытаться начинать решать проблему "с нуля", следует просмотреть список свободно распространяемых или коммерческих компонент, разработанных другими фирмами.. Количество этих фирм в настоящее время несколько сотен. Эта особенность позволит в дальнейшем в программной разработке использовать внешние дополнительные компоненты.
Delphi предназначен как для профессионалов-разработчиков корпоративных информационных систем, так и для рядовых программистов, которым необходимо решить свои задачи, не привлекая для этого специалистов со стороны.
В Delphi 7 включено множество новых возможностей, касающихся среды разработки, веб-технологий, веб-сервисов и др. [48]. Изменения, затронувшие IDE (Integrated Development Environment) - Интегрированную Среду Разработки, коснулись палитры компонент, достройщика кода, отладчика и настроек редактора кода. В палитре компонент появились новые закладки. Окно просмотра сообщений отладчика (Watch List) имеет множество закладок для облегчения процесса отлова ошибок. Каждую закладку можно настроить -отображать ее или спрятать. Диалоговое окно Run Parameters теперь имеет новую настройку: рабочий каталог (Working Directory), указав который, можно настроить каталог, используемый для отладки.
Из изменений в среде разработки следует упомянуть о наличии в меню команды View/Additional Message Info, с помощью которой можно получить последнюю версию списка сообщений компилятора с web-сайта Borland. Следует отметить, что в диалоге Project Options можно указывать, какие именно типы сообщений компилятора необходимо отображать.
Все вышеперечисленные свойства Delphi 7 послужили основной причиной использования данной среды для программной реализации предложенного выше алгоритма.
Использование объектно-ориентированного программирования в программной реализации
Эффективность метода предполагается оценивать, анализируя трудоемкость алгоритмов поиска маршрута. При этом учитывается набор из наименьшего количества ветвей в минимальном направленном графе с проверкой на связность по сравнению с исходным графом.
Для этого проведена серия экспериментов, в которых из исходных произвольных сетей по разработанному алгоритму строятся направленные графы. При этом каждый раз анализируется отношение общего числа ветвей в исходной схеме к числу ветвей в минимальном направленном графе. Таким образом возможно оценить выигрыш по количеству ветвей в направленном графе по сравнению с исходным. При этом предполагается, что таблицы маршрутизации будут содержать меньший объем данных, то есть объем будет уменьшаться с уменьшением числа ветвей в минимальном направленном графе.
Для реализации такого подхода серия экспериментов проводится посредством моделирования сетей в виде графов, содержащих заданное количество узлов и ветвей. Причем количество узлов v задается в процессе эксперимента, а количество ветвей Е выбирается из условия: v-l v(v-l) (4.1) Чтобы распределить это количество ветвей (ребер) графа между узлами, пользователю также необходимо задать вероятность их появления между узлами. Следует отметить, что каково бы ни было это значение, вероятность появления несвязного графа будет крайне мала ( 0,01), потому что имеется ограничивающее условие (4.1). В силу этого, значение вероятности будет влиять только на сосредоточенность ребер у первых или последних узлов. Следовательно, фактами появления несвязного графа можно пренебречь, и на общие результаты анализа это практически не скажется.
С учетом перечисленных выше параметров генерируется случайный граф. Для всех пар узлов источник - получатель тц строится минимальный направленный граф с проверкой на связность (см. гл. 2) и в нем определяется число ветвей Е.
Чтобы оценить выигрыш в количестве ветвей для заданной пары (v,E), следует найти среднее число ребер Е во всех построенных минимальных графах, а затем произвести расчет: D = , (4.2) Е где Е-% - общее (изначальное) число ветвей в исходном графе.
Выражение (4.2) показывает, во столько раз общее количество ветвей в первоначальной схеме больше того количества ветвей, которое было получено в результате работы предложенного алгоритма.
Далее задается другое количество ветвей из условия (4.1) для того же числа узлов. И для каждой такой пары (v,) рассчитывается выигрыш. Таким образом, выполняется необходимое количество итераций (переборов разных значений Е) для одного значения v.
Для того, чтобы оценить выигрыш, который дает алгоритм в целом, необходимо провести серию экспериментов для разных значений v. После чего уже возможно сделать общие выводы. При этом производится построение графика зависимости как- -, так и -Л-. Во втором случае показывается, какую долю составляет в среднем количество ветвей в минимальном направленном графе, по сравнению с исходным графом для заданной пары (v,E ).
В литературе рассматривается несколько стандартных представлений графов - в виде матрицы смежности, в виде списков смежных вершин и др. [58, 69-70]. Так как матрица смежности является более наглядным решением для анализа эффективности [60], приведенного в диссертационной работе, то и в
программной разработке использовался именно этот способ. Справедливости ради, стоит отметить, что объектно-ориентированный подход, использующийся в главах 3 и 4, с одинаковым успехом позволяет реализовать как матрицу смежности, так и список смежных вершин [59, 61].
Для моделирования системы использовалась программная реализация, описанная в главе 3. Кроме того, в модуль uGraphElements был включен процесс генерации графа. В форму MainForm были внесены изменения, связанные с вкладкой «Анализ», а в модуль Main добавлены процедуры, описывающие генерацию графа, расчеты для построения графика зависимости, а также отображение полученной информации. Помимо изменения прежних модулей и форм появился новый модуль uExcel, описывающий перенос данных из Delphi в среду Microsoft Office Excel. Это стало необходимо для дальнейшей обработки данных и сохранения их в удобной форме.
Процедуры создания нового файла описаны в п. 3.4, поэтому здесь их описание опускается. В то время, как основная часть алгоритма представлена на вкладке «Алгоритм», все действия по анализу вынесены на отдельную вкладку «Анализ». Она содержит основные зоны: панель для ввода данных, рабочее поле и поле вывода данных (рис. 4.1).
