\chapter{Latency-sensitive Applications and Scenarios}\label{chapter-applications-scenarios}

% -- Start of introduction
In this chapter, we start by examining interactive applications and discuss their network requirements in general.  We take an in-depth look at multi-player games and provide a classification into different game types each of which have distinct demands from the network. Furthermore, we present the current state of the art in mobile gaming and give an outline and rationale for games in mobile ad-hoc networks. We move on to discuss plausible scenarios in which mobile games are likely to be seen in the future. We conclude this chapter with evaluation criteria for mobile gaming in different scenarios which will be picked up again later on in the evaluation in Chapter~\ref{chapter-evaluation}. Finally, we present a brief summary.
% -- End of introduction

\section{Latency-sensitive applications}

Applications have been classified and differentiated in many different ways \REFMISSING. They can work synchronously or asynchronously, locally or in a distributed system, in a discrete or continuous fashion. In this section, we take a look at network applications that require a certain timeliness in their interaction with the user because the user interacts directly with a remote application or with another user through a network . In order to ensure a good user experience, such an application should give a reaction to any user action within an appropriate time frame. 

We define such distributed and interactive applications through the following three peculiarities: 
% Therefore, we define distributed interactive applications through the following three peculiarities: 
\begin{itemize}
\item[(1)] The application provisions a service directly to a user\\(instead of another machine) 
\item[(2)] The user expects a timely reaction to his actions
\item[(3)] The application runs in a networked environment
\end{itemize}

From a network point of view, a low end-to-end latency is the most promintent task for providing the user with a timely response. Therefore, we use the term {\sl latency-sensitive application} to describe these applications. Examples of latency-sensitive applications are multi-player games, video conferencing and video streaming with a control channel.  

Figure~\ref{figure-action-reaction} looks at an example of an latency-sensitive application in which two users communicate directly with each other and splits down the individual delays in the end-to-end communication process. In this figure, the red areas represent user-related actions including the decision process that leads to an action. The green fields stand for the time need by the users' computers to process and distribute data between the user and the network which includes tasks such as data processing by the program or the rendering of data for the user. Finally, the processing in the network includes transmission, propagation, queueing and processing delays inside the network itself. Regarding the number of users, the nature of interaction or the system architecture, the example presented in Figure~\ref{figure-action-reaction} cannot be generalized for all kinds of latency-sensitive applications. However, our classification into user, computer and network processing remains valid nonetheless. For the remainder of this work, we will focus on efficient network processing and a system architecture for interactive applications in mobile networks.
\begin{figure}
\begin{center}
\includegraphics[height=.8\textwidth,angle=270]{pics/applications-action-reaction.pdf} 
\end{center}
\caption{End-to-end delay breakdown for an latency-sensitive application}
\label{figure-action-reaction}
\end{figure}

The network requirements for some latency-sensitive applications can found in related work. For multi-player games, Begbeder et.al.\cite{Beigbeder04} concluded that round trip times between 100 and 200\,ms are advisable for fast-paced multi-player games.  In \cite{Dick05}, 
we have shown that delay requirements for multi-player games are very 
game-dependent and certain games require round trip times to be well 
below 150\,ms in order for the player to have a pleasant gaming experience.
The ITU-T recommendation G.114 also states that by a one-way 
delay of less than 150\,ms, ``most applications will experience essentially 
transparent interactivity''\cite{ITUG114}. Keeping in mind that, e.g., VoIP  
codecs also introduce delays in the order of 50\,ms for GSM or 80\,ms
for G.723.1, VoIP applications and multi-player games have similar requirements on network latency.
\TODO{Related work for video streaming}

Also important, but often to a less extent is the variation of latency and packet loss. 

%\section{Introduction}

%* Explain interactive vs. non-interactive applications
%   - Human perception (related work!)
%* Describe what the reader should expect from this chapter
%* Related work on the definition of interactive applications

%\section{Network requirements}


\section{Multi-Player Games}

% Introduction

Multi-player games are computer-based games where people can play or
compete with one another. In contrast to multi-player games, single-player
games allow only to play computer-generated figures. During the last two
decades and with the advancement of computer networks, like the Internet,
multi-player games have become more and more popular. Nowadays, the
majority of computer games is specifically designed for direct player
interactions.

%============================================================
%Markt f�r Computerspiele legt in Deutschland zu 

%Der Markt f�r Computer- und Videospiele hat in Deutschland im vergangenen Jahr mit einem Plus von 7,4 Prozent deutlich zugelegt und die Erwartungen der Branche �bertroffen. Insgesamt sei 2006 ein Umsatz von 1,13 Milliarden Euro erzielt worden, teilte der Bundesverband Interaktive Unterhaltungssoftware e.V. (BIU) am heutigen Mittwoch in Berlin mit. 

%Das Wachstum wurde danach vor allem durch Videospiele getragen. Trotz des Generationswechsels bei den Konsolen kletterte hier der Umsatz um 13 Prozent auf 652,6 Millionen Euro. Auch der Umsatz mit Spielesoftware f�r Handhelds legte um 58 Prozent deutlich auf 190 Millionen Euro zu. Der Markt f�r PC-Spiele blieb den Angaben zufolge dagegen mit 473,4 Millionen Euro Umsatz nahezu konstant (2005: 471,3 Millionen Euro). Mit 230 Millionen Euro machte die Branche im Dezember 2006 mit Abstand den meisten Umsatz, die Sommermonate Mai, Juni und Juli bildeten mit 61, 57 und 61 Millionen Euro die umsatzschw�chste Periode. F�r das laufende Jahr erwartet der Verband einen weiteren Umsatzanstieg, der voraussichtlich erneut durch Zuwachs im Videospiele-Sektor getragen wird. 

