Чистый протокол ALOHA

Дискретный протокол ALOHA требует, чтобы все узлы синхронизировали время начала передачи кадров. Собственно, первый протокол ALOHA не был дискретным, представляя собой полностью децентрализованный протокол. В так называемом чистом протоколе ALOHA, когда прибывает первый кадр (то есть дейтаграмма сетевого уровня передается на более низкий уровень передающего узла), узел немедленно передает весь кадр целиком в широковещательный канал. Если переданный кадр сталкивается с одним или несколькими другими кадрами, с вероятностью р узел немедленно передает кадр повторно. В противном случае узел выжидает в течение времени, необходимого для передачи одного кадра, после чего опять с вероятностью р передает кадр либо пережидает еще один интервал времени.
Чтобы определить максимальную эффективность чистого протокола ALOHA, сконцентрируем наше внимание на отдельном узле. Мы будем использовать те же допущения, что и в случае дискретного протокола ALOHA, и примем за единицу времени интервал (слот), требующийся для передачи одного кадра. В любой момент времени вероятность того, что узел передает кадр, равна р. Предположим, передача этого кадра началась в момент времени t(0). Как видно из рис. 5.14, чтобы этот кадр был передан успешно, никакой другой узел не должен начать свою передачу во временном интервале [t(0) - 1, t(0)], так как иначе такая передача совпадет по времени с началом передачи нашего узла. Вероятность того, что остальные узлы не начнут передачу в течение этого интервала времени, равна р(1 -p)(N-1). Аналогично, никакой другой узел не должен начать свою передачу, пока передает наш узел, так как такая передача также приведет к коллизии, но уже с концом нашего кадра. Вероятность этого события также равна р(1 – p)(N-1). Таким образом, вероятность успешной передачи кадра данным узлом равна р(1 – р)(2(N-1)). При стремлении количества узлов к бесконечности максимальная эффективность чистого протокола ALOHA будет равна всего лишь 1/(2е), то есть половине от максимальной эффективности дискретного протокола ALOHA. Такова плата за полную децентрализацию.

19. Протокол CSMA и CSMA/CD

Слушайте, прежде чем говорить. Если кто-то уже говорит, подождите, пока он не закончит. В мире компьютерных сетей это правило называется контролем несущей и заключается в том, что узел прослушивает канал перед тем, как начать передачу. Если по каналу передается кадр, узел выжидает («отступает») в течение случайного периода времени, после чего снова опрашивает канал. Если канал оказывается свободным, узел начинает передачу кадра. В противном случае узел ждет в течение еще одного случайного интервала времени и повторяет весь процесс.
□ Если кто-то начал говорить, прекращайте разговор. В мире компьютерных сетей это правило называется обнаружением коллизий. Оно заключается в том, что во время передачи узел прослушивает канал. Если он обнаруживает, что другой узел в этот момент времени тоже ведет передачу, он прекращает свою передачу и с помощью протокола вычисляет время своей следующей попытки передачи.
Эти два правила реализованы в семействе протоколов CSMA (Carrier Sense Multiple Access — множественный доступ с контролем несущей) и CSMA/CD (CSMA with Collision Detection — множественный доступ с контролем несущей и обнаружением коллизий). Было разработано множество вариантов протоколов CSMA и CSMA/ CD.

Кроме того, протокол CSMA/CD, применяемый в Ethernet-сети, мы подробно обсудим в разделе «Ethernet», а пока рассмотрим некоторые фундаментальные характеристики протоколов CSMA и CSMA/CD.

Первый вопрос о протоколе CSMA, который может возникнуть, состоит в том, как вообще могут возникать коллизии, если все узлы прослушивают несущую? В самом деле, ведь узел воздерживается от передачи, если он замечает, что канал занят.

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

В момент времени t0 узел В опрашивает канал и приходит к выводу, что канал свободен, так как никакой другой узел в этот момент не ведет передачу. Поэтому узел В начинает передачу, и передаваемый им сигнал распространяется по широковещательному носителю в обоих направлениях со скоростью, близкой к скорости света, но конечной. В момент времени t(1)(t(1) > t(0)) у узла D появляется кадр для передачи. Хотя узел В в этот момент уже передает данные, передаваемый им сигнал еще не достиг узла D, таким образом, узел D полагает, что канал свободен. Поэтому в соответствии с протоколом CSMA узел D начинает передачу своего кадра.

Немного позднее сигнал, передаваемый узлом В, смешивается с сигналом узла D — возникает коллизия. Из рисунка видно, что производительность широковещательного канала в значительной степени зависит от времени прохождения сигнала по каналу от одного узла до другого. Чем больше это время, тем выше вероятность коллизий, вызванных тем, что сигнал уже начавшего передачу узла не успел достичь другого узла, готового к передаче.

Изображенные на рис. 5.15 узлы не обнаруживают коллизию. Оба узла (В и D) продолжают передавать свои кадры целиком и после коллизии. При использовании протокола с обнаружением коллизий узел прекращает передачу, как только он обнаруживает коллизию. На рис. 5.16 показан тот же сценарий, что и на рис. 5.15, но в этом случае узлы прекращают передачу, обнаружив коллизию. Очевидно, добавление способности обнаружения коллизий повышает производительность протокола, так как продолжение передачи кадров в случае коллизии не имеет смысла и приводит лишь к дополнительным потерям времени. Протокол Ethernet, который будет рассматриваться в разделе «Ethernet», представляет собой протокол CSMA с обнаружением коллизий.

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

Как уже упоминалось, двумя желательными свойствами протокола коллективного доступа являются, во-первых, возможность единственного активного узла передавать свои данные с максимальной пропускной способностью канала R бит/с, во-вторых, возможность для каждого из М активных узлов передавать свои данные со скоростью R/M бит/с. Протоколы ALOHA и CSMА удовлетворяют первому требованию, но не удовлетворяют второму. Это подвигло исследователей на создание нового класса протоколов — протоколов последовательного доступа. Как и в случае с протоколами произвольного доступа, существуют десятки протоколов последовательного доступа, и у каждого есть множество вариантов. Здесь мы рассмотрим два наиболее важных протокола последовательного доступа. Первый из них — протокол опроса. При использовании протокола опроса один из узлов должен быть назначен главным (управляющим) узлом. Главный узел поочередно опрашивает все узлы. Например, сначала главный узел посылает сообщение узлу 1, сообщая ему, что он может передать некоторое максимальное количество кадров. После того как узел 1 передает несколько кадров, главный узел разрешает передать некоторое количество кадров узлу 2. (Главный узел может определить момент завершения передачи очередным узлом по отсутствию сигнала в канале.) Данная процедура продолжается бесконечно, при этом главный узел в цикле опрашивает все узлы.