Математические модели и алгоритмы оптимизации восстановительного резервирования информации в корпоративной вычислительной сети "Государственной компании "Росвооружение" тема диссертации и автореферата по ВАК РФ 05.13.06, кандидат технических наук Святенко, Кирилл Витальевич

• Святенко, Кирилл Витальевич
• кандидат технических наук
• 2000

Оглавление диссертации кандидат технических наук Святенко, Кирилл Витальевич

Введение.

1. Анализ современного состояния, перспектив развития вычислительных сетей. Постановка задачи исследования.

1.1 Структура и краткий обзор основных направлений совершенствования ВС «ГК «Росвооружение».

1.2 Характеристика и особенности разрушающих факторов, влияющих на носители информации и сравнительная характеристика устройств хранения информации.

1.3 Обеспечение сохранности информации в вычислительных сетях.

1.4 Анализ видов и стратегий резервирования.

1.5 Определение областей эффективного использования восстановительного резервирования.

1.6 Обоснование общего подхода к решению задач оптимизации восстановительного резервирования.

Выводы по первой главе.

2. Математические модели и алгоритмы оптимизации восстановительного резервирования информации в ВС.

2.1 Общая математическая модель оптимизации восстановительного резервирования.

2.2 Декомпозиция общей задачи на систему взаимосвязанных задач.

2.3 Методы решения задач восстановительного резервирования информации.

Выводы по второй главе.

3. Экспериментальная проверка моделей и методов оптимизации восстановительного резервирования информации.

3.1 Экспериментальная оценка эффективности методов и алгоритмов оптимизации.

Введение диссертации (часть автореферата) на тему «Математические модели и алгоритмы оптимизации восстановительного резервирования информации в корпоративной вычислительной сети "Государственной компании "Росвооружение"»

Главным направлением повышение эффективности формирования и осуществления процесса военно-технического сотрудничества является создания Единой автоматизированной информационной системы на основе внедрения компьютерных технологий и использования современных средств вычислительной техники, средств передачи данных и математических методов.

Постоянное совершенствование средств и методов управления различного рода структурными подразделениями «ГК «Росвооружение» стало одним из основных факторов, определяющих повышение эффективности действий России на мировом рынке вооружений и военной техники (В и ВТ). Необходимость дальнейшего интенсивного развития систем управления диктуется возрастающей диспропорцией между постоянно растущим потоком информации, представляющей собой конъюнктуру рынка, прогноз потребностей по каждому конкретному образцу В и ВТ, возможностями предприятий производителей специмущества (СИ), изменения российского законодательства, международные и внутренние политические аспекты, и возможностями средств по обработки для принятия решений. На этой основе возникают и новые повышенные требования к вычислительным системам (ВС) управления.

Наличие широкой сети региональных представительств в более чем 20 странах также требует наличие современной ВС.

Другим, не менее важным фактором, является развитие динамики процесса международного военно-технического сотрудничества (ВТС) и повышения ответственности сторон, где оперативно принимаемые решения несут за собой обязательства на длительный срок (до нескольких десятков лет) и любые ошибки могут привести к серьезным финансовым и политическим потерям. Данный факт на очень напряженном рынке В и ВТ, где присутствует жесткая конкуренция мировых производителей СИ, представляется наиболее серьезным.

Анализ современного состояния средств управления показывает, что они по уровню разработки и производству не полностью соответствуют предъявляемым требованиям, что снижает эффективность работы системы. Увеличение сложности решаемых задач, расширение их перечня, повышение требований к оперативности и достоверности обработки информации обуславливает необходимость создания высокоэффективных средств обработки информации.

Разрешить указанную проблему призвана концепция распределенной системы управления, которая заключается в увеличении количества пунктов управления и обеспечении их тесной взаимосвязи и взаимозаменяемости, и возможности использования общих информационных массивов.

Практическая реализация концепции распределенной системы управления требует реализации целого комплекса научно-технических проблем, связанных с созданием общих информационных массивов, установлением порядка их обновления, пересылки, защиты и оперативного использования, определением номенклатуры технических средств в каждом локальном пункте и др. Целый ряд проектов за рубежом предлагает различные способы решения указанных проблем.

