Нотация Кендалла

Нотация Кендалла — это система обозначений для описания систем массового обслуживания (СМО), предложенная британским статистиком Дэвидом Джорджем Кендаллом в 1953 году. Она представляет собой компактную запись, позволяющую охарактеризовать основные параметры очереди: входящий поток заявок, процесс обслуживания, количество каналов и дисциплину очереди. Нотация получила широкое распространение в теории массового обслуживания, исследовании операций и моделировании вычислительных систем.

История

Дэвид Кендалл впервые представил свою нотацию в статье «Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain», опубликованной в журнале Annals of Mathematical Statistics в 1953 году. Первоначальная форма записи включала три символа: A/B/c, где A обозначал распределение интервалов между поступлениями заявок, B — распределение времени обслуживания, а c — количество обслуживающих приборов (каналов). В 1966 году американский математик Леонард Клейнрок расширил нотацию, добавив четвёртый и пятый символы для описания ёмкости очереди и дисциплины обслуживания. Позднее, в 1970-х годах, к нотации был добавлен шестой символ, обозначающий размер источника заявок (популяции). Таким образом, современная каноническая форма нотации Кендалла имеет вид A/B/c/K/N/D.

Структура нотации

Нотация Кендалла состоит из шести полей, разделённых косыми чертами. В некоторых контекстах, особенно в учебной литературе, используются сокращённые варианты (например, A/B/c), подразумевающие значения по умолчанию для опущенных полей.

Поле A: распределение интервалов поступления

Обозначает вероятностное распределение промежутков времени между последовательными поступлениями заявок в систему. Наиболее распространённые обозначения:

• M (Markovian) — экспоненциальное распределение (пуассоновский поток). Процесс поступления является марковским, то есть обладает свойством отсутствия последействия.
• D (Deterministic) — детерминированные (постоянные) интервалы.
• Eₖ (Erlang) — распределение Эрланга k-го порядка.
• G (General) — произвольное (общее) распределение, не обязательно экспоненциальное.
• GI (General Independent) — общее независимое распределение, обычно используется для потоков с независимыми интервалами.
• Hₖ (Hyperexponential) — гиперэкспоненциальное распределение с k фазами.
• PH (Phase-type) — распределение фазового типа.
• P (Poisson) — иногда используется как синоним M, но менее распространён.

Поле B: распределение времени обслуживания

Обозначает распределение длительности обслуживания одной заявки одним каналом. Используются те же символы, что и для поля A, но с возможными уточнениями:

• M — экспоненциальное распределение.
• D — детерминированное время обслуживания.
• Eₖ, G, Hₖ, PH — аналогично полю A.
• G — общее распределение.

Поле c: количество каналов (приборов)

Целое положительное число, обозначающее число параллельно работающих обслуживающих устройств. Если c = 1, система называется одноканальной; если c > 1 — многоканальной. В некоторых обозначениях вместо числа может стоять символ ∞, означающий бесконечное число каналов (идеальная система без очереди).

Поле K: ёмкость очереди (максимальная длина)

Максимальное количество заявок, которое может одновременно находиться в очереди (включая ожидающие и обслуживаемые). Если поле опущено, по умолчанию считается, что ёмкость очереди не ограничена (K = ∞). В случае конечной очереди (K < ∞) заявка, поступившая в момент, когда очередь заполнена, получает отказ.

Поле N: размер источника (популяции)

Общее количество потенциальных заявок, которые могут поступить в систему. Если N = ∞ (или поле опущено), источник считается бесконечным, что означает, что интенсивность поступления не зависит от числа заявок, уже находящихся в системе. При конечном N (например, N = 10) интенсивность поступления уменьшается по мере того, как больше заявок оказывается в системе.

Поле D: дисциплина обслуживания

Правило, по которому заявки выбираются из очереди для обслуживания. Наиболее распространённые дисциплины:

• FIFO (First In, First Out) — первым пришёл, первым обслужен (также обозначается FCFS — First Come, First Served). Это значение по умолчанию.
• LIFO (Last In, First Out) — последним пришёл, первым обслужен (также LCFS).
• SIRO (Service In Random Order) — обслуживание в случайном порядке.
• PS (Processor Sharing) — разделение процессора: все заявки в очереди обслуживаются одновременно с равной долей ресурса.
• GD (General Discipline) — произвольная дисциплина.
• PR (Priority) — приоритетное обслуживание, где заявки с более высоким приоритетом обслуживаются раньше.

Примеры и интерпретация

