WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 10 |
Ю.Ю. Громов Н.А. Земской О.Г. Иванова А.В. Лагутин В.М. Тютюнник • ИЗДАТЕЛЬСТВО ТГТУ • Министерство образования и науки Российской Федерации ТАМБОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Ю.Ю. Громов, Н.А. Земской, О.Г. Иванова, А.В. Лагутин, В.М. Тютюнник ФРАКТАЛЬНЫЙ АНАЛИЗ И ПРОЦЕССЫ В КОМПЬЮТЕРНЫХ СЕТЯХ Допущено УМО вузов по университетскому политехническому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности 230201 – «Информационные системы и технологии» Тамбов • Издательство ТГТУ • 2004 УДК 004.414.2(07) ББК 965-01я73 Ф82 Рецензенты:

Доктор технических наук, профессор Ю.Л. Муромцев Доктор физико-математических наук, профессор А.И. Булгаков Громов Ю.Ю., Земской Н.А., Иванова О.Г., Лагутин А.В., Тютюнник В.М.

Ф82 Фрактальный анализ и процессы в компьютерных сетях: Учеб. пособие. Тамбов: Изд-во Тамб. гос. техн. ун-та, 2004. 108 с.

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

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

УДК 004.414.2(07) ББК 965-01я73 ISBN 5-8265-0336-Х © Громов Ю.Ю., Земской Н.А., Иванова О.Г., Лагутин А.В, Тютюнник В.М., 2004 © Тамбовский государственный технический университет (ТГТУ), 2004 Учебное издание ГРОМОВ Юрий Юрьевич, ЗЕМСКОЙ Николай Александрович, ИВАНОВА Ольга Геннадьевна, ЛАГУТИН Андрей Владимирович, ТЮТЮННИК Вячеслав Михайлович ФРАКТАЛЬНЫЙ АНАЛИЗ И ПРОЦЕССЫ В КОМПЬЮТЕРНЫХ СЕТЯХ Учебное пособие Редактор Т.М. Глинкина Инженер по компьютерному макетированию Т.А. Сынкова Подписано к печати 18.11.Формат 60 84/16. Гарнитура Times. Бумага офсетная. Печать офсетная.

Объем: 6,28 усл. печ. л.; 6,0 уч.-изд. л.

Тираж 100 экз. С. 799М Издательско-полиграфический центр Тамбовского государственного технического университета 392000, Тамбов, ул. Советская, 106, к. ПРЕДИСЛОВИЕ В связи с тенденциями интеграции различных коммуникационных приложений на основе универсальной сетевой инфраструктуры передачи данных актуальными задачами становятся разработка методов анализа и синтеза информационно-управляющих систем, построенных с использованием современных компьютерных технологий. Предлагаемое пособие посвящено одному из важных аспектов развития таких методов: исследованию процессов в компьютерных сетях, их идентификации и формированию на базе полученного математического описания моделей этих процессов управления сетевым трафиком. Сложность решения такой задачи состоит в том, что сетевые процессы в современных компьютерных сетях имеют случайных характер. Анализ результатов многочисленных экспериментов по исследованию сетевых процессов показывает, что переход к технологии пакетной коммутации и создание интегрированных информационных приложений сопровождается появлением сложных явлений, исследование которых может быть проведено в рамках теоретиковероятностных подходов. Быстрый научно-технический прогресс в области создания и внедрения информационно-управляющих систем, а также необходимость эффективной и надежной их работы стимулировал интерес к исследованиям теоретических проблем статистического моделирования и управления сетевым трафиком. К сожалению, большинство публикаций на эти темы носит узкоспециальный характер, а отсутствие учебно-методических работ существенно ограничивает круг специалистов, принимающих участие в обсуждении данной актуальной научно-технической проблемы.

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

ВВЕДЕНИЕ Компьютеры и компьютерные сети являются неотъемлемыми компонентами современных технологий управления и производства.

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



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

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

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

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

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

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

