1632
правки
Изменения
м
rollbackEdits.php mass rollback
=== Схемы доставки данных ===
* Unicast - доставить данные одному выбранному устройству
[[Файл:unicast.png]]
* Anycast - доставить данные одному устройству из некоторой выбранной группы
[[Файл:anycast.png]]
* Multicast - доставить данные выбранной группе устройств
[[Файл:multicast_network1.png]]
* Geocast - доставить данные некоторому географическому региону
[[Файл:geocast.png]]
* Broadcast - доставить данные всем устройствам в сети
[[Файл:broadcast.png]]
Unicast - это основная схема доставки данных в Интернете. Далее речь пойдет об алгоритмах доставки для схемы Unicast.
=== Алгоритмы роутинга ===
В больших сетях топология постоянно изменяется, поэтому необходимо изменять стратегии доставки сообщений в зависимости от этих изменений, а также в зависимости от загруженности сети. Для решения этой задачи существуют алгоритмы маршрутизации, благодаря которым роутер понимает, какому устройству нужно отправить сообщение, чтобы добиться хороших результатов в его доставке.
==== Алгоритмы Алгоритм на основе расстояния между устройствами ====Используют [[алгоритм Форда-Беллмана]]. Каждому ребру в сети присваивается некоторая цена и узлы выбирают маршрут для отправки данных, используя путь наименьшей цены. Алгоритм: Когда узел запускается, он знает только о своих ближайших соседях и цену для достижения каждого из них. Каждый узел регулярно отправляет своим соседям информацию о цене достижения всех узлов в сети, для которых он знает эту цену. Соседи получают эту информацию и сравнивают с имеющейся у них. Если за счет полученной информации можно улучшить цену достижения некоторой вершины, то они записывают эту информацию в своей таблице маршрутизации. Через какое-то время все узлы сети будут знать наилучшую цену доставки и оптимальный маршрут доставки сообщения от себя до некоторого узла В, благодаря чему смогут отправлять данные оптимально. Если топология сети изменяется, например, в следствии отказа какого-нибудь узла, то его соседи с использованием описанного выше алгоритма могут перестроить маршруты, которые использовали этот узел.==== Link-state algorithm ====Для данного алгоритма каждый узел в сети должен знать структуру графа, которым является сеть. Это достигается следующим образом: каждый узел при запуске знает только о своих соседях. Узел регулярно отправляет информацию о той части сети, про которую он что-то знает (уже узнал на предыдущих итерациях) своим непосредственным соседям, добавляя к этой информации число- версию отправляемых данных. Узел, получая данные от своего соседа, сравнивает версию в данных с собственной версией и если версия в данных больше, чем его собственная, то он использует данные для изменения своего представления о структуре графа и переплывает сообщение своим соседям. Если же версия в сообщении меньше, чем версия у узла, то данное сообщение игнорируется. Когда узнали информацию о структуре сети, можно построить граф сети для поиска кратчайших путей. На графе запускается [[алгоритм Дейкстры]], в результате выполнения которого узел узнает кратчайший путь от себя до любого другого узла сети, а также ближайшего соседа на этом пути, которому и будет пересылаться сообщение. Когда у вершины построен граф, используется специальный протокол, который позволяет понять, доступны ли все соседи вершины. Если с каким-то соседом что-то случилось, то вершина начинает перестраивать свой граф, используя алгоритм, аналогичный алгоритму для изначального построения графа.==== Path vector algorithm ====Описанные выше алгоритмы хороши для не очень больших сетей. В больших сетях их будет сложно реализовать, потому что придется тратить очень много ресурсов на построение графа сети, причем как ресурсов узлов для вычисления таблиц маршрутизации, так и ресурсов сети для постоянной отправки соседям сообщений о структуре сети.{{Определение|definition ='''Автономная система''' (англ. ''Autonomous system'') - система IP-сетей и маршрутизаторов, управляемая одним или несколькими операторами, имеющими единую политику маршрутизации.}} Path vector protocol используется для взяимодействия нескольких автономных систем. Предполагается, что в каждой из систем есть узел, который отвечает за свою автономную систему (speaker). Speaker создает таблицу маршрутизации для своей автономной системы и отправляет ее соседним автономным системам. Алгоритм похож на Алгоритм на основе расстояния между устройствами с той разницей, что между каждый узел одной автономной системы не общается с каждым узлом другой автономный системы, между собой общаются только спикеры, за счет чего экономятся ресурсы и решаются описанные выше проблемы для больших сетей.=== Зачем вообще нужен роутинг ===В общем случае в сети существует несколько путей для доставки данных от узла А до узла В. При этом скорость доставки данных по этим маршрутам может существенно отличаться в зависимости от пропускной способности каналов, задержек сети, количества вершин на пути, загруженности канала и других характеристик. Для того, чтобы доставка сообщения занимала меньше времени и используются алгоритмы маршрутизации.==== Пример ====Представим следующий граф: [[Файл:simple_net_graph.png]] Вершины- узлы сети, на ребрах написано ожидаемое время отправки сообщения между узлами. Пусть вершины A и B находятся в Лондоне, а вершины C и D в Нью-Йорке, в связи с чем время доставки сообщения между вершинами A и B или вершинами C и D быстрое, а между вершинами B и D или A и C медленнее. Теперь представим, что хотим отправить сообщение из вершины B в вершину D. Самый простой способ- отправить напрямую, но он займет 120 мс. Если же отправить по маршруту B -> A -> C -> D, то потратим всего 110 мс, что быстрее, несмотря на большее количество узлов в маршруте. Алгоритмы маршрутизации как раз и используются для улучшения времени передачи таким образом.
