Содержание к диссертации
Введение
ГЛАВА 1. Дискретные модели процедур управления потоком и буферной памятью в пакетных сетях 13
1.1. Классификация процедур управления трафиком в пакетных сетях 13
1.2. Методы распределения буферной памяти 19
1.3. Модели входящего потока 26
1.4. Выводы 35
ГЛАВА 2. Анализ систем с групповым потоком фазового типа и пороговым управлением в дискретном времени 36
2.1. Построение и анализ модели с групповым потоком фазового типа 36
2.2. Матрично-рекуррентное решение системы уравнений равновесия для СМО 49
2.3. Анализ вероятностно-временных характеристик СМО PHDX 60
2.4. Характеристики функционирования и численный анализ СМО 68
2.5. Выводы 76
ГЛАВА 3. Анализ геометрической системы массового обслуживания с конечным накопителем изменяемой емкости
3.1. Построение СМО с конечным накопителем изменяемой емкости и вывод системы уравнений равновесия 77
3.2. Решение системы уравнений равновесия 79
3.3. Вероятностно-временные характеристики и численный анализ 93
3.4. Выводы 115
Заключение 116
Список источников
- Методы распределения буферной памяти
- Модели входящего потока
- Матрично-рекуррентное решение системы уравнений равновесия для СМО
- Решение системы уравнений равновесия
Введение к работе
Развитие телекоммуникаций идет со значительным ускорением; быстрый рост числа пользователей, расширение перечня услуг и их качества повышают уровень требований, предъявляемых к системам и сетям связи [36,38,65,90]. Обеспечение параметров качества услуги для различных типов трафика является сложной задачей, решение которой невозможно без применения специальных механизмов управления в условиях изменяющихся требований услуг к транспортным и другим сетевым ресурсам, К основным механизмам относятся методы и алгоритмы управления доступом, потоком и формирования трафика, алгоритмы распределения ресурсов: ширины полосы пропускания каналов и буферной памяти (БП) пакетных коммутаторов [24-26,29-31, 39,51,71,74-78,81,88,92,94,100].
Коммутационное оборудование пакетных сетей связи характеризуется развитыми процедурами управления ресурсами БП, снижающими совокупные потери пакетов. Исследование вопросов статического распределения БП, оптимизирующего ее использование, ведется с начала 1980 гг., по сути, в период становления компьютерных сетей, и нашло отражение в работах российских ученых (Башарин Г.П., Вишневский В.М., Гнеденко Б.В., Климов Г.П., Наумов В.А., ПечинкинА.В., Рыков В.В., Самуилов К.Е., Севастьянов Б.А., Степанов С.Н., Харкевич А.Д., Шнепс-Шнеппе М.А., Яновский Г.Г. и др.) [1,7-11,14,17,19,32-34,37,41,43-45,47,49,50] и зарубежных авторов (Agrawala А.К., Choudhury А.К., IrlandM., KamounF., KleinrokL., Lam S., Kuhn P., Latouch G., Mark J. W., Tobagi F. и др.) [64,72,79,80,83,95}
Современные пакетные коммутаторы требуют использования методов динамического управления размером памяти, выделяемой буферизуемым пакетам различных направлений, классов качества, виртуальных путей и каналов. Данные задачи приводят к необходимости исследования систем массового обслуживания (СМО) с буферным накопителем (БН), емкость которого может случайно изменяться во времени. В настоящее время известно ограниченное число работ, рассматривающих технические аспекты реализации подобной задачи [60]; математические модели и методы для ее анализа праісгически отсутствуют.
В настоящее время актуальность проблемы лишь возросла с переходом к сетям следующего поколения (NGN), ориентированным на услуги со сложными моделями нагрузки [31,37,98]. В связи с этим возникают задачи исследования систем связи со специальными механизмами управления потоком, изменяющимся в процессе функционирования системы. Исследованию математических моделей систем связи с такими потоками посвятили ряд работ следующие российские и зарубежные авторы: Бочаров П.П., Ершов В.А., Кузнецов Н.А., Лагутин B.C., Наумов В. А., Нейман В.И., Шоргин С JL, IversenV.B., GelenbeE., PerrosH.G., Tran-GiaP. и др. [12,14-16,31,38,41, 58,59,71,74,87,92].
Цифровая синхронная природа современных пакетных технологий приводит к необходимости исследования рассмотренных выше задач в дискретном времени. Развитие методов анализа СМО ограниченной емкости и в дискретном времени, которые позволяли бы учитывать как дискретный характер передаваемых данных, так и существенно дискретный характер функционирования реальных систем связи, является актуальным. Изучению СМО в дискретном времени посвящено значительное число работ (Башарин Г.П., Бочаров ШХ, Ефимушкин В. А., Куренков Б.Е., Соколов И A., Bruneel Н., Kobayashi Н., KonheimA., DadunaH. Woodward Е. и др.) [2-6,13,20,21,23,46,61,62,66, 70,82,99]. Следует отметить при этом, что работ, посвященных анализу СМО в дискретном времени с поступающим потоком фазового типа и/или накопителем сложной структуры, немного.
Таким образом, разработка СМО в дискретном времени с поступающим потоком и накопителем сложной структуры и эффективных методов анализа их вероятностно-временных характеристик (ВВХ) является актуальной задачей в условиях перехода от традиционного к оборудованию сетей следующего поколения в виде высокопроизводительных аппаратно-программных комплексов, быстрого роста возможностей для применения новых методов управления потоками и сетевыми ресурсами.
В связи с изложенным, целью диссертационной работы является разработка расчетных методов и анализ однолинейных СМО ограниченной емкости, функционирующих в дискретном времени, с применением различных методов управления емкостью БН и процессом обслуживания. Перейдем к общей характеристике полученных в диссертации результатов и одновременно продолжим обзор литературы.
Диссертационная работа состоит из 3 глав.
Методы распределения буферной памяти
Современное коммутационное оборудование пакетных сетей связи характеризуется развитыми процедурами распределения БП, минимизирующими совокупные потери пакетов. Исследование этих вопросов ведется с начала 1980 гг. [1,7,9,79,84], по сути, в период становления пакетных сетей и постановки задачи оптимизации памяти сетевых узлов.
Известны (см., например, [7]) пять схем разделения БП. Первая, схема полного разделения (СР, Complete Pardoning), предполагает фиксированное разделение суммарной емкости г буферного пространства (которое может объединять физически разные буферы) между пакетами, направляемыми на К разных выходов. При этом, число пакетов, направляемых на i-c направление (г-пакетов) не может превышать ritrm=r, Здесь и далее в этом разделе і = \,К и точка вместо индекса означает полную сумму по этому индексу. Для марковского процесса, описывающего число nT -(nlt.„9nK) пакетов К типов в памяти, разделяемой в соответствии с данной схемой, пространство состояний имеет вид X] = jn: 0 и,, й rt,і = UK,rt = r\
Ее антиподом является полнодоступная схема (CS, Complete Sharing): поступающий пакет буферизуется при наличии свободного места в общей памяти, независимо от того, на какой выход он адресуется, при этом Х2 = {п: 0 , щ r,i = \,К,п% г\.
Полнодоступная схема с индивидуальными ограничениями на длины выходных очередей, называемыми потолками (SMQ, Sharing with Maximum Queue Length), является развитием предыдущей. В данном случае при наличии общей полнодоступной БП вводятся фиксированные максимальные значения количества буферизуемых пакетов, направляемых на разные направления, т.е. число пакетов каждого типа не может превышать заданного значения (потолка): Х3 = {п: 0 л, rt,i - № л. г,г. г}.
Неполнодоступная схема (SMA, Sharing with a Minimum Allocation) представляет собой симбиоз СР и CS, поскольку предполагает наличие как общей буферной памяти (CS), так и ее выделенных частей для пакетов каждого типа (СР) Xi=L:Q ni r + ai i = UK 1(ni aiy Л
Последний вариант - неполнодоступная схема с индивидуальными потолками (SMQMA, Sharing with Maximum Queue and Minimum Allocation) - отличается от предыдущей введением индивидуальных ограничений в общей части БП Х5 =п:0л(г, + а,,( = 1Г, ,-а,)+ г 1. Схема SMQMA является самой общей из приведенных, а, например, SMQ является ее частным случаем при at=0,i = l,K. Обозначая подобную зависимость знаком имеем для соответствующих значений а, и Гі=0,і = Ї К: {SMQ,SMA} !SMQMA, {CS,CP} i{SMQ,SMA}. Каждая из схем содержит определенную стратегию организации БП фиксированного объема. Причем, в отличие от других, схема 2 (CS) не + допускает оптимизации. Таким образом, встает вопрос определения значений структурных параметров БП: г( для схем СР и SMQ, а( для схемы SMA, а для SMQMA - значений обоих наборов этих параметров. Их выбор может определяться в соответствии с некоторым критерием оптимальности. При управлении перегрузками таким критерием является, например, вероятность потерь на коммутаторе, которую требуется минимизировать.
Класс схем со статическими порогами, включающий CS, СР, SMQ и их производные - SMA и SMQMA, имеет одно важное преимущество: простота реализации. Это - основная причина того, что доступные на сегодняшний день на рынке пакетные коммутаторы и статистические мультиплексоры, действительно, используют этот класс схем буферизации. Тем не менее, характеристики данных схем не могут быть улучшены в процессе функционирования коммутатора, невозможно предотвратить также некоторые нежелательные ситуации без подстройки пороговых параметров в условиях изменяющейся нагрузки. Поэтому, идея динамического управления трафиком и пороговыми параметрами в случае необходимости является заманчивой и на современном этапе развития коммутационной техники становится приоритетной.
Однако, расчет оптимальных значений порогов в коммутаторе с множеством портов является трудной задачей. Схемы с динамическими порогами, являющиеся новейшими из всех рассмотренных стратегий, намного более стойки к изменениям нагрузки, чем схемы со статическими порогами. Так схемы с динамическими порогами просты в реализации, показывают очень хорошие характеристики по адаптируемости к условиям трафика, причем как для малых, так и для больших нагрузок, обеспечивают поддержку нескольких классов обслуживания пакетов [52].
В настоящее время актуальность проблемы распределения буферной памяти лишь возросла с переходом к сетям следующего поколения, ориентированным на использование пакетных технологий и услуги, требующие промежуточного хранения больших объемов информации (распределенные видеоконференции, аудио высокого качества, видео по запросу и др.) [38]. В связи с этим возникают задачи исследования систем связи с изменяющимся в процессе функционирования размером памяти, выделяемой пакетам конкретного направления [60,80,90].
Модели входящего потока
Стационарное распределение может найдено из системы уравнений равновесия (СУР) и нормировочного условия (здесь - R = г + 1, i-ltK):
Основной особенностью СМО в дискретном времени является неординарность событий, которые могут произойти в системе за такт. Например, в рассматриваемой системе в соответствии с описанной выше последовательностью событий может произойти окончание обслуживания, если на приборе находилась заявка; поступление новой заявки, переход управляющего процесса в другое состояние. Конечно же, могут произойти и другие комбинации событий, например, не окончание обслуживания, поступление новой заявки, сохранение состояния управляющей ЦМ. Понятно, что мощность множества комбинаций исходов всех событий в СМО в дискретном времени определяется количеством возможных событий. Так в с -линейной СМО без ожидания в дискретном времени с геометрическими распределениями ординарного поступающего потока и длительностей обслуживания Geom \ Geom \ с может произойти одновременно с+1 событий. Другой пример, в однолинейной СМО конечной емкости с дискретными распределениями фазового типа процессов обслуживания и поступления PHD\PHD\\\r оо - могут произойти следующие активные события: окончание обслуживания и уход заявки с текущей фазы, выбор новой заявки на некоторую фазу обслуживания, поступление новой заявки в БН с текущей фазы фазового распределения, смена фазы нового периода генерации следующей поступающей заявки.
Следует также иметь в виду, что последовательность событий не имеет значения в дискретных системах с БН неограниченной емкости, но должна учитываться в СМО конечной емкости. Так в случае рассматриваемой прямой последовательности событий «окончание обслуживания - поступление» заявка, поступившая в переполненную систему в момент завершения обслуживания заявки на приборе, будет принята в БН, но при обратной последовательности событий «поступление - окончание обслуживания» поступившая заявка будет потеряна, независимо от завершения или не завершения обслуживания в данный момент. Резюмируя вышесказанное, отметим важность выбора необходимой последовательности событий при исследовании СМО в дискретном времени. В общем случае это необходимо делать всякий раз, если рассматриваемая система характеризуется некоторыми не рассматривавшимися ранее возможными активными событиями.
Хотя механизм получения СУР для систем в дискретном времени не представляет сложности, разберем его на примере первого уравнения. Данный механизм в скалярном виде будет использоваться для более сложных СМО в дискретном времени, рассматривающихся в главах 2 и 3, с необходимыми пояснениями и графическими иллюстрациями.
Итак, в состояние (О,/) за один такт можно попасть из состояния (0,_/), в том числе из самого состояния (0,/), лишь за счет не поступления новой заявки (с вероятностью aaj) и перехода управляющего процесса в состояние / (с вероятностью в»), а также из состояния р1} за счет завершения обслуживания заявки на приборе (с вероятностью Ь), не поступления новой заявки (с вероятностью a0j) и перехода управляющего процесса в состояние і (с вероятностью в„).
Подобным образом можно получить все возможные уравнения СУР, обращая внимание на очередность возможных событий и занятость БН в последнем уравнении, когда поступление новой заявки становится невозможным в случае занятости накопителя.
Не рассматривая в данном разделе способы получения решения СУР, отметим, что оно дает возможность найти необходимые характеристики функционирования СМО в стационарном режиме, к -например, вероятность потерь - = ] , вероятность простоя і=ї R системы - J 0J. , среднее число заявок в системе - N = крк ш, другие.
В главе 2 исследуются СМО с поступающим потоком, описываемым дискретным распределением фазового типа, существенно отличающемся от управляемого цепью Маркова геометрического потока.
Геометрический поток, управляемый цепью Маркова, характеризуется независимостью процесса управления от геометрического процесса генерации новой заявки (или группы заявок). В дискретном распределении фазового типа вероятность генерации новой заявки напрямую связана с распределением вероятностей переходов между фазами, поэтому поток, моделируемый PHD, в отличие от потока MMGeom, позволяет при разработке моделей нагрузки для пакетных коммутаторов и статистических мультиплексоров более тонко учитывать влияние физического состояния моделируемого процесса.
Матрично-рекуррентное решение системы уравнений равновесия для СМО
В данном разделе рассматривается однолинейная СМО с накопителем конечной емкости г, Our со, групповым потоком фазового типа и пороговым управлением, функционирующая в дискретном времени (рис.2.3). Хотя данная система обобщает СМО, рассмотренную выше, сделанный в предыдущем разделе анализ позволил на примере структурно более простой системы выяснить механизмы описания подобных СМО, получения СУР, решения, что предоставляет существенные возможности в методическом плане исследований и позволяет сосредоточиться на структурных особенностях СМО, анализируемых в данном разделе и следующей главе.
Итак, события на такте и, т.е. в момент nk, происходят в последовательности, введенной в разделе 2.1. Будем вновь рассматривать неординарный поступающий поток, описанный в разделе 2.1. Пусть с вероятностью gs объем поступившей группы заявок равен s, s l, g, = 1, и потерянные заявки не возобновляются и не оказывают никакого влияния на СМО и входящий поток. Длительности генерации групп заявок вновь описываются дискретным РН -распределением с РН-представлением (а, В) порядка т. Введем целочисленный вектор R =(RXIR.2,...,RL) гДе l iRl R2 ... RL R, \йЬйг R - г +1. Величины Rltl-1,1, будем называть порогами.
Время обслуживания каждой заявки имеет геометрическое распределение с параметром b(q), 0 b(q) ls зависящим от числа q заявок в СМО, q = 0,Я, причем b(q) = bt, если Лм q .Rlt где 0 Ьх 1, / = 1,, Л0=0. Будем говорить, что система находится в режиме обслуживания /, если b(q) - 6,.
Для сокращения записи будем кодировать рассматриваемую СМО как PHDA \Geom(R)\\\r оо, где Geom(R) - геометрическое распределение длительности обслуживания, зависящее от режима (R).
Пусть - число заявок в СМО в момент nh, а Г]в - номер фазы генерации поступающей заявки в этот момент. Функционирование СМО PHDX ] Geom(R) 111 г оо можно описать однородной цепью Маркова =(,77я) и1. Пространство состояний цепи Маркова п есть Здесь q - количество заявок в СМО, аг номер фазы генерации заявки в момент nh.
Из сделанных предположений вытекает, что все состояния рассматриваемой цепи п, и 1, сообщаются и образуют один класс без подклассов. Поэтому финальное распределение вероятностей РГКРЇ»РГ»".,РЯ)» VT94P4l P92 — P4mh = МЇ. Существует, р 0, р не зависит от начального распределения и совпадает со стационарным [48]. Пусть А - матрица переходных вероятностей рассматриваемой цепи Маркова, 0Г = (0,...,0), I - единичная матрица. Тогда р можно найти из СУР порядка \Х\ = {R + 1)/и и ранга \Х\ -1: рг(А-1) = 0г (2.13) с нормировочным условием рг1 = 1. (2.14)
Пояснение поведения ЦМ п, л 1, с помощью диаграммы переходов, изображенной на рис.2.4, в состояниях (0,/), (1,/), (R,i) и (q,i), q = l,r, i = l,m, аналогично представленному в разделе 2.1. Поэтому здесь рассмотрим лишь случай в), как наиболее общий. -52 Как видно из рис.2.2в), в состояние (q,i) можно попасть из состояния: - (q + l,j), если произойдет обслуживание заявки и смена фазы j на і (с вероятностью Ь(д + 1)Ь ); - (д Л если не произойдет обслуживание заявки и произойдет смена фазы j на / (с вероятностью b(q)bp), или, если заявка поступит, и одновременно произойдет обслуживание заявки, а генерация новой группы заявок начнется с фазы і (с вероятностью b djgiGCi); - (О, у) в случае поступления группы из q заявок (с вероятностью - (stj), s = ltq-lt3a. счет поступления группы из #-+1 заявок, одновременного обслуживания одной заявки и начала генерации новой группы заявок с фазы І (с вероятностью b{s)djgq_s+xai), „ или за счет поступления группы из q-s заявок без окончания обслуживания на приборе, при условии, что генерация следующей группы заявок начнется с фазы / (с вероятностью Остальные вероятности переходов поясняются аналогично.
Решение системы уравнений равновесия
Сначала рассмотрим поведение графиков по группам. Для каждой из групп можно отметить, что поведение графиков S{r) и S\r J одинаковое. А именно, при малых и средних значениях вероятности а поступления заявки за такт значения коэффициентов совокупных затрат S(r) и (/) близки, т.е. практически совпадают. Однако при больших значениях вероятности а (от 0,6 до 0,9), а для группы 3 при значениях вероятности а (от 0,35 до 0,9), совокупные затраты увеличиваются. Можно отметить, что для групп 2 и 3 прослеживается значение совокупных затрат 5(?) показывает лучшее поведение по сравнению с S\r J, а для группы 1 мы видим противоположный характер поведения графиков.
Теперь сравним поведение групп графиков между собой. Можно отметить, что при малых значениях вероятности а поступления заявки за такт лучшее поведение показывают графики группы 3, а наихудшее -графики группы 1, графики группы 2 лежат между графиками групп 1 и 3. При больших значениях вероятности а поступления заявки за такт (0,85-0,9) лучшее поведение показывают графики группы 2, а наихудшее - графики группы 3.
Таким образом, можно отметить следующую закономерность: при низкой и средней нагрузках на поведение (увеличение) совокупных затрат S(r) и S\r ) большее влияние оказывает стоимость емкости БН, а не стоимость потери заявки; и наоборот при высокой нагрузке.
Также представляет интерес проведение сравнительного анализа поведения системы, когда изменение rvar осуществляется при значительном изменении числа заявок в БН. Это позволяет освободиться от возможной частой смены значения rvar при «дрожании» числа заявок около значения г;, / = 1,, и, соответственно, уменьшить издержки (стоимость переключений) на управление в технических системах, моделируемых данной СМО.
В качестве примера рассмотрим случай, когда емкость БН rvar может измениться за такт и с вероятностью dt, 0 di 1 на rM, / = 2,L, если число заявок в СМО в момент времени nh меньше или равно г 2; назовем эту процедуру схемой 2, а рассматриваемую ранее - схемой 1. Формулы для вычисления других ВВХ сохраняются.
На рис.3.13 приведены графики вероятности потерь тг в СМО Geom Geom j 1 [ rvar со для схем 1 и 2. Рассматриваются параметры г = 20, 1. = 4, равномерное расположение значений rvar є{5,10,15,20}, & = 0,8, с; = 0,5, / = ЇЗ, и = 0,5, / = 2 4.
В этом случае мы видим, что присутствует превышение вероятности потерь л для схемы 1 (график 1 на рисунке) над ж для схемы 2 (график 2).
На рис.З.На) и рис.3.146) представлены графики зависимости коэффициента совокупных затрат S(r) от вероятности а поступления заявки за такт для схем 1 и 2 при условии равномерного расположения значений емкости БН и следующих общих параметрах: /- = 20, 1 = 4, rvar є {5,10,15,20}, 6 = 0,8, -,=0,5, / = U, /=0,5, / = 2J4, g = 10. Для рис.З.На) стоимостные коэффициенты выбраны равными: / = 10 и v,j =10, / = М, а для рис.3.146): / = {10,100} и v,, ={10,20,30,40}, / = ІД.
В этом случае показанном на рис.З.На) при заданных нагрузочных параметрах мы видим, что совокупные затраты для схемы 1 превышают совокупные затраты для схемы 2. Характер поведения графиков схож с графиками на рис.3.12 при / = 10 и v = {10,20,30,40}. Однако, в случае, когда стоимость емкости БН будет значительно выше стоимости переключений и потери заявки (рис. 14.6) при / = 10), то, как и следовало ожидать, мы видим противоположный характер поведения графиков совокупных потерь для схем 1 и 2.
На рис.3.146) также рассмотрен случай, когда стоимость потери заявки увеличена до значения / = 100 при тех же значениях стоимости емкости БН. Мы видим, что при малых и средних значениях вероятности а поступления заявки за такт совокупные затраты для схемы 1 показывают лучшие значения, чем для схемы 2.
