Che materia stai cercando?

Appunti di Reti

Appunti del corso di Reti e Sicurezza tenuti dal professore Massimo Marchiori. Gli appunti sono della parte di Reti (circa 90 ore di corso) e spaziano dalla descrizione iniziale delle prime comunicazioni ai protocolli di comunicazione della rete mobile, la gestione e correzione degli errori, i primi protocolli di comunicazioni come ALOHA per finire con Ethernet e su cosa si basa e come funziona la... Vedi di più

Esame di Reti e Sicurezza docente Prof. M. Marchiori

Anteprima

ESTRATTO DOCUMENTO

24 canali voce(1.544 Mbps di dati)

Viene usata nella infrastruttura di internet

Viene usata nei cd audio

WAV, PCM Lineare, AIFF

La telefonia mobile: 0G, 1G, 2G, 3G, 4G

Premessa di marketing

Uno dei pochi ambiti in cui l'UE e l'Italia se la contendono con gli USA

- L'Europa dopo i primi tentativi si rende conto che serve uno

standard europeo

- Gli USA per eccesso di liberismo e libera concorrenza hanno lasciato

che ci fossero standard molteplici creando così reti incompatibili

Principio della conoscenza tariffaria

La telefonia mobile costa di più, ma finora non è stato un problema

perchè i numeri dei cellulari sono diversi dai fissi, quindi quando si

effettua una chiamata si conosce in anticipo il costo

Mentre negli USA non c’è distinzione e quindi si è deciso di far pagare

il surplus al possessore del cellulare

-> rallentamento del mercato

Inoltre esiste una grande competizione per quanto riguarda la telefonia

fissa, e ciò fa sì che i prezzi siano relativamente bassi

In Europa invece (specialmente in Italia) accade il contrario e quindi i

mercati alternativi (mobile) sono fioriti molto più velocemente

La telefonia si distingue in varie generazioni

0G-1G - reti analogiche

2G-4G - reti digitali

Tutta la telefonia mobile si basa su un problema fondamentale: la

suddivisione del territorio

Come gestire l'infrastruttura fissa per permettere il mobile?

- Si usa la switching center

0G (1950) Deriva dalle trasmissioni radio, noti come PPT - Push To Talk

- Un solo canale per ricevere e trasmettere

-> Half Duplex

Il PTT è stato reintrodotto in alcuni cellulari di ultima generazione

(es. moto talk)

Essenzialmente il cellulare può funzionare come un walkie-talkie

1960, il sistema IMTS - Improved Mobile Telephone System

- passa a due frequenze

- aumenta il livello di privacy, in quanto non è più possibile sentire

le comunicazioni altrui

- vengono utilizzati super trasmettitori ad altissima frequenza

- per evitare interferenze le celle coprono centinaia di chilometri

- 23 canali nella banda 100-450 MHz

-> troppo limitativo

- Ancora in uso in certe zone remote (Canada)

1G (1982)

I Bell Labs introducono l'AMPS - Advanced Mobile Phone System

- Conosciuto in Europa come TACS - Total Access Communication

System

- Ora le celle sono molto più piccole (10-20Km)

- La capacità di gestione è aumentata e diminuisce la potenza

richiesta per la trasmissione

- Problema delle interferenze tra le celle

- Si usano frequenze diverse tra celle vicine

Quante frequenze usiamo?

Più frequenze usiamo per separare le celle meno banda avremo a

disposizione

Viene usato il teorema dei 4 colori

Il teorema afferma che data una superficie piana divisa in regioni

connesse, come ad esempio una carta geografica politica (o in celle come

nel nostro caso), sono sufficienti quattro colori per colorare ogni

regione facendo in modo che regioni adiacenti non abbiano lo stesso

colore.

Quindi basta usare 4 frequenze diverse

Ma in pratica come sistemiamo le celle?

Supponiamo di avere un buon controllo del territorio

Come interagisce la rete wireless con la strada?

In città si sfasano le celle cercando di usare una matrice esagonale che

permette di ridurre le interferenze.

In questo caso quanti colori servono? Dipende!

Quando il sistema va in overload si suddividono le celle principali in

microcelle

Il numero di colori cambia in base alle infrastrutture e alla densità

d'uso e delle necessità di espansione

Tipicamente si usano dai 3 ai 7 colori

Un cellulare è sempre connesso ad ina sola cella finchè non si sposta.

ma quando si sposta cosa accade?

Handoff

L'Handoff classico 1G

Quando il segnale è troppo debole lo switching center office chiede alle

celle vicine quanta potenza ricevono dal telefono

Nell' Hard Handoff la vecchia stazione molla il cellulare che si aggancia

a quella nuova

- C'è del lag dovuto al cambiamento (circa 0,3 s) e in casi rari la linea

cade

Nel Soft Handoff, la nuova cella acquisisce il cellulare prima che la

cella vecchia lo molli

- Il problema è che il cellulare deve essere in grado di supportare due

frequenze diverse contemporaneamente

Caratteristiche principali del 1G

- Ogni cella gestisce molti utenti, quindi occorre un multiplex (FDM)

- Ogni cella è in grado di gestire 832 canali Full Duplex (due canali

simplex)

- Alcuni canali sono riservati per il controllo e la gestione, mentre

altri possono essere usati per lo smistamento delle frequenze tra celle

Ogni cellulare ha un numero seriale di 32 bit e un numero telefonico di

10 cifre (34 bit)

Ogni 15 minuti circa il cellulare manda un segnale in broadcast

contenente i suoi dati per registrarsi alla cella più vicina

Quando si chiama si usa il canale apposito (condiviso!) per attivare la

richiesta

In ricezione invece c'è un canale apposito di paging che i cellulari

controllano per sapere se ci sono chiamate in arrivo

2G

Anche nel 2G non si è arrivato ad uno standard mondiale

D-AMPS - standard statunitense (retrocompatibile con AMPS)

PDC - standard giapponese, funziona con la stessa tecnologia di D-AMPS

D-AMPS usa tutte le frequenze di AMPS (850MHz)

- Trasmette solo in digitale

- Usa frequenze aggiuntive per aumentare la banda (1850-1990MHz)

- In questa banda la lunghezza d'onda diminuisce quindi bastano

antenne piccole

- Trasmettendo in digitale si usa la compressione della voce

- Dai classici 56kbps si arriva a 8kbps (si arriva anche a 4kbps)

- Sei volte gli utenti standard di AMPS

Esempio di compressione: Delta Modulation

Le comunicazioni compresse vengono gestite in multiplexing usando un

classico TDM

La qualità del suono è peggiorata da 1G a 2G

Gestione dell'handoff

In AMPS è lo switching center a gestire tutto, ma potenziale collo di

bottiglia

In D-AMPS l'onere viene lasciato ai singoli cellulari

Il cellulare è in "patnership" con la cella, periodicamente tiene sotto

controllo la potenza del segnale

Quando il segnale è basso, è il cellulare a "protestare" con la base,

quindi la cella lo molla

A quel punto il cellulare cerca la cella con il segnale più potente

MAHO - Mobile Assited HandOff)

Il carico sul cellulare è minimo perchè si sfruttano i tempi morti dovuti

al multiplexing temporale per misurare la potenza del segnale

GSM - Global System for Mobile Communications, nata in Europa ora

utilizzata in tutto il mondo

Simile a D-AMPS in quanto usa l'FDM temporale

