AKKD

1. Gra wieloosobowa
2. Teoria sprawiedliwości
   1. Pomiar sprawiedliwości (fairness measure)
   2. Pomiar Golestaniego
   3. Sprawiedliwość minimaksymalna (min-max fairness)
3. Problematyczne sytuacje
4. Globalna synchronizacja
5. Jakość usług (QoS)

Pomiar Sprawiedliwości

Sprawiedliwość przydziałów jest ważnym aspektem każdego rozproszonego systemu w którym pewien zasób należy rozdysponować pomiędzy jednostki. Dopiero w początkach lat 80. zaczęto formalizować pojęcie sprawiedliwości na szersza skalę w sieciach komputerowych. Były jednak albo mało dokładne, albo zbyt specyficzne dla konkretnego rozwiązania. Te bardziej ogólne sprowadzały się do określenia, że podział który nie jest równy, nie jest sprawiedliwy. Na przykład Jeffrey Jaffe twierdzi, że podział jest sprawiedliwy jeśli ,,przepustowość każdego użytkownika jest przynajmniej tak duża jak przepustowość innych użytkowników o takim samym wąskim gardle''[1]. Rok później Marco Marsan i Mario Gerla zaprezentowali [2]pomiar sprawiedliwości jako: $$ f(x) = min_{i,j} \left\{ \frac{p_i}{p_j} \right\} $$ gdzie $p_i$ i $p_j$ są współczynnikami przepustowości i opoźnienia odpowiednio użytkownika $i$ oraz $j$. Kolejnymi próbami było mierzenie sprawiedliwości względem współczynnika zmienności opóźnień, jego kwadratu i podobnych wariacji.

Wszystkie sposoby zakładały jednak, że sprawiedliwość to równy podział nie określając co dokładnie powinno być równe. Zauważyli to juz Jain, Chiu i Hawe z DEC Research proponując w 1984 roku bardziej zaawansowany pomiar [3]. Wskaznik sprawiedliwości będący wynikiem tego pomiaru ma kilka interesujących cech:

• Niezależność od ilości populacji. Jeśli podział jest taki sam dla dwóch użytkowników i dla stu, wskaźnik się nie zmieni.
• Niezależność od ilości zasobów. Jeśli ten sam sposób podziału dzieli dwa razy większy zasób, to nie znaczy, że robi to dwa razy bardziej sprawiedliwie, lub dwa razy mniej sprawiedliwie.
• Ograniczenie wartośći od 0 do 1. Co więcej, przykładowy wynik 0.1 można interpretować jako sprawiedliwość dla 10% użytkowników.
• Ciągłość. Najmniejsza zmiana sposobu podziału ma bezpośrednie odzwierciedlenie w wyniku pomiaru.

Pozostaje pytanie, co podstawić za $x$, czyli co dokładnie rozdzielać. Według autorów powyższej teorii jest kilka możliwości zależnych od rodzaju danych:

• czas reakcji – Dla danych przesyłanych przez programy interaktywne
• czas reakcji na jedno przełączenie – W rozbudowanych sieciach od połączenia na dużą odległość można spodziewać się większego opóźnienia i uznać to za sprawiedliwe, liczyć więc wtedy można opóźnienie na pojedyńczym fragmencie sieci.
• przepustowość – Dla aplikacji przesyłających pliki lub inne dane nie wymagające natychmiastowej reakcji.
• przepustowość dzielona na ilość przełączeń – Z takiego samego powodu jak czas reakcji na ilość przełączeń.
• moc obu wartości – Jeśli użytkownik przesyła równocześnie dane interaktywne oraz pliki. Może to być współczynnik przepustowości do opóźnienia.
• ułamek zapotrzebowania – Jeśli użytkownicy mają zróżnicowane potrzeby lub chociażby płącą różne ceny za dostęp.

Przykładowo, jeśli dany użytkownik płaci więcej, powinien dostać większy przydział. Jeśli określimy, że użytkownik $i$ płaci $p_i$ złotych, podczas gdy podstawową ceną jest $p$, to $d_i = \frac{p_i}{p}$ można opisać jako współczynnik określający ile razy więcej użytkownikowi należy się przydziału niż płacącemu cenę podstawową. Wtedy wskaźnik sprawiedliwości można obliczyć wzorem: $$ f(x) = \frac {\left[ \sum_{i=1}^n \frac{x_i}{d_i} \right]^2} {\sum_{i=1}^n \left(\frac{x_i}{d_i}\right)^2} ~ , ~~~ x_i \ge 0 $$

