Содержание к диссертации
Введение
1. Принципы моделирования вычислительной сети 12
1. Основные сложности построения математической модели вычислительной сети 12
2. Теорема об ON/OFF процессе 19
2. О методе кумулятивных сумм в задаче обнаружения изменения свойств трафика 22
1. Постановка задачи 22
2. Определение аналитического вида Мог для распределения Парето 28
3. Определение аналитического вида М^т для распределения Парето 36
4. Имитационное моделирование процедуры поиска разладки 42
5. Применение метода кумулятивных сумм для обнаружения компьютерных атак 47
3. Теоретико-игровые методы в задачах исследования трафика 60
1. Основные определения 60
2. Определение момента прекращения поиска сигнатуры 63
3. Определения оптимального поведения для повышения уровня загрузки телекоммуникационного оборудования 69
4. Задача оптимального выбора для памяти телекоммуникационного оборудования 82
1. Использование урновых моделей при проектировании ATM коммутатора 82
2. Основные определения 86
3. Оптимальная политика выбора в урновой модели с двумя типами шаров 87
4. Парадокс сравнения урн 103
Литература 109
- Теорема об ON/OFF процессе
- Имитационное моделирование процедуры поиска разладки
- Определения оптимального поведения для повышения уровня загрузки телекоммуникационного оборудования
- Оптимальная политика выбора в урновой модели с двумя типами шаров
Введение к работе
В настоящее время существует два основных подхода для моделирования трафика вычислительной сети. При первом подходе фиксируется время и измеряются текущие характеристики сети. Далее, исходя из полученных данных, строится и исследуется математическая модель [36, 81].
Основными недостатками данного подхода являются:
привязанность модели ко времени;
на этапе выделения существенных характеристик получается большое количество параметров одного порядка значимости;
большой размер сети делает сложным получение статистически значимого результата (в смысле "репрезентативности выборки").
Второй подход известен как принцип экономии (principle of parsimony) [50, 56]. Его основная идея состоит в нахождении таких характеристик, которые остаются инвариантными для различных сетей. Поиск подобных характеристик привел к достаточно неожиданным результатам. Прежде всего, было обнаружено большое количество параметров с бесконечной дисперсией (Noah effect) [47, 80, 93, 94]. К таким параметрам относятся: время работы процессора, размеры файлов, времена между приходами пакетов имели функцию распределения с тяжелым хвостом.
Вторая инвариантная характеристика была впервые обнаружена в 1993 году группой ученых (Leland W., Taqqu М., Willinger W. и Wilson D.), которые исследовали Ethernet-трафик в сети Bellcore и обнаружили, что он обладает самоподобием [66]. Под самоподобием подразумевается повторя-
емость распределения нагрузки во времени при различных масштабах. Это означает, что, если мы нарисуем график зависимости плотности информационного потока от времени, взяв за единицу измерения секунду, минуту, час и так далее, то каждый раз получим практически одинаковые диаграммы.
После того, как данный феномен был доказан, большое количество исследователей занялись проблемой самоподобия сетевого трафика. Например, сразу после введения в использование World Wide Web (WWW) появились публикации на тему самоподобия трафика и в этой системе [41, 47, 79]. Удалось определить, что возможная причина такого странного эффекта заключается в особенностях распределения файлов по серверам, их размерах, а также в типичном поведении пользователей [47, 67, 78, 95, 97]. Еще одна причина была обнаружена в ходе недавних исследований, проведенных под руководством Фенга В. и Тиннакорнсрисуфа П. В данном исследовании был поставлен под сомнение протокол TCP: то есть заведомо не проявляющий признаков самоподобия трафик, пройдя через стек протоколов TCP/IP, модулируется последним и превращается в самый настоящий "сетевой фрактал". Особенно сильно этот эффект заметен в высокоскоростных сетях [18].
Также было замечено, что агрегированный самоподобный процесс обладает свойством долговременной зависимости (Joseph Effect или long-range dependence) [47, 54, 83]. То есть, будущее процесса определяется его прошлым, причем с убывающей степенью влияния по мере того, как прошлое удалено от настоящего. Таким образом, процесс с долговременной зависимостью как бы медленно "забывает" свое относительно давнее прошлое по мере продвижения в будущее.
Существует несколько подходов для моделирования трафика вычислительной сети, обладающего свойством долговременной зависимости:
суперпозиция ON/OFF процессов [54];
суперпозиция M/G/oo процессов, где времена обслуживания имеют функцию распределения с тяжелым хвостом [42].
В данной работе используется ON/OFF процесс: идеализированный источник пакетов переключается между ON состоянием, в котором происходит передача данных с постоянной интенсивностью, и OFF состоянием молчания. Длины ON и OFF периодов независимы; ON периоды одинаково распределены с функцией распределения, имеющей тяжелый хвост, то же справедливо для OFF периодов. На практике, как правило, если известно, что распределение имеет тяжелый хвост, то работают с Парето функцией распределения с дополнительным ограничением на показатель а < 2 [47, 78].
В диссертационной работе исследована задача скорейшего обнаружения разладки для ON и OFF периодов. При этом разладкой считается изменение показателя а функции распределения Парето. Полученный в ходе исследования результат позволяет обнаруживать аномальное поведение пользователя в вычислительной сети.
Еще одна задача, связанная с анализом трафика вычислительной сети, — поиск заданного шаблона сетевой атаки. При этом в системах, работающих с большим потоком данных, возникает следующая проблема: из-за физической неспособности системы контролировать весь поток данных необходимо определить интервал времени, в котором будет производиться поиск шаблона. Фактически, необходимо найти
момент прекращения наблюдения, так как момент начала считается заданным.
Следующий тип задач, рассмотренный в данной работе, — это задачи оптимизации работы телекоммуникационного оборудования. В данной работе решаются две задачи, данного типа:
задача динамического распределения нестраничной памяти;
задача определения оптимальной стратегии выбора при работе с буферной памятью.
Подобные задачи возникают, например, при проектировании современных маршрутизаторов. Данные устройства имеют несколько режимов работы (нормальный, критический и т.д.). При работе в критическом режиме маршрутизатор получает пакеты быстрее, чем может отправить их через имеющийся интерфейс (например, когда входной интерфейс быстрее выходного, или когда пакеты с разных входных интерфейсов направляются на один и тот же выходной интерфейс), и тогда он помещает их в очередь (буферную память). Простейший способ организации очереди, когда пакеты помещаются в очередь и отправляются в порядке их поступления, во многих ситуациях неэффективен [6]. Одним из решений данной проблемы является использование результатов, полученных для урновых моделей, для выделения данных, которые необходимо отбросить из буферной памяти [57, 64, 98].
Основными методами исследования в диссертации являются методы последовательного анализа, методы оптимальной остановки, методы комбинаторики и методы теории игр.
Диссертация состоит из четырех глав. Первая глава носит вводный характер. В ней рассматриваются проблемы построения математической модели вычислительной сети, даются основные определения и приводится теорема об ON /OFF процессе. Данная теорема показывает взаимосвязь между распределением ON и OFF периодов и долговременной зависимостью процесса.
Во второй главе для определения момента изменения показателя Парето функции распределения ON и OFF периодов применяется метод последовательного анализа (метод кумулятивных сумм). В отличие от классических методов математической статистики, в которых число производимых наблюдений заранее фиксируется, методы последовательного анализа характеризуются тем, что момент прекращения наблюдения (момент остановки) является случайным и определяется наблюдателем в зависимости от значений наблюдаемых данных [20, 34]. Качество правила остановки метода кумулятивных сумм оценивается следующими характеристиками: среднее время задержки определения разладки Мот и среднее время до ложной тревоги МооТ. Как правило, получить Мот и МооТ в аналитическом виде удается лишь в специальных случаях [20]. В параграфах II.2, И.З удалось получить аналитический вид данных характеристик.
В третьей главе найдены оптимальные стратегии игроков в антагонистической игре, в которой два игрока пытаются угадать значение реализации случайной величины. При этом функция распределения данной величины известна им обоим. Данные стратегии задают правила, согласно которым производится поиск заданного шаблона атаки (сигнатуры) в сетевом трафике. При этом учитывается тот факт, что система обнаружения атаки работает с большим потоком дан-
ных. Также в данной главе решена задача оптимизации работы телекоммуникационного оборудования, в которой необходимо определить оптимальное поведение для повышения уровня загрузки данного устройства (в заданном смысле). То есть, необходимо задать правила, согласно которым будет осуществляться выбор среди предложенных вариантов различных заявок, пришедших на обслуживание. При этом, если заявками считать свободные блоки памяти способные удовлетворить запрос на размещение данных, заданной длины, то данная задача является задачей динамического распределения нестраничной памяти [24, 45]. Решение описанной задачи найдено в классе однопороговых стратегий для антагонистической симметричной игры п лиц, в которой необходимо получить максимальную загрузку среди п одинаковых устройств.
В четвертой главе найдена стратегия игрока, позволяющая оптимизировать работу буферной памяти телекоммуникационного устройства. Для моделирования данной работы используется урновая модель с двумя типами шаров. Каждый тип характеризует "предпочтительность" пришедшей заявки (полученного шара) для игрока. В данной главе исследованы свойства средней "предпочтительности" при оптимальной стратегии игрока.
Основные результаты диссертации:
1. Получено аналитическое выражение среднего времени задержки определения разладки и среднего времени до ложной тревоги в задаче определения разладки методом кумулятивных сумм для случая, когда входной поток имеет распределение Парето. При этом разладкой считается изменение показателя Парето закона распределе-
ния.
Задача обнаружения заданного шаблона атаки в условиях сильной загруженности трафиком вычислительной сети сформулирована как антагонистическая симметричная игра 2-х лиц. Решение игры найдено в смешанных стратегиях для случая явного задания функции распределения шаблона атаки.
Задача динамического распределения нестраничной памяти сведена к задаче оптимальной остановки. Решение данной задачи найдено в классе однопороговых правил остановки.
Задача оптимизации управления буферной памятью сформулирована и решена как задача наилучшего выбора из заданного числа заявок двух типов.
Основные результаты диссертации опубликованы автором в 7 работах [7, 8, 9, 10, 17, 16, 99], из них 1 статья в журнале "Программирование" [17], 2 статьи в сборниках трудов Института прикладных математических исследований Карельского научного центра РАН [7, 10], 4 тезиса докладов на международных, всероссийских и региональных конференциях [8, 9, 16, 99]. Результаты также докладывались на VII Международной конференции по электронным публикациям "EL-Pub2002" (Новосибирск, 2002 г.), International Workshop "Networking games and resource allocation" (Петрозаводск, 2002 г.), Kalashnikov Memorial Seminar (Петрозаводск, 2002 г.), IV Всероссийском симпозиуме по прикладной и промышленной математике (Петрозаводск, 2003 г.), Семинаре "Неделя Финской Информатики" (Петрозаводск, 2003 г.), VI Международной конференции "Вероятностные мето-
ды в дискретной математике" (Петрозаводск, 2004 г.).
Основные результаты, представленные в данной диссертации, были получены в ходе выполнения проекта "Применение теоретико-игровых методов в задачах поиска, распределения и защиты информационных ресурсов в компьютерных
+ сетях" в рамках программы № 4 фундаментальных исследо-
ваний Отделения математических наук РАН "Математические и алгоритмические проблемы информационных систем нового поколения".
В диссертации принята двойная нумерация параграфов и тройная нумерация теорем, лемм, формул и замечаний. Это значит, что параграф III.4 является четвертым по порядку в главе III, а теорема 1.2.3 является третьей по порядку в
т параграфе 1.2.
Теорема об ON/OFF процессе
В данной работе для моделирования сетевого трафика будем использовать стационарный ON/OFF процесс с ON распределением Fon и OFF распределением F0jf. То есть, идеализированный источник пакетов переключается между ON состоянием, в котором происходит передача данных с посто янной интенсивностью, и OFF состоянием молчания. В ниже приведенной теореме 1.2.1 показана взаимосвязь между распределениями Fon и F0ff и долговременной зависимостью процесса ON /OFF. Пусть две независимые последовательности случайных величин. Случайные величины из последовательности (1.2.1)—независимые, одинаково распределенные с функцией распределения Fon и математическим ожиданием jion оо. Для случайных величин (1.2.2) известно, что они независимые, одинаково распределенные с функцией распределения F0ff и математическим ожиданием fioff оо. Дополнительно введем три независимые случайные величины , (\ 77 , которые также не зависят от последовательностей случайных величин (1.2.1) и (1.2.2). Случайная величина f имеет распределение Бернулли с параметром Законы распределения для случайных величин \ т/) определены следующим образом Определим процесс (9(t),t 0). Если С = 1, тогда fj = +770, ty» = SU+fn, и & = г/п+т/ для п = 1,2,..., и Теорема 1.2.1 (HeatD., ResnickS., Samorodnitsky G.). Пусть ON распределение Fon имеет тяжелый хвост с по- ш казателем 1 а 2, и F0ff(t) = o(Fon(t)) при t — оо. Тогда для R(t) = cov(0(s), 6(s + t)), t 0 верно Замечание 1.2.1. .Єсл OFF распределение F0ff с тяжелым хвостом с показателем 1 а 2, и Fon(t) = o(F0ff(t)) при t -+ оо7 то теорема 1.2.1 верна. В статье [54] доказано, что если оба закона распределения Fon, F0ff имеют тяжелый хвост, то процесс (9(t) t 0) также обладает долговременной зависимостью. О методе кумулятивных сумм в задаче обнаружения изменения свойств трафика II. 1 Постановка задачи Пусть в — случайная величина, принимающая значения 0,1,..., а наблюдения i, г таковы, что при условии в = п величины независимы и одинаково распределены с Парето функцией распределения Независимые, одинаково распределенные случайные величины также имеют Парето функцию распределения Параметры к\ и к2 равны наименьшему из возможных наблюдений. Далее будем считать, что к\ Плотности законов распределения (II. 1.1) и (II. 1.2) обозначим соответственно: Таким образом, в момент в происходит разладка, то есть изменение вероятностных характеристик наблюдаемого процесса.
В данном случае это изменение показателя Парето закона распределения. Рассмотрим задачу определения по наблюдениям момента появления разладки [29, 31, 32]. Из всех последовательных параметрических методов обнаружения разладки необходимо выбрать такой метод, который удовлетворяет следующим условиям: 1. распределение момента появления разладки неизвестно; 2. размерность вектора изменяемого параметра равна 1; 3. известно значение параметра после разладки; 4. последовательность наблюдений независима. Существует три метода, представляющих наибольший практический и теоретический интерес и удовлетворяющих данным условиям. Первый из них —метод кумулятивных сумм. Следующий метод основан на многократном использовании процедуры проверки гипотезы Яо (нет разладки) против Hi (есть разладка) согласно критерию Неймана— Пирсона для специальным образом построенной вспомогательной выборки [13]. Третий метод обнаружения разладки основан на экспоненциальном сглаживании [85]. Только метод кумулятивных сумм удовлетворяет следующим дополнительным требованиям: 1. Устойчивость работы алгоритма обнаружения разладки к влиянию мешающих параметров [1, 20]. 2. Независимость алгоритма от априорного распределения момента разладки и "равномерная" эффективность обнаружения разладки по времени ее возникновения. Действительно, зависимость запаздывания момента обнаружения разладки от момента появления разладки #, полученная аналитическими и численными исследованиями, имеет пологий характер и быстро приближается к гори зонтальной асимптотике при в — оо [1, 29]. 3. Простота реализации на ЭВМ. Также, в работе [69] Л орденом Г. была доказана асимптотическая оптимальность метода кумулятивных сумм в смысле критерия, минимизирующего величину То есть, оптимальность понимается как минимизация среднего запаздывания в наиболее неблагоприятный момент изменения г. Таким образом, далее будем использовать наиболее пред- # почтительный в практическом отношении метод — метод ку мулятивных сумм.
Впервые он был предложен Пейджем Е. С. в работе [75]. Данный метод представляет собой многократно применяемый последовательный анализ Вальда А., а именно, последовательный критерий отношения вероятностей для двух простых гипотез Но (нет разладки) и Н\ (есть разладка) [5]. Идея Пейджа Е. С. состоит в анализе поведения следующей величины которая в последовательном критерии отношения вероятностей сравнивается на каждом шаге с двумя порогами: є и , где /і є 0. Если на шаге п значение Sn ц, то принимается гипотеза Hi, если Sn є, то принимается Щ, а если є Sn № то выполняется п+1 наблюдение. Однако прямо применить последовательный критерий отношения вероятностей к задаче о разладке нельзя, так как в ней нарушено предположение о принадлежности всей выборки к гипотезе HQ или Н\. Поэтому Пейдж Е. С. предложил возобновлять применение последовательного критерия отношения вероятностей на шаге п из единицы после того, как на шаге п — 1 принята гипотеза Щ [20]. И так до тех пор, пока не появится разладка. После того, как гипотеза Hi сменила Н$, математическое ожидание отношения правдоподобия будет больше или равно единице, и Sn начнет расти. Позднее Ширяев А. Н. доказал, что выбор порога є = 1 оптимален [30, 33]. Таким образом, метод кумулятивных сумм имеет простую рекуррентную запись При этом обнаружение осуществляется посредством пра- вила остановки, имеющего следующий вид Графическая иллюстрация многократного применения последовательного критерия отношения вероятностей показана на рисунке 1. Существует и другое, быть может, более наглядное толкование метода кумулятивных сумм.
Имитационное моделирование процедуры поиска разладки
Выше показано, что ряды для определения Мот и М т могут расходится при определенных значениях параметров а, /?, /І. Пусть [0, /z ] и [0, /xj] — интервалы сходимости для рядов определяющих соответственно среднее время задержки определения разладки и среднее время до ложной тревоги. Тогда в таблице 2 и таблице 3 представлены значения /І и /І соответственно. Так, например, при а = 1, /3 = 0.3 значение Для а = 1 и /3 = 0.3 выберем значение при котором ряд для определения МооТ расходится, а для Мог конечен. В результате численного моделирования для случая 100 наблюдений с фиксированной разладкой в момент п = 51 получены следующие результаты. Было проведено 100000 экспериментов, и оказалось, что среднее число ложных тревог было равно г = 0.05, а время запаздывания Мот = 4.12, (сравните с аналитическим значением Ъ/IQT = 3.7). Также проводилось численное моделирование, в котором момент разладки был дискретной случайной величиной, принимающей значения 1,..., 100 с одинаковой вероятностью 0.01. В результате проведения 100000 экспериментов были получены следующие результаты г — 0.08, Мот = 4.2. Аналогичные эксперименты проводились для а = 0.1,0.2,..., 1.9 и (3 = 0.1,0.2,..., 1.9. Данное моделирование продемонстрировало хорошее согласие с аналитическим результатом, полученный в параграфах П.2 и П.З. Для проведения имитационного моделирования была написана программа на языке perl, в которой генерация псевдослучайных чисел с периодом 232 проводилась при помощи модуля Math::TrulyRandom. Все численные вычисления в данной работе производились при помощи системы компьютерной математики "Mathcad". Любая, даже самая совершенная защита компьютерных систем не может быть названа абсолютно надежной. Большинство экспертов по компьютерной безопасности соглашаются с тем, что создать абсолютно защищенную систему никогда не удастся. Поэтому столь актуальной остается задача создания методов и систем для выявления и реагирования на компьютерные атаки. Будем считать атакой любое действие нарушителя, которое приводит к реализации угрозы путем использования уяз-вимостей вычислительной системы [14]. Методы обнаружения атак принято разделять на методы обнаружения аномалий и методы обнаружения злоупотреблений. Системы обнаружения злоупотреблений, по существу, определяют, что идет не так, как должно. Они содержат описания шаблонов атак ("сигнатуры") и ищут соответствие этим описаниям в проверяемом потоке данных с целью обнаружить проявление известной атаки [55]. Одна из таких атак, к примеру, возникает, если кто-то создает символьную ссылку на файл паролей ОС Unix и выполняет привилегированное приложение, которое обращается по этой символьной ссылке.
В данном примере атака основана на отсутствии проверки при доступе к файлу. Основное преимущество систем обнаружения злоупотреблений состоит в том, что они сосредотачиваются на анализе проверяемых данных и обычно порождают очень мало ложных тревог. Данные методы оперируют описаниями сценариев известных атак и сопоставляют наблюдаемое поведение объектов системы с этими описаниями. Такие системы обеспечивают высокую эффективность обнаружения известных атак, но не могут самостоятельно адаптироваться к новым атакам. Методы обнаружения аномалий используют историю функционирования вычислительной системы для формирования профилей нормального поведения объектов системы. Поиск аномалий в поведении объектов позволяет обнаруживать ранее неизвестные атаки. Считается, что начало этому направлению было положено в 1980 г. статьей Андерсона Д. "Мониторинг угроз компьютерной безопасности" [38]. Основной постулат обнаружения аномалий состоит в том, что атаки отличаются от нормального поведения [49]. Скажем, определенную повседневную активность пользователей можно смоделировать достаточно точно. Допустим, конкретный пользователь обычно регистрируется в системе около десяти часов утра, читает электронную почту, выполняет транзакции баз данных, уходит на обед около часа дня, допускает незначительное количество ошибок при доступе к файлам и так далее. Если система отмечает, что тот же самый пользователь зарегистрировался в системе в три часа ночи, начал использовать средства компиляции и отладки и делает большое количество ошибок при доступе к файлам, она пометит эту деятельность как подозрительную [14]. Аномальное поведение не всегда является атакой.
Например, рассылку большого числа писем по электронной почте при организации конференции многие системы обнаружения атак идентифицируют как атаку типа "отказ в обслуживании" ("denial of service"). С учетом этого факта можно заметить, что возможны два крайних случая при эксплуатации системы: 1. обнаружение аномального поведения, которое не является атакой, и отнесение его к классу атак; 2. пропуск атаки, которая не попадает под определение аномального поведения. Второй случай гораздо более опасен, чем первый. Главное преимущество систем обнаружения аномалий заключается в том, что они могут выявлять ранее неизвестные атаки. Определив, что такое "нормальное" поведение, можно обнаружить любое нарушение, вне зависимости от того, предусмотрено оно моделью потенциальных угроз или нет. В реальных системах преимущество обнаружения ранее неизвестных атак сводится на нет большим количеством ложных тревог. К тому же, системы обнаружения аномалий трудно настроить корректным образом, если им приходится работать в средах, для которых характерна значительная изменчивость.
Определения оптимального поведения для повышения уровня загрузки телекоммуникационного оборудования
При оптимизации работы телекоммуникационного оборудования возникает задача определения оптимального поведения для повышения уровня загрузки данного устройства (в заданном смысле). То есть необходимо задать правила, согласно которым будет осуществляться выбор среди предложенных вариантов различных заявок, пришедших на обслуживание. Еще одна задача, связанная с оптимизацией работы телекоммуникационного оборудования — задача динамического распределения нестраничной памяти [24]. Пусть имеются блоки памяти длины хг L, г = 1,..., М, такие, что ХІ /, где I - длина запроса на память. Проведем нормировку и будем рассматривать следующие величины (заявки) Тогда возникает задача: какой из подходящих блоков необходимо использовать для удовлетворения запроса длины I. В работе [45] предлагается следующая стратегия использования, основанная на задаче выбора наилучшего объекта. В этой стратегии мы пропускаем К(М) — 1 свободных блоков и выбираем первый подходящий из оставшихся. Здесь то есть, фактически, решается известная задача о "выборе невесты" [2]. В данной главе, заданная выше задача, будет решаться при помощи определения однопорогового правила остановки, при этом снимается ограничение на то, что все М вариантов блоков упорядочены по качеству. Для определения правила, при котором выбор блока будет лучшим среди аналогичных выборов N игроков, рассмотрим игру на правило остановки. Пусть конечные совокупности независимых одинаково распределенных случайных величин с равномерной функцией распределения на интервале [0,1]. Каждый игрок г, где і Є N, і TV, наблюдает за траекторией процесса Q1 и в любой момент может прекратить наблюдение, то есть согласиться с предложенной величиной. Случайный момент времени Tj, который будем предполагать моментом остановки, является стратегией игрока. Обозначим через функцию выигрыша в случае остановки на шаге j. При этом введем дополнительные ограничения на данную функцию: В работе [87] для случая N = 3, М — 2 предложены следующие варианты функции (р: 1. (fi(Ci ,2 ) = 2 —"Сохрани или меняй"; 2. (p2{ei\Ul)) = K?i + $)-"Конкурирующее среднее"; З- з( ,#) = % )} -"Опасный обмен". В игре побеждает тот игрок, который получил в результате остановки большее значение. Никакой информации о поведении противника игроки не имеют. Цель каждого игрока — максимизировать вероятность своего выигрыша.
Оптимальные стратегии т будем искать среди однопоро-говых стратегий Ті(а) вида где xlj — наблюдение случайной величины Я. То есть для заданной функции (р необходимо определить порог а , такой, что, если впервые выполнено условие р(х\,..., xty а , то следует остановиться на этом шаге, иначе необходимо получить следующее наблюдение хг-+1 и рассматривать функцию (р(х\,..., В работе [15] Мазаловым В. В. и Винниченко С. В. было предложено свести данную игру к задаче оптимальной остановки со специально заданной функцией выигрыша. Для определения порога а воспользуемся следующей модифика-цией метода, предложенного в работе [15]. Пусть задан некоторый порог а, тогда можно найти і — 1,..., N. Так как игроки находятся в симметричных условиях, то порог а один и тот же для различных игроков. Тогда для определения данного порога будем использовать функцию при заданном а. Если игрок 1, получив наблюдение х, решит сделать еще один шаг, то его ожидает выигрыш Тогда в состояниях из Г = {х : f(x) Pf(x)} следует останавливаться, а в состояниях из С = {х : нужно взять еще одно наблюдение. Поскольку функция f{x) монотонно возрастает, а Р}{х) не зависит от х, то порог а является единственной абсциссой пересечения графиков у = f(x) и у = Pf(x) в интервале [0,1). В современных вычислительных сетях существует два типа трафика: компьютерный и мультимедийный. Компьютерный трафик имеет ярко выраженный асинхронный и пульсирующий характер. Компьютер посылает пакеты в сеть в случайные моменты времени, по мере возникновения необходимости. При этом интенсивность посылки пакетов в сеть и их размер могут изменяться в широких пределах. Например, коэффициент пульсации трафика (отношение максимальной мгновенной интенсивности трафика к его средней интенсивности) протоколов без установления соединений может доходить до 200, а протоколов с установлением соединений — до 20. Чувствительность компьютерного трафика к потерям данных высока, так как без утраченных данных обойтись нельзя и их необходимо восстановить за счет повторной передачи [21].
Мультимедийный трафик, передающий, например, голос или изображение, характеризуется низким коэффициентом пульсации, высокой чувствительностью к задержкам передачи данных и низкой чувствительностью к потерям данных. То есть, данные типы трафика обладают диаметрально противоположными свойствами. Вследствие увеличения количества мультимедийного тра- фика в современных вычислительных сетях возникла необходимость в создании новых технологий, позволяющих проводить интегрированную передачу обоих типов трафика. Так, например, подход, реализованный в технологии ATM (Asynchronous Transfer Mode), состоит в передаче любого вида трафика ячейками, то есть пакетами, фиксированной и очень маленькой длины в 53 байта. Это позволяет добиться удовлетворительного качества пересылки трафика обоих типов. Использование ячеек также дает возможность создать высокоскоростные коммутаторы ATM. Рассмотрим принципиальную схему коммутатора ATM, причем основное внимание будет уделено "транспортной части", то есть тому, как ячейки передаются со входа коммутатора на выход при условии, что виртуальное соединение уже установлено и коммутатор "знает", на какую выходную линию передавать ячейку с данной входной линии. ATM коммутатор имеет несколько входных и несколько выходных линий, причем, как правило, их число совпадает, так как соединения являются двусторонними. Данные коммутаторы являются синхронными в том смысле, что во время одного цикла одна ячейка берется с каждой входной линии (если она, конечно, есть), проводится через внутреннюю коммутационную структуру и подается на нужную выходную линию.
Оптимальная политика выбора в урновой модели с двумя типами шаров
Пусть урна содержит т черных и р белых шаров. Каждому черному шару соответствует значение —6, а белому а, где а, Ь Є N. Обозначим данное состояние урны как (т,р). Для урновой модели выбираем с = -1 и (i = 0, то есть имеем модель случайного выбора без возвращения. Далее будем рассматривать игру, в которой перед каж дым выбором шара игрок решает: соглашаться или нет с # шаром [25, 43, 46]. При этом состояние урны ему извест- но. После принятия решения производится выбор шара из урны. Если игрок согласился с шаром, то он получает значение выбранного шара. Если же игрок отказался от шара, то он получает только информацию о цвете выбранного шара. Игра продолжается до тех пор, пока все т -\-р шаров не будут выбраны. Цель игрока — получить максимальное значение (выигрыш) в ходе описанной игры. Введем следующее обозначение где По аналогии с результатом, представленным в работах [46, 89], получаем, что А(т,р) — это математическое ожидание всего выигрыша игрока при условии, что урна первоначально находилась в состоянии (т,р), игрок соглашается с первым шаром, и его дальнейшие действия определяются оптимальной стратегией (если урна находится в состоянии (га , р ), то оптимальная стратегия игрока: соглашаться с шаром, если ар Ъ т и отказываться от шара в противном случае). N(m,p) определяется аналогично при условии, что игрок не соглашается с первым шаром. Из то есть для урны, находящейся в состоянии (т,р), оптимальной стратегией будет соглашаться с шаром, если ар Ьт, и отказываться в противном случае. В результате получаем, что V(m,p) — это математическое ожидание всего выигрыша игрока при оптимальной стратегии выбора, если известно, что урна первоначально находилась в состоянии (т,р). Данная игра является обобщением игры, рассмотренной в работе [46], где а = Ь = 1. В случае, когда значение одного черного шара равно сумме значений п Є N белых шаров с обратным знаком, верна следующая теорема. Доказательство. Исходы испытания при извлечении т + р шаров опишем последовательностью случайных величин, принимающих значение а при выборе белого шара и значение — Ь при выборе черного шара. На рисунке 12 показано множество путей, построенных по всем реализациям случайной последовательности (IV.3.5), при р = 7, т = 3, а = 1, п = 2. Точки An В имеют координаты (0,0) и (п,ар — bm) = (п,ар — апт) соответственно. Тогда на каждом таком множестве путей математическое ожидание выигрыша при оптимальной стратегии выбора равно д = V(l,n).
Данный результат следует из того, что мы имеем одинаковую вероятность получить путь любого из вышеописанных типов. При этом получаемый выигрыш для пути данного типа совпадает с выигрышем для пути этого же типа, состоящего из 1-го отрицательного звена и п положительных звеньев. Далее, для заданных тир будем исследовать множество путей, которое построено по всем реализациям случайной последовательности (IV.3.5). Если известно, что Sj = О, О j т + р, то математическое ожидание уже полученного выигрыша игрока увеличится на д = V(l, п) единиц при оптимальной стратегии выбора в момент времени т, где Ниже показано соотношение между математическим ожиданием значения, получаемого игроком при оптимальной стратегии выбора для двух урн, в случае, если количество черных шаров в первой урне равно количеству белых шаров во второй урне и условие равенства сохраняется для шаров другого цвета. Теорема IV.3.4. Если а = Ь, Ъ Є N, то для любых т,р Доказательство. Множество всех реализаций случайной последовательности для урны (р, га) может быть получено зеркальным отображением множества реализаций для урны (т,р) относительно оси ординат. При этом изменяется положение начальной и конечной точки, то есть будет меняться значение, которое игрок обязательно получит с каждой реализации при оптимальной стратегии выбора. Данное значение изменяется на величину, равную Теорема IV.3.5. Если a, b Є N для урны (т,р) и игрок действует согласно оптимальной стратегии, то последний шар с которым согласится игрок, будет белым. Доказательство. Рассмотрим промежуточное состояние урны (га ,р ), где т т, р р. Тогда при выполнении следующего соотношения игрок согласится с текущим шаром. Если же игрок согласился, и при выборе был получен черный шар, то условие выполнено, и игрок будет соглашаться с шарами до тех пор, пока не получит белый шар. По аналогии с работой [46] будем изучать асимптотику V(m,p), для этого воспользуемся следующими результатами. Теорема IV.3.6 (Интегральная теорема Муавра— Лапласа) . Пусть А — событие, которое может произойти в любом из п независимых испытаний с одной и той же вероятностью р = Р(А). Пусть ип(А) — число осуществлений события А в п испытаниях. В работах [44],[89] была впервые решена следующая задача.
Пусть урна содержит т черных и р белых шаров. Каждому черному шару соответствует значение —1, а белому 1. Изначально игроку сообщается состояние урны (т,р), при этом он может произвести от 0 до тг равновероятных выборов без возвращения, по одному в каждый момент времени. Если игрок останавливается (прекращает выбор), то он получает 1 за каждый вытащенный белый шар и —1 за каждый черный. Задача игрока состоит в выборе момента остановки так, чтобы максимизировать ожидаемое количество очков. Обозначим через V(m,p) математическое ожидание значения, получаемого игроком при оптимальной игре с урной, содержащей п = т + р шаров. Это значение вычисляется следующим образом: часть данных. Для выделения данных, которые необходимо отбросить, применяют урновые модели. Так, например, ур-новая модель, рассмотренная в данной главе может быть интерпретирована следующим образом. Белые и черные шары считаются пакетами двух различных типов. При этом пакет первого типа (белый шар) более предпочтителен для обслуживания в данный момент. Это может быть обусловлено тем, что выходная линия, на которую придет пакет второго типа, заблокирована. Степень указанной предпочтительности задается значениями а и —Ь. Тогда V(m,p) —средняя "предпочтительность" при условии оптимальной стратегии сохранения пакетов. При этом для случая, когда а = 6, b Є N и m,p — оо, можно исследовать асимптотику данной величины (теорема IV.3.8).
