1.  A szökőkútkódok és alkalmazásuk a végpontok közötti megbízható adatkommunikációban

1.1. Áttekintő

Napjainkban egyre többen és többen fogyasztanak hétköznapjaik során valamilyen online tartalmat, akik kiszolgálása érdekében a világ több pontján elhelyezett szerverek (szerverközpontok) felelnek. Ilyen nagyobb tartalom szolgáltató például a Youtube, a Vimeo, vagy épp a Facebook is. Élő streameket, televízió adásokat, vagy videófelvételeket nézhetünk bárhol, bármikor. Az otthoni személyi és a hordozható számítógépek fejlődésével, ezzel járó nagyobb teljesítményével, a szolgáltatott anyagok egyre jobb  és jobb minőségűek lehetnek, melyek arányosan egyre nagyobb sávszélességet igényelnek a tökéletes felhasználói és fogyasztói élményhez. A fogyasztói piac átalakulásával pedig, egyre nagyobb arányban használnak ezen célokra különféle vezetékes/nélküli eszközöket. Az internetes adatkommunikációt az 1990-es évek elejétől, a HTTP (Hypertext Transfer Protocol) végzi a TCP (Transmission Control Protocol) protokoll segítségével, melyek együtt egy szabványos közeget biztosítanak bármilyen adat megbízható, veszteségmentes és sorrendtartó átvitelére. A TCP szabványosítása már 1981-ben (melyet azóta bővítettek a nagysebességű átvitelekhez igazodóan), a http szabványosítása pedig a 90-es évek elején megtörtént. Ezek a szabványok még az akkori alapvetően vezetékes és néhány kilobájtnyi kommunikációhoz nyújtottak megoldást, mely a mai fentebb említett egyre különfélébb eszközök és közegek számára nem mindig a legoptimálisabb. Például  a vezeték nélküli eszközök esetében az átviteli közeg, mely nem csak hogy helyben, de folyamatosan időben is jóval drasztikusabban változik mint a vezetékes esetben. A csatornát használó hasonló  készülékeink, az elektromágneses zajokat keltő berendezéseink, valamint a természetben keletkező további a közegre ható zajok összesége folyamatosan változtatja az átvitel megbízhatóságát, és így az átvihető adat mennyiségét is [1]. A zajok hatására olyan csomaghibák is jelentkezhetnek, melyet a jelenleg használt fizikai rétegben lévő hibajavító funkció nem tud megfelelően korrigálni/észlelni, mint például egy nagyon zajos városi helyszínen. Csomaghibák esetén pedig, a hibás adatot a sikeres kézbesítésig újra és újra le kell kérdezni a forrástól. Az újraküldés [1] egy szabványos eljárása az egyedi tartalom továbbításnak, amelyben a fogadó fél, értesíti a küldőt, hogy mely darabjai hiányoznak a küldött anyagnak negatív, vagy pozitív nyugtázások által. Az újraküldés megkövetel egy vissza irányba kialakított csatornát, így csak olyan esetekben használható ahol ez megoldható, valamint kis számú csomagveszteségek, és kis számú kliens esetén. Azonban például egy TV adás közvetítése során több relatív nagy veszteségű kapcsolat a sok újraküldéssel könnyen túlterhelheti a szervert. Túlterhelést okozhat több nagy késleltetésű kapcsolat is, az időben hosszúra nyúló nyugtázások miatt, a küldőnek több ideig kell a memóriában tartani a küldött anyagot, így kevesebb tartalom szolgáltatására leszünk képesek. Tehát az újraküldés több szempontból is többletterhelést okoz a szervernek, ezen kérések feldolgozása során.

1.2. A TCP működési elve

