Epidemisk ruting

Epidemisk ruting er en teknikk som brukes for å rute objekt gjennom et nettverk. Navnet henspiller på biologiske system, der man i epidemier vil se spredning av smitte via biologiske vektorer og annet. Man finner det også i sosiale nettverk der rykte og holdning kan spre seg epidemisk.

Man antar et nett med N noder. Enhver node som mottar et objekt kan, for hver av sine naboer (via en direkte link) videresender objektet med sannsynlighet p. Fra perkolasjon vet man at en p>0.59 sikrer at nesten alt når frem til alle. Under denne verdien, vil nesten ingen komme frem til noen. Dette krever at nodene er tilkoblet symmetrisk og med en viss grad. Men, ideen kan tas inn i kringkasting, som jo ellers baserer seg på å sende alt til alle, og derved være mulig årsak til at nodene og nettet overbelastes.

I et datanett er det meldinger med digital informasjon som skal spres til en eller flere mottakere. Epidemisk ruting kan blant annet brukes for å spre endringsmeldinger i en distribuert database eller en distribuert hashtabell. To noder vil da utveksle oversikter over endringer de har observert den senere tid. Den som ser at noe mangler, vil sende en påfølgende henvendelse om å få en kopi for å gjøre seg oppdatert. Oppdateringen kan påskyndes ved å også inkludere selve endringen i den første epidemisk spredte meldingen. Statistisk kan man oppnå at alle er informert, i løpet av log₂N slike samkvem. Dette kalles også sladring (av engelsk gossip), som er en form for epidemisk spredning, der to noder utveksler siste nytt, forlater hverandre og med en viss sannsynlighet, sprer dette videre.

Teknikken kan brukes på mange andre områder, eksempelvis for å vite hvem som er aktive i et Peer-to-peer datanett, nyhetsformidling og også elektronisk post som skal kringkastes. En rekke varianter av sladring har vært lansert for spredning av meldinger i sensornett, der hver node har svært begrenset batterikraft, regnekraft og rekkevidde via små radioer. For å øke levetiden til nodene er det avgjørende at de er gjør så lite som overhodet mulig. Det å vedlikeholde rutetabeller er en av de arbeidsoppgaver som unngås med epidemisk ruting. Teknikken er uhyre enkel, og krever kun at noden bruker batterikraft til å (a) beregner en tilfeldig verdi og (b) videresende meldingen.

Epidemisk ruting kan også brukes for å rute en melding til en enkelt (unicast), eller en gruppe (multicast). Ulempen, er at den vil involvere mange som egentlig ikke skal motta meldingen. Fordelen er at man tilrettelegger for anynomitet gjennom kryptering, da det kun er de egentlige mottakere som kan den krypterte meldingen.