Guida

Università di Bologna - Corso di Laurea in Informatica

Reti di Calcolatori

Prof. Fabio Panzieri Dipartimento di Scienze dell’Informazione Università di Bologna Mura Anteo Zamboni 7 40127 Bologna tel.: 0512094508 email: [email protected]

Reti di Calcolatori (Fabio Panzieri)

1

Università di Bologna - Corso di Laurea in Informatica

Programma del corso RdC • Fondamenti: – Requisiti applicativi – Architetture di rete (OSI Internet) – Metriche prestazionali – Protocolli di comunicazione

• Tecnologie di rete: – – – – – – –

Hardware di rete Tecniche di codifica Trasmissione affidabile CSMA/CD Token ring Wireless (802.11) ATM

Reti di Calcolatori (Fabio Panzieri)

• Commutazione di pacchetto: RM,

– Datagram, Circuito virtuale – Commutazione, trasmissione – LAN estese

• Internetworking: – Bridge, Switch, Routers e il protocollo ARP, protocollo IP, Instradamento, Internet globale (subnetting, interdomain routing (BGP), IPV6)

• Protocolli end-to-end: – UDP, TCP

• Applicazioni: DNS, Mail, WWW 2

1

Università di Bologna - Corso di Laurea in Informatica

Riferimenti bibliografici • Libri di Testo: – L. L. Peterson, B. S. Davie, Computer Networks - A Systems Approach, 3rd Edition, Morgan Kaufmann, San Francisco, CA, 2003. • Disponibile anche nella traduzione italiana: L. Peterson - B. Davie, Reti di Calcolatori, APOGEO, Milano, 2004. ISBN 88-503-2158-9.

– F. Halsall, Computer Networking and the Internet - 5th Edition, Addison Wesley 2005. • Disponibile anche nella traduzione italiana.

• Ulteriori testi consigliati: – J. F. Kurose, K. W. Ross, Computer Networking - A Top-down Approach Featuring the Internet, Addison Wesley, 2001 – A. S. Tanenbaum, Computer Networks (Third Edition), Prentice Hall, Upper Saddle River, NJ, 1996.

Reti di Calcolatori (Fabio Panzieri)

3

Università di Bologna - Corso di Laurea in Informatica

Modalità d’ esame •

L'esame di RdC e' integrato con l'esame di LPR – questi due corsi danno luogo ad un solo voto – il voto finale dell'esame integrato RdC-LPR si ottiene dalla combinazione dei voti ottenuti nei due esami distinti – i due esami non sono svolti contestualmente – il voto ottenuto in ognuna delle due prove e' mantenuto valido per l'intero Anno Accademico.

•

RdC: prova scritta, obbligatoria, + prova orale, facoltativa – è possibile confermare il voto della prova scritta, senza svolgere la prova orale – è consentito “sedere” alla prova scritta quante volte si vuole – la consegna di una prova scritta annulla eventuale voto ottenuto in precedente appello

• •

LPR: Sviluppo di un progetto (relazione scritta + demo) Appelli d’esame: 6 per A.A.

Reti di Calcolatori (Fabio Panzieri)

4

2

Università di Bologna - Corso di Laurea in Informatica

Promemoria • Lucidi delle lezioni (3pp, formato pdf) disponibili all’URL: http://www.cs.unibo.it/~panzieri/Reti/prog.html User: RdCstudent Password: UniBoRdC90 • N.B.: – NON SOSTITUISCONO I LIBRI – non rispondo a email in cui si richiedono spiegazioni relative ai lucidi – non rispondo a email non provenienti da cs.unibo.it – se avete bisogno di chiariment i , l’orario di ricevimento è il mercoledi dalle 11:30 alle 13:00

Reti di Calcolatori (Fabio Panzieri)

5

Università di Bologna - Corso di Laurea in Informatica

Il problema • Costruire una “rete di elaboratori” capace di – crescere a dimensioni “globali” – supportare varietà di applicazioni (tlconf., VoD, distr. comp., …)

• Le domande principali cui vogliamo rispondere: – Quale tecnologia h/w e s/w occorre? – Quale architettura costruire per integrare le componenti in modo da offrire un “servizio” di comunicazione “efficace” (i.e.: efficiente - affidabile - rispondente ai requisiti applicativi)?

• Soluzione richiede di definire: – Cos’è una rete di elaboratori; – Perché costruirla; – Per chi costruirla.

Reti di Calcolatori (Fabio Panzieri)

6

3

Università di Bologna - Corso di Laurea in Informatica

Cos’ è una rete di elaboratori ? •

Cosa NON è: – Complesso di dispositivi che includono: • linee seriali che consentono il collegamento di terminali ad un mainframe; • rete telefonica; • cavi che consentono la trasmissione di segnali video, p.e. TV via cavo.

– Questi condividono le seguenti caratteristiche • Gestione di un particolare tipo di traffico (caratteri, voce, immagini); • Interconnettono dispositivi specializzati per quel tipo di traffico (terminali, telefoni, televisioni)

•

Rete di elaboratori: – Sistema di interconnessione di dispositivi programmabili – Dispositvi possono gestire una varietà di tipi di traffico (testo, immagini, voce) – Sistema non ottimizzato per un particolare tipo di traffico

Reti di Calcolatori (Fabio Panzieri)

7

Università di Bologna - Corso di Laurea in Informatica

Attualmente Host

Host

Application

Host

Web Server

Channel

Browser

Application

Host

Host

Cosa nasconde la nuvola? Reti di Calcolatori (Fabio Panzieri)

8

4

Università di Bologna - Corso di Laurea in Informatica

Pavone dopo l’incontro con un rullo compressore

Reti di Calcolatori (Fabio Panzieri)

9

Università di Bologna - Corso di Laurea in Informatica

Autopsia del “pavone”: componenti di rete (1) router • Milioni di dispositivi interconnessi • Hosts (o end-systems)

di

calcolo

server local ISP

workstation mobile

– pc’s, workstations, servers, PDA’s, …

– eseguono applicazioni di rete

regional ISP

• Link di comunicazione – fibra, rame, radio, satellite

• routers: trasmettono pacchetti contenenti dati attraverso la rete company network Reti di Calcolatori (Fabio Panzieri)

10

5

Università di Bologna - Corso di Laurea in Informatica

Autopsia del “pavone”: componenti di rete (2) Internet: “rete di reti” su planetaria – Topologia a gerarchia lasca

•

scala

• end systems connessi a ISPs locali mediante access networks (linee telefoniche, LANs, …)

router server local ISP

• ISPs locali connessi a ISPs regionali, connessi a ISPs nazionali, connessi a ISPs internazionali

mobile

regional ISP

Internet e intranets

•

workstation

– intranet: rete privata che usa tecnologia Internet, i cui hosts sono accessibili solo da hosts nella medesima intranet

company network Reti di Calcolatori (Fabio Panzieri)

11

Università di Bologna - Corso di Laurea in Informatica

Servizi di rete •

•

• •

Infrastruttura di comunicazione (tecnologia abilitante ) per supportare applicazioni distribuite: – WWW, email, giochi, commercio elettronico, banche dati, voto elettronico, teleconferenza, VoD, … Servizi di comunicazione: – connectionless – connection-oriented Protocolli: regolano la comunicazione i.e., controllano xmit/rcv di messaggi (e.g., TCP, IP, HTTP, FTP, PPP, …) Internet standards – RFC: Request for comments – IETF: Internet Engineering Task Force

Reti di Calcolatori (Fabio Panzieri)

12

6

Università di Bologna - Corso di Laurea in Informatica

Cos’e un protocollo? • Protocolli umani

•

• acquisto biglietti di viaggio • regole di precedenza in auto, in coda

• Messaggi specifici vengono trasmessi/ricevuti • Azioni specifiche vengono eseguite in conseguenza dei messaggi trasmessi e ricevuti.

Protocolli di rete: – simili a quelli umani – eseguiti da h/w e s/w anzichè da umani – tutte le comunicazioni di rete sono gestite da protocolli

– regolano interazioni fra umani

•

Protocolli di rete definiscono: – formato dei messaggi – azioni da intraprendere in seguito a trasmissione e ricezione di messaggi

• •

Formato: sintassi Azioni: semantica

Reti di Calcolatori (Fabio Panzieri)

13

Università di Bologna - Corso di Laurea in Informatica

Esempio di protocollo Un protocollo umano e un protocollo di rete:

buon giorno

TCP connection req.

‘n giorno

TCP connection reply

Che ora è?

Get http://www.cs.unibo.it/~panzieri

le 2:00

time

Reti di Calcolatori (Fabio Panzieri)

14

7

Università di Bologna - Corso di Laurea in Informatica

Architetture di protocolli • s/w di comunicazione strutturato gerarchicamente • Uso di “astrazione” per nascondere complessità • Astrazioni alternative ad ogni livello Internet Application programs Request/reply channel

Message stream channel

Applications TCP

UDP

Host-to-host connectivity

IP

Hardware

Network

Reti di Calcolatori (Fabio Panzieri)

15

Università di Bologna - Corso di Laurea in Informatica

Perché costruire reti di elaboratori? • Motivazione principale: – Supporto ad applicazioni di rete (p.e. FTP, E-mail, WWW, Ecommerce, digital libraries, …) di uso generale

• Osservazioni: – Crescita esplosiva del n. di utenti di Internet: • 1989: 100.000 computers approx. • 1992: 1.000.000 di computers approx. • 1999: 8, 9 milioni di computers; 160 milioni di utenti appox. (fonte: NetCenter News, Feb. 1999) • 2003: 150 milioni di computers, 500 milioni di utenti (approx.)

• Perché questa crescita? – Funzionalità di Internet accessibili mediante “general purpose workstations” – Basso costo dell’h/w + s/w necessario – La rete ha arricchito le sue funzionalità (p.e. servizi di teleconferenza) • Supporto di applicazioni multi-mediali (p.e., voce+testo+immagini)

Reti di Calcolatori (Fabio Panzieri)

16

8

Università di Bologna - Corso di Laurea in Informatica

Per chi costruire reti di elaboratori? • Utenti: utenti finali e fornitori di servizi (ISP, ASP) • Problema progettuale: utenti esprimono requisiti diversi – Utenti di rete: garanzia che ogni messaggio trasmesso dall’applicazione in uso sia consegnato senza errori in un qualche intervallo di tempo finito – ISP: sistema facile da amministrare, contabilizzare, in cui i guasti possono essere facilmente isolati, e che garantisca la raggiungibilità del servizio – Progettista: risorse di rete allocate efficientemente ed equamente a utenti diversi

• Requisiti principali: – Connettività – Condivisione di risorse (rapporto costi/benefici favorevole) – requisiti “non funzionali” soddisfatti (affidabilità, sicurezza, …)

prestazioni,

Reti di Calcolatori (Fabio Panzieri)

17

Università di Bologna - Corso di Laurea in Informatica

Connettività • Abilitare comunicazione fra computers interconnessi – Reti private possono voler limitare il n. di computers abilitati a comunicare far loro per ragioni di sicurezza/privacy – Reti pubbliche (p.e. Internet) progettate in modo da crescere arbitrariamente in dimensioni (p.e. n. di utenti, n. di elaboratori interconnessi, distanza geografica fra questi) • Reti pubbliche devono poter “scalare”

• Tipi di connettività – Diretta – Indiretta

• Connettività a vari livelli di astrazione: – Macchina (p.e. host-to-host) – Sistema operativo (p.e. driver-to-driver) – Processo (p.e. process-to-process)

=> protocolli specifici ad ogni livello Reti di Calcolatori (Fabio Panzieri)

18

9

Università di Bologna - Corso di Laurea in Informatica

Connettività diretta • Nodi connessi direttamente fra loro mediante qualche supporto fisico • Componenti di base: – link: cavo coassiale, fibra ottica, canale satellitare, … – nodo: elaboratore “general-purpose” (workstation), dedicato (p.e. file server, router)

elaboratore

• Link diretti a) Punto-punto b) Accesso multiplo –

link condiviso

–

distanza limitata

–

n. di nodi limitato (con l’eccezione del satellite)

Reti di Calcolatori (Fabio Panzieri)

19

Università di Bologna - Corso di Laurea in Informatica

Figure 1.12 Satellite systems: (a) broadcast television; (b) data communications Halsall, Computer Networking and the Internet, 5th Edition © Pearson Education Limited 2005

Canale satellitare: - ampiezza di banda elevata (500 MHz) - fornisce linee ad alta velocità sfruttando “TDM” del canale (cf. più avanti) Reti di Calcolatori (Fabio Panzieri)

20

10

Università di Bologna - Corso di Laurea in Informatica

Connettività indiretta • Reti commutate (switched networks) – commutazione di circuito vs. commutazione di pacchetto

• I nodi connessi ad almeno due link eseguono s/w che può trasmettere dati ricevuti da un link su un altro link. Sono chiamati switches, e formano la switched network. – I nodi interni alla “nuvola” implementano la switched network. – I nodi esterni alla “nuvola” usano la rete (i.e., hosts).

Reti di Calcolatori (Fabio Panzieri)

21

Università di Bologna - Corso di Laurea in Informatica

•

Rete consiste di centrali di commutazione (switching exchange)

•

host/terminal

– p.e.: rete telefonica – connesso a exchange locale – identificato da numero/indirizzo di rete unico

•

exchange stabiliscono circuito fisico tra A e B (via “signaling”) – circuito riservato fino al termine della comunicazione Figure 1.5 Circuit-switched network schematic – rilasciato al termine della Halsall, Computer Networking and the Internet, 5th Edition © Pearson Education Limited 2005 comunicazione

Reti di Calcolatori (Fabio Panzieri)

22

11

Università di Bologna - Corso di Laurea in Informatica

• circuito fra A e B utilizza porzione variabile di banda – usa risorse secondo necessità

• trasmette pacchetti dimensione max. prefissata

di

Figure 1.6 Packet-switching network principles: (a) connection-oriented Halsall, Computer Networking and the Internet, 5th Edition © Pearson Education Limited 2005

Reti di Calcolatori (Fabio Panzieri)

23

Università di Bologna - Corso di Laurea in Informatica

Figure 1.6 Packet-switching network principles: (b) connectionless Halsall, Computer Networking and the Internet, 5th Edition © Pearson Education Limited 2005 Reti di Calcolatori (Fabio Panzieri)

24

12

Università di Bologna - Corso di Laurea in Informatica

Connettività indiretta • Reti possono essere connesse ad altre reti per formare un internetwork (Internet e’ una specifica istanza di internetwork). – Nodo connesso a due o più reti è chiamato router o gateway, e svolge le funzioni di uno switch. Host

Internetwork

router/gateway

Reti di Calcolatori (Fabio Panzieri)

25

Università di Bologna - Corso di Laurea in Informatica

Connettività responsabilità principali • Garantire: R1: Utilizzo ottimale dei canali di comunicazione • Strategie di commutazione del canale

R2: Raggiungibilità delle risorse in rete • Identificazione • Indirizzamento • Instradamento

Reti di Calcolatori (Fabio Panzieri)

26

13

Università di Bologna - Corso di Laurea in Informatica

R1: strategie di commutazione • Commutazione di circuito (p.e. rete telefonica): – circuito dedicato fra src e dst; – consente trasmissione/ricezione di flusso di bit – La rete • stabilisce circuito dedicato tra src e dst attraverso serie di link; • src invia flusso di bit su circuito

• Commutazione di pacchetto: store-and- forward mediante send/receive di messaggi (o pacchetti) di dimensione max. predefinita: – Nodi scambiano pacchetti fra loro • ogni pacchetto contiene dst.addr.

– Ogni switch • carica in memoria (store) locale i pacchetti che riceve, e • instrada (forward) ogni pacchetto sul link appropriato.

• Reti di computer: a commutazione di pacchetto (perché …) Reti di Calcolatori (Fabio Panzieri)

27

Università di Bologna - Corso di Laurea in Informatica

R1: commutazione di pacchetto • Problema: condivisione di risorse; i.e., condivisione della rete (links e switches) – multiplexing di flussi di pacchetti su singolo link. – Ogni switch trasmette un po’ alla volta parte dei dati di ciascun host src – Ogni host src che vuole trasmettere ne ha la possibilità.

Src1

Rcv1

Src2

Rcv2

Src3 Reti di Calcolatori (Fabio Panzieri)

Switch 1

Switch 2

Rcv3 28

14

Università di Bologna - Corso di Laurea in Informatica

R1: commutazione di pacchetto – Messaggio (di dimensioni arbitrarie) da host src frammentato in blocchi di dimensione prefissata (pacchetti) – Switch usa qualche strategia per combinare pacchetti (multiplexing) in un singolo flusso sul link (p.e., round-robin: un pacchetto da ogni src). – A dst, switch effettua demultiplexing del flusso combinato in flussi separati per le relative dst.

Src1 Switch …

Src2

Dst

Src3 Reti di Calcolatori (Fabio Panzieri)

29

Università di Bologna - Corso di Laurea in Informatica

R1: Multiplexing • STDM (Synchronized Time Division Multiplexing) – Uso del link diviso in “finestre” (o “quanta”) di tempo – Ogni flusso riceve un quantum di tempo durante il quale può trasmettere (tecnica di round-robin per assegnare i quanta di tempo)

• FDM (Frequency Division Multiplexing) – Ogni flusso trasmesso usando una frequenza diversa

• Vantaggi – Semplici da implementare

• Svantaggi – Se src non ha dati da trasmettere il quantum o la frequenza assegnatele sono inutilizzate (i.e. il canale rimane “idle”) – Max n. di flussi deve essere noto in anticipo per poter definire i quantum o la frequenza da assegnare ad ogni src.

Reti di Calcolatori (Fabio Panzieri)

30

15

Università di Bologna - Corso di Laurea in Informatica

R1: STDM (round-robin) Host

SWITCH

A

C2 A2 D2 D1 B1 C1 A1

B

buffer

D1 ….…. A1

clock

C D

D

A

C

B

Output

Quantum per flusso B

Reti di Calcolatori (Fabio Panzieri)

31

Università di Bologna - Corso di Laurea in Informatica

R1: Statistical Multiplexing • = STDM: link assegnato ad ogni flusso per intervallo di tempo. • ≠ STDM: flusso di dati trasmesso su richiesta anziché in finestra di tempo predefinita. • Vantaggi: – if singolo flusso di dati then accesso al link senza attesa – Eliminazione tempi di “non utilizzo” del canale => commutazione di pacchetto efficiente

• Dimensione dell’intervallo di tempo assegnato ad un flusso? – Statistical multiplexing definisce max size del blocco (i.e. pacchetto) che flusso può trasmettere in un dato istante

Reti di Calcolatori (Fabio Panzieri)

32

16

Università di Bologna - Corso di Laurea in Informatica

R1: Statistical MPX Host

SWITCH

A D1

B

B1 C1 A3 A2 A1

…… A3 A2 A1

buffer

C

clock D

Ciclo di trasmissione

Q4

Q1

Q3

Q2

Output Quanta di tempo

A1

A2

A3

C1

B1

Q1

Q2

Q3

Q4

Q1

t

Reti di Calcolatori (Fabio Panzieri)

33

Università di Bologna - Corso di Laurea in Informatica

R1: Statistical Multiplexing

(dimensionamento quantum di tempo) Implicazioni: – Trasmissione: messaggi di lunghezza arbitraria devono essere frammentati in pacchetti – Ricezione: pacchetti devono essere riassemblati a formare messaggio originale. – Ogni flusso invia sequenza di pacchetti su link fisico – Decisione su quale flusso servire presa dallo switch al momento della trasmissione di ogni pacchetto – if singolo flusso then switch trasmette sequenza di pacchetti di quel flusso – Politica dello switch di trasmissione dei pacchetti: FIFO – Se switch riceve pacchetti più velocemente di quanto possa trasmetterli su link, li deve mantenere (“bufferizzare”) al suo interno • if buffer full then scarta pacchetti; /* congestione allo switch */

Reti di Calcolatori (Fabio Panzieri)

34

17

Università di Bologna - Corso di Laurea in Informatica

R2: raggiungibilità delle risorse • Nome: cosa si vuole (identificatore astratto di una risorsa) • Indirizzo: dove si trova (identificatore della locazione geografica della risorsa) • Rotta (route): come ci si arriva (percorso) • WANs, MANs, LANs, DANs – WANs: reti geografiche a commutazione di pacchetto • Dimensione arbitraria/planetaria

– MANs: reti distribuite su scala cittadina (fibra ottica, ATM) • Dimensione < qualche decina di km

– LANs: reti distribuite localmente (p.e. dipartimento) • Dimensione < 1Km

– DANs: reti distribuite su scala molto ridotta, p.e. scrivania (e.g., bus sostituito da switch ATM, canali Bluetooth) • Dimensione ≤ 10m

– NOC: Network On Chip • Dimensione ≤ 0.1 m Reti di Calcolatori (Fabio Panzieri)

35

Università di Bologna - Corso di Laurea in Informatica

R2: indirizzamento e instradamento (addressing e routing)

• Connettività: src e dst identificabili univocamente. • Identificazione: mediante indirizzo

– Indirizzo: stringa di bytes usata per identificare localizzazione geografica di un nodo – Tipi di indirizzo: • unicast: singolo nodo dst; • broadcast: tutti i nodi in rete; • multicast: qualche sottoinsieme dei nodi in rete

la

• Routing: processo di determinazione dell’instradamento dei messaggi verso la dst, basato sull’indirizzo di dst.

– Switches e routers costruiscono percorso (route) da src a dst sulla base dell’indirizzo dst.

Reti di Calcolatori (Fabio Panzieri)

36

18

Università di Bologna - Corso di Laurea in Informatica

Figure 1.4 Communication modes: (a) unicast Halsall, Computer Networking and the Internet, 5th Edition © Pearson Education Limited 2005 Reti di Calcolatori (Fabio Panzieri)

37

Università di Bologna - Corso di Laurea in Informatica

Figure 1.4 Communication modes: (b) broadcast Halsall, Computer Networking and the Internet, 5th Edition © Pearson Education Limited 2005 Reti di Calcolatori (Fabio Panzieri)

38

19

Università di Bologna - Corso di Laurea in Informatica

Figure 1.4 Communication modes: (c) multicast Halsall, Computer Networking and the Internet, 5th Edition © Pearson Education Limited 2005 Reti di Calcolatori (Fabio Panzieri)

39

Università di Bologna - Corso di Laurea in Informatica

Funzionalità • Connettività e tecniche di condivisione di risorse non sufficienti a garantire utilizzabilità dell’infrastruttura di comunicazione • Obbiettivo principale da conseguire: – fornire servizi di comunicazione che rispondano a requisiti applicativi

1º approccio: – applicazione stessa implementa funzionalità richieste – inefficace, implica ridondanza di implementazioni analoghe

2º approccio: – applicazioni condividono requisiti => progettista fornisce astrazioni comuni a classi di applicazioni

Reti di Calcolatori (Fabio Panzieri)

40

20

Università di Bologna - Corso di Laurea in Informatica

Funzionalità • Problema: – Identificare requisiti applicativi comuni, p.e.: • garanzia di consegna messaggi • ordinamento messaggi • privacy/sicurezza,...

• Obiettivo: – Nascondere all’applicazione complessità di rete – Fornire molteplicità di servizi di comunicazione che l’applicazione può scegliere

• Metodo: – 1. Catturare i requisiti di diverse classi di applicazioni – 2. Identificare requisiti comuni – 3. Incorporare nel s/w di rete funzionalità che soddisfano 2.

Reti di Calcolatori (Fabio Panzieri)

41

Università di Bologna - Corso di Laurea in Informatica

Cattura dei requisiti applicativi: esempi •

Costruire servizi di comunicazione per applicazioni di FTP, Digital Library (DL), VoD, Teleconferenza (Tlcf)

•

FTP: Create, Open, R/W, Seek, Close, Delete file remoto da client a server – Client(read) • Send_request(R_FILE); /*richiesta operazione read e f.name (msg breve)*/ • Get_reply(FILE); /*riceve risposta (file)*/ – Server • Get_request(…); /* riceve breve msg */ • Work(…); /* esegue operazione */ • Send_reply(…) /*trasmette risultato */ – In scrittura avviene l’opposto (msg di richiesta lungo, breve “reply”) – Modalità di interazione applicativa: request/reply

•

DL – (alla WWW) client può richiedere singola pagina o più pagine da server – Modalità di interazione applicativa: request/reply

Reti di Calcolatori (Fabio Panzieri)

42

21

Università di Bologna - Corso di Laurea in Informatica

Cattura dei requisiti applicativi • VoD: – Client invia richiesta di fetching di video, Server genera flusso di “frames” di cui client deve effettuare “rendering” – Client accetta perdita di qualche frame (sotto una certa soglia) 1º approccio: • Server scarica su client l’intero video • Client attende di ricevere l’intero video • Client effettua rendering => Client richiede molta memoria; non richiede synch. Srvr/rendering

2º approccio: • Server invia blocchi di sequenze di frames • Client effettua rendering appena le riceve => Riduce requisiti di memoria del Client; richiede synch. Srvr/rendering

Modalità di interazione applicativa: • flusso di frames unidirezionale Reti di Calcolatori (Fabio Panzieri)

43

Università di Bologna - Corso di Laurea in Informatica

Cattura dei requisiti applicativi •

Teleconferenza (Tlcf) Apparentemente come VoD (i.e. flusso di frames), ma 1. Comunicazione soggetta a vincoli di tempo – Speaker deve avere canale disponibile per la durata del suo intervento 2. Flusso di frames multi-direzionale – Ogni speaker deve poter interagire con ogni altro speaker

In Tlcf, ritardi possono rendere sistema inutilizzabile – in VoD un ritardo di 10’’ dalla richiesta del cliente alla ricezione della prima sequenza di frames è ininfluente – in Tlcf ritardo di flusso da uno speaker può creare interferenze con gli altri speakers

Modalità di interazione applicativa: – flusso di frames multi-direzionale •

molteplicità di destinazioni per ogni flusso

Reti di Calcolatori (Fabio Panzieri)

44

22

Università di Bologna - Corso di Laurea in Informatica

Soddisfare i requisiti applicativi • Applicazioni esaminate richiedono: – Request/reply – Flusso di messaggi

• Request/reply

– Garantisce delivery messaggi trasmessi – Protegge “privacy” dei dati trasmessi

• Flusso di messaggi

– Parametrico: consente half-duplex (VoD) e full-duplex (Tlcf) – Non garantisce delivery di tutti i messaggi • i.e. % frames possono essere “perse” senza danno

– Garantisce ordinamento msg’s

• i.e. msg’s ricevuti nello stesso ordine in cui sono trasmessi

– Garantisce privacy e integrità dei dati – Supporta multicasting

• sia per Tlcf sia per VoD a molteplicità di utenti finali

Reti di Calcolatori (Fabio Panzieri)

45

Università di Bologna - Corso di Laurea in Informatica

Architettura risultante •

Ogni protocollo può supportare applicazioni diverse – RRP (RequestReplyProtocol), MSP (MessageStreamProtocol), HHP (Host-toHostProtocol) – ogni livello può implementare protocolli diversi – ogni protocollo mantiene specifica interfaccia

Video Client

Digital library Client

FS

L3

FS client

Digital Library

Video Server

I2 MSP

RRP

L2

RRP

MSP

I1 HHP

Reti di Calcolatori (Fabio Panzieri)

L1

HHP

46

23

Università di Bologna - Corso di Laurea in Informatica

Funzionalità: “dove” implementarle? • 1º approccio: – S/w di rete fornisce comm’s host-to-host (flusso di pacchetti fra hosts remoti) – Hosts implementano IPC Pros: Semplifica switches (trasmissione di pacchetti, solamente) Cons: Complessità di IPC negli hosts

• 2º approccio: – IPC implementato da switches Pros: rete può supportare dispositivi “ottusi” (p.e. telefoni) Cons: complessità implementazione switch aumenta

Reti di Calcolatori (Fabio Panzieri)

47

Università di Bologna - Corso di Laurea in Informatica

Affidabilità • •

Consegna affidabile di messaggi: requisito fondamentale Non esistono canali di comunicazione “perfetti” – Tolleranza ai guasti • problemi h/w e s/w a vari livelli • Problemi h/w • • • •

Workstation crash e re-boot Cavo danneggiato fisicamente Interferenze elettriche Buffer overflow (congestione) in switch

• Problemi s/w •

•

Trasmissione pacchetti a destinazioni arbitrarie (switch seleziona link errato)

N.B.:

– Definire servizi di comunicazione “utili” richiede conoscenza sia dei requisiti applicativi, sia dei limiti della tecnologia usata. – Difficoltà: • coprire gap fra requisiti applicativi e limiti tecnologici • importanza del modello dei guasti (i.e., che sia realistico)

Reti di Calcolatori (Fabio Panzieri)

48

24

Università di Bologna - Corso di Laurea in Informatica

Affidabilità • Classi di guasti Livello

Causa

Bit

campi magnetici, interferenze elettriche, “burst” di bits errore: 10-6, 10-7 (rame); 10-12, 10-14 (fibra ottica)

•

Packet

congestione (switch buffer overflow), switch misrouting

Node

link fisico danneggiato, crash di nodo

Errori “burst”: sequenza di bit corrotta

Reti di Calcolatori (Fabio Panzieri)

49

Università di Bologna - Corso di Laurea in Informatica

BER • Misura dell’affidabilità di un canale – tasso medio di errore sui bit (Bit Error Rate - BER) • probabilità che un bit sia danneggiato/alterato in trasmissione in un determinato intervallo di tempo – in canale a bit rate costante, BER equivale a probabilità che un bit in un n. definito di bit sia danneggiato. – p.e. BER = 10-3 => 1 bit errato ogni 1000 bit trasmessi • BER noto => blocco dati dimensionato in modo da minimizzare probabilità di errore – p.e. BER = 10-3 => block size << 1000 bit • in generale, dato P (probabilità BER) e N (n. di bit in un blocco), se gli errori sono casuali, la probabilità PB che blocco contenga un errore sui bit è PB = 1 - (1 - P)N • che si approssima NxP, se NxP<1 Reti di Calcolatori (Fabio Panzieri)

50

25

Università di Bologna - Corso di Laurea in Informatica

BER (esempio) • calcolare dimensione massima dei blocchi da utilizzare in un canale con BER medio = 10-4, supponendo che la probabilità che un blocco contenga un errore, e quindi venga scartato, sia 10-1 • Soluzione approssimata PB = 1 - (1 - P)N => approssimazione PB = NxP 0,1 = N x 10-4 1/10 = N/10000 N = 10000/10 = 1000 bit

Reti di Calcolatori (Fabio Panzieri)

51

Università di Bologna - Corso di Laurea in Informatica

Guasti Interferenza Livello bit

… 00111 …

… 00011 canale di comunicazione

buffer overflow

Livello Packet

P5

buffer P4 P3 P2 P1

P5 •

Switch

Tecniche di recovery: basate su uso di “ridondanza” – Livello bit: dell’informazione (p.e. Error Correcting Codes) – Livello packet: delle trasmissioni (i.e. ritrasmissione di pacchetti)

Reti di Calcolatori (Fabio Panzieri)

52

26

Università di Bologna - Corso di Laurea in Informatica

Guasti crash di nodo

Livello Node

switch

switch

Host A switch

Host B switch

INTERNET

• Tecniche di recovery: basate su uso di “ridondanza” – Livello node: ridondanza dei cammini/percorsi fra gli hosts Reti di Calcolatori (Fabio Panzieri)

53

Università di Bologna - Corso di Laurea in Informatica

Performance • •

Prestazioni delle computazioni in ambito distribuito dipendono anche da efficienza con cui la rete consegna dati. Metriche principali: – Bandwidth (o throughput): numero di bit che possono essere trasmessi in un determinato intervallo di tempo. • P.E. 10 Mbps = 107 bit al secondo. • Bandwidth: tempo di trasmissione di ogni singolo bit. – P.E. in rete da 10Mbps, 0.1 µs (microsecondi) necessari a trasmettere un bit.

– Latency (o ritardo): tempo necessario a singolo bit per percorrere distanza da src a dst. – P.E. rete intercontinentale: 24 ms (millisecondi) •

a 2.3 x 108m/s, in 24 ms un bit percorre 5520 Km (distanza Londra - New York = 5585 Km)

– Throughput: sinonimo di bandwidth, oppure: • prestazioni misurate di un sistema. – P.E.: 2 nodi comunicanti via link a 10 Mbps possono raggiungere throughput = 2 Mbps (causa: s/w overheads)

Reti di Calcolatori (Fabio Panzieri)

54

27

Università di Bologna - Corso di Laurea in Informatica

Bandwidth: Rappresentazione lineare •

Bit trasmessi con data bandwidth rappresentabili mediante ampiezza: – Canale da 1Mbps => 1 s frazionato in 1.000.000 µs => 1b/µs – 1 s rappresentato graficamente come distanza fra due punti => 1 bit: impulso di ampiezza 1 µs

1 µs 1 secondo – Canale a 2Mb/s: un bit trasmesso ogni 0.5 µs

1 µs N.B.

1 secondo

1 s = 103 ms (millisec.) = 106µs (microsec) = 109 ns (nanosec.) = 1012 ps (picosec.) => 1ms = 10-3 s; 1µs = 10-6 s; 1ns = 10-9 s; 1ps = 10-12 s. 10 Mbps = 10.000.000 bps => 1/10.000.000 s/bit = 1/10 x 10-6 s/bit = 1/10 µs/bit

Reti di Calcolatori (Fabio Panzieri)

55

Università di Bologna - Corso di Laurea in Informatica

Latenza • •

Tempo impiegato da un bit a percorrere distanza src -> dst Latenza formata da: –

ritardo di propagazione della velocità della luce; •

–

ritardo di trasmissione: tempo necessario a trasmettere unità dati

–

ritardo di accodamento (queueing delay):

• •

•

funzione di bandwidth e dimensione pacchetto tempo speso nei buffer degli switch (causato da store and forward).

Latenza = Propagazione + Trasmissione + Accodamento – –

•

variabile da canale a canale, a seconda del “mezzo” di cui il canale è costituito; p.e.: – nel vuoto: 299.792.458 m/s (circa 3 x 108 metri/secondo, i.e. 300.000 Km/s) – su rame, circa 2.3 x 10 8 m/s – su fibra, circa 2 x 108 m/s

Propagazione = distanza/velocità della luce Trasmissione = dimensione_dati/bandwidth

Round Trip Time (RTT): latenza src -> dst -> src

Reti di Calcolatori (Fabio Panzieri)

56

28

Università di Bologna - Corso di Laurea in Informatica

Latenza vs. Bandwidth • Importanza di bandwith e latenza dipende da applicazione • Es.1: applicazione “latency-bound” – client invia un byte (B) a server, server risponde con un B a client (ip.: ritardo di elaborazione = 0, p.e. ping) • sensibile a latenza (ovvero, RTT): applicazione percepisce tempo di risposta, p.e.: RTT = 100 ms => applicazione esegue più “lentamente” che se RTT = 1 ms

• Bandwidth è irrilevante: – Bandwidth = 100 Mbps = 100.000.000 bps => (1/100.000.000) s/b = (1/100 x 10-6) s/b = (1/100)µs/b => ritardo di trasmiss. di 1 B (B = 8 bit) = (8 x 1/100)µs = 8/100µs = 0.08 µs

– Bandwidth = 1 Mbps = 1.000.000 bps => (1/1.000.000) s/b = 10-6 s/b = 1µs/b => ritardo di trasmiss. di 1 B = 8µs

⇒ Differenza trascurabile

Reti di Calcolatori (Fabio Panzieri)

57

Università di Bologna - Corso di Laurea in Informatica

Latenza vs. Bandwidth • Es.2: applicazione “bandwidth bound” – programma trasmette immagine di 25 Mbyte: – sensibile a bandwidth

• Bandwidth domina prestazioni – Dimensione-dati = 25MB file => 25MB = (25 x 220 x 8) b = 200Mb (dimensione file)

– Poiché ritardo di trasmissione (rdt) = dimensione_dato/bandwidth • BD = 10Mbps => rdt = 200Mb/10Mbps = 20 s • BD = 100Mbps => rdt = 200Mb/100Mbps = 2 s

• Latenza è irrilevante – RTT = 100 ms => tempo di risposta (un bit di ack.) = 20.1 s – RTT = 1 ms => tempo di risposta (un bit di ack.) = 20.001 s Differenza trascurabile

Reti di Calcolatori (Fabio Panzieri)

58

29

Università di Bologna - Corso di Laurea in Informatica

MB, Mbps, KB, Kbps • M = 106 oppure M = 220, K = 103 oppure K = 210 • Bandwidth: gestita dal clock di sistema trasmittente – Misurata con metrica di clock • Clock a 10MHz trasmette bits a 10Mbps • poiché M (in MHZ) indica 106 => M in Mbps indica 106 bps (e K in Kbps indica 103)

• Messaggio: risiede in memoria – misurato secondo metrica di memoria del computer – memoria misurata con potenze di 2 – KB (Kb) indica 210 bytes (210 bits), MB (Mb) indica 220 bytes (220 bits),

• Messaggio di 32 KB trasmesso su canale con bandwidth = 10 Mbps => 32 x 210 x 8 bits trasmessi ad una velocità di 10 x 106 bps.

Reti di Calcolatori (Fabio Panzieri)

59

Università di Bologna - Corso di Laurea in Informatica

Delay x Bandwidth • • • • •

Canale di comunicazione fra due processi: pipe (condotto) Indica quanti bit src deve trasmettere prima che il primo bit trasmesso sia ricevuto a dst Delay = lunghezza della pipe Bandwidth = diametro della pipe Delay x Bandwidth = volume (i.e.,n. di bits che pipe può contenere)

bandwidth

delay

Reti di Calcolatori (Fabio Panzieri)

PIPE

60

30

Università di Bologna - Corso di Laurea in Informatica

Delay x Bandwidth •

