Сетевые игры и распределение ресурсов

Чуйко, Юлия Васильевна

Сетевые игры и распределение ресурсов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Чуйко, Юлия Васильевна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Петрозаводск МЕСТО ЗАЩИТЫ

2006 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Сетевые игры и распределение ресурсов»

Автореферат диссертации на тему "Сетевые игры и распределение ресурсов"

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

Чуйко Юлия Васильевна ООЗОБ ('иьэ

СЕТЕВЫЕ ИГРЫ И РАСПРЕДЕЛЕНИЕ РЕСУРСОВ

Специальность 01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

Санкт-Петербург - 2006 г.

003067065

Работа выполнена в Институте прикладных математических исследований Карельского научного центра Российской академии наук.

Научный руководитель:

доктор физико-математических наук, профессор В.В. Мазалов

Официальные оппоненты: доктор физико-математических наук,

профессор А.Ю. Гарнаев

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

А.Н. Ляпунов

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

Санкт-Петербургский институт информатики и автоматизации РАН

Защита состоится 200.7 г. в ¡.Н. час. на заседании

диссертационного совета К-212.232.07 по защите диссертаций на соискание ученой степени кандидата физико-математических наук при Санкт-Петербургском государственном университете по адресу: 190004, Санкт-Петербург, В.О., Средний пр., д.41/34, ауд. £!3

С диссертацией можно ознакомиться в библиотеке СПбГУ им. А.М.Горького по адресу: С.Петербург, Университетская наб., 7/9.

Автореферат разослан ".^.."...^(Г^}.... 200.? г.

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

диссертационного совета доктор физ.-мат. наук, профессор

В.Ф. Горьковой

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

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

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

В последнее время в исследованиях, связанных с оптимизацией работы вычислительных сетей, стали применяться методы некооперативной теории игр п лиц. Это направление получило название "сетевые игры" (Networking Games, Noncooperative Networks). При этом каждый пользователь сети или узел, входящий в сеть, трактуется как некоторый игрок, а задача распределения ресурсов сети рассматривается как игра, в которой игроки, действуя оптимально, могут достигать равновесия - ситуации, в которой никому из игроков не выгодно отклоняться от своей стратегии.

Один из классов задач данного направления связан с управлением

загруженностью серверов - узлов сети, обрабатывающих запросы клиентов и отвечающих на них. Здесь сервер рассматривается как система массового обслуживания, обрабатывающая поток пользовательских заявок. В диссертационной работе решается задана выбора оптимального момента обращения игроков к системе массового обслуживания 7/М/1/0 с учетом заданной функции "комфортности". В рассматриваемой модели оптимальные стратегии игроков определяют дисциплину поступления заявок в систему обслуживания таким образом, чтобы максимизировать ожидаемую прибыль от обслуживания заявки в выбранный момент времени.

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

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

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

следующие основные задачи:

1. задача выбора оптимального момента обращения игроков к системе массового обслуживания ?/М/1/0 с учетом заданной функции "комфортности";

2. задача оптимальной маршрутизации трафика в сети в вероятностной постановке с неделимым трафиком (КР-модель) и в постановке на основе модели Вардропа с разделяемым трафиком.

3. задача справедливого разделения пропускной способности каналов сети с применением обобщенного критерия справедливости Валранда;

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

В постановке задачи выбора оптимального момента обращения игроков к системе массового обслуживания 1 /М/1/0 введено понятие функции "комфортности", для данной модели получен аналитический вид равновесного решения для для случая двух игроков. Для случая п+1 > 3 игроков построен общий вид функции выигрыша и решены задачи нахождения вида необходимой функции "комфортности" для того, чтобы равновесные стратегии игроков имели заданный вид: равномерное и экспоненциальное распределение. Для этих задач проведен анализ поведения системы при бесконечно большом количестве игроков.

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

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

справедливости Валранда. Разработано программное обеспечение для численного решения таких задач при задаваемых значениях параметра справедливости.

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

Положения, выносимые на защиту. На защиту выносятся следующие положения.

1. Найдены равновесия в задачах выбора оптимального момента обращения игроков к системе массового обслуживания ?/М/1/0 с учетом заданной функции "комфортности".

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

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

Связь работы с научными программами, темами. Основные результаты диссертации были получены в рамках проведения исследований, выполнявшихся в ходе работ по гранту Отделения математических наук РАН (программа "Математические и алгоритмические проблемы информационных систем нового поколения"). В 2005 г. данные исследования также были поддержаны грантом Фонда содействия отечественной науке по программе "Лучшие аспиранты РАН", который был продлен и в 2006 г.

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

1. VI Международная петрозаводская конференция "Вероятностные методы в дискретной математике", Петрозаводск, 10-16 июня 2004 г., ИПМИ КарНЦ РАН.

2. Международный семинар "Optimal Stopping and Stochastic Control" (Петрозаводск, 22-26 августа 2005 г., ИПМИ КарНЦ РАН);

3. Российско-финская летняя школа "Dynamic Games and Multicrite-ria Optimization", 2-7 сентября 200G, Петрозаводск.

4. Всероссийская научная конференция "Научный сервис в сети Интернет: технологии параллельного программирования" (18-23 сентября 2006 г., г. Новороссийск).

По материалам диссертации опубликовано 9 работ, из них 4 статьи [1, 2, 3, 4] и тезисы 5 докладов [5, 6, 7, 8, 9].

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы. Общий объем диссертации составляет 107 страниц. Список литературы включает 64 наименования.

Содержание работы

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

В первой главе рассматривается задача выбора оптимального момента обращения игроков к системе массового обслуживания ?/М/1/0 с учетом заданной функции "комфортности". В этой задаче игроки отправляют свои заявки в систему массового обслуживания со следующими характеристиками:

• дисциплина поступления заявок в систему не задана;

• время обслуживания очередной заявки является экспоненциально распределенной случайной величиной с параметром 1/ц (ц > 0);

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

• в системе отсутствует очередь: если на момент поступления очередной заявки в системе уже обслуживается заявка, то поступившая заявка получает отказ в обслуживании;

• для поступающих заявок задана функция "комфортности" C(t). отражающая выгоду, получаемую пользователем в случае начала обслуживания его заявки в системе в момент t.

Если заявка игрока была принята на обслуживание в момент то он получает выигрыш, равный С(£), иначе его выигрыш равен 0. Для каждого из игроков смешанная стратегия определяется функцией плотности распределения моментов времени его обращения к системе для отправления заявки на некотором интервале времени. Каждый игрок стремится максимизировать свой ожидаемый выигрыш на данном интервале времени. В данной задаче исследуется симметричное равновесие по Нэ-шу в смешанных стратегиях. Равновесная по Нэшу ситуация находится как набор одинаковых стратегий игроков, удовлетворяющих следующим условиям:

• стратегия игрока д(£) является функцией плотности распределения на интервале [¿о,Т];

• ожидаемый выигрыш игрока постоянен на интервале времени [¿о ,Т] и принимает на нем максимальное значение.

Для модели с двумя игроками функция выигрыша игрока, использующего чистую стратегию когда противник использует смешанную стратегию д{Ь), имеет вид

Для этого случая в диссертационной работе удалось получить аналитический вид симметричных равновесных по Нэшу стратегий в общем виде для задаваемой функции "комфортности" С{Ь). Данный результат представлен в следующей теореме.

Теорема 1 Стратегии игроков вида

на интервале где ¿о, Т такие, что

! д(г)<И = 1 и д(г) > 0, С (г) < С(*о) для г £ (-оо,40],

для г е [Г, оо)

обесггечивают симметричное равновесие по Нэшу в задаче с двумя игроками с заданной функцией "комфортности" С{Ь). При этом равновесное значение выигрыша на интервале для каждого из игроков равно Н(Ь,д) = С{Ц).

Условия существования данного равновесия зависят от вида функции С(г). Отдельно в диссертационной работе рассматриваются случаи с экспоненциальной и параболической функциями "комфортности".

Для функции "комфортности" вида С{Ь) = —аеы для Ь > £о и С{£) — —аеьь" — С(Ьо) для £ < ¿о, где а,Ъ> 0, равновесная стратегия на интервале [¿о, Т] имеет вид

Границы интервала [¿о> Г] должны удовлетворять условию

Ье-Ь(Г-40)

ц =

е-ь(т-«о) _ 1 + Ь(Т-г0)'

В этом случае на интервале [¿о> Т] равновесная функция выигрыша имеет вид Н(Ь,д) = —аеы°.

Для случая функции "комфортности" вида С{£) = а1( 1 — £), где а > О, результат решения сформулирован в виде теоремы.

Теорема 2 Стратегии игроков д{Ь) вида

(1 — 2£ — + /Л2)£о(1 ~ ^о)

®(4) =-ЩГ^-

на интервале [¿о, Т], где 0<Ьо<^<Т<1, т,акие что д(Т) = 0 и т

/ д{1)<И = 1, обеспечивают симметричное равновесие по Нэшу в задаче <0

с двумя игроками с заданной функцией ''комфортности" С(£) = at(l — £), где а > 0.

В этом случае на интервале [¿о > Т] равновесная функция выигрыша имеет вид Н(Ь,д) = а£0(1 - ¿о)-

Для случая п+1 > 3 игроков функции выигрыша имеет вид Н(Ь, дп) = С(Ь)Рп(Ь,д), где -Р„(£, д) ~ вероятность, что заявка от игрока, отправляющего ее в момент встанет на обслуживание, в то время как для

остальных игроков моменты обращения к системе распределены с одинаковыми плотностями д(1).

Pn.it,д) = 1 — п / /

