Liniowe kodowanie sieci - Linear network coding

Kodowanie sieciowe to dziedzina badań założona w serii artykułów od końca lat 90. do początku XXI wieku. Jednak koncepcja kodowania sieci, w szczególności liniowego kodowania sieci , pojawiła się znacznie wcześniej. W artykule z 1978 r. zaproponowano schemat poprawy przepustowości dwukierunkowej komunikacji przez satelitę. W tym schemacie dwóch użytkowników próbujących komunikować się ze sobą przesyła swoje strumienie danych do satelity, który łączy oba strumienie, sumując je modulo 2, a następnie nadaje połączony strumień. Każdy z dwóch użytkowników, po odebraniu strumienia rozgłoszeniowego, może zdekodować drugi strumień, wykorzystując informacje z własnego strumienia.

W artykule z 2000 r. podano przykład sieci motylkowej (omówionej poniżej), który ilustruje, w jaki sposób kodowanie sieci liniowej może przewyższać routing. Ten przykład jest odpowiednikiem opisanego powyżej schematu komunikacji satelitarnej. W tym samym artykule podano optymalny schemat kodowania dla sieci z jednym węzłem źródłowym i trzema węzłami docelowymi. Jest to pierwszy przykład ilustrujący optymalność kodowania sieci splotowej (bardziej ogólna forma kodowania sieci liniowej) w sieci cyklicznej.

Liniowe kodowanie sieci może służyć do poprawy przepustowości, wydajności i skalowalności sieci , a także odporności na ataki i podsłuchiwanie. Zamiast po prostu przekazywać otrzymane pakiety informacji, węzły sieci pobierają kilka pakietów i łączą je w celu transmisji. Można to wykorzystać do osiągnięcia maksymalnego możliwego przepływu informacji w sieci .

Udowodniono matematycznie, że teoretycznie kodowanie liniowe wystarcza do osiągnięcia górnej granicy w problemach multicast z jednym źródłem. Jednak ogólnie kodowanie liniowe nie jest wystarczające (np. wieloźródłowe, wieloodpływowe z dowolnymi wymaganiami), nawet w przypadku bardziej ogólnych wersji liniowości, takich jak kodowanie splotowe i kodowanie banku filtrów . Znalezienie optymalnych rozwiązań kodowania dla ogólnych problemów sieciowych z dowolnymi wymaganiami pozostaje otwartym problemem.

Kodowanie i dekodowanie

W problemie z kodowaniem sieci liniowej grupa węzłów bierze udział w przenoszeniu danych z węzłów źródłowych do węzłów ujścia. Każdy węzeł generuje nowe pakiety, które są liniowymi kombinacjami wcześniej odebranych pakietów, mnożąc je przez współczynniki wybrane ze skończonego pola , zwykle o rozmiarze .

Każdy węzeł o stopniu , , generuje wiadomość z liniowej kombinacji otrzymanych wiadomości według relacji:

gdzie wartości są współczynnikami wybranymi z . Zauważ, że ponieważ operacje są obliczane w skończonym polu, wygenerowana wiadomość ma taką samą długość jak oryginalne wiadomości. Każdy węzeł przekazuje obliczoną wartość wraz ze współczynnikami, , używanymi w poziomie, .

Węzły odbiorcze odbierają te zakodowane w sieci wiadomości i gromadzą je w macierzy. Oryginalne wiadomości można odzyskać, wykonując eliminację Gaussa na macierzy. W zredukowanej postaci schodkowej wierszy dekodowane pakiety odpowiadają wierszom postaci .

Krótka historia

Sieć jest reprezentowana przez graf skierowany . jest zbiorem węzłów lub wierzchołków, jest zbiorem skierowanych połączeń (lub krawędzi) i podaje pojemność każdego połączenia . Niech będzie maksymalna możliwa przepustowość od węzła do węzła . Według twierdzenia max-flow min-cut , jest od góry ograniczone przez minimalną nośność wszystkich przecięć , która jest sumą nośności krawędzi na przecięciu, pomiędzy tymi dwoma węzłami.

Karl Menger udowodnił, że zawsze istnieje zestaw rozłącznych krawędziowych ścieżek osiągających górną granicę w scenariuszu unicast , znanym jako twierdzenie o maksymalnym przepływie i odcięciu . Później zaproponowano algorytm Forda-Fulkersona, aby znaleźć takie ścieżki w czasie wielomianowym. Następnie Edmonds udowodnił w artykule „Edge-Disjoint Branchings” górne ograniczenie w scenariuszu rozgłoszeniowym jest również osiągalne i zaproponował wielomianowy algorytm czasu.

