Aanpassing routers kan datatransport versnellen

C|Net Azië bericht dat twee Amerikaanse onderzoekers voorgesteld hebben om routers minder zelfzuchtig te laten functioneren, om zo een versnelling van de gemiddelde datatransportsnelheid op Internet te bewerkstelligen. In hun toespraak 'Selfish routing and the price of anarchy' stellen Eva Tardos en Tim Roughgarden dat de manier waarop routers momenteel bepalen welk traject gekozen zal worden voor het verzenden van data, verre van optimaal is. Tot op heden bekijken de schakelstations welke van de mogelijke routes op dat moment het snelste is en sturen hun gegevens vervolgens over dat bewuste pad, totdat ook die route verstopt raakt. De router zal dan overstappen op een eerder genegeerde route en het proces herhaalt zich. Dit resulteert in een zogenaamde 'Nash flow', die de gemiddelde reistijd van een packet met 33% kan vertragen ten opzichte van een ideaal systeem.

De oplossing die de onderzoekers voorstellen, gaat ervan uit dat het voor de gemiddelde snelheid op een netwerk beter is als de routers niet alleen uit eigenbelang handelen, maar ook 'overwegen' welke actie gunstig is voor het netwerk als geheel. In plaats van gegevens te blijven sturen tot een datapad verstopt raakt, zouden de routers vooraf aan het zenden van data moeten bepalen wat het effect is de verzending op het bewuste traject. Hoewel dit zou betekenen dat een router in sommige gevallen niet de snelste route kiest, zou een dergelijke aanpak een positieve uitwerking kunnen hebben op de gemiddelde datasnelheid. Overigens merken de onderzoekers ook op dat het toevoegen van onderling verbonden pathways niet per se hoeft te leiden tot snelheidswinst:

Adding more interconnected pathways to the network can also be counterproductive because of an effect called Braess' paradox, the researchers said. According to the paradox, the packets of information would simply hop from one path to another--much like drivers switching lanes in a traffic jam--actually slowing down all the other packets traveling on those pathways.

[...] The scientists said these mathematical analyses are based on hypothetical networks. "The extent to which the real Internet conforms to these mathematical models is not yet well understood," Roughgarden said.

Reacties (52)

[ijdod]

Probleem blijft dat in grote netwerken kosten per MB een belangrijke metric is. Het is niet ongebruikelijk dat nu niet de meest optimale route genomen wordt, omdat een bepaalde carrier goedkoper is. Dat routing probleem los je er niet mee op. Theoretisch een leuk verhaal, dat wel.

[miw]

Volgens analyse van internet informatiestromen blijkt inderdaad dat dit soort commericiele overwegingen de overhand hebben bij internet backbone verbindingen. Hierdoor onstaan een aantal regionale clusters die tamelijk los van elkaar staan. Dit routing algorithme zal deze situatie niet veranderen. Als er al een congestie probleem is, kan dat veel eenvoudiger opgelost worden door een black fiber te verlichten, of door een nieuw WLDM techniek te gebruiken. Daar is meer winst te halen dan met een slimmer algorithme.

[ijdod]

Precies. Daarbij heb ik meer vertrwouwen in algoritmes waarvan de pro's en con's uit de praktijk bekend zijn, dan in een nieuw algoritme, om maar te zwijgen van de bugs in de code die dat met zich meebrengt.

[Verwijderd]

De enige manier waarop dit kan werken is als minimaal 70% (gokje) van alle internet routers hier aan meewerkt. Probeer dat maar eens voor elkaar te krijgen.

Wel een erg simpel idee natuurlijk; ik (router1) heb 2 mogelijkheden: sturen naar router2 met een ping van 10ms en een max doorvoer van 100Mbit waarvan al 80% gebruikt óf router3 met een een ping van 15ms en een doorvoersnelheid van 10Mbit waarvan 0% gebruikt. Hij zal dan voor router 3 kiezen, terwijl dat nu via 2 zou gaan (HEEL simpel gezegd).

Maar nog belangrijker lijkt me: als router1 de beste route berekend moeten eigenlijk meteen álle mogelijke routes worden bekeken. Het kan namelijk zijn dat het tót router3 dan wel iets sneller is, maar wie zegt dat de verbinding van router3 naar router3.1 wel goed is, etc., etc.

Al met al een heel simpel idee, maar het implementeren heeft nog wel wat voeten in de aarde lijkt me...

