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

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

Аленичев Алексей Вячеславович

МЕТОДЫ ИССЛЕДОВАНИЯ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С ДИНАМИЧЕСКОЙ МАРШРУТИЗАЦИЕЙ

Специальность 05 13.13 - телекоммуникационные системы и компьютерные сети

АВТОРЕФЕРАТ Диссертации на соискание ученой степени кандидата технических наук

Москва - 2005

Работа выполнена в Московском физико-техническом институте

Научный руководитель-Официальные оппоненты:

Ведущая организация-

кандидат технических наук Н.Б. Лиханов доктор технических наук, профессор П. П. Бочаров

доктор физико-математических наук Н. Д. Введенская

Самарский Государственный Аэрокосмический Университет имени академика С.П. Королева

2005 г. в -Í-Í

1.002.077^1 е

Защита состоится "______11 __ 2005 г. в часов

на заседании диссертационного совета Д.002.077.01 при Институте проблем передачи информации РАН по адресу 127994, Москва, ГСП-4, Б.Каретный пер., 19

С диссертацией можно ознакомиться в библиотеке Института проблем передачи информации РАН.

Автореферат разослан "_____"______________ 2005 г

Ученый секретарь диссертационного совета Д.002.077.01, доктор физико-математических наук

И.И. Цитович

9л <Л-И

Общая характеристика работы

Актуальность. В настоящее время происходит бурное развитие сетей переда^ чи данных: усложняется топология, увеличиваются скорости передачи, предъявляются повышенные требования к качеству обслуживания. Это накладывает дополнительные требования к устройствам и протоколам, обеспечивающим работу сети. Расширение сетей делает все более актуальной проблему выбора маршрута прохождения данных, т.е. маршрутизацию. Одним из видов маршрутизации является динамическая млртр) тизлция, i.e. маршрутизация, которая зависит от текущего состояния системы и относится к семейству протоколов, балансирующих нагрузку в сети В современных сетях функции управления и балансировки потоком возложены на устройства называемые маршрутизаторами Типичной моделью такого маршрутизатора является система взаимодействующих обслуживающих приборов

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

Ряд работ посвящен разработке математического аппарата, дающего возможность изучить поведения систем взаимодействующих приборов и получить аналитические результаты Основной подход, используемый в настоящее время для описания сетей очередей, называемый аппроксимацией среднего поля, был разработан PJI. Добрушиным в начале 70-х и был успешно применен к различным моделям таких систем. Разработанные им методы работают тем лучше, чем "сложнее" система рассматривается. Для определенного класса моделей "сложность" системы может быть измерена через количество N обслуживающих приборов в ней Показано, что при N -¥ оо метод среднего поля дает асимптотически точный результат.

Одной из первых работ, в которой метод среднего поля был применен к системе балансирующей нагрузку, была работа Н.Д. Введенской, P.JI. Добрушина, Ф.И Кар-пелевича1, в которой рассматривалась система с показательным временем обслуживания заявки, состоящая из N приборов, и балансирующая нагрузку по следующему правилу: при поступлении заявки в систему, наудачу выбирается Й-(возможно одинаковых) обслуживающих приборов из N, и заявка становится в очередь минимальной длины. В асимптотике N -Ь оо в работе была получена точная формула вероятности переполнения Оказалось, что с ростом длин вероятность длинных очередей при такой маршрутизации убывает сверхэкспоненциально, что является значительным улучшением по сравнению со случаем, когда заявки направляются в случайно выбранную очередь, в котором убывание экспоненциальное.

'Н.Д. Введенская, P.JI. Добрушин, Ф.И. Карпелевич, Система обслуживания с выбором наименьшей из двух очередей - асимптотический подход. Пробл. передачи информ , 32, № 1, стр 15-27, 1996., _

«И. • • " • .<ГыиГ

■ - • '„КА ^ ( (le <-'.<f>jfn

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

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

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

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

Кроме того, возможность получения аналитических результатов в этих работах связана с тем, что поведение системы рассматривается в предельном переходе N —► оо, когда эволюция системы становится детерминированной Для описания систем с конечным числом обслуживающих приборов используются приближенные результаты, полученные для бесконечных систем.

Появление новых высокоскоростных каналов передачи данных и все большее распространение компьютерных сетей, таких как Интернет, повлекло за собой интенсивные исследования стохастической природы сетевого трафика, которые показали, что традиционные предположения о нем уже не верны. Наряду с пакетным характером трафика, исследования современных сетей показали существование сеансовых зависимостей, которые приводят к значительной корреляции параметров трафика в течение длительного промежутка времени (времени сеанса). Оказалось так же, что в трафике присутствуют заявки, имеющие достаточно медленно убывающее, по сравнению с экспоненциальным, распределение времени обслуживания К такого рода зависимостям времени обслуживания приводит рассмотрение мультипроцессор ных систем с существенно разнородными командными запросами, распределенных файловых систем и множества других систем. Исследования сетей и систем, обеспечивающих высокое качество обслуживания, к которым относятся все вышеперечисленные, приводят к тому, что требуется оценивать вероятность редких событий. Компьютерное моделирование таких систем затруднено, т.к. приходится иметь дело с событиями, происходящими с вероятностью порядка 10~6 — Ю-9. Предложенные ранее методы исследования также перестают работать, т.к. время обслуживания заявок крайне неоднородно и требуется с высокой точностью получить аналитические результаты для систем с конечным числом обслуживающих приборов. Поэтому, осо-

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

В данной работе рассматривается модель системы, балансирующей нагрузку, в которой количество обслуживающих приборов N конечно, время обслуживания заявок имеет медленно убывающее распределение, в приближении, когда входные буферы устройств бесконечны (г —► оо) Используемое приближение естественно, т.к современным устройствам характерен большой объем встроеной памяти.

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

• анализ существующих методов исследования систем взаимодействующих приборов;

• построение новых методов, дающих возможность производить исследования систем с медленно убывающим распределением времени обслуживания заявок;

• получение простых асимптотически точных формул, позволяющих оценивать параметры качества обслуживания таких систем;

• исследование поведения параметров качества обслуживания при переходе от классического экспоненциального распределения времени обслуживания заявки к степенному.

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

Научная новизна исследований, проведенных в рамках диссертационной работы, заключается в следующем:

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

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

3 Предложен метод выбора оптимальных параметров маршрутизации (величины выборки), обеспечивающих требуемое качество обслуживания.

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

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

Реализация результатов работы. Основные теоретические положения и практические результаты работы были использованы при проведении ОКР ООО Научно-технического центра "ЮРИОН". Реализация результатов работы подтверждена соответствующим актом.

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

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

Публикации. Основное содержание диссертации отражено в 3 научных работах, две из которых написаны в неразделимом соавторстве.

Структура и объем работы. Диссертационная работа состоит и) введения, 2-х глав, заключения и библиографического списка, включающего 98 наименований. Работа изложена на 102 лисгах машинописного текста и содержит 10 рисунков

Основные положения, выносимые на защиту.

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

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

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

4 Результат и методика расчета вероятности переполнения системы взаимодействующих приборов с входными заявками, имеющими Вейбулловское распределение времени обслуживания.

Основное содержание работы

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

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

Основными параметрами качества обслуживания в сети являются вероятность потери и время распространения пакета. Высокие требования к качеству обслуживания в современных сетях передачи данных, приводят к тому что приходился рассматривать системы с вероятностью потери пакета порядка 10 " — Ю-9, т.е иметь дело с редкими событиями. Это существенно усложняет применение компьютерного моделирования и делает особенно ценным получение аналитических результатов

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

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

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

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

Степенной закон распределения времени обслуживания заявок хорошо отражает

стохастические закономерности, обнаруженные в современных сетях

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

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

Заметим, что в отличие от других работ по динамической маршрутизации, количество обслуживающих приборов N конечно Кроме того, обычно, при рассмотрении систем с динамической маршрутизацией предполагается, что наудачу выбирается два сервера, т.с К = 2. В данной работе К произвольно, что позволяет оптимально выбирать этот параметр для построения систем с требуемой вероятностью потери пакета.

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

п\

Если через т(ц| обозначить длину ¿-го запроса, поступившего в систему в момеш времени 4, и предполагая, что т%л случайная величина, имеющая степенное распределение, то верно, что

Р(гм > 1) ~ ах-1-^, при х —>■ оо, где а,р > 0, а под знаком А(х) ~ В(х) понимается, что

1ип 4гт =

х—юо В(Х)

Счи1ае-1сн. что случайные величины т^ являются независимыми и не зависят от входного процесса поступления заявок.

Средняя нагрузка на систему

р = ЛГА^Тод].

Предполагается, что р < N и, следовательно, система стационарна

Если обозначить через номер обслуживающего прибора, в который направляется после маршрутизации ¿-ая заявка, поступившая в систему в момент времени

i, то входной процесс Yttl, поступающий в очередь г-го обслуживающего прибора в каждый момент времени t, ■задается как

е,

YU = г),

3=1

где 1(А)- индикатор события А.

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

Wti, = №-!, +п.

где х+ = тат(0, х), а С, = 1, г = 1 N скорость обслуживания г-го прибора

