В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 64
Текст из файла (страница 64)
читатель, интересуюпгиася паиным вопросом, может найти хора игсе абсужление формулировок лгккрстг<аго времени в [371 и 127 5!. 2аб Глава 9. Свмоподобный график 9,6. Параметр Херста 287 Оценка параметра Херста Предположим, что наблюлаемая временная последовательность взята из самон моподобного стохастического процесса с парал1етром Ни что выбрана конкретная „- ая ч орл~а процесса, например процесс дробного броуновского движения.
Тогда спект ральная плотность выбранного процесса может быть выражена как 5(га, Н), л где форма плотности известна, но параметр Н неизвестен. В этом случае можно по~ 1о показать, что параметр Н можно оценить, если найти такое значение Н, которое ми ое минимизирует следующее выражение: ~ Х,(ю) „5(га, Н) Этот метод известен как оценочная формула Уиттла (%'ЫГНе).
Подробно она обсуждается в 1241 Если длина последовательности (хя) равна Ф, тогда описанный выше интеграл можно заменить дискретным суммированием по частота тотам щ = 2я/Н, Ля/Ж, ..., 2я. Преимущество такого подхода заключается в том, что он позволяет получить не только оценку параметра Н, но также еше и выборочную дисперсию, что, в свою очередь, позволяет вычислить величины доверительных интервалов. Это возможно, так как оценочная формула является асимптотически нормальной.
Выборочная дисперсия может быть получена при помощи следукь щей формулы: тмл ~-~ [1(~'чл ~)1 В отличие от графика зависимости дисперсии от времени и графика Л,~К использующихся для проверки временных последовательностей на самоподобие и получения грубой оценки параметра Н, оценочная формула Уиттла предполагает, что временная последовательность представляет собой самоподобный процесс опрелеленного вида, и позволяет оценить параметр Н в доверительном интервале. 9.6.
Параметр Херста Нап т ротяжении всей главы мы использовали параметр самоподобия, или параметР Хе т рс а, в качестве удобной единицы измерения самоподобия стохасгического процесса. Этот параметр был назван по имени Х. Е. Херста (Н. Е. Нцгэг), посвятив- лего свою жизнь изучению Нила и других рек, а также проблемам хранения воды '11910 С е и ь Среди прочих вопросов Херст обнаружил, что уровень волы в Ниле за 300-летний ~ий период проявляет признаки самоподобия. Этот раздел знакомит с не~арией создания параметра Н.
Г идролог по образованию, Херст исследовал долгосрочные характеристики штоков воды различных рек. Он заметил, что некоторые реки (например, Рейн) обладают относительно мягкими флуктуациями. Другие реки, такие как Нил, я вляют собой совершенно иную картину. Херст замерил, что долгосрочные и краткосрочные характеристики сходны. В краткосрочной перспективе, как и следовало ожидать, уровень воды в Ниле изменялся из года в год. Также можно было ожидать, что эти флуктуации будут иметь тенденцию к усреднению, так что за более олгнй период уровень Нила должен был оставаться в довольно узком диапазоне с хорошими и плохими периодами, часто сменяющими друг друга.
Однако в действительности Нил ведет себя не так. В долгосрочной перспективе длинные периоды засухи следуют за долгими периодами высокой воды, в которые наводнения происходили чуть ли не каждый год. Мандельброт назвал это явление эффекяюж Иосифа ()озерЬ ересь), в соответствии с отрывком из Библии (Книга Бытия л1;29-30): «И сказал Иосиф фараону — будут семь лет изобилия по всей земле Епгпетской, и будут после них семь голодных леть, Возможно, зго не лучший термин, поскольку долгосрочное поведение Нила не проявляет такой регулярности.
В действительности не наблюдается какой-либо устойчивой цикличности в любом временном масштабе. Херст занялся проблемой проектирования идеального резервуара для регулирования потока Нила па основании имеющейся записи наблюлений за уровнем реки. Идеальный резервуар должен обеспечивать постоянный поток, равный среднему входному потоку, который никогда не переполняется и никогда не иссякает. Для решения данной задачи требуется получить данные об изменчивости потока воды. Предположим. что уровень воды измеряется раз в год. Определим следующие переменные: + Х.
— входной поток за год Х (1 < 1 < Ю); это изучаемые временные последовательности; + М(Н) — постоянный ежеголный исходящий поток, основанный на наблюдениях в течение Ждет; + Х, — уровень воды в резервуаре к концу года 1(1 .Х < гт); + Ж вЂ” число лет наблюдения. Эти величины иллюстрирует рис. 9,8. Основываясь на записи Ждет, мы хотели бы получить значения минимального и максимального уровней воды в резервуаре (Х.„и(Й), А,„(Н)), а также диапазон Н(Н) = А,()т) — Х.„„.(Н). Рис. ВКЬ Иллюстрация параметровдляанализахерста 288 Глава 9. Самоподобный график 9 8 ЗаДаниЯ 288 1 М(ЛУ) = — Х Х,ч ЛУ, ! 1., = ~Х, -)М(Н); у=! ус(Лу) = шах Е. — пип 1., иусн у мусн у' Диапазон(Х,ЛУ) = шах Х вЂ” шупХ .
!5ухн у !суя,' 9.8. Задания Учитывая данные о входном потоке за интересующий нас период, требую вц ся величины нетрудно вычислить: Таким образом, М(ЛУ) представляет собой средний входной поток за Нлет г. у суммарный входной поток за первые) лет минус суммарный выходной поток о кзате же годы, а Л(Н) — это разница между максимальным и минимальным значения ениями Ц за эти годы. Очевидно, диапазон зависит от интервала времени ЛУ и предстааляет собой неубывающую функцию Лу.
Обратите внимание на то, что параметр )1 не равен диапазону временной последоиательностп Х„которая имеет следующий вид; Вместо этого мы можем рассматривать 1у как накапливаемую величину, на которую временная последоиательность отклоняется от среднего значения за время 7'. Таким образом, Л' представляет собой величину, которая, в определенном смысле, лучше характеризует изменчивость случайной переменной Х. Херст исследовал ряд явлений н разработал нормализованную безразмерную величину ус/5, характеризующую изменчивость, где 5 представляет собой выборочное среднее: В определенном смысле как Л, так и 5 измеряют изменчивость данных. Величинаа Л линейно заэ исит от данных.
тогда как 5 учитывает квадраты исходных значении. Херст называл это отношение маснапаби7уоааннььн диапазоном (гезса!ес] гаойе). Херст ооиаружил, что для многих природных явлений, включая расход волы э реках, отложения осадочных пород и годовые кольца деревьев, отношение у?/5 каус функция Лу хорошо описывается следующей эмпирической формулой для больцуих значений Ф: НуУ5- (ЛУУ2)н пРи Н) ОД. Несложно убедиться а этом визуально, если построить график заэисимосту! ЛУ5от Лу н логарифмическом масштабе. Херст обнаружил, что для многих наборов данных точки ложатся на прямую линию; наклон этой линии представляет собой параметр Н из предыдущей с]юрмулы.
Можно показать, что для любого краткосрочного процесса отношение Н/5 ста ноэнтся асимптотически пропорциональным Лап, то есть Н= 0,5. Однако Херст нашел мно л множество явлений со значениями Н, аарьирующимися э диапазоне от 0,7 до, . оль 0,9. Болыпие значения параметра Н предполагакп болыпую степень изменчиэости данных. 9.7. Рекомендуемые литература и веб-сайты Теме самоподобия, относящейся одновременно к теории фракталов и теории хаоса, посвящено много книг. [198] представляет собой интересную книгу, посвященную ю самоподобию и его проявлениям во фракталах, хаосе и других областях. Объем литературы по самоподобному графику данных стремительно растет, и здесь упоминалось только несколько ключеаых статей.
[144] является однои нз наиболее значимых статей по теме сетей за последнее десятилетие, с которой начался новый метод исследования производительности графика. В [176] содержится убедительный анализ самоподобного графика на основе протокола ТОР, а также ряд полезных приложений, посвященных лежащим э основе математическим понятиям, представляющим общий интерес при моделировании самоподобного графика. В центре внимания книги [77] находится тема влияния самоподобия на производительность очередей, а также а ней содержится подробный обзор методоэ моделирования.
В [104] также рассматривается вопрос производительности очередей и обсуждаются методы управления самоподобным графиком. [2] предстааляет собой важную подборку глав различных авторов, обеспечивающую детальное обозрение данной темы. [24] является еще одной подборкой глав различных авторов, посвященных вопросам моделирования и аналиаа данных. В [82] содержится детальный анализ параметра Херста и отно!я ения Л/5, а также обсуждение процесса дробного броуноэского движения. В [78] также предоставляется превосходное освещение процесса дробного броуновского движения. В [169] обсуждается приложение дробного броуновского движения к анализу графика.
Рекомендуемым эеб-сайтом является Мос[е11пя о/5е11'-5упуу1аг ТуаОус. Это сайт исследовательского проекта а области самоподобия. 1. Чему равна длина множества Кантора после Лс итераций? 2. Покажите, что множество Кантора состоит из всех точек э интервале [О, 1], не имеющих единиц э их троичном представлении. 3. В каком смысле представленная ниже последовательность является само- подобной? ...1/8, 1/4, 1/2, 1, 2, 4. В... 290 Глава 9. Самоподобный график 4. Покажите, что если случайная переменная Х подчиняется распределеншо Парето с парамеграмн л и а, тогда случайная переменная У=!п(Х гй) подчи- ~[ няется зкспоненцнзльнолгу распределению с параметром а, 5. Непрерывное во времени определение самоподобного стохастического процесса, описанное в разделе 9.2, включает равенства, связывающие Е[х(г)) с Е[х(ат) [ и Ъгаг[х(Г)1 с Ътаг[х(ат)1. а) покажите уравнения для Н = 1 и Н = 0,5 и прокомлгентируйте результаты; б) перепишите уравнения, связывающие Е[х(Г)1 с Е[х(аг)1 и Ъгаг[х(Г)[ с Ъгаг[х(ат) [; в) покажите уравнения из задания б для Н = 1 и Н = 0,5 и прокоммекгируйте результаты.
Часть!У Перегрузка и управление трафи ком Главная, а в действительности и единственная причина перехода на более быстрые сети заключается в том, чтобы поддерживать возросший график: больше конечных систем и более высокие скорости передачи данных для приложений оконечных систем. К сожалению, взаимодействие между протоколами в оконечных системах и механизмами управления графиком в сетях и маршрутизаторах могут привести к существенной недогрузке высокоскоростной сети. Например, в [56) сообщается об измерении РТР-графика с удивительнымн результатами.
При передаче по протоколу РТР 4,4-мегабайтного файла данных между двумя хостами, присоединенными к одной и той же 10-мегабитной сети Е1Ьетпе1, наблюдается средняя пропускная способность в 1,313 Мбит/с. Прн использовании того же самого программного обеспечения и компьютеров для передачи этого файла по сети АТМ со скоростью передачи данных 100 Мбит/с была замерена средняя пропускная способность всего лишь в 0,366 Мбит/с, Таким образом, скорость передачи данных в сети увеличивается в 10 раз, а пропускная способность падает почти в 4 раза! Ключ к пониманию данной проблемы заключается в механизмах управления графиком, используемых протоколами транспортного уровня оконечных систем, как, например, ТСР.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
