Portierung eines Multi-Player-Games auf eine Proxy-Plattform sowie anschließende Evaluation

Inhaltsverzeichnis

1 Einleitung
1.1 Die Wahl der Engine
1.2 Die QFusion-Engine
1.3 Verwandte Arbeiten

2 Die QFusion-Engine und die Proxy-Architektur
2.1 Die QFusion-Engine
2.1.1 Netzwerkarchitektur
2.1.2 Netzwerkprotokoll
2.1.2.1 Nachrichtentypen
2.1.2.2 Deltakomprimierung
2.1.2.3 Checksummen
2.1.3 Server-Mainloop
2.1.4 Client-Mainloop
2.1.5 Ausschnitt des Server-Datenmodells
2.2 Die Proxy-Architektur
2.2.1 Aufbau der Netzwerkarchitektur
2.2.2 Möglichkeiten der Kommunikation
2.2.3 Abstraktion der Adressierung
2.2.4 Synchronisation des Spielzustandes
2.2.5 Fairnessunterstützung

3 Implementierung des Framework-API
3.1 Überblick und Notation
3.2 Das Netzwerkprotokoll
3.2.1 Client-Proxy-Kommunikation
3.2.2 Inter-Proxy-Kommunikation
3.2.3 Netzwerkprotokoll-Header
3.3 Die Serverklasse QPA_Server
3.4 Scheduling der eingehenden Pakete
3.5 Die Klasse eingehender Pakete QPA_Message
3.6 Die Clientklasse QPA_Client
3.7 Client/Server-Datenfluss
3.8 Inter-Proxy-Datenfluss
3.9 Remoteclient-Konzept
3.10 Zusammenfassung

4 Synchronisation des Spielzustandes
4.1 Managen des replizierten Zustandes
4.2 Movement-Synchronisation
4.2.1 Ableitung des Zustandsupdates für einen Remoteclient
4.2.2 Das Remoteclientupdate
4.2.3 Zusammenfassung
4.3 Synchronisation der Interaktionen
4.3.1 Synchronisation geführter Waffen
4.3.2 Interaktionen zwischen Spielern
4.3.2.1 Interaktionen mit Remoteclients
4.3.2.2 Interaktionen von Remoteclients
4.3.3 Interaktionen mit der Umgebung
4.3.4 Userinfo-Synchronisation
4.3.5 Zusammenfassung
4.4 Synchronisationsintervalle
4.5 Problem ungültiger Spielerzustände
4.6 Action Reordering
4.7 Synchronisationen durch den Masterserver
4.7.1 Synchronisierung der Hostuhren
4.7.1.1 Slaveproxyserverzeit
4.7.1.2 Clientzeit
4.7.2 Synchronisierung der Spawnpoints
4.7.3 Spielsitzungsverwaltung
4.8 Proxyserver-Mainloop
4.9 Manipulation der Tickrate

5 Installation und Benutzung
5.1 Installieren der 3D-Engine
5.2 Starten des Spiels
5.2.1 Initialisierung der Server
5.2.2 Starten mit Hilfe der Batchdateien
5.3 Die Engine-Konsole
5.3.1 Konsolenvariablen - CVAR’s
5.3.2 Konsolenbefehle
5.4 Konfiguration der Proxy-Architektur
5.4.1 Server-Konfiguration
5.4.2 Client-Konfiguration
5.4.3 Ändern der Voreinstellungen
5.5 Kompilieren der Engine
5.5.1 Compiler-Einstellungen
5.5.2 Aktuelle GPA-Versionen linken
5.6 Die Benutzung und Einstellung des Spieles
5.6.1 Einstellungen des Spielermodells
5.6.2 Deathmatch Scoreboard

6 Evaluation der Portierung
6.1 Analytische Skalierbarkeitsmodelle
6.1.1 Client/Server-Skalierungsmodell
6.1.2 Proxyserver-Skalierungsmodell
6.2 Vergleich der Client/Server- und Proxy-Version
6.2.1 Testbedingungen und Methodik
6.2.2 Erfassen von Messwerten
6.2.3 Auswertung des Versuches
6.2.3.1 Berechnungszeiten für einen Tick
6.2.3.2 Bandbreitenanforderungen pro Tick
6.2.3.3 Zusammenfassung
6.3 Evaluation über das Internet
6.3.1 Testauswertung anhand der benötigten Rechenzyklen
6.3.2 Testauswertung anhand der benötigten Bandbreiten
6.4 Skalierungstest
6.5 Aufwand der Portierung
6.6 Zusammenfassung

7 Bewertung und Ausblick
7.1 Bewertung
7.2 Ausblick

Literaturverzeichnis

A Verzeichnisstruktur

B Definition referenzierter Strukturen
Netzkanalstruktur netchan_t
Netzadress-Strukturen netadrtype_t, netsrc_t, netadr_t
Buffer-Struktur sizebuf_t
Userinput-Struktur usercmd_t
Clientframe-Struktur client_frame_t
Spielerzustands-Struktur player_state_t
Spielerbewegungs-Struktur pmove_state_t
Client-Struktur client_t

C Funktions-Deklarationen

D Die Klasse QPA_Server

E Die Klasse QPA_Client

F Quellcodelinks

G Problembehandlungen

Abbildungsverzeichnis

Abbildung 1 Weltkarte des MMORPG’s Ragnarok Online, Quelle [39]

Abbildung 2 Client/Server-Architektur

Abbildung 3 Verbindungsorientierter Paketheader

Abbildung 4 Nachrichtenorientierter Paketheader

Abbildung 5 Proxyserver-Architektur

Abbildung 6 Kommunikationsarten und Protokolle des Engineports

Abbildung 7 Verbindungsorientierter Paketheader der Client/Server-Kommunikation

Abbildung 8 Verbindungsorientierter Paketheader der Inter-Proxy-Kommunikation

Abbildung 9 Ausschnitt der Klassensstruktur des Servers

Abbildung 10 Ausschnitt der Klassensstruktur des Clients

Abbildung 11 Überblick des Client/Server-Datenflusses und der involvierten Funktionen

Abbildung 12 Überblick des Inter-Proxy-Datenflusses und der involvierten Funktionen

Abbildung 13 Weiterleitung und Verarbeitung einer Benutzeraktion

Abbildung 14 Paketstruktur des Zustandupdates eines Remoteclients

Abbildung 15 Beispiele auftretender Objekte der Spielwelt, Quelle: [33]

Abbildung 16 Beispiel eines Spielermodells (Xaero), Quelle: [33]

Abbildung 17 Differenz der Bandbreitenanforderungen zweier Synchronisations-Intervalle

Abbildung 18 Bandbreitenanforderungen der verschiedenen Synchronisations-Intervalle

Abbildung 19 Bsp. einer erfolgreichen Anwendung des Action Reordering, Quelle: [25]

Abbildung 20 Ausschnitt aus dem Kontrollfluss der Paketverarbeitung

Abbildung 21 Zeitlicher Ablauf der verschiedenen Synchronisationsschritte

Abbildung 22 Benutzerinterface mit Konsolenfenster

Abbildung 23 Graphisches Benutzerinterface der Applikation

Abbildung 24 Einstellungsmenü des Spielermodells

Abbildung 25 Verschiedene Hierarchien der Ergebnisanzeige

Abbildung 26 Koeffizienten der Berechnungszeiten der C/S- und Proxyversionen

Abbildung 27 Berechnungszeiten der C/S- und Proxyversionen für einen Tick

Abbildung 28 Bandbreitenanforderungen der C/S- und Proxyversionen für einen Tick

Abbildung 29 Bandbreitenanforderungen der C/S- und Proxyversionen in kbps

Abbildung 30 Vergleich der Berechnungszeiten der Server in Münster und Lübeck

Abbildung 31 Abbildung in dieser Leseprobe nicht enthalten-Kennlinien

Abbildung 32 Bandbreiten der ein- und ausgehenden Kommunikation

Abbildung 33 Ermittelte Spieleranzahlen des Skalierungstestes

Tabellenverzeichnis

Tabelle 1 CLC_MOVE-Nachricht

Tabelle 2 Deltakomprimierte SVC_PLAYERINFO

Tabelle 3 Ausschnitt aus dem Spielzustand eines Clients auf dem Server

Tabelle 4 Implementierung des Remoteclientflag

Tabelle 5 Zusammenfassung der vorgestellten Synchronisationsintervalle

Tabelle 6 Besonders relevante Konsolenvariablen

Tabelle 7 Voreinstellungen der Server-Konfiguration

Tabelle 8 Voreinstellungen der Client-Konfiguration

Tabelle 9 Maximale Werte der Bandbreitenkoeffizienten

Tabelle 10 Lastverteilung des Experimentes

Danksagung

Bedanken möchte ich mich zunächst bei Prof. Fischer für das etwas außergewöhnliche Thema dieser Arbeit, welches in besonderer Weise meine Interessen im IT-Bereich widerspiegelt. Außerdem bei Christian Werner von der Universität Lübeck für seine Hilfe bei der Evaluierung über das Internet. Insbesondere möchte ich mich bei Jens Müller von der Universität Münster, für seine stets schnellen Hilfestellungen zu Fragen seiner Diplomarbeit und sein langfristiges Engagement, bedanken.

