Методические указания к выполнению лабораторных работ Факультет информатики и систем управления (стр. 6 из 7)
Для оптимизации производительности ЛВС используют методы и средства измерения, анализа и моделирования. Клиент-серверная архитектура и распределенная обработка данных в ЛВС усложняют задачи моделирования.
Аналитическое моделирование ЛВС основано на использовании моделей систем массового обслуживания (СМО) [9, 10] и, как правило, связано со значительными упрощениями. Тем не менее результаты аналитического исследования могут быть очень ценными, даже если они не учитывают всех деталей реальной ЛВС. Такие модели позволяют достаточно быстро получить приближенную инженерную оценку влияния характеристик оборудования и программного обеспечения на показатели производительности ЛВС.
Модель ЛВС строится из отдельных блоков, каждый из которых представляет один узел или канал передачи ЛВС. Блок состоит из буферного накопителя пакетов и обслуживающего элемента (рис.2). На вход блока поступает поток пакетов, характеризуемый функцией распределения интервалов времени между моментами поступления пакетов A(t). Интенсивность l входного потока пакетов – это среднее число пакетов, поступающих на вход блока в единицу времени. Обратная величина 1/l – это среднее значение интервала между моментами поступления пакетов, которое
 |
определяется интегралом
 |
Интенсивность обслуживания блока – это m среднее число обрабатываемых пакетов в единицу времени. Обратная величина 1/m – это среднее значение длительности обслуживания пакета, которое определяется интегралом
где B(t) – функция распределения длительности обслуживания. Отношение r = l / m называется коэффициентом загрузки блока. Реальный блок имеет буфер ограниченной емкости r (см. рис.2,б). Идеализированный модуль может иметь неограниченный по емкости буфер (см. рис.2,а).
 |
Блок M/M/1. Рассмотрим самую простую модель типа M/M/1 (один обслуживающий элемент, неограниченная емкость буфера, экспоненциальные законы распределения интервалов времени между моментами поступления пакетов и времени обслуживания, дисциплина обслуживания FIFO) для блока, изображенного на рис.2,а. В этом случае A(t)=1– e–lt, B(t)=1–e–m t, среднее время задержки пакета в блоке
T = 1 / (m –l), ( 1 )
а среднее число пакетов в блоке (в очереди и в процессе передачи)
L = l / (m –l). ( 2 )
Среднее время ожидания в очереди W = T – (1/m), а среднее число пакетов в очереди LW = L – r.
 |
Блок M/G/1. Эта модель отличается от модели типа M/M/1 только тем, что распределение времени обслуживания B(t) может быть произвольном. Рассмотрим случай, когда распределение B(t) задается для блока двумя параметрами: интенсивностью обслуживания m и дисперсией времени обслуживания
Тогда среднее время нахождения пакета в очереди W = (1 + v2) WП, где WП = (r/2m)´(1–r)–1 – время нахождения пакета в очереди при постоянной длительности обслуживания; v2 = m2 D – квадрат коэффициента вариации времени обслуживания. Для постоянного времени обслуживания v=0, а для экспоненциального распределения времени обслуживания v=1. Для модели M/G/1 оценка времени пребывания пакета в блоке T = W + (1/m), длины очереди в буфере LW =lW и общего числа пакетов в блоке L = LW + r.
Блоки M/M/1/r и M/G/1/r. Модель типа M/G/1/r для блока, изображенного на рис.2,б, отличается от модели M/G/1 тем, что емкость буфера ограничена величиной r (предполагается, что обрабатываемый пакет находится также в буфере). Эта модель характеризуется вероятностью потери пакета (отказа в обслуживании) [10]
PОТК » (1–r) rY(r,v) /(1–rY(r,v)+1), ( 3 )
где Y(r,n)=2r/(1+n2), причем n - коэффициент вариации. Абсолютная пропускная способность блока M/G/1/r
lАБС=l (1– PОТК).
При n=1 формула дает точное значение PОТК для экспоненциального распределения B(t), т.е. для блоков M/M/1/r.
 |
Сеть блоков M/M/1. Модель ЛВС можно представить в виде сети блоков (сети массового обслуживания – СеМО [8]), причем многие блоки содержат буферы. Простые аналитические формулы можно получить для открытой сети блоков M/M/1, пример которой представлен на рис.2.
В этой сети, состоящей из трех блоков, три входных потока пакетов, имеющих интенсивности g1, g2 и g3 соответственно. Требуется оценить среднюю задержку пакетов для каждого потока. Очереди в этой сети можно рассматривать по отдельности [9], причем число пакетов в блоке j=1…3 оценивается по формуле (1), а именно
Lj = lj / (mj – lj).
Интенсивность lj потока на входе каждого блока равна сумме интенсивностей элементарных потоков, поступающих на блок в соответствии с рис.3: l1 = g1 + g2, l2 = g1 + g2 + g3, l3 = g2 + g3.
 |
Можно показать [9], что средняя задержка пакета в сети
 |
где n – число блоков в системе; g – сумма интенсивностей всех потоков, входящих в систему. Для отдельного потока i средняя задержка пакета в сети
где Ji– подмножество блоков, участвующих в обработке потока i. В рассматриваемом примере J1={1, 2, 3}, J2={1, 2} и J3={2, 3}.
Формула (4) верна при следующих предположениях.
· Закон распределения интервалов времени между моментами поступления пакетов A(t) для отдельных потоков экспоненциальный, причем потоки являются независимыми процессами. Это предположение может быть выполнено на практике.
· Закон распределения времени обслуживания B(t) также экспоненциальный, причем процессы обслуживания в каждой очереди независимы. Это предположение не может быть выполнено, поскольку время обслуживания пакета пропорционально его длине, и, следовательно, нельзя говорить о независимости времен обслуживания в очередях.
Однако моделирование показывает [9], что применение формулы (4) дает приемлемую оценку средней задержки пакета в сети.
Имитационное моделирование позволяет имитировать поведение реальной ЛВС. Имеется много программных средств для имитационного моделирования компьютерных сетей (GPSS, COMNET III фирмы Caci Products Co., BONeS Designer фирмы Cadence Inc., OPNET фирмы Modeler Mil3 Inc., ns2 и др.).
Рассмотрим пример алгоритма для имитационного моделирования блоков типа M/G/1 (рис.4). В этом алгоритме использованы следующие обозначения:
tПРИБ – момент прибытия пакета; tНАЧ – момент начала обработки пакета; tКОН – момент окончания обработки пакета; N – число обработанных пакетов; t – время пребывания пакета в блоке; Random – генератор случайных чисел в диапазоне (0, 1). П.3 алгоритма позволяет задавать экспоненциальный закон распре-деления интервалов времени между моментами поступления пакетов A(t) с интенсивностью l, а п.5 – закон распределения времени обслу-живания B(t) с интенсивностью m и коэффициентом вариации n.В рассматриваемом примере имитационная модель позволяет оценить среднее время T пребывания пакетов в блоке, а также среднеквадратическое отклонение sT этого времени. Имитационная модель реализована на языке TurboPascal. В таблице приведены результаты расчетов для трех режимов работы блока.
| N | l | m | n | T (результат расчета) | Результаты имитационного моделирования | |
| T | sT | |||||
| 10000 | 0,100 | 0,500 | 0,5 | 2,313 | 2,243 | 1,258 |
| 10000 | 0,100 | 0,200 | 0,5 | 8,125 | 7,362 | 5,144 |
| 10000 | 0,100 | 0,150 | 0,5 | 15,000 | 12,976 | 10,505 |
Для расчета времени пребывания пакетов в блоке использована формула