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

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

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

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

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

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

Шаги моделирования сетевого трафика

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

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

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

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

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

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

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

Илкка Норрос

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

  • КАЧАТЬ:

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

Процесс распределения Парето производит независимые и одинаково распределенные (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.

Распределенный процесс Вейбулла имеет тяжелый хвост и может моделировать фиксированную скорость в периодах ВКЛ и ВКЛ/ВЫКЛ при создании самоподобного трафика путем мультиплексирования источников ВКЛ/ВЫКЛ. Функция распределения в этом случае задается как: 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]

  • Модели ТЭС:

Модели Transform-expand-sample (TES) — это нелинейные регрессионные модели с арифметикой по модулю 1. Они нацелены на захват как автокорреляции, так и предельного распределения эмпирических данных. Модели TES состоят из двух основных процессов TES: TES+ и TES–. TES+ создает последовательность, которая имеет положительную корреляцию при лаге 1, тогда как TES– создает отрицательную корреляцию при лаге 1. [16]

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

Ссылки

  1. ^ Виллингер и Пэксон (1998). «Там, где математика встречается с Интернетом» (PDF) . AMS.
  2. ^ Парк, Кихонг; Виллингер, Уолтер (2000). Самоподобный сетевой трафик и оценка производительности . Нью-Йорк: Wiley. doi :10.1002/047120644X.fmatter_indsub. ISBN 978-0-471-31974-0.
  3. ^ Адас, А. (1997). «Модели трафика в широкополосных сетях». Журнал IEEE Communications . 35 (7): 82– 89. CiteSeerX 10.1.1.23.1461 . doi :10.1109/35.601746. ISSN  0163-6804. 
  4. ^ Michiel, H.; Laevens, K. (1997). «Инженерия телетрафика в эпоху широкополосной связи». Труды IEEE . 85 (12): 2007–2033 . doi :10.1109/5.650182. ISSN  0018-9219.
  5. ^ Frost, VS; Melamed, B. (1994). «Моделирование трафика для телекоммуникационных сетей». IEEE Communications Magazine . 32 (3): 70– 81. doi :10.1109/35.267444. ISSN  0163-6804. S2CID  19019323.
  6. ^ Цзянь-Син Ву; Хуан-Пао Линь; Леу-Шин Лан (2002). «Новая аналитическая структура для динамического управления мобильностью сетей PCS». Труды IEEE по мобильным вычислениям . 99 (3): 208– 220. doi :10.1109/TMC.2002.1081756.
  7. ^ Thajchayapong, S.; Peha, JM (2006). «Мобильные шаблоны в микросотовых беспроводных сетях» (PDF) . IEEE Transactions on Mobile Computing . 5 (1): 52– 63. doi :10.1109/tmc.2006.13. ISSN  1536-1233. S2CID  1175255.
  8. ^ ab Thomas M. Chen (2007). «Моделирование сетевого трафика». Южный методистский университет, Даллас, Техас.
  9. ^ Клейнрок, Леонард (1975). Системы очередей (на немецком языке). Нью-Йорк: Wiley. ISBN 978-0-471-49110-1.
  10. ^ Barakat, C.; Thiran, P.; Iannaccone, G.; Diot, C.; Owezarski, P. (2003). «Моделирование трафика магистральной сети Интернет на уровне потока». IEEE Transactions on Signal Processing . 51 (8): 2111– 2124. Bibcode : 2003ITSP...51.2111B. CiteSeerX 10.1.1.2.8066 . doi : 10.1109/tsp.2003.814521. ISSN  1053-587X. 
  11. ^ "Заметки об эффективных полосах пропускания". Статистическая лаборатория . Получено 2017-10-26 .
  12. ^ Ногейра, Антониу; Сальвадор, Пауло; Валадас, Руи; Пачеко, Антониу (2003). «Моделирование сетевого трафика с помощью мультифрактального поведения» (PDF) . Телекоммуникационные системы . 24 (2/4): 339–362 . doi :10.1023/a:1026183318200. ISSN  1018-4864. S2CID  15332498. Архивировано из оригинала (PDF) 27 октября 2017 г.
  13. ^ DK Arrowsmith, RJ Mondragon (2006). "Моделирование сетевого трафика данных" (PDF) . Queen Mary, Лондонский университет . Получено 26 октября 2017 г.
  14. ^ abcdefgh Чандрасекаран, Балакришнан (2006-11-27). "Обзор моделей сетевого трафика". Вашингтонский университет в Сент-Луисе - Компьютерные науки и инженерия в Вашингтонском университете . Получено 2017-10-26 .
  15. ^ Уилсон, Майкл Л. (2006). «Исторический взгляд на модели сетевого трафика». wustl.edu . Получено 26.10.2017 .
  16. ^ Jelenkovic, PR; Melamed, B. (1995). "Алгоритмическое моделирование процессов TES" (PDF) . IEEE Transactions on Automatic Control . 40 (7): 1305– 1312. CiteSeerX 10.1.1.421.5082 . doi :10.1109/9.400470. ISSN  0018-9286. 
  17. ^ Джейн, Р.; Рутье, С. (1986). «Пакетные поезда — измерения и новая модель для трафика компьютерных сетей». Журнал IEEE по избранным областям в коммуникациях . 4 (6): 986–995 . CiteSeerX 10.1.1.138.4617 . doi :10.1109/jsac.1986.1146410. ISSN  0733-8716. 
  18. ^ "nsnam". ns и nam Sourceforge home . 2010-04-05 . Получено 2017-10-26 .
  • Макс, Г (2011-01-01). "Моделирование компьютерных сетей". Journal of Physics: Conference Series . 268 (1): 012018. Bibcode : 2011JPhCS.268a2018M. doi : 10.1088/1742-6596/268/1/012018 . ISSN  1742-6596.
  • Гейст, Роберт М.; Уэстолл, Джеймс М. (2001). «Корреляционные и распределительные эффекты в моделях сетевого трафика». Оценка производительности . 44 ( 1–4 ): 121–138 . doi :10.1016/s0166-5316(00)00055-9. ISSN  0166-5316.
Retrieved from "https://en.wikipedia.org/w/index.php?title=History_of_network_traffic_models&oldid=1260109843"