Как работают алгоритмы маршрутизации

[Carding 4 Carders]

Думаете, вы знаете, как работают роутеры? Эти устройства используют сложные формулы, чтобы точно определить, куда отправить пакет и как его туда доставить.

Если вы читали статью HowStuffWorks «Как работают маршрутизаторы», то вы знаете, что маршрутизатор используется для управления сетевым трафиком и поиска наилучшего маршрута для отправки пакетов. Но задумывались ли вы когда-нибудь о том, как маршрутизаторы это делают? Маршрутизаторам требуется некоторая информация о состоянии сети, чтобы принимать решения о том, как и куда отправлять пакеты. Но как они собирают эту информацию?
В этой статье мы узнаем, какая именно информация используется маршрутизаторами при определении, куда отправить пакет.

СОДЕРЖАНИЕ

1. Основы
2. LS Алгоритмы
3. Пример: алгоритм Дейкстры
4. Алгоритмы DV
5. Иерархическая маршрутизация

Основы​

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

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

LS Алгоритмы​

В алгоритмах LS каждый маршрутизатор должен выполнить следующие действия:

1. Определите маршрутизаторы, которые физически подключены к ним, и получите их IP-адреса. Когда маршрутизатор начинает работать, он сначала отправляет пакет «HELLO» по сети. Каждый маршрутизатор, получивший этот пакет, отвечает сообщением, содержащим его IP-адрес.
2. Измерьте время задержки (или любые другие важные параметры сети, такие как средний трафик) для соседних маршрутизаторов. Для этого маршрутизаторы отправляют эхо-пакеты по сети. Каждый маршрутизатор, который получает эти пакеты, отвечает пакетом эхо-ответа. Разделив время приема-передачи на 2, маршрутизаторы могут подсчитать время задержки. (Время приема-передачи - это мера текущей задержки в сети, определяемая по времени, когда пакет отскакивает от некоторого удаленного хоста.) Обратите внимание, что это время включает время передачи и обработки - время, необходимое пакетам для достижения пункта назначения и время, необходимое получателю для его обработки и ответа.
3. Широковещательная передача информации по сети для других маршрутизаторов и получение информации от других маршрутизаторов. На этом этапе все маршрутизаторы обмениваются своими знаниями и передают информацию друг другу. Таким образом, каждый маршрутизатор может знать структуру и статус сети.
4. Используя соответствующий алгоритм, определите лучший маршрут между двумя узлами сети. На этом этапе маршрутизаторы выбирают лучший маршрут к каждому узлу. Они делают это с помощью алгоритма, такого как алгоритм кратчайшего пути Дейкстры . В этом алгоритме маршрутизатор на основе информации, полученной от других маршрутизаторов, строит граф сети. На этом графике показано расположение маршрутизаторов в сети и их связи друг с другом. Каждая ссылка помечена числом, которое называется весом или стоимостью . Это число является функцией времени задержки, среднего трафика, а иногда и просто количества переходов между узлами. Например, если есть два канала между узлом и пунктом назначения, маршрутизатор выбирает канал с наименьшим весом.

Алгоритм Дейкстры проходит через следующие шаги:

1. Маршрутизатор строит граф сети и идентифицирует узлы источника и назначения, например, как V1 и V2. Затем он строит матрицу, называемую «матрицей смежности». В этой матрице координата указывает вес. Например, [i, j] - это вес связи между Vi и Vj. Если между Vi и Vj нет прямой связи, этот вес определяется как «бесконечность».
2. Маршрутизатор создает набор записей состояния для каждого узла в сети. Запись содержит три поля: Поле предшественника - первое поле показывает предыдущий узел. Поле длины - второе поле показывает сумму весов от источника до этого узла. Поле метки - последнее поле показывает статус узла. Каждый узел может иметь один статусный режим: «постоянный» или «предварительный».
3. Маршрутизатор инициализирует параметры набора записей состояния (для всех узлов) и устанавливает их длину равной «бесконечности», а их метку - «предварительная».
4. Маршрутизатор устанавливает Т-узел. Например, если V1 должен быть исходным T-узлом, маршрутизатор изменяет метку V1 на «постоянную». Когда ярлык меняется на «постоянный», он больше никогда не меняется. Т-узел - это агент и не более того.
5. Маршрутизатор обновляет набор записей состояния для всех предварительных узлов, которые напрямую связаны с исходным T-узлом.
6. Маршрутизатор просматривает все предварительные узлы и выбирает тот, чей вес для V1 самый низкий. Тогда этот узел является T-узлом назначения.
7. Если этот узел не V2 (предполагаемый пункт назначения), маршрутизатор возвращается к шагу 5.
8. Если этот узел - V2, маршрутизатор извлекает свой предыдущий узел из набора записей состояния и делает это до тех пор, пока не достигнет V1. Этот список узлов показывает лучший маршрут от V1 до V2.

