On the search of efficient AQM for large delay networks

• Autorzy: Brachman A. , Chrost Ł.

Warianty tytułu

PL

Algorytm AQM dla sieci z dużymi opóźnieniami

• Języki publikacji: EN

Abstrakty

EN

The main idea of all Active Queue Management algorithms, is to notify the TCP sender about incoming congestion by dropping packets, to prevent from the buffer overflow, and its negative consequences. However, most AQM algorithms proposed so far, neglect the impact of the high speed and long delay links. As a result, the algorithms' efficiency, in terms of throughput and/or queue stability, is usually significantly decreased. The contribution of this paper is twofold. First of all, the performance of the well known AQM algorithms in high speed and long delay scenarios is evaluated and compared. Secondly, a new AQM algorithm is proposed, to improve the throughput in the large delay scenarios and to exclude the usage of random number generator.

PL

W obecnym Internecie odrzucanie bądź znakowanie pakietów ma na celu powiadomienie nadawcy o przeciążeniu. Ten fakt jest wykorzystywany przez źródła TCP w celu ograniczenia prędkości nadawania. Rozwiązaniem problemu pełnej kolejki jest prewencyjne odrzucanie pakietów, aby nie dopuścić do zapełnienia bufora i powstania przeciążenia. Prawdopodobieństwo prewencyjnego odrzucenia pakietu rośnie wraz ze wzrostem poziomu przeciążenia. Idea ta jest wykorzystywana w aktywnych algorytmach zarządzania kolejką. Prewencyjne odrzucanie pakietów wprowadza mechanizm sprzężenia zwrotnego informując nadawców o zbliżającym się przeciążeniu. Informacja jest wykorzystywana przez nadawców w celu zwolnienia szybkości nadawania. Losowe odrzucanie wybranych pakietów pozwala uniknąć sytuacji, w której wszystkie źródła zwalniają jednocześnie, co eliminuje problem globalnej synchronizacji. Większość obecnych algorytmów AQM pomija wpływ cech charakterystycznych dla łączy szkieletowych, tj. dużej przepustowości i dużych opóźnień propagacji. W rezultacie sprawność algorytmów AQM rozumiana jako przepustowość łącz i stabilność kolejki jest znacznie mniejsza niż w sieciach dostępowych. W pracy zaprezentowano badania wydajności popularnych algorytmów AQM w sieciach szkieletowych o dużych przepustowościach i dużych opóźnieniach propagacji. Wdalszej części przedstawiono propozycje algorytmu, który ma na celu poprawić przepustowość transmisji na tych łączach i który pozwala wykluczyć użycie generatora liczb losowych. Zaproponowana metoda - algorytm LINDROP - wykorzystuje niemalejącą funkcję liniową, w zależności od średniej długości kolejki, do oszacowania współczynnika odrzucania nadchodzących pakietów. Algorytm poprawia przepustowość w łączu szkieletowym.

Słowa kluczowe

EN

active queue management; large delay network; throughput

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2011
• Tom: Vol. 23, No. 1
• Strony: 3--20
• Opis fizyczny: Bibliogr. 28 poz., rys.

Twórcy

autor

Brachman A.

autor

Chrost Ł.

• Institute of Informatics Silesian University of Technology ul. Akadmicka 16, Gliwice, Poland

Bibliografia

• 1. The network simulator ns-2.
• 2. L. L. H. Andrew, S. Floyd, W. Gang: Common TCP evaluation suite, 6 Jul 2008.
• 3. S. Athuraliya, S.H. Low, V.H. Li, Q. Yin: REM: active queue management. Network,IEEE, 15(3):48 -53, May 2001.
• 4. B. Braden, D. Clark, J. Crowcroft, B. Davie, S. Deering, D. Estrin, S. Floyd, V. Jacobson,G. Minshall, C. Partridge, L. Peterson, K. Ramakrishnan, S. Shenker, J. Wroclawski, L.Zhang: RFC 2309: Recommendations on Queue Management and congestion avoidance in the Internet, April 1998. Status: INFORMATIONAL.
• 5. X. Chang, J. K. Muppala: A stable queue-based adaptive controller for improving AQM performance. Comput. Netw., 50:2204-2224, September 2006.
• 6. W.-C. Feng, K.G. Shin, D.D. Kandlur, D. Saha: The BLUE active queue management algorithms. Networking, IEEE/ACM Transactions on, 10(4):513-528, August 2002.
• 7. M. Christiansen, K. Jeffay, D. Ott, F. D. Smith: Tuning RED for web traffic. In in Proceedings of ACM SIGCOMM 2000, 139-150, 2000.
• 8. L. Chrost, A. Chydzinski: On the evaluation of the Active Queue Management mechanisms.In Evolving Internet, 2009. INTERNET ’09. First International Conference on,113-118, 2009.
• 9. G. Di Fatta, F. Hoffmann, G. Lo Re, A. Urso: A genetic algorithm for the design of a fuzzy controller for active queue management. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, 33(3):313-324, 2003.
• 10. W.-C. Feng, D.D. Kandlur, D. Saha, K.G. Shin: A self-configuring RED gateway. In INFOCOM ’99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 3, 1320-1328, March 1999.
• 11. V. Firoiu, M. Borden: A study of active queue management for congestion control. In INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 3, 1435-1444, March 2000.
• 12. S. Floyd, R. Gummadi, S. Shenker: Adaptive RED: An Algorithm for Increasing the Robustness of RED, 2001.
• 13. S. Floyd: Recommendation on using the "Gentle" variant of RED algorithm, March 2000.
• 14. S. Floyd, V. Jacobson: Random early detection gateways for congestion avoidance.IEEE/ACM Trans. Netw., 1:397-413, August 1993.
• 15. S. Guo, X. Liao, Ch. Li, D. Yang: Stability analysis of a novel exponential-RED model with heterogeneous delays. Comput. Commun., 30:1058-1074, March 2007.
• 16. C.V. Hollot, V. Misra, D. Towsley, W. Gong: Analysis and design of con-trollers for AQM routers supporting TCP flows. Automatic Control, IEEE Trans-actions on, 47(6):945-959, June 2002.
• 17. H. Jiang, C. Dovrolis: Passive estimation of TCP round-trip times. ACM Computer Communication Review, 32:75-88, 2002.
• 18. S.S. Kunniyur, R. Srikant: An adaptive virtual queue (AVQ) algorithm for active queue management. Networking, IEEE/ACM Transactions on, 12(2):286-299, 2004.
• 19. T. O. Lakshman, T. V. Lakshman, L. Wong: SRED: Stabilized RED. In Proceedings of INFOCOM, 1346-1355, 1999.
• 20. S.H. Low, F. Paganini, J. Wang, S. Adlakha, J.C. Doyle: Dynamics of TCP/RED and a scalable control. In INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 1, 239-248, 2002.
• 21. E. Plasser, T. Ziegler: A RED function design targeting link utilization and stable queue size behavior. Comput. Netw., 44:383-410, February 2004.