В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 58
Текст из файла (страница 58)
Самоподобие является в действительности одной из решающих симметрий, формируюших нашу вселенную и оказывающих влияние на наши попытки понять сею Явление, обладаюшее свойством самоподобия, выглядит одинаково или одинаково ведет себя при его рассмотрении с разной степенью «увеличенияэ или в разном масштабе. Масштабируемой величиной может быть пространство (длина„ ширина) или время. В этой главе нас будут интересовать временные последовательности и стохастические процессы, демонстрирующие свойство самоподобия во времени.
Обсуждаемый в данном разделе шабэон проще увидеть на рисунке. На рис. 9.1, а показанапоследовательностьпоступленийкадроввзависимостиотвремени. Каждая вертикальная линия соответствует одному кадру. Ширина линии соответствует 4 мс, то есть времени, необходимому для приема 1гадра целиком, от первого бита до последнего. На рис. 9.1, б показаны данные, сгруппированные в четыре кластера.
Высота и ширина вертикальных линий в этом случае пропорциональна масштабу группирования. На рисунке легко видеть, что один и тот же шаблон (прибытие, короткий интервал, прибытие, длинный интервал, прибытие, короткий интервал, прибытие) можно видеть при разной степени рж1решения. Данный пример получен из множества знаменитого конструктора Кантора (Сэпгог). Его можно найти практически в любой книге, посвященной теме хаоса, фракталов и нелинейной динамики.
На рис. 9.2 показано устройство множества Кантора, подчиняю1цегося следующим правилам: 1. Начните с закрытого интервала 10, 11, представленного линейным сегментом. 2. Удалите открытую среднюю треть линии, то есть исключая концы удаляемого интервала. 3. Для каждого следующего ша1э удалите среднюю треть линий, оставшуюся после предыдущего шага. 262 Глава 9. Самоподобный график и и И ° ° И 11 !1 11 11 !!!! !!!! !!!! !!!! ИИ И ° ° И !! 11 !! !! !!!! !!! !!!! !!!! 1йг :]у Рис. 9.2. Множество Кантора для пяти уровней рекурсии По существу, это рекурсивный процесс, который точнее можно определить следующим образом. Пусть 5; представляет множество Кантора после г уровней рекурсии.
Тогда 5е = [О, Ц; К = [О, 1/3] г.г [2/3, Ц; эт = [О, 1/9] ш [2/9, 1/3] н [2/3, 7/9] чз [8/9, Ц. Если мы будем рассматривать линию Кантора как временную шкалу, тогда на каждом последующелг шаге масштаб временной шкалы увеличивается втрое. Обратите внимание на то, что на каждом шаге левая (и праная) часть множества является точной копией полного множества на предыдущем шаге.
Канторово множество обладает двумя свойствами, наблюдаемыми во всех явлениях самоподобия. + Оно обладает структурой, обнаруживаемой при любом сколь угодно малом масштабе. Если многократно увеличивать часть множества, мы будем продолжать видеть сложный узор точек, разделенных интервалами разного размера. Подобно замысловатому шпионскому детективу со сложными взаимосвязями, этот процесс кажется бесконечным.
Это в корне отличается от обычной непрерывной кривой, которая при увеличении становится все более и более гладкой. + Структура повторяется. Сачоподобная структура содержит уменьшенные копии самой себя на всех уровнях масштабирования. Например, на каждом шаге левая (и правая) часть канторова множества является точной копией полного множества на предыдущем шаге. Эти свойства не могут выполняться бесконечно для реальных объектов. При каком-то уровне разрешения структура и подобие разрушаются. Но многие явления проявляют свойство самомподобия на большом количестве уровней разрешения. 9.2. Саыоподобный трафикданных 263 Хотя наш пример является слишком простым и надуманным, изучая его, мы можем лучше понять некоторые особенности самоподобного трафика. Возможно, наиболее замечательной особенностью самоподобного трафика в контексте производительности сетей является устойчивость кластеризации. В пуассоновском графике кластеризация наблюдается в краткосрочном масштабе, по сглаживается в долгосрочном'.
Мы можем спроектировать систему из серверов и очередей с буферами в расчете на подобное долгосрочное сглаживание. В результате пам будет достаточно буферов умеренного размера, Очередь может образоваться в краткосрочной перспективе, но за долгий период времени буферы очистятся. Однако если неравномерное поведение трафика само по себе неравномерно — то есть кластеры кластеризуются, — тогда могут образовываться очереди большей длины, чем можно ожидать от пуассоновского потока. В результате оказывается, что традиционный аналиа очередей, в основе которого лежит предположение о пуассоновском потоке, не может точно предсказывать производительность системы н условиях самоподобного трафика. Мы увидим, что тому есть подтверждения. Я.2. Самоподобный трафик данных Описанный в разделе 9.1 тип самоподобия может быть назван точным самоподобием: заданный шаблон точно воспроизнодится при разном разрешении.
Это точное самоподобие может быть пост1юено для детерминированных врелгепных последовательностей. Однако трафик данных лучше всего рассматривать как стохастический процесс, поэтому мы можем пзворить лишь о статистическом самоподобииз Здесь может быть полезна аналогия. Детерминированный периодический сигнал характеризуется неизменностью относительно времени. Сигнал является подобным самому себе, отстоягцему на целое число периодов. Например, для детерминированной периодической функции я(Г) с периодом Т можно написать: К(г) = я(г+ а7), а = 0„+1, +2 „, Для стационарного стохастического процесса, напротив, инвариантом относительно времени являнпся статистические характеристики процесса.
Среднее значение не зависит от времени, а функция автокорреляции зависит только от разности времен, Детерминированный самоподобный сигнал инвариантен относительно изменений масштаба. Для стохастического процесса мы можем сказать, что статистические характеристики процесса не изменяются при изменении шкалы времени. Среднее поведение процесса на коротком промежутке времени не отличается от ' То очнее, кластеризация происхопит на временной шкале, определяеьюй средним интервалом между наступлениями пуассоновских собьпий.
термин кршлкосречяыя (аьоа сепв) является относительным. ' Исключение представляет собой непрерывный пшик блоков данных фиксированного размера, например поток ячеек АТМ, переносящих несжатое вилеоизображение с постоянной скоростью передачи ячеек. Наиболее распространенным является случай, в ко~орам ячейки или пакеты передастся с некоей средней сКоростыо, но сушествует некоторая неравномерность вокруг атого средиего значения. 264 Глава 9. Самоподобный график 20 + дисперсия: Ъ'зг[х(аг)] ~и[х(г)1= ' „, и -20 0 -20 300 -.. 1000 0 300 -.
1000 + автокорреляция 10 10 220 -б 230 220 223 б 230 поведения за долгий период времени. Подобное недетерминированное самоподобие часто встречается как в естественных, так и в искусственных явлениях Его можно наблюдать в природных ландшафтах, в распределениях землетрясений, в океанских волнах, в турбулентном потоке, во флуктуациях фондовых рыцков в повторяющихся ошибках и графиках данных каналов связи. На рис. 9.3, и показан пример самоподобного стохастнческого процесса. Обрати те внимание на то, что функция времени не точно повторяется при разном вреьгеп ном разрешении, но ее внешний вид при различных временных масштабах похож Сравните это с графиком на рис. 9.3, б, изображающим типичный стационарный случайный процесс.
В этом случае мы видим, что при большем увеличении функция изменяется, становясь более прерывистой и менее регулярной. Прн переход~ к более длительным интервалам времени сигнал, напротив, становится более регулярным и содержит меньше флуктуаций. — 10 2ЙГ-. 300 200: 2ЯГ -- 300 риа. 9.3.
Сравнение самападабиага и иесзмападабиага стахастических пРоцессов [239] В данном разделе будут приведены некоторые определения самоподобных стохастических процессов. В следующем разделе мы прокомментируем примеры. встречающиеся в литературе, и обсудим причины этих явлений. Самоподобные стохастические процессы определяются в литературе по-разному. В данном разделе рассматриваются некоторые иэ наиболее важных подходов.
Возможно, проще всего понять эту концепцию, рассмотрев непрерывные во времени стохастические процессы, что мы сначала и сделаем. Затем мы перейдем к 9.2. Самоподобный график данных 266 дискретным во времени и стохастическим процессам, более подходящим к нашей теме обсуждения'. Определение непрерывного во времени процессе Общее определение самопод ние самоподобного стохастического процесса (например, см. [239]) основано на прямом ма масштабировании непрерывной переменной времени. Стохастическии процесс х( ) (г) является статистически самоподобиым с параметром Н ,5 < Н< 1), если для любого вещественного значения а > О процесс а дх(аг) об- (Π— — ) 1.'то падает теми же статист ° тистическими характеристиками, что и сам процесс х( ).
Э с утвер жденне можно выразить тремя следующими условиями: + среднее: Е[х(г)] = Е[х(аг)] Вк(ай оз) В (Г з) зл Параметр Н, называемый парамелгром Херсгла (Нпгэ1 рагатетег), или парамеглром сазгоподобия (зе!1-з[пп1аг1су рагагпетег), представляет собой ключевую меру самоподобия. Точнее. Н представляет собой меру устойчивости статистического явления, или меру длительности долгосрочной зависимости т с охастического процесса. Значение Н = 0,5 указывает на отсутствие долгосрочной зависимости. Чем ближе значение Н к 1, тем выше степень устончивостн долгосро чной зависимости'. Процесс броуновского движения Процессом, удовлетворяющим нашему определению самоподоб опо обия, является процесс броуновского движения (определенный в разделе 7.3). Процесс броуновского движения В(г) является самоподобным с параметром Н=- 1/2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
