Kodowanie sieciowe

Kodowanie sieciowe (ang. network coding) – dział teorii informacji i teorii kodowania. Jest metodą osiągania maksymalnego przepływu danych w sieci.

Ogólne informacje

Sieć jest bezpośrednim grafem, gdzie jego brzegi reprezentują przepływ informacji. Używając teorii max-flow min-cut można obliczyć maksymalną ilość informacji, jaka może być przesłana przez sieć pomiędzy wysyłającym a wieloma odbiorcami. Zostało udowodnione, że taka ilość maksymalnego przepływu jest osiągalna, ale że trasowanie nie jest w stanie jej osiągnąć. Podstawą kodowania sieciowego jest pozwolenie na mieszanie danych na średnich sieciowych punktach węzłowych. Odbiorca widzi te pakiety danych i odczytuje z nich wiadomości, które były przeznaczone dla danych sink.

Trasowanie nie może zapewnić maksymalnego przepływu danych, ale można go osiągnąć poprzez użycie prostego kodowania. W środowiskach naukowych pierwsze wzmianki o kodowaniu sieciowym pojawiły się około 7 lat temu^[kiedy?]. Z przedstawionych wówczas wyników badań wynikało, że zastosowanie specjalnego algorytmu umożliwia podwojenie przepływności transmisji.

Zasada działania kodowania sieciowego opiera się na podzieleniu wiadomości na mniejsze części. Umożliwiają one urządzeniu końcowemu odtworzenie nadanej informacji bez konieczności transmisji lub retransmisji całej wiadomości.

Liniowe kodowanie sieci

W 2003 r. zostało pokazane, że kody liniowe osiągną maksymalny przepływ w pojedynczo-źródłowe multicast sieci (każdy docelowy punkt węzłowy otrzymuje wszystkie informacje źródła), biorąc pod uwagę, że rozmiar alfabetu jest dość wielki. W 2004 r. zostało pokazane, że liniowe kody sieciowe nie są ogólnie wystarczające. Nie są one asymptomatycznie liniowe, ani nie są liniowo rozwiązalne używając convolutional codes, badź metod time-sharing. Pokazano też, że braki liniowych kodów odnoszą się do wielu sieci unicast.

Teoria

W przypadku problemu w kodowaniu sieci liniowej grupa punktów węzłowych P przenosi dane z S źródlanych punktów węzłowych do K sink nodes [końcowych punktów węzłowych]. Każdy punkt węzłowy generuje nowy pakiet, który jest liniową kombinacją wcześniej otrzymanych pakietów na link poprzez współczynnik w finite field [skończonym polu]. Wiadomość wygenerowana w sposób taki, że Xk jest połączone z otrzymanymi wiadomościami Mi

X_{k}=\sum _{i=1}^{S}g_{k}^{i}\cdot M_{i}.

Każdy punkt węzłowy przesyła obliczoną wartość $X_{k}$ razem ze wszystkimi współczynnikami używanymi w $k^{th}.$

Wartości $g_{k}^{i}$ są współczynnikami z pola $GF(2^{s}).$ Skoro operacje są obliczane w skończonych polach, rezultat tych operacji jest także tej samej długości, tak jak wielkość każdego wektora M.

Każdy punkt węzłowy wytwarza podobny produkt, tak jak obliczono powyżej. Równa się to liniowemu problemowi typu X = GM gdzie znając X i G musimy obliczyć M. Każdy z odbiorców w K próbuje rozwiązać to liniowe równanie dla którego przynajmniej $N\geqslant S.$

Otrzymane pakiety są bez przerwy używane w metodzie eliminacji Gaussa do ograniczenia matrycy G do „row-echelon” formy. Na końcu uzyskane wartości $X=G_{echelon}M$ są rozwiązane aby uzyskać M.

Przykład

Butterfly Network.

Sieć Motylowa

W sieci motylowej są dwa źródła (na górze schematu), każde posiadające wiedzę o jakiejś wartości A i B. Są dwa docelowe punkty węzłowe(na dole schematu), z których każdy chce „widzie” A i B. Każda krawędź może tylko nieść pojedyncze wartości (możemy myśleć o krawędzi przesyłającej bit w każdym czasowym przedziale).

Jeśli użylibyśmy trasowania to linia centralna mogłaby nieść A lub B, ale nie obydwa. Przypuśćmy, że wysyłamy A poprzez węzeł; docelowy punkt po lewej otrzymałby A dwa razy i nie znałby B w ogóle. Wysyłanie B sprowadza podobny problem dla docelowego punktu po prawej. Mówimy więc że trasowanie jest niewystarczające ponieważ żaden układ trasowania nie może przekazać razem A i B jednocześnie do dwóch punktów docelowych.

