Разработка системы автоматизированного расчёта оптимальных потоков в сетях передачи данных

- Пограничные маршрутизаторы автономной системы (Autonomous System Boundary Router - ASBR) - это маршрутизаторы, имеющие как минимум один интерфейс с внешней сетью (другой автономной системой). Причем это может быть как не OSPF сеть, так и другая сеть, работающая под управлением протокола OSPF. Эти маршрутизаторы могут импортировать (есть еще один термин - перераспределять) информацию из не OSPF сети в сеть OSPF и наоборот.

Маршрутизатор одновременно может классифицироваться как маршрутизатор разного типа. Например, если маршрутизатор подключен к зоне 0 и зоне 1, а также к не OSPF сети, его можно классифицировать как маршрутизатор ABR, ASBR и магистральный маршрутизатор.

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



Рисунок 4.7 - Типы маршрутизаторов

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

Напомним, что базы данных состояния каналов соседних маршрутизаторов синхронизированы, что означает, что они синхронизированы между маршрутизатором, его выделенным маршрутизатором (DR) и его резервным выделенным маршрутизатором (BDR).

4.11.3 Стоимость суммарного маршрута

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

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

- Тип 1 (Е1) - для пакетов Е1 метрика этого типа вычисляется сложением внешней и внутренней стоимости каждого канала, который проходит на своем пути пакет. Такой тип пакета используется при рассылке множества объявлений маршрутизатором ASBR на одну и ту же автономную систему;

- Тип 2 (Е2) - это тип, принимаемый по умолчанию. Для пакетов Е2 метрика состоит только из внешней стоимости и не зависит от внутренней составляющей маршрута. Такой тип пакетов используется, когда хотя бы один маршрутизатор рассылает объявления о маршруте на внешнюю автономную систему. Маршруты типа 2 предпочтительнее маршрутов 1. Это справедливо только в том случае, если к получателю не существует двух маршрутов, имеющих равную стоимость.

4.11.4 Типы зон

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

- Стандартная зона (standard area) - зона, работающая в соответствии с описанием, приведенным в разделе 4.1. Такая зона может принимать пакеты обновлений (внутри зоны), суммарные маршруты (между зонами) и внешние маршруты;

- Магистральная (транзитная) зона (backbone (transit) area) - при подключении множества зон магистральная зона занимает центральное положение. С ее помощью подключаются все другие зоны. Магистральная зона всегда обозначается как "зона 0". Все остальные зоны должны быть подключены к этой зоне для обмена информацией. Магистральная сеть протокола OSPF имеет свойства стандартной зоны OSPF;

- Тупиковая зона (stub area) - зона, не принимающая информацию о маршрутах, являющихся внешними для данной автономной системы (т.е. в сетях, которые работают под управлением протокола, отличного от OSPF). Например, о маршрутах, берущих начало в не OSPF источниках. При необходимости направлять трафик за пределы автономной системы маршрутизатором используется маршрут по умолчанию. Маршрут по умолчанию обозначается как 0.0.0.0;

- Полностью тупиковая зона (totally stubby area) - зона, которая не принимает маршруты внешней автономной системы или суммарные маршруты из других зон, являющихся внутренними для данной автономной системы. Вместо этого, при необходимости выслать пакет в сеть, являющуюся внешней по отношению к зоне, маршрутизатор делает такую рассылку с помощью стандартного маршрута. Полностью тупиковые зоны являются "ноу-хау" компании Cisco;

- Не совсем тупиковая зона (not-so-stubby area, NSSA) - зона, импортирующая ограниченное число внешних маршрутов. Количество маршрутов ограничено только теми, которые необходимы для обеспечения связности между зонами.

4.11.5 Функционирование протокола OSPF в многозонных средах

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

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

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

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

- Пакет посылается из исходной сети на граничный маршрутизатор ABR;

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

- Граничный маршрутизатор ABR зоны, в которой находится получатель, отсылает пакет по зоне в сеть получателя.

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

Шаг 1. Характеристики процесса маршрутизации внутри зоны описаны выше. Заметим, что перед рассылкой суммарных LSA-пакетов граничным маршрутизатором ABR вся внутренняя зона должна быть синхронизирована.