[Gwannoes]

Het zou inderdaad mooi zijn als een groot deel van het internet met zulke routers zou werken.
Maar binnen de wat grotere bedrijfsnetwerken kan het ook al goed van pas komen hoor.

[Jefrey Lijffijt]

Het probleem is dat je datatransport inderdaad veel sneller kan maken, maar dat het berekenen van wat optimaal is gaat aan de hand van het doorrekenen van een graaf, wat een NP-Compleet probleem is. Het volledig doorrekenen van de mogelijke paden en effecten erop kost n! (dus n*n-1*n-2*....*2*1) tijd. Dit is dus praktisch onmogelijk als je meer dan 100 routers (knopen op de graaf) wilt doorrekenen.

Dit is in ieder geval erg oud nieuws, hier denken ze al een jaartje of 30 over na.

Daarnaast staat er niet in wat 'Nash flow' inhoudt. Volgens mij houd dat in dat iedere router voor zichzelf bedenkt wat optimaal is en dat gewoon doet, dit kan een niet optimaal antwoord geven, maar aangezien routers meestal in het bezit zijn van commerciele bedrijven is dit natuurlijk de enige manier, want je wilt niet dat je als bedrijf een router installeerd en iedereen er vervolgens gebruik van gaat maken zodat je eigen snelheid daar onder leidt.

[Denhomer]

Handige manier om op een niet al te moeilijke manier alles wat te versnellen. Ik vraag me wel af of het extra rekenwerk van de router opweegt tegen de snelheidswinst ?

[Fairy]

Ik denk dat dat wel meevalt, de route word in een tabel bijgehouden en als een route is uitgestippelt zou de router deze voor een bepaalde tijd gaan gebruiken. Dat moet met de huidige capaciteit van de routers wel te doen zijn.

[blade181]

Ja maar de vraag is dan ook is deze communicatie binnen een AS of is deze communicatie tussen verschillende AS systemen.

En de vraag is dan ook welke protocollen worden gebruikt? Rip, IGRP, OSPF. En tussen verschillende AS'en BGP?

Ik dacht dat dynamische pad bepaling alleen bekijkt of een route up is en zodra die down is een andere te kiezen.

Want is dat niet het geval dan zijn die routers wel superslecht ingesteld.

[snowbo]

Op internet wordt volgens mij alleen maar met BGP gewerkt.. Rip is zowiezo niet aan de orde die kan maar een beperkt aantal hops.. en convergentietijd met ospf wil jij niet weten op een wereldwijd netwerk ..

IS-IS is opzich ook wel snel maar ik weet niet hoe dat werkt in zeer grote netwerken heb ik alleen nog maar is mee mogen spelen..

[arjankoole]

RIP en OSPF worden bij ISP's vaak wel gebruikt op het eigen netwerk, maar niet over trans-at links en dergelijk, de core backbone routers en switches kennen alleen BGP over het algemeen.

(gelukkig )

[zion]

IGRP zal niet gebruikt worden, is een Cisco Proprietary Protocol, en werkt alleen maar in een 100% Cisco netwerk

[Verwijderd]

Routes hebben vaak een puur economische reden. De lijnen van KPN zijn stervensduur ten opzichte van andere landen en providers. Daarom was het vroeger zo dat een pakketje van nederland via de eigen link naar engeland ging, vervolgens via de AMS-IX naar de VS ging en van daar terug naar europa kwam om uiteindelijk op de bestemming in Frankrijk aan te komen. Puur alleen omdat de KPN lijn naar parijs duurder was dan de transatlantische link. En dan hebben we het nog niet eens gehad over de links van bijvoorbeeld chello. Die stuurden vaak via hele vreemde omwegen om maar onder kosten uit te komen. Dat het daarna huilen met de pet was wanneer iemand die route niet snapte en vervolgens herprogrammeerde hoef ik niemand uit te leggen.

[gp500]

Volgens mij doen ze dat steeds meer, echt leuk van chello.

[LiMy]

uhu, maar wat is dan nog de functie van een firewall?

edit: damn, verkeerde bolletje aangevinkt, comment was bedoelt op de firstposter van deze thread

[mxcreep]

Een firewall en een router zijn 2 verschillende dingen...

[Verwijderd]

Wel eens gehoord van routers met build-in firewall features?

http://www.zdnet.com.au/newstech/security/story/0,2000024985,20263906, 00.htm

...en dan doel ik niet op de normale access-lists...

