Dokument: Opis protokołu na zadanie zaliczeniowe z sik w roku 2007/2008 Autor: Konrad Błachnio Kodowanie: utf8 Koniec lini: Linux === Streszczenie === Na początku opiszemy podstawowe pojęcia potem cele naszego protokołu i ustalimy założenia, po czym opiszemy komunikację i stany. === Podstawowe pojęcia === * kolejka zdalna - kolejka uniksowa pracująca na maszynie odbiorcy. * kolejka transmisyjna - bufor po stronie nadawcy, implementowany przez agenta wysyłającego. * kanał transmisyjny - implementowany w postaci dwóch procesów, agentów kanałowych (oznaczanych jako MCA), jednego dla strony wysyłającej i jednego dla strony odbierającej. === Cele === 1. Protokół ma obsługiwać wszystkie funkcje z opisu zadania. 2. Prostota implementacji. 3. Pewne dodatkowe funkcjonalności nie opisane w zadaniu wpływajace na wydajność protokołu. === Założenia === 1. Dla każdego kanału transmisyjnego tworzymy nowe połączenie TCP i zrywamy po zakończeniu przesyłania danych. 2. Na jednej maszynie może działać tylko jeden MCA nadający i/lub jeden MCA odbierający. Rozszerzenie zadania: 2.*Na jednej maszynie może działać tylko jeden MCA odbierający ale dużo MCA wysyłających związanych z różnymi kolejkami. 3. Różne długości komunikatów. 4. Protokół działa w warstwie aplikacji. === Format komunikatów === Jak było wspomniane w założeniach, komunikaty będą miały zmienną długość. Niezależnie od komunikatu, format pierwszych czterech pól komunikatu będzie wyglądał następująco: uint32 odbierającyIP uint32 wysyłającyIP uint16 typ octet [4] key Przyjmujemy sieciową kolejność octetów w polach typu uint16 i uint32. W każdym komunikacie pola odbierającyIP zawiera numer IP MCA który otrzymał komunikat, pole wysyłającyIP zawiera numer IP MCA który wysłał komunikat. W polu typ zamieszczamy typ komunikatu - jedną ze stałych Timeout = Zależne od implementacji ale >= 10 K_Pytanie = 1 K_NieMa = 2 K_Wolna = 3 K_Zajęta = 4 K_Potwierdzenie = 5 K_Pewna = 6 K_Niepewna = 7 W polu key zamieszczamy identyfikator kolejki której dotyczy wysyłany komunikat. Komunikaty zawierające stałą K_Potwierdzenie, K_Pewna i K_Niepewna będą zawierały pole piąte o formacie następującym octet [4] ident Pole ident jest to unikalny identyfikator wiadomości. Aplikacja wygenerowuje pole ident dla każdej wiadomośći jest to czas systemowy, jednak forma tej informacji jest poza zakresem niniejszego dokumentu. Ponadto komunikaty zawierające stałe K_Pewna i K_Niepewna będą zawierały szóste pole oraz siódme zmiennej długości uint32 rozmiar octet[rozmiar/8 + 1] dane Pole rozmiar będzie zawierało rozmiar przesyłanych danych w bitach. Pole dane będzie siegało do końca komunikatu i będzie zawierało dane przesyłane do zdalnej kolejki. Podsumowanie typów wiadomości i formatów: Pierwszy rodzaj: typ = K_Pytanie format = [odbierającyIP, wysyłającyIP, typ, key] typ = K_NieMa format = [odbierającyIP, wysyłającyIP, typ, key] typ = K_Wolna format = [odbierającyIP, wysyłającyIP, typ, key] typ = K_Zajęta format = [odbierającyIP, wysyłającyIP, typ, key] Drugi rodzaj: typ = K_Potwierdzenie format = [odbierającyIP, wysyłającyIP, typ, key, ident] Trzeci rodzaj: typ = K_Pewna format = [odbierającyIP, wysyłającyIP, typ, key, ident, rozmiar, dane] typ = K_Niepewna format = [odbierającyIP, wysyłającyIP, typ, key, ident, rozmiar, dane] === Wymieniane komunikaty === 1)Komunikat pierwszego rodzaju z polem typ równym stałej K_Pytanie wysyła MCA wysyłający do MCA odbierającego. W pole odbierającyIP wpisuje numer IP MCA odbierającego, w pole wysyłającyIP wpisuje swój numer IP, w pole key wpisuje klucz kolejki do której ma byc wysłana wiadomość. Tą wiadomość rozsyła się po to aby dowiedzieć się gdzie jest dostepna kolejka z interesującym nas kluczem. 2)Komunikat pierwszego rodzaju z polem typ równym stałej K_NieMa wysyła MCA odbierający do MCA wysyłającego. W pole odbierającyIP wpisuje numer IP MCA wysyłającego, w pole wysyłającyIP wpisuje swój numer IP, w pole key wpisuje klucz kolejki dla której przyszła wiadomość ze stałą K_Pytanie. Tą wiadomość wysyła się po to aby oznajmić, że my nie posiadamy kolejki o podanym kluczu. 3)Komunikat pierwszego rodzaju z polem typ równym stałej K_Wolna wysyła MCA odbierający do MCA wysyłającego. W pole odbierającyIP wpisuje numer IP MCA wysyłającego, w pole wysyłającyIP wpisuje swój numer IP, w pole key wpisuje klucz kolejki dla której przyszła wiadomość ze stałą K_Pytanie. Tą wiadomość wysyła się po to aby oznajmić, że posiadamy kolejkę o podanym kluczu i jesteśmy gotowi aby odebrać dla niej dane. 4)Komunikat pierwszego rodzaju z polem typ równym stałej K_Zajęta wysyła MCA odbierający do MCA wysyłającego. W pole odbierającyIP wpisuje numer IP MCA wysyłającego, w pole wysyłającyIP wpisuje swój numer IP, w pole key wpisuje klucz kolejki dla której przyszła wiadomość ze stałą K_Pytanie. Tą wiadomość wysyła się po to aby oznajmić, że posiadamy kolejkę o podanym kluczu ale nie jesteśmy gotowi aby odebrać dla niej dane. 5)Komunikat drugiego rodzaju z polem typ równym stałej K_Potwierdzenie wysyła MCA odbierający do MCA wysyłającego. W pole odbierającyIP wpisuje numer IP MCA wysyłającego, w pole wysyłającyIP wpisuje swój numer IP, w pole key wpisuje klucz kolejki dla której przyszła wiadomość trzeciego rodzaju ze stałą K_Pewna a w pole ident identyfikator wiadomości która jest potwierdzana. Tą wiadomość wysyła się po to aby oznajmić, że poprawnie odebraliśmy wiadomość trzeciego rodzaju ze stałą K_Pewna. 6)Komunikat trzeciego rodzaju z polem typ równym stałej K_Pewna wysyła MCA wysyłający do MCA odbierającego. W pole odbierającyIP wpisuje numer IP MCA odbierającego, w pole wysyłającyIP wpisuje swój numer IP, w pole key wpisuje klucz kolejki do której ma byc wysłana wiadomość, w pole ident wpisuje się obecny czas systemowy, w pole rozmiar rozmiar przesyłanych danych w bitach, w pole dane wpisuje się dane do przesłania. Tą wiadomość wysyła się po to aby przekazać wiadomość z piorytetem K_Pewna do odpowiedniego MCA odbierającego który na nią czeka i musi ją potwierdzić. 7)Komunikat trzeciego rodzaju z polem typ równym stałej K_Niepewna wysyła MCA wysyłający do MCA odbierającego. W pole odbierającyIP wpisuje numer IP MCA odbierającego, w pole wysyłającyIP wpisuje swój numer IP, w pole key wpisuje klucz kolejki do której ma byc wysłana wiadomość, w pole ident wpisuje się obecny czas systemowy, w pole rozmiar rozmiar przesyłanych danych w bitach, w pole dane wpisuje się dane do przesłania. Tą wiadomość wysyła się po to aby przekazać wiadomość z piorytetem K_Niepewna do odpowiedniego MCA odbierającego który na nią czeka ale nie będzie jej potwierdzał. === Opis Stanów === I - MCA wysyłający ==>(*) {Wczytałem nie dobrą wiadomość} | +--------+ | | | \ / \ / | +-------------------+-----+ {K_Potwierdzenie?} +-------->| CZYTANIE Z BUFORA |<------------------------------------+<--------------------+ | +-------------------+ / \ | {x==K_Niepewna && | | | {K_Niepewna!} | kolejka==NULL} | | {x = wiadomość?} | | | \ / | | | +-----------------------------+ +----------------------+ | +------| SZUKANIE KOLEJKI ODBIORCZEJ |----------------------->| WYSYŁANIE WIADOMOŚCI | | +-----------------------------+ {kolejka!=NULL}} +----------------------+ | | | | | {x==K_Pewna && kolejka==NULL} | {K_Pewna!} | \ / \ / | +--------+ +---------------------------+ | | KONIEC |<---------------------------------| CZEKANIE NA POTWIERDZENIE |---+ +--------+ {Timeout} +---------------------------+ Co się dzieje w każdym stanie: CZYTANIE Z BUFORA - w tym stanie czekamy aż w buforze pojawis się wiadomość. Gdy pojawi się wiadomość Sprawdzamy czy wiadmość ma poprawny format jeśli nie to wrzucamy ją do kolejki dead.letter.q o ile istnieje. W przeciwnym przypadku przechodzimy do SZUKANIE KOLEJKI ODBIORCZEJ. SZUKANIE KOLEJKI ODBIORCZEJ - w tym stanie wysyłamy wiadomości do MCA odbierających ze znanej nam listy adresów. Nie wysyłamy kolejnej wiadomośći dopuki nie dostaliśmy odpowiedzi od poprzedniego MCA odbierającego lub nie minął czas równy Timeout. Wiadomość jest pierwszego formatu, w polu typ mamy stałą K_Pytanie a w polu key identyfikator kolejki. Jeśli nie dostaliśmy odpowiedzi zwrotnej od żadnego MCA - odbierającego, bądź wszystkie odpowiedzi miały format pierwszy ze stałą K_Niema w polu typ i odpowiednim identyfikatorem w polu key, wrzucamy taką wiadomośc do kolejki dead.letter.q i przechodzimy do CZYTANIE Z BUFORA jeśli była to wiadomość niepewna, lub przechodzimy do stanu KONIEC jeśli była to wiadomość pewna. Jęśli otrzymaliśmy wiadomość formatu pierwszego ze stałą K_Wolna w polu typ i odpowiednim identyfikatorem w polu key,przechodzimy do stanu WYSYŁANIE WIADOMOŚCI. Gdy otrzymaliśmy natomiast jakąś wiadomość formatu pierwszego ze stałą K_Wolna w polu typ i odpowiednim identyfikatorem w polu key, odczekujemy czas 2*Timeout i wysyłamy zapytanie ponownie. WYSYŁANIE WIADOMOŚCI - Wiemy który MCA odbierający dysponuje kolejką nam potrzebną więc w zależnośći od tego czy nasza wiadomość jest pewna czy niepewna wysyłamy trzeci rodzaj wiadomości z odpowiednią stałą w polu typ, identyfikatorem kolejki w polu key, czasem systemowym w polu ident oraz zawartością wiadomośći w polu dane. Jeśli była to wiadomość o typie K_Niepewna wtedy przechodzimy do stanu CZYTANIE Z BUFORA, w przeciwnym przypadku przechodzmy do stanu CZEKANIE NA POTWIERDZENIE. CZEKANIE NA POTWIERDZENIE - W tym stanie czekamy czas Timeout na wiadomość drugiego rodzaju z odpowiednio ustawionym polem typ oraz ident, takim samym jak w wysyłanej wiadomości. Jeśli w czasie Timeout wiadomość nie nadejdzie, wtedy przechodzimy do stanu KONIEC w przeciwnym przypadku przechodzimy do stanu CZYTANIE Z BUFORA. KONIEC - W tym stanie wrzucamy do kolejki dead.letter.q aktualnie obrabianą wiadomość i kończymy działanie. *Dodatkowa funkcjonalność optymalizacyjna poza zakresem zadania obejmuje dwa aspekty: 1)W każdym stanie może do nas nadejśc wiadmość typu pierwszego ze stałą K_Nie ma w polu typ i identyfikatorem kolejki w polu key. W takim przypadku należy uaktualnić stan wiedzy dotyczący kolejki o identyfikatorze równym key i MCA odbierającym o adresie IP równym wysyłający IP na stan w którym dany MCA odbierajacy nie posiada danej kolejki. 2)Rozszerzenie funkconalności stanu SZUKANIE KOLEJKI ODBIORCZEJ w ten sposób, że najpierw sprawdzamy czy w naszej bazie wiedzy o kolejkach i MCA odbierających istnieje wpis dotyczący kolejki nas interesującej. Jeśli taki wpis istnieje to w pierwszej kolejności odpytujemy danego MCA odbierającego który ma mieć kolejkę o szukanym identyfikatorze. II - MCA odbierający ==>(*) {komunikat niepoprawny} | +------+ | | | \ / \ / | +-----------------------+----+ +---------------------------->| CZEKANIE NA KOMUNIKAT |<----------------------------+ | +-----------------------+ | | | | | {K_Pytanie?} | | | \ / | | +------------------------+ {K_NieMa!} | | | ODPOWIEDŹ NA KOMUNIKAT |---------------------------->+ | +------------------------+ / \ | | | | {K_Wolna!} | +---+{K_NieMa! || K_Zajęta!} | | \ / \ / | | | {Timeout} +-----------------------+--+ | +<----------------------------| CZEKANIE NA WIADOMOŚĆ | | / \ +-----------------------+ | | | | | {x = wiadomość?} | | | \ / | | +----------------------+ | +------------------------------| REAKCJA NA WIADOMOŚĆ |-----------------------------+ {if x==K_Niepewna} +----------------------+ {if x==K_Pewna then K_Potwierdzenie!} Rozróżniamy tutaj komunikat od wiadomości. Komunikat jest to pakiet danych o formacie pierwszego rodzaju ze stałą typ równą K_Pytanie. Wiadomość jest to pakiet danych o formacie trzeciego rodzaju. Nie przewiduje się aby MCA odbierający otrzymywał pakiety danych w formacie drugiego rodzaju. Co się dzieje w każdym stanie: CZEKANIE NA KOMUNIKAT - w tym stanie czekamy aż przydzie do nas jakikolwiek pakiet danych. Gdy pojawi się pakiet danych sprawdzamy czy jest to komunikat. Jeśli nie wtedy wrzucamy pakiet do kolejki dead.letter.q o ile istnieje. W przeciwnym przypadku przechodzimy do stanu ODPOWIEDŹ NA KOMUNIKAT ODPOWIEDŹ NA KOMUNIKAT - tutaj sprawdzamy wsród kolejek nam podlegających czy isnieje kolejka o identyfikatorze równym key z komunikatu który przyszedł. Jeśli nie wtedy wysyłamy odpowiedź jako pakiet danych o formacie pierwszego rodzaju ze stałą K_NieMa i przechodzimy do stanu CZEKANIE NA KOMUNIKAT. W przeciwnym przypadku wysyłamy pakiet danych o formacie pierwszego rodzaju ze stałą K_Wolna i przechodzimy do stanu CZEKANIE NA WIADOMOŚĆ. CZEKANIE NA WIADOMOŚĆ - w tym stanie czekamy na wiadomość o polu key równym wartości key z komunikatu który dostaliśmy wcześniej, przez czas równy Timeout. Po tym czasie jesli nie otrzymaliśmy odpowiedzniej wiadomości przechodzimy do stanu CZEKANIE NA KOMUNIKAT. Jeśli otrzymaliśmy odpowiednia wiadomośc przechodzimy do stanu REAKCJA NA WIADOMOŚĆ. Jesli otrzymaliśmy komunikat odpowiadamy na niego jak stanie CZEKANIE NA KOMUNIKAT jesli kolejki o danym kluczu nie ma lub pakietem danych o formacie pierwszego rodzaju ze stałą K_Zajęta jesli kolejka o podanym kluczu istnieje. Jeśli nadejdą jakieś pakiety danych nie zaliczajace się, do żadnej z powyższych grup wtedy wrzucamy je do kolejki dead.letter.q o ile istnieje. REAKCJA NA WIADOMOŚĆ - jeśli wiadomość dotyczy kolejki której nie mamy wsród kolejek nam podlegających to nie robimy nic i przechodzimy do stanu CZEKANIE NA KOMUNIKAT. Jeśli wiadomośc którą otrzymaliśmy ma pola ident oraz wysyłającyIP równe którejś z poprzednio otrzymanych wiadomości i pole typ równe K_Niepewna wtedy nie robimy nic, jesli pole typ równe K_Pewna wtedy wysyłamy potwierdzenie otrzymania, czyli pakiet danych drugiego rodzaju z odpowiednio wypełnionymi polami ident i key takimi samymi jak w otrzymanej wiadomośći. Jeśli wiadomość którą otrzymaliśmy ma pole ident lub wysyłającyIP różne niż każda z otrzymanych wcześniej wiadomośći wtedy zapisujemy dane z wiadomości do lokalnej kolejki docelowej a dane o otrzymanej wiadomości do odpowiedzniej struktury danych. Jeśli wiadomośc miała typ K_Niepewna to przechodzimy do stanu CZEKANIE NA KOMUNIKAT. Jeśli wiadomość miała typ K_Pewna wtedy wysyłamy potwierdzenie otrzymania, czyli pakiet danych drugiego rodzaju z odpowiednio wypełnionymi polami ident i key takimi samymi jak w otrzymanej wiadomośći i przechodzimy do stanu CZEKANIE NA KOMUNIKAT. *Dodatkowa funkcjonalność optymalizacyjna poza zakresem zadania jedna rzecz: 1)Rozszerzenie funkconalności stanu REAKCJA NA WIADOMOŚĆ w ten sposób, że na początku sprawdzając czy istnieje wśród nam podlegających kolejka o podanym kluczu równym key jesli wykryjemy, że danej kolejki nie ma to nie przechodzimy od razu do stanu CZEKANIE NA KOMUNIKAT ale wcześniej jeszcze wysyłamy dopowiedź taką jak w byśmy byli w stanie ODPOWIEDŹ NA KOMUNIKAT. === Stałe === Timeout = Zależne od implementacji ale >= 10 K_Pytanie = 1 K_NieMa = 2 K_Wolna = 3 K_Zajęta = 4 K_Potwierdzenie = 5 K_Pewna = 6 K_Niepewna = 7