Jednak sytuacja w scenariuszu multiemisji jest bardziej skomplikowana iw rzeczywistości takiej górnej granicy nie można osiągnąć przy użyciu tradycyjnych pomysłów dotyczących routingu . Ahlswede i in. udowodnili, że można to osiągnąć, jeśli dodatkowe zadania obliczeniowe (pakiety przychodzące są łączone w jeden lub kilka pakietów wychodzących) można wykonać w węzłach pośrednich.

Przykład sieci motyli

Sieć motyli.

Sieć motylkowa jest często używana do zilustrowania, w jaki sposób liniowe kodowanie sieci może przewyższać routing . Dwa węzły źródłowe (na górze obrazu) mają informacje A i B, które muszą być przesłane do dwóch węzłów docelowych (na dole). Każdy węzeł docelowy chce znać zarówno A, jak i B. Każda krawędź może przenosić tylko jedną wartość (możemy pomyśleć o krawędzi transmitującej bit w każdej szczelinie czasowej).

Gdyby dozwolony był tylko routing, wówczas łącze centralne mogłoby przenosić tylko A lub B, ale nie oba. Załóżmy, że wysyłamy A przez centrum; wtedy lewy cel otrzymałby A dwa razy i w ogóle nie znałby B. Wysyłanie B stwarza podobny problem we właściwym miejscu docelowym. Mówimy, że routing jest niewystarczający, ponieważ żaden schemat routingu nie może przesyłać jednocześnie A i B do obu miejsc docelowych. Tymczasem potrzeba łącznie czterech przedziałów czasowych, aby oba węzły docelowe znały A i B.

Używając prostego kodu, jak pokazano, A i B mogą być przesyłane do obu miejsc docelowych jednocześnie, wysyłając sumę symboli przez dwa węzły przekaźnikowe – innymi słowy, kodujemy A i B za pomocą formuły „A+B”. Miejsce docelowe po lewej odbiera A i A + B i może obliczyć B, odejmując te dwie wartości. Podobnie właściwe miejsce docelowe otrzyma B i A + B, a także będzie w stanie określić zarówno A, jak i B. Dlatego przy kodowaniu sieci zajmuje to tylko trzy przedziały czasowe i poprawia przepustowość.

Losowe liniowe kodowanie sieci

Losowe liniowe kodowanie sieci jest prostym, ale potężnym schematem kodowania, który w schematach transmisji rozgłoszeniowej umożliwia bliską optymalnej przepustowości przy użyciu zdecentralizowanego algorytmu. Węzły przesyłają losowe kombinacje liniowe otrzymywanych pakietów, ze współczynnikami wybranymi z pola Galois. Jeśli rozmiar pola jest wystarczająco duży, prawdopodobieństwo, że odbiornik(i) uzyskają liniowo niezależne kombinacje (a tym samym uzyskają innowacyjną informację) zbliżają się do 1. Należy jednak zauważyć, że chociaż losowe liniowe kodowanie sieci ma doskonałą przepustowość, jeśli Odbiorca otrzymuje niewystarczającą liczbę pakietów, jest bardzo mało prawdopodobne, aby mógł odzyskać którykolwiek z oryginalnych pakietów. Można temu zaradzić, wysyłając dodatkowe losowe kombinacje liniowe, aż odbiorca otrzyma odpowiednią liczbę pakietów.

Otwarte kwestie

Liniowe kodowanie sieci to wciąż stosunkowo nowy temat. W oparciu o poprzednie badania, w RLNC istnieją trzy ważne otwarte kwestie:

  1. Wysoka złożoność obliczeniowa dekodowania dzięki zastosowaniu metody eliminacji Gaussa-Jordana
  2. Wysoki narzut na transmisję dzięki dołączaniu wektorów o dużych współczynnikach do zakodowanych bloków
  3. Liniowa zależność między wektorami współczynników, która może zmniejszyć liczbę innowacyjnych zakodowanych bloków

Kodowanie sieci bezprzewodowej

Rozgłoszeniowy charakter łączności bezprzewodowej (w połączeniu z topologią sieci) określa charakter zakłóceń . Jednoczesne transmisje w sieci bezprzewodowej zwykle powodują utratę wszystkich pakietów (tj. kolizje, patrz Wielokrotny dostęp z unikaniem kolizji w sieci bezprzewodowej ). Dlatego sieć bezprzewodowa wymaga programu planującego (jako części funkcjonalności MAC ), aby zminimalizować takie zakłócenia. W związku z tym wszelkie korzyści z kodowania sieci są silnie uzależnione od bazowego programu planującego i będą odbiegać od korzyści obserwowanych w sieciach przewodowych. Ponadto łącza bezprzewodowe są zazwyczaj w trybie półdupleksowym ze względu na ograniczenia sprzętowe; tj. węzeł nie może jednocześnie nadawać i odbierać z powodu braku wystarczającej izolacji między dwiema ścieżkami.

