On reducing entity state update packets in distributed interactive simulations using a hybrid model

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.