[논문]Self-Similar 트래픽을 갖는 공유버퍼 메모리 스위치 네트워크 환경에서 호 수락 제어 방법

김기완; 김두용

Self-Similar 트래픽을 갖는 공유버퍼 메모리 스위치 네트워크 환경에서 호 수락 제어 방법
Call Admission Control for Shared Buffer Memory Switch Network with Self-Similar Traffic 원문보기

한국통신학회논문지. The Journal of Korea Information and Communications Society. 네트워크 및 서비스, v.30 no.4B, 2005년, pp.162 - 169

김기완 (순천향대학교 정보기술공학부) , 김두용 (순천향대학교 정보기술공학부)

초록
AI-Helper

패킷 스위치로부터 발생되는 트래픽이 전통적인 트래픽 모델인 포와송 분포와 마코비안 프로세스로 가정된 네트워크로부터 발생되는 트래픽과 상당히 차이가 나는 self-similar 현상을 보이고 있다는 것이 알려지고 있고 또한 기존에 제안된 대부분의 호 수락 제어 방법에 대한 성능 분석은 스위치가 단독으로 존재한다고 가정하여 이루어지고 있다. 그러나 실제 트래픽이 목적지에 도달하기 위해서는 라우팅을 통하여 여러 스위치들을 거쳐야하므로 호 수락 제어 방법에 대한 성능 분석은 다단으로 연결된 스위치로 확장되는 것이 필요하다. 본 논문을 통하여 기존에 제안된 호 수락 제어 방법이 단일 스위치 환경 하에서는 적절하게 동작이 이루어지나 다단으로 스위치가 연결되어 있는 환경에서는 뒤에 위치하고 있는 스위치에 필요 이상의 유효 대역폭을 할당 한다는 것을 알 수 있다. 그러므로 본 논문에서는 공유 버퍼 메모리를 갖는 다단 네트워크 스위치 환경에서 셀 손실률과 이용률 그리고 각 스위치 출력포트의 self-similarity를 분석하여 self-similar 트래픽 환경에서 효과적으로 대역폭을 할당할 수 있는 호 수락 제어 방법을 제안한다.

Abstract ▼ AI-Helper

Network traffic measurements show that the data traffic on packet switched networks has the self-similar features which is different from the traditional traffic models such as Poisson distribution or Markovian process model. Most of the call admission control researches have been done on the performance analysis of a single network switch. It is necessary to consider the performance analysis of the proposed admission control scheme under interconnected switch environment because the data traffic transmits through switches in networks. From the simulation results, it is shown that the call admission control scheme may not operate properly on the interconnected switch even though the scheme works well on a single switch. In this parer, we analyze the cell loss probability, utilization and self-similarity of output ports of the interconnected networks switch by using shared buffer memory management schemes and propose the new call admission control scheme considering the interconnected network switches under self-similar traffic environments.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 self-similar 트래픽 환경에서 공유 메모리를 갖는 버퍼 관리 방법을 적용하여 고속 스위치 망의 효과적인 대역폭 할당 방법을 제안하였다. 기존에 self-similar 환경에서 제안된 호 수락 알고리즘에 대한 성능 분석은 스위치가 단독으로 존재할 경우에만 이루어지고 있는 실정이다.

가설 설정

