Internet-Echtzeitspiele für mobile Netzwerke

Inhaltsverzeichnis

Abbildungsverzeichnis

1 Einleitung
1.1 Danksagung
1.2 Einführung
1.3 Aufbau der Arbeit Netzwerkarchitektur-Modelle

2.1 Peer-to-Peer-Netzwerkmodelle
2.1.1 Unicasting-Systeme
2.1.2 Broadcasting/Multicasting-Systeme
2.2 Client/Server-Netzwerkmodelle
2.2.1 Arten von Client/Server-Modellen
2.3 Anwendung in mobilen Ad-Hoc Netzwerken
2.4 Zusammenfassung Anforderungen an ein Netzwerkprotokoll

3.1 Ursachen von Latenz in Echtzeitspielen
3.2 Informationsabhängige Wahl des Netzwerkprotokolls
3.3 Zusammenfassung Problemlösungen für Mehrbenutzerspiele

4.1 Techniken der Server-Applikation
4.1.1 Unterteilung des virtuellen Raums
4.1.2 Filterung relevanter Informationen
4.1.2.1 Rasterbasierte Filterung
4.1.2.2 Objektbasierte Filterung
4.1.3 Schutz vor Cheatern und Hackern
4.1.3.1 Paket Replay
4.1.3.2 Reverse Engineering
4.1.3.3 Verschlüsselter Datenverkehr
4.1.4 Ephemeral Channels
4.2 Techniken der Client-Applikation
4.2.1 Methoden der Interpolation und Extraplolation
4.2.2 Reversible Simulationen
4.2.3 Dead-Reckoning-Algorithmen
4.2.4 Ansätze der Vorhersage-Techniken
4.2.5 Event-Locking Implementierungen in Echtzeitspielen

5.1 Unreal Tournament - Epic MegaGames
5.1.1Reduktion der Bandbreitenanforderung
5.1.1.1RelevanteAktoren
5.1.1.2Aktoren verschiedener Priorität
5.1.1.3Einschränkung des Wertebereichs
5.1.1.4Abschätzung von Spielerpositionen
5.1.2Konsistenzerhaltung durch Replikation
5.1.2.1Unzuverlässige/Zuverlässige Replikation
5.2 Quake – id Software
5.2.1 Filterung relevanter Informationen
5.2.2 Das Netzwerkprotokoll von Quake I
5.2.3 Positions- und Input-Updates in Quake II
5.2.4 Verteilung der Paketgrößen einer Spielsession
5.2.4.1Client-to-Server
5.2.4.2Server-to-Client
5.2.4.3Bandbreitenanforderungen
5.3 Half-Life – Valve Software
5.3.1 Abschätzung von Spielerpositionen
5.4 Zusammenfassung Mobile Ad-Hoc Netze

6.1 Zukünftige Probleme von Echtzeitspielen
6.1.1 Mobilität der Endgeräte
6.1.2 Limitierte Bandbreiten
6.1.3 Synchronisation des verteilten Spielzustands
6.1.3.1 Trailing-State-Synchronisation
6.1.4 Automatisches Finden von Mitspielern
6.1.5 Sicherheitsrelevante Aspekte
6.2 Portierung eines FPS auf mobile Ad-Hoc Netze
6.3 Zusammenfassung Zusammenfassung und Ausblick

7.1 Zusammenfassung
7.2 Ausblick

Literaturverzeichnis

Abbildungsverzeichnis

I Das Titelblatt zeigt eine Momentanaufnahme (screenshot) des FPS-Spiels Counter-Strike, Quelle: [Mann01].

2.1 Client/Server und Mirrored-Server Bandbreitenanforderungen einer modifizierten Quake-Version , Quelle: [CFK01].

4.1 Beispiel eines Seamless-Server aus Asheron’s Call 2: Fallen Kings, Quelle: [Thor03].

4.2 Server-Randbereiche sind schraffiert dargestellt und von Obj. 5 müssen z.B. 2 Proxy’s auf A, B erstellt werden , Quelle: Veränderte Reproduktion in Anlehnung an [Thor03].

4.2 Ein zu klein dimensionierter Server-Randbereich , Quelle: [Thor03].

4.4 Überblendung der divergierten Client-Sicht in die der Server-Simulation durch Interpolation , Quelle: Veränderte Reproduktion in Anlehnung an [Thor03].