P.e.: link intercontinentale, latenza = 50 ms, bandwidth = 45 Mbps DxB = 50 x 10-3 s x 45 x 106 b/s = = ((5 x 10)/1000)s x (45 x 106)b/s = = (5/100) x 45 x 106 b = 2.25 x 106 b Poiché 106 b = (1.000.000/8)B = 125.000B e (125.000/1024)B = = 122.07 KB => DxB = 2.25 x 122.07 KB = 275 KB (circa)

•

Src attende 1 bit di ack da dst

•

Se dst vuole richiedere STOP di trasmissione

=> src può inviare il doppio del delay x bandwidth di dati prima di ricevere ack => dst può ricevere il doppio del delay x bandwidth di dati prima che src riceva segnale di STOP

Reti di Calcolatori (Fabio Panzieri)

61

Università di Bologna - Corso di Laurea in Informatica

Esempio 1 •

Calcolare Ritardo di Trasmissione RT necessario a trasmettere un file di 1000KB assumendo Bandwidth BW= 1.5Mbps

Svolgimento: 1. Conversione in bit di File_size = 1000KB = 103 x 210 x 23 b 2. RT = Size/BW = File_size/BW = (103 x 210 x 23 )b/(1.5 x 106)bps = (103 x 213)/1500000) s = 8192000/1500000 s ≈ 5.46 s

Reti di Calcolatori (Fabio Panzieri)

62

31

Università di Bologna - Corso di Laurea in Informatica

Esempio 2 •

Calcolare tempo totale TT necessario a trasmettere un file di 1000KB assumendo 1. BW= 1.5Mbps, RTT = 100 ms, pkt-size = 1KB 2. Prima di trasmettere file, src e dst eseguono “handshake” (costo = 2RTT) 3. Dopo trasmissione di ogni pacchetto, src attende 1 RTT

Svolgimento – –

–

Src deve frammentare file in pkts di 1KB: File_size = 1000KB => 1000 pkts di pkt_size = 1KB = 8Kb Per ogni pacchetto impiega tempo di trasmissione pkt-time = (pkt_size/BW) + RTT = = (8 x 210)b/(1.5 x 106 ) bps + RTT = (8192/1500000)s + 0.1s ≈ ≈ 0.0055 s + 0,1 s = 0,1055 Per 1000 pkts + handshake TT = 1000 x 0.1055s + 0.2s = 105.7 s

Reti di Calcolatori (Fabio Panzieri)

63

Università di Bologna - Corso di Laurea in Informatica

Esempio 3 •

Dato un canale con BW = 1.5 Mbps e RTT = 100ms, calcolarne la capacità DxB (i.e., il delay x bandwidth).

•

Svolgimento: 1. RTT = 100ms ⇒ delay (unidirezionale) = 50 ms = 50 x 10

-3

s;

2. BW = 1.5 Mbps = 1.5 x 106 bps. 3. DxB = 50 x 10-3s x 1.5 x 106bps = 50 x 1.5 x 103 b = 75000 b ≈ 73Kb

Reti di Calcolatori (Fabio Panzieri)

64

32

Università di Bologna - Corso di Laurea in Informatica

Esempio 4 • Computers A e B connessi da un canale con DxB = 73Kb e RTT = 100ms. A trasmette a B pkts di pkt_size = 1KB; quanti pkts potrà trasmettere A prima di ricevere 1 bit di ack da B? • Svolgimento – RTT = 100ms ⇒ delay (unidirezionale) = 50 ms (i.e.,tempo impiegato da 1 bit di ack da B ad A) ⇒ ⇒ A può trasmettere per 100ms prima di ricevere ack da B – Canale ha DxB = 73Kb in 50ms, => capacità C doppia in 100ms; C = 73Kb x 2 = 146Kb = (146/8)KB ≈ 18KB

– C = 18KB, singolo pkt da A a B = 1KB => A potrà inviare 18 pkts a B prima di ricevere 1 bit ack da B.

N.B.: pkts da A saturano pipe; non necessariamente ricevuti da B.

Reti di Calcolatori (Fabio Panzieri)

65

Università di Bologna - Corso di Laurea in Informatica

Esempio 5 • Gli elaboratori H1 e H2 sono interconnessi da una rete con bandwidth = 10Mbps. L’elaboratore H1 trasmette un messaggio M di 2 KB all’elaboratore H2. • Assumendo che – la rete possa trasmettere pacchetti contenenti al massimo 1500 B di dati, senza introdurre errori, e – i protocolli di rete introducano un overhead di 26 byte per pacchetto trasmesso, e

calcolare il tempo di trasmissione del messaggio M da H1 a H2.

Reti di Calcolatori (Fabio Panzieri)

66

33

Università di Bologna - Corso di Laurea in Informatica

Soluzione •

Il tempo di trasmissione (TT) di un messaggio è: – –

•

Calcoliamo le dimensioni dei pacchetti da trasmettere. –

•

TT = dimensione-dato/bandwidth Il messaggio di 2KB (i.e. 2048 Bytes) deve essere frammentato in due frammenti M1 e M2, e trasmesso in due pacchetti distinti. Quindi, il tempo di trasmissione di M sarà dato dalla somma dei tempi di trasmissione dei due pacchetti contenenti M1 e M2. Poichè il protocollo di rete può trasportare 1500B max di dati, e introduce 26B di overhead (HDR), le dimensioni dei due paccketti da trassmettere saranno: Pkt1 = HDR + M1 = 26B + 1500B = 1526B Pkt2 = HDR + M2 = 26B + 548B = 574B

Da cui discende che: TT = TT_Pkt1 + TT_Pkt2 = (1526B/10Mbps) + (574B/10Mbps) = 2100B/10Mbps = 16800b/10000000bps = 0.00168s = 1.68 ms

Reti di Calcolatori (Fabio Panzieri)

67

Università di Bologna - Corso di Laurea in Informatica

Architetture di rete • Requisiti applicativi per – connettività affidabile, ad elevate prestazioni, sicura … – scalabilità, adattabilità ad accogliere nuove tecnologie, …

introducono complessità nel s/w di rete • Architettura di rete: schema progettuale che guida la realizzazione dell’infrastruttura di comm’s H/W e S/W richiesta. • Software di rete progettato come “gerarchia di servizi”: – alla base: servizi offerti dall’hardware; – si aggiunge sequenza di “livelli” (o “strati”) software (moduli software), ciascuno dei quali fornisce un livello di servizi più elevato (più “astratto”).

Reti di Calcolatori (Fabio Panzieri)

68

34

Università di Bologna - Corso di Laurea in Informatica

Architetture di rete • Principio progettuale: servizi forniti da un livello implementati usando i servizi forniti dal livello sottostante. – Medesimo principio usato per progettare qualunque sistema complesso. • p.e., file system progettato gerarchicamente: partendo da servizi di basso livello h/w di lettura/scrittura di blocchi di disco, si costruiscono servizi di più alto livello di create, open, close, read, write di oggetti chiamati files.

• L’insieme di livelli l’architettura

H/W

e

S/W

di

rete

ne

costituiscono

– l’architettura descrive le funzionalità di base di ogni livello, in modo da consentire al progettista di costruire i livelli necessari.

Reti di Calcolatori (Fabio Panzieri)

69

Università di Bologna - Corso di Laurea in Informatica

Esempi – Fig. (a): architettura a quattro livelli. • L0: xmit/rcv flusso di bit • L1, usa L0 per implementare scambio di pacchetti host-to-host • L2 usa L1 (host-to-host) per implementare scambio di messaggi process-toprocess. • Programmi applicativi in L3 usano i servizi forniti da L2 per costruire applicazioni specifiche (p.e., file transfer, email,…).

– Fig. (b): ogni livello può fornire uno o più tipi di servizi, p.e. L2.

Application programs

L3

Request/Reply channel

L2

Host-to-host connectivity

L1

Hardware

L0

(a) Reti di Calcolatori (Fabio Panzieri)

Application programs R/R channel MSG Stream Host-to-host connectivity Hardware

(b) 70

35

Università di Bologna - Corso di Laurea in Informatica

Protocolli • •

“Building blocks” di architettura di rete Ogni protocollo mantiene 2 interfacce – –

Interfaccia di servizio: operazioni rese disponibili dall’implementazione del protocollo Interfaccia “peer-to-peer” : formato messaggi scambiati fra “peer” + regole di procedura

N.B. “peer”: componenti allo stesso livello di astrazione (i.e., “di pari grado”) •

Termine “protocollo”: duplice significato 1. Specifica dell’interfaccia peer-to-peer 2. Modulo implementazione di questa interfaccia

Reti di Calcolatori (Fabio Panzieri)

71

Università di Bologna - Corso di Laurea in Informatica

Comunicazioni fra livelli • Interfaccia di servizio Li: definisce le operazioni primitive che Li fornisce a Li+1 • Interfaccia peer-to-peer: definisce formato e regole di scambio messaggi fra componenti allo stesso livello Li Host A Li+1

Protocollo i+1

I/f di servizio i + 1

Host B Protocollo i+1 I/f di servizio i

Li

Protocollo i I/f peer-to-peer

Reti di Calcolatori (Fabio Panzieri)

Protocollo i Comunicazione peer-to peer 72

36

Università di Bologna - Corso di Laurea in Informatica

Modello object-oriented • Oggetto: struttura dati con associate operazioni (metodi) che possono essere esportate per poter essere invocate da altri oggetti. • Oggetti con caratteristiche simili raggruppabili in classi; p.e.: – Classe protocolli – Classe messaggi

• Oggetto protocollo esporta interfaccia di servizio e interfaccia peer-to-peer – Interfaccia di servizio: esporta i metodi che altri protocolli sulla stessa macchina possono invocare – Interfaccia peer-to-peer: definisce formato e significato dei messaggi scambiati fra entità “peer” (i.e. istanze del protocollo su macchine distinte).

Reti di Calcolatori (Fabio Panzieri)

73

Università di Bologna - Corso di Laurea in Informatica

Comunicazioni fra livelli •

A livello H/W, comm’s peerto-peer dirette (via canale fisico).

•

A livelli superiori (p.e. Li+1), comunicazione peer-to-peer indiretta (in pratica, via Li che usa i servizi di Li-1, p.e. chiamata di procedura). Utilizzo dei servizi di Li-1

•

Host 1

Host 2

Application program

Application program

Data

Data RRP

RRP

RRP

Data

RRP HHP

Data

HHP

– incapsulamento – mpx/dmpx HHP

RRP

Data

RRP: Request Reply Protocol HHP: Host-to-Host Protocol Reti di Calcolatori (Fabio Panzieri)

74

37

Università di Bologna - Corso di Laurea in Informatica

Incapsulamento •

• • •

Applicazione in Host 1 “invia messaggio” (“data”) ad applicazione in Host 2: – in pratica, invoca procedura implementatata da RRP locale RRP appende RRP header info. di controllo a dati per RRP peer. Messaggio “combinato” viene trasmesso, i.e. passato a modulo HHP locale (via procedure call). HHP appende header specifico per HHP a messaggio, e lo trasmette a Host2 (invoca primitiva livello sottostante). In generale, ogni livello – 1. 2. – 1. 2. 3. 4.

Host 1

Host 2

Application program

Application program

Data

RRP

in trasmissione (Host1): incapsula il msg in proprio ; trasmette via primitive di livello sottostante in ricezione (Host2), ogni livello riceve msg mediante primitive del livello sottostante rimuove il proprio hdr e tail esegue processing specifico di hdr e tail; passa il msg DATA (privato di hdr e tail) al livello superiore.

Data RRP

RRP

HHP

HHP

Data

RRP

HHP

Data

RRP Data

Reti di Calcolatori (Fabio Panzieri)

75

Università di Bologna - Corso di Laurea in Informatica

Multiplexing/Demultiplexing di protocollo •

Protocollo supporta applicazioni diverse – –

•

RRP src include demultiplexing key (demux key) in RRP header RRP dst esamina demux key e consegna msg a destinazione appropriata

Livello supporta protocolli diversi: stesso meccanismo

Video Client

MSP

File server

Digital library Client

FS Client

Digital Library

RRP

RRP HDR

MSG

RRP

HHP

HHP HDR

MSG

HHP

Reti di Calcolatori (Fabio Panzieri)

Video Server

MSP

76

38

Università di Bologna - Corso di Laurea in Informatica

Architettura di rete OSI • ISO (International Standards Organization) ha definito un’architettura di rete chiamata Open Systems Interconnection Reference Model (OSI RM) per l’interconnessione di sistemi aperti, consistente di 7 livelli funzionali. • OSI RM è uno strumento per capire e descrivere architetture reali, e.g. Internet. • OSI RM non è una guida all’implementazione – Architeture reali raramente hanno 7 livelli; p.e., l’architettura Internet ne ha 4 – OSI RM: strumento utile per classificare le funzionalità di ciascun livello.

Reti di Calcolatori (Fabio Panzieri)

77

Università di Bologna - Corso di Laurea in Informatica

OSI RM End host

End host Application

Application

Presentation

Presentation

Session

Session

Transport

Transport

Network

Network

Network

Network

Data link

Data link

Data link

Data link

Physical

Physical

Physical

Physical

Uno o piu’ nodi di rete

Reti di Calcolatori (Fabio Panzieri)

78

39

Università di Bologna - Corso di Laurea in Informatica

Livelli in OSI RM • Physical Layer: – Gestisce la comunicazione di flussi di bits sul canale fisico.

• Data Link Layer: – Struttura e trasmette/riceve un flusso di bit in unità dati chiamate frames. L’interfaccia di rete (network adaptor card) collegata ad un computer implementa un protocollo data link., i.e. l’host riceve frames, non stringhe di bits.

• Network Layer: – Gestisce l’istradamento dell’informazione fra i nodi in una rete a commutazione di pacchetto. L’unità di informazione a questo livello è il pacchetto.

• Questi tre livelli sono presenti in tutti i nodi della rete: switches e hosts.

Reti di Calcolatori (Fabio Panzieri)

79

Università di Bologna - Corso di Laurea in Informatica

Livelli in OSI RM • Transport Layer: – Implementa comunicazioni process-to-process; l’unità di trasmissione a questo livello è il messaggio.

• Session Layer: – Supporta gestione integrata di flussi di trasporto diversi di una medesima applicazione, p.e. flussi audio e video.

• Presentation Layer: – Gestisce differenze di rappresentazione dati fra hosts (p.e. big-endian vs. little-endian, dimensioni tipi di dato come interi a 16, 32, o 64 bits)

• Application Layer: – Implementa protocolli applicativi specifici, p.e. FTP, HTTP, Telnet, SMTP …

• Transport Layer e superiori eseguiti in Host solamente.

Reti di Calcolatori (Fabio Panzieri)

80

40

Università di Bologna - Corso di Laurea in Informatica

Livelli in OSI RM •

Osservazioni: – Physical layer: consente trasmissione di flussi di bits su canale fisico (cavo, fibra, spazio,…) – Data link layer: consente comunicazione affidabile di frames tra coppie di nodi direttamente connessi. • Canale punto-punto: due nodi sono fisicamente connessi da un canale di comunicazione punto-punto che assolve la funzione di un cavo di collegamento (p.e. canale in fibra, linea telefonica). • Canale ad accesso multiplo (canale broadcast): il Data Link layer è anche responsabile del controllo degli accessi al canale (condivisione risorse).

– Network layer: abilita la comunicazione fra due nodi qualunque, arbitrariamente connessi • Caratteristica avanzata: comunicazioni multicast (un mittente molte destinazioni).

Reti di Calcolatori (Fabio Panzieri)

81

Università di Bologna - Corso di Laurea in Informatica

Architettura INTERNET • Quattro livelli solamente: – I primi due livelli OSI RM corrispondono al livello Network di Internet. – L’ Internet Protocol (IP) corrisponde al Network layer di OSI RM. – TCP (Transmission Control Protocol) and UDP (User datagram Protocol) corrispondono al Transport layer di OSI RM. – le applicazioni possono usare TCP, UDP e protocolli di livello più basso. Application layer Presentation layer Session layer Transport layer Network layer Data Link layer Physical layer

Reti di Calcolatori (Fabio Panzieri)

Application UDP

TCP IP

Network

82

41

Università di Bologna - Corso di Laurea in Informatica

Architettura Internet • Definita da Internet Engineering Task Force (IETF) • Gerarchia lasca FTP

HTTP

NV

TFTP

UDP

TCP

IP

NET 1

NET2

…

NET n

Reti di Calcolatori (Fabio Panzieri)

83

Università di Bologna - Corso di Laurea in Informatica

Programmare la rete • API (application programming interface) – Interfaccia supportata dall’architettura di rete – Consiste di insieme di primitive per la programmazione delle comunicazioni via rete – Definisce sintassi utilizzabile per invocare servizi implementati dai protocolli di rete – Convenzionalmente implementata dal sistema operativo

• Implementazione di applicazioni di rete – Concettualmente, simile a implementazione di gerarchia di protocolli • Applicazione invoca servizi di rete come protocollo di livello X invoca servizi implementati da protocollo di livello X-1

– In pratica, implementazione di gerarchia di protocolli si differenzia per • Limitare il numero dei context switch • Limitare il numero delle operazioni di copia

Reti di Calcolatori (Fabio Panzieri)

84

42

Università di Bologna - Corso di Laurea in Informatica

L’interfaccia socket • API nata per UNIX BSD e supportata da ampia varietà di OSs • Fornisce l’astrazione di “socket”: – Punto di accesso ai servizi di rete, utilizzabile da processo applicativo

• Primitive principali: 1) int socket(int domain, int type, int protocol) 2) int bind(int socket, struct sockaddr *address, int addr_len) 3) int listen(int socket, int backlog) 4) int accept(int socket, struct sockaddr *address, int *addr_len) 5) int connect(int socket, struct sockaddr *address, int addr_len) 6) int send(int socket, char *msg, int msg_len, int flags) 7) int recv(int socket, char *buffer, int buf_len, int flags)

Reti di Calcolatori (Fabio Panzieri)

85

Università di Bologna - Corso di Laurea in Informatica

Esempio di uso di socket /* client TCP*/ … main(…) { … /*risolvi indirizzo host dst*/ ds = gethostbyname(host); … /*stabilisci connessione*/ s = socket(PF_INET,SOCK_STREAM,0); … connect(s, …, …); … while (fgets(…) ) { /*legge e invia linee di testo*/ … send(s, buf, len, 0); } }

Reti di Calcolatori (Fabio Panzieri)

/* Server TCP */ … main() { … /* init open passiva */ s = socket(PF_INET,SOCK_STREAM,0); … bind(s,…,…); … listen(s,MAX_PENDING); /*attendi richiesta connessione*/ while(1){ new_s=accept(s,…,…); … recv(new_s,buf,sizeof(buf),0); close(new_s); } }

86

43

Università di Bologna - Corso di Laurea in Informatica

Interfaccia “socket” • abilita comunicazione fra programmi in esecuzione su nodi remoti – consente l’implementazione di protocolli applicativi

• Osservazioni – uso di interfaccia socket => system calls

• Adatta all’implementazione di protocolli? • Come si implementano i protocolli?

Reti di Calcolatori (Fabio Panzieri)

87

Università di Bologna - Corso di Laurea in Informatica

Protocolli modelli implementativi • •

Process-per-protocol Process-per-message

(a)

Process-per-Protocol Reti di Calcolatori (Fabio Panzieri)

(b)

Process-per-Message 88

44

Università di Bologna - Corso di Laurea in Informatica

Modello process-per-protocol • Ogni protocollo implementato da un processo – i.e., un processo per ogni livello di astrazione

• Msg viene trasmesso da un processo all’altro (i.e. da un livello all’altro) – msg attraversa stack di protocolli utilizzando IPC di OS – processo ricevente assume controllo e interpreta msg – assume disponibilità di qualche meccanismo di accodamento messaggi ai processi

N.B.: passare controllo a processo => costoso context switch Reti di Calcolatori (Fabio Panzieri)

89

Università di Bologna - Corso di Laurea in Informatica

Modello process-per-message • Ogni protocollo implementato mediante codice statico (procedura) – i.e., una procedura (contenente invocazioni di procedura) per livello di astrazione

• Gestione messaggi (in generale): – OS attiva processo responsabile per gestire messaggio – Processo invoca procedura che implementa specifico protocollo ad ogni livello della gerarchia per trattare messaggio – Gerarchia di protocolli attraversata mediante sequenza di chiamate di procedura

NB: chiamata di procedura è un’ordine di grandezza più efficiente di context switch

Reti di Calcolatori (Fabio Panzieri)

90

45

Università di Bologna - Corso di Laurea in Informatica

Ricezione messaggi • fonte di inefficienza: rcv bloccante => protocollo a livello X deve attendere terminazione rcv di protocollo a livello X-1 (equivalente a context switch)

• Risolto mediante upcall deliver (consegna messaggio ricevuto a livello superiore) – upcall: chiamata di procedura da livello X-1 a livello X • principio analogo a “interrupt handling”

TCP sendIPmsg()

deliverTCPmsg()

IP Reti di Calcolatori (Fabio Panzieri)

91

Università di Bologna - Corso di Laurea in Informatica

Protocolli: aspetti implementativi (modello process-per-protocol) • Socket API inadeguata per implementare architettura di protocolli – Ogni invocazione di primitiva socket causa context switch • OS sospende applicazione e passa controllo a kernel (driver che implementa protocollo)

– Costo accettabile a livello applicativo: • si paga una volta per invocazione • semplifica sviluppo

– Inaccettabile nell’implementazione di gerarchia di protocolli: • Invocazione di una primitiva a livello X causa successive invocazioni di primitive ai livelli inferiori • Se ogni primitiva (o protocollo) è implementata(o) da un processo, OS consuma tempo prezioso nell’effettuare i context switch

Reti di Calcolatori (Fabio Panzieri)

92

46

Università di Bologna - Corso di Laurea in Informatica

Inadeguatezza socket API: buffering di messaggi • send, recv: processo applicativo fornisce buffer da cui copiare dati da trasmettere, e dove copiare dati ricevuti – Protocollo di più alto livello copia dati da buffer utente a buffer sistema, e viceversa

•

Operazione “copia” è estremamente costosa (memoria più lenta di CPU) – da evitare nell’implementazione di gerarchie di protocolli Applicazione

copyout_msg()

send()

deliver()

copyin_msg()

Protocollo

Reti di Calcolatori (Fabio Panzieri)

93

Università di Bologna - Corso di Laurea in Informatica

Scatter-Gather • Uso di astrazione “messaggio”: • Messaggio: stringa di bytes di qualche lunghezza predefinita condivisa da i vari protocolli ai diversi livelli di astrazione • Operazioni su “messaggio”: manipolano stringa di bytes – msgAddHdr(…); msgStripHdr(…); – msgFragment(…); msgReassemble(…); • Tecnica dello “scatter/gather” – lista di “puntatori” che indirizzano, per ogni livello, porzioni di msg Lista di puntatori ø

HDR Li

Dati Li

HDR Lj

Scatter-gather Reti di Calcolatori (Fabio Panzieri)

Dati Lj

Lj

HDR Lj

Dati Lj

HDR Li

Dati Li

Ii Li

copy-and-store 94

47

Università di Bologna - Corso di Laurea in Informatica

Protocolli: aspetti implementativi (scheduling di eventi) • Protocollo può voler gestire evento che può accadere in qualche istante futuro p.e.: ritrasmissione di un messaggio allo scadere di un (timeout)

• Sottosistema di rete fornisce Event Manager (EM) – EM consente a protocollo di invocare procedura specifica dopo periodo di tempo prefissato. – p.e.: Event evSchedule(EvFunc function, void *argument, int time) /* invoca function dopo time microsecondi; ritorna descrittore evento ‘event’ per eventuale successiva cancellazione */ Void evCancel(Event event) /* cancella evento ‘event’ */

Reti di Calcolatori (Fabio Panzieri)

95

Università di Bologna - Corso di Laurea in Informatica

OSI RM

End host

End host

Application

Application

Presentation

Presentation

Session

Session

Transport

Transport

Network

Network

Network

Network

Data link

Data link

Data link

Data link

Physical

Physical

Physical

Physical

Uno o piu’ nodi di rete

Reti di Calcolatori (Fabio Panzieri)

96

48

Università di Bologna - Corso di Laurea in Informatica

Livelli Fisico e Data Link (funzionalità) •

Connessione diretta (punto-punto) fra elaboratori – –

•

Accesso singolo Accesso multiplo (condiviso)

Richiede soluzione di 5 problemi principali – – – – –

Encoding: codifica dei singoli bit in modo da essere riconoscibili da destinazione (i.e. distinguibili da rumore) Framing: consentire riconoscimento di sequenza di bit (frame) come singolo messaggio Individuazione di errori: bits in frame possono subire alterazioni in transito; di conseguenza, necessario individuare possibile errori Trasmissione affidabile: “mascherare” errori individuati Controllo di accesso: tecniche di arbitraggio degli accessi in canali ad accesso multiplo.

Reti di Calcolatori (Fabio Panzieri)

97

Università di Bologna - Corso di Laurea in Informatica

Livelli Fisico e Data Link • Livello fisico: – flusso di segnali – flusso di bit

• Livello data link: – flusso di frames Componenti di segnalazione Node

adaptor

segnali

adaptor

Node

bits frames Reti di Calcolatori (Fabio Panzieri)

98

49

Università di Bologna - Corso di Laurea in Informatica

Nodo (host computer) • Memoria: risorsa scarsa (e lenta); minimizzarne l’uso • Network Adaptor (NA) – Codifica/trasferisce dati da host a rete – Decodifica/ trasferisce dati da rete a host – Pilotato da device driver in host OS • Driver src fornisce a NA ptr e size dei dati da codificare/trasmettere • Driver rcv fornisce a NA ptr e size del buffer destinazione cpu

I/O bus

cache

network NA

memoria Reti di Calcolatori (Fabio Panzieri)

99

Università di Bologna - Corso di Laurea in Informatica

Livello Fisico: componenti • Nodi – host computers connessi mediante qualche supporto fisico (p.e., coax., fibra ottica, “spazio”) detto link

• Link – propaga (xmit/rcv) segnali – segnale: onda elettromagnetica che viaggia a velocità della luce (dipendente da supporto fisico) • p.e.: nel vuoto, 3 x 108 m/s, su rame, 2.3 x 108 m/s

– Link half-duplex: unidirezionale • richiede coordinamento fra src e rcv per decidere “chi fa cosa”

– Link full-duplex: bidirezionale

• Xmit/Rcv a livello fisico: – codifica dati (0,1) in segnali / decodifica segnali in dati • p.e. modem (modulator/demodulator): modulazione/demodulazione elettromagnetiche attraverso il canale fisico Reti di Calcolatori (Fabio Panzieri)

di onde

100

50

Università di Bologna - Corso di Laurea in Informatica

Livello fisico: xmit/rcv • Modulazione (variazione della frequenza) del segnale – Frequenza: velocità di oscillazione misurata in Hz

• Codifica – associazione dello stato del segnale ad un dato binario • p.e. 0 < signal ≤ +5v => ON = 1; -5V ≤ signal ≤ 0 => OFF = 0 N.B.: Modulazione istantaneamente

non

avviene

=> velocità di trasmissione del segnale limitata (i.e. bandwidth limitata) – Bandwidth (a livello fisico): velocità max cui h/w può variare il segnale – Bandwidth misurata in: • Cicli al secondo (Hz) per segnali analogici (p.e., da 300Hz a 3300 Hz per voce) • Bit al secondo (bps) per segnali digitali (i.e. impulsi ON e OFF) Reti di Calcolatori (Fabio Panzieri)

101

Università di Bologna - Corso di Laurea in Informatica

Teorema di Nyquist • Nel 1924, Nyquist stabilì che il massimo tasso di trasmissione di bit (bit rate) ottenibile su un canale “perfetto”, con bandwidth di B Hz è: D = 2B log 2 K dove, D e’ il bit rate (in bps), and K è il n. di livelli discreti di voltaggio del segnale. – p.e. su canale a 3 KHz (3000 Hz), max. bit rate per segnali binari (2 livelli) è 6000 bps. – Per ottenere bit rate maggiore sono necessarie tecniche di codifica sofisticate che usano numerosi livelli di voltaggio.

• Il teorema di Nyquist assume canale perfetto, senza rumore. – in pratica, il canale è soggetto a disturbi (interferenze), riducendo così il bit rate teorico. Reti di Calcolatori (Fabio Panzieri)

102

51

Università di Bologna - Corso di Laurea in Informatica

Teorema di Shannon (1948) • Fornisce limite superiore, in bps, della capacità (bit rate) di un canale soggetto a rumore, in funzione del rapporto segnale/rumore (S/N), misurato in dB – S = segnale elettrico, N = rumore termico

• Consente di valutare max capacità C di un dispositivo che trasmette segnale digitale su link analogico (p.e. modem), indipendentemente dal n. di livelli del segnale: C = B log2 (1 + S/N) bps – C: capacità del canale (bit rate, in bps) – B: bandwidth per il segnale analogico (in Hz) – S/N in dB ricavabile da relazione: dB = 10 log10 (S/N) • p.e.:S/N = 10 => 10dB, S/N = 100 => 20dB, S/N = 1000 => 30dB

– quindi, canale con B = 3000Hz e S/N di 30 dB avrà capacità massima C = 3000 log2 (1001) = 30 Kbps (circa) N.B.: 30dB = tipico valore del rapporto S/N su linea per voce Reti di Calcolatori (Fabio Panzieri)

103

Università di Bologna - Corso di Laurea in Informatica

Livello fisico: tipi di link Tecnologia e relative bande di frequenza (in Hz) 105 ≤ Cavo Coassiale < 109 107 < TV < 1010 108 < Satellite < 1011 1014 ≤ Fibra Ottica ≤ 1015

Tecnologia

Reti locali (private) Bandwidth

Reti pubbliche (leased lines)

Distanza

Doppino categoria

10 - 100 Mbps,

100m

50-ohm coax. (Thin Net)

10 - 100 Mbps

200m

75-ohm coax. (Thick Net)

10 - 100 Mbps

500m

Multimode Fiber

100 Mbps

2Km

Single-mode Fiber

100 - 2400 Mbps

40Km

Reti di Calcolatori (Fabio Panzieri)

Servizio Bandwidth T1 (DS1) 1.544 Mbps T3 (DS3) 44.736 Mbps STS-1 51.840 Mbps STS-3 155.250 Mbps … STS-48 2.488320 Gbps

104

52

Università di Bologna - Corso di Laurea in Informatica

Reti pubbliche: “last mile” link • Come connettersi a rete pubblica esistente – Linea telefonica standard, via modem • 56 Kbps

– ISDN (Integrated Services Digital Network) • Due canali a 64Kbps, uno per dati, l’altro per voce digitalizzata – CODEC (COder/DECoder) codifica voce in segnale digitale • Se canale “voce” non in uso, utilizzabile per dati => Bandwith disponibile = 128Kbps

– – – –

ADSL (Asymmetric Digital Subscriber Line) VDSL (Very-high-data-rate Digital Subscriber Line) CATV (Cable TV) Wireless

Reti di Calcolatori (Fabio Panzieri)

105

Università di Bologna - Corso di Laurea in Informatica

ADSL • •

Collegamento ad alta velocità fra host (subscriber) e telecom ISP Collegamento “asimmetrico” – –

i.e. bandwidth ISP -> subscriber (downstream) più ampia che subscriber -> ISP (upstream) Bandwidth effettiva dipende distanza subscriber <-> ISP

downstream (1.554 - 8.448 Mbps) TIN switch

Subscriber upstream (16 - 640 Kbps) Local loop

Reti di Calcolatori (Fabio Panzieri)

106

53

Università di Bologna - Corso di Laurea in Informatica

VDSL • Simmetrico 12.96 Mbps ≤ bandwidth ≤ 55.2 Mbps (dipendentemente da distanza da switch)

• Switch ottico – gestito da compagnia telefonica – Serve comunità di utenti (p.e. un quartiere)

Telecom switch

STS-N su fibra

Switch ottico

12.96 - 55.2 Mbps 300 - 1500 m

Subscriber

Reti di Calcolatori (Fabio Panzieri)

107

Università di Bologna - Corso di Laurea in Informatica

CAble TV (o cable modem) • Servizio alternativo ad ADSL – Fornisce collegamento ad alta velocità fra host (subscriber) e ISP

• Utilizza infrastruttura TV via cavo – Sottoinsieme di canali TV messi a disposizione per trasmissione dati digitali • Bandwidth: 6MHz per canale

• Asimmetrico – tecnologia attuale: 40Mbps downstream, 20Mbps upstream • Downstream maggiore perché si prevede trasmissione di traffico ≠ caratteri

• Condiviso – Comunità di utenti condividono bandwidth => Meccanismi di arbitraggio per allocazione di banda

Reti di Calcolatori (Fabio Panzieri)

108

54

Università di Bologna - Corso di Laurea in Informatica

Wireless •

Standard attuali: per fonia e trasmissione dati – PCS (Personal Communication Services): USA, CANADA – GSM (Global System Mobile): EUROPA (e resto del mondo) – Bluetooth (Ericsson, Nokia, IBM, Toshiba, Intel) • Standard industriale per coprire brevi distanze (decine di metri) • Disegnato per uso in qualunque dispositivo (WSs, stampanti, proiettori, telefoni, …)

– IEEE 802.11: accesso a canale condiviso in area geografica limitata

•

In corso di sviluppo per comm’s su scala planetaria – Costellazioni di satelliti P.e. Teledesic: rete di satelliti in grado di fornire canale da 2048 Mbps fra ogni coppia di hosts sulla terra • 288 satelliti a bassa orbita (1350 Km dalla Terra) • Ogni satellite: 1440 canali satellite-terra a 16Kbps, aggregabili in gruppi di 128 max. per fornire canali da 2048 Mbps • Ogni satellite connesso ad 8 vicini da canali da 155.52 Mbps

Reti di Calcolatori (Fabio Panzieri)

109

Università di Bologna - Corso di Laurea in Informatica

Livello fisico: tecniche di codifica • Principio operativo: – valori 1 e 0 codificati con diversi valori del segnale – Baseline: valore medio del segnale, usato per distinguere codifiche

• Pilotate da clock – Ad ogni ciclo di clock: • src codifica/trasmette un bit • rcv decodifica/riceve un bit

– Sincronizzazione tra src e rcv necessaria affinché rcv decodifichi/riceva lo stesso bit che src ha trasmesso – Rcv deriva segnale di clock da segnale ricevuto (clock recovery) • transizione di segnale da 0 a 1 e da 1 a 0 causa che rcv re-sincronizzi il proprio clock; i.e., rcv riconosce il clock boundary (o terminazione del ciclo)

– Clock potrebbe essere inviato come segnale separato, su link dedicato, ma ciò eleverebbe i costi di cablaggio

Reti di Calcolatori (Fabio Panzieri)

110

55

Università di Bologna - Corso di Laurea in Informatica

Tecniche di codifica • NRZ (Non Return to Zero) – Valore 1 codificato in segnale high, valore 0 codificato in segnale low (relativamente a baseline) stringa di bit

0

0

1

0

1

1

codifica NRZ

• Problemi – Segnale low prolungato: sequenza di 0 o link guasto? – Segnale high prolungato (i.e. sequenza di 1): causa variazione di valor medio (baseline) – Sequenze di 0 o di 1 inibiscono clock recovery, a causa di assenza di transizioni, provocando clock drift

Reti di Calcolatori (Fabio Panzieri)

111

Università di Bologna - Corso di Laurea in Informatica

Tecniche di codifica • NRZI (NRZ Inverted) – Src forza transizione del segnale corrente per codificare 1 – Src mantiene stato del segnale per codificare 0 – Risolve problema delle sequenze di 1 (non risolve quello delle sequenze di 0) stringa di bit

0

0

1

0

1

1

clock

codifica NRZI

Reti di Calcolatori (Fabio Panzieri)

112

56

Università di Bologna - Corso di Laurea in Informatica

Tecniche di codifica • Manchester encoding – Src trasmette XOR di NRZ encoding e clock • 0 codificato come transizione low -> high • 1 codificato come transizione high -> low

+ Risolve problema sequenze di 0 o 1 (i.e., abilita clock recovery a rcv) – Raddoppia il tasso di variazione del segnale => dimezza il bit rate stringa di bit

0

0

1

0

1

1

codifica NRZ clock

xor 0 0 1 1

0 1 0 1

0 1 1 0

Manchester encoding

Reti di Calcolatori (Fabio Panzieri)

113

Università di Bologna - Corso di Laurea in Informatica

Tecniche di codifica •

4B/5B – Inserisce bit aggiuntivo in ogni sequenza di 4 bit i.e. sequenza di 4 bit codificata con codice di 5 bit

– Codici di 5 bit costruiti in modo che • Ogni codice ha al più un bit 0 in testa • Ogni codice ha al più due bit 0 in coda

– Codici trasmessi con codifica NRZI • NRZI risolve problema sequenze di 1 • 4B/5B risolve problema sequenze di 0

•

Osservazioni – 16 i possibili simboli di 4 bit – 32 i possibili codici di 5 bit => 16 codici liberi per scopi speciali,p.e.: • 11111 “canale inutilizzato”, 00000 “canale non attivo”, 00100 “halt” • Dei 13 codici rimanenti, 7 violano regole 4B/5B, perciò non utilizzabili

Reti di Calcolatori (Fabio Panzieri)

114

57

Università di Bologna - Corso di Laurea in Informatica

Livello Data Link • In PSN: scambio di pkts – i.e., “frames” a livello data link

• Responsabilità principale del livello Data Link – Abilitare trasmissione/ricezione di frames fra due hosts connessi punto-punto • Framing: costruzione dei messaggi che possono essere trasmessi/ricevuti • Individuazione di errori • Trasmissione affidabile • Controllo degli accessi, nell’uso di canali punto-punto condivisi (p.e. CSMA/CD, Token Ring)

Reti di Calcolatori (Fabio Panzieri)

115

Università di Bologna - Corso di Laurea in Informatica

Principio operativo • Trasmissione di frame da A a B – A richiede ad adaptor trasmissione di frame da memoria di nodo • e.g. interfaccia Nodo/Adaptor: xmit(*ptr, length) da buf in A

