БИБЛИЯ ХАКЕРА

Маршрутизируемся

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

Компоненты маршрутизации

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

Определение маршрута

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

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

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

Роутеры сообщаются Друг с другом (и поддерживают свои маршрут­ные таблицы) путем передачи различных сообщений. Одним из видов та­ких сообщений является сообщение об «обновлении маршрутизации». Обновления маршрутизации обычно включают всю маршрутную таблицу или ее часть. Анализируя информацию об обновлении маршрутизации, поступающую ото всех любой из них может построить деталь­

Ную картину топологии сети. Другим примером сообщений, которыми обмениваются роверы, является «объявление о состоянии канала». Объ­явление о состоянии канала информирует другие роутеры о состоянии ка­налов отправителя. Канальная информация также может быть использо­вана для построения полной картины топологии сети. После того, как топология сети становится понятной, роутеры могут определить опти­мальные маршруты к пунктам назначения.

Коммутация

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

После проверки адреса протокола пункта назначения пакета роутер определяет, знает он или нет, как передать этот пакет к следующему роу - теру. Во втором случае (когда роутер не знает, как переслать пакет) пакет, как правило, игнорируется. В первом случае роутер отсылает пакет к сле­дующей роутеру путем замены физического адреса пункта назначения на физический адрес следующего роутера и последующей передачи пакета.

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

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

В изложенном выше описании рассмотрена коммутация между ис­точником и системой конечного пункта назначения. Международная Ор­ганизация по Стандартизации (ISO) разработала иерархическую терми­нологию, которая может быть полезной при описании этого процесса. В случае, если пользоваться этой терминологией, то устройства сети, не об­ладающие способностью пересылать пакеты между подсетями, называют­ся конечными системами (ES), в то время как устройства сети, имеющие такую способность, называются промежуточными системами (IS). Про­межуточные системы далее подразделяются на системы, которые могут сообщаться в пределах «доменов маршрутизации» («внутридоменные» IS), и системы, которые могут сообщаться как в пределах домена марш­рутизации, так и с другими доменами маршрутизации («междоменные IS»). Обычно считается, что «домен маршрутизации» — это часть объеди­ненной сети, находящейся под общим административным управлением и регулируемой определенным набором административных руководящих принципов. Домены маршрутизации называются также «автономными системами» (AS). Для определенных протоколов домены маршрутизации могут быть дополнительно подразделены на «участки маршрутизации», однако для коммутации как внутри участков, так и между ними также ис­пользуются внутридоменные протоколы маршрутизации.

Алгоритмы маршрутизации

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

Цели разработки алгоритмов маршрутизации

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

• Оптимальность

• Простота и низкие непроизводительные затраты

• Живучесть и стабильность

• Быстрая сходимость

• Гибкость

І

Оптимальность

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

Простота и низкие непроизводительные затраты

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

Живучесть и стабильность

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

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

Быстрая сходимость

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

Гибкость

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

Типы алгоритмов

Алгоритмы маршрутизации могут быть классифицированы по ти­пам. Например, алгоритмы могут быть:

• Статическими или динамическими

• Одномаршрутными или многомаршрутными

• Одноуровневыми или иерархическими

• С интеллектом в главной вычислительной машине или в роутере

• Внутридоменными и междоменными

• Алгоритмами состояния канала или вектора расстояний

Статические или динамические алгоритмы

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

Таккак статические системы маршрутизации не могут реагировать на изменения в сети, они, как правило, считаются непригодными для со­временных крупных, постоянно изменяющихся сетей. Большинство до­минирующих алгоритмов маршрутизации — динамические.

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

Одномаршрутные или многомаршрутные алгоритмы

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

Одноуровневые или иерархические алгоритмы

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

Ров до конечного пункта назначения.

Системы маршрутизации часто устанавливают логические группы узлов, называемых доменами, или автономными системами (AS), или об­ластями. В иерархических системах одни роутеры какого-либо домена могут сообщаться с других доменов, в то время как другие ро-

Утеры этого домена могут поддерживать связь с роутеры только в преде­лах своего домена. В очень крупных сетях могут существовать дополни­тельные иерархические уровни. Роутеры наивысшего иерархического уровня образуют базу маршрутизации.

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

Алгоритмы с интеллектом в главной вычислительной машине или в роутере

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

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

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

Внутридоменные или междоменные алгоритмы

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

Алгоритмы состояния канала или вектора расстояния

Алгоритмы состояния канала (известные также как алгоритмы «первоочередности наикратчайшего маршрута») направляют потоки мар­шрутной информации во все узлы объединенной сети. Однако каждый роутер посылает только ту часть маршрутной таблицы, которая описыва­ет состояние его собственных каналов. Алгоритмы вектора расстояния (известные также как алгоритмы Бэлмана-Форда) требуют от каждого ро - утера посылки всей или части своей маршрутной таблицы, но только сво­им соседям. Алгоритмы состояния каналов фактически направляют не­большие корректировки по всем направлениям, в то время как алгоритмы вектора расстояний отсылают более крупные корректировки только в со­седние роутеры.

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

Показатели алгоритмов (метрики)

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

• Длина маршрута

Ф Надежность

Ф Задержка

• Ширина полосы пропускания

• Нагрузка

Ф Стоимость связи Длина маршрута

Длина маршрута является наиболее общим показателем маршрути­зации. Некоторые протоколы маршрутизации позволяют администрато­рам сети назначать произвольные цены на каждый канал сети. В этом слу­чае длиной тракта является сумма расходов, связанных с каждым каналом, который был траверсирован. Другие протоколы маршрутизации определяют «количество пересылок», то есть показатель, характеризую­щий число проходов, которые пакет должен совершить на пути от источ­ника до пункта назначения через изделия объединения сетей (такие как роутеры).

Надежность

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

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

Задержка

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

Полоса пропускания

Полоса пропускания относится к имеющейся мощности трафика какого-либо канала. При прочих равных показателях, канал Ethernet 10 Mbps предпочтителен любой арендованной линии с полосой пропуска­ния 64 Кбайт/сек. Хотя полоса пропускания является оценкой макси­мально достижимой пропускной способности канала, маршруты, прохо­дящие через каналы с большей полосой пропускания, не обязательно будут лучше маршрутов, проходящих через менее быстродействующие ка­налы.