Шаг 2. Граничный маршрутизатор ABR пересматривает базу данных каналов и генерирует суммарные пакеты LSA. И отсылает их во все сети, о которых ему известно. Существует возможность уменьшения суммарного количества записей LSA, настройки процедуры суммирования маршрутов таким образом, что множественные зоны могут быть представлены одним-единственным IP-адресом. Чтобы получить возможность использовать процесс суммирования маршрутов, зоны должны иметь совместную IP-адресацию. Хорошее планирование IP-адресного пространства позволяет минимизировать количество LSA-пакетов, рассылаемых граничным маршрутизатором ABR.

Шаг 3. Суммарные пакеты LSA в составе LSU-пакетов рассылаются через все интерфейсы граничного маршрутизатора ABR, подключенного к внешним зонам, кроме следующих исключений:

- Суммарный LSA-пакет не рассылается при подключении интерфейса к соседнему маршрутизатору, не готовому к обмену данными;

- Суммарный пакет LSA также не рассылается, если интерфейс подключен

к полностью тупиковой зоне;

- Рассылка LSA не производится, если суммарный LSA включает (внешний) маршрут типа 5 и интерфейс подключен к тупиковой или полностью тупиковой зоне.

Шаг 4. Получив суммарные LSA-пакеты, граничный маршрутизатор ABR или ASBR добавляет их в свою базу данных состояния каналов и рассылает ее по своей локальной зоне. Внутренние маршрутизаторы записывают полученную информацию в соответствующие базы данных. Отметим, что, для того чтобы уменьшить количество маршрутизирующей информации, хранимой внутренними маршрутизаторами, зону можно объявить тупиковой;

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

Шаг 1. Маршрутизаторы рассчитывают пути к получателям в пределах своих зон и добавляют эти записи в таблицы маршрутизации. Это пакеты LSA типа 1 и 2.

Шаг 2. Все маршрутизаторы, за исключением тех, которые находятся в полностью тупиковых зонах, вычисляют пути к другим зонам в пределах сети. Это записи с межзонными маршрутами или LSA типа 3 и 4. При наличии как межзонного, так и внутризонного пути к получателю сохраняется внутризонный путь.

Шаг 3. Все маршрутизаторы, за исключением тех, которые находятся в тупиковой зоне, вычисляют пути к получателям, находящимся во внешних автономных системах (тип 5).

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

Рисунок 4.8 - Рассылка LSU по многим зонам

маршрутизация алгоритм граф программа

5. Реализация алгоритмов расчёта потоков в сетях передачи данных

5.1 Использованные средства разработки

В качестве основного средства разработки была использована среда Microsoft Visual Studio .NET 2003, а весь код программы написан на языке C++ с использование классов MFC (Microsoft Foundation Classes - Базовые Классы Microsoft).

MFC была разработана для облегчения программирования Windows-приложений фирмой Microsoft, ещё в 1992 году. Сейчас она представляет собой мощный набор классов C++, которые позволяют программировать приложения Windows 95,98/NT на достаточно высоком уровне абстракции, и вместе с тем открывают для опытных программистов легкий доступ к функциям более низкого уровня, что позволяет писать эффективные приложения и полностью использовать все возможности операционной системы.

MFC является альтернативой системам визуального программирования, таким как Delphi или Visual Basic, предназначенной для опытных программистов. На сегодняшний день подавляющее большинство программ разрабатывается при помощи Microsoft Visual С++ и MFC. MFC - это стандарт программирования под Windows и "интернациональный язык общения". Такая ситуация объясняется многими причинами. В частности, только MFC позволяет создавать наиболее эффективные и устойчивые приложения, которые будут корректно вести себя не только в системе разработчика, но и в системах реальных пользователей. Также очень важно, что MFC поддерживает все современные технологии, реализованные в Windows, и при дополнении Windows почти сразу же дополняется и MFC.

MFC - это инструмент для программирования сложных приложений, от которых требуется высокая эффективность и надежность. MFC поощряет использование объектно-ориентированного программирования, что дает ощутимые преимущества при решении сложных (не с точки зрения только интерфейса пользователя) задач, по сравнению с компонентно-ориентированным подходом, применяемым в системах RAD (быстрой разработки приложений). Разрабатывая приложение в системе RAD, программист часто вообще не использует ООП, по крайней мере в явном виде, до тех пор, пока не соберется разработать собственный компонент. Это негативно сказывается на возможности последующего расширения возможностей.

5.2 Реализация алгоритма Прима построения минимального остовного дерева

