|
| |
|
Слаботочка Книги Моменты поступления вызовов на пучок первого выбора -Н т Моменты освобождения линий пучка первого выбора Емкость пучка соединительных линий первого выбора  Моменты поступления избыточных вызовов на пучок соединительных линий последнего выборе Рис. 9.14. Характер избыточной нагрузки создается в результате избыточных нагрузок других пучков соединительных линий, то оценки вероятности блокировки получаются чересчур оптимистическими, если предполагают, что все нагрузки являются чисто случайными. Наиболее распространенный метод учета избыточной нагрузки состоит в том, чтобы установить соответствие между избыточной нагрузкой и эквивалентной ей в смысле вероятности блокировки случайной (пуассоновской) нагрузкой. Например, если интенсивность избыточной нагрузки 1,62 Эрл в примере 9.12 приравнивается к интенсивности случайной (пуассоновской) нагрузки 2,04 Эрл для второго пучка соединительных линий, то получаем вероятность блокировки 1,3 . (Это фактическая вероятность блокировки второго пучка, поскольку оба пучка заняты только тогда, когда занят второй пучок.) Этот метод учета избыточной нагрузки называют методом эквивалентных замен [12]. Имеются таблицы пропускной способности [13], которые учитывают влияние избыточной нагрузки непосредственно при определении максимальных значений интенсивности поступающей нагрузки. Таблицы Нила - Вил кинсона, которыми пользуются инженеры, специализирующиеся по анализу трафика фирмы Bell System, включают один из наборов таких таблиц. Однако таблицы Нила - Вилкинсона построены также с учетом суточных колебаний интенсивности нагрузки (40 Эрл в один день и 30 Эрл в другой - это не то же самое, что по 35 Эрл каждый день) Эти таблицы используются также для определения емкости пучков соединительных линии, которые не создают и не обслуживают избыточную нагрузку. То, что потерянная нагрузка не получает обслуживания на обходных направлениях, означает, что по всей вероятности будут повторные вызовы. Однако влияние повторных вызовов эффективно учитывается величиной В путем эквивалентной замены случайным потоком. 478 9.4. СИСТЕМЫ С ОЖИДАНИЕМ Вторая категория методов теории телетрафика относится к системам, которые задерживают не получившие обслуживания вызовы до тех пор, пока не освободятся необходимые устройства. Эти системы называют по-разному, системами с задержками, системами с ожидающими вызовами и системами с очередями. Вызовы, поступающие в систему в тот момент, когда все обслуживающие приборы заняты, помещаются в очередь и сохраняются до начала обслуживания. Очередь может состоять из ЗУ (таких, как блоки памяти на узле коммутации сообщений) или же лишь из списка источников, ожидающих обслуживания. В последнем случае хранение сообщений является обязанностью самих источников. Используя более общее название теории очередей, можно применить излагаемые далее методы к широкому кругу приложений за пределами связи. Некоторыми из наиболее распространенных приложений являются обработка данных, расчеты с покупателями в магазинах самообслуживания, посадка самолетов, управление оборотными фондами, различные формы бюро обслуживания. Эти и многие другие приложения изучаются в сравнительно новой области исследования операций. Однако основы теории очередей базируются на фундаментальных методах, разработанных первоначально исследователями трафика в электросвязи. Действительно, Эрлангу приписывается первое решение проблемы расчета систем с ожиданием наиболее общего типа. Примерами применения методов расчета систем с ожиданием в электросвязи является коммутация сообщений, коммутация пакетов, статистическое уплотнение с временным разделением, многопунктовая передача данных, автоматическое распределение вызовов, доступ к приемникам набора номера, использование оборудования сигнализации и обработка требований на установление соединений. Кроме того, некоторые из более новых систем УТС с управлением по записанной программе обладают свойствами, которые допускают доступ в порядке очереди к совместно используемым линиям прямой связи между АТС или к линиям междугородной связи WATS. Таким образом, некоторые системы, первоначально работающие как системы с потерями, функционируют теперь как системы с ожиданием. В общем случае работа с ожиданием допускает более высокое использование обслуживающих приборов (устройств передачи), чем система с потерями. В основном повышение использования достигается за счет того, что выбросы в процессе поступления вызовов сглаживаются очередью. Даже хотя характер поступления вызовов в систему случайный, обслуживающие приборы воспринимают в определенной степени его как регулярный. Влияние процесса ожидания в очереди на избыточную нагрузку иллюстрирует рис. 9.15. На этом рисунке изображены те же картины нагрузки, которые были представлены на рис, 9.1, 9.3, 9.9. Однако в данном случае избыточная нагрузка задерживается до тех пор, пока отбои не обеспечат свободных каналов. 20 15 10 5 i 20 eS 10 Характер поступающей нагрузки Характер нагрузки, создаваемой вызовами, ожидающими начала обслуживания Вызовы, ожидающие обслуживания ---1 -Lf-L. 1 2 3 4 5 Время, Мин Рис. 9.15. Временная диаграмма активности абонентов в. системе с ожиданием (13 . обслуживающих приборов) В большей части последующего анализа предполагается, что вся поступающая в систему нагрузка в конце концов обслуживается. Одно предположение, которое подразумевается в этом допущении, состоит в том, что интенсивность поступающей нагрузки А меньше числа обслуживающих приборов N. Даже при условии, что А меньше N, возможны два случая, когда обслуженная нагрузка могла бы быть, меньше поступающей. Первый, когда некоторые источники могли бы устать от ожидания в длинной очереди и снять свое требование; второй, когда объем памяти для хранения требований мог быть конечным. Следовательно, требования могут иногда оказаться не обслуженными системой. Второе предположение, принятое в последующем анализе, состоит .в том, что существует бесконечно большое число источников. В системе с ожиданием число источников в физическом смысле может быть конечным, но в функциональном смысле оно считается бесконечным, поскольку каждый источник может иметь произвольное число необслуженных требований (например, узел коммутации пакетов). Есть примеры, в которых необходим метод расчета для конечного числа источников, однако не в приложениях, рассматриваемых здесь. Обслуживание всей поступающей нагрузки приобретает еще одну особенность, когда существует бесконечно большое число источников,- это потребность в очереди с неограниченным числом мест ожидания. Если даже интенсивность поступающей нагрузки меньше, чем число обслуживающих приборов, то не существует статистического предела числа вызовов, поступающих в систему за короткий интервал времени. Таким образом, в системе, совершен- но не имеющей потерь, очередь должна быть сколь угодно длинной. На практике можно реализовать лишь конечные очереди так, что либо всегда существует статистичесь.ш вероятность блокировки, либо все источники могут быть заняты и не будут создавать дополнительной нагрузки. При анализе систем с ожиданием удобно разделять общее время пребывания требования в системе на время ожидания и длительность занятия. При расчете систем с ожиданием длительность занятия обычно называют длительностью обслуживания. В противовес системам с потерями работа систем с ожиданием зависит от распределения длительности обслуживания, а не от среднего значения < . Здесь рассматриваются два вида распределения длительности обслуживания: постоянная длительность обслуживания и экспоненциальная. Эти распределения представляют собой соответственно в наибольшей степени детерминированные и в наибольшей степени случайные длительности обслуживания. Таким образом, система, которая функционирует в соответствии с каким-либо другим распределением длительностей обслуживания, по показателям работы занимает некоторое промежуточное положение между системами, функционирующими в соответствии с этими двумя распределениями. Основная цель последующего анализа состоит в том, чтобы определить распределение вероятностей времени ожидания. На основе распределения легко можно найти среднее время ожидания. Иногда оно и представляет интерес; однако большей частью интерес представляет вероятность того, что время ожидания превысит некоторое заданное значение. В любом случае время ожидания зависит от следующих факторов: 1) интенсивности и вероятностного характера поступающей нагрузки; 2) распределения длительности обслуживания; 3) числа обслуживающих приборов; 4) числа источников; 5) дисциплины обслуживания очереди. Дисциплина обслуживания очереди может определяться рядом обстоятельств. Первое из них касается способа, каким ожидающие вызовы выбираются из очереди. В общем случае ожидающие вызовы выбираются из очереди по принципу первым пришел, первым обслужен . Однако иногда сама система обслуживания не поддерживает очередь, а лишь циклически опрашивает свои источники с тем, чтобы определить, какой источник ожидает обслуживания. Таким образом, очередь может обслуживаться в порядке последовательности появления ожидающих вызовов. В некоторых приложениях ожидающие требования могут даже выбираться случайно. Кроме того, дополнительные изменения в обслуживании возникают в тех случаях, когда любая из этих схем дополняется дисциплиной приоритетов, которая допускает перестановку некоторых вызовов в очереди размещением их впереди других. 16 .i;.K. I4. Второй аспект, в котором следует рассматривать дисциплину обслуживания - это длина очереди. Если максимальная длина очереди меньше эффективного числа источников, то может возникнуть блокировка (потери вызовов). Поэтому следует рассматривать две характеристики качества обслуживания: вероятность ожидания и вероятность блокировки. Обычным примером системы как с ожиданием, так и с потерями является автоматический распределитель вызовов (АРВ) с большим числом каналов доступа, чем число дежурных (операторов или служащих по приему предварительных заказов). Обычно входящие вызовы ставятся в очередь на обслуживание. Однако при больших нагрузках возникает блокировка даже прежде, чем вызов достигает АРВ. Методы расчета системы с ожиданием, конечными очередями и конечным числом обслуживающих приборов содержатся в [14]. Чтобы упростить описание конкретных систем, специалисты в области теории очередей приняли сокращенные обозначения для классификации систем с ожиданием различных типов. Для обозначений, которые были введены Кендаллом Д. Г., используются буквенные сокращения для идентификации альтернатив в каждой из перечисленных категорий. Несмотря на то, что изложение в данной книге не привязано к этим обозначениям, они вводятся и иногда используются, чтобы читатель мог связать последующие рассмотрения с классическими моделями теории очередей. Объяснение каждой буквы дано на рис. 9Лб. Формат спецификации на рис. 9.16 действительно является расширенным вариантом формата, обьмно используемого большинством специалистов в области теории очередей. Поэтому этот формат иногда сокращают, исключая последние одну или две записи. При исключении этих записей предполагают бесконечный случай . Например, система с одним обслуживающим прибором, случайным Характеристика входящего потока Распределение времени обслуживания G: Распределение общего вида (произвольное, без ограничений) 1 М: Пувссоновское распределение G: Распределение общего вида (произвольное, без ограничений) М: Отрицательное экспоненциальное распределение .D: Постоянное время обслуживания Число обслуживающих приборов N: Ограниченное число ГМ: Ограниченное число Число источников! о : Неограниченное чиспо Ограниченная длина Длина очереди Неограниченная длина ПОТОКОМ И отрицательным экспоненциальным распределением длительности обслуживания обычно определяется так: М/М/1. И число источников, и допустимая длина очереди предполагаются бесконечно большими. 9.4.1. Экспоненциальное распределение длительностей обслуживания Простейшей для анализа системой с ожиданием является система со случайным потоком вызовов и отрицательным экспоненциальным распределением длительностей обслуживания: M/M/N. Вспомним, что случайное распределение вызовов характеризуется отрицательным экспоненциальным распределением промежутков между двумя последовательными вызовами. Таким образом, в сокращенном обозначении специалистов по теории очередей буква М всегда относится к отрицательному экспоненциальному распределению (М используется потому, что чисто случайное распределение является распределением без памяти). Для системы М/М/1 и всех других систем, которые здесь рассматриваются, предполагается, что вызовы обслуживаются в порядке их поступления. В проводимом ниже анализе, кроме того, принимается, что вероятность поступления вызовов не зависит от числа требований, которые уже находятся в очереди (случай бесконечного числа источников). При этих предположениях формула вероятности того, что вызов сталкивается с перегрузкой системы и, следовательно, будет ожидать начала обслуживания, была выведена Эрлангом: Вероятность (ожидания) = р(>0) - NB/IN-A(l-B)], где - число обслуживающих приборов; А - интенсивность поступающей нагрузки, Эрл; В - вероятность блокировки в системе, работающей в режиме с явными потерями (уравнение 9.8). Вероятность ожидания рОО) называют по-разному: либо второй формулой Эрланга, либо EjyC-)-формулой ожидания Эрланга, либо С-формулой Эрланга. Для однолинейных систем, т. е. при N = I, вероятность ожидания уменьшается с уменьшением q, где q - просто использование выхода или нагрузка, обслуженная прибором. Таким образом, вероятность ожидания в однолинейной системе, кроме того, равна поступающей нагрузке Xt (в предположении, что ХС<1). Распределение времени ожидания при случайном потоке вызовов, экспоненциальном распределении длительностей обслуживания , и дисциплине обслуживания в порядке поступления имеет вид РОО =р(>0)е-<-Ч (9.25) где р (>0) - вероятность ожидания, определенная в уравнении ( 9.24); t t - средняя длительность обслуживания при отрицательном экспоненциальном распределении длительностей обслуживания. Уравнение (9.25) определяет вероятность того, что вызов, посту-нощий в случайно выбранный момент времени, ожидает не более 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 [80] 81 82 83 84 85 86 87 88 89 90 91 |