A TCP fő komponense a torlódásszabályozás, mely a torlódás észlelésén alapszik. [2] A kezdetekben ezért egy időzítő felelt, melynek letelte a csomag nyugtázásának hiányában a hálózat torlódását jelezte, habár több esetben is a visszajelzés hiányát nem a torlódás, hanem a zavarok jelentették. Manapság az optikai kábeleken ezen zavarok elhanyagolhatóak, azonban a vezeték nélküli átvitelben igen jelentősek tudnak lenni. Tehát míg az eredeti elgondolás az optikai hálózaton optimálisnak is tekinthető, más közegben jelentős teljesítménycsökkenést okoz. A különböző TCP verziók különböző időzítőket, limiteket, és ezek értékeinek meghatározására  különböző algoritmusokat használnak. A legjelentősebb a retransmission időzítő, mely minden egyes csomag elküldésekor elindul. Ha nem érkezik visszajelzés, és a időzítő lejárt, az adatot újra küldjük, ha megérkezett az időzítőt megállítjuk, és elküldjük a következő csomagot. Tehát a megfelelő idő megválasztása kiemelten fontos. Ha túl kicsit választunk, túl sokszor küldünk újra csomagokat, ha túl nagyot választunk, nem használjuk ki teljes mértékben a hálózat kapacitását, az elvesztett csomagok visszajelzésére várakozással. A másik ilyen fontosabb limit a torlódási ablak, mely az elküldött, még nem nyugtázott csomagok számát határozza meg. Alapvetően a sikeres nyugtázások időben megérkezése esetén növelik a limit értékét, így növelve a sávszélességet, ellenkező esetben pedig csökkentik annak értékét, így csökkentve a sávszélességet.

1.3. Digital Fountain based Communication Protocol

Az elmúlt években a Távközlési és Médiainformatikai Tanszéken fejlesztett DFCP az előző fejezetekben részletezett problémákra, tehát a manapság használt TCP protokollra szeretne nyújtani egy új univerzális, számos közegben hatékonyabb alternatívát [2]. A koncepció legradikálisabb ötlete, hogy a TCP által használt torlódáskezelést egyszerűen elhagynák a kommunikációból, így minden kommunikáló eszköz a lehető legnagyobb sebességével küldhetne adatot a világhálón. Az elvesztett adatok egy hatékony szökőkút (RaptorQ) algoritmussal lehetnének visszaállíthatók. Ezzel a megoldással kiaknázhatnánk a jelenlegi hálózatunk teljes kapacitását, valamint olcsóbbá tehetné jövőbeli eszközeink előállítását is a kevesebb átmeneti tároló alkalmazásával. A torlódáskezelés teljes elhagyásából és a maximum sebességgel való adatküldésből, óhatatlanul következik az átvitel során létrejövő nagyszámú csomagvesztés, a hálózati eszközök folyamatos terhelése miatt. Így nem minden csomag kerül továbbításra. Ezen csomagvesztések azonban egy megfelelő szökőkútkódoláson alapuló algoritmussal kiküszöbölhetőek lennének.

1.4. Szökőkútkódok

A szökőkút kódok úttörő algoritmusok az internet számára, ahol az adatok továbbítása több kis részlet csomag továbbításán alapszik, melyek akár hibát tartalmazhatnak, vagy akár el is veszhetnek. [3] Az egyszerű fájl átviteli protokollok egyszerűen K darabra vágják a küldendő adatot, majd egész addig küldözgetik az egyes darabokat, míg a fogadó meg nem erősíti annak hibátlan célba érését. Ezzel szemben a szökőkút kódok véletlenszerűen generálnak a forrásból egységnyi csomagokat, melyeknek bármely K < N darab halmazából nagy eséllyel visszaállítható az eredeti küldött adat. Használatának előnye, hogy olyan közegekben is lehetőség nyílik megbízhatóbb átvitelre, ahol csak egy irányú kommunikáció lehetséges. (Pl. Digitális műholdas televíziózás). A szökőkútkódok használatával egy tetszőleges hosszú adatból végtelen mennyiségű csomagot generálhatunk. A fogadó képes visszaállítani az eredeti adatot bármely halmazából a fogadott csomagoknak, mely alig nagyobb elemszámú mint az eredeti adat. Tehát, alapvetően a közegbéli veszteségek nem befolyásolják annyira az adatküldést. Az első ilyen szökőkút algoritmus a Luby Transform kód (lásd később), azonban ez még nem tudott alacsony komplexitású megoldást biztosítani. A Raptor kódok melyek jelentős elméleti továbbfejlesztései az LT kódnak, az első olyan kódok, amelyek lineáris idejű kódolást és dekódolást nyújtanak. A kódoló algoritmus végtelen hosszú folyamot tud generálni a forrásból, melyet a fogadó nagy eséllyel vissza tud állítani. Már néhány, a forrás méretén felül érkező csomag fogadása esetén a dekódolás sikeressége majdnem 100%. A +2 szimbólum vétele esetén a sikertelenség már kisebb mint egy a millióhoz. Ráadásul, ha a dekódolás sikertelen, csak várni kell egy újabb csomag megérkezéséig, és egy újabb próbát tehetünk az adat visszanyerésére.