Для реализации алгоритма Прима построения минимального остовного дерева, был разработан класс CMSTree.

Основной функцией данного класса, которая выполняет построение дерева МОД является:

void FindMST(int st[],double wt[]).

По причине особой важности ниже приведён код данной функции:

{

int v,w,min;

int *fr = new int[Vertexs+1];

for (v=0;v<Vertexs;v++)

{st[v]=-1;fr[v]=v;wt[v]=maxWT;}

st[0] = 0; wt[Vertexs] = maxWT;

for (min =0; min != Vertexs;)

{

v = min; st[min] = fr[min];

for (w=0, min = Vertexs; w < Vertexs;w++)

if (st[w] == -1)

{

if (PMST < wt[w])

{wt[w] = PMST; fr[w] = v;}

if (wt[w] < wt[min]) min = w;

}

}

delete[] fr;

return;

}

При реализации данной функции использовались следующие структуры данных:

1) Массив st содержит информацию для каждой вершины дерева - её предка в дереве МОД;

2) Массив fr содержит информацию для каждой вершины вне дерева - ближайшую вершину дерева;

3) Массив wt содержит информацию для каждой вершины дерева - длину её родительской связи и для каждой вершины вне дерева - её расстояние до дерева.

Для древесной вершины v элемент wt[v] содержит длину родительской связи (в соответствии с st[v]), а для недревесной вершины w элемент wt[w] содержит расстояние до дерева (в соответсвии с fr[w]).

Данной реализации отдаётся предпочтение при работе с насыщенными графами. Внешний цикл обеспечивает приращение дерева МОД посредством выбора минимального ребра, пересекающего сечение между вершинами, содержащимися в дереве МОД, и вершинами, не входящими в это дерево. Цикл по w отыскивает минимальное ребро и в то же время (если w не содержится в МОД) сохраняет неизменным условие, согласно которому ребро из w в fr[w] является самым коротким (с весом wt[w]) ребром, ведущим из w в МОД.

Переменная PMST является указателем на ребро из матрицы смежности и определена как:

#define PMST adj[v][w].

Сигнальное значение maxWT обозначает отсутствие ребра. Результат выполнения функции для графа изображенного на рисунке 3.3 будет следующий:

Таблица 4.1

	0	1	2	3	4	5	6	7
st	0	7	0	4	7	3	7	0
wt	0	0.21	0.29	0.34	0.46	0.18	0.25	0.31

Таким образом в дерево МОД вошли ребра: 1-7, 2-0, 3-4, 4-7, 5-3, 6-7, 7-0. Блок-схема алгоритма Прима приведена в приложении А.

Для того чтобы выполнить расчёт дерева МОД нужно создать объект класса CMSTree и вызвать функцию ExeMST имеющую следующий формат:

- bool ExeMST(CBoard *brd).

В качестве параметра brd в функцию передаётся указатель на класс схемы графа CBoard о котором будет рассказано ниже. При выполнении данная функция производит инициализацию матрицы смежности (указатель adj) и заполнение матрицы информацией о ребрах графа, с одновременной проверкой весов ребер (вес ребра должен находиться в диапазоне от 0 до 1). После этого если все рёбра имеют правильный вес функция запускает расчёт дерева МОД при помощи вышеописанной функции FindMST. Если вес хоть одного ребра не лежит в диапазоне от 0 до 1, то функция прекращает своё выполнение и возвращаёт значение false.

Инициализация матрицы смежности производится функцией void Init(int V), входным параметром которой является число вершин в графе.

Для того чтобы занести информацию о ребре в матрицу смежности используется функция void InsertEdge(edge e), параметр e которой является структурой следующего формата:

struct tagEdge

{

int v,w; ? информация о вершинах соединяемые ребром;

double wt; ? вес ребра;

};

Найденной дерево МОД можно обратно преобразовать в схему графа (класс CBoard), функцией void MSTToBoard(CBoard *brd), параметр brd указывает на пустую схему графа.

При помощи функции CString DoReport() можно получит отчёт о построенном дереве МОД в формате (rich text format - RTF).

Для инициализации матрицы смежности используется функция:

- double **MATRIXdouble(int c,int r,double val) - c - число строк, r - число столбцов, val - заполнитель, а для освобождения выделенной памяти применяется функция:

- void MATRIXfree(int V,double **data) - V - размерность матрицы, data - указатель на саму матрицу.

