Analisi a livello pacchetto del traffico di Multiplayer Network GamesFacoltà di IngegneriaCorso di Studi in Ingegneria Informatica

tesi di laureatesi di laurea

relatorerelatore

Ch.mo prof. Antonio Pescapè

correlatorecorrelatore

Ing. Alberto Dainotti

candidatocandidato

Pietro Marchetta

Matr. 534/1475

AnalisiAnalisi a a livellolivello pacchettopacchetto del del trafficotraffico didi

Multiplayer Network GamesMultiplayer Network GamesAnnoAnno AccademicoAccademico 2006/20072006/2007

Analisi a livello pacchetto del traffico di Multiplayer Network GamesFacoltà di IngegneriaCorso di Studi in Ingegneria Informatica

MultiplayerMultiplayer Network Network GamesGames::

� Nel 2000, il 3% del traffico Internet era generato da giochi in rete.

� Alcuni studi prevedono che nel 2008 questa percentuale aumenterà fino al 25%.

� Le infrastrutture di rete, progettate per smaltire il canonico traffico Web e Peer-to-Peer, non riescono a

supportare efficacemente tali applicazioni.

� Il forte interesse economico sorto intorno a questo nuovo bacino di potenziali utenti-giocatori ha spinto i

maggiori telecom operator a investire nell’adeguamento delle reti.

Studiare il traffico generato da Counter-Strike, un network game largamente diffuso e, dunque,

particolarmente rappresentativo:

� Effettuare una caratterizzazione statistica del traffico generato dai client del gioco in termini di

Packet Size e Inter-Departure-Time (analisi a livello pacchetto).

� Ottenere dei modelli statistici approssimanti.

Contesto & ContributoContesto & Contributo

Obiettivo:Obiettivo:

Analisi a livello pacchetto del traffico di Multiplayer Network GamesFacoltà di IngegneriaCorso di Studi in Ingegneria Informatica

BackgroundBackground

I I MultiplayerMultiplayer Network Network GamesGames tipicamente:

� Generano pacchetti piccoli (meno di 100byte) per esigenze legate a una bassa latenza

� Generano pacchetti a intervalli regolari (in virtù della tipica logica del gioco)

� Utilizzano il protocollo UDP (basso overhead, interattività)

CounterCounter--StrikeStrike::

� E’ lo sparatutto più diffuso in assoluto (32000 server attivi e più di 100000 giocatori in tutto il mondo).

� E’ stato trattato in letteratura da ricercatori quali Feng, Färber, Claypool, anche se da punti di vista

diversi.

� In alcuni articoli si sostiene che il comportamento dell’applicazione è caratteristico per tutto il genere

degli sparatutto.

RelatedRelated worksworks::

� W. Feng, F. Chang, W. Feng, and J. Walpole. Provisioning on-line games: a traffic analysis of a busy

Counter-Strike server. In Proceedings of SIGCOMM Internet Measurement Workshop, November 2002.

� M. Claypool, D. LaPoint, , and J. Winslow. Network Analysis of Counter-strike and Starcraft. In

Proceedings of the 22nd (IPCCC), April 2003.

� J. Färber. Network game traffic modelling. In NetGames ’02: Proceedings of the 1st Workshop on

Network and system support for games, May 2002.

Analisi a livello pacchetto del traffico di Multiplayer Network GamesFacoltà di IngegneriaCorso di Studi in Ingegneria Informatica

TestbedTestbed EsperimentiEsperimenti

Parametri modellati statisticamente:Parametri modellati statisticamente:

� Inter-Departure-Time (IDT o IPT): l’intervallo di tempo che

impiega la sorgente di traffico a generare due pacchetti

consecutivi.

� Packet-Size (PS): la dimensione dei pacchetti considerando

esclusivamente il carico utile (payload) dell’applicazione

Gli scenari analizzati:Gli scenari analizzati:

1. LAN party wired a 4 e 8 giocatori

2. LAN party wireless a 4 giocatori

3. Banda larga ADSL a 4 giocatori

Nello scenario ADSL sono state collezionate anche le

tracce in ingresso al server per poter apprezzare gli

effetti che ha la rete sul traffico.

Esperimenti effettuati presso il laboratorio ARCLAB del Dipartimento di Informatica e Sistemistica (D.I.S.), facoltà di Ingegneria.

((11))

((33))

((22))

Analisi a livello pacchetto del traffico di Multiplayer Network GamesFacoltà di IngegneriaCorso di Studi in Ingegneria Informatica

StrumentiStrumenti

Analisi statistica:Analisi statistica:

