Закрыть

Форма обратной связи

Отправить
mashtab

/812/309-03-21

ПРОГНОЗИРОВАНИЕ ИНТЕНСИВНОСТИ САМОПОДОБНОГО ТРАФИКА В СЕТЯХ СПЕЦИАЛЬНОГО НАЗНАЧЕНИЯ С КОММУТАЦИЕЙ ПАКЕТОВ

10.12.2012 /Статьи

FORECASTING THE INTENSITY OF SELF-SIMILAR TRAFFIC IN SPECIAL-PURPOSE PACKET-SWITCHING NETWORKS

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

Proposed here is a method of forecasting the intensity of self-similar traffic in packet-switching networks, with account for statistical dependency of time-series terms in a long correlation interval. The procedure for using the statistics table is described along with determination of maximum forecasting depth.

Ключевые слова: сеть с коммутацией пакетов, самоподобный трафик, статистическое прогнозирование, временной ряд.
Keywords: packet-switching network, self-similar traffic, statistical forecasting, time-series.

При анализе трафика в сетях с коммутацией пакетов выяснилось, что он обладает свойст-вом самоподобия, из-за чего прогноз его интенсивности, выполненный по классическим процеду-рам, приводит к значительным ошибкам. Самоподобный трафик характеризуется медленно убы-вающей зависимостью автокорреляционной функции, что позволяет более точно (по сравнению с классическими потоками) прогнозировать изменения его параметров [1].

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

Статистическая таблица и методика прогнозирования интенсивности трафика.

Рассмотрим временной ряд числа пакетов в единицу времени x(ti), i=1,2,…., где отсчеты x(ti) вычисляются на непересекающихся интервалах времени[ti-T; ti] .

По результатам моделирования или наблюдения за обслуживанием трафика разделим мно-жество значений x(ti) на уровни xm , m=0,…,M;  . Каждому из уровней поставим в соответст-вие объем сетевых ресурсов, необходимый для качественного обслуживания.

Уровнем квантования i-го отсчета x(ti) будем называть максимальное число  (m=0,…,M), при котором x(ti)≥xm.

Предположим наличие статистической зависимости между m(ti+k) – уровнем квантования (i+k) -го члена временного ряда (k=1,…,K) – и уровнями квантования предыдущих членов m(ti), m(ti-1), … , m(ti-N), что соответствует свойству самоподобия трафика. Это предположение позволяет рассматривать условные вероятности попадания члена x(ti+k) в m-й уровень P(m(ti+k)|m(ti),…,m(ti-N). Ниже предлагается метод прогнозирования интенсивности самоподобного трафика.

По результатам наблюдений составляется таблица. Первые ( ) столбцов таблицы со-держат все комбинации уровней квантования текущего и   предыдущих членов ряда xi, xi-1, … , xi-N,. Число строк таблицы равно MN+1 (для N=2 см. табл. 1).

Следующие KM столбцов таблицы содержат значение переменной ni+k,m(m(ti),m(ti-1),…,m(ti-N)), – число наблюдавшихся попаданий (i+k) -го члена ряда в m-й уровень квантования при условии наблюдения последовательности уровней квантования m(ti),m(ti-1),…,m(ti-N)  N предыдущих членов ряда.

Число N-последовательностей, участвующих в прогнозе уровня квантования члена времен-ного ряда xi+k, зависит от его номера k (рис. 1). Так, прогноз уровня квантования следующего за наблюдаемым члена ряда (k=1) производится по K N-последовательностям. Прогноз уровня кван-тования члена ряда, отстоящего от наблюдаемого на K отсчетов (k=K), производится по одной N-последовательности. В общем, для определения уровня (i+k)-го отсчета в таблице имеется (K-k+1)  временных N-последовательностей наблюдаемых значений.

Таблица 1

Таблица наблюдаемых уровней квантования членов временного ряда

Рис. 1

Отсчеты для прогнозирования уровня (i+k)-го члена ряда

Методика прогнозирования интенсивности трафика следующая:

1.Зафиксировать номер прогнозируемого отсчета временного ряда k ≤ K.

2.Используя таблицу, для m=1,…,M  вычислить вероятность m-го уровня квантования (i+k)-го члена ряда

Так как в таблице содержатся все возможные N-последовательности уровней квантования временного ряда, то для вычисления P(m(ti+k)|m(ti),…,m(ti-K+k-N)) требуется обратиться к таблице (K-k+1) раз. Каждый раз при сдвиге N-последовательности на один отсчет влево номер прогнози-руемого отсчета будет увеличиваться на единицу (см. рис. 1).

Выражения (2) определяют сдвиг N-последовательности на один отсчет влево и ее поиск в N первых столбцах таблицы. Выражение (3) есть вероятность m-го уровня квантования при на-блюдении последовательности уровней m*(ti),…,m*(ti-N).

Значение ni+k+s,m(m*(ti),…,m*(ti-N)) содержится на пересечении строки (m*(ti),…,m*(ti-N)) и столбца таблицы (i+k+s)-го прогнозируемого отсчета для данного значения m.

Выражение  есть сумма значений таблицы по строке (m*(ti),…,m*(ti-N)) в столбце (i+k+s)-го прогнозируемого отсчета.

3.За наиболее вероятный прогнозируемый уровень квантования  m(ti+k)(i+k)-го члена ряда выбирается тот, для которого вероятность P(m(ti+k)|m(ti),m(ti-1),…,m(ti-K+k-N)) максимальна, т.е.

Для использования данных таблицы 1 и представленных выражений необходимо:

1) определить минимальное число наблюдений, необходимое для признания состоятельно-сти вероятностей (3);
2) определить число K – глубину прогнозирования.

