TRANSMISJA PAKIETÓW WSKAŹNIKI QoS - pojedynczy kanał

1 TRANSMISJA PAKIETÓW WSKAŹNIKI QoS - pojedynczy kanałZdz...

Author: Teresa Zielińska

0 downloads 2 Views

1 TRANSMISJA PAKIETÓW WSKAŹNIKI QoS - pojedynczy kanałZdzisław PAPIR Katedra Telekomunikacji © Zdzisław Papir

2 RUTER/PRZEŁĄCZNIK – SIEĆ PAKIETOWAWejściowe porty/bufory (kolejki) do przetwarzania Wyjściowe porty/bufory (kolejki) do transmisji Przetwarzanie i przekazywanie pakietów © Zdzisław Papir

3 SYMBOLIKA KENDALLA A/S/K/Nbufor kanał A S A - przybycia (Arrival), S - transmisja (Service) K - # kanałów, N - pojemność systemu A/S - M (Markov, Memoryless), D (Deterministic), G (General), E (Erlang), H (Hiperexponential), C (Cox), SS (Self-Similar) = LRD (Longe Range Dependent) Algorytm szeregowania – FCFS (FIFO), IS, PS, LCFS, priorytety, Round Robin, Fair Queueing © Zdzisław Papir

4 KOLEJKA M/M/1 j j - # pakietów (łącznie z transmitowanym)bufor kanał j - # pakietów (łącznie z transmitowanym)  - natężenie strumienia wejściowego 1/ - średni czas transmisji pakietu fgp odstępów czasu między pakietami fgp czasu transmisji pakietów © Zdzisław Papir

5 KOLEJKA M/M/1 – ewolucja w czasie i stan stacjonarny (ustalony)bufor kanał Ewolucja w czasie Stan stacjonarny t∞ © Zdzisław Papir

6 KOLEJKA M/M/1 – ewolucja w czasie i stan stacjonarny (ustalony)Ewolucja w czasie (proces Markowa) Stan stacjonarny t∞ (GBE – Global Balance Equations) © Zdzisław Papir

7 KOLEJKA M/M/1 - STAN STACJONARNY (Global Balance Equations)μ j 1 j-1 λ j+1 Σ strumienie_wej = Σ strumienie_wyj © Zdzisław Papir

8 KOLEJKA M/M/1 - STAN STACJONARNY (Global Balance Equations)SPOSOBY ROZWIĄZYWANIA: rekurencja (podejście bezpośrednie) Local Balance Equations (tylko systemy markowowskie) funkcja tworząca (transformata Z, dowolne systemy) © Zdzisław Papir

9 FUNKCJA TWORZĄCA Rozkład prawdopodobieństwa (dyskretny)© Zdzisław Papir

10 FUNKCJA TWORZĄCA - WŁAŚCIWOŚCIWarunek normalizacyjny Wartość średnia © Zdzisław Papir

11 FUNKCJA TWORZĄCA - WŁAŚCIWOŚCIPrawdopodobieństwa © Zdzisław Papir

12 FUNKCJA TWORZĄCA – KOLEJKA M/M/1© Zdzisław Papir

13 M/M/1 KOLEJKA ROZKŁAD PRAWDOPODOBIEŃSTWA2 3 4 5 6 7 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 j r = .2 r = .8 .8000 .2000 .1600 .0320 .1280 .0064 .1024 .0013 .0819 Rozkład geometryczny © Zdzisław Papir

14 KOLEJKA M/M/1 – średnia zajętość20 L 18 16 14 12 10 8 6 4  2 © Zdzisław Papir 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

15 KOLEJKA M/M/1 – średnia długość kolejki, średnia zajętość kanału (serwera) bufor kanał Q S L L = ρ /(1-ρ) - średnia zajętość Q - średnia długość kolejki = ? S - średnia zajętość kanału = ? aktualna przepustowość kanału = ? © Zdzisław Papir

16 KOLEJKA M/M/1 – parametry zależne od stanubufor kanał j - # pakietów (łącznie z pakietem w transmisji) j - natężenie strumienia wejściowego w stanie j 1/j - średni czas transmisji w stanie j © Zdzisław Papir

17 KOLEJKA M/M/1 – parametry zależne od stanuμ1 j 1 j-1 λ0 λj-1 λ1 λj μj μ2 μj+1 j+1 bufor kanał j Kolejka M/M/1 © Zdzisław Papir

