В общедоступном значении слова маршрутизация означаетпередвижение информации от источника к пункту назначениячерез об'единенную сеть. При этом, как правило, на путивстречается по крайней мере один узел. Маршрутизация частопротивопоставляется об'единению сетей с помощью моста,которое, в популярном понимании этого способа, выполняетточно такие же функции. Основное различие между нимизаключается в том, что об'единение с помощью моста имеет место на Уровне 2 эталонной модели ISO, в то время как маршрутизация встречается на Уровне 3. Этой разницей об'ясняетсято, что маршрутизация и об'единение по мостовой схеме используютразличную информацию в процессе ее перемещения отисточника к месту назначения. Результатом этого является то,что маршрутизация и об'единение с помощью моста выполняютсвои задачи разными способами; фактически, имеетсянесколько различных видов маршрутизации и об'единения спомощью мостов. Дополнительная информация об об'единениисетей с помощью мостов приведена вГлаве 3 "Основы Об'единения сетей с помощью мостов".
Тема маршрутизации освещалась в научной литературе окомпьютерах более 2-х десятилетий, однако с коммерческой точки зрения маршрутизация приобрела популярность только в1970 гг. В течение этого периода сети были довольнопростыми, гомогенными окружениями. Крупномасштабноеоб'единение сетей стало популярно только в последнее время.
Маршрутизация включает в себя два основных компонента:определение оптимальных трактов маршрутизации итранспортировка информационых групп (обычно называемыхпакетами) через об'единенную сеть. В настоящей работепоследний из этих двух компонентов называется коммутацией.Коммутация относительно проста. С другой стороны,определение маршрута может быть очень сложным процессом.
Определение маршрута может базироваться наразличных показателях (величинах, результирующих изалгоритмических вычислений по отдельной переменной -например, длина маршрута) или комбинациях показателей.Программные реализации алгоритмов маршрутизации высчитываютпоказатели маршрута для определения оптимальных маршрутов кпункту назначения.
Для облегчения процесса определения маршрута, алгоритмымаршрутизации инициализируют и поддерживают таблицымаршрутизации, в которых содержится маршрутная информация.Маршрутная информация изменяется в зависимости отиспользуемого алгоритма маршрутизации.
Алгоритмы маршрутизации заполняют маршрутные таблицынеким множеством информации. Ассоциации"Пункт назначения/следующая пересылка" сообщаютроутеру, что определенный пункт назначения может бытьоптимально достигнут путем отправки пакета в определенныйроутер, представляющий "следующую пересылку" на путик конечному пункту назначения. При приеме поступающегопакета роутер проверяет адрес пункта назначения ипытается ассоциировать этот адрес со следующей пересылкой.На рис. 2-1 приведен пример маршрутной таблицы"место назначения/следующая пересылка".
В маршрутных таблицах может содержаться также и другаяинформация. "Показатели" обеспечивают информацию ожелательности какого-либо канала или тракта. Роутерысравнивают показатели, чтобы определить оптамальныемаршруты. Показатели отличаются друг oт друга в зависимостиот использованной схемы алгоритма маршрутизации. Далее вэтой главе будет представлен и описан ряд общих показателей.
Роутеры сообщаются друг с другом (и поддерживаютсвои маршрутные таблицы) путем передачи различных сообщений.Одним из видов таких сообщений является сообщение об "обновлениимаршрутизации". Обновления маршрутизации обычно включают всюмаршрутную таблицу или ее часть. Анализируя информацию обобновлении маршрутизации, поступающую ото всехроутеров, любой из них может построить детальнуюкартину топологии сети. Другим примером сообщений, которымиобмениваются роутеры, является "об'явление о состоянииканала". Об'явление о состоянии канала информирует другиероутеры о состоянии кааналов отправителя. Канальнаяинформация также может быть использована для построенияполной картины топологии сети. После того, как топологиясети становится понятной, роутеры могут определитьоптимальные маршруты к пунктам назначения.
Алгоритмы коммутации сравнительно просты и в основномодинаковы для большинства протоколов маршрутизации. Вбольшинстве случаев главная вычислительная машинаопределяет необходимость отправки пакета в другую главнуювычислительную машину. Получив определенным способом адресроутера, главная вычислительная машина-источникотправляет пакет, адресованный специально в физический адресроутера (уровень МАС), однако с адресом протокола(сетевой уровень) главной вычислительной машины пунктаназначения.
После проверки адреса протокола пункта назначения пакетароутер определяет, знает он или нет, как передатьэтот пакет к следующему роутеру. Во второмслучае (когда роутер не знает, как переслать пакет)пакет, как правило, игнорируется. В первом случаероутер отсылает пакет к следующей роутерупутем замены физического адреса пункта назначения нафизический адрес следующего роутера и последующей передачипакета.
Следующая пересылка может быть или не бытьглавной вычислительной машиной окончательного пунктаназначения. Если нет,то следующей пересылкой, как правило,является другой роутер, который выполняет такой жепроцесс принятия решения о коммутации. По мере того, какпакет продвигается через об'единенную сеть, его физическийадрес меняется, однако адрес протокола остается неизменным.Этот процесс иллюстрируется на Рис. 2-2.
В изложенном выше описании рассмотрена коммутация междуисточником и системой конечного пункта назначения. МеждународнаяОрганизация по Стандартизации (ISO) разработалаиерархическую терминологию, которая может быть полезной приописании этого процесса. Если пользоваться этойтерминологией, то устройства сети, не обладающиеспособностью пересылать пакеты между подсетями, называютсяконечными системами (ЕS), в то время как устройства сети,имеющие такую способность, называются промежуточнымисистемами (IS). Промежуточные системы далее подразделяются насистемы, которые могут сообщаться в пределах "доменовмааршрутизации" ("внутридоменные" IS), и системы, которыемогут сообщаться как в пределах домена маршрутизации, так ис другими доменами маршрутизации ("междоменные IS"). Обычносчитается, что "домен маршрутизации" - это частьоб'единенной сети, находящейся под общим административнымуправлением и регулируемой пределенным наборомадминистративных руководящих принципов. Домены маршрутизацииназываются также "автономными системами" (AS). Дляопрелеленных протоколов домены маршрутизации могут бытьдополнительно подразделены на "участки маршрутизации",однако для коммутации как внутри участков, так и между нимитакже используются внутридоменные протоколы маршрутизации.
Алгоритмы маршрутизации можно дифференцировать,основываясь на нескольких ключевых характеристиках.Во-первых, на работу результирующего протокола маршрутизациивлияют конкретные задачи, которые решает разработчикалгоритма. Во-вторых, существуют различные типы алгоритмовмаршрутизации, и каждый из них по-разному влияет на сетьи ресурсы маршрутизации. И наконец, алгоритмы маршрутизациииспользуют разнообразные показатели, которые влияют нарасчет оптимальных маршрутов. В следующих разделаханализируются эти атрибуты алгоритмов маршрутизации.
Цели разработки алгоритмов маршрутизации
При разработке алгоритмов маршрутизации часто преследуютодну или несколько из перечисленных ниже целей:
Оптимальность, вероятно, является самой общей цельюразработки. Она характеризует способность алгоритмамаршрутизации выбирать "наилучший" маршрут. Наилучшиймаршрут зависит от показателей и от "веса" этихпоказателей, используемых при проведении расчета. Например,алгоритм маршрутизации мог бы использовать несколькопересылок с определенной задержкой, но при расчете "вес"задержки может быть им оценен как очень значительный.Естественно, что протоколы маршрутизации дожны строгoопределять свои алгоритмы расчета показателей.
Простота и низкие непроизводительные затраты
Алгоритмы маршрутизации разрабатываются как можноболее простыми. Другими словами, алгоритм маршрутизациидолжен эффективно обеспечивать свои функциональныевозможности, с мимимальными затратами программногообеспечения и коэффициентом использования. Особенно важнаэффективность в том случае, когда программа, реализующаяалгоритм маршрутизации, должна работать в компьютере сограниченными физическими ресурсами.
Алгоритмы маршрутизации должны обладать живучестью.Другими словми, они должны четко функционировать в случаенеординарных или непредвиденных обстоятельств, таких какотказы аппаратуры, условия высокой нагрузки и некорректныереализации. Т.к. роутеры расположены в узловых точкахсети, их отказ может вызвать значительные проблемы.
Часто наилучшими алгоритмами маршрутизацииоказываются те, которые выдержали испытание временем идоказали свою надежность в различных условиях работы сети.
Алгоритмы маршрутизации должны быстро сходиться.Сходимость - это процесс соглашения между всемироутерами по оптимальным маршрутам. Когда какое-нибудьсобытие в сети приводит к тому, что маршруты или отвергаются, или ставновятся доступными, роутеры рассылают сообщенияоб обновлении маршрутизации. Сообщения об обновлениимаршрутизации пронизывают сети, стимулируя пересчетоптимальных маршрутов и, в конечном итоге, вынуждая всероутеры придти к соглашению по этим маршрутам. Алгоритмымааршрутизации, которые сходятся медленно, могутпривести к образованию петель маршрутизации или выходам изстроя сети.
На Рис. 2-3 изображена петля маршрутизации. В данномслучае, в момент времени t1 к роутеру 1 прибываетпакет. Роутер 1 уже был обновлен и поэтому он знает,что оптимальный маршрут к пункту назначения требует, чтобыследующей остановкой был роутер 2. Поэтомуроутер 1 пересылает пакет в роутер 2. Роутер 2еще не был обновлен, поэтому он полагает, что следующейоптимальной пересылкой должен быть роутер 1.
Поэтому роутер 2 пересылает пакет обратно вроутер 1. Пакет будет продолжать скакать взад и впередмежду двумя роутерами до тех пор, пока роутер 2не получит корректировку маршрутизации, или пока числокоммутаций данного пакета не превысит допустимогомаксимального числа.
Алгоритмы маршрутизации должны быть также гибкими.Другими словами, алгоритмы маршрутизации должны быстро иточно адаптироваться к разнообразным обстоятельствам в сети.Например, предположим, что сегмент сети отвергнут. Многиеалгоритмы маршрутизации, после того как они узнают об этойпроблеме, быстро выбирают следующий наилучший путь для всехмаршрутов, которые обычно используют этот сегмент. Алгоритмымаршрутизации могут быть запрограммированы таким образом,чтобы они могли адаптироваться к изменениям полосыпропускания сети, размеров очереди к роутеру,величины задержки сети и других переменных.
Алгоритмы маршрутизации могут быть классифицированы потипам. Например, алгоритмы могут быть:
Статические или динамические алгоритмы
Статические алгоритмы маршрутизации вообще вряд лиявляются алгоритмами. Распределение статических таблицмаршрутизации устанавливется администратором сети до началамаршрутизации. Оно не меняется, если только администраторсети не изменит его. Алгоритмы, использующие статическиемаршруты, просты для разработки и хорошо работают вокружениях, где трафик сети относительно предсказуем, а схемасети относительно проста.
Т.к. статические системы маршрутизации не могутреагировать на изменения в сети, они, как правило, считаютсянепригодными для современных крупных, постоянно изменяющихсясетей. Большинство доминирующих алгоритмов маршрутизации1990гг. - динамические.
Динамические алгоритмы маршрутизации подстраиваются кизменяющимся обстоятельствам сети в масштабе реальноговремени. Они выполняют это путем анализа поступающих сообщенийоб обновлении маршрутизации. Если в сообщении указывается,что имело место изменение сети, программы маршрутизациипересчитывают маршруты и рассылают новые сообщенияо корректировке маршрутизации. Такие сообщения пронизываютсеть, стимулируя роутеры заново прогонять своиалгоритмы и соответствующим образом изменять таблицымаршрутизации. Динамические алгоритмы маршрутизации могут дополнятьстатические маршруты там, где это уместно. Например, можноразработать "роутер последнего обращения" (т.е.роутер, в который отсылаются все неотправленные поопределенному маршруту пакеты). Такой роутер выполняетроль хранилища неотправленных пакетов, гарантируя, что всесообщения будут хотя бы определенным образом обработаны.
Одномаршрутные или многомаршрутные алгоритмы
Некоторые сложные протоколы маршрутизации обеспечиваютмножество маршрутов к одному и тому же пункту назначения.Такие многомаршрутные алгоритмы делают возможноймультиплексную передачу трафика по многочисленным линиям;одномаршрутные алгоритмы не могут делать этого. Преимуществамногомаршрутных алгоритмов очевидны - они могут обеспечитьзаначительно большую пропускную способность и надежность.
Одноуровневые или иерархические алгоритмы
Некоторые алгоритмы маршрутизации оперируют в плоскомпространстве, в то время как другие используют иерархииимаршрутизации. В одноуровневой системе маршрутизации всероутеры равны по отношению друг к другу. Виерархической системе маршрутизации некоторые роутерыформируют то, что составляет основу (backbone - базу) маршрутизации.Пакеты из небазовых роутеров перемещаются кбазовыи роутерам и пропускаются через них до тех пор,пока не достигнут общей области пункта назначения. Начиная сэтого момента, они перемещаются от последнего базовогороутера через один или несколько небазовыхроутеров до конечного пункта назначения.
Системы маршрутизации часто устанавливают логическиегруппы узлов, называемых доменами, или автономными системами(AS), или областями. В иерархических системах однироутеры какого-либо домена могут сообщаться сроутерами других доменов, в то время как другие роутерыэтого домена могут поддерживать связь с роутеры тольков пределах своего домена. В очень крупных сетях могут существоватьдополнительные иерархические уровни. Роутерынаивысшего иерархического уровня образуют базумаршрутизации.
Основным преимуществом иерархической маршрутизацииявляется то, что она имитирует организацию большинствакомпаний и следовательно, очень хорошо поддерживает их схемытрафика. Большая часть сетевой связи имеет место в пределахгрупп небольших компаний (доменов). Внутридоменнымроутерам необходимо знать только о другихроутерах в пределах своего домена, поэтому ихалгоритмы маршрутизации могут быть упрощенными.Соответственно может быть уменьшен и трафик обновлениямаршрутизации, зависящий от используемого алгоритмамаршрутизации.
Алгоритмы с игнтеллектом в главной вычислительной машине или в роутере
Некоторые алгоритмы маршрутизации предполагают, чтоконечный узел источника определяет весь маршрут. Обычно этоназывают маршрутизацией от источника. В системахмаршрутизации от источника роутеры действуют простокак устойства хранения и пересылки пакета, без всякийраздумий отсылая его к следующей остановке.
Другие алгоритмы предполагают, что главныевычислительные машины ничего не знают о маршрутах. Прииспользовании этих алгоритмов роутеры определяютмаршрут через об'единенную сеть, базируясь на своихсобственных расчетах. В первой системе, рассмотренной выше,интеллект маршрутизации находится в главной вычислительноймашине. В системе, рассмотренной во втором случае,интеллектом маршрутизации наделены роутеры.
Компромисс между маршрутизацией с интеллектом в главнойвычислительной машине и маршрутизацией с интеллектом вроутере достигается путем сопоставления оптимальностимаршрута с непроизводительными затратами трафика. Системы синтеллектом в главной вычислительной машине чаще выбираютнаилучшие маршруты, т.к. они, как правило, находят всевозможные маршруты к пункту назначения, прежде чем пакетбудет действительно отослан. Затем они выбирают наилучшиймааршрут, основываясь на определении оптимальности даннойконкретной системы. Однако акт определения всех маршрутовчасто требует значительного трафика поиска и большого об'емавремени.
Внутридоменные или междоменные алгоритмы
Некоторые алгоритмы маршрутизации действуют только впределах доменов; другие - как в пределах доменов, так имежду ними. Природа этих двух типов алгоритмов различная.Поэтому понятно, что оптимальный алгоритм внутридоменноймаршрутизации не обязательно будет оптимальным алгоритмоммеждоменной маршрутизации.
Алгоритмы состояния канала или вектора расстояния
Алгоритмы состояния канала (известные также какалгоритмы "первоочередности наикратчайшегомаршрута") направляют потоки маршрутной информации во всеузлы об'единенной сети. Однако каждый роутер посылаеттолько ту часть маршрутной таблицы, которая описываетсостояние его собственных каналов. Алгоритмы векторарасстояния ( известные также как алгоритмы Бэлмана-Форда)требуют от каждогo роутера посылки всей или частисвоей маршрутной таблицы, но только своим соседям. Алгоритмысостояния каналов фактически направляют небольшиекорректировки по всем направлениям, в то время как алгоритмывектора расстояний отсылают более крупные корректировкитолько в соседние роутеры.
Отличаясь более быстрой сходимостью, алгоритмысостояния каналов несколько меньше склонны к образованиюпетель маршрутизации, чем алгоритмы вектора расстояния. Сдругой стороны, алгоритмы состояния канала характеризуютсяболее сложными расчетами в сравнении с алгоритмами векторарасстояний, требуя большей процессорной мощности и памяти,чем алгоритмы вектора расстояний. Вследствие этого,реализация и поддержка алгоритмов состояния канала может быть более дорогостоящей. Несмотря на их различия, обатипа алгоритмов хорошо функционируют при самых различныхобстоятельствах.
Показатели алгоритмов (метрики)
Маршрутные таблицы содержат информацию, которуюиспользуют программы коммутации для выбора наилучшегомаршрута. Чем характеризуется построение маршрутных таблиц?Какова особенность природы информации, которую они содержат?В данном разделе, посвященном показателям алгоритмов,сделана попытка ответить на вопрос о том, каким образомалгоритм определяет предпочтительность одного маршрута посравнению с другими.
В алгоритмах маршрутизации используется много различныхпоказателей. Сложные алгоритмы маршрутизации при выборемаршрута могут базироваться на множестве показателей,комбинируя их таким образом, что в результате получаетсяодин отдельный (гибридный) показатель. Ниже перечисленыпоказатели, которые используются в алгоритмах маршрутизации:
Длина маршрута является наиболее общим показателеммаршрутизации. Некоторые протоколы маршрутизации позволяютадминистраторам сети назначать произвольные цены на каждыйканал сети. В этом случае длиной тракта является суммарасходов, связанных с каждым каналом, который былтраверсирован. Другие протоколы маршрутизации определяют"количество пересылок", т.е. показатель, характеризующийчисло проходов, которые пакет должен совершить на пути отисточника до пункта назначения через изделия об'единениясетей (такие как роутеры).
Надежность, в контексте алгоритмов маршрутизации,относится к надежности каждого канала сети (обычноописываемой в терминах соотношения бит/ошибка). Некоторыеканалы сети могут отказывать чаще, чем другие. Отказы однихканалов сети могут быть устранены легче или быстрее, чемотказы других каналов. При назначении оценок надежностимогут быть приняты в расчет любые факторы надежности. Оценкинадежности обычно назначаются каналам сети администраторамисети. Как правило, это произвольные цифровые величины.
Под задержкой маршрутизации обычно понимаютотрезок времени, необходимый для передвижения пакета отисточника до пункта назначения через об'единенную сеть.Задержка зависит от многих факторов, включая полосупропускания промежуточных каналов сети, очереди в порткаждого роутера на пути передвижения пакета,перегруженность сети на всех промежуточных каналах сети и физическое расстояние, на которое необходимо переместитьпакет. Т.к. здесь имеет место конгломерация нескольких важных переменных, задержка является наиболее общим и полезным показателем.
Полоса пропускания относится к имеющейсямощности трафика какого-либо канала. При прочих равныхпоказателях, канал Ethernet 10 Mbps предпочтителен любойарендованной линии с полосой пропускания 64 Кбайт/сек. Хотяполоса пропускания является оценкой максимально достижимойпропускной способности канала, маршруты, проходящие черезканалы с большей полосой пропускания, не обязательнобудут лучше маршрутов, проходящих через менеебыстродействующие каналы. Например, если болеебыстродействующий канал почти все время занят, тофактическое время, необходимое для отправки пакета в пунктназначения, для этого быстродействующего канала можетоказаться больше.
Нагрузка относится к степени занятости какого-либоисточника сети (такого, как роутер). Нагрузка можетбыть вычислена разнообразными способами, в том числе покоэффициенту использования главного процессора и числупакетов, обработанных в секунду. Постоянный контроль этихпараметров может привести к интенсивному расходованиюресурсов.
Другим важным показателем является стоимость связи.Некоторые компании интересует не столько эффективность,сколько операционные расходы. Даже если задержка в ихлинии может быть большой, они отправят пакеты через своисобственные линии, а не через линии общего пользования, т.к.им ридется платить за использованное время.
Как правило, термины "routed protocol" и "routing protocol" Постоянно путают. Routed protocol - этопротокол, отправленный по определенному маршруту черезоб'единеннувю сеть. Примерами таких протоколов являютсяInternet Protocol (IP), DECnet и Apple Talk. "Routingprotocol" - это протокол, который реализует алгоритммаршрутизации. Если изложить это просто, они отправляютпротоколы по определенному маршруту через об'единенную сеть.Примерами таких протоколов могут быть Interior GatewayRouting Protocol (IGRP), Open Shortest Path First (OSPF),Intermediate System to Intermediate System (IS-IS) и RoutingInformation Pwrotocol (RIP).