– Adaptor invia sequenza di bit su link – Adaptor in B riceve sequenza di bit • e.g. interfaccia Nodo/Adaptor: deliver(*ptr, lenght) in buf in B

Nodo A

adaptor

Reti di Calcolatori (Fabio Panzieri)

bits frames

adaptor

Nodo B

116

58

Università di Bologna - Corso di Laurea in Informatica

Framing • Ruolo del livello Data Link: – imporre formato (frame) a flusso di bit – gestire xmit/delivery di flussi di frames

• Problema principale: determinare inizio/fine frame • Tre approcci – Byte oriented framing: frame come insieme finito di caratteri • basato su “sentinella” (delimitatore) • basato su “contatore” (lunghezza)

– Bit oriented framing: frame come insieme finito di bit • basato su “sentinella”

– Clock based framing: • frame come insieme sender/receiver

finito

di

bytes

costruito

su

sincronizzazione

• SONET: standard per trasmissione dati su fibra ottica Reti di Calcolatori (Fabio Panzieri)

117

Università di Bologna - Corso di Laurea in Informatica

Protocolli “sentinel-based” byte-oriented •

BISYNC (Binary Synchronous Communication) – protocollo IBM usato in computers IBM e switch Internet.

Ogni frame è una sequenza di bytes (caratteri) consistente di: – – – – – –

•

Caratteri speciali SYN e ETX usati per delimitare frame Usa tecnica del “character stuffing”: ogni carattere ETX in “body” sostituito da sequenza DLEETX (DLE: Data Link Escape) CRC: “cyclic redundancy code” su STX, body, ETX SOH

SYN

SYN

8 8 8

Reti di Calcolatori (Fabio Panzieri)

8 header

body

8

16

ETX

• •

2 caratteri SYN :“start of frame” carattere SOH: “start of header” campo “header”: info applicativa di controllo (address, n. di sequenza della frame) carattere STX: identifica “end of header” e “start of text” campo “body” (dati effetivi) carattere ETX: “ end of text”

STX

•

CRC 118

59

Università di Bologna - Corso di Laurea in Informatica

Protocolli “sentinel-based” bit oriented • HDLC (High level data link control) – – – –

Frame trattata come sequenza di bits. Sequenza 01111110 delimita la frame Stessa sequenza trasmessa con canale “idle” Bit stuffing • usato per riconoscere l’occorrenza della sequenza speciale nel “body”

HDLC

8

16

Beginning sequence

Header

16 Body

CRC

8 Ending sequence

Reti di Calcolatori (Fabio Panzieri)

119

Università di Bologna - Corso di Laurea in Informatica

Bit Stuffing in HDLC •

Mittente: – inserisce bit 0 dopo ogni sequenza di cinque bit 1 consecutivi nel “body” della frame

•

Destinatario: – se riceve sequenza di cinque 1 consecutivi nel body di una frame, allora esamina bit_successivo: if bit_successivo = 0 then “scarta bit” /* bit stuffing è avvenuto */ else /* bit_successivo = 1; due i casi possibili */ if bit_successivo = 0 then end-of-frame marker /* ultimi 8 bit ricevuti: 01111110 */ else “scarta frame” /* è stato ricevuto bit = 1; quindi, ultimi 8 bit ricevuti: 0111111; i.e., sequenza non ammessa */ o

siv ces

011111

suc bit_

0 => bit stuffing; scarta bit 1

Reti di Calcolatori (Fabio Panzieri)

0 => End of Frame 1 => sequenza non ammessa; scarta frame 120

60

Università di Bologna - Corso di Laurea in Informatica

Protocolli “counter-based” byte oriented • DDCMP (Digital Data Communication Message Protocol) – Usato da DEC in DECNET – Count: specifica n. di bytes in Body – Problema: corruzione del campo Count

8

8

8

14

42

SYN

SYN

class

• Ricevente: individua “framing error” calcolando CRC if framing error detected then discard frame; receive SYN

Count

Header

16 Body

CRC

Reti di Calcolatori (Fabio Panzieri)

121

Università di Bologna - Corso di Laurea in Informatica

Protocolli “clock-based” •

SONET (Synchronous Optical NETwork) – Standard internazionale per trasmissione su fibra ottica – Gestisce: framing, encoding e multiplexing di flussi a bassa velocità su canale ad alta velocità

•

Framing in SONET – Ogni frame e’ lunga 125µs • STS-1 (51.84 Mbps): frame length = 810 bytes •

STS-3 (155.25 Mbps): frame length = 2430 bytes

Frame STS1

STS -1

Hdr

STS -1

Hdr

Payload

Hdr

Overhead

STS -1

9 rows

Hdr

STS -3c

90 columns

Reti di Calcolatori (Fabio Panzieri)

122

61

Università di Bologna - Corso di Laurea in Informatica

Data Link Layer in Internet • •

Protocolli byte oriented Usati per: – comunicazioni router-to-router – comunicazioni utente_privato-ISP via linea telefonica

Reti di Calcolatori (Fabio Panzieri)

123

Università di Bologna - Corso di Laurea in Informatica

SLIP •

SLIP, Serial Line IP (Rick Adams 1984): – sviluppato per connettere SUN W/S a Internet via modem e linea telefonica – incapsula pacchetti IP in frame speciale • aggiunge flag byte alla fine di ogni pacchetto IP • se flag byte appare nel pacchetto IP, usa “character stuffing” (2 byte speciali)

•

Problemi – Non svolge controllo di errore – Supporta solo IP – Src e rcv devono conoscere relativi indirizzi IP – Non fornisce autenticazione – Non è Internet standard • ne esistono versioni diverse, incompatibili fra loro, e con IP

Reti di Calcolatori (Fabio Panzieri)

124

62

Università di Bologna - Corso di Laurea in Informatica

Point-to-Point Protocol (PPP) • •

IETF standard, utilizzabile via modem, linee seriali HDLC, SONET 3 responsabilità principali 1. Imporre una struttura di frame (simile a frame HDLC) 2. Implementare protocollo di controllo del link (LCP; i.e. Link Control Protocol) per •

attivare la linea

•

testing della linea

•

negoziare opzioni di comunicazione (p.e., velocità di trasmissione, controllo di errori)

•

disattivare la linea

3. Consentire configurazione protocollo di rete usato

del

livello

rete

indipendentemente

da

•

svolto da protocollo NCP (Network Control Protocol)

•

consente uso di un differente NCP per ogni protocollo di livello network usato

Reti di Calcolatori (Fabio Panzieri)

125

Università di Bologna - Corso di Laurea in Informatica

Frame PPP

•

Come HDLC, ma “character oriented”, non “bit oriented”

• •

“flag” = HDLC standard “address”: normalmente settato a 1 – tutte le stazioni possono accettare frame “control”= 00000011: “no error checking, no SeqNum” – assume link sufficientemente affidabile; possibile introdurre SeqNum,… “protocol”: tipo di info. contenuta in “payload” (NCP, LCP, IP, AppleTalk,…) “payload”: lunghezza variabile, default = 1500 B, altrimenti negoziato “checksum”: normalmente 2 B, negoziabili 4 B.

• • • •

– (i.e., frame size = n. intero di bytes)

Reti di Calcolatori (Fabio Panzieri)

126

63

Università di Bologna - Corso di Laurea in Informatica

PPP: principio di funzionamento • Home PC “chiama” host ISP via modem • Stabilisce connessione fisica via linea telefonica • Invia sequenza di pacchetti LCP in payload field per selezionare parametri di comunicazione (e.g. controllo di errore, velocità di trasmissione) • Scambia serie di pacchetti NCP per configurare livello network – se home PC usa TCP/IP, richiede indirizzo IP • in esempio: computer ISP dispone di n indirizzi IP che vengono allocati dinamicamente all’utente (i.e., può avere fino a n utenti collegati simultaneamente). NCP svolge questo ruolo.

• Home PC = Internet host – scambia pacchetti IP

• Terminazione sessione: – NCP chiude sessione a livello network – LCP chiude sessione a livello data link Reti di Calcolatori (Fabio Panzieri)

127

Università di Bologna - Corso di Laurea in Informatica

Attivazione/disattivazione linea in PPP 1. Fase “dead”: connessione assente 2. Fase “establish”: stabilita la connessione fisica, frames LCP scambiate per attivare una connessione con certe proprietà 3. Fase “authentication”: esegue autenticazione (p.e. controllo della password di utente). 4. Fase “network”: frames NCP trasmesse per inizializzare parametri di rete (p.e. indirizzo IP). 5. Fase “open”: trasferimento dati ha luogo 6. Fase “terminate”: chiude comunicazione Reti di Calcolatori (Fabio Panzieri)

128

64

Università di Bologna - Corso di Laurea in Informatica

Reti di Calcolatori (Fabio Panzieri)

129

Università di Bologna - Corso di Laurea in Informatica

Livello Data Link • Framing: costruzione dei messaggi che possono essere trasmessi/ricevuti • Individuazione di errori • Trasmissione affidabile • Controllo degli accessi, nell’uso di canali condivisi (p.e. CSMA/CD, Token Ring)

Reti di Calcolatori (Fabio Panzieri)

130

65

Università di Bologna - Corso di Laurea in Informatica

Individuazione di errori • Come individuare “corruzione” di bit (1 diviene 0, o vv.)? – mediante “ridondanza”, i.e. bit addizionali aggiunti al messaggio

• Bit di parità: un bit (parity bit) viene aggiunto ad un carattere di 7 bit. P.e. Parità “pari”: – mittente aggiunge parity bit = 1 o 0 in modo che il n. totale di 1 (bit di parità incluso) sia un numero pari p.e. parity bit per 0100101 è 1.

– destinatario controlla che ogni byte ricevuto contenga un numero pari di bit 1, altrimenti individua errore • L’occorrenza di un errore in un bit può essere individuata, ma non corretta; un numero pari di errori non può essere individuato.

– Parità dispari: l’opposto di parità pari.

Reti di Calcolatori (Fabio Panzieri)

131

Università di Bologna - Corso di Laurea in Informatica

Parità bidimensionale bit di parità a) bit di parità per singolo byte b) bit di parità per ogni posizione di bit nella frame – Ne risulta un byte di parità

• Proprietà: – Individua tutti gli errori di 1, 2, e 3 bit, e gran parte degli errori di 4 bit

• CRC (Cyclic Redundancy Code): più potente – protegge da “burst” (raffiche) di errori

Reti di Calcolatori (Fabio Panzieri)

dati

• Introduce

0101001 1101001 1011110 0001110 0110100 1011111

1 0 1 1 1 0

1111011 0

byte di parità

132

66

Università di Bologna - Corso di Laurea in Informatica

Errore “burst” • •

Errore “burst” inizia e finisce con bit errato, anche se i bit fra questi due sono corretti Definizione: – numero di bit compresi fra due bit errati (contando anche i due bit errati)

•

Due errori burst consecutivi devono essere separati da almeno B bit consecutivi corretti, dove B è la lunghezza del “burst”

Sequenza trasmessa: 110110 111101 111000 111110 11 Sequenza ricevuta: 111111 111101 011111 111110 11 min. seq. di bit “error-free” burst di 6 bit min. seq. di bit “error-free” burst di 4 bit Reti di Calcolatori (Fabio Panzieri)

133

Università di Bologna - Corso di Laurea in Informatica

Cyclic Redundancy Code •

Principio operativo: –

Rappresentare messaggio di n bit come un polinomio di grado n-1 •

p.e. MSG=10011010 corrisponde a M(x) = x7+ x4 + x3 + x1

•

p.e. C(x) = x3+ x2 + 1, k = 3

•

i.e.,M(x)/C(x) => resto = 0

– mittente e ricevente concordano divisore polinomiale C(x) (detto generatore) di grado k – C(x) deve dividere esattamente M(x) – Aggiungere k bits ridondanti a messaggio di n bit (k << n).

•

Mittente:

•

Ricevente

– trasmette un polinomio P(x) generato da M(x) . xk e divisibile per C(x) – Riceve P(x) – Calcola P(x)/C(x)

• resto = 0 in soli due casi: a. assenza di errori, i.e. P(x) = M(x) . xk b. P(x) ≠ M(x) . xk, ma è divisibile esattamente per C(x) => scegliere C(x) in modo da rendere b. caso “raro”, o impossibile

Reti di Calcolatori (Fabio Panzieri)

134

67

Università di Bologna - Corso di Laurea in Informatica

Aritmetica polinomiale per calcolo del CRC • Aritmetica polinomiale – i coefficienti possono assumere valore 0 o 1, solamente – operazioni sui coefficienti eseguite con aritmetica modulo 2 (i.e., senza riporti per l’addizione, né prestiti per la sottrazione)

• Alcune proprietà – Polinomio B(x) divisibile per polinomio C(x) se B(x) è di grado più elevato di C(x) – Polinomio B(x) divisibile una volta per polinomio C(x) se B(x) e C(x) sono dello stesso grado – resto della divisione ottenuto sottraendo C(x) a B(x) – Sottrazione: B(X) XOR C(X) • i.e., if bit i = bit j then bit i xor bit j = 0 else bit i xor bit j = 1 Reti di Calcolatori (Fabio Panzieri)

135

Università di Bologna - Corso di Laurea in Informatica

Regole di calcolo del CRC •

Obiettivo: creare polinomio che sia – derivato da messaggio originale M(x) – k bits più lungo di M(x) – Divisibile esattamente per polinomio C(x) di grado k

•

Procedura: 1. Moltiplicare M(x) per xk, i.e. creare messaggio T(x) = M(x) con k 0 aggiunti a fine messaggio 2. Dividere T(x) per C(x) e trovare resto 3. Sottrarre resto a T(x) 4. Inviare messaggio così ottenuto – i.e., viene generato e trasmesso un messaggio sicuramente divisibile per C(x)

Reti di Calcolatori (Fabio Panzieri)

136

68

Università di Bologna - Corso di Laurea in Informatica

Esempio Mittente Msg = 10011010 Polinomio corrispondente: M(x) = x7+ x4 + x3 + x1 Generatore C(x) = x3+ x2 + 1, i.e. 1101, k = 3 T(x) 1. moltiplicare M(x) per xk ottenendo • T(x) = x10 + x7 + x6 + x4 (10011010000) Msg 10011010000 : 1101 Generatore G G 1101 2. calcolare resto T(x)/C(x) 3. Sottrarre resto a T(x) resto 1001 • T(x) - resto sicuramente divisibile per C(x) G 1101 4. Trasmette messaggio ottenuto 1000 G 1101 N.B.: Passo 3. equivale a T(x) XOR resto, i.e. Msg concatenato a resto ottenuto in 3. 1011 Ricevente: G 1101 calcola 10011010101/1101 1100 – i.e., divide frame ricevuta per lo stesso G 1101 1000 generatore usato dal mittente G 1101 • Resto = 0 => frame corretta, scarta tre bit finali • Resto ≠ 0 => errore di trasmissione resto 101

Trasmette 10011010101 Reti di Calcolatori (Fabio Panzieri)

137

Università di Bologna - Corso di Laurea in Informatica

Proprietà del generatore • T(x): frame trasmessa; T(x) + E(x): frame ricevuta – polinomio E(x) rappresenta l’errore

• (T(x) + E(x))/C(x) = T(x)/C(x) + E(x)/C(x) • T(x)/C(x) dà resto 0 (per def. di T(x)) => eventuale errore si trova in E(x)/C(x) – se E(x)/C(x) dà resto ≠ 0, allora errore individuato – se E(x)/C(x) dà resto = 0 allora assenza di errore oppure errore non individuato

• Ne consegue: – C(x) tale da non dividere esattamente il polinomio “errore” E(x)

Reti di Calcolatori (Fabio Panzieri)

138

69

Università di Bologna - Corso di Laurea in Informatica

Caratteristiche del generatore • Come costruire C(x)? – Errore di singolo bit i esprimibile da polinomio di un singolo termine E(x) = xi – C(x) di grado k contiene almeno xk = 1 e x0 = 1 ⇒ C(x) di 2 termini non potrà dividere esattamente nessuna stringa di bit contenente errore in un singolo bit (i.e., esprimibile come E(x) = xi) ⇒ C(x) puo’ rilevare tutti gli errori di un singolo bit

• Dimostrato che generatore opportunamente costruito individua – – – –

tutti gli errori di un singolo bit, se i termini xk e x0 hanno coefficiente ≠ 0 tutti gli errori di due bit, se C(x) ha un fattore con almeno tre termini numero arbitrario dispari di errori, se C(x) contiene il fattore (x + 1) ogni errore “burst” la cui lunghezza sia inferiore a k bits e la maggior parte di errori “burst” di lunghezza superiore a k bits

NB: implementabile in H/W mediante registri shift e porte XOR Reti di Calcolatori (Fabio Panzieri)

139

Università di Bologna - Corso di Laurea in Informatica

Generatori

CRC CRC-8 CRC-10 CRC-12

C(x) x10+x9+x5+x4+x1+1 x12+x11+x3+x2+x1+1

CRC-16 CRC-CCITT

x16+x15+x2+1 x16+x12+x5+1

(HDLC) CRC-32 (ethernet)

x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1

x8+x2+x1+1

Reti di Calcolatori (Fabio Panzieri)

140

70

Università di Bologna - Corso di Laurea in Informatica

Checksum in Internet • Mittente: – somma tutte le parole che vengono trasmesse, usando aritmetica in complemento a 1 – trasmette anche il risultato della somma (checksum)

• Ricevente: – fa lo stesso – se checksum calcolato differisce da quello ricevuto, allora errore

• Fornisce protezione “debole” – p.e. non protegge da modifiche nell’ordine delle parole – ritenuto sufficiente

Reti di Calcolatori (Fabio Panzieri)

141

Università di Bologna - Corso di Laurea in Informatica

Checksum in Internet u_short cksum(u_short *buf, int count) { register u_long sum = 0; while (count--) /*count: lunghezza di buf in unità di 16 bit */ { sum += *buf++; if (sum & 0xFFFF0000) { /*si è verificato riporto; incrementa risultato*/ sum &= 0xFFFF; sum++; } } return ~(sum & 0xFFFF); /*due bytes meno significativi di sum in complemento a 1*/ } Reti di Calcolatori (Fabio Panzieri)

142

71

Università di Bologna - Corso di Laurea in Informatica

Trasmissione affidabile

• Ricevente scarta frames contenenti errori di trasmissione • Per ottenere link affidabile

– Ricevente deve segnalare al mittente che ha scartato una frame – Mittente deve essere in grado di ritrasmettere frames scartate

• Due meccanismi di base:

– acknowledgement (ACK): ricevente invia a mittente una frame di controllo (frame priva di dati) a indicare che ha accettato un frame inviata dal mittente • piggybacking: invio di ACK in frame di dati che destinatario trasmette a mittente

– timeout: se mittente non riceve ACK in un intervallo di tempo predefinito, ritrasmette frame • in termini di programmazione: – mittente attiva timer di una certa durata if ACK ricevuto prima che il timer termini, then cancella timer else cattura eccezione dal timer, e ritrasmette • ARQ (Automatic Repeat Request): tecnica basata su ACK e timeout

Reti di Calcolatori (Fabio Panzieri)

143

Università di Bologna - Corso di Laurea in Informatica

Stop-and-wait: semplice schema ARQ Principio operativo: • Dopo aver inviato una frame, mittente attiva time-out attende ACK prima di inviare frame successiva • Terminazione del time-out prima ricezione ack

il e la di

=> ritrasmissione frame

•

N.B.: Casi c), d) – perdita/ritardo dell’ ACK possono provocare richieste replicate

Reti di Calcolatori (Fabio Panzieri)

144

72

Università di Bologna - Corso di Laurea in Informatica

Stop-and-wait: casi particolari 1. situazione normale, ACK ricevuto prima che time-out termini 2. frame non ricevuta (persa in transito), ACK non trasmesso, timeout termina, mittente ritrasmette frame 3. ACK perso, time-out termina, mittente ritrasmette frame, creando “duplicato” N.B.: mittente non può distinguere caso b) “frame persa” da caso c) “ACK perso”

4. ACK ricevuto dopo la terminazione del time-out, frame è stata ritrasmessa creando “duplicato” N.B.: – in c) “ACK perso”, in d) “ACK in ritardo” => ricevente deve poter distinguere duplicati da nuove frames

– a tale scopo, ogni frame contiene nel suo header un numero di sequenza (seqnum), p.e. un bit; – ogni frame ritrasmessa contiene lo stesso seqnum della frame originale – frames duplicate sono ACK’ed (confermate al mittente) e scartate Reti di Calcolatori (Fabio Panzieri)

145

Università di Bologna - Corso di Laurea in Informatica

Stop-and wait: Frames con seqnum • • •

•

•

Ogni frame contiene seqnum di un bit (0, 1) ACK di ogni frame contiene lo stesso seqnum della frame corrispondente Perdita di frame: – No ack generato da receiver – Time out termina e sender ri-invia frame con stesso sn (finchè non riceve un ack) Perdita di ack: – Time out termina e sender ri-invia frame con stesso sn – receiver riconosce duplicato, lo scarta, e ri-invia ack N.B.: funziona perché “stop and wait” ammette che vi sia solo una frame in transito, per cui src è in attesa di ACK – elimina caso di ACK in ritardo – non sfrutta la capacità del link

Reti di Calcolatori (Fabio Panzieri)

Sender

Receiver 0 0 1 1 0 0

146

73

Università di Bologna - Corso di Laurea in Informatica

Problema con Stop-and-Wait (SaW) Bassa utilizzazione del canale •

Assumiamo link con latenza L = 50 ms – SaW prevede che mittente, dopo aver inviato frame, attenda almeno 100msec prima di inviare frame successiva • i.e., il RTT = 100ms necessario a ricevere ack

=> a) frames possono essere inviate ad un tasso massimo di 1 ogni 100 ms. •

Assumiamo dimensione frame = 8 Kb (8192 bits) a) => al più 10 frame/secondo => max. bit rate = 80 Kbps

•

Assumiamo canale con bandwidth B = 2 Mbps => solamente 4% (i.e., 80Kbps/2Mbps) della bandwidth disponibile viene utilizzato – intuitivamente, relativamente a B disponibile, in 100 msec il mittente può inviare circa 200Kb (i.e. 25 frames), ma, in conseguenza di a), invia solo 8 Kbit (i.e. 1 frame).

BitPerFrame/TempoPerFrame = 8Kb/0.1s = 80Kbps

Reti di Calcolatori (Fabio Panzieri)

147

Università di Bologna - Corso di Laurea in Informatica

In termini di delay x bandwith •

Ip: B = 2Mb; L = 50 ms => D = 0.05s => D X B = 0.05s x 2000Kbps = 100Kb – poichè assumiano un bit di ack, src potrebbe trasmettere fino a 2(DxB) = 200Kb in un RTT (i.e. 2L)

2000Kbit

50 ms

100Kb

•

Src trasmette solo 8Kb per RTT su 200 che può trasmetterne

•

Ottimizzazione dell’uso del canale:

•

Protocollo Sliding Window lo consente

=> 8/200 = 1/25, i.e. utilizza solo il 4% della capacità della “pipe”. – mittente deve poter inviare più di una frame durante l’intervallo di RTT • in esempio precedente, un massimo (teorico) = 25 frames

Reti di Calcolatori (Fabio Panzieri)

148

74

Università di Bologna - Corso di Laurea in Informatica

Protocollo Sliding Window •

Receiver

…

Sender

Time

Principio di base: – consentire al mittente di trasmettere più di una frame prima di ricevere un ACK, mantenendo così il canale impegnato. P.e.: dato un canale di capacità Delay x Bandwidth = 8Kb dimensione frame = 1Kb si richiede che – vi possano essere fino a 8 frame in transito, e che – sender possa inviare frame 9 quando riceve ACK di frame 1

=> frames contengono SNs

…

N.B.: frames inviate sono bufferizzate al sender finché non ACK’ed => limite superiore al numero di frames inviate che possono essere non ACK’ed. Reti di Calcolatori (Fabio Panzieri)

149

Università di Bologna - Corso di Laurea in Informatica

Protocollo Sliding Window (mittente) Mittente: – Assegna numero di sequenza (SeqNum) ad ogni frame – Mantiene tre variabili di stato: • “send window size” (SWS): max. num. di frames non-ACK’ed tollerabili • “last acknowledgment received” (LAR): SeqNum di ultimo ACK ricevuto • “last frame sent” (LFS): SeqNum di ultima frame inviata

– Mantiene invariante: LFS - LAR <= SWS – Quando riceve ACK, avanza LAR verso destra (i.e. fa “scorrere finestra”), abilitando la trasmissione di frame successiva – Bufferizza al più SWS frame

≤ SWS

…

… LAR

Reti di Calcolatori (Fabio Panzieri)

LFS 150

75

Università di Bologna - Corso di Laurea in Informatica

Protocollo Sliding Window (ricevente 1/2) • Ricevente: – Mantiene tre variabili di stato: • “receive window size” (RWS): max. num. di frames non ordinate che ricevente può accettare; • “largest acceptable frame” (LAF): max. SeqNum di frame accettabile • “last frame received” (LFR): SeqNum dell’ultima frame ricevuta

– Mantiene invariante: LAF - LFR <= RWS

≤ RWS

…

… LFR

LAF

Reti di Calcolatori (Fabio Panzieri)

151

Università di Bologna - Corso di Laurea in Informatica

Protocollo Sliding Window (ricevente 2/2) • Ricevente riceve frame con SN = SeqNum: – if LFR < SeqNum <= LAF then accetta frame – if SeqNum < LFR or SeqNum > LAF then scarta frame (frame è fuori finestra)

• Invia ACK “cumultativo” (per più di una frame) – Sia SeqNumToAck il numero di sequenza maggiore fra quelli non ancora ACK’ed, i.e. tale che: • tutte le frames con SeqNum < SeqNumToAck sono state ricevute e ack’ed • può avere ricevuto frames con SN > SeqNumToAck, ma non sono ordinate

– Ricevente: • invia ACK di frame con SeqNum = SeqNumToAck per indicare che tutte le frames fino a SeqNumToAck sono state ricevute • aggiorna le variabili di stato: – LFR = SeqNumToAck – LAF = LFR + RWS. Reti di Calcolatori (Fabio Panzieri)

152

76

Università di Bologna - Corso di Laurea in Informatica

Esempio •

Supponiamo LFR = 5 e RWS = 4, allora: 1. 2. – –

ultimo ack inviato da receiver era per SeqNum = 4 LAF = 9 if riceve frames 7 e 8 then accetta e bufferizza, no ACK (attende frame 6) prima o poi riceve frame 6 (p.e., in ritardo perché persa in precedente trasmissione) N.B.: se frame 6 persa, time out a sender termina, e sender ri-invia frame 6

– Ricevente può inviare singolo ACK di frames fino a, ed inclusa, frame 8 – LFR viene incrementato a 8, LAF a 12 (i.e. RWS + 8)

•

Ulteriori strategie di ACK – “negative ack” (NAK) • •

nell’esempio precedente, if 6 ricevuto dopo 4 ritrasmissione di 5, i.e. invia NAK per frame 5 NACK è ridondante, se il sender è dotato di time out

then

ricevente

richiede

– “selective ack” (SAK): ricevente invia ACK delle sole frames ricevute N.B.: facilitano sender a mantenere “pipe full”, ma aumentano complessità di receiver Reti di Calcolatori (Fabio Panzieri)

153

Università di Bologna - Corso di Laurea in Informatica

Dimensionamento di SWS e RWS •

SWS determinata in base a – RTT di singola frame e – bandwidth del canale i.e. SWS calcolata sulla base di quante frames possono essere trasmesse prima di ricevere ACK della prima frame

•

RWS determinata in base a – quante frames fuori ordine (i.e. non in sequenza regolare) il ricevente può accettare – 2 le dimensioni di RWS utilizzate comunemente: RWS = 1 i.e. ricevente non accetta frames non ordinate RWS = SWS i.e. ricevente può bufferizzare tutte le frames che il mittente invia.

•

N.B. Window Size concordata via handshake prima di iniziare trasmissione

Reti di Calcolatori (Fabio Panzieri)

154

77

Università di Bologna - Corso di Laurea in Informatica

Spazio dei numeri di sequenza • SeqNum specificato in campo, di dimensione finita, di HDR – p.e.: campo di 3 bit, SeqNum 0…7 => SeqNum devono essere riutilizzabili (campo riservato di dimensioni finite) => necessità di distinguere fra occorrenze distinte dello stesso SeqNum e duplicati => spazio dei SeqNum deve essere più grande del N. di frames non-ACK’ed

• SWS ≤ MaxSeqNum-1 non è sufficiente – – – – –

Supponiamo campo di 3-bit per SeqNum (0..7) SWS = RWS = 7 Mittente trasmette frames 0..6; ricevute ok a dst. ma ACK perso Mittente ritrasmette frames 0..6 Ricevente si aspetta 7,0..5, con frames 0…5 seconda occorrenza dello stesso SeqNum su nuove frames; invece ottiene replica di precedenti.

• Regola: SWS < (MaxSeqNum+1)/2 – intuitivamente, SeqNum “scorre” (si alterna) tra due metà dello spazio dei SeqNum Reti di Calcolatori (Fabio Panzieri)

155

Università di Bologna - Corso di Laurea in Informatica

Esempio •

HDR contiene 3 bit disponibili per SN ⇒ SN = 0,1,…,7 ⇒ SWS < (7 + 1)/2 = 4 ⇒ SWS = 3 messaggio perso time-out termina S ritrasmette

S

R sn = 0 sn = 1 sn = 2

ack = 3

sn = 0 sn = 1

ack = prossimo sn atteso

R riconosce duplicati; attendeva 3, 4, 5, 6, 7

sn = 2

Reti di Calcolatori (Fabio Panzieri)

156

78

Università di Bologna - Corso di Laurea in Informatica

Livello Data Link • Framing: costruzione dei messaggi che possono essere trasmessi/ricevuti • Individuazione di errori • Trasmissione affidabile • Controllo degli accessi in canali condivisi – – – –

CSMA/CD Token Ring FDDI 802.11

Reti di Calcolatori (Fabio Panzieri)

157

Università di Bologna - Corso di Laurea in Informatica

Canali ad accesso multiplo • A differenza dei link point-to-point, i canali ad accesso multiplo sono canali “broadcast” – Esempi: reti locali (Ethernet, Token ring), reti via satellite

• Caratteristiche principali – Canale condiviso da molteplicità di hosts – Protocollo di accesso al canale necessario per garantirne l’utilizzo senza interferenze fra hosts – Protocollo di accesso: Medium Access Control (MAC) protocol – Protocollo MAC: parte “bassa” del data link layer (MAC sub layer).

Reti di Calcolatori (Fabio Panzieri)

158

79

Università di Bologna - Corso di Laurea in Informatica

Network Adaptor • •

Host I/O bus

•

MAC implementa funzionalità di livello data link; p.e. framing, individuazione di errore Funzionalità come Automatic Repeat reQuest e “sliding window” implementate via s/w in host, di norma. Network adaptor – Interfaccia Link: implementa protocollo MAC – Interfaccia bus: implementa protocollo con host (interrupts, I/O verso memoria) – Buffers necessari a causa delle differenti velocità del bus e del link

Interfaccia

Interfaccia

Bus

Link

Network link

Adaptor Reti di Calcolatori (Fabio Panzieri)

159

Università di Bologna - Corso di Laurea in Informatica

Ethernet • Cenni storici – Sviluppata presso Xerox verso la metà degli anni 70 – Standardizzata da Xerox, DEC, e Intel nel 1978 (Ethernet standard) – Più tardi, IEEE 802.3 standard ratificato (simile a Ethernet standard). – Da allora chiamato 802.3 LAN

• Protocollo MAC di Ethernet: di tipo CSMA/CD – Carrier Sense Multiple Access/Collision Detection

• CSMA/CD – algoritmo distribuito che fornisce accesso al canale condiviso

• Bandwidth – 10Mbps, 100Mbps (Fast Ethernet), 1000 Mbps (Gigabit Ethernet)

Reti di Calcolatori (Fabio Panzieri)

160

80

Università di Bologna - Corso di Laurea in Informatica

Tecnologia Ethernet classica (thick-net) • Segmenti di cavo coassiale (impedenza: 75 ohms) – Lunghezza massima del segmento: 500m

• Segmenti connessi mediante repeaters – Non più di 4 repeaters fra ogni coppia di nodi • Lunghezza massima di una rete: 2500m

– Segnale trasmesso da un host propagato in entrambe le direzioni; repeaters propagano ulteriormente il segnale in tutti i link in uscita. – Ogni segmento è chiuso da un terminatore che assorbe il segnale impedendogli di “rimbalzare”, causando interferenze.

Reti di Calcolatori (Fabio Panzieri)

161

Università di Bologna - Corso di Laurea in Informatica

Interfaccia h/w host - Ethernet 10Base5) •

•

•

transceiver –

Percepisce stato del canale (idle/busy)

–

pilota il segnale quando l’host trasmette

Connessione fisica tra transceiver e host mediante Ethernet controller (o adaptor) –

Xmit/rcv frames a/da transceiver

–

assembla dati in formato frame

–

calcola checksum in in/out frames

–

gestisce buffers di in/out

Cavo Ethernet transceiver

controller

Distanza minima fra coppia di “transceiver”: 2.5m

Host

Reti di Calcolatori (Fabio Panzieri)

162

81

Università di Bologna - Corso di Laurea in Informatica

Tecnologia Ethernet classica (thick-net) • •

•

Numero massimo di hosts: 1024 Chiamata anche: 10Base5 – 10 : opera a 10Mbps – Base : opera in modalità baseband • uso di unica frequenza di trasmissione per tutte le stazioni collegate • ogni stazione deve “partecipare” (i.e. listen) ad ogni trasmissione – 5 : segmento può essere di 500m max. Tecnologie alternative – 10Base2 (thin-net): 200m max; configurazione a “daisy-chain” – 10BaseT (T: twisted-pair): 100m max.; configurazione a stella • segmenti punto-punto collegati ad un repeater multi-porte (Hub)

Repeaters R R R R R

Reti di Calcolatori (Fabio Panzieri)

163

Università di Bologna - Corso di Laurea in Informatica

Collegamenti in LAN 802.3 (Ethernet)

Reti di Calcolatori (Fabio Panzieri)

164

82

Università di Bologna - Corso di Laurea in Informatica

Trasmissione del segnale in 802.3 LAN •

802.3 LAN usa “Manchester encoding” (ME):

– Trasmissione di ciascun bit ha una transizione nel mezzo: • 1: da “high” (+0.85 Volts) a “low” • 0: da “low” (-0.85 Volts) a “high”. N.B.: – schema bit 0 = 0 volt, bit 1 = +ve volt, non consente di distinguere fra “sorgente idle” (0 volts) e “sorgente trasmette bit 0”; ME elimina questa limitazione. – Differential Manchester Enconding: protegge da rumore, aunenta complessità

Reti di Calcolatori (Fabio Panzieri)

165

Università di Bologna - Corso di Laurea in Informatica

Formato della frame Ethernet (Digital-Intel-Xerox)

64 bit preamble

•

48 bit

48 bit 16 bit 46 ≤ n. bytes ≤ 1500

dest. addr. src. addr. type

Body

32 bit CRC

postamble

preamble: primi 7 bytes <- 10101010 ciascuno, 8º byte <- 10101011 (Start of Frame) • Manchester encoding dei primi 7 bytes del preamble genera onda quadra (10 MHz) per 5.6 µs che abilita ricevente a sincronizzare proprio clock con mittente

• •

dest.addr, src. addr.: identificano host destinazione e sorgente type ( demultiplexing key): identifica protocollo di livello superiore

•

Body: campo dati.

– usa codici superiori al valore 1500 (cf. slide successiva) – contiene da 46 bytes min. a 1500 bytes max. – 46 byte min. necessari per individuare collisione

• •

CRC: campo di controllo errori postamble: simile a HDLC, indica fine frame N.B. Frame header a livello host: 2 indirizzi di 6 bytes ciascuno + campo type di 2 bytes. Adaptor include preamble, CRC e postamble prima di trasmettere frame. Reti di Calcolatori (Fabio Panzieri)

166

83

Università di Bologna - Corso di Laurea in Informatica

Formato della frame 802.3 LAN standard •

Differenze principali da Ethernet (Dec-Intel-Xerox) – Campo length di 16 bit al posto di type

• usato per indicare lunghezza di frame • demultiplexing effettuato mediante informazione in campo Data

– Campo Pa (Padding)

• lunghezza minima di frame deve essere 64 bytes (da Destination a Checksum); campo Pa usato per estendere lunghezza di frame se campo Data < 46 bytes

•

Osservazioni

– IEEE standard abilita indirizzi da 2 a 6 bytes di lunghezza • in pratica usati indirizzi di 6 bytes, solamente

– Length elimina necessità di postamble – può coesistere con standard Dec-Intel-Xerox

• driver in host interpreta ultimi 16 bit di hdr come type o lenght a seconda del valore contenuto

Reti di Calcolatori (Fabio Panzieri)

167

Università di Bologna - Corso di Laurea in Informatica

Indirizzamento • Indirizzi: • Indirizzo unico “unicast” di 48-bit assegnato ad ogni adaptor – 24 bit assegnati da IEEE OUI (Organizationally Unique Identifier) rimanenti da produttore • consente di assegnare 224 = 16.777.216 id. diversi

• Broadcast: tutti 1 • Multicast: primo bit è 1 (ma non tutti gli altri sono 1, in modo da distinguere Multicast da Broadcast)

• Host può programmare il proprio adaptor ad accettare un insieme di indirizzi Multicast • Adaptor programmabile ad accettare tutte le frame (modalità promiscua)

• Adaptor riceve tutte le frames, e accetta (i.e. passa al proprio host):

– Frames indirizzate al proprio indirizzo (unico) unicast – Frames indirizzate all’indirizzo broadcast – Frames indirizzate ad ogni indirizzo multicast che l’adaptor è stato programmato ad accettare – Tutte le frames, se programmato in modalità promiscua

