Составление таблиц маршрутизации в маршрутизаторах

Рисунок 13 – Девять маршрутизаторов и локальная сеть (а); графовая модель той же системы (б)

Один из способов моделирования  локальной сети состоит в том, что ЛВС рассматривается в виде узла графа, как и маршрутизаторы. Это показано на рисунке 13, б. На рисунке сеть изображена в виде искусственного узла N, с которым соединены маршрутизаторы А, С и F. Возможность передачи пакетов от А к С по локальной сети отражается здесь наличием пути ANC.

Измерение стоимости линии

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

Возникает интересный вопрос: надо ли учитывать нагрузку на линию во время измерения задержки? Чтобы учесть загруженность линии, таймер должен включаться при отправке пакета ECHO. Чтобы игнорировать загрузку, таймер следует включать, когда пакет ECHO достигает начала очереди.

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

Создание  пакетов состояния линий

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

Рисунок 14 – Подсеть (а); пакеты состояния линий для этой подсети (б)

Создаются пакеты состояния линий  несложно. Самое трудное заключается  в выборе момента времени для  их создания. Их можно создавать  периодически через равные интервалы  времени. Другой вариант состоит  в создании пакетов, когда происходит какое-нибудь значительное событие  — например, линия или сосед  выходит из строя или, наоборот, снова  появляется в сети либо существенно изменяет свои свойства.

Распространение пакетов состояния линий

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

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

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

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

В-третьих, может произойти искажение  порядкового номера — например, вместо номера 4 будет принято число 65 540 (ошибка в 1-м бите); в этом случае пакеты с 5-го по 65 540-й будут игнорироваться некоторыми маршрутизаторами как устаревшие.

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

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

Структура данных, используемая маршрутизатором В для работы с подсетью, изображенной на рисунке 14, а, показана на рисунке 15. Каждый ряд здесь соответствует недавно полученному, но еще не полностью обработанному пакету состояния линий. В таблице записываются адрес отправителя, порядковый номер, возраст и данные. Кроме того, в таблице содержатся флаги рассылки и подтверждений для каждой из трех линий маршрутизатора В (к А, С и F соответственно). Флаги отсылки означают, что этот пакет следует отослать по соответствующей линии. Флаги подтверждений означают, что нужно подтвердить получение этого пакета по данной линии.

Рисунок 15 – Буфер пакетов маршрутизатора B с рисунка 14

Как видно из рисунке 15, пакет состояния линий от маршрутизатора А пришел напрямую, поэтому он должен быть отправлен маршрутизаторам С и F, а подтверждение о его получении следует направить маршрутизатору А, что и показывают флаговые биты. Аналогично, пакет от F следует переслать маршрутизаторам А и С, a F отослать подтверждение.

Однако ситуация с третьим пакетом, полученным от маршрутизатора Е, отличается. Он был получен дважды, по линиям ЕАВ и EFB, Следовательно, его нужно отослать только С, но подтверждения выслать и А, и F, как указывают биты.

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

Вычисление  новых маршрутов

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

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

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

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

Заключение

Маршрутизация с учетом состояния  линий широко применяется в современных сетях, поэтому следует сказать несколько слов о некоторых примерах протоколов, использующих данный алгоритм. Одним из таких протоколов является протокол OSPF (Open Shortest Path First), все чаще применяемый в Интернете.

Другим важным протоколом с учетом состояния линий является IS-IS (Intermediate System to Intermediate System — связь между промежуточными системами) — протокол, разработанный для сети DECnet и принятый впоследствии Международной организацией по стандартизации ISO для использования вместе с протоколом сетевого уровня CLNP, не требующим соединений. С тех пор он был модифицирован для поддержки также и других протоколов, в частности IP. Протокол IS-IS используется в некоторых магистралях сети Интернет (включая старую магистраль NSFNET) и в некоторых цифровых сотовых системах, например, в CDPD. В сети Novell NetWare применяется разновидность протокола ISIS (NLSP) для маршрутизации IPX-пакетов.

 

 

Список  использованных источников

1. Э. Таненбаум. Компьютерные сети. 4-е изд. – СПб.: Питер, 2003. – 992с.: ил.
2. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. 4-е изд. – СПб.: Питер, 2010. – 944с.: ил.