또한 각각의 공유 버퍼의 개수를 150이라고 가정하고 포트 i를 위해 할당된 버퍼 개수를 k 라고 가정한다. 각 스위치의 출력단에서 트래픽은 라우팅 확률 p=0.5, q=0.5의 확률로 랜덤하게 나뉘어 다음 스위치로 들어간다고 가정한다.
공유 메모리를 갖는 다단으로 구성된 스위치 모델을 시뮬레이션하기 위하여 그림1과 같이 3개의 스위치와 두 개의 입력 포트를 갖는 네트워크 모델로 가정한다. 네트워크 모델에 도착하는 트래픽(Xi, i=l, 2)은 self-similar 성질을 갖는다고 가정흐但 각 단의 스위치들은 지수분포 서비스 시간 八 : 스위치의 서비스율, i, j=l, 2)을 갖는다고 가정한다.
먼저 self-similar 특성을 갖는 트래픽[15, 16, 1기을 발생시키기 위하여 그림 2와 같은 on/off 두 가지 상태를 갖는 트래픽 모델을 가정한다. 그림 3에서 on 상태일 때 발생률이 Ap인 지수분포의 트래픽이 발생하고 off 상태일 때는 트래픽이 발생하지 않는다고 가정하고 O 피 off 상태의 변화는 pareto 분포를 따른다고 가정한다.
그림 5는 CS 방식으로 M(H=0.6200), M (H= 0.6213)라 가정하고 그림 6은 SMXQ 방식으로 Xi (H=0.6131), A2(H=0.6255)라 가정하고 그림 7은 PO 방식으로 Xi(H=0.6098), *2(H=0.6267)라고 가정 하여 시뮬레이션을 수행하였다. 세 번째 스위치에 단일 스위치로 존재할 경우의 유효 대역폭 5.
공유 메모리를 갖는 다단으로 구성된 스위치 모델을 시뮬레이션하기 위하여 그림1과 같이 3개의 스위치와 두 개의 입력 포트를 갖는 네트워크 모델로 가정한다. 네트워크 모델에 도착하는 트래픽(Xi, i=l, 2)은 self-similar 성질을 갖는다고 가정흐但 각 단의 스위치들은 지수분포 서비스 시간 八 : 스위치의 서비스율, i, j=l, 2)을 갖는다고 가정한다. 또한 각각의 공유 버퍼의 개수를 150이라고 가정하고 포트 i를 위해 할당된 버퍼 개수를 k 라고 가정한다.
네트워크 모델에 도착하는 트래픽(Xi, i=l, 2)은 self-similar 성질을 갖는다고 가정흐但 각 단의 스위치들은 지수분포 서비스 시간 八 : 스위치의 서비스율, i, j=l, 2)을 갖는다고 가정한다. 또한 각각의 공유 버퍼의 개수를 150이라고 가정하고 포트 i를 위해 할당된 버퍼 개수를 k 라고 가정한다. 각 스위치의 출력단에서 트래픽은 라우팅 확률 p=0.
먼저 self-similar 특성을 갖는 트래픽[15, 16, 1기을 발생시키기 위하여 그림 2와 같은 on/off 두 가지 상태를 갖는 트래픽 모델을 가정한다. 그림 3에서 on 상태일 때 발생률이 Ap인 지수분포의 트래픽이 발생하고 off 상태일 때는 트래픽이 발생하지 않는다고 가정하고 O 피 off 상태의 변화는 pareto 분포를 따른다고 가정한다.
이때 블록킹하는 셀의 결정은 시스템의 상태에 따라서 혹은 셀의 우선순위 클래스에 따라서 결정될 수 있다. 본 논문에서는 셀이 도착할 때 모든 버퍼가 사용 중이어서 셀을 받아 들일 수 없을 경우 새로운 셀을 위하여 버퍼에서 서비스를 기다리는 셀 중 가장 뒤에 있는 셀을 블록킹 시킨다고 가정한다.

제안 방법

본 논문에서는 공유 메모리를 갖는 버퍼 관리 방법인 CS(complete sharing), SMXQ(sharing with maximum queue), PO(push-out)와 CP(complete partitioning)을 이용하여 다단으로 연결된 스위치의 입력포트에 self-similar 성질을 갖는 트래픽이 들어올 때 여러 스위치를 거치면서 나타나는 출력포트의 self-similarity 정도를 분석하고 각 스위치의 셀 손실률과 이용률(utilization)을 사용하여 스위치를 통과하면서 나타나는 트래픽의 특성 변화에 적응할 수 있는 효과적인 대역폭을 할당할 수 있는 호수 락 제어 방식을 제안할 것이다. 제안된 대역폭 제어 방식을 이용하면 기존에 제안된 일반적인 스위치 대역폭 할당 방식으로 낭비되는 대역폭을 감소시킬 수 있으므로 제한된 자원을 보다 효율적으로 이용 할 수 있을 것이다
표의 각 성분을 구하기 위하여 on/off 트래픽 모델로 가정하여 발생시킨 200만 개의 self-similar 트 래픽을 그림 1에 제안된 63600bits의 공유메모리를 갖는 다단 스위치 모델의 입력 데이터 쇼, b로 하여 시뮬레이션을 수행하였다. 각 스위치에서 필요한 유효 대역폭을 계산하기 위하여 variance-time plot 방법을 이용하여 H값과 식 (10) 을 이용하여 Q 값을 계산하였다[18].

이론/모형

표의 각 성분을 구하기 위하여 on/off 트래픽 모델로 가정하여 발생시킨 200만 개의 self-similar 트 래픽을 그림 1에 제안된 63600bits의 공유메모리를 갖는 다단 스위치 모델의 입력 데이터 쇼, b로 하여 시뮬레이션을 수행하였다. 각 스위치에서 필요한 유효 대역폭을 계산하기 위하여 variance-time plot 방법을 이용하여 H값과 식 (10) 을 이용하여 Q 값을 계산하였다[18]. 또한, 각 스위치의 입력단에서 H값의 변화를 보면 스위치의 이용률이 51%에서 73%로 증가할 때 약 2~5% 정도 H값이 증가하는 것을 알 수 있고 시뮬레이션 결과로부터 뒤에 연결된 스위치의 self-similarity는 앞에 위치하는 스위치의 영향을 받는다는 것을 알 수 있다.

성능/효과

그러나 실제 트래픽은 소스에서 목적지까지 여러 스위치를 거쳐야 하므로 호 수락 알고리즘에 대한 성능 분석은 다단으로 연결된 스위치로 확장시키는 것이 필요하다. 따라서 본 논문에서는 기존에 제안된 호수 락 알고리즘을 이용하여 스위치가 다단으로 연결되어 있을 경우의 성능 분석을 통하여 뒤에 위치하고 있는 스위치에 필요 이상의 유효 대역폭을 할당할 수 있음을 알 수 있었다 즉, 대역폭 할당에 상당한 영향을 미치는 블록킹 확률은 앞단에 위치한 스위치가 버퍼 역할을 수행하므로 감소될 수 있다는 현상을 간과하고 있다. 그러므로 필요한 대역폭을 할 당하기 위해서는 주변의 스위치 중에서 앞에 위치 하고 있는 스위치의 이용률을 고려하는 것이 요구된다.
53xl06bits/s 등을 각각 할당함으로써 대역폭의 낭비를 줄일 수 있을 것이다. 따라서 위의 4가지 방식 모두 두 번째 스위치와 세 번째 스위치를 비교해보면 이용률이 73%로 같지만 표 1에 나타난 것과 같이 블록킹 확률이 세 번째 스위치가 상대적으로 작게 나타나는데 이것은 두 번째 스위치가 세 번째 스위치를 위한 버퍼 역할을 수행하므로 블록킹 확률이 작게 발생하는 것으로 볼 수 있다. 그러므로 식 (4) 를 이용하여 유효 대역폭을 계산한다면 앞에 위치한 스위치의 버퍼 효과로 인한 세 번째 스위치에서의 블록킹 확률의 감소를 식(4)에 반영할 수 없으므로 이로 인해 세 번째 스위치에서는 실제 필요한 대역폭보다 많은 대역폭을 할당하게 되므로 대역폭의 낭비를 가져온 다 그림에 나타난 것과 같이 CP, CS, SMXQ, PO 방식 모두 단일 스위치와 비교할 경우보다 최대 10% 이상의 대역폭 낭비가 있음을 알 수 있다.
네트워크의 성능에 중요한 영향을 미치는 호수 락 제어 (call admission control) 절차는 한정된 대역폭을 갖는 시스템에서 사용자가 요구하는 서비스 질(quality of service)을 스위치가 현재 서비스하고 있는 트래픽과 함께 시스템 내에 수락할 수 있는지 결정한다[1]. 따라서 이러한 호 수락 제어는 ATM 망에서 VBR 트래픽과 같은 불규칙한 트래픽 소스를 다룰 때 사용자가 요구하는 성능을 보장하기 위해 사용자가 이용할 수 있는 가장 나쁜 조건을 가 정하여 대역폭을 할당함으로써 실제 필요로 하는 대역폭보다 많은 양의 대역폭을 할당할 수 있다. 즉 네트워크 내의 대기시간 지연, 트래픽 형태 등과 같은 요인으로 원래 사용자가 요구한 UPC(user parameter control) 등이 더 이상 유효하지 않을 수 있으므로 결과적으로 필요 이상의 대역폭이 할당되어 대역폭의 낭비를 가져올 수 있다.
그림에서와같이 각각의 스위치에서 CS 방식보다 PO 방식의 지연시간이 상대적으로 더 짧은 것을 알 수 있다. 또한 같은 이용률을 가지는 두 번째 스위치와 세 번째 스위치를 비교해보면 기대한 바와 같이 상대적으로 블록킹으로 인한 데이터의 손실이 많은 두 번째 스위치가 세 번째 스위치의 평균 지연시간보다 더 긴 것을 알 수 있다
각 스위치에서 필요한 유효 대역폭을 계산하기 위하여 variance-time plot 방법을 이용하여 H값과 식 (10) 을 이용하여 Q 값을 계산하였다[18]. 또한, 각 스위치의 입력단에서 H값의 변화를 보면 스위치의 이용률이 51%에서 73%로 증가할 때 약 2~5% 정도 H값이 증가하는 것을 알 수 있고 시뮬레이션 결과로부터 뒤에 연결된 스위치의 self-similarity는 앞에 위치하는 스위치의 영향을 받는다는 것을 알 수 있다. 즉, 스위치 11의 출력단의 H 값은 스위치 12의 입력단의 H 값과 동일하며 마찬가지로 스위치 12 출력단의 H 값은 스위치 13 입력단의 H 값과 같다.
그리고 위 표에는 나타나고 있지 않지만 시뮬레이션으로부터 스위치13의 출력단에서의 H값은 버퍼 관리 방법에 관계없이 모두 스위치 13의 입력단의 H 값과 동일한 값을 얻을 수 있었으므로 각 출력단의 self-similarity는 뒤에 위치한 스위치의 이용률이 앞 스위치의 이용률과 같거나 작으면 뒤에 오는 스위치의 H값은 앞에 위치한 스위치의 H 값과 같은 결과를 얻을 수 있다(19]. 또한, 표에서 CP, CS, SMXQ 그리고 PO 방식 모두 두 번째 단과 세 번째 단의 스위치의 이용률이 73%로 같지만 스위치12보다 스위치13의 블 록킹 확률이 상대적으로 적은 것을 알 수 있는데 이러한 현상은 앞에 위치한 스위치가 버퍼로서 역할을 수행하기 때문으로 판단된다.
6267)라고 가정 하여 시뮬레이션을 수행하였다. 세 번째 스위치에 단일 스위치로 존재할 경우의 유효 대역폭 5.39x 106bits/s, 5.31xl06bits/s, 5.53xl06bits/s 등을 각각 할당함으로써 대역폭의 낭비를 줄일 수 있을 것이다. 따라서 위의 4가지 방식 모두 두 번째 스위치와 세 번째 스위치를 비교해보면 이용률이 73%로 같지만 표 1에 나타난 것과 같이 블록킹 확률이 세 번째 스위치가 상대적으로 작게 나타나는데 이것은 두 번째 스위치가 세 번째 스위치를 위한 버퍼 역할을 수행하므로 블록킹 확률이 작게 발생하는 것으로 볼 수 있다.
표 2는 다단 스위치로 이루어진 모델의 유효대역 폭 할당 방법에 대한 효과를 단일 스위치로 이루어진 모델과 비교하기 위하여 표 1에서 사용한 방법과 동일한 방법으로 시뮬레이션을 수행하여 얻은 값을 나타내고 있다. 표 1의 스위치13과 표 2를 비교해보면 스위치의 이용률이 73%로 같을 때 단일 스위치로 가정된 모델의 블록킹 확률이 앞단의 영향을 받는 다단 스위치로 이루어진 모델보다 상대적으로 블록킹 확률이 큰 것을 알 수 있다. 이런 현상은 위에서 언급한 바와 같이 앞단의 스위치가 뒤에 오는 스위치에 일종의 버퍼 역할을 수행함으로써 다단으로 이루어진 모델이 같은 스위치 이용률에도 불구하고 블록킹 확률이 작게 발생하는 것을 알 수 있다.