%Bereits in diesem Fr�hjahr k�nnte der Branche erneut ein Umsatzschub bevorstehen: Am 23. M�rz wird Sony seine neue Konsole PlayStation 3 auch in Europa auf den Markt bringen. In den USA und Japan ist das Ger�t seit November zu haben. Nach Erhebungen der Marktforschung NPD Group hat Nintendo mit seiner Konsole Wii im Januar allerdings sowohl die Playstation 3 als auch die seit �ber einem Jahr auf dem Markt erh�ltliche Xbox 360 von Microsoft �berholt. Mit 436.000 verkauften Wii-Konsolen �bertrumpfte das japanische Traditionshaus Microsoft wie auch Marktf�hrer Sony. Den Angaben zufolge rangierte die Xbox 360 mit 294.000 verkauften Ger�ten in dem Monat auf Platz zwei, gefolgt von Marktf�hrer Sony, der 244.000 Playstation 3 abgesetzt hat. (dpa) / (vbr/c't)
%============================================================

%============================================================

%Deutsche spielen zunehmend mit Handy und Konsole  

%Der Markt f�r PC- und Videospiele in Deutschland ist 2006 weiter gewachsen und soll aus Sicht der Hersteller nicht l�nger eine M�nnerdom�ne sein. Der Branchenumsatz stieg im vergangenen Jahr um 13 Prozent auf die Rekordmarke von 1,77 Milliarden Euro, wie der Bundesverband Informationswirtschaft, Telekommunikation und neue Medien (Bitkom) am heutigen Montag in Berlin mitteilte. Dabei legten Konsolentitel zu, w�hrend das Gesch�ft mit PC-Spielen stagnierte. Die Bitkom-Zahlen entstanden aus Berechnungen von Media Control und mit Hilfe der Industrie.
 
%Danach gingen in Deutschland im vergangenen Jahr insgesamt rund 2,9 Millionen station�re und mobile Spielkonsolen �ber die Ladentheken, das sind 400.000 mehr als 2005. Der Umsatz kletterte von 372 Millionen Euro (2005) auf 487 Millionen Euro (2006). Die Branche erwartet, dass dieser Trend insbesondere bei mobilen Konsolen weiter anh�lt. Auch bei den Konsolentiteln meldet die Branche hohe Wachstumsraten. Hier legten die Ums�tze von 702 Millionen Euro (2005) auf 780 Millionen Euro (2006) zu. W�hrend Konsolen damit weiter an Popularit�t gewannen, stagnierte der Verkauf von PC-Spielen. In diesem Segment wurden 2006 etwa 503 Millionen Euro umgesetzt, nur drei Millionen Euro mehr als im Vorjahr.

%Hohe Erwartungen hat die Branche bei Angeboten f�r Handys. Im vergangenen Jahr wurden rund 15 Millionen Spiele f�r 54 Millionen Euro heruntergeladen. Mehr als ein Drittel der Downloads entfiel dabei schon auf Frauen, wie Bitkom-Pr�sidiumsmitglied und Sony-Deutschlandchef Manfred Gerdes der dpa sagte. Um Frauen anzusprechen, wollen die befragten Anbieter st�rker auf Spielkonzepte setzen, bei denen es um Strategie und Emotionen gehe. Zudem sei Handyspielen inzwischen kein Jugendph�nomen mehr, da jeder dritte Nutzer 30 Jahre und �lter sei. Damit liegen die deutschen im internationalen Trend.

%Vielversprechend seien zudem "Multiplayer"-Angebote, bei denen �ber das Internet tausende Spieler gegeneinander antreten. Doch wird online nicht nur gezockt, sondern auch verkauft. Zu einem zentralen Thema f�r die Branche wird auch die Konkurrenz zwischen Online-Vertrieb und station�rem Einzelhandel. Die ersten Schritte in Richtung digitaler Vertrieb sind l�ngst getan, die Softwarehersteller umgehen mit Download-Angeboten den traditionellen Handel. Die zunehmende Verbreitung schneller Breitbandzug�nge spr�che zus�tzlich f�r dieses Entwicklung. (vbr/c't) 
%============================================================


% Anforderungen
%Every multi-player game has its own distinct set of network requirements. 
%This comes from 
%\begin{itemize}
%	\item[a)] the specifc nature of the game play itself, 
%	\item[b)] assumptions on network performance made by the game programmer, and 
%	\item[c)] by the use of specific latency compensation
%	mechanisms.
%\end{itemize}

Multi-player games offer a variety of different game plays from past-faced first-person shooters like Quake %\REFMISSING 
or Unreal Tournament %\REFMISSING 
to card games like poker or board games like chess. In-between there are strategy games  (e.g. Command and Conquer%\REFMISSING
), role-playing games like World of Warcraft%\REFMISSING
, sport games such as Need for Speed %\REFMISSING 
just to name a few examples.


The game play itself influences heavily the importance of latency, jitter and bandwidth

It is comprehensible that it is good, if one does.



Yet, games of the same category often have similar requirements.





the network requirements of interactive multi-player games remains
in spite of their 


%Thus the general requirements 

% Latency compensation techniques


% Categories ....
% List related work that categorises games (e.g. the game book on my desk!)

%To define 





%Over the last couple of years, multi-player games have become more and more
%popular. Additionally, new mobile devices now have sufficient resources to
%play these multi-player games in mobile and wireless networks. While
%commercial mobile game consoles start to emerge, we take a step forward and
%take a look at future mobile gaming.

--- 

