Algoritmo di velocità cellulare generico - Generic cell rate algorithm

L' algoritmo generico della velocità di cella (GCRA) è un algoritmo di pianificazione di tipo bucket che perde per lo scheduler di rete utilizzato nelle reti ATM ( Asynchronous Transfer Mode ). Viene utilizzato per misurare la temporizzazione delle celle sui canali virtuali (VC) e / o sui percorsi virtuali (VP) rispetto ai limiti di larghezza di banda e jitter contenuti in un contratto di traffico per il VC o VP a cui appartengono le celle. Le celle che non sono conformi ai limiti dati dal contratto di traffico possono quindi essere ritemporizzate (ritardate) nel traffic shaping , oppure possono essere eliminate (scartate) o ridotte in priorità (retrocesse) nel controllo del traffico . Le celle non conformi con priorità ridotta possono quindi essere eliminate, preferibilmente a celle con priorità più alta, dai componenti a valle della rete che stanno subendo una congestione. In alternativa possono raggiungere la loro destinazione (terminazione VC o VP) se c'è capacità sufficiente per loro, nonostante siano celle in eccesso per quanto riguarda il contratto: vedi controllo priorità .

Il GCRA viene fornito come riferimento per il controllo del traffico sulle connessioni nella rete, ovvero controllo dei parametri di utilizzo / rete (UPC / NPC) alle interfacce utente-rete (UNI) o interfacce inter-rete o interfacce rete-rete (INI / NNI ). Viene anche dato come riferimento per la temporizzazione delle celle trasmesse (ATM PDU Data_Requests) su una rete ATM da una scheda di interfaccia di rete (NIC) in un host, cioè sul lato utente dell'UNI. Ciò garantisce che le celle non vengano poi scartate da UPC / NCP nella rete, cioè sul lato rete dell'UNI. Tuttavia, poiché il GCRA viene fornito solo come riferimento, i fornitori di rete e gli utenti possono utilizzare qualsiasi altro algoritmo che dia lo stesso risultato.

Descrizione del GCRA

Figura 1: versioni equivalenti dell'algoritmo generico della velocità di cella

Il GCRA è descritto dall'ATM Forum nella sua User-Network Interface (UNI) e dall'ITU-T nella raccomandazione I.371 Controllo del traffico e controllo della congestione in B-ISDN  . Entrambe le fonti descrivono il GCRA in due modi equivalenti: come algoritmo di pianificazione virtuale e come algoritmo di bucket leaky a stato continuo (figura 1).

Descrizione del secchio che perde

La descrizione in termini di algoritmo del leaky bucket può essere la più facile da comprendere da una prospettiva concettuale, in quanto si basa su una semplice analogia di un bucket con una perdita: vedere la figura 1 nella pagina del leaky bucket . Tuttavia, c'è stata confusione in letteratura sull'applicazione dell'analogia del bucket leaky per produrre un algoritmo, che è passato al GCRA. Il GCRA dovrebbe essere considerato come una versione del secchio che perde come un metro piuttosto che il secchio che perde come una coda .

Tuttavia, sebbene ci siano possibili vantaggi nella comprensione di questa descrizione del bucket che perde, non si traduce necessariamente nel codice migliore (più veloce) se implementato direttamente. Ciò è evidenziato dal numero relativo di azioni da eseguire nei diagrammi di flusso per le due descrizioni (figura 1).

La descrizione in termini di algoritmo del bucket a stato continuo che perde è fornita dall'ITU-T come segue: "Il bucket a stato continuo che perde può essere visto come un bucket a capacità finita il cui contenuto a valore reale si esaurisce a una velocità continua di 1 unità di contenuto per unità di tempo e il cui contenuto è aumentato dell'incremento T per ogni cella conforme ... Se all'arrivo di una cella il contenuto del bucket è inferiore o uguale al valore limite τ , la cella è conforme; in caso contrario, la cella non è conforme. La capacità del secchio (il limite superiore del contatore) è ( T + τ ) ". Vale la pena notare che, poiché la perdita è un'unità di contenuto per unità di tempo, l'incremento per ciascuna cella T e il valore limite τ sono in unità di tempo.

