Информационные технологии в САПР. Вычислительные сети и компьютерная графика. Васильев С.А - 15 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Последние входят в систему протоколов TCP/IP и SPX/IPX, соответственно. Протоколы TCP/IP первоначально были разра-
ботаны для сети ARPANET, а затем на их основе стала развиваться сеть Intеrnet. Протоколы SPX/IPX разработаны и приме-
няются фирмой Novell для сетей Novell Netware, объединяющих персональные ЭВМ. Протоколы X.25 разработаны ITU и
включают части для физического, канального и сетевого уровней.
4.2. УПРАВЛЕНИЕ ПОТОКАМИ ДАННЫХ В СЕТЯХ
Управление потоками данных – это одна из функций сетевого уровня, включающая управление нагрузками и борьбу с
блокировками. Различают несколько уровней управления.
Межузловое управление
связано с распределением буферной памяти в промежуточных узлах (выделением каждому на-
правлению определённого числа буферов), сводящееся к ограничению длин канальных очередей.
Управление
«
вход
–
выход
» направлено на предотвращение блокировок. Реализуется указанием в первом пакете сообщения
его длины, что позволяет приёмному узлу прогнозировать заполнение памяти и запрещать приём дейтаграмм определённых
сообщений, если прогнозируется блокировка памяти.
Управление внешними потоками
(доступом) реализуется путём предо-ставления приоритета в передаче внутренним потокам
перед внешними, ограничением числа пакетов в сети (пакет принимается, если у узла есть соответствующее разрешение), посыл-
кой предупредительных пакетов-заглушек в адрес источника, от которого идут пакеты в перегруженную линию связи.
4.3. МАРШРУТИЗАЦИЯ
Цель маршрутизации – доставка пакетов по назначению с максимизацией эффективности. Чаще всего эффективность
выражена взвешенной суммой времён доставки сообщений при ограничении снизу на вероятность доставки. Маршрутизация
сводится к определению направлений движения пакетов в маршрутизаторах. Выбор одного из возможных в маршрутизаторе
направлений зависит от текущей топологии сети (она может меняться хотя бы из-за временного выхода некоторых узлов из
строя), длин очередей в узлах коммутации, интенсивности входных потоков и т.п.
Алгоритмы маршрутизации включают процедуры:
− измерение и оценивание параметров сети;
− принятие решения о рассылке служебной информации;
− расчёт таблиц маршрутизации (ТМ);
− реализация принятых маршрутных решений.
В зависимости от того, используется ли при выборе направления информация о состоянии только данного узла или всей
сети, различают алгоритмы
изолированные
и
глобальные
. Если ТМ реагируют на изменения состояния сети, то алгоритм
адаптивный
, иначе
фиксированный
(
статический
), а при редких корректировках –
квазистатический
. В статических маршру-
тизаторах изменения в ТМ вносит администратор сети.
Простейший алгоритм
– изолированный, статический.
Алгоритм кратчайшей очереди
в отличие от простейшего являет-
ся адаптивным, пакет посылается по направлению, в котором наименьшая очередь в данном узле.
Лавинный алгоритм
–
многопутевой, основан на рассылке копий пакета по всем направлениям, пакеты сбрасываются, если в данном узле другая
копия уже проходила. Очевидно, что лавинный алгоритм обеспечивает надёжную доставку, но порождает значительный
трафик и потому используется только для отдельных пакетов большой ценности.
Наиболее широко используемые протоколы маршрутизации – RIP (Routing Information Protocol) и OSPF (Open Shortest
Path First). Метод RIP иначе называется методом рельефов. Он основан на
алгоритме Беллмана-Форда
и используется пре-
имущественно на нижних уровнях иерархии. OSPF – алгоритм динамической маршрутизации, в котором информация о лю-
бом изменении в сети рассылается лавинообразно.
Алгоритм Беллмана-Форда относится к алгоритмам DVA (Distance Vector Algorithms). В DVA
рельеф
Ra(d) – это оценка
кратчайшего пути от узла
a
к узлу
d
. Оценка (условно назовем её расстоянием) может выражаться временем доставки, на-
дёжностью доставки или числом узлов коммутации (измерение в хопах) на данном маршруте. В ТМ узла, а каждому из ос-
тальных узлов отводится одна строка со следующей информацией:
− узел назначения;
− длина кратчайшего пути;
− номер
N
ближайшего узла, соответствующего кратчайшему пути;
− список рельефов от
а
к
d
через каждый из смежных узлов.
Например, на рис. 4.1 в узле
а
строка для
d
выглядит как
d
R
a
(
d
)
N
(
d
) =
j R
aj
(
d
)
R
ak
(
d
).
Пусть изменилась задержка
R
ak
(
d
) причём так, что
R
ak
(
d
) стало меньше, чем
R
aj
(
d
). Тогда в строке
d
таблицы маршрути-
зации узла
а
корректируется
R
a
(
d
),
N
(
d
) изменяется на
k
и, кроме того, всем соседям узла
а
посылается сообщение об изме-
нённом
R
a
(
d
). Например, в некотором соседнем узле
l
при этом будет изменено значение
R
la
(
d
) =
R
a
(
d
) +
R
l
(
a
). Мы видим, что
возникает итерационный процесс корректировки маршрутной информации в узлах маршрутизации.
Хотя алгоритм Беллмана-Форда сходится медленно, для сетей сравнительно небольших масштабов он вполне прием-
лем. В больших сетях лучше себя зарекомендовал алгоритм OSPF. Он основан на использовании в каждом маршрутизаторе
информации о состоянии всей сети. В основе OSPF лежит алгоритм Дийкстры поиска кратчайшего пути в графах. При этом
сеть моделируется графом, в котором узлы соответствуют маршрутизаторам, а рёбра – каналам связи. Веса рёбер – оценки
(расстояния) между инцидентными узлами. Рассмотрим итерационный алгоритм Дийкстры применительно к формированию
маршрутной таблицы в узле
а
графа, показанного на рис. 4.2 (числа показывают веса рёбер).

Страницы