Остаточное время обслуживания заявок находящихся в очереди, выбранной при маршрутизации виртуальной заявки в момент времени t, обозначено как Dt и определено как

А = Щ-\,х,, •

Под переполнением системы подразумевается попадание виртуальной заявки при маршрутизации в очередь сервера с остаточным временем обслуживания находящихся в нем заявок, превышающим уровень «о, т.е D, > го, для достаточно больших za без учета времени обслуживания поступившей заявки Рассматривается поведение стационарной вероятности переполнения системы.

Основные результаты первой главы: получены следующие асимптотически верные формулы (теоремы 1.1, 1.2) для вероятности переполнения системы с динамической маршрутизацией и степенным распределением времени обслуживания заявок: Если р < N - К, то при го оо верно, что

Иначе, при z0 -> оо верно,что где

щ = arg min (n).

Выражение (1) позволяет исследовать случай, когда нагрузка в системе невелика, а именно р < N — К. В этом случае вероятность переполнения в системе сильно зависит от количества случайно выбираемых при маршрутизации очередей, т.к. их количество К стоит в показателе экспоненты z0. Поэтому, увеличивая количество выбираемых при маршрутизации очередей, можно существенно уменьшить

вероятность переполнения системы Этим надо руководствоваться при построении системы с требуемым С}оЗ, рассчитывая необходимые параметры маршрутизации по формуле (1).

Выражение (2) применимо в случае, когда на систему поступает существенная нагрузка, а именно 3«1 < К : р> N — Пх.В этом случае вероятность переполнения системы имеет другой вид зависимости от количества выбираемых при маршрутизации очередей. А именно, при увеличении количества выбираемых очередей, начиная с определенного значения

вероятность переполнения перестае! существенно уменьшаться, т к. зависимость по К переходит из показателя экспоненты в константу перед ней Поэтому при выборе параметров маршрутизации, обеспечивающих максимальные параметры С^оБ для данной системы, не стоит увеличивать количество выбираемых при маршрутизации очередей больше щ- это не приведет к значительному уменьшению вероятности переполнения в системе.

Доказательство полученных результатов производится методом граничных оценок.

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

Как доказано, типичное переполнение рассматриваемой системы с динамической маршрутизацией в случае, когда р < N -К, вызывается одновременным присутствием в момент времени % в К различных очередях системы одиночных заявок, каждая из которых имеет остаточное время обслуживания превышающее го.

В случае же, когда 3п < К р > N — п, доказано, что типичной конфигурацией, вызывающей переполнение системы, является следующее событие: в системе в момент времени I ъ п различных очередях находятся одиночные заявки, каждая из которых имеет остаточное время обслуживания, превышающее «о и все они пришли в систему не позднее чем г - гь где

Доказательство верхней границы производится значительно сложнее и базируется на разбиении входного потока в систему на короткие(т < его) и длинные заявки(г > его), то есть

щ = ата шш (п), я N-1,<п<кк "

п)

N — п

у< = У/ +

= > ег0),

It

Yl = < "о),

j=i

и рассмотрении влияния процессов Yt' и Yth на переполнение системы.

В доказательстве активно используются результаты, полученные для системы с одним обслуживающим прибором и степенным законом распределения длин заявок, полученные Н. Лихановым и Р Мазумда2, заключающиеся в том, что процесс К/ ведет себя в среднем как р.

Оказывается, что в следствии этого, в системе взаимодействующих приборов, на которую поступают заявки только из входного процесса У/, длины очередей обслуживающих приборов проявляют групповые свойства На чем и основано дока зательство верхней границы вероятности переполнения системы

Во второй главе рассматривается поведение системы с динамической маршрутизацией балансирующей нагрузку в сети в случае, когда время обслуживания заявок имеет распределение Вейбулла

Исследование систем с динамической маршрутизацией и входными заявками, имеющими степенное распределение времени обслуживания, произведенные в ыа-ве 1, показали, что для того чтобы обеспечить такое же качество обслуживания, как при классической модели трафика, в этом случае необходимо значительно увеличив размер входного буфера. Это вызвано тем, что при классической модели трафика, хвост стационарного распределения нагрузки буфера убывает сверхэкспоненциально, а в рассмотренной модели более медленно - по степенному закону.

Как с практической так и с теоретической точки зрения интересно рассмотреть класс источников, на которых происходит переход от классического поведения нагрузки буфера к степенному Известно, что для однородного входного потока переход происходит на источниках с Вейбулловским распределением длины сеанса т при а 6 (0,1).

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

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

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

2N. Likhanov and R Mazumdar, Loss asymptotics in large buffers fed by heterogeneous long-tailed sources, Advances in Applied Probability, 2000, no.32, pp 1168-1189.

распределения времени обслуживания заявки.

Исследование базируется на методах предложенных в главе 1.

Определения входного процесса, поступающего в г'-ую очередь, длины очереди, события переполнения системы, и метода маршрутизации заявок полностью совпадают с данными ранее.

В отличае от ранее сформулированного, rtJ - случайная величина, соответствующая времени обслуживания j-ro запроса, поступившего в систему в момент времени t, имеет распределение Вейбулла, то есть

