Лекции 2010-го года (1130544), страница 42
Текст из файла (страница 42)
Поэтому вероятность коллизии чрезвычайно высока.В локальных сетях есть возможность определить, что делают другие станции, и толькопосле этого решать, что делать самому.Протоколы, которые реализуют именно эту идею – сначала определить, занят канал илинет и только после этого действовать - называются протоколами с обнаружениемнесущей CSMA (Carrier Sensitive Multiple Access).4.2.2.1.
Настойчивые и ненастойчивые CSMA-протоколыСогласно протоколу, который мы сейчас рассмотрим, станция, прежде чем что-либопередавать, определяет состояние канала. Если канал занят, то она ждет. Как только каналосвободился, она пытается начать передачу. Если при этом произошла коллизия, онаожидает случайный интервал времени и все начинает с начала. Этот протокол называетсянастойчивым CSMA-протоколом первого уровня или 1-настойчивым CSMA-протоколом,потому что станция, следуя этому протоколу, начинает передачу с вероятностью 1, кактолько обнаруживает, что канал свободен.Здесь важную роль играет задержка распространения сигнала в канале. Всегда есть шанс,что, как только одна станция начала передачу, другая также стала готовой передавать.Если вторая станция проверит состояние канала прежде, чем до нее дойдет сигнал отпервой о том, что она заняла канал, то вторая станция сочтет канал свободным и начнетпередачу.
В результате - коллизия. Чем больше время задержки, тем больше вероятностьтакого случая, тем хуже производительность канала.Однако даже если время задержки будет равно 0, коллизии все равно могут возникать.Например, если готовыми передавать оказались две станции, пока одна станцияпродолжает передавать. Они вежливо подождут, пока первая закончит передачу, а потомбудут состязаться между собой. Тем не менее, этот протокол более эффективен, чемлюбая из систем ALOHA, так как станция учитывает состояние канала, прежде чем начатьдействовать.9Другой вариант CSMA-протокола - ненастойчивый CSMA-протокол. Основное отличиеего от предыдущего в том, что готовая к передаче станция опрашивает канал. Если онсвободен, то она начинает передачу.
Если он занят, то она не будет настойчиво егоопрашивать в ожидании, когда он освободится, а будет делать это через случайныеотрезки времени. Это несколько увеличивает задержку при передаче, но общаяэффективность протокола возрастает.И, наконец, настойчивый CSMA-протокол уровня р. Он применяется к слотированнымканалам.
Когда станция готова к передаче, она опрашивает канал. Если он свободен, тоона с вероятностью р передает свой кадр и с вероятностью q=1-p ждет следующего слота.Так она действует, пока не передаст кадр. Если произошла коллизия во время передачи,она ожидает случайный интервал времени и опрашивает канал опять. Если при опросеканала он оказался занят, станция ждет начала следующего слота, и весь алгоритмповторяется.
На рисунке 4-3 показана пропускная способность этого протокола взависимости от нагрузки.Рисунок 4-3. Пропускная способность настойчивого CSMA-протокола уровня р посравнению с другими4.2.2.2. CSMA-протокол с обнаружением коллизийНастойчивые и ненастойчивые CSMA-протоколы – несомненное улучшение протоколаALOHA, т.к.
они начинают передачу, только проверив состояние канала. Другоеулучшение этого протокола, которое можно сделать, состоит в том, что станции должныуметь определять коллизии как можно раньше, а не по окончании отправки кадра. Этоэкономит время и пропускную способность канала. Такой класс протоколов известен, какCSMA/CD - Carrier Sensitive Multiple Access with Collision Detection, т.е. протоколмножественного доступа с контролем несущей и обнаружением коллизий. Протоколыэтого класса широко используется в локальных сетях.На рисунке 4-4 показана модель, которая используется во многих протоколах этогокласса. В момент t0 станция заканчивает передачу очередного кадра.
Все станции, укоторых есть кадр для передачи, начинают передачу. Естественно, происходят коллизии,которые быстро обнаруживаются сравнением отправленного сигнала с тем, который естьна линии. Обнаружив коллизию, станция сразу прекращает передачу на случайныйинтервал времени, после чего все начинается сначала. Таким образом, в работе протоколаCSMA/CD можно выделить три стадии: состязания, передачи и ожидания, когда неткадров для передачи.10Рисунок 4-4. Стадии работы протокола CSMA/CDРассмотрим подробнее алгоритм состязаний. Сколько времени станции, начавшейпередачу, нужно, чтобы определить коллизию? Обозначим через τ время распространениясигнала до самой удаленной станции на линии.
Для коаксиала в 1 км τ=5 мксек., в такомслучае минимальное время для определения коллизии будет равно 2τ. Поэтому станция неможет быть уверена, что она захватила канал до тех пор, пока не убедится, что в течение2τ секунд не было коллизий. Поэтому мы будем рассматривать период состязаний какслотированную систему ALOHA со слотом 2τ секунд на один бит. Захватив канал,станция может далее передавать кадр с любой скоростью.Стоит подчеркнуть, что обнаружение коллизий – это аналоговый процесс.
Поэтому, чтобыобнаруживать их, нужно использовать специальные кодировки на физическом уровне.Надо также отметить, что МАС-подуровень обеспечивает надежную передачу, используяспециальные приемы кодирования данных. Примеры таких кодировок мы рассматривалив гл. 2 (см. Манчестерские коды).4.2.3. Бесконфликтные протоколыХотя в протоколе CSMA/CD коллизии могут возникать только в период состязаний, темне менее, при больших t и коротких кадрах они съедают часть пропускной способностиканала. Здесь мы рассмотрим, как можно этих коллизий избежать.Мы будем предполагать, что у нас есть N станций с адресами от 0 до N-1. Все адресауникальны. Основным является вопрос: как определить, кто будет владеть каналом, когдазакончится текущая передача?4.2.3.1. Bit-Map-протоколИдея этого метода показана на рисунке 4-5.
Выделяют специальный период состязаний,где количество слотов равно числу станций. Каждая станция, имеющая кадр для передачи,проставляет 1 в свой слот. Поскольку мы рассматриваем канал с множественнымдоступом (т.е. все видят, что проходит в канале), то в конце состязаний все станции знают,кто будет передавать кадры и в каком порядке. Передача происходит в том же порядке, вкаком пронумерованы слоты. Раз станции знают, кто будет передавать и в каком порядке,то конфликтов не будет. Если станция опоздала с заявкой на передачу, то она должнаждать следующего периода состязаний, который начнется по окончании передач,заявленных на предыдущем периоде состязаний.
Такие протоколы, когда заявки напередачу откладываются и могут быть сделаны лишь в определенные периоды времени,называются протоколами с резервированием.Рисунок 4-5. Bit-Map-протокол11Теперь рассмотрим производительность этого метода. Будем для удобства измерять времяв количестве слотов состязаний.
Будем также предполагать, что передача одного кадрабудет занимать ровно 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.
Адресный счетчик12Этот метод имеет один существенный недостаток – он не справедливый: чем большеномер станции, тем скорее она захватит канал. В 1979 году Мок (Mok) и Уорд (Ward)предложили модификацию этого метода, когда у станций динамически изменяетсяприоритет, на основе которого определяется победитель. Победивший в текущихсостязаниях получает наименьший приоритет, который будет увеличиваться от состязанияк состязанию.4.2.4. Протоколы с ограниченным числом конфликтовРассмотренные нами только что протоколы показывают, что при небольшой загрузкеконфликты не опасны ввиду небольшой задержки на передачу. По мере роста нагрузкиони снижают эффективность использования канала.
Поэтому при высокой загруженностиканала арбитраж желателен и протоколы без коллизий предпочтительнее. А вот принизкой загрузке они лишь вызывают дополнительные накладные расходы.Естественно попытаться создать протокол, объединяющий достоинства этих двух группметодов, т.е. использовать состязания при небольших нагрузках и бесконфликтныеметоды - при высоких. Такие протоколы существуют и называются протоколами сограниченным числом конфликтов. Их изучением мы и закончим рассмотрение классапротоколов с контролем несущей.4.2.4.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
