Содержание к диссертации
Введение
Список сокращений и основных обозначений 4
Введение 5
1. Анализ принципов построения корпоративных сетей 13
1.1. Особенности построения корпоративной сети 13
1.2. Разновидности архитектур согласующих центров 18
1.2.1. Коммутаторы 19
1.2.2. Маршрутизаторы и шлюзы 23
1.3. Принципы построения согласующих центров корпоративной сети 24
1.4. Концептуальная модель адаптивного согласующего центра 27
1.4.1. Допущения при построении концептуальной модели АСЦ 28
1.4.2. Технические средства АСЦ 31
1.5. Критерии производительности согласующих центров 48
1.6. Формулировка задачи исследования 51
Выводы по разделу 54
2. Комплекс моделей адаптивного согласующего центра обработки информации 56
2.1. Математическое обеспечение оценки ВВХ АСЦ 56
2.2. Модель адаптивного согласующего центра в качестве коммутатора с общей памятью 61
2.3. Модель адаптивного согласующего центра в качестве коммутатора на базе общей шины 71
2.4. Модель адаптивного согласующего центра в качестве маршрутизатора/шлюза с общей памятью 77
2.5. Расчет емкости буферной памяти КМ 89
Выводы по разделу 89
3. Алгоритм проектирования адаптивного согласующего центра 91
3.1. Алгоритм оптимизации структуры адаптивного согласующего центра 91
3.1.1. Общая идея генетических алгоритмов 91
3.1.2. Операторы генетического алгоритма 97
3.1.3. Модели генетических алгоритмов 101
3.1.4. Постановка задачи оптимизации структуры АСЦ 104
3.2. Процедура параметрической настройки АСЦ 109
3.3. Разработка программной среды 110
3.4. Алгоритм проектирования АСЦ 111
3.5. Пример оптимизации структуры шлюза с помощью разработанных инструментальных средств 114
Выводы по разделу 115
Заключение 117
Литература 119
- Особенности построения корпоративной сети
- Математическое обеспечение оценки ВВХ АСЦ
- Модель адаптивного согласующего центра в качестве маршрутизатора/шлюза с общей памятью
- Общая идея генетических алгоритмов
Введение к работе
В современном мире инфокоммуникационных технологий, учитывая развивающиеся рыночные отношения, шаги производственной группы, коммерческой организации, корпорации или другого объединения иной формы, по созданию эффективной системы информационных связей как, для взаимодействия внутри компании, так и для взаимодействия с другими организациями, или улучшению уже существующей системы являются'неотъемлемой частью успешного функционирования компании. Основой такой системы информационного обеспечения-стали сетевые технологии-[30; 62].
Корпоративная сеть, построенная' с применением современных сетевых технологий, является одним из главных ресурсов крупной организации, фирмы. Отсутствие'этого ресурса, выход его из строя или неэффективное функционирование приводит к сложностям выполнения функций управления и производственного процесса, избыточным рискам и повышенным затратам [35]. Данные обстоятельства указывают на важность использования удобных в обслуживании, высокопроизводительных, надежных и эффективных с точки зрения затрат корпоративных сетей.
Корпорация является сложной, распределенной структурой, зачастую имеющей международное распространение, но требующей единой-информационной инфраструктуры [4, 17, 64].
Существующие сети, подвергаемые объединению в рамках корпорации, часто используют различное оборудование и программное обеспечение. Для обеспечения взаимодействия необходимо объединять такие часто несовместимые (разнородные) сети. Разработка же сетевых приложений осложняется из-за необходимости организовать совместную работу частей, выполняющихся на разных машинах. Функции по согласованию несовместимых параметров разнородных сетей ложатся на устройства межсетевого взаимодействия или согласующие устройства (СУ). Уже давно задача согласования и сопряжения решается установкой согласующего сетевого оборудования разного уровня и на-
значения (мостов, коммутаторов, маршрутизаторов), обеспечивающего необходимое преобразование разнородного трафика с помощью программного обеспечения и аппаратных решений. Для решения задачи согласования неоднородных сетей применяют различные подходы — мультиплексирование, трансляцию или инкапсуляцию протоколов.
Согласующие устройства внутри корпоративной сети выполняются* в виде многопроцессорных многопортовых устройств, так как,.выполняя основную функцию сопряжения нескольких разнородных сетей, они вынуждены обрабатывать большие потоки данных, что приводит к необходимости параллельной обработки [42].
Параллельная обработка информации включает в себя процессы приема поступающих на порты устройства информационных кадров от различных подсетей, анализа определенной части служебной информации заголовков кадров всеми протоколами, участвующими в процессах обработки, определение порядка обработки, принятия' решений по дальнейшему продвижению кадров внутри устройства, передачи обработанных информационных кадров в исходящие каналы подсетей назначения. Все эти операции предполагают сложную организацию структуры системы (разные по типу связи между элементами системы, характеризующиеся- внутренними свойствами), что требует соответствующих знаний по системному анализу, исследованию операций и системному программированию [13, 38, 45, 59, 65]. Такие сложные устройства с их многофункциональной аппаратной и программной реализацией можно назвать не просто сетевыми устройствами, а сетевыми центрами (СЦ) по аналогии с центрами коммутации в телефонных сетях общего пользования.
При создании или расширении сети, как правило, устанавливается самое высокопроизводительное оборудование сопряжения сетей, имеющееся на рынке этого оборудования. На практике, согласующие устройства оказываются загруженными максимум на четверть, а в ближайшей перспективе не видно признаков к повышению нагрузки. Но при объединении с другой высокопроизводительной сетью, такой избыточной производительности может не хватить. По-
7 этому рациональнее применять обоснованные интеллектуальные решения-, чем приобретать и устанавливать новое согласующее оборудование: целесообразнее функционально или количественно преобразовывать уже имеющийся узел сети, чем каждый раз, когда это необходимо, заменять его на другой. Необходимо искать новые решения, позволяющие динамически настраивать архитектуру многопроцессорного СЦ в зависимости от степени разнородности взаимодействующих сетей и формировать оптимальные (рациональные) конфигурации, обеспечивающие необходимое качество обслуживания и имеющие минимальную стоимость. Т.е. необходимо иметь возможность приспосабливать СЦ к изменениям окружающей среды, другими словами - адаптировать. Такие решения должны стать основой эффективного функционирования корпоративной сети, что подразумевает оптимизацию структуры- сети, более «быстрое» и удобное администрирование сети, сокращение затрат на закупку нового оборудования.
Таким образом, объединение в интегрированную систему различных информационных ресурсов распределенной системы актуализирует разработку эффективных методов, средств и алгоритмов построения согласующих устройств разного уровня архитектуры и назначения.
Большое значение при разработке средств проектирования согласующих устройств имеет принцип структурно-функционального анализа моделей информационных систем, который на этапе системного проектирования! применяется для анализа вариантов тех или иных технических решений, что в свою очередь приводит к обоснованному выбору [19, 22, 62].
Главным при проектировании СЦ становится математическое моделирование и вычислительный эксперимент на модели [10, 11, 20, 22, 23, 43, 53, 66, 61, 72], поскольку практически отсутствует возможность использования физических моделей и натурного эксперимента при разработке таких систем.
Результаты исследований ученых А.В. Бутрименко, В.П. Ильина, A.M. Александрова, О.И. Кутузова, Б.Я. Советова, С.А. Яковлева, Л. Клейнрока, М.
8 Шварца и ряда других составляют теоретическую базу моделирования сетей и составляющих их элементов [15, 17, 25, 31, 52, 53, 54, 75].
Математической базой методологии структурно-функционального анализа многопортовых мультипроцессорных систем, какими являются согласующие центры, являются сети массового обслуживания'(СеМО)-[22, 76]. В-виду вероятностного характера данных, поступающих в систему, детерминированной их обработки, невозможности использования^ физических моделей, разработка моделей теории СеМО для анализа и-проектирования (Щ крайне необходима.
Возможность использования моделей СеМО'определяет предположение о независимости, суть^ которого* сводится к следующему: времена передачи сообщений по разным каналам связи предполагаются независимыми случайными величинами. С другой стороны, очевидно, что-длительности обслуживания сообщения в разных- каналах пропорциональны длине этого сообщения; а значит, зависимы [27].
Наряду с тем, что модели СеМО'не могут полностью отражать сложные информационные процессы в сетях или узлах сети, опыт проектирования и измерений характеристик реальных сетей и узлов говорит о том, что такие модели являются достаточно точным и почти единственным хорошо разработанным математическим аппаратом, позволяющим осуществлять выбор альтернативных вариантов; расчета и оптимизацию характеристик- на этапе проектирования СЦ. Наиболее разработана теория* экспоненциальных СеМО и выражения для расчета их ВВХ.
Задачу выбора оптимальной (рациональной) архитектуры СЦ любого уровня предложено решить с помощью разработанного алгоритма; в основе которого находится генетический алгоритм оптимизации.
Генетический алгоритм (ГА) был разработан американским ученым Джоном Холландом в 1975 году [79], а в 1989 г. сделаны шаги по дальнейшему изучению природы ГА ученым Д. Голдбергом [78]. В-дальнейшем стали использоваться* кодированные множества параметров ГА вместо» самих параметров для общей эффективности работы ГА, определена необходимость правильной на-
стройки параметров ГА для решенияоптимизационных задач и т.п. Все это дало толчок для всех последующих исследований [18, 21, 81].
Генетический алгоритм в приложении задач дискретной оптимизации был получен сравнительно недавно 1998-1999 гг. Сила генетических алгоритмов в том, что этот метод чрезвычайно гибок. Алгоритм успешно справляется с широким кругом задач оптимизации даже при- том, что о системе известен минимум информации, как это часто бывает в сложных технических системах [18, 39, 68].
Учитывая сказанное выше, можно сделать следующий вывод: совокупность задач по проектированию СЦ, определяющих во> многом жизнеспособность корпоративных сетей, и разработке соответствующих моделей и алгоритмов для оценки ВВХ согласующего центра представляет собой важную научную задачу, имеющую большое значение для экономики страны.
Целью работы является разработка моделей и алгоритмов оценки характеристик адаптивных согласующих центров обработки информации корпоративной сети.
Для достижения названной цели необходимо решение следующих задач:
Анализ особенностей построения и процессов функционирования согласующих центров корпоративных сетей.
Разработка комплекса моделей оценки характеристик адаптивного согласующего центра разной архитектуры.
Разработка алгоритма оптимизации структуры адаптивного согласующего центра.
Разработка алгоритма проектирования адаптивного согласующего центра корпоративной сети.
Объектом исследования являются адаптивные согласующие центры обработки информации корпоративной сети, выполненные в виде многопроцессорных вычислительных систем.
10 Предметом исследования являются закономерности процессов функционирования адаптивного согласующего центра при согласовании работы сегментов корпоративной сети.
Методы исследования. Решение сформулированной в работе проблемы разработки моделей оценки характеристик адаптивного согласующего центра обработки информации и алгоритмов-поиска рациональной структуры базируется на математических методах системного анализа, исследования операций, теории вероятности и случайных процессов, теории алгоритмов, теории оптимизации и теории массового обслуживания.
Научная* новизна работы.
Научная новизна работы состоит в разработке моделей оценки характеристик АСЦ и алгоритма проектирования адаптивного согласующего центра- корпоративных сетей, обеспечивающего нахождение структур АСЦ* удовлетворяющих сетевым требованиям.
Новые научные результаты:
Концептуальная модель адаптивного согласующего центра, разработанная, на основе принципов* построения, и функционирования корпоративных сетей, отличается определением набора структурных модулей, обеспечивающего построение всевозможных вариантов АСЦ, что позволяет применять единый подход к проектированию АСЦ разной архитектуры.
Комплекс моделей- оценки характеристик адаптивного согласующего центра обработки информации отличается возможностью оценки соответствия характеристик АСЦ разной архитектуры, полученных с помощью моделей, требуемым характеристикам согласования независимо от функциональных возможностей АСЦ.
Алгоритм оптимизации структуры адаптивного согласующего центра отличается использованием моделей оценки характеристик АСЦ на каждом шаге алгоритма, что позволяет построить рациональную структуру АСЦ.
4. Алгоритм проектирования адаптивного согласующего центра корпоративной сети отличается выполнением полного набора комбинированных действий, как подготовительных, направленных на определение значений требуемых сетевых величин, номинальных значений параметров АСЦ и т.п., так и вычислительных, реализующих модели и оптимизационный алгоритм на ЭВМ, что позволяет осуществлять проектирование рациональной (субоптимальной) структуры АСЦ.
Основные результаты, полученные в работе и выносимые на защиту:
Концептуальная модель адаптивного согласующего центра.
Комплекс моделей оценки характеристик адаптивного і согласующего центра разной архитектуры.
Алгоритм оптимизации структуры адаптивного согласующего центра.
Алгоритм проектирования адаптивного согласующего центра корпоративной сети.
Практическая ценность полученных результатов диссертационной работы заключается в разработанных моделях оценки функциональных характеристик АСЦ, от значения которых зависит выбор структуры и аппаратной реализации АСЦ, алгоритмах и программного обеспечения, реализующих проектирование АСЦ.
Автор является победителем конкурса грантов среди студентов и аспирантов г. Санкт-Петербурга в 2006 г., в отчете которого представлены основные результаты по теме диссертации.
Апробация результатов работы. Предлагаемые решения и результаты диссертационной работы докладывались и обсуждались на одной международной, одной Всероссийской НТК и на НТК профессорско-преподавательского состава СПб ГУТ в 2004 - 2008 гг.
12 Публикации. По теме диссертационной работы опубликовано 5 научных работ, из них - 2 статьи из перечня изданий, рекомендованных ВАК, и 3 работы — в научных трудах международных и Всероссийских конференций.
Структура и объем диссертации. Диссертация состоит из введения, трех разделов, заключения, списка литературы, включающего 81 наименование. Основная часть работы изложена на 125 страницах машинописного текста. Работа содержит 21 рисунок, 2 таблицы.
Особенности построения корпоративной сети
Корпорация является сложной, распределенной структурой, т.к. предпри-ятия, отделения, департаменты и т.п., входящие в корпорацию или ведомство, могут располагаться в различных частях страны или мира и на значительных расстояниях друг от друга. Чтобы централизованно управлять таким объедине-нием предприятий используется корпоративная сеть связи, в состав которой для связи отделений и административных офисов корпораций могут входить магист-ральные (WAN – world area networks) и региональные сети (MAN – metropolitan area networks). Корпоративные сети связи, расположенные на территории Российской федерации, входят в состав единой сети электросвязи Российской Федерации и могут относиться к категории выделенных сетей связи, технологическим сетям связи и ведомственным сетям связи в зависимости от назначения и собственни-ка такой сети.
Отличительными особенностями современных корпоративных сетей явля-ется высокая степень неоднородности (гетерогенности) [24], что выражается в при-менении различных сетевых технологий, необходимости обработки разнород-ной информации, а также в необходимости обслуживания большого числа пользователей, использующих различные сетевые службы. Для пользователя же корпоративная сеть должна обеспечивать высокий уровень сервиса, как по составу прикладных услуг, так и по характеристикам качества предоставления услуг [48, 49].
Интеграция неоднородных подсетей в рамках корпоративной сети дос-тигается включением в каждую подсеть дополнительных согласующих уст-ройств [37], которые для каждой из сопрягаемых подсетей выглядят как обыч-ные узлы сети. Такой подход определяет автономность подсетей, когда сете-вые протоколы, протоколы управления и другие службы в каждой подсети ос-таются неизменными. В этом случае требования к управлению сети в целом повышаются, но каждая подсеть будет претерпевать незначительные измене-ния, а согласование неоднородных подсетей осуществляться с помощью со-гласующего оборудования. Существует набор основных требований, предъявляемых к современным корпоративным сетям: 1) надежность – является одним из факторов, определяющих непрерывность деятельности организации; 2) производительность – рост числа узлов обработки информации и объема передаваемых по сети данных предъявляет постоянно возрастающие требова-ния к пропускной способности используемых каналов связи и производитель-ности устройств, образующих сеть; 3) экономическая эффективность – рост масштаба и сложности корпоратив-ных сетей неминуемо приводит владельца или арендатора сети к мыслям об экономии средств на создание, модернизацию и эксплуатацию сети; 4) информационная безопасность – обработка и хранение в сети конфиденци-альной информации выводит информационную безопасность в число основных аспектов стабильности и безопасности бизнеса в целом. Очевидно, что удовлетворение данных требований в первую очередь за-висит от используемых сетевых согласующих центров, потому что эти узлы в наибольшей степени влияют на перечисленные параметры. В настоящее время в мире накоплен значительный опыт проектирования, исследования и построения корпоративных сетей с интеграцией служб [67]. Среди интенсивно развивающихся в настоящее время и наиболее пер-спективных проектов корпоративных сетей следует отметить BcN (Broadband Convergence Network) или широкополосные конвергентные сети (ШКС), объе-диняющие концепции сетей следующего поколения NGN (Next Generation Net-works), широкополосного мультисервисного доступа и сенсорных сетей.
Новейшие разработки различных сетевых технологий, такие как Triple-Play (передача данных, речи и видео в единой среде передачи), IMS (IP Multi-media Subsystem) как вариант концепции NGN, WiMAX (Worldwide Interoperability for Microwave Access) как технология широкополосного беспро-водного доступа, 802.11 (WiFi) как вариант технологии сенсорных сетей и мно-гие другие технологии, способны обеспечить ШКС всем набором услуг переда-чи разнородных данных, а значит обеспечить потребности пользователей кор-поративной сети в данных услугах.
Внедрение в компаниях новых информационных технологий для ведения бизнеса, таких как ERP (Enterprise Resource Planning — управление ресурсами предприятия), CRM (Customer Relationship Management - концепция управления отношениями с клиентами), EDI (Electronic Data Interchange - электронный об-мен данными) и т.д., порождает необходимость взаимодействия этих систем для обеспечения обмена информационными потоками между ними. Долгое время в корпоративных сетях первостепенной была задача обеспечения рече-вых межличностных взаимодействий пользователей, и под корпоративными се-тями понимали локальные вычислительные сети (LAN – local area networks), обеспечивающие доступ сотрудников к УАТС (учрежденческая автоматическая телефонная станция), предоставляющей речевые услуги. Но на сегодняшний день просматривается динамика в сторону увеличения передачи в сети именно данных, необходимых для работы различных информационных систем ведения бизнеса, которые стали активно внедряться [77].
Математическое обеспечение оценки ВВХ АСЦ
Для оценки вероятностно-временных характеристик АСЦ, как мульти-процессорной системы, разных уровней архитектуры используется математиче-ский аппарат сетей массового обслуживания – СеМО.
За основу таких моделей принята теорема Дж. П. Джексона, определяющая ус-ловия декомпозиции СеМО на отдельные системы массового обслуживания (СМО) [5, 44]. Наиболее разработана теория экспоненциальных СеМО, которые позволяют получить оценивание характеристик в аналитическом виде. Так как исследуемая мультипроцессорная система может состоять из большого количе-ства модулей – канальные модули, обрабатывающие модули, секции общей па-мяти или временные окна общей шины, принятые нами в качестве обслужи-вающих приборов, связанных между собой, для разработки аналитических мо-делей принята именно сетевая модель системы массового обслуживания. Таким образом, модули, представляющие собой отдельные системы массового обслу-живания (СМО), АСЦ образуют сеть. Использование именно экспоненциаль-ных СеМО обусловлено наличием разработанного метода оценки характери-стик такой сети, названного методом расчета средних значений [44, 46].
Теория СеМО изучает методы анализа очередей при взаимодействии от-дельных СМО сети, состоящих из некоторого числа обслуживающих приборов (одинаковых) и буферов для хранения ожидающих в очереди на обслуживание заявок [6, 69], и потоков заявок между ними. Связи между СМО определяют структуру сети, а заявки, циркулирующие по сети, являются сообщениями (па-кетами), требующими обслуживания в АСЦ [55]. Важнейшей характеристикой СеМО является вероятность состояния сети [5, 6, 26, 27, 44, 76]. Чтобы определить это значение вероятности в определен-ный момент времени протекания процесса обработки заявок в сети, исследуется случайный процесс, представляющий собой модель марковского или полумар-ковского процесса [5, 44].
Функционирование экспоненциальных СеМО описывают марковским процессом в непрерывном времени. Экспоненциальной СеМО называется то-гда, когда потоки заявок, поступающие в каждый узел сети, имеют пуассонов-ское распределение, а времена этапов обслуживания заявки - экспоненциальное [55]. Это делает независимыми между собой этапы обслуживания [5]. В подразделе 1.6 определены две основные характеристики АСЦ, кото-рые, для каждого типа устройства, каждого варианта внутренней структуры, необходимо оценить на предмет их соответствия заданным значениям: средняя задержка и производительность. Для их оценки используется аппарат замкну-тых экспоненциальных сетей массового обслуживания (ЗСеМО), а именно, так называемая, рекуррентная процедура [2, 44, 46], позволяющая найти макси-мальное (конечное) число заявок, которое может быть обработано сетью дан-ной конфигурации, после чего с помощью несложных расчетов находятся сред-ние времена задержки и производительность. Дело в том, что в замкнутых Се-МО циркулирует конечно число заявок. Заявки извне не могут попасть в такую систему, т.к. появляющаяся в выходящем потоке сети заявка сразу же вызывает возникновение новой заявки на входе сети, т.е. выход как бы замыкается на вход. Для описания систем, в которых в каждый момент времени находится фиксированное число заявок (устройств пакетной обработки, АСЦ) и имеется большое количество источников заявок, применяются именно замкнутые Се-МО [35]. Помимо замкнутых СеМО существуют также разомкнутые СеМО, кото-рые применяются для описания систем, имеющих переменное количество зая-вок. Обработанные сетью заявки в данном случае покидают систему. Данная модель, как видно, не подходит для описания АСЦ, кроме того, для разомкну-тых СеМО невозможно применить метод анализа средних значений, который необходимо применять, когда в сети имеется большое количество узлов [76]. Существует два метода исследования СеМО: метод анализа средних зна-чений [76] и алгоритм свертки [22, 26, 76], предполагающий вычисление нор-мализующей константы. Когда число узлов в сети массового обслуживания зна-чительно возрастает, например, строится модель для АСЦ, имеющего большое количество канальных портов, которые являются отдельными СМО в модели, расчет вероятностей состояний сети, а значит нормализующей константы, ста-новится невозможен даже на современных ЭВМ – практически невозможным становится расчет вероятностей состояния сети. Поэтому, в работе использует-ся метод анализа средних значений, который позволяет избежать этих трудно-стей при определении таких показателей функционирования, как среднее время задержки и производительность [41].
Модель адаптивного согласующего центра в качестве маршрутизатора/шлюза с общей памятью
Рассмотрим следующий тип АСЦ, который выполняет функции маршру-тизатора или шлюза. Как было сказано в подразделе 1.2.2, такие устройства ра-ботают на 3-м уровне ЭМВОС и выше. Поэтому, наряду с задержками, вноси-мыми на первых двух нижних уровнях, в АСЦ данного типа будут задержки, присущие процессам, выполняемым на верхних уровнях ЭМВОС – задержки на выполнение протоколов верхних уровней.
В данном подразделе представлена модель оценки характеристик шлюза на базе общей памяти, как одной из основных схем внутренней коммутации ИК современных многофункциональных устройств. Адаптивный согласующий центр обработки информации, функциони-рующий в качестве шлюза, выполняет процессы приема входящих в устройство информационных кадров, их коммутации посредствам общей памяти (ОПП), обработку пакетов процессорами, реализующими заданные уровневые прото-колы, и передачи обработанных кадров в исходящий канал [3, 40]. Каждый па-кет, записанный КМ в ОПП и требующий обработку в ОМ, пересылается в ОМ для обработки, при этом ячейка памяти (СОП) освобождается для коммутации следующих пакетов. В ОМ генерируется задание, которое обрабатывается про-токольными процессами по некоторому последовательному алгоритму (цепоч-ке команд) [49]. После обработки в ОМ пакет пересылается в СК для после-дующей передачи в КМ.
Если число ОМ N 1, одновременно может обрабатываться несколько па-кетов различными ОМ. Если пакет не находит свободного ОМ, то он ставится в очередь заданий. Как только какой-либо ОМ освобождается, пакет поступает на обработку в этот ОМ.
При выполнении процессов обработки заданий в ОМ может возникнуть необходимость доступа к различным ресурсам, находящимся в П. Как было по-казано в подразделе 1.4.2, данная область памяти логически разделена с сек-циями памяти, необходимыми для коммутации ИК. Если требуемый для обра-ботки пакета ресурс оказывается занятым, то процесс ставится в очередь к дан-ному ресурсу и его дальнейшее выполнение блокируется. После того, как тре-буемый ресурс освобождается, он занимается первым заблокированным про-цессом, и обработка пакета продолжается с того места алгоритма обработки, где она была прервана.
Надо отметить, что в случае использования аппаратной реализации СК (ОШ) общие ресурсы, необходимые ОМ для обработки пакетов, хранятся непо-средственно в каждом ОМ или общей локальной памяти всех ОМ.
Исходя из рассмотренных моделей функционирования КМ и процессов на ОМ, а также из концептуальной модели АСЦ, видно, что для шлюза, в отли-чие от коммутатора, среднее время задержки заявки будет включать еще и вре-мя обработки пакета на ОМ. Таким образом, для построения модели оценки ха-рактеристик шлюза необходимо взять модель коммутатора (либо модель с об-щей памятью, либо с общей шиной), добавить в нее процесс обработки пакета в ОМ, рассчитав при этом среднее время пребывания пакета в ОМ, и перераспре-делить нагрузку, создаваемую на ОПП.
В подразделах 2.2, 2.3 было показано, что модели оценки характеристик коммутаторов с общей памятью и общей шиной отличаются только временами прохождения кадра через СК – общую память или общую шину ( - в слу-чае общей памяти, - в случае общей шины), а также временем передачи в исходящий канал. При этом процессы прохождения кадра через КМ были иден-тичны, за исключением немного иной формулы для расчета среднего времени передачи. Таким образом, для расчета коммутатора с той или иной СК главным было определить процессы прохождения кадра, которые отличаются друг от друга.
Представленная концептуальная модель АСЦ такова, что это правило можно использовать и для случая расчета характеристик шлюза. Преимущест-вом такой модели шлюза является то, что АСЦ выполняет не только функции маршрутизатора или шлюза, но и функции коммутатора (например, к некото-рым КМ АСЦ могут быть подключены терминалы или подсети, кадры которых не требуют обработки в ОМ). Соответствующая нагрузка на ОМ создается в модели с помощью матрицы переходных вероятностей .
Общая идея генетических алгоритмов
Генетические алгоритмы (ГА) представляют собой вероятностные, эври-стические методы оптимизации, основанные на идее эволюции с помощью ес-тественного отбора [18]. Применение генетических алгоритмов возможно в различных сферах научной деятельности, там, где за короткое время необходи-мо получить оптимальное решение сложной комбинаторной задачи, и где при-менение стандартных методов поиска оптимального решения затруднено.
Каждый биологический вид целенаправленно развивается и изменяется для того, чтобы наилучшим образом приспособиться к окружающей среде [57], т.к. только сильнейшие выживают и производят потомство. Эволюция в этом смысле представляет процесс оптимизации всех живых организмов.
В каждой клетке любого живого организма, особи содержится вся гене-тическая информация, которая представляет собой набор молекул ДНК. В каж-дой такой молекуле ДНК имеется цепочка молекул нуклеотидов четырех типов. Порядок расположения нуклеотидов в ДНК и несет в себе генетическую ин-формацию клетки особи, где генетический код представляется длинной стро-кой, в которой используются всего четыре «символа». Все молекулы ДНК ок-ружены особой оболочкой, и такое образование называется хромосомой [18, 57, 70].
Каждое качество особи кодируется определенной частью хромосомы, ко-торая называется геном. При размножении особей происходит слияние двух родительских поло-вых клеток, ДНК которых взаимодействуют, и образуется ДНК половой клетки потомка. При наследовании возможны мутации, когда происходит изменение одного или нескольких генов в половых клетках одного из родителей. При этом мутированные гены, передающиеся потомку, придают ему новые свойства или качества. Если эти новые свойства или качества оказываются полезны для осо-би-потомка, то они с большой долей вероятности сохраняются в данном виде. При этом происходит скачкообразное повышение приспособленности вида [18, 70].
В начале 70-х годов ХХ века была озвучена идея использования данного природного процесса в задачах оптимизации, причем в не зависимости от сфе-ры использования полученных результатов. Высказал эту идею американский ученый Джон Холланд [79]. Его заинтересовали свойства процессов эволюции в природе и тот факт, что эволюционируют хромосомы, а не сами живые суще-ства. Холланд задумался над идеей создания компьютерной программы, кото-рая бы реализовывала алгоритм, решающий сложные научные и практические задачи путем искусственного воспроизведения процессов эволюции. Он начал работать над алгоритмами, которые оперировали двоичными последовательно-стями, получившими название хромосом. Эти алгоритмы имитировали такие процессы эволюции как скрещивание хромосом, мутация генов, селекция и т.п. Удивительным результатом работы Дж. Холланда было то, что в отсутствие ка-кой-либо информации о характере решаемой задачи, алгоритмы могли реализо-вать поиск хромосом, имеющих более «сильные» характеристики по сравнению с остальными, т.е. сымитировать естественный отбор, имеющий место в приро-де, когда выживает сильнейший. Для успешной работы алгоритма необходимо было лишь дать оценку каждой хромосоме, которая бы отражала ее приспособ-ленность.
И только в конце 90-х годов стали появляться научные работы, показав-шие применимость и значимость использования ГА в задачах оптимизации технических систем.
Как правило, задача оптимизации оперирует несколькими параметрами ( , ,…, ), а целью задачи является максимизация (или минимизация) це-левой функции , которая зависит от этих параметров. Классиче-ский пример: требуется максимизировать целевую функцию дохода компании. В этом случае параметрами функции могут являться объем производства, число сотрудников, затраты на логистику, цены на конечные продукты и т.п., кото-рые, что немаловажно, будут связаны между собой [70]. Математика давно исследует подобные задачи, и разработано немало ме-тодов их решения [56, 81]. Для достаточно простых унимодальных, гладких це-левых функций оптимальное решение можно получить довольно простыми ме-тодами (решением задач линейного программирования, методом градиентного спуска и т.п.). Но в некоторых задачах параметры могут принимать лишь опре-деленные, «дискретные» значения, а во всех остальных точках целевая функция будет не определена. В этом случае целевая функция не является гладкой, и должны применяться другие методы решения [70]. Таким образом, если на некотором множестве задана сложная функция от не-скольких переменных, генетический алгоритм способен за разумное время нахо-дить достаточно близкое к оптимальному значение функции [21]. При этом, чем больше времени отводится на выполнение алгоритма, тем более лучший результат (значение функции стремится к оптимальному) можно получить.
Найти оптимальное значение целевой функции можно с помощью пере-бора всех возможных значений параметров во всех возможных сочетаниях. При этом нет необходимости получать информацию о самой целевой функции, о ее свойствах, а можно просто свести все ее возможные варианты значений в таб-лицу. Однако чтобы решить таким способом, например, задачу определения минимального маршрута между 20-ю точками, требуется перебрать 1020 воз-можных маршрутов, а существуют и более сложные задачи. Все вышесказанное говорит о необходимости применения новых способов и средств оптимизации, которые легко могли быть осуществлены на практике [70].
