Маршрутизация пакетов в сетях

 

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

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

Выбор маршрутов в узлах связи ТКС производится в соответствии с реализуемым алгоритмом (методом) маршрутизации.

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

Основные цели маршрутизации заключаются в обеспечении:

• минимальной задержки пакета при его передаче от отправителя к получателю;

• максимальной пропускной способности сети, что достигается, в частности, нивелировкой загрузки линий связи ТКС;

• максимальной защиты пакета от угроз безопасности содержащей­ся в нем информации;

• надежности доставки пакета адресату;

• минимальной стоимости передачи пакета адресату.

Различают следующие способы маршрутизации.

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

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

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

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

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

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

Эффективность алгоритмов маршрутизации оценивается следу­ющими показателями:

• временем доставки пакетов адресату;

• нагрузкой на сеть, которая при реализации данного алгоритма со­здается потоками пакетов, распределяемыми по линиям и узлам сети. Количественная оценка нагрузки осуществляется длиной очередей пакетов в узлах;

• затратами ресурсов в узлах связи (временем работы коммуника­ционной ЭВМ, емкостью памяти). Факторы, снижающие эффективность алгоритмов маршрутизации:

• передача пакета в узел связи, находящийся под высокой нагрузкой;

• передача пакета в направлении, не приводящем к минимальному времени его доставки;

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

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

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

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

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

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

Локальная адаптивная маршрутизация основана на использова­нии информации, имеющейся в данном узле и включающей: таблицу маршрутов, которая определяет все направления передачи пакетов из этого узла; данные о состоянии выходных линий связи (работают или не работают); длину очереди пакетов, ожидающих передачи. Ин­формация о состоянии других узлов связи не используется. Таблица маршрутов определяет кратчайшие маршруты, обеспечивающие до­ставку пакета адресату за минимальное время. Преимущество тако­го метода состоит в том, что принятие решения о выборе маршрута производится с использованием самых последних данных о состоянии узла. Недостаток метода заключается в его «близорукости», посколь­ку выбор маршрута осуществляется без учета глобального состояния всей сети. Следовательно, всегда есть опасность передачи пакета по перегруженному маршруту.

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

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

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

Защита от ошибок в сетях

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

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

Выделяют две основные причины возникновения ошибок при пере­даче информации в сетях:

• сбои в какой-то части оборудования сети или возникновение не­благоприятных объективных событий в сети (например, коллизий при использовании метода случайного доступа в сеть). Как пра­вило, система передачи данных готова к такого рода проявлениям и устраняет их с помощью предусмотренных планом средств;

• помехи, вызванные внешними источниками и атмосферными явле­ниями.

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

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

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

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

Суть мажоритарного метода, давно и широко используемого в телеграфии, состоит в следующем. Каждое сообщение ограниченной длины передается несколько раз, чаще всего три раза. Принимаемые сообщения запоминаются, а потом производится их поразрядное срав­нение. Суждение о правильности передачи выносится по совпадению большинства из принятой информации методом «два из трех». На­пример, кодовая комбинация 01101 при трехразовой передаче была частично искажена помехами, поэтому приемник принял такие комбинации: 10101, O111O, 01001. В результате проверки каждой позиции отдельно правильной считается комбинация 01101.

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

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

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

К числу наиболее важных показателей корректирующих кодов относятся:

• значность кода, или длина кодовой комбинации, включающей ин­формационные символы (т) и проверочные, или контрольные, сим­волы (К). Обычно значность кода п есть сумма т+К;

• избыточность кода K_изб, выражаемая отношением числа конт­рольных символов в кодовой комбинации к значности кода;

• корректирующая способность кода К_кс, представляющая собой отношение числа кодовых комбинаций L, в которых ошибки были обнаружены и исправлены, к общему числу переданных кодовых комбинаций М в фиксированном объеме информации.

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

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

В этом коде контрольные символы занимают позиции, соответ­ствующие значениям 2°, 2¹, 2², 2³ и т.д., т.е. позиции с номерами 1, 2, 4, 8 и т.д. (нумерация позиций кодовой комбинации — слева направо). Количество контрольных символов в кодовой комбинации должно быть таким, чтобы в процессе декодирования сформированное кор­ректирующее число (в двоичной системе счисления) могло указать позицию кодовой комбинации с максимальным номером. Например, для пяти информационных разрядов потребуется четыре контрольных. В полученной кодовой комбинации позиция с наибольшим номером будет 9-й, что записывается как 1001, т.е. требует четырех разрядов.

