Эндрю Уэзеролл - Компьютерные сети. 5-е издание

В этой главе мы рассмотрим только подход с обратной связью, в основном потому, что подход с ограничением используется только на транспортном уровне (подробнее об этом — в главе 5). Управление потоком с обратной связью применяется на канальном уровне, но чаще — на более высоких уровнях. При этом оборудование канального уровня работает достаточно быстро, чтобы потери информации не происходило. Например, про аппаратную реализацию этого уровня в виде карт NIC( Network Interface Card — сетевая интерфейсная карта) говорят, что она работает со скоростью передачи данных, то есть кадры обрабатываются с той же скоростью, с какой они прибывают. Канальный уровень не отвечает за переполнение, эти проблемы решаются на более высоких уровнях.

Известны различные схемы контроля потока с обратной связью, но большинство из них использует один и тот же принцип. Протокол содержит четко определенные правила, определяющие, когда отправитель может посылать следующий кадр. Эти правила часто запрещают пересылку кадра до тех пор, пока получатель не даст разрешения, либо явно, либо неявно. Например, при установке соединения получатель может сказать: «Вы можете послать мне сейчас n кадров, но не посылайте следующие кадры, пока я не попрошу вас продолжать». В данной главе мы рассмотрим различные механизмы, основанные на этом принципе.

3.2. Обнаружение и исправление ошибок

Как было показано в главе 2, у каналов передачи данных большой диапазон характеристик. В некоторых каналах, таких как оптическое волокно в телекоммуникационных сетях, вероятность ошибки крайне низка, поэтому потеря данных происходит исключительно редко. Но количество ошибок, например, в беспроводных сетях или старых местных сетях в десятки раз больше. Здесь ошибки передачи вообще считаются нормой. Для того чтобы полностью исключить их, потребуются слишком большие затраты в терминах производительности. Отсюда следует вывод: ошибки при передаче данных останутся важным фактором еще на долгие годы. Сейчас мы приступаем к изучению методов их обнаружения и устранения.

Разработчики сетей создали две основные стратегии для борьбы с ошибками. Каждый метод основывается на добавлении к передаваемым данным некоторой избыточной информации. В одном случае этой информации должно быть достаточно, чтобы принимающая сторона могла выявить, какие данные должны были прийти. В другом случае избыточной информации должно быть достаточно только для того, чтобы получатель понял, что произошла ошибка (без указания ее типа), и запросил повторную передачу. Первая стратегия использует коды, называющиеся корректирующимиили кодами с исправлением ошибок( error-correcting codes). Вторая — коды с обнаружением ошибок( error-detecting codes). Использование кода с исправлением ошибок часто называют прямым исправлением ошибок( Forward Error Correction— FEC).

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

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

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

Обе модели имеют практическую значимость, но у каждой свои преимущества и недостатки. Почему последовательность ошибок может быть лучше одиночных? Компьютер всегда отправляет данные блоками. Предположим, что размер блока равен 1000 бит, а вероятность ошибки равна 0,001 на один бит. Если бы ошибки были независимыми, то почти в каждом блоке обнаруживалась бы ошибка. Однако если возникнет целая последовательность ошибок, то в среднем из ста блоков только один будет поврежден. С другой стороны, последовательность ошибок исправить намного сложнее, чем изолированные ошибки.

Существуют и другие типы ошибок. Иногда местоположение ошибки известно. Например, физический уровень получает аналоговый сигнал, значение которого намного отличается от ожидаемого нуля или единицы, и объявляет, что бит потерян. Такой канал называется каналом со стиранием( erasure channel). В каналах со стиранием ошибки исправлять проще, чем в каналах, где значения битов меняются на противоположные: даже если значение бита утеряно, по крайней мере, нам известно, где притаилась ошибка. Тем не менее воспользоваться преимуществами стирающих каналов удается нечасто.

Далее мы рассмотрим коды с исправлением ошибок и коды с обнаружением ошибок. Прошу вас только не забывать о двух вещах. Во-первых, мы изучаем этот вопрос на канальном уровне, так как это первое место, где перед нами встает проблема надежной пересылки группы битов. Однако коды используются весьма широко, так как вопрос надежности важен всегда и везде. Коды исправления ошибок можно встретить на физическом уровне, особенно когда речь идет о зашумленных каналах, и на более высоких уровнях, особенно при рассылке мультимедийной информации в режиме реального времени. Коды обнаружения ошибок применяются на канальном, сетевом и транспортном уровнях.

Помимо этого, следует помнить, что коды ошибок относятся к прикладной математике. Если только вы не крупный специалист по полям Галуа или свойствам слабо заполненных матриц, используйте надежные коды, полученные из проверенных источников, и не пытайтесь конструировать собственные. В действительности, так делается во многих стандартных протоколах; одни и те же коды будут встречаться вам снова и снова. Далее мы подробно изучим простой код, а затем коснемся нескольких более сложных. Так вы сможете лучше понять преимущества и недостатки различных кодов и познакомиться с кодами, применяемыми на практике.