Lineární síťové kódování - Linear network coding

Síťové kódování je oblast výzkumu založená na řadě článků od konce 90. let do počátku 2000. Koncept síťového kódování, zejména lineárního síťového kódování , se však objevil mnohem dříve. V článku z roku 1978 bylo navrženo schéma pro zlepšení propustnosti obousměrné komunikace přes satelit. V tomto schématu dva uživatelé, kteří se snaží komunikovat mezi sebou, přenášejí své datové toky na satelit, který tyto dva toky kombinuje jejich součtem modulo 2 a poté vysílá kombinovaný tok. Každý ze dvou uživatelů může po přijetí vysílacího proudu dekódovat druhý proud pomocí informací o svém vlastním proudu.

Dokument z roku 2000 uvádí příklad motýlové sítě (popsaný níže), který ilustruje, jak může lineární kódování sítě překonat směrování. Tento příklad je ekvivalentní výše popsanému schématu pro satelitní komunikaci. Stejný dokument poskytl optimální schéma kódování pro síť s jedním zdrojovým uzlem a třemi cílovými uzly. Toto je první příklad ilustrující optimálnost konvolučního kódování sítě (obecnější forma kódování lineární sítě) přes cyklickou síť.

Lineární síťové kódování lze použít ke zlepšení propustnosti, efektivity a škálovatelnosti sítě , jakož i odolnosti vůči útokům a odposlechu. Namísto jednoduchého předávání paketů informací, které dostávají, uzly sítě vezmou několik paketů a spojí je dohromady pro přenos. To lze použít k dosažení maximálního možného toku informací v síti .

Matematicky bylo prokázáno, že teoreticky stačí k dosažení horní hranice v multicastových problémech s jedním zdrojem lineární kódování . Lineární kódování však obecně nestačí (např. Multisource, multisink s libovolnými požadavky), a to ani pro obecnější verze linearity, jako je konvoluční kódování a kódování filtrů . Nalezení optimálního řešení kódování pro obecné problémy se sítí s libovolnými požadavky zůstává otevřeným problémem.

Kódování a dekódování

V problému lineárního síťového kódování se skupina uzlů podílí na přesunu dat ze zdrojových uzlů do uzlů jímky. Každý uzel generuje nové pakety, které jsou lineárními kombinacemi dříve přijatých paketů a vynásobí je koeficienty vybranými z konečného pole , obvykle velikosti .

Každý uzel, s indegree , , generuje zprávu z lineární kombinace přijatých zpráv podle vztahu:

kde hodnoty jsou koeficienty vybrané z . Vzhledem k tomu, že operace jsou počítány v konečném poli, má vygenerovaná zpráva stejnou délku jako původní zprávy. Každý uzel předává vypočtené hodnoty spolu s koeficienty, , použitý v úrovni .

Sink uzly přijímají tyto zprávy kódované v síti a shromažďují je v matici. Původní zprávy lze obnovit provedením Gaussovy eliminace na matici. Ve formě s redukovanou řadou řádků odpovídají dekódované pakety řádkům formuláře .

Stručná historie

Síť je reprezentována směrovaným grafem . je sada uzlů nebo vrcholů, je sada směrovaných odkazů (nebo hran) a udává kapacitu každého odkazu . Nechť je maximální možná propustnost od uzlu k uzlu . V max-flow min-cut teorém , je horní ohraničena minimální kapacity všech řezů , což je součet kapacit hran na řezu, mezi těmito dvěma uzly.

Karl Menger prokázal, že vždy existuje soubor hranových disjunktních cest, které dosahují horní hranice ve scénáři unicast , známém jako věta o maximálním průtoku min . Později byl navržen algoritmus Ford-Fulkerson pro nalezení takových cest v polynomiálním čase. Poté Edmonds v příspěvku „Edge-Disjoint Branchings“ prokázal, že horní hranice ve scénáři vysílání je také dosažitelná, a navrhl polynomiální časový algoritmus.

Situace ve scénáři vícesměrového vysílání je však komplikovanější a ve skutečnosti nelze takové horní hranice dosáhnout pomocí tradičních směrovacích nápadů. Ahlswede a kol. dokázal, že toho lze dosáhnout, pokud lze v mezilehlých uzlech provádět další výpočetní úlohy (příchozí pakety jsou kombinovány do jednoho nebo několika odchozích paketů).

Příklad sítě motýlů

Image
Síť motýlů.

Síť motýlů se často používá k ilustraci toho, jak může lineární kódování sítě překonat směrování . Dva zdrojové uzly (v horní části obrázku) mají informace A a B, které musí být přeneseny do dvou cílových uzlů (v dolní části). Každý cílový uzel chce znát A i B. Každá hrana může nést pouze jednu hodnotu (můžeme uvažovat o hraně vysílající bit v každém časovém úseku).

Pokud by bylo povoleno pouze směrování, pak by centrální spojení bylo schopné nést pouze A nebo B, ale ne obojí. Předpokládejme, že pošleme A přes střed; pak by levý cíl obdržel A dvakrát a vůbec nevěděl B. Odeslání B představuje podobný problém pro správné místo určení. Říkáme, že směrování je nedostatečné, protože žádné schéma směrování nemůže přenášet obě A a B současně do obou cílů. Mezitím trvá celkem čtyři časové sloty, aby oba cílové uzly poznaly A a B.

