Diffusion approximation and Markovian models of RED control mechanism

• Autorzy: Atmaca T. , Czachórski T. , Laalaoua R.
• Języki publikacji: EN

Abstrakty

EN

The IP networks are faced today with difficult task of satisfying the needs of connections requiring QoS by sharing the same physical resources, e.g. bandwidth and buffers. Buffers are a key component of packet-switched network, as they absorb burst arrivals of packets and hence reduce losses. Larger buffers can absorb larger bursts but they tend to build up long queues and increase queuing delays. It is believed that RED (Random Early Defection) benefits brought by RED. In particular, we examine the impact of RED on the loss rate and the mean delay. We analyze transient and stationary states. We show that the loss probability is the same for TCP and UDP traffics if RED algorithm is used. This loss rate of a flow going trough a RED router does not will alleviate problems related to synchronization of flows and improve QsS by intelligent dropping. In this paper, we develop two types of analytical models (Markovian and diffusion approximation) for the RED buffer management schemes, and use these models to quantify the depend of the burstiness of this flow but only on the load it generates.

PL

Sieci z protokołem IP spotykają się dzisiaj z trudnym zadaniem zaspokojenia potrzeb połączeń wymagających różnej jakości usług (QsS) poprzez dzielenie tych samych zasobów, np. szerokości pasma i buforów. Bufory są kluczowym składnikiem sieci pracujących w systemie przełączania pakietów, jako że absorbują pakiety, które nadeszły w okresach wzmożonego natężenia ruchu i poprzez to zmniejszają straty. Większe bufory mogą absorbować większą liczbę pakietów, lecz prowadzi to do wydłużania kolejek i wzrostu opóźnień. Artykuł przedstawia dwa analityczne(markowowski i dyfuzyjny) modele kolejki z algorytmem RED (Random Early Detection), o którym sądzi się, że poprawi jakość przesyłu. W artykule sprawdza się wpływ algorytmu RED na współczynnik strat i średnie opóźnienie. Analiza jest przeprowadzona dla stanów ustalonych i nieustalonych. Pokazano, że użycie algorytmy RED daje to samo prawdopodobieństwo strat dla ruchu TCP i UDP. Wyniki modeli analitycznych porównano z symulacją.

Słowa kluczowe

EN

RED mechanism; Markov chains; diffusion approximation

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Archiwum Informatyki Teoretycznej i Stosowanej
• Rocznik: 2001
• Tom: T. 13, z. 4
• Strony: 343--354
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Atmaca T.

• Institut National des Telecommunications, France

autor

Czachórski T.

• Institute of Theoretical and Applied Informatics of Polish Academy of Sciences

autor

Laalaoua R.

• Institut National des Telecommunications; Alcatel CIT, France

Bibliografia

• [1] Ramakrishnan, K., Floyd, S: A Proposal to add Explicit Congestion Notification (ECN) to IP.RFC 2481, ftp://ftp.isi.edu/in-notes/rfc2481.txt.
• [2] Floyd, S., Jacobson, V.: Random Early Detection (RED) gateways for congestion avoidance IF.F.F/ACM Transactions on Networkingl,vol. I, August 1997.
• [3] Chiu, D. M.. Jain, R.: Analysis of the increase and decrease algorithms for congestion avoidance in computer networks. Computer Networks and ISDN Systems. 17(1): 1-14, 1989.
• [4] Floyd, S., Fall, K.: Promoting the use of end-to-end congestion control in the Internet IFFF/ACM Transactions on Networking, August, 1999.
• [5] Jacobson, V.: Congestion avoidance and control. Proceedings of ACM SIGCOMM'88, 1988.
• [6] Paxson, V., Floyd, S.: Wide area traffic: the faillure of Poisson modeling. IEEE/ACM Transactions on Net¬working. vol 3, June 1995.
• [7] Braden, B., et al.: Recommendations on queue management and congestion avoioclance in the Internet. RFC 2309. April 1998.
• [8] Jeffay. M. C. K.. Ott. J. T., Smith, F.: Tuning Red for web traffic. Proceedings of ACM/SIGCOMM }, 2000.
• [9] May, M., Bonald, T.. Bolot, J. C.: Analytic Evaluation of RED Petfonnance. Proceedings of Infocom, 2000.
• [10] Ott, T. J., Lakshman, T. V.. Wong, L. H.: SRED: Stabilized RED. Proceedings of Infocom. 1999.
• [11 ] Feng, W., Kandlur, D., Saha. D.. Shin, K.: Blue: New Class of Active Queue Management Algorithms. tech. Rep. UM CSE-TR-387-99, 1999.
• [12] Lin. D., Morris. R.: Dynamic of random early detection. Proceedings of ACM/SIGCOMM, 1997.
• [13] Firoiu, V.. Borden, M.: A Study of active queue management for congestion control. Proceedings of Infocom, 2000.
• [14] Stewart, W. J.: An Introduction to the Numerical Solution of Markov Chains. Princeton Academic Press, 1994.
• [15] Czachorski, T.: A method to solve diffusion equation with instantaneous return processes acting as boundary conditions. Bulletin of Polish Academy of Sciences, Technical Sciences, vol. 41 (1993). no. 4.
• [16] Laalaoua. R., Czachorski, T., Atmaca, T.: Markovian Model of RED Mechanism. CCGrid'2001. Brisbane Australia, 15-18 May 2001.
• [17] Laalaoua, R.. Czachorski, T., Jednis, S., Atmaca, T.: Diffusion Model of RED Control Mechanism. International Conference on Networking ICNO1 , July 9-13, 2001. CREF, Universite de Haute Alsace, Colmar, France.
• [18] Gelcnbe, E: On Approximate Computer Systems Models. J. ACM, vol.22, no.2, 1975.
• [19] Newell, G. F.: Applications of Queueing Theory. Chapman and Hall, London 1971.