M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 1

Capitolo 5 - parte 2

Corso Reti ed ApplicazioniAndrea Pini

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 2

A

RB

• In un router c’è una tablella ARP per ciascuna rete IPa cui è connesso

ARP e routing

• Spedire un datagramma da A a B attraverso un router R• A conosce l’indirizzo IP di R

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 3

A

RB

• A crea un datagramma IP con sorgente A e destinazione B• Nella sua tabella di routing, A individua il router:

111.111.111.110• A usa ARP per ottenere il MAC address di 111.111.111.110• A crea un frame di livello 2 con il MAC address di R come

destinazione, il frame continene il datagramma IP da A a B• Il livello data link di A invia il frame

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 4

A

RB

• Il livello data link di R riceve il frame• R rimuove il datagramma IP dal frame Ethernet, vede che è

destinato a B• R guarda la sua tabella di routing per instadare il datagramma

-> B è direttamente connesso• R usa ARP per ottenere il MAC address per B• R crea un frame di livello 2 con destinazione il MAC address di

B. Il frame contiene il datagramma IP da A a B. R lo invia

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 5

Lo schizzo originaledi Metcalfe per

Ethernet

Ethernet• La tecnologia LAN dominante - perché:• Economica: 10€ per 100Mbs!• Più diffusa tecnologia LAN• Più semplice ed economica di token ring e ATM• Scelta della velocità :

• 10, 100, 1000, 10000 Mbps

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 6

L’adattatore che spedisce incapsula i datagrammi IP(o di altri protocolli di rete) in un frame Ethernet

Preambolo:• 7 bytes con il pattern 10101010 seguiti da un byte con il

pattern 10101011 (Usato per sincronizzare i clock degliadattatori)

• Tipo: indica il protocollo di livello superiore,soprattutto IP, ma anche Novell IPX o AppleTalk

Struttura del Frame Ethernet

8 6 6 246-1500

(incluso padding) 4

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 7

Struttura del Frame Ethernet (2)

Indirizzi: 6 bytes• Se l’adattatore riceve un frame con il proprio indirizzo

MAC come destinazione, oppure con indirizzodestinazione broadcast (es: ARP packet), passa ilcontenuto del frame al protocollo di rete

• Altrimenti scarta il frameCRC: controllato dal ricevitore, se viene rilevato un errore il frame è scartato senza avvertire, né l’host, né l’altro adattatore

Protocollo semplice implementato in HW8 6 6 2 46-1500 2

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 8

Modello di servizio di Ethernet

• Connectionless: l’adattatore che spedisce e quello chericeve non stabiliscono una connessione

• Inaffidabile: l’adattatore che riceve non manda ack onack a quello che spedisce È possibile che vengano persi pacchetti di livello

rete Saranno recuperati se l’applicazione usa TCP,

oppure se autonomamente garantiscel’affidabilità

Altrimenti l’applicazione subirà una perdita di dati

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 9

Ethernet usa CSMA/CD

• Il tempo non è diviso in slot e quindi non è necessariosincronizzare globalmente i clock degli adattatori

• frame di lunghezza variabile• Ciascun adattatore inizia a trasmettere

indipendentemente - accesso casuale• Un adattatore non trasmette se sente che qualcun’altro

sta trasmettendo - carrier sense• il mezzo è condiviso (multiple access)• Un adattatore che sta trasmettendo si ferma quando si

accorge che un altro adattatore ha iniziato a trasmettere- collision detection- Dopo una collisione, un adattatore aspetta un tempo

casuale prima di riprovare a trasmettere

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 10

L’algoritmo CSMA/CD di Ethernet• Un adattatore riceve un datagramma dallo strato

superiore e crea il frame• Se sente che il canale è libero, inizia a trasmettere il

frame; se è occupato aspetta che sia libero e poitrasmette

• Se rileva una collisione durante la trasmissione, si fermaed invia il segnale di JAM (per aiutare l’altro adattatore arilevare la collisione)

• Dopo una collisione, entra nello stato di backoffexponenziale: dopo la m-esima collisione, l’adattatoresceglie un numero casuale K tra 0 e 2m-1, e aspettaK*512 bit times prima di ritrasmettere

• Quando è riuscito a trasmettere tutto il frame senzacollisioni, considera il frame trasmesso con successo

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 11

L’algoritmo CSMA/CD di Ethernet (2)