4.5 Catmull-Rom-Spline Interpolation für kontinuierlich springende Objekte , Quelle: Veränderte Reproduktion in Anlehnung an [Thor03].

4.6 Auf Positions-Updates basierende Version des Dead-Reckoning-Algorithmus , Quelle: Veränderte Reproduktion in Anlehnung an [Watt01].

4.7 Bestimmung des Grads der verwendeten Tracking-Kurve, Quelle: [Watt01].

4.8 Momentaufnahmen alle 200ms, einer vom Client Nr. 1 initiierten Bewegung eines Panzers, Quelle: [Thor03].

5.1 a) Numerierung der einzelnen Oktanten des Octrees b) Einige Beispielobjekte innerhalb des virtuellen Raumes c) Octree-Darstellung entsprechend der Numerierungsregeln, dabei bedeutet ein schw.-Blatt das der zugehörige Raum komplett von einem Objekt (-teil) ausgefüllt wird, Quelle: [Fellner92].

5.2 Verteilung der Paketgrößen während einer Spielsession, von den Clients zum Server, Quelle: [Armit00].

5.3 Verteilung der Paketgrößen während einer Spielsession, vom Server zu den Clients, Quelle: [Armit00].

6.1 Beispiel einer Trailing-State-Synchronisation anhand zweier Kommandos, Quelle: Veränderte Reproduktion in Anlehnung an [CFK01].

6.2 Beispielhafte Behebung einer Inkonsistenz anhand des Kommandos B mit Hilfe der Trailing-State-Synchronisation, Quelle: Veränderte Reproduktion in Anlehnung an [CFK01].

1 Einleitun

1.1 Danksagung

Bedanken möchte ich mich bei Oliver Wellnitz für die Idee zu dieser Arbeit. Es ist ein Lichtblick hinsichtlich der Einbeziehung des Bereichs der Computerspiele-Entwicklung in den universitären Lehrbereich.

1.2 Einführung

Mehrbenutzerspiele repräsentieren mittlerweile eine der populärsten Arten der Gruppenkommunikation im Internet. In den letzten Jahren wurden Computerspiele mit Mehrspieler-Option bzw. reine Online-Mehrbenutzerspiele immer beliebter und kommerziell erfolgreich. Letzt genannte sind eine der wenigen Internet-Service, deren Nutzer bereit sind, eine monatliche Gebühr zu entrichten [SIG03]. In beiden Bereichen kann man alle Spiele-Genre wieder finden. Hierzu zählen die F irst P erson S hooter (Quake, Unreal Tournament, Counterstrike … ), die R ealtime S trategy G ames (Age of Empires, Command & Conquer…) und die Adventures (Ultima Online, Everquest, Diablo…). Man muß jedoch im Bereich der Onlinespiele, auf Basis der unterstützten Anzahl von Mitspielern pro Spielsession, zwischen denen mit weniger als 100 und den Massive-Multiplayer-Spielen (MMP) mit weit über 1000 Mitspielern, unterscheiden. Diese Arbeit befasst sich nun schwerpunktmäßig mit FPS-Spielen, die einen Online-Mehrspieler-Modus besitzen und bis zu 64 Spieler^[1] pro Session unterstützen.

Im Moment zeichnet sich der Trend ab, das durch die zunehmende Verfügbarkeit des Internets, vor allem durch mobile Geräte, die Zahl der Nutzer von Mehrbenutzerspielen einem schnellen Wachstum unterliegt und sich so ein zukünftiger Massenmarkt entwickelt. Eine diesen Trend unterstützende Entwicklung ist die der Mehrbenutzerspiele in mobilen Ad-hoc Netzen. Ad-hoc Netze sind drahtlose Netzwerke, deren Teilnehmer sich spontan, ohne Unterstützung von Infrastruktur, zusammenfinden und kommunizieren können. Die daraus folgende größte Schwierigkeit bei einer evtl. Portierung eines First Person Shooter, ist die

Mobilität der kooperierenden^[2] Endgeräte. Leistungsfähigkeit und Laufzeit der Geräte sind obendrein in vielen Fällen noch nicht ausreichend, um als Plattformen für Echtzeitspiele zu fungieren. Das gilt teilweise leider auch für die zur Verfügung stehende Bandbreite. Es ist jedoch abzusehen, dass die technologischen Vorraussetzungen in der Zukunft geschaffen werden. Zumindest insofern, dass grafisch abgespeckte und veraltete Versionen aktueller First Person Shooter auf der Mehrheit der Geräte gespielt werden können. Die jeweils aktuellen Spiele werden aufgrund der enormen und stetig wachsenden Hardwareanforderung nur einigen wenigen Endgeräten^[3] vorbehalten bleiben.