[Gwannoes]

Dat ligt er natuurlijk aan wat voor hardware je er in stopt. Het zijn natuurlijk een beperkt aantal instructies, en je hoeft niet een hele GUI zoals WindowsXP op een scherm te toveren. Dat scheelt nogal in de vereiste specificaties. Ik denk dat dit zeer zeker wel realtime prestaties kan verbeteren

[k-oz]

precies, dat is mijn ged8e ook direct. en de controle die hierop uitgevoerd moet worden is ook niet misselijk.

[Venator]

Beetje het wiel opnieuw uitvinden dit. Waarom denk je dat er binnen veel grote netwerken en dataintensieve netwerken aan loadbalancing gedaan wordt? Komt een beetje op hetzelfde neer. Route A is zeer druk, dus gaat er naar Route B wat meer. Als je de treshhold voor meerdere routes op een bepaald niveau instelt, dan heb je hetzelfde effevt. Ik vind het eigenlijk gek dat dit binnen routers nog niet gedaan wordt, d8 dat de meeste cisco gsr's dit al deden eerlijk gezegd.

[Lennie]

Het probleem is dat het op dit moment al heel moeilijk is om te bepalen wat de beste route is, er is zelfs heel weinig bekend over de snelheid van verbindingen en de drukte van een lijn, je hebt alleen direct contact met je buren, terwijl er wel 10 routers tussen zitten, via buur A en 8 via buur B, wat denk je dat men meestal kiest in zo'n geval ?

Wat men ook veel doet is dan kunstmatig het aantal routers ophogen om ergens te komen, terwijl dat toch al iets was dat niks zegt.

great.

Lees maar eens hoeveel informatie men werkelijk heeft voor het routeren:

http://www.rfc-editor.org/rfc/rfc1771.txt

[Burat]

Doet me denken aan de film "A Beautiful Mind". Daar wordt dit principe mooi uitgelegd aan de hand van een groep vrienden die een groep vrouwen wil versieren . De naam "Nash" zegt me trouwens ook wel iets...

[irritableskillz]

Doet me denken aan de film "A Beautiful Mind". Daar wordt dit principe mooi uitgelegd aan de hand van een groep vrienden die een groep vrouwen wil versieren . De naam "Nash" zegt me trouwens ook wel iets...

Ja idd daar moest ik ook direct aan denken . Is dit niet waar die John Nash een nobelprijs voor gewonnen had? Het equilibrium ofzo? Had er volgens mij mee te maken dat het niet goed zijn als iedereen voor zichzelf het beste zou nemen, maar dat er ook rekening gehouden moest worden met wat het beste zou zijn voor iedereen (in dit geval het netwerk dus).

[General_Failure]

Klopt, Nash is een van de grondleggers van de (niet-cooperatieve) speltheorie. Dit is ook zo'n probleem, want als alle routers zich netjes zouden gedragen, wordt het internet er beter van (zoals in dit artikel beschreven is).
Stel nu dat in een dergelijke situatie een router een pakketje moet versturen. Hij kan dan kiezen voor de sociale of voor de goedkope oplossing. In de praktijk wordt dan vaak de goedkope oplossing gekozen, zodat deze router nu beter af is. Maar in toekomst zullen andere routers dit ook doen, zodat het internet steeds meer verstopt raakt en uiteindelijk zijn alle routers slechter af dan in de beginsituatie.

Dit probleem staat bekend als het Prisoner's Dilemma en is op heel veel gebieden van toepassing. Nash was degene die dit als eerste analyseerde.

[Mujo]

Voor wie meer wil lezen over
de speltheorie (gametheory), John Nash, e.d.:

classes.igpa.uiuc.edu/j-giertz/ECON400/game%20theory-pbs.htm

home.planet.nl/~verh2375/johnnash.htm

www.math.kun.nl/abeautifulmind/

[^Mo^]

offtopic:
Highlander?

[Verwijderd]

Klinkt goed. Ik ben erg gecharmeerd van deze theorie.

IPv6 zal ook datatransport versnellen. Als ik het goed begrepen heb: minder grote routing tabellen dankzij IPv6. Dat houdt in wat minder verkeer tussen routers onderling en vooral: minder load. Daarbij komt: iets meer overhead maar wel beter gebruik makende van de TCP/IP headers.

Lijken me dan 2 goede oplossingen voor dit probleem!

[Verwijderd]