� Calcolo di dati sintetici: media, varianza, …

� Diagrammi: PDF, CDF, Sequence plots, Byterate, Packetrate, Fitting, ...

� Fitting: approssimazione della distribuzione empirica con un modello analitico che ne

ricalchi l’andamento.

� Expectation Maximization [1]

� Lambda square λ2[2]

[1] J.A. Bilmes, “A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian

Mixture and Hidden Markov Models”.

[2] S. Pederson, M. Johnson, “Estimating Model Discrepancy”. Technometrics, 32(3), pp. 305-314, Aug. 1990.

Sviluppati i seguenti script in linguaggio Sviluppati i seguenti script in linguaggio matlabmatlab: : � TLSRND - generatore di numeri casuali secondo la distribuzione Student’s T location-scale.

� GAMMAMIX2 - script per il fitting di dati che si basa su un mix di due distribuzioni Gamma.

Software:Software:� Tcpdump per raccogliere le tracce di traffico.

� Plab per estrarre dalle tracce di traffico le occorrenze di IPT e PS.

� Matlab per la caratterizzazione e la modellazione.

Analisi a livello pacchetto del traffico di Multiplayer Network GamesFacoltà di IngegneriaCorso di Studi in Ingegneria Informatica

Analisi Sperimentale (1/2)Analisi Sperimentale (1/2)

� Durante la connessione al server il client

manifesta un comportamento diverso:

Fase inattiva: il giocatore è

semplicemente collegato al server.

Fase attiva: il giocatore partecipa

attivamente alla sessione di gioco.

� Le variazioni del bitrate in funzione della

fase dipendono dal PS non dall’IPT.

� Il PS in fase inattiva è fortemente

prevedibile, con un valore dominante

(27byte).

� Possibile dipendenza

dall’identificativo del giocatore.

� Generati pacchetti di dimensioni

maggiori nel passaggio da una fase

all'altra.

Client IPT byte rate: Alessandro

Clients PS PDF – Fase Inattiva

Client IPT packet rate: Alessandro

Client PS Sequence: Alessandro

Analisi a livello pacchetto del traffico di Multiplayer Network GamesFacoltà di IngegneriaCorso di Studi in Ingegneria Informatica

Analisi Sperimentale (2/2)Analisi Sperimentale (2/2)

InvarianzaInvarianza:: i giocatori manifestano comportamenti simili in

termini di PS e IPT anche in scenari diversi (wired a 4 e 8

giocatori, wireless, ADSL).

�� PacketPacket--SizeSize:: I pacchetti non assumono mai

dimensione superiore ai 60byte, in accordo a quanto

sostenuto da Feng, smentendo invece i valori riportati

da Färber . In dettaglio: il PS assume un insieme di

valori compresi tra i 25 e 60byte.

�� InterInter--PacketPacket--TimeTime:: Confermati gli studi di Färber

sull'IPT che in media, in ogni scenario e fase di gioco,

risulta pari a 41.7ms.

� Nello scenario ADSL la rete ha un’influenza maggiore

sul traffico generato. Pertanto, l’analisi è risultata più

impegnativa.

Traffico sostanzialmente diverso da Starcraft che

appartiene a un’altra categoria di giochi in rete (RTS).

Clients PS PDF – Fase Attiva (wired4)

Clients IPT PDF – Fase Attiva (wired4)

Analisi a livello pacchetto del traffico di Multiplayer Network GamesFacoltà di IngegneriaCorso di Studi in Ingegneria Informatica

Scenari ADSLScenari ADSL

Ricreate 2 sessioni di gioco:

� 1°Sessione: Raccolte tracce in uscita ai client e in ingresso

al server.

� 2°Sessione: Raccolta la sola traccia lato server.

Riscontrata forte anomalia nel comportamento di un singolo

giocatore in termini di IPT:

� Necessario un approfondimento.

Osservare la stessa sessione di gioco sia dal punto di vista del

client ( ) che del server( ) ci permette di apprezzare gli effetti

che ha sul traffico la rete, principale indiziata per l’anomalia

riscontrata:

� Il client genera traffico in funzione dei tempi e del tipo

di informazioni che riceve dal server ma è la rete in

questo senso a ricoprire un ruolo fondamentale.

� Tuttavia la rete influisce, come era prevedibile,

esclusivamente in termini di IPT e non di PS che

assume il consueto andamento.

Clients Upstream IPT PDF

Clients Downstream IPT PDF

Server Upstream IPT PDF

Analisi a livello pacchetto del traffico di Multiplayer Network GamesFacoltà di IngegneriaCorso di Studi in Ingegneria Informatica