In dieser Arbeit werden die Problemlösungen heutiger Mehrbenutzerspiele in Hinblick auf ihre Anwendung in mobilen Ad-Hoc Netzwerken untersucht.

1.3 Aufbau der Arbeit

In Kapitel 2 werden zunächst einmal die verschiedenen Netzwerkarchitektur-Modelle, auf denen die aktuellen Mehrbenutzerspiele basieren, vorgestellt, analysiert und ihre Anwendung in mobilen Ad-Hoc Netzen untersucht. Kapitel 3 beschäftigt sich mit den Ursachen von während der Internet-Kommunikation auftretenden Verzögerungen. Im anschließenden Kapitel 4 werden Konzepte zur Lösung dieses und weiterer Probleme von Mehrbenutzerspielen durchleuchtet. Überdies werden einige Implementierungen der vorgestellten Konzepte, aus aktuellen Mehrbenutzer-Echtzeitspielen in Kapitel 5 aufgezeigt. Kapitel 6 beschäftigt sich letztlich, nach einem Überblick der Schwierigkeiten von Mehrbenutzerspielen in mobilen Ad-Hoc Netzen, mit der Anwendung der gewonnenen Erkenntnisse zu ihrer Bekämpfung. Das letzte Kapitel stellt eine Zusammenfassung der zuvor präsentierten Erkenntnisse dar und gibt einen Ausblick auf im Rahmen der Arbeit interessante Fragestellungen und zukünftige Untersuchungen.

Netzwerkarchitektur-Modelle 2

In diesem Kapitel werden die verschiedenen Netzwerkarchitektur-Modelle, auf denen die Kommunikation aktueller Mehrbenutzerspiele basiert, vorgestellt und analysiert. Es wird weiterhin untersucht, inwieweit sich diese Modelle in mobilen Ad-Hoc Netzwerken anwenden lassen.

2.1 Peer-to-Peer-Netzwerkmodelle

Die ersten Mehrbenutzerspiele (Doom, Descent, …) nutzten diese am leichtesten zu implementierende Art der Kommunikation. Wesentliches Merkmal dieser Modelle ist, dass jeder Teilnehmer mit allen anderen verbunden ist. Man unterscheidet je nach gebotener Funktionalität mehrere Arten:

2.1.1 Unicasting-Systeme

Ein Peer-to-Peer Unicasting-Modell ist die einfachste Art der verwendeten Systeme. Es besteht aus nur einer Applikation, die aus der Spiellogik und einem Modul das Nachrichten senden, empfangen, und bearbeiten kann, zusammengesetzt ist.

Bei n Teilnehmern muss ein Zustandsupdate eines Spielers, zu n-1 Mitspielern gesendet werden. Die Folge ist eine hohe Anzahl von Nachrichten und evtl., je nach Art des verwendeten Protokolls (3.2), offenen Verbindungen. Das System skaliert somit quadratisch zu der Anzahl der Mitspieler und ist deshalb für große Teilnehmerzahlen ungeeignet.

Nachteile ergeben sich auch bei der Skalierbarkeit der internen Bildwiederholrate (framerate). Diese wird durch die folgende Hauptprogrammschleife bestimmt: Zustands-Updates aller Spieler empfangen → Input des Spielers lesen → neuen Spielerzustand berechnen und versenden → Bild anzeigen ↑. Die Bildwiederholrate muss bei allen Mitspielern auf demselben Level^[4] (frame-locking) basieren [Treg02], um die Simulationen konsistent zu halten, d.h. die Hauptprogrammschleife kann nicht unterschiedlich

schnell durchlaufen werden. Dies macht es schwierig unterschiedliche Hardwarepotentiale^[5] auszunutzen.