18 KOLEJKA M/M/1 – parametry zależne od stanu (Global Balance Equations)μ1 j 1 j-1 λ0 λj-1 λ1 λj μj μ2 μj+1 j+1 Σ strumienie_wej = Σ strumienie_wyj © Zdzisław Papir

19 KOLEJKA M/M/1 – parametry zależne od stanu (rekurencja)© Zdzisław Papir

20 GLOBAL BALANCE EQUATIONSj λj-1 λj μj μj+1 j+1 Σ strumienie_wej (przybycie & transmisja) = = Σ strumienie_wyj (przybycie & transmisja) LOCAL BALANCE EQUATIONS λj λj-1 j μj μj+1 j+1 strumień_wej (przybycie) = = strumień_wyj (transmisja) © Zdzisław Papir

21 LOCAL BALANCE EQUATIONS (cd)strumień_wej (przybycie) = = strumień_wyj (transmisja) Oddzielnie dla każdej kolejki Oddzielnie dla każdego strumienia bufor kanał m, n Multipleksacja ruchu GBE?, LBE? Tandem kanałów GBE?, LBE? bufor kanał m n © Zdzisław Papir

22 KOLEJKA M/M/1 – parametry zależne od stanu (Local Balance Equations)rekurencja © Zdzisław Papir

23 KOLEJKA M/M/1 – parametry zależne od stanuZniechęcanie Infinite Server (IS) Kilka serwerów (s>1) Grupa użytkowników Bufor o skończonej pojemności © Zdzisław Papir

24 GLOBAL BALANCE EQUATIONS - przykładyΣ strumienie_wej (przybycie & transmisja) = = Σ strumienie_wyj (przybycie & transmisja) Kolejka M/M/1 z parametrami λ oraz µ. Serwer podejmuje pracę, gdy pojawi się kolejka dwóch zgłoszeń. Graf stanów oraz GBE? Kolejka M/M/1 zasilana przez dwa strumienie pakietów o natężeniu λ oraz γ (multipleksacja ruchu w buforze). Średni czas transmisji jest jednakowy dla obydwóch strumieni 1/µ. Graf stanów i GBE? bufor kanał m, n © Zdzisław Papir

25 Średnie opóźnienie tranzytoweKOLEJKA M/M/1 – średnie opóźnienie tranzytowe TWIERDZENIE LITTLE’a L W Strumień wejściowy Średnie opóźnienie tranzytowe Średnia zajętość Strumień wyjściowy Twierdzenie Little’a © Zdzisław Papir

26 TWIERDZENIE LITTLE’A – szkic dowoduD(t) A(t) A(t) D(t) t L(t) A(t) - # arrivals (0, t) D(t) - # departures (0, t) L(t) – zajętość systemu w chwili t © Zdzisław Papir

27 TWIERDZENIE LITTLE’A – szkic dowoduŁączne opóźnienie tranzytowe dla przedziału czasu (0,t) A(t) D(t) L(t) t średnia liczba zgłoszeń w czasie (0, t) średnie opóźnienie tranzytowe średnia zajętość w przedziale (0, t) © Zdzisław Papir

28 TWIERDZENIE LITTLE’A – szkic dowoduA(t) D(t) t L(t) Stan stacjonarny © Zdzisław Papir

29 KOLEJKA M/M/1 – średnie opóźnienie tranzytowe20 W 18 16 14 12 10 8 6 4   2 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 © Zdzisław Papir

30 KOLEJKA M/M/1 – optymalny punkt pracyPOWER COEFFICIENT Q © Zdzisław Papir

31 KOLEJKA M/M/1 – optymalny punkt pracyPOWER COEFFICIENT Q W optymalnym punkcie pracy (max Q) względne zmiany opóźnienia tranzytowego ∆W/W równoważą względne zmiany przepustowości ∆λ+/λ+. Zmiana punktu pracy nie jest korzystna – wzrost przepustowości ∆λ+/λ+ zostanie zrealizowany przez wzrost opóźnienia ∆W/W (i na odwrót). © Zdzisław Papir

32 KOLEJKA M/M/1 – optymalny punkt pracy0.05 0.1 0.15 0.2 0.25 () Właściwość () obowiązuje dla wszystkich systemów M/G/1; nie jest ważna dla systemów G/M/1. © Zdzisław Papir

