Bart stukken Bjorn Schobben Wietse Jorissen
Verslag Project Gedistribueerde Systemen Platform OS De software is ontwikkeld onder windows (zowel XP als 7).
Taal Er is gebruik gemaakt van C++ om het spel te ontwikkelen. Verder is er gekozen voor QT voor het voorzien van de grafische user interface en multithreading.
Multicast Dit programma maakt gebruik van MSMQ (Microsoft Message Queuing) om multicast te voorzien. Dit is enkel beschikbaar op pc’s die uitgerust zijn met Windows XP Professional en later (o.a. Vista, Windows 7). Dit systeem vergt wel van de gebruiker om de extra windows onderdelen te installeren die onder message queueing vallen. MSMQ voorziet reliable non-ordered multicast. Het onderliggende protocol dat voor de multicast gebruikt wordt, is Pragmatic General Multicast (PGM). Het “pragmatic” gedeelte duidt op het feit dat het protocol basic reliability biedt, maar geen ordering. Het verzekert het afleveren van de gestuurde data, en in het ergste geval het weergeven van onherstelbaar pakketverlies. Alle data-paketten (ODATA) worden genummerd, zo weet de ontvanger steeds of hij alle paketten ontvangen heeft. Indien er toch een pakket niet aankomt, stuurt de ontvanger een NAK (NotAcknowlegded) pakket uit, met daarin het nummer van het pakket dat de ontvanger wil krijgen, maar nog niet kreeg. De originele zender ontvangt deze NAK en verstuurt op zijn beurt een NAK Confirmation (NCF) ook met het nummer van het missende pakket. Een NAK Confirmation onderdrukt mogelijke NAKs van andere ontvangers in het subnet die nog geen NAK gestuurd hebben (dit om het overstelpen van de zender te voorkomen). De zender stuurt daarop repair-data uit (RDATA) naar de ontvangers. Tussen de ODATA pakketten door worden ook Source Path Messages (SPM) paketten uitgestuurd, de welke een router of ontvanger informeren over zijn next-hop upstream.
De gebruikte technieken Consensus: Omdat een consistente toestand van het spel verwacht wordt tussen alle clients is er gebruik gemaakt van een consensus-achtig systeem. Dit houdt in dat elke client met elk bericht, die de toestand van het spel zal veranderen, akkoord moet gaan. Er wordt gebruik gemaakt van een soort consensusset, hierbij worden de berichten die (ongeveer) tegelijk verstuurd worden verzameld in 1 set, deze set wordt consistent gemaakt door uitwisseling met de andere clients, en deze set wordt dan geordend. Als de set consistent is gemaakt over alle clients mag deze pas verwerkt worden. De enige berichten die niet beslist worden aan de hand van consensus zijn de initialisatie berichten omdat deze slechts te toestand van 1 client beïnvloeden en de heartbeats die op zichzelfgeen enkele toestand beïnvloeden. Omdat het voor consensus zeer belangrijk is over welke view we een bepaald bericht sturen, gebeurt er ook al een stukje membership op deze laag. D.m.v. de heartbeats kan er continu bepaald worden wie er aanwezig is en wie niet (meer). Zulke veranderingen in de aanwezigheid worden dan gemeld aan de membership die hiervoor het nodige consensus bericht zal opstellen.
Ordering: Het bepalen van de ordering van berichten gebeurt d.m.v. een dubbele Lamport klok samen met een random nummer. De eerste Lamport zorgt ervoor dat de kleinste (en dus initiële) waarde bijgehouden wordt, zodat een pakket nooit te ver uitgesteld zou worden. Dit is vergelijkbaar met de consensus set, want handelingen die tijdens dezelfde Lamport waarde gebeuren horen in 1 consensus set. Hierna bepaalt eigenlijk de random waarde wie eerst komt. Dit leek de meest eerlijke oplossing in een spelomgeving, omdat zo niemand met goede of slechte verbinding of klok bevoordeeld zou worden. Toch is er de mogelijkheid in de engine zelf deze als klok te gebruiken, maar dan zal men zelf extern de klokken moeten gaan synchroniseren (bv ntp). De tweede Lamport is de uiteindelijke Lamport, en dus deze bepaald mee de ordening. Vooral omdat elk packet toch naar elke client gestuurd wordt dankzij de consensus laag, weet men ook dat bepaalde packeten zouden vertraagd zijn op andere clients. Dit geeft dat men zelf niet van lokale ordening afhankelijk is en enkel beroep doen op de reliability van de lagen erboven.
Membership: Om ervoor te zorgen dat een nieuwe speler toevoegd wordt, en deze vervolgens geupdate wordt met de gamestate en zodoende geen enkel bericht misloopt, (zoals o.a. tijdens het afhandelen van zijn deelname) is er een dynamic membership systeem voorzien. Wanneer een nieuwe client een multicast address joint zal hij een hearbeat uitsturen. Als hij merkt dat er al een spel gaande is zal deze een join request uitsturen (los van de consensuslaag). Waarna hij in een wachttoestand overgaat waarin hij wacht op een initialisatie bericht die de toestand van het spel en de deelnemers moet bevatten. Wanneer de andere clients deze request opmerken zullen deze een membership bericht uitsturen via de consensuslaag. Deze garandeert dat bij deze nieuwe client bij iedere andere client op hetzelfde moment als deelnemer zal beschouwd worden. Hierna zullen ze een initialisatie bericht uitsturen en ieder bericht dat volgt zal ook door de nieuwe client moeten goedgekeurd wordt.
Op deze manier wordt ervoor gezorgd dat een nieuwe client geen informatie ontgaat tijdens het initaliseren. Bij het weggaan van een spel wordt eigenlijk hetzelfde principe gehanteerd. De client die stopt zal melden dat hij vertrekt en dan wordt eigenlijk hetzelfde soort membership bericht uitgestuurd. Wanneer er een client onvrijwillig wegvalt zal dit opgemerkt worden aan de hand van heartbeats. Wanneer een client gedurende een bepaalde tijd geen antwoord geeft zal er ook een membership bericht rondgestuurd worden via consensus. Van de gecrashte client zal ook niet verwacht worden dat hij akkoord gaat met het bericht in dit geval.
Vereisten Variabel aantal spelers: Er is in principe geen limiet op het aantal spelers dat kunnen meedoen aan het spel. Iedere client die probeert te joinen zal dynamisch toegevoegd worden aan het spel. De spelers hoeven hun beurt niet af te wachten: er is een “cooldown” tijd van 1 seconde voorzien waarop de speler moet wachten om een zet te mogen doen. Verder zijn er geen restricties op het maken van een zet. Dimensies van het bord: De speler kan bij het opstarten van zijn spel de gewenste dimensies van het bord instellen. Indien hij de eerste speler is in de multicast group worden dit ook de instellingen, zo niet dan worden de huidige gebruikte instellinge aangenomen van de andere clients. Variabele winconditie: De speler kan bij het opstarten van het spel zelf kiezen hoeveel schijven er op rij gezet moeten kunnen worden voordat iemand wint. Net zoals bij de dimensies wordt ook de winconditie overgenomen een eventueel bestaande sessie. Spelers kunnen ten alle tijden het spel vervoegen of verlaten: Er wordt voorzien dat de speler het spel op eender moment kan verlaten. Zelfs indien een client onvrijwillig het spel verlaat hoort dit opgevangen te worden. Kiezen van kleur: Er is een uitgebreide optie voorzien om een kleur te kiezen. Het is bovendien onmogelijk om een kleur te gebruiken die al gehanteerd wordt door een eerdere deelnemer. Ook als 2 spelers zich tegelijk aanmelden zal de kleur uniek zijn per speler. Consistente volgorde van zetten: De applicatie is, zoals al vermeld, voorzien van global ordering en consensus die garandeert dat alle zetten consistent geordend worden bij iedere deelnemer.
Extra's: Pauzeren: Er is een mogelijkheid voorzien om het spel te pauzeren. Dit wil zeggen dat geen enkele deelnemer een zet zal kunnen doen totdat er iemand terug depauzeert. Crash detection: Zoals er vermeld is er voorzien dat ook onvrijwillig verlaten van het spel gedetecteerd en afgehandeld wordt.
Handleiding Nadat het programma gestart is, krijgt men een dialoogvenster te zien met daarin enkele velden die al voorzien zijn van standaardwaardes. Deze velden zijn:
-
Group IP: Het IP-adress van de multicast groep om op te joinen.
-
Port: Poort waarop gejoined wordt.
-
Dimension: De breedte en hoogte van het vierkante spelbord waarin wordt gespeeld.
-
Win condition: Het aantal schijven dat de speler op rij moet zetten om te winnen.
Indien deze velden geen input bevatten, kan men het spel ook niet joinen. In het geval dat de input correct is, zal het programma proberen de multicast groep te joinen. Men krijgt een bericht of men al dan niet de eerste speler is die de groep joined. De eerste speler bepaalt de dimensie van het spelbord en ook zijn instelling van de winconditie wordt gebruikt. Zo niet neemt men gewoon deel aan het spel zoals het werd opgezet door de eerste speler.
Wanneer de speler een spel joint kan hij het verloop van het spel al waarnemen. Maar vooraleer men kan beginnen spelen, dient men een kleur te kiezen. Dit doet men door op de knop met opschrift “Pick a color” te klikken, en hier een kleur te selecteren. Indien deze kleur al bezet is, wordt er gevraagd een andere kleur te kiezen. Nu kan men zichzelf en zijn kleur zien in de spelerslijst aan de rechterkant van het scherm. Verder staat er onder de spelerslijst ook de speler identificatie (Player ID) die men heeft toegewezen gekregen, alsook de winconditie van het huidige spel. Eens er een kleur gekozen is, kan men op het bord klikken om een schijf te plaatsen. Na iedere zet is er een “cooldown” voorzien van 1 seconde, in deze periode kan je geen zetten meer doen. De speler die het eerst het aantal schijven (bepaald door de win-conditie) op een rij kan plaatsen, wint het spel. Om het spel te stoppen ga naar File->quit. Om het spel te pauzeren ga naar File->pause.