Nachteilig ist ebenfalls das sich die Spieler verabreden müssen, um das Spiel gemeinsam zu starten, wenn sie sich nicht im selben Ethernet-Segment befinden und somit Broadcasting (2.1.2) nicht zur Spielerfindung verfügbar ist. Neue Spieler können dann auch nicht im Verlauf des Spiels teilnehmen. Eine Lösung des Problems stellt der Einsatz eines bekannten^[6] Slot-Servers dar. Dessen Aufgabe beschränkt sich auf die Initialisierung des Peer-to-Peer-Modus durch Übermittlung einer Teilnehmeradressliste. Jeder Server hat eine gewisse Anzahl von Slots zu vergeben, die der maximalen Spieleranzahl pro Session entspricht, so dass auch noch während des Spiels, solange noch Slots frei sind, Clients durch Anfrage an den Server dem Spiel beitreten können. Der Einsatz eines Slot-Servers markiert den Übergang zu einer Client/Server-Architektur (2.2) und beschreibt auf diese Weise ein hybrides System.

2.1.2 Broadcasting/Multicasting-Systeme

Einige der Probleme des oben vorgestellten Systems werden gelöst, wenn das zugrunde liegende Netzwerk das Versenden von Broadcast- oder Multicast-Nachrichten unterstützt. Mit Hilfe von Broadcasting kann man den Kommunikationsaufwand auf O(n) reduzieren. Dies bezieht sich auf den Grossteil der Nachrichten, die häufig und unzuverlässig^[7] übertragenen Zustandsupdates. Für zuverlässige Übertragungen erhöht sich der Aufwand evtl. durch wiederholt gesendete Nachrichten (retransmits). Bei sehr hoch skalierten Systemen mit mehreren hundert Teilnehmern ist der Aufwand trotzdem zu groß, da jeder Client jede Zustandsänderung empfangen und bearbeiten muss, auch wenn die Änderung nicht seine nähere Umgebung beeinflusst und somit irrelevant für das nächste Bild ist. Genau hier setzen Multicasting-Systeme an. Durch eine dynamische Partitionierung des Virtuellen Raums (4.1.2) werden Multicast-Gruppen gebildet und somit die Anzahl der Update-Nachrichten reduziert.

2.2 Client/Server-Netzwerkmodelle

Wegbereiter für die Verwendung der Client/Server-Architektur in der Spielentwicklung war das Spiel Quake. Bei diesem Modell sind alle Spieler bzw. Clients nur noch mit einem Server und nicht mehr untereinander verbunden. Die Server-Applikation empfängt und bearbeitet alle Nachrichten bzw. Anfragen (bewege, erzeuge…) der Clients und versendet dann gültige Zustandsupdates. Die Bandbreite der Serveranbindung und die Rechenleistung des Servers bestimmen folglich die maximale Anzahl von Spielern pro Server. Dieses Problem des Server-Flaschenhalses tritt an die Stelle des Problems der Anzahl der Nachrichten und Verbindungen bei Peer-to-Peer-Architekturen.

Da die Server-Applikation die Zustandsupdates verteilt, kann sie mit Hilfe von Sichtbarkeits-Algorithmen oder anderen Kontext bezogenen Regeln entscheiden, für welche Clients die Updates relevant sind (4.1.2). So kann der Kommunikationsaufwand, ähnlich wie beim Peer-to-Peer Multicasting, reduziert werden.

Der Server kann auch als vertrauenswürdige Instanz zum Schutz vor Cheatern und Hackern dienen (4.1.3).

Eine Client/Server-Architektur stellt letztlich die beste Lösung bei hoher Bandbreite und geringer Latenz dar. Deshalb wird sie auch von allen aktuellen FPS eingesetzt und im weiteren Verlauf der Arbeit favorisiert.

2.2.1 Arten von Client/Server-Modellen

Es gibt verschiedene Arten der Verwendung von Client/Server-Modellen, die durch die Funktionserfüllung (4.2) der Clients gekennzeichnet sind. Bei den ersten Mehrbenutzerspielen wie Quake, die Client/Server-Modelle verwendeten, spricht man von einer rigorosen (monolithischen) Anwendung. Die Clients waren reine Anzeige-Terminals, welche die Benutzereingaben an den Server sendeten und daraufhin eine Liste von anzuzeigenden Objekten empfingen. Mit der Entwicklung von Quake 2 wurde dann zunehmend Funktionalität bzw. Eigenverantwortung auf die Clients übertragen. Unreal führte schließlich ein generalisiertes Client/Server-Modell bei den Mehrbenutzerspielen ein. In diesem Modell bleibt der Server zwar die einzige, über die Evolution des Spielzustands entscheidende Instanz, jedoch spiegelt der Server einen Teil des Gesamtzustands auf jeden der Clients. Dadurch kann der Client, bei Anwendung derselben Spiellogik wie der Server, den Spielfluss voraussagen. In der Folge kommt es eher selten vor, dass der Server die Position des Clients ändern muss (5.1).

