Методика поиска оптимальной топологии сети

Содержание

Введение ………………………………………………………………..5

1. Задание на курсовой проект по дисциплине «Диагностика и надежность автоматизированных систем»…..…………………………….…7

2. Методика поиска оптимальной топологии сети ..……………….10

2.1 Первая ступень фильтрации  множества топологий……………...10

2.2 Вторая ступень фильтрации  множества топологий……………...15

2.3Третья ступень фильтрации множества топологий……………….15

3.Выбор оптимальной топологии……………………………………….17

Заключение………………………………………………………… ……23

Список использованной литературы…………………………………..24

 

 

 

 

 

Введение

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

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

С целью обеспечения высокой надежности современной техники в производстве и увеличения срока ее эксплуатации широко используют разнообразные методы и автоматизированные средства неразрушающего контроля и технического диагностирования. Однако трудоемкость операции контроля для различных видов техники составляет от 15 до 50 % трудоемкости основных операций изготовления. Затраты на ремонт и обслуживание техники в связи с ее износом по многолетним статистическим данным превышают стоимость новых станков или машин в 5-8 раз, а радиотехнической аппаратуры в 10-12 раз. По зарубежным данным, 20-25 % отказов различного рода оборудования вызывается ошибками обслуживающего персонала, 40-90 % происшествий на транспорте, в различных энергосистемах, а также большинство травм на производстве являются результатом ошибочных действий людей. Во всех  отраслях промышленности и народном хозяйстве в целом принимаются активные меры по улучшению организации работ, по повышению эффективности и надежности техники при ее разработке, в производстве и эксплуатации. Развивается и совершенствуется материально-техническая база промышленности – основа высокого качества и надежности техники. Разрабатываются прогрессивные материалы, осваиваются новые технологические процессы, совершенствуется производственное, испытательное оборудование, разрабатываются и все шире внедряются системы автоматизированного проектирования, изготовления, контроля и диагностики, внедряются отраслевые и межотраслевые информационно- управляющие системы управления качеством продукции.

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

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

 

1. Задание на курсовой проект по дисциплине 
   «Диагностика и надежность автоматизированных систем»

Задано некоторое предприятие, состоящее из некоторого множества основных зданий и подсобных строений, распределенных по всей территории предприятия.

В основных зданиях располагаются пользователи сети, которым обязательно требуется связь с пользователями в других зданиях. В подсобных строениях пользователей нет и связь с этими строениями необязательна, однако они могут  использоваться как «промежуточные» узлы связи коммуникационной сети, особенно, когда имеются ограничения на максимальную длину непрерывного отрезка коммуникационного кабеля. На рисунке ниже представлена условная схема расположении зданий и строений.

Задана матрица {Dij},i = 1...9, j = 1...9, «кабельных расстояний» между зданиями и строениями. Кабельное расстояние - полная длина кабеля в километрах, требуемого для соединения коммуникационного оборудования одного здания или строения с оборудованием другого здания или строения, с учетом всех особенностей трассы кабеля и запаса по длине.

 

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

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

• Математическая модель надежности связи: Марковская модель надежности. Интенсивность отказов коммутаторов ядра для всех зданий и строений одинакова и равна λ = 1/720 час-1 . Интенсивность восстановлений коммутаторов ядра так же одинакова и равна µ = 1/24 час-1.
• Экономическое ограничение: Стоимость (в рублях) прокладки одного метра кабеля (с учетом стоимости кабеля и работ) равна С.Суммарная стоимость (в миллионах рублей) прокладки всех отрезков кабеля, обеспечивающих цель проекта, ограничена бюджетом проекта, равным V.
• Техническое ограничение: Максимальная длина(в километрах) непрерывного отрезка кабеля равна Lmax.Если между какими-либо зданиями невозможно проложить, прямой непрерывный отрезок кабеля в силу превышения максимальной кабельной длины, необходимо соединять здания через промежуточные подсобные строения.
• Цель проекта: При заданных ограничениях рассчитать топологию связей между зданиями и строениями, обеспечивающую максимальную PВБСОЗ – вероятность безотказной связи между основными зданиями, в которых находятся пользователи сети, при заданной математической модели надежности.

 

2.Методика поиска оптимальной топологии сети

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

Решением является оптимальная топология сети, состоящей из n = 9 коммутаторов, представленной в виде списка L={(i, j)}, i= 1…n, j= 1…n пар связанных коммутаторов.

Очевидно, что число всевозможных пар связываемых коммутаторов составляет n*(n-1)/2 =36. Учитывая, что между любой парой коммутаторов кабель может либо присутствовать, либо отсутствовать, множество всевозможных топологий U={L} связей содержит |U|=236 различных вариантов – это большое количество, но его можно сократить, используя имеющиеся техническое и экономическое ограничения.

 

2.1 Первая ступень  фильтрации множества топологий.

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

Обозначим в качестве X матрицу размером nn , формируемую с учетом матрицы «кабельных расстояний»  Dij между зданиями и максимально допустимой длины кабеля Dmax следующим образом:             

 