— оо V — оо

х ^ 1 — (п — 2) 7

В рекуррентной записи данные вероятности имеют вид:

Pi(t,g) = l- J glrje-rt-^dn

— ОО

P2(t,g) = 1-2 f g(r1)e-^i-^P1(T1,g)dr1

— ОО

Рп(г,д) = 1 - п / д(т1)е-^-^Рп-1(т1,д)с1т1.

— со

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

Теорема 3 Для того, чтобы равновесные стратегии игроков имел,и вид равномерного распределения на интервале [0,1], функция "комфортности" на данном, интервале должна принимать значения С„(«) = сошЬ/Рп^,д), где

(~и)п \ ^ i\ ^ г\ Г

v ^> \)=0 i—Q /

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

Теорема 4 Для. того, чтобы равновесные стратегии игроков им,ели вид g(t) = \e~xt, t > О, функция "комфортности" для t > 0 должна принимать значения. Cn(t) — const/Pn(t, g), где

™ n\ e-«At _ -(n-i)Xf-Mt

Pn(t,g) = 1 + }^-

8=1 (n г)! П U ~ M/A)

j=i

Для /л, близких к 0, при больших п вероятность попадания заявки на обслуживание Рп(1. д) близка к нулю, л функция "комфортности" имеет также экспоненциальный вид и должна принимать большие значения.

Во второй главе исследуется задача оптимальной маршрутизации трафика в сети в условиях, когда пользователи самостоятельно выбирают маршруты для отправки своего трафика. Задача рассматривается в двух вариантах постановки: вероятностная модель задачи маршрутизации с неделимым трафиком, основанная на КР-модели (Кошяощная, РарасНтйпои), и модель с разделяемым трафиком, основанная на модели Вардропа (\¥аи1гор).

Первая модель описывает систему п пользователей и т параллель-пых каналов. Каждый пользователь г = 1,..., п собирается отправить трафик объемом гиг по одному из каналов. Для каждого канала I = 1,... ,т задана пропускная способность сц. При отправке трафика объемом го по каналу с пропускной способностью с задержка на канале определяется как т/с.