Опыт разработки и опытная эксплуатация показали, что объем и сложность информационно-расчетной деятельности должностных лиц достигли такого масштаба, что возникла необходимость в организации взаимосвязанного функционирования больших коллективов пользователей ЭВМ, территориально размещенных на значительных расстояниях и нуждающихся в оперативном доступе к настолько значительным объемам данных и большим вычислительным мощностям, что удовлетворение этих потребностей не всегда может быть обеспечено средствами отдельных ЭВМ или их локальным объединением вычислительных комплексов. В этих условиях в области создания вычислительных сетей наметилась устойчивая тенденция к использованию сети ЭВМ как перспективной организационно-технической формы применения вычислительных средств.

Создание сетей ЭВМ связано со значительными затратами, а эффективное использование предоставляемых ими возможностей требует количественного обоснования принимаемых решений по выбору рациональных вариантов построения и организации их функционирования.

Существует большое число работ посвященных сетям ЭВМ. В работах В.М.Глушкова [4], Д. Флинта [5], Э.А. Якубайтиса [6,7] излагаются основные принципы построения вычислительных сетей, организация сетей передачи данных и связи, их анализ и синтез. В работе Г.Т.Артамонова и В.Д. Тюрина [8] излагается оригинальная система топологических инвариантов, позволяющая эффективно решать задачи определения изоморфизма и автоморфизма сетей. Исследуется влияние топологических характеристик сетей на их надежность, пропускную способность, стоимость и ряд других системных характеристик. В работе Г.Ф. Янбых и Б.А. Столярова [9] рассматривается проблема оптимизации физической структуры информационно-вычислительных сетей. Методы и алгоритмы синтеза и оптимизации структуры, централизованных и распределенных сетей ЭВМ с единых методологических позиций рассмотрены Ю.П. Зайченко и Ю.В. Гонта [10].

В работах В.А. Балыбердина [11,12,13] предложены единый метод исследования системы вычислительных средств (СВС) сетей ЭВМ, основанный на выделении и рассмотрении совокупностей взаимодействующих информационных процессов, протекающих в СВС, комплекс аналитических моделей совокупностей информационных процессов для решения задач анализа сетей ЭВМ и методы многоуровневой оптимизации для решения задач синтеза.

Приведенный перечень работ свидетельствует о большом интересе к развитию сетей ЭВМ и определенном опыте, накопленном в нашей стране и за рубежом, в области решения задач синтеза и оптимизации структуры, анализа сетей ЭВМ, особенно сетей передачи данных.

Однако основной акцент при создании ВС на базе сетей ЭВМ делается на решение следующих проблем:

- организации информационно-вычислительного процесса (ИБП) в системе вычислительных средств сети ЭВМ;

- организации управления распределенными ресурсами в рамках системы; обеспечении сохранности информации в системах с распределенной обработкой информации;

- организации функционирования распределенных баз данных.

В США и ведущих зарубежных странах решению перечисленных проблем придан статус наивысшего приоритета, так как от их решения в первую очередь зависит эффективность сети в целом.

Если рассмотреть накопленный опыт при решении задач оптимизации и повышения устойчивости информационно-вычислительного процесса (ИВП), сохранности информации в сетях ЭВМ, то необходимо отметить работы В.В. Хорошевского [14], Е.Н.Турута [15,16]. O.K. Кондратьева [17], отражающие прогресс, достигнутый при решении задач повышения устойчивости ИВП. Работы А.Г. Мамиконова, В.В. Кульбы, С.К. Сомова, А.Б. Шелкова [20,21,22] посвящены решению вопросов повышения достоверности и сохранности информационных модулей и программных массивов в вычислительных сетях за счет организации оперативного и восстановительного резервирования.

Практическое решение вопросов синтеза сетей ЭВМ и организации их функционирования связано с развитием теории и практики оптимизации, которым посвящены работы О.Г. Алексеева [23], B.C. Михалевича [24,25], И.В. Сергиенко [26], A.A. Корбута, Ю.Ю. Финкелынтейн [27].

Приведенный обзор работ, показывает, что задачи повышения устойчивости ИВП, обеспечения сохранности информации, повышения эффективности и разработка новых методов оптимизации решались в основном порознь и изучены с различной степенью глубины.

Работы, проведенные в этом направлении к настоящему времени, обладают рядом существенных недостатков:

1. Не разработан системный подход к повышению устойчивости ИБП и сохранности информации на этапах проектирования и эксплуатации ВС.

2. Недостаточно формализованы способы и методы обеспечения устойчивости ИВП и сохранности информации (модели распределения и перераспределения программных модулей и информационных массивов по узлам сети ЭВМ).

