자기 유사 공정

자기 유사 공정은 자기 유사성의 현상을 나타내는 확률적 공정의 일종이다. 자기 유사 현상은 배율의 다른 정도에서 볼 때, 또는 차원(공간 또는 시간)에서 다른 척도로 볼 때 동일하게 작용한다. 자가 유사 프로세스는 긴꼬리 분포라고도 하는 무거운꼬리 분포를 사용하여 설명할 수 있다. 그러한 프로세스의 예는 패킷 간 도착 시간 및 버스트 길이와 같은 트래픽 프로세스를 포함한다. 자체 유사 프로세스는 장기적인 의존성을 보일 수 있다.

개요

강력하고 신뢰할 수 있는 네트워크와 네트워크 서비스의 설계는 오늘날의 인터넷 세계에서 점점 더 어려운 과제가 되었다. 이 목표를 달성하기 위해서는 인터넷 트래픽의 특성을 이해하는 것이 점점 더 중요한 역할을 한다. 측정된 트래픽 추적에 대한 경험적 연구는 네트워크 트래픽에서 자기 유사성을 폭넓게 인식하게 했다.^[1]

자체 유사 이더넷 트래픽은 긴 시간 범위에서 의존성을 나타낸다. 이것은 도착과 출발 과정에서 포아송인 전화 트래픽과 대조된다.^[2]

전통적인 포아송 트래픽에서, 단기 변동은 평균이 될 것이고, 많은 시간을 포함하는 그래프는 일정한 값에 근접할 것이다.

굵은꼬리 분포는 물리적, 사회학적 현상을 포함한 많은 자연현상들에서 관찰되어 왔다. Mandelbrot는 주식 시장, 지진, 기후 및 날씨와 같은 실제 프랙탈 현상을 모델링하기 위해 무거운 꼬리 분포의 사용을 확립했다.^{[citation needed]} 이더넷, WWW, SS7, TCP, FTP, TELNET 및 VBR 비디오(ATM 네트워크를 통해 전송되는 유형의 디지털 비디오) 트래픽은 자체 유사하다.

패킷화된 데이터 네트워크의 자기 유사성은 파일 크기, 인간 상호작용 및/또는 이더넷 역학의 분포에 의해 발생할 수 있다. 컴퓨터 네트워크의 자기 유사성 및 장기 의존적 특성은 네트워크의 분석 및/또는 설계를 수행하는 사람들에게 근본적으로 다른 일련의 문제를 제시하며, 시스템이 구축된 이전의 많은 가정들은 더 이상 자기 유사성의 존재에서는 유효하지 않다.^[3]

포아송 분포

헤비테일 분배가 수학적으로 도입되기 전에, (많은 것 중) 전통적인 전화 네트워크를 모델링하는 데 사용되는 기억 없는 대기 시간 분포를 가진 포아송 과정을 아래에서 간략하게 검토한다.

순차 도착 및 순차 종료를 가정하면 다음과 같다.

주어진 시간 내 통화 도착 횟수는 포아송 분포를 가진다.

P(a)=\left({\frac {\mu ^{a}}}{a!}}}\오른쪽)e^{-\mu }

여기서 a는 시간 T에서의 통화 도착 수입니다. $\mu$ $\mu$ 은 $\mu$ 시간 T에서의 평균 통화 도착 수입니다. 이 때문에 순수치 트래픽은 포아송 트래픽이라고도 한다.

주어진 시간 동안의 통화 출발 횟수도 포아송 분포를 가진다.