Differenza: I canali GSM sono molto più ampi di quelli AMPS (200KHz vs

30KHz)

Tengono più utenti ed hanno un data rate per utente molto più ampio

- 124 canali, ognuno con 8 slot TDFM

- Ogni canale GSM gestisce un data rate di 270Kbps, che per 8

utenti fanno 33,854 kbps a testa

- Meno overhead

-> 24,7 kbps, e dopo la correzione degli errori 13 kbps

Struttura delle celle GSM

Quattro tipi di celle: Macro, Micro, Pico e Umbrella

- Macro: 35 Km di raggio, sopraelevate rispetto agli edifici

- Micro: Cella più piccola posta sopra i tetti degli edifici

- Pico: Molto piccola, usata per aree densamente popolate (utilizzate

sopratutto indoor)

- Umbrella: usata per corpire i buchi tra le celle principali

SIM - Subscriber identity Module

- Varie taglie, dai 4kb fino ai 512kb

- Contiene varie informazioni, di cui le due più importanti sono la

IMSI e la Ki

IMSI - International Mobile Subscriber identity (Identificazione della

SIM)

Ki - chiave di autenticazione (autenticazione crittografica a chiave

condivisa)

Collegamento crypto GSM

- Il cellulare manda L'IMSi della SIM all'operatore

- L'operatore genera un numero casuale e lo manda al cellulare

- Il cellulare firma il numero con la Ki e lo rimanda all'operatore

- L'operatore nel suo DB ha registrato l'IMSI e la Ki associata.

- L'operatore defirma con la ki il numero casuale e controlla che

il numero sia lo stesso

CDMA - Code Division Multiple Access

Mentre D-AMPS e GSM sono abbastanza simili, CDMA funziona in modo

diverso, infatti non usa ne FDM ne TDM

CDMA è stato introdotto solo recentemente per via di un problema che non

lo rendeva fattibile, infatti CDMA "assume che ogni cellulare parli il

suo linguaggio con lo stesso volume di tutti gli altri"

E' un protocollo di accesso multiplo a canale condiviso, tecnicamente

CDMA moltiplica l'informazione binaria generata da una sorgente per

un'opportuna parola codice detta chip; la sequenza in uscita sarà

successivamente modulata e infine trasmessa sul canale.

In ricezione, il segnale ricevuto sarà costituito dalla somma vettoriale

(cioè compresa di modulo e fase) di tutti i segnali trasmessi dalle

singole sorgenti. Se i chip delle sorgenti sono ortogonali tra loro,

l'estrazione dell'informazione associata a ciascuna sorgente potrà essere

fatta in maniera del tutto complementare.

Il risultato di quest'operazione permette di ottenere un segnale che è

dato dalla somma di un segnale di ampiezza dominante, che è il segnale

proveniente dalla sorgente, e di un segnale ad ampiezza minore,

costituito dal rumore e dai segnali delle altre sorgenti.

Relazione del cellulare con le celle

- La base trasmette ad una potenza fissa, nota al cellulare

- Dalla potenza del segnale che riceve, il cellulare puù calcolare

quanto è distante dalla base

- Quindi cerca di trasmettere ad una potenza opportuna

Rispetto a D-AMPS e GSM, CDMA è in grado di gestire le celle senza

sprecare frequenza, infatti CDMA sfrutta al meglio la caratteristica del

traffico e dell'intermittenza

La sua efficienza è dovuta al fatto che ciascun canale utilizza l'intera

banda disponibile per tutto il tempo che desidera

Tra 2G e 3G: GPRS - General Packet Radio Service

E' classificato come 2.5G

E' un overlay del 2G che permette la gestione del traffico a pacchetti

GSM è costruito essenzialmente per trattare voce dato che viene riservato

un intero canale per la comunicazione

Quindi navigando in internet si sprecava la banda del canale, dato che

durante la navigazione sono frequenti i tempi morti in cui non si

trasmette niente,

Inoltre la tariffa era a tempo e non a traffico

Quindi il GPRS permette, analogamente al concetto di switch di cui

abbiamo parlato, la navigazione a pacchetti con tutti i vantaggi

conseguenti

- Non si spreca banda

- Non serve più un canale dedicato

- Si possono usare tariffe a traffico dati

- Alloca dinamicamente i canali Internet e quelli voce a seconda

delle richieste del traffico

Tipo di cellulari

classe C: possono connettersi come GSM o come GPRS, l'utente deve settare

a mano quale comunicazione usare

Classe B: Si può connettere o come GSM o come GPRS automaticamente

Pseudo classe A: Può usare contemporaneamente GSM e GPRS usando la stessa

frequenza (però la rete lo deve supportare)

Classe A: Usa contemporaneamente GSM e GPRS usando due frequenze diverse

EDGE - Enhanced Data rate for GSM Evolution

Classificato come 2.75G

Oltre alla modulazione di frequenza usa la modulazione di fase

- Ne esistono varie versioni

- velocità variabile: da 64kbps a 236Kbps (o EDGE Evolution)

3G

Rispetto al 2G ha più data rate e può supportare più utenti

- Nasce per gestire la banda video

- usa tipicamente bande di frequenza più larghe

- Due standard principali: WCDMA e CDMA2000

WCDMA: Wideband CDMA

- E' conosciuto in Europa come UMTS - Universal Mobile

Telecomunication System

- Usa una banda di 5MHz

- Il data rate tipico è di 384 kbps

CDMA2000

- Chiesto dagli USA (a differenza di EU e Giappone)

- Usa una banda di 1,25MHz

- Ha un data rate di 144kbps

HSDPA - High Speed Downlink Packet Access

Classificato come 3.5G

Evoluzione dell'UMTS (usa CDMA e QAM)

Esistono varie versioni di HSDPA supportati dagli operatori e dalle celle

- 1,8; 3,6; 7,2; 14,4 Mbps in Download

- Da 384kbps ai 2 Mbps in Upload

Attualmente in Italia in 3G si viaggia sui 7,2Mbps

HSUPA: High Speed Uplink Packet Access

Classificato 3.75G

Evoluzione dell'HSPDA con download massimo (teorico) a 5,6 Mbps

(la nuova versione arriva a 11,5 Mbps)

Come è possibile che il 3.5G superi il 3.75G?

HSDPA+ - Evolved HSDPA

E' stato sviluppato in contemporanea di HSUPA, ma anche se considerato

come 3.5G è riuscito a superare in prestazioni HSUPA

- Velocità massima in download teorica: 28Mbps

- velocità massima in upload teorica: 11Mbps

4G

HSOPA - High Speed OFDM Packet Access

- Conosciuto anche come LTE

- Bande variabili, da 1,25Mhz a 20Mhz

- Download fino a 1,2 Gbps e in Upload fino a 600Mhz

Le prime versioni furono commercializzate nel 2009 in Svezia e Finlandia

Come fa ad andare così veloce?

- Usa varie tecniche combinate tra cui: FDM, TDM e altre tecniche

commutate da trasmissioni satellitari.

- Usa più banda

La banda 4G LTE interferisce con la banda del digitale terrestre, quindi

adesso occorrono filtri aggiuntivi ad ogni antenna TV

Lo strato Data Link

- Fornisce un'interfaccia allo strato di rete sovrastante (network layer)

- Si occupa degli errori di trasmissione (error control)

- Regola il flusso di dati a seconda delle capacità della rete e del

ricevente (flow control)

Esistono vari modi in cui questo servizio può essere forte.

