![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Протоколы произвольного доступа
Второй широкий класс протоколов коллективного доступа составляют так называемые протоколы произвольного доступа. В протоколе произвольного доступа передающий узел всегда передает данные в канал с максимальной скоростью, то есть R бит/с. Когда возникает коллизия, каждый вовлеченный в нее узел передает свой кадр повторно до тех пор, пока ему не удастся пройти по каналу без коллизий. Однако, испытав коллизию, узел, как правило, не повторяет передачу тут же, а выжидает в течение случайного интервала времени. Благодаря разной длительности случайных интервалов времени существует ненулевая вероятность того, что интервал, выбранный одним из узлов, окажется меньше, чем у других вовлеченных в коллизию узлов, и он успеет «пропихнуть» свой кадр в канал без коллизии.
Начнем наше изучение протоколов произвольного доступа с одного из наиболее простых протоколов, так называемого дискретного протокола ALOHA. В нашем описании дискретной системы ALOHA мы будем предполагать следующее: Работа дискретного протокола ALOHA на каждом узле проста. Когда у узла есть новый кадр для передачи, он ждет, пока не начнется новый временной слот, после чего весь кадр передается в течение одного временного слота. Если передача проходит без коллизии, повторная передача кадра не требуется (узел может подготовить к передаче новый кадр). В случае коллизии узел обнаруживает факт коллизии, прежде чем заканчивается данный слот. Затем при наступлении каждого последующего слота с вероятностьюр узел передает кадр повторно до тех пор, пока кадр не будет передан без коллизии. Под повторной передачей кадра с вероятностью р мы подразумеваем, что узел как бы подбрасывает монетку. При этом кадр передается повторно, только если выпадает решка, что происходит с вероятностью р. При выпадении орла, что происходит с вероятностью (1 -р), узел пропускает данный временной интервал и подбрасывает монетку еще раз. Все узлы, вовлеченные в коллизию, подбрасывают свои монетки независимо друг от друга. Может показаться, что дискретный протокол ALOHA обладает рядом достоинств. В отличие от протоколов мультиплексирования с разделением канала, дискретный протокол ALOHA позволяет единственному активному в сети узлу передавать кадры без перерыва с максимальной скоростью R (узел называется активным, если у него есть кадр для передачи). Дискретный протокол ALOHA является в большой степени децентрализованным, так как каждый узел сам обнаруживает факт коллизии и независимо от других узлов принимает решение о времени повторной передачи. (Однако для использования дискретного протокола ALOHA требуется синхронизация узлов. Далее мы кратко обсудим непрерывную версию протокола ALOHA, а также протоколы CSMA, не требующие подобной синхронизации и, таким образом, являющиеся полностью децентрализованными.) Кроме того, ALOHA представляет собой чрезвычайно простой протокол. Дискретный протокол ALOHA хорошо работает в тех ситуациях, когда имеется только один активный узел, но какова его эффективность при наличии нескольких активных узлов? Эффективность дискретного протокола ALOHA снижается благодаря двум факторам. Во-первых, как показано на рис. 5.13, когда в сети несколько активных узлов, определенная доля слотов тратится впустую из-за коллизий. (Как показано на рисунке, в первом слоте в коллизию вовлекаются три узла. Затем узлу 2 удается передать кадр в четвертом слоте, узлу 1 — в восьмом слоте, а узлу 3 — в девятом.) Во-вторых, другая доля слотов тратится напрасно, когда все активные узлы одновременно отказываются от передачи. Дискретный протокол ALOHA работает продуктивно только в те слоты, когда передавать требуется ровно одному узлу. Слот, на протяжении которого передает только один узел, называется успешным слотом. Эффективность дискретного протокола коллективного доступа определяется долей успешных слотов в ситуации большого количества активных узлов, у каждого из которых всегда есть большое количество кадров для передачи. Обратите внимание, что, если вообще не использовать протокола коллективного доступа и после коллизии немедленно повторять передачу каждым из узлов, эффективность сети была бы равна нулю. Дискретный протокол ALOHA очевидно увеличивает эффективность сети, но насколько? Попытаемся определить максимальную эффективность дискретного протокола ALOHA. Чтобы упростить наши вычисления, немного изменим протокол, предположив, что каждый узел с вероятностью р пытается передать кадр с наступлением каждого нового слота. То есть мы предполагаем, что у каждого узла всегда есть кадр для передачи и узел всегда с вероятностью р пытается передать кадр независимо от того, новый это кадр или передаваемый повторно. Пусть в сети будет N узлов. В этом случае слот оказывается успешным, если один из узлов передает, а N – 1 узлов воздерживаются от передачи. Вероятность того, что некий конкретный узел будет передавать, равна р. Вероятность того, что остальные N- 1 узлов не будут передавать, равна (1 – p)(N-1). Таким образом, вероятность того, что данному узлу удастся успешно передать кадр, равна р(1 -p)(N-1). Поскольку существует N узлов, вероятность того, что повезет одному (любому) из них, равна Np(i -p)(N-1).
|