Число вершин и число ребер в матрице содержится в переменных Vertexs и Edges соответсвенно.

Порядок действий при использовании класса CMSTree:

- Вызвать конструктор класса CMSTree;

- Вызвать функцию ExeMST, в которой в качестве параметра передать указатель на класс CBoard;

- Вызвать функцию MSTToBoard, где параметром также является указатель на класс CBoard;

- Если требуется создать отчёт то нужно вызвать функцию DoReport.

4.3 Реализация алгоритма Дейкстры для поиска кратчайших путей

Для реализации алгоритма Дейкстры нахождения кратчайших путей от одного источника был разработан класс CSPTree.

Основной функцией данного класса непосредственно реализующей алгоритм Дейкстры является:

- void FindSPT(int s, int st[], double wt[]).

Ниже приводится её код:

{

link t; int v,w;

pq = new CPQ;

pq->Init(Vertexs);

pq->SetPriority(wt);

for (v=0; v < Vertexs; v++)

{

st[v]=-1;

wt[v]=maxWT;

pq->Insert(v);

}

wt[s] = 0.0; pq->Dec(s);

while (!pq->Empty())

if (wt[v = pq->Delmin()] != maxWT)

for (t = adj[v]; t != NULL; t = t->next)

if (PSPT < wt[w = t->v])

{ wt[w] = PSPT; pq->Dec(w);st[w] = v;}

delete pq;

}

Данная реализация алгоритма для вычисления ДКП использует очередь с приоритетами вершин (в порядке их расстояния от источника). В начале очередь заполняется приоритетом 0 для источника и приоритетами maxWT для других вершин, и затем выполняется цикл, в котором вершина с наименьшим приоритетом перемещается из очереди в ДКП, и выполняется ослабление по всем инцидентным ей ребрам.

Результатом выполнения функции будет дерево ДКП, так для рисунка 3.7 содержимое массивов будет следующим:

Таблица 4.2

	0	1	2	3	4	5
st	0	0	4	4	5	0
wt	0	0.41	0.32	0.36	0.21	0.29

Блок-схема алгоритма Дейкстры приведена в приложении А.

Очередь с приоритетами реализована в виде отдельного класса CPQ детальное описание, которого будет рассмотрено ниже.

Функция void Init(int V) производит первоначальную инициализацию переменных класса, в качестве параметра она принимает число вершин в исходном графе.

Функция void InsertEdge(edge e) вставляет новое ребро в граф, в качестве параметра e используется структура tagEdge которая была рассмотрена в предыдущей главе.

Когда происходит вызов функции InsertEdge, она в свою очередь вызывает функцию link CreateLink(int v,link next,double wt) имеющая следующие параметры:

1) v - вершина графа,

2) next - указатель структуру node имеющую следующий формат:

struct node

{

int v; ? вершина графа;

double wt; ? вес ребра;

link next; ? указатель на следующую структуру node;

};

3) wt - вес создаваемого ребра.

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

Функция void Reverse(CSPTree* rspt), параметром которой является указатель на класс CSPTree, используется для обращения графа (создаётся новый граф с теми же вершинами и ребрами, но с обращенными направлениями рёбер).

Функции int GetVertexCount() и int GetEdgeCount() возвращают количество вершин и рёбер в графе соответственно.

Функция void FreeMem() используется для освобождения памяти занимаемой классом CSPTree.

Порядок действий при использовании класса CSPTree:

- Вызвать конструктор класса CSPTree;

- Вызвать функцию Init в которой указать максимальное количество вершин в графе;

- Добавить ребра функцией InsertEdge;

- Вызвать функцию FindSPT, в которой указать источник и указатели на массивы, размерность которых должна быть на 1 больше максимального количества вершин.

4.4 Реализация класса CAllSPath для поиска всех кратчайших путей

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

Данный класс разработан специально для использования совместно с классом CBoard.

Инициализация обьекта класса производиться функцией:

- bool Init(CBoard *board) - в случае когда производиться работа с графом и

bool InitNet(CBoard *board,CPtrArray *links,int maxWeight) - в случае когда производится эмуляция работы сети передачи данных.

Также в данном классе используются следующие функции:

- double GetPathWeight(CVertex* sv,CVertex *dv) - возвращает вес пути между заданными вершинами sv и dv (описание класса CVertex) будет приведено ниже;