P(t(j > х) ~ е~ух°, при х оо,

где а £ (0,1),7 > 0 Случайные величины r(J взаимно независимы и не зависят от входного процесса.

Для вероятности переполнения системы получены следующие основные формулы:

Если существует пi такое, что

щ = arg^ mjn_^(ri ■ да(п) : п - да(п) < К), (3)

то верно:

р{D > го) „ Kl{N~K)l (—У" (9(„l))ni(1-a)e-n'(i°(ni^+(a-(4) rii!iV! \ ог) )

Иначе, верно, что

Р(£> >гоЬ fcS! к (5)

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

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

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

В отличав от случая заявок со степенным распределением времени обслуживания, для которых при р < N — К оптимальной была конфигурация, когда в системе в момент t находится К заявок c остаточным временем обслуживания, превышающим пороговое значение го, при Вейбулловском распределении времени обслуживания, оптимальной будет конфигурация, когда эти заявки пришли в систему практически одновременно (на отрезке порядка o(zo)). Это является следствием более резкого убывания вероятности возникновения заявки с большим временем обслуживания в распределении Вейбулла, по сравнению со степенным.

Построение оптимальной конфигурации для случая р> N — К гораздо сложнее и приводит к необходимости рршать нелинейную оптимизационную задачу, выраженную формулой (3) По сравнению с оптимальной конфигурацией для степенного распределения времени обслуживания, когда переполнение происходило, если "большие" заявки стояли в

П| = arg min (n)

очередях, а остальные очереди переполнялись "маленькими", в случае распределения Вейбулла, даже при р > N -К, оптимальной может быть конфигурация из К заявок с остаточным временем обслуживания превышающим пороговое значение z0.

Доказательство, производится методом граничных оценок.

Наиболее технически сложным, является получение верхней границы вероятности переполнения. При доказательстве производится декомпрессия входного потока на "короткие"(т < ez) и "длинные"(т > ez) заявки, и рассмотрение вклада этих процессов в переполнение системы

В заключении сформулированы основные результаты, полученные в диссертационной работе:

1 Предложена новая математическая модель и методы исследования систем с динамической маршрутизацией, балансирующей нагрузку с заявками имеющими медленно убывающее распределение времени обслуживания

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

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

4. Разработан метод выбора оптимальных параметров маршрутизации (величины выборки), обеспечивающих требуемое качество обслуживания системы.

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

1 Аленичев А В , Лиханов Н Б Оценка вероятности переполнения буфера в системе с неоднородными источниками и ограниченной длиной сеанса. XIV научная конференция МФТИ, Тезисы докладов, часть I, Москва-Долгопрудный, 2002 с.26

2 Аленичев А В , Лиханов Н Б Динамическая маршрутизация в системе с заявками, имеющими степенной закон распределения времени обслуживания Информационные процессы, Москва. 2005. т. 5, №3, с 213-226,(чгигиг..рр ги).

3 Аленичев А.В Система массового обслуживания с динамической маршрутизацией и распределением Вейбулла времени обслуживания заявок Информационные процессы, Москва 2005 т 5, №5, с 431-441 (www.jip.ru).

к исполнению 21/11/2005 Исполнено 22/11/2005

Заказ № 1340 Тираж: 100 экз.

ООО «11-й ФОРМАТ» ИНН 7726330900 Москва, Варшавское т., 36 (095) 975-78-56 (095) 747-64-70 www.autoreferat.ru

(У<У , *

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

2007-4 4285

Получено з 1 г::э ¿006

Введение

Алгоритмы распределения нагрузки

Известные аналитические результаты.

Анализ существующих моделей.

Экспериментальные данные.

Модель и методы исследования.

Результаты, полученные в диссертационной работе.

Структура работы.

1 Система с динамической маршрутизацией и степенным законом распределения времени обслуживания заявок

1.1 Введение.

1.2 Модель и предварительные результаты.

1.3 Доказательство полученных результатов.

2.2 Модель и предварительные результаты.59

2.3 Доказательство полученных результатов.63

2.4 Заключение.74

2.5 Приложение: доказательство вспомогательных лемм.78

Заключение 85

Список иллюстраций

1 Среднее время обслуживания заявок в сервис-кластере с различными алгоритмами динамической маршрутизации. 9

2 (а) Распределение времени обслуживания процессов с длительностью, превышающей 1 секунду. Толстая линия соответствует полученным экспериментальным данным, тонкая - приближению функцией гТк , полученному методом наименьших квадратов.(Ь) Тоже самое распределение в логарифмическом масштабе. Прямая линия покалывает приближение rTfc, где к угол наклона графика. 23

3 В логарифмическом масштабе показаны: толстой линией наблюдаемое распределение времени обслуживания процесса(исследовано более 13000 процессов), и два приближения, полученные методом наименьших квадратов. Первое приближение соответствует гипотезе Pr(x > Т) ~ гхк, второе общепринятой Pr(x > Т) ~ се~АГ.24

4 Блок-схема модели системы обслуживания. 30

5 Вероятность переполнения системы в зависимости от величины выборки К в случае р < N — К. 50

6 Вероятность переполнения системы в зависимости от величины выборки К в случае, когда Зп < К : р> N — п. 51

7 Вероятность переполнения системы в зависимости от величины выборки К в случае р < N — К. 75

8 Вероятность переполнения системы в зависимости от величины выборки К в случае, когда существует решение оптимизационной задачи и р> N -К. 76

9 Эмпирическая плотность распределения вероятностей времени между установлениями TCP/IP соединений во внешнем сегменте сети AT&T

18 Ноября-8 Декабря 1995. 90

10 Эмпирическое дополнительное распределения вероятностей времени между установлениями TCP/IP соединений и приближения, полученные методов наименьших квадратов, во внешнем сегменте сети AT&T

18 Ноября-8 Декабря 1995. 91

Введение

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

Алгоритмы распределения нагрузки

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

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

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

Методы решения:

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

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

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

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

Наряду с рассмотренными выше алгоритмами маршрутизации, существуют и другие методы распределения нагрузки, в которых, учитываются специфические требования, возникающие в реальных системах.

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

Кроме того, разработаны методы маршрутизации, которые описывают системы с приоритетами. Типичным предположением для таких алгоритмов является то, что с вероятность р в систему приходят обычные заявки, а с вероятностью 1 — р приоритетные. При этом, считается, что приоритетные заявки имеют право выбора минимальной очереди, а обычные просто направляются в случайно выбранный обслуживающий прибор.

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

В качестве примера приведем результаты эмпирических исследований проведенных в работе [52|. В ходе экспериментов авторы работы производили сравнение эффективности алгоритмов динамической маршрутизации в условиях современного кластера обслуживания. Под кластером обслуживания авторы подразумевали замкнутую подсеть, состоящую из различных серверов, подсоединенную к сети пользователей через высокоскоростной внешний интерфейс. Эмитациопное моделирование производилось на основании статистики трафика, записанного в течении недели в июле 2001 года в двух внутренних кластерах обслуживания поисковой системы Теота . Один кластер системы отвечал за перевод запрашеваемых пользователем слов во внутреннее представление системы. Другой, - за аналогичный перевод описания Web-страниц. В результате исследований трафика, авторы выяснили, что входной поток первого кластера, далее 'Трафик 1", имеет среднее время обслуживания - 22 мс, а поток второго, называемый далее 'Трафик 2", - 208,9 мс. В ходе эмитационного моделирования записанный поток подавался на систему из 16 серверов через коммутатор Lucent Р550 с полосой пропускания 22Гбит/с. Распределение поступающих запросов между серверами производилось в соответствии с различными алгоритмами динамической маршрутизации, балансирующей нагрузку. Авторы сравнивали следующие, рассмотренные нами выше, алгоритмы: динамическая маршрутизации со случайным выбором очереди (random), маршрутизация с выбором минимальной из A;(polling к) случайных очередей, и маршрутизация с выбором минимальной во всей системе очереди (ideal). Исследования проводились для трех различных входных потоков: 'Трафика 1", 'Трафика 2" и искусственного Пуассон/Эксп. трафика, в ходе моделирования которого, полагалось, что количество поступающих в систему заявок в каждый момент времени имеет распределение Пуассона, время обслуживания заявки имеет экспоненциальное распределение со средним 50. Результаты эмитационного моделирования приведены на Рис. 1. По оси абсцисс отложен уровень загрузки сервера, по оси ординат среднее время обслуживания заявок.

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

1. Метод выбора минимальной очереди из случайного подмножества всех очередей системы (polling к) значительно превосходит простой метод, когда задача поступает в очередь на обслуживание случайно выбранного cepBepa(random).

Трафик Пуассон/Эксп.

Трафик 1

50% 60% 70% 60% 00%

Уровень загрузки сервера О

50%

60% 70% В0% 90%

Уровень загрузки сервера

Трафик 2

600

50% 60% 70% ао% 00%

Уровень загрузки сервера

1. Среднее время обслуживания заявок в сервис-кластере с различными алгоритмами динамической маршрутизации

2. Оказывается, что ресурсоемкий метод выбора минимальной очереди во всей системе(-1с1еа1) не дает значительного улучшения по сравнению с более простым методом с выбором из случайного подмножества очередей cncTeMbi(polling к).

3. Увеличение длины выборки к в методе с выбором минимальной очереди из иод-множества всех очередей (polling к) не приводит к существенному уменьшению среднего времени обслуживания заявки.

Результаты приведенных выше эмпирических исследований, а также многих других эмитационных работ(нанример [96], [78]) подтверждают эффективность алгоритма динамической маршрутизации с выбором минимальной очереди из случайного подмножества всех очередей. Однако, в некоторых случаях, проведение моделирования может быть затруднено. Так, например, исследование динамической маршрутизации в системах с высокими требованиями к качеству обслуживания, приводит к необходимости моделировать редкие события, с вероятностью появления порядка Ю-6 — 10~9. В этих случаях, предпочтительным способом исследования систем являются аналитические методы. Рассмотрим далее существующие аналитические методы исследования систем с динамической маршрутизацией и приведем полученные в ходе них результаты.

Известные аналитические результаты

Один из подходов, используемый в настоящее время для описания систем с динамической маршрутизацией, называемый методом среднего поля, разработан P.JT. Добрушиным в начале 70-х годов и успешно применен для исследования различных моделей сетей взаимодействующих очередей. Для детального описания рассматривавшихся систем и методов исследования достаточно обратиться к оригинальным статьям [14], [16], [29], [54], [57], [58], [88], [32], обзорам [30|, [55], [59], и работам [63], [75], [76]. Исследования P.JI. Добрушина были вызваны тем, что стандартные методы теории массового обслуживания, разработанные для простых систем с одним обслуживающим прибором, не удавалось использовать для систем взаимодействующих обслуживающих приборов. В ходе своих исследований Р.Л. Добрушин показал, что для рассматриваемых им моделей в асимптотике при бесконечной "сложности" системы, поведение системы становится детерменированным и может быть описано бесконечной системой дифференциальных уравнений. Поэтому, разработанные им методы работают тем лучше, чем "сложнее" система рассматривается. Для определенного класса моделей "сложность" системы может быть измерена через количество N обслуживающих приборов в ней. Показано, что при N —> оо метод среднего поля дает асимптотически точный результат для широкого круга систем.

Для описания систем с динамической маршрутизацией, балансирующей нагрузку, метод среднего поля впервые был применен в работе Н.Д. Введенской, Р.Л. Добруши-на, Ф.И. Карпелевича [92], в которой рассматривалась система с экспоненциальным распределением времени обслуживания заявок и пуассоновским входным потоком их поступления интенсивности NX, состоящая из N обслуживающих приборов, и балансирующая нагрузку по следующему правилу: при поступлении заявки в систему, на удачу выбирается г обслуживающих приборов из N и заявка становится в очередь минимальной, из выбранных, длины. Оказалось, что в приближении N —> оо можно получить асимптотически точную формулу вероятности переполнения системы. Сформулируем основной результат, полученный авторами: если обозначить через tifc-долю приборов, длина очереди в которых не меньше чем к, то верно lim ЕNuk = Х^-Шг-D

N—> оо

Если сопоставить полученный ими результат с аналогичной формулой для классического случая, когда в системе имеется N пуассоновских потоков интенсивности Л, и каждый из них обслуживается своим прибором с экспоненциальным распределением времени обслуживания, и в соответствии с формулой Эрланга:

Е Nuk = Afc, то оказывается, что возможность выбора одного из г приборов существенно уменьшает вероятности длинных очередей, а именно, для случая рассмотренного в статье, с ростом длин очередей вероятности длин убывают сверзкспонешщально, в отличие от экспоненциального убывания в классическом случае.

В качестве модели системы, авторы рассматривали однородную по времени цепь Маркова с пространством состояний Хдг = (Z)N, где Z-множество неотрицательных целых чисел. Если через компоненту вектора х = (х\,., х^) £ Х^, X; обозначить длину очереди г-го прибора, то цепь Маркова задается производящим оператором bnrx) = Ei:ii>i № - еО - /(х))+

V {Еи«4<х, (Л* + *) - Л®)) + Еиw ((Л® + е,) + f(x + ej))/2 - f(x))} , где ej-вектор, г-я координата которого равна единице, а остальные равны нулю.

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

-^ = uk+1(t) - uk(t) + АСК.^))2 - (uk(t))2)yk =1,2,., u0(£) = 1.