Mein größter Dank gilt meinen Eltern für ihr spezielles längerfristiges Engagement in Bezug auf meine Ausbildung. Danke.

1 Einleitung

Seit einiger Zeit zeichnet sich der Trend ab, dass im Genre der Mehrbenutzer-Echtzeitspiele (Multiplayer Games) bzw. speziell im Bereich der First-Person-Shooter (FPS) versucht wird, die Anzahl von Teilnehmern pro Spielpartie zu erhöhen. In einigen der bereits erschienenen Spiele, wie Joint Operations und Söldner - Secret Wars [23, 24], als auch bei dem noch in der Entwicklung befindlichen Battlefield 2 [22], wird bereits die Marke der 100 Mitspieler überschritten. Dieser Wunsch nach erhöhter Skalierbarkeit unterliegt jedoch im Moment, neben den Bandbreitenlimitationen, den Restriktionen der verwendeten Netzwerk-Architekturen (Client/Server, Peer-to-Peer) im kommerziellen Bereich [1].

Die dieser Arbeit zugrunde liegende Proxy-Plattform wurde entwickelt, um die Probleme der heutigen Mehrbenutzer-Echtzeitspiele, wie Skalierung der Teilnehmerzahlen, Serverengpässe und Fairnessunterstützung, zu lösen. In der Proxy-Netzwerkarchitektur sind die an einer Partie teilnehmenden Clients jeweils mit einem von mehreren, einen virtuellen Server bildenden, Proxyservern verbunden. Der Spielzustand liegt dabei als lokale Kopie auf den Proxies vor und wird über Benachrichtigungen zwischen ihnen synchronisiert. Ein spezieller Masterserver übernimmt besondere Aufgaben, z.B. das Aufbauen und Verwalten einer Spielsitzung. Für die Unterstützung des Spielens über das Internet werden die Proxyserver kommunikationsnah zu den Clients betrieben. Auf diese Weise soll die Latenz der Client/Proxy-Kommunikation möglichst gering bleiben. Ein Szenario für einen derartigen Aufbau ist beispielsweise die Betreibung der Proxyserver bei Internet Service Providern.

In dieser Arbeit werden nun anhand der Portierung eines Mehrbenutzer-Echtzeitspiels, im Speziellen eines FPS, die Vorteile des Einsatzes der Proxy-Architektur für ein solches Spiel evaluiert. Die für die Portierung eingesetzte 3D-Engine ist die QFusion-Engine [10]. Diese kommt zum Einsatz, weil entscheidende Kriterien wie Aktualität, Serverskalierbarkeit sowie Wartung und Pflege durch den Support einer aktiven Internet-Community erfüllt werden. Die quelloffene QFusion-Engine emuliert das erfolgreiche Mehrbenutzer-Echtzeitspiel Quake III [11] und stellt damit einen allgemeinen und weit verbreiteten Vertreter des FPS-Genres dar. Mit einer Engine wird das Grundgerüst eines Computerspiels bezeichnet, welches unter anderem die Abbildung einer dreidimensionalen virtuellen Welt zum Inhalt hat. Eine solche Engine besteht im Wesentlichen aus Bibliotheken von Funktionen mit deren Hilfe Spielinhalte verschiedener Art wie Grafik, Sound oder bspw. Physik realisiert werden können und die Interaktion verteilter Teilnehmer ermöglicht. Durch die Portierung der Engine auf die Proxy-Architektur können somit auch zukünftige Projekte umgesetzt werden, die über die Emulation des Spiels Quake III hinausgehen.

Im weiteren Verlauf des 1. Kapitels werden die Hintergründe für die Wahl der QFusion-Engine erörtert. Kapitel 2 der Arbeit beschäftigt sich zunächst mit den für die Portierung relevanten Grundlagen der Ausgangsversion der QFusion-Engine. Es wird die verwendete Client/Server-Netzwerkarchitektur zusammen mit dem dabei eingesetzten Netzwerkprotokoll vorgestellt. Anschließend werden die Hauptprogrammschleifen (Mainloops) der beiden Applikationstypen Client und Server beschrieben. Dadurch wird eine Vorstellung über die inneren Abläufe zur Generierung des jeweils nächsten Spielzustands vermittelt. Des Weiteren werden die Spielzustandselemente identifiziert die letztlich auf die Proxyserver repliziert werden müssen. Im zweiten Teil des Kapitels wird ein Überblick über den Aufbau, den Fairnesssupport und die Kommunikationsmöglichkeiten der einzusetzenden Proxy-Architektur gegeben. Es wird ebenfalls auf das Konzept für die Synchronisation des Spielzustands: Die Eventual Consistency eingegangen. In Kapitel 3 wird die Implementierung des Framework-API’s der Proxy-Architektur in den Netzwerkcode der QFusion-Engine erläutert. Begonnen wird mit der Vorstellung der eingesetzten Kommunikationsarten der Client- und Inter-Proxy-Kommunikation sowie der dafür benutzten Protokollheader. Die Implementierungen des Client- und Serverobjektes, welche die Schnittstellen der Proxy-Architektur zur Engine darstellen, werden im Anschluss daran aufgezeigt. Ein Überblick über die in den Client- und Inter-Proxy-Datenfluss involvierten Funktionen sowie die Erläuterung des Remoteclient-Konzeptes schließen das Kapitel ab. Diese Ausführungen sollten ein Verständnis der erfolgten Implementierung vermitteln und zukünftige Arbeiten ermöglichen. Mit der Synchronisation des verteilten Spielzustandes beschäftigt sich das Kapitel 4. Zu Beginn des Kapitels werden beispielhaft die notwendigen Schritte zur Synchronisation des Spielzustandes nach einer neuen Clientinteraktion veranschaulicht. Darauf aufbauend werden die verschiedenen auftretenden Interaktionen kategorisiert. Für jede identifizierte Aktionsart wird anschließend die Implementierung des Synchronisationskonzeptes vorgestellt. Des Weiteren werden mögliche Zeitpunkte innerhalb eines Ticks^[1] für die Initiierung der Zustandssynchronisationen diskutiert. Das implementierte Verfahren (Action Reordering) zur Verbesserung der Fairness zwischen qualitativ unterschiedlich angebundenen Clients wird anschließend ebenso, wie die spezifischen Synchronisationsaufgaben des Masterservers beschrieben. Aus der letztlich angeführten Hauptprogrammschleife des Proxyservers ist die verwendete zeitliche Abfolge der unterschiedlichen Synchronisationsschritte zu ersehen. Kapitel 5 beschäftigt sich mit der Installation und Benutzung der portierten 3D-Engine. Hierbei wird auf das Starten der verschiedenen Applikationen ebenso, wie auf die Benutzung der Konsole eingegangen. Anschließend werden die voreingestellten Konfigurationen präsentiert und es wird auf eventuell notwendige Änderungen eingegangen. Das Kapitel endet mit einigen Anmerkungen über die Benutzung des Spiels und die Einstellungen des Spielermodells. Kapitel 6 stellt die Ergebnisse der Evaluation der Portierung vor. Dazu werden zunächst zwei Skalierbarkeitsmodelle eingeführt mit deren Hilfe die in der Engine gemessenen Werte beschrieben werden. Anschließen folgen die Auswertungen zweier Evaluationstests. Einerseits wird die Client/Server-Version der Engine mit der portierten Version innerhalb eines lokalen Netzes verglichen. Andererseits wird ein auf mehrere Standorte verteilter Test der Engine ausgewertet. In Kapitel 7 erfolgt eine Zusammenfassung der Arbeit und es wird ein Ausblick auf zukünftige weitergehende Themenbereiche gegeben.

1.1 Die Wahl der Engine

Bei der Wahl der zu portierenden Engine wurde neben dem offen zugänglichen Quellcode insbesondere darauf geachtet, dass die anschließenden Kriterien erfüllt werden.

Aktualität. Idealerweise sollte die Engine so gut wie möglich den Stand der aktuellen kommerziellen Produkte (Quake III, Unreal Tournament 2003…) repräsentieren [11, 12]. Dadurch würde die Leistungsfähigkeit der Proxy-Architektur anhand aktueller Spieltechnologien gemessen und somit eine hohe Glaubwürdigkeit erreicht.

Server-Skalierbarkeit. Das Spiel muss eine typische Client/Server-Architektur besitzen ( 2.1.1 ), in welcher der Server den gültigen Spielzustand berechnet und damit die Hauptrechenlast trägt. Demgemäß ist folglich durch eine Verteilung der Last auf mehrere Server eine Skalierung der Spielerzahlen möglich.

Mapgenerierung. Es sollte möglich sein, weitläufige Karten (Maps) für große Spielerzahlen zu erzeugen und auf eine Vielzahl von bereits existierenden Maps zuzugreifen.

Weiterentwicklung, Wartung und Pflege. Ein fortgeführter Support der Engine, über die Version auf der die Arbeit basiert hinaus, wäre wünschenswert.

Zu Beginn der Arbeit wurden unter diesen Gesichtspunkten diverse Open-Source-Projekte untersucht, unter anderem:

- BZFlag [14]
- Cube- Engine [15]
- Quake I und Quake II [7]
- Tenebrae- Engine [16]
- Open-Quarz- Engine [17]
- QbismFusion- Engine [18]
- QFusion- Engine [10]

