To forskere ved Cornell University, professor Eva Tardos (bildet) og hennes doktorgradsstudent Tim Roughgarden, har laget matematiske modeller for å analysere virkningen på datanettverk av et prinsipp kjent som ”selvisk ruting” (”selfish routing”), der rutere settes opp til å sende datapakker av gårde på den stien der trafikken går fortest i øyeblikket, uten hensyn til hvordan farten vil påvirkes av de nye pakkenes inntreden. Selvisk ruting er den vanlige metoden i miljøer der man overlater til ruterne å selv bestemme veivalget.
Fredag vakte Roughgarden oppsikt ved et foredrag på årsmøtet i Denver til foreningen American Association for the Advancement of Science, kalt ”Selfish Routing and the Price of Anarchy” der han gjorde rede for hva slags virkning selvisk ruting har på utnyttelsen av kapasiteten på nettet. Selvisk routing betraktes som et ”anarkistisk” prinsipp, og poenget var å beregne hva dette anarkiet koster i form av dårlig utnyttelse av den samlede kapasiteten i et nettverk.
Det kan trekkes en lettvint parallell til biltrafikk. Hvis alle velger motorveien, ut fra den forutsetningen at fartsgrensen der er størst, vil den faktiske farten etter hvert bli mindre enn på mindre belastede bygdeveier med femtisone. Poenget med datatrafikk, er at når farten minsker på motorveien, vil ruteren oppdage det, og sende de neste pakkene på bygdeveien. Ut fra dette resonnementet vil det aldri bli trafikkork på Internett så lenge den samlede kapasiteten er stor nok.
Beregningene til Tardos og Roughgarden bekrefter dette resonnementet. Gitt en antakelse der tiden for å komme fra en node til neste øker proporsjonalt med antall pakker som ønsker å komme fram, vil prinsippet om selvisk ruting etter hvert føre til en slags likevektstilstand, kalt ”Nash flow”, der gjennomsnittstiden ligger rundt 33 prosent over den man hadde hatt med en ideell fordeling av datapakkene på alternative ruter. Med en mer kompleks antakelse om forholdet mellom fart og trafikk, der en økning i trafikk gjør større utslag på gjennomsnittsfarten, begrenses likevel den gjennomsnittlige forsinkelsen til 67 prosent av idealtiden.
Den konklusjonen Roughgarden trekker, er at det skal forholdsvis beskjedne investeringer i maskinvare for å avverge trafikkork, og at slike investeringer kan gi større gevinst enn å satse på avanserte overvåkings- og trafikkstyringssystemer. En kapasitetsøkning på 33 prosent sikrer nemlig at trafikken går med den opprinnelige kapasitetens maksimalfart.
Et annet forslag er å nyansere prinsippet for selvisk ruting, slik at rutere ikke bare skal finne den stien der trafikken i øyeblikket har størst fart, men også ta hensyn til hva slags innvirkning deres nye pakkene vil ha på den øvrige trafikken i denne åren. Hvis ens egne pakker gjør at farten senkes fra 60 til 40, kan det lønne seg å heller satse på den mindre belastede veien der alt vil fortsette i 50, selv med en vesentlig trafikkøkning. Dette lille innslaget av altruisme vil som regel være tilstrekkelig til å sørge for å begrense ”anarkiets pris”.
Det advares at å øke tallet på alternative ruter, med mulighet for å hoppe fra den ene ruten til den andre, ikke nødvendigvis vil ha en gunstig virkning. Det kan føre til at den gjennomsnittlige veilengden øker mer enn farten, slik at gjennomsnittstiden også øker. Dette fenomenet er kjent som ”Braess’ paradoks”, og kan sammenliknes med virkningen som hyppige filskift har på en overbelastet motorvei: Mindretallet som bytter fil kan ofte tjene noen minutter, men den samlede virkningen er at gjennomsnittsfarten reduseres.
For mer bakgrunnsmateriale: Søk etter strengen ”Selfish Routing and the Price of Anarchy” på Google.
