Алгоритм состояния связей

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

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

Рассмотрим применение алгоритма для вычисления таблицы маршрутизации для первого узла сети, граф которой представлен на рис. 1.

Рис. 1. Граф сети

Связи и расстояния между соседними узлами сети отражены в матрице расстояний L[i,j] между соседними узлами сети.

			-	-	-
			-		-
					-
-	-				-
-
-	-	-	-

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

Узел, соответствующий данному коммутатору, считается исходным. Алгоритм вычисляет маршруты от исходного узла до остальных за n-1 шагов (n – число узлов). На каждом шаге определяется кратчайшее расстояние до очередного узла.

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

Процесс нахождения кратчайших маршрутов между первым и другими узлами сети поясняет таблица 1. За первые два шага определяются расстояния до второго и третьего узлов, непосредственно подключенных к первому узлу. Расстояния до узлов определяем из первой строки матрицы L: S[1,3]=L[1,3]=2 и S[1,2]=L[1,2]=4. На пути к указанным узлам нет транзитных узлов.

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

1. S[1,4]=L[1,4]=∞;

2. S[1,5]=L[1,5]= ∞;

3. S[1,6]=L[1,6]= ∞;

4. S[2,4]=S[1,2]+L[2,4]=4+∞=∞;

5. S[2,5]=S[1,2]+L[2,5]=4+2=6;

6. S[2,6]=S[1,2]+L[2,6]=4+∞=∞;

7. S[3,4]=S[1,3]+L[3,4]=2+5=7;

8. S[3,5]=S[1,3]+L[3,5]=2+3=5;

9. S[3,6]=S[1,3]+L[3,6]=2+∞=∞.

В уравнении 8 расстояние до узла 5 - наименьшее из всех возможных. Следовательно, на третьем шаге алгоритма пятый узел будет ближайшим а узел 3 - транзитным на кратчайшем маршруте до узла 5.

Аналогично вычисляются расстояния до 4-го и 5-го узлов.

Таблица 1.

Шаг	Набор узлов 1	Набор узлов 2	Целевой узел j	Расстояние S[1,j]	Транзитный узел	Порт
		2 3 4 5 6
	1 3	2 4 5 6
	1 2 3	4 5 6				-
	1 2 3 5	4 6				-
	1 2 3 4 5					-

После пяти шагов получим данные для формирования полной таблицы маршрутизации. Чтобы определить номер порта, через который отправляется пакет из узла 1 в направлении некоторого узла, следует воспользоваться методом обратного перемещения по таблице 4 от целевого узла к первому.

В нашем примере порты для передачи пакетов в узлы 3 или 2 известны, т.к. они соединены непосредственно с первым.

Чтобы определить порт для передачи пакета в узел 6, надо в строке 5 таблицы найти номер транзитного узла (5), перейти на 3-ю строку, в которой найти очередной транзитный узел (3), затем перейти на первую строку. В этой строке номер транзитного узла совпал с номером узла, для которого составлена таблица маршрутизации. Следовательно, передать пакет для узла 6 следует через порт 2.

Аналогично определяются порты для передачи пакетов в узлы 4 и 5. Полная таблица маршрутизации для узла 1 представлена в табл. 2.

Таблица 2.

Адрес узла назначения	Порт	Расстояние

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

3. Дистанционно–векторный алгоритм маршрутизации

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

Как работает дистанционно-векторный алгоритм, рассмотрим на примере структуры сети, изображенной на рис. 2.

Рис.2. Структура сети

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

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

В таблице применены обозначения:

S – адрес узла назначения;

Р – номер порта, на который должен быть послан пакет с адресом S;

N – количество транзитных узлов до узла назначения.

Таблица 3.

Узел 1

Узел 2

Узел 3

Узел 4

Узел 5

S

P

N

S

P

N

S

P

N

S

P

N

S

P

N

В определенный момент времени узлы отправляют соседним узлам содержимое своих таблиц маршрутизации. При этом в каждой рассылаемой записи содержится только адрес S и расстояние N. В результате первой рассылки информации о маршрутах таблицы маршрутизации будут иметь записи, представленные в таблице 4.

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

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

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

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

Таблица 4.

Узел 1	Узел 2	Узел 3	Узел 4	Узел 5
S	P	N	S	P	N	S	P	N	S	P	N	S	P	N
						4	2	1
4	2	1	3	2	1	2	1	1	1	3	1	2	2	1
			5	2	1				3	3	1
			4	1	1				2	1	1

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

Дистанционно-векторные алгоритмы хорошо работают только в небольших сетях. В больших сетях они засоряют линии связи интенсивным трафиком. Наиболее распространенным протоколом, основанным на дистанционно-векторном алгоритме, является протокол RIP, который распространен в двух версиях: RIP IP и RIP IPX.

Дата добавления: 2015-07-25