Der Hauptanteil der existierenden Projekte sind Erweiterungen der veröffentlichten Quake I und II Quellcodes und damit in den meisten Aspekten ähnlich. Die untersuchten Projekte waren alle mehr oder weniger gut geeignet. Es stellte sich allerdings heraus, dass die gewählte QFusion-Engine die oben genannten Gesichtspunkte mit Abstand am Besten erfüllte.

1.2 Die QFusion-Engine

Die QFusion-Engine wurde entwickelt, um eine Open Source Engine zu erschaffen, welche die Fähigkeit besitzt, Kontexte (Maps, Waffen, ect.) des Spiels Quake III Arena anzuzeigen. Die Engine ist eine Erweiterung und Veränderung des unter der GPL-Lizenz veröffentlichten Quake II Quellcodes [7]. Eine vollständige Liste der Features findet man in [4]. Die Engine erfüllt dementsprechend die Kriterien Aktualität und Server-Skalierbarkeit [6]. Für die Portierung wurde die QFusion-Engine Version 6.0 und die Modifikation SplitMod Version 2.0 als Basis verwendet [19]. Durch diese Modifikation können auch die Quake III Arena Spielermodelle eingesetzt werden. Es existiert eine Fülle von Karten für Quake III und damit auch für die QFusion-Engine [30]. Weiterhin können Karten über diverse Editoren und Tools (Q3Radiant, Q3map2…) generiert werden [20, 21], womit das Kriterium der Kartengenerierung erfüllt wird. An der Engine arbeitet ständig eine Handvoll Entwickler, die mit der Weiterentwicklung und Pflege beschäftigt sind, so dass in regelmäßigen Abständen neue Versionen erscheinen. Bei Fragen, beispielsweise zur Quellcodeanalyse, kann man sich an das Entwicklerforum wenden [13]. Aus diesen Gründen ist ersichtlich, dass sich die Engine hervorragend als Basis für diese Arbeit eignete.

1.3 Verwandte Arbeiten

In letzter Zeit wurden diverse Anstrengungen im Bereich der IT-Forschung unternommen deren Ziel es war, die Skalierbarkeit von Mehrbenutzerspielen zu erhöhen. Bevor mit den Ausführungen über die Portierung des First Person Shooters QFusion auf die Proxy-Architektur begonnen wird, sollen noch einige weitere erforschte Ansätze kurz vorgestellt und bewertet werden.

In [38] wird eine skalierbare Client/Server-Architektur vorgestellt. Die dort erreichte erhöhte Skalierbarkeit resultiert aus einer Partitionierung der Spielwelt und der daraus folgenden Lastverteilung der Partitionen auf die eingesetzten Server. Ein Client hingegen wird innerhalb einer Session, entsprechend des Aufenthaltsortes seiner Spielfigur (Avatar) in der virtuellen Welt bzw. innerhalb einer Zone, verschiedenen Servern zugewiesen. Diese Partitionierung der Spielwelt findet auch bereits im kommerziellen Bereich des Genres der MMORPG’s^[2] statt und ermöglicht tausenden von Spielern eine Koexistenz in der jeweiligen Spielwelt. Abbildung 1 zeigt beispielhaft die Aufteilung der Spielwelt des japanischen MMORPG’s Ragnarok Online. Die Spielwelt hat

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1 Weltkarte des MMORPG’s Ragnarok Online, Quelle [39]

eine Vielzahl weitgehend unabhängiger Zonen, die jeweils von einem einzelnen Server verwaltet werden können. Unter Ausschluss der Möglichkeit, dass alle Spieler versuchen in eine einzige Zone und damit auf einen Server zu gelangen, erreicht man auf diesem Wege nahezu unabhängige Client/Server-Architekturen. Dieser Ansatz hat allerdings mehrere Nachteile für einen Einsatz im Bereich der FPS. Der Übergang von einem Server zum Anderen ist zeitaufwendig und erzeugt Spielflussunterbrechungen. Die Spielwelten bzw. Maps von First Person Shootern sind deutlich kleiner als die von MMORPG’s. Würde man diese partitionieren, sind Zonenwechsel und damit Unterbrechungen des Spielflusses die Regel. In dem Fall, dass Interaktionen nahe den Serverübergängen erlaubt sind, müssen diese speziell behandelt werden und sind ebenfalls kritisch [38, 6]. Des Weiteren kann man nicht ausschließen, dass sich zeitweise der Großteil der Spieler in einem Bereich befindet. Besonders nicht bei den durch das Spiel Battlefield eingeführten speziellen Spielmodi (Eroberung, Verteidigung, ect.) [22]. In diesem Anwendungsszenario stellt das Vorgehen der Proxy-Architektur, die Autorität über die Spieler zu partitionieren, einen deutlich besser skalierenden Ansatz dar.

Auch in [41] wurde versucht die Skalierbarkeit von Massively Multiplayer Games (MMG’s), durch eine Partitionierung der auftretenden Rechenlast, zu steigern. Die Aufteilung der Last erfolgt darin allerdings anhand von Spielergruppen und nicht durch eine generelle Partitionierung der Spielwelt. Dies ist möglich, da sich in den meisten MMG’s insbesondere in MMORPG’s immer nur eine Gruppe von Spielern an einer Stelle der Spielwelt befindet und dort einer Aufgabe (Quest) nachgeht oder sich beispielsweise duelliert. Die Interaktionen der vielen anderen Spieler haben deshalb auch keinen Einfluss auf deren Teil des Spielzustands. Die Zugehörigkeit eines Spielers zu einer Gruppe bzw. die Gruppenbildung basiert jeweils auf einem spielspezifischen Interessenmanagement durch Sichtbarkeits- und Einflussbereiche. Updates über Änderungen des Zustandes werden in der Folge auch nur innerhalb dieser Gruppen propagiert. Leider ist auch genau aus diesem Grund dieser Ansatz nicht geeignet die Skalierbarkeit von First Person Shootern zu erhöhen. Schließlich sind auch die Bemühungen auf diesem Gebiet dahingehend gerichtet die Anzahl gleichzeitig miteinander interagierender Spieler anzuheben. Gerade in Kampfsimulationen wie Battlefield 2 liegen aufgrund der Vehikelsimulationen die meisten Spieler im Einflussbereich der Mitspieler und verschlechtern somit die Möglichkeit der Gruppenbildung [22].

Eine andere Herangehensweise, zur Erhöhung der Skalierbarkeit von Mehrbenutzerspielen, präsentiert die Arbeit aus [40]. Darin wurde die Serverapplikation des FPS-Spiels Quake auf eine Version mit multiplen Threads portiert und anschließend auf einem Mehrprozessor-Host evaluiert [7]. Im Rahmen der Realisierung der Parallelisierung von Quake, stellte sich die Synchronisation des, nun durch mehrere Threads verwalteten, Spielzustandes als äußerst schwierig und laufzeitkritisch heraus. Bei den Auswertungen der Evaluationstests ergaben sich, bedingt durch das Locking von Teilzuständen, Synchronisationswartezeiten, die bis zu 40% der Berechnungszeit betrugen. Folglich ergab auch die Evaluation der Portierung, auf einem Host mit 8 Prozessoren, lediglich 25% mehr unterstützter Clients im Vergleich zur sequentiellen Originalversion. Im Gegensatz dazu wird sich im Lauf dieser Arbeit zeigen, dass bereits mit nur zwei Proxyservern ein Skalierungsvorteil von bis zu 40% zusätzlicher Teilnehmer im Vergleich zur Orginalversion mit Hilfe der Proxy-Architektur erreicht werden konnte.

Die QFusion-Engine und die Proxy-Architektur

In diesem Kapitel werden die für diese Arbeit relevanten Technologien, der Portierung zu Grunde liegenden QFusion-Engine, beschrieben. Das Verständnis dieser Techniken ist für den weiteren Verlauf der Arbeit entscheidend, da die Portierung so nah wie möglich an den ursprünglichen Konzepten vorgenommen wurde. Dazu wird die verwendete Netzwerkarchitektur zusammen mit dem eingesetzten Netzwerkprotokoll vorgestellt. Anschließend werden die Hauptprogrammschleifen (Mainloops) der Client- und Serverapplikation beschrieben. Des Weiteren werden die Spielzustandselemente identifiziert die auf die Proxyserver repliziert werden. Abschließend wird ein Überblick über die Funktionsweise und den Aufbau der für die Portierung verwendeten Proxy-Netzwerkarchitektur. Das einzusetzende Synchronisationskonzept (Eventual Consistency) wird ebenfalls im zweiten Teil des Kapitels erläutert. Mit diesem Kapitel erhält der Leser einen Überblick über die Softwarekomponenten, welche die Interaktion und Synchronisation der verteilten Spielsimulation eines Mehrbenutzer-Echtzeitspiels realisieren.

2.1 Die QFusion-Engine

Zu Beginn dieses Abschnittes werden die Client/Server-Netzwerkarchitektur und das eingesetzte Protokoll der QFusion-Engine zusammen mit dessen Headern dargelegt. Dabei wird auch auf die wichtigsten Nachrichtentypen und die zur Verringerung des zu versendenden Datenvolumens verwendete Deltakomprimierung eingegangen. Ferner werden die Abläufe innerhalb der Mainloops der beiden Applikationstypen (Client, Server) vorgestellt, um eine Vorstellung über die inneren Abläufe zur Generierung des jeweils nächsten Spielzustands zu vermitteln. Im Anschluss wird auf den Ausschnitt des Server-Datenmodells eingegangen, der die synchronisationsrelevanten Elemente des Spielzustandes beinhaltet.

