РАЗДЕЛ 2
МАТЕМАТИЧЕСКИЕ МОДЕЛИ КОМПЬЮТЕРНЫХ СЕТЕЙ С НЕОДНОРОДНЫМ ВХОДЯЩИМ ПОТОКОМ
2.1. Компьютерные сети, как системы массового обслуживания
Компьютерные сети (КС) созданы для решения совокупности задач обработки потоков заявок на обслуживание. Программы решения задач обслуживания хранятся в постоянной или оперативной памяти интеллектуального узла. Объем, структура и содержание задач из разных потоков - различны. Поэтому различны и программы, их обрабатывающие. Заявки, поступающие на вход сети, инициируются в порядке, определяемом процессами, происходящими в среде передачи компьютерной сети и в самом узле. Они генерируются в объектах источниках сети и поступают в узел-приемник периодически или в произвольные, случайные моменты времени. При этом за короткий отрезок времени может поступить несколько заявок , для обслуживания которых должны быть выполнены соответствующие программы узла обслуживания . При наличии одного процессора в узле обслуживания эти программы могут быть выполнены только последовательно, в связи с чем возникают очереди заявок на обслуживание. При наличии нескольких процессоров (например, в коммутаторах) очереди на обслуживание (заявка на передачу пакета в порт назначения может быть поставлена в очередь) формируются в связи с занятостью порта назначения [17].
Обработка заявок в КС организуется по схеме, показанной на рисунке 2.1. Заявки поступают в устройство прерывания, являющееся частью узла сети. При появлении заявки устройство прерывания инициирует в узле операцию прерывания, в результате выполнения которой узел переключается на выполнение программы приема и постановки заявок в очередь (программа "Диспетчер1").
Рис. 2.1 - Обработка заявок в узле КС
"Диспетчер 1" определяет тип поступившей заявки и ставит заявку в соответствующую очередь на обслуживание. Очередь в физическом отношении состоит из совокупности ячеек оперативной памяти, в которых размещаются коды поступивших заявок. В общем случае каждая из очередей содержит заявки, ожидающие обслуживания. Пусть в каждый момент времени узел может выполнять только одну программу обслуживания. Процесс выбора заявки из множества заявок, ожидающих обслуживания, называется диспетчированием.
Процедура диспетчирования реализуется программой, называемой "Диспетчер 2", которая анализирует состояние очередей , выбирает заявку , имеющую преимущественное право на обслуживание, и инициирует соответствующую прикладную программу . Считается, что в момент окончания работы программы обслуженная заявка покидает систему. По окончании программы управление вновь передается "Диспетчеру 2", который выбирает очередную заявку и инициирует соответствующую прикладную программу. Если очереди отсутствуют, "Диспетчер 2" переключает процессор в состояние ожидания.
Отметим важные особенности процесса функционирования компьютерной сети. Потоки заявок, поступающих в систему, являются случайными. Точно так же случайными для каждой заявки являются продолжительность ожидания начала обслуживания и длительность собственно обслуживания. Таким образом, весь процесс функционирования КС носит стохастический характер, что позволяет рассматривать такие системы как системы массового обслуживания (СМО) [7].
Анализ СМО может быть выполнен аналитически лишь при некоторых достаточно жестких предположениях относительно характера входящего потока и законов распределения продолжительности обслуживания.
Если входящий поток простейший, продолжительность обслуживания экспоненциальна, анализ может быть проведен с использованием теории марковских процессов [18-22]. При этом технология анализа в особенности проста, если потоки заявок однородны и, поэтому, их суперпозицию можно рассматривать как единый однородный входящий поток [23,24].
Пусть на вход -канальной системы с отказами (отсутствуют места для ожидания в очереди) поступает простейший входной поток с интенсивностью , а закон распределения продолжительности обслуживания имеет вид , где - интенсивность обслуживания, равная количественно среднему числу заявок, которое каждый канал системы в состоянии обслужить. В силу экспоненциальности случайной продолжительности обслуживания поток обслуженных заявок является стационарным и ординарным [25]. Поэтому , где - среднее время обслуживания.
Для достаточно малого в силу ординарности потоков заявок и обслуживаний имеем
Здесь
- вероятность поступления ровно заявок в течение интервала времени продолжительности ,
- вероятность, обслуживания ровно заявок в течении интервала времени продолжительности .
С учетом этих соотношений рассчитаем вероятности переходов системы :
Введем интенсивность перехода процесса из -го состояния в -е
.
Тогда
Система дифференциальных уравнений Колмогорова А.Н. для вероятностей состояний имеет вид:
Эту систему уравнений необходимо дополнить условием нормировки . Для решения системы можно использовать преобразование Лапласа [26].
При этом получим следующую систему линейных алгебраических уравнений:
Решив эту систему уравнений обычным образом [27,28] и выполнив обратное преобразование Лапласа, получим соотношения для .
Для оценки эффективности СМО интерес представляет асимптотическое поведение системы при . В этом случае, как можно показать [29], процесс в системе приобретает установившийся характер и поэтому . Тогда дифференциальные уравнения для вероятностей состояний системы упрощаются к виду:
Введем новую переменную . Тогда полученная система уравнений преобразуется к виду:
,
откуда, как легко видеть,
.
Тогда
.
Из этого уравнения следует рекуррентное соотношение используя которое, получим,
.
Таким образом, вероятности всех состояний выражены через . Для расчета используем условие нормировки. При этом
,
откуда
.
Введем параметр , называемый приведенной интенсивностью входного потока.