3. Существующие постановки указанных задач предполагают их решение в процессе синтеза сети ЭВМ. Исходя из этого, к разрабатываемым методам и алгоритмам их решения не предъявляется достаточно жестких требований по времени решения. Вместе с тем, такие задачи возникают в процессе эксплуатации средств автоматизации управления, а их реализация связана с решением дискретных, зачастую нелинейных задач большой размерности в короткие сроки. Это, в свою очередь, порождает проблему дискретности, многомерности и большой размерности задач оптимизации ИВП и разработки эффективных методов их решения.

Таким образом, научной задачей, решаемой в диссертационной работе, является разработка моделей и методов обеспечения сохранности информационных массивов в вычислительных сетях.

Актуальность задачи обусловлена: необходимостью повышения эффективности функционирования вычислительной сети «ГК «Росвооружение» за счет придания ей свойств устойчивости ИВП, необходимостью разработки и совершенствования теоретического аппарата обеспечения сохранности информации, исследования задач многомерности и дискретности задач оптимизации.

Объектом исследования являются автоматическая система обработки информации подразделений «ГК «Росвооружение»

Предметом исследования являются методы обеспечения сохранности информационных массивов в вычислительных сетях «ГК «Росвооружение».

В связи с этим целью работы является расширение функциональных возможностей и улучшение характеристик перспективных ВС за счет обеспечения сохранности информации.

Поставленная цель достигается решением ряда следующих крупных научных задач:

1. разработка общего подхода к решению задач обеспечения сохранности информации в системе вычислительных средств сети;

2. разработка системы математических моделей оптимизации ИБП в ВС с учетом резервирования программных модулей и информационных массивов;

3. повышение эффективности существующих и разработка новых методов решения задач оптимизации;

4. оценка эффективности, обоснование рекомендаций по использованию разработанного теоретического аппарата.

Содержание этих решений изложено в трех главах настоящей работы.

В первой главе рассматриваются требования, предъявляемые к ВС на современном этапе, основные направления совершенствования ВС и связанные с этим задачи. Показано, эффективность ВС, построенных на базе сетей ЭВМ, во многом определяется обеспечением сохранности информации в системе вычислительных средств. Исследуются основные направления обеспечения сохранности информации и методы их реализации. Показано, что при заданных характеристиках технических средств автоматизации сохранность информации обеспечивается рациональным распределением программных модулей (ПМ) и информационных массивов (ИМ) в системе вычислительных средств (СВС) сети ЭВМ с учетом их резервирования. Формулируется задача исследования и обосновывается общий подход ее решения.

Вторая глава посвящена разработке системы математических моделей оптимизации распределения (перераспределения) ПМ и ИМ с учетом их резервирования в СВС сети ЭВМ. Обоснован метод их декомпозиции на ряд взаимосвязанных задач в целях практической разрешимости. Предлагаются методы и алгоритмы решения, основанные на идеях метода ветвей и границ с применением теории двойственности для определения порядка ветвления переменных и вычисления оптимистических оценок и способа встречного решения функциональных уравнений динамического программирования.

В третьей главе обосновываются критерии оценки эффективности разработанных методов и алгоритмов оптимизации. Проводится сравнительная оценка эффективности разработанных и существующих алгоритмов оптимизации. Предлагаются рекомендации по использования разработанного теоретического аппарата на этапах проектирования и эксплуатации ВС.

В заключении формулируются результаты работы в целом.

Основными научными результатами, выносимыми на защиту являются:

1. Система математических моделей оптимизации информационно-вычислительного процесса в сетях ЭВМ, позволяющая комплексно и взаимосвязано решать задачи распределения программных модулей, информационных массивов и их восстановительного резерва в системе вычислительных средств, а также определять необходимый объем резерва.

2. Метод решения общих задач оптимизации распределения (перераспределения) программных модулей и информационных массивов с учетом их резервирования в системе вычислительных средств на основе предложенной их декомпозиции на ряд взаимосвязанных задач и разработанные математические модели оптимизации для каждого этапа декомпозиции.

3. Метод и математическая модель оценки порядка ветвления переменных, способы определения границ решения в методе ветвей и границ, использующие принцип двойственности, позволяющие значительно сократить вычислительную сложность алгоритмов ветвей и границ.

4. Модифицированный метод встречного решения функциональных уравнений динамического программирования, использующий теорию двойственности для упорядочения ограничений и отсева бесперспективных переменных при решении задачи по первому ограничению по условиям метода ветвей и границ, обеспечивающий значительное уменьшение времени решения задач и число членов условно оптимальных последовательностей.