P(d)=\left({\frac {\lambda ^{d}}{d!}}}\오른쪽)e^{-\#da }

여기서 d는 시간 T에서의 통화 출발 횟수이고 $\lambda$ $\lambda$ 은 $\lambda$ 시간 T에서의 평균 통화 출발 수입니다.

통화 도착과 출발 사이의 간격 T는 독립적이고 동일한 분포의 무작위 이벤트 사이의 간격이다. 이러한 구간이 음의 지수 분포를 갖는다는 것을 알 수 있다. 즉,:

P[T\geq \ t]=e^{-t/h}\,

여기서 h는 평균 홀딩 시간(MHT)이다.^{[citation needed]}

헤비테일 분포

분포는 만약의 경우 꼬리가 무겁다고 한다.

\lim_{x\to \infit }e^{\lambda x}\Pr[X]=\infit \quad{\mbox{모두 }\lambda >0.\,

굵은꼬리 분포의 한 가지 간단한 예는 파레토 분포다.

자체 유사 트래픽 모델링

(기존의 전화 트래픽과는 달리) 패킷화된 트래픽은 자기 유사성이나 프랙탈적 특성을 나타내기 때문에, 종래의 트래픽 모델은 자기 유사 트래픽을 전달하는 네트워크에는 적용되지 않는다.^{[citation needed]}

음성과 데이터의 융합으로 미래 멀티 서비스 네트워크는 패킷화된 트래픽을 기반으로 하며, 미래 멀티 서비스 네트워크의 개발, 설계, 차원화를 위해 자기 유사 트래픽의 성격을 정확하게 반영하는 모델이 요구될 것이다.^{[citation needed]}

인터넷 연구에서 수행된 이전의 분석 작업은 기하급수적으로 분산된 패킷 상호접속과 같은 가정을 채택했고, 그러한 가정 하에서 도달한 결론은 무거운 꼬리를 가진 분포가 있는 상황에서 오해의 소지가 있거나 부정확할 수 있다.^[2]

장거리 종속 트래픽을 정확하게 나타내는 수학적 모델을 도출하는 것은 연구의 비옥한 영역이다.

트위디 분포에 의한 자기 유사 확률적 공정 모델링

Leland 외 연구진은 자기 유사 확률적 과정을 기술하는 수학적 형식주의를 제공했다.^[4] 숫자의 순서에 따라

Y=(Y_{i}:i=0,1,2,...,N)

비열하게

{\hat {\mu }}={\text{E}}(Y_{i})

=

{\hat {\mu }}={\text{E}}(Y_{i})

(

Yi

)

{\displaystyle {\hat{\mu }}={\text{E

일탈

{\

Y_{i}-{\hat{\mu

y_{i}=Y_{i}-{\hat {\mu }}

분산

{\displaystyle {\hat {\sigma }^{2}={\text

E}}(y_{i}^{2

및 자기 상관 함수

r(k)={\text{E}}(y_{i},y_{i+k})/{\text{E}}(y_{i}^{2})

지연 k를 사용하여, 이 시퀀스의 자기 상관에 긴 범위 동작이 있는 경우

r(k)\심 k^{-d}L(k)

k로서→∞ 그리고 여기서 L(k)은 k의 큰 값에서 서서히 변화하는 함수로서, 이 시퀀스를 자기 유사 프로세스라고 부른다.

bin을 확장하는 방법은 자가 유사 공정 분석에 사용할 수 있다. 평균 값에 기초하여 새로운 생식 시퀀스가 정의될 수 있도록 N 원소의 원래 시퀀스를 m 동일한 크기의 세그먼트 그룹(N/m은 정수)으로 나누는 동일한 크기의 비 겹침 빈 집합을 고려하십시오.

{\displaystyle Y_{i}^{(m)}=(Y_{im-m+1}+}+...

+Y_{im}/m}

.

이 시퀀스에서 결정된 분산은 bin 크기가 다음과 같이 변경됨에 따라 확장된다.

{\text{var}[Y^{(m)}]={\hat {\sigma }^{2}m^{-d}}

자기 상관에 제한 형식이^[5] 있는 경우에만

\lim _{k\to \infty }r(k)/k^{-d}=(2-d)(1-d)/2

\lim _{k\to \infty }r(k)/k^{-d}=(2-d)(1-d)/2

→

\lim _{k\to \infty }r(k)/k^{-d}=(2-d)(1-d)/2

\lim _{k\to \infty }r(k)/k^{-d}=(2-d)(1-d)/2

( k

\lim _{k\to \infty }r(k)/k^{-d}=(2-d)(1-d)/2

)

\lim _{k\to \infty }r(k)/k^{-d}=(2-d)(1-d)/2

/

\lim _{k\to \infty }r(k)/k^{-d}=(2-d)(1-d)/2

-

\lim _{k\to \infty }r(k)/k^{-d}=(2-d)(1-d)/2

=

\lim _{k\to \infty }r(k)/k^{-d}=(2-d)(1-d)/2

(

\lim _{k\to \infty }r(k)/k^{-d}=(2-d)(1-d)/2

- d

\lim _{k\to \infty }r(k)/k^{-d}=(2-d)(1-d)/2

)

\lim _{k\to \infty }r(k)/k^{-d}=(2-d)(1-d)/2

(

\lim _{k\to \infty }r(k)/k^{-d}=(2-d)(1-d)/2

-

\lim _{k\to \infty }r(k)/k^{-d}=(2-d)(1-d)/2

)

\lim _{k\to \infty }r(k)/k^{-d}=(2-d)(1-d)/2

/ 2

{\displaystyle \lim_{k\to \infty }r(k)/k^{-d}=(2-d)(1-d)/2

}

\lim _{k\to \infty }r(k)/k^{-d}=(2-d)(1-d)/2

.

또한 해당 추가 시퀀스 집합을 구성할 수 있음

{\

Y_{i}^{(m

팽창하는 통에 근거해서

displaystyle Z_{

+Y_{im}}}

.

자기 상관 함수가 동일한 동작을 보인다면, 가법 시퀀스는 관계를 준수할 것이다.

{\displaystyle{\text}{var}}[Z_{i}^{(m)}]=m^{2}}{\text{var}}{{\hat {\sigma }}}=({\hat{2}/{\mu }}}}}}{\text{\text{}}}}}E}}[Z_{i}^{(m)}]^{2-d}}}}

$^{\$ 과 ${\hat {\mu }}$ ( ${\hat {\sigma }}^{2}$ ) ${\hat {\sigma }}^{2}$ ${\$ 은 상수이므로 ${\hat {\sigma }}^{2}$ 이 관계는 p=2-d의 분산-평균 전력 법칙(테일러의 법칙)을 구성한다.^[6]

트위디 분포는 지수 분포 모델의 특별한 경우로서 일반화된 선형 모델의 오차 분포를 설명하는 데 사용되는 모델의 한 종류다.^[7]

이러한 트위디 분포는 고유한 척도 불변성으로 특징지어지며, 따라서 트위디 분포에 따르는 임의 변수 Y의 경우, 분산 변수(Y)는 전력 법칙에 의한 평균 E(Y)와 관련된다.

{\text{var}\,(Y)=a[{\text}E}}\,(Y)]^{p}

여기서 a와 p는 양의 상수다. 특정 자기 유사 확률적 공정과 관련된 평균 전력 법칙에 대한 분산의 지수 p는 1과 2 사이의 범위이므로 트위디 화합물 포아송-감마 분포에 의해 부분적으로 모델링될 수 있다.^[6]

트위디 화합물 푸아송 감마 모델의 첨가제 형태는 누적 생성 함수(CGF)를 가지고 있다.

K_{p}^{*}(s;\theta ,\lambda )=\lambda \kappa _{p}(\theta )[(1+s/\theta )^{\alpha }-1]

,

어디에

\kappa _{p}(\theta )={\dfrac {\alpha -1}{\alpha }}\left({\dfrac {\theta }{\alpha -1}}\right)^{\alpha }

\kappa _{p}(\theta )={\dfrac {\alpha -1}{\alpha }}\left({\dfrac {\theta }{\alpha -1}}\right)^{\alpha }

(

\kappa _{p}(\theta )={\dfrac {\alpha -1}{\alpha }}\left({\dfrac {\theta }{\alpha -1}}\right)^{\alpha }

)

\kappa _{p}(\theta )={\dfrac {\alpha -1}{\alpha }}\left({\dfrac {\theta }{\alpha -1}}\right)^{\alpha }

=

\kappa _{p}(\theta )={\dfrac {\alpha -1}{\alpha }}\left({\dfrac {\theta }{\alpha -1}}\right)^{\alpha }

-

\kappa _{p}(\theta )={\dfrac {\alpha -1}{\alpha }}\left({\dfrac {\theta }{\alpha -1}}\right)^{\alpha }

\kappa _{p}(\theta )={\dfrac {\alpha -1}{\alpha }}\left({\dfrac {\theta }{\alpha -1}}\right)^{\alpha }

(

\kappa _{p}(\theta )={\dfrac {\alpha -1}{\alpha }}\left({\dfrac {\theta }{\alpha -1}}\right)^{\alpha }

- 1

\kappa _{p}(\theta )={\dfrac {\alpha -1}{\alpha }}\left({\dfrac {\theta }{\alpha -1}}\right)^{\alpha }

)

\kappa _{p}(\theta )={\dfrac {\alpha -1}{\alpha }}\left({\dfrac {\theta }{\alpha -1}}\right)^{\alpha }

{\

{\dfrac

-1}{\time

-1}{\

dfrac {}}}{\

pa

-1}\pright)^{\cap }},

\kappa _{p}(\theta )={\dfrac {\alpha -1}{\alpha }}\left({\dfrac {\theta }{\alpha -1}}\right)^{\alpha }

}, },