후속연구

한편, 그림 12와 같이 이용률이 스위치를 통과하면서 계속 증가할 경우 세 번째 스위치의 유효대역 폭 할당을 살펴보면 단일 스위치의 경우보다도 작은 유효 대역폭을 할당하고 있으므로 이러한 경우에는 필요한 유효 대역폭 이상으로 할당되지 않음을 알 수 있다. 그러므로 위의 결과로부터 데이터 트래픽 소스가 라우팅을 통해 중간 경유지의 여러 스위치를 거쳐 목적지에 도달할 경우에 각 스위치에서 필요한 유효 대역폭을 할당하기 위해서는 앞에 위치하고 있는 스위치의 이용률을 고려하는 것이 필요하다. 즉, 앞선 스위치의 이용률과 같거나 작을 때는 최대로 필요한 대역폭이 단일스위치로 이루어진 스위치의 대역폭을 초과하지 않으므로 스위치가 목적지까지 단독으로 존재할 때에 필요한 유효 대역폭을 할당함으로써 대역폭의 낭비를 방지 할 수 있을 것이다
본 논문에서는 공유 메모리를 갖는 버퍼 관리 방법인 CS(complete sharing), SMXQ(sharing with maximum queue), PO(push-out)와 CP(complete partitioning)을 이용하여 다단으로 연결된 스위치의 입력포트에 self-similar 성질을 갖는 트래픽이 들어올 때 여러 스위치를 거치면서 나타나는 출력포트의 self-similarity 정도를 분석하고 각 스위치의 셀 손실률과 이용률(utilization)을 사용하여 스위치를 통과하면서 나타나는 트래픽의 특성 변화에 적응할 수 있는 효과적인 대역폭을 할당할 수 있는 호수 락 제어 방식을 제안할 것이다. 제안된 대역폭 제어 방식을 이용하면 기존에 제안된 일반적인 스위치 대역폭 할당 방식으로 낭비되는 대역폭을 감소시킬 수 있으므로 제한된 자원을 보다 효율적으로 이용 할 수 있을 것이다
제안된 방법을 실제 ATM 망에 적용함으로써 self-similar 현상으로 인한 시스템의 성능 저하를 극복할 수 있고 대역폭의 효율적인 관리로 한정된 자원을 보다 효율적으로 사용할 수 있을 것이다.

