REKLAMA


 

REKLAMA


 

Model stanowiska obsługi i kolejki Model stanowiska obsługi i kolejki

Przez sieci telekomunikacyjne, w tym Internet, przepływa w każdej chwili ogromna ilość informacji. Za każdym razem, gdy łączymy się z jakąś stroną internetową, do naszego komputera płynie przez sieć strumień bitów


Czachorski_Tadeusz

Autorem tekstu jest Tadeusz Czachórski
Instytut Informatyki Teoretycznej i Stosowanej, Polska Akademia Nauk, Gliwice
e-mail: Ten adres pocztowy jest chroniony przed spamowaniem. Aby go zobaczyć, konieczne jest włączenie w przeglądarce obsługi JavaScript.  

 

Prof. dr hab. inż. Tadeusz Czachórski jest dyrektorem IITiS PAN, naukowo zajmuje się modelowaniem i oceną efektywności systemów i sieci komputerowych oraz zagadnieniami Internetu następnej generacji.  


Teksty, obrazy, muzyka, filmy, rozmowy telefoniczne – wszystkie te treści przesyłane są cyfrowo. Poprzez sieć prowadzone są też rozproszone obliczenia, wymagające komunikacji między komputerami. Transmitowane bity są zorganizowane w większe jednostki ‒ pakiety ‒ zawierające prócz danych adres przeznaczenia. Nad ich prawidłowym transportem czuwają protokoły komunikacyjne, których zadaniem jest wykrycie ewentualnych przekłamań transmisji i znalezienie najlepszej drogi od nadawcy do odbiorcy, zazwyczaj przez wiele węzłów pośrednich.

 

Szybkie i niezawodne

 

Szybkość działania sieci sprawia, że między węzłami wciąż znajduje się w drodze wiele bitów i pakietów. Czas przesyłu od węzła do węzła łatwo obliczyć, znając odległości między nimi i prędkość światła w łączu. Nieznany jest natomiast czas oczekiwania w węźle.

 

Ruch pakietów w sieci można porównać do ruchu drogowego: drogami o różnej przepustowości płynie strumień pojazdów. Ruch ten jest mocno nieregularny: natężenie transmisji w ramach typowego połączenia wciąż zmienia się w czasie. Ponieważ do każdego węzła w sieci prowadzi wiele dróg, a węzeł działa jak przełącznik kierujący nadchodzące pakiety do swoich dróg wyjściowych, często zdarza się, że strumień pakietów wysyłanych w danym kierunku przekracza przepustowość łącza wyjściowego. Pakiety są wtedy kolejkowane ‒ zapamiętywane w buforach i wysyłane w miarę dostępności łącza. Podobnie jak w ruchu drogowym tworzą się „korki”: pakiety muszą czekać, zanim dalej ruszą w drogę. Oszacowanie czasu oczekiwania jest bardzo ważne ‒ użytkownik chce krótkiego i o małych wahaniach czasu transmisji.

 

Przykład zmian natężenia ruchu pakietów w czasie, pomiary w sieci IITiS PAN, oś pozioma: numer pakietu, oś pionowa: odstęp czasu w sekundach między kolejnymi pakietami

 

Równie ważna jest niezawodność transmisji. Gdy bufor kolejki pakietów jest pełen, nadchodzący pakiet nie zostanie zapamiętany. Często stosowany protokół internetowy TCP (Transmission Control Protocol) czuwa nad niezawodnością przesyłu: odbiorca potwierdza zwrotnie odbiór kolejnych pakietów, a jeśli tego nie zrobi, to pakiet jest wysyłany ponownie. Wprowadza to jednak dodatkowe opóźnienia, a czasem, przy transmisji „na żywo”, jest już niepotrzebne: pakiet, który nie dotarł w porę, wprowadził pewne zakłócenie w transmitowanym dźwięku lub obrazie i nie da się już tego naprawić. Ważne jest więc także utrzymanie takich warunków pracy sieci, by prawdopodobieństwo utraty pakietu było małe.

 

