Размещено на http://www.allbest.ru/

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

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

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

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

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

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

Выполнила:

студент:

Носаченко Антон

Проверил:

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

Самара 2014



Содержание

• Техническое задание
• Введение
• 1. Алгоритм Дейкстры
• 1.1 Алгоритм, реализованный в программе
• 2. Определение степени сети и узлов
• 2.1 Реализация определения степени сети и узлов
• 3. Определение диаметра сети
• 3.1 Реализация определения диаметра сети
• 4. Маршрутизация
• 5. IP адрес
• 5.1 Класс сети
• 5.2 Маска сети
• 5.3 Номер сети
• 5.4 Номер узла
• 5.5 Широковещательный адрес
• 5.6 Диапазон адресов
• 6. Подсети
• Заключение
• Список использованных источников


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

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.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. Среднее расстояние между узлами. Минимальное число связей, которое необходимо преодолеть, чтобы попасть из узла в узел, называется расстоянием между узлами. Усредненное расстояние между всеми парами узлов сети, для которых существует путь перехода из одного в другой, называется средним расстоянием между узлами .

2.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. Определение диаметра сети

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) - графические представления, основанные на этом подходе.

В блоке Chart находятся маршрутизаторы которые раз в 30 секунд обмениваются таблицами маршрутизации.

Функция для реализации и выходные таблицы маршрутизации для каждого из узлов находятся в приложении B.

Рассмотрим один из таких автоматов подробнее (рис. 2).

Рисунок 2 - Конечный автомат для узла A.

Выходные таблицы маршрутизации для каждого из узлов представлены в таблице 4.



Таблица 4 - Выходные таблицы маршрутизации

Для узла А. № узла Запаздывание Отправка через соседей 1A 0 0 2B 27 5 3C 48 5 4D 50 5 5E 8 - 6F 20 5 7G 13 - 8H 45 5 9I 22 5 10J 8 -	Для узла В № узла Запаздывание Отправка через соседей 1A 27 5 2B 0 0 3C 69 5 4D 71 5 5E 19 - 6F 27 - 7G 40 5 8H 66 5 9I 43 5 10J 35 5
Для узла С № узла Запаздывание Отправка через соседей 1A 48 9 2B 69 9 3C 0 0 4D 54 9 5E 50 9 6F 62 9 7G 35 9 8H 49 9 9I 26 - 10J 56 9	Для узла D № узла Запаздывание Отправка через соседей 1A 50 8 2B 71 8 3C 54 8 4D 0 0 5E 52 8 6F 64 8 7G 37 8 8H 5 - 9I 28 8 10J 58 8
Для узла E № узла Запаздывание Отправка через соседей 1A 8 - 2B 19 - 3C 50 9 4D 52 9 5E 0 0 6F 12 - 7G 21 1 8H 47 9 9I 24 - 10J 16 1	Для узла F № узла Запаздывание Отправка через соседей 1A 20 5 2B 27 5 3C 62 5 4D 64 5 5E 12 - 6F 0 0 7G 33 - 8H 59 5 9I 36 5 10J 28 5
Для узла G № узла Запаздывание Отправка через соседей 1A 13 - 2B 40 1 3C 35 9 4D 37 9 5E 21 1 6F 33 1 7G 0 0 8H 32 9 9I 9 - 10J 21 1	Для узла H № узла Запаздывание Отправка через соседей 1A 45 9 2B 66 9 3C 49 9 4D 5 9 5E 47 9 6F 59 9 7G 32 9 8H 0 0 9I 23 - 10J 53 9
Для узла I № узла Запаздывание Отправка через соседей 1A 22 5 2B 43 5 3C 26 - 4D 28 8 5E 24 - 6F 36 5 7G 9 - 8H 23 - 9I 0 0 10J 30 5	Для узла J № узла Запаздывание Отправка через соседей 1A 8 - 2B 35 1 3C 56 1 4D 58 1 5E 16 1 6F 28 1 7G 21 1 8H 53 1 9I 30 1 10J 0 0



5. IP адрес

Адресация IP.

Особенностью IP является гибкая система адресации. Плата за это -- наличие централизованных служб типа DNS.

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

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

Одним из подходов был классовый метод адресации. Нетрудно посчитать, что всего в пространстве адресов IP -- 128 сетей по 16?777?216 адресов класса A, 16384 сети по 65536 адресов класса B и 2?097?152 сети по 256 адресов класса C, а также 268?435?456 адресов многоадресной рассылки и 268?435?456 зарезервированных адресов. С ростом сети Интернет эта система оказалась неэффективной и была дополнена бесклассовой адресацией (CIDR).

По заданию нам дан IP адрес одного из конечных узлов сети 187.2.201.134

5.1 Класс сети

Существуют 5 классов IP адресов, отличающиеся количеством бит в сетевом номере и хост - номере. Классы IP адресов представлены в таблице 5.

Таблица 5 - Классы IP адресов

