1 MATEMATYKA w ANALIZIE SIECI i SYSTEMÓW (Modelowanie sieci i usług)Zdzisław PAPIR Katedra Telekomunikacji Pok. 404, bud. D6 © Zdzisław Papir
2 WYKŁADY i ĆWICZENIA Modelowanie sieci i usługModele wykładnicze ruchu teleinformatycznego Proces Markowa w modelowaniu ruchu teleinformatycznego Transmisja pakietów – pojedynczy kanał Metryki QoS – pojedynczy kanał Metryki QoS – sieć pakietowa Sterowanie ruchem metodą okna – sieć pakietowa © Zdzisław Papir
3 EGZAMIN etc… Warunkiem dopuszczenia do egzaminu jest: 1. uzyskanie zaliczenia z ćwiczeń audytoryjnych oraz 2. zaliczenia z ćwiczeń laboratoryjnych. Zwolnienie z egzaminu od średniej oceny 4,0 z ćwiczeń audytoryjnych. Ocena końcowa jest wystawiana na podstawie wszystkich ocen ze złożonych egzaminów i zaliczeń zajęć wchodzących w skład przedmiotu. Studentowi przysługują trzy terminy egzaminu - jeden podstawowy oraz dwa poprawkowe. Nieusprawiedliwiona nieobecność powoduje utratę terminu egzaminu. © Zdzisław Papir 3
4 EGZAMIN etc… 6. Nie ma możliwości jednoczesnego złożenia egzaminu i uzyskania zaliczenia z ćwiczeń audytoryjnych; do egzaminu można przystąpić wyłącznie po uzyskaniu wszystkich zaliczeń. Brak zaliczenia skutkuje utratą wszystkich terminów egzaminów, które odbyły się przed uzyskaniem zaliczenia (brak zaliczenia nie usprawiedliwia nieobecności na egzaminie). 7. Egzamin jest przeprowadzany pisemnie – do rozwiązania są 3 (trzy) zadania. Każde zadanie jest oceniane w skali od 2,0 do 5,0. Ocenę 3,0 (dst) gwarantuje rozwiązanie 2 zadań. 8. Część zadań ma charakter rachunkowy, a część teoretyczny. Zadania dotyczą całości materiału z wykładów i ćwiczeń audytoryjnych. © Zdzisław Papir 4
5 EGZAMIN etc… 9. W trakcie egzaminu nie można korzystać z żadnych materiałów (notatki, podręczniki, skrypty, kserokopie) za wyjątkiem zestawu wzorów (A4) przygotowanego przez studentów. W trakcie egzaminu nie można korzystać z wyników uzyskanych przez innych studentów oraz w jakikolwiek sposób konsultować się z nimi. 10. W trakcie egzaminu telefony komórkowe oraz laptopy muszą być wyłączone. Student, który nie przestrzega postanowień zapisów pkt. 9 i 10, kończy egzamin z oceną 2,0 (niedostatecznie). Slajdy i inne materiały na dziekanat.agh.edu.pl. © Zdzisław Papir 5
6 LITERATURA Leonard Kleinrock Queueing Systems - Vol. I: TheoryQueueing Systems - Vol. II: Computer Applications John Wiley & Sons 1975 Dimitri Bertsekas, Robert Gallager Data Networks Prentice Hall 1993 Lester Lipsky Queueing Theory - A Linear Algebraic Approach University of Connecticut, 2008 © Zdzisław Papir
7 LITERATURA Moshe ZukermanIntroduction to Queueing Theory and Stochastic Teletraffic Models EE Department, City University of Hong Kong © Zdzisław Papir 7
8 LITERATURA Boudewijn R. HaverkortPerformance of Computer Communication Systems Wiley 1999 William Stallings High-Speed Networks: TCP/IP and ATM Design Principles Prentice Hall 1998 Zdzisław Papir Ruch telekomunikacyjny i przeciążenia sieci pakietowych WKiŁ 2001 © Zdzisław Papir
9 LITERATURA Jeremiah W. Hayes, Thimma V. J. Ganesh BabuModeling and Analysis of Telecommunications Networks Wiley 2004 Anurag Kumar, D. Manjunath, Joy Kuri Communication Networking – an Analytical Approach Elsevier 2004 Piet Van Mieghem Performance Analysis of Communications Networks and Systems Cambridge University Press 2006 © Zdzisław Papir
10 LITERATURA Hisashi Kobayashi, Brian L. MarkSystem Modeling and Analysis Pearson 2009 Fayez Gebali Analysis of Computer and Communication Networks Springer 2008 © Zdzisław Papir 10
11 MODELOWANIE SIECI i USŁUGteletraffic engineering performance evaluation Quality of Service (QoS) Quality of Experience (QoE) © Zdzisław Papir
12 DLACZEGO MODELUJEMY? Przewidywanie efektywności (jakości) (performance): aplikacji sieciowych (QoE) sieci transportowej (QoS) w celu: unowocześnienia sieci istniejącej zaprojektowania nowej sieci od podstaw © Zdzisław Papir
13 SPOSOBY MODELOWANIA Modele analityczne Modele numeryczneModele symulacyjne © Zdzisław Papir
14 ANALYTICAL vs. SIMULATION MODELS...blind, imitative simulation models are...a waste of time and money. To put it into a more diplomatic way, the return on investment is not nearly as high as on a simpler, analytic-type models. Alan Scherr, IBM, 1987 © Zdzisław Papir
15 ANALYTICAL vs. SIMULATION MODELSCommunication networks are engineering systems, so, as with other engineering systems, an analytical approach can be used for their study and design. Although qualitative heuristics can be used for simple networks, for high-speed, integrated services networks the quantitative approach can yield more efficient solutions (...) and important insights driving good heuristics. Communication Networking – an Analytical Approach, A. Kumar, 2006 © Zdzisław Papir
16 Zasada Pareto Zasada Pareto (zasada 80-20) stwierdza, że w rozmaitych kontekstach, jeżeli pewne zasoby są współdzielone w dużej populacji, to ok 20% of populacji przechwytuje 80% zasobów. 20 80 © Zdzisław Papir
17 Przykłady zasady Pareto20% klientów zapewnia 80% przychodów 20% kierowców powoduje 80% wypadków 30% pracowników dostarcza 80% produkcji 30% lektury tekstu zapewnia zrozumienie 60% problemu 10% studentów otrzymuje 90% bonusów studenckich (praktyki, wymiana Erasmus, stypendia) © Zdzisław Papir
18 Modelowanie efektywności (jakości) vs. zasada ParetoAnalityczne modelowanie jakości dotyczy wyznaczenia tych 10% badanego systemu, które wyjaśnia 90% jego zachowania. Boudewijn Haverkort University of Twente Performance of Computer Communication Systems: A Model-Based Approach © Zdzisław Papir
19 Modelowanie efektywności (jakości) vs. zasada ParetoWyznaczenie tych 10% właściwości systemu [które wyjaśnia 90% jego zachowania] często zabiera 90% czasu trwania zadania. Zdzisław Papir Akademia Górniczo-Hutnicza © Zdzisław Papir
20 RODZAJE STRUMIENI RUCHUAplikacje sieciowe przekazują dane różnego rodzaju: DŻWIĘK OBRAZ DANE WIDEO MULTI MEDIA © Zdzisław Papir
21 PRZEPŁYWNOŚCI STRUMIENI RUCHUTelefonia kb/s Dźwięk CD kb/s Transmisja tekstu 16 kb/page Grafika kb – 4 Mb Zdjęcia 2 Mb –16 Mb Telewizja MPEG 3 Mb - 6 Mb/s © Zdzisław Papir
22 OPÓŹNIENIA i STRATY w STRUMIENIACH RUCHUDANE+OBRAZ tekst grafika zdjęcia DŹWIĘK telefonia VoIP RUCH ELASTYCZNY (data streams) WIDEO telewizja VOD (ruch best-effort, wrażliwy na straty, niewrażliwy na opóźnienie) RUCH NIE- ELASTYCZNY (real-time streams) (ruch strumieniowy, wrażliwy na opóźnienia, niewrażliwy na straty) © Zdzisław Papir
23 PROFILE STRUMIENI RUCHUprzepływność opóźnienie/jitter straty TELEFONIA WIDEO DANE © Zdzisław Papir
24 INTEGRACJA w SIECI SZKIELETOWEJTELEFONIA DANE WIDEO Sieć szerokopasmowa z integracją usług BISDN Broadband Integrated Services Digital Network NGN Next Generation Network IP Integrated/Differentiated Services ATM Asynchronous Transfer Mode © Zdzisław Papir
25 METRYKI EFEKTYWNOŚCI Metryki aplikacji (QoE)Quality of Experience QoE = f(QoS) UŻYT- KOWNIK SERWER MODUŁ TRANSP. MODUŁ TRANSP. Metryki sieciowe (QoS) Quality of Service IP, ATM, FR... © Zdzisław Papir
26 METRYKI QoE QoE = {dostępność, funkcjonalność, jakość medium}Metody subiektywne (testerzy) Metody obiektywne (analiza obrazu) Full Reference No Reference MOS = Mean Opinion Score MOS = {znakomita=5, dobra=4, średnia=3, słaba=2, zła=1} © Zdzisław Papir
27 METRYKI QoS x – metryka QoS (opóźnienie, jitter, straty przepływność)wartość średnia E{x} odchylenie standardowe σx, σx/E{x} funkcja gęstości prawdopodobieństwa fgp(x) ewolucja w czasie fgp(x, t) © Zdzisław Papir
28 METRYKI QoS - SŁOWNIK STRATY PRZEPŁYWNOŚĆ OPÓŹNIENIE bit error ratepacket error rate packet loss PRZEPŁYWNOŚĆ bit rate, packet rate transfer rate bandwidth OPÓŹNIENIE transmission delay packet delay jitter, delay variation end-to-end delay round-trip delay latency transit delay © Zdzisław Papir
29 Sterowanie przepływem Protokoły łącza danychREGULATORY RUCHU (TRAFFIC CONTROLS) W SIECIACH PAKIETOWYCH Szeregowanie Kształtowanie ruchu Zarządzanie pamięcią Akceptacja ruchu Ruting QoS Użytkownik Serwer Sterowanie przepływem Protokoły łącza danych Przeciwdziałanie przeciążeniom © Zdzisław Papir
30 REGULATORY RUCHU (TRAFFIC CONTROLS) W SIECIACH PAKIETOWYCHsterowanie przepływem (flow control) przeciwdziałanie przeciążeniom (congestion control) dobór trasy (routing) kształtowanie ruchu (traffic policing) eliminacja błędów transmisji (error protection) szeregowanie pakietów (packet scheduling) akceptacja ruchu (call admission control) zarządzanie pamięcią (buffer management) © Zdzisław Papir
31 AKCEPTACJA RUCHU ? QoS QoS bufor kanałZasoby sieciowe (przepustowość oraz pamięć) są ograniczone. Algorytm akceptacji ruchu decyduje, czy: czy sieć może przyjąć nowy strumień do sieci zapewniając mu żądane parametry QoS, czy przyjęcie nowego strumienia do sieci nie spowoduje złamania gwarancji QoS dla strumieni już przesyłanych. © Zdzisław Papir
32 ALGORYTMY AKCEPTACJI RUCHUMeasurement-Based Admission Control (MBAC) Algorytmy stosowane dla źródeł ruchu, które nie potrafią określić profilu (opisu) emitowanego ruchu. Parameter-Based Admission Control (PBAC) Algorytmy stosowane dla źródeł ruchu, które potrafią określić profil (opis) emitowanego ruchu. algorytm deterministyczny algorytm probabilistyczny © Zdzisław Papir
33 AKCEPTACJA RUCHU Algorytm deterministycznyPorowata i nieregularna (bursty) struktura strumieni pakietów pozwala na to, aby sumaryczna wartość maksymalnych natężeń przesyłanych strumieni przekraczała przepustowość kanału. Algorytm probabilistyczny © Zdzisław Papir
34 Regularny ruch żetonów (przepustek)ALGORYTMY KSZTAŁTOWANIA RUCHU Cieknące wiadro Ruch chaotyczny Ruch regularny Regularny ruch żetonów (przepustek) Wiadro żetonów Ruch regularny + + zgęstki (bursts) Ruch chaotyczny Zadaniem kształtowania ruchu jest sprawdzanie, czy źródło ruchu zachowuje się zgodnie ze swoim profilem (ustalanym przy akceptacji ruchu) i ewentualne dostosowywanie emitowanego ruchu do profilu. © Zdzisław Papir
35 STEROWANIE PRZEPŁYWEM (OKNO, KREDYT)Window (credit) size CRD.RCV – liczba bajtów, które odbiorczy moduł TCP jest w stanie odebrać (w odniesieniu do właśnie potwierdzonego bajtu – ACK.RCV). bytes ack’ed bytes sent, not ack’ed to be sent bytes sent window, credit CRD.RCV © Zdzisław Papir
36 Przetwarzanie pakietówSZEREGOWANIE PAKIETÓW Zadaniem szeregowania pakietów jest ustalanie kolejności transmisji pakietów oczekujących w kolejkach rutera. Kolejki (porty) wejściowe Kolejki (porty) wyjściowe Przetwarzanie pakietów BUDOWA RUTERA © Zdzisław Papir
37 Algorytm FCFS First Come First Servedwspólne kolejkowanie, a zatem transmisja w kolejności przybyć dłuższe pakiety blokują krótsze pakiety niesprawiedliwy podział przepustowości prosta implementacja © Zdzisław Papir
38 Algorytm Round Robin (RR) Algorytm Fair Queuing (FQ)oddzielne kolejki dla strumieni cykliczne przeglądanie kolejek z kolejki pobierany jest tylko jeden pakiet agresywne strumienie są samo- istnie karane niesprawiedliwy podział przepustowości © Zdzisław Papir
39 Ważony algorytm RR A A A B B B B B B B A B B A B B A B B B α1 = 3α2 = 7 A A A B B B B B B B A B B A B B A B B B sprawiedliwy podział przepustowości długości pakietów muszą być znane © Zdzisław Papir
40 Algorytm PS Processor Sharingoddzielne kolejki cykliczne przeglądanie kolejek pobieranie pojedynczych bajtów penalizacja agresywnych strumieni sprawiedliwy podział przepustowości C/N brak możliwości implementacji © Zdzisław Papir
41 Ważony algorytm GPS Generalized Processor Sharingoddzielne kolejki cykliczne przeglądanie kolejek penalizacja agresywnych strumieni zróżnicowany podział przepustowości brak możliwości implementacji © Zdzisław Papir
42 Generalized Processor SharingImplementacje PS & GPS Processor Sharing Bit Round Fair Queuing Generalized Processor Sharing Weighted Fair Queuing © Zdzisław Papir
43 ZARZĄDZANIE PAMIĘCIĄ buforAlgorytm zarządzania pamięcią: - usuwanie pakietów, gdy bufor jest przepełniony (przepełnia się), - podział pamięci buforowej pomiędzy porty. © Zdzisław Papir
44 Algorytm Tail drop bufor pakiety są usuwane, gdy bufor jest zapełnionyprosta implementacja monopolizacja pamięci potencjalna eliminacja zgęstek pakietów tail drop to algorytm reaktywny – reaguje na przepełnienie, a nie przeciwdziała mu (algorytm proaktywny) © Zdzisław Papir
45 Algorytm Random drop on fullw przypadku przepełnienia buforu usuwany jest z niego losowo wybierany pakiet algorytm przeciwdziała monopolizacji pamięci Algorytm Drop front on full w przypadku przepełnienia buforu usuwany jest z niego pierwszy pakiet algorytm przeciwdziała monopolizacji pamięci Algorytmy drop rules reagują na przepełnienie (algorytmy reaktywne) Algorytmy proaktywne (RED) przeciwdziałają przeciążeniom © Zdzisław Papir
46 Akceptacja probabilistycznaAlgorytm RED - Random Early Discard Bufor RED Akceptacja probabilistyczna Akceptacja Odrzucenie Średnia długość kolejki © Zdzisław Papir
47 PODSUMOWANIE Modelowanie sieci i usług pozwala przewidywać ich jakość (efektywność), odpowiednio Quality of Service oraz Quality of Experience. Modele analityczne w porównaniu do modeli symulacyjnych pozwalają na bardziej dokładny wgląd w istotę zagadnienia. Jakość pracy sieci (Quality of Service) w sposób istotny zależy od: 1. profilu ruchu, 2. integracji usług oraz 3. regulatorów ruchu zastosowanych w sieci. Jakość pracy sieci (Quality of Service) wyznacza w dużej mierze jakość usług (Quality of Experience). Metryki QoS and QoE są zazwyczaj wartościami średnimi pewnych wielkości wyznaczanymi bądź z pomiarów, bądź z modeli (a wtedy z odpowiednich rozkładów prawdopodobieństwa). © Zdzisław Papir
48 SPRAWIEDLIWY DOSTĘP – prosty przykładbufor kanał Algorytm szeregowania FCFS Opóźnienie tranzytowe D λ [pakiet/s] – natężenie strumienia pakietów 1/ λ [s/pakiet] – średni odstęp czasu między pakietami µ [pakiet/s] – przepustowość kanału 1/ µ [s/pakiet] – średni czas transmisji pakietu © Zdzisław Papir
49 SPRAWIEDLIWY DOSTĘP – prosty przykładbufor kanał Multipleksacja strumieni powoduje zmniejszenie dostępnej przepustowości. © Zdzisław Papir 49
50 SPRAWIEDLIWY DOSTĘP – prosty przykładBez względu na to jak agresywny (zachłanny) jest strumień pakietów (co można wyrazić przez współczynniki /, / < 1), opóźnienia tranzytowe są identyczne. Strumienie agresywne uniemożliwiają sprawiedliwy dostęp do przepustowści kanału. © Zdzisław Papir
51 SPRAWIEDLIWY DOSTĘP – algorytm RRoddzielne kolejki dla strumieni cykliczne przeglądanie kolejek z kolejki pobierany jest tylko jeden pakiet agresywne strumienie są samo- istnie karane niesprawiedliwy podział przepustowości © Zdzisław Papir
52 SPRAWIEDLIWY DOSTĘP – algorytm RR (dwie kolejki)Stosunek czasów kolejkowania © Zdzisław Papir