G-сеть - G-network

Эта статья о математической модели. Стандарт беспроводной связи см. 802,11 г.

В теория массового обслуживания, дисциплина в рамках математической теория вероятности, а G-сеть (обобщенная сеть массового обслуживания^[1] или же Сеть Геленбе^[2]) - открытая сеть G-очередей, впервые введенная Эрол Геленбе как модель для систем массового обслуживания со специфическими функциями управления, такими как перенаправление трафика или уничтожение трафика, а также модель для нейронные сети.^[3] G-очередь - это сеть очередей с несколькими типами новых и полезных клиентов:

• положительный клиенты, которые прибывают из других очередей или поступают извне как прибытие Пуассона и подчиняются стандартным правилам обслуживания и маршрутизации, как и в традиционных сетевых моделях,
• отрицательный клиенты, которые прибывают из другой очереди или которые поступают извне как прибытие Пуассона, и удаляют (или «убивают») клиентов в непустой очереди, представляя необходимость удаления трафика, когда сеть перегружена, включая удаление «пакетов» "клиентов ^[4][5][6]
• "триггеры", которые поступают из других очередей или извне сети, и которые вытесняют клиентов и перемещают их в другие очереди

А решение формы продукта внешне похож на Теорема Джексона, но который требует решения системы нелинейных уравнений для потоков трафика, существует для стационарного распределения G-сетей, в то время как уравнения трафика G-сети на самом деле на удивление нелинейны, и модель не соблюдать частичный баланс. Это нарушило предыдущие предположения о том, что частичный баланс был необходимым условием для решения формы продукта. Сильным свойством G-сетей является то, что они являются универсальными аппроксиматорами для непрерывных и ограниченных функций, так что их можно использовать для аппроксимации довольно общего поведения ввода-вывода.^[7]

Определение

Сеть м взаимосвязанные очереди - это G-сеть если

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

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

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

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

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

${displaystyle ho _{i}={frac {lambda _{i}^{+}}{mu _{i}+lambda _{i}^{-}}}}$

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

${displaystyle lambda _{i}^{+}=sum _{j}ho _{j}mu _{j}p_{ji}^{+}+Lambda _{i},}$

(1)

${displaystyle lambda _{i}^{-}=sum _{j}ho _{j}mu _{j}p_{ji}^{-}+lambda _{i}.,}$

(2)

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

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

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

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

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

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

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

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

куда λ = λ⁺ + λ⁻ и ρ = λ⁺/(λ⁻ + μ), требуя ρ <1 для стабильности.

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

Рекомендации

1. Геленбе, Эрол (Сентябрь 1993 г.). «G-сети с инициированным движением клиентов». Журнал прикладной теории вероятностей. 30 (3): 742–748. Дои:10.2307/3214781. JSTOR  3214781.
2. Геленбе, Эрол; Фурно, Жан-Мишель (2002). «G-сети со сбросами». Оценка эффективности. 49 (1/4): 179–191. Дои:10.1016 / S0166-5316 (02) 00127-X.
3. Харрисон, Питер (2009). «Поворачивая время вспять - какое влияние на производительность?». Компьютерный журнал. 53 (6): 860–868. CiteSeerX  10.1.1.574.9535. Дои:10.1093 / comjnl / bxp021.
4. Геленбе, Эрол (1991). «Продуктовые сети массового обслуживания с отрицательными и положительными потребителями». Журнал прикладной теории вероятностей. 28 (3): 656–663. Дои:10.2307/3214499. JSTOR  3214499.
5. Геленбе, Эрол (1993). «G-сети с сигналами и пакетным удалением». Вероятность в технических и информационных науках. 7 (3): 335–342. Дои:10,1017 / с0269964800002953.
6. Арталехо, Дж. Р. (октябрь 2000 г.). «G-сети: универсальный подход для удаления работы в сетях массового обслуживания». Европейский журнал операционных исследований. 126 (2): 233–249. Дои:10.1016 / S0377-2217 (99) 00476-2.
7. Геленбе, Эрол; Мао, Чжи-Хун; Да Ли, Ян (1999). «Аппроксимация функций с помощью случайных сетей с пиками». IEEE-транзакции в нейронных сетях. 10 (1): 3–9. CiteSeerX  10.1.1.46.7710. Дои:10.1109/72.737488. PMID  18252498.
8. Харрисон, П.Г.; Пител Э. (1993). «Время пребывания в очередях на одном сервере с отрицательными клиентами». Журнал прикладной теории вероятностей. 30 (4): 943–963. Дои:10.2307/3214524. JSTOR  3214524.
9. Харрисон, Питер Г. Время отклика в G-сетях. 13-й Международный симпозиум по компьютерным и информационным наукам (ISCIS 1998). С. 9–16. ISBN  9051994052.