Сетевое администрирование ПМИТ

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

показанной на рис. 4.11, в (в предположении, что предел счетчика

сегментов равен 3), то было бы передано 10 пакетов, по сравнению с 8 пакетами, передаваемыми схемой передачи по обратному маршруту.

Рис. 4.11. Широковещательная маршрутизация: а) лавинная передача; б) схема, основанная на дереве; в) передача по обратному маршруту.

4.6. Управление потоками данных

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

специальные пакеты ("заглушки") всякий раз, когда нагрузка на этот узел достигает определенного уровня. Эти пакеты инструктируют источник

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

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

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

использования (utilization) или рассматривая заполнение очереди. Чтобы контролировать параметр использования звена (U), можно

воспользоваться следующим выражением:

Где f— параметр мгновенного использования линии (то есть f= 1, если

линия

занята, или f= 0, если — не занята); a — постоянная, которая определяет, как

быстро узел забывает предысторию; Un— новая, а Un-1— предыдущая

оценка среднего значения параметра использования. Эффективность этого

81

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

системы.

Управление потоками данных может применяться как к дейтаграммным или виртуальным каналам, так и при сквозном(point-to-point) и поэлементном

(link-by-link) подходе к сетевым системам. Поэтому можно иметь механизм,

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

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

4.7. Защита от ошибок

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

систему,

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

Скрытие ошибок. По этой методике выполняется обнаружение

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

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

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

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

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

Автоматический запрос повторения передачи (Automatic Repetition Query, RQ). Как и в предыдущем случае, выполняется

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

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

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

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

Упреждающая (прямая) коррекция ошибок (Forward Error Correction, FEC). В этом случае к посылаемому сообщению добавляются

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

вычислительном отношении FEC-методика сложна и требует

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

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

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

82

Можно использовать комбинации этих стратегий, пытаясь применить сначала FEC на каждом уровне, а затем используя ARQ или скрытие ошибок,

если FEC-методика терпит неудачу. Методика скрытия ошибок может

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

является ARQ.

4.8. Обнаружение ошибок

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

который прибыл в приемник, может пострадать от одной или нескольких ошибок. Во вторых, кадр может вообще не прибыть в приемник. От второй

проблемы можно защититься, включая в каждый кадр порядковый номер. Если кадр с конкретным порядковым номером не прибывает, то он

считается потерянным. Обнаружение ошибок — более сложная задача. Передатчик вычисляет по сообщению некоторую функцию и добавляет

результат ее вычисления к кадру в виде проверочной последовательности кадра (Frame Check Sequence, FCS). Когда приемник получает кадр, он

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

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

сообщении	произошли	какие-то	изменения,
следовательно обнаружена ошибка (рис. 4.12).

Рис. 4.12. Проверочная последовательность кадра

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

Например, если функция состоит в простом добавлении к кадру 16- разрядного слова, как в пакете UDP1, и если одна ошибка добавляет к этому

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

1 UDP — сокр. от User Data Protocol, пользовательский протокол данных

83

циклического избыточного кода, CRC. Обычно используется 16-разрядный

CRC-код, определенный комиссией CCITT, который может обнаруживать:

все пачки ошибок длиной до 16 битов, где пачка определяется как блок,

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

99,997% пачек длиной 17 битов;

99,998 % пачек длиной больше, чем 17 битов;

все возможные комбинации 3-х или меньшего количества случайных

ошибок;

все возможные комбинации нечетного количества ошибок.

4.9. ARQ

Существует три типа ARQ — с остановом и ожиданием, с возвратом N

кадров и с избирательным повторением. Самая простая форма этой

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

назад к источнику (рис. 4.13). Источник не передает следующее

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

предыдущего. В это время передатчик находится в состоянии ожидания, что и объясняет происхождение

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

ничего "не услышит" от адресата за это время, то он снова передает это же сообщение.

Рис.4.13. ARQ с

остановом и ожиданием

Коэффициент использования (utilisation) канала определяется как доля времени активности канала. Если кадр состоит из h битов заголовка и т

битов сообщения, подтверждение содержит а битов, скорость передачи канала — В бит/с, а задержка распространения (время, которое требуется для перехода сообщения от передатчика к приемнику) равна , то в идеальном, свободном от ошибок, звене потребуется (h + т)/В + секунд, для того чтобы

кадр достиг приемника. Затем приемник подтвердит получение этого кадра, посылая подтверждение, которое будет получено источником кадра через а/В

84

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

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

В течение этого периода передается m битов сообщения, так что

полезное время равно т/В. Коэффициент использования равен отношению