Каждый пользователь действует в своих собственных интересах и стремится занять тот канал, на котором задержка его трафика будет наименьшей. Чистой стратегией для пользователя { является выбор канала I, по которому он собирается отправить свой трафик. Тогда вектор Ь = (1\..... 1п) представляет собой профиль чистых стратегий пользователей, где 1г - номер канала, выбранного пользователем г. Смешанной стратегией для него является вероятностное распределение рг = [р\,... ,р™)> где р[ - вероятность, с которой пользователь г выбирает I. Матрица Р, образованная векторами рг, представляет профиль смешанных стратегий пользователей.

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

на используемом им канале 1г определяется как Аг =-'

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

Аг = шш --——.

.7 = 1,. ,ш с->

Для смешанных стратегий определяется ожидаемая задержка трафика пользователя г в случае использования им канала I, равная А' =

к=г.к-Фг — Минимальная ожидаемая задержка пользователя г рав-

С1

на Хг = тш А^.

1—1,. ,т

Определение 2 Профиль Р называется равновесием по Нэгиу, если для каждого пользователя г для любого из используемых им каналов справедливо: \[ = Аг если р[ > 0, и \\ > Аг если р\ — 0.

Определение 3 Смешанное равновесие Р называется полностью смешанным равновесием, если каждый пользователь выбирает каждый канал с положительной вероятностью, то есть для любого г = 1.... ,п и для любого I = 1,..., т р[ > 0.

В качестве функции затрат системы БС{и),с,Ь) для чистого профиля в работе рассматриваются следующие варианты.

1. линейные затраты Ь8С(и>,с,Ь) — ;

г=1 с'

т (V _ 2

2. квадратичные затраты С'¿ЗС(т,с,Ь) = ^ --—к 'кс '——;

1=1

3. максимальные затраты МЗС(ии, с, Ь) — ^ тах

В диссертационной работе приведены примеры систем с функцией затрат системы вида М5С(и;,е, Ь), в которых равновесие в чистых стратегиях ухудшается при добавлении в систему нового канала.

Определение 4 Затратами системы для профиля смешанных стратегий Р называется математическое ожидание затрат системы БС(и1,с, V) для случайного профиля чистых стратегий Ь

БС(1и,с,Р)=Е(ЗС(1и,с,Ь))= £ (.

¿=(«1, -М \ь= 1 /

В работе найдены значения линейных и квадратичных затрат системы в полностью смешанном равновесии по Нэшу Р для случая с различными пользователями и одинаковыми каналами с пропускной способностью равной 1:

п п 2

ЬБС^Р) = <Э8С(т,Р) = + — Х)«7^-

/с—1 т Ьф]

Для случая с одинаковыми пользователями и различными каналами, где каналы упорядочены по возрастанию пропускной способности: с\ < С2 < ■ • • < сто, С = 1 сь а пользователи отправляют трафик объемом 1, вид полностью смешанного равновесия представлен в следующей лемме.

Лемма 1 В модели п одинаковых пользователей, т параллельных каналов единственное полностью смешанное равновесие по Нэшу существует тогда и только тогда, когда с\(т + п — 1)>С. При этом для каждого канала I = 1,..., т для любого пользователя г = 1,..., п равновесные вероятности р[ = р1 — а индивидуальные равновесные задержки для всех пользователей одинаковы и равны .

Тогда соответствующие линейные и квадратичные затраты системы: г аГ(г сл _ тп{т + п- 1) п А1. _ п(т + п- 1)

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

Теорема 5 В модели с п одинаковыми пользователями и т различными параллельными каналами линейные затраты системы в полностью смешанном равновесии увеличиваются при добавлении нового канала с пропускной способностью < со < такого, что выполнено

со(т + п) > С + со и с\{т + п) > С + со-

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

Для общего случая системы с различными пользователями и каналами, где IV = и'г п С = Х^™ 1 сь условия возникновения парадокса Браесса в системе также сформулированы в виде теоремы для случая, когда затраты системы определяются как

Т СП! ЕЛ гп\¥{п + тп- 1) \¥ ^ 1

ь5С(и),с, —-^--—----> —.

У ' С(п -1) п-1^С1

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

пропускной способностью Тп^п_1 < со < ^, такого, что для всех пользователей i = 1,..., п и всех каналов I = 0,... ,т справедливо

(ш + 1)сЛ /__+

С + с0 J \ {n-l)WlJ С + со

В рамках модели маршрутизации с разделяемым трафиком задача оптимальной маршрутизации трафика рассматривается как игра Г = (п, G, w, Z, /), в которой п пользователей отправляют трафик по каналам сети G = (у, Е). где G - граф с источником s и приемником t. Для каждог о пользователя г существует Z, - набор маршрутов из s в t по каналам G и определен объем отправляемого трафика юг. Для каждого из каналов е е Е определена пропускная способность се > 0. Пользователи действуют в собственных интересах, выбирая маршруты для отправки трафика таким образом, чтобы минимизировалась максимальная задержка при пересылке их трафика из s в t. Каждый пользователь определяет для себя стратегию хг = > 0} n.az, - При этом x,ni - количество трафика, которое пользователь i отправляет по маршруту Пг, и ]Г)л = Wi- Тогда х = (х\,..., хп) - профиль стратегий поль-

зователей. Для профиля стратегий х будем использовать обозначение (х-г,х'г) = (х\,... ,хг-\,х'г,х1+1,... ,хп), которое означает, что пользователь г изменил свою стратегию с хг на х[, а остальные пользователи сохранили свои стратегии неизменными.

Для каждого из каналов определяется его загрузка 5в(х), непрерывная и неубывающая по хгцг ,,е_ а, ■ Задержка при пересылке трафика по данному маршруту зависит от загрузки каналов, составляющих маршрут. Непрерывная функция задержки трафика fiRt(x) — /iR,({<5e(^)}e€R,) определяется для каждого пользователя г и используемого им маршрута В., и является неубывающей по величинам загрузки каналов, составляющих маршрут, и, следовательно, по хгя, •

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

РСг{х)= max fiRt(x)-R,ez, хгцг>0

Определение 5 Профиль стратегий х называется равновесием no II.)-шу, если для каждого пользователя i и любого профиля х' = выполняется РСг(х) < РСг(х').

Определение 6 Профиль х называется равновесием по Вардропу, если для, каждого г справедливо: из хгц1 > 0 следует Ля, (z) = min fip% (x) = Хг и из xlRt = О следует Ля, (х) > А,.

Связь данных определений ситуаций равновесия по Нэшу и по Вардропу сформулирована в виде двух теорем.

Теорема 8 Если профиль х является; равновесием по Вардропу, то х - равновесие по Нэгиу.

Теорема 9 Если все функции задерэюки трафика таковы, что для любого профиля, х, пользоват,ел,я г, маршрута В,г G Zt, такого что XiR, > 0, и маршрута рг G Zx из выполнения, /гд, (ж) > ftPl (а;) следует существование окрестности Vx = {х' = (х-г,х[) : x'tRi G [а^я, — Д^гЯ, )} точки х, такой что для любых профилей x' G Vx выполняется, fiRt(x') < fiRl{x), то в такой модели любое равновесие по Нэшу также является равновесием по Вардропу.

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

В рамках модели с разделяемым трафиком рассматривается случай системы с функциями задержки трафика S на канале с пропускной способностью с вида В этом случае функция задержки трафика пользователя г на маршруте R% определяется как /гr,(x) = ]Сеея с > где ¿е(ж) = £Г=1 Ep.ez, е€р, - загрузка каналов е G Яг. Теорема 10 В модели с функциями задержки вида fiRt(э-0 = с S-Se(x) определения равновесия по Нэшу 5 и по Вардропу 6 являются равносильными.

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

SC{x) = £ £ =

1=1 R,ez, ее Е е >

Глобальный оптимум в данной модели определяется как решение задачи минимизации затрат системы SC(x). Для частного случая системы с m параллельными каналами доказано, что любая ситуация равновесия по Нэшу в данной модели дает глобальный оптимум функции затрат системы. Для случая такой системы с общедоступными для

пользователей каналами, где для каждого пользователя г — 1,..., п гг = {1,..., ш}, \¥ = ™г, С = се, равновесием по Нэшу бу-

дет любая ситуация, где нагрузка на каналы распределена следующим образом: хке = Wce/C для всех каналов е — 1,..., т и затраты

системы равны И/2/(С — IV). Примером такого равновесного по Нэшу Профиля МОЖеТ быть X — {{хге — -ШкСе/С}'^

В третьей главе исследуются модели справедливого разделения пропускной способности каналов сети, где в качестве критерия справедливости используется следующий обобщенный критерий справедливости Валранда (\Valrand). Рассматривается игра Г = (Аг, X, /), в которой N игроков определяют значения вектора х — (х1,...,хк) из допустимого выпуклого множества X С Кдг. Для каждого из игроков задана /г(х) - вогнутая и возрастающая по хг функция полезности г игрока, значение которой он хочет максимизировать.

Определение 7 При заданном значении а справедливым решением в игре Г называется решение задачи

1 *

тах--У^Мх)1 а,а> 0,а^1,

я 1 — а

г—1

где а - параметр справедливости.

При этом при а —► 0 решение стремится к глобально оптимальному; при а —* оо решение приближается к равновесию по Нэшу; решение, получаемое при а —> 1, называется пропорционально справедливым, а при а —> 2 - гармонически справедливым. То есть данный обобщенный критерий позволяет применять один и тот же метод для решения задач с различными критериями оптимальности.

В данной главе исследуются две основные модели. В первом варианте рассматривается задача построения справедливой схемы распределения в сети потоков трафика от пользовательских узлов к узлам доступа к внешнему сетевому пространству. Компонентами сети являются: 5 = {йг, г = 1,..., АГ} - узлы пользователей, генерирующие потоки; Т = {вг, г = (И + 1),..., (.М + ЬсоипЬ)} - переходные узлы; -О = {■<>',,, г = (АГ + Ыошй +1),..., (АГ + ¿со?т< + дсоипЬ)} - узлы внешнего доступа, поглощающие потоки;

Ь = {13 = (й,, 5к),з = 1, ■.. ,1соипР, 8г,вк е 5 и Т и £>} - каналы связи, для каждого j — 1,..., 1соигй с3 - пропускная способность канала 1}. Каждый канал может передавать потоки в обоих направлениях. Для

каждого канала = (st, Sk) определим направление st —> sfe как положительное, если i < к, и отрицательное, если г > к. Для каждого пользовательского узла sz по каналам 13 необходимо определить потоки: Ф°г - поток по каналу 13 в положительном направлении, фЗ+1соипг ._ поток по каналу Ц в отрицательном направлении. Потоки должны соответствовать следующим ограничениям:

1. величины всех потоков являются неотрицательными;

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

3. потоки, исходящие из узлов внешнего доступа по инцидентным им каналам, являются нулевыми;

4. для каждого транзитного узла сумма входящих в него потоков одного пользователя должна равняться сумме исходящих потоков того же пользователя;

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

Для каждого пользовательского узла st сумма генерируемых им потоков равна хг = ^ (Ф^ + <I>j+'couni), и ш, - весовой коэффициент. Тогда в соответствии с обобщенным критерием справедливости критерий оптимальности распределения потоков будет выглядеть следующим образом:

1 N (х \ 1~а

Fix) = -- ( —- I —» max,

2—1

где параметр справедливости а > 0, а ф 1. Для численного нахождения и визуализации решения данной задачи разработана программа, в основу вычислительной части которой положена реализация метода возможных направлений, адаптированного к быстрой обработке разряженных матриц как основной структуры хранения данных. С помощью данной программы были проведены численные эксперименты по решению задач маршрутизации и разделения пропускной способности каналов для участка сети ТрансТелеКом Центрально-Черноземного региона России, продемонстрировавшие применимость обобщенного критерия справедливости на практике.

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

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

N транзитных узлов (маршрутизаторов, коммутаторов, концентраторов);

Ь = 2ЛГ — 1 каналов связи, для каждого I — 1,Ь С1 - пропускная способность канала I.

Каждый г-й пользовательский узел соединяется г-м каналом с г-м тра-зитным узлом. Все транзитные узлы последовательно соединены между собой каналами связи, так что г-й транзитный узел соединен с г + 1-м транзитным узлом каналом связи с номером N + г.

В сети между парами пользовательских узлов создаются соединения по которым пользователи обмениваются данными. Каждое такое соединение между пользователями г < j занимает каналы г, г + Л,Г, г + Лг + 1, ... , N + ^ — 2, N + j — 1, Каждый пользователь г = 1..... Л'' создает одно соединение на некоторый другой пользовательский узел ]■ и ему выделяется квота на объем отправляемых данных хг. Для каждого пользователя г = 1,..., /V определены минимальные требования к отправке данных: хг > А,. Считаем, что пропускная способность сети позволяет выполнить все минимальные требования пользователей.

Среднее время прохождения единицы объема данных по каналу I равно

ад =

где агз — 1, если между пользователями г и ] существует соединение, и О - иначе. Для каждого пользователя г = 1,..., ./V определяется вогнутая функция полезности использования сети:

(шах{г,^} + Л/" —1

Тг(х)+ ]Г Щх) + Т3(х)

