Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092), страница 124
Текст из файла (страница 124)
5.28, б. Принцип таков: каждый хост соединяется с сетью через интерфейс, содержащий дырявое ведро, то есть конечную внутреннюю очередь, Если пакет появляется в очерели, когда очередь полная, пакет игнорируется. другими словами, если несколько процессов хоста пытаются послать пакеты, когда в очереди уже стоит максимально допустимое число пакетов, новый пакет игнорируется. Такой интерфейс может быть реализован как аппаратно, так и программно операционной систе- Качество обслуживания 463 мой хоста.
Он был предложен Тернером (Тпгпег, 1986) и называется алгоритмом дырявого ведра. По сути это не что иное, как однолинейная система массового обслуживания с постоянным временем обслуживания. Хосту разрешается посылать в сеть один пакет за один такт. Опять же, это может быть реализовано интерфейсной картой либо операционной системой. Этот механизм преобразует неравномерный поток пакетов от процессов пользователя в равномерный поток пакетов в сети, сглаживая пики и значительно снижая вероятность перегрузки.
Когда размер всех пакетов одинаков (например, в ячейках АТМ), этот алгоритм может применяться, как описано ранее. Однако при использовании пакетов переменного размера часто бывает лучше ограничивать количество байтов, переданных в сеть за такт, нежели передавать один пакет за такт. Так, если правилом установлена передача 1024 байт за тактовый интервал, то за этот период могут быть переданы в сеть либо один пакет размером 1024 байта, либо два пакета по 512 байт, либо четыре пакета по 256 байт и т.
д. Если оставшееся количество байт меньше размера следующего пакета, следующий пакет должен ждать начала следующего такта. Реализация исходного злгоритма дырявого ведра проста, Дырявое ведро состоит из конечной очереди. Когда прибывает пакет и в очереди есть место, пакет добавляется к очереди, в противном случае пакет игнорируется. Если очередь не пуста, то в течение каждого тактового интервала в сеть передается по одному пакету, Алгоритм дырявого ведра со счетчиком байтов реализуется почти также. В каждом тактовом интервале значение счетчика устанавливается равным я. Если размер первого пакета в очереди меньше текущего значения счетчика, он передается, а значение счетчика уменьшается на его размер.
Если значение счетчика еще достаточно велико, могут быть посланы и другие пакеты. Когда значение счетчика становится меньше размера следующего пакета в очереди, передача прекращается до следующего такта, после чего все начинается сначала, а остаток счетчика обнуляется. В качестве примера представьте, что компьютер может производить данные со скоростью 25 млн байт в секунду (200 Мбит/с) и что сеть также работает на этой скорости. Однако маршрутизаторы могут поддерживать эту скорость передачи данных лишь на коротких интервалах (пока не заполнится их буферная память).
В течение больших интервалов времени они могут обеспечить не более 2 млн байт в секунду. Теперь предположим, что данные поступают пачками по 1 млн байт, одна пачка продолжительностью 40 мс в каждую секунду. Чтобы уменьшить среднюю скорость до 2 Мбайт/с, можно воспользоваться алгоритмом дырявого ведра с выходной скоростью р= 2 Мбайт/с и емкостью С= 1 Мбайт. Это означает, что пачки до 1 Мбайта могут обрабатываться без потерь и что такие пачки будут передаваться в сеть за 500 мс независимо от того, как быстро оии приходят. На рис. 5.29,а показан вход дырявого ведра, на который со скоростью 25 Мбайт/с поступает пачка в течение 40 мс.
На рис. 5.29, б показан выход, через который данные проходят с постоянной скоростью 2 Мбайт/с в течение 500 мс. 464 Глава 5. Сетевой уровень 500 Время, мс -В 500 Время, мс Время, мо -В. Время, мс 500 Время, мс Время,мс -Ф 500 Рис. 5.29. Вход дырявого ведра (а); выход дырявого ведра (б); выход маркерного ведра емкостью 250 Кбайт (в), 500 Кбайт (г) и 750 Кбайт (а); выход маркернаго верра емкостью 500 Кбайт на входе дырявого ведра со скоростью протекания 10 Мбайт/с (е) Алгоритм маркерного ведра олгоритм дырявого ведра формирует строгий выходной поток с постоянной скоростью, не зависящей от неравномерности входного потока.
Для многих приложений было бы лучше при поступлении больших пакетов данных немного увеличивать выходную скорость. Таким образом можно было бы попытаться создать более гибкий алгоритм, желательно, не теряющий данные. Одним нз таких алго- Качество обслуживания 465 ритмов является алгоритм маркерного ведра. В этом алгоритме ведро содержит маркеры, создаваемые через равные интервалы времени ЬТ секунд. На рис. 5.30, а изображено ведро с тремя маркерами и пятью пакетами, стоящими в очереди Чтобы передать один пакет, требуется удалить один маркер. На рис. 5.30, б мы видим, что три из пяти пакетов прошли в сеть, а оставшиеся два пакета остались ждать двух новых маркеров. Алгоритм маркерного ведра формирует график не так, как алгоритм дырявого ведра.
Алгоритм дырявого ведра не позволяет простаивающим хостам запасаться впрок разрешениями на передачу больших пакетов. Алгоритм маркерного ведра разрешает запасаться маркерами до определенного размера ведра а. Это свойство означает, что пачки (пакеты) с величиной до л могут быть переданы в сеть сразу, что создает некоторую неравномерность в выходном потоке, но обеспечивает быструю реакцию на неожиданные входные пачки. Еще одно различие двух алгоритмов заключается в том, что при переполнении маркерного ведра алгоритм игнорирует маркеры, но никогда не отвергает пакеты. Алгоритм дырявого ведра, напротив, при переполнении выбрасывает сами пакеты.
Возможен вариант алгоритма, при котором маркер может предоставлять право пересылать не один пакет, а 1 байт. Пакет пересылается только при наличии достаточного числа маркеров, чтобы покрьпь его длину. Лишние маркеры сохраняются для будущего использования. Алгоритмы дырявого и маркерного ведра могут использоваться не только для регулирования выхода хостов, но и для сглаживания трафика между маршрутизаторами. А различаются эти два алгоритма тем, что применение алгоритма маркерного ведра может заставить маршрутизатор остановить передачу пакетов, что может привести к потере данных.
Реализация исходного алгоритма маркерного ведра подразумевает наличие переменной, считающей маркеры. Счетчик увеличивается на единицу через равные интервалы времени ЬТи уменьшается при посылке пакета. Когда счетчик уменьшается до нуля, передача пакетов останавливается. В варианте с учетом количества пеРеданных байт счетчик увеличивается на л байт каждые ЬТ секунд и уменыпается иа размер переданного пакета. Суть алгоритма маркерного ведра состоит в том, что он допускает передачу данных пачками, но ограничивает длительность пачки. для примера рассмотрим Рис.
5,29, в, на котором изображено маркерное ведро емкостью 250 Кбайт. Маркеры появляются с частотой, соответствующей выходной скорости 2 Мбайт/с. Предположим, что маркерное ведро заполнено, когда прибывает пакет данных Размером 1 Мбайт.
Ведро может быть освобождено с максимальной скоростью 25 Мбайт/с примерно за 11 мс. Затем оно должно уменьшить скорость персдачи до 2 Мбайт/с, пока не будет передан весь входной пакет данных. При Расчете длительности выходной пачки (на максимальной скорости) нуж«о Учитывать, что пока ведро опорожняется, появляются новые маркеры. Прп 'длительности пачки 5 секунд, емкости маркерного ведра С байт, скорости появле"ния маркеров р байт/с, и максимальной выходной скорости М байт/с очевидно, что ззаксимальное количество переданных байтов в пачке будет равно С + ря байт.
466 Глава 5. Сетевой уровень Мы также знаем, что количество байтов, переданных в пачке с максимальной скоростью, равно М5. Таким образом, С+ рЯ= М5. Решив это уравнение, получим: 5= С/(М вЂ” р). При наших параметрах С= 250 Кбайт, М= 25 Мбайт/с и р = 2 Мбайт/с получаем длительность пачки около 11 мс. На рис. 5.29, г и д, показаны маркерные ведра емкостью 500 и 750 Кбайт соответственно. вдро аржит кары Один добавя в вад через к Сеть Рис. В.ЗО. Алгоритм маркврного ведра; до (в) и после (о) Недостатком алгоритма маркерного ведра является слишком большая скорость передачи данных при опустошении ведра, несмотря на то что длительность пачки можно регулировать тщательным подбором р и М.
Часто бывает желательно уменьшить пиковую скорость, не возвращаясь при этом к скорости алгоритма дырявого ведра. Один из способов получения более гладкого графика состоит в помещении дырявого ведра после маркерного ведра. Скорость дырявого ведра должна быть выше минимальной скорости маркерного ведра р, но ниже максимальной скорости сети. На рис.5.29, е показан выходной поток маркерного ведра емкостью 500 Кбайт, за которым установлено дырявое ведро со скоростью протекания, равной 10 Мбайт/с. Качество обслуживания 467 Управление такими схемами может оказаться непростым.
По сути, сеть должна имитировать алгоритм и гарантировать, что пакетов и байтов посылается не больше, чем разрешено, Тем не менее, эти методы позволяют формировать сетевой трафик, приводя его к более управляемому виду и обеспечивая тем самым выполнение требований к качеству обслуживания. Резервирование ресурсов Возможность управления трафиком — зто неплохой начальный шаг в деле обеспечения гарантированного качества обслуживания.
Однако на самом деле использование этих методов неявно означает, что все пакеты в потоке должны следовать по одному и тому же пути. При распределении их случайным образом между несколькими маршрутизаторами невозможно что-либо гарантировать. Следовательно, между источником и приемником должно быть установлено нечто вроде виртуального канала, и все пакеты, принадлежащие данному потоку, должны следовать по укаэанному маршруту. Раз у нас есть особый путь, по которому направляется поток, становится возможным резервирование ресурсов вдоль этого пути, что позволяет гарантировать доступность необходимой емкости.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
