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