Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092), страница 81
Текст из файла (страница 81)
4.5, с ее дискретными интервалами конкуренции. Протокол битовой карты В первом протоколе без столкновений, который мы рассмотрим, называющемся основным методом битовой карты, каждый период конкуренции состоит ровно из А(временных интервалов. Если у станции О есть кадр для передачи, она передает единичный бит во время О-го интервала. Другим станциям не разрешается передача в это время. Во время интервала 1 станция 1 также сообщает, есть ли у нее кадр для передачи, передавая бит 1 или О. В результате к окончанию интервала М все А' станций знают, кто хочет передавать.
В этот момент они начинают передачу в соответствии со своим порядком номеров (рис. 4.6). Поскольку все знают, чья очередь передавать, столкновений нет, После того как последняя станция передает свой кадр, что все станции отслеживают, прослушивая линию, начинается новый период подачи заявок из М интервалов. Если станция переходит в состояние готовности (получает кадр для передачи) сразу после того, как она отказалась от передачи, это значит, что ей не повезло и она Протоколы коллективного доступа 305 должна ждать следуюшего цикла. Протоколы, в которых намерение передавать объявляется всем перед самой передачей, называются протоколами с резерви- рованием. Кедры В интервалов В интервалое конкуренции 1 о 01234 5В7 01234 ВВ7 ПЕПЕЛ Н Е [11 (П~~~ ~ Рис.
4.6. Базовый протокол битовой карты Двоичный обратный отсчет Недостатком базового протокола бит-карты являются накладные расходы в 1 бит на станцию. Используя двоичный адрес станции, можно улучшить эффективность канала, Станция, желаюшая занять канал, объявляет свой адрес в виде битовой строки, начиная со старшего бита, Предполагается, что все адреса станций имеют одинаковую длину. Биты адреса в каждой позиции логически складываются (логическое ИЛИ). Мы будем называть этот протокол протоколом с двоич- Оценим производительность такого протокола. Для удобства будем измерять время в однобитовых интервалах периода подачи заявок, при этом кадр данных состоит из И единиц времен~.
При слабой загрузке канала бит-карта просто будет повторяться снова и снова, изредка перемежаясь кадрами. Рассмотрим эту ситуацию с точки зрения станции с небольшим номером, например, О или 1. Обычно в тот момент, когда у нее возникает потребность в передаче, текущий интервал времени уже находится где-то в середине бит-карты. В среднем станция будет ждать йг/2 интервалов до окончания текущего периода резервирования и еще У интервалов следующего (своего) периода резервирования, не считая кадров, передаваемых между двумя этими периодами, прежде чем она сможет начать передачу.
Перспективы станций с большими номерами более радужны. В среднем время ожидания передачи составит половину цикла (Лг/2 однобитовых интервалов). Станциям с большими номерами редко приходится ждать следующего цикла. Поскольку станциям с небольшими номерами приходится ждать в среднем 1,5Х интервалов, а станциям с большими номерами. — У/2 интервалов, среднее время ожидания для всех станций составляет лг интервалов.
При низкой загрузке канала его производительность легко сосчитать. Накладные расходы на кадр составляют л1 бит, и при длине кадра в Ы бит эффективность равна Ы/(лг+ И). При сильной загруженности канала, когда все станции хотят что-то передать, период подачи заявок из Убит чередуется с йг кадрами. При этом накладные расходы на передачу одною кадра составляют всего один бит, а эффективность равна и/(ц + 1). Среднее время задержки для кадра будйт равно сумме времени ожидания в очереди внутри своей станции и дополнительных У(п'+ 1)/2 однобитовых интервалов, когда он попадет в начало своей внутренней очереди. 306 Глава 4.
Подуровень управления доступом к среде ньви обратным отсчетом. Он используется в сети !)ата!пг (ггазег, 1987). Неявно предполагается, что задержки распространения сигнала пренебрежимо малы, поэтому станции слышат утверждаемые номера практически мгновенно. Во избежание конфликтов следует применить правило арбитража; как только станция с 0 в старшем бите адреса видит, что в суммарном адресе этот 0 заменился единицей, она сдается и ждет следующего цикла. Например, если станции 0010, 0100, 1001 и 1010 конкурируют за канал, то в первом битовом интервале они передают биты О, О, 1 и 1 соответственно. В этом случае суммарный первый бит адреса будет равен 1. Следовательно, станции с номерами 0010 и 0100 считаются проигравшими, а станции 1001 и 1010 продолжают борьбу.
Следующий бит у обеих оставшихся станций равен 0 — таким образом, обе продолжают. Третий бит равен 1, поэтому станция 1001 сдается. Победителем оказывается станция 1010, так как ее адрес наибольший. Выиграв торги, она может начать передачу кадра, после чего начнется новый цикл торгов. Схема протокола показана на рис. 4.7. Данный метод предполагает, что приоритет станции напрямую зависит от ее номера В некоторых случаях такое жесткое правило может играть положительную, в некоторых — отрицательную роль. Однобитовые отсчеты времени 0123 0010 0100 1001 100- 1010 1010 Результат 1 0 1 0 Станции 0010 Станция 1001 и 0100 видят ету видит ету единицу единицу и еда слм и сдастся Рио.
4.7. Протокол с двоичным обратным отсчетом. Прочерк означает молчание Эффективность использования канал» при этом методе составляет Н/(Н+ !Ой,М). Однако можно так хитро выбрать формат кадра, что его первое поле будет содержать адрес отправителя, тогда люке эти!ой,Н бит не пропадуг зря и эффективность составит 100 Ж. Мок (М<Й) и Уард (%'агд) в 1979 году описали вариант протокола с обратным отсчетом, в котором использовался параллельный, а не последовательный интерфейс. Они также предложили использовать виртуальные номера станций. После каждой передачи станции, которая успешно послала ющр, присваивается виртуальный номер О, тем самым дается возможность захвата канала станциями, которые молчат слишком долго.
Например, если станции С, Н, Р, А, С, В, Е, Р имели приоритеты 7, 6, 5, 4, 3, 2, 1 и 0 соответственно, тогда при успешной передаче станции 1) она помещается в конец списка, получая номер О. Приоритеты старших Протоколы коллективного доступа 307 станций С и Н остаются неизменными (7 и 6), а приоритеты остальных станций увеличиваются на 1 (например, приоритет А был 4, а стал 5). Таким образом, на следующем цикле формируется такой список: С, Н, А, С, В, Е, Г, Р. Теперь станция р сможет получить доступ к каналу, только если он больше никому не нужен. Двоичный обратный отсчет является примером простого, элегантного и эффективного протокола, который еще предстоит открыть заново разработчикам будущих сетей.
Хочется надеяться, что когда-нибудь он займет свою нишу в сетевых технологиях. Протоколы с ограниченной конкуренцией Итак, мы рассмотрели две основные стратегии предоставления доступа к каналу в кабельных сетях: соревнование, как в СИМА, и бесконфликтные методы. Каждую стратегию можно оценить по двум важным параметрам; времени задержки прн низкой загрузке канала и эффективности канала при большой загрузке. В условиях низкой загрузки конфликты (то есть чистая или дискретная системы АЬОНА) предпочтительнее, так как время задержки в таких системах меньше. По мере роста загруженности канала системы со столкновениями становятся все менее привлекательными, поскольку возрастают накладные расходы, связанные с конфликтами.
Для бесконфликтных протоколов справедливо обратное. При низкой нагрузке у них довольно высокое время задержки, но по мере увеличения нагрузки эффективность использования канала не уменьшается, как у конфликтных протоколов, а наоборот, возрастает. Очевидно, было бы неплохо объединить лучшие свойства обеих стратегий и получить протокол, использующий разные стратегии при разной загруженности канала.
Такие протоколы мы будем называть протоколами с ограниченной конкуренцией. Они в самом деле существуют, и их рассмотрением мы завершим изучение сетей с опросом носителя. До сих пор мы рассматривали только симметричные протоколы коллективного доступа, в которых каждая станция пытается получить доступ к каналу с равной вероятностью р. Интересно, что производительность всей системы может быть улучшена при использовании асимметричного протокола, в котором станциям назначаются различные вероятности. Прежде чем приступить к рассмотрению асимметричных протоколов, давайте кратко рассмотрим производительность в симметричном случае.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
