4. Теория очередей и расчет параметров сети
В условиях стремительного роста интенсивности информационного обмена в современных сетях часто возникает необходимость в применении научно обоснованных методов предсказания последствий изменений в сети, смены топологии сети и т. д. Последствия могут оцениваться с точки зрения влияния на производительность, время ответа сети, доступность тех или иных сервисов и пр. Желательно также уметь проводить априорную оценку параметров сети до ее развертывания. Представим себе следующую ситуацию. В организации установлено определенное количество рабочих станций, подключенных к сети Token Ring со скоростью 16 Мбит/с. Руководитель недавно сформированного отделения организации собирается подключить новые рабочие станции своих сотрудников к этой действующей сети. Перед всей организацией сразу встает вопрос — сможет ли существующая локальная сеть справиться с возросшей нагрузкой или для этого отделения необходимо будет создавать вторую локальную сеть и объединять обе сети мостом?
Существуют и другие случаи, в которых достаточно сложно быстро получить ответ на вопрос о том, насколько возрастет нагрузка на сеть при тех или иных изменениях, и справится ли с ней сеть. С точки зрения проектирования сети это означает, что не существует четкого однозначного метода, позволяющего на основе существующих требований к сети вычислить параметры и конфигурацию будущей системы. Рассмотрим другой пример. Одно из отделений организации намеревается оборудовать все свои рабочие места персональными компьютерами и настроить их для работы в локальной сети с сервером. Конечно, можно, основываясь на опыте какой-либо родственной организации, которая уже проделала подобную работу, оценить примерную загрузку, генерируемую каждым персональным компьютером, и на этом основании оценить требуемую производительность всей локальной сети и сервера в частности. Естественно, основным критерием при оценке совокупности параметров сети в данном случае является ее производительность в целом. При использовании интерактивных приложений реального времени в качестве основной оценочной характеристики обычно используется время ответа сети (иногда оно называется временем реакции сети). В других случаях ориентируются на пропускную способность сети.
Очевидно, что в таких случаях при проектировании сети необходимо иметь аналитические инструменты, позволяющие предсказывать производительность по модели сети. Одним из таких инструментов, предназначенных для разработки сетевых и коммуникационных структур, может быть аналитическая модель, основанная на теории очередей. Оказывается, большое количество проблемных вопросов находят свое решение при использовании математического метода анализа очередей.
Хотя теория очередей математически достаточно сложна, применение этой теории для анализа производительности сети во многих случаях дает желаемые результаты. Знание основ статистики и понимание базовых принципов применения теории очередей — это все, что может потребоваться для получения оценки производительности сети с необходимой степенью точности. Аналитик может провести анализ очередей в заданной сетевой структуре, используя уже готовые таблицы очередей или простые компьютерные программы, которые занимают несколько строк кода.
Перед рассмотрением теории очередей, представляемой далее в виде, удобном для практического использования, можно привести пример конкретного использования этой теории. Рассмотрим Web-сервер, который тратит на обработку одного запроса какое-то заранее известное, фиксированное время — допустим одну миллисекунду (очевидно, что это будет также средним временем, затрачиваемым на обработку). Теперь, если средняя скорость поступления запросов равна одному запросу в одну миллисекунду (1000 запросов в секунду), то вполне можно считать, что сервер справится с этой нагрузкой. Действительно, это произойдет в том случае, когда запросы поступают с одинаковой скоростью (равной, очевидно, одному запросу в каждую миллисекунду). После поступления запроса сервер немедленно обрабатывает его. После того как сервер обработал текущий запрос, поступает новый запрос, сервер начинает его обработку и снова укладывается во время.
Рассмотрим более реальную ситуацию и предположим, что средняя скорость поступления запросов по-прежнему равна одному запросу в миллисекунду, но существует некоторая флуктуация поступления запросов. Тогда в течение любого миллисекундного периода времени может не приходить запросов вообще, а может поступить сразу несколько запросов. Но средняя скорость поступления запросов все равно равна одному запросу в миллисекунду и является достаточно четким критерием того, насколько загружен сервер. С флуктуациями, нерегулярностями в поступлении запросов можно справиться, введя буферную память. Действительно, в течение времени занятости, когда необходимо обработать множество запросов, сервер может сохранять невыполненные запросы в своей буферной памяти. Или, иными словами, сервер помещает эти запросы в очередь. Когда сервер завершит обработку текущего запроса, то, если не поступит следующего запроса, он возьмет запрос из очереди и тем самым уменьшит ее. С этой точки зрения, основным вопросом при разработке сетевой структуры является вопрос о том, насколько большим должен быть буфер сервера.
Довольно часто возникает необходимость в проведении оценки производительности на основе имеющихся данных о загрузке действующей сети или по предполагаемой загрузке вновь проектируемой сети. Для проведения таких оценок существуют различные подходы:
Проведение анализа производительности сети после ее внедрения, основываясь на значениях показателей, которые актуальны в данном конкретном случае;
Выполнение простой оценки работоспособности будущей среды, основанной на существующем опыте разработки и построении подобных сетей;
Разработка и применение аналитической модели, основанной на теории очередей;
Разработка и применение простейшей программы, моделирующей поведение сети.
Первый вариант предполагает пассивную позицию разработчика сети. Разработчик просто ожидает результатов своей деятельности. Естественно, такой метод чреват непредсказуемыми последствиями. Полученным результатом, как правило, оказываются недовольны и пользователи, и руководители организации. Их можно понять — они понесли неоправданные затраты, но, в итоге, так и не получили сети с желаемыми параметрами.
Второй вариант может дать, как правило, лучшие результаты. При анализе будущей сети на основании имеющегося опыта можно увидеть, что при наличных возможностях (в том числе, финансовых) и ограничениях бессмысленно ожидать, что сеть будет удовлетворять тем или иным требованиям. То есть, этот метод позволяет достаточно уверенно предсказать, что не сможет делать проектируемая сеть. С точки зрения выполнения предъявляемых требований, метод, основывающийся на опыте, может дать только достаточно расплывчатые предложения, носящие качественный характер. Абсолютно бессмысленно пытаться выполнять на основе этого метода некую более или менее точную количественную оценку необходимых параметров. Другая проблема, связанная с этим подходом, заключается в том, что поведение большинства систем при изменении загрузки будет не таким, как интуитивно ожидалось. Если существует среда, в которой есть разделяемые каналы связи, то производительность такой системы, как правило, экспоненциально уменьшается при увеличении нагрузки. В результате наблюдается расхождение ожидаемых значений и наблюдаемых (рис. П4.1).
Загрузка сети в данном случае определяется долей задействованной пропускной способности. Следовательно, если рассматривать мост, который способен обрабатывать 1000 кадров в секунду, то загрузка 0.5 означает скорость передачи 500 кадров в секунду. Время ответа есть сумма средних времен, затрачиваемых на передачу входящих в сеть кадров.
На рис. П4.1 верхняя кривая показывает изменение реального времени ответа сети на разделяемых каналах связи при увеличении нагрузки. Нижняя кривая описывает ожидаемые разработчиком значения. Две кривые совпадают только в пределах той нагрузки, с которой реально имел дело наш гипотетический разработчик. Как видим, опыт является достаточно надежным проводником только при половинной загрузке сети. При дальнейшем росте нагрузки производительность сети будет резко снижаться.
Для проведения оценки поведения системы практически на всем диапазоне загрузки может быть использован аналитический метод. При его практическом применении приходится решать набор уравнений, после чего удается получить параметры, необходимые для оценки системы (время ответа, пропускную способность и т. д.). Использование теории очередей дает достаточно точную оценку, которая, в большинстве случаев, хорошо соответствует действительности. Недостатком теории очередей является то, что при выводе формул, на которых она основывается и которые используются для расчета интересующих нас параметров, необходимо принять определенные допущения. Тем не менее, оказывается, что эти допущения вполне оправданны, а получающиеся результаты близки к тем, которые получаются при программном моделировании сети с такими же параметрами. Преимуществом теории очередей по сравнению с моделированием является то, что анализ очередей может быть выполнен за сравнительно короткий срок (для большинства реальных ситуаций), в то время как моделирование может занять дни или даже недели — создать программную модель, описывающую требуемую ситуацию, достаточно непросто.
Определение параметров системы с очередями
Для проведения расчета параметров систем с очередями необходимо определить, что, собственно, входит в состав этой системы и то, какие параметры подлежат
оценке. Простейшая система с организацией очередей к серверу показана на рис. П4.2.
Центральным элементом этой системы является сервер, который производит определенные действия с элементами данных (пакетами, кадрами, дейтаграммами и т. п.). Для рассмотрения этой системы примем некоторые допущения. Все элементы данных, поступающие в систему, сохраняются. Если сервер в определенный момент времени простаивает (свободен), элемент данных обрабатывается немедленно. В противном случае поступающие элементы данных сохраняются в очереди. После выполнения сервером обработки определенного элемента данных, он немедленно отправляется по назначению. Если в очереди находятся другие элементы данных, то один из них немедленно поступает на обработку в сервер.
На рис. П4.2 также показаны некоторые важные параметры, которые используются при расчетах. Элементы данных поступают в эту систему с некоторой средней скоростью поступления λ (она измеряется в элементах в секунду). На определенный момент времени некоторое количество элементов данных будет находиться в очереди. Давайте обозначим среднее число элементов данных, находящихся в очереди, буквой ω, а среднее время, которое элементы данных должны ожидать в очереди — символом Тω. Этот параметр определен и имеет смысл для всех входящих элементов данных, включая и те, которые не ожидали вовсе. Сервер обрабатывает входящие элементы данных, затрачивая на это среднее время обработки Тs. Этот временной интервал отсчитывается от момента поступления элемента данных на сервер вплоть до обработки его сервером (то есть отправки). Утилизация (степень загрузки) сервера р — это доля общего времени, в течение которой сервер был занят.
Кроме того, существуют еще два параметра, характеризующие систему в целом. К ним относятся: среднее число элементов данных, находящихся во всей системе, включая элементы данных, которые начали обрабатываться, и элементы, ожидающие обработки, — q и среднее время, которое эти элементы данных находятся в системе, ожидая своей очереди или уже находясь в обработке, — Tq.
Если предположить, что емкость очереди бесконечна, то в такой системе не будет потерянных элементов данных — элементы просто ожидают в очереди до тех пор, пока не будут обработаны. С учетом этого допущения, средняя скорость отправления элементов данных равна средней скорости поступления. Если скорость поступления элементов данных (которая определяется трафиком, входящим в систему) увеличивается, то, естественно, возрастает нагрузка на сервер, а значит, и утилизация сервера. Из таких же естественных соображений мы заключаем, что увеличение размеров очереди повышает (или, по крайней мере, может повысить, но никак не уменьшить) время ожидания элементов данных в ней. При р = 1 сервер загружается до предела, работая 100 % своего времени. Следовательно, теоретическая максимальная скорость поступления элементов данных, при которой они могут быть обработаны сервером, вычисляется по следующей формуле:
Однако размер очереди резко возрастает при вхождении системы в режим насыщения, стремясь к бесконечности при р=1. Поэтому на практике обычно ограничивают скорость поступления данных на сервер до 70-90 % от теоретического максимума.
Можно показать процессы, происходящие в очереди, в их динамике. На рис. П4.3 показан график, иллюстрирующий работу системы с очередью. По оси ординат откладывается общее число элементов данных в системе. Затененные области по оси абсцисс определяют периоды времени, в течение которых сервер занят. Вдоль этой же оси располагаются отрезки, означающие события двух типов: поступление элемента данных; (элемент поступает во время Аj) и завершение обработки этого же элемента; (обработка завершается в момент времени Di), когда элемент покидает систему. Очевидно, время, которое элемент данных j находился в системе, определяется по следующей формуле: Т. - D.-Aj. Минимальное время обслуживания для элемента; обозначается символом Sy
В нашем примере время обработки первого элемента данных Т1 равно минимальному времени обслуживания для этого элемента S1, так как когда элемент 1 поступает в систему, она находится в режиме простоя, и элемент сразу же поступает на обслуживание. Время обслуживания второго элемента данных Т2 определяется суммированием двух времен: времени, которое элемент 2 ожидает обслуживания в очереди и которое определяется выражением (D1-A2), и времени, затраченного на его обслуживание S2. Аналогично, T3 = (D3-A3) = (d3-d2) + (D2-А3) - S 3 + (D2-A3).
Перед тем как производить любые вычисления параметров для системы с очередью, необходимо определить условия работы этой системы и выявить диапазон изменений параметров. Ниже приведены условия, при которых нами будет рассматриваться система с очередями:
Определение количества элементов данных. Предполагается, что в систему может поступать бесконечное количество элементов данных. Это можно интерпретировать как требование о том, что скорость поступления элементов данных в систему никак не зависит от числа элементов, находящихся в системе. Если бы количество элементов данных было ограничено, это означало бы, что скорость поступления элементов в систему должна была бы быть снижена, чтобы система не переполнилась.
Очередь может неограниченно расти. При рассмотрении системы нами будет предполагаться бесконечный размер очереди. Следовательно, очередь может расти безгранично. Если ввести ограничения для размера очереди, то элементы данных в системе стали бы отбрасываться при заполнении очереди. Если очередь заполнена, а дополнительные элементы данных продолжают поступать в систему, то сервер ничего не сможет сделать с ними, кроме того как отбрасывать. На практике любая очередь имеет конечный размер, но в большинстве случаев теоретическое допущение о ее безграничной вместительности не приводит к существенным ошибкам, так как реальные устройства используют различные механизмы предотвращения ситуаций, при которых будет производиться отбрасывание данных.
Определенный порядок обслуживания элементов данных. Когда сервер становится свободным, и в очереди находится несколько элементов данных, необходимо определить правила, в соответствии с которыми определяется элемент данных, выбираемый сервером для обработки. Простейшим правилом является обслуживание очереди по принципу FIFO (First In, First Out — первым пришел, первым и ушел), также известного под названием FCFS (First Come, First Served — первым поступил, первым и обслужен). Другим возможным правилом обслуживания очереди может быть LIFO (Last In, First Out — первым пришел, последним ушел). Кроме того, на практике приходится иметь дело с порядком обслуживания, базирующимся на времени обслуживания. К сожалению, обслуживание очереди, основанное на временных параметрах, достаточно сложно для моделирования. Более общим случаем является обслуживание очереди на основе приоритетов, которое и будет рассматриваться дальше. При этом рассматривается поступление пакетов с одинаковым приоритетом.
В табл. П4.1 перечислены все параметры, определенные на рис. П4.2, а также добавлены новые параметры, которые будут использованы далее при проведении расчетов, в том числе и для систем со множеством серверов.
Таблица П4.1. Используемые параметры
Символ
| Описание
|
λ
| Средняя скорость поступления элементов данных в систему (число элементов в секунду)
|
Ts
| Среднее время обслуживания поступивших элементов (в секундах)
|
σTs
| Стандартное отклонение во времени обслуживания элемента (в секундах)
|
p
| Утилизация сервера при обслуживании (доля времени, когда сервер занят)
|
u
| Интенсивность трафика
|
Q
| Общее количество элементов данных в системе
|
q
| Среднее количество элементов данных в системе
|
ТQ
| Время, которое элементы данных проводят в системе (в секундах)
|
Tq
| Среднее время, которое элементы данных проводят в системе (в секундах)
|
σq
| Стандартное отклонение q
|
σTq
| Стандартное отклонение Tq (в секундах)
|
ω | Среднее количество элементов данных, ожидающих обслуживания в очереди (размер очереди)
|
Tω
| Среднее время, которое элементы данных ожидают обслуживания (в секундах)
|
Td
| Среднее время ожидания обслуживания для элементов данных, находившихся в очереди (то есть, не включая элементы, для которых время ожидания равно 0)
|
σω
| Стандартное отклонение ω
|
N
| Число серверов
|
mx(r)
| х меньше или равно mx(r) в г процентах случаев (примеры см. ниже)
|
На рис. П4.4, а показана простая модель, которая будет использована нами в случае наличия в системе множества серверов, разделяющих одну общую очередь. При поступлении элементов данных в такую систему, если на данный момент времени хотя бы один сервер свободен, элементы данных немедленно направляются на этот сервер. Предполагается, что в системе все сервера идентичны. Это значит, что если доступны несколько серверов, то не делается никаких различий между серверами для выбора того, который будет обрабатывать очередной элемент данных. Можно сказать, что вероятность поступления элементов данных для обслуживания на разные сервера одинакова. Если все сервера заняты, то начинает формироваться очередь. Очередь одна для всех серверов. При освобождении одного из серверов очередь покидает элемент данных, выбранный в соответствии с установленным порядком.
За исключением параметра утилизации серверов, все остальные параметры, приведенные в табл. П4.1, соответствуют ситуации, показанной на рис. П4.2. Если в системе N идентичных серверов, а р обозначает утилизацию каждого сервера, то можно рассматривать Np как утилизацию всей системы. Этот показатель часто рассматривают как интенсивность трафика (в табл. П4.1 обозначена символом и) или интенсивность работы системы. Следовательно, теоретическая максимальная утилизация такой системы будет равна Nx100%. Максимальная скорость поступления элементов данных в такую систему будет определяться по формуле:
В случае множества идентичных серверов выбор определенного сервера для обслуживания определенного элемента данных не влияет на время обслуживания. На рис. П4.4, б показана структура с организацией нескольких очередей для множества серверов. Такое изменение структурной схемы в значительной степени влияет на производительность всей системы в целом.
Искомые параметры можно вычислить с помощью нескольких несложных формул, перечисленных в табл. П4.2. Такие формулы могут быть использованы для вычисления качественных и количественных характеристик систем с очередями, представленных на рис. П4.2 и П4.4. Следует подчеркнуть, что вычисления с применением этих формул носят приближенный характер.
Таблица П4.2. Формулы для расчета параметров систем с очередями
Эти формулы могут быть полезны для вычисления некоторых параметров при «интуитивном» выборе структуры системы. Для получения формулы р = λTs достаточно заметить, что для скорости поступления элементов данных λ, среднее время между поступлениями элементов будет определяться выражением Т = 1/λ. Если интервал времени T меньше интервала времени Тs, то можно будет записать Тs/Т = λТS Аналогичные рассуждения подходят и в случае со множеством серверов: р = (λTs)/N.
Рассмотрим момент времени прихода очередного элемента данных. При поступлении этого элемента в систему в очереди находится в среднем со элементов данных, которые ожидают обслуживания. В момент, когда этот элемент покидает очередь для обслуживания, он оставляет после себя такое же среднее количество элементов в очереди (на то оно и среднее количество, что не меняется). Среднее время, которое элемент ждет своей очереди до обслуживания, равно Тs. А так как элементы поступают в очередь со скоростью λ, то можно утверждать, что за промежуток времени Tω должно поступить λTω элементов данных. Следовательно, ω = λTω. Рассуждая аналогично, можно заключить, что q =λТq.
Из табл. П4.2 видно, что время, которое элемент данных находится в системе, равно сумме времени ожидания обслуживания и времени самого обслуживания. На любой момент времени количество элементов во всей системе равно сумме количества элементов, ожидающих обслуживания, и количества элементов, которые уже обслуживаются. Для одного сервера среднее число элементов, которые обслуживаются в данный момент времени, равно ρр. Следовательно, q = ω + ρ для одного сервера. Аналогично, q =ω+Nρ, если рассматривать случай с N серверами.
Основная задача при проведении анализа очередей заключается в получении информации о:
скорости поступления элементов данных в очередь;
времени обслуживания этих элементов на сервере на входе в систему;
общем количестве ожидающих элементов;
времени ожидания элементов в системе.
При этом важно знать средние значения этих параметров и диапазон их изменений. Следовательно, большое значение при анализе очередей имеет знание стандартных (среднеквадратичных) отклонений каждого из перечисленных параметров; эти отклонения обозначаются σq, σTq, σω и σTω.
Для анализа систем или отдельных модулей сетевых устройств могут быть полезны и другие показатели. Например, при вычислении размеров буферной памяти для моста или мультиплексора, предназначенного для того или иного сегмента рынка, его производителям могут потребоваться данные о размере буфера, при котором вероятность его переполнения будет меньше, допустим, 0.001.
Для ответа на эти вопросы, в основном, необходимо знать закон изменения Скорости поступления элементов данных в систему и закон распределения времени обслуживания элементов данных сервером. Следует отметить, что, даже имея эти данные, очень непросто получить результат элементарными методами, так как исходные формулы для вычислений достаточно сложны. Для того чтобы упростить процесс вычислений, необходимо сделать некоторые естественные допущения. Наиболее важное из этих допущений заключается в том, что изменение скорости поступления элементов данных подчиняется закону Пуассона. Для применимости закона Пуассона необходимо выполнение следующих гипотез:
Поступление одного элемента данных не зависит от поступления другого элемента, то есть события происходят независимо;
Никогда не поступают сразу два или более элементов данных;
Среднее количество поступлений не изменяется со временем (то есть распределение статично).
При соблюдении этих условий вероятность поступления элемента данных подчиняется закону Пуассона, который описывается следующей формулой:
где е — основание натуральных логарифмов; λ — скорость поступления элементов данных; п — количество элементов, поступивших за время t.
Закон Пуассона часто используется в различных приложениях теории вероятности и статистики. Его преимуществом является простота получаемых формул. Практически всегда, когда последовательность каких-либо событий разделена случайными интервалами времени и справедливы три перечисленные выше гипотезы, то, с некоторым приближением, можно использовать пуассоновский закон.
Продолжительность обслуживания элементов на сервере обычно описывается несколько другими законами. Чаще всего в этом случае используется закон интервалов или экспоненциальный закон. Для этого закона используются большое количество продолжительностей времен обслуживания. Рассмотрим пример с использованием 1000 продолжительностей времен обслуживания (каждый промежуток из этой 1000 отличается по времени). Такое количество продолжительностей позволяет повысить точность вычислений. Для упрощения расчетов интервалы времени обслуживания группируются. Например: первая группа с временами обслуживания, лежащими в промежутке времени от 0 до 15 с, следующая группа с временами обслуживания, лежащими в промежутке времени от 15 до 30 с, следующая — от 30 до 45 с и т. д. Приведем таблицу, поясняющую смысл сказанного (табл. П4.3).
Таблица П4.3. Пример распределения интервалов обслуживания
-
Сгруппированные интервалы времени, с
Экспоненциальный закон
0
1000
15
798
30
635
45
508
60
406
75
324
90
259
105
207
120
165
135
131
150
105
165
84
180
67
195
53
210
42
225
34
240
27
255
21
270
17
285
14
300
11
В промежутке времени 0-15 с (второй столбец) имеет место 1000 вариантов продолжительностей обслуживания. В промежутке 15-30 с (третий столбец) имеет место 798 вариантов продолжительностей обслуживания. А в промежутке времени 300-315 секунд (последний столбец) имеет место всего 11 вариантов продолжительностей обслуживания.
Если интервалы времени, разделяющие события, поместить на одной прямой вплотную, то получится ряд событий, удовлетворяющих закону Пуассона. При этом три перечисленные, гипотезы остаются верными и для времени обслуживания. Однако интервалы времени наступления событий могут располагаться не вплотную, так как возможны случаи простоя сервера. В этом случае применяется экспоненциальный закон распределения времени обслуживания. Кроме того, для описания закона распределения времен поступления элементов и их обслуживания может быть использован нормальный закон распределения.
Для проведения оценки системы можно определить параметр, характеризующий интенсивность работы системы. Так как рассматриваются средние величины, важно, чтобы норма поступления элементов данных не превосходила общего уровня обслуживания, то есть λ < pN, или >λ/pN< 1. Эта величина и определяет интенсивность работы системы.
Существуют классические формулы, которые были выведены датским инженером Эрлангом при проведении им аналитического изучения очередей. Эрланг изучал очереди применительно к работе телефонной сети. Составлены специальные таблицы, с помощью которых можно определить ряд параметров для системы с очередями. Например, можно определить среднее время ожидания элементов в очереди как функцию интенсивности обслуживания, уровня утилизации и количества серверов.
Для обобщения всех возможных (или точнее, всех вероятных) случаев организации системы с очередями, к которым применимы рассмотренные выше допущения, был разработан удобный подход. Все такие системы можно разделить, исходя из применяемых законов распределения времен обслуживания и поступления в систему. Система (в том аспекте, который мы рассматриваем) может быть определена тройкой X/Y/N, где Х — это закон распределения времени поступления элементов данных в систему; Y — закон распределения времени обслуживания элементов данных сервером и N — число серверов. Для рассматриваемых здесь систем характерны следующие возможные законы распределения (ниже также указаны буквы, которыми обозначаются эти законы):
G — нормальное распределение времени поступления или времени обслуживания элементов данных;
М — пуассоновское распределение времени поступления; пуассоновское или экспоненциальное распределение времени обслуживания элементов данных;
D — детерминированное время поступления или время обслуживания элементов данных.
Следовательно, модель М/М/1 определяет систему с одним сервером, пуассоновским распределением времени поступления элементов данных в систему и экспоненциальным временем обслуживания элементов на сервере.
Система с одним сервером
В первом столбце табл. П4.4 показаны формулы для определения некоторых параметров системы с одним сервером, которая подчиняется модели M/G/1. В соответствии с этой моделью скорость поступления элементов данных подчиняется пуассоновскому закону, а время обслуживания — нормальному распределению. Использование масштабирующего коэффициента А в значительной мере упрощает формулы для вычисления основных выходных параметров. Следует учесть, что коэффициент масштабирования зависит только от отношения стандартного (среднеквадратичного) отклонения времени обслуживания к среднему времени обслуживания (см. формулу). При этом не требуется никакой другой информации о времени обслуживания.
Другие два случая, разобранные в табл. П4.4, это — модель с распределением времени ожидания по пуассоновскому закону, а времени обслуживания по экспоненциальному закону (М/М/1, второй столбец) и модель, в которой время обслуживания всех элементов одинаково (а значит, отклонение времени обслуживания равно нулю), а время поступления элементов подчиняется пуассоновскому закону (M/D/1, третий столбец в табл. П4.4). Как мы уже отмечали, вычисления при помощи этих формул носят приближенный характер, но для практического применения их точности вполне достаточно.
Таблица П4.4. Формулы для определения параметров системы с одним сервером
Практика показывает, что наихудшую производительность демонстрирует система с экспоненциальным распределением времени обслуживания, а наилучшую производительность — система с постоянным временем обслуживания (что, впрочем, неудивительно). Поэтому обычно можно рассматривать систему с экспоненциальным распределением времени обслуживания, как систему с худшими параметрами.
Эти же рассуждения применимы при рассмотрении различных распределений времен поступления элементов данных (то есть различного характера варьирования скорости прихода данных в систему). Для скорости поступления элементов, подчиняющейся пуассоновскому распределению, время между поступлениями элементов изменяется по формуле Пуассона (см. выше), и коэффициент стандартного отклонения от среднего равен единице. Если наблюдаемый коэффициент меньше единицы, то скорость поступления элементов постоянна. В этом случае применение предположения о пуассоновском распределении скорости поступления даст завышенную оценку размера очереди и задержек в ней. С другой стороны, если коэффициент больше единицы, то перегрузка системы в этом случае становится более вероятной.
Система с несколькими серверами
В табл. П4.5 приведены формулы для определения основных параметров в случае работы с системой со множеством серверов. Эти формулы применимы только для случая использования модели M/M/N. То есть предполагается пуассоновский характер распределения времен поступления элементов данных и экспоненциальный характер времени обслуживания этих элементов. При этом формула Пуассона для распределения времени обслуживания применима для всех N серверов. Во всех выражениях используется функция Эрланга С, которая, в одних случаях, определяет вероятность того, что все сервера заняты в определенный момент времени, а в других случаях — вероятность того, что количество элементов данных, находящихся в данный момент времени в системе (ожидающих в очереди или обслуживающихся), будет больше или равно количеству серверов. Для вычисления функции С применима следующая формула:
где К — коэффициент пуассоновского распределения.
Значение этой функции зависит от количества серверов (N) и их утилизации (р). Функцию Эрланга приходится часто применять при расчете очередей, что значительно усложняет вычисления. Следует отметить, что для системы с одним сервером эта функция значительно упрощается. А именно: С = (1, и) = р. Такое упрощение как раз и позволяет для системы с одним сервером получить красивые законченные формулы (табл. П4.5).
Таблица П4.5. Формулы для определения параметров системы со множеством серверов
Рассмотренная теория очередей достаточно эффективно может быть использована на практике в различных ситуациях. Приведем пример практического применения теории очередей. Рассмотрим локальную сеть, имеющую в своем составе 100 рабочих станций и один сервер (N = 1), который обслуживает общую базу данных. Среднее время ответа сервера на запрос — 0.6 с. Стандартное отклонение этого времени также равно 0.6 с. В пиковые периоды работы локальной сети скорость поступления запросов к серверу достигает значения 20 запросов в минуту.
Ответим на следующие вопросы:
Чему равно среднее время ответа сервера?
Если время ответа, равное 1.5 с, рассматривается как максимально приемлемое, то насколько может вырасти процент загрузки до достижения насыщения сервера?
Если ожидается, скажем, 20-процентное увеличение утилизации сервера, то насколько увеличится время ответа (на 20 %, больше чем 20 %, меньше чем 20 %)?
Предположим, что в рассматриваемой ситуации применима модель М/М/1. Будем игнорировать задержки, вносимые сетью, полагая, что распределение задержки в ней можно не принимать в расчет.
Вычислим некоторые параметры сети. Сначала найдем скорость поступления λ:
λ = 20 поступлений в минуту = 20/60 поступлений в секунду = 1/3 поступлений в секунду.
Утилизация сервера вычисляется по формуле:
р = λTs = (1/3 поступлений в секунду) (0.6 секунд на передачу) = 0.2. Вычислим среднее время ответа:
Tq = Ts/(1 -р)= 0.6/(1 - 0.2) = 0.75 с.
На второй вопрос однозначно ответить сложно, так как существует ненулевая вероятность того, что в некоторых случаях время ответа сервера будет превышать 1.5 с. Поэтому можно предположить, что в 90 % ответы сервера будут даны менее чем за 1.5 с. Если сделать такое допущение, то мы сможем воспользоваться формулой из второго столбца в табл. П4.4:
mTq (r) = Tq ln(100/(100 - r)).
Получаем:
m-Tq(90) = Tq ln(10) = Ts/(1 - р) 2.3 = 1.5 с.
Учитывая, что Ts = 0.6 с, получаем утилизацию сервера р = 0.008, то есть 8 %. Итак, можно сказать, что при изменении загруженности сервера в диапазоне от 8 % до 20 % (см. выше) время ответа сервера будет менее 1.5 с в 90 % случаев.
В заключение определим зависимость между возрастанием нагрузки и увеличением времени ответа. Время ответа будет увеличиваться несколько медленнее, чем утилизация. Действительно, в нашем случае, если утилизация сервера возросла с 20 % до 40 %, то значение Tq изменится от 0.75 с до 1.0 с (как нетрудно подсчитать), что означает увеличение на 33.3 %.
- Максим Кульгин Технологии корпоративных сетей. Энциклопедия
- Часть I основы корпоративных сетей.
- 1. Базовые сетевые технологии
- Соединения и каналы
- Технологии b-isdn и atm
- Технология Frame Relay
- Технология isdn
- Плезиохронная и синхронная цифровые иерархии
- Технология sonet
- Технология smds
- Технология Ethernet
- Дальнейшее развитие технологии Ethernet
- Технология 100vg-AnyLan
- 2. Методология построения корпоративной сети
- Сравнение современных технологий передачи данных
- Требования к сети
- Архитектура сети
- Магистраль на базе коммутации ячеек
- Маршрутизация
- Коммутация
- Выделение маршрутов
- Сетевые шаблоны
- Сетевой шаблон глобальной сети
- Сетевой шаблон городской сети
- Шаблон городской сети с технологией sonet/sdh
- Шаблон городской сети с передачей atm поверх sonet/sdh
- Шаблон городской сети, как расширенной локальной сети
- Сетевой шаблон центрального офиса
- Реализация доступа и магистрали
- Критерии выбора технологии
- 3. Качество обслуживания в современных сетях
- Характеристики трафика
- Трафик разных приложений
- Качество обслуживания «на самоокупаемости»
- Обзор технологий качества обслуживания
- Обеспечение перекрывающей пропускной способности
- Приоритетные очереди в маршрутизаторах
- Протокол резервирования ресурсов
- Установление приоритетов в виртуальных сетях
- Качество обслуживания в сетях Frame Relay
- Качество обслуживания в сетях atm
- Рекомендации
- 4. Модель и уровни osi
- Эталонная модель osi
- Протоколы и интерфейсы
- Уровни модели osi Физический уровень
- Канальный уровень
- Сетевой уровень
- Транспортный уровень
- Сеансовый уровень
- Уровень представления
- Прикладной уровень
- Назначение уровней модели osi
- 5. Основные типы сетевых устройств
- Витая пара
- Коаксиальный кабель
- Оптоволоконный кабель
- Сетевые адаптеры
- Концентраторы
- Коммутаторы
- Коммутация «на лету»
- Коммутация с буферизацией
- Бесфрагментная коммутация
- Дополнительные функции коммутаторов
- Протокол stp
- Протокол stp и виртуальные сети
- Протокол stp: заключение
- Маршрутизаторы
- Брандмауэры
- Часть II стек протоколов тср/ip
- 6. Ip и другие протоколы нижнего уровня
- Протокол ip
- Протокол arp
- Протокол 1смр
- Протокол udp
- Протокол rtp
- Адресная схема протокола ip
- 7. Протокол tcp
- Формат заголовка
- Состояние системы
- Блок управления передачей
- Установление и закрытие соединений
- Плавающее окно
- Пропускная способность
- Контроль за перегрузками
- Управление потоком данных
- Политики отправки и приема сегментов
- Таймер повторной передачи
- Адаптивный таймер повторной передачи
- Узкие места в сети
- Протокол tcp в сетях atm
- 8. Маршрутицазия протокола ip
- Автономные системы
- Подсети
- Маска подсети
- Протокол rip
- Маска подсети переменной длины
- 9. Протоколы маршрутизации Протокол ospf
- Протоколы igrp и eigrp
- Протоколы политики маршрутизации egp и bgp
- Протокол igmp
- Алгоритмы построения дерева доставки
- Магистраль mbone
- Протоколы групповой маршрутизации Протокол dvmrp
- Протокол mospf
- Протокол рiм
- Бесклассовая междоменная маршрутизация
- Часть III Технология atm
- 10. Введение в технологию атм
- Появление atm
- Форум atm
- Основные компоненты atm
- Уровни atm
- Уровень адаптации atm
- Уровень atm
- Физический уровень
- Прямая передача ячеек
- Использование транспортных кадров
- Использование plcp
- Интерфейсы atm
- Мультиплексирование в сетях atm
- Инверсное мультиплексирование
- Безопасность в сетях atm
- Сигнализация atm
- 11. Основы технологии атм Соединения atm
- Сети без установления соединения
- Сети с установлением соединения
- Виртуальные соединения в сетях atm
- Типы виртуальных соединений
- Виртуальные пути и виртуальные каналы
- Установление соединений atm
- Ячейки atm
- Сети с передачей ячеек
- Формат ячеек atm
- Ячейки формата uni
- Ячейки формата nn1
- Подготовка ячеек к передаче
- Уровень адаптации aal1
- Уровень адаптации aal3/4
- Уровень адаптации aal5
- Адресация atm
- Адрес dcc aesa
- Адреса icd и е.164 aesa
- Управление адресами
- 12. Коммутация и маршрутизация в атм Коммутаторы atm
- Архитектура коммутаторов atm
- Интеграционные функции коммутаторов
- Управляемость
- Маршрутизация в atm
- Протокол маршрутизации запросов pnni
- Протокол сигнализации pnni
- Качество обслуживания
- Протокол tcp
- Протокол udp
- Резервирование ресурсов и протоколы управления потоком данных
- Организация очередей в маршрутизаторе
- Метод явного контроля скорости
- 14. Интегрированные и дифференцированные услуги Качество обслуживания
- Интегрированные услуги
- Сервисные уровни обслуживания
- Сервисное управление нагрузкой
- Гарантируемое обслуживание
- Протокол резервирования ресурсов rsvp
- Стили резервирования
- Развитие сетей с is
- Дифференцированные услуги
- Архитектура системы с предоставлением ds
- Граничные устройства домена ds
- Внутренние устройства домена ds
- Выходные домены
- Использование протокола rsvp в сетях с ds
- 15. Управление трафиком в атм
- Трафик-контракт
- Параметры трафика
- Категории сервиса
- Связь механизмов управления трафиком
- Контроль за установлением соединения
- Контроль за использованием полосы пропускания
- Формирование трафика
- Контроль потока abr
- Контроль приоритетов
- Организация очередей в коммутаторах
- Реализация очередей для службы ubr
- Реализация очередей для службы abr
- Методы отбрасывания пакетов
- Адаптивное управление буферами в коммутаторах
- 16. Интеграция с атм
- Протокол ip поверх atm
- Передача ip-Дейтаграмм по сети atm
- Взаимодействие устройств в одной логической подсети
- Групповая доставка информации в сети atm
- Взаимодействие устройств в разных логических подсетях
- Протокол nhrp
- Оценка потерь при работе протокола ip поверх atm
- Передача ip-дейтаграмм в кадрах sonet
- Технология эмуляции локальной сети — lane
- Концепция lane
- Технология мроа
- Клиент мроа
- Сервер мроа
- Взаимодействие технологий мроа и nhrp
- Масштабируемость в глобальных сетях
- Технология Tag Switching фирмы Cisco
- Технология aris фирмы ibm
- Технология mpls комитета ietf
- Перспективные разработки. Рекомендации
- Взаимодействие технологий atm и Frame Relay
- 17. Интеграция маршрутизации и коммуникации
- Общие вопросы выбора технологий
- Коммутирующие маршрутизаторы
- Коммутация третьего уровня в atm
- Технологии фирм Ipsilon и Toshiba
- Технология FastIp фирмы 3Com
- Технология NetFlow фирмы Cisco
- Технология SecureFast фирмы Cabletron
- Технология Multiprotocol Switched Services фирмы ibm
- 18. Мультимедиа в сети
- Передача видеоинформации
- Технические требования к передаче видеоинформации в сетях atm
- Некоторые рекомендации по созданию сетей atm с видео
- Передача голоса
- Часть V Приложения
- 1. Стандарты стека протоколов tcp/ip
- 2. Порты протоколов tcp и udp
- 3. Выделение ip - подсетей
- 4. Теория очередей и расчет параметров сети
- 5. Организации по стандартизации
- 6 Список фирм - членов Форума атм
- 7. Спецификации Форума атм
- 8. Список терминов
- 9. Список литературы Основная литература
- Дополнительная литература Технология atm и протокол ip поверх atm
- Технология качества обслуживания
- Система ip-адресаиии
- Некоторые ресурсы Internet
- Алфавитный указатель
- Оглавление
- Часть I 3
- Часть II 109
- Часть III Технология atm 207
- Часть IV 269
- Часть V Приложения 402