1 STEROWANIE RUCHEM METODĄ OKNA – SIEĆ PAKIETOWAZdzisław PAPIR Katedra Telekomunikacji

2 WINDOW FLOW CONTROL packets ack’ed packets sent, not ack’ed packetsto be sent SENDER RECEIVER packets sent window, credit CRD.RCV SENDER RECEIVER Mechanizm okna (kredytu) pozwala odbiorcy informacji dostosowywać tempo nadawania pakietów przez nadajnik do aktualnych możliwości przetwarzania nadawanych pakietów. Mechanizm okna ma też właściwości przeciwdziałania przeciążeniom sieci, gdyż ogranicza liczbę pakietów znajdujących się w sieci. © Zdzisław Papir

3 WINDOW FLOW CONTROL SENDER RECEIVER packets ack’s, creditPACKET NETWORK Zwracane potwierdzenia (ack’s) oraz szerokość okna (credit, window size) można traktować jak bufor przepustek. Pakiet może zostać wysłany tylko wtedy, gdy w buforze jest (wolna) przepustka. Liczba zgromadzonych przepustek powiększona o liczbę wysłanych, a jeszcze niepotwierdzonych pakietów jest równa aktualnej szerokości okna. SENDER RECEIVER packets PACKET NETWORK TOKEN BUFFOR © Zdzisław Papir

4 ZAMKNIĘTE SIECI KOLEJEK GORDON & NEWELL 1967jn jN j3 j2 µN = ? © Zdzisław Papir

5 MODEL KOLEJKOWY M/M/1/K - otwartybufor kanał j < K j = K j ? © Zdzisław Papir

6 MODEL KOLEJKOWY M/M/1/K - zamkniętybufor kanał j < K j ? j = K j  K j bufor pakietów γ γ j + i = K bufor przepustek i © Zdzisław Papir

7 Globalne równanie równowagiKOLEJKA M/M/1/K - otwarta  zamknięta Globalne równanie równowagi j i j + i = K γ = ? γ = ? © Zdzisław Papir

8 MODEL KOLEJKOWY M/M/1/K - zamkniętyj + i = K γ = ? γ = ? © Zdzisław Papir

9 ZAMKNIĘTE SIECI KOLEJEK GORDON & NEWELL 1967jn jN j3 j2 λ1 λ1 λ3 λ3 λn λn λN λN © Zdzisław Papir

10 ZAMKNIĘTE SIECI KOLEJEK GORDON & NEWELL 1967Ruting Wektor ruchu Bilans ruchu Sieć zamknięta Rozkład prawdopodobieństwa (postać iloczynowa) © Zdzisław Papir

11 ZAMKNIĘTE SIECI KOLEJEK STAŁA NORMALIZUJĄCA© Zdzisław Papir

12 ALGORYTMY SPLOTOWE © Zdzisław Papir Stała normalizującaZłożoność obliczeniowa algorytmu bezpośredniego sumowania w przestrzeni stanów Złożoność obliczeniowa algorytmu splotowego © Zdzisław Papir

13 ALGORYTMY SPLOTOWE STAŁA NORMALIZUJĄCA© Zdzisław Papir

14 ALGORYTMY SPLOTOWE STAŁA NORMALIZUJĄCA© Zdzisław Papir

15 ALGORYTMY SPLOTOWE STAŁA NORMALIZUJĄCAWartości początkowe: k pakietów jest zgromadzonych w jednym buforze (n = 1) k = 0 pakietów jest rozproszonych pomiędzy n buforów © Zdzisław Papir

16 ALGORYTMY SPLOTOWE ROZPŁYW STRUMIENIWektor ruchu Brak jednoznacznego rozwiązania; układ równań bilansu ruchu (rozpływu strumieni) jest układem równań liniowo zależnych. Bilans ruchu Rzeczywisty rozpływ strumieni © Zdzisław Papir

17 WINDOW FLOW CONTROL DOBÓR SZEROKOŚCI OKNAACK ACK © Zdzisław Papir

18 WINDOW FLOW CONTROL DOBÓR SZEROKOŚCI OKNAW (opóźnienie tranzytowe) ACK Zadanie optymalizacyjne Założenia („jednorodne” połączenie wirtualne): © Zdzisław Papir

19 WINDOW FLOW CONTROL DOBÓR SZEROKOŚCI OKNAW (opóźnienie tranzytowe) ACK Obserwacja: Każdy bufor jednorodnego połączenia wirtualnego zawiera w stanie stacjonarnym tę samą średnią liczbę pakietów/potwierdzeń Ln: © Zdzisław Papir

20 WINDOW FLOW CONTROL DOBÓR SZEROKOŚCI OKNAW (opóźnienie tranzytowe) ACK Twierdzenie Little’a Przepustowość © Zdzisław Papir

21 WINDOW FLOW CONTROL DOBÓR SZEROKOŚCI OKNAW (opóźnienie tranzytowe) ACK 1 2 N N+1  K Liczba R(K, N) rozmieszczeń K przedmiotów w N pojemnikach © Zdzisław Papir

22 WINDOW FLOW CONTROL DOBÓR SZEROKOŚCI OKNAACK Przepustowość © Zdzisław Papir

23 WINDOW FLOW CONTROL DOBÓR SZEROKOŚCI OKNAPrzepustowość Opóźnienie tranzytowe Power coefficient W jednorodnym połączeniu wirtualnym szerokość okna powinna być równa liczbie kanałów wchodzących w połączenie. © Zdzisław Papir

24 PODSUMOWANIE Zamknięte sieci kolejek służą do modelowania łączy wirtualnych w sieci pakietowej z mechanizmem okna. W najprostszym przypadku (jednorodne łącze wirtualne) szerokość okna powinna być równa liczbie kanałów transmisyjnych tworzących połączenie wirtualne. Dla zamkniętych sieci kolejek obowiązuje (podobnie jak dla sieci otwartych) iloczynowa postać rozkładu prawdopodobieństwa stanów. Określenie rozkładu prawdopodobieństwa stanów wymaga znajomości stałej normalizacyjnej rozkładu oraz rozpływu ruchu. W przypadku sieci złożonych stałą normalizacyjną oraz rozpływ ruchu wyznacza się za pomocą algorytmu splotowego redukującego liczbę obliczeń. © Zdzisław Papir