Reti di Calcolatori (Fabio Panzieri)

168

84

Università di Bologna - Corso di Laurea in Informatica

Trasmissione • Se canale idle, adaptor: – Invia immediatamente, senza negoziare uso del canale con altri adaptors – Dimensione massima del Body inviabile: 1500 bytes => adaptor può occupare il canale per intervallo di tempo di lunghezza max. prefissata

– Deve attendere 9.6µs prima di inviare nuova frame => fairness: altri adaptors possono utilizzare il canale

• Se canale busy, adaptor: – Attende finché idle, quindi trasmette immediatamente (i.e., dopo 9.6µs) • Protocollo Ethernet chiamato 1-persistent (i.e. adaptor con frame da inviare trasmette con probabilità 1 quando canale passa da busy a idle)

– Controlla trasmissione per rilevare eventuali collisioni • Collisione: si verifica quando più adaptors trasmettono contemporaneamente • Rilevamento di collisione: segnale inviato non è quello in transito sul canale. • Minima dimensione frame = 64 bytes (i.e., 512 bits) – necessaria per garantire che collisione venga rilevata Reti di Calcolatori (Fabio Panzieri)

169

Università di Bologna - Corso di Laurea in Informatica

Rilevamento di collisione • • • • •

Sia τ il ritardo di propagazione di una frame trasmessa da stazione A alla destinazione più lontana B. Al tempo 0, stazione A invia frame a B. Subito prima che frame raggiunga B (al tempo τ − ε, ε: frazione di tempo), B inizia trasmissione di sua frame, che colide con quella da A al tempo τ Quando B rileva collisione, interrompe trasmissione e invia “rumore” (32 bit) per allertare le altre stazioni in rete. Dopo un tempo di al più 2τ, A recepisce il “rumore” e sospende trasmissione.

Reti di Calcolatori (Fabio Panzieri)

170

85

Università di Bologna - Corso di Laurea in Informatica

Rilevamento di collisione: dimensione frame

• Se frame da A è corta e trasmissione termina prima che A riceva “rumore” da B all’istante 2τ, A potrebbe concludere erroneamente che la propria frame è stata trasmessa con successo. • Prevenzione: tutte le frame devono impiegare più di 2τ. • In 10Mbps Ethernet di lunghezza max. = 2500 m, con max . 4 repeaters: τ = 51.2µs – corrisponde a trasmettere 512 bit (64 bytes), i.e. 14 bytes di header (dest.addr., src.addr., type) e almeno 46 bytes di Body, da cui il vincolo su min. num. di bytes in campo dati Reti di Calcolatori (Fabio Panzieri)

171

Università di Bologna - Corso di Laurea in Informatica

Exponential backoff • Tecnica di ritramissione in seguito a collisione • Collisione => necessario evitare che stazioni concorrentemente • Ogni adaptor riprova usando tecnica di exponential backoff

riprovino

• 1ª volta: attende tra 0 e 51.2µs, a caso e riprova. Se fallisce… • 2ª volta: attende tra 0 e 102.4µs, a caso, e riprova. Se fallisce… • 3ª volta: attende 0 e 204.8µs, a caso, e… • Rinuncia dopo vari tentativi (solitamente 16) e riporta errore

Reti di Calcolatori (Fabio Panzieri)

172

86

Università di Bologna - Corso di Laurea in Informatica

Reti Token Ring • Insieme di nodi interconnessi ad anello • Alcune tecnologie: – IBM: 4Mbps token ring (256 stazioni max.) – 16Mbps IEEE 802.5/token ring (250 stazioni max.) – 100Mbps Fiber Distributed Data Interface (FDDI) (500 stazioni max)

ethernet bridge

bridge

IBM token Ring FDDI Ring

Reti di Calcolatori (Fabio Panzieri)

173

Università di Bologna - Corso di Laurea in Informatica

Token Ring vs. Ethernet • Similarità: – algoritmo distribuito per controllo condivisione canale – tutte le stazioni ricevono tutte le frames

• Differenza: – topologia ad anello anziché a bus ⇒frame trasmessa ritorna alla stazione src; i.e., ack intrinseco

• FDDI Token Ring: – due anelli concentrici con senso di rotazione opposto – consente riconfigurazione in caso di guasti di nodo e di link

Reti di Calcolatori (Fabio Panzieri)

174

87

Università di Bologna - Corso di Laurea in Informatica

Token Ring: principio operativo • Frames trasmesse in un’unica direzione • Ogni stazione

– riceve frame da stazione vicina (upstream) – trasmette frame a stazione vicina (downstream)

• Token:

– frame contenente particolare configurazione di bit che circola sul ring

• Src: – – – –

cattura token prima di trasmettere inserisce propria frame e trasmette rimuove propria frame dal ring quando gli ritorna rilascia il token a trasmissione terminata

• i.e., consente ad altro nodo di trasmettere (“ring fairness”)

• Dst:

– Salva copia di frame, se campo destinazione contiene Dst addr. – Rilascia frame “downstream”

Reti di Calcolatori (Fabio Panzieri)

175

Università di Bologna - Corso di Laurea in Informatica

Interfaccia fisica Host-token ring b)

a)

host

host da host precedente

a host successivo

da host precedente relay

relay a)

Relay aperto: •

host funzionante • •

cattura token trasmette frame

Reti di Calcolatori (Fabio Panzieri)

a host successivo

b) Relay chiuso: •

host isolato •

in caso di giasto di nodo il ring non è interrotto

176

88

Università di Bologna - Corso di Laurea in Informatica

Formato della frame IEEE 802.5 Bytes

1 SoF

1 AC

1 FC

2o6 dst. addr.

2o6

dimensione variabile

src. addr.

Body

4 CRC

1

1

EoF Status

• SoF: start of frame; EoF: end of frame (marche di inizio e fine frame) • AC: access control – configurazione particolare di bit in AC identifica token – priorità della frame

• FC: frame control – usato per distinguere frame di dati da frame di controllo

• dst addr, src addr, CRC: come in 802.3 • Status: usato per acknowledgement/flow control da destinazione a mittente Reti di Calcolatori (Fabio Panzieri)

177

Università di Bologna - Corso di Laurea in Informatica

Consegna affidabile •

Due bit (A,C) in campo Status servono da ack – inizializzati A = 0, C = 0 – interfaccia a dst di frame • •

-

setta A = 1 if copia frame in memoria nodo OK then C = 1 else C = 0 /* trasferimento in memoria nodo fallito (p.e. buffer ricevente “full”) */

src estrae frame da ring, quando torna, e esamina bits A, C 1. [A=0, C=0] => destinazione non attiva (p.e., guasta/spenta) 2. [A=1, C=0] => destinazione attiva ma frame scartata 3. [A=1, C=1] => destinazione attiva e frame accettata

-

N.B. A=0, C=1 => combinazione non ammissibile -

se si verifica trattata come caso 1.

Reti di Calcolatori (Fabio Panzieri)

178

89

Università di Bologna - Corso di Laurea in Informatica

Protocollo di accesso principio di funzionamento • Anello “idle” – Token, costituito dai 3 bytes SoF AC EoF, circola sull’anello

• Trasmissione: – stazione cattura token, costruisce frame, trasmette • setta un bit in campo AC a indicare “ring busy”

– può trattenere token per Token Holding Time (THT) • default THT = 10 ms in 802.5.

– se THT non terminato, dopo trasmissione di una frame, può trasmettere nuova frame • prima di trasmettere nuova frame, src controlla se THT residuo è sufficiente a trasmettere tutti i bit in nuova frame

– altrimenti rigenera token di 3 bytes e lo invia sull’anello

N.B. Uso del THT determina dimensione variabile del campo Body

Reti di Calcolatori (Fabio Panzieri)

179

Università di Bologna - Corso di Laurea in Informatica

Gestione del Token Ring • Ogni ring ha una stazione eletta a monitor che individua eventuali “smarrimenti” del token • Smarrimento del token – Token non generato a tempo di inizializzazione del ring – Errore in un bit altera token e lo rende irriconoscibile – Nodo che detiene token subisce crash

• Ogni stazione può agire da monitor del ring • Monitor “sano” annuncia sua presenza con messaggio periodico – “active monitor present” = 00000101 in campo Frame Control (FC)

• Nodo che non riceve “active monitor present” sospetta guasto del monitor e si candida per diventarlo – Stessa procedura usata per eleggere monitor a tempo di bootstrap del ring Reti di Calcolatori (Fabio Panzieri)

180

90

Università di Bologna - Corso di Laurea in Informatica

Ring Monitor • Elezione del Monitor

– Nodo X invia claim frame sul ring

• annuncia propria intenzione a diventare monitor

– if claim frame torna al mittente then • Nodo X diviene Monitor • Monitor genera token

– if claim frame inviata concorrentemente da altro Nodo Y then

• X e Y eseguono “regola di risoluzione” p.e.: regola di risoluzione = nodo con indirizzo maggiore eletto monitor

• Monitoring del token (svolto da stazione monitor)

– Monitor osserva passaggio token – Per ogni passaggio attiva timeout = “max token rotation time” • max token rotation time = NumNodi x THT + LatenzaRing – LatenzaRing: ritardo di propagazione

– if timeout termina prima di passaggio token then rigenera token

• Monitor elimina frames

– “corrotte” (p.e. checksum error, formato invalido) – “orfane” (src ha subito crash)

Reti di Calcolatori (Fabio Panzieri)

181

Università di Bologna - Corso di Laurea in Informatica

FDDI •

Ring secondario entra in funzione in caso di guasto del primario e riconfigurazione Host A Host A

crash Host B

Host B

Host D

Host D

Host C

Reti di Calcolatori (Fabio Panzieri)

Host C

182

91

Università di Bologna - Corso di Laurea in Informatica

Formato della frame FDDI 8 bit

8 bit

SoF

Control

16 o 48 bit 16 o 48 bit dst. addr.

src. addr.

n. bytes ≤ 4478

Body

8 bit

32 bit

CRC

24 bit

EoF

Status

• Standard supporta indirizzi di 16 o 48 bit – 48 bit è il formato solitamente usato

• Start of frame/ End of frame:

– sequenza di bit che identifica inizio/fine frame

• Control: informazione riguardo la frame

– bit 1 = 0: frame trasporta traffico asincrono; bit 1 = 1: frame trasporta traffico sincrono – bit 2 = 0: indirizzi di 16 bit; bit 2 = 1: indirizzi di 48 bit – bit 3 … bit 8: demultiplexing key come campo type in frame Ethernet

•

• alcuni types di frame riservati per uso interno del protocollo FDDI P.E.: token identificato da una configurazione speciale del campo control

Status: settato dalla destinazione per riportare al mittente informazione di stato frame – P.E.: ricevuta frame errata – utilizzabile da dst. per implementare controllo di flusso

• P.E.: informa mittente di non avere sufficiente memoria per bufferizzare frame

Reti di Calcolatori (Fabio Panzieri)

183

Università di Bologna - Corso di Laurea in Informatica

IEEE 802.11 (reti wireless) • Standard di comunicazione per uso geograficamente limitate (abitazioni, uffici)

in

aree

• Responsabilità principale: – Accesso a “canale condiviso”: i.e., “spazio”

• Specificato per operare utilizzando 2 supporti fisici – radio frequenza • 802.11b: 2.4 GHz, 11Mbps • 802.11a: 5GHz, 54Mbps

– infrarosso: 2Mbps, range = 10m (approx.)

Reti di Calcolatori (Fabio Panzieri)

184

92

Università di Bologna - Corso di Laurea in Informatica

IEEE 802.11 tecniche di trasmissione • Frequency hopping: trasmette segnale usando una sequenza “casuale” di frequenze: • “casuale”: prodotta da un generatore di numeri pseudo-casuali noto a src e dst

• Direct sequence: rappresenta ogni bit come sequenza di bit ottenuta da XOR di quel bit e n-bit chipping code • n-bit chipping code: sequenza di bit casuali nota a src e dst p.e.: 4-bit chipping code: 1 0

Flusso dati: 1010

1 0

n-bit chipping code: 0100 |1011 | 0101 | 1001

1 0

Sequenza ottenuta 1011 | 1011 | 1010 | 1001

XOR

Reti di Calcolatori (Fabio Panzieri)

185

Università di Bologna - Corso di Laurea in Informatica

Collisioni • Simile a Ethernet – Attende link idle – Trasmette – if collisione_rilevata then exponential back off • Complicato dal fatto che nodi non sempre mutualmente raggiungibili – ogni nodo rileva presenza dei nodi nel proprio raggio di copertura, esclusivamente

• Problemi: – nodi nascosti – nodi esposti Reti di Calcolatori (Fabio Panzieri)

186

93

Università di Bologna - Corso di Laurea in Informatica

Nodi nascosti •

Figura illustra raggio copertura di B e C

di

•

A sente B ma non C e D; B sente A e C, ma non D; C sente B e D, ma non A.

•

A e C inviano frame a B contemporaneamente => collisione

N.B.: •

A

B

C

D

A e C non a conoscenza di reciproca esistenza =>

non possono collisione

prevenire

Reti di Calcolatori (Fabio Panzieri)

187

Università di Bologna - Corso di Laurea in Informatica

Nodi esposti • • • •

B trasmette ad A C vuole trasmettere a D C rileva trasmissione da B ed assume canale occupato C non trasmette per non creare interferenze => decisione errata:

A

B

C

D

– C può trasmettere a D senza creare interferenze con comunicazioni da B ad A – C non può/deve trasmettere a B

Reti di Calcolatori (Fabio Panzieri)

188

94

Università di Bologna - Corso di Laurea in Informatica

Protocollo MACAW: Multiple Access Collision Avoidance for Wireless LANs • Src invia RequestToSend (RTS) frame

• informa i vicini di richiesta di accesso al canale • frame contiene campo “durata”, indica per quanto tempo src impegnera’ canale

• Dst risponde con ClearToSend (CTS) frame • Vicini:

• intercettano CTS: non trasmettono (sono vicini al dst, possono inteferire) • intercettano RTS ma non CTS: possono trasmettere (non creano interferenze)

• Dst invia ACK quando ha ricevuto frame

• Vicini non trasmettono fin quando non intercettano ACK

• Collisoni • • • • •

Due nodi inviano RTS concorrentemente; RTS frames collidono Non vi è meccanismo di individuazione di collisone Collisione scoperta quando non ricevono CTS dopo timeout Exponential backoff: riprova dopo attesa “casuale” (cf. IEEE 802.3)

Reti di Calcolatori (Fabio Panzieri)

189

Università di Bologna - Corso di Laurea in Informatica

Sistema di distribuzione • Ambito wireless: – comunicazioni abilitate dipendentemente da distanza fra nodi – nodi “mobili” =>insieme dei nodi abilitati a comunicare fra loro varia nel tempo

• IEEE 802.11 definisce infrastruttura supporta “mobilità”, e consiste di:

aggiuntiva

che

– nodi mobili: abilitati a “roaming” (mobilità) – Access Points (APs): nodi fissi connessi a infrastruttura di rete (cablata) detta Sistema di Distribuzione (SdD) • Ogni AP serve una “regione” e abilita comm’s fra nodi nella propria regione – regione: anologa a cella in infrastruttura di supporto a telefoni cellulari

Reti di Calcolatori (Fabio Panzieri)

190

95

Università di Bologna - Corso di Laurea in Informatica

Sistema di distribuzione •

Ogni nodo mobile si connette ad un AP – P.e.: comunicazione A <-> E: • A invia frame ad AP-1 • AP-1 invia frame ad AP-3 • AP-3 invia frame ad E

Distribution system

– Come fa AP-1 a scoprire di dover inviare ad AP-3? • non in IEEE 802.11 • può usare standard definito per rete fissa (p.e., BGP)

•

AP-1

AP-3 F

AP-2 A

IEEE 802.11 definisce protocollo di – selezione dell’AP – gestione della mobilità del nodo da una cella all’altra

B

G H

C

E D

Reti di Calcolatori (Fabio Panzieri)

191

Università di Bologna - Corso di Laurea in Informatica

Selezione dell’AP •

•

•

Protocollo di “active scanning” 1.

Nodo src invia frame di PROBE (sonda)

2.

Tutti gli APs raggiungibili rispondono con frame PROBE_RESPONSE

3.

Nodo src seleziona un AP (p.e., quello con segnale migliore), e invia frame ASSOCIATION_REQUEST

4.

AP risponde con ASSOCIATION_REPONSE

Active scanning eseguito a)

ogni volta che nodo entra in rete

b)

quando segnale da AP corrente si attenua (p.e., causa movimento del nodo)

–

N.B.: quando nodo si connette a nuovo AP, questo informa AP precedente del movimento del nodo attraverso SdD.

Oltre ad active scanning: “passive scanning” –

ogni AP invia periodicamente frame speciale (BEACON) che annuncia prestazioni dell’AP (p.e., velocità di trasmissione supportate)

–

ogni nodo può cambiare AP quando ne rileva BEACON

Reti di Calcolatori (Fabio Panzieri)

192

96

Università di Bologna - Corso di Laurea in Informatica

Formato frame 802.11 bits

16

16

48

Control Duration Addr1

48 Addr2

48 Addr3

16 SeqCtrl

48 Addr4

0 - 18.496

P a y l o a d

32 CRC

• Control: contiene 3 sottocampi – Type (6 bits): indica se frame contiene DATI, RTS, CTS, o è usata da protocollo di scanning – ToDS, FromDS bits: consentono intrepretazione di campi Addr

• Duration: durata dell’utilizzo del canale • Addr1,2,3,4: campi indirizzi (cf. slide successiva) • Payload: 2312 B max • SeqCtrl: n. di sequenza frame • CRC: ciclic redundancy checksum Reti di Calcolatori (Fabio Panzieri)

193

Università di Bologna - Corso di Laurea in Informatica

ToDS FromDS bits • Identificano provenienza frame – i.e., se da src a dst entrambe in medesima regione o attraverso SdD

• ToDS = 0, FromDS = 0 – src e dst in medesima regione => Addr1 = dst finale Addr2 = src “origine”

• ToDS = 1, FromDS = 1: – frame proviene da nodo mobile via SdD, e da qui a nodo mobile => Addr1 = dst finale Addr2 = src più “recente” (ha effettuato forward di frame) Addr3 = src “intermedia” (ha accettato frame da src “origine” e l’ha trasmessa via SdD) Addr4 = src “origine” Reti di Calcolatori (Fabio Panzieri)

194

97

Università di Bologna - Corso di Laurea in Informatica

Esempio

Distribution system

• A trasmette ad E – – – –

Addr1 = E Addr2 = AP-3 Addr3 = AP-1 Addr4 = A

AP-1

AP-3 F

AP-2 A

B

G H

C

E D

Reti di Calcolatori (Fabio Panzieri)

195

Università di Bologna - Corso di Laurea in Informatica

IEEE 802.15 • Deriva da standard industriale Bluetooth • Copertura geografica – raggio limitato (10m) • conseguenza di potenza di trasmissione molto bassa

• bit rate < 1Mbps • robustezza – poichè potenza di trasmissione è molto bassa, dispositivi più potenti (p.e., 802.11) possono interferire e degradare il segnale Bluetooth