2.1.1 Netzwerkarchitektur

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2 Client/Server-Architektur

Die in der Engine eingesetzte Architektur ist die im Allgemeinen in Multiplayer-Spielen verwendete Client/Server-Architektur [6]. In diesem Szenario sendet der Client die Aktionen seines Spielers an den Server (1). Der Server empfängt alle Aktionen der Clients und berechnet den daraus folgenden Spielzustand, siehe Abbildung 2. Darin inbegriffen sind die Legalitätsprüfung der Aktionen, die Berechnung der Auswirkungen der Clientinteraktionen und das Voranschreiten aller vom Server kontrollierten Elemente der Spielumgebung (2). Im nächsten Schritt werden allen Clients die daraus resultierenden neuen Spielerzustände sowie die aktualisierten Zustände der Objekte mitgeteilt (3). Diese zeigen daraufhin eine aktualisierte Sicht auf die Spielwelt an. Im folgenden Abschnitt wird ein Überblick über das für die Kommunikation eingesetzte Protokoll und die im Zusammenhang stehenden Konzepte gegeben.

2.1.2 Netzwerkprotokoll

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3 Verbindungsorientierter Paket-header

Die QFusion-Engine wie auch ihre Derivate (Quake I, II…) verwenden für die Versendung von Daten ausschließlich das UDP-Protokoll [7, 36]. Der Großteil des Kommunikationsaufwandes erfolgt dementsprechend auch unzuverlässig. Zur Kompensation der entstehenden Nachteile, wie Paketverluste, Duplikation und Vertauschung der Paketreihenfolge werden zusätzlich Paketsequenznummern eingesetzt. Für die Realisierung und Verwaltung des Netzverkehrs existiert deshalb eine Art Netzkanal (Struktur netchan_t , Anhang B) zu jedem Client, in dem unter anderem die Sequenznummer des zuletzt empfangenen Paketes gespeichert wird. Nachfolgende Pakete mit kleineren Sequenznummern und Duplikate können infolgedessen verworfen werden. Einige wenige Performance unkritische Transmissionen, wie Initialisierungsphase bzw. Verbindungsaufbau, Veränderung des Spielermodells und z.B. der Inhalt des Client-Inventars, werden auf UDP basierend zuverlässig übertragen. Dies geschieht, in dem die Sequenznummern dieser Pakete durch ein „Zuverlässigkeitsbit“

Abbildung in dieser Leseprobe nicht enthalten

(0x800000000) gekennzeichnet werden. Trifft solch ein zuverlässig zu versendendes Paket bei seinem Empfänger ein, wird von diesem bei der nächsten Sendegelegenheit die Sequenznummer des Paketes, inklusive gesetztem Bit, zurück an den Paketsender übertragen. Transmissionen werden folglich solange wiederholt, bis die entsprechende Sequenznummer einer zuverlässigen Transmission in dem zweiten Fragment des Headers ( Abbildung 3 ) eines empfangenen Paketes enthalten ist. Aufgrund des ständig beiderseitigen Sendens von Informationen (Aktionen und Zustandsupdates) können die nötigen Bestätigungen (Acknowledgements) eines erfolgreichen zuverlässigen Transports auf diese Weise im regulären Datenverkehr integriert werden. Die Versendung von zusätzlichen ACK-Paketen, wie im Fall von TCP, kann somit entfallen [35]. Einer der Paketheader der bidirektionalen Kommunikation ist in Abbildung 3 dargestellt, wobei die angegebenen Zahlen für die Bytegröße des jeweiligen Fragmentes stehen. Das dritte Headerfragment^[3] bezeichnet den Port der Clientapplikation um eventuelle Adressierungsfehler auf Internetroutern nachträglich zu korrigieren. Darauf folgt mindestens ein Block aus Nachrichtentyp und den Daten der Nachricht (Payload). Der gesamte Datenverkehr bei dem dieser Header Verwendung findet unterliegt einer Huffman-Komprimierung [Codelink16], wodurch eine Verringerung des Datenvolumens des jeweiligen Paket-Payloads erreicht wird.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4 Nachrichtenorientierter Paketheader

In dem Fall das der jeweilige Netzkanal noch nicht initialisiert ist oder für spezielle Belange, wenn z.B. an alle Clients gesendet werden soll, wird der Header aus Abbildung 4 verwendet. Weitere Informationen findet man in [Codelink02] und [8].

2.1.2.1 Nachrichtentypen

Die wichtigste Nachricht die vom Server zu einem Client versendet wird, ist die Nachricht SVC_FRAME. Sie beinhaltet all die Informationen die der Client benötigt, um eine aktualisierte Sicht, somit ein neues Bild (Frame) der Simulation, anzuzeigen. Inbegriffen sind die Frame- und Deltaframe-Nummer des Komprimierungs-Verfahrens ( 2.1.2.2 ), die Nachricht die den Spielerzustand aktualisiert SVC_PLAYERINFO und die Nachricht die den Zustand aller im Sichtfeld des Client liegenden Objekte aktualisiert SVC_PACKETENTITIES.

Der Client sendet hauptsächlich Nachrichten des Typs CLC_MOVE. Darin enthalten sind die Benutzeraktionen die aus den Eingaben des Users resultieren. In einem Paket wird jeweils die aktuelle Aktion (Struktur usercmd_t, Anhang B) zusammen mit den letzten beiden Aktionen versendet. Dies dient dem Server für Voraussagen auf Basis der Geschwindigkeit und Beschleunigung des Clients [6] und der Kompensation von Paketverlusten. Tabelle 1 gibt einen kurzen Überblick über den Inhalt der CLC_MOVE-Nachricht.

Eine Auflistung aller verwendeten Nachrichtentypen findet man in [Codelink01] und [8]. In [28] werden des Weiteren einige näher erläutert.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1 CLC_MOVE-Nachricht

2.1.2.2 Deltakomprimierung

Die QFusion-Engine setzt zur Reduktion des Datenaufkommens an mehreren Stellen verschiedene Versionen einer Deltakomprimierung ein. Besonders relevant ist die Komprimierung der Clientupdates ( SVC_FRAME ) durch den Server. Diese wird ermöglicht, in dem beim Übertragen des Updates ein Deltaframe angegeben wird, d.h. die Nummer eines Updates, welches als Basis für die Bildung des neuen Frames dient. Versendet werden dann nur die Elemente eines neuen Updates, die sich zu dem Deltaframe unterscheiden. Auf beiden Seiten wird dafür eine gewisse Anzahl alter Zustände zur Referenzierung gespeichert. Damit der Server Kenntnis über das vom Client als letztes empfangene Update hat, übermittelt der Client mit jeder CLC_MOVE die entsprechende Framenummer ( Tabelle 1 ). Auch die Nachricht CLC_MOVE ist innerhalb ihres Wiederholungsteils komprimiert. Das erste Benutzerkommando wird noch unkomprimiert in die Nachricht übernommen, bei dem zweiten und dritten Kommando werden dann mit Hilfe der Bitmaske die Felder markiert, die sich gegenüber dem Deltakommando geändert haben und nur noch diese werden versendet.

Beispiel anhand der SVC_PLAYERINFO

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2 Deltakomprimierte SVC_PLAYERINFO

Die Tabelle 2 soll eine Vorstellung der Effizienz der Deltakomprimierung, am Beispiel der Nachricht die den Spielerzustand aktualisiert, vermitteln. Es wird die Nachrichtengröße der SVC_PLAYERINFO mit und ohne aktivierte Deltakomprimierung Abbildung in dieser Leseprobe nicht enthalten, in Abhängigkeit von der jeweilig durchgeführten Spielerbewegung, in Bytes angegeben. Die Werte wurden mit Hilfe der Methode QPA_SV_SendRemoteCL Update aufgezeichnet [Codelink03]. Dieses typische Bsp. zeigt den Vorteil der Verwendung des Verfahrens, da der hier auftretende Kommunikationsaufwand um 33-56% verringert werden konnte.

2.1.2.3 Checksummen

Zur Vorbeugung von Manipulationen und damit zum Schutz des Inhaltes einer Benutzerkommando-Nachricht ( CLC_MOVE ), wird über den Kontext dieser Nachricht eine Checksumme gebildet. Der zur Generierung der Signatur verwendete Algorithmus ist MD4 [9]. Von den erzeugten 128 Bit pro Signatur werden 8 Bit für eine Nachrichten-Checksumme verwendet. Nähere Informationen findet man in [6] und [Codelink04].

2.1.3 Server-Mainloop

In diesem Abschnitt soll der Mainloop der Serverapplikation der QFusion-Engine näher beschrieben werden. Der Server-Mainloop wird durch die Methode SV_Frame(_)^[4] [Codelink05] repräsentiert. Das wiederholte Ausführen dieser Methode generiert jeweils einen neuen Spielzustand, ein so genanntes Serverframe. Dieser neue Spielzustand wird vom Server nach einer Zeitspanne von ca. 100ms, auch Länge eines Ticks genannt [1], mit Hilfe der Nachricht SVC_FRAME ( 2.1.2.1 ) an die Clients versendet. Im Wesentlichen werden die folgenden Schritte zur Generierung eines neuen Serverframes abgearbeitet:

1. Auslesen, verifizieren und verarbeiten aller vorhandener Clientpakete. Es wird jeweils das erste Paket das beim Server eintrifft, als aktuell zu verarbeitendes gewählt. Speziell die Clientkommandos der Nachricht CLC_MOVE ( 2.1.2.1 ) werden durch die Methode ClientThink(_) [Codelink06] zu einem neuen Spielzustand verarbeitet.
2. Als nächstes zieht der Server von der Ticklänge die Berechnungszeit des letzten Frames ab und schläft für die Dauer der Differenz. Bei einer stetigen Erhöhung der Spieleranzahl, bis hin zur maximal unterstützten Anzahl, konvergiert diese Differenz gegen Null. Ist ein Paket eingetroffen wird Schritt 1 erneut ausgeführt und anschließend ruht der Server für die noch verbleibende Zeit. Nach Ablauf dieser Zeit werden nun aufgrund des Voranschreitens der Simulationszeit die Zustände aller von dem Server kontrollierten Objekte (Waffen, Rüstungen…) aktualisiert. Zu diesem Zweck dient die Methode G_RunFrame() aus [Codelink07] .
3. Das Ende eines Durchlaufs durch den Mainloop ist durch das Übermitteln des neuen Spielzustandes, mit Hilfe der Methode SV_SendClientMessages() [Codelink03], an die Clients gekennzeichnet. Dafür ist es nötig, dass der Server zur Generierung eines clientspezifischen Updates die relevanten Informationen aus dem Gesamtspielzustand filtert. Durch die Reduktion der Updateinformationen auf die Objekte des Sichtbarkeitsbereiches (Viewspace) des Clients, werden die Bandbreitenanforderungen gesenkt und Betrugsversuche (Cheating) verhindert.

Die benötigte Zeit für die Abarbeitung dieser Schritte hängt maßgeblich von der Anzahl der Clients ab und bildet zugleich eine obere Grenze für die Anzahl der unterstützten Clients pro Spielsitzung. Für ein akzeptables Gameplay muss der Server eine Rate von 10 Clientupdates pro Sekunde (Tickrate) einhalten. Durch zu viele Clients wird der Server überfordert und kann die Tickrate nicht mehr erfüllen, so dass das Spiel zunehmend ruckelt (lagged) und unspielbar wird.

2.1.4 Client-Mainloop

Die Clientapplikation bleibt zwar bei der Portierung bis auf wenige Ausnahmen unangetastet, ist jedoch für die Steuerung der Synchronisationsintervalle des Servers von Interesse (vgl. 4.4). Die Hauptprogrammschleife der Clientapplikation wird durch die Methode CL_Frame(_) [Codelink08] implementiert. Ähnlich zum Server erzeugt das wiederholte Durchlaufen dieser Methode ein neues Clientframe bzw. eine aktualisierte und dem Benutzer angezeigte Sicht auf die virtuelle Welt. Eine Ausführung des Client-Mainloops besteht im Wesentlichen aus den folgenden Schritten:

1. Auslesen und verarbeiten eventuell vorhandener Serverpakete. Auch hier wird jeweils das erste Paket das eintrifft, als aktuell zu verarbeitendes gewählt. Im Speziellen werden die Clientupdates des Servers ( SVC_FRAME ) durch die CL_ParseFrame() Methode aus [Codelink09] verarbeitet.
2. Als nächstes wird mit Hilfe der CL_SendCommand() [Codelink08] eine Nachricht generiert ( CLC_MOVE), welche die aktuelle Benutzeraktion repräsentiert. Anschließend sendet der Client die Nachricht an den Server.
3. Im letzten Schritt wird durch die SCR_UpdateScreen() Methode in [Codelink12] das aktuelle Frame angezeigt.

Der Client durchläuft diese Schleife mit einer individuellen und variablen Bildwiederholrate (Framerate), die aus der Komplexität der darzustellenden Szene und der Leistungsfähigkeit des Hosts resultiert. Für ein flüssiges Spielerlebnis muss die Clientframerate wesentlich höher liegen als die Tickrate des Servers es ermöglicht. Aus diesem Grund lässt man die Clientapplikation mit Hilfe derselben Bewegungsroutinen die auch der Server verwendet die Spielerposition bestimmen und anzeigen (Movement Prediction) [10, 6]. Auch wenn dieser Zustand erst noch durch den Empfang eines Zustandsupdates vom Server ( SVC_FRAME ) bestätigt werden muss. Der Server empfängt demzufolge innerhalb eines Ticks mehrere Nachrichten des Typs CLC_MOVE pro Client. Diese repräsentieren die Aktionen zwischen den Updates und synchronisieren die Simulationen. Damit eine sehr hohe Framerate auf dem Client nicht die zur Verfügung stehende Bandbreite überlastet, bestimmt man eine obere Grenze für die maximal erlaubte Bildwiederholrate. Zu diesem Zweck wird die Konsolenvariable cl_maxfps ( 5.3.1 ) gesetzt.

2.1.5 Ausschnitt des Server-Datenmodells

Die von der Engine simulierte virtuelle Welt besteht aus den statischen Informationen (Geometriedaten, Texturen, …) der jeweils geladenen Kartendaten (pk3-Dateien) und den Objekten (Entities), wie beispielsweise Spielern, Monstern oder Waffen. Der Spielzustand ist innerhalb der Engine stark verteilt, weshalb im Folgenden nur der Teil des Server-Datenmodells beschrieben werden soll, der von der Game-DLL ( 5.5 ) kontrolliert wird und für die Arbeit besonders relevant ist. Die zuvor erwähnten Objekte sind Instanzen der Struktur edict_t [Codelink14] und über ein globales Array zugreifbar:

Abbildung in dieser Leseprobe nicht enthalten

Handelt es sich bei einem solchen Objekt um einen Avatar^[5], enthält die Instanz der Struktur einen gültigen Zeiger auf eine gclient_t-Struktur. Diese und die übergeordnete edict_t beherbergen dann die Informationen über den Zustand eines Clients auf dem Server und sind somit von besonderem Interesse. In der folgenden Tabelle 3 werden aus diesem Grund die Attribute der Strukturen vorgestellt, die die wichtigsten Elemente des Spielzustandes eines Clients repräsentieren und im späteren Verlauf auf die Proxyserver repliziert werden.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3 Ausschnitt aus dem Spielzustand eines Clients auf dem Server

Ein Objekt enthält einen gültigen Zeiger auf eine gitem_t-Struktur, vorausgesetzt es handelt sich bei dem Objekt um einen benutzbaren Gegenstand (Item), etwa Waffen, Rüstungen oder Munition. Diese Struktur beinhaltet die Informationen, welche die Eigenschaften des Gegenstands beschreiben. In [Codelink10] werden die Items der globalen Liste itemlist vordefiniert.

Weitere Informationen über den von der DLL verwalteten Spielzustand und über einige der inneren Abläufe kann man in [29] finden. Allerdings beziehen sich die dort gemachten Angaben auf Quake II, während jedoch die Quellcodeorganisation der QFusion-Engine eher Quake III ähnelt, sodass die Angaben nur bedingt zutreffen.

2.2 Die Proxy-Architektur

In den nachfolgenden Abschnitten werden die von der Proxy-API angebotenen Arten der Kommunikation und das Konzept (Eventual Consistency) für die Synchronisation des verteilten Spielzustandes, welches von der Applikation zu implementieren ist, vorgestellt. Im Anschluss wird auf die Möglichkeiten einer Unterstützung des fairen Spielens eingegangen.

2.2.1 Aufbau der Netzwerkarchitektur

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5 Proxyserver-Architektur

Der Aufbau der Proxy-Architektur ähnelt dem einer replizierten Client/Server-Architektur [1]. Die an einer Spielsession teilnehmenden Clients sind mit einem von mehreren Proxyservern verbunden, siehe Abbildung 5. Der jeweils notwendige Teil des Spielzustandes, der zur Berechnung der momentanen Spielersicht auf die virtuelle Welt dient, liegt als lokale Kopie auf

den Clients vor. Die aus den Benutzeraktionen resultierenden Veränderungen des Spielzustandes werden mit Hilfe von Benachrichtigungen zwischen den Proxies synchronisiert. Anschließend werden die neuen Zustände über die jeweils verantwortlichen Server an deren Clients propagiert. Der Spielzustand wird folglich durch einen verteilten virtuellen Server kontrolliert, welcher aus der Vereinigung der beteiligten Proxyserver aufgebaut ist. Einer der Proxyserver wird als Masterserver gestartet und hat zusätzliche Aufgaben, wie etwa Synchronisationssteuerung, Generieren von Spielereignissen und Loggin.

2.2.2 Möglichkeiten der Kommunikation

