Перепроектирование конфигурации сетевого оборудования Сафонов А.В. студент, МФТИ Левин М.Ш., с.н.с., к.т.н., ИППИ РАН Секция 2. Интегрированные системы проектирования и управления технологическими процессами. PDM - системы ( ) VI международная конференция и выставка CAD/CAM/PDM – 2006 Институт проблем управления РАН, лаборатория 18, Москва

Задача проектирования сети Топология Правила/стандарты Физические условия Технологии Предпочтение лишь 1 Оборудование

Задача выбора конфигурации Возникает при Проектировании сети Перепроектировании сети

Задача выбора конфигурации Определим ее как частный случай Блочной задачи о рюкзаке + Многокритериальное ранжирование (для оценки вариантов)

Схема сети филиала предприятия

Схема сети - примера В ней мы можем выделить 4 точки, требующие установки следующего оборудования: Коммутатор третьего уровня или выше, имеющий не менее 8 портов Маршрутизатор для безопасного широкополосного доступа к сети головного офиса и к Интернету Коммутаторы, предоставляющие не менее 30 портов (VLAN3) Коммутаторы, предоставляющие не менее 30 портов (VLAN7)

Требования и критерии оценки Параметр оценкиГруппа кластеризованных критериев Базовые параметры гарантированной надежностиНадежность ИзбыточностьНадежность Прогнозируемое время между ошибкамиНадежность Базовые средства безопасностиНадежность Современные средства безопасностиНадежность Базовая поддержка технологий Quality of service (QoS)Производительность Расширенная поддержка технологий Quality of service (QoS)Производительность Поддержка базовых возможностей по управлениюЭффективность управления Легкость внедрения и эксплуатацииЭффективность управления Поддержка ПО Network Assistant Эффективность управления Работа на макс. возможной для линии передачи скоростиПроизводительность МасштабируемостьПроизводительность Поддержка технологии Power over the Ethernet (PoE)Прочие особенности Возможность объединения в стэкПрочие особенности UplinksПроизводительность

Требования и критерии оценки Мы объединяем все критерии в 4 группы: ПроизводительностьC 1 Эффективность управленияC 2 НадежностьC 3 Прочие функцииC 4

Требования и критерии оценки С1С1 С2С2 С3С3 С4С4 полезность Кластеризация критериев Многокрит. ранжирование

Список оборудования Общие инженерные требования Список возможных устройств Детальное описание требований Оценки по критериям C 1 C 2 C 3 C 4

Список оборудования Список подходящих устройств с оценками, группа 4 УстройствоC1C1 C2C2 C3C3 C4C4 R

Многокритериальное ранжирование Альтернативы Критерии Оценки Относительный вес (важность) критерия i

Метод порогов несравнимости Электре Для каждой парывычисляем коэффициенты Согласия и несогласия

Метод порогов несравнимости Электре Правило: A u лучше чем A v если где p и q - пороги (напр., ) Метод порогов несравнимости Электре основан на применении этого правила и обеспечивает единственную оценку для каждой альтернативы

Задача о рюкзаке

Бинарная задача о рюкзаке Дробная задача о рюкзаке Каждая задача о рюкзаке является NP-трудной (за полиномиальное время приводится к задаче о разбиении)

Задача о рюкзаке - методы Релаксационные и верхних границ Жадный алгоритм Методы ветвей и границ Динамическое программирование Приближенные решения Sahni Ibarra и Kim Точные алгоритмы для больших n (числа эл.)

= Бинарная задача о рюкзаке + Разбиение множества предметов N на r подмножеств N i + требование: выбрать 1 предмет из каждого подмножества Блочная задача о рюкзаке

Динамическое программирование Алгоритмы ветвей и границ Ключевую роль имеет критерий доминирования: Блочная задача о рюкзаке - методы если