1.4.1. Luby Transform kód

A Luby Transform kód egy szökőkút algoritmus, melyeknek futási ideje akár lineáris is lehet a üzenet méretének függvényében (pl. raptor). [4] Eljárás egy csomag előállítására röviden (encoding):
  • A forrást (adatot) K darabra tördeljük (csak az első körben)
  • Véletlenszerűen választunk egy 0 < n < K számot (fokszám)
  • Majd szintén véletlenszerűen választunk n darab töredéket, a K darabból
  • Ezeket a töredékeket XOR-oljuk egymással, majd ezen adatok mellé eltároljuk mely csomagokat XOR-oltuk össze
  • Végül CRC kóddal kiegészítve elküldjük a csomagot.
Amennyiben van visszairányú kapcsolat is, ez a folyamat egész addig ismétlődik, míg a fogadó fél vissza nem tudta állítani a küldött forrást (adatot). Eljárás a forrás visszaállítására röviden (decoding):
  • Ha a pillanatnyilag fogadott csomag hibás, vagy már kaptunk egy ilyet, a csomagot eldobjuk.
  • Ha a kapott csomag hibátlan, és még nem kaptunk ilyet, valamint a csomagban egynél több forrásdarab modulo-ja van kódolva, a csomagot XOR-oljuk az összes eddig kapott teljesen dekódolt forrásdarabbal.
  • Ha az így kapott n-1 fokszámú csomag még n!=1 fokszámú, egy átmeneti tárolóba (buffer) helyezzük azt.
  • Ha egy n=1 fokszámú csomagot kapunk, ami egy forrástöredék is egyben, az összes átmeneti tárolóban lévő, ezen forrástöredéket tartalmazó csomaggal XOR-oljuk (így minden csomag fokszáma csökken egyel).
  • Mikor egy csomag fokszáma n=1-re csökken, a csomag adata a fogadott üzenet tárolójába kerül.

1.4.2. Raptor kódok

A Raptor kódok az első olyan ismert szökőkút algoritmusok, melyek lineáris kódolási és dekódolási tulajdonságokkal bírnak. [5]

T kódolás, dekódolás = O(1)

Az első Raptor kódot Amin Shokrollahi iráni matematikus 2004-ben publikálta. A raptor kód egy jelentősen feljavított változata az LT kódolási eljárásnak, és már például a DVB-H szabvány része is, ugyanis már egy kisebb hibajavító adattöbblet elküldésével jelentős szolgáltatás minőségbéli javulást érhetnek el.

2.  RaptorQ (RFC6330) kódolás működése

2.1. Áttekintő

A kódolás menete A legfejlettebb Raptor kód a RaptorQ. [6]
  • Első lépésben, mielőtt a RaptorQ algoritmust lefuttatnánk a forrásadaton, a forrást Z >= 1 blokkra daraboljuk, amit forrásblokknak nevezünk. Majd ezekre a forrás blokkokra (source block) alkalmazzuk a RaptorQ kódoló algoritmusát. Minden blokk kap egy egyedi – Source Block Number (SBN) – sorszámot, nullától kezdődően.
  • Második lépésben minden forrásblokkot feldarabolunk K darabra, így a töredékek – melyet forrás szimbólumnak nevezünk. Minden töredéket sorszámozunk az előzőhez hasonlóan, melyet ESI – Encoding Symbol Indentifier – azonosítónak hívunk.
  • Harmadik lépésben a forrásszimbólumokat tovább tördelhetjük forrás al-szimbólumokra, az előzőkhez hasonlóan, azonban darabszámuk nem kell hogy megegyezzen K-val.
  • Negyedik lépésben köztes szimbólumokat állítunk elő a forrás szimbólumokból.
  • Ötödik lépésben elküldjük a forrás szimbólumokat a vevőnek, majd a köztes szimbólumokból javító szimbólumokat hozunk létre.
  • A vevő oldalon előszőr a kapott csomagokból visszaállítjuk a köztes szimbólumokat, majd ezekből, és a többi forrásszimbólumból a hiányzó forrásszimbólumokat.