Развитием идей, предложенных в статье [92], послужила работа Н.Д. Введенской и Ю.М. Сухова [93], в которой рассматривалась обобщенная модель системы с динамической маршрутизацией. Авторы рассматривали систему, состоящую из большого числа идентичных серверов, имеющих бесконечные входные буферы и работающих в соответствии с дисциплиной обслуживания FIFO. Процесс поступления заявок в систему - пуассоиовский с интенсивностью AN, времена обслуживания заявок - независимые случайные величины, независящие от входного потока. Авторы рассматривали следующий алгоритм маршрутизации: каждая приходящая в систему заявка поступает на обслуживание в сервер, который выбирается из некоторого случайно выбранного подмножества обслуживающих приборов т N на основании фиксированного способа маршрутизации. Авторы доказали, что для широкого класса способов маршрутизации статистические свойства предельного при N —» со процесса детерминированы. Разработанный в статье, математический аппарат был использован для исследования конкретных способов маршрутизации. В частности, был рассмотрен случай, когда при маршрутизации заявки случайно выбирается т обслуживающих приборов и заявка направляется в прибор с s-ой по величине длиной очереди. При s = 1 - имеем стандартный способ маршрутизации, когда заявка направляется в очередь минимальной длины из выбранных, при ,<? = т имеем способ маршрутизации, когда заявка поступает в очередь максимальной длины. Выбор параметра s обусловлен конкретикой решаемой задачи, так например в некоторых случаях желательно иметь в системе небольшое количество относительно свободных очередей для обслуживания запросов наиболее критичных ко времени исполнения, для обеспечения этого логично использовать маршрутизацию с s > 1. В статье был рассмотрен также, так называемый, обобщенный пороговый метод динамической маршрутизации. В рамках него полагалось, что при поступлении в систему заявки в каждый последующий момент времени случайно выбирается тестовая очередь, длина которой сравнивается с некоторой фиксированной константой К. Если длина очереди оказалась меньшей или равной К - заявка направляется в нее, иначе тестируется следующая очередь. Если за т испытаний, очередь выбрана не была, то заявка направляется в последнюю очередь, независимо от ее размера. Если обозначить через Ufc - долю приборов в системе с длиной очереди, не превышающей к, а под 7Tfc подразумевать стационарное значение Uk предельной системы, то есть считать тгк = Птдг—эо Ед-иь то результат, полученный авторами, можно представить в следующем виде:

7Tfc = 1гК(\тт%~1)к-К где к > К, 0 < тгК < 1.

В зарубежных публикациях для описания систем взаимодействующих очередей был независимо разработан подход, аналогичный методу среднего поля P.JI. Доб-рушина. Для детального описания предложенной методологии можно обратиться к статьям [95], [97], [72], [48], [49], обзорам [60], и последующим работам [43], [44), [45].

Методы управления потоком посредством динамической маршрутизации с выбором минимальной очереди из случайного подмножества всех очередей системы аналитически исследовались Ягером в работах [33], [34], [35], моделирование производилось в работе Зоа [96]. Ягер использовал в своих работах марковскую модель системы, однако в ней он полагал, что состояние каждой очереди системы стохастически независимо от состояния других очередей. Это приближение верно в асимптотике, когда количество очередей стремится к бесконечности. Работы Зоа эмпирически оценивали эффективность методов балансировки нагрузки, предложенных в работах [33], [34], [35], используя при этом так называемое потоковое моделирование, в ходе которого, записанный в течении длительного промежутка времени трафик некоторой реальной системы подавался на моделируемую систему. И Ягер, и Зоа в своих работах пришли к выводу, что алгоритмы динамической маршрутизации, в которых производится выбор из некоторого подмножества доступных обслуживающих приборов, достаточно эффективно балансируют нагрузку. Дальнейшие исследования в этой области продолжил М. Митценмахер.

В своей работе М. Митценмахер [78] рассмотрел пороговый метод динамической маршрутизации, в рамках которого полагалось, что входной ноток заявок в систему из N приборов - пуассоновский с интенсивностью XN, время обслуживания заявок -экспоненциальное со средним равным 1. При поступлении заявки в систему на удачу выбирается один прибор, и длина его очереди сравнивается с пороговым значением Т, если она меньше или равна Т, - заявка поступает в эту очередь. Иначе, случайно выбирается следующая очередь, и заявка поступает в нее. Автором получены следующие результаты: в предыдущих обозначениях ттт+\ является единственным решением следующего уравнения на отрезке [0,1] ! (1-А)[((1 + 7ГГ+1)А)Г+1-1] (1 + 7ГГ+1)Л - 1 и для щ = lim/voo Е^Щ верно, что

7Ti = TTi-1 — А(7Гг2 - TTj—1)(1 + 7Tr+i)

Автор указал, что для порогового метода, рассмотренного в статье, с ростом длин очередей вероятности длин убывают не сверхэкспонепциальио, как в случае системы с выбором минимальной очереди из случайного подмножества всех очередей, а гораздо медленней, хотя скорость может быть достаточно большой, если ттт+\ мало. В этой же работе рассмотрен случай пороговой маршрутизации, в котором заявка после выбора второй очереди, становится в минимальную из выбранных. Для этого случая доказано, что с ростом длин очередей вероятности длин убывают сверэкс-поненциалыю.(Лемма 12 [78]). Эмпирические исследования, проведенные в [96], [33], подтвердили этот результат.

Другой алгоритм балансировки нагрузки, в котором заявки при маршрутизации поступают в очередь минимальной во всей системе длины, также хорошо изучен рядом авторов. Результаты и детальное описание модели можно найти в работах [2],

3], М

Модели, балансирующие нагрузку, изучались и в статическом случае, когда необходимо распределить фиксированное количество задач на постоянное обслуживание, как в хеш-таблице. Например, в работе [56] авторы показали, что использование для этого двух хеш-фуикций вместо одной, может дать экспоненциальное уменьшение максимальной нагрузки буфера. Дальнейшее исследование и развитие этой идеи было произведено в работе [11].

Большие уклонения в системах с динамической маршрутизацией для случая экспоненциального обслуживания изучались в работе Тернера [90]. В качестве модели автор рассматривал систему обслуживания, состоящую из двух обслуживающих приборов с бесконечными входными буферами и экспоненциальным распределением времени обслуживания заявок, и полагал, что в систему поступает три пуассоновских потока заявок. Два потока фиксировано направляются на разные обслуживающие приборы, а третий состоит из заявок, маршрутизируемых в момент поступления в прибор с наименьшей очередью. В результате проведенного исследования, автором были получены асимптотически точные формулы для логарифма вероятности переполнения системы.

Дальнейшее исследование больших уклонений в системах, балансирующих нагрузку, продолжили Е.А.Печерский, Ю.М.Сухов и Н.Д.Введенская [84]. В своей работе они рассматривали аналогичную приведенной выше модель системы обслуживания с динамической маршрутизацией, состоящую из двух обслуживающих приборов и трех входных пуассоновских потоков заявок. Однако, в отличие от работы Тернера, авторы полагали, что времена обслуживания заявок являются независимыми, одинаково распределенными случайными величинами с неизвестной функцией распределения. В статье получена асимптотически точная формула логарифма вероятности переполнения системы. Сформулируем полученные авторами результаты. Обозначим через A= 0,1,2 интенсивности входных пуассоновских потоков заявок E!o,Hi,!E2 соответственно и положим, что заявки из потока Si фиксированно направляются в первый обслуживающий прибор, заявки из потока Н2 во второй обслуживающий прибор, а заявки из Но при поступлении в систему направляются в прибор с очередью минимальной длины. Обозначим через S^ случайную величину, соответствующую времени обслуживания заявок из г-го потока, а через = Ee0S(o ее преобразование Лапласа. Через Wi, W2 обозначим длины очередей первого и второго прибора соответственно в момент времени 0, и Wmm — min(Wi, И^). В статье рассматривалось поведение стационарной вероятности переполнения системы в смысле попадания виртуальной заявки после маршрутизации в очередь достаточно большой длины, то есть искалась функция вида

Ud) = lim — logP(Wm<" > nd),d > 0. n—00 П

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

A. Если верно, что Лo(p'0(i9) > lAi^i?) — A2(^2(i?)|, то о (d) = 2 dd.

B. Если верно, что \2<р'2($) > + AoVo(^)> то

I0(d) = d(62 + 0о, i).

C. Если верно, что Aiy?i($) > А+ AoVoC^), то

Io(d) = d(fft + 00,2), где 19 положительное решение уравнения = \ ( Е -1)), t=0,l,2 / a 0i,0o,2 и 02,0о,1 положительные решения следующей системы с i = 2,j = 1 и г = 1, j = 2 соответственно: ft + во j = - 1) + Xj(ipj(e0j) - 1) + A0(^o(^oj) - 1)

A M(6i) = Wj(0oj) + Ao<p'o(0oj).

