Глава 7. Алгоритмы сети Ethernet-Fast Ethernet (537692), страница 2
Текст из файла (страница 2)
Рис. 7.2. Зависимость показателя использования сети от времени при линейном увеличении предложенной нагрузки (1 - наилучшая область работы, 2 - приемлемая, 3 - плохая)
Некоторые авторы предлагают использовать для широко распространенного понятия «перегрузка» (overload) сетей на основе метода доступа CSMA/CD следующее определение: сеть перегружена, если она не может работать при полной нагрузке в течении не менее 80% своего времени (предполагается, что при этом в течении не менее 20% времени показатель использования сети недопустимо мал из-за коллизий). После точки насыщения наступает крах Ethernet (Ethernet collapse), когда возрастающая предложенная нагрузка заметно превышает возможности сети.
Стоит заметить, что реально маловероятно, чтобы предложенная нагрузка постоянно увеличивалась во времени и надолго превышала пропускную способность сети типа Fast Ethernet. Более того, любой детерминированный метод доступа не может обеспечить реализацию сколь угодно большой предложенной нагрузки, существующей продолжительное время. Если данный вариант детерминированного метода доступа не предусматривает, как и метод CSMA/CD, систему приоритетов, то никакой из абонентов не может захватить сеть более чем на время передачи одного пакета, однако передача данных отдельными пакетами с долгими паузами между ними ведет к снижению скорости передачи для каждого абонента. Однако преимущество детерминированных методов состоит в возможности простой организации системы приоритетов, что полезно из-за существования определенной иерархии в любом крупном коллективе.
7.2. Использование помехоустойчивых кодов для обнаружения ошибок в сети
Сигналы, непосредственно передаваемые по последовательным линиям (типа витой пары, коаксиального кабеля или телефонной линии), подвержены влиянию ряда факторов, воздействие которых может привести к возникновению ошибок в принятой информации. Ошибки могут возникать вследствие влияния на канал связи наводок и помех естественного или искусственного происхождения, а также вследствие изменения конфигурации системы передачи информации с временным нарушением или без нарушения целостности канала связи (например, в случае подключения новых абонентов к существующей локальной информационной сети).
Некоторые из ошибок могут быть обнаружены на основании анализа вида принятого сигнала, так как в нем появляются характерные искажения. Примером может служить код Манчестер-П, используемый в сетях Ethernet. На передающем конце линии этот код обязательно содержит переход с низкого электрического уровня на высокий или обратно в середине каждого тактового интервала, требуемого для передачи одного бита информации. Он также имеет среднюю составляющую, близкую к нулю. Эти свойства кода Манчестер-П могут использоваться для обнаружения разного рода ошибок. В частности, отличие средней составляющей сигнала от нуля является одним из признаков возникновения коллизий (наложений пакетов от разных абонентов), характерных для метода доступа CSMA/CD в сетях типа Ethernet. Однако сколько-нибудь серьезную систему обнаружения ошибок, вызванных воздействием помех с непредсказуемым поведением, на этой основе построить невозможно.
Стандартные протоколы обмена информации в сетях предусматривают введение обязательного поля для размещения помехоустойчивого (корректирующего) кода. Если в результате обработки принятого пакета обнаружится несоответствие принятого и вновь вычисленного помехоустойчивого кода, с большой долей вероятности можно утверждать, что среди принятых бит имеются ошибочные. Передачу такого пакета нужно будет повторить (в расчете на случайный характер помех).
7.2.1. Способы снижения числа ошибок в принятой информации
Имеется разрыв между требованиями к верности принимаемой информации и возможностями существующих каналов связи. В частности, стандартами международных организаций МККТТ и МОС установлено, что вероятность ошибки при телеграфной связи не должна превышать 3 • 10"5 (на знак), а при передаче данных - 10~6 (на единичный элемент, бит). На практике допустимая вероятность ошибки при передаче данных может быть еще меньше - 10~9. В то же время существующие каналы связи (особенно каналы большой протяженности и протяженные радиоканалы) обеспечивают вероятность ошибки на уровне 10~3...10"4 даже при использовании фазовых корректоров, регенеративных ретрансляторов и других устройств, улучшающих качество каналов связи.
Кардинальным способом снижения вероятности ошибок при приеме является введение избыточности в передаваемую информацию. В системах передачи информации без обратной связи данный способ реализуется в виде помехоустойчивого кодирования, многократной передачи информации или одновременной передачи информации по нескольким параллельно работающим каналам. Помехоустойчивое кодирование доступнее и при прочих равных условиях позволяет обойтись меньшей избыточностью и за счет этого повысить скорость передачи информации.
7.2.2. Характеристики и разновидности помехоустойчивых кодов
Помехоустойчивое кодирование предполагает введение в передаваемое сообщение, наряду с информационными, так называемых проверочных разрядов, формируемых в устройствах защиты от ошибок (кодерах-на передающем конце, декодерах — на приемном). Избыточность позволяет отличить разрешенную и запрещенную (искаженную за счет ошибок) комбинации при приеме, иначе одна разрешенная комбинация переходила бы в другую.
Помехоустойчивый код характеризуется тройкой чисел (n, k, d0), где n— общее число разрядов в передаваемом сообщении, включая проверочные (г), k=n-r - число информационных разрядов, d0— минимальное кодовое расстояние между разрешенными кодовыми комбинациями, определяемое как минимальное число различающихся бит в этих комбинациях. Число обнаруживаемых (tj и (или) исправляемых (t ) ошибок (разрядов) связано с параметром d0 соотношениями
Иногда используются дополнительные показатели избыточности, производные от приведенных выше характеристик n, k:R = r/n- относительная избыточность, v = k / n - относительная скорость передачи.
Существующие помехоустойчивые коды можно разделить на ряд групп, только часть из которых используется для обнаружения ошибок в передаваемых по сети пакетах (на рис. 7.3 используемые для этой цели группы выделены утолщенными стрелками). В группе систематических (линейных) кодов общим свойством является то, что любая разрешенная комбинация может быть получена в результате линейных операций над линейно-независимыми векторами. Это способствует упрощению аппаратной и программной реализации данных кодов, повышает скорость выполнения необходимых операций.
Рис. 7.3. Классификация помехоустойчивых кодов
Простейшими систематическими кодами являются биты четности/нечетности. Они не позволяют обнаружить ошибки четной кратности (т.е. ошибки одновременно в двух, четырех и т.д. битах) и поэтому используются при невысоких требованиях к верности принимаемых данных (или при малой вероятности ошибок в линии передачи). Примером может служить бит Parity (соответствие) в установках режимов работы последовательного порта с помощью команды MODE (MS DOS). Несмотря на ограниченные возможности обнаружения ошибок, биты четности/нечетности имеют большое значение в теории помехоустойчивого кодирования. Одни иг первых математически обоснованных и практически использовании? помехоустойчивых кодов - коды Хэмминга представляют собой простс совокупность перекрестных проверок на четность/нечетность. Циклические коды могут рассматриваться как обобщенные проверки на четность/ нечетность (см. далее).
7.2.3. Циклические коды (CRC)
Циклические коды - это целое семейство помехоустойчивых кодов, вклю чающее в себя в качестве одной из разновидностей коды Хэмминга, но : целом обеспечивающее большую гибкость с точки зрения возможност] реализации кодов с необходимой способностью обнаружения и исправ ления ошибок, определяемой параметром d0, по сравнению с кодами Хэм минга (для которых dQ=3 или d0=4). Широкое использование цикличес ких кодов на практике обусловлено также простотой реализаци соответствующих кодеров и декодеров.
Основные свойства и само название циклических кодов связаны с те!\ что все разрешенные комбинации бит в передаваемом сообщении (коде вые слова) могут быть получены путем операции циклического сдвиг некоторого исходного кодового слова:
Циклические коды задаются с помощью так называемых порождающр полиномов (многочленов) g(x) или их корней. Кроме того, вводятся понятия полинома исходного сообщения
Для этих полиномов, представляющих собой, по существу, альтерната ную запись чисел в двоичной системе счисления, определяются опер ции сложения, умножения и деления, необходимые для организации i
дирования н декодирования сообщения. Все эти операции выполняются по модулю 2.
Рассмотрим последовательность кодирования на примере циклического кода (7,4,3), имеющего g(x) = х3 + х + 1:
1) информационная часть сообщения записывается в виде полинома:
В рассматриваемом примере k = 4 и для сообщения 0111 получаем
2) и(х) умножается хг, что соответствует циклическому сдвигу исходного сообщения на г разрядов влево:
3) полученный многочлен делится на g(x):
где с(х)-полином - частное с максимальной степенью (k-1); R(x)-полином - остаток с максимальной степенью (г-1); © - обозначение поразрядной операции суммирования по модулю 2 (исключающее ИЛИ).
Кодированное сообщение представляется в виде
то есть на месте младших, освобожденных после домножения на хг, разрядов, записываются проверочные разряды.
Для рассматриваемого примера:
Таким образом, в данном случае А(х) = (х3 + х4 + х3) © х = х5 + х4 + х3 + х. Передаваемое кодированное сообщение в обычной двоичной форме имеет вид:
Один из возможных вариантов аппаратурной реализации кодера для рассматриваемого примера представлен на рис. 7.4 вместе с последовательностью сигналов, подтверждающей получение тех же самых проверочных разрядов (010) на восьмом такте (г + k + 1 = 8).
Кодер представляет собой сдвиговый регистр с обратными связями, организуемыми с помощью элементов М2 (исключающее ИЛИ, сумматор по модулю 2). Структура обратных связей полностью определяется ненулевыми коэффициентами порождающего полинома g(x).
Рис. 7.4. Пример формирования циклического кода (сигнал обратной связи отличен от нуля на 5-м и б-м тактах)
На первых восьми тактах ключ Кл. находится в верхнем положении и формируются проверочные разряды. Затем ключ Кл. устанавливается в
нижнее положение, что соответствует разрыву цепей обратных связей и передаче непосредственно в канал связи или на модулятор проверочных разрядов. Для временного хранения информационной части сообщения с целью последующей ее передачи вместе с проверочными разрядами кодер, очевидно, должен быть дополнен сдвиговым регистром длиной в k разрядов, ключами и соответствующими цепями управления. Однако, в целом, аппаратурные затраты при реализации кодеров в случае циклических кодов невелики - общее число триггеров и элементов М2 (исключая регистр временного хранения информационной части сообщения) не превышает 2 г и не зависит от длины информационной части сообщения.
Двухвходовый элемент М2, на один из входов которого подается в последовательной форме сообщение, на выходе формирует бит четности или нечетности (в зависимости от значения сигнала на втором входе элемента М2 - 0 или 1) для этого сообщения. В схеме кодера (рис. 7.4) элементы М2 включены между отдельными триггерами сдвигового регистра, причем сигналы обратной связи, поступающие на «свободные» входы элементов М2 (не связанные с передачей собственно сообщения через сдвиговый регистр), зависят как от предшествующих разрядов сообщения, так и от структуры обратных связей, принятой в кодере. В результате циклический код, формируемый таким кодером, можно считать совокупностью обобщенных бит четности и нечетности, тип которых (четность или нечетность) не определен заранее и может динамически меняться от такта к такту.
Порождающие полиномы, представляющие собой т. н. неприводимые многочлены (многочлены, которые делятся лишь на единицу и на самих себя), табулированы для разных значений n, k и dQ, например, п = 7...255, k = 3...247, d0= 3...127. Практически в компьютерных сетях используются циклические коды длиною в 2 или 4 байта (16 или 32 бита), а параметры п, k и d0 в явном виде не указываются. Это связано с возможностью выбора различной длины поля данных в пакете на этапе установления и выбора параметров соединения при неизменной длине поля циклического кода. Теоретическая вероятность ошибки при приеме в случае использования циклического кода не хуже рощ < 1/2г, так что для выполнения условия стандарта рош < 10"6 необходимое число проверочных разрядов г > Iog2106 = 20. Кроме случайно распределенных, циклический код позволяет обнаруживать подряд следующие ошибки (так называемые пакеты ошибок) длиною 1 = г или меньше. Это особенно важно в связи с возможностью возникновения продолжительных во времени помех, действующих на протяженные линии передачи в компьютерных сетях.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