Класс	Перве биты	Дифпозон адресов	Количество узлов
А	0	1.0.0.0...126.0.0.0	16777216(2^24)
В	10	128.0.0.0...191.255.0.0	65536(2^16)
С	110	192.0.1.0...223.255.225.0	256(2^8)
D	1110	224.0.0.0...239.255.255.255	Multicast
E	11110	240.0.0.0...247.255.255.255	Зарезервирован

Класс заданного IP адреса - B.

5.2 Маска сети

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

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

Для стандартных классов сетей маски имеют следующие значения:

255.0.0.0 - маска для сети класса А;

255.255.0.0 - маска для сети класса B;

255.255.255.0 - маска для сети класса C.

Так как класс заданного IP адреса В, то его маска - 255.255.0.0.

5.3 Номер сети

Номер сети( сколько в маске не 0 сетей): 187.2.0.0



5.4 Номер узла

Номер узла(все остальные): 0.0.201.134

5.5 Широковещательный адрес

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

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

Широковещательный адрес: 187.2.255.255

5.6 Диапазон адресов

Число возможных адресов сети: 16 386



6. Подсети

По заданию у нас имеются 2 подсети - 9 8 1 и 2 7 5 6, каждая из которых содержит несколько маршрутизаторов. Для первой подсети, исходя из того условия, что может быть добавлено 3 узла, мы можем узнать максимальное количество возможных вложенных подсетей следующим образом: 9+27+6+3+3=48. Данные о числе подключенных к маршрутизаторам конечных узлов для этого расчёта мы брали в таблице 2.

Теперь мы можем определить значение N, то есть количество нулей в маске: отсюда N=6 - количество нулей в маске.

Отсюда маска подсети: 11111111.11111111.11111111.11000000 или 255.255.255.192

Все полученные данные об этой подсети внесли в таблицу 6.

Таблица 6 - Все данные о первой подсети

Маска	255.255.255.192
Ncети=IP and M	Nсети=187.2.201.128
IPш=IP or notM	IPш=187.2.201.191
IPmin=Nсети+1	IPmin=140.46.22.129
IPmax=IPш-1	IPmax=187.2.201.190

Теперь приступим к анализу второй подсети.

По условию обеспечения не менее 2 дополнительными сетями при максимальном количестве узлов в подсетях мы получим следующее выражение: 2+2=4, , следовательно N=2.

Отсюда маска подсети: 11111111.11111111.11000000.00000000 или 255.255.192.0



Таблица 7 - Все данные о второй подсети

Маска	255.255.192.0
Ncети=IP and M	Nсети=187.2.192.0
IPш=IP or notM	IPш=187.2.255.255
IPmin=Nсети+1	IPmin=187.2.192.1.
IPmax=IPш-1	IPmax=187.2.255.254



Заключение

Теоретически сетевые адреса администратор может выделять по своему выбору. К несчастью, только теоретически - на практике адресное пространство IP жестко распределяются. Это связано с использованием Internet. Для того, чтобы можно было связать частную сеть с Internet большинство организаций использует адреса, выделенные IAN (Internet Number Authority) или соответствующей национальной организацией. Быстрый рост Internet привел к тому, что адресное пространство IP уже почти полностью распределено. Маршрутизаторы не помогают решить проблему нехватки сетевых номеров, поскольку каждый порт маршрутизатора в общем случае имеет свою собственную подсеть.



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

1. CITForum [Электронный ресурс] = Некоторые секреты IP-протокола/ Бред Тёрнер - Журнал "Сети" № 03, 2000 - Режим доступа: http://citforum.ru/nets/tcp/ip_secr.shtml, свободный. - Загл. с экрана

2. Информационные сети и телекоммуникации [Конспект лекций]

3. CITForum [Электронный ресурс] = Введение в IP-сети/ Виктор и Наталья Олифер - Информационно-аналитические материалы, 2004 - Режим доступа: http://citforum.ru/nets/ip/contents.shtml, свободный. - Загл. с экрана

4. Компьютерные сети. Принципы, технологии, протоколы: учеб. Пособие для студентов вузов/ Олифер В. Г., Олифер Н. А. - 3-е изд. - Спб.: Питер, 2006. - 958 с.

5. Современные компьютерные сети. 2-е изд./ В.Столлингс. - Спб.: Питер, 2003. - 783с.

6. Основы маршрутизации в телекоммуникационных сетях : Учеб. пособие / Д.В. Куракин; Моск. гос. ин-т радиотехники, электрон. и автоматики (Техн. ун-т). - М. : [б. и.], 2000. - 68 с.

7. Справочник по применению системы PC MatLAB / В.П. Дьяконов. - М. : Физ.-мат. лит., 1993. - 111 с.

8. Matlab 6/6.1/6.5 + Simulink 4/5. Основы применения / В.П. Дьяконов. - М. : Солон-Пресс, 2002. - 767 с.

9. Simulink : среда создания инженер. прил. / И. В. Черных ; Под общ. ред. В. Г. Потемкина. - М. : Диалог-МИФИ, 2004. - 491 с. : ил. ; 20 см. - Предм. указ.: с. 482-485. - Библиогр.: с. 486-487.

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