автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Исследование методов структурной оптимизации кампусных сетей

Введение.

Глава 1. Постановка задачи оптимизации структуры кампусной сети.

1.1. Особенности функционирования кампусных сетей.

1.2. Характеристики эффективности функционирования кампусных сетей.

1.3. Постановка задачи оптимизации структуры кампусной сети.

1.4. Основные подходы к оптимизации вычислительных сетей.

Выводы.

Глава 2. Анализ методов оптимизации структуры кампусных сетей.

2.1. Математическая формулировка задачи оптимизации кампусной сети.

2.2. Выбор математического аппарата для оптимизации структуры кампусной сети.

2.3. Описание выбранного метода решения задачи.

Выводы.

Глава 3. Синтез алгоритма оптимизации структуры кампусной сети.

3.1. Разработка методики решения задачи оптимизации на основе генетического алгоритма.

3.2. Дополнительные алгоритмы.

3.3. Рекомендации по практическому применению алгоритма и пример реализации.

Выводы.

Глава 4. Сравнительная оценка алгоритмов оптимизации структуры кампусных сетей.

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

4.2. Определение эффективности синтезированного алгоритма.

Выводы.

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

Частным случаем корпоративных сетей являются кампусные сети, то есть вычислительные сети, объединяющие все вычислительные устройства в одном здании, или нескольких близлежащих зданиях. В настоящее время кампусные сети - один из наиболее распространенных классов вычислительных сетей, кампусная сеть есть практически в любой крупной организации. Корпоративная сеть крупного предприятия может объединять несколько кампусных сетей, находящихся в различных городах или странах. Кампусные сети обладают определенными особенностями, налагающими соответствующие требования на проектирование. К числу таких особенностей относятся:

1. Относительно небольшая площадь, и, как следствие, использование для передачи данных высокоскоростных технологий локальных сетей.

2. Использование в качестве основного коммуникационного устройства не маршрутизаторов и концентраторов, а коммутаторов различной мощности.

3. Использование структурированных кабельных систем.

4. Гетерогенность сети (одна кампусная сеть может состоять из подсетей, построенных на базе различных сетевых технологий).

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

Целью работы является оптимизация структуры кампусной сети при заданных ограничениях на её технические характеристики.

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

Основные положения, выносимые на защиту:

1. Предлагаемая математическая модель кампусной сети позволяет осуществлять ее структурную оптимизацию.

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

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

Научная новизна диссертационной работы заключается в следующем:

1. Сформулирована и формализована задача оптимизации структуры кампусной сети.

2. Разработан эволюционный метод решения задачи оптимизации структуры кампусной сети.

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

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

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

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

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

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

Сведения о внедрении полученных результатов приведены в Приложении 2.

Краткое содержание работы.

Основные результаты диссертационной работы были опубликованы в 11 работах [41-45, 58,72,78-81], из них 3 статьи и 8 тезисов докладов.

Данные о внедрении результатов диссертационной работы приведены в приложении 2.

ЗАКЛЮЧЕНИЕ

В результате выполнения диссертационной работы получены следующие результаты:

1. На основе анализа литературных источников выделены характерные признаки кампусных сетей.

2. Формализована задача оптимизации структуры кампусной сети, записана математическая модель кампусной сети.

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

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

- разработаны специализированные генетические операторы;

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

- исследован метод пульсации численности популяции.

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

6. Создана программная система разработанного метода. Выработаны рекомендации по практическому применению программной системы.

167

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

8. Проведен сравнительный анализ методов оптимизации кампусных сетей. Сделан вывод о целесообразности использования разработанного метода для применения на практике.

1. Зайченко Ю.П. Динамические задачи структурного синтеза распределенных вычислительных сетей. Механизация и автоматизация упр., 1982, № 1, с. 31-36.

2. Янбых Г.Ф., Столяров Б.А. Оптимизация многоярусной сети передачи информации // Автоматика и вычислительная техника. 1974. - №6. - с.49-54.

