ON REDUCING ENTITY STATE UPDATE PACKETS IN DISTRIBUTED
INTERACTIVE SIMULATIONS USING A HYBRID MODEL
Declan Delaney*, Tomás Wa d, Séamus McLoone
Na ional Uni e si y o I eland, Maynoo h, Co. Kilda e, I eland.
*[email p o ec ed]
ABSTRACT
A key componen in Dis ibu ed In e ac i e Simula ions
(DIS) is he numbe o da a packe s ansmi ed ac oss he
connec ed ne wo ks. To educe he numbe o packe s
ansmi ed, DIS applica ions employ clien -side
p edic i e con ac s. One widesp ead clien -side
p edic i e con ac echnique is dead eckoning. This
pape p oposes a hyb id p edic i e con ac echnique,
which chooses ei he he de e minis ic dead eckoning
model o a s a is ically based model. This esul s in a
mo e accu a e ep esen a ion o he en i y’s mo emen
and a consequen educ ion in he numbe o packe s ha
mus be communica ed o ack ha mo emen emo ely.
The pape desc ibes he hyb id echnique and p esen s
esul s ha illus a e he educ ion in packe
ansmissions. This hyb id echnique is compa ed o he
s anda d dead eckoning me hod.
KEY WORDS
Dis ibu ed In e ac i e Simula ions, Dead Reckoning,
Hyb id Models, La ency
1. INTRODUCTION
Dis ibu ed In e ac i e Simula ion (DIS) in ol es he
pa icipa ion o mul iple pa icipan s communica ing o e
a compu e ne wo k [1]. The objec i e o he DIS
applica ion is o p o ide a ealis ic in e ac i e expe ience
o he pa icipan s. A ypical example o such an
applica ion is a dis ibu ed compu e game [2]. Howe e ,
a numbe o echnical p oblems combine o make deli e y
o such an expe ience di icul [3,4,5]. One such p oblem
is la ency, which is he ime i akes o in o ma ion o
p opaga e ac oss he ne wo k o all pa icipan s. Ano he
closely ela ed issue is he p oblem o ne wo k bandwid h.
Wi hin a DIS we e e o hese p oblems as he
in o ma ion upda ing issue. Se e al me hods ha e been
de ised o educe he quan i y o da a ha needs o be
ansmi ed be ween pa icipan s [6,7,8]. The DIS
s anda d de ines a clien p edic i e con ac mechanism
called dead eckoning [9].
This pape p oposes a hyb id p edic i e con ac
echnique, which dynamically swi ches be ween a sho -
e m dead eckoning model and a longe - e m s a is ical
s a egy model. This esul s in a educ ion in he numbe
o packe s ha mus be communica ed o ack ha
mo emen emo ely compa ed o a pu e dead eckoning
con ac . The educ ion is dependen on he model e o
h eshold, as will be explained.
In sec ion wo o his pape we desc ibe he in o ma ion
upda ing issue as i applies o dis ibu ed in e ac i e
applica ions. Exis ing solu ions o his issue, including
dead eckoning, a e also ou lined. Sec ion h ee desc ibes
ou p oposed hyb id swi ching echnique. A es
en i onmen was de eloped o compa e he new
echnique wi h exis ing dead eckoning echniques. This
en i onmen is desc ibed in sec ion ou . Example esul s
a e p esen ed in sec ion i e o bo h he hyb id and dead
eckoning echniques. The pape ends wi h he
conclusions and sugges ions o u u e esea ch.
2. THE INFORMATION UPDATING ISSUE
Ne wo k la ency and bandwid h es ic ions can combine
o p o ide poo in e ac i e expe ience in a dis ibu ed
applica ion. I an en i y is any elemen ha can be
con olled hen i will ha e a s a e ha can change wi h
ime. To unde s and he mechanism in ol ed in
communica ing en i y s a e in o ma ion o all pa icipan s
in a dis ibu ed applica ion, we will conside he ypical
case shown in Figu e 1. He e we ha e a cen al se e S
main aining he de ini i e s a e o a DIS. I
communica es wi h wo clien s, C1 and C2, sepa a ed by
ne wo k links wi h la encies T1 and T2 espec i ely.
Figu e 1 depic s a map o he i ual en i onmen and he
posi ion o en i ies wi hin ha en i onmen . The s a e o
he DIS, which we will call
Η
, will be ep esen ed by a se
o x-y coo dina es o each en i y in he simula ion. Fo
he scena io below we would ha e H = {(x1, y1), (x2, y2)}.
The de ini i e s a e o he DIS is ha held by he se e ,
Hs. This s a e is upda ed egula ly using en i y s a e
packe s ansmi ed om he clien se , C={C1, C2},
acco ding o some unde lying p o ocol. We will assume
he imp ac ical case ha a new packe is ansmi ed om
a clien once pe ende ing ame.
In Figu e 1 we assume ha T1 >> T2 and ha T2 is
negligible compa ed o he eloci y o he en i ies. As a
Use 1
Use 2
Figu e 1: S a e o DIS a ins an = n. No e he di e ence in local pe cei ed en i onmen s a es.
esul we can say ha he s a e o he DIS as a as C2 is
conce ned, H2, is igh ly coupled ia a sho la ency link
o he se e such ha
(1)
s
HH ≈
2
C1 on he o he hand is connec ed ia a high la ency link
and he e o e H1 is ending o lag Hs.
We can say,
{
}
1
),(,),()( 22111 T n nn yxyx H −
= (2)
The main consequence o his is ha he use a C1 is
eac ing o an en i onmen s a e H ha is no ha o he
se e Hs. Bu e en s in he en i onmen a e de e mined
globally and dis ibu ed by he se e and i s no ion o he
en i onmen s a e Hs. This ends o lead o dis up ion o
he use in e ac i i y o clien C1, which we will desc ibe
as localized in e ac i i y dis o ion.
We now de ine a measu e o his dis o ion. A con enien
one may be
D =
()
∑ (3)
=
−
N
iis HH
1
2
whe e N is he numbe o clien s pa icipa ing in a DIS.
We can call his a global DIS dis o ion igu e.
Gi en he p oblems mani es in such a DIS how do we
sol e he p oblem such ha
(4)
sc HH →
In o he wo ds, how do we main ain a consis en DIS s a e
ac oss all clien s o a leas dynamically ack Hs as as as
possible o all pa icipan s wi h minimum dis o ion?
Exis ing solu ions a e p esen ed in he nex sec ion.
2.1 PREDICTIVE SOLUTIONS
The mos common solu ion o he in o ma ion upda ing
issue in ol es a clien side p edic ion con ac mechanism
called dead eckoning [9]: all pa icipa ing clien s ag ee
o main ain he same low o de local models o he
dynamics o all o he pa icipa ing en i ies. This is he
con ac . Each pa icipan also main ains a model o i s
own en i y dynamics, which i con inuously compa es o
i s ac ual dynamics. When hese di e by a p e-de ined
h eshold, upda e in o ma ion is b oadcas o all o he
pa icipan s. These hen upda e hei models o ha
en i y. Con e gence algo i hms a e necessa y o allow a
na u al ansi ion o occu be ween he modeled and ac ual
mo ion when upda e da a a i es [9,10].
Al e na i e me hods ha e also been explo ed, and hese
include:
• Rele ance Fil e ing echniques: These seek o educe
he in o ma ion being ansmi ed o e he ne wo k
by il e ing he da a based on c i e ia such as
geog aphical p oximi y o a e o change [8].
• Ne wo k ansmission p o ocol: Mul icas ing and
eliable mul icas ing allow hos s o subsc ibe and
unsubsc ibe o any o possibly se e al mul icas
g oups. Mul icas g oups migh be c ea ed based on
en i y ype o geog aphical loca ion in he i ual
en i onmen [12].
• Packe bundling: This in ol es combining a numbe
o da a packe s o c ea e a la ge da a packe because
ne wo k de ices can only p ocess a limi ed numbe
o packe s pe uni ime [8].
• Da a Comp ession: These echniques allow he
educ ion in he size o he in o ma ion packe being
ansmi ed. One echnique is o encode di e ences
be ween successi e da a packe s ins ead o
ansmi ing he absolu e s a e [8].
S a in
g
Poin
S1
• Time Managemen : This in ol es p e-emp ing
e en s and hen locking up he sys em so ha he
e en can occu . Al e na i ely, he execu ion o
local use inpu is delayed and disguised as
some hing else un il he local use inpu can be
elayed o all pa icipan s [13,14]
• P io i y Scheduling: A ansmission p io i y can be
assigned o in o ma ion based on c i e ia such as
speed o mo emen o a e o e o change [15].
This also includes Quali y o Se ice p o ocols [5].
• Visibili y Culling: The en i onmen is di ided in o
cells and mul icas ing upda es a e p o ided o all
en i ies ha a e isible o each o he in each cell [3].
The abo e echniques a e based on ne wo k managemen
and ne wo k pa i ioning policies. We a e going o look a
a packe - educ ion me hod based on clien beha io al
modeling, whe e we swi ch be ween a sho - e m dead
eckoning model and a long- e m s a is ical-based s a egy
model.
3. THE HYBRID TECHNIQUE
3.1 TERMINOLOGY
A goal is he aim o objec i e a pe son has in mo ing
h ough any en i onmen . Fo example, he goal migh be
o go om poin A o poin B. Goals can be classi ied as
ei he s a ic o dynamic. S a ic goals a e s a iona y in
ime and space whe eas dynamic goals de elop o e ime.
In achie ing a goal a pe son can adop a numbe o
s a egies, so ha any one s a egy is an exp ession o he
goal. S a egies can be ei he s eady s a e, ansien o
al e na i e. S eady s a e s a egies a e ob ious s a egies
ha can be modeled on pas da a and a ise ou o use
amilia i y wi h he DIS. T ansien s a egies ela e o
new use s in he en i onmen who beha e in a somewha
e a ic way because hey a e un amilia wi h he
en i onmen . Al e na i e s a egies a e s a egies ha
lead o he goal bu a e nei he ansien o s eady s a e
s a egies. The idea unde lying he hun o s a egies is
o ain a sys em o expec ce ain s a egies based on pas
use beha io o based on expec ed use beha io . Each
s a egy comp ises one o mo e ajec o ies – a se o
ajec o ies can be iden i ied wi h any s a egy. A
ajec o y is an ins ance o en i y mo ion in achie ing a
goal. As wi h s a egies, ajec o ies can be s eady s a e
o ansien . Mul iplici y can e e o ei he s a egies o
goals. S a egy Mul iplici y Index (SMI) e e s o he
numbe o goals a s a egy leads o. Goal Mul iplici y
Index (GMI) e e s o he numbe o s eady-s a e
s a egies ha lead o he goal. This e minology is
illus a ed in Figu e 2. In his pape we p esen esul s o
a s a ic GMI o 1.
Figu e 2: Te minology – S1 o S11 a e s a egies;G1 o
G9 a e goals; T1 is a sample ajec o y; GMI is he Goal
Mul iplici y Index – how many s a egies each ha goal;
SMI = S a egy Mul iplici y Index – how many goals his
s a egy lead o.
3.2 THE HYBRID MODEL
The hyb id model M is o he ollowing o m;
Γ
−
+
=
)1( ppM
χ
(5)
whe e
χ
is any con en ional dead eckoning model,
Γ
is a
long e m model o en i y s a egy and p is a bina y
weigh ing ac o go e ned by:
p = 1 o
θ
≥Γ−M
= 0 o he wise (6)
whe e
θ
ep esen s a dis ance measu e h eshold be ween
he modeled beha io and he long e m model.
The model gi en by M is used by pa icipa ing clien s in a
DIS. The pa ame e s and ini ial en i y s a e used by he
model a e upda ed e e y ime he s a e de ia es om he
ue s a e by a p ede ined h eshold amoun Tm.
While al e na i e so blending echniques could be
employed he e, we ha e op ed o a simple swi ching
echnique o illus a e he p inciples in ol ed.
4 DEVELOPING THE STRATEGY MODEL
4.1 THE TEST ENVIRONMENT
The long- e m s a egy model employed in he hyb id
p edic ion echnique can be cons uc ed in a ious ways:
(1) by eco ding pas ac ual en i y mo emen s in he
en i onmen , (2) by heu is ically iden i ying possible
s a egies based on he examina ion o he en i onmen
and (3) by employing au oma ic pa h- inding echniques.
Goal
S2
S3S4
S5
G1
G2
G3
S7S8
S6
S9
S10
S11
GMI
=
2
T1
G9
SMI = 3
G8
G7
G6
G5
G4
Fo his pape we de eloped a Ja a, game- ype
applica ion ha eco ded use ajec o ies in a con olled
wo-dimensional en i onmen – see igu e 3.
Figu e 3: A sc een sho o he ajec o y eco ding
so wa e. The a ge is shown as a ci cle o he op igh .
The black a eas a e obs acles ha do no allow use s o
pass. The whi e ail ep esen s he pas mo ion.
Figu e 4: A sc een sho o he ajec o y eco ding
so wa e showing he use - es ic ed iew.
Use s we e asked o na iga e om a ixed s a ing
posi ion o a ixed a ge posi ion in as sho a ime as
possible. Thei iew o any obs acles in hei pa h was
es ic ed o a ci cula a ea a ound hei immedia e
posi ion. This is illus a ed in Figu e 4. The use began
wi h no knowledge o he loca ion o he a ge and
epea ed he exe cise un il hey had p oduced he quickes
ime possible. Each a emp cons i u ed a ajec o y. Da a
was collec ed and s o ed o each ajec o y. This
p o ided he basis o he s a is ical-based s a egy model
ha we will use in he hyb id con ac echnique.
4.2 THE STRATEGY MODEL
Using he so wa e applica ion, a minimum o i e and
maximum o ou een ajec o ies we e eco ded om
ou een di e en use s. The inal ajec o y o en o
he ou een use s is plo ed in Figu e 5.
150 200 250 300 350 400 450 500 550 600
0
50
100
150
200
250
300
350
400
X coo dina e
Y Coo dina e
Plo o Raw Use A emp s o achie e Goal
Figu e 5: A plo o he las use ajec o y o 10 use s.
The ajec o y indica ed in bold is he s a egy chosen o
be he s a egy model.
Obse a ion o his plo shows ha he ajec o ies o he
use s con e ge o a ecognizable s eady-s a e s a egy.
This obse a ion unde lies he mo i a ion behind he
hyb id con ac app oach. In his pape we will selec and
use one o hese ajec o ies as ep esen a i e o he
s eady-s a e s a egy. In u u e wo k, we in end o ob ain
a be e s a egy model based on all en da a se s. The
esul s ob ained a e desc ibed in he ollowing sec ion.
5. RESULTS
The s a egy model was ob ained as desc ibed in he
p e ious sec ion. O he emaining ou da a se s, wo
we e chosen and analyzed o compa e he hyb id and i s
o de dead eckoning con ac echniques. The same
h eshold alue was se o bo h. Table 1 shows he
numbe o packe s sen o all ials o bo h use da ase s
and o bo h me hods.
Use 1 Use 2
T ial
no. Dead
Reckoning Hyb id Dead
Reckoning Hyb id
1 19 13 31 32
2 19 17 26 27
3 28 25 18 15
4 20 19 8 3
5 14 12 10 7
6 17 13 14 4
7 9 6 13 13
8 14 12 8 4
Table 1: The numbe o packe s ansmi ed o wo use
se s o bo h pu e dead eckoning and he hyb id me hod.
T ial 1 is he ini ial ial. Th eshold alue: 25.
A selec ed numbe o ials o use 2 a e shown in
Figu es 6a o 6c. Each plo shows he model s a egy
(do ed line), he use ajec o y (con inuous line), he
packe s ansmi ed (as e isks) and he ajec o y as
econs uc ed by he emo e clien .
Figu e 6a plo s he ini ial use ajec o y. The use
wande s a ound he en i onmen seeking he a ge , which
is loca ed a he op igh end o he s a egy model cu e.
The s a egy model is employed on only one occasion,
whe e i o e laps he ajec o y. Mos packe s a e
he e o e he esul o he h eshold alue be ween he
ajec o y and he dead eckoning model being exceeded.
I was expec ed ha he s a egy model would ha e almos
no ele ance since he use had ne e seen he
en i onmen be o e. The econs uc ed ajec o y a he
emo e clien is jagged because a i s o de dead
eckoning algo i hm is used. Thi y- wo packe s a e
ansmi ed.
In Figu e 6b ajec o y i e o use 2 is plo ed. In his
case he use has had ou p e ious a emp s and is mo e
amilia wi h he en i onmen . The ajec o y and he
s a egy model a e in ag eemen o all bu wo sec ions o
he ajec o y. In hese wo sec ions dead eckoning is
employed. The emo e clien uses he s a egy model o
econs uc ion pu poses excep o hese wo sec ions.
Only se en packe s a e ansmi ed. I pu e dead
eckoning we e used, en packe s would be equi ed.
Figu e 6c shows use 2’s inal ajec o y. The use
ajec o y meande s abou he model s a egy, bu emains
wi hin he h eshold dis ance om he s a egy o all bu
one sec ion o he ajec o y. The econs uc ed ajec o y
is he e o e supe imposed on he s a egy cu e excep o
his sec ion. Only ou packe s we e ansmi ed. I pu e
dead eckoning we e used, eigh packe s would be
equi ed.
−100 0 100 200 300 400 500 600
0
50
100
150
200
250
300
350
400
450
X coo dina e
Y coo dina e
Model S a egy
Use T ajec o y
Hyb id Packe s T ansmi ed
Remo e econs uc ion o use ajec o y
Figu e 6a: The i s use 2 ajec o y a emp . The use
wande s, a emp ing o loca e he a ge ( o he op igh ).
The ugged emo e econs uc ion esul s om using a
i s o de dead eckoning algo i hm. The s a egy model
is used on one occasion.
150 200 250 300 350 400 450 500 550 600
0
50
100
150
200
250
300
350
400
X coo dina e
Y coo dina e
Model S a egy
Use T ajec o y
Hyb id Packe s T ansmi ed
Remo e econs uc ion o use ajec o y
Figu e 6b: This is he i h use 2 a emp . The use
ajec o y eaches he a ge . Whe e he emo e
econs uc ion (dashed line) appea s o disappea , i is in
ac supe imposed on he model s a egy. Dead eckoning
is employed on wo occasions only.
150 200 250 300 350 400 450 500 550 600
0
50
100
150
200
250
300
350
400
X coo dina e
Y coo dina e
Model S a egy
Use T ajec o y
Hyb id Packe s T ansmi ed
Remo e econs uc ion o use ajec o y
Figu e 6c: This is he eigh h ajec o y o use 2. Dead
eckoning is only employed on one occasion. Fo mos o
i s leng h, he ajec o y is emo ely ep esen ed as he
s a egy.
I should be no ed he pe o mance o he hyb id
echnique is based on a ela i ely high h eshold e o
alue. Reducing his alue esul s in a poo e
pe o mance om he hyb id model, al hough i is ne e
any wo se han he pu e dead eckoning model. I is
concei able ha employing a mul iple-model s a egy,
whe e he numbe o models is ela ed o h eshold, would
signi ican ly imp o e modeling pe o mance.
6. Conclusions and Fu u e Wo k
In his pape we ha e desc ibed a echnique called hyb id
swi ching ha educes he numbe o packe s ha need o
be ansmi ed o main ain s a e ideli y ac oss a simple
dis ibu ed applica ion.
Using a es en i onmen de eloped in Ja a we compa ed
he dead eckoning echnique wi h a hyb id swi ching

echnique and we illus a ed ha he hyb id echnique
equi ed ewe packe s compa ed o dead eckoning o
emo e ajec o y econs uc ion. Howe e , as p e iously
no ed, his was based on a high h eshold alue.
Fu u e wo k will in ol e looking a imp o ing
pe o mance o lowe alues o h eshold h ough he use
o mul iple model s a egies and mul iple model blending
echniques.
ACKNOWLEDGEMENT
This wo k was unded by En e p ise I eland Basic
Resea ch G an SC/2002/129/.
REFERENCES
[1] S. K. Singhal and M. Zyda, Ne wo ked Vi ual
En i onmen s ( S. Spence ACM P ess, 1999).
[2] D. Kushne , The Wiza d y o ID, IEEE Spec um
(39) 8 Augus 2002, 42-47.
[3] C. Faiss naue , D. Schmals ieg, and W. Pu ga ho e ,
Scheduling o e y la ge Vi ual En i onmen s and
Ne wo ked Games using Visibili y and p io i ies,
P oceedings o he 4 h IEEE In e na ional Wo kshop
on Dis ibu ed Simula ion and Real-Time
Applica ions, San F ancisco, Cali o nia 24 - 26
Augus 2000, 31-38.
[4] L.A.H. Liang, Wen ong Cai, u-Sung Lee and S. J.
Tu ne , Pe o mance Analysis o Packe Bundling
Techniques in DIS, P oceedings o he 3 d IEEE
In e na ional Wo kshop on Dis ibu ed In e ac i e
Simula ion and Real-Time Applica ions, College
Pa k, Ma yland 23 - 24 Oc obe 1999, 75-82.
[5] A.S. Tannenbaum, Compu e Ne wo ks Thi d
Edi ion, (P en ice-Hall, 1996).
[6] Wen ong Cai, F.B.S. Lee, and L. Chen, An Au o-
adap i e Dead Reckoning Algo i hm o Dis ibu ed
In e ac i e Simula ion, P oceedings o he 13 h
Wo kshop on Pa allel and Dis ibu ed Simula ion,
A lan a, Geo gia 1 - 4 May 1999, 82-89.
[7] G.J. Valen ino, S.T. Thompson, T. Kniola and C.J.
Ca lisle, An SMP-based, Low-la ency, Ne wo k
In e ace Uni and La ency measu emen Sys em: he
SNAPpy sys em, P oceedings o he 2nd IEEE
In e na ional Wo kshop on Dis ibu ed In e ac i e
Simula ion and Real-Time Applica ions, Mon eal,
Canada, 19 - 20 July 1998, 62-70.
[8] M.A. Bassiouni, Chiu Ming-Hsing, M. Lope , M.
Ga nsey and J. Williams, Pe o mance and eliabili y
analysis o ele ance il e ing o scalable dis ibu ed
in e ac i e simula ion, ACM T ansac ions on
modeling and compu e simula ion, (7)3, July 1997,
293-331.
[9] IEEE S anda d o Dis ibu ed In e ac i e
Simula ion - Applica ion P o ocols IEEE S d
1278.1-1995.
[10] C. Du bach and J.M. Fou neau, Pe o mance
e alua ion o a dead eckoning mechanism,
P oceedings o he 2nd IEEE In e na ional
Wo kshop on Dis ibu ed In e ac i e Simula ion and
RealTime Applica ions, A lan a, Geo gia, 1 - 4 May
1999, 23-29.
[11] T.K. Capin, J. Eme aldo and D. Thalmann, A dead
eckoning echnique o s eaming i ual human
anima ion, IEEE T ansac ions on Ci cui s and
Sys ems o Video Technology, (9)3 Ap il 1999, 411-
414.
[12] J. M. Pullen, Reliable Mul icas ne wo k T anspo
o Dis ibu ed Vi ual Simula ion, P oceedings o
he 3 d IEEE In e na ional Wo kshop on Dis ibu ed
In e ac i e Simula ion and Real-Time Applica ions,
College Pa k, Ma yland, 23 - 24 Oc obe 1999, 59-
66.
[13] B. G. Wo hing on and D.J. Robe s, Encapsula ing
Ne wo k La ency Compensa o s in VRML,
P oceedings o VWSIM (Vi ual Wo lds and
Simula ion Con e ence) In . Con . SCS Wes e n
Mul i-con e ence, San Diego, USA, Janua y 2000.
[14] D.J. Robe s and P. M. Sha key, Maximising
Concu ency and Scalabili y in a Consis en ,
Causal, Dis ibu ed Vi ual Reali y Sys em, whils
minimising he e ec o Ne wo k Delays,
P oceedings o he 6 h IEEE Wo kshop on Enabling
Technologies: In as uc u e o Collabo a i e
En e p ises, Camb idge, MA , June 1997, 161-166.
[15] C. Faiss naue , D. Schmals ieg, and W. Pu ga ho e ,
P io i y Round-Robin Scheduling o e y la ge
Vi ual En i onmen s, P oceedings o he IEEE
Vi ual Reali y 2000 Con e ence, New B unswick,
New Je sey, 18 - 22 Ma ch 2000, 135-142.