- int GetNextVertex(int first,int last) - возвращает индекс следующей вершины на пути;

- void HighlitePath(CVertex* sv,CVertex *dv) - выделяет на текущей схеме хранимой в переменной pBoard путь от вершины sv до dv;

- void UnHighLiteOldPath() - убирает ранее выбранный путь;

- CString DoReport() - возвращает информацию о текущем пути в формате RTF.

Внутренние функции класса:

- void spAll() - непосредственно реализует поиск всех кратчайших используя ранее описанный класс CSPTree для нахождения всех кратчайших путей;

- double spDist(int s,int t) - возвращает вес пути, определяемый вершинами s и t;

- int spPath(int s,int t) - возвращает следующую вершину на пути определяемом вершинами s и t;

- double** MATRIXdouble(int r,int c, double val) и int** MATRIXint(int r,int c, int val) - возвращают указатель на двумерный массив размером r на с заполненный val;

- void MATRIXfree(int V,double **data) и void MATRIXfree(int V,int **data) -освобождают память, выделенную вышеописанными функциями.

Основные используемые переменные:

- norm и reversed указатели на класс CSPTree используемые при нахождении всех кратчайших путей;

- double **dist указатель на двумерный массив в котором хранится информация о весах пути.

- int **path указатель на двумерный массив в котором хранится информация о всех кратчайших путях.

Порядок действий при использовании класса CAllSPath

- Вызвать конструктор класса CAllSPath.

- Вызвать функцию Init, которой передать указатель на CBoard.

- Выделить путь при помощи HighlitePath, вызывать UnHighLiteOldPath не обязательно.

- Получить информацию о пути выделенном HighlitePath, функцией DoReport.

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

int s,t,olds;

while(true)

{

olds = s;

s = GetNextVertex(s,t);

if (s == t)

{

достигнута конечная вершина t; break;

}

else

{

if (s != maxWT)

{промежуточное ребро на пути от s к t лежит между вершинами olds и s;}

else произошла ошибка.

}

- Для того чтобы получить вес пути от s к t нужно воспользоваться функцией GetPathWeight.

4.5 Реализация класса очереди с приоритетом CPQ

Класс CPQ реализует функции очереди с приоритетом и используется совместно с классом CSPTree.

Основные объекты используемые в данном классе:

- pq и qp - массивы целочисленных значений, используемые непосредственно для организации очереди;

- mxPQ - переменная содержит максимальное количество элементов в очереди;

- priority - указатель на массив приоритетов;

- N - содержит текущее количество элементов в очереди.

Следующие функции доступны программисту:

- void Init(int maxPQ) - производит инициализацию объектов класса, значению mxPQ присваивается maxPQ;

- int Empty() - проверка на то, что очередь пуста;

- void Insert(int) - вставляет новый элемент в очередь;

- Item Delmin() - возвращает и удаляет элемент из очереди, имеющий минимальный приоритет;

- void Dec(int k) - изменяет приоритет элемента k;

- void SetPriority(double *pr) - присваивает указателю priority значение pr.

Порядок действий при использовании класса CPQ:

- Вызвать конструктор класса CPQ;

- Вызвать функцию Init;

- Установить указатель на массив приоритетов функцией SetPriority;

- Добавить элементы при помощи функции Insert;

- Дальше можно использовать функции Delmin, Dec и Empty.

5 .Разработка контрольного примера

5.1 Использование программы для нахождения минимального остовного дерева

На рисунке 6.1 изображен граф, минимальное остовное дерево (МОД), которого нам нужно найти с помощью разработанного программного комплекса. МОД данного графа изображено на рисунке 6.2, в него вошли следующие рёбра:

1) 0 - 1 - вес равен 0,368;

2) 0 - 3 - вес равен 0,254;

3) 1 - 5 - вес равен 0,32;

4) 5 - 2 - вес равен 0,25;

5) 5 - 7 - вес равен 0,16;

6) 7 - 4 - вес равен 0,35;

7) 7 - 6 - вес равен 0,49;

8) 6 - 8 - вес равен 0,61.

Аналогичный результат должна показать программа.

На рисунке 6.3 изображена панель инструментов программы. Кнопки имеют следующие значения, по порядку:

1) Создать новую схему - показывает диалог создания новой схемы;

2) Сохранить схему - сохраняет текущую схему в файл;