Considerando il diagramma di flusso dell'algoritmo del bucket leaky a stato continuo, in cui T è l'intervallo di emissione e τ è il valore limite: cosa succede quando arriva una cella è che lo stato del bucket viene calcolato dal suo stato quando è arrivata l'ultima cella conforme , X e quanto è trapelato nell'intervallo, t a - LCT . Questo valore attuale del bucket viene quindi memorizzato in X ' e confrontato con il valore limite τ . Se il valore in X ' non è maggiore di τ , la cella non è arrivata troppo presto e quindi è conforme ai parametri del contratto; se il valore in X ' è maggiore di τ , allora non è conforme. Se è conforme allora, se è conforme perché era in ritardo, cioè il secchio vuoto ( X ' <= 0), X è posto a T ; se fosse presto, ma non troppo presto, ( τ > = X ' > 0), X è impostato su X' + T .

Pertanto il diagramma di flusso imita direttamente l'analogia del secchio che perde (usata come misuratore), con X e X 'che agiscono come l'analogo del secchio.

Descrizione della pianificazione virtuale

L'algoritmo di pianificazione virtuale, sebbene non sia così ovviamente correlato a un'analogia così facilmente accessibile come il leaky bucket, fornisce una comprensione più chiara di ciò che fa il GCRA e di come può essere implementato al meglio. Di conseguenza, l'implementazione diretta di questa versione può risultare in un codice più compatto e quindi più veloce rispetto a un'implementazione diretta della descrizione del bucket che perde.

La descrizione in termini di algoritmo di scheduling virtuale è data dall'ITU-T come segue: "L'algoritmo di scheduling virtuale aggiorna un Theoretical Arrival Time (TAT), che è il tempo di arrivo 'nominale' della cella supponendo che le celle siano inviate equidistanziate ad un intervallo di emissione di T corrispondente alla velocità cellulare Λ [= 1 / T ] quando la sorgente è attiva. Se il tempo di arrivo effettivo di una cellula non è "troppo precoce" rispetto alla TAT e la tolleranza τ associata alla velocità cellulare , cioè se il tempo di arrivo effettivo è successivo al suo tempo di arrivo teorico meno il valore limite (t a > TAT - τ ), allora la cella è conforme, altrimenti la cella non è conforme ". Se la cella non è conforme, il TAT rimane invariato. Se la cella è conforme, ed è arrivato prima della sua TAT (equivalente al secchio non essere vuoto ma essendo inferiore al valore limite), allora la cella successiva TAT è semplicemente TAT + T . Tuttavia, se una cella arriva dopo il suo TAT , il TAT per la cella successiva viene calcolato dall'ora di arrivo di questa cella, non dal suo TAT . Ciò impedisce l'accumulo di credito quando c'è una lacuna nella trasmissione (equivalente al secchio che diventa meno che vuoto).

Questa versione dell'algoritmo funziona perché τ definisce quanto prima una cella può arrivare rispetto a quanto sarebbe se non ci fosse il jitter: vedere leaky bucket: tolleranza alla variazione del ritardo . Un altro modo per vederlo è che TAT rappresenta la prossima volta che il secchio si svuoterà, quindi un tempo τ precedente è quando il secchio è esattamente riempito al valore limite. Quindi, in entrambi i casi, se arriva più di τ prima del TAT , è troppo presto per conformarsi.

Confronto con il bucket di token

Il GCRA, a differenza delle implementazioni dell'algoritmo del bucket di token , non simula il processo di aggiornamento del bucket (la perdita o l'aggiunta di token regolarmente). Piuttosto, ogni volta che arriva una cella, calcola la quantità in base alla quale il bucket sarà fuoriuscito dall'ultima volta che il suo livello è stato calcolato o quando il bucket si svuoterà successivamente (= TAT ). Questo essenzialmente sta sostituendo il processo di perdita con un orologio (in tempo reale), che è probabile che la maggior parte delle implementazioni hardware abbia già.

Questa sostituzione del processo con un RTC è possibile perché le celle ATM hanno una lunghezza fissa (53 byte), quindi T è sempre una costante, e il calcolo del nuovo livello di bucket (o di TAT ) non comporta alcuna moltiplicazione o divisione. Di conseguenza, il calcolo può essere eseguito rapidamente nel software e, sebbene all'arrivo di una cella vengano intraprese più azioni di quante ne vengano eseguite dal bucket di token, in termini di carico su un processore che esegue l'attività, la mancanza di un processo di aggiornamento separato più che compensa questo. Inoltre, poiché non esiste alcuna simulazione dell'aggiornamento del bucket, non vi è alcun carico del processore quando la connessione è inattiva.

