Содержание к диссертации
Введение
1. Разработка теоретических основ оптимального построения и функционирования ЛВС 14
1.1. Формальная интерпретация информационных процессов, протекающих в автоматизированных системах на базе ЛВС 14
1.2. Логико-физические основы оптимизации структуры и организации ЛВС 23
1.3. Общая формулировка задач оптимизации ЛВС 29
1.4. Построение и обоснование совокупности показателей эффективности ЛВС 33
1.5. Особенности расчета характеристик ЛВС 41
2. Разработка методов оптимизации ЛВС 47
2.1. Анализ основных организационных структур ЛВС 47
2.2. Методы структурной оптимизации ЛВС 49
2.2.1. Определение количества узлов в системе и уровня их загрузки 49
2.2.2. Обоснование структурной организации подсистем 54
2.3. Методы оптимальной организации ЛВС 58
2.3.1. Оптимизация распределения нагрузки при реализации взаимодействий типа "клиент-сервер" 58
2.3.2. Оптимизация распределения нагрузки в системе серверов 65
2.4. Комбинированные методы оптимизации ЛВС 71
3. Разработка системы эвристик для решения задач оптимизации ЛВС 80
3.1. Эвристические методы решения сложных задач. Их общая характеристика и возможности 80
3.2. Разработка эвристических методов решения задач структурной оптимизации ЛВС 83
3.3. Эвристические методы для решения задач оптимальной организации ЛВС 94
3.4. Эвристический метод решения задачи комплексной оптимизации ЛВС 112
Выводы 120
Заключение 121
Список литературы 123
Приложение.. 131
- Логико-физические основы оптимизации структуры и организации ЛВС
- Методы структурной оптимизации ЛВС
- Комбинированные методы оптимизации ЛВС
- Разработка эвристических методов решения задач структурной оптимизации ЛВС
Введение к работе
В настоящее время уровень развития средств обработки и передачи данных достиг такого этапа, когда стало возможным дальнейшее существенное улучшение технико-экономических характеристик АСУ и других информационных систем не только и не столько за счет совершенствования технических параметров вычислительных средств и каналов связи, сколько за счет перехода к новой организации информационно-вычислительных процессов -распределенной обработке данных. Системы с распределенной обработкой данных, позволяя рассредоточивать процессы хранения и обработки данных в соответствии с потребностями в информации пользователей, в состоянии обеспечить тем самым весьма широкий круг требований по оперативности управления, качеству информационного обслуживания, а также по живучести и надёжности системы в целом. Наиболее характерным представителем таких систем являются локальные вычислительные сети (ЛВС).
Однако характеристики производительности систем с распределенной обработкой данных существенно зависят от организации информационного взаимодействия между элементами таких систем. Предварительные расчеты показывают, что за счет оптимизации построения и функционирования систем такого рода их производительность может быть повышена на порядок и более. Практически это означает, что, например, ЛВС с быстродействием 10 Мб/с в результате ее оптимизации может выполнять задачи, для решения которых в обычных условиях требуется поставить ЛВС с быстродействием 100 Мб/с. С учетом того, что в подобной ситуации осуществляется переход от системы с малым быстродействием к системе со средним быстродействием, становится очевидным значительный экономический выигрыш. Чтобы подобное стало возможным, необходимо иметь соответствующий аппарат оптимизации построения и функционирования систем рассматриваемого типа.
Вопросы подобного плана неоднократно привлекали внимание исследователей и разработчиков ЛВС и систем на их основе. Однако исторически сложилось такое положение, что первые теоретические проработки вопросов построения и функционирования ЛВС были связаны лишь с проблемами организации сетевого доступа к ресурсам ЛВС [29,30,31] и вылились в создание ряда стандартов сетевого доступа, получивших широкое признание на международной арене. Серьезные проработки в этом направлении имеются и в нашей стране. Достаточно сослаться на работы [79,80], заложившие основу интервально-маркерного метода доступа, обладающего весьма хорошими эксплуатационными характеристиками.
С развитием и широким распространением различного рода информационных систем на базе ЛВС стало ясно, что повышение производительности системы за счет лишь совершенствования процедур управления доступом в ЛВС явно недостаточно, поскольку практически не обеспечивает надлежащего учета вероятностных характеристик используемой в сети информации.
Осознание этого факта явилось побудительным мотивом к развертыванию широкого круга исследований по созданию теоретического и методического аппарата, направленного на решение задач оптимального построения и функционирования ЛВС [13,14,15,16]. Особенно активно работы рассматриваемого плана начали проводиться с появлением и практической реализацией при создании информационных систем концепции распределенной обработки данных.
Первые практические реализации указанной концепции при построении реальных информационных систем позволили установить, что во многих случаях ожидания предполагаемого эффекта от внедрения систем с распределенной обработкой данных (СРОД) на базе ЛВС не вполне оправдываются. Более глубокий анализ сложившихся ситуаций позволил сделать ряд основополагающих выводов, которые обобщенно можно сформулировать следующим образом [4,5,6,11]:
(1 Эффективное функционирование СРОД на базе ЛВС может быть обеспечено лишь в том случае, когда учитываются оеальные статистические ха-
6 рактеристики обработки конкретной информации в конкретной информационной системе;
(2)Имеющиеся на рынке сетевые операционные системы не обеспечивают должного учета особенностей каждой конкретной информационной системы;
(З)Наиболее полное использование потенциальных возможностей СРОД на базе ЛВС может быть достигнуто лишь при наличии и активном использовании теоретического и методического аппарата, обеспечивающего принятие рациональных решений по построению и организации функционирования ЛВС.
Широкое развертывание работ по теоретическим и методическим аспектам построения и функционирования ЛВС в 80-90-х годах ушедшего столетия характерно для большинства ведущих государств мира. Вместе с тем, организация и проведение этих работ в разных странах имело свою специфику. Для исследователей Западной Европы и, особенно, США характерным стало широкое использование специальных стендов и мощных имитационных программных комплексов [13,33,75,101]. На этом пути был получен ряд весомых результатов, позволивших значительно улучшить эксплуатационные характеристики крупных информационных систем на базе ЛВС, реализующих концепцию распределенной обработки данных [13,101].
Однако для зарубежных разработок характерно также (хотя и в меньшей мере) использование аналитического аппарата для исследования рассматриваемых вопросов. Здесь необходимо отметить, прежде всего, работы [14,15,16].
Более детальный анализ работ зарубежных исследователей позволяет сделать некоторые обобщающие выводы, существо которых сводится к следующему.
Использование больших моделирующих стендов и имитационных программных комплексов позволяет осуществить полунатурное моделирование создаваемой информационной системы на базе ЛВС и получить характеристики ее функционирования, близкие к реальным. Вместе с тем, этот подход обладает двумя существенными недостатками.
Во-первых, он связан с весьма значительными затратами и в этом плане его осуществление под силу лишь крупным специализированным организациям, располагающим большими финансовыми возможностями.
Во-вторых, имитационное моделирование, позволяя получать достаточно точные эксплуатационные характеристики для каждого выбранного варианта построения и организации функционирования ЛВС, не обеспечивают систематизированного поиска наиболее рационального варианта, т.е. практически не позволяет решать задачу оптимизации ЛВС.
Наличие широких возможностей по использованию полунатурного имитационного моделирования ЛВС у зарубежных исследователей, по-видимому, явилось причиной того фактического положения, что развитие ими аналитических методов исследований в данной области на привело к появлению логически завершенной теории, которая бы обеспечивала решение всего комплекса основных задач, возникающих при проектировании и эксплуатации ЛВС. Известные работы зарубежных авторов в этом направлении связаны, главным образом, лишь с отдельными частными аспектами рассматриваемой проблематики. Так, значительное внимание уделено вопросам анализа очередей в системах на базе ЛВС. Здесь можно отметить достаточно широкий круг авторов, работавших в данном направлении и получивших весомые результаты [2,8,14,15,16].
Отечественные исследователи в последние два десятилетия внесли значительный вклад в развитие теории и методологии построения и функционирования ЛВС и различного рода информационных систем на их основе [1,4,5,6,9,11,12,28]. Характерной особенностью исследований, проводимых в нашей стране в рассматриваемой области, является широта охвата тематики и стремление развивать, по возможности, аналитический аппарат для решения вопросов анализа и синтеза ЛВС.
Из известных работ в этом направлении по глубине и научной значимости полученных результатов, в первую очередь, необходимо выделить работы [4,5,6,9].
В [6] реализуется оригинальный подход к оптимизации ЛВС, основанный на своеобразной интерпретации процедур последовательного развития, анализа и отбраковки неперспективных вариантов, навеянный основными идеями [22]. Этот подход был апробирован при разработке ряда реальных информационных систем на базе ЛВС и положительно себя зарекомендовал. Однако данный подход не лишен и ряда серьезных недостатков. Прежде всего необходимо отметить, что собственно схема ветвления не является логически прозрачной и ее построение требует значительной аналитической работы. Кроме того, расчетная процедура ориентирована на конкретику решаемой задачи и ее каждый раз необходимо программировать заново, что затрудняет ее прикладное использование.
Достаточно интересный подход характерен для работ [9,28], где предпринимается попытка формулировки задач оптимизации ЛВС в терминах целочисленного математического программирования. Однако в указанных работах не учитывается сложный характер зависимости временных оценок процессов функционирования ЛВС от конкретных наборов переменных назначения. Это снижает доверие к конечному результату, полученному в итоге решения оптимизационной задачи.
Более реальным в плане широкого использования в практических приложениях представляется подход, изложенный в работах [4,5], где в качестве основного аппарата также предлагаются методы математического программирования, однако оценка вариантов построения и организации функционирования ЛВС осуществляется на основе критериев затратного типа, не связанных непосредственно с временными характеристиками протекающих в ЛВС информационных процессов. Основным недостатком указанного подхода является слабая обоснованность взаимосвязи используемых показателей с эксплуатационными характеристиками ЛВС.
Значительный круг работ посвящен вопросам рациональной организации функционирования серверных станций в составе ЛВС, в частности, эти вопросы рассмотрены в [24,25,44]. Наиболее глубокие результаты в этом отношении хаоактеоны для исследований, опубликованных в Г241. Вместе с тем.
9 предлагаемые в указанных работах методологические подходы не взаимосвязаны с описанием информационных процессов на более высоких уровнях, что в заметной степени снижает их общенаучную ценность.
В целом, обобщая вышеизложенное, можно констатировать, что исследования по рассматриваемой тематике проводятся в ряде организаций как в нашей стране (например, в ИПУ РАН, г. Москва, в СПИИРАН, г.С-Петербург, в ряде НИИ Министерства Обороны РФ), так и за рубежом. Наиболее ощутимых результатов удалось достичь авторам работ [1,4,5,6,9,11], а также [13,15].
Вместе с тем, анализ известных публикаций позволяет утверждать, что существующие подходы к решению рассматриваемых вопросов имеют ряд серьезных недостатков. К основным из них можно отнести следующие.
Авторы большинства публикаций замыкаются на решении, как правило, отдельных частных , хотя и достаточно важных задач. Это не позволяет охватить исследуемую проблематику в целом.
Другой важный недостаток имеющихся публикаций заключается в том, что развиваемые в них подходы предъявляют настолько высокие требования по детализации описания процессов функционирования ЛВС, что их практическое выполнение становится нереальным.
С учетом изложенного можно утверждать, что назрела необходимость разработки такого подхода, который бы обеспечивал решение на единой теоретической основе всего комплекса вопросов по управлению процессами построения и функционирования ЛВС и, в то же время, позволял формулировать необходимые практические задачи на реально возможной совокупности исходных данных. Именно такую направленность имеет настоящая диссертационная работа.
В свете изложенного становится очевидной актуальность диссертационной работы, в которой решается научная задача разработки методического аппарата управления процессами построения и функционирования ЛВС на основе их структурной и организационной оптимизации.
Целью работы является повышение функциональной эффективности широкого круга автоматизированных систем (АС), построенных на базе ЛВС с распределенной обработкой данных.
В рамках поставленной в работе научной задачи решается ряд частных исследовательских задач, основными из которых являются следующие:
1.Формализация и анализ процессов функционирования ЛВС.
2.Обоснование логико-физических основ оптимизации структуры и организации ЛВС.
3.Построение совокупности показателей эффективности ЛВС.
4.Разработка методов структурной оптимизации ЛВС.
5.Разработка методов оптимальной организации ЛВС.
6.Анализ возможностей эвристического подхода для построения методов поиска решений в задачах оптимизации ЛВС, формулируемых в терминах целочисленного (псевдобулевого) математического программирования.
7.Разработка системы эвристик для поиска решений в задачах оптимизации ЛВС.
8.Разработка методического, алгоритмического и программного обеспечения оптимизации ЛВС.
По итогам проведенных в диссертации исследований на защиту выносятся следующие положения:
1. Общая формулировка задач оптимизации построения и функционирования ЛВС как систем с распределенной обработкой данных.
2.Совокупность показателей оценки эффективности ЛВС.
3.Методы структурной оптимизации ЛВС, обеспечивающие построение наиболее рациональной структуры рассматриваемых систем.
4.Методы оптимальной организации ЛВС, позволяющие определять наиболее эффективные варианты организации функционирования ЛВС.
5.Система эвристик для поиска решений в задачах оптимизации ЛВС.
6.Методическое, алгоритмическое и программное обеспечение оптимизации ЛВС.
Научная значимость и новизна паботы заключается в следующем:
1 .Впервые в рамках единого системного подхода сформулирована и решена задача обоснования логико-физических основ оптимизации ЛВС, методов построения оптимизационных моделей и системы эвристических алгоритмов для поиска решений в этих моделях.
2.Разработана оригинальная логико-физическая трактовка и общая формулировка задач оптимизации ЛВС.
3.Разработаны методы оптимизации структуры и организации ЛВС, сформулированные в терминах целочисленного (псевдобулевого) математического программирования.
4.Разработана система эвристик для поиска решений в задачах оптимизации ЛВС.
Практическая значимость диссертационной работы определяется тем, что предложенный аппарат оптимизации ЛВС доведен до логического завершения в виде системы эвристических алгоритмов, обеспечивающих получение конкретных решений для любых практических ситуаций использования ЛВС. Указанные алгоритмы практически не имеют ограничений на размерность решаемых оптимизационных задач и легко реализуются в виде машинных программ для современных персональных ЭВМ. Полученные результаты позволили обосновать структуру и алгоритмы функционирования АСУ специального назначения организационного типа.
В структурном отношении материал диссертации скомпонован в трех главах.
В первой главе дается формальная интерпретация информационных процессов, протекающих в автоматизированных системах на базе ЛВС с распределенной обработкой данных. Излагаются логико-физические основы оптимизации структуры и организации ЛВС, формулируется общая постановка задач оптимизации и обосновывается совокупность показателей эффективности ЛВС.
Вторая глава отведена непосредственно методам оптимизации ЛВС, формулируемым в рамках аппарата теории дискретного математического про-гоаммиоования. Разоабатываются методы стоуктуоной оптимизации ЛВС.
12 методы оптимальной организации ЛВС, а также комбинированные методы оптимизации.
В третьей главе разрабатывается система эвристических алгоритмов для поиска решений в задачах оптимизации ЛВС. В основу построения системы положены логико-физические аналогии, отображающие смысловое содержание каждой конкретной прикладной задачи.
В приложение вынесены результаты практического использования разработанного теоретического и методического аппарата для оптимизации ЛВС на примере реальной АСУ организационного типа, предназначенной для управления техническим обеспечением специальных подразделений.
Логико-физические основы оптимизации структуры и организации ЛВС
В информатике, как и в любой другой области знаний, существуют некоторые фундаментальные положения, знание которых необходимо для правильного принятия основополагающих технических и организационных решений. Одним из таких положений является принцип локализации вычислений, который неявно присутствовал в процессе всей истории развития ЭВМ. Поясним его существо на примере.
Для современных ЭВМ характерна иерархическая структура памяти (запоминающих устройств — ЗУ):сверхоперативное ЗУ (СОЗУ);оперативное ЗУ (ОЗУ);внешнее ЗУ (ВЗУ).
В СОЗУ хранятся наиболее часто используемые на некотором этапе работы ЭВМ данные, которые участвуют в выполнении нескольких смежных операций. В ОЗУ — программы и данные, необходимые для текущего этапа вычислений. Все остальное находится в ВЗУ. Такое распределение информации осуществляется автоматически, при этом характерно соблюдение следующих соотношений для вероятностей обращения за элементом информации: Prn4V Pn?v Pmv. Т. Є. обШПІЄНИЯ К б0ЛЄЄ быСТООЛеЙСТВУЮШИМ УСТООЙ 23 ствам происходят чаще. Тем самым повышается общее быстродействие ЭВМ, а следовательно — снижаются затраты ресурсов ЭВМ для выполнения заданного объема ИВР. Таким образом, прослеживается тенденция — если то, что чаще используется, хранить "под рукой", то затраты на выполнение работы снижаются. Это характерно и для СРОД в целом.
Теперь можно сформулировать два постулата, составляющих существо принципа локализации вычислений.Постулат 1, Система работает эффективно, если она выполняет требуемые функции в заданных условиях без излишних затрат ресурсов.Постулат 2. Общие затраты ресурсов на выполнение требуемых функций можно уменьшить, если часто выполняемые действия будут потреблять минимальное количество ресурсов.
Здесь понятие ресурса трактуется достаточно широко: это все то, что необходимо для выполнения требуемых функций (с учетом временного фактора) — время процессора, продолжительность использования ОЗУ, канала обмена данными и т.д.
Постулаты 1 и 2, составляющие существо принципа локализации вычислений, позволяют сформулировать задачи оптимизации СРОД.Основываясь на формальном описании функционирования СРОД с помощью совокупностей протекающих в них ИП и с учетом принципа локализации вычислений, можно выделить основные группы факторов, определяющих эффективность информационных технологий РОД. На рис. 1.3 показано влияние распределения информации для хранения и обработки в системе на характеристики совокупностей ИП (продолжительность отдельных ИП).
На уровне сети продолжительность ИП определяется затратами на передачу информации между узлами и зависит от относительного положения узла, в котором формируется заявка на выполнение ИВР, и узла, где хранится обрабатываемая информация. Это хорошо демонстрируют граф-схемы соответствующих ИП и временные диаграммы их выполнения, из которых видно, что продолжительность ИП тем больше, чем больше объем передачи инфор мации, осуществляемой в процессе реализации ИП, и чем больше промежуточных коммутаций информации при ее передаче в сети. Здесь рассмотрен случай, когда обработка информации осуществляется в узле 1, а в узлы 2 и 3 передаются заявки на выдачу информации, причем узел 3 не имеет прямой связи с узлом 1.
На уровне ВК продолжительность ИП зависит от затрат на обмен информацией с ВЗУ. Последние же определяются тем, в какой памяти хранятся данные и программы, необходимые для выполнения соответствующих ИВР. Это показано на рис. 1.4, где приведены граф-схемы ИП и временные диаграммы их выполнения для трех вариантов размещения информации: в оперативной памяти (ИПі), в памяти прямого (ИЩ) и последовательного доступа (ИП3). Видно, что количество этапов ИП и их продолжительности, т.е. затраты на обмен информацией определяются типом используемого ЗУ.
Для уровня устройства ВК продолжительность ИП определяется, в основном, затратами на поиск информации. Сокращение этих затрат за счет рационального распределения информации в ЗУ способствует значительному уменьшению продолжительности ИП, что следует из диаграмм, приведенных на рис Л .5. Увеличение количества этапов ИП на этом рисунке связано с поиском информации в ЗУ на устройстве последовательного доступа.
Таким образом, продолжительность ИП на каждом из уровней их представления связана с затратами на передачу и обмен информацией и на ее поиск. Чем выше затраты, тем больше, в среднем, продоююительностъ ИП. Величина этих затрат является переменной и зависит от принятых решений по построению и организации функционирования СРОД в рамках выбранной информационной технологии.
Методы структурной оптимизации ЛВС
Реализация любой СРОД на базе ЛВС обеспечивается, в конечном счете, посредством некоторой совокупности элементов технического, программного, информационного и других видов обеспечения, присущих соответствующей АС. Будем называть подобную совокупность элементов организационной основой СРОД. Тогда СРОД вместе со своей организационной основой может рассматриваться как некая система, т.е. множество элементов, находящихся в отношениях и связях друг с другом и образующих определенную целостность.
По совокупности признаков такую систему можно отнести к категории сложных систем [1]. Последние принято характеризовать структурой и организацией [20]. Структура выражает то, что остается устойчивым, статическим, относительно неизменным при различных преобразованиях системы. При исследовании сложных систем в интересах упрощения аппарата исследования зачастую рассматривают структуру системы укрупненно, обобщенно. При этом объединяют некоторые подмножества элементов системы таким образом, чтобы сохранить наиболее существенные с точки зрения текущего исследования проявления свойств системы. Так при исследовании распределенной обработки данных система рассматривается обычно в виде некоторой совокупности обрабатывающих узлов, объединенных соответствующими информационными взаимосвязями [4].
Организация системы включает в себя как относительно статические, так и динамические характеристики системы, обеспечивающие ее направленное функционирование. Применительно к рассматриваемым СРОД к организации можно отнести вопросы распределения информации для хранения и обработки в системе, управления информационными процессами в динамике их протекания и т.п. В свете изложенного интерес представляет анализ основных организационных структур СРОД на базе ЛВС, которые во многом определяют совокупность решений по построению методов оптимизации соответствующих ЛВС.
Поскольку современные АС строятся на основе принципа обеспечения автоматизированными рабочими местами (АРМ) должностных лиц и связывания этих АРМ в единую систему, то структура такой системы неизбежно повторяет структуру соответствующего органа управления. Вместе с тем, сложившаяся структура органов управления имеет иерархический вид. Логически это оправдано, поскольку в соответствии с общей теорией систем иерархическая структура позволяет обеспечить наиболее эффективное управление в системе [21].
Отметим, что с точки зрения топологии межсоединений подобная схема может в значительной мере видоизменяться. Например, при наличии быстродействующего канала все АРМ могут иметь непосредственный выход в этот канал и тогда образуется сетевая структура с моноканалом. Подобные ситуации следует учитывать при формулировке оптимизационных задач, о чем более подробно будет сказано ниже.
В рамках дальнейшего изложения будут рассмотрены методы статической оптимизации ИТТ для сетевого уровня. Это связано с тем, что, как показали предварительные исследования, оптимизация ИП на данном уровне позволяет получить наибольший эффект в плане улучшения функционирования исследуемой системы в целом.
В свою очередь рассматриваемые методы подразделяются на три основные подгруппы:методы, связанные собственно с определением основных структурных решений;методы, направленные на решение вопросов организации функционирования системы;комбинированные методы. 2.2. Методы структурной оптимизации ЛВС
Будем рассматривать СРОД на базе ЛВС, состоящей из некоторого количества узлов, объединенных каналами передачи данных. По существующей терминологии всю совокупность узлов такой системы можно условно разделить на две большие категории: рабочие станции и серверы. Рабочие станции (PC) представляют собой персональные ЭВМ (ПЭВМ), за пультами которых непосредственно работают пользователи системы. Серверы (С) -файл-серверы, принт-серверы, коммуникационные серверы и др. - служат для выполнения некоторых действий и процессов в интересах многих PC: хранение и ведение информационных файлов, проведение сложных расчетов, вывод данных на печать, обслуживание запросов на взаимодействие с другими абонентами системы и т.д.
В идеальном случае, по-видимому, может рассматриваться случай выделения отдельной PC для каждого должностного лица функциональной системы. Однако в реальных условиях такая постановка задачи, как правило, невыполнима ввиду наличия различного рода ограничений, как экономических (недостаток средств на закупку техники), так и фактических (ограниченные возможности подвижных единиц в полевых АСУ, недостаток площадей, режимные требования и т.п.). В таких ситуациях ставится вопрос о коллективном использовании PC некоторыми группами пользователей. В результате возникает задача определения оптимального количества PC и закрепления их за пользователями, решение которой для небольших систем, по сути дела, и формирует их структуру, поскольку организация взаимосвязей между узлами для таких систем решается тривиально. Построим математическую формулировку (модель) и дадим примеры решения такой задачи.
Пусть в системе (в учреждении, на предприятии) имеется I должностных лиц - пользователей. Каждый пользователь характеризуется средней tt, /-1,/. Обобщенно потребности пользователя будем задавать с помощью величины pt - Л,./. - загрузки пульта.
По некоторым соображениям (связанным, например, с обеспечением конфиденциальности, с удаленностью пользователей, их принадлежностью к разным функциональным подразделениями т.п.) можно однозначно указать возможность или невозможность объединения пользователей для работы на одной PC. С этой целью вводится матрица В = {fi }, где
Комбинированные методы оптимизации ЛВС
В ряде сетевых операционных систем, таких как, например, ORACLE, LAN MANAGER, имеется возможность перераспределения работ не только между PC и серверами, но и между PC. Тем самым информационные взаимодействия могут осуществляться как по принципу "клиент-сервер", так и по принципу "каждый с каждым". Рассматриваемая ниже математическая модель позволяет отображать подобные ситуации.
Пусть в ЛВС имеется J рабочих станций, формирующих узлы сети. Общее количество ИО -1, а каждый і-й ИО характеризуется объемом дисковой памяти wi, которая необходима для его хранения. Bj-м узле случайнымобразом возникают запросы на использование /-го ИО с интенсивностью &9и донесения по его корректировке с интенсивностью A j. При обработкезапроса к /-у ИО осуществляется обмен информацией с пользователем, объем этого обмена (удельный) - \\. Соответствующий объем обмена прикорректировке /-го ИО - v . Кроме того, в процессе обработки запроса к /-уИО может возникать дозапрос к k-y ИО с суммарным взаимообменом vlk.
Для установки в узлах системы имеется R типов ЭВМ (ПЭВМ, мини-ЭВМ), каждая из которых характеризуется некоторым быстродействием
Br и объемом памяти Wr, г = 1, /?, предназначенной для хранения ИО. Исходя из характера ИВР, потребность в выполнении которых возникает ву-м узле, можно указать минимальную загрузку /?, которую желательно обеспечить для ЭВМ г-го типа при ее размещении в j-u узле. Это обусловлено соображениями практического характера: нет смысла размещать в узле мощные вычислительные средства, если потребности в ИВР данного узла невелики и не предвидится их увеличения. Можно также указать максимальнуюзагрузку р , певышение которой в узле нежелательно из-за соображений,связанных с обеспечением оперативности выполнения ИВР. С учетом изложенного математическая модель системы может быть сформулирована следующим образом.
Определить такое размещение ЭВМ по узлам и такое распределение ИО в системе, которые бы обеспечивали минимизацию суммарного взаимообмена информацией.
Ограничения (2.41) и (2.42) связаны с обеспечением требований по надежности (живучести) функционирования системы и оперативности обслуживания пользователей. Здесь величина п{ задает степень дублирования ИО,a pijr - загрузку ЭВМ r-го типа обработкой запросов і-го типа дляу-го узла.
Ограничение (2.43) вытекает из требования производительного использования ЭВМ в узлах, а (2.44) - учитывает конечный объем ресурсов памяти. Ограничение (2.45) определяет единственность размещения ЭВМ в узле. Особо следует остановиться на ограничении (2.46), которое определяет предпочтительность использования вычислительных средств в узлах. Здесь величина djr есть элемент бинарной матрицы D, единичные значениякаждой j-й строки которой определяют возможность использования тех или иных типов ЭВМ в j-м узле. С помощью этого ограничения можно, например, выделить узел вычислительного центра, задав в нем возможность размещения мощного вычислительного комплекса, на который будут распределяться все те ИВР, для реализации которых в узлах пользователей недостаточно имеющихся ресурсов. Можно также рассматривать обобщенный узел, состоящий из некоторой совокупности серверов.
Основная сложность получения решений в модели (2.40) - (2.46) заключается в том, что величины pijr в ограничениях (2.42) и (2.43) не являются параметрами, а, в свою очередь, зависят от получаемого решения. В общем случае выражение для расчета piJr можно записать следующим образом: где сы есть элемент бинарной матрицы С, ненулевое значение которого определяет наличие дозапроса к /-у ИО при обработке &-го.
С целью иллюстрации практического применения изложенной модели рассмотрим числовой пример. В табл.2.17 представлены значения wi9 vl9 v , и vik для системы с пятью станциями (узлами).
В табл.2 Л 8 приведены значения интенсивностей Яр и AJ (последняявеличина под чертой).
Анализ значений величин, представленных в табл.2.17 и 2.18, показывает, что ИО с номерами 4, 8 и 10 являются информационными массивами (обращения к ним генерируются лишь через другие ИО, а сами они обращений не генерируют). Остальные ИО являются программами, причем некоторые из программ (например, 3 и 5) являются чисто расчетными процедурами, не связанными с использованием массивов.
Характеристики вычислительных средств, которые могут устанавливаться в узлах, даны в табл.2Л 9, а возможности их установки определяются значениями dJr, приведенными в табл.2.20. Значения величин сь, характеризующих наличие дозапросов при обработке ИО, даны в табл.2.21.
Остальные параметры задачи характеризуются следующими значениями: п1 =1, тіг =т іг =т"г =0,001 V / и г = 1,2; для г=Ъ соответствующие величины на порядок ниже.
Разработка эвристических методов решения задач структурной оптимизации ЛВС
Как отмечалось выше, в широком смысле слова под структурой системы понимают совокупность устойчивых взаимосвязей между ее элементами. В отличие от структуры организация системы характеризует менее устойчивые связи, более подверженные изменениям в процессе функционирования системы [20]. В отношении информационных сетей и ЛВС понятие структуры представляется достаточно специфичным и имеет множественную трактовку: физическая структура, логическая структура, топологическая структура и т.д. [21]. Поэтому для большей определенности при изложении материала настоящей главы условимся, что в понятие структуры ЛВС будем вкладывать совокупность таких взаимосвязей между элементами, которые опреде ляются физическим размещением пользователей соответствующей информационной системы и обрабатывающих и коммутационных центров.
В рамках рассматриваемой трактовки понятия структуры ЛВС возникает ряд оптимизационных задач, математические постановки которых рассматривались выше (гл.2).
Одной из задач такого рода является задача выбора количества рабочих станций и уровня их загрузки, которая достаточно часто решается на начальных этапах создания ЛВС специального назначения. Ее математическая постановка заключается в определении оптимального количества рабочих станций (PC) и закреплении их за пользователями с таким расчетом, чтобы загрузка PC была, по возможности равномерной.
Общая задача выбора количества рабочих станций и уровня их загрузки в гл.2 формулируется в виде двух оптимизационных задач в терминах ПМП. Математическая формулировка первой из них, связанной с предварительным распределением пользователей, выражается следующим образом.
Здесь целевая функция (3.1) стимулирует поиск такого решения, которое при условии выполнения ограничений (3.2) - (3.5) обеспечивает использование минимального числа рабочих станций для выполнения заданного объема информационно-вычислительных работ (ИВР).
Решение задачи (3.1)-(3.5) обеспечивает выбор минимального числа PC для выполнения заданного объема ИВР, однако не позволяет получить равномерную загрузку PC. С учетом последнего обстоятельства ставится вторая оптимизационная задача, которая формулируется следующим образом.
Для заданного числа N PC с учетом ограничений (3.2) - (3.5) осуществить такое перераспределение пользователей по PC, которое бы обеспечивало:
Как видно, задачи (3.1) - (3.5) и (3.6), (3.2) - (3.5) являются квадратичными задачами ПМП Попытки решения задач такого рода на базе строгих математических методов наталкиваются на значительные трудности теоретического характера, особенно с возрастанием размерности задачи.
Эвристика для решения задачи (3.1) - (3.5) основывается на идее "плотной упаковки" PC, которая по своему физическому смыслу близка соображениям, связанным с поиском решений задачи о размещении предметов разного объема в рюкзаках [22]. Из интурггивньтх представлений становится ясным, что количество рюкзаков (рабочих станций) уменьшается, если мы будем стремиться их упаковывать "плотно". С этой целью предлагается достаточно простой алгоритм, включающий следующие шаги. а) Множество пользователей упорядочивается по убыванию pt. Получаем последовательность пользователей а. б) Осуществляется выбор пользователей для компоновки очередной их группы для работы на одной PC. Для этого, начиная с левого конца упорядо ченной последовательности, выбираются пользователи, и для каждого из них проверяется выполнимость условий (3.2) - (3.5) с учетом уже вошедших в группу пользователей. Если эти соотношения выполняются, то очередной пользователь включается в группу и анализируется возможность включения в группу следующего по порядку. в) Если условия (3.3) - (3.5) выполняются, а (3.2) - не выполняется, то очередной пользователь в текущую группу не включается, а анализируется в соответствии с (б) возможность включения в эту группу следующего по по рядку пользователя. г) Формирование очередной группы завершается после просмотра всех членов последовательности т. д) Осуществляется корректировка последовательности а путем ис ключения из ее состава всех пользователей, вошедших в текущую группу. В новой последовательности а упорядоченность пользователей сохраняется. е) Проверяется условие: последовательность и - пуста. Если условие не выполняется, то повторяется последовательность шагов (б) - (д) и форми руется очередная группа. В противном случае алгоритм завершает работу. Заметим, что в силу логики алгоритма он всегда завершается за конечное число шагов. Рассмотрим методический пример. Пусть пользователи АС характеризуются нагрузкой, представленной в табл.3.1, а значения матриц А и В не препятствуют любым их совместным группировкам.
