Wpływ mechanizmów protokołu TCP oraz algorytmów kolejkowania na transmisje danych w sieci Internet

• Autorzy: Domański A.

Identyfikatory

DOI

DOI: http://dx.doi.org/10.21936/si2017_v38.n1A.797

Warianty tytułu

Influence of the TCP mechanisms and queue management on Internet transsmision

• Języki publikacji: PL

Abstrakty

PL

Na początku istnienia Internetu, przy ówczesnych prędkościach transmisji, nikt nie był w stanie przewidzieć, że kiedyś będzie możliwy przesył dźwięku, obrazu oraz innych treści multimedialnych. Konsekwencje wynikające z projektu, który cechowała niezawodność i niski koszt połączenia, okazały się barierą, w momencie kiedy sieć Internet stała się dostępna niemal w każdym domu i w każdym miejscu na kuli ziemskiej. Naukowcy opracowujący w połowie lat 70. zeszłego wieku podstawy rodziny protokołów TCP/IP nie przewidzieli, jakie wyzwania dla tych protokołów przyniosą technologie i rozwiązania powstałe kilkanaście czy nawet kilkadziesiąt lat później. Najpoważniejszą aktualnie barierą okazał się by protokół internetowy IP (oparty na bezpołączeniowym modelu datagramowym). Model ten nie jest dobrym rozwiązaniem dla przesyłu danych wrażliwych na przepustowość, opóźnienie czy tez gubienie pakietów. Na szczęście struktura Internetu pozwalała na wprowadzanie zmian, które początkowo można implementować na niewielkim obszarze, a potem ewentualnie dane rozwiązania rozprzestrzenić. W celu dostosowania sieci do dzisiejszych potrzeb jej użytkowników stworzono wiele mechanizmów sieciowych, których zadaniem jest zapewnienie możliwie najlepszych parametrów połączeń w sieci. Najważniejsze elementy sterowania strumieniami ruchu sieciowego to: zarządzanie pakietami nadchodzącymi do węzła transmisyjnego, zarządzanie odrzucaniem pakietów w kolejce oraz zarządzane prędkością wysyłania pakietów przez nadajnik na poziomie protokołu transportowego. W miejsce standardowego podejścia do obsługi różnych strumieni według reguły „best efford” (kolejka FIFO), zaczęto wprowadzać algorytmy kolejkowania, umożliwiające podział łącza między równolegle odbywające się transmisje. Algorytmy te szeregują pakiety i wysyłają, zachowując pewną dyscyplinę kolejkowania (np. algorytmy WFQ, WRR, DRR, CBQ i inne). Poważnym problemem, który pojawił się wraz z rozwojem sieci Internet, były przeciążenia sieci. Objawiały się one brakiem miejsca w buforach wyjściowych routerów. Przepełnienie kolejek powoduje straty pakietów, a w następstwie retransmisje danych. Tradycyjne podejście zakładało odrzucanie nadchodzących pakietów z kolejki dopiero po przepełnieniu bufora. Zastosowanie mechanizmów aktywnego zarzadzania wprowadziło nowy sposób podejścia do tego zagadnienia. Zgodnie z regułami AQM możliwe jest wcześniejsze, prewencyjne odrzucanie pakietów. Mechanizmy te polegają na monitorowaniu stanu łącza poprzez śledzenie liczby danych w kolejce. Na tej podstawie podejmuje się decyzję o ewentualnym usunięciu nadchodzącego pakietu. Dodatkowo mechanizmy AQM wykorzystują pewne cechy protokołu TCP (mechanizm okna przeciążeniowego). Sposób działania mechanizmu kontroli przeciążeń jest prosty, a przez to bardzo skuteczny. Rozmiar okna przeciążenia zależny jest od liczby uzyskanych zwrotnych potwierdzeń i rośnie aż do momentu, gdy pewna porcja danych nie zostanie zaakceptowana. Odrzucenie w routerze nadchodzącego pakietu jest jednocześnie informacja dla nadawcy sugerująca zmniejszenie prędkości nadawania. W najpopularniejszych mechanizmach AQM prawdopodobieństwo odrzucenia pakietu rośnie wraz z zapełnieniem bufora. Na poziomie warstwy transportowej modelu warstwowego sieci Internet istnieją dwa protokoły – UDP i TCP. Protokół TCP jest nieporównywalnie bardziej złożony niż UDP. Większość internetowego ruchu odbywa się z wykorzystaniem protokołu TCP. Został on wyposażony m.in. w mechanizmy sterowania przepływem danych i pewnego dostarczania przesyłki do adresata. W protokół ten wbudowano również mechanizmy kontroli przeciążeń. Wraz z rozwojem Internetu mechanizmy te rozbudowywano o kolejne, coraz sprawniej przesyłające dane mechanizmy. Mechanizmów takich, dostosowanych do różnorodnych warunków sieciowych, jest kilkadziesiąt, z czego kilkanaście znalazło już swoje stałe miejsce w systemach operacyjnych komputerów.

