Hlavní navigace

Názor k článku Network coding v peer-to-peer sieťach od anonym - S tou výpočetnou zložitosťou by som to nevidel...

  • Článek je starý, nové názory již nelze přidávat.
  • 11. 7. 2006 18:40

    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.