Перепроектирование конфигурации сетевого оборудования            

А.В. Сафонов, студент, МФТИ
М.Ш. Левин, с.н.с., к.т.н., ИППИ РАН

1. Введение

Задача проектирования сети включает три основные подзадачи: проектирование топологии, выбор реализуемых технологий и выбор оборудования. Задачи выбора топологии и технологий в сетях исследуются во многих работах (например, [Ошибка! Источник ссылки не найден.,Ошибка! Источник ссылки не найден.,-1], по общим вопросам дизайна сети см. [-4]). Следует заметить, что во многих реальных ситуациях топология предопределена стандартами (например, СКС) или физическими условиями, а среди технологий предпочтение отдается лишь одной единственной. Таким образом, проблема выбора конфигурации оборудования обретает все большее значение. В данной работе эта задача рассматривается в применении к перепроектированию сети. В качестве формальной модели применяется блочная задача о рюкзаке (multiple-choice knapsack problem) [5], дополнительно для оценки конфигураций используется многокритериальное ранжирование [6]. Предложены три схемы решения задачи перепроектирования конфигурации оборудования: (а) полного перепроектирования, (б) частичного перепроектирования, (в) гибридного подхода. Приведены примеры численных расчетов.

2. Коммуникационная сеть

2.1 Описание сети

В качестве базового примера рассматривается часто используемая схема сети филиала предприятия или небольшого офиса. Указанная схема приведена на рисунке 1 (схема основана на материалах фирмы Cisco, см. сайт [8]).

Рисунок 1. Схема сети филиала предприятия

В рассматриваемом примере сети можно выделить 4 точки, требующие установки следующего оборудования:

-      коммутатор 3+ уровня, имеющий не менее 8 1G портов;

-      маршрутизатор для безопасного подключения к Интернету;

-      коммутаторы, имеющие не менее 30 портов (VLAN3);

-      коммутаторы, имеющие не менее 30 портов (VLAN7).

2.2 Требования и критерии оценки

На основании требований к сети можно выделить список параметров, приведенный в Таблице 1.

Множество параметров сети разбивается на 4 группы (кластеры):

-      производительность (C1);

-      управляемость (т.е. эффективность управления, C2);

-      надежность (C3);

-      прочие особенности (C4).

Дополнительно обозначен требуемый для устройства ресурс R.

2.3 Список оборудования

В общем наборе имеется 4 группы устройств (соответствующие 4 точкам в сети, см. 2.1). В Таблице 2 приведено удовлетворяющее требованиям оборудование (с учетом разбивки по группам) с оценками по 4 кластеризованным группам критериев.

 

Таблица 1

Соответствие параметров оценки и кластеризованных групп

Параметр оценки

Группа кластеризованных критериев

Базовая гарантированная надежность

Надежность

Избыточность

Надежность

Прогнозируемое время между ошибками

Надежность

Базовые средства безопасности

Надежность

Современные средства безопасности

Надежность

Базовая поддержка технологий QoS

Производительность

Расширенная поддержка технологий QoS

Производительность

Базовые возможности по управлению

Управляемость

Легкость внедрения и эксплуатации

Управляемость

Поддержка ПО “Network Assistant“

Управляемость

Максимально возможная для линии скорость

Производительность

Масштабируемость

Производительность

Скорость аплинков (uplinks)

Производительность

Поддержка технологии Power over the Ethernet

Прочие особенности

Возможность объединения в кластер (стэк)

Прочие особенности

3. Модели

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

           

4. Задача перепроектирования сети

4.1 Описание задачи

Задача перепроектирования конфигурации оборудования состоит в выборе наилучшего набора устройств на основе трех схем решения: (а) полного перепроектирования, (б) частичного перепроектирования, (в) гибридного подхода. Наилучший набор оборудования – это выборка одного элемента (т.е. устройства) из каждой группы альтернативных вариантов таким образом, чтобы было получено наилучшее соответствие требованиям (т.е., чтобы выбранные устройства имели наивысшие оценки по критериям)  при выполнении бюджетного ограничения. Для решения данной задачи используется комбинаторный подход [1,7].

Исследуется следующая практическая ситуация: рассматриваемый в качестве примера офис (см. 1.1) расширяется, и это приводит к новым требованиям к сетевой инфраструктуре. В частности, необходимо добавить 10 1GE портов (UTP) в VLAN 3 (группа №3).

Таблица 2

Список подходящих устройств с оценками

#

C1

C2

C3

C4

R

#

C1

C2

C3

C4

R

1.1

7

4

6

5

4795

3.7

4

7

6

5

4790

1.2

7

6

6

6

8790

3.8

4

7

6

4

3590

1.3

7

4

6

5

5595

3.9

9

5

7

7

13995

1.4

7

6

6

6

9590

3.10