Zum besseren Verständnis der Kommunikationsarten der Architektur, kann man einen Proxy und die mit ihm verbundenen Clients als Teilarchitektur betrachten und sie mit einer Client/Server-Architektur vergleichen. Demgemäß kommunizieren die Clients ausschließlich mit ihrem Server über einen 1-zu-1-Kanal. Die Proxy-Architektur bietet Funktionen an, die mehrere Stufen der Zuverlässigkeit beim Transport von Daten realisieren. Die unterste Ebene markiert die direkte Verwendung des UDP-Protokolls. Darüber hinaus wird eine zeitlich begrenzte zuverlässige Übertragung auf Basis von UDP über die Funktionen der Kategorie sendTimedReliable angeboten. Das heißt, dass Pakete nach Verlusten nur innerhalb eines benutzerspezifischen Intervalls neu versendet werden. Die oberste Ebene wird durch die Verwendung des TCP-Protokolls realisiert [2].

Isoliert man die Proxyserver erhält man wiederum eine Architektur, die mit einer Peer-to-Peer-Architektur vergleichbar ist. Die Proxyserver kommunizieren untereinander über eine 1-zu-N-Verbindung, um den Spielzustand zu synchronisieren. Die Proxy-Architektur ermöglicht dies, in dem sie Multicast-Kommunikation unterstützt. Für den Fall das Multicasting nicht verfügbar ist wurde ein automatischer Unicast-Fallback implementiert. Beispielsweise im Regelfall der Übertragung von Daten über das Internet. Für dieses Szenario wird auch über die Implementierung eines Application Level Multicast nachgedacht [1].

2.2.3 Abstraktion der Adressierung

Die Proxy-Architektur abstrahiert die Adressierung der partizipierenden Clients und Proxyserver von Netzwerkadressen und Ports. Dies wird erreicht, in dem automatisch architekturweit eindeutige numerische Werte (Identifier) als Adressen vergeben werden. Des Weiteren können zusätzliche Identifier angefordert werden, um spezifische Daten zu kennzeichnen.

2.2.4 Synchronisation des Spielzustandes

Eines der Hauptmerkmale der verwendeten Proxy-Architektur ist die Replikation des Spielzustandes auf die teilnehmenden Proxyserver. Diese Replikation bedingt einen Synchronisationsmechanismus, welcher die Faktoren Skalierbarkeit, Antwortzeiten und Konsistenz entsprechend den Entwicklungszielen der Proxy-Architektur in Einklang bringt. Unter diesen Gesichtspunkten wurde ein Konzept der verteilten Authorität bezüglich einzelner Zustandsauschnitte, die Eventual Consistency, für die Synchronisation gewählt [25, 1]. Diese EC-Synchronisationsmethode ist dadurch gekennzeichnet, dass nicht alle teilnehmenden Prozesse zu einem bestimmten Zeitpunkt dieselbe Sicht auf die Daten haben. Der Grad der Konsistenz wird infolgedessen zu Gunsten der Performance und Skalierbarkeit verringert. Bei der Eventual Consistency wird jeweils einem Prozess, in dem Fall einem Proxyserver, die Verwaltung eines Teils der replizierten Daten zugewiesen. Nur dieser Server hat die Befugnis zur Manipulation der Daten, die in ihrer Gesamtheit den Zustand der mit ihm direkt verbundenen Clients ausmachen. Eine solche Veränderung am Spielzustand durch einen Proxy, wird unmittelbar an die partizipierenden Proxyserver weitergegeben und von diesen übernommen. Spielinformationen, wie

aufnehmbare Objekte (Waffen, Rüstungen…) oder NPC’s^[6], die nicht einem speziellen Client und damit einem Proxy zugeordnet werden können, sind von einem Masterserver zu verwalten. Damit auf diesem Wege kein Single Point of Failure geschaffen wird, sollte ein Election-Algorithmus implementiert werden, der im Falle eines Ausfalls des Masterservers die Zuständigkeit neu zuweist [26]. Durch das Managen des verteilten Spielzustandes mit Hilfe der vorgestellten Eventual Consistency erhält man eine robuste, effiziente Synchronisation und schnelle Bestätigungen der Benutzeraktionen durch die Proxyserver.

2.2.5 Fairnessunterstützung

Die Proxy-Architektur versucht die Folgen eventuell auftretender Latenz durch das Verfahren des Client Latency Levelling zu kompensieren und so das Spielen über qualitativ unterschiedliche Verbindungen gerechter zu gestalten. Zu diesem Zweck werden kontinuierlich Latenzzeiten zu den einzelnen Clients gemessen. Des Weiteren wird der Framework-API ein Grenzwert für die minimale Latenz übergeben. Die gesamte Kommunikation schneller angebundener Clients wird in der Folge für die jeweilige Latenzdifferenz zum Grenzwert verzögert. Auf diese Weise unterliegt das Verfahren einer einstellbaren oberen Grenze und verhindert, dass ein Spielen durch extrem schlecht angebundene Clients unmöglich wird.

Implementierung des Framework-API 3

Das Kapitel 3 und das darauf Folgende beschreiben, wie die in Kapitel 2 vorgestellte QFusion-Engine auf die Proxy-Architektur portiert wurde. In diesem Kapitel wird damit begonnen, einige Vorbemerkungen hinsichtlich der erfolgten Portierung anzuführen. Im Anschluss wird das eingesetzte Netzwerkprotokoll und die damit einhergehenden Kommunikationsarten der Client- und Inter-Proxy-Kommunikation vorgestellt. Die verbleibenden Abschnitte des 3. Kapitels beschäftigen sich mit der Einbindung der Framework-API in die Engine. Ein Überblick über die in den Client- und Inter-Proxy-Datenfluss involvierten Funktionen sowie die Erläuterung des Remoteclient-Konzeptes schließen das Kapitel ab.

3.1 Überblick und Notation

Der Quellcode der QFusion-Engine ist relativ umfangreich und auf 3 Bibliotheken und eine ausführbare Datei aufgeteilt (s. 5.5 ). Der Code umfasst mehr als 400 Dateien und ist hauptsächlich in C und stellenweise in Assembler programmiert worden. Durch die Nutzung der in C++ verfassten Proxy-API wurden alle neuen Dateien in C++ geschrieben und Teile der Engine nach C++ portiert [2]. Als Plattform für die Portierung wurde zunächst nur Windows XP^[7] gewählt, eine Linux-Version der Engine (Revision 7) ist allerdings im späten Verlauf der Arbeit fertig gestellt worden, so dass sich die Möglichkeit einer Portierung auf eine Linux-Version ergibt [10, 13]. Alle neu generierten Dateien befinden sich im Verzeichnis .\source\ProxyArchitecture. Darüber hinaus wurden alle ca. 150 Codefragmente im Originalquelltext, an denen Veränderungen vorgenommen wurden, durch „=BEGIN==============ProxyArchitecture==================PORT=“

markiert. Dies erleichtert das Verständnis des Portierungscodes und ermöglicht Updates auf neuere Engine Versionen.

Ist in den folgenden Kapiteln die Rede von der 3D-Engine, wird die neue portierte Version mit dem Namen QFusionProxyArchitecture referenziert. Referenzen auf die Ausgangsversion werden durch den Zusatz „original“ gekennzeichnet. Objekte die mit dem Bereichsauflöser gpa gekennzeichnet sind, stammen aus der Proxy-API und kennzeichnen deren Namensbereich Game Proxy-Architecture.

Das Unterstrichzeichen _ steht innerhalb von Funktionsdeklarationen als Abkürzung für die jeweils verbleibenden Parameter, dies ist stellenweise für die Übersichtlichkeit unabdingbar und notwendig, da die Standardabkürzung … bereits Element der C-Syntax ist.

Wird eine Methode als Server- oder Clientmethode bezeichnet, ist eine Elementfunktion aus der Schnittstelle der in den Abschnitten 3.3 und 3.6 vorgestellten Objekte gemeint.

3.2 Das Netzwerkprotokoll

In diesem Abschnitt werden die eingesetzten Kommunikationsarten der Client- und Inter-Proxy-Kommunikation sowie die dafür eingesetzten Protokollheader vorgestellt.

3.2.1 Client-Proxy-Kommunikation

Bei der Portierung der Engine auf die Proxy-Architektur wurde versucht, die gesamten Kommunikationsabläufe zwischen Server und Client weitgehend zu erhalten, da der originale Netzwerkcode entsprechend den Anforderungen der Applikation entwickelt und vielfach getestet wurde. In der originalen Engine erfolgt die gesamte Kommunikation unzuverlässig (vgl. 2.1.2 ) per UDP. Der Grund dafür ist, das diese Versandart optimal für den Einsatz im Bereich Echtzeit-Simulationen, in denen es auf schnellstmöglichen Transport der Daten zur Synchronisierung der Client- und Serversimulationen ankommt, geeignet ist. Die Nachteile, wie Paketverluste und Verlust der Reihenfolge werden durch die Engine wie in Abschnitt 2.1.2 erläutert ausreichend kompensiert. Der dafür nötige Aufwand ist vergleichsmäßig gering. Paketverluste werden durch die dreifach übertragenen Aktionen^[8] kompensiert. Die hierfür zusätzlich verwendete Bandbreite ist aufgrund der Deltakomprimierung der Aktionen gering. Das Sequencing der Pakete erfordert keine zusätzlichen Bestätigungspakete, da ständig bidirektional gesendet wird. Dementsprechend ist auch dieser Aufwand unbedeutend. Aus diesen Gründen wird auch der gesamte Datenverkehr zwischen Proxy und Client über die entsprechenden Schnittstellen der Proxy-API, auf der Clientseite sendUnreliable(_) und auf der Serverseite sendUnreliableClient(_), für unzuverlässige Kommunikation geleitet.