Segnale di JAM:garantisce che tutti glialtri trasmettitori rilevinola collisione - 48 bits;

Bit time: 0,1 microsec per10 Mbps Ethernet;per m=10, l’attesa ècirca 50 msec

Dopo 10 collisionil’adattatore rinuncia allatrasmissione

backoff exponenziale:scopo: adattare i tentativi di

ritrasmissione al caricosotto forte carico le attesesaranno più lunghe

• Prima collisione: sceglie Kin {0,1}; il ritardo è K x512 bit times

• Dopo la seconda collisione:{0,1,2,3}…

• Dopo 10 collisioni,{0,1,2,3,4,…,1023}

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 12

Algoritmo MAC per Ethernet

// In attesa Ricezione un pacchetto dallo strato superiore;K := 0; n :=0; // K: random wait time; n: no. di collisionirepeat: wait for K * 512 bit-time; while (network busy) wait; wait for 96 bit-time after detecting no signal; // 96 bit è l’interframe gap o interpacket time transmit and detect collision; if {detect collision} stop and transmit a 48-bit jam; n ++; m:= min(n, 10) // n è il numero delle collisioni {scegli K a caso da {0, 1, 2, …, 2m-1}} if n < 16 goto repeat else giveup

CSMA/CD e backoff esponenziale

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 13

• Tprop = massimo tempo di propagazione tra 2 nodi• Ttrans = durata della trasmissione del frame di

dimensione massima

• L’efficienza tende a 1, se Tprop tende a 0 (è immediato ilriscontro di collisioni con minore perdita tempo)

• L’efficienza tende a 1, se Ttrans tende a infinito (unavolta catturato il canale è bene usato)

• Molto meglio di ALOHA, ma sempre decentralizzato,semplice ed economico

Efficienza di CSMA/CD

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 14

Technologie Ethernet : 10Base2

• 10: 10Mbps; 2: lunghezza del cavo fino a 200 metri• Cavo coassiale sottile, topologia a bus

• Si usano ripetitori per connettere più segmenti• I ripetitori copiano i bit che leggono su una interfaccia su

tutte le altre interfacce: sono dispositivi di livello fisico• Tecnologia ormai obsoleta

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 15

• Velocità di 10/100 Mbps; 100Mbps è “fast ethernet”• T: Twisted Pair (fili di rame in doppini incrociati)• I nodi sono connessi ad un hub: “topologia stellare”; max

distanza tra nodi e hub: 100 m• Gli hub sono ripetitori di livello fisico:

• I bit che arrivano su una interfaccia vengono ripetuti su tutte le altre

• Non c’è buffering dei frame• Gli hub non implementano CSMA/CD: sono gli adattatori

a riconoscere le collisioni• Funzionalità degli hub per la gestione della rete:

monitoraggio ed isolamento nodi malfunzionanti

hub

Nodi

10BaseT e 100BaseT

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 16

Codifica Manchester

• Usata in 10BaseT e 10Base2• Ogni bit ha una transizione• Permette ai clock del miittente e del destinatario di

sincronizzarsi• Non serve un clock centralizzato

• È una funzionalità di livello fisico

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 17

Gbit Ethernet

• Usa il formato di frame standard Ethernet• Collegamenti punto-punto o canali condivisi• in “shared mode” usa CSMA/CD

• per essere efficente, su rame le distanze tra i nodidevono essere modeste

• esistono dispositivi simili agli hub, chiamati “BufferedDistributors”, ma soprattutto si usano switch• Se il canale è occupato, possono immagazzinare

frame sulle porte di ingresso• Collegamenti punto-punto sono Full-Duplex a 1Gbps• Già disponibile 10 Gbps Ethernet

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 18

• Bridge• livello data link• Copiano i frame• Filtrano i frame e li

inoltranoselettivamente

• Separano i domini dicollisione

• Full duplex• Tecnologie eterogenee

• Switch• bridge con molte porte

Connettere i segmenti di LAN

• Ripetitori• livello fisico• Copiano i bit• Inoltrano tutto su tutte le

interfacce• Uniscono i domini di

collisione• Half duplex• Singola tecnologia

ethernet• Hub

• ripetitori con molte porte

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 19

Interconnettere con gli HUB

• Un hub di backbone connette diversi segmenti di LAN• Rigenera il segnale• Estende la distanza massima tra i nodi e il numero di nodi• ma: I domini di collisione vengono uniti

