Компьютерные сети. 6-е изд. - Эндрю Таненбаум

времени и о разнице между реализациями.

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

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

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

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

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

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

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

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

4.2.1. Система ALOHA

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

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

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

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

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

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

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

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

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

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

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

Помимо новых, станции повторно отправляют старые фреймы, пострадавшие от столкновений. Предположим, что старые и новые фреймы хорошо распределены по Пуассону со средним значением G