Next: Виды доступа в Internet Up: Работа Internet: организацияструктура, Previous: Системы сетевых адресов

Маршрутизация

  Более подробно см. в RFC 1022, 1036, 1467, 1517-1520.

Маршрутизация является необходимой составной частью функционирования Сети. Она осуществляется на сетевом уровне, поэтому стоило бы рассказать о ней раньше, когда шёл разговор о протоколе IP, но это не было сделано преднамеренно, только для того, чтобы сохранить генеральную линию изложения, не метаться из стороны в сторону, пытаясь объять необъятное. Про работу Internet можно рассказывать очень долго и всё будет очень интересно, но нам придётся себя смирить и наступить, как говорил воистину великий поэт, на горло собственной песне. Расскажем только о маршрутизации.

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

Маршрутизация в Internet происходит раздельно для различных уровней группирования в Сети. Каждая локальная сеть использует свои методы маршрутизации. Определённые группы локальных сетей объединяются в RD -- Routing Domains -- домены (области) маршрутизации, в которых маршрутизация производится согласно единым принципам, алгоритмам и протоколам. Элементарным объектом маршрутизации в RD являются уже не отдельные компьютеры, а сети Internet.

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

Сами RD полностью находятся внутри какого-либо одного AD -- Administration Domain -- административного домена. AD -- это сеть или группа сетей, работающих под единым управляющим началом. В одном административном домене может быть много разных маршрутных доменов. AD обычно соответствует какой-либо организации или ассоциации. Сами AD могут объединяться в AD более высокого уровня и т.д. То есть, административный домен является основным иерархическим элементом в структуре Сети.

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

Всё это похоже на то, как люди путешествуют по Земле. Путешественник знает, где спросить, как добраться до нужной страны, добирается туда, там спрашивает, как попасть в нужный регион, добравшись куда спрашивает, как попасть в город N, по прибытии в который начинает приставать к прохожим с вопросами типа:``Извините, Вы мне не подскажете, как я могу попасть на Невский проспект?'' и далее:``Пипл, а где тут Сайгон?''. Так и добирается.

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

Рассказ о самой этой структуре совсем нас не привлекает, нам более интересны сами алгоритмы маршрутизации. Протоколы, которыми пользуются маршрутизаторы для прокладки путей по Сети, в общем основаны на нескольких базовых алгоритмах. Расскажем о двух разных протоколах: RIP и OSPF.

RIP

RIP -- это Routeing Information Protocol -- протокол маршрутной информации. RIP относится к широкоизвестному классу протоколов маршрутизации, основанных на алгоритме Беллмана-Форда, относящемуся к классу так называемых алгоритмов векторов расстояний. Этот протокол наиболее подходит для использования в качестве внутреннего (меж)шлюзового протокола (IGP), т.е. для маршрутизации сообщений внутри автономной системы (AS), которая работает под неким единым началом и по единым принципам. RIP предназначен для работы в сетях (автономных системах) умеренных размеров, использующих достаточно однородную технологию. Он подходит для сетей многих компаний, научных и учебных заведений, использующих последовательные линии передачи данных, пропускные способности которых меняются в пределах сети незначительно.

RIP в качестве метрики может использовать только статические функции (постоянные по времени). Использование динамических метрик приводит к возникновению неустойчивостей, которые RIP отрабатывать не умеет.

Алгоритмы векторов расстояний основаны на обмене между маршрутизаторами только информацией о ``расстояниях'' между ними, точнее о соответствующих метриках. При этом считается, что сами сети являются точечными объектами, т.е. расстояния между любыми двумя узлами одной сети равны нулю, поэтому расстояния между маршрутизаторами двух разных сетей равны расстоянию между этими сетями.

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

Очевидно, что из этой таблицы расстояний составить собственно таблицу маршрутизации -- пара пустяков -- просто выбросить длины путей, и таблица готова. Вся проблема в том, как составить эти таблицы (вектора) расстояний так, чтобы они соответствовали действительности. Именно для этого и нужен алгоритм Беллмана-Форда.

Давайте придумаем простенькую систему сетей и будем вести рассуждения на её примере. См. рис. 3.6. Пусть узлы A, B, C, D и T являются маршрутизаторами сетей с аналогичными названиями. Пусть, далее, все линии, кроме линии C-D имеют ``длины'' 1, а линия C-D -- 10. Можно считать, что реально это не длины, а, например, стоимости пересылки по этим линиям связи.

 
Figure: Пример сети 

