В-формула Эрланга основана на модели, которая содержит три элемента: структура, стратегия и нагрузка (рис.1.1).
Стратегия. Вызов, достигая системы, принимается для обслуживания, если, по крайней мере, один канал свободен. Каждый вызов использует один и только один канал. Мы говорим, что группа имеет полную доступность. Часто используется термин полная готовность, но эта терминология будет использоваться только для случаев определения надежности соединения. Если все каналы заняты, система переполняется, и попытка вызова блокируется. Это блокированный вызов (отклоненный, потерянный) называется попыткой и исчезает из системы без всяких последствий. Последствия могли быть, если бы была принята стратегия с альтернативными маршрутами. Это стратегия - самая важная и применялась успешно много лет.
Она называется системой с потерями Эрланга или с явными потерями вызовов (LCC Lost Calls Cleared).
Определение предложенной нагрузки. Мы определяем предложенную нагрузку как нагрузку, которая поступает при бесконечном числе каналов (емкости) (2.2). В Эрланговской
Мы рассматриваем два случая:
Мы увидим позже, что эта модель нечувствительна к распределению времени пребывания в системе, то есть для вероятностей состояния важно только среднее время пребывания в системе. Тип распределения не имеет никакого значения для вероятностей состояния.
Критерии качества работы. Самые важные показатели уровня обслуживания для систем с потерями - потери по времени $$E$$, потери по вызовам $$B$$ и потери по нагрузке $$C$$. Все они равны между собой для PASTA - Poisson Arrival See Time Average, секция 6.3). Наиболее важные из этих свойств:
Мы предполагаем, что процесс поступления вызовов - Пуассоновский процесс, и что времена пребывания в системе имеет экспоненциальное распределение, то есть мы рассматриваем нагрузку PCT-I. Предполагается, что число каналов бесконечно, так что блокировка (перегрузка) отсутствует.
Мы определяем состояние системы $$[i] $$ как число занятых каналов $$i (i = 0,1,2, \dots) $$.
На рис.7.1 все состояния системы даны в виде окружностей и дуг от одного состояния до другого состояния, на которых показано значение интенсивности. Этот процесс простой (секция 5.1). Мы рассматриваем только переходы в соседние состояния.
(рис 7.1) Пуассоновское распределение. Диаграмма переходов состояний схематически изображает переходы для системы с бесконечным числом каналов, Пуассоновским потоком вызовов ( $$\lambda$$ ) и экспоненциально распределенными временами пребывания в системе ( $$\mu$$ ).
Если мы предполагаем, что система находится в статистическом равновесии, то система будет находиться в состоянии $$[i] $$ в течение определенного времени, пропорционального $$p(i) $$, где $$p(i) $$ - вероятность существования системы в состоянии $$[i] $$ в случайный момент времени. Когда процесс находится в состоянии $$[i] $$, он может перейти в следующий момент времени в состояние $$[i+1] \lambda$$ раз в единицу времени или в состояние $$[i-1] i \mu$$ раз в единицу времени. В момент перехода из состояния в состояние процесс покидает состояние $$[i] $$. Будущее развитие диаграммы состояний зависит только от существующего состояния, а не от того, как процесс прибыл в это состояние (Марковское свойство).
Уравнения, описывающие состояние системы, согласно предположению о статистическом равновесии могут быть получены двумя способами, которые основаны на принципе глобального равновесия.
а. Уравнения узла
В статистическом равновесии число переходов в состояние $$[i] $$ в единицу времени равно числу переходов из состояния $$[i] $$. Вероятность состояния равновесия $$р (i) $$ обозначает соотношение времени (отношение всего времени процесса к отношению в единицу времени), когда процесс находится в состоянии $$[i] $$. Среднее число переходов из состояния [0] в состояние [1] равно $$\lambda \times р(0) $$, в единицу времени, и среднее число переходов из состояния [1] в состояние $$[0] - \mu \times p(1) $$ в единицу времени. Для состояния $$[i] $$ мы получаем следующее равновесие или уравнение равновесия:
$$\lambda *p(0)=\mu *p(1), i=0,$$ $$\lambda *p(i-1)+(i+1) \mu * p(i+1)=(\lambda +i \mu)*p(i), I > 0.$$Уравнения узла также всегда применимы, для диаграмм перехода, где от одного состояния можно перейти в одно из нескольких состояний (несколько измерений), которые мы рассмотрим в более поздних лекциях.
б. Уравнения сечения
Во многих случаях мы можем применять простую структуру диаграммы перехода состояния. Применим фиктивное сечение, например, между состоянием $$[i-1] $$ и $$[i] $$ (т.е. выделяем переходы от состояния $$[0],[1], \dots , [i-1] $$ ). Затем рассматриваем статистическое равновесие нагрузки от состояния $$[i - 1] $$ к $$[i] $$ и изменение от состояния $$[i] $$ к $$[i-1] $$. В статистическом равновесии мы, таким образом, имеем в единицу времени:
$$\lambda *p(i-1)=i \mu * p(i), i=1,2, \dots$$Уравнения сечения, прежде всего, используются для одномерных диаграмм перехода состояния, тогда как уравнения узла применимы к любой диаграмме.
Так как система всегда будет в некотором состоянии, мы имеем нормализующее ограничение:
$$\sum_{i=0}^{\infty}p(i)=1, p(i) \ge 0.$$Можно заметить, что уравнения узла (7.3) включают три вероятности состояния, тогда как уравнения сечения (7.4) включают только две. Поэтому уравнения сечения решаются проще.
Для одномерной диаграммы перехода состояний в большинстве случаев применяют подход на основе метода сечений. Из рис.7.1 мы получаем следующие уравнения равновесия:
$$\lambda * p(0)= \mu *p(1),\\ \lambda *p(1)=2 \mu *p(2),\\ \dots \dots\\ \lambda * p(i-1)=i\mu *p(i),\\ \lambda * p(i)=(i+1)\mu *p(i+1).$$Используя выражение $$p(0) $$ и обозначая $$А= \lambda / \mu,$$ получаем
$$p(0)=p(0),\\ p(1)=A*p(0),\\ p(2)=\frac{A}{2}*p(1)=\frac{A^2}{2}*p(0),\\ \dots \dots \dots\\ p(i-1)=\frac{A}{i-1}*p(i-2)=\frac{A^{i-1}}{(i-1)!}*p(o),\\ p(i)=\fracAi*p(i-1)=\frac{A^i}{i!}*p(0),\\ p(i+1)=\frac{A}{i+1}*p(i)=\frac{A^{i+1}}{(i+1)!}*p(0),\\ \dots \dots \dots$$Из ограничения нормализации получаем $$р(0) $$:
$$1=\sum_{j=0}^{\infty}p(j)\\\ =p(0)*\left \{1+A+\frac{A^2}{2!}+ \dots + \frac{A^i}{i!} + \dots \right \}\\ =p(0)*e^A,\\ p(0)=e^{-A},$$Это
Число занятых каналов в случайный момент времени подчиняется
С точки зрения измерения нагрузки, система с бесконечным числом линий не очень интересна. Просмотрим важные характеристики нагрузки
Потери по времени $$E=0$$
Потери по вызовам $$B=0$$
Обслуженная нагрузка $$Y=\sum_{i=0}^{\infty}i*p(i)=A$$,
Потерянная нагрузка $$A_l=A-Y=0$$,
Потери по нагрузке $$C=0$$
Нагрузка, которая обслужена $$i$$ -той линией, принимающей последовательную нагрузку, дается позже в (7.14).
Пиковость Z определяется как отношение между дисперсией и средней величиной распределения вероятностей состояния.
Для
Пиковость имеет размерность [число каналов] и отличается от коэффициента вариации, который не имеет никакого измерения (3.9).
Продолжительность состояния [i]
В состоянии $$[i] $$ процесс имеет полную интенсивность $$(\lambda + I \mu) $$. Поэтому время до первого перехода (переход из состояния $$i$$ либо к $$i+1$$, либо к $$i-1$$ ) - распределено по экспоненте (секция 4.1.1):
$$f_i(t)=(\lambda + i \mu)e^{-(\lambda + I \mu)t}, t \ge 0.$$В примере 6.2.2 мы рассматривали протокол синхронная (сегментированная) АЛОХАа, где оси времени были разделены на слоты времени. Мы теперь рассматриваем тот же самый протокол в непрерывное время. Предположим, что пакеты прибывают согласно Пуассоновскому процессу и что они имеют постоянную длину $$h$$. Система соответствует случаю нагрузки, заканчивающемуся Пуассоновским распределением, которое также является справедливым для постоянных времен занятия (секция 7.2). Вероятности состояния отображаются Пуассоновским распределением (7.6), где $$A = \lambda h$$. Пакет передается правильно, если: (а) система находится в состоянии [0] во время прибытия и (б) никакие другие пакеты не поступают в течение времени обслуживания $$h$$. Мы находим:
$$P_{correct} =р(0)-е^{-\lambda h}=е^{-2A}.$$Переданная правильно нагрузка, таким образом, получается:
$$A_{correct}=A*p_{rcorrect}=A*e^{-2A}.$$Это - соотношение оси времени, при эффективном использовании оно имеет оптимум для $$h = А = 1/2$$, где производная относительно $$А$$ равняется нулю:
$$\frac{\partial A_{correct}}{\partial A}=e^{-2A}*(1-2A),\\ max\{A_{correct}\}=\frac{1}{2e}=0.1839$$Мы, таким образом, получаем, что максимальное использование равно 0.1839, когда предложение равно 0.5 Эрл. Это - половина значения, которое мы получили для системы, использующей слоты в синхронных спутниковых передатчиках. Сравнение различных моделей АЛОХА уже было сделано на рис.6.4.
Мы рассматриваем вариант, когда Чистая Случайная Нагрузка I (PCT-I) такая же, как в секции 7.2. Число каналов теперь ограничено и я конечно. Число состояния становится $$n+1$$, диаграмма Чистая Случайная Нагрузка I при переходе состояний показана на рис.7.2.
(рис 7.2) Усеченное Пуассоновское распределение..Диаграмма переходов состояний схематически изображает систему с ограниченным числом каналов $$(n) $$, Пуассоновский поток вызовов $$(\lambda) $$ и экспоненциальное время обслуживания $$(\mu) $$ )
Мы получаем уравнения сечения, как и в случае Пуассоновского процесса, но пространство состояний ограничено $$\{0, 1, \dots , п) $$ и условие нормализации (7.5) теперь равно:
$$p(0)=\left \{ \sum_{j=0}^n \frac{A^j}{j!} \right\}^{-1}$$Мы получаем так называемое усеченное Пуассоновское распределение (первая формула Эрланга):
$$p(i)=\frac{\frac{A^i}{i!}}{\sum_{j=0}^n \frac{A^j}{j!}}, 0 \le i \le n.$$Название усеченное означает "укороченное" вследствие того, что решение может интерпретироваться как усеченное
Зная вероятности состояния, мы можем найти критерии качества работы, определяемые этими вероятностями состояния.
Потери по времени
Вероятность, что все $$п$$ каналов заняты в случайный момент времени, равна отношению всего времени работы ко времени занятости всех каналов (математическое ожидание времени). Это видно из (7.9) для $$i=n$$:
$$E_n(A)=p(n)=\frac{\frac{A^n}{n!}}{1+A+\frac{A^2}{2!}+\dots +\frac{A^n}{n!}}.$$Это - известная В-формула Эрланга (1917, [11]). Она обозначается $$Е_n (А) = Е_{1,п} (А) $$, где указатель "1" рассматривается как указатель названия первая формула Эрланга.
Потери по вызовам
Вероятность, что случайный вызов будет потерян, равна отношению всех попыток вызовов к числу блокированных попыток вызова. Если мы рассматриваем единицу времени, то находим $$В = В_n (А) $$:
$$B=\frac{\lambda * p(n)}{\sum_{v=0}^n} \lambda * p(v)=p(n)=E_n(A)$$Обслуженная нагрузка
Если мы используем усеченное уравнение между состоянием $$[i-1] $$, и $$[i] $$, то получим:
$$Y=\sum_{i=1}^n i*p(i)=\sum_{i=1}^n \frac{\lambda}{\mu}*p(i-1)=A*\{1-p(n)\},\\ Y=A*\{1-E_n(A)\},$$где А - предложенная нагрузка. Обслуженная нагрузка будет меньше и чем А, и чем п.
Потери по нагрузке
$$A_l=A- Y=A-E_nA).\\ C=\frac{A-Y}{A}=E_n(A).$$Мы, таким образом, имеем Е=В=С, потому что интенсивность вызова не зависит от состояния. Это свойство - PASTA (Poisson Arrivals See Time Averages - Пуассоновское поступление вызовов, наблюдаемое за среднее время) - справедливо для всех систем с Пуассоновскими потоками вызовов. Во всех других вариантах, по крайней мере, два из трех случаев потерь различны. В-формула Эрланга показана графически на рис. 7.3 для некоторых выбранных значений параметров.
Нагрузка, которую обслуживает i -ый канал (использование $$а_{ij}$$ )
Случайный поиск. В этом случае все каналы в среднем обслуживают одну и ту же нагрузку. Полная обслуженная нагрузка не зависит от стратегии поиска, и мы можем найти использование:
(рис 7.3) Вероятность блокировки $$Е_n(А) $$ как
Эта функция показана на рис. 7.4, и мы наблюдаем, что в данном случае при потерях Е получается самое высокое использование для больших групп канала (экономия из-за масштаба).
(рис 7.4) Среднее удельное использование а (7.13) как функция числа каналов n для заданных значений потерь Е Обусловленный поиск - последовательный поиск: нагрузка, которую обслуживает канал, есть разность между нагрузкой, потерянной i-1 каналами, и нагрузкой, потерянной i каналами:
Отметим, что нагрузка, которую обслуживает канал i, не зависит от общего числа каналов. Таким образом, каналы после i -того канала не влияют на нагрузку, обслуживаемую каналом i, т.е. между каналами нет никакой обратной связи.
Функция увеличения
Она обозначает увеличение обслуженной нагрузки, когда число каналов увеличено на один от n до n + 1:
Мы имеем $$0 \le F_n(A) \le 1$$..
Функция увеличения Fn (А) сведена в таблицу (Арн Дженсен, 1950 [50]) и показана на рис.7.5. В секции 7.6.2 мы рассматриваем приложение этого принципа для оптимального экономичного измерения нагрузки.
Пиковость
Она определяется как отношение между дисперсией и средней величиной распределения числа занятых каналов, сравните с IDC (Индексрассеяния для расчетов - Index of
Размерность - [число каналов]. В группе с обусловленным поиском мы можем таким образом оценить пиковость нагрузки, которую обслуживает последний канал.
(рис 7.5) Функция увеличения $$F_n (A) $$ (7.16) по В формуле Эрланга. $$F_n (А) $$ при
Продолжительность состояния [i]
Полная интенсивность для перехода из состояния $$[i] $$ постоянна и равна $$(\lambda + i \mu) $$, и поэтому продолжительность времени в состоянии $$[i] $$ (время пребывания) экспоненциально распределена с функцией плотности:
$$f_i(t)=(\lambda + I \mu)*e^{-(\lambda + i \mu)t}, 0 \le I < n,\\ f_n(t)=(n \mu)* e^{-(n \mu)t}, i=n$$Самый важный инструмент в теории телетрафика - формулировка и решение задач с помощью моделей, посредством применения диаграмм перехода состояния. Из предыдущих секций мы можем установить следующую стандартную процедуру для того, чтобы применить диаграмму перехода состояния. Она состоит из множества шагов и может быть сформулирована в общих терминах. Эта процедура также применима для
Процедура всегда проходит следующие шаги.
Созданием диаграммы перехода состояния:
Этим способом мы получаем законченную диаграмму перехода состояния.
Составить уравнения, описывающие систему.
Если условия для статистического равновесия выполнены, уравнения устойчивости состояний могут быть получены из:
Решить уравнения равновесия, отображающие статистическое равновесие.
На практике мы находим ненормализованное значение вероятности состояния $$q(0) $$, равное единице, а затем вычисляем относительную величину $$q(i), (i= 1, 2 \dots ) $$. Нормализуя ее, находим:
$$p(i)=\frac{q(i)}{Q_n}, i=0,1, \dots , n,$$где
$$Q_n=\sum_{v=0}^n q(v).$$Тогда потери по времени получаются равными:
$$p(n)=\frac{q(n)}{Q_n}=1-\frac{Q_{n-1}}{Q_n}$$Если значения $$q(i) $$ становятся очень большими (например, $$10^{10}$$ ), то мы можем умножить все $$q (i) $$ на одну и ту константу (например, $$10^{-10}$$ ), так как мы знаем, что все значения вероятностей находятся в пределах интервала [0, 1]. Этим способом мы избегаем проблем вычисления. Если значения $$q(i) $$ становятся очень маленькими, мы можем усечь пространство состояний, так как плотность распределения $$p(i) $$ часто имеет колоколоо-бразный вид $$a$$ (unimodal - "унимодальный") и поэтому имеет максимум. Во многих случаях мы, теоретически, способны контролировать ошибку, вносимую усечением пространства состояний (Степанов, 1989 [94]).
Мы можем нормализовать вероятности состояний после каждого шага, который требует больших вычислений, но гарантирует высокую точность. Нормализуем вероятности состояний для системы с $$х-1$$ каналами:
$$P_{x-1}=\{p_{x-1}(x-1), p_{x-1}(x-2), \dots, p_{x-1}(0)\}, x=1,2, \dots,$$где индекс $$(х-1) $$ указывает, что это вероятности состояния для системы с $$(х-1) $$ каналом. Предположим, что мы имеем следующую рекурсию для $$q_x(x) $$, заданную некоторой функцией от предыдущих вероятностей состояний:
$$q_x(x)=f\{p_{x-1}(x-1}, p_{x-1}(x-2), \dots, p_{x-1}(0)\}, x=1,2, \dots,$$где $$q_x(x) $$ будет относительной вероятностью состояния. Предположим, что мы знаем нормализованные вероятности состояний для $$(х-1) $$ каналов (7.22) и хотим найти нормализованные вероятности состояния для системы с $$х$$ каналами. Относительные значения вероятностей состояния не изменяются, когда мы увеличиваем число каналов на один, тогда получаем:
$$q_x(i)=\begin{cases} p_{x-1}, i=0,1,2,\dots, x-1,\\ f\{p_{x-1}(x-1}, p_{x-1}(x-2), \dots, p_{x-1}x(0)\}, i=x \end{cases}$$Новая константа нормализации получается:
$$Q_x=\sum_{i=0}^xq_x(i)=1+q_x(x),$$так как мы на предыдущем шаге нормализовали сумму вероятностей состояний в пределах от 0 к $$х-1$$, и, увеличивая их на единицу, получаем:
$$p_x(i)=\begin{cases} \frac{p_{x-1}(i)}{1+q_x(x)}, i=0,1,2, \dots, x-1,\\ \frac{q_x(x)}{1+q_x(x)}, i=x \end{cases}.$$В начале процесса рекурсии присваивается значение $$р_0(0)=1$$. Алгоритм рекурсии начинается с этого значения и находит вероятности состояния системы с одним каналом больше (7.24) и (7.25). Рекурсия в цифровой форме очень устойчива, потому что мы в (7.25) делим на число, большее единицы.
Рассмотрим простой процесс гибели и размножения с интенсивностью поступления $$\lambda_i$$ и скоростью выхода из состояния $$i \mu$$ в состоянии $$i$$. Тогда $$q_x(x) $$ зависит только от вероятности предыдущего состояния. Используя уравнение сечения, мы получаем следующую формулу рекурсии:
$$q_x(x)=\frac{\lambda_{x-1}}{x \mu}*p_{x-1}(x-1).$$Потери по времени для $$х$$ каналов - $$Е_x(А) = р_х(х) $$. Подставляя (7.26) в (7.25), получаем простую рекурсивную формулу для потерь по времени:
$$E_x=\frac{q_x(x)}{1+q_x(x)}=\frac{\frac{\lambda_{x-1}}{x \mu}*E_{x-1}}{1+\frac{\lambda_{x-1}}{x \mu}*E_{x-1}}, E_0=1$$Находя инверсию вероятности потерь по времени $$Iх = Е^{-1}$$, мы получаем:
$$I_x=1+\frac{x \mu}{\lambda_{x-1}}*I_{x-1}, I_0=1$$Это общая рекурсивная формула для вычисления потерь по времени для всех систем с интенсивностью поступления состояния $$\lambda_i$$ и однородными обслуживающими приборами.
Если мы хотим вычислить
Для вычислений формула (7.10) не является удобной: $$n$$! увеличивается так быстро, что в компьютере возникает перегрузка. Если мы применим (7.27), то получим рекурсивную формулу:
$$E_x(A)=\frac{A*E_{x-1}(A)}{x+A*E_{x-1}(A)}, E_0(A)=1$$С числовой точки зрения,
где $$I_n(А) = 1/Е_n(А) $$. Эта рекурсивная формула точна, и даже для больших значений $$(n, А) $$ нет ошибок округления. Это - основная формула для многочисленных таблиц В-формул Эрланга и так называемых классических таблиц (Пальма, 1947 [81] ). Для очень больших значений $$n$$ есть более эффективные алгоритмы. Заметим, что рекурсивная формула, которая является точной при увеличении индекса, обычно неточна при уменьшении индекса, и наоборот.
Мы рассматриваем Эрланговскую систему с потерями с $$n = 6$$ каналами, интенсивностью поступления вызовов $$\lambda = 2$$ в единицу времени и интенсивностью освобождения $$\mu = 1$$ в единицу времени отклонения так, чтобы предложенная нагрузка была $$А = 2$$ Эрл. Если мы обозначим ненормализованную вероятность относительного состояния $$q(i) $$, то получим диаграмму перехода состояния, которая схематически изображает значения, показанные в следующей таблице:
| $$i$$ | $$\lambda (i)$$ | $$\mu (i)$$ | $$q(i)$$ | $$p(i)$$ | $$i*p(i)$$ | $$\lambda (i)- p(i)$$ |
|---|---|---|---|---|---|---|
| 0 | 2 | 0 | 1.0000 | 0.1360 | 0.0000 | 0.2719 |
| 1 | 2 | 1 | 2.0000 | 0.2719 | 0.2719 | 0.5438 |
| 2 | 2 | 2 | 2.0000 | 0.2719 | 0.5438 | 0.5438 |
| 3 | 2 | 3 | 1.3333 | 0.1813 | 0.5438 | 0.3625 |
| 4 | 2 | 4 | 0.6667 | 0.0906 | 0.3625 | 0.1813 |
| 5 | 2 | 5 | 0.2667 | 0.0363 | 0.1817 | 0.0725 |
| 6 | 2 | 6 | 0.0889 | 0.0121 | 0.0725 | 0.0242 |
| Total | 7.3556 | 1.0000 | 1.9758 | 2.0000 |
Мы получаем следующие вероятности блокировки:
Потери по времени $$Е_е(2) = р(6) = 0.0121$$.
Потери по нагрузке $$C_6(2)=\frac{A-Y}{A}=\frac{2-1.9758}{2}=0.0121$$.
Потери по вызовам $$B_6(2)=\frac{\{\lambda (6)*p(6)\}}{\left \{ \sum_{i-0}^6 \lambda (i)*p(i)\right \}}=\frac{0.0242}{2.0000}=0.0121$$.
Отметим, что $$Е = В = С$$ из-за свойства PASTA (Poisson Arrival See Time Average - Пуассоновское поступление вызовов, наблюдаемое за среднее время).
Применяя рекурсивную формулу (7.29), мы, конечно, получаем те же самые результаты
$$E-0(2)=1\\ E_1(2)=\frac{2*1}{1+2*1}=\frac 23,\\ E_2(2)=\frac{2*\frac 23}{2+2*\frac 23}=\frac 25,\\ E_3(2)=\frac{2*\frac 25}{3+2*\frac 25}=\frac{4}{19}\\ E_4(2)=\frac{2*\frac{2}{19}}{4+2*\frac{2}{19}}=\frac{2}{21},\\ E_5(2)=\frac{2*\frac{2}{21}}{5+2*\frac{2}{21}}=\frac{4}{109},\\ E_6(2)=\frac{2*\frac{4}{109}}{6+2*\frac{4}{109}}=\frac{4}{331}=0.121.$$Применяя рекурсию, (7.30) мы находим:
$$I_x(A)=1+\frac xA+\frac{x(x-1)}{A^2}+ \dots +\frac{x!}{A^x},$$Это выражение является обратной вероятностью блокировки В-формулы. При больших значениях х эта формула может быть применена для быстрого вычисления В-формулы, потому что мы можем ограничить сумму, когда ее элементы становятся очень маленькими.
Когда измеряется нагрузка системы обслуживания, необходимо обеспечить баланс требований уровня обслуживания и экономических ограничений. В этой лекции мы увидим, как это может быть сделано.
В системах телекоммуникации есть несколько показателей, которые характеризуют обслуживание. Самый объемный показатель - Качество обслуживания ( QoS ). Он включает все аспекты соединения, такие, как качество речи, задержка информации, потери, надежность и т.д. Мы рассматриваем только небольшое подмножество этих аспектов: Уровень обслуживания ( GoS ) или сетевые рабочие характеристики включают аспекты, связанные только с емкостью сети.
После публикации формулы Эрланга в 1920 были установлены функциональные отношения между числом каналов, предложенной нагрузкой и уровнем обслуживания (вероятностью блокировки). Таким образом, были установлены показатели по качеству обслуживания нагрузки. Тогда существовали прямые линии между всеми станциями в области Копенгагена по
Если зафиксировать значение потерь нагрузки от блокировки по всем направлениям, то применение В-формулы Эрланга для слежения за нагрузкой по направлениям было бы ограниченным.
Кай Мо (Kai Мое 1893-1949), который был главным инженером Копенгагенской Телефонной Компании, сделал некоторые количественные экономические оценки и издал несколько распоряжений, где он вводил критические соображения по связи коммерческих интересов и блокировок. Сегодня они известны, в математической экономике как принципы Мо. Самуэльсон (Р.А. Samuelson) позже привел подобные соображения в своей известной книге, первоначально изданной в 1947 г.
На основе работ Мо сформулированы фундаментальные принципы измерения нагрузки для телекоммуникационных системах как Принципы Мо (Jensen, 1950 [50]).
Для хорошей работы
Таблица 7.1 показывает предложенную нагрузку для фиксированной вероятности блокировки Е=1% при некоторых значениях п.
Таблица также дает удельное использование каналов, которое принимает более высокое значение для больших групп. Если мы увеличиваем предложенную нагрузку на 20 % до $$А_1 = 1,2А$$, то замечаем увеличение вероятности блокировки для всех значений $$n$$, но больше всего - для больших значений п.
Общая стоимость для данного числа каналов тогда: (а) стоимость кабеля и (б) убытки из-за потерянной нагрузки (упущенный доход):
$$C_n=g*AE_{1,n}(A)+c_0+c*n,$$Здесь - А предложенная нагрузка, то есть потенциальный запрос на обслуживание нагрузки в рассматриваемой группе. Затраты из-за потерянной нагрузки уменьшаются с увеличением я, тогда как расходы из-за кабеля увеличиваются с увеличением п. Общая стоимость может иметь минимум для некоторого значения п. Практически п - целое число, и мы ищем значение n, для которого имеем (см. рис.7.6):
$$C_{n-1} > C_n$$ и $$C_n \le C_{n+1}$$
| n | 1 | 2 | 5 | 10 | 20 | 50 | 100 |
|---|---|---|---|---|---|---|---|
$$F_{1,n}(A)$$ |
0.010 0.010 0.000 |
0.153 0.076 0.001 |
1.361 0.269 0.011 |
4.461 0.442 0.027 |
12.031 0.596 0.052 |
37.901 0.750 0.099 |
84.064 0.832 0.147 |
$$A_1=1.2*A$$
$$F_{1,n}(A_1)$$ |
0.012 1.198 0.012 0.000 |
0.183 1.396 0.090 0.002 |
1.633 1.903 0.320 0.023 |
5.353 2.575 0.522 0.072 |
14.437 3.640 0.696 0.173 |
45.482 5.848 0.856 0.405 |
100.877 8.077 0.927 0.617 |
| $$n$$ | 1 | 2 | 5 | 10 | 20 | 50 | 100 |
|---|---|---|---|---|---|---|---|
$$A(F_B=0.05)$$ $$a$$ $$E_{1,n}(A)[\%]$$ |
0.271 0.213 21.29 |
0.607 0.272 10.28 |
2.009 0.387 3.72 |
4.991 0.490 1.82 |
11.98 0.593 0.97 |
35.80 0.713 0.47 |
78.73 0.785 0.29 |
$$A_1=1.2*A$$
$$F_{1,n}(A_1)$$ |
0.325 24.51 0.245 0.067 |
0.728 13.30 0.316 0.074 |
2.411 6.32 0.452 0.093 |
5.989 4.28 0.573 0.120 |
14.38 3.55 0.693 0.169 |
42.96 3.73 0.827 0.294 |
94.476 4.62 0.901 0.452 |
(рис 7.6) Общая стоимость состоит из затрат на кабель и упущенного дохода из-за блокировок нагрузки (7.32). Минимум общей стоимости получается, когда выполняется неравенство (7.33), то есть когда две функции стоимости имеют тот же самый наклон с противоположными знаками (квант приращения). ( $$F_B = 0,35, А = 25 Эрл$$ ). Минимум получен для n = 30 каналов
При $$E_{1,n} (А) = Е_п(А) $$ мы имеем
$$A\{E_{n-1}(A)-E_n(A)\} > \frac cg \ge A\{E_n(A)-E_{n+1}(A)\},$$ $$F_{1,n-1}(A) > F_B \ge F_{1,n}(A),$$где
$$F_B=\frac cg=\frac{\mbox{ стоимость увеличения на канал }}{\mbox{ доход увеличения на канал }}$$$$F_B$$ называется значением выигрыша. Заметим, что $$c_0$$ не входит в условие минимума. Это значение определяет, выгодно ли передавать нагрузку вообще. Мы должны потребовать, что для некоторого положительного значения п выполняется неравенство:
$$g*A\{1-F_n(A)\} > c_0+c*n.$$Pис.7.7 показывает вероятности блокировки для некоторых значений $$F_B$$. Отметим, что экономический расчет на прибыль в некотором смысле заложен в значении выигрыша. Практически мы выбираем $$F_B$$ частично независимо от функции стоимости.
В Дании использовались следующие значения:
$$F_B = 0,35$$ для первичных групп каналов;
$$F_B = 0,20$$ для обслуживания резервных первичных групп. (7.37);
$$F_B = 0,05$$ для групп без альтернативного маршрута.
(рис 7.7) Случай, когда размерность вероятности блокировки нагрузки с фиксированным значением значения выигрыша $$F_B$$ для малых значений предложенной нагрузки становится большим (см. таблицу. 7.2)
Е, потери по вызовам В, и потери по нагрузке С.[i], как число занятых каналов i (i = 0; 1; 2,...). Все состояния системы показаны в виде окружностей и дуг от одного состояния до другого состояния, на которых приведены значения интенсивности.[i] равно числу переходов из состояния [i].Во многих случаях мы можем применять простую структуру диаграммы перехода состояния. Применим фиктивное сечение, например, между состоянием [i-1] и [i] (т.е. выделяем переходы от состояния [0]; [1].... [i-1]). Затем рассматриваем в статистическое равновесие нагрузки от состояния [i-1] к [i] и изменение от состояния [i] к [i-1]
{0; 1,... n}.Потери по времени: вероятность, что все п каналов заняты в случайный момент времени.
Потери по вызовам: вероятность, что случайный вызов будет потерян.
Потери по нагрузке: разность между предложенной и потерянной нагрузкой.
Для всех систем с Пуассоновскими потоками вызовов эти характеристики равны.
i - ый канал (использование $$a_{ij}$$ ), зависит от типа поиска.п до п + 1.n! увеличивается так быстро, что в компьютере возникает перегрузка, поэтому на практике применяется рекурсивная формула.QoS ). Он включает все аспекты соединения, такие, как качество речи, задержка информации, потери, надежность и т.д. Уровень обслуживания ( GoS ) или сетевые рабочие характеристики включают аспекты, связанные только с емкостью сети.В-формула Эрланга основана на модели, которая содержит три элемента: структура, стратегия и нагрузка (рис.1.1).
Стратегия. Вызов, достигая системы, принимается для обслуживания, если, по крайней мере, один канал свободен. Каждый вызов использует один и только один канал. Мы говорим, что группа имеет полную доступность. Часто используется термин полная готовность, но эта терминология будет использоваться только для случаев определения надежности соединения. Если все каналы заняты, система переполняется, и попытка вызова блокируется. Это блокированный вызов (отклоненный, потерянный) называется попыткой и исчезает из системы без всяких последствий. Последствия могли быть, если бы была принята стратегия с альтернативными маршрутами. Это стратегия - самая важная и применялась успешно много лет.
Она называется системой с потерями Эрланга или с явными потерями вызовов (LCC Lost Calls Cleared).
Определение предложенной нагрузки. Мы определяем предложенную нагрузку как нагрузку, которая поступает при бесконечном числе каналов (емкости) (2.2). В Эрланговской
Мы рассматриваем два случая:
Мы увидим позже, что эта модель нечувствительна к распределению времени пребывания в системе, то есть для вероятностей состояния важно только среднее время пребывания в системе. Тип распределения не имеет никакого значения для вероятностей состояния.
Критерии качества работы. Самые важные показатели уровня обслуживания для систем с потерями - потери по времени $$E$$, потери по вызовам $$B$$ и потери по нагрузке $$C$$. Все они равны между собой для PASTA - Poisson Arrival See Time Average, секция 6.3). Наиболее важные из этих свойств:
Мы предполагаем, что процесс поступления вызовов - Пуассоновский процесс, и что времена пребывания в системе имеет экспоненциальное распределение, то есть мы рассматриваем нагрузку PCT-I. Предполагается, что число каналов бесконечно, так что блокировка (перегрузка) отсутствует.
Мы определяем состояние системы $$[i] $$ как число занятых каналов $$i (i = 0,1,2, \dots) $$.
На рис.7.1 все состояния системы даны в виде окружностей и дуг от одного состояния до другого состояния, на которых показано значение интенсивности. Этот процесс простой (секция 5.1). Мы рассматриваем только переходы в соседние состояния.
(рис 7.1) Пуассоновское распределение. Диаграмма переходов состояний схематически изображает переходы для системы с бесконечным числом каналов, Пуассоновским потоком вызовов ( $$\lambda$$ ) и экспоненциально распределенными временами пребывания в системе ( $$\mu$$ ).
Если мы предполагаем, что система находится в статистическом равновесии, то система будет находиться в состоянии $$[i] $$ в течение определенного времени, пропорционального $$p(i) $$, где $$p(i) $$ - вероятность существования системы в состоянии $$[i] $$ в случайный момент времени. Когда процесс находится в состоянии $$[i] $$, он может перейти в следующий момент времени в состояние $$[i+1] \lambda$$ раз в единицу времени или в состояние $$[i-1] i \mu$$ раз в единицу времени. В момент перехода из состояния в состояние процесс покидает состояние $$[i] $$. Будущее развитие диаграммы состояний зависит только от существующего состояния, а не от того, как процесс прибыл в это состояние (Марковское свойство).
Уравнения, описывающие состояние системы, согласно предположению о статистическом равновесии могут быть получены двумя способами, которые основаны на принципе глобального равновесия.
а. Уравнения узла
В статистическом равновесии число переходов в состояние $$[i] $$ в единицу времени равно числу переходов из состояния $$[i] $$. Вероятность состояния равновесия $$р (i) $$ обозначает соотношение времени (отношение всего времени процесса к отношению в единицу времени), когда процесс находится в состоянии $$[i] $$. Среднее число переходов из состояния [0] в состояние [1] равно $$\lambda \times р(0) $$, в единицу времени, и среднее число переходов из состояния [1] в состояние $$[0] - \mu \times p(1) $$ в единицу времени. Для состояния $$[i] $$ мы получаем следующее равновесие или уравнение равновесия:
$$\lambda *p(0)=\mu *p(1), i=0,$$ $$\lambda *p(i-1)+(i+1) \mu * p(i+1)=(\lambda +i \mu)*p(i), I > 0.$$Уравнения узла также всегда применимы, для диаграмм перехода, где от одного состояния можно перейти в одно из нескольких состояний (несколько измерений), которые мы рассмотрим в более поздних лекциях.
б. Уравнения сечения
Во многих случаях мы можем применять простую структуру диаграммы перехода состояния. Применим фиктивное сечение, например, между состоянием $$[i-1] $$ и $$[i] $$ (т.е. выделяем переходы от состояния $$[0],[1], \dots , [i-1] $$ ). Затем рассматриваем статистическое равновесие нагрузки от состояния $$[i - 1] $$ к $$[i] $$ и изменение от состояния $$[i] $$ к $$[i-1] $$. В статистическом равновесии мы, таким образом, имеем в единицу времени:
$$\lambda *p(i-1)=i \mu * p(i), i=1,2, \dots$$Уравнения сечения, прежде всего, используются для одномерных диаграмм перехода состояния, тогда как уравнения узла применимы к любой диаграмме.
Так как система всегда будет в некотором состоянии, мы имеем нормализующее ограничение:
$$\sum_{i=0}^{\infty}p(i)=1, p(i) \ge 0.$$Можно заметить, что уравнения узла (7.3) включают три вероятности состояния, тогда как уравнения сечения (7.4) включают только две. Поэтому уравнения сечения решаются проще.
Для одномерной диаграммы перехода состояний в большинстве случаев применяют подход на основе метода сечений. Из рис.7.1 мы получаем следующие уравнения равновесия:
$$\lambda * p(0)= \mu *p(1),\\ \lambda *p(1)=2 \mu *p(2),\\ \dots \dots\\ \lambda * p(i-1)=i\mu *p(i),\\ \lambda * p(i)=(i+1)\mu *p(i+1).$$Используя выражение $$p(0) $$ и обозначая $$А= \lambda / \mu,$$ получаем
$$p(0)=p(0),\\ p(1)=A*p(0),\\ p(2)=\frac{A}{2}*p(1)=\frac{A^2}{2}*p(0),\\ \dots \dots \dots\\ p(i-1)=\frac{A}{i-1}*p(i-2)=\frac{A^{i-1}}{(i-1)!}*p(o),\\ p(i)=\fracAi*p(i-1)=\frac{A^i}{i!}*p(0),\\ p(i+1)=\frac{A}{i+1}*p(i)=\frac{A^{i+1}}{(i+1)!}*p(0),\\ \dots \dots \dots$$Из ограничения нормализации получаем $$р(0) $$:
$$1=\sum_{j=0}^{\infty}p(j)\\\ =p(0)*\left \{1+A+\frac{A^2}{2!}+ \dots + \frac{A^i}{i!} + \dots \right \}\\ =p(0)*e^A,\\ p(0)=e^{-A},$$Это
Число занятых каналов в случайный момент времени подчиняется
С точки зрения измерения нагрузки, система с бесконечным числом линий не очень интересна. Просмотрим важные характеристики нагрузки
Потери по времени $$E=0$$
Потери по вызовам $$B=0$$
Обслуженная нагрузка $$Y=\sum_{i=0}^{\infty}i*p(i)=A$$,
Потерянная нагрузка $$A_l=A-Y=0$$,
Потери по нагрузке $$C=0$$
Нагрузка, которая обслужена $$i$$ -той линией, принимающей последовательную нагрузку, дается позже в (7.14).
Пиковость Z определяется как отношение между дисперсией и средней величиной распределения вероятностей состояния.
Для
Пиковость имеет размерность [число каналов] и отличается от коэффициента вариации, который не имеет никакого измерения (3.9).
Продолжительность состояния [i]
В состоянии $$[i] $$ процесс имеет полную интенсивность $$(\lambda + I \mu) $$. Поэтому время до первого перехода (переход из состояния $$i$$ либо к $$i+1$$, либо к $$i-1$$ ) - распределено по экспоненте (секция 4.1.1):
$$f_i(t)=(\lambda + i \mu)e^{-(\lambda + I \mu)t}, t \ge 0.$$В примере 6.2.2 мы рассматривали протокол синхронная (сегментированная) АЛОХАа, где оси времени были разделены на слоты времени. Мы теперь рассматриваем тот же самый протокол в непрерывное время. Предположим, что пакеты прибывают согласно Пуассоновскому процессу и что они имеют постоянную длину $$h$$. Система соответствует случаю нагрузки, заканчивающемуся Пуассоновским распределением, которое также является справедливым для постоянных времен занятия (секция 7.2). Вероятности состояния отображаются Пуассоновским распределением (7.6), где $$A = \lambda h$$. Пакет передается правильно, если: (а) система находится в состоянии [0] во время прибытия и (б) никакие другие пакеты не поступают в течение времени обслуживания $$h$$. Мы находим:
$$P_{correct} =р(0)-е^{-\lambda h}=е^{-2A}.$$Переданная правильно нагрузка, таким образом, получается:
$$A_{correct}=A*p_{rcorrect}=A*e^{-2A}.$$Это - соотношение оси времени, при эффективном использовании оно имеет оптимум для $$h = А = 1/2$$, где производная относительно $$А$$ равняется нулю:
$$\frac{\partial A_{correct}}{\partial A}=e^{-2A}*(1-2A),\\ max\{A_{correct}\}=\frac{1}{2e}=0.1839$$Мы, таким образом, получаем, что максимальное использование равно 0.1839, когда предложение равно 0.5 Эрл. Это - половина значения, которое мы получили для системы, использующей слоты в синхронных спутниковых передатчиках. Сравнение различных моделей АЛОХА уже было сделано на рис.6.4.
Мы рассматриваем вариант, когда Чистая Случайная Нагрузка I (PCT-I) такая же, как в секции 7.2. Число каналов теперь ограничено и я конечно. Число состояния становится $$n+1$$, диаграмма Чистая Случайная Нагрузка I при переходе состояний показана на рис.7.2.
(рис 7.2) Усеченное Пуассоновское распределение..Диаграмма переходов состояний схематически изображает систему с ограниченным числом каналов $$(n) $$, Пуассоновский поток вызовов $$(\lambda) $$ и экспоненциальное время обслуживания $$(\mu) $$ )
Мы получаем уравнения сечения, как и в случае Пуассоновского процесса, но пространство состояний ограничено $$\{0, 1, \dots , п) $$ и условие нормализации (7.5) теперь равно:
$$p(0)=\left \{ \sum_{j=0}^n \frac{A^j}{j!} \right\}^{-1}$$Мы получаем так называемое усеченное Пуассоновское распределение (первая формула Эрланга):
$$p(i)=\frac{\frac{A^i}{i!}}{\sum_{j=0}^n \frac{A^j}{j!}}, 0 \le i \le n.$$Название усеченное означает "укороченное" вследствие того, что решение может интерпретироваться как усеченное
Зная вероятности состояния, мы можем найти критерии качества работы, определяемые этими вероятностями состояния.
Потери по времени
Вероятность, что все $$п$$ каналов заняты в случайный момент времени, равна отношению всего времени работы ко времени занятости всех каналов (математическое ожидание времени). Это видно из (7.9) для $$i=n$$:
$$E_n(A)=p(n)=\frac{\frac{A^n}{n!}}{1+A+\frac{A^2}{2!}+\dots +\frac{A^n}{n!}}.$$Это - известная В-формула Эрланга (1917, [11]). Она обозначается $$Е_n (А) = Е_{1,п} (А) $$, где указатель "1" рассматривается как указатель названия первая формула Эрланга.
Потери по вызовам
Вероятность, что случайный вызов будет потерян, равна отношению всех попыток вызовов к числу блокированных попыток вызова. Если мы рассматриваем единицу времени, то находим $$В = В_n (А) $$:
$$B=\frac{\lambda * p(n)}{\sum_{v=0}^n} \lambda * p(v)=p(n)=E_n(A)$$Обслуженная нагрузка
Если мы используем усеченное уравнение между состоянием $$[i-1] $$, и $$[i] $$, то получим:
$$Y=\sum_{i=1}^n i*p(i)=\sum_{i=1}^n \frac{\lambda}{\mu}*p(i-1)=A*\{1-p(n)\},\\ Y=A*\{1-E_n(A)\},$$где А - предложенная нагрузка. Обслуженная нагрузка будет меньше и чем А, и чем п.
Потери по нагрузке
$$A_l=A- Y=A-E_nA).\\ C=\frac{A-Y}{A}=E_n(A).$$Мы, таким образом, имеем Е=В=С, потому что интенсивность вызова не зависит от состояния. Это свойство - PASTA (Poisson Arrivals See Time Averages - Пуассоновское поступление вызовов, наблюдаемое за среднее время) - справедливо для всех систем с Пуассоновскими потоками вызовов. Во всех других вариантах, по крайней мере, два из трех случаев потерь различны. В-формула Эрланга показана графически на рис. 7.3 для некоторых выбранных значений параметров.
Нагрузка, которую обслуживает i -ый канал (использование $$а_{ij}$$ )
Случайный поиск. В этом случае все каналы в среднем обслуживают одну и ту же нагрузку. Полная обслуженная нагрузка не зависит от стратегии поиска, и мы можем найти использование:
(рис 7.3) Вероятность блокировки $$Е_n(А) $$ как
Эта функция показана на рис. 7.4, и мы наблюдаем, что в данном случае при потерях Е получается самое высокое использование для больших групп канала (экономия из-за масштаба).
(рис 7.4) Среднее удельное использование а (7.13) как функция числа каналов n для заданных значений потерь Е Обусловленный поиск - последовательный поиск: нагрузка, которую обслуживает канал, есть разность между нагрузкой, потерянной i-1 каналами, и нагрузкой, потерянной i каналами:
Отметим, что нагрузка, которую обслуживает канал i, не зависит от общего числа каналов. Таким образом, каналы после i -того канала не влияют на нагрузку, обслуживаемую каналом i, т.е. между каналами нет никакой обратной связи.
Функция увеличения
Она обозначает увеличение обслуженной нагрузки, когда число каналов увеличено на один от n до n + 1:
Мы имеем $$0 \le F_n(A) \le 1$$..
Функция увеличения Fn (А) сведена в таблицу (Арн Дженсен, 1950 [50]) и показана на рис.7.5. В секции 7.6.2 мы рассматриваем приложение этого принципа для оптимального экономичного измерения нагрузки.
Пиковость
Она определяется как отношение между дисперсией и средней величиной распределения числа занятых каналов, сравните с IDC (Индексрассеяния для расчетов - Index of
Размерность - [число каналов]. В группе с обусловленным поиском мы можем таким образом оценить пиковость нагрузки, которую обслуживает последний канал.
(рис 7.5) Функция увеличения $$F_n (A) $$ (7.16) по В формуле Эрланга. $$F_n (А) $$ при
Продолжительность состояния [i]
Полная интенсивность для перехода из состояния $$[i] $$ постоянна и равна $$(\lambda + i \mu) $$, и поэтому продолжительность времени в состоянии $$[i] $$ (время пребывания) экспоненциально распределена с функцией плотности:
$$f_i(t)=(\lambda + I \mu)*e^{-(\lambda + i \mu)t}, 0 \le I < n,\\ f_n(t)=(n \mu)* e^{-(n \mu)t}, i=n$$Самый важный инструмент в теории телетрафика - формулировка и решение задач с помощью моделей, посредством применения диаграмм перехода состояния. Из предыдущих секций мы можем установить следующую стандартную процедуру для того, чтобы применить диаграмму перехода состояния. Она состоит из множества шагов и может быть сформулирована в общих терминах. Эта процедура также применима для
Процедура всегда проходит следующие шаги.
Созданием диаграммы перехода состояния:
Этим способом мы получаем законченную диаграмму перехода состояния.
Составить уравнения, описывающие систему.
Если условия для статистического равновесия выполнены, уравнения устойчивости состояний могут быть получены из:
Решить уравнения равновесия, отображающие статистическое равновесие.
На практике мы находим ненормализованное значение вероятности состояния $$q(0) $$, равное единице, а затем вычисляем относительную величину $$q(i), (i= 1, 2 \dots ) $$. Нормализуя ее, находим:
$$p(i)=\frac{q(i)}{Q_n}, i=0,1, \dots , n,$$где
$$Q_n=\sum_{v=0}^n q(v).$$Тогда потери по времени получаются равными:
$$p(n)=\frac{q(n)}{Q_n}=1-\frac{Q_{n-1}}{Q_n}$$Если значения $$q(i) $$ становятся очень большими (например, $$10^{10}$$ ), то мы можем умножить все $$q (i) $$ на одну и ту константу (например, $$10^{-10}$$ ), так как мы знаем, что все значения вероятностей находятся в пределах интервала [0, 1]. Этим способом мы избегаем проблем вычисления. Если значения $$q(i) $$ становятся очень маленькими, мы можем усечь пространство состояний, так как плотность распределения $$p(i) $$ часто имеет колоколоо-бразный вид $$a$$ (unimodal - "унимодальный") и поэтому имеет максимум. Во многих случаях мы, теоретически, способны контролировать ошибку, вносимую усечением пространства состояний (Степанов, 1989 [94]).
Мы можем нормализовать вероятности состояний после каждого шага, который требует больших вычислений, но гарантирует высокую точность. Нормализуем вероятности состояний для системы с $$х-1$$ каналами:
$$P_{x-1}=\{p_{x-1}(x-1), p_{x-1}(x-2), \dots, p_{x-1}(0)\}, x=1,2, \dots,$$где индекс $$(х-1) $$ указывает, что это вероятности состояния для системы с $$(х-1) $$ каналом. Предположим, что мы имеем следующую рекурсию для $$q_x(x) $$, заданную некоторой функцией от предыдущих вероятностей состояний:
$$q_x(x)=f\{p_{x-1}(x-1}, p_{x-1}(x-2), \dots, p_{x-1}(0)\}, x=1,2, \dots,$$где $$q_x(x) $$ будет относительной вероятностью состояния. Предположим, что мы знаем нормализованные вероятности состояний для $$(х-1) $$ каналов (7.22) и хотим найти нормализованные вероятности состояния для системы с $$х$$ каналами. Относительные значения вероятностей состояния не изменяются, когда мы увеличиваем число каналов на один, тогда получаем:
$$q_x(i)=\begin{cases} p_{x-1}, i=0,1,2,\dots, x-1,\\ f\{p_{x-1}(x-1}, p_{x-1}(x-2), \dots, p_{x-1}x(0)\}, i=x \end{cases}$$Новая константа нормализации получается:
$$Q_x=\sum_{i=0}^xq_x(i)=1+q_x(x),$$так как мы на предыдущем шаге нормализовали сумму вероятностей состояний в пределах от 0 к $$х-1$$, и, увеличивая их на единицу, получаем:
$$p_x(i)=\begin{cases} \frac{p_{x-1}(i)}{1+q_x(x)}, i=0,1,2, \dots, x-1,\\ \frac{q_x(x)}{1+q_x(x)}, i=x \end{cases}.$$В начале процесса рекурсии присваивается значение $$р_0(0)=1$$. Алгоритм рекурсии начинается с этого значения и находит вероятности состояния системы с одним каналом больше (7.24) и (7.25). Рекурсия в цифровой форме очень устойчива, потому что мы в (7.25) делим на число, большее единицы.
Рассмотрим простой процесс гибели и размножения с интенсивностью поступления $$\lambda_i$$ и скоростью выхода из состояния $$i \mu$$ в состоянии $$i$$. Тогда $$q_x(x) $$ зависит только от вероятности предыдущего состояния. Используя уравнение сечения, мы получаем следующую формулу рекурсии:
$$q_x(x)=\frac{\lambda_{x-1}}{x \mu}*p_{x-1}(x-1).$$Потери по времени для $$х$$ каналов - $$Е_x(А) = р_х(х) $$. Подставляя (7.26) в (7.25), получаем простую рекурсивную формулу для потерь по времени:
$$E_x=\frac{q_x(x)}{1+q_x(x)}=\frac{\frac{\lambda_{x-1}}{x \mu}*E_{x-1}}{1+\frac{\lambda_{x-1}}{x \mu}*E_{x-1}}, E_0=1$$Находя инверсию вероятности потерь по времени $$Iх = Е^{-1}$$, мы получаем:
$$I_x=1+\frac{x \mu}{\lambda_{x-1}}*I_{x-1}, I_0=1$$Это общая рекурсивная формула для вычисления потерь по времени для всех систем с интенсивностью поступления состояния $$\lambda_i$$ и однородными обслуживающими приборами.
Если мы хотим вычислить
Для вычислений формула (7.10) не является удобной: $$n$$! увеличивается так быстро, что в компьютере возникает перегрузка. Если мы применим (7.27), то получим рекурсивную формулу:
$$E_x(A)=\frac{A*E_{x-1}(A)}{x+A*E_{x-1}(A)}, E_0(A)=1$$С числовой точки зрения,
где $$I_n(А) = 1/Е_n(А) $$. Эта рекурсивная формула точна, и даже для больших значений $$(n, А) $$ нет ошибок округления. Это - основная формула для многочисленных таблиц В-формул Эрланга и так называемых классических таблиц (Пальма, 1947 [81] ). Для очень больших значений $$n$$ есть более эффективные алгоритмы. Заметим, что рекурсивная формула, которая является точной при увеличении индекса, обычно неточна при уменьшении индекса, и наоборот.
Мы рассматриваем Эрланговскую систему с потерями с $$n = 6$$ каналами, интенсивностью поступления вызовов $$\lambda = 2$$ в единицу времени и интенсивностью освобождения $$\mu = 1$$ в единицу времени отклонения так, чтобы предложенная нагрузка была $$А = 2$$ Эрл. Если мы обозначим ненормализованную вероятность относительного состояния $$q(i) $$, то получим диаграмму перехода состояния, которая схематически изображает значения, показанные в следующей таблице:
| $$i$$ | $$\lambda (i)$$ | $$\mu (i)$$ | $$q(i)$$ | $$p(i)$$ | $$i*p(i)$$ | $$\lambda (i)- p(i)$$ |
|---|---|---|---|---|---|---|
| 0 | 2 | 0 | 1.0000 | 0.1360 | 0.0000 | 0.2719 |
| 1 | 2 | 1 | 2.0000 | 0.2719 | 0.2719 | 0.5438 |
| 2 | 2 | 2 | 2.0000 | 0.2719 | 0.5438 | 0.5438 |
| 3 | 2 | 3 | 1.3333 | 0.1813 | 0.5438 | 0.3625 |
| 4 | 2 | 4 | 0.6667 | 0.0906 | 0.3625 | 0.1813 |
| 5 | 2 | 5 | 0.2667 | 0.0363 | 0.1817 | 0.0725 |
| 6 | 2 | 6 | 0.0889 | 0.0121 | 0.0725 | 0.0242 |
| Total | 7.3556 | 1.0000 | 1.9758 | 2.0000 |
Мы получаем следующие вероятности блокировки:
Потери по времени $$Е_е(2) = р(6) = 0.0121$$.
Потери по нагрузке $$C_6(2)=\frac{A-Y}{A}=\frac{2-1.9758}{2}=0.0121$$.
Потери по вызовам $$B_6(2)=\frac{\{\lambda (6)*p(6)\}}{\left \{ \sum_{i-0}^6 \lambda (i)*p(i)\right \}}=\frac{0.0242}{2.0000}=0.0121$$.
Отметим, что $$Е = В = С$$ из-за свойства PASTA (Poisson Arrival See Time Average - Пуассоновское поступление вызовов, наблюдаемое за среднее время).
Применяя рекурсивную формулу (7.29), мы, конечно, получаем те же самые результаты
$$E-0(2)=1\\ E_1(2)=\frac{2*1}{1+2*1}=\frac 23,\\ E_2(2)=\frac{2*\frac 23}{2+2*\frac 23}=\frac 25,\\ E_3(2)=\frac{2*\frac 25}{3+2*\frac 25}=\frac{4}{19}\\ E_4(2)=\frac{2*\frac{2}{19}}{4+2*\frac{2}{19}}=\frac{2}{21},\\ E_5(2)=\frac{2*\frac{2}{21}}{5+2*\frac{2}{21}}=\frac{4}{109},\\ E_6(2)=\frac{2*\frac{4}{109}}{6+2*\frac{4}{109}}=\frac{4}{331}=0.121.$$Применяя рекурсию, (7.30) мы находим:
$$I_x(A)=1+\frac xA+\frac{x(x-1)}{A^2}+ \dots +\frac{x!}{A^x},$$Это выражение является обратной вероятностью блокировки В-формулы. При больших значениях х эта формула может быть применена для быстрого вычисления В-формулы, потому что мы можем ограничить сумму, когда ее элементы становятся очень маленькими.
Когда измеряется нагрузка системы обслуживания, необходимо обеспечить баланс требований уровня обслуживания и экономических ограничений. В этой лекции мы увидим, как это может быть сделано.
В системах телекоммуникации есть несколько показателей, которые характеризуют обслуживание. Самый объемный показатель - Качество обслуживания ( QoS ). Он включает все аспекты соединения, такие, как качество речи, задержка информации, потери, надежность и т.д. Мы рассматриваем только небольшое подмножество этих аспектов: Уровень обслуживания ( GoS ) или сетевые рабочие характеристики включают аспекты, связанные только с емкостью сети.
После публикации формулы Эрланга в 1920 были установлены функциональные отношения между числом каналов, предложенной нагрузкой и уровнем обслуживания (вероятностью блокировки). Таким образом, были установлены показатели по качеству обслуживания нагрузки. Тогда существовали прямые линии между всеми станциями в области Копенгагена по
Если зафиксировать значение потерь нагрузки от блокировки по всем направлениям, то применение В-формулы Эрланга для слежения за нагрузкой по направлениям было бы ограниченным.
Кай Мо (Kai Мое 1893-1949), который был главным инженером Копенгагенской Телефонной Компании, сделал некоторые количественные экономические оценки и издал несколько распоряжений, где он вводил критические соображения по связи коммерческих интересов и блокировок. Сегодня они известны, в математической экономике как принципы Мо. Самуэльсон (Р.А. Samuelson) позже привел подобные соображения в своей известной книге, первоначально изданной в 1947 г.
На основе работ Мо сформулированы фундаментальные принципы измерения нагрузки для телекоммуникационных системах как Принципы Мо (Jensen, 1950 [50]).
Для хорошей работы
Таблица 7.1 показывает предложенную нагрузку для фиксированной вероятности блокировки Е=1% при некоторых значениях п.
Таблица также дает удельное использование каналов, которое принимает более высокое значение для больших групп. Если мы увеличиваем предложенную нагрузку на 20 % до $$А_1 = 1,2А$$, то замечаем увеличение вероятности блокировки для всех значений $$n$$, но больше всего - для больших значений п.
Общая стоимость для данного числа каналов тогда: (а) стоимость кабеля и (б) убытки из-за потерянной нагрузки (упущенный доход):
$$C_n=g*AE_{1,n}(A)+c_0+c*n,$$Здесь - А предложенная нагрузка, то есть потенциальный запрос на обслуживание нагрузки в рассматриваемой группе. Затраты из-за потерянной нагрузки уменьшаются с увеличением я, тогда как расходы из-за кабеля увеличиваются с увеличением п. Общая стоимость может иметь минимум для некоторого значения п. Практически п - целое число, и мы ищем значение n, для которого имеем (см. рис.7.6):
$$C_{n-1} > C_n$$ и $$C_n \le C_{n+1}$$
| n | 1 | 2 | 5 | 10 | 20 | 50 | 100 |
|---|---|---|---|---|---|---|---|
$$F_{1,n}(A)$$ |
0.010 0.010 0.000 |
0.153 0.076 0.001 |
1.361 0.269 0.011 |
4.461 0.442 0.027 |
12.031 0.596 0.052 |
37.901 0.750 0.099 |
84.064 0.832 0.147 |
$$A_1=1.2*A$$
$$F_{1,n}(A_1)$$ |
0.012 1.198 0.012 0.000 |
0.183 1.396 0.090 0.002 |
1.633 1.903 0.320 0.023 |
5.353 2.575 0.522 0.072 |
14.437 3.640 0.696 0.173 |
45.482 5.848 0.856 0.405 |
100.877 8.077 0.927 0.617 |
| $$n$$ | 1 | 2 | 5 | 10 | 20 | 50 | 100 |
|---|---|---|---|---|---|---|---|
$$A(F_B=0.05)$$ $$a$$ $$E_{1,n}(A)[\%]$$ |
0.271 0.213 21.29 |
0.607 0.272 10.28 |
2.009 0.387 3.72 |
4.991 0.490 1.82 |
11.98 0.593 0.97 |
35.80 0.713 0.47 |
78.73 0.785 0.29 |
$$A_1=1.2*A$$
$$F_{1,n}(A_1)$$ |
0.325 24.51 0.245 0.067 |
0.728 13.30 0.316 0.074 |
2.411 6.32 0.452 0.093 |
5.989 4.28 0.573 0.120 |
14.38 3.55 0.693 0.169 |
42.96 3.73 0.827 0.294 |
94.476 4.62 0.901 0.452 |
(рис 7.6) Общая стоимость состоит из затрат на кабель и упущенного дохода из-за блокировок нагрузки (7.32). Минимум общей стоимости получается, когда выполняется неравенство (7.33), то есть когда две функции стоимости имеют тот же самый наклон с противоположными знаками (квант приращения). ( $$F_B = 0,35, А = 25 Эрл$$ ). Минимум получен для n = 30 каналов
При $$E_{1,n} (А) = Е_п(А) $$ мы имеем
$$A\{E_{n-1}(A)-E_n(A)\} > \frac cg \ge A\{E_n(A)-E_{n+1}(A)\},$$ $$F_{1,n-1}(A) > F_B \ge F_{1,n}(A),$$где
$$F_B=\frac cg=\frac{\mbox{ стоимость увеличения на канал }}{\mbox{ доход увеличения на канал }}$$$$F_B$$ называется значением выигрыша. Заметим, что $$c_0$$ не входит в условие минимума. Это значение определяет, выгодно ли передавать нагрузку вообще. Мы должны потребовать, что для некоторого положительного значения п выполняется неравенство:
$$g*A\{1-F_n(A)\} > c_0+c*n.$$Pис.7.7 показывает вероятности блокировки для некоторых значений $$F_B$$. Отметим, что экономический расчет на прибыль в некотором смысле заложен в значении выигрыша. Практически мы выбираем $$F_B$$ частично независимо от функции стоимости.
В Дании использовались следующие значения:
$$F_B = 0,35$$ для первичных групп каналов;
$$F_B = 0,20$$ для обслуживания резервных первичных групп. (7.37);
$$F_B = 0,05$$ для групп без альтернативного маршрута.
(рис 7.7) Случай, когда размерность вероятности блокировки нагрузки с фиксированным значением значения выигрыша $$F_B$$ для малых значений предложенной нагрузки становится большим (см. таблицу. 7.2)
Е, потери по вызовам В, и потери по нагрузке С.[i], как число занятых каналов i (i = 0; 1; 2,...). Все состояния системы показаны в виде окружностей и дуг от одного состояния до другого состояния, на которых приведены значения интенсивности.[i] равно числу переходов из состояния [i].Во многих случаях мы можем применять простую структуру диаграммы перехода состояния. Применим фиктивное сечение, например, между состоянием [i-1] и [i] (т.е. выделяем переходы от состояния [0]; [1].... [i-1]). Затем рассматриваем в статистическое равновесие нагрузки от состояния [i-1] к [i] и изменение от состояния [i] к [i-1]
{0; 1,... n}.Потери по времени: вероятность, что все п каналов заняты в случайный момент времени.
Потери по вызовам: вероятность, что случайный вызов будет потерян.
Потери по нагрузке: разность между предложенной и потерянной нагрузкой.
Для всех систем с Пуассоновскими потоками вызовов эти характеристики равны.
i - ый канал (использование $$a_{ij}$$ ), зависит от типа поиска.п до п + 1.n! увеличивается так быстро, что в компьютере возникает перегрузка, поэтому на практике применяется рекурсивная формула.QoS ). Он включает все аспекты соединения, такие, как качество речи, задержка информации, потери, надежность и т.д. Уровень обслуживания ( GoS ) или сетевые рабочие характеристики включают аспекты, связанные только с емкостью сети.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.