Э. Таненбаум - Компьютерные сети. (4-е издание) (PDF) (1130118), страница 77
Текст из файла (страница 77)
Способ кодирования сигнала должен304Протоколы коллективного доступаГлава 4, Подуровень управления доступом к средедолжна ждать следующего цикла. Протоколы, в которых намерение передаватьобъявляется всем перед самой передачей, называются протоколами с резерви-позволять определять столкновения (например, столкновение двух сигналовв О В в явном виде не так просто обнаружить). По этой причине используетсяспециальное кодирование.Передающая станция должна постоянно прослушивать канал, выявляя всплески шума, которые могут означать столкновение.
По этой причине CSMA/CD смоноканалом считается полудуплексной системой. Станция не может одновременно передавать и принимать кадры, поскольку задействован механизм обратной связи для определения столкновений.Во избежание неправильного понимания вопроса следует также отметить, чтони один протокол подуровня MAC не может гарантировать надежную доставку.Даже при отсутствии столкновений получатель может не получить правильнуюкопию кадра по различным причинам (например, из-за нехватки места в буфереили пропущенного прерывания).рованием.8 интерваловконкуренции0 12 3 4 6 6 /11 18 интерваловконкуренцииКадры1370 123 4 5 6 71110151213 4 5 6 72Рис.
4.6. Базовый протокол битовой картыОценим производительность такого протокола. Для удобства будем измерятьвремя в однобитовых интервалах периода подачи заявок, при этом кадр данныхсостоит из d единиц времени. При слабой загрузке канала бит-карта просто будет повторяться снова и снова, изредка перемежаясь кадрами.Рассмотрим эту ситуацию с точки зрения станции с небольшим номером, например, 0 или 1. Обычно в тот момент, когда у нее возникает потребность в передаче, текущий интервал времени уже находится где-то в середине бит-карты.В среднем станция будет ждать N/2 интервалов до окончания текущего периодарезервирования и еще N интервалов следующего (своего) периода резервирования, не считая кадров, передаваемых между двумя этими периодами, прежде чемона сможет начать передачу.Перспективы станций с большими номерами более радужны.
В среднем время ожидания передачи составит половину цикла (N/2 однобитовых интервалов).Станциям с большими номерами редко приходится ждать следующего цикла.Поскольку станциям с небольшими номерами приходится ждать в среднем 1,5JVинтервалов, а станциям с большими номерами^— N/2 интервалов, среднее времяожидания для всех станций составляет N интервалов. При низкой загрузке канала его производительность легко сосчитать. Накладные расходы на кадр составляют JV бит, и при длине кадра в d бит эффективность равна d/(N + d).При сильной загруженности канала, когда все станции хотят что-то передать,период подачи заявок из N бит чередуется с N кадрами.
При этом накладные расходы на передачу одного кадра составляют всего один бит, а эффективность равнаd/(d +1). Среднее время задержки для кадра будет равно сумме времени ожидания в очереди внутри своей станции и дополнительных N(d + l)/2 однобитовыхинтервалов, когда он попадет в начало своей внутренней очереди.Протоколы без столкновенийХотя в протоколе CSMA/CD столкновения не могут происходить после того, какстанция захватывает канал, они могут случаться в период конкуренции. Этистолкновения снижают производительность системы, особенно при большойдлине кабеля (то есть при больших т) и коротких кадрах. Метод CSMA/CD оказывается не универсальным. В данном разделе мы рассмотрим протоколы, которые решают проблему борьбы за право занять канал, причем делают это даже безпериода конкуренции.В описываемых далее протоколах предполагается наличие N станций, у каждой из которых есть постоянный уникальный адрес в пределах от 0 до N- 1.
То,что некоторые станции могут часть времени оставаться пассивными, роли не играет. Также предполагается, что задержка распространения сигнала пренебрежимо мала. Главный вопрос сохраняется: какой станции будет предоставлен каналпосле передачи данного кадра? Мы будем по-прежнему использовать модель,изображенную на рис. 4.5, с ее дискретными интервалами конкуренции.Протокол битовой картыВ первом протоколе без столкновений, который мы рассмотрим, называющемсяосновным методом битовой карты, каждый период конкуренции состоит ровноиз N временных интервалов.
Если у станции 0 есть кадр для передачи, она передает единичный бит во время 0-го интервала. Другим станциям не разрешается передача в это время. Во время интервала 1 станция 1 также сообщает, есть ли у неекадр для передачи, передавая бит 1 или 0. В результате к окончанию интервала Nвсе Дистанций знают, кто хочет передавать. В этот момент они начинают передачув соответствии со своим порядком номеров (рис. 4.6).Поскольку все знают, чья очередь передавать, столкновений нет.
После тогокак последняя станция передает свой кадр, что все станции отслеживают, прослушивая линию, начинается новый период подачи заявок из N интервалов. Если станция переходит в состояние готовности (получает кадр для передачи) сразу после того, как она отказалась от передачи, это значит, что ей не повезло и она305Двоичный обратный отсчетLНедостатком базового протокола бит-карты являются накладные расходы в 1 битна станцию.
Используя двоичный адрес станции, можно улучшить эффективность канала. Станция, желающая занять канал, объявляет свой адрес в виде битовой строки, начиная со старшего бита. Предполагается, что все адреса станцийимеют одинаковую длину. Биты адреса в каждой позиции логически складываются (логическое ИЛИ).
Мы будем называть этот протокол протоколом с двоич-306Глава 4. Подуровень управления доступом к среденым обратным отсчетом. Он используется в сети Datakit (Fraser, 1987). Неявнопредполагается, что задержки распространения сигнала пренебрежимо малы, поэтому станции слышат утверждаемые номера практически мгновенно.Во избежание конфликтов следует применить правило арбитража: как толькостанция с 0 в старшем бите адреса видит, что в суммарном адресе этот 0 заменился единицей, она сдается и ждет следующего цикла. Например, если станции0010, 0100, 1001 и 1010 конкурируют за канал, то в первом битовом интервалеони передают биты 0, 0, 1 и 1 соответственно.
В этом случае суммарный первыйбит адреса будет равен 1. Следовательно, станции с номерами 0010 и 0100 считаются проигравшими, а станции 1001 и 1010 продолжают борьбу.Следующий бит у обеих оставшихся станций равен 0 — таким образом, обепродолжают. Третий бит равен 1, поэтому станция 1001 сдается.
Победителемоказывается станция 1010, так как ее адрес наибольший. Выиграв торги, она может начать передачу кадра, после чего начнется новый цикл торгов. Схема протокола показана на рис. 4.7. Данный метод предполагает, что приоритет станциинапрямую зависит от ее номера. В некоторых случаях такое жесткое правило может играть положительную, в некоторых — отрицательную роль.Однобитовые отсчетывремени0 12 30 0 100| 0 1 0 01 01 0 0 1|10 0 -10 1010 10Результат10 10\Станции 0010Станция 1001и 0100 видят эту видит эту единицуи сдаетсяединицу и сдаютсяРис. 4 . 7 . Протокол с двоичным обратным отсчетом.
Прочерк означает молчаниеЭффективность использования канала при этом методе составляет d/(d + g^Однако можно так хитро выбрать формат кадра, что его первое поле будет содержать адрес отправителя, тогда даже эти logjiV бит не пропадут зря и эффективность составит 100 %.Мок (Мок) и Уард (Ward) в 1979 году описали вариант протокола с обратнымотсчетом, в котором использовался параллельный, а не последовательный интерфейс. Они также предложили использовать виртуальные номера станций. Послекаждой передачи станции, которая успешно послала кадр, присваивается виртуальный номер 0, тем самым дается возможность захвата канала станциями, которыемолчат слишком долго. Например, если станции С, Я, D, A, G, В, Е, F имели приоритеты 7, 6, 5, 4, 3, 2, 1 и 0 соответственно, тогда при успешной передаче станции D она помещается в конец списка, получая номер 0.
Приоритеты старшихПротоколы коллективного доступа307станций С и Н остаются неизменными (7 и 6), а приоритеты остальных станцийувеличиваются на 1 (например, приоритет А был 4, а стал 5). Таким образом, наследующем цикле формируется такой список: С, И, A, G, В, Е, F, D. Теперь станцияD сможет получить доступ к каналу, только если он больше никому не нужен.Двоичный обратный отсчет является примером простого, элегантного и эффективного протокола, который еще предстоит открыть заново разработчикамбудущих сетей.
Хочется надеяться, что когда-нибудь он займет свою нишу в сетевых технологиях.Протоколы с ограниченной конкуренциейИтак, мы рассмотрели две основные стратегии предоставления доступа к каналув кабельных сетях: соревнование, как в CSMA, и бесконфликтные методы. Каждую стратегию можно оценить по двум важным параметрам: времени задержкипри низкой загрузке канала и эффективности канала при большой загрузке. В условиях низкой загрузки конфликты (то есть чистая или дискретная системыALOHA) предпочтительнее, так как время задержки в таких системах меньше.По мере роста загруженности канала системы со столкновениями становятся всеменее привлекательными, поскольку возрастают накладные расходы, связанныес конфликтами.
Для бесконфликтных протоколов справедливо обратное. Принизкой нагрузке у них довольно высокое время задержки, но по мере увеличениянагрузки эффективность использования канала не уменьшается, как у конфликтных протоколов, а наоборот, возрастает.Очевидно, было бы неплохо объединить лучшие свойства обеих стратегийи получить протокол, использующий разные стратегии при разной загруженности канала. Такие протоколы мы будем называть протоколами с ограниченнойконкуренцией. Они в самом деле существуют, и их рассмотрением мы завершимизучение сетей с опросом носителя.До сих пор мььрассматривали только симметричные протоколы коллективного доступа, в которых каждая станция пытается получить доступ к каналу с равной вероятностью р. Интересно, что производительность всей системы можетбыть улучшена при использовании асимметричного протокола, в котором станциям назначаются различные вероятности.Прежде чем приступить к рассмотрению асимметричных протоколов, давайтекратко рассмотрим производительность в симметричном случае.
Предположим,что k станций борются за доступ к каналу. Вероятность передачи каждой станции в каждый интервал времени равна р. Вероятность того, что какая-то станцияуспешно получит доступ к каналу на данный интервал времени, равна kp(l -рУ'1Чтобы найти оптимальное значение вероятности р, продифференцируем данноевыражение по р, приравняем результат к нулю и решим полученное уравнениеотносительно р. В результате мы получим, что наилучшее значение р равно 1/k.Заменяя в формуле р на 1/k, получаем вероятность успеха при оптимальном значении р:Р[успех при оптимальной вероятности р] = —— .(4-4)Протоколы коллективного доступа3 0 8 Глава 4, Подуровень управления доступом к средеЗависимость этой вероятности от количества готовых станций графическипоказана на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