Практическое значение и реализация работы. Предложенные методики, методы, модели и алгоритмы использованы при проведении ряда работ по созданию образцов комплексов средств автоматизации, а также в силу своей общности могут найти применение при разработке, эксплуатации перспективных комплексов средств автоматизации различных уровней управления, методы и алгоритмы доведены до рабочих программ и позволяют решать широкий круг научно-технических задач. Основные практические результаты диссертационной работы внедрены: в 3 ЦНИИ МО России; в Таганрогском авиационном научно-техническом комплексе им. Бериева; в учебном процессе Тульского ВАИУ в дисциплине "Исследование операций"

Апробация работы и публикации. Материалы диссертации докладывались, обсуждались и одобрены на НТК Тульского ВАИУ (1997, 1999 г.г.), Михайловской артиллерийской академии г. С-Петербург (1998 г.), на расширенных заседаниях кафедр "ЭВМ и ВС", "Математическое, программное и информационное обеспечение ВС" Тульского артиллерийского инженерного института. Материалы диссертации опубликованы в 10 печатных работах в ведомственных научно-технических изданиях:

Киселев В.Д., Есиков О.В., Святенко К.В. Декомпозиция задачи восстановительного резервирования программных модулей и информационных массивов в сети ЭВМ,- НТК №9 (сборник тезисов докладов). Тула: ТВАИУ, 1993 г.

Есиков О.В., Святенко К.В. Обеспечение сохранности информации в локальных сетях ЭВМ.- НТК №9 (сборник тезисов докладов). Тула: ТВАИУ, 1993 г.

Есиков О.В. , Святенко К.В., Матвеев Д.В. Имитационная модель оценки эффективности перспективных АСУ- НТК №10 (сборник тезисов докладов). Тула: ТВАИУ, 1995 г.

Киселев В.Д. , Есиков О.В.,Святенко К.В., Логвинов С.С. Анализ влияния восстановительного резервирования на эффективность функционирования АСУ, построенных на базе сетей ЭВМ- НТС N 14. Тула : ТВАИУ, 1997. С.-144-148.

Киселев В.Д., Крутских В.А., Святенко К.В. Определение типа носителей восстановительного резерва информации в территориально-распределенных ВС. НТС N 5. Санкт-Петербург: МО РФ. 1998. С.-27-31.

Киселев В.Д., Святенко К.В. Обеспечение сохранности информации в ВС специального назначения, построенных на базе сетей ЭВМ. НТС N 5. Санкт-Петербург: МО РФ. 1998. С.-38-41.

Киселев В.Д., Новиков В.В., Святенко К.В. Распределение задач в системе обработки информации методом альтернативного программирования,- НТС N 15. Тула : ТВАИУ, 1998. С,-134-138.

Святенко К.В., Новиков В.В. Оценка способов ветвления переменных в методе ветвей и границ. - НТС N 15. Тула: ТВАИУ, 1998. С,-175-179.

Святенко К.В., Федосов Е.И., Лагутин H.H. Оптмизация информационно-вычислительного процесса на объектах ВС - НТС N 15. Тула : ТВАИУ, 1998. С,-179-182.

Есиков О.В., Святенко К.В. Принципы построения систем защиты информации в современных АСОД - НТС N 16. Тула : ТАИИ, 1999. С.-82-85.

Заключение диссертации по теме «Автоматизация и управление технологическими процессами и производствами (по отраслям)», Святенко, Кирилл Витальевич

Выводы по третей главе

1. Применение для автоматизации экспериментальной проверки предложенных методов и алгоритмов решения задач оптимизации распределения и восстановительного резервирования ИМ в системе ВС сети разработанной АСИА (автоматизированная система исследования алгоритмов) позволяет управлять процессом исследования, проводить сравнительную оценку алгоритмов по выбранной программе и значительно снизить затраты на организацию и проведение экспериментов.

2. Результаты экспериментальной оценки способов определения границ решения с использованием теории двойственности показали, что наиболее эффективным является однократное решение двойственной задачи итерационными методами, который позволяет уточнять оценки переменных и определить порядок их ветвления. Среднее время решения с применением данного способа в 7-42 раза относительно первого, 3-13 раза относительно второго и в 1,1-2,2 раза относительного третьего способа меньше. С ростом числа ограничений и переменных задачи это преимущество возрастает.

3. Упорядочивание ограничений по жесткости и включение дополнительного отсева бесперспективных вариантов по условиям метода ветвей и границ с использованием двойственной задачи в способе встречного решения дает выигрыш по времени в 2,3-14,8 раза за счет уменьшения числа

