Narzędzia użytkownika

Narzędzia witryny


2016:krusek:start

Zaproszenie na obronę pracy doktorskiej

DZIEKAN i RADA WYDZIAŁU
INFORMATYKI, ELEKTRONIKI I TELEKOMUNIKACJI
AKADEMII GÓRNICZO-HUTNICZEJ im. ST. STASZICA W KRAKOWIE
zapraszają na
publiczą dyskusję nad rozprawą doktorską

mgr inż. Krzysztofa Ruska
Router interface as a queuing system with correlated service times
Dyskusja odbędzie się 18 maja 2016 roku o godz. 12:00 w Sali 1.19
pawilon D-17, ul. Kawiory 21, 30-059 Kraków
PROMOTOR: prof. dr hab. inż. Zdzisław Papir, Akademia Górniczo-Hutnicza im. Stanisława Staszica
PROMOTOR POMOCNICZY: dr inż. Lucjan Janowski, Akademia Górniczo-Hutnicza im. Stanisława Staszica
RECENZENCI: prof. dr hab. inż. Andrzej Chydziński, Politechnika Śląska
prof. dr hab. inż. Michał Pióro, Politechnika Warszawska
Z rozprawą doktorską i opiniami recenzentów można się zapoznać
w Czytelni Biblioteki Głównej AGH, al. Mickiewicza 30





Router interface as a queuing system with correlated service times


mgr inż. Krzysztof Rusek


Promotor: prof. dr hab. inż. Zdzisław Papir (AGH)
Promotor pomocniczy: dr inż. Lucjan Janowski (AGH)
Dyscyplina: Telekomunikacja


Rozprawa dotyczy modelowania interfejsu routera w celu obliczania charakterystyk kolejki. Głównym zadaniem przedstawionej analizy jest zbadanie architektury pamięci urządzenia oraz jej implikacja w modelach analitycznych. Wiele z istniejących badań odnosi się do modelu samego ruchu. Poprawność tych modeli wraz z modelem interfejsu rutera nie jest jednak tak często weryfikowana. Eksperymenty na rzeczywistym urządzeniu pokazują jednak, że nieprawidłowy model interfejsu może spowodować znaczne różnice między prawdopodobieństwem odrzucenia pakietu mierzonym na interfejsie fizycznym i pochodzącym z symulacji.

W rozprawie zaproponowano dokładny model interfejsu routera (router na bazie Cisco IOS o nie-rozproszonej architekturze), który zweryfikowano eksperymentalnie na fizycznym urządzeniu. Interfejs jest modelowany jako bufor ograniczony określoną liczbą pakietów (niezależnie od ich długości) a nie rozmiarem pamięci. Bufor ten jest opisany jako skończony system kolejkowy FIFO zasilany przez markowski proces zgłoszeń (MAP) z półmarkowski (SM) czasem obsługi (MAP/SM/1/b w notacji Kendalla). Takie założenia pozwalają uzyskać nowe wyniki analityczne dla charakterystyk kolejkowania pakietów. Wyznaczone zostały następujące charakterystyki: czas do przepełnienia bufora, lokalne natężenia strat, współczynnik strat oraz łączna liczba strat w danym przedziale czasowym. Przewidywania proponowanego modelu mogą być nawet kilka rzędów wielkości bliżej wyników symulacji w porównaniu do wyników dla systemu MAP/G/1/b.

Wyniki analizy zostały porównane z wynikami dla systemu o niezależnych czasach usługi oraz z symulacjami bazującymi na śladach ruchu. Proponowany model MAP/SM/1/B produkuje zawsze bardziej dokładne wyniki w porównaniu do poprzednich rozwiązań zakładających niezależne czasy obsługi. Jednakże stopień poprawy zmienia się znacząco w zależności od autokorelacji odstępów pomiędzy pakietami. W przypadku autokorelacji o dużym zasięgu, wpływ autokorelacji czasów obsługi na charakterystyki jest Podobna sytuację obserwuje się w wysoko obciążonych systemach. W przypadku umiarkowanego zasięgu autokorelacji odstępów pomiędzy pakietami poprawa dokładności po zastosowaniu modelu o skorelowanych czasach obsługi może sięgać kilku rzędów wielkości dla systemu o typowym rozmiarze bufora.

Przedstawione wyniki analityczne mogą pomóc w optymalizacji parametrów urządzeń dla różnych typów ruchu i dać wskazówki, jak poprawić ich konstrukcję, na przykład poprzez wprowadzenie mechanizmów kształtowania ruchu zmniejszającego negatywny wpływ autokorelacji długości pakietu na charakterystyki kolejek.

Postawiono następującą tezę:

The interface of the network device whose buffer can accommodate a certain number of packets regardless of their length can be modeled as a queuing system MAP/SM/1/b with autocorrelated service times. It is possible to solve the model analytically and calculate selected transient and stationary queue characteristics

W tłumaczeniu na język polski teza brzmi następująco:

Interfejs urządzenia sieciowego, którego bufor może pomieścić określoną liczbę pakietów bez względu na ich długość, można modelować jako system kolejkowy MAP/SM/1/b o skorelowanych czasach obsługi. Dla takiego modelu możliwe jest wyznaczenie wybranych charakterystyk kolejkowania pakietów w stanie przejściowym i ustalonym.

Najważniejsze osiągnięcia pracy można streścić w następujących punktach:

  1. Wyczerpująca analiza stanu wiedzy na temat modelowania skończonych buforów.
  2. Zaprojektowanie eksperymentu do zbadania mechanizmu kolejkowania w interfejsie routera.
  3. Uogólnienie metody potencjału na systemy o skorelowanych czasach obsługi.
  4. Procedury numeryczne do użycia mieszanek rozkładów w metodzie potencjału.
  5. Wyprowadzenie zależności na proces strat w systemie MAP/SM/1/B.
  6. Wyprowadzenie zależności na rozkład czasu do przepełnienia bufora w systemie MAP/SM/1/B.
  7. Implementacja procedur numerycznych do wyznaczania charakterystyk kolejek.
  8. Porównanie dokładności systemów MAP/SM/1/B i MAP/G/1/B jako modeli interfejsu rutera.


Dłuższa wersja autoreferatu tutaj.



Recenzje


prof. dr hab. inż. Andrzej Chydziński

prof. dr hab. inż. Michał Pióro




Ważniejsze publikacje dokotoranta:

  1. K. Rusek, L. Janowski, and Z. Papir. Correct router interface modeling. In Proceedings of the second joint WOSP/SIPEW international conference on Performance engineering, ICPE ’11, pages 97–102, 2011. ISBN 978-1-4503-0519-8
  2. K. Rusek, Z. Papir, and L. Janowski. MAP/SM/1/b model of a store and forward router interface. In Performance Evaluation of Computer and Telecommunication Systems (SPECTS), 2012 International Symposium on, pages 1–8, 2012
  3. K. Rusek, L. Janowski, and Z. Papir. Transient and stationary characteristics of a packet buffer modelled as an MAP/SM/1/b system. International Journal of Applied Mathematics and Computer Science, 24(2):429–442, 2014
  4. K. Rusek and Z. Papir. Analiza pojemnosci bufora i skali czasu autokorelacji ruchu. Przeglad Telekomunikacyjny, Wiadomosci Telekomunikacyjne, 8–9/2015:730–732, 2015




2016/krusek/start.txt · ostatnio zmienione: 2016/05/04 10:58 przez Krzysztof Rusek