• IEEE 802.15 vs. IEEE 802.11 – IEEE 802.11 estende standard 802.3 – copertura geografica: fino a 150m (in interni), fino a 300m in esterno – bit rate: • 802.11 originale da 1Mbps a 2Mbps • 802.11b da 5.5Mbps a 11Mbps (throughput reale atteso: 4 - 5 Mbps) • 802.11a da 24Mbps a 54Mbps (throughput reale atteso: 10 - 22 Mbps

– robustezza: non subisce interferenze da dispositivi Bluetooth Reti di Calcolatori (Fabio Panzieri)

196

98

Università di Bologna - Corso di Laurea in Informatica

Bluetooth http://www.bluetooth.com: • Unlike many other wireless standards, the Bluetooth wireless specification includes both link layer and application layer definitions for product developers which supports data, voice, and content-centric applications. Radios that comply with the Bluetooth wireless specification operate in the unlicensed, 2.4 GHz radio spectrum ensuring communication compatibility worldwide. These radios use a spread spectrum, frequency hopping, full-duplex signal at up to 1600 hops/sec. The signal hops among 79 frequencies at 1 MHz intervals to give a high degree of interference immunity. Up to seven simultaneous connections can established and maintained.

Reti di Calcolatori (Fabio Panzieri)

197

Università di Bologna - Corso di Laurea in Informatica

Interconnesione di reti locali a livello data link (LAN estese) •

Limiti di singola LAN – supporta traffico limitato • su LAN singola, le stazioni condividono bandwidth

– lunghezza limitata (p.e., 802.3 specifica lunghezza max.) – numero limitato di stazioni (in 802.5 ritardo del passaggio del token) – collisioni

•

Soluzioni: interconnesione di due o più LANs mediante – Hubs – Bridges a livello data link • i.e., senza introdurre pkt header addizionale

Reti di Calcolatori (Fabio Panzieri)

198

99

Università di Bologna - Corso di Laurea in Informatica

Dispositivi di interconnessione: repeaters, hubs, bridges •

Repeater: dispositivo di livello fisico, i.e. propaga segnali elettrici fra due segmenti Ethernet; usato per estendere singola rete Ethernet.

•

Hub: repeater multi-porte

•

Bridge: trasmette frames di livello data link da una rete fisica ad un altra (detto anche switch di LAN); usato per interconnettere LANs

ethernet repeater

bridge

bridge

IBM token Ring FDDI Ring

Reti di Calcolatori (Fabio Panzieri)

199

Università di Bologna - Corso di Laurea in Informatica

Hubs •

Dispositivi di interconnesione a livello fisico – i.e. repeaters multi-porta che operano a livello fisico (i.e., di segnale):

•

Consentono interconnessione di LANs omogenee (i.e., medesima tecnologia)

•

– singola LAN: segmento di LAN estesa Organizzabili in gerarchia (o “multi-tier design”):

• propagano segnali ricevuti da porta di input a tutti le porte di output

– radice: “backbone hub”

Reti di Calcolatori (Fabio Panzieri)

200

100

Università di Bologna - Corso di Laurea in Informatica

Hub (vantaggi) • Semplice e poco costoso • Multi-tier design garantisce riduzione graduale del servizio (“graceful degradation”) – i.e., segmenti continuano a funzionare anche se un hub si guasta

• Estende distanza massima fra coppie di nodi – E.g.: 10BaseT • 100 m dist. max. fra coppia di nodi • segmenti 10BaseT collegati via Hub: 100 m dist. max. fra nodo e hub => 200 m dist. max. fra coppia di nodi

Reti di Calcolatori (Fabio Panzieri)

201

Università di Bologna - Corso di Laurea in Informatica

Hubs (limiti) • Hubs non isolano collisioni su singolo segmento – creano singolo dominio di collisione • i.e. se si verifica collisione, su qualunque segmento, ogni nodo in trasmissione esegue exponential backoff

• Singolo dominio di collisione non aumenta bandwidth – multi-tier bandwidth = bandwidth di singolo segmento E.g.: LAN estesa di tre reti interdipartimentali da 10 Mbps ciascuna • bandwidth aggregata potenziale = 30Mbps • interconnesse con hub, appartengono allo stesso dominio di collisione => bandwidth aggregata = 10Mbps

• Limitazioni di singolo segmento limitano n. di nodi nel dominio di collisione e copertura geografica totale • Non consentono interconnesione di tecnologie diverse – propagano segnali, non bufferizzano frames, non consentono interconnessione di segmenti con diverse velocità (e.g., Ethernet 10BaseT e 100baseT) Reti di Calcolatori (Fabio Panzieri)

202

101

Università di Bologna - Corso di Laurea in Informatica

Bridge •

Dispositivo multi-porta collocato a livello Data Link – lavora su frames del protocollo data link (p.e., CSMA/CD di Ethernet) in modalità “store and forward” – store…: bufferiza frame ed esamina campo “dst” in frame header – …and forward: inoltra frame verso destinazione sulla base del dst address in frame • utilizza data link protocol di specifico segmento di rete per trasmettere (i.e., abilita interconnessione di reti eterogene) Il problema: • se frame per B è ricevuta su Porta 1, non occorre che Bridge la inoltri via Port 2 • come dotare il Bridge di sufficiente info per determinare cosa inoltrare e attraverso quale Port#?

A

B

C Port 1 Bridge Port 2 X

Y

Z

Reti di Calcolatori (Fabio Panzieri)

203

Università di Bologna - Corso di Laurea in Informatica

Bridge: funzioni principali •

Filtering – determinare se inoltrare o scartare una frame • scarta frame se src e dst connessi a medesima LAN

•

Forwarding – determinare la porta di output (i.e., l’interfaccia di LAN) cui una frame deve essere diretta

•

Decisione presa sulla base di “tabella di filtering” mantenuta da bridge – tabella associa porte di output a nodi della rete (non necessariamente tutti) – costruita automaticamente e mantenuta dinamicamente • non richiede configurazione iniziale • bridge auto-apprende (“learning bridge”) locazione hosts su LANs e costruisce tabella

Reti di Calcolatori (Fabio Panzieri)

204

102

Università di Bologna - Corso di Laurea in Informatica

Filtering • Bridge auto-apprende attraverso quali porte può raggiungere quali hosts quando attraversato da frame – frame in input: bridge legge indirizzo src in frame – mantiene/aggiorna tabella di filtering • registra in tabella indirizzo src e relativa porta da cui ha ricevuto frame

• Entry in tabella – – Time Stamp: data di ingresso dell’entry in tabella

– Entry obsolete vengono scartate (TTL: 60’)

Reti di Calcolatori (Fabio Panzieri)

205

Università di Bologna - Corso di Laurea in Informatica

Procedura di filtering … /* esamina frame */ if dst in medesima LAN di src then scarta frame else {

/* trasmessa comunque da src */

cerca dst in tabella di filtering if entry contenente dst trovata then forward frame su porta indicata in tabella else forward frame su tutte le porte eccetto quella di provenienza }

…

Reti di Calcolatori (Fabio Panzieri)

206

103

Università di Bologna - Corso di Laurea in Informatica

Learning bridge: esempio •

Ip.: C invia frame a D e D risponde a C con nuova frame

tabella di filtering

• C invia frame; bridge non ha info per D, inoltra frame su LAN 2 e 3 – bridge registra che C è su porta 1 (i.e., aggiorna tabella) – frame ignorata in LAN 3 – frame trasmessa a D Reti di Calcolatori (Fabio Panzieri)

207

Università di Bologna - Corso di Laurea in Informatica

Esempio: learning bridge • D invia risposta a C – bridge attraversato da frame da D – bridge registra che D è su porta 2 – tabella contiene entry per C (C associato a porta 1) • bridge trasmette frame via porta 1 esclusivamente • successive comunicazioni C <-> D via porte 1 e 2 esclusivamente tabella di filtering

address port A 1 B 1 C 1 D 2 E 2 H 3 J 3 Reti di Calcolatori (Fabio Panzieri)

208

104

Università di Bologna - Corso di Laurea in Informatica

Interconnessione di LANs via bridge

• Soluzione sconsigliata – Hub di CS Dept.: singolo punto di guasto – traffico tra EE and SE deve passare attraverso segmento CS

Reti di Calcolatori (Fabio Panzieri)

209

Università di Bologna - Corso di Laurea in Informatica

Interconnessione di LANs via bridge: backbone bridge

• Pros: risolve problema di hub e traffico superfluo • Cons: bridge diviene singolo punto di guasto Reti di Calcolatori (Fabio Panzieri)

210

105

Università di Bologna - Corso di Laurea in Informatica

Bridges ridondanti •

Per aumentare affidabilità necessario avere link/cammini alternativi (ridondanti) da src a dst, via bridges diversi – però: cammini alternativi possono provocare cicli • bridges possono replicare e trasmettere frames indefinitamente

•

Soluzione: – organizzare bridges in grafo aciclico (o “spanning tree” = albero di copertura) disabilitando sotto-insieme di porte

collegamento disabilitato

collegamento disabilitato Reti di Calcolatori (Fabio Panzieri)

211

Università di Bologna - Corso di Laurea in Informatica

Algoritmo di spanning tree •

Problema dei loop –

•

A

B1, B4, B6 formano ciclo

Bridges eseguono algoritmo distribuito di “spanning tree” – determina quali bridge effettuano il forwarding – ideato da Radia Perlman (DEC) – standard IEEE 802.1

B

B3

C E

D

B2

B5 B7

K F

B1 G

H I

B6

B4 J

B3

B3

B5

B5

B7

B2

B1

B6

B4

Reti di Calcolatori (Fabio Panzieri)

Algoritmo di spanning tree Trasforma grafo con cicli in un sottografo senza cicli, contenente tutti i vertici,

B7

B2

B1

B6

B4 212

106

Università di Bologna - Corso di Laurea in Informatica

Obiettivi principali dell’algoritmo 1. Rendere trasparente ai nodi l’eventuale internetwork di LANs • i.e., extended LAN = LAN, dal punto di vista del nodo

2. Consentire uso di bridges ridondanti in LAN estese al fine di far fronte a guasti 3. Essere auto-configurante • ogni nodo conosce solo il suo ID (MAC address)

4. Scalabile: requisiti di memoria di bridge non devono aumentare con l’aumentare del n. di LANs o bridges 5. Bandwidth usata da alg. deve essere costante, indipendentemente dal n. di bridges e LANs nell’extended network 6. Alg. deve “stabilizzarsi” (i.e., produrre uno spanning tree deterministico) rapidamente, indipendentemente dal n. di bridges e LANs nell’extended network • in un multiplo del round trip time di rete, in assenza di guasti e perdita di msgs o successivamente alla riparazione di un guasto. Reti di Calcolatori (Fabio Panzieri)

213

Università di Bologna - Corso di Laurea in Informatica

Obiettivi principali dell’algoritmo 7. Consentire caching al bridge della locazione dei nodi in LAN estesa; i.e., – ogni bridge seleziona le porte attraverso cui trasmettera’ frames; – ogni bridge mantiene DB di indirizzi per limitare traffico

8. Garantire assenza di loop permanenti, e minimizzare probabilità di loop temporanei 9. Spezzare gli eventuali loops anche se alcuni bridge non implementano questo algoritmo (alcuni , ma non tutti, ovviamente) 10. Essere basato su servizio “datagram” • i.e., servizio “connectionless” (o “best effort”) a livello DataLink

11. Configurabile (mediante settaggio di parametri ) secondo la specifica configurazione di LAN estesa in cui viene eseguito Reti di Calcolatori (Fabio Panzieri)

214

107

Università di Bologna - Corso di Laurea in Informatica

Algoritmo “spanning tree” •

Ogni bridge identificato da id unico (e.g., B1, B2, B3, …)

•

Algoritmo nomina bridge con id minore come “root”

•

Algoritmo nomina, in ogni LAN, il bridge più vicino a root “bridge designato” –

responsabile per effettuare forwarding di frames da LAN verso radice •

se più di 1, sceglie quello con id minore

•

Inizialmente, ogni bridge assume di essere root (quindi “designato”)

•

Ogni bridge invia frames su ogni LAN per cui è stato nominato “bridge designato” (bridge non designati scartano frames)

•

Bridge scambiano “messaggi di configurazione” (cfg_msg) delle porte contenenti: –

id del bridge mittente del msg

–

id del bridge che mittente presume sia root

–

distanza (hops) fra mittente a presunta root

Reti di Calcolatori (Fabio Panzieri)

215

Università di Bologna - Corso di Laurea in Informatica

Algoritmo “spanning tree” •

Ogni bridge mantiene il miglior cfg_msg ricevuto da ogni porta (scartando eventuali “migliori” precedenti) –

miglior cfg_msg contiene: • • •

root con id minore, oppure root con id uguale ma distanza minore, oppure root con id e distanza uguali ma bridge mittente ha id minore

– if miglior cfg_msg ricevuto then

• incrementa campo “distanza da radice” • scarta eventuali “migliori” precedenti

•

Se scopre di non essere root, interrompe generazione cfg_msg

•

Se scopre di non essere bridge designato interrompe trasmissione di cfg_msg

• •

Root invia cfg_msg periodicamente Se qualche bridge non riceve cfg_msg, dopo time out assume di essere root e genera cfg_msg

– –

a regime, solo root genera cfg_msg a regime, solo bridge designati trasmettono cfg_msg

Reti di Calcolatori (Fabio Panzieri)

216

108

Università di Bologna - Corso di Laurea in Informatica

• •

•

Esempio

Istante di bootstrap: – ogni bridge ha tabella vuota – ogni bridge assume di essere root Cfg-msg da bridge X: – Y: id di presunta root – d: distanza di X da presunta root – X: id di bridge mittente Esempio B3 invia (B3,0,B3); riceve (B2, 0, B2)

• 2 < 3 => B3 accetta B2 come root • B3 somma 1 a distanza 0 annunciata da B2 e invia (B2, 1, B3) a B5

B2 riceve (B1, 0, B1) da B1, accetta B1 come root, invia a B3 (B1, 1, B2) B5 riceve (B1, 0, B1) da B1, accetta B1 come root, e invia a B3 (B1, 1, B5) B3 accetta B1 come root, registra che B2 e B5 sono più vicini a root di lui (quindi designati per LANs C e A), sospende trasmissione messaggi su entrambe le sue interfacce, restando con entrambe le porte non selezionate (spezzando eventuale loop)

A B

B3

C E

D

B2

B5 B7

K F

B1 G

H I

B6

B4 J

Reti di Calcolatori (Fabio Panzieri)

217

Università di Bologna - Corso di Laurea in Informatica

Bridge • Vantaggi – mantiene isolati i domini di collisione dei singoli segmenti • consente uso concorrente di segmenti distinti

– può interconnetere tecnologie diverse (grazie a “store and forward”) se queste usano medesimo formato indirizzi di 48 bit • Ethernet-Ethernet, Ethernet-802.5 (ring), 802.5-802.5

– non limita dimensioni di LAN estesa – trasparente: non richiede modifiche agli adaptors di LAN incorporati negli hosts

• Svantaggi – Algoritmo di spanning tree scala linearmente; i.e.: • all’aumentare del n. di LANs il tempo di exec. aumenta linearmente => uso limitato a qualche decina di LANs Reti di Calcolatori (Fabio Panzieri)

218

109

Università di Bologna - Corso di Laurea in Informatica

OSI RM

End host

End host

Application

Application

Presentation

Presentation

Session

Session

Transport

Transport

Network

Network

Network

Network

Data link

Data link

Data link

Data link

Physical

Physical

Physical

Physical

Uno o piu’ nodi di rete

Reti di Calcolatori (Fabio Panzieri)

219

Università di Bologna - Corso di Laurea in Informatica

Livello Network •

Requisito – abilitare comunicazioni fra ogni coppia di nodi, anche non direttamente connessi, in rete composta da numero arbitrario di nodi • hosts possono essere separati da una combinazione arbitraria di reti (WANS, LANs)

•

Reti a connessione diretta – Limiti di scalabilità (dovuti a tecnologia di comuunicazione) • Link punto-punto: collega 2 nodi • 1024 nodi max in Ethernet • Distanza geografica limitata

•

LAN estese – Limiti di scalabilità (dovuti a tecnologia “bridge”) • Algoritmo di spanning tree • Eterogeneità

Reti di Calcolatori (Fabio Panzieri)

220

110

Università di Bologna - Corso di Laurea in Informatica

Livello Network • Soddisfa requisito in reti a commutazione di pacchetto (Packet Switched Network) consistenti di links, switches e routers • Responsabilità principale: – instradamento dei pacchetti da src a dst • calcolo della rotta

– internetworking • hosts devono possedere un identificatore unico globale

• Dispositivi di interconnessione: – switches, routers (spesso usati come sinonimi)

Reti di Calcolatori (Fabio Panzieri)

221

Università di Bologna - Corso di Laurea in Informatica

•

•

Dispositivi di interconnessione: switches e routers

Switch: – trasmette pacchetti di livello network da porta di input a porta di output – utilizza informazione di indirizzamento contenuta negli header dei pacchetti stessi – usato per interconnettere reti omogenee. Router: – Trasmette pacchetti di livello network – usato per interconnettere reti eterogenee.

switch

Reti di Calcolatori (Fabio Panzieri)

router

222

111

Università di Bologna - Corso di Laurea in Informatica

Switch • Trasmette pacchetti da una porta di input ad una porta di output – se connesso a più link, esegue i protocolli data link di ciascuno

• Seleziona porta di output sulla base di indirizzo dst in pkt hdr • Originariamente implementati da computers “general-purpose” – Switches moderni implementati da hardware specializzato – Tecnologia switch consente di • costruire reti che coprono vaste aree geografiche – i link fisici possono essere linee telefoniche pubbliche, fibre ottiche, microonde … • costruire reti che interconnettono un vasto numero di computers • estendere la rete con computers (hosts) addizionali senza interferire con le prestazioni degli hosts già in rete

Reti di Calcolatori (Fabio Panzieri)

223

Università di Bologna - Corso di Laurea in Informatica

Switches e links •

Switches e links – infrastruttura per costruire una WAN

•

Switch – collegato a molteplicità di links – esegue protocollo data link appropriato su ogni link per comunicare con host connesso direttamente allo stesso link – responsabilità principale: instradamento di pacchetti i.e. riceve pacchetti da uno dei suoi links e li trasmette su un altro dei suoi link.

Reti di Calcolatori (Fabio Panzieri)

224

112

Università di Bologna - Corso di Laurea in Informatica

Switches: proprietà •

Scalabilità della rete: – –

•

singolo switch: n. limitato di porte di I/O limita n. di hosts che possono essere connessi ad esso, però interconnessione di switches: consente implementazione di reti “switched” con vasta copertura geografica

Ottimizzazione prestazioni: –

Connessione di host a switch via link punto-punto => host puo’ trasmettere sfruttando bandwidth completa del link N.B.: switch deve fornire sufficiente “bandwidth aggregata” => connessione di nuovo host a rete “switched” non implica prestazionale per gli hosts già connessi

degrado

≠ da rete “shared” (e.g. Ethernet, token ring) – impossibile per due hosts su rete shared trasmettere alla velocità della rete (causa: condivisione)

Reti di Calcolatori (Fabio Panzieri)

225

Università di Bologna - Corso di Laurea in Informatica

Instradamento (switching/forwarding) • Scelta della porta di output su cui trasmettere pkt – switch esamina identificatore di destinazione in pkt hdr e lo usa per decidere porta di output.

• Scelta effettuata sulla base di “tabelle di forwarding” (o “routing tables”) • N.B.: Switching/Forwarding ≠ Routing – Forwarding: come sopra – Routing: processo di costruzione delle tabelle di routing • avviene in background • Consente di gestire variazioni (i.e. dinamicità) della topologia della rete • abilita percorsi multipli verso destinazioni

Reti di Calcolatori (Fabio Panzieri)

226

113

Università di Bologna - Corso di Laurea in Informatica

Instradamento •

Tre approcci principali: • “datagram”: – ogni pacchetto è instradato indipendentemente dagli altri • “circuito vituale” (o “connection-oriented”): – percorso (connessione) da src a dst inizializzato prima di trasferimento dati, usando qualche tecnica di routing – i pacchetti da src a dst seguono quel percorso per tutta la durata della connessione. • “source routing”: – header del pacchetto specifica l’intera rotta. – semplice, ma non scalabile (assume che ogni src conosca topologia di rete per costruire header).

•

N.B.

– Network layer in OSI RM fornisce servizi connection-oriented e connection-less a transport layer • Transport layer in Internet richiede solo servizio connection-less da network layer.

Reti di Calcolatori (Fabio Panzieri)

227

Università di Bologna - Corso di Laurea in Informatica

Datagram routing

(connection-less routing)

• Non richiede di stabilire connessione – –

Ogni pacchetto contiene l’indirizzo dst completo Ogni switch mantiene una tabella di instradamento

• Pacchetti trasmessi indipendentemente uno dall’altro (non garantisce ordinamento) •

Simile a sistema postale; ogni lettera inviata/consegnata indipendentemente dalle altre Switch 2 Dest

Reti di Calcolatori (Fabio Panzieri)

Porta I/O

A

3

B

0

C

3

D

3

E

2

F

1

G

0

H

0 228

114

Università di Bologna - Corso di Laurea in Informatica

Datagram routing: proprietà 1. Host può inviare datagram in qualunque istante di tempo a qualunque destinazione – Switch inoltra datagram appena lo riceve, se la sua tabella di forwarding è correttamente configurata

2. Host non può sapere se datagram verrà inoltrato da switch o no, nè se la destinazione sia attiva, nè se la rete consegni datagrams 3. Due datagrams in sequenza da medesimo host possono seguire rotte diverse verso la medesima destinazione 4. Switch o link guasto possono essere “aggirati” se esiste rotta alternativa => tabella di forwarding degli switch deve essere agiornata Reti di Calcolatori (Fabio Panzieri)

229

Università di Bologna - Corso di Laurea in Informatica

Virtual circuit routing (connection-oriented routing) •

Richiede fase esplicita di attivazione (e disattivazione) “connessione” (o circuito virtuale) fra host src e host dst

di

=> Trasferimento dati in due fasi sequenziali: 1. “connection set-up” 2. “data transfer”

•

Connection set-up: – costruzione di “stato” della connessione all’interno degli switch tra src e dst (i.e. costruzione delle tabelle di fowarding negli switches) – effettuata mediante protocolllo di “signalling” •

•

“signalling”: scambio di messaggi fra host src, switches, e host dst

Data transfer – tutti i data pkts da src a dst inviati su connessione consegnati nell’ordine di trasmissione (principio simile a chiamata telefonica, i.e. PVC)

Reti di Calcolatori (Fabio Panzieri)

230

115

Università di Bologna - Corso di Laurea in Informatica

Virtual circuit routing: esempio •

Host A invia richiesta di connessione a Switch 1 contenente indirizzo completo di B;

•

Switch 1

–

connection request trasmessa/consegnata a Switch 1 via porta 2 •

– – –

assumere che ogni switch conosca la propria porta di uscita verso destinazione

assegna VCI unico localmente a connessione da A verso B, p.e. 5; crea entry incompleta in tabella per la richiesta di connessione da A a B => trasmettere via porta 1 tutti i pacchetti da porta 2, con VCI = 5; N.B.: dovrà informare A di usare VCI = 5 per comunicazioni con B Invia a Switch 2 via porta 1 richiesta di connessione di A a B

0 Switch 1 1

3

2 B

B

Tabella connessioni in Sw1

in i/f

in vci

2

5

……

……

out i/f

3

2 Switch 2 1 0

out vci

Host A

1

B 0 Switch 3 3

1

2

B

Host B

Reti di Calcolatori (Fabio Panzieri)

231

Università di Bologna - Corso di Laurea in Informatica

Virtual circuit routing: esempio •

Switch 2 – assegna VCI unico localmente a connessione da A a B, p.e. 11; – crea entry incompleta in tabella per la richiesta di connessione da A a B => trasmettere via porta 0 tutti i pacchetti da porta 2, con VCI = 11; N.B.: dovrà informare Switch 1 di usare VCI = 11 per comunicazioni con B – Invia a Switch 3 via porta 0 richiesta di connessione di A a B

0 Switch 1 1

3

2 B

Tabella connessioni in Sw2

in i/f

in vci out i/f

3

11

……

……

out vci

3 B

2 Switch 2 1 0

Host A

0

B 1

0 Switch 3 3 2

Reti di Calcolatori (Fabio Panzieri)

B

Host B 232

116

Università di Bologna - Corso di Laurea in Informatica

Virtual circuit routing: esempio •

Switch 3 – assegna C_Id unico localmente a connessione da A a B, p.e. 7; – crea entry incompleta in tabella per la richiesta di connessione da A a B => trasmettere via porta 3 tutti i pacchetti da porta 0, con VCI = 7; N.B.: dovrà informare Switch 2 di usare VCI = 7 per comunicazioni con B – Invia a B via porta 3 richiesta di connessione da A 0 Switch 1 1

3

2

3

B

Tabella connessioni in Sw3

in i/f

in vci

out i/f

0

7

3

……

……

B

2 Switch 2 1 0

Host A

out vci

B 1

0 Switch 3 3 B

2

Host B

Reti di Calcolatori (Fabio Panzieri)

233

Università di Bologna - Corso di Laurea in Informatica

Virtual circuit routing: esempio •

Host B accetta (o scarta) la connection request ed invia ack (o nack) ad A seguendo il percorso inverso. –

•

–

alloca un VCI unico (localmente), p.e. 4; • VCI = 4 identificherà univocamente a B tutti i pkts provenienti da A invia a switch 3 ack contenente il VCI = 4 selezionato

– –

completa la sua forwarding table inserendo VCI = 4 in “out vci” invia ack (nack) di B a Switch 2 contenente VCI = 7

– –

completa la sua forwarding table inserendo VCI = 7 in “out vci” invia ack (nack) di B a Switch 1 contenente VCI = 11

– –

completa la sua forwarding table inserendo VCI = 11 in “out vci” invia ack (nack) di B ad A contenente VCI = 5

Switch 3

•

Switch 2

•

Switch 1

Tabella connessioni in Sw3 in i/f

in vci

out i/f

out vci

0

7

3

4

……

……

Reti di Calcolatori (Fabio Panzieri)

Tabella connessioni in Sw2 in i/f

in vci out i/f

3

11

……

……

0

out vci

7

Tabella connessioni in Sw1 in i/f

in vci

2

5

……

……

out i/f

1

out vci

11

234

117

Università di Bologna - Corso di Laurea in Informatica

Esempio (segue) • Trasmissione dati – Se richiesta di connessione da A a B accettata: • A invierà a B pacchetti con VCI = 5 in hdr, senza più includere indirizzo dst. • Ogni switch sostituisce “in vci” con “out vci” nei pacchetti

• N.B.: – meccanismo di assegnamento di “vci” garantisce univocità locale di id’s => Switches possono appartenere ad amministrazioni indipendenti

• Terminazione della connessione: – A invia un pacchetto di connection release a B – switches rimuovono C_Id dalle loro tabelle quando ricevono connection release packet.

Reti di Calcolatori (Fabio Panzieri)

235

Università di Bologna - Corso di Laurea in Informatica

– – – –

Source Routing

Indirizzo: lista di porte da src a dst. Switch legge elemento più a destra della lista. Ogni switch ruota la lista di una posizione, dopo aver letto la sua porta. Semplice, ma non scala: su rete vasta, impossibile per host costruire lista

0

Switch 1

1

0

1 3 0

3 2

3 0 1

0 0

1

Switch 3 3

2 Reti di Calcolatori (Fabio Panzieri)

1 2

3

0 1 3 Host A

3

2 Switch 2 1

Host B 236

118

Università di Bologna - Corso di Laurea in Informatica

Modelli di servizio a Livello Network • Quale modello di servizio offrire ? – Bandwidth garantita? – Controllo dei ritardi nella consegna di pacchetti (e variazioni)? – Consegna senza perdite di pacchetti? – Ordinamento dei pacchetti? – Segnalazione di congestione di rete?

• Astrazione a livello rete: Circuito virtuale o datagram?

Reti di Calcolatori (Fabio Panzieri)

237

Università di Bologna - Corso di Laurea in Informatica

Circuito virtuale • Switch mantengono stato della connessione

application transport network data link physical

5. Data flow begins 4. Call connected 1. Initiate call

Reti di Calcolatori (Fabio Panzieri)

6. Receive data 3. Accept call 2. incoming call

application transport network data link physical

238

119

Università di Bologna - Corso di Laurea in Informatica

Datagram • Switch non mantengono informazione di stato • Utilizzato in Internet (i.e., servizio “best-effort”)

application transport network data link physical

1. Send data

application transport 2. Receive data network data link physical

Reti di Calcolatori (Fabio Panzieri)

239

Università di Bologna - Corso di Laurea in Informatica

Circuito virtuale vs. Datagram •

Circuito virtuale – Impone un ritardo di RTT completo per stabilire connessione prima di poter inviare pacchetti di dati + Mentre connection request contiene indirizzo completo della destinazione, ogni pacchetto dati contiene solo C_Id + ridotto overhead di header per pacchetto

– Se uno switch o un link nella connessione si guastano, la connessione è interrotta e una nuova connessione deve essere stabilita. + Attivare una connessione fornisce la possibilità di riservare risorse di rete + per scopi di QoS: la rete fornisce garanzie relativamente alle prestazioni che può offrire + switch riservano risorse (p.e. memoria, bandwidth nei link in uscita) per soddisfare garanzie

Reti di Calcolatori (Fabio Panzieri)

240

120

Università di Bologna - Corso di Laurea in Informatica

Circuito virtuale vs. Datagram •

Datagram + Non richiede ritardo di RTT per stabilire connessione + host può inviare dati senza ritardi, se disponibili – Host src non ha modo di sapere • se la rete è in grado di consegnare i pacchetti • se host dst è attivo o no + Pacchetti trattati indipendentemente uno dall’altro + in caso di guasto di uno switch o di un link è possibile instradare pacchetti attraverso rotte alternative - Pacchetti trattati indipendentemente uno dall’altro - Ordinamento non garantito – Overhead di protocollo per-pacchetto più alto che in connection-oriented routing – ogni pacchetto contiene indirizzo completo di dst

Reti di Calcolatori (Fabio Panzieri)

241

Università di Bologna - Corso di Laurea in Informatica

Asynchronous Transfer Mode (ATM) • Tecnologia packet-switching connection-oriented • 1980/90 standard per architettura ad alta velocità Broadband ISDN (da 155Mbps a 622 Mbps e superiore) • Obbiettivo: trasporto integrato end-to-end di voce, video, dati – Soddisfare requisiti temporali di traffico voce e video (a differenza di modello Internet best-effort) => diverse classi di servizio con diverse garanzie di QoS

– Utilizza packet-switching su circuiti virtuali • Protocollo di “signalling”: Q.2931 – “route discovery” – allocazione di risorse negli switch ATM per garantire QoS • Pacchetto di lunghezza fissa: “cell” – dimensione cell: 5 B hdr + 48 B payload = 53B

Reti di Calcolatori (Fabio Panzieri)

242

121

Università di Bologna - Corso di Laurea in Informatica

Dimensione cell ATM: proprietà •

Dimensione fissa: – agevola progettazione switch hardware • processing di cells di lunghezza fissa => predicibilità di tempo di elab. • predicibilità di tempo di elab. di cell abilita parallelismo fra switches

•

Dimensione ridotta: – riduce latenza in switch ottimizzando gestione code in switch Ex. 1a - rete con pkts a dimensione variabile: • • • •

Dimensione max. pacchetto: PktSize = 4 KB Bandwidth di canale: 100Mbps tempo di trasmissione pkt “X”: PktSize/bandwith=4096x8/100= 327.68µs pkt “X + 1” ad alta priorità in attesa per 327.68µs

Ex.1b - rete con cells a dimensione fissa: • Pacchetti frammentati in cells ATM di 53 B • Tempo di trasmissione cell “X”: 53 x 8 /100 = 4.24µs • cell “X+1” ad alta priorità in attesa per 4.24µs

Reti di Calcolatori (Fabio Panzieri)

243

Università di Bologna - Corso di Laurea in Informatica

Dimensione cell ATM: proprietà •

Dimensione ridotta: abilita comportamento “cut-through” – pacchetto inizia ad essere trasmesso su porta di output prima di essere ricevuto completamente. (Di nuovo: minimizzazione latenza in switch)

Ex. 2a – – => –

bandwith = 100Mbps, max. pktsize = 4KB 2 pacchetti di 4KB ricevuti contemporaneamente Canale di output “idle” per 327.68µs (fino a termine consegna) Al termine dei 327.68µs: 8 KB in coda di trasmissione

Ex.2b – Pacchetti frammentati in cells ATM – Cut-through: dopo 4.24µs può trasmettere prima cell => dopo 327.68µs ha trasmesso circa 77 cells con 48 B di payload ciascuna, i.e. circa 3.6KB totali di payload – Al termine dei 327.68µs: 4.4 KB, circa, in coda di trasmissione

Reti di Calcolatori (Fabio Panzieri)

244

122

Università di Bologna - Corso di Laurea in Informatica

Architettura ATM

•

Livello ATM Adaptation (AAL): residente in host (end system) – Frammentazione in cells/riassemblaggio in pkts di payload utente • pkts di utente possono essere di lunghezza variabile – analogo a servizio di trasporto in OSI RM o TCP

• •

Livello “ATM”: livello “network” (analogo a IP) – switching, routing di cells ATM, implementazione di classi di servizio Livello “physical”: codifica/temporizzazione bit, framing

Reti di Calcolatori (Fabio Panzieri)

245

Università di Bologna - Corso di Laurea in Informatica

Formato cella Livello Adaption •

Specificate differenti versioni dipendentemente da classe di servizio ATM – AAL1: per CBR (Constant Bit Rate), e.g. voce – AAL2: per VBR (Variable Bit Rate), e.g. MPEG video – AAL3/4: per dati (frammentazione complessa) – AAL5: per dati (frammentazione semplificata; usato per IP datagrams)

•

Strutturato in 2 livelli gerarchici => 2 formati di pacchetto

User data AAL convergenza AAL frammentazione/ riassemblaggio Reti di Calcolatori (Fabio Panzieri)

(Segmentation And Reassembly)

246

123

Università di Bologna - Corso di Laurea in Informatica

AAL 3/4: convergenza •

Common Part Convergence Sublayer Protocol Data Unit (CPCS-PDU) – Definisce modialità di incapsulamento di PDU di lunghezza variable, prima di frammentazione in cells

– –

– – –

8

8

16

CPI

Btag

BASize

< 64 KB

0– 24

8

8

16

Pad

0

Etag

Len

User data

CPI (8 bit): Common Part Indicator • Specifica versione di CPCS-PDU in uso (attualmente = 0 ) Btag/Etag (8 bit): • Beginning and Ending tag (uguali fra loro per ogni PDU) • proteggono dal caso in cui la perdita dell’ultima cell di una PDU e la prima di un’altra provochino che le due PDUs siano considerate una sola BASize (16 bit): • suggerisce dimensione buffer da allocare per riassemblare Pad (24 bit) + “0”: campo “padding” • fino a 3 Byte di Pad + Byte 0 assicurano allineamento a 32 bit del “trailer” (Etag + Len) Len (16 bit): dimensione della PDU

Reti di Calcolatori (Fabio Panzieri)

247

Università di Bologna - Corso di Laurea in Informatica

AAL 3/4: frammentazione/riassemblaggio •

AAL3/4: hdr + trailer trasportati in ogni cella ATM 40

•

ATM header

Header

2

4

10

Type

SEQ

MID

352 (44 bytes) Payload

6

10

Length

CRC-10

– Type (2 bits): per scopi di frammentazione/riassemblaggio • • • •

BOM: Beginning Of Message COM: Continuation Of Message EOM: End Of Message SDU: Single Data Unit

– SEQ: SEQuence number relativo a cella

• per individuare perdite di celle e errato ordine – protezione debole se perdite elevate

– MID: Message ID

• per multiplexing di PDUs su singola connessione

•

Trailer:

•

N.B.: CPCS PDU trasportata in frammenti di 44 bytes max.

– Length: numero di bytes di PDU in questa cell – CRC-10: 10 bit di CRC per individuare errori nella pdu di 48B (i.e., in cell)

Reti di Calcolatori (Fabio Panzieri)

248

124

Università di Bologna - Corso di Laurea in Informatica

AAL5 - Simple And Efficient AL (SEAL)

•

< 64 KB

0– 47 bytes

16

16

32

Data

Pad

Reserved

Len

CRC-32

SEAL: livello adaptation “a basso costo” (prestazionale) per trasmettere pacchetti IP – Consiste di campo dati (da livello superiore) e trailer di 8 bytes – Pad: campo “padding” • garantisce che “trailer” sia sempre collocato alla fine di una cell ATM

– trailer: • Reserved (16 bits): campo riservato per uso futuro (attualmente = 0) • Length (16 bits): n. di bytes della PDU (solo dati) • CRC-32 (32 bits): applicato a PDU intera , individua celle mancanti o non in ordine – Frammentazione: sostituisce campo Type di AAL3/4 con un bit in ATM header • bit = 1: identifica “end of PDU”; cella successiva : prima di nuova PDU; successive considerate di tipo Continuation of Message (COM), fino a “ultima” con ATM hdr bit = 1 Reti di Calcolatori (Fabio Panzieri)

249

Università di Bologna - Corso di Laurea in Informatica

Incapsulamento e segmentazione per AAL5

User data

48 bytes

Padding CS-PDU trailer

48 bytes

48 bytes

… Header ATM Reti di Calcolatori (Fabio Panzieri)

Payload di cella 250

125

Università di Bologna - Corso di Laurea in Informatica

Livello ATM • diverse “classi di servizio” Architetura di rete

Modello di servizio

Internet

best effort

ATM

CBR

Garanzie ? data rate

Loss Order

Timing

rilevamento congestione

non garantito costante

no

no

no

no

si

si

si

variabile entro limiti minimo garantito non garantito

si

si

si

no

si

no

congestione prevenuta congestione prevenuta si

no

si

no

no

constant bit rate

ATM

VBR variable bit rate

ATM

ABR available bit rate

ATM

UBR unspecified bit rate

Reti di Calcolatori (Fabio Panzieri)

251

Università di Bologna - Corso di Laurea in Informatica

Livello ATM: circuiti virtuali •

Permanent VCs (PVCs) – Connessioni di lunga durata • Percorso “permanente” tra coppie di routers IP

•

Switched VCs (SVC)

•

Trasporto di “cells” su VC da src a dst

– Stabiliti dinamicamente per sessione – call setup/teardown iniziare/terminare

per

ogni

chiamata

prima

che

trasferimento

possa

• seleziona classe di servizio

– ogni cell contiene VC id (non dst ID) – ogni switch sul cammino src-dst mantiene “stato” per ogni connessione che lo attraversa – link, switch, risorse (bandwidth, buffers) possono essere allocate a VC per fornire garanzie prestazionali

Reti di Calcolatori (Fabio Panzieri)

252

126

Università di Bologna - Corso di Laurea in Informatica

ATM VCs • Vantaggi – Garanzie prestazionali di QoS per connessioni mappate su VC (bandwidth, delay, delay jitter) • Svantaggi – Supporto inefficiente di traffico datagram – Switched VCs introducono latenza di call setup + overhead di processing per connessioni brevi

Reti di Calcolatori (Fabio Panzieri)

253

Università di Bologna - Corso di Laurea in Informatica

Formato cella livello ATM • User-Network Interface (UNI); – formato host-to-switch

• GFC: Generic Flow Control (t.b.d.) • VPI: Virtual Path Identifier • VCI: Virtual Circuit Identifier – VPI + VCI: abilitano gerarchia di connessioni virtuali • Virtual Path può contenere fino a 216 Virtual Circuits

• Type: management, controllo di congestione • CLP: Cell Loss Priority

– CLP = 1 => cell a bassa priorità • può essere scartata in caso di congestione • HEC: Header Error Check (CRC-8) 4

8

16

3

1

GFC VPI VCI Type • Network-Network Interface (NNI)CLP

8

384 (48 bytes)

HEC (CRC-8)

Payload

– Formato switch-to-switch

• GFC diviene parte del campo VPI

Reti di Calcolatori (Fabio Panzieri)

254

127

Università di Bologna - Corso di Laurea in Informatica

Livello Network: Internetworking • Problemi – Eterogeneità • quale servizio di comunicazione host-to-host fornire in contesto tecnologico di reti eterogenee ? – i.e., ≠ schemi di indirizzamento, ≠ velocità di trasmissione, ≠ protocolli di accesso, ≠ modelli di servizio

– Scalabilità • Internet raddoppiata in dimensione ogni anno negli ultimi 20 anni – come costruire percorsi (rotte) host-to-host efficienti e “loop free” in una rete con numero arbitrario di nodi, che varia dinamicamente ? – come costruire identificatori unici (i.e., indirizzi) della locazione geografica di questi nodi ?

• Le soluzioni IPV4 e IPV6

Reti di Calcolatori (Fabio Panzieri)

255

Università di Bologna - Corso di Laurea in Informatica

Esempio di internetwork Network 1 (Ethernet) H7

Concatenazione di reti

H2

H1 Network 2 (Ethernet)

H3

R3

H8

Network 4 (point-to-point link)

R1 R2

H4 Network 3 (FDDI)

Internetworking mediante IP

H5

H6

H1

H8

TCP

R1

ETH

R2

IP

IP ETH

Reti di Calcolatori (Fabio Panzieri)

R3

IP FDDI

FDDI

IP PPP

PPP

TCP IP

ETH

ETH

256

128

Università di Bologna - Corso di Laurea in Informatica

Protocollo IP Modello di servizio

Formato datagram IP

– Comunicazioni “connectionless”

0

• consegna “best-effort” – pkts possono essere persi – consegnati non in ordine – duplicati – ritardati in switch

4 Version

8 HLen

16

31 Length

Ident TTL

19

TOS Flags Protocol

Offset Checksum

SourceAddr DestinationAddr

– Schema di indirizzamento globale

Options (variable)

Pad (variable)

Data

Formato datagram IP • Version: versione IP (IPv4, IPv6) • Hlen: lunghezza hdr in words di 32 bit – no Options => Hlen = 20 bytes • TOS: type of service – trattamento pkt, p.e. “low delay”; usato per DiffServ • Length: lunghezza d/gram, incluso hdr, in bytes (i.e., 65535 B max)

•

Ident (pkt id), Flags, Offset

• • • • • •

TTL: time to live (default = 64) Protocol: demux key (TCP, UDP) Checksum: CRC descritto Src/dst fields: IP addr’s globali Options: estendono IP hdr Pad: padding a completare 32bit

–

usati in frammentazione

Reti di Calcolatori (Fabio Panzieri)

257

Università di Bologna - Corso di Laurea in Informatica

Frammentazione e re-assembly • Ogni rete in internetwork può usare propria MTU – MTU: max. dim. di IP datagram trasportabile in frame data link – interconnessione di reti con diverse MTU richiede frammentazione e riassemblaggio

• Strategia di frammentazione in IP – Frammentare solo se necessario (i.e. MTU < datagram) – Evitare frammentazione a src host – Assumere possibilità di ri-frammentazione – Frammenti trasmessi come datagram, indipendenti uno dall’altro – Riassemblaggio a dst – Non effettuare recovery di frammenti persi Reti di Calcolatori (Fabio Panzieri)

258

129

Università di Bologna - Corso di Laurea in Informatica

Esempio

Start of header Ident = x

0

Offset = 0

Rest of header

H1

R1

ETH IP (1400)

•

R2

FDDI IP (1400)

R3

PPP IP (512)

ETH IP (512)

PPP IP (512)

ETH IP (512)

PPP IP (376)

MTUs

1400 data bytes

H8

Start of header Ident = x

1

Offset = 0

Rest of header

ETH IP (376)

512 data bytes

– Ethernet = 1500 B – FDDI = 4500 B – Point-to-Point = 532 B

Start of header Ident = x

1

Offset = 512

Rest of header 512 data bytes

• H1 invia msg di 1400 B a H8 • IP in H1 genera datagram di 1420 B

Start of header Ident = x

0 Offset = 1024 Rest of header

– R1: tramette senza frammentare; – R2: frammenta e trasmette; – R3 non riassembla e trasmette

376 data bytes

Reti di Calcolatori (Fabio Panzieri)

259

Università di Bologna - Corso di Laurea in Informatica

Indirizzi IP • Proprietà – Unici globalmente – Gerarchici • Strutturati in • Hosts connessi a stessa rete condividono parte network p.e., H1, H2 e R1 in Network 1, … • Router che interconnette 2 reti ha 2 indirizzi IP, uno per interfaccia di rete (p.e. R1, R2 e R3 in fig.) N.B. indirizzi IP associati a interfacce di rete

H1

Reti di Calcolatori (Fabio Panzieri)

R1

R2

R3

H8

260

130

Università di Bologna - Corso di Laurea in Informatica

Indirizzi IP •

Strutturati in “classi” A, B, C, D e E (non usata; riservata per usi futuri) – 232bit = 4.294.967.296 indirizzi possibili cosi’ allocati: –

Classe A: 27 - 2 = 126 reti (0 e 127 riservati); 224 - 2 = 16.777.214 indirizzi di hosts ognuna (2 indirizzi riservati)

–

Classe B: 214 = 16384 reti, 216 - 2 = 65534 hosts ognuna

–

Classe C: 221 = 2.097.152 reti, 28 = 256 hosts di cui 254 utili (~12.5%)

=> 126 x 16.777.214 = 2.113.928.964 (~50% di spazio indirizzi) => 16384 x 65534 = 1.073.709.056 (~25%) •

(255: broadcast, 0: non valido)

Rappresentazione decimale: ogni intero rappresenta il decimale contenuto nel byte corrsipondente

Classe A

0 network

B

10

network

C

110

network

D

1110

1.0.0.0 -> 127.255.255.255

host

128.0.0.0 -> 191.255.255.255

host host

192.0.0.0 -> 223.255.255.255

multicast address

224.0.0.0 -> 239.255.255.255

32 bits Reti di Calcolatori (Fabio Panzieri)

261

Università di Bologna - Corso di Laurea in Informatica

Datagram Forwarding

• Strategia – – – – – –

Ogni datagram contiene indirizzo dst Src, se direttamente connesso a rete destinazione, trasmette a dst Src, se non direttamente connesso trasmette a router Ogni network ha un router di default, noto a hosts Ogni router mantiene una tabella di forwarding Tabella di forwarding mappa network number in next hop

Esempio H1

Ethernet 2

R1

tabella di forwarding in R2 R2

FDDI 3

R3

P-to-P 4

H8

Ethernet 1

Network Number 1 2 3 4

Next hop R3 R1 I/F 1 I/F 2

N.B.: tabella contiene solo 4 entry per raggiungere tutti gli hosts su tutte e 4 le reti => scalabilità Reti di Calcolatori (Fabio Panzieri)

262

131

Università di Bologna - Corso di Laurea in Informatica

Traduzione indirizzi • Problema – da schema precedente • datagrams IP trasportati su rete destinazione

– Come raggiungere host dst? • Datagram IP contiene indirizzo IP • Interfaccia h/w di dst (host o router) indirizzata con schema indirizzamento di rete dst specifica => indirizzo IP deve essere “tradotto” in indirizzo di livello data link della rete (p.e., 48 bit Ethernet addr.) • Solo successivamente, datagram IP incapsulato in frame di livello data link e trasmesso a dst

• Soluzioni – Codificare indirizzi fisici in parte host di indirizzi IP p.e., ind. fisico di host: 00010001 00101001 -> IP: 128.96.33.81 • richiede indirizzi fisici di rete < 16 bit (classe C: host addr = 8 bit) • non funziona per indirizzi di 48 bit (Ethernet)

– Address Resolution Protocol: uso di tabella dinamica

Reti di Calcolatori (Fabio Panzieri)

263

Università di Bologna - Corso di Laurea in Informatica

ARP (Address Resolution Protocol) • • •

Consente ad ogni host, o router, di costruire tabella di mapping di indirizzi IP e corrispondenti indirizzi fisici Sfrutta broadcasting (in ethernets e rings) Invio di datagram IP a dst (host o router) su medesima rete il cui indirizzo data link è ignoto 1. Host src consulta suo “ARP cache” (i.e., tabella) 2. se indirizzo fisico di host dst non in ARP cache allora broadcast richiesta ARP (i.e. “chi possiede questo IP?”) 3. Ogni host in network intercetta richiesta ARP 4. Confronta proprio IP con quello in richiesta ARP 5. Se uguali, host risponde con il suo indirizzo fisico 6. Host src aggiorna propria cache 7. Host dst aggiorna propria cache

Reti di Calcolatori (Fabio Panzieri)

264

132

Università di Bologna - Corso di Laurea in Informatica

ARP: Note • Entries in tabelle sono periodicamente, se non usate

scartate

e

rigenerate

– p.e. guasto/sostituzione interfaccia di rete (i.e. nuovo indirizzo) – TTL = 15’ (circa)

• Host target aggiorna tabella con indirizzo src, quando riceve datagram • Host non-target intercetta richiesta ARP se src presente tabella allora “refresh” entry (i.e. re-setta TTL ) altrimenti ignora richiesta

Reti di Calcolatori (Fabio Panzieri)

265

Università di Bologna - Corso di Laurea in Informatica

Formato del pacchetto ARP • • • • • •

Hardware type: Tipo di 0 8 16 rete (1 = ethernet) Protocol type: protocollo Hardware type = 1 Protocol Type = 0x0800 di livello superiore (p.e. IP) HLen = 48 PLen = 32 Operation Hlen: lunghezza indirizzo SourceHardwareAddr (bytes 0-3) data link Plen: lunghezza indirizzo SourceHardwareAddr (bytes 4-5) SourceProtocolAddr (bytes 0-1) livello superiore Operation: ARP request, SourceProtocolAddr (bytes 2-3) TargetHardwareAddr (bytes 0-1) o ARP response Indirizzi data link e TargetHardwareAddr (bytes 2-5) protocollo superiore di src e dst TargetProtocolAddr (bytes 0-3)

31

Pacchetto ARP per mappare indirizzi IP in indirizzi Ethernet Reti di Calcolatori (Fabio Panzieri)

266

133

Università di Bologna - Corso di Laurea in Informatica

Internetworking via IP • IP soddisfa requisiti di: • Eterogeneità – Modello “best-effort” (i.e. datagram) • assunzioni minime su infrastrutture di rete di supporto a IP

– Formato del pacchetto comune a qualunque supporto di rete • Meccanismo di frammentazione/re-assemblaggio consente di lavorare con differenti MTUs

– Spazio di indirizzi “globale” • ARP supporta spazio indirizzi globale su reti con schemi di indirizzamento diversi

• Scalabilità – Struttura gerarchica degli indirizzi () riduce quantità di informazione necessaria a trasmettere datagrams

• Come assegnare indirizzi IP a hosts? Reti di Calcolatori (Fabio Panzieri)

267

Università di Bologna - Corso di Laurea in Informatica

Configurazione di hosts con indirizzi IP • Indirizzi IP devono – essere unici in internetwork (per scopi di identificazione univoca) – riflettere struttura dell’internetwork (per scopi di routing) – essere riutilizzabili – per rilocare un host da una rete ad un altra – sostituire host guasto

• Soluzioni manuali: non proponibili (soggette a errore) • Soluzione automatica: Dynamic Host Configuration Protocol (DHCP) – Basato su DHCP server che:

• mantiene “serbatoio” di indirizzi IP per particolare dominio amministrativo da assegnare a hosts richiedenti • evita all’amministratore del dominio – l’assegnazione di indirizzi IP a hosts – l’assegnazione dell’indirizzo del DHCP server a hosts

– Almeno un DHCP server per dominio amministrativo

Reti di Calcolatori (Fabio Panzieri)

268

134

Università di Bologna - Corso di Laurea in Informatica

DHCP •

Host cliente – Invia msg DHCPDISCOVER a ind. 255.255.255.255 • 255.255.255.255: indirizzo IP di broadcast • routers e nodi ≠ DHCP server ignorano messaggio • msg include h/w net. addr. (e.g. Ethernet MAC addr.) di host cliente

•

DHCP server – risponde con • indirizzo IP per host cliente • indirizzo di router di default per host cliente (se disponibile)

•

N.B.: Dominio amministrativo può consistere di internetwork – DHCP server in ogni rete? •

potenzialmente gran n. di DHCP servers – complessità: •

configurazione e allineamento (coerenza) dei DHCP servers

– Uso di relay agents

Reti di Calcolatori (Fabio Panzieri)

269

Università di Bologna - Corso di Laurea in Informatica

DHCP: Relay agents •

Almeno un relay agent per rete –

configurato con (i.e. conosce) indirizzo IP di DHCP server

• Host: invia in broadcast DHCPDISCOVER msg • Realy agent: – cattura DHCPDISCOVER msg – invia in unicast DHCPDISCOVER a DHCP server – attende risposta – invia risposta a host broadcast msg

unicast msg

DHCP relay

a DHCP server

Rete

DHCP Server

Host Reti di Calcolatori (Fabio Panzieri)

270

135

Università di Bologna - Corso di Laurea in Informatica

DHCP: riutilizzabilità di indirizzi IP •

Indirizzi IP assegnati dinamicamente (su richiesta) da DHCP server => conflitto di requisiti (A vs. B) A. devono essere restituiti da hosts altrimenti server esaurisce serbatoio •

DHCP non può affidarsi a host per la restituzione – host può guastarsi, essere disconnesso, imbrogliare, …

B. host deve poter usare indirizzo IP per quanto necessario

•

Soluzione – – –

•

DHCP “affitta” ogni indirizzo IP per lasso di tempo (i.e. TTL) Se TTL termina, DHCP server riutilizza indirizzo Host può rinnovare periodicamente “affitto” di indirizzo, se necessario

N.B.: Complessità indotta da DHCP in gestione di rete –

Associazione dinamica indirizzo <mac address; IP> •

complesso localizzare host guasto sulla base del suo indirizzo IP

Reti di Calcolatori (Fabio Panzieri)

271

Università di Bologna - Corso di Laurea in Informatica

Internet Control Message Protocol (ICMP) •

IP configurato con protocollo “peer” ICMP per 1. segnalazione di errori a host src •

“Destination unreachable” – p.e., link guasto, host guasto

•

“TTL exceeded” – TTL = 0 (previene loop permanente di datagram) “Checksum failed” “Reassembly failed” – p.e., frammento mancante

• •

2. messaggi di controllo router-host •

ICMP-redirect

Reti di Calcolatori (Fabio Panzieri)

272

136

Università di Bologna - Corso di Laurea in Informatica

ICMP-REDIRECT • Router notifica host src rotta migliore per dst

2

via R2

3

1 4

host src

Msg 2 a dst

Net B

host dst

R2

Net A Msg 1 a dst via R1

ICMP-REDIRECT: msgs a dst via R2

R1 (default)

Msg 1 a dst via R2

Net C

Reti di Calcolatori (Fabio Panzieri)

273

Università di Bologna - Corso di Laurea in Informatica

Routing • •

Forwarding vs. Routing = instradamento vs. costruzione di rotte Tabella di routing –

mapping fra rete destinazione e indirizzo IP di “next hop” •

E.g.:

Network num Next hop 10 130.136.2.253 •

Tabella di forwarding –

mapping fra rete dst., porta di uscita (i.e., come raggiungere “next hop”), e indirizzo fisico di “next hop” (p.e., MAC address fornito da ARP) •

E.g.

Network num Interface 10 0 •

MAC Address 7:0:3b:e5:b:2:3

1 o 2 tabelle? • •

scelta implementativa meglio se separate: – modifiche di topologia richiedono cambiamento di tabella di routing, solamente – sostituzione di MAC i/f richiede modifica di forwarding table, solamente

Reti di Calcolatori (Fabio Panzieri)

274

137

Università di Bologna - Corso di Laurea in Informatica

Routing in Internet • Protocolli (IGPs))

intra-dominio

