27
правок
Изменения
Новая страница: «'''Алгоритмы маршрутизации''' применяются для нахождения наилучшего пути между хостами с...»
'''Алгоритмы маршрутизации''' применяются для нахождения наилучшего пути между хостами сети. При этом сеть рассматривается, как граф, в котором маршрутизаторы - вершины графа, а физические линии соединения между ними - ребра. Каждому ребру присваивается свой вес, который может быть функцией многих параметров, например от количества транзитных участков, расстояния, стоимости связи, измеренной величины задержки и многих других.
Все алгоритмы маршрутизации можно разделить на статические, для которых выбор маршрута между каждой парой хостов производиться заранее, в автономном режиме, и не меняется со временем, и динамические - алгоритмы, меняющие решения при выборе маршрута в зависимости от изменения топологии и загруженности линий связи.
==Заливка(flooding)==
Алгоритм заливки является одним из самых простых, в нем каждый приходящий пакет пересылается на все исходящие линии, кроме той по которой он пришел.
====Дубликаты пакетов====
Этот алгоритм порождает много лишних пакетов, а в сетях с замкнутыми контурами бесконечное число пакетов, поэтому в заголовок пакета помещают счетчик пройденных им транзитных участков, каждый маршрутизатор, при получении этого пакета и пересылкой дальше уменьшает этот счетчик на единицу. Как только значение счетчика достигает нуля пакет дальше не пересылается. Изначально этот счетчик можно задать равным длине максимального пути в сети, или длине пути от отправителя до получателя, если она известна. Тем не менее один и тот же маршрутизатор может отправлять один и тот же пакет несколько раз, если получил его с разных линий. Один из методов борьбы с отправкой одного и того же пакета много раз состоит в том, что каждый маршрутизатор нумерует каждый пакет получаемый от своих хостов и добавляет этот номер в заголовок. Все маршрутизаторы ведут для всех маршрутизаторов-источников счетчик, хранящий максимальный номер полученного от него пакета. Теперь, когда приходит пакет с номером меньшим, чем тот, что храниться в счетчике пакет вместо пересылки просто игнорируется, поскольку этот пакет уже был переслан.
====Преимущества====
*гарантированно доставляет пакет
*может быть эффективен при широковещательной рассылке
*надежен
*не требует настройки, поэтому может быть использован внутри другого более сложного алгоритма
*удобен для тестирования, так как находит все пути от источника к получателю, в том числа и кратчайшие
====Недостатки====
*дублирование пакетов
*не практичен, так как увеличивает нагрузку на сеть
==Маршрутизация по вектору расстояний(distance vector routing)==
Алгоритмы маршрутизации работают опираясь на таблицы(называемые векторами), поддерживаемые всеми маршрутизаторами и содержащие сведения о кратчайших путях к каждому из возможных адресатов и о том, какую линию соединения при этом использовать. Для обновления этих таблиц маршрутизаторы периодически обмениваются информацией с соседними маршрутизаторами.
Каждая запись таблицы состоит из двух частей: предпочитаемые номер линии для данного адресата и предполагаемое расстояние до него. Будем считать, что каждый маршрутизатор знает расстояние до своих соседей(если расстояние изменяется в транзитных участках то оно равно 1, а если же расстояние измеряется временем задержки распространения, то маршрутизатор может измерить его с помощью специального пакета <tex>ECHO</tex>, в который отправитель помещает время отправления, а получатель отправляет обратно как можно быстрее). Каждые <tex>T</tex> мс все маршрутизаторы посылают свои таблицы всем своим соседям и получают подобные вектора от них. Пусть одна из таких таблиц пришла от соседа <tex>X</tex> и в ней указано расстояние от маршрутизатора <tex>X</tex> до маршрутизатора <tex>Y</tex>, обозначим его <tex>T_{xy}</tex>. Если маршрутизатор знает, что расстояние между ним и маршрутизатором <tex>X</tex> равно <tex>T_x</tex>, то расстояние до маршрутизатора <tex>Y</tex> через маршрутизатор <tex>X</tex> равно <tex>T_x + T_{xy}</tex>. Выполнив такие расчеты для всех своих соседей маршрутизатор может выбрать наилучшие пути и поместить их в соответствующую запись таблицы.
====Проблема счета до бесконечности====
Рассмотрим ситуацию: пусть в сети 5 маршрутизаторов <tex>A, B, C, D, E</tex>, соединенных последовательно. Изначально все они включены и расстояние измеряется в количестве транзитных участков. Внезапно связь между маршрутизаторами <tex>A</tex> и <tex>B</tex> теряется, либо <tex>A</tex> просто отключается. При первом обмене пакетами <tex>B</tex> не слышит ответа от <tex>A</tex>, но маршрутизатор <tex>C</tex> сообщает, что он знает путь до <tex>A</tex> длиной 2. Маршрутизатор <tex>B</tex> изменяет запись в таблице и считает, что теперь у него есть путь длиной 3 до маршрутизатора <tex>A</tex>. Аналогично, при следующей рассылке маршрутизатор <tex>C</tex> установит в своей таблице путь до <tex>A</tex> равным 4, так как получит от маршрутизаторов <tex>B</tex> и <tex>D</tex> таблицы, по которым они знают путь до маршрутизатора <tex>A</tex> длиной 3. С каждой следующей итерацией обновления таблиц расстояние до маршрутизатора <tex>A</tex> будет только увеличивается и через какое-то время уйдет в бесконечность.
====Преимущества====
*относительно небольшой объем хранимых каждым маршрутизатором данных
*простой алгоритм пересчета расстояний на каждой итерации
*быстрое распространение хороших новостей
====Недостатки====
*проблемы счета до бесконечности
==Маршрутизация с учетом состояния линий(link state routing)==
В основе данного алгоритма лежит простая идея каждый маршрутизатор должен уметь:
*обнаруживать своих соседей и узнавать расстояние до них
*задавать метрику расстояния с каждым из своих соседей
*создавать пакет, содержащий всю собранную информацию
*посылать этот пакет другим маршрутизаторам и принимать от них аналогичные
*вычислять кратчайший путь до всех маршрутизаторов
В результате выполнения всех этих пунктов каждый маршрутизатор будет иметь в своем распоряжении полную топологию сети и может запустить [[Алгоритм Дейкстры|алгоритм Дейкстры]] для определения кратчайших путей. Рассмотрим эти пункты подробнее.
====Знакомство с соседями====
Как только маршрутизатор загружается ему нужно получить информацию от соседей, для этого он посылает специальный пакет <tex>HELLO</tex>. В ответ маршрутизатор на другом конце линии посылает ответ, содержащий свое имя. Имена маршрутизаторов должны быть совершенно уникальными.
В случае соединений <tex>point-to-point</tex> проблем не возникает, но если некоторые маршрутизаторы соединены широковещательной связью ситуация усложняется. Пусть, например, маршрутизаторы <tex>A, B, C</tex> соединены широковещательной связью. Моделирование данной модели в виде связей <tex>point-to-point</tex> будет сильно увеличивать размер топологии, поэтому создает искусственный узел, назовем его <tex>N</tex>, соответствующий самой широковещательной связи. На самом деле роль этого узла будет играть один из маршрутизаторов <tex>A, B, C</tex>. Теперь, передача пакетов от <tex>A</tex> к <tex>C</tex> будет следовать по пути <tex>ANC</tex>.
====Задание метрики расстояний====
Метрика расстояния между двумя соседними маршрутизаторами может быть задана автоматически или оператором сети. Чаще всего ее задают обратно пропорциональной пропускной способности линии, благодаря этому будут выбираться пути с большей пропускной способностью. Второй способ заключается в определении задержки специального пакета <tex>ECHO</tex>, на который принимающий его маршрутизатор должен незамедлительно ответить. В это случае будут выбираться пути с наименьшей задержкой.
====Создание пакета состояния линий====
Специальный пакет для обмена информацией между соседними маршрутизаторами начинается с идентификатора отправителя, за которым следует порядковый номер и возраст. Далее для каждого соседа указывается соответствующая стоимость пути с ним. Важен вопрос времени создания этих пакетов. Обычно используются два варианта, первый заключается в том, что такие пакета создаются через определенные равные интервалы времени; второй - в те момента, когда в сети происходит какое-то событие, например линия или маршрутизатор выходят из строя или, наоборот, появляются в сети.
====Распространение пакетов состояния линий====
Распространение пакетов состояния линий - это самая сложная часть алгоритма. Все маршрутизаторы должны принимать такие пакеты как можно быстрее и безотказно, иначе может сложится ситуация, в которой маршрутизаторы могут использовать разные версии топологии, что может привести к петлям или недоступностям машин.
Самый простой способ распространения таких пакетов заключается в использовании алгоритма заливки. Для этого в пакет добавляется порядковый номер, увеличивающий с каждым следующим пакетом(см. [[Алгоритмы маршритизации#Заливка|алгоритм заливки]]).
С этим связано несколько проблем. Первая из них заключается в том, что порядковый номер может достигнуть максимального значения. Решение заключается в использовании 32-битных порядковых номеров, в этом случае даже если каждую секунду рассылать пакеты состояния линий, то порядковых номеров хватит больше, чем 137 лет.
Вторая заключается в том, что если маршрутизатор выключится будет потерян порядковый номер последнего отправленного пакета состояния линий. Если же в последствии он включится с нулевым номером, то часть пакетов будут проигнорированы как устаревшие.
Еще одна проблема состоит в том, что при пересылки пакетов могут произойти искажения, в следствии чего может измениться порядковый номер пакета, и некоторые следующие пакеты могут быть проигнорированы.
Решением двух последних проблем является добавление в пакет его возраста и уменьшении его на единицу каждую секунду. Когда возраст доходит до нуля, он считается устаревшим и данные об маршрутизаторе-отправителе сбрасываются, в том числе и счетчик полученных от него пакетов.
Для повышения надежности могут быть использованы некоторые усовершенствования. Например, когда пакет состояния линий приходит на маршрутизатор для заливки, он может быть поставлен в очередь на отправку не сразу, а через какой-то промежуток времени. Если в течении этого времени приходит еще один пакет от этого же маршрутизатора-отправителя, то маршрутизатор сравнивает их номера, и удаляется более старый пакет. А если номера совпадают, то удаляется дубликат. Так же для защиты от ошибок на линиях связи получение всех пакетов состояния линий подтверждается.
====Вычисление новых маршрутов====
Собрав полный комплект пакетов состояния линий, маршрутизатор может построить полный граф сети, так как он располагает данными о всех линиях. Теперь для построения кратчайших путей можно запустить [[Алгоритм Дейкстры|алгоритм Дейкстры]].
====Преимущества====
*отсутствие проблем медленного распространения новостей
====Недостатки====
*требуется большое количество памяти для хранения топологии сети
*требуется большое количество вычислительных ресурсом маршрутизатора
==Источники информации==
*Э. Таненбаум, Д.Уэзеролл - Компьютерные сети (5-е издание, 2012)
*[https://ru.wikipedia.org/wiki/Алгоритмы_маршрутизации Алгоритмы маршрутизации - Википедия]
Все алгоритмы маршрутизации можно разделить на статические, для которых выбор маршрута между каждой парой хостов производиться заранее, в автономном режиме, и не меняется со временем, и динамические - алгоритмы, меняющие решения при выборе маршрута в зависимости от изменения топологии и загруженности линий связи.
==Заливка(flooding)==
Алгоритм заливки является одним из самых простых, в нем каждый приходящий пакет пересылается на все исходящие линии, кроме той по которой он пришел.
====Дубликаты пакетов====
Этот алгоритм порождает много лишних пакетов, а в сетях с замкнутыми контурами бесконечное число пакетов, поэтому в заголовок пакета помещают счетчик пройденных им транзитных участков, каждый маршрутизатор, при получении этого пакета и пересылкой дальше уменьшает этот счетчик на единицу. Как только значение счетчика достигает нуля пакет дальше не пересылается. Изначально этот счетчик можно задать равным длине максимального пути в сети, или длине пути от отправителя до получателя, если она известна. Тем не менее один и тот же маршрутизатор может отправлять один и тот же пакет несколько раз, если получил его с разных линий. Один из методов борьбы с отправкой одного и того же пакета много раз состоит в том, что каждый маршрутизатор нумерует каждый пакет получаемый от своих хостов и добавляет этот номер в заголовок. Все маршрутизаторы ведут для всех маршрутизаторов-источников счетчик, хранящий максимальный номер полученного от него пакета. Теперь, когда приходит пакет с номером меньшим, чем тот, что храниться в счетчике пакет вместо пересылки просто игнорируется, поскольку этот пакет уже был переслан.
====Преимущества====
*гарантированно доставляет пакет
*может быть эффективен при широковещательной рассылке
*надежен
*не требует настройки, поэтому может быть использован внутри другого более сложного алгоритма
*удобен для тестирования, так как находит все пути от источника к получателю, в том числа и кратчайшие
====Недостатки====
*дублирование пакетов
*не практичен, так как увеличивает нагрузку на сеть
==Маршрутизация по вектору расстояний(distance vector routing)==
Алгоритмы маршрутизации работают опираясь на таблицы(называемые векторами), поддерживаемые всеми маршрутизаторами и содержащие сведения о кратчайших путях к каждому из возможных адресатов и о том, какую линию соединения при этом использовать. Для обновления этих таблиц маршрутизаторы периодически обмениваются информацией с соседними маршрутизаторами.
Каждая запись таблицы состоит из двух частей: предпочитаемые номер линии для данного адресата и предполагаемое расстояние до него. Будем считать, что каждый маршрутизатор знает расстояние до своих соседей(если расстояние изменяется в транзитных участках то оно равно 1, а если же расстояние измеряется временем задержки распространения, то маршрутизатор может измерить его с помощью специального пакета <tex>ECHO</tex>, в который отправитель помещает время отправления, а получатель отправляет обратно как можно быстрее). Каждые <tex>T</tex> мс все маршрутизаторы посылают свои таблицы всем своим соседям и получают подобные вектора от них. Пусть одна из таких таблиц пришла от соседа <tex>X</tex> и в ней указано расстояние от маршрутизатора <tex>X</tex> до маршрутизатора <tex>Y</tex>, обозначим его <tex>T_{xy}</tex>. Если маршрутизатор знает, что расстояние между ним и маршрутизатором <tex>X</tex> равно <tex>T_x</tex>, то расстояние до маршрутизатора <tex>Y</tex> через маршрутизатор <tex>X</tex> равно <tex>T_x + T_{xy}</tex>. Выполнив такие расчеты для всех своих соседей маршрутизатор может выбрать наилучшие пути и поместить их в соответствующую запись таблицы.
====Проблема счета до бесконечности====
Рассмотрим ситуацию: пусть в сети 5 маршрутизаторов <tex>A, B, C, D, E</tex>, соединенных последовательно. Изначально все они включены и расстояние измеряется в количестве транзитных участков. Внезапно связь между маршрутизаторами <tex>A</tex> и <tex>B</tex> теряется, либо <tex>A</tex> просто отключается. При первом обмене пакетами <tex>B</tex> не слышит ответа от <tex>A</tex>, но маршрутизатор <tex>C</tex> сообщает, что он знает путь до <tex>A</tex> длиной 2. Маршрутизатор <tex>B</tex> изменяет запись в таблице и считает, что теперь у него есть путь длиной 3 до маршрутизатора <tex>A</tex>. Аналогично, при следующей рассылке маршрутизатор <tex>C</tex> установит в своей таблице путь до <tex>A</tex> равным 4, так как получит от маршрутизаторов <tex>B</tex> и <tex>D</tex> таблицы, по которым они знают путь до маршрутизатора <tex>A</tex> длиной 3. С каждой следующей итерацией обновления таблиц расстояние до маршрутизатора <tex>A</tex> будет только увеличивается и через какое-то время уйдет в бесконечность.
====Преимущества====
*относительно небольшой объем хранимых каждым маршрутизатором данных
*простой алгоритм пересчета расстояний на каждой итерации
*быстрое распространение хороших новостей
====Недостатки====
*проблемы счета до бесконечности
==Маршрутизация с учетом состояния линий(link state routing)==
В основе данного алгоритма лежит простая идея каждый маршрутизатор должен уметь:
*обнаруживать своих соседей и узнавать расстояние до них
*задавать метрику расстояния с каждым из своих соседей
*создавать пакет, содержащий всю собранную информацию
*посылать этот пакет другим маршрутизаторам и принимать от них аналогичные
*вычислять кратчайший путь до всех маршрутизаторов
В результате выполнения всех этих пунктов каждый маршрутизатор будет иметь в своем распоряжении полную топологию сети и может запустить [[Алгоритм Дейкстры|алгоритм Дейкстры]] для определения кратчайших путей. Рассмотрим эти пункты подробнее.
====Знакомство с соседями====
Как только маршрутизатор загружается ему нужно получить информацию от соседей, для этого он посылает специальный пакет <tex>HELLO</tex>. В ответ маршрутизатор на другом конце линии посылает ответ, содержащий свое имя. Имена маршрутизаторов должны быть совершенно уникальными.
В случае соединений <tex>point-to-point</tex> проблем не возникает, но если некоторые маршрутизаторы соединены широковещательной связью ситуация усложняется. Пусть, например, маршрутизаторы <tex>A, B, C</tex> соединены широковещательной связью. Моделирование данной модели в виде связей <tex>point-to-point</tex> будет сильно увеличивать размер топологии, поэтому создает искусственный узел, назовем его <tex>N</tex>, соответствующий самой широковещательной связи. На самом деле роль этого узла будет играть один из маршрутизаторов <tex>A, B, C</tex>. Теперь, передача пакетов от <tex>A</tex> к <tex>C</tex> будет следовать по пути <tex>ANC</tex>.
====Задание метрики расстояний====
Метрика расстояния между двумя соседними маршрутизаторами может быть задана автоматически или оператором сети. Чаще всего ее задают обратно пропорциональной пропускной способности линии, благодаря этому будут выбираться пути с большей пропускной способностью. Второй способ заключается в определении задержки специального пакета <tex>ECHO</tex>, на который принимающий его маршрутизатор должен незамедлительно ответить. В это случае будут выбираться пути с наименьшей задержкой.
====Создание пакета состояния линий====
Специальный пакет для обмена информацией между соседними маршрутизаторами начинается с идентификатора отправителя, за которым следует порядковый номер и возраст. Далее для каждого соседа указывается соответствующая стоимость пути с ним. Важен вопрос времени создания этих пакетов. Обычно используются два варианта, первый заключается в том, что такие пакета создаются через определенные равные интервалы времени; второй - в те момента, когда в сети происходит какое-то событие, например линия или маршрутизатор выходят из строя или, наоборот, появляются в сети.
====Распространение пакетов состояния линий====
Распространение пакетов состояния линий - это самая сложная часть алгоритма. Все маршрутизаторы должны принимать такие пакеты как можно быстрее и безотказно, иначе может сложится ситуация, в которой маршрутизаторы могут использовать разные версии топологии, что может привести к петлям или недоступностям машин.
Самый простой способ распространения таких пакетов заключается в использовании алгоритма заливки. Для этого в пакет добавляется порядковый номер, увеличивающий с каждым следующим пакетом(см. [[Алгоритмы маршритизации#Заливка|алгоритм заливки]]).
С этим связано несколько проблем. Первая из них заключается в том, что порядковый номер может достигнуть максимального значения. Решение заключается в использовании 32-битных порядковых номеров, в этом случае даже если каждую секунду рассылать пакеты состояния линий, то порядковых номеров хватит больше, чем 137 лет.
Вторая заключается в том, что если маршрутизатор выключится будет потерян порядковый номер последнего отправленного пакета состояния линий. Если же в последствии он включится с нулевым номером, то часть пакетов будут проигнорированы как устаревшие.
Еще одна проблема состоит в том, что при пересылки пакетов могут произойти искажения, в следствии чего может измениться порядковый номер пакета, и некоторые следующие пакеты могут быть проигнорированы.
Решением двух последних проблем является добавление в пакет его возраста и уменьшении его на единицу каждую секунду. Когда возраст доходит до нуля, он считается устаревшим и данные об маршрутизаторе-отправителе сбрасываются, в том числе и счетчик полученных от него пакетов.
Для повышения надежности могут быть использованы некоторые усовершенствования. Например, когда пакет состояния линий приходит на маршрутизатор для заливки, он может быть поставлен в очередь на отправку не сразу, а через какой-то промежуток времени. Если в течении этого времени приходит еще один пакет от этого же маршрутизатора-отправителя, то маршрутизатор сравнивает их номера, и удаляется более старый пакет. А если номера совпадают, то удаляется дубликат. Так же для защиты от ошибок на линиях связи получение всех пакетов состояния линий подтверждается.
====Вычисление новых маршрутов====
Собрав полный комплект пакетов состояния линий, маршрутизатор может построить полный граф сети, так как он располагает данными о всех линиях. Теперь для построения кратчайших путей можно запустить [[Алгоритм Дейкстры|алгоритм Дейкстры]].
====Преимущества====
*отсутствие проблем медленного распространения новостей
====Недостатки====
*требуется большое количество памяти для хранения топологии сети
*требуется большое количество вычислительных ресурсом маршрутизатора
==Источники информации==
*Э. Таненбаум, Д.Уэзеролл - Компьютерные сети (5-е издание, 2012)
*[https://ru.wikipedia.org/wiki/Алгоритмы_маршрутизации Алгоритмы маршрутизации - Википедия]