참고문헌 (19)

Sathaya. S, ATM forum traffic management specification. ver. 4.0, ATM Forum, Feb, 1996
R. Gibbens and F. Kelly, 'Measurement-based connection admission control,' 15th International Teletraffic Congress, pp. 879-888, Jun. 1997
S. Jamin, P. B. Danizig, S. J. Shenker, and L. Zhang, 'A measurement-based admission control algorithm for integrated services packet networks,' IEEF/ACM Trans. on Networking, vol. 5, no. 1, pp. 56-70, Feb. 1997

상세보기
S. Jamin, S. Shenker and P. Danzig, 'Comparison of measurement-based admission control algorithms for controlled-load service,' IEEE INFOCOM '97, pp. 973-980, Apr. 1997
W. W. Knightly and J. Qiu, 'Measurement-based admission control with aggregate traffic envelope,' IEEE ITWDC '98, Sep. 1998

상세보기
Tse, D. and Grossglauser, M, 'Measurement-based call admission: analysis and simulations,' Proc. IEEE INFOCOM, Japan, Apr, 1997
Grossglauser, M and Tse, D, 'A framework for robust measurement-based admission control,' Proc. ACM SIGCOMM, France, Aug, 1997
I. Norros, 'A storage model with self-similar input,' Queueing Systems, vol. 16, no. 2, pp. 387-396, 1994