Węzły sieci mogą dzielić pakiety na bardziej i mniej uprzywilejowane i wysyłać najpierw te z wyższym priorytetem, zapewniając im wyższą jakość usług. Można też zarezerwować na całej drodze od nadawcy do biorcy pewną przepustowość łącz dla wybranego połączenia, choć z punktu widzenia efektywności całej sieci nie jest to dobre rozwiązanie. Zarządzający siecią operator musi szukać kompromisu: z jednej strony zależy mu na jak najlepszym wykorzystaniu zasobów sieci, a z drugiej wzrost wykorzystania sieci pogarsza jakość usług (rosną kolejki w węzłach, rośnie prawdopodobieństwo ich przepełnienia), co powoduje niezadowolenie klientów.

 

Zarządzanie kolejkami

 

Planowanie sieci oraz ich rozwój można wspomóc, uciekając się do modelowania. W przypadku sieci komputerowych i probabilistycznego opisu natężenia transmitowanego ruchu pomocna okazała się teoria kolejek. Podstawowy rozpatrywany tu model jest następujący: klienci nadchodzą do stanowiska obsługi w odstępach czasu, które są znaną (opisana pewnym rozkładem prawdopodobieństwa) zmienną losową, są szeregowani w oczekiwaniu na obsługę; czas obsługi jest również losowy. Trzeba określić rozkład długości kolejki, tj. prawdopodobieństwo, że kolejka jest pusta lub że znajduje się w niej 1, 2, ..., n klientów oraz rozkład prawdopodobieństwa czasu czekania w kolejce i prawdopodobieństwo przepełnienia kolejki o skończonej pojemności. Stanowiska obsługi można łączyć w sieć, określając w niej drogi klientów.

 

Modele kolejkowe były budowane dla różnych zastosowań. Prócz oczywistych: klientami są ludzie, a stanowiskiem obsługi np. pocztowe okienko czy kasa w supermarkecie, jest wiele innych interpretacji: klientami mogą być statki przybijające do nabrzeża portowego (czasem obsługi jest czas ich rozładunku), paczki nadsyłane do magazynu (czas obsługi to czas przechowywania ich w magazynie), samochody wjeżdżające na skrzyżowanie (czasem obsługi jest czas przejazdu przez skrzyżowanie). W telekomunikacji modele kolejkowe są stosowane od około 100 lat, od czasów gdy Erlang i Molina zastosowali je do opisu pracy central telefonicznych: centrala może obsłużyć jednocześnie określoną liczbę połączeń, klientami są rozmówcy nawiązujący połączenia, czas obsługi to czas rozmowy, trzeba określić prawdopodobieństwo, że wszystkie kanały są zajęte i klient nie będzie obsłużony. Dziś modele kolejkowe w telekomunikacji angażują coraz większe środki obliczeniowe ‒ interesują nas przecież ilościowe wyniki obliczeń odnoszące się do konkretnych sieci i ich parametrów. Społeczność zajmująca się problemami ruchu w Internecie jest ogromna ‒ są w niej organizacje prowadzące pomiary ruchu internetowego, instytucje i programy międzynarodowe i narodowe zmierzające do usprawnienia zasad transmisji zawartych w protokołach komunikacyjnych. Działa polski projekt Inżynieria Internetu Przyszłości, w którym pracuje dziewięć uczelni, instytutów PAN i innych instytucji naukowych.

 

Model węzła (routera) przełączającego pakiety

 

Instytut Informatyki Teoretycznej i Stosowanej PAN od 30 lat zajmuje się kolejkowymi modelami systemów i sieci komputerowych. Najczęściej stosowanymi metodami są łańcuchy Markowa, aproksymacja dyfuzyjna i aproksymacja ciągła. Łańcuchy Markowa to rodzaj procesu losowego, szczególnie łatwego w opisie matematycznym, ale problemem jest liczba niewiadomych i równań, które trzeba rozwiązać. Aproksymacja dyfuzyjna wykorzystuje analogie pomiędzy procesem dyfuzji a długością kolejki: równanie różniczkowe, opisujące położenie cząstki w ruchu dyfuzyjnym, może być wykorzystane do określenia rozkładu prawdopodobieństwa długości kolejki. Aproksymacja płynna jest uproszczoną wersją tej metody ‒ bierze pod uwagę tylko wartości średnie ‒ natężenia strumieni pakietów, ich rozmiarów i wynikających długości kolejek ‒ nie można za jej pomocą określić rozkładów prawdopodobieństwa. Stosowane w niej równania różniczkowe są jednak prostsze, a obliczenia mogą być przeprowadzone w rozsądnym czasie. Prócz modeli analitycznych można wykorzystywać komputerową symulację pracy protokołów i zachowania się kolejek.

 