где ^ - номер узла, которому пользователь г отправляет данные (1 < ] < N \ агз — 1), иг(хг) - прибыль, получаемая пользователем от отправки данных. В соответствии с данным критерием справедливым решением будет решение задачи условной максимизации:

1 к

шах--УЧ^)1"01.«^ 1,

х 1 — а '

С1—Х1— £ ар1Хр р=1

ДЛЯ 1 < I < ЛГ,

С1~

l<p<l-N,l-N + l<q<N

у-1-, х+а х) для ЛГ + 1 < / < 2ЛГ — 1,

для всех 1 — 1,...,N хг > Аг, для всех 1 = 1,...,Ь Т^х) > 0.

В рассмотренных в диссертационной работе частных случаях таких задач полагается пропускная способность всех каналов связи равна с, а все Аг = 0. Пользователи, отправляя данные, получают прибыль, равную их,. Для частного случая с параллельной передачей данных в линейной сети, в которой четное число пользовательских узлов, а пользователи создают следующие попарные соединения: для каждого 1 < г < (г) —> (Лг - г + 1) и (./V - г + 1) —> (г) через каналы г, г + И, ... , 2АГ — г, N — г + 1, целевая функция имеет вид

N/2

1=1

N + N/2-1

1 —а X) I X

l=г+N

Х(Хг а + ^ЛГ-Л-ц)"

Для этой модели получена система нелинейных уравнений, решение которой дает оптимальное решение:

©'(ж) • Лад(2х) + ¿гад(3'(х)) ) ( {(Мх))~а}^ ) = 0,

где для 1 < г < — 1

е;»