Заметим, что для получения аналитических результатов и в работе Тернера и в работе Е.А.Печерского, Ю.М.Сухова и Н.Д.Введенской использовалась аналогичная техника исследований. Так как входной поток в серверы в этой модели не является независимым и пуассоновким, для исследования авторы переходили к рассмотрению вспомогательной системы, в которой маршрутизируемый поток разделялся между серверами в некоторой постоянной пропорции на независимые потоки; таким образом, рассматривалась система из двух обслуживающих приборов с независимыми пуассоновскими входными потоками заявок. Затем находилась истинная пропорция, которая возникает в исходной системе в стационарном режиме, и доказывалось, что с ней вероятности переполнения вспомогательной и исходной системы совпадают.

Предложенная техника хорошо работает для системы из двух обслуживающих приборов, но, как указал Тернер [90], применение ее для исследования систем с большим количеством выбираемых приборов затруднено.

Модель системы динамической маршрутизации с выбором из двух обслуживающих приборов, предложенная в работе Тернера [90] и описанная выше, также была изучена в режиме критической нагрузки [91].

Анализ существующих моделей

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

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

Рассмотрение систем с другими распределениями времени обслуживания затруднено. Разработанные для этого методы, например в [78], основываются па, так называемом, методе стадий Эрланга, состоящем в том, что функция распределения любой положительной случайной величины может быть произвольно точно приближена счетной композицией 7-распределений. Так, например, чтобы представить постоянное время обслуживания, необходимо рассматривать каждую заявку, как состоящую из г стадий обслуживания, каждая стадия распределена экспоненциально со средним 1 /г. При увеличении г время обслуживания остается равным 1, а дисперсия уменьшается как 1 /г, поэтому при г —> оо полученная композиция ведет себя как константа. Однако па практике, как указывает автор, для того, чтобы задача была вычислима за конечное время, необходимо, чтобы количество 7-распределений в композиции и количество стадий в каждом 7-распределении было мало, что накладывает существенные ограничения на применение этого метода.

Во-вторых, в основном, во всех работах рассматриваются случаи, когда количество обслуживающих приборов в системе либо бесконечно, либо равно двум. В приближении бесконечного количества обслуживающих приборов, поведение системы обслуживания становится детерминированным, а эволюция состояний непрерывной, что позволяет производить ее исследование. Применение такой асимптотики хорошо подходит для описания систем с большим количеством обслуживающих приборов. Изучение же систем небольшого масштаба, не равного двум, вызывает определенные трудности. При переходе к конечному количеству приборов, необходимому для описания таких систем, приближение осуществляется на основании работ Кур-ца [63], [64], [65] и формул, полученных для бесконечного случая. Теоремы Курца в основном представляют собой закон больших чисел и границы типа Чернова для систем с динамической маршрутизацией.

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

Экспериментальные данные

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

В качестве аргументации сформулированного выше утверждения приведем исследования, проведенные в работе [46]. В этой работе авторы исследовали динамическую маршрутизацию процессов в современных распределенных вычислительных сетях под управлением операционной системы Linux. Целью исследования было сравнение различных способов маршрутизации, необходимых для эффективного использования вычислительных ресурсов. В качестве одного из способов авторы рассматривали следующий: при поступлении в систему нового процесса, из всех узлов выбирается тот, иа котором минимально ожидаемое время исполнения, процесс направляется в этот узел и находится в нем до конца обслуживания. Второй рассматриваемый способ маршрутизации, состоял в том, что при обслуживании некоторого процесса в узле системы, в каждый момент времени на основании текущей длительности исполнения, может быть принято решение о приостановке этого процесса, маршрутизации его в другой узел и перезапуске там. Как показали авторы, ответ на вопрос какой из способов более эффективен существенно зависит от гипотезы о распределении времени исполнения процессов.

Так, в результате ранее проведенных исследований аналогичной системы ( Ягер. [35]),был сделан вывод, что маршрутизация с прерыванием обслуживания не дает значительного улучшения эффективности использования распределенных вычислительных ресурсов, по сравнению с маршрутизацией при поступлении, и поэтому ее применение не целесообразно. В своей работе Ягер полагал, что распределение времени обслуживания задачи вырожденное экспоненциальное,и следовательно в системе обычно находится мало задач с ненулевым временем обслуживания. Автор рассчитал, что при дисперсии вырожденного экспоненциального распределения, равной дисперсии наблюдаемого ими трафика, менее 4% всех задач имеют ненулевое время обслуживания, что, естественно, нивелировало выгоду от маршрутизации с прерыванием исполнения. Результаты, полученные в статье, широко цитировались и были применены при разработке системы Utopia [96].

В результате, как указали, основываясь на своих исследованиях, авторы в [46], выводы, сделанные в работе [35], оказались неверными, прежде всего, потому, что время исполнения процессов плохо аппроксимируется экспоненциальным распределением. Поэтому, для исследования динамической маршрутизации в распределенных вычислительных системах крайне важно точно знать закон распределения времени исполнения процессов. Однако, как указывают авторы, результаты исследований распределения времени исполнения процессов, проведенных ранее, крайне неоднозначны.

Так, Розин еще в 1965 году показал, что в вычислительных системах есть много задач, малых по длительности, и мало - с большой длительностью; дисперсия наблюдаемого распределения больше, чем у экспоненциального.

Последующие исследования, проведенные в 1986 году Леландом и Оттом, уточнили вид распределения. Авторы на основании исследования времени исполнения более 9.5 миллионов UNIX процессов, проведенных в период времени с 1984 по 1985, предложили новую функциональную форму распределения времени исполнения процессов. В ходе исследований, они выяснили интересную закономерность, что, чем больше текущее время исполнения процесса, тем больше его ожидаемое оставшееся время исполнения. Оказалось, что для процессов с большим временем исполнения Т > 3 секунд, вероятность того, что процесс будет исполняться более Т секунд, порядка rTk, где г- нормализующая константа, и —1.25 < к < —1.05. То есть по их измерениям время обслуживания процесса имеет распределение с тяжелым хвостом.

Однако Роммел в 1991 году, основываясь на своих опытных данных, заключил, что "длинные процессы имеет экспоненциальное распределение времени обслуживания". И снова возникла неоднозначность, в следствии чего при проведении многих новых исследований динамической маршрутизации процессов стали предполагать экспоненциальное время обслуживания.

Чтобы разрешить возникшие разногласия, авторы статьи [46] решили провести свои независимые исследования. При проведении их они измерили длительность порядка миллиона процессов, порожденных различными академическими службами, вычислительными, исследовательскими и администраторскими компьютерами. Время исполнения каждого процесса было получено на основании информации команды lastcomm, выводимой на консоль операционной системой UNIX. В результате, основываясь на эмпирических данных, полученных при различных нагрузках, они пришли к выводу, что предложенная Леландом и Оттом функциональная форма распределения времени обслуживания хорошо описывает процессы с рабочим временем большим 1 секунды. Кроме того, они выяснили, что параметр к, в предложенном распределении меняется в пределах —1.3 < к < —0.8.

Результаты измерения длительности процессов на одном из компьютеров приведены на Рис.2. На рисунке отражены только процессы с временем выполнения превышающим 1 секунду. Жирная кривая соответствует наблюдаемому распределению; тонкая кривая отражает приближение экспериментальных данных методом наименьших квадратов функцией вида Тк. Из графика видно, что время выполнения процесса хорошо аппроксимируется предложенным распределением. Для подтверждения полученного результата авторы исследовали гипотезу о распределении времени выполнения процессов методом х2 и получили достоверность порядка 99%. Авторы также произвели сравнение наблюдаемого распределения времени выпол

Дополнительное распределение времени выполнения процессов

Длительность, с

Дополнительное распределение времени выполнения процессов (log)

2. (а) Распределение времени обслуживания процессов с длительностью, превышающей 1 секунду. Толстая линия соответствует полученным экспериментальным данным, тонкая - приближению функцией гТк , полученному методом наименьших квадратов.(Ь) Тоже самое распределение в логарифмическом масштабе. Прямая линия показывает приближение гТк, где к угол наклона графика.

Наблюдаемое распределение и два приближения

3. В логарифмическом масштабе показаны: толстой линией наблюдаемое распределение времени обслуживания процесса(исследовано более 13000 процессов), и два приближения, полученные методом наименьших квадратов. Первое приближение соответствует гипотезе Pr(x > Т) ~ гхк, второе общепринятой

Pr{x > Т) ~ се~хт. нения процесса с приближениями экспоненциальным и степенным распределением, полупенными методом наименьших квадратов. Результаты сравнения приведены на Рис.3. Из рисунка видно, что экспоненциальное приближение времени выполнения процессов в распределенных вычислительных системах является слишком грубым по сравнению со степенным.