Chociaż pierwotnie proponowano stosowanie kodowania sieciowego w warstwie sieciowej (patrz model OSI ), w sieciach bezprzewodowych kodowanie sieciowe było szeroko stosowane zarówno w warstwie MAC, jak i warstwie PHY . Wykazano, że kodowanie sieciowe stosowane w bezprzewodowych sieciach kratowych wymaga uważnego projektowania i przemyśleń, aby wykorzystać zalety mieszania pakietów, w przeciwnym razie korzyści nie można zrealizować. Istnieje również wiele czynników wpływających na przepustowość, takich jak protokół warstwy dostępu do mediów, algorytmy kontroli przeciążenia itp. Nie jest oczywiste, w jaki sposób kodowanie sieciowe może współistnieć i nie zagrażać temu, co istniejące algorytmy przeciążenia i kontroli przepływu robią dla naszego Internetu .

Aplikacje

Krótka ilustracja kodowania sieciowego zastosowanego do komunikacji urządzenie-urządzenie. D1 i D2 oznaczają urządzenia, BS to stacja bazowa, a M1, M2 i M3 to pewne komunikaty.

Ponieważ kodowanie sieci liniowych jest stosunkowo nowym tematem, jego przyjęcie w przemyśle jest nadal w toku. W przeciwieństwie do innego kodowania, kodowanie sieci liniowej nie jest w pełni możliwe do zastosowania w systemie ze względu na jego wąski scenariusz zastosowania. Teoretycy próbują połączyć się z aplikacjami w świecie rzeczywistym. W rzeczywistości okazało się, że podejście BitTorrent jest znacznie lepsze niż kodowanie sieciowe.

Przewiduje się, że kodowanie sieciowe jest przydatne w następujących obszarach:

  • Ze względu na wieloźródłową, multiemisyjną naturę dostarczania treści w sieciach zorientowanych na informacje ogólnie, aw szczególności w sieciach nazwanych danych , kodowanie liniowe może poprawić wydajność całej sieci.
  • Alternatywa dla przekazywania korekcji błędów i ARQ w tradycyjnych i bezprzewodowych sieciach z utratą pakietów. np.: kodowany TCP , ARQ dla wielu użytkowników
  • Solidny i odporny na ataki sieciowe, takie jak szpiegowanie, podsłuchiwanie, powtarzanie lub ataki na uszkodzenie danych.
  • Dystrybucja plików cyfrowych i udostępnianie plików P2P. np.: Avalanche firmy Microsoft
  • Rozproszona pamięć masowa.
  • Wzrost przepustowości w bezprzewodowych sieciach kratowych. np : COPE , CORE , Coding-aware routing , BATMAN
  • Redukcja bufora i opóźnienia w przestrzennych sieciach czujników: multipleksowanie bufora przestrzennego
  • Zmniejsz liczbę retransmisji pakietów dla bezprzewodowej transmisji multicast z jednym przeskokiem, a tym samym zwiększ przepustowość sieci.
  • Rozproszone udostępnianie plików
  • Przesyłanie strumieniowe wideo o niskiej złożoności do urządzeń mobilnych
  • Rozszerzenia Device-to-Device (D2D)

Pojawiają się nowe metody wykorzystania kodowania sieciowego w systemach wielodostępowych do opracowywania definiowanych programowo sieci przewodowych (SD-WAN), które mogą oferować mniejsze opóźnienia, jitter i wysoką niezawodność. W propozycji wspomniano, że metoda jest agnostyczna w stosunku do podstawowych technologii, takich jak LTE, Ethernet, 5G.

Dojrzałość i problemy

Ponieważ obszar ten jest stosunkowo nowy, a matematyczne podejście do tego tematu jest obecnie ograniczone do garstki osób, kodowanie sieciowe znalazło jeszcze drogę do komercjalizacji produktów i usług. Na tym etapie nie jest jasne, czy ten temat zwycięży, czy przestanie być dobrym ćwiczeniem matematycznym.

Badacze wyraźnie wskazali, że należy zachować szczególną ostrożność, aby zbadać, w jaki sposób kodowanie sieciowe może współistnieć z istniejącym routingiem, dostępem do mediów, przeciążeniem, algorytmami kontroli przepływu i protokołem TCP. Jeśli nie, kodowanie sieciowe może nie oferować wielu korzyści i może zwiększyć złożoność obliczeń i wymagania dotyczące pamięci.

Zobacz też

Bibliografia

  • Fragouli, C.; Le Boudec, J. & Widmer, J. „Kodowanie sieciowe: natychmiastowy elementarz” w Computer Communication Review , 2006.

Ali Farzamnia, Sharifah K. Syed-Yusof, Norsheila Fisa „Multicasting Multiple Description Coding Using p-Cycle Network Coding”, KSII Transactions on Internet and Information Systems, tom 7, nr 12, 2013.

Linki zewnętrzne