In den seltenen Fällen, in denen Daten zwischen Client und Proxy zuverlässig übertragen werden müssen, wird ebenfalls das existierende Verfahren über Paketsequenznummern verwendet ( 2.1.2 ). Eine Umstellung dieses Kommunikationsparts auf die von der API zur Verfügung gestellte zuverlässige Übertragung per TCP, hätte keine Vorteile und würde lediglich weitreichende Veränderungen des Quellcodes erfordern.

3.2.2 Inter-Proxy-Kommunikation

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6 Kommunikationsarten und Protokolle des Engineports

Die Inter-Proxy-Kommunikation wurde vollständig neu implementiert und unterscheidet sich in ihrer Art von der Client-Proxy-Kommunikation. Die verschiedenen Arten der verwendeten Kommunikation werden in Abbildung 6 zusammengefasst. Für den Fall, dass Daten selten, Performance unkritisch und damit zuverlässig zwischen den Proxies übertragen werden sollen, werden die Methoden sendReliableProxy(_) und sendReli-ableProxies(_) für zuverlässigen Transport mittels TCP, der Proxy-API verwendet. Anwendungsbeispiele sind das Ändern des Aussehens einer Spielerfigur oder das Wechseln der aktuellen Map.

Die einzigen Informationen die kontinuierlich und in kurzen Abständen übertragen werden, sind die Zustandsupdates für die Clients und eventuell deren Bestätigungen. In diesem Fall wird abhängig von der Verfügbarkeit einer Multicast-Kommunikation zwischen den Proxyservern die Art der Übertragung wie nachfolgend gewählt. Diese Unterscheidung ist aufgrund der auch für die Zustandsupdates der Inter-Proxy-Kommunikation implementierten Deltakomprimierung ( 2.1.2.2 ) notwendig. Ist kein Multicasting verfügbar, werden die Updates per unzuverlässigen Unicast über die Schnittstelle sendUnreliableProxy(_) der Framework-API übertragen. Die Komprimierungsmethode benötigt dann allerdings pro Client die Nummer des zuletzt empfangenen Updates, um eine Kompensation von Paketverlusten zu gewährleisten. Ein Proxyserver sendet demzufolge am Ende eines Ticks an jeden Proxy ein Bestätigungspaket (Acknowledgment). In diesem sind die Framenummern der zuletzt empfangenen Zustandsupdates der direkt mit diesem jeweiligen Proxy verbundenen Clients enthalten. Für ein Szenario in dem die Proxyserver über ein Netzwerk mit Multicast-Fähigkeit verbunden sind, ist ein zuverlässiger Versand der Updates über die Schnittstelle sendReliableProxies(_) des Frameworks implementiert. In diesem Fall sind keine ACK-Pakete erforderlich, da nicht zugestellte Pakete durch die API mit Hilfe von UDP-Unicast zugestellt werden und die Deltakomprimierung somit stets das letzte Frame referenzieren kann. Eine unzuverlässige Übertragung im Fall von Multicasting ist nur unter Deaktivierung der Deltakomprimierung implementiert, da aufgrund von möglichen Paketverlusten anderenfalls kein generelles Update an alle Proxies gesendet werden könnte. Diese Kommunikationsart ist unter Verwendung von Multicasting ab 4 Proxyservern zu favorisieren. Das liegt daran, dass dann der Nachteil der optimistisch geschätzt 50% größeren Zustandsupdates (vgl. 2.1.2.2 ) durch die Anzahl der Proxyserver kompensiert wird und dass bei steigender Proxyzahl der Kommunikationsaufwand nicht mit wächst. Die Art der Übertragung der Zustandsupdates kann durch die Makros QPA_UNRELIABLE_REMOTE_CLIENT_UPDATES und QPA_MULTICASTING [Codelink18] zur Kompilierzeit an die Laufzeitumgebung des Servers angepasst werden. Standardmäßig ist die Engine für den Unicast-Inter-Proxy-Betrieb, d.h. für unzuverlässige Clientupdates kompiliert.

3.2.3 Netzwerkprotokoll-Header

Die Engine verwendet entgegen der originalen Version drei verschiedene Paketheader. Der nachrichtenorientierte Paketheader aus 2.1.2 bleibt erhalten. Dieser Header wird für die originale Client/Server-Kommunikation, als auch für die nachrichtenorientierte Inter-Proxy-Kommunikation verwendet. Nachrichtenorientiert bedeutet im letzten Fall, dass der Header vorangestellt wird, wenn kein spezieller Client das Ziel der Transmission darstellt. Informationen demzufolge nur an einen oder an alle Proxyserver gerichtet sind und z.B. zwecks Spielsitzungsverwaltung übertragen werden:

- Synchronisierung der Proxyuhren durch den Master (siehe 4.7.1 )
- Spielsession-Informationen (Mapwechsel, Ende einer Spielrunde)
- Verbindungsaufbau der Clients zu den Proxyservern

Abbildung in dieser Leseprobe nicht enthalten

Der in Abbildung 7 aufgeführte verbindungsorientierte Paketheader ist nur leicht gegenüber der originalen Version aus 2.1.2 verändert worden. Lediglich der Zeitstempel der Paketentstehung wurde hinzugefügt (vgl. 4.6 ). Der Header wird ausschließlich von der originalen Client/Server-Kommunikation eingesetzt:

- void Netchan_Transmit (netchan_t *chan, int length, qbyte *data)

Abbildung in dieser Leseprobe nicht enthalten

Der Header der verbindungsorientierten Inter-Proxy-Kommunikation ist in Abbildung 8 zu sehen. Informationen wie Zustandsupdates, die einen speziellen Client betreffen werden durch Pakete mit diesem Header zwischen den Proxyservern propagiert. Das erste Fragment kennzeichnet die Sequenznummer des Paketes, falls es sich um ein unzuverlässig übertragenes, beispielsweise ein Zustandsupdate oder ein Bestätigungspaket, handelt. Daran anschließend wird der Empfänger (Client) des Paketes durch einen Identifier ( 2.2.3 ) angegeben. Das folgende Fragment ist momentan unbenutzt und bringt lediglich die beiden verbindungsorientierten Header auf gleiche Länge. Abschließend wird wiederum ein Zeitstempel angehängt. Die folgenden Methoden aus [Codelink03] generieren diesen Header:

Abbildung 8 Verbindungsorientierter Paketheader der Inter-Proxy-Kommunikation

- void QPA_SV_WriteDataPacket( qboolean reliable, client_t* sourceClient, unsigned long destProxyID, Timestamp *timestamp, sizebuf_t* message)
- void QPA_SV_WriteStringPacket( qboolean reliable, client_t* sourceClient, unsigned long destProxyID, Timestamp *timestamp, sizebuf_t* message, char* string, ... )

Die Payloads der Pakete der gesamten verbindungsorientierten Kommunikation werden, entsprechend dem originalen Enginecode, mit Hilfe einer Huffman-Codierung komprimiert [Codelink16].

3.3 Die Serverklasse QPA_Server

Die Implementierung der Framework-API wird über die beiden Klassen QPA_Server und QPA_Client realisiert. Die Applikation eines partizipierenden Proxyservers beinhaltet ein Objekt ( qPaServer ) des Typs QPA_Server, welches die Nutzung der Funktionalität der Proxy-Architektur ermöglicht. Hierfür erzeugt das Serverobjekt ein gpa::ProxySender-Objekt, worüber ausgehende Daten an die Proxy-Architektur übergeben werden. Mit Hilfe des QPA_ProxyMsgCallback-Objektes wird der Datenempfang über die Proxy-API implementiert. Es ist von der gpa::ProxyMessageCallback-Klasse abgeleitet und definiert deren virtuelle Funktionen für die verschiedenen Arten eingehender Kommunikation. Abbildung 9 zeigt einen Überblick über die verschiedenen verwendeten Klassen. Die Methoden des _callback - Objektes werden von einem der Proxy-Architektur-Threads aufgerufen, vorausgesetzt neue Pakete sind eingetroffen. Ein empfangenes Paket wird der implementierenden Applikation als Folge von Bytes übergeben. Aus diesen Daten und den beinhalteten Informationen des Paketheaders generiert der Server ein, dass Paket repräsentierendes, QPA_Message-Objekt und fügt es in die _incomingMsgs-Queue ein.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 9 Ausschnitt der Klassensstruktur des Servers

3.4 Scheduling der eingehenden Pakete

Die vom Proxyserver empfangenen Pakete (QPA_Message) werden in eine Queue vom Typ QPA_ThreadSafePriorityQueue eingefügt. Als die der Queue zugrunde liegende Datenstruktur, wurde ein Multiset, ein degenerierter assoziativer Container der C++ Standardbibliothek, gewählt [27]. Die Implementierung des Containers sortiert die übergebenen Objekte beim Einfügen nach der Größe eines Attributes. Das Sortierkriterium ist in diesem Fall das Alter der Pakete, gemessen an deren Zeitstempeln ( 3.2.3 ). Pakete mit einem identischen Zeitstempel werden nach der Reihenfolge ihres Eintreffens eingefügt (FIFO^[9] ), dieses Verhalten ist aufgrund der zu erhaltenden Reihenfolge der Sequenznummern der Pakete zwingend und verhindert den alternativen Einsatz der Priority-Queue aus der Standardbibliothek. Die Komplexität des benutzten STL-Containers^[10] liegt bei den verwendeten Operationen höchstens bei O(log(n)) [27]. Durch diese Implementierung einer Prioritäts-Queue wird ein effizienter Zugriff auf das jeweils älteste der vorhandenen Pakete ermöglicht. In Abschnitt 4.6 wird im Rahmen des Action Reordering detailliert auf die Auswirkungen dieses Schedulings auf ein faires Spielen eingegangen.

