Introduzione al livello di rete e Dijkstra algorithm
24
Transcript of Introduzione al livello di rete e Dijkstra algorithm
2
La rete Internet3
Livello di rete (3)
Interconnessione di reti di diverso tipo
Gestione infrastruttura di rete
No vera struttura
Linee a banda larga + Router veloci
Nasconde al livello 4 complessità e
problematiche di networking
Protocollo IP
4
Protocollo IP
Transito dei PACCHETTI (datagrammi) in rete
Non orientato alla connessione
Commutazione di pacchetto vs circuito
5
L’header fisso di 20 byte
Version: 4 bit, utile per transazione IPv4>>>IPv6. '4' (0100) per IPv4.
IHL: 4 bit, lunghezza dell'intestazione, da 5 a 60 (60 con opzioni max 40
byte)
Type service: 7 bit. Voce richiede velocità, dati richiede precisione
Total lenght: 16 bit, lunghezza totale intestazione + dati. Max 65535
Identification: 16 bit, identificativo datagramma di appartenenza del
frammento
Don't framment: 1 bit, non frammentare, per evitare la frammentazione
More framment: 1 bit, tutti i frammenti, tranne l'ultimo, lo attivano.
Framments offset: 13 bit, posizione del frammento all'interno del segmento.
TTL: 8 bit, massimo 255. Contatore decrementato ad ogni salto. Se TTL=0
il diagramma viene scartato e inviato un messaggio al mittente.
Protocol: 8bit, quale processo di trasporto è in attesa dei dati. p.e. Tcp,
Udp, Icmp.
Header checksum: 16 bit, verifica solo l'intestazione. Ricalcolato ad ogni
salto.
Source e destination address, 32bit x 2, indirizzi IP
6
Hop by hop7
Indirizzo IPv4
32 bit ≈ 4G indirizzi possibili
Indirizzi privati e riservati
Dot-decimal notation 192.168.0.10
Rete + host
Classi di indirizzi
Indirizzi IP- Ad ogni scheda di rete viene assegnato un indirizzo appartenente ad una classe:
A) 0, 7 bit per la rete, 24 bit per host da 1… a 127…
B) 10, 14 bit per la rete, 16 bit per host da 128… a 191…
C) 110, 21 bit per la rete, 0 bit per host da 192… a 223…
D) 1110, 28 bit per indirizzi multicast da 224… a 239…
E) 11110, per scopi sperimentali e “futuri”
8
Il Router
Dispositivo di livello 3
Interconnette più reti
p.e. router domestici
connettono WAN e LAN
Instrada i pacchetti verso la
destinazione
Utilizza protocolli e algoritmi di
routing
9
Algoritmi
Caratteristiche:
Ottimalità in base a hop e costi
Semplicità richiesta di poche risorse e software minimo
Robustezza, Rapidità di convergenza, Flessibilità fault tolerance, traffico, icmp
Classificazione:
Autonomus System (IGP e EGP)
Non adattativi (statici, Link state, Dijkstra)
Adattativi (dinamici, distance vector, Bellman-Ford)
Percorso singolo o multiplo
10
Se cammino ottimo tra I e K, J tra I e K, allora I-J e J-K ottimi
Internal/External Gateway Protocol
Routing Table11
Link State Routing Protocol12
1. Invio messaggi HELLO all’accensione, interfaccia
2. Misurazione costo interfaccia con invio A/Rmessaggi ECHO
3. Costruzione del pacchetto dello stato deicollegamenti (Link State Packet): identitàneighbor, costo, informazioni di controllo (pergarantire integrità e #sequenza)
4. Distribuzione pacchetto. Al ricevimento di unnuovo o più recente # LSP, memorizza etrasmette in flooding; se più vecchio trasmette ilpiù recente
5. Elaborazione nuovi path (p.e. con Dijkstra)
Link state vs Distance vector
Protocol13
Distance Vector
Link State
Il problema
Trovare il CAMMINO
MINIMO (Shortest Path) in
un GRAFO???
Con pesi non negativi sugli
archi???
14
Cammino Casa - Ufficio15
Minimal guide to Graphs
G = (V, E)
coppia ordinata di insiemi
V insieme dei nodi
E insieme degli archi
Grafi orientati o semplici
Archi uscenti (p.e. A B)
Nodo di partenza ≠ Nodo di destinazone
16
Le strutture necessarie17
Shortest paths di Dijkstra
Dijkstra(G,ω,s)
Initialize(G,s)
S Ф
Q V
While Q ≠ Ф dou Extract-min(Q)
S S U {u}
for each vertice V є adj(u)
Relax(u,v, ω)
end for
End while
return d[], π[]
Initialize(G,s)
For each nodo єV
d[v] ∞
π[v] nil
end for
d[s] 0
Relax(u,v,ω)
If d[v]>d[u]+ ω(u,v)
d[v] d[u]+ ω(u,v)
π[v] u
end if
Extract-min() estrae il nodo con d()
minore
18
Shortest paths di Dijkstra
Dijkstra(G,ω,s)
Initialize(G,s)
S Ф
Q V
While Q ≠ Ф dou Extract-min(Q)
S S U {u}
for each vertice V є adj(u)
Relax(u,v, ω)
end for
End while
return d[], π[]
Initialize(G,s)
For each nodo єV
d[v] ∞
π[v] nil
end for
d[s] 0
Relax(u,v,ω)
If d[v]>d[u]+ ω(u,v)
d[v] d[u]+ ω(u,v)
π[v] u
end if
19
Cammino da Casa a Ufficio
Estratto nodo Casa, d[]=0
Adiacenti di Casa sono A e D
relax d[A]2, d[D]8
Estratto nodo A, d[]=2
Adiacenti di A sono C e B; relax d[C]4, d[B]8
Estratto nodo C, d[]=4
Adiacenti di C sono A, D, E; relax d[D]6, d[E]13
Estratto nodo D, d[]=6
Adiacenti di D sono C ed E; relax d[E]11
Estratto nodo B, d[]=8
Adiacenti di B sono A e Ufficio; relax d[Ufficio]13
Estratto nodo E, d[]=9.
Adiacenti di E sono C e Ufficio. D[Ufficio] sarà rilassato definitivamente a 10
20
Le strutture dopo l’esecuzione21
In laboratorio…22
Ping
Ipconfig
Nlslookup
Net
Netstat –n
Route print
Tracert
Wireshark
Una realizzazione
Una tesina d’esame di Jonathan La Mela, alunno diplomato nel 2013
http://test.mebuy.it/
Gestione Grafi
Gestione Nodi
Gestione Archi
Gestione Utenti
Rendering + Percorso e distanza minimi tra 2 nodi
23
Esercizio24
Senza usare Google Maps determinare qual’è il percorso
minimo Mantova-Varese?
MILANO
LODI
PAVIA
COMO
BERGAMO
LECCO
VARESE
CREMONA
BRESCIA
SONDRIO
MANTOVA