Приведенный выше пример системы со степенным распределением времени обслуживания, является не единственным. Существует и множество других примеров систем с такими вероятностными характеристиками обслуживания. Так, например, если возвратиться к рассмотренным выше эмпирическим исследованиям динамической маршрутизации в сервис-кластере, проведенным авторами работы [52|, легко обнаружить, что и в них оказалось, что время обслуживания запросов в сервис-кластере плохо описывается экспоненциальным распределением. Для этого достаточно сравнить поведение системы с одним из записанных реальных трафиков с поведением в случае искуственного Пуассон/Эксп. трафика(Рис.1). Авторы в своей работе указали на это, и сделали заключение, что более подходящими для описания процессов динамической маршрутизации в сервис-кластерах являются модели, когда длительность обслуживания и время между поступлением заявок имеют распределения типа Парето, Вейбулловское, степенное.

Модель и методы исследования

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

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

Система обслуживания состоит из N серверов. Процесс поступления заявки в систему - пуассоновский с интенсивностью NX. Время обслуживания заявок имеет распределение вероятностей с тяжелым хвостом. Рассматриваются случаи степенного и Вейбулловского распределения. Маршрутизация производится следующим образом. При поступлении в систему заявки в момент времени t, случайно выбираются К различных серверов из N, и заявка направляется в очередь сервера с минимальной длинной. Изучается поведение вероятности переполнения системы в асимптотике большого входного буфера, а именно, вероятности попадания виртуальной заявки в очередь с временем обслуживания находящихся в ней заявок большим уровня ~о(~о —> оо), без учета времени обслуживания поступившей заявки, но с учетом заявки, стоящей на обслуживании. Рассматривается модель системы обслуживания дискретного времени.

Результаты, полученные в диссертационной работе

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

1. Получены простые асимптотически точные формулы вероятности переполнения системы с динамической маршрутизацией для случая степенного распределения времени обслуживания заявки.

• 2. Рассмотрен "промежуточный", между классическим экспоненциальным и степенным, случай, когда время обслуживания заявки имеет распределение Вей-булла. Получены асимптотически точные формулы для вероятности переполнения системы.

3. Разработан метод выбора оптимальных параметров маршрутизации (величины выборки), обеспечивающих требуемое качество обслуживания системы.

Структура работы

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

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

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

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

Заключение

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

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

В результате предложена следующая модель системы балансирующей нагрузку - модель обслуживания дискретного времени. Входной процесс поступления заявок в систему - пуассоновский, с интенсивностью NX. Время обслуживания заявок имеет распределение вероятностей с тяжелым хвостом. Заявки, поступающие в систему, распределяются между обслуживающими приборами по следующему правилу маршрутизации: при поступлении j-й заявки в момент времени t из N обслуживающих приборов случайно выбираются К, неповторяющихся и заявка направляется па выбранный прибор с минимальной длиной очереди.

Исследования были проведены в асимптотике большого буфера, что является естественным приближением при исследовании современных систем с высокими требованиями, предъявляемыми к качеству обслуживания, а именно рассматриваются системы с вероятностью переполнения порядка Ю-6 — Ю-9.

Исследовалось стационарное поведение системы. Рассматривалась вероятность переполнения системы в смысле вероятности попадания виртуальной заявки при маршрутизации в очередь сервера с остаточным временем обслуживания находящихся в нем заявок, превышающим уровень г0> для больших zq - без учета времени обслуживания поступившей заявки.

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

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

Во второй главе работы рассмотрен важный, как с практической, так и с теоретической точки зрения "переходный случай" между классическими системами с экспоненциальным временем обслуживания и системами с вероятностными характеристиками с тяжелым хвостом-случай Вейбулловского распределения времени обслуживания. Как уже было указано ранее, исследование этого случая затруднено, так как требует использования более точных асимптотических методов. Однако, применение новых разработанных методов исследования систем с динамической маршрутизацией позволило получить и в этом случае простые аналитические результаты в виде асимптотически точных формул переполнения системы. Как и следовало ожидать, вероятность переполнения системы имеет существенно другой вид зависимости от параметров маршрутизации по сравнению со случаем, рассмотренным в первой главе, и описывающим поведение системы со степенным распределением времени обслуживания заявок. В отличие от медленного, степенного убывания вероятности переполнения с увеличением параметра маршрутизации К, полученного ранее, вероятность переполнения в системе с Вейбулловским распределением времени обслуживания заявки убывает значительно быстрее- экспоненциально. Кроме того, в отличие от случая заявок со степенным распределением времени обслуживания, для которых при р < N — К оптимальной была конфигурация, когда в системе в момент t находится К заявок с остаточным временем обслуживания, превышающим пороговое значение го, при Вейбулловском распределении времени обслуживания оптимальной будет конфигурация, когда эти заявки пришли в систему практически одновременно (на отрезке порядка o(zo)). Это является следствием более резкого убывания вероятности возникновения заявки с большим временем обслуживания в распределении Вейбулла по сравнению со степенным.

Построение оптимальной конфигурации переполнения Вейбулловской системы для случая р > N — К гораздо сложнее и приводит к необходимости решать нелинейную оптимизационную задачу. По сравнению с оптимальной конфигурацией для степенного распределения времени обслуживания, когда переполнение происходило, если "большие" заявки стояли в

Tii = агд min (п) и N—p<n<K ' очередях, а остальные очереди переполнялись "маленькими", в случае распределения Вейбулла, даже при р > N — К, оптимальной может быть конфигурация из К заявок с остаточным временем обслуживания, превышающим пороговое значение г0.

Дальнейшие направления исследования и нерешенные задачи.

Несмотря на то, что пакет данных является основной единицей измерения в современных сетях передачи данных, и большинство исследований производится именно в масштабе пакета, конечный пользователь работает не с ним, а с некоторой логической последовательностью пакетов. Действительно, большинство операций пользователя может быть выражено через некоторую последовательность запросов и ответов. Так скачивание файла с удаленного сервера влечет за собой открытие TCP/IP соединения и передачи по нему множества пакетов, открытие Web страницы также приводит к установлению TCP/IP соединения. Логично заключить, что при разработке методов повышения качества обслуживания в сети необходимо руководствоваться вышеизложенными соображениями и реализовывать алгоритмы (например балансировки нагрузки), работающие не на уровне пакета, а на уровне TCP/IP соединения. Задачи повышения качества обслуживания для конкретного соединения возникают часто, например, в мультимедийных сетевых приложениях, когда пользователь хочет установить соединение и потребовать эксклюзивные параметры качества обслуживания для трафика реального времени. Понятно, что алгоритм предоставления их должен работать па уровне TCP/IP сеанса. Поэтому важным является установление вероятностных характеристик трафика сетей, не только на уровне пакетов, но и соединений.

Исследования трафика сетей передачи данных имеют богатую историю. Изначально, общепринятой моделью трафика являлась классическая модель с Пуассо-новским поступлением и экспоненциальным обслуживанием. Однако благодаря работе Leland, Wilson, Willinger и Taqqu [66], исследовавших трафик локальных сетей, было обнаружено явление, невписывавшееся в общепринятую модель. Трафик сетей оказался самоподобным, то есть имеющим одинаковое конечномерное распределение во всех временных масштабах.

Это явление, обнаруженное на пакетном уровне, объяснил Willinger, сделав предположение о том, что трафик локальных сетей является суперпозицией ВКЛ/ВЫКЛ источников с распределением длин ВКЛ/ВЫКЛ периодов с тяжелым хвостом.

Дальнейшее исследование трафика сетей продолжили Paxson & Floyd [83], которые показали, что трафик глобальных сетей (WAN) также самоподобеи. В качестве объяснения явления они предложили модель, в которой пакеты поступают в систему согласно распределению Пуассона, по несут с собой работу, количество которой имеет распределение с тяжелым хвостом вероятности. Однако, они также отметили, что процесс возникновения FTP и SMTP соединений плохо аппроксимируется Пуассоновским процессом.

Новейшие исследования статистических закономерностей трафика на уровне соединений провела A.Feldmann [37] для случая HTTP сеансов. Она указала, что Пуас-соновское распределения входного потока хорошо описывает случай, когда пользователи устанавливают соединения независимо друг от друга и от предыдущих установленных соединений, что было справедливо еще в 1995 году. Однако, последовавший в последнее время бурный рост сетей вывел на лидирующие позиции Web приложения,- более половины пакетов и более двух третой TCP соединений инициировано Web браузерами. Современный сетевые страницы содержат в среднем не один ресурс, а пользователи склонны в течении Wreb соединения просматривать не одну страницу и инициировать не одно связанное с контекстом ftp соединение. То есть запросы пользователя взаимосвязаны. Таким образом оказалось, что с ростом сетей изменяются их вероятностные характеристики, предположение о пуассонов-ском характере трафика становится менее применимо, и появляется необходимость разработки новых моделей сетевого трафика.

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

I I I I I I I I

ЧСУМ- 10*43 10*-2 10М 10*0 10*4 10Л2 10*3 time (in seconds}

9. Эмпирическая плотность распределения вероятностей времени между установлениями TCP/IP соединений во внешнем сегменте сети AT&T

18 Ноября-8 Декабря 1995. показала, что для случая Web соединений особенно хорошую аппроксимацию дает распределение Вейбулла времени между установлениями новых соединений. Трафик исследовался в течении длительного промежутка времени в разных сегментах сети AT&T. Выло установлено ,что как во внешнем сегменте, так и во внутреннем домину-руют пакеты от TCP/IP соединений, порожденных HTTP протоколом. В результате исследований была построена эмпирическая плотность распределения вероятности времени между установлением новых соединений, приведенная на Рис.9.

По оси абсцисс отложено время возникновения в секундах, по оси ординат количество возникших соединений. Наличие небольшого выброса в районе 0.000234 объX о

А + О measured data

Weibull с = 0.605, а = 4.477 Д" Pareto к = 0.68 , а = 1.289 • exp. mean = 6.68 Д

Inorm mean = 0.533 var =

10л-5

10л-3

10л-1 time

10л1 10л2 10л3

10. Эмпирическое дополнительное распределения вероятностей времени между установлениями TCP/IP соединений и приближения, полученные методов наименьших квадратов, во внешнем сегменте сети AT&T 18 Ноября-8 Декабря

1995. яснястся существованием зависимостей в протоколах, а именно, при открытии HTTP документа по протоколу необходимо установить несколько TCP/IP соединений для скачивания встроенных в документ объектов(gif-анимации).

На Рис.10 отражено наблюдаемое дополнительное распределение времени между установлениями соединений и его приближения, распределениями с тяжелым хвостом и экспоненциальным, полученные методом наименьших квадратов, . Из рисунка видно, что распределения Логнормальное, Парето и экспоненциальное - дают значительно менее точное приближение, чем Вейбулловское. Так экспоненциальное распределение дает заниженный результат, как для коротких, так и для длинных времен. Логнормальное, напротив, дает оценку выше действительной в обоих случаях. Парето дает завышенную оценку средних значений времени и очень плохо аппроксимирует короткие промежутки возникновения.

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

1. J. Abate, G. L. Choudhury, W. Whitt, Waiting-time tail probabilities in queues with long-tail service-time distributions, Queueing systems, 1994, no. 16, pp.311-338.

2. I. J. B. F. Adan, G. van Houtum, and J. var der Wal, Upper and lower bounds for the waiting time in the symmetric shortest queue system, Annals of operations reserch, 1994, vol. 48, pp.197-217.

3. I. J. B. F. Adan, J. Wessels and W. H. M. Zijm, Analysis of the symmetric shortest queue problem, Stohastics models, 1990, vol. 6, pp.691-713.

4. I. J. B. F. Adan, J. Wessels and W. H. M. Zijm, Analysis of the asymmetric shortest queue problem, Queueing Systems, 1991, vol. 8, pp.1-58.

5. S. Asmussen and C. Kluppelberg,Stationary M/G/l excursions in the presence of heavy tails, J. Appl. Prob., 1997, no.34, pp.208-212.

6. S. Asmussen, Ruin probabilities, 2000, World Scientific, Singapore.

7. S. Asmussen, Applied probabilities and queues, 1987, Wiley, Chichester.

8. S. Asmussen, Busy period analysis, rare events and transient behavior in fluid flow models, Journal of applied mathematics and stochastic analysis, 1994, no.7, pp.269299.

9. S. Asmussen, Conditioned limit theorems relating a random walk to its associate, with applications to risk reserve processes and the GI/G/1 queue, Advances in Applied probability, 1982, no.14, pp.143-170.

10. S. Asmussen and Л. Tcugels, Convergence rates for M/G/l queues and ruin problems with heavy tails, Journal of Applied probability, 1996, no.33, pp.1181 1190.

11. Y. Azar, A. Broder, A. Karlin and E. Upfal, Balanced allocations, Proceedings of the 26th ACM Symposium of the Theory of Computing, 1994, pp.593-602.

12. Аленичев A.B., Лиханов Н.Б. Динамическая маршрутизация в системе с заявками, имеющими степенной закон распределения времени обслуживания. Информационные процессы, Москва. 2005. т. 5, №3, с. 213-226.

13. Аленичев А.В. Система массового обслуживания с динамической маршрутизацией и распределением Вейбулла времени обслуживания заявок. Информационные процессы, Москва. 2005. т. 5, JV®5, с. 431-441.

14. F. Baccelli, F. I. Karpilevich, М. Ya. Kelbert, A. A. Puhalskii, А. N. Rybko and Yu. M. Suhov, A mean field limit for class of queueing networks, J. Stat. Phys., 1992, vol. 66, pp.803-825.

15. F. Baccelli and P.Bremaud, Elements of queueing theory,(Springer New York,1994).

16. S. A. Berezner, D. Roze and Yu. M. Suhov, Starlike networks whith sinhronization constrains, In Stochastic Networks, F.P.Kelly and R.J.Williams, Eds.,vol. 71 of IMA Volumes in Mathematics and its Applications, 1995, pp.313-333, Springer-Verlag.

17. A. A. Borovkov, Some limit theorems in the theory of mass service, Theory of probability and its applications, 1964, no.9, pp.550-565.

18. A. Botvich and N. G. Duffield, Large deviation, economies of scale and the shape of the loss curve in large multiplexers, Queueing Systems, 1995, no.20, pp.293-320.

19. О. J. Boxma and J. W. Cohen, Heavy traffic analysis for the GI/G/1 queues with heavy-tailed distributions, Queueing Systems, 1999, no.33, pp. 177-204.

20. О. Л. Boxma and J. W. Cohen, The single server queue: heavy tails and heavy traffic, In Park, K., and Willinger, W., (editors), Self-similar network traffic and performance evaluation, 2000, Wiley, New York, pp. 143-170.

21. J. Choe and N. B. Shroff, On the supremum distribution of integrated stationary Gaussian processes with negative linear drift, Advances in Applied Probability, 1999, no.31, pp.135-157.

22. J. W. Cohen, O. J. Boxma, A survey of evolution of queueing theory, Statistica Neerlandica, 1985, no.39, pp. 143-158.

23. J. W. Cohen, Heavy-traffic limit theorems for the heavy-tailed GI/G/1 queue, Report PNA-R9719, CWI, Amsterdam.

24. J. W. Cohen, Heavy-traffic theory for the heavy-tailed M/G/l queue and ^-stable Levy noise traffic, Report PNA-R9805, CWI, Amsterdam.

25. C. Courcoubeties and R. Weber, Buffer overflow asymptotics for a switch handling many traffic soutces, J. Appl. Prob., 1996, vol.33, no.3, pp.886-903.

26. H. Cramer, On the mathematical theory of risk, Skandia Jubilee Volume, 1930, Stokholm.

27. V. Chistakov, A theorem on sums of independent positive random variable and its application to branching random processes, Theory Probab. Appl., 1964, no.9, pp.640-648.

28. D. R. Cox, Long-range dependence: A review, in, Statistics: An Appraisal, eds. H.A.David and H.T.David(Iowa state univ. press, Ames, IA, 1984).

29. R. L. Dobrushin and Yu. M. Suhov, Asymptotical investigation of starshape message switching networks whith a large number of radial rays, Problems Inform. Transmission, 1976, № 12, pp. 49-65.

30. N. G. Duffield and N. O'Connel, Large deviation and overflow probabilities for the general single-server queue with applications, Math. Proc. Camb. Phil. Soc, 1995, no.118(1), pp.363-374.

31. D. L. Eager, E. D. Lazokwska and J. Zahorjan, Adaptive load sharing in homogenious distributed systems, IEEE J. Transactions on Software Engineering, 1986, vol. 12, pp.662-675.

32. D. L. Eager, E. D. Lazokwska and J. Zahorjan, A comparison of receiver-initiated and sender-initiated adaptive load sharing, Performance evaluation review, March 1986, vol. 16, pp.53-68.

33. D. L. Eager, E. D. Lazokwska and J. Zahorjan, The limited performance benefits of migrating active processes for load sharing, Performance evaluation review, May 1988, vol. 16, pp.63-72.

34. S. N. Ethier, T. G. Kurtz, Markov Processes Characterization and Convergence, N.Y. etc: John Willey and Stons ,1986.

35. A. Feldmann, Characteristics of TCP Connection Arrivals, Technical report, AT&T Labs Research, 1998.

36. W. Feller, An introduction to probability theory and its applications, Volume. ДД971, Wiley, New York.

37. H. Furrer, Z. Michna, A. Weron, Stable L£vy motion approximation in collective risk theory, Insurance: Mathematics and Economics, 1997, no. 20, pp.97-114.

38. M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of NP-completness, W.H. Freeman and Company, 1979.

39. N. Gautam, V. G. Kulkarni, Z. Palmowski, T. Rolski, Bounds for fluid models driven by semi-Markov inputs, Probability in the Engineering and Informational Sciences, 1998, no.13, pp.429-475.

40. P. W. Glynn and W. Whitt, Logarithmic asymptotics for steady-state tail probabilities in a single-server queue, J. Appl. Prob., 1994, no.31 A, pp. 131-156.

41. C. Graham and S. Meleard, Propagation of chaos for a fully connected loss network whith alternate routing, Stochastic Process. Appl., 1993, vol. 44, pp. 159-180.

42. C. Graham and S. Meleard, Chaos hypothesis for a system interacting through shared resources, Probab. theor. rel. fields , 1994, vol. 100, pp. 157-174.

43. C. Graham and S. Meleard, Fluctuations for a fully connected loss network whith alternate routing, Stochastic Process. Appl., 1994, vol. 53, pp.97-115.

44. M. Harchold-Balter and A. B. Downey, Exploiting Process Lifetime Distributions for Dynamic load balancing, ACM Trans, on Computer Systems, 1997, no. 15(3), pp.253-285.

45. J. Hui, Resource allocation for broadband networks , IEEE Journal on Selected Areas in Communications, 1988, no.6, pp. 1598-1608.

46. P. J. Hunt, Loss networks under diverse routing: the symmetric star network, Adv. Appl. Probab., 1995, vol. 25, pp. 225-272.

47. Р. Л. Hunt and Т. G. Kurz, Large loss networks, Stochastic Process. Appl., 1994, vol. 53, pp. 363-378.

48. D. Iglehart, Limit theorems for traffic with intensity one, Annals of Mathematical Statistics, 1965, no.36, pp.1437-1449.

49. P. Jacquet, N.D. Vvedenskaya, ON/OFF Sources in an Interconnection Network: Performance Analysis when Packets are Routed to the Shortest Queue of two Randomly Selected Nodes, Rapport de Recherche No 3570, INRIA, pp 1-35, December 1998.

50. Kai Shen, Tao Yang and Lingkun Chu, Claster load balancing for Fine-grain network services, ACM Trans, on Computer Systems, 1997, no.l5(3), pp.253-285.

51. V. Kalashnikov, Geometric Sums: Bounds for rare events with applications, 1997, Kluwer, Dordrecht.

52. F. I. Karpilevich, M. Ya. Kelbert and Yu. M. Suhov, High-order Lindley equations, Stochastic process. Appl., 1994, vol. 53, pp.65-96.

53. F. I. Karpilevich, E. A. Pechersky and Yu. M. Suhov, Dobrushin's approach to queueing network theory, J. Appl. Math. Stoch. Anal., 1996, vol. 9, pp.373-398.

54. R. M. Karp, M. Luby and F. Meyer auf der Heide, Efficien PRAM simulation on a distributed memory mashine, Proceedings of the 24th ACM Symposium of the Theory of Computing, 1992, pp.318-326.

55. M. Ya. Kelbert and Yu. M. Suhov, Asymptotical analysis of star-like packet switching networks, Problems Inform. Transmission, 1979, vol. 15, pp.53-72.

56. M. Ya. Kelbert and Yu. M. Suhov, A Poisson limit theorem for hybrid star networks: a mean field approximation, Problems Inform. Transmission, 1989, vol. 25, pp.60-67.

57. M. Ya. Kelbert and Yu. M. Suhov, Mathematical problems in theory of queueing networks, J. Soviet Math., 1990, vol. 50, pp.1527-1600.

58. F. P. Kelly, Loss networks, Ann. Appl. Probab., 1991, vol. 1, pp.319-378.

59. J. F. C. Kingman, The heavy traffic approximation in the theory of queues,In Smith, W. L., Wilkinson, W. E. (editors), Proceedings of the Symposium on Congestion Theory, 1965, The University of North Carolina Press, Chapel Hill, pp. 137-159.

60. M. Yu. Kradinov, Proof of the Poisson hypothesis of circuit-switching loss networks, Problems Inform. Transmission, 1992, vol. 28, pp.375-383.

61. T. G. Kurz, Solutions of ordinary differential equations as limits of pure jump Markov processes, J. Appl. Prob., 1970, vol. 7, pp.49-58.

62. T. G. Kurz, Limit theorems for sequences of jump Markov processes approximating ordinary differential processes, J. Appl. Prob., 1971, vol. 8, pp.344-356.

63. T. G. Kurz, Strong approximatin theorems for dencity dependent Markov chains, Stochastic Processes and Applicationc, 1978, vol. 6, pp.223-240.

64. W. E. Leland, M. S. Taqqu, YV. Willinger and D. V. Wilson, On the self-similar nature of Ethernet traffic (extended version), IEEE/ACM Trans, on Networking, 1994, no.2, pp.1-15.

65. N. Likhanov and R. Mazumdar, Cell loss asymptotics in buffers fed with a large number of independent stationary sources, J. Appl. Prob., 1999, no.36, pp.86-96.

66. N. Likhanov, Bounds on the buffer occupancy with self-similar input traffic,in Self-similar network traffic and performance evaluation, K. Park and W. Willinger eds., Wiley, 2000, pp. 193-214.

67. N. Likhanov and R. Mazumdar,Loss asyrnptotics in large buffers fed by heterogeneous long-tailed sources, Advances in Applied Probability, 2000, no.32, pp. 11681189.

68. N. Likhanov, R. Mazumdar, O. Ozturk, Large buffer asyrnptotics for fluid queues whith heterogeneous M/G/со Weibullian inputs, Queueing Systems, 2003, no.45, pp.333-356.

69. Z. Liu, P.Nain, D.Towsley and Z-L. Zhang, Asyrnptotics behavior of a multiplexer fed by long-range dependent process, Journal of Applied Probability, 1999, no.36, pp.105-118.

70. I. MacPhee and I. B. Ziedins, Admission control for loss networks whith diverse routing, In Stochastic Networks. Theory and Applications, F.P.Kelly, S. Zachary and I. Ziedins, Eds. Clarendon Press, 1996, pp.205-214, Oxford.

71. M. Mandjes and S. C. Borst, Overflow behavior in queues with many long-tailed inputs , Advances in Applied probability, 2000, no.32, pp. 1150-1167.

72. M. Mandjes and J.- H. Kim, Large diviations for small buffers: an insensitivity result , Queueing systems, 2001, no.37, pp.349-362.

73. V. V. Marbukh, Asymptotic study of a fully-connected communication network whith large number of nodes and circuit routing, Problems Inform. Transmission, 1981, vol. 17, pp.89-95.

74. V. V. Marbukh, Study of a fully-connected communication network whith large number of nodes and circuit routing and a bounded number of waiting-places at the node, Problems Inform. Transmission, 1985, vol. 21, pp.90-98.

75. J.B. Martin, Yu. M. Suhov, Fast Jackson networks, J. Appl. Prob., 9, pp 854-870, 1999.

76. M. Mitzenrrmcher, The power of two choices in randomized load balancing, PhD thesis, September 1996, University of California, Berkley.

77. I. Norros, A storage model with self-similar input, Queueing Systems, 1994, no. 16, pp.387-396.

78. Z. Palmowski, T. Rolski, The superposition of alternating on-off flows and a fluid model, Annals of Applied Probability, 1998, no.8, pp.524-541.

79. Z. Palmowski, Bounds for steady-state buffer content in fluid models, Ph.D Thesis, Mathematical Institute, University of Wroclaw, Poland.

80. M. Parulekar and A. M. Makowski, Tail probabilities for M/G/oo input processes, Queueing Systems, 1994, no.27, pp.271-296.

81. V. Paxon, S. Floyd, Wide area traffic: the failure of Poisson modeling, IEEE/ACM Trans, on Networking, 1993, no.3, pp.226-244.

82. E. A. Pechersky, Y. M. Suhov and N. D. Vvedenskaya, Large deviations in a two-servers system whith dynamic routing, preprint.

83. S. Resnick and G. Samorodnitsky, A heavy traffic approximation for workload processes with heavy tailed service requirements, Management Science, 2000, no. 46, pp.1236-1248.

84. A. Shwartz and A. Weiss, Large Diviations for performance analysis, 1995, Chap-manfe Hall, London.

85. A. Simonian and J. Guibert, Large deviations approximation for fluid queues fed by a large number of ON/OFF sources, IEEE J. Sel. Areas Cornmun., 1995, vol. 13, no.6, pp.1017-1027.

86. H. C. Tijms,Stochastic models-an algorithmic approach, 1994, Wiley, Chichester.

87. S. R. E. Turner, Large deviations for Join the Shortest Queue, Fields Ints. Communications, 2000, vol. 28, pp. 95-106.

88. S. R. E. Turner, A Join the Shortest Queue Model in heavy traffic, Fields Ints. Communications, 2000, vol. 29, pp. 92-101.

89. Н.Д. Введенская, P.JT. Добрушин, Ф.И. Карпелевич, Система обслуживания с выбором наименьшей из двух очередей асимптотический подход, Пробл. передачи информ., 32, No 1, стр. 15-27, 1996.

90. N.D. Vvedenskaya and Yu. М. Suhov, Dobrushin's mean field approximation for a queue whith dynamic routing, Rapport de Recherche No 3328, INRIA, pp 1-39, December 1997.

91. A. Weiss, A new technique of analyzing large traffic systems, Advances in Applied probability,1986, no. 18, pp.506-532.

92. S. Zachary, The asymptotic behavior of large loss networks, In Stochastic Networks. Theory and Applications, F.P.Kelly, S. Zachary and I. Ziedins, Eds. Clarendon Press, 1996, pp. 193-203, Oxford.

93. S. Zhou, A trace-driven simulation study of dynamic load balancing, IEEE J. Transactions on Software Engineering, 1988, vol. 14, pp. 1327-1341.

94. I. B. Ziedins and F. P. Kelly, Limit theorems for loss networks whith diverse routing, Adv. Appl. Probab., 1989, vol. 21, pp. 804-830.

95. A. P. Zwart, Queueing systems with heavy tails, 2001, Universiteitsdrukkerij Tech-niche Universiteit Eindhoven.