3) Открыть схему - открывает схему ранее записанную на диск;

4) Окно свойств - показывает окно свойств элемента схемы;

5) Список элементов - показывает список элементов текущей схемы;

6) Инструмент указатель - выбирает текущий элемент инструмент указатель, который используется для выделения элементов на схеме;

7) Инструмент перемещения - используется для перемещения элементов и их названия по схеме;

8) Создать вершину - используется для создания вершин на схеме в режиме построения графа;

9) Создать ребро - используется для создания рёбер на схеме в режиме построения графа или канала связи в режиме построения схемы сети;

10) Создать маршрутизатор - используется для создания маршрутизатора на схеме в режиме построения схемы сети;

11) Создать сеть - используется для создания сети на схеме в режиме построения схемы сети;

12) Построить минимальное остовное дерево - строит МОД текущего графа;

13) Режим поиска кратчайших путей - при нажатие переводит текущую схему графа в режим поиска кратчайших путей, при повторном нажатии переводит схему в режим построения графа;

14) Запустить процесс эмуляции - запускает на текущей схеме сети процесс эмуляции работы маршрутизаторов по протоколу OSPF;

15) Остановить процесс эмуляции - останавливает на текущей схеме сети процесс эмуляции работы маршрутизаторов по протоколу OSPF.

Теперь опишем процесс нахождения МОД по шагам:

Шаг 1. Нажать на кнопку “Создать новую схему”, появится диалог изображённый на рисунке 6.4. В нем нужно выбрать “создать схему графа”, установить высоту и ширину новой схемы и нажать кнопку “OK”.

Рисунок 6.1



Рисунок 6.2

Рисунок 6.3

Рисунок 6.4

Рисунок 6.5

Шаг 2. На экране появится окно изображенное на рисунке 6.5. Это базовое окно на котором производится построение схемы графа. Также в качестве инструмента по умолчанию выбирается “инструмент указатель”. Начнём построение графа с размещения вершин на схеме, для этого нажимаем на кнопке “создать вершину”. Далее в месте будущего положения вершины нужно нажать левой кнопкой мыши. Для того чтобы удалить вершину нужно на ней нажать правой клавишей мыши и во всплывающем меню выбрать “удалить”.

Шаг 3. Для того чтобы изменить название вершины нужно сначала открыть окно свойств элемента схемы (кнопка “окно свойств”), появится окно изображённое на рисунке 6.6. Далее выбрав инструмент “инструмент указатель” щелкнуть левой кнопкой мыши на вершине (в панели свойств появятся свойства вершины), затем в поле “название” дважды щелкнуть левой клавишей мыши, появится диалог ввода названия вершины (рисунок 6.7), в котором нужно ввести новое имя и нажать кнопку “OK”. Существует второй способ изменения названия вершины, он заключается в том что, выбрав инструмент “инструмент указатель” дважды нажать левой кнопкой мыши на вершине, тогда сразу появится диалог изображённый на рисунке 6.7.

Рисунок 6.6

Шаг 4. Разместим девять вершин как показано на рисунке 6.8 и перейдем к построению рёбер графа. Ребра создаются при помощи инструмента “создать ребро”. Для того чтобы создать ребро между двумя вершинами нужно нажать левой кнопкой мыши на одной вершине, переместить мышь (удерживая левую кнопку нажатой) на другую вершину и опустить левую кнопку мыши. Изменение веса и названия ребра производится аналогично изменению названия вершины описанной в шаге 3. Вес ребра должен лежать в диапазоне от 0 до 1. Удалить ребро можно также как и вершину.

Рисунок 6.7

Рисунок 6.8

Рисунок 6.9

Шаг 5. Создадим ребра с весами как показано на рисунке 6.1, и сохраним схему в файл нажав на кнопу “сохранить схему”, появится диалог в котором потребуется ввести имя файла (в нашем примере схема сохраняется под именем “graf.brd”). Результат построения графа приведён на рисунке 6.9.

Шаг 6. Для того чтобы построить МОД построенного графа нужно нажать на кнопку “построить минимальное остовное дерево”, при этом высветиться запрос о создании отчёта, нажмём на кнопку “OK”. Построенное МОД изображено на рисунке 6.10, на рисунке 6.11 приведён отчет который выдала программа, отчет также можно сохранить в файл, выделив окно отчёта и нажав “Файл - Сохранить отчёт”. Отчёт сохраняется в формате RTF пригодный для просмотра в программе Microsoft Word.

