Сетевой уровень

Введение, сервисы

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

Сетевой уровень оперирует пакетами. Наиболее известный протокол сетевого уровня — IP. На сетевом уровне работают маршрутизаторы.

Задачи, ставившиеся при разработке сервисов сетевого уровня:

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

Возможны два типа сервисов:

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

Принципиальные отличия представлены в таблице:

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

Роутинг на сетевом уровне

Определение:

Сетевой уровень (англ. Network layer) - третий уровень в сетевой модели OSI, отвечающий за трансляцию логических адресов (IP) в физические (MAC), определения пути передачи данных, отслеживания неполадок и заторов в сети.

На сетевом уровне работает такое сетевое устройство, как маршрутизатор.

Схемы доставки данных

• Unicast - доставить данные одному выбранному устройству

• Anycast - доставить данные одному устройству из некоторой выбранной группы

• Multicast - доставить данные выбранной группе устройств

• Geocast - доставить данные некоторому географическому региону

• Broadcast - доставить данные всем устройствам в сети

Unicast - это основная схема доставки данных в Интернете. Далее речь пойдет об алгоритмах доставки для схемы Unicast.

Алгоритмы роутинга

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

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

Алгоритм на основе расстояния между устройствами

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

Алгоритм:

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

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

Link-state algorithm

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

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

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

Path vector algorithm

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

Определение:

Автономная система (англ. Autonomous system) - система IP-сетей и маршрутизаторов, управляемая одним или несколькими операторами, имеющими единую политику маршрутизации.

Path vector protocol используется для взяимодействия нескольких автономных систем. Предполагается, что в каждой из систем есть узел, который отвечает за свою автономную систему (speaker). Speaker создает таблицу маршрутизации для своей автономной системы и отправляет ее соседним автономным системам.

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

Зачем вообще нужен роутинг

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

Пример

Представим следующий граф:

Вершины- узлы сети, на ребрах написано ожидаемое время отправки сообщения между узлами. Пусть вершины A и B находятся в Лондоне, а вершины C и D в Нью-Йорке, в связи с чем время доставки сообщения между вершинами A и B или вершинами C и D быстрое, а между вершинами B и D или A и C медленнее.

Теперь представим, что хотим отправить сообщение из вершины B в вершину D. Самый простой способ- отправить напрямую, но он займет 120 мс. Если же отправить по маршруту B -> A -> C -> D, то потратим всего 110 мс, что быстрее, несмотря на большее количество узлов в маршруте. Алгоритмы маршрутизации как раз и используются для улучшения времени передачи таким образом.