Traffic Modeling (2)

네트워크 트래픽의 좋은(예측적) 모델은 확률적 process이다.

우리는 일반적으로 단위 시간당 byte 수(또는 패킷 또는 flow)에 대해 말한다.

stochastic process(확률적 과정)은 랜덤 변수의 집합이다.

 

Distribution Function

랜덤 변수 X가 주어지면 확률 분포 함수(PDF)로 나타낼 수 있다.

histogram

f(x) = P(x)

 

Histogram and CDFs

CDF F(x) = P[X_i <= x]는 각각의 고유한 데이터 값에 대한 point를 가지며, PDF를 평가한 histogram 보다

정확할 수 있다.

통계적 data binning은 더 많거나 덜 연속적인 값의 숫자를 더 적은수의 "bins"으로 그룹화 하는 방법이다.

CDF

 

Modeling a Distribution

통계적 방법은 data set가 특정 분포에 의해 잘 설명되는지 여부를 묻기 위함이다.

관련된 매개변수들을 추정한다.

Distribution Tails

분포의 특히 중요한 부분은 tail 이다.

P[X > x]

큰 값은 통계와 성능을 지배한다.

tail의 모양은 매우 중요하다.

 

Light Tails, Heavy Tails

Light tails - Exponential or faster decline = f1 (x)

Heavy tails - Slower than any exponential = f2 (x)

 

Heavy-tailed

분포의 점근적 형상이

가 되도록 power-law(멱법칙)를 따르는 경우 분포는 heavy tailed가 된다.

매개 변수 a는 tail 분포의 heaviness를 설명하며, a가 작아질 수록 분포가 heavy-tailed된다.

확률 질량의 많은 부분이 분포의 tail에 존재할 수 있다.

분포의 점근적(즉, tail) 모양은 쌍곡선이며 지수분포보다 느리게 수렴한다.

 

A fundamental Shift in Viewpoint

예전에는 light tail에 집중하였다.

하지만 요즘에는 heavy tail에 집중한다.

large observation은 무시할 수 없는 확률을 가진다.

대규모 large observation은 드물지만, 시스템의 성능 특성을 지배할 수 있다.

 

Use of Heavy-tailed

컴퓨터 시스템의 데이터 객체 크기.

웹서버에 저장된 파일

인터넷을 통해 이동하는 데이터의 객체/흐름

일반적인 Unix 파일 시스템에 저장된 파일

파일 시스템, 디스크 및 테이프 작업의 I/O 추적

process/job 수명

특정 그래프의 노트 차수

인터넷 도메인 간 및 라우터 구조

WWW 페이지의 연결

Zipf의 법칙

 

Zipf's law

zipf의 법칙은 언어 corpus와 같이 특정 데이터 집합에서 특정 단어의 빈도가 순위에 반비례하는 통계 분포이다.

 

Pareto distribution

파레토 분포 process는 독립적이고 동일하게 분포된 시간을 생성한다.

가장 단순한 heavy-tailed 분포이다.

k는 x의 최솟값(척도 계수 포함)이며, tail 분포에 영향을 주지 않는다.

The effect of k in the Pareto distribution with (a) k =1; and (b) k = 10

x는 랜덤 변수이며, 랜던 실험의 결과를 숫자에 mapping하는 수학적 함수이다.

a는 tail 분포의 heaviness이다.

매개변수 a와 k는 각각 shape parameter(형상 모수), location parameter(위치 모수)

파레토 분포는 패킷 traffic의 self-similar arrival(자기 유사 도착)모델이 적용된다.

model의 중요한 특성은 a<= 2 일 때 파레토 분포가 무한한 분산을 가지며, a <= 1일 때 무한한 평균을

달성한다는 것이다.

 

X가 파레토 분포를 갖는 임시 변수라면, X가 어떤 숫자 X보다 클 확률, 즉 생존함수(tail function)는 

에 의해 주어지며, 여기서 k(k > 0)는 X의 가능한 최솟값이고, a는 양의 매개 변수이다.

 

파레토 분포는 scale parameter(척도 모수) k와 tail index로 알려진 shape parameter(형상 모수) a로

특징지어진다.

파레토 분포의 CDF

모든 x ≥ k 에 대해 P(X > x) = (k / x)^a 

여기서 a는 양의 매개변수(모수)이고, k는 x의 최소 가능 값이다.

