Теория телетрафика. Модели систем массового обслуживания

Введение Общеизвестен факт, что развитие современных телекоммуникационных систем проходит под действием двух сил, имеющих различные истоки, с одной стороны традиционных телефонных компаний и поставщиков телефонного оборудования, а с другой - производителей средств компьютерной техники и провайдеров услуг Интернет. Каждая из сторон борется за потребителя и основным оружием в этой борьбе является качество предоставляемых услуг. Телетрафик. - это понятие, которое может быть определено как движение сообщений (информационных поток). Теория телетрафика - это научная дисциплина о закономерностях и количественном описании процессов движения этих сообщений в сетях и системах. Начало теории телетрафика восходит к работам датского математика Агнера Крарупа Эрланга, исследовавшего статистические характеристики работы телефонных сетей. С помощью теории телетрафика, возможно рассчитать характеристики качества обслуживания в телекоммуникационных системах, управлять основными параметрами качества обслуживания реальных сетей и систем и измерять их, а также предложить оптимальные с точки зрения качества обслуживания технические решения при проектировании новых сетей и систем. Вопросы построения сетей с гарантированным качеством услуг являются предметом внимания ITU-International Telecommunication Union (Международного Союза Электросвязи) особенно в связи с развертывание работ по созданию глобальных сетей третьего и четвертого поколений. В курсе «Теория телетрафика» рассматриваются процессы обработки информации в телекоммуникационных сетях с точки зрения теории систем массового обслуживания. Основными понятиями системы массового обслуживания (СМО) являются заявки (требования) и серверы, называемые также обслуживающими приборами. Заявки образуют входной поток на входе СМО и работа системы состоит в обслуживании этих заявок, затрачивая на каждую некоторое время. Если число серверов недостаточно для обслуживания всех поступивших заявок, то возникает конфликт, разрешение которого состоит в том, что часть заявок отбрасывается или помещается в очередь. Поэтому в зарубежной литературе, обычно используется термин Queuing Theory (теория очередей). В телекоммуникационных системах заявка ассоциируется, прежде всего, с попыткой абонента получить доступ к ресурсам системы для передачи или приема сообщений. Например, снимая трубку телефонного аппарата, абонент телефонной сети порождает сигнал, который является заявкой на обслуживание его этой сетью. Если аппарат включен через блокиратор, и снявший трубку не услышит ничего - то сеть отказывает ему в обслуживании, заявка отбрасывается. Наличие гудка означает, что заявка принята и абонент получает обслуживание. Абонент телефонной сети порождает заявки и другого типа: набор номера вызываемого абонента. Эта заявка также может быть удовлетворена, если ресурсы сети позволят установить соединение между всеми телефонными станциями, которые обеспечивают передачу речевого сигнала от телефона вызывающего до телефона вызываемого абонента. Однако, это произойдет не всегда. Заявка на установление соединения может быть не удовлетворена. Вероятность такого события для абонентов телефонной сети рассматривается как характеристика качества обслуживания этой сети и расчет вероятности отказа в обслуживании является одной из важнейших задач теории телетрафика. Рассмотрим теперь пользователей другой, компьютерной сети, например Internet. Здесь качество сети ассоциируется с другой характеристикой: временем доступа к тому или иному ресурсу. Причиной замедления работы являются образующиеся в маршрутизаторах очереди, состоящие из пакетов, в которые упакована вся передающаяся по сети информация. В компьютерных сетях заявка на передачу информации от одного узла к другому даже в случае нехватки ресурса, как правило, не отбрасывается, а помещается в очередь на ожидание освобождения необходимого ресурса. Поэтому характеристикой качества обслуживания в этом случае считают время нахождения заявки в очереди на обслуживание. Задача расчета времени ожидания также решается в теории телетрафика. Таким образом, изучив основные методы теории телетрафика, вы сможете рассчитать характеристики качества обслуживания в телекоммуникационных системах, управлять основными параметрами качества обслуживания реальных сетей и систем и измерять их, а также предложить оптимальные с точки зрения качества обслуживания технические решения при проектировании новых сетей и систем. Вопросы построения сетей с гарантированным качеством услуг являются предметом внимания ITU-International Telecommunication Union (Международного Союза Электросвязи) особенно в связи с развертывание работ по созданию глобальных сетей третьего и четвертого поколений в третьем тысячелетии. 1 МОДЕЛИ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ 1.1 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ТЕЛЕТРАФИКА Объем оборудования рассчитывается по максимальной нагрузке в ЧНН, при каком-то качестве обслуживания, которое определяется величиной потерь. График концентрации нагрузки. Р – потери, рассчитываются в промилле (‰). Если потеря 1‰, то из 1000 вызовов один будет потерян. Если расчет оборудования считать с потерей в 1‰, то стоимость оборудования падает на 5%. Математическая модель включает в себя три основные элемента: - входной поток вызовов; - схему системы распределения информации; - дисциплину обслуживания. Поток вызовов – последовательности вызовов, поступающие через какие-либо интервалы или в какие-либо моменты времени. Схемы системы распределения информации можно разделить на: 1) однозвенную, полнодоступную коммутационную систему с потерями; 2) однозвенную, не полнодоступную коммутационную систему с потерями; 3) однозвенную, полнодоступную коммутационную систему с ожиданиями; 4) однозвенную, полнодоступную коммутационную систему с повторениями вызовов; 5) двухзвенную, полнодоступную коммутационную систему с потерями; 6) многозвенные коммутационные системы. Если рассматривать многозвенную КС., то ее можно разделить на несколько ступеней коммутации. Рассматривается как одно звено в общей структуре, а сама структура многозвенная. Для цифровых систем В-П-В либо В-П-П-В. Временная коммутация обеспечивает коммутацию временных интервалов. Пространственная соединяет вход с выходом. Дисциплина обслуживания – характеризует взаимодействие потока вызовов в системе взаимодействия информации. Дисциплина обслуживания описывается следующими характеристиками: 1) способом обслуживания вызовов – потери, ожидания, повторения, комбинированный; 2) порядком обслуживания – очередный, случайный, пакетами; 3) законами распределения длительности обслуживания вызовов - показательный, постоянный или произвольная длительность обслуживания; 4) наличием преимуществ и приоритетов; 5) наличием ограничений (длительность обслуживания, число ожидаемых вызовов); 6) законами распределения вероятности выхода из строя элементов системы. При анализе работы схемы необходимо учитывать условия, при которых работают те или иные устройства. Для компактной записи математической модели часто используют следующие сокращения: М – показательное распределения длительности; D – регулярное (равномерное) распределение длительности; Е – эрланговское распределение; Еn – эрланговское n-го порядка; НМ – гиперэкспоненциальное; НМn – гиперэкспоненциальное n-го порядка; НЕ – гиперэрланговское; НЕn - гиперэрланговское n-го порядка; СМ – комбинированное; СМn – комбинированное n-го порядка; G(GL) – произвольное распределение независимых промежутков; Mt – пуассоновский поток с переменным параметром; Mr - пуассоновский поток с условным параметром; Mi – примитивный поток; G – произвольный поток. Общие (схема распределения): S – система телетрафика. Если система телетрафика имеет конечное число линий или каналов V: FM(U) – система ослуживания полнодоступной системы; G – неполнодоступные системы; HG – равномерные системы; PG – ступенчатые системы; LS – многозвенные системы. Характеристики обслуживания: LL - обслуживание без потерь; L – обслуживание с явными потерями; W – обслуживание с ожиданием; R – обслуживание с повторением; r – число мест для ожидания; Выбор из ожидания: I – индивидуальная очередь; SP – равновероятностная выборка вызова из очереди; FF – упорядоченный выбор; LF – магазинный. Приоритет в обслуживании: PR – приоритет вызовов; PRR – относительный приоритет; PRA - абсолютный приоритет. Занятие прибора: S – занятие прибора последовательное; R – случайное занятие. Условное обозначение потока несколькими символами: 1-й – функция распределения промежутков м-д вызовами; 2-й - функция распределения длительности обслуживания; 3-й – схема распределения; 4-й – дисциплина обслуживания; 5-й – очередь дисциплины обслуживания; 6-й – выбор из очереди. В обозначении может участвовать от 3 до 6 групп условных обозначений. Основные термины теории телетрафика: событие, сообщение, вызов, освобождение, поток однородных событий. Событие – изменение какого-либо состояния. Сообщение – форма представления информации имеющая признаки начала и конца, и предназначена для передачи через сеть связи или коммутационную систему. Сообщения характеризуются: - объемом занимаемого канала; - временем передачи; - категорийностью; - адресами источника и приемника; - формой предоставления. Различают следующие виды сообщений: Обслуженное – переданное через сеть связи приемнику; Потерянное – поступившее в сеть связи и не переданное приемнику; Задержанное – поступившее в сеть связи и ожидающее начало передачи; Условно потерянное - поступившее в сеть связи и задержанное сверх допустимого срока, даже если оно потом и было передано. Вызов – требование источника на установление соединения, поступившее в сеть связи, коммуникационную систему, на вход системы искания. Вызовы характеризуются только моментом поступления. Вызовы подразделяются также на несколько видов: Обслуженный – получивший соединение в пределах рассматриваемого пучка линий, приборов либо коммутационной системы; Потерянный – получивший отказ сети связи (КС) в установлении соединения. Из-за занятости линии, прибора, приемника, ошибочного соединения; Задержанный – ожидающий начала установления соединения; Первичный – первый для данного сообщения; Повторный – поступивший в сеть связи через случайный или детерминированный момент времени после того, как был потерян предыдущий вызов, соответствующий тому же сообщению; Полностью обслуженный – вызов получивший соединение с приемником; Частично обслуженный – в пределах прибора или группы; Успешный вызов – окончившийся передачей сообщения к приемнику. Занятие – любое использование прибора, линии, устройства с целью установления соединения независимо от того, закончилось оно передачей сообщения или нет. Занятие характеризуется моментом занятия и длительностью. Освобождение – возвращение прибора, линии, устройства в исходное нерабочее состояние. Освобождение характеризуется только моментом наступления. Множество последовательных моментов поступления вызовов образует поток вызовов. Множество последовательных моментов изменения случайных событий образует поток однородных событий. Потоки вызовов могут быть детерминированными и случайными. Детерминированный поток – такой, в котором последовательность моментов поступления вызовов заранее известна. Случайный поток – такой, в котором последовательность поступления вызовов является случайной величиной. Случайные значения обозначаются прописными символами, а их возможные значения – строчными. Потоки вызовов характеризуются тремя параметрами (эквивалентными значениями): 1. Моментами поступления вызовов: t1, t2, … 2. Промежутками между моментами вызовов: z1, z2, … 3. Количеством поступивших вызовов за какой-то промежуток времени. Детерминированные потоки редко встречаются на практике, поскольку сложно обеспечить четкое поступление вызовов по заранее известному расписанию. Поток случайных событий определяется функцией распределения вероятности некоторой случайной велечины – Х F(x)=P{Xz. Особое внимание: Вероятность поступления вызовов характеризуется тремя эквивалентными значениями: 1. Совместный закон распределения случайных вызывных моментов. Под вызывным моментом понимается, когда поступает не менее одного вызова. 2. Совместный закон распределения случайных промежутков времени между вызывающими моментами 3. Совместный закон распределения вызовов на отрезках времени Потоки вызовов подразделяются на ординарные и неординарные. Ординарный поток – характеризуется последовательностью, определенной только закономерностью поступления вызовов. Неординарный поток вызовов – это такой поток, в котором каждый вызов имеет две и более характеристики, т.е. вероятность поступления, длительность обслуживания, направление и т.д. 1.2 ПРИНЦИПЫ КЛАССИФИКАЦИИ ПОТОКА ВЫЗОВОВ. Случайные потоки вызовов классифицируются с точки зрения: стационарности, последействия, ординарности. Стационарность – с течением времени вероятностные характеристики потока не меняются, т.е. вероятность поступления вызовов в любой момент времени постоянная. Ординарность – означает практическую невозможность группового поступления вызовов, иначе говоря, вероятность поступления двух или более вызовов за любой бесконечно малый промежуток времени ∆t есть величина бесконечно малая более высокого порядка, чем ∆t, т.е. . Последействие – означает зависимость вероятностных характеристик потока от предыдущих событий, иначе говоря, вероятность поступления вызовов в промежуток [t1, t2) зависит от числа, времени поступления и длительности обслуживания вызовов до момента t1. По характеристике и числу поступления вызовов поток вызовов можно разделить на: примитивный и простейший. Примитивный поток – стационарный, ординарный поток с последействием, параметры которого зависят от состояния коммутационной системы и числа свободных источников (≤100). Простейший поток – стационарный, ординарный поток без последействия, формируется от большого числа источников (>100). При большом числе источников относительное последействие не влияет на состояние системы. 1.3 ХАРАКТЕРИСТИКИ ПОТОКА ВЫЗОВОВ. К основным характеристикам потока вызовов относится ведущая функция – X или λ, параметр потока вызовов λ(t) и интенсивность µ. Ведущая функция – математическое ожидание числа вызовов в промежутке (0, t). Она неубывающая, неотрицательная и в практических задачах теории телетрафика информации непрерывна и принимает только конечные значения. Параметр потока вызовов λ(t) в момент времени t есть предел отношения вероятности поступления не менее одного вызова в промежутке [t, t+∆t) к величине этого промежутка ∆t при ∆t→0. Параметр потока определяет плотность вероятности поступления вызовов в момент времени t. Параметр потока вызовов характеризует не поток вызовов, а вызывающие моменты. Эта характеристика относится к фиксированному моменту времени. Интенсивностью потока называется математическое ожидание числа вызовов в единицу времени. Единица времени может быть выбрана произвольно, но в теории телетрафика применяется средняя длительность одного занятия . Интенсивность характеризуется как средняя интенсивность потока, так и мгновенная интенсивность потока – час наибольшей нагрузки. Средняя интенсивность потока – есть математическое ожидание числа вызовов в этом промежутке в единицу времени. Для стационарного потока. Мгновенная интенсивность потока µ(t) в момент времени t есть производная ведущей функции потока по t. Для нестационарного потока. . Если мгновенная интенсивность характеризует потоки вызовов, то параметр – поток вызывающих моментов. Поэтому всегда µ(t)≥ λ(t), а равенство имеет место лишь для ординарных потоков, когда в каждый вызывающий момент поступает только один вызов. 1.4 ПРОСТЕЙШИЙ ПОТОК ВЫЗОВОВ. Простейший поток – стационарный, ординарный поток без последействия, формируется от большого числа источников (>100). При большом числе источников отностительное последействие не влияет на состояние системы. Задается простейший поток, как и стационарный поток без последействия, семейством вероятностей Pi(t) поступления i(i=) вызовов в промежутке t. В заданный промежуток времени возможно поступление либо 1 вызова, либо одного освобождения, либо 2-х, 3-х и т.д. вызовов. Вероятности поступления этих значений независимы друг от друга, поэтому вероятностные состояния системы определяются как сумма всех вероятностных состояний системы. Где i – вероятность состояния системы. Если поток ординарен, тогда Т.е. система в бесконечно малый промежуток времени может получить либо одно изменение, либо остаться в первоначальном состоянии. Решая систему уравнений получим: P’(t)=-λPi(t)+λPi-1(t) P0(0)=1; Pi(0)=0 где i=(0,∞). Вероятность поступления вызовов в заданный момент t определяется формулой Пуассона. P(z1-P(z>t); P(z>t)=P0(t); P(z 1, т.к. 1 + a = , a «a» - число положительное. = f(T, разг, зан, но, ош, тех, пот, tc) здесь как и прежде: tc - время установления соединения и разъединения. tс - 2.5 с для АТСК tc - 1 с для АТС ДШС. Экспериментально установлено, что =1,051.25 Это значит, что непроизводительная нагрузка составляет от 5 до 25% от производительной нагрузки. Зависимость коэффициента от одного из влияющих факторов - Т представлена графиком. Из которого видно, что с ростом , коэффициент уменьшается. Рис 2. Зависимость . Понятие о потерях Часть поступающей на КС нагрузки теряется. Особенно это заметно в ЧНН. Yn = Y - Y0 Величина потерянной нагрузки является основной характеристикой качества обслуживания. Качество обслуживания зависит от принятой дисциплины обслуживания. С этой точки зрения различают следующие виды КС: - с явными потерями; • с условными потерями; • с комбинированными потерями; • с повторением; • приоритетные. Явными потерями называется такая дисциплина обслуживания коммутационной системой поступающего потока вызовов, при которой вызовы поступающие в момент отсутствия свободных соединительных путей, способных обслуживать эти вызовы, теряются. Коммутационные системы, реализующие такую дисциплину обслуживания, называются системами с потерями. Системы с потерями применяются в АТС ДШС и в АТСК, применительно к разговорному тракту. Условные потери - это такая дисциплина обслуживания при которой вызов, поступивший в момент отсутствия свободных соединительных путей, способных обслуживать этот вызов, не теряется, а ставится на ожидание (обслуживается с ожиданием). Коммутационные системы, реализующие такую дисциплину обслуживания, называются системами с ожиданием. Системами с ожиданием являются машинные АТС, УУАТСК, квазиэлектронные и электронные АТС. Комбинированные потери являются разновидностью условных потерь с ограничением по какому - либо признаку. Например, по числу вызовов находящихся на ожидании или по времени ожидания. В первом случае при поступлении числа вызовов больше предельно - допустимого значения, вновь поступившие вызовы теряются. Во втором случае, если вызовы находятся более tогр, то они теряются. Системы с потерями: Различают потери: 1. по вызовам - Рв; 2. по времени – Рt; 3. по нагрузке - Рн; ()= - потери по вызовам за промежуток времени. Это случайная величина, т.к. число поступивших и число потерянных вызовов есть величины случайные. В вероятностном смысле потери по вызовам можно представить следующей формулой: = где: - интенсивность теряемого потока вызовов; - интенсивность поступающего потока вызовов; ()= здесь: Yn(t1, t2) - нагрузка потерянная за отрезок [t1 t2); Y(t1,t2) - поступающая нагрузка; В вероятностном смысле (эта величина также случайная) можно записать: = , Под потерями no времени понимается доля времени [t1 t2), в течение которого заняты все соединительные пути, способные обслужить поступающий поток вызовов, если последний имеет место. Другими словами это есть "опасное время", в течение которого теряются поступающие вызовы. Рис 3. К определению потерь по времени. В промежутки заняты все приборы коммутации. Тогда: (t1, t2)= Для любого вида потерь справедливо: 0<Р< 1 Величину потерь измеряют либо в процентах, либо в промилях, либо в долях. Наиболее часто в промилях. 1 промиля (1%о) = 0,1 процента (0,1%) Пример: Поступило С=1000 выз. Сн = 5 выз. Рв = 5/1000 = 0,005 = 0,5% = 5‰. Пропускная способность коммутационной системы. Основным критерием качества обслуживания является потерянная нагрузка. Однако на практике более удобно пользоваться потерями. Поэтому будем считать основной характеристикой качества обслуживания потери - Р. Потери на сетях связи нормируются. На АТС ДШС они нормируются по ступеням искания: Р = 0,001 -0,005 Общие потери на ГТС между двумя абонентами: Р = 0,02 - 0,025 = (20 - 25)% На СТС более высокие потери по сравнению с ГТС, что объясняется большими длинами соединительных линий и малой их загруженностью. Пропускная способность КС задается как функция от потерь. Под пропускной способностью понимается нагрузка, которую обслуживает КС, при заданном качестве обслуживания (при заданной величине потерь). Y = f(P). Однако пропускная способность КС определяется потерями неоднозначно. На ее величину влияет ряд факторов: Y = f(P, v, П, S, Cx, H(X), Д), где: Р - потери сообщения; v - емкость обслуживающего пучка; П - класс потока вызовов; S - структура КС; Сх - способ объединения выходов; Н(Х) - закон распределения длительности обслуживания вызовов; Д - дисциплина обслуживания вызовов; На практике удобнее определять не нагрузку, а потери: Р =(Y, v, П, Сх, S, Н(Х), Д). Часто вместо Y — нагрузки пользуются параметром потока - , Р = (, v, П, Сх, S, Н(Х), Д). Нас интересует состояние коммутационной системы, как вероятностный процесс. Введем обозначение - вероятность того, что в КС занято ровно i путей. Очевидно, что : = f(, v, П, Сх, S, Н(Х),Д). Свойства и характеристики нагрузки в цифровых сетях интегрального обслуживания. На современном этапе развития систем автоматической коммутации наблюдается значительный рост межмашинного обмена. В некоторых странах его объем начинает превосходить объем телефонного обмена. В этих условиях чрезвычайно важно своевременно отслеживать свойства и характеристики нагрузки в сети связи и корректировать модели расчета систем связи. Основные результаты таких исследований, выполненных в последнее десятилетие, сводится к тому, что потоки требований на установление соединения не являются пуассоновскими. Длительность сеансов описывается распределениями логонормального, а не показательного типа (т.е. характеризуется наличием "весомых хвостов"), поступления пакетов, а также требования на установление сеансов связи коррелированны. Особенностью этих систем является образование т.н. пачечной нагрузки, которая практически не учитывается в традиционных пуассоновских моделях. Исследование нагрузки позволило обнаружить неизвестное ранее явление структурного сходства статических характеристик пакетной нагрузки при ее измерении в разных режимах времени. Это явление получило название самоподобия. К числу объектов на которых обнаружены подобные явления, относятся пакетная передача данных в ЦСИО, локальные вычислительные сети Ethernet, сети стандарта ОКС № 7, видео передача по сети ATM и многое другое. К самоподобным процессам относятся процессы, обладающие следующими свойствами: • > дисперсия среднего значения выборки убывает медленнее, чем обратная величина объема выборки; • корреляция убывает не по показательному, а по гиперболическому закону, т.е. характеризуется долгосрочной зависимостью; • спектральная плотность описывается степенной функцией в области начала координат; Теоретические свойства приводят к тому, что свойство сглаживания случайного процесса с увеличением времени, широко используемое в традиционных моделях ТТ, в потоках высокоскоростной цифровой передачи отсутствует. Как следствие этого свойства является то обстоятельство, что объединение конечного числа цифровых потоков не приводит к пуассоновскому характеру суммарного потока. Основной характеристикой самоподобной нагрузки является параметр Херста - Н, который является мерой самоподобия, или статистической инерцией процесса. Значение параметра Херста лежит в пределах: 0,5 < Н < 1 При Н = 0,5 процесс не обладает самоподобием и может быть описан Марковской моделью. Если Н=1, то процесс имеет жесткую долгосрочную зависимость, т.е. является детерминированным. Таким образом, самоподобные процессы характеризуются строгим неравенством. 0,5 < Н < 1 Результаты, полученные Херстом (1951г.), послужили важным толчком для дальнейшего развития теории самоподобных процессов с 3х точек зрения: теории фракталов, хаотических отображений и степенных законов. Теория фракталов. Определение автора: "Я задумал и разработал новую геометрию природы. Она описывает многие неправильные и отрывочные образы и приводит к завершенным теориям путем определения форм, которые я называю фракталами". В качестве примера самоподобного процесса с непрерывным временем может служить Фрактальное броуновское движение (ФБД), которое записывается в виде: (t) = X где: X - нормально распределенная СВ с единичной дисперсией; Н - параметр Херста. Плотность вероятности ФБД имеет вид: нулевым средним значением и (x,t)= При Н=0,5 процесс характеризуется независимыми и некоррелированными приращениями. Хаотическое отображение. Трудности моделирования и расчета систем с входящими потоками типа ФБД привели к разработке метода хаотических отображений. Суть метода заключается в том, что зная начальное условия и параметр расходимости процесса (обычно экспоненциальный, называемый параметром Ляпунова), дальнейшее поведение системы может быть вычислено для всех моментов времени. На практике начальные условия задаются с конечной точностью, что приводит к непредсказуемости долгосрочных характеристик таких систем. Степенные функции. Важной характеристикой самоподобных процессов является долгосрочная зависимость, которая может быть описана в виде соотвествующей степенной функции. С помощью степенных функций были выполнены исследования ошибок в цифровых каналах связи, потоков видеотрафика с переменной скоростью передачи и нагрузки локальных вычислительных сетей типа Ethernet. Раздел 3 Полнодоступный пучок. Система с явными потерями. Понятие о пропускной способности коммутационных систем (КС). Для анализа и сравнения КС и отдельных пучков линий вводится понятие пропускной способности системы или пучка. Под пропускной способностью (ПП) понимается интенсивность обслуживания этой системой нагрузки или пучка линий в рассматриваемом промежутке времени при заданном качестве обслуживания. ПП определяется дисциплиной обслуживания. Дисциплины обслуживания бывают без потерь и с потерями. При обслуживании с явными потерями нормируется вероятность потери вызова. C повторением – вероятность потери первичных вызовов. С ожиданием – вероятность ожидания. ПП системы, в общем случаем зависит от: 1. Свойств поступающего потока вызовов 2. Закона распределения времени обслуживания 3. Структуры и емкости коммутационной системы и способов включения ее выходов (полнодоступный, неполнодоступный) 4. Дисциплины обслуживания вызовов 5. Установления нормы качества обслуживания Для повышения качества используется комбинированная дисциплина обслуживания. Обслуживание симметричного потока с простым последействием. Пример: Полнодоступный пучок емкостью v – линий, включенных в выходы неблокирующих коммутационных систем с потерями, обслуживает вызовы, образует симметричный поток с простым последействием с параметром . Длительность обслуживания вызовов распределяется по показательному закону Где h – параметр длительность занятия =1 условная единица времени. Требуется определить вероятности различных состояний полнодоступного пучка в процессе обслуживания поступающих вызовов - . Если коммутационная система является неблокирующей и полнодоступной, то оценка вероятностного состояния (пучок линий) определяется макросостоянием, то есть каким-то общим состоянием. Если КС содержит неполнодоступный пучок, то оценка вероятностного состояния определяется микросостоянием, то есть вероятностным состоянием каждой отдельно взятой линией пучка. Для микросостояний необходимо , где V – количество линий пучка. Для оценки макросостояний используется теория вероятности Маркова. В этой задаче достаточно исследовать макросостояние системы, то есть состояния различающиеся числом i одновременно заняты линий в любой момент времени. Определим вероятность различных макросостояний системы в момент нахождения системы в состоянии i и ее возможных изменений за бесконечно малый промежуток времени. В процессе изменения состояния системы за бесконечно малый промежуток времени, следующих состояний, используя «теорию Маркова «гибели и рождения»», определяются в процессе рождения отождествляется с процессом занятия, а процесс гибели – освобождение линий пучка. Поэтому, используя эти состояния, данный процесс изображается схематично и теоретически. 1. В момент времени t пучок находится в состоянии равновесия. Используя состояние равновесия, определяем состоянием i-1,и за бесконечно малый промежуток может поступить только 1 вызов 2. В момент времени t пучок находится в состоянии i+1 и за бесконечно малый промежуток времени освобождается 1 линия 3. В момент времени t пучок находится в состоянии i и за не произойдет никакого изменения состояния 4. За время (t) в пучке произойдет 2 или несколько изменений состояний Так как все эти условия исключают друг друга и являются взаимно непересекающимися, поэтому вероятностное состояние определяется как сумма всех событий Найдем вероятности поступления точно одного вызова и точно одного освобождения за бесконечно малый промежуток времени. Из определенного параметра Поступление одного или более вызовов: Тогда: Вероятность освобождения одной и более линии r – занят прибор Вероятность освобождения H - длительность обслуживания Подставляя данные в выражение (1) и перенося неизвестные из первой чатси в другую и разделив обе части уравнения на r получим Переходя к пределу, то есть эти отношения определяет предел Исследуя это состояние можно определить что при i=0 переход в состояние i-1 невозможно, поэтому из этого уравнения вытекают 2 состояния Продифференцировав данное выражение получим Обозначив из этой систему получим , тогда Тогда выражая вероятности Pi через P0 получим: Из этого состояния возможны: Решая эти уравнения относительно P0 получим: Вероятность потерь по времени можно рассматривать как долю времени в течении которого в пучке заняты все линии (4) Вероятность потерь по вызовам – отношение интенсивности потерянных вызовов км поступающим. определяется вероятностью занятости всех линий. Обслуживание вызовов простейшего потока. Полнодоступный пучок емкостью V-линий, который включен в выходы неблокирующей коммутационной системы с потерями, обслуживает вызова, образующие простейший поток с параметром Длительность обслуживания вызовов распределяется по показательному закону. Требуется определить вероятностное состояние КС , , ,(вероятность которой по нагрузке, времени, вызовов) По окончанию предыдущего анализа параметром простейшего потока является постоянной величиной, не зависит от состояния КС, поэтому в выражения 3,4,5 подставляя вместо ,получаем Данное выражение называется распределением Эрланга. Оно показывает, что вероятность зависит от числа занятых линий, емкости пучка и параметра потока вызовов. Вероятность потерь по времени Потери по вызовам, теряются вызовы свыше V, это V+1 в простейшем потоке эти параметры равны между собой Если V ≠1, то вероятностное состояние системы Установим зависимость вероятностного состояния системы от поступающей нагрузки - простейший поток Подставляя это в предыдущее выражение Вероятность того, что в пучке V заняты все линии Если V, тогда Получим: Выражение Эрланга преобразуется в распределение Пуассона. Вероятность потерь на нагрузке (6); – обслуженная нагрузка Y - поступающая нагрузка – потери по нагрузке Подставляя в уравнение (6) и решая это уравнение, получим: (7) Если число линий стремится к , то потери по времени 0 , тогда обслуженная нагрузка Обслуживание вызовов примитивного потока. Полнодоступный пучок емкостью V – линий, включенных в выходы неблокирующей коммутационной схемы с потерями, обслуживает вызовы, которые образуют примитивный поток с параметром . Длительность обслуживаемого вызова распределяется по показательному закону. Требуется определить , , , (вероятностное состояние системы ) Параметр примитивного потока =(N-i) N – общее число источников i – число занятых источников – параметр потока вызовов от свободного источника. Анализируя состоянии КС аналогично предыдущим и заменяя вместо =(N-к) , подставляя в выражение 3,4 и 5 можно получить вероятностное состояние системы: числитель- Число стираний из N по i знаменатель- Число сочетаний (10) формула Энгсета Определяет вероятность того, что в полнодоступном пучке емкостью V – линий обслуживается примитивный поток в любой произвольный момент времени занято точно i линий. Если N, , тогда приводя соответствующие расчеты Тогда предельно вероятностное состояние системы: -вероятностное состояние системы при N Из Формулы Энгеста, получается формула Эрланга и примитивный поток стремится к простейшему потоку. Состояние между параметрами потока вызовов и нагрузкой, поступающей от одного источника. Рассмотрим состояние системы в которой число источников = V. Для примитивного потока достаточно исследовать состояние N=V=1. В этом случае в (10) подставляем 0 и 1, получим Выражая вероятность того, что поступил 1 вызов (интенсивность, создаваемая одним источником ) (11) – параметр потока Так как в бесконечно малый момент времени от одного источника может поступить только один вызов, то параметр потока (12) Параметр потока вызовов одного источника численно равен интенсивности поступающей нагрузки от одного источника. Подставляя в уравнение (3) вероятностное состояние источника. Состояние, при котором система может находиться в состоянии, когда: • Все приборы свободны • Все приборы заняты • В состоянии i - для примитивного потока Система находится в состоянии - число приборов равно числу источников, все приборы свободны. Поступает вызов, система переходит в состояние , где - это Если емкость станции равна числу источников, т.е V=N, то мы получим: Вероятность того, что в произвольный момент t из N источников занято i истояников – распределение Бернули. Потери по времени численно равны вероятности занятости всех линий пучка (15) Потери по вызовам, подставляя параметр примитивного потока в формулу (5) получим (16) Потери по нагрузки Поступающая нагрузка Y=N= Подставляя данное значение получим Подставляя и приводя к общему знаменателю (17) Из этого следует, что потери по нагрузке значительно меньше потерь по времени и даже в том случае, когда N=V. Потери по нагрузке меньше, чем по вызовам. Для простейшего потока , , равны между собой. В примитивном потоке , , ,различны и наименьшее это , , Раздел 4 Полнодоступный пучок. Система с ожиданием. Для количественной оценки качества обслуживания дисциплины с ожиданием рассчитываются следующие характеристики – вероятность ожидания для поступающего вызова свыше t (P()), P() - время ожидания задержки вызовов. Среднее время ожидания по отношению ко всем поступающим вызовам. - среднее время ожидания по отношению ко всем задержанным вызовам. – средняя длина очереди P(R>r) - вероятность того, что длина очереди > r заданной. Основными характеристиками являются P()= - вероятность поступающих вызовов. Вероятность ожидания для любого поступающего вызова свыше времени t Для оценки состояния и качества обслуживания данной дисциплины поставим задачу из которой следует, что полнодоступный пучок емкостью V – линий, включенный в выходы неблокирующей системы с ожиданием, обслуживает вызовы, поступающие на КС, создающую простой поток с параметром . Каждый вызов для обслуживания занимает любую свободную линию пучка. Если все линии заняты в момент поступления вызова, то вызов становится в очередь на ожидание. Поступающие вызовы на ожидание образуют очередь различной конечной длины. Вызовы находятся на ожидании обслуживания в порядке очереди. Длительность обслуживания вызова распределяется по показательному закону , где - параметр качества обслуживания. В КС V – линий для обслуживания и r – прибор для ожидания. В результате чего, количество обслуженных вызовов равно (V+r) и при количестве (V+r+1) возникает потеря явная. Для оценка качественных характеристик обслуживания системы также воспользуемся теорией Маркова, т.е соответствия из 4 раздела уравнения 3,4 и 5 (3) из предыдущей главы Так как в рассмотренной задаче на обслуживание поступают вызовы простого потока, то параметр освобождения имеет два значения (1) Подставляя вместо (2) (3) Решая данное уравнение и подставляя значение конечной величины < , при i > V, и Y < V. (4) Вероятностное состояние системы с ожиданием составляет (5) Рассмотрим данное состояние при ограничении 0iV и переходя к системе с потерями которые определяются =(Y), получим (6) Так как в выражение (6) знаменатель > 1, то меньше(Y) для всех значений в пределах 0iV (7) Тогда рекуррентное значение полученное для системы с потерями сохраняется и для системы с ожиданием при i < V, т.е . Несколько другой характер при состоянии i>V+r+1 : Из этого соотношения вытекает, что >>, т.е вероятность того, что в пучке заняты все линии и на ожидания нет вызова больше, чем вероятность того, что на ожидании находится 1 вызов, > 2 вызов…. Поэтому в системе с ожиданием потери по времени есть доля времени в течении которого все линии пучка заняты и на ожидании находится r=0,1,2…вызовов. Исходя из этого, потери по времени равны вероятности того, что поступивший вызов не будет немедленно обслужен, а будет ожидать начала обслуживания. Т.е Подставляя это выражение в формулу (6) Это вторая формула Эрланга Это выражение показывает, что потери по t численно равны условным потерям P(), которые могут быть определен при помощи таблицы 1 формулы Эрланга, т.е (9) Потери по времени с в системе с ожиданием больше, чем в системе с явными потерями. Характеристика качества обслуживания в системе с ожиданием. Качество обслуживания вызовов в системе с ожиданием характеризуется вероятностью задержки поступающего вызова свыше времени t. Время обслуживания начала ожидания больше времени t для вызова, поступающего на ожидание, т.е () Тогда (10) Для оценки качественных характеристик системы с ожиданием и системы с потерями являются, значение времени, потери при которых дают сравнение двух систем. Для определения этого сравнения приравнивают потери (вероятностные потери в системе с потерями), в которых время ожидания возьмем одинаковыми. (11) Решая данное уравнение, получим (12) Т.е в системе с ожиданием нет такого времени Среднее время ожидания (13) (14) Среднее время задержки (15) (16) Средняя длина очереди (17) (из 14) Все эти формулы проанализированы Бергом по отношению к однолинейной системе Где t - количество приборов ожидания. Раздел 5 Неполнодоступный пучок. Система с явными потерями. Раздел 6 Звеньевые коммутационные системы. Раздел 7 Однозвенные полнодоступные коммутационные системы. Раздел 8 РАСПРЕДЕЛЕНИЕ НАГРУЗКИ И ПОТЕРЬ НА СЕТЯХ СВЯЗИ. Суммарные потери. Основной количественной характеристикой качества обслуживания потоков вызова в сетях связи является математическое ожидание величины потерь из-за отсутствия свободных соединительных устройств. Пусть соединительный тракт содержит п последовательно включенных ступеней искания (см. рис 1.) Рис 1. – Структура соединительного тракта между двумя абонентами. На рисунке показаны: ri- число направлений на i-й ступени; pi - вероятность потерь i-й ступени. Требуется определить результирующую(суммарную) вероятность потерь от абонента А до абонента В. Под суммарными потерями понимаются общие потери, которые имеют место при установлении соединения между вызывающим и вызываемым абонентами на всех ступенях искания. Обозначим эти потери - Р. Исследования показали что величина Р зависит от величины потерь на каждой ступени, числа ступеней искания, числа направлений, включаемых в каждую ступень, то есть P = f(Pi,n,ri), i=. При этом величина потерь находится в интервале , Где: – максимальное значение потерь на ступенях соединительного тракта. Причем при ri (i=)=1. P= В другом предельном случае при r процессы обслуживания вызовов на отдельных ступенях искания становятся независимыми и для определения величины Р можно использовать правило сложения вероятностей P=1- (1) Величины , нормируются, Их величины на различных ступенях искания изменяются в пределах 0,001 < , < 0,005. В этих условиях без большой погрешности выражение (1) можно заменить простой формулой P Нормы суммарных потерь для разных видов ТФОП приведены в [15]. В заключение отметим, что в пределах одной сети суммарные потери распределяются таким образом, что на более дорогие участки соединительного тракта отводится большая величина потерь. Способы распределения нагрузки. Телефонная нагрузка, создаваемая источниками, включенными в АТС распределяется между другими АТС телефонной сети. При m АТС на сети интенсивности межстанционных потоков нагрузки полностью характеризуется следующей матрицей (2) Отметим некоторые свойства этой матрицы: 1. Относится к классу квадратных; 2. Элементами главной диагонали являются внутристанционные нагрузки =(i=); 3. Сумма элементов по строкам определяет исходящую нагрузку АТС ; 4. Сумма элементов по столбцам определяет входящую к АТС нагрузку. = 5. Сумма всех элементов матрицы определяет общую исходящую (входящую) нагрузку сети связи == Задача распределения нагрузки сводится к определению всех элементов матрицы (2). Существующие способы распределения нагрузки рассмотрим на примере простейшей сети из трех АТС Рис. 2 Виды потоков нагрузки на районированной ГТС. На рис. 2 обозначены виды потоков нагрузки на районированной ГТС. Обозначим Y1 Y2, Y3 возникающие нагрузки АТС . Тогда общая возникающая нагрузка сети определится как YC = Y1+Y2 + Y3 Немецкий специалист Люббергер предложил распределить нагрузку в сети пропорционально долям возникающих нагрузок входящих АТС в общей нагрузке телефонной сети. Например, для РАТС 1 имеем: ;;; Таким образом, Y1= Y11 +Y12 +Y13 или Y1= ;+ + Английский ученый Майтланд предложил учитывать неравномерность тяготений между разными АТС с помощью т. н. коэффициентов тяготения Y1= f11 +f12 +f13 откуда ;;; Приведенные формулы позволяют выражение для коэффициента тяготения ; ; В общем виде можно записать В выражение (3) входит общая возникающая нагрузка всей сети, которая с развитием сети увеличивается. Следовательно, и значения коэффициентов f по мере расширения ГТС будут иметь тенденцию к увеличению. Это обстоятельство в значительной степени затрудняло прогнозирование межстанционной нагрузки. Для устранения отмеченного недостатка польский ученый Кун предложил нормировать величину fij относительно его внутристанционного значения Коэффициенты n называются нормированными коэффициентами НКТ. Исследование динамики их изменения в процессе развития ГТС за длительные отрезки времени полностью подтвердило гипотезу Куна о большей стабильности их значений. Значения НКТ зависит от большого числа влияющих факторов. Наиболее значимым из них является расстояние между станциями. Эта зависимость иллюстрируется графиком на рис. 3 Рис 3. – Зависимость nij=f(lij) Из рисунка видно, что с увеличением расстояния между станциями значение НКТ уменьшается. Приведенная графическая зависимость аппроксимирована для некоторых ГТС уравнением nij =a+C lij - расстояние между станциями в км, а,в,с - параметры аппроксимирующей кривой. Формулу (4) обычно используют для определения НКТ в процессе проектирования сетей связи. Колебания нагрузки. Расчетная интенсивность нагрузки. Телефонная нагрузка является случайной величиной. Поэтому нагрузка в ЧНН, порядок определения которой рассмотрен в разделе 2.3, не является величиной постоянной. Работы выполненные в ЛО НИИС под руководством проф. Б.С. Лившица, показали, что распределение нагрузки по отдельным ЧНН хорошо аппроксимируется нормальным законом распределения. При этом вероятность отклонения нагрузки в произвольно взятый ЧНН-У. От МО ожидания нагрузки в ЧНН-У определяется из выражения P(|-Y|)< где: σ(y) - СКО нагрузки в ЧНН; Ф(t) - нормированная функция Лапласа; t - аргумент функции Лапласа. Из выражения (5) следует, что реальные потери в сети связи будут меньше или равны нормированным только в 50 % всех ЧНН. Очевидно, что для повышения качества обслуживания расчет объема оборудования необходимо проводить по расчетной нагрузке Yp, причем Yp>Y. Для определения величины Ур можно использовать, например, 75% квантиль распределения Yp =Y+t Здесь t можно трактовать, как коэффициент доверия, соответствующей заданной доверительной вероятности (5). При Р = 0,75, t = 0,6742. Окончательно имеем Yp =Y+0.6742 Обратное преобразование имеет вид Y= Формула (7) табулирована. В заключение отметим, что в формулах(7 и 8) Y и Yp связаны не линейно. Это означает, что расчетная нагрузка не обладает аддитивными свойствами. Все арифметические операции можно выполнять только со средними значениями нагрузки. Раздел 9 Расчет обходных направлений в сетях связи Раздел 10 Измерение нагрузки и потерь в сетях связи Раздел 11 Методы расчета характеристик качества обслуживания в цифровых системах интегрального обслуживания (ЦСИО) Общие положения Объединение различных видов связи на основе единых организационных и технологических принципов является одним из этапов создания цифровой сети с интеграцией служб (ISDN). Такая сеть предоставляет пользователям возможность мультисервисного обслуживания, т.е. передавать, принимать, обрабатывать различную по виду и объему информацию в цифровом виде. При этом возникают вопросы оценки качества обслуживания пользователей (прямая задача) и вопросы расчета объема ресурсов сети (обратная задача), которые зависят как от характера трафика, так и от пропускной способности отдельных звеньев мультисервисной сети (МС). Изложению особенностей трафика в ISDN посвящены разделы 1.9 и 2.8, в которых показано, что потоки вызовов в этих сетях не являются простейшими, а нагрузка не является пуассоновской. Что касается входящих потоков, то промежутки между вызовами распределяются не по показательному закону, а представляют собой свертку гамма-распределений разных порядков и распределения Парето. Нагрузка на сетях мультисервисного обслуживания носит самоподобный характер, т.е. отличается от пуассоновской наличием долгосрочной зависимости. В разделе 2.8 сформулированы три точки зрения к описанию самоподобной нагрузки: • Теория фракталов; • Хаотические отображения; • Степенные функции. В качестве примера самоподобного процесса с непрерывным временем введено понятие - нагрузка типа ФБР (фрактальное броуновское движение). Таким образом, при расчете качества обслуживания (ресурсов сети) необходимо учитывать изменение класса входящих потоков и изменение свойств и характеристик создаваемой ими нагрузки. В нашей стране активно создается узкополосная ISDN (N-ISDN), которая предоставляет пользователям услуги на основе многоканальной коммутации. Эти услуги требуют различной скорости передачи информации и, как следствие, каналов с различной пропускной способностью. В сети N-ISDN это базовый канал типа В (64 Кбит/с) и его кратные комбинации 2В, ЗВ, ..., ЗОВ. Обязательными являются каналы В, 2В и З0В, представляющие стандартные интерфейсы станций с услугами ISDN. В связи с этим возникает важная проблема - разработка метода расчета числа потоков со скоростью 2 Мбит/с (канал З0В) на магистралях ISDN. Обслуживание самоподобной нагрузки По аналогии с телефонными сетями, на которых различают удельную абонентскую и общую нагрузку, в современных сетях цифровой передачи различают нагрузку на прикладном и сетевом уровнях. Самоподобная нагрузка на прикладном уровне может наблюдаться, если самоподобие присуще самому источнику. Примером может являться источник цифровой видеопередачи с переменной скоростью. Самоподобная нагрузка на сетевом уровне формируется в ходе ее взаимодействия с сетью и может меняться в зависимости от перегрузки сети, схем переприема, требованиям к объемам файлов и др. Все это затрудняет выполнение расчетов и требует новых подходов в ТТ. Одной из первых работ в этом направлении являются исследования финского специалиста И. Норроса. Он модифицировал формулу Полячека -Хинчина (см. раздел 4.5), учитывающую самоподобный характер поступающей нагрузки =(1+) где: Н - параметр Хёрста, характеризующий степень самоподобия (0,5<Н<1). При Н=0,5 нагрузка теряет свойства самоподобия, приведенное выражение упрощается и принимает классический вид: =(1+) Для модели М/М/1 при = 1 а, = 1. Тогда ;;; Для модели М/D/1 =0 ;;. приведенные выражения иллюстрируются графиком на рис.1, где показана зависимость длины очереди от пуассоновской нагрузки и самоподобной нагрузки типа ФБД с Н=0,75; 0,9. Рис. 1 – Зависимость j=f(y) Как видно из рисунка, требования к накопителям, предъявляемые в классической теории телетрафика, здесь отвергаются начиная с небольших значений нагрузки, из-за сильной долгосрочной зависимости нагрузки (большие значения параметра Херста). Поэтому, если нужно обслужить большую самоподобную нагрузку, необходимо предусмотреть накопители достаточно большой емкости, чем это требуется на основании расчетов классической теории. Расчет пропускной способности мультисервисных телекоммуникационных сетей. Постановка задачи здесь аналогична предыдущему методу. Системы коммутации на узле коммутации (УК) N-ISDN должны соединять между собой одновременно i каналов l V. Тогда потери i-канальных вызовов из-за занятости каналов пучка будут равны , а общие потери из-за занятости каналов пучка , где: - вероятность занятости (V-j) каналов из v. С учетом того, что среди i свободных i каналов могут находиться заблокированные, вероятность блокировки при установлении соединения для i-канального вызова: где: Pj - вероятность занятости j каналов из v; =1-- условная вероятность того, что вызов, поступивший в i-ом состоянии системы будет обслужен; =- условная вероятность того, что вызов, поступивший в i-ом состоянии системы будет потерян; =1. Средневзвешанные потери вследствии внутренних блокировок на узле: . Общие потери от внутренних блокировок УК и потерь из-за блокировки исходящего пучка каналов P=+. Величина (d) интерпретируется как эффективная доступность узла коммутации в данном направлении. Тогда при d=V идеально-симметричная система переходит в полнодоступную и полученные формулы переходят в формулы мультисервисного полнодоступного пучка каналов. Изложенный метод может использоваться для определения качества обслуживания пользователей (прямая задача) и расчета ресурсов сети (числа каналов, скорости передачи и др.) - обратная задача. Прямая задача. Полагая, что пользователю сети может представляться обслуживание по каналам В, 2В и З0В, обозначим поступающие (исходящие и входящие) нагрузки соответственно через А1 А2, А30- данное соотношение называется профилем трафика. Зададимся профилем трафика типа А1: А2:A30=90:9:l, причем А1=12 Эрл. Результаты вычислений по приведенным выше формулам представлены на рис. 2. Рис. 2 – Зависимость Р=f(V) Из рисунка видно, что при общей тенденции к уменьшению, потери имеют волнообразный характер. Это означает, что необоснованное увеличение числа цифровых каналов может привести даже к ухудшению качества обслуживания для некоторых классов пользователей. Аналогичная тенденция сохраняется при изменении профиля трафика. Обратная задача. Результаты, полученные при решении прямой задачи позволяют сделать следующие выводы: • Предоставление услуг, требующих различного числа канальных ресурсов, приводит к значительной неравномерности вероятности потерь для различных пользователей. • При фиксированной емкости пучка каналов невозможно одновременно удовлетворить наперед заданное качество обслуживания для разных классов пользователей. Одним из возможных подходов к решению этой задачи является использование нормированных средневзвешенных потерь. Проиллюстрируем это понятие графиком зависимости потерь от числа двухмегабитных потоков для трафика, имеющего следующий профиль: А1:А2:А30=100:10:1. При этом А1=100 Эрл, А2=10 Эрл, А30=1 Эрл. Рис. 3 - Зависимость потерь от числа двухмегабитных потоков для трех классов пользователей. Из рисунка видно, что при выборе средневзвешенных потерь Р=0,001 требуется 8 двухмегабитных трактов, что соответствует пропускной способности в 16 Мбит/с или V=240 каналов по 64 Мбит/с в каждом. В этом случае качество обслуживания будет следующим: Р1=6,2Е-0,4, Р2=1,27Е-0,3, Р30=3,83Е-0,2. Это является вполне приемлемым даже для наихудшего случая -предоставления услуги З0В. Изложенный выше материал позволяет сделать следующие выводы: • Расчет можно выполнять для средневзвешенных потерь. • При выборе нормы среднеквадратичных потерь Р=0,001, качество обслуживания в наихудшем случае (услуга З0В) не превышает нескольких процентов. Приведенные численные исследования различных профилей трафика показали, что при определении числа цифровых трактов достаточно ограничиться применением линейной регрессии. На рис. 4 представлены зависимости необходимого числа двухмегабитных трактов от изменения интенсивности нагрузки А) для трех профилей: А1:А2:А30=100:0:0; А1:А2: А30=100:10:1; А1:A2: А30=l00:10:3. Профиль 100:0:0 соответствует случаю отсутствия мультисервисного обслуживания. На этом рисунке для сравнения показано число потоков 2Мбит/с, размещаемых в синхронном транспортном модуле STM-1 цифровой системы SDN. Рис. 4 - Зависимость числа двухмегабитных каналов ог нагрузки А1для трех профилей трафика. Из рисунка видно, что относительно небольшое увеличение числа пользователей услуги З0В, приводит к необходимости резкого увеличения пропускной способности магистралей. Например, увеличение трафика А30 с4 до 12 Эрл удваивает число двухмегабитных потоков. В заключение отметим, что в случае, если заданный трафик отличается от рассмотренных, то пользуясь рассмотренным методом, можно получить аналогичные расчетные формулы или номограммы. Приближенный метод расчета характеристик качества обслуживания распределенных систем обработки информации Как уже отмечалось, исследуемые модели характеризуются тем, что в сети связи циркулируют потоки трафика, включающие информацию разного вида. При этом одни и те же ресурсы сети служат для коммутации и передачи потоков с отличающимися характеристиками, т.е. в данном случае имеет место многоканальная коммутация. Объектом исследования в данном методе [18] авторы выбрали полнодоступную группу из v цифровых каналов. Входящим потоком принимается неординарный маркированный пуассоновский поток (НМПП). Общий поток интенсивностью создается вызовами (n) типов, при этом каждый вызов с вероятностью (i= ) требует одновременного наличия свободных каналов, которые занимаются в течение времени , и после этого одновременно освобождаются. Основная идея метода заключается в замене НМПП эквивалентным по действию ординарным рекуррентным потоком. Для обоснования данного подхода рассмотрим полнодоступную систему s, состоящую из v каналов. На систему поступает простейший поток с параметром , причем каждый вызов требует для обслуживания m каналов и занимает их на время h. Моменты распределения поступающей нагрузки определяется как у = hm; D = hm2, а коэффициент скученности нагрузки z= =m. Для расчета вероятности потери вызова исследуем модифицированную модель из v = комплектов, каждый из которых объединяет m каналов. Отдельно поступающему вызову требуется для обслуживания один из таких комплектов, поэтому поток вызовов можно считать ординарным. Поступающая нагрузка в модифицированной модели определяется числом занятых комплектов, считается пуассоновской первого рода с первым моментом, равным h. Это положение позволяет определить вероятность потери вызова () по первой формуле Эрланга. В целом для системы s имеем: (), (1) где: z - коэффициент скученности нагрузки. В случае многомерных потоков нагрузки с заявками разных типов имеем: ; D=; =. Откуда видно, что скученность суммарного потока неоднородных вызовов равна средневзвешенному числу каналов (), которые требуются для обслуживания одной заявки i-гo типа, с весами , равным соответствующим нагрузкам. После определения по формуле (1) средней вероятности потерь для произвольной заявки () расчет индивидуальных потерь () для заявок i-гo типа (i =)можно произвести с помощью приближенной формулы = (2) В таблице 1 приведены результаты расчета потерь по приведенным выше формулам и точным при n=3, m=3 и v=70. Таблица 1 Результаты вычеслений. n v i прибл. точно 3 70 1 20 1 0,01347 0,0137 2 10 2 0,0274 0,0293 3 5 3 0.0412 0,0470 Из таблицы видно, что точность приближенной оценки вероятности потерь для индивидуальных потоков является вполне удовлетворительной. Самоподобные (фрактальные) модели трафика Во всех рассматриваемых ранее моделях потоков событий считалось, что вероятность появления следующего события зависит только от времени, прошедшего от момента совершения предыдущего события и не зависит от всей предыстории появления событий ранее. Однако, в некоторых случаях такие модели не могут адекватно отразить реальный поток событий. По­этому кроме потоков без последействия приходится рассматривать и та­кие, в которых вероятность появления следующего события зависит от на­ступления событий в предыдущие интервалы времени. Типичным приме­ром таких потоков являются потоки с ограниченным последействием. Для них задается конечный набор функций распределения для соседних интер­валов к между поступлением К событий. Один из наиболее типичных по­токов с ограниченным последействием является стационарный поток с за­паздыванием - поток Пальма. Функции распределения вероятности для ин­тервалов между соседними событиями потока Пальма задаются через ус­ловную вероятность(t) отсутствия событий в интервале длиной t , если в начале этого интервала поступало событие следующим образом: P(к 0. Из п.З также можно сделать следующий вывод: D( -) = (-)2-(-)2 = Последовательность приращений fBM т.е. его производная в определен­ном смысле, образует фрактальный гауссовский шум (Fractal Gaussian Noise- fGN). Фрактальный гауссовский шум (чёрный шум) - это стационарный гаус­совский процесс с заданными параметрами (m,2) и автокорреляционной функцией ( ) Исходя из самых общих соображений, можно показать, что параметр Херста сохраняется при суммировании любого конечного числа независи­мых самоподобных процессов с фиксированным параметром самоподобия. Действительно, для суммы независимых случайных процессов функция корреляции равна сумме функций корреляции слагаемых. Если каждая из функций имела асимптотическое поведение в соответствии с выражением (1). Тем самым сохраняются все важнейшие характеристики самоподобности. Одной из таких характеристик является величина выбросов процес­са. Для самоподобных процессов характер выбросов сохраняется при рас­смотрении процесса в различных масштабах времени. Это означает, что если вы будете записывать нагрузку на каком либо элементе сети с дис­кретностью, например, 10 миллисекунд, то рассматривая график измене­ния нагрузки во времени на интервале 10 секунд и 10 минут и 10 часов вы не заметите существенных различий в поведении кривой. В этом смысле самоподобие графиков может быть охарактеризовано соотношением y(t) = aay() Величину а можно называть коэффициентом самоподобия непрерыв­ных процессов. Для нас далее важнейшим, из рассмотренных здесь свойств самоподоб­ных процессов является то, что такие процессы имеют выбросы, величина которых сохраняется как для агрегированных из них процессов (т.е. при усреднении по различным временным интервалам), так и при суммирова­нии независимых самоподобных процессов. Это означает, что распределение числа событий во времени для трафи­ка, представимого самоподобным процессом, носит характер сложной взаимосвязанной последовательности случайных пачек поступлений. Это делает моделирование такого потока событий весьма сложной задачей. Раздел 12 Сравнение характеристик качества обслуживания в сетях с коммутацией каналов и коммутацией пакетов. 2.1 Анализ времени доставки сообщений в сети с коммутацией каналов. В качестве важного практического примера применения методов теории телетрафика рассмотрим анализ передачи данных по сети с коммутацией каналов. Передача данных по сетям с коммутацией каналов осуществляется в три фазы - установление соединения, передача данных, разъединение соединения. Для реализации этих процессов применяется система сигнализации. На рис. 1.1 показаны упрощенно сигнальные сообщения, которыми обмениваются абоненты и коммутационные узлы в процессе передачи. Рис. 1.1 Сигнализация в сети с коммутацией каналов. Передача сигнализации может осуществляться как по специальному общему для всех коммутируемых каналов каналу сигнализации (ОКС), так и в полосе речевого сигнала, т.е. по тем же соединительным линиям, по которым передаются информационные сообщения. Рассмотрим сначала именно этот случай. Найдем время установления соединения, которое будет являться функцией нагрузки в сети, длины управляющих и информационных сообщений, интенсивности передачи сигнальных сообщений и данных (скорости передачи), а также числа каналов (соединительных линий) предоставленных для связи. Рассмотрим модель сети с коммутацией каналов в виде системы обслуживания, в которой вызовы ожидают освобождения каналов, а не блокируются. Отбросим на этом этапе проблему маршрутизации, предположив сеть полносвязной. На рис. 1.2 показана модель СМО, соответствующая сделанным предположениям. Два узла коммутации А и В связаны между собой N каналами (СЛ) с пропускной способностью СL ,бит/с. Пусть это также и скорость передачи по абонентскому шлейфу . С этой скоростью данные будут передаваться по каналу после установления соединения. Вызовы от абонентских устройств поступают на узел А и находятся в очереди пока не станет свободным хотя бы одна СЛ до узла В. На рис. 1.3 показаны все составляющие времени Тс –времени установления соединения от момента передачи сообщения запроса передачи до момента приема сообщения о начале передачи. Временем на соединение узла В и получателя пренебрегаем. Показанные отрезки времени требуется для передачи каждого из сигнальных сообщений, обработка в узлах А и В требует в каждом случае среднее время M<Тр>. Среднее время ожидания в очереди в узле А до освобождения одного из N каналов обозначено M. Рис. 1.2 Пара узлов в полносвязной сети с коммутацией каналов; модель системы обслуживания; сигнализация по разговорному каналу. Рис. 1.3 Составляющие времени установления соединения. Теперь примем для простоты, что каждое сигнальное сообщение имеет одну и ту же длину и требует времени передачи Тs . Время передачи сообщения о соединении примем равным ТI. При таком упрощении время соединения равно: . Для расчета среднего времени ожидания M воспользуемся моделью системы обслуживания типа M/M/N с бесконечной длиной буфера и N серверами. Предположение о пуассоновском распределении потока вызовов является, как правило, адекватным в задачах со многими абонентами, допущение о показательном распределении времени обслуживания существенно более грубое, однако описание времени обслуживания статистикой общего вида сильно усложнит задачу. Пусть интенсивность потока вызовов в узел А равна λ, а среднее значение времени обслуживания – 1/μ. Тогда можно использовать модель M/M/N со следующими характеристиками интенсивностей переходов Здесь n - состояние СМО, т.е. число установленных соединений, включая обслуживаемый вызов. Решение уравнений равновесия для данной системы было дано ранее. Введя параметр ρ=λ/(μN), стационарные вероятности состояний определяются как Теперь можно определить все необходимые характеристики качества обслуживания. Найдем сначала вероятность того, что сообщение будет задержано в системе, т.е. заявка не найдет свободного сервера. Очевидно, что эта вероятность равна . Мы ранее получали эту формулу в несколько ином виде ( явно выписывая вероятность p0 ) . Эта формула известна как С - формула Эрланга: . Обратите внимание, что вторым аргументом в С - формуле Эрланга используется полная нагрузка на пучок каналов, а не удельная нагрузка ρ<1. Будем для определенности обозначать далее полную нагрузку A=ρN. Эта нагрузка, конечно, также измеряется в Эрлангах. Рассмотрим пример. Пусть нагрузка на узел λ/μ =0.8 Эрл и в одном случае узел имеет один исходящий канал N=1, а в другом – пять (N=5). Вычислим С(1,0.8)=0.8 и С(5.0.8)=0.0018. Таким образом, применение пяти каналов вместо одного сокращает вероятность задержки более чем в 400 раз. Найдем теперь среднее число сообщений, ожидающих обслуживание. Оно равно разности между средним числом сообщений в системе и средним числом сообщений, находящихся на обслуживании . В качестве подтверждения правильности сделанного вывода можно найти значение среднего числа ожидающих сообщений для N=1. Оно получится в точности таким, как было выведено ранее для СМО типа M/M/1. . Теперь найдем среднее число сообщений, находящихся в системе M и число сообщений, находящихся в обслуживании M. Вычисление показывает, что Пользуясь формулой Литтла теперь можно найти задержку в узле M и среднее время ожидания для сообщения М: Для иллюстрации вернемся к рассмотренному ранее примеру. Пусть А=0.8 Эрл. При N=1 получим, что среднее время ожидания составит M=1/μ (0.8/0.2)=4(1/μ), а средняя задержка M=5(1/μ). При среднем времени занятия канала 1/μ=0.1c получим M=0.4c, M=0.5c . Если теперь увеличить число исходящих каналов до пяти, то при тех же предположениях будем иметь M=0.0004(1/μ) = 40 мс. Таким образом, применение многоканальной системы резко снижает время ожидания обслуживания. С другой стороны интересен вопрос о целесообразности разделения одного канала фиксированной пропускной способности на несколько менее производительных каналов. Пусть имеется канал с пропускной способностью 9600 бит/c и нужно решить, стоит ли разделить его на 5 отдельных каналов по 1920 бит/с. Предположим, что 1/μ=10 мс, т.е. сообщения имеют среднюю длину 192 бита. Средняя задержка при нагрузке А=0.8 при пяти каналах будет равна: M=10-2C(5,0.8)/(5-0.8)= 0,1 сек Если же использовать один канал со скоростью передачи 9600 бит/с, значение среднего времени ожидания будет равно: M=0,024сек Что существенно меньше. Таким образом, канал с большей пропускной способностью предпочтительнее, чем составляющие его каналы с меньшей пропускной способностью для передачи некоторого заданного объема пакетов данных. В случае передачи сообщений по сети с коммутацией каналов собственно время передачи данных ТМ представляет собой только одну из составляющих и для определения величины среднего времени обслуживания 1/μ необходимо учитывать все составляющие времени занятия канала. Обозначим далее среднее значение этого полного времени занятия канала Tн=1/μ=4Ts+TI+4M+TM Эта формула соответствует временной диаграмме занятия канала, изображенной на рис.1.4 в предположении, что все сигнальные сообщения имеют одну и ту же длительность Ts . Рис. 1.4 Составляющие времени занятия; пример рис. 2. С уже сделанной оговоркой о предположении экспоненциальности распределения этого времени (из формулы видно, что это сумма случайных величин), будем использовать полученное ранее соотношение для расчета среднего времени ожидания обслуживания Введем величину, определяющую параметр удельного полезного использования канала ρM=λTM/N . Этот параметр отличается от обычного коэффициента использования ρ=λTH/N, который не различает время на передачу информационного сообщения и время на передачу сигнализационных сообщений. Рассмотрим зависимость нормированного времени установления соединения в сети с коммутацией каналов TC /TM от параметра удельного полезного использования канала при различных длительностях передачи сигнальной информации. Примем для определенности время передачи сообщения о соединении TI=0.1TM. Обозначим Tsig– время для передачи всех других сигнальных сообщений (4Ts). Пусть узел имеет N=10 исходящих каналов. На рисунке 1.5. приведены два графика, позволяющие проанализировать некоторые характерные черты сети с коммутацией каналов. Графики построены для двух случаев – когда время для передачи сигнальных сообщений Tsig различаются в десять раз. Как видно из графиков, такое различие приводит к разным предельным значениям параметра полезного использования канала от 0.67 до 0.88 при меньших в десять раз длительностях сигнальных пакетов. Также видно, что увеличение нагрузки на узел сначала медленно, а затем резко увеличивает время установление соединения, причем сокращение сигнальных сообщений в любом случае уменьшает это время. Рисунок 1.5. Нормированное время распределения соединения; N = 10 каналов T1=0.1TM 2.2 Анализ времени доставки сообщений в сетях с коммутацией пакетов. Теперь перейдем к рассмотрению сети с коммутацией пакетов, а чтобы быть более точным, сети с передачей данных не ориентированной на соединение. В такой сети каждый пакет доставляется индивидуальным маршрутом и передача пакета считается завершенной только после получения подтверждения о его приеме. На рис.1.6 приведен фрагмент сети, состоящий из двух узлов и соединяющих их дуплексных каналов. Для сопоставимости результатов с сетью с коммутацией каналов будем считать полную интенсивность потока во входящем узле равной λ, пропускную способность дуплексного канала между узлами положим равной СТ=NСL в каждом направлении, где величина СL определяет максимальную скорость доступа к узлу от индивидуального абонента (пропускная способность абонентской линии). В этой сети принципиально отсутствуют расходы времени на установление соединения, однако в качестве накладных расходов выступает время на получение подтверждений о приеме пакета. Рассмотрим два способа передачи подтверждений. Первый состоит в передаче от узла В отдельных пакетов с информацией о подтверждении, а второй предполагает, что в информационные пакеты обратного направления встраиваются специальные поля битов подтверждения о приеме пакетов встречного направления. Рассмотрим сначала первый способ. Пусть каждый принятый пакет генерирует отдельное подтверждение фиксированной длины LI бит. Тем самым в каждом узле образуется поток пакетов переменной длины, состоящих из некоторого фиксированного поля длины LI и поля случайной длины со средним значением mc . Такие пакеты поступают в очередь на входном узле и обслуживаются в порядке поступления. Рис. 1.6 Пара узлов; сеть с коммутацией пакетов. Очевидно, что здесь мы должны использовать модель СМО с произвольным распределением времени обслуживания в силу специфики структуры пакетов. Поставим задачу найти среднее время отклика TD от узла до узла, используя модель M/G/1. На рис. 1.7 показано как можно рассматривать входную очередь и какой вид функции распределения времени обслуживания следует принять. Рис. 1.7 Передача отдельных подтверждающих пакетов. Найдем среднее значение времени обслуживания на один пакет. Поскольку весь выходной поток узла считывается в канал со скоростью СТ, можно записать, что время на передачу будет равно: . Первая составляющая представляет собой время на передачу «заголовков», а вторая составляющая – время на передачу собственно данных. Средняя длина подтверждений также равна th . Таким образом, среднее «эквивалентное» время обслуживания в системе M/G/1 следует принять равным . Поскольку поступления двух типов входящих сообщений равновероятны, и обслуживание происходит в порядке поступления, можно считать, что коэффициент использования для данной системы будет определяться как . Здесь был введен параметр ρM=λtm эффективный коэффициент использования передаваемых через канал битов. Его смысл полностью совпадает с введенным выше с тем же обозначением коэффициента для сети с коммутацией каналов. Действительно из соотношений Таким образом, мы ввели для сети с коммутацией пакетов параметр сравнения, совпадающий с параметром сети, ориентированной на соединение. Вспомним теперь, что для СМО типа M/G/1 среднее время ожидания зависит от второго момента распределения времени обслуживания. Найдем . Используя формулу Полячека-Хинчина, получаем выражение для среднего значения времени ожидания пакета в системе: В конечном счете общее время отклика от узла до узла складывается из только что полученного времени задержки в очереди в узле А и задержки в очереди подтверждений в узле В, а также среднего времени передачи пакета и времени передачи подтверждения. Искомое время равно . Для сравнения полученной величины со временем соединения в сети с коммутацией каналов, нормируем эту величину на время передачи данных по абонентской линии, как это делалось ранее. Вводя обозначение отношение длины управляющего пакета к длине информационного пакета k=LI /mc=th /tm, получим . На рис. 1.8 приведены графики зависимости этой величины от ρM при тех же параметрах сети, что и сети с коммутацией каналов k=0.1, N=10. Рис. 1.8 Нормированное время ответа; случай коммутации пакетов. Рассмотрение и сравнение зависимостей показывает, что если сигнальные сообщения имеют ту же длину, что и сообщения об установлении соединений, максимальное использование канала в сети с коммутацией канала составляло величину в 0.67. При сигнальных сообщения в десять раз короче, эта величина возрастала до 0.88. В сети с коммутацией пакетов полезное использование не превышает 0.83. На рисунке приведены также зависимости для второго способа передачи подтверждающих прием пакета сообщений в теле обратных пакетов (вложенные подтверждения). Можно показать, что в этом случае нормированное время отклика может рассчитываться по формуле Как видно из графика вложенные подтверждения несколько эффективнее при больших нагрузках и сильно ухудшают характеристики сети при малых нагрузках. На этом же рисунке приведены результаты расчетов, сделанные в приближении экспоненциального распределения времени обслуживания. Как видно учет второго момента распределения незначительно влияет на результаты даже при больших нагрузках, если только правильно выбрать средние значения. В заключение приведем сравнение двух видов коммутации в зависимости от длины передаваемых данных. Будем определять величину задержки в системе как функцию длины информационной части пакета mc. Для сети с коммутацией каналов величина задержки определяется временем соединения TC =M+TI+3TS, где среднее время ожидания в очереди и время на передачу сигнализационных сообщений необходимо выразить через длины пакетов, пропускные способности и сопоставимую величину коэффициента эффективного использования ρM. Для сети с коммутацией пакетов и потоком подтверждений будем находить время ответа TD, выраженное через те же самые величины. На рис. 1.9 приведены сравнительные графики, рассчитанные по приведенным выше формулам для случая сети с 16 битовыми сигнальными сообщениями, сообщениями запроса и подтверждения длиной 160 бит и скоростями на абонентской линии и межузловом канале в 2.4 Кбит/c и 120 Кбит/с соответственно. На рис. 1.10 приведены результаты расчетов для сети с медленными каналами в 110 бит/с на абонентской линии и 1100 бит/c на межузловом канале. Длина сигнального сообщения о соединении и подтверждения имеет длину в 100 бит, а другие сигнальные сообщения в 50 бит. В целом рассмотрение полученных результатов приводит к следующим выводам. Коммутация пакетов может дать меньшее время реакции в диапазонах малых длин сообщений (пакетов), тогда как коммутация каналов имеет преимущества при больших длинах сообщений. Каналы с большей пропускной способностью при коммутации пакетов тем эффективнее, чем меньше коэффициент полезного использования ρM. При увеличении длины сигнального сообщения характеристики сети с коммутацией каналов сильно ухудшаются (в том случае, если для передачи сигнальной информации используются те же каналы). Рис. 1.9 Сравнение коммутации пакетов и коммутации каналов. Пример 1. Рис. 1.10 Сравнение коммутации пакетов и коммутации каналов. Пример 2. Раздел 13 3 Анализ характеристик каналов с интеграцией речи и данных Для решения этой задачи нам потребуется новый математический аппарат, краткое изложение которого дается в следующем разделе. 3.1 Метод производящих функций Этот метод является применением известного вам по теории обработки сигналов z-преобразования к описанию распределения вероятностей. Пусть имеется функция дискретного аргумента n , представляющая собой невозрастающую последовательность. Z-преобразованием последовательности называют функцию комплексной переменной . Если функция pn имеет смысл распределения вероятностей полной системы событий, то соответствующее z-преобразование называют производящей функцией. Применение этого преобразования позволяет упростить решение уравнений равновесия для процессов гибели-размножения, сводя решение систем разностных уравнений к системам алгебраических. Будем опираться на известные свойства z – преобразований, приведенные, например, в книге Л. Клейнрок «Теория массового обслуживания». Для производящих функций нетрудно получить как частный случай следующие соотношения Теперь вернемся к системе массового обслуживания M/M/1, уравнения которой имеют вид Решим эти уравнения методом производящих функций. Умножим правую и левую часть на zn и просуммируем от нуля до бесконечности. В результате получим . Группируя соответствующие члены, получаем Из соотношения Полученное выражение сразу позволяет найти среднюю длину очереди, исходя из свойств производящей функции . Этот результат, конечно, совпадает с полученным ранее прямым методом. Найденная производящая функция позволяет сразу определить и все значения ве­роятностей. С этой целью можно воспользоваться таблицей z-преобразований или разложить производящую функцию в степенной ряд и выписать полученные коэф­фициенты. Можно также воспользоваться вычислением обратного z-преобразова­ния с помощью теоремы о вычетах. . Рассмотрим теперь систему M/M/2, которая встретится нам в дальнейшем еще раз. Решение уравнения равновесия для неё было найдено в виде Найдем производящую функцию Выражения для полученных здесь производящих функций будут использованы далее при рассмотрении сетей с интеграцией средств коммутации пакетов и каналов. 3.2 Модели интеграции речи и данных. Рассмотрим объединение двух видов нагрузки – обслуживание с коммутацией каналов, кратко – речь и нагрузка, требующая обслуживания с коммутацией пакетов – данные. Назовем первую из этих видов нагрузка 1-го класса. Будем считать, что интенсивность поступлений ВЫЗОВОВ (требований на соединение) λ1 а среднее время занятия 1/μ1. Этот тип нагрузки требует одного временного канала и при отсутствии свободных каналов – блокируется. Второй из видов нагрузки назовем Нагрузка 2-го класса. Интенсивность поступлений ПАКЕТОВ положим равной λ2, а средняя длина пакета определяет время обслуживания 1/μ2. Эта группа заявок ставится в очередь при отсутствии свободных каналов. В этом и состоит основное отличие двух классов нагрузки с точки зрения теории телетрафика. Для обслуживания нагрузки в зависимости от класса может быть выделено фиксированное или переменное число каналов. В зависимости от способа предоставления каналов для заявок разного класса будет получаться различное качество обслуживания нагрузки. Наша задача проанализировать различные методы обслуживания. 3.2.1 Интеграция на основе обслуживания в порядке поступления. При этой стратегии обслуживания контроллер, показанный на рис. 1.1, назначает канал (временной слот) любому пользователю при его появлении независимо от класса нагрузки. При отсутствии свободного канала запросы на соединение блокируются, а пакеты помещаются в буфер. Найдем точное решение задачи определения характеристик качества обслуживания интегральной сети с такой стратегией интеграции. Приемлемая сложность задачи получается для простейшего случая разделения ресурса в виде одного N=1 канала. Однако, несмотря на простоту случая, он позволяет проследить все важнейшие особенности рассматриваемого способа объединения. Для более общего случая с большим числом каналов N будут приведены приближенные формулы. Рис. 1.1 Модель с непрерывным временем; интеграция нагрузки с коммутацией каналов и коммутацией пакетов. Построим диаграмму переходов состояний системы массового обслуживания, соответствующей рассматриваемой задаче. СМО имеет двумерную структуру пространства состояний (См. рис.1.2). Обозначим стационарные вероятности нахождения системы в каждом из состояний pij . Верхний ярус состояний i=1 соответствует случаю занятости канала заявкой первого класса, а нижний ярус i=0 описывает состояния без наличия заявки первого класса. Значение j определяет число заявок второго класса, находящихся в системе. Переходы между состояниями в точности соответствуют возможным процессам в системе. Так при занятости канала заявкой первого класса, его освобождение происходит с интенсивностью μ1 в состояние, определяемое числом заявок второго класса, находящихся на обслуживании. Поступление новой заявки второго класса производит переход в состояние с j+1 с интенсивностью λ2, а ее обслуживание производит переход в состояние с j-1 с интенсивностью μ2, но только в случае отсутствия заявки первого класса (i=0). Рис. 1.2 Диаграмма состояний интегральной схемы; обслуживание в порядке поступления; N=1 канал. Выпишем уравнения баланса для всех состояний. Обозначая как обычно ρ1=λ1/μ1, ρ2=λ2/μ2 и используя уравнения (1) и (2) можно получить выражения для вероятностей состояний где - коэффициент, определяющий соотношение между длительностью заявок первого и второго класса. Для определения вероятностей при i=0 воспользуемся методом производящих функций. Определим производящую функцию . Умножим правую и левую часть уравнения (2) на zj и, суммируя по всем j, начиная с единицы, можно получить следующее алгебраическое уравнение для функции комплексной переменной – производящей функции При выводе этих уравнений использовались следующие вспомогательные соотношения В уравнении для G0(z) в правой и левой части может быть выделен сомножитель (z-1). После сокращения на него можно записать выражение для производящей функции . Единственным неизвестным остается вероятность в нулевой точке. Воспользуемся условием нормировки и свойством производящей функции Теперь мы можем найти характеристики качества обслуживания. Вероятность блокировки заявок первого класса равна вероятности 1-p00. . В качестве подтверждения правдоподобности полученного соотношения найдем значение вероятности блокировки при отсутствии заявок второго класса, т.е. при Это в точности значение вероятности блокировки системы с одним сервером, получаемое при расчете по В - формуле Эрланга. Теперь найдем среднее значение задержки нагрузки второго класса. Сначала найдем среднее число пакетов в системе, а затем воспользуемся формулой Литтла. Заметим, что первое слагаемое описывает задержку в системе M/M/1, а второе слагаемое определяет увеличение числа пакетов в очереди за счет состязаний за доступ к каналу с заявками первого класса. Условие равновесия для нагрузки второго класса не зависит от нагрузки первого класса и состоит в выполнении неравенства ρ2<1. Воспользовавшись формулой Литтла, найдем нормированную задержку заявок второго класса . Обычно при интеграции заявки первого класса - телефонные разговоры имеют существенно большую длительность, чем длительности пакетов. При этом α>>1. Как видно из полученной формулы, задержка пакетов сильно возрастает по сравнению с чисто пакетной сетью. Интересно как изменится ситуация при достаточно большом числе каналов. Случай с N>1 был проанализирован и позволил предложить приближенную формулу для расчета вероятности блокировки для нагрузки первого класса в виде Это известная формула Эрланга. Соотношение точно при α=1 и может быть применено для других значений α в силу слабой зависимости вероятности блокировки от ее величины. Рассмотрим пример. Пусть 1/μ1=100c ,1/μ2=10 мс. Тогда α=10000. Пусть нагрузки таковы, что ρ1=0.1, ρ2=0.4. Тогда PB=0.45 т.е. весьма значительна. В то же время задержка для пакетов μ2M=1.7+990=991.7 что существенно превышает задержку без учета влияния «разговорной» нагрузки. Фактическое время задержки составит 9.9 с вместо 1.7 мс для соответствующей системы M/M/1 когда пакеты поступали бы в отдельный канал. Как показывает анализ, стратегия интеграции нагрузки в порядке поступления запросов не обеспечивает приемлемого регулирования характеристик качества обслуживания. Другим способом интеграции является стратегия абсолютного приоритета заявок первого класса. 3.2.2 Интеграция с абсолютным приоритетом. В этом случае заявки первого класса, безусловно, снимают с обслуживания заявки второго класса при поступлении. Очевидно, что при этом вероятность блокировки для заявок первого класса никак не зависит от нагрузки второго класса и определяется только числом каналов и нагрузкой первого класса. Вероятность блокировки определяется В - формулой Эрланга . Определить среднее значение времени задержки для нагрузки второго класса удается аналитически только для случая N=1. Вероятность блокировки для этого случая равна . Нетрудно видеть, что это значение меньше, чем для вероятности блокировки в сети с интеграцией обслуживания в порядке поступления, в силу того, что отсутствует влияние заявок второго класса. Найдем теперь, какова будет задержка обслуживания для таких заявок. Построим снова диаграмму переходов состояний для модели системы с такой дисциплиной обслуживания классов заявок. Пространство состояний системы также как и в предыдущем случае будет двумерным, а структура переходов еще более сложной. На рис.1.3 приведена диаграмма состояний для интегральной сети с абсолютным приоритетом заявок первого класса. Основным отличием диаграммы переходов является наличие переходов из состояний нижнего яруса с i=0 для всех j в состояния верхнего яруса (i=1) с тем же j с интенсивностью 1. Эти переходы отражают процесс снятия заявки второго класса с обслуживания немедленно с поступлением заявки первого класса с вероятностью равной 1t в течение промежутка времени (t, t+t). Рис. 1.3 Диаграмма состояний интегральной системы; абсолютный приоритет вызовам 1 – го класса; N=1 канал. Составим уравнения равновесия для построенной модели системы. Они оказываются более сложными, чем для предыдущего случая. Выпишем сначала уравнения для нулевого состояния. Их сразу можно разрешить относительно вероятностей состояний, соседних начальному, а затем выписать уравнения для остального множества состояний Для решения этой системы уравнений воспользуемся методом производящих функций. Введем Умножим (9) и (10) на zj , и, суммируя по всем значениям j=1,2,3…,найдем после некоторых выкладок Решая систему алгебраических уравнений и подставляя выражения (7) и (8) получим выражения для производящих функций. Далее, используя условия нормировки, выразим вероятность нулевого состояния Последнее соотношение позволяет установить нетривиальное условие стабильности в системе (существования стационарного распределения вероятностей) для максимального значения коэффициента нагрузки со стороны заявок второго класса - на коммутацию пакетов Смысл полученного неравенства состоит в необходимости обеспечения средней поступающей нагрузки второго класса меньшей, чем остаток пропускной способности канала после обслуживания нагрузки первого класса. В противном случае очередь из заявок второго класса просто переполнится и они никогда не будут обслужены (не получат доступ к каналу). При выполнении же этого условия среднее число заявок в очереди будет конечным и может быть определено непосредственно через производящие функции по формуле . Воспользуемся формулой Литтла и вычислим в явном виде значение нормированного среднего времени задержки в системе для заявок второго класса . В качестве подтверждения правдоподобности полученного результата положим равной нулю интенсивность нагрузки первого класса. Получающееся при этом выражение будет в точности соответствовать известному выражению для задержки заявок в системе M/M/1. Рассмотрим в качестве примера исходные данные для предыдущего раздела. При 1/1=100c,1/2=10мс, и =10000, 1=0.1, 2=0.4 вероятность блокировки для нагрузки первого рода будет равна 0.09, что в 5 раз меньше, чем для интеграции в порядке поступления заявок. Однако при этом нормированная средняя задержка для пакетов возрастет с 2М=992 до 1600, т.е. более чем на 60%. Можно показать, что в общем случае при достаточно больших  выигрыш в вероятности блокировки при переходе на интеграцию с абсолютным приоритетом по сравнению с обслуживанием в порядке поступления будет определяться отношением . В то же самое время задержка пакетов возрастет в отношении . Таким образом стратегия интеграции с абсолютным приоритетом , гарантируя заданное качество обслуживания для соединений, приемлема только для очень низких нагрузок со стороны передачи пакетов. Сочетания гарантированной вероятности блокировки для соединений и минимально возможной задержки при заданной пропускной способности канала удается достигнуть, применяя адаптивное распределение ресурса - стратегию подвижной границы. 3.2.3 Интеграция на основе стратегии подвижной границы. При этом методе интеграции N канальных интервалов делятся на две части. Одна часть, содержащая N1 канальных интервалов, предназначается для обслуживания нагрузки первого класса (запросов на соединение). Другая часть, содержащая N2=N-N1 канальных интервалов, резервируется для пакетов – обслуживания нагрузки второго класса. Пакеты могут занимать также любой из N1 канальных интервалов первого класса, если он не используется в данный момент времени. Однако при поступлении заявки первого класса она имеет абсолютный приоритет перед нагрузкой второго класса и сбрасывает при необходимости пакет, занимающий один из N1 канальных интервалов. В этом и состоит смысл подвижной границы между группами каналов, отведенных для двух различных классов нагрузки. На рис. 1.4 приведена иллюстрация этого метода. Рис. 1.4 Стратегия подвижной границы. Очевидно, что вероятность блокировки для нагрузки первого класса при такой стратегии предоставления ресурса определяется по В - формуле Эрланга для N1 серверов. Задержка для пакетов при этом будет не хуже, чем рассчитанная для системы с N2 серверами, а лучше, поскольку вся оставшаяся от обслуживания нагрузки первого класса пропускная способность системы будет также использоваться для обслуживания пакетов. В системе такого типа также может возникнуть перегрузка для нагрузки второго класса. Максимально допустимая величина этой нагрузки не должна превышать . Здесь вероятность блокировки для нагрузки первого класса определяется по В - формуле Эрланга. Записанное соотношение может быть интерпретировано как интуитивно очевидное, поскольку выражает собой условие не превышать единицу для среднего на один сервер коэффициента использования по отношению к нагрузке второго класса . В знаменателе при этом находится выражение описывающее среднее число каналов, доступных для очереди пакетов. С другой стороны, оно может быть переписано в виде условия ограничения величиной N полной средней нагрузки на систему . Общий анализ системы с подвижной границей оказывается слишком сложным с алгебраической точки зрения. Поэтому при аналитическом исследовании применяются приближенные методы. Раздельно изучаются два возможных режима – не перегруженный (ρ20, преобразуем это уравнение в алгебраическое относительно производящих функций. Повторяя ту же процедуру с уравнением (12) и исключая неизвестные составляющие с помощью (13), (14). Получим в итоге : Полученные уравнения позволяют сразу выписать несколько важных соотношений, приводящих к определению вероятности блокировки нагрузки первого класса: Это соотношение в точности соответствует В-формуле Эрланга для однолинейной системы. Теперь перейдем к определению среднего времени задержки пакетов. Складывая уравнения для производящих функций, сокращая общий множитель правой и левой частях (1-z) и обозначив отношение 2/2=2, найдем следующее соотношение Введем несколько обозначений Тогда можно найти в явном виде выражения для вероятностей Выпишем теперь выражения для производящих функций Найдем соотношение для среднего числа пакетов в системе, исходя из формулы для производящих функций В качестве подтверждающих правдоподобность полученного выражения соотношений найдем предел правой части при стремлении к нулю нагрузки первого класса и предел при стремлении этой нагрузки к бесконечности. В первом случае результат в точности соответствует модели M/M/2, а во втором - модели M/M/1 , что и соответствует нашим представлениям. Воспользовавшись формулой Литтла, выпишем выражение для нормированной задержки в системе . Это выражение еще не является окончательным, поскольку содержит три вероятности, связанные только двумя уравнениями. Как уже было отмечено, воспользуемся некоторыми свойствами корней знаменателя выражения для производящей функции G0(z). Обратимся к выписанному выше выражению для этой функции. Пусть z0 - корень многочлена D0. Из определения производящей функции необходимо выполнение требования При этом значении z выражение для числителя также должно обратиться в ноль. Полученное при этом выражение N0(z0)=0 и определяет третье необходимое уравнение для нахождения всех вероятностей, входящих в выражение для задержки. Решение алгебраического уравнения третьей степени в общем случае не дается в виде конечной формулы. Мы используем приближенное решение этого уравнения для нахождения двух различных формул для определения задержки пакетов в системе с подвижной границей На рис.1.6 приведены графики функции нормированной задержки при различных значениях нагрузки первого класса. Для сравнения приведен график задержки для системы с фиксированным разделением каналов для двух классов нагрузки (по одному каналу на каждый). Как видно из сравнения стратегия подвижной нагрузки дает существенный выигрыш в характеристиках качества обслуживания по сравнению с другими способами интеграции каналов. Анализ показывает, что такое преимущество только усиливается при увеличении числа канальных ресурсов. Рис.1.6 Сравнение систем с подвижной и фиксированной границей; N=2; N1=N2=1. Раздел 14 СТАТИСТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ЗАДАЧ ТЕОРИИ ТЕЛЕТРАФИКА 1 Общие сведения. Большое число задач ТТ в настоящее время не имеют точных аналитических решений. Это объясняется в первую очередь тем, что в большом числе моделей обслуживания требуется учитывать микросостояния систем. К таким системам в первую очередь относятся неполнодоступные КС. Число состояний в таких схемах С = 2v. В реальных системах V=50,100 и соответственно С ≥ 260 ÷ 1010. Решение системы уравнений такого порядка невозможно на самых быстродействующих ЭВМ. Звеньевые КС обладают ещё большим числом состояний и всё сказанное справедливо и для этого класса схем. В этих условиях наиболее эффективным в некоторых случаях единственным средством решения является метод статистического моделирования. Основным достоинством метода является возможность получения интересующих статистических характеристик с любой наперёд заданной точностью. При этом чем выше требуемая точность, тем в большем объеме необходимо провести статистическое моделирование и, следовательно, требуется больше машинного времени. Обычно для экономного расходования машинного времени при сохранении требуемой точности результатов непосредственное статистическое моделирование истинного процесса обслуживания коммутационной системой входящего потока вызовов заменяется моделированием искусственных вероятностных моделей. В качестве такой модели широко используется моделирование марковской цепью. 2 Моделирование случайных величин Моделирование систем массового обслуживания связано с моделированием случайных величин, имеющих различные распределения: равномерное, показательное, нормальное и др. Для получения таких случайных величин (СВ) используются СВ X, равномерно распределённая на отрезке [0,1], из которой с помощью различных преобразований получают СВ, подчиняющуюся требуемому распределению. Случайная величина X называется равномерно распределенной на отрезке [0,1], если её плотность f (χ) на этом отрезке постоянная и равна единице: Плотность распределения СВ иногда называют дифференциальной функцией распределения СВ. Интегральная функция распределения (далее просто функция распределения) этой СВ имеет следующий вид: F() Плотность f(χ) и функция распределения F(χ) случайной величины X, равномерно распределённой на отрезке [0,1], показаны на рис. 1 1 О Рис.1- Плотность и функция распределения СВ, равномерно распределенной на единичном отрезке. СВ X, равномерно распределённую на отрезке [0,l], можно получить из дискретной СВ, равновероятно принимающей значения 0 и 1. Рассмотрим двоичную дробь: Х=0, а-1,а-2, ..., где: а -1, а -2, ..., есть последовательность независимых СВ, каждая из которых с вероятностью 0,5 принимает значение 0 и с такой же вероятностью единицу, т.е. предоставляет дискретную СВ, равновероятно распределенную на отрезке [0,1]. Для того чтобы промежутки между соседними значениями равномерно распределенной СВ X стремились к нулю, необходимо иметь бесконечную последовательность независимых СВ (ai, i = -1, -2, ... ) равновероятно принимающих значения 0 и 1 . На практике непрерывно распределенная СВ моделируется приближенно. При этом может быть достигнута сколь угодно высокая точность за счет выбора числа К двоичных разрядов в ЭВМ, определяющих двоичную дробь 0, а-1, а-2, ..., а-к Таким образом, вместо непрерывной СВ, равномерно распределенной на отрезке [0,1], моделируется дискретная СВ, равновероятно принимающая значения 0,,,….. С промежутками между соседними значениями 1/2 К. Случайные величины X, равномерно распределённой на отрезке [0,1] обычно получают программным путем на ЭВМ (псевдослучайные числа). Псевдослучайные последовательности вырабатываются рекуррентным способом по алгоритмам, в которых каждое последующее число получается из предыдущих в результате применения некоторых арифметических и логических операций. Эти последовательности называются псевдослучайными , т.к. они являются периодическими. Однако период может быть выбран столь большим, что практически этот недостаток можно не учитывать. Возможность моделирования СВ X, равномерно распределённой на отрезке [0,l], позволяет моделировать и непрерывную СВ ξ, распределенную по любому закону F(ξ)=P(ξ<ζ) Функция распределения СВ ξ, монотонно возрастает от 0 до 1. можно показать, что значение СВ ξ, распределенную по любому закону в интервале [а, b) с плотностью f(ξ), определяется из уравнения. d ξ (1) Для каждой реализации величины X решается уравнение(1) относительно ξ 1, т.е. определяется реализация величины ξ. Эта процедура показана на рис 2. Рис 2. - К определению СВ ξ. Для каждой конкретной реализации равномерно распределенной СВ X прямая F(ξ) = χ пересекает кривую функции распределения только в одной точке, абсцисса которой ξ 1, и определяет значение ξ в этой реализации. Рассмотрим принцип моделирования СВ £, равномерно распределенной в интервале [а, b), и СВ, распределенной по конкретному закону. Равномерно распределенная в интервале [а, b) СВ имеет в этом интервале постоянную плотность, равную Согласно (1) ==, откуда (2) Используя в процессе моделирования каждую реализацию СВ X и преобразование (2), получаем последовательность СВ ξ равномерно распределенных в интервале [а, b). СВ ξраспределенная в интервале [0, ∞) по показательному закону с параметром λ имеет плотность распределения Согласно (1) 1- Откуда Величина (1 - χ) точно так же, как и χ, является равномерно распределенной на отрезке [0, 1]. Поэтому (3) Умение моделировать непрерывные СВ ξ дает возможность моделировать любой поток вызовов, заданный последовательностью функций распределения промежутков между вызовами. В частности, при моделировании простейшего потока вызовов, последовательность случайных величин Zi (промежутки между вызовами) можно получить используя преобразование (3). 3 Основы моделирования коммутационных систем. При моделировании процесса обслуживания входящего потока вызовов КС нет необходимости полностью имитировать реальный процесс. Достаточно ограничиться моделированием некоторого искусственного процесса при условии, что получаемые при этом характеристики в статистическом смысле соответствовали реальному процессу. Ранее было показано, что обслуживание потока с простым последованием любой КС является марковским процессом. Поэтому вместо моделирования реального процесса можно моделировать марковский процесс. При этом требуется учитывать случайные отрезки времени пребывания системы в различных состояниях. Дальнейшее упрощение моделирования достигается заменой моделирования марковского процесса моделированием цепи Маркова. При этом переход модели из одного состояния в другое происходит в дискретные моменты времени, в каждый из которых реализация СВ имитирует либо поступление нового вызова, либо окончание обслуживания. При моделировании цепи Маркова каждое изменение происходит за один цикл работы ЭВМ, в течении которого реализуется случайная величина и происходит переход цепи в другое состояние. Отметим, что при этом не требуется в явном виде учитывать время пребывания системы в различных состояниях. На рис. 3 показана КС произвольной структуры, которая имеет 3 группы входов и h групп выходов На каждую группу входов поступает поток с простым последованием с параметром A.(i, j, k), где: i - номер группы входов; j - номер выбираемого направления к - номер состояния КС в момент поступления вызова Обозначим параметр потока освобождений между i - ой группой входов и j - м направлением выходов при котором состояние системы - v(I, j, k). Тогда суммарный параметр потока вызовов ак и суммарный параметр потока освобождений bк в промежутке времени, в которые КС находится в состоянии К, составит: = = В каждом состоянии цепи Маркова моделируется СВ ξ, равномерно распределенная на отрезке [0, ак + bк). Если в рассматриваемом цикле работы ЭВМ СВ ξ, реализуется на участке равномерно распределенного отрезка [0, ак + bк), соответствующем ξ < то считается, что эта СВ определяет поступление вызова на n - ю группу входов и соединение требуется установить в требуемом направлении (m). Если ξ реализуется на участке + ξ < то считается, что соединительный путь между n - ой группой выходов m - й группой входов освобождается. 4 Статистические характеристики моделирования. К таким характеристикам относится: • в системах с потерями - вероятность потерь, вероятности различных состояний системы; • в системах с ожиданием - функция распределения времени ожидания начала обслуживания, средняя длинна очереди и др. Обычно моделирование осуществляется в течение n серий, в каждой из которых производится равное число m испытаний. Число испытаний выбирается таким, чтобы статистические характеристики исследуемых величин были представительными. Так, например, при определении вероятности потерь с ожидаемой величиной ≈ 5‰величина m должна быть не менее 10 ч/с тем чтобы число потерянных выходов было порядка нескольких десятков или сотен. По результатам моделирования определяются средние значения, дисперсия, СКО и доверительные интервалы исследуемых статических характеристик. 5 Достоверность результатов моделирования. По результатам моделирования, выполненного за n серий по m испытаний (обычно вызовов) в каждой серии вычисляется величина xi для каждой серии где: ri - число проявлений исследуемого события (число потерянных вызовов), xi - экспериментальное значение статистической характеристики (потерь) в этой серии. При этом, с целью исключения нестационарных процессов, первую (ее обычно называют нулевой) серию во внимание не принимают. После завершения процесса моделирования определяются статистические оценки среднего значения х , дисперсии σ2 и СКО σ по формулам Точность результатов моделирования обычно производится по критерию Стьюдента: где: P(Z*n-1) - доверительная вероятность, т.е. вероятность того, что случайный доверительный интервал содержит теоретическую характеристику X; - значение функции Стьюдента при (n-1) - й степени свободы; Zn_1 - коэффициент доверия, соответствующей заданной доверительной вероятности. Значение величины определяется по таблицам [17] при заданном числе степени свободы (n -1) и коэффициенте доверия Последние выражение можно использовать для определения величины ε Если число степеней достаточно велико (n ≥30), то величину () можно определить по приближенной формуле ()=0.5+(Z) где: (Z) - интегральная функция для нормального законы распределения (Z)=du Значение функции Ф(Z) определяется по таблицам [17]. Расчетами установлено, что при n ≥ (30 ÷50) достигается достаточно устойчивое значение статических оценок исследуемых характеристик. Раздел 15 4 Анализ систем массового обслуживания с приоритетами 4.1 Дисциплины обслуживания. Модель с приоритетами. Дисциплина обслуживания – это способ определения того, какое требование в очереди должно обслуживаться следующим. Решение может основываться на одной из приведенных ниже характеристик или на их совокупности: 1) мера, определяемая относительным временем поступления рассматриваемого требования в очередь; 2) мера требуемого или полученного до сих пор времени обслуживания; 3) функция, определяющая принадлежность требования к той или иной группе. Примерами дисциплин обслуживания являются постоянно используемая модель «первый пришел - первый обслужен» (FCFS-first came-first served) , называемая в русскоязычной литературе «дисциплина обслуживания в порядке поступления»-ОПП. Приведем здесь список некоторых типичных дисциплин обслуживания. ОПП-обслуживание в порядке поступления (FCFS); ООП – обслуживание в обратном порядке, т.е. последнее поступившее требование обслуживается первым (LCFS); ПК – первоочередное обслуживание требований с кратчайшей длительностью обслуживания (SPT/SJE); ПКД – первоочередное обслуживание требований с кратчайшей длительностью дообслуживания (SRPT); ПКС – первоочередное обслуживание требований с кратчайшей средней длительностью обслуживания (SEPT); ПКСД – первоочередное обслуживание требований с кратчайшей средней длительностью дообслуживания (SERPT); ПКОВ – первоочередное обслуживание требований с кратчайшим обязательным временем (SIPT). Если сравнивать эти дисциплины по среднему времени ожидания попарно, и обозначать тот факт, что среднее время ожидания для дисциплины D1 ,больше или равно среднему времени ожидания для дисциплины D2 следующим образом: D1D2, то можно построить следующую диаграмму ПО  ОПП  ПК  ПКД     ОП   Итак, основным предметом анализа различных дисциплин обслуживания будем считать расчет среднего времени ожидания требования в очереди или среднего времени пребывания в системе. Предположим, что требования принадлежат одному из P различных приоритетных классов, обозначаемых индексом p=1,2,3…P. Каждому требованию, находящемуся в системе в момент времени t ставится в соответствие значение некоторой приоритетной функции qp(t). Чем больше значение этой функции, тем выше приоритет требования. Всякий раз, когда принимается решение для выбора требования на обслуживание, выбор делается в пользу требования с наибольшим значением приоритетной функции. В простейшем случае в качестве приоритетной функции выбирается просто значение p. В этом случае приоритет требования тем больше, чем больший номер класса принадлежности оно имеет. Рассмотрим достаточно общую модель, основанную на системе M/G/1. Предположим, что требования из приоритетного класса p образуют пуассоновский поток с интенсивностью p требований в секунду. Время обслуживания каждого требования из этого класса выбирается независимо в соответствие с распределением с плотностью вероятности bp(x) со средним значением . Введем следующие определения Здесь  интерпретируется как доля времени, в течение которого сервер занят (<1), а каждый из парциальных коэффициентов p – как доля времени, в течение которого сервер занят обслуживанием заявок из приоритетного класса с номером p. Если требование в процессе обслуживания может быть удалено из сервера и возвращено в очередь при поступлении требования с более высоким приоритетом, то говорят, что система работает с абсолютным приоритетом, если обслуживание любого требования, находящегося в сервере не может быть прервано, то говорят что СМО работает с относительным приоритетом. 4.2 Основная модель расчета среднего времени ожидания Будем использовать далее следующие обозначения для среднего значения времени ожидания в очереди требований из приоритетного класса p - Wp, и среднего времени пребывания в системе для требований этого класса - Tp: . Основное внимание будем уделять системам с относительным приоритетом. Рассмотрим процесс с момента поступления некоторого требования из приоритетного класса p. Будем далее называть это требование меченым. Первая составляющая времени ожидания для меченого требования связана с требованием, которое оно застает в сервере. Эта составляющая равна остаточному времени обслуживания другого требования. Обозначим теперь и будем использовать это обозначение и далее, среднюю задержку меченого требования, связанную с наличием другого требования на обслуживании W0. Зная распределение времени между соседними поступлениями входных требований для каждого приоритетного класса, можно всегда вычислить эту величину. В нашем предположении пуассоновского закона для потока заявок каждого класса можно записать . Вторая составляющая времени ожидания для меченого требования определяется тем, что перед меченым требованием обслуживаются другие требования, которые меченое требование застало в очереди. Обозначим далее число требований из класса i, которое застало в очереди меченое требование (из класса p) и которые обслуживаются перед ним Nip. Среднее значение этого числа будет определять величину среднего значения этой составляющей задержки . Третья составляющая задержки связана с требованиями, поступившими после того как пришло меченое требование, однако получившими обслуживание раньше его. Число таких требований обозначим Mip. Среднее значение этой составляющей задержки находится аналогично и составляет . Складывая все три составляющие, получаем, что среднее время ожидания в очереди для меченого требования определяется формулой . Очевидно, что независимо от дисциплины обслуживания число требований, Nip и Mip в системе не может быть произвольным, поэтому существует некоторый набор соотношений, связывающий между собой задержки для каждого из приоритетного класса. Важность этих соотношений для СМО позволяет называть их ЗАКОНАМИ СОХРАНЕНИЯ. Основой законов сохранения для задержек является тот факт, что незаконченная работа в любой СМО в течение любого интервала времени занятости не зависит от порядка обслуживания, если система является консервативной (требования не исчезают внутри системы и сервер не простаивает при непустой очереди). Распределение времени ожидания существенно зависит от порядка обслуживания, но если дисциплина обслуживания выбирает требования независимо от времени их обслуживания (или любой меры, зависящей от времени обслуживания), то распределение числа требований и времени ожидания в системе инвариантно относительно порядка обслуживания. Для СМО типа M/G/1 можно показать, что для любой дисциплины обслуживания должно выполняться следующее важное равенство Это равенство означает, что взвешенная сумма времен ожидания никогда не изменяется, независимо от того, насколько сложна или искусно подобрана дисциплина обслуживания. Если удается сократить задержку для одних требований, то она немедленно возрастет для других. Для более общей системы с произвольным распределением времени поступления требований G/G/1 закон сохранения может быть записан в виде . Общий смысл этого соотношения таков: взвешенная сумма времен задержки остается постоянной. Просто в правой части стоит разность средней незавершенной работы и остаточного времени обслуживания. Если предположить пуассоновский характер входного потока, то выражение для незавершенной работы можно записать в виде . Подставляя его в предыдущее выражение, сразу получается приведенный ранее закон сохранения для СМО типа M/G/1. Рассмотрим теперь расчет среднего времени ожидания для СМО с обслуживанием в порядке приоритета, задаваемого приоритетной функцией . На рис.7.1 приведена схема функционирования СМО с такой дисциплиной обслуживания: поступающее требование ставится в очередь слева от требования с равным или большим приоритетом. Рис. 7.1 СМО с обслуживанием в порядке приоритета. Воспользуемся формулой для Wp. Исходя из механизма функционирования, можно сразу выписать Все требования более высокого, чем у меченого приоритета будут обслужены раньше. Из формулы Литтла число требований класса i находящихся в очереди, будет равно: Требования более высокоприоритетных классов, поступившие в систему после меченого требования, пока оно находится в очереди, также будут обслужены перед ним. Так как меченое требование будет находиться в очереди в среднем Wp секунд, то число таких требований будет равно . Непосредственно из формулы (*) получаем: Эта система уравнений может быть решена рекуррентно, начиная с W1,W2 и т.д. Полученная формула позволяет рассчитывать характеристики качества обслуживания для всех приоритетных классов. На рисунке 7.2. показано, как изменяется нормированная величина времени ожидания в очереди для СМО с пятью приоритетными классами с равной интенсивностью потока требований каждого приоритетного класса и равным средним временем обслуживания требований каждого класса (нижний рисунок детализирует кривые при значениях малой нагрузки). Рисунок 7.2.Обслуживание в порядке приоритетов в случае относительных приоритетов (Р=5, Р= /5, ). Особую задачу представляет определение законов распределения времени ожидания. Рассмотрим теперь систему с абсолютными приоритетами и обслуживанием в порядке приоритета с дообслуживанием. Применим подход полностью аналогичный рассмотренному ранее. Средняя задержка в системе меченого требования также состоит из трех составляющих: первая составляющая- это среднее время обслуживания, вторая – это задержка из-за обслуживания тех требований равного или более высокого приоритета, которые меченое требование застало в системе. Третья составляющая средней задержки меченого требования представляет собой задержку за счет любых требований, поступающих в систему до ухода меченого требования и имеющих строго больший приоритет. Расписывая все эти три составляющие общего времени нахождения в системе, получим . Весьма интересной задачей является выбор приоритетов для заявок различных классов. Поскольку имеет место закон сохранения, оптимизация имеет смысл только при рассмотрении некоторых дополнительных атрибутов каждого класса требований. Предположим, что можно оценить каждую секунду задержки заявки приоритетного класса p некоторой стоимостью Cp. Тогда средняя стоимость секунды задержки для системы может быть выражена через среднее число требований каждого класса, находящихся в системе Решим задачу нахождения дисциплины обслуживания с относительными приоритетами для системы M/G/1, которая минимизирует среднюю стоимость задержки C. Пусть имеется P приоритетных классов заявок с заданной интенсивностью поступления и средним временем обслуживания. Перенесем в левую часть постоянную сумму и выразим правую часть через известные параметры Задача состоит в минимизации суммы в правой части этого равенства путем выбора соответствующей дисциплины обслуживания, т.е. выбора последовательности индексов p. Обозначим В этих обозначениях задача выглядит так: нужно минимизировать сумму произведений при условии Условие независимости суммы функций gp от выбора дисциплины обслуживания определяется законом сохранения. Иначе говоря задача состоит в минимизации площади под кривой произведения двух функций , при условии , что площадь под кривой одной из них постоянна. Решение состоит в том, что сначала упорядочим последовательность значений fp: . А затем выберем для каждого fp свое значение gp, так, чтобы минимизировать сумму их произведений. Интуитивно ясно, что оптимальная стратегия выбора состоит в подборе наименьшего значения gp для наибольшего fp , далее для оставшихся значений следует поступать тем же образом. Поскольку gp=Wpp, то минимизация сводится к минимизации значений средней задержки. Таким образом, решение рассматриваемой задачи оптимизации состоит в том, что из всех возможных дисциплин обслуживания с относительным приоритетом минимум средней стоимости обеспечивает дисциплина с упорядоченными приоритетами в соответствие с неравенствами . 4.3 Дисциплины обслуживания с приоритетами, зависящими от времени На практике часто встречается задача назначения приоритетов в зависимости от времени поступления заявки. Например, для того, чтобы никакие требования не задерживались в системе очень долго, несмотря на общую нагрузку, организуют дисциплину обслуживания, при которой чем дольше заявка находится в системе, тем ее приоритет становится выше. Рассмотрим приоритетные функции, линейно зависящие от времени с крутизной нарастания, зависящей от номера класса, к которому принадлежит требование. Предположим, что некоторое меченое требование поступает в момент  и получает в момент t приоритет, определяемый значением приоритетной функции Всякий раз, когда сервер готов к обслуживанию нового требования он выбирает из очереди требование с наивысшим мгновенным приоритетом- наибольшим значением приоритетной функции. Требования из класса с большим значением p наращивают приоритет с большей скоростью, чем требования из низшего приоритетного класса. На рисунке 7.3. показан пример того, как поступившее позже требование, но из высшего приоритетного класса, может получить обслуживание раньше, чем поступившее ранее требование из менее приоритетного класса. Это произойдет, если сервер освободится позже момента t0 . При освобождении сервера до этого момента, обслуживание получит первое из поступивших требований. Рис.7.3. Взаимодействие между приоритетными функциями для СМО с приоритетами, зависящими от времени. Исследуем эту систему при экспоненциальном распределении времени обслуживания. Найдем среднее число требований , поступивших позже меченого , из классов с p  i , которые будут обслужены раньше меченого. Очевидно, что для таких требований скорость нарастания приоритетной функции меньше скорости нарастания приоритетной функции меченого требования и , следовательно число таких требований равно нулю. Теперь определим число таких требований для классов с большей, чем у меченого скоростью нарастания приоритетной функции p< i. Из рассмотрения рисунка 7.3. можно видеть, что задержка меченого требования в системе для этого случая Wp=t0- связана с интервалом времени на котором поступают заявки, опережающие меченое требование VI = i -  соотношением Отсюда получаем, что этот интервал равен Следовательно, при интенсивности i входящего потока для требований i-го класса находим среднее число «обгоняющих» требований Рассмотрим теперь меченое требование из класса p, поступающее в момент =0 и находящееся в очереди в течение времени tp. Рисунок 7.4. График приоритета qp(t), используемый для получения . На рисунке 7.4. показано, что значение функции приоритета этого требования к моменту поступления на сервер будет равно bptp. При поступлении меченого требования оно застает в очереди ni требований из класса i . Одно из таких требований показанное на рисунке 7.4. поступило в момент t=-t1. Определим теперь среднее число требований из класса i , которые поступают до нулевого значения момента времени, находятся в нулевой момент еще в очереди и получают обслуживание раньше меченого требования. Из рисунка 7.4. можно видеть, что этому условию удовлетворяет требование из класса i , которое поступает в момент -t1 и ожидает в очереди в течение времени Из рассмотрения соотношений на рисунке видно, что Тогда среднее число требований При i > p Подставив вычисленные средние значения для «обгоняющих» требований получим систему линейных уравнений для величин задержки меченого требования Производя преобразования, можно свести решение этой системы уравнений к рекурсивной форме Полученная формула представляет собой главный результат анализа дисциплины обслуживания с приоритетами, зависящими от времени. Типичная характеристика СМО с проанализированной дисциплиной обслуживания приведена на рисунке 7.5. Штриховая линия показывает характеристику для системы без приоритетов. Видно, что действие закона сохранения проявляется здесь в том, что хотя одна часть заявок, получившая высший приоритет будет иметь меньшее время ожидания, чем в системе без приоритетов с обслуживанием в порядке поступления, другая часть заявок при этом обязательно будет задержана на большее, чем в бесприоритетной системе время. Рис. 7.5 для СМО с относительными приоритетами, зависящими от времени (Р=5, р=/5,). 4.4 Оптимизация назначения приоритетов В настоящем разделе мы рассматриваем задачу , когда с потоком заявок связывается некоторая неотрицательная функция, значение которой для каждой заявки может интерпретироваться как стоимость обслуживания. Рассмотрим систему M/G/1 с интенсивностью поступающего пуассоновского потока  требований в секунду и произвольной функцией плотности вероятности для времени обслуживания с заданным средним временем обслуживания. Пусть плата за требование Y является случайной величиной с произвольной функцией распределения . Система функционирует следующим образом: новое требование, поступившее в систему «предлагает» неотрицательную плату Y «организатору очереди». После этого требованию предоставляется место в очереди такое, что все требования внесшие меньшую плату оказываются позади , большую впереди данного требования. В каждый момент времени сервер, завершив обслуживание очередного требования, принимает на обслуживание требование, оказавшееся впереди всей очереди. До полного завершения обслуживания требование не покидает сервер. Требования, внесшие одинаковую плату, обслуживаются в порядке поступления. Найдем среднее время ожидания в очереди для требования, внесшего плату Y=y. Это время складывается из трех составляющих. Во-первых, это время на дообслуживание требования, находящегося в данный момент в сервере. Во-вторых – время обслуживания требований, которые поступили раньше и внесли большую или равную плату. Наконец меченому требованию придется ждать обслуживания всех требований поступивших позже его, но внесли большую плату. Среднее число требований, плата которых лежит в интервале (u,u+du) определяется по формуле Литтла :, где . Используя обозначения для нижнего и верхнего предела функции (u) можно записать суммарное выражение для времени ожидания в очереди для меченого требования в виде: Используя ряд соотношений и обозначений можно найти, что при разрывной функции распределения вероятности это соотношение может быть приведено к виду При абсолютно непрерывной функции плотности вероятности получим . Таким образом, мы получили конечное среднее время ожидания для всех требований, которые вносят плату выше, чем некоторое критическое значение В пределе, когда размер платы стремится к бесконечности, среднее время ожидания стремится к W0. Нетрудно убедиться, что когда размер платы для всех требований одинаков Это известный результат для СМО типа M/G/1 при обслуживании в порядке поступления, как и следовало ожидать, поскольку равная плата равносильна ее отсутствию с точки зрения распределения приоритетов. При распределении приоритетов можно рассмотреть и другие стоимостные задачи. Определим оптимальное распределение платы за приоритеты в следующих предположениях. Пусть имеется зависимость стоимости от времени задержки в очереди для каждого требования, т.е. есть возможность определить, сколько стоит каждая секунда ожидания в очереди. Опишем эту зависимость с помощью случайного коэффициента нетерпения . Очевидно, что общие затраты клиента при обслуживании будут состоять из платы за место в очереди и потерь от времени ожидания. Для требования с фиксированным коэффициентом нетерпения эти затраты равны Пусть для всей совокупности клиентов можно определить функцию распределения вероятностей коэффициентов нетерпения Сформулируем следующую задачу оптимизации: найти функцию y , которая минимизирует среднюю стоимость С при условии ограничения всей средней платы некоторой заданной величиной B. Определим Преобразуя минимизируемый интеграл, получим Из закона сохранения в непрерывной форме следует, что решение задачи минимизации стоимости сводится к нахождению такой функции, при которой минимальна площадь под кривой произведения : . В то время как площадь под кривой, определяемой первым сомножителем должна оставаться постоянной. Путем рассуждений о согласованности возрастания и убывания функций, входящих в произведение, можно сделать вывод, что решением задачи являются все функции, удовлетворяющие условию Множество S такое, что. Выберем самую простую строго возрастающую функцию – линейную. Таким образом, будем считать, что плата пропорциональна коэффициенту нетерпения. . Применяя ограничение средней платы получим, что, если считать средний коэффициент нетерпения равный A Это и есть функция оптимальной платы. В качестве примера рассмотрим систему с показательным распределением платы Время ожидания можно непосредственно вычислить: Используя рассмотренное правило оптимальной платы можно найти распределение коэффициента нетерпения Следовательно, средняя стоимость получается: Описанная оптимизация является глобальной и позволяет найти функцию платы, которые минимизируют общую среднюю стоимость. Раздел 16 СЕТИ ПЕТРИ КАК ЭФФЕКТИВНАЯ МОДЕЛЬ СМО. СРЕДСТВА ПРОГРАММНОЙ РЕАЛИЗАЦИИ СЕТЕЙ ПЕТРИ. СИСТЕМА МОДЕЛИРОВАНИЯ ARTIFEX И ЕЕ ИСПОЛЬЗО­ВАНИЕ. Для изучения СМО требуется сначала логически описать ее модель, в ко­торой должны реально воплотиться наиболее интересные для изучения и исследования свойства системы. При этом для описания могут быть ис­пользованы различные средства. С одной стороны СМО можно описать просто словесно, это самый простой способ, но и самый неэффективный, так как дает возможность максимум понять как работает система, но не позволяет изучить ее свойства и тем более невозможно проследить какие-либо изменения в ее работе. Можно к словесному описанию добавить еще и схематичное. Тогда модель СМО будет гораздо более понятной, так как ее можно будет наблюдать визуально, однако, как правило, схематичное представление несет минимум информации. Кроме того, такой моделью нельзя наглядно отобразить функционирование системы во времени. По­этому работать с такой моделью можно только на раннем этапе исследова­ния СМО, используя ее как наглядное пособие в изучении статических свойств системы. С другой стороны СМО можно описать в виде совокупно сти математических соотношений, представив модель реальной СМО с по­мощью алгебраических, дифференциальных, интегральных и других урав­нений. Такой подход используется для установления зависимостей между входными и выходными параметрами системы и незаменим для глубокого исследования свойств СМО. Однако у пего есть ряд недостатков: во-первых, большая сложность разработки такой модели, заключающаяся в отображении реальных свойств системы абстрактным языком математики. Во вторых, из-за изобилия математических соотношений страдает нагляд­ность создаваемой системы, а это усложняет восприятие модели как физи­чески реального объекта. Кроме того, во многих практических задачах ин­терес представляет не только количественная оценка параметров системы, сколько ее работа в различных ситуациях, при смене условий и с течением времени, а выполнить это в данном случае довольно нелегко. Еще одним недостатком является то, что при добавлении НОВОГО компонента или но­вого параметра в модель, придется менять всю модель, заново выстраивать цепочку математических соотношений. Особенно сильно проявляются опи­санные выше недостатки при исследовании сложных, иерархических сис­тем, к которым и относятся большинство моделей СМО. А можно воспользоваться менее формальным и более наглядным средст­вом описания, которое предоставляет аппарат сетей Петри. Сеть Петри - инструмент для описания и исследования динамических систем. Развитие теории сетей Петри проводилось по двум направлениям. Формальная теория сетей Петри занимается разработкой основных средств, методов и понятий, необходимых для применения сетей Петри. Прикладная теория сетей Петри связана главным образом с применением сетей Петри к моделированию систем и их анализу. Формальная теория сетей Петри - это достаточно долго разрабатывае­мый аппарат для описания и моделирования параллельных и распределён­ных процессов. Благодаря абсолютно простой основе, сети Петри наглядны и просты для понимания. Основанная в начале 60-х годов немецким мате­матиком К.А.Петри, в настоящее время она содержит большое количество моделей, методов и средств анализа, имеющих обширное количество при­ложений практически во всех отраслях вычислительной техники и даже вне ее. В соответствии с требованиями прикладных областей были разра­ботаны различные расширения сетей Петри направленные на учёт времен­ных, вероятностных характеристик, использование данных, построение иерархических моделей и т.д. Одно из основных достоинств сетей Петри заключается в том, что они могут быть представлены как в графической форме, что обеспечивает их наглядность, так и в аналитической. При графической интерпретации сеть Петри представляет собой граф особого вида, состоящий из вершин двух типов - позиций (position) и пе­реходов (transition), соединенных ориентированными дугами, причем ка­ждая дуга может связывать лишь разнотипные вершины (позицию с пере­ходом или переход с позицией). Вершины-позиции обозначаются кружка­ми, вершины переходы - прямоугольниками (или черточками). Рисунок 1. – Простая сеть Петри В содержательном плане, переходы соответствуют событиям, присушим исследуемой системе, а позиции - условиям их возникновения. Переход (событие) характеризуется определенным числом входных и выходных по­зиций, соответствующих предусловию и постусловию данного события. Со­вокупность переходов, позиций и дуг позволяет описать статическую сис­тему. Для описания динамики, вводится еще один объект - так называе­мый маркер(token), или метка позиции, которая соответствует выполне­нию того или иного условия (обозначается точкой внутри позиции). Распо­ложение маркеров в позициях называется разметкой сети. Переход счита­ется активным, если в каждой его входной позиции есть хотя бы один мар­кер, что равносильно выполнению всех необходимых условий для наступ­ления события. Наступление события в терминах сетей Петри представля­ется срабатыванием перехода, при этом маркеры из входных позиций изымаются и добавляются в каждую выходную позицию. Текущее состоя­ние исследуемой системы определяется распределением маркеров по пози­циям сети, а динамика поведения системы отображается перемещением маркеров по позициям сети. Рисунок 2. Маркированная сеть Петри. Пример изменения разметки «ли при срабатывании переходов. Строгое аналитическое определение сетей Петри хорошо представлено в литературе, поэтому здесь излагаться не будет, ограничимся описанием наиболее важных расширений сетей Петри. Это приоритетные сети, сети с цветными маркерами (раскрашенные или цветные) и структурированные сети. Приоритетные сети, это сети, учитывающие приоритетные соотноше­ния между переходами. В приоритетных сетях при наличии двух и более активных переходов сработать может лишь переход, имеющий высший приоритет. Структурированные сети служат для моделирования иерархи­ческих систем, которые наряду с неделимыми компонентами содержат со­ставные компоненты, сами представляющие собой системы. В раскрашен­ных сетях каждому переходу ставится в соответствие функция, опреде­ляющая маркирование выходных позиций в зависимости от цветов вход­ных маркеров. Расширение простых сетей в цветные заключается в добав­лении следующей информации к элементам сети: - Маркеры вместо простого обозначения выполнения условия преобра­зуются в объект, который может содержать в себе один или более парамет­ров, каждый из которых может принимать дискретный набор значений. В соответствии с этим маркеры различаются по типам параметров (перемен­ных). Чтобы отличать маркеры различных типов их можно окрашивать в различные цвета (поэтому сети называют цветными) - К местам добавляется информация о типах маркеров, которые могут находится в данном месте. - К переходам может быть добавлена информация с предикатом акти­визации перехода, в зависимости от переменных, содержащихся в марке­рах. - К начальной маркировке сети добавляется информация о значении переменных, содержащихся в маркерах. Приведем пример цветной сети Петри, которая моделирует поведение отдельного абонента телефонной сети (рисунок 4). Позиции сети соответствуют состояниям процесса установления теле­фонной связи, а переходы - смене соответствующих состояний. В процессе работы каждый телефонный аппарат может быть переведен из пассивного состояния «ожидание» (Р 1) в такое при котором трубка снята и слышен «непрерывный гудок». Далее во время набора номера «сигнала нет» до тех пор, пока не появятся либо короткие гудки, свидетельствующие о том, что вызываемый абонент (аj) занят, либо длинные гудки, свидетельствующие, что телефон вызываемого абонента звонит. В последующем абонент аj мо­жет поднять трубку и телефонная связь будет восстановлена до тех пор по­ка вызывающий абонент не вернется в пассивное состояние, отсоединив тем самым абонента аj. Рисунок 3. - Сеть Петри моделирующая повеление телефонного абонента со стороны пользователя. В дополнение к сети, описывающей функционирование отдельных або­нентов, на рисунке 3 представлена сеть Петри, отражающая синхрониза­цию между ними. Анализ синхронизирующей сети показывает, что каждый абонент может быть свободен или занят. Пара (ai, aj), которой помечена по­зиция «вызов 1» , показывает, что абонент ai вызван абонентом aj. Когда абонент aj свободен, вызов (ai, aj) может перейти в фазу «вызов 2» и при снятии трубки абонентом aj устанавливается соединение. Рисунок 4. - Сеть Петри моделирующая поведение телефонного абонента со стороны АТС. Таким образом, работа телефонной сети описывается двумя сетевыми моделями, наложенными друг на друга (т.е. с разных точек зрения модели­рующих одни и те же события - переходы, имеющие одинаковые номера). Эти две сети Петри представляют собой наглядную формальную модель, позволяющую прочувствовать многие слабоуловимые свойства интерпре­тируемой телефонной системы. Например, можно проследить, что про­изойдет, если абонент вызывает сам себя, или если соединение может быть прервано только со стороны вызывающего (а не вызываемого) абонента. При вербальном (не формальном) описании такие подробности можно легко забыть или истолковать неоднозначно. В дополнение к описанным выше существуют расширения сетей Петри, с помощью которого некоторые количественные характеристики исследуе­мых систем можно определить аналитически. Это временные и стохастиче­ские сети. Именно стохастические сети Петри наиболее полно позволяют описать элементы СМО. Стохастические сети это сети Петри, в которые вводятся некоторые вероятностные атрибуты, например вероятности или плотности вероятностей срабатывания активных переходов. Например, простейшая СМО состоит из источника заявок, который формирует входной поток, сервера, обслуживающего поступающие заявки с определенной производительностью и очереди перед сервером, обуслов­ленной ограниченной производительностью. Один из возможных вариан­тов сети Петри, моделирующей данную СМО представлена на рисунке 4. Рисунок 4. – Модель простейшей СМО в виде сети Петри. Представленная на рисунке модель состоит из бесконечного источника заявок, который способен генерировать одну заявку каждую единицу вре­мени; очереди, неограниченного размера, и сервера, обладающего беско­нечно большой производительностью, который, забирая по одной заявке из очереди, мгновенно их обслуживает. Однако такая модель не представляет практической ценности, так как не хватает информации о параметрах СМО. Таким образом, необходимо данную сеть Петри преобразовать в сто­хастическую. Сделаем это следующим образом: процесс формирования заявок на обслуживание является в общем случае случайным и может рас­сматриваться как поток событий, происходящих через случайные проме­жутки времени. Случайные временные интервалы между поступлениями заявок могут подчиняться различным законам распределения. Информа­цию о законе распределения поместим в переход Т1. Производительность сервера обратна длительности обслуживания заявки, равной промежутку времени, необходимому серверу для обслуживания заявки. В общем случае это тоже случайная величина, функцию распределения которой зададим в переходе ТЗ. Кроме того, очередь тоже обладает рядом параметров. Это число мест в очереди N и время пребывания в очереди. В результате получаем модель, в которой переход Т1 по заданному зако­ну генерирует заявки, далее заявки поступают в очередь Р2, и если сервер свободен (а это характеризуется наличием маркера в позиции Р4), то об­служивается и попадает в обслуженные заявки. Если же сервер занят, то заявка стоит в очереди заданное время Т, а затем покидает ее и попадает в потерянные заявки (позиция Р6). 1 Введение. Потоки случайных событий. Основные понятия: сообщение, вызов, попытка вызова, понятия занятия. Состояние объекта. Потоки случайных событий. Принципы классификации потоков. Характеристики потоков, распределение потока. Нестационарный пуассоновский поток. Пуассоновский поток с условными потерями. Примитивный поток. Простейший поток. Поток освобождения. Поток с ограниченным последействием. 2 Нагрузка и хар-ки качества обслуживания. Дисциплина обслуживания потока вызовов. Нагрузка и ее виды, основные параметры. Иерархическая система свойств обслуживания. Показатели качества обслуживания. Изменение нагрузки во времени. Концентрация нагрузки. Виды занятий и их продолжительность. Понятия об исследованиях процессов обслуживания потоков вызовов. 3 Полнодоступный пучок. Система с явными потерями. Понятие о пропускной способности КС. Обслуживание простейшего потока. Обслуживание примитивного потока. Сравнение показателей качества. 4 Полнодоступный пучок. Система с ожиданием. Обслуживание простейшего потока. Вторая формула Эрланга. Обслуживание простейшего потока при постоянном времени занятия. Однолинейные системы, область применения. 5 Неполнодоступный пучок. Система с явными потерями. Общие сведения. Основные характеристики НД схем. 6 Звеньевые коммутационные системы. Общие сведения. Расчет двухзвенных КС. Метод эффективной доступности. Структура многозвенных КС. Особенности цифровых коммутационных полей. Расчет однозвенных КС. Метод цилиндров. Метод О’Делла. Расчет многозвенных КС. 7 Однозвенные полнодоступные коммутационные системы при совместном обслуживании разнотипных потоков сообщений. Многопотоковые модели. Модели с обобщенным входным потоком. 8 Распределение нагрузки и потерь в сетях связи. Прогнозирование нагрузки. Распределение нагрузки. Качество обслуживания в сетях связи. 9 Расчет обходных направлений в сетях связи. Эффективность обходных направлений. Метод эквивалентных замен. 10 Измерение нагрузки и потерь в сетях связи. Цели и задачи. Классификация измерений. Методы измерений. Обработка результатов. 11 Методы расчета характеристик качества обслуживания в ЦСИО. Обслуживание самоподобной нагрузки. Расчет пропускной способности мультисервисных телекоммуникационных сетей. 12 Сравнение характеристик качества обслуживания в сетях с коммутацией каналов и коммутацией пакетов. 13 Анализ характеристик каналов с интеграцией речи и данных. Метод производящих функций. Модели интеграции речи и данных. 14 Статистическое моделирование систем теории телетрафика. Моделирование случайных величин. Статистические характеристики моделирования. Программное моделирование трафика. Основы языка GPSS. 15 Анализ систем массового обслуживания с приоритетами. Дисциплины обслуживания. Модель с приоритетами. Основная модель расчета среднего времени ожидания. 16 Сети Петри как эффективная модель СМО.