(Для любознательных: это результат для очереди «M/M/1». Требуется, чтобы случайность длительности промежутков между фреймами и длины фреймов соответствовала экспоненциальному распределению или, что эквивалентно, являлась результатом пуассоновского процесса.)
В нашем примере C равно 100 Мбит/с, средняя длина фрейма 1/μ = 10 000 бит, скорость входного потока λ = 5000 фреймов в секунду. Тогда T = 200 мкс. Обратите внимание: если бы мы не учли задержки при формировании очереди и просто посчитали, сколько времени нужно на передачу фрейма длиной 10 000 бит по сети с пропускной способностью 100 Мбит/с, то получили бы неправильный ответ: 100 мкс. Этот результат верен лишь при отсутствии конкуренции за канал.
Теперь разделим канал на N независимых подканалов, каждый из которых имеет пропускную способность C/N бит/с. Средняя входная скорость в подканале теперь равна λ/N фреймов в секунду. Вычислив новое значение средней задержки T, получим:
В разделенном канале средняя задержка в N раз хуже, чем в канале, в котором все фреймы волшебным образом организованы в одну общую очередь. Тот же вывод можно сделать на следующем примере: предоставляя доступ к банкоматам в холле банка, лучше организовать посетителей в одну общую очередь. Отдельные очереди могут привести к тому, что одни банкоматы будут простаивать, в то время как перед другими выстроится много людей.
Аргументы, применимые к FDM, относятся и к другим способам статического распределения канала. Можно использовать схему TDM и выделять каждому пользователю N-й слот. Но если абонент не будет передавать данные, этот слот просто пропадет. С тем же успехом можно разделить сети физически. Если взять 100-мегабитную сеть и сделать из нее десять 10-мегабитных, статически распределив по ним пользователей, то в результате средняя задержка возрастет с 200 мкс до 2 мс.
Таким образом, ни один статический метод распределения каналов не подходит для неравномерного трафика, поэтому далее мы рассмотрим динамические методы.
4.1.2. Допущения, связанные с динамическим распределением каналов
Прежде чем приступить к рассмотрению многочисленных методов распределения каналов, следует тщательно сформулировать задачу. В основе всех разработок в данной области лежат следующие пять допущений.
1. Независимый трафик. Модель состоит из N независимых станций (компьютеров, телефонов, персональных средств связи и т.д.), в каждой из которых программа или пользователь формируют фреймы для передачи. Ожидаемое число фреймов в интервале времени ∆t равно λ∆t, где λ — постоянная величина (скорость прибытия новых фреймов). Как только фрейм сформирован, станция блокируется и ничего не делает, пока он не будет успешно передан.
2. Единый канал. Он доступен для всех. Все станции могут передавать и принимать по нему данные. Они обладают одинаковой производительностью, хотя программно протокол может устанавливать для них различные роли (например, приоритеты).
3. Наблюдаемые коллизии. Если два фрейма передаются одновременно, они перекрываются по времени, и в результате сигнал искажается. Такое событие называется коллизией (collision). Обнаруживать их могут все станции. Фрейм, искаженный из-за коллизии, должен быть передан повторно. Других ошибок, кроме тех, которые вызваны коллизиями, нет.
4. Непрерывное/дискретное время. Если допустить, что время непрерывно, то передача фреймов может начаться в любой момент. В противном случае время разделяется на дискретные интервалы (слоты). Отправка фрейма происходит только с началом слота. Один слот может содержать 0 (свободный интервал), 1 (успешная передача) или более фреймов (коллизия).
5. Контроль (опрос) несущей/его отсутствие. При контроле несущей станции определяют, свободна ли линия, прежде чем начать ее использовать. Если канал занят, станции не будут пытаться передавать по нему фреймы, пока тот не освободится. Если контроля несущей нет, то станции не могут заранее получить эту информацию. Они просто начинают передачу и только потом выясняют, была ли она успешной.
О приведенных выше допущениях следует сказать несколько слов. Первое утверждает, что фреймы приходят независимо друг от друга (как на разные станции, так и в пределах одной) и что они формируются непредсказуемо, но с постоянной скоростью. В действительности это не слишком хорошая модель сетевого трафика, поскольку давно известно, что пакеты прибывают целыми последовательностями в определенные диапазоны временной шкалы (см. работу Паксона и Флойд; Paxson, Floyd, 1995). Последние исследования подтверждают данную закономерность (Фонтюнь и др.; Fontugne et al., 2017). При этом пуассоновские модели, как их часто называют, находят широкое применение, в том числе потому, что они легко поддаются математическому описанию. Они позволяют анализировать протоколы, чтобы составить общее представление об изменении производительности с течением времени и о разнице между реализациями.
Единый канал — центральное допущение в данной модели. Никаких дополнительных средств связи нет. Станции не могут тянуть руки в надежде, что учитель их спросит, поэтому приходится искать лучшее решение.
Оставшиеся три допущения зависят от инженерной реализации системы, поэтому при изучении конкретных протоколов мы будем указывать, какие допущения следует считать верными.
Допущение о коллизиях является базовым. Станциям необходим способ обнаружения коллизий, если они собираются повторно пересылать фреймы, а не мириться с их потерей. Для проводных каналов можно использовать оборудование, умеющее определять коллизии. В этом случае станции заранее обрывают передачу, чтобы не засорять канал. В беспроводных каналах распознавать коллизии намного сложнее; об их возникновении приходится узнавать по факту, когда не прибывает ожидаемое подтверждение. Также возможно успешное получение некоторых фреймов, попавших в коллизию, — это зависит от типа сигнала и оборудования на получающей стороне. Подобные ситуации встречаются нечасто, поэтому будем предполагать, что все эти фреймы теряются. Кроме того, есть протоколы, специально предназначенные для предотвращения коллизий, а не решения создаваемых ими проблем.
Причина существования двух альтернативных допущений для времени заключается в том, что дискретное время иногда помогает повысить производительность. Однако использующие его станции должны синхронизироваться с тактовым генератором или друг с другом, а это не всегда возможно. Мы рассмотрим оба варианта. В каждой конкретной системе работает только одно из возможных допущений.
Контроль несущей также реализован не во всех системах. В проводных сетях такой контроль обычно присутствует, но беспроводные не всегда могут эффективно его использовать, поскольку не каждая станция может слышать все остальные из-за разницы частотных диапазонов. Аналогично, когда станция не может напрямую взаимодействовать с другими (например, ей приходится пересылать информацию через кабельный модем, играющий роль центрального узла), контроль несущей бывает недоступен. Обратите внимание, что слово «несущая» здесь означает электрический сигнал, распространяющийся по каналу.
Чтобы избежать недопонимания, стоит заметить, что ни один протокол коллективного доступа не гарантирует надежную доставку. Даже при отсутствии коллизий получатель мог по каким-то причинам неправильно скопировать часть фрейма. Надежность обеспечивают другие составляющие канального или более высоких уровней.
4.2. Протоколы коллективного доступа
Существует множество алгоритмов коллективного доступа. В следующих разделах будут рассмотрены наиболее интересные из них и даны примеры их применения на практике.
4.2.1. Система ALOHA
История первого протокола подуровня MAC начинается на нетронутых цивилизацией Гавайях в 1970-х годах. В данном случае «нетронутые цивилизацией» означает «не имеющие рабочей телефонной системы». Это не упрощало жизнь Нормана Абрамсона (Norman Abramson) и его коллег из Гавайского университета, которые пытались подключить пользователей на удаленных островах к главному компьютеру в Гонолулу. Идея протянуть кабели на громадное расстояние по дну Тихого океана даже не рассматривалась, так что исследователи искали другой способ.
Решение было основано на использовании радиосистемы ближнего радиуса действия. Терминал каждого пользователя передавал фреймы на центральный компьютер в пределах общей полосы частот. Также был найден простой и элегантный метод решения проблемы распределения каналов. Результаты работы этой группы ученых впоследствии стали основой многих исследований (Шварц и Абрамсон; Schwartz and Abramson, 2009). Несмотря на то что в разработанной Абрамсоном сети ALOHA использовалась широковещательная радиосвязь со стационарными передатчиками, ее общий принцип применим к любой системе, в которой независимые пользователи соревнуются за право использования одного общего канала.
В данном разделе мы рассмотрим две версии системы ALOHA: чистую и дискретную. Различие между ними состоит в том, что в чистой версии время является непрерывным, а в дискретной делится на дискретные интервалы, в которые должны помещаться все фреймы.
Чистая система ALOHA
В основе ALOHA лежит простая идея: разрешить пользователям передачу, как только у них появляются данные для отправки. Конечно, будут возникать коллизии, приводящие к повреждению фреймов. Отправителям необходимо уметь обнаруживать такие ситуации. Каждая станция отправляет свой фрейм центральному компьютеру, а тот передает его на все остальные станции. Отправитель прослушивает широковещательную передачу, чтобы понять, насколько она была успешной. В других системах, например проводных LAN, отправитель имеет возможность распознавать коллизии во время передачи.
Если фрейм был уничтожен, отправитель выжидает в течение случайного временного интервала и пытается переслать его снова. Время ожидания должно быть случайным, иначе одни и те же фреймы будут синхронно попадать в коллизию снова и снова. Системы, в которых несколько пользователей используют один общий канал так, что время от времени возникают конфликты, называются системами с конкуренцией (contention systems).