3. Вишневский В.М. Принципы построения системы автоматизации проектирования сетей ЭВМ // Автоматизированные системы массового обслуживания. М.: Ин-т проблем управления, 1982. - с. 58-70.

4. Якубайтис Э.А. Информационно-вычислительные сети. М.: Финансы и статистика, 1984. - 232 с.

5. Мартин Д. Сети связи и ЭВМ. Ч. I. М.: «Связь», 1974. 232 с.

6. Шварц М. Сети связи: протоколы, моделирование и анализ. 4.1. М.: Наука, 1992.-336 с.

7. Янбых Г.Ф., Эттингер Б.Я. Проектирование структуры отраслевой ВЦ. -М.: Энергия, 1974,- 104 с.

8. Максименков A.B. Выбор выделенных каналов связи и оптимизация потока в сети с пакетной коммутацией // Кибернетика. 1983. - № 6. - с. 72-76.

9. Зайченко Ю.П., Печурин Н.К., Кондратова Л.П. Интерактивная система проектирования топологии сетей ВЦ. Техн. Кибернетика, 1979, № 3, с. 51-52.

10. Sinclair, M.C., Minimum Cost Topology Optimisation of the COST 239 European Optical Network Proc. Intl. Conf. on Artificial Neural Networks and Genetic Algorithms, Ales, France, April 1995, pp.26-29.

11. B.Parnis, N., Jones, E.V., Sinclair, M.C. & O'Mahony, M.J., Hierarchical Network Design for ACTS OPEN: Initial Considerations, Proc. 12th UK Performance Engineering Workshop, Edinburgh, September 1996, pp. 141-155.

12. Labourdette J.-F. P., Traffic optimization and reconfiguration management of multiwavelength multihop broadcast lightwave networks,Computer Networks and ISDN Systems, 1998, pp. 981-998.

13. Выставкин Я.П. Сети обмена информацией между ЭВМ. М.: Наука, 1975.-216 с.16.0лифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. СПб.: Издательство «Питер», 1999. - 672 с.

14. Кульгин М.В. Технологии корпоративных сетей. Энциклопедия. СПб.: Издательство «Питер», 1999. - 704 с.

15. Янбых Г.Ф., Столяров Б.А. Оптимизация информационно-вычислительных сетей. М.:Радио и связь, 1987. - 232 с.

16. Васильев В.И., Буркин А.П., Свириденко В.А. Системы связи: Учеб. Пособие для втузов. М.: Высш. Шк., 1987. - 280 с.20.3айченко Ю.П., Гонта Ю.В. Структурная оптимизация сетей ЭВМ. К.: Техшка, 1986.- 168 с.

17. Новиков Ю.В., Карпенко Д.Г. Аппаратура локальных сетей: функции, выбор, разработка. М., Издательство ЭКОМ, 1988. - 288 с.

18. Олифер В.Г., Олифер Н.А. Новые технологии и оборудование IP-сетей. -СПб.: БХВ Санкт-Петербург, 2000. - 512 с.

19. Норенков И.П., Трудоношин В.А. Телекоммуникационные технологии и сети. М.: Изд-во МГТУ им. Н.Э. Баумана, 1998. 232 с.

20. Якубайтис Э.А. Локальные информационно-вычислительные сети. Рига: Зинатне, 1985. 284 с.

21. Семенов А.Б., Стрижаков С.К., Сунчелей И.Р. Структурированные кабельные системы. Стандарты, компоненты, проектирование, монтаж и техническая эксплуатация. М.: КомпьютерПресс, 1999. - 482 с.

22. Кульгин М.В. Коммутация и маршрутизация IP/IPX трафика. М.: КомпьютерПресс, 1998. - 320с.

23. Ганьжа Д. Коммутаторы в локальной сети // LAN. 1997. - № 3. - С. 21-25.

24. Евдокименко А, Тутов А., Подольный Е. Большая стройка.// Сети. 2000. -№ 1. - С. 78-80.

