Algoritmo per l'implementazione di QOS nel mio proxy

Question

Algoritmo per l'implementazione di QOS nel mio proxy

#1 da (0 voti)
#2 da (0 voti)

2

Ecco la situazione: sto facendo un proxy (per il momento in esecuzione sul mio laptop) che tratta le richieste HTTP (S) dai client in arrivo (per ora solo un client, cioè il mio browser Chrome sul mio laptop). Funziona senza problemi, ma è un proxy best effort, cioè non dà priorità ad alcuni tipi di traffico (streaming su SMTP, ad esempio).

Ho pensato a tre classi di priorità (minimo: 1, medio: 2 e massimo: 3) e poiché il mio traffico ha due direzioni ( LAN -> proxy -> WAN e WAN -> proxy -> LAN ), ho pensato a sei code di priorità come queste ( la natura della coda FIFO non causa la fame dei pacchetti):

// LAN -> proxy -> WAN, from max to min priority
queue queue_to_remote_3;
queue queue_to_remote_2;
queue queue_to_remote_1;
// WAN -> proxy -> LAN, from max to min priority
queue queue_to_local_3;
queue queue_to_local_2;
queue queue_to_local_1;

Questo è lo pseudocodice (C-like) dell'algoritmo che ho fatto trattando i pacchetti in arrivo sia dalla LAN che dalla WAN: pubblicherò solo la parte che tratta LAN -> proxy -> WAN , poiché WAN -> proxy -> LAN ha lo stesso ragionamento, ma invece di queue_to_remote_X utilizza queue_to_local_X :

void algoQueues(packet pkt, int direction, int priority) {
    if (direction == TO_REMOTE) {
        switch (priority) {
            case 1: { // MAXIMUM priority
                // if queue1 is empty, just let it pass
                if (queue_to_remote_1.empty()) {
                    letPass(pkt);
                }
                // if queue1 is not empty, push the arrived pkt and
                // pop another pkt from the queue to let it pass
                else {
                    queue_to_remote1.push(pkt); 
                    packet new_pkt = queue_to_remote1.pop();
                    letPass(new_pkt);
                }
                break;
            }
            case 2: { // MEDIUM priority
                // first check if queue1 has pkts to send
                if (queue_to_remote_1.empty()) {
                    // if queue1 is empty, then check queue2
                    if (queue_to_remote_2.empty()) {
                        // if queue2 is empty too, just let the packet pass
                        letPass(pkt);
                    }
                    // if queue1 is empty and queue2 is not empty,
                    // push the new arrived pkt in queue2 and send 
                    // a queued pkt from queue2
                    else {
                        queue_to_remote_2.push(pkt);
                        packet new_pkt = queue_to_remote_2.pop();
                        letPass(new_pkt);
                    }
                }
                // if queue1 is not empty, I must queue the new arrived pkt
                // in queue 2 and send a queued pkt from queue1
                else {
                    queue_to_remote_2.push(pkt);
                    packet new_pkt = queue_to_remote_1.pop();
                    letPass(new_pkt);
                }
                break;
            }
            case 3: { // MINIMUM priority
                // first check if queue1 has pkts to send
                if (queue_to_remote_1.empty()) {
                    // if queue1 is empty, then check queue2
                    if (queue_to_remote_2.empty()) {
                        // if queue3 is empty, just let it pass
                        if (queue_to_remote_3.empty()) {
                            letPass(pkt);
                        }
                        // if queue3 is not empty, push the arrived pkt 
                        // in queue3 and pop another pkt from the 
                        // same queue to let it pass
                        else {
                            queue_to_remote_3.push(pkt);
                            packet new_pkt = queue_to_remote_3.pop();
                            letPass(new_pkt);
                        }
                    }
                    // if queue2 is not empty and queue1 is empty, push the 
                    // arrived pkt in queue3, get a pkt from queue2 and send it
                    else {
                        queue_to_remote_3.push(pkt);
                        packet new_pkt = queue_to_remote_2.pop();
                        letPass(new_pkt);
                    }
                }
                // if queue1 is not empty, queue the pkt in queue3
                // and send a pkt from queue1
                else {
                    queue_to_remote_3.push(pkt);
                    packet new_pkt = queue_to_remote_1.pop();
                    letPass(new_pkt);
                }
                break;
            }
            default: {
                printf("To remote: unknown priority, strange...\n");
                exit(EXIT_FAILURE);
            }
        }
    }
    else if (direction == TO_LOCAL) {
        /* ... */
    }
}

Un osservatore intelligente potrebbe obiettare: "quando inserisci il primo pacchetto ???", e questo è il mio problema; la prima volta che viene chiamato questo algoritmo, tutte le code sono vuote, quindi ogni pacchetto passerà!

Non posso spingere il primo pacchetto di nessuna priorità nella sua coda e interrompere l'istruzione switch per sbloccare tutti gli altri if s, sembra stupido: il mio ragionamento (e quindi il mio algoritmo) è sbagliato, o sto usando la struttura dati sbagliata?

data-structures algorithms networking proxy