EN

At the beginning of the Internet, the speed transmission does not allow to predict that it will ever be possible to transfer audio, video and other multimedia content. Consequences of the project, which was characterized by reliability and low cost of the connections proved to be a barrier at a time when the Internet became available in almost every home and in every place on the globe. Scientists developing in the 70s the base of the family of TCP/IP protocols not predicted the challenges for these protocols which bring technologies and solutions created several decades later. The most serious barrier appeared to be an Internet Protocol IP (Based on the connectionless datagram model). This model is not a good solution for the data bandwidth, delay or loosing packets sensitive transmissions. Fortunately, the structure of the Internet allowed to make changes, which initially can be implemented in a small area and then eventually spread to the larger areas. For adapt the network possibilities to the needs of its users a number of network mechanisms were created. The mission of this mechanisms is the best possible performance of the network links ensuring. The most important elements of the network traffic control are: the packets incoming management, the packets rejection in the queue, and the transmitter sending packets speed control at the transport protocol level. The standard queue behavior handle different streams according to the rule "best effort" (FIFO queue). Nowadays, the queuing algorithms that divide a link between parallel transmissions were introduced. This algorithms rank the packets preserving a queuing discipline (e.g. WFQ, WRR, DRR, CBQ). A major problem, which appeared with the development of the Internet was the network overload. They manifested by a lack of space in the routers queues. Queue overflow causes packet losses and consequently, the data retransmissions. The traditional approach implied rejection of incoming packets from the queue only after overflow. Mechanisms of active queue management introduced a new approach to this issue. According to the rules AQM earlier, preventive packet rejection is possible. These mechanisms depend on monitoring link status by monitoring the number of data in the queue. On this basis, the decision to remove the incoming packet is taken. In addition, AQM mechanisms use some TCP feature (congestion window mechanism). A congestion control method mechanism is simple, and therefore very efficient. Congestion window size is dependent on the number of received acknowledgments and grows until the sent data is accepted. Rejection of the incoming packet in the router is also an information for the sender suggesting a transmission speed reduction.The most popular AQM mechanisms increase the dropping packet probability with the queue length. In the Internet layer model there are two transport protocols UDP and TCP. TCP is incomparably more complex than UDP. The better part of Internet traffic uses the TCP protocol. TCP has the control data flow and control the correctness of the transmitted data mechanisms. Also congestion control mechanisms have been introduced in this protocol. With the development of the Internet the better congestion control mechanisms were created. Currently, there are dozens adapted to a variety of network conditions mechanisms. The control of the speed generation, acting efficiently under all reasonable network conditions is not a trivial problem. This feature of the transport protocol is extremely important in the era of heterogeneous network consisting of various transmission media (wireless, satellite, optical, or simply cable).

Słowa kluczowe

PL

algorytm sterowania; algorytm kolejkowania; TCP; AQM

EN

control algorithm; queue algorithm; TCP; AQM

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2017
• Tom: Vol. 38, nr 1A
• Strony: 1--245
• Opis fizyczny: Bibliogr. 87 poz.

Twórcy

autor

Domański A.

• Politechnika Śląska, Instytut Informatyki Gliwice, ul. Akademicka 16

Bibliografia

