r =
s =
ss =

AKKD

Nowości Historia i teoria : : Algorytmy bezklasowe : : Algorytmy klasowe : : Klasyfikowanie ruchu (filtry) : : Dobre praktyki

Historia i teoria / Gra Wieloosobowa

Rok 1970

Pierwsze pomysły kontrolowania ruchu pojawiły się już w 1970 roku. Jednym z nich był zaproponowany przez jednego z twórców ARPANetu – Stephena Crockera protokół Host-to-host [1]. Jeden z hostów łącząc się z drugim rezerwował pewną ilość buforów dla pakietów które wysyłał. Ilość wolnych buforów spadała razem z wysyłaniem danych. Odbiorca mógł zwiększać bufory kiedy łącze było wolne, lub czekać z nowym przydziałem jeśli chciał najpierw obsłużyć innego nadawce. Należy jednak zwrócić uwagę, że protokół ten obsługuje komunikację tylko między dwoma hostami bez wiedzy na temat pośredniczących routerów.

Kolejnym podejściem do problemu, rozwijającym myśl protokołu HOST-HOST, był pomysł Richarda Kalina (z MIT) bardzo obrazowo opisany w RFC60 [2]. Odbiorca dla każdego nadawcy rezerwował skrzynie, w których ten mógł przysłać pakiety. Taka skrzynia po dotarciu do odbiorcy wysyłana była spowrotem, mogąc zawierać odpowiedź. Skrzynie, które wróciły, gotowe były do użytku dla następnych pakietów. Manewrując ilością skrzyń można było sterować przepływem. Warto zauważyć, że aby komunikować się na łączu nie pozwalającym na równoczesny przesył w dwie strony wystarczyło ograniczyć ilość skrzyń do jednej.

Jeszcze w tym samym roku David Walden zaproponował nowe podejście [3] działające na zasadzie deklaracji o gotowości do działania. Przykładowe przesłanie danych mogłoby rozpocząć się na hoście nadawcy X od deklaracji procesu wysyłającego, że na porcie N są dane do wysłania na host Y na port M. Host Y dostaje taką deklarację i wpisuje ją do tablicy spotkań (ang. randez-vous table). Jeśli proces na komputerze Y zadeklaruje gotowość odebrania informacji na porcie M z hosta X, nastąpi spotkanie X:N - Y:M pozwalające na przesłanie danych (i tak powstał conntrack :). Zarządzając tablicą spotkań, można kontrolować przepływ przez urządzenie odbierające lub przekazujące (czyli przechowujące tablicę). Możliwa była deklaracja odbioru danych z jakiegokolwiek hosta i jakiegokolwiek portu, co było równoznaczne z ustanowieniem serwera słuchającego nadchodzących połączeń.

Gra wieloosobowa

Wszystkie te rozwiązania, chociaż miały zasadniczy wpływ na dzisiejszy Internet, nie dawały faktycznej kontroli w dzieleniu dostępu do sieci. Dlaczego tak się stało, wyjasniał 15 lat później John Nagle podczas rozważań nad hipotetycznymi urządzeniami sieciowymi o niekończącej się pamięci [4]. Porównał on sieć komputerową do wieloosobowej gry, której tworcy próbują ustalić reguły zachowania graczy pozwalające na sprawiedliwą współpracę. O grze w której optymalna strategia dla jednego gracza nie jest optymalna dla wszystkich mówi się, że ma skłonność do stanów nieoptymalnych. Znanym przykładem jest tutaj dylemat więźnia [5].

Dylemat więźnia

Dwóch zamieszanych w duże przestepstwo osobników złapano za małe przewinienie. Policja wie, że są oni winni, lecz nie ma dowodów. Jeśli:

żaden z nich nie będzie zeznawać, odsiedzą niewielką karę za małe przewinienie,
jeden będzie zeznawał, a drugi nie, wtedy pierwszy zostanie uwolniony, drugi natomiast pójdzie do więzienia za poważne przestępstwo,
obaj będą zeznawać — obaj pójdą siedzieć, przy czym wyrok będzie z tego względu nieco złagodzony.

Problem jest następujący: niezależnie od postępowania drugiego, opłaca się zeznawać. Jeśli natomiast żadna ze stron by nie zeznawała, wynik byłby o wiele lepszy dla obu graczy.

Tragedia wspólnego pastwiska

Bardziej podobnym do sieci komputerowych przykładem, choć nie tak wyrazistym, jest tzw. tragedia wspólnego pastwiska. Pojedyncza osoba korzystająca z dobra publicznego bardziej, niż się jej należy, zawsze na tym zyskuje. Z kolei duża liczba użytkowników nadużywająca dobra wspólnego może doprowadzić do zniszczenia tego dobra. W ogólności, systemy, które mają takie tendencje prędzej czy później prowadzą do poważnego problemu.

Nagle rozważa trzy możliwości uporania się z problemem „pastwiska”: współpraca graczy, dyktatura, rozwiazania rynkowe. Współpraca graczy, polega na zgodzie, że każdy będzie zachowywać się poprawnie i zgodnie z przyjętymi regułami. Rozwiązanie działające w grupie znających się osób niesprawdza się kompletnie w momencie szybkiego wzrostu liczby graczy. Dyktatura wymaga ciągłego monitorowania i podejmowania drastycznych działań, ale wpada w problemy jeśli definicja dobrego zachowania gracza jest subtelna. Rozwiązanie rynkowe jest możliwe, jeśli można tak zmienić reguły gry, by optymalna strategia gracza dawała optymalny wynik dla wszystkich. W przypadku sieci komputerowych graczem jest zaprogramowany komputer, ale to nie oznacza, że będzie on sprawiedliwie grał. Może on tak działać, by osiągać najlepsze korzyści dla użytkownika nie zwracając uwagi na konsekwencje występujące w sieci.

Analogiczny problem występuje w sieci telefonicznej kiedy na skutek wzmożonego ruchu próba połączenia zostaje odrzucona. Wtedy użytkownik probóje dzwonić kolejno kilka razy jeszcze bardziej przeciążając sieć. Podobno w niektórych krajach (w Brazylii?) telefony robiące to automatycznie zostały zabronione w tamtych czasach.

Rynek pakietów

Aby zastosować trzecią z możliwości w sieci komputerowej, należy nagradzać za dobre zachowanie, a karać za złe. Nie możemy jednak zaprogramować reguł na komputerze użytkownika, ani nie można wysyłać komputerom instrukcji zachowania. Stały by się częścią gry, gracz mógłby przeprogramować zasady i nie stosować się do otrzymywanych instrukcji. Jedynym sposobem jest sterowanie tym na czym graczowi zależy, czyli przesłaniem (lub blokowaniem) właśnie jego danych. Odrzucanie lub opóźnianie pakietów staje się więc jedynym sposobem na regulację rynku. Każde urządzenie przekazujące dane musi w ten sposób tworzyć rynek dla swoich klientów tak, by przydział zasobów był sprawiedliwy, a jednocześnie zostać klientem na rynku swoich urządzeń dostępowych.

Przypisy

Content by Michał Pokrywka is licensed under a Creative Commons BY-SA 3.0
Ostatnia znacząca zmiana: 2010-04-28