Определение минимального числа наблюдений.


Значение P(m(ti+k+s)|m*(ti),…,m*(ti-N)) получается по результатам статистических наблю-дений. Знаменатель выражения (3) равен общему числу наблюдавшихся N-последовательностей m*(ti),…,m*(ti-N) для (k+s)-го прогнозируемого отсчета:

Числитель (3) равен числу положительных исходов – попаданию x(ti+k+s) в m-й уровень.

Попадание x(ti+k+s) в m-й уровень является дискретным событием. Оно в каждом наблюде-нии при фиксированных m*(ti),…,m*(ti-N) может либо произойти, либо не произойти. Таким образом, задача определения минимально необходимого числа наблюдений сводится к оценке вероятности положительного исхода при ее биномиальном распределении по относительной частоте.
Нахождение доверительного интервала для оценки вероятности по относительной частоте основывается на известном выражении [2]

где X – нормально распределенная случайная величина с математическим ожиданием M(X)=a и среднеквадратическим отклонением σ; δ – точность оценки; Ф (σ/δ) – функция Лапласа, значения которой табулированы.

В [2, 3] определено, что если число наблюдений Ni+k+s(m*(ti),…,m*(ti-N)) не слишком ма-ло, то относительная частота появления события P(m(ti+k+s)|m*(ti),…,m*(ti-N)) распределена при-ближенно нормально, а ее математическое ожидание равно истинному значению вероятности.

Для упрощения записи формул введем обозначения:

Границы доверительного интервала p1< P(*)<p2 находятся по формулам:

где γ – надежность (доверительная вероятность) оценки. Обычно принимается γ=0,95.

Задавшись требуемой надежностью и величиной доверительного интервала, расчетным пу-тем или по таблицам [4] можно определить минимальное число наблюдений.

При γ=0,95 и ∆=p2-p1≤0,2 определим зависимость числа положительных исходов n от обще-го числа наблюдений N(*) (табл. 2).

Таблица 2

Число наблюдений

Число положительных исходов n

70

(с1 по 17) и (с 53 по 69)

80

(с1 по 25) и (с 55 по 79)

90

(с1 по 38) и (с 52 по 89)

92

(с 1 по 43) и (с 49 по 91)

93

с1 по 92

Из таблицы видно, что при 93 наблюдениях для любого числа положительных исходов оценка вероятности P(m(ti+k+s)|m*(ti),…,m*(ti-N)) с надежностью 0,95 попадает в 20%-й довери-тельный интервал. Поэтому, при данных условиях число наблюдений в строке (m(ti),…,m(ti-N))  k-м столбце таблицы должно быть не менее 93. С увеличением числа наблюдений доверительный интервал будет уменьшаться.

Определение глубины прогнозирования.

Определение глубины прогнозирования (максимального числа прогнозируемых отсчетов K) связано с выявлением зависимости между наблюдаемым событием (m(ti),…,m(ti-N)) и прогнозом m(ti+k), k=1,…,K.

Известно, что случайное событие Y не зависит от случайного события X, если условная ве-роятность появления события Y равна его безусловной вероятности [2]: P(Y|X)=P(Y).

Для нашего случая  m(ti+k) не зависит (m(ti),…,m(ti-N)), если

Статистическое определение независимости прогноза m(ti+k) и события (m(ti),…,m(ti-N))  сводится к проверке при заданном уровне значимости α=1-γ нулевой гипотезы о равенстве вероятностей биномиальных распределений (7).

Для упрощения записи формул введем обозначения:

Чтобы при заданном уровне значимости   проверить нулевую гипотезу   P(m(ti+k)|m(ti),…,m(ti-N))=P(m(ti+k)) о равенстве вероятности появления событий в двух гене-ральных совокупностях, имеющих биномиальное распределение, при конкурирующей P(m(ti+k)|m(ti),…,m(ti-N))≠P(m(ti+k)) надо вычислить наблюдаемое значение критерия

и по таблице функции Лапласа найти критическую точку uкр по равенству Ф(uкр)=(1-α)/2 .

Величина U при справедливости нулевой гипотезы распределена приближенно нормально с нулевым математическим ожиданием и единичным средним квадратическим отклонением.

Если  , то нет оснований отвергать нулевую гипотезу, а событие (m(ti),…,m(ti-N)) и прогноз m(ti+k) считаются зависимыми.

Таким образом, глубина прогнозирования есть максимальное число шагов K, при котором для заданного уровня значимости   событие (m(ti),…,m(ti-N)) и прогноз m(ti+k) могут считаться зависимыми.

Если событие (m(ti),…,m(ti-N)) и прогноз m(ti+k) зависимы, то элемент таблицы   представляет собой данное, значимое для прогноза.

Методика определения глубины прогнозирования позволяет увязать число прогнозируе-мых отсчетов K с числом анализируемых членов ряда xi, xi-1, xi-2,…, xi-N. С увеличением N возрас-тает глубина, точность прогноза и число строк в таблице.

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

Литература


1. Городецкий А.Я., Заборовский В.С. Фрактальные процессы в компьютерных сетях. СПб.: Изд-во СПбГТУ, 2000.
2. Гмурман В.Е. Теория вероятностей и математическая статистика: Учеб. пособие для ву-зов. М.: Высш. шк., 2004.
3. Брандт З. Статистические методы анализа наблюдений. М.: Мир, 1975.
4. Янко Я. Математико - статистические таблицы. М.: Госстатиздат, 1961.

 

К. т. н. Давыдов А.Е.
A. Davydov