Multi-player games can be distinguished in different categories. In his PhD dissertation, Tristan Henderson categorizes games into four groups: First-person shooters (FPS), real-time strategy games (RTS), massively multi-player online role playing games (MMORPG), and  non-realtime games. He also states that ``the FPS, RTS and MMORPG genres account for the majority of networked games''\cite{phdthesis-henderson}.

We take a different approach and look at multi-player games from the player's point of view.

Multi-player games -> (Continous actions, Discrete actions, hybrid games) -> (directly controlled avatars, indirectly controlled avatars), round-based

Because most games are developed as closed-source applications with llittle or no information about the internal methods of operation,  



We differentiate multi-player games in three general categories. %from which we derive general network requirements: 
Games with directly controlled avatars, games with indirectly controlled avatars and round-based games. Although, games 
Subsequently, we will discuss all three categories in detail. 

\begin{figure}
\begin{center}
\includegraphics[height=.8\textwidth,angle=270]{pics/multiplayer-categories.pdf} 
\end{center}
\caption{Multi-player game categories}
\label{figure-multiplayer-categories}
\end{figure}

\myglossar{Avatar}{An avatar is representation of a user in a shared virtual reality. Basically, it's the character that is played by the user.}

%--------------
Book\cite{NetOnlineGames},
Faerber -- CounterStrike\cite{Faerber02}
Lang -- Quake 3 \cite{Lang04}
-- Leider keine Papers zu RTS oder MMORPGs

MMOPGs often also use directly controlled avatars, but updates are sent less frequently to the players. Usually when two players fight in an MMOPG, the game uses a round-based fight mechanism to provide a fair result. (Often TCP). \REFMISSING
%-----------------


\TODO{Check if game servers or C/S in general is mentioned before. We are using it below to make our point.}

% **************************************************************************************************
%  MOBILE GAMING - STATE OF THE ART
% **************************************************************************************************

\subsubsection{Games with directly controlled avatars}

% Describe games
% Give examples
The first category describes games in which the player has direct influence over his avatar or character. This means that e.g. the player can move his virtual character by giving commands like forward, left, right, stop and so on. Any command or keystroke is transmitted to the game server which checks it for validity and reports back if such a move is allowed or not. Games with directly controlled avatars often use a first-person view where the players sees virtually through the eyes of his avatar. Another possibility is a bird's eye view where the players sees his virtual character from above. Examples of directly controlled games are first-person shooters or some sports games like car racing.

% Requirements
With directly controlled games, players expect almost instantaneous reactions of their avatar in according to their commands. For example, imagine the driver of a racing car who wants to make a turn at high speed. At 100\,km/h, the car travels one meter every 36\,ms. Achieving synchronism with such a high accuracy is very difficult when using a wireless network when you consider that the action has to be transmitted to the server, processed by the server, and then sent back to the player. Thus, directly controlled games are generally very challenging when it comes to its network requirements. Later on in chapter~\ref{chapter-qos}, we discuss network optimizations which can disguise bad network performances up to a certain point.

%Related work
Games with directly controlled avatars have been widely discussed in related work. F�rber\cite{Faerber02} looked at measurements from a 36~hour LAN party and determined the specific traffic characteristics for the first person shooter ``Counter Strike''. He found that a Counter Strike client on average sends and receives approx. 20\,packets per second each utilizing a bandwidth of 4\,KBytes/s total during the game. 
%
Beigbeder et.al.\cite{Beigbeder04} looked at the effects of loss and latency on ``Unreal Tournament 2003'', another first-person shooter. They noticed that users rarely even notice packet loss at or below 5\,\% and that shooting accuracy is greatly effected by 75--100\,ms latency. The comments from their players during their tests state that latencies as low as 100\,ms were noticeable and the players found latencies of 200\,ms annoying. The authors suggest to keep delay below 150\,ms and packet loss below 3\,\% to achieve an enjoyable user experience. 
%
Armitage\cite{Armitage03} found similar results for Quake III where player seem to prefer game servers with latencies less than 150 -- 180\,ms. Quak et al.\cite{Quax04} concluded from their experiments with Unreal Tournament that players notice impairment with delays above 60\,ms. They also mention that jitter does not play a prominent role with that particular first-person shooter game.
%
Nichols and Claypool\cite{Nichols04} analyzed the effects of latency on Madden NFL Football which remains playable even with delays of up to 500\,ms. They suggest that Madden NFL uses a ``prediction of the round trip time to delay user inputs in an attempt to compensate for any latency effects across both players''. This method, however, fails when latencies are asymmetric. Again, with bandwidth utilization below 20\,kB/s, Madden NFL does not require large link capacities. 
%
Wattimena et.al\cite{Wattimena06} have investigated Quake IV and found out that latency and jitter have both a significant impact with a regression coefficient $R=0.98$ on the perceived game quality and the results of the game. Especially the introduction of jitter resulted in a large negative effect on the subjective game quality. In \cite{Dick05}, we analyzed different kind of games and found that latency and jitter has a different effect on distinct games. For Counter Strike, the introduction of jitter was the most disturbing influence, where for Unreal Tournament 2004 only latency was the important factor. We concluded that the design of the network protocol and the latency compensation techniques used in these games mainly influence the behaviour of a game in different network situations.

% Not USED reference: Influences of network latency and packet loss on consistency in networked racing games
%* Predicting the perceived quality of a first person shooter: the Quake IV G-model


% Conclusion for directly controlled avatars

We can conclude that directly controlled games place high requirements on the network in order for the game to be playable and fun to the user. Latency and jitter are the most important factors for these kind of game. Packet loss does not play a prominent role and the loss of some packets (below five percent) of the game traffic hardly affects the game play. Finally, bandwidth is of no concern for directly controlled games when we look at the player' side\footnote{Bandwidth may be of concern for a game server. However, for the moment, we are focusing on the individual player and will discuss the server side later on.}. Games with directly controlled avatars often use UDP as transport protocol because the high network requirements don't allow for retransmissions or exponential backoffs which are present in reliable protocols such as TCP.


\myglossar{RTS}{Real-Time Strategy games}
\myglossar{FPS}{First-Person Shooter games}

\subsubsection{Games with indirectly controlled avatars}

% Describe games, give examples
We define games where avatars are not directly controlled by the player as the second category of multi-player games. With this game type, a player does not direct an avatar itself but defines goals that the avatar tries to reach on its own. E.g. a player can direct an avatar to go to certain destination, attack another player's avatar or do a certain action. The avatar then decides on its own how to achieve that goal. E.g. if a movement order was given the computer calculates the way the avatar takes in order to reach the destination. From the network's point of view, only the goal of an avatar has to be transported to the other players. All moves can then be computed locally because they all base on the same game logic. 
% Requirements

Indirectly controlled games can cope with much higher delay than direct controlled games. Usually, network requirements are less demanding compared to directly controlled games and the user does not notice delays of several hundred milliseconds. 
\TODO{jitter, packet loss, protocol(TCP/UDP)}
Examples of indirectly controlled games are real-time strategy games such as the Warcraft or Command and Conquer series or role playing games like Diablo.

However, there are cases where some players do notice higher delays. These player micromange their avatars by giving only short term goals e.g. influencing the exact way on which the avatar moves to its destination. This is usually done because the player think that he knows a better way of doing things than the game logic. In cases where the latency between the players is high, the player's perception of the responsiveness of the game is low during micromanagement of his avatars. 
%Related work
Nevertheless, \REFMISSING shows that players can adapt to these situations by giving up micromanagement and defining more long-term goals for their avatars. Although players may be unfamiliar with this playing style, the game remains playable and enjoyable. Furthermore, \REFMISSING (THE SAME) shows that changing the game style has little or no effect on the game score.

%In the literature, one can find fewer papers on indirectly controlled games than 
 In \cite{Dick05}, we have looked at Warcraft 3 and found that the skill of the player was the most important factor of the game outcome and that latency and jitter played a negligible role. Sheldon et. al.\cite{Sheldon03} also looked into Warcraft 3 (The effect of latency on user performance in Warcraft3)


% Conclusion for indirectly controlled avatars
We conclude that games with indirectly controlled avatars have less demands on the network as games from the previous type. This is mainly due to the fact that avatars move and behave on their own which allows for an increased delay.
\TODO{We are mainly talking about delay here. I think this is also true for the previous section. Check that the introduction discusses bandwidth, delay, jitter, packet loss and so on. It should probably made clear there that delay and packet loss is the same (in our case)}




\subsubsection{Round-based games}

% Describe games, give examples
Round-based games are a classical game style which is well known from card and board games. Here, players make moves in a round-robin fashion. Usually, each player is allowed only a certain number of actions per round. In round-based games the move of a single player may be also limited by time either per round or as a sum for the duration of a single game. Examples for round-based games are chess or poker. For computer games, Civilization is a popular representative of this category.

% Requirements

Round-based games have very little requirements on the network because they often do not impose time limits on the duration of a move by a player or that time constraint is in the order of several minutes or more and therefore several orders of magnitudes higher than the delay usually found in computer networks. E.g. games like chess are also played by mail where moves can take up to several weeks or more.


%Related work
% Conclusion for round-based games
Round-based games can be differentiated from the previous two cateogories in that it does not allow a  seamless and continuous experience of the game by the player. The game is interrupted after each round. Because game data does not need to be sent in real-time\TODO{define real time in the introduction of this chapter}, deficiencies or errors in the network can easily be faced with retransmissions of game data on the transport layer. Round-based games usually choose TCP as transport protocol.


\subsubsection{Hybrid games}

The fourth and last category of multi-player games are hybrid games. This game type combines ideas and elements from the previous three categories. One example for hybrid games is Earth \& Beyond, a massively multi-player role playing online games (MMORPG). Here, players directly control their space ship when moving through the game world space. 
You will see other players passing by or flying next to you giving you the feeling of a real-time game. However, as long as you don't interact with these players, you cannot be sure whether a response to your action comes instantaneously or if it comes with a high delay. However, because you have direct control over your ship and a fast response from the static environment around you (which is computed locally), this gives you a great illusion of a real-time environment. During interactions between players, e.g. fights, such games often resort to a round-based mechanism to ensure a fair game between the player even if one player is impaired with a high latency connection.

Hybrid games use TCP as well as UDP as transport protocol. 
\TODO{Find out if there are other MMORPGs which are hybrid games}



Because of the variety of different games and game types, it is not easy to put each and every game into a single of these categories. An example are ...... MMORPGs like A and B usually round-based games\refm.


\myglossar{MMOPG}{Massively Multi-player Online Playing Games}
\myglossar{MMORPG}{Massively Multi-player Online Role-Playing Games}
\myglossar{NPC}{Non-player character, a computer-controlled participant of the game}

\begin{table}
\begin{center}

\setlength\doublerulesep{.5pt}\doublerulesepcolor{white} 
\setlength\arrayrulewidth{2pt}\arrayrulecolor{white} 

\begin{tabular}{>{\columncolor[gray]{.70}[.80\tabcolsep]}l
>{\columncolor[gray]{.85}[.80\tabcolsep]}c
%@{\extracolsep{\fill}}
>{\columncolor[gray]{.70}[.80\tabcolsep]}c
%@{\extracolsep{\fill}}
>{\columncolor[gray]{.85}[.80\tabcolsep]}c
%@{\extracolsep{\fill}}
>{\columncolor[gray]{.70}[.80\tabcolsep]}c}
%\hline

			   & \multicolumn{4}{>{\columncolor[gray]{.85}[.80\tabcolsep]}c}{Typical Requirements} \\ \hline
{\bf Game type } & {\bf Bandwidth} & {\bf Delay} & {\bf Jitter} & {\bf Packet loss}  \\ \hline \hline
%\arrayrulecolor{white} 
directly controlled     & low & high & high\,/\,medium & medium \\ \hline 
indirectly controlled  & low & medium & medium\,/\,low & medium \\ \hline 
round-based            & low & low\,/\,no req. & no req. & N/A \\ \hline
\end{tabular}
\end{center}
\caption{Network requirements of multi-player games during the game}
\end{table}

\TODO{CONCLUSION NETWORK PARAMETERS FOR GAMES}

% A game can be specified by
%  - number of concurrent users in a single game
%  - time between game state updates on the server


% #############################################################
%  MOBILE GAMING - STATE OF THE ART
% #############################################################

\subsection{Mobile gaming: State of the art}

%\subsubsection{Mobile game consoles}
% Mobile games 
Besides its commercial importance, the video game market is also becoming
more and more focused on mobile devices. According to the BIU and the GfK
(Gesellschaft f\"ur Konsumforschung AG), the market share for handhelds
went up from 8\% in 2004 to 19\% in 2006.  In this emerging market,
mobile devices now for the first time have sufficient capabilities and
resources to allow playing multi-player games in mobile wireless networks.

% Commercial success

From a commercial point of view, computer and video games is a huge market.
In Germany and according to the federal association of interactive
entertainment software (BIU, Bundesverband Interaktive
Unterhaltungssoftware e.V.), the total turnover in 2006 for computer and
video games was 1.13~billion Euros.  Compared to 2005, this market
increased significantly by 7.4 percent.  This growth was particularly
carried by video game sales which increased by 13 percent.  In the United
States, computer and video game software sales grew six percent to \$9.5 billion in 2007.
According to the entertainment software association (ESA), 69\% of heads of 
US households play computer or video games\cite{esa-facts-2006}. 

We believe that with stationary computer and video consoles still widely in
use, mobile games are in a tough spot. Players will expect the similar
quality and performance from these new mobile games as they are used to
from their stationary devices. To achieve a satisfactory game experience, \TODO

% Computers are more and more mobile.

Recently and regarding private owners in many countries, more laptops have been sold than desktop personal computers. In the third quarter of 2007 and for the first time ever, mobile computers have outsold stationary devices in the region of Europe, the Middle East and Africa. This includes private sells as well as devices sold for business purposes. The market research company IDC states that 11.2 million laptops and 10.7 million desktop PCs were sold in the third quarter of 2007. Compared to the previous quarter, desktop PCs sales increased by 2.5 percent while laptops sales went up 48 percent during the same time. \REFMISSING -- c't 24/2007 S.24


Another factor, of course, is the proliferation of wireless data networks
like WLAN or GPRS/UMTS during the last ten years. As of 2007, examples of
mobile game consoles are Sony's Playstation Portable (PSP) or the Nintendo
DualScreen (NDS) both of which can be seen in Figure~\ref{figure-psp-nds}.

\begin{figure}
\includegraphics[width=.5\textwidth]{pics/psp.jpg} % Picture from Wikipedia (DE)
\hfill
\includegraphics[width=.4\textwidth]{pics/nintendo-ds.jpg} % Picture from Wikipedia (DE)
\caption{Mobile video consoles: Sony Playstation Portable and the Nintendo DS}
\label{figure-psp-nds}
\end{figure}
\TODO{Copyright kl\"aren, neues NDS Bild}

% Sony's PSP
Sony's PSP allows the user to play with other PSP users via it's IEEE
802.11b-based WLAN adapter. It can be used to connect to a WLAN access
point so that multi-player games can be played through the Internet. It
also allows the creation of an ad-hoc wireless network in which 2--16
players can compete against each other without the need for any additional
network infrastructure. Some titles for the PSP offer a so called
``gamesharing'' mode which allows multi-player sessions between two or more
players with only one copy of the game. In this mode, the game owner's PSP
transmitts the game code wirelessly to the other PSPs where it is loaded
into RAM. Gameshare versions often support only a reduced feature set of
the original game. One reason for this is to limit the transfer time of the
game code to the other playstations which is done wirelessly at a maximum
rate of 11\,MBit/s.

% Gamesharing came later? Claypool mentions that Nintendo DS has it but not the PSP!

% Nintendo DS

The Nintendo DS employs a subset of IEEE 802.11b for wireless
communication. It supports only data frames with short preambles and
communicates at speeds of 1 and 2\,MBit/s, possibly with a lower than
normal signal strength to save power\cite{claypool05}.  Another reason
for that behaviour could be that the Nintendo DS broadcasts its frames
so that only  the basic rates of IEEE 802.11b\cite{IEEE-802.11b} can
be used. The Nintendo DS supports up to 16 concurrent players which
can communicate through an ad-hoc network or WLAN access points. As
for the PSP, the Nintendo DS allows networked play with only one copy
of the game in the network, called ``DS Download Play''. However not
all NDS games support DS Download Play and require that all players
have their own copy of the game inserted into their consoles. Again,
some games support only a reduced set of functionality when used in DS
Download Play mode. Additionally, DS Download Stations give game
stores the opportunity to provide free demo of new games to potential
customers. Technically, download stations work in the same way as DS
Download Play -- DS Download Stations simply contain a couple of
Nintendo DS devices with special software cartridges. Currently, there
is no freely available information on the technical details of DS
Download Play. More on WLAN and game traffic analyses with respect to
the Sony PSP and the Nintendo DS can be found in \cite{claypool05}.

In addtion to player multi-player games, both mobile game consoles also
allow to play a single-player game with or against the computer. 

Other trends, like the Nintendo's WII video console follow a different
approach. With this control the player holds a controler in his hand while
an infrared camera in the controller detects it's position in 3D space.
Additionally, an accelerometer  gives additional sensor feedback.
Information from the controller is transmitted back to the game console
wirelessly via Bluetooth. The game console itself is stationary and usually
connected to a TV set. However, the WII shows the latest example of gaming
devices with integrated sensors which allow for the inclusion of real-world
information into a game. Sensors such as localization/positioning,
acceleration and tilt as well as other data from the environment of a
player can complement a game with enhanced reality and immersion. Hence, we
see the addition of environmental or personal sensors as an important step
in the evolution of computer games in general. Together with the newly
achieved freedom of mobility, this development could lead to new game types
where players can freely move around and where interaction with the real
world is an essential part of the game itself.

% TODO: Neuartige Spiele (Singapore) - Allerdings auch neue Spielformen! K�nnte daher problematisch werden

%\subsection{Other kinds of applications}
%Beside games, there are other kinds of applications which 


%\subsection{Application phases}
%\subsubsection{Setup}
%\subsubsection{Running}
%\subsubsection{Aftermath}

\section{Scenarios}

%--- Introduction
Generally, scenarios define the neighbourhood and the environment of an application. They can provide 
 not only the condition of the network but also the number of network users, (background) traffic, mobility and many other parameters. We believe that comprehensive scenarios are essential for an realistic evaluation of applications or single algorithms. As an example, it is a fair assumption that rather few people will play multi-player games during business meetings or a lecture class but the majority will enjoy them in their spare time. Also, when at home, it makes more fun to play a sophisticated game on a desktop computer or game console which is attached to a big screen rather than on tiny mobile devices. Therefore, on the following pages, we will introduce three different scenarios which we believe are a plausible plots for mobile multi-player gaming. The initial idea for all scenarios is that the player must have the opportunity as well as the ability in a particular situation to play a game. \TODO{A sentence which describes the meaning of these external and internal requirements would be helpful}

%In order to create a realistic scenario for mobile games, a player should have 
%\begin{itemize}
%\item[a)] the opportunity and
%%to play a game (e.g. the player has some spare time)
%\item[b)] the ability to play a game.
%% (e.g. the player is able to pay the necessary attention to the game)
%\item[c)] 
%% the player should not be able to use another game device (computer, infrastructure)
%\end{itemize}


