Embed Size (px)
Citation preview
1
Um sistema distribuído para busca de caminhos em grafos dinâmicos
Marcelo Luís Vinagreiro
Orientador: Prof. Alfredo Goldman
2
Descrição do Problema/Cenário de aplicação
Desenvolvimento de um modelo que permita a busca de caminhos em um grafo distribuído
Exemplos de aplicação:
• Sistema descentralizado para monitoramento do trânsito de uma dada cidade
• Busca de caminhos para unidades móveis
• Simulação de rede distribuída
3
Algoritmos dinâmicos – Narváez et al.
• Considerações iniciais:
1. Algoritmo básico: permite transformar versões estáticas de algoritmos de busca em suas respectivas versões dinâmicas
2. Duas variações do algoritmo básico: First Incremental Method, Second Incremental Method.
4
Arquitetura Proposta
Modelagem
EA EB
8
6
5
79 10
1314
1516
1817
19
11
12
2
3
1
4
• Bordas
• B(GA) = { 1, 2, 5, 6, 8, 10, 11, 12 }• B(GB) = {10, 11, 12, 13, 14, 16, 18, 20}• B(GA) B(GB) = { 10, 11, 12 }
5
Modelagem – (cont.)
• Dois tipos de servidores:
• Estação-base (Base Server) (BSi)
• Servidor de Busca (Search Server) (SBi)
Seja:
NBS >= 1 : o número de BSs BS = { BSi | 1 i NEB } NSS >= 1 : o número de SSs SS = { SSi | 1 i NSB }
Onde: SS BS
6
RootSet e RootWeightSet• RootSet(Gi) = RS(Gi) : um subconjunto de nós na borda de Gi
• RootWeightSet(RSi) : custo dos melhores caminhos entre todas combinações possíveis de pontos em RSi
Exemplo:
B2
B1
B3
I1
B4
1
8
2
5
0
8
RootSet(Gi): { B1, B2, B3, B4 }
BSi
Peers X->Y Y->XB1-B2 1 8B1-B3 0 -B1-B4 3 -B2-B4 2 -
RootWeightSet(Gi):
7
Forward Tree de RSi – FT(RSi)
RS2
RS1
RS4X
RS5
8
2
0
8
RS3
10
2
RS23
RS1
RS3 RS4
RS5
KZ Z
2
28
32
0
Forward Tree (RS2)
8
Model Tree – MT(Rx)
9
Roteamento adaptativo através de árvores dinâmicasProcessamento em BSi
• BSi mantém subgrafo Gi;• Em intervalos regulares, BSi obtém/atualiza as
árvores FTstateId(RSk), para cada nó RSk, com dados de stateId;
• Com os dados de FT(RSk), BSi gera RootWeightSetstateId(Gi) e envia para o conjunto SS;
Processamento em SSk
• SSk recebe de EBt o conjunto RootWeightSetstateIdt, em
1 t NBS. Assim que SSk recebe todos conjuntos RootWeightSetstateId
t, SSk atualiza árvores MTstateId(t) • E envia msg Received_RwsetstateId, informando a Bt
com uma o recebimento de RootWeightSetstateIdt
10
Busca de caminhosA. Seja uma requisição de caminho de X a Y enviada à
estação-base BSX. O processamento da busca de caminhos é feita em dois níveis:
• Intra-estação: busca no interior de BSX e/ou,
• Inter-estação: nesse caso BSX consulta algum servidor de busca SSj para incluir informações de outras estações na busca.
B. Dois tipos de requisições cliente:
• Busca global: caminho completo de X a Y
• Busca local: caminho de X a R tal que R está em RS(BSX).
11
Procedimento de Busca
Formado por 4 procedimentos principais:
• PerformBSPathSearch: executado em BSx;
• PerformInterPath: executado em BSx;
• PerformSSPathSearch: executado em SSj
• PerformPathInForwardTrees: executado em BSy;
12
Busca em BSi
Procedure PerformBSPathSearch(X,Y,req)
BSX calcula a árvore de caminhos TstateId(X);
if Y BSX then/* se há um caminho PXY com custo , retorna PXY
*/if um caminho PXY TstateId(X) | Weight(PXY)
then return PXY; else
Seja PINTRA := { PXY | Weight(PXY) é mínimo } PINTER = FindInterPath(X,Y,req, TstateId(X),stateId)
Seja PMIN o caminho de peso mínimo entre PINTER e PINTRA
return PMIN.else
return FindInterPath(X,Y,req, TstateId(X),stateId).
End Procedure
13
Busca em BSi (cont.)
Procedure FindInterPath(X, Y, req, TstateId(X), stateId)
XToRSWeightSet :=
/* caminhos para as bordas */for each r RootSet(Gx) do if r TstateId(X) then
XToRSWeightSet := XToRSWeightSet {r, Weight(X,r)} else
XToRSWeightSet := XToRSWeightSet {r, }
/* escolhe SS e chama remotamente FindShortestPath */
Resp := RPC (SSj, FindSSPathSearch(X,Y, req, XToRSWeightSet,
stateId) )
14
Busca em BSi (cont.)
if req = Global then /* Resp é um caminho: RSt -> N1 -> ... -> Y */
Seja Rt o nó inicial do caminho Resp; Rt RootSet(GX)
Seja P’t o caminho de X a Rt, em TstateId(X)/* retira-se o nó Rt do conjunto */ Seja Pt = P’t - Rt
return Pt Respelse
/* Resp = (Rt,C) retorna o nó Rt em RootSet(GX) que gera o caminho de X a Y com custo C */
Seja C o peso calculado por SBj para chegar em Y. E, Rt RootSet(GX) o nó que origina tal caminho. Seja Pt o caminho
de X a Rt TstateId(X)./* retorna Pt com peso C */return Pt
End Procedure
15
Busca em SBj
Procedure FindSSPathSearch(X, Y, req, XToRSWeightSet, stateId)
RSWeightSetToY := RPC(BSY, FindPathInForwardTrees(Y,stateId))
P´ := DynamicSPT(X, Y, XToRSWeightSet, RSWeightSetToY, stateId)
if req = Local then
Seja Rk o nó em RootSet de BSX que está no caminho mínimo de X até Y e C o custo associado
return {Rk, C}
16
Busca em SBj
elseSeja P= P1->P2->...->Py o caminho global,
montado buscando-se os caminhos intermediários (Pi) nas respectivas BSs envolvidas com o caminho P.
return P
End Procedure
17
Busca em BSY
Procedure FindPathInForwardTrees(Y, stateId)
RSWeightSetToY :=
for each árvore FTstateId(Ri) doif Y FTstateId(Ri) then
RSWeightSetToY := RSWeightSetToY {Ri, Weight(Ri,Y)}
else RSWeightSetToY := RSWeightSetToY {Ri, }
return RSWeightSetToY
End Procedure
18
Atualização do sistema
K K+1
EB1=EBc
EB2
EB3
Update_Rset(k+1)
(I)
(I)
(I)
Received_Rset(k+1)
Received_Rset(k+1)
Commit_Rset(k+1)
Commit_Rset(k+1)Update_Rset(k+1)
19
20
Base Server
Perform_Path_Search
Find_RsetToY_Values
Rqst_Sub_Path
Update_Rset
Update_Global_State
Commit_Rset
Update_Link_State
AçãoBaseServerRequestAgentFindRset2YAgent
RequestSubPathAgent
UpdateRsetAgent
UpdateTransactionAgent
CommitRsetAgent
UpdateDataLinkAgent
Agente
BSAgents
21
SSAgents
Search Server
Find_Inter_Path
Update_RwsetCommit_Rset
Ação
PerformSSPathAgent
UpdateRwsetAgentCommitRsetAgent
Agente
22
Influência do RootSet – Atualização
0
100000
200000
300000
400000
500000
25% 50% 75% 100%
RootSet
Atua
lizaç
ão S
S-E
(ms)
2
3
4
5
0
50000
100000
150000
200000
250000
300000
25% 50% 75% 100%
RootSet
Atua
lizaç
ão B
S-E
(ms)
2
3
4
5
0
50000
100000
150000
200000
250000
300000
25% 50% 75% 100%
RootSet
Atua
lizaç
ão B
S-D
(ms)
2
3
4
5
0
100000
200000
300000
400000
500000
25% 50% 75% 100%
RootSet
Atua
lizaç
ão S
S-D
(ms)
2
3
4
5
23
0%
10%
20%
30%
40%
50%
2 3 4 5
Número de estações-base
Com
para
ção
BS-D
/ BS
-E
25%
50%
75%100%
0%
20%
40%
60%
80%
100%
2 3 4 5
Número de estações-base
Com
para
ção
SS-D
/SS-
E
25%
50%
75%
100%
Influência do RootSet – Atualização (cont)
24
Influência do RootSet – Buscas
0
1000
2000
3000
4000
5000
0,25 0,50 0,75 1,00
RootSet
B. G
loba
l (m
s) 1
2
3
4
5
0
1000
2000
3000
4000
5000
0,25 0,50 0,75 1,00
RootSet
B. L
ocal
(ms)
1
2
3
4
5
0%
5%
10%
15%
20%
25%
1 2 3 4 5
Número de estações-base
Dife
renç
a Te
mpo
B. G
loba
l e
B.
Loca
l
25%
50%
75%
100%
25
Arcos modificados
0
10000
20000
30000
40000
50000
60000
25% 50% 75% 100%
% arcos afetados
Atua
lizaç
ão B
S-E
(ms)
2
3
4
5
0
10000
20000
30000
40000
50000
60000
25% 50% 75% 100%
% arcos afetados
Atua
lizaç
ão B
S-D
(ms)
2
3
4
5
0
2000
4000
6000
8000
10000
25% 50% 75% 100%
% arcos afetados
Atua
lizaç
ão S
S-E
(ms)
2
3
4
5
0
2000
4000
6000
8000
10000
25% 50% 75% 100%
% arcos afetados
Atua
lizaç
ão S
S-D
(ms)
2
3
4
5
26
Desempenho
0
2000
4000
6000
8000
10000
12000
14000
16000
2 3 4 5
Número de estações-base
Tem
po (m
s)
SS-E
SS-D
0
2000040000
60000
80000100000
120000
140000160000
180000
2 3 4 5
Número de estações-base
Tem
po (m
s)
BS-E
BS-D
0
500
1000
1500
2000
2500
1 2 3 4 5
Número de estações-base
Tem
po (m
s)
B. Local
B. Global
27
Qualidade da Solução
0%
5%
10%
15%
20%
25%
30%
25% 50% 75%
RootSet
Erro
Méd
io 34
5
0%
5%
10%
15%
20%
25%
30%
3 4 5
Número de estações-base
Erro
Méd
io 25%50%
75%
28
Conclusão
• RootSet é um parâmetro importante do modelo
• Partições devem minimizar o comprimento da borda
• Modelo apropriado para o uso de algoritmos de busca em grafos dinâmicos
• Políticas de interpolação podem ser consideradas, para melhorar a qualidade da solução
