История моделей сетевого трафика

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

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

«Теория телетрафика — это применение математики к измерению, моделированию и управлению трафиком в телекоммуникационных сетях . Целью моделирования дорожного движения является поиск случайных процессов, отражающих поведение дорожного движения. Работая в Копенгагенской телефонной компании в 1910-х годах, А. К. Эрланг охарактеризовал телефонный трафик на уровне вызовов с помощью определенных распределений вероятностей поступления новых вызовов и времени их удержания. Эрланг применил модели трафика для оценки мощности телефонного коммутатора, необходимой для достижения заданной вероятности блокировки вызова. Формулы блокировки Эрланга имели огромный практический интерес для операторов связи, поскольку телефонные средства (коммутация и передача) требовали значительных инвестиций. В течение нескольких десятилетий работа Эрланга стимулировала использование теории массового обслуживания и вообще применение вероятности для проектирования коммутируемых телефонных сетей общего пользования . Теория телетрафика для пакетных сетей за последние десятилетия добилась значительного прогресса. Значительные успехи были достигнуты в подходах дальнодействующей зависимости, вейвлет- и мультифрактальном подходах. В то же время моделирование трафика по-прежнему сталкивается с проблемами из-за развития сетевых технологий и новых мультимедийных приложений. Например, беспроводные технологии обеспечивают большую мобильность пользователей. Мобильность должна быть дополнительным фактором при моделировании трафика в беспроводных сетях. Моделирование дорожного движения — это непрерывный процесс, не имеющий реального конца. Модели дорожного движения представляют собой наше лучшее понимание поведения дорожного движения на данный момент, но со временем наше понимание будет меняться и расширяться».

Использование моделей сетевого трафика

Измерения полезны и необходимы для проверки фактической производительности сети . Однако измерения не обладают тем уровнем абстракции, который делает модели трафика полезными. Модели трафика можно использовать для решения гипотетических проблем, тогда как измерения трафика отражают только текущую реальность. С вероятностной точки зрения трассировка трафика — это реализация случайного процесса , тогда как модель трафика — это случайный процесс. Таким образом, модели дорожного движения обладают универсальностью. Трассировка трафика дает представление о конкретном источнике трафика, а модель трафика дает представление обо всех источниках трафика этого типа. Модели дорожного движения имеют три основных применения. Одним из важных применений моделей трафика является правильное определение сетевых ресурсов для достижения целевого уровня QoS . Ранее упоминалось, что Erlang разработал модели голосовых вызовов для оценки мощности телефонного коммутатора и достижения целевой вероятности блокировки вызова. Аналогичным образом, модели пакетного трафика необходимы для оценки пропускной способности и ресурсов буфера, чтобы обеспечить приемлемые задержки пакетов и вероятность потери пакетов . Знания о средней скорости трафика недостаточно. известно Из теории массового обслуживания , что длина очереди увеличивается с изменением трафика. Следовательно, понимание пульсаций или изменчивости трафика необходимо для определения достаточных размеров буферов в узлах и пропускной способности каналов. Вторым важным применением моделей трафика является проверка производительности сети при определенных мерах управления трафиком. Например, при наличии алгоритма планирования пакетов можно было бы оценить производительность сети в зависимости от различных сценариев трафика. Другой пример: популярной областью исследований являются новые улучшения алгоритма предотвращения перегрузки TCP. Крайне важно, чтобы любой алгоритм был стабильным и позволял нескольким хостам справедливо распределять полосу пропускания, сохраняя при этом высокую пропускную способность. Эффективная оценка стабильности, справедливости и производительности новых алгоритмов была бы невозможна без реалистичных моделей источников. Третьим важным применением моделей дорожного движения является контроль доступа. В частности, сети, ориентированные на соединение, такие как ATM, зависят от контроля доступа, который блокирует новые соединения для поддержания гарантий QOS. Простая стратегия допуска может быть основана на пиковой скорости нового соединения; новое соединение допускается, если доступная пропускная способность превышает пиковую скорость. Однако эта стратегия была бы слишком консервативной, поскольку для соединения с переменной скоростью передачи данных может потребоваться значительно меньшая полоса пропускания, чем его пиковая скорость. Более сложная стратегия допуска основана на эффективной пропускной способности. Поведение исходного трафика преобразуется в эффективную полосу пропускания между пиковой скоростью и средней скоростью, которая представляет собой конкретный объем полосы пропускания, необходимый для удовлетворения заданного ограничения QoS. Эффективная полоса пропускания зависит от изменчивости источника.