Unacknowledged connectionless

In questo servizio i pacchetti vengono inviati senza aspettare conferma

di una eventuale ricevuti(unacknowledged)e tantomeno senza stabilire una

connessione dedicata (connectionless).

Utile ad esempio per voce/streaming media, o quando il canale è molto

affidabile.

Acknowledeged connectionless

Altro servizio analogo, è come il precedente solo che in questo caso ho

la conferma della ricevuta dei pacchetti.

Acknowledged connection-oriented

Una connessione dedicata con ricevuta di ritorno (servizio di lusso)

La codifica: Framing

L'approccio classico è di prendere dei pacchetti dati dallo strato

superiore e codificarli in appositi frames

[packet] -> [Header|Payload Field|Trailer]

Payload (contenuto del pacchetto)

Uno dei problemi della trasmissione dei frame è accorgersi dove inizia e

dove finisce un frame.

Si potrebbe usare la sincronizzazione degli orologi, ma è impraticabile

per vari motivi

Metodo del Character count

Semplicemente mettiamo nell'header l'informazione del numero di caratteri

che costituiscono il corpo dati.

Simile a quello che fanno certi linguaggi di programmazione internamente.

ES:

[5]|0|1|2|3|4|[5]|5|6|7|8|9|[8]|0|1|2|3|4|5|6|7|

|---------|---|---------|---|---------------|

| frame 1 | | frame 2 | | frame 3 |

|5 charac.| |5 charac.| | 8 character |

Problemi !->errore

[5]|0|1|2|3|4|[7]|5|6|7|8|9|[5]|0|1|2|3|4|

|---------|---|---------|---|---------|

| frame 1 | | frame 2 | | frame 3 |

| | | (wrong) | | |

Il character count è stato uno dei primi metodi (derivati dai primi

linguaggi di programmazione, ma l'ambiente delle reti dove ci possono

essere errori molto più frequentemente che non su un desktop ha imposto

di cambiare metodo.

Metodo dei Flag Bytes

Il problema del Character count è che perdiamo tutti i dati in caso di

errore di sincronizzazione

->usiamo un byte speciale per segnalare (flag byte) l'inizio e la fine di

ogni frame

Byte stuffing

Usato per fare l'escaping, in modo da trasmettere qualunque messaggio

[ FLAG | Header | Payload Field | Trailer | FLAG ]

[A][FLAG][B] ---> [A][ESC][FLAG][B]

[A][ESC][B] ----> [A][ESC][ESC][B]

Un problema analogo con i linguaggi di programmazione si è avuto quando

si è passati dai caratteri ASCII ai caratteri più globali (UNICODE)

Usare bytes o in ogni caso grandezze fisse prima o poi non và più bene

Il bit stuffing

E' analogo al byte stuffing, stavolta a livello di bit

Ad esempio, si prende come "flag" 01111110

Escaping: Se lo stream di bits ha cinque 1 di fila allora dopo il quinto

bit viene inserito uno 0

a) 0110111111111111111111110010

b) 0110111110111110111110111110010

| | |

bits stuffing

Se tecniche come quelle che abbiamo visto ci permettono di sapere come

identificare gli errori in un frame nella rete, vogliamo sapere come

comportarci in caso di errori.

ERROR CONTROL

L' error detection ci permette di controllare se ci sono stati errori

durante la trasmissione; nel caso richiediamo una ritrasmissione.

Error detection è utile quando il canale è affidabile o gli errori non

sono critici, ma spesso serve anche error correction, cioè cercare di

correggere gli errori.

Error Correction (1)

Nelle reti quando il canale non è affidabile, ritrasmettere troppi

pacchetti diventerebbe oneroso, facendo direttamente correzioni degli

errori sui pacchetti si evita la ritrasmissione.

Error control: distanze

Prima di procedere ci occorre una misura del "danno" che un errore può

fare; gli errori meno gravi sono quelli che danneggiano un solo bit nel

messaggio o che ne danneggiano 2 e via dicendo.

La distanza

Diciamo allora che due messaggi di lunghezza uguale sono distanti 1 se

sono diversi solo per 1 bit, distanti 2 se sono diversi per 2 bit

Si chiama distanza di Hamming

Tecniche di Error Control

Sono più o meno potenti a seconda di quanta distanza di Hamming riescono

a sopportare nei messaggi (ovvero la gravità massima dell'errore che

riescono a sopportare)

Error Detection

Dovremmo avere informazione extra rispetto ai dati che ci permetta

stavolta di individuare l'errore

Avremo quindi un encoding (aggiungiamo una protezione ai dati) e poi una

fase di decoding dove ci liberiamo della protezione dei dati.

L'error detection quindi sarà nella fase di decoding, dove il ricevente

controlla se ci sono stati errori.

Modo semplice? Basta ad esempio verificare se il messaggio arrivato non

può essere stato creato con l'encoding (Messaggio illegale)

Condizione sufficiente ma non necessaria.

Potrebbero esserci talmente tanti errori da trasformare un messaggio

"legale" in un altro messaggio "legale", quindi, quand'è che siamo sicuri

di trovare l'errore?

Dobbiamo limitare la potenza dell'errore!

Dato un certo modo di proteggerci dagli errori (encoding/decoding)

vorremmo sapere: qual è il massimo errore che riusciamo a trovare?

->(la distanza minima tra i messaggi legali) - 1

Una semplice tecnica è quella del bit di parità (parity bit)

Ogni tot bit (n), inseriamo uno 0 o un 1 a seconda che la somma degli n

bit precedenti sia pari o dispari

n = 2 : 01 -> 01(1) 10-> 10(1)

Quanto è potente il parity bit "n"?

Facile vedere qualunque sia l'n: Presi due messaggi diversi, i loro

messaggi codificati sono a minima distanza 2

Il fattore n

Possiamo avere un errore (un bit "flippato") ogni n+1 bits -> possiamo

identificare un error rate di 1/(n+1)

Il codice migliore di controllo si ha con n=1: in quel caso, possiamo

identificare un error rate del 50%

Quanto stiamo sprecando per controllo dell'errore? 1/(n+1)

Esempio con n = 3 -> 1/4 del datarate sprecato

Ad ogni modo il parity bit ha potenza 1: significa che non appena c'è un

errore di potenza due il codice fallisce.

I Repetitions Code

Nel repetition code ogni bit viene ripetuto N volte

R(3) 110 -> 111111000

010 -> 000111000

E' facile vedere che per ogni due messaggi diversi, i loro messaggi

codificati con Rn sono distanti almeno N

Quindi con Rn possiamo fare error detection fino a potenza N-1

-> possiamo alzare la potenza quanto vogliamo.

Error Correction (2)

Significa che dato un valore sbagliato, possiamo farlo tornare al valore

corretto

Repetition N ci dà una affidabilità a K errori tale che K sia meno della

metà di N

Ad esempio abbiamo che con R3 il K massimo è (3-1)/2=1

-> R3 oltre a fare error detection a potenza, è un codice di error-

correction

Però la banda diventa 1/N

Error detection viene usato un diversi ambiti, come il codice IMEI del

telefono, o il codice ISBN dei libri, e nelle carte di credito

Altri esempi: codici a barre (UPC - Universal Product Code)

(somma delle cifre dispari) x 3 + (somma delle cifre pari) == Multiplo di

10

ISBN13 - C'è un nuovo tipo di codici ISBN dal 2007: ISB13 (13 cifre

invece di 10)

