class="p">Очевидно, что для предотвращения подобной ситуации следует что-то предпринять. В настоящее время применяются два подхода. Первый из них — управление потоком с обратной связью (feedback-based flow control): получатель отсылает отправителю сообщение, в котором разрешает продолжить передачу или просто сообщает о своем состоянии. При втором подходе, управлении потоком с ограничением (rate-based flow control), в протокол встраивается механизм, ограничивающий скорость, с которой отправитель может передавать данные. Обратная связь с получателем отсутствует.

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

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

3.2. Обнаружение и коррекция ошибок

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

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

Каждая стратегия занимает свою нишу. В высоконадежных (например, оптоволоконных) каналах дешевле использовать код для обнаружения ошибок и просто заново передавать поврежденные блоки. А беспроводные соединения, в которых возникает множество ошибок, чаще используют избыточность информации, позволяющей определить, какие данные должны были прийти. FEC применяется в зашумленных каналах, поскольку вероятность ошибки при повторной передаче так же велика, как и при первой.

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

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

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

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

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

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

3.2.1. Корректирующие коды

Мы рассмотрим четыре разных корректирующих кода:

1. Коды Хэмминга.

2. Двоичные сверточные коды.

3. Коды Рида — Соломона.

4. Коды с малой плотностью проверок на четность.

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