Um sistema distribuído para busca de caminhos
em grafos dinâmicos
Marcelo Luís Vinagreiro
Orientador: Prof. Alfredo Goldman
1
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
2
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.
3
Arquitetura Proposta
Modelagem
8
• Bordas
13
14
6
9
10
7
11
4
5
12
3
2
1
EA
16
15
17
18
19
EB
• 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 }
4
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
NSS >= 1 : o número de SSs
BS = { BSi | 1  i  NEB }
SS = { SSi | 1  i  NSB }
Onde: SS  BS
5
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:
RootSet(Gi): { B1, B2, B3, B4 }
RootWeightSet(Gi):
B1
1
0
8
B3
5
B2
I1
2
8
B4
Peers
X->Y
Y->X
B1-B2
1
8
B1-B3
0
-
B1-B4
3
-
B2-B4
2
-
BSi
6
Forward Tree de RSi – FT(RSi)
RS3
RS2
3
RS1
10
2
8
RS5
0
RS2
8
2
2
X
2
K
8
RS4
Z
RS1
3
RS3
2
0
Z
RS4
Forward Tree (RS2)
RS5
7
Model Tree – MT(Rx)
8
Roteamento adaptativo através de árvores dinâmicas
Processamento 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
RootWeightSetstateIdt, SSk atualiza árvores MTstateId(t)
E envia msg Received_RwsetstateId, informando a Bt com uma
o recebimento de RootWeightSetstateIdt
9
Busca de caminhos
A. Seja uma requisição de caminho de X a Y enviada à estaçãobase 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).
10
Procedimento de Busca
Formado por 4 procedimentos principais:
•
PerformBSPathSearch: executado em BSx;
•
PerformInterPath: executado em BSx;
•
PerformSSPathSearch: executado em SSj
•
PerformPathInForwardTrees: executado em BSy;
11
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
12
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) )
13
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  Resp
else
/* 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
14
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}
15
Busca em SBj
else
Seja 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
16
Busca em BSY
Procedure FindPathInForwardTrees(Y, stateId)
RSWeightSetToY := 
for each árvore FTstateId(Ri) do
if Y  FTstateId(Ri) then
RSWeightSetToY := RSWeightSetToY  {Ri, Weight(Ri,Y)}
else
RSWeightSetToY := RSWeightSetToY  {Ri, }
return RSWeightSetToY
End Procedure
17
Atualização do sistema
K+1
K
EB1=EBc
(I)
Update_Rset(k+1)
EB 2
Commit_Rset(k+1)
(I)
Update_Rset(k+1)
EB 3
Received_Rset(k+1)
Received_Rset(k+1)
Commit_Rset(k+1)
(I)
18
19
BSAgents
Ação
Agente
Perform_Path_Search
BaseServerRequestAgent
Find_RsetToY_Values
FindRset2YAgent
Rqst_Sub_Path
RequestSubPathAgent
Update_Rset
UpdateRsetAgent
Update_Global_State
UpdateTransactionAgent
Commit_Rset
CommitRsetAgent
Update_Link_State
UpdateDataLinkAgent
Base Server
20
SSAgents
Ação
Agente
Find_Inter_Path
PerformSSPathAgent
Update_Rwset
Commit_Rset
UpdateRwsetAgent
CommitRsetAgent
Search Server
21
Influência do RootSet – Atualização
500000
400000
2
300000
3
4
200000
5
100000
Atualização SS-D (ms)
Atualização SS-E (ms)
500000
400000
2
300000
3
4
200000
5
100000
0
0
25%
50%
75%
25%
100%
50%
RootSet
100%
300000
250000
200000
2
3
150000
4
100000
5
50000
0
Atualização BS-D (ms)
300000
Atualização BS-E (ms)
75%
RootSet
250000
200000
2
3
150000
4
100000
5
50000
0
25%
50%
75%
RootSet
100%
25%
50%
75%
100%
RootSet
22
Influência do RootSet – Atualização (cont)
100%
40%
25%
30%
50%
75%
20%
100%
10%
0%
Comparação SS-D/SS-E
Comparação BS-D / BS-E
50%
80%
25%
60%
50%
75%
40%
100%
20%
0%
2
3
4
Número de estações-base
5
2
3
4
5
Número de estações-base
23
Influência do RootSet – Buscas
5000
5000
4000
1
2
3000
3
2000
4
5
B. Local (ms)
B. Global (ms)
4000
1
3
2000
1000
0
0
0,50
0,75
1,00
0,25
RootSet
Diferença Tempo B. Global e B.
Local
4
5
1000
0,25
2
3000
0,50
0,75
1,00
RootSet
25%
20%
25%
15%
50%
75%
10%
100%
5%
0%
1
2
3
4
5
Número de estações-base
24
Arcos modificados
60000
50000
40000
2
3
30000
4
20000
5
10000
Atualização BS-D (ms)
Atualização BS-E (ms)
60000
0
50000
40000
2
3
30000
4
20000
5
10000
0
25%
50%
75%
100%
25%
% arcos afetados
75%
100%
% arcos afetados
10000
8000
2
6000
3
4
4000
5
2000
0
Atualização SS-D (ms)
10000
Atualização SS-E (ms)
50%
8000
2
6000
3
4
4000
5
2000
0
25%
50%
75%
% arcos afetados
100%
25%
50%
75%
100%
% arcos afetados
25
16000
180000
14000
160000
12000
140000
10000
SS-E
8000
SS-D
6000
Tempo (ms)
Tempo (ms)
Desempenho
120000
100000
BS-E
80000
BS-D
60000
4000
40000
2000
20000
0
0
2
3
4
5
2
Número de estações-base
3
4
5
Número de estações-base
2500
Tempo (ms)
2000
1500
B. Local
B. Global
1000
500
0
1
2
3
4
5
Número de estações-base
26
30%
30%
25%
25%
20%
3
15%
4
5
10%
5%
Erro Médio
Erro Médio
Qualidade da Solução
20%
25%
15%
50%
75%
10%
5%
0%
0%
25%
50%
RootSet
75%
3
4
5
Número de estações-base
27
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
28