3.5 Die Klasse eingehender Pakete QPA_Message

Im vorletzten Abschnitt wurde bereits auf die Bildung von Instanzen der Klasse QPA_Message aus den von der Proxy-Architektur empfangenen Paketen eingegangen. Weiterführend sollen nun noch einige Erläuterungen zu den Attributen der in Abbildung 5.3 aufgeführten Klasse folgen. Neben den eigentlichen Paketdaten und dem Zeitstempel ist die Adressenstruktur netadr_t (Anhang B) von Interesse. Die Struktur bildet die Schnittstelle zwischen der originalen Host-Adressierung über IP-Adressen und Ports und der Adressierung der partizipierenden Teilnehmer über Identifier der Proxy-Architektur. Zur Erhaltung der Kompatibilität mit dem Code, der die originale Adressierung verwendet, beispielsweise die Netzwerkunterstützungsfunktionen^[11], wurde ein neuer Adresstyp NA_PROXYARCHITECTURE_ ID der Engine und damit der netadr_t hinzugefügt. Bei der Erzeugung eines QPA_Message-Objektes wird nun aus den von der Proxy-API übergebenen Informationen, der Identifier als pa_ID und der Typ des Hosts^[12], der sich hinter dem Identifier verbirgt, in qPaNetSrcType gespeichert. In dem Fall, dass die Adresse eines Clients aus dem Protokoll-Header ausgelesen wird, ersetzt diese die pa_ID der Adresse und es wird der Identifier des vermittelnden Proxies ins Feld qPaNetSrcProxy_ID der netadr_t verschoben.

3.6 Die Clientklasse QPA_Client

Abbildung 5.3 zeigt einen Überblick über die verschiedenen verwendeten Klassen die zur Bildung des Clientobjektes ( qPaClient ) vom Typ QPA_Client benötigt werden. Die Implementierung der Proxy-API für den Client ist ähnlich aufgebaut, wie die für den zuvor beschriebenen Server. Ermöglicht wird der Datenversand über die Proxy-Architektur entsprechend auch über die Erzeugung eines gpa::ClientSender-Objekts. Der Datenempfang ist, wie in Abbildung 10 ersichtlich, über die Clientgegenstücke der Callback-Objekte implementiert. Übereinstimmend werden auch aus den Byteströmen der eingehenden Pakete, vom Client Objekte des Typs QPA_Message erzeugt. Im weiteren Verlauf werden diese dann in die _incomingMsgs-Queue des Clients eingefügt. Diese Queue unterscheidet sich jedoch in ihrem Typ von der des Servers. Da auf der Clientseite kein Paket-Scheduling erforderlich ist, kommt die von der Proxy-API angebotene PA_ThreadSafeQueue für die Pufferung der eingehenden Pakete zum Einsatz. Diese verhält sich wie die standardisierte Queue und arbeitet nach dem FIFO-Prinzip.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 10 Ausschnitt der Klassensstruktur des Clients

3.7 Client/Server-Datenfluss

In Abbildung 11 wird ein Überblick über den Datenfluss der Client/Server-Kommunikation aus Sicht des Engine-Programmierers (funktionale Sicht) gegeben. Der Versand von Paketen wird von beiden Applikationstypen durch den Aufruf einer der beiden Funktionen der ersten Versandfunktionsebene erreicht. Je nachdem welche Kommunikationsart ( 3.2.3 ) verwendet werden soll. Die Methode Net_SendPacket bestimmt anschließend anhand des Hosttyps, welcher durch den ersten Parameter ( netsrc_t , Anhang B) angegeben wird, dass für die Transmission einzusetzende Objekt: qPaServer oder qPaClient.

Die Methode Net_GetPacket ist für das Entnehmen des nächsten zu verarbeitenden Paketes aus den Queues verantwortlich. Auch sie entscheidet entsprechend des Wertes ( NS_CLIENT, NS_PROXY ) ihres ersten Parameters über die zu verwendende Server- oder Client-Queue. Die Versionen der ReadPackets-Methoden rufen die Methode Net_GetPacket solange auf, bis sich keine Pakete mehr in den Queues befinden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 11 Überblick des Client/Server-Datenflusses und der involvierten Funktionen

3.8 Inter-Proxy-Datenfluss

Abbildung 12 vermittelt einen Überblick über den Datenfluss der Inter-Proxy-Kommunikation aus funktionaler Sicht. Für den Versand eines Paketes an einen Proxy muss eine der drei Funktionen der ersten Versandfunktionsebene aufgerufen werden. Entscheidend für die Wahl ist erneut die Kommunikationsart ( 3.2.3 ) und zusätzlich der Pakettyp. Anschließend wird anhand der benötigten Zuverlässigkeit die entsprechende Methode des Serverobjektes für den Datenversand ausgewählt.

Die Methode Net_GetPacket holt wiederum das aktuell zu verarbeitende Paket aus der Nachrichtenqueue und wird wiederholt von der QPA_SV_ReadPackets aufgerufen, bis alle Pakete eines Serverloops^[13] gelesen wurden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 12 Überblick des Inter-Proxy-Datenflusses und der involvierten Funktionen

3.9 Remoteclient-Konzept

Einen Teil des Spielzustandes auf dem Server repräsentiert die Liste der Clients in der Struktur server_static_t. Dieses Array wird durchlaufen, um an Hand einer übergebenen Adresse ( netadr_t , Anhang B) den Zielclient für die Ausführung eines Paketinhaltes zu identifizieren. Das folgende Codefragment zeigt ein Beispiel für einen solchen Durchlauf:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 4 Implementierung des Remoteclientflag

Die Clients werden hier durch die Struktur client_t beschrieben (s. Anhang B), ein weiterer Teil des Gesamtzustandes eines Clients, neben den in ( 2.1.5 ) vorgestellten Strukturen. Zur Integration der nicht direkt angebundenen Clients in den Spielzustand wurde der Typ des Remoteclients eingeführt. Diese, von anderen Proxyservern verwalteten Clients werden durch dieselben Datenstrukturen repräsentiert wie ihre Pendants und ebenfalls in die obige Liste aufgenommen. Unterschieden werden die Clienttypen durch den Parameter qPaRemoteClient, welcher an zwei Stellen des Clientzustands definiert ist, siehe Tabelle 4. Ein Server behandelt demzufolge zunächst alle Clients gleich, wird aber an spezifischen Stellen, nach der Prüfung des Remoteclientflags^[14], veranlasst, die Codeexekution zu überspringen oder mit dem nächsten Client fortzufahren. Auf diese Weise wurde eine kompakte und übersichtliche Zusammenführung der verteilten Kontrolle über die Clients in die existierenden Abläufe der Engine erreicht.

3.10 Zusammenfassung

In den zurückliegenden Abschnitten dieses Kapitels wurde aufgezeigt, auf welche Art und Weise die API der Proxy-Architektur in den Enginecode implementiert wurde. Es wurden die verschiedenen Arten der verwendeten Client/Server- und Inter-Proxy-Kommunikation vorgestellt sowie die dafür eingesetzten Schnittstellenmethoden. Die Vorgehensweise beim Versand von Daten ist anhand der beschriebenen Protokollheader und deren Erzeugung zu erkennen. Mit Hilfe der Übersichten über den Client/Server und Inter-Proxy-Datenfluss sowie der Erläuterung der involvierten Methoden ist ebenso ein schnelles Verständnis der Paketverarbeitung möglich. Durch diese Punkte und die Vorstellung der Client-, Server- und Paketklasse sollte es, neben dem Verständnis der Arbeit, auch möglich sein die Engine zu einem späteren Zeitpunkt zu erweitern. Dieses Kapitel stellt den ersten Teil der Portierung dar und liefert die notwendigen Werkzeuge, wie Datenversand, Paketscheduling und Identifikation der nicht direkt angebundenen Clients, für den zweiten Teil: Die Synchronisation des Spielzustands.

[...]

---

^[1] eine Abarbeitung des Server-Mainloops

^[2] Massively Multiplayer Online Role-Playing Games

^[3] Ist nur in Paketen enthalten, die vom Client zum Server übertragen werden

^[4] Auslassung der Parameter, siehe Notation 3.1

^[5] vom Spieler gesteuerte Figur bzw. Spielermodell

^[6] Non-Player Charakters

^[7] Abwärtskompatibilität wurde nicht getestet

^[8] jeweils das aktuelle und die zwei vorherigen

^[9] First In First Out

^[10] Standard Template Library

^[11] wie NET_IsLocalAddress, NET_AdrToString(…) etc. [Codelink01]

^[12] Client oder Proxy

^[13] Ein Durchlauf/Abarbeitung der Hauptprogrammschleife des Servers

^[14] Variable nimmt nur booleanische Werte an