Сеть потерь

В теории массового обслуживания сеть с потерями — это стохастическая модель телефонной сети , в которой вызовы маршрутизируются по сети между узлами. Каналы между узлами имеют ограниченную пропускную способность, поэтому некоторые поступающие вызовы могут не найти доступного маршрута к месту назначения. Эти вызовы теряются из сети, отсюда и название сети потери.

Сеть потерь была впервые изучена Эрланом для одной телефонной линии. Фрэнк Келли был удостоен премии Фредерика Ланчестера. для его статьи «Сети потерь» 1991 года. где он продемонстрировал, что поведение сетей с потерями может проявлять гистерезис .

Модель

Фиксированная маршрутизация

Рассмотрим сеть с J звеньями, помеченными 1, 2, …, J , и каждая ссылка j имеет C _j цепей . Пусть R — это набор всех возможных маршрутов в сети (комбинации каналов, которые может использовать вызов), и для каждого маршрута r запишите A _jr для количества каналов, которые маршрут r использует на канале j ( A следовательно, — это J x | R | матрица). Рассмотрим случай, когда все элементы A равны 0 или 1 и для каждого маршрута r вызовы, требующие использования этого маршрута, поступают в соответствии с процессом Пуассона со скоростью v _r . При поступлении вызова, если на всех необходимых каналах остается достаточная пропускная способность, вызов принимается и занимает сеть в течение экспоненциально распределенного периода времени с параметром 1. Если на каком-либо отдельном канале недостаточно мощности для принятия вызова, он отклоняется. (потеряно) из сети.

Запишите n _r ( t ) для количества вызовов по маршруту r , выполняющихся в момент времени t , n ( t ) для вектора ( n _r ( t ): r в R ) и C = ( C ₁ , C ₂ , .. , Си _Джей ). Тогда марковский процесс n ( t ) с непрерывным временем имеет единственное стационарное распределение

$\pi (n)=G(C)^{-1}\prod _{r\in R}{\frac {v_{r}^{n_{r}}}{n_{r}!}}{\text{ for }}n\in S(C)$

где

$S(C)=\{n\in \mathbb {Z} _{+}^{R}:An\leq C\}$

и

$G(C)=\left(\sum _{n\in S(C)}\prod _{r\in R}{\frac {v_{r}^{n_{r}}}{n_{r}!}}\right).$

На основании этого результата можно рассчитать вероятности потери вызовов, поступающих по разным маршрутам, путем суммирования по соответствующим состояниям.

Вычисление вероятностей потерь

Существуют общие алгоритмы расчета вероятностей потерь в сетях с потерями.

1. Аппроксимация Эрланга с фиксированной точкой
2. Метод среза
3. метод среза по 3 точкам