M/M/1

Одноканальная система с пуассоновским потоком поступлений и экспоненциальным временем обслуживания. Ёмкость очереди и источник не ограничены, дисциплина — FIFO. Это классическая модель, для которой существуют аналитические решения для среднего времени ожидания, длины очереди и вероятности простоя.

M/M/c

Многоканальная система с теми же распределениями, но c параллельными каналами. Используется для моделирования, например, телефонных станций или многоканальных серверов.

M/D/1

Одноканальная система с пуассоновским потоком и детерминированным временем обслуживания. Применяется для анализа систем с фиксированным временем обработки, например, в конвейерных линиях.

G/G/1

Общая одноканальная система с произвольными распределениями. Для таких систем редко существуют точные аналитические решения, но разработаны приближённые методы (например, аппроксимация по формуле Кингмана).

M/M/1/K

Одноканальная система с конечной ёмкостью очереди K. Если K = 1, система фактически работает как «отказовая» — заявка либо обслуживается, либо получает отказ. Такие модели используются для анализа буферов ограниченного размера в сетях передачи данных.

M/M/1/∞/N

Система с конечным источником заявок (например, N станков, которые могут выходить из строя). Интенсивность поступления заявок зависит от числа исправных станков.

Расширения и модификации

Двухбуквенные обозначения

В некоторых работах, особенно в области телекоммуникаций, для полей A и B используются двухбуквенные обозначения, например:

• MM — экспоненциальное распределение (синоним M).
• DD — детерминированное.
• GG — общее.

Нотация с индексами

Для уточнения параметров распределений (например, среднего значения или дисперсии) допускается использование индексов, например M₁/M₂/1, где M₁ и M₂ могут обозначать разные средние значения.

Нотация для систем с приоритетами

Для систем с приоритетами иногда добавляют дополнительное поле, например M/M/1/PR, где PR указывает на приоритетную дисциплину, а также может указываться число приоритетных классов.

Применение

Нотация Кендалла используется в следующих областях:

• Теория массового обслуживания — для классификации и анализа моделей очередей.
• Исследование операций — при оптимизации производственных процессов, логистики и транспортных систем.
• Компьютерные сети — для моделирования трафика, буферизации и задержек в маршрутизаторах и коммутаторах.
• Проектирование центров обработки данных — оценка производительности серверов и систем хранения.
• Телефония и связь — анализ нагрузки на коммутаторы и каналы связи.
• Медицина — моделирование потоков пациентов в больницах и поликлиниках.
• Банковское дело — расчёт числа операционистов и времени ожидания в очереди.

Критика и ограничения

Нотация Кендалла, несмотря на свою широкую распространённость, имеет ряд ограничений:

• Не описывает все аспекты системы. Например, не учитывает возможность переключения каналов, блокировку, многофазное обслуживание или сетевые структуры (сети очередей).
• Предполагает стационарность. Большинство аналитических результатов, полученных для моделей Кендалла, справедливы только для установившегося режима работы.
• Сложность при неэкспоненциальных распределениях. Для систем с общими распределениями (G/G/c) точные аналитические решения, как правило, отсутствуют, и приходится прибегать к численным методам или имитационному моделированию.
• Неоднозначность в обозначениях. В литературе встречаются различные варианты нотации, особенно в отношении дисциплины обслуживания и ёмкости очереди, что может приводить к путанице.

Альтернативные нотации

Помимо нотации Кендалла, существуют другие системы обозначений, например:

• Нотация Басмана (Bassmann) — использует символы для описания структуры сети очередей.
• Нотация Джексона (Jackson) — применяется для открытых сетей очередей с экспоненциальными распределениями.
• Нотация Гордона — Ньюэлла (Gordon-Newell) — для замкнутых сетей очередей.
• Расширенная нотация Кендалла — иногда включает дополнительные поля для описания фаз обслуживания, времени ожидания в очереди и других характеристик.

Источники

1. Kendall, D. G. (1953). «Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain». Annals of Mathematical Statistics, 24(3), 338–354.
2. Kleinrock, L. (1975). Queueing Systems, Volume 1: Theory. John Wiley & Sons.
3. Gross, D., Harris, C. M. (1998). Fundamentals of Queueing Theory (3rd ed.). John Wiley & Sons.
4. Бочаров, П. П., Печинкин, А. В. (2003). Теория массового обслуживания. Москва: Издательство РУДН.
5. Шварц, М. (1987). Сети связи: протоколы, моделирование и анализ. Москва: Мир.