Camada de Rede - fenix.tecnico.ulisboa.pt · • execução de algoritmos/protocolos de encaminhamento (RIP, OSPF, BGP) • comutação de datagramas das ligações de entrada para

Redes de Computadores 4.1

Camada de Rede

• Serviços da camada de rede– Circuitos virtuais

– Datagramas

• Funcionamento de um encaminhador (“router”)

• Camada de rede na Internet: o protocolo IP

• Princípios de encaminhamento: selecção de um caminho

• Encaminhamento hierárquico

• Encaminhamento na Internet– intra domínio

– inter domínio

• Encaminhamento “multicast”

• Outros aspectos da camada de rede na Internet: ICMP, DHCP, NAT, IPv6

• Mobilidade


Funções da camada de redeObjectivo:

transporte de pacotes do computador origem ao computador destino

– os protocolos da camada de rede existem em todos os computadores terminais e todos os nós intermédios

Funções importantes

• determinação do caminho: rota seguida pelos pacotes da origem ao destino. Algoritmos de encaminhamento

• comutação: copiar os pacotes de uma entrada do nó (“router”) para a saída apropriada

• estabelecimento de chamada: algumas arquitecturas exigem o estabelecimento de uma ligação entre origem e destino antes da comunicação de dados (“call setup”)

networkdata linkphysical








applicationtransportnetworkdata linkphysical



Modelo de serviços da camada de rede

Qual deve ser o modelo de serviçosno transporte de pacotes da origem para o destino?

• Largura de banda garantida?

• Preservação do intervalo de tempo entre pacotes (eliminação do “jitter”)?

• Entrega sem perdas?

• Entrega na ordem?

• Envio de informação de congestionamento para a fonte?

? ??Circuito Virtual

oudatagrama?

Característica maisimportante do serviço

prestado pela camada de rede:


Circuitos Virtuais

• Estabelecimento de um caminho (chamada) antes da transmissão de dados e correspondente acção de desligar cada chamada.

• Cada pacote transporta o identificador do circuito virtual (não inclui necessariamente a identificação do computador destino)

• Cada nó, no caminho origem-destino, mantém o estado de cada ligação

• Para cada circuito virtual podem ser reservados recursos ao longo do caminho, incluindo largura de banda e memória nos nós

o caminho entre origem e destino “assemelha-se” a um circuito telefónico tradicional


Circuitos Virtuais12 22 32

1 23

Número do VC

Número dainterface

Interface de entrada # do VC de entrada Interface de saída # do VC de saída

1 12 3 222 63 1 18 3 7 2 171 97 3 87… … … …

Tabela de expedição

Os Routers guardam informação do estado de cada ligação


Protocolos de sinalização em circuitos virtuais

• Protocolos usados para estabelecer, manter e terminar um circuito virtual

– ATM, frame-relay, X.25



1. Initiate call 2. incoming call

3. Accept call4. Call connected5. Data flow begins 6. Receive data


Redes de datagramas (Internet)

• Não há estabelecimento de ligação ao nível da camada de rede

• Os nós não guardam informação sobre ligações extremo a extremo– o conceito de ligação não existe ao nível da camada de rede

• Os pacotes são tipicamente encaminhados pelo identificador do computador de destino

– pacotes entre o mesmo par origem-destino podem seguir caminhos diferentes



1. Send data 2. Receive data


Rede de datagramas

Endereços de Destino Interface de saída

11001000 00010111 00010000 00000000até 0

11001000 00010111 00010111 11111111

11001000 00010111 00011000 00000000até 1

11001000 00010111 00011000 11111111

11001000 00010111 00011001 00000000até 2

11001000 00010111 00011111 11111111

Outros 3



Rede de datagramas

Prefixo Interface de saída11001000 00010111 00010 0 11001000 00010111 00011000 111001000 00010111 00011 2

Outros 3

11001000 00010111 00011000 10101010

Exemplos:

11001000 00010111 00010110 10100001 Qual a interface de saída para os endereços?

O maior prefixo do endereço na tabela determina a interface de saída


Modelos de serviços na camada de rede

Arquitecturade rede

Internet

ATM

ATM

ATM

ATM

Modelode serviço

best effort

CBR

VBR

ABR

UBR

Banda

nenhuma

taxaconstantetaxagarantidataxa mínimanenhuma

Perdas

não

sim

sim

não

não

Ordem

não

sim

sim

sim

sim

Tempo

não

sim

sim

não

não

Informação deCongestionamento

não

não aplicável

não aplicável

sim

não

Garantia ?

• Para a Internet estão a ser definidos novos modelos de serviços: Intserv, Diffserv


Datagramas versus circuitos virtuais

Internet• troca de dados entre computadores

– serviço “elástico”; a eliminação do “jitter” não era importante

• terminais “inteligentes” (computadores)– os terminais podem adaptar-se,

implementar controlo de erros e recuperar de situações de erro

– o interior da rede pode ser simples reservando a complexidade para os extremos

• tipos diferentes de ligações físicas com– diferentes características

– dificuladade em fornecer um serviço uniforme

ATM• evoluiu a partir da rede

telefónica

• conversação humana: – eliminação do “jitter” muito

importante, grandes exigências de fiabilidade

– necessidade de garantia de qualidade de serviço

• sistemas terminais “estúpidos”– aparelho de telefone tradicional

– complexidade introduzida no interior da rede


Camada de Rede


– Datagramas






– inter domínio



• Mobilidade


Arquitectura de um nó (“router”)

Duas funções fundamentais:• execução de algoritmos/protocolos de encaminhamento (RIP, OSPF, BGP)

• comutação de datagramas das ligações de entrada para as ligações de saída


Funções dos portos de entrada

Comutação descentralizada:• dado o endereço de destino de um datagrama, determinar

o porto de saída consultando a tabela de encaminhamento na memória local

• objectivo: completar todas as tarefas ao ritmo de chegada da ligação

• se os datagramas chegam mais depressa que o ritmo de envio para a malha de comutação existe um fila de espera

Camada Física:nível do bit

Camada de ligação de dados:

e.g., Ethernet


Fila de espera no porto de entrada

• Se a malha de comutação é mais lenta que os portos de entrada combinados podem surgir filas de espera na entrada

• Bloqueio “Head-of-the-Line (HOL)”: o datagrama na primeira posição da fila impede outros de serem encaminhados para uma saída

• surgem atrasos e perdas


Funções dos portos de saída

• É necessário o armazenamento (“Buffering”) quando os datagramas chegam da malha a um ritmo maior que a largura de banda de saída

• Disciplina de serviço: escolhe o datagrama, de entre os que estão na fila, que é transmitido a seguir (FCFS, WFQ)


Fila de espera no porto de saída

• A fila de espera do porto de saída pode introduzir Atraso e Perdas


Arquitecturas de comutação


Comutação através da memória“routers” de primeira geração:

• cada pacote é copiado para a memória pela única CPU do sistema

• velocidade limitada pela largura de banda de acesso à memória (2 passagens pelo “bus” do sistema por datagrama

InputPort

OutputPort

Memory

System Bus

“routers” modernos:

• o processador de entrada consulta a tabela e copia para memória partilhada (Exemplo: Cisco Catalyst 8500).


Comutação através de um “bus”

• Cada datagrama é transmitido da memória do porto de entrada para a memória do porto de saída através de um “bus”

• velocidade de comutação limitada pela largura de banda do “bus”

• Exemplo: Cisco 1900 (“bus” de 1 Gbps) -suficiente para o acesso de médias empresas àInternet


Comutação através de uma malha

• Ultrapassa as limitações impostas pelo “bus”

• Redes inicialmente propostas para interligar processadores num ambiente multiprocessador, redes de Banyan

• estruturas avançadas: fragmentação de datagramas em pacotes de tamanho fixo dentro da malha de comutação.

• Exemplo Cisco 12000: pode comutar dezenas de Gbps através da sua malha de comutação


Camada de Rede


– Datagramas






– inter domínio



• Mobilidade


Camada de rede na Internet

Tabela deencaminhamento

Funções da camada de rede:

Protocolos de encaminhamento•sel. de caminhos•RIP, OSPF, BGP

Protocolo IP•endereçamento•formato dos datagramas•manuseamento

Protocolo ICMP •erros•sinalização

Camada de transporte: TCP, UDP

Camada de ligação de dados

Camada física

Camadade rede


Endereçamento IP

• Endereço IP: identificador de 32 bits para uma “interface” de um nó(“router”) ou computador

• “interface”: ligação entre um computador/nó e o canal físico

– tipicamente um nó tem várias “interfaces”

– um computador tem muitas vezes apenas uma “interface”, mas pode ter mais

– os endereços IP estão associados às “interfaces”

223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2223.1.3.1

223.1.3.27

223.1.1.1 = 11011111 00000001 00000001 00000001

223 1 11


Endereçamento IP

• Endereço IP:– parte de rede (bits de maior

ordem) - “network part”

– parte de computador (bits de menor ordem) - “host part”

• Uma rede do ponto de vista do protocolo IP é

– um conjunto de “interfaces”com o mesmo número da parte de rede

• podem comunicar entre elas sem intervenção de um nóencaminhador (“router”)

223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2223.1.3.1

223.1.3.27

Sistema constituído por 3 redes IP (para os endereços IP começados por 223, os primeiros 24 bits são o endereço de rede)

LAN


Endereçamento IP

223.1.1.1

223.1.1.3

223.1.1.4

223.1.2.2223.1.2.1

223.1.2.6

223.1.3.2223.1.3.1

223.1.3.27

223.1.1.2

223.1.7.2

223.1.7.1223.1.8.2223.1.8.1

223.1.9.1

223.1.9.2

Sistema interligadoconstituído por 6 redes IP


Endereçamento IP

0 network host

10 network host

110 network host

1110 multicast address

A

B

C

D

classe1.0.0.0 a127.255.255.255

128.0.0.0 a191.255.255.255

192.0.0.0 a223.255.255.255

224.0.0.0 a239.255.255.255

32 bits

Endereçamento em classes (“class-full”):


Endereçamento IP

• Endereçamento em classes: – uso ineficiente do espaço de endereçamento

– e.g., a atribuição de uma rede de classe B reserva espaço para cerca de 65000 computadores

• CIDR: “Classless InterDomain Routing”– a parte de rede do endereço tem comprimento arbitrário

– formato do endereço: a.b.c.d/x, onde x é o número de bits da parte de rede do endereço

11001000 00010111 00010000 00000000

networkpart

hostpart

200.23.16.0/23


Obtenção de endereços IP

Redes (“network portion”):• atribuição de parte do espaço de endereçamento do fornecedor do

serviço Internet (ISP):

Bloco do ISP 11001000 00010111 00010000 00000000 200.23.16.0/20

Organização 0 11001000 00010111 00010000 00000000 200.23.16.0/23

Organização 1 11001000 00010111 00010010 00000000 200.23.18.0/23

Organização 2 11001000 00010111 00010100 00000000 200.23.20.0/23 ... ….. …. ….

Organização 7 11001000 00010111 00011110 00000000 200.23.30.0/23


Endereçamento hierárquico

“Send me anythingwith addresses beginning 200.23.16.0/20”

200.23.16.0/23

200.23.18.0/23

200.23.30.0/23

Fly-By-Night-ISP

Organization 0

Organization 7Internet

Organization 1

ISPs-R-Us“Send me anythingwith addresses beginning 199.31.0.0/16”

200.23.20.0/23Organization 2

...

...

O endereçamento hierárquico permite a publicação eficiente da informação de encaminhamento:


Endereçamento hierárquico

O fornecedor de serviços ISPs-R-Us publica um caminho específicopara “Organization 1”

“Send me anythingwith addresses beginning 200.23.16.0/20”

200.23.16.0/23

200.23.18.0/23

200.23.30.0/23

Fly-By-Night-ISP

Organization 0

Organization 7Internet

Organization 1

ISPs-R-Us“Send me anythingwith addresses beginning 199.31.0.0/16or 200.23.18.0/23”

200.23.20.0/23Organization 2

...

...


Obtenção de blocos de endereços

A instituição ICANN “Internet Corporation for Assigned Names and Numbers” é responsável por

– atribuir endereços

– gerir o “Domain Name System - DNS”

– atribuir nomes de domínios e gerir conflitos

• Actualmente há cinco instituições regionais:– AfriNIC “African Network Information Center”

– APNIC “Asia Pacific Network Information Center”

– ARIN “American Registry for Internet Number”

– LACNIC “Latin American and Caribbean Internet Addresses Registry”

– RIPE NCC “Reseaux IP Europeans”


Datagrama IP: da origem ao destino

miscfields

sourceIP addr

destIP addr data

datagrama IP:

223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2223.1.3.1

223.1.3.27

A

B

E

• No que respeita aos campos de endereço origem e destino o datagrama não é alterado desde a origem ao destino

Dest. Net. next router Nhops

223.1.1 1223.1.2 223.1.1.4 2223.1.3 223.1.1.4 2

Tabela de encaminhamento em A



223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2223.1.3.1

223.1.3.27

A

B

E

Da origem A (223.1.1.1)

ao destino B (223.1.1.3)

• consulta a tabela de encaminhamento com a parte de rede do endereço de B

– B está na mesma rede que A

• a camada de ligação de dados envia, dentro da sua trama, o datagrama directamente a B


223.1.1 1223.1.2 223.1.1.4 2223.1.3 223.1.1.4 2

miscfields 223.1.1.1 223.1.1.3 data



223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2223.1.3.1

223.1.3.27

A

B

E


223.1.1 1223.1.2 223.1.1.4 2223.1.3 223.1.1.4 2

Da origem A (223.1.1.1)

ao destino E (223.1.2.2)

• consulta a tabela de encaminhamento com a parte de rede do endereço de E

– E não está na mesma rede que A

– caminho para E passa pelo nó (“router”) 223.1.1.4

• camada de ligação de dados envia trama para 223.1.1.4 contendo o datagrama

• datagram chega a 223.1.1.4

• continua…..

miscfields 223.1.1.1 223.1.2.2 data



223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2223.1.3.1

223.1.3.27

A

B

E

Do “router” 223.1.1.4

ao destino E (223.1.2.2)

• consulta a tabela de encaminhamento com a parte de rede do endereço de E

– E está na mesma rede que a “interface”223.1.2.9 do “router”

• camada de ligação de dados associada à “interface” 223.1.2.9 do “router”envia trama para 223.1.2.2 contendo o datagrama

• datagrama chega a 223.1.2.2

miscfields 223.1.1.1 223.1.2.2 data network router Nhops interface

223.1.1 - 1 223.1.1.4

223.1.2 - 1 223.1.2.9

223.1.3 - 1 223.1.3.27

Dest. next


Formato do datagrama IP

ver length

32 bits

data (variable length,typically a TCP

or UDP segment)

16-bit identifier

Internetchecksum

time tolive

32 bit source IP address

IP protocol versionnumber

header length(bytes)

max numberremaining hops

(decremented at each router)

forfragmentation/reassembly

total datagramlength (bytes)

upper layer protocolto deliver payload to

head.len

type ofservice

“type” of data flgsfragment

offsetupperlayer

32 bit destination IP address

Options (if any) E.g. timestamp,record routetaken, specifylist of routers to visit.


Fragmentação e reagrupamento em IPv4

• As ligações da rede têm um tamanho máximo para as tramas da camada de ligação de dados (MTU “max. transfer size”)

– em ligações diferentes há diferentes MTUs

• datagramas IP grandes podem ser divididos (“fragmentados”) dentro da rede

– um datagrama passa a ser vários datagramas

– são reagrupados apenas no destino

– existem campos no cabeçalho IP que são usados para identificar e ordenar os fragmentos

fragmentação: in: 1 datagramaout: 3 datagramas

reagrupamento



ver length

32 bits

data

16-bit identifier

Internetchecksum

time tolive

32 bit source IP address

head.len

type ofservice

flagsfragment

offsetupperlayer

32 bit destination IP address

Options (if any)

0xx Reserved

x0x May Fragment

x1x Do Not Fragment

xx0 Last Fragment

xx1 More Fragments (fragflag)

This 13-bit field indicates the position of a particular fragment's data in relation to the first byte of data (offset 0).

This 16-bit field contains a unique number used to identify the frame and any associated fragments for reassembly



ID=x

offset=0

fragflag=0

length=4000

ID=x

offset=0

fragflag=1

length=1500

ID=x

offset=185

fragflag=1

length=1500

ID=x

offset=370

fragflag=0

length=1040

Um datagrama transforma-se em vários datagramas mais pequenos


Camada de Rede


– Datagramas






– inter domínio



• Mobilidade


Encaminhamento

Representação da rede por grafos:

• os encaminhadores (“routers”) são os nós do grafo

• as ligações físicas são os arcos do grafo

– custo da ligação: atraso, distância em km, nível de congestionamento

Objectivo: determinar “bons”caminhos na rede (sequências de

nós) entre a origem e o destino

A

ED

CB

F

2

2

13

1

1

2

53

5

Caminho “bom”:– tipicamente o caminho de menor

custo


Classificação dos algoritmos de encaminhamentoInformação global ou

descentralizada?Global:

• todos os nós conhecem completamente a topologia e o custo das ligações

• algoritmos de estado das ligações(“link state” algorithms)

Descentralizada:

• cada nó conhece os que lhe estão ligados directamente e os custos associados a essas ligações

• processo de cálculo iterativo por troca de informação com os vizinhos

• algoritmos de vector de distâncias(“distance vector” algorithms)

Estáticos ou dinâmicos?Estáticos:

• os caminhos mudam lentamente no tempo

Dinâmicos:

• os caminhos mudam rapidamente– modificação periódica

– modificação sempre que se alterem os custos das ligações ou a topologia


Um algoritmo de encaminhamento “Link -State”

Algoritmo de Dijkstra• topologia da rede e custos das

ligações conhecidos por todos os nós– consegue-se através da difusão da

informação sobre o estado das ligações (“link state broadcast”)

– todos os nós têm a mesma informação

• calcula o menor custo desde um nó(fonte) até cada um dos restantes

– produz a tabela de encaminhamentopara esse nó

• iterativo: depois de k iterações, conhece o menor custo para k destinos

Notação:

• c(i,j): custo da ligação do nó ipara o nó j; o custo é infinito se os nós não são vizinhos

• D(v): valor actual do custo da origem para o destino v

• p(v): penúltimo nó no caminho da origem para o nó v

• N: conjunto de nós para os quais já se conhece o caminho de menor custo


Passo012345

NA

ADADE

ADEBADEBC

ADEBCF

D(B),p(B)2,A 2,A 2,A

D(C),p(C)5,A 4,D 3,E 3,E

D(D),p(D)1,A

D(E),p(E)infinito

2,D

D(F),p(F)infinito infinito

4,E 4,E 4,E

Algoritmo de Dijkstra: exemplo

A

ED

CB

F

2

2

13

1

1

2

53

5


Algoritmo de Dijkstra

1 Initialization:2 N = {A} 3 for all nodes v 4 if v adjacent to A 5 then D(v) = c(A,v) 6 else D(v) = infty 7 8 Loop9 find w not in N such that D(w) is a minimum 10 add w to N 11 update D(v) for all v adjacent to w and not in N: 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v */ 15 until all nodes in N


Algoritmo de Dijkstra: discussãoComplexidade do algoritmo: n nós

• em cada iteração: é necessário avaliar todos os nós, w, que não estão em N

• n(n+1)/2 comparações: O(n2)

• em implementações mais eficientes: O(n logn)

O algoritmo pode conduzir a oscilações:

• e.g., se custo da ligação = tráfego transportado

A

D

C

B1 1+e

e0

e

1 1

0 0

A

D

C

B2+e 0

001+e 1

A

D

C

B0 2+e

1+e10 0

A

D

C

B2+e 0

e01+e 1

initially… recompute

routing… recompute … recompute


Algoritmo de vector de distâncias - DV

iterativo:• actualizações contínuas até que não haja troca de informação entre nós

• termina automaticamente

assíncrono:• cada nó actualiza a sua informação em instantes independentes dos outros nós

distribuído:

• cada nó comunica apenas com os seus vizinhos directos

Estrutura das tabelas de distância• existe uma tabela em cada nó

• uma linha para cada nó destino

• uma coluna para cada nó vizinho directo

• exemplo: no nó X, para o nó destino Y via nó vizinho Z:

D (Y,Z)X

distância de X aY, via Z

c(X,Z) + min {D (Y,w)}Z

w

=

=


Exemplo de tabela de distâncias

A

E D

CB7

8

1

2

1

2

D ()

A

B

C

D

A

1

7

6

4

B

14

8

9

11

D

5

5

4

2

ECusto ao nó destino via

dest

ino

D (C,D)E

c(E,D) + min {D (C,w)}D

w== 2+2 = 4

D (A,D)E

c(E,D) + min {D (A,w)}D

w== 2+3 = 5

D (A,B)E

c(E,B) + min {D (A,w)}B

w== 8+6 = 14

loop!

loop!



D ()

A

B

C

D

A

1

7

6

4

B

14

8

9

11

D

5

5

4

2

ECusto ao nó destino via

dest

ino

A

B

C

D

A,1

D,5

D,4

D,2

Ligação de saída, custo

dest

ino

Tabela de distâncias Tabela de expedição

Nó E

A

E D

CB7

8

1

2

1

2


Funcionamento do algoritmo de vector de distâncias

espera por mudanças no custo de uma ligação local ou por mensagem de um vizinho

recalcula tabela de distâncias

se algum caminho de menor custo para um nó destino mudou, informa vizinhos

Em cada nó:

Iterativo

Assíncrono

Distribuído


Funcionamento do algoritmo de vector de distâncias

1 Initialization: 2 for all adjacent nodes V: 3 D (*,V) = infty /* the * operator means "for all rows" */ 4 D (V,V) = c(X,V) 5 for all destinations, y 6 send min D (y,w) to each neighbor /* w over all X's neighbors */

XX

Xw

Em todos os nós, X:


Funcionamento do algoritmo de vector de distâncias8 loop9 wait (until I see a link cost change to neighbor V 10 or until I receive update from neighbor V) 11 12 if (c(X,V) changes by d) 13 /* change cost to all dest's via neighbor v by d */14 /* note: d could be positive or negative */ 15 for all destinations y: DX(y,V) = DX(y,V) + d 16 17 else if (update received from V with destination Y) 18 /* shortest path from V to some Y has changed */19 /* V has sent a new value for its minwDV (Y,w) */ 20 /* call this received new value is "newval" */ 21 for the single destination y: DX(Y,V) = c(X,V) + newval 22 23 if we have a new minwDX(Y,w) for any destination Y 24 send new value of minwDX(Y,w) to all neighbors 25 26 forever


Vector de distâncias (DV): Exemplo

X Z

12

7

Y

D (Y,Z)X

c(X,Z) + min {D (Y,w)}w=

= 7+1 = 8

Z

D (Z,Y)X

c(X,Y) + min {D (Z,w)}w=

= 2+1 = 3

Y


Vector de distâncias (DV): Exemplo

X Z

12

7

Y


Vector de distâncias: alteração do custo de ligação

Alteração do custo de uma ligação:• nó detecta a alteração

• racalcula a tabela de distâncias

• se o custo de um caminho de menor custo se altera, informa os vizinhos

X Z

14

50

Y1

algoritmotermina“boas

notícias propagam-sedepressa”


Vector de distâncias: alteração do custo de ligação

Alteração no custo de uma ligação:• boas notícias propagam-se depressa

• más notícias propagam-se devagar -problema de “contagem para infinito”!

X Z

14

50

Y60

algoritmocontinua


Vector de distâncias: “poisoned reverse”

Se Z encaminha para X via Y:• Z diz a Y que a sua distância a X é infinito

(asssim Y nunca encaminha para X via Z)

• Será que isto resolve completamente o problema da “contagem para infinito”?

X Z

14

50

Y60

algoritmotermina


Comparação dos algoritmos LS e DV

Complexidade das mensagens• LS: com n nós e E ligações, cada nó

envia O(nE) mensagens

• DV: troca de mensagens apenas entre nós vizinhos

Velocidade de convergência• LS: o algoritmo (em cada nó)

converge em O(n2) comparações– pode conduzir a oscilações

• DV: tempo de convergência varia– podem criar-se circuitos fechados

– problema da contagem para infinito

Robustez: mau funcionamento dos nós

• LS:– cada nó pode difundir erradamente os

custos das ligações

– cada nó calcula a sua tabela de expedição

• DV:– cada nó pode difundir erradamente o

custo de um caminho

– a tabela de cada nó é usada pelos restantes

• este erro propaga-se a toda a rede


Camada de Rede


– Datagramas






– inter domínio



• Mobilidade


Encaminhamento hierárquico

Escala (milhões de destinos)• não se podem memorizar todos em

cada tabela de encaminhamento!

• A troca de informação para a construção das tabelas esgotaria a capacidade da rede!

Autonomia administrativa• internet = rede de redes

• cada instituição/organização/empresa tem o direito de usar mecanismos de encaminhamento próprios

Até aqui considerámos que:

• todos os nós são idênticos

• a rede é “plana”

Pelo menos dois problemas:


Encaminhamento hierárquico

Organização de nós em regiões autónomas, “autonomous systems” (AS)

• nós especiais em cada AS

• utilizam um protocolo de encaminhamento intra-AS com todos os nós desse AS

• são responsáveis pelo encaminhamento para destinos fora desse AS– utilizam um protocolo de encaminhamento inter-AS com os restantes nós “gateway”

Nós “gateway”

utilizam o mesmo protocolo de encaminhamento “intra-AS”Nós no mesmo AS

Nós em diferentes ASpodem utilizar diferentes protocolos de encaminhamento intra-AS


Encaminhamento Intra-AS e Inter-AS“Gateways”:

- usam encaminhamento inter-AS entre eles;- usam encaminhamento intra-AS com os nós do seu AS.

encaminhamentointer-AS, intra-ASna “gateway” A.c

Camada de rede


Camada física

a

b

b

aaC

A

Bd

A.a

A.c

C.bB.a

cb

c


Encaminhamento Intra-AS e Inter-AS

Host h2

a

b

b

aaC

A

Bd c

A.a

A.c

C.bB.a

cb

Hosth1

Encamin. Intra-AS dentro do AS A

Encamin.Inter-ASentre A e B

Encamin. Intra-ASdentro do AS B

• Veremos adiante protocolos de encaminhamento intra-AS (RIP, OSPF, IGRP) e inter-AS (BGP) usados na Internet


Camada de Rede


– Datagramas






– inter domínio



• Mobilidade


Encaminhamento na Internet

• A Internet é constituída por Sistemas Autónomos “Autonomous Systems” (AS) interligados entre si.

• Existem 2 níveis de encaminhamento: – Intra-AS: cada administrador é responsável pela escolha do protocolo usado

– Inter-AS: protocolo único


Hierarquia de AS’s na Internet

Nós fronteira Inter-AS (“exterior gateway”)

Nós interiores Intra-AS


Encaminhamento Intra-AS

• Conhecidos como “Interior Gateway Protocols (IGP)”

• IGP’s mais comuns:

– RIP: “Routing Information Protocol” (2, RFC 2453 – Nov. 1998)

– OSPF: “Open Shortest Path First” (v2, RFC 2328 – Abril 1998)

– IGRP: “Interior Gateway Routing Protocol” (Cisco propr.)


RIP (“Routing Information Protocol”)

• Algoritmo de vector de distâncias

• Incluído na distribuição de BSD-UNIX, 1982

• Métrica de distância: # de saltos (max = 15 saltos)

• Vectores de distância: trocados de 30 em 30 segundos via “Response Message” (também chamada mensagem de anúncio, “advertisement”)

• Cada anúncio: caminhos até um máximo de 25 destinos


RIP (“Routing Information Protocol”)

Destination Network Next Router Num. of hops to dest.w A 2y B 2z B 7x -- 1…. …. ....

w x y

z

A

C

D B

Tabela de encaminhamento em D

. . .

. . .

A 5


RIP: falha de uma ligação

Se não forem ouvidas mensagens de anúncio (“advertisement”) num período de 180s. da parte de um vizinho ele é declarado inexistente

1. caminhos que incluam esse vizinho são retirados da tabela

2. são enviadas mensagens de anúncio aos restantes vizinhos

3. os vizinhos por sua vez enviam novas mensagens se as suas tabelas tiverem mudado

– a falha é rapidamente propagada a toda a rede


RIP: processamento de tabelas

• As tabelas de encaminhamento RIP são geridas por um processo na camada de aplicação chamado route-d (“daemon”)

• As mensagens de anúncio são enviadas periodicamente usando o protocolo de transporte UDP (porto 520)


RIP: processamento de tabelasNó: giroflee.eurocom.fr

• Três redes classe C (LANs) directamente ligadas

• Nó para enviar todos os datagramas com endereços que não constam da tabela - “default router”

• Endereço multicast: 224.0.0.0

• Interface “Loopback”: 127.0.0.1

Destination Gateway Flags Ref Use Interface -------------------- -------------------- ----- ----- ------ ---------127.0.0.1 127.0.0.1 UH 0 26492 lo0 192.168.2. 192.168.2.5 U 2 13 fa0 193.55.114. 193.55.114.6 U 3 58503 le0 192.168.3. 192.168.3.5 U 2 25 qaa0 224.0.0.0 193.55.114.6 U 3 0 le0 default 193.55.114.129 UG 0 143454


OSPF (“Open Shortest Path First”)

• “open”: público

• Algoritmo de estado das ligações – disseminação de pacotes de estado das ligações (LS packet”)

– topologia conhecida em todos os nós

– cálculo dos caminhos usando o algoritmo de Dijkstra

• As mensagens OSPF de divulgação para toda a rede têm apenas uma entrada por cada nó vizinho

• As mensagens de divulgação são disseminadas por inundação

• O protocolo OSPF usa directamente o IP (protocolo 89).


Características do OSPF

• Segurança: todas as mensagens OSPF são autenticadas (para impedir acessos não autorizados)

• Múltiplos caminhos: caminhos de igual custo para o mesmo destino podem ser mantidos (RIP permite apenas um)

• Métricas diferentes para a mesma ligação dependendo do tipo de serviço (campo TOS dos datagramas)

– e.g., ligação satélite com custo baixo para tráfego de melhor esforço e custos elevados para tráfego de tempo real

• Multicast: suporte integrado de uni/multicast– OSPF multicast (MOSPF) usa a topologia construída para OSPF unicast

• Hierarquia: OSPF suporta hierarquia de nós em domínios de grande dimensão


Hierarquia no OSPF

• Hierarquia em dois níveis: area local, “backbone”.– anúncios do estado das ligações circulam apenas

numa área: cada nó tem conhecimento detalhado da área em que se insere;

– Cada nó conhece apenas a direcção para as redes noutras áreas.

• Nós de fronteira de área (“Area border routers”):conhecem as distâncias para as redes na sua área e anunciam para os restantes nós de fronteira de área.

• Nós do “backbone”: executam o protocolo OSPF apenas no conjunto dos nós do mesmo tipo.


Encaminhamento Inter-AS


BGP (“Border Gateway Protocol”)

• Standard de facto (4, RFC 4271 – Janeiro 2006 e também RFCs 1772, 1773)

• Protocolo de vector de caminhos (Path Vector Protocol):– Cada nó da fronteira de um AS (ou BGP router; ou exterior router) envia aos

seus pares, também nós de fronteira de outros AS’s, informação sobre a acessibilidade para as redes contidas nesse AS (colecção de prefixos CIDR);

– Os nós de fronteira vão coleccionando informação dos seus pares e preenchem as suas path vector tables, que especificam os caminhos (sequências de ASes para os vários destinos).



Exemplo: Suponhamos que X é um nó fronteira de AS1 e W é um nó fronteira de AS2. O nó Xenvia a W o caminho que conhece de AS1 para um destino Z (em que Z é uma rede e o caminho será uma lista de AS’s):

Path (AS1, Z) = AS1, ASi , ASj , ASk ,…, Z

• W pode ou não escolher o caminho anunciado com base em:

– Custo

– Conveniências comerciais/políticas

– Critérios técnicos: evitar caminhos fechados

• Se W aceitar o caminho comunicado por X, então anuncia aos vizinhos:

Path (AS2, Z) = AS2, Path (AS1, Z)

• Um nó pode controlar o tráfego que encaminha escolhendo os anúncios que faz:

– e.g., se não quer encaminhar tráfego para Y → não anuncia nenhum caminho para Y



• BGP – troca mensagens usando o protocolo TCP (porto 179)

• Mensagens BGP:– OPEN: inicia a ligação TCP e envia autenticação do emissor

– UPDATE: anúncio de caminhos

– KEEPALIVE: mantém uma ligação aberta na ausência de mensagens de UPDATE; usada para responder à mensagem OPEN

– NOTIFICATION: reporta erros em mensagens anteriores; usada para fechar uma ligação


Porquê diferentes protocolos Inter- e Intra-AS

Considerações de Escala:• Encaminhamento hierárquico poupa espaço nas tabelas de expedição e

economiza mensagens de actualização das condições da rede

Considerações políticas:• Inter-AS: as administrações dos domínios querem controlar como e

por onde o seu tráfego é encaminhado através da internet.

• Intra-AS: não têm em geral requisitos de natureza política

Considerações de desempenho:• Inter-AS: interesses políticos podem prevalecer

• Intra-AS: critérios técnicos de velocidade e optimização de recursos


Camada de Rede


– Datagramas






– inter domínio



• Mobilidade


Encaminhamento “multicast”• Multicast: entrega do mesmo pacote a um grupo de receptores

• A técnica Multicasting dá suporte, ao nível da camada de rede, a aplicações com múltiplos participantes: e.g., video on demand, whiteboard, interactive games, software distribution.

Múltiplas ligações ponto a ponto versus ligação “multicast”


Endereços de grupo

• Endereços de grupo m-cast atribuídos a todos os participantes no grupo

• A Internet usa endereços da classe D para m-cast(224.0.0.0 - 239.255.255.255)

• A distribuição de endereços m-cast é gerida pelo protocolo IGMP (“Internet Group Management Protocol”)


2 tipos de protocolos para “multicast”

• LAN-to-router– Internet Group Management Protocol (IGMP)

• router-to-router

IGMP

Rtr-2-rtr

– Core Based Trees (CBT)

– Source Based Trees

• Distance Vector Multicast Routing Protocol (DVMRP)

• Multicast Open Shortest Path First (MOSPF)

• Protocol Independent Multicast (PIM)


Protocolo IGMP

• IGMP (Internet Group Management Protocol) operates between Router and local Hosts, typically attached via a LAN (e.g., Ethernet)

• IGMP uses IP directly (protocol 2)

• Router queries the local Hosts for m-cast group membership info

• Router “connects” active Hosts to m-cast tree via m-cast protocol


Protocolo IGMP

• Hosts respond with membership reports– randomly delays response

• Host issues “leave-group” msg to leave– optional since router periodically polls anyway (soft state concept)

– “leave-group” causes immediate poll


Tipos de mensagens IGMPIGMP Message type Sent by Purpose

membership query: general router query for current active multicast groups

membership query: specific router query for specific m-cast group

membership report host host wants to join goup

leave group host host leaves the group


Encaminhamento “multicast” “router-to-router”• Problem: find the best (e.g., min cost) tree which

interconnects all the members (Steiner tree problem)


Opções na construção de árvores

• CORE-BASED/SHARED TREE: single tree per group; the root (A) is the “CORE” or the “Rendez Vous”point; all messages go through the CORE

• SOURCE BASED TREE: each source (A, B) is the root of its own tree per group connecting to all the members


Estado num nó (“router”)

To: 224.112.40.16

• What information must a router maintain to provide multicast?– Core-Based/Shared Tree: per interface, per-group

– Source-Rooted Tree: per-interface, per-group, and per-source!

Group Shared Tree

Y Y N

To: 224.112.40.16

Fr: 128.119.40.12

Fr: 128.8.17.134

Source Based Tree

Y Y NN Y N


Árvore de fonte vs. Árvore partilhada

• Source-Rooted pros:– no single point-of-failure (the CORE)

– less centralization of traffic (around core)

– packet sent along shortest path to receiver

• Core-Based/Shared better:– one router entry per source-group pair

– trees often utilize fewer links (consider min. spanning tree vs. shortest path tree)

– (How do you advertise the core??)

– Explicit Join less traffic, but longer delay.


Opções de sinalização

• The tree can be constructed with two options

– Receiver-initiated: receivers send messages to the source. The tree is formed by the path construction messages take to the source.

– Broadcast & Prune: a single node uses Reverse-Path Forwarding to broadcast the tree. Receivers prune back the tree when they don’t want the data.

A router that receives mcast packets buts has no mcast hosts sends a prune message to its upstream router.


Árvore com ponto central (sinalização iniciada no receptor)

• Predefined CORE for given m-cast group (e.g., posted on web page)

• New members “join” and “leave” the tree with explicit join and leave control messages

• Tree grows as new branches are “grafted” onto the tree

Join

coreJoin

Join


CBT (Core Based Tree)

• Group Shared Tree Protocol

• Upon a receiver join request, routers construct a path from the core toward that receiver

• Multicast transmissions traverse the tree (packets need not proceed through the CORE)

• Route maintenance:– downstream router issues ECHO-REQUEST

– upstream router refreshes link state and responds with ECHO-REPLY

core

A

B

C


Árvores baseadas nas fontes

Reverse Path Forwarding

• Packets are forwarded to all neighbors.

• If a packet is received on a link that is not the shortest path back to the source host of the packet, drop it!

• Doesn’t prevent packets from being received twice, but more efficient than flooding.

Each source is the root of its own tree: the tree of shortest paths (least unicast-cost path tree )


“Reverse Path Forwarding”


“Pruning”


Distance Vector Multicast Routing Protocol• DVMRP was the first m-cast protocol deployed on the Internet;

used in MBone (Multicast Backbone)

• Initially, the source broadcasts the packet to ALL routers (using Reverse Path Forwarding)

• Routers with no active Hosts (in this m-cast group) “prune” the tree; i.e., they disconnect themselves from the tree

• Recursively, interior routers with no active descendents self-prune after timeout (3 minutes in Internet) pruned branches “grow back”

• Problems: only few routers are mcast-able; solution: tunnels


PIM - DM (Protocol Independent Multicast - Dense Mode)

• Similar to DVMRP– Default: reverse-path forward routing, with pruning/grafting strategies

– Routers that are not in the path of any group member send prune messages;

– Routers (that do not belong to the multicast group) but are in the path of new members send graft messages.

• Difference with DVMRP:– usage of underlying unicast routing tables makes protocol simpler (the

underlying unicast protocol may be a distance vector [RIP] or link state protocol [OSPF]).


PIM - SM (Protocol Independent Multicast - Sparse Mode)

• Like CBT:– Default: router not joined to multicast group

– Initially, members join the “Shared Tree” centered around a Rendez-Vous Point (also called an RP)

• Difference: Packet first unicast to CORE, then dispersed

• Later, once the “connection” to the shared tree has been established, opportunities to connect DIRECTLY to the source are explored (thus establishing a partial Source Based tree)

core

A

B

C


Camada de Rede


– Datagramas






– inter domínio



• Mobilidade


Camada de rede na Internet

Tabela deencaminhamento

Protocolos de encaminhamento• sel. de caminhos• RIP, OSPF, BGP

Protocolo IP• endereçamento• formato dos datagramas• manuseamento

Protocolo ICMP • erros• sinalização

Camada de transporte: TCP, UDP


Camada física

Camadade rede


Protocolo ICMP (“Internet Control Message Protocol”)

• Usado por computadores e nós (“routers”) para comunicação de controlo da camada de rede

– informação de erros (exemplos): “unreachable host”, “unreachable protocol”, ...

– pedido/resposta de eco (usado pelo comando ping)

• situa-se na camada de rede “acima” do IP:– as mensagens ICMP são inseridas (campo

de dados) dos datagramas IP

• mensagem ICMP:

Type Code description0 0 echo reply (ping)3 0 dest. network unreachable3 1 dest host unreachable3 2 dest protocol unreachable3 3 dest port unreachable3 6 dest network unknown3 7 dest host unknown4 0 source quench (congestion

control - not used)8 0 echo request (ping)9 0 route advertisement10 0 router discovery11 0 TTL expired12 0 bad IP header

type code 8 bytes do datagrama IP

RFC 792, Setembro 1981

http://www.iana.org/assignments/icmp-parameters


Obtenção dinâmica de endereços IP

Endereço IP de uma interface individual (“host portion”):

• Atribuído pelo administrador do sistema e configurado manualmente

• DHCP: “Dynamic Host Configuration Protocol”: atribuição dinâmica de um endereço (“plug-and-play”):– RFC 1531, Outubro 1993

– http://www.ietf.org/html.charters/dhc-charter.html


DHCP: motivação

223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2223.1.3.1

223.1.3.27

A

BE

DHCP servidor

cliente DHCP: à chegadaprecisa obterum endereçodesta rede


DHCP: cenário de utilização Servidor DHCP : 223.1.2.5 Cliente à

chegada

time

DHCP discover

src : 0.0.0.0, 68 dest.: 255.255.255.255,67yiaddr: 0.0.0.0transaction ID: 654

DHCP offer

src: 223.1.2.5, 67 dest: 255.255.255.255, 68yiaddrr: 223.1.2.4transaction ID: 654Lifetime: 3600 secs

DHCP request

src: 0.0.0.0, 68 dest:: 255.255.255.255, 67yiaddrr: 223.1.2.4transaction ID: 655Lifetime: 3600 secs

DHCP ACK

src: 223.1.2.5, 67 dest: 255.255.255.255, 68yiaddrr: 223.1.2.4transaction ID: 655Lifetime: 3600 secs

1. Computador difunde a mensagem “DHCP discover”

2. Servidor DHCP responde com “DHCP offer”

3. Computador pede o endereço IP “DHCP request”

4. Servidor confirma endereço IP “DHCP ACK”


Tradução de endereços de rede (NAT)

10.0.0.1

10.0.0.2

10.0.0.3

10.0.0.4

138.76.29.7

Rede local10.0.0/24

Internetpública

Os datagramas com fonte e destino nesta rede têmendereços 10.0.0/24

Todos os datagramas ao deixar a rede local têm o mesmo endereço IP

(NAT IP): 138.76.29.7,mas número de porto diferente

• Motivação: do ponto de vista do mundo exterior todos os elementos da rede local

usam apenas um endereço IP:

– não há necessidade de requisitar uma colecção de endereços da entidade competente; basta um endereço IP

– podem mudar-se os endereços na rede local sem notificar o mundo exterior

– pode mudar-se de ISP sem mudar os endereços da rede local e sem mudanças nos nós da rede exterior

– os elementos da rede local não são endereçáveis explicitamente a partir do mundo exterior contribuindo para um aumento de segurança.

NAT (“Network Address Translation”): Ideias básicas em RFC 1631, Maio 1994


NAT - Implementação

Tarefas do encaminhador NAT:

– datagramas de saída: substituir (endereço IP de origem, porto #) de cada datagrama de saída por (endereço NAT IP, novo porto #)

. . . Os clientes/servidores remotos respondem usando como endereço de destino (endereço NAT IP, novo porto #).

– guardar (na tabela de tradução NAT) todos os pares (endereço IP de origem, porto #), (endereço NAT IP, novo porto #).

– datagramas de entrada: substituir (endereço NAT IP, novo porto #) no campo de endereço de destino de cada datagrama de entrada o valor correspondentena tabela de tradução NAT (endereço IP de origem, porto #).


Tabela de tradução NATendereço público endereço privado


10.0.0.1

10.0.0.2

10.0.0.3

S: 10.0.0.1, 3345D: 128.119.40.186, 80

1

10.0.0.4

138.76.29.7

138.76.29.7, 5001 10.0.0.1, 3345…… ……

S: 128.119.40.186, 80 D: 10.0.0.1, 3345 4

S: 138.76.29.7, 5001D: 128.119.40.186, 802

S: 128.119.40.186, 80 D: 138.76.29.7, 5001 3



• Campo de numeração de porto de 16 bits: – 216 = 65.536 ligações simultâneas com um único endereço!

Esta implementação do NAT é controversa:- os nós encaminhadores deviam processar apenas o que diz respeito ao nível de rede- viola o princípio de que o nível de transporte funciona estritamente extremo a extremo- a escassez de endereços deve ser resolvida por outros mecanismos (IPv6).


IPv6 (“Next Generation Internet Protocol”, IPng)

• Motivação inicial: o espaço de endereços de 32 bits estaria completamente atribuído até 2008 (visão pessimista do início dos anos 90).

• Breve história: – Recomendado pelo “IPng Area Directors” do IETF em Toronto, Julho de

1994, RFC 1752, (“The Recommendation for the IP Next Generation Protocol”) .

– Recomendação aprovada pelo “the Internet Engineering Steering Group”em Novembro de 1994.

– O corpo principal do protocolo IPv6 é um “Draft Standard” do IETF

desde Agosto de 1998.


Endereços IPv6

• Número de endereços (128 bits) disponíveis: 340.282.366.920.938.463.463.374.607.431.768.211.456, ou 665.570.793.348.866.943.898.599 por m2

• Exemplo de atribuições:

Reserva para Prefixo (binário) Fracção do total

Provider-Based Unicast Address 010 1/8

Multicast Addresses 1111 1111 1/256


IPv6

• Motivações adicioniais:– o formato do cabeçalho pode ajudar a aumentar a velocidade de

processamento em cada nó

– o cabeçalho pode incluir campos especialmente dedicados para o fornecimento de QoS.

– podem introduzir-se novos tipos de endereço, e.g., “anycast”(encaminhamento, em cada momento, para o melhor de um conjunto de servidores replicados)

• Formato do datagrama IPv6: – cabeçalho de tamanho fixo, 40 byte

– fragmentação não permitida


Cabeçalho dos pacotes IPv6

Priority: identifica a prioridade de um datagrama num fluxoFlow Label: identifica datagramas do mesmo fluxo (“flow”).

(o conceito de fluxo não está bem definido)Next header: identifica o protocolo que processa os dados


Algumas mudanças em relação ao IPv4

• Checksum: campo removido para reduzir o tempo de processamento em cada nó

• Options: pode continuar a haver opções mas são tratadas do mesmo modo que um protocolo de nível superior (campo Next header)

• ICMPv6: nova versão do ICMP– novos tipos de mensagens, e.g. “Packet Too Big”

– funções de gestão de grupos (“multicast”)


Transição IPv4 → IPv6

• Nem todos os nós podem ser modificados simultaneamente– impossibilidade de chegar a acordo para um dia e hora específicos

– Como funcionar na presença de nós heterogéneos IPv4/IPv6?

Duas abordagens possíveis:• Dual Stack: alguns nós com pilha dupla de protocolos (v6, v4) conseguem traduzir

um formato no outro

• Tunnelling: datagramas IPv6 transportados como “payload” em datagramas IPv4 em troços da rede que só suportam a versão 4.


Pilha dupla (“dual stack”)


Túnel (“tunneling”)


Camada de Rede


– Datagramas






– inter domínio



• Mobilidade


Mobilidade

• Mobilidade do ponto de vista da camada de rede:

mobilidade nula grande mobilidade

Utilizador sempre com o mesmo ponto deacesso

Utilizador passando por vários pontos de acesso sem perder as ligações estabelecidas

Utilizador ligando-e/desligando-se da rede com DHCP.


Mobilidade

“home network”: rede permanente do utilizador(e.g., 128.119.40/24)

“Permanent address”:endereço no “home network”, que pode sempre ser usado para aceder ao utilizador móvel, e.g., 128.119.40.186

“home agent”: entidade que executa funções de mobilidade no “home network” para manter o utilizador móvel acessível quando este está distante

wide area network

“correspondent”


Mobilidade

“Care-of-address”: endereço no “visited network” (e.g., 79.129.13.2)

wide area network

“visited network”: rede onde está actualmente o utilizador móvel (e.g., 79.129.13/24)

“Permanent address”: permanece constante (e.g., 128.119.40.186)

“foreign agent”: entidade que executa funções de mobilidade no “visited network” para manter o utilizador móvel acessível .

“correspondent”: utilizador que pretende comunicar com o móvel


Mobilidade: abordagens

• A cargo dos algoritmos de encaminhamento: os nós da rede são responsáveis por tornar conhecidos, pelos meios normais de troca de informação de encaminhamento, os endereços permanentes (“permanent adresses”) dos utilizadores móveis que em cada momento são capazes de atingir.– Tabelas de encaminhamento contêm o ponto de acesso actual de cada utilizador

móvel

– Não há necessidade de alterar os sistemas terminais

• A cargo dos sistemas terminais: – encaminhamento indirecto (“indirect routing”): a comunicação de um

correspondente para um utilizador móvel passa sempre por um agente na sua rede permanente (“home agent”) e só depois é enviada para a rede onde actualmente se situa.

– encaminhamento directo (“direct routing”): cada correspondente começa por obter o endereço actual do utilizador móvel com quem quer comunicar e envia directamente para a rede onde ele se encontra.


Mobilidade: registo

Resultado:

• O “foreign agent” conhece o utilizador móvel na sua rede

• O “home agent” sabe a localização do utilizador móvel

wide area network

“home network”“visited network”

1

Utilizador móvel contacta o “foreign agent” quando entra no “visited network”

2

“foreign agent” contacta o “home agent” passando-lhe a informação da nova localização do utilizador


Mobilidade por encaminhamento indirecto

wide area network

“homenetwork”

“visitednetwork”

3

2

41

correspondente endereça os datagramas para o endereço permanente do utilizador móvel

“home agent” intercepta os datagramas e envia-os para o “foreign agent”

“foreign agent” recebe os datagramas e envia-os para o utilizador móvel

Utilizador móvel responde directamente para o correspondente


Encaminhamento indirecto: comentários

• Utilizador móvel usa dois endereços:– endereço permanente (“permanent address”): usado pelo correspondente

– endereço no ponto de acesso actual (“care-of-address”): usado pelo “home agent” para enviar datagramas para o utilizador móvel

• as funções do “foreign agent” podem ser executadas pelo próprio utilizador móvel

• encaminhamento em triângulo:

correspondente → “home-network” → utilizador móvel– muito ineficiente quando

correspondente e utilizador móvel

se encontram na mesma rede


Envio de datagramas para o utilizador móvel

“Permanent address”: 128.119.40.186

“Care-of address”: 79.129.13.2

dest: 128.119.40.186

Datagrama enviado pelo correspondente

dest: 79.129.13.2 dest: 128.119.40.186

“home agent” → “foreign agent” dest: 128.119.40.186

“foreign-agent” → móvel


Encaminhamento indirecto: mudança de rede

• Suponha-se que o utilizador móvel muda de rede visitada– regista-se com um novo “foreign agent”

– o novo “foreign agent” regista-se com o “home agent”

– o “home agent” aceita o novo “care-of-address” do utilizador móvel

– os datagramas continuam a ser enviados para o móvel (com o novo “care-of-address”)

• Mudança de rede visitada é transparente: as ligações em curso podem ser mantidas!


Mobilidade por encaminhamento directo

wide area network

“homenetwork”

“visitednetwork”

4

2

41Correspondente pede e recebe o novo endereço do móvel

correspondente envia para o “foreign agent”

“foreign agent” recebe datagrama e envia para o móvel

Móvel responde directamente para o correspondente

3


Mobilidade por endereçamento directo: comentários

• Resolvido o problema de endereçamento em triângulo

• Necessidade de execução de funções de mobilidade no correspondente: correspondente tem de obter o “care-of-address” através do “home agent”

– O que acontece se o utilizador móvel muda de rede visitada durante a ligação?


Mobile IP

• RFC 3344 (Agosto 2002)

• Muitas das funções descritas atrás: – “home agents”, “foreign agents”, registo em “foreign-agents”, “care-of-

addresses”, endereçamento indirecto

• Alguns componentes da norma:– descoberta de agentes

– registo com o “home agent”

– endereçamento indirecto de datagramas


Mobile IP: descoberta de agente

• “agent advertisement”: “foreign/home agents” anunciam o serviço por difusão de mensagens ICMP (typefield = 9)

RBHFMGV bits reserved

type = 16

type = 9 code = 0 checksum

router address

standard ICMP fields

mobility agent advertisement

extension

length sequence #

registration lifetime

0 or more care-of-addresses

0 8 16 24

R bit: registo obrigatório

H,F bits: home and/or foreign agent


Mobile IP: exemplo de registo

visited network: 79.129.13/24 home agent

HA: 128.119.40.7 foreign agent

COA: 79.129.13.2 COA: 79.129.13.2

….

ICMP agent adv. Mobile agent MA: 128.119.40.186

registration req. COA: 79.129.13.2 HA: 128.119.40.7 MA: 128.119.40.186 Lifetime: 9999 identification:714 ….

registration req. COA: 79.129.13.2 HA: 128.119.40.7 MA: 128.119.40.186 Lifetime: 9999 identification: 714 encapsulation format ….

registration reply

HA: 128.119.40.7 MA: 128.119.40.186 Lifetime: 4999 Identification: 714 encapsulation format ….

registration reply

HA: 128.119.40.7 MA: 128.119.40.186 Lifetime: 4999 Identification: 714 ….

time

Documents

Camada de Rede - fenix.tecnico.ulisboa.pt · • execução de algoritmos/protocolos de encaminhamento (RIP, OSPF, BGP) • comutação de datagramas das ligações de entrada para