2.3 Anwendung in mobilen Ad-Hoc Netzwerken

Das sich im Internet stellende Problem der Verfügbarkeit der Broadcasting/Multicasting-Unterstützung wird in mobilen Ad-Hoc Netzen gelöst. Da es sich um lokale Netze handelt sind beide Dienste einsetzbar und man kann die beschriebenen Features nutzen. Der größte Vorteil eines Einsatzes einer Peer-to-Peer-Architektur in mobilen Ad-Hoc Netzen liegt jedoch in der hohen Fehlertoleranz und in der geringeren Latenz, im Vergleich zu einer Client/Server-Architektur. Der Ausfall eines Spielers ist relativ einfach zu kompensieren, da der Spielzustand zwischen allen bzw. durch alle Teilnehmer propagiert wird. Dessen ungeachtet überwiegen die in Tabelle 2.1 zusammengefassten Nachteile, insbesondere die Anfälligkeit gegenüber Cheatern und die Anwendung des Frame-Locking-Verfahrens. Des Weiteren nutzen die meisten am Markt positionierten Spiele Client/Server-Architekturen, so dass ein verbreiteter Einsatz dieser Architektur nicht zu erwarten ist.

Das größte Problem der Client/Server-Architektur in Bezug auf mobile Ad-Hoc Netze ist die Fehleranfälligkeit des Servers. Auf Grund von fehlender Infrastruktur und der Mobilität der Clients, ist die Übertragung der Serverfunktionalität auf einen der Clients nicht ausreichend fehlertolerant, da beim Ausfall des Servers das gesamte Spiel zusammenbricht und somit alle Clients betroffen sind. Einen ersten Ansatz dieses Problem zu lösen stellt die in [CFK01] vorgestellte Mirrored-Server-Architektur dar. Der Spielzustand wird hier auf mehrere topologisch verteilte Mirror-Server gespiegelt. Jeder der teilnehmenden Clients verbindet sich mit dem am nächsten liegenden Mirror-Server (sogen. ingress mirror). Die Server übertragen per zuverlässigen^[8] Multicasting die eingehenden Kommandos ihrer Clients an die anderen Server (sogen. egress mirror) und jeder der Server berechnet den daraus resultierenden aktuellen Spielzustand. Dieser wird den Clients wiederum per Unicasting mitgeteilt. Entgegen den Clients sind die Mirror-Server in dieser Architektur über ein privates Netzwerk mit Multicasting-Fähigkeit und geringer Latenz verbunden. Durch diese Trennung der Server-Server-Kommunikation von der Client-Server-Kommunikation und die Aufteilung der Last auf mehrere Server, wird ein weiterer Vorteil dieser Architektur, die abfallende Bandbreitenanforderung der Mirror-Server bei steigender Clientanzahl^[9], im Vergleich zu einer zentralisierten Version erreicht. In einer hierfür speziell angepassten Quake-Version wurde z.B. eine Last von 2Mbs an den Mirror-Servern und im Vergleich dazu 6Mbs am zentralen Server gemessen, bei 4 Mirror-Servern und 32 Clients (s.a. Abbildung 2.1).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1

Client/Server und Mirrored-Server Bandbreiten-anforderungen einer modifizierten Quake-Version [CFK01].

Diese Trennung und damit der Vorteil, kann jedoch nicht in mobilen Ad-Hoc Netzen aufrechterhalten werden, da alle Informationen über dasselbe Netz ausgetauscht werden müssen.

Die Motivation für die Entwicklung dieser Architektur lag in der Verringerung der Latenzkosten, die bei der herkömmlichen Kommunikation der Clients mit dem zentralisierten Server entstehen. Explizite Methoden zur Erhöhung der Fehlertoleranz sind deshalb nicht vorgesehen. Einzig die Aufteilung des Spielzustands auf mehrere Server kann man als ersten Schritt in Richtung erhöhte Fehlertoleranz werten.