Usa lo stesso codice di error detection usato dai codici a barre

Torniamo ai codici error detection

Abbiamo visto i codici a ripetizione, ma sprecano molta banda

Limite Error rate vs Data rate

Man mano che vogliamo ridurre l'error rate a zero, anche il data rate

diventa zero

Conosciuto come No Free Lunch Principle

Shannon ha dimostrato che invece, anche se sembra impossibile, la curva

dei codici riesce ad avere un data rate positivo, anche se si vuole un

tasso degli

errori sempre più piccolo.

0.6 |

E | /

r | x /

r 0.4 | x x x /

o | x /

r | x / Non ottenibile

i 0.2 | x x x /

| x x /

|_x_x_x_x_ _ _ _ _/_ _ _ _ _ _ _ _ Data rate

0 0.2 0.4 | 0.6 0.8

Limite

Il teorema di Shannon

Hr(x) = xlog(1/x) + 1(1-x)*log(1/1-x)

Conseguenza

Dischi rigidi "scassoni" con un tasso di errore del 10%

Però vogliamo un tasso di errore decente ad esempio un errore ogni 10^15

letture

Usando al meglio le nostre tecnologie, dovremmo usare 60 dischi

Shannon però ci dice che in realtà c'è un codice per cui da un error rate

di 0,1 ad uno di 10^15 bastano (usando la formula dell'entropia) 2 dischi

Quali codici si avvicinano

LDPC - Low Density Parity Check

- Usato nella TV digitale e nel WIMAX

- Potenza: molto vicino al limite di Shannon

- Il decoding è NP-completo

I codici di Hamming

Sono una famiglia di codici famosissima, fanno parte dei cosiddetti

codici lineari perchè le loro operazioni si possono esprimere tramite

combinazioni lineari

Il codice Hamming(7,4)

Un codice Hamming(X,Y) significa che codifica Y bits di dati usandone X

in totale, quindi con X-Y bit extra.

I bit extra si dividono equamente la parità dei bit dati

L'encoding si può scrivere linearmente usando una matrice, che si chiama

matrice generatrice

|1 0 0 0 |0 1 1|

G=|0 1 0 0 |1 0 1|

|0 0 1 0 |1 1 0|

|0 0 0 1 |1 1 1|

---------|------

| |

Bit dati Bit di

protezione

Che proprietà hanno questi codici?

Fanno parte della famiglia più grande, come detto, dei codici lineari

(sottospazi lineari di uno spazio vettoriale su campi finiti)

Un codice Hamming (X,Y) e che ha distanza minima di Hamming Z viene anche

detto (X,Y,Z)

Diciamo che il peso (weight) di un messaggio binario è il numero di 1 che

ha.

Teorema del peso minimo

Se il peso minimo dei vettori della matrice generatore X per Y è d,

allora ogni coppia di messaggi codificati dista almeno d.

Il codice corrispondente è un codice error detecting di potenza d-1 e

error correcting di potenza (d-1)/2

Quanto abbiamo guadagnato: l'altro codice a potenza 1 aveva un data rate

di 1/3 = 0.33

Qui invece il data rate è di 4/7 = 0.57

I codici lineari sono molto belli perchè l'error correction si fa in un

modo molto più veloce (usando la cosiddettà sindrome)

Hamming superiori - Hamming ibridi (8,4)

Hamming (8,4), molto semplice si aggiunge un altro parity bit

La distanza minima è aumentata a 4, quindi error-detection 3 ed error-

correcting 1

Il data rate però è sceso, il data rate è del 50%

Hamming superiori - Hamming (11,7)

Distanza minima 5 -> (11,7,5)

Quindi corregge fino a 2 errori

Data rate 7/11 = 0.637

Bisogna notare che i codici di Hamming sono una generalizzazione dei

codici che abbiamo vista prima (parity bit, repetition)

Problemi pratici con gli errori

Se non sappiamo nulla degli errori non c'è nulla che possiamo fare

Se invece conosciamo delle proprietà degli errori, cioè se gli errori

hanno una struttura allora le cose cambiano.

I burst

Nella pratica, in molti casi gli errori non sono del tutto casuali, ma

occorrono in burst ("esplosioni" ravvicinate)

Questo crea problemi mostruosi ad ogni codice error-correcting

Potremmo tenerne conto e anzi sfruttare la loro struttura

Nel nostro computer, anche nel suo piccolo, avviene la comunicazione dei

dati, dal processore alla ram al disco rigido etc etc

Esempio:

Consideriamo ad esempio la RAM, ci serve una unità di misura

sufficientemente grande, il quadrilione (10^15)

Dati del nostro computer

RAM che va a 1600MHz

1Gb di RAM

Supponiamo, la probabilità di un errore nella RAM sia bassissima: uno

ogni cento quadrilioni

Ogni quanto in media ci sarà un errore? Un errore ogni 0.08 secondi!

E un doppio errore?

Senza tenere conto dei burst, un doppio errore circa ogni 8 quadrilioni

di secondi

Scelta di design: se vogliamo migliorare il nostro sistema, dovremmo

tenere ben conto degli errori di potenza 1, e possiamo tralasciare quelli

di potenza 2

E per i dischi rigidi?

La situazione non cambia molto: l'access rate è di certo minore della

RAM, ma non di molti ordini di grandezza, il che significa che ci saranno

errori in termini di anni invece che di secondi

RAID

RAID 0 - Overlay, striping dei dati

RAID 1 - Repetition 2

RAID 2 - Overlay a livello di bit con Hamming Code

RAID 3 - Overlay con parity bit

RAID 4 - Parity bit

RAID 5 - Parity bit distribuito

La RAM usa un codice di error correction, variante di quello di Hamming,

di tipo (72,64)

Se vi siete mai chiesti perchè la RAM di nuova generazione non andavano

più veloci delle vecchie:

hanno una penalità dell'11% (il data rate è l'89%)

SECDED - Single Error Correction, Double Error Detection

Attenzione che la scheda madre deve supportare la funzionalità

Anche se nella scheda madre è scritto che "supporta le ECC" significa che

potete usarle, ma non necessariamente che ci sia error correction

Esempio paradossale: le schede grafiche di fascia alta possono non

supportare SECDED

Altro esempio:

Le schedine di memoria usano ECC con Hamming

Le missioni Voyager (1977)

Funzionano ancora, sono "solo" a 14 bilioni di chilometri

In tutte le trasmissioni spaziali anche le più recenti si fa uso di

codici di correzione

Il codice Reed-Solomon

E' basato su aritmetica polinomiale

Un codice RS(X,Y) al solito codifica Y parole usandone X, può correggere

(X-Y)/2 errori!

Si usa anche in tantissimi altri ambiti, come i CD dove si usa il codice

a correzione di Reed-Solomon, in una sua applicazione a due canali.

Nei DVD

Nelle ADSL

Nei Blu Ray

Nel WiMAX

Nella TV Digitale con un RS(204,188)

Il passo oltre Hamming

Uno dei grandi aspetti del codice di Reed-Salomon è che va oltre Hamming;

invece che singoli bit come unità di base, può considerare gruppi di

bytes.

Permette ad esempio nei lettori CD di supportare errori di burst lunghi

fino a 4000 bits.

Le Erasures

Sono errori ma non nel senso di corruzione del dato, ma proprio di

cancellazione del dato: il dato non c'è più.

RS(X,Y) riesce a correggere fino a X-Y erasures, quindi il doppio degli

errori.

In generale può correggere contemporaneamente errori ed erasures: gli

errori contano doppio delle erasures, quindi 2*errori + erasures < X - Y

Reed-Solomon semplificato

CRC - Cyclic Redundancy Check

Un codice simile al funzionamento di Reed-Solomon che fa solo error

detection e non correction

Basato sull'architettura polinomiale a 2

Possiamo vedere ogni numero binario come il corrispondente polinomiale,

considerando ogni bit come il coefficiente di potenza sempre crescente

1011 -> x^3 + x + 1

11010 -> x^4 + x^3 + x

Come funziona l'aritmetica in GF(2)[]

- L'addizione è come fare lo XOR

- La sottrazione è come l'addizione

Il controllo di parità è dato dal resto della divisione, però usando

l'aritmetica di GF(2)[]

Si sceglie un polinomio, il cosiddetto polinomio generatore G(x)

Abbiamo un messaggio M(x)

Potremmo dividere M(x) per G(x), calcolare il resto R(x) e fare

l'encoding trasmettendo M(x) seguito da R(x)

Il problema è che se scegliamo un numero G qualunque con G(x) > M(x), e

quindi, se il messaggio M(x) è minore di G(x), allora il resto sarà della

stessa grandezza di M(x)

Per risolvere questo problema, allora moltiplichiamo M(x) per x^r con r =

(grado(G(x))

Quindi moltiplicare per x^r un polinomio, equivale, ovviamente a fare lo

shift a sinistra di r posizioni.

Abbiamo trasmesso M(x) seguito da R(x) -> "seguito da" equivale a x^r *

M(X) + R(x) ma per le magiche proprietà di GF(2)[] è lo stesso che x^r *

M(X) - R(x)

L'error detectiotn semplicemente prendere il numero trasmesso e calcola

il resto della divisione per G(x) che per quanto detto prima deve essere

zero. Quindi se il resto è zero è tutto ok, altrimenti c'è stato un

errore.

Potenza

Qual è la potenza di un tale metodo?

Supponiamo ci sia un errore, sono bits che sono stati invertiti

In altre parole, per l'aritmetica di GF(2)[] è lo stesso che sommare un

polinomio di errore, diciamo E(x)

Abbiamo il polinomio trasmesso T(x) più un polinomio di errore e

calcoliamo il resto della divisione per G(x)

T(x) + E(x) mod G(x) = (sappiamo che T(x) mod G(x) = 0) -> E(x) mod G(x)

Quindi non riusciamo a trovare l'errore solo quando E(x) mod G(x) da come

resto 0

Singoli errori

Abbiamo E(x)= x^i

->basta che G(x) abbia due o più termini

Doppi errori

E(x)= x^i + x^j

= x^j * (x^(i-j)+1)

-> basta che G(x) non sia multiplo di (x^i + x^j)

Ogni errore con un numero dispari di bits

Basta che x+1 sia un fattore di G(x), (deriva dagli zeri dei polinomi)

G(x) = (x+1) * ...

E(x) = x^i + x^j + ...

---------------

Dispari

E(x) mod G(x) = 0 -> ( E(x) = G(x) * .... )

E(0) = G(0) * .... | E(1) = G(1) * ....

= (x+1) * .... * .... | = (x+1) * .... * ....

= (0+1) * .... * .... | = (1+1) * .... * ....

= 1 * .... * .... | = 0 * .... * ....

I Burst Errors

E(x) = x^i(x^j+...+1) è il burst error di lunghezza j+1

-> basta che G abbia grado > j e termini con + 1, e correggiamo

tutti i burst lunghi fino a j+ 1!

In generale mettere "+1" è una buona scelta per un polinomio

Vaste opzioni: possiamo combinare tra loro più polinomi oppure scegliere

(per quanto possibile) i polinomi irriducibili.

All'aumentare del grado G, aumenta la potenza: ogni burst error di

lunghezza arbitraria più grande del grado di G

-> probabilità: 0.5^grado(G(x))

Cosa vuol dire nella pratica?

Protezione esponenziale col grado di G

Tipi di polinomi

CRC-1

x+1

-> è il codice parity bit 1

CRC-5 | CRC-16

x^5 + x^2 + 1 | X^16 + x^15 + x^2 + 1

-------------------------------------------------------

Vengono usati nelle chiavette USB

Bluetooth

CRC-32

x^32 + x^30 + x^26 + x^25 + x^24 + x^18 + x^15 + x^14 + x^12+ x^11...

Usato nei Modem v.4

Formato .zip

Fibra Ottica

CD

Ethernet

Immagini PNG

Come detto questa tecnica "polinomiale" è alla base poi dei codici di

error-correction più avanzati come Reed-Solomon.

Dove informalmente, invece di usare GF(2)[] si va a "ordini superiori",

ad esempio GF(2^n)...

RS(255,233) su GF(255) è uno dei principali standard NASA

Potenza fino a ordine 16

Data rate 91%

I codici QR

I codici QR possono memorizzare fino a un massimo di 4.296 caratteri

alfanumerici, 7.089 caratteri numerici. Nei codici QR è utilizzato il

codice Reed-Solomon per la rilevazione e correzione d'errore: nel caso in

cui il QR fosse in parte danneggiato, per esempio da macchie o graffi sul

supporto cartaceo, l'applicazione Reed-Solomon permette di ricostruire i

dati persi, ripristinando, durante la decodifica, fino al 30% delle

informazioni codificate.

Quattro livelli di error correction

L(Low), M(Medium), Q(Quartile), H(High)

->error recovery del 7%, 15%, 25%, 30%

Passiamo ora all'altro lato del Data Link, i flussi.

Servono quindi delle regole:

I protocolli come detto sono i tramiti cui si passano dati da un punto

all'altro della rete

Il problema del flow control

In un canale semplice, se "inviamo troppi dati" rischiamo che il

ricevente non riesca a gestirli e che quindi vadano persi.

In questo caso l'error control dentro ai dati non serve a nulla, anche se

il dato arriva correttemente, è il ricevente che non riesce a gestirlo.

Potremmo disegnare la rete in modo da inviare i dati al giusto data rate

Questo approccio però è ovviamente limitativo perchè le capacità del

ricevente/mittente possono essere diverse.

Occorre necessariamente andare su un altro tipo di approccio dove l'unica

soluzione possibile è far parlare il ricevente con chi manda i dati.

Costruiamo il nostro primo protocollo di rete

I protocolli stop-and-wait

Sono una famiglia di protocolli in cui si introduce appunto il parlare

tra ricevente e mittente.

L'idea è semplice: si manda un blocco dati e poi si aspetta (stop and

wait) che il ricevente ci mandi un messaggio di conferma (ACK -

Acknowledgement) segnalandoci che possiamo inviarne un altro.

Vantaggi: per implementare un protocollo di questo tipo basta un canale

half duplex, visto che non c'è mai comunicazione contemporanea

Svantaggi: abbastanza lento

Mr Murphy

Supponiamo di dover lottare contro la legge di Murphy: cioè che nel

canale di comunicazione ci sia qualche errore.

Ovviamente abbiamo protetto il nostro pacchetto, ma ciò non significa che

sia immune da errori.

Quindi il protocollo andrebbe modificato in questo modo: il receiver

invia il messaggio di conferma solo se il pacchetto supera il controllo

dell'errore altrimenti lo ignora.

Mandiamo un pacchetto

