Aula4d

Interação entre roteamento e repasse algoritmo de roteamento tabela de repasse local valor cab. enlace saída
0100
0101
0111
1001

3
2
2
1

valor no cabeçalho do pacote de chegada

1

0111

3 2

slide 67

© 2010 Pearson Prentice Hall. Todos os direitos reservados.

Abstração de grafo
5
2

u

2
1

Grafo: G = (N,E)

v

x

3

w
3

1

5

z

1

y

2

N = conjunto de roteadores = { u, v, w, x, y, z }
E = conjunto de enlaces = { (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
Comentário: Abstração de grafo é útil em outros contextos de rede
Exemplo: P2P, onde N é conj. de pares e E é conj. de conexões TCP

slide 68

© 2010 Pearson Prentice Hall. Todos os direitos reservados.

1

Abstração de grafo: custos
5
2

u

v
2

1

x

• c(x,x’) = custo do enlace (x,x’)
3

w
3

1

z

1

y

- p. e., c(w,z) = 5

5

• custo poderia ser sempre 1, ou inversamente relacionado à largura ou inversamente relacionado ao congestionamento 2

Custo do caminho (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)
Pergunta: Qual é o caminho de menor custo entre u e z?

algoritmo de roteamento: algoritmo que encontra o caminho de menor custo slide 69

© 2010 Pearson Prentice Hall. Todos os direitos reservados.

Classificação do algoritmo de roteamento informação global ou descentralizada? Estático ou dinâmico?

global: todos os roteadores têm topologia completa, informação de custo do enlace algoritmos de “estado do enlace” descentralizada: roteador conhece vizinhos conectados fisicamente, custos de enlace para vizinhos processo de computação iterativo, troca de informações com vizinhos algoritmos de “vetor de distância” slide 70

estático: rotas mudam lentamente com o tempo dinâmico: rotas mudam mais rapidamente atualização periódica em resposta a mudanças no custo do enlace © 2010 Pearson Prentice Hall. Todos os direitos reservados.

2

Algoritmo de roteamento de estado do enlace notação: c(x,y): custo do enlace

algoritmo de Dijkstra

slide 71

nova topologia, custos de