Полный курс лекций 2009-го года (1130357), страница 42
Текст из файла (страница 42)
Настойчивые и ненастойчивые CSMA-протоколыСогласно протоколу, который мы сейчас рассмотрим, станция, прежде чем что-либо передавать,определяет состояние канала. Если канал занят, то она ждет. Как только канал освободился, она пытаетсяначать передачу. Если при этом произошла коллизия, она ожидает случайный интервал времени и всеначинает с начала. Этот протокол называется настойчивым CSMA-протоколом первого уровня или 1настойчивым CSMA-протоколом, потому что станция, следуя этому протоколу, начинает передачу свероятностью 1, как только обнаруживает, что канал свободен.Здесь важную роль играет задержка распространения сигнала в канале. Всегда есть шанс, что, кактолько одна станция начала передачу, другая также стала готовой передавать.
Если вторая станцияпроверит состояние канала прежде, чем до нее дойдет сигнал от первой о том, что она заняла канал, товторая станция сочтет канал свободным и начнет передачу. В результате - коллизия. Чем больше времязадержки, тем больше вероятность такого случая, тем хуже производительность канала.Однако даже если время задержки будет равно 0, коллизии все равно могут возникать. Например,если готовыми передавать оказались две станции, пока одна станция продолжает передавать. Онивежливо подождут, пока первая закончит передачу, а потом будут состязаться между собой.
Тем не менее,этот протокол более эффективен, чем любая из систем ALOHA, так как станция учитывает состояниеканала, прежде чем начать действовать.Другой вариант CSMA-протокола - ненастойчивый CSMA-протокол. Основное отличие его отпредыдущего в том, что готовая к передаче станция опрашивает канал. Если он свободен, то она начинаетпередачу.
Если он занят, то она не будет настойчиво его опрашивать в ожидании, когда он освободится, абудет делать это через случайные отрезки времени. Это несколько увеличивает задержку при передаче,но общая эффективность протокола возрастает.И, наконец, настойчивый CSMA-протокол уровня р.
Он применяется к слотированным каналам. Когдастанция готова к передаче, она опрашивает канал. Если он свободен, то она с вероятностью р передаетсвой кадр и с вероятностью q = 1 - p ждет следующего слота. Так она действует, пока не передаст кадр.Если произошла коллизия во время передачи, она ожидает случайный интервал времени и опрашиваетканал опять. Если при опросе канала он оказался занят, станция ждет начала следующего слота, и весьалгоритм повторяется. На рисунке 4-3 показана пропускная способность этого протокола в зависимостиот нагрузки.Рисунок 4-3. Пропускная способность настойчивого CSMA-протокола уровня рпо сравнению с другими4.2.2.2.
CSMA-протокол с обнаружением коллизийНастойчивые и ненастойчивые CSMA-протоколы – несомненное улучшение протокола ALOHA, т.к. ониначинают передачу, только проверив состояние канала. Другое улучшение этого протокола, котороеможно сделать, состоит в том, что станции должны уметь определять коллизии как можно раньше, а не поокончании отправки кадра. Это экономит время и пропускную способность канала. Такой класс протоколовизвестен, как CSMA/CD - Carrier Sense Multiple Access with Collision Detection, т.е. протокол множественногодоступа с контролем несущей и обнаружением коллизий. Протоколы этого класса широко используется влокальных сетях.На рисунке 4-4 показана модель, которая используется во многих протоколах этого класса.
Вмомент t0 станция заканчивает передачу очередного кадра. Все станции, у которых есть кадр дляпередачи, начинают передачу. Естественно, происходят коллизии, которые быстро обнаруживаютсясравнением отправленного сигнала с тем, который есть на линии. Обнаружив коллизию, станция сразупрекращает передачу на случайный интервал времени, после чего все начинается сначала. Такимобразом, в работе протокола CSMA/CD можно выделить три стадии: состязания, передачи и ожидания,когда нет кадров для передачи.Рисунок 4-4.
Стадии работы протокола CSMA/CDРассмотрим подробнее алгоритм состязаний. Сколько времени станции, начавшей передачу, нужно,чтобы определить коллизию? Обозначим через t время распространения сигнала до самой удаленнойстанции на линии. Для коаксиала в 1 км t = 5 мксек., в таком случае минимальное время для определенияколлизии будет равно 2t.
Поэтому станция не может быть уверена, что она захватила канал до тех пор,пока не убедится, что в течение 2t секунд не было коллизий. Поэтому мы будем рассматривать периодсостязаний как слотированную систему ALOHA со слотом 2t секунд на один бит. Захватив канал, станцияможет далее передавать кадр с любой скоростью.Стоит подчеркнуть, что обнаружение коллизий – это аналоговый процесс. Поэтому, чтобыобнаруживать их, нужно использовать специальные кодировки на физическом уровне.
Надо такжеотметить, что МАС-подуровень обеспечивает надежную передачу, используя специальные приемыкодирования данных. Примеры таких кодировок мы рассматривали в гл. 2 (см. Манчестерские коды).4.2.3. Бесконфликтные протоколыХотя в протоколе CSMA/CD коллизии могут возникать только в период состязаний, тем не менее, прибольших t и коротких кадрах они съедают часть пропускной способности канала.
Здесь мы рассмотрим, какможно этих коллизий избежать.Мы будем предполагать, что у нас есть N станций с адресами от 0 до N - 1. Все адреса уникальны.Основным является вопрос: как определить, кто будет владеть каналом, когда закончится текущаяпередача?4.2.3.1. Bit-Map-протоколИдея этого метода показана на рисунке 4-5. Выделяют специальный период состязаний, гдеколичество слотов равно числу станций.
Каждая станция, имеющая кадр для передачи, проставляет 1 всвой слот. Поскольку мы рассматриваем канал с множественным доступом (т.е. все видят, что проходит вканале), то в конце состязаний все станции знают, кто будет передавать кадры и в каком порядке.Передача происходит в том же порядке, в каком пронумерованы слоты. Раз станции знают, кто будетпередавать и в каком порядке, то конфликтов не будет. Если станция опоздала с заявкой на передачу, тоона должна ждать следующего периода состязаний, который начнется по окончании передач, заявленныхна предыдущем периоде состязаний.
Такие протоколы, когда заявки на передачу откладываются и могутбыть сделаны лишь в определенные периоды времени, называются протоколами с резервированием.Рисунок 4-5. Bit-Map-протоколТеперь рассмотрим производительность этого метода. Будем для удобства измерять время вколичестве слотов состязаний. Будем также предполагать, что передача одного кадра будет заниматьровно d таких слотов.
Для станции с небольшим номером, например, 0 или 1, время ожидания на передачув среднем будет равняться 1,5 N, потому что она, пропустив начало состязаний, будет ждать 0,5 N впервом периоде состязаний и N единиц времени во втором. Другая участь у станций со старшиминомерами. Эти станции будут ожидать в среднем N/2 слотов до начала передачи. Таким образом, в среднемлюбая станция должна будет ждать N слотов до передачи.При небольшой нагрузке накладные расходы на передачу одного кадра будут N бит, аэффективность передачи одного кадра - d/ (d+N), где N - накладные расходы на передачу кадра.
Приплотной загрузке, когда практически каждая станция каждый раз что-то посылает, накладные расходыбудут 1 бит на кадр, т.е. d/ (d+1). Средняя задержка кадра будет равна средней задержке кадра внутриочереди в станции плюс N(d+1) / 2 слотов ожидания, когда кадр достигнет заголовка очереди.
Отсюдавидно, что с ростом N, хотя накладные расходы на передачу одного кадра и падают, задержка кадра вканале существенно возрастает, и эффективность падает. Следует также отметить, что если d и N сопоставимые величины, то значительную часть пропускной способности канала мы будем тратить насостязания.4.2.3.2. Адресный счетчикОдин из недостатков bit-map протокола - затраты в 1 бит на кадр. При коротких кадрах этонакладно. Есть другая возможность, позволяющая повысить эффективность использования канала.
Онаоснована на двоичном представлении адреса станции.В этом методе каждая станция, готовая к передаче, выставляет свой адрес бит за битом, начиная состаршего разряда. Эти разряды подвергаются логическому сложению. Если станция выставила наочередном шаге 0, а результат логического сложения - 1, то она должна ждать и в текущих состязанияхучастия не принимает. Этот метод проиллюстрирован на рисунке 4-6. Эффективность использованияканала в этом методе - d/ (d+ lnN). Если структура заголовка кадра была выбрана так, чтобы его можнобыло использовать для выбора очередной станции для передачи, то lnN битов также будет использовано,тем самым эффективность использования канала достигнет 100%.Рисунок 4-6.
Адресный счетчикЭтот метод имеет один существенный недостаток – он не справедливый: чем больше номер станции,тем скорее она захватит канал. В 1979 году Мок (Mok) и Уорд (Ward) предложили модификацию этогометода, когда у станций динамически изменяется приоритет, на основе которого определяется победитель.Победивший в текущих состязаниях получает наименьший приоритет, который будет увеличиваться отсостязания к состязанию.4.2.4. Протоколы с ограниченным числом конфликтовРассмотренные нами только что протоколы показывают, что при небольшой загрузке конфликты неопасны ввиду небольшой задержки на передачу. По мере роста нагрузки они снижают эффективностьиспользования канала.
Поэтому при высокой загруженности канала арбитраж желателен и протоколы безколлизий предпочтительнее. А вот при низкой загрузке они лишь вызывают дополнительные накладныерасходы.Естественно попытаться создать протокол, объединяющий достоинства этих двух групп методов, т.е.использовать состязания при небольших нагрузках и бесконфликтные методы - при высоких. Такиепротоколы существуют и называются протоколами с ограниченным числом конфликтов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