Этапы моделей сетевого трафика

Моделирование трафика состоит из трех этапов:

• (i) выбор одной или нескольких моделей, которые могут обеспечить хорошее описание типа трафика
• (ii) оценка параметров выбранных моделей
• (iii) статистическое тестирование для выбора одной из рассматриваемых моделей и анализ ее пригодности для описания анализируемого типа трафика.

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

Параметр моделей сетевого трафика

В последние годы было обнаружено несколько типов поведения трафика, которые могут оказать существенное влияние на производительность сети: дальнодействующая зависимость, самоподобие и, в последнее время, мультифрактальность. Существует два основных параметра, генерируемых моделями сетевого трафика: распределение длин пакетов и распределение пакетов между поступлениями. Другие параметры, такие как маршруты, распределение пунктов назначения и т. д., имеют меньшее значение. Моделирование, в котором используются трассировки, созданные моделями сетевого трафика, обычно исследуют один узел в сети, например маршрутизатор или коммутатор; Факторы, которые зависят от конкретных сетевых топологий или информации о маршрутизации, специфичны для этих топологий и моделей. Проблема распределения размеров пакетов сегодня достаточно хорошо изучена. Существующие модели размеров пакетов оказались обоснованными и простыми. Большинство моделей размера пакетов не учитывают проблему порядка размеров пакетов. Например, за дейтаграммой TCP в одном направлении, скорее всего, последует крошечный ACK в другом направлении примерно через половину времени приема-передачи (RTT). Проблема распределения пакетов между поступлениями гораздо сложнее. Понимание сетевого трафика за прошедшие годы значительно изменилось, что привело к ряду изменений в моделях сетевого трафика.

Самоподобные модели трафика

Одним из первых возражений против самоподобных моделей дорожного движения была сложность математического анализа. Существующие самоподобные модели нельзя было использовать в традиционных моделях массового обслуживания. Это ограничение было быстро преодолено и были построены работоспособные модели. Как только базовые самоподобные модели стали возможными, сообщество моделирования дорожного движения углубилось в «детальные» проблемы. Алгоритм управления перегрузкой TCP усложнил задачу моделирования трафика, поэтому необходимо было найти решения. Оценка параметров самоподобных моделей всегда была сложной задачей, и недавние исследования посвящены способам моделирования сетевого трафика без полного его понимания.

Илкка Норрос

• Дробное броуновское движение :

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

• КАЧАТЬ:

Все модели самоподобного трафика страдают одним существенным недостатком: оценка параметров самоподобия на основе реального сетевого трафика требует огромных объемов данных и требует расширенных вычислений. Самый современный метод — вейвлет-анализ с несколькими разрешениями — более эффективен, но все же очень дорог. Это нежелательно в модели трафика. SWING использует удивительно простую модель анализа и генерации сетевого трафика. Модель исследует характеристики пользователей, обмены запросами и ответами (RRE), соединения, отдельные пакеты и сеть в целом. Никаких попыток проанализировать характеристики самоподобия не предпринимается; любое самоподобие в генерируемом трафике естественным образом возникает в результате агрегирования множества источников ВКЛ/ВЫКЛ.

• Процесс распределения Парето :

Процесс распределения Парето создает независимые и одинаково распределенные (IID) времена между поступлениями. В общем, если X — случайная величина с распределением Парето, то вероятность того, что X больше некоторого числа x, определяется выражением P(X > x) = (x/x_m)-k для всех x ≥ x_m, где k — положительный параметр, а x_m — минимально возможное значение Xi. Распределение вероятностей и функции плотности представлены как: F(t) = 1 – (α/t)β, где α,β ≥ 0 и t ≥ α f(t) = βαβ t-β-1 Параметры β и α являются параметрами формы и местоположения соответственно. Распределение Парето применяется для моделирования самоподобного поступления в пакетном трафике. Его также называют двойным экспоненциальным распределением по степенному закону. Другими важными характеристиками модели являются то, что распределение Парето имеет бесконечную дисперсию, когда β ≥ 2, и достигает бесконечного среднего, когда β ≤ 1.

• Процесс распространения Weibull :