posta elmazzun 10.04.2016 - 13:22

fonte

2 risposte

0

Codice di lavoro (non pseudocodice come ho detto, duh! ma questo è più esplicativo): ho due file desciptor, uno per client e un altro per server, entrambi aperti con socket(AF_INET, SOCK_STREAM, IPPROTO_TCP) ; il select() controlla se il client del server ha inviato qualcosa, il fd_set è solo per la lettura (da client e server).

Avviso : non sono sicuro di chiudere correttamente i descrittori di file dove devo o se ci sono errori concettuali, ma questo funziona per me: select (), check for reading for client e server, recv (), push () in coda, pop () dalla coda e send ().

int maxp = server_fd >= client_fd ? server_fd+1 : client_fd+1;
int r;
int priority = 0;
int read_from_client = 0;
int read_from_server = 0;
int send_to_client = 0;
int send_to_server = 0;
struct timeval timeout;
char https_buf[1500];
int https_buf_size = sizeof(https_buf);
fd_set fdset;

while(true) {
    memset(https_buf, 0, https_buf_size);
    FD_ZERO(&fdset);
    FD_SET(client_fd, &fdset);
    FD_SET(server_fd, &fdset);

    timeout.tv_sec = 30;
    timeout.tv_usec = 0;

    r = select(maxp, &fdset, NULL, NULL, &timeout);

    if (r < 0) {
        perror("select()");
        close(client_fd);
        client_fd = -1;
        close(server_fd);
        server_fd = -1;
        break;
    }

    if (r == 0) { // select timed out
        close(client_fd);
        client_fd = -1;
        close(server_fd);
        server_fd = -1;
        break;
    }

    if (FD_ISSET(client_fd, &fdset)) {
        read_from_client = recv(client_fd, https_buf, https_buf_size, 0);
        if (read_from_client < 0) {
            perror("recv():");
            close(client_fd);
            client_fd = -1;
            close(server_fd);
            server_fd = -1;
            break;
        }
        else if (read_from_client == 0) {
            // connection closed
            close(client_fd);
            client_fd = -1;
            close(server_fd);
            server_fd = -1;
            break;
        }
        priority = whatPriorityHasPkt();
        insertInQueue(/* useful data */);
        // specify the direction and the buffer 
        // where to write data
        removeFromQueue(TO_REMOTE, https_buf);
        send_to_server = send(server_fd, https_buf, read_from_client, 0);
        // if send() returns error, close both 
        // sockets and break;
    }

    if (FD_ISSET(server_fd, &fdset)) {
        read_from_server = recv(server_fd, https_buf, https_buf_size, 0);
        if (read_from_server < 0) {
            perror("recv:");
            close(client_fd);
            client_fd = -1;
            close(server_fd);
            server_fd = -1;
            break;
        }
        else if (read_from_server == 0) {
            close(client_fd);
            client_fd = -1;
            close(server_fd);
            server_fd = -1;
            break;
        }
        priority = whatPriorityHasPkt();        
        insertInQueue(/* useful data */);
        removeFromQueue(TO_LOCAL, https_buf);
        send_to_client = send(client_fd, https_buf, read_from_server, 0);       
        // if send() returns error, close both 
        // sockets and break;
    }
}

risposta data 10.04.2016 - 19:17

fonte

Leggi altre domande sui tag data-structures algorithms networking proxy

Mocking di servizi Web di terze parti ODBC 3 più dichiarazioni rispetto a più connessioni

score 0 · Accepted Answer

Algoritmo QOS

Se possibile, puoi risolvere questo problema con più thread (o processi):

Un thread / processo riceve richieste e inserisce la richiesta nella coda con la priorità corretta.
Un altro thread / processo blocca in attesa di richieste che arrivano in una qualsiasi coda.

Quando il thread / processo si risveglia, invia i messaggi che si trovano nelle code, prima controlla la coda con priorità più alta, quindi la priorità successiva e così via.

Quando non ci sono messaggi lasciati in alcuna coda, il thread / processo si blocca di nuovo.

Struttura della coda dei messaggi simultanei

Il sistema operativo può fornire pipe, socket, file o code di messaggi. È possibile utilizzare queste strutture esistenti come code per la comunicazione tra processi:

Il (i) thread (i) del ricevitore / i processi scrivono la richiesta alla pipe, al socket, al file o alla coda dei messaggi.

Il thread di ascolto controlla simultaneamente tutti i pipe / socket / file in coda. Linux fornisce select per questo, Windows (Embedded) ha probabilmente qualcosa di simile - forse GetQueuedCompletionStatus

Quando si utilizzano i thread è disponibile una memoria condivisa. Se si dispone di operazioni atomiche "confronta e imposta" è possibile implementare (o utilizzare un'implementazione esistente di) una coda simultanea non bloccante ( qui è l'origine java da usare come ispirazione).

Se non si dispone di operazioni atomiche ma do ha blocchi / semafori / ... è possibile utilizzare una coda regolare / elenco collegato / buffer ciclico e utilizzare i blocchi per garantire che i puntatori vengano aggiornati in modo coerente.