De siste årene er regnekraft blitt stadig billigere, mens båndbredde framstår som knapphetsressurs. Derfor er det grunn til å tenke over hvor lurt det egentlig er at nettverksnoder ikke gjør annet enn å videresende alle datapakker nøyaktig slik de mottar dem. Kunne man ikke effektivisert overføringen ved å bygge billig regnekraft inn i nodene og la dem kode – regne på – pakkene før de sendte dem videre?
Denne ideen, «nettverkskoding», er gjenstand for en disputas for PhD-graden ved Universitet i Bergen i morgen. Mohammad Ravanbakhsh skal forsvare sin avhandling Towards Optimal Data Transmission By Network Coding.
Enkle eksempler viser at ideen har noe for seg.
I en popularisering fra Ecole Polytechnique Fédérale de Lausanne, den sveitsiske polytekniske høyskolen i Lausanne, kalt Network Coding: An Instant Primer, vises en situasjon der to noder, A og B, utveksler datapakker gjennom det trådløse aksesspunktet S.
I et vanlig nettverk sender A datapakken a til S for videresending til B. Samtidig mottar S pakken b fra B. Siden S ikke gjør annet enn å sende videre pakkene det mottar, kringkastes først a og så b, beregnet på henholdsvis B og A.
Det kreves med andre ord at S gjennomfører fire operasjoner for at B skal få a fra A og A få b fra B. Halvparten av de to siste synes overflødige: Når S kringkaster a og b hver for seg, mottar både A og B de samme pakkene som de selv har sendt videre.
Spørsmålet er følgelig: Kunne S gjort noe med pakkene a og b, slik at det hadde vært tilstrekkelig å kringkaste én pakke for å oppdatere nodene A og B i én operasjon?
Svaret er enkelt: S kringkaster den ene pakken (a XOR b). XOR er den logiske bitoperasjonen «eksklusiv eller». Den virker slik: Hvis begge bitene er like, er resultatet 0. Hvis bitene er ulike, er resultatet 1.
Vi kan tenke oss at pakken a består av 1110 og pakken b av 1001. Da gjennomfører S operasjonen (1110 XOR 1001) = 0111, og kringkaster denne.
Hvordan skal A rekonstruere b ved mottaket av (a XOR b)? Ganske enkelt ved å bruke samme operasjon XOR på pakken den har mottatt og pakken den har sendt. (1110 XOR 0111) = 1001. Denne relasjonen er alltid sann:
a XOR (a XOR b) = b
Ved å lage en koderegel der S kringkaster (a XOR b) i stedet for a og b for seg, og der mottakerne bruker XOR på pakken de sender og pakken de mottar for å gjenopprette det som er nytt for dem, altså b, reduserer man antall overføringer i nettet fra fire til tre, altså med 25 prosent.
Instant Primer illustrerer dette slik:
Merk at denne egenskapen til XOR også ligger til grunn for andre anvendelser, for eksempel ordninger der man kan rekonstruere all opprinnelig data spredt på tre disker, med utgangspunkt i et tilfeldig utvalg av to av dem. Man lagrer a på disk 1, b på disk 2 og (a XOR b) på disk 3.
Et annet enkelt eksempel på nettverkskoding er nettverket nedenfor. De to øverste nodene skal sørge for at pakkene de mottar, skal overføres så fort som mulig til begge de nederste nodene. De mottar a og b hver for seg, og de nederste nodene skal begge motta både a og b.
Utfordringen er hvordan den midterste kanalen skal utnyttes best mulig. Noden som mottar både a og b må bestemme seg. Oppfører den seg tradisjonelt, sender den først a og så b. Sender den a, vil den nederste noden til høyre være alene om å motta både a og b: Den nederste noden til venstre mottar a to ganger.
En bedre løsningen er igjen å erstatte de to innkomne pakkene med (a XOR b), og la denne gå videre til de to nederste nodene. Den til venstre mottar a gjennom én forbindelse, og (a XOR b) gjennom den andre, og kan straks rekonstruere b. Tilsvarende kan den til høyre straks rekonstruere a. To operasjoner gjør unna det som ellers hadde krevd tre, og gjennomstrømningen i nettet er økt med 33 prosent.
Dette er svært enkle eksempler. For mer omfattende nettverk er det utviklet teori som beskriver langt mer omfattende operasjoner på pakkene.
I en e-postutveksling med digi.no sier Ravanbakhsh at nettverkskoding kan beskrives som en overføringsmetode der nodene ikke videresender pakkene slik de mottas, men gjennomfører kodeoperasjoner på dem med tanke på å oppnå ønskede mål innen gjennomstrømning, forsinkelse eller energibruk.
Ravanbakhsh sier ellers at det går et viktig skille mellom deterministisk koding, der kodeoperasjonen er avhengig av hvor noden befinner seg i nettverket, og slumpmessig koding («random») der kodingen foregår uavhengig av nodens plass i nettet. De to enkle eksemplene ovenfor viser deterministisk nettverkskoding.
I sin avhandling understreker Ravanbakhsh at nettverkskoding befinner seg på et svært tidlig standpunkt, og at det ikke implementeres i dag, med unntak av noen ytterst få protokoller som i Microsoft Content Distribution.
Nettverkskoding er mer utfordrende i trådløse nett enn i kablede.
Avhandlingen til Ravanbakhsh tar opp koding og topologier som påvirker utstrålt effekt, og foreslår algoritmer for optimal koding av trådløse nett.
Et interessant tema har med sikkerhet og personvern å gjøre: Muligheten til å bruke nettverkskoding for sikker overføring av hemmelige meldinger i et nettverk der noen av kanalene er avlyttet. Nettverkskoding innebærer at den riktige meldingen bare kan rekonstrueres dersom man har mottatt en bestemt mengde pakker. Problemet er da hvordan man skal kode med tanke på at en avlytter som ikke har full tilgang til alle kanalene, aldri skal være i stand til å kunne rekonstruere noen melding i sin helhet.