1 ФРАКТАЛЬНАЯ РАЗМЕРНОСТЬ 1.1 Береговая линия Норвегии Сколь велика длина береговой линии Норвегии Взгляните на рис. 1.1. В масштабе карты хорошо видны глубокие фиорды на западном побережье. Более мелкие детали очертаний побережья к северо-востоку от южной оконечности различимы хуже, но на картах береговая линия выглядит так же, как западное побережье на рис. 1.1. Идя под парусом, вы то и дело встречаете скалы, острова, бухты, обрывы и узкости, которые похожи друг на друга, даже если они не обозначены на подробных картах. Прежде чем ответить на вопрос, с которого начинается эта глава, необходимо решить, стоит ли включать в береговую линию острова. Как быть с реками В каком месте фиорд перестает быть фиордом и где именно он переходит в реку Ответить на этот вопрос иногда легко, иногда не очень. Но даже если мы сумеем удовлетворительно ответить на все вопросы такого рода, одна трудность все же остается. Дело в том, что можно придать циркулю раствор, соответствующий км, и сосчитать число шагов N(), которые понадобились бы, чтобы пройти по карте из конца в конец все побережье. В спешке можно было бы выбрать раствор циркуля настолько большим, что не понадобилось бы заботиться даже о самых глубоких фиордах, и принять за длину береговой линии величину L = N().

Можно было бы выбрать меньший раствор циркуля. Тогда в длину береговой линии вошли бы и наиболее глубокие фиорды, но юго-восточное побережье по-прежнему было бы пройдено за несколько шагов. Для еще более точного подсчета длины береговой линии понадобились бы такие карты, которыми пользуются соседи при решении вопросов о том, где должен проходить забор между земельными участками, или о том, как далеко по реке простираются границы рыбной ловли. Ясно, что при решении такого рода вопросов уточнения можно вносить бесконечно. Всякий раз, когда будет увеличиваться разрешающая способность, длина береговой линии будет разрастаться. Кроме того, при использовании циркуля могут возникнуть проблемы с островами и реками. Альтернативный способ измерения длины береговой линии состоит в том, чтобы покрыть карту сеткой, как показано в верхней части рис. 1.1. Пусть квадратные ячейки сетки имеют размеры. Число N() таких ячеек, необходимых, чтобы покрыть береговую линию на карте, приближенно равно числу шагов, за которое можно обойти по карте береговую линию циркулем с раствором. Уменьшение приводит к увеличению числа ячеек, необходимых для покрытия береговой линии. Если бы береговая линия Норвегии имела вполне определенную длину LN, то Рис. 1.1 Побережье южной части Норвегии. Береговая линия перечерчена из географического атласа и представлена в цифровом виде с помощью растра, состоящего примерно из 1800 1200 ячеек.

Изображенная вверху квадратная решетка имеет шаг ~ 50 км можно было бы ожидать, что число шагов циркуля или число квадратных ячеек N(), необходимых для покрытия береговой линии на карте, будет обратно пропорционально, а величина L() = N() при уменьшении будет стремиться к постоянной LN.

Как видно из рис. 1.2, при уменьшении длины шага измеренная длина возрастает. График на этом рисунке выполнен в дважды логарифмическом масштабе и показывает, что при уменьшении измеренная длина береговой линии отнюдь не стремится к постоянному значению. Наоборот, измеренная длина прекрасно описывается приближенной формулой L() = A1 – D. (1.1) Для обычной кривой можно было бы ожидать, что A = LN (по крайней мере при достаточно малых ) и показатель D равен единице. Но для береговой линии Норвегии, как видно из графика, D 1,52. Береговая линия – фрактал с фрактальной размерностью D.

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

Угловой коэффициент этих прямых равен 1 – D, где D – фрактальная размерность береговой линии (или сухопутной границы). Береговая линия Великобритании имеет D ~ 1,3. Мандельброт приводит также данные для окружности и находит, как и следовало ожидать, что Dокр = 1 [4].





