tanenbaum_seti_all.pages (525408), страница 61
Текст из файла (страница 61)
В этом случае принимающая сторона его просто не получит и, соответственно, никак не прореагирует, а отправитель может вечно ожидать положытелыюго или.отрицательного ответа и так ничего и не получить. Чтобы избежать зависаний сети в случае полной потери кадров, используются таймеры уровня передачи данных. После посылки кадра включается таймер н отсчитывает интервал времени, достаточный для получения принимающим компьютером этого кадра, его обработки и посылки обратно подтверждения.
В нормальной ситуации кадр правильно принимается, а подтверждение посылается назад и вручается отправителю, прежде чем истечет установленный интервал времени, и только после этого таймер отключается. Однако если либо кадр либо подтверждение теряется по пути, установленный интервал времени истечет, и отправитель получит сообщение о возможной проблеме, Самым простым решением для отправителя будет послать кадр еще раз. Однако при этом возникает опасность получения одного и того же кадра несколько раз уровнем передачи данных принимающего компьютера и повторной передачи его сетевому уровню.
Чтобы атого не случилось, необходимо последовательно пронумеровать отсылаемые кадры, так чтобы получатель мог отличить повторно переданные кадры от оригиналов. Вопрос управления таймерами и порядковыми номерами, гарантирующими, что каждый капр доставлен сетевому уровню принимающего компьютера ровно один раз, не болыне и нс меньше, является очень важной частью задачи, решаемой уровнем передачи данных. Далее в этой главе мы подробно изучим методы управления на серии постепенно усложняющихся примеров. Управление потоком Еще один важный аспект разработки уровня передачи данных (а также более высоких уровней) связан с вопросом о том, что делать с отправителем, который постоянно желает передавать кадры быстрее, чем получатель способен их получать. Такая ситуация может возникнуть, если у псрсдаюгцей стороны оказывается более мощный (илн менее загруженный) компьютер, чем у принимающей.
Отправитель продолжает посылать кадры на высокой скорости до тех пор, пока получатель не окажется полностью ими завален. Даже прн идеально работающей линии связи в определенный момент получатель просто не сможет продолжать обработку все прибывающих кадров и начнет их терять. Очевидно, что для предотвращения подобной ситуации следует что-то предпринять. 232 Глава 3. Уровень передачи данных В настоящее время примеыяются два подхода. При первом, называющемся управлением потоком с обратной связью, получатель отсылает отправителю информацию, разрешающую последнему продолжить передачу или, по крайней мере, сообщающую о том, как идут дела у получателя. При втором подходе, управлеиии потоком с ограиичеиием, в протокол встраивается механизм, ограничивающий скорость, с которой передатчики могут передавать данные.
Обратная связь с получателем отсутствует. В этой главе мы рассмотрим только подход с обратиой связью, поскольку второй подход никогда ие применяется иа уровне передачи данных (впрочем, мы вернемся к нему в главе 5), Известны различные схемы коптроля потока с обратной связью, ио большииство из иих используют олин и тот же принцип. Протокол содержит четко определениые правила, определяющие, когда отправитель может посылать следующий кадр. Эти правила часто запрещают пересылку кадра до тех пор, пока получатель ие даст разрсшсш1я, либо явно, либо неявно.
Например, при установке соединения получатель может сказать: «Вы можете послать мне сейчас п кадров, по ие посылайте следующие кадры, пока я ие попрошу вас продолжать». Вдациой главе мы рассмотрим различные мсхаиизмы, основанные иа этом принципе. Обнаружение и исправление ошибок Как было показано в главе 2, телефонная система состоит из трех частей — коммутаторов, межкоммутаториых магистралей и местных телефонных линий.
Первые две части являются сегодня почти полностью цифровыми. Местные телефоииые линии до сих пор представляют собой аналоговые медные витые пары и останутся такими еьце в течение нескольких лет, поскольку их замена стоит очень дорого. И хотя в цифровой части телефонной системы ошибки случаются редко, в местных телефонных линиях вероятность ошибки очень велика. Кроме того, впоследнее время все большее распростраиеиие получает беспроводиая связь, в которой уровень ошибок ца несколько порядков выше, чем в соединяющих телефоипые станции магистралях. Отсюда следует вывод; ошибки при передаче даииых останутся важным фактором еще иа долгие годы.
Сейчас мы приступаем к изучению метолов их обнаружения и устранения. Вследствие особенностей физических процессов, порождающих пх, ошибки в искоторых типах носителей (иапример, радио) чаще бывают це единичными, а групповыми. В этом есть как положительные, так и отрицательиые стороны. Положительиые связаны с тем, что компьютеры всегда посылают даицые битовыми блоками. Представьте себе блок размером в 1000 бит при вероятности ошибки 0,001 ца бит. Если бы ошибки были независимыми, то очень большой процент блоков содержал бы ошибки. Однако если ошибки приходят пакетами, искажая по 100 бит подряд, то из 100 блоков будут испорчены в среднем только один или два.
Неудобством групп ошибок является то, что их значительно труднее исправить, чем изолированные ошибки. Обнаружение и исправление ошибок 23;. Корректирующее кодирование Разработчики сетей создали две основные стратегии для борьбы с ошибками. Ка ждый метод основывается на добавлении к передаваемым данным некоторой из. быточной информации. В одном случае этой информации должно б>ыть достаточно чтобы выявить, какие данные должны были прийти.
В другом случае избыточно( информации должно быть достаточно только для того, чтобы получатель понял что произошла ошибка (без указания ес типа) и запросил повторную передачу Первая стратегия использует колы, называющиеся корректирующими, илп кода. ми с исправлением ошибок. Вторая — код с обнаружением ошибок. Использование кода с обнаружением ошибок часто называют прямым исправлением ошибок. Каждая стратегия занимает свою, так сказать, экологическую нишу.
В высоконадежных каналах, таких как оптоволокно, дешевле использовать код с обнаружением ошибок и просто заново передавать случайные поврежденные блоки. Однако, скажем, беспроводные соединения, в которых можст возникать множество ошибок, чаще используют коды с избыточностью, достаточной для того, чтобы приемник мог определить, какие данные должны были прийти.
Это надежнее, чем полагаться на повторную передачу, которая тоже, возможно, не сможет пройти без ошибок. Чтобы понять, как могут обнаруживаться и исправляться ошибки, необходимо рассмотреть подробнее, что же представляет собой ошибка. Обы шо кадр состоит из л> битов данных (то есть информационных битов) и г избыточных или контрольных битов. Пусть полная длина кадра равна и (то есть и = и + г). Набор из и бит, содержащий информационные и контрольные биты, часто называк>т п-битовым кодовым словом или кодовой комбинацией. Если рассмотреть два кодовых слова, например 10001001 и 10110001, можно определить число различа>ощихся в них соответствующих разрядов.
В данном примере различаются 3 бита. Для нахождения этого числа нужно сложить два кодовых слова по модулю 2 (операция <исключающее или») и сосчитать количсство единиц в результате, напримср: 10001001 10110001 00111000 Количество битов, которыми различаются два кодовых слова, называется кодовым расстоянием, или расстоянием между кодовыми комбинациями в смысле Хэмминга (На>пш1лд, 1950).
Смысл этого числа состоит в том, что если два кодовых слова находятся на кодовом расстоянии Ы, то для преобразования одного кодового слова в другое понадобится Ы ошибок в одиночных битах. В большинстве приложений передачи данных все 2" возможных сообщений являются допустимыми, однако благоларя использованию контрольных битов не все 2" возможных кодовых слов используются. Зная алгоритм формирования контрольных разрядов, можно построить полный список всех допустимых кодовых слов и в атом списке найти такую пару кодовых слов, кодовое расстояние 234 Глава 3. Уровень передачи данных между которыми будет минимальным. Это расстояние называется минимальным кодовым расстоянием кода, или расстоянием всего кода в смысле Хзмминга, Способности кода по обнаружению и исправлению ошибок зависят от его минимального кодового расстояния. Лля обнаружения << ошибок в одном кодовом слове необходим код с минимальным кодовым расстоянием, равным <( ~ 1, поскольку <( однобитовых ошибок не смогут изменить одну допустимую комбинацию так, чтобы получилась другая допустимая комбинация.
Когда приемник встречает запрещенную кодовую комбинацию, он понимает, что при передаче произошла ошибка. Аналогично, для исправления <<' онщбок в одном кодовом слове требуется код с минимальным кодовым расстоянием, равным 2«' <- 1, так как в данном случае даже при <( одпобитовых ошибках результат окажется ближе к исходному кодовому слову, чем к лк~бох<у другому, и, следовательно, его можно будет однозначно восстановить.
В качестве простейшего примера кода с обнаружением ошибок рассмотрим код, в котором к данным добавляется одни бнт четности. Бнт четности выбирается таким образом, чтобы количество единиц во всем кодовом слове было четным (или нечетным). Например, прн посылке числа 10110101 с добавлением бита четности в конце оно становится равным 101101011, тогда как 10110001 преобразуется в 101100010. Код с единственным битом четности имеет кодовое расстояние, равное 2, так как любая однократная ошибка в любом разряде образует кодовое слово с неверной четностью. Такой код может использоваться для обнаружения однократных ошибок, В качестве простейшего примера корректирующего кола рассмотрим код, у которого есть всего четыре допустимые кодовые комбинации: 0000000000, 0000011111, 1111100000 и 1111111111 Этот код имеет расстояние, равное 5, что означает, что он может исправлять двойные ошибки.
Если приемник получит кодовое слово 0000000111, он поймет, что оригинал должен быть равен 0000011111. Однако если тройная ошибка изменит 0000000000 на 0000000111, ошибка будет исправлена неверно. Попробуем создать код, состоящий из т информационных и г контрольных битов, способный исправлять одиночные ошибки. Каждому из 2 допустимых сообщений будет соответствовать п недопустимых кодовых слов, отстоящих от сообщения на расстояние 1. Их можно получить инвертированием каждого из л битов и-битового кодового слова, Таким образом, каждому нз 2 допустимых сообщений должны соответствовать п + 1 кодовых комбинаций, Поскольку общее количество возможных кодовых комбинаций равно 2", получается, что (и+ 1)2 ь 2".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