По сути, матрица X показывает между какими парами коммутаторов допускается по техническому ограничению прокладка непрерывного отрезка кабеля. Соответственно, множество вариантов топологий U уменьшается до «отфильтрованного» подмножества Ʌ:

Ʌ=

Проводим первую ступень фильтрации. Тем самым отсекаем все топологии, которые содержат связи, превышающие по длине заданную максимально допустимую длину Dmax=0,9. Строим матицу, показывающую доступные связи между коммутаторами по длине кабеля

 

Из данной матрицы видно, что «разрешенными» парами коммутаторов являются такие пары, как: (1;2), (1;5), (1;6), (1;7), (1;8), (2;1), (2;3), (2;5), (2;6), (2;7), (2;8), (2;9), (3;2), (3;4), (3;5), (3;6), (3;7), (3;8), (3;9), (4;3), (4;5), (4;6), (4;7), (4;8), (4;9), (5;1), (5;2), (5;3),(5;4), (5;6), (5;7), (5;8), (5;9), (6;2), (6;3), (6;4), (6;5), (6;7), (6;8), (6;9), (7;1), (7;2), (7;3), (7;4),(7;5), (7;6), (7;8), (7;9), (8;1), (8;2), (8;3), (8;4) , (8;5), (8;6), (8;7), (8;9), (9;1), (9;2), (9;3), (9;4) ,(9;5), (9;6), (9;7), (9;8).

2.2 Вторая ступень  фильтрации множества топологий.

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

Соответственно, формируется второе «отфильтрованное» подмножество топологий:

Ω=

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

При C=400руб/м и бюджете, равным 6 млн.рублям, проходят все топологии содержащие не более 37 связей, так как:

 

 

Схема 1:

 

Рассчитаем общую длину кабеля L, необходимого для соединения коммутаторов в схеме 1:

L= 0,4+0,8+0,5+0,5+0,3+0,9+0,6+0,3+0,3=4,6(км)

L=4600 (м);

Общая стоимость равна: 4600*400=1 840 000 рублей.

 

 

 

 

 

Схема 2:

Рассчитаем общую длину кабеля L, необходимого для соединения коммутаторов в схеме 3:

L=5400 (м);

Общая стоимость равна: 5400*400=2 160 000 рублей

 

Схема 3:

Рассчитаем общую длину кабеля L, необходимого для соединения коммутаторов в схеме 3:

L=4600 (м);

Общая стоимость равна: 4600*400=1 840 000 рублей

 

 

 

Схема 4:

Рассчитаем общую длину кабеля L, необходимого для соединения коммутаторов в схеме 3:

L=3900 (м);

Общая стоимость равна: 3900*400=1 560 000 рублей

Схема 5:

Рассчитаем общую длину кабеля L, необходимого для соединения коммутаторов в схеме 3:

L=4900 (м);

Общая стоимость равна: 4900*400=1 960 000 рублей

 

2.3 Третья ступень  фильтрации множества топологий.

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

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

Для установления «связности» топологии используется так называемая матрица достижимости R, которая в свою очередь, вычисляется по матрице смежности A.

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

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

Признаком «несвязности» является наличие нулей в матрице достижимости. Для связной топологии матрица достижимости всегда состоит из одних единиц.

Тогда, мы можем ввести «индикатор связности» W и вычислять его по матрице достижимости R, вычисляемой, в свою очередь, по матрице смежности A, формируемой по списку L, представляющему топологию связей:

W(L)=

Тогда, используя индикатор связности W, мы можем формировать третье «отфильтрованное» подмножество, содержащее только связные топологии:

Ѱ=

Нужные топологии выбраны теперь приступаем к третьей ступени фильтрации. связности W, и отсекая варианты, для которых W = 0, мы получаем «отфильтрованное» подмножество Ѱ, содержащее всего |Ѱ|=5 вариантов «связных» топологий L:

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Выбор оптимальной топологии.

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

Для схемы 1 составим матрицу смежности А по заданному количеству коммутаторов.

 

 

 

Строим матрицу достижимости R при q=0. В этом случае, в качестве начального состояния матрицы достижимости принимается матрица смежности A в неизменном виде, и далее по рекуррентной схеме вычисляется матрица достижимости:

 

Из полученной матрицы достижимости, очевидно, что все коммутаторы (в том числе и граничные) достижимы друг для друга. Индикатор связности граничных коммутаторов, который, учитывая, что PV={6,7,8,9}, определяется по угловой подматрице достижимости Rij=1, W=1, Ѱ0=1.

При q=1 имеем =4 сочетания FV = {6}, FV = {7}, FV = {8}, FV = {9} 2 отказа из 4 опорных коммутаторов (при FV = {6}, FV = {7}). Для каждого сочетания вычисляем матрицу достижимости, принимая в качестве начальной матрицы достижимости матрицу смежности А с обнуленными строками и столбцами, имеющими номера, входящие в сочетание FV. В результате вычислений получаем 4 матрицы достижимости:

 

 

Во всех 4-х случаях граничные коммутаторы остаются связанными между собой, поскольку, в угловой подматрице все элементы во всех 4 случаях равны 1, и, соответственно индикатор связности граничных коммутаторов: W=1, то коэффициент Ѱ1 = 2