полезного времени (то есть времени передачи информационных битов т/B к

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

высокой

степени

использования

канала

требуется,

чтобызаголовок и подтверждение были короткими, а время распространения — небольшим. Для преодоления неэффективности ARQ с

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

подтверждений (ASK-сообщений2). Для числа3 кадров, ожидающих

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

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

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

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

пространства.

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

использовать тайм-аут (как в ARQ с остановом и ожиданием). Если подтверждение не было своевременно получено, то интервал тайм-аута

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

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

последовательности.

Существуют два режима повторной передачи: или передатчик передает

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

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

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

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

2АСК — сокр. от acknowledgement (подтверждение)

3Это число называют окном (window).

85

уровень должен правильно буферизовать полученные кадры во время ожидания повторно передаваемых кадров.

В схеме с возвратом N кадров, передатчик "возвращается назад" к потерянному кадру и от этой точки снова посылает все кадры. Преимущество этого подхода состоит в том, что в приемнике не требуется буферизации или

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

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

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

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

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

В системе с возвратом N кадров для определения того момента, когда

произошла ошибка или когда были приняты дубликаты кадра, приемник

проверяет порядковые номера кадров. Если был получен правильный кадр с порядковым номером N, то следующий полученный кадр должен иметь номер N+ 1. Если номер следующего принятого кадра равен N + 2, то кадр с

номером N+ 1 считается потерянным.

В протоколах со скользящим окном роль порядковых номеров является

решающей. Когда передается кадр, ему приписывается номер, который определяет порядок его вывода по отношению к другим кадрам. Эти номера

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

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

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

окна размером К кадров, диапазон требуемых порядковых номеров простирается от 0 до 2К+1 для системы, использующей избирательную повторную передачу, и от 0 до К+1 — для систем с возвратом N кадров. Для

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

размером в 3 или 8 разрядов. Вычисление коэффициента использования (р) для протоколовсо скользящимокномнесколько сложнее. Здесь различают два

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

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

позволяющую одновременно передавать несколько кадров.

86

Пусть на передачу кадра затрачиваетсясекунд, а на прием подтверждения— секунд. Это означает, что при ожидании

подтверждения
можно передавать	кадров. Если размер окна на 1 (или

на еще большую величину) больше, чем это значение, то возможна

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

как m/(h +m). Дополнительная единица в этом условии появляется из-за

начального кадра, для которого было получено подтверждение. В случае небольшого окна его размер (W) удовлетворяет следующему соотношению:

За каждый временной интервал размером в секунд можно передать W кадров, так что эффективность свободнойот ошибок передачи

возрастает (в формуле ее вычисления появляется множитель

Поэтому в канале с малым окном эффективность можно вычислять по формуле

где W— размер окна для случая ARQ с остановом и ожиданием.

На рис. 4.14 показаны схемы работы ARQ различных типов. В каждом

случае

канал страдает от ошибок в одной и той же точке. Для ARQ с остановом и

ожиданием (рис. 4.14, а) 1, 2 и 3-й блоки передаются и принимаются

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

4-е сообщение искажено ошибками и имеет отрицательное подтверждение, поэтому оно передается повторно. Для случая ARQ с возвратом N кадров

(рис. 4.14, б) первый пакет ошибок искажает 2-й блок сообщения, но

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

передавая за это время 3-й и 4-й блоки сообщения. После этого источник должен вернуться ко 2-му блоку и передать его снова. В таком случае величина должна быть равной 3 или больше. Если бы N было равно только 2,

источник должен был бы остановиться после передачи блока 3 до тех пор, пока не будет принято подтверждение приема блока 2. В системе ARQ с

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

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

только с 7 или 5 блоками.

Если в блоке есть ошибки, то его нужно передавать повторно. Поэтому

для

87

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

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

что заголовок имеет минимальный размер).

Коэффициент использования для ARQ с остановом и ожиданием при

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

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

2t + а/В (время, которое обычно требуется для возврата подтверждения). В

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

независимо от того возникает ошибка или нет. Пусть Рf— вероятность

потери кадра, а Ра — вероятность потери подтверждения. Вероятность

правильного		приема		кадра
		Поэтому полезная пропускная способность (в кадрах)
равнаm x Р„	а	коэффициент	использования	вычисляется
как

Подобный подход можно использовать и для ARQ с избирательным

повторением передачи, если допустить некоторое упрощение, состоящее в том, что повторные передачи потерянных пакетов — это еще не сами потери,

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

интенсивности ошибок. В таком случае коэффициент использования свободной от ошибок передачи равен Р„ так что для случая большого окна

он становится равным mPs(h + m), а для случая малого окна — равным mWPs(h + m + a + 2B ).

88

Рис. 4.14. Работа различных типов ARQ

К сожалению, мы не можем прямо применять этот подход для ARQ с

возвратом N кадров, потому что в дополнение к тому, что нужно снова посылать более одного кадра (N кадров в случае большого окна и W кадров

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

состоящее в том, что этого не случится, то каждый потерянный кадр приведет к повторной передаче N или W кадров. Среднее число передач, требуемых

для того, чтобы получить успешно переданный кадр, равно 1/PS. Средне число повторных передач на 1 меньше, чем эта величина, т. е. 1/Ps—1, так что

общее количество переданных кадров будет равно (1/Ps—)N+l для большого окна или (1/Ps—1)W+1 — для малого. Из-за этого множителя коэффициент

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

— для малого окна

На рис. 4.15 показаны графики относительной производительности

схем

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

системы со скоростью передачи 1 Мбит/с, 40-разрядным заголовком и 40-

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

89

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

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

Вероятность появления ошибочного бита на передаваемых данных или на их подтверждении равна 10-4.

Рис. 4.15. Относительная производительность схем ARQ:

1- с остановом и ожиданием (задержка 10 мс.); 2- с остановом и ожиданием (задержка 10 мкс.);

3- с избирательным повторением (оба случая).

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

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

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

правой стороне кривых (см. рис. 4.3) этот фактор начинает доминировать. Например, при интенсивности побитовых ошибок 10-4 только около трети

пакетов размером в 10 000 битов будут приняты правильно. Лучше всех

работает ARQ с избирательным повторением, и это справедливо всегда.

Для пакетов больших размеров (и поэтому с большой интенсивностью

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

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

возвратом N кадров приближается к производительности ARQ с

избирательным повторением, а при высокой интенсивности ошибок — к производительности ARQ с остановом и ожиданием. В силу того, что на

90