Если вы читали статью Как работают маршрутизаторы , то знаете, что маршрутизатор используется для управления сетевым трафиком и поиска наилучшего маршрута для отправки пакетов. Но задумывались ли вы когда-нибудь о том, как это делают маршрутизаторы? Маршрутизаторы должны иметь некоторую информацию о состоянии сети, чтобы принимать решения о том, как и куда отправлять пакеты. Но как они собирают эту информацию?
В этой статье мы узнаем, какая именно информация используется маршрутизаторами при определении того, куда отправить пакет.
- Основы
- LS-алгоритмы
- Пример: алгоритм Дейкстры
- Алгоритмы DV
- Иерархическая маршрутизация
Основы
Маршрутизаторы используют алгоритмы маршрутизации для поиска наилучшего маршрута к месту назначения. Когда мы говорим «лучший маршрут», мы учитываем такие параметры, как количество переходов (путешествие пакета от одного маршрутизатора или промежуточной точки к другому в сети), временная задержка и стоимость связи при передаче пакета.
Этот контент несовместим с этим устройством.
Основываясь на том, как маршрутизаторы собирают информацию о структуре сети и их анализе информации для определения наилучшего маршрута, у нас есть два основных алгоритма маршрутизации: алгоритмы глобальной маршрутизации и алгоритмы децентрализованной маршрутизации . В алгоритмах децентрализованной маршрутизации каждый маршрутизатор имеет информацию о маршрутизаторах, к которым он напрямую подключен, а не о каждом маршрутизаторе в сети. Эти алгоритмы также известны как алгоритмы DV (вектор расстояния). В алгоритмах глобальной маршрутизации каждый маршрутизатор имеет полную информацию обо всех других маршрутизаторах в сети и состоянии сетевого трафика. Эти алгоритмы также известны как алгоритмы LS (состояние канала). Мы обсудим алгоритмы LS в следующем разделе.
LS-алгоритмы
В алгоритмах LS каждый маршрутизатор должен выполнить следующие шаги:
- Определите маршрутизаторы, которые физически подключены к ним, и получите их IP-адреса. Когда маршрутизатор начинает работать, он сначала отправляет по сети пакет «HELLO». Каждый маршрутизатор, получивший этот пакет, отвечает сообщением, содержащим его IP-адрес .
- Измерьте время задержки (или любые другие важные параметры сети, такие как средний трафик) для соседних маршрутизаторов. Для этого маршрутизаторы отправляют эхо-пакеты по сети. Каждый маршрутизатор, который получает эти пакеты, отвечает пакетом эхо-ответа. Разделив время приема-передачи на 2, маршрутизаторы могут подсчитать время задержки. (Время прохождения туда и обратно — это мера текущей задержки в сети, определяемая по времени отскока пакета от какого-либо удаленного хоста.) Обратите внимание, что это время включает в себя как время передачи, так и время обработки — время, которое требуется пакетам для достижения места назначения и время, которое требуется получателю, чтобы обработать его и ответить.
- Рассылка своей информации по сети для других маршрутизаторов и получение информации от других маршрутизаторов. На этом этапе все маршрутизаторы делятся своими знаниями и передают свою информацию друг другу. Таким образом, каждый маршрутизатор может знать структуру и статус сети.
- Используя соответствующий алгоритм, определите наилучший маршрут между двумя узлами сети. На этом этапе маршрутизаторы выбирают наилучший маршрут к каждому узлу. Они делают это с помощью алгоритма, такого как алгоритм кратчайшего пути Дейкстры . В этом алгоритме маршрутизатор на основе информации, полученной от других маршрутизаторов, строит граф сети. На этом графике показано расположение маршрутизаторов в сети и их связи друг с другом. Каждая ссылка помечена числом, называемым весом или стоимостью . Это число является функцией времени задержки, среднего трафика, а иногда просто количества переходов между узлами. Например, если между узлом и пунктом назначения есть две ссылки, маршрутизатор выбирает ссылку с наименьшим весом.
Алгоритм Дейкстры проходит следующие этапы:
- Маршрутизатор строит граф сети и идентифицирует исходный и конечный узлы, например V1 и V2. Затем он строит матрицу, называемую «матрицей смежности». В этой матрице координата указывает вес. Например, [i, j] — это вес связи между Vi и Vj. Если нет прямой связи между Vi и Vj, этот вес идентифицируется как «бесконечность».
- Маршрутизатор создает набор записей состояния для каждого узла в сети. Запись содержит три поля: Поле предшественника — первое поле показывает предыдущий узел. Поле длины. Второе поле показывает сумму весов от источника до этого узла. Поле метки — последнее поле показывает статус узла. Каждый узел может иметь один режим статуса: «постоянный» или «предварительный».
- Маршрутизатор инициализирует параметры набора записей состояния (для всех узлов) и устанавливает их длину на «бесконечность» и их метку на «предварительно».
- Маршрутизатор устанавливает Т-узел. Например, если V1 должен быть исходным T-узлом, маршрутизатор изменяет метку V1 на «постоянный». Когда ярлык меняется на «постоянный», он больше никогда не меняется. Т-узел — это агент и не более того.
- Маршрутизатор обновляет набор записей состояния для всех предварительных узлов, которые напрямую связаны с исходным T-узлом.
- Маршрутизатор просматривает все предварительные узлы и выбирает тот, чей вес для V1 наименьший. Затем этот узел является T-узлом назначения.
- Если этот узел не является V2 (предполагаемый пункт назначения), маршрутизатор возвращается к шагу 5.
- Если это узел V2, маршрутизатор извлекает свой предыдущий узел из набора записей о состоянии и делает это до тех пор, пока не достигнет узла V1. Этот список узлов показывает лучший маршрут от V1 до V2.
Мы будем использовать этот алгоритм в качестве примера на следующей странице.
Пример: алгоритм Дейкстры
Здесь мы хотим найти лучший маршрут между A и E (см. ниже). Вы можете видеть, что существует шесть возможных маршрутов между A и E (ABE, ACE, ABDE, ACDE, ABDCE, ACDBE), и очевидно, что ABDE — лучший маршрут, поскольку его вес наименьший. Но жизнь не всегда так проста, и бывают сложные случаи, когда приходится использовать алгоритмы для поиска наилучшего маршрута.
- Как вы видите на первом изображении, исходный узел (A) был выбран в качестве T-узла, поэтому его метка является постоянной (постоянные узлы показаны закрашенными кружками, а T-узлы — символом -->).
- На следующем шаге вы увидите, что набор записей состояния предварительных узлов, непосредственно связанных с T-узлом (B, C), был изменен. Кроме того, поскольку B имеет меньший вес, он был выбран в качестве T-узла, а его метка была изменена на постоянную (см. ниже).
- На шаге 3, как и на шаге 2, был изменен набор записей состояния предварительных узлов, которые имеют прямую связь с T-узлом (D, E). Кроме того, поскольку D имеет меньший вес, он был выбран в качестве Т-узла, а его метка была изменена на постоянную.
- На шаге 4 у нас нет предварительных узлов, поэтому мы просто идентифицируем следующий T-узел. Поскольку E имеет наименьший вес, он был выбран в качестве T-узла.
Наконец, E — это пункт назначения, поэтому мы остановимся здесь.
Мы в конце! Теперь нам нужно определить маршрут. Предыдущий узел E — это D, предыдущий узел D — это B, а предыдущий узел B — это A. Таким образом, лучший маршрут — ABDE. В этом случае общий вес равен 4 (1+2+1).
Хотя этот алгоритм работает хорошо, он настолько сложен, что маршрутизаторам может потребоваться много времени для его обработки, а эффективность сети снижается. Кроме того, если маршрутизатор предоставляет неверную информацию другим маршрутизаторам, все решения о маршрутизации будут неэффективными. Чтобы лучше понять этот алгоритм, вот исходник программы, написанной на C:
#define MAX_NODES 1024 /* максимальное количество узлов */
#define INFINITY 1000000000 /* число больше любого максимального пути */
int n,расст[MAX_NODES][MAX_NODES]; /*dist[I][j] — расстояние от i до j */
void shortest_path (int s, int t, int path[])
{struct state { /* обрабатываемый путь */
предшественник ; /*предыдущий узел */
int length /*длина от источника до этого узла*/
enum {постоянный, предварительный} метка /*состояние метки*/
}состояние[MAX_NODES];
инт I, к, мин;
состояние структуры *
п;
for (p=&state[0];p < &state[n];p++){ /*инициализировать состояние*/
p->предшественник=-1
p-> длина = БЕСКОНЕЧНОСТЬ
р->метка=предварительно;
}
состояние[t].length=0; состояние[t].label=постоянный ;
к=т;
/*k — начальный рабочий узел */
делать{
/* лучший путь от k? */
для I=0; я < п; я++)
/*этот граф имеет n узлов */
if (dist[k][I] !=0 && state[I].label==предварительно){
если (состояние [k]. длина + расстояние [k] [I] < состояние [I]. длина) {
состояние[I].predecessor=k;
состояние[I].length=состояние[k].length + расстояние[k][I]
}
}
/* Найдите предварительно помеченный узел с наименьшей меткой. */
k=0;мин=БЕСКОНЕЧНОСТЬ;
для (I=0;I < n;I++)
if(state[I].label==tentative && state[I].length <
мин)=состояние[I].длина;
к=I;
}
состояние[k].label=постоянный
} пока (k!=s);
/*Копируем путь в выходной массив*/
я=0;к=0
Do{path[I++]=k;k=state[k].predecessor;} while (k > =0);
}
Алгоритмы DV
Алгоритмы DV также известны как алгоритмы маршрутизации Беллмана-Форда и алгоритмы маршрутизации Форда-Фалкерсона. В этих алгоритмах у каждого маршрутизатора есть таблица маршрутизации, которая показывает лучший маршрут для любого пункта назначения. Типичный график и таблица маршрутизации для маршрутизатора J показаны вверху страницы.
Как видно из таблицы, если маршрутизатор J хочет передать пакеты маршрутизатору D, он должен отправить их маршрутизатору H. Когда пакеты поступают на маршрутизатор H, он проверяет свою собственную таблицу и решает, как отправить пакеты маршрутизатору D.
В алгоритмах DV каждый маршрутизатор должен выполнить следующие шаги:
- Он подсчитывает вес ссылок, непосредственно связанных с ним, и сохраняет информацию в свою таблицу.
- В определенный период времени он отправляет свою таблицу своим соседним маршрутизаторам (не всем маршрутизаторам) и получает таблицу маршрутизации каждого из своих соседей.
- Основываясь на информации в таблицах маршрутизации своих соседей, он обновляет свою собственную.
Одна из важнейших проблем с алгоритмами 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.
Иерархическая маршрутизация
Как видите, в алгоритмах LS и DV каждый маршрутизатор должен сохранять некоторую информацию о других маршрутизаторах. Когда размер сети растет, количество маршрутизаторов в сети увеличивается. Следовательно, размер таблиц маршрутизации также увеличивается, и маршрутизаторы не могут эффективно обрабатывать сетевой трафик. Мы используем иерархическую маршрутизацию для решения этой проблемы. Давайте рассмотрим эту тему на примере:
Мы используем алгоритмы DV для поиска лучших маршрутов между узлами. В ситуации, изображенной ниже, каждый узел сети должен сохранить таблицу маршрутизации с 17 записями. Вот типичный график и таблица маршрутизации для A:
В иерархической маршрутизации маршрутизаторы классифицируются по группам, известным как регионы . Каждый маршрутизатор имеет информацию только о маршрутизаторах в своем регионе и не имеет информации о маршрутизаторах в других регионах. Таким образом, маршрутизаторы просто сохраняют одну запись в своей таблице для каждого другого региона. В этом примере мы классифицировали нашу сеть на пять регионов (см. ниже).
Если A хочет отправить пакеты любому маршрутизатору в регионе 2 (D, E, F или G), он отправляет их B и так далее. Как видите, при таком типе маршрутизации таблицы можно суммировать, поэтому эффективность сети повышается. В приведенном выше примере показана двухуровневая иерархическая маршрутизация. Мы также можем использовать трех- или четырехуровневую иерархическую маршрутизацию.
В трехуровневой иерархической маршрутизации сеть классифицируется на несколько кластеров . Каждый кластер состоит из нескольких регионов, и каждый регион содержит несколько маршрутизаторов. Иерархическая маршрутизация широко используется в интернет-маршрутизации и использует несколько протоколов маршрутизации.
Для получения дополнительной информации о маршрутизации и смежных темах перейдите по ссылкам на следующей странице.
Много дополнительной информации
Статьи по Теме
- Как работают маршрутизаторы
- Маршрутизатор Викторина
- Как работают брандмауэры
- Как работает интернет-инфраструктура
- Как работают коммутаторы LAN
- Как работает домашняя сеть
- Как работает трансляция сетевых адресов
- Что такое пакет?
- Когда люди ссылаются на «компьютерный алгоритм», о чем именно они говорят?
Больше отличных ссылок
- Интернет-энциклопедия: Маршрутизация
- Таблицы маршрутизации
- Сетевая маршрутизация
- Сетевой уровень
- Иерархическая маршрутизация
об авторе
Розбех Разави изучает электронику в Технологическом университете КНТ. Он также является переводчиком книги «Networking Essentials Plus» корпорации Microsoft. Его исследования были сосредоточены на областях TCP/IP, маршрутизации и сетевой безопасности.