(Interior

Gateway

Protocols

– Protocolli di routing per uso interno a dominio • dominio: internetwork i cui routers sono sotto il medesimo controllo ammistrativo (p.e., Università di Bologna) • Non scalano a livello globale • Costituiscono “building block” per routing su scala globale • Includono – Routing Information Protocol (RIP) – Open Shortest Path First (OSPF) Protocol

– Protocolli extra-dominio (Exterior Gateway Protocols (EGPs)) • Usati per routing attraverso domini amministrativi diversi • Boarder Gateway Protocol 4 (BGP-4) Reti di Calcolatori (Fabio Panzieri)

275

Università di Bologna - Corso di Laurea in Informatica

Routing •

Costruzione delle routing table – applicazione della teoria dei grafi • rete rappresentata come un grafo – nodi = routers, archi = links

– ogni arco ha un “costo” • costo: ritardo, livello di congestione, €, … • permette di valutare opportunità di usare il link corrispondente

– problema del routing

• trovare il cammino di costo minimo tra due nodi qualunque

A

3 B

E

4 C Reti di Calcolatori (Fabio Panzieri)

6

1 1

2

F

1 9

D 276

138

Università di Bologna - Corso di Laurea in Informatica

Routing tables • Costruite mediante algoritmi distribuiti

– routers scambiano informazione e costruiscono propria routing table • periodicamente (periodic udate), o • se si verifica qualche cambiamento – p.e. aggiunta di link, crash di link (triggered update)

• Due tecniche principali per la costruzione delle routing tables: – in entrambe:

• ogni router stabilisce costo della comunicazione con i routers cui è direttamente connesso, e costruisce routing table iniziale

– Distance Vector Routing

• Ogni router invia routing table corrente ai routers cui è direttamente connesso, solamente • Ogni router aggiorna la propria routing table sulla base di quella ricevuta, se scopre in questa percorsi meno costosi verso le destinazioni note

– Link State Routing

• Ogni router invia routing table a tutti gli altri routers in rete • Ogni router aggiorna la propria routing table sulla base di quanto ricevuto

Reti di Calcolatori (Fabio Panzieri)

277

Università di Bologna - Corso di Laurea in Informatica

Distance Vector (RIP) • •

Ogni nodo mantiene tabella di routing consistente di insieme di triple: Ogni nodo invia aggiornamenti a (e riceve aggiornamenti da) i nodi vicini direttamente connessi – periodicamente (ordine di qualche secondo) – quando la sua tabella cambia (triggered update)

• •

Ogni aggiornamento è una coppia: Aggiorna la propria tabella se scopre una rotta migliore

•

Ad ogni riga in tabella (rotta) è assegnato un max. time to live (TTL) if nodo vicino non invia propria tabella (aggiornamento) entro TTL, then reset valori di rotta /* i.e. sospetta che il canale di comunicazione al nodo vicino sia guasto */

Reti di Calcolatori (Fabio Panzieri)

278

139

Università di Bologna - Corso di Laurea in Informatica

Distance Vector: esempio • Vector: direzione, i.e. primo passo che un pacchetto deve compiere • Ip.: – ogni nodo (router) conosce il costo (distance ) dei links connessi direttamente – distance vector iniziale: costo unitario di ogni link

• Routing table iniziale al nodo A (INF = costo infinito; i.e., ignoto) Destination

Cost

Next Hop

B

1

B

C

1

C

D

INF

-

E

1

E

F

1

F

G

INF

-

1 1

B

1

A

1

C D

E

F

G

Reti di Calcolatori (Fabio Panzieri)

279

Università di Bologna - Corso di Laurea in Informatica

Distance vector: esempio

•

Ogni nodo invia il proprio distance vector ai vicini (i.e., nodi direttamente connessi) Se un nodo scopre che il vettore ricevuto ha un cammino di costo migliore (i.e. più basso), di quello conosciuto, sostituisce quello conosciuto con il nuovo valore.

•

Ogni nodo costruisce “distance vector” per raggiungere tutti gli altri nodi

•

B

1 A

1 F

C

1 1

D

E

1

1

G

Destination

Cost

Next Hop

B

1

B

C

1

C

D

2

C

E

1

E

F

1

F

G

2

F

Routing table al nodo A al termine del calcolo del distance vector Reti di Calcolatori (Fabio Panzieri)

280

140

Università di Bologna - Corso di Laurea in Informatica

Distance Vector: trattamento dei guasti •

Mancanza di aggiornamento da un nodo direttamente connesso

•

Esempio 1

•

In generale la situazione tende a stabilizzarsi, però:

=> considerare guasto il link con quel nodo – – – – – –

F sospetta guasto del link con G F setta la sua distanza con G a infinito e invia aggiornamento ad A A setta la sua distanza con G a infinito poiché usa F per raggiungere G A riceve aggiornamento periodico da C con costo 2 per G A setta la sua distanza con G a 3 invia aggiornamento a F F decide che può raggiungere G a costo 4 via A, ristabilendo connettività con G

– rischio di routing loops

B C

A

D

E F

G

Reti di Calcolatori (Fabio Panzieri)

281

Università di Bologna - Corso di Laurea in Informatica

Distance Vector: routing loops • Esempio 2: A rileva guasto nel link da A a E – A annuncia costo infinito con E a B, C, F

N.B.: msg viaggia via IP; può subire ritardi in rete

– B e C annunciano costo = 2 con E

• msg consegnato prima di msg di A

– B riceve msg’s da C e A, decide che può raggiungere E a costo 3 via C (B->C + C->E), e lo comunica ad A – A decide che può raggiungere E a costo 4 (A->B + B->E annunciato), e lo comunica a C – C decide che può raggiungere E a costo 5 (C->A + A->E annunciato) … – Processo termina solo quando costo = “infinito” B C

A

D

E F Reti di Calcolatori (Fabio Panzieri)

G 282

141

Università di Bologna - Corso di Laurea in Informatica

Distance Vector •

Euristiche per spezzare i routing loops – “infinito = n”, n quantità sufficientemente piccola • dopo n aggiornamenti viene sollevata eccezione – p.e., forward di email fra gli stessi due indirizzi: dopo 16 iterazioni sospende e invia messaggio di errore

– Split horizon: • Non inviare informazione ricevuta da un vicino indietro a quel vicino P.E.: – se tabella di B contiene rotta <E,2,A>, B sa di averla ottenuta da A stesso; – quando invia aggiornamenti ad A non include rotta <E,2> nell’aggiornamento N.B.: spezza solo routing loops fra due nodi

•

Routing loops risolti da Link State Routing

Reti di Calcolatori (Fabio Panzieri)

283

Università di Bologna - Corso di Laurea in Informatica

Routing in Internet: Routing Information Protocol (RIP) • Basato su algoritmo di “distance vector” • Ogni router – annuncia costo per raggiungere “rete dst ”, anzichè “router dst” – invia annunci ogni 30” • oppure quando “triggered” da annuncio da altro router che modifica la sua routing table

– assume “costo” di link unitario (i.e., “costo”: n. di hops) – supporta “famiglie” di indizzi (i.e., non solo IP) – spezza routing loops assumendo “infinito = 16”

• RIP utilizzabile per routing in reti di dimensioni contenute – Lunghezza path: 15 hops max. • i.e. ok in singolo dominio amministrativo

Reti di Calcolatori (Fabio Panzieri)

284

142

Università di Bologna - Corso di Laurea in Informatica

Link State Routing • Ip: ogni nodo è in grado di valutare costo dei link con cui è direttamente connesso • Strategia: – fornire ad ogni nodo sufficiente informazione di routing affinchè questo possa determinare la migliore rotta per ogni destinazione • informazione di stato relativa ai link a cui un nodo è direttamente connesso è trasmessa da questo ai suoi vicini, e propagata a tutti • ogni nodo riceve informazione relativa a tutta la rete da tutti i nodi

• Algoritmo di LSR basato su due meccanismi: – Reliable Flooding • dissemina informazione di stato sui link attraverso la rete

– Shortest path first • costruisce tabelle di routing (algoritmo di Dijkstra) calcolando rotte sulla base dell’informazione di stato ottenuta via reliable flooding Reti di Calcolatori (Fabio Panzieri)

285

Università di Bologna - Corso di Laurea in Informatica

Reliable Flooding • • •

Ogni nodo invia informazione di stato relativa ai link a lui direttamente connessi su ognuno di questi link mediante Link State Packet (LSP) Nodo che riceve LSP ne effettua il forwarding sui link a lui direttamente connessi (eccetto quello da cui l’LSP proviene) LSP contiene: – – – – –

id del nodo che ha creato l’LSP stesso Per scopi di calcolo lista di nodi direttamente connessi delle rotte costo di ogni link direttamente connesso numero di sequenza (seq.no.) Per consetire “flooding” affidabile time-to-live (TTL) per l’LSP

Reti di Calcolatori (Fabio Panzieri)

286

143

Università di Bologna - Corso di Laurea in Informatica

Reliable Flooding • Quando nodo X riceve LSP da nodo Y, controlla se possiede già un LSP da Y – si:

• if seq. no. del nuovo LSP > seq. no. di LSP attualmente mantenuto then {nuovo LSP sostituisce precedente LSP; “forward” nuovo LSP su tutti i link di uscita,tranne quello di provenienza} else scarta nuovo LSP

– no:

• mantiene copia di LSP ricevuto, • “forward” LSP su tutti i link di uscita, tranne quello di provenienza => ogni LSP raggiunge tutti i nodi (a meno di guasti di comunicazione)

• Ogni nodo genera l’LSP periodicamente

=> ogni volta, il seq. no. è incrementato di 1 – necessario che seq.no. non ciclino

=> uso di un campo ampio (64 bits) per rappresentarli

Reti di Calcolatori (Fabio Panzieri)

287

Università di Bologna - Corso di Laurea in Informatica

Reliable Flooding •

Garanzia che LSPs obsoleti siano scartati – ogni LSP ha associato un TTL (alcuni minuti) – TTL decrementato da ogni nodo attraverso cui l’LSP transita; – TTL di ogni LSP mantenuto dal nodo è decrementato periodicamente da quel nodo; – ogni LSP con TTL = 0 scartato (e “re-flooded” con TTL = 0 in modo che possa essere scartato da tutti i nodi) – Nodo “guasto” (crashed) dopo recovery genera LSPs partendo da seq.no. = 0 • => • =>

durata del guasto sufficientemente lunga TTL degli LSPs del nodo re-inizializzato sono terminati e info. di stato rimossa durata guasto sufficientemente breve nodo re-inizializzato riceve (prima o poi) suo pre-crash LSP; in questo caso, può continuare da quel seq. no.

Reti di Calcolatori (Fabio Panzieri)

288

144

Università di Bologna - Corso di Laurea in Informatica

Calcolo della rotta (in teoria) • Shortest path algorithm (Dijkstra)

– calcola cammino fra nodo s, che esegue l’algoritmo, e il resto dei nodi nel grafo – N: insieme di nodi nel grafo; – l(i,j): costo dell’arco fra i nodi i e j • posto a infinito se non vi è alcun link diretto fra i e j.

– s: nodo che esegue l’algoritmo – M: insieme dei nodi per cui è stata calcolato un cammino con relativo costo – C(n): costo del cammino dal nodo s al nodo n

M = {s} /Inizializza M for each n in N - {s} / Inizializza tabella con costi dei C(n) = l(s,n) /nodi direttamente connessi while (N ≠ M) /Cerca nodo w di costo min. e mettilo in M M = M ∪ {w} such that C(w) is the minimum for all w in (N-M) for each n in (N-M) /Aggiorna tabella con costi via w C(n) = MIN (C(n), C(w)+l(w,n)) Reti di Calcolatori (Fabio Panzieri)

289

Università di Bologna - Corso di Laurea in Informatica

Shortest Path Algorithm (principio di funzionamento) 1. Inizializza M a contenere solo s (il nodo che esegue l’alg.) 2. Inizializza tabella dei costi (tutti i C(n)) verso gli altri nodi – i.e. inserisci costo conosciuto per i nodi direttamente connessi e infinito per gli altri

3. Seleziona nodo w ≠ s a costo più basso, e aggiungilo a M. 4. Calcola costo per raggiungere il resto dei nodi via w; 5. if uno di questi è più economico di quelli noti in tabella then aggiorna tabella; 6. Ripeti da passo 3 finché M = N. Reti di Calcolatori (Fabio Panzieri)

290

145

Università di Bologna - Corso di Laurea in Informatica

Costruzione di tabelle di routing: esempio • Implementazione dell’algoritmo di Dijkstra (algoritmo forward search): – Ogni nodo mantiene due liste: Tentative e Confirmed – Ogni nodo calcola la sua tabella di routing sulla base degli LSP ricevuti dagli altri nodi in Confirmed – Ogni lista contiene un insieme di triple: Costruzione di routing table di D

5 A

B

3

Confirmed

1.

(D,0,-)

2.

(D,0,-)

Tentative

2

Commenti D: unico membro in Confirmed. Esamina LSP di D LSP di D indica C(B) = 11, C(C) = 2 (da D); li aggiunge a Tentative

(B,11,B) (C,2,C)

C

10 11

Step

3.

(D,0,-)

(B,11,B)

(C,2,C)

D 4.

(D,0,-)

(B,5,C)

(C,2,C)

(A,12,C)

Muovi (C,2,C) in Confirmed [membro di costo minore in Tentative] Esamina LSP da C

LSP da C indica costo C ->B = 3, C -> A = 10. Aggiorna Tentative

Reti di Calcolatori (Fabio Panzieri)

291

Università di Bologna - Corso di Laurea in Informatica

Costruzione di tabelle di routing: esempio Step

Confirmed

Tentative

Commenti

5.

(D,0,-)

(A,12,C)

Muovi (B,5,C) in Confirmed [membro di costo più basso in Tentative]

(C,2,C)

Esamina LSP di B

(B,5,C) 6.

(D,0,-) (C,2,C)

(A,10,C)

LSP da B indica costo B -> A = 5. Aggiorna Tentative

(B,5,C) 7.

(D,0,-) (C,2,C)

Muovi (A,10,C) in Confirmed [membro di costo più basso in Tentative]

(B,5,C)

if Tentative = ø then termina

(A,10,C)

5 A

B

3 C

10 11

2

D Reti di Calcolatori (Fabio Panzieri)

292

146

Università di Bologna - Corso di Laurea in Informatica

Calcolo della rotta (in pratica) 1. Nodo S (esecutore) inizializza Confirmed con tripla relativa a se stesso •

assume costo = 0

2. esamina l’LSP del nodo in Confirmed (detto Next, nel seguito). 3. Per ogni Neighbour di Next, calcola il costo per raggiungere Neighbour come somma del costo da se a Next, e da Next a Neighbour 3.1. Se Neighbour non è attualmente né in Confirmed né in Tentative, aggiungi (Neighbour, Cost, NextHop) a Tentative, dove NextHop è la direzione per raggiungere Next. 3.2 Se Neighbour è attualmente in Tentative e costo è inferiore al costo corrente per Neighbour, allora sostituisci entry attuale con (Neighbour, Cost, NextHop)

4. Se Tentative è vuota, stop. Altrimenti, seleziona entry da Tentative con costo più basso, spostala in Confirmed, e ritorna al passo 2.

Reti di Calcolatori (Fabio Panzieri)

293

Università di Bologna - Corso di Laurea in Informatica

Link State Routing: proprietà • Pro’s

– Si stabilizza rapidamente – Introduce overhead di traffico ridotto – Risponde rapidamente a modifiche della topologia di rete

• Con’s

– Volume di informazione di stato mantenuta ad ogni router (un LSP per ogni switch nella rete) – non sufficientemente scalabile • i.e., utile in singolo dominio amministrativo (i.e., reti con n. contenuto di nodi)

• Distance Vector Routing (DSR) vs. Link State Routing (LSR)

– In DSR ogni router comunica con i routers direttamente connessi, solamente, ma invia loro la propria tabella di forwarding, completa. – In LSR ogni router comunica con tutti i router in rete, ma invia loro stato dei link a lui direttamente connessi, solamente

• Entrambi non sufficientemente scalabili

– Si richiedono tecniche di routing per internetwork globale

Reti di Calcolatori (Fabio Panzieri)

294

147

Università di Bologna - Corso di Laurea in Informatica

Costo dei link • Determinato sperimentalmente • Inizialmente, metriche di ARPANET (divenuta poi Internet) – Misura di numero di pacchetti mantenuti ad ogni switch – Non consideravano né latenza né bandwidth

• Successivamente sostituite da “new ARPANET metric”: – Marca ogni pacchetto ricevuto con il suo arrival time (AT) – Registra departure time (DT) – Quando riceve ACK da livello Data Link, calcola Delay = (DT - AT) + TransmissionTime + Latency (DT - AT): tempo in cui il pacchetto è rimasto in coda nello switch TransmissionTime e Latency: definite staticamente

– if timeout per mancanza di ACK, then risetta DT all’istante di ritrasmissione – Costo del link = ritardo medio su un periodo di tempo

Reti di Calcolatori (Fabio Panzieri)

295

Università di Bologna - Corso di Laurea in Informatica

Metriche di costo •

Problemi con metriche “New” – Carico di rete basso: • fattori statici (latency, transmission time) dominano il costo (OK)

– Carico di rete elevato: • link congestionati assumono costo molto elevato, e lo annunciano; • pacchetti transitano verso link scarichi, scaricando quelli congestionati, • e congestionando quelli scarichi, e così via.

•

Metriche di costo “revised”, in uso oggi: – Basate su riduzione del campo di variabilità delle metriche: – Sostituiscono misure di delay con link utilization, mediato con l’ultimo link utilization conosciuto (per evitare sbalzi di carico improvvisi) – Impongono limite su variabilità dei valori misurati fra un ciclo di misure ed il successivo => attenuando i cambiamenti nei costi, si riduce la probabilità che tutti i nodi abbandonino una rotta tutti insieme.

Reti di Calcolatori (Fabio Panzieri)

296

148

Università di Bologna - Corso di Laurea in Informatica

Livello Network in Internet sommario Transport layer: TCP, UDP IP protocol •addressing conventions •datagram format •packet handling conventions

Routing protocols •path selection •RIP, OSPF, BGP

Network layer

routing table

ICMP protocol •error reporting •router “signaling”

Link layer physical layer

Reti di Calcolatori (Fabio Panzieri)

297

Università di Bologna - Corso di Laurea in Informatica

Internet globale •

Indirizzamento gerarchico IP rende routing non sufficientemente scalabile – Routers mantengono indirizzi di tutte le reti connesse ad Internet, solamente, i.e. non mantengono indirizzi degli hosts (usano ARP)

•

Scalabilità insufficiente a causa della crescita di Internet in termini di n. di reti interconnesse che la compongono

•

Principali problemi di scalabilità nel routing 1. Ottimizzare uso di spazio indirizzi IP •

i.e., garantire che non si esaurisca

2. Minimizzare dimensioni tabelle di routing nei routers •

i.e., minimizzare numero di “network numbers” trasportati nei pacchetti IP e mantenuti nelle tabelle di routing dei routers

Reti di Calcolatori (Fabio Panzieri)

298

149

Università di Bologna - Corso di Laurea in Informatica

Struttura attuale di Internet •

Insieme di “Autonomous Systems” (ASs) – AS: rete, o interconnessione di reti, amministrata indipendentemente dagli altri ASs (e.g., università, compagnia, ISP, ASP) Large corporation “Consumer Peering point

Backbone service provider

“ Consumer ” ISP Large corporation

” ISP

Peering point

“Consumer ”ISP

Small corporation

•

Identificazione univoca di ciascuna rete con network number – non praticabile • saturazione memoria dei routers • esaurimento network numbers di IP

Reti di Calcolatori (Fabio Panzieri)

299

Università di Bologna - Corso di Laurea in Informatica

Scalabilità del routing: gestione dello spazio indirizzi IP • • •

Classe A: 27 = 256 reti, 224 hosts Classe B: 214 = 16384 reti, 216 = 65534 hosts Classe C: 221 reti, 28 - 2 = 254 hosts – Organizzazione con 2000 hosts riceve classe B, • lascia inutilizzati 63334 indirizzi • Efficienza = 2000/65534 = 0.03 = 3%

– Organizzazione con 2 hosts riceve classe C • lascia inutilizzati 252 indirizzi • Efficienza = 2/254 = 0.0078 = 0.78%

– Spazio indirizzi si esaurisce rapidamente

•

Soluzione: –

tecnica di subnetting

Reti di Calcolatori (Fabio Panzieri)

300

150

Università di Bologna - Corso di Laurea in Informatica

Subnetting: ottimizzare uso degli indirizzi IP • Idea di base: allocare gli indirizzi IP con stesso IP network number a molteplicità di “subnets” (reti fisiche) • IP standard: hosts su medesima rete fisica configurati con medesimo network number • IP con subnetting: hosts su medesima rete fisica configurati con medesima subnet mask – unica per tutti gli hosts nella medesima subnet – subnets distinte possono usare la stessa subnet mask

• Subnet mask: consente di introdurre subnet number • Subnet number – AND bit a bit di indirizzo IP e subnet mask – Hosts su medesima rete fisica: = subnet number

– Hosts su diverse reti fisiche: = network number ≠ subnet number

– Subnet numbers visibili solo all’interno di rete con medesimo network number (invisibili al resto di Internet)

Reti di Calcolatori (Fabio Panzieri)

301

Università di Bologna - Corso di Laurea in Informatica

Meccanismo di subnetting • Subnet mask – definisce partizione (variabile) del campo host number; • i.e., campo Host Number diviso in <subnet ID; host ID>

– in esempio: • 16 bit di ordine più alto – network number (classe B) • 8 successivi: – subnet ID; • 8 successivi: – host ID

⇒ Indirizzo diviso in 3 parti:

Reti di Calcolatori (Fabio Panzieri)

Network number

Host number

Indirizzo classe B 111111111111111111111111

00000000

Subnet mask (255.255.255.0) Network number Subnet ID

Host ID

Indirizzo “subnetted”

N.B.: Subnet mask introduce ulteriore livello gerarchico nell’ indirizzamento 302

151

Università di Bologna - Corso di Laurea in Informatica

IP addressing

Network ranges

Reti di Calcolatori (Fabio Panzieri)

303

Università di Bologna - Corso di Laurea in Informatica

Subnetting: esempio •

Sia assegnato al gestore di rete l’indirizzo di classe B = 152.15.x.x

• •

2 bytes non assegnati, i.e. disponibili per indirizzamento è responsabilità del gestore disporre di questi 2 bytes per indirizzare eventuali sottoreti, e dispositivi su queste (i.e. hosts) usiamo le lettere n(etwork), s(ubnet), e h(ost) per denotare la struttura dell’indirizzo

•

– quindi, per ora 152.15.x.x = nnnnnnnn.nnnnnnnn.xxxxxxxx.xxxxxxxx

•

Si vuole dividere rete 152.15.x.x in 4 sottoreti: – si possono usare i 2 bit di ordine piu alto dei due bytes disponibili, ottenendo: nnnnnnnn.nnnnnnnn.sshhhhhh.hhhhhhhh. – settando questi bit a 00, 01, 10, 11 lo spazio indirizzi disponibile può essere diviso in 4 gruppi

Reti di Calcolatori (Fabio Panzieri)

304

152

Università di Bologna - Corso di Laurea in Informatica

Subnetting 152.15.x.x • Subnet 1: – 152.15.0.1 to 152.15.63.254. – da x.x.00000000.00000001 a x.x.00111111.11111110

• Subnet 2: – 152.15.64.1 to 152.15.127.254 – da x.x.01000000.00000001 a x.x.01111111.11111110

• Subnet 3: – 152.15.128.1 to 152.15.191.254 – da x.x.10000000.00000001 a x.x.10111111.11111110

• Subnet 4: – 152.15.192.1 to 152.15.255.254 – da x.x.11000000.00000001 a x.x.11111111.11111110

Reti di Calcolatori (Fabio Panzieri)

305

Università di Bologna - Corso di Laurea in Informatica

Subnet mask – concetto di base • Subnet mask: – bit pattern usato per identificare parti comuni a gruppo di indirizzi IP – consente di identificare hosts su medesima sottorete – simile a indirizzo IP – creata confrontando i bit di due indirizzi IP, a partire da sinistra – se i bit nella medesima posizione (1º, 2º, ...) sono uguali, il corrispondente bit nella mask è uguale 1 – dalla posizione del primo bit che differisce in poi, tutti i bit della mashera sono uguali a 0

Reti di Calcolatori (Fabio Panzieri)

306

153

Università di Bologna - Corso di Laurea in Informatica

Subnet mask – concetto di base •

P.e.: dati i due indirizzi di host: 152.15.12.9 = 1011000.00001111.00001100.00001001 152.15.46.48 = 1011000.00001111.00101110.00110000 possiamo creare una maschera che isola le componenti da componente individuando sequenza di bit nella medesima posizione uguali fra loro

1011000.00001111.00001100.00001001 1011000.00001111.00101110.00110000 1111111.11111111.11000000.00000000 – ovvero: 255.255.192.0

•

Network mask: bit selezionati per identificare sottoreti p.e.: bit 11 nel 3º byte 11000000

Reti di Calcolatori (Fabio Panzieri)

307

Università di Bologna - Corso di Laurea in Informatica

Subnet mask – uso • • •

Network manager vuole consentire accesso a file server solo a richieste provenienti dalla rete della propria organizzazione, cui è stato assegnato indirizzo di classe C: 220.121.10.X. la mask è: 255.255.255.0 poichè relativa a indirizzi di classe C il firewall può essere programmato a confrontare l’indirizzo sorgente di tutte le richieste con il proprio (p.e. 220.121.10.1), usando la mask – i.e., estrae bit significativi dal proprio indirizzo e dal sorgente mediante la mask e li confronta

•

P.e.: e viene ricevuta la richiesta da indirizzo confronta: 11011100.01111001.00001100.00000010 11011100.01111001.00001010.00000001 11111111.11111111.11111111.00000000 yyyyyyyy.yyyyyyyy.yyyyynxx.xxxxxxxx

Reti di Calcolatori (Fabio Panzieri)

220.121.12.2, il firewall = = = =

220.121.12.2 220.121.10.1 255.255.255.0 respinta!

308

154

Università di Bologna - Corso di Laurea in Informatica

Subnet mask – uso •

Network manager vuole consentire accesso a file server solo a richieste provenienti dal dipartimento che possiede il firewall.

•

La sua organizzazione dispone dell’indirizzo di classe C 220.121.10.X e usa i primi due bit di byte X per definire 4 sottoreti.

•

Mask = 255.255.255.192. – –

primi 3 byte: mask di classe C 192 (11000000) deriva da uso dei primi 2 bit nel 4º byte, per subnetting

–

il firewall confronta indirizzi sorgenti di richieste con il proprio (p.e. 220.121.10.130) usando mask.

–

Se richiesta proviene da 220.121.10.12:

•

estrae bit significativi da proprio indirizzo e da quello sorgente e li confronta

11011100.01111001.00001010.10000010 11011100.01111001.00001010.00001100 11111111.11111111.11111111.11000000 yyyyyyyy.yyyyyyyy.yyyyyyyy.nxxxxxxx

= = = =

220.121.10.130 220.121.10.12 255.255.255.192 respinta!

Reti di Calcolatori (Fabio Panzieri)

309

Università di Bologna - Corso di Laurea in Informatica

Esempio: Routing R3

Subnet mask: 255.255.255.128 Subnet number: 128.96.34.0

128.96.34.15

Subnet number di H1: 128.96.34.15 AND 255.255.255.128 = 128.96.34.0

128.96.34.1 H1 R1

Subnet mask: 255.255.255.128 Subnet number: 128.96.34.128

128.96.34.130

128.96.34.139

128.96.34.129 R2

H3 128.96.33.14

H2

128.96.33.1

Subnet mask: 255.255.255.0 Subnet number: 128.96.33.0

H1 invia d/g a H2 if H2 IP addr AND subnetmask ≠ H1 subnet number then invia a R1

/*default router*/

else invia direttamente a H2 Reti di Calcolatori (Fabio Panzieri)

310

155

Università di Bologna - Corso di Laurea in Informatica

Subnetting e Routers •

Modifiche alle tabelle di forwarding – –

IP semplice: Subnetting: <SubnetworkNum; SubnetMask; NextHop> • •

router mantiene subnet mask di reti dst in generale, mantiene anche indirizzo di default router

Tabella di forwarding del router R1 Subnet number

Subnet mask

NextHop

128.96.34.0

255.255.255.128

interface 0

128.96.34.128

255.255.255.128

interface 1

128.96.33.0

255.255.255.0

R2

default

R3

Reti di Calcolatori (Fabio Panzieri)

311

Università di Bologna - Corso di Laurea in Informatica

Algoritmo di forwarding D = indirizzo IP di destinazione for ogni entry (SubnetNum, SubnetMask, NextHop) in tabella D1 = SubnetMask & D if D1 = SubnetNum if NextHop è una interfaccia trasmetti datagram direttamente a D else trasmetti datagram a NextHop if Subnetnum non in tabella then trametti datagram a router di default

Reti di Calcolatori (Fabio Panzieri)

312

156

Università di Bologna - Corso di Laurea in Informatica

Subnetting • •

Pre-condizione: vicinanza universitario) Motivazione

fisica

delle

subnets