% Scenario 1: School yard
In our first scenario, we narrow down our focus group to pupils or students because we believe that in the beginning new game ideas and devices will be mainly successful with young people. Therefore, we propose a school yard to be our first scenario. Between classes, pupils or students come together on the school yard to talk or play games. We believe that among other activities during breaks, computer games will become a factor in this scenario if they are not already.

% Scenarios 2 & 3: Train station, Train
In our next two scenarios we focus on the main advantage of mobile gaming which is that you can play them wherever you are. This is especially interesting when you are on the move because you often don't have any network infrastructure to rely on. Hence, we have chosen a train station and a train ride as scenarios for mobile gaming. In both scenarios the player has the opportunity to play a game because he waits for his train to arrive or to reach its destination. On the other hand, when traveling on the train the player has the ability to play the game because he is able to pay the necessary attention to the game. 

In all scenarios, players usually don't have access to any PC or game consoles that are not mobile. Also, while the occasional access to the Internet may exist in these scenarios through WLAN access points or mobile networks, availability may be intermittent and access is often not free of charge.



%You need:
%* Able to pay the necessary attention to the game (ability)
%* Have free time available. (opportunity)

\TODO{I believe we have not introduced multi-hop before. I suggest we keep the scenarios on games and introduce multi-hop later. (Although some info about multi-hop would help here, we can make good arguments without the need to mention it here.}


While our scenarios do not imply a claim of completeness, we use indoor and outdoor scenarios which exhibit many different characteristics. While we focus on multi-player games for our scenarios, the basic principle is true for other applications as well.

%--- Definition of a scenario
We define a scenario as the combination of a location together with
the environmental factors and contexts that come with it. We will scatter our 
mobile devices and users across the scenario to measure the behaviour of our game application algorithms.
From a scenario, we can deduce a variety of parameters, first and foremost, the size and shape
of the area. Other parameters include the number of people
inside and outside the area of interest, their likely movement pattern
and speeds as well as the presence and kind of background traffic.
However, there are limits to what can be concluded from our scenarios. First and foremost, the penetration of mobile devices and the percentage of devices which are switched on cannot be gathered from our scenarios.
As such, these parameters have to be estimated.


Scenarios give us an idea what behaviour the user will experience from
his application. In this section, we present three different
scenarios for multi-player gaming in mobile ad-hoc networks. 
\TODO{more}
As scenarios are dependant on a specific application, they are
introduced here and used for the evaluation of our approach later on
in chapter~\ref{chapter-evaluation}.

%--- For Chapter 'Evaluation' / Definition of background traffic

Background traffic can be divided into three different classes. First,
mobile devices communicating with each other in the ad-hoc network.
They could either use a different application or another instance of
the same application, e.g. play the same multi-player game on another
map.


%Why we expect rather small scenarios?
%
%* Why do we need scenarios?
%* Define what a scenario is:
%  - Area and boundary
%  - Number of nodes
%    * Playing the applications
%    * Using the MANET (idle or busy using another application)
%       - Traffic is forward through the ad-hoc network (multihop)
%    * Other wireless nodes on the same channel (not participating in the ad-hoc network)
%       - Traffic is usually not forward through the ad-hoc network. (assume AP nodes, rather stationary)
%  - Direction and speed of nodes (includes movement restrictions)
%  - Traffic
%    * Number, Size, Frequency of packets (CBR) or protocol (in case of traffic like TCP with congestion and flow control mechanisms)
%    * Source and Destination of traffic
%    * Time of start and duration of traffic
%    
% - Traffic models
%    * Game traffic models
%    * Background traffic models
%       - For the moment we could take another game session and Internet-like traffic (Web traffic, HTTP), find related work for 'what is Internet-like traffic', 'what is traffic in WLAN networks', and 'what does web traffic really looks like?'
% - Mobilty models
  
\subsection{Scenario 1: Schoolyard}

% Why are schoolyards interesting for multi-player games - Done before
% How does this scenario look like (area, size, shape)
% Number of people, number of mobile devices, background traffic
% Mobility, distribution of people, scenarios

% Schulbaurichtlinien Niedersachsen
																	
For this scenario, we take a look at a medium-sized german grammar school with 600~pupils with an outdoor school yard of 2,000\,$\rm m^3$. As not all german states regulate the size of school yards, we take an example from the state of Bavaria which states in paragraph 2(2)  of its school building ordinance (Bayrische Schulbauverordnung)\cite{bayrische-schulbauverordnung}  that an outdoor area with a minimum of 3\,$\rm m^2$ per pupil should be provided. With that information and according to our knowledge the school yard has the appropriate size for a medium-sized grammar school. We assume a penetration of 5--10\,\% which results in 30 to 60 devices on the school yard. 

Without loss of generality, we define our school yard to be an outdoor rectangular area with a size of 200\,$\times$\,100\,$\rm m^2$.  Figure~\ref{schoolyard} shows an example of a german school yard. While all players could technically scatter across the school yard, we believe that they will rather stay close together to enjoy the company of their fellow players. In cases where the game allows one or more teams to compete against each other, we expect a grouping of players either close to their respective team members or as whole group. Also, we believe that movement in this scenario will be very low when traditional multi-player games are played. However, in the future when location-based games or other games that exploit the fact that the user is able to move during the game are becoming popular, we will see movement of players. But for this work, we consider these new game types out of scope and will simulate this scenario without any movement. For this scenario, we will also assume that there is no significant background traffic which in general makes the school yard scenario a best-case scenario for mobile gaming.



%define a school yard as an open outdoor rectangular area  of approximately 2,000\,$\rm m^3$.

%600

%Bayrische Schulbauverordnung  (SchulbauV)
%Vom 30. Dezember 1994 (GVBl 1995 S. 61, KWMBl I 1995 S. 74), zuletzt ge�ndert durch Verordnung vom 27. November 2003 (GVBl S. 896)
%� 2(2)
%(2) F�r den Pausenhof sollen mindestens 3 qm je Sch�ler vorgesehen werden.




% For the school yard scenario, we assume a larger rectangular area of
% 150\,$\times$\,250\,$\rm m^2$ and define it as an open outdoor space. The
% main difference between the previously mentioned scenarios is the lack
% of supporting nodes and the grouping of players. For this scenario, we
% assume that students who turned on their mobile nodes are playing
% games. So there are no additional supporting nodes. Secondly, we think
% that students will stand or sit in groups together rather than playing
% from different positions distributed across the school yard. We define
% these groups as clusters of players or mobile nodes. On a school yard,
% several player clusters can evolve for two different reasons:
% Different clusters of players can play different games or clusters are
% formed up of members of the same team which compete against other
% teams in the same game. With players remaining stationary and no 
% supporting nodes, this scenario is static. However, students can
% decide to switch on their mobile devices and join the game or players
% may decide to leave the game.


\begin{figure}
\begin{center}
\includegraphics[scale=0.52]{pics/Elisabethschule-Schulhof.jpg}
\end{center}
\caption{A school yard}
\label{schoolyard}
\end{figure}

%\subsection{Bus}
%
%Mercedes-Benz Citaro
%% http://www.mercedes-benz.de/content/germany/mpc/mpc_germany_website/de/home_mpc/buses/home/products/new_buses/%new_Citaro_12/technical_data.html
%
%Pl�aetze (Fahrer/Sitzpl�tze/Stehpl�tze) 2-T�uerer: 1/32/74 - 106 gesamt
%Pl�aetze (Fahrer/Sitzpl�tze/Stehpl�tze) 3-T�uerer: 1/28/77 - 105 gesamt


\subsection{Scenario 2: Train station}

For the second scenario we take a look at a train station where people can walk around from and to the train platforms or wait for their train to arrive. Similar to the first scenario we assume that players do not move during the game and a penetration ratio of mobile devices of 5--10\%. In addition to the school yard, there are other people participating in the wireless network. This could be people using different applications which again communicate directly over the wireless network or talking to computers in the Internet through existing infrastructure at the station. This could be business people sharing an important company document with each other or another visitor just surfing on the Internet. From the point of view of the game, data from these applications is considered background traffic which competes with our game traffic for the use of the wireless channel. Also, in contrast to our players, background nodes are able to freely move around at the train station. This comes from the fact that mobile devices can communicate without any user interaction, e.g. syncing email, which leaves the possibility for the owner to move around. 


\TODO{Bild vom Braunschweiger Bahnhof / Bauplan?}





%This scenario involves a medium-sized area, e.g. $100\times 250\,m^2$. People in train stations usually walk 
%around, wait in designated waiting areas, or wait on a platform. The group of players only comes from the 
%group of waiting people while supporting nodes may also be carried by people roaming around. This scenario 
%contains a number of attractors such as the rail service center, the shops, the entries and exists, and the plattforms.
%When moving around, people usually travel on foot, hence we assume a maximum speed of $2\myunitfrac{m}{s}$. 
%Meanwhile, other mobile nodes in trains that pass through the train station can have speeds up to $25\myunitfrac{m}{s}$
%Players as well as other people carrying supporting nodes walk in the hallways or on the plattforms.

\begin{figure}
\begin{center}
\includegraphics[scale=0.15]{pics/DeutscheBahn_gobeirne.jpg}
\end{center}
\caption{An InterCityExpress at a train station}
\label{trainstation}
\end{figure}


When discussing wireless communication at train stations, some particular problems have to be taken into account.
Besides the usual obstacles for wireless communication such as walls or other people, a commercial 
wireless infrastructure may exist at train stations (e.g. one or more WLAN access points that can be used to access 
the Internet). Any communication with this infrastructure interferes with game transmissions if both utilize the same frequency.
Wireless communication between platforms is impaired if a train blocks the line of sight between two devices. 
Additionally, electromagnetic noise from the overhead line and other electric equipment also has a negative effect on wireless communication.

Generally, people do not stay very long at train stations. They either get on or off the train. 
Therefore, we expect the game time for one player usually to last no longer than 15~minutes. 
However, train delays could increase that number.

\subsection{Scenario 3: Train ride}
% ICE 3
% 2 Endwagen, 6 Mittelwagen
% L<8A>�nge / Breite / H<9A>�he Endwagen:               25.835 / 2.950 / 3.890 mm
% L�<8A>nge / Breite / H<9A>�he Mittelwagen:    24.775 / 2.950 / 3.890 mm
% Quelle: http://www.hochgeschwindigkeitszuege.com/germany/index_ice_3.htm
%\cite{ICE3}


For the train scenario, we use a common long-range InterCity train like the ICE 3 built by Adtranz/Bombardier. This train often uses eight coaches which have altogether cover $3\,\times\,175\,m^2$ and have a capacity of 431 seats total. Assuming that two thirds of these seats are occpuied, which is a reasonable assumption for popular connections, our ICE 3 has 287 people on board.

In this scenario, two different situations should be distinguished. First of all, during the train ride, people usually sit at their 
seats and do not move often. The second situation is a stop at a train station when people get 
on or off the train and in the following minutes while they make their way through the coaches. 
So again, players are not expected to move during their game and the mobility of supporting nodes 
is also low as long as the train is on the move. Again, people travel on foot, so we assume a maximum 
speed of \mps{2}. Generally, we conclude as far as node mobility is concerned the train 
scenario is of rather static nature.

\begin{figure}
\begin{center}
\includegraphics[scale=0.70]{pics/ICE2_Erste_Klasse.jpg}
\end{center}
\caption{The inside of an InterCityExpress}
\label{train}
\end{figure}

The area in this scenario is quite long but not very wide which means from a communication point of 
view that data always has to travel along the axis of the train. There is usually no alternate route available 
so that  e.g. game traffic may have to be routed through congested areas in order to reach the players. 
Another problem for wireless networking is that carbodies are made of metal mostly aluminium or steel. 
This leads to attenuation of the wireless signals to stations in other coaches. To communicate between 
nodes at both ends of the train could require up to 10 hops. Again, commercial access 
points may be present in trains which may lead to an increased usage of ISM-band frequencies. Finally, 
other nodes outside the train may pass by at relative speeds of up to \mps{100}.

A train ride usually lasts longer than ten minutes with exceptions for local trains or subways. In trains, 
games could also last several hours with some users playing the whole time while other leave or join 
late in the game as the get on or off the train. Here, we 

\subsection{Other scenarios}
Mixed reality

\subsection{Summary}

\begin{table}\begin{center}\begin{tabular}{|l|r|r|r|r|}
\cline{2-5}
\multicolumn{1}{c|}{}& 
	\multicolumn{1}{c}{School yard} & 
	\multicolumn{1}{c}{Train Station} & 
	\multicolumn{1}{c}{Train} \\ \cline{2-5} \hline
Size of area ($w\times l$) &
	${\rm 200\times100\,m^2}$&
	${\rm 150\times 350\,m^2}$ &
	${\rm 3\times175\,m^2}$& \\[0.25em] \hline
People (total) & 600 & 100 & 287 \\[0.25em]
Penetration ratio &\multicolumn{3}{c}{5\,--\,10\,\%}& \\[0.25em]
%Nodes (total) & 30\,--\,60 & 50\,--\,100 &  \\ 
Nodes running\\
\hspace{1em}game application & 30\,--\,60 & 5 & 7\,--\,14 &\\ 
% \hspace{1em}Supporting & & 5 & \\ 
\hspace{1em}other apps (background)& -- & 10 & 7\,--\,14\\[0.25em]
% \hspace{1em}Outside &&&?& \\ 
\hline
Mobility &&&& \\ 
\hspace{1em}Model & \multicolumn{1}{c}{no} &RWP&\\ 
\hspace{1em}Internal speed & \multicolumn{1}{c}{mobility} &${\rm \le4\,m/s}$&\\ 
\hspace{1em}External speed & &${\rm \le4\,m/s}$&\\[0.25em] \hline
Time & 15\,min. & 15\,min. & 60\,min.\\ \hline
\end{tabular}
\end{center}
\caption{Parameters from the scenarios}
\label{table-scenario-parameters}
\end{table}

\section{Evaluation criterias}
Evaluation criterias for latency-sensitive applications (in general).

* Describe what applications expect from a network (in the next section we describe what a standard MANET can deliver)

\section{Summary}