Мы будем использовать этот алгоритм в качестве примера на следующей странице.

Пример: алгоритм Дейкстры​

Шаг 1.

Шаг 2.

Шаг 3.

Шаг 4.

Здесь мы хотим найти лучший маршрут между A и E (см. Ниже). Вы можете видеть, что существует шесть возможных маршрутов между A и E (ABE, ACE, ABDE, ACDE, ABDCE, ACDBE), и очевидно, что ABDE - лучший маршрут, потому что его вес самый низкий. Но жизнь не всегда так проста, и бывают сложные случаи, когда нам приходится использовать алгоритмы, чтобы найти лучший маршрут.

1. Как вы видите на первом изображении, исходный узел (A) был выбран как T-узел, и поэтому его метка является постоянной (мы показываем постоянные узлы с закрашенными кружками и T-узлы с символом ->).
2. На следующем шаге вы увидите, что набор записей состояния предварительных узлов, напрямую связанных с T-узлом (B, C), был изменен. Кроме того, поскольку B имеет меньший вес, он был выбран в качестве T-узла, и его метка была изменена на постоянную (см. Ниже).
3. На шаге 3, как и на шаге 2, был изменен набор записей состояния предварительных узлов, которые имеют прямую связь с T-узлом (D, E). Кроме того, поскольку D имеет меньший вес, он был выбран в качестве T-узла, и его метка была изменена на постоянную.
4. На шаге 4 у нас нет предварительных узлов, поэтому мы просто определяем следующий T-узел. Поскольку E имеет наименьший вес, он был выбран в качестве T-узла.

Наконец, пункт назначения - E., поэтому мы останавливаемся на этом.
Мы подошли к концу! Теперь нам нужно определить маршрут. Предыдущий узел E - это D, предыдущий узел D - это B, а предыдущий узел B - это A. Итак, лучший маршрут - ABDE. В этом случае общий вес равен 4 (1 + 2 + 1).

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

#define MAX_NODES 1024        /* maximum number of nodes */
#define INFINITY 1000000000      /* a number larger than every maximum path */
int n,dist[MAX_NODES][MAX_NODES];  /*dist[I][j] is the distance from i to j */
void shortest_path(int s,int t,int path[ ])
{struct state {                          /* the path being worked on */
int predecessor ;                     /*previous node */
int length                                /*length from source to this node*/
enum {permanent, tentative} label    /*label state*/
}state[MAX_NODES];
int I, k, min;
struct state *
                     p;
for (p=&state[0];p < &state[n];p++){       /*initialize state*/
p->predecessor=-1
p->length=INFINITY
p->label=tentative;
}
state[t].length=0; state[t].label=permanent ;
k=t ;                                                         
/*k is the initial working node */
do{                                                           
/* is  the better path from k? */
for I=0; I < n; I++)                                       
/*this graph has n nodes */
if (dist[k][I] !=0 && state[I].label==tentative){
            if (state[k].length+dist[k][I] < state[I].length){
               state[I].predecessor=k;
               state[I].length=state[k].length + dist[k][I]
            }
}
/* Find the tentatively labeled node with the smallest label. */
k=0;min=INFINITY;
for (I=0;I < n;I++)
     if(state[I].label==tentative && state[I].length <
min)=state[I].length;
     k=I;
    }
