Vlákno názorů k článku
Network coding v peer-to-peer sieťach
Palo (neregistrovaný)
10. 7. 2006 23:02
Nepochopil som
Prosim vas pomozte mi. Cela tato "teoria" je o kompresii? Preco kompresiu robit takto komplikovane?
uživatel si přál zůstat v anonymitě
10. 7. 2006 23:40
Re: Nepochopil som
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.
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.
d0h (neregistrovaný)
11. 7. 2006 10:40
Re: Nepochopil som
ty jsi to taky moc nepochopil. nicmene souhlasim s tim, ze to nema prakticky prinos.
aura:60
11. 7. 2006 11:36
Re: Nepochopil som
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.
Skúste si predstaviť network coding, kde namiesto lineárnych kombinácií budete jednotlivé bloxy xor-ovať. Tým sa to trocha urýchli.
aura:65
11. 7. 2006 15:24
Re: Nepochopil som
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.
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.
aura:60
11. 7. 2006 17:26
Re: Nepochopil som
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.
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ý)
11. 7. 2006 20:55
Re: Nepochopil som
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.
To co tu riesite sa da podla mna da zvladnut nejakym protokolom bez potreby akejkolvek datovej transformacie.
uživatel si přál zůstat v anonymitě
12. 7. 2006 14:51
Re: Nepochopil som
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.
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ý)
12. 7. 2006 15:00
Re: Nepochopil som
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.
technocrat (neregistrovaný)
12. 7. 2006 17:39
Re: Nepochopil som
a) Error correcting codes != Rateless erasure codes
b) K vasmu prispevku vyssie: ked nabuduce budete nieco tvrdit, tak pridajte naznak dokazu/algoritmu. Hocikto dokaze tvrdit milion veci, ktore nikto nevyvrati.
b) K vasmu prispevku vyssie: ked nabuduce budete nieco tvrdit, tak pridajte naznak dokazu/algoritmu. Hocikto dokaze tvrdit milion veci, ktore nikto nevyvrati.
uživatel si přál zůstat v anonymitě
14. 7. 2006 13:08
Re: Nepochopil som
Á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.
Tento článok, je o tom, ako z rôznych kombinácií blokov, vytiahnuť bloky ktoré potrebujem.
aura:99
16. 7. 2006 21:09
Re: Nepochopil som
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.
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.