ParamParam.. WiredWired

4PL4PL

WiredWired

8PL8PL

WirelessWireless ADSL ADSL

11°°SesSes

(C)(C)

ADSL ADSL

11°°SesSes

(S)(S)

ADSL ADSL

22°°SesSes

(S)(S)

NormalNormal 11

mumu 34.8334.83 33.4933.49 35.6335.63 34.7834.78 34.7834.78 34.234.2

sigmasigma 4.394.39 1.571.57 4.234.23 3.683.68 3.223.22 3.223.22

peso peso 0.370.37 0.20.2 0.340.34 0.350.35 0.320.32 0.30.3

NormalNormal 22

mumu 49.4949.49 48.0548.05 49.6249.62 49.7349.73 49.8349.83 49.7449.74

SigmaSigma 3.613.61 4.54.5 3.433.43 3.843.84 3.773.77 3.443.44

peso peso 0.630.63 0.80.8 0.650.65 0.650.65 0.680.68 0.690.69

λλ22 0.080.08 0.240.24 0.10.1 0.090.09 0.240.24 0.220.22

ScenarioScenario mumu sigmasigma nunu λλ 22

WiredWired 4PL4PL 4169941699 104.82104.82 0.7040.704 0.180.18

WiredWired 8PL8PL 4167941679 51.8551.85 0.820.82 0.070.07

WirelessWireless 4171141711 147.196147.196 0.90.9 0.090.09

AdslAdsl 11°°S.(C)S.(C) 4168241682 71.3671.36 0.680.68 0.30.3

AdslAdsl 11°°S.(S)S.(S) 4043340433 1534.61534.6 0.90.9 0.530.53

AdslAdsl 22°°S.(S)S.(S) 4070440704 1859.61859.6 1.211.21 0.450.45

Tabella 1: Packet Size – Fase Attiva – byte

FittingFitting StatisticoStatistico

PS: Fitting con Mix di 2 distrib. Gaussiane

IPT: Fitting con distrib Student’s T location-scale

Tabella 2: Inter-Deparute-Time – Fase Attiva – Student’s T location scale - us

PS – PDF A CONFRONTO – FASE ATTIVA

IPT – PDF A CONFRONTO – FASE ATTIVA

Analisi a livello pacchetto del traffico di Multiplayer Network GamesFacoltà di IngegneriaCorso di Studi in Ingegneria Informatica

ConclusioniConclusioni

Sono stati confermati alcuni risultati presenti in letteratura eSono stati confermati alcuni risultati presenti in letteratura e sono stati forniti sono stati forniti

ulteriori approfondimenti.ulteriori approfondimenti.� Il client di Counter-Strike genera un pacchetto di dimensioni non superiori ai 60bytes, in media,

ogni 41.7ms

� Differenziazione del traffico in termini di PS tra fase attiva e inattiva

� Invarianza nel comportamento del client in scenari diversi

� Caratterizzazione statistica del traffico generato dal client in ogni scenario di gioco e fase di

attività in termini di interpartenze (IPT) e dimensione (PS) dei pacchetti.

� Analisi preliminare degli effetti della rete sulle statistiche di livello pacchetto.

Modellazione delle distribuzioni mediante Modellazione delle distribuzioni mediante fittingfitting statistico.statistico.� Le distribuzioni che hanno prodotto i risultati migliori si confermano in ogni scenario:

� IPT: Student’s T location-scale

� PS in fase attiva: mix di due Gaussiane

� PS in fase inattiva: una semplice distribuzione discreta

� I risultati del fitting statistico rappresentano una ulteriore conferma delle invarianze presenti nel

traffico generato dal client di Counter-Strike.

Analisi a livello pacchetto del traffico di Multiplayer Network GamesFacoltà di IngegneriaCorso di Studi in Ingegneria Informatica

Sviluppi FuturiSviluppi Futuri

�� Possibili impieghi:Possibili impieghi:I modelli ottenuti potranno essere impiegati in simulatori di rete e generatori di traffico sintetico al fine di effettuare studi realistici di analisi di performance e testare l’effettiva capacità delle infrastrutture di supportare queste particolari applicazioni.

�� Possibili approfondimenti:Possibili approfondimenti:� Studio delle dipendenze mutue tra PS e IPT e dipendenze temporali.

� Fase Inattiva di Counter-Strike.

� Effetti della rete su statistiche di livello pacchetto (es. nel caso ADSL).

�� Altri network Altri network gamesgames::� l’analisi e confronto del traffico generato da altri sparatutto.

� confronto con il traffico generato da videogiochi di altri generi.