Распределенный процесс Вейбулла имеет тяжелый хвост и может моделировать фиксированную скорость в периоде включения и длительности периода включения/выключения при создании самоподобного трафика путем мультиплексирования источников включения/выключения. Функция распределения в этом случае определяется выражением: F(t) = 1 – e-(t/β)α t > 0 а функция плотности распределения Вейбулла задается как: f(t) = αβ-α tα-1 e -(t/β)α t > 0 где параметры β ≥ 0 и α > 0 — параметры масштаба и местоположения соответственно. Распределение Вейбулла близко к нормальному. При β ≤ 1 функция плотности распределения имеет L-образную форму, а при значениях β > 1 – колоколообразную. Это распределение дает интенсивность отказов, увеличивающуюся со временем. При β > 1 интенсивность отказов со временем уменьшается. При β = 1 интенсивность отказов постоянна, а сроки службы распределены экспоненциально.

• Авторегрессионные модели :

Модель авторегрессии — одна из группы формул линейного прогнозирования, которые пытаются предсказать выходные данные y_n системы на основе предыдущего набора выходных данных {y_k}, где k < n, и входных данных x_n и {x_k}, где k < n. Существуют незначительные изменения в способе расчета прогнозов, на основе которых разрабатывается несколько вариантов модели. По сути, когда модель зависит только от предыдущих результатов системы, ее называют авторегрессионной моделью. Ее называют моделью скользящего среднего (MAM), если она зависит только от входных данных системы. Наконец, модели авторегрессии и скользящего среднего — это модели, которые зависят как от входных, так и от выходных данных для прогнозирования текущего выпуска. Авторегрессионная модель порядка p, обозначаемая как AR(p), имеет следующий вид: Xt = R1 Xt-1 + R2 Xt-2 + ... + Rp Xt-p + Wt где Wt — белый шум, Ri — действительные числа, а Xt — заданные коррелированные случайные числа. Автокорреляционная функция процесса AR(p) состоит из затухающих синусоидальных волн в зависимости от того, являются ли корни (решения) модели действительными или мнимыми. Дискретная авторегрессионная модель порядка p, обозначаемая как DAR(p), генерирует стационарную последовательность дискретных случайных величин с распределением вероятностей и со структурой автокорреляции, аналогичной структуре авторегрессионной модели порядка p.[3]

• Регрессионные модели :

Модели регрессии явно определяют следующую случайную величину в последовательности предыдущих в пределах заданного временного окна и скользящее среднее белого шума.[5]

• Модели ТЕС :

Модели преобразования-расширения-выборки (TES) представляют собой модели нелинейной регрессии с арифметикой по модулю 1. Их цель – выявить как автокорреляцию, так и предельное распределение эмпирических данных. Модели TES состоят из двух основных процессов TES: TES+ и TES–. TES+ создает последовательность, которая имеет положительную корреляцию с задержкой 1, а TES– создает отрицательную корреляцию с задержкой 1.

Несамоподобные модели трафика

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

• Модель распределения Пуассона :

Одной из наиболее широко используемых и старейших моделей дорожного движения является модель Пуассона. Распределение Пуассона без памяти является преобладающей моделью, используемой для анализа трафика в традиционных телефонных сетях. Процесс Пуассона характеризуется как процесс обновления. В пуассоновском процессе времена между поступлениями распределяются экспоненциально с параметром скорости λ: P{An ≤ t} = 1 – exp(-λt). Распределение Пуассона подходит, если поступления поступают из большого количества независимых источников, называемых источниками Пуассона. Распределение имеет среднее значение и дисперсию, равные параметру λ. Распределение Пуассона можно представить как предельную форму биномиального распределения, и оно также широко используется в моделях массового обслуживания. Процессы Пуассона обладают рядом интересных математических свойств. Прежде всего, суперпозиция независимых пуассоновских процессов приводит к новому пуассоновскому процессу, скорость которого равна сумме скоростей независимых пуассоновских процессов. Кроме того, свойство независимого приращения делает пуассоновский процесс без памяти. Процессы Пуассона распространены в сценариях приложений управления трафиком, которые состоят из большого количества независимых потоков трафика. Причина использования проистекает из теоремы Пальма, которая утверждает, что при подходящих условиях такое большое количество независимых мультиплексированных потоков приближается к процессу Пуассона по мере роста числа процессов, но отдельные скорости уменьшаются, чтобы поддерживать постоянную совокупную скорость. Агрегация трафика не всегда должна приводить к процессу Пуассона. Два основных предположения, которые делает модель Пуассона: 1. Количество источников бесконечно 2. Характер поступления трафика является случайным.

• Сложные пуассоновские модели трафика :