상세보기
F. H. M. Chen, J. Mellor and P. Mar, 'A hybrid approach for generating fractional Brownian motion,' IEEE GLOBECOM '96, pp. 591-595, 1996
A. Elwalid and D. Mitra, 'Effective bandwidth of general markovian traffic sources admission control of high speed networks,' IEEF/ACM Trans. on Networking, vol. 1, no. 3, pp.329-343, Jun. 1993

상세보기
B. B. Mandelbrot and J. W. Van Ness, 'Fractional brownian motions,' fractional noises and applications. SIAM Rev., vol. 10, pp. 422-437, 1968

상세보기
J. R. M. Hosking. 'Modeling persistence in hydrological time series using fractional differencing,' Water Resources Research, vol. 20, no. 12, pp. 1898-1908, 1984

상세보기
A. Neidhardt and A. Erramilli, 'Shaping and policing of fractal traffic,' ITC Specialists Seminar on Control in Communication, pp. 253-264, 1996
Stathis, Ch. and B. Maglaris, 'Modeling the self-similar behavior of network traffic,' In the Proceedings of the 6th IFIP Workshop of Performance Modeling and Evaluation of ATM Networks, 1998
H. D. J. Jeong, D. McNickle and K. Pawlikowski, 'A comparative study of three self-similar teletraffic generators,' Proc. European Simulation Multiconference ESM'99, pp. 356-362, Jun. 1999
H. D. J. Jeong, D. McNickle and K. Pawlikowski. 'Fast self-similar teletraffic generation based on FGN and wavelets'. Proc. IEEE International Conference on Networks ICON'99, Brisbane, IEEE Computer Society, pp. 75-82, Sep, 1999
F. Brichet, J. Roberts, A. Simonian, and D. Veitch, 'Heavy traffic analysis of a storage model with long range dependent on/off sources,' Queueing Systems, vol. 23, no. 2, pp. 197-215, 1996

상세보기
Droz. P, Le Boudec, A high-speed self-similar ATM traffic generator including traffic parameter, Technical Report RZ2854
김기완, 김두용, '다중 ATM 스위치의 Self-similar 트래픽 영향분석,' 한국정보과학회 가을학술대회 논문집(III), 제30권, 2호, pp. 136-138, 2003.10

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증