Курсовая работа по «Информационным сетям и телекоммуникациям»

Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Самарский государственный технический университет»

 

Факультет автоматики информационных технологий

Кафедра «Автоматика и управление в технических системах»

 

 

 

 

Курсовая работа

По дисциплине «Информационные сети и телекоммуникации лекции»

Вариант 36

 

 

 

 

 

 

Выполнила: студентка:

3-АИТ-1 Носаченко Антон

Проверил:

Левин Илья Сергеевич

 

 

                                                               

Самара 2014

 

Содержание

 

 

 

 

 

 

 

Техническое задание

1. Определить наикратчайшие пути от узла B ко всем остальным узлам сети по алгоритму Дейкстры. Алгоритм реализовать в виде программы, считывающей матрицу всех связей в сети, и в качестве результата выдающей наикратчайший путь (описываемый как последовательность узлов, через которые он проходит) и его совокупный вес до произвольных узлов A, I, J. Структура матрицы представлена в таблице 1.

Таблица 1 - Структура матрицы А

2. Определить степень сети и всех её узлов. Структуру сети брать из задания 1. Алгоритм определения степеней сети и узлов реализовать в виде программы.

3. Определить диаметр сети из задания 1. Для узлов B и F определить связанность по связям и узлам.

4. Реализовать в виде программы алгоритм маршрутизации по вектору состояний (RIP). Маршрутизаторы раз в 30 сек. должны обмениваться таблицами маршрутизации. В качестве единицы измерения принять время задержки. Исходное время задержек между маршрутизаторами и структуру сети взять из матрицы связей для задания 1. В ходе работы алгоритма реализовать произвольное изменение задержек в пределах ±5 единиц (изменение времени задержек производить после каждого обмена таблицами). Предусмотреть возможность проверки текущего состояния таблицы маршрутизации любого из маршрутизаторов, а также времени задержки между соседними маршрутизаторами. Длительность моделирования - 90 сек.

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

Таблица 2 – Маршрутизаторы и подключенные к нему узлы

Номер маршрутизатора	Число подключенных к нему конечных узлов
1	6
2	7
3	18
4	11
5	16
6	19
7	21
8	27
9	9
10	9

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

7. Исходный код всех реализованных программ представить в приложении к курсовой работе.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

История развития средств передачи информации на большое расстояние. 
Непосредственное общение людей друг с другом возможно лишь на небольшом расстоянии, поэтому на любом уровне развития общества существовали многообразные способы передачи данных на расстоянии. Это костры, морская флажковая азбука, семафоры на железных дорогах, азбука Морзе, телеграф, телефон, радио, телевидение, пейдженговая связь, факсимильная связь. Приставка теле- означает "дальний" или "удалённый" (телеграф = письмо на расстоянии, телефон = звук на расстоянии, телевидение = изображение на расстоянии). Одним из самых древних способов передачи информации является почта. Письма существуют столько же времени, сколько и письменность. Первоначально письма доставлялись специальными людьми - гонцами или животными (голубиная почта). При достаточном уровне развития общества формируется государственная система доставки писем - почта. Услугами почты могут пользоваться все, кто соблюдает правила: письмо должно содержать адрес человека, которому оно предназначено, и обратный адрес; письмо имеет конверт, на котором записывается дополнительная информация (номер почтового отделения, дата отправки и приёма, категория письма). Важное отличие писем от других способов передачи информации на расстоянии состоит в том, что получатель письма не обязательно должен присутствовать в тот момент, когда письмо доставляется по назначению. Письмо обычно сохраняется в почтовом ящике до тех пор, пока получатель не заберёт его от туда. Таким образом, письмо - это передача данных не только на расстоянии, но ещё и во времени.  Отметим характерные особенности любой передачи данных на большое расстояние:  на большое расстояние данные передаются по цепочке, через ряд промежуточных участников передачи (промежуточных станций, ретрансляторов и т.п.);  всякая такая передача должна быть подчинена чётким, заранее установленным правилам; должны быть заранее определены виды сигналов, смысл каждого из них, действия, которые надо совершать при успешном приёме сообщения или при необходимости повторной передачи.  
Передачи бывают двусторонними, либо односторонними; в последнем случае передача может быть широковещательной - адресованной сразу большому числу участников. Современную цивилизацию невозможно представить без таких способов передачи информации как телефон, телевидение, в которых используют для передачи информации электромагнитные колебания, т.е. радиоволны. Чем меньше длина волны (чем больше частота колебаний), тем большее количество информации можно передать в единицу времени, тем большего качества можно достичь при передачи. Это утверждение имеет точное математическое обоснование, и инженерам-практикам оно было известно с появлением радио. Высококачественная стереофоническая музыка может быть передана только на ультракоротких волнах. Передача изображения требует ещё более высоких частот, длины волн уже измеряются метрами и дециметрами. В проектах цифрового телевидения будущего в качестве несущей будет использоваться свет видимого диапазона, генерируемый микролазером. Средой передачи будет служить оптоволоконный кабель.

 

 

 

 

 

 

 

 

 

 

 

1. Алгоритм Дейкстры

Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS. Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены. Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые. Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.

 

1. Алгоритм, реализованный в программе

Проинициализируем переменные

n=size(A,1);

prev(1:n)=n+1;

dist(1:n)=inf;

visite(1:n)=false;

 

dist(3)=0;

Индекс начального узла

T=1;

Удалим столбец из таблицы

