Network coding switch

Abstract

O tráfego na internet está a crescer a um ritmo elevado. A ocorrência de Gargalos é, então, cada vez mais, uma ocorrência comum, resultando em atrasos no transporte de informação e em ineficiências. Isto é um problema em parte decorrente do paradigma tradicional “store and foreward”. Quando um pacote chega a um nó da rede, é armazenado numa fila de espera enquanto aguarda por uma decisão de encaminhamento. Quando existe tráfego elevado, as filas de pacotes crescem e os atrasos aumentam (assim como as perdas de pacotes). O conceito de Codificação na Rede procura oferecer um paradigma. A ideia fundamental é a seguinte: à capacidade de armazenamento e encaminhamento. Quando existe tráfego elevado, as filas de pacotes crescem e os atrasos aumentam (assim como a perda dos pacotes).O Conceito de Codificação na Rede procura oferecer uma alternativa de paradigma. A ideia fundamental é a seguinte: à capacidade de armazenamento e encaminhamento é adicionada aos nós a capacidade de combinar pacotes. Com esta Técnica é possível aumentar as taxas de transferência de informação, assim como a resiliência da rede. Para se entender melhor o conceito vajamos um exemplo. Considere um nó A e um B que comunicam através de um ponto de acesso S, num ambiente sem fios. Vejamos as transmissões necessárias para A enviar a e B, e para B enviar mensagem b para A, usando o modelo tradicional:1A envia a para S 2B envia b para S 3S faz broadcast de a para os dois nós4S faz broadcast de b para os dois nós Como se pode observar, foram necessárias quatro transmissões ao todo. Ao aplicarmos codificação na rede podemos poupar no número de transmissões da seguinte forma:1A envia a para S2B envia b para S3S combina as duas mensagens aplicando um XOR sobre elas e envia o resultado, a b, para A e BNo entanto, o exemplo demonstrado acima é um caso base de Linear Network Coding (LNC). Esta técnica de codificação consiste em dar capacidade, a cada nó da rede, de gerar novos pacotes através de combinações lineares de pacotes recebidos anteriormente, multiplicando-os por coeficientes escolhidos de um dado campo finito, sendo o mais comum de tamanho 28. Já no exemplo anterior, em que foi utilizado uma técnica de codificação através do XOR para codificar dois pacotes, o tamanho do campo finito era de 2. Sendo este, então, um caso particular.Porém, o LNC requere que os coeficientes utilizados nas combinações lineares sejam definidos e computados à prori por todos os nós da rede através de um algoritmo e de informação partilhada. Estamos, então, perante uma Limitação desta técnica que introduz um custo. Random Linear Network Coding (RLNC), uma variante da técnica de LNC, permite ultrapassar essa limitação. Isto é possível devido à sua natureza aleatória, significando que os coeficientes empregues nas combinações lineares são gerados deforma aleatória dado um certo campo finito. Esta propriedade garante com uma dada probabilidade, desde que o campo finito tenha um tamanho suficiente largo, de que as combinações lineares geradas sejam independentes entre si, com o intuito de aumentar esta probabilidade, RLNC introduz ainda a capacidade de recodificar pacotes, isto é, codificar pacotes que já foram codificados por outro nó na rede. Assim, quando o nó destinatário recebe uma quantidade suficiente de pacotes codificados que sejam linearmente independentes é possível descodificar os pacotes resolvendo as combinações lineares. Para tal, o destinatário tem de ter conhecimento dos coeficientes empregues nas combinações lineares. Então, por norma, em RLNC os coeficientes empregues nas combinações lineares. Então por norma, em RLNC os coeficientes são anexados ao cabeçalho do pacote, após a codificação deste, para que os coeficientes sejam levados até ao destinatário. Tanto a operação de codificação como de descodificação introduzem uma certa complexidade computacional proporcional ao tamanho dos dados a serem transmitidos. A técnica designada por Generation-based RLNC, permite solucionar este problema. Esta consiste em dividir em grandes quantidades de dados em blocos mais pequenos, chamados gerações. Então, tanto a operação de codificação como a de descodificação são aplicadas por geração e não na totalidade de dados. Existe uma grande quantidade de trabalho teórico relacionado com Network Coding e implementações ao nível da Camada aplicacional. No entanto, não existe nenhum trabalho concreto cujo objetivo tenha sido desenvolver e implementar uma solução de Network Coding diretamente no plano de dados da rede. Isto resulta do facto de os switches serem hardware especializado com função única, não permitindo a codificação de pacotes.Recentemente, no entanto, foram desenvolvidos switches programáveis, que removem esta restrição. Ao contrário dos switches tradicionais que são dispositivos fechados que seguem um conjunto de protocolos definidos pelo fabricante, estes switches permitem ao operador definir exatamente o processamento dos pacotes. Entretanto foi desenvolvida também uma linguagem de alto nível para programar estes novos switches programáveis, designada como P4. Em Suma, uma das limitações de todas as soluções de codificação em rede existentes prende-se com o facto de serem implementações em software. Esta Limitação é resultado de inflexibilidade dos planos de dados em hardware (switches e routers) tradicionais, que não permitem a combinação de pacotes. Nesta dissertação começamos a atacar este problema através da exploração dos novos switches em hardware programáveis, desenhando e implementando um switch que executa Random Linear Network Coding usando a versão mais recente da linguagem de programação de switches P4 (especificamente, P4_16). A avaliação da nossa solução oferece boas perspetivas para a possibilidade de deployment em hardware destas técnicas de codificação em rede, mas apresente também alguns dos desafios que permanecem em aberto para explorar em trabalho futuro.