автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Системы массового обслуживания в дискретном времени с поступающим потоком и накопителем сложной структуры

На правах рукописи

ДЕДОВСКИХ Татьяна Владимировна

УДК 519.872

СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ В ДИСКРЕТНОМ ВРЕМЕНИ С ПОСТУПАЮЩИМ ПОТОКОМ И НАКОПИТЕЛЕМ СЛОЖНОЙ СТРУКТУРЫ

05.13.17 - теоретические основы информатики

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Москва-2005

Работа выполнена на кафедре систем телекоммуникаций факультета физико-математических и естественных наук Российского университета дружбы народов

Научный руководитель -кандидат физико-математических наук, доцент Ефимушкин В. А.

Официальные оппоненты: доктор технических наук, профессор Степанов С.Н. кандидат физико-математических наук Меркулов В.Е.

Ведущая организация: Институт проблем информатики Российской Академии наук

Защита состоится 21 октября 2005 г. в 16 час. 30 мин. на заседании диссертационного совета К 212.203.08 в Российском университете дружбы народов

Адрес: 115419, Москва, ул. Орджоникидзе, 3

С диссертацией можно ознакомиться в Научной библиотеке Российского университета дружбы народов по адресу: 117198, Москва, ул. Миклухо-Маклая, д.6

Автореферат разослан «_»

2005 г.

Ученый секретарь

диссертационного совета

кандидат физико-математических наук,

доцент

Фомин М.Б.

^006-У

7Ш"

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы

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

Коммутационное оборудование пакетных сетей связи характеризуется развитыми процедурами управления ресурсами БП, снижающими совокупные потери пакетов. Исследование вопросов статического распределения БП, оптимизирующего ее использование, ведется с начала 1980 гг., по сути, в период становления компьютерных сетей, и нашло отражение в работах российских ученых (Башарин Г.П., Боровков A.A., Вишневский В.М., Гнеденко Б.В., Наумов В.А., Печинкин A.B., Рыков В.В., Самуйлов К.Е., Севастьянов Б.А., Степанов С.Н., Харкевич А.Д., Шнепс-Шнеппе М.А., Яновский Г.Г. и др.) и зарубежных авторов (Agrawala А.К., Choudhury А.К., Irland М., Kamoun F., Kleinrok L., Lam S., Kuhn P., Latouch G., Mark J.W., Tobagi F. и др.).

Современные пакетные коммутаторы требуют использования методов динамического управления размером памяти, выделяемой буферизуемым пакетам различных направлений, классов качества, виртуальных путей и каналов. Данные задачи приводят к необходимости исследования систем массового обслуживания (СМО) с буферным накопителем (БН), емкость которого может случайно изменяться во времени. В настоящее время известно ограниченное число работ, рассматривающих технические аспекты реализации подобной задачи (Briem U., Wallmeier Е.), а математические модели и методы анализа практически отсутствуют.

В настоящее время актуальность проблемы лишь возросла с переходом к сетям следующего поколения, ориентированным на услуги со сложными моделями нагрузки. В связи с этим возникают задачи исследования систем связи со специальными процедурами управления потоком, изменяющимся в процессе функционирования системы. Исследованию математических моделей систем связи с такими потоками посвятили ряд работ следующие российские и зарубежные авторы: Бочаров П.П., Ершов В.А., Кузнецов H.A., Лагутин B.C., Нейман В.И., Iversen V.B., Gelenbe Е., Perros H.G.,

Цифровая синхронная природа современных пакетных технологий приводит к необходимости исследования рассмотренных выше задач в дискретном времени. Поэтому актуальным является развитие методов анализа СМО ограниченной емкости и в дискретном времени, которые позволяли бы учитывать как дискретный характер передаваемых данных, так и существенно дискретный характер функционирования реальных систем связи. Изучению СМО в дискретном времени посвящено значительное число работ (Башарин Г.П., Бочаров П.П., Ефимушкин В.А., Куренков Б.Е., Соколов И.А., Bruneel Н., Kobayashi Н., Konheim А., DadunaH. Woodward Е. и др.). Следует отметить при этом, что работ, посвященных анализу СМО в дискретном времени с поступающим потоком фазового типа и/или накопителем сложной структуры, немного.

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

Целью диссертационной работы является разработка численных методов для анализа и расчета характеристик однолинейных СМО ограниченной емкости в дискретном времени с различными методами управления емкостью БН и процессом обслуживания.

Методы исследования. В работе использованы методы теории вероятностей, теории массового обслуживания, теории телетрафика, линейной алгебры.

Научная новизна и результаты, выносимые на защиту, состоят в следующем:

- проведена классификация процедур управления трафиком в пакетных сетях;

- получено матричное рекуррентное решение для стационарного распределения вероятностей однолинейной СМО ограниченной емкости с неординарным поступающим потоком, описываемым распределением фазового типа и геометрическим распределением длительностей обслуживания в дискретном времени;

- получены выражения для ВВХ функционирования указанной выше СМО и проведен сравнительный анализ поведения некоторых ВВХ для различных распределений объема поступающей группы заявок;

- получена система уравнений равновесия (СУР) для однолинейной СМО ограниченной емкости с неординарным поступающим потоком, описываемым распределением фазового типа, геометрическим распределением длительностей обслуживания с пороговой

I! ' 1

; >Г0«-иМ ' V

: . wi -2-

зависимостью от числа заявок в системе, найдено матрично-рекуррентное решение СУР;

- получены выражения для ВВХ функционирования однолинейной СМО ограниченной емкости с неординарным поступающим потоком, описываемым распределением фазового типа, геометрическим распределением длительностей обслуживания с пороговой зависимостью от числа заявок в системе, проведен численный анализ в сравнении с СМО без порогов, рассмотрены частные случаи;

- впервые предложена модель динамического управления размером БП в виде СМО с БН изменяемой емкости в дискретном времени, для которой получена СУР, решение в матрично-рекуррентном виде. Проведен численный анализ ВВХ и интегральной штрафной функции, учитывающей стоимости БН, изменений его емкости и потерь заявок.

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

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

Реализация результатов работы. Результаты, полученные в диссертации, использованы в спецкурсах, читаемых кафедрой перспективных телекоммуникационных технологий и услуг МТУСИ и кафедры систем телекоммуникаций РУДН. Исследованные в диссертации СМО, методы их анализа и расчета ВВХ применены в НИР ФГУП ЦНИИС в области анализа характеристик функционирования пакетных сетей связи.

Апробация работы. Основные результаты, изложенные в диссертации, докладывались на следующих конференциях и семинарах:

- 55-й Научной сессии Российского НТОРЭС им. А.С. Попова, посвященной дню радио (Москва, 2000);

