Journal of KIISE:Information Networking (한국정보과학회논문지:정보통신)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

(A New Queue Management Algorithm Improving Fairness of the Internet Congestion Control)

인터넷 혼잡제어에서 공정성 향상을 위한 새로운 큐 관리 알고리즘

  • Published : 2003.06.01
Download PDF
⟨ Previous Next ⟩

Abstract

In order to reduce the increasing packet loss rates caused by an exponential increase in network traffic, the IETF(Internet Engineering Task Force) is considering the deployment of active queue management techniques such as RED(Random Early Detection) algorithm. However, RED algorithm simple but does not protect traffic from high-bandwidth flows, which include not only flows that fail to use end-to-end congestion control such as UDP flow, but also short round-trip time TCP flows. In this paper, in order to solve this problem, we propose a simple fairness queue management scheme, called AFQM(Approximate Fair Queue Management) algorithm, that discriminate against the flows which submit more packets/sec than is allowed by their fair share. By doing this, the scheme aims to approximate the fair queueing policy Since it is a small overhead and easy to implement, AFQM algorithm controls unresponsive or misbehaving flows with a minimum overhead.

현재 인터넷 라우터는 네트워크 트래픽의 지수적인 증가로 인해 발생하는 혼잡 상황을 명시적으로 해결 할 수 없다. 이러한 문제를 해결하기 위해 IETF(Internet Engineering Task Force)에서는 RED(Random Early Detection) 알고리즘과 같은 능동적인 큐 관리(Active Queue Management) 알고리즘을 제시하였다. 하지만 RED 알고리즘은 UDP 플로우와 같이 양 종단간 혼잡제어를 하지 않는 플로우(flow)나 RTT(Round Trip Time)값이 작은 TCP 플로우에 대한 불공정성 문제를 가지고 있으며 이로 인하여 혼잡상황이 악화되는 문제를 가지고 있다. 본 논문에서는 이러한 문제를 해결하기 위해, 새로운 공정성 향상 큐 관리 알고리즘인 AFQM(Approximate Fair Queue Management) 알고리즘을 제안하였다. AFQM 알고리즘은 공정분배율(fair share rate) 이상의 대역폭을 차지하는 플로우를 판별하여 공정성을 보장한다. AFQM 알고리즘은 적은 오버헤드(overhead)와 구현의 용이성을 가지고 있기 때문에 비반응 플로우(unresponsive flow)와 불량 사용자 플로우(misbehaving flow)를 큰 오버헤드 없이 관리하여 플로우간의 공정성을 보장하는 알고리즘 이다.

Keywords

References

  1. Braden, B., Clark, D., Crowcroft, J., Davie, B., Deering, S., Estrin, D., Floyd, S., Jacobson, V., Minshall, G., Partridge, C., Peterson, L., Ramakrishman, K., Shenker, S., Wroclawski, J., Zhang, L., 'Recommendations on Queue Management and Congestion Avoidance in the Internet,' IETF RFC (Informational) 2309, April 1998
  2. Jacobson, V., 'Congestion Avoidance and Control,' Proceeding of SIGCOMM 88, August 1988 https://doi.org/10.1145/52324.52356
  3. Stevens, W., 'TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery,' IETF RFC 2001, January 1997
  4. Floyd, S., and Fall, K., 'Router Mechanisms to Support End-to-Eng Congestion Control,' LBL Techinical report, Frbruary 1997
  5. Demers, A., Keshav, S., and Shenker, S., 'Analysis and Simulation of a Fair Queueing Algorithm,' Journal fo Internetworking Research and Experience, Also in Proceedings of ACM SIGCOMM 89 https://doi.org/10.1145/75246.75248
  6. Stocia, I., Shemker, S., and Zhang, H., 'Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks,' Proceedings of ACM SIGCOMM 98, August 1998 https://doi.org/10.1145/285237.285273
  7. Mckenny, P., 'Stochastic Faimess Queueing,' Proceedings of INFOCOM 90, pp733-740, June 1990
  8. Legout, A. and Biersack, E. W., 'Revisiting the Fair Queueing Paradigm for End-to-End Congestion Control,' IEEE Network Magazine, 2002, September https://doi.org/10.1109/MNET.2002.1035116
  9. Floyd, S. and Jacobson, V., 'Random Early Detection Gateways for Congestion Avoidance,' IEEE/ACM Transaction on Networking, August 1993 https://doi.org/10.1109/90.251892
  10. Lin, D. and Morris, R., 'Dynamics of random early detection,' ACM SIGCOMM 97, pp127-137, October 1997 https://doi.org/10.1145/263105.263154
  11. Pan, R., Prabhakar, B., and Psounis. K., 'CHOKe, A Stateless Active Queue Management Scheme for Approximating Fair Bandwidth Allocation,' Proceedings of INFOCOM 2000, February 2000
  12. Mahajan, R. and Floyd, S. 'Controlling High-Bandwidth Flows at the Congested Router,' ACIRI, Berkeley, California, November 2000
  13. Padhy, J., Firoiu, V., Towsley, D. and Kurose, J., 'A Stchastic Model of TCP Reno Congestion Avoidance and Control,' Technical Report CMPSCI TR 99-02, Univ. of Massachusetts, Amberst, 1999
  14. UCB/LBNL/VINT, 'Network Simulator-ns (version2.1b9a),' http://www-mash.cs.berkeley.edu/ns/