Murphy interviene e corrompe il pacchetto

Il receiver se ne accorge e non ci invia il messaggio di conferma

E noi aspettiamo...

E aspettiamo

...

Così non funziona

Introduciamo un timeout: se entro un certo periodo di tempo non riceviamo

nessun messaggio di conferma, rimandiamo il pacchetto.

In questo modo, noi mandiamo il pacchetto, Murphy corrompe il pacchetto,

il receiver se ne accorge, non ci arriva il messaggio di conferma, noi

aspettiamo e quando scade il timeout noi rinviamo il pacchetto.

Però può accadere che Murphy corrompa il messaggio di conferma del

receiver, quindi noi rinviamo il pacchetto.

Quindi al ricevente il flusso di dati arriva con dentro ripetuto due

volte un pacchetto dati.

Un modo per uscire fuori da questa situazione è aumentare il carico del

messaggio (frame) non solo con l'informazione per il controllo degli

errori, ma anche l'informazione sul controllo del flusso stesso.

Ad esempio numerando i pacchettti, in modo tale da accorgerci se ci sono

ripetizioni.

Morale: Numeriamo ogni pacchetto

In questo caso se accadesse la situazione di prima il ricevente sa

riconoscere un eventuale errore del flusso.

Aumentiamo l'informazione del frame con una parte dedicata ai numeri del

controllo del flusso.

Quanto grande lo facciamo questo controllo? Grande quanto è grande il

flusso

Se il numero è troppo piccolo rischiamo di non poter trasmettere un

flusso di dati che sia più grande.

Pensandoci, in realtà il problema può avvenire solo fra pacchetti che

sono consecutivi

Quindi non ci serve distinguere tra due frame qualsiasi ma solo fra frame

contigui.

-> Ci bastano due simboli: 0 e 1

I frame vengono spediti usando un bit extra per i controllo di flusso: 0

o 1 alternati tra frame pari e dispari.

Siamo andati oltre il semplice stop-and-wait: famiglie di protocolli di

questo tipo, dove si ritrasmettono tramite il timeout nel caso il

pacchetto vada perso, si chiamano

PAR (Positive Acknolewedgement

ARQ

Quando il canale è full duplex possiamo dunque prendere un protocollo

"simplex", metterne due ad ogni lato della linea e trasmettere da ambo i

lati.

Un grosso problema è l'overhead: praticamente per ogni pacchetto che

arriva, ne circola un altro per la riconferma.

Piggybacking

Invece di essere frettolosi e mandare un messaggio di conferma ogni volta

che riceviamo un frame aspettiamo e inviamo il messaggio di conferma non

da solo ma in piggyback sulle spalle del primo frame dati che stiamo

ritornando

in questo modo stiamo riducendo la banda usata: essenzialmente il

messaggio di conferma arriva gratis con un overhead minimo rispetto ai

dati che stiamo trasmettendo (una conferma sono pochi bit rispetto a

trasmettere un intero frame)

Per sfruttare bene la tecnica del piggybacking bisogna stare attenti a

non aspettare troppo per la ritrasmissione (se ad esempio non stiamo

trasmettendo dati).

Quindi funziona bene quando la comunicazione è abbastanza equilibrata.

Quindi ci vuole un corretto bilanciamento di flussi, oppure un calcolo

accorto del timeout di ritrasmissione .

In tutti questi tipi di protocolli, la logica era sempre quella di

aspettare la trasmissione prima di aver avuto la conferma del messaggio

precedente.

In alcuni contesti questo tipo di protocollo può rivelarsi estremamente

inefficacie.

Esempio

Abbiamo una comunicazione satellitare con un GEO

Tempo di trasmissione: 250 ms

Banda assegnata: 50 kbps

Taglia ogni Frame: 1000 bit

Dopo 20 ms abbiamo inviato il nostro primo frame e poi aspettiamo la

ricevuta di ritorno; supponendo che non ci siano errori aspettiamo 250 +

250 = 500 ms

-> su 520 ms, trasmettiamo per 20 ms

-> siamo rimasti bloccati per il 96% del tempo.

In generale il problema c'è quando il prodotto (bandwidth) * (round-trip-

delay) è grande: i protocolli visti funzionano male, perchè

sottoutilizzano il canale.

Se il canale ha capacità C (bit/s) la taglia del frame è S (bit) e il

tempo di round trip è R, possiamo calcolare l'utiilizzo della linea nel

caso di protocolli con ack: S / ( S + C * R )

Se S < CR abbiamo un utilizzo del canale minore del 50%

Soluzione: Sliding Windows

La tecnica delle sliding windows sfrutta l'idea di non preoccuparsi della

conferma dei pacchetti fino a quando non trasmettiamo un numero di frame

n, (con n > 1)

Tiene conto di quanto siamo stressati: più apriamo la finestra, più siamo

rilassati e più pacchetti lasciamo andare senza bisogno di conferma.

La taglia della sliding windows può variare sia per il sender che per il

receiver, dando luogo a vari protocolli.

I protocolli "Go Back N"

Si hanno quando la taglia della sliding windows di chi riceve è 1, cioè

noi siamo rilassati, mentre il nostro interlocutore è super-apprensivo.

Funziona bene quando non ci sono molti errori ma il prodotto del

bandwidth * round-trip-delay è alto

Il nostro rischio è aumentato perchè nel caso peggiore abbiamo n

pacchetti inviati, e non sappiamo se sono arrivati, e quindi dobbiamo

essere pronti a rinviare quei pacchetti.

-> dobbiamo avere un buffer di taglia n-frames

->Assieme a n timer per l'eventuale ritrasmissione

I selective repeat

Sono quelli in cui anche il nostro interlocutore, finalmente si rilassa

un po' e apre la sua finestra.

Funziona bene, ma ha il problema che ora anche il receiver deve allocare

un buffer per i pacchetti ricevuti.

La taglia richiesta del buffer è l'ampiezza dell'apertura massima della

finestra, non la grandezza complessiva della finestra.

Esempi di protocolli reali

HDLC - High Level Data Link Control

Ha alcune varianti LAP - LAPB

Ideato inizialmente dall'IBM

Si usa ancora per modem/fax, reti vario tipo e per molti altri (bancomat)

Usa dei frames delimitati tramite il bit stuffing che abbiamo visto

La struttura del frame

[ 01111110 | Address | Control | Data | Checksum | 01111110 ]

8 8 8 >0 16 8

la parte Data è il payload, i dati effettivi

La parte Checksum è calcolato usando CRC

La parte Address consente di gestire indirizzi multipli

La parte di Control è quella più interessante. Essenzialmente, ci possono

essere tre tipi fi Frame:

- Information

- Supervisory

- Unnumbered

Control del Frame

Il controllo del flusso avviene tramite una sliding window di grandezza

massima di tre bit ("8 spicchi")

Il Frame Information

- Seq contiene il numero del controllo di flusso della sliding window

- Next contiene gli ACK( in piggyback)

- P/F sta per Poll/Final. quando il bit indica P si chiede al ricevente

di iniziare la trasmissione

con F si rischiede di terminare la trasmissione

[ 0 | Seq | P/F | Next ]

1 3 1 3

C'è anche una variante dove il controllo di flusso si fa con una sliding

window grande 128 "spicchi", usata per le comunicazioni satellitari.

Il frame Supervisory

Si occupa della supervisione del flusso

Il campo type indica i vari tipi di supervisione: quattro tipi sono

possibili

