Algorytmy kolejkowania : algorytm RED (Random Early Detection)

• Autorzy: Iljaszewicz Paweł

Warianty tytułu

EN

Queueing algorithms : algorithm RED (Random Early Detection)

• Języki publikacji: PL

Abstrakty

PL

Artykuł omawia algorytm Losowego Wczesnego Wykrywania RED (ang. Random Early Detection) pozwalający bramce unikania przeciążeń w sieciach z komutacją pakietów. Brama wykrywa początkowe przeciążenie, obliczając średni rozmiar kolejki. Brama może powiadamiać o przeciążonych połączeniach lub o upuszczeniu pakietów przybywających do bramy, ustawiając bit w nagłówkach pakietów. Kiedy rozmiar średniej kolejki przekracza ustawiony próg, brama opada lub zaznacza każdy przybywający pakiet z pewnym prawdopodobieństwem, gdzie dokładny rozkład prawdopodobieństwa jest funkcją średniego rozmiaru kolejki. Bramki RED utrzymują średnią wielkość kolejki na niskim poziomie, jednocześnie zezwalając na sporadyczne impulsy pakietów w kolejce. Podczas przeciążenia prawdopodobieństwo, że brama powiadamia o konkretnym połączeniu, by zmniejszyć jego okno, jest mniej więcej proporcjonalne do udziału tego w przepustowości przez bramę. Bramki RED są zaprojektowane tak, aby dostarczyć protokół taki jak TCP, przeciążając warstwę transportową. Symulacje sieci TCP / IP są używane do zilustrowania wydajności bramki.

EN

The subject of the study is to present the Random Early Detection (RED) algorithm that allows the gateway to avoid overloading in packet switched networks. The gateway detects the initial overload by calculating the average size of the queue. The gateway can notify about overload connections or by dropping packets arriving at the gate by setting a bit in the packet headers. When the size of the average queue exceeds the set threshold, the gate descends or marks each arriving packet with a certain probability, where the exact probability distribution is a function of the average queue size. RED gates maintain the average queue size at a low level, while allowing occasional packet bursts in the queue. During overload, probability that the gateway informs about a specific connection to reduce its window is more or less proportional to this connection involved in bandwidth through the gate. The RED gateways are designed to provide a protocol such as TCP to overload the transport layer. TCP / IP network simulations are used to illustrate the performance of the gateway.

Słowa kluczowe

PL

aktywne zarządzanie kolejkami; AQM; metody kolejkowania; algorytm RED; przepustowość sieci

EN

active queue management; AQM; queuing methods; RED algorithm; network bandwidth

• Wydawca: Wrocławska Wyższa Szkoła Informatyki Stosowanej "Horyzont"
• Czasopismo: Biuletyn Naukowy Wrocławskiej Wyższej Szkoły Informatyki Stosowanej. Informatyka
• Rocznik: 2018
• Tom: vol. 8, nr 1
• Strony: 4--8
• Opis fizyczny: Bibliogr. 14 poz., rys.

Twórcy

autor

Iljaszewicz Paweł

• Instytut Technologiczno-Przyrodniczy, Falenty, al. Hrabska 3, 05-090 Raszyn

Bibliografia

• [1] D. Agrawal, N.L.S. da Fonseca and F. Granelli, “Integrated ARM/AQM mechanisms based on PID controllers,”Proc. ICC, pp. 6-10, May 2005.
• [2] S. Athuraliya, S.H. Low, V.H. Li and Q. Yin, “REM: Active queue management,” IEEE Network Mag., vol. 15, no. 3, pp. 48-53, 2001
• [3] B. Braden, et al., “Recommendations on queue management and congestion avoidance in the Internet,” IETF RFC2309, 1998
• [4] G. Chen and T. T. Pham, “Introduction to fuzzy systems,”Chapman & Hall/CRC, 2006.
• [5] M. Christiansen, K. Jeffay, D. Ott, and F. D. Smith. “Tuning RED for web traffic,” IEEE/ACM Trans. Networking, vol. 9, No. 3, pp. 249-264, 2001.
• [6] W. Feng, D. Kandlur, D. Saha, and K. Shin, “A selfconfiguring RED gateway,” Proc. INFOCOM, pp. 1320-1328, Mar. 1999.
• [7] S. Floyd, R. Gummadi and S. Shenker, “Adaptive RED: An algorithm for increasing the robustness of RED’s active queue management,” available at http://www.icir.org/floyd/red.html
• [8] S. Floyd and V. Jacobson, “Random early detection gateways for congestion avoidance,” IEEE/ACM Trans. Networking, vol. 1, no. 4, pp. 397-413, Aug. 1993.
• [9] C. V. Hollot, V. Misra, D. Towsley and W. Gong, “On designing improved controllers for AQM routers supporting TCP flows,” Proc. IEEE INFOCOM 2001, vol. 3, Anchorage, Alaska, pp. 1726-1734, April 2001.
• [10] L. Hu and A. D. Kshemkalyani, “HRED: A simple and efficient active queue management algorithm,” Proc. ICCCN 2004, pp. 387-393, 2004.
• [11] C. Joo, S. Bahk and S. S. Lumetta, “Hybrid active queue management,” Proc. ISCC’03, pp. 999-1004, 2003.
• [12] P. Kardasz i inni Termografia w inżynierii biomedycznej Laboratorium-Przegląd Ogólnopolski, 31-38
• [13] J. Koo, K. Chung, H. Kim and H. Lee, “A new active RED algorithm for congestion control in IP networks” LNCS 2343, pp. 469-479, 2002.
• [14] S. S. Kunniyur and R. Srikant, “An adaptive virtual queue (AVQ) algorithm for active queue management,” IEEE/ACM Transactions on Networking, vol. 12, no. 2, pp. 286-299, April 2004.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).