HGRID: A self-configuring grid resource discovery

Jou nal o Compu ing and In o ma ion Technology - CIT 16, 2008, 4, 333–338 doi:10.2498/ci .1001402 333 HGRID: A Sel -con igu ing G id Resou ce Disco e y An onia Galla do1,LuisDiazdeCe io 2and Kana Sanjee an1 1Depa men o Compu e A chi ec u e, Poly echnic Uni e si y o Ca alonia, Ba celona, Spain 2Depa men o Au oma ion and Compu e Science, Public Uni e si y o Na a e, Pamplona, Spain G id Resou ce Disco e y Se ice is a undamen al p ob- lem ha has been he ocus o esea ch in he ecen pas . We p opose a scheme ha p esen s essen ial cha ac- e is ics o e icien , sel -con igu ing and aul - ole an esou ce disco e y able o handle dynamic a ibu es such as memo y capaci y. Ou app oach consis s o an o e - lay ne wo k wi h a hype cube opology connec ing he g id nodes and a scalable, aul - ole an , sel -con igu ing sea ch algo i hm. By design, he algo i hm imp o es he p obabili y o eaching all wo king nodes in he sys em, e en in he p esence o non-ali e nodes (inaccessible, c ashed o nodes loaded by hea y a ic).Weanalyze he s a ic esilience o he app oach p esen ed, which is he measu e o how well he algo i hm can disco e e- sou ces wi hou ha ing o upda e he ou ing ables. The esul s show ha he p esen ed app oach has signi ican ly high s a ic esilience. Keywo ds: s a ic esilience, aul - ole an , g id esou ce disco e y, hype cube, sel -con igu ing p o ocol 1. In oduc ion A G id is an en i onmen which allows he sha - ing o esou ces (compu e s, disk space, mem- o y, bandwid h, da a, ins umen s such as ele- scopes o mic oscopes e c.) ha a e connec ed o a ne wo k (e.g. he In e ne ). The main objec i e o a G id is o enable use s o sol e p oblems using he a ailable collec- i e esou ces. In his way, he G id esou ce disco e y se ice plays a undamen al ole, al- lowing g id-enabled applica ions o loca e e- sou ces based on a gi en se o equi emen s. Resou ce sea ch in Pee - o-Pee (P2P)sys ems o e s an a ac i e app oach o deploy ully dis- ibu ed aul - ole an G id disco e y se ice. Bu o he G id, we ha e some ex a equi e- men s such as he exis ence o dynamic esou ce in o ma ion (e.g. a ailable memo y, disk space, e c). In hese cases, some o he P2P sea ching echniques a e di icul o apply because hey a e mo e sui able o non-dynamic con en . Ou a chi ec u e is based on an o e lay ne wo k opology in he o m o a hype cube which in- e connec s nodes p o ided by he Vi ual O - ganiza ions (VOs). Wealsop esen asel - con igu ing esou ce disco e y algo i hm ha is able o adap o complex en i onmen s whe e some nodes migh be non-ali e (c ashed, inac- cessible, expe iencing hea y a ic, e c.)when a esou ce is equi ed. Resilience in he p esence o node ailu e has di e en aspec s – s a ic esilience and ou ing eco e y. As he p esen wo k is ocused on he esou ce disco e y algo i hm we only ad- d ess s a ic esilience in his pape – ha is, how well ou app oach can loca e equi ed e- sou ces be o e ou ing ables a e upda ed by he ou ing eco e y algo i hm in o de o emo e non-ali e nodes in he o e lay [4]. The o he issue, ou ing eco e y, is no add essed in his pape as his issue is ela ed o he building and main aining o he o e lay opology. The es o he pape is o ganized as ollows: In Sec ion 2 we p esen an o e iew o ou o e lay ne wo k a chi ec u e. Sec ion 3 desc ibes ou esou ce sea ch algo i hm. A b ie o e iew o ela ed wo k is p esen ed in Sec ion 4. In Sec ion 5, he pe o mance o he algo i hm is e alua ed. Conclusions and ou plans o u u e wo k can be ound in Sec ion 6. 334 HGRID: A Sel -con igu ing G id Resou ce Disco e y 2. The Hype cube O e lay A chi ec u e In he hype cube o e lay ne wo k ha we p esen – named HG id – each VO belonging o he G id p o ides a ailable esou ces (compu e s, appli- ca ions, disk space, memo y e c.)and makes hem accessible h ough wha we call he G id In o ma ion Sys em (GIS)[1]. In HG id, he in e connec ions be ween GISs ha e he opology o a hype cube. An n-dimen- sional hype cube (Hn)has V(Hn)=2nnodes, whe e each one ep esen s a GIS. Each node (o GIS)has an iden i ie ha goes om 0 o 2n−1. Two nodes a e said o be di ec ly connec ed o each o he ( hey a e said o be neighbo s in he m- h dimension)i he bina y ep esen a ions o hei iden i ie s di e exac ly by he m- h bi . The e o e, in a comple e hype cube Hn, each e ex (GIS)has exac ly nneighbo s. Figu e 1 illus a es he a chi ec u e o he in e ac ion among 2, 4 and 8 nodes espec i ely. Figu e 1. H1)The a chi ec u e o he in e ac ion among 2 nodes, a one-dimensional hype cube, H2)4 nodes, a wo-dimensional hype cube and H3)8 nodes, a h ee-dimensional hype cube. 3. Resou ce Sea ch Using HGRID In his sec ion we p esen a scalable sel -con i- gu ing esou ce sea ch algo i hm (named Algo- i hm-H) ha is able o adap o complex en i- onmen s. I is possible o ini ia e a sea ch eques om any o he li e nodes. Fo easons o cla i y howe e , he examples used om now on as- sume ha node 0 is he s a node, wi hou any loss o gene ali y. 3.1. The Sea ch P ocedu e in an HnUsing Algo i hm-H The sea ch p ocedu e s a s when a consume wan s o disco e a G id se ice. The consume connec s o one o he GIS nodes o he sys- em and eques s a se ice (a esou ce o some esou ces). The se ice disco e y is ied i s inside he eques e ’s own GIS I he e is no p o ide , hen he eques is edi ec ed o o he GISs. Figu e 2 shows he pseudo-code ha is pe o med a each node when a new se ice e- ques message a i es: 1)When a new se ice eques message is e- cei ed by a node he unc ion p ocessRe- ques (message. eques ) is called. I he e- ques included in he message canno be sa - is ied, he node se s he alue o sa is yRe- ques o alse and he eques is p opaga ed. Figu e 2. Algo i hm-H pseudo-code. HGRID: A Sel -con igu ing G id Resou ce Disco e y 335 O he wise, sa is yReques is se o ue and no p opaga ion is pe o med. The message o wa ded is composed o he eques (mes- sage. eques )and wo ec o s o dimensions (message. dand message. a). In case he eques canno be sa is ied and he node ha ecei es he message is he s a node (s a Node is ue), he lis d is ini ialized o d={0,1,...,n−1}( he comple e se o dimensions)and ais ini ial- ized o a={} (an emp y lis ).O he wise, dand aa e ini ialized o he lis s ecei ed along wi h he eques message. In bo h cases, he lis s ep esen he se o dimen- sions (neighbo s)along which he message mus be p opaga ed. 2)The node calls he s a usNeighbo s( d) unc- ion and eo de s he lis din such a way ha he dimensions co esponding o he non- ali e neighbo s a e loca ed a he las po- si ions o he lis . Fo example i d= {0,1,2,3}and he neighbo along dimen- sion 1 is no esponding, hen dis eo de ed o {0,2,3,1}.Thes a usNeighbo s( d)also e u ns wo in ege alues nnon−ali e and dali e. The in ege alue nnon−ali e ep esen s he numbe o non-ali e nodes in he eo de ed lis d. The in ege alue dali e ep esen s he dimension o he las ali e neighbo s o ed in d. Fo example, i d={2,1,0,3}and i s neighbo s in dimensions 0 and 3 a e non- ali e nodes, nnon−ali e =2anddali e =1. 3)I he numbe o non-ali e neighbo s (nnon−ali e)is mo e han one, he node calls he addToLis ( a,dali e) unc ion. This unc- ion appends dali e o he end o he lis a and e u ns he new lis ( a2). 4)Fo each posi ion kin he lis d ha ep- esen s a li e neighbo node, he node calls he c ea eLis (k, d) unc ion which c ea es a new lis composed o all he dimensions loca ed a e posi ion kin he o de ed lis d. In o he wo ds, i he numbe o el- emen s in d( d.size())is q, he unc ion e u ns { d[k+1],..., d[q−1]}.Fo ex- ample, i d={0,2,3,1}and k=1, he call o c ea eLis (k, d)will e u n {3,1}. Also, o each ali e neighbo , he alis is ini ialized. The eques , d,and aa e sen o he co esponding neighbo in he d[k]dimension inside a new message by calling he sendToNeigbo ( d[k],message) unc ion. See Figu e 3 (a comple e exam- ple using Algo i hm-H)whe e he s a node (0000)sends d={2,1,0}and a={3} o i s las ali e neighbo ( he only one in his case). 5)Finally, he node p opaga es he eques o each o he neighbo s along adimensions only i he co esponding neighbo is no i s pa en node. The eques a els inside a message oge he wi h aand das emp y lis s. P opaga ing he eques s in his way, he e ec o non-ali e nodes is educed. Mak- ing he ea angemen in he dlis , non- ali e nodes would p opaga e he eques o ewe neighbo s han ali e ones (in case he p opaga ion we e ied). Consequen ly, he algo i hm ies o isola e he nodes ha a e in a non-ali e s a e so ha hey become lea nodes (i i is possible). I , unde he ci - cums ances, each node has only one non- ali e neighbo , hen all li e nodes can be eached. On he o he hand, he nodes ha a e un eachable because o inaccessible o c ashed nodes along a pa h o hem, can be eached e en ually ia o he nodes – using he alis . 3.2. A Comple e Example Using Algo i hm-H Figu e 3 illus a es a comple e example. We ans o m he hype cube ep esen a ion o ha o a ee-like igu e in o de o illus a e be e ou sea ch p ocedu e ( o example, some ‘child’ nodes could appea mo e han once du ing sub- sequen ime s eps). A eques o se ice Ps a s a node 0000 in a ou -dimensional hype cube. We assume ha none o he nodes has he se ice eques ed (no e ha his is he wo s case).In heex- ample, he alue o he lis da he s a node is {0,1,2,3}and he o de ing a e calling he s a- usNeighbo s() unc ion is {3,2,1,0}.In his case 2, 1 and 0 a e loca ed a he las h ee po- si ions o d={3,2,1,0}because we assume ha neighbo s in dimensions 2 (0100),1(0010) and 0 (0001)a e non-ali e nodes. The neighbo in dimension 3 (1000)is he las ali e node, so a2={3}and a={}. In i e s eps almos all o he li e nodes in- side he ou -dimensional hype cube a e isi ed 336 HGRID: A Sel -con igu ing G id Resou ce Disco e y Figu e 3. A comple e example using Algo i hm-H. A eques o esou ce P s a ed a node 0000 in a ou -dimensional hype cube. (all excep node 0110), e en when h ee ou o ou o he s a node’s neighbo s (0100, 0010 and 0001)and wo addi ional nodes (1100 and 1010)a e p esumed o be non-ali e. 4. Rela ed Wo k The Globus Toolki ’s Moni o ing and Disco e y Sys em (MDS)de ines and implemen s mech- anisms o se ice and esou ce disco e y and moni o ing in dis ibu ed G id en i onmen s [2]. Mo i a ed by hese issues, ecen ly he e ha e been se e al s udies using he P2P model o build a decen alized a chi ec u e o VOs. Mos o hem adop Dis ibu ed Hash Tables (DHTs), and a ew o hem in oduce uns uc u ed P2P opologies. All hese s udies indica e ha some P2P models could help o o e come he chal- lenges posed by he dynamic en i onmen in G ids. Ad iana Iamni chi and Ian Fos e [6]sugges a decen alized a chi ec u e simila o he Gnu ella P2P sys em. This app oach is no able o gua - an ee ha some equi ed in o ma ion exis ing in he sys em can be ound, e en when he sys em has no ailu es (none o he nodes a e inaccessi- ble o c ashed). Mo eo e , a pee could be o en eached se e al imes by he same eques . Ou app oach assu es ha nodes a e eached only once. In he absence o ailu es, all nodes in he sys em a e eached and i ailu es occu almos all he nodes a e eached. DHT-based sys ems handle unexpec ed node ailu e h ough edundancy in he ne wo k and some o hem also do node lookups asynch o- nously o pe iodically, o compensa e o disap- pea ed nodes – o example, Kadmelia [7]. In o de o enable e icien sea ches, a DHT needs o ha e he da a-i em dis ibu ed ac oss he pee s. Ou app oach does no equi e dis- ibu ing he da a-i ems, bu each eques sends om 0 o N−1 messages. Keeping he s a e o highly dynamic da a-i ems upda ed (such as a ailable memo y o CPU p ocessing) equi es sending a e y la ge amoun o messages in DHTs. HGRID: A Sel -con igu ing G id Resou ce Disco e y 337 In HG id, changes in he o e lay ne wo k when a G id node joins o lea es he sys em do no cause esou ce in o ma ion (da a-i ems) o be emapped, whe eas in adi ional DHTs, i cau- ses bo h ou ing ables and da a-i ems o be emapped. Recen ly, an uns uc u ed opology based on hy- pe cubes has been p oposed o use on Da a G ids [5]. The nodes in his wo k con ain poin - e s o sha ed da a. Da a G ids need o im- p o e locali y among dis ibu ed da a (which a e s o ed as poin e s in he o e lay nodes).In o de o imp o e he locali y o da a, he pape imposes a hype cube opology o GIS (named DGIS). I hen p oposes a ansposi ion algo- i hm o op imize he o e lay ne wo k’s opol- ogy acco ding o he access s a is ics be ween pee s ( ha is, o imp o e he da a locali y). Howe e , he algo i hm shown does no add ess non-ali e nodes. 5. Pe o mance E alua ion Nex we p esen simula ions o e alua e i some equi ed in o ma ion ha exis s in he sys em can be ound (lookup gua an ees)wi hou e- so ing o ac i e eco e y algo i hms. Fo his simula ion, we ha e es ed s a ic e- silience [2]wi h en housand, one hund ed housand and one million nodes - using 14, 17 and 20 dimensional hype cube o e lays. All nodes ha e he same p obabili y P o ailu e. P can be seen as he pe cen age o non-ali e nodes ha can be ound in he o e lay. We un he simula ion o alues o P be ween 0 and 50% – because we assume ha he G id en i onmen is no ex emely ansien . Gi en aP , we s a a eques o se ice Pa node 0, assuming ha none o he nodes has he se - ice eques ed, and coun how many li e nodes a e no eached by he eques P( ailed pa hs). The simula ion is epea ed 20 imes o each P ge ing he a e age numbe o ailed pa hs. Fi- nally we compa e ou app oach (Algo i hm-H) wi h wo o he sea ch algo i hms o hype cube o e lays [5][3]. The a e age pe cen age o ailed pa hs o a y- ing P is shown in Figu e 4. Ou p oposal o - e s subs an ially be e s a ic esilience han he HaoRen e al.’s algo i hm [5]. The HG id algo i hm-H wo ks e y well in non-ex emely ansien en i onmen s, whe e a educed ac- ion o he nodes a e down a any gi en ime (<50% o ailed nodes in he en i e G id).A he same ime, Algo i hm-H o e s be e e- silience han Algo i hm-P [3]as i can each mo e li e nodes wi hou using ac i e eco e y algo i hms. Algo i hm-H is no only scalable in o e lay hops (n ime s eps whe e nis he dimension- ali y), bu as seen in Figu e 4, i is scalable in he numbe o nodes (214 o 220 om Figu e 4). Figu e 4. Pe cen age o a e age o ailed pa hs o a ying P ac oss di e en sea ch algo i hms. HaoRen e al.’s algo i hm is a non aul - ole an algo i hm desc ibed in [5]. Algo i hm-P is a aul - ole an algo i hm desc ibed in [3]. 6. Conclusions and Fu u e Wo k The p oposed algo i hm is scalable in e ms o ime, because i keeps he maximum numbe o ime s eps equi ed o esol e a esou ce e- ques , o a loga i hmic scale wi h espec o he o al numbe o nodes. Mo eo e , each node has only pa ial knowledge o he o e lay G id. Nodes do no equi e ha ing he s a e in o ma- ion o he es o nodes in he o e lay, bu only o he s a e o i s neighbo s. The e o e, ou ap- p oach is also scalable in e ms o da a s o age. Fu he mo e, scalabili y is also main ained by que ying each node only once a he mos (i possible). This impo an p ope y (scalabili y) also ex ends o he numbe o nodes in he G id – as can be seen clea ly in Figu e 4. Unlike adi ional app oaches based on DHTs, ou scheme is sui able o e icien ly handling dynamic a ibu es such as memo y capaci y, wi hou gene a ing o e head ac oss geog aphi- cally dis ibu ed nodes. Ou me hod helps o balance he sys em load and is mo e e icien han o he schemes like 338 HGRID: A Sel -con igu ing G id Resou ce Disco e y looding. Addi ionally, i is sel -con igu ing when he e a e c ashed o hea ily loaded nodes. By using he deep mul i-dimensional in e con- nec ion o a hype cube, we p o ide enough con- nec i i y so ha esou ce eques s can always be p opaga ed in spi e o non-ali e nodes. This makes ou p oposed algo i hm much mo e aul - ole an when i is compa ed wi h o he opolo- gies such as cen alized, hie a chical o ees. In he absence o non-ali e nodes, i is able o o e lookup gua an ees. Comple ing he compa ison wi h DHT-enabled implemen a ions is a goal o u u e wo k. The e a e se e al in e es ing a eas ha ha e opened up as a esul o his wo k and we a e p esen ly wo king on hem: a)Design and e alua ion o new eques o wa ding s a egies, b)Inco po a ion o opology cons uc ion and main enance algo i hms and c)E alua ion in e ms o esponse ime, scalabili y e c. by simu- la ion. 7. Acknowledgmen s This wo k was suppo ed by he Minis y o Science and Technology o Spain and he Eu- opean Union unde he e e ences TIN2007- 68050-C03-01 and TIN2007-68050-C03-02. Re e ences [1]R. BUYYA AND M. MURSHED, “G idSim: A Toolki o he Modeling and Simula ion o Dis ibu ed Re- sou ce Managemen and Scheduling o G id Com- pu ing”, Concu ency and Compu a ion: P ac ice and Expe ience (CCPE), Volume 14, Issue 13-15, (2002). [2]K. CZAJKOWSKI,S.FITZGERALD,I.FOSTER AND C. KESSELMAN, “G id In o ma ion Se ices o Dis- ibu ed Resou ce Sha ing”. 10 h IEEE In e na ional Symposium on High Pe o mance Dis ibu ed Com- pu ing, IEEE P ess, 2001. [3]A. GALLARDO,L.D ´ IAZ DE CERIO,K.SANJEEVAN AND L. C. E. BONA, “HGRID: A Hype cube-Based G id Resou ce Disco e y”, submi ed o Special Is- sue on G id Resou ce Managemen , IEEE Sys ems Jou nal, Sep embe 2007. [4]K. GUMMADI ET.AL, “The Impac o DHT Rou ing Geome y on Resilience and P oximi y”, in P oc. o he 2003 Con e ence on Applica ions, Technologies, A chi ec u es, and P o ocols o Compu e Commu- nica ions, Ka ls uhe, Ge many, Augus 2003, pp. 381 – 394, ISBN:1-58113-735-4. [5]HAO REN,ZHIYING WANG,ZHONGLIU, “A Hype - cube based P2P In o ma ion Se ice o Da a G id”, Fi h In e na ional Con e ence on G id and Coop- e a i e Compu ing, 2006, pp. 508-513. [6]A. IAMNITCHI AND I. FOSTER, “On ully decen- alized esou ce disco e y in g id en i onmen s”, Second In e na ional Wo kshop on G id Compu ing, pp 51-62, London, UK, 2001. Sp inge -Ve lag. [7]KADEMLIA:ADESIGN SPECIFICATION, a ailable- h p://xla ice.sou ce o ge.ne /componen s/ p o ocol/kademlia/specs.h ml. Recei ed: June, 2008 Accep ed: Sep embe , 2008 Con ac add esses: An onia Galla do Depa amen de A qui ec u a de Compu ado s a he Uni e si a Poli ´ ecnica de Ca alunya A da. del Canal Ol´ ımpic s/n 08860 Cas ellde els Ba celona, Spain e-mail: [email p o ec ed] Luis Diaz de Ce io Dp o. Auo m´ a ica y Compu aci´ on Uni e sidad P´ ublicadeNa a a Campus de A osadia Edi icio depa amen al de los Pinos 31006 Pamplona, Spain e-mail: luismanuel.diazdece io@una a a.es K. Sanjee an Depa amen de A qui ec u a de Compu ado s a he Uni e si a Poli ´ ecnica de Ca alunya A da. del Canal Ol´ ımpic s/n 08860 Cas ellde els Ba celona, Spain e-mail: [email p o ec ed] ANTONIA GALLARDO ecei ed he deg ee in elecommunica ions engi- nee ing in 2000 om he Uni e si a Poli ` ecnica de Ca alunya (UPC) in Ba celona, Spain. Cu en ly, she is a PhD s uden and assis an p o esso in he Compu e A chi ec u e Depa men a he Uni e si a Poli ` ecnica de Ca alunya. He esea ch in e es s ocus on dis ibu ed compu ing and g id sys ems. LUIS M. DIAZ DE CERIO ecei ed he deg ee in elecommunica ions enginee ing in 1993 and he PhD deg ee in elecommunica ions en- ginee ing in 1998, bo h om he Uni e si a Poli ` ecnica de Ca alunya (UPC)in Ba celona, Spain. He is cu en ly an associa e p o esso in he Au oma ics and Compu ing Depa men a he Uni e sidad P´ ublica de Na a a (UPNA). His esea ch in e es s ocus on dis ibu ed compu ing and g id sys ems. KANA SANJEEVAN has a Bachelo s deg ee om he Indian Ins i u e o Technology, Chennai. He also has double Mas e s deg ees in engi- nee ing and compu e science om he Uni e si y o Cali o nia. He is cu en ly an assis an p o esso in he Depa men o Compu e A chi- ec u e, a he Uni e si a Poli ` ecnica de Ca alunya (UPC)in Ba celona, Spain. His esea ch in e es s ocus on dis ibu ed compu ing and g id sys ems.