Сравнивая рисунки 6.2 и 6.10 видно, что построенные МОД одинаковы, что доказывает пригодность программы для нахождения минимального остовного дерева.

Рисунок 6.10

6.2 Использование программы для поиска кратчайших путей

Для демонстрации возможностей программы при поиске кратчайших путей воспользуемся графом, построенным в предыдущем разделе (рисунок 6.1). Для того чтобы открыть ранее сохраненную схему нужно нажать на кнопку “открыть схему”, и в появившемся диалоге выбрать или ввести имя файла схемы графа. Схемы графа сохраняются в файл с разрешением “brd”.

Рисунок 6.11

Найдем кратчайший путь из вершины 0 в вершину 8, этот путь будет проходить через следующие рёбра:

1) 0 - 1 - вес ребра 0.368;

2) 1 - 5 - вес ребра 0.32;

3) 5 - 7 - вес ребра 0.16;

4) 7 - 8 - вес ребра 0.82;

Таким образом путь из из вершины 0 в вершину 8 содержит 4 ребра и имеет суммарный вес равный:

0.368+0.32+0.16+0.82=1.668

Остальные пути имеют больший вес.

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

Чтобы найти кратчайший путь, например, между вершинами 0 и 8 нужно сначала нажать левой клавишей мыши на вершине 0, а затем на вершине 8. В результате будет построен кратчайший путь 0-1-5-7-8, как показано на рисунке 6.12, а в окне отчёта появится текст, отображающий список рёбер вошедших в этот путь (рисунок 6.13).

Рисунок 6.12

6.3 Использование программы для эмуляции работы маршрутизаторов по протоколу OSPF

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

Рисунок 6.13

Так как все маршрутизаторы работают, используя протокол OSPF, то стоимость передачи по каналу связи определяться по формуле:

Сеть с рассчитанной стоимостью каналов связи приведена на рисунке 6.16.

Построим таблицу маршрутизации для маршрутизатора R1. Протокол OSPF для построения таблиц маршрутизации использует алгоритм поиска кратчайших путей, причем оптимальным считается путь, имеющий минимальную стоимость. Например, кратчайший путь от маршрутизатора R1 до сети N5 будет пролегать следующим образом:

Таким образом в таблице маршрутизации R1, запишется строчка вида - О сеть N5 [IP 201.125.100.0 маска 255.255.255.0] через 194.100.108.2 стоимость 29

Таблица 6.1

Направление передачи данных	Интерфейс, через который передаются данные	Стоимость канала связи	Суммарная стоимость пути
R1 R3	194.100.108.2	12	12
R3 R4	194.100.104.2	4	16
R4 R5	194.100.103.1	10	26
R5 N5	201.125.100.1	1	27

Впереди буква “O” ставится, если информация о сети получена используя протокол OSPF, если сеть непосредственно подключена к маршрутизатору, то ставиться буква “C”.

Ниже приведена полная таблица маршрутизации R1.

Таблица 6.2

С сеть N1 [IP 155.201.0.0 маска 255.255.0.0] через 155.201.0.1 стоимость 1
O сеть N2 [IP 201.126.102.0 маска 255.255.255.0] через 194.100.106.2 стоимость 11
O сеть N3 [IP 201.126.101.0 маска 255.255.255.0] через 194.100.108.2 стоимость 13
O сеть N4 [IP 154.191.0.0 маска 255.255.0.0] через 194.100.108.2 стоимость 17
О сеть N5 [IP 201.125.100.0 маска 255.255.255.0] через 194.100.108.2 стоимость 27
O сеть N6 [IP 201.125.101.0 маска 255.255.255.0] через 194.100.108.2 стоимость 21

Опишем процесс построения схемы сети передачи данных и построение таблиц маршрутизации:

Шаг 1. Нажать на кнопку “Создать новую схему”, появится диалог изображённый на рисунке 6.4. В нем нужно выбрать “создать схему сети”, установить высоту и ширину новой схемы и нажать кнопку “OK”.

Шаг 2. На экране появится окно изображенное на рисунке 6.17. Это базовое окно на котором производится построение схемы графа. Также в качестве инструмента по умолчанию выбирается “инструмент указатель”. Размещение на схеме маршрутизаторов, сетей и каналов, а также изменение их свойств производится также как и при работе со схемой графа. Построим схему сети изображенную на рисунке 6.14.