De recente IOS releases die Cisco meelevert met routers zijn al IPv6 prepared. Over het hoe en het wanneer overschakelen is een discussie op zich.

Denk hierbij aan een mogelijke strategie om het 'oude' IPv4 te laten voor wat het is en een nieuw op IPv6 gebasseerd internet te bouwen zonder IPv4 equipment te upgraderen. M.a.w. vanaf een bepaald tijdstip geen nieuwe netwerken/nodes meer toe te voegen aan het oude netwerk.

Of kiezen voor een upgrade festijn waar Cisco, Nortel, etc. zeker niet armer van zullen worden. De partijen die echter wel diep in hun buidel zullen moeten tasten zijn de grote telecommers. En daar staat dus het project stil, omdat deze jongens zich wezenloos diep in het rood hebben gewerkt door te investeren in peperdure licenties van 3G mobiele netwerken.

En nu juist de telecommers zullen in hun ASsen ( Autonomous Systems, een grote wolk van netwerken) moeten beginnen met upgraderen, voordat de rest kan overstappen.

[voodooless]

Dit is dus een soort QOS (Quality of Service) voor routers.

En dan ff reactie op The Jester: ATM is een heel ander protocol dan IP en heeft een heel ander toepassingsgebied. Verder is IP over ATM natuurlijk ook mogelijk.

Overigens merken de onderzoekers ook op dat het toevoegen van onderling verbonden pathways niet per se hoeft te leiden tot snelheidswinst

Het is idd net zo met autosnelwegen. Als je meerder afspilsingen maakt die uiteindelijk bij hetzelfde punt uitkomen, lost dat het fileprobleem niet per definitie op (hoewel er dus meer wegen ter beschikking staan). Vreemd maar waar...

[Verwijderd]

dit is grote flauwekul. ze l*llen uit hun nek.

de snelste route = de route met meeste bandbreedte.

en "interconnected pathways" zijn wel degelijk nuttig, zij reduceren het totaal aan netwerkverkeer.

Deze scientists zijn m.i. netwerk bobo's die hebben geprobeerd iets op kleine schaal te simuleren, en komen dan ook zelf niet voor niks met de conclusie dat deze gesimuleerde modellen wellicht niet opgaan voor het internet als geheel.

[jfk]

en "interconnected pathways" zijn wel degelijk nuttig, zij reduceren het totaal aan netwerkverkeer.

Dat lijkt me toch stug. Het totaal aan netwerkverkeer neemt niet af door meer routes aan te leggen. Vergelijk: het totaal aantal voertuigen wat van A naar B rijdt blijft gelijk, ongeacht of de snelweg 2- of 5 baans is. Wel zal de netwerkbelasting lager zijn.

[Parody]

Is toch wel een beetje waar, hoor. IP congestiebeheersing bestaat voor een belangrijk deel uit het weggooien van pakketjes. Routers die een pakket niet binnen een zekere tijd kwijt kunnen aan een andere router dumpen 'm in het bittenbakje. Na een zekere time-out wordt het pakketje opnieuw verzonden door de bron. Als dit veel gebeurt zou er een andere route gekozen moeten worden voor die bestemming. Als de route vast ligt voor bepaalde doelen, en er op die route voldoende bandbreedte is, wordt het netwerk dus per saldo minder belast, want je hebt minder retransmits.

[Swinnio]

ze l*llen uit hun nek.

Beargumenteer dat fatsoenlijk, schrijf een paper, en je wordt een stuk serieuzer genomen dan met dit statement.

de snelste route = de route met meeste bandbreedte.

Natuurlijk niet! Wel eens van congestie of load gehoord? Ik verstuur mijn data liever via een 10Mb verbinding met een 5% load dan een 100Mb verbinding met een load van 99%.

Deze scientists zijn m.i. netwerk bobo's die hebben geprobeerd iets op kleine schaal te simuleren, en komen dan ook zelf niet voor niks met de conclusie dat deze gesimuleerde modellen wellicht niet opgaan voor het internet als geheel.

Dat is ook de enige mogelijke werkwijze. Je moet eerst op kleine schaal simuleren om een idee van de werking te krijgen. Pas daarna kun je overgaan tot de volgende stap, namelijk de vraag of het ook toegepast zou kunnen worden op mondiale schaal. Of wou jij het Internet meteen als proefkonijn gebruiken voor een wellicht niet functionerend algoritme?

[Verwijderd]

