Оглавление:
1.1. Описание предметной области
1.2. Обзор опыта информатизации
предметной области
1.3. Системный анализ процессов
информатизации предметной области
1.4. Обоснование класса проектируемой
системы
1.5. Постановка задачи можно увидеть в
разделе приложение.
2. Теория математического аппарата применяемого в модулях
2.1. Определение топологии между
сегментами сети
2.2. Выбор активного, пассивного и
вспомогательного оборудования
3. Диаграмма вариантов использования
4. Реализация программного продукта
1. Системотехническая часть
С недавнего времени ИТ технологии стали развиваться очень бурно. Появление новых разработок в области сетевых технологи накрыла мир как волна. Общество уже не представляет себе жизнь без сотовых телефонов, Интернета, домашних сетей, корпоративных сетей и т.д. Но проектирование сетей достаточно трудоемкое занятие. Бросить два кабеля между домами соседей уже не является сверх задачей. Для решения задачи разработки сетей требуется профессиональный системный подход.
Поэтому была поставлена задача автоматизации процесса разработки сети. Для автоматизации сети требуется решение комплекса задач:
1) выбрать физическую топологию сети по критериям и по входным параметрам;
2) выбор логической топологии сети по критериям и по входным параметрам;
3) выбор технического обеспечения;
4) подготовка и реализация вывода рекомендаций по построению сети;
Проблема разработки крупномасштабных компьютерных сетей относится к NP-полным задачам, которые невозможно решить только математическими методами. Следовательно, система проектирования вычислительных сетей должна поддерживать гибридные модели представления знаний, работать с нечетко представленными и с разноформатными данными, то есть быть открытой. Более того, система должна иметь возможность общаться с пользователем на языке близком к естественному [1].
Задачей автоматизации проектирования сетей активно занимаются многие инженеры-исследователи, в частности: доцент Комарцова Л. Г., Колосов А. С., Пятаев О. В., Семашко А. В., Логунов Д.В., Аллаев А.Э., Вишневский В.М..
Комарова Людмила Георгиевна занимается проблемой автоматизации построения сетей достаточно давно. Ее публикации: «Исследование возможностей нейронных сетей для создания проекта локальной», «Методика имитационного моделирования вычислительных систем с использованием нейронной сети для обобщения результатов».
Колосов Александр Сергеевич опубликовал работу под названием «Построение логической топологии сети организации средствами среды SNMP».
Пятаев О. В. Нижегородский Государственный Технический Университет. Публикации: «Особенности формализации задачи оптимизации структуры кампусных сетей», «Использование методов эволюционного моделирования для поиска квазиоптимальных структур сетей кампусов».
Одна из наиболее интересных работ Логунова Д. «Принципы разработки интеллектуальных интерфейсов (на примере проектирования корпоративных сетей)».
«Теоретические основы проектирования компьютерных сетей», Вишнеский В.М., Техносфера, Москва 2003 год. Выдержка из данной монографии: «Повсеместное внедрение компьютерных сетей должно сопровождаться опережающим развитием фундаментальной теории в этой области, созданием инженерных методов анализа и синтеза, систем автоматизации проектирования, направленных на сокращение сроков и повышение качества проектирования компьютерных сетей.» [2]
На рынке предоставления услуг есть компании, которые занимаются созданием компьютерных сетей. Одна из таких компаний под названием «Тауэр-сети» (http://www.tower.ru) предлагает Интернет сервис создания ЛВС с помощью системы NetWizard (http://www.netwizard.ru). Возможно, кому-то покажется, что система NetWizard мало отличается от достаточно привычного конфигуратора, с помощью которого заказчику предлагается выбрать предпочтительное оборудование или ПО, однако это совсем не так. В отличие от конфигуратора, назначение которого - подготовить спецификацию путем управляемого системой выбора из заданного перечня конкретного оборудования, NetWizard - полноценная система, позволяющая строить ЛВС целиком, хотя и по определенному шаблону (при этом можно выбрать и подходящий шаблон проекта сети).
Цель системы NetWizard - помочь клиенту не только сформировать техническое задание на построение локальной сети, но и получить оптимальное решение.
Минусы проекта NetWizard. Как мною говорилось ранее приложение NetWizard представлено в Интернете в качестве рекламного инструмента, для продвижения услуг компании «Тауэр-сети». Авторы этого проекта дают достаточно скудные рекомендации по построению сети, а также это приложение работает только в Интернет среде.
Задача проектирования сети выполняется, специалистами по сетям. Они подбирают оптимальную топологию сети. Выбирают необходимое оборудование, программное обеспечение и т.д. Этот процесс занимает достаточно много времени, поэтому многие инженеры-исследователи ищут математические методы для построения сети (см. п. 1.2.).
И так разобьем задачу построения сети на подзадачи, которые необходимо выполнить для получения рекомендации, которые будут на выходе системы:
1) Определение входных параметров для сети:
§ Тип сети (Офисная сеть, CAN (Campus-Area Network – кампусная сеть), MAN (Metropolitan-Area Network – сеть городского масштаба), WAN (Wide-Area Network – широкомасштабная сеть), GAN (Global-Area Network – глобальная сеть)).
§ Количество сегментов сети
§ Расстояние между сегментами сети
§ Количество рабочих станции в каждом сегменте
§ Максимальное расстояние между станциями в каждом сегменте
§ Необходимые сервисы в сети (e-mail, ftp и т.д.) или в отдельном сегменте
§ Надежность каждого сегмента сети
§ Таблица тяготения между сегментами сети
§ Предполагаемая расширяемость сети
2) Определение топологии между сегментами сети
Данный этап строится на методологии, которую предложил Аллаев А.Э. в
своей статье «Выбор топологии построения сетей абонентского доступа» (Журнал
"Электросвязь", №5,
3) Определение количества активного, пассивного и вспомогательного оборудования в каждом сегменте сети
4) Оптимальный выбор активного, пассивного и вспомогательного оборудования
На данном этапе используется математический метод многокритериального анализа «Метод ПРИНН» Пиявского С.А.
5) Настройка сети
Данный модуль строится на основе экспертной системы продукционного типа.
6) Подготовка и реализация вывода рекомендаций по построению сети
Поставленную задачу, можно отнести к СППР в области построения сетей. Так как в данной системе реализуются как методики для реализации экспертных систем, которые относятся к классу задач ИИ, так и математические методы, которые позволяю принимать решения на основании многокритериального анализа (метод ПРИНН).
В предметной области (построения сетей) накопилось достаточно много теоретических и практических знаний, которые необходимо объединять и использовать в проектной деятельности.
1.5.1.
Цели проектирования
Разработка программы реализующей комплекс поставленных задач см. п.1.3.
2. Теория математического аппарата применяемого в модулях программы
Для определения базовой топологии построения магистрального участка САД представим ее в виде неориентированного графа G={A,B}, где A={ai}, i=1,...,N – множество узлов, с которыми сопоставляются узел предоставления услуг в выносные модули (ВМ) сети (мультисервисные абонентские концентраторы), базовые станции WLL и т.д.); B={bij} – множество возможных ребер, i, j = 1, …, N, которым соответствую линии связи соединяющие узлы ai с узлами aj;
D = A U B = {dij} – множество элементов графа G. Расположение узлов сети и возможные трассы строительства линий задаем матрицей L = | lij |, где lij – длинна ребра bij (lij = ∞, строительство линии между узлами ai и aj невозможно).
Ожидаемые надежности ребер представим в виде матрицы P= [pij], где pij – ожидаемая надежность (вероятность исправного состояния) линии между узлами ai и aj.
Односвязная сеть с числом ребер N-1 и полносвязная сеть с N (N-1) / 2 составляют две предельные топологии сети связи, а все другие топологии по числу ребер находятся между этими структурами.
Главной характеристикой топологии сети является обеспечиваемой ею связность сети h. Переход от односвязной (h=1) сети к топологиям с большим числом связей осуществляется добавлением новых ребер, что с одной стороны приводит к росту стоимости сети из-за необходимости строительства новых линий, а с другой стороны к увеличению надежности сети за счет организации новых связей. Следовательно, достаточная связность сети h определяет уровень стоимости построения САД в рамках данной топологии.
Задачу выбора базовой топологии построения магистрального участка САД можно сформулировать в следующем виде. При заданных G={A,B}, L={lij} и P={pij} необходимо определить такую минимальную - связную топологию, которая обеспечивает заданную надежность Pд, сети абонентского доступа.
Выбор базовой топологии - один из начальных этапов построения САД и поэтому расчета точного значения надежности не требуется. Достаточно оценки достижимого уровня надежности сети при данной топологии. Для САД, являющихся сложными многофункциональными системами, состоящими из элементов, разнородных по своим свойствам и назначению, сложно определить однозначно, что следует понимать под ее надежностью, практически невозможно. Если предположить, что все связи на сети имеют одинаковую важность, то надежность САД можно характеризовать вероятностью того, что данная сеть является связной, т.е. любые две пары узлов данной сети связаны хотя бы одним путем.
Для простоты оценки надежности будем полагать, что все ребра САД имеют
одинаковую надежность (pij = p для всех i и j) и вероятности выхода их из строя являются
взаимно независимыми случайными величинами.
Очевидно, что надежность P(h) - надежность h - связной N - узловой сети
можно определить как вероятность того, что из общего числа ребер M(h) , содержащихся в данной
сети в неисправном состоянии находятся не более M(h) – (N
-1) произвольных ребер. Это определение правомерно, так как в дальнейшем, неисправность
хотя бы еще одного ребра делает сеть несвязной. Следовательно, используя распределение Бернулли можно получить:
(1)
h=1, 2, … , N-1
Минимальное число ребер M(h) для построения h 3 связной N узловой сети определяется по формулам:
- при четном N (M(h)=M(h-1)+N/2) (2)
- при нечетном N и четном h (M(h)=M(h-1)+(N+1)/2) (3)
- при нечетном N и четном h (M(h)=M(h-1)+(N-1)/2) (4)
Используя выражения (2)–(4) и учитывая, что M(1)=N-1, а M(2)=N рассчитаем
M(h) при различных N и h .
В таблице 1 приведены результаты расчетов M(h) и P(h) при различных значениях h,
для N=5; 10; 15 и вероятности исправного состояния ребер p = 0,6 и p=0,9 . Зависимости
представлены на рис. 1. и 2.
Рис.1
Рис 2
Таблица 1
Результаты расчетов показывают, что увеличение связности сети h вызывает более интенсивный рост числа ребер M(h) (необходим для построения САД), чем рост надежности этой сети P(h) . Кроме того, переход от односвязной к кольцевой топологии позволяет при наименьших затратах (за счет включения в сеть только одного дополнительного ребра) обеспечить наибольший прирост надежности САД.
Выражения (1)-(4) также дают возможность решить вопрос выбора топологии
САД по критерию стоимости. Если обозначить через c1 стоимость одного ребра
сети (стоимость строительства линии между узлами ai и aj), через c2
стоимость одного часа нарушения связности сети, то задачу выбора оптимальной
топологии САД можно сформулировать в следующем виде. При заданных значениях N, p, c1, c2 из
возможных топологий сети h=1,2,
… , N-1 необходимо
определить такую топологию h*,
при которой достигается минимум функции
(5)
где T - срок службы САД в часах.
На рис. 3 и
4 приведены зависимости
С(h).
Рис. 3
Рис.
4
Результатов расчета показывает, что функция C(h) имеет явно выраженный минимум и снижение надежности ребер приводит к смещению оптимума функции в сторону увеличения h, т.е. к необходимости построения САД с более сложными многосвязными топологиями.
Таким образом, метод позволяет выбрать оптимальную топологию построения сетей при ожидаемой надежности их ребер. При этом можно определить минимально связную топологию, обеспечивающую заданную надежность сети или оптимальную топологию по критерию стоимости. [3]
Для выбора активного, пассивного и вспомогательного оборудования в данной работе применяется метод ПРИНН. Алгоритм реализации этого метода состоит из следующих шагов:
1) Выбор наибольших и наименьших оценок по каждому критерию.
mi, где i 0 1…n
Mi, где i 0 1…n
m – минимальные значения критериев
M – максимальные значения критериев
n – количество критериев.
2) Перевод качественных критериев в количественные
(1) ,
где i=1..n, j= 1..p
где p – количество сообщений,
A – матрица оценок.
3) Нормировка критериев
если более высокая оценка соответствует более высокому качеству, то
(2)
если наоборот, то
(3)
Для столбцов m и M выбираются новые максимальные и минимальные значения.
4) Расчет эффективности.
, где j = 1..p (4)
q – столбец веса критериев
E – столбец эффективности сообщений
Метод ПРИНН разработан С.А. Пиявcким [9]
2.3. Настройка сети
Математический аппарат данного модуля строится на ЭС продукционного типа.
Ниже предоставлено описание ЭС:
Продукционная модель или модель,
основанная на правилах, позволяет представить знания в виде предложений типа
«Если (условие), то (действие)».
Под «условием» понимается некоторое предложение-образец, по которому осуществляется поиск в базе знаний, а под «действием» (консеквентном) – действия, выполняемые при успешном исходе поиска (они могут быть промежуточными, выступающими далее как условия и терминальными или целевыми, завершающими рабочую систему).
Бывает два типа вывода прямой (от данных к поиску цели) и обратный (от цели для ее подтверждения – к данным). Данные - это исходные факты, хранящиеся в базе фактов, на основании которого запускается машина логического вывода или интерпретатор правил, перебирающий правила из продукционной базы знаний.
Продукционная модель чаще всего применяется в промышленных экспертных системах. Она привлекает разработчиков своей наглядностью, высокой модульностью, легкостью внесения дополнений и простой механизм логического вывода. [4] [6] [7]
3.
Диаграмма вариантов использования
4. Реализация программного
продукта
На данном этапе
реализован метод «ПРИНН» Пиявского С.А. и методика Аллаева А. Э..
Листинг метода Prinn (программа
зашита в dll, которая в дальнейшем будет хранить всю «математику»):
//mRC - количество критериев
//nVar - количество переменных
//A[1,j] - табличка (матрица)
ввриант(шина,звезда,кольцо) - критерий
//gT[j] - определяет, качественный критерий или
количественный
//если качественный, то он равен 1,
происходит перевод качественной оценки в количественную
//gN[j] - направление к максимуму
или минимуму
//gV[j]- данный показатель
определяет важность критерия
//E[i]
- результат
procedure
prinn(A:TTableKoef;gT:array of Boolean;gN:array of Boolean;gV:array of
Integer;var E:array of real); export; stdcall;
var
i,j:Integer;
minA:array of real;
maxA:array of real;
qq:Boolean;
Ediv:Real;
mCR:Integer;
nVar:Integer;
stepen,stepen1:Integer;
begin
mCR:=high(A.A[high(A.A)]);
nVar:=high(A.A);
SetLength(minA,mCR+1);
SetLength(maxA,mCR+1);
//Нахождение предельных значение в
столбцах
j:=-1;
While (j<(mCR)) do
begin
inc(j);
minA[j]:=A.A[0,j];
maxA[j]:=A.A[0,j];
i:=0;
While (i<(nVar)) do
begin
inc(i);
if minA[j]>A.A[i,j] then
minA[j]:=A.A[i,j];
if maxA[j]<A.A[i,j] then
maxA[j]:=A.A[i,j];
end;
end;
//Перевод качественных критериев в
количественные
j:=-1;
While (j<(mCR)) do
begin
inc(j);
qq:=gT[j];
if qq=true then
begin
i:=-1;
While (i<(nVar)) do
begin
inc(i);
stepen:=StrToInt(floattostr(A.A[i,j]));
stepen1:=StrToInt(floattostr(maxA[j]));
if stepen <>0
then
A.A[i,j]:=(power(3,stepen)-1)/(power(3,stepen1)-1)
else A.A[i,j]:=0;
end;
//optim++++++++++++++++++++++++++++++++++++++++
minA[j]:=A.A[1,j];
maxA[j]:=A.A[1,j];
i:=-1;
While (i<(nVar)) do
begin
inc(i);
if minA[j]>A.A[i,j]
then minA[j]:=A.A[i,j];
if maxA[j]<A.A[i,j]
then maxA[j]:=A.A[i,j];
end;
//optim++++++++++++++++++++++++++++++++++++++++
end;
end;
//Перевод на минимум и нормирование
(напровление к максимуму или миним)
i:=-1;
While (i<(nVar)) do
begin
inc(i);
j:=-1;
While (j<(mcR)) do
begin
inc(j);
if maxA[j] <> minA[j]
then
begin
if gN[j]=false then
A.A[i,j]:=1-(A.A[i,j]-minA[j])/(maxA[j]-minA[j])
else
if gN[j]=true then
A.A[i,j]:=1-(maxA[j]-A.A[i,j])/(maxA[j]-minA[j])
else A.A[i,j]:=1;
end
else A.A[i,j]:=1;
end;
end;
//Расчет эффективности
i:=-1;
While (i<(nVar)) do
begin
inc(i);
E[i]:=0; Ediv:=0;
j:=-1;
While (j<(mcR)) do
begin
inc(j);
E[i]:=E[i]+(power(3,(gV[j]-1))*A.A[i,j]);
Ediv:=Ediv+power(3,(gV[j]-1));
end;
E[i]:=E[i]/Ediv;
end;
i:=-1;
While (i<(nVar)) do
begin
inc(i);
E[i]:=100*E[i];
end;
end;
Листинг реализованной методики
Аллаева А. Э. (на данный момент подпрограмма отлаживается):
type
Mas1=array of integer;
var
i,j:integer;
Kc:integer;
Nc:Mas1;
h:integer;
p:real;
c1:real;
c2:real;
T: real;
procedure
Topolog(Kc,h:integer;p,T,c1,c2:real;Nc:Mas1);
type
M1=array of array of integer;
M2=array of array of real;
var
i,j,k,N:integer;
C:real;
Mh:M1;
Ph:M2;
Ch:M2;
function
Fact(a:integer):Extended;
var
i:integer;
n:Extended;
begin
n:=1;
for i:=1 to a do n:=n*i;
Fact:=n;
end;
begin
SetLength(Ph,h);
for i:=0 to h-1 do
for j:=0 to Kc-1 do SetLength(Ph[i],Kc);
SetLength(Mh,h);
for i:=0 to h-1 do
for j:=0 to Kc-1 do SetLength(Mh[i],Kc);
SetLength(Ch,h);
for i:=0 to h-1 do
for j:=0 to Kc-1 do SetLength(Ch[i],Kc);
for i:=0 to Kc-1 do
begin N:=Nc[i];
for j:=0 to h-1 do
begin
if j=0 then Mh[j,i]:=N-1;
if j=1 then Mh[j,i]:=N;
if j>1 then
begin
if(N Mod 2=0)then
Mh[j,i]:=Mh[j-1,i]+N div 2;
if(N Mod 2>0)and((j+1)
Mod 2>0)then Mh[j,i]:=Mh[j-1,i]+(N+1)div 2;
if(N Mod 2>0)and((j+1)
Mod 2=0)then Mh[j,i]:=Mh[j-1,i]+(N-1)div 2;
end;
end;
end;
for j:=0 to h-1 do WriteLn(J+1,'
',Mh[j,0],' ',Mh[j,1],' ',Mh[j,2]);
ReadLn;
for i:=0 to Kc-1 do
begin
for j:=0 to h-1 do
begin Ph[j,i]:=0;
for k:=0 to Mh[j,i]-(Nc[i]-1)
do
begin
C:=Fact(Mh[j,i])/(Fact(k)*Fact(Mh[j,i]-k));
Ph[j,i]:=Ph[j,i]+(C*Power(1-p,k)*Power(p,Mh[j,i]-k));
end;
end;
end;
for j:=0 to h-1 do WriteLn(J+1,'
',Ph[j,0]:10:7,' ',Ph[j,1]:10:7,' ',Ph[j,2]:10:7);
ReadLn;
for i:=0 to Kc-1 do
begin
for j:=0 to h-1 do
Ch[j,i]:=c1*Mh[j,i]+c2*(1-Ph[j,i])*T;
end;
for j:=0 to h-1 do WriteLn(J+1,'
',Ch[j,0]:10:7,' ',Ch[j,1]:10:7,' ',Ch[j,2]:10:7);
ReadLn;
end;
begin
Kc:=3;
h:=14;
SetLength(Nc,Kc);
Nc[0]:=5;
Nc[1]:=10; Nc[2]:=15;
c1:=7000;
c2:=1; T:=131400;
p:=0.6;
Topolog(Kc,h,p,T,c1,c2,Nc);
p:=0.9;
Topolog(Kc,h,p,T,c1,c2,Nc);
WriteLn('
============================');
ReadLn;
end.
Использованная
литература:
1) «Принципы
разработки интеллектуальных интерфейсов (на примере проектирования
корпоративных сетей)» Логунов Д.В. (http://prof9.narod.ru/, 01.11.2006)
2) «Теоретические
основы проектирования компьютерных сетей», Вишнеский В.М., Техносфера, Москва
2003 год.
3) «Выбор топологии построения сетей
абонентского доступа», Аллаев А.Э., Журнал "Электросвязь", №5,
4) «Базы знаний
интеллектуальных систем», Гаврилова Т.А., Хорошевский В.Ф., издательство
«ПИТЕР»
5) «Аппаратные
средства локальных сетей», Михаил Гук, издательство «ПИТЕР»
6) «Искусственный интеллект. Стратегии и методы
решения сложных проблем.», Четвертое
издание, Джордж Ф. Люгер, Москва – Санкт-Петербург-Киев 2003
7) «Искусственный
интеллект. Методы поиска решений.», Н.Нильсон., Издательство мир, Москва 1973
год
8) «Структурные
кабельные системы», А.Б. Семенов, С.К.Стрижаков, И.Р.Сунчелей, издательство
«ДМК», 2002 год
9) «Методы
оптимизации и оптимального управления», Пиявский С. А., Самара