• se un nodo in CS e uno in EE trasmettonocontemporaneamente si ha collisione

• la banda disponibile è condivisa tra tutti i dipartimenti• Non si possono interconnettere 10BaseT & 100BaseT

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 20

Bridge

• Dispositivo di livello di data link• memorizza e inoltra frame Ethernet• esamina l’intestazione del frame

– Usa il MAC address sorgente per imparare su qualeporta risiede un adattatore

– inoltra selettivamente i frame basandosi sul MACaddress di destinazione

• Quando deve inoltrare un frame su un segmento, usaCSMA/CD con gli altri adattatori sul segmento

• trasparente: gli adattatori non si accorgono della suaesistenza

• plug-and-play, autoapprendente, non richiedeconfigurazione

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 21

bridge Dominio di collisione

Dominio di collisione

= hub

= host

LAN (sottorete IP)

segmento LAN segmento LAN Domini di collisione

Dominio di broadcast

Bridge: isolamento del traffico

• L’installazione di un bridge divide la LAN in “segmenti”• I bridge filtrano i frame:

• normalmente i frame interni ad una LAN non sonoinoltrati ad altri segmenti di LAN

• I segmenti diventano domini di collisione separati

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 22

Come decidere su quale segmento di lan inoltrare unframe ?

Analogo al problema di routing a livello IP.

Bridge: inoltro

bridge Dominio di collisione

Dominio di collisione

= hub

= host

Dominio di collisione

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 23

Bridge: autoapprendimento

• Un bridge ha una tabella di inoltro• Voce nella tabella di inoltro:

• <mac address, interfaccia, Time Stamp>• Le voci sono eliminate dopo un periodo di tempo

fissato (il TTL può essere 60 min)• Il bridge impara quali host sono raggiungibili attraverso

quali interfacce• Quando riceve un frame, impara il segmento LAN da

cui proviene il mittente• Memorizza o aggiorna una voce nella tabella di inoltro

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 24

Bridge: algoritmo filtraggio e inoltro

Quando un bridge ha ricevuto un frame:• dst_MAC indirizzo MAC destinazione del frame• in_if interfaccia da cui arriva il frame• fwd_tab tabella di inoltro• find_fwd ricerca nella tabella di inoltro

out_if = find_fwd(fwd_tab,dst_MAC);if (out_if == in_if)

then ignora il frame;else if (out_if == null) // MAC sconosciuto

then inoltra il frame su tutte le interfacce tranne in_if - flooding;

else inoltra il frame su out_if;

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 25

• Il bridge riceve il frame da C• Annota nella tabella di inoltro che C è sulla interfaccia 1• D non è nella tabella, spedisce il frame sulle interfacce

2 e 3 (flooding)• D riceve il frame

Bridge: esempio di apprendimento

• C spedisce un frame a D, e D risponde a C

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 26

• D invia un frame a C• Il bridge riceve il frame

• Annota nella tabella di inoltro che D è sulla interfaccia 2• Il bridge sa già che C è sulla interfaccia 1, quindi inoltra

selettivamente il frame sull’interfaccia 1

Bridge: esempio di apprendimento (2)

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 27

Interconnessione senza backbone

• Non consigliabile per due ragioni:• l’hub di Computer Science è un single point of failure• tutto il traffico tra EE e SE passa sul segmento di CS

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 28

Raccomandata!• il bridge separa i domini di collisione• Sugli hub passa solo il traffico locale• Ma il bridge è ancora un single point of failure

Configurazione con backbone

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 29

Portadisabilitata

Bridge: Spanning Tree

• Per migliorare l’affidabilità si creano percorsi multipli tragli hub, ma questo crea percorsi ciclici – i bridgepotrebbero moltiplicare i frame e inoltrarli all’infinito

• Soluzione: disabilitare una parte delle interfacce pertrasformare una rete con cicli in uno spanning tree(albero coprente privo di loop)

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 30

Portadisabilitata

LinkInterrotto

Porta che torna in esercizio

Bridge: Spanning Tree (2)

• In caso di guasti di un collegamento o di un apparato,alcune delle interfacce che erano in stand-by vengonoriattivate e la rete torna connessa• Richiede un tempo di convergenza (decine di secondi)• Il protocollo STP è plug & play, ma…

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 31

Caratteristiche dei bridge

• Separano i domini di collisione• Migliora il throughput complessivo della rete