Значения контрольных символов при кодировании определяются путем контроля на четность количества единиц в информационных разрядах кодовой комбинации. Значение контрольного символа рав­но 0, если количество единиц будет четным, и равно 1 при нечетном количестве единиц.

При определении значения 1-го контрольного символа, размещае­мого на 1-й позиции кодовой комбинации, проверяются на четность те информационные позиции, двоичные изображения номеров кото­рых содержат единицу в младшем разряде, т.е. проверяются позиции с нечетными номерами. При определении значения 2-го контрольного символа, размещаемого на 2-й позиции кодовой комбинации, прове­ряются на четность те информационные позиции, двоичные изобра­жения номеров которых содержат единицу во 2-м разряде, т.е. пози­ции с номерами 3, 6, 7, 10, 11 и т.д. Значение 3-го контрольного симво­ла, размещаемого на 4-й позиции кодовой комбинации, определяется путем контроля на четность тех информационных позиций, двоичные изображения номеров которых содержат единицу в 3-м разряде, т.е. позиции с номерами 5, 6, 7, 12 и т.д. Аналогично устанавливаются значения и других контрольных символов.

В процессе декодирования формируется корректирующее число (КЧ), разрядность двоичного изображения которого устанавливается по указанному выше правилу. Значения разрядов этого числа опреде­ляются по правилам, аналогичным тем, которые использовались для определения значений контрольных символов в процессе кодирова­ния. Разница лишь в том, что при определении значений разрядов КЧ проверяются на четность не только информационные позиции, но и контрольные. Например, для определения значения младшего разряда КЧ проверяются на четность те позиции кодовой комбинации, двоич­ные изображения номеров которых содержат единицу в младшем раз­ряде, т.е. позиции с нечетными номерами 1, 3, 5, 7 и т.д.

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

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

Системы передачи с обратной связью делятся на системы с ре­шающей обратной связью и системы с информационной обратной связью.

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

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

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

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

Исходные данные:

Е_инф = 2 Мбит — объем передаваемой информации;

L_k = 7 — длина окна (количество кадров в окне);

R_k = 4096 бит — длина одного кадра;

V _k = 9600 бит/с — пропускная способность канала связи;

М_к = 1000 — количество каналов в многоканальной линии связи;

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

Постановка задачи иллюстрируется на рис. 13.2. Данные передаются от узла А к узлу В по прямому каналу. В семикадровом окне на приемном пункте (в узле В) во втором кадре обнаружены ошибки, и сигнал об этом (NAK 2) по обратному каналу передается в узел А (рис. 13.2, а). В протоко­ле ARQ реализуется один из двух методов обнаружения и повторной пере­дачи искаженных данных:

• выборочное повторение (рис. 13.2, б), когда повторно передается только искаженный кадр данного окна. Все другие кадры этого окна, поступившие в узел В после искаженного кадра (в нашем примере это кадры с номерами от 3 до 7), временно хранятся на приемном пункте в буферном ЗУ;

• возвращение на n_k кадров (рис. 13.2, в), когда повторно передается не только искаженный кадр, но и все кадры данного окна, посту­пившие вслед за искаженным (предполагается, что источник, по­служивший причиной искажения второго кадра, продолжает дей­ствовать). Здесь надобность в буферном ЗУ пропадает. Рассчитаем показатели для первого варианта системы ARQ — с выбо­рочным повторением.

Время на передачу заданного объема информации определяется по формуле

где n_ok — количество окон в передаваемом объёме информации, причем

 

в

Рис. 13.2. Система с решающей обратной связью ARQ:

а — передача данных по прямому каналу; б — выборочное повторение;

в — возвращение на n_k кадров

 

 

Следовательно,

T₁ = 70 • (7+1) • 4096 / 9600 = 238,9 с.

Необходимый объем буферного ЗУ:

(13.3)

где L_3у — количество кадров данного окна, временно сохраняемых в буферном ЗУ (в нашем примере L_3y = 5).

Следовательно, Е_зу = 5 • 4096 • 1000 = 20 480 000 бит.

Для второго варианта системы ARQ — с возвращением на n_k кадров (в нашем примере N_K = 6) — определяется только время на передачу ин­формации:

(13.4)

Как видно, первый вариант предпочтительнее по времени на передачу заданного объема информации, зато требует на приемном пункте буфер­ной памяти. Разница в значениях показателей Т1, и Т₂ будет тем больше, чем выше интенсивность ошибок в линиях связи.

 

⇐ Предыдущая1234Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: