Algoritmi di compressione delle immagini senza perdita. Cos'è una finestra scorrevole

Una delle tecniche più naturali utilizzate per stabilire una trasmissione affidabile è l'handshaking. Il mittente invia i dati e attende fino a quando non riceve una ricevuta che conferma che i suoi dati sono pervenuti in modo sicuro al destinatario. Il protocollo TCP utilizza caso speciale stretta di mano - algoritmo della finestra scorrevole. Prima di procedere ad una considerazione dettagliata dell'implementazione di questo algoritmo nel protocollo TCP, è molto utile discuterne da un punto di vista generale.

Esistono quindi due metodi per organizzare il processo di scambio delle ricevute: il metodo della fonte inattiva e il metodo della finestra scorrevole.

Il metodo della sorgente inattiva richiede che la sorgente che ha inviato il frame (in questo caso indipendentemente dal nome utilizzato per l'unità di dati trasmessi), attendeva una ricevuta dal ricevente che informava che il frame originale era stato ricevuto e che i dati in esso contenuti erano corretti, e solo dopo inviava il frame successivo (o ripeteva il frame distorto uno). Se la ricevuta non è arrivata durante il timeout, il frame (o la ricevuta) viene considerato perso e la sua trasmissione viene ripetuta. Sulla fig. 1 mostra che il secondo frame viene inviato solo dopo l'arrivo di una ricevuta che conferma la consegna del primo frame. Tuttavia, c'è stata una lunga pausa nell'invio del terzo frame successivo.

Durante questa pausa, la sorgente è stata costretta a ritrasmettere il frame 2, poiché la ricevuta della prima copia è andata persa. È chiaro che con un tale algoritmo di funzionamento della sorgente, il lato ricevente deve essere in grado di riconoscere i frame duplicati e liberarsene.

Riso. 1. Metodo della sorgente inattiva

È abbastanza ovvio che quando si utilizza questo metodo le prestazioni di scambio dei dati sono inferiori a quelle potenzialmente possibili: il trasmettitore potrebbe inviare il frame successivo immediatamente dopo aver inviato quello precedente, ma deve attendere l'arrivo della ricevuta.

Il secondo metodo è chiamato metodo della finestra scorrevole. In questo metodo, per aumentare la velocità di trasferimento dei dati, la sorgente può trasmettere un certo numero di trame in modalità continua, cioè alla massima velocità possibile per la sorgente, anche prima di ricevere le ricevute di tali trame. Il numero di frame che possono essere trasmessi in questo modo è chiamato dimensione della finestra.

La figura 2 illustra l'applicazione di questo metodo per una finestra di 5 frame. Al momento iniziale, quando non è stato ancora inviato alcun frame, la finestra definisce un intervallo di numeri di frame da 1 a 5 inclusi. La sorgente inizia a trasmettere frame e dopo un po' di tempo riceve le ricevute in risposta. Per semplicità, supponiamo che gli scontrini arrivino nella stessa sequenza (ma non necessariamente allo stesso ritmo) dei frame a cui corrispondono. Nel momento in cui il mittente riceve la ricevuta 1, la finestra si sposta in alto di una posizione, definendo un nuovo range di frame consentiti per l'invio (da 2 a 6).

I processi di invio di pacchi e ricezione di ricevute sono abbastanza indipendenti l'uno dall'altro. Nel nostro esempio, il mittente continua a trasmettere frame, ma per un po' di tempo non ne riceve alcuna ricevuta. Dopo che il frame 6 è stato trasmesso, la finestra è esaurita e la sorgente sospende la trasmissione.

Riso. 2. Metodo della finestra scorrevole

Dopo la ricezione della ricevuta 2 (dal frame 2), la finestra viene spostata verso l'alto di uno, determinando l'intervallo di frame consentito per la trasmissione da 3 a 7. Un simile "scorrimento" della finestra verso l'alto si verifica dopo la ricezione di ogni ricevuta: la finestra viene spostato verso l'alto di 1, ma la sua dimensione non cambia e rimane uguale a 5. Dopo l'arrivo della ricevuta 8, la finestra risulta essere nell'intervallo da 9 a 13 e rimane tale per molto tempo, poiché per qualche motivo la sorgente smette di ricevere conferme sulla consegna dei frame. Dopo aver inviato l'ultimo frame consentito 13, il trasmettitore interrompe nuovamente la trasmissione per riprenderla dopo aver ricevuto la ricevuta 9.

Quando viene inviato un frame, all'origine viene impostato un timeout. Se per tempo impostato Se la ricevuta del frame inviato non viene ricevuta, il frame (o la relativa ricevuta) viene considerato perso e il frame viene ritrasmesso. Se il flusso di ricevute arriva regolarmente entro una tolleranza di 5 frame, allora il tasso di cambio raggiunge il valore massimo possibile per il dato canale e il protocollo accettato.

IN caso generale il metodo della finestra scorrevole è più difficile da implementare rispetto al metodo della sorgente idle, in quanto il trasmettitore deve memorizzare in un buffer una copia di tutte le trame per le quali non sono ancora state ricevute conferme. Inoltre, quando si utilizza questo metodo, è necessario tenere traccia di diversi parametri dell'algoritmo, come la dimensione della finestra, il numero di frame per il quale è stata ricevuta la ricevuta, il numero di frame che può ancora essere trasmesso prima che venga ricevuta una nuova ricevuta ricevuto.

Per aumentare il carico utile del canale viene utilizzato meccanismo a finestra scorrevole. Preliminarmente si noti che se i meccanismi di riconoscimento e di timeout sopra considerati assumessero l'esistenza di un semi canale doppio, allora il meccanismo della finestra scorrevole può essere implementato solo in presenza di un canale duplex. Allo stesso tempo, i frame di dati e le ricevute possono essere trasmessi simultaneamente diversi canali(figura 1.48).

L'essenza del meccanismo della finestra scorrevole è la seguente. Il nodo mittente può inviare diversi frame di dati di seguito senza ricevere le ricevute per questi frame. I frame sono numerati ciclicamente da 1 a W, Dove W - dimensione della finestra (larghezza) - il numero massimo di frame che possono essere trasmessi senza riconoscimento. Il numero di telaio è indicato nell'intestazione. La larghezza della finestra può essere scelta dalla condizione carico massimo canale diretto comunicazione dal nodo mittente al nodo ricevente, che può essere ottenuta inviando qualche frame in più in attesa della ricezione del primo frame:

Dove - tempo minimo di attesa per una ricevuta; -

tempo di trasmissione del frame - tempo di propagazione del canale

comunicazioni, - il tempo trascorso presso il nodo ricevente che elabora il frame, e

generazione scontrino.

Come segue dall'espressione presentata, se trascuriamo il tempo di propagazione del segnale sul canale di comunicazione e il tempo di elaborazione del frame nel nodo ricevente Y 2 , allora la larghezza minima della finestra dovrebbe essere almeno 2.

Supponiamo che nel momento iniziale la finestra del nodo mittente U1 sembra che sia mostrato in Fig. 1.49, a), il che significa la possibilità di trasmissione W fotogrammi senza conferma. Al fine di ridurre al minimo i tempi di inattività del canale di comunicazione, la ricevuta al nodo ricevente può essere generata prima del trasferimento di tutto W frame, ovvero il nodo ricevente può inviare una ricevuta al nodo mittente in qualsiasi momento conveniente per esso. Tale momento è solitamente associato alla formazione di un frame di dati inviato canale posteriore dal nodo U2 al nodo U1. In questo caso, nell'intestazione di questo frame viene inserita una conferma che indica il numero dell'ultima trama ricevuta senza errori (conferma positiva) o con un errore (conferma negativa). Se la ricevuta per una cornice con un numero A(1 < A< W) - è positivo, allora la finestra al nodo U1 viene spostata come mostrato in Fig. 1.49.6), il che significa la possibilità di trasmettere di più W cornici con numeri senza scontrino. Se la ricevuta per una cornice con un numero - è negativo, ciò significa che i frame con numeri fino a (k-1) ricevuti correttamente e frame a partire dal numero A, deve essere ritrasmesso. In questo caso, la finestra nel nodo U1 si sposta come mostrato in Fig. 1.49, c) il che significa la possibilità di trasmettere più W cornici con numeri senza scontrino. Pertanto, potrebbe non essere generata una ricevuta per tutti i frame trasmessi, ma solo per alcuni di essi, inoltre, se è arrivata una ricevuta positiva al numero di frame A, allora si considera che questo frame e tutti i frame precedenti con numeri da 1 a (A-1) accettato senza errori. Allo stesso modo, una ricevuta negativa per un telaio con numero A significa che tutti i frame precedenti sono stati ricevuti senza errori e tutti i frame trasmessi in precedenza sono soggetti a ritrasmissione, a partire dal numero A.

Algoritmo di timeout adattivo KARN

Timeout

Numeri di byte

duplicati

Problemi risolti con l'handshaking

Se la stazione invia 20 byte, il server aumenterà l'ACK di 20 (diventerà 751 byte) e così via.

Viene generato un riconoscimento per tutti i byte che arrivano nella sequenza corretta. Se vengono inviati duplicati, non rovinerà l'immagine. Puoi confermare 3 volte che sono arrivati ​​731 byte (questo è un esempio). Tutte le conferme sono cumulative. I riconoscimenti persi non sono un problema.

Possono verificarsi duplicati in TCP:

1. A causa della perdita del segmento originale
2. A causa della perdita della conferma
3. A causa del timeout di ritrasmissione
4. A causa del ritardo del segmento
5. A causa dell'enumerazione di tutti numeri possibili byte

Numeri sequenziali fino a 2 32 . Ad una velocità di 2 Mbps, ci vorranno 9 ore per enumerare tutti i valori. A causa della duplicazione del numero di serie, potrebbe risultarne un duplicato. All'aumentare della velocità, aumenta la probabilità che ciò avvenga.

Combattono con un'incredibile quantità di denaro.

Imposta i timeout. Il valore di timeout influisce sulle prestazioni. Il timeout è correlato a doppio tempo di esecuzione(RTT). Grande timeout - grande attesa in caso di errore. Un piccolo timeout è una ritrasmissione non necessaria.

Ce ne sono vari algoritmi di timeout adattativi(attività del sistema operativo). CISCO utilizza l'algoritmo KARN.

L'essenza dell'algoritmo. Viene calcolato il tempo medio RTT, moltiplicato per un certo coefficiente (in KARN il coefficiente è 2). È necessario modificare non solo il tempo medio di timeout, ma anche la dimensione della finestra. In KARN, la finestra cambia fino a liberarsi dal 20% al 40% della finestra.

Il protocollo TCP presuppone una finestra dinamica. Il ricevitore riporta il numero di byte che può ricevere (da 0 a 65535). Numero di partenza windows è sempre impostato nella fase di creazione di una connessione. Il ricevitore determina quale finestra dovrebbe essere, in base alle capacità minime. Il processo dell'applicazione ricevente che utilizza i buffer ha un impatto significativo sulle prestazioni TCP. Selezione corretta la dimensione della finestra ottimizza il TCP. Una finestra si apre quando il processo ricevente dall'altra parte legge il riconoscimento e libera il buffer TCP. Se bordo sinistro coincide con il limite destro, il mittente deve interrompere la trasmissione (finestra zero). La finestra si chiude quando i dati vengono trasmessi e confermati (il bordo sinistro si sposta a destra).

La connessione viene terminata quando la stazione invia il flag FIN al server. Il server invia ACK e FIN. Inoltre, il server invia di nuovo FIN e la stazione invia ACK e FIN.

Protezione da sovraccarico - avvio lento- non inviare immediatamente e rapidamente i pacchetti alla rete.

C'è anche meccanismo di ritrasmissione rapida(non è necessario un avvio lento) e

meccanismo di riconoscimento ritardato (in Windows).

Questo algoritmo (algoritmo LZ77 4 Prende il nome dagli autori Abraham Lempel e Jacob Ziv. Pubblicato nel 1977.) è stato uno dei primi a utilizzare un dizionario. Gli ultimi N elementi già codificati della sequenza sono usati come dizionario. Durante la compressione, il dizionario delle sottosequenze si sposta ("scorre") sulla sequenza in arrivo. La catena di elementi in uscita è codificata come segue: la posizione della parte corrispondente della catena di elementi elaborata nel dizionario - offset (rispetto alla posizione corrente), lunghezza, il primo elemento che segue la parte corrispondente della catena. La lunghezza della catena di corrispondenza è delimitata dall'alto dal numero n . Di conseguenza, il compito è trovare dal dizionario la stringa più grande che corrisponda alla sequenza elaborata. Se non ci sono corrispondenze, vengono scritti offset zero, lunghezza unitaria e solo il primo elemento della sequenza non codificata - (0, 1, e).

Lo schema di codifica sopra descritto porta alla nozione finestra scorrevole(finestra scorrevole inglese), composta da due parti:

1. una sottosequenza di elementi già codificati di lunghezza N - un dizionario - buffer di ricerca(buffer di ricerca inglese);
2. sottosequenza di lunghezza n dalla catena di elementi per i quali verrà effettuato un tentativo di ricerca di una corrispondenza - respingente anteprima (Buffer di previsione inglese).

In termini finestra scorrevole l'algoritmo di compressione è descritto come segue: if e 1 , . . . , e i - sottosequenza già codificata, quindi e i-N+1 , . . . , e i è un dizionario o buffer di ricerca ed e i+1 , . . . , e i+n - buffer di anteprima. Allo stesso modo, il compito è trovare la più grande catena di elementi dal buffer di anteprima, a partire dall'elemento e i+1 , abbinando la catena dal buffer di ricerca - questa catena può iniziare con qualsiasi elemento e terminare con qualsiasi elemento , cioè andare oltre il buffer di ricerca, invadendo il buffer di anteprima. È naturale andare oltre finestra scorrevoleè vietato. Sia la finestra scorrevole trovare la catena di elementi abbinata di lunghezza massima e i-p , . . . , e i+q , verrà codificato come segue: (p+1, q+p+1, e i+p+q+2 ) - offset dall'inizio del buffer di anteprima (e i+1) , la lunghezza della stringa corrispondente , l'elemento che segue la stringa corrispondente dal buffer di anteprima. Se la ricerca restituisce due corrispondenze con la stessa lunghezza, viene selezionato quello più vicino all'inizio del buffer di anteprima. Dopo di che finestra scorrevole viene spostato in avanti di p + q + 2 elementi e la procedura di ricerca viene ripetuta.

La scelta dei numeri N e n è un problema importante separato, perché maggiore è N e n , maggiore è lo spazio necessario per memorizzare i valori di offset e lunghezza. Naturalmente, anche il tempo di esecuzione dell'algoritmo aumenta con la crescita di N e n. Si noti che di solito N e n differiscono di un ordine di grandezza.

Facciamo un esempio di compressione con questo algoritmo. Comprimiamo la stringa "TOBEORNOTTOBE" con i parametri N = 10 e n = 3 :

Se allochiamo 4 bit per memorizzare l'offset, 2 bit per la lunghezza e 8 bit per gli elementi, la lunghezza della sequenza codificata (esclusa la designazione della fine della sequenza) sarà 4 x 8 + 2 x 8 + 8 x 8 = 112 bit e l'originale - 102 bit. In questo caso non abbiamo compresso la sequenza, ma, al contrario, abbiamo aumentato la ridondanza della rappresentazione. Ciò è dovuto al fatto che la lunghezza della sequenza è troppo piccola per un tale algoritmo. Ma, per esempio, disegnare albero del codice Huffman nella fig. 13.1, che occupa 420 kilobyte spazio sul disco, dopo la compressione ha una dimensione di circa 310 kilobyte.

Di seguito è riportato lo pseudocodice dell'algoritmo di compressione.

// M - limite fisso // legge i caratteri in sequenza dal flusso di input // in - input - sequenza compressa // n - lunghezza massima strings // pos - posizione nel dizionario, len - lunghezza della stringa // nelem - elemento per stringa, str - stringa trovata // in - input, out - output // SlideWindow - buffer di ricerca while(!in.EOF()) // finché ci sono dati ( // cerca la corrispondenza massima e i suoi parametri SlideWindow.FindBestMatch(in, n, pos, len, nelem); // scrive l'output: offset, length, element out.Write(pos); out .Write(len ); out.Write(nelem); // sposta la finestra scorrevole di len + 1 elementi SlideWindow.Move(in, len + 1); ) Listato 13.2. Algoritmo di compressione LZ77

La decodifica di una sequenza compressa è una decodifica diretta dei codici registrati: ad ogni voce viene abbinata una catena da un dizionario e un elemento scritto esplicitamente, dopodiché il dizionario viene spostato. Ovviamente, il dizionario viene ricreato mentre funziona l'algoritmo di decodifica.

Si può vedere che il processo di decodifica è molto più semplice dal punto di vista computazionale.

// n - lunghezza massima della stringa // pos - posizione nel dizionario, len - lunghezza della stringa // nelem - elemento per stringa, str - stringa trovata // in - input, out - output // Dict - dizionario while(!in. EOF()) //mentre ci sono dati ( in.Read(pos); in.Read(len); in.Read(nelem); if(pos == 0) ( //new singolo carattere//rimuove il primo (lontano) elemento dal dizionario Dict.Remove(1); //aggiungo un elemento al dizionario Dict.Add(nelem); out Scrivi(nelem); ) else ( //copia la stringa corrispondente dal dizionario str = Dict.Get(pos, len); //rimuove dal dizionario len + 1 elementi Dict.Remove(len + 1); //aggiunge il Dict.Add( str) catena al dizionario + nelem); out.Write(str + nelem); ) ) Listato 13.3. Algoritmo

Questo algoritmo è l'antenato di un'intera famiglia di algoritmi e di per sé nella sua forma originale non viene praticamente utilizzato. I suoi vantaggi includono un discreto grado di compressione su sequenze sufficientemente grandi, una rapida decompressione e l'assenza di un brevetto 5 un documento che prevede il diritto esclusivo di sfruttare l'invenzione per un certo periodo (di solito 15-20 anni) all'algoritmo. Gli svantaggi includono bassa velocità compressione, nonché un rapporto di compressione inferiore rispetto agli algoritmi alternativi (le modifiche dell'algoritmo affrontano questo inconveniente). La combinazione degli algoritmi Huffman (Lossless Image Compression Algorithms) e LZ77 è chiamata metodo DEFLATE 6 Questo è ciò che viene chiamata la compressione e la decompressione si chiama INFLATE (inglese DEFLATE - blow off, INFLATE - inflate).. Il metodo DEFLATE è utilizzato nella grafica Formato PNG, così come dentro formato universale Compressione dei dati ZIP.

Il livello di trasporto utilizza i servizi forniti dal livello di rete:

migliori servizi di selezione del percorso e di indirizzamento logico. Questi servizi di livello 3 forniscono una connessione end-to-end tra un mittente e un destinatario. Questo capitolo descrive come il livello di trasporto regola il flusso di informazioni trasmesse dal mittente al destinatario. Il livello di trasporto ha seguenti caratteristiche:

─ Un flusso di dati a livello di trasporto è una connessione logica tra punti finali reti;

─ Il meccanismo della finestra scorrevole fornisce controllo end-to-end e affidabilità della connessione, consente di tenere traccia della sequenza dei numeri dei pacchetti e delle notifiche;

─ gestire vari le connessioni di rete nei protocolli del quarto strato TCP e UDP e per trasmettere informazioni ai livelli superiori, i cosiddetti porti(porta).

Strato di trasporto della pilaTCP/IP

Come suggerisce il nome, il livello di trasporto dello stack del protocollo TCP/IP è responsabile del trasporto dei dati tra le applicazioni su un dispositivo di ricezione e un dispositivo di invio. La conoscenza dei principi del livello di trasporto è un punto chiave necessario per una profonda comprensione del moderno tecnologie di rete. Le sezioni seguenti descrivono in dettaglio le caratteristiche ei servizi di uno dei livelli più importanti del modello TCP/IP, il livello di trasporto.

Introduzione al livello di trasporto dello stackTCP/IP

Per descrivere il quarto, trasporto, livello, si usa spesso l'espressione qualità del servizio. Il protocollo UDP, discusso in dettaglio di seguito, appartiene al livello di trasporto e fornisce servizi di trasporto senza connessione. Tuttavia, il protocollo principale che opera a questo livello è il protocollo TCP, che utilizza un meccanismo di creazione della connessione. Le funzioni principali di questo protocollo sono il trasporto e il controllo affidabile del flusso di informazioni dal mittente al destinatario. Le funzioni principali del livello di trasporto includono il controllo della trasmissione end-to-end, il controllo del flusso attraverso il meccanismo della finestra scorrevole e la garanzia dell'affidabilità della consegna attraverso la definizione di numeri di sequenza e l'uso di riconoscimenti.

Per capire perché sono necessari l'affidabilità della trasmissione dei dati e il controllo del flusso, immagina uno straniero che parla molto velocemente. Molto probabilmente il suo ascoltatore sarà costretto a chiedere di nuovo a volte singole parole (analogo all'affidabilità della trasmissione) e chiedere di parlare più lentamente (analogo al flusso).

Il livello di trasporto fornisce i mezzi per trasferire in modo affidabile i dati da un host mittente a un host ricevente. A questo livello, viene creata una connessione logica tra gli endpoint di rete; inoltre, i compiti del livello di trasporto includono la segmentazione e il riassemblaggio dei dati trasmessi da vari applicazioni strati superiori in un unico flusso di dati del livello di trasporto. Questo flusso fornisce il trasferimento di dati end-to-end tra gli endpoint.

Un traffico a livello di trasporto è una connessione logica tra gli endpoint in una rete; il livello di trasporto controlla anche se è possibile stabilire una connessione tra le applicazioni. Sulla fig. La Figura 11.2 illustra come funziona il livello di trasporto.

Il livello di trasporto fornisce le seguenti funzioni:

segmentazione dei dati applicativi di livello superiore;

gestione dell'interazione end-to-end;

trasferire segmenti da un nodo finale a un altro;

controllo del flusso modificando le dimensioni della finestra;

Garantire l'affidabilità assegnando numeri e utilizzando le conferme.

Per strato di trasporto rete esterna può essere rappresentato come un mezzo (di solito raffigurato come una nuvola) attraverso il quale i pacchetti di dati vengono trasmessi dal mittente al destinatario. Tale ambiente è responsabile di quale percorso è ottimale per un particolare destinatario. Già in questa fase, puoi capire quale ruolo importante svolgono i router nel processo di trasmissione dei dati nella rete.

La suite di protocolli TCP/IP è costituita da due protocolli separati: TCP e IP. Il protocollo IP è un protocollo di livello 3 senza connessione che fornisce un trasferimento efficiente dei dati su una rete. TCP è un protocollo di livello 4, è un servizio orientato alla connessione e fornisce il controllo del flusso e quindi un'elevata affidabilità di trasmissione. La combinazione di questi due protocolli consente di risolvere un'ampia gamma di problemi di trasmissione dati. Naturalmente, lo stack del protocollo TCP/IP è costituito da molti altri protocolli, ma TCP e IP sono i protocolli principali. A proposito, tutti Internet basato sullo stack del protocollo TCP/IP.

controllo del flusso

Quando il protocollo del livello di trasporto TCP inoltra i segmenti di dati, può garantire l'integrità dei dati. Un modo per raggiungere questo obiettivo è controllo del flusso (fluirecontrollo) , che evita i problemi associati a situazioni in cui l'host a un'estremità della connessione supera i buffer della stazione all'altra estremità. L'overflow causa seri problemi perché può portare alla perdita di dati.

I servizi del livello di trasporto consentono agli utenti di richiedere un trasporto affidabile dei dati tra host di invio e ricezione. Per garantire un trasferimento dati affidabile tra i sistemi dei partner di comunicazione, viene utilizzato un meccanismo basato sul collegamento. Il trasporto affidabile offre le seguenti caratteristiche:

assicura che il mittente riceva conferma della consegna di ciascun segmento;

fornisce rispedire eventuali segmenti per i quali non è stata ricevuta conferma di consegna;

consente di ordinare i segmenti nella destinazione nell'ordine corretto;

previene la congestione della rete e gestisce la congestione qualora si verificasse.

Installazione, gestione e chiusura della sessione

Nel modello di riferimento OSI, più applicazioni possono condividere contemporaneamente la stessa connessione di trasporto. La funzione di trasporto dei dati è implementata segmento per segmento. Ciò significa che diverse applicazioni possono trasferire i dati in base all'ordine di arrivo (FIFO). I segmenti possono essere destinati allo stesso destinatario oa destinatari diversi. Questa regola è talvolta indicata come meccanismo di multiplexing della finestra di dialogo dell'applicazione di primo livello (Figura 3).

Riso. 3. Varie applicazioni del livello più alto del modello OSI utilizzano il livello di trasporto

Una delle funzioni principali del livello di trasporto è l'organizzazione di una sessione di comunicazione con la creazione di una connessione con un sistema peer-to-peer. Per avviare un trasferimento di dati, le applicazioni del mittente e del destinatario informano il loro Sistema operativo sull'inizializzazione della connessione. Una delle stazioni avvia una connessione che deve essere accettata dall'altra stazione. I moduli del sistema operativo preposti al funzionamento dei protocolli comunicano tra loro inviando un messaggio speciale e controllano la possibilità di trasferimento dei dati e la prontezza dei nodi finali.

Una volta completato il processo di sincronizzazione e stabilita la connessione, inizia il trasferimento dei dati. Durante il trasferimento, entrambe le stazioni non smettono di scambiarsi messaggi che assicurano che i dati ricevuti siano corretti. Sulla fig. 4 illustra una tipica connessione tra un mittente e un destinatario. Il primo messaggio di richiesta è necessario per sincronizzare i nodi finali. Il secondo e il terzo sono necessari per riconoscere la richiesta di sincronizzazione iniziale; sincronizzano anche i parametri di connessione nella direzione opposta. L'ultimo post è conferma(riconoscimento), che viene utilizzato per informare il destinatario che entrambe le parti sono pronte a stabilire una connessione. Una volta stabilita la connessione, inizia il trasferimento dei dati.

Riso. 4. Il processo di stabilire una connessione con un sistema peer-to-peer

Durante il trasferimento dei dati, la congestione può verificarsi per due motivi. Il primo è che un computer veloce può generare un flusso di dati più velocemente di quanto la rete possa trasmetterlo. Il secondo si verifica quando molti computer devono inviare dati allo stesso destinatario contemporaneamente. In questo caso, il destinatario potrebbe riscontrare congestione, sebbene ciascun mittente individualmente non causi problemi.

Nei casi in cui i datagrammi arrivano troppo velocemente e il nodo finale o il gateway non possono elaborarli, vengono temporaneamente archiviati in memoria. Se l'intensità del flusso di dati non diminuisce, allora l'end node o gateway, avendo esaurito, alla fine, le sue risorse di memoria, sarà costretto a scartare tutti i successivi datagrammi.

Per prevenire la perdita di dati, la funzione di trasporto può inviare al mittente un messaggio informativo "dispositivo non pronto a ricevere". Agendo come un semaforo rosso, questo messaggio indicatore segnala al mittente di interrompere l'invio dei dati. Dopo che il ricevitore è in grado di elaborare nuovamente più dati, invia un messaggio di trasporto dell'indicatore "dispositivo pronto a ricevere dati", che è come un semaforo verde. Dopo aver ricevuto tale indicatore, il mittente può riprendere la trasmissione dei segmenti.

Dopo la fine del trasferimento dei dati, il mittente invia un segnale al destinatario, che indica il completamento del trasferimento. Il destinatario conferma la cessazione della connessione, dopodiché la connessione tra le macchine viene terminata.

Riconoscimento in tre fasi

Il protocollo TCP utilizza un algoritmo orientato alla connessione, quindi è necessario stabilire una connessione logica prima che i dati possano essere trasmessi. Per stabilire una connessione di rete tra due postazioni di lavoro è necessario sincronizzare i loro numeri di sequenza iniziali (ISN - Initial Sequence Number). La sincronizzazione si ottiene scambiando segmenti specializzati che contengono il bit di controllo SYN (abbreviazione di Ssincronizzazione) e numeri ISN. I moduli che portano il bit SYN sono talvolta indicati anche come messaggi SYN. Per risolvere il problema dello stabilimento, è necessario scegliere un meccanismo appropriato per selezionare i numeri ISN stabilendo una connessione iniziale per lo scambio di numeri ISN.

La sincronizzazione richiede che ciascuna parte invii il proprio ISN iniziale e riceva un riconoscimento sotto forma di un messaggio di notifica ACK (abbreviazione di riconoscimento) da un altro membro della connessione. Inoltre, ciascuna parte deve ottenere il numero ISN del partner di comunicazione e inviare una notifica ACK al riguardo. La sequenza di scambio di messaggi tra due nodi di rete, A e B, è descritta di seguito.

Questo scambio di messaggi è chiamato stretta di mano in tre fasi (tre- modo stretta di mano) (figura 5).

Riso. 5. Riconoscimento in tre fasi

1. A SI SI. La mia iniziale numero di serie ISN è X, il numero ACK è 0, il bit SYN è impostato ma il bit ACK non è impostato.

2. B A.ACK. Il tuo numero di sequenza è X+1, il mio ISN è Y, i bit SYN e ACK sono impostati.

3. A INDIETRO. Il tuo numero di sequenza è Y+1, il mio numero di sequenza è X+1, il bit ACK è impostato e il bit SYN non è impostato.

L'handshake a 3 vie è un meccanismo di connessione asincrona necessario per mantenere sincronizzati i numeri di sequenza, poiché i numeri di sequenza sono indipendenti da un contatore globale virtuale sulla rete. Pertanto, in una rete che esegue il protocollo TCP, vengono utilizzati vari meccanismi per l'assegnazione dei numeri ISN. Uno di questi è la stretta di mano in tre fasi. Tuttavia, questo meccanismo non è solo per ottenere un ISN. Con esso, i dispositivi finali si scambiano informazioni sulla dimensione della finestra di trasferimento dei dati, Parametro MTU e latenza di rete. Il destinatario del primo SYN non ha mezzi disponibili per determinare se il segmento ricevuto era un messaggio vecchio o nuovo in attesa fino alla ricezione del messaggio successivo; l'unica eccezione è quando il destinatario memorizza l'ultimo numero di sequenza utilizzato sulla connessione (che non è sempre possibile). Pertanto, il destinatario deve chiedere al mittente di convalidare tale messaggio SYN.

meccanismo a finestra scorrevole

Nella forma più generale di trasferimento dati affidabile orientato alla connessione, i pacchetti di dati devono essere consegnati all'estremità ricevente nello stesso ordine in cui sono stati trasmessi. Il protocollo fallisce se i pacchetti di dati vengono persi, danneggiati, duplicati o ricevuti fuori servizio. La soluzione più semplice a questo problema consiste nell'utilizzare la conferma di ricezione da parte del destinatario di ciascun segmento di dati.

Tuttavia, se il mittente è costretto ad attendere un riconoscimento dopo l'invio di ogni segmento, come mostrato in Fig. 6, la velocità di trasmissione viene notevolmente ridotta con questo metodo. Poiché dal momento in cui il mittente termina di inviare un pacchetto di dati fino al completamento dell'elaborazione di qualsiasi conferma ricevuta, trascorre un certo periodo di tempo, che può essere utilizzato per inviare un'ulteriore porzione di dati. Viene chiamato il numero di pacchetti di dati che possono essere inviati al mittente senza ricevere un riconoscimento finestra(finestra).

Il protocollo TCP utilizza i cosiddetti riconoscimenti attesi; contengono un numero riferito all'ottetto previsto dopo. Il meccanismo della finestra scorrevole è che la negoziazione della dimensione della finestra avviene dinamicamente durante una sessione TCP. meccanismo a finestra scorrevoleè un meccanismo di controllo del flusso che richiede al destinatario di accettare una conferma dal mittente dopo che una certa quantità di dati è stata trasmessa.

Riso. 6. La dimensione della finestra è una

Per controllare il flusso di dati tra due dispositivi, utilizza il protocollo TCP meccanismo di controllo del flusso(meccanismo di controllo del flusso). Il destinatario comunica al mittente la ricezione dei dati; la ricezione di tale notifica consente di impostare la dimensione della finestra. La finestra specifica il numero di ottetti, contati dal numero di riconoscimento corrente, che il dispositivo TCP è in grado di ricevere in un determinato momento.

Ad esempio, con una dimensione della finestra di 3, il mittente può inviare tre ottetti al destinatario. Successivamente, deve attendere la conferma del destinatario. Se il destinatario ha ricevuto tre ottetti, deve inviare un avviso di ricevimento al mittente degli ottetti. Il mittente può quindi inviare i successivi tre ottetti. Se il destinatario non ha ricevuto tre ottetti, ad esempio a causa di un overflow del buffer, non invierà una conferma. Se il mittente non riceve una conferma di ricezione, ciò significa che gli ultimi ottetti devono essere ritrasmessi e la velocità di trasmissione ridotta.

La dimensione della finestra TCP può cambiare durante la trasmissione di un flusso di dati tra due dispositivi di rete. Ogni conferma inviata dal destinatario contiene informazioni sul numero di byte che il destinatario è in grado di ricevere. Il protocollo TCP prevede l'utilizzo di una cosiddetta finestra di controllo della congestione, che normalmente è uguale alla finestra del dispositivo di destinazione, ma la sua dimensione viene dimezzata se qualche segmento di dati viene perso (ad esempio, durante la congestione della rete). Questo meccanismo consente di ridurre o aumentare le dimensioni della finestra secondo necessità nel processo di gestione del buffer del dispositivo e di elaborazione del flusso di dati. Le dimensioni maggiori della finestra consentono la trasmissione simultanea grande quantità ottetti.

Quando il mittente trasmette tre ottetti, passa all'attesa di un segnale ACK per quattro ottetti. Se il ricevitore è in grado di elaborare un blocco di dati di due ottetti, scarta il terzo ottetto e lo designa come successivo blocco di dati previsto. Questo specifica la nuova dimensione della finestra, che è uguale a due. Il mittente invia i successivi due ottetti, ma la dimensione della finestra è ancora tre (supponendo che il dispositivo possa ancora elaborare tre ottetti contemporaneamente). Il destinatario richiede l'ottetto numero 5 e imposta nuova dimensione finestre pari a due.

Conferme

Un meccanismo di consegna affidabile garantisce che un flusso di dati inoltrato da una stazione venga consegnato tramite il collegamento dati a un'altra senza duplicazione o perdita di dati. Il riconoscimento positivo con la ritrasmissione è una tecnica per garantire la consegna affidabile dei flussi di dati. Un riscontro positivo richiede che il destinatario comunichi con il mittente inviando un messaggio di riscontro dopo aver ricevuto i dati. Il mittente registra ogni pacchetto che invia e attende la conferma prima di inviare il successivo pacchetto di dati. Al momento dell'invio di un segmento, il mittente avvia anche un timer e ritrasmette il blocco dati se impostato dal timer il tempo scade prima che arrivi la conferma.

Sulla fig. La Figura 7 mostra un mittente che invia i pacchetti 1, 2 e 3. Il destinatario riconosce i pacchetti richiedendo il pacchetto 4. Il mittente, dopo aver ricevuto una conferma, invia i pacchetti 4, 5 e 6. inviando il pacchetto 5. Il mittente invia nuovamente il pacchetto 5 e deve ricevere un riscontro appropriato per continuare a inviare il pacchetto numero 7.

Il protocollo TCP impone la sequenza di segmenti seguita da un riconoscimento. Ad ogni datagramma viene assegnato un numero prima della trasmissione (Figura 8). Dopo che il destinatario ha ricevuto tutti i datagrammi, questi vengono assemblati in un messaggio completo. È responsabilità del protocollo TCP recuperare i dati danneggiati, persi, duplicati o fuori servizio trasmessi su Internet. Il meccanismo di ripristino funziona assegnando un numero di sequenza a ciascun ottetto trasmesso, alla ricezione del quale il ricevente deve inviare un avviso di ricevimento (ACK). Se non viene ricevuta alcuna conferma entro l'intervallo di timeout, i dati vengono ritrasmessi dal mittente. Dopo che gli ottetti sono stati consegnati al destinatario, i loro numeri di sequenza vengono utilizzati per assemblare il messaggio dai frammenti ed eliminare i duplicati. I dati danneggiati vengono riparati utilizzando un checksum che viene aggiunto a ciascun segmento trasmesso. Il checksum viene verificato dal destinatario e, se non corrisponde, i dati danneggiati vengono eliminati.

Riso. 7. La dimensione della finestra è tre

Riso. 8. Numeri progressivi e conferme

ProtocolloTCP

TCP(Protocollo di controllo della trasmissione - protocollo di controllo della trasmissione) è un protocollo di connessione di trasporto che fornisce una trasmissione dati full duplex affidabile. Il protocollo TCP fa parte dello stack del protocollo TCP/IP. In un ambiente orientato alla connessione, è necessario stabilire una connessione tra due computer per iniziare il trasferimento dei dati. Il protocollo TCP è responsabile della segmentazione dei messaggi in pacchetti, del loro riassemblaggio da parte del destinatario e della ritrasmissione dei dati se non sono stati ricevuti. Il protocollo è anche in grado di creare canali virtuali tra le applicazioni dell'utente finale.

Servizi e protocolli di primo livello che utilizzano meccanismi TCP:

FTP (File Protocollo di trasferimento- File Transfer Protocol);

HTTP (Hypertext Transfer Protocol - protocollo di trasferimento ipertestuale);

SMTP (Simple Mail Transfer Protocol - un semplice protocollo di posta elettronica);

Di seguito sono descritti i campi del segmento TCP mostrato nella slide.

Porta del mittente - numero della porta chiamante.

Porto di destinazione - numero di porta chiamato.

Numero di serie - numero utilizzato per organizzare i dati in arrivo nella sequenza corretta.

Numero di confermaè il numero del successivo ottetto TCP previsto.

HLEN- il numero di parole a 32 bit nell'intestazione.

campo riservato- tutti i bit sono impostati a 0.

Bit di codice- funzioni di servizio (ad esempio, impostazione e conclusione di una sessione).

Finestra- il numero di ottetti che il mittente è disposto ad accettare.

Controlla la somma- stimato assegno somma intestazione e campi dati.

Puntatore dati urgenti- indica la fine dei dati urgenti.

Opzioni- un parametro è attualmente definito: taglia massima Segmento TCP.

Dati- dati di protocollo di livello superiore.

ProtocolloUDP

UDP(utente datagramma Protocollo- protocollo datagramma utente), il cui formato di segmento è mostrato nella diapositiva, è un protocollo di trasporto senza connessione nello stack del protocollo TCP/IP. UDP è un semplice protocollo che scambia datagrammi senza riconoscimento e senza garanzia di consegna. La semplicità del protocollo diventa evidente quando si confrontano i formati dei segmenti del protocollo UDP e TCP. Quando si utilizza il protocollo UDP, la gestione degli errori e la ritrasmissione dei dati devono essere gestite da un protocollo di livello superiore. Ad esempio, se la trasmissione viene interrotta durante il trasferimento dei dati utilizzando il protocollo TFTP, solo l'operatore umano può riscaricare le informazioni.

L'elenco seguente elenca i campi del segmento UDP, mostrato nella diapositiva

Porta del mittente - numero della porta chiamante.

Porto di destinazione - numero di porta chiamato.

Lunghezza- numero di byte, inclusi intestazione e dati.

Controlla la somma- somma di controllo calcolata dell'intestazione e dei campi dati.

Dati- dati di protocollo di livello superiore.

Il protocollo UDP non utilizza un meccanismo a finestra scorrevole, pertanto è necessario garantire l'affidabilità della trasmissione dei dati protocolli a livello di applicazione(protocollo a livello di applicazione). Il protocollo UDP è stato progettato per applicazioni che non hanno bisogno di connettere insieme segmenti ordinati.

Il protocollo UDP è utilizzato dai seguenti servizi e protocolli di primo livello:

TFTP (Trivial File Transfer Protocol) il protocollo più semplice trasferimenti di file);

SNMP (Simple Network Management Protocol - un semplice protocollo di gestione della rete);

DHCP (Dynamic Host Configuration Protocol - protocollo di configurazione dinamica dell'host);

DNS (Domain Name System - servizio dei nomi di dominio).

Numeri di porta del protocolloTCPEUDP

Per trasferire informazioni a livelli superiori sia il protocollo TCP che Protocollo UDP utilizzare il numero di porta (porta) o il cosiddetto socket (socket). I numeri di porta vengono utilizzati per tenere traccia delle varie interazioni in corso contemporaneamente sulla rete.

Gli sviluppatori di software applicativo hanno accettato di utilizzare numeri di porta riservati amministrati dalla Internet Assigned Numbers Authority (IANA). Ad esempio, qualsiasi comunicazione FTP dovrebbe utilizzare le porte standard 20 (per i dati) e 21 (per il controllo). Le interazioni di rete che non sono correlate ad applicazioni con un numero di porta noto vengono assegnate arbitrariamente, ma vengono selezionate da un intervallo specifico di valori, superiore a 1023. Alcune porte sono riservate in Protocolli TCP e UDP. Sebbene alcune porte siano riservate nei protocolli TCP e UDP, le applicazioni potrebbero non essere cablate a questi numeri.

Come mostrato nella diapositiva, per selezionare l'applicazione appropriata sistema finale utilizza il numero di porta. Il numero di porta del mittente è in genere qualcosa di maggiore di 1023 che viene assegnato dinamicamente dall'host di invio. Ad esempio, un host tenta di connettersi a un altro host tramite FTP inviando pacchetti che specificano il numero di porta TCP di destinazione 21 (FTP) e genera dinamicamente un numero di porta del mittente pari a 1028. Questa coppia di porte (mittente e destinazione) determina l'unicità di l'interazione tra due host. Se lo stesso host avvia una connessione FTP verso un terzo host, allora la porta di destinazione rimane la 21, ma la porta di origine viene scelta diversa dalla precedente (ad esempio, 1030) per separare le due sessioni.