В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 124
Текст из файла (страница 124)
17.3. Прн справедливой организации очередей каждый входящий пакет помещается в соответствующую очередь. Очереди обслуживаются в циклическом порядке, та есть из каждой очереди пгючередно выбирается олин пакет. Пустые очереди пропускаются. Такая схема является справедливой в том смысле, что каждому непустому потоку удается послать ровно олин пакет за цикл. Кроме того, эта схема представляет собой форму балансировки нагрузки между потоками.
Также обратите внимание н» то, что при такой схеме потоку нет смысла быть жадным. Единственное, что получит эгоистичный поток, это уллинение своей очереди н соответствующее увеличение задержки в доставке пакетов, при этом его поведение никак не скажется на других потоках. Серьезный недостаток схемы справедливой организации очередей заключается в том, что короткие пакеты получают менее качественное обслуживание. Потоки с большим средним размером пакета получают большую долю пропускной способности па сравнению с потоками с меньшим средним размером пакетов. Причина этого в там, чта каждая очередь передает па одному пакету за цикл.
Этот недостаток можно преодолеть с помогцью схемы справедливой организации очередей с побитовым циючолг (В11-Воцпг1 Гап Яцец1пй, ВКГО), в которой при планировании пакетов учитываются не только идентификаторы пакетов, но и длина пакетов. Эта техника описывается в 1701.
Чтобы понять, как работает метод справедливой организации очередей с побитовым циклом, рассмотрим сначала идеальную политику, которая на практике не применяется. Сформируем несколько очередей, как в схеме справедливой оргашгзацгги очередей, но будем передавать в каждом цикле нс целый пакет, а всего один бит. Таким образом, более длинные пакеты не получат преимущества, и каждому источнику будет предоставлена равная пропускная способность, В частности, если илгеются ггг очередей и в каждой нз этих очередей всегда есть пакет для передачи, тогда каждая очередь получает ровно 1/ггг*достуггной пропускной способности. Такой идеальный побитовый подход известен также как разделение процессора (Ргосеззог ЯЬаг1пя, РВ).
Чтобы дальнейшее обсуждение было понятнее, введем следующие обозначения: + гг(г) — количество циклов обслугкивапия с разделением процессора, которые проггзошли к моменту времени Г, норма лизован нее относительна выходной скорости передачи данных; + гтг(Г) — количество непустых очередей в момент времени ц + Р," — время передачи для пакета г' в очереди а, приведенное к выходной скорости передачи ланных; + т", — время прибытггя пакета г в очередь ой + 5г — значение Й(Г) в момент начала передачи пакета г в очереди од + Г," — значение й(г) в момент завершения передачи пакета г в очереди сс 17.2, Дисциплина очередей 541 Очередь а 1 ----а- Очередь Р Очередь у г я(!) ВЧ-0 а Р,=З РЧ =3 0 О Б;=1 РЧ =г 4=2 РР=4 , '4=2 Очередь а Пакет 1 Пакет 2 Очередь В Очередь у Лвквт 1 Пакет 2 Пакет 1 1 1 2 зх =З ° ч Рх=1 Рвальиав время прибытия В Время передачи Р, Виртуальное время начала Гя Виртуальное время конца Р 0 3 0 3 2 1 3 4 1 2 1 4 1 2 2 6 3 3 2 б гх=4 0 4 ч 10 11 6 Г," =5" +Р,", 5," = шах[Е,."и )7(т, )].
(17.1) 12 6 ч 540 Глава 17. Интегрированные и дифференцирсваннгве службы Значение )г(г) можно рассматривать как виртуальное время, соответствутсп ующее скорости обслуживания пакета, находящегося в начале очереди. Эквиваленту ентное определение выглядит следующим образом: й'(г) = — )7(1) = г) г)г шах[1, У(г)] Для примера рассмотрим три очереди, график которых описывается табл, 17 1 Таблица 17.1. Трафик трех очередей, обслуживаемый по схеме РВ Значения т; и Р; задаются; значения 5; н Б опрелеляются политикой разделения процессора.
На рис. 17А тонкие черные линии нллюсгрнруап обслуживание трех очередей. Первый прибывший в очередь и пакет получает одну единицу обслуживания в реальном интервале времени [О, 1] с виртуальным временем )7(1) = 1 к концу этого интервала. В реальном интервале времени [1, 3] биты передаются из двух очередей, в результате чего ха!алая очередь получает скорость обслуживания )7'= 1/2 и аккумулирует за этот интервал одну единицу обслуживания, так что )7(З) = )7(1) + 1/2 (3 — 1) = 2.
Аналогично, в течение интервала времени [3, 9] все три очереди сохраняют активность, поэтому каждая получает обслуживание со скоростью л'= 1/3 и аккумулирует две елнницы обслуживания за этот интервал. Этого достаточно, чтобы были целиком переданы два пакета из очереди а и олин пакет из очереди ]); к моменту времени г = 9 дополнительный пакет из очереди В и один пакет из очереди Т находятся в стадии обработки. Следую!нее рекуррентное соотношение показывает, как система разделении процессора развивается в виртуальном времени: Обратите внимание на то, что по этим соотношениям мы можем сосчитать виртуальное время окончания передачи пакета в момент прибытия пакета.
Однако мы не можем вычислить реальное время окончания передачи пакета в момент его прибытия, потому что реальное время окончания передачи пакета зависит от прибытия других пакетов. Справедливая организация очередей с побитовым циклом Упоминавшаяся ранее схема справедливой организации очерелей с побитовым пиклом (Вйщ), эмулирующая побнтоную дисциплину, позволяет передавать не отдельные биты, а пакеты целиком. Эта схема реализуется путем нычисления «на лету» значений ниртуальпого времени начала и окончания передачи пакета, как если бы применялось разделение процессора. Правило очереди ВКЩ формулируется просто: когда завершается передача очередного пакета, для передачи выбирается пакет с наименьшим значением ~;.", Рив.
17.4. Пример рабаты схем РВ и ВНЕО [по [1001) Рисунок 17А позволяет сравнить схемы РЯ и ВКГО. Тонкие черные линии показывают нремя передачи при испо.льзовании схемы разделения процессора, а сеРые линии — при использовании схемы справедливой организации очередей с побитовым циклом. Обратите ннимание на то, что очередность передачи пакетов, основанная либо на реальном времени начала, либо на реальном времени окончания, не совсем совпадает. Тем не менее, схема ВКЩ довольно точно соответствует схеме разделенин процессора по производительности.
В самом деле, в [100] показано, что прп увеличении интервала времени наблюдения значения срелней пропускной способности и средней задержки каждого потока в схеме ВЕРЯ стре мятся к соответствующим значениям схемы РЯ. 17.2. Дисциплина очередей 54Э Поток 1 Поток 2 Поток 3 Е!ЕО Поток 1 Поток 2 ф ф~ Поток 3 Поток 4 ~ь Г," =5'+ 'р« 5," = шах[Г,."и тс(т'.)1 (17.2) 542 Глава 17. Интегрированные и дифференцированные службы Па рис. 17.5, а показаны временные диаграммы трех потоков на ныходном пор ту лсаршрутизатора.
В первых трех рядах вертикальными стрелками обозначесця времена прибытия пакетов, при этом значения длины стрелок пропорционадьны размеру пакетов. Пакеты первого потока в два раза больше пакетов остальных и . ков. В следующих трех строках показаны времена передачи пакетов при испозсьзо ванин различных дисциплин организации очередей'. Затенения позволяют увиде соответствие между временными диаграммами поступления пакетов и временны ми диаграммалси передачи пакетов.
В данном случае использование дисциплин очередей НГО и ГЯ приводит к одинаковому рисунку выходного трафнка. Подоб но другим дисциплинам, схема ВКГ! з предоставляет всем патокам одинаковьсй объем обслуживания, но при одновременном прибытии нескольких пакетов пред почтение отдается более коротким пакетам. Соответственно, в схеме ВКГО потоки 2 и 3 получают меньшие средние задержки, чем в схеме НГО гыш Щ.
1 2 3 2 с'""'"11: Ф: с с 1 2 3 2,'".. !-:.! '2'-3 '2: 1 2 3 2 '.- .з;$ 'ФФ 1 2 3 2 .:з1".:: 2 !3г'2. ВНЕО 2 3 1 2 5! В;::-кФ'-' '! - 2 3 1 2 !2з ' ":Ктсй сй' Е!ЕО 1 2 3 4 2 .ФЖиФ7:3,:4. 1 2 3 4 2 Е'4'-:: ЕО 1 2 3 4 у.;о 2' '. :1 2:3 4 1 зх!3 4 ВНЕО 2 3 4 1 2 - ...!В.лб гГ),'7,2! 2 3 4 1 2 2 3! Рис.
1'7.6. Сравнение схемы ВЕС и двух схем справедливой органиэации очередей ' Мы будем использовать соглашение, иа которому сиориыс случаи разрешаются в ислюу потока тока с мииилсалысылс номером вотока. При добавлении дополнительного потока (рис. 17.5, б) маршрутизатор уже не успевает обрабатывать запросы. 11о мере роста очередей задержки увеличиваются, Если все источники представляют собой «правильные» ТСР-сущности, тогда скорость передачи данных в потоках будет снижена, и перегрузка <сойдет на неть.
В то же время, очевидны различия политик. В схеме НГО задержки всех потоков равномерно растут со скоростью, равной одной временной единице за каждые пять единиц времени. В схеме ГЯ страдает только поток 2, для остальных поток х потоков задержки не увеличиваются.
Соответственно, растет только очередь потока 2, пока наконец поток 2 не обнаружит увеличение задержки и не снизит скорость передачи данных. В определенном смысле это справедливо, так как каждому потоку р ° отоку разрешается посылать только один пакет за цикл. Однако потоки 1 и 2 хотят перед а т передавать данные с одинаковой скоростью передачи данных, и поток 1 получает преимушество, поскольку использует пакеты больших размеров. Схема ВКГО также справедлива, но в плане объема переданных данных, а не количества переданных пакетов. Подобно НГО, схема ВКГО вызывает увеличение всех задержек, но в случае ВКГО преимутцество получают небольшие пакеты, Обобщенная схема разделения процессора Схема ВКГО является более совершенной по сравнению со схемами Г? ГО и ГО в том смысле, что она справедливо распределяет доступные ресурсы среди всех активных потоков, протекающих через узел. Однако схема ВКГО не способна предоставлять различным потокам разный объем ресурсов.
Для передачи графика с различными уровнями качества обслуживания необходима способность дифференцированного выделения ресурсов. Метод, получивший самое широкое применение, представляет собой усовершенствованную схему ВКГО и называется навешенной справедливой организацией очередей (Чге!КЬГес1 Гшг Яцецслй, 'сага)'. Опять же, описание метода будет понятнее, если мы сначала рассмотрим побитовую версию. Для учета различающихся требований разных ресурсов мы можем обобщить дисциплину разделения процессора, наделив ее способностью произвольного предоставления ресурсов. В схеме обобщенного разделения процессора (Геиега!!хег) Ргосеьзог 5Ьагспй, ОР5) каждому потоку а назначается вес ср„, определяющий количество битов, передаваемых из очереди в каждом цикле.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
