버퍼 관리 알고리즘에 관한 연구

소개글

현재의 인터넷환경에서 효율적인 혼잡제어를 위하여 라우터 등에서 사용되는 버퍼관리 알고리즘을 조사/연구한 논문입니다.
RED(Random Early Detection), BLUE, FRED(Fair RED)를 중점적으로 연구했으며 이 외에 ARED(Adaptive RED), RIO(RED with In/Out), WRED(Weighted RED), SRED(Stabilized RED), BIO(BLUE with In/Out) 등의 알고리즘도 간략하게 살펴보았습니다.
RED, FRED, BLUE는 바로 구현가능할정도의 알고리즘까지 담고 있으며
단일 소스에서 RED vs BLUE, 다중 소스에서 RED vs FRED 를 시뮬레이션 하여 각 환경에서 알고리즘이 나타내는 특징/경향 등을 그래프와 함께 도시하였습니다.

목차

1. 서론
2. 관련연구
2.1 RED, ARED, RIO
2.2 FRED, WRED, SRED
2.3 BLUE, BIO
3. 주요 알고리즘 분석
3.1 RED
3.2 FRED
3.3 BLUE
4. 성능 비교 및 분석
4.1 단일 연결에서의 RED/BLUE
4.2 다중 연결에서의 RED/FRED
5. 결론
6. 참고문헌

본문내용

요 약
현재의 인터넷은 트래픽 증가의 상황에서 소스 기반의 TCP 혼잡 제어 방식과 함께 라우터에서의 버퍼 관리를 통한 혼잡 제어의 필요성이 대두됨에 따라 QoS의 보장과 스트리밍 서비스를 위한 버퍼 관리 및 스케줄링 기법이 고도화 되고 있다. IETF(Internet Engineering Task Force)에서는 이러한 혼잡 상황의 해결을 위해 RED(Random Early Detection) 알고리즘과 같은 능동적인 버퍼 관리 기법을 제시하였으나, 평균 버퍼 길이를 이용한 RED의 한계와 불공정성 등에 대한 문제를 가지고 있다. 이러한 문제를 해결하기 위한 RED를 변형한 여러 가지 방법들이 제시되고 있으며, 본 논문에서는 기반이 되는 RED 알고리즘과 FRED(Fair RED), 그리고 평균 버퍼 길이를 갖지 않고 현재의 버퍼 길이를 사용하여 혼잡을 제어하는 BLUE 알고리즘에 대하여 자세히 분석, 실험하여 비교해 보았고 이들을 기반으로 한 몇 가지 알고리즘들에 대하여 간단히 살펴보았다.

2. 관련 연구
현재 제안된 많은 버퍼 관리 알고리즘들은 평균 버퍼 길이를 기준으로 하는 RED와 이를 변형 또는 보완한 것이다. 여기에는 RED, ARED(Adaptive RED), 패킷을 In/Out으로 나누어 RED를 적용하는 RIO(RED with In/Out), 여러 flow에 대하여 RED를 적용하는 FRED, WRED(Weighted RED), SRED(Stabilized RED) 등이 있다. 또한 RED와 다르게 패킷 손실과 링크 사용률을 기준으로 하는 BLUE, BIO(BLUE with In/Out) 등이 있다.

3. 주요 알고리즘 분석
앞에서 간단히 알아본 알고리즘 중 여러 응용 알고리즘들의 기반으로 많이 사용되고 있는 RED, FRED, BLUE 알고리즘을 자세히 분석해보았다.

참고 자료

[1] Ja-Hon Koo, Woong-Chul Choi, Kwang-Sue Chung, “A New Queue Management Algorithm Improving Fairness of the Internet Congestion Control," 정보과학회논문지: 정보통신, vol. 30, no. 3, Jun. 2003, pp. 437-447.
[2] In-Tae Ryoo, Een-Kee Hong, Doug-Young Shu, "A Study on State Dependent RED and Dynamic Scheduling Scheme for Real-time Internet Service," 한국통신학회논문지, vol. 28, no. 9B, Sep. 2003, pp. 823-833.
[3] H. Jonathan Chao, Xiaolei Guo, QUALITY OF SERVICE CONTROL IN HIGH-SPEED NETWORKS, 2002. pp. 214-234.
[4] Dong Lin, Robert Morris, "Dynamics of Random Early Detection," Proc. ACM SIGCOMM., Sep. 1997, pp. 127-137.
[5] Teunis J. Ott, T.V. Lakshman, Larry H. Wong, "SRED: Stabilized RED," Proc. IEEE INFOCOM, Mar. 1999.
[6] Wu-chang Feng, Dilip D. Kandlur, Debanjan Saha, Kang G. Shin, "BLUE: A new class of active queue management," Univ. Michigan CSE-TR-387-99, Apr. 1999.
[7] Bahri Okuroglu, Sema Oktug, "BIO: An Alternative to RIO," SPIE ITCom: Int`l Symp. Convergence of IT and Comm., Denver, USA, Aug. 2001, pp. 4524-4532.