Компьютерные сети. 6-е изд.

3.1. Ключевые вопросы проектирования канального уровня

Канальный уровень использует определенные службы нижележащего физического уровня для отправки и получения битов по потенциально ненадежным коммуникационным каналам, которые могут терять данные. У него есть ряд специфических функций. К ним относятся:

1. Обеспечение строго очерченного служебного интерфейса для сетевого уровня (раздел 3.1.1).

2. Формирование отдельных фреймов из последовательностей байтов (раздел 3.1.2).

3. Обнаружение и исправление ошибок передачи (раздел 3.1.3).

4. Управление потоком данных, исключающее «затопление» медленных приемников быстрыми передатчиками (раздел 3.1.4).

Для этих целей канальный уровень берет пакеты, полученные с сетевого уровня, и вставляет их в специальные фреймы (frames), также называемые кадрами, для передачи. В каждом фрейме содержатся поля Header (Заголовок), Payload (Пользовательские данные) и Trailer (Трейлер). Структура фрейма показана на илл. 3.1. Управление фреймами — это основная задача канального уровня. В следующих разделах мы более подробно изучим обозначенные выше цели. Кроме того, в ненадежных беспроводных сетях использование протоколов для улучшения канала связи часто увеличивает производительность в дальнейшем.

Илл. 3.1. Соотношение между пакетами и фреймами

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

3.1.1. Службы, предоставляемые сетевому уровню

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

Илл. 3.2. (а) Виртуальное соединение. (б) Реальное соединение

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

1. Служба без подтверждений и без установки соединения.

2. Служба с подтверждениями и без установки соединения.

3. Служба с подтверждениями, ориентированная на установление соединения.

Алгоритм работы службы без подтверждений и без установки соединения заключается в том, что отправляющее устройство посылает независимые фреймы принимающему, которое не отвечает подтверждением о получении. Хороший пример канального уровня, предоставляющего службу такого класса, — Ethernet. Соединения заранее не устанавливаются и не разрываются после передачи. Если какой-либо фрейм теряется из-за шума в линии, то на канальном уровне не предпринимается никаких попыток восстановить его. Этот класс служб приемлем при очень низком уровне ошибок. В этом случае задача восстановления потерянных данных может быть решена на верхних уровнях. Кроме того, такие службы подходят для трафика в реальном времени, например голосовых или видеоданных, поскольку в этом случае лучше получить данные в искаженном виде, чем с большой задержкой.

Следующим шагом в сторону повышения надежности является служба с подтверждениями и без установки соединения. При ее использовании соединение также не устанавливается, но получение каждого фрейма подтверждается. В результате отправитель знает, дошел ли фрейм до пункта назначения в целости или потерялся. Если в течение установленного интервала времени подтверждения не поступает, фрейм отправляется снова. Такая служба полезна при передаче по ненадежным каналам, в частности беспроводным. Хороший пример — протокол 802.11 (Wi-Fi).

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

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

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

3.1.2. Формирование фрейма

Для обслуживания сетевого уровня канальный уровень использует службы, предоставляемые ему физическим уровнем. Физический уровень принимает необработанный поток битов и пытается передать его по назначению. Если канал зашумлен (как обычно бывает с беспроводными и большинством проводных соединений), то на физическом уровне добавляются избыточные сигналы, чтобы снизить количество ошибок до допустимого уровня. Однако поток битов, получаемый на уровне передачи данных, не застрахован от ошибок. У некоторых битов могут быть другие значения, количество принятых битов может быть меньше, равно или больше числа переданных. Канальный уровень должен обнаружить ошибки и, если нужно, исправить их.

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

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

1. Подсчет байтов.

2. Флаговые байты с байт-стаффингом.

3. Использование сигнальных битов с бит-стаффингом.

4. Применение запрещенных сигналов физического уровня.

Первый метод формирования фреймов заключается в указании количества байтов фрейма в поле заголовка. Канальный уровень на принимающем устройстве видит это поле, узнает, сколько байтов последует, и таким образом определяет, где находится конец фрейма. Этот прием проиллюстрирован на илл. 3.3 (а) для четырех небольших фреймов размером 5, 5, 8 и 8 байт.

Недостаток такой системы в том, что при передаче может быть искажен сам счетчик. Например, если при подсчете байтов второго фрейма произойдет ошибка в единственном бите и число 5 превратится в 7, как показано на илл. 3.3 (б), то целевое устройство потеряет синхронизацию и не сможет правильно обнаружить начало следующего фрейма. Даже если контрольная сумма не сойдется (скорее всего) и устройство поймет, что фрейм принят неверно, то оно все равно не сможет определить начало следующего фрейма. Запрашивать повторную передачу фрейма бесполезно, поскольку неизвестно, сколько байтов нужно пропустить до начала повторной передачи. По этой причине на сегодняшний день метод подсчета байтов отдельно практически не применяется.

Илл. 3.3. Поток байтов: (а) без ошибок; (б) с одной ошибкой

Второй метод формирования фреймов решает проблему восстановления синхронизации после сбоя при помощи маркировки начала и конца каждого фрейма специальными байтами. Зачастую в качестве разделителя используется один и тот же байт, называемый флаговым (flag byte). Он устанавливается в начальной и конечной точке фрейма. Этот байт помечен на илл. 3.4 (а) как FLAG. Два соседних флаговых байта говорят о том, что закончился один фрейм и начался другой. Таким образом, если приемник теряет синхронизацию, ему необходимо просто найти два флаговых байта, с помощью которых он распознает конец текущего фрейма и начало следующего.

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

