Corso di RETI DI COMUNICAZIONE E INTERNET Modulo 1Parte 2 RETI DATI IN AREA GEOGRAFICA (WAN) Reti di...

Reti di Comunicazione – M. De Marco

2. RETI DATI IN AREA GEOGRAFICA (WAN)

Slide 1

Politecnico di Milano – Sede di Cremona A.A. 2013/14

Corso di

RETI DI COMUNICAZIONE E INTERNET

Modulo 1

Martino De Marco email: [email protected]

skype: martino.demarco

Parte 2

RETI DATI IN AREA GEOGRAFICA (WAN)



Slide 2

Programma del corso

1 - RETI E SERVIZI DI

TELECOMUNICAZIONI

1.1 Servizi di telecomunicazioni

1.2 Caratterizzazione delle reti di

telecomunicazioni

1.3 Protocolli di comunicazione

2 - RETI DATI IN AREA GEOGRAFICA

(WAN)

2.1 Il livello data-link

2.2 Il livello di rete

2.3 Valutazione delle prestazioni

2.4 Cenni sull’evoluzione delle reti

dati in area geografica

3 - RETI DATI IN AREA LOCALE (LAN)

3.1 Architetture e protocolli LAN

3.2 LAN IEEE 802.3

3.3 Wireless LAN

3.4 Interconnessione LAN (bridging e routing)

4 - FONDAMENTI DI TELEFONIA FISSA E MOBILE

4.1 Reti fisse analogiche e digitali

4.2 Reti radiomobili



Slide 3

Sommario

• Generalità

• Livello 2: collegamento dati

• Livello 3: rete

• Prestazioni



Slide 4

Reti in area geografica - Generalità

• Topologia costituita da

– Rete di trasporto a lunga distanza

– Nodi della rete di accesso

– Rami tra le due reti

• Caratteristiche

– Rete a maglia

– Senza o con gerarchia

• Aspetti fondamentali

– Rami

• Capacità trasmissiva

– Nodi

• Velocità di elaborazione

• Capacità di memoria

• Parametri di prestazione

– Throughput

– Ritardo

– Probabilità di perdita



Slide 5

Sommario

• Generalità


– Protocolli Stop and wait e ARQ

– Protocollo HDLC

• Livello 3: rete

• Prestazioni



Slide 6

OSI – Data-link Layer

• Trasferisce IU prive di errore tra entità di rete su un mezzo

trasmissivo reale

• Fornisce i mezzi funzionali e procedurali per instaurare una

connessione tra entità dello strato di rete per il trasferimento

dei dati in modo trasparente e affidabile

• I servizi forniti sono:

– L'apertura e il rilascio di una connessione di collegamento

– La frammentazione dei dati in trame

– Il trasferimento trasparente dei dati (framing)

– Il rilevamento e il recupero degli errori

– Il controllo di flusso

– Il controllo della sequenza dei dati

– Accesso a mezzo condiviso

• Esempi: HDLC, ITU-T LAP-B e LAP-D, IEEE 802.x

A p p l i c a t i o n l a y e r

P r e s e n t a t i o n l a y e r

S e s s i o n l a y e r

T r a n s p o r t l a y e r

N e t w o r k l a y e r

D a t a l i n k l a y e r

P h y s i c a l l a y e r

7

6

5

4

3

2

1

LIVELLO 2: COLLEGAMENTO DATI



Slide 7

Livello di collegamento dati

• Compito fondamentale: elevare le prestazioni di una linea

fisica con dato tasso di errore offrendo al livello di rete un

servizio di collegamento privo di errori

• Informazione strutturata in trame

• Funzioni fondamentali

– Gestione del collegamento dati

– Delimitazione delle trame

– Indirizzamento

– Controllo degli errori e delle eventuali ritrasmissioni

– Controllo di flusso




Slide 8

Controllo e recupero degli errori

• Strategie

– Forward Error Control - FEC

• Codici a blocchi

• Codici convoluzionali

• Traffico indipendente dal tasso di errore

• Processing sempre più spinto per codici più complessi

– Automatic Repeat reQuest

• Usa un codice di rivelazione di errore

• Richiede un canale di ritorno

• Il traffico aumenta con il tasso di errore

• Protocolli impiegati:

– Stop and wait

– Continuous ARQ: trame numerate




Slide 9

Stop and wait - Assenza di errori

• Parametri:

– Tf: tempo di trasmissione di una trama (s)

– Ta: tempo di trasmissione di un riscontro (s)

– Tp: tempo di elaborazione (s)

- : tempo di propagazione (s)

– C: frequenza di cifra del canale (bit/s)

– Lf: lunghezza della trama (bit)

– La: lunghezza del riscontro (bit)

– d: distanza tra trasmettitore e ricevitore (m)

– v: velocità di propagazione (m/s)

• Efficienza del protocollo in assenza di errori:

frazione di tempo in cui il canale è impegnato

a trasmettere “trame utili”

T f

T p

T a T p

B A


= T f

T f + T a + 2 T p + 2 @

T f

T f + 2 =

1

1 + 2 a a =

T f =

d v

L f C



Slide 10

Stop and wait - Presenza di errori

• Presenza di errori su trame o riscontri

richiede la ritrasmissione con time-out T

• Esempio di trasmissione con errore sul

riscontro

– Tx trasmette una trama due volte per

scadenza del time-out e riceve un riscontro

– Rx crede di aver ricevuto due trame diverse!

È necessario numerare le trame!

• T Ta +2Tp +2T f

T p

T a T

T p

B A




Slide 11


• Esempio di trasmissione con errore

sulla trama

– Tx trasmette una trama due volte per

scadenza del time-out e riceve un

riscontro

T

B A




Slide 12


• Selezione del time-out T

– Il tempo di elaborazione non è

controllabile

– Il time-out non deve essere troppo

