Чернега В., Платтнер Б. Компьютерные сети. Учебное пособие для вузов

Подождите немного. Документ загружается.

Раздел 1. Общие принципы построения компьютерных сетей

рые должно проходить сообщение. Специальные программы маршрутиза-

ции анализируют адресные части пакетов и на основании таблиц и дополни-

тельной информации о состоянии сети преобразуют их в направления пере-

дачи. При этом на многих узлах осуществляется определение оптимального

маршрута. Критерием оптимизации чаще всего выступает время доставки

пакетов в сети.

В качестве математического аппарата оптимизации используется тео-

рия графов, потоков и сетей. Оптимизация маршрута сводится к выбору

кратчайшего пути в графе с минимальной очередью пакетов.

1.4.3. Алгоритмы маршрутизации в компьютерных сетях

В отличие от классических телефонных сетей и интегральных цифро-

вых сетей передачи данных, компьютерные сети имеют специфические осо-

бенности транспортировки сообщений, в частности следующие:

 многие соединения проходят через очень большое число узлов комму-

тации;

 линии и узлы обладают недостаточно высокой надежностью;

 характер передаваемых сообщений в течение нескольких минут может

существенно измениться;

 малое количество альтернативных путей передачи.

При рассмотрении наиболее широко используемых алгоритмов мар-

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

адреса соседних узлов, а для всех линий связи, соединяющих соседние узлы,

определена их метрика. В качестве метрики связей часто используется

"стоимость" или "расстояние". Обобщенное понятие стоимости учитывает

как фактическую стоимость использования линии, так и ряд других пара-

метров (расстояние, пропускную способность, задержку передачи и т.д.).

Рассматриваемые алгоритмы относятся к распределенным, в которых

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

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

нивается сообщениями только со своими соседями. Для этого в общем тре-

буется большое число шагов (хопов), пока сеть не установится в стабильное

состояние.

При выполнении алгоритма маршрутизации узел должен получать

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

тизации, о сетях, которые могут быть достижимы при передаче данных че-

рез каждый соседний узел. Накапливая полученную информацию, каждый

узел может определить направление – маршрут передачи данных для каж-

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

Компьютерные сети

сколько, алгоритм маршрутизации может предусматривать использование

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

В зависимости от способа, используемого для обеспечения обмена

информацией о маршрутах в сети между узлами при выполнении алгорит-

ма маршрутизации, различают два типа протоколов маршрутизации:

 дистанционно-векторные (distant vector);

 оценки состояния линий (link state).

Дистанционно-векторные протоколы передают информацию о мар-

шрутах периодически через установленные интервалы времени.

Протоколы оценки состояния линий предусматривают передачу ин-

формации о маршрутах в момент первоначального включения или при воз-

никновении изменений в существующей структуре информационных свя-

зей.

Алгоритм Беллмана-Форда относится к дистанционно-векторным

алгоритмам DVA (Distance Vector Algorithms). Исходным положением в

этом алгоритме является то, что каждому узлу известно расположение и

возможности узлов сети, но неизвестны кратчайшие пути к ним. Под крат-

чайшим путем подразумевается путь с минимальной стоимостью. На каж-

дом узле имеется вектор расстояний, представляющий собой список с запи-

сями вида: "Получатель; Стоимость". Стоимость обозначает при этом те-

кущее значение суммы стоимостей доставки сообщения по кратчайшему пу-

ти к соответствующему получателю. В качестве начального значения каж-

дый узел устанавливает такие стоимости доставки сообщений к несмежным

узлам, которые заведомо выше самых высоких ожидаемых затрат (устанав-

ливается бесконечно большое значение).

Через установленное время узлы сети периодически рассылают слу-

жебные пакеты update, содержащие текущие значения векторов стоимостей,

всем своим непосредственным соседям. На основании этой информации ка-

ждый узел сети определяет для любого возможного получателя пути с ми-

нимальными затратами. Это производится суммированием стоимостей дос-

тавки сообщений соседям с соответствующими стоимостями доставки от

соседа к получателю, которые сообщил его соседний узел.

Для формального описания алгоритма Беллмана-Форда введем внача-

ле следующие обозначения: s – исходный узел, от которого будет находить-

ся оптимальный путь до некоторого узла k; w(i,j) – стоимость пути от узла i