- Regional International Teletraffic Seminar "Telecommunication Network and Teletraffic Theory" (St.-Petersburg, 2002);

- Научном семинаре Института проблем информатики РАН "Проблемы и методы математического моделирования современных и перспективных информационно-телекоммуникационных сетей" (Москва, 2002);

- XXXVIII научной конференции факультета физико-математических и естественных наук Российского университета дружбы народов (Москва, 2002);

- Научных семинарах секции "Моделирование сетей связи, информационных систем и процессов" МНТОРЭС им. A.C. Попова (Москва, 2003,2004);

- Семинарах кафедры "Системы телекоммуникаций" Российского университета дружбы народов (Москва, 2005).

Публикации. По теме диссертации опубликовано 8 работ.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы из 100 наименований, приложения. Диссертация содержит 131 страниц текста, 31 рисунок.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе, в разделе 1.1 классифицированы процедуры управления трафиком в пакетных сетях. Проведен сравнительный анализ процедур управления доступом, формирования трафика, распределения ШПП, управления потоком, распределения буферной памяти.

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

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

Во второй главе, в разделе 2.1 исследована однолинейная СМО PHDX | Geom 111 г < со с накопителем конечной емкости г, 0 < г < оо (рис. 1), все изменения в которой могут происходить лишь в моменты времени nh, и = 1,2,.... Предполагается, что п-к такт представляет собой полуинтервал [(n-l)h, nh), и события на такте п, т.е. в момент nh, происходят в прямой последовательности: окончание обслуживания, поступление заявки и буферизация, выбор на обслуживание. Состояние системы в такте п +1 совпадает с состоянием в момент nh по окончании всех активных событий, произошедших в такте п.

Заявки поступают в систему группами, причем с вероятностью gs объем поступившей группы заявок равен s, si 1, g. =1; здесь и далее точка вместо индекса используется для обозначения полной суммы по этому индексу. Здесь и далее поступившие заявки, для которых не хватает свободных мест в накопителе, теряются, более не возобновляются и не оказывают никакого влияния на СМО и входящий поток. Порядок отбора теряемых заявок поступившей группы не учитывается.

Интервалы между поступлениями заявок, называемые длительностями генерации группы заявок, имеют дискретное фазовое распределение с РН-представлением (а,В) порядка т, где аг =(а,,...а„) - вероятностный вектор управления выбором фры генерации, вг1=1,

a. =1; В = Ijb^ | _ - субстохастическая матрица переходов между фазами

генерации, такая, что В1 < 1 и матрица В - невырождена; dr = (rf......dm) -

вектор вероятностей завершения генерации заявки на данной фазе /;

b,.+d,= 1, d.> 0, i = l,m. Таким образом, процесс блуждания заявки по фазам генерации описывается цепью Маркова (ЦМ), независящей от процессов хранения заявок в накопителе и их обслуживания. Здесь и далее 1Г =(!,...,1). Будем использовать также обозначение R = г+ \\ черта над параметром обозначает дополнение до единицы, если не оговорено иное.

Время обслуживания каждой заявки имеет геометрическое распределение с параметром Ь, 0 < Ь < 1.

Для описанной СМО получена СУР, найдено ее решение матричным методом, использующим специфический вид матрицы переходных вероятностей А однородной ЦМ, описывающей поведение системы.

Функционирование СМО можно описать однородной ЦМ £„ = (£п,г]п) по моментам nh, п>1, над пространством состояний х е X,

х=()хч, 1=1,4

Я=о

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

