Э. Таненбаум - Компьютерные сети. (4-е издание) (PDF) (1130118), страница 58
Текст из файла (страница 58)
В такой схеме каждый передаваемый бит данных содержит в середине переход, благодаря чему упрощается распознавание границбитов. Комбинации уровней сигналов (низкий—низкий и высокий—высокий) неиспользуются для передачи данных, но используются в качестве ограничителейкадров в некоторых протоколах.В заключение разговора о кадрировании заметим, что многие протоколы передачи данных для повышения надежности применяют комбинацию счетчика символов с другим методом формирования кадра. Когда прибывает кадр, для обнаружения его конца используется счетчик. Кадр воспринимается как правильныйтолько в том случае, если соответствующий разделитель присутствует в нужнойпозиции и совпадает контрольная сумма.
В противном случае сканируется входной поток, в котором ищется следующий разделитель.Обработка ошибокРешив проблему маркировки начала и конца кадра, мы сталкиваемся с новойпроблемой: как гарантировать доставку сетевому уровню принимающей машинывсех кадров и при этом расположить их в правильном порядке. Предположим,что отправитель просто посылает кадры, не заботясь о том, дошли ли они до адресата. Этого было бы достаточно для сервиса без подтверждений и без установления соединения, но не для ориентированного на соединение сервиса с подтверждениями.•Ключевые аспекты организации уровня передачи данных231Обычно для гарантирования надежной доставки поставщику посылается информация о том, что происходит на другом конце линии. Протокол требует отполучателя посылать обратно специальные управляющие кадры, содержащие позитивные или негативные сообщения о полученных кадрах.
Получив позитивноесообщение, отправитель узнает, что посланный им кадр успешно получен на томконце линии. Негативное сообщение, напротив, означает, что с кадром что-то случилось и его нужно передать снова.Кроме того, посланный кадр может из-за неисправности оборудования иликакой-нибудь помехи (например, шума) пропасть полностью. В этом случае принимающая сторона его просто не получит и, соответственно, никак не прореагирует, а отправитель может вечно ожидать положительного или .отрицательногоответа и так ничего и не получить.Чтобы избежать зависаний сети в случае полной потери кадров, используются таймеры уровня передачи данных.
После посылки кадра включается таймер иотсчитывает интервал времени, достаточный для получения принимающим компьютером этого кадра, его обработки и посылки обратно подтверждения. В нормальной ситуации кадр правильно принимается, а подтверждение посылается назад и вручается отправителю, прежде чем истечет установленный интервал времени, и только после этого таймер отключается.Однако если либо кадр либо подтверждение теряется по пути, установленный интервал времени истечет, и отправитель получит сообщение о возможнойпроблеме. Самым простым решением для отправителя будет послать кадр ещераз. Однако при этом возникает опасность получения одного и того же кадра несколько раз уровнем передачи данных принимающего компьютера и повторнойпередачи его сетевому уровню. Чтобы этого не случилось, необходимо последовательно пронумеровать отсылаемые кадры, так чтобы получатель мог отличитьповторно переданные кадры от оригиналов.Вопрос управления таймерами и порядковыми номерами, гарантирующими,что каждый кадр доставлен сетевому уровню принимающего компьютера ровноодин раз, не больше и не меньше, является очень важной частью задачи, решаемой уровнем передачи данных.
Далее в этой главе мы подробно изучим методыуправления на серии постепенно усложняющихся примеров.Управление потокомЕще один важный аспект разработки уровня передачи данных (а также более высоких уровней) связан с вопросом о том, что делать с отправителем, который постоянно желает передавать кадры быстрее, чем получатель способен их получать.Такая ситуация может возникнуть, если у передающей стороны оказывается более мощный (или менее загруженный) компьютер, чем у принимающей. Отправитель продолжает посылать кадры на высокой скорости до тех пор, пока получатель не окажется полностью ими завален. Даже при идеально работающей линиисвязи в определенный момент получатель просто не сможет продолжать обработку все прибывающих кадров и начнет их терять. Очевидно, что для предотвращения подобной ситуации следует что-то предпринять.232Глава 3. Уровень передачи данныхВ настоящее время применяются два подхода. При первом, называющемсяуправлением потоком с обратной связью, получатель отсылает отправителюинформацию, разрешающую последнему продолжить передачу или, по крайнеймере, сообщающую о том, как идут дела у получателя.
При втором подходе, управлении потоком с ограничением, в протокол встраивается механизм, ограничивающий скорость, с которой передатчики могут передавать данные. Обратная связьс получателем отсутствует. В этой главе мы рассмотрим только подход с обратной связью, поскольку второй подход никогда не применяется на уровне передачи данных (впрочем, мы вернемся к нему в главе 5).Известны различные схемы контроля потока с обратной связью, но большинство из них используют один и тот же принцип.
Протокол содержит четко определенные правила, определяющие, когда отправитель может посылать следующий кадр. Эти правила часто запрещают пересылку кадра до тех пор, покаполучатель не даст разрешения, либо явно, либо неявно. Например, при установке соединения получатель может сказать: «Вы можете послать мне сейчас п кадров, но не посылайте следующие кадры, пока я не попрошу вас продолжать».В данной главе мы рассмотрим различные механизмы, основанные на этомпринципе.Обнаружение и исправление ошибокКак было показано в главе 2, телефонная система состоит из трех частей — коммутаторов, межкоммутаторных магистралей и местных телефонных линий. Первые две части являются сегодня почти полностью цифровыми.
Местные телефонные линии до сих пор представляют собой аналоговые медные витые пары иостанутся такими еще в течение нескольких лет, поскольку их замена стоит оченьдорого. И хотя в цифровой части телефонной системы ошибки случаются редко,в местных телефонных линиях вероятность ошибки очень велика. Кроме того,в последнее время все большее распространение получает беспроводная связь,в которой уровень ошибок на несколько порядков выше, чем в соединяющих телефонные станции магистралях. Отсюда следует вывод: ошибки при передачеданных останутся важным фактором еще на долгие годы. Сейчас мы приступаемк изучению методов их обнаружения и устранения.Вследствие особенностей физических процессов, порождающих их, ошибкив некоторых типах носителей (например, радио) чаще бывают не единичными,а групповыми. В этом есть как положительные, так и отрицательные стороны.
Положительные связаны с тем, что компьютеры всегда посылают данные битовымиблоками. Представьте себе блок размером в 1000 бит при вероятности ошибки0,001 на бит. Если бы ошибки были независимыми, то очень большой процентблоков содержал бы ошибки. Однако если ошибки приходят пакетами, искажаяпо 100 бит подряд, то из 100 блоков будут испорчены в среднем только один илидва. Неудобством групп ошибок является то, что их значительно труднее исправить, чем изолированные ошибки.Обнаружение и исправление ошибок233Корректирующее кодированиеРазработчики сетей создали две основные стратегии для борьбы с ошибками. Каждый метод основывается на добавлении к передаваемым данным некоторой избыточной информации.
В одном случае этой информации должно быть достаточно,чтобы выявить, какие данные должны были прийти. В другом случае избыточнойинформации должно быть достаточно только для того, чтобы получатель понял,что произошла ошибка (без указания ее типа) и запросил повторную передачу.Первая стратегия использует коды, называющиеся корректирующими, или кодами с исправлением ошибок. Вторая — код с обнаружением ошибок.
Использование кода с обнаружением ошибок часто называют прямым исправлением ошибок.Каждая стратегия занимает свою, так сказать, экологическую нишу. В высоконадежных каналах, таких как оптоволокно, дешевле использовать код с обнаружением ошибок и просто заново передавать случайные поврежденные блоки.Однако, скажем, беспроводные соединения, в которых может возникать множество ошибок, чаще используют коды с избыточностью, достаточной для того, чтобыприемник мог определить, какие данные должны были прийти.
Это надежнее,чем полагаться на повторную передачу, которая тоже, возможно, не сможет пройти без ошибок.Чтобы понять, как могут обнаруживаться и исправляться ошибки, необходимо рассмотреть подробнее, что же представляет собой ошибка. Обычно кадр состоит из т битов данных (то есть информационных битов) и г избыточных иликонтрольных битов. Пусть полная длина кадра равна п (то есть п = т + г). Набориз п бит, содержащий информационные и контрольные биты, часто называют«-битовым кодовым словом или кодовой комбинацией.Если рассмотреть два кодовых слова, например 10001001 и 10110001, можноопределить число различающихся в них соответствующих разрядов.
В данном/примере различаются 3 бита. Для нахождения этого числа нужно сложить двакодовых слова по модулю 2 (операция «исключающее или») и сосчитать количество единиц в результате, например:100010011011000100111000Количество битов, которыми различаются два кодовых слова, называется кодовым расстоянием, или расстоянием между кодовыми комбинациями в смыслеХэмминга (Hamming, 1950). Смысл этого числа состоит в том, что если два кодовых слова находятся на кодовом расстоянии d, то для преобразования одного кодового слова в другое понадобится d ошибок в одиночных битах.В большинстве приложений передачи данных все 2т возможных сообщенийявляются допустимыми, однако благодаря использованию контрольных битовне все 2" возможных кодовых слов используются.
Зная алгоритм формированияконтрольных разрядов, можно построить полный список всех допустимых кодовых слов и в этом списке найти такую пару кодовых слов, кодовое расстояние234Обнаружение и исправление ошибокГлава 3. Уровень передачи данныхмежду которыми будет минимальным. Это расстояние называется минимальнымкодовым расстоянием кода, или расстоянием всего кода в смысле Хэмминга.Способности кода по обнаружению и исправлению ошибок зависят от его минимального кодового расстояния. Для обнаружения d ошибок в одном кодовомслове необходим код с минимальным кодовым расстоянием, равным d + 1, поскольку d однобитовых ошибок не смогут изменить одну допустимую комбинацию так, чтобы получилась другая допустимая комбинация. Когда приемниквстречает запрещенную кодовую комбинацию, он понимает, что при передаче произошла ошибка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