Советуем вам самим проследить, что происходит в этой системе с таблицами расстояний. Пусть, например, начальное состояние векторов расстояний такое, как показано в таблице 3.2. Учтите, мы специально придумали наиболее идиотское начальное состояние таблиц, чтобы вы сами смогли убедиться, что алгоритм Беллмана-Форда приводит к нужному результату при любых начальных условиях. Естественно, расстояния между соседями должны всегда соответствовать действительности, идиотизировать их мы не имеем права, иначе, исчезнет источник достоверной информации о состоянии сети.

Алгоритм Беллмана-Форда велит действовать так.

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

А именно, если маршрутизатор, положим для определённости, C видит, что его сосед, пусть это будет A, знает более короткий путь до некоторой сети, например до сети T, чем он сам, естественно, маршрутизатор учитывает путь от него до соседа, просто складывая эти пути, т.е. если оказывается, что через соседа A путь до сети T короче, то он изменяет запись в своей таблице расстояний, соответствующую сети T, вписывает туда, что до сети T путь лежит через этого самого соседа A и имеет длину:

Если же маршрутизатор C видит, что тот его сосед (A), через который проходит путь от него (C) к сети T, вдруг говорит, что путь от него (от A) до этого самой сети T, оказывается, длиннее, чем он (A) думал раньше, то C безропотно меняет в записи в своей таблице, соответствующей сети T, старое расстояние на новое, которое он вычисляет тем же очевидным образом:

Очевидно, что расстояния между соседями должны быть известны заранее -- это собственно и есть задаваемая метрика. И такие переговоры нужно повторять до полного удовлетворения. Вот, собственно, и весь алгоритм Беллмана-Форда.

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

Отсутствие ограничений на моменты рассылки сообщений позволяет всем маршрутизаторам работать асинхронно, по своим собственным часам.

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

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

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

Однако, исходный алгоритм Беллмана-Форда не предусматривает случая, когда некая сеть или её маршрутизатор становятся совсем недоступны, так как это фактически равносильно тому, что этот маршрутизатор перестаёт рассылать сообщения. В таком случае, теорема о сходимости неприменима, а процесс, совершенно очевидно, никогда не сойдётся.

Поэтому RIP развивает алгоритм Беллмана-Форда, обвешивая его разными хитростями. Покажем, как постепенно приходится навешивать парочку таких уловок.

Для случаев обрыва линий RIP должен иметь механизм диагностики обрыва. Диагностика выполняется просто: если сеть не отвечает соседу слишком долго, считается, что линия связи оборвана. Этой линии присваивается метрика, называемая ``бесконечностью''. В действительности, это просто число, которое реальной метрикой быть не может, будем пока считать, что оно является только признаком этой ``бесконечности'' и никаким иным целям не служит. ``Бесконечность'' при сложении с любым числом даёт опять ``бесконечность''. И ``бесконечность'' больше любого другого числа.

Теперь самостоятельно (это очень просто!) составьте таблицы расстояний для каждого маршрутизатора для приведённого примера сети, соответствующих стационарному состоянию системы сетей, убедитесь, что они порождают корректные таблицы маршрутизации. Убедились?

Всё бы хорошо, да вот приехал дядя Вася на экскаваторе и перепахал линию B-D. Промоделируйте, что будет твориться в сети теперь. Особенно внимательно следите за тем, что будет происходить с маршрутизацией сообщений от A к T и от С к T. Видите? До A и C быстро дошло, что путь к T через B теперь закрыт. Но A продолжает считать, что путь к T по-прежнему открыт через C, а C считает, что путь к T открыт через A. Так они кивают друг на друга и медленно увеличивают длину пути к T, проложенному друг через друга. Это забава длится довольно долго, очевидно, тем дольше, чем больше ``длина'' линии C-D.

Теперь представьте себе, что дядя Вася совсем разошёлся и, пока шёл этот процесс, перекопал линию C-D. A и C будут кивать друг на друга до бесконечности.

Для борьбы с такими зацикливаниями было решено использовать пресловутую ``бесконечность''. Её сделали обычным конечным числом, но оставили правило, гласящее, что сумма ``бесконечности'' и любого числа есть ``бесконечность''. При такой трактовке ``бесконечности'' вышеописанное кивание A и C друг на друга, очевидно, будет продолжаться до тех пор, пока они постепенно не доведут длину путей к T, проложенных друг через друга до ``бесконечности''+1. Тогда они поймут, что линия-то оборвана, и бросят это занятие.