2.2. A forrás előkészítése

A forrás blokk és forrás al-blokkok előállítása 5 paramétertől függ:
  • F: a forrás hossza bájtban
  • Al: szimbólum
  • T: szimbólum méret bájtban
  • Z: a forrás blokkok száma
  • N: a forrás al-blokkok száma, minden egyes forrás blokkban
A PARTITION[I,J] függvény: Bemeneti paraméter: [I (felosztandó blokk mérete), J (egyenlő darabra)] Kimeneti paraméter: [IL, IS, JL, JS], ahol: IL=felkerekít(I/J), IS=lekerekít(I/J), JL= I – IS * J, darab hossz JS= J – JL Így kapunk IL darab * JL hosszú, és JS darab * IS hosszú darabot Legyen Kt = felkerekít(F/T), tehát forráshossz/szimbólum méret: (KL, KS, ZL, ZS) = Partition[Kt,Z] (TL, TS, NL, NS) = Partition[Kt,Z] Ezután a forrást felosztjuk Z=ZL (KL hosszú) + ZS (KS hosszú) forrásblokkra. Ha Kt*T > F, a forrást kibővítjük Kt*T-F db null bájttal, így kapunk egy K’ hosszú kiterjesztett forrást. Ezután minden forrásblokkot N = NL + NS al-blokkra osztunk. Az első NL db K1 TL*Al bájt méretű,  a maradék NS db al-blokk pedig K darab TS*Al bájtos szimbólumot tartalmaz.

2.3. Kódolt csomag szerkezete

Minden csomag tartalmazza az alábbiakat:
  • SBN
  • ESI
  • Kódolt szimbólumok
Minden forrásblokkot egymástól függetlenül kódolunk. Minden kódolt csomag a forrásblokkból generálunk, amit az SNB azonosít. Az ESI 0-tól K-1-ig a forrás szimbólumokat azonosítja, K-tól kezdve pedig a generált hibajavító szimbólumokat. Minden csomag csak forrás vagy csak javító csomagokat tartalmaz. Egy csomag tartalmazhat bármennyi forrás szimbólumot vagy javító szimbólumot ugyanazon forrásblokkból. Minden forrás szimbólum csomagban az ESI az első X-edik kódolt szimbólumot azonosítja, ami után az X+1, X+2 … X+G-1 csomagok következnek G darab szimbólum esetén. Hasonlóan a javító csomagoknál az ESI az első javító csomag sorszámát jelöli.

2.4. Kódolás

RaptorQ kódolás működése, blokkvázlat

Első lépés: Köztes szimbólumok generálása (előkódolás).

Ebben a lépésben L darab C köztes szimbólumot generálunk a K’ darab C’ forrás szimbólumból, ahol L > K’. [7] Két fázisú algoritmust használunk. Az első fázisban az LDPC kód segítségével állítunk elő redundáns szimbólumokat a forrás szimbólumokból. Az LPDC kód generálja a legtöbb köztes szimbólumot (Low Density Parity Check Code) az előkódolás alatt, melyeknek kódolása / dekódolása lineáris a forrás blokk méretével. A második fázisban a HDPC kóddal generálunk kis mennyiségű HDPC  (High Density Parity Check Code) szimbólumot,  melyeknek kódolása / dekódolása szintén lineáris. 

Második lépés: Kódolás

A második lépés során minden X > K’ csomaghoz, javító szimbólumokat generálunk a köztes szimbólumok véletlenszerű felhasználásával. LT kódolás segítségével a köztes szimbólumokból kódolt szimbólumokat állítunk elő, hogy aztán az LT dekódolás során visszaállíthassuk belőlük a köztes szimbólumokat. Az előny az, hogy ahelyett, hogy minden egyes köztes szimbólumot vissza kellene állítanunk, a beépített redundancia miatt csak egy nagyobb részét kell visszaállítanunk a köztes szimbólumoknak, és aztán ezt a redundanciát felhasználva állíthatjuk elő a maradék köztes szimbólumokat.