{ -2Тг2+м(х), г < 3,

-2Т?+м(х)-2Т?(х), 1=3,

21? 1 + 1=3,

0, иначе,

и для всех 1 < з < ^ ©'«Да;) = &л:)(х)-,

т У

( 51 (а:) -52(х) 0 0

0 52(Х) -5З(®) 0

0 0 53(гс) -54 (ж)

V 0

О \ о о

(ж) )

<?г(ж) = 1^1 = и-

Хг

N + N/2-1

2Тг(ж) - 2 ^ Т,(ж) (ж).

1=1+N

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

для каждого 1 < г < N — 1 (г) —> (г + 1) через каналы г, г + ЛГ, г + 1; (И) -+ (1) через каналы 1, N + 1, ... , 2ЛГ — 1, ЛГ, целевая функция имеет вид

= гЬ - Г,(яг) - - Тг+1(х))1-»хг1"а+

г=1

2ЛГ-1

+ £ ВД-ВД)1-"^"".

г=лг+1

Система нелинейных уравнений для нахождения оптимального решения выглядит следующим образом:

(Т12(х)+Т^4,1(х)+Т22(х))х1-51(х) , Г22(х)х2 , (Т12(х)+Т^ + 1(х))х№ _

(/Их))" +1Шг+ (/«(х))"

Г2^,-, (Г,2(х)+Г2+,(х)+Г2+1(х))х,-3,(х)

(Л-1(х))° + (М*))" 2 ^

, т„+1(х)хы _ 2 < »' < /V — 9

Т^_1(х)хм_2 (Т2_1(х)+Т|Л,_1(х)+Г2(х))хЛ,-1-5;у-1(х)

I (^(х)+Гг2;у_1(х))хЛ, _

+ (/лг(х))« - и

(Т2(х)+Т2+1(х))х1 Т2+,(х)х, (Г|л,_1(х)+Г2(х))хл,_1 ,

