eMail
 Suche
 Impressum

Subsections


4. Das Framework ``MMPGP2P''

4.1 Einführung einer einfachen Architektur

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
Image sichtweite 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
Image region_3geteilt 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
Image RegionTree


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)
Image R_3_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
Image R_1_RC_Clients


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.

4.2.0.1 Probleme auf Seiten der RegionController

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?

4.2.0.2 Probleme auf Seiten der Clients und Avatare

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.

4.2.1.1 Ersetzen des RegionControllers

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.

4.2.1.2 Übergabe der Region an einen anderen RegionController

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
Image RC_fail

4.2.2.1 Mögliche Ursachen für einen Ausfall

  • 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

4.2.2.2 Konsequenzen eines Ausfalls

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
Image region_splitt 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).

4.2.6.2 Übertragen des neuen Teils der Region an einen freien RC

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
Image region_cross

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:

  1. Der Avatar erreicht und überschreitet die Grenze zwischen R1 und R2.
  2. Der zum Avatar gehörige Client C1 kontaktiert den RC der Zielregion R2.
  3. RC2 überträgt die notwendigen Daten an RC1 und übergibt ihm die Kontrolle.
  4. 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.

  1. Der Client erhält die benötigten Informationen weiterhin von seinem RC
  2. 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.

4.2.9 Problem: Cheating

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.

4.3.1.1 Gründe für die Einführung eines Servers

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.

4.3.1.2 Integration in die eingeführte Architektur

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
Image Server 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.

4.3.2.1 Kachel als kleinste Verwaltungseinheit einer Region

Eine Region wird nun weiter aufgeteilt in quadratische Kacheln der Kantenlänge $l$. 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
Image kachel 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.

4.3.2.2 Koppelung der Sichtweite an die Kachelung

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 $r$ gibt, sondern vielmehr ein Intervall zwischen minimaler und maximaler Sichtweite $[r_{min};r_{max}]$, in dem sich $r$ 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 $r_{min}$ entspricht der Kachelgröße $l$, die maximale Sichtweite $r_{max}$ ergibt sich aus der doppelten Diagonalen einer Kachel, also $r_{max} = 2 * \sqrt{ 2 * l^2 } = \sqrt{4} * \sqrt{ 2 * l^2} = \sqrt{ 8 * l^2}$.

Zusammengefasst gilt für quadratische Kacheln:
$r \in [r_{min}; r_{max}]$
$r_{min} = l$
$r_{max} = \sqrt{ 8 * l^2}$

4.3.2.3 Sonderfälle an den Grenzen von Regionen

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
Image R_RCpool_Clients
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.

4.3.3.2 Erwartete Probleme

  • 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.

4.3.4.1 Wann wird gesplittet?

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.

4.3.4.2 Ablauf eines Splittvorgangs

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.

4.3.6.1 Merging zweier Blätter

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
Image merge2leaves

4.3.6.2 Merging Blatt und Knoten

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
Image mergeLeafAndNode 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 $y=b$.

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 $x=a$) 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 $y=b$) 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.

4.3.6.3 Merging zweier Knoten

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/
Menü

Home
Funstuff
Linux
Hardware
Distributionen
Spiele
Kontakt
Projekte
Java
Webcut
Strength and Honor
A-Mobile
Holy-Wars 2
Holy-Wars 3
-> Dokumentation
Biometrie
Performanzermittlung
-> Mmpg
-> Mmpg-peer to peer
Javadoc
Mmpgp2p-Server
Semantic Web
WSA



- Impressum -
designed using WebCut - Copyright (c) 2001-2008 by Markus Sinner