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

4.1.1. Статическое распределение канала

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

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

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

Низкую эффективность статического FDM можно увидеть на примере простых вычислений теории массового обслуживания. Для начала подсчитаем среднее время задержки T для отправки фрейма по каналу емкостью C бит/с. Предполагается, что фреймы приходят в случайном порядке со средней скоростью λ фреймов в секунду. Длина фреймов варьируется и в среднем равна 1/μ бит. При таких параметрах скорость обслуживания канала равна μC фреймов в секунду. Теория массового обслуживания говорит о том, что

(Для любознательных: это результат для очереди «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). При этом пуассоновские модели, как их часто называют, находят широкое применение, в том числе потому, что они легко поддаются математическому описанию. Они позволяют анализировать протоколы, чтобы составить общее представление об изменении производительности с течением