grande per evitare inefficienze

– Valore minimo del time-out:

Ta+2Tp+2

• Presenza di errori su trame o riscontri

richiede la numerazione di trame e

riscontri per evitare ambiguità

– 1 bit di numerazione consente di scartare

trame duplicate o riscontri duplicati

T

B A

0

A C K 0

A C K 1

1

0

A C K 0




Slide 13


Calcolo dell'efficienza in presenza di errori

• Assunzioni

– Errori sui bit e sulle trame mutuamente indipendenti

– p: probabilità di un bit errato

– P: probabilità di una trama errata

– ai: probabilità di successo alla trasmissione i-esima

– Ns: numero medio di trame trasmesse per trama ricevuta con successo

• Calcolo efficienza (coeff. utilizzazione link)

• P =1- 1- p Lf +La

• Ns = iaii =1

= iP i-1 1-P i =1

= 1-P iP i -1

i=1

=1

1-P

• =Tf

Ns -1 Tf +T +Tf +Ta + 2Tp + 2=

Tf 1-P

Tf +TP + Ta + 2Tp + 2 1-P

• T =Ta + 2Tp + 2 = max =Tf 1-P

Tf +Ta + 2Tp + 2

• Ta =Tp = 0 max =1-P

1+ 2a




Slide 14

Continuous ARQ

Esempio di trasmissione

senza errori

1

2

3

4

5

6

7

A C K 1

A C K 2

A C K 3

A C K 5

A C K 7

A C K 6

A C K 4

B A




Slide 15

Continuous ARQ

• Due tipi di riscontri entrambi numerati

– ACK i: riscontro positivo di tipo cumulativo fino alla trama i

– NACK i: riscontro negativo della trama i

• Protocolli

– Go-back-n

• Trame ricevute fuori sequenza a causa di errori sono scartate

• Ritrasmissione a partire dall'ultima trama non riscontrata

• n è il numero massimo di trame che possono essere trasmesse in assenza di riscontri (es. n=7 con numerazione modulo 8)

• NACK i indica riscontro negativo della trama i, ma anche riscontro positivo fino alla trama i-1

– Selective repeat

• Trame accettate anche fuori sequenza buffer richiesto in ricezione per risequenziare le trame

• NACK i indica solo riscontro negativo della trama i

• Ritrasmissione selettiva

– Esplicitamente richiesta (NACK)

– Per scadenza di time-out




Slide 16

Continuous ARQ - Esempi

1

2

3

4

5

6

7

4

5

6

7

A C K 1

A C K 2

A C K 3

N A C K 4

A C K 4

A C K 5

B A

G o - b a c k - n

1

2

3

4

5

6

7

4

0

1

2

A C K 1

A C K 2

A C K 3

N A C K 4

A C K 7

A C K 0

B A

S e l e c t i v e r e p e a t

1

2

3

4

5

6

7

0

5

4

1

A C K 1

A C K 2

A C K 3

A C K 0

N A C K 5 T

A C K 4

B A




Slide 17

Continuous ARQ - Efficienza

• Assunzioni

– Ta = Tp = 0

– K: numero di trame ritrasmesse in seguito a errore (trascurando la trama errata)

• Calcolo efficienza (coeff. utilizzazione link)

– Hp: il buffer del Tx è sempre non vuoto

• =T f

N sT f

=1

N s

• Selective repeat

• N s =1

1- P• Go- back- n

• N s = 1 1- P + K +1 P 1- P + 2K + 1 P2 1- P + ...+ iK +1 P i 1- P + ...=

= iK +1 P i 1- P i=0

=KP

1- P+ 1=

1+ K -1 P1- P

• KT f @ T f + 2 K = 1+ 2a

• =

1- P SR

1- P

1+ 2aPGBN




Slide 18

Continuous ARQ - Sliding window

• Controllo di flusso sul collegamento dati mediante sliding window

– Controlla il riempimento dei buffer

– Basato su numerazione di trame modulo N

• Sliding window utilizza due finestre

– Finestra in trasmissione con ampiezza W

• Fino a Wt trame possono essere trasmesse in assenza di riscontro

• Ogni riscontro ricevuto fa scorrere la finestra

– Finestra in ricezione con ampiezza Wr

• Fino a Wr trame possono essere accettate

• Le trame accettate in sequenza fanno scorrere la finestra

– Vincolo per evitare ambiguità: Wt + Wr N

• Protocollo Go-back-n

– Wr = 1

– Wt N-1

• Protocollo Selective repeat

– Wt = Wr = W W = N/2




Slide 19

Continuous ARQ - Sliding window

• Effetto della relazione tra W e

T f

2 W T f

B A

0

1

2

3

A C K 0

A C K 1

A C K 2

A C K 3

W = 4

T f

2

W T f

B A

0

1

2

3

A C K 0

A C K 1

A C K 2

A C K 3

W = 2




Slide 20

Sliding window - Efficienza

• Casi

• WTf Tf + 2 W 1+ 2a

• WTf Tf + 2 W 1+ 2a

• Senza errori

• =

1 W 1+ 2aWTf

Tf + 2=

W

1+ 2aW 1+ 2a

• Con errori

• W 1+ 2a : come prima

=1-P SR1-P

1+ 2aPGBN

• W 1+ 2a

=WTf Ns

Tf + 2=

W

Ns 1+ 2a =

W 1-P

1+ 2aSR

W 1-P

1+ 2a 1+ W -1 P GBN K =W




Slide 21

Sliding window - Efficienza




Slide 22

Sommario

• Generalità


– Protocolli Stop and wait e ARQ

– Protocollo HDLC

• Livello 3: rete

• Prestazioni



Slide 23

High-level Data Link Control

• Tipo di stazione

– Primaria: responsabile del collegamento, emette comandi

– Secondaria: asservita alla primaria, emette risposte