В составной модели Пуассона базовая модель Пуассона расширена для одновременной доставки пакетов пакетов. Время прибытия между пакетами распределено экспоненциально, а размер пакета является геометрическим. Математически эта модель имеет два параметра: λ, скорость поступления, и ρ в (0,1), параметр партии. Таким образом, среднее количество пакетов в пакете составляет 1/ ρ, а среднее время прибытия между пакетами составляет 1/ λ. Среднее количество поступивших пакетов за период времени t равно tλ/ ρ. Сложная модель Пуассона разделяет некоторые аналитические преимущества чистой модели Пуассона: модель по-прежнему не имеет памяти, агрегирование потоков по-прежнему является (составным) методом Пуассона, а уравнение устойчивого состояния по-прежнему достаточно просто вычислить, хотя параметры партии варьируются для различные потоки усложнили бы вывод.

• Марковские и встроенные марковские модели:

Марковские модели пытаются смоделировать деятельность источника трафика в сети с помощью конечного числа состояний. Точность модели увеличивается линейно с увеличением количества состояний, используемых в модели. Однако сложность модели также увеличивается пропорционально увеличению количества состояний. Важный аспект модели Маркова — свойство Маркова утверждает, что следующее (будущее) состояние зависит только от текущего состояния. Другими словами, вероятность следующего состояния, обозначаемого некоторой случайной величиной Xn+1, зависит только от текущего состояния, обозначаемого Xn, а не от какого-либо другого состояния Xi, где i<n. Набор случайных величин, относящихся к различным состояниям {Xn}, называется дискретной цепью Маркова.

• Пакетные поезда :

Другая попытка создания модели пакетного трафика была найдена в модели пакетных поездов Джайна и Рутье. Эта модель была главным образом разработана для признания того, что локальность адреса применима к решениям о маршрутизации; то есть пакеты, приходящие вовремя друг к другу, часто направляются в один и тот же пункт назначения. Создавая модель трафика, которая позволяет упростить анализ местоположения, авторы создали понятие пакетных поездов — последовательности пакетов из одного источника, направляющихся в один и тот же пункт назначения (с ответами в противоположном направлении). Пакетные поезда по желанию подразделяются на тандемные прицепы. Трафик между источником и пунктом назначения обычно состоит из серии сообщений туда и обратно. Таким образом, серия пакетов отправляется в одном направлении, за ней следует один или несколько ответных пакетов, а затем новая серия в начальном направлении. В этом случае объем трафика представляет собой суперпозицию пакетных поездов, что приводит к существенному неравномерному поведению. Это уточняет общую концепцию составной модели Пуассона, которая признает, что пакеты доставляются группами, путем анализа того, почему они приходят группами, и лучшего описания атрибутов группы. Наконец, авторы демонстрируют, что время прибытия пакетов не является распределенным по Пуассону, что привело к созданию модели, которая отклоняется от вариаций темы Пуассона. Модель пакетного поезда характеризуется следующими параметрами и связанными с ними распределениями вероятностей:

• среднее время прибытия поездов
• среднее время прибытия автомобилей
• средний размер грузовика (в модели тандемного прицепа)
• средний размер поезда.

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

Модели дорожного движения сегодня

NS-2 — популярный сетевой симулятор; PackMimeHTTP — генератор веб-трафика для NS-2, опубликованный в 2004 году. Он учитывает долгосрочные зависимости и использует дистрибутив Weibull . он полагается на тяжелые хвосты Таким образом, для имитации истинного самоподобия . В большинстве временных масштабов эти усилия оказываются успешными; только длительное моделирование позволит провести различие. Это следует из предположений, согласно которым самоподобные процессы могут быть представлены как суперпозиция многих источников, каждый из которых индивидуально моделируется с распределением с тяжелым хвостом. Понятно, что самоподобные модели дорожного движения находятся в мейнстриме.

См. также

• Модель генерации трафика
• Модель трафика
• Моделирование сетевого трафика

Ссылки

• Макс, Г (01 января 2011 г.). «Моделирование компьютерных сетей» . Физический журнал: серия конференций . 268 (1): 012018. Бибкод : 2011JPhCS.268a2018M . дои : 10.1088/1742-6596/268/1/012018 . ISSN   1742-6596 .
• Гейст, Роберт М; Уэстолл, Джеймс М. (2001). «Корреляционные и распределительные эффекты в моделях сетевого трафика». Оценка производительности . 44 (1–4): 121–138. дои : 10.1016/s0166-5316(00)00055-9 . ISSN   0166-5316 .