Tuttavia, se il GCRA dovesse essere utilizzato per limitare a una larghezza di banda, piuttosto che un pacchetto / frame rate, in un protocollo con pacchetti di lunghezza variabile (Link Layer PDU), comporterebbe la moltiplicazione: in pratica il valore aggiunto al bucket (o a TAT) per ogni pacchetto conforme dovrebbe essere proporzionato alla lunghezza del pacchetto: mentre, con GCRA come descritto, l'acqua nel secchio ha unità di tempo, per pacchetti di lunghezza variabile dovrebbe avere unità che sono il prodotto di lunghezza e tempo del pacchetto. Pertanto, l'applicazione del GCRA per limitare la larghezza di banda dei pacchetti di lunghezza variabile senza accesso a un moltiplicatore hardware veloce (come in un FPGA ) potrebbe non essere pratico. Tuttavia, può sempre essere utilizzato per limitare il pacchetto o la velocità delle celle, a condizione che le loro lunghezze vengano ignorate.

Dual Leaky Bucket Controller

È possibile applicare più implementazioni del GCRA contemporaneamente a un VC o un VP, in una funzione di controllo del traffico o di modellazione del traffico a doppio bucket leaky , ad esempio applicato a un VC a velocità di trasmissione variabile (VBR). Ciò può limitare le celle ATM su questo VBR VC a una velocità di cella sostenuta (SCR) e a una dimensione massima di burst (MBS). Allo stesso tempo, la funzione di polizia del traffico dual leaky bucket può limitare il tasso di celle nei burst a un Peak Cell Rate (PCR) e una tolleranza massima di variazione del ritardo cellulare (CDVt): vedere il contratto di traffico # Parametri del traffico .

Figura 2: esempio di temporizzazioni delle celle su una connessione VBR

Questo può essere meglio compreso dove la trasmissione su un VBR VC è sotto forma di messaggi di lunghezza fissa (CPCS-PDU), che vengono trasmessi con un intervallo fisso o l'Inter Message Time (IMT) e richiedono un numero di celle, MBS, portarli; tuttavia, la descrizione del traffico VBR e l'uso del dual leaky bucket non sono limitati a tali situazioni. In questo caso, la velocità di cella media nell'intervallo di IMT è l'SCR (= MBS / IMT). I singoli messaggi possono essere trasmessi a una PCR, che può essere qualsiasi valore compreso tra la larghezza di banda per il collegamento fisico (1 / δ ) e l'SCR. Ciò consente di trasmettere il messaggio in un periodo inferiore all'intervallo di messaggio IMT, con spazi tra le istanze del messaggio.

Figura 3: Algoritmo di riferimento per Sustainable Cell Rate (SCR) e Peak Cell Rate (PCR) per CLP = 0 + 1 flusso cellulare

Nel dual leaky bucket, un bucket viene applicato al traffico con un intervallo di emissione di 1 / SCR e un valore limite τ SCR che fornisce un MBS che è il numero di celle nel messaggio: vedere leaky bucket # Maximum burst size . Il secondo bucket ha un intervallo di emissione di 1 / PCR e un valore limite τ PCR che tiene conto del CDV fino a quel punto nel percorso della connessione: vedere leaky bucket # Delay Variation Tolerance . Le cellule vengono quindi lasciate passare alla PCR, con jitter di τ PCR , fino a un numero massimo di cellule MBS. Il successivo burst di celle MBS sarà quindi consentito avviando MBS x 1 / SCR dopo il primo.

Se le cellule arrivano in un burst a una velocità superiore a 1 / PCR (le cellule MBS arrivano in meno di (MBS - 1) / PCR - τ PCR ), o più delle cellule MBS arrivano alla PCR, o arrivano burst di cellule MBS più vicino dell'IMT, il doppio bucket che perde lo rileverà e ritarderà (modellando) o eliminerà o ridurrà la priorità (policing) celle sufficienti per rendere conforme la connessione.

La Figura 3 mostra l'algoritmo di riferimento per il controllo SCR e PCR per entrambi i valori di priorità di perdita cellulare (CLP) 1 (basso) e 0 (alto) flussi cellulari, cioè dove le cellule con entrambi i valori di priorità sono trattate allo stesso modo. Algoritmi di riferimento simili in cui le celle ad alta e bassa priorità sono trattate in modo diverso sono forniti anche negli allegati da I a I.371.

Guarda anche

Riferimenti