33 JAKA MULTIPLEKSACJA RUCHU ?1. STATISTICAL TIME DIVISION MULTIPLEXING (STDM) KANAŁ TRANSMISYJNY C [pakiet/s] 2. FREQUENCY/TIME DIVISION MULTIPLEX PODKANAŁY C/N [pakiet/s] © Zdzisław Papir

34 KOLEJKA M/M/1/N – bufor o skończonej pojemnościj  N bufor kanał j < N j = N j ? © Zdzisław Papir

35 KOLEJKA M/M/1/N – bufor o skończonej pojemnościj  N bufor kanał j < N j = N j ? © Zdzisław Papir

36 KOLEJKA M/M/1/N – bufor o skończonej pojemności0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 0.1 0.3 0.5 0.7 0.9 N=11 N=7 N=3 N=  © Zdzisław Papir

37 KOLEJKA M/M/1/N – bufor o skończonej pojemnościBufory o skończonej pojemności są przyczyną strat ruchu, ale też – kosztem strat – powodują stabilizację opóźnienia. © Zdzisław Papir

38 KOLEJKA M/M/1/N – bufor o skończonej pojemności2 4 6 8 10 12 14 16 18 20 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 N © Zdzisław Papir

39 ZARZĄDZANIE PAMIĘCIĄ BUFOROWĄPamięć buforowa Kanał transmisyjny Zarządzanie pamięcią buforową: Podział pamięci pomiędzy strumienie Zasady usuwania pakietów z pamięci © Zdzisław Papir

40 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 © Zdzisław Papir

41 Akceptacja probabilistycznaAlgorytm RED - Random Early Discard Bufor RED Akceptacja probabilistyczna Akceptacja Odrzucenie Średnia długość kolejki © Zdzisław Papir

42 Opóźnienie kolejkowania QSZEREGOWANIE PAKIETÓW bufor kanał k Algorytm szeregowania FCFS Opóźnienie kolejkowania Q 1/ λ 1/ µ 1/ λ [s/pakiet] – średni odstęp czasu między pakietami 1/ µ [s/pakiet] – średni czas transmisji pakietu © Zdzisław Papir

43 SZEREGOWANIE PAKIETÓW (FCFS, FIFO)bufor kanał m, n Multipleksacja strumieni powoduje zmniejszenie dostępnej przepustowości. © Zdzisław Papir

44 SZEREGOWANIE PAKIETÓW (FCFS, FIFO)bufor kanał m bufor kanał n © Zdzisław Papir

45 SZEREGOWANIE PAKIETÓW (FCFS, FIFO)bufor kanał m bufor kanał n © Zdzisław Papir

46 SZEREGOWANIE PAKIETÓW Round Robin (RR)Algorytm karuzelowy (Round Robin – RR) zapewnia bardziej sprawiedliwy dostęp do kanału w porównaniu do algorytmu szeregowania FCFS (FIFO). © Zdzisław Papir

47 M/G/1 – FUNKCJA TWORZĄCA M/M/1 – FUNKCJA TWORZĄCAKOLEJKA M/G/1 bufor kanał M/G/1 – FUNKCJA TWORZĄCA M/M/1 – FUNKCJA TWORZĄCA © Zdzisław Papir

48 opóźnienie tranzytowe opóźnienie kolejkowaniaKOLEJKA M/G/1 bufor kanał W opóźnienie tranzytowe opóźnienie kolejkowania czas transmisji Wzór Pollaczka-Chinczyna: kolejkowanie © Zdzisław Papir

49 WZÓR POLLACZKA-CHINCZYNAKolejka M/G/1 opóźnienie tranzytowe zależy od dwóch pierwszych momentów fgp czasu transmisji opóźnienie tranzytowe nie zależy od kształtu fgp czasu transmisji opóźnienie tranzytowe rośnie ze wzrostem rozproszenia czas transmisji najkrótsze opóźnienie tranzytowe zapewnia system M/D/1 (stały czas transmisji) Kolejka M/D/1 Kolejka M/M/1 © Zdzisław Papir

50 WZÓR POLLACZKA-CHINCZYNA (interpretacja)czas transmisji opóźnienie kolejkowania M/D/1 dodatkowe opóźnienie kolej- kowania wynikające ze zmienności czasów transmisji © Zdzisław Papir

52 KOLEJKA G/G/1 Kolejka M/G/1 Kolejka G/G/1Wzrost zmienności (rozproszenie) strumienia pakietów oraz czasów ich transmisji powoduje nadmierny wzrost opóźnienia tranzytowego. © Zdzisław Papir

