Теоретические основы современных информационных сетей. Теория очередей

Такие параметры, как число и длина пакетов, поступающих в сеть или проходящих через неё в любой момент времени, число вызовов, поступающих на вход сети за заданное время, продолжительность занятия (ресурса) - в общем случае подвержены статистическим изменениям. Поэтому для изучения их воздействия на сеть и получения соответствующих количественных характеристик должны применяться вероятностные методы.

Ключевую роль в анализе сетей играет теория очередей (называемая также теорией массового обслуживания)

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

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

Рассмотрим простейшую модель обслуживания:

В качестве пакетов будем рассматривать пакеты данных для случая коммутации пакетов или вызовы для систем с коммутацией каналов.

Пакты поступают случайным образом со скоростью λ в единицу времени. Они ожидают обслуживания в накопителе, и обслуживаются в соответствии с некоторой конкретной дисциплиной со средней скоростью μ пакетов в единицу времени. На рисунке показана одна обслуживающая линия - это средство передачи (исходящий канал или линия, передающие пакеты или, в случае систем с коммутацией каналов, обрабатывающие вызовы), которое передает данные с предписанной скоростью С блоков данных в единицу времени. В более же общем случае могут быть доступны несколько обслуживающих линий, и в этом случае одновременно могут обслуживаться несколько пакетов. Длительность процесса обслуживания определяется длиной пакета или продолжительностью соединения.

Если интенсивность поступления λ приближается к скорости обработки пакетов μ, очередь начинает расти. При накопителе конечной ёмкости очередь достигает наибольшей допустимой величины, а при переполнении накопителя поступление всех последующих пакетов будет заблокировано.

Для однолинейных систем обслуживания стабильность обеспечивается при λ≤μ. Введём параметр ρ = λ/μ. Его называют коэффициентом использования канала или интенсивностью нагрузки. Когда ρ приближается к 1 или превышает её, возникает область перегрузки, и поступающие пакеты блокируются более часто. Характеристики сети (время задержки, вероятность блокировки и т.д.) зависят также от вероятности состояний очереди. Для расчёта вероятностей состояния должны быть известны следующие характеристики:

· процесс поступления пакетов (статистика входящих потоков);

· распределение длин пакетов (распределение времени обслуживания);

· дисциплина обслуживания (FIFO, некоторые дисциплины обслуживания с приоритетами).

Для многолинейных систем вероятности состояний зависят также от числа обслуживающих линий.

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

Пуассоновский процесс

Рассмотрим бесконечно малый промежуток времени Δ t (Δt → 0), проходящий между моментами t и t+Δt. При определении пуассоновского процесса используются три основные предпосылки:

1. вероятность одного поступления в течение времени Δt определяется в виде: λΔt+О(Δt), где О(Δt) - члены более высокого порядка, которыми мы можем пренебречь при Δt→0;

2. вероятность нулевого поступления в течение времени Δt равна 1-λΔt;

3. поступление - без последействия (без памяти), т.е. поступление в течение Δt не зависит от предыдущих поступлений.

Если теперь рассмотреть большой промежуток времени Т, то вероятность p(k) того, что в промежутке Т произойдут k поступлений, равна:

,

где k = 0, 1, 2, …

Это равенство называется распределением Пуассона.

Процесс обслуживания является полным аналогом процесса поступления и обладает всеми свойствами последнего. На основании этого вероятность завершения обслуживания в малом промежутке времени (t, t+Δt) в точности равна μ Δt + О(Δt), а вероятность незавершения обслуживания в промежутке (t, t+Δt) равна 1-μ Δt+О(Δt) независимо от предыдущих или последующих завершений.

Ещё одно полезное свойство, объединяющее одну из причин, по которой Пуассоновский процесс часто используется для моделирования входящих потоков, заключается в том, что при объединении m независимых Пуассоновских потоков с произвольными интенсивностями λ₁, λ₂, … λ_m, объединённый поток также будет Пуассоновским с интенсивностью

.

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