Reti di Calcolatori II-B - collegamento

Riassunto gerarchico delle nozioni del corso 2003-2004 di RETI DI CALCOLATORI del Prof. G.Fenu - Università degli Studi di Cagliari, Facoltà di Scienze Matematiche Fisiche Naturali, Dipartimento di Matematica ed Informatica, Corso di Laurea in Informatica

Riferimenti: Andrew S. Tanenbaum, Reti di Calcolatori IV ed., Prentice Hall

• 2. livello di collegamento (data-link layer)
  • funzioni principali
    • 1. fornire un servizio di interfaccia per lo strato network
    • 2. gestire gli errori di trasmissione
    • 3. regolare il flusso dati in modo che i ricevitori lenti non vengano soprafatti da trasmettitori veloci.
  • modalità operativa
    • nella macchina sorgente lo strato data link prende i pacchetti provenienti dallo strato network e li incapsula in frame prima di trasmetterli
    • nella macchina di destinazione lo strato data link prende i frame provenienti dallo strato fisico e li scompone prima di trasmetterli al livello network
  • frame, è composto da:
    • intestazione (header)
    • carico utile (payload)
    • coda (trailer)
  • servizi
    • possono essere diversi e cambiano a seconda del sistema
    • la scelta del servizio dipende sopratutto dal mezzo fisico
    • i tre servizi comunemente offerti sono:
      • 1. servizio unacknowledged senza connessione
        • non viene stabilita alcuna connessione logica
        • la perdita di un frame non viene rilevata ne corretta
        • utilizzato per canali di trasmissione affidabili (bassa frequenza degli errori in trasmissione) o per trasmissioni real-time (voce o video)
        • utilizzato dalla maggior parte delle LAN
      • 2. servizio acknowledged senza connessione
        • non viene stabilita alcuna connessione logica
        • ciascun frame è inviato individualmente e ne viene fatto l'acknowledge (conferma della ricezione)
        • un frame può essere rispedito se non arriva entro un determinato intervallo di tempo
        • un acknowledgement perso può far si che il frame venga trasmesso e ricevuto più volte (per questo ogni frame ha un suo numero di sequenza che serve ad evitare che duplicati vengano passati allo strato di network)
        • utilizzato per canali di trasmissione non affidabili (reti wireless)
      • 3. servizio acknowledged orientato alla connessione
        • stabilisce una connessione sorgente-destinazione prima del trasferimento dei dati
        • ogni frame trasmesso viene numerato così che possa essere ricevuto nell'ordine corretto (flusso di bit affidabile)
        • la trasmissione avviene in tre fasi:
          • 1. viene stabilita la connessione
            • sorgente e destinazione inizializzano variabili e contatori per tener traccia dei frame ricevuti e persi
          • 2. uno o più frame vengono trasmessi
          • 3. viene rilasciata la connessione
            • vengono liberate le variabili, i buffer e le altre risorse usate per mantenere la connessione
    • acknowledgement
      • nello strato data-link non è un requisito obbligatorio in quanto può essere implementato nello strato network (in quest'ultimo caso però in caso di errore verrà rispedito l'intero pacchetto)
  • suddivisione in frame
    • consiste nel prendere il flusso di bit dallo strato fisico e di suddividerli in una serie discreta di frame per poi servire lo strato network
    • non esiste alcuna garanzia che il flusso di bit proveniente dallo strato fisico sia esente da errori (si possono ricevere un numero diverso di bit e con valori diversi da quelli trasmessi)
    • tipicamente lo strato data-link aggiunge ai frame un checksum che verrà ricalcolato e confrontato a destinazione così da verificare l'eventuale presenza di errori
    • metodi per la suddivisione dei frame (alcuni):
      • 1. conteggio dei caratteri
        • usa un campo nell'intestazione per indicare il numero di caratteri nel frame
        • un errore di trasmissione può alterare il conteggio dei caratteri rendendo impossibile il ritrovamento dell'inizio del frame successivo
      • 2. flag byte con byte stuffing
        • introduce un byte speciale (flag byte) all'inizio (STX = Start of TeXt) ed alla fine di ogni frame (ETX = End of TeXt)
        • due flag byte consecutivi indicano la fine di un frame e l'inizio di un'altro
        • byte stuffing o character stuffing
          • uno speciale byte di escape (ESC o DLE = Data Link Escape) viene aggiunto prima di ogni occorrenza accidentale del flag byte o dell'ESC stesso nei dati, così che non vengano scambiati per un delimitatore
          • la rimozione dei byte di riemimento (stuffing) in ricezione è detta destuffing
        • ha lo svantaggio di essere legato a caratteri di 8 bit
      • 3. flag di inizio e fine con bit stuffing
        • è la tecnica magiormente usata
        • permette di creare data frame che contengono sia un numero arbitrario di bit, sia codifiche di carattere con un numero arbitrario di bit
        • ogni frame comincia e finisce con un gruppo speciale di bit (01111110), che in sostanza è un flag byte
        • bit stuffing
          • lo strato sorgente aggiunge uno 0 ogni cinque 1 consecutivi trovati nel carico utile
        • destuffing
          • lo strato destinazione riconosce e rimuove i bit di stuffing (uno 0 preceduto da cinque 1)
      • 4. violazioni della codifica dello strato fisico
        • si applica solo alle reti la cui codifica contiene delle ridondanze a livello fisico
        • il frame viene delimitato usando delle codifiche non utilizzate per trasmettere 1 e 0 (diverso voltaggio, diverse combinazioni di segnali)
      • questi metodi possono anche essere combinati per aumentare la ridondanza
  • controllo degli errori
    • è necessario per assicurarsi che arrivino tutti i frame, e che arrivino nell'ordine corretto (nei servizi con connessione)
    • i controlli d'errore impattano sulla banda
    • tipicamente il protocollo richiede che la destinazione mandi indietro degli speciali frame di controllo , che contengono un acknowledgment positivo o negativo relativamente ai frame ricevuti
    • per evitare l'attesa infinita di un mancato acknowledgement, viene introdotto un timer che parte all'invio di ogni frame
      • il timer viene impostato su un tempo abbastanza lungo da permettere che il frame raggiunga la destinazione, venga elaborato e l'acknowledgement possa ritornare indietro
      • se il timer scade senza che sia stato ricevuto l'ack, il frame viene ritrasmesso
    • i frame vengono numerati progressivamente per poter scartare i frame ripetuti e per poter ricostruire la sequenza originale
  • controllo del flusso
    • meccanismi che regolano la velocità della sorgente e della destinazione per evitare che un trasmettitore veloce possa sovraccaricare un ricevitore lento
    • si utilizzano 2 approcci:
      • controllo di flusso tramite feedback (retroazione)
        • la destinazione manda indietro alla sorgente delle informazioni per autorizzarla ad inviare altri frame o per informarla dello stato
      • controllo di flusso tramite limitazione della velocità
        • sono raramente unsati nello strato data-link
        • il protocollo contiene al suo interno un meccanismo che limita la velocita alla quale la sorgente può trasmettere i dati, senza alcun feedback dalla destinazione
  • rilevazione e correzione degli errori
    • gli errori dipendono prevalentemente dal mezzo fisico, sono quindi maggiormente presenti nelle reti con doppino di rame e nelle reti wireless
    • gli errori possono presentarsi sia in maniera distribuita che concentrati a grappoli (errori burst)
    • codeword (parola di codice)
      • unità di n bit costituita da m bit di dati ed r bit di controlli (n = m + r)
    • distanza di Hamming (Hamming, 1950)
      • numero di bit ( d ) diversi tra due codeword
      • si ottiene facendo l'OR esclusivo tra le due codeword
      • se due codeword hanno distanza di Hamming d , saranno necessari d errori su singoli bit per convertire una sequenza nell'altra
    • distanza di Hamming della codifica
      • distanza di Hamming tra le due codeword con distanza minima prese tra tutte le codeword legali (sottoinsieme di tutte le le 2 ⁿ possibili codeword)
      • le proprietà di rilevazione e correzione degli errori di una codifica dipendono dalla sua distanza di Hamming
    • esistono due strategie di base per la gestione degli errori:
      • 1. codifica a correzione d'errore (forward error correction)
        • consiste nell'includere in ciascun blocco dati trasmesso una quantità di informazioni ridondanti, tale da poter permettere di ricostruire il contenuto del blocco in caso d'errore
        • è utilizzata tipicamente nelle reti non affidabili come le reti wireless (notoriamente rumorose) in cui la richiesta di ritrasmissione potrebbe anch'essa essere in errore
        • per correggere d errori è necessaria una codifica con distanza di Hamming di almeno 2d + m
        • codifica di Hamming per errori singoli
          • i bit della codeword vengono numerati consecutivamente a partire da 1 per il primo a sinistra e si dividono in:
            • bit di controllo
              • sono gli r bit numerati con potenze di 2 (1, 2, 4, 8, 16, ...)
            • dit di dati
              • sono gli m bit rimanenti (3, 5, 6, 7, 9, ...)
          • ogni bit di controllo forza la parità di alcuni gruppi di bit incluso se stesso ad essere pari (o dispari)
          • un bit può essere incluso in diversi calcoli di parità
          • un bit di dati è controllato solo dai bit di controllo presenti nella sua espansione (es.: 11 è controllato da 1, 2 e 8)
          • quando viene ricevuta una codeword la destinazione inizializza il contatore a zero, esamina poi ogni bit di controllo k per verificare la parità ed in caso negativo aggiunge k al contatore
          • se k è a zero al termine del controllo, la codeword è giusta, altrimenti il numero del contatore indica il bit in errore
        • codifica di Hamming per errori a raffica (burst)
          • per poter correggere degli errori burst le codeword vengono disposte su una matrice di k righe
          • la matrice viene trasmessa e ricostruita per colonne così da poter correggere errori di lunghezza k (un bit per ogni codeword)
          • questo metodo usa kr bit di controllo per rendere immuni km bit di dati agli errori burst di lunghezza minore o uguale a k
      • 2. codifica a rilevazione d'errore
        • consiste nell'includere in ciascun blocco abbastanza ridondanza da permettere alla destinazione di capire se c'è stato un'errore
        • su canali affidabili (fibre ottiche, 10 ^-6 - 10 ^-8 errori per bit) è più efficiente usare questa tecnica limitandosi a ritrasmettere i blocchi corrotti
        • per rilevare d errori è necessaria una codifica con distanza di Hamming di almeno d + 1
        • bit di parità
          • si aggiunge un 1 o uno 0 al blocco dati in modo che il numero totale degli 1 sia sempre pari (o dispari)
          • un codice con bit di parità ha distanza di Hamming d=2, infatti ogni errore su un singolo bit produce una codeword con la parità sbagliata
          • può essere usata per rilevare errori su un singolo bit
          • la probabilità che venga intercettato un errore burst di lunga estensione è 0,5
        • bit di parità per errori burst
          • si trasmettono matrici di k righe ed n colonne alle quali viene aggiunta una riga di bit di parità per le colonne
          • è possibile rilevare errori burst di lunghezza n
          • la probabilità che un blocco in errore venga accettato è 2 ^-n
        • codifica polinomiale (CRC - Cyclic Redudancy Check, cotrollo ciclico di ridondanza)
          • CRC-CCITT = CRC-16 = x ¹⁶ + x ¹⁵ + ... + x ² + x ¹ + 1
          • un frame di k bit è visto come una lista di coefficienti per un polinomio di grado k-1 (con k termini che variano da x ^k-1 a x ⁰
          • l'aritmetica dei polinomi si gestisce in modulo 2, l'addizione e la sottrazione corrispondono all'OR esclusivo
          • la sorgente e la destinazione devono concordare anticipatamente su un polinomio generatore G(x) che dovrà avere i bit di ordine più alto e più basso uguali ad 1
          • ad un frame di m bit corrisponde un polinomio M(x) più lungo di G(x)
          • in coda al frame viene aggiunto un checksum in modo che il polinomio rappresentato dal frame sia divisibile per G(x)
          • le destinazione proverà a dividere il frame per G(x) e segnalerà un errore nel caso che ci sia resto
          • Peterson e Brown (1961) hanno dimostrato che basta costruire un circuito a registro di shift per controllare in hardware tutti i checksum (così è implementato nella quasi totalità delle LAN)
          • per rilevare r errori occorre una codifica polinomiale con r bit di controllo
  • protocolli data-link elementari
    • caratteristiche generali
      • lo strato data-link sorgente accetta i pacchetti dallo strato network e li incapsula in un frame agiungendogli un'intestazione (header) ed una coda (trailer) per poi trasmetterli allo stato data-link dell'altra macchina.
      • i frame hanno tipicamente la seguente struttura:
        • header (intestazione)
          • kind (tipo): indica se ci sono dati nel frame per distinguere i frame di controllo da quelli dati
          • seq (sequenza): numero di sequenza del frame per l'ordinamento, può anche essere circolare
          • ack (acknowledgment): utilizzato per inviare l'acknowlegement per il frame ricevuto in precedenza
        • data (dati)
          • info: contiene un singolo pacchetto di dati che può essere omesso nei frame di controllo
        • trailer (coda)
          • checksum (CRC): informazioni per la rilevazione o correzione degli errori
    • 1. protocollo simplex senza restrizioni
      • è un protocollo non realistico (utopia)
      • i dati sono trasmessi in una sola direzione (simplex)
      • il canale di comunicazione non perde mai nessun frame (canale privo di errori)
      • gli strati network della sorgente e della destinazione sono sempre pronti
      • il tempo per elaborare i dati può essere ignorato (velocità infinita)
      • il buffer per immagazzinare i dati è infinito
      • i frame sono costituiti solo dal campo info (non ci sono controlli di errore e di flusso)
      • il protocollo consiste di due distinte procedure:
        • mittente (nello strato data-link sorgente)
          • il mittente invia i dati alla massima velocità possibile dall'interno di un loop infinito che esegue tre azioni:
            • andare a prendere il pacchetto dallo strato network (sempre pronto a fornirlo)
            • costruire un frame in uscita
            • instradare il frame
        • destinatario (nello strato data-link destinazione)
          • aspetta che arrivi un frame
          • rimuove il frame dal buffer hardware
          • estrae i dati dal frame e li passa allo stato network
    • 2. protocollo simplex stop-and-wait (fermati ed aspetta)
      • i dati sono trasmessi in una sola direzione (simplex) ma il canale deve essere bidirezionale per poter trasmettere gli acknowledgement di ritorno (half duplex)
      • il canale di comunicazione non perde mai nessun frame (canale privo di errori)
      • la velocità di elaborazione è finita
      • il buffer per immagazzinare i dati è limitato
      • occorre controllare il flusso (evitare che il mittente veloce inondi il ricevente lento)
      • in assenza di un buffer di accodamento, il mittente dovrà astenersi dal trasmettere un nuovo frame fino a quando il precedente non verrà prelevato dallo strato fisico del destinatario (stop-and-wait)
      • dopo il ricevimento di un frame il destinatario manderà indietro un acknowledgement attraverso un frame senza dati (dummy) per abilitare il mittente all'invio di un nuovo frame
    • 3. protocollo simplex per canali rumorosi
      • i dati sono trasmessi in una sola direzione (simplex) ma il canale deve essere bidirezionale per poter trasmettere gli acknowledgement di ritorno (half duplex)
      • il canale di comunicazione è realistico, i frame possono arrivare danneggiati o perdersi
      • la velocità di elaborazione è finita
      • il buffer per immagazzinare i dati è limitato
      • occorre controllare sia il flusso che gli errori
      • il destinatario controllerà il frame attraverso il checksum e segnalerà al mittente l'arrivo di un frame corretto con un acknowledgement
      • il destinatario non invierà alcun acknowledgement per i frame non ricevuti o in errore
      • il mittente farà partire un timer all'invio di ogni frame e ritrasmetterà il frame se non riceverà un acknowledgement prima dello scadere
      • per evitare che il destinatario possa accettare frame ripetuti (a seguito della perdita di un acknowledgment), il destinatario aggiungerà sempre un numero di sequenza (seq) nell'header di ogni frame
      • in questo protocollo è sufficiente un numero di sequenza di un bit per distinguere il frame corrente dal precedente e dal successivo
      • questo protocollo differisce dai precedenti perchè sia la sorgente che la destinazione hanno delle variabili da ricordare durante lo stato di attesa
      • i protocolli in cui la sorgente aspetta un acknowledgement positivo prima della ritrasmissione sono detti:
        • PAR (Positive Acknowledgement with Retransmission)
        • ARQ (Automatic Repeat reQuest)
  • protocolli a finestra scorrevole (sliding window)
    • caratteristiche generali
      • usano un canale full-duplex (due canali fisici simplex separati, uno per la ricezione ed uno per l'invio) per poter trasmettere in entrambe le direzioni
      • i frame di dati vengono mescolati con quelli di acknowledgement dai quali si distinguono grazie al campo kind nell'header del frame
      • piggybacking
        • gli acknowledgement possono essere ritardati per poter essere inseriti nel campo ack del successivo frame in uscita (così da risparmiare un frame per un uso più efficiente della banda)
        • se non ci sono frame disponibili per il piggybacking entro un dato intervallo temporale (si usa un timer ausiliario più corto di quello per i frame di dati), il protocollo invia un frame di acknowledgement separato
      • in tutti i protocolli sliding window i frame in uscita contengono un numero di sequenza (seq) che va da 0 ad un valore massimo (generalmente 2 ⁿ - 1, per far entrare seq in un campo di n bit)
      • finestra di invio (sending window)
        • ad ogni istante la sorgente tiene traccia dei numeri di sequenza dei frame che è autorizzata ad inviare
        • il numero di sequenza nella finestra di invio rappresenta i frame trasmessi o in transito che non hanno ancora ricevuto l'acknowledgement corrispondente, e pertanto andranno mantenuti in memoria (saranno necessari n buffer ed n timer per una finestra di dimensioni n)
        • ad ogni nuovo pacchetto proveniente dallo strato network viene assegnato un numero di sequenza progressivo incrementando di uno il limite superiore della finestra
        • ad ogni arrivo di acknowledgement il limite inferiore della finestra viene incrementato di uno
        • se la finestra cresce fino alla sua massima dimensione, lo strato data-link è costretto a chiudere forzatamente lo strato network finchè non si libera almeno un buffer
      • finestra di ricezione (receiving window)
        • ad ogni istante la destinazione tiene traccia dei numeri di sequenza dei frame che può accettare
        • ogni frame al di fuori della finestra verrebbe rigettato senza commenti
        • quando viene ricevuto un frame con numero di sequenza uguale al limite inferiore della finestra avvengono le seguenti cose:
          • il frame viene passato allo strato network
          • viene generato un acknowledgement
          • la finestra viene ruotata di uno
        • questa finestra rimane sempre alla dimensione iniziale
        • se la finestra ha dimensione 1 lo strato data-link accetterà solo frame in ordine
        • con finestre più grandi di 1 lo strato data-link potrà accettare anche frame non in ordine ma li passerà comunque in ordine allo strato network
      • le dimensioni delle finestre di invio e ricezione possono essere diverse tra loro e possono anche essere variabili nel tempo
    • 1. protocollo sliding window ad 1 bit
      • la finestra ha dimensione 1, usa quindi il metodo stop-and-wait (invia solo dopo aver ricevuto l'acknowledgement del frame precedente)
      • il campo acknowledgement contiene il numero dell'ultimo frame ricevuto senza errori
      • nessuna combinazione di pacchetti persi o timeout prematuri può causare la trasmissione di pacchetti duplicati allo strato network, la perdita di pacchetti oppure situazioni di deadlock
      • quando sia la sorgente che il destinatario tentano di inviarsi contemporaneamente il primo frame si verifica un caso particolare in cui la metà dei frame contengono duplicati, anche quando non ci sono errori di trasmissione
    • 2. protocollo sliding window a più bit (pipelining, instradamento nel tubo)
      • si utilizza nei sistemi con un forte ritardo di propagazione (sistemi satellitari) ovvero quando il prodotto tra la banda (b) ed il ritardo di propagazione (R) è particolarmente grande (capacità della pipeline)
      • per evitare lo spreco della banda durante le attese degli aknowledgement la sorgente invia un blocco w di frame prima di bloccarsi
      • la dimensione w viene scelta in modo da permettere alla sorgente di trasmettere per un tempo pari al tempo totale di transito senza arrivare a riempire la finestra
      • per il ripristino degli errori in presenza di pipelining sono disponibili 2 approcci base:
        • protocollo che usa go back n (indietro di n)
          • la destinazione scarta tutti i frame successivi a quello in errore senza inviarne l'acknowledgment
          • questa strategia corrisponde ad una finestra di ricezione di dimensione 1
          • la pipeline si svuoterà in attesa che scatti il timeout della sorgente, dopo di che verrà reinviato il blocco dei frame a partire da quello danneggiato
          • questa tecnica può far perdere molta banda se la frequenza degli errori è alta
        • protocollo a ripetizione selettiva
          • il frame in errore viene scartato ed i frame successivi vengono inseriti in un buffer
          • questa strategia corrisponde ad una finestra di ricezione di dimensione maggiore di 1
          • quando la sorgente va in timeout viene ritrasmesso solo il frame senza l'acknowledgement
          • quando la destinazione riceve il frame corretto passa in sequenza tutto il blocco dei frame nel buffer allo strato network ed invia un'ack relativo all'ultimo frame corretto passato allo strato network
          • NAK (Not AcKnowledgement)
            • viene inviato dalla destinazione alla sorgente in caso di errore del frame (checksum errata o frame fuori sequenza)
            • i NAK stimolano la ritrasmissione prima che il timer corrispondente scatti, e quindi aumentano le performance
          • per evitare che lo stesso blocco di frame possa essere accettato più volte a causa della perdita di tutti gli acknowledgement corrispondenti, la dimensione massima della finestra dovrebbe essere uguale alla metà della sequenza dei numeri
  • specifica e verifica dei protocolli
    • data la complessità dei protocolli sono state sviluppate delle tecniche matematiche per la loro specifica e verifica:
      • modelli a stati finiti
        • implementa il concetto di macchina a stati finiti
        • ogni macchina protocollo (sorgente o destinazione) si trova sempre in uno specifico stato per ogni istante di tempo
        • stato di una macchina
          • è dato dal valore di tutte le sue variabili incluso il protocollo
          • gli stati possono essere raggruppati per facilitare l'analisi
          • il numero degli stati è 2 ⁿ , dove n è il numero di bit necessari a rappresentare tutte le variabili prese insieme
        • stato del sistema
          • è la combinazione di tutti gli stati delle due macchine protocollo e del canale
        • partendo da ogni stato ci sono zero o più possibili transizioni verso altri stati in occasione degli eventi
        • eventi tipici per macchina protocollo
          • invio di un frame
          • arrivo di un frame
          • timeout di un timer
          • generazione di un interrupt
          • ...
        • eventi tipici per canale
          • inserimento di un nuovo frame
          • perdita di un frame dovuta al rumore
        • grafo orientato
          • è possibile costruirne uno attraverso la descrizione completa delle macchine protocollo e delle caratteristiche del canale
          • i nodi rappresentano gli stati
          • gli archi rappresentano le transizioni
        • stato iniziale
          • particolare stato corrisondente alla descrizione del sistema nel momento in cui comincia a lavorare (o tempo prossimo a quello considerato iniziale)
          • dallo stato iniziale è possibile raggiungere altri stati con una opportuna sequenza di transizioni
        • analisi di raggiungibilità
          • tecnica utilizzata per determinare quali stati sono raggiungibili a partire dallo stato iniziale
          • serve a determinare la correttezza dei protocolli
        • modello di un protocollo
          • può essere considerato come una quadrupla:
            • S è l'insieme degli stati dei processi del canale
            • M è l'insieme dei frame che possono essere scambiati su un canale
            • I è l'insieme degli stati iniziali dei processi
            • T è l'insieme delle trasizioni fra stati
        • deadlock
          • situazione in cui il protocollo non può proseguire nelle sue attività indipendentemente dalla sequenza degli eventi
      • modelli a rete di Petri
        • una rete di Petri ha 4 elementi costitutivi:
          • posizioni (posti)
            • stato nel quale si può trovare il sistema o una sua parte
            • vengono indicate con dei cerchi
          • transizioni
            • corrispondono agli eventi
            • indicano le transizioni fra le posizioni
            • sono indicate con delle barrette verticali o orizzontali
            • hanno zero o più archi di input ed output
            • può essere abilitata se esiste almeno un indicatore di input per ognuna delle sue posizioni di input
            • una transizione abilitata può scattare a piacimento (in maniera non deterministica) per togliere un indicatore da ogni posizione di input e metterlo in ogni posizione di output
            • gli indicatori non saranno conservati se il numero degli input è differente da quello di output
          • archi
            • sono orientati e connettono le posizioni con le transizioni
          • indicatori (token)
            • indicano in quale posizione si trova il sistema
            • si indicano con dei pallini all'interno del cerchio indicante la posizione
        • il concetto di deadlock è equivalente a quello per le macchine a stati finiti
        • le reti di petri possono essere convenientemente rappresentate in una forma algebrica che assomiglia ad una grammatica
          • ogni transizione contribuisce ad una regola della grammatica
          • ogni regola specifica le posizioni di input ed output della transizioni
  • esempi di protocolli data link
    • HDLC (High-level Data Link Control, controllo del data link ad alto livello)
      • standard ISO derivante dal protocollo SDLC (Syncronous Data Link Control) usato originariamente nell'ambiente IBM dei mainframe
      • dall'SDLC deriva lo standard ANSI ADCCP (advanced Data Communication Control Procedure)
      • dall'HDLC deriva lo standard CCITT LAP (Link Access Procedure) a sua volta modificato in LAPB per maggiore compatibilità con le successive versioni di HDLC
      • protocollo orientato ai bit che usa il bit stuffing per la trasparenza dei dati
      • protocollo molto usato ma ben lontano dall'essere perfetto
      • formato del frame
        • start flag (8 bit = 01111110)
          • indica l'inizio del frame
        • address (8 bit)
          • indirizzo del terminale a cui è destinato il frame
        • control (8 bit)
          • contiene i numeri di sequenza, gli acknowledgment ed altre informazioni
        • data (>= 0 bit e tipicamente < 8500 byte)
          • può contenere qualunque tipo di informazione
          • può avere lunghezza arbitraria
        • checksum (16 bit)
          • codice di ridondanza ciclica (CRC-16 o CRC-CCITT) per il controllo degli errori
          • l'efficienza diminuisce con il crescere del campo data
        • end flag (8 bit = 01111110)
          • indica la fine del frame
      • nelle linee punto-punto quando non ci sono dati da trasmettere viene continuamente trasmessa le sequenza di flag
      • il frame di lunghezza minima contiene tre campi per un totale di 32 bit (esclusi i flag)
      • i frame possono essere di tre tipi:
        • informazione (information)
          • per la trasmissione dati
          • control : 0 (1 bit) + Seq (3 bit) + P/F (1 bit) + Next (3 bit)
        • supervisione (supervisory)
          • per comandare diverse modalità di ritrasmissione
          • control : 1 (1 bit) + 0 (1 bit) + Type (2 bit) + P/F (1 bit) + Next (3 bit)
        • senza numero (unnumbered)
          • per finalità di controllo o per trasportare il traffico di servizi senza connessione e non affidabili
          • control : 1 (1 bit) + 1 (1 bit) + Type (2 bit) + P/F (1 bit) + Next (3 bit)
      • il protocollo usa una finestra scorrevole con un numero di sequenza di 3 bit (7 frame)
      • elementi del control:
        • Seq (sequenza)
          • indica il numero di sequenza
        • Next (successivo)
          • è utilizzato per il piggybacking dell'acknowledgement (indica il numero del frame che ci si aspetta e non quello ricevuto)
        • P/F (Poll/Final)
          • è utilizzato quando un computer (o un concentratore) vuole interrogare un gruppo di terminali
          • se P/F è impostato a P (Poll) il computer invita il terminale a mandare i dati
          • tutti i frame inviati al terminale hanno il bit P/F impostato a P tranne l'ultimo impostato ad F
          • può essere utilizzato per forzare l'atra macchina ad inviare immediatamente un frame di supervisione senza aspettare di avere traffico per il piggybacking
          • in alcuni rari casi è utilizzato con i frame senza numero
        • Type (tipo)
          • tipo 0
            • frame di acknowledgement (RECEIVE READY, ricevi e stai pronto), indica il prossimo numero di sequenza attesa
          • tipo 1
            • frame di tipo acknowledgement negativo (NAK, REJECT)
            • il campo Next indicherà il primo frame della sequenza non ricevuto correttamente
          • tipo 2
            • RECEIVE NOT READY (ricevi e fermati)
            • serve per generare l'acknowledgement di tutti i frame fino a Next (escluso)
            • viene usato per indicare problemi temporanei con la destinazione (es.: riempimento del buffer)
          • tipo 3
            • SELECTIVE REJECT (rifiuta selettivamente)
            • richiede la ritrasmissione solo del frame specificato
      • i 5 bit del control possono anche essere usati per comunicare particolari situazioni:
        • DISC (DISConnect, disconnetti)
          • permette ad una macchina di annunciare il fatto che sta andando fuori linea
        • SNRM (Set Normal Response Mode, imposta il modo di risposta normale)
          • permette ad una macchina di annunciare il suo ritorno in linea
        • SNRME
          • analogo a SNRM ma abilita un formato esteso del frame con 7 bit per Seq
        • SABM (Set Asyncronous Balanced Mode, imposta il modo asincrono bilanciato)
          • esegue un reset della linea e dichiara che entrambe i soggetti della comunicazione sono di pari grado
        • SABME
          • analogo a SABM ma abilita un formato esteso del frame con 7 bit per Seq
        • FRMR (FRaMe Reject, rifiuta i frame)
          • usato per indicare un frame con il checksum corretto ma dalla sematica impossibile
          • contengono un campo dati di 24 bit con l'indicazione degli errori nel frame con la semantica impossibile
        • UA (Unnumbered Acknowledgement, acknowledgement senza numero)
          • acknowledgement per i frame di controllo
        • UI (Unnumbered Information, informazione non numerata)
          • frame di controllo destinato solo allo strato data link
    • SLIP (Serial Line Internet Protocol) - RFC 1055, RFC 1144
      • nato nel 1984, è il più vecchio protocollo data link dell'Internet Protocol Suite
      • nacque per collegare via modem macchine Sun ad Internet
      • spedisce sulla linea pacchetti IP terminati con il byte 0xC0
      • usa character stuffing
      • ha diversi limitazioni:
        • non c'è controllo degli errori
        • supporta solo IP e solo per indirizzi statici
        • non è uno standard ufficiale di Internet
    • PPP (Point to Point Protocol) - RFC 1661, RFC 1662, RFC 1663
      • usato da Internet per la gestione del traffico da router a router e quello tra gli utenti di casa e gli ISP
      • è un meccanismo di framing multiprotocollo adatto alla trasmissione dati via modem, linee seriali HDLC, SONET ed altri strati fisici
      • principali funzionalità e caratteristiche:
        • rilevazione degli errori
        • supporto per più protocolli
        • supporta la compressione dell'intestazione
        • possibilità di negoziare gli IP al momento della connessione
        • possibilità di effettuare l'autenticazione
        • metodo di framing che permette di delimitare in modo non ambiguo la fine di un frame e l'inizio del successivo
        • LCP (Link Control Protocol, protocollo di controllo del collegamento)
          • protocollo di collegamento per gestire la connessione, il test della linea, negoziare le opzioni di collegamento e gestire la disconnessione in modo pulito quando la linea non serve più.
          • supporta sia circuiti asincroni che sincroni
          • gestisce sia codifiche orientate ai bit che ai byte
          • non si occupa delle opzioni negoziate ma solo del meccanismo di negoziazione
          • l'RFC 1661 definisce 11 tipi di frame LCP:
            • configure request (I -> R)
              • elenca valori e scelte possibili
            • configure ack (R -> I)
              • tutte le scelte sono accettate
            • configure nak (R -> I)
              • alcune scelte non sono accettate
            • configure reject (R -> I)
              • alcune scelte non sono negoziabili
            • terminate request (I -> R)
              • richiesta di chiudere la linea
            • terminate ack (R -> I)
              • OK, linea chiusa
            • code reject (R -> I)
              • ricevuta una richiesta sconosciuta
            • protocol reject (R -> I)
              • richiesto un protocollo sconosciuto
            • echo request (I -> R)
              • prego rimandare indietro questo frame
            • echo reply (R -> I)
              • ecco il frame rimandato indietro
            • discard request (I -> R)
              • scartare questo frame (per test)
        • modalità per negoziare le opzioni relative allo strato network in modo indipendente dalla sua implementazione
          • il metodo scelto avrà un diverso NCP (Network Control Protocol) per ogni strato network supportato
      • esempio di connessione tramite modem
        • il PC chiama il router del provider tramite il modem
        • stabilita la connessione fisica, il PC manda al router una serie di pacchetti LCP nel campo payload di uno o più frame PPP per negoziare i parametri PPP da usare
        • dopo aver stabilito i parametri PPP, vengono inviati una serie di pacchetti NCP per configurare lo strato network
        • tipicamente un PC vuole usare TCP/IP e quindi l'ISP gli assegnerà un IP (risorsa limitata) solo per la durata della connessione
        • il PC è diventato ora a tutti gli effetti un host connesso ad Internet
        • al termine della comunicazione LCP si prende carico della disconnessione data link
        • successivamente verrà chiusa la connessione modem e rilasciata la linea fisica
      • frame PPP
        • somiglia all'HDLC ma diversamente da questo, PPP è orientato ai byte
        • usa il byte stuffing sulle linee telefoniche così che tutti i frame sono costituiti da un numero intero di byte
        • possono essere trasferiti anche su linee SONET o linee orientate ai bit con protocollo HDLC
        • formato del frame
          • start flag (1 byte = 01111110)
            • indica l'inizio del frame
            • se compare nel campo payload si usa il byte stuffing
          • address (1 byte = 11111111)
            • indica che tutte le stazioni devono accettare il frame
          • control (1 byte = 00000011)
            • indica un frame senza numero
          • protocol (1 o 2 byte)
            • indica quale tipo di pacchetto è contenuto nel campo payload
            • i protocolli che iniziano con un bit a 0 sono protocolli di strato network (IP, IPX, OSI, CLNP, XNS)
              • i protocolli che iniziano con un bit a 1 sono usati per negoziare altri protocolli (includono LCP ed un diverso NCP per ogni strato network supportato)
          • payload (numero variabile di byte)
            • contiene i dati da trasmettere
            • ha lunghezza variabile fino ad un valore massimo che può essere negoziato con LCP durante l'inizializzazione della connessione
            • la lunghezza solita è di 1500 byte
            • se necessario ci può essere un riempimento del campo dopo i dati
          • checksum (2 o 4 byte)
            • la dimensione può essere negoziata a 4 byte con LCP
          • end flag (1 byte = 01111110)
            • indica la fine del frame
        • i campi address e control sono sempre costanti e possono essere omessi previa negoziazione LCP per risparmiare 2 byte per frame
      • fasi di connessione:
        • il protocollo comincia nello stato DEAD
        • dopo aver stabilito una connessione fisica la linea si sposta allo stato ESTABILISH
        • inizia la negoziazione LCP che se ha successo porta allo stato AUTHENTICATE
        • sorgente e destinazione possono controllare la loro reciproca identità
        • quando si entra nella fase NETWORK, viene invocato l'appropriato protocollo NCP per configurare lo strato
        • se la configurazione ha successo si raggiunge OPEN e può cominciare il trasporto dei dati
        • quando il trasporto è finito la linea si sposta su TERMINATE e da li torna a DEAD
    • ATM Data Link
      • formato del frame
        • header (5 byte)
          • VC (4 byte)
          • header checksum (1 byte)
        • data (48 byte)
      • supporta le seguenti modalità:
        • trasmissione asincrona
          • le celle vengono inviate appena sono pronte
        • trasmissione sincrona
          • l'assenza di celle per il sincronismo viene compensata da delle celle oziose (idle cells)
      • TC (Transmission Convergence)
      • OAM (Operation And Manteinance)
        • celle di controlllo