распределение рг=(р£,р[,-.-.р*), Р^ =(/>,,,/>,2,? = <>>*> существует, р>0, не зависит от начального распределения, совпадает со стационарным и находится из СУР порядка \Х\ = (Л +1 )т и ранга -1:

рг(А-1) = 0т, (1)

с нормировочным условием

Рг1 = 1, (2) где 0Г = (0,...,0), I - единичная матрица.

Матрица А является клеточной верхней почти треугольной квазитеплицевой. Ее ненулевые клетки имеют следующий вид: А-оо «В,

Ам_,и,

А„ =Р, /„ -Ц +М,*,<*,,

АЛЛ = Г,Г = |4У ш-,г9*ььи+а,яъ,

Ам+1 -С,, С, Сч'Ъй&Р]*™^^01)' й = =

А- С', С', = <ц = bd¡g'saJ + bdig's+iaJ , * = и,

- . С, = *»|*Д ,,-й' ««/ - . Я = С?.

гда*; = 1г„,, 5=1,2,..., я; =1. /=0

Используя условие (2), СУР (1) преобразуется к виду:

(РоГ.РГ«)(А-1)'=(Ог,ег), (3)

где (А-1)1 является клеточной верхней почти треугольной квазитеплицевой матрицей А-1, последний столбец которой заменен единичным вектором:

(А-1) =

"В-1 С. с2 " СЯ-1 С*

ьв р-1 С,

0 ьв р-1 •• Ся-З с'я-2

0 0 0 .. ¥-1 С',

0 0 0 .. ЬВ Г-1

К Ь М N

(4)

В (3) ег=(ОгД) - размерности тЯ, а в (4) матрицы К, Ь, М, N определяются разбиением, показанным пунктирными линиями.

Пусть М0 =6В , М, =Р-1, М, =С,_|, 1 = 2,г. Запишем (3) с учетом (4) в виде системы линейных алгебраических уравнений (СЛАУ): р0гК + р[яМ = Ог р£ь+р?> = ег '

Теорема 2.1. СЛАУ (5) имеет единственное решение

р£=ег(Ь-КУМ)-'

Р[«=-Р£КУ

где V - клеточная верхняя треугольная теплицева матрица:

ГУ0 У, ... уг

У =

о Уо ... У,_,

О О ... УоА

у0 = м;1, V, = -Мо1 £М,_,У, , /•=иг.

У-о

В разделе 2.2 осуществляется анализ однолинейной СМО РНОх | веотф) 111 г <ю, с накопителем конечной емкости г, 0<г<оо, функционирующая в дискретном времени, с групповым поступающим потоком фазового типа, описанным в разделе 2.1, и пороговой зависимостью геометрического распределения длительности обслуживания от числа заявок в системе. События на такте и, т.е. в момент пИ, происходят в последовательности, введенной в разделе 2.1.

Введем целочисленный вектор порогов =(Л1,Л2,...,Л£), где 1<й, <Д2 < - =Л, 1 <Ьйг. Время обслуживания заявки имеет геометрическое распределение с параметром Ь(ц), 0 < Ь(д) <, 1, зависящим от числа заявок в СМО, и система находится в режиме обслуживания /, если Дм < # < , при этом £(<?) = Ъ1, где 0 < Ь, < 1, / = 1,1, <? = О,Я, Д0 = 0.

В разделе получена СУР для описанной СМО и найдено ее решение рекуррентно-матричным методом. В сделанных предположениях все состояния хеХ (X определяется аналогично), однородной ЦМ £п=(4„,г}„) по моментам и/г, п> 1, описывающей функционирование СМО, сообщаются и образуют один класс без подклассов, а стационарное распределение ЦМ

•р у у у у I

Р =(Ро>Ри-"»Рл)> Р9=0>?1.Р,2>—>Р9».)> 9 = О,Л,

находится из СУР (1) порядка \Х\ = (R+1 )т и ранга с нормировочным условием (2). Матрица переходных вероятностей А имея клеточное представление аналогичное введенному в разделе 1.2, не является квазитеплицевой, что не позволяет использовать тот же матричный метод нахождения решения. Пусть А', = А„ -1, г = 1,г.

Теорема 2.2. Для СМО PHDX \ Geom(R) 111 г < да решение СУР имеет вид _

Pi =PoW,,9-Ul,

Wi =—— АздАда,

г>(1)

q-2

W„ = -- '

У=!

а вектор p0 определяется из системы уравнений

p£w=or,

q=0

и условия нормировки.

Рассмотрены частные случаи исследуемой СМО и получены выражения для стационарного распределения.

В разделе 2.3 получены выражения и проведен численный анализ для ряда ВВХ функционирования СМО PHDX \ Geom\l\r <<х>, включая вероятность потери хотя бы одной заявки, среднее число заявок потерянных за такт, среднее число заявок в СМО, среднее число заявок, поступивших за один такт, среднее время пребывания заявки в СМО.

Проведен сравнительный анализ некоторых ВВХ для биноминального и геометрического распределений объема поступающей группы заявок с параметрами п, р, и р2, соответственно, в условиях равенства средних значений объемов групп, при этом р2 = пр, /(1 + wp,), или их дисперсий, при этом р2 = 1 + (1-^2<р + 1)/<р, <р = 2лр,(1-р,).

На рис.2 представлены графики зависимости вероятности л потерь хотя бы одной заявки от вероятности окончания обслуживания Ъ при значениях и = 10, р, = ОД, Л = 50, т = 3, ¿,=0,4, = аг =(0,4;0,3;0,3),

(

В =

0,2 0,2 0,2

Обозначения Geom 1 и Geom 2 на графиках

0,2 0,1 0,3 ^0,15 0,25 0,2,

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

Рис.2. Графики зависимости вероятности потерь хотя бы одной заявки я от параметра геометрического распределения длительности обслуживания

Графики на рис.2 показывают, что в случае равенства средних значений объемов групп вероятность потерь ниже для биноминального распределения, чем для геометрического. В случае одинаковых значений дисперсий кривые для обоих распределений близки друг к другу.

В разделе 2.4 получены выражения для основных ВВХ функционирования СМО PHDX | Geom(R) 111 г < да, включая вероятность пребывания на фазе генерации / в режиме обслуживания / и др.

Проведен сравнительный анализ некоторых ВВХ для СМО PHDX \Geom(R)\\\r <00 и рассмотренной в разделе 2.1 СМО без порогов с

_ L

емкостью накопителя равной величине bL=^p'.bi, называемой в

диссертации усредненным параметром порогового обслуживания. Здесь р[ - вероятность пребывания на фазе генерации / в режиме обслуживания /,

вычисляемая по формуле р\ = ^pgi+u(2-l)p0l, i = \,m, / = 1,L; «(*) -

q-R,-, +1

функция Хевисайда.

На рис.3 представлены графики зависимости вероятности потерь

R т во

л = ££pq,u(d,) J^gj от вероятности завершения генерации заявок d

q'Ol-i j=R-q+\

при следующих значениях параметров: т-3, 1 = 2, аТ =(0,4;0,3;0,3), Л, =15, R2=R = 30 и 6, = {0,1; 0,3}, Ь2 = {0,9; 0,7}, соответственно. Рассматривается геометрическое распределение объема поступающей группы заявок с параметром п = 10, р = 0,1.

Предполагается симметричность <1, т.е. / = 1,3. Элементы

матрицы В при этом пересчитываются пропорционально. Например, для

( 0,3 0,3 0,3"! Й? = 0,1 - В = 0,3 0,2 0,4 .

0,25 0,35 0,Зу

Из рис.3 видно, что вероятность потерь значительно меньше при использовании порогов и является нижней огибающей для я в системе без порогов с емкостью БН, равной усредненному параметру порогового обслуживания. Анализ позволил сделать вывод об улучшении ВВХ при введении порогов по сравнению с системой без порогов. л

1

0,9 0,1

0,7 0.« 0,5 0,4 0,3 0,2 0,1 о

.....пороги 15.30 А| =0,1;^ =0,9

-пороги 15. 30 Ь, = 0,3; ^ = 0,7

------без порогов А, = 0,1; = 0,9

----без порогов Ь, = 0,3; ^ = 0,7

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

Рис.3. Графики зависимости вероятности потерь п от вероятности завершения генерации заявок г/

В главе 3 в разделах 3.1, 3.2 описывается и исследуется впервые предложенная СМО в дискретном времени Оеот \ Сеот 1110 < гуаг < <ю с БН изменяемой емкости (рис.4). События на такте п происходят в последовательности, введенной в разделе 1.3, но добавляется рассматриваемое первым событие изменения емкости БН. Поступающий поток и процесс обслуживания описываются геометрическим законом распределения с параметрами а и Ь, 0 < а < 1, 0 < 6 < 1, соответственно.

Пусть гуаг €{/-,,/ = 1 ,Ь}, Г1 б ЗУ, где 1 <,г{<г1<...<г1=г, г <оо, 1 <1<г. Величина гуаг определяет емкость БН в данный момент. Считается, что обслуживаемая заявка занимает одно место в БН и освобождает его в момент окончания обслуживания. Далее - г = (г,, гг,..., гь).

- ю-

п=г г1 +1 п П-1

г1=г г'+| Г1 г/-1

Л'

Л5

1

■О

а) возможное увеличение гхзг с Г/ нагм б) возможное уменьшение гуаг с г- на/}_|

Рис.4. СМО веот \ Сеот 1110 < гш < оо с изменяемой емкостью БН

Пусть здесь и далее д - число заявок, а / - номер значения емкости БН. Емкость БН гуаг может измениться за такт п с вероятностью

- с,, 0<с, <1, на г;+1, если вмомент (и-1)А д = г;, / = 1,1-1, рис.4, а;

- ¿¡, 0< <1, на гм, если в момент (и-1)А ^ < г,_,, / = 2,Ь, рис.4, б. Функционирование СМО может быть описано однородной ЦМ

= (¿¡л'Чп) по моментам пк, п й 1, над пространством состояний

В сделанных предположениях ЦМ неразложима и апериодична, финальное распределение вероятностей рг =(р[,р2>- »рГ), рГ=(р?/).

<7 = о7о, 1 = \,Ь, существует, единственно, р>0, р не зависит от начального распределения и совпадает со стационарным.

Пусть А - матрица переходных вероятностей рассматриваемой ЦМ. Тогда р можно найти из СУР (1) порядка |Х\ = г. + Ь и ранга I-1 с нормировочным условием (2).

Разбиение X на подпространства X/, 1 = \,1, индуцирует разбиение матрицы А на клетки А/т = . причем вследствие

предположения об ординарности входящего потока матрица А является клеточной трехдиагональной.

Элементы клеток А1т имеют следующий вид: для диагональных клеток

с^'-^'-'^^-'НЬа^+Ьа), / = у = 1,г„

^Л^и^-^Ь^а, у = / + 1, /' = 0,г( -1,

еП.пМп-'ЦшЬ*-у=/-1, / = По,

О, в остальных случаях,

-П-

aIJ*i

0.7) =

для клеток верхней диагонали

с,Ш, i = r,,j = rt-1,

Ci(ba+ba), /' = у = , с,6a, i = r,,j = r,+\, 0, в остальных случаях, для клеток нижней диагонали </,а, / = У = 0,

«лм ('./) =

dt(ba + ba), i = j = 1, rM -1,

d.b^a, j = / = 0,rM-l,

¿,6а, j = i-l, /=1,г,_,-1, 0, в остальных случаях. Здесь <5(х,.у) - символ Кронекера.

Теорема 3.2. Для СМО Оеот | <7еот 1110 < гуаг < да решение СУР имеет

вид

где

—А^А^Х^А^)"1, т = 2,1-1,

а вектор р, определяется из системы уравнений р[\У' = еГ,

где матрица W' есть матрица W, у которой последний столбец заменен ¿-1 /

вектором £(П™т)1,а еГ = (0,...,0Д).

/=0 л>>1

В разделе 3.3 получены выражения для ВВХ, включая вероятность потерь в СМО с гуаг =г;, среднее число заявок в СМО при гУаг =г;, среднее число заявок в СМО независимо от текущей емкости БН, вероятности увеличения/уменьшения БН; проводится численный анализ.

На рис.5 изображены графики зависимости вероятности потерь ж = я,, где л1 есть вероятность потерь в СМО с гуаг = г,, / = 1, £, /г, = Ьрп 1С, , I =1,1 -1, я ь = Ьрп ^, от вероятности я поступления заявки за такт при значениях параметров г = 30, ¿ = 5, 6 = 0,8, с, =0,5, / = 1,4 и с/, = 0,5, / = 2,5. Рассматриваются следующие области изменения гуаг:

а) г = (6,12,18,24,30) - случай равномерного расположения значений ^ емкости БН;

б) г = (3,6,9,12,30) - случай малых значений гуаг;

в) г = (18,21,24,27,30) - случай больших значений гиаг.

Рис.5. Влияние неравномерности значений емкости БН rm на вероятность потерь п при изменении параметра поступающего потока а

Относительно характера поведения графиков для различных вариантов расположения значений rvar можно сделать следующие выводы. Для малых значений rvar (случай б) вероятность потерь наибольшая, а для больших (случай в) - меньше по сравнению с предыдущим случаем на всем интервале изменения вероятности поступления за такт. Это объясняется тем, что для меньших значений rvai в случае б) возможность наличия свободного буферного пространства существенно ниже, чем в случае в). Но при увеличении вероятности поступления текущее значение гуаг емкости БН приближается к 30 в обоих случаях, что проявляется в сближении. При равномерном распределении значений rvar (случай а) график вероятности потерь лежит между рассматривавшимися кривыми.