누적 함수, α는 트위디 지수

\alpha ={\dfrac {p-2}{p-1}}

=

\alpha ={\dfrac {p-2}{p-1}}

-

\alpha ={\dfrac {p-2}{p-1}}

\alpha ={\dfrac {p-2}{p-1}}

- 1

{\

s는 생성 함수 변수, θ은 표준 파라미터, λ은 인덱스 파라미터다.

CGF의 첫 번째와 두 번째 파생상품은 s=0으로 각각 평균과 분산을 산출한다. 따라서 가법 모형의 경우 분산이 검정력 법칙에 의한 평균과 관련이 있음을 확인할 수 있다.

\mathrm {var} (Z)\propto \mathrm {E} (Z)^{p}

\mathrm {var} (Z)\propto \mathrm {E} (Z)^{p}

(

\mathrm {var} (Z)\propto \mathrm {E} (Z)^{p}

Z

\mathrm {var} (Z)\propto \mathrm {E} (Z)^{p}

)

\mathrm {var} (Z)\propto \mathrm {E} (Z)^{p}

E

\mathrm {var} (Z)\propto \mathrm {E} (Z)^{p}

(

\mathrm {var} (Z)\propto \mathrm {E} (Z)^{p}

)

\mathrm {var} (Z)\propto \mathrm {E} (Z)^{p}

{\

이 트위디 화합물 포아송-감마 CGF는 특정 자기 유사 확률적 공정의 확률밀도 함수를 나타내지만, 시퀀스 Y에 내재된 장거리 상관관계에 관한 정보는 반환하지 않는다.

그럼에도 불구하고 트위디 분포는 트위디 수렴 정리라고 알려진 중심 한계 유사 수렴 효과에 초점을 맞춘 역할의 이유 때문에 자기 유사 확률 프로세스의 가능한 기원을 이해하는 수단을 제공한다. 비기술적인 용어로 이 정리는 우리에게 점증적으로 분산-평균 전력 법칙을 나타내는 지수 분포 모델이 트위디 모델의 매력 영역 내에 오는 분산 함수를 가져야 한다고 말해준다.

트위디 수렴 정리는 분산의 기원을 평균 전력 법칙 , 1/f 소음 및 다원성, 자기 유사 공정과 관련된 특징으로 설명하는데 사용할 수 있다.^[6]

네트워크 성능

네트워크 성능은 자기 유사성이 증가함에 따라 점차 저하된다. 트래픽이 자체 유사할수록 대기열 크기는 더 길어진다. 자체 유사 트래픽의 대기열 길이 분포는 포아송 소스에서보다 더 느리게 변화한다. 그러나 장기 의존성은 소형 버퍼의 성능에 영향을 미치는 단기 상관관계에 대해 아무런 의미가 없다. 또한 자기 유사 트래픽의 스트림을 집계하면 일반적으로 자기 유사성("버스트성")을 평활화하기 보다는 강화하여 문제를 복잡하게 만든다.^{[citation needed]}

자체 유사 트래픽은 네트워크 성능에 부정적인 영향을 미치는 클러스터링의 지속성을 나타낸다.

(기존의 전화 통신망에서 발견되는) 포아송 트래픽으로, 클러스터링은 단기적으로는 발생하지만 장기적으로는 완화된다.
자체 유사 트래픽에서는 버스트 동작 자체가 버스트(bursty)가 되어 클러스터링 현상을 악화시키고 네트워크 성능을 저하시킬 수 있다.

네트워크 서비스 품질의 많은 측면은 다음과 같이 네트워크 장애를 일으킬 수 있는 트래픽 피크에 대처하는 것에 달려 있다.

셀/패킷 손실 및 대기열 오버플로
지연 한계 위반(예: 비디오)
통계 멀티플렉싱에서 최악의 경우

포아송 프로세스는 상태 비저장 상태여서 품행이 단정하고, 피크 로딩이 지속되지 않아 대기열이 채워지지 않는다. 장기적 질서가 있을 경우 최고점은 더 오래 지속되고 더 큰 영향을 미친다. 즉 평형이 잠시 변화한다.^[8]

참고 항목

긴꼬리교통

참조

^ Park, Kihong; Willinger, Walter (2000), Self-Similar Network Traffic and Performance Evaluation, New York, NY, USA: John Wiley & Sons, Inc., ISBN 0471319740.
^ ^a ^b "Appendix: Heavy-tailed Distributions". Cs.bu.edu. 2001-04-12. Retrieved 2012-06-25.
^ "The Self-Similarity and Long Range Dependence in Networks Web site". Cs.bu.edu. Retrieved 2012-06-25.
^ Leland, W E; Leland, W. E.; M. S. Taqqu; W. Willinger; D. V. Wilson (1994). "On the self-similar nature of ethernet traffic". IEEE/ACM Trans. Netw. 2: 1–15. doi:10.1109/90.282603. S2CID 6011907.
^ Tsybakov B&Georganas ND(1997) ATM 대기열의 자기 유사 트래픽: 정의, 오버플로 확률 바인딩, 셀 지연 분포. IEEE/ACM 트랜스. 네트워 5, 397–409
^ ^a ^b ^c Kendal, Wayne S.; Jørgensen, Bent (2011-12-27). "Tweedie convergence: A mathematical basis for Taylor's power law, 1/f noise, and multifractality". Physical Review E. American Physical Society (APS). 84 (6): 066120. doi:10.1103/physreve.84.066120. ISSN 1539-3755. PMID 22304168.
^ Jørgensen, Bent (1997). The theory of dispersion models. Chapman & Hall. ISBN 978-0412997112.
^ "Everything you always wanted to know about Self-Similar Network Traffic and Long-Range Dependency, but were ashamed to ask*". Cs.kent.ac.uk. Retrieved 2012-06-25.

외부 링크

자체 유사 트래픽이 네트워크 성능에 미치는 영향에 대해 작성된 기사에 대한 수많은 링크를 제공하는 사이트.

[1] Park, Kihong; Willinger, Walter (2000), Self-Similar Network Traffic and Performance Evaluation, New York, NY, USA: John Wiley & Sons, Inc., ISBN 0471319740.

[autogenerated1-2] "Appendix: Heavy-tailed Distributions". Cs.bu.edu. 2001-04-12. Retrieved 2012-06-25.

[3] "The Self-Similarity and Long Range Dependence in Networks Web site". Cs.bu.edu. Retrieved 2012-06-25.

[Leland1994-4] Leland, W E; Leland, W. E.; M. S. Taqqu; W. Willinger; D. V. Wilson (1994). "On the self-similar nature of ethernet traffic". IEEE/ACM Trans. Netw. 2: 1–15. doi:10.1109/90.282603. S2CID 6011907.

[Tsybakov1997-5] Tsybakov B&Georganas ND(1997) ATM 대기열의 자기 유사 트래픽: 정의, 오버플로 확률 바인딩, 셀 지연 분포. IEEE/ACM 트랜스. 네트워 5, 397–409

[Kendal2011b-6] Kendal, Wayne S.; Jørgensen, Bent (2011-12-27). "Tweedie convergence: A mathematical basis for Taylor's power law, 1/f noise, and multifractality". Physical Review E. American Physical Society (APS). 84 (6): 066120. doi:10.1103/physreve.84.066120. ISSN 1539-3755. PMID 22304168.

[Jørgensen-1997-7] Jørgensen, Bent (1997). The theory of dispersion models. Chapman & Hall. ISBN 978-0412997112.

[8] "Everything you always wanted to know about Self-Similar Network Traffic and Long-Range Dependency, but were ashamed to ask*". Cs.kent.ac.uk. Retrieved 2012-06-25.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Search