Den Ansatz der Verteilung des Spielzustands aufgreifend und die Fehlertoleranz im Blickfeld wurde in [RWW03] eine Erweiterung der Standard Client/Server-Architektur, die Zone-based-Gaming-Architektur, vorgestellt. Diese wurde speziell zur Anwendung in mobilen Ad-Hoc Netzen entworfen wurde. Bei dieser Architektur werden mehrere Clients zusätzlich als Zonen-Server ^[10] ausgewiesen und sind dann für eine Teilmenge der am Spiel beteiligten Clients verantwortlich. Je nach Leistungsfähigkeit der Client-Hardware kann der Spieler entscheiden ob sein System zusätzlich als Zonen-Server fungieren soll. Die Zonen-Server empfangen die Updates ihrer Clients, berechnen den sich daraus ergebenen Spielzustand und senden diesen per Multicasting^[11] an die anderen Zonen-Server. Nachdem ein Zonen-

Server eine solche Änderung empfangen hat oder selbst einen neuen Spielzustand generiert hat, wird dieser wiederum mit Hilfe von Multicasting an die mit ihm verbundenen Clients verschickt. Im Angesicht der First Person Shooter ist die Übertragung der Spielzustände zwischen den Zonen-Servern, im Gegensatz zu einer Übermittlung der Client-Kommandos wie z.B. zwischen den Mirror-Servern, allerdings eher als kritisch zu bewerten. Einerseits können die sich aus der Verarbeitung der Client-Kommandos ergebenden Zustände weitaus mehr Bandbreite konsumieren, andererseits sind die vorzunehmenden Änderungen am Server-Code einer bestehenden Client/Server-Implementierung wesentlich komplizierter [CFK01].

Ebenfalls zu beachten ist, dass man in beiden Architekturen nun nicht mehr nur eine autoritative Instanz hat, sondern das sich die Server für ihre Entscheidungen untereinander abstimmen müssen. Eine Lösung für die Konsistenzerhaltung des durch die Server gemeinsam verwalteten Spielzustands ist in der Zonen-Server-Architektur noch nicht realisiert. Es wird jedoch auf einige, noch zu implementierende, Synchronisationsverfahren verwiesen, wovon das für den Bereich der First Person Shooter relevanteste Verfahren^[12] (trailing state synchronisation) in dieser Arbeit (6.1.3) noch näher erläutert wird.

Die für mobile Ad-Hoc Netze notwendige Fehlertoleranz wird erreicht, indem die Clients sich im Fehlerfall an einen geeigneten neuen Zonen-Server wenden können. Dies geschieht falls der momentan zuständige Server ausfällt oder die von den Clients überwachte Latenz zu groß wird. Des Weiteren wird, in dem Fall das ein Zonen-Server den Kontakt zu allen anderen Zonen-Servern verliert, dass Spiel aufgeteilt und der Server wird allein autoritativ.

Auch wenn in diesem Entwurf noch nicht alle Teilprobleme wie:

- Synchronisation des Spielzustands
- alternatives Versenden von Kommandos zwischen den Servern für existierende FPS
- automatische Zuweisung der Geräte als Zonen-Server
- Integration neuer Zonen-Server nach der Isolation eines Zonen-Servers
- Wiedervereinigung zuvor aufgeteilter Spiele

gelöst sind, stellt die Verwendung von mehreren Servern, die den Spielzustand gemeinsam verwalten, als Erweiterung der Client/Server-Architektur, die Architektur zukünftiger Mehrbenutzerspiele in mobilen Ad-Hoc Netzen dar. Solange die Server-Server-Kommunikation nicht zu große Verzögerungen verursacht, erreicht man durch eine solche Architektur die Vereinigung der Vorteile der Client/Server-Architektur mit einer ausreichenden Fehlertoleranz.

2.4 Zusammenfassung

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2.1

Zusammenfassung der Netzwerkarchitektur-Modelle und ihrer Eignung für Mehrbenutzerspiele ^{[13][14][15][16]}

Anforderungen an ein Netzwerkprotokoll 3

3.1 Ursachen von Latenz in Echtzeitspielen

Allgemein gilt als oberstes Gebot beim Design eines Netzwerkcodes für ein Echtzeitspiel, dass die Verzögerungen (delays) durch die Kommunikation der Spielinformationen nicht die Spielbarkeit, dass so genannte Gameplay, beeinflussen. Diese Verzögerungen auf dem Kommunikationskanal entstehen durch folgende interagierende Faktoren:

- Anzahl der Mitspieler^[17]
- Datenmenge der zu übertragenden Spielinformationen
- Bandbreite und Wartezeiten des Kommunikationskanals
- Hardware die der Verbindungsherstellung dient
- Grad der nötigen Zuverlässigkeit bei der Übertragung
- Aufwand bei der Bearbeitung der Nachrichten auf dem Server

Echtzeitspiele wie FPS sind durch rasante Bewegungen und häufige Richtungswechsel gekennzeichnet. Aus diesem Grunde sind sie auf einen ständigen Informationsaustausch zwischen Server und Client angewiesen, um die Simulationen konsistent zu halten. Geringere Bandbreiten mit niedrigeren Wartezeiten würden ein besseres Spielerlebnis ermöglichen als hohe Bandbreiten mit hohen Wartezeiten.

Hohe Latenz wird dem Spieler auf unterschiedliche Weise bewusst. Bei Spielen mit monolithischen Client/Server-Architekturen entsteht ein Ruckeln der Simulation bzw. eine verzögerte Reaktion, da jede Aktion von dem Server verarbeitet werden muss. Bei Peer-to-Peer- Architekturen läuft die Simulation flüssig, jedoch entstehen Sprünge in den Spielerpositionen und Spielzuständen. Solche Sprünge entstehen auch in den erweiterten, nicht monolithischen Client/Server-Architekturen aufgrund von Vorhersagefehlern (4.2). Hierbei sind fluktuierende Latenzzeiten für den Menschen schlechter zu kompensieren, als konstante Latenzen bis zu einer oberen Grenze.

Selbstverständlich spielt auch die Hardware, über die man mit dem Internet oder Ethernet verbunden ist, eine Rolle. So erhöhen zum Bsp. Standard-Modems die Latenz durch

Wartezeiten, bedingt durch interne Buffer, Kompressions- und Fehlerkorrekturverfahren. Durch Ausschalten solch entsprechender „Features“ erreicht man, dass die Pakete so schnell wie möglich versendet werden. Die erste Ebene auf der man Kommunikationsverzögerungen entgegenwirken kann, ist die Wahl des Netzwerkprotokolls in Abhängigkeit von der Art der zu übertragenden Spielinformationen.

3.2 Informationsabhängige Wahl des Netzwerkprotokolls

Bei der Wahl des zu verwendenden Protokolls gilt es zu beachten, dass die Verzögerungen auf dem Kommunikationskanal invers Proportional zur Zuverlässigkeit der Datenübertragung sind. Des Weiteren muss die auftretende Latenz der versendeten Informationen im Bereich unterhalb von 225ms liegen, um ein akzeptables Gameplay zu erreichen [Hend01]. Weitere Untersuchungen im Rahmen von Quake III Arena haben ergeben, dass die Latenz besonders im Bereich der First Person Shooter sogar unter 150 ms liegen muss, um die Spieler für längere Zeit bei Laune zu halten [Armit01]. Die Folge ist eine Aufteilung der Spieleinformationen in:

- Daten bei denen es auf die Reihenfolge und die zuverlässige Übertragung ankommt
- z.B. Objekte erzeugen, übereignen, entfernen
- Allgemein wird in dieser Kategorie TCP verwendet
- Daten die sehr oft und besonders schnell übertragen werden müssen
- z.B. Spielerpositionen
- In dieser Kategorie wird allgemein UDP eingesetzt und

zusätzlich evtl. Sequenznummern und einfache Bestätigungen (acknowledgements) (5.2.2).

In einigen Spielen wird nur auf unzuverlässige Übertragung gesetzt und je nach Art der Information entschieden, wie Paketverluste kompensiert werden. Im ersten Fall wird dann eine zuverlässige Übertragung simuliert, indem Bestätigungen und Paketwiederholungen eingesetzt werden. Andererseits werden Paketverluste im zweiten Fall nicht speziell behandelt sondern geduldet, da eine neue, aktuellere Übertragung ohnehin kurz bevorsteht. Entsprechendes gilt auch für den etwaigen Verlust der Reihenfolge der Übertragungen, indem zu spät eintreffende Pakete verworfen werden.

Ansätze zur Entwicklung eines zuverlässigen Protokolls basierend auf UDP, speziell für die Übertragung von Spieldaten, haben sich als nicht praktikabel erwiesen [Treg02].

3.3 Zusammenfassung