9

7

7

7

21990

1.5

8

5

8

6

5995

3.11

9

5

6

8

15495

1.6

8

7

8

7

9990

3.12

9

7

6

8

23490

1.7

8

5

7

6

7495

3.13

8

5

8

6

6995

1.8

8

7

7

7

11490

3.14

8

7

8

6

8990

1.9

8

5

8

7

6995

3.15

8

5

7

7

8495

1.10

8

7

8

8

10990

3.16

8

7

7

7

10490

1.11

8

5

7

6

7795

3.17

8

5

7

7

7995

1.12

8

7

7

7

11790

3.18

8

7

7

7

11990

1.13

7

5

7

8

11995

3.19

8

5

6

8

9495

1.14

7

7

7

9

15990

3.20

8

7

6

8

13490

1.15

6

5

9

7

7995

3.21

7

5

9

6

4995

1.16

6

7

8

8

8995

3.22

7

7

9

6

6990

2.1

3

4

4

4

949

3.23

7

5

7

7

6495

2.2

4

4

4

4

1049

3.24

7

7

7

7

8490

2.3

5

5

5

4

1695

4.1

8

5

8

7

10990

2.4

5

6

7

5

1895

4.2

8

7

8

7

14980

2.5

6

7

8

6

2495

4.3

8

5

7

8

13290

2.6

6

7

8

6

2995

4.4

8

7

7

8

17280

2.7

6

7

8

7

4845

4.5

7

5

9

7

7990

2.8

6

7

8

7

7445

4.6

7

7

9

7

11980

2.9

8

7

8

6

2995

4.7

7

5

7

8

10290

2.10

8

7

8

7

4845

4.8

7

7

7

8

14280

2.11

8

7

8

7

7445

4.9

5

4

6

5

6990

3.1

5

4

6

5

4495

4.10

5

4

6

5

3590

3.2

5

4

6

5

2495

4.11

5

5

5

5

5790

3.3

6

4

5

6

6590

4.12

5

7

6

6

6990

3.4

5

5

5

5

3995

5.1

6

4

5

6

3295

3.5

5

5

5

5

2495

5.2

5

3

5

3

1995

3.6

5

7

6

5

4495

5.3

4

7

6

5

2495

 

Таблица 3

Первоначальные конфигурации оборудования

 

Бюджет

выбор в группе №

 

Бюджет

выбор в группе №

1

2

3

4

1

2

3

4

1

12000

1.1

2.01

3.05

4.10

4

30000

1.6

2.09

3.21

4.06

2

15500

1.5

2.05

3.05

4.10

5

40000

1.6

2.09

3.10

4.10

3

20000

1.9

2.05

3.21

4.10

6

50000

1.6

2.10

3.10

4.06

 

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

-      перепроектирование лишь для узлов, к которым предъявляются новые требования

-      перепроектирование для всех узлов (с учетом изменившихся требований)

4.2 Описание схемы решения

Как видно из требований, необходимо 10 1GE портов в дополнение к старым 30 портам, которые обеспечивают как минимум 100-мегабитную скорость подключения. В результате требуется 30 100M+ портов и 10 1G портов. Этому требованию отвечают следующие  варианты выбора устройств: 48 1G/24 100M+ 24 1G/48 100M+ и 24 1G/48 100M+ и 12 1G портов. Таким образом, возможны следующие варианты действий для выполнения новых требований:

-      установленное оборудование им уже удовлетворяет и никаких мер предпринимать не надо;

-      приобрести новое в дополнение к уже установленному устройству;

-      приобрести новое и заменить им установленное ранее устройство.

4.3 Частичное перепроектирование конфигурации

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

В нашем случае требуется рассмотреть в соответствии с алгоритмом все возможные варианты выбора устройств в группе №3, не нарушающие наложенного ресурсного ограничения. Рассмотрим случаи № 2, 4 и 6 из таблицы 3 (с бюджетами в 15500, 30000 и 50000). Случай №6 удовлетворяет также и новым требованиям, а №2 и 4 - не удовлетворяют и требуют добавления нового устройства или замены старого более совершенным. Как было отмечено, для них возможны различные варианты улучшения.

Следующие результаты были получены для случаев № 2, 4 и 6 (см. табл. 3) с несколькими ресурсными ограничениями (новое ограничение = выделенный новый бюджет + неизрасходованная часть старого). В них попали лишь варианты добавления нового устройства, т.к. во всех случаях они оказались предпочтительней замены. В других условиях может быть выгоднее провести замену, чем присоединять еще одно устройство.

Таблица 4

Выбранные устройства при различных бюджетах (частичное п/п)

Случай №

Бюджет

Устройство, выбранное в группе №

1

2

3

Добавляемое #

4

2

2000

1,5

2,5

3,5

5,2

4,10