- Type 0: ACK; (in questo protocollo detto Receive Ready), si usa

quando il flusso è sbilanciato e non si può fare ACK con piggybacking

- Type 1: Reject; è un NAK generalizzato, segnale che vanno

ritrasmessi tutti i frame partire da quello indicato in poi nella sliding

window Qui il Next indica il primo frame.

- Type 2: Receive Not Ready; questo è qualcosa di concettualmente

nuovo: segnala che ci sono problemi di congestione nel receiver, e quindi

la trasmissione va bloccata, finchè il receiver non rimanda un ACK.

- Type 3: Selective Reject; questo è il classico NAK.

[ 1 | 0 | Type | P/F | Next ]

Il Frame Unnumbered

Usato per ulteriori comandi di controllo

- DISC: Sta per DISConnect, segnala che la macchina sta uscendo dalla

rete in maniera definitiva (quindi diverso dal frame Supervisory di tipo

2

- SNRM: Set Normal Response Mode

E' il comando duale, segnala che una nuova macchina è entrata

nella rete

Indica un canale asimmetrico, dove il nuovo entrato è meno

importante

- SABM: Set Asynchronous Balanced Mode

E' il comando (introdotto successivamente) per creare una

connessione bilanciata, dove chi

entra ha gli stessi diritti degli altri

- FRMR: FRaMe Reject

Indica che è arrivato un frame con una sequenza di controllo non

corretta/sconosciuta

Infine anche i comandi di controllo unnambered possono essere "toccati"

da Murphy

-> c'è bisogno anche qui di SCK

-> comando dedicato, UA (Unnumbered Acknowledgement)

[ 1 | 1 | Type | P/F | Modifier ]

Anche per un semplice protocollo come HDLC abbiamo visto quanta

complessità occorre introdurre per semplicemente far funzionare le cose.

Un altro protocollo, che si usa molto di più dell' HDLC, perchè è il

protocollo di referenza di Internet per quanto riguarda le connessioni

point-to-point

Point to Point

Sono le connessioni internet dedicate punto-a-punto

In internet si usa il protocollo PPP (Point-to-Point Protocol)

Ovviamente dà un metodo di framing per impacchettare i bit

Cosa fa PPP?

Comandi di controllo del flusso per attivare le connessioni, test,

negoziazione, chiusura

Questa parte si chiama LCP (Link Control Protocol)

Metodo per negoziare con lo strato superiore dl network layer.

Questa parte si chiama NCP (Network Control Protocol)

Il Frame PPP

E' stato disegnato cercando di essere quanto più simile a HDLC

Ad esempio il delimitatore del frame è lo stesso di HDLC

PPP gestisce frame a lunghezza variabile

[ Flag | Address | Control | Protocol | Payload | Checksum | Flag ]

PPP vs HDLC

Differenza:

- PPP usa però byte stuffing invece che bit stuffing

- Il campo Address ha lo stesso significato che in HDLC e non si usa: ha

sempre il valore costante 11111111.

- Il campo Control non si usa quindi tutti i frame sono di tipo non

numerato.

- E Control ha valore fisso 00000011.

Dunque PPP, è un protocollo che non usa le tecniche di numbering e ACKs

per creare una comunicazione

Il campo Protocol

In questo campo si specifica il protocollo che PPP sta implementando

Quindi in un certo senso PPP stesso è un meta-protocollo

Il campo payload

Nel campo payload ci sono i dati, il cui significato dipenderà dal campo

protocollo specificato in Protocol

Il campo checksum

C'è il checksum del frame, calcolato usando CRC (-> PPP fa error

detection, ma non correction)

I protocolli supportati da PPP

Nel campo protocol ci possono essere essenzialmente due tipi di

protocolli:

quelli di negoziazione (essenzialmente che restano nel data link layer) e

quelli di livello più alto (network layer)

Due famiglie, LCP (che stabilisce la linea) e NCP (che interagisce con i

stati superiori)

LCP

Vediamo quali sono i comandi che LCP usa:

Sono 11:

-> 4 di configurazione

-> 2 di terminazione

-> 2 rifiuto

-> 2 di eco

-> 1 di test

Configurazione LCP

Configure-request:

Sender -> Receiver

Propone opzioni per la configurazione della linea

Configure-ack:

Sender <- Receiver

Manca il controllo ACK nel contenitore PPP viene quindi rimpiazzata da

una reimplementazione nel sottoprotocollo

Configure-nak:

Sender <- Receiver

Il NAK per configure-request

Configure-reject:

Sender <- Receiver

Non c'è nulla da fare, (opzioni non negoziabili)

Per evitare sprechi è possibile rimuovere i campi Address e Control

Terminazione LCP

Terminate-request

Sender-Reciver

Terminate-ack

L'ACK di terminazione-request va bene, comunicazione chiusa

Rifiuto LCP

Code-reject

Receiver -> Sender

Non ho capito cosa intendevi, richiesta sconosciuta

Protocl-reject