Проведен сравнительный анализ ВВХ для СМО с БН изменяемой и фиксированной емкости (во втором случае равной усредненной емкости изменяемого БН) и СМО с другой схемой изменения емкости БН.

В реальных устройствах связи операция переключения привносит дополнительные затраты; представляет интерес анализ совокупных затрат, учитывающих потери заявок и переключения. Вводится штрафная функция S(г), интегрирующая стоимости емкости БН, изменений емкости и потерь заявок, и исследуется ее поведение. На рис.6 для зависимости от вероятности а поступления заявки за такт представлены графики

L £-1 L L

коэффициента 5(г)=£У/Я-; +Z£/+P/+ pj совокупных

1=1 М 1=2 /=1

затрат исследуемой СМО и коэффициента затрат £(/•*)= /г-Ьрг. для СМО Оеот\Сеот\\\г* <оо, где г* - верхнее целое от усредненного значения емкости БН гщ. Здесь g* и gJ, 1 = \,Ь-\, - стоимости увеличения и уменьшения емкости БН, соответственно, /, - стоимость потери заявки при гУаг=г,, 1 = \,Ь, - стоимость части накопителя размером д. Для $(г") используются значения согласно полученной емкости г* БН системы Сеот | Сеот 111 г* < да, а fr. выбирается равным /, где / соответствует значению г,, являющемуся ближайшим целым к г .

Рис.6. Графики зависимости коэффициента совокупных затрат S(г) и ¿(г*) от параметра поступающего потока а

Графики получены при условии равномерного расположения значений гшг емкости БН и следующих значениях параметров: г-20,

1 = 4, г = (5,10,15,20), 6 = 0,8, с, =0,5, /-13, ¿,=0,5, 1 = 2А, £ = 10,

/€{10,100,1000}, vn ={10/;/;0,1/}, / = Ц5. На графиках (1) соответствует S(r),

а (2) - s(r'). Таким образом, при = g+, gj = g~, = g~ = g, /, = / для всех значений / рассматривается случай пропорционального увеличения коэффициента стоимости потери заявки / и уменьшения коэффициента стоимости емкости vn БН при неизменном коэффициенте стоимости изменения емкости БН g.

Относительно поведения графиков отметим, что при одинаковых значениях / = / = 10 и g значения коэффициента совокупных затрат

s(r*) показывают лучшие значения по сравнению с S(r).

Выявлена также следующая закономерность: при низкой и средней нагрузках большее влияние на увеличение совокупных затрат S(r) и s(r*) оказывает стоимость емкости БН, а не стоимость потери заявки; и наоборот при высокой нагрузке.

Для проведения численного анализа рассмотренных в главах 2,3 СМО, были разработаны программные средства на языке С++, обеспечивающие работу с матрицами произвольного размера. Для этого использовалась технология отображения файлов, особенностью которой является обработка файлов на жестком диске, как областей оперативной памяти. Таким образом, размеры матриц зависят только от объема свободного места на диске и типа используемой файловой системы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

3. Получены СУР для однолинейной СМО ограниченной емкости с неординарным поступающим потоком фазового типа и пороговой зависимостью параметра геометрического распределения длительностей обслуживания от числа заявок в СМО, ее матрично-рекуррентное решение, выражения для ВВХ. Проведен численный анализ в сравнении с СМО без порогов, рассмотрены частные случаи.

4. Впервые предложена СМО Geom | Geom 1110 < rvar < да с БН изменяемой емкости в дискретном времени, для которой получена СУР, найдено ее решение в матрично-рекуррентном виде, получены основные ВВХ, проведен численный анализ их поведения.

5. Показано улучшение ВВХ функционирования СМО Geom|Geom|ljO<rvar <оо в сравнении с системой с фиксированной емкостью БН равной усредненной емкости изменяемого БН. Проведен анализ интегральной штрафной функции, учитывающей стоимости БН, изменений его емкости и потерь заявок в сравнении с системой с фиксированным БН.

Основные результаты диссертации отражены в следующих

опубликованных работах:

1. Ледовских Т.В. Методы управления перегрузками в сетях ATM: сравнительный обзор // Сб. трудов XXXVI Всероссийской научной конференции по проблемам математики, информатики, физики, химии и методики преподавания естественно-научных дисциплин. Секция "Системы телекоммуникаций и теория телетрафика". - М.: ПАИМС, 2000. - С.16-17.

2. Efimushkin V., Ledovskikh Т. Analysis of the discrete time queueing system with burst phase-type input model // Proc. of St.-Petersburg Regional International Teletraffic Seminar "Telecommunication Network and Teletraffic Theory", 2002. - C. 200-214.

3. Ефимушкин В.А., Ледовских Т.В. Численный анализ порогового управления обслуживанием в дискретной системе с групповым потоком фазового типа // Сб. трудов XXXVIII Всероссийской научной конференции по проблемам математики, информатики, физики, химии и методики преподавания естественно-научных дисциплин. Секция "Системы телекоммуникаций и теория телетрафика". - М.: РУДН, 2002. - С.75-80.

4. Ледовских Т.В. Дискретная система массового обслуживания с групповым потоком фазового типа и пороговым управлением // Вестник РУДН. Сер. "Прикладная математика и информатика", 2002, № 1. — С. 107-118.

5. Ефимушкин В.А., Ледовских Т.В., Салькова М.В. Механизмы управления трафиком в сетях ATM // Электросвязь, 2003, № 1. -С.39-41.

6. Ефимушкин В.А., Ледовских Т.В., Салькова М.В. Механизмы управления потоками класса ABR в сетях ATM // Электросвязь, 2003, № 3.-C.33-36.

7. Ефимушкин В.А., Ледовских Т.В. Анализ геометрической системы массового обслуживания с конечным накопителем изменяемой емкости // Вестник РУДН. Сер. «Прикладная и компьютерная математика», 2005, Т.4, № 1,-С. 19-30.

8. Efimushkin V., Ledovskikh Т. Performance evaluation of discrete time queueing system with variable buffer capacity // Proc. of the 19-th International Teletraffic Congress, Beijing, August 29 - September 2, 2005. V.6C.- Pp.2081-2090.

Ледовских Татьяна Владимировна (Россия)

Системы массового обслуживания в дискретном времени с поступающим потоком и накопителем сложной структуры

В диссертационной работе исследуются однолинейные СМО ограниченной емкости, функционирующие в дискретном времени, с применением различных методов управления поступающим потоком, емкостью буферного накопителя и процессом обслуживания. В главе 1 проведен сравнительный анализ процедур управления трафиком в пакетных сетях. Показана актуальность исследования моделей в дискретном времени с динамическим распределением буферной памяти и входящими потоками, описываемыми дискретными распределениями фазового типа. В главе 2 рассматриваются СМО с неординарным поступающим потоком, описываемым распределением фазового типа, и геометрическим распределением длительности обслуживания, в том числе с пороговым управлением изменением его параметра. В главе 3 описывается и исследуется впервые предложенная СМО накопителем случайной емкости, ординарным поступающим потоком и процессом обслуживания, описываемыми геометрическим распределением. Дня каждой из систем получена СУР и найдено ее матричное решение. Получены основные ВВХ функционирования систем. Выполнен сравнительный численный анализ поведения некоторых ВВХ.

Ledovskikh Tatiana Vladimirovna (Russia)

The Discrete Oueueing Systems with Input Stream and Buffer of Complex Structure

The thesis implies the study of the single server finite buffer capacity queueing systems functioning in discrete time using different control methods of input stream, buffer capacity and servicing process. The comparative analysis of traffic management in packet networks is provided in Chapter 1. The actuality of study of queueing systems functioning in discrete time with dynamic buffer capacity allocation and discrete phase-type input stream. Chapter 2 consider the queueing systems with burst phase-type input stream and geometric-type service including the threshold control of its parameter change. Chapter 3 includes the description and the study of a new queueing system with variable buffer capacity, geometric-type general input stream and geometric-type service. For each system the solution of system's balance equations in matrix form is obtained. The formulas for performance characteristics are derived. The comparative numerical analysis is carried out.

Р1 5 9 5 0

РНБ Русский фонд

2006-4 13023

Подписано в печать 4 (>0 в &ГФормат 60x84/16. Тираж'-^экз.Усл.печ.л. А Заказ

Типография Издательства РУДН 117923, ГСП-1, г. Москва, ул. Орджоникидзе, д. 3

СПИСОК СОКРАЩЕНИЙ

СПИСОК ОСНОВНЫХ ОБОЗНАЧЕНИЙ

ВВЕДЕНИЕ

ГЛАВА 1. Дискретные модели процедур управления потоком и буферной памятью в пакетных сетях

1.1. Классификация процедур управления трафиком в пакетных сетях

1.2. Методы распределения буферной памяти

1.3. Модели входящего потока

1.4. Выводы

ГЛАВА 2. Анализ систем с групповым потоком фазового типа и пороговым управлением в дискретном времени

2.1. Построение и анализ модели с групповым потоком фазового типа

2.2. Матрично-рекуррентное решение системы уравнений равновесия для СМО

PHD*\Geom{R)\\\r «п

2.3. Анализ вероятностно-временных характеристик СМО PHDX | Geom 111 г < оо

2.4. Характеристики функционирования и численный анализ СМО

PHD*\Geom{R)\\\r <ъ

2.5. Выводы

ГЛАВА 3. Анализ геометрической системы массового обслуживания с конечным накопителем изменяемой емкости

3.1. Построение СМО с конечным накопителем 77 изменяемой емкости и вывод системы уравнений равновесия

3.2. Решение системы уравнений равновесия

3.3. Вероятностно-временные характеристики и 93 численный анализ

3.4. Выводы 115 ЗАКЛЮЧЕНИЕ 116 СПИСОК ИСТОЧНИКОВ 118 ПРИЛОЖЕНИЕ. Документы, подтверждающие 128 использование результатов диссертации

СПИСОК СОКРАЩЕНИЙ

БЫ - Буферный накопитель

БП - Буферная память

ВВХ - Вероятностно-временные характеристики

МП - Марковский процесс

СВ - Случайная величина

СМО - Система массового обслуживания СУР - Система уравнений равновесия

ЦМ - Цепь Маркова

1111111 - Ширина полосы пропускания ATM - Asynchronous Transfer Mode, асинхронный режим переноса

ABR - Available Bit Rate, доступная скорость передачи

САС - Connection Admission Control, управление установлением соединения

D-BMAP - Discrete-time batch Markovian arrival process, неординарный дискретный поток, управляемый ЦМ IP - Internet Protocol, протокол Интернет

NGN - Next Generation Network, сеть следующего поколения NPC - Network Parameter Control, управление параметрами сети nrt-VBR - Non-real time Variable Bit Rate, переменная скорость передачи не в реальном времени QoS - Quality of Service, качество услуги

RM - Resource Management, ячейка управления ресурсами

UBR - Unspecified Bit Rate, неспецифицированная скорость передачи

UPC - Usage Parameter Control, управление параметрами использования

СПИСОК ОСНОВНЫХ ОБОЗНАЧЕНИЙ и(х) =

S(iJ) =

1, jc > О О, х<0,

H = J

Geom Geom(R) var X si gj функция Хевисайда символ Кронекера геометрическое распределение геометрическое распределение длительности обслуживания, зависящее от режима ( R). распределение фазового типа в дискретном времени распределение фазового типа в дискретном времени с групповым поступающим потоком геометрическое распределение с параметром b(q), зависящим от числа q заявок в СМО емкость БН емкость СМО текущая емкость накопителя в СМО с БН изменяемой емкости вектор-столбец транспонированная матрица мощность множества стоимость изменения емкости БН с г{ на гм стоимость изменения емкости БН с ц на гм стоимость потери заявки при rvar = ту стоимости БН емкости q коэффициент совокупных затрат, учитывающий стоимости изменений емкости БН и потерь заявок коэффициент совокупных затрат, учитывающий стоимости емкости БН, изменений его емкости и потерь заявок

Развитие телекоммуникаций идет со значительным ускорением; быстрый рост числа пользователей, расширение перечня услуг и их качества повышают уровень требований, предъявляемых к системам и сетям связи [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., Наумов В.А., Нейман В.И., Шоргин СЛ., Iversen V.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 глав.

3.4. Выводы

1. Построена СМО Geom | Geom 111 rvar < qo с конечным накопителем изменяемой емкости в дискретном времени.

2. Получено матрично-рекуррентное решение СУР.

3. Получены выражения для вероятности потерь и других характеристик. Проведен численный анализ ВВХ системы. Проведен сравнительный анализ СМО с изменяемой емкостью БН с системой с фиксированным БН, и с аналогичной СМО с изменяемой емкостью БН, но с применением другой схемы изменения БН.

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

ЗАКЛЮЧЕНИЕ

В заключение сформулируем основные результаты работы.

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

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

3. Получены СУР для однолинейной СМО ограниченной емкости с неординарным поступающим потоком фазового типа и пороговой зависимостью параметра геометрического распределения длительностей обслуживания от числа заявок в СМО, ее матрично-рекуррентное решение, выражения для ВВХ. Проведен численный анализ в сравнении с СМО без порогов, рассмотрены частные случаи.

Впервые предложена СМО Geom \ Geom 1110 < rvar < оо с БН изменяемой емкости в дискретном времени, для которой получена СУР, найдено ее решение в матрично-рекуррентном виде, получены основные ВВХ, проведен численный анализ их поведения.

Показано улучшение ВВХ функционирования СМО Geom | Geom 1110 < rvar < оо в сравнении с системой с фиксированной емкостью БН равной усредненной емкости изменяемого БН. Проведен анализ интегральной штрафной функции, учитывающей стоимости БН, изменений его емкости и потерь заявок в сравнении с системой с фиксированным БН.

1. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. Теория и методы расчета. // М.: Наука, 1989. -336 с.

2. Башарин Г.П., Самуйлов К.Е. Об оптимальной структуре буферной памяти в сетях передачи данных с коммутацией пакетов / Препринт НСК АН СССР // М.: ВИНИТИ, 1982.

3. Башарин Г.П., Самуйлов К.Е. Современный этап в развитии теории телетрафика // Вычислительная математика, 2001. Том 1, №1.

4. Башарин Г.П., Самуйлов К.Е. О двух методах анализа однолинейных систем массового обслуживания с ограниченнымнакопителем // Труды VI Всес. шк.-семинара по вычислительным сетям, Москва-Винница, 1981, ч. II. С.75-81.

5. Башарин Г.П., Толмачев A.JI. Теория сетей массового обслуживания и ее приложения к анализу информационно-вычислительных систем / ИНТ. Теория вероятностей. Мат. статистика. Техн. кибернетика. // М.: ВИНИТИ, 1983. Т.21.-С.З-119.

6. Башарин Г.П., Харкевич А.Д., Шнепс М.А. Массовое обслуживаниев телефонии // М.: Наука, 1968. 247 с.

7. Бочаров П.П. Однолинейные системы обслуживания конечной емкости // М.: Изд-во УДН, 1985.

8. Бочаров П.П., Матюшенко С.И. Анализ однолинейной системы обслуживания конечной емкости с заявками нескольких видов в дискретном времени / В сб. Системы массового обслуживания и информатика // М.: Изд-во УДН, 1987. С.39-49.

9. Бочаров П.П., Печинкин В.А. Теория массового обслуживания // М.: Изд-во РУДН, 1995. 529 с.

10. Бочаров П.П., Литвин В.Г. Методы анализа и расчета системмассового обслуживания с распределениями фазового типа // Автоматика и телемеханика, 1986. № 5. С.5-23.

11. Бочаров П.П., Громов А.И. О пуассоновской двухфазной системе ограниченной емкости / В сб. Методы теории телетрафика в системах распределения информации // М.: Наука, 1975. С. 15-28.

12. Вишневский В.М. Теоретические основы проектированиякомпьютерных сетей // М.: Техносфера, 2003.-512с.

13. Гантмахер Ф.Р. Теория матриц // М.: Наука, 1988. 549 с.

14. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания // М.: Наука, ГРФМЛ, 1987. 368 с.

15. Ефимушкин В.А. Системы массового обслуживания в дискретномвремени и их приложение к анализу производительности локальныхсетей // Диссертация на соискание ученой степени к.ф.-м.н. по специальности 05.25.01 Теоретические основы информатики. 1989.-223 с.

16. Ефимушкин В.А. Анализ системы конечной емкости с обслуживанием общего вида и неоднородными заявками в дискретном времени / В кн.: Модели информационных сетей // М.: Наука, 1984. С.76-83.

17. Ефимушкин В.А. Классификация систем массового обслуживания случайной структуры / В кн. Системы телекоммуникаций и моделирование сложных систем // М.: Изд-во ПАИМС, 2000. С.5-6.

18. Ефимушкин В.А., Сосорев М.А. Анализ модели узла коммутации сообщений / В кн. Техническая эксплуатация аппаратуры связи. Сб. научных трудов ЦНИИС // М.: Изд-во ЦНИИС, 1987. С. 10-20.

19. Ефимушкин В.А., Дедовских Т.В. Коммутация в сетях ATM // Сети,1999. № 12. С.28-35.

20. Ефимушкин В.А., Дедовских Т.В. Коммутация в сетях ATM. Часть 2 // Сети, 2000. № 1. С.26-31.

21. Ефимушкин В.А., Дедовских Т.В. Методы управления перегрузками в сетях ATM // Труды 55-й Научной сессии Российского НТОРЭС им. А.С. Попова, посвященной Дню Радио.2000. -С.41-43.

22. Ефимушкин В.А., Дедовских Т.В. Анализ геометрической системы массового обслуживания с конечным накопителем изменяемойемкости // Вестник РУДН. Сер. Прикладная и компьютерная математика, 2005. Т.4, № 1. С. 19-30.

23. Ефимушкин В.А., Дедовских Т.В., Салькова М.В. Механизмы управления трафиком в сетях ATM // Электросвязь, 2003. № 1. -С.39-41.

24. Ефимушкин В.А., Дедовских Т.В., Салькова М.В. Механизмы управления потоками класса ABR в сетях ATM // Электросвязь, 2003. № 3. С.33-36.

25. Ершов В.А., Кузнецов Н.А. Мультисервисные телекоммуникационные сети // М.: Изд-во МГТУ им. Н.Э. Баумана, 2003.-432 с.

26. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ // М.: Радио и связь, 1988.

27. Клейнрок Л. Теория массового обслуживания // М.: Машиностроение, 1979. 432 с.

28. Клейнрок Л. Вычислительные системы с очередями // М.: Мир, 1979.-600 с.

29. Климов Г.П. Стохастические системы обслуживания // М.: Наука, 1966.-244 с.

30. Концепция развития отрасли «Связь и информатизация» Российской Федерации / Под ред. Л.Д. Реймана, Л.Е. Варакина // М.: Изд-во Международной академии связи, 2001. 340 с.

31. Кох Р., Яновский Г.Г. Эволюция и конвергенция в электросвязи // М.: Радио и связь, 2001.-280 с.

32. Лагутин B.C., Степанов С.Н. Телетрафик мультисервисных сетей связи // М.: Радио и связь, 2000. 320 с.

33. Дедовских Т.В. Дискретная система массового обслуживания с групповым потоком фазового типа и пороговым управлением // Вестник РУДЫ. Сер. Прикладная математика и информатика, 2002. № 1.-С.107-118.

34. Наумов В.А. Численные методы анализа марковских систем // М.: Изд-во РУДН, 1985.-36 с.

35. Нейман В.И. Структуры систем распределения информации // М.: Радио и связь, 1983.

36. Рыков В.В. Сети обслуживания прозрачных требований // Автоматика и телемеханика, 2001. №5. С.147-158.

37. Самуйлов К.Е. Системы массового обслуживания ограниченной емкости и их приложение к анализу информационно вычислительных систем / Автореферат дисс. на соискание уч. степени к.ф.-м.н. //М: 1984. 16 с.

38. Севастьянов Б.А. Курс теории вероятностей и математической статистики // М.: Изд-во ИКИ, 2004. 272 с.

39. Соколов И.А. Дискретная СМО с абсолютным приоритетом // Техника средств связи. Серия СС, 1986. Вып.6. С. 69-77.

40. Степанов С.Н. Численные методы расчета моделей с повторными вызовами // М.: Наука, 1983. 229 с.

41. Феллер В. Введение в теорию вероятностей и ее приложения. Т.1 // М.: Мир, 1984. -528 с.

42. Шварц М. Сети связи: протоколы, моделирование и анализ. 4.1// М.: Наука, 1992.

43. Шнепс-Шнеппе Системы распределения информации. Методы расчета//М.: Связь, 1979.

44. ATM Forum Traffic management. Traffic management specification version 4.1, AF-TM-0121.000, March 1999.

45. Arpaci M., Copleland J.A. Buffer Management For Shared-Memory ATM Switches // IEEE Commun. Surveys & Tutorials, 2000. No.l. -Pp.1-10.

46. Bae J.J., Suda T. Survey of Traffic Control Schemes and Protocols in ATM Networks // Proc. IEEE, 1991. No.79. Pp. 170-189.

47. Bernet Y. Networking Quality of Service and Windows Operating Systems // NY: New Riders Publ., 2001. 702 p.

48. Blondia C. A Discrete-time Batch Markovian Arrival Process as B-ISDN Traffic Model. // Belgian J. of Operations Research, Statistics and Computer Science, 1992. No.3. Pp.3-23.

49. Blondia C., Casals O. Statistical Multiplexing of VBR Sources: A Matrix Analytical Approach. // Performance Evaluation, 1996. No. 16. Pp. 521.

50. Blondia C., Casals O. Buffer and Throughput Analysis of the Explicit Rate Congestion Control Mechanism for ABR Services in ATM Networks / COST 257 Final Report. Eds. Tran-Gia P., Vicari N. // 1997. -Pp.1-11.

51. Bocharov P.P., D'Apice C., Pechinkin A.V., Salerno S. Queueing theory // Ultrecht Boston: VSP, 2004.

52. Bocharov P.P., Naumov V.A. Matrix-geometric stationary distribution for the PH/PH/l/r queue // Elektron. Informationsverarb. Kyb. 1986. No.4.-Pp.179-186.

53. Briem U., Wallmeier E., Beck C., Matthiese F. Traffic Management for an ATM Switch with Per-VC Queuing: Concept and Implementation // IEEE Communications Magazine, 1998. No.l. Pp.47-52.

54. Bruneel H. Performance of Discrete Time Queueing Systems // Computers and Operations Research, 1993. V.20. Pp. 303-320.

55. Bruneel H., Kim B.G. Discrete-Time Models for communication systems including ATM // Boston: Klumer Academic Publ., 1993.

56. Charny A. An Algorithm for Rate Allocation, in a Packet-Switching Network with Feedback. Master thesis, MIT TR-601, May 1994.

57. Choudhury А. К., Hahne E. L. Dynamic Queue Length Thresholds for Shared-Memory Packet Switches // IEEE/ACM Trans. Commun., Apr. 1998. No.2.-Pp. 130-40.

58. COST-257. Final Report. Impacts of New Services on the Architecture and Performance of Broadband Networks . Eds. Tran-Gia P., Vicari N.

59. Daduna H. Discrete Time Queueing Networks. Recent Developments // Tutorial Lecture Notes. Performance' 96, Lausanne, 1996.

60. Efimushkin V., Ledovskikh T. Performance evaluation of discrete time queueing system with variable buffer capacity // Proc. of the 19-th International Teletraffic Congress, Beijing, August 29 September 2, 2005, V.6C. - Pp.2081-2090.

61. Fiems D., Walraevens J., Bruneel H. The Discrete-Time Gated Vacation Queue Revisited // Int. J. of Electronics and Communications (AEU) 2004, 58.-Pp.136-141.

62. Gelenbe E., Mang X., Onvural R. Bandwidth Allocation and Call Admission Control in High-Speed Networks // IEEE Commun. Mag., 1997. No.5. Pp. 122-129.

63. Irland M. Buffer Management in a Packet Switch // IEEE Trans. Commun., 1978. No.3. Pp.328-337.

64. Ishizaki F., Takine Т., Takahashi Y., Hasegawa T. A generalized SBBP/G/1 queue and its applications // Proc. of Int. Conf. Modelling and

65. Performance Evaluation of ATM Technology. La Martinique, French Carribean Island, 1993. Pp. 1-21.

66. Iversen V.B. Teletraffic Engineering Handbook // Geneve: Publ. of ITU-D, 2002.-323 p.

67. ITU-T Recommendation 1.371. Traffic Control and Congestion Control in B-ISDN, March 2004.

68. Kalyanarama S., Jain R., Fahmy S., Vandalore B. The ERICA Switch Algorithm for ABR Traffic Management in ATM Networks. // IEEE/ACM Trans, on Networking, 2000. No.8.

69. Kalyanarama S., Jain R. ERICA+ Extension to the ERICA Switch Algorithm // ATM Forum/95-1346,1995.

70. Kamolphiwong S., Karbowiak A., Mehrpour H. Flow Control in ATM Networks: Survey // Computer Communications, 1998. No.21. Pp.951968.

71. Kamoun F., Kleinrock L. Analysis of shared finite storage in a computer networks under general traffic conditions // IEEE Trans. Сотр., 1980. No.7. Pp.982-1003.

72. Karam M.J., Tobagi F.A. Rate and Queue Controlled Random Drop (RQRD): A Buffer Management Scheme for Internet Routers // Proc. of Globecom '2000, San Francisco, CA.

73. Kim D., Cho Y. Analysis of Relative Rate Switch Algorithms for ABR Flow Control in ATM Networks. // IEICE Transactions on Communications, 1999. No.10. -Pp.1586-1594.

74. Kobayashi H., Konheim A. Queueing Models for Computer . Communications System Analysis // IEEE Trans. Commun., 1977. No.l.-Pp. 2-29.

75. Krishnan S., Choudhury A.K., Chiussi F.M. Dynamic Partitioning: A Mechanism for Shared-Memory Management // Proc. IEEE INFOCOM '99, Mar. 1999. Pp.144-152.

76. Latouch G. Exponential Servers Sharing a Finite Storage: Comparison of Space Allocation Policies // IEEE Trans. Commun., 1980. No.6. -Pp.910-915.

77. Ledovskikh Т., Nurmiev M., Zharkov M. The calculation of a delay using the SSCOP error correction mechanism // Amendment to the new ITU-T Recommendation Q.738. January 2001. Geneve, ITU-T, SG2, D.l. -6 p.

78. Ledovskikh T. Addendum to Delayed Contribution D-l. September ► 2001. Geneve, ITU-T, SG2, TD GVA-X. 4 p.

79. Mottonen K. W-ERICA: A Simple and Efficient ABR Control Algorithm // Technical Report 26. Cost 257, 1997.

80. Neuts M.F. Matrix-Geometric Solution in Stochastic Models // The Johns Hopkins University Press, Baltimore, 1981.

81. Nong G, Hamdi M. On the Provision of Quality-of-Service Guarantees « for Input Queued Switches // IEEE Commun. Magazine, 2000. No. 12.1. Pp.62-69.

82. Park D., Perros H.G. m-MMBP Characterization of the Departure Process of an m-MMBP/Geo/l/K Queue // Proc. 14th Int. Teletraffic Cong., 6-10 June 1994. North-Holland Elsevier Science B.V., 1994. Vol.1.-Pp.75-84.

83. Perros H.G., Elsayed K.M. Call Admission Control Schemes: A Review , // IEEE Commun. Mag., 1996. No. 11. Pp.82-91.

84. Slosiar R. Busy and Idle Periods at an ATM Multiplexer Output Resulting from the Superposition of Homogeneous ON/OFF Sources // Proc. ITC 14,1994.-Pp.431-440.

85. Su D., Golmie N., Chang D. More on the Simulation Study of the Rate-Based and Credit-Based Traffic Management Mechanisms. // IEEE Network Magazine, 1995. No.4. Pp.49-56.

86. Thareja A.K., Agrawala A.K. On the Design of Optimal Policy for Sharing Finite Buffers // IEEE Trans. Commun., 1984. No.6. Pp. 737740.

87. Tran-Gia P. Discrete-time analysis for the interdeparture distribution of G1\G\\ queues / In: Teletraffic Analysis and Computer Performance Evaluation. Eds. Boxma O.J., Cohen J.W., Tijms H.C. // North-Holland Elsevier.-Pp.341-3 57.

88. Walraevens J., Fiems D., Bruneel H. Transient Analysis of A Discrete-Time Priority Queue // Proc. of the 12th Int. Conf. on Analytical and Stochastic Modelling Techniques and Applications. Riga, Latvia, 1-4 June 2005. Pp. ASMTA 05-18.

89. Wilkinson N. Next Generation Network Services: Technologies & Strategies // Chichester: John Wiley & Sons, Ltd., 2002. 197 p.

90. Woodward M.E. Communication and Computer Networks: Modelling with Discrete-Time Queues // Washington: IEE Pres, 1994.

91. Wu G.-L., Mark J. W. A Buffer Allocation Scheme for ATM Networks: Complete Sharing Based on Virtual Partition // IEEE/ACM Trans. Networking, 1995. No.6. Pp. 660-670.