Лекция 11. Стохастические модели компьютерных сетей

Стохастический характер поступления данных и детерминированная обработка их в каналах связи и узлах коммутации предопределяет использование моделей теории МО для анализа и проектирования компьютерных сетей. Однако следует отметить, что исследование компьютерной сети в целом или отдельных протоколов (например, сквозных) с помощью простейших однофазных или двухфазных моделей МО (концепция «черного ящика»), характерных для подходов, позволяет дать лишь некоторое качественное представление о характере протекания информационных процессов, так как не учитывает сложного взаимодействия устройств и процессов в компьютерной сети. В тоже время указанные процессы естественно отображаются в моделях сетей МО, которые нашли широкое применение для анализа компьютерных сетей.

Модели сетей МО применяются для анализа характеристик протоколов практически всех уровней (в первую очередь второго, третьего и четвертого). На канальном уровне эти модели используются для определения эффективной скорости передачи данных. При анализе сквозных протоколов модели теории сетей МО позволяют находить межконцевую задержку сообщений (пакетов), определять параметры управления потоками и т.д. Сетевые модели отдельных компонент компьютерной сети адекватно отражают многоэтапный процесс обработки сообщений (пакетов) в этих устройствах, позволяя не только рассчитывать характеристики, но и осуществлять выбор различных параметров, например объемов буферной памяти узлов коммутации. Сложную структуру отдельных узлов необходимо учитывать и при расчете базовой сети передачи данных в целом. В тоже время необходимость решения оптимизационных задач (выбор топологии и пропускных способностей каналов связи, отыскание оптимальных маршрутов и т.д.) требует применения упрощенных моделей сетей МО, позволяющих находить явный вид целевой функции, в качестве которой используется время задержки сообщений (пакетов). Такой упрощенный подход требует дальнейшего уточнения характеристик сети с помощью более реальных моделей, учитывающих особенности сетевых протоколов. Это приводит к итерационной процедуре проектирования компьютерных сетей. Рассмотрены модели сетей МО, позволяющее осуществлять оценку эффективности и оптимизацию механизма глобального и локального управления потоками, основанного на пороговых ограничениях (использовании механизма окна) и распределении ресурсов (в основном буферов).

Предположением, необходимым для возможности использования аналитических моделей сетей МО, является предположение о независимости, суть которого состоит в том, что времена передачи сообщений (пакета) по разным каналам связи предполагаются независимыми случайными величинами. В то же время, очевидно, что длительности обслуживания сообщения в разных каналах пропорциональны длине этого сообщения и, следовательно, зависимы. Дополнительные зависимости вносятся процессами сборки и разборки сообщений на пакеты. Тем не менее, многочисленные сравнения результатов аналитического моделирования с помощью сетей МО и результатов имитационного моделирования или измерений на реальных сетях показали, что постулирование независимости не вносит существенных погрешностей. Указанный факт объясняется следующими причинами: 1) нарушением корреляции между длительностями обслуживания и длинами сообщений (пакетов) из-за восстановления после ошибок (например, на канальном уровне); 2) объединением различных независимых входящих потоков в одном исходящем канале; 3) использованием в основном средних характеристик, которые менее чувствительны к описанной выше зависимости.

При применении теории сетей МО для анализа характеристик компьютерных сетей различные устройства и процессы обычно моделируются четырьмя типами центров обслуживания. Центр типа 1. Обслуживание сообщений в центре осуществляется с дисциплиной FCFS (FIFO). Длительность обслуживания сообщений всех классов имеет одно и то же экспоненциальное распределение с интенсивностью m_I(n_i), i- номер данного центра в сети, i=1,M, зависящий от числа сообщений в центре n_i. Состояние n_i центра определяется вектором n_i1,n_i2,…,n_ini, где n_ij - номер класса сообщения, стоящего j -м в очереди (j = 1,n_i, n_ij = 1,R). Центр типа 2. Обслуживание сообщений в однолинейном центре осуществляется с дисциплиной PS (разделение процессора). Длительность обслуживания сообщений r-го класса, r=1,2,…,R, распределена по закону Кокса с параметрами a_irl, b_irl, m_irl, L_irl и средним , где A_irl - вероятность того, что сообщение класса r достигает l-й стадии обслуживания в i-том узле. Таким образом, скорость завершения обслуживания сообщений r-го класса, находящегося на l-том этапе в состоянии n_i центра, равна n_irl / n_i. После завершения обслуживания сообщение покидает центр с вероятностью b_irl и переходит к следующей стадии с вероятностью a_irl. Центр типа 3. Многолинейный центр с числом обслуживающих приборов, равным или большим максимального количества сообщений в этом центре, и дисциплиной обслуживания IS (обслуживанием без ожидания). Состояние центра и распределение длительности обслуживания, имеющее рациональное преобразование Лапласа, описывается, так же как и для центра второго типа. Центр типа 4. Однолинейный центр с дисциплиной обслуживания LCFS (LIFO). Так же, как для узлов второго и третьего типов, распределение длительности обслуживания имеет рациональное преобразование Лапласа и может отличаться для сообщений разных классов. Состояние центра n_i определяется вектором (r₁l₁, r₂l₂,…, r_nil_ni,), где n_i-число сообщений в i-том центре, r_jl_j,-пара характеризующая сообщение, стоящее j-тым в очереди и l_j -номер прерванного этапа обслуживания. Обслуживание прерванного сообщения начинается с того этапа, на котором оно было прервано. В частности, процессоры узлов коммутации моделируются центрами FIFO или разделение времени, а каналы передачи данных однолинейными и многолинейными центрами FIFO. Для моделирования терминалов и учета задержек, обусловленных временем подтверждения об успешной доставке пакета (ACK) или временем ожидания time-out, обычно используются центры типа IS. Это позволяют применить для расчета характеристик хорошо разработанные алгоритмы, описание которых было дано в предыдущих главах.

Значительное явление на характеристики сети пакетной коммутации оказывают способы доставки пакетов(диаграммы или виртуальные каналы) и методы маршрутизации. Моделирование различных способов доставки пакетов и методов маршрутизации осуществляются путем выбора соответствующего типа сети МО и матрицы маршрутов , структура которой учитывает и топологию сети. Например, в качестве модели датаграммной сети со случайной процедурой выбора маршрутов часто применяется открытая или замкнутая однородная сеть МО, а для моделирования постоянных виртуальных каналов (с возможным наличием альтернативных путей) и фиксированной маршрутизации – модель сети МО с несколькими классами сообщений. При этом учет служебных сообщений может быть осуществлен различными способами в зависимости от используемых протоков: либо увеличением длительности обслуживания сообщений в модели сети МО, либо введением дополнительного приоритетного класса служебных сообщений (длина служебных сообщений значительно меньше пакета данных).

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

Осн. лит.12[250-259],

Доп. лит.2[43-56].

Контрольные вопросы:

1. Для каких целей применяются модели сетей?

2. Что решается при оптимизации компьютерных сетей?

3. Какие типы центров обслуживания рассматриваются при анализе компьютерных сетей?

4. В чем состоит моделирование способов доставки пакетов?

5. В чем состоит зависимость и независимость величин обслуживания пакетов?