(/.(х))» + (Л(х))- + (/*-!(*))" +

г=2

2N-l

{тЦх)+ £ Т12(х)+Т12(х))х«-5л(х)

+__ = О

В данной системе

ЗД = 1М = и- Тг(х) - Тм+1(х) - Тг+1(х), 1 < г < N - 1,

, , Ч 2ЛГ-1

5Дг(а:) = М^ = и-Глг(а:)- £ ВД - ВД.

ХМ ¡=N+1

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

Список опубликованных работ по теме диссертации

Статьи

[1] Чуйко Ю. В. Задача справедливого разделения емкости каналов сети между соединениями // Методы математического моделирования и информационные технологии. Труды ИПМИ. - Петрозаводск: КарНЦ РАН, 2004, 5, с. 136-146.

[2] Чуйко Ю. В. Задача выбора оптимального момента обращения к системе массового обслуживания для двух игроков // Методы математического моделирования и информационные технологии. Труды ИПМИ. - Петрозаводск: КарНЦ РАИ, 2005, 6, с. 243-252.

[3] Мазалов В. В., Чуйко Ю. В. Некооперативное равновесие по Нэ-шу в задаче выбора оптимального момента обращения к системе обслуживания // Вычислительные технологии, 2006, 11, N 6, с. 60-71, (вклад диссертанта 50%).

[4] Чуйко Ю. В. Равновесие но Нэшу в задаче оптимальной маршрутизации трафика в сети передачи данных// Системы управления и информационные технологии, 2006, N4(26), с. 37-40.

Тезисы докладов

[5] Чуйко Ю. В. Задача справедливого разделения емкости каналов сети между соединениями // Обозрение прикладной и промышленной математики, 2004, 11, вып. 2, с. 267-268.

[6] Chuiko J. V. The Problem of Fair Bandwidth Sharing in Linear Network // Труды 4-й Московской международной конференции по исследованию операций (ORM2004): Москва, 21-24 сентября 2004 г. - М.: МАКС Пресс, 2004, с. 52-54.

[7] Mazalov V. V., Chuiko J. V. An optimal airival time problem for queuing system. // Extended abstracts of International Workshop "Optimal Stopping and Stochastic Control", August 22-26, 2005, Petrozavodsk, Russia, 2005, pp. 49-50, (вклад диссертанта 50%).

[8] V. Mazalov, J. Chuiko, Nash Equilibria in Optimal Routing Problem // Extended abstracts of Russian-Finish Summer School "Dynamic Games and Multictriteria Optimization", September 2-7, 2006, Petrozavodsk, Russia, 2006, pp. 64-66, (вклад диссертанта 50%).

[9] Вдовицын В. Т., Луговая Н. В., Мазалов В. В., Чуйко Ю. В. Применение теоретико-игрового подхода для оптимального использования сети передачи данных // Научный сервис в сети Интернет: технологии параллельного программирования: Труды Всероссийской научной конференции (18-23 сентября 2006 г., г. Новороссийск) - М.: Изд-во МГУ, 2006, с. 207-208, (вклад диссертанта 30%).

Изд. лиц. № 00041 от 30.08.99. Подписано в печать 02.02.07. Формат 60x84 '/i6. Бумага офсетная. Гарнитура «Times». Печать офсетная. Уч.-изд. л. 1,0. Печ. л. 1,3. Тираж 100 экз. Изд. № 4. Заказ 644.

Карельский научный центр РАН 185003, Петрозаводск, пр. А. Невского, 50 Редакционно-издательский отдел

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Чуйко, Юлия Васильевна

Введение

1 Определение оптимального момента времени обращения к системе обслуживания

1.1 Постановка задачи.

1.2 Модель для системы с двумя игроками.

1.3 Равновесное по Нэшу решение задачи с двумя игроками

1.3.1 Решение для экспоненциальной функции "комфортности"

1.3.2 Решение для параболической функции "комфортности"

1.4 Модель для системы с числом игроков >3.

1.4.1 Вид функции "комфортности" в случае равномерных стратегий игроков.

1.4.2 Вид функции "комфортности" в случае экспоненциальных стратегий игроков.

1.5 Результаты.

2 Оптимальная маршрутизация трафика в сети передачи данных

2.1 Задача оптимальной маршрутизации в вероятностной постановке

2.1.1 Равновесие в чистых стратегиях.

2.1.2 Полностью смешанное равновесие в задаче с различными пользователями и одинаковыми каналами.

2.1.3 Полностью смешанное равновесие в задаче с одинаковыми пользователями и различными каналами.

2.1.4 Полностью смешанное равновесие в общем случае

2.2 Задача оптимальной маршрутизации с разделяемым трафиком

2.2.1 Равновесие по Нэшу.

2.2.2 Модель для системы с функциями задержки трафика на канале вида ^.

2.2.3 Оптимальность равновесия по Нэшу для системы т параллельных каналов с функциями задержки трафика на канале вида ^.

2.3 Результаты.

3 Справедливое разделение пропускной способности каналов

3.1 Критерий справедливости в задачах разделения пропускной способности

3.2 Маршрутизация и разделение пропускной способности каналов в открытой сети

3.2.1 Постановка задачи.

3.2.2 Математическая модель.

3.2.3 Сокращение размерности задачи.

3.2.4 Схема численного решения задачи.

3.2.5 Особенности реализации алгоритма решения.

3.2.6 Численные эксперименты.

3.3 Разделение пропускной способности каналов в линейной сети . . 81 3.3.1 Постановка задачи.

3.3.2 Случай параллельной передачи данных.

3.3.3 Случай последовательной передачи данных.

3.3.4 Схема приближенного решения задач.

3.3.5 Численные эксперименты.

3.4 Результаты.

Введение диссертация по математике, на тему "Сетевые игры и распределение ресурсов"

Актуальность темы. В настоящее время в связи с повсеместным внедрением, ростом и объединением вычислительных сетей стали актуальными задачи повышения их производительности. С ростом числа пользователей и увеличением объема обрабатываемой и передаваемой в сетях информации все чаще возникают проблемы, обусловленные высоким уровнем загруженности узлов и каналов связи. Более того, если на первых этапах своего развития вычислительные сети предназначались преимущественно для обеспечения совместного доступа пользователей к ресурсам сети (файлам, принтерам и т.п.), где отсутствовали жесткие требования на ограничение задержки передачи данных, то сейчас по сети передается также и мультимедийная информация в виде потоков, требующих синхронизации (видеоизображение, аудиопоток), что делает неприемлемым возникновение задержек, приводящих к искажению получаемой информации. Один из примеров - срыв Интернет-трансляции солнечного затмения 29 марта 2006 г., подготавливаемой коллективом САО РАН [1]. За время трансляции было зарегистрировано 1 200 ООО подключений (до 3000 в секунду, при норме в 250 подключений в секунду). Это привело к сбоям в работе сервера, десинхронизации и большим задержкам в передаче кадров. [2]

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

В области прикладной теории вероятностей новый импульс получила теория систем массового обслуживания, в котором исторически исследования велись в контексте управления загрузкой телефонных линий связи [4]. С развитием информационных технологий активно разрабатываются такие направления, как теория очередей (queuing theory) и теория транспортной загрузки (traffic theory) в применении к анализу работы вычислительных сетей.

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

В последнее время в исследованиях, связанных с оптимизацией работы вычислительных сетей, стали применяться методы некооперативной теории игр п лиц [5, б, 7, 8, 9]. Это направление получило название "сетевые игры" (Networking Games, Noncooperative Networks) [10, 11, 12, 13, 14]. При этом каждый пользователь сети или узел, входящий в сеть, трактуется как некоторый игрок, а задача распределения ресурсов сети рассматривается как игра, в которой игроки, действуя оптимально, могут достигать равновесия -ситуации, в которой никому из игроков не выгодно отклоняться от своей стратегии.

Один из классов задач данного направления связан с управлением загруженностью серверов - узлов сети, обрабатывающих запросы клиентов и отвечающих на них. Здесь сервер рассматривается как система массового обслуживания, обрабатывающая поток пользовательских заявок. В зависимости от назначения и условий работы сервера-прототипа в рассматриваемой модели система может обрабатывать одновременно одну или несколько заявок, может иметь одну или несколько очередей, или же в случае занятости системы заявка получает отказ в обслуживании. В работах [15,16] исследуются модели, в которых дисциплина поступления заявок в систему определяется стратегиями игроков, стремящихся минимизировать время ожидания своих заявок в очереди на обслуживание. В моделях [17, 18, 19, 20] дисциплина поступления заявок задается сверху, а в качестве сратегии рассматривается схема выбора одной из очередей. В работах [21, 22] рассматриваются модели, в которых пользователь, зная длину очереди на обслуживание на мощном сервере общего доступа, решает, отправлять ли свою заявку в очередь или выполнить ее на своей рабочей станции, стремясь минимизировать временные затраты.

Другой класс задач данного направления составляют задачи маршрутизации трафика, где пользователи, действуя в собственных интересах, самостоятельно выбирают свои маршруты, стремясь минимизировать задержку своего пересылаемого трафика. Здесь рассматриваются две базовые модели: модель Вардропа (Wardrop model) с произвольно разделяемым трафиком [23, 24, 25] и КР-модель (Koutsoupias, Papadimitriou) [23, 26, 27, 28, 29, 30, 31, 32, 33] с неделимым трафиком. В первой модели пользователи определяют количество трафика, посылаемого по каждому из маршрутов, а во второй - вероятности, с которыми может быть выбран каждый из маршрутов для отправки всего своего трафика. В работах, посвященных решению таких задач при задаваемом виде функций задержки трафика (например, линейных [24, 26, 33], квадратичных [32], полиномиальных [26, 29], произвольных выпуклых [34]), исследуется основной вопрос - насколько отказ от централизованного управления ухудшает систему, то есть насколько равновесные затраты всей системы в целом больше затрат в ситуации глобального оптимума.

К другому подклассу можно отнести задачи оптимальной маршрутизации трафика в сети. В отдельный подкласс таких задач можно выделить задачи определения схемы статической маршрутизации с справедливым разделением номинальной пропускной способности каналов сети между соединениями [35, 36, 37, 38]. В работе [39] схема статической маршрутизации в сети считается известной, и строится протокол контроля перегрузок, управляющий размером окна (TCPWindowSize) - количества пакетов, отправляемых до получения подтверждения о доставке при передаче по протоколу TCP [3, 40]. В перечисленных работах данного подкласса в качестве критерия оптимальности используется обобщенный критерий справедливости Валран-да (Walrand) [35], дающий, в зависимости от выбора задаваемого значения параметра справедливости, решение, близкое к глобально оптимальному, пропорционально или гармонически справедливому решению или к равновесию по Нэшу.

Во многих моделях, связанных с оптимизацией работы вычислительной сети, отдельного изучения требует вопрос возможного ухудшения качества работы сети при физическом наращивании мощности отдельных ее компонент. Этот вопрос в литературе получил название парадокса Браесса [41]. В частности, в задачах маршрутизации при добавлении нового канала могут увеличиться пользовательские затраты при отправке трафика [14,42,43]. Ряд 1 работ [14, 44] направлен на нахождение характеристик добавляемого канала, таких чтобы гарантированно избежать возникновения парадокса Браесса. В работах [45, 46, 47] исследуется вопрос проявления и обнаружения данного парадокса в равновесных ситуациях в рамках модели Вардропа.

1. задача выбора оптимального момента обращения игроков к системе массового обслуживания 7/М/1/0 с учетом заданной функции "комфортности";

В постановке задачи выбора оптимального момента обращения игроков к системе массового обслуживания 7/М/1/0 введено понятие функции "комфортности", для данной модели получен аналитический вид равновесного решения для для случая двух игроков. Для случая п + 1 > 3 игроков построен общий вид функции выигрыша и решены задачи нахождения вида необходимой функции "комфортности" для того, чтобы равновесные стратегии игроков имели заданный вид: равномерное и экспоненциальное распределение. Для этих задач проведен анализ поведения системы при бесконечно большом количестве игроков.

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

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

Положения, выносимые на защиту. На защиту выносятся следующие положения.

1. Найдены равновесия в задачах выбора оптимального момента обращения игроков к системе массового обслуживания ?/М/I/O с учетом заданной функции "комфортности".

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

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

2. Международный семинар "Optimal Stopping and Stochastic Control" (Петрозаводск, 22-26 августа 2005 г., ИПМИ КарНЦ РАН);

3. Российско-финская летняя школа "Dynamic Games and Multicriteria Optimiza 2-7 сентября 2006, Петрозаводск.

По материалам диссертации опубликовано 9 работ, из них 4 статьи [48, 49, 50, 51] и тезисы 5 докладов [52, 53, 54, 55, 56].

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

Заключение диссертации по теме "Дискретная математика и математическая кибернетика"

Заключение

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

Рассмотрена задача выбора оптимального момента обращения игроков к системе массового обслуживания 7/М/1/0 с учетом заданной функции "комфортности". Для случая двух игроков найден аналитический вид равновесного решения и условия его допустимости. Для частных случаев задачи с экспоненциальной и параболической функциями "комфортности" проведен анализ существования допустимого равновесного решения. Для случая п + 1 > 3 игроков построен общий вид функции выигрыша и решены задачи нахождения вида необходимой функции "комфортности" для того, чтобы равновесные стратегии игроков имели заданный вид: равномерное и экспоненциальное распределение. Для этих задач проведен анализ поведения системы при бесконечно большом количестве игроков.

Рассмотрена задача оптимальной маршрутизации трафика в сети в двух вариантах постановки: вероятностная модель задачи маршрутизации с неделимым трафиком, основанная на КР-модели, и модель с разделяемым трафиком, основанная на модели Вардропа. В КР-модели для случая одинаковых каналов найдены линейные и квадратичные затраты системы в полностью смешанном равновесии. В этой же модели для случаев различных каналов найдены линейные и квадратичные затраты системы в полностью смешанном равновесии, а также условия ухудшения такого равновесия при добавлении в систему нового канала. Для модели Вардропа доказана в общем виде связь равновесия по Нэшу с равновесием по Вардропу. Данное свойство позволяет получить явный вид системы уравнений и неравенств для нахождения ситуаций равновесия по Нэшу. Для случая с заданным видом функций задержки трафика fiR^x) = YleeRi сс-1%) Д°казапа равносильность определений равновесия по Нэшу и по Вардропу. Для частного случая с параллельными каналами доказана глобальная оптимальность равновесных по Нэшу ситуаций и для случая общедоступных каналов найдено равновесие.

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

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

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Чуйко, Юлия Васильевна, Петрозаводск

1. Кульгин М. Практика построения компьютерных сетей. Для профессионалов. СПб.: Питер, 2001, - 320 с.

2. Cooper R. В. Introduction to Queuing Theory, 1981, 348 p.

3. Дрешер M. Стратегические игры. М.: Издательство "Советское радио", 1964, - 352 с.

4. Мак-Кинси Дж. Введение в теорию игр. М.: Государственное издательство физико-математической литературы, 1960, - 420 с.

5. Муллен Э. Теория игр с примерами из математической экономики. Пер. с франц. М.: Мир, 1985, - 200 с.

6. Оуэн Г. Теория игр. М.: Мир, 1971, - 230 с.

7. Теория игр: учебное пособие для университетов / Петросян JI. А., Зенкевич Н. А., Семина Е. А. М.: Высшая школа, 1998, - 300 с.

8. Altman Е., Boulogne Т., El Azouzi R., Jimenez Т. and Wynter L. A survey on networking games // Computers and Operations Research, 2004.

9. Altman E., Wynter L. Equilibrium, games, and pricing in transportation and telecommunications networks // Crossovers between Transportation Planning and Telecommunications, 2004, 4, N 1, pp. 7-21.

10. El Azouzi R., Altman E. Constrained Traffic Equilibrium in Routing Networks // IEEE Trans, on Automatic Control, 2003, 48, N 9, pp. 1656-1660.

11. El Azouzi R., Altman E., Wynter L. Telecommunications Network Equilibrium with Price and Quality-of-Service Characteristics // Proc. of ITC, Berlin, Sept 2003, http://www-sop.inria.fr/mistral/personnel/Rachid. Elazouzi/R-ElazouziITC.ps.

12. Korilis Y. A., Lazar A. A., Orda A. Architecting noncooperative networks // J. on Selected Areas in Communications, 1995, 13, N 7, pp. 1241-1251.

13. Glazer A., Hassin R. ?/M/l: On the equilibrium distribution of customer arrivals // European Journal of Operational Research. 1983, 13, N 2, pp. 146-150.

14. Glazer A., Hassin R. Equilibrium arrivals in queues with bulk service at scheduled times // Transportation Science, 1987, 21, N 4, pp. 273-278.

15. Altman E. Applications of dynamic games in queues // Advances in Dynamic Games, 2005, 7, pp. 309-342.

16. Altman E. A Markov game approach for optimal routing into a queueing network 11INRIA report N 2178, 1994.

17. Altman E., Jimenez Т., Nunez Queija R. and Yechiali U. Optimal routing among -/М/1 queues with partial information j j Stochastic Models, 2004, 20, N 2, pp. 149-172.

18. Altman E., Koole G. Stochastic scheduling games with Markov decision arrival processes // Journal Computers and Mathematics with Appl., 1993, 26, N 6, pp. 141-148.

19. Altman E., Hassin R. Non-Threshold Equilibrium for Customers Joining an M/G/l Queue Non-Threshold Equilibrium for Customers Joining an M/G/l Queue, 2002, http://www-sop.inria.fr/maestro/personnel/Eitan. Altman/PAPERS/hassin.ps.

20. Altman E., Shimkin N. Individually Optimal Dynamic Routing in a Processor Sharing System // Operations Research, 1998, pp. 776-784.

21. Feldmann R., Gairing M., Lucking Т., Monien В., Rode M., Selfish routing in non-cooperative networks: a survey. In Proc. of 28th Int. Symp. on Mathematical Foundation of Computer Science, LNCS 2747, 2003, pp. 21-45.

22. Wardrop J. G. Some theoretical Aspects of Road Traffic Research // Proceedings of the Institute of Civil Engineers, 1952, II, 1, pp. 325-278.

23. Awerbuch В., Azar Y., Epstein A. The Price of Routing Unsplittable Flow // Proceedings of the 37th Annual ACM Symposium on Thery of Computing (STOC'05), 2005, pp. 57-66.

24. Awerbuch В., Azar Y., Richter Y, Tsur D. Tradeoffs in worst-case equilibria //In Proceedings of 1st WAOA, 2003, pp. 41-52.

25. Feldmann R., Gairing M., Lucking Т., Monien В., Rode M., Nashification and the coordination ratio for a selfish routing game. In Proc. of the 30th Int. Colloc. on Automata, Languages and Programming, LNCS 2719, 2003, pp. 514-526.

26. Gairing M., Lucking Т., Mavronicolas M., Monien B. The price of anarchy for polynomial social cost // Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), 2004, pp. 574-585.

27. Koutsoupias E., Papadimitriou С. H. Worst-case Equilibria // Proceedings of STACS 1999, 1999, 1563, pp. 404-413.

28. Lucking Т., Mavronicolas M., Monien В., Rode M., Spirakis P., Vrto I. Which is the Worst-case Nash Equilibrium? // Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science, 2003, LNCS 2747, pp. 551-561, 2003.

29. Lucking Т., Mavronicolas M., Monien В., Rode M. A New Model for Selfish Routing // Proceedings of STACS 2004, 2004, LNCS 2996, pp. 547-558.

30. Mavronicolas M., Spirakis P. The Price of Selfish Routing // Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 2001, pp.510.519.

31. Gairing M., Liicking Т., Mavronicolas M., Monien В., Rode M., Nash equilibria in discrete routing games with convex latency functions // Proceedings of the 31th Int. Colloc. on Automata, Languages and Programming, LNCS 2719, 2004, pp. 645-657.

32. Maulloo A., Kelly F. P., Tan D. Rate control in communication networks: shadow prices, proportional fairness and stability //J. Oper. Res. Society, 1998, 49, pp. 237-252.

33. Touati C., Altman E., Galtier J. On fairness in bandwidth allocation // INRIA Research report RR-4269, 2001.

34. Touati C., Altman E., Galtier J. Semi-Definite Programming Approach for Bandwidth Allocation and Routing in Networks // Game Theory and Application Nova publisher, 2003, 9, pp. 169-179.

35. Touati C., Altman E., Galtier J. Utility-based fair bandwidth allocation // In IASTED NPDPA, 2002.

36. Mo J., Walrand J. Fair end-to-end window-based congestion control // IEEE/ACM Transactions on Networking (TON), 2000, 8, N 5, pp. 556-567.

37. Чегтел JI., Титтел Э. TCP/IP. Учебный курс. Пер. с англ. СПб.: БХВ-Петербург, 2003, 976 с.

38. Murchland J. D. Braess's paradox of traffic flow // Transportation Research, 1970, 4, pp. 391-394.

39. Bean N. G., Kelly F. P., Taylor P. G. Braess' Paradox in a Loss Network, Journal of Applied Probability, 1997, 34, pp. 155-159.

40. Roughgarden Т., Tardos Ё. How bad is selfish routing? j j Journal of the ACM, 2002, 49, N 2, pp. 236-259.

41. Korilis Y. A., Lazar A. A., Orda A. Avoiding the Braess paradox in non-cooperative networks // J. Appl. Prob., 1999, 36, 211-222.

42. Hagstrom J. N., Abrams R. A. Characterizing Braess's paradox for traffic networks // Proceedings of IEEE 2001 Conference on Intelligent Transportation Systems, 2001, pp. 837-842.

43. Lin H., Roughgarden Т., Tardos Ё. On Braess's Paradox // Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, LA, 2004, pp. 333-334.

44. Roughgarden T. On the severity of Braess's paradox: Designing networks for selfish users is hard // J. of Computer and System Sciences, 2006, 72, pp. 922-953.

45. Чуйко Ю. В. Задача справедливого разделения емкости каналов сети между соединениями // Методы математического моделирования и информационные технологии. Труды ИПМИ. Петрозаводск: КарНЦ РАН, 2004, 5, с. 136-146.

46. Чуйко Ю. В. Задача выбора оптимального момента обращения к системе массового обслуживания для двух игроков // Методы математического моделирования и информационные технологии. Труды ИПМИ. -Петрозаводск: КарНЦ РАН, 2005, 6, с. 243-252.

47. Мазалов В. В., Чуйко Ю. В. Некооперативное равновесие по Нэшу в задаче выбора оптимального момента обращения к системе обслуживания

48. Вычислительные технологии, 2006, И, N 6, с. 60-71.

49. Чуйко Ю. В. Равновесие по Нэшу в задаче оптимальной маршрутизации трафика в сети передачи данных// Системы управления и информационные технологии, 2006, N4(26), с. 37-40.

50. Чуйко Ю. В. Задача справедливого разделения емкости каналов сети между соединениями // Обозрение прикладной и промышленной математики, 2004, И, вып. 2, с. 267-268.

51. Chuiko J. V. The Problem of Fair Bandwidth Sharing in Linear Network // Труды 4-й Московской международной конференции по исследованию операций (ORM2004): Москва, 21-24 сентября 2004 г. М.: МАКС Пресс, 2004, с. 52-54.

52. Mazalov V. V., Chuiko J. V. An optimal arrival time problem for queuing system. // Extended abstracts of International Workshop "Optimal Stopping and Stochastic Control", August 22-26,2005, Petrozavodsk, Russia, 2005, pp. 49-50.

53. V. Mazalov, J. Chuiko, Nash Equilibria in Optimal Routing Problem // Extended abstracts of Russian-Finish Summer School "Dynamic Games and Multictriteria Optimization", September 2-7, 2006, Petrozavodsk, Russia, 2006, pp. 64-66.

54. Belkovskii D. V., Garnaev A. Y. A Competitive Prediction Number Game under Unsymmetrical Conditions // Game Theory and Applications, 10, Nova Sci. Publ., Commack, NY, 2005, pp. 27-36.

55. Sakaguchi M., Szajowski K. Competitive prediction of a random variable // Mathematica Japonica, 1996, 43, N 3, pp. 461-472.

56. Gairing M., Lucking Т., Mavronicolas M., Monien В., Spirakis P. Extreme Nash Equilibria // Proceedings of the 8th Italian Conference on Theoretical Computer Science (ICTCS'03), LNCS 2841, 2003, pp. 1-20.

57. Васильев Ф. П. Численные методы решения экстремальных задач. М.: Наука, 1980, - 520 с.

58. Юго-Восток ТрансТелеКом http://www.uvttk.ru/

59. Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. М.: Наука, 1986, - 328 с.

60. Численные методы условной оптимизации / Под ред. Гилла Ф., Мюррэя У. М.: Мир, 1977, - 290 с.