Názory k článku Network coding v peer-to-peer sieťach
-
anonymníTo neni komprese. Na stazeni souboru o X bajtech stale potrebujete stahnout alespon X bajtu + rezii protokolu. To je transformace dat, ktera by mela umoznit p2p distribuci souboru typu bittorrent, ktera je schopna se vyrovnat s nekterymi okrajovymi stavy, ktere by teoreticky bittorrent nezvladl. Ovsem za cenu velke vypocetni rezie a dalsich omezeni (diky transformaci neni dost dobre mozne si natahat nejake soubory z torrentu prednostne, pripadne stahnout jen cast).
Snad jediny prinos by mel nastat v situaci, kdy torrent opusti posledni seed a vsichni klienti maji jen ruzne casti souboru. I BT sam se z teto situace vetsinou umi zotavit, tato metoda by pouze zvysovala pravdepodobnost uspechu. -
No práve by som povedal, že ten, na koho reagujete, to vystihol presne. Hlavne to rieši situáciu, kde seed opustil sieť. Ale môže to pomôcť pri distribúcii jednotlivých blokov - myslím tým toto: http://en.wikipedia.org/wiki/Network_coding#Example (pozrite si tú sieť na obrázku).
Skúste si predstaviť network coding, kde namiesto lineárnych kombinácií budete jednotlivé bloxy xor-ovať. Tým sa to trocha urýchli. -
Tak od oka by som povedal, ze prvotny seed pred jeho opustenim siete musi odoslat aspon N blokov (nezavislych lin. kombinacii), aby bola nejaka sanca ze ten subor zbytok klientov posklada.
T.j. identicka situacia s BT, kde ked seed odosle N blokov do siete klientov, tak ti uz maju tiez moznost subor poskladat.
Vzhladom na to ze ti klienti v reale tiez opustaju siet, tak network coding mozno sancu na stiahnutie zvysi, ale v specialnom pripade "seed posle N blokov a odide, klienti neodidu nikdy" to oproti BT vyhodu nema, naopak sa len zvysi mnozstvo sietovych dat o koeficienty.
Netrufam si tipovat o kolko tato metoda tu sancu zvysuje a ci to ma vyznam. -
Práve predpoklad "seed posle N blokov a odide, klienti neodidu nikdy" neplatí, v skutočnosti sa správajú klienti väčšinou opačne, po stiahnutí často prestanú zdieľať.
Na to, aby BitTorrent umožnil maximalizáciu pravdepodobnosti úspešného doťahania, musel by tracker neustále sledovať, kto čo aktuálne má (čo myslím nerobí). Tak by vedel distribuovať momentálne najzriedkavejšie bloky. Je nemožné, aby to vedel vždy presne, napr. niektorý uzol môže vypadnúť a on to zistí až po nejakom timeoute. -
Palo (neregistrovaný)Neviem o com stale tocite. Miesate protokol s datovym formatom. Na jednej strane nejaka datova teoria na druhej strane popis prenosov atd. Fakt nerozumiem. Potrebujete prenasat data s redundaciou? Potrebujete zabezpecit najprv prenos najmemej rozdistribuovanych casti? Kazdy s tych problemov sa da riesit bud na urovni datoveho formatu alebo protokolu.
To co tu riesite sa da podla mna da zvladnut nejakym protokolom bez potreby akejkolvek datovej transformacie. -
anonymníTa transformace resi to, ze lze poskladat nejaky blok dat z jinych bloku => neni treba stahnout zrovna ten konkretni blok dat. Tudiz klient potrebuje blok A, ale ten ma prave jen trebas uvodni seed, ktery je pomaly nebo v siti aktualne neni vubec => klient si zjisti, ze blok A lze poskladat kombinaci bloku X, Y (ktere uz ma) a bloku Z, ktery maji ostatni.
pr: (x = 10, y = 5, z = 1)
nekdo mi posle blok dat s informaci 2x + 3y + 10z = 45 a dalsi s informaci 5y + z = 26.
Ja sam potebuju jeste jednu informaci o vztahu x a y abych mohl soustavu vyresit, ale tentyz problem ma pravdepodobne nekdo dalsi. Ten nekdo si napr stahne informaci 3x + 2y + 10z = 50 a x + z = 11.
Takze me posle
2(3x + 2y + 10z) + 3(x + z) = 133
=> budu mit soustavu
2x + 3y + 10z = 45
5y + z = 26
9x + 4y + 23z = 133
kterouzto uz snadno vyresim. A to aniz by v siti byl pritomen blok, ktery prave shanim, stacilo mi, ze nekdo uz ma jeho linearni kombinaci, jinou nez mam ja.
Jedinej problem je v tom, ze nelze stahnout jen blok Y, coz u BT muzu. -
Palo (neregistrovaný)Ja uz len tolko ze na to existuje 100 rokov stara teoria ktora dokaze detekovat alebo opravovat N chyb v retazci M znakov. Tie rovnice sa daju lahko urobit, matematicky aparat je hotovy. Pouzivali to niektore velmi stare pakovacie programy. Proste som si povedal ze jedna (ktorakolvek) disketa z 10 sa moze uplne zmrsit a potrebujem redundaciu ktora takyto vypadok nahradi. Fakt tu znovuobjavujeme ameriku.
-
anonymníÁno trochu ste to nepochopili, tento článok nie je o redundancií dát(špeciálna technika kódovanie) napr posielam 20 bitov, na koniec našej slnečnej sústavy, pri ceste sa priemerne 5 bitov poškodí, preto pošlem 30 bitov, ktoré obashujú informáciu len 20 botov a pri poškodení ľubovoľných 10 bitov to dokžem detekovať a opraviť. Ak je chýb viac, tak mám smolu.
Tento článok, je o tom, ako z rôznych kombinácií blokov, vytiahnuť bloky ktoré potrebujem. -
K cemu je to dobre uz tu receno bylo - jde o to, ze se dosahne stejneho efektu jako kdyby se poslal ten blok, ktery by v budoucnu nejvice chybel, coz jinak nelze poznat.
Dodal bych, ze JE mozne natahat nejake soubory z torrentu prednostne, jen to neni moc podporovane. Staci, kdyz se vam povede stahnout nebo vypocitat blok (nebo lepe nekolik bloku) s vetsim mnozstvim nulovych koeficientu. Namatkou pokud mate linearni rovnice 2w+3x+7y+2z=12, x+y=1, 3x+5y=7 tak vite, ze y=2, x=-1 prestoze jste stahl 3 bloky ze ctyr. Vhodne koeficienty muzete vynutit tim, ze budete odmitat takove ktere se vam nehodi. Dosahnout tak stahnuti 350MB z 4GB je prudce neefektivni, ale pokud chcete 2GB, mohlo by to stat za to. Krome toho prakticky protokol by mohl obsahovat specialni podporu pro ovlivneni vyberu koeficientu. -
anonymníPro pochopeni staci jeden rok linearni algebry na FJFI :) Clanek je velmi zajimavy a kvalitni, diky za nej! Jen me tak napada, jestli by sla odesilana linearni kombinace (koeficienty) komprimovat, pak by se mohlo usetrit par zajimavych byte... ale asi to nepujde, kdyz musi byt vsechny koeficienty uplne ruzne...
-
Na pochopenie myšlienky zrejme stačí matematika základnej školy. Ale veľa vecí je tam skrytých. Napr. pri násobení n-bitového čísla (blok) koeficientom (16-bitové číslo) normálne potrebujete k*n bitových operácií, kde k je počet jednotkových bitov v koeficiente. Ale to násobenie sa dá robiť v 2 bytových operáciách použitím modulárnej reprezentácie.
Každý blok je prvkom telesa GF(2^(2^m)), pre predstavu si za m dosaďte napr. 23 pre 1 MB bloky (2^23=1MB*8 bitov/byte). Teleso GF(2^(2^m)) je izomorfné vektorovému priestoru dimenzie d nad telesom GF(2^(2^m/d)). Inak povedané, každý prvok (blok) sa dá vyjadriť ako vektor dĺžky d, každý prvok je 2^m/d bitové číslo. 1MB blok sa dá vyjadriť napr. ako vektor 1024*1024 bajtov. To je zrejme celkom jasné.
Trik je, že modulárna reprezentácia je homomorfizmus (alebo izomorfizmus v tomto prípade). To znamená, že násobenie môžme robiť po zložkách. Napr. použijeme vektorový priestor nad GF(2^8), každý blok sa dá zobraziť na vektor bytov. Násobenie obrovského čísla koeficientom s vektorovou reprezentáciou (0, 0, 0, ..., 0, 0, a, b) nám zabere len 2 bytové operácie.
Prevod z "normálnej" do modulárnej reprezentácie ale trvá d*log(d) (Fast Fourier Transform). Lenže my si môžme predstaviť, že bloky súboru už v modulárnej reprezentácii sú, takže žiadny prevod nás zaťažovať nebude. Nakoniec je sčítanie paradoxne pomalšie než násobenie malým koeficientom :-)
Násobenie a invertovanie v GF(2^8) sa dá jednoducho implementovať predpočítanými tabuľkami, 16kB tabuľka pre násobenie (matica 256x256) a pole 256 bytov pre invertovanie. Sčítanie je xor. -
J (neregistrovaný)Obavam se ze v praxi by vypocetni slozitost nevyvazila vyhody z toho plynouci. Navic jak bylo zmineno, problematicke stazeni jen pozadovane casti. U torrentu byva mnoho problemu zpusobeno nevhodnou volbou velikosti bloku - casto prilis velky. Pak je ona pozadovana lavina velmi zpomalena. IMO prilis vysoka cena za castecne reseni specificke situace.
-
anonymníS tou výpočetnou zložitosťou by som to nevidel až tak čierne: pre 200 MB súbor rozdelený na 100 častí (invertovanie matice 100x100) a následné násobenie to na Pentiu III 650 MHz s 512 MB RAM trvalo 3 minúty 38 sekúnd. (http://www.research.microsoft.com/~pablo/files/P2PContentDistribution.ppt, slide 20) a to nie je žiadny superstroj. To je asi jediná vec, ktorú skutočne odmerali ;-)
Vytváranie nových lineárnych kombinácií nie je o moc náročnejšie než obyčajné posielanie kusov - každé násobenie malým koeficientom je operácia s dvoma bajtami, najdrahšie je sčítanie. Aj to len preto, že čítanie z disku je pomalé, ale zase stále oveľa rýchlejšie než uploadovanie (a to rádovo). Klient vytvárajúci nové lineárne kombinácie zo starých (alebo z celého súboru) môže novú lineárnu kombináciu vytvárať postupne, tj. nemusí si ju najprv celú predpočítať a až potom posielať.Nespotrebuje na to o moc viac pamäte než klienti ostatných p2p sietí, ktoré posielajú súbory po kusoch. Toto vyplýva z výhod modulárnej reprezentácie (písal som o tom o pár príspevkov vyššie).
Ak by sa napr. robila vždy kombinácia troch predchádzajúcich (viac ani netreba), tak je to síce teoreticky 3x pomalšie než pri klientovi bežnej p2p siete, v skutočnosti to ale moc nepoznáte (pretože posielate dáta oveľa pomalšie než čo dokáže disk a procesor, a to rádovo).
Posledná výhoda network codingu je "load balancing", to znamená, že s najväčšou pravedpodobnosťou bude každý klient dotázaný na rovnaký počet lineárnych kombinácií, pretože je v podstate jedno, od koho ju stiahnete. (Nie je to tak úplne pravda, pretože klientský program bude pravdepodobne uprednostňovať uzly s rýchlym uploadom, platí to pre uzly v "rovnakých rýchlostných kategóriách").
Nakoniec, network coding som vybral skôr ako zaujímavosť. Podľa mňa by stálo za to to naprogramovať a vyskúšať. Aj keby to bolo pomalé, tak by sme aspoň mali jednoznačnú odpoveď. Zrovna tie triky s modulárnou reprezentáciou z toho robia dosť použiteľnú vec, ale nie je to vidieť na prvý pohľad.
ČLÁNKY DO MAILU