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

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

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

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

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

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

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

накопитель

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

Пакты поступают случайным образом со скоростью l в единицу времени. Они ожидают обслуживания в накопителе, и обслуживаются в соответствии с некоторой конкретной дисциплиной со средней скоростью m пакетов в единицу времени. На рисунке показана одна обслуживающая линия. В более же общем случае могут быть доступны несколько обслуживающих линий, и в этом случае одновременно могут обслуживаться несколько пакетов. В контексте сети передачи данных обслуживающая линия ¾ это средство передачи (исходящий канал или линия, передающие пакеты или, в случае систем с коммутацией каналов, обрабатывающие вызовы), которое передает данные с предписанной скоростью C блоков данных в единицу времени. Таким образом, процесс обслуживания определяется длиной пакета или продолжительностью соединения.

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

Для однолинейных систем обслуживания стабильность обеспечивается при l<m. Введём параметр r=l/m. Его называют коэффициентом использования канала или интенсивностью нагрузки. Когда r приближается к 1 или превышает её, возникает область перегрузки, и поступающие пакеты блокируются более часто.

Характеристики сети (время задержки, вероятность блокировки и т.д.) зависит также от вероятности состояний очереди. Для расчёта вероятностей состояния должны быть известны следующие характеристики:

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

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

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

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

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