G-сеть

Эта статья о математической модели. Информацию о стандарте беспроводной связи см. в 802.11g .

В теории массового обслуживания — дисциплине математической теории вероятностей — G-сети ( обобщённая сеть массового обслуживания , часто называют сетью Геленбе ) — открытая сеть G-очередей, впервые представленная Эролом Геленбе как модель систем массового обслуживания со специфическими функциями управления, такими как перемаршрутизация или уничтожение трафика, а также модель для нейронных сетей . G-очередь — это сеть очередей с несколькими типами новых и полезных клиентов:

• положительные клиенты, которые поступают из других очередей или поступают извне как поступления Пуассона и подчиняются стандартным правилам обслуживания и маршрутизации, как в традиционных сетевых моделях,
• отрицательные запросы, которые поступают из другой очереди или которые поступают извне как поступления Пуассона, и удаляют (или «убивают») запросы в непустой очереди, что представляет собой необходимость удаления трафика, когда сеть перегружена, включая удаление « партии" клиентов</ref>
• «триггеры», которые поступают из других очередей или извне сети и которые вытесняют клиентов и перемещают их в другие очереди.

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

Определение

Сеть из m взаимосвязанных очередей называется G-сетью, если

1. каждая очередь имеет один сервер, который обслуживает со скоростью µ _i ,
2. внешние поступления положительных требований или триггеров или сбросов формируют пуассоновские процессы скорости $\scriptstyle {\Lambda _{i}}$ для положительных клиентов, тогда как триггеры и сбросы, включая отрицательных клиентов, образуют процесс скорости Пуассона $\scriptstyle {\lambda _{i}}$,
3. после завершения обслуживания клиент переходит из очереди i в очередь j как положительный клиент с вероятностью $\scriptstyle {p_{ij}^{+}}$, как триггер или сброс с вероятностью $\scriptstyle {p_{ij}^{-}}$ и покидает сеть с вероятностью $\scriptstyle {d_{i}}$,
4. по прибытии в очередь положительный клиент действует как обычно и увеличивает длину очереди на 1,
5. по прибытии в очередь отрицательный клиент уменьшает длину очереди на некоторое случайное число (если в очереди присутствует хотя бы один положительный клиент), в то время как триггер вероятностно перемещает клиента в другую очередь, а сброс устанавливает состояние очереди в ее устойчивое состояние, если очередь пуста, когда приходит сброс. Все триггеры, негативные запросы и сбросы исчезают после того, как они предприняли свои действия, так что они фактически являются «управляющими» сигналами в сети.

• Обратите внимание, что обычные клиенты, покидающие очередь, могут стать триггерами или сбросами и отрицательными клиентами при посещении следующей очереди.

Очередь в такой сети называется G-очередью .

Стационарное распределение

Определите загрузку на каждом узле,

$\rho _{i}={\frac {\lambda _{i}^{+}}{\mu _{i}+\lambda _{i}^{-}}}$

где $\scriptstyle {\lambda _{i}^{+},\lambda _{i}^{-}}$ для $\scriptstyle {i=1,\ldots ,m}$ удовлетворить

$\lambda _{i}^{+}=\sum _{j}\rho _{j}\mu _{j}p_{ji}^{+}+\Lambda _{i}\,$ ( 1 )

$\lambda _{i}^{-}=\sum _{j}\rho _{j}\mu _{j}p_{ji}^{-}+\lambda _{i}.\,$ ( 2 )

Затем записываем ( n ₁ , ... , n _m ) для состояния сети (с длиной очереди n _i в узле i ), если единственное неотрицательное решение $\scriptstyle {(\lambda _{i}^{+},\lambda _{i}^{-})}$ существует для приведенных выше уравнений ( 1 ) и ( 2 ) такой, что ρ _i для всех i, то существует стационарное распределение вероятностей π, которое определяется выражением

$\pi (n_{1},n_{2},\ldots ,n_{m})=\prod _{i=1}^{m}(1-\rho _{i})\rho _{i}^{n_{i}}.$

Доказательство

Достаточно показать $\pi$ удовлетворяет уравнениям глобального баланса , которые, в отличие от сетей Джексона, являются нелинейными. Отметим, что модель также допускает несколько классов.

G-сети использовались в широком спектре приложений, в том числе для представления сетей регулирования генов, сочетания управления и полезной нагрузки в пакетных сетях, нейронных сетях, а также для представления цветных изображений и медицинских изображений, таких как магнитно-резонансные изображения.

Распределение времени отклика

Время ответа — это время, которое клиент проводит в системе. Распределение времени ответа для одной G-очереди известно. где клиенты обслуживаются с использованием дисциплины FCFS со скоростью μ , с положительными поступлениями со скоростью λ. ⁺ и отрицательные поступления со скоростью λ ⁻ которые убивают клиентов с конца очереди. Преобразование Лапласа распределения времени отклика в этой ситуации имеет вид

$W^{\ast }(s)={\frac {\mu (1-\rho )}{\lambda ^{+}}}{\frac {s+\lambda +\mu (1-\rho )-{\sqrt {[s+\lambda +\mu (1-\rho )]^{2}-4\lambda ^{+}\lambda ^{-}}}}{\lambda ^{-}-\lambda ^{+}-\mu (1-\rho )-s+{\sqrt {[s+\lambda +\mu (1-\rho )]^{2}-4\lambda ^{+}\lambda ^{-}}}}}$

где λ = λ ⁺ + л ⁻ и ρ = λ ⁺ /( л ⁻ + µ ), требующий ρ <1 для устойчивости.

Время отклика для тандемной пары G-очередей (когда клиенты, закончившие обслуживание на первом узле, немедленно переходят на второй, а затем покидают сеть) также известно, и считается, что расширение на более крупные сети будет невозможным.