Of je nu een e-mail verstuurt, rondsurft op het internet, of een film downloadt, je wilt dat de digitale bestanden die je opvraagt zo goed mogelijk van de digitale snelweg op je computer aankomen. Het protocol dat daarvoor automatisch zorgt, heet het transmission control protocol (TCP). TCP zit ingebouwd in elke computer en elk tussenstation waarlangs het internetverkeer loopt. Het is als het ware de ruggengraat van internet. De internationale non-profitorganisatie ICANN (Internet Corporation for Assigned Names and Numbers) heeft deze standaard voor internet afgesproken en beoordeelt ook voorstellen voor verbetering.
Het protocol zorgt ervoor dat alle gegevens die worden verstuurd, worden opgeknipt in pakketjes. Elk pakketje krijgt een etiket waarop staat waar het vandaan komt en waar het naartoe moet. Vervolgens worden de pakketjes als in een estafette van het ene naar het andere tussenstation overgedragen tot ze uiteindelijk bij de ontvanger aankomen. Pakketjes van hetzelfde bestand kunnen ook via verschillende wegen uiteindelijk bij de ontvanger aankomen. Helaas kunnen er onderweg pakketjes kwijtraken of beschadigd raken. Dat gebeurt vooral op internetknooppunten waar het heel druk is.
YouTube
TCP is ontworpen om te zorgen dat de gebruiker ondanks mogelijke problemen onderweg toch de juiste informatie ontvangt. Daarvoor gebruikt het protocol een denkbeeldig raam waarin het bekijkt of het vaste aantal pakketjes dat het door het raam kan zien, wel of niet goed zijn ontvangen. En dat gebeurt op elk tussenstation. Stel dat tussenstation D door zijn raam bijvoorbeeld de pakketjes 11 tot en met 16 bekijkt. En stel dat het constateert dat 11 tot en met 14 goed zijn ontvangen, dat er iets mis is met 15 en dat 16 helemaal niet is ontvangen. Dan meldt tussenstation D aan het vorige tussenstation C dat het nog een keer de pakketjes 15 en 16 moet versturen en dat het tegelijk de nieuwe pakketjes 20 tot en met 23 kan meesturen. Zo gaat het doorsturen van pakketjes verder totdat alle pakketjes goed bij de ontvanger zijn aangekomen.
Nu zijn de mogelijkheden van het internet in de loop van de tijd veranderd. Toen mensen massaal YouTube-filmpjes gingen bekijken, werd het bijvoorbeeld belangrijker dat je elk filmpje kunt blijven kijken zonder dat het blijft hangen, dan dat precies elk datapakketje ook echt aankomt. Liever dat een datapakketje kwijtraakt, dan dat je filmpje steeds blijft hangen. Maar bij het verzenden van data is het belangrijker dat alle data aankomen dan dat de datastroom tijdelijk blijft hangen.
“In de loop van de tijd”, vertelt professor Jos Baeten van de Technische Universiteit Eindhoven, “is het oorspronkelijke TCP-protocol daarom steeds meer vervuild met nieuwe eisen. Het is steeds ingewikkelder geworden. Zeker met de opkomst van het bekijken van filmpjes merk je af en toe dat TCP begint te kraken in zijn voegen. Wij wilden TCP met nieuwe wiskundige hulpmiddelen analyseren, om te onderzoeken hoe het protocol kan worden verbeterd.”
Die wiskundige hulpmiddelen komen uit de procesalgebra, een wiskundige taal waarmee je kunt redeneren over wat er gebeurt in een willekeurig systeem met aan elkaar gekoppelde processoren of computers. De algebra beschrijft hoe toestanden in zo’n systeem veranderen. Een typische opdracht in de procesalgebra luidt bijvoorbeeld: “Stuur over kanaal C een 0 en ga dan verder met x en doe dat in parallel met het ontvangen over C van een 0 en ga dan verder met y.”
Datarace
“Procesalgebra bestaat sinds eind jaren zeventig”, vertelt Baeten. “Wat wij hebben gedaan is een uitbreiding ervan met stochastische variabelen. Dat zijn variabelen die op elk tijdstip een gebeurtenis met een bepaalde kans laten gebeuren, bijvoorbeeld het moment waarop je in een wachtrij aan de beurt komt. Een berucht probleem ontstaat wanneer een protocol met meerdere stochastische variabelen tegelijk te maken heeft. Er is een bepaalde kans dat A gebeurt en tegelijk een bepaalde kans dat B gebeurt. Vaak is een systeem ontworpen met het idee dat A altijd voor B gebeurt, maar toch bestaat er een kans dat B voor A komt. Nu kan het in de praktijk 99 keer goed gaan, maar de honderdste keer kan het ineens fout gaan. Het is onvoorspelbaar wanneer dat gebeurt. Dat noemen we de race-conditie, omdat het gaat om een soort race tussen twee of meer dingen die tegelijk kunnen gebeuren.”
Promovendus Jasen Markovski heeft samen met Baeten een stochastische procesalgebra ontwikkeld waarmee ze kunnen analyseren hoe een protocol de mist in kan gaan bij een race-conditie (zie het onderstaande kader). Met deze nieuwe procesalgebra kunnen ze wiskundig bewijzen of een protocol wel of niet een race-conditie bevat. Daarnaast kunnen ze ook kwantitatief evalueren hoe goed een protocol werkt. “Helaas zijn we uiteindelijk niet toegekomen aan het toepassen van onze algebra op TCP”, vertelt Baeten. “Maar we hebben het succesvol gedemonstreerd bij een eenvoudiger protocol, dat een soort uitgeklede versie is van TCP. In een volgend project gaan we het toepassen op TCP. We hopen dat we daar voorstellen voor verbetering kunnen uithalen. TCP moet echt beter kunnen dan de huidige versie.”
Stochastische procesalgebra
Bestaande stochastische procesalgebra’s nemen aan dat de kansverdeling van een bepaalde gebeurtenis verloopt volgens een negatieve e-macht. Bovendien nemen ze aan dat je weet wanneer twee gebeurtenissen tegelijk optreden. Markovski en Baeten ontwikkelden een algemenere stochastische procesalgebra waarin de kansverdeling niet langer een negatieve e-macht hoeft te zijn en waarin je niet van tevoren weet wanneer twee processen tegelijk optreden. Hiermee analyseerden ze bijvoorbeeld hoe de bezetting van datakanaal K afhangt van de onbetrouwbaarheid van K en van de onbetrouwbaarheid van het terugmeldkanaal L. Langs kanaal K komen de data binnen en langs kanaal L wordt teruggemeld aan het vorige tussenstation welke datapakketjes wel of niet goed zijn aangekomen. Hoe vaak het pakketje kwijtraakt, wordt aangegeven door een stochastische grootheid. Het resultaat van de analyse geven de onderzoekers weer in een driedimensionale grafiek, die eruitziet als een berglandschap voor de bezettingsgraad. De top in het berglandschap leert je vervolgens welke betrouwbaarheden voor de communicatiekanalen je moet realiseren voor een optimale bezetting van communicatiekanaal K.
Zie ook:
De homepage van Jos Baeten De homepage van Jasen Markovski
Dit artikel is oorspronkelijk verschenen in het boek Omringd door informatica van wetenschapsjournalist Bennie Mols (www.benniemols.blogspot.com). Het boek is geschreven op initiatief van het BRICKS-consortium (Basic Research in Informatics for Creating the Knowledge Society) en het Centrum Wiskunde & Informatica. Omringd door informatica is in december 2009 gepubliceerd.