Уловка сработала, но для её практического использования следует придумать, каким числом должна быть ``бесконечность''. Очевидно, что с одной стороны, это число должно быть достаточно большим, чтобы никакой реальный путь не мог иметь такую большую длину. Однако, с другой стороны, это число должно быть как можно меньше, чтобы вышеописанный процесс ``счёта до бесконечности'' продолжался как можно меньшее время. Сначала в качестве компромиса было выбрано 15. Позже, с ростом Internet ``бесконечность'' довели до 30. Очевидно, что эта самая ``бесконечность'' ограничивает сверху возможную длину пути, что может быть нежелательно в больших сетях.

Существует множество других уловок, придуманных для избавления от ``счёта до бесконечности'', но все они носят частный характер, и только ``бесконечность'' по-прежнему остаётся надёжной гарантией от зацикливаний в общем случае.

На этом мы кончим наш рассказ о RIP. Более подробно о RIP вы можете прочитать в RFC 1058, 1721-1724.

OSPF

Подробно об OSPF можно прочитать в RFC 1583-1585.

Начнём с указания недостатков протокола RIP.

Этот протокол использует фиксированную метрику -- методику вычисления ``длин'' маршрутов для их сравнения друг с другом. Поэтому он неприменим в ситуациях, требующих динамической маршрутизации, в зависимости от текущего состояния сети (текущей загруженности линий, их надёжности и т.п.). Попытки искусственного расширения возможностей RIP путём введения динамических метрик типа времён задержек при передаче по линии, пропускной способности и т.п. приводят к возникновению неустойчивостей, с которыми алгоритм Беллмана-Форда справиться не способен.

RIP можно использовать только в достаточно однородных сетях умеренных размеров. Использование алгоритма Беллмана-Форда (RIP) для маршрутизации в больших сетях очень неэффективно. При расширении сети увеличивается количество изменений топологии сети в единицу времени, что требует более частой передачи маршрутной информации. При этом также увеличивается и сама таблица маршрутизации, что в RIP означает увеличение объёма передаваемой за один раз маршрутной информации.

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

Ещё одна проблема -- ограничение накладываемое RIP на количество проходимых пакетом узлов.

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

OSPF -- это Open Shortest Path First -- открой кратчайший путь первым -- протокол следующего (по сравнению с RIP) поколения. Помимо основной функции -- маршрутизации -- он предоставляет услуги, отсутствующие у RIP. Он оперативно распределяет трафик между равноценными маршрутами, оптимизируя таким образом использование линий связи. Обеспечивает аутентификацию маршрутов и административный контроль, производя маршрутизацию областей. Также он предоставляет возможности маршрутизации по типу трафика.

OSPF использует иные механизмы сбора и использования маршрутной информации. Для составления таблиц маршрутизации он может использовать любые методы, в том числе алгоритм Беллмана-Форда.

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

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

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

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

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

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

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

OSPF также делает простым осуществление маршрутизации по типу трафика. Такая маршрутизация позволяет разделять весь трафик на классы (до восьми классов) и предоставлять разные маршруты для разных классов. Например, передача файлов может осуществляться по спутниковой линии с большой пропускной способностью, обладающей, однако, значительными задержками, и одновременно осуществляться передача трафика telnet по наземной арендованной линии с малой пропускной способностью, но малыми задержками.

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

OSPF хорош ещё и тем, что его можно очень просто доработать для осуществления маршрутизации груповых передач. Групповая передача (multicasting) -- передача сообщения сразу нескольким получателям. Если широковещание -- это передача всем компьютерам данной сети, то групповая передача -- только группе указанных.

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

Так как при использовании OSPF каждый маршрутизатор имеет всю необходимую для маршрутизации информацию о состоянии сети, он легко может определить маршрут групповой передачи, минимально загружающий сеть. Подробнее об этом расширении OSPF (MOSPF) можно прочитать в RFC 1584, 1585.

Пожалуй, единственным недостатком OSPF является его сложность. Если описание RIP в RFC 1058 занимает 93KB, то описание OSPF в RFC 1583 занимает 524KB.

Наслаждение результатами

Результаты всей этой хитрой работы можно легко пронаблюдать, если воспользоваться утилитой traceroute (в UNIX и VAX/VMS она называется так). Она показывает, через какие узлы следует тестовый пакет -- своего рода пробный шар. Наблюдать за путешествиями такого пакета -- преувлекательнейшее занятие, оно может очень многое рассказать о структуре Сети, линиях связи, маршрутизации, интеллектуальном уровне администраторов различных сетей. Весьма поучительное развлечение.

Для трассировки маршрута traceroute использует ICMP пакеты особого рода. Подробнее об этом можно прочитать, например, в RFC 1393.