Używanie prostego kodu, jak pokazano powyżej, dostarczamy razem A i B do obydwóch punktów docelowych jednocześnie poprzez wysyłanie suma symboli przez centrum (innymi słowy, kodujemy A i B używając formuły „A+B”). Lewy punkt docelowy otrzymuje A i A+B i może znaleźć B przez odjęcie tych dwóch wartości. To jest kod liniowy, ponieważ schematy kodowania, jak i schematy odkodowania są operacjami liniowymi.

Przekaz

W środku sieci motylowej są przesyłane trzy wiadomości (A. A+B. B). Aczkolwiek cztery wiadomości są odbierane na punktach końcowych na dole (odbierane są cztery wiadomości kosztem trzech wiadomości, poprawienie o 33%). Zauważmy, że pamięć w wiadomości w środkowym routerze mogłaby przechować wiadomości A i B i nadal przekazać wszystkie cztery wiadomości do punktów końcowych (odbierane są cztery wiadomości kosztem dwóch wiadomości, poprawienie o 100%).

Dekodowanie

Kodowanie sieciowe wykorzystuje operację różnicy symetrycznej (XOR, exclusive or), by połączyć dwa pakiety informacji. Bit po bicie pakiety poddawane są wspomnianemu działaniu logicznemu, które daje wynik równy 1 jeśli dane wejściowe były różne. Rezultat wynosi zero, jeśli obydwa bity były tej samej wartości. Te jedynki i zera tworzą kod, na podstawie którego stacja końcowa wyposażona w odpowiednią „inteligencję” może odtworzyć wiadomość otrzymaną od nadawcy. W ten sposób kodowanie sieciowe pozwala przesłać i odebrać wiele wiadomości jednocześnie, bez wzrostu ilości przesłanych pakietów. Poprzez kodowanie sieciowe będzie można wzmocnić bezpieczeństwo informacji, gdyż zakłada wymieszanie dwóch strumieni danych przy użyciu funkcji logicznej XOR. Jeśli mamy dwa bity, A i B, i zastosujemy różnicę symetryczną, wówczas na podstawie samej wartości XOR nie jesteśmy w stanie jednoznacznie określić początkowej wartości poszczególnych bitów. Oczywiście, można zdefiniować jaka kombinacja par daje w efekcie otrzymany wynik, jednak jedynie w przypadku, gdy znana jest wartość bitu B można z całą pewnością powiedzieć, jaka była wartość bitu A.

Kodowanie sieci i P2P

Wielu uczonych uważa, że kodowanie sieci mogłoby pomóc i ulepszyć wydajność sieci P2P, inni natomiast są zupełnie innego zdania. Dr Yeung zapytany „Czy kodowanie sieci może pomóc w P2P?” odpowiedział, że kodowanie sieci niekoniecznie pomaga sieciom P2P, podał on kilka problemów jakie mogą się pojawić przy stosowaniu tej techniki.

Istnieje wiele trudności dla Kodowania Sieciowego w sieciach P2P:

Użytkownik może spędzić większą ilość czasu na odkodowywaniu otrzymanych danych.
Moc obliczeniowa potrzebna do odkodowania.
Jak zapewnić unikalność współczynników kiedy jest dużo części pliku w przesłanych danych?
Topologia sieci P2P zmienia się.
Użytkownicy mogą opuścić sieć kiedy tylko zechcą.

W oparciu o te argumenty, niektórzy naukowcy sądzą, że sieci P2P z Kodowaniem Sieciowym mogłyby być jeszcze gorsze niż sieci BitTorrent.

Historia

Fundamentalny koncept kodowania sieci został zastosowany w sieciach komunikacji satelitarnej w pracy R.W. Yeunga i Z. Zhanga.

Koncept ten był w pełni rozwinięty w kolejnych pracach R. Ahlswede’a, N. Caia, S.Y.R. Lia oraz R.W. Yeunga, gdzie termin kodowanie sieci został ukształtowany. W tej pracy, zaleta kodowania sieci nad tradycyjnym sposobem operowania siecią, została wskazana po raz pierwszy przy pomocy bardzo prostego przykładu znanego jako sieć motylowa.

W 2006 roku, Chiu et al zademonstrował, że maksymalnie osiągalny przepływ systemu p2p w sieci bez multicastingu jest dokładnie taki sam z lub bez jakiegokolwiek rodzaju kodowania sieci, jeśli idealne informacje trasowania są dostępne (co nie jest do końca prawdą w realnych sytuacjach).

Pozytywne skutki korzystania z kodowania sieciowego

Kodowanie sieci jest uważane za przydatne w następujących sytuacjach:

jako alternatywa na forward error correction i ARQ w tradycyjnych i bezprzewodowych sieciach, np. Multi-user ARQ (ARQ z wieloma użytkownikami);
odporne na ataki sieci typu snooping, eavesdropping czy replay;
cyfrowa dystrybucja plików i P2P, np. Avalanche Microsoftu;
zwiększony przepływ w bezprzewodowych sieciach mesh, np.: COPE, Coding-Aware Routing.

Bibliografia

http://www.idg.pl