Следующий логичный вопрос: а что, если и символ ESC случайно окажется в данных? Решение такое же: вставить перед фиктивным escape-символом настоящий. На стороне получателя первый символ ESC будет удален, а следующий байт данных останется, даже если это еще один байт ESC или флаговый байт. На илл. 3.4 (б) показаны некоторые примеры. В любом случае байтовая последовательность после ее очищения от вставленных символов в точности совпадает с исходной. Найти границу фрейма можно все так же по двум последовательным флаговым байтам до удаления дополнительных символов ESC.

Илл. 3.4. (а) Фрейм, ограниченный флаговыми байтами. (б) Четыре примера байтовых последовательностей до и после байт-стаффинга

Схема байт-стаффинга, представленная на илл. 3.4, — это немного упрощенная модель протокола PPP (Point-to-Point Protocol, протокол «точка-точка»), который служит для передачи пакетов по коммуникационным каналам и широко используется в сети интернет. Мы подробно обсудим протокол PPP в разделе 3.5.1.

Третий метод разделения потока битов на фреймы позволяет обойти недостатки байт-стаффинга, который обязывает использовать исключительно 8-битные байты. Делить данные на фреймы можно на уровне битов, причем фреймы могут содержать произвольное число битов и состоять из блоков любого размера. Данный метод был разработан для некогда популярного протокола HDLC (High-level Data Link Control — высокоуровневый протокол управления каналом передачи данных). Каждый фрейм начинается и завершается специальной последовательностью битов, 01111110 (или 0x7E в шестнадцатеричной системе). Это все тот же флаговый байт. Если в битовом потоке встретится пять единиц подряд, уровень передачи данных автоматически вставит в выходной поток нулевой бит. Бит-стаффинг (bit stuffing) аналогичен байт-стаффингу, при котором во фрейм вставляется escape-символ перед случайным флагом. Он также гарантирует минимальную плотность передачи, помогающую сохранять синхронизацию на физическом уровне. По этой причине бит-стаффинг применяется в протоколе USB.

Когда принимающая сторона встречает пять единиц подряд, за которыми следует ноль, она автоматически удаляет его. Бит-стаффинг, как и байт-стаффинг, является абсолютно прозрачным для сетевого уровня обоих устройств. Если флаговая последовательность 01111110 встречается в данных пользователя, она передается в виде 011111010, но в памяти целевого устройства сохраняется в исходном виде: 01111110. При этом вышележащие уровни остаются в полном неведении о применении бит-стаффинга. На илл. 3.5 приведен пример этого метода.

Илл. 3.5. Бит-стаффинг. (а) Исходные данные. (б) Данные на линии. (в) Данные, сохраненные в памяти после удаления вставленных битов

Благодаря бит-стаффингу границы между двумя фреймами могут быть безо­шибочно распознаны с помощью флаговой последовательности. Таким образом, если принимающая сторона потеряет границы фреймов, ей нужно всего лишь отыскать в полученном потоке битов флаговый байт, поскольку он встречается только на границах фреймов и никогда не встречается в данных пользователя.

Побочный эффект как бит-стаффинга, так и байт-стаффинга состоит в том, что длина фрейма зависит от содержимого, то есть от входящих в него данных. Например, если в данных нет флаговых байтов, то 100 байт можно передать во фрейме размером приблизительно 100 байт. Если же данные состоят исключительно из флаговых байтов, то перед каждым из них вставляется ESC и длина фрейма увеличивается примерно до 200 байт. При бит-стаффинге увеличение составляет около 12,5 %, так как к каждому байту добавляется 1 бит.

Последний метод формирования фреймов напрямую связан с особенностями физического уровня. В главе 2 мы узнали, что при кодировании битов в виде сигналов для облегчения работы получающей стороны добавляются избыточные данные. Это означает, что в самих данных некоторые сигналы не появляются. Например, в линии 4B/5B четыре бита данных сопоставляются с пятью сигнальными битами, для того чтобы гарантировать удовлетворительную передачу. Таким образом, 16 из 32 возможных сигналов не используются. Некоторые из зарезервированных сигналов можно применять для обозначения начальной и конечной границы фреймов. Фактически для разграничения фреймов можно применять «нарушения правил кодирования» (неправильные символы). Преимущество этого метода в том, что использование зарезервированных сигналов делает поиск границ фрейма чрезвычайно простым. При этом заполнять данные дополнительными байтами или битами не требуется.

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

3.1.3. Обработка ошибок

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

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

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

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

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

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

3.1.4. Управление потоком

Еще один важный вопрос разработки канального уровня (а также более высоких уровней) — что делать с отправителем, постоянно передающим фреймы быстрее, чем получатель способен их получать. Такая ситуация может возникнуть, если у передающей стороны оказывается более быстрый и мощный компьютер, чем у принимающей. Представьте смартфон, запрашивающий веб-страницу с высокотехнологичного сервера. Мощнейшее устройство развертывает пожарный шланг, наводит его на бедный телефон и поливает его данными до тех пор, пока тот не захлебнется. Даже при полном отсутствии ошибок передачи данных в определенный момент получатель просто не сможет продолжать обработку все прибывающих фреймов и начнет их терять.

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

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

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