su=[];

 

 

while ~isempty(T)

    y=dist;

    h=true;

    while h

    [a k]=min(y);

        if visite(k)==true

            y(k)=inf;

            h=true;

        else

            h=false;

        end

    end

T(find(k==T))=[];

visite(k)=true;

m=A(k,:);

все соседи узла

ss=find(m);

s=min(find(m));

 

цикл по всем соседям

for i=1:length(ss)

вес связи от к до соседа

a=dist(k)+m(ss(i));

сравниваем дистанцию

if a<dist(ss(i))

    dist(ss(i))=a;

    prev(ss(i))=k;

    T=[T ss(i)];

end

end

end

prev %предыд вершина

dist %совокупный вес

Полный код программы представлен в приложении A.

Таким образом:

наикратчайший путь от узла B к узлу A

B→A (22)

наикратчайший путь от узла B к узлу I

B→A→J→I (51)

наикратчайший путь от узла B к узлу J

B→A→J (41)

 

 

 

 

 

 

 

 

 

 

2. Определение степени сети и узлов

Основные характеристики сложных сетей. Ориентированные и неориентированные сети. Каждый узел сети (node) может быть связан с другими узлами определенным числом связей (links). Связи между узлами могут иметь направление. В этом случае сеть называется ориентированной (directed network). Если связь симметрична для обеих связанных ею узлов, то образованная такими связями сеть называется неориентированной сетью (undirected network). Например, Веб это ориентированная сеть, а интернет это неориентированная сеть. Иногда вопрос об ориентированности сети не столь тривиален. Например, отношения между людьми. Если считать что связь существует, если две персоны являются близкими друзьями, то сеть будет неориентированной. Если считать что связь существует, если одна персона считает себя другом другой, то образованная сеть будет ориентированной. Распределение степеней узлов (Degree distribution of nodes) Число связей узла будем называть степенью (degree) узла. Для ориентированных сетей различают исходящую и входящую степени узла (out degree и in degree). Распределение степеней узлов является важной характеристикой сложной сети. Большинство сложных сетей имеют близкое к степенному закону распределение степеней узлов с показателем степени между 2 и 3. Среднее расстояние между узлами. Минимальное число связей, которое необходимо преодолеть, чтобы попасть из узла в узел, называется расстоянием между узлами. Усредненное расстояние между всеми парами узлов сети, для которых существует путь перехода из одного в другой, называется средним расстоянием между узлами  .Для большинства комплексных сетей  , где   — количество узлов в сети.

Степень узла – это количество связей, заканчивающихся на этом узле.

Степень сети – минимальная степень любого из её узлов.

 

1. Реализация определения степени сети и узлов

for i =1:10;

вывод всех не нулевых значений матрицы

neNul=find(A(i,:));

su(i)=length(neNul);

end

su

Результат работы программы представлен в таблице 3.

Таблица 3 – Результаты определения степени сети и всех узлов

№ узла	Степень узла
1A	5
2B	2
3C	2
4D	2
5E	2
6F	5
7G	4
8H	2
9I	2
10J	4

 

Степень сети=2

 

 

 

 

 

 

 

3. Определение диаметра сети

1. Реализация определения диаметра сети

Сеть представлена на рисунке 1. Линиями от узла к узлу обозначены связи между ними.

Геодезический путь – это путь между двумя узлами с наименьшим количеством связей.

Диаметр сети – величина самого длинного геодезического пути.

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

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

Рисунок 1 – Заданная сеть

Нам нужно найти диаметр сети, а для узлов B и F определить связанность по связям и узлам:

Dиаметр=4

Связанность по узлам между парой узлов B и F=2

 

Связанность по связям между B и F=2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. Маршрутизация

Чтобы реализовать в виде программы алгоритм маршрутизации по вектору состояний, воспользуемся графической средой имитационного моделирования Simulink. Программа Simulink является приложением к пакету MATLAB. При моделировании с использованием Simulink реализуется принцип визуального программирования, в соответствии с которым, пользователь на экране из библиотеки стандартных блоков создает модель устройства и осуществляет расчеты. При этом, в отличие от классических способов моделирования, пользователю не нужно досконально изучать язык программирования и численные методы математики, а достаточно общих знаний, требующихся при работе на компьютере и, естественно, знаний той предметной области, в которой он работает. Stateflow-Конечный автомат (finite state machine (FSM)) - вариант управляемой событиями (реактивной) системы. Управляемая событиями система переходит из одного состояния (режима) в другое предписанное состояние в том случае, если условие, определяющее изменение, истинно.

Например, можно использовать конечный автомат, чтобы описать автоматическую передачу автомобиля. Передача имеет ряд состояний: парковка, нейтраль, движение, реверс и т. д. Система переходит из одного состояния в другое, когда водитель перемещает рычаг из одной позиции в другую, например, из позиции парковка в нейтральное положение. Представления конечного автомата (FSM ). Традиционно проектировщики использовали таблицы истинности, чтобы представить отношения между вводами, выводами и состояниями FSM. Результирующая таблица описывает логику поведения системы. Другой подход к проектированию управляемых событиями систем состоит в том, чтобы моделировать поведение системы, описывая его в терминах переходов между состояниями. Переход состояния в активную фазу определяется наступлением событий при наличии некоторых условий. Диаграммы переходов (state-transition diagrams (STDs)) и пузырьковые диаграммы (bubble diagrams) - графические представления, основанные на этом подходе.