25. Гринфилд Д. Оптическая революция. // LAN. 2000. - № 3. - С. 93-98.

26. Корнышев Ю.Н., Пшеничников А.П., Харкевич А.Д. Теория телетрафика: Учебник для вузов. М.: Радио и связь, 1996. - 272 с.

27. Берганов И.Р., Гордиенко В.Н., Крухмалев В.В. Проектирование и техническая эксплуатация систем передачи: Учеб. Пособие для вузов. -М.: Радио и связь, 1989. 272 с.

28. Верма П. Сети связи ЭВМ. Оценка эффективности функционирования: структурный анализ.: Пер. с англ. М.: Радио и связь, 1992. - 114 с.

29. Юрлов Ф.Ф. Технико-экономическая эффективность сложных радиоэлектронных систем. -М.: Сов. Радио, 1980. 280 с.

30. Валиев Т.А., Нишанбаев Т.Н., Лосский И.О. Оптимизация информационно-вычислительных систем методами имитационного моделирования на ЭВМ. Ташкент; Фан., 1991. 132 с.

31. Штейнер С.М. Оценка эффективности локальных вычислительных сетей. -СПб.: О-во «Знание», 1991. 28 с.

32. Филин Б.П. Методы анализа структурной надежности сетей связи. М.: Радио и связь, 1988. - 208 с.

33. Бертсекас Д., Галлагер Р. Сети передачи данных: Пер. с англ. М.: Мир, 1989.-544 с.

34. Шварц М. Сети ЭВМ. Анализ и проектирование. Пер. с англ. / Под ред. В.А.Жожикашвили. -М.: Радио и связь, 1981. 336 с.39.0кунев Ю.Б. Опыт оптимального проектирования систем связи. Л.: Типография ЛДНТП, 1971. - 36 с.

35. Построение сетей ЭВМ: Пер. с япон. / Като М., Иимура Д., Токоро М., Тома Ё. М.: Мир, 1988. - 307 с.

36. Пятаев О.В., Семашко A.B. Моделирование процессов передачи данных по радиоканалам // Моделирование и оптимизация сложных систем. Межвузовский тематический сборник научных трудов. 1997 г. - С. 133140.

37. Гепнер A.B., Семашко A.B., Пятаев О.В. Алгоритм быстрого синтеза цифрового многополосного КИХ-фильтра // Научно-техническая конференция факультета информационных систем и технологий: тезисы докладов / Н.Новгород. 1998г. Стр. 84.

38. Berry L., Murtagh В., McMahon G., Sugden S. Optimization models for communication network design, Proceedings of the Fourth International Meeting Decision Sciences Institute, Sydney Australia, 1997.

39. Максименков A.B., Селезнев M.JI. Основы проектирования информационно-вычислительных систем и сетей ЭВМ. М.: Радио и связь, 1991.-320 с.

40. Griffith P.S., Proestaki A., Sinclair М.С., Heuristic Topological Design of Low-cost Optical Telecommunication Networks, Proc. 12th UK Performance Engineering Workshop, Edinburgh, September 1996, pp. 129-140.

41. Янбых Г.Ф., Эттингер Б.Я. Методы анализа и синтеза сетей ЭВМ. Л.: Энергия, 1980.-96 с.

42. Scott В., Michael L. Managing IP Networks With Cisco Routers. O'Reilly, 1997.

43. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей: Пер. с англ. М.: Мир, 1984.-496 с.

44. Фрэнк Г., Фриш И. Сети связи и потоки / Пер. с англ. Под ред. Д.А. Поспелова. -М.: Связь, 1978. 448 с.

45. Филькенштейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976. - 264 с.

46. Вычислительные сети и сетевые протоколы / Дэвис Д., Барбер Д., Прайс У., Соломонидес С.: Пер. с англ. М.: Мир, 1982. - 563 с.

47. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979. 600 с.