Рис. 1.2 Измеренная длина береговой линии, изображенной на рис. 1.1, как функция шага (км) – длины стороны квадратных ячеек, образующих покрытие береговой линии на карте. Прямая на графике в дважды логарифмическом масштабе соответствует зависимости L() = A1 – D, где D 1,Рис. 1.3 Длина береговых линий как функция выбранного шага (км) 1.2 Парадокс Шварца с площадью боковой поверхности цилиндра Измерение площади – процедура, не всегда легко осуществимая на практике. Рассмотрим боковую поверхность цилиндра (радиусом R и высотой Н), изображенную на рис. 1.4. Ее площадь равна А = 2RH. Но если мы попытаемся измерить площадь боковой поверхности этого цилиндра на практике с помощью линеек, то придется тем или иным образом триангулировать поверхность, например так, как это показано на рис. 1.4. Разделив поверхность на m полос и N секторов, как показано на этом рисунке, мы получим оценку площади боковой поверхности цилиндра в виде суммы A площадей всех малых треугольников. Разбивая поверхность на все более мелкие треугольники, т.е. устремляя N и m, мы ожидаем, что и A A. Но подобный прогноз верен не всегда. Площадь всех треугольников можно записать в виде 2 1+ R 4m2 2n A = RH sin cos 1+ sin n 2n 2n 2n H 2n n RH 1+ (R / H )2(2m / n2) 1+.

n (1.2) Рис. 1.4 Боковая поверхность цилиндра радиусом R и высотой H равна 2RH. Поверхность аппроксимируется с помощью триангуляции, как показано на рисунке Первые слагаемые здесь соответствуют треугольникам того типа, который на рис. 1.4 обозначен a1.

Вторые, те, что с квадратным корнем, соответствуют треугольникам, обозначенным на рис. 1.4 через a2.

Нетрудно видеть, что если m / N 2 0 при m и N, то суммарная площадь треугольников стремится к ожидаемому пределу. Но если мы воспользуемся триангуляцией, для которой m = N 2, то обнаружим, что A > A и что в действительности А может принимать сколь угодно большие значения. Выбирая m = N, мы получаем A N – 2, при > 2. Следовательно, когда отдельные треугольники становятся все меньше и меньше, суммарная площадь треугольников неограниченно возрастает. Вместо того, чтобы улучшаться, аппроксимация при уменьшении величины треугольников ухудшается. К аналогичным проблемам приводят и многие другие способы триангуляции. Возникающая ситуация известна под названием парадокса Шварца с площадью боковой поверхности цилиндра. Нетрудно понять, в чем здесь дело. При увеличении отношения m / N 2 аппроксимирующая поверхность, состоящая из треугольников, все сильнее и сильнее складывается в гармошку, и в пределе треугольники типа а2 практически перпендикулярны поверхности цилиндра.

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

1.3 Фрактальная размерность Мандельброт предложил следующее пробное определение фрактала.

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

Это определение в свою очередь требует определений терминов множество, размерность Хаусдорфа – Безиковича (D) и топологическая размерность (Dт), которая всегда равна целому числу. Позже Мандельброт сузил свое предварительное определение, предложив заменить его следующим.

Фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому.

Строгого и полного определения фракталов пока не существует. Дело в том, что первое определение при всей правильности и точности слишком ограничительно. Оно исключает многие фракталы, встречающиеся в физике. Второе определение содержит существенный отличительный признак, подчеркиваемый в данном пособии и наблюдаемый в эксперименте [4, 5]: фрактал выглядит одинаково, в каком бы масштабе его ни наблюдать. Взять хотя бы некоторые прекрасные кучевые облака. Они состоят из огромных «горбов», на которых возвышаются «горбы» поменьше, на тех – «горбы» еще меньше и т.д. вплоть до самого малого масштаба, который вы в состоянии разрешить. На самом деле, располагая только внешним видом облаков и не используя никакой дополнительной информации, размер облаков оценить невозможно.

Фракталы, о которых пойдет речь далее, можно рассматривать как множества точек, вложенные в пространство. Например, множество точек, образующих линию в обычном евклидовом пространстве, имеет топологическую размерность Dт = 1 и размерность Хаусдорфа – Безиковича D = 1. Евклидова размерность пространства равна Е = 3. Так как для линии D = Dт линия, согласно определению Мандельброта, не фрактальна, что подтверждает разумность определения. Аналогично множество точек, образующих поверхность в пространстве с Е = 3, имеет топологическую размерность Dт = 2 и D = 2. Мы видим, что и обычная поверхность не фрактальна независимо от того, насколько она сложна. Наконец, шар, или полная сфера, имеет D = 3 и Dт = 3. Эти примеры позволяют определить некоторые из рассматриваемых нами типов множеств.

Pages:     || 2 | 3 | 4 | 5 |   ...   | 10 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.