Теоретическое исследование этих систем началось в семидесятые годы и было вызвано следующими практическими соображениями.

Рассмотрим, к примеру, одноканальную систему с несколькими типами вызовов. Допустим, что любой вызов (любого типа) требует обслуживания в течение единичного времени (скажем, время обслуживания равно 1 секунде). Предположим, что сервер находится на космической станции, все вызовы первого типа скапливаются в очереди где-то в Австралии, второго - в России, третьего - в Бразилии, и т.д. Наземная связь работает намного хуже, чем связь космическая. Упорядочить вызовы в каждой очереди можно, а упорядочивать поступление на сервер вызовов из разных очередей очень сложно, на это может теряться большое количество времени и средств. Поэтому на практике стали применять такой алгоритм:

• заранее каждой очереди указывается некоторое число (i-ой очереди - число p_i, где 0 < p_i < 1);
• в каждую единицу времени, первый вызов из первой очереди посылает сигнал на сервер с вероятностью p₁, первый вызов из второй очереди - с вероятностью p₂, и т.д., причем делают они это независимо один от другого (если некоторая очередь пуста, то из нее сигнала не поступает);
• если число полученных сервером сигналов равно единице (послан только один сигнал), то соответствующий вызов обслуживается и затем (через единицу времени) покидает систему;
• если число сигналов равно нулю, то сервер простаивает в течение единицы времени;
• если число сигналов не меньше двух, то они вступают в "конфликт", и сервер также простаивает в течение единицы времени.

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

Такого рода системы (и сети) получили название "системы множественного доступа" ("multi-access broadcast channel"). Часто в литературе термин "вызов" заменяют на "сообщение", а "обслуживание вызова" - на "передачу сообщения".

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

Предположим, что p₁ = p₂ = p. Если в некоторый момент одна очередь пуста, а другая - нет, то вероятность обслуживания за следующую единицу времени равна p. Если же обе очереди непусты, то обслуживание происходит в двух симметричных случаях, когда из одной очереди сигнал поступает, а из другой - нет. Так как сигналы подаются независимо, каждый из случаев осуществляется с вероятностью p(1-p). Следовательно, вероятность обслуживания равна 2p(1-p).

Пусть, как и в предыдущем параграфе, X_n⁽¹⁾ означает количество вызовов, поступающих за n-ую единицу времени в первую очередь, и X_n⁽²⁾ - во вторую. Предположим, что все случайные величины

Используя правило насыщения, можно предложить достаточные условия стабильности системы.

Теорема 4.1. Симметричная система множественного доступа с двумя очередями стабильна, если выполняется одно из двух:

• p і ¹/₂   и   2p(1-p) > 2a;
• 2a < p < ¹/₂.

Действительно, рассмотрим первый случай (во втором рассуждения аналогичны). Если система насыщена, то либо обе очереди непусты (и обслуживание происходит с вероятностью 2p(1-p)), либо одна пуста, а другая нет (и обслуживание происходит с вероятностью

Ясно, почему сформулированные в теореме 4.1 условия являются только достаточными для стабильности. Предположим, что система насыщена, и нам удалось посчитать, какую часть времени в течение длительного времени T обе очереди непусты (скажем, эта доля равна c). Тогда "средняя" интенсивность обслуживания за время T равняется c · 2p(1-p) +(1-c) · p, и "верное" условие стабильности есть

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

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

Пусть, например, в систему за единицу времени поступает X_n вызовов (где, как и ранее, случайные величины X₁, X₂, ј являются независимыми и одинаково распределенными, M(X₁) = a > 0), и в каждый момент времени n каждый из имеющихся вызовов посылает сигнал на станцию с вероятностью p_n (независимо от всех других). Будем рассматривать случай невырожденных случайных величин X_n, причем P(X₁ > 1) > 0. Набор вероятностей { p_n } естественно назвать "дисциплиной", или "алгоритмом" обслуживания.

Самый простой вариант - когда вероятности p_n от n не зависят и равны одному и тому же числу p < 1. Но в этом случае справедлива

Теорема 4.2. При любом выборе числа p система без очередей нестабильна!

Следовательно, надо брать числа p_n различными. Сформулируем следующий вопрос: можно ли задать заранее такую последовательность чисел p₁, p₂, ј, при которой система будет работать стабильно? "Заранее" означает, что при выборе этих чисел не может использоваться никакая информация о состоянии системы. Делалось много попыток ответить на этот вопрос; опубликован ряд статей, где показывается, что для различных классов последовательностей ответ всегда является отрицательным. Однако до сих пор не все случаи изучены, и вопрос остается открытым.

Допустим теперь, что в каждый момент времени известно общее число вызовов в системе (пусть Q_n - число вызовов в момент n), и можно использовать знание чисел Q₁, Q₂, ј, Q_n для определения вероятности p_n. Тогда имеет место следующая

Теорема 4.3. Если a < e ^-1, то существует алгоритм, при котором система стабильна. Если a і e ^-1, то таких алгоритмов нет.

Здесь e - основание натуральных логарифмов и e ^-1 = ¹/_e .

Доказательство этого утверждения также проводится с использованием правила насыщения. Предложим алгоритм вида

Отметим, что e ^-1 » 0,37. Как следует из теоремы 4.3, даже при оптимальном алгоритме сервер вынужден простаивать приблизительно 63 процента времени. Различными авторами рассматривались алгоритмы из более широкого класса (в частности, допускалась возможность вызову каждый раз при определении вероятности подачи сигнала учитывать, сколько раз он пытался подать сигнал до этого), что позволило поднять границу области стабильности с e ^-1 до 0,57.