• J. Postel (Ed.), Transmission Control Protocol, RFC 793, 1981.
• V. Cerf, R. Khan, A Protocol for Packet Network Intercommunication, IEEE Transactions on communications, 1974.
• V. Cerf, Y. Dalal, Carl Sunshine, Specification of Internet transmission control program, RFC 675, 1974.
• V. Jacobson, R. Braden, D. Borman, TCP Extensions for High Performance, RFC 1323, 1992.
• M. Hassan, R. Jain, Wysoko wydajne Sieci TCP/IP, Helion 2004.
• W. Stevens, TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms, RFC 2001 ,1997.
• M. Allman, S. Floyd, C. Partridge, Increasing TCP's Initial Window, RFC 2414, 1998.
• M. Allman, V. Paxson, W. Stevens, TCP Congestion Control, RFC 2581, 1999.
• K. Wehrle, F. Pählke, H. Ritter, D. Müller, M. Bechler, The Linux Networking Architecture Design and Implementation of Network Protocols in the Linux Kernel, Prentice Hall 2004.
• S. Floyd, T. Henderson, A. Gurtov, The NewReno Modification to TCP's Fast Recovery Algorithm, RFC 3782, 2004.
• V. Jacobson, R. Braden, TCP Extensions for Long-Delay Paths, RFC 1072, 1988.
• M. Mathis, J. Mahdavi, S. Floyd, A. Romanow, TCP Selective Acknowledgment Options, RFC 2018, 1996.
• S. Floyd, J. Mahdavi, M. Mathis, M. Podolsky, An Extension to the Selective Acknowledgement (SACK) Option for TCP, RFC 2883, 2000.
• M. Gerla, M.Y. Sanadidi, R. Wang, A. Zanella, TCP Westwood: Congestion Window Control Using Bandwidth Estimation,Global Telecommunications Conference IEEE, 2001.
• S. Mascolo, C. Casetti, M. Gerla, M.Y. Sanadidi, R. Wang, TCP westwood: Bandwidth estimation for enhanced transport over wireless links, MobiCom '01 Proceedings of the 7th annual international conference on Mobile computing and networking, 2001.
• L. Brakmo, L. Peterson, TCP Vegas: End to end congestion avoidance on a global Internet, IEEE Journal on Selected Areas in Communication, 1995.
• S. Low, L. Peterson, L. Wang, Understanding Vegas: A Duality Model, Journal of ACM, 2002.
• O. Hellal, E. Altman, Analysis of TCP Vegas and TCP Reno, Telecommunication Systems, 2000.
• J.S. Ahn, P.B. Danzig, Z. Liu, L. Yan, Experience with TCP Vegas: emulation and experiment, ACM SIGCOMM Conference, SIGCOMM , 1995.
• N. Cardwell, B. Bak, A TCP Vegas Implementation for Linux, Report, 2004.
• L. Xu, K. Harfoush, I. Rhee, Binary Increase Congestion Control for Fast, Long Distance Networks, INFOCOM, Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, 2004.
• Y.T. Li, D.Leith, BicTCP Implemenation in Linux Kernels, report, 2004.
• P. Sarolahti, M. Kojo, K. Raatikainen, F-RTO: an enhanced recovery algorithm for TCP retransmission timeouts, ACM SIGCOMM Computer Communication Review, 2003.
• P. Sarolahti, M. Kojo, Forward RTO-Recovery (F-RTO): An Algorithm for Detecting Spurious Retransmission Timeouts with TCP and the Stream Control Transmission Protocol (SCTP), RFC 4138, 2005.
• P. Sarolahti, M. Kojo, K. Yamamoto, M. Hata, Forward RTO-Recovery (F-RTO): An Algorithm for Detecting Spurious Retransmission Timeouts with TCP, RFC 5682, 2009.
• R. Ludwig, A. Gurtov, The Eifel Response Algorithm for TCP, RFC 4015, 2005.
• K. Ramakrishnan, S. Floyd, D. Black, The Addition of Explicit Congestion Notification (ECN) to IP, RFC3168, 2001.
• S. Athuraliya, S.H. Low, V.H. Li, Q. Yin, REM: Active Queeue Management, The Magazine of Global Internetworking, 2001.
• P. McKenney, Stochastic fairness queueing, INFOCOM '90, Ninth Annual Joint Conference of the IEEE Computer and Communication Societies. The Multiple Facets of Integration. Proceedings, IEEE, 1990.
• K.J. Loh, I. Gui, K.C. Chua, Performance of a Linux implementation of class based queueing, Computer Communications and Networks, 1998.
• C. Fragouli, V. Sivaraman, M.B. Srivastava, Controlled multimedia wireless link sharing via enhanced class-based queuing with channel-state-dependent packet scheduling, INFOCOM '98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. 1998.
• N. Yin, M. Hluchyj, Analysis of the leaky bucket algorithm for on-off data sources, Global Telecommunications Conference, 1991.
• P. Tang, T. Tai, Network traffic characterization using token bucket model, INFOCOM '99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies, 1999.
• P. McKenney, Stochastic fairness queueing INFOCOM '90, Ninth Annual Joint Conference of the IEEE Computer and Communication Societies. The Multiple Facets of Integration, 1990.
• Źródła Linuksa w wersji 2.4.18.
• A. Sang, Z. Haifeng, S. Li, Weighted fairness guarantee for scalable DiffServ assured forwarding, ICC Communications, 2001.
• J. Nieminen, M. Luoma, O. Lamminen, A. Paju, Implementation and Simulation of DBHPD and CBQ scheduling - A Comparative Study, Implementation and Simulation of DBHPD and CBQ scheduling - A Comparative Study, ICC '07. IEEE International Conference on Communications, 2007.
• D. Clark, S. Shenker, L. Zhang, Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanism, SIGCOMM '92 Conference proceedings on Communications architectures & protocols, 1992.
• 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, Recommendations on queue management and congestion avoidance in the internet. RFC 2309, IETF, 1998.
• S. Floyd, V. Jacobson, Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on Networking, vol. 1, no. 4, 1993.
• E. Hashem, Analysis of random drop for gateway congestion control, Massachuset Institute of Technology, 1989.
• T. Ott, T. Lakshman, L. Wong, SRED: stabilized RED, INFOCOM '99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 1999.
• W. Feng, A. Arbor, D. Kandlur, D. Saha, K.G. Shin, A self-configuring RED gateway, INFOCOM '99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 1999.
• S. Floyd, V. Jacobson, Random early detection gateways for congestion avoidance. IEEE/ACM Transactions on Networking 1(4), 1993.
• S. Floyd, Discussions of setting parameters, http://www.icir.org/ floyd/ RED- parameters.txt, 1997.
• B. Zheng, M. Atiquzzaman, A framework to determine the optimal weight parameter of RED in next generation Internet routers. Technical report, The University of Dayton, Department of Electrical and Computer Engineering, 2000.
• M. May, T. Bonald, J. Bolot, Analytic evaluation of red performance. IEEE Infocom 2000, Tel-Aviv, Izrael, 2000.
• J. Domańska, A. Domański, D.R. Augustyn, J. Klamka, A RED modified weighted moving average for soft real-time application, International Journal of Applied Mathematics and Computer Science, Vol. 24, Issue 3, 2014.
• V. Jacobson, Random Early Detection (RED): Algorithm, Modeling and Parameters Configuration.
• S. Floyd, R. Gummadi, S. Shenker, Adaptive RED: An Algorithm for Increasing the Robustness of RED’s Active Queue Management, IEEE Transactions on Control Systems Technology, 2011.
• B. Zheng, M. Atiquzzaman, DSRED: An Active Queue Management Scheme for New Generation Network, Local Computer Networks, 2000.
• K. Zhou, K.L. Yeung, V. Li, Nonlinear RED: Asimple yet efficient active queue management scheme, Computer Networks 50, Elsevier 2006.
• D.R. Augustyn, A. Domański, J. Domańska, A Choice of Optimal Packet Dropping Function for Active Queue Management, Communications in Computer and Information Science, Springer-Verlag, vol. 79, 2010.
• J. Domańska, D.R. Augustyn, A. Domański, The choice of optimal 3-rd order polynomial packet dropping function for NLRED in the presence of self-similar traffic, Bulletin of the Polish Academy of Sciences, Technical Sciences vol. 60, 2012.
• R. Pan, B. Prabhakar, K. Psounis, CHOKe, A stateless AQM scheme for approximating fair bandwidth allocation, IEEE INFOCOM, 2000.
• Ch. Panninder, Ch. Shobhit, G. Anurag, J. Ajita, K. Abhishek, S. Huzur, S. Rajeev, XCHOKe: malicious source control for congestion avoidance at Internet gateways, ICNP 2002.
• A. Eshete, Y. Jiang, Generalizing the CHOKe flow protection, Computer Network Journal, 2012.
• D. Lin, R. Morris, Dynamics of Random Early Detection, SIGCOMM '97 Proceedings of the ACM SIGCOMM '97 Conference on applications, technologies, architectures, and protocols for computer communication, 1997.
• G. Chatron, M.A. Labrador, S. Banerjee, BLACK: Detection and Prererential Dropping High Bandwidth Unresponsive Flows, Communications, ICC '03. IEEE International Conference on, 2003.
• M. Farooq, M. Anjum, L. Tassiulas, Balanced-RED: An Algorithm to achieve Fairness in the Internet, Proc. IEEE INFOCOM '99, 1999.
• B. Wydrowski, M. Zukerman, GREEN: An active Queue Management Algorithm for a Self Managed Internet, ICC 2002. IEEE International Conference on, 2002.
• W. Feng, K.G. Shin, D.D. Kandlur, D. Saha, The BLUE Active Queue Management Algorithms, Networking, IEEE/ACM Transactions on, 2002.
• W. Feng, D.D. Kandlur, D. Sha, K.G. Shin, Stochastic Fair Blue: A Queue Management Algorithm for Enforcing Fariness, INFOCOM '01, Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 2001.
• J. Teunis, T.V. Ott, V. Lakshman, L. Wong, SRED: Stabilized RED, INFOCOM '99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 1999.
• K.H. Ang, G. Chong, PID Control System Analysis, Design, and Technology, IEEE Transactions on Control Systems Technology, 2005.
• K.H. Ang, Y. Li, PID control system analysis, design, and technology, Control Systems Technology, IEEE Transactions on, 2005.
• C.V. Hollot, V. Misra, D. Towsley, W.B. Gong, On Designing Improved Controllers for AQM Routers Supporting TCP Flows, in Proceedings of IEEE Infocom, 2000.
• J.L. Battaglia, O. Cois, J.C. Batsale, A. Oustaloup, La Dérivation Non Entière: Outil de Modélisation en Thermique. In Les Sysémes á Dérivées Non Entières: Théorie et Applications, volume 7. Alain Oustaloup and Michael Guglielmi, 2001.
• B.M. Vinagre, V. Feliu, Modeling and control of dynamic system using fractional calculus: Application to electrochemical processes and flexible structures. In Proceedings of 41st IEEE Conference on Decision and Control, Las Vegas, dec 2002.
• V. Zaborovsky, R. Meylanov. Informational network traffic model based on fractional calculus. In Proceedings of the International Conference on Info-tech and Info-net, Beijing, 2001. ICII 2001.
• W. Krajewski, U. Viaro, Fractional order PI controllers for TCP packet flow ensuring given modulus margins, Control & Cybernetics, 2014.
• P. Ostalczyk, P. Duch, D. Brzeziński, D. Sankowski. On the variable-fractional-order PID controller DSP realization problems. Proceedings of the FDA'12, 5th IFAC Workshop on Fractional Differentiation and its Applications., Nanjing, China, May 2012.
• A.K. Grünwald, Uber begrenzte Derivationen und deren Anwendung, Z.Angew.Math. Phys., 1867.
• R. Hilfer, editor. Application of Fractional Calculus in Physics. World Scientific, 2000.
• D. Sierociuk, Estymacja i sterowanie dyskretnych układów dynamicznych ułamkowego rzędu opisanych w przestrzeni stanu, Rozprawa doktorska, 2007.
• K. Kurata, G. Hasegawa, M. Murata, Fairness Comparisons Between TCP Reno and TCP Vegas for Future Deployment of TCP Vegas, 2000.
• https://simpy.readthedocs.org/
• V. Paxson, Fast approximate synthesis of fractional Gaussian noise for generating self-similar network traffic, ACM SIGCOMM Computer. 1997.
• C. Liu, R. Jain, Improving explicit congestion notification with the mark-front strategy. Computer Networks, 35(2-3), 2000.
• J. Domańska, A. Domański, T. Czachórski, The Drop-From-Front Strategy in AQM', Lecture Notes in Computer Science, vol. 4712/2007, Springer Berlin/Heidelberg, 2007.
• V. Misra, W.B. Gong, D. Towsley, Fluid-based Analysis of a Network of AQM Routers Supporting TCP Flows with an Application to RED, ACM SIGCOMM, 2000.
• C.V. Hollot, V. Misra, D. Towsley, A control theoretic analysis of RED, IEEE/INFOCOM, 2001.
• D.R. Augustyn, A. Domański, J. Domańska, Active Queue Management with non linear packet dropping function, Performance Modelling and Evaluation of Heterogenous Networks, 133-143, HET-NETs 2010.
• A. Domański, J. Domańska, T. Czachórski, Comparison of CHOKe and gCHOKe active queues management algorithms with the use of fluid flow approximation, Computer Networks, Communications in Computer and Information Science, vol. 370, Springer, 2013.
• L. Wang, Z. Li, Y.-P. Chen, K. Xue, Fluid-based stability analysis of mixed TCP and UDP traffic under RED, 10th IEEE International Conference on Engineering of Complex Computer Systems, 2005.
• J. Domańska, A. Domański, T. Czachórski, J. Klamka, Fluid flow approximation of time-limited TCP/UDP/XCP streams, Bulletin of the Polish Academy of Sciences: Technical Sciences, Vol. 62, 2014.
• S. Deering, R. Hinden, Internet Protocol, Version 6 (IPv6) Specification, RFC 2460, 1998.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017)