state[k].label=permanent
}while (k!=s);
/*Copy the path into output array*/
I=0;k=0
Do{path[I++]=k;k=state[k].predecessor;} while (k > =0);
}

Алгоритмы DV​

Типичный сетевой граф и таблица маршрутизации для маршрутизатора J.

Алгоритмы DV также известны как алгоритмы маршрутизации Беллмана-Форда и алгоритмы маршрутизации Форда-Фулкерсона. В этих алгоритмах каждый маршрутизатор имеет таблицу маршрутизации, которая показывает лучший маршрут для любого пункта назначения. Типичный график и таблица маршрутизации для маршрутизатора J показаны вверху страницы.
Как показано в таблице, если маршрутизатор J хочет получить пакеты на маршрутизатор D, он должен отправить их маршрутизатору H. Когда пакеты прибывают на маршрутизатор H, он проверяет свою собственную таблицу и решает, как отправить пакеты на D.

В алгоритмах DV каждый маршрутизатор должен выполнить следующие действия:

1. Он подсчитывает вес ссылок, напрямую связанных с ним, и сохраняет информацию в своей таблице.
2. В определенный период времени он отправляет свою таблицу соседним маршрутизаторам (не всем маршрутизаторам) и получает таблицу маршрутизации каждого из своих соседей.
3. На основе информации в таблицах маршрутизации своих соседей он обновляет свои собственные.

Одна из наиболее важных проблем с алгоритмами DV называется « счет до бесконечности». Давайте рассмотрим эту проблему на примере:
Представьте себе сеть с графиком, показанным ниже. Как вы видите на этом графике, существует только одна связь между A и другими частями сети. Здесь вы можете увидеть график и таблицу маршрутизации всех узлов:

Сетевой график и таблицы маршрутизации.

Теперь представьте, что связь между A и B разорвана. В это время B исправляет свою таблицу. По прошествии определенного времени маршрутизаторы обмениваются своими таблицами, и B получает таблицу маршрутизации C. Поскольку C не знает, что случилось со связью между A и B, он говорит, что у него есть ссылка на A с весом 2 (1 для C и B и 1 для B и A - это не так. знаю, что B не имеет связи с A). B получает эту таблицу и думает, что существует отдельная связь между C и A, поэтому он исправляет свою таблицу и меняет бесконечность на 3 (1 для B на C и 2 для C на A, как сказал C). И снова маршрутизаторы обмениваются столами. Когда C получает таблицу маршрутизации B, он видит, что B изменил вес своей ссылки на A с 1 до 3, поэтому C обновляет свою таблицу и изменяет вес ссылки с A на 4 (1 для C на B и 3 от B до A, как сказал B).

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

Проблема "счет до бесконечности".

Одним из способов решения этой проблемы является отправка маршрутизаторами информации только соседям, которые не являются эксклюзивными ссылками на пункт назначения. Например, в этом случае C не должен посылать B никакой информации об A, потому что B - единственный путь к A.

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

Сетевой график и таблица маршрутизации A.

Как видите, и в алгоритмах LS, и в DV каждый маршрутизатор должен сохранять некоторую информацию о других маршрутизаторах. Когда размер сети увеличивается, количество маршрутизаторов в сети увеличивается. Следовательно, размер таблиц маршрутизации также увеличивается, и маршрутизаторы не могут обрабатывать сетевой трафик так же эффективно. Для решения этой проблемы мы используем иерархическую маршрутизацию. Разберем эту тему на примере:
Мы используем алгоритмы DV, чтобы найти лучшие маршруты между узлами. В ситуации, изображенной ниже, каждый узел сети должен сохранить таблицу маршрутизации с 17 записями. Вот типичный график и таблица маршрутизации для A:

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

Если A хочет отправить пакеты любому маршрутизатору в регионе 2 (D, E, F или G), он отправляет их B и так далее. Как видите, при таком типе маршрутизации таблицы можно суммировать, поэтому эффективность сети повышается. В приведенном выше примере показана двухуровневая иерархическая маршрутизация. Мы также можем использовать трех- или четырехуровневую иерархическую маршрутизацию.

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