Algoritmo di DijkstraShortest Path First

ugo.rinaldi@gmail.com

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