Предложенные принципы и критерии распределения ПМ и ИМ обеспечивают работоспособность ВС в условиях функциональной деградации и деградации по производительности системы вычислительных средств сети в заданных пределах показателей эффективности ВС.

Большая размерность общей задачи оптимизации ИБП, дискретность, нелинейный характер целевых функций и ограничений не позволяет решить их существующими методами и выдвигает проблему снижения их размерности.

Для сокращения размерности задачи оптимизации восстановительного резервирования предложена ее декомпозиция на ряд взаимосвязанных подзадач, а именно:

1. оптимизации распределения ИМ в системе ВС без учета их восстановительного резервирования при известном распределении ПМ;

2. оптимизация распределения восстановительного резерва ИМ без учета его разрушения (без определения объема восстановительного резерва) с учетом заданного распределения восстановительного резерва ПМ;

3. оптимизация объема восстановительного резерва ИМ.

4. Разработанный в соответствии с декомпозицией общей задачи на уровне вычислительной сети, комплекс математических моделей сводится к следующим классам задач:

5. оптимизация распределения ИМ по критерию минимума передаваемой информации по каналам связи - к классу задач ЦЛП со смешанными ограничениями;

6. оптимизация распределения восстановительного резерва - к классу целочисленных линейных задач;

7. оптимизация объема восстановительного резерва - к стандартной задаче оптимального резервирования.

Необходимость решения предложенных задач в реальном масштабе времени (в период эксплуатации и боевого применения) предполагает поиск путей повышения эффективности существующих и разработку новых методов и алгоритмов оптимизации.

Сформулированные задачи распределения и оптимизации восстановительного резервирования программных модулей и информационных массивов в сети ЭВМ относятся к классу задач комбинаторного типа. Трудоемкости сформулированных задач выдвигает требование дальнейшего совершенствования и модификации алгоритмов ее решения.

Для сокращения вычислительной сложности определения границ решения могут быть использованы разработанные и обоснованные способы на основе теории двойственности: решение двойственной задачи для каждой вершины дерева ветвления; решения двоственной задачи для уровня; однократное решение двойственной задачи; однократное решение двойственной задачи с уточнением границы итерационными алгоритмами. Результаты экспериментальной оценки способов определения границ решения с использованием теории двойственности показали, что наиболее эффективным является однократное решение двойственной задачи итерационными методами, который позволяет уточнять оценки переменных и определить порядок их ветвления.

Применение теории двойственности для упорядочения ограничений по жесткости в методе встречного решения и включение дополнительного отсева бесперспективных вариантов решений по целевой функции по условиям метода ветвей и границ позволяет повысить эффективность динамического программирования при определении множества допустимых решений задач оптимизации восстановительного резервирования информации.

Применение приближенных методов решения задач дискретной оптимизации позволяет решать задачи большой размерности. В качестве приближенных методов решения задачи восстановительного резервирования

19. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации.- 2-е изд., доп. и перераб.-Киев: Наук. Думка, 1988.472 с.

20. Сергиенко И.В., Лебедева Т.Т., Рогцин В.А. Приближенные методы решения дискретных задач оптимизации.- Киев: Наук. Думка, 1980.-276 с.

21. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение // Кибернетика. - 1965. -№1.- с. 45-55.

22. Первозванский A.A., Гайцгори В.Г. Декомпозиция, агрегирование и приближенная оптимизация. - М.: Наука, 1979. -276 с.

23. Мельник Э.М., Киселев В.Д. Об одном подходе к распределению задач между работоспособными микро ЭВМ при функциональной деградации вычислительной системы. // Алгоритмы и структуры систем обработки информации. - Тула: ТулПИ, 1990.- с. 99-105.

24. Киселев В.Д., Алексеев О.Г., Мировицкий Г.П. Сужение области поиска в задачах дискретного программирования на основе теории двойственности.// Электронное моделирование. - 1989.- Т 11.-№5.

25. Алексеев О.Г., Алексеев А.О., Киселев В.Д., Мировицкий Г.П. Применение двойственности для повышения эффективности метода встречного решения функциональных уравнений динамического программирования // Кибернетика. - 1990,- №1. с. 114-116.

26. Киселев В.Д., Алексеев О.Г. Упорядочение ограничений в методе встречного решения функциональных уравнений динамического программирования.// Экономика и математические методы. - 1994.

27. Майника Э. Алгоритмы оптимизации на сетях и графах,- М.: Мир, 1981.-323с.

28. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. Пер. с англ.- М.: Мир, 1985. - 512 с.