Zusammenfassend kann man 3 Ebenen, auf denen Verzögerungen entstehen können, identifizieren:

Verzögerungen auf Hardwareebene, bedingt durch:

- Geringe Bandbreiten und hohe Wartezeiten des Kommunikationskanals
- Die Netzwerkverbindung herstellende Hardware
- Standardmodems, Satellitenverbindungen

Verzögerungen auf Protokollebene, bedingt durch:

- Verwendete Netzwerkprotokolle
- Schnelles, unzuverlässiges UDP im Gegensatz zum langsamen, zuverlässigen TCP.
- Bei zuverlässigen Übertragungen wird die Latenz durch TCP- oder UDP-Paketwiederholungen^[18] erhöht.
- Das Warten auf eigene oder automatische Bestätigungen vergrößert die Latenz.

Verzögerungen auf Applikationsebene, bedingt durch:

- Verwendetes Netzwerkarchitektur-Modell
- Die Client/Server-Architekturen erzeugen eine höhere Latenz, als Peer-to-Peer-Architekturen, da die Informationen erst zum Server und wieder zurück übertragen werden müssen.
- Zeit für die Informationsverarbeitung auf dem Server
- Hängt von der Anzahl der Mitspieler, dem Aufwand zur Berechnung des neuen Zustands und der evtl. nötigen Server-Server-Kommunikation ab.
- Datenmenge der zu übertragenden Spielinformationen

Im Rahmen von mobilen Ad-Hoc Netzen stellen insbesondere die aus den Verzögerungen auf Hardwareebene resultierenden Probleme die Herausforderung für Mehrbenutzer-Echtzeitspiele dar (Kap. 6). Die für Internet-Mehrbenutzerspiele entwickelten Techniken zur Kompensation der Verzögerungen auf Protokoll- und Applikationsebene lassen sich auch in mobilen Ad-Hoc Netzen anwenden und werden im folgenden Kapitel vorgestellt.

Problemlösungen für Mehrbenutzerspiele 4

Dieses Kapitel befasst sich mit Problemen, die bei der Entwicklung von Mehrbenutzerspielen auftreten und stellt jeweils aktuelle Techniken zu ihrer Bekämpfung vor. Die meisten Probleme resultieren aus den Auswirkungen der in Kapitel 3 vorgestellten Latenz in Mehrbenutzerspielen.

Im Folgenden werden Techniken zur Erweiterung der Client/Server-Architektur, kategorisiert nach ihrer Zugehörigkeit zur Client- oder Server-Seite, vorgestellt. Pioniere auf dem Gebiet waren QuakeWorld und Quake 2, welche erstmals zusätzliche Simulations- und Vorhersage-Techniken auf der Client-Seite einführten.

[...]

---

^[1] aktuelle obere Grenze in FPS, gesetzt von Battlefield 1942

^[2] d.h. jedes Gerät leitet Nachrichten für andere Geräte weiter (Forwarding im multi-hop Netzwerk)

^[3] z.B. Laptops mit hoher Performance oder zukünftig spez. entwickelte Spiel-Endgeräte

^[4] es wird eine Zeitlang gewartet, bis alle Updates von allen Spielern eingetroffen sein müssen

^[5] höherwertige Hardware ermöglicht eine höhere Framerate und somit flüssige Simulationen höherer Qualität

^[6] feste IP-Adresse oder URL

^[7] Broadcasting/Multicasting-Übertragungen sind stets unzuverlässig

^[8] unabhängig von der Art des Ereignisses, welches das Kommando repräsentiert

^[9] topologisch gleichmäßige Verteilung wird unterstellt

^[10] nicht zu verwechseln mit den Zoned-Server aus ( 4.1.1 )

^[11] zuverlässiges und unzuverlässiges Multicasting wird unterstützt

^[12] wird auch in der zuvor beschriebenen Mirrored-Server-Architektur eingesetzt

^[13] im Fall von Multicasting

^[14] zukünftige Architektur wie bspw. Zone-based Gaming Architekture for Ad-Hoc Networks [RWW03]

^[15] wird durch die Aufteilung der Spieler auf mehrere Server relativiert

^[16] Aufwand für die Synchronisierung des Gesamtzustands zwischen den Servern

^[17] außer bei Peer-to-Peer Multicasting/Broadcasting

^[18] im Fall von TCP sind automatische Wiederholungen (retransmits) gemeint