Redes de computadores II - EEL879
Routing in Fat Trees
Introdução
Redes baseadas em Fat Trees são amplamente utilizadas no contexto de clusters de computação de alto desempenho para efetuar a comunicação entre os processadores (endpoints na rede). Esse modelo garante comunicação eficiente e permite conectar grande quantidade de endpoints através de switches.
RIFT é um protocolo de roteamento especializado para redes baseadas em Fat Trees, cujas características e funcionamento serão exploradas neste texto.
Fat trees
O que são
O conceito de Fat-Trees foi inicialmente elaborado pelo pesquisador do MIT Charles E. Leiserson em 1985 com intuito de superar as dificuldades de construir uma rede de roteadores com árvores regulares. A figura a seguir mostra uma estrutura de interconexão em uma árvore binária normal:
Observando a figura, torna-se evidente o problema de congestionamento dos enlaces (ou arestas) mais próximas do topo: basta perceber que dada uma folha qualquer dessa árvore, a quantidade de folhas que ela pode se comunicar quase dobra à medida que subimos em cada nível da árvore.
Partindo da folha indicada e subindo um nível, tem-se apenas uma outra folha disponível para comunicação. No segundo nível, esse número sobe para três. Com esse exemplo, podemos inferir que o número de folhas com possibilidade de comunicação é de 2n-1, onde n é o nível que estamos analisando a partir da folha inicial da árvore binária. Generalizando para qualquer grau de árvore ( ternária, quaternária, etc.), temos que o número de folhas com possibilidade de comunicação é de kn-1 , onde k é o grau da árvore e n é o nível a partir de uma folha.
Sendo assim, a utilização dessa estrutura para redes de computadores sobrecarrega os enlaces de nível mais alto da árvore, uma vez que eles mediam a comunicação entre o maior número de pares de sistemas finais (assumindo que todos os sistemas finais têm igual probabilidade de se contactar). Além disso, um grande problema com essa estrutura é o grande efeito negativo de falhas em nós de níveis altos. Se um enlace conectado à raiz da árvore sofrer uma falha, a árvore irá se particionar em duas, pois metade das folhas não poderão se comunicar. As Fat-Trees visam mitigar esses dois pontos negativos de trabalhar com árvores.
Uma Fat-Tree aumenta o número de enlaces quanto maior a distância das folhas (assim como uma árvore real que veríamos na natureza). Essa propriedade faz com que ambos os problemas encontrados anteriormente sejam sanados.
A ideia é que as arestas no nível n devem ter o dobro da capacidade das de nível n-1 (nesse caso as folhas estão no nível zero). Na realidade, como foi discutido, isso é implementado replicando os enlaces. Dessa forma, a estrutura não sofre com pontos únicos de falha e aumenta o throughput de enlaces mais ocupados perto da raiz da árvore. Nas Fat-Trees, os processadores estão localizados nas folhas de uma árvore binária completa, e os nós internos são comutadores de pacotes.
Charles E. Leiserson, criador das Fat-Trees, chegou a afirmar em seu artigo inovador: “Fat-trees são uma família de estratégias de interconexão de uso geral que utilizam efetivamente qualquer quantidade de recursos de hardware dedicados à comunicação.” . Essa afirmação se sustenta até os dias de hoje, pois de fato é possível provar que para um determinado volume físico de hardware, nenhuma estrutura rede é muito melhor do que uma Fat-Tree.
Funcionamento do RIFT
Para entender o funcionamento do RIFT, é necessário compreender como funcionam os roteamentos por distance vector e por link-state.
Roteamento por vector de distância
No roteamento por distance vector, que utiliza o algoritmo Bellman-Ford, cada nó anuncia os comprimentos dos caminhos que conhece (inicialmente só seus vizinhos) a todos seus vizinhos, que por sua vez incorporam essas distâncias a sua tabela de roteamento, incrementando-as. Esse processo é executado repetidamente em todos os nós até que as tabelas de roteamento convirjam. Nessa modalidade de roteamento, os nós não têm conhecimento sobre a topologia da rede além das distâncias de si para cada nó.
Roteamento por estado de enlace
No roteamento por link-state, que utiliza do algoritmo Dijkstra, cada nó mantém uma base de dados contendo todos os enlaces da rede (inicialmente só os adjacentes) e anuncia suas informações através do algoritmo de inundação. Isso é feito até que as bases de dados de todos os nós estejam iguais. Nessa modalidade de roteamento, todos os nós conhecem a topologia da rede (sabem todos os enlaces e seus “comprimentos”).
Natureza híbrida do RIFT
Primeiramente, o RIFT necessita de uma topologia com um senso de “cima e baixo”, sendo que os nós com maior profundidade estariam mais “abaixo na árvore” e vice versa. A abordagem do RIFT não pode ser comparada puramente à de link-state nem distance vector, mas sim como um híbrido dos dois, mais especificamente “link-state em direção à raiz" e “distance vector em direção às folhas”. Os níveis inundam suas informações link-state em direção aos níveis superiores enquanto cada nó gera rotas default e inunda-as em direção aos níveis inferiores.
Em condições normais, RIFT inunda informação link-state para os níveis superiores ao nó para que cada nível obtenha a topologia completa dos níveis abaixo dele. Além disso, apenas uma rota default é enviada aos níveis inferiores ao nó, utilizando inundação, para evitar que seja feito um update por adjacência. Dessa forma, as informações são propagadas de modo que os nós não recebem a mesma informação de múltiplas direções diferentes ao mesmo tempo, além de dispensar a necessidade de desempate de informações de alcançabilidade de múltiplas direções.
Arquitetura
Estrutura Fat tree em data centers
As malhas de comutação de fat trees são muito implementadas em Data Centers da atualidade. Esta arquitetura foi inicialmente desenvolvida visando a melhora de desempenho do tráfego entre dispositivos em um mesmo data center, por meio da redução do número de saltos entre quaisquer dois dispositivos na rede.
Para que tal objetivo seja alcançado, cada switch de acesso na rede tem uma conexão direta com cada switch de interconexão. Dessa forma, todos os dispositivos de acesso e do backbone estão a um salto de distância.
A arquitetura Fat Tree, também chamada de spine-leaf, possui duas camadas, uma de núcleo e agregação e outra de acesso. A primeira, a camada spine, é constituída por comutadores de interconexão, os quais são responsáveis por interligar todos os comutadores de acesso. Na prática, pode-se afirmar que a camada spine atua como backbone da rede. Já a segunda camada, chamada de leaf, é composta por switches de acesso que podem ser conectados com servidores, roteadores de borda, balanceadores de carga e firewalls.
Como podemos perceber na figura, cada switch de acesso está conectado a cada switch de interconexão. Nesse sentido, podemos balancear a carga da rede escolhendo um caminho aleatório entre dispositivos. Além disso, esta malha completa faz com que não existam pontos únicos de falha, sendo que, se um switch de interconexão parar, a perda de desempenho do data center será mitigada.
Imagem adaptada de https://dc.mynetworkinsights.com/what-is-three-tier-architecture-and-fat-tree-architecture
Outras vantagens da arquitetura spine-leaf são a facilidade de sua expansão e a previsibilidade da latência enfrentada. Nesse âmbito, um novo comutador de acesso sempre pode ser adicionado a rede, ao conectá-lo a cada comutador da camada spine. Ademais, servidores que estão em folhas diferentes da rede sempre necessitam de um mesmo número de saltos para se comunicarem, promovendo, assim, menor variação na latência.
Conclusão
Em aplicações que utilizam redes de switches em árvores, como em clusters de supercomputadores, o RIFT permite a comunicação entre endpoints de forma a reduzir o congestionamento nos nós mais próximos à raiz e reduzir o impacto de ocasionais falhas em enlaces. Esse tipo de roteamento tem papel fundamental na garantia de comunicação eficiente em inúmeras redes de alta performance.