Dzięki temu sieci stają się nie tylko coraz szybsze, lecz także coraz bardziej niezawodne.

 

 

Chcesz wiedzieć więcej?

Czachórski T. (1999). Kolejkowe modele w ocenie efektywności sieci i systemów komputerowych. Gliwice: Pracownia Komputerowa Jacka Skalmierskiego.
Hassan M., Jain R. (2004; 2010). Wysoko wydajne sieci TCP/IP. Gliwice: Helion.
Kobayashi H., Mark B.L. (2009). System Modeling and Analysis: Foundations of System Performance Evaluation. Prentice Hall.


© Academia nr 3 (31) 2012

 

 

Oceń artykuł
(0 głosujących)

Tematy

agrofizyka antropologia jedzenia antropologia kultury antropologia społeczna archeologia archeometalurgia architektura Arctowski arteterapia astrofizyka astronomia badania interdyscyplinarne behawioryzm biochemia biologia biologia antaktyki biologia płci biotechnologia roślin borelioza botanika chemia chemia bioorganiczna chemia fizyczna chemia spożywcza cywilizacja demografia edukacja ekologia ekologia morza ekonomia energia odnawialna etnolingwistyka etnomuzykologia etyka ewolucja fale grawitacyjne farmakologia filozofia finanse finansowanie nauki fizyka fizyka jądrowa gender genetyka geochemia środowiska geoekologia geofizyka geografia geologia geologia planetarna geoturystyka grafen historia historia idei historia literatury historia nauki historia sztuki humanistyka hydrogeologia hydrologia informatyka informatyka teoretyczna internet inżynieria inżynieria materiałowa inżynieria żywności język językoznawstwo kardiochirurgia klimatologia kobieta w nauce komentarz komunikacja kooperatyzm kosmologia kryptografia kryptologia kulinaria kultoznawstwo kultura lingwistyka literatura literaturoznawstwo matematyka medycyna migracje mikrobiologia mineralogia mniejszości etniczne mniejszości narodowe modelowanie procesów geologicznych muzykologia mykologia na czasie nauka obywatelska neurobiologia neuropsychologia nowe członkinie PAN 2017 oceanografia ochrona przyrody orientalistyka ornitologia paleobiologia paleogeografia paleontologia palinologia parazytologia PIASt politologia polityka społeczna polska na biegunach prawo protonoterapia psychologia psychologia zwierząt punktoza Puszcza Białowieska robotyka rozmowa „Academii” seksualność smog socjologia szczepienia sztuka technologia wieś w obiektywie wulkanologia zastosowania zdrowie zoologia zwierzęta źródła energii żywienie

Komentarze

O serwisie

Serwis naukowy prowadzony przez zespół magazynu Academia PAN.Academia Zapraszamy do przysyłania informacji o badaniach, aktualnie realizowanych projektach naukowych oraz imprezach popularyzujących naukę.

 

Dla użytkowników: Regulamin

Pliki cookies

Informujemy, że używamy ciasteczek (plików cookies) w celu gromadzenia danych statystycznych, emisji reklam oraz prawidłowego funkcjonowania niektórych elementów serwisu. Pliki te mogą być umieszczane na Państwa urządzeniach służących do odczytu stron, a korzystając z naszego serwisu wyrażacie Państwo zgodę na używanie cookies, zgodnie z aktualnymi ustawieniami przeglądarki.

Więcej informacji o celu używania i zmianie ustawień ciasteczek w przeglądarce: TUTAJ

Wydanie elektroniczne

Kontakt

  • pisz:

    Redakcja serwisu online
    Academia. Magazyn Polskiej Akademii Nauk
    PKiN, pl. Defilad 1, pok. 2110
    (XXI piętro)
    00-901 Warszawa

  • dzwoń:

    tel./fax (+48 22) 182 66 61 (62)

  • ślij:

    e-mail: academia@pan.pl