2.5. Dekódolás

A dekódolónak minden esetben tudnia kell a következő adatokat:
  • T: szimbólum méret
  • K: szimbólum szám a forrás blokkban
  • K’: szimbólum szám a kiterjesztett forrás blokkban
A dekódoláshoz N >= K’ szimbólumra van szükségünk.
  1. A kapott szimbólumokat egy mátrixba helyezzük, majd Gauss eliminálunk, végezetül megfelelően összegezve a kódolt szimbólumokat, visszakapjuk a köztes szimbólumokat.
  1. A megkapott forrás szimbólumokhoz tartozó sorokból megállapítjuk, hogy mely köztes szimbólumokat kell összegezni a hiányzó forrás szimbólumok visszaállításához, majd visszaállítjuk a forrás szimbólumokat.

3.  RaptorQ kódolás teljesítményelemzése különböző tesztesetek segítségével

3.1. Előkészítés

A félév során a végső feladat, a szökőkút RaptorQ algoritmus, és az új protokoll koncepció megismerése után, egy már C++-ban implementált RaptorQ algoritmus teljesítmény elemzése volt, különböző paraméterek függvényében. A forráskód a következő GitLab repoból érhető el jelenleg: https://www.fenrirproject.org/Luker/libRaptorQ A projekt letöltése után, ubuntu Linux alatt a cmake, libevent, libevent-dev, libunbound-dev telepítése után a leírás alapján hiba nélkül lefordult. Lépések:
  • cd libRaptorQ/
  • mkdir build
  • cd build
  • cmake -DCMAKE_BUILD_TYPE=Release ../
  • make -j4
  • sudo make install
Mivel Linux alatt nem ismerek könnyen használható IDE-t, és az Xcode-hoz már hozzászoktam, a libRaptorQ-t megpróbáltam a Mac-en is lefordítani. A project még nem volt tesztelve ilyen környezetben, így több függőséget is kikellett elégíteni a megfelelő forduláshoz. Ezen unix-os eszközöket, a macports segítségével tölthetjük le.  A profiling (kódoptimalizáció) viszont továbbra sem működik, mellyel egy teszt utáni újra fordításnál akár, de nem feltétlen, kicsit gyorsabb kódot kaphatnánk. Miután a kód sikeresen lefordult, és előállt a libRaptorQ.dylib dinamikus állomány, lefuttattam kipróbáltam a projektben lévő tesztprogramokat is. Sajnos ezekkel csak korlátozott paraméter állítási lehetőség volt, és az output sem volt túl könnyen feldolgozható. Úgy döntöttem, hogy a kapott eredményeket Matlab segítségével szeretném ábrázolni, valamint az összes paraméter hatását megvizsgálni. Miután megértettem a tesztprogram működését, amit elsőre eléggé nehezen olvashatónak találtam, elkezdtem annak teljes átírását az igényeimnek megfelelően. A végeredmény egy, a fentebb fordított dinamikus binárishoz linkelt, a bemeneti paramétereket és futási időket megfelelően mátrixba elhelyező, majd egy meghatározott fájlba lementő program lett.

3.2. Tesztkörnyezet

A teszteléshez használt programom forráskódja: https://github.com/majonez/libraptorQ_tester Tesztelői környezet:
  • Intel Core i5 6400@3.10GHz,
  • 16GB DDR4 RAM,
  • Gigabyte Z170X-Gaming-3,
  • Mac OS X 10.11.5,
  • Xcode 7.3.1
A tesztelés során 3 processzormagot használtam a 4 rendelkezésre állóból, a gyors de mégis pontos teszthez. Annak érdekében, hogy az eredmények ne torzuljanak az esetek kevesebb, mint 1 százalékában előforduló más programok okozta CPU terheléstől vagy a dekódolási sikertelenségek miatt (amit a K mennyiségű csomag elégtelensége okozhat), minden egyes tesztfázis 3x futtatam le. Ezután kiszűrtem az átlaguktól jelentősen eltérő értéket és újra számoltattam az átlagot a maradék értékek alapján. Minden teszt során egyetlen blokknyi adaton végeztem a teljesítmény méréseket, így az „átvitt” adatok mennyisége megegyezik a blokkmérettel. Tehát, forrásméret=blokkméret.

