|
|
Разработка теоретических основ развития региональных образовательных компьютерных
сетей
на базе анализа структурной сложности # 11, ноябрь 2006
УДК 004.7:519.8 С.В.Мищенко, В.Е.Подольский, С.С.Толстых
Тамбовский государственный технический университет
Компьютерные сети в сфере образования – важный аспект современного общества. Качество обучения напрямую зависит от уровня компьютеризации, предполагающего сейчас активное участие подавляющего большинства компьютеров образовательного учреждения в телекоммуникациях. Появилось понятие РОКС – региональные образовательные компьютерные сети. В начале существования они функционировали, как правило, в масштабах одного вуза. По мере развития, количество абонентов сети увеличивалось с каждым годом, и география РОКС расширилась до масштабов региона. Абонентами сети постепенно становятся практически все образовательные и научные организации областей России. С развитием глобальной сети Интернет сфера образования в отдельной области становится элементом российского и международного образовательного информационного пространства [1-9]. По мере укрупнения РОКС наблюдался неуклонный рост расходов на ее поддержку и развитие. В развитие РОКС на разных этапах вкладывались весьма значительные денежные средства. Стало актуальным решение вопроса о самоокупаемости затрат на функционирование сети. Каждый следующий этап развития РОКС по отношению к предыдущему нуждался в строгом экономическом обосновании. В связи с этим возникла задача повышения эффективности работы РОКС в настоящем и будущем. Для этого необходим математический аппарат, на основе которого можно было бы проиграть различные варианты развития РОКС, в зависимости от прогноза потребностей в услугах сети и с учетом передового зарубежного и российского опыта. В качестве теоретической основы имитационного моделирования РОКС предлагается использовать научные достижения в области структурного анализа и теории сложности. Основанием к этому являются попытки охватить реальные масштабы РОКС как системы большой размерности. В этом случае неизбежен переход от традиционных способов представления математической модели сети к рассмотрению ее структурных свойств, оказывающих превалирующее влияние на получение знаний по сравнению со статистическим анализом сетевого трафика в отдельных узлах. Применительно к РОКС рассматривается понятие «структурная сложность» и используются соответствующие приемы моделирования, основанные на оценке этой обобщенной характеристики структурных свойств большой системы. Предлагается философия рассмотрения структуры РОКС на уровне замкнутой системы, состоящей из совокупности сильно связных подсистем. Внешние связи РОКС моделируются введением в систему конечного числа объектов внешней информационной среды, связанных с региональным базисом. Свойства связей и размерность могут меняться во времени, но представление РОКС как целостной замкнутой системы при этом сохраняется, причем как на уровне трендов активности, так и на этапах ее эволюции. На рис. 1 представлена иллюстрация к развитию теории сложности, где обозначены место и роль наших концепций. На этом рисунке показано, что в составе теории сложности, помимо традиционных понятий «сложности вычислений» и «алгоритмической сложности» появилось новое направление – структурная сложность. Этот вид сложности стал теперь сугубо количественной характеристикой технической системы, взамен общефилософских концепций. Пользуясь понятием «термодинамическая сложность» И.Пригожина, мы оцениваем состояние технической системы путем наблюдения за информационной энтропией – величины, которая по отношению к сложности является обратной. Чтобы уточнить связь этих понятий, потребуется ввести в рассмотрение алгебру сложности, и, в том числе, единичную сложность.
Рис. 1. Место и роль концепций структурной сложности
Познание сложности явлений и систем всегда имело тенденцию к переходу от качественного на уровень количественного анализа. Главным препятствием к этому было и остается механизм перевода общечеловеческих понятий «сложнее», «проще» на кибернетический уровень (рис. 2). Наибольших успехов здесь добилась вычислительная математика, где вопросы оценки сложности вычислений уже давно стали привычной механикой доказательств. Однако в области системного анализа имеется еще много неизученного, если речь идет о сложности и, прежде всего, это касается сложности структур, моделируемых с использованием понятия «орграф». Количественный уровень познания сложности предполагает невозможность или бесполезность назначения семантических оценок сложности типа «сложнее/проще» и начинается с обозначения границ системы, в рамках которой находится исследуемое явление. Применительно к РОКС можно сказать, что ее границы обозначены масштабами самого региона (области, края), а явление, подлежащее моделированию – телекоммуникационные взаимодействия. Здесь важно отметить, что не всякое моделируемое явление подлежит структуризации, т.е. порой структура взаимодействий отдельных объектов в системе может быть совершенно непознаваема. Структура взаимодействий объектов РОКС (узлов сети), наоборот, совершенно очевидна, но, тем не менее, структуризация в данном случае должна сопровождаться агрегированием (т.е. в структуру РОКС не обязательно включать абсолютно все компьютеры, которые могут быть подключены к сети).
Рис. 2. Соотношение качественного и количественного уровня познания сложности
Начальным этапом развития теории структурной сложности является оценка сложности такого известного математического объекта как орграф
где
Матрица достижимости служит для выявления сильно связных подсистем (бикомпонент) (см. иллюстрацию на рис. 3) при удалении дуг из орграфа и для проверки его сильной связности: нас интересуют только сильно связные орграфы, для которых Модифицированные матричные представления (учитывается вес):
Рис. 3. Использование матрицы достижимости для выявления сильно связных подсистем
Рис. 4. Информационная сущность взвешенной матрицы инцидентности
Рис. 5. Пример сильно связного орграфа
Таблица 1. Взвешенная матрица контуров для орграфа на рис. 5
Дуга (2→3) называется наиболее приоритетной, т.к. имеет наибольшую контурность (если таких дуг несколько, то она, кроме наибольшей контурности, должна иметь минимальный вес). Анализ сложности предполагает поэтапное упрощение сильно связного орграфа, вплоть до состояния, когда в орграфе не останется ни одного контура (случай дерева). Поэтому для наискорейшего упрощения орграфа резонно разорвать именно ту дугу, которая чаще всех других входит в контуры и при этом ее вес, образно говоря, небольшой. По аналогии с критерием структурной сложности не взвешенного орграфа вводится критерий сложности взвешенного орграфа. Он базируется на новом понятии – «матрица сложности»
На рис. 6 показана связь формулы (2) с формулой (1). Из этого рисунка видно, что число дуг Критерий структурной сложности взвешенного орграфа представляет собой проецирование матрицы сложности в пространство
где
Рис. 6. Аналогия между структурными сложностями не взвешенного и взвешенного орграфов
Для верификации критерия (3) нам потребуется понятие «критической дуги». Это дуга, разрыв которой приводит орграф к дереву. На рис. 7 показан так называемый «гамак» – орграф с единственной критической дугой. Возникает вопрос: всегда ли критическая дуга орграфа является наиболее приоритетной при упрощении, благодаря которому мы познаем структурную сложность? Для ответа на этот вопрос потребуется ввести определение меры приоритетности дуги
Рис. 7. Гамак с критической дугой (1→2)
Поясним формулу (4): - - - мера приоритетности – по характеру формирования – мультипликативная величина, что объясняется необходимостью баланса структурных и алгебраических свойств дуги при оценке структурной сложности; - алгебраические свойства взвешенной дуги проявляются в первом сомножителе: чем вес больше, тем приоритет дуги меньше; - структурные свойства дуги оцениваются вторым сомножителем – чем меньше приращение сложности в числителе дроби, тем в меньшей мере дуга может повлиять на оценку структурной сложности; фактически это приближение к частной производной структурной сложности по весу дуги. На рис. 8 показан (на качественном уровне) характер изменения приоритетности дуг орграфа. Продемонстрировано, что при одинаковых весах дуг (случай
Рис. 8. Приоритетность дуги
На рис. 9 показано явление структурной бифуркации для изначально не взвешенного орграфа (
Рис. 9. Структурная бифуркация Таким образом, критерий структурной сложности Цель анализа структурной сложности, соответствующая формуле (3) – сортировка орграфов. В нашем случае РОКС – сложная техническая система и для оценки ее структурной сложности необходимо дальнейшее развитие критериев. В таблице 2 дан перечень новых операторов, действующих на два абстрактных объекта. Они необходимы для изложения концепций структурной сложности замкнутых детерминированных технических систем со следующим формальным представлением
В представлении системы (5) Множество дуг системы
где Множество достижимостей систем
Замкнутость и сильная связность обозначаются одинаково:
Подсистема – аналог сильно связной подсистемы орграфа
где
Рис. 10. Иллюстрация к определению подсистемы Формальное определение абстрактной системы
где В соответствии с (10) двух абстрактных одинаковых систем не существует, т.е.
РОКС – параметризованная система (см. рис. 11). Мы идентифицируем структуру системы, но не утверждаем, что охватываем все возможные взаимодействия в системе.
Рис. 11. Параметризованная система: стрелки показывают аналогию с орграфами Формализация структурной сложности замкнутой детерминированной технической системы подразумевает, что должны быть найдены соответствующие этой задаче дескрипторы, которые, являясь непротиворечивыми, описывают искомую шкалу полностью и досконально. В свою очередь, шкала структурной сложности должна отражать цель анализа системы. Основными дескрипторами шкалы структурной сложности являются набор аксиом сложности и ее алгебра. Сначала вводится понятие «нулевая структурная сложность» (
Алгебра структурной сложности должна содержать операции сложения и умножения для подсистем
1. сложение сложностей,
2. Умножение сложностей,
Наряду с нулевой структурной сложностью необходимо ввести единичную структурную сложность
Следуя постулатам И.Пригожина, познание сложного производится путем упрощения – в данном случае необходимо выбрать дугу
Иллюстрацией (16) может служить рис. 12.
Рис. 12. Варианты состояния
Если нам удалось найти последовательность разрывов, которая минимизирует структурную сложность
Рис. 13. Оптимальная последовательность разрывов Опуская подробности (см. [11]), общий вид критерия структурной сложности можно упрощенно представить в следующем виде
где Важнейшим приложением теории структурной сложности может являться РОКС как техническая система большой размерности, поведение которой с трудом поддается осмыслению и количественному анализу. Вес дуги в РОКС является безразмерной величиной, вещественным числом. Это доля стоимости трафика абонентов сети в отношении к затратам на обслуживание линий связи. Проблематика РОКС показана на рис. 15. Более подробно эти аспекты отражены в работах [12-16].
Рис. 14. Иерархия расчетного модуля системы
Рис. 15. Проблематика РОКC Ставятся две задачи, которые необходимо решать на уровне РОКС. На рис. 16 показаны главные тенденции к постановке этих задач, показано, что двухзадачный комплекс подразумевает взаимодействие задач на уровне их взаимопроникновения.
Рис. 16. Основные тенденции решения проблем системного анализа РОКС Без ограничения общности, для исследования структуры РОКС применяем взвешенные орграфы. В данном случае 1. РОКС структурируется орграфом динамического развития 2. 3. Предполагается, что за период имитационного моделирования число вершин орграфа остается неизменным, тогда как множество дуг (связей между узлами сети) может меняться как во времени, так и в информационном пространстве. В каждый отдельно взятый момент времени орграф системы Число Внешние связи региональной компьютерной сети рассматриваются как множества Для оценки структурной сложности РОКС предлагается использовать преобразование
Рис. 17. Учет внешних связей РОКС
В результате преобразования, после переиндексации, получается орграф Политика
исходя из допущения, что энтропия сложных информационных систем связана со структурной сложностью монотонной зависимостью. В задаче (18)–(20) присутствуют: – – Оценку структурной сложности производим на основе матричного критерия с внутренней полиномиальной вычислительной сложностью. Для упрощения системы обозначений в последующих выкладках время Для нахождения сильно связных подсистем используется оператор структурной декомпозиции
В нахождении структурной сложности на всех уровнях рекурсии участвует конденсированная форма орграфа
Рис. 18. Иллюстрация к правилам конденсации орграфа РОКС Для нахождения
Параллельные вычисления необходимы в данном случае из-за большой размерности решаемой задачи и ее высокой внутренней вычислительной сложности. Рассмотрим матричный критерий применительно к орграфу
где Аксиоматика сложности РОКС порождает матричный критерий сложности – критерий предпочтительности
где значок * означает оптимальность иерархической кластеризации, когда используются все имеющиеся ресурсы региональной сети, причем для связей между подзадачами предпочтительными являются каналы наибольшей мощности с наименьшей загрузкой; индекс «1» означает, что дуга Критерии (17) и (25) применительно к РОКС являются двойственными, порождая одну и ту же иерархию распараллеливания. Ставим задачу поиска научно обоснованной стратегии реконструкции РОКС при наличии трендов (медленных изменений) и флуктуаций нагрузки на информационные каналы связи, активности пользователей. Анализ возможных путей развития сети осуществляется на базе параметризации структуры сети, представляемой в виде сильно связного ориентированного взвешенного орграфа. На рис. 19 иллюстрируется задача поиска времени ближайшей реконструкции. Сплошными линиями условно показано состояние орграфа РОКС без мероприятий реконструкции. Пунктирными линями изображены новые узлы и линии связи, ввод которых планируется осуществить. Состав нововведений считается известным. Требуется найти оптимальное время реконструкции: излишне ранняя реконструкция чревата тем, что она не предусматривает появление более совершенного оборудования в будущем, поэтому по вложениям денежных средств реконструкция может оказаться сравнимой с отложенной, срок же еще одной реконструкции может оказаться ощутимо близко.
Рис. 19. Поиск времени проведения ближайшей реконструкции
Излишне поздняя реконструкция также опасна: состав нововведений может оказаться недостаточным для покрытия возросших к этому времени запросов пользователей. Предлагается обобщить результаты статистического анализа на базе исследования поведения структурной сложности во времени. Для оценки структурной сложности в детерминированной сети нами используется рекурсивный критерий структурной сложности (17). Вводится понятие «стохастическая структурная сложность»: это случайная величина Для оценки стохастической структурной сложности используется статистика слежения за состоянием РОКС, по которой сначала производится выделение трендов на заданном периоде рассмотрения и выявление устойчивых колебаний нагрузок каналов, а затем – выделение случайной составляющей (по известным методикам). На основе этой информации производится параметризация стохастического состояния РОКС, итогом которой является назначение дугам орграфа весов в виде функций
где Качество QoS обслуживания работы РОКС оценивается по дисперсии стохастической структурной сложности
Рис. 20. Соответствие между дисперсией стохастической
Задача принятия решения по назначению времени ближайшей реконструкции иллюстрируется на рис. 21. Показано, что прогнозное время ближайшей реконструкции определяется моментом, когда колебания (или неуклонный рост) информационной энтропии, вычисляемой как величины, обратной к математическому ожиданию
Рис. 21. Решение задачи принятия решения по назначению времени ближайшей реконструкции РОКС
Таким образом, на основе теории сложности удается прогнозировать время ближайшей реконструкции при известном составе ее мероприятий. Наблюдение за состоянием РОКС должно осуществляться при поддержании заданного уровня QoS. Предложенная методика нашла применение в практических мероприятиях по реконструкции РОКС Тамбовской области. Список используемых источников
1. Подольский В.Е., Писецкий А.Ф. Использование Internet – и Intranet-технологий в сфере образования Тамбовской области // Материалы международной научно-методической конференции «Новые информационные технологии в университетском образовании». – Новосибирск, 1998. – С. 166 – 168. 2. Подольский В.Е. Создание инфраструктуры системы открытого образования. // Информатика и образование. 2001. – № 4. – С. 11 – 18. 3. Подольский В.Е., Храпов И.В., Овсянкин Т.В. Интеграция действующих систем управления ВУЗом в распределенной корпоративной сети ТГТУ // Тезисы докладов международной научно-методической конференции «Телематика - 2000». - СПб., 2000. - С. 62 – 63. 4. Храпов И.В., Мищенко С.В., Подольский В.Е., Букреев Д.В. Архитектура корпоративной информационной системы поддержки принятия решений. // Вестник ТГТУ. 2003. – Т. 9, – № 1. - С. 30 – 33. 5. Мищенко С.В., Подольский В.Е. Тамбовский государственный технический университет – центр информатизации региона // Тезисы докладов Всероссийской научно-технической конференции «Перспективные информационные технологии в высшей школе». – Тамбов, 1995. – С. 7 – 8. 6. Подольский В.Е., Писецкий А.Ф., Бродович С.М. Тамбовская область в Интернет // Тезисы докладов Всероссийской научно-методической конференции «Телематика-99». - СПб., 1999. – С. 136 – 137. 7. Подольский В.Е., Писецкий А.Ф., Инькова Н.А. Опыт ТамбовЦНИТ по развитию научно-технического международного сотрудничества и вовлечению вузов в международное информационное образовательное пространство // Тезисы и доклады научно-практической конференции «Региональная стратегия вхождения вузов в международное образовательное и научное пространство». – Тамбов, 2000. – С. 36 – 37. 8. Подольский В.Е. Десять лет работы Тамбовского государственного технического университета в качестве образовательного Интернет-провайдера // Труды Всероссийской научно-методической конф. «Телематика-2002», 3-6 июня 2002 г. – СПб., 2002. – С. 75 – 76. 9. Подольский В.Е., Писецкий А.Ф., Севастьянов С.Ю. Internet в сфере образования и науки Тамбовской области // Сб. докл. конф. Ассоциации научных и учебных организаций пользователей сетей передачи данных Relarn «Relarn'97», 16-17 декабря 1997 г. – Н. Новгород, 1997. – С. 12 – 14. 10. Куракин Д.В. Основы маршрутизации в телекоммуникационных сетях // Учеб. пособие. – М.: МГИРЭА, 2000. – 68 с. 11. Подольский В.Е., Толстых С.С. Повышение эффективности региональных образовательных компьютерных сетей с использованием элементов структурного анализа и теории сложности. – М.: Машиностроение-1, 2006. – 176 с. 12. Тихонов А.Н., Мищенко С.В., Подольский В.Е., Толстых С.С. Особенности математического моделирования современных компьютерных сетей в образовательной сфере. // Телематика-2003, Т.1, Санкт-Петербург, 2004. – С.78 – 79. 13. Подольский В.Е., Толстых С.С. Структурная оптимизация региональной образовательной компьютерной сети // Сб. трудов междунар. научно-техн. конф. «Информационные технологии в науке, технике и образовании». – Т.1. – Аланья-Севастополь, 2004 г., С.56 – 58. Подольский В.Е., Толстых С.С. Оптимизация кластерных вычислений с использованием критериев структурной сложности // Вторая Сибирская школа-семинар по параллельным вычислениям. – Томск: Изд-во Том. ун-та, 2004. – С.45 – 50. 14. Подольский В.Е., Толстых С.С. Оценка эффективности функционирования региональной образовательной компьютерной сети на основе критериев структурной сложности // Сб. трудов научно-практической конф. КБД-ИНФО-2004. – Сочи, 2004 г., С.159. 15. Подольский В.Е., Толстых С.С. Использование критериев структурной сложности для имитационного моделирования региональных компьютерных сетей // Сб. статей «Параллельные вычисления в задачах математической физики». – Изд-во РГУ. – Ростов, 2005. – С.67-75. 16. Podolskiy V.E. The use of stochastic structural complexity criteria for acceptance of decisions on reconstruction of a regional educational computer network // Materials of the International Scientific Conference “Information technologies in Education and Scientific research”. – Ege University. – 2005, pp. 234 – 237.
Публикации с ключевыми словами: структурный анализ, компьютерные сети, теория сложности Публикации со словами: структурный анализ, компьютерные сети, теория сложности Тематические рубрики: |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||