– Combinata: emette sia comandi, sia risposte

• Configurazione del collegamento

– Sbilanciata: 1 primaria, 1 secondarie

– Bilanciata: 2 stazioni combinate

• Modi di trasferimento

– Asynchronous Balanced Mode (ABM): configurazione bilanciata

• 2 stazioni combinate

• Trasmissione di tipo full-duplex

– Normal Response Mode (NRM): configurazione sbilanciata

• 1 stazione primaria e almeo 1 stazione secondaria

• Trasmissione di tipo half-duplex

– Asynchronous Response Mode (ARM): configurazione sbilanciata

• Come NRM con possibilità per il secondario di iniziare la trasmissione senza permesso

LIVELLO 2: HDLC



Slide 24

Struttura di trama

• Formato di trama

Flag Address Control Information FCS Flag

8 bit 8xn bit 8/16 bit variable 16/32 bit 8 bit

LIVELLO 2: HDLC



Slide 25

Funzioni

• Flag: 01111110

– Trasparenza dati realizzata tramite bit stuffing

• Trasmittente inserisce uno 0 dopo ogni occorrenza di cinque 1 (non nei

flag)

• Ricevente rimuove lo zero dopo i cinque uni

•

– Occorrenza di errori può causare

• Divisione di una trama in due (flag simulato all'interno di una trama)

• Fusione di due trame (flag tra due trame consecutive soggetto ad errore)

a 011111101011111110111111111110100011111101111110b 0111111010111110110111110111110101000111110101111110

LIVELLO 2: HDLC



Slide 26

Funzioni

• Address: indica il secondario in configurazioni sbilanciate

– Campo di 8 bit estendibili a multipli di 8

– 128 stazioni indirizzabili con configurazione base

– Comandi (C): indirizzo indica il destinatario

– Risposte (R): indirizzo indica il mittente

LIVELLO 2: HDLC



Slide 27

Funzioni

• Control: indica il tipo di trama e contiene la numerazione

– Tipi di trame

• Information

• Supervisory

• Unnumbered

– Numerazione 3 bit estendibili a 7 con SNRME

• N(S): numero sequenziale

di trama

• N(R): numero prossima

trama attesa (riscontro

implicito fino a N(R)-1)


• Esercitato con il controllo a finestra con N(s) e N(r)

– Recupero da errori

• Implementa sia Go-back-n, sia Selective repeat

LIVELLO 2: HDLC

0 N(S) P/F N(R)

1 2 3 4 5 6 7 8

I

1 S P/F N(R)

1 2 3 4 5 6 7 8

S

1 M P/F M

1 2 3 4 5 6 7 8

U

0

1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

S 1 S 0 0 0 0 0 P/F N(R)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

I 0 N(S) P/F N(R)



Slide 28

Funzioni • Frame check sequence: verifica la correttezza degli altri campi eccetto i flags

– Polinomio divisore CCITT-ITU: D(X) = X16 + X12 + X5 + 1 per FCS con k=16 bit (cioè 10001000000100001)

– Campo da proteggere P(X) a n bit

– Campo FCS a k bit

– Trama trasmessa P'(X) a n+k bit

– Rivelazione di errore basata sull'aritmetica modulo 2

– Errore rivelato se la divisione in ricezione produce resto 0

– Protezione da

• Errori singoli su bit

• Errori su due bit se D(X) ha almeno tre 1

• Errori a burst con lunghezza di burst < k

• La maggior parte degli errori a burst

• P X X k

D(X )= Q(X )+

R X

D(X )

• P X = P X X k+R X

• P X

D(X )=

P X X k

D(X )+

R X

D(X )= Q(X )+ 2

R X

D(X )= Q(X )

LIVELLO 2: HDLC



Slide 29

Gestione del collegamento dati

• Comandi e risposte

– Comando: indirizzo del destinatario

– Risposta: indirizzo del mittente

SIM

SNRM/SNRME

SARM/SARME

SABM/SABME

UA

UI

RSET

FRMR

DISC

Others

RR

RNR

REJ

SREJ

Frame C R

¦ ¦

¦

¦

¦

¦

¦

¦

¦

¦

¦

¦

¦

¦

¦

¦

¦

¦

¦

¦

¦

¦

Type

I

S

U

LIVELLO 2: HDLC



Slide 30


T

S A B M

UA

S A B M

UA

D I S C

B A

I , 0 , 0

I , 3 , 1

I , 1 , 0

I , 2 , 0

I , 0 , 0

R R , 2

R R , 4

I , 1 , 2

R R , 2

B A

ABM ideale

LIVELLO 2: HDLC



Slide 31


I , 0 , 0

I , 3 , 1

I , 1 , 0

I , 2 , 0

I , 0 , 0

R R , 1

I , 3 , 2

I , 1 , 1

I , 2 , 1

R E J , 1

I , 1 , 1

R R , 2

R R , 3

R R , 4

B A

I , 0 , 0

I , 3 , 0

I , 1 , 0

I , 2 , 0 I , 0 , 0

I , 1 , 1

S R E J , 1

R R , 4 I , 4 , 1

R R , 5

I , 1 , 1

R R , 2

R R , 1

B A

ABM con errore

in GBN e SR

LIVELLO 2: HDLC



Slide 32


T

I , 0 , 0

I , 2 , 1

I , 1 , 0

I , 0 , 0

R R , 1

I , 0 , 1

I , 3 , 1

R R , 2

I , 1 , 3

R R , 3

R R , 4

R R , 2

B A

ABM con

ritrasmissione

per timeout

LIVELLO 2: HDLC



Slide 33


B , I , 0 , 1

C , I , 1 , 4 , P

C , I , 4 , 2 . F

B , S R E J , 1 , P

C , R N R , 5 U I U I U I U I

B , R R , 0 , P

B , I , 1 , 1 B , I , 2 , 1 , F

B , I , 1 , 1 , F

B , R R , 3

B

A

C

C , S N R M , P

B , U A , F

B , S N R M , P

C , U A , F

C , I , 0 , 0 , P

C , I , 0 , 1 C , I , 1 , 1 C , I , 2 , 1 C , I , 3 , 1 , F

B , I , 0 , 0 , P

B , R R , 1 , F

C , R R , 4

B

A

C

Esempio di

NRM

LIVELLO 2: HDLC



Slide 34


C , R R , 5 , P

T

C , R R , 5 , P

C , I , 5 , 2 . F

C , I , 5 , 3 . F

C , I , 2 , 5 , P

C , R R , 6

T

B

A

C

Esempio di

NRM (cont.)

LIVELLO 2: HDLC



Slide 35

Gestione delle finestre

• Finestra in trasmissione

– Trasmesse, in assenza di riscontro, fino a Ws trame con

Ls N(s) (Ls+Ws-1)modN

– Ls = ultimo N(r) ricevuto in trame I, RR, RNR, REJ

• Finestra in ricezione

– Accettate tutte le trame con Lr N(s) (Lr+Wr-1)modN

– Lr = ultimo N(r) inviato in trame I, RR, RNR, REJ

• Protocollo Go-back-n

– Wr = 1

– Ws ≤ N-1

• Protocollo Selective repeat

– Ws = Wr = W W = N/2

0

12

3

4

5 6

7

Lr=5

Wr=1

0

12

3

4

5 6

7

Ls=3

Ws=7

LIVELLO 2: HDLC



Slide 36

Parametri del protocollo

• Alcuni parametri del protocollo

– T1: time-out per ritrasmissione in assenza di riscontro

– T2: max intervallo di tempo ammesso per elaborazione trama ricevuta e

inizio di trasmissione riscontro

– N1: max numero di bit del campo informativo

– N2: max numero di ritrasmissioni ammesse per ogni trama

LIVELLO 2: HDLC



Slide 37

Sliding window - Efficienza Collegamenti

terrestre e via satellite



Slide 38

Sliding window - Efficienza - Collegamento via

satellite



Slide 39

Sommario

• Generalità


• Livello 3: rete

– Servizi forniti

– Algoritmi di instradamento

– Controllo di congestione e di flusso

– Protocollo X.25

• Prestazioni



Slide 40

OSI – Network Layer

• Fornisce i mezzi per instaurare e rilasciare connessioni logiche

di rete su cui instradare le informazioni

• Svolge funzioni di trasferimento dati nodo-nodo

• Maschera alle entità di trasporto la tecnica di commutazione

• I servizi forniti sono:

– Apertura e il rilascio di una connessione di rete

– Organizzazione dei dati in pacchetti

– Indirizzamento e trasferimento dei dati end-to-end

(instradamento)

– Controllo della congestione

– Gestire la qualità del servizio (ad esempio il tempo di

attraversamento della rete)

– Internetworking

• Esempio: ITU-T X.25 liv. 3, IETF IP

A p p l i c a t i o n l a y e r

P r e s e n t a t i o n l a y e r

S e s s i o n l a y e r

T r a n s p o r t l a y e r

N e t w o r k l a y e r

D a t a l i n k l a y e r

P h y s i c a l l a y e r

7

6

5

4

3

2

1

Traffico offerto

Tra

ffic

o s

ma

ltito

Capacità max della rete

desiderabile

congestione

CONGESTIONE

LIVELLO 3: SERVIZI



Slide 41

Livello di rete

• Obiettivo: trasferire T-PDU attraverso la rete di comunicazione

mascherando ai livelli superiore i dettagli relativi a

– Tipo di rete sottostante

– Modalità di commutazione

• Funzioni fondamentali

– Instradamento di pacchetti, attuato mediante la funzione di “attraversamento”

– Multiplazione di più flussi di livello 3 su un singolo collegamento di livello 2


– Controllo di congestione

– Intercooperazione di reti diverse

• Servizi forniti

– Datagramma

– Chiamata virtuale o circuito virtuale

– Circuito virtuale permanente

LIVELLO 3: SERVIZI



Slide 42

Servizio datagramma

Duplicazione Perdita

Fuori sequenza

1

3 2

2

3 A

B C

F E

D

1

2

2

A

B C

F E

D

1

2

A

B C

F E

D

2

3

2

1

A

B C

F E

D

LIVELLO 3: SERVIZI



Slide 43

Servizio chiamata virtuale

Fase di segnalazione Fase dati

A

B C

F E

D

2

3

1

A

B C

F E

D

LIVELLO 3: SERVIZI



Slide 44

Chiamata virtuale - Canali logici

Chiamata

virtualePercorso

1 HA-HD A-B-E-D

2 HA-HE A-F-E

3 HB-HC B-C

4 HB-HA B-A

5 HC-HB C-B

6 HD-HE D-F-E

7 HE-HB E-F-A-B

8 HF-HD F-B-C-D

9 HF-HD F-D

A

B C

F E

D

H 41 B 23

H 2 F 7

F 23 B 19

H 1 B 23

H 8 D 41

D 2 E 41

A 7 E 33

E 33 A 23

B 6 D 16

F 41 H 5

F 33 H 13

H 13 F 33

E 16 H 5

F 41 H 2

C 56 H 8

H 10 F 2

A 23 E 6

H 0 C 3

H 7 A 3

C 14 H 2

A 19 H 1

B 23 D 56

B 3 H 2

H 11 B 14F 23 C 23

B 3 H 2

IN OUT

IN OUT IN OUT

IN OUTIN OUT

IN OUT

LIVELLO 3: SERVIZI



Slide 45

Servizio circuito virtuale permanente

• Analogo alla chiamata virtuale

– Le fasi di instaurazione e rilascio

• Non avvengono tramite pacchetti di segnalazione

• Sono attuate da operatori

– Gestione “manuale” delle tabelle di instradamento

LIVELLO 3: SERVIZI



Slide 46

Reti in area geografica - Servizi

Caratteristica DG VC

Indirizzamento di

pacchetti (dati)

Source e destin address

in ogni pacchetto

VCI nel pacchetto

Instradamento Indipendente per

pacchetto

Indipendente per

chiamata.

Fisso nella chiamata

Controllo di sequenza No Si

Throughput Minore Maggiore

Complessità nodi Minore Maggiore (tabelle routing)

Controllo di congestione Difficile Relativamente più facile

Guasto ad un nodo Perdita pacchetti

interessati a quel nodo

Reset di tutti i VC passanti

nel nodo

LIVELLO 3: SERVIZI



Slide 47

Sommario

• Generalità


• Livello 3: rete

– Servizi forniti



– Protocollo X.25

• Prestazioni



Slide 48

Algoritmi di instradamento

• Requisiti di un algoritmo di instradamento

– Semplicità

– Robustezza

– Stabilità

– Ottimalità

• Pacchetti che devono essere instradati

– Pacchetti di segnalazione in servizi VC

– Pacchetti dati in servizi DG

• Localizzazione della decisione di instradamento

– Algoritmi centralizzati: un unico centro di controllo prende tutte le decisioni

– Algoritmi distribuiti: tutti i nodi cooperano per determinare il migliore

instradamento in ogni nodo

– Algoritmi isolati: il nodo sorgente prende le proprie decisioni eventualmente

anche in base a informazioni chieste ad altri nodi

LIVELLO 3: INSTRADAMENTO



Slide 49

Algoritmi di instradamento -Tassonomia

Instradamento

con tabella

Instradamento

senza tabellaInstradamento

gerarchico

Algoritmi di

instradamento

Source routingRandom FissoDinamicoFlooding

Link stateDistance vector




Slide 50

Algoritmi senza tabella

• Random: il link uscente è scelto casualmente

– Molto robusto

– Tempi di ritardo con alta varianza

– Variazione: instradamento deterministico solo se la destinazione è adiacente (tabella ridotta che definisce solo le adiacenze)

• Flooding: il pacchetto è replicato su tutti i link uscenti

– Limitazione del traffico interno garantita se ogni nodo

• Scarta i pacchetti già transitati oppure

• Scarta i pacchetti il cui massimo numero di salti si è esaurito (necessario un contatore nel pacchetto)

– Il nodo generico scarta un pacchetto se

• Esso è giunto a destinazione

• Il criterio di scarto è soddisfatto

– Robustissimo (adottato in applicazioni militari)

– Aumenta il traffico interno a parità di quello esterno

– Variazione: instradamento solo su un gruppo di linee uscenti (tabella ridotta con link diretti verso la destinazione)




Slide 51

Algoritmi senza tabella

• Source routing: il nodo sorgente predetermina la strada scrivendola nel

pacchetto

– Forma di indirizzo: Hs,N1,N2,...,NL,Hd (Ni identifica il nodo i)

– Path determination

• Fornita da un path server (soluzione centralizzata, semplice ma inaffidabile)

• Fornita da un path discovery (soluzione isolata)

– Path discovery

• Il nodo sorgente invia in flooding un pacchetto alla destinazione

• I nodi attraversati riempiono il campo Ni

• Il nodo destinazione sceglie tra i pacchetti arrivati quello che identifica la via migliore

(primo arrivato o quello con il minore numero di nodi attraversati)

• Il nodo destinazione comunica la sua scelta al nodo sorgente che utilizza la via

scelta

– Problema critico: determinazione della frequenza di aggiornamento dei singoli

percorsi




Slide 52

Algoritmi con tabella - Instradamento fisso

• Algoritmo di instradamento a distanza minima (o costo minimo) richiede

la definizione di una metrica

– Possibili metriche

• Numero di salti

• Capacità dei link sulla via

• Ritardo medio sulla via

• Numero totale di pacchetti in coda sulla via

• ecc.

• Instradamento fisso

– Un centro di controllo costruisce le tabelle di instradamento che devono

essere applicate da ogni singolo nodo e le comunica ai nodi stessi

– Le tabelle vengono cambiate solo a seguito di aggiornamento della

topologia

– Poco flessibile, in quanto non reagisce a sovraccariche e guasti aleatori




Slide 53

Instradamento a minima distanza –

Distance vector

• Algoritmo distance vector

– Tabella in ogni nodo che specifica la minima distanza ad ogni altro nodo e

quale link in uscita deve essere usato

– Il nodo riceve la stima dei suoi vicini, somma la sua distanza al vicino e

scopre la distanza minima verso ogni altro nodo e il link uscente relativo

(vettore delle distanze)

– Corrisponde ad applicare in ogni nodo l’algoritmo di Bellman-Ford con

calcolo centralizzato dell’albero

• Esempio




Slide 54

Algoritmo distance vector - Esempio




Slide 55

Algoritmo distance vector - Esempio

Calcolo del vettore nel nodo A

Dest. Cost Rout.

A -

B 1 B

F 3 F

Node A - Step 1

Dest. Cost Rout.

A 1 A

B -

C 3 C

E 5 E

F 1 F

Node B - Step 1

Dest. Cost Rout.

A 3 A

B 1 B

D D

E 2 E

F -

Node F - Step 1

Dest. Cost Rout.

A 2 B

B 1 B

C B

D E

E 2 E

F -

Node F - Step 2

Dest. Cost Rout.

A 2 B

B 1 B

C B

D E

E 2 E

F -

Node F - Step 3

Dest. Cost Rout.

A -

B 1 B

C 4 B

D 9 F

E 5 F

F 2 B

Node A - Step 2

Dest. Cost Rout.

A -

B 1 B

C 4 B

D 6 F

E 4 B

F 2 B

Node A - Step 3

Dest. Cost Rout.

A -

B 1 B

C 4 B

D 5 B

E 4 B

F 2 B

Node A - Step 4

Dest. Cost Rout.

A 1 A

B -

C 3 C

D C

E 3 F

F 1 F

Node B - Step 2

Dest. Cost Rout.

A 1 A

B -

C 3 C

D F

E 3 F

F 1 F

Node B - Step 3




Slide 56

Algoritmo di Bellman-Ford - Esempio

2

3

,min

1+=2

11

salti max con a da costo minimo a via della Costo

diretto) link senza ( a da diretta via della costo

11

togoelse

stoph=hIf

DdDD

hh

sjdD

h

hjsD

djid

max

hjij

hi

i

hj

ijhj

hj

ijij

-- +=

=

=

=

==

Dest. Cost Rout.

A -

B 1 B

C

D

E

F 3 F

Node A

Dest. Cost Rout.

A -

B 1 B

C 4 B

D 9 F

E 5 F

F 2 B

Node A

Dest. Cost Rout.

A -

B 1 B

C 4 B

D 6 F

E 4 B

F 2 B

Node A

Dest. Cost Rout.

A -

B 1 B

C 4 B

D 5 B

E 4 B

F 2 B

Node A




Slide 57

Instradamento a minima distanza - Algoritmi

• Algoritmo distance vector

– Usato in ARPANET fino al 1979 con periodo di aggiornamento di

125 ms

– Basato sulla lunghezza delle code (non su velocità dei link)

– Anche con metriche diverse era troppo lento a convergere in un

contesto dinamico

• Nuovo algoritmo per ARPANET (1979): link state

– Ogni nodo misura la distanza (secondo la metrica ritardo) a tutti i

suoi vicini

– Questa distanza è comunicata a tutti altri nodi con flooding

– Ogni nodo può così costruirsi i percorsi a minima distanza ad ogni

altro nodo

– Periodo di aggiornamento nell’ordine dei 10s




Slide 58

Instradamento a minima distanza -

Algoritmo di Dijkstra

N = nodi della rete

M = insieme dei nodi del grafo corrente MST

V(J )= nodi "vicini" all'insieme J

d ij = costo della via diretta da i a j (d ij = in assenza del link i - j)

D j = Costo della via a minimo costo da s a j

1 M = s

D j = dsj j V s

D j = otherwise

2 Select k V M Dk = miniV M

Di

M = M + k

D j = min D j ,Dk + dkj j V M

3 If M = N stop

else go to 2




Slide 59

Algoritmo di Dijkstra - Esempio




Slide 60

Instradamento a minima distanza - Osservazioni

• Bellman-Ford e Dijkstra convergono alla stessa soluzione in

condizioni statiche

• Algoritmo di Bellman-Ford

– Ha convergenza più lenta in condizioni dinamiche

– E’ implicitamente di tipo distribuito

– Ogni nodo deve conoscere solo ciò che vedono i suoi vicini

• Algoritmo di Dijkstra

– Può essere implementato sia in forma centralizzata che in forma

distribuita

– Nella forma distribuita, ogni nodo deve “vedere” l’intera rete




Slide 61

Algoritmi gerarchici

• Grande numero di nodi implica

– Grande occupazione di memoria per le tabelle di

instradamento

– Sovraccarico di rete per scambio tabelle di instradamento

in algoritmi distribuiti

• Strutturazione dei nodi in regioni

– Instradamento basato

su tabelle semplificate

Dest.Routfull

Routred

A.1 A.6 A.6

A.2 A.4 A.4

A.3 A.4 A.4

A.4 A.4 A.4

A.5 - -

A.6 A.6 A.6

B.1 B.1

B.1

B.2 B.1

B.3 B.1

B.4 B.1

B.5 B.1

C.1 C.1

C.1

C.2 C.1

C.3 A.4

C.4 A.4

C.5 C.1

C.6 C.1

A.5 routing table




Slide 62

Algoritmi gerarchici

• Strutturazione gerarchica dei nodi su più livelli

– Nodi suddivisi in regioni (primo livello)

– Regioni divise in aree (secondo livello)

– Aree divise in zone (terzo livello)

– ecc.




Slide 63

Sommario

• Generalità


• Livello 3: rete

– Servizi forniti



– Protocollo X.25

• Prestazioni



Slide 64

Controllo di congestione e di flusso

A

B

Region I Region II Region III

No congestion

within network

Mild

congestion

Severe

congestion

Offered load

Network Throughput

B

A

Region I Region II Region III

No congestionwithin network

Mildcongestion

Severecongestion

Offered load

Network Delay

LIVELLO 3: CONGESTIONE



Slide 65

Generalità

• Portata – In accesso alla rete

– Internodo

• Hop-by-hop

• Edge-to-edge

– End-to-end

• Tipologia – Metodi reattivi

• Operano con schema a catena chiusa

• Sono previsti a differenti scale temporali

– Metodi preventivi

• Operano con schema a catena aperta

• Tecnica

– Credit-based

• Window scheme

– Rate-based

• Tecnica isaritmica

• Leaky bucket

• Token bucket




Slide 66

Meccanismi Credit-based • Controllo di flusso a finestra a catena chiusa

– Utilizzato tipicamente hop-by-hop a livello 3

• Avanzamento della finestra determinato dai riscontri (ack-based window)

• Realizza un controllo di flusso per circuito virtuale

– Se utilizzato a livello end-to-end (livello 4)

• Lo schema diventa del tipo a credito esplicito (credit-based window)

– Il ricevente invia al trasmittente dei messaggi di credito che possono essere opportunamente adattati

• Il flusso diventa bursty (critico il dimensionamento di W)

• Non garantisce una capacità minima alla sessione

• Controllo di congestione mediante meccanismo a finestra (a catena chiusa)

– La dimensione della finestra può essere dinamicamente aumentata o diminuita in base alle indicazioni di congestione (esplicite o implicite) che il destinatario riceve

• Incremento/decremento additivo

• Incremento/decremento moltiplicativo

• Combinazione dei due (per esempio decremento moltiplicativo, incremento additivo)




Slide 67

Meccanismi Credit-based

• Controllo di flusso a finestra a catena aperta – Per ogni pacchetto trasmesso la finestra si chiude di una posizione

– Ogni r secondi la finestra si riapre alla massima apertura W

W / r

B A

W = 2




Slide 68

Meccanismi Rate-based

• Tecnica isaritmica – Utilizzata tipicamente all’accesso della rete

– Un numero fisso di permessi circola nella rete

– Un pacchetto entra in rete se nel nodo di ingresso vi é un permesso che viene consumato

– Un pacchetto che esce dalla rete genera un permesso nel nodo di uscita

– Gestione critica della distribuzione dei permessi in rete

• Tecniche a bucket – Utilizzate sia in accesso, sia tra nodi

– Due tecniche

• Leaky bucket

• Token bucket




Slide 69


• Controllo di flusso con leaky bucket

– Buffer pacchetti con capacità W (pacchetti)

– Un pacchetto trasmesso consuma un

permesso

– Ogni r secondi viene generato un permesso

– Perde pacchetti quando ne ha accumulati W

• Controllo di flusso con token bucket

– Buffer dei permessi con capacità W (permessi)

– Ogni r secondi viene generato un permesso

– Un pacchetto trasmesso consuma un

permesso

– Perde permessi in eccesso di W, ma non perde

a priori pacchetti

– Serve meglio sorgenti bursty

P e r m i t s

P a c k e t s

W 1

P s P b

1 / r

P e r m i t s

P a c k e t s

W

1

1 / r

P s P b




Slide 70


• Esempio

• Leaky bucket

• Token bucket

10

4.0

/4

000,25

1

8.0

/1

=

=

=

=

=

=

=

W

sr

sMbitP

byteL

sT

sT

sMbitP

b

p

OFF

ON

s

5 4 3 2 1 0

0 . 5 1 . 0 1 . 5 2 . 0 2 . 5 3 . 0

C [ M b i t / s ]

6

0

t [ s ]

C [ M b i t / s ]

5 4 3 2 1 0

t [ s ]

0 . 5 1 . 0 1 . 5 2 . 0 2 . 5 3 . 0

6

0

1 . 0 0 . 8 0 . 6 0 . 4 0 . 2 0

t [ s ]

0 . 5 1 . 0 1 . 5 2 . 0 2 . 5 3 . 0

C [ M b i t / s ]

1 . 2

0




Slide 71


• Esempio

• Leaky bucket

• Token bucket

10

3.0

/1

000,25

1

8.0

/1

=

=

=

=

=

=

=

W

sr

sMbitP

byteL

sT

sT

sMbitP

b

p

OFF

ON

s1 . 0

0 . 8

0 . 6

0 . 4

0 . 2

0

t [ s ]

0 . 5 1 . 0 1 . 5 2 . 0 2 . 5 3 . 0

C [ M b i t / s ]

1 . 2

0

0 . 5 1 . 0 1 . 5 2 . 0 2 . 5 3 . 0

C [ M b i t / s ]

0

t [ s ]

1 . 0

0 . 8

0 . 6

0 . 4

0 . 2

0

1 . 2

t [ s ]

0 . 5 1 . 0 1 . 5 2 . 0 2 . 5 3 . 0

C [ M b i t / s ]

0

1 . 0

0 . 8

0 . 6

0 . 4

0 . 2

0

1 . 2




Slide 72

Sommario

• Generalità


• Livello 3: rete

– Servizi forniti



– Protocollo X.25

• Prestazioni



Slide 73

Transport layer

Layer 3

Layer 2

User data

Layer 3

Header

LAP-B

Header

LAP-B

Trailer

FCSF A C F

X.25 - Generalità

• X.25

– Protocollo precedentemente più diffuso per reti dati

– Specifica l’interfaccia tra host (DTE) e rete (DCE)

• Architettura protocollare

– Strato fisico: X.21 oppure V.24 (cioé la EIA RS-232-F)

– Strato di collegamento: LAP-B (sottoinsieme di HDLC)

– Strato di rete: protocollo PLP (Packet Level Protocol)

• Servizi resi disponibili

– Chiamata virtuale (VC)

– Circuito virtuale

permanente (PVC)

LIVELLO 3: X.25



Slide 74

X.25 - Caratteristiche principali • Strato 2

– Unità informativa: trama

– Protocollo LAP-B, derivato da HDLC in modalità ABM

• Numerazione modulo 8, o modulo 128, o modulo 32768

• Protocollo ARQ Go-back-n modulo 8 o 128, Selective Repeat modulo 128 o 32768

• Strato 3

– Unità informativa: pacchetto

– Multiplazione

• LCI usa 12 bit

• Fino a 4095 circuiti virtuali possono essere multiplati su un unico collegamento fisico

– Controllo di sequenza (rilevazione perdita di pacchetti)

• Numerazione modulo 8, oppure 128, oppure 32768

• Realizzato con protocollo ARQ Go-back-n (NACK implementato da pacchetti REJ)


• Sliding window con opportuna apertura Ws (default Ws=2)

– Massima dimensione di pacchetto e finestra negoziate all’instaurazione

• Max packet size: 16, 32, 64, 128, 256, 512, 1024, 2048, 4096 bytes (default 128)

• Max window size: Ws=7, 127, 32767

LIVELLO 3: X.25



Slide 75

X.25 - Tipo di pacchetti

Data

Interrupt request

Receiver ready

Receiver not ready

Reject

Reset request

Reset confirmation

Restart request

Restart confirmation

Call request

Call accepted

Clear request

Clear confirmation

DTE DCE Type

Call set-up and clearing

Flow control

Interrupt confirmation

Resynchronize and error reporting

Data

Interrupt request

Receiver ready

Receiver not ready

Reset indication

Reset confirmation

Restart indication

Restart confirmation

Diagnostic

Incoming call

Call confirmation

Clear indication

Clear confirmation

DCE DTE

Interrupt confirmation

LIVELLO 3: X.25



Slide 76

X.25 - Formato dei pacchetti

• General format identifier (GFI)

– Qualifier bit (Q): distingue i pacchetti tra tipi di pacchetto (non standard, consente di distinguere dati di utente)

– Delivery confirmation bit (D): specifica se i riscontri devono essere locali (DTE-DCE, D=0) o end-to-end (DTE-DTE, D=1)

– Modulo: specifica il modulo di numerazione dei pacchetti (8, 128, 32768)

• Logical channel identifier (LCI)

– Logical group number (LGN)

– Logical channel number (LCN)

• 0: riservato

• 1 - x: PVC

• x - 4095: VC

• Packet type identifier (PTI)

– P(S): numerazione dei pacchetti in trasmissione

– P(R): numerazione dei pacchetti in ricezione

– More bit (M): indica (M=1) l’ultimo pacchetto da fornire all’entità di trasporto insieme ai precedenti (M=0)

12345678

1

2

3

Logical Channel Identifier

bit

GFI

Packet Type Identifier

Additional packet headerand/or user data

byte

LIVELLO 3: X.25



Slide 77

X.25 - Formato dei pacchetti

P ( R ) P ( S ) M 0 U s e r d a t a

3 1 3 1 ² 4 0 9 6 b y t e s

D a t a

P T I R e s e t / R e s t a r t / C l e a r

c a u s e

D i a g n o s t i c c o d e

( o p t i o n a l )

U s e r d a t a

( o n l y c l e a r r e q . )

8 b i t s 8 b i t s ² 3 2 b y t e s

R e s e t R e s t a r t C l e a r

r e q u e s t

P T I C a l l i n g D T E a d d r l e n g t h

C a l l i n g D T E a d d r e s s

C a l l e d D T E a d d r l e n g t h

C a l l e d D T E a d d r e s s

F a c i l i t i e s

l e n g t h F a c i l i t i e s U s e r d a t a

( o n l y c a l l r e q )

4 b i t s 4 b i t s 8 b i t s 3 2 / 1 2 8 b y t e s

P ( R ) T y p e M

3 1 4

R R R N R R E J

C a l l r e q u s t C a l l a c c e p t e d

P T I

R e s e t R e s t a r t C l e a r

I n t e r r u p t c o n f i r m a t i o n

P T I U s e r d a t a

² 3 2 b y t e s

I n t e r r u p t r e q u e s t

P T I D i a g n o s t i c

c o d e E x p l a n a t i o n

8 b i t s

D i a g n o s t i c

4 b i t s 4 b i t s

G F I L G N L C N

Q D M o d u l o

8 b i t s

L C I

8 b i t s

0 1 : m o d u l o 8 1 0 : m o d u l o 1 2 8

P T I

0 : d a t a p a c k e t 1 : c o n t r o l p a c k e t

LIVELLO 3: X.25



Slide 78

X.25 - Esempio di chiamata virtuale

i n c o m i n g c a l l

C a l l r e q u e s t

D a t a , 0 , 0 C a l l c o n f i r m a t i o n

D a t a , 1 , 0

D a t a , 2 , 1

D a t a , 0 , 0

C l e a r c o n f i r m a t i o n

C l e a r i n d i c a t i o n

R R , 3

D a t a , 1 , 3

C a l l a c c e p t e d

C l e a r c o n f i r m a t i o n

C l e a r r e q u e s t

A B

LIVELLO 3: X.25



Slide 79

Sommario

• Generalità


• Livello 3: rete

• Prestazioni

– Modello di nodo

– Parametri di traffico



Slide 80

2

N

1

2

M

1

T o l o c a l d e s t i n a t i o n s

F r o m l o c a l s o u r c e s

L e v e l 2 L e v e l 3 L e v e l 2

Modello di nodo

• Funzioni di livello di collegamento dati

– Ingresso: verifica trama

– Uscita: generazione e trasmissione trama

• Funzioni di livello di rete

– Memorizzazione dei pacchetti entranti

– Analisi del campo intestazione

– Instradamento dei pacchetti

– Controllo di flusso e di congestione

• Tempo di attraversamento del nodo da

parte di un pacchetto

– Ipotesi: tempo trascurabile nel primo stadio

– Componenti

• Attesa nella memoria di ingresso

• Elaborazione per instradamento

• Attesa nella memoria di uscita

• Trasmissione

ttpptptot TWTWDDD +++=+= •

PRESTAZIONI



Slide 83

Modelli

• Tempo di attraversamento

– Modello base: assunzione di indipendenza

• Processi di arrivo e di servizio in ogni nodo

• Processi di arrivo e di servizio in nodi diversi

– Tempo totale di attraversamento = Somma dei tempi di nodo

– Modelli reali di sorgente richiedono modellizzazione di nodo molto più

complessa

• Nodo reale: memoria finita

– Probabilità di perdita di pacchetti

PRESTAZIONI

Corso di RETI DI COMUNICAZIONE E INTERNET Modulo 1Parte 2 RETI DATI IN AREA GEOGRAFICA (WAN) Reti di...

Documents

Transcript of Corso di RETI DI COMUNICAZIONE E INTERNET Modulo 1Parte 2 RETI DATI IN AREA GEOGRAFICA (WAN) Reti di...