• Uniscono i domini di broadcast• Un frame broadcast raggiunge tutta la rete• Se sono tanti possono intasare

• Numero di nodi e copertura geografica illimitati• Possono interconnettere diversi tipi di ethernet (es:

10Base2 – 100BaseT – 1000BaseSX)• Sono transparenti (“plug-and-play”): non richiedono

configurazione

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 32

Bridges vs. Routers• Sono dispositivi store-and-forward

• router: dispositivi di livello rete• Bridges: dispositivi di livello di data link

• I router mantengono tabelle di routing (una voce perrete connessa) ed eseguono algoritmi di routing

• I bridge mantengono tabelle di inoltro (una voce peradattatore attivo) ed eseguono autoapprendimento,fitraggio e spanning tree

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 33

Routers vs. Bridge

Bridge: vantaggi• operazioni più semplici, richiedono meno modifiche ai

pacchetti• le tabelle sono apprese automaticamentee svantaggi• Se ci sono percorsi multipli, il traffico può usare solo i link

selezionati dallo spanning tree, anche se ci sarebbe altrabanda disponibile• uso subottimale della capacità della rete

• non proteggono dalle tempeste di broadcast• occupano una voce di tabella per ogni host

• scalabilità limitata

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 34

Routers vs. Bridges

Router: vantaggi• possono supportare topologie più varie, i cicli sono limitati

dal TTL IP (e da buoni protocolli di routing cg!)• proteggono dalle tempeste di broadcaste svantaggi• Richiedono configurazione di indirizzi IP sulle interfacce e di

default gateway sugli host (non plug and play)• Gli host non possono essere spostati plug&play da una rete

all’altra (ma c’è DHCP… )• devono modificare i pacchetti• occupano una voce di tabella di routing per ogni rete• I bridge sono adeguati per reti piccole (decine o centinaia

di host), i router sono usati in reti più grandi (migliaia)

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 35

Switch Ethernet

• Essenzialmente un bridge conmolte interfacce con unastruttura HW veloce e distribuita

• Inoltro di frame a livello 2,usando indirizzi LAN

• Switching: possono parlarecontemporaneamente A-con-A’e B-con-B’, senza collisioni

• Molte interfacce (decine)

Rete tipica:stella di host connessi su switch

Ethernet, senza collisioni

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 36

Switch Ethernet

• store & forward switching: il frame viene ricevutocompletamente, controllato e poi inoltrato (tipico)

• cut-through switching: il frame viene inoltrato dalla portadi ingresso a quella di uscita senza attendere che siacompletamente ricevuto• Leggera riduzione della latenza• Non può controllare il checksum

• Combinazioni di interfacce a banda condivisa/dedicata, a10/100/1000 Mbps• 24 porte 10/100 condivise, 2 uplink 10/100 dedicato• 24 porte 10/100, 2 uplink Gbit, tutto dedicato

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 37

Dedicated

Shared

Un esempio di LAN

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 38

Confronto

hub bridge router switch

Isolamento deltraffico no si si si

plug & play si si no si

Routing ottimale no no si no

cutthrough si no no possibile

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 39

Il Cablaggio ai tempi del coassiale

• Ethernet basata su cavo coassiale:• Topologia a bus• lo stesso cavo serve molti host

– Un host o un cavo malfunzionante influenza tutti, ebisogna andarlo a cercare (magari a km di distanza)

• Diversi segmenti sono concentrati nello stesso localetecnico, con Repeater, bridge, router, …

• Hub o switch venivano aggiunti nelle stanze più popolateo più attive– …e connessi al cavo coassiale

• Prime forme di cablaggio strutturato: cavo coassialecanalizzato, cavi “andata e ritorno” per un solo host

M. Campanella Corso Reti ed Applicazioni - Como 2006 Cap 5 - 2 pag. 40

Cablaggio strutturato (ultime due lezioni)

• Ethernet basata su hub o switch• Topologia inerentemente stellare• Ogni host ha un cavo dedicato verso l’apparato di

distribuzione• Edifici predisposti con prese RJ45 in tutti i locali attestate in

un armadi di distribuzione, cavi canalizzati• Sistema modulare:

apparato - patch - cavo canalizzato - patch - host• Il cablaggio può servire anche altri tipi di utenza (telefoni,

ma non solo)• E se non basta si mette uno switch nella stanza…• Edifici complessi, campus: struttura gerarchica del

cablaggio, fibre e multicoppia di backbone