4000

5,1

6000

1,5

4

3500

1,6

2,9

3,21

5,1

4,6

6000

1,5

8000

1,11

6

-

1,6

2,10

3,10

-

4,6

4.4 Полное перепроектирование конфигурации

На практике полное перепроектирование ограниченно применимо ввиду чрезвычайно больших (в сравнении с частичным перепроектированием) затрат, но представляется целесообразным провести расчеты и для этого случая. Их результаты могут помочь в анализе нашей конфигурации. Необходимо решить задачу проектирования, состоящую из нового набора для группы № 3, а для остальных (№1,2 и 4) – из старых наборов (см. соответствующие разделы таблицы 2).

Следующие результаты были получены при разных ресурсных ограничениях (бюджетах) для случаев № 2, 4 и 6 (Таблица 3).

Таблица 5

Выбранные устройства при различных бюджетах (полное п/п)

№

Бюджет

# выбранное в группе №

1

2

3

4

2

17500

1.5

2.09

5.02+3.05

4.10

19500

1.9

2.09

5.02+3.05

4.10

21500

1.9

2.09

5.01+5.03

4.10

4

33500

1.6

2.10

3.18

4.11

36000

1.6

2.10

3.18

4.05

38000

1.6

2.09

3.18

4.06

6

50000

1.6

2.10

3.10

4.06

4.5 Гибридный подход к перепроектированию

Как уже было отмечено выше, в практических ситуациях зачастую проведение полного перепроектирования невозможно ввиду ресурсных ограничений. Однако, именно полное перепроектирование обычно дает наилучшее возможное решение. Таким образом, имеется следующие множества вариантов решений: (1) множество всех возможных вариантов, (2) множество наилучших вариантов, полученных при полном перепроектировании и (3) множество наилучших вариантов, полученных при частичном перепроектировании. Сущность гибридного подхода к проектированию заключается в детальном изучении этих множеств для анализа возможных наборов устройств и нахождения наилучшего реализуемого варианта.

4.5.1 Описание схемы решения

Рассмотрим множества наилучших вариантов, полученных при полном и частичном перепроектировании. Эти множества могут: a) не пересекаться; b) иметь непустое пересечение (см. рис. 2); c) полностью совпадать.

Рисунок 2. Множества наилучших вариантов

Во-первых, самым простым является случай c): можно произвести частичное перепроектирование и быть увереным в том, что получили наилучший вариант. Далее, в случае b) необходимо считать результатом элементы, принадлежащие обоим множествам. Наконец, случай c): в нем должны рассматриваться близость реализуемых вариантов к наилучшим (полученным при полном перепроектировании). Таким образом, возникает задача нахождения предметов, наиболее близких к множеству “идеальных” предметов. Подход к этой задаче основывается на следующем: вернуться к оценкам элементов по группе критериев C, изучить оценки реализуемых вариантов, а далее попытаться найти наиболее “близкие” к “идеалам”.

4.5.2 Анализ численных результатов

Рассмотрим варианты, отвечающие ресурсным ограничениям в 17500 и 19500. Для первого варианта имеется лишь одно отличие – в группе № 2 при частичном перепроектировании выбрано устройство 2.5 вместо 2.9. Их оценки очень слабо отличаются, разница в ценах – также невелика. Таким образом, можно сказать, что реализуемый вариант почти совпадает с наилучшим. Для второго варианта имеется существенное отличие выбранного набора от наилучшего (полученного при полном перепроектировании). Таким образом можно сделать вывод о том, что такой вариант улучшения не очень эффективен и расходование дополнительных средств не дает ожидаемого выигрыша в качестве.

5. Заключение

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

6. Список использованных источников

1.       N.A. Kuznetsov, M.Sh. Levin, V.M. Visnevsky, Some Combinatorial Optimization Schemes for Multi-Layer Network Topology. IMACS 2005, Paris, July 2005.

2.       H. Noltmeier, H.-C. Wirth, S.O. Krumke, Network Design and Improveemnt. ACM Computing Surveys, 32(3es), Artcile No. 2, Sept. 1999.

3.       P.M. Pardalos, D. Du, (Eds.) Network Design: Connectivity and Facilities Location. AMS, Providence, 1998.

4.       M.W. Murhammer, K.-K. Lee, P. Motallebi, P. Borghi,  K. Wozabal, IP Network Design Guide, IBM RedBook, 1999.

5.       S. Martello, P. Toth, Knapsack Problem: Algorithms and Compouter Implementation. Wiley, New York, 1990.

6.       B. Roy. Multicriteria Methodology for Decision Aiding. Kluwer, 1996.

7.       M.Sh. Levin. Combinatorial Engineering of Decomposable Systems, Kluwer, Boston, 1998.

8.       Cisco Systems corp., official site http://www.cisco.com