Шаг 3. Для того чтобы приступить к эмуляции нужно задать IP адрес и маску сети, IP адреса интерфейсов маршрутизаторов и пропускную способность каналов связи. IP адрес и маска сети задаются следующим образом: выбрав инструмент “инструмент указатель” на схеме сети выделяется сеть, тогда в окне свойств появятся свойства сети. Изменение производится двойным нажатием левой кнопкой мыши на соответствующем свойстве (рисунок 6.18). Чтобы изменить IP адреса интерфейсов маршрутизатора и пропускную способность канала связи нужно выделить канал и в окне свойств задать требуемые значения (рисунок 6.19). Схема сети приведена на рисунке 6.20.

Рисунок 6.14

Шаг 4. После построения схемы сети и задания всех параметров можно приступить к эмуляции работы маршрутизаторов по протоку OSPF, для этого нужно нажать на кнопку “запустить процесс эмуляции”. В режиме эмуляции доступны такие пункты всплывающего меню как “таблица маршрутизации” и “консоль”.



Рисунок 6.15

Шаг 5. Чтобы просмотреть таблицу маршрутизации маршрутизатора нужно на нём нажать правой клавишей мыши и выбрать пункт меню “таблица маршрутизации”. На рисунке 6.21 изображена таблица маршрутизации маршрутизатора 1, она полностью совпадает с приведённой выше.

Шаг 6. При выборе во всплывающем меню пункта “консоль” открывается окно в котором выводится более подробная информация о маршрутизаторе, а также в нём возможен ввод команд, тем самым эмулируется консоль маршрутизатора. Доступны следующие команды:

- “show ip route” - выводит в консоль таблицу маршрутизации;

- “show configuration” - выводит текущую конфигурацию маршрутизатора;



Рисунок 6.16

Рисунок 6.17

Рисунок 6.18



Рисунок 6.19

Рисунок 6.20

Рисунок 6.21

- “trace IP адрес сети” - выводит информацию о пути, проходящий от маршрутизатора которому принадлежит консоль до сети заданной IP адресом.

На рисунке 6.22 изображена консоль с выполненной командой “show configuration”.

Шаг 7. Чтобы остановить эмуляцию и перейти в режим редактирования схемы сети нужно нажать кнопку “остановить процесс эмуляции”.

Рисунок 6.22

7. Расчет надёжности программного продукта

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

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

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

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

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

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

Функция надёжности есть вероятность того, что случайная наработка до отказа будет больше заданной наработки отсчитываемой с момента последнего (m-1)-го отказа. Функция надёжности программы определяется в зависимости от числа возникших отказов:

, (8.1)

где Ф(x) - функция Лапласа, функция табулирована, причем Ф(-x)=- Ф(x).

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

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

, (8.2)

где случайные величины независимы и имеют одинаковые математические ожидания и средние квадратичные отклонения . Из формулы (8.2) следует, что m-й отказ программы произойдёт через время:

Также предполагается, что:

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

При таком предположении, средняя наработка между (m-1)-м и m-м отказами программы будет равна:

Средняя наработка до возникновения m-го отказа определяется выражением:

Во время тестирования и отладки, программа прошла тестирование в течении 100 часов. За этот период было зафиксировано пять отказов, . Время возникновения отказов представлено в таблице 7.1. Интервалы между отказами представлены в таблице 7.2.

Таблица 7.1 - Время возникновения отказов

Время возникновения отказов , i = 0,1,2,3,4,5
Время возникновения отказов, ч.	0	0,2	2	10	40	100

Таблица 7.2 - Интервалы между отказами

Интервалы между отказами, I=1,2,3,4,5
Интервалы между отказами, ч	0,2	1,8	8	30	60

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

1) ,(часов);

2) , ,

где - число отказов программы за период;

-момент возникновения i-го отказа программы.

;

По формуле (8.1) находим:

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

Заключение

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

- Визуально проектировать схему графа и автоматически строить минимальное остовное дерево данного графа;

- Находить между двумя вершинами графа кратчайший путь с выводом на экран свойств рёбер входящих в этот путь;

- Строить сеть передачи данных и производить эмуляцию работы маршрутизаторов, входящих в эту сеть, используя протокол маршрутизации OSPF.

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

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

Размещено на Allbest.ru