Jeśli rozdzielamy według potrzeb, jako $d_i$ możemy przyjąć ilość potrzebnego zasobu. W tym wypadku jednak przydzielenie więcej niż potrzeba nie powoduje, że użytkownik jest traktowany lepiej. Dlatego do wzoru na wskaźnik za $x$ wypada podstawić: $$ x_i = \left\{ \begin{array}{ll} \frac{a_i}{d_i} & \textrm{jeżeli } a_i < d_i \\ 1 & \textrm{w przeciwnym wypadku} \end{array} \right. $$ gdzie $a_i$ jest rzeczywistym przydziałem.

Jednym ze sposobów wykorzystania wskaźnika sprawiedliwości przez samego użytkownika jest sprawdzenie, czy dostaje on tyle przydziału ile mu się należy. Aby to zrobić wystarczy wyraźić proponowany wskaźnik następująco: $$ f(x) = \frac{1}{n} \sum_{i=1}^{n} \frac {x_i} {x_f} $$ gdzie $x_f$ jest tak zwanym znacznikiem sprawiedliwego podziału obliczanym według wzoru: $$ x_f = \frac { \sum_{i=1}^{n} x_i^2 } { \sum_{i=1}^{n} x_i } = \frac{b_2}{b_1} $$ Każdy użytkownik może porównać swój udział $x_i$ ze znacznikiem $x_f$ i stwierdzić, że jego przydział jest sprawiedliwy lub nie, jeśli $x_i$ jest odpowiednio większy lub mniejszy niż $x_f$. Jeśli $x_i < x_f$ to można powiedzieć, że udział $i$-tego użytkownika jest w $\frac{x_i}{x_f} \cdot 100\%$ sprawiedliwy.

Autorzy udowadniają kilka twierdzeń prawdziwych dla tak zdefiniowanego wskaźnika sprawiedliwości:

1. Twierdzenie o wymianie przydziału: Jeżeli przydział $\Delta x$ zostanie zabrany użytkownikowi $k$ i przydzielony użytkownikowi $j$ to ogólna sprawiedliwość:
   • rośnie, jeśli $ \Delta x < x_k - x_j $
   • maleje, jeśli $ \Delta x > x_k - x_j $
   • nie zmienia się, jeśli $ \Delta x = x_k - x_j $
2. Twierdzenie o dodatkowym przydziale: Jeżeli każdemu użytkownikowi dodana zostanie jednakowa ilość $c$ przydziału, to sprawiedliwość wzrośnie lub niezmieni się: $$ f(x_1+c,~ x_2+c,~ \ldots,~ x_n+c) \ge f(x_1,~ x_2,~ \ldots,~ x_n) $$
3. Twierdzenie o dodatkowym małym przydziale: Jeżeli jednemu użytkownikowi dodana zostanie pewna mała ilość przydziału, to sprawiedliwość:
   • wzrośnie, jeśli był to dyskryminowany użytkownik,
   • zmaleje, jeśli był to faworyzowany użytkownik.
   (Autorzy zakładają zapewne, że będzie to ilość na tyle mała by użytkownik nie stał się bardziej faworyzowany niż wcześniej dyskryminowany i na odwrót, gdyż wtedy twierdzenie nie byłoby prawdziwe)
4. Twierdzenie o maksymalizacji: Jeśli będziemy zmieniać przydział użytkownika $j$ (nie zmianiając przydziałów innym), to sprawiedliwość osiągnie maksimum jeśli $$ x_j = x_{f,n-1} $$ gdzie $x_{f,n-1}$ to znacznik sprawiedliwego podzialu dla pozostałych $n-1$ użytkowników.
5. Twierdzenie o ograniczeniu przydziałów: Jeśli $x_{min} \le x_i \le x_{max}$ dla każdego $i$ oraz $x_{min} > 0$ to sprawiedliwość nie przekracza gwarantowanego minimalnego poziomu oraz:
   1. minimalna sprawiedliwość zachodzi gdy ułamek ($\gamma$) użytkowników dostaje $x_{min}$ przydziału a reszta $x_{max}$, wtedy $$ \gamma = \frac {K} {K+1} ~~~ \textrm{gdzie } K = \frac {x_{max}} {x_{min}} $$
   2. minimalny poziom sprawiedliwości gwarantowany jest przez ograniczenie $$ f \ge \frac {4K} {(K+1)^2} $$

1. [^] Jeffrey M. Jaffe ,,Bottleneck Flow Control'', IEEE Transactions on Communications, vol. COM–29, s. 954–962, 1981
2. [^] Marco A. Marsan, Mario Gerla ,,Fairness in Local Computer Networks'', Proc. IEEE International Communications Conference (ICC '02), Czerwiec 1982
3. [^] R. Jain, D.M. Chiu, W. Hawe ,,A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Systems'', DEC Research Report TR-301, 1984