53 SAMOPODOBIEŃSTWO GEOMETRYCZNEObiekt samopodobny (geometrycznie) to obiekt, którego kształt jest taki sam jak kształt jego części. Samopodobieństwo jest charakterystyczną cechą fraktali. Fraktal to figura geometryczna, którą cechuje powtarzający się w nieskończoność wzorzec. Wacław Sierpiński Polski matematyk 700 artykułów i książek Dywan Sierpińskiego – przykład fraktala „How Long Is the Coast of Britain? Statistical Self-Similarity and Fractional Dimension” (przeczytaj artykuł) © Zdzisław Papir

58 SAMOPODOBIEŃSTWO STATYSTYCZNEParametr Hursta H samopodobieństwa statystycznego dotyczy samopodobieństwa procesów losowych na różnych skalach czasu. Parametr Hursta nie opisuje samopodobieństwa fraktali na różnych ich skalach. Harold Edwin Hurst (1880 – 1978) – brytyjski hydrolog. Hurst zajmował się badaniem zdolności retencyjnych zbiorników wodnych i wykrył hydrologiczne zjawisko dalekosiężnej korelacji (w szczególności dla fluktuacji poziomu wody w rzece Nil). Hurst opracował miarę zmienności szeregów czasowych dla różnych skal czasu (rescaled range methodology) pozwalającą wykrywać korelację dalekosiężną. Parametr (wykładnik) Hursta jest używany w teorii ruchu teleinformatycznego, finansach i kardiologii. © Zdzisław Papir

60 ruch samopodobny (selfsimilar) opóźnienie kolejkowaniaRUCH SAMOPODOBNY – KOLEJKA SS/M/1 bufor kanał ruch samopodobny (selfsimilar) Q opóźnienie kolejkowania Kolejka SS/M/1 (0.5 Kolejka M/M/1 (H = 0.5) © Zdzisław Papir

62 Parametr Hursta samopodobieństwo ruchuY(t) - proces zliczeniowy (niestacjonarny) jednostek ruchu (bitów, bajtów, pakietów) do (dyskretnego) czasu t = 1, 2,… Statystyczne samopodobieństwo ruchu zliczanego – ruch zliczony do czasu at jest taki sam jak zliczony do czasu t – przy założeniu przeskalowania wolumenu ruchu przez współczynnik a-H. Przyrosty (zmiana) ruchu X(t) – proces stacjonarny: E(X) = const, Var(X)=2. © Zdzisław Papir

63 Parametr Hursta samopodobieństwo ruchuProces zliczania ruchu na różnych skalach czasu s. Przyrosty (zmiana) ruchu X(t) – proces stacjonarny: E(X) = const, Var(X)=2: © Zdzisław Papir

64 Parametr Hursta samopodobieństwa ruchuPrzyrosty (zmiany) ruchu X(t), t = 1, 2,… są procesem odnowy – ciągiem identycznych i niezależnych zmiennych losowych. Jeżeli przyrosty (zmiany) ruchu X(t), t = 1, 2,… są niezależne, to ze wzrostem skali obserwacji ruchu s będziemy obserwować zanikające fluktuacje wolumenu ruchu. © Zdzisław Papir

65 Parametr Hursta samopodobieństwo ruchuRuch samopodobny – ruch zliczany skaluje się: Y(t) = a-HY(at). Fluktuacje ruchu samopodobnego (½ niezależne (H = ½) . Projektowanie regulatorów ruchu (traffic controls) dla ruchu samopodobnego (½ © Zdzisław Papir

67 PODSUMOWANIE Markowowski proces narodzin-śmierci o współczynnikach zależnych od stanu jest modelem różnych systemów kolejkowych istniejących w sieciach pakietowych. Znamy kilka metod rozwiązywania globalnych równań równowagi dla stanu stacjonarnego (równania lokalne, funkcja tworząca, rekurencja). Uniwersalne twierdzenie Little’a wiąże średnie wartości przepustowości, liczby zgłoszeń w systemie oraz opóźnienia tranzytowego. Power coefficient - kryterium QoS dla systemów kolejkowych integrujące przepustowość oraz opóźnienie. Im większa jest zmienność ruchu, tym większe są opóźnienia kolejkowania. © Zdzisław Papir

TRANSMISJA PAKIETÓW WSKAŹNIKI QoS - pojedynczy kanał

Recommend Documents