Pomocí jednoduchého kódu, jak je znázorněno, lze A a B přenášet do obou cílů současně odesláním součtu symbolů přes dva uzly přenosu - jinými slovy kódujeme A a B pomocí vzorce „A + B“. Levý cíl přijímá A a A + B a může vypočítat B odečtením dvou hodnot. Podobně správný cíl obdrží B a A + B a bude také schopen určit A i B. Proto se síťovým kódováním trvá pouze tři časové sloty a zlepšuje propustnost.

Náhodné lineární síťové kódování

Náhodné lineární síťové kódování je jednoduché, ale výkonné kódovací schéma, které v přenosových schématech vysílání umožňuje téměř optimální propustnost pomocí decentralizovaného algoritmu. Uzly přenášejí náhodné lineární kombinace paketů, které přijímají, s koeficienty vybranými z pole Galois. Pokud je velikost pole dostatečně velká, přistupuje pravděpodobnost, že přijímač (přijímače) získá lineárně nezávislé kombinace (a tedy získá inovativní informace) 1. Je však třeba poznamenat, že ačkoli má náhodné lineární kódování sítě vynikající propustnost, pokud přijímač získá nedostatečný počet paketů, je velmi nepravděpodobné, že by mohl obnovit některý z původních paketů. To lze řešit odesláním dalších náhodných lineárních kombinací, dokud přijímač nezíská příslušný počet paketů.

Otevřené problémy

Lineární síťové kódování je stále relativně novým tématem. Na základě předchozích studií existují v RLNC tři důležité otevřené problémy:

  1. Vysoká dekódovací výpočetní složitost díky použití Gauss-Jordanovy eliminační metody
  2. Vysoká přenosová režie kvůli připojení vektorů velkých koeficientů ke kódovaným blokům
  3. Lineární závislost mezi vektory koeficientů, která může snížit počet inovativních kódovaných bloků

Kódování bezdrátové sítě

Vysílací povaha bezdrátového připojení (ve spojení s topologií sítě) určuje povahu rušení . Simultánní přenosy v bezdrátové síti mají obvykle za následek ztrátu všech paketů (tj. Kolize, viz Vícenásobný přístup s předcházením kolizím pro bezdrátové sítě ). Bezdrátová síť proto vyžaduje plánovač (jako součást funkce MAC ), aby se takové rušení minimalizovalo. Proto jakékoli zisky z kódování sítě jsou silně ovlivněny základním plánovačem a budou se lišit od zisků zaznamenaných v kabelových sítích. Kromě toho jsou bezdrátová spojení typicky poloduplexní kvůli hardwarovým omezením; tj. uzel nemůže současně vysílat a přijímat kvůli nedostatku dostatečné izolace mezi těmito dvěma cestami.

Ačkoli bylo původně navrženo síťové kódování, které se má použít na síťové vrstvě (viz model OSI ), v bezdrátových sítích se síťové kódování široce používá buď ve vrstvě MAC, nebo ve vrstvě PHY . Ukázalo se, že kódování sítě, když se používá v bezdrátových sítích typu mesh, vyžaduje pozorný design a myšlenky, aby využily výhod míchání paketů, jinak výhody nelze realizovat. Existuje také celá řada faktorů ovlivňujících výkon propustnosti, jako je protokol vrstvy přístupu k médiím, algoritmy řízení přetížení atd. Není zřejmé, jak může síťové kódování koexistovat a neohrožovat to, co stávající algoritmy přetížení a řízení toku dělají pro náš internet .

Aplikace

Image
Krátký obrázek síťového kódování použitého na komunikaci mezi zařízeními. D1 a D2 označují zařízení, BS je základnová stanice a M1, M2 a M3 jsou určité zprávy.

Protože lineární síťové kódování je relativně nový předmět, jeho přijetí v průmyslových odvětvích stále čeká. Na rozdíl od jiných kódování není lineární kódování sítě v systému zcela použitelné kvůli jeho úzkému konkrétnímu scénáři použití. Teoretici se snaží připojit k reálným aplikacím. Ve skutečnosti bylo zjištěno, že přístup BitTorrent je mnohem lepší než síťové kódování.

Předpokládá se, že kódování sítě je užitečné v následujících oblastech:

Objevují se nové metody pro použití síťového kódování v systémech s více přístupy k vývoji softwarově definovaných drátových sítí (SD-WAN), které mohou nabídnout nižší zpoždění, chvění a vysokou robustnost. Návrh uvádí, že metoda je agnostická vůči základním technologiím, jako je LTE, Ethernet, 5G.

Splatnost a emise

Jelikož je tato oblast relativně nová a matematické zpracování tohoto předmětu je v současné době omezeno na několik lidí, síťové kódování si dosud našlo cestu ke komercializaci produktů a služeb. V této fázi není jasné, zda tento předmět zvítězí nebo přestane jako dobré matematické cvičení.

Vědci jasně poukázali na to, že je třeba věnovat zvláštní pozornost zkoumání toho, jak může síťové kódování koexistovat s existujícím směrováním, přístupem k médiím, přetížením, algoritmy řízení toku a protokolem TCP. Pokud ne, síťové kódování nemusí poskytovat mnoho výhod a může zvýšit složitost výpočtu a požadavky na paměť.

Viz také

Reference

  • Fragouli, C .; Le Boudec, J. & Widmer, J. „Network coding: an instant primer“ v 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, Vol 7, No 12, 2013.

externí odkazy