Subsections
4. Das Framework ``MMPGP2P''
Dieses Kapitel stellt Architekturen zum Betrieb eines Spieles auf einer
P2P-Basierten Plattform vor. Die sich daraus ergebende Schnittstelle soll
eine möglichst breite Palette von Spielen unterstützen.
Zunächst wird eine einfache Architektur entwickelt, das den Betrieb eines Spieles in
einem P2P Netzwerk unterstützt. Diese Architektur wird dann weiter verfeinert
und später im Kapitel durch einen zentralen Server ergänzt. Da es sich dann nicht mehr um
ein reines P2P System handelt, nennen wir diese Architektur ``P2P-hybrid''.
Im weiteren Verlauf werden damit verbundene Probleme aufgezeigt und die Entwicklung
verfeinert bzw. verbessert. In diesem Kapitel wird noch keinerlei Implementierung
vorgeschlagen.
4.1.1 Beteiligte Einheiten und Nomenklatur
Im folgenden werden immer wieder Begriffe auftauchen, die hier kurz definiert werden
sollen.
4.1.1.1 Endanwendung
Wird im Folgenden von der ``Endanwendung'' gesprochen, dann ist damit ein
Spiel gemeint, das die hier vorgestellte Technik als Schnittstelle
einsetzt. In der später vorgestellten Implementierung ist Beispielcode einer
solchen Endanwendung enthalten, welche mithilfe eines einfachen Spiels die Nutzung
der Schnittstelle demonstriert.
In der Regel bezieht sich der Begriff auf diejenigen Teile einer Anwendung,
die von dieser Arbeit nicht zur Verfügung gestellt werden.
Die genauen Funktionen und Regeln eines bestimmten Spiels sind spezifisch
für den jeweilige Spieltyp und für die Bereitstellung einer Schnittstelle unrelevant.
4.1.1.2 Peers
Grundsätzlich sind am Spiel zwei Typen von Einheiten (Peers) beteiligt:
Auf der einen Seite ``Trusted'' Peers: dies sind vom Betreiber kontrollierte Comutersysteme,
auf denen Server-Prozesse oder bestimmte RegionController-Prozesse laufen (später als
initiale RegionController bezeichnet).
Auf der anderen Seite stehen ``Untrusted'' Peers:
dies sind Computersysteme der Spieler, die sich dynamisch ins Netzwerk einklinken und es
normalerweise nach einer Sitzung wieder verlassen. Diese Peers sollen oder müssen einen Teil
ihrer Rechenzeit zur Verfügung stellen,
indem sie RegionController-Prozesse für die Verwaltung einer Region der Spielewelt
ausführen und der ``Allgemeinheit'' zur Verfügung stellen.
4.1.1.3 Spieler und Avatar
Als Spieler bezeichnen wir eine reale Person, die ein Computersystem zur Verfügung hat und
die Endanwendung ausführt bzw. benutzt. Der Spieler meldet sich mithilfe
dieser Endanwendung und einer Benutzername-Passwort-Kombination am Netzwerk an
und erhält dann die Kontrolle über seinen Avatar.
Der Avatar ist die zum Spieler gehörige virtuelle Spielfigur, die
er (ausschließlich) über die Endanwendung innerhalb der Spielewelt steuern kann.
In der Regel besitzt ein Avatar nur einen Besitzer/Spieler, es kann unter Umständen jedoch
vorkommen, dass ein Spieler mehrere Avatare besitzt. Ob dies überhaupt erlaubt ist, ob er diese
Avatare parallel steuern kann oder welche Regeln zur Benutzung eines Avatars sonst bestehen, ist
nicht Bestandteil dieser Arbeit und wird den Endanwendungsentwicklern überlassen.
4.1.1.4 Client
Ein Spieler startet in der Regel eine Endanwendung, die am Netzwerk teilnimmt.
Mit dem Begriff Client ist hierbei der Prozess auf dem Computersystem des Spielers gemeint,
der während einer Sitzung Spielzüge sendet und fortlaufend Updates über den Zustand
der Welt erhält. Nicht gemeint ist damit der Spieler selbst oder dessen Hardware,
ebenso wenig der Avatar des Spielers.
Da die Daten auf dem Computer des Spielers frei zugänglich sind, kann diesem Prozess
nicht vertraut werden. Es muß also dafür Sorge getragen werden, dass der Client
keine Informationen erlangt, die er ausnutzen kann. Es muß auch das Ausführen von
ungültigen oder manipulierten Kommandos verhindert werden, die der Client versendet.
4.1.1.5 Server
Dieser Begriff bezeichnet einen Prozess auf einem Computersystem des Betreibers.
Dieser Prozess läuft auf einem kontrollierten System und ist vertrauenswürdig.
Der Server ist Zuständig für Authentifizierung der Spieler und Verteilung der Clients
an die Zuständigen RegionController. Zu jedem Zeitpunkt weiß der Server darüber
Bescheid, in welcher Region der Spielewelt sich ein Spieler aufhält (bzw. mit
welcher Region der Client kommuniziert).
Der Server nimmt eine zentrale Rolle ein und ist daher möglichst ausfallsicher
zu implementieren. Ohne Server können sich keine neuen Clients anmelden und es
treten Probleme bei der Verwaltung der Regionen auf. Dazu später mehr.
4.1.1.6 RegionController (RC)
Ein RegionController, oft als RC abgekürzt, ist ebenfalls ein Prozess auf einem
beteiligten Computersystem. Die RCs verwalten einen Teil der Spielewelt, erhalten
Befehle von den Clients, die in dieser Region zugegen sind und senden ihrerseits
Änderungen des Zustandes der Spielewelt an diese zurück. Da ein RC sensible Informationen
über eine Region der Spielewelt erhält muß dafür gesorgt werden, dass diese Informationen
nicht zum Erringen eines Vorteils für einen Spieler ausgenutzt werden können (Cheating).
In der Regel laufen RC-Prozesse auf den Computern der Spieler im Hintergrund,
jedoch spricht nichts dagegen, dass auch Systeme ohne Client- oder Serverprozesse
einen oder mehrere Instanzen eines RegionControllers starten. Durch den plötzlichen
Verlust der Verbindung eines RegionControllers mit dem Netzwerk
(was bei DSL oder sonstigen dynamisch angebundenen Systemen durchaus häufig auftreten kann),
dürfen sich keine Schwierigkeiten für den weiteren Betrieb des Spiels ergeben.
Dazu siehe 4.2.2.
Ein RegionController, der auf den Erhalt der Kontroller über eine Region wartet und
bis dahin zur Verfügung, wird ``freier RegionController'' genannt.
4.1.1.7 Sichtweite
Die Sichtweite ist ein Maß dafür, in welchem Radius rings um den Avatar Objekte erspäht
werden. Idealerweise handelt es sich bei dem Gebiet, das der Avatar einsehen kann, um
einen Kreis mit dem Avatar als Mittelpunkt und einem Radius entsprechend der Sichtweite.
Figure 4.1:
Sichtweite eines Avatars
Die drei hier dargestellten Avatare erblicken allesamt das Objekt. Avatar A und B
sehen sich gegenseitig, weil ihr Abstand kleiner als die Sichtweite beträgt. Avatar C
jedoch sieht die beiden Avatare A und B nicht. |
Es sei an dieser Stelle jedoch bereits erwähnt, dass die Sichtweite auf der Ebene
des hier vorgestellten Frameworks nicht fix ist, sondern sich aus technischen Gründen
innerhalb eines Intervalles bewegt. Dieses Intervall kann jedoch von einer Implementierung
angepasst werden. Das Framework garantiert eine minimale und eine maximale Sichtweite.
Dem Entwickler steht es jedoch frei, innerhalb der Endanwendung eine fixe
Sichtweite zu implementieren, in der Regel wird hierfür der Minimalwert des Intervalls
gewählt. Informationen über Objekte, die weiter entfernt, sich aber noch innerhalb des Intervalls
befinden, erreichen den Client trotzdem und bieten in diesem Fall eine Möglichkeit zum
Erlangen von unfairen Vorteilen. Dies sollte vom Entwickler berücksichtigt werden.
4.1.2 Aufteilung der Spielewelt
Die Spielewelt sollte möglichst einfach abstrahiert werden. Daher wird die Aufteilung
der Welt durch x-y-Koordinaten durchgeführt (z-Koordinaten können von der
Implementierung unterstützt werden). Um eine konsistentes Konzept der Aufteilung
zu erreichen, werden Gebiete bei Bedarf aufgesplittet in zwei oder vier Teilgebiete.
Bei hoher Konzentration von Objekten oder Spielern in einer Region wird die
dadurch anfallende Last verteilt.
Eine Region ist rechteckig und wird anhand ihrer unteren linke Ecke sowie ihrer
Höhe und Breite eindeutig beschrieben.
Figure 4.2:
Aufteilung der Spielewelt in Regionen
Diese Spielewelt wurde in zwei Schritten geteilt. Zunächst wurde die komplette
Welt in die Regionen R1 und R2 geteilt. Danach wurde R2 in die Regionen R21 und R22 aufgeteilt. |
Jeder Spieler bewegt sich innerhalb einer Region und darf Regionen auch wechseln.
Die Ausführung des Wechsels einer Region ist Sache der hier vorgestellten Architektur und
bedarf keines Eingriffes der Endanwendung.
Welche Regionswechsel von der Spielidee her erlaubt sind, ist Sache des Spiele-Herstellers (z.B. Wechsel durch
Grenzüberschreitung oder Wechsel durch Teleporter) und wird hier nicht weiter behandelt.
Die Aufteilung der Spielewelt geschieht dynamisch und während das Spiel weiterläuft.
Wird eine Region zu voll, dann wird sie in kleinere Regionen aufgeteilt.
Die neuen Regionen müssen nicht zwangsweise den gleichen Flächeninhalt aufweisen,
sie müssen lediglich eine rechteckige Form aufweisen.
4.1
Eine Region wird entweder entlang einer vertikalen oder horizontalen Geraden in zwei Hälften gesplittet,
oder es wird ein Punkt innerhalb der Region festgelegt, der die Region viertelt.
In der Regel wird eine Region in zwei kleinere aufgeteilt, die Aufteilung in vier Regionen
ist Spezialfällen vorbehalten und wird durch eine Sequenz von drei Halbierungen ersetzt.
4.1.2.1 Verwaltung der Regionen im RegionTree
Da die Aufteilung der Regionen hierarchisch funktioniert, bietet sich die Verwaltung
in einem Binärbaum an (Siehe Abbildung 4.3).
Dabei werden die verschiedenen Stufen der Aufteilung in den Knoten
gespeichert. Die Blätter enthalten dann eine Region und die zur Region gehörigen Daten.
Figure 4.3:
Aufbau eines RegionTrees
|
4.1.3 Kontrolle einer Region
Für jede Region gibt es eine kontrollierende Instanz, welche die Spielzüge
der Spieler in dieser Region auswertet und einen neuen Zustand der Region
berechnet. Diese kontrollierenden Instanzen nennen wir RegionController (RC).
Figure 4.4:
Kontrolle und Verwaltung der Regionenen durch RegionController (RC)
|
Die RegionController sind, wie in der Einleitung beschrieben, Prozesse auf
Computersystemen. Die Clients der Spieler kommunizieren mit dem RegionController
der Region, in der sie sich gerade aufhalten.
In dieser ``einfachen'' Architektur kommunizieren die Clients bidirektional
mit ihrem jeweiligen RegionController. Der Avatar des Spielers wird dabei vom
Spieler in der Region bewegt, es können Aktionen ausgeführt und eventuell
Objekte manipuliert werden. Dies ist jedoch wieder Sache der Endanwendung,
die Architektur kümmert sich lediglich um den Transfer der Befehle vom
Client zum RC und um die Übermittlung von Updates der Spielewelt vom RC zurück
zum Client. Clients interagieren also stets über einen RC und niemals direkt
miteinander.
Figure 4.5:
RegionController (RC) und 4 Clients mit jeweils einem Avatar
|
4.2 Probleme dieser Architektur
Die vorliegende Architektur ist einfach und überschaubar, wirft jedoch einige
Fragen auf und verursacht diverse Probleme. Ausserdem ist die Architektur
in ihrer jetzigen Form nicht geeignet, die gestellten Anforderungen aus Abschnitt
2.3.1 zu erfüllen. Die Probleme werden zunächst stichwortartig
aufgelisten und im späteren Verlauf genauer beschreiben.
Wenn möglich, werden auch eine oder mehrere Lösungen angeboten.
Bisher gingen wir davon aus, dass RegionController jederzeit zur
Verfügung stehen. In der Realität jedoch ergeben sich einige Fragen:
- Wie verfährt man, wenn ein RC das Netzwerk verlassen möchte (RC-Logout)?
- Was geschieht, wenn ein RC plötzlich ausfällt (RC-Fail/Down)?
- Wie findet man einen freien RC?
- Was geschieht, wenn keine freien RCs mehr übrig sind?
- Wie wird erreicht, dass die verschiedenen RCs zeitlich synchron arbeiten?
- Wie wird das Aufteilen einer Region entschieden und durchgeführt?
- Wer garantiert, dass ein RC nicht cheatet?
Da sich ein Spieler möglichst uneingeschränkt in der Welt bewegen möchte,
ergeben sich auch hier einige Probleme:
- Woher erfährt ein Client, mit welchem RC er kommunizieren soll/muß?
- Wie kann ein Avatar von einer Region in eine andere gelangen?
- Avatar am Rand einer Region: welche Objekte ``sieht'' er?
- Wie wird gewährleistet, dass Avatardaten über mehrere Sitzungen hinweg verfügbar sind
- Wer garantiert, dass ein anderer Client nicht cheatet?
Die Architektur wird nun schrittweise verbessert und verfeinert. Einige Probleme
werden zurückgestellt, aber im Hinterkopf behalten und sowohl bei der Einführung des Servers
(siehe 4.3.1) als auch bei der Erweiterung des RegionControllers auf
parallele Kontrolle einer Region (siehe 4.3.3) behandelt.
4.2.1 Problem: Logout des RegionController (RC-Logout)
Da es bei Onlinespielen die Regel ist, dass Spieler nur eine kurze Zeit im Spiel verweilen
(gemessen an der Laufzeit des Spiels, die möglicherweise mehrere Jahre
betragen kann), ist dieses Problem wohl oft anzutreffen und gehört zum regulären Spielbetrieb.
Falls der Spieler die Endanwendung beendet, muß in der Regel auch der dazugehörigen
RegionController beendet und seine Funktion ersetzt werden.
Die Daten müssen an einen freien RegionController übertragen werden, der die Region übernehmen soll.
Dieses Problem ist weniger gravierend, führt unter Umständen jedoch zu kurzzeitigen
Unterbrechungen des Spielbetriebs. Es muß zunächst ein freier RegionController gefunden werden, der
die Kontrolle dieser Region übernimmt. Vereinfachend gehen wir davon aus, dass es
zu jedem Zeitpunkt mindestens einen zur Verfügung stehenden, freien RegionController gibt.
Das Auffinden eines freien RegionControllers wird weiter unten (4.2.3) in diesem Abschnitt erörtert.
Ist ein neuer RegionController gefunden, dann wird die Region ``übergeben''.
Der alte RegionController informiert die verbundenen Clients darüber, dass sie sich
mit dem neuen RegionController verbinden müssen. Der Spielbetrieb muß dann für kurze
Zeit eingefroren werden, während der alte RegionController die Daten der Region an
den neuen RegionController überträgt. Während dieses Einfrierens findet keine Kommunikation
zwischen Clients und RegionController statt bzw. die Spielzüge werden nicht ausgeführt.
Sind alle Daten übertragen, kann der neue RegionController den Betrieb aufnehmen und
die Clients können normal weiterarbeiten.
Diese Aktion sollte in der Regel in wenigen Sekunden vollständig ausgeführt sein.
4.2.2 Problem: Ausfall eines RegionControllers (RC-Fail)
Die RegionController sind Prozesse auf den Computersystemen der Spieler.
Man kann davon ausgehen, dass es zu einer Vielzahl von unvorhergesehenen Ausfällen
kommen kann, die dabei nicht unbedingt vom Spieler selbst verschuldet sind.
Figure 4.6:
Der RegionController für die 4 Clients fällt aus
|
- Die Endanwendung stürzt ab
- Das Computersystem des Spielers stürzt ab
- Die dynamische Onlineverbindung wird getrennt (Ausfall, DSL-Zwangstrennung)
- Ausfall von Netzwerkkomponenten auf dem Weg zum RegionController
Der Ausfall eines RegionControllers in der vorgestellten Architektur stellt ein
gravierendes Problem dar. Die Clients verlieren unmittelbar den Zugang
zu ihrer Region und können nicht mehr weiter kommunizieren. Dem Spieler ist
es damit nicht mehr möglich, seinen Avatar zu steuern.
Da allein der RegionController die Informationen über die kontrollierte Region speichert,
sind diese nicht mehr zugänglich. Es kann also auch kein anderer RegionController
durch Übernahme der Kontrolle den alten Zustand wiederherstellen.
Im schlimmsten Fall sind die kompletten Daten der Region unwiederbringlich verloren,
falls der RegionController nicht schnell wieder verfügbar wird oder falls er
selbst die Daten verloren hat.
4.2.2.3 Lösungsansätze
- Erkennen von Problemen
Wichtig für die Fehlerbehandlung ist zunächst das Erkennen eines Problemes.
Wenn ein einzelner Client keine Verbindung mehr zum RegionController hat, muß
das nicht zwangsweise bedeuten, dass der RegionController ein Problem hat. Es
liegt erst dann ein Problem vor, wenn die Mehrheit der verbundenen Clients
nicht mehr mit ihrem RegionController kommunizieren kann. Die beteiligten
Parteien (Clients und übrige RegionController) müssen dann für eine befriedigende
Lösung des Problems sorgen.
- Lokale Sicherung der Daten
Der RegionController-Prozess auf dem Computersystem des Spielers sichert
den Zustand der Region regelmäßig auf den lokalen Datenträger.
Dieser Ansatz macht jedoch nur Sinn, wenn der RegionController innerhalb kürzester
Zeit wieder online gehen kann, zum Beispiel bei Abstürzen oder Fehlern des
RegionController-Prozesses unter der Endnwendung.
Bei einem kompletten Absturz des Computersystems ist die Down-Zeit des RegionControllers
während des Neustarts extrem störend, da es in der Regel mehrere Minuten dauern kann bis ein
Computersystem wieder betriebsbereit ist. Während dieser Zeit wäre die Region nicht
verfügbar und somit die Avatare darin nicht mehr spielbar.
Es kommt erschwerend hinzu, dass der Spieler die Endanwendung nach einem
Neustart möglicherweise nicht erneut startet und somit die abgetrennte Region
nicht länger zur Verfügung steht.
- Daten replizieren und regelmäßige Backups erstellen
Die RegionController sollen ihre Daten regelmäßig auf andere RegionController oder
entsprechende Dienste sichern. Durch diese Art von Backup kann ein gravierender Ausfall
eines RegionControllers ein wenig entschärft werden, da es damit möglich ist, auf
einen früheren, nämlich den zuletzt gesicherten Stand der Spielewelt zurückzukehren. Der
Nachteil hierbei ist, dass ein Backup des Zustandes zeitaufwendig und eventuell nicht
sehr ressourcenfreundlich ist. Somit könnte ein flüssiger Spielbetrieb durch zu häufige
Durchführung von Backups stark beeinträchtig werden.
- Parallele Kontrolle einer Region durch mehrere RegionController
Um dem Aufall eines RegionControllers vorzubeugen wird die Region von mehreren RegionControllern
parallel kontrolliert. Die erweiterte Architektur behandelt diese Thematik ausführlich
(siehe Abschnitt 4.3.3).
4.2.3 Problem: Auffinden von freien RegionControllern
Wird eine Region aufgeteilt, dann muß ein Teil an einen freien RegionController
delegiert werden. Der bisherige RC dieser Region muß also einen geeigneten freien RC
finden.
An dieser Stelle wird es schwierig, denn der RC kennt bisher nur seine Clients.
In der Regel sollte zwar jeder dieser Clients einen RegionController stellen, aus deren
Menge sich der alte RC der Region einen geeigneten aussuchen könnte. Da aber
keine globalen Informationen über die Belegung dieser RCs zur Verfügung stehen könnte
es sein, dass einige bereits eine Region kontrollieren.
Der Aufwand wäre ziemlich hoch, einen geeigneten RC aus dieser Menge auszusuchen. Hinzu
kommt, dass dem alten RC keine Informationen über Clients und entsprechende RCs zur
Verfügung stehen, die sich nicht in seiner Region befinden. Die Lösung dieser Probleme
wird mit der Einführung des zentralen Servers im Abschnitt 4.3.1
vorgestellt.
4.2.4 Problem: keine freien RegionController mehr übrig
Dieses Problem sollte eigentlich niemals aufkommen. In der Regel entspricht die
Anzahl an RegionControllern im Netzwerk der Anzahl an verbundenen Clients, da jeder
Spieler sowohl einen Client als auch einen RegionController zur Verfügung stellt.
Ein Mangel an RegionControllern kann sich also nur einstellen, wenn:
- keine freien RCs auffindbar sind (siehe Abschnitt 4.2.3)
- Firewalls auf vielen Computersystemen eine Verbindung dorthin unterbinden
Dieses Problem soll in dieser Arbeit nicht behandelt werden, da bereits Techniken für
eine Lösung existieren.
- es mehr Regionen geben sollte als RegionController
Auf dieses Problem möchte ich nun im Detail eingehen.
4.2.4.1 Problem: Es existieren mehr Regionen als RegionController
Zunächst stellt sich die Frage: wie kann es dazu kommen, dass es mehr Regionen
gibt, als RegionController zur Verfügung stehen. Man kann sich einige realistische
Szenarien ausdenken, die zu einer solchen Situation führen können.
Nehmen wir an, ein Spiel läuft gerade mit einer sehr hohen Anzahl an Clients, z.B.
zu einer Stoßzeit in der regelmäßig viele Spieler online sind. Dies führt dazu,
dass das Spiel in viele Regionen zerlegt wird und sich in jeder Region mehrere
Avatare bewegen. Nach einer kurzen Zeit aber werden immer mehr Clients aus dem Spiel
aussteigen, und die Regionen werden dünner besetzt.
Es kann sogar geschehen, dass eine Region komplett verlassen wird. Dieser Gedanke ist
daher gar nicht so abwegig, weil viele Spieler sich in Gruppen zusammenfinden, zusammen
spielen und daher das Spiel meist auch als Gruppe wieder verlassen.
Die Region ist nun also ``leer'', d.h. es sind keine Clients mehr mit dem RegionController
dieser Region verbunden. Jedoch befinden sich noch Objekte in der Region und der zugehörige
RegionController verwaltet sie weiter.
Geschieht dies in mehreren Regionen, dann kann es dazu kommen, dass mit der Zeit
sämtliche existierende RegionController jeweils eine Region kontrollieren. Verlässt nun ein Spieler
und damit auch sein RegionController das Spiel, dann muß ein Ersatz gefunden werden
(siehe ``RC-Logout'' in Abschnitt 4.2.1). Zu diesem Zeitpunkt ist aber kein
RegionController mehr frei und es kommt zu einem schwerwiegenden Problem
Fazit: es darf niemals mehr Regionen geben als RegionController zur Verfügung stehen. Das
System muß geeignete Maßnahmen treffen um eine gewisse Mindestanzahl freier RegionController zu garantieren.
Regionen, in denen sich weniger als eine Mindestanzahl von Clients befinden müssen mit anderen
Regionen verschmolzen oder neu organisiert werden. Ausführlicher wird dieser Teil im
Abschnitt 4.3.5 behandelt.
4.2.5 Problem: Synchronität der Zeit zwischen den Regionen
Da jede Region von einem anderen Prozess kontrolliert wird und daher
auch verschiedene Computersysteme im Einsatz sind, kann es leicht
dazu kommen, dass die Systeme zeitlich nicht mehr synchron arbeiten.
Wird z.B. ein RegionController kurzzeitig überlastet, dann ``hinkt''
er vielleicht der globalen Zeit hinterher. Verlassen sich die RegionController
auf die Systemuhren, dann kann es ebenso zu Asynchronität kommen, da nicht
jede Systemuhr gleich präzise arbeitet.
Zwischen den Regionen sind kleine Abweichungen nicht weiter schlimm, solange
die Clients innerhalb der Region synchron arbeiten. Ein Problem ergibts
sich nur zu dem Zeitpunkt, an dem ein Avatar die Region wechselt.
Die RCs müssen sich also regelmäßig synchronisieren und das System muß dafür sorgen,
dass eine zuverlässige globale ``Systemzeit'' zur Verfügung steht. Die Toleranz
für Abweichungen sollte nicht zu hoch gewählt sein, um Probleme beim Wechsel
der Region zu verhindern. Zu niedrige Toleranzen wiederum erhöhen den Aufwand,
der für die Synchronisierung betrieben werden muß.
4.2.6 Problem: Aufteilen einer Region (Region-Splitting)
Wie bereits erwähnt können Regionen aufgeteilt werden, falls eine hohe Belegung
durch Clients zu Problemen beim RegionController führt. Eventuell ist ein RegionController
der Datenflut nicht mehr gewachsen, oder seine Rechenleistung reicht nicht weiter aus. Dann
muß er einen Teil der Region und die Kontroller über darin befindliche Avataren
einem anderen RegionController übergeben. Durch die Übergabe der Avatare nimmt
die Anzahl der verbundenen Clients ab.
4.2.6.1 Finden einer geeigneten geografischen Aufteilung
Die Aufteilung der Region sollte möglichst homogen erfolgen, d.h. die neuen Gebiete sollten
gleich groß sein. Theoretisch sind jedoch beliebige geografische Aufteilungen möglich, solange sie
parallel zur X- oder Y-Achse verlaufen .
Der RegionController kann entscheiden, welchen Teil der Region er abtreten möchte. Dabei sollte ein Mittelmaß
zwischen Anzahl an Clients pro Region und Größe der beiden Regionen gefunden werden. In Abb. 4.7
wird eine einfache Aufteilung einer Region skizziert.
Figure 4.7:
Region wird aufgeteilt / gesplittet
Die hier dargestellte Region wird optimal aufgeteilt, sowohl hinsichtlich Fläche als auch
hinsichtlich der beteiligten Clients (in jeder der beiden neuen Regionen befinden sich drei Avatare). |
Zunächst muß ein freier RegionController gefunden werden (siehe 4.2.3).
Steht ein freier RegionController zur Verfügung, dann muß diesem die Information über seine
zukünftige Spielewelt übermittelt werden. Die Übertragung stellt eine kritische Phase im Spiel dar,
denn solange die Übertragung nicht vollständig abgeschlossen ist, dürfen keine Spielzüge mehr
ausgeführt werden.
Unter den Objekten befinden sich auch Avatare, die von Clients gesteuert werden. Jene Clients müssen
natürlich darüber in Kenntnis gesetzt werden, dass sich ihr zuständiger RC nun geändert hat. Sie müssen
dann ab sofort mit dem RC der neu geschaffenen Teilwelt kommunizieren.
Im Abschnitt 5.4.6 wird dieser Vorgang grafisch Dargestellt (Abbildung 5.4).
4.2.7 Problem: Avatar wechselt Region
Steuert der Spieler seinen Avatar an den Rand der Region und übertritt die Grenze,
dann muß ein Wechsel der Region durchgeführt werden (siehe Abb. 4.8).
Hat der Avatar die Region gewechselt, dann muß sich der zugehörige Client ab sofort mit dem RegionController
der Ziel-Region verbinden.
Figure 4.8:
Avatar wechselt Region
|
Die zum Avatar gehörigen Objekte sowie die Datenstrukturen
des Avatars selbst müssen an den RegionController der Ziel-Region übertragen werden. Dies
muß zuverlässig geschehen und darf keine Ansätze für Datenmanipulationen bieten. Der
Avatar darf nicht in beiden Regionen gleichzeitig existieren, d.h. die Übertragung der Daten
muß atomar geschehen.
In Abbildung 4.8 sind folgende Schritte skizziert:
- Der Avatar erreicht und überschreitet die Grenze zwischen R1 und R2.
- Der zum Avatar gehörige Client C1 kontaktiert den RC der Zielregion R2.
- RC2 überträgt die notwendigen Daten an RC1 und übergibt ihm die Kontrolle.
- RC2 trennt die nun nicht mehr notwendige Verbindung zum Client C1.
Ein grundlegendes Problem ist das Auffinden des zugehörigen RegionControllers.
Dieses Problem wird durch die Einführung des zentralen Servers behoben
(siehe Abschnitt 4.3.1). Im Idealfall sollte der Wechsel einer Region
innerhalb weniger hundert Milisekunden abgeschlossen sein, der Spieler sollte davon nichts mitbekommen.
Im Abschnitt 5.4.4 wird dieser Vorgang detailliert beschrieben.
4.2.8 Problem: Avatar am Rande seiner Region
Die vorgestellte Architektur sieht vor, dass jeder Client während des regulären Spielbetriebes
ausschliesslich mit seinem RegionController kommuniziert.
Kommt er jedoch an den Randbereich einer Region, dann möchte er durchaus Informationen
über Objekte und Avatare erhalten, die sich jenseits der Region-Grenze,
aber innerhalb seiner Sichtweite befinden.
Um Informationen über jene Objekte und Avatare zu erhalten, die sich innerhalb seiner Sichtweite, aber
ausserhalb seiner Region befinden, muß der zum Avatar gehörige Client Daten von einem RegionController
erhalten. Es gibt im Prinzip zwei Möglichkeiten, die hier kurz erläutert werden sollen.
Beide Versionen haben Vor- und Nachteile.
- Der Client erhält die benötigten Informationen weiterhin von seinem RC
- Der Client kontaktiert zusätzlich den RC der benachbarten Region und erhält die Daten von diesem
Die erste Variante, nämlich das Erhalten der Informationen von seinem aktuellen RegionController,
ist für den Client die einfachste und transparenteste Lösung. Der RegionController übermittelt
in diesem Fall einfach die Daten zu den Objekte. Allerdings muß der RegionController diese Information
erst erlangen, und daher Kontakt zum benachbarten RegionController aufnehmen. Im schlimmsten Fall muß
der RegionController Verbindungen zu den RegionControllern aller benachbarten Regionen offen halten.
Erhält der Client die Informationen direkt vom zuständigen RegionController, wie im zweiten
Fall beschrieben, dann muß er eine zusätzlich Verbindung aufbauen und halten. Dies könnte von Vorteil sein, wenn er kurz
darauf in diese Region wechselt, denn dann kann er diese Verbindung aufrecht erhalten. Jedoch
ergibt sich auch hier ein schwerwiegendes Problem: der benachbarte RegionController müßte
eine Verbindung zum RegionController des Clients aufbauen, um sich zu vergewissern, dass
der Client auch zum Erhalten von Objektinformationen berechtigt ist.
In beiden Fällen müssen die RegionController Informationen untereinander austauschen. Die direkte
Kommunikation des Clients mit dem benachbarten RegionController hat den Vorteil, dass die Übermittlung der
Objektdaten nicht umständlich umgeleitet werden muß und spart somit Netzwerkbandbreite.
Die vorgestellte Architektur enthält einige Schwachstellen, die es einem Spieler erlauben,
unfaire Vorteile zu erlangen. Auf einige Möglichkeiten möchte ich an dieser Stelle kurz eingehen
und eventuelle Lösungsansätze nennen.
Im Prinzip gibt es in der vorgestellten Architektur zwei grundsätzliche Möglichkeiten des
Cheatings: die Erlangung und Nutzung von Informationen, die einem Client eigentlich verborgen bleiben sollen,
und das gezielte Manipulieren der Spielewelt durch einen RegionController.
4.3 Erweiterte Architektur
Wie wir im Abschnitt 4.2 bereits behandelt haben, verursacht die einfache Architektur
viele Probleme, einige davon schwerwiegendend (wie der Ausfall eines RegionControllers).
In diesem Abschnitt soll die Architektur nun so erweitert werden, dass die meisten Probleme
behoben oder entschärft werden.
4.3.1 Einführung eines zentralen Servers
In diesem Abschnitt wird ein Server als zentrale Verwaltung der Clients und RegionController
eingeführt. Dieser Server sollte jedoch möglichst wenig Rechenleistung erbringen
müssen, um die Anforderungen an anzuschaffende Hardware gering zu halten.
Ein reines Peer-to-Peer-Netzwerk verursacht erheblichen Verwaltungsaufwand. Die
beteiligten Peers müssen gefunden werden und sich untereinander so organisieren,
dass man gesuchte Peers schnell finden kann. Tritt ein Client in das Peer-To-Peer-Netzwerk
ein, dann verbringt er womöglich eine lange Zeit damit, die übrigen beteiligten Peers
ausfindig zu machen.
Für den Betrieb eines MMGs ist dieser Verwaltungsaufwand zu groß. Es kommt hinzu,
dass der Betreiber möglicherweise Zugangskontrollen einrichten möchte, zum Beispiel
weil es sich um einen bezahlten Dienst handelt und somit auch nur zahlende Kunden
einen Zugang bekommen sollen. Ausserdem sollten Account-Daten
zentral gespeichert und der Zustand der Welt gesichert werden können, um bei
Bedarf den Betrieb des Spiels aussetzen zu können.
Daher wird in diesem Abschnitt die Verwendung eines zentralen Servers behandelt.
Der Server lässt sich leicht in die vorgestellte Architektur einbinden. Er kann
als ein Serviceprovider für zentral zu verwaltende Funktionen angesehen werden.
Figure 4.9:
Zentraler Server übernimmt Verwaltungsfunktionen
Dieser Server verwaltet Informationen über eine Region mit drei RCs und drei Clients.
Ein neuer Client C4 möchte sich ins System einloggen, er hat jedoch keinerlei Kenntnis über
Regionen, RCs und andere Clients. |
4.3.1.3 Aufgabengebiete des Servers
Der Server wird die Verwaltung sensibler Daten übernehmen, die man schlecht
oder gar nicht nicht auf ein Peer-to-Peer Netzwerk verteilen kann oder will,
sowie als Quelle für globale Informationen dienen.
Die Manipulation der Spielewelt ist alleinige Aufgabe der RegionController.
Einige der im Abschnitt 4.2 genannten Probleme können durch
den Einsatz eines Servers entschärft oder behoben werden. Vor allem die Verwaltung der
RegionController und Clients wird erheblich vereinfacht, wenn eine zentrale
Instanz vorhanden ist, die Informationen über diese Strukturen speichert. Zum
Beispiel erleichtert ein zentraler Server das Auffinden eines RegionControllers
für einen Client, da der Server genau weiß, welcher RegionController für die Region
des Clients zuständig ist.
Folgende Aufgaben werden fortan an den Server delegiert:
- Bereitstellen einer zentralen Informationsquelle für alle beteiligten Peers
- Authentifizierung und Zugangskontrolle zum Spiel (Login)
- Persistente Speicherung von Account- und Avatardaten
- Zuordnung von Avataren zu ihren Regionen und Zuweisung der Clients zu ihren RCs
- Verwaltung von freien und bereits zugeordneten RegionControllern
- Erkennen von Engpässen bei der Verwaltung von RegionControllern
- Einleiten von Splitten und erneutem Zusammenfügen von Regionen
- Organisation der Datenübertragen beim Wechsel der Region durch einen Avatar
- Datensicherung bei administrativer Unterbrechung des Spiels
- Sammeln von Daten zur statistischen Auswertung
4.3.2 Kachelung der Regionen
Im Zusammenhang mit dem Aufsplitten und wieder Zusammenfügen von Regionen ergeben sich einige Probleme (siehe 5.4.6),
die mit der bisherigen Vorstellung schwierig zu lösen sind. Ebenso ergeben sich Probleme, wenn
ein Avatar den Rand einer Region erreicht (siehe 4.2.8).
Bereits weit vorne in diesem Abschnitt wurde die Sichtweite beschrieben (siehe 4.1.1.7).
Die Sichtweite wird bei der nun vorzustellenden Erweiterung des Konzeptes durch
Kacheln eine bedeutende Rolle spielen.
Eine Region wird nun weiter aufgeteilt in quadratische Kacheln der Kantenlänge . Eine Kachel ist dabei die kleinste
zu verwaltende Einheit. Die Aufteilung einer Region oder das Zusammenfügen von Regionen
kann somit nur kachelweise erfolgen. Die rechteckige Struktur einer Region darf bei
solchen Vorgängen nicht zerstört werden.
Figure 4.10:
Kachelung der Region
Der Avatar befindet sich in der linken unteren Ecke der roten Kachel und
überblickt eine Kachel in jede Richtung (blau umrandete Kacheln), insgesamt also neun Kacheln. |
Alternativ könnte man die Kachelung hexagonal durchführen.
Die Sichtweite wird nicht in Pixeln oder sonstigen Maßeinheiten festgelegt, sondern
sie beträgt eine Kachel in jede Richtung. Ein Avatar überblickt somit neun quadratische Kacheln:
die, auf der er sich zur Zeit befindet, und die umliegenden acht. Bei hexagonaler Form
gäbe es nur sechs umliegende und insgesamt sieben zu überblickende Kacheln.
Diese Definition der Sichtweite führt dazu, dass es keinen fixen Radius gibt, sondern vielmehr
ein Intervall zwischen minimaler und maximaler Sichtweite
, in dem sich bewegt.
Minimale und maximale Sichtweite sind in Grafik 4.10 skizziert und treten dann auf, wenn sich der Avatar
an einen Eckpunkt der Kachel bewegt. Die minimale Sichtweite
entspricht der Kachelgröße , die maximale Sichtweite ergibt sich aus der doppelten Diagonalen einer
Kachel, also
.
Zusammengefasst gilt für quadratische Kacheln:
Bewegt sich der Spieler innerhalb einer Kachel, die sich am Rande einer Region befindet, dann
benötigt er Informationen über Kacheln, die sich in ``fremden'' Regionen befinden. Da die Sichtweite
als eine Kachel in jede Richtung definiert ist, kann es im Extremfall passieren, dass ein Client Informationen
von neun RCs (inklusive dem RC seiner derzeitigen Region) erhalten muß.
Um die Anzahl an möglichen Verbindungen zu RegionControllern zu minimieren, wird eine
weitere Forderunge an die Größe einer Region gestellt. Eine Region muß mindestens aus 3x3 Kacheln bestehen.
Somit verringert sich die Anzahl der möglichen Verbindungen zu RegionControllern auf vier,
und dieser Fall tritt nur dann auf, wenn sich der Avatar des Spieler in eine Eckkachel
der Region bewegt und falls dort genau drei Regionen benachbart sind.
4.3.3 Parallele Kontrolle einer Region durch mehrere RegionController
Ein gravierendes Problem ist der Ausfall eines RegionControllers, wie im Abschnitt 4.2.2
bereits erläutert. In diesem Abschnitt wurden bereits einige Lösungsansätze vorgestellt
(siehe 4.2.2.3), einer davon wird nun an dieser Stelle ausgearbeitet: die
Erweiterung der Architektur, so dass eine Region nun von mehreren RegionControllern
verwaltet wird. Dieser Vorschlag wird durch die Implementierung umgesetzt (siehe Abschnitt 5.3.5).
Figure 4.11:
Ein Pool von RegionControllern kontrolliert die Region
|
Die vorgeschlagene Lösung für das Problem des Ausfalls scheint einleuchtend: die Region wird von mehreren RegionControllern
parallel kontrolliert. Zur Vereinfachung betrachten wir mehrere RegionController für diesselbe
Region als ``Pool''. D.h. die Clients kommunizieren nicht direkt mit jedem RegionController, sondern
mit einem ``RC-Pool''. Wie die Implementierung dieser Kommunikation ausfällt wird später behandelt.
Jeder beteiligte RegionController verwaltet die Daten selbständig und führt eine aktuelle Kopie
der Spielewelt. An dieser Stelle ergeben sich einige Fragen:
- Wieviele RegionController pro Region sind sinnvoll? (siehe 4.3.3.1)
- Sind überhaupt genügend RegionController vorhanden?
- Wie kommunizieren die Clients mit dem RC-Pool?
- Wer verwaltet die RC-Pools, die RCs und die Zuordnungen?
- Wie wird gewährleistet, dass jeder RC denselben Zustand der Spielewelt hat?
- Wie sieht es mit Cheating aus?
4.3.3.1 Anzahl der RegionController für eine Region
Eine wichtiger Punkt ist die Anzahl der RegionController, die innerhalb eines
Pools für die Kontrolle der Region zuständig sind. Die Anzahl wirkt sich auf
Performanz, Stabilität und Restistenz gegen Cheating aus.
Zu wenige RegionController erhöhen die Gefahr eines Ausfalls. Das absolute Minimum
sollte daher zwei RegionController sein, um bei einem Ausfall keine Daten zu verlieren.
Je mehr RegionController in einem Pool sind, desto geringer ist die Gefahr
eines Ausfalls der Region und eines Datenverlustes. Ausserdem steigt mit der Anzahl
der RegionController auch die Anzahl sich gegenseitig überprüfender Einheiten
und somit auch die Resistenz gegen Cheating.
Zu viele RegionController verkomplizieren die Kommunikation mit den Clients erheblich
und erschweren einige Punkte wie Zeit-Synchronität und Konsistenz der Spielewelt zwischen
den beteiligten RegionControllern.
Es ist daher sinnvoll, eine minimale sowie eine maximale Anzahl an RegionControllern
pro Region festzulegen. Wünschenswert wäre es, dass diese Parameter im laufenden Betrieb
angepasst werden können.
- Splitting der Region eines RC-Pools
Da nun mehrere RCs an der Verwaltung einer Region beteiligt sind, gestaltet sich
das Splitting aufwendiger. Siehe 4.3.4.
- Synchronisation der RCs innerhalb desselben RC-Pools
Jeder RC innerhalb des Pools verwaltet diesselbe Region und erhält die
Spielzüge von den Clients. In der Regel kann man nicht verhindern, dass die
Kommunikation zwischen RCs und Clients ab und zu fehlerbehaftet ist oder
gar kurzfristig ausfällt. Solche Fehler dürfen die Konsistenz der Region
nicht stören. Fehler müssen auffallen und korrigiert werden.
4.3.4 Splitting der Region eines RC-Pools
Weiter oben in diesem Kapitel (siehe 4.1.2) wurde bereits auf das Splitting
einer Region eingegangen. Dieser Vorgang wird nun durch die Tatsache erschwert,
dass mehrere RCs an der Verwaltung einer Region beteiligt sind. Beim Splitting muß einerseits
der Befehl an alle RCs innerhalb des RC-Pools erteilt werden und andererseits muss die
gesplittete Region an einen neuen RC-Pool übertragen werden. Der hierfür benötigte Aufwand
ist nicht unerheblich und soll nun eingehend erläutert werden.
Da die hauptsächliche Rechenleistung von den RCs im RC-Pool bereitgestellt wird, sollten
diese auch entscheiden dürfen, wann ihnen ``die Arbeit zuviel wird''. Stellt ein RegionController
fest, dass er nicht mehr zuverlässig Daten verarbeiten oder übertragen kann, dann schlägt
er dem Server ein Splitting vor.
Zusätzlich werden vom System Obergrenzen für die Bevölkerung einer Region gesetzt. Wird
diese Grenze erreicht, dann wird ebenso der Split-Vorgang eingeleitet.
In beiden oben genannten Fällen kontaktieren die RCs den Server und erbitten das Splitting ihrer Region.
Der Server teilt diesen RCs dann einen neuen, leeren RC-Pool zu, der einen
Teil der Region aufnimmt und in Zukunft verwaltet. Die RCs des leeren RC-Pools werden darüber
informiert, dass sie nun eine Spielwelt erhalten werden und welcher Teil der Welt das sein wird.
Abbildung 5.4 in Abschnitt 5.4.6 verdeutlicht den Ablauf eines Splittvorgangs.
4.3.5 Mindestbesetzungen einer Region
Es wurde bereits angedeutet, dass eine Region mit einer Mindestanzahl an Clients besetzt
werden sollte. Dieser Ansatz soll nun in die Architektur mit aufgenommen werden.
Prinzipiell wäre nichts gegen eine Unterbesetzung einzuwenden. Jedoch könnte das System
in ernsthafte Schwierigkeiten kommen, wenn irgendwann die Regionen ausdünnen. Denn in der
Regel verlässt zusammen mit einem Client auch ein RegionController das System. Daher bietet
es sich an, dass dünn besiedelte Regionen mit anderen Regionen zusammengefügt werden.
Diesen Vorgang nennen wir ``Merging''.
4.3.6 Merging von Regionen im RegionTree
Soll eine Region zu einer anderen hinzugefügt werden, dann sprechen wir von ``Merging''. In
einem solchen Fall werden Gebiete vereinigt, um RegionController freizugeben.
Durch die unterschiedlich großen Grenzen der Regionen ergeben sich jedoch einige Probleme.
Man kann nicht immer direkt zwei benachbarte Regionen vereinigen.
Da die verschiedenen Split-Operationen der Welt im RegionTree nachvollziehbar sind, liegt
es nahe, auch das Merging anhand des RegionTrees zu steuern und die Operationen dort anzusiedeln.
Die einfachste Operation ist das Merging zweier Regionen, die Blätter mit einem gemeinsamen
Vater-Knoten sind (siehe Abbildung 4.12). In diesem Fall werden die beiden Regionen vereinigt, und der Vater durch
ein neues Blatt mit den gemergten Daten ersetzt. Die RegionController der dünn besetzten
Region werden danach freigegeben.
Figure 4.12:
Merging zweier Blätter im RegionTree
|
Die etwas schwierigere Variante ist das Merging eines Blattes mit einem Knoten. Dieser
Fall kann durchaus oft auftreten, da das Splitting nicht immer einen optimalen Baum
aufbaut. In diesem Fall erfolgt ein rekursiver Aufruf, wie in Abbildung
4.13 skizziert.
Figure 4.13:
Merging eines Blattes und eines Knotens im RegionTree
Die dargestellte Funktionsweise ist symmetrisch und funktioniert analog,
falls sich das Blatt auf der rechten Seite des obersten Knotens befände. |
Das Merging durchläuft mehrere Schritte. Zunächst wird die zu mergende Teilwelt
an jener Grenze gesplittet, wo auch die Teilwelt des benachbarten (Y-) Knotens gesplittet
worden ist. In der Abbildung ist das bei .
Es entstehen nun zwei neue Teilwelten, die genau zu den Teilwelten des benachbarten (Y-) Knotens
passen. Nun wird auf die Söhne der benachbarten Knoten ein Merge-Befehl erteilt, so dass
diese die beiden neu entstandenen Teilwelten mit ihrer bereits verwalteten Teilwelt
vereinigen. Der oberste (X-) Knoten (Splitting bei ) fällt nun weg, da im kompletten
Teilbaum keine Aufteilung in X-Richtung mehr nötig ist. An die Stelle dieses Knotens
tritt der (Y-) Knoten.
Achtung: in Abbildung 4.13 wird suggeriert, dass es sich
bei den Söhen des (Y-) Knotens (Splitting bei ) um Blätter handelt. Das muß nicht so sein,
die Funktionsweise lässt sich auch auf Knoten übertragen - in diesem Fall wird
es dann zu weiteren rekursiven Aufrufen kommen.
In der Regel wird das Merging für Regionen benötigt, die ausdünnen,
und daher für solche RCPools, deren Information in einem Blatt gespeichert ist.
Ein direktes Merging zweier Knoten kommt also nicht vor.
In den rekursiven Aufrufen kann es jedoch durchaus vorkommen, dass ein Knoten anstelle
eines Blattes mit einer Region gemerged werden soll.
Dieser Vorgang ist in Abbildung 4.13 ebenfalls dargestellt.
Die zu mergende Region wird aufgesplittet entsprechend des im Knoten gespeicherten
Splittvorgangs. Die beiden entstehenden Teile passen dann zu den Kindern,
es erfolgt dann ein rekursiver Aufruf, der die beiden Teile mit den beiden
Kindern merged.
http://www.psitronic.de/ti/mmpg/mmpg-peer_to_peer/
|
|