до узла j, которая при начальной инициализации устанавливается w(i,i)=0, а

w(i,j)=, если эти узлы не являются смежными и w(i,j)  0, если узлы i и j

непосредственно соединены между собой; h – максимальное количество

участков (хопов) в пути на текущем этапе алгоритма; L(k) – стоимость оп-

тимального пути от узла s до узла k, содержащего не более h участков.

Алгоритм сводится к следующим действиям.

Раздел 1. Общие принципы построения компьютерных сетей

1. Начальная инициализация

(k) =



для всех k s; L

(s)=0 для всех h=0;

2. Модификация

Для всех последующих h  0; для каждого k s вычисляем

.)],()([min)(

kiwjLkL







Соединяем k узел с предшествующим узлом j, который дает мини-

мальную стоимость, и удаляем соединение k с другим предшествующим уз-

лом, созданное на предыдущей итерации. Путь от s до k заканчивается уча-

стком линии от j до k.

На рисунке 1.14 показан пример, иллюстрирующий действие алгорит-

ма для сети с топологией, изображенной на рисунке 1.14,а.

Сеть моделируется графом, в котором узлы соответствуют маршрути-

заторам, а ребра – линиям связи. Веса ребер – оценки стоимостей доставки

сообщений между узлами. Построение оптимальных маршрутов от узла А

до остальных узлов сети для трех этапов (h=3) изображены соответственно

на рисунке 1.14,б-г.

Здесь цифрами на ребрах графа отмечены стоимости линий связи

w(i,j) между узлами, а цифрами внутри кружков – стоимости L

(s) соответ-

ствующих путей.

Использование алгоритма в представленной упрощенной форме (без

учета состояния линий) может привести к проблемам в сети, в случае если

произойдет нарушение (отказ) одного из соединений, или в сеть введены

новые каналы связи. Одним из недостатков, присущих алгоритму Беллмана-

Рисунок 1.14 – Иллюстрация построения маршрутов минимальной

стоимости на основании алгоритма Беллмана-Форда

Компьютерные сети

Форда, является возможность возникновения петель (шлейфов) маршрути-

зации, в результате чего один и тот же пакет циркулирует определенное

время между двумя или несколькими узлами. Вторым недостатком алгорит-

ма является несоответствие таблиц маршрутизации узлов мгновенному со-

стоянию сети (большое время переходного процесса).

Для иллюстрации процесса образования петель рассмотрим фрагмент

сети, состоящий из четырех узлов-маршрутизаторов A, B, C и D (рисунок

1.15), соединенный с сетью N с помощью маршрутизатора А. Пусть, как по-

казано на рисунке, все связи между узлами имеют метрику (стоимость)1.

В исходном состоянии, когда все каналы передачи данных функцио-

нируют нормально, маршруты из узлов D и C к сети N проходят через мар-

шрутизатор B и имеют метрику 2. Если в некоторый момент времени канал,

связывающий маршрутизаторы A и В, выходит из строя, то маршрутизатор

B в этом случае перестает принимать от маршрутизатора A модифицирую-

щую информацию о состоянии сети N.

По истечении установленного интервала времени маршрутизатор B

определяет сеть N в качестве недостижимой и исключает её из своих масси-

вов векторов состояний. Однако из-за того, что эти массивы передаются в

сети асинхронно, вполне возможно, что вскоре после этого маршрутизатор

C до поступления информации от В о недостижимости узла А, получит

сначала модифицирующий массив от маршрутизатора D. Последний пока

ещё считает, что маршрут из B до сети N существует. Получив такую ин-

формацию, маршрутизатор C включит в свою таблицу маршрутизации но-

вый маршрут до сети N через маршрутизатор D с метрикой 3 (C-D-B-A) и

сообщает о нем соседним узлам B и D.

После того, как истечет время существования исходного пути в мар-

шрутизаторе D о достижимости узла А, эта ситуация повторится совершен-

но аналогичным образом. В результате маршрутизатор D скорректирует

свою таблицу маршрутизации и внесет в неё путь до сети N через шлюз C с

метрикой 4 (D-C-D-B-A). Подобная ситуация будет таким образом цикличе-

ски возобновляться снова и снова. Обратите внимание на то, что процесс

зацикливания маршрутов возможен только за счет наличия разницы во вре-

Рисунок 1.15 – Иллюстрация процесса зацикливания маршрутов

Раздел 1. Общие принципы построения компьютерных сетей

мени прихода информации о состоянии сети. Для борьбы с зацикливанием

ограничивают количество допустимых циклов (на практике 15…20).

В процессе маршрутизации возможно возникновение ситуации, когда

периодическое обновление может быть потеряно в сети из-за возникновения

краткосрочной перегрузки или временной неработоспособности канала пе-

редачи данных. Для того, чтобы в этой ситуации маршруты не были оши-

бочно удалены из таблицы, каждому маршруту ставится в соответствие спе-

циальный счетчик времени, который называется timeout – timer. В тот мо-

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

или когда для него приходит очередное обновление значение счетчика

timeout – timer, устанавливается равным T

to max

и этот счетчик начинает об-

ратный отсчет времени. В том случае, если счетчик timeout – timer какого

либо маршрута достигнет значения 0, этот путь должен быть исключен из

числа активных маршрутов. В реальных сетях T

to max

инициируют на 180 с.

Маршрутизация с учетом состояния линий. Недостатки, присущие

дистанционно-векторной маршрутизации, вызваны тем, что узлы имеют

слишком мало информации о топологии всей сети. При учете состояния ли-

ний связи (Link State Routing - LSR) узлы сети располагают информацией о

топологии всей сети и о стоимости связей между ними. Все узлы сети ис-

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

ти SPF (Shortest Path First).

В начале функционирования сети каждый узел формирует группу па-

кетов состояния линий LSA (Link State Advertisements). LSA-пакет содержит

идентификаторы собственного и соседнего узлов, а также стоимость связей

между ними. На следующем шаге пакеты состояния линий рассылаются

широковещательно всем другим узлам сети. Узлы, получившие LSA-пакеты

от всех маршрутизаторов сети, параллельно друг с другом создают тополо-

гическую базу данных, содержащую все LSA-сообщения. На основе полу-

ченной информации узлы рассчитывают пути с минимальными стоимостя-

ми. При этом маршрутизатор рассчитывает топологию кратчайших путей в

виде SPF-дерева, помещая себя в корень. Всякий раз, когда LSA-пакет вызы-

вает изменение в базе данных состояния каналов, алгоритм учета состояний

линий пересчитывает пути и обновляет таблицу маршрутизации.

Алгоритм SPF гарантирует правильное функционирование сети при

нарушениях связи или выходе из строя отдельных маршрутизаторов и ис-

ключает возможность двукратной передачи пакета по одному и тому же пу-

ти. К алгоритмам, использующим знания о топологии всей сети и учиты-

вающим стоимости связей между всеми ее узлами, относится алгоритм

Дийкстры (Dijkstra's algorithm). С помощью этого алгоритма находятся

кратчайшие маршруты от данного узла-источника до всех остальных узлов

сети.

Компьютерные сети

На основании алгоритма Дийкстры определяются оптимальные пути

от заданного узла-источника до всех остальных узлов сети в процессе пере-

бора маршрутов в порядке увеличения их длин. Построение путей происхо-

дит поэтапно. На l-м шаге находятся l путей с минимальной стоимостью к l

узлам.

Для формального определения алгоритма введем следующие обозна-

чения: N

– множество узлов сети; s– узел-источник; T

– множество узлов,

уже обработанных алгоритмом; w(i,j) – стоимость пути от узла i до узла j,

которая при начальной инициализации устанавливается w(i,i)=0 или

w(i,j)=



, если эти узлы не являются смежными и w(i,j)  0, если узлы i и j

непосредственно соединены между собой; L(k) – стоимость оптимального

пути от узла s до узла k.

Алгоритм содержит 3 шага. Шаги 2 и 3 циклически повторятся до тех

пор, пока для всех вершин сети не будут определены оптимальные пути, т.е.

пока множество T

на совпадет с множеством N

1. Произвести начальную инициализацию.

= {s}, это означает, что в множество исследованных узлов включен

только исходный узел-источник;

L(k) = w(s,k) для k



s, т.е. стоимости начальных путей к соседним уз-

лам состоят пока что только из узла-источника.

2. Найти следующий узел.

Осуществляется поиск следующего узла х графа сети, не входящего в

множество Т

и имеющего путь с минимальной стоимостью от этого узла до

узла-источника s. Производится включение найденного узла в множество Т

и соединение его с узлом множества Т

, т.е. выполняется операция

.)(min)( jLxL

Tj



3. Модифицировать путь с минимальной стоимостью. Обновление пу-

ти осуществляется на основании вычислений по следующей формуле:

L(k) = min [L(k), L(x) + w(x,k)] для всех k T

Шаги 2–3 повторяются до тех пор, пока все узлы сети не будут включены в

множество Т

На каждой итерации к множеству Т

добавляется новый узел х, а зна-

чение L(х) на этот момент времени представляет собой минимальную стои-

мость пути от узла-источника s до узла х. Путь с наименьшей стоимостью

должен проходить только через узлы, уже входящие в множество Т

. Сле-

дует заметить, что на первой итерации узел х должен быть связан с источни-

ком напрямую. Второй, добавляемый в множество Т

узел, должен быть свя-

Раздел 1. Общие принципы построения компьютерных сетей

зан напрямую либо с узлом-источником, либо с узлом, уже добавленным к

множеству Т

. На последующих шагах значение путей с наименьшей стои-

мостью обновляется только для узлов, еще не включенных в множество Т

На рисунке 1.15 приведена иллюстрация этапов процесса построения

кратчайших путей от узла А к остальным узлам сети, изображенной на ри-

сунке 1.15,а.

В настоящее время наиболее широко используемые протоколы мар-

шрутизации в сети Internet – это RIP (Routing Information Protocol) и его

усовершенствованная версия RIP 2, а также OSPF (Open Shortest Path First).

Протокол RIP основан на алгоритме Беллмана-Форда и применяется пре-

имущественно на нижних уровнях иерархии. Хотя алгоритм Беллмана-

Форда сходится медленно, однако для сетей сравнительно небольших мас-

штабов он вполне приемлем.

В больших сетях лучше себя зарекомендовал алгоритм OSPF, осно-

ванный на использовании в каждом маршрутизаторе информации о состоя-

нии всей сети. OSPF – алгоритм динамической маршрутизации, в котором

информация о любом изменении в сети рассылается лавинообразно. При

этом каждый маршрутизатор считает себя исходной точкой и строит опти-

мальный путь до всех известных ему сетей. В основе OSPF лежит алгоритм

Дийкстры – поиска кратчайшего пути в графах.

Рисунок 1.15 – Иллюстрация работы алгоритма Дийкстры

Компьютерные сети

1.5. Управление потоками и сигнализация в коммуникационных сетях

1.5.1. Перегрузки в сетях

Цель процедуры управления потоками в сети – исключение явления

перегрузки сети. Под перегрузкой понимается снижение производительно-

сти сети при чрезмерном повышении интенсивности входного потока. Наи-

более серьезно сказываются последствия перегрузки для сетей, работающих

в дейтаграммном режиме. Возникновение этого явления связано либо с не-

достаточной пропускной способностью узла или сети в целом, либо с неэф-

фективным распределением сетевых ресурсов (каналов, памяти, оборудова-

ния) между отдельными абонентскими потоками.

На сетевом узле имеется множество портов ввода-вывода для подклю-

чения оконечных пользователей и несколько портов, связывающих его с

другими узлами сети. Для каждого порта выделяется по два буфера памяти,

один для приема поступающих пакетов, а другой – для хранения пакетов,

ожидающих отправки (рисунок 1.17). Входные и выходные буферы имеют

ограниченную емкость.

Пакеты, ожидающие отправки, образуют очередь. Основная причина

возникновения перегрузок в сети – это превышение скорости поступления

информации над скоростью ее вывода, что при ограниченной емкости запо-

минающих устройств приводит к переполнению буферов хранения в узлах

связи и при определенных условиях – к блокировке (отказу функциониро-

вания) некоторых узлов или всей сети в целом. По причине перегрузки сети

происходит существенное ухудшение основных ее характеристик – времени

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

случае – к отказу узла или сети. Возникновение перегрузки объясняется

Рисунок 1.17 – Схема связей сетевого узла

Раздел 1. Общие принципы построения компьютерных сетей

следующим образом. В нормальных условиях работы сети время передачи

пакета через сеть определяется в основном временем передачи по каналу

связи между источником и адресатом. Время ожидания в очередях на обра-

ботку и передачу в узлах незначительно по сравнению со временем переда-

чи по каналам. Однако по мере роста числа пакетов, циркулирующих в сети,

при возникновении перегрузки время ожидания в очередях возрастает, и

это приводит к увеличению задержки и росту числа пакетов, находящихся в

сети.

В некоторых узлах может возникнуть переполнение буферных уст-

ройств, а это обуславливает многократное повторение передачи одних и тех

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

за переполнения памяти. В результате может возникнуть блокировка от-

дельных групп узлов или всей сети в целом, которая в определенных усло-

виях не снимается сама по себе при уменьшении входного потока. Причи-

ной блокировки является полная загрузка буферных устройств, например,

пары узлов, которые имеют информацию один для другого. Каждый из этих

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

ний не принимает их из-за отсутствия места в буферной памяти. Чтобы раз-

блокировать такую систему, необходимо, например, стереть хотя бы один

пакет в памяти одного из узлов, чтобы появилась возможность начать вза-

имную передачу.

Другой причиной блокировки может служить перегрузка памяти вы-

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

ки вызвана тем, что в сетях с коммутацией пакетов длинные сообщения во

входных узлах разбиваются на короткие пакеты, которые перемещаются по

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

нечном узле из последовательности пакетов собирается исходное сообще-

ние, выдаваемое получателю в целом виде. Для сборки каждого сообщения

в выходном узле резервируется определенный объем памяти, освобождае-

мый лишь после получения всех необходимых пакетов и выдачи собранного

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

новременно собираться в узле, ограничено, то не исключается ситуация, ко-

гда узел оказывается переполнен пакетами. Возникшая блокировка узлов

получила название "блокировка сборки".

На основании рассмотренных ситуаций можно сделать вывод, что при

отсутствии эффективных мер ограничения нагрузки происходит уменьше-

ние производительности всей сети в целом или ее отдельных участков. Пе-

регрузка – это ключевая проблема, которую необходимо решать на этапе

проектирования компьютерных сетей с коммутацией пакетов, ретрансляци-

ей кадров, а также объединенных сетей.

Компьютерные сети

В сетях с виртуальным соединением проблема контроля входной на-

грузки является не такой острой, так как для отдельного потока резервиру-

ется не только маршрут, но и сетевые ресурсы, включая буферную память

на узлах коммутации и у потребителя, а также пропускную способность ка-

нала связи.

При выявлении перегрузки узла последний обычно посылает специ-

альное служебное уведомление источнику, сигнализирующее о перегрузке.

Получив пакет с подобной индикацией, отправитель снижает интенсивность

выходного потока данных. Обнаружение явления перегрузки в сети может

производиться и по косвенным признакам, т.е. неявным способом. При этом

используется тот факт, что при наличии перегрузок в сети увеличивается

время задержки доставки пакетов, а также возрастает количество пропав-

ших (отброшенных) пакетов. Если отправитель в состоянии обнаружить

возрастание времени доставки сообщения и явление сброса пакетов, то он

может самостоятельно принять решение о снижении скорости передачи. Та-

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

оконечный узел, а от сетевых узлов не требуется никаких действий.

1.5.2. Методы защиты от перегрузок

Для защиты компьютерных сетей от перегрузок необходимо осущест-

влять контроль перегрузок как между узлами сети так и между отправите-

лем и получателем. Контроль перегрузок между узлами должен обеспечи-

вать согласование пропускных способностей узлов, чтобы в процессе пере-

дачи не возникали такие потоки пакетов, с которыми не справляются узлы.

На уровне "отправитель-получатель" необходимо следить за тем, чтобы

информация не накапливалась во входных буферах компьютера-получателя,

а достаточно быстро использовалась в процессах обработки, выполняемых в

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

процесс передачи данных будет согласован с процессами обработки на пе-

редающей и принимающих ЭВМ.

Методы борьбы с перегрузкой подразделяются на локальные и гло-

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

сети осуществляются с учетом информации, имеющейся на данном узле или

получаемой от соседних узлов. В глобальных методах используется инфор-

мация о состоянии всей сети в целом.

В локальных методах широко применяются резервирование буферов,

посылка сдерживающих пакетов, адаптивная маршрутизация, а в ряде

случаев также неявная сигнализация о перегрузке.