met iets andere woorden wordt dat dus "dit is grote nulkoek".
Als een verbinding potdicht zit is het iets anders, maar een lijn zal nooit permanent dichtzitten.
een 100Mb verbinding met 90% load heeft meer bandbreedte beschikbaar dan een 10Mb verbinding met 5% load.
Bovendien moet je de totale verblijftijd van het pakketje meerekenen. Vergelijk met een snelweg: daar kunnen meer auto's overheen rijden als alle auto's sneller rijden. Bij tijdelijke files iedereen over de provinciale weg sturen heeft geen zin, want dan zit die binnen no-time verstopt.
Vergeleken met een 100Mb verbinding levert een 10Mb verbinding dus maar een marginale bijdrage aan de totaal beschikbare bandbreedte. Een deel van de auto's over de provinciale weg sturen helpt je niks, want dat maakt de knooppunten alleen maar drukker, wat onnodig het verkeer stagneert.

Het steeds wisselen van routes is funest voor de performance, omdat dat onnodige overhead geeft voor de routers.
Dat zeggen de onderzoekers idd zelf:
"According to the paradox, the packets of information would simply hop from one path to another--much like drivers switching lanes in a traffic jam--actually slowing down all the other packets traveling on those pathways."

Wat eventueel zin heeft is om routes intelligent aan te leggen met een permanent karakter, gebaseerd op herkomst en bestemming.
Als je vanuit zeg Utrecht naar de universiteit van Utrecht surft gaat het verkeer via de amsterdam exchange. Het klinkt logisch als de ISP een lijntje zou hebben direct naar de uni.
Maar als die verbinding niet genoeg bandbreedte heeft houdt het op.
Zo gaat verkeer naar sommige delen in oost-europa vaak via new-york. simpelweg omdat die lijnen meer bandbreedte hebben. Daardoor neemt de totale verblijftijd van een netwerkpakket af, waardoor er meer bandbreedte overblijft, ook al wordt een onnodig grote afstand afgelegd.

Routers dermate intelligent maken levert een vergrote storingsgevoeligheid op. Beter heb je 1 betrouwbare route, dan 3 onbetrouwbare routes.
Nu klaagt men al dat er (te) veel verkeer is tussen de verschillende routers, dat zou alleen maar verergeren als we de ideeen van de onderzoekers zouden implementeren.

Sinds de glasvezel is in de meeste gevallen is de bekabeling niet de belemmerende factor, maar de netwerkapparatuur zelf.

M.i. wegen de voordelen (enkele procenten performancewinst) niet op tegen de nadelen (onbetrouwbaarheid).

[arjankoole]

waar je eerder aan moet denken als je dit leest zijn de kosten.

de meeste providers moeten toch echt wel betalen voor hun transit verkeer. Peering aan de andere kant is gratis. Dus als die routers opeens dingen over de transit pijp gaan smijten, omdat dat socialer is ( groot vraagteken!) dan kost het veel meer, dan als ie dat verkeer gewoon netjes over de peering zou doen.

snelheids winst? Nee.

stel ik stuur nu iets van een machine in de colo naar een server bij xs4all. Dan is dat nu razendsnel waar het moet zijn. Wat als dit niet over de peering die we met xs4all hebben zou gaan, maar over de transit? Dan gaan we niet van R'dam naar A'dam naar Diemen, maar van R'dam naar A'dam, naar London, naar New York, naar A'dam naar Diemen

veel trager dus. (valt in principe wel mee, maar het is niet de snelste, en zeker wel de duurste route).

[Verwijderd]

Wat ze wel eens mogen doen is dat die verrekte firewall volledig uit te schakelen is.

Die firewall is toch vaak vreselijk irritant

[Verwijderd]

Ehm, ze hebben het hier niet over je E-Tech routertje waarmee je thuis je netwerkje aan je provider koppelt. Het gaat hier om de grote routers die de knooppunten van het internet als zodanig zijn.

[feuniks]

Voor je thuismodem ben je trouwens ook al snel uitgepoept: je stuurt pakketjes van je interne net werk naar de gateway (router) van je provider. Je hebt geen route die je zou kunnen kiezen, en je kunt dus ook niet overschakelen naar een andere route als de gateway van de provider verstopt begint te raken...

[Verwijderd]

S33kEr:

Wat loop jij nou te blaten. Daar gaat het helemaal niet over...

[NuKeFaCe]

LOLOLOL