48. Пятаев О.В., Семашко А.В. Математическое представление задачи оптимизации структуры кампусной сети // Радиоэлектронные ителекоммуникационные системы и устройства: Межвузовский тематический сборник научных трудов. 2000 г. - С. 49-55.

49. Голого Ш.У., Яновский Г.Г. Оптимальное распределение пропускных способностей в сети передачи данных с отказами // Коммутация и управление потоками в сетях связи: Сб. науч. трудов учеб. ин-тов связи / Л.: ЛЭИС., 1987. С. 20-25.

50. Вентцель Е.С. Исследование операций: задачи, принципы, методология.-М.: Наука., 1988.-208 с.

51. Лэсдон Л. Оптимизация больших систем. М.: Наука, 1975. - 432 с.

52. Berry L., Murtagh В., Sugden S., McMahon G. An Integrated GA{LP Approach to Communication Network Design. Baltzer Journals, January 20, 1998, pp.,.

53. Жиглявский A.A., Жилинскас А.Г. Метода поиска глобального экстремума. М.: Наука, 1991. - 248 с.

54. Castillo L., Gonzalez A. Distribution network optimization: Finding the most economic solution by using genetic algorithms, European Journal of Operational Research, October, 1996, pp. 527-537.

55. DeJong K., Spears W.M. Using genetic algorithms to solve NP-complete problems. In J.D. Schaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms, Morgan Kaufmann, 1989, pp. 124-132.

56. Schuster P., Stadler P.F. Landscapes: Complex optimization problems and biopolymer structures. Computers Chem., 1994, pp. 295-314.

57. Адаптация случайного поиска. Растригин Л.А., Рипа К.К., Тарасенко Г.С. Рига, «Зинатне», 1978. 243 с.

58. Букатова И.Л., Михасев Ю.И., Шаров A.M. Эвоинформатика: Теория и практика эволюционного моделирования. М.: Наука, 1991. - 206 с.

59. Шмальгаузен И.И. Кибернетические вопросы биологии. Новосибирск: Наука, 1968. 224 с.

60. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности / Г.К. Вороновский, К.В. Махотило, С.Н. Петрашев, С.А. Сергеев. -X.: ОСНОВА, 1997. 112 с.

61. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности / Г.К. Вороновский, К.В. Махотило, С.Н. Петрашев, С.А. Сергеев. X.: ОСНОВА, 1997. - 112 с.

62. Д.И.Батищев, С.А.Исаев, Е.К.Ремер. Эволюционно-генетический подход к решению задач невыпуклой оптимизации. / Межвузовский сборник научных трудов "Оптимизация и моделирование в автоматизированных системах", Воронеж, ВГТУ, 1998г, стр.20-28.

63. Пятаев О.В. Применение генетического алгоритма для оптимизации структуры кампусной сети // Радиоэлектронные и телекоммуникационные системы и устройства: Межвузовский тематический сборник научных трудов. 2000 г. - С. 55-61.

64. Д.И.Батищев, С.А.Исаев Оптимизация многоэкстремальных функций с помощью генетических алгоритмов. / Межвузовский сборник научных трудов "Высокие технологии в технике, медицине и образовании", Воронеж, ВГТУ, 1997г, стр.4-17.

65. В.В. Кулейчик, В.М. Кулейчик. Генетический алгоритм размещения графа // Изв. РАН. ТиСУ. 2000 г., №5.

66. В.М. Кулейчик. Генетические алгоритма. Состояние. Проблемы. Перспективы // Изв. РАН. ТиСУ, 1999 г., № 1.

67. Свами М., Тхуласираман К. Графы, сети и алгоритмы: Пер. с англ. М.: мир, 1984.-455 с.

68. Семашко A.B., Пятаев О.В., Баранов В.Г. Оптимизация архитектуры распределенных вычислительных сетей // Научно-техническая конференция факультета информационных систем и технологий НГТУ: тезисы докладов / Н.Новгород, 1999г.С. 57-58.