(p.e.

campus

– Insieme di subnets che condividono IP network number appaiono a routers remoti come singola rete – Routers remoti • •

mantengono singolo network number per raggiungere tutte le subnets con medesimo IP network number • riduzione dimensioni tabelle di forwarding in routers selezionano unico percorso per raggiungere tutte le subnets con medesimo IP network number

– Vicinanza fisica di subnets con medesimo IP network number agevola routing interno a subnets

•

Scalabilità di subnetting

1. Migliora efficienza di assegnamento indirizzi (i.e., un classe B per più di una rete) 2. Aggregazione di informazione (i.e., un network number per raggiungere più reti) riducendo requisiti di memoria nei routers

Reti di Calcolatori (Fabio Panzieri)

313

Università di Bologna - Corso di Laurea in Informatica

Subnetting: esercizi • • • • • •

Dato l’indirizzo: 50.16.12.178... Qual’è il suo valore binario? 00110010.00010000.00001100.10110010 In quale classe si trova? A Come si stabilisce? valore del 1º byte (0 in posizione più alta) Qual’è la maschera di rete per questa classe? 255.0.0.0 Se la maschera di sottorete fosse: 255.255.240.0… – quante sottoreti questa maschera consentirebbe di specificare? – 255 nel byte di ordine più alto è la network mask; questo lascia 255.240.0 come subnet mask; in binario: 11111111.11110000.00000000; ovvero: 12 bits per sottoreti (gli 1) e i rimanenti 12 per hosts. Quindi,il nº di sottoreti è (2^12)-2, (escludendo sottoreti “tutti 0” e “tutti 1”). – quanti hosts/sottorete? (2^12)-2 (“tutti 0” e “tutti 1” esclusi per hosts) – quanti hosts in totale? Sottoreti x (host/sottorete)=((2^12)-2) x ((2^12)-2)

Reti di Calcolatori (Fabio Panzieri)

314

157

Università di Bologna - Corso di Laurea in Informatica

Scalabilità del routing: minimizzazione delle tabelle di routing • Problemi di scala: – Ip.: 50.000.000 di destinazioni • non realistico mantenere tutti gli indirizzi destinazione nelle tabelle di routing • il solo scambio della tabelle congestionerebbe le linee

• Problemi di amministrazione del routing – Internet: rete di reti – Amministratore di ciascuna rete può voler adottare politiche di routing proprietarie

• Soluzioni: – Classless routing – Gerarchie di routers Reti di Calcolatori (Fabio Panzieri)

315

Università di Bologna - Corso di Laurea in Informatica

Classless Inter-Domain Routing (CIDR) •

Tecnica per limitare – –

• •

crescita delle tabelle di routing nei routers di backbone (tra ASs) esaurimento indirizzi IP

Elimina classi statiche (A, B, C) e le rende di dimensioni variabili Assegna blocchi di network numbers contigui –

Dimensione blocco: potenza di 2 •

indirizzi nello stesso blocco devono condividere stesso prefisso

•

Rappresenta numero di rete mediante coppia

•

P.E.: Blocco assegnato all’ISP: [200.23.16.0, 200.23.16.30]

– – – –

length: n. di bits nel prefisso “network number” 20 bit di ordine più alto uguali Assegna a se stesso 200.23.16.0/20 Sfrutta 3 bit per assegnare a 8 organizzazioni clienti indirizzi di length 23

Blocco dell’ISP Organizzazione 0 Organizzazione 1 … Organizzazione 7

11001000 00010111 0001 0000 00000000 11001000 00010111 0001 0000 00000000 11001000 00010111 0001 0010 00000000

length 200.23.16.0/20 200.23.16.0/23 200.23.18.0/23

11001000 00010111 0001 1110

200.23.30.0/23

Reti di Calcolatori (Fabio Panzieri)

00000000

316

158

Università di Bologna - Corso di Laurea in Informatica

•

Subnetting:

•

CIDR:

•

E.g.:

CIDR

– singolo indirizzo IP condiviso da molteplicità di reti fisiche – collassa molteplicità di indirizzi IP in singolo indirizzo – aggrega rotte – ISP assegna network numbers adiacenti (20 bit) a AS X e AS Y – Gateway: accetta pacchetti con dst = 19 bit comuni (prefisso) – Risolve indirizzi secondo il criterio del “longest match” • E.g.: 179.10 e 179.10.15 in tabella di routing – IP dst: 179.10.15.6 -> forward a 179.10.15 – IP dst: 179.10.20.4 -> forward a 179.10

AS X gateway

ISP network

11000000000001 000001

Fornisce accesso a rete 11000000000001

AS Y 11000000000001 000000

Reti di Calcolatori (Fabio Panzieri)

317

Università di Bologna - Corso di Laurea in Informatica

Routing in Internet globale •

In generale, gerarchia a due livelli – Interior Gateway Protocols (ogni AS seleziona il suo) • P.e. RIP, OSPF

– Exterior Gateway Protocols (Internet standard) • P.e. EGP, BGP-4

•

Interior Gateway Protocols comunemente usati – RIP: Route Information Protocol • Distribuito con Unix • Algoritmo di distance-vector • Basato su hop-count

– OSPF: Open Shortest Path First • • • •

Internet standard usa algoritmo di link-state supporta bilanciamento del carico supporta autenticazione

Reti di Calcolatori (Fabio Panzieri)

318

159

Università di Bologna - Corso di Laurea in Informatica

Routing in Internet: Open Shortest Path First (OSPF) • OSPF – – – – –

“open”: di dominio pubblico implementa algoritmo link state usa algoritmo di Dijkstra per calcolare rotte annunci OSPF contengono un entry per ogni router vicino distribuiti all’intero dominio amministrativo

• Aggiunge a RIP – sicurezza: msgs OSPF sono autenticati – metriche di costo “tarate” su TOS (e.g., canale satellitare: basso costo per “best effort”, alto costo per “real time”)

• Introduce gerarchie di routing: – ogni dominio partizionabile in “aree” (area = internetwork fisica) – ogni router configurato per raggiungere “aree” (anzichè sotto-reti) => aumenta scalabilità del routing in domini ampi e strutturati Reti di Calcolatori (Fabio Panzieri)

319

Università di Bologna - Corso di Laurea in Informatica

OSPF • •

•

AS rappresentato da grafo OSPF usa reliable flooding e usa algoritmo di shortest path first per costruire tabelle di routing Link rappresentato da coppia di archi con pesi possibilimente diversi

Reti di Calcolatori (Fabio Panzieri)

320

160

Università di Bologna - Corso di Laurea in Informatica

OSPF •

AS puo’ essere ampio (i.e. rete di reti) – OSPF usa strutturazione gerarchica di AS in aree (numerate univocamente) • Area: rete o insieme di reti contigue

– Ogni AS ha area di backbone (area 0); – Routing inter-area è via l’area backbone – Routers in un’area mantengono stato dei link relativi ai routers nella stessa area e ai routers nell’area backbone • Flooding avviene solo internamente ad un area

– Inter-area routing in tre fasi • va al backbone area • da li all’area destinazione • infine alla destinazione

Reti di Calcolatori (Fabio Panzieri)

321

Università di Bologna - Corso di Laurea in Informatica

OSPF: gerarchie di routers •

Aggrega routers in ASs

•

Internal routers (stesso AS): eseguono protocollo di routing intra-AS, esclusivamente

•

Backbone routers: instradamento entro il solamente

•

Boundary routers (gateways):

•

eseguono backbone,

–

instradano traffico in/out l’AS

–

Eseguono protocollo intra-AS con tutti i routers nel medesimo AS

–

Eseguono protocollo inter-AS con gli altri gateway routers

Area border routers: instradano in/out backbone

Relazione tra ASs, backbones, e aree in OSPF Reti di Calcolatori (Fabio Panzieri)

322

161

Università di Bologna - Corso di Laurea in Informatica

Boundary routers (gateways) C.b

a

A.a

b

C

Boundary routers: •eseguono inter-AS routing fra loro •eseguono intra-AS b routing con altri routers nel loro AS

B.a A.c

A

a

a

d

c B

c

b

inter-AS e intra-AS routing in gateway A.c

network layer link layer physical layer

Reti di Calcolatori (Fabio Panzieri)

323

Università di Bologna - Corso di Laurea in Informatica

Intra-AS e Inter-AS routing

C.b

a Host h1

C

A.a

b

a

Inter-AS routing Fra A e B A.c

d c b A Intra-AS routing in AS A

Reti di Calcolatori (Fabio Panzieri)

B.a a

c B

Host h2 b

Intra-AS routing in AS B

324

162

Università di Bologna - Corso di Laurea in Informatica

Exterior Gateway Protocols EGP, BGP • Garantiscono raggiungibilità delle risorse attraverso gli ASs – non necessariamente rotte ottimali

• Complessità di costruire rotte ottimali dovuta a natura autonoma degli ASs – Costo dei link può essere quantificato diversamente da AS ad AS – Considerazioni politiche • Traffico da/per AS-IBM non deve transitare via AS-Microsoft, traffico USA - Europa non deve transitare via Canada

• EGP – Progettato per Internet strutturata ad albero • singolo backbone(radice) • ASs connessi come padri e figli, solamente • Non sufficientemente generale

Reti di Calcolatori (Fabio Panzieri)

325

Università di Bologna - Corso di Laurea in Informatica

BGP-4: Border Gateway Protocol • Classifica ASs in – stub AS

• singola connessione ad altro AS • trasporta solamente traffico locale – i.e. originato e/o destinato localmente

– multihomed AS

• connette a più di un AS • non accetta traffico “di passaggio” (i.e. non originato o destinato al suo AS)

– transit AS

• connette a più di un AS • accetta traffico di passaggio e traffico locale

• Ogni AS possiede:

– uno o più boundary routers – un BGP speaker che fornisce info di raggiungibilità da/a: • reti locali interne all’AS • altre reti raggiungibili (solamente nei transit AS)

Reti di Calcolatori (Fabio Panzieri)

326

163

Università di Bologna - Corso di Laurea in Informatica

BGP (esempio) • BGP Speaker per AS2: annuncia raggiungibilità di P e Q – network 128.96, 192.4.153, direttamente da AS2

192.4.32,

Regional provider A (AS 2) Backbone network (AS 1) Regional provider B (AS 3)

• BGP Speaker per backbone

e

192.4.3,

raggiungibili

Customer P (AS 4)

128.96 192.4.153

Customer Q (AS 5)

192.4.32 192.4.3

Customer R (AS 6)

192.12.69

Customer S (AS 7)

192.4.54 192.4.23

– networks 128.96, 192.4.153, 192.4.32, e 192.4.3 raggiungibili lungo il persorso (AS1, AS2).

• BGP Speakers possono cancellare percorsi annunciati Reti di Calcolatori (Fabio Panzieri)

327

Università di Bologna - Corso di Laurea in Informatica

IPv6 •

Motivazione iniziale: – IPv4: spazio indirizzi di 32-bit completamente esaurito entro il 2008 – IPv6: circa 5000 indirizzi IP per m2

•

Inoltre: – Nuovo formato header facilita processing/forwarding di d/g’s (semplificato rispetto a IPv4) – header modificato consente di supportare QoS – Nuovo indirizzo anycast • Specifica “entità topologiche” anzichè nodi – p.e.: • •

indirizzo anycast assegnato a gruppo di i/f’s d/g’s con dst=anycast inviati all’i/f “più vicina”, dove “più vicino” è determinato dai protocolli di routing

Reti di Calcolatori (Fabio Panzieri)

328

164

Università di Bologna - Corso di Laurea in Informatica

IPv6 •

Caratteristiche generali – – – – – – –

•

Indirizzi “classless” di 128-bit Multicasting Servizi real-time Supporto per autenticazione e sicurezza Supporto per autoconfigurazione Frammentazione Estensioni del protocollo

Header – –

40-byte di header di “base” Headers di estensione per • • • •

frammentazione source routing Autenticazione e sicurezza Altre opzioni

trasportati come payload

Reti di Calcolatori (Fabio Panzieri)

329

Università di Bologna - Corso di Laurea in Informatica

IPv6 Header (Cont) • Ver: V6 • Priority (o traffic class): priorità di d/g in un flusso • Flow Label: identifica d/g’s nello stesso flusso • N.B.: priority e flow label per QoS • Payload len: lunghezza in B di data • Next header: • chiave di demux (TCP, UDP)

• codice 44: hdr di estensione per frammentazione in “data” • codice 6: hdr TCP in “data” • Codice 51: header di autenticazione in “data”

• Hop limit: come TTL in IPv4 • Source/destination addresses:

• campo indirizzi di 16 B ciascuno

Reti di Calcolatori (Fabio Panzieri)

330

165

Università di Bologna - Corso di Laurea in Informatica

Altri cambiamenti da IPv4 • Checksum: rimosso per ridurre overhead di processing • Options: consentite, fuori dell’ header, indicate in “Next Header” – P.e., indirizzo anycast specificato in estensione di header per routing

• ICMPv6: nuova versione di ICMP – Ulteriori tipi di messaggi, e.g. “Packet Too Big” – Funzioni di management id gruppi multicast

Reti di Calcolatori (Fabio Panzieri)

331

Università di Bologna - Corso di Laurea in Informatica

Transizione da IPv4 a IPv6 • Routers non possono essere aggiornati simultaneamente in tutta Internet – impossibile riservare un giorno in cui si passa da IPv4 a IPv6 in tutta Internet

• Come far lavorare contemporaneamente? • 2 approcci proposti:

i

routers

con

IPv4

e

IPv6

– Dual Stack: alcuni routers con doppia pila di protocolli (v6, v4) “traducono” da un formato all’altro – Tunneling: IPv6 trasportato come payload in datagram IPv4 datagram fra routers IPv4 Reti di Calcolatori (Fabio Panzieri)

332

166

Università di Bologna - Corso di Laurea in Informatica

Approccio Dual Stack

• A e F, anche se nodi IPv6, si scambiano pacchetti IPv4 – Nella traduzione, campi specifici corrispondenti IPv4, vanno persi.

IPv6

non mappabili in campi

Reti di Calcolatori (Fabio Panzieri)

333

Università di Bologna - Corso di Laurea in Informatica

Tunneling

IPv6 inside IPv4 where needed

D to E IPv4 (encapsulating IPv6) Reti di Calcolatori (Fabio Panzieri)

334

167

Università di Bologna - Corso di Laurea in Informatica

Ulteriore utilizzo di tunnel IP •

Tecnica di realizzazione di reti private virtuali

•

Routers connessi da VC

• •

VC creato c/o router src fornendo indirizzo IP di router dst Router src incapsula datagram IP in ingresso in datagram IP con src = router_src e dst = router_dst Router dst

– i.e., basate su reti pubbliche – i.e., n. arbitrario di reti può separarli

•

– riconosce proprio indirizzo IP in datagram – esamina payload e estrae datagram IP da datagram IP ricevuto – legge campo dst – invia a dst

•

N.B.: routers lungo il cammino tra router src e router dst trattano il datagram “capsula” come datagram IP standard

Reti di Calcolatori (Fabio Panzieri)

335

Università di Bologna - Corso di Laurea in Informatica

IP Tunneling: esempio Rete privata

Net 1

Rete privata

R1

R2

tunnel

10.0.0.1

IP hdr: DST := 2.x IP payload

IP hdr: DST:= 10.0.0.1 IP hdr: DST = 2.x IP payload

Tabella di routing in R1 NetworkNum 1 2 default

Internetwork

NextHop I/F 0 I/F virtuale 0 I/F 1

Reti di Calcolatori (Fabio Panzieri)

Net 2

IP hdr: DST := 2.x IP payload

Payload di IP d/g da R1 a R2

Configurazione tabella di routing in R1: I/F 0: connette a Net 1 I/F 1: default (i.e., connette a reti ≠ Net 1) I/F virtuale 0: connette a tunnel (i.e. R2) R1 trasmette datagram per Net2 a R2 via I/F virtuale 0 –

incapsulato in d/g IP (Dst = R2_addr = 10.0.0.1) •

R2_netnum = 10 ≠ 1 e da 2

=>

d/g trasmesso via I/F di default

336

168

Università di Bologna - Corso di Laurea in Informatica

Tunneling •

Vantaggi –

Implementazione di politiche di sicurezza

–

Specializzazione dei routers

• •

–

possono supportare funzionalità specifiche, solo nei tunnel – p.e., rete privata virtuale con multicasting

Utilizzo di protocolli non standard nella rete privata virtuale ⇒

•

Tunnel può trasportare traffico crittografato

Routers alle estremità dei tunnel possono gestire protocolli non standard

Svantaggi – – –

Aumento delle dimensioni dei d/g’s Routers possono soffrire di degrado prestazionale (p.e. causa conversione protocolli) Costi di management dei tunnel (setting-up, verifiche di correttezza del routing)

Reti di Calcolatori (Fabio Panzieri)

337

Università di Bologna - Corso di Laurea in Informatica

Livello di Trasporto •

Livello Network fornisce scambio messaggi host-to-host – in Internet: servizio ‘best effort’ fornito da IP • Scarta pacchetti • Scambia ordine • Consegna duplicati • Limita dimensione • Consegna con ritardo arbitrario

•

Livello Trasporto fornisce servizio scambio di messaggi process-to-process (o “end-to-end” ), i.e. da applicazione ad applicazione – In Internet • UDP (User Datagram Protocol): servizio “best effort” processo-processo • TCP (Transmission Control Protocol): servizio di consegna affidabile di flusso di bytes ordinato processo-processo

– In Unix: servizi accessibili via libreria “socket”

Reti di Calcolatori (Fabio Panzieri)

338

169

Università di Bologna - Corso di Laurea in Informatica

Livello di Trasporto: UDP/TCP • UDP aggiunge “indirizzamento di processo” a IP – i.e. pacchetti trasmessi/ricevuti a/da processi in elaboratori ospiti

• TCP copre gap fra requisiti applicativi e servizi del livello rete i.e., TCP: – Garantisce consegna messaggi/pacchetti – Mantiene ordine di trasmissione – Consegna al più una copia – Abilita trasmissione/ricezione di messaggi di lunghezza arbitraria – Consente al ricevente di regolare il flusso

• Ulteriori requisiti applicativi soddisfatti a livelli superiori (p.e. autenticazione)

Reti di Calcolatori (Fabio Panzieri)

339

Università di Bologna - Corso di Laurea in Informatica

UDP • • •

Servizio “best effort” – Trasmissione/ricezione di datagrams non affidabile, non ordinata Aggiunge demultiplexing a IP Sorgente e destinazione identificati da “port#”: srcPort, dstPort – Coppia identifica univocamente processo applicativo – Servers utilizzano porte well-known; •

•

•

eg: server DNS su qualunque ospite è a porta no. 53, talk a porta no. 517 (cf. /etc/services in Unix)

Checksum – pseudo header + udp header + data • pseudo header: campi length, src, dst in IP hdr • attualmente opzionale, obligatorio con IPV6

0

16 SrcPort

31 DstPort

Checksum

Length Dati

UDP header

Length: lunghezza in bytes di d/g UDP, incluso hdr UDP

Reti di Calcolatori (Fabio Panzieri)

340

170

Università di Bologna - Corso di Laurea in Informatica

Demultiplexing in UDP • d/g: unità dati scambiata fra entità a livello UDP dst

P3

Dati di applicazione

M

M

Ht M Hn d/g

M

P4

application transport network

P1 src

d/g header

Demultiplexing: consegna dei d/g’s ricevuti ai processi applicativi destinazione

application transport network

M

P2 src

application transport network

Reti di Calcolatori (Fabio Panzieri)

341

Università di Bologna - Corso di Laurea in Informatica

Multiplexing/demultiplexing: esempi host A

src port: x dst port: 23

server B

src port:23 dst port: x

Source IP: C Dest IP: B source port: y dest. port: 53

Uso di port#: telnet

Client host A Reti di Calcolatori (Fabio Panzieri)

Client host C

Source IP: A Dest IP: B source port: x dest. port: 53

Source IP: C Dest IP: B source port: x dest. port: 53

DNS server B Uso di port#: DNS server 342

171

Università di Bologna - Corso di Laurea in Informatica

UDP • Implementazione di astrazione di porta può differire da OS a OS – in genere • Porta implementata come coda di messaggi • Coda messaggi mantenuta in spazio utente • Gestione/assegnazione porte effettuata da kernel di OS

• Ricezione di messaggi – UDP accoda msg a porta (coda) in esso specificata if coda piena then scarta messaggio – Processo in ricezione su porta: • rimuove messaggio in testa alla coda if coda vuota then blocca finché msg ricevuto

Reti di Calcolatori (Fabio Panzieri)

343

Università di Bologna - Corso di Laurea in Informatica

UDP: osservazioni • Non fornisce controllo di flusso che indica a src di ridurre rate di trasmissione • Non implementa trasmissione/consegna affidabile/ordinata di datagrams (solo “best effort”) • Implementa individuazione di errori via checksum • A che serve? – Streaming di oggetti multimediali tolleranti perdite di d/g’s e sensibili a tasso di trasferimento dati (p.e. telefonia via Internet) – DNS – Simple Network Management Protocol (SNMP) • Monitoring di routers e hosts

• Trasferimento dati affidabile utilizzando UDP? – aggiungere affidabilità a livello applicativo • tecniche di error recovery “ad hoc” per l’applicazione

Reti di Calcolatori (Fabio Panzieri)

344

172

Università di Bologna - Corso di Laurea in Informatica

TCP

• Flusso di bytes ordinato, affidabile, connection-oriented – Processo src scrive no. arbitrario di bytes (flusso/stream) su connessione – TCP (xmit) frammenta in segmenti, e invia ogni segmento via IP – TCP (rcv) riceve e riassembla segmenti, e effettua delivery a processo dst

– Processo dst legge flusso di bytes da connessione Application process

Application process

…

…

Write bytes

TCP Send buffer

Read bytes

TCP Receive buffer

Segment

Segment

…

Segment

Transmit segments

•

Full duplex (per semplicità, figura mostra half duplex)

• •

Controllo di flusso: impedisce che src sovraccarichi dst Controllo di congestione: impedisce che src’s sovraccarichino rete

(i.e., i routers)

Reti di Calcolatori (Fabio Panzieri)

345

Università di Bologna - Corso di Laurea in Informatica

Segmenti TCP • Pacchetti TCP: segmenti – ognuno trasporta un segmento del flusso di bytes – max. seg. size (MSS) uguale a max. trasfer unit (MTU) supportata da rete direttamente connessa (meno overhead di headers IP e TCP) – TCP invia segmento quando: • MSS bytes sono disponibili, oppure • applicazione forza trasmissione invocando operazione di push su TCP; • timer periodicamente forza TCP a trasmettere segmento non vuoto, anche se non completamente pieno.

Reti di Calcolatori (Fabio Panzieri)

346

173

Università di Bologna - Corso di Laurea in Informatica

Formato Segmenti TCP Quadrupla

0

<src_IP_addr, srcPort;

10

4

16

31

SrcPort

dst_IP_addr, dstPort> identifica univocamente connessione fra due processi Poiché connessioni sono stabilite e rilasciate, numeri di porta riutilizzabili in tempi diversi per identificare connessioni diverse.

DstPort SequenceNum Acknowledgment

HdrLen

0

Flags

AdvertisedWindow

Checksum

UrgPtr Options (variable) Data

Reti di Calcolatori (Fabio Panzieri)

347

Università di Bologna - Corso di Laurea in Informatica

Segmenti TCP • Acknowledgment,SequenceNum,AdvertisedWindow: usati per controllo di flusso • SequenceNum contiene seq. no. del primo byte di dati nel segmento (ogni byte ha un seq.no.)

– Acknowledgment e AdvertisedWindow contengono info. su flusso di dati nell’altra direzione (in fig., flusso in un’unica direzione) Dati (SequenceNum)

Sender

Receiver Acknowledgment + AdvertisedWindow

Flags: SYN, FIN, RESET, PUSH, URG, ACK SYN per stabilire, FIN per chiudere connessione ACK: se settato indica che il campo acknowledgment è valido RESET: ricevente vuole chiudere connessione (condizione anormale individuata) PUSH: src ha invocato push; TCP deve notificare ricevente URG: segmento contiene “urgent data” (in testa); UrgPtr punta ai dati non urgenti Reti di Calcolatori (Fabio Panzieri)

348

174

Università di Bologna - Corso di Laurea in Informatica

Attivazione connessione “Three way handshake” • •

• •

• • • •

Processo server: ‘passive open’, in ricezione (p.e., su porta “well-known”) Processo client: inizia connessione con ‘active open’: – invia segmento SYN, con seq.no. iniziale • Flags = SYN, SequenceNum = x Se “Server not listening”: – TCP ritorna segmento RESET altrimenti, server risponde con ack – Flags = ACK, Ack = x+1 – server SN (Flags = SYN, SequenceNum = y). Infine, client risponde: (Flags = ACK, Ack = y+1). Campo ack identifica prossimo SN atteso da destinatario (client o server) e conferma SNs precedenti. SN iniziali scelti a caso per ridurre la possibilità che connessione accetti SNs di connessioni precedenti , e ora chiuse, utilizzanti la stessa porta. Timers usati per ritransmissioni (non mostrati in figura)

Server

Client Flags

= SY N, S equen

ceNu

en Sequ

K, N.AC = SY s g + 1 Fla = x Ack Flags

= AC K,

m = x

ceNu

m=y

,

Ack = y+1

Reti di Calcolatori (Fabio Panzieri)

349

Università di Bologna - Corso di Laurea in Informatica

Rilascio di connessione •

Ogni connessione è full duplex – Ogni processo agli estremi della connessione può rilasciare la sua parte di connessione ( “simplex”) indipendentemente.

•

Per rilasciare connessione, – ogni partecipante invia segmento FIN • p.e., A invia FIN a B • quando questo è confermato (ack’ed) da B, A chiude la sua connessione e attende FIN da B; • quando A riceve FIN da B, A invia un ACK, attende per periodo “time-wait”, e chiude – “time-wait”: doppio del massimo TTL di un datagram IP (120 secs). – motivazione: se ACK da A va perso e B invia un altro FIN, si vuole evitare che venga ricevuto da una nuova connessione e interpretato erroneamente. • B chiude dopo “time-wait”, se non riceve ACK da A.

Reti di Calcolatori (Fabio Panzieri)

350

175

Università di Bologna - Corso di Laurea in Informatica 2. Client effettua active open e entra in SYN_SENT

Connect/Disconnect: Diagramma di transizione degli stati

CLOSED Active open /SYN

1.

Server effettua passive open e entra in “listen”

Passive open

Close

connect

Close LISTEN

3. Server riceve SYN, genera SYN+ACK, entra stato SYN_RCVD

Send/ SYN SYN/SYN + ACK

ACK

Close/FIN

SYN_SENT

SYN + ACK/ACK

ESTABLISHED Close /FIN

4. Client riceve SYN+ACK, invia ACK, entra stato entra stato ESTABLISHED FIN/ACK

FIN_WAIT_1 ACK FIN_WAIT_2

CLOSE_WAIT

AC FIN/ACK K + FI N /A CK FIN/ACK

Close/FIN CLOSING

LAST_ACK

ACK Timeout after two segment lifetimes TIME_WAIT

disconnect

N.B. In 4, se ACK di client perso => client in ESTABLISHED => client invia dati con ACK settato + campo Acknowledgement corretto => server entra in ESTABLISHED al primo segmento ricevuto

SYN/SYN + ACK SYN_RCVD

ACK CLOSED

Reti di Calcolatori (Fabio Panzieri)

351

Università di Bologna - Corso di Laurea in Informatica

Controllo di flusso in TCP • Implementa “sliding window” – Garantisce consegna affidabile dei messaggi – Garantisce ordinamento (i.e. consegna nello stesso ordine trasmissione) – Impone controllo di flusso (i.e. mittente non sovraccarica dst)

di

• Inoltre in TCP – Dst informa dinamicamente src di dimensione “window” utilizzando campo “advertized_window” nell’header di segmento TCP => src non può avere mai più di “advertized_window” bytes non confermati

– Dst dimensiona buffer di ricezione ad “advertized_window” bytes dipendentemente da memoria disponibile – Src può inviare esclusivamente “advertized_window” Reti di Calcolatori (Fabio Panzieri)

un no. max

di

bytes pari

a

352

176

Università di Bologna - Corso di Laurea in Informatica

Sliding window: TCP vs.Data Link Livello Data Link – protocollo esegue su configurazione fissa di nodi • link singolo che connette due computers (src e dst) direttamente

Livello di Trasporto – src e dst dovunque in Internet – necessità di stabilire e rilasciare esplicitamente connessione

Livello Data Link – RTT fisso per data configurazione

Livello di trasporto – RTT variabile • i due processi possono essere arbitrariamente vicini (stessa LAN), o lontani (in continenti distinti, connessi da molteplicità di reti) • richiede meccanismo di timeout adattivo per scopi di ritrasmissione • gestione conseguenze dovute a ritardi; in particolare, consegna di pacchetti “vecchi” (non si verifica a livello data link). Reti di Calcolatori (Fabio Panzieri)

353

Università di Bologna - Corso di Laurea in Informatica

Sliding window: TCP vs.Data Link Livello data link – protocollo esegue con window size prefissata – src e dst configurati con sufficiente spazio buffer

Livello di trasporto – host può avere in esecuzione molteplicità di applicazioni che mantengon o connessioni TCP => dimensioni buffer variabili.

Livello data link – capacità (bandwidth) link nota, quindi src può decidere max data rate di trasmissione.

Livello di trasporto – molteplicità di links con differenti capacità possono essere utilizzati in singola connessione – link a bassa bandwidth può essere congestionato – TCP deve poter gestire congestione di rete

Reti di Calcolatori (Fabio Panzieri)

354

177

Università di Bologna - Corso di Laurea in Informatica

Ordinamento segmenti in TCP •

TCP mantiene buffers mittente e ricevente – Buffer mittente contiene: (i) dati trasmessi ma non ack’ed, (ii) dati scritti da applicazione in buffer TCP, ma non ancora trasmessi

– Buffer ricevente contiene: (i) dati ricevuti, possibilmente non in sequenza (ii) dati ricevuti in sequenza, ma non ancora letti da applicazione

– Puntatori ai buffers = SNs dei singoli bytes (per semplicità)

Sending application

Receiving application

TCP

TCP

LastByteWritten

LastByteRead

Buffer mittente

Buffer ricevente LastByteAcked

LastByteSent

NextByteExpected

LastByteRcvd

Reti di Calcolatori (Fabio Panzieri)

355

Università di Bologna - Corso di Laurea in Informatica

Ordinamento segmenti in TCP: invarianti •

Mittente mantiene 3 puntatori (SNs): – LastByteAcked, LastByteSent, LastByteWritten M.1 LastByteSent ≥ LastByteAcked – SN di ultimo byte trasmesso ≥ SN ultimo byte ack’ed

M.2 LastByteSent ≤ LastByteWritten – SN di ultimo byte trasmesso ≤ SN di ultimo byte scritto da applicazione in buffer TCP

– Bytes compresi tra LastByteAcked e LastByteWritten devono essere mantenuti in buffer mittente

•

Ricevente mantiene 3 puntatori (SNs): – LastByteRead, NextByteExpected, LastByteRcvd R.1 LastByteRead < NextByteExpected •

Applicazione non può leggere un byte prima di averlo ricevuto e prima di aver ricevuto tutti i precedenti a quello • NextByteExpected = SN di primo byte che soddisfa questo criterio

R.2 NextByteExpected ≤ LastByteRcvd + 1 •

a causa di possibile consegna non ordinata: – se in ordine allora NextByteExpected = SN successivo – se non in ordine allora NextByteExpected = SN di inizio gap (per R.1)

– Bytes compresi tra LastByteRead e LastByteRcvd devono essere mantenuti in buffer ricevente

Reti di Calcolatori (Fabio Panzieri)

356

178

Università di Bologna - Corso di Laurea in Informatica

Controllo di flusso in TCP: invarianti • Assumiamo: – dimensione buffer mittente: MaxSendBuffer – dimensione buffer ricevente: MaxRcvBuffer

• Ricevente deve garantire R.1 LastByteRcvd - LastByteRead ≤ MaxRcvBuffer (per evitare buffer overflow) ⇒ R.2 AdvertisedWindow = MaxRcvBuffer - (LastByteRcvd LastByteRead) i.e. spazio libero in buffer ricevente

• N.B. – LastByteRead avanza quando il ricevente legge dati, liberando spazio nel buffer; se ricevente lento, allora AdvertisedWindow si riduce e può calare a 0 – Se AdvertisedWindow = 0, mittente sospende trasmissione Reti di Calcolatori (Fabio Panzieri)

357

Università di Bologna - Corso di Laurea in Informatica

Controllo di flusso in TCP •

Mittente LastByteSent - LastByteAcked indica i bytes inviati e non ancora ack’ed => mittente deve garantire che, ad ogni istante: LastByteSent - LastByteAcked ≤ AdvertisedWindow del ricevente Perciò, mittente mantiene EffectiveWindow (max. dati che può inviare) EffectiveWindow = AdvertisedWindow - (LastByteSent - LastByteAcked)

– EffectiveWindow deve essere > 0 perché possa inviare dati

N.B. :

EffectiveWindow usata per abilitare/inibire trasmissione.

E.g.: • Mittente riceve ACK di x bytes • incrementa LastByteAcked = LastByteAcked + x • Ricevente non ha consumato/letto dati • Annuncia AdvertisedWindow di x bytes più piccola • Mittente può liberare spazio in buffer di trasmissione ma non può trasmettere

Reti di Calcolatori (Fabio Panzieri)

358

179

Università di Bologna - Corso di Laurea in Informatica

Controllo di flusso in TCP • Mittente Prevenzione di overflow del buffer di mittente LastByteWritten - LastByteAcked ≤ MaxSendBuffer – Applicazione mittente può riempire buffer TCP mittente solo se in questo c’è spazio. Se l’applicazione vuole scrivere y bites, sarà bloccata se: (LastByteWritten - LastByteAcked) + y > MaxSendBuffer

• Se AdvertisedWindow = 0, mittente blocca, in attesa di AdvertisedWindow > 0. – Per sbloccarlo, TCP mittente invia segmento con unico byte di dati, occasionalmente. Ack del ricevente indica dimensione corrente della AdvertisedWindow. Assumendo che applicazione ricevente legga/consumi dati da buffer TCP (window), prima o poi AdvertisedWindow > 0.

Reti di Calcolatori (Fabio Panzieri)

359

Università di Bologna - Corso di Laurea in Informatica

Controllo di flusso in TCP: esempio Receiver buffer = 4K (comunicato a sender durante “connect”) Sender

Receiver 4KB RCV buffer = ø

1. Write 2KB 2KB dati SN = 0

2KB data

ø

ACK = 2048 WS = 2KB /* NextByteExpected */ 2. Write 3KB

/* WS = 2048 => sender frammenta dati in 2 segmenti */

/* 1º segmento */

2KB dati SN = 2048 ACK = 4096

/* Sender bloccato da WS = 0 */

WS = 0

BUFFER

SATURO

/* Receiver legge 2KB dati */ ø

dati non letti

ACK = 4096 WS = 2KB

/* Sender può inviare fino a 2KB */ 3. Write 1KB

1KB dati SN = 4096 ACK = 5120

Reti di Calcolatori (Fabio Panzieri)

1KB dati

ø dati non letti

WS = 1KB 360

180

Università di Bologna - Corso di Laurea in Informatica

Sliding Window: osservazioni • Consente di massimizzare l’uso del link, a condizione che la window sia sufficientemente ampia • Throughput = ~ (n/RTT) – n: numero di pkts trasmessi e non ack’ed – in fig.: n = 9 pacchetti in un RTT invece di 1

tempo Reti di Calcolatori (Fabio Panzieri)

361

Università di Bologna - Corso di Laurea in Informatica

Sliding Window: osservazioni • Mittente – deve mantenere tutti i pacchetti non ack’ed in buffer perchè possono dover essere ritrasmessi

• Ricevente – può accettare pacchetti fuori ordine, ma solo entro i limiti delle dimensioni della finestra di ricezione

• Mittente: – deve attivare timer per richiedere ritrasmissione di segmento, se ACK non ricevuto in un certo intervallo di tempo (time-out).

• DURATA DEL TIME-OUT ?

Reti di Calcolatori (Fabio Panzieri)

362

181

Università di Bologna - Corso di Laurea in Informatica

Time-out 1

Timeout

RTT

RTT

1 1

Timeout 1

Timeout troppo lungo inefficienza

Timeout troppo breve pacchetti duplicati

Reti di Calcolatori (Fabio Panzieri)

363

Università di Bologna - Corso di Laurea in Informatica

Time-out adattivo in TCP • TCP usa meccanismo “adattivo”: – – – =>

in generale, durata del time-out ≈ RTT tra src <-> dst noto in LANs (in generale), ignoto in multi-hop WANs deve essere utilizzabile in entrambi i contesti protocollo deve adattarsi alle caratteristiche del path tra src e dst

• Schema in uso oggi definito dopo sperimentazioni attraverso gli anni • Nel seguito – Schema originale – Schema modificato, in uso oggi

Reti di Calcolatori (Fabio Panzieri)

364

182

Università di Bologna - Corso di Laurea in Informatica

Timeout adattivo in TCP: schema originale 1. Misura SampleRTT per ogni coppia segment/ACK 2. Calcola media pesata di RTT EstimatedRTT = α x EstimatedRTT + (1 − α) x SampleRTT dove 0.8 ≤ α ≤ 0.9 –

EstimatedRTT: combinazione pesata del suo valore con il valore attualmente misurato di SampleRTT

3. Setta timeout sulla base di EstimatedRTT TimeOut = 2 x EstimatedRTT

•

Schema insoddisfacente – non tiene conto della varianza del RTT • RTT può variare da segmento a segmento a causa di carico/congestione nei routers, carico variabile agli hosts, …

– Varianza piccola fra campioni di RTT => EstimatedRTT può essere credibile e non ci dovrebbe essere bisogno di moltiplicarlo per 2 – Varianza ampia => valore di TimeOut non dovrebbe essere influenzato troppo da EstimatedRTT

Reti di Calcolatori (Fabio Panzieri)

365

Università di Bologna - Corso di Laurea in Informatica

Timeout adattivo in TCP: schema modificato •

Principio: time out deve essere settato in modo tale che solo raramente termini troppo presto  TimeOut > EstimatedRTT  TimeOut = EstimatedRTT + Difference dove Difference è una quantità che cattura quanto SampleRTT si discosta da EstimatedRTT (detta “deviazione media”)

•

Nuovo calcolo di EstimatedRTT tiene conto di variazione media del ritardo: EstimatedRTT = EstimatedRTT + (δ x Difference)/* RTT medio */

• i.e.: Difference = SampleRTT - EstimatedRTT

–

•

•

Calcola deviazione da RTT medio: Deviation = Deviation + δ(|Difference|- Deviation), 0 ≤ δ ≤ 1

Valore di time out settato sulla base di RTT stimato e deviazione da questo: TimeOut = µ x EstimatedRTT + φ x Deviation (i valori µ = 1, φ = 4 sono risultati soddisfacenti). Quindi: Deviation piccola => valore di TimeOut vicino a EstimatedRTT Deviation grande => valore di TimeOut dominato da varianza in RTT

Reti di Calcolatori (Fabio Panzieri)

366

183

Università di Bologna - Corso di Laurea in Informatica

Controllo di Congestione Ciò che sappiamo: • come instradare pacchetti da src a dst • come trasmetterli in modo “affidabile” (i.e., ordinati, individuando eventuali perdite, ...) Cio’ che non sappiamo: • a che velocità una src può trasmettere senza intasare la rete?

Reti di Calcolatori (Fabio Panzieri)

367

Università di Bologna - Corso di Laurea in Informatica

Problemi • Trasmissione troppo lenta – link sotto-utilizzato – inutili ritardi

• Trasmissione troppo veloce – link utilizzato a pieno ma ... • si possono formare code nei buffers dei router – => ritardi • overflow nei buffers dei router – => pkts scartati

Reti di Calcolatori (Fabio Panzieri)

368

184

Università di Bologna - Corso di Laurea in Informatica

In astratto

A

B

Src Host

Buffer in Router

•

Assumiamo router consistent di:

•

Tre problemi di congestione

– – – –

Dst Host

singola coda per ogni coppia di input - output singolo flusso deve adattarsi a collo di bottiglia causato da banda ad ampiezza fissa singolo flusso deve adattarsi a collo di bottiglia causato da banda ad ampiezza variabile flusso multipli devono condividere banda

Reti di Calcolatori (Fabio Panzieri)

369

Università di Bologna - Corso di Laurea in Informatica

Flusso singolo, banda fissa

A

100 Mbps

B

• Richiede di adattare DTR all’ampiezza di banda disponibile – non banale, senza saperlo a priori – potrebbe essere un link con capacità in Gb, o un moden con capacità in Kb

Reti di Calcolatori (Fabio Panzieri)

370

185

Università di Bologna - Corso di Laurea in Informatica

Flusso singolo, banda variabile

BW(t)

A

B

• Richiede di adattare DTR istantaneamente a variazioni di banda

Reti di Calcolatori (Fabio Panzieri)

371

Università di Bologna - Corso di Laurea in Informatica

Flussi multipli Due problemi • Adattare DTR totale (i.e., traffico “aggregato”) a sfruttare al meglio la Banda totale disponibile • Allocare la banda fra flussi distinti “equamente”

A1 A2 A3 Reti di Calcolatori (Fabio Panzieri)

B1 100 Mbps

B2 B3 372

186

Università di Bologna - Corso di Laurea in Informatica

In pratica • Controllo di congestione: problema di allocazione di risorse che coinvolge molteplicità di flussi, attraverso molteplicità di links e routers

Reti di Calcolatori (Fabio Panzieri)

373

Università di Bologna - Corso di Laurea in Informatica

Controllo di congestione •

Problema (in generale): – allocazione “equa” di risorse a utenti in competizione per accedervi • risorse: ampiezza di banda, memoria dei router • utenti: pacchetti in competizione per l’accesso ad un link

•

Origine del problema: – Internetwork • src e dst connessi da link con differenti velocità di trasmissione

– Store-and-forward • Pacchetti ricevuti ai routers mantenuti in code, in attesa di trasmissione • Code possono andare in overflow e pacchetti essere scartati • => CONGESTIONE

•

Soluzione: meccanismi di controllo di congestione – implementano politiche di gestione di code nei routers – limitano la velocità di trasmissione degli host src

Reti di Calcolatori (Fabio Panzieri)

374

187

Università di Bologna - Corso di Laurea in Informatica

Approcci alla soluzione • Prevenzione – pre-allocare risorse in modo da evitare congestione => ruolo attivo della rete nell’allocare risorse P.e.: scheduling di VC su link fisico in particolare intervallo di tempo

+ Consente di evitare congestione • rende meccanismi di controllo di congestione non necessari

- Complesso - richiede “negoziazione” di risorse prima dell’uso

- Sotto-utilizzazione di risorse

• Ottimistico (senza prenotazione) – non pre-allocare risorse e controllare congestione se e quando si verifica • consente a qualunque src di trasmettere n. arbitrario di pacchetti • se si verifica congestione, abilita ritrasmissione

Reti di Calcolatori (Fabio Panzieri)

375

Università di Bologna - Corso di Laurea in Informatica

Approcci alla soluzione • Tariffario – scarta prima pacchetti di chi “paga meno” (i.e., offerta di servizi differenziati) – richiede modello tariffario

• Adattamento dinamico – mantiene controllo del livello di congestione della rete – aumenta traffico a rete scarica – riduce traffico a rete carica

• Tutte e 4 le tecniche possono avere senso (in contesti diversi) – in Internet si usa “adattamento dinamico” • a causa di caratteristiche di traffico, assenza di tariffe, ... Reti di Calcolatori (Fabio Panzieri)

376

188

Università di Bologna - Corso di Laurea in Informatica

Allocazione di risorse e controllo di congestione • Allocazione di risorse: componenti di rete cercano di soddisfare requisiti applicativi per risorse di rete – Host usano protocolli di “signaling” per esprimere requisiti di risorse – Routers/host intermedi rispondono relativamente alla disponibilità delle risorse richieste

• Controllo di congestione: componenti di rete prevengono, o reagiscono a, condizioni di sovraccarico delle risorse di rete – può utilizzare meccanismi di allocazione di risorse

• Implementazione: parte nei routers, parte negli hosts (livello di trasporto) • Controllo di flusso (CdF) vs. Controllo di congestione (CdC) – CdF: impedisce che src veloce sovraccarichi dst lento – CdC: controlla che insieme di src’s non sovraccarichino risorse di rete Reti di Calcolatori (Fabio Panzieri)

377

Università di Bologna - Corso di Laurea in Informatica

Allocazione di risorse: problemi •

Modello di rete a commutazione di pacchetto –

Link possono avere diverse capacità (cf. Fig.) ≠ – –

da reti ad accesso condiviso (shared access media (SAM), p.e. Ethernet, token ring) in SAM, src “osserva” traffico su rete e decide se trasmettere o no protocollo MAC effettua controllo di congestione

Source 10-M 1

bps

Ethe

rnet

Router 1.5-Mbps T1 link

•

Destination

I FDD

CdC e routing: CdC ps non implementabile mediante routing alternativo che evita router -Mb Source congestionato 100 2 – –

Possibilità di “bottleneck router” (cf. Fig.) => assenza di rotte alternative Complessità di routing in Internet => garantire rotta priva di cicli

Reti di Calcolatori (Fabio Panzieri)

378

189

Università di Bologna - Corso di Laurea in Informatica

Allocazione di risorse: problemi • Modello di rete: flussi “connectionless”

– Sequenza di pkts trasmessi fra coppie di src/dst

• pkts in un flusso seguono identico percorso attraverso la rete • Astrazione di flusso: visibile ai routers – Mantengono “soft state” per ogni flusso – “soft state” non richiede attivazione di connessione – non ha semantica end-to-end, i.e. non implica consegna ordinata dei pkts

≠ VC: astrazione end-to-end visibile agli host e non ai routers Perchè non mantenere VC attraverso routers (e.g., X.25)? • Sotto-utilizzazione di risorse

• VC setup riserva risorse nei routers; se non usato, risorse inutilizzate

Source 1 Router

Destination 1 Router

Source 2 Router

Destination 2

Molteplicità di flussi attraverso i routers

Source 3 Reti di Calcolatori (Fabio Panzieri)

379

Università di Bologna - Corso di Laurea in Informatica

Politiche di allocazione di risorse Classificazioni principali a) Router-centric vs. Host-centric b) Reservation-based vs. Feedback-based c) Window-based vs. Rate-based Router-centric vs. Host-centric • Router-centric: ogni router – –

•

Host-centric –

•

decide quali pacchetti trasmettere e quali scartare segnala a hosts tasso di trasferimento dati che possono generare End host osserva condizioni di rete (p.e., quanti pacchetti raggiungono dst), e regola traffico che genera

Non mutualmente esclusive – –

in router-centric: host devono rispettare messaggi di cntrl dai router in host-centric: routers devono implementare politiche di eliminazione pacchetti da code quando queste vanno in overflow

Reti di Calcolatori (Fabio Panzieri)

380

190

Università di Bologna - Corso di Laurea in Informatica

Politiche di allocazione di risorse Reservation-based vs. feedback-based • Reservation-based – – –

•

ogni host richiede a rete una certa “capacità” quando attiva un VC ogni router valuta disponibilità risorse e le alloca, se possibile se risorse non disponibili, router rigetta flusso