확률 분포 및 밀도 함수는 다음과 같이 표현된다.

 

Weibull distribution

weibull 분산은 heavy-tailed 하고 ON/OFF 소스를 다중화 하여 자체 유사 traffic(self similar traffic)을 생성할 때, 

ON/OFF 기간 및 ON/OFF 기간 길이로 고정 속도를 모델링할 수 있다.

The effect of (a) a; and (b) b in Weibull distribution

모수(distribution) a와 b는 모두 tail 분포에 영향을 미친다.

b의 값에 더 민감하다.

weibull 분포의 CDF는 다음과 같다.

이 경우의 분포함수는

, x >= 0

 

으로 주어지며, Weibull 분포의 밀도 함수는

로 주어진다.

여기서 매개변수 a > 0 와 b > 0은 각각 척도 모수(scale parameter)와 위치 모수(location parameter)이다.

 

weibull 분포가 정규분포에 가깝다.

a<=1 의 경우 분포의 밀도함수는 L자 모형이고 a>1 의 값은 종 모양이다.

 

Meaning of heavy-tailed distribution

일반적으로, heavy tailed 분포는 packet 도착 시간 및 burst 길이와 같은 traffic process를 

설명한다.

heavy tail 분포는 값이 매우 높은 value가 많은 경향이 있다.

그것은 arrival rate가 service rate보다 높다는 의미이다.

 

Characterizing a traffic process

marginals(한계) 와 autocorrelation(자기상관)

두가지 특성이 중요하다.

LAN 및 WAN 과 같은 packet 데이터 네트워크의 traffic 측정에 대한 최근의 분석은 

heavy tailed, self-similar(자기 유사성), fractal 그리고 LRD 특성을 보여준다.

 

How Does Self-Similarity Arise?

Flows -> Autocorrelation -> Self-similarity

flow의 길이의 분포에는 power law(멱함수)의 tail이 있다.

=> autocorrelation은 power law(멱함수) 처럼 감소한다.

 

Self-Similarity

Self-similarity indicator

광범위한 시간 범위에 걸쳐 집계 traffic이 시간 상관관계를 나타내는 경우 Hurst parameter(H)라고 하는

단이 매개 변수로 특징지을 수 있다.

 

Hurst parameter

집계 traffic stream의 self-similarity 측정

H가 1에 가까워지면, self-similarity의 정도가 증가

 

1) Variancd vs Time

2) R/S plot

3) Whittle Estimator

위 3가지가 Hurst parameter을 측정한다.

 

H = 1일 때 정확한 self-similarity

0.5 < H < 1 일때 점근적(asymptotically) self-similarity

 

Evidence of Self-similarity

self-similarity는 모든 scale(척도)에서 동일한 특성을 나타내는 분포를 나타낸다.

이것은 포아송 분포와 다르다.



bin 크기가 증가하면, 

포아송 traffic smooth하게 되어

분포 평균에서 평평한 선에 도달한다.

 

진정한 self-similarity는 그렇지 않을 것이다.

self-similarity는 모든 scale(척도)에서

burst를 보여준다.

 

 

 

 

 

 

 

 

 

 

 

왼쪽에는 실제 네트워크 추적이 다른

시간 scale로 나타납니다.

 

 

오른쪽에는 동일한 시간 scale에서 

합성 traffic을 생성하는 순순한 포아송

process가 있다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

packet 수는 시간 scale이 변경됨에 따라 적절한 scale로 재정규화 된다.

가장 큰 시간 scale에서 차이가 명확하다.

포아송 process와 self-similar process는 모두 올바른 시간 scale에서 burst성질을 가진다.

그러나 포아송 process와 달리 self-similar process의 burst는 natural length가 없다.

burst는 10ms scale에서 100s scale까지 명확하다.

 

Meaning of Self-similarity

시간 함수로 시간 간격 당 관측 packet 수를 표시하면, 선택한 간격 크기에 관계없이 그래프가 

동일하게 표시된다.

데이터를 검사하는데 사용하는 시간 scale에 관계없이 유사한 패턴이 나타난다.

ex) 10msec, 100msec, 1 sec, 10 sec, ...

 

1) burstiness는 많은 시간 scale에 걸쳐 존재한다.

2) burst의 natural length는 없다.

3) 포아송 traffic과 달리 traffic을 집계할 때 , traffic이 반드시 smoother하지는 않다.