Сетевой уровень. Функции и проблемы сетевого уровня. Алгоритмы маршрутизации. Принципы оптимальности. Маршрутизация по наикратчайшему пути и по вектору расстояния

Основной задачей сетевого уровня является маршрутизация пакетов: получение пакетов от всех источников и передача их по назначению.

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

Сервис сетевого уровня разрабатывался в след. целях:

- сервис должен быть независимым от технологии

передачи, используемой в подсети;

- транспортный уровень должен быть независим от числа,

типа и топологии подсети;

- адрес подсети доступный на транспортном уровне должен

иметь унифицированную форму по всей сети.

Проблемы выбора кач-ва сериса и внутр. организации:

1) Качество сервиса (надежный - с соединением или

ненадежный - без соединения).

2) Внутренняя организация сетевого уровня - виртуальные

каналы или дейтаграммы.

(В первом случае этот маршрут устанавливается один раз

для всех пакетов, а во втором - для каждого пакета.)

Теоретически возможны все четыре комбинации.

Качество сервиса.

Сервис не ориентированный на соединение подобен обычной почте, а ориентированный на соединение - телефонной системе.

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

Внутренняя организация сетевого уровня.

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

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

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

 

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

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

Заметим, что каждый процесс должен указать ожидаемое время освобождения виртуального канала. В противном случае возникнут проблемы с принятием решения при освобождении виртуального канала: может быть одна из машин на маршруте "зависла"?

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

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

 

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

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

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

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

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

Алгоритмы маршрутизации.

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

Устойчивость:

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

Стабильность:

Существуют алгоритмы маршрутизации, которые никогда не сходятся к какому-либо равновесному состоянию как бы долго они не работали.

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

На рис.5.4 приведен пример такого противоречия. Трафики между А-А', В-В', С-С' могут уже забить канал между Х-Х'. Поэтому вместо кратчайшего маршрута между Х и Х' надо будет выбирать какой-то другой маршрут.

Критерии оптимизации:

1) Минимизация средней задержки пакета один из

возможных критериев.

2) Максимизация пропускной способности сети.

Однако, эти критерии конфликтуют.

Виды алгоритмов маршрутизации:

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

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

 Т секунд, когда меняется нагрузка, когда меняется топология), какая метрика используется при оптимизации

(расстояние, число скачков, ожидаемое время передачи).

 

Принципы оптимальности.

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

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

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