3.3. Teszteredmények

LibRaptorQ futási idő az alszimbólumszámok függvényében Forrásméret: ~220KB (K=K_max), veszteség=50%, szimbólum méret=1024bájt Az 1. ábra mérési eredményeiből látható, hogy az al-szimbólumok számától a futási idő nem függ. LibRaptorQ futási idő az eldobott csomagok függvényében Forrásméret: ~220KB (K=K_max), szimbólum méret=1024bájt, al-szimbólum szám=64 A 2. ábrából látható, hogy a hibátlan vétel kivételével, melynél a dekódolásra szánt idő közel 0, a dekódolás futási ideje nem függ az elvesztett csomagok arányától, és a szükséges idő megegyezik a kódolásra szánt idővel. A teszt során az elvesztett csomagok „kiválasztását” egy véletlen generátor végzi. Így két azonos százalékú teszt során is különböző indexű csomagok vesznek el. LibRaptorQ futási idő az szimbólumméret függvényében Forrásméret: ~220KB (K=K_max), veszteség=50%, al-szimbólum szám=64 Ahogy a 3. ábrán láthatjuk, a futási idő nagyban függ attól, hogy egy kódolandó blokkot hány szimbólumra bontunk fel. A még elfogadható teljesítményt jelen esetben 512 és 1024 körül találhatjuk. Az átvitt adat mennyisége K*sizeof(uint_32)=226kB, így például 1024 választása esetén 1000/64*226=3.5MB/s sávszélességet érhetünk el egyetlen processzormag használata esetén. Az 1024 byte szimbólum nagyság viszont nem teljesen optimális az Ethernet számára, ugyanis egy keretben ~1500byte fér el. Az első optimálisnak mondható szimbólum méret a 128byte, ugyanis 1500-128*11=92byte amiből még a szimbólumokhoz tartozó azonosítók is használnak el bájtokat. Így közel 100%-osan kihasználhatjuk a jelenlegi szabvány szerinti keretet. LibRaptorQ futási idő a K méret függvényében Veszteség=50%, al-szimbólum szám=64, szimbólum méret=128 bájt A 4. ábrán látható, hogy a futási idő a forrásblokk méretétől négyzetesen függ. A mérés a 128 bájtos szimbólumméret megválasztásával készült. Az előzőeket végig gondolva, a kimenő sávszélesség növelhető valamelyest a szimbólumok egy blokkon belüli számának csökkentésével. LibRaptorQ futási idő konstant arány mellett Veszteség=50%, al-szimbólum szám=64, szimbólum szám=~10 Az ábráról látható, hogy ha biztosítjuk a konstans blokk/szimbólum méret arányt, tehát a szimbólumok számát egy blokkban, a (de)kódolás sebessége valóban  lineárisan függ a forrásblokk méretétől. savszel_konst A 6. Ábrán látható, hogy az elérhető maximális sávszélesség 10 szimbólum/blokk esetén, kb. 12.5MB/s ~ 100Mbps

4.  Értékelés

A teszt során kapott eredmények hasonlóak a nyílt forráskódú, javában írt RaptorQ implementáció sebesség eredményeivel is: https://github.com/openrq-team/OpenRQ Összességében, a RaptorQ és a DFCP ötlete is nagyon jó, és az algoritmus néhány elenyésző kivételt kivéve, az összes esetben sikeresen előállítja az eredeti adatot. Manapság viszont már jóval túlléptük a 100Mbps-es sávszélességet, így ebben a formában, CPU-n futtatva, egy hálózati protokoll részeként nem tudom elképzelni a kódot. Egyszerűen túl sok az elpazarolt CPU idő.

5.  Tanulmányozott irodalmak jegyzéke

  • [6] M. Luby, Qualcomm Incorporated, A. Shokrollahi, EPFL, M. Watson, Netflix Inc., T. Stockhammer, Nomor Research, L. Minder – „RaptorQ Forward Error Correction Scheme for Object Delivery” https://tools.ietf.org/html/rfc6330