Non capisco di che protocollo parli, (o c'è stato un errore sulla linea)

Echo LCP

Echo-request

Sender -> Receiver

Per favore, rimandami il frame indietro

Echo-reply

Sender <- Receiver

Serve a controllare/misurare la qualità della linea di comunicazione

Test LCP

Discard-request

Sender -> Receiver

Ignora il frame

Serve a fare un primo test preliminare della linea e trovare eventuali

loops.

PPP e le ADSL

Ricordiamo che ci sono vari parametri settabili in PPP

Alcuni ovvi come abbiamo visto, che tolgono byte inutili da ogni frame.

L'altro aspetto è il payload variabile

La taglia dei pacchetti

Significa quindi che dovremmo scegliere una taglia massima per i nostri

pacchetti

Quello che in gergo si chiama MTU - Maximum Transmission Unit

Ogni protocollo ha un MTU, fissato dallo standard ed eventualmente

riconfigurabile verso il basso

Lo Zen e l'arte dell'MTU ADSL

Intuizione generale sull'MTU

MTU grande -> pacchetti più grandi -> meno overhead -> più banda (va bene

se il canale ha pochi errori)

MTU piccolo -> pacchetti più piccoli -> più overhead -> meno banda (va

bene se il canale ha molti errori)

PPP si usa in due varianti primarie

Le varianti sono

PPPoE - PPP over Ethernet

PPPoA - PPP over ATM

"over" = incapsulato dentro flussi Ethernet ed ATM

PPP -> PPPoE/PPPoA -> Ethernet/ATM

Ma la situazione è più complessa

Flusso dati 1: dal computer al router

Flusso dati 2: dal router al modem

Flusso dati 3: dal modem al provider

Ma neanche così è finita

Flusso 3: dal modem "al provider"...?

Flusso 3: dal modem al primo DSLAM (Digital Subscriber Line Access

Multiplexer)

Flusso 4: dal primo DSLAM fino a qualche punto del provider

Flusso 5: ci si collega alla rete Internet

Nei flussi "lato provider"

ci possono essere due tecnologie, quella ATM e quella Ethernet

Molto spesso il primo tratto è formato da ATM e l'ultimo da Ethernet

ATM

Asynchronous Transfer Mode

Usa TDM, si dividono i dati in flusso di celle di ampiezza fissa.

Analogo di HDLC ma nato per telefonia/bancomat etc e non per internet,

gestisce controllo di flusso con sliding windows( "16 spicchi"), error

detection (CRC-8)

Indirizzamento ATM

Doppia gerarchia, cammmini ("path") e canali ("channel")

Che sono le due etichette VPI e VCI che vediamo nelle configurazioni ADSL

VPI - Virtual Path Identifer

VCI - Virtual Channel Identifer

-> terminologia: Virtual Channel - ATM è connection-oriented

Anche ATM, come PPP, viene concretamente embeddato dentro altri

pacchetti.

Giacchè appunto si tratta di canali in multiplex e quindi c'è interazione

con altri flussi dati

LLC o VC-MUX

LLC - Logical Link Control: Protocolli multipli per canale

VC-MUX - Virtual Connection Multiplexing: Un solo protocollo per canale

Flusso dati 1: dal computer al router (Es. PPPoEoE PPP -> PPPoE ->

Ethernet)

Flusso dati 2: dal router al modem (Es. PPPoEoA Ethernet -> ATM)

Flusso dati 3: dal modem al provider (Es. PPPoA ATM -> LLC/VC-MUX)

Flusso dati 4: dal provider ad un punto interno

Flusso dati 5: da un punto interno ad una rete Ethernet esterna

Se di mezzo c'è il wireless la situazione si fa ancora più complicata

In pratica l'MTU interagisce con tutti gli altri protocolli in tutti i

flussi in atto

Quindi occorre stare bene attenti a sapere esattamente cosa si modifica.

caso ideale: linea senza errori

-> MTU grande

Ma, diminuendo l'MTU sotto certe soglie critiche, la banda migliora.

Deriva tutto dall'interazione con gli altri flussi.

C'è poi da considerare tutta l'interazione con gli strati superiori

In ogni caso ci torneremo quando avremo altre nozioni che ora ci mancano

Alla visione più vicina a PPP, e quella più comune: PPPoE

PPPoE: ciclo iniziale

La connessione ADSL inizia così:

Il nostro computer/modem invia un frame PPPoE (Active Discovery

Initiation) col suo indirizzo fisico (MAC)

Ogni servizio ADSL disponibile risponde con un PADO in cui dà il proprio

indirizzo e si "offre" per la connessione.

Il nostro computer risponde con un PADR (PPPoE Active Discovery Request)

in cui segnala il servizio ADSL che ha scelto.

Il servizio fa l'ACK usando un frame PADS

Competizione e "lock-in"

I protocolli multiaccesso

Finora abbiamo visto il caso point-to-point, in cui c'è uno che parla e

uno che ascolta, ed un canale tutto pe loro.

Ovviamente, ci sono molti altri contesti in cui queste assunzioni non

sono valide, e ci sono molte entità diverse che vogliono usare lo stesso

canale per parlarsi

I contention system

Sono quei sistemi di comunicazione multipla in cui c'è un unico canale

condiviso da molti, e si possono creare contenziosi.

Assunzioni

Station Model: sono le entità che trasmettono. Dopo che hanno iniziato la

trasmissione di un frame, non fanno altro finchè non è stato trasmesso.

Single Channel: c'è un canale singolo disponibile per tutti

Collision: se due frame si sovrappongono, c'è una collisione e sono

inutilizzabili

Sul tempo

O continuo (non c'è un orologio centrale)

oppure slotted (a intervalli)

Su carrier (il mezzo di trasporto)

Carrier Sense (una stazione può vedere se il canale è in uso prima di

tentare una trasmissione)

No Carrier Sense

Sfruttamento del caso

Probabilità

La distribuzione di Poisson

Pr[k] = ( G^k * e^-G ) / k!

Protocollo Aloha

Dobbiamo vedere qual è la probabilità che ci sia una sola trasmissione

(pr[1)] in un tempo doppio

-> la media in quel periodo è 2G

-> la probabilità ( Pr[k] = (G^k * e^-G ) / k! è 2G*e-2G

La probabilità che il canale sia usato correttamente in ogni singolo slot

di tempo è la meta G * e^-2G

E quindi, a quanto mi conviene settare la velocità di tentativi di

accesso al canale (G) per massimizzare le prestazioni?

Il massimo facile da vedere si ottiene con G = 0.5

-> 1/2e frame/sec -> circa 0.184

18.4% di banda... è poco

Però il 18.4 non dipende da quante entità possono trasmettere, che

possono essere tantissimi

Altra variabile possibile: lunghezza del frame random

Ma conviene fissare frame di lunghezza fissa

Motivo intuitivo: perchè avere frame diversi creerebbe rotture di

simmetria

Slotted Aloha

Due anni dopo Aloha, Roberts trova un modo per migliorarla

Assume che il tempo sia "slotted" tramite una stazione principale che

manda un segnale di sincronizzazione

In tal modo, una stazione deve attendere prima di trasmettere il

pacchetto, non c'è trasmissione istantanea.

Come cambiano le prestazioni?

Il periodo "critico" che può generare conflitti stavolta è dimezzato.

Ora la probabilità di successo è Pr[1] = G * e^-G

Il numero massimo di frame al secondo si ha con G=1 e diventa: 1/e

Cioè circa 36.8%, il doppio di Aloha

Abbiamo raddoppiato la velocità alterando le regole del gioco

Si può fare ancora meglio?

Carrier Sense

1 - persistent CSMA

CSMA - Carrier Sense Multiple Access protocol

-> prima di trasmettere, controlla che non ci sia già una

trasmissione (carrier sense)

Se c'è una trasmissione, controlla il canale, e non appena si libera,

trasmette

Può lo stesso succedere che ci siano collisioni (Murphy...) in questo

caso?

Si riaspetta un certo tempo casuale e poi si riprova

Performance: aumenta a più del 50%

Difetto di 1-CSMA

Se molte stazioni stanno aspettando durante una trasmissione, alla fine

della trasmissione tutte cercano di trasmettere contemporaneamente

provocando una collisione

Se fossero un po' meno "egoiste", il mondo funzionerebbe meglio

p-persistent CSMA

Si ottiene rilassando l'ipotesi che uno debba sempre trasmettere (p=1)

quando trova la linea libera, ma invece, trasmette con probabilità p (non

deve trasmettere a tutti i costi)

Performance: Migliora, con molte stazioni al diminuire di p

Al limite si può arrivare al 100% dell'efficienza

Nonpersitent CSMA

Usa un metodo alternativo: invece di tenere d'occhio il canale per

ricominciare la trasmissione non appena è libero, se trova il canale

occupato aspetta un periodo di tempo casuale e poi riprova.

Performance: la curva di performance si comporta differentemente da p-

CSMA e poò raggiungere performance vicine al 90&

CSMA/CD - CSMA Collision Detection


PAGINE

59

PESO

276.21 KB

AUTORE

Evettore

PUBBLICATO

8 mesi fa


DESCRIZIONE APPUNTO

Appunti del corso di Reti e Sicurezza tenuti dal professore Massimo Marchiori. Gli appunti sono della parte di Reti (circa 90 ore di corso) e spaziano dalla descrizione iniziale delle prime comunicazioni ai protocolli di comunicazione della rete mobile, la gestione e correzione degli errori, i primi protocolli di comunicazioni come ALOHA per finire con Ethernet e su cosa si basa e come funziona la rete Internet


DETTAGLI
Corso di laurea: Corso di laurea in informatica
SSD:
Università: Padova - Unipd
A.A.: 2017-2018

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Evettore di informazioni apprese con la frequenza delle lezioni di Reti e Sicurezza e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Padova - Unipd o del prof Marchiori Massimo.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!