Блочная задача о рюкзаке - методы Динамическое программирование: - рекурсивная функция, которая дает значение полезности оптимального решения подзадачи, сост. из j подмножеств с ограничением Оптимальное решение - F(r,c)

Задача перепроектирования сети 4 группы устройств Оценки устройств по критериям C 1 C 2 C 3 C 4 Единственная оценка (полезность) для каждого устройства Наилучший возможный набор устройств (не нарушающих ограничения) Многокритер. ранжирование (Электре) Блочная задача о рюкзаке

Задача перепроектирования сети N3N3 el. index group … … N3N k2k2 m1m1 N элементов в r = 4 подмножествах Оценка по Электре в едином множестве Сортировка по убыванию полезности Последовательное добавление элементов в рюкзак Разработана программа в среде MatLab

Задача перепроектирования сети Появление новых требований –> - Если они не удовлетворены установленным оборудованием – -> требуется улучшение Возможные пути улучшения: Перепроектирование лишь для узлов, к которым предъявляются новые требования Полное перепроектирование для всех узлов

Задача перепроектирования сети Возможные варианты выбора устройств 48 1G портов M+ портов и 24 1G портов M+ портов и 24 1G портов M+ портов и 12 1G портов Альтернативы действий для выполнения новых требований 1.Установленное оборудование им уже удовлетворяет и никаких мер предпринимать не надо 2.Приобрести новое устройство (в дополнение) 3.Приобрести новое устройство (для замены)

Задача проектирования сети - результаты Бюджет Устройство, выбранное в группе

Частичное перепроектирование Улучшение Устройств о C1C1 C2C2 C3C3 C4C4 R Добавить 5.2 за 1995 к Добавить 5.1 за 3295 к Добавить 1.1 за 4795 к Добавить 1.3 за 5595 к Добавить 1.5 за 5995 к Добавить 1.9 за 6995 к Добавить 1.7 за 7495 к Добавить 1.11 за 7795 к Заменить 3.5 (350 возврат) на Заменить 3.14 (900 возврат) на Список возможных вариантов улучшения с оценками

Частичное перепроектирование Случай Бюдже т Добавляемое устройство Оценки Заменяюще е устройство Оценки , , , , , , , , , Изначально удовлетворяет новым требованиям Предварительные результаты

Частичное перепроектирование - результаты Случай Бюджет Устройство, выбранное в группе 123 Добавляемо е устройство ,52,53,5 5,2 4, , , ,62,93,21 5,1 4, , ,11 6-1,62,103,10-4,6

Полное перепроектирование – результаты Случай Бюджет Устройство, выбранное в группе

Гибридный подход Результаты полного перепроектирования могут быть полезны при анализе возможных решений (частичного перепроектирования) Множества наилучших вариантов, полученных при полном и частичном перепроектировании могут : a)не пересекаться b)иметь непустое пересечение c)Полностью совпадать

Гибридный подход – 2 множества

Гибридный подход Альтернативы в вышеуказанных случаях: a)Необходимо дополнительно рассматривать близость реализуемых вариантов к наилучшим (полученным при полном перепроектировании), возвращаясь к оценкам C 1 C 2 C 3 C 4 b)результат (наилучший вариант) - элементы, принадлежащие обоим множествам c)мы можем произвести частичное перепроектирование и быть уверены в том, что получили абсолютно лучший вариант

Гибридный подход в действии Бюджет Устройство, выбранное в группе 1234 Частичное перепроектирование Полное перепроектирование

Возможные улучшения 1.Усовершенствование кластеризации критериев 2.Учет влияния устройств друг на друга 3.Дальнейшее изучение вопросов относительной важности узлов и соответствующих устройств 4.Учет различных вариантов топологий-технологий (или с использованием указанного в п.2, или как некоторые виртуальные устройства с учетом п.3) 5.Дальнейшее исследование вопроса о качественности получаемого набора с точки зрения влияния оценок отдельных устройств

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

Спасибо за внимание!