Страница 67

Вычислительные комплексы и сети. Лекции

Главная
Страница 1
Страница 2
Страница 3
Страница 4
Страница 5
Страница 6
Страница 7
Страница 8
Страница 9
Страница 10
Страница 11
Страница 12
Страница 13
Страница 14
Страница 15
Страница 16
Страница 17
Страница 18
Страница 19
Страница 20
Страница 21
Страница 22
Страница 23
Страница 24
Страница 25
Страница 26
Страница 27
Страница 28
Страница 29
Страница 30
Страница 31
Страница 32
Страница 33
Страница 34
Страница 35
Страница 36
Страница 37
Страница 38
Страница 39
Страница 40
Страница 41
Страница 42
Страница 43
Страница 44
Страница 45
Страница 46
Страница 47
Страница 48
Страница 49
Страница 50
Страница 51
Страница 52
Страница 53
Страница 54
Страница 55
Страница 56
Страница 57
Страница 58
Страница 59
Страница 60
Страница 61
Страница 62
Страница 63
Страница 64
Страница 65
Страница 66
Страница 67
Страница 68
Страница 69
Страница 70
Страница 71
Страница 72
Страница 73
Страница 74
Страница 75
Страница 76
Страница 77
Страница 78
Страница 79
Страница 80
Страница 81
Страница 82
Страница 83
Страница 84

Скачать учебник

Предыдущая страница

Следующая страница

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

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

Если маршрутизатор вышел из строя, то пакет маршрутизатора будет изменен в соответствии с состоянием сети. Эти изменения прочувствуют все маршрутизаторы. Недостатки: последовательный номер пакета может достичь максимально возможного и обнулиться, тогда возникнет путаница. Одним из решений увеличения до 32 разрядов порядковых номеров пакетов (если обмен каждую секунду происходит, то 32х разрядов хватит на 100 лет). Другим недостатком является то, что при выключении одного из маршрутизаторов и потом включении порядковые номера его пакетов будут начинаться с нуля и будут игнорироваться в сети как устаревшие. Решение — использование возраста пакета. Возраст пакета уменьшается на 1 каждую секунду (как правило). Когда возраст становится равным нулю, он удаляется. Как правило, обмен пакетами в сети осуществляется раз в 10 секунд. Когда маршрутизатор выключится, т.е. больше 10 секунд поле возраста пакета будет уменьшено на единицу все равно и при загрузке и последующем распространении пакета он не удалится, т.к. возраст не ноль, т.е. будет сохранен во всех узлах сети.

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

Наиболее известные протоколы, использующие маршрутизаторы с учетом состояния линии (канала) — OSPF (в Интернете) и IS-IS (DecNet, часть Интернета).

Иерархическая маршрутизация

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

Пример:

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

Тогда для 1A таблица будет такая:

1A`	-	-
1B	1B	1
1C	1C	1
----
2	1B	2
3	1C	3
4	1C	3
5	1C	4

7 строк.

Вместо 720 можно хранить 23+ 30= 53 строки для 2 уровневой структуры. То есть можно избавится от излишнего количества строк. Оптимальное число уровней иерархии ln(N), где N – число маршрутизаторов.

Широковещательная маршрутизация

Широковещание — рассылка пакетов по всем пунктам назначения. Реализуется следующими способами:

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

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

Связующее дерево – представляет собой подмножество сети без петель. Пакет распространяется по всем линиям связующего дерева. Недостаток – надо знать связующее дерево (может быть доступно, или не доступна маршрутизация по векторам состояний).

Предыдущая страница

Следующая страница