В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 54
Текст из файла (страница 54)
8.7. Очереди с приоритетами До сих пор мы рассматривали очереди в которых запросы обслуживаются на основе дисциплины Е(ГО (Е!гзг ш Е1гзг От!1 — первым прибыл, первым обслужен). Однако как в сетях, так н в операционных системах во многих случаях желательно использовать приоритеты. Приоритеты могут назначаться по-разному, например на основе типа трафика. Если оказывается, что среднее время обслуживания для трафиков различного типа идентично, тогда общие формулы для системы не изменяются, хотя производительность системы на разных классах графика будет различаться.
Важным является случай назначения приоритета на основе среднего времени обслуживания, Часто запросам с меньшим ожидаемым временем обслуживания лается более высокий приоритет, чем запросам с большим ожидаемым временем обслуживания. Например„маршрутизатор может назначить гютоку пакетов, содержащих оцифрованную речь, более вьк:окий приоритет по сравнению с потоком данных. Кроме того, как правило, пакеты с данными короче пакетов с оцифрованным телефонным сигналом.
При такой схеме производительность высокопр!!ИР!! тетного графика увеличивается. Ниже перечислены формулы для очередей с одним сервером, применимые при наличии двух классов приоритетов с различным временем обслуживания для кажлого класса. Эти результаты нетрудно обобп!ить для любого числа классов приоритетов Для перечисленных формул имеют место следующие допущения: + частота поступления запросов распределена по Пуассону; + запросы с приоритетом 1 обслуживаются прежде запросов с приоритетом 2; 244 Глава 8. Анализ очередей 8.8.
Сети очередей 245 т -01+ ' ' =0,833с; 0,98-0,01 1 — 0,88 8.8. Сети очередей Т, = — 'Т„+ — 'Та; Л Л2 Ла Л"' Т„= — ' Т„+ — Тни Р,(Р,Т„+ РзТ„) Та(1 р,) Л., ' Л,(1-Р) ' Р>Т.> + Р,т„, г1 .>+ 1 — Р, — 2 -..НБП У;., =Т„+ 1 — Р Рис. 8.7. Пример сети очередей 0,08 ° 0,01 + 0,8 . 0,1 Та=0,01+ 1 008 + для запросов с равным приоритетом применяется дисциплина диспетчеризации Г1ЕО (Г>гзг ш Г(гзг Оцг — первым прибыл, первым обслужен); + обслуживание запроса не прерывается; + запросы не выбрасываются из очереди.
Итак, общие формулы: Л=Л +Ля Р, =л,т.;, рз = Лгте,' Р=Р + Рь Теперь формулы для случая, когда время обслуживания распределено экспоненциально: Чтобы оценить эффект от использования приоритетов, рассмотрим простой пример потею> данных, состоящего из смеси длинных и коротких пакетов, передаваемых узлом сети с коммугацней пакетов, причем частоты поступления пакетов двух типов одинаковы.
Предположим, что длины пакетов обоих типов распределены экспоненциально и что средний размер длинных пакетов в десять раз больше среднего размера коротких. Допустим также, что пропускная способность линии составляет 64 Кбит,>с и что средние длины пакетов равны 80 и 800 байт. Затем допустим, что среднее время обслуживания коротких и длинных пакетов равно 0,01 с и 0,1 с соответственно, а частота поступления пакетов каждого типа составляет 8 пакетов в секунду. Чтобы длинные пакеты не задерживали короткие, назначим более коротким пакетам более высокий приоритет.
Тогда р>=8 0001=008р>=8 001=08Р=088; % Т,=05 0,098+ 0,5 0,833=0,4855 с. Ж Таким образом, мы видим, что обслуживание высокоприоритетных пакетов вы- полняется значительно лучше, чем низкоприоритетных. К сожалению. в распределенном окружении аналитик моткет встретиться не только с изолированными очередями. Часто анализируемая система состоит нз нескольких соединенных друг с другом очередей. Эту ситуацию иллюстрирует рис. 8,7, где рядом с узлами пою>заны очереди. а соединяющие их липин представляют потоки данных. По сравнению с уже рассматривавшил>ися случаями подобная сеть оказывается сложнее по двум причинам: + Имеет место разделение и объединение графика, как, например, соответственно, в узлах 1 и 5 нарисунке.
+ Существуют цепочки очередей, например цепочка, образованная узлами 3 и 4 на рисунке. Обшего метода анализа очередей, содержащих вышеупомянутые элементы, нет. Однако если трафик подчиняется распределению Пуассона, а время обозу>кивания распределено экслоненциально, сушествует точное и простое решение. В далном разделе мы сначала изучим два описанных выше элемента, а затем представим метод анализа системы очередей. Разделение и объединение потоков данных Предположим, что график прибывает в очередь со средней скоростью Л и что есть два пути, А н В, по которым пакеты могут отправляться дальше, то есть имеет место разделение потоков (рис. 8.8, е). Когда запрос обслужен и покидает очеРель, он делает это ло пути А с вероятностью Р и по пути В с вероятностью (1 — Р). В обшем случае распределение потоков А и В будет отличаться от распределе-ния входящего потока.
Однако если входяший поток подчиняется распределению 246 Глава В. Анализ очередей В.В. Сети очередей 247 Пуассона, тогда два исходящих пото1са также будут подчиняться распределению Пуассона со средними частотами РЛ и (1 — Р)Л. Рис. 8.8. Элемен1ъ1 сетей очередей Сходная ситуация возникает при объединении потоков (рис. 8.8, б). Если объединяются два потока, подчиняющиеся распределению Пуассона, со среднилги частотами Л1 н Ль получаюшийся в результате поток также подчиняется распределению Пуассона со средней частотой, равной Л1 е )е. Приведенные выше результаты можно обобшнть для любого количества объединяемых или разделяемых потоков. Цепочки очередей На рис.
8.8, в показан пример цепочки очередей к одному серверу каждая. Вход каждой очереди, кроме первой, является выходом предыдущей очереди. Допустим, что на входе первой очереди поток подчиняется распределению Пуассона. В этом случае, если время обслуживания каждой очереди подчиняется экспоненциальному распределению, а длина очередей не ограничена, на выходе каждой очереди также будет поток, подчиняющиеся распределеник1 Пуассона и статистически идентичный входному, Когда этот поток подается на вход следующей очереди, задержки во второй очереди будут такими же, как если бы исходный поток миновал первую очередь и направлялся напрямую во вторую очередь.
Таким образом, очереди являются независимыми, и их можно анализировать по отдельности. Поэтому средняя суммарная задержка для системы цепочек очередей равна сумме средних задержек каждой очереди. Этот результат можно расширить до случая, в котором отдельные или все узлы цепочки представляют собой очереди к нескольким серверам. теорема Джексона Для анализа сети очередей может использоваться теорема Джексона [[ас)гзоп).
Эта теорема основана на трех допущениях: + Сеть очередей состоит из и узлов, каждый из которых предоставляет независимое обслуживание с экспоненциально распределенным временем, + Запросы поступают в систему снаружи на любой из узлов с частотой, распределенной по Пуассону. + После обслуживания на узле запрос немедленно с некоторой фиксированной вероятностью поступает на другой узел или покидает систему.
Теорема Джексона утверждает, что в подобной сети очередей каждый узел представляет собой независимую очередь с распределенным по Пуассону входным потоком, детерминированным в соответствии с принципами разделения, объединения и цепочек очередей. Таким образом, каждый узел может анализироваться отдельно от остальных при помощи схем М/М/1 и М/М/тЧ; а результаты могут комбинироваться с использованием обычных статистических методов. Средние значения времени задержки на узлах можно складывать, но ничего нельзя сказать о моментах более высокого порядка времени задержки (например, о среднеквадратичных отклонениях).
Использование теоремы Джексона оказывается привлекательным для приложений, работающих в сетях с коммутацией пакетов. Подобную сеть можно моделироватыагк сеть очередей, Каждый пакет представляет собой индивидуальный запрос. Предположим, что каждый пакет передается отдельно и что на каждом узле с коммутацией пакетов на пути от отправителя до получателя пакет устанавливается в очередь на передачу по следукяцей линии.
Обслуживание на каждом узле заключается в передаче пакета, а время обслуживания пропорционально длине пакета. Недостагок такого подхода состоит в том, что нарушается условие теоремы, а именно это не тот случай, в котором обслуживание при распределении независимо. Поскольку длина пакета не изменяется при его прохождении по маршруту, процесс поступления в каждую очередь оказывается коррелированным с процессом обслуживания. Однако в [1 371 показано, что благодаря усредняюшему зффек ту объединения и разделения потоков предположение о независимых временах обслуживания вполне приемлемо. Приложение для сетей с коммутацией пакетов Рассмотрим сеть с коммутацией пакетов, состоящую из узлов, соединенных линиями передачи. Каждый узел действует как интерфейс для нескольких присоединенных систем, а также как отправитель и получатель графика.
Внешняя нагрузка на сеть может быть охарактеризована так у=ХХуя, 1=1 еа 8 8. Другие модели очередей 249 248 Глава 8. Анализ очередей М А,. М Т.= — ' 1 МЛ> Л; -МЛ; Л, »= 1 ° МЛ> Х'Т, -МЛ й Т тв Тю 1-р> 1-Л>т. Здесь: + у — суммарная нагрузка в пакетах в секунду; + у>ь — нагрузка между отправителем > и получателем >>; + >ч' — суммарьк>е количество отправителей и получателей. Поскольку пакет может на пути от отправителя к получателю преодолеть не.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
