cerca
Sistemi per l'elaborazione delle informazioni - Lezione 2
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Sistemi per l'elaborazione delle informazioni - Lezione 2

Torna alla pagina di Sistemi per l'elaborazione delle informazioni


:: Sistemi per l'elaborazione delle informazioni ::

Lezione 27 Settembre 2007

Introduzione a livello di Data Link

Le reti tra computer nascono come reti private, per l'ovvio motivo che non si possono tirare in giro i cavi per l'Italia etc.

Tecniche standard per i computer

Gli standard offrono dei pro e dei contro. Il pro è che ci può essere intercomunicabilità fra produttori diversi, mentre il contro è che in genere, una volta che si è fatto uno standard, poi non lo si cambia più per un bel pezzo e la tecnologia viene per così dire congelata; inoltre è possibile che ci siano più standard per la stessa funzione.

Gli standard vengono inventati, per esempio, dalla Internet Society, dall'ISO, dal CCITT, dal forum ATM (Azienda Trasporti Milanese, lo standard del degrado della linea dei pullman è loro...).

Come dicevo all'inizio, all'interno del computer i bit sono organizzati spazialmente: ogni bit è una carica in una certa porzione piccola ma fisicamente reale all'interno del computer. Ma devo spostarli 1 alla volta, nel dominio del tempo, affinché io possa trasmetterli lungo una rete. Per fare ciò, occorre codificare in qualche modo la presenza e l'assenza di carica (cioè lo 0 e l'1 nella memoria del computer) in un segnale.

Un modo per farlo è stabilire che 0 Volt = 1, e 5 Volt = 0. Bene. Bello. Problema: lungo un filo è più che probabile che il segnale si attenuerà, perché il filo ha una sua resistività e così via. Quindi è possibile che fra 10 metri non arrivino più 5 volt, ma 2,5, e a questo punto l'apparecchio ricevente potrebbe interpretare i 2,5 Volt arrotondandoli per difetto, e ricevendo 0 al posto di 1. I dati si perdono. La perdita di dati è ancora accettabile durante le conversazioni telefoniche, perché anche se perdiamo addirittura pezzi interi di parola, si capisce lo stesso. Ma non è assolutamente accettabile perdere pezzi durante la trasmissione di dati informatici.

Quindi, per evitare sto problema del voltaggio, si è pensato di inviare i bit non come livelli diversi di corrente, ma come variazioni del livello di corrente, ovvero come fronti di salita e fronti di discesa. Un fronte di salita si ha quando il voltaggio sale, mentre un fronte di discesa si ha quando il voltaggio scende. Ecco quindi che abbiamo scoperto il baud rate, ovvero la quantità di fronti che si inviano per secondo. Da notare che il baudrate non è necessariamente uguale al bitrate.

Nel caso dei calcolatori, NON si fa multiplexing come abbiamo visto finora: semplicemente, le varie stazioni si danno il turn nel comunicare, secondo un sistema detto Statistical Division Multiplexing, che vuol dire semplicemente che ci si dà il turno. Un altro modo per indicare questa faccenda del parlare a turni è il MAC: Medium Access Control, ovvero il modo per controllare l'accesso al medium, che non è chi comunica coi morti ma il mezzo di trasmissione.

Il DLL, che sta per Data Link Layer, è il formato in cui vengono inviati i singoli blocchi di comunicazione. Come abbiamo visto prima per il misterioso ATM, se non c'è isocronia, le trasmissioni avvengono a blocchi, e ogni blocco deve essere autosufficiente nel senso che deve saper arrivare a destinazione in modo autonomo. Le informazioni per andare in giro per la rete sono distribuite nel blocco in un certo formato, detto appunto DLL. La differenza con le trame del TDM è che le trame sono i pezzi di dati circondati dai bit di sincronimo.

Nelle reti di computer il controllo degli errori è fondamentale, per il motivo che ho detto prima. Occorre quindi anche un sistema per accertarsi che i blocchi siano stati ricevuti senza errori.

Responsabilità del Data Link

  • deve fare il multiplexing finto dei flussi di dati, cioè saper dire: ora parlo io, ora parli tu
  • deve controllare l'accesso al mezzo di trasmissione
  • deve controllare gli errori.

La necessità del multiplexing finto di qualche paragrafo fa nasce da una semplice constatazione amichevole. Se ho due computer, posso benissimo immaginare di tirare un cavo tra uno e l'altro ed è morta lì. Se ho tre computer idem: ho un cavo per ogni coppia di computer. Ma quando comincio ad avere 20 computer, che faccio? Un cavo per ogni coppia è improponibile. Ecco perché si usa un filo solo, e si usa questo multiplexing a turni per decidere chi parla e chi sta zitto: è il controllo di accesso al mezzo.

Protocolli MAC Collision Free

In questi protocolli, si fa in modo che non ci sia del tutto la possibilità che due stazioni si mettano ad inviare contemporaneamente dati sulla rete, rendendoli di fatto inutilizzabili. Occorre quindi stabilire dei turni: la stazione che vuole comunicare "alza la mano" (handrising) e invia a tutte le altre stazioni il segnale che indica la sua volontà di comunicare. Ogni scheda dice la sua in proposito, e quando si sono messe d'accordo quello che vince la trattativa (in base a certe regole) è quello che invia il messaggio.

In questo caso si ha tanto overhead, perché si perde tanto tempo a mandare microframes per queste trattative.

Protocolli MAC a contesa

Con i protocolli MAC a contesa, invece, è ammesso il caso che si parli tutti insieme: nel caso Collision Free si evita a priori la collisione, qui invece la si risolve dopo che è successa.

Slotted Aloha

È il sistema inventato all'Università delle Hawaii, dove usavano le onde radio per collegare i diversi campus presenti su isole diverse. Avevano 1 solo canale, e le collisioni succedevano frequentemente.

La parola slotted si rifà all'idea di voler dare ad ogni stazione un suo tempo di trasmissione che abbia una lunghezza fissa: ognuno può inviare messaggi solo all'inizio del suo slot temporale. Ci sono poche probabilità che due computer si mettano ad inviare segnali nello stesso istante. Però, in caso di collisione, non è affatto stabilito quando una singola stazione potrà di nuovo comunicare.

La rilevazione delle collisioni è semplice: una stazione invia dei dati, e li confronta con i dati che sta ricevendo. Se i due stream coincidono, vuol dire che solo lei sta inviando dati sulla rete. Se invece ci sono discrepanze, vuol dire che c'è una collisione in corso, e che il messaggio è da reinviare.

Un altro problema dello Slotted Aloha è che le onde elettromagnetiche, per quanto veloci, hanno un tempo finito di propagazione, che è di 2*10^8 m/s. Quindi, può accadere che una stazione senta il canale libero quando invece un'altra stazione sta già inviando, proprio perché il segnale radio ci mette tempo a viaggiare da un'isola all'altra, e questo tempo è apprezzabile dalle apparecchiature elettroniche.

CSMA / CD

Carrier Sensing Multiple Access / Collision Detection.
Inventato da Bob Metcalfe, è il sistema che sta alla base di Ethernet. Nella stessa parola Ethernet, si ritrova Ether, cioè etere, ovvero il richiamo alle onde radio del sistema Slotted Aloha.

Carrier Sensing vuol dire che si rileva (sensing) la portante (carrier): quando questa è pulita, vuol dire che posso cercare di trasmettere i dati che voglio. Come con Aloha, si fa il confronto tra dati inviati e ricevuti: se coincidono, allora la trasmissione non è disturbata, altrimenti c'è stata una collisione da qualche parte.

Che cosa avviene quando c'è una collisione? Certo, si deve aspettare un certo po' di tempo per riprovare, ma quanto? Ci sono diverse strategie:

  • non persistent = aspetto un tempo random. Siccome è poco probabile che tutte le stazioni selezioneranno lo stesso tempo random, è quasi come darsi i turni ed evitare le collisioni.
  • 1 persistent = aspetto un tempo determinato
  • p-persistent = una via di mezzo tra le due precedenti.

Da notare che tutti sti protocolli a contesa funzionano bene se il carico totale sulla rete è basso. In effetti, il rapporto tra banda impegnata e non impegnata non deve superare il 30%, nel caso dell'Ethernet. Questo perché altrimenti le collisioni diventerebbero tante, e si sprecherebbe tantissimo tempo. In caso di traffico più elevato occorrono protocolli Collision Free. Una delle ragioni del successo di Ethernet si è avuta nel fatto che ci sono state molte schede a basso costo: costando così poco la banda, non c'era problema anche se la si usava solo al 30%.

Negli ultimi tempi, tuttavia, con gli switch che vedremo più sotto, non c'è quasi più bisogno di gestire le collisioni, quindi la banda viene sfruttata completamente.

Soluzione adattiva

Questo titolo altisonante e vagamente misterioso si riferisce ad un sistema di gestione del traffico di rete che è una specie di misto di quelli visti finora. Non appena si rileva una collisione, si mette il gruppo su cui si è verificata la collisione in modalità Collision Detection, mentre le comunicazioni tra gruppi avvengono con Collision Free. Questo cambio di modalità dipende dalle condizioni del traffico, per questo viene detto adattivo.

Visione unificante

Per tirare un po' le somme di questi sistemi, e vedere dove e come sono utili, viene buono il seguente schema:

  • Si ha basso carico & si vuole poca latenza => Protocollo a contesa
  • Si ha alto carico & si vuole massima efficienza => Collision Free
  • Carico variabile & Problemi assortiti => Ibridi vari

Perché il protocollo a contesa ha il vantaggio di avere poca latenza? Innanzitutto, la latenza è l'intervallo di tempo che passa dalla richiesta di trasmissione all'effettivo invio dei dati. Nei sistemi Aloha e derivati, quando voglio trasmettere trasmetto, saranno gli altri a fermarsi, e tipicamente essendo il carico non superiore al 30% questo avviene quasi sempre: invio subito. Il problema sta invece nell'efficienza: non appena il carico si alza, allora le collisioni diventano così tante che continuo a inviare roba e non arriva mai! Ecco perché se voglio inviare tanta tanta merce, è meglio usare un protocollo Collision Free: quando partono i dati, nessuno li ferma. Lo svantaggio dei sistemi Collision Free al converso sta nella latenza: siccome tutte le stazioni si devono mettere d'accordo per decidere i turni, si perde tanto tempo dal momento in cui io esprimo la volontà di inviare i miei dati a quando effettivamente questi miei dati avranno il turno libero. Più si è in tanti, più ci si mette tempo a mettersi d'accordo.

Ethernet

È proprio vero che il cavo di rete dell'Ethernet sia proprio come l'Ethere? Metcalfe ha usato questo paragone, perché si rifaceva all'Aloha: io trasmetto, e tutti sentono.

Ma c'è una differenza: se tutti sono collegati al cavo, è scontato che tutti sentano il messaggio da me inviato. Nel caso dell'Ethere vero, invece, può anche darsi che ci siano stazioni che NON si accorgano del messaggio perché sono fuori campo! Questo è proprio il caso delle reti Wireless.

È il problema dell' Hidden Terminal: A vuole parlare a B, e sente il campo libero, e invia. Allo stesso tempo anche C vuole mandare a B, e siccome è distante da A e non si accorge che A sta parlando, parla anche lui. In casi come questo Ethernet non funziona, perché cade miseramente uno dei principi base del CSMA/CD: la Collision Detection! Infatti nel caso qui citato non c'è nessuna collision detection perché né A né B se ne accorgono! Ahi ahi ahi!

E non è finita qui: c'è anche il problema inverso, quello della Stazione Esposta. A parla con B, e C vuole parlare con D. Sono tutti nello stesso campo. C vorrebbe parlare, ma sente che il campo è occupato dalla conversazione di A con B, e allora si astiene, mentre in realtà potrebbe benissimo parlare con D perché A sta parlando con B e non con D. Bia bi e e ba be bi e i babebi bi e o babebibo bi e u bu babebibobu.

La soluzione è adottare schemi più complicati. Chi vuole intavolare una discussione invia un messaggio RTS: Request To Send, un avviso di intenzione di voler parlare. Finché non ricevo un CTS, cioè un Clear To Send (libero di parlare) non comincio. Questi messaggi vanno avanti e indietro per tutto il campo, tirando in mezzo anche le stazioni che non si sentono direttamente.


Torna alla pagina di Sistemi per l'elaborazione delle informazioni