Feedback-based: – –

End-host invia dati e regola tasso di trasferimento sulla base del feedback che riceve Feedback implicito: • =>

–

Host regola tasso di trasfermento dati (DTR) sulla base del comportamento “osservabile” della rete (p.e., % pkts persi) host-centric (routers non prendono decisioni)

Feedback esplicito: • =>

Router congestionato invia messaggio a host di ridurre DTR router-centric, dato che il router è coinvolto

Reti di Calcolatori (Fabio Panzieri)

381

Università di Bologna - Corso di Laurea in Informatica

Politiche di allocazione di risorse Window-based vs. rate-based – Window-based: • Src “annuncia” la window_size, i.e. la quantità di buffer che richiede

– Rate-based: • Rete regola flusso da src segnalando quanti bps può trasmettere

•

In Internet attuale – Servizio “best-effort” => usare tecniche “feedback-based” • Utenti di Internet non possono “prenotare” risorse • CdC in end-host, usando meccanismi “window-based”

•

In Internet2 – DiffServ: meccanismi reservation-based – “reservation” espressa in “rate”, i.e. DTR in bps

Reti di Calcolatori (Fabio Panzieri)

382

191

Università di Bologna - Corso di Laurea in Informatica

Allocazione di risorse: metriche di valutazione • Efficacia del meccanismo

Throughput/delay

– Power (rapporto throughput/delay) – Obiettivo: massimizzare questo rapporto al variare del carico di rete

Optimal load

Load

• “Fairness”: indice di “equità” con cui vengono allocate risorse – ancora oggetto di ricerca

Reti di Calcolatori (Fabio Panzieri)

383

Università di Bologna - Corso di Laurea in Informatica

Politiche di gestione delle code: FIFO • Regolano bufferizzazione pkts in attesa di trasmissione e eventuale eliminazione • Allocano bandwidth e buffer – decisione relativa a quali pkts trasmettere e quali scartare

• First-In-First-Out (FIFO)

– Non discrimina fra src’s di traffico – Singola coda contiene pkt’s da varie src’s – Coda piena?

• tail drop policy: prossimo pacchetto indipendentemente dal flusso cui appartiene

ricevuto

viene

scartato

• FIFO con priorità – – – – –

Variazione di FIFO di base Ogni pacchetto marchiato da priorità (p.e., campo TOS in IP hdr) Routers mantengono code multiple con priorità diverse Servono prima code a priorità più alta Problema: “starvation” di code a priorità bassa

Reti di Calcolatori (Fabio Panzieri)

384

192

Università di Bologna - Corso di Laurea in Informatica

Politiche di gestione delle code: FQ • Fair Queuing (FQ)

– Mantiene coda separata per ogni flusso di traffico – Router serve code in round-robin – Se coda di un flusso raggiunge lunghezza max. prefissata

=> tail drop su pacchetti addizionali di quel flusso => FAIRNESS: ogni src non può acquisire maggior capacità di canale a scapito di altre src’s Flow 1

Flow 2 Round-robin service Flow 3

Flow 4

Reti di Calcolatori (Fabio Panzieri)

385

Università di Bologna - Corso di Laurea in Informatica

FQ: osservazioni • FQ

– si limita a gestire risorse (code) separando i flussi di traffico => src’s “dannose” (p.e. troppo veloci) non interferiscono con altre

– non informa src di stato del router, nè ne limita la velocità di trasmissione – richiede meccanismo di CdC end-to-end che regoli velocità di trasmissione dei flussi

• Implementazione

– Per scopi di fairness, deve tenere conto di lunghezza pkts

• P.e. router gestisce 2 flussi – Flusso A: pkts di 1000 B, Flusso B: pkts di 500 B – Servizio round-robin => flusso A ottiene 2/3 della bandwidth disponibile

– Soluzione: round-robin (RR) “bit a bit” • non pratica • FQ simula RR “bit a bit”

Reti di Calcolatori (Fabio Panzieri)

386

193

Università di Bologna - Corso di Laurea in Informatica

Algoritmo FQ •

•

Principio di funzionamento –

Determina istante di terminazione di trasmissione di pkt, se tramesso bit a bit

–

Usa timestamp ottenuto per sequenzializzare pacchetti

Caso di singolo flusso Assunzioni: 1.

Clock avanza di un “tick” ogni volta che un bit è trasmesso da flusso “attivo” (i.e., non vuoto)

2. Pi: lunghezza di pkt I, in bits 3. Si: istante di inizio trasmissione di pkt i 4. Fi: istante di fine trasmissione di pkt i (i.e., time stamp) => Fi = Si + Pi (a causa di condizione 1.)

•

Quando inizia la trasmissione di pkt i?

Reti di Calcolatori (Fabio Panzieri)

387

Università di Bologna - Corso di Laurea in Informatica

Calcolo del time stamp • Se pkt i ricevuto al router prima di fine trasmissione di pkt i-1 da medesimo flusso, allora – i può essere trasmesso immediatamente dopo ultimo bit di pkt i-1 (i.e. al tempo Fi-1) • coda relativa a flusso non vuota, RR trova bit da trasmettere

• Se i ricevuto al router dopo fine trasmissione di i-1 da medesimo flusso, allora – coda relativa a flusso rimasta temporaneamente vuota – RR non ha potuto trasmettere da questa coda per un certo tempo

• In conclusione – se Ai è l’istante di arrivo di pkt i, allora Si = MAX(Fi-1, Ai)

• Quindi: Fi = MAX (Fi-1, Ai) + Pi

Reti di Calcolatori (Fabio Panzieri)

388

194

Università di Bologna - Corso di Laurea in Informatica

Algoritmo FQ • Per flussi multipli – calcola Fi per ogni pacchetto che arriva in ogni flusso – tratta gli Fi’s come timestamp – dà priorità a pkt con timestamp più bassa

• Non perfetto: non effettua preemption di pacchetto in trasmissione (Fig. (b)) • Esempio Flow 1

F=8 F=5

Flow 2

Output

Flow 1 (arriving)

F = 10

Flow 2 (transmitting)

Output

F = 10 F=2 (a)

(b)

Reti di Calcolatori (Fabio Panzieri)

389

Università di Bologna - Corso di Laurea in Informatica

Controllo di congestione in TCP • Approccio in TCP

– inviare pkts in rete, senza prenotazione di risorse – reagire/adattarsi a eventi osservati

• Specificamente, TCP:

– assume rete best-effort (routers FIFO o FQ) – ogni src determina capacità di rete autonomamente • valuta n. di pkts che può mantenere in transito

– src usa ACK da dst come segnale che uno dei suoi pkt ha lasciato la rete (i.e., feedback implicito) • quindi, può trasmetterne un’altro

– ACKs abilitano e regolano trasmissione: TCP è self-clocking

• Difficoltà

– determinare la capacità di canale disponibile – adattarsi a variazioni di capacità di canale disponibile

• Combina tre meccanismi:

– AdditiveIncrease/MultiplicativeDecrease, Slow Start, Fast Retrasmit/ Fast Recovery

Reti di Calcolatori (Fabio Panzieri)

390

195

Università di Bologna - Corso di Laurea in Informatica

Additive Increase/Multiplicative Decrease (AIMD) • •

Obiettivo: adattarsi a variazioni di capacità del canale disponibile Mantiene ulteriore variabile di stato “CongestionWindow” per ogni connessione (simile a AdvertisedWindow per flow control) => N. max. di bytes non ack’ed che src ammette ricalcolato come: MaxWindow = MIN(CongestionWindow, AdvertisedWindow) e il n. max di bytes che src può inviare diviene: EffectiveWindow = MaxWindow - (LastByteSent - LastByteAcked) – limita n. di pkts che src può avere in transito – MaxWindow sostituisce AdvertisedWindow

•

Idea di base: – incrementare CongestionWindow quando congestione cala – decrementare CongestionWindow quando congestione aumenta

Reti di Calcolatori (Fabio Panzieri)

391

Università di Bologna - Corso di Laurea in Informatica

AIMD (segue) •

Individuazione di congestione di rete in TCP – src utilizza timeout – se timeout termina, allora pkt perso

Source

Destination

• pkts raramente persi in seguito a errori di trasmissione • pkts persi implicano congestione (scartati da qualche router)

•

Algoritmo

•

In pratica: incrementa CongestionWindow di “frazione” di MSS ogni volta riceve un ACK

– MSS: Max Segment Size che TCP può inviare senza che IP frammenti specificamente:

…

– incrementa CongestionWindow di 1 pkt per RTT (additive increase lineare) – divide CongestionWindow per 2 quando si verifica timeout (multiplicative decrease)

Increment = MSS * (MSS/CongestionWindow) CongestionWindow += Increment Reti di Calcolatori (Fabio Panzieri)

392

196

Università di Bologna - Corso di Laurea in Informatica

Slow Start • •

Obiettiv o : determinare rapidamente capacità del canale disponibile Principio: – –

Inizia con CongestionWindow = 1 pkt Raddoppia CongestionWindow ad ogni RTT

–

Se si verifica perdita “multiplicative decrease”

–

Utilizzo di Slow Start

Source

Destination

≠ “additive increase”: incrementa di 1 pkt per ogni RTT

di

pkt

(i.e.,

timeout),

applica

i.e. CongestionWindow = CongestionWindow/2 • •

…

•

in fase di attivazione di connessione quando connessione “bloccata” da pkt perso, e src sbloccata da time out quando src riceve ACK cumultativo che riapre intera “advertised window”

Reti di Calcolatori (Fabio Panzieri)

393

Università di Bologna - Corso di Laurea in Informatica

Fast Retransmit e Fast Recovery •

Sender

Problema – time out in TCP comportano che connessioni entrino in stato di “idle” per lunghi periodi

•

Fast Retransmit – usa ACKs duplicati per abilitare ritransmissioni prima della terminazione dei time out

Packet 2 Packet 3

ACK 1

Packet 4

ACK 2

Packet 5

ACK 2

Packet 6

– non elimina time out •

ACK 2

Principio di funzionamento – Pkt fuori ordine => TCP(rcv) non può inviare ACK finchè non arrivano pkts precedenti – TCP(rcv): ri-invia ultimo ACK trasmesso (duplicate ACK) – TCP(src): riceve duplicate ACK e sospetta perdita o ritardo di pkt trasmesso – Se TCP(src ) riceve ritrasmette pkt

Reti di Calcolatori (Fabio Panzieri)

Receiver

Packet 1

3

duplicate

ACK 2 Retransmit packet 3 ACK 6 (cumulativo di 4 e 5)

ACK , allora

394

197

Università di Bologna - Corso di Laurea in Informatica

Fast Recovery • Evita fase di slow-start quando Fast Retrasmit individua perdita di pkt • Riparte con CongestionWindow = CongestionWindow/2

e riavvia AIMD • In conclusione: – Slow start usato in fase di connection establishment – In altri casi, CongestionWindow gestita via AIMD

Reti di Calcolatori (Fabio Panzieri)

395

Università di Bologna - Corso di Laurea in Informatica

Nomi & Indirizzi in Internet • Nomi: e.g. maddalena.cs.unibo.it – identificatore mnemonico di risorsa (p.e., computer) • facile da ricordare per un essere umano • riflette struttura organizzativa

• Indirizzi: p.e., 130.136.5.6 – etichette utilizzabili convenientemente da programmi in esecuzione nei router – conformi alla struttura della rete

• Come avviene il mapping di uno nell’altro? – Domain Name System (DNS)

Reti di Calcolatori (Fabio Panzieri)

396

198

Università di Bologna - Corso di Laurea in Informatica

Esempio • Mailboxes User 1 [email protected]

2 cs.unibo.it Name server

Mail program 130.136.1.110

130.136.1.110 3

4

TCP 130.136.1.110

5

IP

Reti di Calcolatori (Fabio Panzieri)

397

Università di Bologna - Corso di Laurea in Informatica

DNS: Storia • Inizialmente: mapping host<->addess mantenuto nel file hosts.txt (in /etc/hosts di ogni host in rete) – “spazio dei nomi” non strutturato (i.e., flat) • spazio dei nomi: insieme dei nomi utilizzabili

– Amministratori di rete sceglievano nomi hosts a loro discrezione – Cambiamenti venivano comunicati a network Information Center (NIC) via email – Nuove versioni di hosts.txt trasmesse via ftp da NIC periodicamente

• Al crescere di Internet il sistema non funzionò più: – NIC non poteva sostenere il carico – Nomi non erano unici – Hosts avevano copie non coerenti di hosts.txt

• La crescita di Internet era messa a rischio – fu introdotto il Domain Name System (DNS)

Reti di Calcolatori (Fabio Panzieri)

398

199

Università di Bologna - Corso di Laurea in Informatica

DNS: Caratteristiche di Base • Spazio dei nomi gerarchico anzichè “flat” – aumenta scalabilità dello spazio di nomi

• Architettura distribuita, anzichè centralizzata – aumenta sia la scalabilità che le garanzie di continuità del servizio

• Interazione client-server via Porta UDP # 53 – ma può essere configurato ad usare TCP se richiesto

Reti di Calcolatori (Fabio Panzieri)

399

Università di Bologna - Corso di Laurea in Informatica

Gerarchia di nomi root

edu

berkeley

mil

org

net

uk

mit

sims

argus

Reti di Calcolatori (Fabio Panzieri)

it etc.

unibo •

eecs

gov

com

strutturata ad albero – –

• • •

nodi: radici di sotto-domini, foglie: hosts

deis

profondità dell’albero è arbitraria (max 128) domini: sottoalberi – P.e.: .it, unibo.it, cs.unibo.it unicità dei nomi limitata al singolo sotto-dominio – P.e. maddalena.cs.unibo e maddalena.deis.unibo coesistere

cs maddalena

possono

400

200

Università di Bologna - Corso di Laurea in Informatica

Nomi di hosts amministrati gerarchicamente root

edu

mit

berkeley eecs

gov

com

sims

mil

org

net

uk

•

zona: porzione della gerarchia di responsabilità di una particolare autorità amministrativa

•

zona eecs controla i nomi

•

zona berkeley controlla i nomi:

fr

x.eecs.berkeley.edu

x.berkeley.edu y.sims.berkeley.edu

argus

Reti di Calcolatori (Fabio Panzieri)

401

Università di Bologna - Corso di Laurea in Informatica

Gerarchia di Server • Ogni server ha autorità su una zona – ogni server mantiene solo un sottoinsieme di tutti i nomi

• Ogni server mantiene tutti i records per gli hosts della sua zona – può essere replicato per scopi di robustezza

• Ogni server conosce l’indirizzo di qualche altro server, responsabile di altre zone – Ogni server conosce l’indirizzo del server “radice” (controllato dal NIC) – Il server radice può indirizzare i domini di livello più alto

Reti di Calcolatori (Fabio Panzieri)

402

201

Università di Bologna - Corso di Laurea in Informatica

DNS Name Servers

• Locale: – Ogni ISP (compagnia) ha un name server locale di default – Host DNS query indirizzata a name server locale prima di altri

• “Authoritative”: – per un host: mantiene mapping per quell host – Può eseguire risoluzione del nome di quellhost nel suo indirizzo IP

Reti di Calcolatori (Fabio Panzieri)

403

Università di Bologna - Corso di Laurea in Informatica

DNS: Root Name Servers •

una dozzina di root name servers sparsi per il mondo

•

contattati da name server locali non in grado di risolvere un nome Root name server:

•

– contatta name server “authoritative” per quel nome, se non è in grado di risolverlo autonomamente – ottiene indirizzo IP – invia IP a name server locale

Reti di Calcolatori (Fabio Panzieri)

404

202

Università di Bologna - Corso di Laurea in Informatica

Strategie di risoluzione dei

• “forward” • iterativa • ricorsiva • Server locale – deve conoscere indirizzo di un root server (non ogni host)

Reti di Calcolatori (Fabio Panzieri)

405

Università di Bologna - Corso di Laurea in Informatica

Esempio di interrogazione “forward”

Host maddalena.cs.unibo.it richiede indirizzo IP di www.berkeley.edu

1. contatta DNS server locale, ns. ns.cs.unibo.it 2. ns.cs.unibo.it contatta root name server, se necessario 3. Root name server contatta “authoritative” name server, ns1.berkeley.edu, se necessario N.B.: se necessario = non è in grado di risolvere nome in indirizzo IP

root name server

2 5

4

name server locale authorititive name server ns.cs.unibo.it

1

ns1.berkeley.edu

6

host richiedente maddalena.cs.unibo.it Reti di Calcolatori (Fabio Panzieri)

3

www.berkeley.edu 406

203

Università di Bologna - Corso di Laurea in Informatica

Esempio di Interrogazione Ricorsiva root name server

Root name server: • •

può non conoscere name server “authoritative” può conoscere name server intermedio: chi contattare in caso non si conosca il name server “authoritative”

Interrogazione ricorsiva: •

impone carico della risoluzione del nome in indirizzo sul name server contattato

•

rischio di sovraccarico?

Alternativamente ...

2

6 7

3

local name server ns.cs.unibo.it 1

name server intermedio (edu server) 5 4

8

name server “authoritative” ns1.berkeley.edu

requesting host maddalena.cs.unibo.it

www.berkeley.edu Reti di Calcolatori (Fabio Panzieri)

407

Università di Bologna - Corso di Laurea in Informatica

Esempio di Interrogazione Iterativa root name server

Interrogazione Iterativa: •

nel caso server contattato non sia in grado di risolevere nome, invia al richiedente nome di server alternativo da contattare i.e.“non conosco questo nome, prova a chiedere a quest’altro server”

iterated query

2 3

4 5 name server intermedio (edu server)

name server locale ns.cs.unibo.it 1

8

host richiedente maddalena.cs.unibo.it

6

7

name server “authoritative” ns1.berkeley.edu

www.berkeley.edu Reti di Calcolatori (Fabio Panzieri)

408

204

Università di Bologna - Corso di Laurea in Informatica

DNS Records • Ogni DNS server mantiene records di 4 campi: • Type = A: name = nome host; value = indirizzo IP • Type = NS: name = dominio; value = nome di server DNS per quel dominio • Type = CNAME: name = hostname; value = nome canonico (alias) • Type = MX: name = dominio in indirizzo email; value = nome canonico di mail server • TTL: time to live associato a record Reti di Calcolatori (Fabio Panzieri)

409

Università di Bologna - Corso di Laurea in Informatica

dig cs.unibo.it ;; AUTHORITY SECTION: cs.unibo.it. cs.unibo.it. cs.unibo.it.

432000 432000 432000

IN IN IN

NS NS NS

leporello.cs.unibo.it. simon.cs.cornell.edu. dns2.nic.it.

;; ADDITIONAL SECTION: leporello.cs.unibo.it. simon.cs.cornell.edu. dns2.nic.it.

345600 27773 14500

IN IN IN

A A A

130.136.1.110 128.84.154.10 193.205.245.8

;; AUTHORITY SECTION: unibo.it. unibo.it. unibo.it.

86400 86400 86400

IN IN IN

NS NS NS

dns.cineca.it. dns2.cineca.it. almadns.unibo.it.

;; ADDITIONAL SECTION: dns.cineca.it. dns2.cineca.it. almadns.unibo.it.

364 364 432000

IN IN IN

A A A

130.186.1.53 130.186.1.9 137.204.1.15

dig unibo.it

Reti di Calcolatori (Fabio Panzieri)

410

205

Università di Bologna - Corso di Laurea in Informatica

dig it ;; AUTHORITY SECTION: nic.it. nic.it. nic.it. nic.it.

43252 43252 43252 43252

IN IN IN IN

NS NS NS NS

itgeo.mix-it.net. nameserver.cnr.it. dns.nic.it. dns2.nic.it.

;; ADDITIONAL SECTION: itgeo.mix-it.net. nameserver.cnr.it. dns.nic.it. dns.nic.it. dns2.nic.it.

2353 23854 7684 64136 13552

IN IN IN IN IN

A A AAAA A A

217.29.76.5 194.119.192.34 2001:760:600:1::5 193.205.245.5 193.205.245.8

Reti di Calcolatori (Fabio Panzieri)

411

Università di Bologna - Corso di Laurea in Informatica

DNS: servizio di ri-direzionamento • Consente di identificare hosts per nome, anzichè indirizzo – non solo comodo per esseri umani (facile da ricordare) – consente anche di cambiare indirizzo IP a hosts senza dover cambiare modo di identificarli (anche da programma)

• Consente di identificare host mediante “alias” – www.berkeley.edu può identificare un server Web generico – DNS risolve questo nome nell’indirizzo IP di un host particolare che può cambiare nel tempo

• Questa flessibilità vale solo all’interno del singolo dominio!

Reti di Calcolatori (Fabio Panzieri)

412

206

Università di Bologna - Corso di Laurea in Informatica

Osservazioni conclusive • Caching – aumenta prestazioni salvando risultati di precedenti ricerche in memoria cache • N.B.: TTL può causare problemi di sovraccarico in conseguenza della struttura gerarchica del DNS, e del caching

• Principio di delega amministrativa a singoli domini, e architettura distribuita: – riducono complessità nella generazione di nomi unici – inducono “condivisione della sorte” fra gli hosts all’interno del medesimo dominio in caso di guasti di rete

Reti di Calcolatori (Fabio Panzieri)

413

Università di Bologna - Corso di Laurea in Informatica

World Wide Web •

WWW: esempio di sistema Client-Server distribuito su larga scala – descrizione dell’architettura del WWW – analisi dei pro’s e con’s di questa architettura alla luce di quello che abbiamo studiato

•

Nota storica su Internet – DoD USA finanzia progetto di ricerca su reti a commutazione di pacchetto (PSN) agli inizi degli anni ‘70 (ARPAnet Project) – fine anni ‘70: PSNs di vari paesi interconnesse via routers e gateways (nasce Internet) – Internet Society (organizzazione internazionale) responsabile per assegnare “indirizzi di Internet” a computers che si connettono. Name servers (Domain Name Servers, DNSs) mappano “nomi” (stringhe di caratteri), e.g. leporello.cs.unibo.it, in “indirizzi di Internet”, e.g. 130.136.2.204.

Reti di Calcolatori (Fabio Panzieri)

414

207

Università di Bologna - Corso di Laurea in Informatica

Nota storica

• Tutti gli elaboratori ospiti in Internet utilizzano protocolli standard per scambio di informazione: – UDP: messaggio inviato senza ack da ricevente (servizio datagram) – TCP: trasmissione affidabile e consegna in sequenza di messaggi

• connessione stabilita fra src e dst , msgs trasmessi con ack da dst, terminazione di connessione.

• Utenti iniziali di Internet: comunità accademiche (email, ftp applicazioni principali). • Introduzione di “News groups” e “Bulletin Boards” estendono le classi di utenza. • Inizio anni ‘80: Tim berners-Lee e colleghi al CERN (centro europeo di ricerca su fisica delle particelle) sviluppano varie applicazioni che supportano lavoro collaborativo per la comunità dei ricercatori in fisica. Queste applicazioni si affermano a livello internazionale come WWW. • Oggi, WWW si sta sviluppando come infrastruttura di supporto a sistemi di commercio elettronico, insegnamento, intrattenimento, …

Reti di Calcolatori (Fabio Panzieri)

415

Università di Bologna - Corso di Laurea in Informatica

Architettura del WWW • WWW consiste di varie componenti: – Programmi cliente (e.g. Netscape Browser, Apple Safari, ...) – WWW Servers (HTTP Servers o HTTP Demons) che mantengono dati scritti in linguaggio HTML (HyperText Markup Language) – Servers mantengono pagine in formato HTML; pagine sono consegnate a clienti usando HTTP (HyperText Transfer Protocol) – Browser mostra testo HTML in un formato familiare a tutti (links ipertestuali sono sottolineati)

• P.E. il codice HTML che implementa University of Bologna nella home page del nostro Dipartimento di Scienze dell’Informazione è: il testo in "…"è un URL (Uniform Resource Locator), i.e. il nome di una risorsa. Il Browser individua la risorsa e ne fa il rendering sul display se uno “clicka” University of Bologna .

Reti di Calcolatori (Fabio Panzieri)

416

208

Università di Bologna - Corso di Laurea in Informatica

Architettura del WWW • •

Vantaggio principale di un browser: può utilizzare un ampio n. di protocolli differenti, quindi può contattare un ampio n. di servers differenti Protocolli usati da browser includono: http, ftp (per file transfer), telnet (per login remoto), …

P.E.: URL di server che usa ftp (rapporti tecnici del Dipartimento)

ftp://ftp.cs.unibo.it/pub/techreports/93-22.ps.gz

protocollo

nome host

directory

file

Reti di Calcolatori (Fabio Panzieri)

417

Università di Bologna - Corso di Laurea in Informatica

WWW Server • Processo applicativo eseguito su elaboratore – attende richieste di connessione da clienti su porta TCP (porta di default: # 80) – usa HTTP (che a sua volta usa TCP per trasmissione messaggi) – Contenuto dei messaggi: rappresentato in MIME • MIME (Multiporpose Internet Mail Extension): standard di email per inviare posta elettronica multimediale

– Uso di MIME: consente al ricevente l’uso di applicazioni adeguate per trattare l’informazione ricevuta – Tipi di messaggi MIME più comunemente usati da WWW: • contenuto di tipo text – text/plain: testo senza particolari requisiti di formattamento – text/html: testo contenente istruzioni HTML • contenuto di tipo image: – image/gif: un immagine in formato GIF

Reti di Calcolatori (Fabio Panzieri)

418

209

Università di Bologna - Corso di Laurea in Informatica

HTTP (V1.0) • HTTP V1.0: – protocollo prima versione (ancora in uso) – di tipo RPC client-server – server è “stateless” (i.e. non mantiene stato della richiesta dopo averla servita) – fasi di esecuzione di un comando HTTP: • connessione: Cliente stabilisce una connessione TCP con Server, identificato dall’URL nel comando P.E. open ftp://ftp.cs.unibo.it/pub/techreports • richiesta: richiesta di servizio inviata dal Cliente al Server • risposta: Cliente riceve la risposta dal Server • terminazione: Cliente o Server chiudono la connessione Reti di Calcolatori (Fabio Panzieri)

419

Università di Bologna - Corso di Laurea in Informatica

Esempio Client Establish connection Client request Request response

TCP Syn

Server

TCP syn + ack TCP ac k+

HTTP GET

.. .

Close connection

Reti di Calcolatori (Fabio Panzieri)

420

210

Università di Bologna - Corso di Laurea in Informatica

Osservazioni • Servers WWW – implementano un insieme prefissato di operazioni – operazioni sono codificate all’interno del protocollo HTTP – operazioni includono • GET: ottiene la risorsa identificata dall’URL • HEAD: simile a GET, ritorna però solo gli headers HTML • PUT: carica i dati all’URL specificato

• Protocolli di RPC “tradizionali” – combinati con generatori di stubs possono essere usati per invocare qualunque operazione implementata da un server – non esiste compilatore di stubs per HTTP – protocollo di RPC usato in HTTP è per uso esclusivo con servers WWW – se server deve essere esteso con nuove operazioni, anche il protocollo HTTP deve essere esteso

Reti di Calcolatori (Fabio Panzieri)

421

Università di Bologna - Corso di Laurea in Informatica

Scripts di Server

• WWW non limitato a ricerca di files HTML. Cliente può richiedere a server di eseguire particolari programmi applicativi (principio di funzionamento delle “mappe attive”). Realizzato mediante CGI (Common Gateway Interface. • In sostanza, server mantiene un certo numero di programmi applicativi e Shell Scripts per la loro esecuzione. Cliente può usare CGI per impartire direttive al server per eseguire questi scripts, fornendo gli opportuni parametri • P.E. Invio di richiesta GET con URL: http://www.unibo.it/cgi-bin/htimage/usr/www/img/bolognamap?450,451

– WWW Server usa convenzione che se URL contiene nome cgi-bin allora l’URL deve essere interpretato per eseguire un programma – Server effettua “fork” di processo che esegue shell script htimage e usa il resto del pathname come parametri

Reti di Calcolatori (Fabio Panzieri)

422

211

Università di Bologna - Corso di Laurea in Informatica

Proxy di Servers •

Proxy Server: – server programmabile ad agire da cache per ridurre il traffico di rete al server di origine – fornisce informazione da un suo cache interno – richieste cliente consegnate a Proxy Server – se risorse richieste non disponibili in cache di Proxy, questo ne effettua fetching da Server di origine N.B. Web caching: problema di ricerca; meccanismo principale di minimizzazione del carico dei Web Servers

WWW Client Proxy Server

WWW Client

Web Server

WWW Client Reti di Calcolatori (Fabio Panzieri)

423

Università di Bologna - Corso di Laurea in Informatica

Alcuni problemi di WWW • Popolarità di WWW: chiara indicazione del fatto che gli utenti lo trovano facile da usare e comodo/utile per condividere informazione • Richiede miglioramenti: – Problemi con il protocollo HTTP/1.0 (versione in uso): affrontati in HTTP/1.1 – Problemi con l’architettura generale di WWW e come si può migliorare

• Vantaggio principale di HTTP/1.0: SEMPLICITA’ – servers non mantengono stato. Relativamente facili da costruire. Con ampio numero di clienti è importante minimizzare la necessità di mantenere stato (i.e. chi sta facendo cosa). – Approccio HTTP: aprire e chiudere una nuova connessione TCP per ogni risorsa URL richiesta dal cliente – Uso di TCP implica: HTTP non deve gestire (i) perdita di messaggi, o delivery fuori sequenza, (ii) problemi di congestione di Internet (se ne preoccupa TCP)

• Caratteristiche precedenti limitano scalabilità di HTTP all’aumentare dei clienti Reti di Calcolatori (Fabio Panzieri)

424

212

Università di Bologna - Corso di Laurea in Informatica

Problemi di WWW

• Fetching di pagina Web: può richiedere fetching di varie risorse URL (di testo e immagini). E’ comune che cliente effettui diverse richieste a un Web server in rapida successione. Ogni richiesta crea e chiude (i.e. connect, disconnect) una nuova connessione TCP

– connessione/disconnessione: operazione costosa in termini di carico computazionale, memoria, numero di messaggi. Se effettutata frequentemente, aumenta il carico del Server e causa congestione di rete. – TCP, quando individua congestione di rete, riduce il tasso di trasferimento messaggi – effetto al cliente: server lento.

• Come evitare questi problemi e implementare servers scalabili: – ridurre la necessità di creare molte connessioni • uso di connessioni persistenti

– ridurre le richieste di accesso a servers •

• uso di proxy di servers e caching

N.B. Necessario implementare quanto sopra (significativamente) la complessità del protocollo HTTP

senza

aumentare

Reti di Calcolatori (Fabio Panzieri)

425

Università di Bologna - Corso di Laurea in Informatica

Connessioni persistenti in HTTP/1.1 • HTTP/1.1: nuova versione di HTTP prodotta da HTTP WG, organizzato da Internet Society e WWW Consortium (cf. http://www.w3.org/ per il draft report) • Connessioni persistenti: cliente usa la medesima connessione TCP con server per inviare molteplicità di richieste • Vantaggi: – aprendo un minor n. di connessioni si risparmia memoria e tempo di CPU – molteplicità di richieste HTTP possono essere inviate da cliente a server in pipeline sulla medesima connessione. Pipelining consente al cliente di inviare molteplicità di richieste senza attendere ogni singola risposta; ne consegue un uso più efficiente della connessione – possibilità di congestione di rete viene ridotta

Reti di Calcolatori (Fabio Panzieri)

426

213

Università di Bologna - Corso di Laurea in Informatica

Connessioni persistenti in HTTP/1.1 Principio operativo • cliente – apre connessione con server e la chiude esplicitamente solo quando non richiede più il server

• server – controlla connessione aperta con un cliente mediante un timeout – Se il timeout termina senza che siano state ricevute richieste dal cliente, allora server chiude connessione N.B.: semplice meccanismo che assicura che le connessioni vengono chiuse anche in caso di crash cliente o disconnessione per guasto di comunicazione

• cliente – deve essere in grado di gestire server che chiude connessione e, in caso, aprire nuova connessione per continuare

Reti di Calcolatori (Fabio Panzieri)

427

Università di Bologna - Corso di Laurea in Informatica

Caching in HTTP/1.1 • •

Obiettivo: ridurre il carico sul server e migliorare il tempo di risposta Attualmente HTTP/1.0: – supporta la creazione di proxy che mantengono copie in cache di risorse URL – non fornisce supporto per garantire che il cache di proxy contenga la versione più recente della risorsa URL (si assuma che il contenuto informativo di una risorsa può cambiare) => cliente non protetto dal ricevere copie non aggiornate della risorsa

• •

Si richiede: meccanismo a basso overhead che assicuri che il cache mantenga sempre la versione più recente di una risorsa Approccio in HTTP/1.1: parte di questa responsabilità delegata a livello superiore del fornitore di informazione (p.e. proprietario della risorsa URL, fornitore del contenuto della risorsa URL)

Reti di Calcolatori (Fabio Panzieri)

428

214

Università di Bologna - Corso di Laurea in Informatica

Caching in HTTP/1.1 • In HTTP/1.1 una risposta da cache è definita corretta se soddisfa una delle seguenti condizioni: – è stata controllata con quella del server di origine ed è uguale • accettabile in quanto un cache può convalidare la sua copia di informazione con quella del server di origine

– è “sufficientemente attuale” , dove il concetto di “attuale” è specificato dal gestore della risorsa URL • accettabile in quanto i servers possono fornire stime su quanto recenti sono le loro risorse URL

– contiene un qualche avviso (eccezione) se non soddisfa il requisito di “sufficientemente attuale” • accettabile in quanto il cliente almeno è informato della possibilità che abbia ottenuto informazione non aggiornata

Reti di Calcolatori (Fabio Panzieri)

429

Università di Bologna - Corso di Laurea in Informatica

Determinare se copia in cache è “attuale” • Attività di caching è più efficiente se cache può evitare di controllare con il server d’origine l’età delle proprie copie. • Meccanismo principale (assume orologi sincronizzati => letture di clock consistenti globalmente ): – ogni server d’origine attribuisce un data_di_morte ad ogni risorsa URL che indica fino a quando la risorsa rimane attuale (data_di_morte: definito dal fornitore di informazione) – server d’origine invia Date Header con ogni risposta, indicando il tempo (data_di_nascita) a cui la risposta è stata generata – Cache calcola età_attuale e margine_di_vita di una risorsa:

età_attuale = valore_attuale_del_clock - data_di_nascita margine_di_vita = data_di_morte - data_di_nascita – risorsa in cache è attuale se

margine_di_vita > età_attuale

Reti di Calcolatori (Fabio Panzieri)

430

215

Università di Bologna - Corso di Laurea in Informatica

Validazione di risorse “obsolete” • Cache deve inviare risorsa in una risposta – se scopre che risorsa non è attuale, allora controlla con il server d’origine se la risorsa è ancora utilizzabile

• Sever d’origine deve associare un validatore con ogni risorsa, p.e.: – validatore: data dell’ultima modifica – validatore: numero di versione

• Cache invia al server il valore del validatore della risorsa che mantiene

Reti di Calcolatori (Fabio Panzieri)

431

Università di Bologna - Corso di Laurea in Informatica

Validazione di risorse “obsolete” • Server controlla l’ ”attualità” del valore del validatore ricevuto confrontandolo con il valore corrente del validatore della risorsa richiesta, e invia una nuova copia della risorsa, se necessario • Cliente aggiorna risorsa: cache deve aggiornare risorsa su server d’origine – N.B. non assicura che tutti gli altri cache contenenti quella risorsa siano aggiornati automaticamente: non pratico in sistemi distribuiti su larga scala (o per lo meno non vi sono ancora soluzioni accettabili) => Schema di caching in HTTP/1.1: ottimizzato per aggiornamenti di informazione da parte del fornitore Reti di Calcolatori (Fabio Panzieri)

432

216

Università di Bologna - Corso di Laurea in Informatica

WWW: problemi architetturali • Due problemi principali: – URLs: nomi a basso livello,dipendenti dalla locazione fisica => spostare fisicamente una risorsa URL provoca rottura dei links

– WWW non è facilmente estendibile

• Difficoltà di estendere WWW – progettato principalmente per trattare documenti iper-testuali basati su files read-only (risorse standard) – risorse non standard trattate da meccanismi “ad hoc” via scripts CGI – scrivere script CGI non è banale. Non vi è supporto per controllo di concorrenza. Utenti tendono ad adottare politiche ad hoc per ottenere persistenza di, e controllo di concorrenza su, risorse – HTTP è un protocollo di RPC per invocare un insieme predefinito di operazioni. Aggiungere nuove operazioni richiede re-implementazione dei servers HTTP N.B.: tutto ciò si poteva evitare usando tecniche note (cf. seguito)

Reti di Calcolatori (Fabio Panzieri)

433

Università di Bologna - Corso di Laurea in Informatica

WWW: problemi architetturali • Soluzioni: – RPC: protocollo per invocare operazioni generiche (i.e. non vi è un set di operazioni prefissato cui è associato il protocollo di RPC) – Le risorse definiscono le operazioni ad esse applicabili in un IDL – Dall’IDL si possono generare stubs di cliente e server usando generatori di stub (come in RPC) – In tal modo si ottiene un metodo uniforme per trattare risorse arbitrarie (inclusi meccanismi come Azioni Atomiche per l’integrità dei dati) – Questa soluzione è estendibile: nuove risorse possono essere aggiunte, con nuove operazioni, senza dover modificare il protocollo di RPC, ne usare soluzioni ad hoc come gli script CGI

Reti di Calcolatori (Fabio Panzieri)

434

217

Università di Bologna - Corso di Laurea in Informatica

WWW: problemi architetturali • Troppo tardi per applicare questo approccio a WWW – architettura attuale ormai consolidata in prodotti – non pratico introdurre modifiche fondamentali all’architettura WWW

• Possibile consentire interazione di WWW con sistemi object oriented, in modo che WWW possa sfruttare i vantaggi di questa tecnologia

Reti di Calcolatori (Fabio Panzieri)

435

218