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.