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

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

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

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

4.2. Протоколы коллективного доступа

Известно множество алгоритмов коллективного доступа. В следующих разделах будут рассмотрены наиболее интересные алгоритмы и даны примеры их применения на практике.

4.2.1. Система ALOHA

История нашего первого MAC начинается на нетронутых цивилизацией Гавайях в 1970-х годах. В данном случае «нетронутые цивилизацией» означает «не имеющие рабочей телефонной системы». Это не упрощало жизнь исследователя Нормана Абрамсона (Norman Abramson) и его коллег из Гавайского университета, которые пытались подключить пользователей на удаленных островах к главному компьютеру в Гонолулу. Идея протянуть кабели по дну Тихого океана даже не рассматривалась, так что исследователи искали другое решение.

Найденное решение основывалось на использовании радиосистемы ближнего радиуса действия. Терминал каждого пользователя передавал кадры на центральный компьютер в пределах общей полосы частот. Также присутствовал простой и элегантный метод решения проблемы распределения каналов. Их труды впоследствии стали основой многих исследований (Schwartz, Abramson, 2009). Хотя в работе Абрамсона, получившей название системы ALOHA, использовалась широковещательная радиосвязь со стационарными передатчиками, основная идея применима к любой системе, в которой независимые пользователи соревнуются за право использования одного общего канала.

В данном разделе мы рассмотрим две версии системы ALOHA: чистую и дискретную. Они отличаются тем, непрерывно ли время (чистая версия) или делится на дискретные интервалы, в которые должны помещаться все кадры.

Чистая система ALOHA

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

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

На рис. 4.1 показан пример формирования кадров в системе ALOHA. Все кадры на нашем рисунке имеют один размер, так как при этом пропускная способность системы становится максимальной, именно за счет единого фиксированного размера кадров.

Рис. 4.1. В чистой системе ALOHA кадры передаются в абсолютно произвольное время

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

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

Пусть «время кадра» означает интервал времени, требуемый для передачи стандартного кадра фиксированной длины (то есть длину кадра, деленную на скорость передачи данных). На данный момент мы предполагаем, что новые кадры, порождаемые станциями, хорошо распределены по Пуассону со средним значением N кадров за время кадра. (Допущение о бесконечном количестве пользователей необходимо для того, чтобы гарантировать, что величина N не станет уменьшаться по мере блокирования пользователей.) Если N > 1, это означает, что сообщество пользователей формирует кадры с большей скоростью, чем может быть передано по каналу, и почти каждый кадр будет страдать от столкновений. Мы будем предполагать, что 0 < N <1.