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

Ожидаемое число попыток передачи для одной строки, введенной на терминале, равно:

Поскольку число попыток передачи для одного кадра E экспоненциально зависит от количества попыток передачи в единицу времени G , небольшое увеличение нагрузки в канале может сильно снизить его производительность.

Дискретная система ALOHA чрезвычайно важна по одной причине, которая на первый взгляд не кажется очевидной. Она появилась в 1970-х годах, применялась в некоторых экспериментальных системах, затем была почти забыта. Когда был изобретен метод доступа в Интернет по кабельным сетям, вновь возникла проблема распределения единственного канала между большим числом конкурирующих абонентов. Тогда с полок достали запыленные описания дискретной системы ALOHA. Позднее в ситуации, когда несколько тегов RFID пытались общаться с одним считывателем RFID, возник еще один вариант старой проблемы. Дискретная система ALOHA, приправленная несколькими другими идеями, снова сумела спасти ситуацию. Не раз уже было так, что вполне работоспособные протоколы и методы оказывались невостребованными по политическим причинам (например, когда какая-нибудь крупная компания выражала желание, чтобы все на свете использовали исключительно ее продукцию) или из-за постоянно меняющихся технологий. Однако по прошествии многих лет какой-нибудь мудрый человек вспоминал о существовании одного древнего метода, способного решить современную проблему. По этой причине мы изучим в данной главе ряд элегантных протоколов, которые сейчас широко не используются, но запросто могут оказаться востребованными в будущем, — если, конечно, об их существовании будет знать достаточное количество разработчиков сетей. Разумеется, мы изучим и многие протоколы, используемые в настоящее время.

4.2.2. Протоколы множественного доступа с контролем несущей

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

Протоколы, в которых станции прослушивают среду передачи данных и действуют в соответствии с этим, называются протоколами с контролем несущей. Было разработано много таких протоколов и их давным-давно подробно проанализировали. Например, см. работу Кляйнрок и Тобаги (Kleinrock, Tobagi, 1975). Ниже мы рассмотрим несколько версий протоколов с контролем несущей.

Настойчивый и ненастойчивый CSMA

Первый протокол с опросом несущей, который мы рассмотрим, называется 1-на-стойчивый протокол CSMA (Carrier-Sense Multiple Access — множественный доступ с контролем несущей). Длинноватое название для простейшей схемы CSMA. Когда у станции появляются данные для передачи, она сначала прослушивает канал, проверяя, свободен он или занят. Если канал бездействует, то станция отправляет данные. В противном случае, когда канал занят, станция ждет, пока он освободится. Затем станция передает кадр. Если происходит столкновение, станция ждет в течение случайного интервала времени, затем снова прослушивает канал и, если он свободен, пытается передать кадр еще раз. Такой протокол называется протоколом CSMA с настойчивостью 1, так как станция передает кадр с вероятностью 1, как только обнаружит, что канал свободен.

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

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

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

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

Наконец, третий протокол, который мы рассмотрим, это протокол CSMA с настойчивостью р. Он применяется в дискретных каналах и работает следующим образом. Когда станция готова передавать, она опрашивает канал. Если канал свободен, она с вероятностью p начинает передачу. С вероятностью q = 1 - p она отказывается от передачи и ждет начала следующего такта. Этот процесс повторяется до тех пор, пока кадр не будет передан или какая-либо другая станция не начнет передачу. В последнем случае станция ведет себя так же, как в случае столкновения. Она ждет в течение случайного интервала времени, после чего начинает все снова. Если при первом прослушивании канала он оказывается занят, станция ждет следующего интервала времени, после чего применяется тот же алгоритм. В IEEE 802.11 применяется улучшенная версия протокола CSMA с настойчивостью р, которую мы рассмотрим далее.